[Powered by Google Translate] [Týždeň 6] [David J. Malan] [Harvard University] [To je CS50.] [CS50.TV] 

To je CS50, a to je začiatok týždňa 6, takže pár nových nástrojov sú teraz k dispozícii pre vás využiť, z ktorých prvá sa nazýva CS50 štýl. Kurzy sú, ak ste rovnako ako ja, alebo niektorý z výučbových chlapíkov, pravdepodobne ste videli program, ktorého štýl vyzerá trochu niečo takého. Možno začnete rezať niektoré rohy neskoro v noci, alebo budete riešiť neskôr, a potom sa TF alebo CA príde počas úradných hodín. Potom je to pre nás ťažké čítať. No, tento kód je syntakticky správny, a to bude kompilovať, a to bude skutočne spustiť. Ale to rozhodne nie je 5 pre štýl. 

Ale teraz, keď ideme do tohto adresára tu- a všimnite si, že mám conditions2.c- a ja som spustiť tento nový príkaz, style50, na tomto súbore conditions2.c, Enter, Všimnite si, že to ma informoval, že to bolo štylizované. Gedit si všimol, že súbor bol zmenený na disku, a keď klepnem znovu načítať, sú všetky vaše problémy teraz automatizovaný. [Potlesk] To je jedna z vecí, ktoré sme urobili tento víkend. Si uvedomiť, že je nedokonalé, pretože tam sú niektoré kód že to jednoducho nebude môcť štylizovať dokonale, ale uvedomte si, to je teraz nástroj, ktorý môžete využiť ak len upratať niektoré z chybne umiestnené zloženými zátvorkami a podobne. 

Ale závažnejšie je teraz CS50 Check. S CS50 kontroly, môžete skutočne vykonávať rovnaké korektnosť skúšky na vlastný kód, ktorý učebné chlapi sú schopní. To je nástroj príkazového riadku, ktorý je dodávaný so v spotrebiči akonáhle urobiť update50 ako za PSet 4 špecifikácie a použiť ju v podstate takhle. Môžete spustiť príkaz check50. Potom si odovzdať argument príkazového riadku, alebo viac všeobecne známy ako spínač alebo značkou. Všeobecne platí, že sú veci, ktoré majú pomlčky tzv switch k programu z príkazového riadku, tak-c určuje kontroly, ktoré chcete spustiť. 

Testy, ktoré chcete spustiť sa jednoznačne identifikujú podľa tohto reťazca, 2012/pset4/resize. Inými slovami, že je to len ľubovoľný, ale jedinečný reťazec ktoré používame k jednoznačnej identifikácii PSet 4 je korektnosť skúšky. A potom určíte priestor oddelený zoznam súborov, ktoré chcete nahrať na CS50 Kontrola pre analýzu. Napríklad, keď som ísť do mojej riešenie tu pre resize.c- dovoľte mi, aby som otvoriť väčšie okno terminálu- a idem do toho a spustiť povedzme check50-c 2012/pset4/resize, a potom som ísť dopredu a zadať názvy súborov, resize.c, a potom stlačte kláves Enter, to komprimuje, to nahrávanie, kontroluje, a ja som nedokázal veľa testov. Ten v červenom hore vľavo hovorí, že resize.c a bmp existujú. To bol test. To bola otázka, ktorú sme požiadaní. A je to nešťastné, pretože odpoveď bola falošná. Biela Text pod ňou hovorí, že očakáva, že bmp.h existovať, a že je to jednoducho moja chyba. Zabudol som nahrať, tak som potrebné nahrať oba súbory, resize.c a bmp.h. Ale teraz všimnete všetkých ostatných testov sú v žltej farbe, pretože ste nespustili, a tak smiley tvár je zvislá, pretože to ani šťastný, ani smutný, ale musíme k náprave tohto problému v červenej farbe, než tie ostatné kontroly pobeží. 

Dovoľte mi, aby som tento problém vyriešiť. Dovoľte mi, aby som oddialiť a znova to, tentoraz s bmp.h tiež na príkazovom riadku, zadajte, a teraz, keď všetko pôjde dobre, to bude kontrolovať a vráti výsledok of-zadržte dych- celý zelený, čo znamená, že som si naozaj dobre PSet 4 tak ďaleko. Môžete vidieť a vyvodiť z popisného textu tu presne to, čo sme to my, testovaný. Testovali sme najprv urobiť súbory existujú? My potom testovaný robí resize.c kompilácie? Potom sme testovali to meniť veľkosť 1x1 pixel BMP, keď n, zmenu veľkosti faktor, je 1. Teraz, ak máte tušenie, čo n je, budete akonáhle sa ponoriť do PSet 4, ale že jednoducho je zdravý rozum skontrolujte, či nie ste zmenu veľkosti obrázok vôbec v prípade, že zmeny veľkosti činiteľ je 1. Ak naopak, to zmení na 1x1 pixel 1x1 pixelov BMP na 2x2 správne keď n je 2, potom podobne, moje tvorí zodpovedajúcim spôsobom. 

Stručne povedané, je to znamenalo, jeden, prijmú kríženie prstov z rovnice P pred vami odošlite PSet. Budete presne vedieť, aké sú vaše TF bude čoskoro vedieť keď idete o podaní niektoré z týchto problémových súborov, a tiež pedagogickej motivácia je naozaj dať možnosť pred vami tak, že keď viete, a priori že je chyba v kóde a testy, ktoré nie sú odovzdané, si môžete dať k účinnejšiemu včas do prednej strany k riešeniu týchto problémov skôr než stratiť body, získať spätnú väzbu od svojho TF, a potom ísť, "Ahh," ako by som mal to zistili. Teraz aspoň tú nástroj, ktorý vám pomôže zistiť, že. Nebude to poukázať, kde je chyba, ale to vám povie to, čo je príznačné to. 

Teraz si uvedomiť, že testy nie sú nevyhnutne vyčerpávajúce. Len preto, že dostanete obrazovku plnú zelenej smajlíky neznamená, že váš kód je perfektný, ale to neznamená, že prešiel niektoré testy predpísané špec. Niekedy sme sa neuvoľní kontroly. Napríklad, detektívka, jeden z aspektov PSet 4, je druh sklamaním, keby sme vám odpoveď na otázku, čo to je, a tam je niekoľko spôsobov, ako odhaliť kto je osobou v tej červenej hluku. Spec bude vždy uvedené, v budúcnosti PSet 5 dopredu čo kontroluje existujú pre vás. Určite ste si všimli, že je to biele URL dole. Pre túto chvíľu, je to len diagnostická výstup. Ak navštívite túto adresu URL, dostanete veľa bláznivých, záhadné správy že ste vítaní prezrieť, ale je to väčšinou pre zamestnancov takže môžeme diagnostikovať a ladenie chýb v check50 sám. 

Bez okolkov, poďme sa presunúť na miesta, kde sme skončili. CS50 knižnica sme považovali za samozrejmosť niekoľko týždňov, ale potom minulý týždeň, sme začali strhnutím jedného z vrstiev nej. Začali sme dávať stranou reťazec v prospech čo miesto? [Študenti] Char. Char *, ktorý bol char * po celú tú dobu, ale teraz nemáme predstierať, že je to skutočný dátový typ string. Skôr, je to už synonymom druhov pre char *, a reťazec je postupnosť znakov, tak prečo to zmysel reprezentovať reťazca ako * char s? Čo char * predstavujú v rámci tejto koncepcie reťazca? Jo. >> [Študent] Prvý znak. Dobrý, prvý znak, ale nie úplne prvý znak. Sú to-[Študenti] Address. Dobrý, adresa prvého znaku. Všetko, čo je potrebné na reprezentáciu reťazec v pamäti počítača je len jedinečná adresa jeho prvého bajtu. Nemusíte ani vedieť, ako dlho to je pretože ako môžete zistiť, že sa dynamicky? [Študent] Dĺžka reťazca. Môžete volať dĺžku reťazca, vynikajúci, ale ako sa dĺžky reťazca prácu? Čo to robí? Jo. [Študent] Pokračujte, kým sa dostanete na nulový znak. Jo, presne tak, to len opakuje s pre slučky, zatiaľ čo slučka, čo od * do konca, a koniec je reprezentovaný z \ 0, tzv znak NUL, núl, nesmie zamieňať s hodnotou null, čo je ukazovateľ, ktorý príde v rozhovore dnes znova. 

Sme zlúpnuť vrstvu GetInt, a potom sme sa pozreli na GetString, a pripomínajú, že obe tieto funkcie, alebo naozaj, GetString, bolo pomocou určitej funkcie skutočne analyzovať, to je, čítať alebo analyzovať, vstup užívateľa. A čo to bolo nové funkcie? Scanf alebo sscanf. Je to vlastne príde v niekoľkých rôznych príchutiach. Tam je scanf, tam sscanf, tam je fscanf. Pre túto chvíľu, aj keď, poďme zamerať na jeden najviac ľahko ilustrované, a nechaj ma ísť dopredu a otvoriť v prístroji súbor takto, scanf1.c. To je super jednoduchý program, ale že robí niečo, čo sme ešte nikdy neurobili bez pomoci CS50 knižnice. To dostane int od užívateľa. Ako to funguje? No, v riadku 16 tam, Všimnite si, že sme deklarovať int s názvom X, a na tomto mieste v príbehu, to, čo je hodnota x? [Nepočuteľné Študent odpoveď] [David M.] Právo, kto vie, niektoré odpadky hodnota potenciálne, tak v 17, sme len povedať užívateľa daj mi číslo, prosím, a krok 18 je miesto, kde to začína byť zaujímavé. Scanf Zdá sa, že požičať nápad z printf v tom, že používa tieto formátovacie kódy v úvodzovkách. % D je samozrejme desatinné číslo. Ale prečo som okolo v & X miesto len x? Prvá z nich je správna. Jo. [Nepočuteľné Študent odpoveď] Presne, v prípade, že cieľom tohto programu, ako funkcie GetInt sám, je získať int od užívateľa môžem odovzdať funkcie všetky premenné chcem, ale keď nemám okolo nich odkazom alebo adresy alebo ukazovateľ, všetko synonymom pre dnešné účely, potom táto funkcia nemá možnosť zmeniť obsah tejto premennej. To by odovzdať kópiu rovnako ako buggy verzii swapu že sme hovorili o niekoľkých časoch teraz. 

Ale namiesto toho, tým, že robí a x, som doslova okolo v čom? [Študent] adresa. >> Adresu x. Je to ako kreslenie mapy pre funkciu nazvanú scanf a tú hovorí, sú smery na kusu pamäte v počítači že môžete ísť ukladať nejaké celé číslo a Aby sscanf do teraz robiť, že čo operátor, čo kus syntax ich bude musieť použiť aj keď nemôžeme vidieť, pretože niekto iný napísal túto funkciu? Inými slovami - čo to je? [Študent] X čítať. Tam to bude nejaké čítanie, ale len s ohľadom na x tu. Ak scanf je odovzdaná adresu x, syntakticky, čo je prevádzkovateľ povinný niekde existujú vnútri vykonávanie scanf je tak, že scanf môže skutočne napísať číslo 2 na túto adresu? Jo, takže *. Pripomeňme si, že * je naša dereferencia operátor, čo v podstate znamená tam. 

Akonáhle bola odovzdaná adresu, ako je tomu tu, scanf je pravdepodobne Ak sa skutočne pozrel okolo jeho zdrojový kód, robí * x alebo ekvivalent skutočne ísť na túto adresu a dať nejakú hodnotu tam. Teraz, ako na to, ako scanf dostane vstup z klávesnice, budeme mávať rukami von pre dnešok. Len predpokladať, že operačný systém umožňuje sscanf hovoriť na užívateľa klávesnice, ale v tomto okamihu teraz v súlade 19, keď sme jednoducho vytlačiť x, sa zdá byť prípad že scanf dal int v x. To je presne to, ako scanf funguje, a pripomínajú minulý týždeň to je presne to, ako GetString a GetInt a jej ďalšie rodina funkcií nakoniec funguje, aj keď s miernym rozptylu ako sscanf, čo znamená, že skenovanie reťazec namiesto klávesnice. Ale poďme sa pozrieť na malú odchýlkou ​​to. V scanf2, som vlastne podelal. Čo je zle a ja skryť komentár, ktorý vysvetľuje, ako veľa- Čo je zle s týmto programom, verzia 2? Buďte tak technické, ako je to možné dobe. Vyzerá to celkom dobre. Je to pekne odsadený, ale- v poriadku, ako sa o poďme strih do kratších otázky? Riadok 16. Čo je to linka 16 robí v presnom, ale technické angličtiny? Získanie trochu trápne. Áno, Michael. [Študent] Je to s poukazom na prvé písmeno reťazca. 

Dobre, úzkym. Dovoľte mi, aby som trik, že trochu. S poukazom na prvé písmeno reťazca, s ktorým sa premenná s názvom vyrovnávacia pamäť že bude smerovať k prvému adresu reťazca, alebo skôr, bude to ukazovať konkrétne na char. Všimnite si, že to nie je v skutočnosti ukazuje všade, pretože neexistuje žiadny operátor priradenia. Nie je znamienko rovná sa, takže všetko, čo robia, je rozdelenie premennej tzv vyrovnávacej pamäte. Stáva sa, že je 32 bitov, pretože je to ukazovateľ, a obsah pufra pravdepodobne nakoniec bude obsahovať adresu char, ale teraz, čo pufer obsahuje? To sú len niektoré falošné, kto vie, niektoré odpadky hodnota, pretože sme explicitne inicializovať, takže sme nemali nič predpokladať. Dobre, takže teraz linka 17 je-čo linka 17 robiť? Možno, že bude ohrievať toto hore. To vytlačí reťazec, nie? Tlačí String prosím. 

Linka 18 je trochu oboznámený teraz v tom, že sme práve videli, rozptyl tohto ale s iným formátu kódu, tak v riadku 18, hovoríme scanf je tu adresa bloku pamäte. Chcem, aby si, aby vás v reťazci, ako vyplýva z% s, ale problém je, že sme neurobili pár vecí tu. Čo je to jeden z problémov? [Študent] Snaží sa dereferencia ukazovatele null. Dobré, null, alebo len inak neznámy ukazovatele. Tie podal scanf adresu, ale práve si povedala pred chvíľou táto adresa je asi nezmyselné hodnoty, pretože sme nemali vlastne priradiť ju k ničomu, a tak hovoríte scanf účinne ísť dať reťazec tu, ale nevieme, kde tu ešte je, takže sme sa vlastne pridelené pamäte pre vyrovnávaciu pamäť. Navyše, to, čo ste tiež ani hovoriť scanf? Predpokladám, že to bol kus pamäte, a to nebolo odpadky hodnotu, ale stále nehovoríš scanf niečo dôležité. [Študent] Kde to vlastne je, ampersand. Ampersand, takže v tomto prípade, je to v poriadku. Vzhľadom k tomu, vyrovnávacia pamäť je už deklarovaný ako ukazovateľ s * kus syntaxe, nepotrebujeme použiť ampersand pretože je to už adresu, ale myslím, že som to počul sem. [Študent] Ako je to veľké? Dobré, my nehovoríš scanf, aký veľký tento buffer, čo znamená, že aj keď sa vyrovnávacia ukazovateľ, hovoríme scanf, dal reťazec tu, ale tu by mohlo byť 2 bytov, mohlo by to byť 10 bytov, mohlo by to byť megabajt. Scanf nemá ani potuchy, a pretože to je kus pamäte pravdepodobne, že to nie je reťazec doteraz. Je to len reťazec akonáhle písať znaky a \ 0 na tomto kuse pamäti. Teraz je to len nejaký kus pamäte. Scanf nebude vedieť, kedy prestať písať na túto adresu. 

Ak si spomeniete, niektoré príklady v minulosti, keď som náhodne písané na klávesnici sa snaží pretečeniu vyrovnávacej pamäte, a hovorili sme o tom v piatok presne to. Ak protivník nejako vstrekuje do svojho programu oveľa väčšie slovo alebo veta alebo fráza potom ste čakali, môžete prekročení kus pamäte, ktorý môže mať zlé následky, ako prevzatie celého programu samotného. Musíme to opraviť nejako. Dovoľte mi, aby som oddialiť a ísť do verzie 3 tohto programu. To je trochu lepšie. V tejto verzii, všimnete rozdielu. V riadku 16, som opäť deklarovať premennú s názvom vyrovnávacej pamäte, ale čo je to teraz? Je to rad 16 znakov. To je dobre, pretože to znamená, že môžem teraz povedať, scanf Tu je skutočný kus pamäte. Môžete takmer myslieť polí ako ukazovatele teraz, aj keď sú v skutočnosti ekvivalentné. Budú sa správajú odlišne v rôznych kontextoch. Ale je to určite pravda, že vyrovnávacia pamäť je odkazovanie 16 po sebe idúcich znakov, pretože to je to, čo pole je a bol niekoľko týždňov teraz. 

Tu, hovorím scanf tu kus pamäte. Tentokrát, je to vlastne kus pamäte, ale prečo je tento program stále využiteľný? Čo sa deje stále? Ja som povedal, daj mi 16 bajtov, ale- [Študent] Čo keď typ vo viac ako 16? Presne, čo keď používateľ zadá do 17 znakov alebo 1700 znakov? V skutočnosti, uvidíme, či nemôžeme výlet cez túto chybu hneď. Je to lepšie, ale nie je dokonalý. Nechaj ma ísť napred a spustite make scanf3 zostaviť tento program. Dovoľte mi, aby som bežať scanf3, String prosím: ahoj, a zdá sa, že bude v poriadku. Nechaj ma to skúsiť mierne dlhšia jeden, hello there. Dobre, poďme si hello there ako sa dnes máte, Enter. Získanie druh šťastie tu, povedzme, hello there ako sa máš. Sakra. Dobre, takže máme šťastie. Poďme sa pozrieť, či nemôžeme napraviť. Nie, to nebude, aby som kopírovať. Skúsme to znovu. Dobre, pripravte sa. Uvidíme, ako dlho môžem predstierať, že sa sústrediť a pritom robí. Sakra. To je dosť vhodné, v skutočnosti. Tam ideme. Point vykonaná. 

To nepríjemné keď to tiež je, že je tiež jeden zo zdrojov veľkom zmätku pri písaní programov, ktoré majú chyby, pretože sa prejavujú len raz za čas niekedy. Skutočnosť je taká, že aj keď váš kód je úplne rozbité, to by mohlo byť úplne rozbité raz za čas pretože niekedy, v podstate, čo sa stane, je, že operačný systém prideľuje trochu viac pamäte, než je skutočne nutné z akéhokoľvek dôvodu, a tak nikto iný využitie pamäte bezprostredne po kuse 16 znakov, takže ak idete na 17, 18, 19, bez ohľadu na, že to nie je tak veľký problém. Teraz, počítač, aj keď to nie je zlyhanie v tomto bode, môže v konečnom dôsledku používať byte číslo 17, 18, alebo 19 pre niečo iné, na ktorom mieste si údaje, ktoré ste tam dal, aj keď príliš dlho, dostane prepísané potenciálne iným funkcií. Nie je to nutne ísť zostať neporušený, ale to nemusí nutne spôsobiť seg poruchu. Ale v tomto prípade, som konečne poskytol dostatok znakov že som v podstate prekročila svoj segment pamäte, a bum, operačný systém povedal, "Je mi ľúto, že to nie je dobré, Segmentation fault." 

A uvidíme, či to, čo teraz zostane tu v mojom adresári, Všimnite si, že som tento súbor tu, jadro. Všimnite si, že toto je opäť nazýva core dump. Je to v podstate súbor, ktorý obsahuje obsah vášho programu do pamäti v mieste, v ktorom je havaroval, a len skúsiť malý príklad tu nechaj ma ísť sem a spustiť gdb na scanf3 a potom zadať tretí argument s názvom core, a všimnite si, že keď som tu vypísať kód, budeme môcť ako zvyčajne s gdb, kto prechádzal tohto programu, a môžem spustiť, a akonáhle som narazila-ako s krokom príkaz do gdb- akonáhle som narazila na potenciálne buggy riadok po zadaní v obrovskej reťazca, Budem schopný skutočne identifikovať ho sem. Viac informácií o tomto, keď v sekcii, pokiaľ ide o core dump a podobným spôsobom, ktorý je možné skutočne hrabať okolo vnútri jadra skládky a vidieť, čo riadok programu sklamal. Akékoľvek otázky potom na ukazovateli a adresy? Pretože dnes, budeme začať užívať za samozrejmé, že tieto veci existujú a presne vieme, čo sú zač. Áno. 

[Študent] Ako to, že nemusel dať ampersand vedľa časti- Dobrá otázka. Ako to, že som nemal dať ampersand vedľa poľa znakov, ako som to urobil skôr s väčšinou z našich príkladov? Stručná odpoveď je polia sú trochu zvláštne. Môžete takmer premýšľať vyrovnávacej pamäte ako by v skutočnosti bol adresu, a to len tak sa stane, že je pravda, že hranatá zátvorka notácie je pohodlie, takže môžeme ísť do držiaka 0, držiakom 1, držiak 2, bez toho aby museli používať * zápis. To je trochu lož, pretože pole a ukazovatele sú v skutočnosti, trochu iná, ale oni môžu často, ale nie vždy používajú zameniteľné. Stručne povedané, ak funkcia očakáva ukazovateľ na kus pamäti, môžete buď odovzdať adresu, ktorá bola vrátená malloc, a uvidíme, malloc zase netrvalo dlho, alebo môžete odovzdať názov poľa. Nemusíte robiť ampersand s poľami, pretože sú už v podstate ako adresy. To je jedna výnimka. Hranaté zátvorky, aby boli zvláštne. 

Mohli by ste dať ampersand vedľa vyrovnávacej pamäte? Nie v tomto prípade. To nebude fungovať, pretože, opäť, z tohto rohu veci kde pole nie sú tak vlastne adries. Ale my snáď vrátiť k tomu onedlho s ďalšími príkladmi. Poďme sa snaží vyriešiť problém tu. Máme štruktúru dát, ktoré sme sa pomocou dlhšiu dobu známe ako pole. Vec v bode, že je to to, čo sme práve mali. Ale polia majú nejaký upsides a tienisté stránky. Polia sú pekné, prečo? Čo je jedna vec, ktorá sa vám páči, a to v rozsahu vám páči pole-o pole? Čo je vhodné o nich? Čo je to presvedčivý? Prečo sme sa predstaviť je na prvom mieste? Jo. [Študent] Môžu uložiť veľké množstvo dát, a nemusíte používať celú vec. Môžete použiť časť. Dobré, s radom môžete uložiť veľké množstvo dát, a nemusíte nutne používať všetko, takže môžete overallocate, ktoré by mohli byť užitočné, ak nemáte vopred vedieť, koľko niečo očakávať. 

GetString je dokonalým príkladom. GetString, napísal nám, nemá ani potuchy, koľko znakov sa očakávať, takže skutočnosť, že môžeme prideliť kusy súvislej pamäte je dobrá. Pole tiež vyriešiť problém, čo sme videli pred pár týždňami dnes kde váš kód začína prešla do niečoho veľmi zle navrhnutý. Pripomeňme si, že som vytvoril študent štruktúru nazvanú David, a potom, že bol vlastne alternatíva, aj keď, , Aby s premennou s názvom meno a ďalšie premenné s názvom, myslím, dom, a ďalšie premenné volal ID, pretože v tomto príbehu, ktorý som potom chcel predstaviť niečo iné Páči Roberta do programu, tak som sa rozhodol počkať, Musím premenovať tieto premenné. Hovorme moja NAME1, ID1, house1. Hovorme Robova name2, house2, ID2. Ale potom počkať, čo o Tommym? Potom sme mali ďalšie tri premenné. Zaviedli sme niekoho iného, ​​štyri sady premenných. Svet začal dostať chaotický veľmi rýchlo, tak sme zaviedli structs, a čo je presvedčivá struct? Čo struct C nechať urobiť? Je to naozaj trápne dnes. Čo? >> [Nepočuteľné Študent odpoveď] Jo, konkrétne typedef umožňuje vytvoriť nový dátový typ, a struct, že struct kľúčové slovo, umožňuje zapouzdřit koncepčne súvisiace kúsky dát dohromady a potom im hovoria niečo ako študenta. 

To bolo dobre, pretože teraz môžeme modelovať oveľa viac druh koncepčne konzistentné pojem študenta v premennej skôr než svojvoľne mať jeden pre reťazec, jeden identifikátor, a tak ďalej. Polia sú pekné, pretože nám umožní začať upratovať náš kód. Ale čo je nevýhoda teraz z poľa? Čo môžete to urobiť? Jo. [Študent] Musíte vedieť, ako je veľký. Musíte vedieť, ako je to veľké, takže je to trochu bolesti. Tí z vás, s predchádzajúcim programovacím skúsenosti vieme, že v mnohých jazykoch, ako Java, môžete požiadať kus pamäte, konkrétne pole, aký veľký ste, s dĺžkou, majetku, tak povediac, a to je naozaj pohodlné. V jazyku C, nemôžete ani volať strlen na generické pole pretože strlen, ako slovo znamená, je len pre reťazce, a je možné zistiť dĺžku reťazca, pretože v tomto ľudskej konvencie mať na \ 0, ale celú škálu, viac druhovo, je len kus pamäte. Ak je to pole ints, že to nebude mať nejaký špeciálny znak Na konci na vás čaká. Musíte si uvedomiť, dĺžku poľa. Ďalšou nevýhodou pole dvíha hlavu v GetString sám. Čo je ďalší nevýhoda pole? Pane, len ty a ja dnes. [Nepočuteľné Študent odpoveď] >> To je to, čo? Je to vyhlásil na zásobníku. Dobre, vyhlásil na zásobníku. Prečo nemáš rád, že? [Študent] Vzhľadom k tomu, že dostane znova. To dostane znova. Dobre, ak používate pole alokovať pamäť, nemôžete, napríklad, vrátiť, pretože je to na zásobníku. Dobre, že je to nevýhoda. A čo takto jeden ďalší s radom? Akonáhle prideliť ju, si trochu skrutkované, ak potrebujete viac miesta ako pole má. 

Potom sme zaviedli, obnovu, malloc, ktorý nám dal schopnosť dynamicky alokovať pamäť. Ale čo keď sme sa snažili iný svet dohromady? Čo keď budeme chcieť riešiť niekoľko týchto problémov tak sme namiesto toho, moje pero zaspal tu- čo keby sme namiesto toho chceli v podstate vytvoriť svet, ktorý je už takto? To je pole, a, samozrejme, tento druh zhoršuje, akonáhle sa dostaneme na koniec poľa, a teraz už majú priestor pre ďalšie celé číslo alebo iný znak. Čo keď sme trochu preventívne povedať dobre, prečo nie my relaxovať túto požiadavku, že všetky tieto kúsky pamäte byť súvislé chrbtom k sebe, a prečo nie, keď som potrebné int alebo char, Daj mi priestor pre jedného z nich? A keď som potrebovať ďalšie, daj mi ďalší priestor, a keď som potrebovať ďalšie, daj mi ďalší priestor. Výhodou, ktorá teraz je, že ak niekto iný berie pamäť tu, žiadny veľký problém. Chcel by som tento ďalší kus pamäte tu a potom toto. 

Teraz, len úlovok je, že to takmer pocit, ako by som sa celá partia rôznych premenných. Tento pocit piatich rôznych premenných potenciálne. Ale čo keby sme ukradol nápad z reťazcov kedy sme nejako prepojiť tieto veci dohromady koncepčne, a čo keď som to urobil? To je môj veľmi zle vypracovaný arrow. Predpokladajme však, že každý z týchto blokov z pamäte ukázal na druhý, a ten chlap, ktorý nemá súrodencov na jeho pravej, nemá takú šípku. To je v skutočnosti to, čo sa nazýva prepojený zoznam. To je nová dátová štruktúra, ktorá nám umožňuje prideliť kus pamäte, potom ďalší, potom ďalší, potom ďalšie, kedykoľvek chceme počas programu, a my sme si, že sú všetci nejako súvisiace doslova priviazať je dohromady, a to sme urobili, že obrazovo sem s šípkou. Ale v kóde, čo by ich mechanizmus, cez ktorý by ste sa mohli nejako spojiť, skoro ako Scratch, jeden kus na iný kus? Mohli by sme použiť ukazovateľ, nie? Vzhľadom k tomu, naozaj šípka, ktorá sa deje v ľavom hornom námestí, ten chlap tu k tomuto, by mohli obsahovať vnútri tohto štvorca nie len niektoré ints, nie len niektoré char, ale čo keď som vlastne pridelené niečo naviac priestor tak, že teraz, Každý z mojich kúsky pamäti, aj keď to bude stáť mňa, teraz vyzerá trochu obdĺžnikový, kde jeden z kúskov pamäte sa používa pre množstvo, ako je číslo 1, a potom, ak ten chlap ukladá počet 2, Tento ďalší kus pamäte sa používa pre šípkou, alebo konkrétnejšie, ukazovateľ. A že som chcete uložiť číslo 3 tu, keď som použiť to ukázať na toho chlapca, a teraz ten chlap, predpokladajme, že chcem len tri takéto kúsky pamäti. Budem čiaru cez to, že uvedením null. Neexistuje žiadny ďalší znak. 

Naozaj, je to, ako môžeme ísť o implementácii niečo, čo sa nazýva prepojený zoznam. Spájať zoznam je nová dátová štruktúra, a to odrazový mostík k oveľa obsiahlejší dátové štruktúry, ktoré začnú riešiť problémy po vzore Facebook typu problémov a Google typu problémov kde máte veľké dátové súbory, a to už seká ju uložiť všetko súvisle a použiť niečo ako lineárny hľadanie alebo dokonca niečo ako binárne vyhľadávanie. Ak ešte lepšie jazdné doby. V skutočnosti, jeden z svätých Grails budeme hovoriť o ešte tento týždeň, alebo budúci je algoritmus, ktorého hrací čas je konštanta. Inými slovami, to je vždy na rovnakú dobu bez ohľadu na to aký veľký je vstup, a že by bolo naozaj presvedčivé, dokonca viac tak ako niečo logaritmickej. Čo je to na obrazovke tu? Každý z obdĺžnikov je presne to, čo som práve nakreslil rúk. Ale to, čo celú cestu na ľavej strane je špeciálna premenná. Je to bude jediný ukazovateľ, pretože ten Gotcha s prepojeného zoznamu, pretože tieto veci sú nazývané, je to, že budete musieť zavesiť na jednom konci prepojeného zoznamu. 

Rovnako ako s reťazcom, musíte poznať adresu prvého char. Rovnaké riešenie pre prepojených zoznamov. Musíte poznať adresu prvého bloku pamäte pretože odtiaľ sa môžete dostať každý iný. Nevýhodou. Akú cenu sme platiť za túto univerzálnosť s dynamicky značná dátová štruktúra, ktorá ak budeme niekedy potrebovať viac pamäte, jemné, Len prideliť jednu blok a nakresliť ukazovateľ z starého k novému chvosta zoznamu? Jo. [Študent] To trvá asi dvakrát tak veľký priestor. To trvá dvakrát toľko miesta, takže je to určite nevýhoda, a my sme videli to kompromis pred medzi časom a priestorom a flexibilitou kde teraz, nemusíme 32 bitov pre každý z týchto čísel. My naozaj potrebujeme 64, 32 v závislosti od počtu a 32 pre ukazovatele. Ale hej, mám 2 GB pamäte RAM. Pridanie ďalších 32 bitov tu a tu sa nezdá, že veľký problém. Ale pre veľké súbory dát, to určite pridá až doslova dvakrát toľko. Čo je ďalšia nevýhoda teraz, alebo čo funkcií budeme vzdať, ak budeme zastupovať zoznam vecí s prepojeného zoznamu a nie pole? [Študent] Nemôžete prechádzať dozadu. Nemôžete prechádzať dozadu, takže tak trochu skrutkované, ak idete zľava doprava pomocou slučky for alebo while cyklu a potom si uvedomíte, "Oh, chcem sa vrátiť na začiatok zoznamu." Nemôžete, pretože tieto ukazovatele len ísť zľava doprava ako šípky ukazujú. 

Teraz môžete spomenúť na začiatok zoznamu s inou premennou, ale to je zložitosť mať na pamäti. Pole, bez ohľadu na to, ako ďaleko ísť, vždy môžete urobiť mínus, mínus, mínus, mínus a vrátiť sa, odkiaľ si prišiel. Čo je ďalší nevýhoda tu? Jo. [Nepočuteľné Študent otázka] Dalo by sa, tak ste vlastne len navrhnutej dátovej štruktúry zvané dvojnásobne spájať zoznam, a naozaj, mali by ste pridať ďalší ukazovateľ pre každý z týchto obdĺžnikov že ide opačným smerom, je hore, ktoré Teraz ich môžete prechádzať tam a späť, Nevýhodou, ktorá je teraz používate trikrát toľko pamäte, ako sme zvyknutí a tiež zvyšovanie zložitosti z hľadiska kódu musíte napísať, aby si to pravé. To sú však všetky možno veľmi rozumné kompromisy, v prípade, že obrátenie je dôležitejšie. Jo. [Študent] tiež nemožno mať 2D prepojeného zoznamu. Dobré, nemôžete mať naozaj 2D spájať zoznam. Dalo by sa. Nie je to zďaleka tak jednoduché, ako pole. Rovnako ako maticu, robíte otvorený držiak, uzavretý držiak, otvorený držiak, uzavretý držiak, a máte nejaké 2-dimenzionální štruktúru. Dalo by sa vykonávať 2-rozmerný spájať zoznam ak si add-ako ste navrhoval-tretina ukazovateľ na každú z týchto vecí, a ak si myslíte, že o inom zozname, prichádza na vás 3D štýl z obrazovky nám všetkým, čo je len iný reťazec nejakého druhu. Mohli by sme to urobiť, ale nie je to tak jednoduché ako písanie otvorený držiak, hranatá zátvorka. Jo. [Nepočuteľné Študent otázka] Dobré, takže to je skutočný kicker. 

Tieto algoritmy, ktoré sme túžila po, rovnako ako oh, binárne vyhľadávanie, môžete vyhľadávať rad čísel na palube alebo telefónne kniha tak oveľa rýchlejšie, ak budete používať rozdeľ a panuj a binárne vyhľadávacie algoritmus, ale binárny vyhľadávací potrebné dva predpoklady. Jeden, že dáta boli zoradené. Teraz môžeme pravdepodobne si to zoradená, takže možno to nie je starosť, ale binárny vyhľadávací tiež predpokladá že ste mali náhodný prístup k zoznamu čísel, a pole vám umožní mať náhodný prístup, a náhodným prístupom, Chcem povedať, ak ste rovnako pole, koľko času zaberie vám dostať sa do držiaka 0? Jedna operácia, stačí použiť [0] a máš pravdu tam. Koľko krokov je potrebné, aby sa na miesto 10? Jeden krok, stačí ísť na [10], a ste tam. Naproti tomu, ako sa dostať na 10. integer v prepojenom zozname? Musíte začať od začiatku, pretože ste len spomínanie začiatok prepojeného zoznamu, rovnako ako reťazec je pamätal adresou jeho prvý znak, a zistiť, že 10. int alebo že 10. znak v reťazci, budete musieť hľadať celú tú stratenú vec. 

Opäť, nie sme riešenie všetkých našich problémov. Sme zavádzanie nových, ale je to naozaj záleží na tom, čo sa snažíte navrhnúť pre. Pokiaľ ide o vykonávanie, môžeme požičať nápad z tohto študentského štruktúry. Syntax je veľmi podobná, s výnimkou teraz, nápad je trochu abstraktná ako dom a meno a číslo. Ale ja navrhujem, že by sme mohli mať dátovú štruktúru v C , Ktorá sa nazýva uzol, ako posledné slovo na snímke naznačuje, vnútri uzla, a uzol je len všeobecný kontajner v informatike. Je to zvyčajne kreslený ako kruh alebo štvorec alebo obdĺžnik, ako sme kedy urobili. A v tejto dátovej štruktúre, máme int, n, tak to je číslo chcem uložiť. Ale čo je to druhý riadok, struct node * next? Prečo je to správne, alebo akú úlohu táto vec hra, aj keď je to trochu záhadný na prvý pohľad? Jo. [Nepočuteľné Študent odpoveď] Presne, takže * druh koristi, že je to ukazovateľ nejakého druhu. Názov tohto ukazovateľa je ľubovoľne ďalšie, ale mohli sme to nazval, čo chceme, ale to, čo robí tento ukazovateľ prejdite na? [Študent] Ďalšie uzol. >> Presne tak, to ukazuje na iné takéto uzla. 

Teraz, to je niečo ako zvedavosti C. Pripomeňme si, že C je čítať kompilátora zhora nadol, zľava doprava, čo znamená, že ak-je to trochu odlišné od toho, čo sme robili so študentom. Keď sme definovali študenta, sme vlastne nedal slovo tam. To práve povedal typedef. Potom sme mali int id, názov reťazca, reťazec dom, a potom sa študuje na spodnej časti struct. Toto vyhlásenie je trochu iný, pretože, znovu, C prekladač je trochu hlúpy. Je to len bude čítať zhora nadol, tak ak sa dosiahne 2. riadok tu kde je ďalší deklarovaný a vidí, oh, tu je premenná názvom ďalšie. Je to ukazovateľ na struct uzol. Kompilátor bude uvedomiť si, čo je struct uzol? Nikdy som nepočul o tejto veci skôr, pretože slovo uzol by inak objaviť až do dna, takže je táto nadbytočnosť. Musíš povedať struct uzol tu, ktoré potom môžete skrátiť neskôr vďaka typedef tu dole, ale to je preto, že my odkazujete štruktúru sám vnútri konštrukcie. To je ten mám ťa tam. 

Niektoré zaujímavé problémy budú vznikať. Máme zoznam čísel. Ako vložíme do nej? Ako sme hľadať to? Ako sme odstrániť z neho? Zvlášť teraz, že musíme zvládnuť všetky tieto ukazovatele. Myslel si si, že ukazovatele sú trochu myseľ-ohýbanie keď mal jeden z nich sa len snažím čítať int na neho. Teraz musíme manipulovať celý zoznam stojí za to. Prečo berieme 5 minút prestávku tu, a potom budeme prinášať niektorí ľudia až na javisku robiť presne to. 

C je oveľa zábavnejšie, keď je to predvádzal. Kto by doslova chcel byť prvý? Dobre, poď hore. Ste prvý. Kto by chcel byť 9? Dobre, 9. Ako asi 9? 17? Trochu kľučka tu. 22 a 26 v tomto prednej rade. A potom, ako na niekoho tam je zameraný. Ste 34. Dobre, 34, poď hore. Prvá z nich je tam. Dobre, všetci štyria z vás. A kto sme povedať 9? Kto je náš 9? Kto chce byť skutočne 9? Dobre, poď, byť 9. Ideme na to. 34, stretneme sa tam. Prvá časť je, aby sami vyzerať takto. 26, 22, 17, dobrý. Ak môžete stať stranou, pretože budeme malloc vás za chvíľu. 

Dobre, dobre. Dobre, vynikajúce, takže poďme položiť pár otázok tu. A vlastne, Ako sa voláte? >> Anita. Anita, v poriadku, poď sem. Anita je nám pomôže trochu vyriešiť jeden celkom jednoduchú otázku v prvej, ktoré je, ako si zistiť, či je alebo nie je hodnota je v zozname? Teraz si všimnite, že prvý, zastúpená tu Lucas, je trochu iný, a tak sa jeho kus papiera je zámerne stranou pretože to nie je zas až tak vysoká a nezaberá toľko bitov, aj keď technicky má rovnakú veľkosť papiera len otáčať. Ale je to trochu iný v tom, že je to iba 32 bitov pre ukazovateľ, a všetky tieto chlapci sú 64 bitov, z ktorých polovica je počet, z ktorých polovica je ukazovateľ. Ale ukazovateľ nie je zobrazený, takže ak ste mohol trochu rozpačito používať ľavú ruku k bodu na osobu vedľa vás. A ty si číslo 34. Ako sa voláte? Ari. Ari, tak vlastne, držte papier v pravej ruke, a ľavá ruka ide dole. Nachádzate predstavujú null vľavo. 

Teraz náš obraz človeka je veľmi konzistentné. To je vlastne, ako ukazovatele fungujú. A ak môžete zmotať trochu takhle, takže nie som v ceste. Anita tu, aby sme mi číslo 22, ale predpokladajú obmedzenia, ktoré nie je človek drží kúsky papiera, ale to je zoznam, a máte len Lucas začať pretože on je doslova prvý ukazovateľ. Predpokladajme, že vy sami ste ukazovateľ, a tak aj vy máte možnosť poukázať na niečo. Prečo si začať tým, že na to, čo Lucas mieri na? Dobrá, a dovoľte mi, aby som prijať toto sem. Len pre diskusie, dovoľte mi, aby som vytiahnuť prázdnu stránku tu. Ako sa píše vaše meno? >> Anita. Dobre, Anita. Povedzme, že uzol * Anita = Lucas. No, nemali by sme hovoriť lucas. Mali by sme hovoriť ako prvý. Prečo je tomu v skutočnosti je v súlade s realitou? Jeden, prvý už existuje. Prvé bolo pridelené pravdepodobne niekde tu. Uzol * prvý, a to bolo pridelené zoznam nejako. Neviem, ako sa to stalo. To sa stalo pred trieda začala. Tento spájať zoznam ľudí bola vytvorená. A teraz v tomto okamihu v príbehu-je to všetko deje na Facebooku zrejme neskôr, V tejto fáze príbehu, ktorý Anita bol inicializovaný musí rovnať prvej, čo neznamená, že body Anita na Lucasa. Skôr poukazuje na to, čo ukazuje na pretože rovnaká adresa, ktorá je vo vnútri 32 bitov Lucas je - 1, 2, 3 - Teraz je tiež v 32-bitovej Anita tieto - 1, 2, 3. 

Teraz nájsť 22. Ako by ste ísť asi robí? Čo je to? >> Point na čokoľvek. Prejdite na čokoľvek, tak choďte do toho a konať to, ako najlepšie môžete tu. Dobre, dobre, a teraz si ukázal na-to, čo je vaše meno s 22? Ramon. >> Ramon, takže Ramon sa drží 22. Teraz ste urobil kontrolu. Má Ramon == 22, a ak je to tak, napríklad, môžeme vrátiť pravda. Dovoľte mi, aby som pri-títo chalani tu stáť trochu nemotorne- dovoľte mi, aby som niečo rýchlo ako bool nájsť. Chystám sa ísť dopredu a povedať (uzol * list, int n). Budem hneď späť s vami. Len musím napísať nejaký kód. A teraz budem pokračovať a urobiť, uzol * Anita = zoznam. A ja idem ďalej a povedať, while (anita! = NULL). 

Metafora je tu stále trochu pretiahol, ale zároveň (anita! = NULL), čo chcem robiť? Potrebujem nejaký spôsob odkazovanie celé číslo, ktoré Anita ukazuje na. V minulosti, keď sme mali štruktúry, čo je uzol, sme použili bodkovaný notáciu, a povedali by sme niečo ako anita.n, ale problém je, že Anita nie je struct sebe. Čo je to? Je to ukazovateľ, takže naozaj, ak chceme použiť tento bodkovaný notácie, a to bude vyzerať zámerne trochu záhadný, musíme urobiť niečo ako ísť do ľavej ruky bez ohľadu na Anita je ukazuje na a potom sa pole s názvom n Anita je ukazovateľ, ale to, čo je * anita? Čo pre vás, keď idete na to, čo Anita mieri na? Struct, uzol, uzol, odvolanie, má pole s názvom n pretože, spomínam, táto 2 polia, ďalšie a n, že sme videli pred chvíľou tu. 

Ak chcete skutočne napodobniť to v kóde, by sme mohli urobiť to a povedať if ((* anita). n == n), n, že som hľadal. Všimnite si, že funkcia bola odovzdaná v počte Aj záleží. Potom môžem ísť ďalej a robiť niečo ako návrat skutočný. Else, ak to nie je tento prípad, čo chcem robiť? Ako môžem preložiť do kódu, čo Anita robil tak intuitívne prechádzky v zozname? Čo mám robiť, až tu simulovať Anita aby takýto krok doľava, tento krok doľava? [Nepočuteľné Študent odpoveď] >> Čo je to? [Nepočuteľné Študent odpoveď] Dobré, nie je zlý nápad, ale v minulosti, kedy sme urobili to, čo sme urobili anita + + pretože to by pridať číslo 1 Anita, ktoré by obvykle poukazujú na ďalšie osoby, ako Ramon, alebo osoba vedľa neho, alebo vedľa neho človek po línii. Ale to nie je tak celkom sa tu dobre, pretože to, čo to, čo vyzerá v pamäti? Nie, že. Musíme zakázať to. Vyzerá to, že to v pamäti, a to aj keď som vypracované 1 a 2 a 3 blízko seba, ak chceme skutočne simulovať, môžete chlapci, zatiaľ čo ešte ukázal na rovnakými ľuďmi, môžu niektorí z vás sa náhodný krok späť, niektorí z vás náhodná krok vpred? 

Tento neporiadok je stále prepojený zoznam, ale títo chlapci môže byť kdekoľvek v pamäti, tak anita + + nebude fungovať prečo? Čo je v mieste Anita + +? Kto vie. Je to nejaká iná hodnota, ktorá len tak náhodou sa prerušil medzi všetkými týmito uzlami náhodou, pretože sme nepoužívate poľa. My pridelené každej z týchto uzlov jednotlivo. Dobre, ak vy môžete vyčistiť sami zálohovať. Dovoľte mi, aby som navrhla, že namiesto toho, aby anita + +, sme namiesto toho Anita začne- dobre, prečo nejdeme na čokoľvek Anita ukazuje na a potom vykonajte. ďalej? Inými slovami, sme šli do Ramon, ktorý je drží číslo 22, a potom. ďalšie, ako by Anita by byť kopírovanie jeho ľavý ukazovateľ. Ale nechcel ísť ďalej, než Ramon, pretože sme našli 22. Ale to by bolo nápad. Teraz, to je strašný neporiadok. Úprimne povedané, nikto nikdy zapamätať si túto syntax, a tak našťastie, je to vlastne trochu úmyselné-oh, ty si skutočne vidieť, čo som napísal. To by bolo presvedčivejšie, keby ste mohol. Voila! 

V zákulisí, bol som riešenie problému týmto spôsobom. Anita, aby tento krok doľava, Najskôr sme sa ísť na adresu, ktorú Anita ukazuje na a kde nájdete nielen n, čo sme práve čítal z dôvodu porovnanie, ale tiež nájdete ďalšie - v tomto prípade, Ramon ľavá ruka ukazuje na ďalší uzol v zozname. Ale to je strašný neporiadok, ktorý som spomínal skôr, ale to dopadá C nám umožňuje zjednodušiť tým. Miesto písania (* anita), môžeme namiesto toho len napísať Anita-> n, a je to presne to isté funkčne, ale je to oveľa viac intuitívne, a je to oveľa viac v súlade s obrázkom, ktorý sme už kreslíš celú tú dobu pomocou šípok. 

Napokon, čo musíme urobiť, na konci tohto programu? Je tu jeden riadok kódu zostávajúce. Návrat čo? False, pretože ak dostaneme cez celú while a Anita je, v skutočnosti, nulový, to znamená, že išiel celá cesta na koniec zoznamu kde ukazoval na-aké je vaše meno? Ari. >> Ariho ľavá ruka, ktorá je null. Anita je teraz null, a Uvedomujem si, že ste práve stojím nešikovne v limbu pretože budem preč na monológu tu, ale budeme zapojiť sa znovu za chvíľu. Anita je null v tomto bode v príbehu, takže zatiaľ čo slučka končí, a musíme vrátiť false, pretože keby dostala až k nulovej ukazovateľ Ariho potom tam bol žiadne číslo, ktoré ona hľadala v zozname. Môžeme vyčistiť to až príliš, ale to je celkom dobrý vykonávanie potom z funkcie traversal, nájsť funkciu prepojeného zoznamu. Je to stále lineárne vyhľadávanie, ale nie je to tak jednoduché, ako + + ukazovateľ alebo + + premenná i, pretože teraz nemôžeme odhadnúť , Kde každý z týchto uzlov sú v pamäti. Musíme doslova sledovať stopu strúhanky, alebo viac špecificky, ukazovatele, ako získať z jedného uzla do druhého. 

Teraz sa poďme skúsiť iný. Anita, chceš vrátiť sa sem? Prečo by sme pokračovať a prideliť jednu ďalšiu osobu z publika? Malloc-Ako sa voláte? >> Rebecca. Rebecca. Rebecca bola malloced z publika, a ona je teraz uloženie čísla 55. A cieľ na dosah ruky je teraz pre Anita vložiť Rebecca do prepojeného zoznamu tu v správne miesto. Poď sem na chvíľu. Urobil som niečo také. Urobil som uzla *. A čo že sa to voláš? Rebecca. >> Rebecca, v poriadku. Rebecca sa dostane malloc (sizeof (uzol)). Rovnako ako sme pridelené veci ako študentov a ktovie čo ešte v minulosti, potrebujeme veľkosť uzla, tak sa Rebecca ukazuje na to, čo? Rebecca má dve polia vo vnútri nej, z ktorých jeden je 55. Poďme urobiť to, čo, rebecca-> = 55. Ale potom rebecca-> next by mal byť-teraz páči, jej ruka je tak trochu kto vie? Je to ukazuje na určité uvoľnenie hodnote, tak prečo nie pre správnu mieru by sme aspoň to tak, že ľavá ruka je teraz na jej strane. Teraz Anita, vezmite si ju odtiaľ. Máte Rebecca ktoré boli pôvodne pridelené. Nehanbite sa a nájsť miesto, kde by sme mali dať Rebeccu. Dobré, veľmi dobré. Dobre, dobre, a teraz musíme si zaistiť trochu smer, tak ste dosiahli Ari. Jeho ľavá ruka je null, ale Rebecca jednoznačne patrí doprava, tak ako sa máme zmeniť tento spájať zoznam aby vložiť Rebeccu na príslušné miesto? Ak by ste mohli doslova pohybovať doľava ľudí okolo seba rukami, podľa potreby, budeme problém vyriešiť týmto spôsobom. Dobre, dobre, a medzitým, Rebecca ľavá ruka je teraz po jej boku. 

To bolo príliš jednoduché. Skúsme pridelenie-Sme takmer hotoví, 20. Dobre, poď hore. 20 bolo pridelené, tak nechajte ma ísť napred a povedal opäť tu sme práve urobili uzol * Saad. Máme malloc (sizeof (uzol)). Potom sme urobiť rovnakú presnú syntax, ako sme to urobili pred pre 20, a ja budem robiť budúci = NULL, a teraz je to na Anita vložiť si do prepojeného zoznamu, ak si mohol hrať, že presne rovnakú úlohu. Execute. Dobre, dobre. Teraz si pozorne skôr, ako začnete pohybu ľavej ruky okolo. Tie zďaleka dostal najviac nepríjemnú úlohu dnes. Čí ruka by mala byť presunutá ako prvý? Dobre, počkaj, ja počujem niektoré nie je. Ak niektorí ľudia by zdvorilo rád pomohol vyriešiť nepríjemnú situáciu. Čí ľavá ruka by mala byť aktualizovaná prvého snáď? Jo. [Študent] Saad je. Dobre, Saad je, prečo, aj keď? [Nepočuteľné Študent odpoveď] Dobré, pretože ak my sa pohybujeme-Ako sa voláte? >> Marshall. Marshall, ak my sa pohybujeme ruku prvý down na hodnotu null, Teraz sme doslova osamotené štyroch ľudí v tomto zozname pretože on bol jediná vec, ukazuje na Ramon a všetci na ľavici, takže aktualizácia tento ukazovateľ Prvý bol zlý. Poďme späť, že. Dobrá, a teraz choďte do toho a presuňte príslušnú ľavú ruku ukazuje na Ramon. To cíti trochu nadbytočný. Teraz je tu dvaja ľudia ukazuje na Ramon, ale to je v poriadku pretože teraz, ako inak máme aktualizovať zoznam? Čo na druhej strane sa musí pohybovať? Skvelé, teraz máme stratila pamäť? Nie, tak dobre, uvidíme, či nemôžeme ti to ešte raz. 

Mallocing jeden posledný čas, číslo 5. Celú cestu v chrbte, poď dole. Je to veľmi vzrušujúce. [Potlesk] Ako sa voláte? >> Ron. Ron, v poriadku, ste malloced ako číslo 5. Práve sme vykonaný kód, ktorý je takmer totožný s týchto len s iným názvom. Výborný. Teraz, Anita, veľa šťastia vkladanie číslo 5 do zoznamu teraz. Dobrá, a? Skvelé, takže to je naozaj tretia z troch celkového počtu prípadov. Najprv sme mali niekoho na konci, Rebecca. Potom sme mali niekoho v stredu. Teraz máme niekoho na začiatku, a v tomto príklade, Teraz sme mali aktualizovať Lucas prvýkrát pretože prvý prvok zoznamu má teraz poukazujú na nový uzol, kto, podľa poradia, ukazuje na číslo uzla 9. 

To bolo veľmi trápne demonštrácie, som si istý, tak veľký potlesk pre týchto ľudí, ak by ste mohli. Skvele. To je všetko. Môžeš si nechať svoje kúsky papiera ako malý pamäte. Ukazuje sa, že robí v kóde nie je tak jednoduché, ako len pohybujúce sa okolo seba rukami, a ukázal ukazovatele na rôznych veciach. Ale uvedomte si, že keď príde čas na vykonanie niečo ako spájať zoznam alebo variant to, ak sa zameriate na naozaj tieto základné základy, na bite-size problémov, ktoré som sa prísť na to,, je to to ručne alebo to ruka, si uvedomiť, že to, čo je inak pomerne komplexný program môže byť v skutočnosti znížená na pomerne jednoduchých stavebných blokov, ako je tento. 

Poďme sa veci vo viac sofistikované smere stále. Teraz máme predstavu prepojeného zoznamu. Máme tiež-vďaka návrh späť tam, dvojnásobne spojené zoznam, ktorý vyzerá takmer rovnako, ale teraz máme dva ukazovatele vnútri struct miesto jedného, ​​a by sme pravdepodobne mohli zavolať tie ukazovatele predchádzajúce a nasledujúce doprava alebo doľava, ale my, v skutočnosti, je treba dva z nich. Tento kód by byť trochu viac zapojiť. Anita by musel robiť viac práce tu na javisku. Ale my sme mohli určite realizovať tento druh konštrukcie. Z hľadiska prevádzkového času, aj keď, čo by byť doba chodu pre Anita nájdenie číslo N v prepojenom zozname teraz? Stále veľký O n, takže je to o nič lepšie ako lineárne vyhľadávanie. Nemôžeme urobiť binárne vyhľadávanie, aj keď, znovu. Prečo tomu tak bolo v prípade? Nemôžete skákať okolo. Aj keď sme samozrejme vidieť všetkých tých ľudí na javisku, a Anita mohol eyeballed ho a povedal: "Tu je stred zoznamu," by nevedela, že keby to bola ona, počítačový program pretože jediné, čo sa musela západky na na začiatku scenára bol Lucas, ktorý bol ako prvý ukazovateľ. Ona by nutne musel nasledovať tieto odkazy, počítanie si cestu až našla zhruba uprostred, a dokonca aj vtedy, keď to nebude vedieť, kedy je ona dostal do stredu pokiaľ ona ide celú cestu až do konca zistiť, koľko ich je, potom ustúpi, a to aj bude ťažké, ak ste mali dvojnásobne spájať zoznam nejakého druhu. 

Riešenie niektorých problémov dnes, ale zavedenie ostatné. Čo inú dátovú štruktúru dohromady? Toto je fotografia zo zásobníkov v Mather dom, a v tomto prípade, máme štruktúru dát sme tiež trochu už hovorí. Hovorili sme o zásobníka v súvislosti s pamäťou, a to je druh zámerne pomenovaný pretože stack v podmienkach pamäti je účinne dátová štruktúra, ktorá má viac a viac vecí navrstvené na neho. Ale zaujímavé na tom hromadu, ako je tomu v skutočnosti, je to, že je to zvláštny druh dátové štruktúry. Je to dátová štruktúra, kedy prvý prvok v je posledný prvok von. Ak ste prvý zásobník na uvedenie do fronty, budete mať bohužiaľ posledný zásobník ktoré majú byť prijaté mimo zásobník, a to nie je nevyhnutne dobrá vec. Naopak, môžete premýšľať o tom opačne, posledný v je prvý von. 

Teraz, sa všetky scenáre príde na myseľ, kde majú hromadu dátová štruktúra, kde budete mať túto vlastnosť z poslednej dovnútra, prvý von, je vlastne presvedčivé? Je to dobrá vec? Je to zlá vec? Je to určite zlá vec, ak zásobníky neboli všetky rovnaké a oni boli všetci mimoriadne rôzne farby alebo ktovie čo ešte, a farbu, ktorú chcete, je úplne na dne. Samozrejme, môžete sa dostať, že bez veľkej námahy. Musíte začať od vrcholu a prácu si cestu dole. Podobne, čo keď ste bol jedným z týchto ventilátorov chlapcov ktorý čaká celú noc snaží dostať iPhone a zoradia na mieste ako je toto? Nebolo by pekné, keby v obchode Apple boli stack štruktúra dát? Yay? Nay? Je to len dobre pre ľudí, ktorí sa ukážu na poslednú chvíľu a potom si trhal frontu. A v skutočnosti, že som bol tak naklonený povedať fronty je vlastne v súlade s tým, čo by sme mohli nazvať tento druh dátové štruktúry, jeden v realite, kde poradí záleží, a chcete prvý v byť prvý z ak len kvôli ľudskej spravodlivosti. Budeme obvykle vyžadujú, aby fronta dátová štruktúra. 

Ukázalo sa, že okrem prepojených zoznamov, môžeme začať používať tieto rovnaké základné myšlienky a začať vytvárať nové a odlišné typy riešení problémov. Napríklad, v prípade, že v zásobníku, môžeme predstavovať zásobník pomocou dátovej štruktúry, ako je tento, by navrhujem. V tomto prípade, som vyhlásil struct, a ja som povedal, vo vnútri tejto štruktúry je rad čísel a potom premenná nazýva veľkosť, a budem nazývať túto vec stack. A teraz, prečo to vlastne funguje? V prípade zásobníka, mohol som čerpať túto efektívne na obrazovke ako pole. Tu je môj stack. To sú moje čísla. A budeme kresliť ako toto, toto, toto, toto, toto. A potom som mať nejaký iný dátový člen tu, ktorá sa nazýva veľkosť, takže je veľkosť, a to je číslo, a kolektívne, celá iPad tu predstavuje jednu zásobníka štruktúru. Teraz, v predvolenom nastavení, veľkosť sa pravdepodobne dostala byť inicializovaná na 0, a to, čo je vo vnútri poľa čísel spočiatku keď som prvýkrát prideliť poľa? Garbage. Kto vie? A to nie je v skutočnosti nezáleží. Nezáleží na tom, v prípade, že je 1, 2, 3, 4, 5, úplne náhodne smola uložené v mojom štruktúre, pretože tak dlho, ako viem, že veľkosť zásobníku je 0, potom viem, že programovo, nepozerajte sa na niektorý z prvkov v poli. Nezáleží na tom, čo tam je. Nepozerajte sa na ne, ako by dôsledky pre veľkosti 0. 

Predpokladajme však, že teraz som do toho pustite a vložte niečo do zásobníka. Chcem vložiť číslo 5, a tak som dal číslo 5 tu, a potom čo som dal sem dole? Teraz by som vlastne dal dole 1 pre veľkosť, a teraz je zásobník veľkosti 1. Čo keď som do toho pustite a vložte číslo, povedzme, 7 ďalší? To potom dostane aktualizovaný na 2, a potom budeme robiť 9, a potom to dostane aktualizovaný na 3. Ale zaujímavý rys teraz tohto zásobníka je, že Mám na odstránenie, ktorý prvok, keď chcem, aby pop niečo z frontu, tak hovoriť? 9 bude prvá vec, ktorú ísť. Ako by mala obraz zmeniť, ak chcem pop prvok zo zásobníka, veľa ako zásobník v Mather? Jo. >> [Študent] Nastavte veľkosť na 2. Presne tak, je všetko, čo som urobiť, nastaviť veľkosť 2, a čo mám robiť s poli? Nemám nič robiť. Mohol by som, len aby bol anal, dať tam 0 alebo -1, alebo niečo znamenať , Že sa nejedná dôveryhodne hodnota, ale to nevadí, pretože Aj možno zaznamenať mimo ARR ako dlho je takže viem, len sa pozrieť na prvé dva prvky v tomto poli. Teraz, keď odídem a pridať číslo 8 na toto pole, ako sa obraz zmeniť budúci? To sa stáva 8, a to sa stáva 3. Ja rezanie pár rohov tu. Teraz máme 5, 7, 8, a sme späť do veľkosti 3. To je celkom jednoduché realizovať, ale keď sa budeme ľutovať tohto návrhu rozhodnutia? Keď sa veci začnú ísť veľmi, veľmi zle? Jo. [Nepočuteľné Študent odpoveď] Ak chcete vrátiť späť a získať prvý prvok vložíte dovnútra 

Ukázalo sa, že tu, aj keď je stoh poľa pod kapotou, Tieto dátové štruktúry sme začali hovoriť o sú tiež všeobecne známe ako abstraktné dátové štruktúry, kedy, ako už implementované je úplne okrem bodu. Dátová štruktúra ako hromada má pridať podporu operácie, ako Push, ktorá tlačí zásobník na zásobníku, a pop, ktorý odstráni prvok zo zásobníka, a to je všetko. Ak by ste mali stiahnuť niekto iný kód, ktorý už zavedených to, čomu sa hovorí hromadu, by táto osoba písali iba dve funkcie pre vás, tlačiť a pop, ktorého jediným zmyslom života by bolo robiť presne to. Vy alebo on alebo ona, kto ju vykonáva tento program by boli úplne ten, kto rozhodne, ako implementovať sémantika tlačí a praskanie pod pokrievku alebo funkčnosť tlačenie a praskanie. A ja som urobil niečo krátkozrakú rozhodnutie tu vykonávacie môj stack s týmto jednoduchým dátové štruktúry prečo? Kedy Táto dátová štruktúra prestávku? V akom momente musím vrátiť chybu, keď používateľ volá tlak, napríklad? [Študent] Ak to nie je miesto. Presne tak, ak to nie je viac miesta, keď som prekročil kapacitu, ktorý je všetky čiapky, pretože to naznačuje, že je to nejaký globálny konštanty. No, potom som len tak povedať, "Je mi ľúto, nemôžem tlačiť ďalšiu hodnotu do zásobníka, "veľa ako v Mather. 

Na nejakom mieste, idú zasiahnuť hornú časť tohto malého kabinetu. Tam to nie je miesto, alebo kapacita v zásobníku, na ktorom mieste je tu nejaká chyba. Majú dať prvok niekde inde, zásobník niekde inde, alebo nikde vôbec. Teraz, s fronty, mohli by sme realizovať to trochu inak. Fronta sa trochu líši v tom, že pod kapotou, môže byť vykonaná ako pole, ale prečo, v tomto prípade, som navrhuje tiež mať hlavu prvok predstavujúci hlavu zoznamu, predné zoznamu, prvá osoba v súlade v obchode Apple, okrem veľkosti? Prečo potrebujem ďalšiu časť dát sem? Spomeňte si na to, čo čísla je keď som čerpané takto. Predpokladajme, že toto je teraz fronta miesto zásobníka, Rozdiel je, rovnako ako Apple store-queue je spravodlivé. Prvá osoba v súlade na začiatku zoznamu, číslo 5 je v tomto prípade, on alebo ona sa bude nechať do obchodu ako prvý. Poďme urobiť. Predpokladajme, že je to stav môjho frontu v túto chvíľu v čase, a teraz obchod Apple otvorí a prvá osoba, číslo 5, je vedený do skladu. Ako môžem zmeniť obrázok teraz, keď som odpojený fronte prvej osobe na začiatku riadku? Čo je to? >> [Študent] Zmena frontu. Zmena hlavu, takže 5 zmizne. V skutočnosti, je to, ako by-ako najlepšie to urobiť? V skutočnosti, je to, ako by ten chlap zmizne. Čo by číslo 7 robiť v skutočnom obchode? Oni by urobiť veľký krok vpred. 

Ale to, čo sme prišli oceniť, pokiaľ ide o pole a pohybujúce sa veci okolo? To je trochu strata času, že jo? Prečo musíš byť tak análny, ako mať prvú osobu na začiatku riadku na fyzicky začiatku kus pamäte? To je úplne zbytočné. Prečo? Čo som mohol len spomenúť miesto? >> [Nepočuteľné Študent odpoveď] Presne, mohol Pamätám si s touto ďalšie dátového členovi hlavy že teraz vedúci zozname nie je 0, čo bolo pred chvíľou. Teraz je to vlastne číslo 1. Týmto spôsobom, získam mierny optimalizáciu. Len preto, že som odpojený fronte niekoho z riadku na začiatku riadku v Apple obchode neznamená každý má posunúť, čo vyvolanie je lineárna operácia. Môžem miesto tráviť konštantný čas iba a dosiahnuť potom oveľa rýchlejšiu reakciu. Ale cena platím, je to, čo získať, že ďalší výkon a nemajú presunúť všetky? Jo. >> [Nepočuteľné Študent odpoveď] Môže pridať viac ľudí, dobre, že problém je ortogonálne k tomu, že nie sme radenie ľudí okolo. Je to stále pole, takže tiež posunieme všetky, alebo nie- oh, vidím, čo máte na mysli, v poriadku. Vlastne, súhlasím s tým, čo hovoríte, v tom, že je to skoro, ako by sme teraz nikdy používať začiatku tohto poľa už pretože keď som odstrániť 5, potom som odstrániť 7. Ale ja som len dať ľuďom doprava. 

Je to pocit, ako by som plytváte diskovým priestorom, a nakoniec moja fronta rozpadá do ničoho vôbec, takže sme mohli len mať ľudia wraparound, a my sme mohli myslieť na tohto poľa naozaj ako akési kruhové štruktúry, ale my používame to, čo operátor v C k tomu, že druh wraparound? [Nepočuteľné Študent odpoveď] >> operátor modulo. Bolo by trochu nepríjemné premyslieť, ako si urobiť wraparound, ale my sme mohli urobiť, a my sme mohli začať dávať ľudí na to, čo bývala prednej línie, ale my jednoducho zapamätať, s touto hlavou premenné, kto je skutočným vedúci línia vlastne je. Čo keď miesto, naším cieľom nakoniec, aj keď, Bol sa pozrieť do čísel, ako sme to urobili tu na javisku s Anita, ale naozaj chceme to najlepšie zo všetkých týchto svetov? Chceme sofistikovanejším, ako pole umožňuje pretože chceme schopnosť dynamicky rast dátovú štruktúru. Ale my nechceme musieť uchýliť k niečomu, čo sme poukázali v prvom prednáške nebol optimálny algoritmus, že lineárne hľadanie. Ukazuje sa, že je to možné, v skutočnosti, dosiahnuť alebo aspoň v blízkosti konštantnom čase, kedy niekto ako Anita, keď konfiguruje jej štruktúru dát nesmie byť prepojený zoznam, že sa nejedná o zásobník, že sa nejedná o fronty, mohol, v skutočnosti, prísť s dátovou štruktúru, ktorá mu umožňuje sa pozrieť do vecí, dokonca aj slová, nie len čísla, v čom budeme hovoriť konštantný čas. 

A v skutočnosti, s výhľadom do budúcnosti, jeden z psets v tejto triede je takmer vždy implementácia pravopisu, pričom sme vám zase nejaké 150.000 anglických slov a cieľom je nahrať tie do pamäte a rýchlo byť schopní odpovedať na otázky formulára je toto slovo napísané správne? A to by bolo naozaj sať, ak ste mali určiť iteráciou cez všetky 150.000 slov odpovedať. Ale v skutočnosti, uvidíme, že to môžeme urobiť veľmi, veľmi rýchlom čase. A to bude zahŕňať realizáciu niečo, čo nazýva hash tabuľky, a to aj keď na prvý pohľad to, čomu sa hovorí hash tabuľky bude dovoľte nám dosiahnuť tieto super rýchle odozvy, ukazuje sa, že je v podstate problém. Keď príde čas na prevedenie túto vec s názvom-zase robím to znova. Som tu jediný. Keď príde čas na vykonávanie tejto veci tzv hash tabuľky, budeme musieť urobiť rozhodnutie. Ako veľká by tá vec vlastne je? A keď začneme vkladanie čísel do tohto hash tabuľky, ako budeme ukladať takým spôsobom, že sa môžeme dostať je späť tak rýchlo, ako sme sa dostali dovnútra? Ale uvidíme onedlho, že táto otázka Keď sa všetci narodeniny, je v triede bude celkom Germáni. Ukazuje sa, že v tejto miestnosti, máme niekoľko stoviek ľudí, takže pravdepodobnosť, že dvaja z nás majú rovnaké narodeniny je asi dosť vysoká. Čo keby tam bol len 40 z nás v tejto miestnosti? Aké sú šance dvoch ľudí, ktorí majú narodeniny v rovnaký deň? [Študenti] Viac ako 50%. Jo, viac ako 50%. V skutočnosti, dokonca som priniesol graf. Ukazuje sa, a to je naozaj len plížiť preview- v prípade, že je len 58 z nás v tejto miestnosti, pravdepodobnosť 2 z nás majú narodeniny v rovnaký deň, je veľmi vysoká, takmer 100%, a že to bude spôsobovať veľa zranenie pre nás v stredu. 

Vďaka, že povedal, poďme odročenie tu. Uvidíme v stredu. [Potlesk] [CS50.TV]