SPEAKER 1: Dobře, takže jsme zpátky. Vítejte na CS50. To je konec týdne sedm. Takže připomenout, že minule jsme začali při pohledu na něco propracovanější datové struktury. Vzhledem k tomu, až do teď, jsme měli opravdu máme k dispozici to bylo, pole. Ale dříve, než jsme se zbavit pole tak, že vše zajímavé, což opravdu to ve skutečnosti je, jaké jsou některé z klady tohoto jednoduchého dat struktura tak daleko? Co je to dobrý? Zatím, jak jsme viděli? Co to máš? Nic. STUDENT: [neslyšitelné]. SPEAKER 1: Co je to? STUDENT: [neslyšitelné]. SPEAKER 1: Pevná velikost. OK, tak proč je pevnou velikost dobrý i když? STUDENT: [neslyšitelné]. SPEAKER 1: OK, takže je to efektivní pocit, že můžete přidělovat pevná částka z vesmíru, což snad je přesně tolik, kolik prostor tak, jak chcete. Takže to může být naprosto plus. Co jiného se strana pole? Jo? STUDENT: [neslyšitelné]. SPEAKER 1: All - Cože? STUDENT: [neslyšitelné]. SPEAKER 1: Všechny boxy v paměti nebo vedle sebe. A to je užitečné - proč? To je docela pravda. Ale jak můžeme využít, že pravdu? STUDENT: [neslyšitelné]. SPEAKER 1: Přesně tak, můžeme sledovat kde je vše jen na základě znalosti jednu adresu, a to na adresu první byte tohoto bloku paměti. Nebo v případě, že řetězec, adresa první char v tomto řetězci. A odtud můžeme nalézt konec řetězce. Najdeme zde Druhý prvek, Třetí část, a tak dále. A tak fantastický způsob, jak to popsat je, že pole nám náhodný přístup. Jen pomocí hranatou závorkou zápis a číslo, můžete přeskočit na specifický prvek v poli v konstantním čase, velké O jednoho, abych tak řekl. Ale tam bylo nějaké stinné stránky. Co pole neudělal velmi snadno? Co je to vůbec dobré? STUDENT: [neslyšitelné]. SPEAKER 1: Co je to? STUDENT: [neslyšitelné]. Reproduktor 1: Rozšíření ve velikosti. Takže stinné pole jsou přesně opak toho, co upsides jsou. Takže jedna z nevýhod je že je to pevnou velikost. Takže si můžete opravdu ji pěstovat. Můžete přidělit větší kus paměť, a pak se přesunout staré prvky do nového pole. A pak bez stará pole, pro instance, pomocí malloc nebo podobný funkce je volána realloc, které realokuje paměť. Realloc, jako stranou, se snaží, aby vám paměť, která je vedle pole že již máte. Ale to by se věci pohnuly asi úplně. Ale ve zkratce, je to drahé, ne? Protože pokud máte kus paměti této velikosti, ale opravdu chci této velikosti, a chcete zachovat zachovány původní prvky, budete muset zhruba lineární čas Proces kopírování že je třeba, aby se stalo od staré na nové pole. A realita se ptá provozní systém znovu a znovu a opět velké kusy paměti může začít stát nějaký čas stejně. Takže je to požehnáním i prokletím v zastírat, že tato pole jsou pevné délky. Ale když si představíme něco místo takhle, kterou nazývá propojený seznam, dostaneme několik upsides a několik stinné i zde. Takže spojový seznam je prostě dat struktura tvořena structs C v tomto případ, kdy struct, odvolání, je jen kontejner pro jeden nebo více specifických typy proměnných. V tomto případě, co si datové typy Zdá se, že uvnitř struct, který naposledy jsme nazývaný uzel? Každý z těchto obdélníků je uzel. A každý z menších obdélníků uvnitř ní je datový typ. Jaké typy si říkáme byli v pondělí? Jo? STUDENT: [neslyšitelné]. SPEAKER 1: variabilní a ukazatel nebo Přesněji řečeno, int, pro N, a ukazatel v dolní části. Oba ti stalo, že 32 bitů na alespoň na počítači, jako je tento CS50 Zařízení, a tak jsou tažené stejně ve velikosti. Takže to, co používáte ukazatel když za zjevně? Proč přidat na tuto šipku teď, když pole bylo tak pěkné a čisté a jednoduché? Co dělá ukazatel pro nás v každé z těchto uzlů? STUDENT: [neslyšitelné]. SPEAKER 1: Přesně tak. Je to řekne, kde další je. Tak nějak jsem použít analogii pomocí vlákno nějak nit těchto uzlů dohromady. A to je přesně to, co děláme s ukazatele, protože každý z nich kousky paměti může, ale nemusí být souvislé, zády k sobě k sobě v paměti RAM, protože pokaždé, když se volání malloc řekl, dej mi dost bajtů pro nový uzel, mohlo by to tu, nebo by to mohlo být. Mohlo by to být tady. Mohlo by to být tady. Prostě nevím. Ale s použitím ukazatele na adresy ty uzly, můžete steh je společně tak, že vypadá vizuálně jako seznam, i když tyto věci jsou vše rozprostřené v celém jednom nebo vaše dvě nebo čtyři gigabajty vaše RAM uvnitř vašeho vlastního počítače. Tak nevýhodou, pak, spojový seznam je co? Co je to cena, kterou jsme zřejmě platit? STUDENT: [neslyšitelné]. SPEAKER 1: Více prostoru, ne? My jsme v tomto případě, zdvojnásobil množství prostoru, protože jsme šli z 32 bitů pro každý uzel, pro každou int, takže teď 64 bitů, protože musíme držet kolem ukazatel stejně. Získáte větší účinnost, pokud váš struct je větší než tato jednoduchá věc. Pokud jste skutečně studenta uvnitř z nichž je několik stringů jméno a dům, možná číslo, možná některých dalších oborů dohromady. Takže pokud máte dostatečně velký struct, pak možná cena ukazatel je není tak velký problém. Toto je trochu rohové případu v tom, že jsme ukládání takový jednoduchý primitivní uvnitř propojeného seznamu. Ale jde o to samé. Ty určitě trávit více paměť, ale vy jste stále flexibilita. Protože teď, když chci přidat prvek na začátku tohoto seznamu, Musím přidělit nový uzel. A já mám jen ty aktualizace šipky jaksi jen pohybující několik rad kolem. Pokud chci vložit něco do uprostřed seznamu, nemám na tlačit všechny stranou, jako tomu bylo v minulost týdnů s našimi dobrovolníky, kteří představovala pole. Dovedu si vyhradit nový uzel a pak stačí poukázat na šipky v různé směry, protože to není musí zůstat v aktuální paměť pravda, linka, jako bych vypracovány je to tady na obrazovce. A pak konečně, pokud chcete vložit něco na konec seznamu, je ještě jednodušší. To je trochu libovolného notaci, ale 34 je ukazatel, hádejte. Jaká je hodnota jeho ukazatel nejvíce pravděpodobně vyvodit něco jako starý Škola anténa tam? STUDENT: [neslyšitelné]. SPEAKER 1: Je to asi null. A opravdu to je jedna autora zastoupení null. A to je null, protože jste naprosto Potřebujete vědět, kde je konec spojového seznam, jinak budete mít následující a sledování a po těchto šipek do určité hodnoty odpadky. Takže null bude znamenat, že neexistuje více uzlů napravo od čísla 34, v tomto případě. Takže navrhujeme, že můžeme realizovat tento uzel v kódu. A my jsme viděli tento druh syntaxe před. Typedef jen definuje nový typ nám, nám dává jako synonymum string byl pro char *. V tomto případě to bude, aby nám zkrácený zápis tak, že struct uzel Místo toho můžete být jen zapsat jako uzel, který je mnohem čistší. Je to mnohem méně upovídaný. Uvnitř uzlu je zřejmě int tzv. n, a pak struct node * což znamená, že přesně to, co jsme chtěli šipky znamená, ukazatel na další uzel přesně stejného typu. A já navrhuji, abychom mohli realizovat vyhledávací funkce jako je tento, který v první pohled by se mohlo zdát trochu složitější. Ale podívejme se, že v kontextu. Nech mě jít přes spotřebiče tady. Dovolte mi otevřít soubor s názvem Seznam nulový bod h. A že obsahuje pouze definici my právě viděl před chvílí na tato data typ nazývaný uzel. Takže jsme dali, že do souboru dot hodin. A jak je stranou, i když to program, který se chystáte vidět, je není tak složité, je to ve skutečnosti Konvence při psaní programu dát věci jako datové typy, táhnout konstanty někdy uvnitř vašeho hlavičkový soubor a ne nutně v Váš soubor C, jistě, když si Programy se větší a větší, takže víte, kde hledat a to jak pro dokumentace v některých případech, nebo pro základy, jako je toto, Definice některých typů. Kdybych se tak otevírá seznam nulovou tečku c, všimněte si pár věcí. Obsahuje několik hlavičkové soubory, většina které jsme ještě neviděli. Obsahuje vlastní hlavičkový soubor. A stranou, proč je to dvakrát cituje zde, na rozdíl od úhlu držáky na trati, která Jsem zdůraznil, že? STUDENT: [neslyšitelné]. SPEAKER 1: Jo, tak to je místní soubor. Takže jestli je to místní soubor z vašich vlastních zde na lince 15, například, můžete použít uvozovky místo z šikmých závorkách. Teď je to docela zajímavé. Všimněte si, že jsem prohlásil, globální proměnnou v tomto programu na řádku 18 tzv. první, myšlenka je to bude ukazatel na první uzel v mém propojeného seznamu, a já jsem inicializována, na hodnotu null, protože jsem není přiděleno žádné skutečné uzly jen zatím. Takže to znamená, obrazově, co jsme viděl před chvílí na obrázku jako že ukazatel na daleko levé straně. Takže teď, že ukazatel nemá šipku. Je to místo je jen null. Ale představuje to, co bude adresa první skutečný uzel v tomto seznamu. Tak jsem se provádění je globální protože, jak uvidíte, to vše Program se v životě realizovat spojový seznam pro mě. Teď mám několik prototypů zde. Rozhodl jsem se implementovat funkce, jako je mazání, vkládání, vyhledávání a průchod - poslední být jen pěšky přes seznam, vytištění jeho prvky. A teď je můj hlavní rutina. A nebudeme trávit příliš mnoho času na to, protože to je něco, doufejme starý klobouk nyní. Chystám se udělat následující, zatímco uživatel spolupracuje. Takže jedno, já jdu k tisku z tohoto menu. A já jsem ho formátovat jako čistě, jak jsem mohl. Pokud uživatel zadá v jednom, to znamená, že které chcete odstranit něco. Pokud uživatel zadá ve dvou, to znamená, že které chcete vložit něco. A tak dále. Chystám se poté vás vyzve pak na příkaz. A pak budu používat GetInt. Tak to je opravdu jednoduché menuing interface, kde stačí zadat číslo mapování na jeden z těchto příkazů. A teď mám pěkný čistý vypínač prohlášení, že se to zapnout co uživatel napsal palců A když napsal jeden, já zavolejte odstranit a rozbít. Pokud zadali dva, já zavolejte vložit a zlomit. A teď Povšimněte si, že jsem dal každý z nich na stejném řádku. Je to jen stylistické rozhodnutí. Obvykle jsme viděli něco takhle. Ale já jsem se rozhodl, upřímně řečeno, můj program Podíval čitelnější, protože to bylo jen čtyři případy, na vypsalo to takhle. Zcela legitimní použití stylu. A já budu dělat to tak dlouho, dokud uživatel nezadali nulu, což jsem rozhodl, bude znamenat, že chtějí s kouřením přestat. Takže teď upozornění, co jsem dělat tady. Chystám se uvolnit seznamu zdánlivě. Ale o tom až za chvíli. Pojďme si nejprve tento program spustit. Takže mi dovolte větší terminál okna, tečka lomítko list 0. Chystám se jít dopředu a vložit, psaní dva, jako je číslo 50, a nyní uvidíte seznam je nyní 50. A můj textu jen posouvat se trochu. Takže teď všimnete seznam obsahuje číslo 50. Pojďme udělat další vložku tím, že dva. Pojďme zadejte číslo jako jeden. List je nyní jeden, následuje 50. Takže je to jen textová reprezentace seznamu. A pojďme vložit ještě jedno číslo jako číslo 42, což je snad chystá skončit ve středu, protože Tento program v jednotlivých druhů se prvky, jak to vloží nimi. Takže tady to máme. Super jednoduchý program, který by absolutně použili celou řadu, ale já stalo, že se pomocí propojeného seznamu jen tak mohu dynamicky zvětšit a zmenšit ji. Takže pojďme se podívat pro vyhledávání, když jsem spustit příkaz tři, Chci vyhledávat pro, řekněme, číslem 43.. A nic se zřejmě našel, protože jsem se vrátil žádnou odpověď. Tak jdeme na to znovu. Hledat. Pojďme hledání 50, nebo spíše hledání na 42, což je pěkný Trochu jemnější význam. A já jsem našel smysl života tam. Číslo 42, pokud nevíte, reference, Google jej. Dobrá. Takže to, co tento program pro mě udělal? Je to jen mi dovolil vložit tak daleko a hledání prvků. Pojďme rychle vpřed, pak se že funkce se podíval na v pondělí jako ukázku. Takže tuto funkci, tvrdím, hledá element v seznamu jako první jeden, upozornění uživatele a volání GetInt získat aktuální int které chcete vyhledat. Pak nevšiml. Chystám se vytvořit dočasnou proměnnou v souladu s názvem 188 ukazatel - PTR - mohla zavolat tomu nic. A je to ukazatel na uzel protože jsem řekl, že uzel *. A já inicializace je rovná nejprve tak, že jsem skutečně mít svou prstem, abych tak řekl, na velmi První prvek seznamu. Takže pokud moje pravá ruka je zde PTR jsem ukazuje na stejnou věc, že ​​první ukazuje na. Takže teď zpátky v kódu, co se bude dít dál - je to společný vzor, ​​když iterace přes struktury, jako spojový seznam. Chystám se udělat následující, zatímco ukazatel není rovno null Takže zatímco můj prst neukazuje na nějaké null hodnota, pokud je ukazatel šipka n se rovná n. Jsme si všimnete jako první, že n je to, co Uživatel napsal v přepočtu GetInts zavolat tady. A ukazatel šipka n rozumí co? No, pokud se vrátíme k obrázku zde když mám prst ukazující na že první uzel obsahuje devět, Šipka v podstatě znamená, že jít do uzel a chytit hodnotu při umístění n, V tomto případě jsou data pole s názvem n. Jako stranou - a viděli jsme to ještě před pár týdny, když se někdo zeptal - tato syntaxe je nový, ale to není nám síly, které jsme už nemělo. Co to bylo za výraz ekvivalentní k použití tečka zápis a hvězda pár týdny, když jsme sloupnout tato vrstva trochu předčasně? STUDENT: [neslyšitelné]. SPEAKER 1: Přesně tak, je to hvězda, a pak je to hvězda tečka n, s závorky zde, který vypadá, Upřímně řečeno, myslím, že spousta více tajemné číst. Ale hvězda ukazatel, jako vždy, znamená jít. A jakmile jste tam, jaké údaje Pole chceš přístup? No použít tečka notaci pro přístup struct datové pole, a já konkrétně chcete n. Upřímně řečeno, řekl bych to je prostě těžší číst. Je to těžší si vzpomenout, kde se závorky jdou, hvězda a to všechno. Aby celý svět přijal některé syntaktické cukr, abych tak řekl. Jen sexy způsob, jak říct, To je ekvivalentní, a možná více intuitivní. Je-li ukazatel je skutečně ukazatel, znamená notace šipky jít a najít pole je v tomto případě tzv. n. Takže pokud ji najdu, všimněte si, co dělám. Prostě vytisknout, našel jsem procent ia zapojíte hodnotou pro daný int. Nazval jsem spát po dobu jedné sekundy, jen aby druhu pauzy věcí na obrazovce poskytují uživateli druhé absorbovat co se právě stalo. A pak jsem se zlomit. Jinak, co mám dělat? Aktualizovat ukazatele rovna ukazatel šipku vedle. Tak aby bylo jasno, to znamená jít tam přes můj old-school notace. Takže to znamená jen jít do čehokoliv jste ukázal na, které velmi Prvním případem je, že jsem ukázal na struct s devíti v něm. Tak jsem šel tam. A pak tečka notace znamená, získat hodnotu na další. Ale hodnota, a to i když je čerpány jako úzký, jen číslo. Je to číselná adresa. Takže tento jeden řádek kódu, ať již napsal takhle víc složitější způsobem, nebo jako je to, o něco více intuitivní způsob, prostě znamená pohnout rukou z prvního uzlu na další, a pak další, a potom další, a tak dále. Takže nebudeme bydlet na straně druhé implementace vkládání a mazání a průchod, z nichž první dva které jsou poměrně zapojit. A myslím, že je to docela snadné se dostat ztratil, když dělá to ústně. Ale to, co můžeme udělat, je zde pokusu o stanovení nejlepší udělat to vizuálně. Protože bych navrhoval, že pokud bychom Chci vložit prvky do tohoto Stávající seznam, který má pět základních prvků - 9, 17, 22, 26, a 33 - Kdybych měl jít k provedení tohoto v kód, musím zvážit, jak jít asi dělá. A já bych navrhnout, přičemž dítě kroky přičemž v tomto případě mám na mysli, jaké jsou možných scénářů, které jsme setkat obecně? Při provádění vložka pro propojenou seznam, to je náhodou Konkrétním příkladem velikosti pět. No, pokud chcete vložit číslo, rádi říkají, že číslo jedna, a udržování seřazeny objednávky, kde samozřejmě dělá číslo jedna je třeba jít v tomto konkrétním příkladu? Stejně jako na začátku. Ale co je zajímavé je, že Chcete-li vložit jeden do toho seznam, co potřebuje speciální ukazatel aktualizovat zřejmě? První. Takže bych si dovolil tvrdit, toto je první případ že bychom mohli chtít, aby zvážila, scénář zahrnující vkládání na na začátku seznamu. Pojďme trhat off možná tak jednoduché, nebo dokonce jednodušší případ, relativně vzato. Předpokládejme Chci vložit číslo 35 v seřazeném pořadí. To samozřejmě patří tam. Takže to, co ukazatel zřejmě bude musí být aktualizovány v tomto případě? 34 je ukazatel stále není null ale adresa struct obsahující číslo 35. Tak to je případ dvou. Tak už jsem trochu kvantizace kolik práce musím udělat tady. A konečně zřejmé, prostřední případ opravdu, ve středu, když chci vložit něco jako, řekněme 23, která vede mezi 23 a 26, ale nyní se věci trochu víc podílí protože to, co ukazatele je třeba změnit? 22 tak samozřejmě je třeba změnit protože nemůže odkazovat na 26 už ne. Že je třeba, aby odkazoval na nový uzel, který Budu se muset rozdělit na telefonním čísle malloc nebo jiným ekvivalentním. Ale pak jsem také potřebovat nový uzel, 23 V tomto případě, aby se její ukazatel ukázal na koho? 26. A tam to bude pořadí úkonů zde. Protože když jsem to hloupě a já například od začátku roku seznam, a mým cílem je, vložit 23. A já jsem zkontrolovat, to patří Zde, v blízkosti devíti? Ne. Znamená to sem patří, vedle 17? Ne. Má to sem patří vedle 22? Ano. Teď, když jsem hloupý tady, a ne myslí si, až bych mohl přidělit můj nový uzel pro 23 let. Bych mohl aktualizovat ukazatel z uzel s názvem 22, směřující že na nový uzel. A pak to, co mám aktualizovat Nový uzel je ukazatel, že? STUDENT: [neslyšitelné]. SPEAKER 1: Přesně tak. Ukázal na 26 let. Ale dammit kdybych neměl již aktualizovat 22 je ukazatel ukazovat na toho chlapa, a teď mám sirotky, zbytek seznamu, abych tak řekl. Takže pořadí operací zde bude důležité. K tomu jsem mohl ukrást, řekněme, šest dobrovolníků. A uvidíme, jestli můžeme to udělat vizuálně namísto kódu ručiček. A máme nějaké krásné stres míče pro vás dnes. OK, jak se o jeden, dva, ve zpět - na konci tam. tři, čtyři, oba kluci na konci. A pět, šest. Jistě. Pět a šest. Dobře a my se na vás příště. Dobře, pojď nahoru. Dobře, když už jsi tady poprvé, byste chtěli být tím, kdo nešikovně ve skle Google tady? Dobře, takže OK, sklo, videozáznam. OK, máte dobré jít. Dobře, takže pokud vy můžete přijít tady jsem předem připravené některá čísla. Dobře, pojď sem. A proč nejdeš trochu dále tímto způsobem. A podívejme se, jak se jmenuješ, se skleněným Google? STUDENT: Ben. SPEAKER 1: Ben? OK, Bene, budete první, a to doslova. Takže budeme posílat do konce období. Dobře, a vaše jméno? STUDENT: Jason. SPEAKER 1: Jason, OK budete být číslo devět. Takže pokud budete chtít sledovat Ben tímto způsobem. STUDENT: Jill. SPEAKER 1: Jill, budete mít 17, která, pokud bych to udělal více inteligentně, musel bych začal na druhém konci. Můžete jít tudy. 22. A vy jste? STUDENT: Mary. SPEAKER 1: Mary, budete 22. A vaše jméno? STUDENT: Chris. SPEAKER 1: Chris, budete 26. A pak konečně. STUDENT: Diana. SPEAKER 1: Diana, budete 34. Takže si pojď sem. Dobře, takže perfektní řazeny objednat již. A pojďme dál, a to takže můžeme opravdu - Ben jsi jen trochu hledat ven nikde tam. OK, takže pojďme dál, a líčí to použití zbraně, stejně jako já, přesně, co se děje. Takže jděte do toho a dát sami si noha nebo dva mezi sebou. A jděte do toho a přitom s jednou rukou na ten, kdo byste měli směřovat na na základě tohoto. A pokud jste null jen bod přímo na podlahu. OK, tak dobře. Takže teď máme propojený seznam, a dovolte mi, abych navrhnout, že budu hrát roli PTR, tak jsem se neobtěžoval provádění tohoto okolí. A pak - někdo hloupý konvence - můžete volat to, co chcete - předchůdce ukazatel, pred ukazatel - je to jen přezdívka jsme dali v náš ukázkový kód k mé levé ruce. Na druhé straně, která bude udržovat sledovat, kdo je kdo v následující scénáře. Takže předpokládám, nejprve chci utrhnout pryč , že první příklad vkládání, řekněme 20, do seznamu. Takže budu potřebovat někoho, kdo by ztělesňují číslo 20 pro nás. Tak jsem třeba někoho malloc z publika. Pojď nahoru. Jak se jmenujete? STUDENT: Brian. SPEAKER 1: Brian, v pořádku, takže musí být uzel obsahující 20. Dobře, pojď sem. A samozřejmě, pokud Brian se patří? Tak, ve středu - ve skutečnosti, počkej. Děláme to mimo pořadí. Děláme to mnohem těžší než je třeba, aby se na prvním místě. OK, jdeme na volný Brian a realloc Brian jak pět. OK, tak teď chceme vložit Brian jak pět. Tak pojď sem vedle Ben na chvíli. A můžete říct, pravděpodobně kde tento příběh bude. Ale pojďme pečlivě promyslet, pořadí úkonů. A je to právě tato vizuální že se to seřadí s tímto ukázkový kód. Tak tady jsem PTR ukázal nejprve není na Bena, samo o sobě, ale bez ohledu na cení, že obsahuje, což je v tomto případě je - jak se jmenuje? STUDENT: Jason. SPEAKER 1: Jason, tak jak Ben a já jsme ukázal na Jasona v tomto okamžiku. Takže teď musím zjistit, kde se Brian patří? Takže jediné, co mám přístup k Právě teď je jeho n datová položka. Takže budu kontrolovat, je Brian méně než Jasona? Odpověď je pravda. Tak co teď musí stát, ve správném pořadí? Musím aktualizovat, kolik ukazatelů celkem v tomto příběhu? Kde je moje ruka stále ukazuje na Jason a vaše ruce - chcete-li dát ruku jako, tak nějak jsem nevím, otazník. OK, dobře. Dobře, takže máte několik kandidátů. Buď Ben nebo já nebo Brian nebo Jason nebo všichni ostatní, které ukazatele je třeba změnit? Kolik celkem? OK, tak dva. Můj ukazatel nezáleží už protože jsem jen dočasné. Takže je to tihle dva, pravděpodobně, jak Ben a Brian. Takže mi dovolte navrhnout, abychom aktualizace Ben, protože je to poprvé. První prvek tohoto seznamu se nyní bude Brian. Takže Ben bod na Briana. OK, co teď? Kdo dostane ukázal na koho? STUDENT: [neslyšitelné]. SPEAKER 1: OK, takže Brian má ukázat na Jasona. Ale už jsem ztratil přehled o tomto ukazatel? Vím, kde je Jason? STUDENT: [neslyšitelné]. SPEAKER 1: já, protože jsem dočasný ukazatel. A pravděpodobně jsem se nezměnil ukázat na nový uzel. Takže můžeme jednoduše Brian bod na toho, kdo mi ukázal na. A jsme hotovi. Tak jeden případ, ve vložení na začátku seznamu. Tam byly dva hlavní kroky. Za prvé, musíme aktualizovat Bena, a pak musíme rovněž aktualizovat Briana. A pak nemám obtěžovat traipsing přes zbytek seznam, protože jsme již našli jeho umístění, protože patřil k vlevo od prvního prvku. Dobře, takže docela jednoduché. Ve skutečnosti, pocit, že jsme skoro takže to příliš složité. Takže pojďme se utrhnout z konce seznamu, a zjistit, kde složitost začíná. Takže když teď jsem alloc z publika. Každý, kdo chce hrát 55? Tak jo, viděl jsem svou ruku jako první. Pojď nahoru. Jo. Jak se jmenujete? STUDENT: [neslyšitelné]. SPEAKER 1: Habata. OK, pojď nahoru. Budete mít číslo 55. Takže vy, samozřejmě, patří na konci seznamu. Takže pojďme přehrát simulaci se mnou bytí PTR jen na chvíli. Tak jsem poprvé bude ukazovat na bez ohledu na to Ben ukázal na. Oba jsme ukazuje nyní na Briana. Takže 55 je ne méně než pět. Takže budu aktualizovat tím, že jsem ukázal na další ukazatel Brianovi, který Nyní je samozřejmě Jasona. 55 je menší než devět, takže Chystám se aktualizovat PTR. Chystám se aktualizovat PTR. Chystám se aktualizovat PTR Budu aktualizovat PTR. A já jdu - hmm, co je Vaše jméno znovu? STUDENT: Diana. SPEAKER 1: Diana ukazuje, samozřejmě, při nulovém s levou rukou. Takže tam, kde se skutečně Habata patří jasně? Na levé straně, zde. Tak jak mám vědět, že ji zde Myslím, že jsem to podělal. Protože to, co je umění PTR tento okamžik v čase? Null. Takže i když vizuálně, můžeme samozřejmě vidět všechny z nich kluci tady na jevišti. Já jsem to sledoval z předchozí osoba v seznamu. Nemám prst ukazující ven, V tomto případě, uzel číslo 34. Takže pojďme skutečně začít to znovu. Takže teď vlastně nepotřebujete Druhý lokální proměnná. A to je to, co uvidíte v Skutečný vzorek C kód, kde, jak jsem jít, když jsem aktualizovat pravou ruku k bodu Jason, přičemž je nutno Brian zezadu, jsem lepší začít používat levou ruku k aktualizovat, kde jsem byl, takže, jak jsem jít pomocí tohoto seznamu - více rozpačitě, než jsem chtěl teď tady vizuálně - Chystám se dostat do konec seznamu. Tato ruka je stále nulový, což je docela zbytečné, pouze ukazují Jsem jednoznačně na konci seznamu, ale teď aspoň to mám předchůdce ukazovatel tady, tak Co teď předává a jaké ukazatele musí aktualizovat? Čí ruka chceš překonfigurovat první? STUDENT: [neslyšitelné]. SPEAKER 1: OK, tak Dianin. Kam chcete nasměrovat Dianin levý ukazatel na? Na 55, pravděpodobně, aby jsme tam vložit. A kde by 55 ukazatel jít? Dolů, což null. A moje ruce, v tomto bodě, ne jedno, protože oni byli jen dočasné proměnné. Takže teď jsme hotovi. Takže další složitosti tam - a že to není tak těžké zavést, ale potřebujeme sekundární proměnnou, aby se jistý, že předtím, než jsem se pohnout právo ruka, jsem aktualizovat hodnotu mé levici ruka, pred ukazatel v tomto případě, tak že mám koncové ukazatele sledovat, kde jsem byl. Nyní, jak stranou, pokud si myslíte tohle přes to pocit, že je to Trochu nepříjemné mít na sledování tohoto levé ruky. Co by jiné řešení tohoto problému byly? Pokud jste se dostali k redesign data Struktura mluvíme až teď? Pokud je to jen trochu cítí trochu nepříjemné mít ráda, dva ukazatele prochází seznam, kdo by mohl jinak se, v ideálním světě, udržovány Informace, které potřebujete? Jo? STUDENT: [neslyšitelné]. SPEAKER 1: Přesně tak. Pravá takže je to vlastně zajímavý zárodek nápadu. A tato myšlenka na předchozí ukazatel, ukazuje na předchozí prvek. Co když jsem ztělesněný, že v seznamu sám? A to bude těžké si představit, to bez všech papíru pádu na zem. Ale předpokládejme, že tito lidé používají jak jejich rukou mít předchozí ukazatel, a další ukazatel, čímž realizuje to, co budeme říkat dvakrát spojový seznam. To by mi dovolte, abych nějak vzad mnohem snadněji, aniž by mě, programátor, musela držet sledovat ručně - skutečně ručně - , kde jsem byl předtím v seznamu. Takže nebudeme dělat. Budeme držet to jednoduchý, protože to je přijde za cenu, což je dvakrát mnoho prostoru pro ukazatele, chcete-li druhou. Ale to je opravdu společný datové struktury známé jako dvojnásobně spojový seznam. Pojďme udělat poslední příklad zde a dal tihle kluci z jejich utrpení. Tak malloc 20. Pojď nahoru od uličky tam. Dobře, Jak se jmenujete? STUDENT: [neslyšitelné]. SPEAKER 1: Je nám líto? STUDENT: [neslyšitelné]. SPEAKER 1: Demeron? OK pojď nahoru. Ty musí být 20. Ty samozřejmě budou Patří mezi 17 a 22. Takže dovolte mi učit mé lekci. Chystám se začít ukazatel ukázal na Briana. A já budu mít levou ruku aktualizovat pouze k Brianovi, jak jsem se přesunout na Jason, kontrola dělá 20 méně než devět? Ne. Je o 20 méně než 17? Ne. Je o 20 méně než 22? Ano. Takže to, co ukazovátka nebo ruce je třeba změnit kde to ukazuje teď? Takže, co můžeme udělat 17 ukazuje na 20 let. Tak to je v pořádku. Kde chceme upozornit ukazatel myši teď? Ve 22. A my víme, kde 22 je opět díky k mému dočasné ukazatele. Tak to je v pořádku tam. Takže kvůli této dočasné skladování Nechal jsem sledovat, kde se všichni. A teď můžete jít do vizuálně, kde patříte, a teď potřebujeme 1, 2, 3, 4, 5, 6, 7, 8, 9 stres míče, a potlesk pro tihle kluci, kdybychom mohli. Dobrá práce. [APPLAUSE] SPEAKER 1: Dobře. A můžete držet kusy papíru jako památku. Dobře, takže, věřte mi, je to hodně jednodušší projít, aby se lidé, než je tomu u skutečného kódu. Ale to, co najdete za chvíli teď, je to stejné - ach, děkuji. Děkuji - je, že zjistíte, že stejné údaje struktura, spojový seznam, může ve skutečnosti být použity jako stavební blok k ještě sofistikované datové struktury. A uvědomit si taky téma zde je, že jsme absolutně představil více složitost do provádění tohoto algoritmu. Vložení, a když jsme šli přes to, výmaz a vyhledávání, je trochu komplikovanější, než se byl s řadou. Ale získat nějaké dynamiku. Dostáváme adaptivní strukturu dat. Ale opět platíme cenu, že některé další složitost, a to jak v provádění. A my jsme se vzdali náhodný přístup. A abych byl upřímný, že to není nějaký pěkný čištění snímek můžu dát, že říká, že je zde důvod, proč spojový seznam je lepší než pole. A nechat to tak. Protože téma znovu objevuje nyní, i více v nadcházejících týdnech, je že to nemusí být nutně správná odpověď. To je důvod, proč máme samostatnou osu designu pro základní problémové okruhy. Bude to velmi kontextová zda chcete tato data použít struktura nebo že jeden, a to bude závisí na to, co je pro vás z hlediska zdrojů a složitosti. Ale dovolte mi navrhnout, aby byla ideální údajů struktura, Svatý grál, bude něco, co je konstantní čas bez ohledu na to, kolik věcí je uvnitř, nebylo by úžasné, kdyby datová struktura se vrátil v odpovědi konstantní čas. Ano. Toto slovo je v obrovské slovníku. Nebo ne, to slovo není. Nebo nějaký takový problém. No uvidíme, jestli můžeme alespoň ne krok směrem k tomuto. Dovolte mi navrhnout novou datovou strukturu, která mohou být použity pro různé věci, v tomto případě nazývá hash tabulky. A tak jsme vlastně zpět pohledem na poli, v tomto případě, a trochu uměle, já jsem to vypracovány hash tabulky jako pole s druhem dvourozměrné pole - nebo spíše to zde zobrazen jako dva rozměrné pole - ale je to jen pole o velikosti 26, tak, že pokud se zavolejte pole, stolní držák nula je obdélník v horní části. Stolní držák 25 je obdélník v dolní části. A to je, jak bych mohl nakreslit dat struktura, ve které chci uložit Jména lidí. Tak například, a nebudu kreslit Celá věc tady na stropě, když jsem měl toto pole, které jsem teď bude volání hash tabulky, a to je opět umístění nula. Tohle je místo jeden, a tak dále. Tvrdím, že chci použít tato data struktura, v zájmu diskuse Uložení jmen lidí, Alice a Bob a Charlie a další podobné názvy. Takže myslíte, že o tom dnes stejně jako začátky , řekněme, ve slovníku se spoustou slov. Oni stalo, že se jména v našem příkladu zde. A to je příliš germane, snad, aby provádí kontrolu pravopisu, jako my Mohou to být problém nastavit šest. Takže pokud máme řadu celkové velikosti 26 tak, že je to místo 25. na dně, a tvrdím, že je Alice první slovo ve slovníku Názvy, které chci vložit do paměti RAM, do tohoto datové struktury, kde jsou instinkt říká, že Alice je Název by měl jít v tomto poli? Máme 26 možností. Pokud chceme ji? Chceme ji v závorce nula, ne? A pro Alici, řekněme, že nula. A B bude jeden, a C budou dva. Takže budeme psát Alicin jméno tady. Pokud se poté vložte Bob, jeho název půjde zde. Charlie naleznete zde. A tak dále dolů Tato datová struktura. Je to nádherná struktura dat. Proč? No to je doba chodu vložením lidského jméno do tohoto struktura dat právě teď? Vzhledem k tomu, že tato tabulka je implementována, opravdu jako pole. No, je to konstantní čas. To je cílem jednoho. Proč? Tak, jak si zjistit, kde Alice patří? Když se podíváte na které písmeno jejího jména? První. A můžete se tam dostat, když je to řetězec, jen o pohledu na provázku držák nula. Takže nultý znak řetězce. To je jednoduché. To jsme udělali v crypto přiřazení týdny. A pak ještě jednou víte, že Alice písmeno velké, můžeme odečíst off 65 nebo kapitálu je sám, že nám dává nulu. Takže nyní víme, že Alice patří v místě nulové. A vzhledem k tomu ukazatel k těmto údajům struktura, nějakého druhu, jak dlouho trvá to se mi najít místo nula v poli? Jen jeden krok, že je to konstantní čas protože s libovolným přístupem se Navrhovaný byl charakterizován pole. Takže ve zkratce, zjišťuje, co index Alice je název, který je v V tomto případě je, nebo ať to prostě řešit že k nule, kde B je jedna a C je dva, zjišťuje, že z je konstantní čas. Musím se podívat na její první dopis, přijít na to, kde je nula Pole je také konstantní čas. Takže technicky to jako dva kroky nyní. Ale to je stále konstantní. Takže říkáme, že velký O jedné, takže jsme vložena Alici do této tabulky v konstantní čas. Ale samozřejmě, já jsem byl naivní, ne? Co když tam Aaron ve třídě? Nebo Alicia? Nebo jakékoliv jiné názvy začínající A. Kam jdeme dát že člověk, ne? Myslím, že právě teď je tu jen tři Lidé na stole, takže možná jsme měli dát Aaron v místě nula jedna dva tři. Jasně, mohl jsem tady. Ale pak, když se snažíme vložit do Davida tento seznam, kde se David jít? Nyní náš systém spustí vypínací dolů, ne? Protože teď David skončí tady pokud Aaron je ve skutečnosti zde. A tak se celá tahle představa, že čistá datová struktura, která nám dává konstantním čase vložky již není konstantní čas, protože musím zjistit, oh, sakra, někdo to již v místě Alice. Dovolte mi, abych prozkoumat zbytek těchto údajů struktura, hledat místo dát někdo jako jméno Aaron. A tak to taky začíná aby se lineární čas. Navíc, pokud se chcete vyhledat Aaron v této datové struktuře, a zkontrolovat, a Áronova jméno tu není. V ideálním případě by jste právě řekl Aronovi není v datové struktuře. Ale pokud si začnete dělat prostor pro Aaron tam, kde by byly D nebo E, ty, v nejhorším případě, je nutné zkontrolovat Celá struktura dat, ve takovém případě přejde do něčeho lineární ve velikosti tabulky. Takže v pořádku, já to opravit. Problém je, že jsem měl 26 prvků v tomto poli. Dovolte mi, abych ji změnit. Jejda. Dovolte mi, abych ho změnit tak, že místo bytí velikost 26 celkem, všimněte si na dno index se změní na n mínus jedna. Pokud 26 je zjevně příliš malá pro člověka " jména, protože tam jsou tisíce jména na světě, prostě dělat na 100 nebo 1000 nebo 10000. Řekněme přidělit mnohem více prostoru. Dobře, že nemusí nutně snížit pravděpodobnost, že nebudeme mít dva lidé s názvy začínající a tak jsi to zkusit dát jména na umístění nulu stále. Pořád bude srazí, což znamená, že stále potřebujeme řešení, aby Alice a Árona a Alicia a další Jména začínající A jinde. Ale jak velký problém to je? Co je to pravděpodobnost, že si mají kolize v datovém Struktura takhle? No, dovolte mi, abych - vrátíme se na tuto otázku zde. A podívejte se na to, jak bychom mohli řešit jako první. Dovolte mi, abych vytáhnout tento návrh zde. To, co jsme právě popsal, je algoritmus, heuristický tzv. lineární snímání, kdy, pokud jste se pokusili vložit něco, co zde v těchto údajů struktura, která se nazývá hash tabulky, a neexistuje žádný prostor tam, skutečně zkoumat strukturu dat kontrola, je to k dispozici? Je to k dispozici, je to k dispozici? Je to k dispozici? A když konečně je vložíte jméno, které jste původně zamýšlel jinde v tomto místě. Ale v nejhorším případě pouze bod může být velmi spodní údajů struktura, velmi konec pole. Takže lineární sondy, v nejhorším případě, přejde do lineární algoritmus, kde Aaron, když se stane být vložen poslední v této datové struktuře, mohl by kolidovat s tímto prvním místě, ale pak konec smůla v samém závěru. Takže to není konstantní Doba svatý grál pro nás. Tento přístup, vkládání prvků do datová struktura nazývá hash tabulka se nezdá být konstantní čas alespoň ne v obecném případě. To může přejít do něčeho lineární. Takže co kdybychom vyřešit kolize poněkud jinak? Tak tady je to složitější přiblížit to, co je ještě tzv. hash tabulky. A hash, jako stranou, co Mám na mysli, je index, který Jsem se zmínil dříve. Chcete-li něco hash může být myšlenka jako slovesa. Takže pokud hash Alice je jméno, hašovací funkce, abych tak řekl, by měla vrátit číslo. V tomto případě je nula, pokud se patří na umístění nula, jedna, pokud se patří na polohy na jedné, a tak dále. Takže moje hashovací funkce bylo dosud Super jednoduché, jen při pohledu na První písmeno v něčí jméno. Ale hašovací funkce bere jako vstup některých údaj, string, int, cokoliv. A to vyplivne typicky číslo. A to číslo je, že data, kdy element patří do datové struktury známý zde jako tabulky hash. Tak jen intuitivně, to je mírně odlišný kontext. Toto vlastně odkazuje na příklad zahrnující narozeniny, kde zde může být tolik, kolik 31 dnů v měsíci. Ale co se to člověk rozhodnout, dělat v případě nehody? Kontext teď být, ne kolizi jména, ale kolize narozenin, když se dva lidé mají narozeniny ve stejný den na 2. října, například. STUDENT: [neslyšitelné]. Reproduktor 1: Jo, tak tady máme využití propojených seznamů. Takže to vypadá trochu jinak než jsme nakreslil dříve. Ale zdá se, že na pole na levé straně. To je jeden index, a to bez zvláštní důvod. Ale je to pořád pole. Je to pole ukazatelů. A každý z těchto prvků, z nichž každý z Tyto kruhy nebo lomítka - slash představuje null - každá z těchto ukazatele se zřejmě ukazuje na co datová struktura? Spojový seznam. Takže teď máme schopnost pevný kód do našeho programu velikost tabulky. V tomto případě víme, že nikdy více než 31 dnů v měsíci. Tak těžké kódování hodnoty, jako je 31 rozumné v tomto kontextu. V souvislosti s názvy, pevný kódování 26 není od věci, že lidé to pouze názvy začínají, například, abeceda zapojení do Z. Můžeme se nacpat je všechny do těchto údajů struktura tak dlouho, jak když jsme si kolize, nemáme dát jména zde, namísto toho, že z těchto buněk ne jako řetězce samotné, ale ukazatele na, například, Alice. A pak Alice může mít jiný ukazatel na jiný název začíná A. A Bob se vlastně děje tady. A pokud je tu další jméno začínající pomocí B, on skončí tady. A tak každý z prvků tohoto stolní dva, když jsme navrhli tento trochu víc chytře - no - když jsme navrhli to trochu víc chytře, se nyní stává adaptivní údajů struktura, kde neexistuje žádný pevný limit na tom, kolik prvků můžete vložit do ní, protože pokud máte kolize, to je v pořádku. Jen do toho pusťte a připojit ji ke co jsme viděli trochu byl ještě před známý jako propojeného seznamu. Tak pojďme pauzu jen na chvíli. Co je pravděpodobnost kolize na prvním místě? Dobře, možná jsem přemýšlel nad, možná Jsem na inženýrské tento problém, protože víte co? Ano, mohu přijít s libovolnou Příklady z vrcholu mé hlavy, jako je Allison a Aaron, ale ve skutečnosti, vzhledem k rovnoměrné rozložení vstupy, to je nějaký náhodný vkládání do datové struktury, co je opravdu pravděpodobnost kolize? Tak se ukázalo, že je to vlastně Super vysoká. Dovolte mi, abych zobecnit Problém je v tom, jak to. Takže v místnosti n CS50 studenti, co je pravděpodobnost, že alespoň dva studenti v místnosti mají narozeniny ve stejný den? Takže to, co. několik Hund - 200, 300 lidí tady a několik set lidí doma dnes. Takže pokud jste se chtěl zeptat sami sebe, co je pravděpodobnost dvou lidí v této místnosti má narozeniny ve stejný den, můžeme přijít na to. A tvrdím, ve skutečnosti existují dva lidé se stejným narozeniny. Například, má někdo má dnes narozeniny? Včera? Zítra? Dobře, takže to vypadá, budu muset udělat 363 nebo tak více Časy skutečně zjistit, pokud máme kolizi. Nebo bychom to mohli udělat matematicky spíše než zdlouhavě jak to udělat. A navrhuji následující. Takže navrhuji, abychom mohli modelovat pravděpodobnost, že dvě osoby, které mají narozeniny ve stejný den jako pravděpodobnost 1 minus pravděpodobnost nikdo s stejně nejlepší. Takže si to, a to je jen ozdobný způsob, jak psát to, pro první osoba v pokoji, on nebo ona může mít jeden z možných narozeniny za předpokladu, že 365 dnů v roce, s omluvou osobám s 29.února narozeniny. Takže první člověk v této místnosti je zdarma mít libovolný počet narozeniny ze 365 možností tak, že budeme to dělat 365 děleno 365, což je jedna. Další osoba v místnosti, v případě, že cílem je, aby se zabránilo kolizi, může jen mají jeho životnímu jubileu, jak mnoho různých možných dní? 364. Takže druhý termín v tomto výrazu je v podstatě tím, že matematiku pro nás odečtením off jeden možný den. A pak další den, další den, Následující den se na celkovém počtu lidí v místnosti. A když jsme pak zváží, co pak je pravděpodobnost, ne každý má Unikátní narozenin, ale opět mínus 1 to, co dostaneme, je výrazem které mohou velmi fancifully vypadat takto. Ale je to mnohem zajímavější podívat se na vizuálně. Toto je tabulka, kde na ose x je počet lidí v místnosti, počet narozenin. Na ose y je pravděpodobnost, kolize, dva lidé mají narozeniny ve stejný den. A stánek s jídlem z této křivky je že jakmile se dostanete do líbí 40 studenti, že jste se na 90% pravděpodobností combinatorically dvou osoby nebo více, které mají narozeniny ve stejný den. A jakmile se dostanete líbí 58 lidem, že je to téměř 100% šance dvou lidé v místnosti se bude muset narozeniny ve stejný den, i když je 365 nebo 366 možných kbelíky a Pouze 58 lidí v místnosti. Jen statisticky budete pravděpodobně se kolizím, což ve zkratce motivuje tuto diskusi. Že i když se dostaneme fantazie tady, a začít s těmito řetězy, jsme stále bude mít kolize. Tak to vyvolává otázku, co je Náklady dělá inserce a delece do datové struktury, jako je tento? Tak mi dovolte navrhnout, - a nech mě jít zpět na obrazovku přes zde - pokud jsme n prvky seznam, takže pokud se snažíme vložit n prvků, a máme kolik celkem lopaty? Řekněme, že celkem 31 věder v případě narozenin. Jaká je maximální délka jednoho z těchto řetězců potenciálně? Pokud opět tam 31 možné narozeniny v daném měsíci. A my jsme jen hrudkující všechny - ve skutečnosti, že je to hloupý příklad. Jdem na 26 místo. Takže pokud skutečně lidé, jejichž jména začít s A až Z, čímž nás 26 možností. A my jsme pomocí datové struktury, jako ten jsme právě viděli, čímž máme pole ukazatelů, z nichž každá poukazuje na připojeném seznamu, kde se První seznam je každý s názvem Alice. Druhý seznam je každý s jméno začínající, počínaje s B, a tak dále. To, co je pravděpodobné, že délka každé z tyto seznamy když budeme předpokládat, pěkný čistý Rozdělení jmen A až Z v celé datové struktury? K dispozici je n lidí v datové struktuře děleno 26, pokud jsou dobře rozprostřeny po celé datové struktury. Takže délka každé z těchto řetězce je n děleno 26. Ale ve velkém notace, co to je? Co je to doopravdy? Takže je to opravdu jen n, ne? Protože jsme řekli v minulosti, že fuj vydělte 26. Ano, ve skutečnosti je to rychlejší. Ale teoreticky, to není zásadně všechno rychleji. Tak jsme se nezdají být až tak moc blíže k tomuto svatého grálu. V podstatě je to jen lineární dobu. Sakra, na tomto místě, tak proč ne my stačí použít jeden obrovský spojový seznam? Proč ne my stačí použít jeden velký Pole pro ukládání názvů všichni v místnosti? No, je tu ještě něco, co přesvědčivá tabulky hash? Je tu ještě něco, co přesvědčivé o datové struktuře to vypadá takhle? Toto. STUDENT: [neslyšitelné]. SPEAKER 1: Jasně, a znovu když je to jen lineární algoritmus, a lineární čas datová struktura, proč ne já jen ukládat každého název velké pole, nebo ve velkém propojeného seznamu? A přestaň dělat UO tak mnohem těžší než je třeba, aby se? Co je přesvědčivá, byť i když jsem škrábal ven? STUDENT: [neslyšitelné]. SPEAKER 1: Insertions nejsou? Drahé už ne. Takže vložky potenciálně mohli i nadále být konstantní čas, i když data Struktura vypadá to, řadu ukazatele, z nichž každý ukazuje na potenciálně spojové seznamy. Jak byste mohli dosáhnout konstantní čas vložení jména? Držet ji v přední části, ne? Pokud bychom obětovat cíl návrhu od dříve, kde jsme chtěli udržet každého název, například, třídění, nebo všechna čísla na scéně řazeny, Předpokládejme, že máme netříděného spojový seznam. To jen nás stojí jeden nebo dva kroky, jako v případě Bena a Brianem dříve, vložit prvek na na začátku seznamu. Takže pokud se nechcete starat o třídění všechny jmen začínajících nebo všechny jména začínající na B, můžeme stále dosáhnout konstantní čas vložení. Nyní vzhlédl Alice nebo Bob nebo jakýkoli název obecně je stále co? Je to velký O n děleno 26, v ideální případ, kdy jsou všichni jednotně distribuovány, kde je tolik, kolik je protože jsou to Z, což je pravděpodobně nereálné. Ale to je stále lineární. Ale tady jsme se vrátit k bodu z asymptotické notace bytí teoreticky pravda. Ale v reálném světě, když tvrdí, že můj program něco udělat 26 krát rychleji než ty, jejichž program, budete raději používáte? S pozdravem a dolu, což je 26 krát rychlejší? Realisticky, osoba, která je o 26 krát rychlejší, i když je to teoreticky naše algoritmy spustit ve stejném asymptotická době jeho běhu. Dovolte mi navrhnout jiný řešení vůbec. A pokud to nebude foukat vaši mysl, jsme z datových struktur. Tak to je trie - druh hloupé jméno. Pochází z rešerší, a slovo se píše trie, t-r-i-e, protože Kurz vyhledávání zní jako trie. Ale to je historie na slovo trie. Takže trie je opravdu nějaký druh stromu, a je to také hra na dané slovo. A i když nemůžete docela vidět s touto vizualizací, trie je strom strukturován jako rodokmenu s jeden předek nahoře a mnoho vnoučat a velkých vnoučata jako listy na dně. Ale každý uzel trie je pole. A to je v poli - a pojďme zjednodušovat na chvíli - je to pole, v tomto případě o velikosti 26, kde každý uzel je opět pole o velikosti 26, kde je v tom, že nultý prvek pole představuje, a poslední element v každé takové Pole představuje Z. Takže navrhuji tedy, aby tato data struktury, známé jako trie, může být použít i pro ukládání slova. Viděli jsme před chvílí, jak bychom mohli uložit slova, nebo v tomto případě jména, a my již viděli, jak můžeme uložit čísla, ale pokud se zaměříme na názvy nebo řetězce Zde si všimněte, co je zajímavé. Tvrdím, že název je Maxwell v této datové struktury. Kde vidíte Maxwell? STUDENT: [neslyšitelné]. SPEAKER 1: Na levé straně. Takže to, co je zajímavé, s těmito daty struktura je spíše než obchod se řetězec M-A-X-W-E-L-L lomítko nula, všechny souvislý, co můžete udělat, místo toho je následující. Pokud se jedná o trie jako datové struktury, každý jehož uzlech je opět pole, a chcete uložit Maxwell, musíte nejprve index, a tak v kořenovém uzlu, takže mluvit, nejhořejší uzel, na umístění M, vpravo, tak zhruba do středu. A pak odtud, postupujte ukazatel na podřízené uzly, abych tak řekl. Takže v rodokmenu smyslu, budete postupovat směrem dolů. A, které vás dovedou do jiného uzlu Vlevo, který je jen další pole. A pak, pokud chcete uložit Maxwell, najdete ukazatel, který představuje A, což je toto zde. Pak můžete jít na další uzel. A upozornění - to je důvod, proč je obraz trochu klame - Tento uzel vypadat Super malý. Ale na pravé straně je Y a Z. Je to jen autor zkrácen obraz tak, že jste skutečně vidět věci. Jinak tento obrázek by bylo velmi široké. Takže teď si index do umístění X, pak W, pak E, pak L, pak L. Tak co je to zvědavost? No, pokud budeme používat tento druh nový se o tom, jak ukládat řetězec datová struktura, stále musíte v podstatě zaškrtnout v datech struktura, která slovo zde končí. Jinými slovy, každý z těchto uzlů nějak musí pamatovat, že jsme vlastně následoval všech těchto ukazatelů a odcházejí trochu chléb drobky ve spodní části zde v této Struktura pro označení M-A-X-W-E-L-L ve skutečnosti v této datové struktury. Tak bychom mohli postupovat takto. Každý z uzlů v obraze jsme jen Pila má jeden, pole o velikosti 27. A to je v současné době 27, protože v p nastavit šest, budeme ve skutečnosti vám apostrof, takže můžeme mít jména jako O'Reilly a jiní s apostrofy. Ale stejný nápad. Každý z těchto prvků v pole poukazuje na struct uzel, tak jen uzel. Tak to je velmi připomínající našeho propojeného seznamu. A pak jsem si Boolean, který budu zavolejte slovo, které je jen bude true, pokud slovo končí na to uzel ve stromu. Je to skutečně představuje malý trojúhelník jsme viděli před chvílí. Takže pokud slovo končí v tomto uzlu strom, bude to slovo pole je pravda, který je koncepčně zaškrtnutím nebo jsme kreslíte tohoto trojúhelníku, ano, tam je slovo zde. Tak to je trie. A teď je otázka, co je jeho doba chodu? Je to velký O n? Je to něco jiného? No, pokud jste n názvy těchto údajů struktura, Maxwell je pouze jedním z je, jaká je doba chodu vkládání nebo zjištění Maxwell? Co je to doba chodu vložení Maxwell? Pokud existuje n jiná jména již v tabulce? Jo? STUDENT: [neslyšitelné]. SPEAKER 1: Jo, je to délka jména, ne? Tak M-a-x-w-e-l-l, takže to je takto algoritmus je velký O sedm. Nyní, samozřejmě, název mají různou délku. Možná je to krátký název. Třeba je to delší jména. Ale co je klíčové je to, že je to neustálý číslo. A možná to opravdu není konstantní, Ale Bůh, když realisticky, v slovník, je to asi nějaká hranice, Na počtem písmen ve jméno osoby v dané zemi. A tak můžeme předpokládat, že hodnota je konstantní. Nevím, co to je. Je to pravděpodobně větší než si myslíme, že je. Protože tam je vždy nějaký roh pouzdro s crazy dlouhým názvem. Takže řekněme, že k, ale je to stále konstantní pravděpodobně, protože každý jméno ve světě, alespoň v Zejména země, je to, že délka nebo kratší, takže je konstantní. Ale když jsme řekli, že je něco velké O konstantní hodnoty, co je to skutečně odpovídá? To je opravdu to samé jak říká konstantní čas. Teď jsme trochu podvádění, ne? Jsme druh využití teorii, zde říci, že dobře, aby součinitele je opravdu jen řádově jedné, a to je konstantní čas. Ale ve skutečnosti je. Vzhledem k tomu, Klíčovou myšlenkou je, že pokud jsme n jména již v tomto datové struktury, a vložíme Maxwell, je množství času, které nás zavede do vložit Maxwell vůbec postižené tím, kolik dalších lidí jsou v datové struktuře? Nezdá se, že být. Kdybych měl miliardu více prvků této trie a vložte Maxwell, je se vůbec týká? Ne. A to je na rozdíl od některého z denních dat struktury jsme viděli doposud, kdy doba chodu algoritmu je zcela nezávisle na tom, jak moc věc je nebo není již v této datové struktury. A tak s tím poskytuje nyní je příležitost pro p sadu šesti, která bude opět zahrnovat realizaci vlastní Kontrola pravopisu, čtení v 150000 slova, jak nejlépe uložit, že není nutně zřejmé. A když jsem usiloval, aby si Svatý grál, vůbec se mi nelíbí tvrdí, že je trie. Ve skutečnosti může být hašovací tabulka velmi dobře ukáže být mnohem efektivnější. Ale to jsou jen - to je jen jedna z rozhodnutí o návrhu budete muset udělat. Ale při uzavírání pojďme 50 nebo tak sekund se podívat na to, co je před příští týden a my po přechodu z tohoto příkazového řádku světě, pokud C programy k věcem web založené a jazyky jako PHP a JavaScript a internet sám, protokoly jako HTTP, kterou jste brát za samozřejmost let teď, a napsal většinu každý den, možná, nebo vidět. A začneme oloupejte vrstvy, co je internet. A co je kód, který tvoří základ dnešní nástroje. Takže 50 sekund tohoto ukázku zde. Dám vám Bojovníci sítě. [PŘEHRÁVÁNÍ] -Přišel se zprávou. S protokolem všichni jeho vlastní. Přišel na svět krutých firewallů, bezcitný routery a nebezpečí daleko horší než smrt. Je rychlý. Je silný. Je TCPIP. A má svou adresu. Válečníci sítě. [END PŘEHRÁVÁNÍ] SPEAKER 1: To je, jak internet musí pracovat od příštího týdne.