[Prehrávanie hudby] David J. Malan: Dobre. To je CS50. To je týždeň päť pokračuje, a my nejaké dobré správy a zlé správy. Takže dobrá správa je, že CS50 začína tento piatok. Ak máte záujem sa k nám pripojiť, zamierte do obvyklej adrese tu. Ešte lepšia správa, nie prednáška tento rok v pondelok 13 .. O niečo menej lepšie správy, kvíz nula je budúcu stredu. Viac informácií môže byť nájdete na tejto adrese tu. A v najbližších pár dní budeme vypĺňať prázdne miesta s ohľadom na izbách že budeme mať vyhradené. Lepšie správou je, že tam budem byť preskúmanie samozrejme celej Zasadnutí tento rok V pondelok vo večerných hodinách. Zostaňte naladení na kurze je Internetové stránky pre umiestnenie a podrobnosti. Sekcie, a to aj keď sa jedná o dovolenka, zobrazia sa aj stretnúť tiež. Najlepšie novinky, prednáška budúci piatok. Tak to je tradícia nám majú podľa osnov. Len--, že to bude úžasné. Uvidíte veci, ako je dátové štruktúry konštantné časové a hashovacie tabuľky a stromy a snaží sa. A budeme hovoriť o problémoch narodenín. Celá partia vecí čaká budúci piatok. OK. Tak či onak. Takže pripomenúť, že sme boli so zameraním na obrázku o tom, čo je vnútornej pamäti nášho počítača. Takže je pamäť RAM, alebo tam, kde programy existuje, keď ste im beží. Ak dvakrát kliknete na ikonu spustiť nejaký program, alebo dvakrát kliknite na icon otvoriť niektoré súbory, je nabitá z vášho pevného disk alebo jednotku SSD do pamäte RAM, Random Access Memory, kde žije, kým sa nevypne napájanie, veko notebooku sa zavrie, alebo ukončenia programu. 

Teraz, pamäť, z ktoré pravdepodobne máte 1 GB v týchto dňoch, 2 GB, alebo dokonca oveľa viac, je všeobecne stanovené pre daný program v tomto druhu pravouhlého konceptuálny model čím máme zásobníka v spodnej časti a veľa ďalších vecí, na vrchole. Ide o to, na samom vrchole sme videli na obrázku skôr, ale nikdy nehovoril o je takzvaný texte segmentu. Text segment je len ozdobný spôsob, ako hovoriť nuly a tie, ktoré vytvorte aktuálny skompilovaný program. 

Takže keď poklepete Microsoft Word v počítači Mac alebo PC, alebo pri spustení bodka lomítko Mario na Linux počítač v okne vášho terminálu, nuly a tie, ktoré sa skladajú Word a Mario sú dočasne uložené v pamäti RAM počítača v takzvanej Text segmentu pre konkrétny program. Pod tým ide inicializovaný a neinicializovaný údaje. To je vec ako globálne premenné, že sme nepoužíva veľa, ale občas máme mal globálne premenné alebo staticky definované reťazce, ktoré je pevný kódované slová ako "ahoj" ktoré nie sú prijaté od užívateľa , Ktoré sú pevne do svojho programu. 

Teraz, sa v spodnej časti sme majú takzvaný stack. A stack, doteraz sme boli použitím, aké druhy účely? Čo zásobník sa používa? Jo? 

Divákov: Funkcia. 

David J. Malan: Pre funkcie? V akom zmysle pre funkcie? 

Divákov: Pri volaní funkcie, argumenty sú skopírované do zásobníka. 

David J. Malan: Presne tak. Pri volaní funkcie, jej argumenty sú skopírované do zásobníka. Takže nejaké X alebo Y alebo či B je že ste prechádza do funkcie sú dočasne kladený na takzvaný zásobník, rovnako ako jeden z Annenberg jedáleň podnosy, a tiež veci, ako lokálne premenné. Ak váš foo funkcie alebo odkladacieho funkcie majú lokálne premenné, ako je teplota, tí dvaja skončiť na zásobníku. Teraz budeme moc nehovorila o ne, ale tieto premenné prostredia v dolnej časti sme videli pred chvíľou, keď Bol som futzing na klávesnici jeden deň a začal som prístup k veci ako argv 100 alebo argv 1000, Len elements-- som zabudol numbers-- ale, že nemali byť prístupné mnou. Začali sme vidieť niektoré funky symboly na obrazovke. Boli to takzvané premenné prostredia ako globálne nastavenie pre môj programu alebo pre svoj počítač, nie nesúvisí s poslednou chyba, že sme sa bavili, Shellshock, že to bolo trápi pomerne málo počítačov. 

Teraz konečne, v dnešnej zameranie budeme nakoniec mať na halde. Jedná sa o ďalší kus pamäti. A v podstate všetko pamäť je isté. Je to rovnaký hardvér. Sme len trochu liečenie rôznych klastrov bajtov pre rôzne účely. Haldy bude tiež tam, kde premenné a pamäti, ktoré požadujete z operačného systému sú dočasne uložené. 

Ale je to trochu problém tu, rovnako ako obraz znamená. Máme druh má dva lode sa zraziť. Pretože ak budete používať viac a viac zo zásobníka, a ako vidíme dnes dopredu, ak budete používať viac a viac haldy, iste zlé veci sa môže stať. A skutočne, môžeme vyvolať, že úmyselne alebo neúmyselne. Takže Cliffhanger posledného čas bol tento program, ktoré nemali slúžiť nejaký funkčný účel iný ako ukázať ako ste ako zloduch môže skutočne trvať Výhodou chýb v niečí programe a prevziať program alebo dokonca Celý počítačový systém alebo server. Takže stačí, aby sa pozrel krátko vás Všimnite si, že najdôležitejšie na dne sa v príkazovom riadku argumenty, podľa argv. A to je volanie funkcie f, v podstate bezmenná funkcia nazvaná f, a to odovzdaním argv [1]. 

Takže bez ohľadu na slovo, že užívateľ zadá na riadku za menom tohto programu, a potom ľubovoľná funkcia hore top, f, sa v reťazci, AKA char *, ako sme začali diskutovať, a to len nazýva "bar". Ale my sme to mohli nazvať čokoľvek. A potom prehlasuje, vnútri f, pole znakov volal C-- 12 týchto znakov. 

Teraz, podľa príbehu, ktorý som hovoril pred chvíľou, kedy v pamäti je c, alebo sú tie 12 znakov skončí? Len aby bolo jasno. Jo? 

Divákov: Na zásobníku. 

David J. Malan: Na zásobníku. Takže c je lokálna premenná. Pýtame sa na 12 znakov alebo 12 bajtov. Tí, ktorí sa skončí na takzvané zásobníka. Teraz konečne je to iná funkcia to je vlastne celkom užitočné, ale my sme naozaj použiť to sami, strncopy. To znamená, že reťazec kópiu, ale iba n listy, n znakov. Tak n znaky budú kopírovať z baru do cca. A koľko? Dĺžka tyče. Takže inými slovami, že jeden riadok, strncopy, bude kopírovať účinne bar do cca. 

Teraz, len trochu predvídať Ponaučenie z tohto príbehu, to, čo je tu potenciálne problematické? Aj keď sme skontrolovať dĺžku tyče a jej odovzdanie do strncopy, Aký je váš gut hovoríš, je stále zlomený o tomto programe? Jo? 

Divákov: Nezahŕňa priestor pre nulový znak. David J. Malan: Nezahŕňa priestor pre nulový znak. Potenciálne, na rozdiel od v bežná minulá prax my ani mať toľko ako plus 1 na ubytovať, že znakom null. Ale je to ešte horšie, než to. Čo iného sme nedarí robiť? Jo? 

Divákov: [nepočuteľné] David J. Malan: Perfect. Sme pevne dané 12 dosť ľubovoľne. To nie je tak moc problém, ale skutočnosť, že sme ani kontrolovať, či Dĺžka tyče je menšia ako 12, v tom prípade to bude bezpečné, aby to do pamäti volal c, že ​​sme pridelené. V skutočnosti, ak je ako bar 20 znakov, Zobrazí sa táto funkcia sa kopírovania 20 znakov z baru do C, čím sa pričom aspoň 8 bajtov že by nemalo byť. To je dôsledok tu. 

Takže v skratke, rozbité programu. Nie je tak veľký problém. Možno, že máte chybu segmentácie. Všetci sme mali chyby v programoch. My všetci môžu mať chyby programov práve teraz. Ale čo je dôsledok? No, tu je zväčšené verzie že obraz pamäte môjho počítača. Jedná sa o spodnú časť môjho stacku. A skutočne, na samom dne je to, čo je volal rodič rutina zásobník, ozdobný spôsob, ako povedať, že je to hlavné. Tak, že ten, kto nazýva funkcia f, že hovoríme o. Tak toto je dno zásobníka. Spiatočná adresa je niečo nové. Je to vždy tam, vždy v tomto obrázku. Práve sme sa nikdy obrátil pozornosť k tomu. Vzhľadom k tomu, že ukáže, že spôsob, akým funguje, je c , Že keď jeden volanie funkcie druhého, nielen že tvrdenie, podľa ktorej Funkcie tlačil do fronty, nielen že funkcia je miestna premenné tlačil do fronty, niečo ako spiatočná adresa získa tiež dať do zásobníka. Konkrétne, ak hlavný volá foo, hlavné je vlastnej adresu v pamäti, vôl niečo, efektívne dostane dať do zásobníka tak, že ak je f vykonáva spustením vie, kam skočiť späť do textu segmentu, aby mohol pokračovať vykonávanie. 

Takže keď sme tu koncepčne, V hlavnej, potom f volaná. Ako sa f vedieť, kto na ručné ovládanie späť? No, tento malý strúhanka v červenej tu, volal spiatočná adresa, to jednoducho kontroly, čo je to spiatočná adresa? Oh, nechaj ma skočiť späť na hlavnú tu. A to je trochu ako zjednodušujúce, pretože núl a jednotiek Pre Main sú technicky tu v tech segmente. Ale to je nápad. f jednoducho musí vedieť, čo tam, kde konanie nakoniec sa vráti. 

Ale spôsob, akým počítače už dlho stanovené veci ako lokálne premenné a argumenty ako je táto. Takže v hornej časti obrázku v modrá je stack frame pre f, takže všetko na pamäti, že f konkrétne ich používate. Tak teda, všimnite si, že Bar je na tomto obrázku. Bar bol jeho argument. A tvrdí, že argumenty Funkcie tlačil do zásobníka. A c, samozrejme, je Aj na tomto obrázku. 

A len pre Značky účely, Všimnite si, v ľavom hornom rohu je to, čo by c držiaku 0 a potom mierne vpravo dole je c držiak 11. Takže inými slovami, ktore si možno predstaviť že tam je mriežka z bytov tam, z ktorých prvá je vľavo hore, dole, z ktorých je posledná z týchto 12 bytov. 

Ale teraz sa snaží rýchlo vpred. Čo sa má stať, ak sme sa prejsť v reťazci bare, ktorý je dlhší ako c? A my nie sme kontrole, či je to naozaj dlhšie ako 12 rokov. Ktorá časť obrázka bude prepísané po bajtoch 0, 1, 2, 3, dot dot dot, 11, a potom sa zlý, 12, 13 až 19? Čo sa bude diať tu, ak vyvodiť z objednania že držiak c 0 je na vrchole c držiak 11 je trochu dole k poriadku? Jo? 

DIVÁKOV: No, to sa deje prepísať char * bar. 

David J. Malan: Jo, vyzerá to, že budete prepísať char * bar. A čo je horšie, ak ste poslali naozaj dlho reťazec, môžete dokonca prepísať, čo? Spiatočná adresa. Čo je opäť rovnako ako strúhanka povedať programu, kde sa vrátiť, keď f sa vykonáva volaná. 

Takže to, čo protivníci obvykle do je v prípade, že narazia na program , Že sú zvedaví, či je využívanie, buggy takým spôsobom, že on alebo ona môže mať Výhodou tejto chybe, väčšinou sa im nedostáva to hneď na prvýkrát. Jednoducho začať vysielať, napríklad, náhodné reťazce do svojho programu, či na klávesnici, alebo povedané, že pravdepodobne napísať malý program, len automaticky generovať reťazca, a začať búšiť na programe odoslanie v mnohých rôznych vstupov v rôznych dĺžkach. 

Akonáhle vaše zrútenie programu, to je úžasná vec. Pretože to znamená, že alebo ona zistila, čo je asi naozaj chyba. A potom sa môžete dostať múdrejší a začať sústrediť užšie o tom, ako využiť túto chybu. Konkrétne, čo sa on alebo ona by mohla urobiť, je poslať, v najlepšom prípade, ahoj. Žiadny veľký problém. Je to reťazec, ktorý je dostatočne krátky. Ale čo keď on alebo ona pošle, a my zovšeobecniť ako, Útok code-- tak nulami a tie, ktoré sa robiť veci, ako rm-rf, že odstráni všetko z pevného disku alebo rozosielanie spamu alebo nejako napadnúť počítač? 

Takže v prípade, každý z nich písmená A práve predstavuje koncepčne, útok, útok, útok, útok, nejaký zlý kód že niekto iný napísal, ale ak táto osoba je dosť šikovný, nielen zahŕňať všetky z tých RM-RFS, ale tiež mať jeho alebo jej posledný pár bajtov je číslo, ktoré zodpovedá na adresu jeho alebo jej vlastný útok kód že on alebo ona prešla v niekoľkých tým, že ju na výzvu, môžete efektívne trik počítač do všímať, keď je f vykonáva vykonávania, oh, to je čas, aby som sa skákať späť na červenú spiatočnú adresu. Ale pretože on alebo ona má nejako prekrývali, že spiatočnú adresu s vlastným číslom, a oni sú dosť bystrí na to aby ste nakonfigurovali, že číslo, ktoré chcete odkazovať, ako vy pozri v super hore ľavá tam kútik, skutočná adresa počítača Spomienka na niektoré ich útoku kódu, zlý človek môže oklamať počítač k vykonaniu svojej vlastnej kód. 

A ten kód znova, môže to byť čokoľvek. To je všeobecne nazývaný shell kód, ktorý je práve spôsob, ako povedať, že to nie je všeobecne niečo tak jednoduchého ako rm-rf. Je to vlastne niečo ako Bash, alebo skutočný program, ktorý mu dáva alebo jej programové riadenie na vykonanie čokoľvek iného, ​​čo chcú. Takže v skratke, to všetko pochádza z jednoduchej skutočnosti, že táto chyba sa netýkala kontrolu hranice svojho poľa. A preto, že na ceste počítače práce je to, že použiť zásobník z efektívne, koncepčne, Spodná hore, ale potom sa prvkami zatlačíte do zásobníka rastie zhora nadol, To je neuveriteľne problematické. Teraz existujú spôsoby, ako obísť to. A úprimne povedané, tam sú jazyky s ktorou sa tento problém vyriešiť. Java je imúnny, napríklad, k tejto konkrétnej otázke. Vzhľadom k tomu, že vám nedávajú odkazy. Oni vám nedávajú priame adresy pamäte. Tak s týmto výkonom, že máme na nič siahať do pamäti chceme, je síce veľké riziko. 

Takže dávať pozor. Ak je, úprimne povedané, v mesiacoch alebo rokov prísť, kedykoľvek budete čítať o nejakom zneužívaní programu alebo servera, Ak ste niekedy vidieť náznak niečoho ako útok pretečeniu vyrovnávacej pamäti, alebo pretečeniu zásobníka je iný typ útoku, podobne ako v duchu, rovnako ako inšpiruje webové stránky meno, ak ho poznáte, je to všetko hovorí len o pretekaniu veľkosť nejakého znaku poľa alebo niektoré polia všeobecnejšie. Akékoľvek otázky, potom, o tom myslíte? Neskúšajte to doma. 

V poriadku. Takže malloc doteraz bola naša nová priateľ v tom, že môžeme prideliť pamäť že nemusí nutne vedieť, dopredu, že chceme, aby sme nemuseli mať na pevný kód do našich čísla programov, ako je 12 rokov. Akonáhle užívateľ nám hovorí, koľko Dáta on alebo ona chce na vstup, môžeme malloc toľko pamäte. 

Takže malloc to dopadá, na miery sme sa ju používať, výslovne naposledy, a potom vy ste sa používať pre getString nevedomky pre niekoľko týždňov, všetky pamäte malloc je pochádza z takzvaného haldy. A to je dôvod, prečo getString, napríklad, môže alokovať pamäť dynamicky bez toho aby vedel, čo ste bude písať v predstihu, odovzdať späť ukazovateľ na pamäti, že, a že pamäť je stále na vás, aby, aj po getString vráti. Pretože odvolanie po tom všetkom Zásobník je neustále ísť hore a dole, hore a dole. A akonáhle to ide dole, to znamená, že akýkoľvek pamäť táto funkcia použitá, nemal byť používaný niekým iným. Je to hodnoty odpadky teraz. 

Ale hromada je tu. A čo je pekné o malloc je to, že keď malloc prideľuje pamäť tu, to nie je ovplyvnený, pretože z väčšej časti tým, že v zásobníku. A tak nejaká funkcia prístup pamäť, ktorá bola malloc'd, ani funkcie ako je getString, aj potom, čo sa vráti. 

Teraz hovoriť malloc je zadarmo. A skutočne, na pravidlo, ktoré treba začať prijatie je nejaký, niektorý, nejaký čas používať malloc musíte sami používať zadarmo, prípadne, na rovnakom ukazovateli. Celú tú dobu sme sa písať buggy, buggy kód, z mnohých dôvodov. Ale jeden z nich bol pomocou knižnice CS50, ktoré sama o sebe je zámerne buggy, to nevracia pamäť. Zakaždým, keď som volal getString počas posledných niekoľkých týždňov pýtame sa prevádzkové systém, Linux, pre pamäť. A vy ste ani raz ho dal naspäť. A to nie je, v praxe, dobrá vec. 

A Valgrind, jeden z nástroje zavedené v pset 4, je predovšetkým o ktorý vám pomôže teraz nájsť chyby, ako že. Ale našťastie pre pset 4 nepotrebujete iba v CS50 knižnicu alebo getString. Takže nejaké chyby spojené s pamäťou sú nakoniec bude váš vlastný. 

Takže malloc je viac než len vhodné na tento účel. Môžeme vlastne teraz riešiť zásadne odlišné problémy, a zásadne riešiť problémy viac efektívne, ako za týždeň nula sľubu. Potiaľto je to sexy štruktúra dát sme mali. A dátové štruktúry som na mysli spôsob Konceptualizácia pamäte spôsobom, ktorý presahuje len hovorím, to je int, to je char. Môžeme začať klastra veci dohromady. 

Takže pole vyzeral takto. A čo je kľúčom k Pole je, že vám dáva back-to-back kusy pamäte, z ktorých každá bude rovnakého typu, int, int, int, int alebo char, char, char, char. Ale je tu niekoľko tienisté stránky. To napríklad, je poľa veľkosti šesť. Predstavte si, že vyplnenie tohto poľa sa šiestimi čísla a potom, z akéhokoľvek dôvodu, Vaše užívateľské chce dať ste sedmina číslo. Kde si dať? 

Aké je riešenie, ak máte vytvoril rad na zásobníku, Napríklad, iba s týždeň dve notácie, že sme uviedli, hranatých zátvoriek s číslom vnútri? No, máš šesť Čísla v týchto krabiciach. Čo by vaše inštinkty byť? Kam by ste chceli dať? 

Divákov: [nepočuteľné] 

David J. Malan: Sorry? 

Divákov: Dajte ju na konci. 

David J. Malan: Dajte ju na konci. Tak len niečo málo cez doprava, mimo tento box. Čo by bolo pekné, ale je to Ukazuje sa, môžete to urobiť. Pretože ak ste nepožiadal pre tento kus pamäti, mohlo by to byť náhodou, že tento sa používa nejaké iné premenné úplne. Spomeňte si týždeň alebo tak, keď sme položili z Zamyla a DAVINA a Gabe je menami v pamäti. Boli doslova chrbtom k sebe k sebe. Takže nemôžeme byť nutne verím, že čokoľvek je tu je k dispozícii pre mňa použitie. 

Takže čo iného môžete robiť? No, akonáhle si uvedomil, vás Potrebujete poľa veľkosti sedem, môžete len vytvoriť poľa veľkosti sedem potom použite cyklu for alebo while, skopírujte ho do nového poľa, a potom nejako jednoducho zbaviť Toto pole alebo jednoducho prestaňte ho používať. Ale to nie je príliš efektívne. Stručne povedané, pole nenechajte dynamicky meniť veľkosť. 

Takže na jednej strane sa dostanete náhodný prístup, čo je úžasné. Vzhľadom k tomu, že nám umožňuje robiť veci, ako rozdeľ a panuj, binárne vyhľadávanie, všetci máme hovoril o na obrazovke tu. Ale tie farby sa do kúta. Akonáhle stlačíte koniec tvojho poľa, čo musíte urobiť veľmi drahý prevádzku alebo napísať veľa kódu aby sa vysporiadať s týmto problémom. 

Čo keď namiesto toho sme mali niečo ako zoznam, alebo spájať zoznam sa konkrétne jedná? Čo keď namiesto toho, aby obdĺžniky chrbtom k sebe k sebe, máme obdĺžniky, ktoré opustí malý trochu manévrovací priestor medzi nimi? A aj keď som sa vyvodiť tento obrazu alebo prispôsobiť tento obrázok z jedného z textov, tu sa vráti do chrbtom k sebe veľmi usporiadane, v skutočnosti, jeden z týchto obdĺžnikov by mohol byť tu v pamäti. Jedným z nich by mohol byť tu. Jedným z nich by mohla byť tu, sem, a tak ďalej. 

Ale čo keď sme vychádzali, v tomto prípade, šípky to nejako prepojiť ich obdĺžniky dohromady? Skutočne sme videli technický stelesnenie šípkou. Čo sme v poslednej dni, že pod kapotou, vyjadrujúce šípky? Ukazovateľ, že jo? 

Čo keď miesto len uloženie čísla, ako 9, 17, 22, 26, 34, čo keby sme neukladá iba číslo, ale ukazovateľ pri každej takejto číslo? Tak, že podobne ako by ste závit ihlu cez veľa látky, nejako viazanie veci spoločne, podobne môžu sme sa s ukazovateľmi, ako je inkarnoval šípkami tu druh tkať spolu tieto jednotlivé obdĺžniky tým, že účinne pomocou ukazovateľa vedľa každého čísla, ktoré poukazuje na niektoré ďalšie číslo, ktoré poukazuje na zase nejaký ďalšie číslo? Takže inými slovami, to, čo Ak by sme skutočne chceli realizovať niečo také? Tak bohužiaľ, tieto obdĺžniky Aspoň že ten s 9, 17, 22, a tak ďalej, to sú už pekné námestie s jednotlivými číslami. Spodné, obdĺžnik pod 9, napríklad, predstavuje to, čo by malo byť ukazovateľ, 32 bitov. Teraz som ešte nevie akýkoľvek dátový typ v jazyku C, ktoré vám umožnia nielen int ale ukazovateľ úplne. 

Takže aké je riešenie, ak chceme vymyslieť vlastnú odpoveď na to? Jo? 

Divákov: [nepočuteľné] 

David J. Malan: Čo je to? 

Divákov: Nová štruktúra. 

David J. Malan: Jo, tak prečo Čo keby sme vytvoriť novú štruktúru, alebo C, struct? Videli sme structs skôr, ak krátko, kde sme sa zaoberali štruktúrou študentov takto, ktorý mal meno a domu. V pset 3 útek, ktorú ste použili celý banda structs-- GRect a GOvals že Stanford vytvorený klaster informácie dohromady. Tak čo, ak vezmeme rovnaký nápad kľúčové slová "typedef" a "struct", a potom nejaký študent-špecifické veci, a vyvíjať sa to do nasledujúcich: typedef struct node-- a uzol je len veľmi všeobecná počítačová vedy termín pre niečo, čo v dátovej štruktúre, Kontajner v dátovej štruktúre. Uzol Tvrdím, bude mať int n, úplne jednoduché, a potom sa trochu záhadne, Tento druhý riadok, struct uzol * ďalšie. Ale menej z technického hľadiska, čo je to druhý riadok kódu vnútri zložených zátvoriek? Jo? 

Divákov: [nepočuteľné] David J. Malan: ukazovateľ do iného uzla. Takže síce syntaxe trochu záhadné. Ale ak budete čítať doslova, Ďalšia je názov premennej. Aký je jej dátový typ? Je to trochu ukecaný tentoraz, ale to je typu struct uzol *. Kedykoľvek sme videli niečo hviezdu, ktorá znamená, že je ukazovateľ na tento typ dát. Takže ďalší je zrejme ukazovateľ na struct uzol. 

A teraz, čo je uzol struct? Dobre si všimnite, vidíš ty, Rovnaké slová v pravom hornom rohu. A skutočne, môžete tiež vidieť slovo "Uzol" tu dole v ľavom dolnom rohu. A to je vlastne len pohodlie. Všimnite si, že v našej definícii študenta je tu slovo "žiak" iba raz. A to preto, že študent Objekt nebol úplne evidentné. Nie je nič vnútri študenta že je potrebné, aby ukazoval na iný študent, persay. To by bolo trochu divný v reálnom svete. 

Ale s uzlom v spojen zoznam, my chceme uzol ako referenčná k podobným predmetom. A tak zistíte tu zmena nie je len to, čo je vo vnútri zložených zátvoriek. Ale pridať slovo "uzol" v hornej časti, ako aj pridaním na dno namiesto "študenta." A to je len technický detail tak, že, opäť Vaša dátová štruktúra môže byť samo-referenčná, takže uzol môže ukazovať na iného takého uzla. 

Takže to, čo je v konečnom dôsledku bude znamenať pre nás? No, jeden, toto dovnútra je obsah nášho uzla. To, čo tu, vpravo hore, je tak že opäť môžeme odkazovať na seba. A potom vonkajšie veci, aj keď uzol je nový termín, Možno, že je to stále rovnako ako študenti, a čo bol pod kapotou v SPL. 

Takže ak by sme sa chceli začať vykonávanie tohto prepojeného zoznamu, Ako by sme mohli preložiť niečo také sa kód? No, povedzme, viď Príklad programu, ktorý v skutočnosti používa spájať zoznam. Medzi dnešné distribučné kódu je program, nazvaný zoznam nula. A keď som spustiť tento som vytvoril super jednoduché GUI, Graphical User Interface, ale je to naozaj len printf. A teraz som vzhľadom k tomu sám pár ponuku options-- Delete, Insert, vyhľadávanie, a Traverse. A ukončite. To sú len bežné operácie dátové štruktúry známej ako zoznam odkazov. 

Teraz, Delete sa chystá Vymazanie čísla zo zoznamu. Vložte ide pridať číslo v zozname. Vyhľadávanie bude vyzerať na číslo v zozname. A traverz je len ozdobný spôsob, ako hovoriť, prejsť zoznamu vytlačiť, ale to je všetko. Nemeňte ho žiadnym spôsobom. 

Takže skúsme to. Poďme ďalej a typ 2. A potom budem vložte číslo, povedzme 9. Enter. A teraz môj program je jednoducho naprogramovaný tak, aby povedať, zoznam je teraz deväť. Teraz, keď som sa do toho pustite a Vložte si znova, nech ma ísť napred a oddialenie a zadajte 17. Teraz môj zoznam je 9, potom 17. Ak sa mi vložiť znova, poďme preskočiť jeden. Namiesto 22, podľa obrázku máme sa pri pohľade na tú, dovoľte mi, aby som náskok a vložte 26 ďalšie. Takže budem písať 26. Tento zoznam je, ako som očakávať. Ale teraz, len aby zistil, či tento kód bude flexibilná, dovoľte mi, aby som sa typ 22, ktorý aspoň koncepčne, keď sme Udržať tento radené, čo je naozaj bude ďalším cieľom práve teraz, by mal ísť medzi 17 a 26 rokov. Tak som stlačte Enter. V skutočnosti, to funguje. A tak teraz mi dovoľte vložiť Posledný, na obrázku, 34. 

V poriadku. Takže teraz mi dovoľte stanovuje, že Odstrániť a Traverse a hľadanie robiť, v skutočnosti, pracovať. V skutočnosti, keď sa mi spustiť vyhľadávanie, poďme vyhľadať číslo 22, Enter. Bolo zistené 22. Takže to je to, čo tento Program Zoznam Zero robí. 

Ale čo sa vlastne deje na ktorý implementuje to? No, najprv by som mohol mať, a skutočne Musím, súbor s názvom list0.h. A niekde tam je to linka, typedef struct uzol, potom mám zložené zátvorky, int n, a potom struct-- čo bolo definícia? Struct uzol ďalšie. Takže potrebujeme hviezdu. Teraz technicky sme sa dostali do zvyk kreslenie tu. Môžete vidieť učebnice a on-line odkazy na to tam. Je to funkčne ekvivalentný. V skutočnosti, je to trochu typické. Ale budem v súlade s čím sme minule a to. A potom konečne, budem to robiť. 

Takže v hlavičkovom súbore niekde v list0.h dnes je táto definícia struct, a možno niektoré ďalšie veci. Zatiaľ v list0c tú bude pár vecí. Ale budeme len štart a nie dokončiť. List0.h je súbor chcem zaradiť do môjho C súbor. A potom sa v určitom okamihu som bude mať int, hlavné, neplatné. A potom budem mať niektoré úloh je tu. Taky budem mať prototyp, ako neplatné, vyhľadávanie, int, n, ktorých zmyslom života je hľadať elementu. A potom sa tu tvrdí, v Dnešné kód, void, hľadanie, int n, nie bodkočiarka, ale otvorené zložené zátvorky. A teraz chcem nejako vyhľadávanie prvku v tomto zozname. Ale nemáme dosť informácie na obrazovke ešte. Nemám vlastne predstavovali samotný zoznam. Takže jeden spôsob, ako by sme mohli realizovať spájať zoznam v programe je, že som trochu urobiť niečo ako vyhlásiť, spájať zoznam tu. Pre jednoduchosť budem robiť tento globálny, aj keď v Všeobecne nemali robiť to príliš veľa. Ale to bude zjednodušenie tento príklad. Tak som chcel deklarovať spájať zoznam tu. Teraz, ako by to robil? 

Tu je obrázok prepojeného zoznamu. A ja naozaj nemám vedieť, v okamihu, kedy ako Chystám sa ísť o zastupovanie toľko vecí, ktoré sa len jeden premenná v pamäti. Ale spomínam na okamih. Celú tú dobu sme mali reťazce, ktoré potom odhalil, že je pole pre znaky, ktoré potom odhalený byť len ukazovateľ na prvý znak v poli znakov , Ktorý je ukončený nulovým znakom. Takže podľa tejto logiky, a s tým obrázok druh siatie svoje myšlienky, Načo nám vlastne napísať v našej kód predstavuje spájať zoznam? Koľko z týchto informácií potrebujeme zachytiť v C kóde, povedali by ste? Jo? 

Divákov: Potrebujeme ukazovateľ na uzol. David J. Malan: ukazovateľ na uzol. Najmä, ktorý uzol by bol váš inštinkty sa udržať ukazovateľ? 

Divákov: prvý uzol. 

David J. Malan: Áno, asi len ten prvý. A všimnite si, prvý Uzol je odlišný tvar. Je to len polovičná veľkosť struct, pretože je to naozaj len ukazovateľ. Takže to, čo môžete naozaj urobiť, je vyhlásiť spájať zoznam byť typu uzla *. A povedzme prvý nazvať a inicializovať ju na hodnotu null. Takže null, je opäť prichádza na obrázku tu. Nielen, že je null používaný ako napríklad špeciálne Návratová hodnota pre veci, ako getString a malloc, null je takisto nulová ukazovateľ, nedostatok ukazovatele, ak chcete. To jednoducho znamená, že nič, čo je ešte tu. Teraz prvýkrát, mohol som volal to čokoľvek. Mohol som to nazval "zoznam" alebo ľubovoľný počet ďalších vecí. Ale ja som volať to "prvý", takže , Aby sa ocitol obrázku. Tak ako reťazec môže byť reprezentovaný s adresou svojho prvého bytu, takže môže spájať zoznam. A uvidíme ďalšie dáta konštrukcia je zastúpená iba s jedným ukazovateľom, 32-bit šípka smerujúca v prvom uzle v štruktúre. 

Ale teraz poďme predpokladať problém. Ak som len spomínanie v mojom programe adresy z prvého uzla, najskôr obdĺžnik v tejto dátovej štruktúre, čo bolo lepšie byť prípad o Realizácia zvyšok môjho zoznamu? Čo je to kľúčový detail, čo sa deje zabezpečiť, že toto skutočne funguje? A tým "skutočne funguje" Aj Teda, podobne ako reťazec, nám umožňuje prejsť od prvého znaku v Davin menom na druhej, na tretí, na štvrtý, až do samého konca, ako vieme, keď sme na konci prepojeného zoznamu, ktorý vyzerá takto? Keď je null. A ja som predstavoval tento druh ako ako elektrický inžinier silou, s malou uzemnenie symbol, druhov. Ale to len znamená, null v tomto prípade. Môžete nakresliť ľubovoľný počet spôsobmi, ale tento autor Stalo sa tu používať tento symbol. 

Tak dlho, ako budeme navliekať všetkých týchto uzlov spoločne, zapamätanie iba v prípade, Prvý z nich je, tak dlho ako vložiť špeciálny symbol na úplne posledný uzol v zozname, a budeme používať hodnotu null, pretože to je to, čo máme k dispozícii pre nás, Tento zoznam je kompletný. A aj keď som len dať ukazovateľ na prvý prvok, tie, programátor, určite prístup zvyšok. Ale poďme sa nechať svoju myseľ blúdiť trochu, v prípade, že nie sú už docela wandered-- čo je bude čas behu nájsť niečo v tomto zozname? Sakra, je to veľké O n, čo nie je zlé, v spravodlivosti. Ale je to lineárna. Vzdali sme to, čo funkcia polí presunutím viac k tomuto obrázku dynamicky tkané spoločne alebo prepojené uzly? Dali sme si náhodný prístup. Pole je pekné, pretože matematicky všetko je chrbtom k sebe k sebe k sebe. Aj keď tento obrázok vyzerá pekne, a dokonca aj aj keď to vyzerá, že tieto uzly sú pekne od seba, v skutočnosti by mohli byť kdekoľvek. OX1, Ox50, Ox123, Ox99, títo uzly by mohli byť kdekoľvek. Vzhľadom k tomu, malloc robí alokovať pamäť z haldy, ale kdekoľvek v halde. Nemusíte nutne vedieť, že je bude chrbtom k sebe k sebe. A tak to registrácia do reality je to bude celkom to pekná. 

Takže to bude trvať trochu pracovať na vykonávanie tejto funkcie. Takže poďme realizovať Hľadať. A uvidíme, druh šikovný spôsob, ako to urobiť. Takže keď som vyhľadávacie funkcie a Ja som vzhľadom k premennej, číslo N hľadať, musím vedieť, Nová syntax hľadá vnútri štruktúry, ktorá je ukázal, nájsť n. Tak poďme na to. 

Takže najprv som ísť dopredu a vyhlásiť uzol *. A budem to hovoriť ukazovateľ, len konvencií. A ja sa inicializovať ju ako prvý. A teraz môžem urobiť v mnohých ohľadoch. Ale budem mať spoločný prístup. Kým ukazovateľ nie je rovné null, a to je platné syntaxe. A to jednoducho znamená, že nasledujúci kód, takže ak nie ste ukázal na nič. Čo chcete robiť? 

Ak sa ukazovateľ bodka n, dovoľte mi, aby som sa vrátil k tomu, equals-- rovná čo? Aké hodnoty mám hľadať? Skutočná n, ktorý bol schválený v. Tak tu je ďalšia vlastnosť, o C a mnohých jazykov. Aj keď uzol štruktúry zvané má hodnotu n, úplne legitímne tiež mať miestnu argumentu alebo premenné s názvom n. Pretože aj my, s ľudské oko môže rozlíšiť že toto n je pravdepodobne odlišný od tohto n. Vzhľadom k tomu, syntax je odlišná. Máš bodku a ukazovateľ, že táto jedna nemá žiadnu takú vec. Takže to je v poriadku. To je v poriadku, aby im hovoriť rovnaké veci. 

Ak mám sa vám nájsť to, ja som bude chcieť niečo urobiť ako oznamujeme, že sme našli n. A necháme to ako komentár alebo pseudokód kód. Else, a tu je Zaujímavosťou, čo nechcem robiť, keď aktuálneho uzla nie obsahujúce n, že mi záleží? Ako môžem dosiahnuť nasledujúce? Ak sa môj prst na moment je PTR, a to je ukázal na čokoľvek Prvý ukazuje na, ako sa môžem pohnúť prstom k ďalšiemu uzlu v kóde? No, čo je strúhanka sme bude nasledovať v tomto prípade? Divákov: [nepočuteľné]. David J. Malan: Jo, tak nabudúce. Takže keď sa vrátim k môjmu Kód tu, naozaj, ja som ísť ďalej a povedať ukazovateľ, ktorý je to len dočasné proměnná-- je to divný názov, ptr, ale Je to ako temp-- Chystám sa nastaviť ukazovateľ rovná ktoréhokoľvek ukazovateľa je-- a znova, to bude malý kočík pre moment-- bodkou. Inými slovami, ja vezmem môj prst, ktorý sa ukázal v tomto uzle tu a budem hovoriť, viete, čo, pozrite sa na ďalšie pole a pohybom prsta bez ohľadu na to ukazujú. A to bude opakovať, opakovať, opakovať. Ale keď sa robí môj prst prestať robiť vôbec nič? Akonáhle sa to, čo riadok kódu kopy v? Divákov: [nepočuteľné] David J. Malan: Ak je bod, zatiaľ čo ukazovateľ nerovná null. Na nejakom mieste môj prst je bude ukazovať na null a budem si uvedomiť, to je koniec tohto zoznamu. Teraz, to je malý lož pre jednoduchosť. Ukazuje sa, že aj keď sme sa dozvedel túto tečkové notácie pre stavby, ukazovateľ nie je struct. ptr je čo? Stačí, aby sa viac nitpicky. Je to ukazovateľ na uzol. Nie je to uzol sám. Keby som nemal hviezdu tu, ukazovateľ absolutely-- je to uzol. To je ako týždeň jedno deklarácia premennej, aj keď slovo "uzol" je nový. 

Ale akonáhle sme zaviedli hviezda, to je teraz ukazovateľ na uzol. A bohužiaľ nemožno použiť bodka zápis pre ukazovateľ. Musíte použiť šípky zápis, ktorý, prekvapivo, Je to prvýkrát, kedy nejaký kus syntax vyzerá intuitívne. Tento doslova vyzerá ako šíp. A tak to je dobrá vec. A tu doslova Vyzerá ako šíp. Takže si myslím, že je to la-- vôbec sa mi nepáči myslím, že som príliš spáchanie tady-- I si myslí, že je to posledná nový kus syntaxe budeme vidieť. A vďakabohu, že je to naozaj trochu viac intuitívne. 

Teraz, pre tých z vás, ktorí by radšej postarom, môžete stále používať tečkové notácie. Ale podľa pondelňajšieho rozhovor, najprv treba ísť tam, choďte na to riešiť, a potom prístup k poľu. Tak to je tiež v poriadku. A úprimne povedané, je to trochu pedantská. Tie doslova hovorí, dereferencia ukazovateľ a tam. Potom si n, pole s názvom n. Ale úprimne povedané, nikto nechce písať alebo čítať. A tak svet vynašiel notácie šípky, ktoré je ekvivalentná, totožné, je to len syntaktický cukor. Takže ozdobný spôsob, ako hovoriť to vyzerá lepšie, alebo vyzerá jednoduchšie. 

Takže teraz budem robiť jednu vec. Budem hovoriť "pauzu", akonáhle som Zistili, že je tak nemám udržať ju hľadajú. Ale to je podstata vyhľadávacie funkcie. Ale je to oveľa jednoduchšie, v koniec, a nie prejsť kód. To je skutočne formálna realizácia hľadanie v dnešnej distribúcie kóde. Trúfam si povedať, že vložka nie je obzvlášť zábavné prejsť vizuálne, ani ich mazať, a to aj aj keď na konci dňa sa redukuje na pomerne jednoduché heuristiky. 

Tak poďme na to. Ak budete humor ma tu, som prináša veľa stresu gule. Priniesol som veľa čísel. A mohli by sme získať len niekoľko dobrovoľníkov reprezentovať 9, 17, 20, 22, 29, a 34? Takže v podstate každý kto je tu dnes. To bol jeden, dva, tri, štyri, päť, šesť ľudí. A ja som bol požiadaný, aby jít-- vidieť, no jeden na zadnej strane zvyšuje svoje ruky. OK, jeden, dva, tri, štyri, five-- dovoľte mi načíta balance-- šesť. OK, šesť poď hore. Budeme potrebovať ďalších ľudí. Priniesli sme ďalšie stres gule. A ak by ste mohol, pre len na chvíľu, linka Sami si jednoducho páči tento obrázok tu. 

V poriadku. Poďme sa pozrieť, Ako sa voláte? 

DIVÁKOV: Andrew. 

David J. Malan: Andrew, ste číslo 9. Teší ma. Tu to máš. DIVÁKOV: Len. David J. Malan: Len. David. Číslo 17. Áno? 

Divákov: Som Julia. 

David J. Malan: Julia, David. Číslo 20. DIVÁKOV: Christian. David J. Malan: Christian, David. Číslo 22. A? 

DIVÁKOV: JP. David J. Malan: JP. Číslo 29. Takže choďte do toho a dostať v-- Uh oh. Uh oh. Standby. 20. Má niekto značku? Divákov: Mám Sharpie. David J. Malan: Máš Sharpie? OK. A má niekto kus papiera? Uložiť prednášku. Poď. Divákov: Máme to. David J. Malan: Máme to? Dobre, ďakujem. Ideme na to. Bolo to od vás? Práve ste zachránil deň. Tak 29. V poriadku. Aj chybne 29, ale OK. Len do toho. Dobre, dám vám pero späť na okamih. Takže máme týchto ľudí tu. Poďme sa jeden druhého. Gabe, chceš hrať prvý prvok tu? Musíme vás upozorniť v týchto jemných ľudí. Takže 9, 17, 20, 22, triediť z 29, a potom 34. Sme stratili niekoho? Mám 34. Kde udělal-- OK, kto chce byť 34? OK, poď hore, 34. Tak jo, to bude stojí za vyvrcholenie. Ako sa voláte? 

DIVÁKOV: Peter. 

David J. Malan: Peter, poď hore. Dobre, takže tu je Celá partia uzlov. Každý z vás predstavuje jeden z týchto obdĺžnikov. A Gabe, trochu zvláštne človek sa predstavuje ako prvý. Takže jeho ukazovateľ je o niečo menšia na obrazovke, než všetci ostatní. A v tomto prípade, každý po ľavej strane ruky, bude buď smerovať nadol, v dôsledku čoho sa null, tak len absencia ukazovateľa, alebo to bude ukazovať v uzle vedľa vás. 

Takže teraz, keď sa zdobia sami ako na obrázku tú, choďte do toho a bod na seba, s Gabe najmä ukazuje na číslo 9 reprezentovať zoznam. OK, a číslo 34, vaša ľavá ruka by mala byť len ukázal na podlahu. 

OK, takže to je previazaný zoznam. Tak toto je scenár v pochybnosť. A skutočne, to je reprezentatívna triedy problémov , Že by sa mohli pokúsiť riešiť s kódom. Ak chcete nakoniec vložiť nový prvok do zoznamu. V tomto prípade budeme skúste vložiť číslo 55. Ale tam to bude rôzne prípady, aby zvážila. A skutočne, to bude jeden z big-obraz takeaways tu, je, Aké sú rôzne prípady. Aké sú rôzne, ak podmienky, alebo vetvy, ktoré váš program mohol mať? 

No, číslo sa snažíte vložka, ktorá dnes už vieme, že je 55, ale ak ste nevedeli, v predstihu, trúfam si tvrdiť, spadá do najmenej troch možné situácie. Tam, kde by mohol byť nový prvok? Divákov: A koniec alebo stred. David J. Malan: Na konci, v strednej, alebo na začiatku. Tak som sa tvrdí, že je aspoň tri problémy musíme riešiť. Poďme si vybrať, čo je potrebné pravdepodobne najjednoduchšie jeden, kde nový prvok patrí na začiatku. Takže budem mať kód úplne ako je vyhľadávanie, ktoré som napísal. A ja budem mať ptr, ktoré Budem reprezentovať tu s mojím prstom, ako obvykle. 

A pamätajte si, akú hodnotu sme inicializovať ptr na? Tak sme sa inicializuje ju spočiatku null. Ale to, čo sme urobili, akonáhle sme boli v našej funkciu vyhľadávania? Vydali sme sa rovná prvej, čo neznamená, že robí. Ak mám nastaviť prvý ptr rovno, čo by moja ruka naozaj ukazuje na? Presne tak. Takže ak Gabe a ja sa chystáte byť rovnaké hodnoty tu Potrebujeme ako bodu číslo 9. 

Tak toto bol začiatok nášho príbehu. A teraz je to len jednoduchý, aj keď syntax je nové. Koncepčne je to len lineárne hľadanie. Je 55 rovná 9? Alebo skôr, povedzme, menej ako 9. Pretože sa snažím prísť na to, kam umiestniť 55. Menej ako 9, menej ako 17, menej ako 20, menej ako 22, menej ako 29, menej ako 34, nie. Takže teraz sme v prípade jeden z najmenej troch. 

Ak chcem vložiť 55 sem, čo riadky kódu potrebné sa dostať popravený? Ako to obrázok ľudia potrebujú zmeniť? Čo mám robiť s mojou ľavú ruku? To by malo byť null spočiatku, preto, že som na konci zoznamu. A čo by sa stalo, tu s Petrom, že? Očividne bude ukazovať na mňa. Takže tvrdím, že je to najmenej dva riadky kódu v ukážkovom kóde odo dneška že to bude na vykonanie tohto Scenár pridanie 55 na chvoste. A mohol by som mať niekoho hop a práve predstavuje 55? Dobre, že ste nový 55. 

Takže teraz, čo keď ďalšie scenár príde, a chceme vložiť na na začiatku alebo na čele tohto zoznamu? A aké je vaše meno, číslo 55? 

DIVÁKOV: Jack. 

David J. Malan: Jack? OK, rád ťa spoznávam. Vitajte na palube. Takže teraz budeme vložiť, povedzme, číslo 5. Tu je druhý prípad tri sme prišli s pred. Takže v prípade, 5 patrí na začiatku, poďme sa pozrieť, ako sme zistili, že von. Aj inicializovať svoj ptr ukazovateľ opäť číslo 9. A uvedomil som si, oh, 5 je menšia ako 9. Takže opraviť tento obrázok pre nás. Čí ruky, Gabe či Davida nebo--, čo je číslo deväť meno? 

DIVÁKOV: Len. 

David J. Malan: Jenin hands-- ktoré v našich rukách je potrebné zmeniť? OK, takže Gabe poukazuje na to, čo teraz? Na mňa. Som nový uzol. Tak som si len trochu pohybu tu vidieť vizuálne. A medzitým čo som zdôrazniť, že? Napriek tomu, kde som ukázal. Tak takto to je. Takže naozaj len jeden riadok kódu opravy tento konkrétny problém, by sa mohlo zdať. Dobre, takže to je dobré. A môže niekto byť zástupný symbol pre 5? Poď hore. Budeme vám nabudúce. 

Dobre, takže teď-- a Mimochodom, názvy Nebudem robiť explicitné zmienku o práve Teraz, pred ukazovateľ, predchodca ukazovateľ a nový ukazovateľ, ktorý je vzhľadom k tomu len mená v ukážkovom kóde na ukazovateli alebo ruky, že to trochu polohovacie okolo. Ako sa voláte? 

DIVÁKOV: Christine. 

David J. Malan: Christine. Vitajte na palube. Dobre, takže uvažujme teraz trochu nepríjemné scenár, čím Chcem vložiť niečo ako 26 do toho. 20? Čo je? Tieto jsou-- dobrú vec máme toto pero. V poriadku, 20. Ak sa niekto mohol dostať ešte kúsok papier pripravený, len case-- v poriadku. Oh, zaujímavé. No to je príklad prednáškového chyby. OK, takže to, čo sa voláš? DIVÁKOV: Julia. David J. Malan: Julia, môžete pop , A predstierať, že si nikdy nebol? OK, to sa nikdy nestalo. Ďakujem vám. Takže predpokladám, že chceme vložiť Julia do tohto prepojeného zoznamu. Je číslo 20. A samozrejme, že je bude patriť k begin-- neukazujú na nič zatiaľ. Takže vaša ruka môže byť trochu dole null alebo nejaké odpadky hodnotu. Poďme povedať, rýchly príbeh. Som ukázal na číslo 5 tejto dobe. Potom som skontrolovať 9. Potom som skontrolovať 17. Potom som skontrolovať 22. A ja si uvedomujem, ooh, Julia musí ísť pred 22. Takže to, čo sa musí stať? Čí ruky je potrebné zmeniť? Julie, moje, nebo-- čo sa voláš? 

DIVÁKOV: Christian. 

David J. Malan: Christian, alebo? 

DIVÁKOV: Andy. 

David J. Malan: Andy. Christian, alebo Andy? Andy je potrebné poukázať na? Julia. V poriadku. Tak Andy, chceš ukázať na Julia? Ale počkajte chvíľku. V príbehu tak ďaleko, Ja som tak nejako jedno na starosti, v tom zmysle, že ukazovateľ je vec, ktorá je pohybujúce sa v zozname. Mohli by sme mať názov pre Andyho, ale nie je premenná s názvom Andy. Iba iné premenné máme, je Prvý, kto zastupuje Gabe. 

Takže to je vlastne dôvod, prečo sa tak Zatiaľ sme to potrebovali to. Ale teraz na obrazovke je znovu zmieniť o pred ukazovatele. Tak nechaj ma byť konkrétnejší. Ak je to ukazovateľ, mal som lepší trochu inteligentnejšie o mojom iteráciu. Ak vám nevadí, že môj prechádza tu opäť ukázal tu, ukazuje tu. Ale dovoľte mi mať pred ukazovateľ, predchodca ukazovateľ, ktorý je druh ukazuje na element som bola na. Takže keď idem tu a teraz Moja ľavá ruka aktualizácie. Keď idem tu moja ľavá aktualizácie ručne. A teraz mám nielen ukazovateľ prvok, ktorý ide po Julii, Stále mám ukazovateľ Andy, prvok pred. Takže budete mať prístup, v podstate, strúhanka, ak chcete, na všetkých potrebných ukazovateľov. 

Takže keď som ukázal na Andy a ja som tiež ukázal u kresťana, ktorého ruky by teraz mala byť zdôraznené inde? Takže Andy teraz možno poukázať na Júliu. Julia sa teraz poukázať na Christiana. Vzhľadom k tomu, že môžete kopírovať moje pravá ruka je ukazovateľ. A to vám účinne prenáša späť na toto miesto tu. Takže stručne povedané, aj keď toto nás berie druh navždy skutočne aktualizovať spájať zoznam, realizovať že operácia sú relatívne jednoduché. Je to z jedného, ​​dva, tri riadkov kódu nakoniec. Ale omotal okolo tých riadkov kódu pravdepodobne je trochu logiky, ktorá účinne kladie otázku, kde to sme? Sme na začiatku, stredná, alebo koniec? 

Teraz, tam sú určite iné operácie môžeme realizovať. A tieto fotky tu len opísať to, čo sme práve robili s ľuďmi. Čo je odstránenie? Ak chcem, napríklad, odstrániť číslo 34 alebo 55, Možno mám rovnaký druh kódu, ale budem potrebovať jeden alebo dva kroky. Vzhľadom k tomu, čo je nové? Ak mám odstrániť niekoho, kto na konci, ako číslo 55 a 34, čo má tiež zmeniť, ako to urobiť? Musím sa evict-- čo sa voláš? 

DIVÁKOV: Jack. 

David J. Malan: Jack. Musím nielen evict-- zadarmo Jack, tak doslova Volajte zadarmo Jack, alebo aspoň tam ukazovateľ taky, ale teraz to, čo sa musí zmeniť s Petrom? Jeho ruka lepší štart smerom nadol. Pretože akonáhle som volať zadarmo na Jacku, či Peter je stále ukazuje na Jacka a preto, aby kríženie Zoznam a prístup tohto ukazovateľa, to je, keď náš starý priateľ segmentácie Porucha môže skutočne kopať do. Vzhľadom k tomu, že sme vzhľadom na pamäť späť na Jacka. 

Môžete tam zostať nešikovne len na chvíľu. Pretože máme len pár finálne operácie, aby zvážila. Odstránenie hlavy zoznamu, alebo beginning-- a ten je trochu nepríjemné. Vzhľadom k tomu, musíme vedieť, že Gabe je tak trochu zvláštne v tomto programe. Pretože v skutočnosti, má vlastný ukazovateľ. On nie je len sa ukázal na, rovnako ako takmer všetci ostatní tu. 

Takže keď v čele zoznamu je odstránená, ktorého ruky je potrebné zmeniť práve teraz? Ako sa voláš? 

DIVÁKOV: Christine. 

David J. Malan: Som hrozný na mená, zrejme. Takže Christine a Gabe, ktorého ruke je potrebné zmeniť kedy sa snažíme odstrániť Christine, číslo 5, z obrázku? OK, tak sa poďme robiť Gabe. Gabe sa deje na bod, Možno predpokladať, že u čísla 9. Ale čo ďalšie by sa malo stať? Divákov: Christine by byť null [nepočuteľné]. David J. Malan: OK, mali by sme asi make-- Počul som, "null" niekde inde. Divákov: Null a oslobodiť ju. David J. Malan: Null čo? Divákov: Null a oslobodiť ju. David J. Malan: Null a oslobodiť ju. Takže je to veľmi jednoduché. A je to perfektné, že si teraz nejako zo tam stál, ktorá nepatrí. Vzhľadom k tomu, že ste bol oddelená od zoznamu. Vy ste skutočne boli osirel zo zoznamu. A tak sme mali lepšie volať zadarmo teraz Christine, aby tú spomienku späť. Inak zakaždým, keď odstrániť uzol zo zoznamu by sme mohli byť robiť zoznam kratšie, ale nie v skutočnosti znižuje veľkosť v pamäti. A tak, ak budeme držať pridávanie a pridávať, pridávať veci do zoznamu, Môj počítač sa môže dostať pomalší a pomalší a pomalší, pretože bežím z pamäť, aj keď nie som v skutočnosti pomocou Christine bajtov pamäti ešte. 

Takže na konci sú iné scenáre, z course-- odstránenie v stredu, odstránenie Na konci, ako sme videli. Ale ešte zaujímavejšie Teraz je bude uvažovať presne čo je doba chodu je. Takže nielen môžete nechať kúsky papiera, v prípade, Gabe, by vám nevadilo dať každý stres loptičku. Ďakujem moc nášho prepojeného zoznamu dobrovoľníkov tu, keby si mohol. 

[APPLAUSE] 

David J. Malan: Dobre. Takže pár analytické otázok, potom, keby som mohol. Sme videl tento zápis, veľké O a omega, horná hranica a dolná hranica na doba chodu nejakého algoritmu. Takže uvažujme len pár otázok. 

Raz, a to povedal, že sme predtým, čo je beh Doba hľadania zoznam, pokiaľ ide o veľké O? Čo je to horná hranica na prevádzku Doba hľadania spájať zoznam ako realizovať naše dobrovoľníkmi tu? Je to veľký O n, lineárne. Vzhľadom k tomu, v najhoršom prípade, prvok, ako je 55, môžeme hľadať, kde by mohla byť Jack, úplne na konci. A bohužiaľ, na rozdiel od mnohých nemôžeme dostať chuť tentoraz. Aj napriek tomu, že všetci naši ľudia boli radené od malých prvkov, 5, celú cestu až do väčšieho prvku, 55, je to zvyčajne dobrá vec. Ale to, čo robí tento predpoklad už nám umožňujú robiť? Divákov: [nepočuteľné] David J. Malan: znova, povedz? Divákov: Random prístup. David J. Malan: s náhodným prístupom. A zase to znamená, že môžeme bez ďalej používať slabý nuly, intuície, a samozrejmosť použitie binárne vyhľadávanie a rozdeľ a panuj. Vzhľadom k tomu, aj keď sme ľudia mohli samozrejme vidieť, že Andy a Christian boli zhruba v polovici zoznamu, Vieme len, že ako Počítač zbieraním na zoznam od samého začiatku. Tak sme sa vzdali, že náhodný prístup. 

Tak veľký O n je teraz horný viazané na nášho vyhľadávacieho času. Čo omega nášho vyhľadávania? Čo je dolná hranica na vyhľadávanie pre nejaké číslo v tomto zozname? Divákov: [nepočuteľné] David J. Malan: znova, povedz? DIVÁKOV: One. David J. Malan: One. Takže časová konštanta. V najlepšom prípade, Christine naozaj na začiatku zoznamu. A my hľadáme číslo 5, takže sme ju našli. Takže žiadny veľký problém. Ale to musí byť na začiatku zoznamu v tomto prípade. Čo asi niečo ako Delete? Čo keď chcete zmazať prvok? Čo je horná hranica a dolná hranica o zmazanie niečo z spojená Zoznam? Divákov: [nepočuteľné] David J. Malan: znova, povedz? DIVÁKOV: n. David J. Malan: n je naozaj horná hranica. Vzhľadom k tomu, v najhoršom prípade sa snažíme odstrániť Jacka, ako sme to urobil. Je to úplne na konci. Nám trvá celú večnosť, alebo n kroky, aby ho našli. Tak to je horná hranica. To je lineárna, iste. A v najlepšom prípade doba chodu alebo dolná hranica v najlepšom prípade by byť konštantný čas. Vzhľadom k tomu, že by sme sa snaží odstrániť Christine, a my len mať šťastie ona je na začiatku. Teraz počkajte chvíľku. Gabe bol tiež na začiatku, a tiež sme museli aktualizovať Gabe. Takže to nebol len jeden krok. Tak to je naozaj konštantná Doba, v najlepšom prípade, na odstránenie najmenší prvok? To znamená, že aj keď to môže byť dve, tri, alebo dokonca sto riadkov kódu, či je to rovnaký počet linky, nie v nejakej slučke, a nezávisí od veľkosti zoznamu, absolútne. Odstránenie prvku na začiatok zoznamu, aj keď máme čo do činenia s Gabe, je stále konštantný čas. 

Takže to vyzerá, masívny krok späť. A čo je strata času v prípade, v jednom týždni a týždeň nula sme mali nielen pseudokód kód, ale skutočný kód realizovať niečo, čo denník base n, alebo prihláste skôr n, základ 2, pokiaľ ide o jeho prevádzke. Tak prečo sakra by sme chceli začať používať niečo ako prepojeného zoznamu? Jo. 

Divákov: Takže môžete pridať prvky do poľa. David J. Malan :, takže môžete pridať prvky do poľa. Aj to je tematická. A budeme aj naďalej vidieť by tento trade-off, veľa ako sme videli, trade-off s zlučovacie druhu. Naozaj by sa urýchliť vyhľadávania alebo triedenia, skôr ak by sme stráviť trochu viac priestoru a majú ďalší kus pamäte alebo pole pre zlúčenie druhu. Ale trávime viac priestor, ale šetrí čas. V tomto prípade sme vzdať sa času, ale my sme získanie flexibility, dynamika ak chcete, čo je pravdepodobne pozitívnu vlastnosť. 

Sme tiež výdavky priestor. V akom zmysle je spojený Zoznam drahšie z hľadiska priestoru, než pole? Ak je priestor navyše prichádza? Jo? 

Divákov: [nepočuteľné] ukazovateľ. 

David J. Malan: Jo, to sme majú tiež ukazovateľ. Tak toto je minorly nepríjemné v tom, že už som Aj ukladanie len int reprezentovať int. Som uloženie int a A ukazovateľ, ktorý je tiež 32 bitov. Takže som doslova zdvojnásobí množstvo priestoru podieľať. Takže je to kompromis, ale to je v prípade int. Predpokladajme, že si nie ste ukladanie int, ale predpokladám, že každý z týchto obdĺžnikov alebo každý z týchto ľudí bola predstavujúce slovo, anglické slovo, ktoré môže mať päť znakov, 10 postavy, možno aj viac. Potom sa pridá len 32 viac bitov môže byť menej veľký problém. 

Čo keď každý zo študentov na demonštráciu doslova študentské structs že majú mená a domy a možno telefónne čísla a Twitter spracováva a podobne. Takže všetky polia sme začali hovorí o iný deň, oveľa menej veľký problém, ako naše uzly dostať oveľa zaujímavejšie a veľké minúť, čo, ďalšie ukazovateľ len ich prepojenie. Ale naozaj, je to kompromis. A skutočne, je kód zložitejšie, ako budete viď zbieraním prostredníctvom že konkrétny príklad. Ale čo v prípade, že boli nejaký svätý grál tu. Čo keď nebudeme brať krok dozadu, ale masívny krok vpred a implementáciu dát Štruktúra cez ktorú môžete nájsť prvky, ako je Jack, alebo Christine alebo akékoľvek iné prvky v tomto poli v pravom konštantnom čase? Vyhľadávanie je konštantná. Odstrániť je konštantná. Vložte je konštantná. Všetky tieto operácie sú konštantné. To by nám svätý grál. A to je miesto, kde sme sa zdvihne nabudúce. Uvidíme sa potom.