1 00:00:00,000 --> 00:00:12,350 >> [Musikgengivelse] 2 00:00:12,350 --> 00:00:13,050 >> ROB BOWDEN: Hej. 3 00:00:13,050 --> 00:00:13,640 Jeg er Rob. 4 00:00:13,640 --> 00:00:16,210 Og lad os denne løsning. 5 00:00:16,210 --> 00:00:20,070 Så her vi kommer til at gennemføre en generel tabel. 6 00:00:20,070 --> 00:00:24,090 Vi ser, at struct node i vores Tabellen kommer til at se sådan ud. 7 00:00:24,090 --> 00:00:28,710 Så det kommer til at have en char ord vifte af størrelse længde + 1. 8 00:00:28,710 --> 00:00:32,259 Glem ikke + 1, da den maksimale ord i ordbogen er 45 9 00:00:32,259 --> 00:00:33,130 tegn. 10 00:00:33,130 --> 00:00:37,070 Og så vil vi brug for en ekstra karakter for backslash nul. 11 00:00:37,070 --> 00:00:40,870 >> Og så er vores Hashtabelsamling i hver spand vil gemme en 12 00:00:40,870 --> 00:00:42,320 forbundet nodeliste. 13 00:00:42,320 --> 00:00:44,420 Vi gør ikke lineær probing her. 14 00:00:44,420 --> 00:00:48,430 Og så for at linke til den næste element i spanden, vi har brug for en 15 00:00:48,430 --> 00:00:50,390 struct node * næste. 16 00:00:50,390 --> 00:00:51,110 OK. 17 00:00:51,110 --> 00:00:53,090 Så det er hvad en knude ser ud. 18 00:00:53,090 --> 00:00:56,180 >> Nu her er den erklæring af vores Hashtabelsamling. 19 00:00:56,180 --> 00:00:59,640 Det kommer til at have 16.834 spande. 20 00:00:59,640 --> 00:01:01,910 Men dette tal er faktisk ligegyldigt. 21 00:01:01,910 --> 00:01:05,450 Og endelig, vi kommer til at have den global variabel hashtabelsamling størrelse, hvilket 22 00:01:05,450 --> 00:01:07,000 kommer til at starte som nul. 23 00:01:07,000 --> 00:01:10,760 Og det kommer til at holde styr på hvor mange ord der er i vores ordbog. 24 00:01:10,760 --> 00:01:13,710 >> Så lad os tage et kig på belastning. 25 00:01:13,710 --> 00:01:16,390 Bemærk, at belastning, den returnerer en bool. 26 00:01:16,390 --> 00:01:20,530 Du vender tilbage sandt, hvis det var lykkedes indlæst, og falsk ellers. 27 00:01:20,530 --> 00:01:23,990 Og det tager en const char * ordbog, som er ordbogen 28 00:01:23,990 --> 00:01:25,280 at vi ønsker at åbne. 29 00:01:25,280 --> 00:01:27,170 Så det er den første ting vi kommer til at gøre. 30 00:01:27,170 --> 00:01:29,500 >> Vi kommer til at fopen den ordbog til læsning. 31 00:01:29,500 --> 00:01:31,680 Og vi er nødt til at gøre sikker på, at det lykkedes. 32 00:01:31,680 --> 00:01:35,920 Så hvis det returnerede NULL, så vi ikke gjorde held åbne ordbogen. 33 00:01:35,920 --> 00:01:37,440 Og vi har brug for at vende tilbage falsk. 34 00:01:37,440 --> 00:01:41,580 Men det antages, at den gjorde med succes åben, så vi ønsker at læse 35 00:01:41,580 --> 00:01:42,400 ordbogen. 36 00:01:42,400 --> 00:01:46,450 Så hold looping indtil vi finder nogle grund til at bryde ud af denne sløjfe, 37 00:01:46,450 --> 00:01:47,570 som vi vil se. 38 00:01:47,570 --> 00:01:48,920 Så hold looping. 39 00:01:48,920 --> 00:01:51,780 >> Og nu vil vi allokere en enkelt node. 40 00:01:51,780 --> 00:01:54,020 Og selvfølgelig har vi brug for at lufte kontrollere igen. 41 00:01:54,020 --> 00:01:58,680 Så hvis mallocing ikke lykkes, så vi ønsker at losse enhver knude, som vi 42 00:01:58,680 --> 00:02:02,590 sket med malloc før, lukke ordbog og returnere falsk. 43 00:02:02,590 --> 00:02:06,830 Men at ignorere det, antager vi lykkedes, så vi ønsker at bruge fscanf 44 00:02:06,830 --> 00:02:12,400 at læse et enkelt ord fra vores ordbogen til vores knude. 45 00:02:12,400 --> 00:02:17,940 Så husk at post> Ordet er char ord buffer størrelse LENGHTH + 1 46 00:02:17,940 --> 00:02:20,300 at vi kommer til at gemme ord i. 47 00:02:20,300 --> 00:02:25,070 >> Så fscanf vil returnere 1, så længe som det var i stand til at 48 00:02:25,070 --> 00:02:26,750 læse et ord fra filen. 49 00:02:26,750 --> 00:02:30,460 Hvis der sker enten en fejl, eller vi nå enden af ​​filen, det 50 00:02:30,460 --> 00:02:31,950 vil ikke vende tilbage 1.. 51 00:02:31,950 --> 00:02:35,180 I så fald er det ikke returnere 1, vi endelig kommer til at bryde ud af 52 00:02:35,180 --> 00:02:37,280 dette, mens løkke. 53 00:02:37,280 --> 00:02:42,770 Så vi kan se, at når vi har med succes læse et ord i 54 00:02:42,770 --> 00:02:48,270 post> ord, så vi skal til at ordet ved hjælp af vores hash funktion. 55 00:02:48,270 --> 00:02:49,580 >> Lad os tage et kig på hash-funktionen. 56 00:02:49,580 --> 00:02:52,430 57 00:02:52,430 --> 00:02:55,610 Så du behøver ikke virkelig har brug for at forstå dette. 58 00:02:55,610 --> 00:02:59,460 Og faktisk vi bare trak denne hash fungere fra internettet. 59 00:02:59,460 --> 00:03:04,010 Det eneste, du skal erkende, er at det tager en const char * ord. 60 00:03:04,010 --> 00:03:08,960 Så det tager en streng som input, og returnere en usigneret int som output. 61 00:03:08,960 --> 00:03:12,360 Så det hele er en hash-funktion er, er det tager i et input og giver dig en 62 00:03:12,360 --> 00:03:14,490 indekset i Hashtable. 63 00:03:14,490 --> 00:03:18,530 >> Bemærk, at vi moding ved NUM_BUCKETS, så returnerede værdi 64 00:03:18,530 --> 00:03:21,730 faktisk er et indeks i Hashtable og indekserer ikke ud over 65 00:03:21,730 --> 00:03:24,320 grænserne for array. 66 00:03:24,320 --> 00:03:28,060 Så eftersom funktion, vi kommer at hash det ord, vi læser 67 00:03:28,060 --> 00:03:29,390 ordbogen. 68 00:03:29,390 --> 00:03:31,700 Og så vil vi bruge at hash for at indsætte 69 00:03:31,700 --> 00:03:33,750 indrejse i Hashtable. 70 00:03:33,750 --> 00:03:38,520 >> Nu Hashtable hash er den aktuelle forbundet liste i tabellen. 71 00:03:38,520 --> 00:03:41,410 Og det er meget muligt at det er bare NULL. 72 00:03:41,410 --> 00:03:44,960 Vi ønsker at indsætte vores indtræden på det begyndelsen af ​​denne linkede liste. 73 00:03:44,960 --> 00:03:48,600 Og så vil vi have vores nuværende indgang til hvad Hashtable 74 00:03:48,600 --> 00:03:50,380 øjeblikket peger på. 75 00:03:50,380 --> 00:03:53,310 Og så vil vi gemme, i Hashtable på 76 00:03:53,310 --> 00:03:55,350 hash, det aktuelle opslag. 77 00:03:55,350 --> 00:03:59,320 Så disse to linjer held indsætte posten i begyndelsen af 78 00:03:59,320 --> 00:04:02,260 forbundet listen på det pågældende indeks i Hashtable. 79 00:04:02,260 --> 00:04:04,900 >> Når vi er færdig med det, vi kender at vi fandt et andet ord i 80 00:04:04,900 --> 00:04:07,790 ordbog, og vi tilvækst igen. 81 00:04:07,790 --> 00:04:13,960 Så vi holde gør, at indtil fscanf endelig returneres noget ikke-1 ved 82 00:04:13,960 --> 00:04:16,950 hvilket punkt huske, at vi nødt til at frigøre post. 83 00:04:16,950 --> 00:04:19,459 Så heroppe vi malloced en post. 84 00:04:19,459 --> 00:04:21,329 Og vi har forsøgt at læse noget fra ordbogen. 85 00:04:21,329 --> 00:04:23,910 Og vi havde ikke held læst noget fra ordbogen, i 86 00:04:23,910 --> 00:04:26,650 hvilket tilfælde vi har brug for at frigøre posten at vi faktisk aldrig sat ind i 87 00:04:26,650 --> 00:04:29,140 hashtabelsamling, og endelig at bryde. 88 00:04:29,140 --> 00:04:32,750 >> Når vi bryde ud, vi har brug for at se, ja, vi bryde ud, fordi der 89 00:04:32,750 --> 00:04:34,360 var en fejl ved læsning fra filen? 90 00:04:34,360 --> 00:04:37,120 Eller gjorde vi bryde ud, fordi vi nået til slutningen af ​​filen? 91 00:04:37,120 --> 00:04:39,480 Hvis der var en fejl, vi ønsker at vende tilbage falsk. 92 00:04:39,480 --> 00:04:40,930 Fordi belastning ikke lykkedes. 93 00:04:40,930 --> 00:04:43,890 Og i den proces, vi ønsker at losse alle de ord, som vi læser i, og 94 00:04:43,890 --> 00:04:45,670 lukke ordbogen fil. 95 00:04:45,670 --> 00:04:48,740 >> Hvis man antager, vi lykkes, så vi bare stadig nødt til at lukke ordbogen 96 00:04:48,740 --> 00:04:53,040 fil, og endelig returnere sandt, da vi har indlæst ordbogen. 97 00:04:53,040 --> 00:04:54,420 Og det er det for belastning. 98 00:04:54,420 --> 00:04:59,020 Så nu kontrollere, givet en ladt Hashtabelsamling, kommer til at se sådan ud. 99 00:04:59,020 --> 00:05:03,140 Så tjek det returnerer en bool, der er kommer til at angive, om den passerede 100 00:05:03,140 --> 00:05:07,530 i char * ord, uanset om det passerede i strengen er i vores ordbog. 101 00:05:07,530 --> 00:05:09,890 Så hvis det er i ordbogen, hvis det er i vores Hashtabelsamling, 102 00:05:09,890 --> 00:05:11,170 vi vil vende tilbage sandt. 103 00:05:11,170 --> 00:05:13,380 Og hvis det ikke er, vil vi returnere falsk. 104 00:05:13,380 --> 00:05:17,740 >> I betragtning af dette gik i ord, er vi kommer til hash ordet. 105 00:05:17,740 --> 00:05:22,110 Nu er en vigtig ting at erkende, er at vi belastning vidste, at alle 106 00:05:22,110 --> 00:05:23,820 ord, vi kommer til at være lavere sag. 107 00:05:23,820 --> 00:05:25,820 Men her er vi ikke så sikker på. 108 00:05:25,820 --> 00:05:29,510 Hvis vi tager et kig på vores hash funktion, vores hash-funktionen faktisk 109 00:05:29,510 --> 00:05:32,700 er underdelen hver karakter af ordet. 110 00:05:32,700 --> 00:05:37,940 Så uanset kapitalisering af ord, vores hash funktion er afkastet 111 00:05:37,940 --> 00:05:42,270 det samme indeks for uanset kapitalisering er, som det ville have 112 00:05:42,270 --> 00:05:45,280 vendt tilbage til en helt små bogstaver version af ord. 113 00:05:45,280 --> 00:05:46,600 Okay. 114 00:05:46,600 --> 00:05:49,790 Det er vores indeks er i Hashtabelsamling for dette ord. 115 00:05:49,790 --> 00:05:52,940 >> Nu er dette for løkke kommer til gentage over den linkede liste 116 00:05:52,940 --> 00:05:55,000 der var på dette indeks. 117 00:05:55,000 --> 00:05:59,610 Så opdager vi initialiseres indgang at pege på dette indeks. 118 00:05:59,610 --> 00:06:02,750 Vi kommer til at fortsætte mens post! = NULL. 119 00:06:02,750 --> 00:06:07,770 Og husk at opdatere markøren i vores linkede liste entry = post> næste. 120 00:06:07,770 --> 00:06:14,400 Så har vores nuværende indgang til det næste element i den linkede liste. 121 00:06:14,400 --> 00:06:19,250 >> Så for hver post i den linkede liste, vi kommer til at bruge strcasecmp. 122 00:06:19,250 --> 00:06:20,330 Det er ikke strcomp. 123 00:06:20,330 --> 00:06:23,780 Fordi igen, vi ønsker at gøre tingene tilfælde ufølsomt. 124 00:06:23,780 --> 00:06:27,870 Så vi bruger strcasecmp at sammenligne ord, der blev passeret gennem denne 125 00:06:27,870 --> 00:06:31,860 funktion mod ordet der er i denne post. 126 00:06:31,860 --> 00:06:35,570 Hvis det returneres nul, betyder det, der var en kamp, ​​i hvilket tilfælde vil vi 127 00:06:35,570 --> 00:06:36,630 returnere sandt. 128 00:06:36,630 --> 00:06:39,590 Vi har med held fundet ord i vores hashtabelsamling. 129 00:06:39,590 --> 00:06:43,040 >> Hvis der ikke var en kamp, ​​så er vi gå til loop igen og se på 130 00:06:43,040 --> 00:06:43,990 næste post. 131 00:06:43,990 --> 00:06:47,640 Og vi vil fortsætte looping mens der er poster i denne linkede liste. 132 00:06:47,640 --> 00:06:50,160 Hvad sker der, hvis vi bryder ud af denne for-løkke? 133 00:06:50,160 --> 00:06:55,110 Det betyder, at vi ikke finde en post, der matches dette ord, i hvilket tilfælde 134 00:06:55,110 --> 00:07:00,220 vi vender tilbage falsk for at angive, at vores Hashtabelsamling ikke indeholder dette ord. 135 00:07:00,220 --> 00:07:02,540 Og det er en check. 136 00:07:02,540 --> 00:07:04,790 >> Så lad os tage et kig på størrelse. 137 00:07:04,790 --> 00:07:06,970 Nu størrelse kommer til at være temmelig simpel. 138 00:07:06,970 --> 00:07:11,080 Siden huske belastning, for hvert ord vi fundet, vi øges en global 139 00:07:11,080 --> 00:07:12,880 variabel Hashtabelsamling størrelse. 140 00:07:12,880 --> 00:07:16,480 Så størrelsen funktionen er bare at returnere global variabel. 141 00:07:16,480 --> 00:07:18,150 Og det er det. 142 00:07:18,150 --> 00:07:22,300 >> Nu endelig er vi nødt til at losse ordbog når alt er gjort. 143 00:07:22,300 --> 00:07:25,340 Så hvordan skal vi gøre det? 144 00:07:25,340 --> 00:07:30,440 Lige her er vi looping løbet alle spande vores bord. 145 00:07:30,440 --> 00:07:33,240 Så der er NUM_BUCKETS spande. 146 00:07:33,240 --> 00:07:37,410 Og for hver linkede liste i vores Hashtabelsamling, vi kommer til løkken over 147 00:07:37,410 --> 00:07:41,070 hele den linkede liste, frigøre hvert element. 148 00:07:41,070 --> 00:07:42,900 >> Nu er vi nødt til at være forsigtig. 149 00:07:42,900 --> 00:07:47,910 Så her har vi en midlertidig variabel der er lagre markøren til den næste 150 00:07:47,910 --> 00:07:49,730 element i den linkede liste. 151 00:07:49,730 --> 00:07:52,140 Og så vil vi fri det aktuelle element. 152 00:07:52,140 --> 00:07:55,990 Vi er nødt til at være sikker på, vi gør dette, da vi kan ikke bare frigøre det aktuelle element 153 00:07:55,990 --> 00:07:59,180 og derefter prøve at gå til det næste pointer, da når vi har befriet det, 154 00:07:59,180 --> 00:08:00,870 hukommelsen bliver ugyldig. 155 00:08:00,870 --> 00:08:04,990 >> Så vi nødt til at holde omkring en pegepind til det næste element, så vi kan frigøre 156 00:08:04,990 --> 00:08:08,360 aktuelle element, og så vi kan opdatere vores aktuelle element til at pege på 157 00:08:08,360 --> 00:08:09,550 det næste element. 158 00:08:09,550 --> 00:08:12,800 Vi vil sløjfe, mens der er elementer i denne linkede liste. 159 00:08:12,800 --> 00:08:15,620 Vi vil gøre det for alle forbundet lister i hashtabelsamling. 160 00:08:15,620 --> 00:08:19,460 Og når vi er færdige med det, vi har helt losset Hashtable, og 161 00:08:19,460 --> 00:08:20,190 vi er færdige. 162 00:08:20,190 --> 00:08:23,200 Så det er umuligt for unload til nogensinde vender tilbage falsk. 163 00:08:23,200 --> 00:08:26,470 Og når vi er færdige, vi bare returnere sandt. 164 00:08:26,470 --> 00:08:29,000 >> Lad os give denne løsning en chance. 165 00:08:29,000 --> 00:08:33,070 Så lad os tage et kig på, hvad vores struct node vil se ud. 166 00:08:33,070 --> 00:08:36,220 Her ser vi, at vi kommer til at have en bool ord og et struct node * børn 167 00:08:36,220 --> 00:08:37,470 beslag alfabet. 168 00:08:37,470 --> 00:08:38,929 169 00:08:38,929 --> 00:08:42,020 Så den første ting du måske være gad vide, hvorfor er ALPHABET 170 00:08:42,020 --> 00:08:44,660 ed defineret som 27? 171 00:08:44,660 --> 00:08:47,900 Nå, huske, at vi får brug for at håndtering apostrof. 172 00:08:47,900 --> 00:08:51,910 Så det kommer til at blive noget af en særligt tilfældet i hele dette program. 173 00:08:51,910 --> 00:08:54,710 >> Nu huske, hvordan en trie rent faktisk virker. 174 00:08:54,710 --> 00:08:59,380 Lad os sige, at vi indeksering ordet "katte". Så fra roden af ​​trie, 175 00:08:59,380 --> 00:09:02,610 vi kommer til at se på børnene array, og vi kommer til at se på 176 00:09:02,610 --> 00:09:08,090 indeks, der svarer til det bogstav C. Så det vil blive indekseret 2. 177 00:09:08,090 --> 00:09:11,530 Så i betragtning af at, der vil give os en ny node. 178 00:09:11,530 --> 00:09:13,820 Og så vil vi arbejde ud fra denne node. 179 00:09:13,820 --> 00:09:17,770 >> Så da knude, vi igen kommer til at se på børn array. 180 00:09:17,770 --> 00:09:22,110 Og vi kommer til at se på indeks nul at svare til A i kat. 181 00:09:22,110 --> 00:09:27,170 Så vi kommer til at gå til denne node, og eftersom knude vi kommer 182 00:09:27,170 --> 00:09:31,090 til at se på i slutningen, det er A svarer T. Og går videre til denne node, 183 00:09:31,090 --> 00:09:35,530 Endelig har vi helt kigget gennem vores ord "kat". Og nu bool 184 00:09:35,530 --> 00:09:40,960 ord er meningen at angive, om dette givne ord er faktisk et ord. 185 00:09:40,960 --> 00:09:43,470 >> Så hvorfor har vi brug for, at særlige tilfælde? 186 00:09:43,470 --> 00:09:47,700 Nå hvad ordet "katastrofe" er i vores ordbog, men den 187 00:09:47,700 --> 00:09:50,150 Ordet "kat" er ikke? 188 00:09:50,150 --> 00:09:54,580 Så og søger at se, hvis ordet "kat" er i vores ordbog, er vi 189 00:09:54,580 --> 00:09:59,970 vil held se gennem indeksene C-A-T i regionen node. 190 00:09:59,970 --> 00:10:04,290 Men det er kun fordi katastrofe sket for at skabe knudepunkter på vej 191 00:10:04,290 --> 00:10:07,190 fra C-A-T, hele vejen til slutningen af ​​ordet. 192 00:10:07,190 --> 00:10:12,020 Så bool ord bruges til at angive, om dette særlige sted 193 00:10:12,020 --> 00:10:14,310 faktisk angiver et ord. 194 00:10:14,310 --> 00:10:15,140 >> Ok. 195 00:10:15,140 --> 00:10:19,310 Så nu, at vi ved, hvad det trie er kommer til at se ud, lad os se på det 196 00:10:19,310 --> 00:10:20,730 indlæse funktion. 197 00:10:20,730 --> 00:10:24,610 Så belastning kommer til at returnere en bool for, om vi med succes eller 198 00:10:24,610 --> 00:10:26,720 forgæves indlæst ordbogen. 199 00:10:26,720 --> 00:10:30,460 Og det kommer til at være ordbogen at vi ønsker at indlæse. 200 00:10:30,460 --> 00:10:33,930 >> Så første ting vi skal gøre er at åbne op at ordbogen for læsning. 201 00:10:33,930 --> 00:10:36,160 Og vi er nødt til at sørge vi ikke svigte. 202 00:10:36,160 --> 00:10:39,580 Så hvis ordbogen ikke var succes åbnet, vil den vende tilbage 203 00:10:39,580 --> 00:10:42,400 null, i hvilket tilfælde vi kommer til at vende tilbage falsk. 204 00:10:42,400 --> 00:10:47,230 Men at antage, at det er lykkedes åbnet, så kan vi rent faktisk læst 205 00:10:47,230 --> 00:10:48,220 gennem ordbogen. 206 00:10:48,220 --> 00:10:50,880 >> Så første ting, vi kommer til at ønsker at gøre, er at vi har denne 207 00:10:50,880 --> 00:10:52,500 global variabel rod. 208 00:10:52,500 --> 00:10:56,190 Nu rod bliver en node *. 209 00:10:56,190 --> 00:10:59,760 Det er toppen af ​​vores trie, at vi er vil blive iteration igennem. 210 00:10:59,760 --> 00:11:02,660 Så den første ting, vi vil ønsker at gøre, er at tildele 211 00:11:02,660 --> 00:11:04,140 hukommelse for vores rod. 212 00:11:04,140 --> 00:11:07,980 Bemærk, at vi bruger den calloc funktion, som er stort set den samme 213 00:11:07,980 --> 00:11:11,500 som allokere funktion, medmindre det er garanteret til at returnere noget, der er 214 00:11:11,500 --> 00:11:13,180 helt nulstillet. 215 00:11:13,180 --> 00:11:17,290 Så hvis vi brugte malloc, ville vi nødt til at gå igennem alle de pejlemærker i vores 216 00:11:17,290 --> 00:11:20,160 node, og sørg for, at de er alle nul. 217 00:11:20,160 --> 00:11:22,710 Så calloc vil gøre det for os. 218 00:11:22,710 --> 00:11:26,330 >> Nu ligesom malloc, er vi nødt til at gøre sikker på, at tildelingen var faktisk 219 00:11:26,330 --> 00:11:27,520 succes. 220 00:11:27,520 --> 00:11:29,990 Hvis det returnerede null, så vi nødt til at lukke eller ordbog 221 00:11:29,990 --> 00:11:32,100 fil og returnere falsk. 222 00:11:32,100 --> 00:11:36,835 Så under forudsætning af, at tildelingen var succes, vi kommer til at bruge en node * 223 00:11:36,835 --> 00:11:40,270 markøren til gentage gennem vores trie. 224 00:11:40,270 --> 00:11:43,890 Så vores rødder aldrig kommer til at ændre, men vi kommer til at bruge markøren til 225 00:11:43,890 --> 00:11:47,875 faktisk gå fra knudepunkt til knudepunkt. 226 00:11:47,875 --> 00:11:50,940 >> Så i denne for-løkke, vi læser gennem ordbogen fil. 227 00:11:50,940 --> 00:11:53,670 Og vi bruger fgetc. 228 00:11:53,670 --> 00:11:56,290 Fgetc kommer til at få fat i en enkelt tegn fra filen. 229 00:11:56,290 --> 00:11:59,370 Vi kommer til at fortsætte med at snuppe tegn, mens vi ikke nå 230 00:11:59,370 --> 00:12:01,570 slutningen af ​​filen. 231 00:12:01,570 --> 00:12:03,480 >> Der er to sager, vi har brug for at håndtere. 232 00:12:03,480 --> 00:12:06,610 Den første, hvis karakter var ikke en ny linje. 233 00:12:06,610 --> 00:12:10,450 Så vi ved, om det var en ny linje, så vi er ved at gå videre til et nyt ord. 234 00:12:10,450 --> 00:12:15,240 Men forudsat det ikke var en ny linje, så her vi ønsker at finde ud af 235 00:12:15,240 --> 00:12:18,380 indeks vil vi indekset i i børn array, 236 00:12:18,380 --> 00:12:19,810 vi kiggede på før. 237 00:12:19,810 --> 00:12:23,880 >> Så som jeg sagde før, er vi nødt til særligt tilfælde apostrof. 238 00:12:23,880 --> 00:12:26,220 Bemærk vi bruger den ternære operatør her. 239 00:12:26,220 --> 00:12:29,580 Så vi kommer til at læse dette som, hvis karakter vi læser i var en 240 00:12:29,580 --> 00:12:35,330 apostrof, så vi kommer til at sætte index = "alfabet" -1, hvilket vil 241 00:12:35,330 --> 00:12:37,680 være indekset 26. 242 00:12:37,680 --> 00:12:41,130 >> Else, hvis det ikke var en apostrof, der vi kommer til at indstille indekset 243 00:12:41,130 --> 00:12:43,760 svarende til c - a. 244 00:12:43,760 --> 00:12:49,030 Så husk tilbage fra tidligere p-sæt, c - a kommer til at give os 245 00:12:49,030 --> 00:12:53,410 alfabetisk position C. Så hvis C er bogstavet A, vil dette 246 00:12:53,410 --> 00:12:54,700 give os indekset nul. 247 00:12:54,700 --> 00:12:58,120 For bogstavet B, vil det give os indeks 1, og så videre. 248 00:12:58,120 --> 00:13:03,010 >> Så det giver os indekset i børn array, vi ønsker. 249 00:13:03,010 --> 00:13:08,890 Nu, hvis dette indeks er i øjeblikket null i børnene, der betyder, at en knude 250 00:13:08,890 --> 00:13:11,830 findes ikke i øjeblikket fra denne vej. 251 00:13:11,830 --> 00:13:15,160 Så vi er nødt til at afsætte en knude til den vej. 252 00:13:15,160 --> 00:13:16,550 Det er, hvad vi vil gøre her. 253 00:13:16,550 --> 00:13:20,690 >> Så vi kommer til igen at bruge calloc funktion, så vi ikke behøver at 254 00:13:20,690 --> 00:13:22,880 nul ud af alle pointere. 255 00:13:22,880 --> 00:13:27,240 Og vi igen nødt til at tjekke at calloc svigtede ikke. 256 00:13:27,240 --> 00:13:30,700 Hvis calloc undlod, så har vi brug at losse alt, lukke vores 257 00:13:30,700 --> 00:13:32,820 ordbog, og returnere falsk. 258 00:13:32,820 --> 00:13:40,050 Så under forudsætning af, at det ikke mislykkes, da dette vil skabe et nyt barn for os. 259 00:13:40,050 --> 00:13:41,930 Og så vil vi gå til det pågældende barn. 260 00:13:41,930 --> 00:13:44,960 Vores markør gentage ned til barnet. 261 00:13:44,960 --> 00:13:49,330 >> Nu, hvis dette ikke var nul at begynde med, så markøren kan bare gentage 262 00:13:49,330 --> 00:13:52,590 ned til det barn uden egentlig skulle afsætte noget. 263 00:13:52,590 --> 00:13:56,730 Dette er tilfældet, når vi først skete tildele ordet "kat". Og 264 00:13:56,730 --> 00:14:00,330 det betyder, når vi går til at afsætte "Katastrofe", behøver vi ikke at skabe 265 00:14:00,330 --> 00:14:01,680 knudepunkter for C-A-T igen. 266 00:14:01,680 --> 00:14:04,830 De findes allerede. 267 00:14:04,830 --> 00:14:06,080 >> Hvad er det andet? 268 00:14:06,080 --> 00:14:10,480 Det er den tilstand, hvor c var backslash n, hvor c var en ny linje. 269 00:14:10,480 --> 00:14:13,710 Det betyder, at vi har succes afsluttet et ord. 270 00:14:13,710 --> 00:14:16,860 Hvad gør vi nu vil gøre, når vi gennemført et ord? 271 00:14:16,860 --> 00:14:21,100 Vi kommer til at bruge dette ord felt inde i vores struct node. 272 00:14:21,100 --> 00:14:23,390 Vi ønsker at sætte det til sand. 273 00:14:23,390 --> 00:14:27,150 Så det tyder på, at dette knudepunkt indikerer en vellykket 274 00:14:27,150 --> 00:14:29,250 ord, en faktiske ord. 275 00:14:29,250 --> 00:14:30,940 >> Sæt nu, at til sand. 276 00:14:30,940 --> 00:14:35,150 Vi ønsker at nulstille vores markøren til punkt til begyndelsen af ​​trie igen. 277 00:14:35,150 --> 00:14:40,160 Og endelig, forøge vores ordbog størrelse, da vi fandt et andet værk. 278 00:14:40,160 --> 00:14:43,230 Så vi kommer til at holde gør det, læsning i tegn for tegn, 279 00:14:43,230 --> 00:14:49,150 konstruere nye noder i vores trie og for hvert ord i ordbogen, indtil 280 00:14:49,150 --> 00:14:54,020 vi endelig nå C! = EOF, hvor tilfælde vi bryde ud af filen. 281 00:14:54,020 --> 00:14:57,050 >> Nu er der to sager under som vi måske har EOF ramt. 282 00:14:57,050 --> 00:15:00,980 Den første er, hvis der var en fejl læsning fra filen. 283 00:15:00,980 --> 00:15:03,470 Så hvis der var en fejl, vi nødt til at gøre det typiske. 284 00:15:03,470 --> 00:15:06,460 Unload alting tæt filen, returnerer falsk. 285 00:15:06,460 --> 00:15:09,810 Hvis man antager, at der ikke var en fejl, at betyder bare, at vi faktisk ramt slutningen af 286 00:15:09,810 --> 00:15:13,750 filen, i hvilket tilfælde vi lukker fil og returnere sandt, da vi 287 00:15:13,750 --> 00:15:17,330 indlæst ordbog ind i vores trie. 288 00:15:17,330 --> 00:15:20,170 >> Så lad os nu tjekke check. 289 00:15:20,170 --> 00:15:25,156 Ser ved check funktionen, ser vi at kontrollen kommer til at returnere en bool. 290 00:15:25,156 --> 00:15:29,680 Den returnerer sand, hvis dette ord, at det er væltes er i vores trie. 291 00:15:29,680 --> 00:15:32,110 Den returnerer falsk ellers. 292 00:15:32,110 --> 00:15:36,050 Så hvordan er du bestemme, om dette ord er i vores trie? 293 00:15:36,050 --> 00:15:40,190 >> Vi ser her, at, ligesom før, vi kommer til at bruge markøren til at gentage 294 00:15:40,190 --> 00:15:41,970 gennem vores trie. 295 00:15:41,970 --> 00:15:46,600 Nu her vi kommer til at gentage over vores hele ordet. 296 00:15:46,600 --> 00:15:50,620 Så iteration over ord, vi er forbi, vi kommer til at bestemme 297 00:15:50,620 --> 00:15:56,400 indeks i børn array, svarer til ordet beslag I. Så dette 298 00:15:56,400 --> 00:15:59,670 kommer til at se ud nøjagtig som belastning, hvor hvis ordet [i] 299 00:15:59,670 --> 00:16:03,310 er en apostrof, så vi vil at bruge index "alfabet" - 1. 300 00:16:03,310 --> 00:16:05,350 Fordi vi besluttet, at der er, hvor vi kommer til at gemme 301 00:16:05,350 --> 00:16:07,100 apostroffer. 302 00:16:07,100 --> 00:16:11,780 >> Else vi kommer til at bruge to lavere ord beslag I. Så husk at ord kan 303 00:16:11,780 --> 00:16:13,920 have vilkårlige bogstaver. 304 00:16:13,920 --> 00:16:17,540 Og så ønsker vi at sikre, at vi er ved hjælp af et lille version af ting. 305 00:16:17,540 --> 00:16:21,920 Og så trække fra, at 'a' til en gang igen give os alfabetisk 306 00:16:21,920 --> 00:16:23,880 position af denne karakter. 307 00:16:23,880 --> 00:16:27,680 Så det kommer til at være vores indeks i børn array. 308 00:16:27,680 --> 00:16:32,420 >> Og nu, hvis dette indeks i børnene array er null, det betyder at vi 309 00:16:32,420 --> 00:16:34,990 ikke længere kan fortsætte iteration ned vores trie. 310 00:16:34,990 --> 00:16:38,870 Hvis det er tilfældet, kan dette ord ikke muligvis være i vores trie. 311 00:16:38,870 --> 00:16:42,340 Da var det, der ville betyde, at der ville være en sti 312 00:16:42,340 --> 00:16:43,510 ned til det ord. 313 00:16:43,510 --> 00:16:45,290 Og du vil aldrig støde null. 314 00:16:45,290 --> 00:16:47,850 Så støder null, vi vender tilbage falsk. 315 00:16:47,850 --> 00:16:49,840 Ordet ikke er i ordbogen. 316 00:16:49,840 --> 00:16:53,660 Hvis det ikke var null, så er vi vil fortsætte iteration. 317 00:16:53,660 --> 00:16:57,220 >> Så vi vil derud markøren til at pege på det særlige 318 00:16:57,220 --> 00:16:59,760 knude på dette indeks. 319 00:16:59,760 --> 00:17:03,150 Vi holde gør det hele hele ordet, under forudsætning af 320 00:17:03,150 --> 00:17:03,950 vi aldrig ramt null. 321 00:17:03,950 --> 00:17:07,220 Det betyder, at vi var i stand til at komme igennem hele ordet og finde 322 00:17:07,220 --> 00:17:08,920 en knude i vores prøve. 323 00:17:08,920 --> 00:17:10,770 Men vi er ikke helt færdig endnu. 324 00:17:10,770 --> 00:17:12,290 >> Vi ønsker ikke bare at returnere sandt. 325 00:17:12,290 --> 00:17:14,770 Vi ønsker at vende tilbage cursoren> ord. 326 00:17:14,770 --> 00:17:18,980 Siden huske igen, er "kat" er ikke i vores ordbog, og "katastrofe" 327 00:17:18,980 --> 00:17:22,935 er, så vil vi med held får vi gennem ordet "kat". Men cursor 328 00:17:22,935 --> 00:17:25,760 ord vil være falsk og ikke sandt. 329 00:17:25,760 --> 00:17:30,930 Så vender vi tilbage markøren ord for at angive hvorvidt denne node er faktisk et ord. 330 00:17:30,930 --> 00:17:32,470 Og det er det for check. 331 00:17:32,470 --> 00:17:34,250 >> Så lad os se størrelse. 332 00:17:34,250 --> 00:17:37,350 Så størrelse kommer til at være temmelig nemt siden, husker i lasten, er vi 333 00:17:37,350 --> 00:17:41,430 forøgelse ordbog størrelse for hvert ord, som vi støder på. 334 00:17:41,430 --> 00:17:45,350 Så størrelse er bare at returnere ordbog størrelse. 335 00:17:45,350 --> 00:17:47,390 Og det er det. 336 00:17:47,390 --> 00:17:50,590 >> Så endelig har vi losse. 337 00:17:50,590 --> 00:17:55,100 Så losse, vi kommer til at bruge en rekursiv funktion til rent faktisk at gøre alt 338 00:17:55,100 --> 00:17:56,530 af arbejdet for os. 339 00:17:56,530 --> 00:17:59,340 Så vores funktion vil blive kaldt på aflæsser. 340 00:17:59,340 --> 00:18:01,650 Hvad aflæsser gøre? 341 00:18:01,650 --> 00:18:06,580 Vi ser her, at aflæsser kommer til at gentage over alle børnene på 342 00:18:06,580 --> 00:18:08,410 dette knudepunkt. 343 00:18:08,410 --> 00:18:11,750 Og hvis barneknudepunktet er ikke null, så vi kommer til at 344 00:18:11,750 --> 00:18:13,730 losse barneknudepunktet. 345 00:18:13,730 --> 00:18:18,010 >> Så det er dig rekursivt losse alle vores børn. 346 00:18:18,010 --> 00:18:21,080 Når vi er sikre på, at alle vores børn er blevet losset, så vi 347 00:18:21,080 --> 00:18:25,210 kan frigøre os selv, så losse os selv. 348 00:18:25,210 --> 00:18:29,460 Dette vil arbejde rekursivt losse hele trie. 349 00:18:29,460 --> 00:18:32,850 Og derefter en gang det er gjort, vi kan bare returnere sandt. 350 00:18:32,850 --> 00:18:34,210 Unload kan ikke fejle. 351 00:18:34,210 --> 00:18:35,710 Vi er bare frigøre ting. 352 00:18:35,710 --> 00:18:38,870 Så når vi er færdig frigør alt, returnere sandt. 353 00:18:38,870 --> 00:18:40,320 Og det er det. 354 00:18:40,320 --> 00:18:41,080 Mit navn er Rob. 355 00:18:41,080 --> 00:18:42,426 Og dette var stave. 356 00:18:42,426 --> 00:18:47,830 >> [Musikgengivelse]