ZAMYLA Chan: Teeme õigekirjakontrolli. Kui avate speller.c, siis näete, et enamik funktsionaalsust kontroll tekstifaili vastu sõnastik on juba tehtud sinu jaoks. . / Speller, läbides sõnastik tekst faili ja siis teise tekstifaili kontrollib, et tekstifaili vastu sõnastik. 

Nüüd sõnastik tekstifaile sisaldab kehtivad sõnad, üks rea kohta. Siis speller.c kutsuvad Load sõnastiku tekstifaili. Ta helistab funktsioon nimega Saate kohta iga sõna sisestanud tekstifaili printimist kõik valesti sõnu. 

Speller.c ka helistada suurus kuni määrata sõnade arv sõnastik ja helistada mahalaadimine vaba mälu. speller.c ka jälgida, kui palju aega läbiviimiseks kasutati nende protsesse, kuid me saada hiljem. 

Mida me peame tegema? Me peame täitma dictionary.c. In dictionary.c meil abimees funktsiooni Load, mis laeb sõnastik. Funktsioon Kontrolli, mis kontrollib, kas antud sõna on sõnastikus. Funktsioon Suurus tagastab arvu sõnade sõnastik. Ja lõpuks oleme Eemalda, mis vabastab sõnastik mälust. 

Nii et esimene, olgem tegeleda Kandev. Iga sõna on sõnastikus tekst Faili Load salvestab need sõnad sõnastik andmestruktuur Teie valitud, kas hash tabelit või trie. Ma lähen üle nii Selle läbi kõndida. 

Kõigepealt räägime hash tabeleid. Ütle, et sul oli 10 piljardilauad pallid ja sa tahtsid need salvestada. Te võite panna need kõik kopp, ja kui teil on vaja konkreetseid numbriga kuuli, siis tahaks võtta ühe välja ämber korraga otsin seda palli. Ja ainult 10 kuule, siis peaks olema võimalik leida oma palli mõistlik ajaga. 

Aga mis siis, kui sa olid 20 palli? See võib võtta veidi aega nüüd. Aga 100? 1000? Nüüd oleks palju lihtsam kui teil oli mitu ämbrid. Võib-olla üks kopp kuuliga nulli läbi üheksa, teine ​​kopp kuuliga 10 kaudu 19, ja nii edasi. 

Nüüd, kui teil on vaja otsida konkreetseid ball, siis võiks automaatselt minge üks konkreetne kopp ja Otsige et kopp. Ja kui iga ämber on umbes 10 pallid, siis sa võiksid lihtsalt otsida läbi. 

Nüüd, kuna me tegeleme sõnastikud, ühe kopp kõik sõnad sõnastikku ilmselt liiga vähe ämbrid. Võtame pilk hash tabeleid. 

Mõtle seda massiivi ämbrid. Ja sel juhul, ämbrid on meie ahelloendid. Ja me jaotada kõik meie sõnad nende seas mitu ahelloendid sisse korraldatud viisil, kasutades räsifunktsiooni, mis ütleb meile, mis kopp antud võti, arvestades sõna kuulub. 

Olgem esindama seda skemaatiliselt. Blue siin kastid sisaldavad väärtusi ja red karbid punktist teise väärtus pointer paari. Me kutsume neid paari sõlmed. Nüüd iga ämber, nagu ma ütlesin varem, on seotud nimekirja. In ahelloendid iga sõlm on väärtus, samuti kursorit Järgmise väärtuse. 

Nüüd tegelevad seotud loendite see on väga tähtis, et te ei kaota lingid. Ja teine ​​fakt on meeles pidada, et viimase sõlme, kui ta ei osuta teine ​​lümfisõlm, juhib null. 

Niisiis, kuidas me esindame seda C? Me määratleda meie struct siin. Ja väärtus on sel juhul char massiiv pikkusega. Pikkus pluss 1, kus pikkus on maksimaalne pikkus iga sõna, pluss 1 null terminaator. Ja siis on meil viit teise sõlme nimetatakse Next. 

Seega teeme väikese seotud nimekirja. Esiteks, sa tahad malloc oma sõlme, mis loovad ruumi mälu suurust oma sõlme tüübist. Ja teha veel sõlme, jälle mallocing. 

Nüüd, kui soovite, et väärtustada sõna, siis võib öelda, node1 nool sõna võrdub "Tere." See nool operaator dereferences pointer ja juurdepääsude struct muutujate puhul. Nii, et me ei pea kasutama nii punkti ja tähe operaator. 

Nii siis on mul node2 nool sõna võrdub "Maailmas." Ja seal, väärtused asustatud minu sõlmed. Et lingid, ma läbima node1 noolt, tutvumise et sõlm star, et sõlm pointer, võrdub node2, juhtides node1 et node2 kaks. Ja seal on meil seotud nimekirja. 

Nii et oli lihtsalt üks seotud nimekirja, kuid hash tabel on terve rida ahelloendid. Noh, me peame sama sõlme struktureerida nii nagu enne. Aga kui me tahame tegelik hash tabel, siis saame lihtsalt sõlme pointer array siin. Näiteks suurus 500. 

Nüüd teate, seal saab olema kaubandus off vahel suurusest hash tabelit ja suurus Teie ahelloendid. Kui teil on tõesti suur arv kopad, kujutledes, millel töötamiseks tagasi edasi-rida leida oma ämber. Aga sa ei taha ka väike number kopad, sest siis me oleme tagasi algne probleem, kuidas võttes liiga palju palle meie ämber. 

OK, aga kui ei, meie pall minna? Noh, meil on vaja kõigepealt on ball, eks? Teeme malloc sõlme iga uus sõna, et meil on. node * new_node võrdsete malloc (sizeof (node)). 

Nüüd, kui meil on see struktuur, me saab skaneerida, kasutades funktsiooni fscanf, string meie faili, kui see sõnastik faili sisse new_node nool sõna, kus new_node nool sõna on meie sihtpunkt sõna. 

Järgmisena me tahame hash et sõna hash funktsiooni. Räsifunktsiooni võtab stringi ja tagastab indeks. Sel juhul indeks peab olla väiksem kui arv Kopad, et teil on. 

Nüüd hash funktsiooni, kui üritate leida üks ja luua üks oma meeles pidada, et nad olema deterministlik. See tähendab, et sama väärtus peab map sama ämber iga kord et sa hash see. 

See on nagu raamatukogu. Kui te võtate raamat, mis põhineb autor, sa tead, mis riiulil peaks minna, olgu see riiul number üks, kaks või kolm. Ja see raamat on alati kuulud kas riiulil üks, kaks või kolm. 

Niisiis, kui new_node nool sõna on sõna oma sõnaraamat, siis hashing new_node nool sõna meile indeks ämber hash tabel. Ja siis lisada, et sellesse konkreetne seotud nimekirja tähistatud tagastatav väärtus meie hash funktsiooni. 

Vaatame näiteks lisades sõlme alguses seotud nimekirja. Kui juht on sõlm pointer, mis näitab alguses seotud nimekirja ja new_node tähistab uut sõlm, mida soovite sisestada, vaid määrates pea new_node kaotaks link ülejäänud nimekirja. Nii et me ei taha seda teha. 

Pigem tahame veenduda et me kinni hoida iga ühe sõlme meie programmis. Nii töötab new_node noolt võrdsete pea ja siis pea võrdne new_node säilitab kõik lingid ja ei kaota. 

Aga kui soovite, et teie nimekirjas olla sorteeritud, sest olles järjestatud seotud nimekiri võiks olla lihtsam otsides seda hiljem? Noh, et sa pead teadma kuidas läbida ahelloendid. 

Läbida seotud nimekirja, ajame sõlme pointer, sõlme *, tegutseda kursor, mis näitab, milline sõlme sa oled, alustades esimesel element. Suvalises kuni kursor on null, saame läbi teatud protsessid ja seejärel edasi kursori peame kasutades kursori noolt väärtus. 

Pea meeles, et see on sama asi, mis öeldes täht kursori viite mahavõtmine kursori järgi, seejärel kasutades dot operaator väärtus. Nii ajakohastamine kursor määrates kursor kursori noolt. 

Ütle, et määrata kindlaks, et D saab sisse vahel C ja E. lisamiseks sõlme, on new_node D käsk sõlme E, mis on kursori kõrval. Ja siis C, kursor, saab siis juhtida D. Nii, siis peab nimekirja. Ole ettevaatlik, et mitte kaotada oma linke kursori noolt D kohe. 

Hea küll. Nii see on, kuidas sa võiksid lisada sõlmede laadige neid, koormus sõnad need sõlmede ja neid sisestada oma hash tabel. Nüüd vaatame proovib. 

In Prefiksipuu, iga sõlm sisaldab massiivi sõlme suunanäitajaks, üks iga tähestiku tähe pluss ülakoma. Ja iga element massiivi toob välja teise sõlme. Kui see sõlm on null, siis see kiri ei kavatse olla järgmine kiri mõni sõna järjest, sest iga sõna näitab, kas see on viimane iseloomu sõna või mitte. 

Vaatame joonisel. Loodetavasti asjad natuke selgem. Sellel joonisel on näha, et ainult Teatud tähtede ja teatud alimerkkijonojen mida loetletud välja. Nii saab jälgida teatud rajad, ja kõik need rajad viivad teid erinevaid sõnu. 

Niisiis, kuidas me esindame seda C? Noh, iga sõlme nüüd läheb on tõeväärtuse mis näitab, kas et sõlm on lõpuks antud sõna või mitte. Ja siis on teil ka massiivi sõlme vihjeid kutsus lapsed ja seal saab olema 27 neist. Ja pea meeles, sa ka tahad jälgida oma esimese sõlme. Me nimetame seda root. 

Nii et see struktuur Prefiksipuu. Kuidas me esindame seda nagu sõnastikku? Noh, et laadida sõnad, et iga sõnastik sõna, sa lähed tahan itereerima läbi Prefiksipuu. Ja iga element laste vastab erinev täht. 

Nii kontrollides raha lastele indeks i, kus i tähistab konkreetse indeksi kirjas, et üritate sisestada. Noh, kui see on null, siis tahad, et malloc uus sõlm ja lapsi i osutavad, et sõlme. 

Kui see ei ole null, siis see tähendab, et et antud haru, mis antud substring, on juba olemas. Siis sa lihtsalt liikuda, et uus sõlm ja jätkata. Kui oled lõpuks sõna, üritate koormus sõnastik, siis saate määrata, et aktiivse sõlme, et sa kellelegi tõsi. 

Nii vaatame näiteks sisestades sõna "rebane" meie sõnastik. Teeskle alustame tühi sõnastik. Esimene täht F, mis asub Lastel indeks viis juured lapsed massiivi. Nii me lisada, et sisse 

Kirjas O on siis lastel indeks 15, pärast seda F. Ja siis X veelgi madalam, hargnevate off O lapsed. Ja siis, kuna X on viimane kiri sõna "rebane", siis ma lähen värv, roheline näitab, et see lõpuks sõna. C, et oleks, millega Is Word Boole'i ​​väärtusele tõene. 

Mis nüüd, kui järgmise sõna, et sa oled laadimist on sõna "foo"? Noh, sa ei pea malloc enam ruumi F või O, sest need on juba olemas. Aga viimase O suva? See üks, pead malloc. Tee uus sõlm, et kehtestada Kas Word Loogiline tõeseks. 

Nüüd lähme sisestada "koer." Koer alustada indeks kolm juured lapsed, sest D ei ole veel loodud. Ja me järgima samasugust protsessi nagu enne, luues substring koer, Kus on G roheliseks sest see on sõna lõpus. 

Nüüd, aga kui me tahame, et sisestada "ei"? Noh, see on substring koera, nii me ei pea malloc enam. Aga me peame näitama, kus me oleme jõudnud, et sõna. Nii O on värvitud roheliseks. Jätkuv et protsessi iga sõna sinu sõnastik, olete laaditakse need ühte oma hash tabelit või oma Prefiksipuu. 

speller.c möödub stringid dictionary.c neid kontrollima. Nüüd kontrolli funktsioon peab toimima alusel juhul tundetus. See tähendab, et suurte tähtedega ja väiketähti ja mix nii peaks kõik võrduda tõsi, kui mõni kombinatsioon, mis on sõnastik. Võite eeldada, et stringid on ainult kavatse sisaldada tähestikulises märki või ülakomade. 

Seega vaatame, kuidas sa võiksid vaadata koos hash tabeli struktuuri. Noh, kui sõna on olemas, siis leidub hash tabelis. Siis võid proovida leida, et sõna asjaomases ämber. 

Nii et mis ämber oleks see sõna olema? Noh, siis tahaks saada number, et indeks kopa, hashing et sõna ja siis otsides selle seotud nimekirja läbimisel läbi kogu seotud nimekirja kasutades String Võrdle funktsiooni. 

Kui lõpuks lingitud loetelus jõudnud, mis tähendab, et kursor jõuab null, siis sõna pole võib leida sõnaraamatust. See ei ole muul ämber. Nii et siin, võite näha, kuidas seal võib olema kompromiss, millel on üks järjestatud ahelloendid või sortimata ones. Kas võtab rohkem aega jooksul laadida või enam ajal vaadata. 

Kuidas võiks sa kontrollida Prefiksipuu struktuur? Me läheme mööda allapoole aastal Prefiksipuu. Iga täht sisestatakse sõna et me kontrollime me läheme, et vastav osa lastele. 

Kui see element on null, siis see tähendab et ei ole alimerkkijonojen sisaldavad meie sisend sõna, nii et sõna valesti. Kui see ei ole null, saame liikuda Järgmise kirja sõna, et me oleme kontrollimine ja seda protsessi jätkata kuni jõuame lõpuks sisend sõna. Ja siis saame vaadata Juhul kui on sõna tõsi. Kui on, siis suur. Sõna on õige. Aga kui ei ole, kuigi see substring olemas Prefiksipuu sõna on valesti. 

Kui funktsioon Suurus nimetatakse, suurus peaks tagasi sõnade arv on teie antud sõnastik andmestruktuur. Nii et kui te kasutate hash tabel, siis saab kas minna läbi iga seotud nimekirja iga kopp loendades sõnad on olemas. Kui te kasutate Prefiksipuu saate läbima kõik mitte null tee oma Prefiksipuu. Või kui oled laadimist sõnastik aastal, võib-olla saab jälgida, kuidas palju sõnu sa laadimist sisse 

Kui speller.c lõpetab kontroll tekstifaili vastu sõnastik, siis ta on teinud ja et ta nõuab mahalaadimine, kus teie töö on tasuta midagi et olete malloced. Nii et kui te kasutate hash tabel, siis peavad olema eriti ettevaatlik, et vältida mälulekked mitte vabastades midagi enneaegselt ja kellel peale iga ühe lingi enne teid. 

Nii iga element hash tabel ja iga sõlme seotud nimekirja, tahad tasuta, et sõlme. Kuidas minna umbes vabastades seotud nimekirja? Seades oma sõlme pointer kursor pea, et aasta algusest seotud nimekirja, siis kui kursor ei ole null, saate ajutiselt sõlme kursor kursor. Siis edasi kursor. Ja siis saad tasuta, et ajutine väärtus hoides samal ajal endiselt edasi kõike hiljem. 

Mis siis, kui te kasutate Prefiksipuu? Siis parim viis seda teha laadimata päris alt üles. Reisides madalaima võimaliku sõlme, saad tasuta kõik lähtekohad et lapsed ja siis tagasiteed ülespoole, vabastades kõik elemendid kõik laste massiivid, kuni põrkad oma top root sõlme. Siin, kus Recursion tulevad mugav. 

Veendumaks, et te olete ilmselt vabaks kõik, mis sa oled malloced, saate Valgrind. Running Valgrind kestab oma programmi lugedes mitu baiti mälu te kasutate ja veenduge, et olete vabastas neile kõik, ütlen kus peate võib-olla unustanud tasuta. Nii kestab see ja teine ​​kord Valgrind ütleb ja annab teile minna, siis olete valmis maha laadida. 

Nüüd paar näpunäiteid enne reisile minekut maha ja alustada selle rakendamist oma sõnastik. Salli läbida väiksem sõnastik kui üritate testida asjad ja silumine koos SKPst. Kasutamine speller on. / Speller, vabatahtlik sõnastik, ja siis tekst. 

Vaikimisi see laeb suur sõnastik. Seega võiksite läbida väike sõnastik või isegi muuta oma oma, kohandades oma sõnastik ja oma tekstifaili. 

Ja lõpuks, ma ka soovitada võtta pliiatsi ja paberi ja juhtida asjad läbi enne, selle ajal ja pärast seda olete kirjutanud kõik oma koodi. Lihtsalt veenduge, et sul neid näpunäiteid õige. 

Soovin teile õnne. Ja kui olete valmis, kui soovite vaidlustada suur tahvel ja näha, kui kiiresti teie programm võrreldes oma klassikaaslaste, siis ma kutsun teil kontrollida, et välja. 

Mis, et olete valmis speller pset. Minu nimi on Zamyla ja see on CS50.