[Powered by Google Translate] [Návod - Problém Set 5] [Zamyla Chan - Harvard University] [To je CS50. - CS50.TV] 

Dobrá. Ahoj, všetci, a vitajte na Walkthrough 5. 

Pset5 je Pravopisné chyby, v ktorom budeme robiť pravopisu. Spell-dáma, sú nesmierne dôležité. Má to niekedy stalo? Môžete pracovať veľmi, veľmi hromadia na papieri pre stret a potom ešte nakoniec dostať veľmi žiara Rade ako D alebo D = a všetci preto, že ste liverwurst spojler v veľrýb širokom slova. Áno, korektúry vašich papriky je vec, maximálna impotencia. To je problém, ktorý postihuje mužské, mužné študentov. Bol som raz povedal môj mučiteľovi stupňa Sith, že by som nikdy dostať do dobrého kolegu. A to je všetko, čo som kedy chcel, to je všetko, každý chlapec chce v mojom veku, Len dostať sa do dobrej kolegovi. A nie len tak hocijaký kolega. Nie Chcel som ísť do Slonoviny Právne kolegovi. Takže ak som to zlepšenie, by šiel sa moje sny o ísť na Harvard, Jale, alebo Prison - viete, vo väznici, New Jersey. Tak som si sám sebe pravopisu. To je trochu výpis z jednej z mojich najobľúbenejších hovorené slovo umelcov, Taylor Mali. Každopádne, ako hovorí, že je dôležité mať pravopisu je veľmi dôležité. 

Takže vitajte na Walkthrough 5, v ktorom sa bude hovoriť o pset5: pravopisné chyby, , V ktorom budeme robiť naše vlastné pravopisu. Nástrojov pre tento týždeň, distribúcia kód, bude dôležité, aby sa na len pochopiť rôzne funkcie, ktoré váš slovník bude mať. Sme vlastne bude mať viac. C. súborov, ktoré dohromady tvoria našu PSet. A tak hľadá prostredníctvom rôznych aspektoch, aj keď sme vlastne nie pre editáciu jeden zo súborov, speller.c, vedel, ako to funguje vo vzťahu k dictionary.c, ktoré budeme písať, bude dosť dôležité. Spec Pset tiež obsahuje mnoho užitočných informácií pokiaľ ide o veci, ktoré môžete predpokladať, pravidlá a podobné veci, ktoré, tak sa určite prečítajte PSet špec starostlivo tipy. A v prípade pochybností o pravidlá alebo niečo také, potom sa vždy vzťahujú k PSet spec alebo Diskutovať. Tento Pset bude spoliehať na ukazovatele, tak chceme, aby sa ubezpečil, že sme pochopili rozdiel medzi pridávanie hviezdičiek v prednej časti je ukazovateľ meno a ampersand, ako sa oslobodiť a atď Takže byť majstrom ukazovateľov bude veľmi užitočné v tomto probléme sade. Budeme sa pozrieť do prepojené zoznamy trochu viac, kde majú prvky, ktorý nazývame uzly, ktoré majú ako hodnotu, rovnako ako ukazovateľ k nasledujúcemu uzlu, a tak v podstate prepojenie rôznych prvkov jeden po druhom. Existuje niekoľko rôznych možností na realizáciu svojej skutočnej slovník. Budeme sa pozrieť do dvoch hlavných metód, ktoré je hashovacie tabuľky a potom sa pokúsi. V oboch tých, ktoré zahŕňajú nejaký druh pojmu prepojeného zoznamu kde ste elementy navzájom prepojené. A tak budeme vyzerať nad tým, ako by ste mali byť schopní pracovať okolo prepojených zoznamov, vytvoriť, prechádzať z hľadiska ako, napríklad, vložiť uzol do neho alebo bez všetky uzly rovnako. Pokiaľ ide o uvoľňovacími uzlov, to je naozaj dôležité že kedykoľvek sme malloc pamäti, potom sme uvoľniť ju. Takže chceme, aby sa ubezpečil, že žiadny ukazovateľ ide unfreed, že nemáme žiadne úniky pamäte. Budeme zaviesť nástroj nazývaný Valgrind, ktorý beží na programe a kontroluje, či všetky pamäti, že pridelené je potom oslobodený. Vaša Pset je len dokončiť, keď to funguje, a má plnú funkčnosť, ale tiež, Valgrind vám povie, že ste nenašli žiadne úniky pamäte. Napokon, pre tento PSet, naozaj chcem zdôrazniť - Myslím, ako zvyčajne, ja som rozhodne zástancom použitia pera a papiera pre vaše problémové súbory, ale pre tento jeden, myslím, že pero a papier bude obzvlášť dôležité ak chcete, aby sa čerpanie šípky na veci a pochopenie toho, ako veci fungujú. Takže určite skúste použiť ceruzku a papier k tomu, čo pred vás kódovanie pretože by to mohlo byť trochu chaotický. 

Po prvé, poďme do prepojených zoznamov trochu. Prepojené zoznamy sa skladajú z uzlov, kde každý uzol má hodnotu spojenú s ním, rovnako ako ukazovateľ na ďalší uzol po ňom. Pár vecí dôležitých s lineárnymi zoznamy je, že musíme mať na pamäti kde naša prvá uzol je, a potom raz vieme, kde prvý uzol je, že spôsob, ako môžeme pristupovať na uzol, ktorý prvý uzol odkazuje na a potom ešte do a jeden po tom. A potom posledný prvok vo vašom prepojeného zoznamu je tento uzol je ukazovateľ je vždy poukázať na NULL. Keď uzol bodov na hodnotu NULL, potom viete, že ste na konci zoznamu, že uzol je posledný, že nie je nič po tom. Tu v tomto schéme, uvidíte, že šípky sú ukazovatele, a modré sekcia je miesto, kde je uložený hodnota, a potom červené pole s ukazovateľ na nej je uzol je ukazovateľ ukazuje na ďalší uzol po ňom. A tak tu vidíte, by uzol D poukázať na NULL, pretože to je posledný prvok v zozname. 

Poďme sa pozrieť na to, ako by sme mohli definovať struct pre uzol. A pretože chceme mať viac uzlov, to sa stane typedef struct , V ktorom budeme mať niekoľko rôznych inštancií uzlov. A tak sme ju definujú ako nový dátový typ. Tu máme typedef struct uzol. V tomto príklade, máme čo do činenia s celočíselnými uzlami, takže máme celočíselnú názvom hodnotu a potom máme ďalšie ukazovateľ, a v tomto prípade, je to ukazovateľ na uzol, takže máme struct uzol * volal ďalšie. A potom voláme celú túto vec uzol. Uistite sa, že budete dodržiavať nasledujúce syntax. Všimnite si, že uzol je v skutočnosti odkazuje hore rovnako ako dole zložených zátvoriek. Potom sledovať, kde moja prvá uzol v tomto prepojenom zozname, potom som si uzol ukazovateľ s názvom hlava, a ja malloc dostatok priestoru pre veľkosť uzla. Poznámka, však, že hlava je vlastne uzol ukazovateľ na rozdiel od aktuálneho uzla samotného. Takže hlava skutočne neobsahuje žiadnu hodnotu, iba poukázať na podľa toho, čo prvý uzol v mojom prepojeného zoznamu je. 

Ak chcete získať lepšiu predstavu o súvisiacich zoznamov, pretože je to veľmi dôležité, sledovať uistiť sa, že budete udržiavať reťaz, Páči sa mi myslieť na to, ako sa ľudia v rade sa drží za ruky, , Kde každá osoba je drží za ruky s ďalšie. Nemôžete vidieť v tomto výkresu, ale v podstate sú to ukazuje na ďalšiu osobu že je v ich reťazci. A tak ak chcete prejsť prepojené zoznam, kde títo ľudia - predstaviť všetkých tých ľudí majú hodnoty spojené s nimi a tiež poukazujú na ďalšie osoby v súlade - Ak chcete prejsť prepojeného zoznamu, napríklad, buď upraviť hodnoty alebo hľadanie hodnote alebo niečo také, potom budete chcieť mať ukazovateľ na konkrétnu osobu. Takže budeme mať dátový typ uzla ukazovateľ. Pre tento Napríklad, povedzme, že kurzor. Ďalším bežným spôsobom pomenovať to bude Iterator, alebo niečo také pretože je to iterácie a vlastne dojemná, ktorý uzol to ukazuje. Toto bude naše kurzor. Náš kurzor sa najprv poukázať na prvý prvok v našom zozname. A tak to, čo chceme urobiť, je, že sme sa v podstate bude pokračovať kurzor, pohybujúce sa zo strany na stranu. V tomto prípade, chceme presunúť na ďalší prvok v zozname. S poľom, čo budeme robiť, je by sme len povedať, že sme zvýšiť index 1. V tomto prípade, čo musíme urobiť, je skutočne zistiť, ktoré osoby tento prúd osoba smerujúce, a že to bude ďalšiu hodnotu. Takže ak kurzor je len uzol ukazovateľ, potom to, čo chceme robiť je, že sa chcú dostať na hodnotu, ktorá je kurzor ukazuje. Chceme sa dostať do tohto uzla a potom, až budeme v tomto uzle, zistiť, kde to ukazuje. Ak chcete dostať do aktuálneho uzla, ktorý kurzor ukazuje na, zvyčajne označujeme ju (* kurzor). To by vám aktuálne uzol, ktorý kurzor ukazuje. A potom, čo chceme urobiť, je chceme pristupovať čo to uzla budúci hodnota. K tomu, aby sa prístup k hodnoty vnútri struct, máme operátora bodka. Takže potom by to bolo (* kurzor). Ďalšie. Ale to je trochu chaotický, pokiaľ ide o to, aby zátvorky okolo * kurzora, a tak sme sa nahradiť celú túto vyhlásenie s kurzorom->. To je pomlčka a potom väčšia ako znak, tak aby sa šípkou. Kurzor-> next. To bude skutočne vám uzol, ktorý sa kurzor ukazuje. Táto hodnota je o ďalšie. Takže namiesto toho, aby na hviezdičku a bodku, budete nahrádzať, že sa šípkou. Buďte veľmi opatrní, aby sa ubezpečil, že sa pokúsite použiť túto syntax. 

Teraz, keď máme kurzor, ak chceme, aby prístup k hodnote, predtým, sme mali kurzor-> next, ale pre prístup k hodnote na uzla, ktorý kurzor ukazuje na, sme jednoducho povedať node-> hodnota. Odtiaľ je to na dátový typ, čo sme definovali hodnoty a uzlov byť. Ak je to int uzol, potom kurzor-> hodnota je len bude číslo. Takže môžeme urobiť operácie na to, pozrite sa rovnosťou, priradiť jej rôzne hodnoty, atď Takže to, čo chcete robiť, keď chcete presunúť kurzor na ďalšiu osobu, môžete skutočne zmeniť hodnotu kurzora. Vzhľadom k tomu, kurzor je uzol ukazovateľ, môžete zmeniť aktuálnu adresu ukazovateľ na adresu ďalšieho uzla v zozname. To je len nejaký kód, kde by ste mohli iterácii. Kde mám komentár niečo urobiť, to, kde ste pravdepodobne bude prístup k hodnote alebo niečo do činenia s týmto konkrétnym uzla. Ak chcete začať ho, hovorím, že môj kurzor pôvodne bude ukazovať na prvý prvok v prepojenom zozname. A tak sa pred nami, som definoval to ako hlava uzla. 

Ako som už spomenul skôr, uvoľňovať je naozaj dôležité. Chcete, aby sa ubezpečil, že ste uvoľniť každý prvok v zozname, akonáhle ste skončil s ním. Keď nemusíte odkazovať niektoré z týchto ukazovateľov už, chcete, aby sa ubezpečil, že ste oslobodiť všetky tieto ukazovatele. Ale vy chcete byť veľmi opatrní v tom, že budete chcieť, aby sa zabránilo pretečeniu pamäte. Ak si zadarmo jeden človek predčasne, potom všetky ukazovatele, ktoré tento uzol odkazuje na sa bude stratená. Vráťme sa späť k osobe príklad, aby bolo trochu viac high stakes, poďme si týchto ľudí, s výnimkou v tomto prípade, že sa vznášajú nad jazerom s monštrom. Chceme sa uistiť, že vždy, keď sme uvoľnení, aby sme nestratili a pustil všetky uzly, ako sme v skutočnosti je oslobodil. Napríklad, ak ste boli jednoducho volať zadarmo na toho chlapa tu, potom by bola uvoľnená, ale potom všetky tieto ľudí by potom dôjsť k strate a oni by zaspať a spadnúť. Takže chceme, aby sa ubezpečil, že miesto, chceme zachovať odkaz na zvyšok. Naša hlava ukazovateľ, ktorý ukazuje na prvý prvok v zozname. Je to niečo ako lano kotevné prvej osobe. Čo budete chcieť robiť, keď ste uvoľnenie zoznam je mať - Ak chcete, aby sa uvoľnil prvý prvok prvý, potom môžete mať dočasný ukazovateľ že poukazuje na akýkoľvek prvý prvok je. Takže máte váš dočasný ukazovateľ tu. Tak, máme držať prvého uzla. A potom, pretože vieme, že prvý uzol bude oslobodený, potom môžeme presunúť lano, tento kotevné, naše hlavy, skutočne poukazujú na čokoľvek prvý ukazuje. Tak toto hlava skutočne odkazuje na druhý prvok teraz. Teraz sa môžu uvoľniť, čo je uložené v teplote, a tak sa môže odstrániť, že bez nej ohrozenia všetkých ostatných uzlov v našom zozname. Ďalším spôsobom, že by ste mohli urobiť to mohlo byť zakaždým, keď stačí uvoľniť posledný prvok v zozname pretože oni zaručené, že sa ukázal na čokoľvek. Takže vy ste mohli len uvoľniť tento, potom voľný tentoraz, potom bez tentoraz. To určite funguje, ale je trochu pomalší, pretože podľa povahy prepojených zoznamov, môžeme nielen okamžite skočiť do posledného. Musíme prejsť každý prvok v pripojenom zozname a skontrolujte, či že jeden ukazuje na NULL, skontrolujte zakaždým, a potom ešte raz dôjdeme na koniec, potom zadarmo, ktoré. Ak by ste mali urobiť tento proces, by si skutočne byť kontrola tu, kontrola tu, potom kontrola tu, uvoľňovať to, potom ísť späť, kontrola tu, kontrola tu, uvoľňovať to, kontrola tu, a potom uvoľňovať to. To si vyžaduje trochu viac času. Jo. 

[Študent] Bolo by možné, aby sa spájať zoznam, ktorý ukladá návratový ukazovateľ na koniec? To by určite bolo možné. Ak chcete zopakovať otázku, je možné mať prepojenú zoznam štruktúru tak, že si mať ukazovateľ smerujúce do konca prepojeného zoznamu? Povedal by som, že je to možné, a zakaždým, keď vložíte niečo do prepojeného zoznamu budete musieť aktualizovať tento ukazovateľ a podobné veci. Tie by mali uzla * chvost, napríklad. Ale keď ste vykonávanie tejto funkcii, musíte myslieť na kompromisov, Páči koľkokrát budem sa iterácia nad tým, ako ťažké ich bude sledovať z chvosta, rovnako ako hlava rovnako ako môj Iterator, a podobné veci. Znamená to, že -? >> [Študent] Jo. Je to možné, ale pokiaľ ide o návrhu rozhodnutia, budete musieť zvážiť možnosti. 

Tu je kostra kódu, ktorý by vám umožní uvoľniť každý prvok prepojeného zoznamu. Opäť, pretože som iterácie previazanom zoznamu, budem chcieť mať nejaký kurzora alebo Iterator. Sme iterácií, kým kurzor NULL. Nechcete, aby iterácii, kedy je kurzor na NULL pretože to znamená, že nie je nič v zozname. Takže tu som vytvoriť dočasnú uzla * poukazuje na to, čo som za zváženie, je prvý z môjho zoznamu, a potom som pohnúť kurzorom dopredu 1 a potom voľný, čo som mal v režime dočasného uskladnenia. 

Teraz sa dostávame k vloženiu do prepojených zoznamov. Mám tri uzly v mojej prepojeného zoznamu, a poďme sa jednoduchom prípade tam, kde chceme vložiť ďalšie uzol na konci nášho prepojeného zoznamu. K tomu, všetko, čo bude robiť je, že sme sa prejsť zistiť, kde prúd koniec prepojeného zoznamu je, tak podľa toho, uzol ukazuje na NULL - že je to jedno - a potom povedať, vlastne, toto je nebude posledný uzol; sme vlastne bude mať inú. Takže budeme mať tento súčasný jeden bod k tomu, čo sme vkladanie. Takže teraz to červené osoba tu stáva posledný uzol v prepojenom zozname. A tak charakteristický posledného uzla v prepojenom zozname je, že sa poukazuje na NULL. Takže to, čo by sme mali urobiť, je nastaviť túto červenú chlapa ukazovateľ na NULL. Tam. 

Ale čo keď chceme vložiť uzol medzi druhým a tretím jeden? To človek nie je tak jednoduché, pretože chceme, aby sa ubezpečil že nepúšťaj žiadneho uzla v našej prepojeného zoznamu. Čo by sme mali urobiť, je uistiť, že sme ukotviť, aby sme sa každé z nich. Napríklad, povedzme túto druhú možnosť. Ak ste povedal druhý teraz ukazuje na túto novú a ste práve urobil ukazovateľ tam, potom by to bolo za následok ten chlap strate pretože tam nie je žiadny odkaz na neho. Namiesto toho - budem kresliť to znova. Ospravedlňte moje umelecké schopnosti. Vieme, že nemôžeme len tak priamo pripojiť 2 do nového. Musíme sa uistiť, že sme sa držať na posledný. Čo by sme mohli chcieť urobiť, je mať dočasný ukazovateľ na prvok, ktorý ich bude pripojená na. Takže máme dočasný ukazovateľ tam. Pretože vieme, že to tretie je držaný sledovať, 2 môže teraz prepojiť do nášho nového. A ak táto nová červená chlap bude medzi 2 a 3, potom to, čo je ten chlap je ukazovateľ bude ukazovať na? >> [Študent] Temp. Temp. Jo. Takže táto červená chlap ďalšie hodnota bude tepl. Keď ste vložením do prepojených zoznamov, videli sme, že by sme mohli ľahko pridať niečo do konca vytvorením dočasnej poľa, alebo ak sme chceli pridať niečo do stredu nášho poľa, potom by to trvať trochu viac prešľapuje. Ak chcete, napríklad, majú zoradená prepojeného zoznamu, potom sa budete musieť trochu zvažovať náklady a prínosy, ktoré pretože ak chcete mať zoradené poľa, to znamená, že zakaždým, keď vložíte do neho, to bude trvať trochu dlhšie. Avšak, ak chcete, aby neskôr, až nájdeme budeme chcieť, Hľadanie pomocou prepojeného zoznamu, potom to môže byť jednoduchšie, ak budete vedieť, že je všetko v poriadku. Takže možno budete chcieť zvážiť náklady a prínosy, ktoré. 

Ďalším spôsobom, ako vložiť do prepojeného zoznamu je vložiť do začiatku zoznamu. Ak čerpáme kotvu tu - to je naša hlava - a potom títo ľudia s ňou súvisí, a potom máme nový uzol má byť vložená do začiatku, potom to, čo by sme mohli chcieť urobiť? Aký by mal byť v poriadku s len hovorím chcem prepojiť červenej k modrej, pretože to je prvý? Čo by sa stalo tu? Všetky z týchto troch by stratiť. Takže nechceme urobiť. Opäť sme sa dozvedeli, že musíme mať nejaký druh dočasného ukazovatele. Poďme si vybrať na dočasnú dobu bod na toho chlapa. Potom môžeme mať modrú jeden bod k tomu dočasné a potom červený bod na modrej. Dôvodom, prečo som využívala ľudí tu je, pretože my naozaj chceme vizualizovať drží na ľudí a uistiť sa, že máme odkaz na ne pred pustíme iného ruky alebo niečo také. 

Teraz, keď máme pocit lineárnymi zoznamy - ako by sme ich mohli vytvoriť odkazovaný zoznam a vytvoriť štruktúry pre ktoré sa skladá z definície typu pre uzol a potom uistiť sa, že máme ukazovateľ na hlave toho prepojeného zoznamu - akonáhle budeme mať to a vieme, ako prejsť cez pole, prístup k jednotlivým prvkom, vieme, ako vložiť a my vieme, ako sa oslobodiť, potom sa môžeme dostať do preklepy. Ako obvykle, máme časť otázok, na ktoré sa vám slúži k prevádzke s prepojenými zoznamy a rôzne štruktúry ako sú napríklad frontu a komínov. Potom sa môžeme presunúť do preklepy. 

Pravopisné chyby sa v distribučnej kóde niekoľko súborov významu. Najprv sme si všimli, že máme túto Makefile tu, ktoré sme naozaj nestretol. Ak ste sa pozreli dovnútra pset5 zložky, tak zistíte, že máte. H súbor, potom máte dve. C súbory. Čo to robí, je Makefile predtým, by sme stačí napísať make a potom názov programu a potom by sme videli všetky tieto argumenty a vlajok odovzdané do kompilátora. Čo Makefile robí, je nám umožňuje zostaviť niekoľko súborov naraz a odovzdať vlajok, ktoré chceme. Tu sme len vidieť, že je súbor hlavičke tu. Potom sme vlastne dva zdrojové súbory. Máme speller.c a dictionary.c. Ste vítaní upraviť Makefile ak si budete priať. Všimnite si, že tu, ak zadáte čistý, potom to, čo robí, je v skutočnosti odstraňuje niečo že je jadro. Ak máš Segmentation fault, v podstate máte core dump. Tak to škaredý malý súbor sa zobrazí vo vašom adresári s názvom core. Budete chcieť odobrať, že aby bolo čistenie. To odstráni všetky spustiteľné súbory a Súbory o 

Poďme sa pozrieť do dictionary.h. To hovorí, že to deklaruje slovníka funkčnosť. Máme maximálnu dĺžku pre ľubovoľné slovo v slovníku. Povieme, že je to bude najdlhšia slovo. Je to dĺžky 45. Takže my nebudeme mať žiadne slovo, ktoré presahujú túto dĺžku. Tu musíme len funkčné prototypy. Nemáme vlastnú realizáciu, pretože to je to, čo budeme robiť v tomto PSet. Ale čo to robí, je, pretože máme čo do činenia s väčšími súbormi tu a funkčnosť vo väčšom meradle, je užitočné mať. h súbor tak, že niekto iný čítať, alebo pomocou kódu nemôže pochopiť, čo sa deje. A možno, že chcú zaviesť pokúsi, ak ste hash tabuľky alebo naopak. Potom by povedali mi zaťaženie funkcie, Vlastná realizácia bude líšiť, ale tento prototyp nebude meniť. Tu sme zistiť, ktorá vracia true, ak dané slovo v slovníku. Potom máme zaťaženia, ktorá v podstate trvá do slovníka súboru a potom načíta do nejakej dátovej štruktúry. Máme veľkosť, ktorá, ak je volaná, vracia veľkosť vášho slovníka, koľko slov sú uložené v nej, a potom uvoľnite, ktoré uvoľní všetku pamäť, ktorú možno vziať do a pritom svoj slovník. 

Poďme sa pozrieť na dictionary.c. Je vidieť, že to vyzerá veľmi podobne ako dictionary.h, s výnimkou teraz to jednoducho má všetky tieto todos v ňom. A tak to je vaša práca. Nakoniec, budete vyplňovať speller.c so všetkými tohto kódu. Dictionary.c, pri spustení, nie je naozaj nič robiť, takže sa pozrieme na speller.c vidieť skutočné vykonávanie kontroly pravopisu. Aj keď nie ste bude editovať žiadnu z tohto kódu, je dôležité prečítať, pochopiť, keď je zaťaženie nazýva, keď som volať kontrolu, len pochopiť, zmapovať to, ako funkcia pracuje. Vidíme, že je to kontrola správne použitie. V podstate, keď niekto beží pravopisu, znamená to, že je to voliteľný pre ne prejsť do slovníka súboru, pretože tam to bude predvolený slovník súboru. A potom sa musí prejsť v texte byť spell-skontrolovať. rusage zaoberá času, pretože časť tohto PSet ktoré budeme zaoberať neskôr nie je len dostať fungujúci spell-checker pracovné ale v skutočnosti dostať, aby to bolo rýchlo. A tak potom to je miesto, kde rusage sa príde dovnútra Tu vidíme prvý hovor s jedným z našich dictionary.c súborov, ktorý je zaťaženie. Load vracia true alebo false - true na úspech, false pri výpadku. Takže ak slovníka nie je vložený správne, potom speller.c vráti 1 a ukončite. Ale ak to robí záťaž správne, potom to bude pokračovať. Budeme pokračovať, a my vidíme nejaký súbor I / O tu, kde to bude rokovaní s otvorením textového súboru. Tu, čo to robí, je kúzlo-kontroluje každé slovo v texte. Takže to, čo speller.c robí tu je iterácie každého slova v textovom súbore a potom kontrola je v slovníku. Tu máme logickú chybne, že uvidíme, či kontrola vráti pravda alebo nie. Ak slovo je vlastne v slovníku, potom kontrola vráti true. To znamená, že slovo nie je chybne. Takže chybne by bolo falošné, a to je dôvod, prečo máme bang tam, indikácie. Držíme ďalej, a potom to sleduje, koľko slov s chybným pravopisom sú v súbore. To pokračuje ďalej a zavrie súbor. Potom tu, hlási, koľko chybne napísané slová, ktoré mal. To počíta, ako dlho to trvalo načítať slovník, Ako dlho to trvalo pozrieť sa na to, Ako dlho to trvalo vypočítať veľkosť, ktorá, ako budeme pokračovať, by malo byť veľmi malé, a potom ako dlho to trvalo vyložiť slovník. Tu hore vidíme výzvu, aby ste si vyložili tu. Ak by sme skontrolovať veľkosť tu, potom vidíme, že je tu výzva k veľkosti, kde sa určuje veľkosť slovníka. Awesome. 

Našou úlohou pre túto PSet je implementovať zaťaženie, ktoré načíta slovník Dátová štruktúra - podľa toho, čo si vyberiete, či už je to hash tabuľka alebo skúsiť - so slovami zo slovníka súboru. Potom máte veľkosť, ktorá vráti počet slov v slovníku. A ak sa rozhodnete zaťaženie v inteligentným spôsobom, potom veľkosť by mala byť celkom jednoduché. Potom ste zistiť, ktorý bude či dané slovo v slovníku. Takže speller.c prechádza v reťazci, a potom sa budete musieť skontrolovať, či reťazec je obsiahnutý vo vašej slovníku. Všimnite si, že vo všeobecnosti majú štandardné slovníky, ale v tomto Pset, v podstate akékoľvek slovník prešiel v ktoromkoľvek jazyku. Takže nemôžeme len predpokladať, že slovo je vnútri. Slovo foobar mohla byť definovaná v istom slovníku, ktorý míňame dovnútra A potom sme vyložiť, ktorá oslobodzuje slovník z pamäte. 

Najprv by som chcel ísť cez hash tabuľky metódy o tom, ako by sme mohli implementovať všetky z týchto štyroch funkcií, a potom pôjdem cez snaží metódy, ako vykonávať tieto štyri funkcie, a na konci rozhovoru o niektorých všeobecných tipov, keď ste robiť PSet a tiež, ako by ste mali byť schopní používať Valgrind pre kontrolu únikov pamäte. 

Poďme do hash tabuľky metódou. Hash tabuľka obsahuje zoznam segmentov. Každá hodnota, každé slovo, je ísť do jedného z týchto segmentov. Hash table ideálne rovnomerne distribuuje všetky tieto hodnoty, ktoré ste mimochodom v a potom vyplní ich do vedra tak, že každá lopata má asi rovnaký počet hodnôt v ňom. Štruktúra tabuľky hash, máme rad prepojených zoznamov. Čo máme urobiť, je, keď sme sa prejsť v hodnote, môžeme skontrolovať, kde táto hodnota by mala patriť, ktoré vedro patrí, a umiestnite ho do prepojeného zoznamu spojené s týmto lopatou. Tu, čo mám, je hash funkcie. Je to int hash tabuľky. Takže pre prvého segmentu, všetky celé čísla pod 10 ísť do prvého segmentu. Akékoľvek celé čísla nad 10, ale nižšia ako 20 zaobchádzajú do druhej, a potom sa tak ďalej a tak ďalej. Pre mňa, každý vedro zastupuje tieto čísla. Avšak, povedať, že som bol prejsť v 50, napríklad. Zdá sa, že prvé tri obsahujú rad desiatich čísel. Ale ja chcem, aby moje hash tabuľky, aby sa v nejakom druhu celých čísel, tak potom budem musieť odfiltrovať všetky čísla nad 30 do posledného segmentu. A tak potom by to mať za následok akési nevyvážené hash tabuľky. Ak chcete zopakovať, hash tabuľka je len rad lopát kde každý vedro je previazaný zoznam. A tak sa určiť, kde každá hodnota ide, čo vedro to ide do, budete chcieť, čo sa nazýva hash funkcie že vezme hodnotu a potom hovorí táto hodnota zodpovedá určitej nádoby. Takže hore v tomto príklade, moja hashovacie funkcie sa každú hodnotu. Je kontrolované, či to bolo menej ako 10. Ak to bolo, to by dať do prvého segmentu. Skontroluje, či je to menej ako 20, dá to do druhého, ak platí, kontroluje, či je to menej ako 30, a potom ju umiestni do tretieho vedra, a potom všetci ostatní len patrí do štvrtej vedra. Takže zakaždým, keď majú hodnotu, vaše hashovacie funkcie bude klásť túto hodnotu do príslušného vedra. Hashovacie funkcie v podstate potrebuje vedieť, koľko vedierka máte. Vaša veľkosť hash tabuľky, počet segmentov, ktoré máte, že to bude pevné číslo, ktoré je na vás, pre vás sa rozhodnúť, ale to bude stanovený počet. Takže vaše hash funkcie bude spoliehať na to určiť, ktorý lyžice každý kľúč ide do také, že je to rovnomerne. Podobne ako naše vykonávanie súvisiacich zoznamov, teraz každý uzol v hash tabuľke bude skutočne mať typu char. Takže máme char pole s názvom Slovo a potom ešte ukazovateľ na ďalší uzol, čo dáva zmysel, pretože to bude spájať zoznam. Pamätáš, keď sme sa spojil zoznamy, urobil som uzla * s názvom hlava ktorý bol s poukazom na prvom uzla v prepojenom zozname. Ale pre naše hash tabuľky, pretože máme niekoľko prepojených zoznamov, to, čo chceme, je chceme, aby náš hash table byť ako, "Čo je to vedro?" Lopata je len zoznam uzlov ukazovateľov, a tak každý prvok v segmente je vlastne ukazuje na jeho zodpovedajúce prepojeného zoznamu. Ak sa chcete vrátiť k tomuto schémy, uvidíte, že vedierka samotné sú šípky, nie skutočné uzly. Jednou zo základných vlastností hašovacia funkcia je, že sú deterministické. To znamená, že ak ste hash číslo 2, by mal vždy vrátiť rovnaký vedro. Každý hodnota, ktorá ide do hash funkcie, ak by sa opakovali, musí dostať rovnaký index. Takže vaše hash funkcia vracia index poľa kde táto hodnota patrí. Ako som už spomenul predtým, je stanovená počet segmentov, a tak si index, ktorý sa vrátiť musí byť menšia, než je počet segmentov ale väčšie ako 0. Dôvodom, prečo sme hašovacia funkcia miesto len jednej prepojeného zoznamu alebo jeden jediný pole je to, že chceme byť schopný skočiť do určitej časti najľahšie ak poznáme charakteristiku hodnoty - namiesto toho, aby museli prehľadávať celého slovníka, budú môcť prejsť na určité časti nej. Váš hash funkcia by mala brať do úvahy, že v ideálnom prípade, Každý vedro má približne rovnaký počet kľúčov. Vzhľadom k tomu, hash tabuľka je séria spojených zoznamov, potom spojené zoznamy sami budú mať viac ako jeden uzol. V predchádzajúcom príklade, dve rôzne čísla, aj keď neboli rovnaké, keď rozhádzané, vráti rovnaký index. Takže keď máte čo do činenia so slovami, jedno slovo, keď klasifikácii by byť rovnaká hodnota mriežky ako iné slovo. To je to, čo nazývame kolízii, keď máme uzol, ktorý, keď rozhádzané, spájať zoznam v tomto segmente nie je prázdny. Technika, ktorá nazývame je lineárne snímanie, kde idete do prepojeného zoznamu a potom nájsť miesto, kde chcete vložiť tento uzol pretože máte kolízii. Môžete vidieť, že tam by mohlo byť trade-off, že jo? Ak máte veľmi malú hash tabuľky, veľmi malý počet segmentov, potom budete mať veľa kolízií. Ale potom, ak urobíte veľkú hash tabuľky, budete pravdepodobne k minimalizácii kolízií, ale to bude veľmi veľké dátové štruktúry. Tam to bude kompromisy s tým. Takže keď ste vykonali PSet, skúste sa pohrať medzi možná robiť menšie hash tabuľky ale potom s vedomím, že to bude trvať trochu dlhšie prechádzať jednotlivé prvky z týchto prepojených zoznamov. 

Čo zaťaženie sa chystá urobiť, je iterácii každé slovo v slovníku. To prejde ukazovateľ na súbor slovníka. Takže budete využívať súboru I / O funkcií, ktoré ovládajú v pset4 a iteráciu každé slovo v slovníku. Ak každé slovo v slovníku, aby sa stal nový uzol, a budete umiestniť každý z týchto uzlov vnútri vášho slovníka dátové štruktúry. Kedykoľvek dostanete nové slovo, viete, že to bude stáť uzol. Takže môžete ísť hneď a malloc uzla ukazovateľ pre každú novú slovo, ktoré ste. Tu som volá moje uzla ukazovateľ new_node a ja mallocing čo? Veľkosť uzla. Potom si prečítať aktuálne reťazec zo súboru, pretože slovník je v skutočnosti uložená slovom a potom nový riadok, čo môžeme využiť je funkcia fscanf, pričom súbor je slovník súbor, ktorý sme prešiel v roku, tak to skenuje súbor pre reťazce a miesta, ktoré reťazec do posledného argumentu. Ak si spomeniete, späť k jednému z prednášok, keď sme išli cez a druh lúpané vrstvy späť na knižnici CS50, Videli sme implementáciu fscanf tam. Ak sa chcete vrátiť do fscanf, máme súbor, ktorý sme čítanie z, hľadáme pre reťazec v tomto súbore, a potom sme uvedení do tu mám new_node-> slovo, pretože new_node je uzol ukazovateľ, nie je aktuálny uzol. Takže hovorím new_node, chcem ísť do uzla, že to ukazuje na a potom priradiť túto hodnotu na slovo. Chceme, aby potom toto slovo a vložte ho do hash tabuľky. Uvedomte si, že sme urobili new_node uzla ukazovateľ pretože budeme chcieť vedieť, čo adresa tohto uzla je keď sa vložiť do preto, že štruktúra uzlov samotných, v struct, je to, že majú ukazovateľ na nový uzol. Takže to, čo je adresa tohto uzla ísť poukázať na? Táto adresa bude new_node. Dáva to zmysel, prečo robíme new_node uzla * na rozdiel od uzla? Dobre. Máme slovo. Táto hodnota je new_node-> slovo. , Ktorý obsahuje slovo zo slovníka, ktoré chceme na vstup. Takže to, čo chceme urobiť, je chceme nazývať našu hash funkcie na tomto reťazci pretože naše hash funkcie má v reťazci a vráti nám celé číslo, kde, že číslo je index, kde Hashtable v tomto indexe predstavuje tento vedro. Chceme, aby sa tento index a potom ísť do toho indexu hash tabuľky a potom použiť tento spájať zoznam pre vloženie uzla na new_node. Pamätajte si, že sa však sa rozhodnete vložiť svoje uzol, či už je to v stredu, ak chcete radiť ho alebo na začiatku alebo na konci, len sa uistite, že vaša posledná uzol vždy ukazuje na NULL pretože to je jediný spôsob, ako vieme, kde posledný prvok nášho prepojeného zoznamu je. 

Ak je veľkosť celé číslo, ktoré predstavuje počet slov v slovníku, potom jeden spôsob, ako to urobiť, je to, že vždy, keď sa nazýva veľkosť prejdeme každý prvok v našej hašovacia tabuľke a potom určiť iteráciou každého prepojeného zoznamu v hash tabuľke a potom vypočítať dĺžku, že zvýšenie našej čítač 1 do 1. Ale zakaždým, keď veľkosť sa nazýva, že to bude trvať dlho pretože budeme mať lineárne snímanie každý spájať zoznam. Namiesto toho, to bude oveľa jednoduchšie, ak budete mať prehľad o tom, koľko slov sú odovzdávané palcov Takže ak ste napríklad počítadlo priamo vo Vašom zaťaženie funkcie to, že aktualizácia je to potrebné, potom čítač, ak ju nastaviť na globálne premenné, budú môcť byť prístupné veľkosti. Takže to, čo veľkosť by jednoducho urobiť, je v jednej línii, stačí sa vrátiť hodnotu čítača, veľkosť slovníka, ktorý ste už zaoberal v zaťažení. To je to, čo som mal na mysli, keď som hovoril, že keď sa rozhodnete zaťaženie v užitočné spôsobom, potom veľkosť bude celkom jednoduché. 

Takže teraz sme si to overiť. Teraz máme čo do činenia so slovami zo súboru vstupného textu, a tak budeme mali overovať, či všetky tie vstupných slov sú vlastne v slovníku, alebo nie. Podobne ako Scramble, chceme, aby pre prípad necitlivosti. Chcete, aby sa ubezpečil, že všetky slová prešiel v roku, aj keď sú zmiešaný prípad, pri volaní sa sláčikovým porovnanie, sú rovnocenné. Slová v súboroch slovníka textového sú vlastne všetci malá. Ďalšia vec je, že môžete predpokladať, že každé slovo prešiel v roku, každý reťazec, sa bude buď v abecednom alebo obsahujú apostrofy. Apostrofy sa bude platné slová v našom slovníku. Takže ak máte slovo s apostrof S, to je skutočný legitímny slovo vo vašom slovníku že to bude jeden z uzlov vo vašom tabuľky hash. Kontrola pracuje s ak slovo existuje, potom to musí byť v našej hašovacia tabuľke. Ak je slovo v slovníku, potom všetky slová v slovníku, sú v hash tabuľke, tak sa poďme pozrieť na tohto slova v hash tabuľke. Vieme, že od tej doby sme realizovali náš hash funkcie tak, že každá jedinečná slovo vždy klasifikované na rovnakú hodnotu, potom vieme, že miesto prehľadávanie nášho celého hash tabuľky, môžeme skutočne nájsť prepojený zoznam, ktorý toto slovo by malo patriť k Ak to bolo v slovníku, potom by to bolo v tomto bloku. Čo môžeme robiť, keď slovo je názov nášho reťazca prešiel v, môžeme len hash, že slovo a pohľad na prepojenom zoznamu pri hodnote Hashtable [hash (slovo)]. Odtiaľ, čo môžeme urobiť, je, že sme menší podmnožinu uzlov pre vyhľadávanie tohto slova, a tak môžeme prejsť prepojeného zoznamu, na príklade z predtým v návode, a potom volať reťazec nákupný na slovo všade tam, kde je kurzor ukazuje na, to slovo, a zistiť, či sú tieto. V závislosti na spôsobe, akým ste organizovať svoj hash funkcie, ak je to zoradená, mali by ste byť schopní vrátiť false niečo skôr, ale ak je to netriedený, potom budete chcieť pokračovať kríženia cez prepojeného zoznamu kým nenájdete posledný prvok zoznamu. A ak ste ešte nenašli slovo v čase, keď ste dosiahli konca prepojeného zoznamu, to znamená, že vaše slovo neexistuje v slovníku, a tak to slovo je neplatný, a kontrola by mal vrátiť false. 

Teraz sa dostávame k uvoľneniu, kde chceme oslobodiť všetky uzly, ktoré sme malloc'd, tak bez všetkých uzlov vnútri nášho stola mriežky. Budeme chcieť, aby iteráciu cez všetky prepojených zoznamov a zdarma všetky uzly v tom. Ak sa pozriete vyššie v návode na príklade, kde sme uvoľniť prepojeného zoznamu, potom budete chcieť zopakovať tento proces pre každý prvok v hash tabuľke. A ja budem ísť cez tento na konci návodu, ale Valgrind je nástroj, kde môžete vidieť, ak ste správne oslobodil každý uzol, ktorý ste malloc'd alebo čokoľvek iné, čo ste malloc'd, iné ukazovateľ. Tak to je hashovacie tabuľky, kde máme konečný počet segmentov a hash funkcie, ktorá bude mať hodnotu a potom priradiť túto hodnotu do určitej vedra. 

Teraz sa dostávame k pokusoch. Pokúsi druh vyzerajú takto, a ja tiež čerpať z príkladu. V podstate, máte celý rad potenciálnych listov, a potom kedykoľvek budete budovať slovo, že list môže byť spojené za slovníku na širokú škálu možností. Niektoré slová začať s C, ale potom pokračovať s, ale iní pokračujú s O, napríklad. Trie je spôsob vizualizácie všetkých možných kombinácií týchto slov. Trie sa bude sledovať sledu písmen, ktoré tvoria slová, odbočenie ak je to potrebné, keď je jedno písmeno nasledovať násobok písmen, a na konci uviesť v každom bode, či tento výraz je platná alebo nie pretože ak ste hláskovať slovo MAT, MA nemyslím si, že je platný slovo, ale MAT je. A tak v trie, by to znamenať, že po MAT, že je to vlastne platné slovo. Každý uzol v našom trie je vlastne bude obsahovať množstvo uzlov ukazovateľov, a budeme mať, konkrétne 27 z týchto uzlov ukazovateľov, jeden pre každé písmeno v abecede, rovnako ako Apostrof. Každý prvok v tomto poli je samo o sebe bude ukazovať do iného uzla. Takže, ak tento uzol je NULL, v prípade, že je to nič po tom, potom vieme, že tam žiadne ďalšie písmená v tomto slove poradí. Ale ak tento uzol nie je NULL, znamená to, že existuje viac písmen v tomto liste poradí. A potom ďalej, každý uzol označuje, či je to posledný znak slova, alebo nie. 

Poďme do príklade trie. Najprv som mať priestor pre 27 uzlov v tomto poli. Ak mám slovo BAR - Ak mám slovo BAR a chcem vložiť, že v, prvé písmeno je B, takže ak má trie je prázdny, B je druhé písmeno v abecede, takže budem voliť, aby to tu v tomto indexe. Budem mať B tu. B bude uzol, ktorý ukazuje na iného pole všetkých možných znakov že môže nasledovať po písmenom B. V tomto prípade, sa zaoberám slovom BAR, takže pôjdu sem. Po, mám list R, tak potom teraz ukazuje na vlastnú kombináciu, a potom R bude tu. BAR je úplné slovo, takže potom budem mať R bod do iného uzla , Ktorý hovorí, že toto slovo je platné. To je uzol tiež bude mať rad uzlov, ale tie by mohli byť NULL. Ale v podstate, môže pokračovať takhle. To bude trochu jasnejší, keď sme išli do iného príkladu, takže stačí mať so sebou tam. Teraz máme BAR vnútri nášho slovníka. Teraz, že máme slovo Baz. Začneme s B, a už máme B ako jeden z listov, ktoré v našom cenníku. To je nasledoval s A. Máme už. Ale potom miesto, máme Z nasledujúcej. Takže prvkom v našom poli sa bude Z, a tak, že jeden potom bude poukázať na inú platnú koniec slova. Takže vidíme, že keď budeme pokračovať cez B a potom, existujú dve rôzne možnosti v súčasnej dobe v našom slovníku pre slová, ktoré začínajú B a A. Povedzme, že by sme chceli vložiť slovo foobar. Potom by sme urobiť vstup na F. F je uzol, ktorý ukazuje na celú radu. Radi by sme vás O, choďte na O, O a potom spája do celého zoznamu. Mali by sme B a potom pokračovať, mali by sme a potom R. Takže foobar prechádza celú cestu dole, kým foobar je správne slovo. A tak potom by to bolo platné slovo. Teraz hovoria, naše ďalšie slovo v slovníku je vlastne slovo FOO. Mali by sme povedať, F. Čo bude nasledovať, F? Vlastne som už priestor pre O, takže budem pokračovať. Nepotrebujem, aby sa nový. Pokračovať. FOO je platná slovo v tomto slovníku, tak potom budem uvádzať že je platná. Keby som prestala som sekvenciu tam, to by bolo správne. Ale ak sme pokračovali v poradí od FOO až B a proste musel FOOB, FOOB nie je slovo, a to nie je uvedené ako platnú. V trie, ste každý uzol označujúci, či je to platné slovo, alebo nie, a potom každý uzol má aj rad 27 uzla ukazovateľov , Ktoré potom prejdite na uzly samotných. 

Tu je spôsob, ako na to, ako budete chcieť definovať to. Avšak, rovnako ako v hash tabuľke príklade, kde sme mali uzla * hlavu na označenie začiatku nášho prepojeného zoznamu, budeme tiež chcieť nejaký spôsob, ako vedieť, kde je počiatok nášho trie je. Niektorí ľudia hovoria, sa snaží stromy, a to je miesto, kde koreň pochádza. Takže chceme koreň nášho stromu, aby sa ubezpečil, že sme zostať uzemnený tam, kam naše trie je. Už sme trochu prešiel ako by ste mohli premýšľať o nakladaní každé slovo do slovníka. V podstate, pre každé slovo budete chcieť určiť iteráciou svojho trie a vedel, že každý prvok u detí - hovorili sme, že deti v tomto prípade - zodpovedá iným písmenom, budete chcieť skontrolovať tieto hodnoty v tomto konkrétnom indexe, ktorý zodpovedá písmeno. Takže myslieť celú cestu späť k Caesarovi a Vigenère, s vedomím, že každý list si môžete druh mapy späť na index abecedy, Rozhodne až Z bude celkom jednoduché mapovať abecedný list, ale bohužiaľ, apostrofy sú tiež prijímaný znak v slovách. Nie som si ani istý, čo ASCII hodnota je, tak na to, ak chcete nájsť index rozhodnúť, či chcete, aby to bolo buď prvý alebo posledný, budete musieť pevný kódované šek na ktoré a potom dať, že v indexe 26, napríklad. Takže potom ste kontrolou hodnoty u detí [i] kde [i] odpovedá na čokoľvek písmeno ste na. Ak je to NULL, to znamená, že nie je v súčasnej dobe prípadné listy vyplývajúce z predchádzajúceho sekvencie, takže budete chcieť malloc a vytvoriť nový uzol a mať deti, že [i] prejdite na ňu takže môžete vytvoriť - keď sme vložili list do obdĺžnika - Vďaka deťom non-NULL a bod do tohto nového uzla. Ale ak to nie je NULL, ako v našom prípade z FOO keď už sme mali foobar, budeme pokračovať, a my sa nikdy robiť nový uzol, ale len nastaviť is_word na hodnotu true Na konci tohto slova. 

Takže rovnako ako predtým, pretože tu máte čo do činenia s každým listom v čase, to bude pre vás jednoduchšie pre veľkosť, namiesto toho, aby výpočet a prejsť celý strom a vypočítať, koľko detí mám a potom odbočenie, spomenul koľko sú na ľavej strane a na pravej strane a podobné veci, to bude oveľa jednoduchšie pre vás ak ste práve sledovať, koľko slov ste tým, že do keď máte čo do činenia s nákladom. A potom sa to tak veľkosť môže len návrat globálne premenné veľkosti. 

Teraz sa dostávame k skontrolovať. Rovnakých štandardov ako predtým, kde chceme, aby pre prípad necitlivosti. Rovnako, my predpokladáme, že reťazce sú len abecedné znaky alebo apostrofy pretože deti je pole 27 dlhé, takže všetky písmená abecedy plus apostrof. Pre kontrolu toho, čo budete chcieť urobiť, je, že budete chcieť začať pri koreni pretože koreň bude ukazovať na pole, ktoré obsahuje všetkých možných východiskových písmen slova. Budeš začať tam, a potom budete kontrolovať, je táto hodnota NULL alebo nie, pretože ak je hodnota NULL, to znamená, že v slovníku nemá žiadne hodnoty ktoré obsahujú ten list v tomto konkrétnom poradí. Ak je to NULL, potom to znamená, že toto slovo je chybne hneď. Ale ak to nie je NULL, potom môžete pokračovať, povedať, že prvé písmeno je možné prvé písmeno v slove, tak teraz chcem skontrolovať, či druhý list, že sekvencie, je v mojom slovníku. Takže sa chystáte ísť do indexu deti na prvom uzle a skontrolujte, či druhý list existuje. Potom si opakovať, že proces skontrolovať, či postupnosť je platná alebo nie vo vašej trie. Kedykoľvek uzol deti na to, že indexových bodov na hodnotu NULL, Viete, že postupnosť neexistuje, ale potom, keď sa dostanete na koniec slova, ktoré ste vložili, potom chcete skontrolovať teraz, že som dokončil túto sekvenciu a zistil, že je v mojom trie, je to, že slovo platí, alebo nie? A potom sa budete chcieť skontrolovať, či, a to je, keď, ak ste zistili, že postupnosť, potom chcete skontrolovať, či slovo je platná alebo nie pretože Spomínam si v predchádzajúcom prípade, že som nakreslil, kde sme mali FOOB, , Ktorý bol platný sekvencie, ktoré sme našli, ale nebola skutočná platné slovo samo o sebe. 

Podobne, pre vyložiť v pokusoch, ktoré chcete uvoľniť všetky uzly vo vašom trie. Prepáčte. Podobne ako hash tabuľky, kde v vyložiť sme oslobodil všetky uzly, v pokusoch, ktoré chceme tiež uvoľniť všetky uzly. Uvoľniť bude skutočne fungovať najjednoduchšie zdola nahor pretože tieto sú v podstate spojené zoznamy. Takže chceme sa uistiť, že máme na všetky hodnoty a bez všetky z nich výslovne. Čo budete chcieť robiť, keď pracujete s trie je cestovať až na dno a voľný najnižšiu možnú uzol prvý a potom sa do všetkých týchto detí a potom bez všetkých tých, hore a potom zadarmo, atď Niečo ako zaoberajúca sa spodnou vrstvou trie prvý a potom ísť až hore, akonáhle ste oslobodil všetko. Toto je dobrý príklad, kde rekurzívne funkcie môže hodiť. Akonáhle oslobodil spodnú vrstvu vášho trie, potom volať vyložiť na to ostatné, Uistite sa, že ste uvoľniť každý mini - Môžete trochu predstaviť, že ako mini pokusov. Takže máte koreň tu. Ja len zjednodušiť tak, nemám k tomu 26 z nich. Takže budete mať tieto, a potom títo reprezentujú sekvencie slov kde všetky tieto malé kruhy sú listy, ktoré sú platné postupnosti písmen. Poďme pokračovať len trochu viac. Čo budete chcieť urobiť, je zadarmo spodnej tu a potom zadarmo tento a potom zadarmo to jeden na dne pred uvoľniť hornej jeden až sem pretože ak vás úplne zadarmo, niečo, čo v druhej úrovni tu, potom skutočne prídu túto hodnotu tu. To je dôvod, prečo je to dôležité v uvoľnenie pre trie, aby sa ubezpečil, že ste uvoľniť dno ako prvý. Čo budete chcieť urobiť, je povedať, pre každý uzol Chcem vyložiť všetky deti. 

Teraz, keď sme preč cez vyložiť na hash tabuľky metódy, ako aj spôsobu trie, budeme chcieť pozrieť na Valgrind. Valgrind spustiť s nasledujúcimi príkazmi. Máte Valgrind-V. Ste kontrola všetkých netesností pri spustení pravopisu, rovnako to určitý text pretože Speller potrebné, aby v textovom súbore. Takže Valgrind bude spustite program, povedať, koľko bytov si pridelené, koľko bytov si oslobodený, a to vám povie, či ste oslobodený len dosť alebo či ste to už dosť, alebo niekedy dokonca môžete cez-free, ako je voľný uzol, ktorý už bol oslobodený a tak sa vrátite chyby. Ak používate Valgrind, bude vám niektoré správy uvedie, či ste oslobodení buď menej než dosť, len dosť, alebo viac než dosť časov. 

Súčasťou tejto PSet, je to voliteľná napadnúť veľkú tabuľu. Ale keď máme čo do činenia s týmito dátovými štruktúrami je to celkom zábavné vidieť, ako rýchlo a ako efektívne vaše dátové štruktúry môže byť. Má vaše hash funkcie majú za následok veľa kolízií? Alebo je vaša veľkosť dát naozaj veľký? Má to trvať veľa času prejsť? V protokole o Speller, že výstupy, koľko času budete používať pre načítanie, kontrolovať, vykonávať veľkosti, a vyložiť, a tak tie sú uložené v The Big rade, kde môžete súťažiť proti svojim spolužiakom a niektorí zamestnanci sa vidieť, kto má najrýchlejší pravopisu. Jedna vec, že ​​by som chcel poznamenať, o hash tabuľky je to, že tam sú niektoré docela jednoduché hashovacie funkcie, ktoré by sme mohli myslieť. Napríklad, máte 26 vedrá, a tak každý vedro zodpovedá prvé písmeno v slove, ale že to bude mať za následok docela nevyvážené hash tabuľky pretože tam sú veľa menej slov, ktoré začínajú s X než štarte sa M, napríklad. Jeden spôsob, ako ísť o Speller je, ak chcete získať všetky ostatné funkcie dole, potom stačí použiť jednoduchý hash funkcie, aby mohli dostať váš kód beží a potom sa vrátiť späť a zmeniť veľkosť vašej hash tabuľky a definície. Existuje veľa zdrojov na internete pre hašovacia funkcia, a tak pre tento PSet je povolené výskum hash funkcie na internete o nejaké rady a inšpiráciu tak dlho, ako sa uistiť, citovať, kde ste získali. Rado sa stalo sa pozrieť a interpretovať niektoré hash funkcie, ktoré nájdete na internete. Späť na to, že môžete byť schopní zistiť, či niekto použil trie či je ich realizácia je rýchlejší ako váš hašovacia tabuľky alebo nie. Môžete predložiť veľkú tabuľu viackrát. To bude zaznamenávať vaše poslednú položku. Takže možno zmeníte funkciu hash a potom si uvedomí, že je to vlastne oveľa rýchlejšie alebo oveľa pomalší ako predtým. To je trochu zábavnou formou. Tam je vždy 1 alebo 2 zamestnanci, ktorí sa snažia, aby sa najpomalší možnú slovník, tak to je vždy zábavné sa pozerať na. 

Použitie pre PSet je spustiť pravopisu s voliteľným slovníka a potom povinný textový súbor. V predvolenom nastavení pri spustení pravopisu sa len textového súboru a neuvediete slovník, to bude používať slovník textový súbor, toho veľkého v cs50/pset5/dictionaries zložke. Že jeden má viac ako 100.000 slov. Majú tiež malý slovník, ktorý má podstatne menej slov že CS50 urobil pre vás. Avšak, môžete veľmi ľahko stačí si len vlastný slovník ak si len chcete pracovať v malých príkladoch - Napríklad, ak chcete použiť gdb a viete, že konkrétne hodnoty že chcete, aby vaše hash tabuľka mapuje na. Takže stačí vytvoriť svoj vlastný textový súbor len s barom, bázou, foo, a foobar, aby to v textovom súbore, oddeliť tie, každý s 1 riadok, a potom vytvoriť svoj vlastný textový súbor, ktorý doslova obsahuje len možno 1 alebo 2 slová takže presne viete, čo výstup by mal byť. Niektoré z ukážkových súborov textových, že Big Board pri spustení úlohy bude kontrolovať sú Vojna a mier a Jane Austen román alebo niečo také. Takže, keď ste začínal, je to oveľa jednoduchšie, aby vaše vlastné textové súbory ktoré obsahujú len pár slov alebo možno 10 takže môžete predvídať, čo výsledok by mal byť a overiť si to proti tomu, aby viac kontrolovanej príklad. A tak od tej doby máme čo do činenia s predpovedanie a kreslenie veci okolo, raz chcem povzbudiť, aby ste sa používať ceruzku a papier pretože je to naozaj ti pomôže s týmto - kreslenie šípok, ako hash tabuľka alebo ako sa vaše trie vyzerá, keď ste uvoľnenie niečo, kde sa šípky idete, sa držíš na dosť, vidíte nejaké odkazy mizne a pádu do priepasti unikli pamäte. Takže, prosím, skúste nakresliť veci ešte predtým, než sa dostanete na písanie kódu dole. Nakreslite veci tak, že ste pochopili, ako sa veci chodiť do práce pretože potom som zaručiť, že budete spúšťať do menej ukazovateľ muddles tam. 

Dobrá. Chcem vám popriať veľa šťastia s týmto PSet. Je to asi najťažšia. Tak skúste začať čoskoro, kresliť veci, kresliť veci, a veľa šťastia. To bolo Návod 5. 

[CS50.TV]