[Mūzikas atskaņošanai] ROB BOWDEN: Hi. Es esmu Rob. Un pieņemsim šo risinājumu out. Tāpēc šeit mēs ejam, lai īstenotu vispārēja tabula. Mēs redzam, ka struktūrai mezgla mūsu tabula gatavojas izskatās šādi. Tātad, tas notiek, lai būtu char vārds masīva izmēru GARUMS + 1. Neaizmirstiet + 1, jo maksimālais vārdu vārdnīcā ir 45 rakstzīmes. Un tad mēs spēsim nepieciešams viens papildus rakstzīme slīpsvītru nulles. Un tad mūsu Hashtable katrā kauss ir gatavojas glabāt saistīts saraksts mezglu. Mēs nedarām lineāra zondēšana šeit. Un tāpēc, lai saite uz nākamā elements spainī, mums ir nepieciešams struct mezglā * nākamo. OK. Tātad, tas ir tas, ko mezglā izskatās. Tagad šeit ir deklarācija Mūsu Hashtable. Tas nāksies 16834 spaiņos. Bet šis numurs nav īsti jautājums. Un visbeidzot, mēs esam nāksies globālo mainīgo Hashtable lielums, kas gatavojas sākt kā nulle. Un tas notiek, lai sekotu, kā daudzi vārdi ir mūsu vārdnīcā. Tātad, pieņemsim to apskatīt slodzes. Ievērojiet, ka slodze, tā atgriež bool. Jūs atgrieztos taisnība, ja tas bija veiksmīgi piekrauts, un viltus citādi. Un tas notiek const char * vārdnīcu, kas ir vārdnīcā ka mēs vēlamies, lai atvērtu. Tā ka ir pirmā lieta, mēs gatavojamies darīt. Mēs ejam, lai fopen vārdnīca lasījumā. Un mēs esam nāksies veikt pārliecināti, ka tas izdevās. Tātad, ja tas atgriezās nulle, tad mēs neesam veiksmīgi atvērt vārdnīcu. Un mums ir nepieciešams, lai atgrieztos nepatiesa. Bet, pieņemot, ka tā veiksmīgi atvērt, tad mēs vēlamies, lai izlasītu vārdnīca. Lai saglabātu looping kamēr mēs atrodam kādu iemesls, lai izkļūt no šīs cilpas, ko mēs redzēsim. Lai saglabātu looping. Un tagad mēs esam gatavojas malloc vienu mezglu. Un, protams, mums ir nepieciešams gaisā pārbaudiet vēlreiz. Tātad, ja mallocing neizdevās, tad Mēs vēlamies, lai izkrautu jebkuru mezglu, ko mēs notika ar malloc pirms slēgt vārdnīcu un atgriezties viltus. Bet ignorējot, ka, pieņemot, ka mēs izdevies, tad mēs vēlamies izmantot fscanf lasīt vienu vārdu no mūsu vārdnīca mūsu mezglā. Tātad, atcerieties, ka ienākošo> vārds ir char vārdu bufera izmēra garumiem + 1 ka mēs ejam, lai saglabātu vārdu iekšā Tāpēc fscanf gatavojas atgriezties 1, ja vien jo tas varēja veiksmīgi lasīt vārdu no lietas materiāliem. Ja nu kļūda notiek, vai mēs beigs faila, tā vairs neatgriezīsies 1. Tādā gadījumā tas neatgriežas 1, mēs beidzot gatavojas izkļūt no to, kamēr cilpa. Tātad mēs redzam, ka tad, kad mēs esam veiksmīgi lasīt vārdu uz Ierakstu> vārds, tad mēs ejam, ka vārdu, izmantojot mūsu hash funkciju. Pieņemsim to apskatīt hash funkciju. Tātad jums nav tiešām ir nepieciešams saprast. Un faktiski mēs vienkārši velk šo hash darboties no interneta. Vienīgais, kas jums ir nepieciešams atzīt, ka tas aizņem const char * vārdu. Tātad, tas ir ņemot virkni kā ievade, un atgriešanās neparakstītu int kā produkciju. Tātad tas viss hash funkciju, tas ir uzņem ieejas un sniedz jums indeksu uz Hashtable. Ievērojiet, ka mēs esam moding ar NUM_BUCKETS, lai atgrieztā vērtība patiesībā ir rādītājs uz Hashtable un nav rādītājs pārsniedz robežas no masīva. Tāpēc, ka funkciju, mēs ejam hash vārdu, ka mēs lasām vārdnīca. Un tad mēs ejam, lai izmantotu ka hash ievietot iekļūšanu Hashtable. Tagad Hashtable hash ir pašreizējā saistīts sarakstu tabulā. Un tas ir ļoti iespējams, ka tas ir tikai NULL. Mēs vēlamies, lai ievietotu savu ienākšanu sākumā šī saistīta saraksta. Un tā mēs ejam, lai ir mūsu pašreizējo ieejas punkts, ko Hashtable Pašlaik norāda. Un tad mēs ejam uz veikalu, in Hashtable pie hash, pašreizējais ieraksts. Tātad šīs divas līnijas veiksmīgi ievietot ieraksts sākumā saistīts saraksts šajā indeksā in Hashtable. Pēc tam, kad mēs esam darīts ar to, ka mēs zinām, ka mēs atradām vēl vienu vārdu vārdnīcu, un mēs solis vēlreiz. Tāpēc mēs turpinām darām līdz fscanf beidzot atgriezās kaut non-1 at Kurā brīdī jāatceras, ka mums ir nepieciešams, lai atbrīvotu ierakstu. Tāpēc šeit mēs malloced ierakstu. Un mēs centāmies, lai lasītu kaut ko no vārdnīcas. Un mēs neesam veiksmīgi nolasīt kaut kas no vārdnīcas, kas tādā gadījumā mums ir nepieciešams, lai atbrīvotu ierakstu ka mēs nekad faktiski laisti Hashtable, un beidzot pauze. Kad mēs izcelties mums ir nepieciešams, lai redzētu, labi, mēs esam izcelties, jo tur bija kļūda lasot no lietas materiāliem? Vai mēs esam izcelties, jo mēs sasnieguši faila? Ja tur bija kļūda, tad mēs vēlamies atgriezties viltus. Jo slodze neizdevās. Un šajā procesā mēs vēlamies, lai izkrautu visi vārdi, ka mēs lasām, un aizveriet vārdnīcas faila. Pieņemot, ka mums izdosies, tad mēs vienkārši joprojām ir nepieciešams, lai aizvērtu vārdnīcu failu, un visbeidzot atgriezties taisnība, jo mēs veiksmīgi ielādēta vārdnīca. Un tas ir tas, lai slodze. Tāpēc tagad pārbaudiet, ņemot piekrauts Hashtable, gatavojas izskatās šādi. Lai pārbaudītu, tas atgriež bool, kas ir gatavojas, lai norādītu, vai pagājis in char * vārdu, vai pagājis virknē ir mūsu vārdnīcā. Tātad, ja tas ir norādīts vārdnīcā, ja tas ir mūsu Hashtable, mēs atgriezīsimies taisnība. Un, ja tā nav, mēs atgriezīsimies nepatiesa. Ņemot vērā šo pieņemts vārdu, mēs esam gatavojas hash vārdu. Tagad svarīga lieta atzīt, ka slodze mēs zinājām, ka visi vārdus mēs gribam būt mazie burti. Bet šeit mēs esam tik pārliecināts. Ja mēs to apskatīt mūsu hash funkciju, mūsu hash funkcija faktiski ir mazāks korpuss katra rakstzīme vārda. Tāpēc neatkarīgi no kapitalizācijas Vārds, mūsu hash funkcija ir atgriešanās pats indekss neatkarīgi kapitalizācija, jo tas būtu atpakaļ uz pavisam mazie burti versija vārda. Alright. Tas ir mūsu indekss ir spēkā Hashtable par šo vārdu. Tagad šis cilpa gatavojas atkārtot pa saistīts saraksts tas bija šajā indeksā. Tāpēc paziņojums mums ir inicializēta ierakstu , lai norādītu uz minētā indeksa. Mēs ejam, lai turpinātu bet ieraksts! = NULL. Un atcerieties, ka rādītāju atjaunināšana mūsu saistīts saraksts ieraksts = ieraksts> nākamo. Tā ir mūsu pašreizējais piekļuves vietu Nākamais punkts saistītajā sarakstā. Tātad uz katru ierakstu saistītajā sarakstā, mēs ejam, lai izmantotu strcasecmp. Tas nav strcomp. Jo atkal, mēs vēlamies darīt lietas gadījumā insensitively. Tāpēc mēs izmantojam strcasecmp, lai salīdzinātu vārdu, kas tika pieņemts, izmantojot šo funkcija pret vārdu , kas ir šā ieraksta. Ja tā atgriež nulli, tas nozīmē, ka tur bija spēles, un tādā gadījumā mēs vēlamies atgriezties true. Mēs veiksmīgi atraduši vārdu mūsu Hashtable. Ja nebija spēle, tad mēs esam dodas uz cilpu atkal un apskatīt Nākamais ieraksts. Un mēs turpināsim looping, bet tur Ir ieraksti šajā saistīta sarakstā. Kas notiek, ja mēs pārkāpjam no šīs cilpa? Tas nozīmē, ka mēs neesam atrast ierakstu, kas saskaņota šo vārdu, tādā gadījumā mēs atgriežamies viltus, lai norādītu, ka mūsu Hashtable neietvēra šo vārdu. Un tas ir pārbaude. Tātad, pieņemsim to apskatīt lieluma. Tagad lielums būs diezgan vienkārši. Jo atceros, slodzes, katram vārdam mēs noskaidrojām, mēs palielina globālās mainīgais Hashtable izmērs. Tā lielums funkcija ir tikai gatavojas atgriezties globālo mainīgo. Un tas arī viss. Beidzot, mums ir nepieciešams, lai izkrautu vārdnīca, kad viss ir izdarīts. Tātad, kā mēs gatavojamies darīt? Tieši šeit mēs esam looping vairāk visi spaiņi mūsu galda. Tāpēc ir NUM_BUCKETS kausi. Un katram, kas saistīta saraksta mūsu Hashtable, mēs ejam, lai cilpa vairāk veselums saistītā saraksta atbrīvojot katru elementu. Tagad mums ir jābūt uzmanīgiem. Tātad, šeit mums ir pagaidu mainīgo kas ir uzglabāšanas rādītāju uz nākamā elements saistītajā sarakstā. Un tad mēs ejam uz brīvu pašreizējais elements. Mums ir nepieciešams, lai pārliecinātos, mēs to darām, jo ​​mēs var ne tikai brīvi Pašlaik skatītās elements un tad mēģināt piekļūtu nākamajai rādītāju, jo, kad mēs esam atbrīvojušies to, atmiņa ir nederīgs. Tāpēc mums ir nepieciešams, lai saglabātu apmēram rādītāju uz nākamais elements, tad mēs varam brīvi strāvas elements, un pēc tam, mēs var atjaunināt Mūsu pašreizējais elements, lai norādītu nākamais elements. Mēs cilpas, bet tur ir elementi Šajā saistīts sarakstā. Mēs darīsim, ka visi ir saistīti sarakstus Hashtable. Un, kad mēs esam darīts ar to, ka mēs esam pilnībā izkrauta Hashtable, un mēs esam darījuši. Tātad, tas ir neiespējami, lai izkrautu kādreiz atgriezties viltus. Un, kad mēs esam darīts, mēs vienkārši atgriezties true. Pieņemsim sniegt šo risinājumu izmēģināt. Tātad, pieņemsim apskatīt to, kas mūsu struktūrai mezgls izskatīsies. Šeit mēs redzam, mēs ejam, lai būtu bool vārdu un struct mezglā * bērni kronšteins alfabētu. Tātad pirmā lieta, jūs varētu būt jautājums, kāpēc ir ALFABĒTS ed definēta kā 27? Nu, atcerieties, ka mēs ejam uz nepieciešamību kas apstrādes apostrofu. Tā, ka būs nedaudz Īpašs gadījums visā šajā programmā. Tagad atceros, kā trie faktiski darbojas. Pieņemsim, ka mēs indeksāciju vārdu "kaķi". Tad no saknes Trie, mēs ejam apskatīt bērniem masīvs, un mēs ejam apskatīt indekss, kas atbilst vēstules C. Tāpēc, ka tiks indeksētas 2. Tātad, ņemot vērā, ka tas būs dod mums jaunu mezglu. Un tad mēs strādājam no šī mezgla. Tāpēc, ka mezglā, mēs atkal esam skatīsies uz bērnu masīvs. Un mēs ejam apskatīt indeksu nulles lai tā atbilstu A kaķu. Tātad, tad mēs ejam, lai dotos uz šo mezglu, un ņemot vērā, ka mezgla mēs ejam apskatīt beigās tas ir atbilst ar T. un pārvietojas uz šo mezglu, Visbeidzot, mēs esam pilnīgi izskatījās caur mūsu vārdu "kaķis". Un tagad bool Vārds ir paredzēts, lai norādītu, vai tas dots vārds ir faktiski vārdu. Tātad, kāpēc mums ir nepieciešams, ka īpaša gadījumā? Nu ko par vārdu "katastrofa" ir mūsu vārdnīcā, bet vārdu "kaķis" ir ne? Tik un vēlas redzēt, ja vārds "kaķis" ir mūsu vārdnīcā, mēs esam būs veiksmīgi izskatīt indeksi C-T reģionā mezglā. Bet tas ir tikai tāpēc, ka katastrofa noticis, lai radītu mezglu ceļā no C-A-T, visu veidu vārda beigām. Tāpēc bool vārds tiek izmantots, lai norādītu, vai šo konkrēto atrašanās vietu faktiski norāda vārdu. Labi. Tāpēc tagad, ka mēs zinām, kas tas trie ir gatavojas izskatās, aplūkosim slodze funkciju. Tāpēc slodze gatavojas atgriezties bool par to, vai mēs veiksmīgi vai nesekmīgi ielādes vārdnīca. Un tas būs vārdnīca ka mēs gribam, lai slodze. Tātad pirmā lieta, ko mēs darīt, ir atvērts līdz šim vārdnīcā lasījumā. Un mums ir jāpārliecinās, mēs neesam neizdoties. Tātad, ja vārdnīcā nav veiksmīgi atvērts, tas atgriezīsies null, tādā gadījumā mēs esam gatavojas atgriezties viltus. Bet, pieņemot, ka tā veiksmīgi atvērts, tad mēs faktiski var izlasīt izmantojot vārdnīcu. Tātad pirmā lieta, ko mēs gatavojamies vēlaties darīt, ir, mums ir šis globālo mainīgo saknes. Tagad sakne būs mezglā *. Tā ir top mūsu Trie, ka mēs esam būs atkārtojot cauri. Tātad pirmā lieta, ka mēs ejam vēlaties darīt, ir piešķirt atmiņā mūsu saknes. Ievērojiet, ka mēs esam, izmantojot calloc funkcija, kas būtībā ir tas pats jo malloc funkciju, izņemot tā garantēta, lai atgrieztos kaut ko, kas ir pilnīgi nulli out. Tātad, ja mēs izmantojām malloc, mums būtu nepieciešams, lai iet cauri visiem norādes mūsu mezglā, un pārliecinieties, ka viņi visi null. Tāpēc calloc būs darīt, ka mums. Tagad, tāpat kā malloc, mums ir nepieciešams veikt pārliecināts, ka piešķīrums bija faktiski veiksmīga. Ja tas atgriezās null, tad mēs nepieciešams slēgt vai vārdnīca failu un atgriezties viltus. Tātad, pieņemot, ka sadalei ir veiksmīga, mēs ejam, lai izmantotu mezglu * kursoru atkārtot, izmantojot mūsu Trie. Tāpēc mūsu saknes nekad mainīsies, bet mēs esam gatavojas izmantot kursoru tiešām iet no mezgla uz mezglu. Tātad šis cilpa mēs lasām ar vārdnīcas faila. Un mēs esam izmantojot fgetc. Fgetc gatavojas sagrābt vienotu rakstzīmi no lietas materiāliem. Mēs turpināsim satveršanas rakstzīmes, kamēr mēs nenonāk faila beigas. Ir divi gadījumi, mums ir nepieciešams rīkoties. Pirmais, ja raksturs nebija jauna līnija. Tātad mēs zinām, ja tas bija jaunu līniju, tad mēs esam par to, lai pārietu uz jaunu vārdu. Bet pieņemot, ka tas nebija jaunu līniju, tad šeit mēs gribam, lai noskaidrotu indekss mēs ejam indeksēt ar bērnu masīvā, ka mēs paskatījās agrāk. Tātad, kā es teicu iepriekš, mums ir nepieciešams Īpašs gadījums Apostrofs. Ievērojiet, mēs izmantot trīskāršo operators šeit. Tāpēc mēs esam gatavojas lasīt to kā, ja rakstura lasām bija Apostrofs, tad mēs ejam, lai uzstādītu indekss = "ALFABĒTS" -1, kas būs būt indekss 26. Cits, ja tas nav Apostrofs, tur Mēs ejam, lai uzstādītu indeksu vienāds ar c -. Līdz ar to atcerēties atpakaļ ar iepriekš p komplektu, c - gatavojas sniegt mums alfabēta pozīcija C. Tātad, ja C ir burts, tas dod mums indekss nulle. Par vēstules B, tas dos mums indekss 1, un tā tālāk. Tāpēc tas dod mums indekss spēkā bērni, masīvs, ko mēs gribam. Tagad, ja šis rādītājs pašlaik Null bērni, tas nozīmē, ka mezgls Pašlaik nav no šī ceļa. Tāpēc mums ir nepieciešams piešķirt mezglu, lai šajā ceļā. Tas ir tas, ko mēs darīsim šeit. Tāpēc mēs esam gatavojas atkal izmantot calloc funkcija, tāpēc, ka mums nav nulle visas norādes. Un mums atkal nepieciešams, lai pārbaudītu ka calloc nav neizdoties. Ja calloc tomēr neizdodas, tad mums izkraut viss, aizvērt vārdnīcu, un atgriezties viltus. Tātad, pieņemot, ka tas nav neizdoties, tad Tas radīs jaunu bērnu mums. Un tad mēs dosimies uz šo bērnu. Mūsu kursors atkārtot uz leju, lai šo bērnu. Tagad, ja tas nav null, lai sāktu ar, tad kursors var tikai atkārtot uz leju, lai šo bērnu, bet faktiski kam piešķirt neko. Šis ir gadījums, kad mēs pirmo reizi notika piešķirt vārdu "kaķis". Un tas nozīmē, ka tad, kad mēs ejam, lai sadalītu "Katastrofa", mums nav nepieciešams, lai izveidotu mezglu C-A-T vēlreiz. Viņi jau pastāv. Kas ir šis cits? Tas ir stāvoklis, kurā c ir slīpsvītru n, kur c ir jauna līnija. Tas nozīmē, ka ir veiksmīgi pabeidzis vārdu. Tagad tas, ko mēs vēlamies darīt, kad mēs sekmīgi pabeigta vārdu? Mēs ejam, lai izmantotu šo vārdu lauku iekšpusē mūsu struct mezglā. Mēs gribam, lai noteiktu, kas ir taisnība. Tā, kas norāda, ka šis mezgls norāda veiksmīgs vārdu, faktisko vārdu. Tagad ir noteikts, ka, lai taisnība. Mēs vēlamies, lai atjaunotu savu kursoru uz punktu līdz sākumā Trie atkal. Un visbeidzot, solis mūsu vārdnīca izmērs, jo mēs atradām citu darbu. Tātad, mēs ejam, lai saglabātu darot, ka, lasījumā raksturu, raksturs, būvējot jaunas mezglu mūsu Trie un par katru vārdu vārdnīcā, līdz mēs beidzot sasniedz C! = EOF, kurā gadījumā mēs izkļūt no faila. Tagad ir divas lietas, ko kas mēs varētu būt hit EOF. Pirmais ir, ja tur bija kļūda lasot no lietas materiāliem. Tātad, ja tur bija kļūda, mēs jādara tipisks. Izkraut viss, close failu, atgriezties viltus. Pieņemot, ka tur nebija kļūda, ka tikai nozīmē, ka mēs faktiski hit beigām failu, un tādā gadījumā, mēs cieši failu un atgriezties taisnība, jo mēs veiksmīgi ielādēta vārdnīca mūsu Trie. Tāpēc tagad pieņemsim izbraukšana pārbaudi. Raugoties uz pārbaudes funkciju, mēs redzam, ka pārbaude ir gatavojas atgriezties bool. Tā atgriež true, ja šis vārds, ka tas ir tiek pieņemts, tur ir mūsu Trie. Tā atgriež false citādi. Tātad, kā jūs noteikt, vai šis vārds ir mūsu Trie? Mēs redzam šeit, ka, tāpat kā iepriekš, mēs gatavojamies izmantot kursoru atkārtot caur mūsu Trie. Tagad šeit mēs gatavojamies atkārtot pār mūsu visu vārdu. Tātad, atkārtojot visā vārdu mēs pagātnē, Mēs ejam, lai noteiktu indeksu uz bērnu masīvu, kas atbilst vārdu stiprinājuma I. Tātad šis gatavojas izskatās tieši tāpat kā slodze, kur, ja vārds [i] ir Apostrofs, tad mēs gribam izmantot indeksa "Alfabēts" - 1. Jo tika konstatēts, ka tas ir vieta, kur mēs ejam, lai saglabātu apostrofi. Vēl mēs spēsim izmantot divas zemāku vārdu kronšteins I. Līdz ar to atcerēties, ka vārds var ir patvaļīgu kapitalizāciju. Un tāpēc mēs vēlamies, lai pārliecinātos, ka mēs esam izmantojot mazo burtu versiju lietām. Un tad atņemt no tā "", lai pēc tam, kad atkal dod mums alfabētiskā nostāja šajā raksturs. Tā, ka būs mūsu indeksu uz bērnu masīvs. Un tagad, ja tas indekss par bērniem masīvs ir nulle, tas nozīmē, ka mēs vairs nevar turpināt, atkārtojot leju mūsu Trie. Ja tas ir gadījumā, šis vārds nevar iespējams, varētu būt mūsu Trie. Jo, ja tas tā būtu, tas būtu nozīmē, ka varētu būt ceļš uz leju, lai šo vārdu. Un jūs nekad sastapties null. Tātad sastopas Null, mēs atgriežamies nepatiesa. Vārda nav vārdnīcā. Ja tas nav null, tad mēs esam turpinās atkārtojot. Tātad, mēs ejam ārā tur kursoru norādīt to, ka īpaši mezglā šajā indeksā. Mēs turpinām darām visu visu vārdu, pieņemot mēs nekad hit null. Tas nozīmē, ka mēs varējām dabūt cauri visu vārdu un atrast mezglu mūsu mēģināt. Bet mēs esam ne gluži izdarīts vēl. Mēs nevēlamies, lai tikai atgrieztos taisnība. Mēs vēlamies, lai atgrieztos kursora> vārdu. Jo atceros atkal ir "kaķis" nav mūsu vārdnīcā, un "katastrofa" ir, tad mēs veiksmīgi mēs saņemam ar vārdu "kaķis". Bet kursors vārds būs nepatiess un nav taisnība. Tāpēc mēs atgriežamies kursora vārdu, lai norādītu vai šis mezgls ir patiesībā vārds. Un tas ir tas, lai pārbaudi. Tāpēc pieņemsim izbraukšana izmēru. Tā lielums būs diezgan viegli jo atceros, slodzes, mēs esam palielināšanai vārdnīca izmēru katrs vārds, ko mēs saskaramies. Tā lielums ir tikai gatavojas atgriezties vārdnīca izmēru. Un tas arī viss. Tātad visbeidzot mēs esam izkraut. Tātad izkraut, mēs ejam, lai izmantotu rekursīvas funkcijas, lai faktiski darīt visu darbu mums. Tāpēc mūsu uzdevums būs saukt par unloader. Kas ir izlādēšanas gatavojas darīt? Mēs redzam šeit, ka izlādēšanas gatavojas atkārtot pār visiem bērniem Tas īpaši mezglā. Un, ja bērns mezgls nav null, tad mēs ejam uz izkraut bērnu mezglu. Tāpēc tas ir jums rekursīvi izkrauj visiem mūsu bērniem. Pēc tam, kad mēs esam pārliecināti, ka visi mūsu bērni ir izkrautas, tad mēs var atbrīvot sevi, tāpēc izkraut sevi. Tas darbosies rekursīvi izkraut visu Trie. Un tad, kad tas ir izdarīts, mēs varam vienkārši atgriezties taisnība. Izkraut nevar neizdoties. Mēs esam tikai atbrīvojot lietas. Tātad, kad mēs esam darījuši atbrīvojot viss, atgriezties true. Un tas arī viss. Mans vārds ir Rob. Un tas bija Pareizrakstības. [Mūzikas atskaņošanai]