SPEAKER 1: Dobre, takže sme späť. Vitajte na CS50. To je koniec týždňa sedem. Takže pripomenúť, že minule sme začali pri pohľade na niečo sofistikovanejšie dátové štruktúry. Vzhľadom k tomu, až do teraz, sme mali naozaj máme k dispozícii to bolo, pole. Ale skôr, než sme sa zbaviť poľa tak, že všetko zaujímavé, čo naozaj to v skutočnosti je, aké sú niektoré z klady tohto jednoduchého dát štruktúra tak ďaleko? Čo je to dobrý? Zatiaľ, ako sme videli? Čo to máš? Nič. STUDENT: [nepočuteľné]. SPEAKER 1: Čo je to? STUDENT: [nepočuteľné]. SPEAKER 1: Pevná veľkosť. OK, tak prečo je pevnou veľkosť dobrý aj keď? STUDENT: [nepočuteľné]. SPEAKER 1: OK, takže je to efektívna pocit, že môžete prideľovať pevná suma z vesmíru, čo snáď je presne toľko, koľko priestor tak, ako chcete. Takže to môže byť absolútne plus. Čo iného sa strana pole? Jo? STUDENT: [nepočuteľné]. SPEAKER 1: All - Čože? STUDENT: [nepočuteľné]. SPEAKER 1: Všetky boxy v pamäti alebo vedľa seba. A to je užitočné - prečo? To je celkom pravda. Ale ako môžeme využiť, že pravdu? STUDENT: [nepočuteľné]. SPEAKER 1: Presne tak, môžeme sledovať kde je všetko len na základe znalosti jednu adresu, a to na adresu prvý bajt tohto bloku pamäte. Alebo v prípade, že reťazec, adresa prvý char v tomto reťazci. A odtiaľ môžeme nájsť koniec reťazca. Nájdeme tu Druhý prvok, Tretia časť, a tak ďalej. A tak fantastický spôsob, ako to opísať rysom je, že pole nám náhodný prístup. Len pomocou hranatou zátvorkou zápis a číslo, môžete preskočiť na špecifický prvok v poli v konštantnom čase, veľké O jedného, ​​aby som tak povedal. Ale tam bolo nejaké tienisté stránky. Čo pole neurobil veľmi ľahko? Čo je to vôbec dobré? STUDENT: [nepočuteľné]. SPEAKER 1: Čo je to? STUDENT: [nepočuteľné]. Reproduktor 1: Rozšírenie vo veľkosti. Takže tienisté polia sú presne opak toho, čo upsides sú. Takže jedna z nevýhod je že je to pevnú veľkosť. Takže si môžete naozaj ju pestovať. Môžete prideliť väčší kus pamäť, a potom sa presunúť staré prvky do nového poľa. A potom bez stará pole, pre inštancie, pomocou malloc alebo podobný funkcia je volaná realloc, ktoré realokuje pamäť. Realloc, ako stranou, sa snaží, aby vám pamäť, ktorá je vedľa poľa že už máte. Ale to by sa veci pohli asi úplne. Ale v skratke, je to drahé, nie? Pretože ak máte kus pamäti tejto veľkosti, ale naozaj chcem tejto veľkosti, a chcete zachovať zachované pôvodné prvky, budete musieť približne lineárny čas Proces kopírovania že je potrebné, aby sa stalo od staré na nové pole. A realita sa pýta prevádzkové systém znovu a znovu a opäť veľké kusy pamäte môže začať stáť nejaký čas rovnako. Takže je to požehnaním i prekliatím v zastierať, že tieto polia sú pevné dĺžky. Ale keď si predstavíme niečo miesto takto, ktorú nazýva prepojený zoznam, dostaneme niekoľko upsides a niekoľko tienisté i tu. Takže spájať zoznam je jednoducho dát štruktúra tvorená structs C v tomto prípad, kedy struct, odvolanie, je len kontajner pre jeden alebo viac špecifických typy premenných. V tomto prípade, čo si dátové typy Zdá sa, že vo vnútri struct, ktorý Naposledy sme nazývaný uzol? Každý z týchto obdĺžnikov je uzol. A každý z menších obdĺžnikov vnútri nej je dátový typ. Aké typy si hovoríme boli v pondelok? Jo? STUDENT: [nepočuteľné]. SPEAKER 1: variabilné a ukazovateľ alebo Presnejšie povedané, int, pre N, a ukazovateľ v dolnej časti. Obaja ti stalo, že 32 bitov na aspoň na počítači, ako je tento CS50 Zariadení, a tak sú ťahané rovnako vo veľkosti. Takže to, čo používate ukazovateľ keď za zjavne? Prečo pridať na túto šípku teraz, keď pole bolo tak pekné a čisté a jednoduché? Čo je to ukazovateľ robí pre nás v každej z týchto uzlov? STUDENT: [nepočuteľné]. SPEAKER 1: Presne tak. Je to povie, kde Ďalšie nikto. Tak nejako som použiť analógiu pomocou vlákno nejako niť týchto uzlov dohromady. A to je presne to, čo robíme s ukazovatele, pretože každý z nich kúsky pamäti môže, ale nemusí byť súvislé, chrbtom k sebe k sebe v pamäti RAM, pretože zakaždým, keď sa volania malloc povedal, daj mi dosť bajtov pre nový uzol, mohlo by to tú, alebo by to mohlo byť. Mohlo by to byť tu. Mohlo by to byť tu. Proste neviem. Ale s použitím ukazovateľa na adresy ty uzly, môžete steh je spoločne tak, že vyzerá vizuálne ako zoznam, aj keď tieto veci sú všetko rozprestreté v celom jednom alebo vaše dve alebo štyri gigabajty vaše RAM vnútri vášho vlastného počítača. Tak nevýhodou, potom, spájať zoznam je čo? Čo je to cena, ktorú sme zrejme platiť? STUDENT: [nepočuteľné]. SPEAKER 1: Viac miesta, že jo? Sme v tomto prípade, zdvojnásobil množstvo priestoru, pretože sme šli z 32 bitov pre každý uzol, pre každú int, takže teraz 64 bitov, pretože musíme držať okolo ukazovateľ rovnako. Získate väčšiu účinnosť, ak váš struct je väčšia ako táto jednoduchá vec. Ak ste skutočne študenta vnútri z ktorých je niekoľko stringov meno a dom, možno číslo, možno niektorých ďalších odborov dohromady. Takže ak máte dostatočne veľký struct, potom možno cena ukazovateľ je nie je tak veľký problém. Toto je trochu rohové prípadu v tom, že sme ukladanie taký jednoduchý primitívne vnútri prepojeného zoznamu. Ale ide o to isté. Tie určite tráviť viac pamäť, ale vy ste stále flexibilita. Pretože teraz, keď chcem pridať prvok na začiatku tohto zoznamu, Musím prideliť nový uzol. A ja mám len tie aktualizácie šípky akosi len pohybujúce niekoľko rád okolo. Ak chcem vložiť niečo do uprostred zoznamu, nemám na tlačiť všetky stranou, ako tomu bolo v minulosť týždňov s našimi dobrovoľníkmi, ktorí predstavovala pole. Môžem len prideliť nový uzol a potom stačí poukázať na šípky v rôzne smery, pretože to nie je musí zostať v aktuálnej pamäť pravda, linka, ako by som vypracované je to tu na obrazovke. A potom napokon, ak chcete vložiť niečo na koniec zoznamu, je ešte jednoduchšie. To je niečo svojvoľného notáciu, ale 34 je ukazovateľ, hádajte. Aká je hodnota jeho ukazovateľ najviac pravdepodobne vyvodiť niečo ako starý Škola anténa tam? STUDENT: [nepočuteľné]. SPEAKER 1: Je to asi null. A naozaj to je jedna autora zastúpenie null. A to je null, pretože ste úplne Potrebujete vedieť, kde je koniec spojovaceho zoznam, inak budete mať nasledujúce a sledovanie a po týchto šípok do určitej hodnoty odpadky. Takže null bude znamenať, že neexistuje viac uzlov napravo od čísla 34, v tomto prípade. Takže navrhujeme, že môžeme realizovať tento uzol v kóde. A my sme videli tento druh syntaxe pred. Typedef len definuje nový typ nám, nám dáva ako synonymum string bol pre char *. V tomto prípade to bude, aby nám skrátený zápis tak, že struct uzol Namiesto toho môžete byť len zapísať ako uzol, ktorý je oveľa čistejšie. Je to oveľa menej ukecaný. Vnútri uzla je zrejme int tzv n, a potom struct node * čo znamená, že presne to, čo sme chceli šípky znamená, ukazovateľ na ďalšie uzol presne rovnakého typu. A ja navrhujem, aby sme mohli realizovať vyhľadávacie funkcie ako je tento, ktorý v prvý pohľad by sa mohlo zdať trochu zložitejšie. Ale pozrime sa, že v kontexte. Nechaj ma ísť cez spotrebiče tady. Dovoľte mi otvoriť súbor s názvom Zoznam nulový bod h A že obsahuje iba definíciu my práve videl pred chvíľou na tieto dáta typ nazývaný uzol. Takže sme dali, že do súboru dot hodín. A ako stranou, aj keď to program, ktorý sa chystáte vidieť, je nie je tak zložité, je to v skutočnosti Konvencie pri písaní programu dať veci ako dátové typy, ťahať konštanty niekedy vnútri vášho hlavičkový súbor a nie nevyhnutne v Váš súbor C, iste, keď si Programy sa väčšie a väčšie, takže viete, kde hľadať a to ako pre dokumentácia v niektorých prípadoch, alebo pre základy, ako je toto, Definície niektorých typov. Keby som sa tak otvára zoznam nulovú bodku c, všimnite si pár vecí. Obsahuje niekoľko hlavičkové súbory, väčšina ktoré sme ešte nevideli. Obsahuje vlastný hlavičkový súbor. A stranou, prečo je to dvakrát cituje tu, na rozdiel od uhla držiaky na trati, ktorá Som zdôraznil, že? STUDENT: [nepočuteľné]. SPEAKER 1: Jo, tak to je miestna súbor. Takže či je to miestna súbor z vašich vlastných tu na linke 15, napríklad, môžete použiť úvodzovky miesto z šikmých zátvorkách. Teraz je to celkom zaujímavé. Všimnite si, že som vyhlásil, globálne premennou v tomto programe na riadku 18 tzv prvé, myšlienka je to bude ukazovateľ na prvý uzol v mojom prepojeného zoznamu, a ja som inicializovaná, na hodnotu null, pretože som nie je pridelené žiadne skutočné uzly len zatiaľ. Takže to znamená, obrazovo, čo sme videl pred chvíľou na obrázku ako že ukazovateľ na ďaleko ľavej strane. Takže teraz, že ukazovateľ nemá šípku. Je to miesto je len null. Ale to znamená, čo bude adresa prvý skutočný uzol v tomto zozname. Tak som sa implementácie je globálna pretože, ako uvidíte, to všetko Program sa v živote realizovať spájať zoznam pre mňa. Teraz mám niekoľko prototypov tu. Rozhodol som sa implementovať funkcie, ako je mazanie, vkladanie, vyhľadávanie a priechod - posledný byť len pešo cez zoznam, vytlačenie jeho prvky. A teraz je môj hlavný rutina. A nebudeme tráviť príliš veľa času na to, pretože to je niečo, dúfajme starý klobúk teraz. Chystám sa urobiť nasledovné, zatiaľ čo používateľ spolupracuje. Takže jedno, ja idem k tlači z tohto menu. A ja som ho formátovať ako čisto, ako som mohol. Ak používateľ zadá v jednom, to znamená, že ktoré chcete odstrániť niečo. V prípade, že užívateľ zadá vo dvoch, to znamená, že ktoré chcete vložiť niečo. A tak ďalej. Chystám sa potom vás vyzve potom na príkaz. A potom budem používať GetInt. Tak to je naozaj jednoduché menuing rozhranie, kde stačí zadať číslo mapovanie na jeden z týchto príkazov. A teraz mám pekný čistý vypínač vyhlásenie, že sa to zapnúť čo užívateľ napísal palcov A keď napísal jeden, ja zavolajte odstrániť a rozbiť. Ak zadali dva, ja zavolajte vložiť a zlomiť. A teraz Všimnite si, že som dal každý z nich na rovnakom riadku. Je to len štylistické rozhodnutia. Zvyčajne sme videli niečo takhle. Ale ja som sa rozhodol, úprimne povedané, môj program Pozrel čitateľnejší, pretože to bolo len štyri prípady, na vypísalo to takto. Úplne legitímne použitie štýlu. A ja budem robiť to tak dlho, kým užívateľ nezadali nulu, čo som rozhodol, bude znamenať, že chcú s fajčením prestať. Takže teraz upozornenie, čo som robiť tu. Chystám sa uvoľniť zoznamu zdanlivo. Ale o tom až za chvíľu. Poďme si najprv spustiť tento program. Takže mi dovoľte väčší terminál okná, bodka lomítko list 0. Chystám sa ísť dopredu a vložiť, písanie dva, ako je číslo 50, a teraz uvidíte zoznam je teraz 50. A môj texte len posúvať sa trochu. Takže teraz všimnúť zoznam obsahuje číslo 50. Poďme urobiť ďalšie vložku tým, že dvaja. Poďme zadajte číslo ako jeden. List je teraz jeden, nasleduje 50. Tak to je len textová reprezentácia zoznamu. A poďme vložiť ešte jedno číslo ako číslo 42, čo je snáď chystá skončiť v stredu, pretože Tento program v jednotlivých druhov sa prvky, ako to vloží je. Takže tu to máme. Super jednoduchý program, ktorý by absolútne použili celý rad, ale ja stalo, že sa pomocou prepojeného zoznamu len tak môžem dynamicky zväčšiť a zmenšiť ju. Takže poďme sa pozrieť pre vyhľadávanie, keď som spustiť príkaz tri, Chcem vyhľadávať pre, povedzme, číslom 43.. A nič sa zrejme našiel, pretože som sa vrátil žiadnu odpoveď. Tak ideme na to znova. Hľadať. Poďme hľadania 50, alebo skôr hľadanie na 42, čo je pekný Trochu jemnejší význam. A ja som našiel zmysel života tam. Číslo 42, pokiaľ neviete, referencie, Google ho. Dobrá. Takže to, čo tento program pre mňa urobil? Je to len mi dovolil vložiť tak ďaleko a hľadanie prvkov. Poďme rýchlo vpred, potom sa že funkcia sa pozrel na v pondelok ako ukážku. Takže túto funkciu, tvrdím, hľadá element v zozname ako prvé jeden, upozornenia užívateľa a volanie GetInt získať aktuálne int ktoré chcete vyhľadať. Potom nevšimol. Chystám sa vytvoriť dočasnú premennú v súlade s názvom 188 ukazovateľ - PTR - mohla zavolať tomu nič. A je to ukazovateľ na uzol pretože som povedal, že uzol *. A ja inicializácia je rovná najprv tak, že som skutočne mať svoju prstom, aby som tak povedal, na veľmi Prvý prvok zoznamu. Takže ak moja pravá ruka je tu PTR som ukazuje na rovnakú vec, že ​​prvý ukazuje na. Takže teraz späť v kóde, čo sa bude diať ďalej - je to spoločný vzor, ​​keď iterácie cez štruktúry, ako spájať zoznam. Chystám sa urobiť nasledovné, zatiaľ čo ukazovateľ nie je rovné null Takže zatiaľ čo môj prst neukazuje na nejaké null hodnota, ak je ukazovateľ šípka n sa rovná n Sme si všimnete ako prvé, že n je to, čo Užívateľ napísal v prepočte GetInts zavolať tady. A ukazovateľ šípka n znamená čo? No, ak sa vrátime k obrázku tu keď mám prst ukazujúci na že prvý uzol obsahuje deväť, Šípka v podstate znamená, že ísť do uzol a chytiť hodnotu pri umiestnení n, V tomto prípade sú dáta poľa s názvom n Ako stranou - a videli sme to ešte pred pár týždne, keď sa niekto opýtal - táto syntax je nový, ale to nie je nám sily, ktoré sme už nemalo. Čo to bolo za výraz ekvivalentná k použitie bodka zápis a hviezda pár týždne, keď sme zlúpnuť táto vrstva trochu predčasne? STUDENT: [nepočuteľné]. SPEAKER 1: Presne tak, je to hviezda, a potom je to hviezda bodka n, s zátvorky tu, ktorý vyzerá, Úprimne povedané, myslím, že veľa viac tajomné čítať. Ale hviezda ukazovateľ, ako vždy, znamená ísť. A akonáhle ste tam, aké údaje Pole chceš prístup? No použiť bodka notáciu pre prístup struct dátové polia, a ja konkrétne chcete n Úprimne povedané, povedal by som to je jednoducho ťažšie čítať. Je to ťažšie si spomenúť, kde sa zátvorky idú, hviezda a to všetko. Aby celý svet prijal niektoré syntaktické cukor, aby som tak povedal. Len sexy spôsob, ako povedať, To je ekvivalentné, a možno viac intuitívne. Je-li ukazovateľ je skutočne ukazovateľ, znamená notácie šípky ísť a nájsť pole je v tomto prípade tzv n Takže ak ju nájdem, všimnite si, čo robím. Jednoducho vytlačiť, našiel som percent ia zapojíte hodnotou pre daný int. Nazval som spať po dobu jednej sekundy, len aby druhu pauzy vecí na obrazovke poskytujú užívateľovi druhej absorbovať čo sa práve stalo. A potom som sa zlomiť. Inak, čo mám robiť? Aktualizovať ukazovatele rovná ukazovateľ šípku vedľa. Tak aby bolo jasno, to znamená ísť tam cez môj old-school notácie. Takže to znamená len ísť do čohokoľvek ste ukázal na, ktoré veľmi Prvým prípadom je, že som ukázal na struct s deviatimi v ňom. Tak som šiel tam. A potom bodka notácie znamená, získať hodnotu na ďalšie. Ale hodnota, a to aj keď je čerpané ako úzky, len číslo. Je to číselná adresa. Takže tento jeden riadok kódu, či už napísal takhle viac zložitejšie spôsobom, alebo ako je to, o niečo viac intuitívny spôsob, jednoducho znamená pohnúť rukou z prvého uzla na ďalšie, a potom ďalší, a potom ďalšie, a tak ďalej. Takže nebudeme bývať na strane druhej implementácia vkladanie a mazanie a priechod, z ktorých prvé dva ktoré sú pomerne zapojiť. A myslím, že je to celkom jednoduché sa dostať stratil, keď robí to ústne. Ale to, čo môžeme urobiť, je tu pokusu o stanovenie najlepšie urobiť to vizuálne. Pretože by som navrhoval, že ak by sme Chcem vložiť prvky do tohto Existujúci zoznam, ktorý má päť prvkov - 9, 17, 22, 26, a 33 - Keby som mal ísť na vykonanie tohto v kód, musím zvážiť, ako ísť o robiť. A ja by som navrhnúť, pričom dieťa kroky pričom v tomto prípade mám na mysli, aké sú možných scenárov, ktoré sme stretnúť všeobecne? Pri vykonávaní vložka pre prepojenú zoznam, to je náhodou Konkrétnym príkladom veľkosti päť. No, ak chcete vložiť číslo, radi hovoria, že číslo jedna, a udržiavanie zoradené objednávky, kde samozrejme robí číslo jedna potreba ísť v tomto konkrétnom príklade? Rovnako ako na začiatku. Ale čo je zaujímavé je, že Ak chcete vložiť jeden do toho zoznam, čo potrebuje špeciálny ukazovateľ aktualizovať zrejme? Prvý. Takže by som si dovolil tvrdiť, toto je prvý prípad že by sme mohli chcieť, aby zvážila, scenár zahŕňajúci vkladanie na na začiatku zoznamu. Poďme trhať off možno tak jednoduché, alebo dokonca jednoduchší prípad, relatívne vzaté. Dajme tomu, že chcete vložiť číslo 35 v zoradení poradí. To samozrejme patrí tam. Takže to, čo ukazovateľ zrejme bude musia byť aktualizované v tomto prípade? 34 je ukazovateľ stále nie je null ale adresa struct obsahujúce číslo 35. Tak to je prípad dvoch. Tak už som trochu kvantizácia koľko práce musím urobiť tu. A konečne zrejmé, prostredný prípad naozaj, v stredu, keď chcem vložiť niečo ako, povedzme 23, ktorá vedie medzi 23 a 26, ale teraz sa veci trochu viac podieľa pretože to, čo ukazovateľa je treba zmeniť? Tak 22 samozrejme je potrebné zmeniť pretože nemôže odkazovať na 26 už nie. Že je potrebné, aby odkazoval na nový uzol, ktorý Budem sa musieť rozdeliť na telefónnom čísle malloc alebo iným ekvivalentným. Ale potom som tiež potrebovať nový uzol, 23 V tomto prípade, aby sa jej ukazovateľ ukázal na koho? 26. A tam to bude poradí úkonov tu. Pretože keď som to hlúpo a ja napríklad od začiatku roka zoznam, a mojím cieľom je, vložiť 23. A ja som skontrolovať, to patrí Tu, v blízkosti deviatich? Nie. Znamená to sem patrí, popri 17? Nie. Má to sem patrí popri 22? Áno. Teraz, keď som hlúpy tu, a nie myslí si, až by som mohol prideliť môj nový uzol 23. By som mohol aktualizovať ukazovateľ z uzol s názvom 22, smerujúce že na nový uzol. A potom to, čo mám aktualizovať Nový uzol je ukazovateľ, že? STUDENT: [nepočuteľné]. SPEAKER 1: Presne tak. Ukázal na 26 rokov. Ale Dammit keby som nemal už aktualizovať 22 je ukazovateľ ukazovať na toho chlapa, a teraz mám siroty, zvyšok zoznamu, aby som tak povedal. Takže poradí operácií tu bude dôležité. K tomu by som mohol ukradnúť, povedzme, šesť dobrovoľníkov. A uvidíme, či môžeme to urobiť vizuálne namiesto kódu ručičiek. A máme nejaké krásne stres lopty pre vás dnes. OK, ako sa o jeden, dva, vo späť - na konci tam. tri, štyri, obaja chlapci na konci. A päť, šesť. Iste. Päť a šesť. Dobre a my sa na vás nabudúce. Dobre, poď hore. Dobre, keď už si tu prvýkrát, by ste chceli byť tým, kto nešikovne v skle Google tu? Dobre, takže OK, sklo, videozáznam. OK, máte dobré ísť. Dobre, takže ak vy môžete prísť tu som vopred pripravené niektoré čísla. Dobre, poď sem. A prečo nejdeš trochu ďalej týmto spôsobom. A pozrime sa, ako sa voláš, so skleneným Google? STUDENT: Ben. SPEAKER 1 Ben? OK, Bene, budete prvý, a to doslova. Takže budeme posielať do konca obdobia. Dobre, a vaše meno? STUDENT: Jason. SPEAKER 1: Jason, OK budete byť číslo deväť. Takže ak budete chcieť sledovať Ben týmto spôsobom. STUDENT: Jill. SPEAKER 1: Jill, budete mať 17, ktorá, ak by som to urobil viac inteligentne, musel by som začal na druhom konci. Môžete ísť tadiaľ. 22. A vy ste? STUDENT: Mary. SPEAKER 1: Mary, budete 22. A vaše meno? STUDENT: Chris. SPEAKER 1: Chris, budete 26. A potom konečne. STUDENT: Diana. SPEAKER 1: Diana, budete 34. Takže si poď sem. Dobre, takže perfektné radené objednať už. A poďme ďalej, a to takže môžeme naozaj - Ben si len trochu hľadať von nikde tam. OK, takže poďme ďalej, a líči to použitie zbrane, rovnako ako ja, presne, čo sa deje. Takže choďte do toho a dať sami si noha alebo dva medzi sebou. A choďte do toho a pritom s jednou rukou na ktokoľvek, mali by ste sa ukázal na na základe tohto. A ak ste null len bod priamo na podlahu. OK, tak dobre. Takže teraz máme prepojený zoznam, a dovoľte mi, aby som navrhnúť, že budem hrať rolu PTR, tak som sa neobťažoval vykonávanie tohto okolia. A potom - niekto hlúpy konvencie - môžete volať to, čo chcete - predchodca ukazovateľ, pred ukazovateľ - je to len prezývka sme dali v náš ukážkový kód k mojej ľavej ruke. Na druhej strane, ktorá bude udržiavať sledovať, kto je kto v nasledujúce scenáre. Takže predpokladám, najprv chcem trhať off , Že prvý príklad vkladanie, povedzme 20, do zoznamu. Takže budem potrebovať niekoho, kto by stelesňujú číslo 20 pre nás. Tak som potrebné niekoho malloc z publika. Poď hore. Ako sa voláte? STUDENT: Brian. SPEAKER 1: Brian, v poriadku, takže musí byť uzol obsahujúci 20. Dobre, poď sem. A samozrejme, ak Brian sa patrí? Tak, v stredu - v skutočnosti, počkaj. Robíme to mimo poradia. Robíme to oveľa ťažšie než je potrebné, aby sa na prvom mieste. OK, ideme na voľný Brian a realloc Brian ako päť. OK, tak teraz chceme vložiť Brian ako päť. Tak poď sem vedľa Ben na chvíľu. A môžete povedať, pravdepodobne kde tento príbeh bude. Ale poďme starostlivo premyslieť, poradí úkonov. A je to práve táto vizuálna že sa to zoradia s týmto ukážkový kód. Tak tu som PTR ukázal najprv nie je na Bena, samo o sebe, ale bez ohľadu na cení, že obsahuje, čo je v tomto prípade je - ako sa volá? STUDENT: Jason. SPEAKER 1: Jason, tak ako Ben a ja sme ukázal na Jasona v tomto okamihu. Takže teraz musím zistiť, kde sa Brian patrí? Takže jediné, čo mám prístup k Práve teraz je jeho n údajová položka. Takže budem kontrolovať, je Brian menej než Jasona? Odpoveď je pravda. Tak čo teraz musí stať, v správnom poradí? Musím aktualizovať, koľko ukazovateľov celkom v tomto príbehu? Kde je moja ruka stále ukazuje na Jason a vaše ruky - ak chcete dať ruku ako, tak nejako som neviem, otáznik. OK, dobre. Dobre, takže máte niekoľko kandidátov. Buď Ben alebo ja alebo Brian alebo Jason alebo všetci ostatní, ktoré ukazovateľa je treba zmeniť? Koľko celkom? OK, tak dva. Môj ukazovateľ nezáleží už pretože som len dočasné. Takže je to títo dvaja, pravdepodobne, ako Ben a Brian. Takže mi dovoľte navrhnúť, aby sme aktualizácie Ben, pretože je to prvýkrát. Prvý prvok tohto zoznamu sa teraz bude Brian. Takže Ben bod na Briana. OK, čo teraz? Kto dostane ukázal na koho? STUDENT: [nepočuteľné]. SPEAKER 1: OK, takže Brian má ukázať na Jasona. Ale už som stratil prehľad o tomto ukazovateľ? Viem, kde je Jason? STUDENT: [nepočuteľné]. SPEAKER 1: ja, pretože som dočasný ukazovateľ. A pravdepodobne som sa nezmenil ukázať na nový uzol. Takže môžeme jednoducho Brian bod na toho, kto mi ukázal na. A sme hotoví. Tak jeden prípad, vo vloženie na začiatku zoznamu. Tam boli dva hlavné kroky. Po prvé, musíme aktualizovať Bena, a potom musíme tiež aktualizovať Briana. A potom nemám obťažovať traipsing cez zvyšok zoznam, pretože sme už našli jeho umiestnenie, pretože patril k vľavo od prvého prvku. Dobre, takže celkom jednoduché. V skutočnosti, pocit, že sme skoro takže to príliš zložité. Takže poďme sa odtrhnúť z konca zoznamu, a zistiť, kde zložitosť začína. Takže keď teraz som Alloc z publika. Každý, kto chce hrať 55? Tak jo, videl som svoju ruku ako prvý. Poď hore. Jo. Ako sa voláte? STUDENT: [nepočuteľné]. SPEAKER 1: Habata. OK, poď hore. Budete mať číslo 55. Takže vy, samozrejme, patrí na konci zoznamu. Takže poďme prehrať simuláciu so mnou bytia PTR len na chvíľu. Tak som prvýkrát bude ukazovať na bez ohľadu na to Ben ukázal na. Obaja sme ukazuje teraz na Briana. Takže 55 je nie menej ako päť. Takže budem aktualizovať tým, že som ukázal na ďalší ukazovateľ Brianovi, ktorý Teraz je samozrejme Jasona. 55 je menšia ako deväť, takže Chystám sa aktualizovať PTR. Chystám sa aktualizovať PTR. Chystám sa aktualizovať PTR Budem aktualizovať PTR. A ja idem - hmm, čo je Vaše meno znova? STUDENT: Diana. SPEAKER 1: Diana ukazuje, samozrejme, pri nulovom s ľavou rukou. Takže tam, kde sa skutočne Habata patrí jasne? Na ľavej strane, tu. Tak ako mám vedieť, že ju tu Myslím, že som to pokašľal. Pretože to, čo je umenie PTR tento okamih v čase? Null. Takže aj keď vizuálne, môžeme samozrejme vidieť všetky z nich chalani tu na javisku. Ja som to sledoval z predchádzajúcej osoba v zozname. Nemám prst ukazujúci von, V tomto prípade, uzol číslo 34. Takže poďme skutočne začať to znova. Takže teraz vlastne nepotrebujete Druhý lokálna premenná. A to je to, čo uvidíte v Skutočný vzorka C kód, kde, ako som ísť, keď som aktualizovať pravú ruku k bodu Jason, pričom je nutné Brian zozadu, som lepšie začať používať ľavú ruku k aktualizovať, kde som bol, takže, ako som ísť pomocou tohto zoznamu - viac rozpačito, ako som chcel teraz tu vizuálne - Chystám sa dostať do koniec zoznamu. Táto ruka je ešte stále nulový, čo je celkom zbytočné, iba ukazujú Som jednoznačne na konci zoznamu, ale teraz aspoň to mám predchodca ukazovateľ tu, tak Čo teraz odovzdáva a aké ukazovatele musia aktualizovať? Čí ruka chceš prekonfigurovať prvý? STUDENT: [nepočuteľné]. SPEAKER 1: OK, tak Dianin. Kam chcete nasmerovať Dianin ľavý ukazovateľ na? Na 55, pravdepodobne tak, že sme tam vložiť. A kde by 55 ukazovateľ ísť? Nadol, čo null. A moje ruky, v tomto bode, nie jedno, pretože oni boli len dočasné premenné. Takže teraz sme hotoví. Takže ďalšie zložitosti tam - a že to nie je tak ťažké zaviesť, ale potrebujeme sekundárnu premennú, aby sa istý, že predtým, než som sa pohnúť právo ruka, som aktualizovať hodnotu mojej ľavici ruka, pred ukazovateľ v tomto prípade, tak že mám koncové ukazovatele sledovať, kde som bol. Teraz, ako stranou, ak si myslíte tohle cez to pocit, že je to Trochu nepríjemné mať na sledovanie tohto ľavej ruky. Čo by iné riešenie tohto problému boli? Ak ste sa dostali k redesign dáta Štruktúra hovoríme až teraz? Ak je to len trochu cíti trochu nepríjemné mať rada, dva ukazovatele prechádza zoznam, kto by mohol inak sa, v ideálnom svete, udržiavané Informácie, ktoré potrebujete? Jo? STUDENT: [nepočuteľné]. SPEAKER 1: Presne tak. Pravá takže je to vlastne zaujímavý zárodok nápadu. A táto myšlienka na predchádzajúcu ukazovateľ, ukazuje na predchádzajúci prvok. Čo keď som stelesnený, že v zozname sám? A to bude ťažké si predstaviť, to bez všetkých papiera pádu na zem. Ale predpokladajme, že títo ľudia používajú ako ich rúk mať predchádzajúce ukazovateľ, a ďalší ukazovateľ, čím realizuje to, čo budeme hovoriť dvakrát spájať zoznam. To by mi dovoľte, aby som nejako vzad oveľa ľahšie, bez toho by ma, programátor, musela držať sledovať ručne - skutočne ručne - , Kde som bol predtým v zozname. Takže nebudeme robiť. Budeme držať to jednoduchý, pretože to je príde za cenu, čo je dvakrát veľa priestoru pre ukazovatele, ak chcete druhú. Ale to je naozaj spoločný dátové štruktúry známej ako dvojnásobne spájať zoznam. Poďme urobiť posledný príklad tu a dal títo chlapci z ich utrpenia. Tak malloc 20. Poď sa z uličky tam. Dobre, Ako sa voláte? STUDENT: [nepočuteľné]. SPEAKER 1: Je nám ľúto? STUDENT: [nepočuteľné]. SPEAKER 1: Demeron? OK poď hore. Tie musia byť 20. Tie samozrejme budú Patrí medzi 17 a 22. Takže dovoľte mi učiť moje lekciu. Chystám sa začať ukazovateľ ukázal na Briana. A ja budem mať ľavú ruku aktualizovať iba k Brianovi, ako som sa presunúť na Jason, kontrola robí 20 menej ako deväť? Nie. Je o 20 menej ako 17? Nie. Je o 20 menej ako 22? Áno. Takže to, čo ukazovátka alebo ruky je potrebné zmeniť kde to ukazuje teraz? Takže, čo môžeme urobiť 17 ukazuje na 20 rokov. Tak to je v poriadku. Kde chceme upozorniť ukazovateľ myši teraz? V 22. A my vieme, kde 22 je opäť vďaka k môjmu dočasné ukazovatele. Tak to je v poriadku tam. Takže kvôli tejto dočasné skladovanie Nechal som sledovať, kde sa všetci. A teraz môžete ísť do vizuálne, kde patríte, a teraz potrebujeme 1, 2, 3, 4, 5, 6, 7, 8, 9 stres lopty, a potlesk pre títo chlapci, keby sme mohli. Dobrá práca. [APPLAUSE] SPEAKER 1: Dobre. A môžete držať kusy papiera ako pamiatku. Dobre, takže, verte mi, je to veľa jednoduchšie prejsť, aby sa ľudia, než je tomu u skutočného kódu. Ale to, čo nájdete za chvíľu teraz, je to rovnaké - ach, ďakujem. Ďakujem - je, že zistíte, že rovnaké údaje štruktúra, komunikačné zoznam, môže v skutočnosti byť použité ako stavebný blok k ešte sofistikované dátové štruktúry. A uvedomiť si taky tému tu je, že sme absolútne predstavil viac zložitosť do realizácie tohto algoritmu. Vloženie, a keď sme išli cez to, vymazanie a vyhľadávanie, je trochu komplikovanejšia, než sa bol s radom. Ale získať nejaké dynamiku. Dostávame adaptívne štruktúru dát. Ale opäť platíme cenu, že niektoré ďalšie zložitosť, a to ako v vykonávanie. A my sme sa vzdali náhodný prístup. A aby som bol úprimný, že to nie je nejaké pekné čistenie snímku môžem dať, že hovorí, že je tu dôvod, prečo spájať zoznam je lepšia ako pole. A nechať to tak. Pretože téma znovu objavuje teraz, aj viac v nadchádzajúcich týždňoch, je že to nemusí byť nutne správna odpoveď. To je dôvod, prečo máme samostatnú os dizajnu pre základné problémové okruhy. Bude to veľmi kontextová či chcete tieto dáta použiť štruktúra alebo že jeden, a to bude závisí na to, čo je pre vás z hľadiska zdrojov a zložitosti. Ale dovoľte mi navrhnúť, aby bola ideálna údajov štruktúra, Svätý grál, bude niečo, čo je konštantný čas, bez ohľadu na to, koľko vecí je vnútri, nebolo by úžasné, keby dátová štruktúra sa vrátil v odpovedi konštantný čas. Áno. Toto slovo je v obrovskej slovníka. Alebo nie, to slovo nie je. Alebo akýkoľvek taký problém tam. No uvidíme, či môžeme aspoň nie krok smerom k tomuto. Dovoľte mi skoncipovať novú dátovú štruktúru, ktorá môžu byť použité pre rôzne veci, v tomto prípade nazýva hash tabuľky. A tak sme vlastne späť pohľadom na poli, v tomto prípade, a trochu umelo, ja som to vypracované hash tabuľky ako polia s druhom dvojrozmerné pole - alebo skôr to tu zobrazený ako dva rozmerné pole - ale to je len pole o veľkosti 26, tak, že ak sa zavolajte pole, stolný držiak nula je obdĺžnik v hornej časti. Stolný držiak 25 je obdĺžnik v spodnej časti. A to je, ako by som mohol nakresliť dát štruktúra, v ktorej chcem uložiť Mená ľudí. Tak napríklad, a nebudem kresliť Celá vec tu na strope, keď som mal toto pole, ktoré som teraz bude volanie hash tabuľky, a to je opäť umiestnenie nula. Tohle je miesto jeden, a tak ďalej. Tvrdím, že chcem použiť tieto dáta štruktúra, v záujme diskusie Uloženie mien ľudí, Alice a Bob a Charlie a ďalšie podobné názvy. Takže myslíte, že o tom dnes rovnako ako začiatky , Povedzme, v slovníku s množstvom slov. Oni stalo, že sa mená v našom príklade tu. A to je príliš Germany, snáď, aby vykonáva kontrolu pravopisu, ako my Môžu to byť problémom nastaviť šesť. Takže ak máme rad celkovej veľkosti 26 tak, že sa jedná o umiestnenie 25. na dne, a tvrdím, že je Alice prvé slovo v slovníku Názvy, ktorých chcem vložiť do pamäte RAM, do tejto dátové štruktúry, kde sú inštinkt hovorí, že Alice je Názov by mal ísť v tomto poli? Máme 26 možností. Ak chceme ju? Chceme ju v zátvorke nula, nie? A pre Alicu, povedzme, že nula. A B bude jeden, a C budú dva. Takže budeme písať Alicin meno tu. Ak sa potom vložte Bob, jeho názov pôjde tu. Charlie pôjde tu. A tak ďalej nadol Táto dátová štruktúra. Je to nádherná štruktúra dát. Prečo? No čo je časová zložitosť vložením ľudského meno do tohto štruktúra dát práve teraz? Vzhľadom k tomu, že táto tabuľka je implementovaná, naozaj ako pole. No, je to konštantný čas. To je cieľom jedného. Prečo? Tak, ako si zistiť, kde Alice patrí? Keď sa pozriete na ktoré písmeno jej mena? Prvý. A môžete sa tam dostať, keď je to reťazec, len o pohľade na povrázku držiak nula. Takže nultý znak reťazca. To je jednoduché. To sme urobili v crypto priradenie týždne. A potom ešte raz viete, že Alice písmeno veľké, môžeme odčítať off 65 alebo kapitálu je sám, že nám dáva nulu. Takže teraz vieme, že patrí Alice v mieste nulové. A vzhľadom k tomu ukazovateľ k týmto údajom štruktúra, nejakého druhu, ako dlho trvá to sa mi nájsť miesto nula v poli? Len jeden krok, že je to konštantná čas pretože s ľubovoľným prístupom sa Navrhované bol rys poľa. Takže v skratke, zisťuje, čo index Alice je názov, ktorý je v V tomto prípade je, alebo nech to jednoducho riešiť že k nule, kde B je jedna a C je dva, zisťuje, že z je konštantný čas. Musím sa pozrieť na jej prvý list, prísť na to, kde je nula Pole je tiež konštantná dobu. Takže technicky to ako dva kroky teraz. Ale to je stále konštantná. Takže hovoríme, že veľký O jednej, takže sme vložená Alicu do tejto tabuľky v konštantný čas. Ale samozrejme, ja som bol naivné, nie? Čo keď tam Aaron v triede? Alebo Alicia? Alebo nejaké iné názvy začínajúce na A. Kam ideme dať že človek, nie? Chcem povedať, teraz je tu len tri Ľudia na stole, takže možno sme mali dať Aaron v mieste nula jedna dva tri. Jasne, mohol som tu. Ale potom, keď sa snažíme vložiť do Davida tento zoznam, kde sa Dávid ísť? Teraz náš systém spustí vypínací nadol, nie? Pretože teraz David skončí tu ak Aaron je v skutočnosti tu. A tak sa celá táto predstava, že čistá dátová štruktúra, ktorá nám dáva konštantnom čase vložky už nie je konštantný čas, pretože musím zistiť, oh, sakra, niekto to už v mieste Alice. Dovoľte mi, aby som preskúmať zvyšok týchto údajov štruktúra, hľadať miesto dať niekto ako meno Aaron. A tak to taky začína aby sa lineárny čas. Navyše, ak sa chcete vyhľadať Aaron v tejto dátovej štruktúre, a skontrolovať, a Áronova meno tú nie. V ideálnom prípade by ste práve povedal Áronovi nie je v dátovej štruktúre. Ale ak si začnete robiť priestor pre Aaron tam, kde by boli D alebo E, tie, v najhoršom prípade, je nutné skontrolovať Celá štruktúra dát, vo takom prípade prejde do niečoho lineárne vo veľkosti tabuľky. Takže v poriadku, ja to opraviť. Problém je, že som mal 26 prvkov v tomto poli. Dovoľte mi, aby som ju zmeniť. Jejda. Dovoľte mi, aby som ho zmeniť tak, že namiesto bytia veľkosť 26 celkom, všimnite si na dno index sa zmení na n mínus jedna. Ak 26 je zjavne príliš malá pre človeka " mená, pretože tam sú tisíce mená na svete, jednoducho robiť na 100 alebo 1000 alebo 10000. Povedzme prideliť oveľa viac priestoru. Dobre, že nemusí nevyhnutne znížiť pravdepodobnosť, že nebudeme mať dva ľudia s názvami začínajúci a tak si to skúsiť dať mená na umiestnení nulu stále. Stále bude zrazí, čo znamená, že stále potrebujeme riešenia, aby Alice a Árona a Alicia a ďalšie Mená začínajúce A inde. Ale aký veľký problém to je? Čo je to pravdepodobnosť, že si majú kolízie v dátovom Štruktúra takto? No, dovoľte mi, aby som - vrátime sa na túto otázku tu. A pozrite sa na to, ako by sme mohli riešiť ako prvé. Dovoľte mi, aby som vytiahnuť tento návrh tu. To, čo sme práve popísal, je algoritmus, heuristický tzv lineárne snímanie, kedy, ak ste sa pokúsili vložiť niečo, čo tu v týchto údajov štruktúra, ktorá sa nazýva hash tabuľky, a neexistuje žiadny priestor tam, skutočne skúmať štruktúru dát kontrola, je to k dispozícii? Je to k dispozícii, je to k dispozícii? Je to k dispozícii? A keď konečne je vložíte meno, ktoré ste pôvodne zamýšľal inde v tomto mieste. Ale v najhoršom prípade iba bod môže byť veľmi spodné údajov štruktúra, veľmi koniec poľa. Takže lineárne sondy, v najhoršom prípade, prejde do lineárny algoritmus, kde Aaron, keď sa stane byť vložený posledný v tejto dátovej štruktúre, mohol by kolidovať s týmto prvom mieste, ale potom koniec smola v samom závere. Takže to nie je konštantná Doba svätý grál pre nás. Tento prístup, vkladanie prvkov do dátová štruktúra nazýva hash tabuľka sa nezdá byť konštantný čas aspoň nie vo všeobecnom prípade. To môže prejsť do niečoho lineárne. Takže čo keby sme vyriešiť kolízie trochu inak? Tak tu je to zložitejšie priblížiť to, čo je ešte tzv hash tabuľky. A hash, ako stranou, čo Mám na mysli, je index, ktorý Som sa zmienil predtým. Ak chcete niečo hash môže byť myšlienka ako slovesá. Takže ak hash Alice je meno, hašovacej funkcie, aby som tak povedal, by mala vrátiť číslo. V tomto prípade je nula, ak sa patrí na umiestnenie nula, jedna, ak sa patrí na polohy na jednej, a tak ďalej. Takže moja hashovacie funkcie bolo doteraz Super jednoduché, len pri pohľade na Prvé písmeno v niečí meno. Ale hašovacej funkcie berie ako vstup niektorých údaj, string, int, čokoľvek. A to vypľuje typicky číslo. A to číslo je, že dáta, kedy element patrí do dátovej štruktúry známy tu ako tabuľky hash. Tak len intuitívne, to je mierne odlišný kontext. Toto vlastne odvoláva na príklad zahŕňajúce narodeniny, kde tu môže byť toľko, koľko 31 dní v mesiaci. Ale čo sa táto osoba rozhodne robiť v prípade nehody? Kontext teraz byť, nie kolízii mená, ale kolízie narodenín, keď sa dvaja ľudia majú narodeniny v rovnaký deň na 2. októbra, napríklad. STUDENT: [nepočuteľné]. Reproduktor 1: Jo, tak tu máme využitie prepojených zoznamov. Takže to vyzerá trochu inak než sme nakreslil predtým. Ale zdá sa, že na pole na ľavej strane. To je jeden index, a to bez osobitný dôvod. Ale je to stále poľa. Je to pole ukazovateľov. A každý z týchto prvkov, z ktorých každý z Tieto kruhy alebo lomky - slash predstavuje null - každá z týchto ukazovatele sa zrejme ukazuje na čo dátová štruktúra? Spájať zoznam. Takže teraz máme schopnosť pevný kód do nášho programu veľkosť tabuľky. V tomto prípade vieme, že nikdy viac ako 31 dní v mesiaci. Tak ťažké kódovanie hodnoty, ako je 31 rozumné v tomto kontexte. V súvislosti s názvami, pevný kódovanie 26 nie je od veci, že ľudia to iba názvy začínajú, napríklad, abeceda zapojenie do Z. Môžeme sa napchať ich všetky do týchto údajov štruktúra tak dlho, ako keď sme si kolízie, nemáme dať mená tu, namiesto toho, že z týchto buniek nie ako reťazce samotné, ale odkazy na, napríklad, Alice. A potom Alice môže mať iný ukazovateľ na iný názov začína A. A Bob sa vlastne deje tu. A ak je tu ďalší meno začínajúce pomocou B, on skončí tu. A tak každý z prvkov tohto stolný dva, keď sme navrhli tento trochu viac chytro - no - keď sme navrhli to trochu viac chytro, sa teraz stáva adaptívne údajov štruktúra, kde neexistuje žiadny pevný limit na tom, koľko prvkov môžete vložiť do nej, pretože ak máte kolízie, to je v poriadku. Len do toho pustite a pripojiť ju ku čo sme videli trochu bol ešte pred známy ako prepojeného zoznamu. Tak poďme pauzu len na chvíľu. Čo je pravdepodobnosť kolízie na prvom mieste? Dobre, možno som premýšľal nad, možno Som na inžinierske tento problém, pretože viete čo? Áno, môžem prísť s ľubovoľnou Príklady z vrcholu mojej hlavy, ako je Allison a Aaron, ale v skutočnosti, vzhľadom k rovnomerné rozloženie vstupy, to je nejaký náhodný vkladanie do dátovej štruktúry, čo je naozaj pravdepodobnosť kolízie? Tak sa ukázalo, že je to vlastne Super vysoká. Dovoľte mi, aby som zovšeobecniť Problém je v tom, ako to. Tak v miestnosti n CS50 študenti, čo je pravdepodobnosť, že aspoň dvaja študenti v miestnosti majú narodeniny v rovnaký deň? Takže to, čo. niekoľko Hund - 200, 300 ľudí tu a niekoľko stoviek ľudí doma dnes. Takže ak ste sa chcel spýtať sami seba, čo je pravdepodobnosť, že dve osoby v tejto miestnosti má narodeniny v rovnaký deň, môžeme to vyriešiť. A tvrdím, v skutočnosti existujú dva ľudia s rovnakým narodeniny. Napríklad, má niekto má dnes narodeniny? Včera? Zajtra? Dobre, takže to vyzerá, budem musieť urobiť 363 alebo tak viac Časy skutočne zistiť, ak máme kolízii. Alebo by sme to mohli urobiť matematicky skôr než zdĺhavo ako to urobiť. A navrhujem nasledovné. Takže navrhujem, že by sme mohli modelovať pravdepodobnosť, že dve osoby, ktoré majú narodeniny v rovnaký deň ako pravdepodobnosť 1 mínus pravdepodobnosť nikto s narodeniny v rovnaký deň. Takže si to, a je to len ozdobný spôsob, ako písať to, pre prvá osoba v izbe, on alebo ona môže mať jeden z možných narodeniny za predpokladu, že 365 dní v roku, s ospravedlnením osobám s 29.února najlepšie. Takže prvý človek v tejto miestnosti je zadarmo mať ľubovoľný počet narodeniny zo 365 možností tak, že budeme to robiť 365 delené 365, čo je jedna. Ďalšia osoba v miestnosti, ak je cieľom je, aby sa zabránilo kolízii, môže len majú jeho životnému jubileu, ako mnoho rôznych možných dní? 364. Takže druhý termín v tomto výraze je v podstate tým, že matematiku pre nás odpočítaním off jeden možný deň. A potom ďalší deň, ďalší deň, Nasledujúci deň sa na celkovom počte ľudí v miestnosti. A keď sme potom zváži, čo potom je pravdepodobnosť, nie každý má Unikátny narodenín, ale opäť mínus 1 to, čo dostaneme, je výrazom ktoré môžu veľmi fancifully vyzerať takto. Ale je to oveľa zaujímavejšie pozrieť sa na vizuálne. Toto je tabuľka, kde na osi x je počet ľudí v miestnosti, počet narodenín. Na osi y je pravdepodobnosť, kolízie, dvaja ľudia majú narodeniny v rovnaký deň. A stánok s jedlom z tejto krivky je že akonáhle sa dostanete do páči 40 študenti, že ste sa na 90% pravdepodobnosťou combinatorically dvoch osoby alebo viac, ktoré majú rovnako najlepší. A akonáhle sa dostanete páči 58 ľuďom, že je to takmer 100% šanca dvoch ľudia v miestnosti sa bude musieť narodeniny v rovnaký deň, aj keď je 365 alebo 366 možných vedierka a Iba 58 ľudí v miestnosti. Len štatisticky budete pravdepodobne sa kolíziám, čo v skratke motivuje túto diskusiu. Že aj keď sa dostaneme fantázie tu, a začať s takýmito reťazami, sme stále bude mať kolízie. Tak to vyvoláva otázku, čo je Náklady robí inserce a delécie do dátovej štruktúry, ako je tento? No dovoľte mi navrhnúť - a nechaj ma ísť späť na obrazovku cez tu - ak sme n prvkami zoznam, takže ak sa snažíme vložiť n prvkov, a máme koľko celkom lopaty? Povedzme, že celkom 31 vedier v prípade narodenín. Aká je maximálna dĺžka jedného z týchto reťazcov potenciálne? Ak opäť tam 31 možné narodeniny v danom mesiaci. A my sme len hrudkujúce všetky - v skutočnosti je to hlúpy príklad. Jdem na 26 miesto. Takže ak skutočne ľudia, ktorých mená začať s A až Z, čím nás 26 možností. A my sme pomocou dátovej štruktúry, ako tá, ktorú sme práve videli, kedy máme pole ukazovateľov, z ktorých každá poukazuje na pripojenom zozname, kde sa Prvý zoznam je každý s názvom Alice. Druhý zoznam je každý s meno začínajúci, počnúc s B, a tak ďalej. To, čo je pravdepodobné, že dĺžka každej z tieto zoznamy keď budeme predpokladať, pekný čistý Rozdelenie mien A až Z v celej dátovej štruktúry? K dispozícii je n ľudí v dátovej štruktúre delené 26, ak sú dobre rozprestreté po celej dátové štruktúry. Takže dĺžka každej z týchto reťazca je n delené 26. Ale vo veľkom notácie, čo to je? Čo je to naozaj? Takže je to naozaj len n, nie? Pretože sme povedal v minulosti, že fuj vydeľte 26. Áno, v skutočnosti je to rýchlejšie. Ale teoreticky, to nie je zásadne všetko rýchlejšie. Tak sme sa nezdajú byť až tak moc bližšie k tomuto Svätého grálu. V skutočnosti, je to len lineárny čas. Sakra, na tomto mieste, tak prečo nie my stačí použiť jeden obrovský komunikačné zoznam? Prečo nie my stačí použiť jeden veľký Pole pre ukladanie názvov všetci v miestnosti? No, je tu ešte niečo, čo presvedčivá tabuľky hash? Je tu ešte niečo, čo presvedčivé o dátovej štruktúre to vyzerá takto? Toto. STUDENT: [nepočuteľné]. SPEAKER 1: Jasne, a znovu keď je to len lineárny algoritmus, a lineárny čas dátová štruktúra, prečo nie ja len ukladať každého názov veľké pole, alebo vo veľkom prepojeného zoznamu? A prestaň robiť UO tak oveľa ťažšie než je potrebné, aby sa? Čo je presvedčivá, hoci aj keď som škriabal von? STUDENT: [nepočuteľné]. SPEAKER 1: Insertions nie sú? Drahé už nie. Takže vložky potenciálne mohli aj naďalej byť konštantný čas, aj keď dáta Štruktúra vyzerá to, rad ukazovatele, z ktorých každý ukazuje na potenciálne spojové zoznamy. Ako by ste mohli dosiahnuť konštantná čas vloženia mená? Držať ju v prednej časti, nie? Ak by sme obetovať cieľ návrhu od skôr, kde sme chceli udržať každého názov, napríklad, triedenie, alebo všetky čísla na scéne radené, Predpokladajme, že máme netriedeného spájať zoznam. To len nás stojí jeden alebo dva kroky, ako v prípade Bena a Brianom skôr, vložiť prvok na na začiatku zoznamu. Takže ak sa nechcete starať o triedení všetky mien začínajúcich alebo všetky mená začínajúce na B, môžeme stále dosiahnuť konštantný čas vloženia. Teraz vzhliadol Alice alebo Bob alebo akýkoľvek názov všeobecne je stále čo? Je to veľký O n delené 26, v ideálny prípad, kedy sú všetci jednotne distribuované, kde je toľko, koľko je pretože sú to Z, čo je pravdepodobne nereálne. Ale to je stále lineárna. Ale tu sa dostávame späť do bodu z asymptotickej notácie bytia teoreticky pravda. Ale v reálnom svete, keď tvrdí, že môj program niečo urobiť 26 krát rýchlejšie než tie, ktorých program, budete radšej používate? S pozdravom a bane, čo je 26 krát rýchlejší? Realisticky, osoba, ktorá je o 26 krát rýchlejšie, aj keď je to teoreticky naše algoritmy spustiť v rovnakom Asymptotická dobe jeho behu. Dovoľte mi navrhnúť iný riešenie vôbec. A ak to nebude fúkať vašu myseľ, sme z dátových štruktúr. Tak to je trie - druh hlúpe meno. Pochádza z rešerší, a slovo sa píše trie, t-r-i-e, pretože Kurz vyhľadávanie znie ako trie. Ale to je história zo slova trie. Takže trie je naozaj nejaký druh stromu, a je to aj hra na dané slovo. A aj keď nemôžete celkom vidieť s touto vizualizáciou, trie je strom štruktúrovaný ako rodokmeni s jeden predok hore a mnoho vnúčat a veľkých vnúčatá ako listy na dne. Ale každý uzol trie je pole. A to je v poli - a poďme zjednodušovať na chvíľu - je to pole, v tomto prípade o veľkosti 26, kde každý uzol je opäť poľa veľkosti 26, kde je v tom, že nultý prvok pole predstavuje, a posledná element v každej takej Pole predstavuje Z. Takže navrhujem teda, že tieto dáta štruktúry, známej ako trie, môže byť použiť aj pre ukladanie slová. Videli sme pred chvíľou, ako by sme mohli uložiť slová, alebo v tomto prípade mena, a my už videli, ako môžeme uložiť čísla, ale ak sa zameriame na názvy alebo reťazca Tu si všimnite, čo je zaujímavé. Tvrdím, že názov je Maxwell v tejto dátovej štruktúry. Kde vidíte Maxwell? STUDENT: [nepočuteľné]. SPEAKER 1: Na ľavej strane. Takže to, čo je zaujímavé, s týmito dátami štruktúra je skôr než obchod so reťazec M-A-X-W-E-L-L lomka nula, všetky súvislý, čo môžete urobiť, namiesto toho je nasledujúci. Pokiaľ sa jedná o trie ako dátové štruktúry, každý ktorého uzloch je opäť pole, a chcete uložiť Maxwell, musíte najprv index, a tak v koreňovom uzle, takže hovoriť, najhornejšia uzol, na umiestnenie M, vpravo, tak zhruba do stredu. A potom odtiaľ, postupujte ukazovateľ na podriadené uzly, aby som tak povedal. Takže v rodokmeni zmysle, budete postupovať smerom nadol. A, ktoré vás dovedú do iného uzla Vľavo, ktorý je len ďalšie polia. A potom, ak chcete uložiť Maxwell, nájdete ukazovateľ, ktorý predstavuje A, čo je toto tu. Potom môžete ísť na ďalšiu uzol. A upozornenie - to je dôvod, prečo je obraz trochu klame - Tento uzol vyzerať Super malý. Ale na pravej strane je Y a Z. Je to len autor skrátený obraz tak, že ste skutočne vidieť veci. Inak tento obrázok by bolo veľmi široké. Takže teraz si index do umiestnenia X, potom W, potom E, potom L, potom L. Tak čo je to zvedavosť? No, ak budeme používať tento druh nový sa o tom, ako ukladať reťazec dátová štruktúra, stále musíte v podstate zaškrtnúť v dátach štruktúra, ktorá slovo tu končí. Inými slovami, každý z týchto uzlov nejako musí pamätať, že sme vlastne nasledoval všetkých týchto ukazovateľov a odchádzajú trochu chlieb omrvinky v spodnej časti tu v tejto Štruktúra pre označenie M-A-X-W-E-L-L v skutočnosti v tejto dátovej štruktúry. Tak by sme mohli postupovať takto. Každý z uzlov v obraze sme len Píla má jeden, poľa veľkosti 27. A to je v súčasnej dobe 27, pretože v p nastaviť šesť, budeme v skutočnosti vám apostrof, takže môžeme mať mená ako O'Reilly a iní s apostrofy. Ale rovnaký nápad. Každý z týchto prvkov v poľa poukazuje na struct uzol, tak len uzol. Tak to je veľmi pripomínajúci nášho prepojeného zoznamu. A potom som si Boolean, ktorý budem zavolajte slovo, ktoré je len bude true, ak slovo končí na to uzol v strome. Je to skutočne predstavuje malý trojuholník sme videli pred chvíľou. Takže ak slovo končí v tomto uzle strom, bude to slovo pole je pravda, ktorý je koncepčne zaškrtnutím alebo sme kreslíte tohto trojuholníka, áno, tam je slovo tu. Tak to je trie. A teraz je otázka, čo je jeho doba chodu? Je to veľký O n? Je to niečo iné? No, ak ste n názvy týchto údajov štruktúra, Maxwell je iba jedným z je, aká je doba chodu vkladanie alebo zistenie Maxwell? Čo je to doba chodu vloženie Maxwell? Ak existuje n iné mená už v tabuľke? Jo? STUDENT: [nepočuteľné]. SPEAKER 1: Jo, je to dĺžka mená, nie? Tak M-a-X-w-e-l-l, takže to je takto algoritmus je veľký O sedem. Teraz, samozrejme, názov majú rôznu dĺžku. Možno je to krátky názov. Možno je to dlhší názov. Ale čo je kľúčové je to, že je to neustály číslo. A možno to naozaj nie je konštantná, Ale Boh, keď realisticky, v slovník, je to asi nejaká hranica, na počte písmen meno osoby v danej krajine. A tak môžeme predpokladať, že hodnota je konštantná. Neviem, čo to je. Je to pravdepodobne väčšie než si myslíme, že je. Pretože tam je vždy nejaký roh puzdro s crazy dlhým názvom. Takže povedzme, že k, ale je to stále konštantný pravdepodobne, pretože každý meno vo svete, aspoň v Najmä krajiny, je to, že dĺžka alebo kratšie, takže je konštantná. Ale keď sme povedali, že je niečo veľké O konštantné hodnoty, čo je to skutočne zodpovedá? To je naozaj to isté ako hovorí konštantný čas. Teraz sme trochu podvádzanie, nie? Sme druh využitia teóriu, tu, aby som povedal, že dobre, aby koeficient sa naozaj iba rádovo jednej, a to je konštantný čas. Ale v skutočnosti je. Vzhľadom k tomu, Kľúčovou myšlienkou je, že ak sme n mená už v tomto dátové štruktúry, a vložíme Maxwell, je množstvo času, ktoré nás zavedie do vložiť Maxwell vôbec postihnuté tým, koľko ďalších ľudí sú v dátovej štruktúre? Nezdá sa, že byť. Keby som mal miliardu viac prvkov tejto trie a vložte Maxwell, je sa vôbec týka? Nie. A to je na rozdiel od niektorého z denných dát štruktúry sme videli doteraz, kedy doba chodu algoritmu je úplne nezávisle na tom, ako moc vec je alebo nie je už v tejto dátovej štruktúry. A tak s tým poskytuje teraz je príležitosť pre p sadu šiestich, ktorá bude opäť zahŕňať realizáciu vlastnej Kontrola pravopisu, čítanie v 150000 slová, ako najlepšie uložiť, že nie je nutne zrejmé. A keď som sa usiloval nájsť Svätý grál, vôbec sa mi nepáči tvrdí, že je trie. V skutočnosti môže byť hašovacia tabuľka veľmi dobre ukáže byť oveľa efektívnejšie. Ale to sú len - to je len jedna z rozhodnutia o návrhu budete musieť urobiť. Ale pri uzatváraní poďme 50 alebo tak sekúnd sa pozrieť na to, čo je pred budúci týždeň a my po prechode z tohto príkazového riadku svete, ak C programy k veciam web založené a jazyky ako PHP a JavaScript a internet sám protokoly ako HTTP, ktorú ste brať za samozrejmosť rokov teraz, a napísal väčšinu každý deň, možno, alebo vidieť. A začneme olúpte vrstvy, čo je internet. A čo je kód, ktorý tvorí základ dnešnej nástroja. Takže 50 sekúnd tohto ukážku tu. Dám vám Bojovníci siete. [PLAYBACK] -Prišiel so správou. S protokolom všetci jeho vlastné. Prišiel na svet krutých firewallov, bezcitný routery a nebezpečenstvo ďaleko horšie ako smrť. Je rýchly. Je silný. Je TCPIP. A má svoju adresu. Bojovníci siete. [END PLAYBACK] SPEAKER 1: To je, ako internet musia pracovať od budúceho týždňa.