1 00:00:00,000 --> 00:00:12,350 >> [Musikk spilles] 2 00:00:12,350 --> 00:00:13,050 >> ROB BOWDEN: Hei. 3 00:00:13,050 --> 00:00:13,640 Jeg er Rob. 4 00:00:13,640 --> 00:00:16,210 Og la oss denne løsningen ut. 5 00:00:16,210 --> 00:00:20,070 Så her kommer vi til å implementere en generell tabell. 6 00:00:20,070 --> 00:00:24,090 Vi ser at struct node av vår tabellen kommer til å se slik ut. 7 00:00:24,090 --> 00:00:28,710 Så det kommer til å ha en char ord matrise av størrelse LENGDE + 1. 8 00:00:28,710 --> 00:00:32,259 Ikke glem + 1, siden den maksimale ord i ordlisten er 45 9 00:00:32,259 --> 00:00:33,130 tegn. 10 00:00:33,130 --> 00:00:37,070 Og så kommer vi til å trenge en ekstra tegnet for backslash null. 11 00:00:37,070 --> 00:00:40,870 >> Og da er vår hashtabellen i hvert bøtte kommer til å lagre en 12 00:00:40,870 --> 00:00:42,320 lenket liste av noder. 13 00:00:42,320 --> 00:00:44,420 Vi gjør ikke lineær sondering her. 14 00:00:44,420 --> 00:00:48,430 Og så for å koble til den neste element i bøtta, trenger vi en 15 00:00:48,430 --> 00:00:50,390 struct node * neste. 16 00:00:50,390 --> 00:00:51,110 OK. 17 00:00:51,110 --> 00:00:53,090 Så det er hva en node ser ut. 18 00:00:53,090 --> 00:00:56,180 >> Nå her er erklæringen av vår hashtabellen. 19 00:00:56,180 --> 00:00:59,640 Det kommer til å ha 16 834 bøtter. 20 00:00:59,640 --> 00:01:01,910 Men dette tallet ikke virkelig betyr noe. 21 00:01:01,910 --> 00:01:05,450 Og til slutt, kommer vi til å ha den global variabel hashtabellen størrelse, som 22 00:01:05,450 --> 00:01:07,000 kommer til å starte som null. 23 00:01:07,000 --> 00:01:10,760 Og det kommer til å holde oversikt over hvordan mange ord er i vår ordbok. 24 00:01:10,760 --> 00:01:13,710 >> Så la oss ta en titt på lasten. 25 00:01:13,710 --> 00:01:16,390 Legg merke til at laste, returnerer den en bool. 26 00:01:16,390 --> 00:01:20,530 Du return true hvis det var vellykket lastet, og falsk ellers. 27 00:01:20,530 --> 00:01:23,990 Og det tar en const char * ordbok, som er ordlisten 28 00:01:23,990 --> 00:01:25,280 at vi ønsker å åpne. 29 00:01:25,280 --> 00:01:27,170 Så det er den første tingen vi kommer til å gjøre. 30 00:01:27,170 --> 00:01:29,500 >> Vi kommer til å fopen den ordbok for lesing. 31 00:01:29,500 --> 00:01:31,680 Og vi er nødt til å gjøre sikker på at det lyktes. 32 00:01:31,680 --> 00:01:35,920 Så hvis det returneres NULL, så vi gjorde ikke hell åpne ordboken. 33 00:01:35,920 --> 00:01:37,440 Og vi trenger å returnere false. 34 00:01:37,440 --> 00:01:41,580 Men forutsatt at det gjorde med hell åpen, så vi ønsker å lese 35 00:01:41,580 --> 00:01:42,400 ordbok. 36 00:01:42,400 --> 00:01:46,450 Så hold looping til vi finner noen Grunnen til å bryte ut av denne sløyfe, 37 00:01:46,450 --> 00:01:47,570 som vi skal se. 38 00:01:47,570 --> 00:01:48,920 Så hold looping. 39 00:01:48,920 --> 00:01:51,780 >> Og nå skal vi malloc en enkelt node. 40 00:01:51,780 --> 00:01:54,020 Og selvfølgelig må vi å lufte sjekke igjen. 41 00:01:54,020 --> 00:01:58,680 Så hvis mallocing ikke lykkes, da vi ønsker å losse noen node som vi 42 00:01:58,680 --> 00:02:02,590 skjedde med malloc før, lukker ordbok og return false. 43 00:02:02,590 --> 00:02:06,830 Men ignorerer det, forutsatt at vi lyktes, da vi ønsker å bruke fscanf 44 00:02:06,830 --> 00:02:12,400 å lese et eneste ord fra vår ordlisten, i vår node. 45 00:02:12,400 --> 00:02:17,940 Så husk at entry> Ordet er røye Ordet buffer størrelse lenghth + 1 46 00:02:17,940 --> 00:02:20,300 at vi kommer til å lagre ordet i. 47 00:02:20,300 --> 00:02:25,070 >> Så fscanf kommer til å returnere en, så lenge som det var i stand til å lykkes 48 00:02:25,070 --> 00:02:26,750 lese et ord fra filen. 49 00:02:26,750 --> 00:02:30,460 Hvis enten en feil skjer, eller vi kommer til slutten av filen, den 50 00:02:30,460 --> 00:02:31,950 vil ikke returnere en. 51 00:02:31,950 --> 00:02:35,180 I så fall betyr det ikke returnere en, vi endelig kommer til å bryte ut av 52 00:02:35,180 --> 00:02:37,280 dette mens loop. 53 00:02:37,280 --> 00:02:42,770 Så vi ser at når vi har lykkes lese inn et ord i 54 00:02:42,770 --> 00:02:48,270 entry> ord, så vi kommer til at ordet med vår hash-funksjon. 55 00:02:48,270 --> 00:02:49,580 >> La oss ta en titt på hash-funksjon. 56 00:02:49,580 --> 00:02:52,430 57 00:02:52,430 --> 00:02:55,610 Så du ikke virkelig trenger å forstå dette. 58 00:02:55,610 --> 00:02:59,460 Og faktisk vi bare trakk denne hash fungere fra internett. 59 00:02:59,460 --> 00:03:04,010 Det eneste du trenger å anerkjenne er at dette tar en const char * ord. 60 00:03:04,010 --> 00:03:08,960 Så det tar en streng som input, og returnere en usignert int som utgang. 61 00:03:08,960 --> 00:03:12,360 Så det er alt en hash-funksjon er, er det tar i en inngang og gir deg en 62 00:03:12,360 --> 00:03:14,490 indeksen inn hashtabellen. 63 00:03:14,490 --> 00:03:18,530 >> Legg merke til at vi Moding av NUM_BUCKETS, slik at verdien som returneres 64 00:03:18,530 --> 00:03:21,730 faktisk er en indeks inn i hashtabellen og indekserer ikke utover 65 00:03:21,730 --> 00:03:24,320 matrisegrensen. 66 00:03:24,320 --> 00:03:28,060 Så gitt at funksjonen skal vi til hasj ordet som vi leser 67 00:03:28,060 --> 00:03:29,390 ordbok. 68 00:03:29,390 --> 00:03:31,700 Og så skal vi bruke at hasj for å sette inn 69 00:03:31,700 --> 00:03:33,750 inntreden i hashtabellen. 70 00:03:33,750 --> 00:03:38,520 >> Nå hashtabellen hash er gjeldende lenket liste i tabellen. 71 00:03:38,520 --> 00:03:41,410 Og det er meget mulig at det er bare NULL. 72 00:03:41,410 --> 00:03:44,960 Vi ønsker å sette vår inntreden på I begynnelsen av denne lenket liste. 73 00:03:44,960 --> 00:03:48,600 Og så skal vi ha vår nåværende inngangspunkt til hva hashtabellen 74 00:03:48,600 --> 00:03:50,380 i dag peker på. 75 00:03:50,380 --> 00:03:53,310 Og så kommer vi til å lagre, i hashtabellen på 76 00:03:53,310 --> 00:03:55,350 hash, den gjeldende oppføringen. 77 00:03:55,350 --> 00:03:59,320 Så disse to linjene med hell sette trer ved begynnelsen av 78 00:03:59,320 --> 00:04:02,260 lenket liste ved at indeksen i hashtabellen. 79 00:04:02,260 --> 00:04:04,900 >> Når vi er ferdig med det, vi vet at vi fant et annet ord i 80 00:04:04,900 --> 00:04:07,790 ordboken, og vi øke igjen. 81 00:04:07,790 --> 00:04:13,960 Så vi fortsette med det inntil fscanf endelig tilbake noe ikke-1 i 82 00:04:13,960 --> 00:04:16,950 som peker huske at vi trenger å frigjøre oppføring. 83 00:04:16,950 --> 00:04:19,459 Så her oppe vi malloced en oppføring. 84 00:04:19,459 --> 00:04:21,329 Og vi prøvde å lese noe fra ordboken. 85 00:04:21,329 --> 00:04:23,910 Og om vi ikke lykkes lese noe fra ordboken, i 86 00:04:23,910 --> 00:04:26,650 hvilket tilfelle vi trenger å frigjøre oppføring at vi aldri faktisk satt i 87 00:04:26,650 --> 00:04:29,140 hashtabellen, og til slutt bryte. 88 00:04:29,140 --> 00:04:32,750 >> Når vi bryter ut vi trenger å se, vel, gjorde vi bryte ut fordi det 89 00:04:32,750 --> 00:04:34,360 ble en feil ved lesing fra filen? 90 00:04:34,360 --> 00:04:37,120 Eller gjorde vi bryte ut fordi vi nådd slutten av filen? 91 00:04:37,120 --> 00:04:39,480 Hvis det var en feil, så vi ønsker å returnere false. 92 00:04:39,480 --> 00:04:40,930 Fordi belastningen ikke lyktes. 93 00:04:40,930 --> 00:04:43,890 Og i den prosessen vi ønsker å losse alle ordene som vi leser i, og 94 00:04:43,890 --> 00:04:45,670 lukke ordlistefilen. 95 00:04:45,670 --> 00:04:48,740 >> Antar vi lykkes, så vi bare fortsatt trenger å lukke ordlisten 96 00:04:48,740 --> 00:04:53,040 fil, og til slutt returnere sant siden vi lastet ordlisten. 97 00:04:53,040 --> 00:04:54,420 Og det er det for last. 98 00:04:54,420 --> 00:04:59,020 Så nå sjekke, gitt en ladd hashtabellen, kommer til å se slik ut. 99 00:04:59,020 --> 00:05:03,140 Så sjekk, den returnerer en bool, som er kommer til å indikere hvorvidt passert 100 00:05:03,140 --> 00:05:07,530 i char * ord, om bestått i strengen er i vår ordbok. 101 00:05:07,530 --> 00:05:09,890 Så hvis det er i ordboken, hvis det er i vår hashtabellen, 102 00:05:09,890 --> 00:05:11,170 vi vil returnere true. 103 00:05:11,170 --> 00:05:13,380 Og hvis det ikke er det, vil vi returnere false. 104 00:05:13,380 --> 00:05:17,740 >> Gitt dette vedtatt i ord, er vi kommer til hasj ordet. 105 00:05:17,740 --> 00:05:22,110 Nå er en viktig ting å gjenkjenne er at belastningen vi visste at alle de 106 00:05:22,110 --> 00:05:23,820 ord vi skal være små bokstaver. 107 00:05:23,820 --> 00:05:25,820 Men her er vi ikke så sikker. 108 00:05:25,820 --> 00:05:29,510 Hvis vi tar en titt på vår hash-funksjon, vår hash-funksjon faktisk 109 00:05:29,510 --> 00:05:32,700 er lavere casing hvert tegn av ordet. 110 00:05:32,700 --> 00:05:37,940 Så uavhengig av kapitalisering av ord, er vår hash-funksjon retur 111 00:05:37,940 --> 00:05:42,270 den samme indeksen for uansett kapitalisering er, som det ville ha 112 00:05:42,270 --> 00:05:45,280 returneres for et helt små bokstaver versjon av ordet. 113 00:05:45,280 --> 00:05:46,600 Alright. 114 00:05:46,600 --> 00:05:49,790 Det er vår indeks er ned i Hashtabellen for dette ordet. 115 00:05:49,790 --> 00:05:52,940 >> Nå er dette for loop kommer til å iterere over lenket liste 116 00:05:52,940 --> 00:05:55,000 som var på den indeksen. 117 00:05:55,000 --> 00:05:59,610 Så oppdager vi initialisering oppføring å peke på at indeksen. 118 00:05:59,610 --> 00:06:02,750 Vi kommer til å fortsette mens oppføringen! = NULL. 119 00:06:02,750 --> 00:06:07,770 Og husk at å oppdatere pekeren i vår lenket liste entry = entry> neste. 120 00:06:07,770 --> 00:06:14,400 Så har vår nåværende inngangspunkt til det neste elementet i lenket liste. 121 00:06:14,400 --> 00:06:19,250 >> Så for hver oppføring i lenket liste, vi kommer til å bruke strcasecmp. 122 00:06:19,250 --> 00:06:20,330 Det er ikke strcomp. 123 00:06:20,330 --> 00:06:23,780 Fordi en gang, vi ønsker å gjøre ting tilfelle insensitively. 124 00:06:23,780 --> 00:06:27,870 Så vi bruker strcasecmp å sammenligne ord som ble ført gjennom denne 125 00:06:27,870 --> 00:06:31,860 funksjon mot ordet som er i dette innlegget. 126 00:06:31,860 --> 00:06:35,570 Hvis den gir null, som betyr at det var en kamp, ​​og da ønsker vi å 127 00:06:35,570 --> 00:06:36,630 returnere true. 128 00:06:36,630 --> 00:06:39,590 Vi vellykket funnet ord i vår hashtabellen. 129 00:06:39,590 --> 00:06:43,040 >> Hvis det ikke var en kamp, ​​så vi er kommer til å sløyfe igjen og se på 130 00:06:43,040 --> 00:06:43,990 neste oppføring. 131 00:06:43,990 --> 00:06:47,640 Og vi vil fortsette looping mens det er oppføringer i denne lenket liste. 132 00:06:47,640 --> 00:06:50,160 Hva skjer hvis vi bryter ut av dette for løkke? 133 00:06:50,160 --> 00:06:55,110 Det betyr at vi ikke finner en oppføring som matchet dette ordet, i så fall 134 00:06:55,110 --> 00:07:00,220 vi return false for å vise at vår hashtabellen inneholdt ikke dette ordet. 135 00:07:00,220 --> 00:07:02,540 Og det er en sjekk. 136 00:07:02,540 --> 00:07:04,790 >> Så la oss ta en titt på størrelse. 137 00:07:04,790 --> 00:07:06,970 Nå størrelse kommer til å være ganske enkel. 138 00:07:06,970 --> 00:07:11,080 Siden husker i lasten, for hvert ord Vi fant, vi økes en global 139 00:07:11,080 --> 00:07:12,880 variable hashtabellen størrelse. 140 00:07:12,880 --> 00:07:16,480 Så størrelsen funksjonen er bare kommer å 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 >> Nå endelig, trenger vi å losse ordbok når alt er ferdig. 143 00:07:22,300 --> 00:07:25,340 Så hvordan skal vi gjøre det? 144 00:07:25,340 --> 00:07:30,440 Akkurat her vi looping løpet alle bøtter av bordet vårt. 145 00:07:30,440 --> 00:07:33,240 Så det er NUM_BUCKETS bøtter. 146 00:07:33,240 --> 00:07:37,410 Og for hver lenket liste i vår hashtabellen, vi skal til løkken over 147 00:07:37,410 --> 00:07:41,070 helheten av lenket liste, frigjør hvert element. 148 00:07:41,070 --> 00:07:42,900 >> Nå må vi være forsiktige. 149 00:07:42,900 --> 00:07:47,910 Så her har vi en midlertidig variabel som er lagring pekeren til neste 150 00:07:47,910 --> 00:07:49,730 element i lenket liste. 151 00:07:49,730 --> 00:07:52,140 Og så skal vi gratis det aktuelle elementet. 152 00:07:52,140 --> 00:07:55,990 Vi må være sikker på at vi gjør dette fordi vi kan ikke bare frigjøre det aktuelle elementet 153 00:07:55,990 --> 00:07:59,180 og deretter prøve å få tilgang til neste pekeren, siden når vi har befridd det, 154 00:07:59,180 --> 00:08:00,870 minnet blir ugyldig. 155 00:08:00,870 --> 00:08:04,990 >> Så vi trenger å holde rundt en peker til neste element, så vi kan frigjøre 156 00:08:04,990 --> 00:08:08,360 gjeldende element, og da kan vi oppdatere vår nåværende element for å peke på 157 00:08:08,360 --> 00:08:09,550 det neste element. 158 00:08:09,550 --> 00:08:12,800 Vi vil sløyfe mens det er elementer i dette lenket liste. 159 00:08:12,800 --> 00:08:15,620 Vi vil gjøre det for alle knyttet lister i hashtabellen. 160 00:08:15,620 --> 00:08:19,460 Og når vi er ferdig med det, vi har helt losset hashtabellen, og 161 00:08:19,460 --> 00:08:20,190 vi er ferdige. 162 00:08:20,190 --> 00:08:23,200 Så det er umulig for losse å stadig return false. 163 00:08:23,200 --> 00:08:26,470 Og når vi er ferdige, vi bare returnere true. 164 00:08:26,470 --> 00:08:29,000 >> La oss gi denne løsningen en prøve. 165 00:08:29,000 --> 00:08:33,070 Så la oss ta en titt på hva våre struct node vil se ut. 166 00:08:33,070 --> 00:08:36,220 Her ser vi at vi kommer til å ha en bool ord og en struct node * barn 167 00:08:36,220 --> 00:08:37,470 brakett alfabetet. 168 00:08:37,470 --> 00:08:38,929 169 00:08:38,929 --> 00:08:42,020 Så det første du kan være lurer på, hvorfor er ALFABET 170 00:08:42,020 --> 00:08:44,660 ed definert som 27? 171 00:08:44,660 --> 00:08:47,900 Vel, husk at vi kommer til å trenge å være håndtering apostrof. 172 00:08:47,900 --> 00:08:51,910 Så det kommer til å bli litt av en spesialtilfelle gjennom dette programmet. 173 00:08:51,910 --> 00:08:54,710 >> Nå husker hvordan en trie faktisk fungerer. 174 00:08:54,710 --> 00:08:59,380 La oss si at vi indekserer ordet "katter." Deretter fra roten av trie, 175 00:08:59,380 --> 00:09:02,610 vi kommer til å se på barna matrise, og vi kommer til å se på 176 00:09:02,610 --> 00:09:08,090 indeks som tilsvarer bokstaven C. Så det vil bli indeksert to. 177 00:09:08,090 --> 00:09:11,530 Så gitt at, som vil gi oss en ny node. 178 00:09:11,530 --> 00:09:13,820 Og så får vi jobbe fra den noden. 179 00:09:13,820 --> 00:09:17,770 >> Så gitt at node, er vi nok en gang kommer til å se på barn array. 180 00:09:17,770 --> 00:09:22,110 Og vi kommer til å se på indeksen null for å svare til en på katten. 181 00:09:22,110 --> 00:09:27,170 Så da skal vi gå til den noden, og gitt at noden vi kommer 182 00:09:27,170 --> 00:09:31,090 å se på slutten er det en svarer til T. Og går videre til den noden, 183 00:09:31,090 --> 00:09:35,530 endelig, har vi helt sett gjennom vår ordet "katt". Og nå bool 184 00:09:35,530 --> 00:09:40,960 Ordet er ment å indikere om dette gitt ord er faktisk et ord. 185 00:09:40,960 --> 00:09:43,470 >> Så hvorfor trenger vi den spesielle saken? 186 00:09:43,470 --> 00:09:47,700 Vel hva med ordet "katastrofe" er i vår ordboken, men 187 00:09:47,700 --> 00:09:50,150 ordet "katt" er ikke det? 188 00:09:50,150 --> 00:09:54,580 Så og ønsker å se om ordet "katt" er i vår ordbok, er vi 189 00:09:54,580 --> 00:09:59,970 kommer til å lykkes se gjennom indeksene C-A-T i området node. 190 00:09:59,970 --> 00:10:04,290 Men det er bare fordi katastrofe skjedde for å skape noder på den måten 191 00:10:04,290 --> 00:10:07,190 fra C-A-T, helt til slutten av ordet. 192 00:10:07,190 --> 00:10:12,020 Så bool ordet brukes til å indikere om denne spesielle beliggenheten 193 00:10:12,020 --> 00:10:14,310 faktisk indikerer et ord. 194 00:10:14,310 --> 00:10:15,140 >> OK. 195 00:10:15,140 --> 00:10:19,310 Så nå som vi vet hva det trie er kommer til å se ut, la oss se på 196 00:10:19,310 --> 00:10:20,730 laste funksjon. 197 00:10:20,730 --> 00:10:24,610 Så last kommer til å returnere en bool for om vi lykkes eller 198 00:10:24,610 --> 00:10:26,720 uten hell lastet ordlisten. 199 00:10:26,720 --> 00:10:30,460 Og dette kommer til å være ordlisten at vi ønsker å laste. 200 00:10:30,460 --> 00:10:33,930 >> Så første vi skal gjøre er å åpne opp at ordboken for lesing. 201 00:10:33,930 --> 00:10:36,160 Og vi må sørge for at vi ikke mislykkes. 202 00:10:36,160 --> 00:10:39,580 Så hvis ordboken var ikke hell åpnet, vil den returnere 203 00:10:39,580 --> 00:10:42,400 null, og da er vi kommer til å returnere false. 204 00:10:42,400 --> 00:10:47,230 Men forutsatt at det med hell åpnet, så kan vi faktisk lese 205 00:10:47,230 --> 00:10:48,220 gjennom ordlisten. 206 00:10:48,220 --> 00:10:50,880 >> Så det første vi kommer til å ønsker å gjøre er vi har dette 207 00:10:50,880 --> 00:10:52,500 global variabel rot. 208 00:10:52,500 --> 00:10:56,190 Nå root kommer til å være en node *. 209 00:10:56,190 --> 00:10:59,760 Det er toppen av vår trie at vi er kommer til å bli itera gjennom. 210 00:10:59,760 --> 00:11:02,660 Så det første at vi skal å ønske å gjøre er å fordele 211 00:11:02,660 --> 00:11:04,140 minne for vår rot. 212 00:11:04,140 --> 00:11:07,980 Legg merke til at vi bruker den calloc funksjon, som er utgangspunktet det samme 213 00:11:07,980 --> 00:11:11,500 som malloc funksjon, bortsett fra det er garantert å returnere noe som er 214 00:11:11,500 --> 00:11:13,180 helt nullet ut. 215 00:11:13,180 --> 00:11:17,290 Så hvis vi brukte malloc, ville vi trenger å gå gjennom alle pekere i vår 216 00:11:17,290 --> 00:11:20,160 node, og sørge for at de er alle null. 217 00:11:20,160 --> 00:11:22,710 Så calloc vil gjøre det for oss. 218 00:11:22,710 --> 00:11:26,330 >> Nå akkurat som malloc, trenger vi å gjøre sikker på at tildeling var faktisk 219 00:11:26,330 --> 00:11:27,520 vellykket. 220 00:11:27,520 --> 00:11:29,990 Hvis dette returneres null, så vi må lukke eller ordbok 221 00:11:29,990 --> 00:11:32,100 fil og returnere false. 222 00:11:32,100 --> 00:11:36,835 Så anta at allokering ble vellykket, kommer vi til å bruke en node * 223 00:11:36,835 --> 00:11:40,270 markøren til reagere gjennom vår trie. 224 00:11:40,270 --> 00:11:43,890 Så våre røtter aldri kommer til å forandre seg, men vi kommer til å bruke markøren til 225 00:11:43,890 --> 00:11:47,875 faktisk gå fra node til node. 226 00:11:47,875 --> 00:11:50,940 >> Så i dette for loop vi leser gjennom ordboken filen. 227 00:11:50,940 --> 00:11:53,670 Og vi bruker fgetc. 228 00:11:53,670 --> 00:11:56,290 Fgetc kommer til å ta en enkelt karakter fra filen. 229 00:11:56,290 --> 00:11:59,370 Vi kommer til å fortsette å gripe tegn, mens vi ikke når 230 00:11:59,370 --> 00:12:01,570 slutten av filen. 231 00:12:01,570 --> 00:12:03,480 >> Det er to tilfeller vi trenger for å håndtere. 232 00:12:03,480 --> 00:12:06,610 Den første, hvis tegnet var ikke en ny linje. 233 00:12:06,610 --> 00:12:10,450 Så vi vet ikke om det var en ny linje, deretter vi er i ferd med å flytte til et nytt ord. 234 00:12:10,450 --> 00:12:15,240 Men forutsatt at det ikke var en ny linje, deretter her vi ønsker å finne ut av 235 00:12:15,240 --> 00:12:18,380 indeksen vi kommer til å indeksere inn i barn array som 236 00:12:18,380 --> 00:12:19,810 vi så på før. 237 00:12:19,810 --> 00:12:23,880 >> Så, som jeg sa før, må vi spesielt tilfelle apostrof. 238 00:12:23,880 --> 00:12:26,220 Legg merke til at vi bruker trefoldig operatør her. 239 00:12:26,220 --> 00:12:29,580 Så vi kommer til å lese dette som, hvis tegnet vi leste i var en 240 00:12:29,580 --> 00:12:35,330 apostrof, så vi kommer til å sette index = "Alphabet" -1, noe som vil 241 00:12:35,330 --> 00:12:37,680 være indeksen 26. 242 00:12:37,680 --> 00:12:41,130 >> Else, hvis det ikke var en apostrof, det vi kommer til å sette indeksen 243 00:12:41,130 --> 00:12:43,760 lik c - en. 244 00:12:43,760 --> 00:12:49,030 Så husker tilbake fra tidligere p-sett, c - en kommer til å gi oss 245 00:12:49,030 --> 00:12:53,410 alfabetisk stilling C. Så hvis C er bokstaven A, dette vil 246 00:12:53,410 --> 00:12:54,700 gi oss indeks null. 247 00:12:54,700 --> 00:12:58,120 For bokstaven B, vil det gi oss indeksen 1, og så videre. 248 00:12:58,120 --> 00:13:03,010 >> Så dette gir oss indeksen inn i barn array som vi ønsker. 249 00:13:03,010 --> 00:13:08,890 Nå hvis denne indeksen er for tiden null i barn, som betyr at en node 250 00:13:08,890 --> 00:13:11,830 øyeblikket ikke eksisterer fra denne banen. 251 00:13:11,830 --> 00:13:15,160 Så vi trenger å fordele en node for denne banen. 252 00:13:15,160 --> 00:13:16,550 Det er det vi skal gjøre her. 253 00:13:16,550 --> 00:13:20,690 >> Så vi kommer til å igjen bruke calloc funksjon, slik at vi ikke trenger å 254 00:13:20,690 --> 00:13:22,880 null ut alle pekere. 255 00:13:22,880 --> 00:13:27,240 Og vi igjen må sjekke at calloc ikke mislykkes. 256 00:13:27,240 --> 00:13:30,700 Hvis calloc gjorde mislykkes, så vi trenger å lesse alt, lukke våre 257 00:13:30,700 --> 00:13:32,820 ordbok, og return false. 258 00:13:32,820 --> 00:13:40,050 Så forutsatt at det ikke mislykkes, da Dette vil skape et nytt barn for oss. 259 00:13:40,050 --> 00:13:41,930 Og da vil vi gå til det barnet. 260 00:13:41,930 --> 00:13:44,960 Vår markøren vil iterere ned til at barnet. 261 00:13:44,960 --> 00:13:49,330 >> Nå hvis dette ikke var null til å begynne med, deretter markøren kan bare iterere 262 00:13:49,330 --> 00:13:52,590 ned til at barnet uten å faktisk å måtte fordele noe. 263 00:13:52,590 --> 00:13:56,730 Dette er tilfelle hvor vi først skjedd allokere ordet "kat." Og 264 00:13:56,730 --> 00:14:00,330 det betyr at når vi går å tildele "Katastrofe", vi trenger ikke å skape 265 00:14:00,330 --> 00:14:01,680 noder for C-A-T på nytt. 266 00:14:01,680 --> 00:14:04,830 De som allerede eksisterer. 267 00:14:04,830 --> 00:14:06,080 >> Hva er dette annet? 268 00:14:06,080 --> 00:14:10,480 Dette er den tilstand hvor c var backslash n, der c var en ny linje. 269 00:14:10,480 --> 00:14:13,710 Dette betyr at vi har lykkes gjennomført et ord. 270 00:14:13,710 --> 00:14:16,860 Nå hva vi vil gjøre når vi fullført et ord? 271 00:14:16,860 --> 00:14:21,100 Vi kommer til å bruke dette ordet feltet innsiden av våre struct node. 272 00:14:21,100 --> 00:14:23,390 Vi ønsker å sette det til sann. 273 00:14:23,390 --> 00:14:27,150 So som indikerer at denne noden indikerer en vellykket 274 00:14:27,150 --> 00:14:29,250 ord, en faktisk ord. 275 00:14:29,250 --> 00:14:30,940 >> Nå satt det til sann. 276 00:14:30,940 --> 00:14:35,150 Vi ønsker å tilbakestille vår markøren til punkt til begynnelsen av den trie nytt. 277 00:14:35,150 --> 00:14:40,160 Og til slutt, øke vår ordbok størrelse, siden vi fant en annen jobb. 278 00:14:40,160 --> 00:14:43,230 Så vi kommer til å fortsette med det, lesing i tegn for tegn, 279 00:14:43,230 --> 00:14:49,150 bygging av nye noder i vår trie og for hvert ord i ordlisten, inntil 280 00:14:49,150 --> 00:14:54,020 vi endelig kommer C! = EOF, der tilfelle vi bryte ut av filen. 281 00:14:54,020 --> 00:14:57,050 >> Nå er det to saker under som vi kan ha truffet EOF. 282 00:14:57,050 --> 00:15:00,980 Den første er om det var en feil lesing fra filen. 283 00:15:00,980 --> 00:15:03,470 Så hvis det var en feil, vi trenger å gjøre den typiske. 284 00:15:03,470 --> 00:15:06,460 Losse alt, tett filen, return false. 285 00:15:06,460 --> 00:15:09,810 Antar det ikke var en feil, at betyr bare at vi faktisk traff slutten av 286 00:15:09,810 --> 00:15:13,750 filen, og i så fall, vi lukker fil og returnere sant siden vi 287 00:15:13,750 --> 00:15:17,330 lastet ordbok inn i vår trie. 288 00:15:17,330 --> 00:15:20,170 >> Så nå la oss sjekke ut sjekken. 289 00:15:20,170 --> 00:15:25,156 Ser på sjekken funksjon, ser vi at sjekken kommer til å returnere en bool. 290 00:15:25,156 --> 00:15:29,680 Det returnerer true hvis dette ordet at det er blir vedtatt er i vår trie. 291 00:15:29,680 --> 00:15:32,110 Den returnerer false ellers. 292 00:15:32,110 --> 00:15:36,050 Så hvordan skal du finne ut om dette ordet er i vår trie? 293 00:15:36,050 --> 00:15:40,190 >> Vi ser her at, akkurat som før, vi kommer til å bruke markøren til å reagere 294 00:15:40,190 --> 00:15:41,970 gjennom vår trie. 295 00:15:41,970 --> 00:15:46,600 Nå her kommer vi til å reagere over vår hele ord. 296 00:15:46,600 --> 00:15:50,620 Så itera over ordet vi er forbi, vi kommer til å bestemme 297 00:15:50,620 --> 00:15:56,400 indeksen inn i barn array som tilsvarer ordet brakett I. Så dette 298 00:15:56,400 --> 00:15:59,670 kommer til å se ut akkurat som belastning, der hvis ordet [i] 299 00:15:59,670 --> 00:16:03,310 er en apostrof, da vi ønsker å bruke indeksen "Alphabet" - en. 300 00:16:03,310 --> 00:16:05,350 Fordi vi fastslått at det er der vi kommer til å lagre 301 00:16:05,350 --> 00:16:07,100 apostrofer. 302 00:16:07,100 --> 00:16:11,780 >> Else vi kommer til å bruke to lavere ordet brakett I. Så husk at ordet kan 303 00:16:11,780 --> 00:16:13,920 har vilkårlig kapitalisering. 304 00:16:13,920 --> 00:16:17,540 Og så ønsker vi å sørge for at vi er ved hjelp av en liten bokstav versjon av ting. 305 00:16:17,540 --> 00:16:21,920 Og deretter trekke fra det 'a' til en gang igjen gi oss den alfabetiske 306 00:16:21,920 --> 00:16:23,880 stilling av det tegnet. 307 00:16:23,880 --> 00:16:27,680 Så det kommer til å bli vår hovedside inn i barn array. 308 00:16:27,680 --> 00:16:32,420 >> Og nå om at indeksen inn barna matrise er null, betyr det at vi 309 00:16:32,420 --> 00:16:34,990 kan ikke lenger fortsette itera ned vår trie. 310 00:16:34,990 --> 00:16:38,870 Hvis det er tilfelle, dette ordet kan ikke muligens være i vår trie. 311 00:16:38,870 --> 00:16:42,340 Siden hvis det var, ville det mener det ville være en bane 312 00:16:42,340 --> 00:16:43,510 ned til det ordet. 313 00:16:43,510 --> 00:16:45,290 Og du vil aldri møte null. 314 00:16:45,290 --> 00:16:47,850 Så møter null, returnerer vi false. 315 00:16:47,850 --> 00:16:49,840 Ordet er ikke i ordboken. 316 00:16:49,840 --> 00:16:53,660 Hvis det ikke var null, så vi er kommer til å fortsette itera. 317 00:16:53,660 --> 00:16:57,220 >> Så vi går ut der markøren å peke på den aktuelle 318 00:16:57,220 --> 00:16:59,760 node på at indeksen. 319 00:16:59,760 --> 00:17:03,150 Vi fortsetter å gjøre det hele hele ordet, forutsatt 320 00:17:03,150 --> 00:17:03,950 vi aldri truffet null. 321 00:17:03,950 --> 00:17:07,220 Det betyr at vi var i stand til å komme gjennom hele ord og finne 322 00:17:07,220 --> 00:17:08,920 en node i våre forsøk. 323 00:17:08,920 --> 00:17:10,770 Men vi er ikke helt ferdig ennå. 324 00:17:10,770 --> 00:17:12,290 >> Vi ønsker ikke å bare returnere true. 325 00:17:12,290 --> 00:17:14,770 Vi ønsker å returnere markøren> ord. 326 00:17:14,770 --> 00:17:18,980 Siden huske igjen, er "cat" er ikke i vår ordbok, og "katastrofe" 327 00:17:18,980 --> 00:17:22,935 er, så vi vil lykkes får vi gjennom ordet "kat." Men markør 328 00:17:22,935 --> 00:17:25,760 Ordet vil være falske og ikke sant. 329 00:17:25,760 --> 00:17:30,930 Så vi tilbake markøren ord for å indikere vidt denne noden er faktisk et ord. 330 00:17:30,930 --> 00:17:32,470 Og det er det for sjekk. 331 00:17:32,470 --> 00:17:34,250 >> Så la oss sjekke ut størrelse. 332 00:17:34,250 --> 00:17:37,350 Så størrelsen kommer til å være ganske lett siden, husker i lasten, er vi 333 00:17:37,350 --> 00:17:41,430 økes ordbok størrelse for hvert ord som vi møter. 334 00:17:41,430 --> 00:17:45,350 Så størrelsen er bare kommer til å returnere ordbok 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å til slutt har vi losse. 337 00:17:50,590 --> 00:17:55,100 Så losse, kommer vi til å bruke en rekursiv funksjon å faktisk gjøre alt 338 00:17:55,100 --> 00:17:56,530 av jobben for oss. 339 00:17:56,530 --> 00:17:59,340 Så vår funksjon skal bli kalt på losser. 340 00:17:59,340 --> 00:18:01,650 Hva er losser kommer til å gjøre? 341 00:18:01,650 --> 00:18:06,580 Vi ser her at unloader kommer til å iterere over alle barna på 342 00:18:06,580 --> 00:18:08,410 denne noden. 343 00:18:08,410 --> 00:18:11,750 Og hvis barnet noden er ikke null, så vi kommer til å 344 00:18:11,750 --> 00:18:13,730 losse barnet node. 345 00:18:13,730 --> 00:18:18,010 >> Så dette er du rekursivt losse alle våre barn. 346 00:18:18,010 --> 00:18:21,080 Når vi er sikker på at alle våre barn har blitt losset, så vi 347 00:18:21,080 --> 00:18:25,210 kan frigjøre oss, så losse oss selv. 348 00:18:25,210 --> 00:18:29,460 Dette vil fungere rekursivt losse hele trie. 349 00:18:29,460 --> 00:18:32,850 Og så når det er gjort, vi kan bare returnere true. 350 00:18:32,850 --> 00:18:34,210 Losse kan ikke mislykkes. 351 00:18:34,210 --> 00:18:35,710 Vi bare frigjøre ting. 352 00:18:35,710 --> 00:18:38,870 Så når vi er ferdig å frigjøre alt, returnere true. 353 00:18:38,870 --> 00:18:40,320 Og det er det. 354 00:18:40,320 --> 00:18:41,080 Mitt navn er Rob. 355 00:18:41,080 --> 00:18:42,426 Og dette var stavekontroll. 356 00:18:42,426 --> 00:18:47,830 >> [Musikk spilles]