1 00:00:00,000 --> 00:00:12,350 >> [MUSIC nagpe-play] 2 00:00:12,350 --> 00:00:13,050 >> Rob BOWDEN: Hi. 3 00:00:13,050 --> 00:00:13,640 Ako Rob. 4 00:00:13,640 --> 00:00:16,210 At sabihin na solusyon na ito out. 5 00:00:16,210 --> 00:00:20,070 Kaya dito kami ay pagpunta sa ipatupad isang pangkalahatang table. 6 00:00:20,070 --> 00:00:24,090 Nakita namin na ang struct node ng aming talahanayan ay pagpunta sa ganito ang hitsura. 7 00:00:24,090 --> 00:00:28,710 Kaya ito ay pagpunta sa magkaroon ng isang pansamantalang trabaho salita hanay ng mga laki LENGTH + 1. 8 00:00:28,710 --> 00:00:32,259 Huwag kalimutan ang + 1, dahil ang maximum salita sa diksyunaryo ay 45 9 00:00:32,259 --> 00:00:33,130 character. 10 00:00:33,130 --> 00:00:37,070 At pagkatapos ay kami ay pagpunta sa kailangan isang extrang character para sa backslash zero. 11 00:00:37,070 --> 00:00:40,870 >> At pagkatapos ay aming hashtable sa bawat bucket ay pagpunta sa mag-imbak ng 12 00:00:40,870 --> 00:00:42,320 naka-link na listahan ng mga node. 13 00:00:42,320 --> 00:00:44,420 Kami ay hindi gumagawa ng linear probing dito. 14 00:00:44,420 --> 00:00:48,430 At kaya upang mai-link sa susunod sangkap sa mga bucket, kailangan namin ng isang 15 00:00:48,430 --> 00:00:50,390 struct node * susunod. 16 00:00:50,390 --> 00:00:51,110 OK. 17 00:00:51,110 --> 00:00:53,090 Kaya na kung ano ang hitsura ng isang node tulad. 18 00:00:53,090 --> 00:00:56,180 >> Ngayon dito ay ang deklarasyon sa aming mga hashtable. 19 00:00:56,180 --> 00:00:59,640 Ito ay pagpunta sa may 16,834 mga bucket. 20 00:00:59,640 --> 00:01:01,910 Ngunit ang numerong iyon ay hindi talagang mahalaga. 21 00:01:01,910 --> 00:01:05,450 At sa wakas, kami ay pagpunta sa may global variable na laki hashtable, na 22 00:01:05,450 --> 00:01:07,000 Pupunta upang simulan off bilang zero. 23 00:01:07,000 --> 00:01:10,760 At ito ay pagpunta sa masubaybayan kung gaano maraming mga salita ay nasa aming diksyunaryo. 24 00:01:10,760 --> 00:01:13,710 >> Kaya ipaalam sa tumagal ng isang pagtingin sa pag-load. 25 00:01:13,710 --> 00:01:16,390 Pansinin na load, nagbabalik ito ng isang bool. 26 00:01:16,390 --> 00:01:20,530 Ikaw nagbabalik ng tunay na kung matagumpay na ito ay load, at hindi totoo kung hindi man. 27 00:01:20,530 --> 00:01:23,990 At ito ay tumatagal ng isang const pansamantalang trabaho * diksyonaryo, kung saan ay ang diksyunaryo 28 00:01:23,990 --> 00:01:25,280 na nais naming buksan. 29 00:01:25,280 --> 00:01:27,170 Kaya iyon ang unang bagay kami ay pagpunta sa gawin. 30 00:01:27,170 --> 00:01:29,500 >> Kami ay pagpunta sa fopen ang diksyunaryo para sa pagbabasa. 31 00:01:29,500 --> 00:01:31,680 At kami ay pagpunta sa may upang gumawa ng siguraduhin na ito ay nagtagumpay. 32 00:01:31,680 --> 00:01:35,920 Kaya kung ibinalik ito null, pagkatapos kami ay hindi Matagumpay na buksan ang diksyunaryo. 33 00:01:35,920 --> 00:01:37,440 At kailangan namin upang bumalik hindi totoo. 34 00:01:37,440 --> 00:01:41,580 Ngunit sa pag-aakala na matagumpay na ginawa ito bukas, pagkatapos ay nais naming basahin ang 35 00:01:41,580 --> 00:01:42,400 diksiyunaryo. 36 00:01:42,400 --> 00:01:46,450 Kaya panatilihin looping hanggang sa mahanap namin ang ilang dahilan upang masira papalabas sa loop, 37 00:01:46,450 --> 00:01:47,570 kung saan ipapakita namin makita. 38 00:01:47,570 --> 00:01:48,920 Kaya panatilihin looping. 39 00:01:48,920 --> 00:01:51,780 >> At ngayon kami ay pagpunta sa malloc isang solong node. 40 00:01:51,780 --> 00:01:54,020 At syempre kailangan namin upang maisahimpapawid suriin muli. 41 00:01:54,020 --> 00:01:58,680 Kaya kung mallocing ay hindi magtagumpay, pagkatapos ay gusto naming mag-ibis anumang node na namin 42 00:01:58,680 --> 00:02:02,590 nangyari bago sa malloc, isara ang diksyunaryo at bumalik hindi totoo. 43 00:02:02,590 --> 00:02:06,830 Ngunit hindi papansin ang na, sa pag-aakala namin nagtagumpay, pagkatapos ay nais naming gamitin fscanf 44 00:02:06,830 --> 00:02:12,400 basahin ang isang solong salita mula sa aming diksyunaryo sa aming mga node. 45 00:02:12,400 --> 00:02:17,940 Kaya tandaan na ang entry> salita ay ang pansamantalang trabaho salita buffer ng laki LENGHTH + 1 46 00:02:17,940 --> 00:02:20,300 na aming pagpunta upang i-imbak ang salitang in 47 00:02:20,300 --> 00:02:25,070 >> Kaya fscanf ay pagpunta upang bumalik 1, hangga't dahil ito ay matagumpay na mai- 48 00:02:25,070 --> 00:02:26,750 basahin ang isang salita mula sa file. 49 00:02:26,750 --> 00:02:30,460 Kung nangyari ang alinman sa isang error, o namin maabot ang dulo ng file, 50 00:02:30,460 --> 00:02:31,950 Hindi nagbabalik 1. 51 00:02:31,950 --> 00:02:35,180 Sa aling mga kaso hindi ito bumalik 1, sa wakas kami ay pagpunta sa magsimula ng 52 00:02:35,180 --> 00:02:37,280 ito habang loop. 53 00:02:37,280 --> 00:02:42,770 Kaya nakikita natin na sa sandaling matagumpay na mayroon kami basahin ang isang salita sa 54 00:02:42,770 --> 00:02:48,270 entry> salita, pagkatapos kami ay pagpunta sa na salita gamit ang aming hash. 55 00:02:48,270 --> 00:02:49,580 >> Hayaan ang kumuha ng isang pagtingin sa ang hash. 56 00:02:49,580 --> 00:02:52,430 57 00:02:52,430 --> 00:02:55,610 Kaya huwag talagang kailangan mo upang maunawaan ito. 58 00:02:55,610 --> 00:02:59,460 At talagang nakuha lang namin ito ng hash gumana mula sa internet. 59 00:02:59,460 --> 00:03:04,010 Ang tanging bagay na kailangan mo upang makilala ang na ito ay tumatagal ng isang const pansamantalang trabaho * salita. 60 00:03:04,010 --> 00:03:08,960 Kaya tumatagal string na ito bilang input, at bumabalik isang wala pang kontratang int bilang output. 61 00:03:08,960 --> 00:03:12,360 Kaya iyon ang lahat ng hash function na ay, ay ito tumatagal sa isang input at nagbibigay sa iyo ng isang 62 00:03:12,360 --> 00:03:14,490 index sa hashtable. 63 00:03:14,490 --> 00:03:18,530 >> Pansinin na aming moding sa pamamagitan ng NUM_BUCKETS, kaya ibinalik na halaga na 64 00:03:18,530 --> 00:03:21,730 talaga ay isang index sa hashtable at hindi ini-index nang higit sa 65 00:03:21,730 --> 00:03:24,320 hanggahan ng array. 66 00:03:24,320 --> 00:03:28,060 Kaya ibinigay na function, kami ay pagpunta sa hash ang salita na aming basahin ang 67 00:03:28,060 --> 00:03:29,390 diksiyunaryo. 68 00:03:29,390 --> 00:03:31,700 At pagkatapos ay kami ay pagpunta sa gamitin na hash upang ipasok ang 69 00:03:31,700 --> 00:03:33,750 entry sa hashtable. 70 00:03:33,750 --> 00:03:38,520 >> Hashtable Ngayon hash ay ang kasalukuyang listahan na naka-link sa talahanayan. 71 00:03:38,520 --> 00:03:41,410 At ito ay napaka-posible na ito ay para lamang null. 72 00:03:41,410 --> 00:03:44,960 Gusto naming upang ipasok ang aming entry sa simula ng ito na naka-link listahan. 73 00:03:44,960 --> 00:03:48,600 At kaya kami ay pagpunta sa may aming kasalukuyang entry point sa kung ano ang hashtable 74 00:03:48,600 --> 00:03:50,380 Kasalukuyang nagtuturo sa. 75 00:03:50,380 --> 00:03:53,310 At pagkatapos ay kami ay pagpunta upang mag-imbak, sa hashtable sa 76 00:03:53,310 --> 00:03:55,350 hash, ang kasalukuyang entry. 77 00:03:55,350 --> 00:03:59,320 Kaya matagumpay na ipasok ang dalawang mga linya ang entry sa simula ng 78 00:03:59,320 --> 00:04:02,260 naka-link na listahan sa index na sa hashtable. 79 00:04:02,260 --> 00:04:04,900 >> Sa sandaling tapos na kami doon, alam namin nakakita kami ng isa pang salita sa 80 00:04:04,900 --> 00:04:07,790 diksyonaryo, at dinagdagan namin muli. 81 00:04:07,790 --> 00:04:13,960 Kaya panatilihin namin ang paggawa na hanggang fscanf sa wakas ay ibinalik ng isang bagay na hindi pang-1 sa 82 00:04:13,960 --> 00:04:16,950 na kung saang tandaan na kailangan namin upang palayain entry. 83 00:04:16,950 --> 00:04:19,459 Kaya hanggang dito malloced kami ng isang entry. 84 00:04:19,459 --> 00:04:21,329 At sinubukan naming basahin ang isang bagay mula sa diksyunaryo. 85 00:04:21,329 --> 00:04:23,910 At kami ay hindi matagumpay na basahin isang bagay mula sa diksyonaryo, sa 86 00:04:23,910 --> 00:04:26,650 Kung saan kailangan namin upang palayain ang entry na talaga namin kailanman ilagay sa 87 00:04:26,650 --> 00:04:29,140 hashtable, at sa wakas ay masira. 88 00:04:29,140 --> 00:04:32,750 >> Sa sandaling magsimula namin na kailangan namin upang makita, mahusay, ay masira kami out dahil mayroong 89 00:04:32,750 --> 00:04:34,360 ay isang error sa pagbabasa mula sa file? 90 00:04:34,360 --> 00:04:37,120 O kaya ay masira out namin dahil kami Naabot ang dulo ng file? 91 00:04:37,120 --> 00:04:39,480 Kung nagkaroon ng error, at pagkatapos ay gusto naming ibalik hindi totoo. 92 00:04:39,480 --> 00:04:40,930 Dahil ang pag-load ay hindi magtagumpay. 93 00:04:40,930 --> 00:04:43,890 At sa proseso ng gusto naming alisan ng bala lahat ng mga salita na binabasa namin sa, at 94 00:04:43,890 --> 00:04:45,670 isara ang file na diksiyunaryo. 95 00:04:45,670 --> 00:04:48,740 >> Sa pag-aakala namin ginawa magtagumpay, pagkatapos namin lamang kailangan pa rin upang isara ang diksyunaryo 96 00:04:48,740 --> 00:04:53,040 maghain, at sa wakas ay nagbabalik ng tunay na mula noong namin Matagumpay na na-load sa diksyunaryo. 97 00:04:53,040 --> 00:04:54,420 At na ito para sa pag-load. 98 00:04:54,420 --> 00:04:59,020 Kaya ngayon suriin, bibigyan ng load hashtable, ay pagpunta sa ganito ang hitsura. 99 00:04:59,020 --> 00:05:03,140 Kaya tingnan, nagbabalik ito ng isang bool, na pagpunta upang ipahiwatig kung ang pumasa sa mga 100 00:05:03,140 --> 00:05:07,530 sa pansamantalang trabaho * salita, kung ang pumasa sa mga sa string ay nasa aming diksyunaryo. 101 00:05:07,530 --> 00:05:09,890 Kaya kung ito ay nasa sa diksyunaryo, kung ito ay nasa aming hashtable, 102 00:05:09,890 --> 00:05:11,170 magkakaroon kami nagbabalik ng tunay. 103 00:05:11,170 --> 00:05:13,380 At kung hindi, magkakaroon kami bumalik hindi totoo. 104 00:05:13,380 --> 00:05:17,740 >> Given ito nakapasa sa salita, kami ay pagpunta sa hash ang salita. 105 00:05:17,740 --> 00:05:22,110 Ngayon isang mahalagang bagay upang makilala ang na sa pagkarga Alam namin na ang lahat ng mga 106 00:05:22,110 --> 00:05:23,820 salita kami ay pagpunta sa maging mas mababa kaso. 107 00:05:23,820 --> 00:05:25,820 Ngunit dito kami ay hindi kaya sigurado. 108 00:05:25,820 --> 00:05:29,510 Kung tumagal kami ng isang tumingin sa aming hash, ang aming hash talaga 109 00:05:29,510 --> 00:05:32,700 ay mas mababa casing bawat karakter ng salita. 110 00:05:32,700 --> 00:05:37,940 Kaya anuman ang capitalization ng salita, ang aming hash ay ang pagbalik 111 00:05:37,940 --> 00:05:42,270 ang parehong index para sa anumang mga capitalization ay, gaya ng ang mga ito ay may 112 00:05:42,270 --> 00:05:45,280 ibinalik para sa isang ganap na lowercase bersyon ng salita. 113 00:05:45,280 --> 00:05:46,600 Mabuti na. 114 00:05:46,600 --> 00:05:49,790 Iyon lang ang aming index ay sa hashtable para sa salitang ito. 115 00:05:49,790 --> 00:05:52,940 >> Ngayon na ito para sa loop ay pagpunta sa umulit sa ibabaw ng naka-link na listahan 116 00:05:52,940 --> 00:05:55,000 na noon ay sa index iyon. 117 00:05:55,000 --> 00:05:59,610 Kaya't mapapansin ay Sinisimulan namin entry upang tumuro sa index iyon. 118 00:05:59,610 --> 00:06:02,750 Kami ay pagpunta upang magpatuloy habang entry! = null. 119 00:06:02,750 --> 00:06:07,770 At tandaan na ina-update ang pointer sa aming mga naka-link na listahan entry = entry> susunod. 120 00:06:07,770 --> 00:06:14,400 Kaya mayroon aming kasalukuyang entry point sa ang susunod na item sa naka-link na listahan. 121 00:06:14,400 --> 00:06:19,250 >> Kaya para sa bawat entry sa naka-link na listahan, kami ay pagpunta sa gamitin strcasecmp. 122 00:06:19,250 --> 00:06:20,330 Ito ay hindi strcomp. 123 00:06:20,330 --> 00:06:23,780 Dahil sa sandaling muli, nais naming gawin kaso bagay insensitively. 124 00:06:23,780 --> 00:06:27,870 Kaya ginagamit namin strcasecmp upang ihambing ang salita na dumaan sa ito 125 00:06:27,870 --> 00:06:31,860 function na laban sa mga salita na sa entry. 126 00:06:31,860 --> 00:06:35,570 Kapag bumalik ito sa zero, ibig sabihin nagkaroon isang tugma, kung saan nais naming 127 00:06:35,570 --> 00:06:36,630 nagbabalik ng tunay. 128 00:06:36,630 --> 00:06:39,590 Kami matagumpay nahanap ang salita sa aming hashtable. 129 00:06:39,590 --> 00:06:43,040 >> Kung nagkaroon hindi isang tugma, pagkatapos kami ay pagpunta sa loop muli at tumingin sa 130 00:06:43,040 --> 00:06:43,990 susunod na entry. 131 00:06:43,990 --> 00:06:47,640 At patuloy kaming looping habang doon mga entry sa naka-link na ito listahan. 132 00:06:47,640 --> 00:06:50,160 Ano ang mangyayari kung masira namin out na ito para sa loop? 133 00:06:50,160 --> 00:06:55,110 Nangangahulugan iyon na hindi kami nakahanap ng isang entry na tugmang salita na ito, kung saan 134 00:06:55,110 --> 00:07:00,220 bumalik kami huwad upang ipahiwatig na ang aming hashtable Hindi naglalaman ang salitang ito. 135 00:07:00,220 --> 00:07:02,540 At na ang isang tseke. 136 00:07:02,540 --> 00:07:04,790 >> Kaya ipaalam sa tumagal ng isang pagtingin sa laki. 137 00:07:04,790 --> 00:07:06,970 Laki Ngayon ay magiging kaakit-akit simple. 138 00:07:06,970 --> 00:07:11,080 Dahil tandaan sa pag-load, para sa bawat salita nahanap namin, incremented kami ng isang global 139 00:07:11,080 --> 00:07:12,880 variable na laki hashtable. 140 00:07:12,880 --> 00:07:16,480 Kaya ang function ng laki ay lamang ng pagpunta upang bumalik global variable. 141 00:07:16,480 --> 00:07:18,150 At na ito. 142 00:07:18,150 --> 00:07:22,300 >> Ngayon sa wakas, kailangan naming mag-ibis ang diksyunaryo-sabay ang lahat ng bagay tapos na. 143 00:07:22,300 --> 00:07:25,340 Kaya paano kami makapupunta sa gawin iyon? 144 00:07:25,340 --> 00:07:30,440 Mag-right dito kami looping sa ibabaw lahat ng mga bucket ng aming table. 145 00:07:30,440 --> 00:07:33,240 Kaya may mga NUM_BUCKETS bucket. 146 00:07:33,240 --> 00:07:37,410 At para sa bawat naka-link na listahan sa aming hashtable, kami ay pagpunta sa loop sa ibabaw 147 00:07:37,410 --> 00:07:41,070 ang kabuuan ng mga naka-link na listahan, pagbabakante bawat elemento. 148 00:07:41,070 --> 00:07:42,900 >> Ngayon kailangan namin upang maging maingat. 149 00:07:42,900 --> 00:07:47,910 Kaya dito mayroon kaming isang pansamantalang variable na pag-iimbak ang pointer sa susunod 150 00:07:47,910 --> 00:07:49,730 elemento sa naka-link na listahan. 151 00:07:49,730 --> 00:07:52,140 At pagkatapos ay kami ay pagpunta sa libreng ang kasalukuyang elemento. 152 00:07:52,140 --> 00:07:55,990 Kailangan naming siguruhin ang ginagawa namin ito dahil kami Hindi maaaring lamang palayain ang kasalukuyang elemento 153 00:07:55,990 --> 00:07:59,180 at pagkatapos ay subukang i-access ang susunod na pointer, dahil sa sandaling na-nabakante namin ito, 154 00:07:59,180 --> 00:08:00,870 nagiging di-wasto ang memory. 155 00:08:00,870 --> 00:08:04,990 >> Kaya kailangan namin upang panatilihin sa paligid ng isang pointer upang sa susunod na elemento, pagkatapos ay maaari naming palayain ang 156 00:08:04,990 --> 00:08:08,360 kasalukuyang elemento, at pagkatapos ay maaari naming i-update aming kasalukuyang elemento upang tumuro sa 157 00:08:08,360 --> 00:08:09,550 sa susunod na elemento. 158 00:08:09,550 --> 00:08:12,800 Kami na magugustuhan loop habang mayroong mga elemento sa naka-link na listahan. 159 00:08:12,800 --> 00:08:15,620 Gagawin namin ang na para sa lahat na naka-link mga listahan sa hashtable. 160 00:08:15,620 --> 00:08:19,460 At sa sandaling tapos na kami sa na, hindi namin ganap deskargado ang hashtable, at 161 00:08:19,460 --> 00:08:20,190 tapos na kami. 162 00:08:20,190 --> 00:08:23,200 Kaya imposibleng para sa alisan ng bala upang kailanman bumalik hindi totoo. 163 00:08:23,200 --> 00:08:26,470 At kapag tapos na kami, namin bumalik lang totoo. 164 00:08:26,470 --> 00:08:29,000 >> Bigyan ng solusyon ang isang try Hayaan. 165 00:08:29,000 --> 00:08:33,070 Kaya ipaalam sa tumagal ng isang pagtingin sa kung ano ang aming struct node magiging hitsura. 166 00:08:33,070 --> 00:08:36,220 Narito makita namin kami ay pagpunta sa magkaroon ng isang bool salita at isang struct node * mga bata 167 00:08:36,220 --> 00:08:37,470 bracket alpabeto. 168 00:08:37,470 --> 00:08:38,929 169 00:08:38,929 --> 00:08:42,020 Kaya ang unang bagay na maaari mong nagtataka, kung bakit ay alpabeto 170 00:08:42,020 --> 00:08:44,660 ed tinukoy bilang 27? 171 00:08:44,660 --> 00:08:47,900 Well, tandaan na kami ay pagpunta sa kailangan na paghawak ng mga kudlit. 172 00:08:47,900 --> 00:08:51,910 Kaya na pupuntahan na medyo ng isang espesyal na kaso sa buong programa na ito. 173 00:08:51,910 --> 00:08:54,710 >> Ngayon tandaan kung paano ang isang trie talaga gumagana. 174 00:08:54,710 --> 00:08:59,380 Sabihin nating kami sa paglilista ng salita "Cats." Pagkatapos mula sa root ng trie, 175 00:08:59,380 --> 00:09:02,610 kami ay pagpunta sa tumingin sa mga bata array, at kami ay pagpunta sa tumingin sa 176 00:09:02,610 --> 00:09:08,090 index na tumutugon sa titik C. Kaya na mai-index 2. 177 00:09:08,090 --> 00:09:11,530 Kaya ibinigay na, kalooban na bigyan kami ng isang bagong node. 178 00:09:11,530 --> 00:09:13,820 At pagkatapos ay makikipagtulungan kami mula sa na node. 179 00:09:13,820 --> 00:09:17,770 >> Kaya ibinigay na node, kami ay isang beses muli pagpunta sa tumingin sa mga anak ng array. 180 00:09:17,770 --> 00:09:22,110 At kami ay pagpunta upang tumingin sa index zero upang tumugma sa A sa pusa. 181 00:09:22,110 --> 00:09:27,170 Kaya pagkatapos kami ay pagpunta upang pumunta sa na node, at ibinigay na node kami ay pagpunta 182 00:09:27,170 --> 00:09:31,090 upang tumingin sa dulo ito ay isang tumutugon sa T. At gumagalaw sa sa na node, 183 00:09:31,090 --> 00:09:35,530 sa wakas, ganap namin ay tumingin sa pamamagitan ng aming salitang "pusa." At ngayon bool 184 00:09:35,530 --> 00:09:40,960 salita ay dapat na ipahiwatig kung ito ibinigay na salita ay tunay na isang salita. 185 00:09:40,960 --> 00:09:43,470 >> Kaya bakit kailangan namin na espesyal na kaso? 186 00:09:43,470 --> 00:09:47,700 Well kung ano ng salitang "sakuna" ay nasa aming diksyunaryo, ngunit ang 187 00:09:47,700 --> 00:09:50,150 salitang "pusa" ay hindi? 188 00:09:50,150 --> 00:09:54,580 Kaya at naghahanap upang makita kung ang salitang "pusa" ay sa aming diksyonaryo, kami ay 189 00:09:54,580 --> 00:09:59,970 pagpunta sa matagumpay na tingnan ng masinsinan ang mga indeks ng C-A-T sa rehiyon na node. 190 00:09:59,970 --> 00:10:04,290 Ngunit iyon ay dahil lamang sakuna nangyari upang lumikha ng mga node sa paraan 191 00:10:04,290 --> 00:10:07,190 mula C-A-T, ang lahat ng mga paraan upang sa dulo ng salita. 192 00:10:07,190 --> 00:10:12,020 Kaya bool salita ay ginagamit upang ipahiwatig kung ang ito partikular na lokasyon 193 00:10:12,020 --> 00:10:14,310 talaga ay nagpapahiwatig ng isang salita. 194 00:10:14,310 --> 00:10:15,140 >> Ayos lang. 195 00:10:15,140 --> 00:10:19,310 Kaya ngayon na alam namin kung ano ito ay trie pagpunta sa hitsura, tingnan natin ang ipaalam 196 00:10:19,310 --> 00:10:20,730 load ang function. 197 00:10:20,730 --> 00:10:24,610 Kaya pagkarga ay pagpunta upang magbalik ng bool para kung namin matagumpay o 198 00:10:24,610 --> 00:10:26,720 unsuccessfully load ang diksyunaryo. 199 00:10:26,720 --> 00:10:30,460 At ito ay magiging diksyunaryo na gusto naming i-load. 200 00:10:30,460 --> 00:10:33,930 >> Kaya unang bagay na ikaw ay naming gawin ay bukas up na diksyunaryo para sa pagbabasa. 201 00:10:33,930 --> 00:10:36,160 At mayroon kaming upang tiyakin hindi namin ginawa mabibigo. 202 00:10:36,160 --> 00:10:39,580 Kaya kung ang diksiyonaryo ay hindi Matagumpay na nabuksan, at ibabalik ito 203 00:10:39,580 --> 00:10:42,400 null, kung saan kami ay pagpunta sa bumalik hindi totoo. 204 00:10:42,400 --> 00:10:47,230 Ngunit sa pag-aakala na ito matagumpay binuksan, pagkatapos ay maaari naming talagang basahin 205 00:10:47,230 --> 00:10:48,220 sa pamamagitan ng diksyunaryo. 206 00:10:48,220 --> 00:10:50,880 >> Kaya unang bagay na kami ay pagpunta sa gusto lang gawin ay mayroon kaming na ito 207 00:10:50,880 --> 00:10:52,500 global variable na ugat. 208 00:10:52,500 --> 00:10:56,190 Ngayon ugat ay magiging isang node *. 209 00:10:56,190 --> 00:10:59,760 Ito ay sa tuktok ng aming trie na kami pagpunta sa ma-iterating sa pamamagitan ng. 210 00:10:59,760 --> 00:11:02,660 Kaya ang unang bagay na aming pagpunta sa gusto lang gawin ay magtalaga ng 211 00:11:02,660 --> 00:11:04,140 memory para sa aming mga ugat. 212 00:11:04,140 --> 00:11:07,980 Pansinin na ginagamit namin ang calloc function, na kung saan ay isa lamang ang parehong 213 00:11:07,980 --> 00:11:11,500 bilang ang malloc function, maliban ito ay garantisadong upang magbalik ng bagay na 214 00:11:11,500 --> 00:11:13,180 ganap zeroed out. 215 00:11:13,180 --> 00:11:17,290 Kaya kung ginamit namin malloc, gusto naming i- pumunta sa pamamagitan ng lahat ng mga mungkahi ukol sa aming mga 216 00:11:17,290 --> 00:11:20,160 node, at tiyakin na ang mga ito ay lahat null. 217 00:11:20,160 --> 00:11:22,710 Kaya ang gagawin calloc na para sa amin. 218 00:11:22,710 --> 00:11:26,330 >> Ngayon tulad ng malloc, kailangan naming gumawa Tiyakin na ang paglalaan ay talagang 219 00:11:26,330 --> 00:11:27,520 matagumpay. 220 00:11:27,520 --> 00:11:29,990 Kung ito ibinalik null, pagkatapos namin kailanganin mong isara o diksyunaryo 221 00:11:29,990 --> 00:11:32,100 maghain at bumalik hindi totoo. 222 00:11:32,100 --> 00:11:36,835 Kaya kung ipagpalagay na laang-gugulin na matagumpay, kami ay pagpunta sa gumamit ng isang node * 223 00:11:36,835 --> 00:11:40,270 cursor upang umulit sa pamamagitan ng aming trie. 224 00:11:40,270 --> 00:11:43,890 Kaya aming Roots hindi kailanman pagpunta sa magbago, ngunit kami ay pagpunta upang gamitin ang cursor sa 225 00:11:43,890 --> 00:11:47,875 talaga pumunta mula sa node sa node. 226 00:11:47,875 --> 00:11:50,940 >> Kaya sa na ito para sa loop na binabasa namin sa pamamagitan ng file diksiyunaryo. 227 00:11:50,940 --> 00:11:53,670 At aming ginagamit fgetc. 228 00:11:53,670 --> 00:11:56,290 Fgetc ay pagpunta sa grab isang solong karakter mula sa file. 229 00:11:56,290 --> 00:11:59,370 Kami ay pagpunta sa magpatuloy daklot character habang hindi namin maabot ang 230 00:11:59,370 --> 00:12:01,570 dulo ng file. 231 00:12:01,570 --> 00:12:03,480 >> Mayroong dalawang mga kaso na kailangan namin upang mahawakan. 232 00:12:03,480 --> 00:12:06,610 Ang una, kung ang karakter ay hindi isang bagong linya. 233 00:12:06,610 --> 00:12:10,450 Upang malaman namin kung ito ay isang bagong linya, pagkatapos ay Ikinalulungkot namin tungkol sa paglipat sa isang bagong salita. 234 00:12:10,450 --> 00:12:15,240 Ngunit sa pag-aakala ay hindi ito isang bagong linya, pagkatapos ay dito gusto naming malaman kung ang 235 00:12:15,240 --> 00:12:18,380 index namin ang pagpunta sa index sa sa mga anak ng array na 236 00:12:18,380 --> 00:12:19,810 itinuturing namin ang bago. 237 00:12:19,810 --> 00:12:23,880 >> Kaya, tulad ng sinabi ko dati, kailangan naming i- espesyal na kaso ang kudlit. 238 00:12:23,880 --> 00:12:26,220 Pansinin na aming ginagamit ang tatlong bagay operator dito. 239 00:12:26,220 --> 00:12:29,580 Kaya kami ay pagpunta sa basahin ito bilang, kung ang character na binabasa namin sa isang 240 00:12:29,580 --> 00:12:35,330 kudlit, pagkatapos kami ay pagpunta upang i-set index = "alpabeto" -1, na 241 00:12:35,330 --> 00:12:37,680 maging index 26. 242 00:12:37,680 --> 00:12:41,130 >> Iba Pa, kung ito ay hindi isang kudlit, mayroong kami ay pagpunta upang itakda ang index 243 00:12:41,130 --> 00:12:43,760 katumbas ng c - isang. 244 00:12:43,760 --> 00:12:49,030 Kaya tandaan pabalik mula sa dati p-sets, c - isang ay pagpunta sa bigyan kami ng mga 245 00:12:49,030 --> 00:12:53,410 alpabetikong posisyon ng C. Kaya kung C ay ang letrang A, aabutin ang 246 00:12:53,410 --> 00:12:54,700 bigyan kami ng index zero. 247 00:12:54,700 --> 00:12:58,120 Para sa titik B, ito ay magbibigay sa amin index 1, at iba pa. 248 00:12:58,120 --> 00:13:03,010 >> Kaya ito ay nagbibigay sa amin ng index sa mga anak ng array na gusto namin. 249 00:13:03,010 --> 00:13:08,890 Ngayon kung ito index ay kasalukuyang null sa ang mga anak, ay nangangahulugan na na ang isang node 250 00:13:08,890 --> 00:13:11,830 Sa kasalukuyan ay hindi umiiral mula ang path na iyon. 251 00:13:11,830 --> 00:13:15,160 Kaya kailangan naming maglaan isang node para ang path na iyon. 252 00:13:15,160 --> 00:13:16,550 Iyon ay kung ano ang gagawin namin dito. 253 00:13:16,550 --> 00:13:20,690 >> Kaya kami ay pagpunta sa muli gamitin ang calloc function, kaya na namin Hindi mo na kailangang 254 00:13:20,690 --> 00:13:22,880 Zero ang lahat ng mga payo. 255 00:13:22,880 --> 00:13:27,240 At muli kailanganin naming suriin na calloc ay hindi mabibigo. 256 00:13:27,240 --> 00:13:30,700 Kung calloc nabigo, pagkatapos kailangan namin upang mag-ibis ang lahat ng bagay, isara ang aming 257 00:13:30,700 --> 00:13:32,820 diksyonaryo, at ibalik hindi totoo. 258 00:13:32,820 --> 00:13:40,050 Kaya sa pag-aakala na hindi ito mabibigo, at pagkatapos ay ito ay lilikha ng bagong bata para sa amin. 259 00:13:40,050 --> 00:13:41,930 At pagkatapos ay magpapatuloy kami sa bata na iyon. 260 00:13:41,930 --> 00:13:44,960 Ang aming cursor ay umulit pababa sa bata na iyon. 261 00:13:44,960 --> 00:13:49,330 >> Ngayon kung hindi ito ay walang bisa upang magsimula sa, pagkatapos ay ang cursor maaari lamang umulit 262 00:13:49,330 --> 00:13:52,590 pababa sa bata na walang tunay pagkakaroon upang magtalaga ng kahit ano. 263 00:13:52,590 --> 00:13:56,730 Ito ay ang kaso kung saan unang namin ang nangyari maglaan ang salitang "pusa." At 264 00:13:56,730 --> 00:14:00,330 Nangangahulugan itong kapag tayo pupunta maglaan "Sakuna," ay hindi kami kailangan upang lumikha ng 265 00:14:00,330 --> 00:14:01,680 node para sa C-A-T muli. 266 00:14:01,680 --> 00:14:04,830 Sila ay umiiral na. 267 00:14:04,830 --> 00:14:06,080 >> Ano ang tao? 268 00:14:06,080 --> 00:14:10,480 Ito ang kalagayan kung saan c noon ay backslash n, kung saan c ay isang bagong linya. 269 00:14:10,480 --> 00:14:13,710 Ang ibig sabihin nito na matagumpay na mayroon kami Nakumpleto ang isang salita. 270 00:14:13,710 --> 00:14:16,860 Ngayon kung ano ang gusto naming gawin kapag kami Matagumpay na nakumpleto ang isang salita? 271 00:14:16,860 --> 00:14:21,100 Kami ay pagpunta sa gamitin ang salita patlang sa loob ng aming struct node. 272 00:14:21,100 --> 00:14:23,390 Gusto naming i-set na sa totoo. 273 00:14:23,390 --> 00:14:27,150 Kaya na nagpapahiwatig na ito node ay nagpapahiwatig ng isang matagumpay na 274 00:14:27,150 --> 00:14:29,250 salita, isang aktwal na salita. 275 00:14:29,250 --> 00:14:30,940 >> Ngayon nakatakda na sa totoo. 276 00:14:30,940 --> 00:14:35,150 Gusto naming upang i-reset ang aming cursor sa punto upang muli sa simula ng trie. 277 00:14:35,150 --> 00:14:40,160 At sa wakas, dinagdagan ng aming diksyunaryo laki, dahil nakakita kami ng isa pang trabaho. 278 00:14:40,160 --> 00:14:43,230 Kaya kami ay pagpunta upang panatilihin ang paggawa na iyon, pagbabasa sa katangian ng karakter, 279 00:14:43,230 --> 00:14:49,150 bumubuo ka ng mga bagong nodes sa aming trie at para sa bawat salita sa diksyunaryo, hanggang sa 280 00:14:49,150 --> 00:14:54,020 sa wakas namin maabot C! = EOF, kung saan kaso masira kami sa labas ng file. 281 00:14:54,020 --> 00:14:57,050 >> Ngayon mayroong dalawang mga kaso sa ilalim na maaring pindutin namin EOF. 282 00:14:57,050 --> 00:15:00,980 Ang una ay kung nagkaroon ng error pagbabasa mula sa file. 283 00:15:00,980 --> 00:15:03,470 Kaya kung nagkaroon ng error, namin kailangan na gawin ang tipikal. 284 00:15:03,470 --> 00:15:06,460 Alisan ng bala ang lahat ng bagay, malapit ang file, bumalik hindi totoo. 285 00:15:06,460 --> 00:15:09,810 Sa pag-aakala nagkaroon hindi isang error, na Ang ibig sabihin lang talaga pindutin namin ang katapusan ng 286 00:15:09,810 --> 00:15:13,750 ang file, na kung saan, isara namin ang maghain at nagbabalik ng tunay na mula noong namin 287 00:15:13,750 --> 00:15:17,330 Matagumpay na na-load diksyunaryo sa aming trie. 288 00:15:17,330 --> 00:15:20,170 >> Kaya ni check out check ngayon hayaan. 289 00:15:20,170 --> 00:15:25,156 Naghahanap sa check-andar, makikita natin check na pagpunta upang magbalik ng bool. 290 00:15:25,156 --> 00:15:29,680 Ibinabalik nito ang totoo kung ang salitang ito na ito ini ang pumasa ay nasa aming trie. 291 00:15:29,680 --> 00:15:32,110 Ibinabalik nito ang hindi totoo kung hindi man. 292 00:15:32,110 --> 00:15:36,050 Kaya paano mo matukoy kung ang salitang ito ay nasa aming trie? 293 00:15:36,050 --> 00:15:40,190 >> Nakakakita kami dito na, tulad ng dati, kami ay pagpunta upang gamitin ang cursor na umulit 294 00:15:40,190 --> 00:15:41,970 sa pamamagitan ng aming trie. 295 00:15:41,970 --> 00:15:46,600 Ngayon dito kami ay pagpunta upang umulit lagpas sa aming buong salita. 296 00:15:46,600 --> 00:15:50,620 Kaya iterating sa ibabaw ng salita hindi namin nakaraan, kami ay pagpunta upang matukoy ang 297 00:15:50,620 --> 00:15:56,400 index sa mga bata array na tumutugon sa salita bracket I. Kaya ito 298 00:15:56,400 --> 00:15:59,670 Pupunta upang tumingin nang eksakto tulad ng load, kung saan kung salita [i] 299 00:15:59,670 --> 00:16:03,310 ay isang kudlit, pagkatapos ay nais naming upang gamitin ang index "alpabeto" - 1. 300 00:16:03,310 --> 00:16:05,350 Dahil natukoy namin na iyon ay kung saan kami ay pagpunta upang mag-imbak 301 00:16:05,350 --> 00:16:07,100 apostrophes. 302 00:16:07,100 --> 00:16:11,780 >> Iba Pa kami ay pagpunta upang gamitin ang dalawang mas mababang mga salita tandaan Kaya bracket I. na salita maaari 303 00:16:11,780 --> 00:16:13,920 May di-makatwirang paggamit ng malaking titik. 304 00:16:13,920 --> 00:16:17,540 At kaya gusto naming matiyak na hindi namin gamit ang isang maliit na mga bersyon ng mga bagay. 305 00:16:17,540 --> 00:16:21,920 At pagkatapos ay ibabawas mula sa na 'ang isang' upang sabay muli magbibigay sa amin ang alpabetikong 306 00:16:21,920 --> 00:16:23,880 posisyon ng na character. 307 00:16:23,880 --> 00:16:27,680 Kaya na pupuntahan maging aming index papunta sa mga anak ng array. 308 00:16:27,680 --> 00:16:32,420 >> At ngayon kung index na papunta sa mga bata array ay walang bisa, ibig sabihin namin 309 00:16:32,420 --> 00:16:34,990 hindi na magpatuloy iterating down na aming trie. 310 00:16:34,990 --> 00:16:38,870 Kung iyon ang kaso, ang salitang ito ay hindi maaaring marahil maging sa aming trie. 311 00:16:38,870 --> 00:16:42,340 Dahil parang ito ay, na gagawin ibig sabihin doon ay magiging isang path 312 00:16:42,340 --> 00:16:43,510 pababa sa salitang iyon. 313 00:16:43,510 --> 00:16:45,290 At hindi mo nais makaharap null. 314 00:16:45,290 --> 00:16:47,850 Kaya Nakakaranas ng mga null, bumalik kami ng hindi totoo. 315 00:16:47,850 --> 00:16:49,840 Salita ay wala sa diksyonaryo. 316 00:16:49,840 --> 00:16:53,660 Kung ito ay hindi null, pagkatapos kami ay pagpunta sa magpatuloy iterating. 317 00:16:53,660 --> 00:16:57,220 >> Kaya ka ng pagpunta namin out doon cursor upang tumuro sa partikular na 318 00:16:57,220 --> 00:16:59,760 node sa index iyon. 319 00:16:59,760 --> 00:17:03,150 Panatilihin namin ang paggawa na sa buong ang buong salita, sa pag-aakala 320 00:17:03,150 --> 00:17:03,950 kami ay hindi kailanman pindutin null. 321 00:17:03,950 --> 00:17:07,220 Iyon ay nangangahulugang namin nagawang upang makakuha ng sa pamamagitan ng ang buong salita at hanapin 322 00:17:07,220 --> 00:17:08,920 isang node sa aming try. 323 00:17:08,920 --> 00:17:10,770 Ngunit kami ay hindi masyadong pa tapos. 324 00:17:10,770 --> 00:17:12,290 >> Hindi namin nais upang bumalik lamang totoo. 325 00:17:12,290 --> 00:17:14,770 Gusto naming bumalik cursor> salita. 326 00:17:14,770 --> 00:17:18,980 Dahil tandaan muli, ay "pusa" ay hindi sa aming diksyonaryo, at "sakuna" 327 00:17:18,980 --> 00:17:22,935 ay, pagkatapos kami ay matagumpay na makuha namin sa pamamagitan ng salitang "pusa." Ngunit cursor 328 00:17:22,935 --> 00:17:25,760 salita ay hindi totoo at hindi totoo. 329 00:17:25,760 --> 00:17:30,930 Kaya bumalik kami cursor salita upang ipahiwatig kung ito node ay talagang isang salita. 330 00:17:30,930 --> 00:17:32,470 At na ito para sa check. 331 00:17:32,470 --> 00:17:34,250 >> Kaya ni tingnan ang laki ipaalam. 332 00:17:34,250 --> 00:17:37,350 Kaya laki ay magiging kaakit-akit sa madaling dahil, alalahanin sa pag-load, hindi namin 333 00:17:37,350 --> 00:17:41,430 incrementing laki ng diksyunaryo para sa bawat salita na nakatagpo kami. 334 00:17:41,430 --> 00:17:45,350 Kaya laki ay pagpunta lamang sa bumalik laki na diksiyunaryo. 335 00:17:45,350 --> 00:17:47,390 At na ito. 336 00:17:47,390 --> 00:17:50,590 >> Kaya sa wakas ay mag-ibis namin. 337 00:17:50,590 --> 00:17:55,100 Kaya mag-ibis, kami ay pagpunta sa gumamit ng isang recursive function na upang aktwal na gawin ang lahat 338 00:17:55,100 --> 00:17:56,530 ng trabaho para sa amin. 339 00:17:56,530 --> 00:17:59,340 Kaya aming mga function ay pagpunta sa tawagin sa unloader. 340 00:17:59,340 --> 00:18:01,650 Ano ang unloader pagpunta sa gawin? 341 00:18:01,650 --> 00:18:06,580 Nakakakita kami dito na unloader ay pagpunta sa umulit sa ibabaw ng lahat ng mga bata sa 342 00:18:06,580 --> 00:18:08,410 ang partikular na node. 343 00:18:08,410 --> 00:18:11,750 At kung ang bata node ay hindi null, pagkatapos kami ay pagpunta sa 344 00:18:11,750 --> 00:18:13,730 alisan ng bala ang bata node. 345 00:18:13,730 --> 00:18:18,010 >> Kaya ito ay sa iyo recursively alisan ng bala lahat ng ating mga anak. 346 00:18:18,010 --> 00:18:21,080 Sa sandaling sigurado kami na ang lahat ng ating mga anak Na-deskargado, pagkatapos namin 347 00:18:21,080 --> 00:18:25,210 Maaari palayain ang ating mga sarili, sa gayon alisan ng bala ang ating mga sarili. 348 00:18:25,210 --> 00:18:29,460 Ito ay gagana recursively alisan ng bala ang buong trie. 349 00:18:29,460 --> 00:18:32,850 At pagkatapos ay isang beses na tapos na, maaari naming bumalik lang totoo. 350 00:18:32,850 --> 00:18:34,210 Hindi maaaring mabigo alisan ng kargada. 351 00:18:34,210 --> 00:18:35,710 Lamang kami pagbabakante bagay. 352 00:18:35,710 --> 00:18:38,870 Kaya sa sandaling tapos na kami pagbabakante ang lahat ng bagay, nagbabalik ng tunay. 353 00:18:38,870 --> 00:18:40,320 At na ito. 354 00:18:40,320 --> 00:18:41,080 Ang pangalan ko ay Rob. 355 00:18:41,080 --> 00:18:42,426 At ito ay speller. 356 00:18:42,426 --> 00:18:47,830 >> [MUSIC nagpe-play]