[Powered by Google Translate] [6. týždeň, pokračovanie] [David J. Malan] [Harvard University] [To je CS50.] [CS50.TV] To je CS50, a to je koniec 6. týždni. Takže CS50x, jeden z prvých kurzov Harvardu zapojených do EDX iniciatívy skutočne debutoval tento rok v pondelok. Ak by ste chceli, aby si pohľad na to, čo iní na internete sú teraz po spolu s, môžete vyraziť do x.cs50.net. To vás presmeruje na príslušné miesto na edx.org, ktorý bol kde tento a ďalšie kurzy z MIT a Berkeley teraz žijú. Budete sa musieť zaregistrovať k účtu, zistíte, že materiál je veľmi rovnaký ako ste mali tento semester, aj keď niekoľko oneskorené týždňov, ako sme si všetko pripravené. Ale to, čo študenti v CS50x teraz môžete vidieť, je rozhranie úplne, ako je tento. Tento, napríklad, je Zamyla vedie návod k problému sady 0. Po prihlásení do edx.org, CS50x Študent vidí rad vecí by ste očakávať, že v kurze: prednášku pre pondelok, prednáška na stredu, rôzne šortky, problém súpravy, je priechody, PDF. Okrem toho, ako tu vidíte, strojové preklady anglických prepisov do čínština, japončina, španielčina, taliančina, a celá partia ďalších jazykov, ktoré budú určite nedokonalá ako sme ich zaviesť programovo pomocou tzv API, alebo rozhranie pre programovanie aplikácií, od Google ktoré nám umožňuje previesť z angličtiny do týchto iných jazykov. Ale vďaka nádhernej duchu niekoľko sto-plus dobrovoľníkov, Náhodní ľudia na internete, ktorí sa láskavo ponúkol, aby sa zapojili v rámci tohto projektu, budeme postupne zlepšovať kvalitu týchto prekladov tým, že ľudia napraviť chyby, ktoré naše počítače vykonali. 

Tak to dopadá sme niekoľko ďalších študentov ukázať v pondelok, ako sme pôvodne očakávali. V skutočnosti, teraz CS50x má 100.000 ľudí po doma. Takže uvedomíte, že ste to všetko je súčasťou tejto otváracej trieda robiť tento kurz v informatike vzdelávanie všeobecne, viac široko, prístupné. A realita je teraz, s niektorými z týchto masívnych online kurzov, všetci začnú s týmito veľmi vysokých čísel, ako sa zdá, urobili tu. Ale cieľom, nakoniec, pre CS50x je naozaj dostať toľko ľudí na cieľovú čiaru ako je to možné. Podľa návrhu, CS50x sa bude ponúknutá z tejto minulosti pondelok celú cestu cez 15 apríl 2013, tak, že ľudia, ktorí majú školské povinnosti inde, práca, rodina, iné konflikty a podobne, majú trochu väčšiu flexibilitu s ktorými sa ponoriť do tohto kurzu, ktorý, stačí povedať, je pomerne ambiciózne robiť, keď len v priebehu iba troch mesiacov počas obvyklého semestra. Ale títo študenti budú riešiť rovnaký problém sady, prezeranie rovnaký obsah, majú prístup k rovnakým šortky a ako. Takže si uvedomiť, že sme všetci naozaj v tom spoločne. A jeden z koncových cieľov CS50x nie je len dostať toľko ľudí na cieľovej čiare a dať im túto novo nájdenú chápanie informatiky a programovanie, ale aj nechať túto zdieľanú skúsenosť. Jedným z určujúcich charakteristík 50 na akademickej pôde, dúfame, bol tento druh komunálneho skúseností, pre lepšie alebo pre horšie, niekedy, ale s títo ľudia obrátiť na vľavo a vpravo, a úradné hodiny a hackathon a spravodlivé. Je to trochu ťažšie k tomu, že osobne s ľudí on-line, ale CS50x skončí v apríli historicky prvej CS50 Expo, ktorý bude on-line adaptácia našej predstave o veľtrhu kde budú tieto tisíce študentov všetci vyzvaní na predloženie 1 - až 2-minútového videoklipu, buď screencast ich konečného projektu alebo videa z nich mával ahoj a hovorí o svojich projektoch a demoing to, rovnako ako zoznam predchodcov tu na akademickej pôde na veľtrhu, tak, že semester konca, je nádej, mať globálny výstavu z konečných CS50x študentov projektov, rovnako ako ten, ktorý na vás čaká tento rok v decembri tu na akademickej pôde. Takže o tom viac v nadchádzajúcich mesiacoch. 

S 100.000 študentov však prichádza aj potreba niekoľkých ďalších autorít. Vzhľadom k tomu, že chlapci sú horiace stopu tu a užívať CS50 niekoľko týždňov vopred, tento materiál je vydanie na ľudí na EDX, uvedomiť, radi by sme zapojiť čo najviac našich vlastných študentov, ako je to možné v tejto iniciatíve, ako v priebehu semestra aj tohto zime a tento rok na jar. Takže ak by ste chceli, aby sa zapojili do CS50x, najmä spojenie v na CS50x diskutovať, verzii EDX z CS50 diskutovať, ktoré mnohí z vás používa na akademickej pôde, on-line bulletin board, vykonajte hlavu k tejto adrese URL, dajte nám vedieť, kto ste, pretože by sme radi vybudovať tím študentov a zamestnancov fakulty a podobne na akademickej pôde, ktorí sú jednoducho hrať spolu a pomáhať. A keď vidí otázku, ktorá je oboznámení, počujete študenta nehlási nejaké chyby niekde tam v nejakej krajine na internete, a že krúžky zvonu, pretože ste príliš mal ten rovnaký problém v d-haly pred časom, dúfajme, že potom môžete přizvukovat a podeľte sa o svoje vlastné skúsenosti. Takže prosím, podieľať sa, ak chcete. 

Kurzy Počítačové vedy na Harvarde majú trochu tradície, CS50 medzi nimi, mať nejaké oblečenie, niektoré oblečenie, ktoré môžete nosiť hrdo na semester konci, hovorí celkom hrdo, že ste skončil CS50 a vzal CS50 a podobne, a vždy sa snažíme zapojiť študentov v tomto procese, ako je to možné, pričom pozývame, V tejto dobe semestra, študenti predkladať návrhy pomocou Photoshopu, alebo čokoľvek nástroj výberu by ste chceli použiť ak ste dizajnér, aby predložila návrhy na tričká a mikiny a slnečníky a malé šatky pre psov máme a podobne. A všetko je potom - víťazi každý rok sú potom vystavené na ihrisku internetových stránkach store.cs50.net. Všetko je predávaný za cenu tam, ale na internetových stránkach jednoducho beží sám a umožňuje ľuďom si vybrať farby a vzory, ktoré sa im páčia. Tak som myslel, že sme sa práve podeliť o minuloročných návrhov ktoré boli na internetových stránkach okrem tento tu, čo je každoročné tradíciou. "Každý deň som Seg Faultn" bol jeden z príspevkov v minulom roku, ktorý je stále k dispozícii tam pre absolventov. Mali sme tento, "CS50, so sídlom 1989." Jeden z našich Bowdeny, Rob, bol veľmi populárny v minulom roku. "Tím Bowden" sa narodil, bol tento dizajn predložený, medzi top predajcov. Ako bola táto tu. Mnoho ľudí v tej "Bowden Fever" podľa predajných protokolov. Uvedomte si, že teraz môže byť váš návrh je, a to až na internete. Ďalšie podrobnosti o tomto v ďalší problém nastaví prísť. 

Jeden z ďalších nástrojov: si mal nejaký prejav a dúfajme, že teraz niektoré hands-on skúsenosti s GDB, ktorý je, samozrejme, debugger a umožňuje manipulovať váš program na pomerne nízkej úrovni, robiť to, čo druhy vecí? Čo GDB nechať urobiť? Jo? Daj mi niečo. [Študent odpoveď, nezrozumiteľným] Dobre. Krok do funkcie, takže to nie je len musieť zadať spustiť a mať program ranu cez plnom rozsahu, tlač na veci, na štandardný výstup. Skôr, môžete krokovať ju riadok po riadku, a to buď zadaním ďalšie ísť riadok po riadku po riadku alebo krok sa ponoriť do funkcie, obvykle ten, ktorý si napísal. Čo iného to GDB nechať urobiť? Jo? [Študent odpoveď, nezrozumiteľným] Tlač premenných. Takže ak chcete urobiť trochu sebapozorovania vnútri programu aby bolo nutné uchýliť sa k písaniu printf vyhlásenie všade možne, stačí vytlačiť premennú alebo zobraziť premenné. Čo ešte môžete urobiť s debuggerom ako GDB? [Študent odpoveď, nezrozumiteľným] Presne tak. Môžete nastaviť zarážky, môžete povedať prerušenie výkonu na hlavnú funkciu alebo funkciu foo. Môžete povedať, že prerušenie výkonu na riadku 123. A zarážky sú naozaj účinný spôsob pretože ak máte všeobecný pocit o tom, kde váš problém Pravdepodobne je, nemusíte strácať čas prechádzaním programu rozsahu. Môžete v podstate skočiť priamo tam a potom začať písať - krokovanie to s krokom alebo ďalšie alebo podobne. Ale úlovok s niečím, ako je GDB je, že to pomôže, človek, nájsť svoje problémy a nájsť svoje chyby. To nemusí nutne nájsť im tak veľa pre teba. 

Takže sme zaviedli druhý deň style50, ktorý je krátky príkaz čiara , Ktorý sa snaží štylizovať váš kód trochu čistejšie, než vy, môže človek mať hotovo. Ale aj to je naozaj len estetickú záležitosť. Ale ukázalo sa, že je to ďalší nástroj s názvom Valgrind, že je trochu viac nejobskurnější na použitie. Jeho výstup je ukrutne mystický na prvý pohľad. Ale je to nádherne užitočné, zvlášť teraz, keď sme u tej časti funkčného obdobia kde začínate používať malloc a dynamického prideľovania pamäte. Veci môžu ísť naozaj, ale naozaj zle rýchlo. Pretože ak ste zabudli uvoľniť pamäť, alebo dereferencia nejaký ukazovateľ NULL, alebo dereferencia nejaké odpadky ukazovateľ, čo je zvyčajne príznakom, že výsledky? Seg poruchu. A dostanete tento základný súbor určitého počtu kilobajtov alebo megabajty , Ktorý predstavuje stav vášho programu do pamäte, keď havaroval, ale váš program nakoniec seg chyby, Segmentation fault, čo znamená, že sa niečo zlé stalo takmer vždy súvisí na pamäti súvisiace chyby, ktoré ste urobili niekde. Takže Valgrind vám pomôže nájsť veci, ako je táto. Je to nástroj, ktorý môžete spustiť ako GDB, potom, čo ste zostavil svoj program, ale skôr ako spustiť program priamo, spustiť Valgrind a odovzdáte jej svoj program, rovnako ako vy s GDB. Teraz, použitie, aby ste získali najlepší druh výstupu, je trochu dlhý, takže tam na vrchole obrazovky uvidíte Valgrind-V. "-V" takmer všeobecne rozumie výrečnosť, keď používate programy na počítači so systémom Linux. Takže to znamená, vypľuť viac dát, ako ste mohli v predvolenom nastavení. "- Únik kontrola = plná." To je len hovorí kontrolu všetkých možných únikov pamäte, chyby, ktoré som mohol nekoná. To je tiež obyčajný vzor s linuxovými programami. Všeobecne platí, že ak máte príkazového riadku argument, že je to "switch", že to má zmeniť správanie programu, a to jedno písmeno, to-v, ale ak to je zapnutý, len tým, že konštrukciu programátora, je na celé slovo alebo rad slov, argument príkazového riadku začína -. To sú len ľudské konvencie, ale budete vidieť stále. A potom, nakoniec, "a.out" je ľubovoľný názov pre program v tomto konkrétnom prípade. A tu je niekoľko zástupca výstup. 

Než sa pozrieme na to, čo by to mohlo znamenať, nechaj ma ísť sa k úryvok kódu sem. A dovoľte mi prejsť to z cesty, čoskoro, a poďme sa pozrieť na memory.c, čo je tento krátky príklad. Takže v tomto programe, dovoľte mi, aby som sa zamerať na funkcie a otázky. Máme funkciu hlavnej, ktorá volá funkciu, f, a potom to, čo sa f pokračovať robiť, mierne technické angličtiny? Čo f pokračovať robiť? Ako asi začnem s linkou 20, a na hviezdy zaradenie nezáleží, ale ja budem len v súlade tu s poslednej prednáške. Čo je to riadok 20 sa pre nás? Na ľavej strane. Budeme vyraziť ďalej. Int * x: čo to robí? Dobre. Je to prehlasuje ukazovateľ, a teraz poďme ešte technická. Čo to znamená, veľmi konkrétne, vyhlásiť ukazovateľ? Niekto iný? Jo? [Študent odpoveď, nezrozumiteľné] Príliš ďaleko. Takže čítate na pravej strane rovná sa. Zamerajme sa len na ľavej strane, len na int * x. To "vyhlásil" ukazovateľ, ale teraz poďme ponoriť hlbšie do tejto definície. Čo to konkrétne, technicky znamená? Jo? [Študent odpoveď, nezrozumiteľným] Dobre. Je to príprava na jednu adresu uložiť do pamäte. Dobre. A poďme ešte o krok ďalej, je to deklarovaní premennej, x, to je 32 bitov. A ja viem, že je to 32 bitov, pretože -? Nie je to preto, že je to int, pretože je to ukazovateľ v tomto prípade. Náhoda, že je to jedno a to isté s int, ale skutočnosť, že je hviezda, že znamená, že tento je ukazovateľ a v zariadení, ako s mnohými počítačov, ale nie všetky, ukazovatele sú 32 bitov. Na viac moderný hardvér, ako najnovšie Macy, najnovšie počítačov, môžete mať 64-bit ukazovatele, ale v zariadení, tieto veci sú 32 bitov. Takže budeme štandardizovať na tom. Konkrétnejšie, príbeh znie takto: My "vyhlásil" ukazovateľ, čo to znamená? Pripravíme pre uloženie adresu pamäte. Čo to znamená? My vytvoríme premennú s názvom X, ktorý zaberá 32 bitov že bude čoskoro uložiť adresu integer. A to je asi asi tak presné, ako sa môžeme dostať. To je v poriadku dopredu zjednodušiť svet a len povedať, deklarovať ukazovateľ s názvom x. Declare ukazovateľ, ale uvedomiť si a pochopiť, čo sa vlastne deje dokonca v niekoľkých tých niekoľkých znakov. 

Teraz, toto je skoro niečo jednoduchšie, aj keď je to dlhší výraz. Takže to, čo je to robí, že je zvýraznený teraz: "malloc (10 * sizeof (int));" Jo? [Študent odpoveď, nezrozumiteľným] Dobre. A ja si to tam. Je to pridelenie kus pamäte pre desať celých čísel. A teraz poďme ponoriť do mierne hlbšie, je to pridelenie kus pamäte pre desať celých čísel. Čo je malloc potom sa vracať? Adresa tohto bloku, alebo, viac konkrétne, adresa prvého bajtu tohto bloku. Ako potom som, programátor, vedieť, kde to kus pamäte koncoch? Ja viem, že je to súvislá. Malloc, podľa definície, vám súvislý kus pamäte. Žiadne medzery v ňom. Máte prístup ku všetkým bytu v tomto bloku, chrbtom k sebe k sebe, ale ako to mám vedieť, kde na konci tohto bloku pamäte je? Pri použití malloc? [Študent odpoveď, nezrozumiteľné] Good. Vy nie. Musíte si uvedomiť,. Musím si uvedomiť, že som použil hodnotu 10, a nemám ani Zdá sa, že urobiť to tu. Ale povinnosť je úplne na mňa. Strlen, ktoré sme sa mierne závislé na pre slučke, funguje len preto, že tohto dohovoru, že bude \ 0 alebo tento špeciálny znak NUL, NUL, na konci reťazca. To však neplatí pre len ľubovoľné kúsky pamäti. Je to len na vás. Takže riadku 20, potom prideľuje kus pamäte že je možné uložiť desať celé čísla, a to uloží adresu prvého bajtu tohto kusu pamäti v premennej nazvanej x. Ergo, čo je ukazovateľom. Takže riadku 21, bohužiaľ, bola to chyba. Ale najprv, čo to robí? Je to hovorí obchod v mieste 10, 0 indexované, z bloku pamäte zvanej x hodnota 0. 

Takže si všimnúť pár vecí sa deje. Aj keď x je ukazovateľ, prevezme od pred pár týždňami že môžete aj naďalej používať pole-štýle hranatá zátvorka notáciu. Vzhľadom k tomu, že je to vlastne krátky-ruka zápis pre viac tajomné vyzerajúce ukazovateľ aritmetiky. kde by sme urobiť niečo takéto: Take adresu x, presuňte 10 miest po, potom tam na čokoľvek adresa je uložená na tomto mieste. Ale úprimne povedané, to je len otrasné čítať a zoznámiť sa tak s Takže svet sa zvyčajne používa hranaté zátvorky len preto, že je to oveľa viac človeka-friendly čítať. Ale to je to, čo sa naozaj deje pod kapotou; x je adresa, nie pole, samo o sebe. Tak to je ukladanie 0 na mieste 10 v x. Prečo je to zlé? Jo? [Študent odpoveď, nezrozumiteľné] Presne tak. Máme len pridelené desať Ints, ale počítame od 0 pri programovaní v C, takže máte prístup k 0 1 2 3 4 5 6 7 8 9, ale nie 10. Takže buď program bude seg vinou alebo to nie je. Ale my naozaj nevieme, to je niečo ako nedeterministického správanie. To naozaj záleží na tom, či budeme mať šťastie. Ak sa ukáže, že operačný systém nevadí, keď budem používať, že ďalší bajt, aj keď to nie je, rovnako mi to, možno môj program nespadne. Je to surové, je to buggy, ale možno nie je vidieť, že príznak, alebo môžete vidieť len raz za čas. Skutočnosť je však taká, že chyba je v skutočnosti, tam. A je to naozaj problematické, ak ste napísali program, ktorý chcete byť správne, že ste predal program, ktorý ľudia používajú, že každý raz za čas spadne pretože, samozrejme, to nie je dobrá. V skutočnosti, ak máte telefón so systémom Android alebo iPhone a sťahovať aplikácie v týchto dňoch, ak ste niekedy mali app ukončiť, naraz zmizne, je to takmer vždy dôsledkom nejakej pamäti otázkach súvisiacich, kedy programátor posral a dereferenced ukazovateľ že on alebo ona by nemala mať, a výsledok iOS alebo Android, je len tak zabiť program úplne skôr než riskovať nedefinovanej správanie alebo nejaký druh zabezpečenia kompromisu. 

Je tu ešte jedna chyba v tomto programe okrem tohto jedného. Čo iného som podelal v tomto programe? Ešte som cvičil, čo som kázal. Jo? [Študent odpoveď, nezrozumiteľné] Good. Som nebola uvoľnená pamäť. Takže pravidlo teraz musí byť kedykoľvek budete volať malloc, musíte volať zadarmo, keď ste hotoví použitie tejto pamäte. Teraz by keď chcem uvoľniť túto pamäť? Pravdepodobne, za predpokladu, že tento prvý riadok bol správny, chcel by som to robiť tu. Pretože som nemohla, napríklad, to tu. Prečo? Len mimo rozsah. Takže aj keď hovoríme o ukazovatele, To je týždeň 2 alebo 3 vydanie, kde x je len v rozsahu vnútornej strane zložených zátvorkách, kde bolo deklarované. Takže si rozhodne nemôžete uvoľniť ju tam. Moja jediná šanca, ako oslobodiť je zhruba po riadku 21. Jedná sa o pomerne jednoduchý program, to bolo celkom jednoduché, akonáhle tak nejako zabalené svoju myseľ okolo, čo program robí, kde chyby boli. A aj keď ste to nevidel na prvý, dúfajme, že to je trochu jasné hneď že tieto chyby sú celkom ľahko vyriešiť a ľahko vykonávať. Ale keď program je viac ako 12 liniek dlho, je to 50 riadkov dlhý, 100 riadkov dlhý, pešia cez riadky kódu, premýšľaní toho logicky, je možné, ale nijako zvlášť zábavné robiť, neustále hľadá chyby, a je to tiež ťažké robiť, a to je dôvod, prečo nástroj ako Valgrind existuje. Nechaj ma ísť ďalej a to: dovoľte mi, aby som otvorím okno terminálu, a nenechaj ma stačí spustiť pamäť, pretože pamäť sa zdá byť v poriadku. Začínam mať šťastie. Prechod na tejto dodatočnej byte na konci poľa nezdá byť príliš problematické. Ale dovoľte mi, aby som napriek tomu, urobiť zdravý rozum kontrolu, ktorá sa práve znamená pre kontrolu či alebo nie toto je vlastne správne. 

Tak poďme urobiť Valgrind-V - leak-check = full, a potom názov programu v tomto prípade je pamäť, nie je a.out. Tak nechaj ma ísť ďalej a robiť to. Stlačte Enter. Vážení Boh. To je jeho výkon, a to je to, čo som spomenul skôr. Ale, ak sa naučíte čítať cez všetky nezmysly tu, väčšina z toho je len diagnostických výstup, že to nie je tak zaujímavé. Aký je váš oko naozaj chce, že sa pozerá, je akákoľvek zmienka o chybe alebo neplatné. Slová, ktoré naznačujú problémy. A skutočne, pozrieme sa, čo sa deje zle tu. Mám prehľad o akési ", v použití na výjazde:. 40 bytov v 1 blokov" Nie som si istý, čo blok je ešte, ale 40 bytov skutočne cíti, že by som mohol prísť na to, kde to prichádza z 40 bytov. Prečo sú 40 bytov v použití na výjazde? A konkrétne, ak budeme prechádzať sem, Preto som definitívne stratil 40 bajtov? Jo? [Študent odpoveď, nezrozumiteľné] Perfect. Jo, presne tak. Tam bolo desať celé čísla, a každý z nich je veľkosť 4, alebo 32 bitov, takže som stratil presne 40 bajtov, pretože, ako ste navrhoval, som nevolal zadarmo. To je jedna chyba, a teraz sa poďme pozrieť dole trochu ďalej a vidieť vedľa tohto, "Neplatný písať veľkosti 4". Teraz, čo je to? Táto adresa je vyjadrené to, čo základný zápis, zrejme? To je hexadecimálny, a kedykoľvek uvidíte číslo začínajúce 0x, to znamená hexadecimálne, ktoré sme už v roku, myslím, oddielu PSet 0 zo otázok, ktorý bol len urobiť zahrievacie cvičenia, prevod desiatkovej na hexadecimálne do binárnej a tak ďalej. Hexadecimálne, len ľudskú konvencií, je zvyčajne používaný reprezentovať ukazovatele alebo, všeobecnejšie, rieši. Je to len konvencie, pretože je to trochu jednoduchšie čítať, je to trochu kompaktnejšie, než niečo ako desiatkové, a binárne je k ničomu pre väčšinu ľudí používať. Takže teraz, čo to znamená? No, to vyzerá, že je neplatný zápis o veľkosti 4 na riadku 21 v memory.c. Takže sa vráťme k riadku 21, a naozaj, je to, že neplatný zápis. Takže Valgrind nebude úplne ma držal za ruku a povedz mi, čo je oprava, ale to je zistenie, že robím neplatný zápis. Ja dotýkať 4 bajty, že by som nemal byť, a zrejme to preto, že, ako ste zdôraznil, robím [10] namiesto [9] maximálne alebo [0] alebo niečo medzi tým. S Valgrind uvedomiť, kedykoľvek budete teraz písanie programu ktorý používa ukazovatele a využíva pamäť, a malloc konkrétnejšie, určite si do zvyku beží tak dlho ale veľmi ľahko kopírovať a vložiť velenie Valgrind vidieť, či je nejaké chyby tam. A bude to ohromujúci zakaždým, keď vidíte výstup, ale len analyzovať prostredníctvom vizuálne všetok výstup a uvidíme, či vidíte zmieni chýb alebo varovanie alebo neplatný alebo strate. Akékoľvek slovo, ktoré znie, ako ste vy podelal niekde. Takže si uvedomiť, že je to nový nástroj v toolkit. 

Teraz v pondelok, sme mali veľa ľudí prísť sem a predstavujú pojem prepojeného zoznamu. A sme predstavili prepojený zoznam ako riešenie toho, čo problém? Jo? [Študent odpoveď, nezrozumiteľné] Good. Pole nemôže mať pamäť a pribudli k nim. Ak pridelíte pole o veľkosti 10, to je všetko, čo dostanete. Môžete volať funkcie ako realloc, ak ste pôvodne volal malloc, a že môže pokúsiť pestovať pole v prípade, že je priestor na jeho konci že nikto iný používa, a ak nie, bude to len ti nájsť väčší kus niekde inde. Ale potom to bude kopírovať všetky tie bajtov do nového poľa. To znie ako veľmi správne riešenie. Prečo je to neatraktívne? Myslím, že funguje, ľudia tento problém vyriešil. Prečo musíme vyriešiť to v pondelok s lineárnymi zoznamy? Jo? [Študent odpoveď, nezrozumiteľné] To by mohlo trvať dlho. V skutočnosti, zakaždým, keď voláte malloc alebo realloc alebo calloc, čo je ešte ďalší, kedykoľvek, program, hovorí do operačného systému, Máte tendenciu spomaľovať program. A ak robíte tieto druhy vecí slučiek, ste naozaj spomaľuje veci nadol. Nebudete si všimnúť to pre najjednoduchšie "Hello World" programy typu, ale v oveľa väčších programov, požiadal operačný systém znovu a znovu pre pamäte alebo to, že ho znova a znova nebýva dobrá vec. Plus, je to len trochu intelektuálne - je to úplná strata času. Prečo prideliť viac a viac pamäte, riziko kopírovanie všetko do nového poľa, Ak máte alternatívu, ktorá vám umožní prideliť len toľko pamäte, ako budete skutočne potrebovať? Takže je tu plusy a mínusy v tu. Jeden z plusy teraz je, že máme dynamiku. Nezáleží na tom, kde sa kusy pamäti je, že sú zadarmo, Môžem len trochu vytvoriť tieto strúhanky cez ukazovatele na reťazec celú svoju spájať zoznam spoločne. Ja ale aspoň jednu cenu. 

Čo mám dať do získavania prepojených zoznamov? Jo? [Študent odpoveď, nezrozumiteľné] Good. Potrebujete viac pamäte. Teraz som potrebné priestor pre tieto ukazovatele, a v prípade, že tento super jednoduchý prepojenom zoznamu , Ktorý je len pokusu o uložení celočíselné hodnoty, ktoré sú 4 byty, sme stále hovoríš dobre, ukazovateľ je 4 bajty, takže teraz som doslova zdvojnásobil množstvo pamäte som potreboval uložiť tento zoznam. Ale znova, to je konštanta kompromis v informatike medzi časom a priestorom a vývoj, úsilia a iných zdrojov. Čo je ďalšia nevýhoda použitia prepojeného zoznamu? Jo? [Študent odpoveď, nezrozumiteľným] Dobre. Nie je to tak ľahký prístup. Môžeme už využiť týždeň 0 zásady ako rozdeľuj a panuj. A konkrétne, binárne vyhľadávanie. Vzhľadom k tomu, aj keď my ľudia vidieť hrubo kde uprostred tohto zoznamu je, počítač iba vie, že to súvisí Zoznam začína na adrese volal ako prvý. A to je 0x123 alebo niečo také. A jediný spôsob, ako môže program nájsť strednú prvok je skutočne hľadať celý zoznam. A aj potom, doslova sa musí snažiť nájsť celý zoznam, pretože dokonca akonáhle sa dostanete na strednej prvok podľa nasledujúcich ukazovateľov, vy, program, nemám potuchy, ako dlho tento zoznam je, prípadne, kým nenarazíte na koniec toho, a ako viete, programovo že ste na konci prepojeného zoznamu? Je tu špeciálna NULL pointer, takže opäť, konvencie. Skôr než používať tento ukazovateľ, my rozhodne nechceme, aby to bolo nejaké smeti hodnota smerujúce z pódia niekam, chceme, aby to bolo rúk dole, NULL, tak, že máme túto terminus v tejto dátovej štruktúre, takže vieme, kde končí. 

Čo keď budeme chcieť manipulovať toto? Robili sme väčšinu z tejto vizuálne, a s ľuďmi, ale čo keď chceme urobiť vkladanie? Takže pôvodný zoznam bol 9, 17, 20, 22, 29, 34. Čo keď sme potom chceli malloc priestoru pre číslo 55, uzol pre to, a potom chceme vložiť 55 do zoznamu, rovnako ako sme to urobili v pondelok? Ako to urobíme? No, Anita prišiel a ona v podstate išla zoznam. Začala na prvý prvok, potom ďalší, ďalší, ďalší, ďalší, ďalší. Nakoniec zasiahla ľavý celú cestu dole a uvedomil si, oh, to je NULL. Takže to, čo ukazovateľ manipulácie je potrebné urobiť? Osoba, ktorá bola na konci, číslo 34, treba jeho ľavá ruka zvýšená poukázať na 55, 55 potreba ich ľavú ruku smerom dole, že je nový NULL zakončenie. Hotovo. Celkom ľahko vložiť 55 do triedeného zoznamu. A ako by to mohlo vyzerať? 

Nechaj ma ísť napred a otvoriť nejaké príklad kódu tu. Otvorím sa gedit, a dovoľte mi, aby som otvoriť dva súbory ako prvý. Jedným z nich je list1.h, a dovoľte mi pripomenúť, že to bol kus kódu že sme použili pre reprezentáciu uzla. Uzol má oba int s názvom n a ukazovateľ s názvom ďalší, že len poukazuje na ďalšie veci v zozname. To je teraz v súbore. H.. Prečo? Tam je to konvencie, a my sme nevyužili tejto obrovské množstvo sami, ale ten, kto písal printf a ďalšie funkcie dal ako darček k svetu všetky tieto funkcie písomne ​​súbor s názvom stdio.h. A potom je tu string.h, a potom je tu map.h, a tam je všetky tieto h súbory ktoré ste mohli vidieť alebo používa počas doby napísali inými ľuďmi. Typicky v tých. H súbory sú len veci, ako typedefs alebo vyhlásenie užívateľských typov, alebo vyhlásenie konštánt. Nemusíte dať implementácia funkcie "v hlavičkových súboroch. Tie, že miesto, len ich prototypy. Môžete dať veci, ktoré chcete zdieľať s celým svetom, čo potrebujú na zostavovanie kódu. Takže len sa dostať do tohto zvyku, sme sa rozhodli urobiť to isté. Nie je toho veľa, v list1.h, ale my sme dali niečo, čo by vás mohlo zaujímať ľuďom vo svete ktorí chcú využiť náš spájať zoznam implementáciu. Teraz, v list1.c, nešiel by som celú túto vec pretože je to trochu dlhý, tento program, ale poďme spustiť ju v reálnom rýchlo na riadku. Dovoľte mi, aby som zostaviť Hárok1, dovoľte mi, aby som potom spustiť Hárok1, a to, čo uvidíte je máme simulované jednoduchý malý program tu , Čo sa deje, aby mi k pridávanie a odoberanie čísel do zoznamu. Tak nechaj ma ísť napred a zadajte 3 pre 3 položku menu. Chcem vložiť číslo - poďme urobiť prvé číslo, ktoré bolo 9, a teraz som povedal, že zoznam je teraz 9. Nechaj ma ísť ďalej a urobiť ďalšie vkladanie, takže som narazila menu 3. Aké číslo si chcem vložiť? 17. Enter. A ja urobím len jeden. Dovoľte mi, aby som vložiť číslo 22. Takže máme začiatky prepojeného zoznamu, ktorý sme mali v prezentácii formou pred chvíľou. Ako je táto vloženie vlastne deje? Vskutku, 22 je teraz na konci zoznamu. Takže príbeh sme si povedali na pódiu v pondelok a zhrňme teraz musí byť skutočne deje v kóde. Poďme sa pozrieť. Dovoľte mi, aby som posunúť nadol v tomto súbore. Budeme zakrývať niektoré z funkcií, ale pôjdeme dole, povedzme, vložka funkcie. 

Poďme sa pozrieť, ako ísť o vloženie nového uzla do tohto prepojeného zoznamu. Ak je zoznam vyhlásil? Dobre, poďme posunúť celú cestu až na vrchol, a všimnite si, že moja spájať zoznam je v podstate deklarovaný ako jediný ukazovateľ, ktorý je pôvodne NULL. Takže som pomocou globálne premenné, ktorá sem všeobecne sme hlásali proti pretože to robí váš kód trochu chaotický zachovať, je to trochu lenivý, zvyčajne, ale to nie je lenivý, a to nie je nič zlého, a to nie je zlé Ak váš program je jediným cieľom v živote je simulovať jeden z prepojených zoznam. Čo je presne to, čo robíme. Takže skôr ako toto uviesť v hlavnej a potom ju odovzdať každému funkciu písali sme v tomto programe, sa namiesto toho si uvedomiť, oh, poďme robiť to globálny pretože celý účel tohto programu je demonštrovať jeden a iba jeden spájať zoznam. Tak, že sa cíti v poriadku. Tu sú moje prototypy, a nebudeme prejsť všetky z nich, ale napísal som funkciu odstránenie, a nájsť funkciu, insert funkcie, a funkcie pojazdu. Ale poďme sa teraz vrátiť dole do vložky funkciu a uvidíte, ako to funguje tu. Vložiť je on-line - ideme na to. Vložiť. Takže to neberie žiadne argumenty, pretože sme sa opýtať, užívateľ vnútri tejto funkcie vzhľadom k počtu chcú vložiť. Ale najprv musíme pripraviť dať im nejaký priestor. To je druh kopírovanie a vkladanie z iných príklade. V tomto prípade sme boli pridelení int, tentoraz sme pridelenie uzol. Naozaj neviem, koľko som ich bytov uzol je, ale to je v poriadku. Sizeof môže prísť, že pre mňa. A prečo som kontrolu na NULL v súlade 120? Čo sa môže pokaziť v súlade 119? Jo? [Študent odpoveď, nezrozumiteľným] Dobre. Len by mohol byť prípad, že som požiadal o príliš veľa pamäte alebo tak niečo nie je v poriadku, a operačný systém nemá dostatok bytov, ktoré by zabezpečili ma, tak to signalizuje, ako moc tým, že vráti NULL, a keď nemám kontrolu, že a ja len slepo pokračovať používať adresy, ktorú vráti, mohlo by to byť NULL. Mohlo by to byť nejaký neznámy hodnota, nie je dobrá vec, ak I - vlastne nebude neznáma hodnota. Mohlo by to byť NULL, takže nechcem zneužívať ju a riskovať dereferencing ju. Ak sa to stane, len som sa vrátiť a my vám predstierať, že som sa nedostal staré nejakú spomienku vôbec. 

Inak, poviem užívateľ mi číslo vložiť, hovorím náš starý priateľ GetInt, a potom to bolo nové syntaxe sme predstavili v pondelok. "Newptr-> n" znamená mať adresu, ktorú ste dostali od malloc ktorá predstavuje prvý bajt nového uzla objektu, a potom ísť na pole s názvom n Trochu Trivia Otázka: Jedná sa o ekvivalent toho, čo viac kryptické riadok kódu? Ako inak by som napísal toto? Chcete, aby sa bodnúť? [Študent odpoveď, nezrozumiteľným] Dobre. Pomocou. N, ale nie je to tak jednoduché, ako to. Čo som sa po prvýkrát robiť? [Študent odpoveď, nezrozumiteľným] Dobre. Musím urobiť * newptr.n. Tak to hovorí nový ukazovateľ je samozrejme adresa. Prečo? Vzhľadom k tomu, že bola vrátená malloc. * Newptr hovoriť "tam," a potom raz si tam, potom môžete použiť na viac známou. n, ale to len vyzerá trochu škaredá, najmä ak my ľudia budú kresliť ukazovatele s šípkami po celú dobu, svet má normalizované na tomto arrow zápisu, ktorý robí presne to isté. Takže môžete používať iba -> notáciu, kedy vec na ľavej strane je ukazovateľ. V opačnom prípade, ak je to skutočný struct, použite. N. A potom: Prečo som inicializovať newptr-> vedľa NULL? Nechceme sa klátící ľavú ruku preč konca etapy. Chceme, aby to smeruje priamo nadol, čo znamená koniec tohto zoznamu by mohla byť v tomto uzle, takže lepšie sa uistite, že je NULL. A všeobecne, inicializácia svoje premenné alebo dátové členmi a structs na niečo je jednoducho dobré praxe. Len nájom odpadky existujú a naďalej trvajú zvyčajne dostane do problémov ak ste zabudli niečo neskôr. 

Tu je niekoľko prípadov. To je opäť vložka funkcie, a prvá vec, ktorú som skontrolovať, ak je premenná najskôr zavolať, že globálna premenná NULL, to znamená, že nie je spájať zoznam. Sme nie je vložená žiadna čísla, takže je to triviálne vložiť toto aktuálne číslo do zoznamu, pretože to jednoducho patrí na začiatku zoznamu. Takže to bolo, keď Anita práve stál tu sám, predstierať nikto iný tu na javisku, kým sme pridelené uzol, potom mohla zdvihnúť ruku prvýkrát, ak všetci ostatní prišli na pódium za ňou v pondelok. Teraz je tu, je to trochu šek, kde musím povedať, či nový uzol je hodnota n je <hodnotu n v aktuálnej prvom uzla, to znamená, že je prepojený zoznam, ktorý ich začal. Tam je aspoň jeden uzol v zozname, ale tento nový chlap patrí pred, takže musíme presunúť veci okolo. Inými slovami, v prípade, že zoznam bol zahájený len s, povedzme, len číslo 17, to je - vlastne, môžeme to urobiť jasnejšie. Ak začneme náš príbeh s ukazovateľom tu volal ako prvý, a spočiatku je to NULL, a vložíme číslo 9, číslo 9 jasne patrí na začiatku zoznamu. Takže poďme predstierať, že sme len malloced adresu alebo číslo 9 a dať ho sem. Ak prvá je 9 štandardne, prvý scenár diskutovalo sa rozumie Poďme bod ten chlap tu, nechajte to ako NULL, teraz máme číslo 9. Ďalšie číslo chceme vložiť, je 17. 17 patrí sem, takže budeme musieť urobiť nejaký logický krokovanie cez to. Takže poďme miesto, ako to urobíme, poďme predstierať, že sme chceli vložiť číslo 8. 

Tak práve pre pohodlie boží, budem kresliť tu. Ale nezabudnite, že malloc dá to najviac kdekoľvek. Ale pre výkresu záujmu, dám to sem. Takže predstierať, že som práve pridelené uzol pre číslo 8, je to NULL v predvolenom nastavení. Čo teraz musí stať? Pár vecí. Urobili sme túto chybu na javisku v pondelok, kedy sme aktualizovali ukazovateľ, ako je tento, potom to urobil, a potom sme tvrdili - sme osamotené všetky ostatné na javisku. Pretože ste nemôžeš - poradie operácií tu je dôležité, pretože teraz sme stratili túto uzla 9, ktorý je len trochu vznáša v priestore. Takže to nie je správny prístup v pondelok. Musíme najprv urobiť niečo iné. Stav sveta vyzerá. Pôvodne sa 8 bola pridelená. Čo by to bolo lepší spôsob, ako vkladanie 8? Namiesto aktualizácia tento ukazovateľ ako prvý, len aktualizovať túto tu miesto. Takže potrebujeme riadok kódu, ktorý sa deje, aby túto NULL znak do skutočného ukazovateľ, ktorý sa ukazuje na uzol 9, a potom môžeme bezpečne meniť najprv poukázať na toho chlapa tu. Teraz máme zoznam, súvisí zoznam, z dvoch prvkov. A čo to vlastne vyzerá tu? Ak sa pozrieme na kód, zistíte, že som urobil presne to. Povedal som newptr, a v tomto príbehu, newptr mieril na toho chalana. 

Dovoľte mi teda čerpať ešte jednu vec, a ja som mal nechať trochu väčší priestor pre to. Takže odpustiť malinkú výkresu. Ten chlap sa volá newptr. To je premenná je deklarovaná niekoľko riadkov predtým, v súlade - tesne nad 25 rokov. A to ukazuje na 8. Takže keď hovorím newptr-> next, to znamená, že ísť do struct , Ktorá je momentálne ukázal na o newptr, takže sme tu, tam. Potom šípka hovorí získať ďalšie pole, a potom = hovorí kladený aké hodnoty tam? Hodnota, ktorá bola v prvej, čo hodnota bola prvá? Prvý ukazoval na tento uzol, tak to znamená, že by to malo teraz ukazujú v tomto uzle. Inými slovami, to, čo vyzerá hoci smiešne si s mojím rukopisom, Čo je jednoduchý nápad len pohybujúce sa tieto šípky okolo prekladá kód s len tento jeden vložky. Skladujte čo je v prvý v ďalšom poli a potom aktualizovať, čo najprv vlastne je. Poďme ďalej a rýchlo prechádzať niektoré z týchto, a pozrieť sa len na tomto chvosta vloženie do teraz. Predpokladám, že som sa dostať do bodu, kedy som nájsť, že budúci poľa nejakého uzla je NULL. A v tomto okamihu v príbehu, detail, že som úmyselne cez je, že som zaviedla ďalšie ukazovateľ sa tu v súlade 142, predchodca ukazovatele. V podstate, v tomto bode v príbehu, akonáhle zoznam dostane dlhý, Tak nejako som potrebné chodiť s dvoma prstami, pretože keď som ísť príliš ďaleko, pamätať v single-dĺžka zoznamu, nemôžete ísť späť. Takže táto predstava predptr je môj ľavý prst, a newptr - nie newptr. Ďalšie ukazovateľ, ktorý je tu, je môj druhý prst, a ja som to jednoducho chôdzu zoznamu. To je dôvod, prečo, že existuje. Ale poďme brať do úvahy len jeden z jednoduchších prípadoch tu. Ak tento ukazovateľ je ďalšie pole NULL, čo je logické dôsledky? Ak sa prekračovať tento zoznam a stlačíte ukazovateľ NULL? Ste na konci zoznamu, a tak kód sa potom pripojí tento jeden ďalší prvok je druh intuitívne bude tento uzol, ktorého ďalší ukazovateľ je NULL, tak to je v súčasnej dobe NULL, a zmeniť to, hoci, byť adresa nového uzla. Takže my sme len kreslenie v kóde na šípku, ktorá sme vychádzali na javisku zvýšenie niečí ľavú ruku. 

A v prípade, že budem mávať rukami na teraz, len preto, že si myslím, že je to ľahké sa stratiť, keď to robíme v tomto druhu prostredia, je kontrola vkladania do zoznamu je uprostred. Ale len intuitívne, čo sa musí stať, ak chcete zistiť, kde nejaké číslo patrí v stredu, je to, chodiť ho s viac ako jedným prstom, viac ako jeden ukazovateľ, zistiť, kam patrí podľa kontroly je element <prúd jeden, > Aktuálne jeden, a akonáhle zistíte, že miesto, potom budete musieť urobiť tento druh hazardnú hru, kde si presunúť ukazovatele okolo veľmi starostlivo. A tá odpoveď, ak by ste chceli, aby z dôvodu cez to doma na vlastnú päsť, scvrkáva len na tieto dva riadky kódu, ale poradie týchto riadkov je super dôležité. Pretože ak pustíte niekoho za ruku a zvýšiť niekoho iného v nesprávnom poradí, znova, môžete skončiť orphaning zoznam. Aby sme to zhrnuli viac koncepčne, vloženie na chvoste je pomerne jednoduché. Vloženie v čele je tiež pomerne jednoduché, ale budete musieť aktualizovať dodatočnú kurzora tentoraz stlačiť číslo 5 do zoznamu tu, a potom vloženie do stredu zahŕňa ešte viac úsilia, veľmi opatrne vložte číslo 20 vo svojom správnom mieste, ktorý je medzi 17 a 22. Takže budete musieť urobiť niečo ako majú nový uzol 20 bod 22, a potom, ktorý uzol je ukazovateľ musí byť naposledy aktualizovaný? Je to 17, skutočne vložiť ju. Takže znovu, budem odložiť skutočný kód pre túto konkrétnu implementáciu. 

Na prvý pohľad je to trochu ohromujúci, ale je to naozaj len nekonečné slučky že je opakovanie, opakovanie, opakovanie, opakovanie, a lámaniu akonáhle narazí na ukazovateľ NULL, na ktorom mieste si môžete urobiť potrebné vloženie. To je teda reprezentatívna spájať zoznam vloženie kódu. To bolo celkom veľa, a je to ako sme vyriešili jeden problém, ale sme zaviedli celú druhú. Úprimne povedané, sme strávili celý čas na veľké O a Ω a beží čas, snažia sa riešiť problémy rýchlejšie, a tu sme urobili veľký krok späť, je to pocit. A ešte, v prípade, že cieľom je ukladanie dát, to je ako svätý grál, ako sme povedali v pondelok, by bolo naozaj uložiť veci okamžite. 

V skutočnosti, predpokladám, že sme dať stranou spájať zoznam na chvíľu a my sme namiesto toho zaviedol pojem tabuľky. A povedzme, že z tabuľky na chvíľu ako pole. Toto pole a tento prípad tu má asi 26 prvkov, 0 až 25, a predpokladám, že ste potreboval nejakú kus pamäte pre názvy: Alice a Bob a Charlie a podobne. A budete potrebovať nejaké dátové štruktúry pre uloženie týchto mien. No, môžete použiť niečo ako prepojeného zoznamu a môžete ísť na zoznam vkladanie Alicu pred Bobom a Charlie po Bobovi a tak ďalej. A v skutočnosti, ak chcete vidieť kód, ako že stranou, vedieť, že v list2.h, robíme presne to. Nebudeme ísť cez tento kód, ale to je varianta prvý príklad , Ktorá zavádza jednu ďalšiu struct sme videli pred tzv študenta, a potom to, čo skutočne ukladá v prepojenom zozname je ukazovateľ na štruktúru študentov skôr než jednoduchý malý celé číslo, n Takže si uvedomujem, že je kód tam, že sa týka skutočnej reťazca, ale ak cieľ po ruke naozaj je teraz riešiť účinnosť problém, Nebolo by pekné, keby sme rovnako objekt nazvaný Alice, chceme, aby ju do správnej polohy v dátovej štruktúry, to cítia sa ako, že by bolo naozaj pekné len dať Alicu, ktorého meno začína v prvom mieste. A Bob, ktorého meno začína B, v druhom mieste. S radom, alebo začnime nazývať to tabuľku, hash tabuľka na to, môžeme robiť presne to. Ak sme dostali meno ako Alice, reťazec ako Alenka, kde si môžete dať-l-i-c-e? Potrebujeme hueristic. Musíme funkciu, aby sa nejaký vstup, ako Alice a vráti odpoveď, "Put Alicu na tomto mieste." A táto funkcia, to čierna skrinka, sa bude nazývaný hašovacia funkcia. 

Hash funkcia je niečo, čo sa vstup, rovnako ako "Alice", a vráti sa do teba, zvyčajne číselná umiestnenie v nejakom dátové štruktúry, kde Alice patrí. V tomto prípade by mal náš hashovacie funkcie bude pomerne jednoduché. Naša hash funkcia by mala povedať, ak ste rovnako "Alice", ktorý znak mám starať o? Prvý z nich. Tak som sa pozrieť na [0], a potom som povedal, ak [0] znak, vráti číslo 0. Ak je to B, vráti 1. Ak je to C, vráti 2, a tak ďalej. Všetko 0 index, a že by mi umožnilo vložiť Alicu a potom Bob a potom Charlie a tak ďalej do tejto dátovej štruktúry. Ale je tu problém. Čo keď Anita príde znova? Kam dáme Anita? Jej meno, tiež začína písmenom A, a to pocit, ako by sme urobili ešte väčší neporiadok tohto problému. V súčasnej dobe máme okamžitý vloženie, konštantný čas vloženia, do dátovej štruktúry skôr než horšom prípadu lineárne, ale čo môžeme robiť s Anitou v tomto prípade? Aké sú dve možnosti, naozaj? Jo? [Študent odpoveď, nezrozumiteľné] Dobre, takže sme mohli mať ďalší rozmer. To je dobre. Takže môžeme stavať veci v 3D, ako sme hovorili o slovne v pondelok. Mohli by sme pridať ďalší prístup sem, ale predpokladám, že nie, ja sa snažím, aby to jednoduché. Celá cieľom je mať okamžitý konštantný-time prístup, tak, aby sa pridaním príliš veľa zložitosť. Aké sú ďalšie možnosti, keď sa snaží vložiť Anitu do tejto dátovej štruktúry? Jo? [Študent odpoveď, nezrozumiteľné] Good. Takže sme mohli pohybovať všetci ostatní dole, ako Charlie štuchanec dole Bob a Alice, a potom sme dali Anita, kde naozaj chce byť. 

Samozrejme, teraz, tu vedľajší efekt tohto. Táto dátová štruktúra je pravdepodobne užitočné nie preto, že chceme vložiť ľudí raz ale preto, že chceme, aby zistili, či v prípade, že to tam neskôr Ak chceme vytlačiť všetky názvy v dátovej štruktúre. Budeme robiť niečo s týmito dátami nakoniec. Takže teraz máme takú zoskrutkované cez Alice, ktorý je už tam, kde je jej má byť. Ani je Bob, ani Charlie. Takže možno to nie je tak dobrý nápad. Ale naozaj, to je jedna možnosť. Mohli by sme posunúť všetky dole, alebo sakra, Anita prišiel neskoro do hry, prečo nie my len dať Anita nie tu, nie tu, nie tu, poďme dať ju trochu nižšie v zozname. Ale potom tento problém začne preniesť znova. Môžete byť schopní nájsť Alice okamžite, na základe jej krstného mena. A Bob okamžite, a Charlie. Ale potom sa pozriete na Anita, a uvidíte, hmm, Alice stojí v ceste. No, dovoľte mi, aby som skontrolovať nižšie Alice. Bob nie je Anita. Charlie nie je Anita. Oh, tam je Anita. A ak budete pokračovať, že vlak logiky celú cestu, čo je najhoršie doba chodu nájsť alebo vložením Anitu do tejto novej dátovej štruktúry? Je to O (n), že jo? Vzhľadom k tomu, v najhoršom prípade je to Alice, Bob, Charlie. . . celú cestu dole do niekoho menom "Y", takže je tu len jedno miesto doľava. Našťastie, nemáme s názvom "Z", takže dáme Anitu na samom dne. 

My sa naozaj vyriešiť tento problém. Takže možno naozaj musíme zaviesť tento tretí rozmer. A ukázalo sa, ak sa nám predstaví tento tretí rozmer, môžeme to urobiť dokonale, ale svätý grál sa bude stále konštantný čas vloženie a dynamické vložky tak, aby nemáme na pevný kód poľa veľkosti 26. Môžeme vložiť toľko mien, ako chceme, ale poďme sa náš 5-minút prestávku tu a potom to, že správne. Dobrá. Nastavil som ten príbeh pekne umelo tam výberom Alicu a potom Bob a potom Charlie a potom Anita, ktorého meno bolo zrejme bude kolidovat s Alicou. Ale otázka, ktorú sme skončila v pondelok, je, ako pravdepodobné je, že že by ste si tieto druhy kolízií? Inými slovami, ak začneme používať tento tabuľkový štruktúru, ktorá je naozaj len pole, v tomto prípade z 26 miest, čo keď naše vstupy miesto rovnomerne rozložené? Nie je to umelo Alice a Bob a Charlie a David, a tak ďalej abecedne, to rovnomerne rozložených do Z. 

Možno budeme mať šťastie a jednoducho nebudeme mať dva takéto alebo dve dvojky s veľmi vysokou pravdepodobnosťou, ale ako niekto poukázal, ak by sme generalizované tento problém a čo nerobiť 0-25 ale, povedať, 0 až 364 alebo 65, často sa počet dní v typickom roku a pýtal sa: "Čo je to pravdepodobnosť, že dvaja z nás v tejto miestnosti majú narodeniny v rovnaký deň?" Inak povedané, to, čo je pravdepodobnosť, že dvaja z nás má meno začínajúce? Radenie otázky je rovnaká, ale tento adresný priestor, Tento priestor hľadanie, je väčšie v prípade narodenín, pretože máme toľko viac dní v roku, než písmen v abecede. Čo je pravdepodobnosť kolízie? No, môžeme myslieť na to by prísť na matematiku na opačnú stranu. Čo je pravdepodobnosť žiadne kolízie? No, tento výraz tu hovorí, že to, čo je pravdepodobnosť ak tam je len jedna osoba v tejto miestnosti, že majú jedinečnú narodeniny? Je to 100%. Pretože v prípade, že je len jedna osoba v izbe, jeho alebo jej narodeniny môže byť ktorýkoľvek z 365 dní z roka. Takže 365/365 Možnosti mi dáva hodnotu 1. Takže pravdepodobnosť ide v súčasnej dobe je len 1. Ale v prípade, že je druhá osoba v izbe, Čo je pravdepodobnosť, že ich narodeniny sa líšia? Je tu len 364 možných dni, ignorovanie prestupných rokov, k narodeninám, aby sa zrazí s inými osobami. Takže 364/365. Ak tretia osoba príde, že je to 363/365, a tak ďalej. Takže budeme držať súčinu týchto kúskov, ktoré sú stále menšie a menšie, prísť na to, aká je pravdepodobnosť, že každý z nás má unikátnu narodeniny? Ale potom môžeme, samozrejme, len sa, že odpoveď a otočte okolo a to 1 mínus všetko, výraz budeme nakoniec dostať ak si spomeniete na zadnej strane matematických kníh, vyzerá to trochu niečo také, , Ktorý je oveľa ľahšie interpretovať graficky. A to grafický tu má na osi x počet narodenín, alebo počet ľudí s narodenín, a na osi y je pravdepodobnosť zápasu. A čo to hovorí, je, že ak máte, povedzme, aj, Poďme si niečo ako 22, 23. Ak je 22 alebo 23 ľudí v miestnosti, pravdepodobnosť, že dva z týchto veľmi málo ľudí bude mať narodeniny v rovnaký deň je vlastne veľmi vysokým, combinatorially. 50% šanca, že v triede len 22 ľudí, semináre, prakticky, 2 z týchto ľudí bude mať narodeniny v rovnaký deň. Vzhľadom k tomu, že je tak veľa spôsobov, ako môžete mať narodeniny v rovnaký deň. Ešte horšie je, keď sa pozriete na pravej strane grafu, v čase, keď budete mať triedu s 58 žiakmi v tom, pravdepodobnosť 2 osoby, ktoré majú narodeniny je super, veľmi vysokým, takmer 100%. No, to je niečo ako zábavný fakt o skutočnom živote. 

Ale dôsledky, teraz, dátových štruktúr a ukladanie informácií Znamená to, že len za predpokladu, že máte pekný, čistý, rovnomerné rozloženie dát a máte dosť veľký pole, aby sa zmestili na veľa vecí, neznamená, že budete, aby si ľudia v unikátnych lokalitách. Budeš mať kolízie. Takže tento pojem hašovanie, ako sa to volá, pričom vstup ako "Alice" a masírovať ju nejakým spôsobom a potom sa dostať späť odpoveď ako 0 alebo 1 alebo 2. Dostať sa späť nejaký výstup z tejto funkcie je sužovaný tejto pravdepodobnosti kolízie. Takže, ako môžeme zvládnuť tieto kolízie? No, na jednom prípade, môžeme myšlienku, že bolo navrhnuté. Môžeme len posunúť všetky dolu, alebo možno, trochu jednoduchšie, skôr než pohyb všetci ostatní, poďme presunúť Anitu na spodnej časti je k dispozícii mieste. Takže ak Alice je 0, Bob je v 1, Charlie je 2, budeme len dať Anitu na mieste 3. A to je technika v dátových štruktúrach tzv lineárne snímanie. Lineárne preto, že ste len pešia tento riadok, a ty si nejako snímanie dostupných miestach v dátovej štruktúre. Samozrejme, že to prejde do O (n). Ak dátová štruktúra je naozaj plná, je tu 25 ľudí v ňom už, a potom Anita príde, ona skončí na to, čo by bolo zaradenie Z, a to je v poriadku. Stále sedí, a nájdeme ju neskôr. 

Ale to bolo v rozpore s cieľmi urýchlenie veci. Takže čo keby sme miesto zaviedla tento tretí rozmer? Táto technika sa všeobecne nazýva oddelené zreťazenie, alebo s reťazami. A čo hash tabuľka je teraz, to tabuľkové štruktúry, Váš stôl je len pole ukazovateľov. Ale čo tie ukazovatele poukazujú, je odhad, čo? Spájať zoznam. Takže čo keby sme vziať to najlepšie z oboch týchto svetov? Používame pole pre počiatočné indexy do dátovej štruktúry, takže môžeme okamžite prejsť na [0] [1], [30], alebo tak podobne, ale tak, že máme určitú flexibilitu a my sa zmestí Anitu a Alice a Adam a iné meno, sme namiesto toho nechať druhej osi rast ľubovoľne. A nakoniec sme sa, v pondelok, má to výrazný schopnosť s prepojeného zoznamu. Môžeme pestovať dátovú štruktúru ľubovoľne. Prípadne môžeme len urobiť veľký 2-rozmerné pole, ale že to bude hrozné situácie, ak jeden z riadkov v 2-rozmerné pole nie je dostatočne veľké pre ďalšie osobe, ktorej meno sa stane začať s A. Boh chráň, musíme prerozdeliť obrovský 2-dimenzionální štruktúra len preto, že je tu toľko ľudí s názvom, zvlášť keď je tu tak málo ľudí s názvom Z niečo. Je to len bude veľmi riedke dátová štruktúra. Takže to nie je dokonalé v žiadnom prípade, ale teraz máme mať aspoň možnosť okamžite zistiť, kde Alice alebo Anita patrí, aspoň pokiaľ ide o zvislej osi, a potom sme sa len rozhodnúť, kam Anitu alebo Alice v tomto prepojenom zozname. Ak sa nezaujíma radenie veci, ako by rýchlo vložíme Alicu do štruktúry, ako je tento? Je to konštantný čas. My index do [0], a ak nie je niečí tam, Alice pokračuje na začiatku tohto prepojeného zoznamu. Ale to nie je veľký problém. Pretože ak Anita potom príde nejaké číslo z krokov neskôr, kedy sa Anita patrí? No, [0]. OOP. Alice je už v tomto prepojenom zozname. 

Ale ak nebudeme starať o radenie tieto mená, môžeme len presunúť Alice cez, vložka Anita, ale aj to je konštantný čas. Aj v prípade, že je Alice a Adam a všetko ostatné A mená, to nie je naozaj posun je fyzicky. Prečo? Pretože sme práve urobili tu s prepojeného zoznamu, ktorý vie, boli tieto uzly sú vlastne je? Jediné, čo musíte urobiť, je presunúť strúhanky. Presuňte šípkami okolo, nemusíte fyzicky presunúť všetky dáta okolo. Takže môžeme vložiť Anita, v tomto prípade, okamžite. Konštantný čas. Takže máme konštantný čas vyhľadávania a konštantný čase vkladanie niekoho ako Anita. Ale trochu zjednodušujúce svet. Čo keď sme neskôr chcete nájsť Alicu? Čo keď sme neskôr chcete nájsť Alicu? Koľko krokov je to, že bude trvať? [Študent odpoveď, nezrozumiteľným] Presne tak. Počet ľudí, ako Alice v pripojenom zozname. Takže to nie je úplne dokonalý, pretože naše dátová štruktúra, znovu, má túto vertikálny prístup a potom má tieto prepojené zoznamy visiace - vlastne, nech to nie je nakresliť poľa. Je táto spojené zoznamy visiace z nej, že vyzerá trochu niečo takého. Ale problém je, ak Alice a Adam a všetko ostatné A mená nakoniec viac a viac tam, nájsť niekoho, kto by mohol skončiť brať veľa krokov, bcause budete musieť prechádzať prepojeného zoznamu, ktorý je lineárna operácia. Takže naozaj, potom, vloženie času nakoniec je O (n), kde n je počet prvkov v zozname. Delené, nech je ľubovoľne nazvať m, kde m je počet prepojených zoznamov že majú v tomto zvislej osi. Inými slovami, ak sa skutočne predpokladať rovnomerné rozloženie mien, úplne nereálne. Je tu samozrejme viac niektorých písmen než ostatní. 

Ale ak budeme predpokladať pre túto chvíľu jednotný distribučné, a my sme n celkovej ľudí, a m celkom reťaze K dispozícii nám, potom dĺžka každej z týchto reťazcov pomerne jednoducho bude celkový, n delí počtom reťazcov. Takže n / m Ale tu je miesto, kde môžeme byť všetci matematicky šikovný. m je konštanta, pretože tam je pevne stanovený počet z nich. Budeš deklarovať svoju ponuku na začiatku, a my nie sme zmeny veľkosti zvislú os. Podľa definície, ktorá zostáva pevná. Je to len na vodorovnej osi, aby som tak povedal, že to mení. Takže technicky, to je konštanta. Takže teraz, vloženie času je do značnej miery O (n). Takže nie je pocit, že všetci, že oveľa lepšie. Ale čo je pravda tu? No, tentoraz, celé týždne, sme hovorili O (n ²). O (n), 2 x n?, - N, deleno 2. . . ech. Je to len n ². Ale teraz, v tejto časti semestra, môžeme začať hovoriť o reálnom svete znovu. A n / m, je úplne rýchlejší než len n sám. Ak máte tisíce mien, a rozdeľujú ich do viacerých segmentov takže majú len desať mien v každej z týchto reťazcov, úplne vyhľadávania desať vecí bude rýchlejší než tisíc vecí. A tak jeden z nasledujúcich problémových súborov sa chystá vyzvať vás premýšľať o tom, presne, že aj keď, jo, asymptoticky a matematicky, to je stále len lineárne, ktorý nasáva všeobecne, keď sa snažia nájsť veci. V skutočnosti, to bude rýchlejšie, než že pretože toto deliteľ. A tak tam je zase bude tento trade-off a tento konflikt medzi teóriou a realitou, a jeden z gombíkov začne otáčať v tomto bode v semestri je viac v realite s tým, ako sme trochu pripraviť na koniec semster je, ako sme predstaviť svet programovanie pre web, kde naozaj, výkon bude počítať, pretože používatelia budú začať cítiť a oceniť chudobné návrhárska rozhodnutia. 

Tak ako sa vám ísť o realizáciu prepojené - hash tabuľku s 31 prvkami? A predchádzajúci príklad bol ľubovoľne o narodeniny. Ak má niekto narodeniny k 1. januári alebo vo februári 1, dáme ich do tejto vedra. Ak je to 2. januára 2. februára 2. marca dáme im v tomto vedre. To je dôvod, prečo to bolo 31. Ako deklarovať hash tabuľky? To môže byť celkom jednoduché, uzol * stôl je moja ľubovoľný názov pre to, [31]. To mi dáva 31 ukazovatele na uzly, a to mi umožňuje mať 31 ukazovatele na súvisiace zoznamy aj keď tieto reťazce sú spočiatku NULL. Čo chcem, aby, keď chcem uložiť "Alice," "Bob", "Charlie"? No, musíme baliť tie veci v štruktúre pretože musíme Alice bodu k Bobovi, aby ukazoval na Charliem, a tak ďalej. Nemôžeme len tak mať mená sám, takže som mohol vytvoriť novú štruktúru s názvom uzla tu. 

Čo je skutočná uzol? Čo je uzol v tomto novom prepojeného zoznamu? Prvá vec, hovorí slovo, je pre meno osoby. DĹŽKA, pravdepodobne, sa týka maximálnej dĺžky ľudského mená, čo to je, 20, 30, 40 znakov v bláznivých rohových prípadoch, a 1 je pre čo? Je to len ďalší znak NULL, \ 0. Tak to je uzol balenia "niečo" vo vnútri seba samého, ale tiež deklaruje ukazovateľ s názvom ďalšie takže môžeme reťazec Alice k Bobovi s Charliem, a tak ďalej. Môže byť NULL, ale nemusí byť. Akékoľvek otázky týkajúce sa týchto hash tabuľky? Jo? [Študent pýtať otázku, nezrozumiteľné] Pole - dobrá otázka. Prečo je tento char slovo v poli skôr než len char *? V tomto trochu svojvoľné príklade, nechcel som, aby sa uchýliť malloc pre každú z pôvodných názvov. Chcel som, aby určil maximálne množstvo pamäte pre reťazec tak, že by som mohol skopírovať do štruktúry Alice \ 0 a nebudú sa musieť vysporiadať s malloc a slobodné a podobne. Ale čo som mohol urobiť, že keď som chcel byť viac vedomí využitie priestoru. Dobrá otázka. Takže poďme sa pokúsiť zovšeobecniť od tohto a zamerať sa na zvyšok dnešného dňa dátových štruktúr všeobecne a iné problémy, ktoré môžeme vyriešiť použitím rovnakých základy aj keď dátové štruktúry samy sa môžu líšiť vo svojich údajov. 

Tak to dopadá vo vede o počítačoch, stromy sú veľmi časté. A vy môžete myslieť stromu druhu ako rodinný strom, tam, kde je nejaké korene, niektoré matriarchát alebo patriarcha, babička alebo dedko alebo starší späť, , Pod ktorým sú mama a otec, alebo rôzne súrodenci alebo podobne. Takže stromová štruktúra má uzly a má deti, zvyčajne 0 alebo viac detí pre každý uzol. A niektoré z žargónu, ktorý vidíte na obrázku tu je niektorý z malé deti alebo vnúčatá na okrajoch ktorí nemajú žiadne šípky vychádzajúce z nich, to sú tzv listy, a niekto na vnútornej strane je vnútorný uzol, môžete tomu hovoriť čokoľvek na týchto tratiach. Ale táto štruktúra je celkom bežné. To je trochu svojvoľný. Máme jedno dieťa na ľavej strane, máme tri deti na pravej strane, dve deti na ľavej dolnej časti. Takže môžeme mať rôzne veľkosti stromy, ale ak začneme štandardizovať veci, a môžete pripomenúť to z videa Patrika na binárne vyhľadávanie z predchádzajúcej krátkej on-line, binárne vyhľadávanie nemusí byť realizované s radom alebo kúsky papiera na tabuľu. Predpokladajme, že ste chceli uložiť čísla v sofistikovanejšie dátové štruktúry. Môžete vytvoriť strom, ako je tento. Tie by mohli mať uzol deklarované v C, a že uzol môže mať najmenej dva prvky vnútri nej. Jedným z nich je číslo, ktoré chcete uložiť, a druhý je - dobre, potrebujeme ešte jeden. Na druhej strane je jeho deti. Tak tu je ďalšie dátové štruktúry. Tento čas je uzol definovaný ako ukladanie čísla n a potom dva ukazovatele, ľavá dieťaťa a právo dieťaťa. A sú to nebolo svojvoľné. Čo je na tom zaujímavé tohto stromu? 

Čo je vzor v tom, ako sme podľa tohto, alebo ako Patrick položil ju vo svojom videu? Je to trochu zrejmé, že tam je nejaký triedenie deje, ale to, čo je jednoduché pravidlo? Jo? [Študent odpoveď, nezrozumiteľným] Perfect. Ak sa pozrel na to, uvidíte malé množstvo na ľavej strane, veľké čísla na ľavej strane, ale to je pravda pre každého uzla. Pre každý uzol, jeho ľavý dieťa menej než to, a jej právo dieťa väčšie než to. Čo to znamená, je teraz, keď chcem hľadať túto dátovú štruktúru pre, povedzme, číslo 44, Musím začať pri koreni, pretože podobne ako u všetkých týchto zložitejších dátových štruktúr teraz, máme len ukazovateľ na jednu vec, na začiatku. A v tomto prípade, je začiatok koreňový. Nie je to ľavý koniec, to je koreň tejto štruktúry. Tak vidím, tu je 55, a ja hľadám 44. Ktorým smerom sa chcem ísť? No, ja chcem ísť doľava, pretože samozrejme, doprava bude príliš veľký. Tak zistíte tu, že ste trochu koncepčne sekanie strom v polovici preto, že ste nikdy ísť dole na pravej strane. Takže teraz idem od 55 do 33. Je to príliš malá čísla. Hľadám 44, ale teraz viem, že ak 44 je v tejto vetve, môžem ísť samozrejme doprava. Takže znova, ja som prerezávanie stromu na polovicu. Je to celkom veľa totožné koncepčne do telefónneho zoznamu. Je to rovnaké ako to, čo sme robili s papiermi na tabuľu, ale je to zložitejšie štruktúra, ktorá nám umožňuje skutočne robiť Tento rozdeľ a panuj podľa návrhu algoritmu, a v skutočnosti, posuvné konštrukcie, ako je tento - POZOR. Pojazdová štruktúru, ako je tento, kde je to len "ísť tade alebo tade," znamená, všetky tie kód, ktorý sklonil svoju myseľ ako prvé, keď jeho zavedenie do oddielu alebo pri chôdzi cez to doma, pre binárne vyhľadávanie, pomocou rekurzie alebo iterácie, je to bolesť v krku. Nájsť prostredný prvok, potom urobiť si zaokrúhlenie nahor alebo nadol. 

Je tu krásu, pretože môžeme teraz používať rekurziu znovu, ale oveľa čistejšie. Naozaj, ak ste sa na číslo 55 a chcete nájsť 44, môžete ísť doľava v tomto prípade, potom to, čo robíte? Spustenie presne rovnaký algoritmus. Skontrolovať hodnotu uzla, potom ísť doľava alebo doprava. Potom si zistiť hodnotu uzla, prejdite vľavo alebo vpravo. Toto sa dokonale hodí pre rekurzie. Takže aj keď v minulosti sme urobili niektoré docela ľubovoľné príklady zahŕňajúce rekurzia že sa nemusí byť rekurzívne, s dátovými stuctures, najmä stromy, je to perfektné aplikácie tejto myšlienky brať problém, zmršťovanie, a potom riešiť rovnaký typ, ale menšie, program. 

Takže je tu ďalšia dátová štruktúra, ktorá môžeme predstaviť. Ten je určený na prvý pohľad vyzerať záhadné, ale toto je úžasné. Tak to je dátová štruktúra volal trie, trie, ktorá sa dedí od slova vyhľadávania, ktoré sa nevyslovuje re-try-Val, ale to je to, čo svet nazýva tieto veci. Skúsi. T-r-i-e. Je to strom štruktúra nejaký, ale každá z uzlov v trie Zdá sa, že to, čo? A to je trochu zavádzajúce, pretože je to trochu skrátený. Ale vyzerá to, že každý uzol v tomto trie je vlastne pole. A aj keď autor tohto diagramu nepreukázala to, v tomto prípade, to trie je dátová štruktúra, ktorej cieľom v živote je ukladať slová ako A-l-i-c-e alebo B-o-b. A spôsob, akým tieto dáta ukladá Alice a Bob a Charlie a Anita a tak ďalej je používa pole, kedy k ukladaniu Alice v trie, začíname na koreňový uzol, ktorý vyzerá ako pole, a to bolo napísané v rýchlopisný záznam. Autor vynechať abcdefg pretože tam neboli žiadne názvy s tým. Oni len ukázal, M a P a T, ale v tomto prípade, poďme od Alice a Bob a Charlie niektorých názvov, ktoré sú tu. Maxwell je vlastne v tomto diagrame. Tak ako ste s autorom obchod M - x-w-e-l-l? On alebo ona začala na koreňový uzol, a šiel do [M], tak zhruba 13, 13. miesto v poli. Potom odtiaľ, tam je ukazovateľ. Ukazovateľ vedie k ďalšie pole. Odtiaľ autor indexované do tohto poľa v mieste A, ako je znázornené tu vľavo hore, a potom on alebo ona nasledovala tento ukazovateľ do iného poľa, a šiel na ukazovateľ na umiestnenie X. Potom v ďalšom poli umiestnenie W, E, L, L, a tak ďalej, a konečne, poďme sa skutočne snaží, aby obraz na to. Čo uzol vyzerá v kóde? Uzol v trie obsahuje pole ukazovateľov na viac uzlov. Ale tam je tiež to byť nejaký druh Logické hodnota, aspoň v tomto prevedení. A stalo sa, hovorím is_word. Prečo? Pretože keď ste vkladanie Maxwella, nie ste vkladanie niečo do tejto dátovej štruktúry. Nie ste písanie M. Nie ste písanie X. Všetko, čo robíte, je po ukazovateľov. Ukazovateľ, ktorý predstavuje M, potom ukazovateľ, ktorý predstavuje, potom ukazovateľ, ktorý predstavuje X, potom W, E, L, L, ale to, čo musíte urobiť, na konci je trochu ísť, skontrolujte, som dosiahol tohto umiestnenia. Tam bolo slovo, ktoré tu končí v dátovej štruktúre. 

Takže to, čo trie je naozaj plný a autor sa rozhodol reprezentovať Tieto medzníky s malými trojuholníkmi. To jednoducho znamená, že skutočnosť, tento trojuholník je tu, táto boolean hodnotu true znamená, že ak pôjdete späť do stromu, to znamená, že slovo s názvom Maxwell je v tomto. Ale slovo foo, napríklad, nie je v strome, pretože keď som sa začať v koreňovom uzle tu hore, Nie je f ukazovateľ, nie ukazovateľ o, nie ukazovateľ o Foo nie je meno v tomto slovníku. Ale naopak, Turing, t-u-r-i-n-g. Opäť platí, že nebudú ukladať t alebo u alebo r alebo aj alebo n alebo g Ale som obchod v tejto dátovej štruktúre hodnota skutočného tu dole v tomto uzle - na strome Nastavením tejto boolovská is_word na true. Takže trie je druh tejto veľmi zaujímavej meta štruktúry, kam naozaj ukladanie slov sám pre tento druh slovníka. Aby bolo jasno, ste len ukladanie áno alebo nie, tam je slovo, ktoré tu končí. 

Teraz, čo je dôsledok? Ak máte 150.000 slov v slovníku, že sa snažíte uložiť do pamäte používať niečo ako prepojeného zoznamu, budete mať 150.000 uzly vo vašom prepojeného zoznamu. A nájsť jednu z tých slov abecedne môže trvať O (n) čas. Lineárne čas. Avšak v prípade tu o trie, čo je doba chodu nájsť slovo? Ukazuje sa, že krásu je, že aj keď máte 149999 slov už v tomto slovníku, ako bol vykonaný s touto dátovou štruktúrou, koľko času zaberie nájsť alebo vložiť jednu osobu do toho, ako Alenka, Alice? No, je to len 5, možno 6 krokov pre koncových znak. Vzhľadom k tomu, presense ďalších mien v štruktúre nie je v ceste vkladanie Alice. Navyše, hľadanie Alice akonáhle tam sú 150.000 slov v tomto slovníku nedostane v ceste nájsť Alicu vôbec, pretože Alice je. . . . . tu, pretože som našiel logickú hodnotu. A v prípade, že nie je boolean true, potom Alice nie je v tejto dátovej štruktúre slov. Inými slovami, doba chodu zistiť veci a vkladanie vecí do tohto nového dátová štruktúra trie je O z - nie je to n Vzhľadom k tomu, presense zo 150.000 ľudí, nemá žiadny vplyv na Alicu, ako sa zdá. Takže povedzme, že k, kde k je maximálna dĺžka slova v angličtine ktorý je typicky nie viac ako 20-niečo znaky. Takže k je konštanta. Takže Svätý Grál sa zdá, že sme našli hneď je to, že z trie, konštantnom čase pre vložiek, pre vyhľadávanie, pre vymazanie. Vzhľadom k tomu, mnoho vecí už v štruktúre, ktoré nie sú ani fyzicky tam. Opäť platí, že sú to len nejako odškrtnúť, áno alebo nie, nemá žiadny vplyv na jej budúcu dobu prevádzky. 

Ale tam to musí byť nejaký háčik, inak by sme nemali plytvať toľko času na všetkých týchto ostatných dátových štruktúr, len aby konečne dostať do tajnej ten, ktorý je úžasný. Takže akú cenu sú platíme, aby dosiahnutie tohto veľkosť tu? Space. Táto vec je masívny. A dôvod, prečo autor nepredložila to tu, všimnite si, že všetky tieto veci, ktoré vyzerajú ako pole, nemal čerpať zvyšok stromu, zvyšok z trie, pretože to jednoducho nie je relevantné k príbehu. Všetky tieto uzly sú super široký, a každý uzol v strome zaberá 26 alebo vlastne, môže byť 27 znakov, pretože v tomto prípade som bol, vrátane priestoru pre apostrof tak, že by sme mohli mať apostrophized slová. V tomto prípade sa jedná o široké pole. Takže aj keď to nie sú picutured, to zaberá obrovské množstvo pamäte RAM. Ktorý by mohol byť v poriadku, especilly v modernom hardvéri, ale to je kompromis. Dostávame menej času tým, že míňa viac priestoru. Takže tam, kde sa to všetko deje? Dobre, poďme robiť - uvidíme tu. Poďme urobiť skok s tymto chlapom tu. 

Verte tomu alebo nie, taká zábava ako C už dlhšiu dobu, sme dosiahnutí bodu v semestri, kedy je čas na prechod k veciam viac moderné. Veci na vyššej úrovni. A aj keď pre najbližších pár týždňov budeme aj naďalej pokračovať v ponoriť do sveta ukazovateľov a správa pamäte sa dostať, že pohodlie, s ktorými sa potom môžeme stavať na, Koniec hry je nakoniec zaviesť, ironicky, nie tento jazyk. Strávime, rovnako ako 10 minút hovoriť o HTML. Všetko HTML je je značkovací jazyk, a to, čo značkovací jazyk je je, že tieto série otvorených zátvoriek a uzavretých hranatých zátvoriek, ktoré hovoria, že "aby to tučne" ", Aby to kurzívou" "túto stredu." To nie je všetko, že intelektuálne zaujímavé, ale je to super užitočné. A rozhodne to všadeprítomný v týchto dňoch. Ale čo je najlepšie o svete HTML, a webové programovanie všeobecne, je vytváranie dynamických veci, písanie kódu v jazykoch ako PHP alebo Python alebo Ruby alebo Java alebo C #. Naozaj, aký je váš jazyk výberu je, a generovanie HTML dynamicky. Generovanie niečo ako CSS dynamicky. Kaskádové štýly, čo je tiež o estetike. A tak aj keď dnes, keď som ísť do nejakej webovej stránky, ako známe Google.com, a ja idem na prezeranie, developer, pohľad zdroj, ktorý možno ste nevyskúšali, ale ak bude zobraziť zdroj, toto asi vyzerá dosť záhadné. Ale to je zdrojový kód, ktorý implementuje Google.com. Na prednej strane. A vlastne to všetko je nadýchaná estetika veci. To je CSS tu. Keby som posúvanie bude pokračovať, sa budeme trochu farebne veci. To je HTML. Google kód vyzerá neporiadok, ale keď som v skutočnosti otvoriť iné okno, môžeme vidieť nejakú štruktúru, aby to. Ak otvorím toto hore, všimnite si, tu je to trochu zrozumiteľnejšie. Budeme vidieť, ako dlhé túto značku, [word] je tag, HTML, hlava, telo, div, skript, text area, span, stred, div. A to je tiež nejako tajomné vyzerajúce na prvý pohľad, ale všetky z tejto šlamastiky riadi určitými vzormi, a opakovateľné vzory, tak, že akonáhle sa dostaneme základy dole, budete môcť písať kód, ako je tento a potom manipulovať kód, ako to pomocou ešte ďalší jazyk, s názvom JavaScript. A JavaScript je jazyk, ktorý beží vnútri webového prehliadača dnes používame na Harvard kurzov, pre nástroj predmetu nákupné že Google maps používa aby vám veľa dynamiky, Facebook vám dáva pre zobrazenie okamžitej aktualizácie stavu, Twitter používa to, aby vám ukázať tweety okamžite. To všetko začneme ponoriť dovnútra Ale aby sa tam dostať, musíme pochopiť, niečo málo o internete. Tento klip je tu len minútu dlhé, a predpokladajme, že pre túto chvíľu je to v skutočnosti, ako internet funguje ako upútavka na to, čo je asi príde. Dám vám "Warriors of internete." 

[♫ Slow chorus music ♫] [Muž rozprávač] Prišiel so správou. S protokolom všetky jeho vlastné. [♫ Rýchlejšie electronic music ♫] Prišiel na svet v pohode firewallov, bezcitný smerovača, a nebezpečenstvo ďaleko horšie ako smrť. Je rýchly. Je to silný. Je to TCP / IP, a on má svoju adresu. Warriors siete. [Malan] Budúci týždeň, a potom. Internet. Web programovanie. To je CS50. [CS50.TV]