1 00:00:00,000 --> 00:00:09,700 2 00:00:09,700 --> 00:00:12,140 >> ZAMYLA CHAN: La oss gjøre en stavekontroll. 3 00:00:12,140 --> 00:00:16,900 Hvis du åpner speller.c, så vil du se at det meste av funksjonalitet for 4 00:00:16,900 --> 00:00:20,810 sjekker en tekstfil mot en ordbok er allerede gjort for deg. 5 00:00:20,810 --> 00:00:26,330 . / Stavekontroll, passerer i en ordbok tekst fil og deretter en annen tekstfil, 6 00:00:26,330 --> 00:00:28,960 vil sjekke at tekstfil mot ordlisten. 7 00:00:28,960 --> 00:00:34,160 >> Nå vil ordbok tekstfiler inneholder gyldige ord, ett per linje. 8 00:00:34,160 --> 00:00:37,910 Deretter vil speller.c ringe Load på ordlisten tekstfil. 9 00:00:37,910 --> 00:00:43,650 Det vil kalle en funksjon kalt Sjekk på hvert ord i inputted tekstfil, 10 00:00:43,650 --> 00:00:46,460 utskrift av alle feilstavede ord. 11 00:00:46,460 --> 00:00:50,030 >> Speller.c vil også ringe størrelse til bestemme antall ord i 12 00:00:50,030 --> 00:00:53,500 ordbok og ringe Last ut å frigjøre minne. 13 00:00:53,500 --> 00:00:57,600 speller.c vil også holde styr på hvor mye tid blir brukt til å drive disse 14 00:00:57,600 --> 00:01:00,560 prosesser, men vi vil komme til det senere. 15 00:01:00,560 --> 00:01:02,440 >> Så hva trenger vi å gjøre? 16 00:01:02,440 --> 00:01:05,110 Vi trenger å fylle ut dictionary.c. 17 00:01:05,110 --> 00:01:09,940 I dictionary.c, har vi hjelperen funksjon Load, som laster 18 00:01:09,940 --> 00:01:10,855 ordbok. 19 00:01:10,855 --> 00:01:15,490 Funksjonen Check, som sjekker om et gitt ord er i ordboken. 20 00:01:15,490 --> 00:01:19,150 Funksjonen Size returnerer antall av ord i ordboken. 21 00:01:19,150 --> 00:01:24,870 Og til slutt, har vi losse, som frigjør ordlisten fra minnet. 22 00:01:24,870 --> 00:01:27,070 >> Så først, la oss takle Load. 23 00:01:27,070 --> 00:01:32,110 For hvert ord i ordlisten tekst fil, vil Load lagre disse ordene i 24 00:01:32,110 --> 00:01:34,860 ordlisten datastruktur som du selv velger, enten en 25 00:01:34,860 --> 00:01:36,750 hash tabell eller en trie. 26 00:01:36,750 --> 00:01:39,440 Jeg skal gå over både i dette går gjennom. 27 00:01:39,440 --> 00:01:43,150 >> Først la oss snakke om hash tabeller. 28 00:01:43,150 --> 00:01:47,050 Si at du hadde 10 billiard baller og du ønsket å lagre dem. 29 00:01:47,050 --> 00:01:50,420 Du kan sette dem alle i en bøtte, og når du trengte en bestemt 30 00:01:50,420 --> 00:01:54,010 nummerert ball, vil du ta en ut av skuffen om gangen 31 00:01:54,010 --> 00:01:55,880 på jakt etter den ballen. 32 00:01:55,880 --> 00:01:59,370 Og med bare 10 baller, bør du være i stand til å finne ballen din i en rimelig 33 00:01:59,370 --> 00:02:01,160 tidsperiode. 34 00:02:01,160 --> 00:02:03,180 >> Men hva hvis du hadde 20 baller? 35 00:02:03,180 --> 00:02:05,480 Det kan ta litt lengre tid nå. 36 00:02:05,480 --> 00:02:06,180 Hva med 100? 37 00:02:06,180 --> 00:02:07,880 1000? 38 00:02:07,880 --> 00:02:11,590 Nå ville det være mye lettere hvis du hadde flere bøtter. 39 00:02:11,590 --> 00:02:15,890 Kanskje en bøtte for baller nummerert fra null gjennom ni, en annen bøtte for 40 00:02:15,890 --> 00:02:18,800 baller nummerert 10 gjennom 19, og så videre. 41 00:02:18,800 --> 00:02:22,330 >> Nå når du trengte å lete etter spesifikke ball, kan du automatisk 42 00:02:22,330 --> 00:02:26,320 gå til en bestemt bøtte og søke gjennom at bøtte. 43 00:02:26,320 --> 00:02:29,840 Og hvis hver bøtte har ca 10 baller, så du kan enkelt søke 44 00:02:29,840 --> 00:02:31,790 gjennom den. 45 00:02:31,790 --> 00:02:34,960 >> Nå, siden vi har med å gjøre ordbøker, én bøtte for 46 00:02:34,960 --> 00:02:41,970 alle ordene i ordlisten vil sannsynligvis være altfor få bøtter. 47 00:02:41,970 --> 00:02:44,370 Så la oss ta en titt på hash tabeller. 48 00:02:44,370 --> 00:02:46,940 >> Tenk på det som en matrise av bøtter. 49 00:02:46,940 --> 00:02:50,370 Og i dette tilfellet, de bøtter er våre lenkede lister. 50 00:02:50,370 --> 00:02:54,770 Og vi vil distribuere alle våre ord blant disse flere lenkede lister i 51 00:02:54,770 --> 00:02:58,940 en organisert måte ved hjelp av en hash-funksjon, som vil fortelle oss hvilke 52 00:02:58,940 --> 00:03:03,720 bøtte en gitt nøkkel, en gitt ord, tilhører. 53 00:03:03,720 --> 00:03:05,960 >> La oss representerer dette skjematisk. 54 00:03:05,960 --> 00:03:11,320 De blå boksene her inneholder verdier og røde boksene peker til en annen verdi 55 00:03:11,320 --> 00:03:12,280 pekeren pair. 56 00:03:12,280 --> 00:03:14,800 Vi kaller disse parene noder. 57 00:03:14,800 --> 00:03:18,260 Nå, hver bøtte, som jeg sa tidligere, er en lenket liste. 58 00:03:18,260 --> 00:03:21,820 I lenkede lister, har hver node en verdi, samt en peker til 59 00:03:21,820 --> 00:03:23,170 neste verdi. 60 00:03:23,170 --> 00:03:26,150 >> Nå arbeider med koblede lister, det er svært viktig at du 61 00:03:26,150 --> 00:03:28,120 ikke mister noen linker. 62 00:03:28,120 --> 00:03:32,250 Og et annet faktum å huske er at siste node, hvis det ikke peker til 63 00:03:32,250 --> 00:03:35,120 en annen node, peker på null. 64 00:03:35,120 --> 00:03:37,970 >> Så hvordan skal vi representerer dette i C? 65 00:03:37,970 --> 00:03:40,540 Vi definerer vår struct her. 66 00:03:40,540 --> 00:03:44,850 Og verdien i dette tilfellet er en røye array av lengde. 67 00:03:44,850 --> 00:03:48,880 Lengde pluss 1, hvor lengden er Maksimal lengde på noen ord, pluss en for 68 00:03:48,880 --> 00:03:50,380 den avsluttende null. 69 00:03:50,380 --> 00:03:54,210 Og så har vi en peker til en annen node kalt Next. 70 00:03:54,210 --> 00:03:56,730 >> Så la oss gjøre et lite lenket liste. 71 00:03:56,730 --> 00:04:00,390 Først vil du ønsker å malloc din noden, som skaper plass i minnet på 72 00:04:00,390 --> 00:04:04,010 størrelsen på nodetypen. 73 00:04:04,010 --> 00:04:06,100 Og foreta en ny node, igjen mallocing. 74 00:04:06,100 --> 00:04:09,370 75 00:04:09,370 --> 00:04:14,340 >> Nå hvis du ønsker å tilordne en verdi til en Ordet, så vi kan si node1 pil 76 00:04:14,340 --> 00:04:18,820 Ordet er lik "Hei." Denne pilen operatør dereferences pekeren og 77 00:04:18,820 --> 00:04:20,620 aksesserer struct variabler. 78 00:04:20,620 --> 00:04:24,330 På denne måten trenger vi ikke å bruke både prikken og stjernen operatør. 79 00:04:24,330 --> 00:04:30,100 >> Så da har jeg node2 pil ord lik "Verden." Og det er verdiene 80 00:04:30,100 --> 00:04:33,110 befolket i mine noder. 81 00:04:33,110 --> 00:04:38,780 For å gjøre koblingene, vil jeg passere i node1 arrow neste, tilgangen til denne noden stjerne, 82 00:04:38,780 --> 00:04:44,160 at node pekeren, lik node2, peker node1 å node2 to. 83 00:04:44,160 --> 00:04:46,360 Og der har vi en lenket liste. 84 00:04:46,360 --> 00:04:51,480 >> Så det var bare en lenket liste, men en hash table er en hel rekke 85 00:04:51,480 --> 00:04:52,520 lenkede lister. 86 00:04:52,520 --> 00:04:55,920 Vel, vi har den samme node strukturere som før. 87 00:04:55,920 --> 00:05:00,140 Men hvis vi ønsket en faktisk hash table, da kan vi bare gjøre en node peker 88 00:05:00,140 --> 00:05:01,330 matrise her. 89 00:05:01,330 --> 00:05:04,940 For eksempel, størrelsen 500. 90 00:05:04,940 --> 00:05:08,910 >> Nå varsel, kommer det til å være en avveining off mellom størrelsen på 91 00:05:08,910 --> 00:05:11,280 nøkkeltabell og størrelsen av dine lenkede lister. 92 00:05:11,280 --> 00:05:15,640 Hvis du har et virkelig høyt antall bøtter, forestille å måtte kjøre tilbake 93 00:05:15,640 --> 00:05:18,230 og tilbake i en linje for å finn din bøtte. 94 00:05:18,230 --> 00:05:21,530 Men du også ønsker ikke et lite antall av bøtter, for da er vi tilbake til 95 00:05:21,530 --> 00:05:26,850 den opprinnelige problemet med hvordan ha altfor mange baller i vår bøtte. 96 00:05:26,850 --> 00:05:30,480 >> OK, men hvor kommer vår ballen gå? 97 00:05:30,480 --> 00:05:33,150 Vel, må vi først har en ball, ikke sant? 98 00:05:33,150 --> 00:05:39,130 Så la oss malloc en node for hver nytt ord som vi har. 99 00:05:39,130 --> 00:05:42,900 node * new_node likemenn malloc (sizeof (node)). 100 00:05:42,900 --> 00:05:46,760 >> Nå som vi har denne strukturen, vi kan skanne inn ved hjelp av funksjonen 101 00:05:46,760 --> 00:05:51,850 fscanf, en streng fra vår fil, hvis det er en ordbok fil, inn 102 00:05:51,850 --> 00:05:55,780 new_node pil ord, hvor new_node pil ord er vår 103 00:05:55,780 --> 00:05:58,110 målet for det ordet. 104 00:05:58,110 --> 00:06:01,900 >> Deretter vil vi ønsker til hasj som ordet med en hash-funksjon. 105 00:06:01,900 --> 00:06:05,860 En hash-funksjon tar en streng og returnerer en indeks. 106 00:06:05,860 --> 00:06:09,760 I dette tilfellet har indeksen til være mindre enn antallet 107 00:06:09,760 --> 00:06:11,440 bøtter som du har. 108 00:06:11,440 --> 00:06:14,600 >> Nå, hash funksjoner, når du prøver å finne en og skape en av 109 00:06:14,600 --> 00:06:17,890 din egen, husk at de må være deterministisk. 110 00:06:17,890 --> 00:06:22,420 Det betyr at den samme verdi må kart til samme bøtte hver gang 111 00:06:22,420 --> 00:06:23,800 at du hash det. 112 00:06:23,800 --> 00:06:25,300 >> Det er litt som et bibliotek. 113 00:06:25,300 --> 00:06:28,560 Når du tar en bok, basert på forfatter, vet du hvilken hylle den skal 114 00:06:28,560 --> 00:06:31,890 gå på, enten det er hyllenummer en, to, eller tre. 115 00:06:31,890 --> 00:06:36,280 Og at boken vil alltid hører hjemme på enten hylle en, to, eller tre. 116 00:06:36,280 --> 00:06:39,460 117 00:06:39,460 --> 00:06:43,810 >> Så, har hvis new_node pil ordet ord fra ordboken, deretter 118 00:06:43,810 --> 00:06:47,770 hashing new_node pil ord vil gi oss indeksen for 119 00:06:47,770 --> 00:06:49,370 bøtte med hash tabellen. 120 00:06:49,370 --> 00:06:54,040 Og så får vi sette det inn i den spesifikke lenket liste indikeres av 121 00:06:54,040 --> 00:06:56,060 returnere verdien av vår hash-funksjon. 122 00:06:56,060 --> 00:06:59,070 >> La oss se på et eksempel på sette inn en node inn i 123 00:06:59,070 --> 00:07:01,750 begynnelsen av en lenket liste. 124 00:07:01,750 --> 00:07:06,930 Hvis hodet er en node peker som angir I begynnelsen av en koblet 125 00:07:06,930 --> 00:07:12,420 liste, og new_node angir nye node som du ønsker å komme inn, bare 126 00:07:12,420 --> 00:07:17,340 tildele hodet til new_node ville miste koblingen til resten av listen. 127 00:07:17,340 --> 00:07:19,330 Så vi ønsker ikke å gjøre dette. 128 00:07:19,330 --> 00:07:22,160 >> Snarere ønsker vi å sørge for at at vi holder fast ved hver 129 00:07:22,160 --> 00:07:23,550 enkelt node i vårt program. 130 00:07:23,550 --> 00:07:29,560 Så kjører new_node pilen ved likhets hodet og deretter hodet tilsvarer new_node 131 00:07:29,560 --> 00:07:34,470 vil bevare alle linker og ikke miste noen. 132 00:07:34,470 --> 00:07:39,330 >> Men hva hvis du vil at listen for å være sortert, fordi det å ha en sortert knyttet 133 00:07:39,330 --> 00:07:42,910 Listen kan være lettere for søker det senere? 134 00:07:42,910 --> 00:07:46,020 Vel, for det, vil du trenger å vite hvordan å traversere lenkede lister. 135 00:07:46,020 --> 00:07:51,210 >> Å krysse en lenket liste, la oss ha en node peker, en node *, for å fungere som 136 00:07:51,210 --> 00:07:54,120 markøren, som angir hvilke node du er på, starter 137 00:07:54,120 --> 00:07:55,460 på det første element. 138 00:07:55,460 --> 00:08:01,070 Looping inntil markøren er null, kan vi gjennomføre visse prosesser og deretter 139 00:08:01,070 --> 00:08:04,330 flytte markøren når vi trenger bruker markørpilen verdi. 140 00:08:04,330 --> 00:08:08,820 >> Husk, dette er det samme som sier stjerne markøren, dereferencing 141 00:08:08,820 --> 00:08:13,480 markøren, deretter bruke dot operatør verdi. 142 00:08:13,480 --> 00:08:19,000 Så oppdaterer markøren ved å tildele markøren til markørpilen ved. 143 00:08:19,000 --> 00:08:24,960 >> Si du finner ut at D blir i mellom C og E. For å sette noden, 144 00:08:24,960 --> 00:08:30,030 har new_node D punktet til node E, som er markøren ved siden av. 145 00:08:30,030 --> 00:08:36,409 Og så C, markøren, kan deretter peke til D. På den måten opprettholder du en liste. 146 00:08:36,409 --> 00:08:41,080 Vær forsiktig så du ikke mister koblingene ved flytte markøren pilen ved siden av D 147 00:08:41,080 --> 00:08:43,929 med en gang. 148 00:08:43,929 --> 00:08:44,620 >> OK. 149 00:08:44,620 --> 00:08:48,920 Så det er slik du kan sette noder, laste dem inn, last ord inn i de 150 00:08:48,920 --> 00:08:51,600 noder, og sett dem inn i hash table. 151 00:08:51,600 --> 00:08:53,580 Så nå la oss se på prøver. 152 00:08:53,580 --> 00:08:58,540 >> I en trie, vil hver node inneholde en rekke node pekere, en for hver 153 00:08:58,540 --> 00:09:02,260 bokstav i alfabetet pluss en apostrof. 154 00:09:02,260 --> 00:09:06,150 Og hvert element i matrisen vil peke til en annen node. 155 00:09:06,150 --> 00:09:10,130 Hvis det node er null, så det brevet ikke kommer til å bli den neste bokstaven 156 00:09:10,130 --> 00:09:15,690 noen ord i en sekvens, fordi hver Ordet viser om det er den siste 157 00:09:15,690 --> 00:09:18,160 karakter av et ord eller ikke. 158 00:09:18,160 --> 00:09:19,750 >> La oss se på et diagram. 159 00:09:19,750 --> 00:09:22,260 Forhåpentligvis vil ting være litt klarere. 160 00:09:22,260 --> 00:09:27,210 I dette diagrammet ser vi at bare bestemte bokstaver og enkelte dels 161 00:09:27,210 --> 00:09:28,190 blir listet ut. 162 00:09:28,190 --> 00:09:32,500 Så du kan følge visse stier, og alle disse banene vil lede deg til 163 00:09:32,500 --> 00:09:34,020 forskjellige ord. 164 00:09:34,020 --> 00:09:37,630 >> Så hvordan skal vi representerer dette i C? 165 00:09:37,630 --> 00:09:41,910 Vel, hver node nå kommer til å ha en boolsk verdi som angir om 166 00:09:41,910 --> 00:09:46,580 at noden er slutten av et gitt ord eller ikke. 167 00:09:46,580 --> 00:09:50,690 Og så det vil også ha en rekke node pekere kalt barn, og 168 00:09:50,690 --> 00:09:53,440 det kommer til å være 27 av dem. 169 00:09:53,440 --> 00:09:56,510 Og husk, du vil også være lurt å holde styr på din første noden. 170 00:09:56,510 --> 00:09:59,830 Vi kommer til å kalle det rot. 171 00:09:59,830 --> 00:10:01,690 >> Så det er strukturen i en trie. 172 00:10:01,690 --> 00:10:05,630 Hvordan kan vi representerer dette som en ordbok? 173 00:10:05,630 --> 00:10:09,890 Vel, for å laste ord i, for hver ordbok ord, du kommer til å ønske 174 00:10:09,890 --> 00:10:11,960 å reagere gjennom den trie. 175 00:10:11,960 --> 00:10:16,170 Og hvert element i barna svarer til en annen bokstav. 176 00:10:16,170 --> 00:10:21,660 >> Så sjekker verdien på barn indeksen i, hvor jeg representerer 177 00:10:21,660 --> 00:10:24,840 nærmere angitt indeks av brevet at du prøver å sette inn. 178 00:10:24,840 --> 00:10:28,980 Vel, hvis det er null, så vil du ønsker å malloc en ny node og har barn 179 00:10:28,980 --> 00:10:31,110 Jeg peker på at node. 180 00:10:31,110 --> 00:10:35,630 >> Hvis det ikke er null, så det betyr at at gitt gren, at gitt 181 00:10:35,630 --> 00:10:37,350 delstreng, finnes allerede. 182 00:10:37,350 --> 00:10:40,160 Så da vil du bare flytte til at ny node og fortsetter. 183 00:10:40,160 --> 00:10:43,220 Hvis du er på slutten av ordet som du prøver å laste inn i 184 00:10:43,220 --> 00:10:48,120 ordbok, så kan du sette at gjeldende node at du er på å true. 185 00:10:48,120 --> 00:10:51,550 >> Så la oss se på et eksempel på å sette inn ordet "rev" i vår 186 00:10:51,550 --> 00:10:53,070 ordbok. 187 00:10:53,070 --> 00:10:56,110 Lat som vi starter med en tom ordbok. 188 00:10:56,110 --> 00:11:01,610 Den første bokstaven, F, vil bli plassert hos barn indeks fem av røttene 189 00:11:01,610 --> 00:11:03,700 barn array. 190 00:11:03,700 --> 00:11:05,430 Så vi setter det i. 191 00:11:05,430 --> 00:11:14,610 >> Bokstaven O vil da være i barn indeks 15, etter at F. Og så X 192 00:11:14,610 --> 00:11:20,180 vil bli enda under det, forgrener ut av Os barn. 193 00:11:20,180 --> 00:11:24,120 Og så fordi X er den siste bokstaven av ordet "rev", så jeg kommer til å 194 00:11:24,120 --> 00:11:27,210 farge som grønt for å indikere at det er slutten av ordet. 195 00:11:27,210 --> 00:11:32,880 I C, ville det være å sette Is Word boolsk til verdien true. 196 00:11:32,880 --> 00:11:36,780 >> Hva nå hvis det neste ordet som du er lasting i er ordet "foo"? 197 00:11:36,780 --> 00:11:41,490 Vel, du trenger ikke å malloc noe mer plass for F eller for O, fordi 198 00:11:41,490 --> 00:11:42,990 de som allerede eksisterer. 199 00:11:42,990 --> 00:11:45,910 Men den siste O i foo? 200 00:11:45,910 --> 00:11:47,320 At man, må du malloc. 201 00:11:47,320 --> 00:11:52,390 Lag en ny node for det, innstilling Is Word boolsk til sann. 202 00:11:52,390 --> 00:11:57,340 >> Så nå skal vi sette inn "hund". Dog vil starte med indeks tre av røttene 203 00:11:57,340 --> 00:12:00,520 barn, fordi D har ikke er laget ennå. 204 00:12:00,520 --> 00:12:04,990 Og vi vil følge en tilsvarende prosess som før, skaper substrengen hund, 205 00:12:04,990 --> 00:12:10,400 hvor er G er farget grønt fordi det er slutten av et ord. 206 00:12:10,400 --> 00:12:13,160 >> Nå, hva om vi ønsker å sette inn "gjøre"? 207 00:12:13,160 --> 00:12:17,150 Vel, dette er en delstreng av hund, så vi trenger ikke å malloc lenger. 208 00:12:17,150 --> 00:12:20,800 Men vi trenger ikke å indikere hvor vi har nådd slutten av det ordet. 209 00:12:20,800 --> 00:12:24,020 Så O vil bli farget grønn. 210 00:12:24,020 --> 00:12:27,810 Fortsetter denne prosessen for hver enkelt ord i ordlisten, har du 211 00:12:27,810 --> 00:12:32,120 lastet dem inn i enten ditt hash table eller din trie. 212 00:12:32,120 --> 00:12:37,530 >> speller.c vil passere i strenger for dictionary.c å sjekke dem. 213 00:12:37,530 --> 00:12:41,140 Nå har Check-funksjonen for å operere henhold tilfelle ufølsomhet. 214 00:12:41,140 --> 00:12:45,980 Det betyr at store bokstaver og små bokstaver og en blanding av begge deler 215 00:12:45,980 --> 00:12:50,670 bør alle likestille til sann hvis noen kombinasjon av det som er i 216 00:12:50,670 --> 00:12:51,880 ordbok. 217 00:12:51,880 --> 00:12:55,580 Du kan også anta at strengene er bare kommer til å inneholde alfabetisk 218 00:12:55,580 --> 00:12:58,200 tegn eller apostrofer. 219 00:12:58,200 --> 00:13:02,490 >> Så la oss se på hvordan du kan sjekke med en hash tabell struktur. 220 00:13:02,490 --> 00:13:07,330 Vel, hvis ordet finnes, så det kan finnes i nøkkeltabell. 221 00:13:07,330 --> 00:13:12,240 Så da kan du prøve å finne at ordet i det aktuelle skuffe. 222 00:13:12,240 --> 00:13:14,480 >> Så hvilken bøtte ville det ordet være i? 223 00:13:14,480 --> 00:13:20,060 Vel, vil du få antall, at indeksen av bøtta, ved hashing det ordet 224 00:13:20,060 --> 00:13:23,690 og deretter søke i det lenket liste, krysser gjennom hele 225 00:13:23,690 --> 00:13:28,060 lenket liste, ved hjelp av String Sammenligne funksjon. 226 00:13:28,060 --> 00:13:31,940 >> Hvis slutten av lenket liste er nådd, noe som betyr at markøren 227 00:13:31,940 --> 00:13:36,030 når null, da ordet ikke å finne i ordlisten. 228 00:13:36,030 --> 00:13:39,090 Det vil ikke være i en hvilken som helst annen bøtte. 229 00:13:39,090 --> 00:13:43,020 Så her kan du se hvordan det kan være en avveining mellom å ha enten 230 00:13:43,020 --> 00:13:46,280 sortert lenkede lister eller usorterte seg. 231 00:13:46,280 --> 00:13:51,180 Enten vil ta mer tid under laste eller mer tid under innsjekking. 232 00:13:51,180 --> 00:13:53,560 >> Hvordan kan du sjekke inn en trie struktur? 233 00:13:53,560 --> 00:13:56,370 Vi kommer til å reise nedover i trie. 234 00:13:56,370 --> 00:14:00,390 For hver bokstav i inputted ordet at vi sjekker, vil vi gå til det 235 00:14:00,390 --> 00:14:03,280 tilsvarende element i barna. 236 00:14:03,280 --> 00:14:07,770 >> Hvis dette elementet er null, så det betyr at det ikke er noen dels 237 00:14:07,770 --> 00:14:11,110 inneholder våre innspill ord, så ordet er feilstavet. 238 00:14:11,110 --> 00:14:15,140 Hvis det ikke er null, kan vi flytte til neste bokstav i ordet at vi er 239 00:14:15,140 --> 00:14:18,850 kontroll og fortsette denne prosessen før vi når slutten 240 00:14:18,850 --> 00:14:20,350 av inngangsordet. 241 00:14:20,350 --> 00:14:23,330 Og så kan vi sjekke If er Word er sant. 242 00:14:23,330 --> 00:14:24,610 Hvis det er, så flott. 243 00:14:24,610 --> 00:14:25,590 Ordet er riktig. 244 00:14:25,590 --> 00:14:30,890 Men hvis ikke, selv om det substring eksisterer i trie, er ordet 245 00:14:30,890 --> 00:14:32,250 feilstavet. 246 00:14:32,250 --> 00:14:36,590 >> Når funksjonen Size kalles, størrelse skal returnere antall ord som 247 00:14:36,590 --> 00:14:39,110 er i din gitt ordbok datastruktur. 248 00:14:39,110 --> 00:14:42,780 Så hvis du bruker en hash table, du kan enten gå gjennom hver enkelt 249 00:14:42,780 --> 00:14:45,860 lenket liste i hver enkelt bøtte telle antall 250 00:14:45,860 --> 00:14:47,130 av ordene er der. 251 00:14:47,130 --> 00:14:49,940 Hvis du bruker en trie, kan du gå gjennom alle ikke null 252 00:14:49,940 --> 00:14:52,030 banen i din trie. 253 00:14:52,030 --> 00:14:56,420 Eller mens du laster ordlisten i, kanskje du kan holde styr på hvor 254 00:14:56,420 --> 00:14:58,760 mange ord du lasting i. 255 00:14:58,760 --> 00:15:03,180 >> Når speller.c ferdig sjekke tekstfil mot ordboken, deretter 256 00:15:03,180 --> 00:15:08,010 det er gjort og så det kaller losse, hvor din jobb er å frigjøre noe 257 00:15:08,010 --> 00:15:09,500 at du har malloced. 258 00:15:09,500 --> 00:15:14,420 Så hvis du bruker en hash table, så du må være spesielt nøye med å unngå 259 00:15:14,420 --> 00:15:18,830 minnelekkasjer ved ikke å frigjøre noe tidlig og holder på hver 260 00:15:18,830 --> 00:15:20,780 single link før du gratis. 261 00:15:20,780 --> 00:15:24,680 262 00:15:24,680 --> 00:15:30,100 >> Så for hvert element i hash table og for hver node i lenket liste, 263 00:15:30,100 --> 00:15:32,370 vil du ønsker å frigjøre den noden. 264 00:15:32,370 --> 00:15:34,970 Hvordan du går om å frigjøre en lenket liste? 265 00:15:34,970 --> 00:15:38,570 Innstilling din node pekeren til hodet, til begynnelsen av 266 00:15:38,570 --> 00:15:43,100 lenket liste, deretter mens markøren er ikke null, kan du sette en midlertidig 267 00:15:43,100 --> 00:15:45,610 node pekeren til markøren. 268 00:15:45,610 --> 00:15:48,370 Deretter flytte markøren. 269 00:15:48,370 --> 00:15:52,950 Og så kan du frigjøre at midlertidig verdi mens du fremdeles holder på å 270 00:15:52,950 --> 00:15:55,650 alt etterpå. 271 00:15:55,650 --> 00:15:57,800 >> Hva hvis du bruker en trie? 272 00:15:57,800 --> 00:16:00,410 Så den beste måten å gjøre dette er å losse fra selve 273 00:16:00,410 --> 00:16:02,290 bunnen til toppen. 274 00:16:02,290 --> 00:16:06,920 Ved å reise til lavest mulig node, kan du frigjøre alle pekere i 275 00:16:06,920 --> 00:16:11,430 at barn og deretter backtrack oppover, frigjør alle elementene i alle 276 00:16:11,430 --> 00:16:15,610 av barnas arrays, inntil du treffer din topp rotnoden. 277 00:16:15,610 --> 00:16:18,920 Her er der Rekursjon vil komme godt med. 278 00:16:18,920 --> 00:16:22,780 >> For å være sikker på at du har sikkert frigjort alt som du har malloced, 279 00:16:22,780 --> 00:16:24,400 du kan bruke Valgrind. 280 00:16:24,400 --> 00:16:28,640 Kjører Valgrind vil kjøre programmet telle hvor mange byte minne 281 00:16:28,640 --> 00:16:32,440 du bruker, og å sørge for at du har frigjort dem alle, forteller deg 282 00:16:32,440 --> 00:16:34,530 hvor du kan ha glemt å fri. 283 00:16:34,530 --> 00:16:38,390 Så kjører det og når Valgrind forteller deg og gir deg klarsignal, deretter 284 00:16:38,390 --> 00:16:41,160 du er ferdig med å losse. 285 00:16:41,160 --> 00:16:44,420 >> Nå, et par tips før du går av og begynne å implementere din 286 00:16:44,420 --> 00:16:46,260 ordbok. 287 00:16:46,260 --> 00:16:49,650 Jeg vil anbefale å passere i en mindre ordbok når du prøver å teste 288 00:16:49,650 --> 00:16:52,620 ting ut og debugging med BNP. 289 00:16:52,620 --> 00:16:58,550 Bruken av stavekontroll er. / Stavekontroll, en valgfritt ordbok, og deretter en tekst. 290 00:16:58,550 --> 00:17:01,550 >> Som standard laster det i den store ordbok. 291 00:17:01,550 --> 00:17:06,670 Så kan det være lurt å passere i den lille ordlisten, eller kanskje til og med lage din 292 00:17:06,670 --> 00:17:11,819 egne, tilpasse ordbok og tekstfilen. 293 00:17:11,819 --> 00:17:15,950 >> Og så til slutt, jeg vil også anbefale å ta en penn og papir og tegne 294 00:17:15,950 --> 00:17:20,490 ting ut før, under og etter du har skrevet alt av koden din. 295 00:17:20,490 --> 00:17:24,170 Bare sørg for at du har fått disse pekere akkurat. 296 00:17:24,170 --> 00:17:26,480 >> Jeg ønsker deg lykke til. 297 00:17:26,480 --> 00:17:29,690 Og når du er ferdig, hvis du ønsker å utfordre den store bord og 298 00:17:29,690 --> 00:17:34,390 se hvor fort programmet er i forhold til klassekameratene dine ', så jeg oppfordrer 299 00:17:34,390 --> 00:17:35,960 deg til å sjekke det ut. 300 00:17:35,960 --> 00:17:39,220 >> Med det, er du ferdig stavekontrollen PSett. 301 00:17:39,220 --> 00:17:41,800 Mitt navn er Zamyla, og dette er CS50. 302 00:17:41,800 --> 00:17:49,504