1 00:00:00,000 --> 00:00:02,740 [Powered by Google Translate] [Walkthrough - Problema Itakda 5] 2 00:00:02,740 --> 00:00:04,870 [Zamyla Chan - Harvard University] 3 00:00:04,870 --> 00:00:07,190 [Ito ay CS50. - CS50.TV] 4 00:00:07,190 --> 00:00:10,400 >> Ayos lang. Hello, lahat, at maligayang pagdating sa walkthrough 5. 5 00:00:10,400 --> 00:00:17,400 >> Pset5 ay mga maling spelling, kung saan kami gumagawa ng spell-checker. 6 00:00:17,400 --> 00:00:21,030 -Spell-pamato ay lubos na mahalaga. 7 00:00:21,030 --> 00:00:23,390 Ay ito kailanman nangyari sa iyo? 8 00:00:23,390 --> 00:00:27,170 Makipagtulungan ka napaka, napaka magtipon sa isang papel para sa isang pagkakagalit 9 00:00:27,170 --> 00:00:33,120 at pagkatapos pa rin ng isang napaka-rade ng glow tulad ng D o D = 10 00:00:33,120 --> 00:00:39,390 at lahat ng dahil ikaw ang liverwurst spoiler sa salitang whale malawak. 11 00:00:39,390 --> 00:00:44,710 Oo, pagwawasto iyong peppers ay isang bagay ng, ang sukdulan kawalan ng lakas. 12 00:00:44,710 --> 00:00:49,140 Ito ay isang problema na nakakaapekto sa tunay na lalaki, tunay na lalaki mag-aaral. 13 00:00:49,140 --> 00:00:56,260 Isang beses ako ay sinabi sa pamamagitan ng aking sith grado tagapagpapasakit na hindi ko nais na makakuha ng sa isang mahusay na kasamahan. 14 00:00:56,260 --> 00:01:00,250 At na ang lahat ko kailanman nais, na ang lahat ng kid anumang nais sa aking edad, 15 00:01:00,250 --> 00:01:04,569 lamang upang makakuha ng sa isang mahusay na kasamahan. 16 00:01:04,569 --> 00:01:12,720 At hindi lamang anumang kasamahan. Hindi. Nais kong pumunta sa isang kasamahan sa Ivory Legal. 17 00:01:12,720 --> 00:01:18,360 Kaya kung ako ay hindi pagpapabuti, nawala ang aking mga pangarap ng pagpunta sa Harvard, 18 00:01:18,360 --> 00:01:22,730 Jale, o Bilangguan - alam mo, sa Bilangguan, New Jersey. 19 00:01:22,730 --> 00:01:25,170 Kaya nakuha ko sa aking sarili ng spell-checker. 20 00:01:25,170 --> 00:01:29,380 Na ang isang maliit na sipi mula sa isa sa aking paboritong pasalitang salita artist, Taylor Mali. 21 00:01:29,380 --> 00:01:34,630 Pa rin, sabi niya, ang kahalagahan ng pagkakaroon ng spell-checker ay napakahalaga. 22 00:01:34,630 --> 00:01:39,440 >> Kaya Malugod sa walkthrough 5, na kung saan kami ay pakikipag-usap tungkol sa pset5: mga maling spelling, 23 00:01:39,440 --> 00:01:44,300 kung saan namin ang aming sariling spell-checker. 24 00:01:44,300 --> 00:01:50,880 Ang toolbox para sa linggong ito, ang code ng pamamahagi, ay mahalaga upang tumingin sa 25 00:01:50,880 --> 00:01:54,950 lamang upang maunawaan ang ibang mga function na ang iyong diksyunaryo ay pagpunta sa may. 26 00:01:54,950 --> 00:02:01,500 Aktwal Kami ay pagpunta sa ay ang pagkakaroon ng maramihang mga. File c na gumawa ng sama-sama ang aming pset. 27 00:02:01,500 --> 00:02:05,420 At kaya hinahanap sa pamamagitan ng iba't ibang aspeto, kahit na aktwal na kami ay hindi nag-e-edit 28 00:02:05,420 --> 00:02:10,770 isa sa mga file, speller.c, alam kung paano ito gumagana na may kaugnayan sa dictionary.c, 29 00:02:10,770 --> 00:02:14,100 na namin ang pagsusulat, ay medyo mahalaga. 30 00:02:14,100 --> 00:02:16,970 Ang pset spec din ay naglalaman ng maraming mga kapaki-pakinabang na impormasyon 31 00:02:16,970 --> 00:02:21,360 sa mga tuntunin ng mga bagay na maaari mong ipagpalagay, mga patakaran at mga bagay tulad na, 32 00:02:21,360 --> 00:02:24,710 kaya siguraduhin na basahin ang spec ng pset mabuti para sa mga tip. 33 00:02:24,710 --> 00:02:29,310 At kapag pagdududa ng isang panuntunan o isang bagay tulad na, pagkatapos ay palaging sumangguni sa spec ang pset 34 00:02:29,310 --> 00:02:31,550 o Talakayin. 35 00:02:31,550 --> 00:02:34,060 Ito ay pagpunta ang pset umasa mabigat sa payo, 36 00:02:34,060 --> 00:02:37,890 kaya gusto naming upang matiyak na naiintindihan namin ang pagkakaiba sa pagitan ng pagdaragdag ng mga bituin 37 00:02:37,890 --> 00:02:41,680 sa harap ng pangalan ng pointer at ampersand, kung paano magbakante ang mga ito, atbp. 38 00:02:41,680 --> 00:02:47,550 Kaya isang master ng mga payo upang maging lubhang kapaki-pakinabang sa set na ito ng problema. 39 00:02:47,550 --> 00:02:50,460 Kami ay pagpunta sa tumingin sa naka-link na listahan ng kaunti pang, 40 00:02:50,460 --> 00:02:57,790 kung saan mayroon kaming ang mga elemento na tinatawag naming node na may parehong halaga pati na rin ang pointer 41 00:02:57,790 --> 00:03:02,520 sa susunod na node, at iba pa mahalagang pag-link iba't ibang mga elemento isa pagkatapos ng isa. 42 00:03:02,520 --> 00:03:07,190 Mayroong ilang iba't ibang mga pagpipilian ng pagpapatupad ng iyong aktwal na diksyunaryo. 43 00:03:07,190 --> 00:03:13,150 Kami ay pagpunta sa tumingin sa dalawang pangunahing pamamaraan, na hash talahanayan at pagkatapos ay sinusubukan. 44 00:03:13,150 --> 00:03:17,660 Sa parehong ng mga sangkot na nila ang ilang uri ng paniwala ng isang naka-link na listahan 45 00:03:17,660 --> 00:03:20,790 kung saan mo elemento na naka-link sa isa't isa. 46 00:03:20,790 --> 00:03:25,640 At sa gayon kami ay pagpunta upang tumingin sa kung paano mo maaaring magagawang upang gumana sa paligid ng mga naka-link na listahan, 47 00:03:25,640 --> 00:03:29,680 likhain ang mga ito, mag-navigate sa mga tuntunin ng kung paano, halimbawa, magpasok ng isang node ito 48 00:03:29,680 --> 00:03:32,760 o libreng lahat ng node pati na rin. 49 00:03:32,760 --> 00:03:34,740 Sa mga tuntunin ng pagbabakante node, na talagang mahalaga 50 00:03:34,740 --> 00:03:37,700 tuwing namin malloc memory, pagkatapos magbakante namin ito. 51 00:03:37,700 --> 00:03:42,910 Kaya gusto namin upang matiyak na ang pointer walang pupunta unfreed, na hindi namin anumang mga paglabas ng memory. 52 00:03:42,910 --> 00:03:48,330 Kami ay pagpunta upang ipakilala ang isang tool na tinatawag na Valgrind na tumatakbo ang iyong programa 53 00:03:48,330 --> 00:03:52,260 at mga tseke kung ang lahat ng memory na iyong inilalaan ay pagkatapos ay napalaya. 54 00:03:52,260 --> 00:03:59,080 Lamang ang iyong pset ay makumpleto kapag ito gumagana at ito ay may ganap na pag-andar, 55 00:03:59,080 --> 00:04:03,990 ngunit din, Valgrind ay nagsasabi sa iyo na hindi mo pa nahanap ang anumang mga paglabas memory. 56 00:04:03,990 --> 00:04:06,690 Panghuli, para sa pset, ko talagang gusto Stress - 57 00:04:06,690 --> 00:04:11,360 Ibig kong sabihin, gaya ng dati, Ako ay talagang isang tagataguyod ng paggamit ng panulat at papel para sa iyong mga set ng problema, 58 00:04:11,360 --> 00:04:14,840 ngunit para sa isa, tingin ko na pen at papel ay lalong mahalaga 59 00:04:14,840 --> 00:04:19,000 kung kailan mo nais na pagguhit ng mga arrow sa mga bagay at pag-unawa kung paano bagay gumagana. 60 00:04:19,000 --> 00:04:24,440 Kaya talagang subukang gamitin ang pen at papel upang gumuhit ng mga bagay bago ka makapag-coding 61 00:04:24,440 --> 00:04:26,970 dahil maaaring makakuha ng bit ng magulo. 62 00:04:26,970 --> 00:04:30,700 >> Una, sabihin pumunta sa naka-link na mga listahan ng kaunti. 63 00:04:30,700 --> 00:04:35,510 Naka-link na listahan ay binubuo ng node, kung saan ang bawat node ay may halaga na nauugnay dito, 64 00:04:35,510 --> 00:04:39,810 pati na rin ang isang pointer sa susunod na node matapos itong. 65 00:04:39,810 --> 00:04:43,680 Ang ilang mga bagay na mahalaga sa mga naka-link na listahan na kailangan namin upang alalahanin 66 00:04:43,680 --> 00:04:48,810 kung saan ang aming unang node, at pagkatapos ay sa sandaling matapos namin alam kung saan ang unang node ay, 67 00:04:48,810 --> 00:04:52,990 na paraan na maaari naming ma-access ang node na ang unang node punto upang 68 00:04:52,990 --> 00:04:55,850 at pagkatapos ay matapos na at ang isa matapos na. 69 00:04:55,850 --> 00:05:00,340 At pagkatapos ay ang huling elemento sa iyong listahan ng naka-link pointer na node 70 00:05:00,340 --> 00:05:02,340 ay palaging pagpunta upang tumuro sa null. 71 00:05:02,340 --> 00:05:08,230 Kapag ang isang puntos ng node sa null, pagkatapos ay alam mo na naabot mo na ang dulo ng listahan, 72 00:05:08,230 --> 00:05:12,320 na node ay ang huling isa, na may walang matapos na. 73 00:05:12,320 --> 00:05:16,970 Dito sa eskematiko na ito, makikita mo na ang mga arrow ay ang mga payo, 74 00:05:16,970 --> 00:05:20,290 at ang mga asul na seksyon na kung saan ang halaga ay naka-imbak, 75 00:05:20,290 --> 00:05:24,420 at pagkatapos ay ang pulang kahon na may ang pointer dito pointer sa node 76 00:05:24,420 --> 00:05:27,050 na tumuturo sa susunod na node matapos itong. 77 00:05:27,050 --> 00:05:33,730 At kaya makikita mo dito, ang D node ay tumuturo sa null sapagkat ito ay ang huling elemento sa listahan. 78 00:05:33,730 --> 00:05:38,240 >> Tingnan natin sa kung paano namin tukuyin ang isang struct para sa isang node. 79 00:05:38,240 --> 00:05:40,130 At dahil gusto naming magkaroon ng maramihang mga node, 80 00:05:40,130 --> 00:05:43,180 ito ay pagpunta sa maging isang typedef struct 81 00:05:43,180 --> 00:05:46,870 kung saan kami ay pagpunta sa magkaroon ng ilang iba't-ibang mga kaso ng node. 82 00:05:46,870 --> 00:05:50,850 At kaya namin tukuyin ang mga ito bilang isang bagong uri ng data. 83 00:05:50,850 --> 00:05:53,630 Dito, mayroon kaming isang typedef struct node. 84 00:05:53,630 --> 00:05:56,160 Sa halimbawang ito, kami ay pagharap sa integer node, 85 00:05:56,160 --> 00:06:00,490 kaya kami ay may isang integer na may pangalang halaga at pagkatapos namin ng isa pang pointer, 86 00:06:00,490 --> 00:06:07,390 at sa kasong ito, ito ay isang pointer sa isang node, kaya kami ay may isang struct node * tinatawag susunod. 87 00:06:07,390 --> 00:06:09,520 At pagkatapos kami ay pagtawag sa buong node bagay na ito. 88 00:06:09,520 --> 00:06:11,110 Tiyakin na sundin mo ang syntax na ito. 89 00:06:11,110 --> 00:06:17,940 Pansinin na node ay aktwal-reference up sa itaas pati na rin sa ibaba ang kulot tirante. 90 00:06:17,940 --> 00:06:23,400 Pagkatapos upang subaybayan kung saan ang aking unang node sa naka-link na listahan, 91 00:06:23,400 --> 00:06:29,390 Mayroon akong isang node pointer na tinatawag na ulo, at ako malloc espasyo sapat para sa laki ng isang node. 92 00:06:29,390 --> 00:06:36,240 Paunawa, gayunpaman, ang ulo na ay talagang isang node pointer bilang kabaligtaran sa isang aktwal na node mismo. 93 00:06:36,240 --> 00:06:40,130 Kaya ulo aktwal na ay hindi naglalaman ng anumang halaga, 94 00:06:40,130 --> 00:06:45,590 POINTS lamang ito sa alinman ang unang node sa aking listahan ng naka-link. 95 00:06:55,080 --> 00:06:58,340 >> Upang makakuha ng isang mas mahusay na pakiramdam ng mga naka-link na listahan, dahil ito ay napakahalaga 96 00:06:58,340 --> 00:07:02,220 subaybayan ng siguraduhin na mapanatili mo ang chain, 97 00:07:02,220 --> 00:07:09,990 Gusto ko sa tingin ng ito ng mga tao sa isang linya na may hawak kamay, 98 00:07:09,990 --> 00:07:14,330 kung saan ang bawat tao ay may hawak kamay sa susunod na. 99 00:07:14,330 --> 00:07:18,350 Hindi mo maaaring makita sa guhit na ito, ngunit isa lamang sila nagtuturo sa susunod na tao 100 00:07:18,350 --> 00:07:23,760 na sa kanilang chain. 101 00:07:23,760 --> 00:07:29,270 At kaya kung gusto mong pagbagtas isang naka-link na listahan kung saan ang mga taong ito - 102 00:07:29,270 --> 00:07:32,830 isipin ang lahat ng mga taong iyon ay may halaga na nauugnay sa kanila 103 00:07:32,830 --> 00:07:36,590 at ituro din sa susunod na tao sa linya - 104 00:07:36,590 --> 00:07:40,810 kung gusto mong pagbagtas sa naka-link na listahan, halimbawa, upang i-edit ang mga halaga 105 00:07:40,810 --> 00:07:42,830 o paghahanap para sa isang halaga o isang bagay tulad na, 106 00:07:42,830 --> 00:07:48,270 makikita mo nais upang magkaroon ng isang pointer sa partikular na tao. 107 00:07:48,270 --> 00:07:52,670 Kaya kami ay pagpunta sa magkaroon ng data uri ng node pointer. 108 00:07:52,670 --> 00:07:55,580 Para sa halimbawang ito, sabihin tumawag ito cursor. 109 00:07:55,580 --> 00:07:59,630 Isa pang karaniwang paraan upang pangalanan ito ay iterator o isang bagay tulad na 110 00:07:59,630 --> 00:08:05,130 dahil ito iterating at aktwal na paglipat kung aling node ito na tumuturo sa. 111 00:08:05,130 --> 00:08:14,410 Dito ay ang aming cursor. 112 00:08:14,410 --> 00:08:20,180 Aming cursor ay unang ituro sa unang elemento sa aming listahan. 113 00:08:20,180 --> 00:08:26,910 At kaya kung ano ang gusto naming gawin ay gusto namin talaga ay magpatuloy ang cursor, 114 00:08:26,910 --> 00:08:29,130 gumagalaw ito mula sa gilid sa gilid. 115 00:08:29,130 --> 00:08:33,409 Sa kasong ito, nais naming upang ilipat ang mga ito sa susunod na elemento sa listahan. 116 00:08:33,409 --> 00:08:38,480 Sa mga array, kung ano ang gusto naming gawin ay gusto lang namin sabihin namin dagdagan ang index ng 1. 117 00:08:38,480 --> 00:08:46,020 Sa kasong ito, kung ano ang kailangan namin upang gawin ang aktwal na mahanap kung saan ang tao ang kasalukuyang tao ay tumuturo sa, 118 00:08:46,020 --> 00:08:48,930 at na na ang susunod na halaga. 119 00:08:48,930 --> 00:08:53,230 Kaya kung cursor lamang node pointer, pagkatapos kung ano ang gusto naming gawin 120 00:08:53,230 --> 00:08:56,320 nais namin upang makakuha ng sa ang halaga na ang cursor ay tumuturo sa. 121 00:08:56,320 --> 00:09:01,350 Gusto naming upang makakuha ng sa node na iyon at pagkatapos, kapag hindi namin na node, hanapin kung saan ito na tumuturo sa. 122 00:09:01,350 --> 00:09:05,820 Upang makapunta sa aktwal na node na ang cursor ay tumuturo sa, 123 00:09:05,820 --> 00:09:13,160 karaniwang ipahiwatig namin ito sa pamamagitan ng (* cursor). 124 00:09:13,160 --> 00:09:19,160 Na ay magbibigay sa iyo ang aktwal na node na cursor ay tumuturo sa. 125 00:09:19,160 --> 00:09:21,730 At pagkatapos ay matapos na, kung ano ang gusto naming gawin ay gusto naming i-access 126 00:09:21,730 --> 00:09:25,680 anumang na ang susunod na halaga ng node ay. 127 00:09:25,680 --> 00:09:32,820 Upang gawin na, upang ma-access ang mga halaga sa loob ng struct, mayroon kaming ang tuldok operator. 128 00:09:32,820 --> 00:09:39,530 Kaya pagkatapos ay ito ay (* cursor). Susunod. 129 00:09:39,530 --> 00:09:44,840 Ngunit ito ay isang bit magulo sa mga tuntunin ng pagkakaroon ng mga bracket sa paligid ng cursor *, 130 00:09:44,840 --> 00:09:56,800 at kaya namin palitan ang buong pahayag na may cursor->. 131 00:09:56,800 --> 00:10:02,700 Ito ay isang gitling at pagkatapos ay mas malaki kaysa sa pag-sign, kaya paggawa ng isang arrow. 132 00:10:02,700 --> 00:10:05,840 cursor-> susunod. 133 00:10:05,840 --> 00:10:12,390 Na ang aktwal na makakuha mo ang node na ang cursor puntos. Na ang halaga ng susunod na. 134 00:10:12,390 --> 00:10:16,790 Kaya sa halip ng pagkakaroon ng star at ang tuldok, ikaw ay pinapalitan na may isang arrow. 135 00:10:16,790 --> 00:10:24,820 Maging maingat upang tiyakin na sinusubukan mong gamitin ang syntax na ito. 136 00:10:33,550 --> 00:10:37,620 >> Ngayon na kami ay may aming cursor, kung gusto naming i-access ang halaga, 137 00:10:37,620 --> 00:10:40,450 bago, nagkaroon kami cursor-> susunod, 138 00:10:40,450 --> 00:10:46,260 ngunit upang ma-access ang halaga sa node na ang cursor ay tumuturo sa, namin lamang lamang sabihin 139 00:10:46,260 --> 00:10:48,070 node-> halaga. 140 00:10:48,070 --> 00:10:53,600 Mula doon, ito ay ng uri ng data anumang tinukoy kami ang mga halaga at ang mga node upang maging. 141 00:10:53,600 --> 00:10:59,620 Kung ito ay isang int node, cursor-> halaga lamang pagpunta sa maging isang integer. 142 00:10:59,620 --> 00:11:04,870 Upang maaari naming gawin ang mga pagpapatakbo sa na, i-check ang equalities, italaga ito ng mga iba't ibang mga halaga, atbp. 143 00:11:04,870 --> 00:11:11,090 Kaya pagkatapos kung ano ang gusto mong gawin kung gusto mong ilipat ang iyong cursor sa susunod na tao, 144 00:11:11,090 --> 00:11:15,270 iyong aktwal na baguhin ang halaga ng cursor. 145 00:11:15,270 --> 00:11:19,340 Dahil ang cursor ay isang node pointer, baguhin mo ang aktwal na address ng pointer 146 00:11:19,340 --> 00:11:23,890 sa address ng susunod na node sa iyong listahan. 147 00:11:23,890 --> 00:11:28,930 Ito ay ilang mga code na kung saan maaari mong umulit. 148 00:11:28,930 --> 00:11:31,230 Kung saan mayroon akong komento sa gawin ang isang bagay, 149 00:11:31,230 --> 00:11:33,850 na kung saan marahil ka upang ma-access ang halaga 150 00:11:33,850 --> 00:11:37,850 o gawin ang isang bagay na gawin sa partikular na node. 151 00:11:37,850 --> 00:11:43,050 Upang simulan-off ito, sinasabi ko na ang aking cursor sa simula 152 00:11:43,050 --> 00:11:48,430 ay upang tumuro sa unang elemento sa naka-link na listahan. 153 00:11:48,430 --> 00:11:52,910 At kaya hanggang magpatuloy, na tinukoy ko ito bilang ang ulo ng node. 154 00:11:52,910 --> 00:11:57,610 >> Tulad ng aking nabanggit bago, pagbabakante ay talagang mahalaga. 155 00:11:57,610 --> 00:12:02,440 Nais mong tiyakin na magbakante bawat elemento sa listahan kapag natapos mo na dito. 156 00:12:02,440 --> 00:12:04,940 Kapag hindi mo na kailangang upang isangguni ang anumang ng mga payo, 157 00:12:04,940 --> 00:12:10,620 nais mong tiyakin na magbakante mo ang lahat ng mga payo. 158 00:12:10,620 --> 00:12:14,460 Ngunit nais mong maging maingat dito sa na nais mong upang maiwasan ang anumang mga paglabas ng memorya. 159 00:12:14,460 --> 00:12:25,080 Kung ang ka ng libreng isang tao maaga, pagkatapos ang lahat ng payo na na node puntos upang 160 00:12:25,080 --> 00:12:26,900 pagpunta sa mawawala. 161 00:12:26,900 --> 00:12:32,070 Pagpunta pabalik sa halimbawa sa tao upang gumawa ito ng kaunti mas mataas na pusta, 162 00:12:32,070 --> 00:12:49,600 sabihin may mga taong ito, maliban sa kasong ito sila ay pagpasada sa isang lawa na may halimaw. 163 00:12:49,600 --> 00:12:53,200 Nais naming tiyakin na tuwing magbakante namin, hindi namin mawala 164 00:12:53,200 --> 00:12:58,920 at bitawan ng anumang node bago aktwal namin ang napalaya sa kanila. 165 00:12:58,920 --> 00:13:05,730 Halimbawa, kung ikaw ay lamang tumawag ng libre sa tao na ito dito, 166 00:13:05,730 --> 00:13:15,350 siya ay napalaya, ngunit pagkatapos ang lahat ng mga guys ay pagkatapos ay mawawala 167 00:13:15,350 --> 00:13:18,450 at gusto nila sumama sa agos off at matumba. 168 00:13:18,450 --> 00:13:24,900 Kaya gusto namin upang matiyak na sa halip, gusto namin upang mapanatili ang isang link sa natitirang. 169 00:13:37,630 --> 00:13:42,480 Aming pointer sa ulo, na mga punto sa unang elemento sa listahan. 170 00:13:42,480 --> 00:13:49,990 Ito ay uri ng tulad ng isang lubid angkora ang unang tao. 171 00:13:52,870 --> 00:13:57,470 Ano ang maaaring gusto mong gawin kapag magbakante listahan ng may - 172 00:13:57,470 --> 00:14:04,520 Kung nais mong magbakante muna sa unang elemento, pagkatapos ay maaari kang magkaroon ng isang pansamantalang pointer 173 00:14:04,520 --> 00:14:07,370 na tumuturo sa anumang sa unang elemento. 174 00:14:07,370 --> 00:14:11,420 Kaya mayroon ka sa iyong pansamantalang pointer pagturo dito. 175 00:14:11,420 --> 00:14:15,840 Sa ganoong paraan, mayroon kaming isang hold ng unang node. 176 00:14:15,840 --> 00:14:18,930 At pagkatapos, dahil alam namin na ang unang node ay pagpunta sa ay napalaya, 177 00:14:18,930 --> 00:14:24,890 pagkatapos ay maaari naming ilipat ang lubid, ang anchor, ang aming ulo, 178 00:14:24,890 --> 00:14:31,930 sa aktwal na tumuturo sa anumang unang na tumuturo sa. 179 00:14:31,930 --> 00:14:38,760 Kaya ang ulo na ito ay aktwal na mga punto sa pangalawang elemento sa ngayon. 180 00:14:38,760 --> 00:14:43,980 Ngayon kami ay pinapayagan upang magbakante anumang ay naka-imbak sa Temp, 181 00:14:43,980 --> 00:14:53,360 at upang maaari naming burahin na hindi ito mapanganib ang lahat ng iba pang mga node sa aming listahan. 182 00:14:54,140 --> 00:15:05,020 Ang isa pang paraan na maaari mong gawin ito ay maaaring 183 00:15:05,020 --> 00:15:08,650 tuwing magbakante lamang ang huling elemento sa listahan 184 00:15:08,650 --> 00:15:11,010 dahil sila ay hindi katiyakan sa tulis sa anumang bagay. 185 00:15:11,010 --> 00:15:15,570 Kaya maaari mong magbakante ito, pagkatapos libreng ang isang ito, ang libreng ang isang ito. 186 00:15:15,570 --> 00:15:21,900 Na talagang gumagana ngunit ng kaunti mas mabagal dahil sa pamamagitan ng likas na katangian ng naka-link na listahan, 187 00:15:21,900 --> 00:15:24,670 hindi lamang namin ay maaaring agad na lumipat sa huling. 188 00:15:24,670 --> 00:15:28,030 Mayroon kaming pagbagtas bawat elemento sa naka-link na listahan 189 00:15:28,030 --> 00:15:31,020 at suriin kung ang isa na ay tumuturo sa null, suriin ang bawat oras na, 190 00:15:31,020 --> 00:15:33,780 at pagkatapos ay sa sandaling matapos namin maabot ang pagtatapos, pagkatapos libreng na. 191 00:15:33,780 --> 00:15:40,270 Kung ikaw ay upang gawin ang prosesong ito, nais mong aktwal na check dito, 192 00:15:40,270 --> 00:15:44,190 check dito, pagkatapos check dito, pagbabakante ito, 193 00:15:44,190 --> 00:15:47,470 pagkatapos balik, check dito, check dito, pagbabakante ito, 194 00:15:47,470 --> 00:15:49,660 check dito, at pagkatapos ay pagbabakante ito. 195 00:15:49,660 --> 00:15:52,880 Na tumatagal ng kaunti pang oras. Oo. 196 00:15:52,880 --> 00:15:59,060 >> [Mag-aaral] Gusto ito ay posible na gumawa ng isang naka-link na listahan na nag-iimbak ng isang exit pointer sa dulo? 197 00:15:59,060 --> 00:16:01,320 Na tiyak na panahon. 198 00:16:01,320 --> 00:16:08,340 Upang ulitin ang tanong, ay posibleng magkaroon ng naka-link na istraktura ng listahan 199 00:16:08,340 --> 00:16:12,490 tulad na mayroon kang isang pointer na tumuturo sa dulo ng naka-link na listahan? 200 00:16:12,490 --> 00:16:18,090 Gusto kong sabihin na posible, at ang bawat oras na magpasok ng isang bagay sa iyong listahan ng naka-link 201 00:16:18,090 --> 00:16:21,470 nais mong i-update ang na pointer at mga bagay tulad na. 202 00:16:21,470 --> 00:16:26,640 Mayroon kang isang node * buntot, halimbawa. 203 00:16:26,640 --> 00:16:29,840 Ngunit kapag ikaw ay pagpapatupad ng ang tampok na ito, mayroon kang mag-isip ng kalakalan-offs, 204 00:16:29,840 --> 00:16:32,700 bang kung gaano karaming beses ako pagpunta sa ay iterating sa paglipas ng ito, 205 00:16:32,700 --> 00:16:36,100 kung paano mahirap ito upang subaybayan ng buntot pati na rin ang ulo 206 00:16:36,100 --> 00:16:38,400 pati na rin ang aking iterator, at mga bagay tulad na. 207 00:16:40,730 --> 00:16:42,480 Sinusuportahan ba na -? >> [Mag-aaral] Oo. 208 00:16:42,480 --> 00:16:48,270 Posible, ngunit sa mga tuntunin ng mga desisyon ng disenyo, mayroon kang sa timbangin ang mga pagpipilian. 209 00:16:53,850 --> 00:17:01,090 >> Narito ang isang balangkas ng code na ay magbibigay-daan sa iyo upang magbakante bawat elemento sa isang naka-link na listahan. 210 00:17:01,090 --> 00:17:05,460 Muli, dahil ako iterating sa loob ng isang naka-link na listahan, ako pagpunta sa nais na magkaroon ng ilang mga uri ng cursor 211 00:17:05,460 --> 00:17:08,670 o iterator. 212 00:17:08,670 --> 00:17:14,640 Namin ay iterating hanggang ang cursor ay null. 213 00:17:14,640 --> 00:17:17,640 Hindi mo nais upang umulit kapag ang iyong cursor ay null 214 00:17:17,640 --> 00:17:20,579 dahil na ay nangangahulugan na walang anuman sa listahan. 215 00:17:20,579 --> 00:17:25,069 Kaya pagkatapos dito gumawa ako ng isang pansamantalang node * 216 00:17:25,069 --> 00:17:29,610 na tumuturo sa kung ano ang isinasaalang-alang ako ay ang unang ng aking listahan, 217 00:17:29,610 --> 00:17:35,340 at pagkatapos ko bang ilipat ang aking cursor magpatuloy 1 at pagkatapos libreng anumang ko nagkaroon sa pansamantalang imbakan. 218 00:17:38,460 --> 00:17:43,650 >> Na namin ngayon sa pagpasok sa naka-link na listahan. 219 00:18:00,200 --> 00:18:09,660 Mayroon akong tatlong node sa aking naka-link na listahan, at sabihin pumunta sa mga simpleng kaso 220 00:18:09,660 --> 00:18:18,970 kung saan nais namin upang magpasok ng isa pang node sa dulo ng aming mga listahan ng naka-link. 221 00:18:18,970 --> 00:18:25,980 Upang gawin na, ang lahat ng gusto naming gawin ay na namin pagbagtas 222 00:18:25,980 --> 00:18:32,100 upang mahanap kung saan ang kasalukuyang dulo ng naka-link na listahan ay, kaya alinmang node ay tumuturo sa Null - 223 00:18:32,100 --> 00:18:33,850 na ang isang ito - 224 00:18:33,850 --> 00:18:37,260 at pagkatapos ay sabihin, aktwal na, ang isang ito ay hindi na ang huling node; 225 00:18:37,260 --> 00:18:39,830 aktwal na kami ay pagpunta sa isa pa. 226 00:18:39,830 --> 00:18:46,260 Kaya gusto namin ito kasalukuyang isang punto sa anumang namin ang pagpasok. 227 00:18:46,260 --> 00:18:50,080 Kaya ngayon ito pulang tao dito naging ang huling node sa naka-link na listahan. 228 00:18:50,080 --> 00:18:56,080 At kaya ang katangian ng huling node sa naka-link na listahan ay na punto upang null. 229 00:18:56,080 --> 00:19:09,380 Kaya pagkatapos ay kung ano ang gusto naming gawin ay itakda ang pointer ito pulang tao sa null. Doon. 230 00:19:09,380 --> 00:19:25,370 >> Ngunit ano kung gusto namin upang magpasok ng isang node in sa pagitan ng pangalawa at pangatlong? 231 00:19:25,370 --> 00:19:28,960 Na ang isa ay hindi lubos na simple dahil gusto naming matiyak na 232 00:19:28,960 --> 00:19:34,290 na hindi namin ipaalam sa pumunta ng anumang node sa aming listahan ng naka-link. 233 00:19:34,290 --> 00:19:43,450 Ano ang gusto naming gawin tiyakin na namin anchor sa ating sarili sa bawat isa. 234 00:19:43,450 --> 00:19:49,900 Halimbawa, sabihin tinatawag ito ang pangalawang. 235 00:19:49,900 --> 00:19:54,390 Kung sinabi mo ang pangalawang ngayon punto upang ang bagong 236 00:19:54,390 --> 00:20:02,520 at mo lamang ginawa ng isang pointer doon, na magreresulta sa tao na ito na nawala 237 00:20:02,520 --> 00:20:07,830 dahil doon ay hindi anumang link sa kanya. 238 00:20:07,830 --> 00:20:18,970 Sa halip - ako gumuhit ito muli. Mawalang ang aking mga artistikong kakayahan. 239 00:20:18,970 --> 00:20:26,570 Alam namin na hindi lamang namin maaaring direktang link 2 sa bagong. 240 00:20:26,570 --> 00:20:30,480 Mayroon kaming upang matiyak na hawakan namin sa huling. 241 00:20:30,480 --> 00:20:39,200 Ano ang maaari naming nais gawin ay magkaroon ng isang pansamantalang pointer 242 00:20:39,200 --> 00:20:42,650 sa elemento na pagpunta sa ikinakabit sa. 243 00:20:42,650 --> 00:20:45,140 Kaya pagkatapos namin magkaroon ng pansamantalang pointer doon. 244 00:20:45,140 --> 00:20:50,780 Dahil alam namin na ang ikatlong isa ay pinananatiling track ng, 245 00:20:50,780 --> 00:20:53,680 2 maaari na ngayong mag-link sa aming bagong isa. 246 00:20:53,680 --> 00:20:57,490 At kung ito bagong pulang tao ay magiging sa pagitan ng 2 at 3, 247 00:20:57,490 --> 00:21:05,550 pagkatapos kung ano ang pointer na tao upang tumuro sa? >> [Mag-aaral] Temp. 248 00:21:05,550 --> 00:21:07,490 Temp. Oo. 249 00:21:07,490 --> 00:21:15,430 Kaya ang susunod na halaga ng ito pulang tao ay pagpunta sa Temp. 250 00:21:26,090 --> 00:21:33,010 Kapag ikaw ay pagpasok sa naka-link na listahan, nakita namin na maaari naming 251 00:21:33,010 --> 00:21:38,260 madaling magdagdag ng isang bagay sa dulo sa pamamagitan ng paglikha ng isang pansamantalang array, 252 00:21:38,260 --> 00:21:42,850 o kung gusto naming upang magdagdag ng isang bagay sa gitna ng aming mga array, 253 00:21:42,850 --> 00:21:46,810 tumagal ng kaunti pang shuffling sa paligid. 254 00:21:46,810 --> 00:21:50,240 Kung nais mong, halimbawa, isang pinagsunod-sunod na naka-link na listahan, 255 00:21:50,240 --> 00:21:54,880 pagkatapos ay mayroon kang uri ng timbangin ang mga gastos at mga benepisyo ng na 256 00:21:54,880 --> 00:21:59,720 dahil kung gusto mong magkaroon ng isang pinagsunod-sunod na array, na nangangahulugan na ang bawat oras mong ipasok ito, 257 00:21:59,720 --> 00:22:01,630 ito ay pagpunta sa tumagal ng kaunti pang oras. 258 00:22:01,630 --> 00:22:05,500 Gayunpaman, kung gusto mong mamaya sa, dahil kakailanganin namin mahanap namin nais na, 259 00:22:05,500 --> 00:22:10,280 paghahanap sa pamamagitan ng isang naka-link na listahan, pagkatapos ay maaari itong maging mas madali kung alam mo na ang lahat ng bagay ay upang. 260 00:22:10,280 --> 00:22:15,340 Kaya baka gusto mong timbangin ang mga gastos at mga benepisyo ng na. 261 00:22:20,150 --> 00:22:27,740 >> Ang isa pang paraan upang ipasok sa isang naka-link na listahan ay upang ipasok sa simula ng isang listahan. 262 00:22:27,740 --> 00:22:34,700 Kung gumuhit namin ang aming anchor dito - ito ay ang aming ulo - 263 00:22:34,700 --> 00:22:40,960 at pagkatapos na ang mga taong ito na naka-link dito, 264 00:22:40,960 --> 00:22:48,460 at pagkatapos kami ay may isang bagong node na ipinasok sa simula, 265 00:22:48,460 --> 00:22:52,590 pagkatapos kung ano ang maaari naming nais gawin? 266 00:22:55,220 --> 00:23:03,580 Ano ang mali na may lamang sinasabi na gusto kong i-link ang pula sa asul, 267 00:23:03,580 --> 00:23:05,790 dahil na ang unang isa? 268 00:23:05,790 --> 00:23:08,570 Kung ano ang mangyayari dito? 269 00:23:08,570 --> 00:23:12,130 Ang lahat ng mga tatlong ay mawawala. 270 00:23:12,130 --> 00:23:14,140 Kaya hindi namin nais upang gawin iyon. 271 00:23:14,140 --> 00:23:21,430 Muli, natutunan namin na kailangan namin upang magkaroon ng ilang mga uri ng pansamantalang pointer. 272 00:23:21,430 --> 00:23:34,470 Natin pumili upang magkaroon ng isang pansamantalang nagtuturo sa tao na ito. 273 00:23:34,470 --> 00:23:39,640 Pagkatapos ay maaari kaming magkaroon ng asul isang punto sa pansamantalang 274 00:23:39,640 --> 00:23:43,240 at pagkatapos ay ang pulang point sa asul. 275 00:23:43,240 --> 00:23:47,830 Ang dahilan kung bakit gumagamit ako ng mga tao dito ay dahil gusto talaga namin upang mailarawan ang 276 00:23:47,830 --> 00:23:53,180 may hawak na sa mga tao at tinitiyak na kami ay may isang link sa kanila 277 00:23:53,180 --> 00:23:57,590 bago namin ipaalam sa pumunta ng isa pang kamay o isang bagay tulad na. 278 00:24:05,630 --> 00:24:10,650 >> Ngayon na kami ay may isang pakiramdam ng mga naka-link na listahan - kung paano maaari naming lumikha ng isang naka-link na listahan 279 00:24:10,650 --> 00:24:15,090 at lumikha ang mga kaayusan para sa na binubuo ng ang kahulugan ng uri para sa isang node 280 00:24:15,090 --> 00:24:19,060 at pagkatapos ay siguraduhin na mayroon kami ng pointer sa ulo ng na naka-link na listahan - 281 00:24:19,060 --> 00:24:23,210 sa sandaling mayroon kaming na at alam namin kung paano pagbagtas sa pamamagitan ng isang array, 282 00:24:23,210 --> 00:24:28,200 ma-access ang iba't ibang mga elemento, alam namin kung paano upang ipasok at alam namin kung paano magbakante ang mga ito, 283 00:24:28,200 --> 00:24:30,260 maaari naming makakuha ng sa mga maling spelling. 284 00:24:30,260 --> 00:24:38,150 Gaya ng dati, mayroon kaming isang seksyon ng mga tanong na makapag ginamit mo sa operating na may mga naka-link na listahan 285 00:24:38,150 --> 00:24:41,750 at iba't-ibang kaayusan tulad ng mga queues at stack. 286 00:24:41,750 --> 00:24:46,000 Pagkatapos ay maaari naming ilipat sa maling spelling. 287 00:24:46,000 --> 00:24:55,170 >> Mga maling pagbabaybay ay may sa code ng pamamahagi ng ilang mga file ng kahalagahan. 288 00:24:55,170 --> 00:24:58,850 Unang napansin namin na mayroon namin ito Makefile dito, 289 00:24:58,850 --> 00:25:03,040 kung saan hindi namin talagang nakatagpo ng bago. 290 00:25:03,040 --> 00:25:10,090 Kung ikaw ay tumingin sa loob ng pset5 folder, gusto mong mapansin na mayroon ka ng isang file na. H, 291 00:25:10,090 --> 00:25:12,530 pagkatapos ay mayroon kang dalawang. file c. 292 00:25:12,530 --> 00:25:18,920 Ano Makefile ito ginagawa ay bago, gusto naming i-type lamang gumawa at pagkatapos ay ang pangalan ng programa 293 00:25:18,920 --> 00:25:25,550 at pagkatapos ay namin makita ang lahat ng mga argumento at flag na nakapasa sa sa tagatala. 294 00:25:25,550 --> 00:25:30,580 Ano ang Makefile ginagawa ay nagbibigay-daan sa amin upang ipunin ang ilang mga file nang sabay-sabay 295 00:25:30,580 --> 00:25:34,650 at pumasa sa flag na gusto namin. 296 00:25:34,650 --> 00:25:41,300 Narito lang namin kung may isang header na file dito. 297 00:25:41,300 --> 00:25:43,730 Pagkatapos namin ang aktwal na may dalawang source file. 298 00:25:43,730 --> 00:25:47,520 Mayroon kaming speller.c at dictionary.c. 299 00:25:47,520 --> 00:25:54,560 Maligayang pagdating sa i-edit ang Makefile kung nais mo. 300 00:25:54,560 --> 00:26:03,310 Pansinin na dito kung nagta-type ka malinis, at pagkatapos ay kung ano ang ginagawa nito ay talagang aalis ng anumang 301 00:26:03,310 --> 00:26:06,340 na ang core. 302 00:26:06,340 --> 00:26:09,190 Kung ikaw Mayroon segmentation fault, talaga kang makakuha ng core dump. 303 00:26:09,190 --> 00:26:13,260 Kaya ito pangit maliit na file ay lilitaw sa iyong direktoryo ng tinatawag na core. 304 00:26:13,260 --> 00:26:16,310 Makikita mo nais na alisin na upang gawin itong linisin. 305 00:26:16,310 --> 00:26:20,940 Ito aalis ng anumang mga file ng exe at o file. 306 00:26:27,900 --> 00:26:30,220 >> Natin tingnan sa dictionary.h. 307 00:26:30,220 --> 00:26:34,410 Ito sabi ni na ito declares-andar ng diksyunaryo. 308 00:26:34,410 --> 00:26:39,530 Mayroon kaming isang maximum na haba para sa anumang salita sa diksyunaryo. 309 00:26:39,530 --> 00:26:45,130 Sinasabi namin na ito ay ang pinakamahabang posibleng salita. Ng haba 45. 310 00:26:45,130 --> 00:26:48,900 Kaya hindi namin ay pagpunta sa anumang mga salita na lumampas na haba. 311 00:26:48,900 --> 00:26:50,980 Narito lang namin ang modelo ng function na. 312 00:26:50,980 --> 00:26:55,290 Hindi namin ang aktwal na pagpapatupad dahil na kung ano ang makikita namin ginagawa para sa pset. 313 00:26:55,290 --> 00:26:59,940 Ngunit ano ito ginagawa ay dahil kami ay pagharap sa mas malaking file dito 314 00:26:59,940 --> 00:27:06,650 at pag-andar sa isang mas malaking scale, ito ay kapaki-pakinabang upang magkaroon ng isang file na. h 315 00:27:06,650 --> 00:27:11,290 sa gayon na ang ibang tao pagbabasa o paggamit ng iyong code ay maaaring maunawaan kung ano ang nangyayari sa. 316 00:27:11,290 --> 00:27:17,910 At maaaring gusto nilang ipatupad sinusubukan kung ginawa mo hash na mga talahanayan o vice versa. 317 00:27:17,910 --> 00:27:21,850 Pagkatapos ay sila sabihin sa aking ng pagkarga function na, 318 00:27:21,850 --> 00:27:26,950 ang aktwal na pagpapatupad ay pagpunta sa-iba, ngunit ang prototype na ito ay hindi magbabago. 319 00:27:26,950 --> 00:27:33,280 Narito namin na suriin, na nagbabalik ng tunay na kung ang isang ibinigay na salita sa diksyunaryo. 320 00:27:33,280 --> 00:27:39,800 Pagkatapos kami ay may load, na isa lamang tumatagal sa isang file ng diksyunaryo 321 00:27:39,800 --> 00:27:44,360 at pagkatapos ay ikinarga ito sa ilang mga istraktura ng data. 322 00:27:44,360 --> 00:27:47,500 Mayroon kaming mga laki, kung saan, kapag tinatawag, nagbabalik ang laki ng iyong diksyunaryo, 323 00:27:47,500 --> 00:27:50,310 kung gaano karaming mga salita ay naka-imbak sa loob nito, 324 00:27:50,310 --> 00:27:54,390 at pagkatapos ay mag-ibis maglapag, na frees ang lahat ng memory na iyong kinuha up 325 00:27:54,390 --> 00:27:57,900 habang paggawa ng iyong diksyunaryo. 326 00:28:01,070 --> 00:28:03,590 >> Natin tingnan sa dictionary.c. 327 00:28:03,590 --> 00:28:10,490 Nakikita namin na ito ay mukhang katulad na katulad sa dictionary.h, maliban ngayon ito lang ay may lahat ng ng mga TODOs sa ito. 328 00:28:10,490 --> 00:28:16,980 At kaya na ang iyong trabaho. Sa paglaon, makikita mo na pagpuno sa speller.c sa lahat ng ang code na ito. 329 00:28:16,980 --> 00:28:21,540 Dictionary.c, kapag nagpatakbo, ay hindi talagang pagpunta sa gawin, 330 00:28:21,540 --> 00:28:29,590 kaya tinitingnan namin patungo speller.c upang makita ang aktwal na pagpapatupad ng spell-checker. 331 00:28:29,590 --> 00:28:32,060 Kahit na hindi ka pagpunta sa pag-edit ng anumang ng ang code na ito, 332 00:28:32,060 --> 00:28:38,050 mahalaga ito upang mabasa, maunawaan kapag tinatawag ay ng pagkarga, kapag ako pagtawag ng tseke, 333 00:28:38,050 --> 00:28:42,350 lamang upang maunawaan, imapa ito, tingnan kung paano gumagana ang ang function. 334 00:28:42,350 --> 00:28:49,860 Nakita namin na ito ay check para sa tamang paggamit. 335 00:28:49,860 --> 00:28:55,200 Mahalaga, kapag ang isang tao na tumatakbo ang speller, ito ay nagpapahiwatig na ito ay opsyonal 336 00:28:55,200 --> 00:29:00,950 para sa kanila upang pumasa sa isang diksyunaryo file dahil mayroong isang default na diksyunaryo file. 337 00:29:00,950 --> 00:29:05,410 At pagkatapos ay mayroon silang upang pumasa sa teksto ng spell-check. 338 00:29:05,410 --> 00:29:11,410 deal rusage sa oras dahil isang bahagi ng ito pset na magpapadala kami makitungo sa ibang pagkakataon 339 00:29:11,410 --> 00:29:14,790 ay hindi lamang sa pagkuha ng isang nagtatrabaho ng paggana ng spell-checker 340 00:29:14,790 --> 00:29:17,190 pero sa totoo ay pagkuha ng ito upang maging mabilis. 341 00:29:17,190 --> 00:29:22,040 At kaya pagkatapos na kung saan rusage ay pagpunta sa darating. 342 00:29:22,040 --> 00:29:28,740 Dito, tingnan namin ang unang tawag sa isa sa aming mga dictionary.c file, na ng pagkarga. 343 00:29:28,740 --> 00:29:34,720 Ng pag-load nagbabalik true o false - totoo sa tagumpay, maling kapag pagkabigo. 344 00:29:34,720 --> 00:29:41,400 Kaya kung diksyunaryo ay hindi na-load nang maayos, pagkatapos speller.c ay magbabalik 1 at mag-quit. 345 00:29:41,400 --> 00:29:47,920 Ngunit kung ito ng pagkarga maayos, pagkatapos ito upang magpatuloy. 346 00:29:47,920 --> 00:29:50,740 Patuloy namin, at nakita namin ang ilang file I / O dito, 347 00:29:50,740 --> 00:29:56,210 kung saan ito ay pagpunta sa pagharap sa pagbubukas ng text file. 348 00:29:56,210 --> 00:30:04,640 Dito, kung ano ang ginagawa ng spell-nagsusuri ang bawat solong salita sa teksto. 349 00:30:04,640 --> 00:30:09,270 Kaya kung ano ang speller.c ay ginagawa dito mismo iterating sa paglipas ng bawat isa sa ang mga salita sa text file 350 00:30:09,270 --> 00:30:12,790 at pagkatapos ay check ito sa diksyunaryo. 351 00:30:24,680 --> 00:30:32,350 Dito, mayroon kaming isang Boolean maling nabaybay na makita kung check nagbabalik totoo o hindi. 352 00:30:32,350 --> 00:30:37,110 Kung ang salita ay aktwal na sa diksyunaryo, pagkatapos ay i-check ang nagbabalik ng tunay na. 353 00:30:37,110 --> 00:30:39,760 Iyon ay nangangahulugang ang salitang iyon ay hindi tamang spelling. 354 00:30:39,760 --> 00:30:45,330 Kaya maling nabaybay ay maling, at na ang dahilan kung bakit mayroon kaming doon ang putok, ang pahiwatig. 355 00:30:45,330 --> 00:30:56,320 Panatilihin namin sa pagpunta, at pagkatapos ay iniingatan nito ang track kung gaano karaming mga maling nabaybay salita 356 00:30:56,320 --> 00:30:58,910 may sa file. 357 00:30:58,910 --> 00:31:03,870 Patuloy ito sa at isinasara ang file. 358 00:31:03,870 --> 00:31:09,250 Pagkatapos dito, nag-uulat ito kung gaano karaming mga maling nabaybay salita na mayroon kang. 359 00:31:09,250 --> 00:31:12,680 Kinakalkula kung gaano karaming oras na ito kinuha load ang diksyunaryo, 360 00:31:12,680 --> 00:31:15,080 kung gaano karaming oras na ito kinuha upang suriin ito, 361 00:31:15,080 --> 00:31:18,510 kung gaano karaming oras na ito kinuha upang makalkula ang laki, 362 00:31:18,510 --> 00:31:21,260 kung saan, bilang ipagpapatuloy namin, dapat ay napakaliit, 363 00:31:21,260 --> 00:31:25,390 at pagkatapos ay kung gaano karaming oras na ito kinuha upang tanggalin sa diksyunaryo. 364 00:31:25,390 --> 00:31:27,700 Dito hanggang sa itaas nakita namin ang tawag sa mag-ibis maglapag dito. 365 00:31:27,700 --> 00:31:52,690 Kung namin suriin para sa laki dito, 366 00:31:52,690 --> 00:31:59,050 pagkatapos naming makita na dito ang tawag sa laki kung saan tumutukoy sa laki ng diksyunaryo. 367 00:32:05,730 --> 00:32:07,100 Kahanga-hanga. 368 00:32:07,100 --> 00:32:10,920 >> Aming gawain para sa pset ipatupad load, na-load ang diksyunaryo 369 00:32:10,920 --> 00:32:15,480 data istraktura - alinman mong piliin, na ito ng hash table o subukan - 370 00:32:15,480 --> 00:32:18,810 may mga salita mula sa diksyunaryo file. 371 00:32:18,810 --> 00:32:25,290 Pagkatapos mayroon kang laki, na ibalik ang bilang ng mga salita sa diksyunaryo. 372 00:32:25,290 --> 00:32:29,860 At kung ikaw ipatupad ng load sa isang smart paraan, pagkatapos laki ay dapat na medyo madali. 373 00:32:29,860 --> 00:32:33,860 Pagkatapos mo na check, na suriin kung ang isang ibinigay na salita sa diksyunaryo. 374 00:32:33,860 --> 00:32:38,690 Kaya speller.c pass sa isang string, at pagkatapos ay mayroon kang upang suriin kung na string 375 00:32:38,690 --> 00:32:41,610 ay nilalaman sa loob ng iyong diksyunaryo. 376 00:32:41,610 --> 00:32:46,750 Pansinin na namin pangkalahatang standard na mga diksyunaryo, 377 00:32:46,750 --> 00:32:53,020 ngunit sa ang pset na ito, isa lamang diksyunaryo anumang ang pumasa sa sa anumang wika. 378 00:32:53,020 --> 00:32:57,040 Kaya hindi lang namin ipinapalagay na ang salitang ANG ay sa loob. 379 00:32:57,040 --> 00:33:03,090 Ang salitang FOOBAR maaaring tinukoy sa isang tiyak na diksyunaryo na pumasa kami. 380 00:33:03,090 --> 00:33:07,920 At pagkatapos namin mag-ibis maglapag, na frees sa diksyunaryo mula sa memorya. 381 00:33:07,920 --> 00:33:11,930 >> Una, gusto kong pumunta sa ibabaw ng hash paraan ng talahanayan 382 00:33:11,930 --> 00:33:14,630 tungkol sa kung paano namin ipatupad ang lahat ng mga apat na function, 383 00:33:14,630 --> 00:33:18,650 at pagkatapos ay kukunin ko na pumunta sa ibabaw ng sinusubukan paraan ng, kung paano namin ipatupad ang mga apat na function, 384 00:33:18,650 --> 00:33:22,720 at sa dulo talk tungkol sa ilang pangkalahatang mga tip kapag nagsasagawa ka sa pset 385 00:33:22,720 --> 00:33:27,870 at din kung paano mo magagamit ang Valgrind mag-check para sa mga paglabas ng memorya. 386 00:33:27,870 --> 00:33:30,550 >> Makakuha natin sa hash paraan ng talahanayan. 387 00:33:30,550 --> 00:33:35,910 Isang hash na talahanayan ay binubuo ng isang listahan ng mga bucket. 388 00:33:35,910 --> 00:33:43,010 Bawat halaga, bawat salita, ay pagpunta sa pumunta sa isa sa mga bucket. 389 00:33:43,010 --> 00:33:53,200 Isang hash talahanayan perpektong pantay-pantay namamahagi ng lahat ng mga halagang ito na kayo ay pagpasa sa 390 00:33:53,200 --> 00:33:57,160 at pagkatapos populates ito sa bucket na bawat bucket 391 00:33:57,160 --> 00:34:02,000 may tungkol sa isang patas na bilang ng mga halaga sa loob nito. 392 00:34:02,000 --> 00:34:09,630 Ang istraktura para sa isang hash table, mayroon kaming isang array ng mga naka-link na listahan. 393 00:34:09,630 --> 00:34:17,900 Ano ang ginagawa namin kapag pumasa kami sa isang halaga, namin suriin kung saan ang halaga na dapat nabibilang, 394 00:34:17,900 --> 00:34:23,840 kung saan bucket ito ay kabilang sa, at pagkatapos ay ilagay ito sa naka-link na listahan na nauugnay sa na bucket. 395 00:34:23,840 --> 00:34:28,199 Dito, kung ano ang mayroon akong ay isang hash. 396 00:34:28,199 --> 00:34:31,320 Ang isang int hash talahanayan. 397 00:34:31,320 --> 00:34:38,540 Kaya para sa unang bucket, anumang integer sa ibaba 10 ay pumunta sa unang bucket. 398 00:34:38,540 --> 00:34:42,190 Anumang integer sa itaas 10 ngunit sa ibaba 20 go sa segundo, 399 00:34:42,190 --> 00:34:44,179 at pagkatapos ay iba pa at iba pa. 400 00:34:44,179 --> 00:34:52,370 Para sa akin, ang bawat bucket ay kumakatawan sa mga numerong ito. 401 00:34:52,370 --> 00:34:59,850 Gayunpaman, sinasabi ko upang pumasa sa 50, halimbawa. 402 00:34:59,850 --> 00:35:07,490 Lumilitaw na kung ang unang tatlong naglalaman ng isang hanay ng mga sampung numero. 403 00:35:07,490 --> 00:35:12,570 Ngunit nais ko upang payagan ang aking hash table upang tumagal sa anumang uri ng integer, 404 00:35:12,570 --> 00:35:19,860 kaya Gusto ko upang i-filter ang lahat ng mga numero sa itaas 30 sa huling bucket. 405 00:35:19,860 --> 00:35:26,660 At kaya pagkatapos na maaaring magresulta sa isang uri ng hindi balanseng hash talahanayan. 406 00:35:31,330 --> 00:35:35,640 Upang mag-ulit, ng hash table ay lamang ng isang hanay ng mga bucket 407 00:35:35,640 --> 00:35:38,590 kung saan ang bawat bucket ay isang naka-link na listahan. 408 00:35:38,590 --> 00:35:43,730 At iba pa upang matukoy kung saan napupunta ang bawat halaga, kung saan bucket ito napupunta sa, 409 00:35:43,730 --> 00:35:46,260 ka pagpunta sa nais kung ano ang tinatawag na hash 410 00:35:46,260 --> 00:35:55,010 na tumatagal ng isang halaga at pagkatapos ay sabi ni Ang halagang ito ay tumutugma sa isang tiyak na bucket. 411 00:35:55,010 --> 00:36:00,970 Kaya sa itaas hanggang sa halimbawang ito, ang aking hash kinuha bawat halaga. 412 00:36:00,970 --> 00:36:03,020 Ito ay naka-check kung ito ay mas mababa sa 10. 413 00:36:03,020 --> 00:36:05,360 Kung ito ay, ilagay ang mga ito sa unang bucket. 414 00:36:05,360 --> 00:36:08,910 Sumusuri kung ito ay mas mababa sa 20, Binibigyan ito sa ang pangalawang kung totoo, 415 00:36:08,910 --> 00:36:12,880 tseke kung ito ay mas mababa sa 30, at pagkatapos ay Binibigyan ito sa sa ikatlong bucket, 416 00:36:12,880 --> 00:36:16,990 at pagkatapos ang lahat ng ibang tao na Nabibilang ang ang ika-apat na bucket. 417 00:36:16,990 --> 00:36:20,110 Kaya kapag mayroon kang isang halaga, ang iyong mga hash 418 00:36:20,110 --> 00:36:25,420 maglalagay na halaga sa naaangkop na bucket. 419 00:36:25,420 --> 00:36:32,430 Ang hash talaga kailangang malaman kung gaano karaming mga bucket mayroon kang. 420 00:36:32,430 --> 00:36:37,960 Iyong hash laki ng talahanayan, ang bilang ng mga bucket na mayroon ka, 421 00:36:37,960 --> 00:36:41,190 na pagpunta sa isang nakapirming numero na ay nasa sa iyo, para sa iyo upang magpasya, 422 00:36:41,190 --> 00:36:43,590 ngunit ito ay pagpunta sa isang nakapirming numero. 423 00:36:43,590 --> 00:36:51,840 Kaya iyong hash ay umasa sa na upang matukoy kung saan bucket key tuwing pupunta sa 424 00:36:51,840 --> 00:36:54,450 tulad na pantay-pantay ito ay ibinahagi sa. 425 00:36:56,150 --> 00:37:03,820 Katulad sa aming pagpapatupad ng mga naka-link na listahan, ngayon ang bawat node sa hash table 426 00:37:03,820 --> 00:37:07,000 ay aktwal na pagpunta sa magkaroon ng isang uri ng pansamantalang trabaho. 427 00:37:07,000 --> 00:37:14,340 Kaya mayroon kaming magpasinda array na tinatawag na salita at pagkatapos ng isa pang pointer sa susunod na node, 428 00:37:14,340 --> 00:37:19,010 na saysay dahil ito pagpunta sa isang naka-link na listahan. 429 00:37:19,010 --> 00:37:24,350 Tandaan kapag kami ay naka-link listahan, ginawa ko ang isang node * na tinatawag na ulo 430 00:37:24,350 --> 00:37:31,060 na nagtuturo sa unang node sa naka-link na listahan. 431 00:37:31,060 --> 00:37:34,020 Ngunit para sa aming hash talahanayan, dahil mayroon kaming maraming naka-link listahan, 432 00:37:34,020 --> 00:37:37,520 kung ano ang gusto namin ay gusto naming ang aming hash table upang maging tulad ng, "Ano ang isang bucket?" 433 00:37:37,520 --> 00:37:43,340 Bucket ay isang listahan ng mga node payo, 434 00:37:43,340 --> 00:37:50,620 at sa gayon ang bawat elemento sa bucket ay aktwal na nagtuturo sa kaukulang naka-link na listahan. 435 00:37:56,180 --> 00:38:01,520 Upang bumalik sa eskematiko, makikita mo na ang bucket mismo ang mga arrow, 436 00:38:01,520 --> 00:38:06,980 hindi aktwal na node. 437 00:38:11,680 --> 00:38:16,420 Isa mahahalagang ari-arian ng hash function ay na hindi sila deterministic. 438 00:38:16,420 --> 00:38:19,440 Iyon ay nangangahulugan na tuwing nag-hash ang bilang 2, 439 00:38:19,440 --> 00:38:22,270 dapat itong palaging bumalik sa parehong bucket. 440 00:38:22,270 --> 00:38:26,440 Bawat solong halaga na napupunta sa hash, kung paulit-ulit, 441 00:38:26,440 --> 00:38:29,690 ay may upang makuha ang parehong index. 442 00:38:29,690 --> 00:38:34,210 Kaya ang iyong hash nagbabalik ang index ng array 443 00:38:34,210 --> 00:38:38,530 kung saan ang halaga na nabibilang. 444 00:38:38,530 --> 00:38:41,790 Tulad ng aking nabanggit bago, ang numero ng mga bucket ay maayos, 445 00:38:41,790 --> 00:38:49,630 at sa gayon ang iyong index na bumalik ka na mas mababa kaysa sa numero ng mga bucket 446 00:38:49,630 --> 00:38:52,680 ngunit mas malaki kaysa sa 0. 447 00:38:52,680 --> 00:39:00,780 Ang dahilan kung bakit mayroon kaming hash function sa halip na isa lamang sa iisang naka-link na listahan 448 00:39:00,780 --> 00:39:09,290 o isang single array ay na gusto naming upang lumipat sa isang tiyak na seksyon pinaka madaling 449 00:39:09,290 --> 00:39:11,720 kung alam namin ang mga katangian ng isang halaga - 450 00:39:11,720 --> 00:39:14,760 sa halip ng pagkakaroon upang maghanap sa pamamagitan ng buong buong diksyunaryo, 451 00:39:14,760 --> 00:39:18,320 upang lumipat sa isang tiyak na seksyon ng. 452 00:39:19,880 --> 00:39:24,440 Iyong hash ay dapat isinasaalang-alang na may perpektong, 453 00:39:24,440 --> 00:39:28,980 bucket ang bawat isa ay humigit-kumulang ang parehong bilang ng mga susi. 454 00:39:28,980 --> 00:39:35,040 Dahil ang hash talahanayan ay isang serye ng mga naka-link na listahan, 455 00:39:35,040 --> 00:39:38,480 pagkatapos ang mga naka-link na listahan ang kanilang mga sarili upang magkaroon ng higit sa isang node. 456 00:39:38,480 --> 00:39:43,210 Sa nakaraang halimbawa, ang dalawang magkaibang mga numero, kahit na sila ay hindi katumbas, 457 00:39:43,210 --> 00:39:46,950 kapag hash, ay ibalik ang parehong index. 458 00:39:46,950 --> 00:39:53,620 Kaya kapag ikaw ay pagharap sa mga salita, isang salita kapag hash 459 00:39:53,620 --> 00:39:57,450 ay ang parehong halaga ng hash ng isa pang salita. 460 00:39:57,450 --> 00:40:04,140 Iyon ay kung ano ang tinatawag naming isang banggaan, kapag mayroon kaming isang node na, kapag hash, 461 00:40:04,140 --> 00:40:09,610 ang naka-link na listahan sa bucket na ay hindi walang laman. 462 00:40:09,610 --> 00:40:14,180 Ang diskarteng na tinatawag naming may linear probing, 463 00:40:14,180 --> 00:40:22,550 kung saan ka pumunta sa naka-link na listahan at pagkatapos ay hanapin kung saan mo gustong ipasok na node 464 00:40:22,550 --> 00:40:25,520 dahil mayroon kang isang banggaan. 465 00:40:25,520 --> 00:40:28,070 Maaari mong makita na may maaaring ng trade-off dito, i-right? 466 00:40:28,070 --> 00:40:33,760 Kung mayroon kang isang napakaliit na hash table, isang maliit na bilang ng mga bucket, 467 00:40:33,760 --> 00:40:36,380 ka pagpunta sa magkaroon ng maraming mga banggaan. 468 00:40:36,380 --> 00:40:40,460 Ngunit pagkatapos ay kung gumawa ka ng isang napakalaking hash talahanayan, 469 00:40:40,460 --> 00:40:44,110 marahil ka upang i-minimize ang mga banggaan, 470 00:40:44,110 --> 00:40:47,170 ngunit ito ay pagpunta sa isang napakalaking istraktura ng data. 471 00:40:47,170 --> 00:40:49,310 May pagpunta sa kalakalan-offs na iyon. 472 00:40:49,310 --> 00:40:51,310 Kaya kapag nagsasagawa ka ng iyong pset, subukan upang i-play sa paligid 473 00:40:51,310 --> 00:40:54,210 sa pagitan ng maaaring paggawa ng isang mas maliit na hash talahanayan 474 00:40:54,210 --> 00:41:02,100 ngunit pagkatapos ay alam na ito bit na pagbagtas sa iba't ibang mga elemento 475 00:41:02,100 --> 00:41:04,270 ng mga naka-link na listahan. 476 00:41:04,270 --> 00:41:09,500 >> Ano ng pagkarga ay pagpunta sa gawin ay umulit sa paglipas ng bawat salita sa diksyunaryo. 477 00:41:09,500 --> 00:41:13,180 Pass sa isang pointer sa file ng diksyunaryo. 478 00:41:13,180 --> 00:41:18,050 Kaya ka pagpunta sa samantalahin ng file I / O function na pinagkadalubhasaan mo sa pset4 479 00:41:18,050 --> 00:41:23,010 at umulit sa paglipas ng bawat salita sa diksyunaryo. 480 00:41:23,010 --> 00:41:26,620 Gusto mong bawat salita sa diksyunaryo upang maging isang bagong node, 481 00:41:26,620 --> 00:41:32,730 at ikaw ay pagpunta sa ilagay ang bawat isa sa mga node sa loob ng iyong istraktura ng data ng diksyunaryo. 482 00:41:32,730 --> 00:41:36,560 Sa tuwing makakakuha ka ng isang bagong salita, alam mo na ito ay pagpunta sa maging isang node. 483 00:41:36,560 --> 00:41:46,590 Sa gayon ay maaari kang pumunta kagayat at malloc isang node pointer para sa bawat bagong salita na mayroon kang. 484 00:41:46,590 --> 00:41:52,610 Narito ako pagtawag sa aking node pointer new_node at ako mallocing kung ano? Ang laki ng isang node. 485 00:41:52,610 --> 00:41:59,190 Pagkatapos basahin ang aktwal na string mula sa isang file, dahil ang diksyunaryo ay aktwal na naka-imbak 486 00:41:59,190 --> 00:42:03,340 sa pamamagitan ng isang salita at pagkatapos ng isang bagong linya, kung ano ang maaari naming samantalahin 487 00:42:03,340 --> 00:42:06,520 ay-andar ng fscanf, 488 00:42:06,520 --> 00:42:10,280 kung saan ang file ay sa diksyunaryo file na kami ay nakapasa sa, 489 00:42:10,280 --> 00:42:18,900 kaya scan ng kahera ang file para sa isang string at mga lugar na string sa huling argumento. 490 00:42:18,900 --> 00:42:26,890 Kung manariwa sa diwa mo sa isa sa mga aralin, kapag nagpunta kami sa paglipas ng 491 00:42:26,890 --> 00:42:29,320 at uri ng peeled ang mga layer sa library CS50, 492 00:42:29,320 --> 00:42:33,430 nakita natin ang isang pagpapatupad ng fscanf doon. 493 00:42:33,430 --> 00:42:37,700 Upang bumalik sa fscanf, mayroon kaming ang file na kami ay binabasa mula sa, 494 00:42:37,700 --> 00:42:42,570 kaming naghahanap para sa isang string sa file na iyon, at pagkatapos ay namin ang paglalagay nito sa 495 00:42:42,570 --> 00:42:48,340 dito mayroon akong new_node-> salita dahil new_node ay isang node pointer, 496 00:42:48,340 --> 00:42:50,380 hindi isang aktwal na node. 497 00:42:50,380 --> 00:42:57,100 Kaya ako sinasabi new_node, gusto kong pumunta sa node na ito na tumuturo sa 498 00:42:57,100 --> 00:43:01,190 at pagkatapos ay italaga na halaga sa salita. 499 00:43:01,190 --> 00:43:08,540 Gusto naming pagkatapos na salita at ipasok ito sa hash table. 500 00:43:08,540 --> 00:43:13,750 Napagtanto na aming ginawa new_node node pointer 501 00:43:13,750 --> 00:43:18,230 dahil kami ay pagpunta sa gusto mong malaman kung ano ang address ng node na 502 00:43:18,230 --> 00:43:23,940 kapag namin ipasok ito sa dahil ang istraktura ng node mismo, ng struct, 503 00:43:23,940 --> 00:43:26,380 na mayroon silang isang pointer sa isang bagong node. 504 00:43:26,380 --> 00:43:30,820 Kaya pagkatapos ay kung ano ang address ng na node pagpunta upang tumuro sa? 505 00:43:30,820 --> 00:43:34,550 Address na iyon ay pagpunta sa new_node. 506 00:43:34,550 --> 00:43:42,140 Ba na may kabuluhan, bakit ginagawa namin new_node node * bilang laban sa isang node? 507 00:43:43,700 --> 00:43:45,700 Okay. 508 00:43:45,700 --> 00:43:52,840 Mayroon kaming isang salita. Ang halaga na iyon ay new_node-> salita. 509 00:43:52,840 --> 00:43:55,970 Na naglalaman ng salita mula sa diksyunaryo na gusto naming input. 510 00:43:55,970 --> 00:44:00,210 Kaya kung ano ang gusto naming gawin ay gusto naming tawagan ang aming hash na string 511 00:44:00,210 --> 00:44:03,780 dahil ang aming hash tumatagal sa isang string at pagkatapos ay bumalik sa amin ng isang integer, 512 00:44:03,780 --> 00:44:12,090 kung saan ang integer na ang index kung saan hashtable sa index na kumakatawan na bucket. 513 00:44:12,090 --> 00:44:18,260 Gusto naming na-index at pagkatapos ay pumunta na index ng hash table 514 00:44:18,260 --> 00:44:26,960 at pagkatapos ay gamitin na nag-link na listahan upang ipasok ang node sa new_node. 515 00:44:26,960 --> 00:44:31,950 Tandaan na gayunpaman magpasya sa iyo upang ipasok ang iyong node, 516 00:44:31,950 --> 00:44:34,370 maging ito man ay sa gitna kung nais mong upang pag-uri-uriin ang mga ito 517 00:44:34,370 --> 00:44:39,650 o sa simula o sa katapusan, tiyakin lamang na ang iyong huling node laging punto upang null 518 00:44:39,650 --> 00:44:46,730 dahil iyon ang tanging paraan na alam namin kung saan ang huling elemento ng aming mga listahan ng naka-link. 519 00:44:50,790 --> 00:44:59,710 >> Kung ang laki ay isang integer na kumakatawan sa bilang ng mga salita sa diksyunaryo, 520 00:44:59,710 --> 00:45:03,060 pagkatapos ay isang paraan upang gawin ito ay tuwing laki ay tinatawag na 521 00:45:03,060 --> 00:45:05,840 pumunta kami sa pamamagitan ng bawat elemento sa aming hash talahanayan 522 00:45:05,840 --> 00:45:09,410 at pagkatapos ay umulit sa pamamagitan ng bawat naka-link na listahan sa loob ng hash table 523 00:45:09,410 --> 00:45:13,770 at pagkatapos ay kalkulahin ang haba ng na, pagtaas ng aming counter 1 ng 1. 524 00:45:13,770 --> 00:45:16,580 Ngunit sa bawat oras na ang laki ay tinatawag na, na pagpunta sa isang mahabang panahon 525 00:45:16,580 --> 00:45:22,120 dahil kami ay pagpunta sa linearly probing ang bawat solong-link listahan. 526 00:45:22,120 --> 00:45:30,530 Sa halip, ito ng maraming mas madali kung patuloy mong pagsubaybay ng kung gaano karaming mga salita ay lumipas. 527 00:45:30,530 --> 00:45:36,330 Kaya pagkatapos kung isinama mo ang isang counter sa loob ng iyong ng pagkarga function na 528 00:45:36,330 --> 00:45:42,430 na update kung kinakailangan, pagkatapos ay counter, kung itinakda mo ito sa isang global variable, 529 00:45:42,430 --> 00:45:44,930 ay magagawang ma-access sa pamamagitan ng laki. 530 00:45:44,930 --> 00:45:51,450 Kaya kung ano ang laki ay maaaring lamang gawin ay sa isang linya, ibalik ang counter halaga, 531 00:45:51,450 --> 00:45:55,500 ang laki ng diksyunaryo, kung saan ikaw ay Aaksyunan sa ng pagkarga. 532 00:45:55,500 --> 00:46:05,190 Na kung ano ang ko nilalayong kapag sinabi ko kung ipatupad mo ng load sa isang kapaki-pakinabang na paraan, 533 00:46:05,190 --> 00:46:08,540 pagkatapos ay ang laki ay medyo madali. 534 00:46:08,540 --> 00:46:11,350 >> Kaya ngayon namin upang suriin. 535 00:46:11,350 --> 00:46:15,960 Ngayon kami ay pagharap sa mga salita mula sa file ng input ng teksto, 536 00:46:15,960 --> 00:46:19,910 at sa gayon kami ay pagpunta sa ma-check kung ang lahat ng mga salita ng input 537 00:46:19,910 --> 00:46:22,520 ay talagang sa diksyunaryo o hindi. 538 00:46:22,520 --> 00:46:26,520 Katulad sa mang-uayabit, gusto naming upang payagan para sa kawalan ng damdamin ng kaso. 539 00:46:26,520 --> 00:46:32,110 Nais mong tiyakin na ang lahat ng salita nakapasa sa, kahit na nasa magkahalong case, 540 00:46:32,110 --> 00:46:37,840 kapag tinawag gamit ang string Ihambing ang, katumbas. 541 00:46:37,840 --> 00:46:42,450 Ang mga salita sa file ng teksto ng diksyunaryo ay talagang lahat ng maliit na. 542 00:46:42,450 --> 00:46:49,280 Isa pang bagay ay na maaari mong ipagpalagay na ang bawat salita nakapasa sa, bawat string, 543 00:46:49,280 --> 00:46:53,200 pagpunta sa alinman sa alpabetikong o naglalaman apostrophes. 544 00:46:53,200 --> 00:46:58,010 Apostrophes wastong salita sa aming diksyunaryo. 545 00:46:58,010 --> 00:47:06,470 Kaya kung mayroon kang isang salita na may kudlit S, na isang aktwal na lehitimong salita sa iyong diksyunaryo 546 00:47:06,470 --> 00:47:11,650 na pagpunta sa isa sa mga node sa iyong hash talahanayan. 547 00:47:13,470 --> 00:47:18,350 Suriin ay nagpapatakbo ng kung umiiral ang salita, pagkatapos ito ay nakuha sa aming hash talahanayan. 548 00:47:18,350 --> 00:47:22,210 Kung ang salita sa diksyunaryo, pagkatapos ang lahat ng mga salita sa diksyunaryo sa hash table, 549 00:47:22,210 --> 00:47:26,560 kaya tingnan natin para sa salita sa hash table. 550 00:47:26,560 --> 00:47:29,250 Alam namin na mula noong ipinatupad namin ang aming hash 551 00:47:29,250 --> 00:47:38,420 tulad ang bawat natatanging salita ay palaging hash sa parehong halaga, 552 00:47:38,420 --> 00:47:43,340 pagkatapos ay alam namin na sa halip ng paghahanap sa pamamagitan ng aming buong buong hash talahanayan, 553 00:47:43,340 --> 00:47:48,310 maaari naming aktwal na mahanap ang naka-link na listahan na salita na dapat kabilang sa. 554 00:47:48,310 --> 00:47:51,850 Kung ito ay sa diksyunaryo, pagkatapos ay sa bucket na. 555 00:47:51,850 --> 00:47:57,140 Ano ang maaari naming gawin, kung ang salita ay ang pangalan ng aming mga string na nakapasa sa, 556 00:47:57,140 --> 00:48:01,560 maaari lang namin hash na ang salita at hitsura sa naka-link na listahan 557 00:48:01,560 --> 00:48:06,410 sa ang halaga ng hashtable [hash (salita)]. 558 00:48:06,410 --> 00:48:12,410 Mula doon, kung ano ang maaari naming gawin ay kami ay may isang mas maliit na subset ng mga node upang maghanap para sa salita, 559 00:48:12,410 --> 00:48:16,770 at sa gayon ay maaari naming pagbagtas sa naka-link na listahan, gamit ang isang halimbawa mula sa mas maaga sa walkthrough, 560 00:48:16,770 --> 00:48:24,110 at pagkatapos ay tumawag ng string ihambing sa mga salita saanman ang cursor ay tumuturo sa, 561 00:48:24,110 --> 00:48:28,430 na salita, at makita kung ang mga ihambing. 562 00:48:30,280 --> 00:48:35,110 Depende sa paraan na kang ayusin ang iyong hash, 563 00:48:35,110 --> 00:48:39,260 kung ito ay pinagsunod-sunod, na maaaring magawa upang bumalik maling maaga nang kaunti, 564 00:48:39,260 --> 00:48:43,440 ngunit kung ito ay unsorted, pagkatapos ay nais mong magpatuloy traversing sa pamamagitan ng iyong listahan ng naka-link 565 00:48:43,440 --> 00:48:46,480 hanggang sa mahanap mo ang huling elemento ng listahan. 566 00:48:46,480 --> 00:48:53,320 At kung hindi mo pa rin natagpuan ang salita ng oras na naabot mo na ang dulo ng naka-link na listahan, 567 00:48:53,320 --> 00:48:56,890 na nangangahulugan na ang iyong salita ay hindi umiiral sa diksyunaryo, 568 00:48:56,890 --> 00:48:59,410 at kaya ang salita na ay hindi wasto, 569 00:48:59,410 --> 00:49:02,730 at check dapat bumalik false. 570 00:49:02,730 --> 00:49:09,530 >> Ngayon dumating namin upang mag-ibis maglapag, kung saan nais namin upang magbakante ang lahat ng node na namin malloc'd, 571 00:49:09,530 --> 00:49:14,050 kaya libreng lahat ng node sa loob ng aming hash talahanayan. 572 00:49:14,050 --> 00:49:20,270 Kami ay pagpunta sa nais upang umulit sa lahat ng naka-link na listahan at libreng lahat ng node sa na. 573 00:49:20,270 --> 00:49:29,350 Kung tumingin ka sa itaas sa walkthrough sa halimbawa kung saan magbakante kami ng isang naka-link na listahan, 574 00:49:29,350 --> 00:49:35,140 gugustuhin mong ulitin ang prosesong iyon para sa bawat elemento sa hash table. 575 00:49:35,140 --> 00:49:37,780 At makikita ko pumunta sa paglipas ng ito patungo sa dulo ng walkthrough, 576 00:49:37,780 --> 00:49:46,600 ngunit Valgrind ay isang tool na kung saan maaari mong makita kung maayos mo na napalaya 577 00:49:46,600 --> 00:49:53,600 bawat node na iyong malloc'd o anumang bagay na iyong malloc'd, anumang iba pang pointer. 578 00:49:55,140 --> 00:50:00,530 Kaya na ang hash table, kung saan mayroon kaming isang tiyak na numero ng mga bucket 579 00:50:00,530 --> 00:50:09,220 at ng hash na halaga at pagkatapos ay italaga na halaga sa isang tiyak na bucket. 580 00:50:09,220 --> 00:50:13,340 >> Na namin ngayon sa mga pagsusubok na. 581 00:50:13,340 --> 00:50:18,750 Sinusubukan ng uri ng hitsura tulad nito, at ko rin gumuhit ang isang halimbawa. 582 00:50:18,750 --> 00:50:25,630 Talaga, mayroon kang isang buong array ng mga potensyal na mga titik, 583 00:50:25,630 --> 00:50:29,210 at pagkatapos ay tuwing ka bumuo ng isang salita, 584 00:50:29,210 --> 00:50:36,490 sulat na naka-link para sa isang diksyunaryo sa isang malawak na hanay ng mga posibilidad. 585 00:50:36,490 --> 00:50:40,840 Simulan ang ilan sa mga salita sa C ngunit pagkatapos ay magpatuloy sa A, 586 00:50:40,840 --> 00:50:42,960 ngunit iba patuloy sa O, halimbawa. 587 00:50:42,960 --> 00:50:51,090 Trie ay isang paraan ng pagtingin ng lahat ng posibleng mga kumbinasyon ng mga salitang iyon. 588 00:50:51,090 --> 00:50:59,070 Trie ay upang masubaybayan ang pagkakasunud-sunod ng mga titik na bumubuo ng mga salita, 589 00:50:59,070 --> 00:51:08,280 sumasanga off kapag kinakailangan, kapag ang isang titik ay maaaring sinundan sa pamamagitan ng maramihang mga ng mga titik, 590 00:51:08,280 --> 00:51:16,630 at sa dulo ay nagpapahiwatig sa bawat punto kung wasto o hindi ang salita na 591 00:51:16,630 --> 00:51:30,120 dahil kung ikaw ay pagbaybay ng salita Mat, MA palagay ko ay hindi isang wastong salita, ngunit Mat ay. 592 00:51:30,120 --> 00:51:37,820 At iba pa sa iyong trie, ito ay magdudulot ng magpahiwatig na pagkatapos Mat na talagang isang wastong salita. 593 00:51:41,790 --> 00:51:48,590 Ang bawat node sa aming trie talagang pagpunta upang maglaman ng isang hanay ng mga node payo, 594 00:51:48,590 --> 00:51:52,970 at kami ay pagpunta sa may, partikular, 27 ng mga node na payo, 595 00:51:52,970 --> 00:52:00,550 isa para sa bawat titik sa alpabeto pati na rin ang mga kudlit character. 596 00:52:00,550 --> 00:52:10,450 Bawat elemento sa array na mismo upang ituro sa ibang node. 597 00:52:10,450 --> 00:52:14,020 Kaya kung ang node na ay null, kung may walang matapos iyon, 598 00:52:14,020 --> 00:52:20,550 alam namin na walang karagdagang titik sa na pagkakasunud-sunod ng salita. 599 00:52:20,550 --> 00:52:26,950 Ngunit kung ang node na ay hindi null, na nangangahulugan na may higit pang mga titik sa na pagkakasunud-sunod ng titik. 600 00:52:26,950 --> 00:52:32,160 At pagkatapos ay tangi sa roon, ang bawat node ay nagpapahiwatig ito man ang huling character ng isang salita o hindi. 601 00:52:38,110 --> 00:52:43,170 >> Natin pumunta sa isang halimbawa ng isang trie. 602 00:52:50,500 --> 00:52:58,340 Una mayroon akong room para sa 27 node sa array. 603 00:52:58,340 --> 00:53:03,200 Kung mayroon ko ang salitang Bar - 604 00:53:13,310 --> 00:53:15,370 Kung mayroon ko ang salitang bar at gusto ko upang ipasok na sa, 605 00:53:15,370 --> 00:53:22,700 ang unang titik ay B, kaya kung walang laman ang aking trie ay, 606 00:53:22,700 --> 00:53:29,910 B ay ang ikalawang titik ng alpabeto, kaya ako pagpunta upang piliin upang ilagay ito dito sa index na ito. 607 00:53:29,910 --> 00:53:33,450 Ako pagpunta sa may B dito. 608 00:53:33,450 --> 00:53:42,400 B ay pagpunta sa isang node na mga punto sa isa pang hanay ng lahat ng posibleng mga character 609 00:53:42,400 --> 00:53:45,870 na maaaring sundin pagkatapos ng sulat ng B. 610 00:53:45,870 --> 00:53:57,610 Sa kasong ito, ako pagharap sa bar ng salita, kaya ay pupunta dito. 611 00:54:02,000 --> 00:54:08,990 Pagkatapos A, mayroon akong ang sulat R, kaya pagkatapos ngayon puntos sa sarili nitong kumbinasyon, 612 00:54:08,990 --> 00:54:15,120 at pagkatapos R ay dito. 613 00:54:15,120 --> 00:54:22,470 Bar ay isang kumpletong salita, kaya pagkatapos ako na magkaroon ng ng R punto sa isa pang node 614 00:54:22,470 --> 00:54:33,990 na sinasabi na ang salitang iyon ay wastong. 615 00:54:36,010 --> 00:54:40,970 Na node ay din pagpunta sa magkaroon ng isang hanay ng mga node, 616 00:54:40,970 --> 00:54:45,260 ngunit ang mga maaaring maging null. 617 00:54:45,260 --> 00:54:49,080 Ngunit isa lamang, maaari itong magpatuloy tulad na. 618 00:54:49,080 --> 00:54:54,250 Iyon ay magiging isang bit mas malinaw kapag pumunta kami sa isang iba't ibang mga halimbawa, 619 00:54:54,250 --> 00:54:56,780 kaya lang makisama sa akin doon. 620 00:54:56,780 --> 00:55:02,050 Ngayon kami ay may bar sa loob ng aming diksyunaryo. 621 00:55:02,050 --> 00:55:05,980 Ngayon sinasabi namin ang salitang BAZ. 622 00:55:05,980 --> 00:55:12,630 Sisimulan namin sa B, at kami ay mayroon B bilang isa sa mga titik na sa aming diksyunaryo. 623 00:55:12,630 --> 00:55:15,170 Na sinusundan may A. Mayroon kaming A na. 624 00:55:15,170 --> 00:55:19,250 Ngunit sa halip, mayroon kaming Z sumusunod. 625 00:55:19,250 --> 00:55:25,490 Kaya ang isang elemento sa aming array ay pagpunta sa Z, 626 00:55:25,490 --> 00:55:30,810 at kaya pagkatapos na ang isa ay upang tumuro sa isa pang wastong dulo ng salita. 627 00:55:30,810 --> 00:55:36,930 Kaya nakita namin na kapag patuloy naming sa pamamagitan ng B at pagkatapos A, 628 00:55:36,930 --> 00:55:43,480 mayroong dalawang iba't ibang mga pagpipilian na kasalukuyang nasa aming diksyunaryo para sa mga salita na nagsisimula sa B at A. 629 00:55:49,650 --> 00:55:57,460 Sabihin nating gusto naming ipasok ang salita FOOBAR. 630 00:55:57,460 --> 00:56:05,620 Pagkatapos naming gumawa ng isang entry sa F. 631 00:56:05,620 --> 00:56:11,320 F ay isang node na mga punto sa isang buong array. 632 00:56:11,320 --> 00:56:22,790 Gusto namin mahanap ang O, pumunta sa O, O pagkatapos ay naka-link sa isang buong listahan. 633 00:56:22,790 --> 00:56:35,340 Gusto namin magkaroon ng B at pagkatapos ay magpatuloy, nais naming magkaroon ng A at pagkatapos R. 634 00:56:35,340 --> 00:56:43,570 Kaya pagkatapos FOOBAR traverses ang lahat ng mga paraan pababa hanggang FOOBAR ay isang tamang salita. 635 00:56:43,570 --> 00:56:52,590 At kaya pagkatapos na ito ay isang wastong salita. 636 00:56:52,590 --> 00:57:00,170 Ngayon sinasabi aming susunod na salita sa diksyunaryo ay talagang ang salitang FOO. 637 00:57:00,170 --> 00:57:03,530 Gusto namin sabihin F. Ano sumusunod F? 638 00:57:03,530 --> 00:57:06,190 Ako aktwal na magkaroon ng espasyo para sa O, kaya ako pagpunta upang magpatuloy. 639 00:57:06,190 --> 00:57:09,150 Hindi ko kailangan upang gumawa ng bagong. Magpatuloy. 640 00:57:09,150 --> 00:57:15,500 FOO isang wastong salita sa diksyunaryo, kaya ako pagpunta upang isaad 641 00:57:15,500 --> 00:57:21,660 na na wasto. 642 00:57:21,660 --> 00:57:28,370 Kung ko bang itigil ang aking pagkakasunud-sunod doon, na tama. 643 00:57:28,370 --> 00:57:33,050 Ngunit kung patuloy namin ang aming pagkakasunud-sunod mula FOO down sa B 644 00:57:33,050 --> 00:57:39,750 at nagkaroon FOOB, FOOB ay hindi isang salita, at hindi na ipinahiwatig bilang isang balidong. 645 00:57:47,370 --> 00:57:57,600 Trie, na iyong node bawat nagpapahiwatig kung ito ay isang wastong salita o hindi, 646 00:57:57,600 --> 00:58:05,840 at pagkatapos node bawat ay mayroon ding isang array ng 27 na node payo 647 00:58:05,840 --> 00:58:09,520 na pagkatapos ay tumuturo sa node kanilang sarili. 648 00:58:09,520 --> 00:58:12,940 >> Narito ang isang paraan kung paano mo nais na tukuyin ito. 649 00:58:12,940 --> 00:58:17,260 Gayunpaman, tulad sa hash Halimbawa ng talahanayan, kung saan nagkaroon kami ng node ulo * 650 00:58:17,260 --> 00:58:21,320 upang ipahiwatig ang simula ng aming mga listahan ng naka-link, din kami ay pagpunta sa gusto 651 00:58:21,320 --> 00:58:29,150 ilang mga paraan ng pag-alam kung saan ang simula ng aming trie. 652 00:58:29,150 --> 00:58:34,110 Ang ilang mga tao tawag ay sinusubukan ng mga puno, at na kung saan ugat ay mula. 653 00:58:34,110 --> 00:58:36,910 Kaya gusto namin ang root ng aming puno upang matiyak na manatili namin grawnded 654 00:58:36,910 --> 00:58:39,570 saanman ay ang aming trie. 655 00:58:42,910 --> 00:58:46,300 Namin na uri ng nagpunta sa paglipas ng 656 00:58:46,300 --> 00:58:50,240 ang paraan maaari mong isipin ang tungkol sa paglo-load ng bawat salita sa diksyunaryo. 657 00:58:50,240 --> 00:58:54,540 Mahalaga, para sa bawat salita ka pagpunta sa nais upang umulit sa pamamagitan ng iyong trie 658 00:58:54,540 --> 00:58:59,590 at alam na ang bawat elemento sa mga bata - tinatawag namin itong bata sa kasong ito - 659 00:58:59,590 --> 00:59:04,290 tumutugon sa ibang sulat, ikaw ay pagpunta sa gusto mong tingnan ang mga halagang iyon 660 00:59:04,290 --> 00:59:08,320 sa partikular na index na tumutugma sa sulat. 661 00:59:08,320 --> 00:59:11,260 Kaya iniisip ang lahat ng mga paraan pabalik sa Caesar at Vigenere, 662 00:59:11,260 --> 00:59:16,070 alam na ang bawat titik na maaari mong uri ng mapa sa isang alpabetikong index, 663 00:59:16,070 --> 00:59:20,690 talagang A sa pamamagitan ng Z ay medyo madali upang i-map sa isang alpabetikong sulat, 664 00:59:20,690 --> 00:59:25,200 ngunit sa kasamaang palad, apostrophes din ang isang tanggap na character sa mga salita. 665 00:59:25,200 --> 00:59:31,650 Hindi ako kahit sigurado kung ano ang ASCII halaga ay, 666 00:59:31,650 --> 00:59:39,250 ito para sa kung gusto mong mahanap ang isang index upang magpasya kung nais mong ito sa alinman ang unang 667 00:59:39,250 --> 00:59:44,550 o ang huling isa, makikita mo upang gumawa ng isang hard code na tseke para sa 668 00:59:44,550 --> 00:59:48,930 at pagkatapos ay ilagay na sa index 26, halimbawa. 669 00:59:48,930 --> 00:59:55,300 Kaya ikaw ay check ang halaga sa mga bata [i] 670 00:59:55,300 --> 00:59:58,400 kung saan ang [i] ay tumutugon sa anumang sulat ikaw ay nasa. 671 00:59:58,400 --> 01:00:04,110 Kung na null, na nangangahulugan na may kasalukuyang hindi anumang posibleng mga titik 672 01:00:04,110 --> 01:00:08,150 stemming mula sa nakaraang sequence, kaya ka pagpunta sa gusto sa malloc 673 01:00:08,150 --> 01:00:13,150 at gumawa ng isang bagong node at na ang mga bata [i] tumuturo dito 674 01:00:13,150 --> 01:00:17,890 sa gayon ay lumikha ka ng - kapag ipinasok namin ng sulat sa parihaba - 675 01:00:17,890 --> 01:00:23,680 paggawa ng mga bata na di-null at punto sa node na bagong. 676 01:00:23,680 --> 01:00:28,340 Ngunit kung iyon ay hindi null, gusto sa aming halimbawa ng FOO 677 01:00:28,340 --> 01:00:34,570 kapag namin na nagkaroon FOOBAR, patuloy namin, 678 01:00:34,570 --> 01:00:44,010 at hindi namin kailanman paggawa ng isang bagong node ngunit lamang sa halip ng pagtatakda ng is_word sa true 679 01:00:44,010 --> 01:00:47,790 sa dulo ng salitang iyon. 680 01:00:50,060 --> 01:00:55,340 >> Kaya pagkatapos tulad ng dati, dahil dito ka pagharap sa bawat titik sa isang pagkakataon, 681 01:00:55,340 --> 01:01:01,470 ito upang maging mas madali para sa iyo para sa laki, sa halip ng pagkakaroon upang makalkula 682 01:01:01,470 --> 01:01:06,910 at pumunta sa pamamagitan ng buong puno at kalkulahin kung gaano karaming mga bata ay mayroon akong 683 01:01:06,910 --> 01:01:10,850 at pagkatapos ay sumasanga off, na-alala kung gaano karaming sa kaliwang bahagi at sa kanang bahagi 684 01:01:10,850 --> 01:01:12,850 at mga bagay tulad na, ito ng maraming mas madali para sa iyo 685 01:01:12,850 --> 01:01:16,220 kung ikaw subaybayan kung gaano karaming mga salita nagdaragdag ka sa 686 01:01:16,220 --> 01:01:18,080 kapag ikaw ay pagharap sa ng pagkarga. 687 01:01:18,080 --> 01:01:22,630 At kaya pagkatapos na paraan laki lang ibalik isang pandaigdigang variable ng laki. 688 01:01:25,320 --> 01:01:28,530 >> Ngayon dumating namin upang suriin. 689 01:01:28,530 --> 01:01:33,920 Parehong mga pamantayan tulad ng dati, kung saan nais namin upang payagan para sa kawalan ng damdamin ng kaso. 690 01:01:33,920 --> 01:01:40,400 Pati na rin, ipinapalagay namin na ang mga string lamang alpabetikong character o ang mga apostrophes 691 01:01:40,400 --> 01:01:44,000 dahil ang bata ay isang hanay ng mga 27 ang haba, 692 01:01:44,000 --> 01:01:48,480 sa gayon ang lahat ng mga titik ng alpabeto kasama ang kudlit. 693 01:01:48,480 --> 01:01:53,800 Para tingnan kung ano ang gusto mong gawin ay makikita mo nais na magsimula sa root 694 01:01:53,800 --> 01:01:58,440 dahil ang root ng magtuturo sa isang array na naglalaman 695 01:01:58,440 --> 01:02:01,630 lahat ng mga posibleng nagsisimula sa mga titik ng isang salita. 696 01:02:01,630 --> 01:02:03,680 Ka pagpunta upang simulan doon, 697 01:02:03,680 --> 01:02:11,590 at pagkatapos ka upang suriin ang halaga null o hindi, 698 01:02:11,590 --> 01:02:16,490 dahil kung ang halaga ay null, na nangangahulugan na diksyunaryo ay hindi magkaroon ng anumang mga halaga 699 01:02:16,490 --> 01:02:21,480 na naglalaman na titik sa partikular na pagkakasunud-sunod. 700 01:02:21,480 --> 01:02:24,970 Kung ito ay null, pagkatapos na nangangahulugan na ang salita ay maling kaagad. 701 01:02:24,970 --> 01:02:27,110 Ngunit kung ito ay hindi null, maaari kang magpatuloy, 702 01:02:27,110 --> 01:02:34,090 sabihin na ang unang titik ay isang posibleng unang letra sa isang salita, 703 01:02:34,090 --> 01:02:40,630 kaya ngayon gusto ko upang suriin kung ang pangalawang sulat, na pagkakasunud-sunod, sa loob ng aking diksyunaryo. 704 01:02:40,630 --> 01:02:46,540 Kaya ka pumunta sa index ng mga bata ng unang node 705 01:02:46,540 --> 01:02:50,720 at suriin kung umiiral na pangalawang sulat. 706 01:02:50,720 --> 01:02:57,440 Pagkatapos mong ulitin na proseso upang suriin kung ang pagkakasunod-sunod na ay wasto o hindi 707 01:02:57,440 --> 01:02:59,060 sa loob ng iyong trie. 708 01:02:59,060 --> 01:03:06,430 Tuwing ang node bata sa na puntos ng index sa null, 709 01:03:06,430 --> 01:03:10,710 alam mo na ang pagkakasunod-sunod na hindi umiiral, 710 01:03:10,710 --> 01:03:16,230 ngunit pagkatapos kung naabot mo na ang dulo ng mga salita na iyong inputted, 711 01:03:16,230 --> 01:03:20,070 gusto mong mag-check ngayon Nakumpleto ko na ang pagkakasunod-sunod na ito 712 01:03:20,070 --> 01:03:27,610 at natagpuan ito sa loob ng aking trie, ang salitang iyon wasto o hindi? 713 01:03:27,610 --> 01:03:32,480 At kaya pagkatapos na nais mong upang suriin na, at na kapag kung natagpuan na pagkakasunod-sunod, 714 01:03:32,480 --> 01:03:35,120 nais mong upang suriin kung wasto o hindi ang salita na 715 01:03:35,120 --> 01:03:40,290 dahil tandaan bumalik sa nakaraang kaso na iginuhit ko kung saan nagkaroon kami FOOB, 716 01:03:40,290 --> 01:03:48,410 na isang wastong pagkakasunud-sunod na nakita namin ngunit ay hindi isang aktwal na wastong salita mismo. 717 01:03:50,570 --> 01:03:59,000 >> Gayundin, para sa mga mag-ibis maglapag sa pagsusubok na gusto mong mag-ibis maglapag ang lahat ng node sa iyong trie. 718 01:03:59,000 --> 01:04:04,790 Sorry. Katulad sa ang hash na mga talahanayan kung saan sa mag-ibis maglapag namin napalaya ang lahat ng mga node, 719 01:04:04,790 --> 01:04:09,740 sa pagsusubok na gusto naming din magbakante lahat ng node. 720 01:04:09,740 --> 01:04:15,000 Mag-ibis maglapag ang talagang gumagana ang pinakamadaling mula sa ibaba sa itaas 721 01:04:15,000 --> 01:04:19,290 dahil ito ay mahalagang-link listahan. 722 01:04:19,290 --> 01:04:22,540 Kaya gusto namin upang matiyak na hawakan namin sa lahat ng mga halaga 723 01:04:22,540 --> 01:04:25,700 at libreng lahat ng mga ito tahasang. 724 01:04:25,700 --> 01:04:28,840 Kung ano ang iyong pagpunta sa nais na gawin kung nagtatrabaho ka na may trie 725 01:04:28,840 --> 01:04:35,640 maglakbay sa ibaba at libre ang posibleng pinakamababang node unang 726 01:04:35,640 --> 01:04:39,190 at pagkatapos ay pumunta sa lahat ng mga bata at pagkatapos ay libre sa lahat ng mga, 727 01:04:39,190 --> 01:04:43,050 pumunta up at pagkatapos ay libre, atbp. 728 01:04:43,050 --> 01:04:48,790 Uri ng tulad ng pagharap sa ibabang layer ng trie unang 729 01:04:48,790 --> 01:04:51,940 at pagkatapos ay pagpunta up itaas sa sandaling napalaya ang lahat. 730 01:04:51,940 --> 01:04:56,720 Ito ay isang mahusay na halimbawa ng kung saan ang recursive function na ay maaaring dumating sa madaling-gamiting. 731 01:04:56,720 --> 01:05:03,830 Sa sandaling na-napalaya ang layer sa ilalim ng iyong trie, 732 01:05:03,830 --> 01:05:08,000 pagkatapos ay tumawag kang tanggalin sa natitirang, 733 01:05:08,000 --> 01:05:13,620 bang na magbakante bawat mini - 734 01:05:13,620 --> 01:05:16,410 Maaari mong uri ng maisalarawan ito bilang mini sinusubukan ng. 735 01:05:23,300 --> 01:05:28,990 Kaya iyong root dito. 736 01:05:30,840 --> 01:05:35,230 Ako Pinasisimple ito kaya hindi ko upang gumuhit ng 26 sa kanila. 737 01:05:37,250 --> 01:05:43,770 Kaya mayroon kang mga ito, at pagkatapos ay ito kumakatawan pagkakasunud-sunod ng mga salita 738 01:05:43,770 --> 01:05:54,620 kung saan ang lahat ng mga maliit na lupon ang mga titik na wastong pagkakasunud-sunod ng mga titik. 739 01:06:03,040 --> 01:06:07,160 Natin magpatuloy lamang ng kaunti pang. 740 01:06:15,110 --> 01:06:25,750 Kung ano ang iyong pagpunta sa nais na gawin ang libreng ibaba dito at pagkatapos ay libre ang isang ito 741 01:06:25,750 --> 01:06:31,640 at pagkatapos libreng ito isa sa ibaba bago magbakante sa tuktok hanggang dito 742 01:06:31,640 --> 01:06:38,180 dahil kung ikaw ay libreng isang bagay sa ikalawang antas dito, 743 01:06:38,180 --> 01:06:47,230 iyong aktwal na mawala ang halagang ito dito. 744 01:06:47,230 --> 01:06:54,780 Iyon ang dahilan kung bakit ito ay mahalaga sa mag-ibis maglapag para sa isang trie upang matiyak na magbakante mo sa ibaba sa unang. 745 01:06:54,780 --> 01:06:59,480 Ano ang maaari mong nais na gawin ay sabihin para sa bawat node 746 01:06:59,480 --> 01:07:06,430 Gusto kong mag-ibis maglapag ang lahat ng mga bata. 747 01:07:16,060 --> 01:07:22,140 >> Ngayon na kami nawala sa mag-ibis maglapag para sa hash paraan ng talahanayan pati na rin ang trie paraan ng, 748 01:07:22,140 --> 01:07:27,020 kami ay pagpunta sa gusto upang tumingin sa Valgrind. 749 01:07:27,020 --> 01:07:29,640 Valgrind mong tumakbo gamit ang mga sumusunod na utos. 750 01:07:29,640 --> 01:07:32,700 Mayroon kang valgrind-v. 751 01:07:32,700 --> 01:07:40,960 Sinusuri para sa lahat ng paglabas kapag nagpatakbo ka speller na ibinigay na ang ilang teksto na ito 752 01:07:40,960 --> 01:07:46,980 dahil speller ay kailangang gawin sa isang text file. 753 01:07:46,980 --> 01:07:52,330 Kaya Valgrind tatakbo iyong programa, sabihin sa iyo kung gaano karaming mga byte inilaan mo, 754 01:07:52,330 --> 01:07:57,150 kung gaano karaming mga byte napalaya mo, at ito ay magsasabi sa iyo kung napalaya mo lang sapat na 755 01:07:57,150 --> 01:07:58,930 o kung hindi libreng sapat, 756 01:07:58,930 --> 01:08:02,850 o minsan kahit over-free, tulad ng libreng isang node na na-napalaya 757 01:08:02,850 --> 01:08:05,140 at sa gayon ito ay bumalik ka ng mga error. 758 01:08:05,140 --> 01:08:11,600 Kung gumagamit ka ng Valgrind, ito ay magbibigay sa iyo ng ilang mga mensahe 759 01:08:11,600 --> 01:08:15,970 nagpapahiwatig kung napalaya mo ang alinman sa mas mababa kaysa sa sapat, lang sapat, 760 01:08:15,970 --> 01:08:19,609 o higit pa kaysa sa sapat na beses. 761 01:08:24,370 --> 01:08:30,410 >> Isang bahagi ng ito pset, opsyonal hamunin ang Big Board. 762 01:08:30,410 --> 01:08:35,790 Ngunit kapag kami ay pagharap sa mga istraktura ng data na ito 763 01:08:35,790 --> 01:08:40,689 uri ng masaya upang makita kung gaano kabilis at kung paano mahusay na ang iyong data ng istraktura ay maaaring. 764 01:08:40,689 --> 01:08:44,490 Gumagana ba ang iyong hash resulta sa maraming ng banggaan? 765 01:08:44,490 --> 01:08:46,300 O ang iyong data sa laki talagang malaking? 766 01:08:46,300 --> 01:08:49,420 Aabutin ng maraming oras pagbagtas? 767 01:08:49,420 --> 01:08:54,800 Sa log ng speller, output kung gaano karaming oras na gamitin mo upang i-load, 768 01:08:54,800 --> 01:08:57,700 upang suriin, upang magsagawa ng laki, at mag-ibis maglapag, 769 01:08:57,700 --> 01:09:00,720 at kaya ang mga ay nai-post sa Ang Big Board, 770 01:09:00,720 --> 01:09:03,600 kung saan maaari kang makipagkumpetensya laban sa iyong mga kaklase 771 01:09:03,600 --> 01:09:11,350 at ilang mga miyembro ng kawani upang makita kung sino ay ang pinakamabilis na spell-checker. 772 01:09:11,350 --> 01:09:14,760 Ang isang bagay na Gusto ko upang tandaan tungkol sa hash na mga talahanayan 773 01:09:14,760 --> 01:09:20,470 na mayroong ilang mga medyo simpleng hash function na maaaring sa tingin namin ng. 774 01:09:20,470 --> 01:09:27,240 Halimbawa, mayroon kang 26 bucket, at kaya bawat bucket 775 01:09:27,240 --> 01:09:30,200 tumutugon sa ang unang titik sa isang salita, 776 01:09:30,200 --> 01:09:35,229 ngunit na magresulta sa medyo hindi balanseng hash talahanayan 777 01:09:35,229 --> 01:09:40,979 dahil may mga ng maraming ng mas kaunting mga salita na nagsisimula sa X kaysa sa panimula sa M, halimbawa. 778 01:09:40,979 --> 01:09:47,890 Ang isang paraan upang pumunta tungkol sa speller kung nais mong makakuha ng lahat ng iba pang mga pag-andar pababa, 779 01:09:47,890 --> 01:09:53,240 pagkatapos lamang gamitin ang isang simpleng hash upang makuha ang iyong code sa pagtakbo 780 01:09:53,240 --> 01:09:58,650 at pagkatapos ay bumalik at baguhin ang laki ng iyong hash table at ang kahulugan. 781 01:09:58,650 --> 01:10:03,430 May ng maraming mga mapagkukunan sa Internet para sa hash function, 782 01:10:03,430 --> 01:10:08,250 at ito para sa pset ka pinapayagang upang saliksikin ang mga hash function sa Internet 783 01:10:08,250 --> 01:10:15,560 para sa ilang mga pahiwatig at inspirasyon hangga't gumawa ka bang banggitin kung saan mo nakuha ito mula sa. 784 01:10:15,560 --> 01:10:22,060 Maaari kang upang tingnan at bigyang-kahulugan ang ilang hash na mahanap ka sa Internet. 785 01:10:22,060 --> 01:10:27,460 Bumalik sa na, maaari mong upang makita kung may isang taong gumamit ng isang trie 786 01:10:27,460 --> 01:10:31,700 kung ang kanilang pagpapatupad ay mas mabilis kaysa sa iyong hash talahanayan o hindi. 787 01:10:31,700 --> 01:10:35,290 Maaari kang magsumite sa Ang Big Board maraming beses. 788 01:10:35,290 --> 01:10:37,660 Ito ay record ang iyong pinaka-kamakailang mga entry. 789 01:10:37,660 --> 01:10:44,300 Kaya maaaring mong baguhin ang iyong hash at pagkatapos ay mapagtanto na ito ay talagang ng maraming mas mabilis 790 01:10:44,300 --> 01:10:46,780 o ng maraming mas mabagal kaysa dati. 791 01:10:46,780 --> 01:10:50,960 Na ang isang bit ng isang paraan ng masaya. 792 01:10:50,960 --> 01:10:57,190 Mayroon laging 1 o 2 mga miyembro ng kawani na subukan ang pinakamabagal na posibleng diksyunaryo, 793 01:10:57,190 --> 01:11:00,210 kaya na palaging masaya upang tumingin sa. 794 01:11:00,210 --> 01:11:07,630 >> Ang paggamit para sa pset kang magpatakbo ng speller sa isang opsyonal na diksyunaryo 795 01:11:07,630 --> 01:11:12,840 at pagkatapos ng ipinag-uutos na file ng teksto. 796 01:11:12,840 --> 01:11:18,380 Sa pamamagitan ng default kapag nagpatakbo ka speller sa pamamagitan lamang ng isang text file at hindi tukuyin ang isang diksyunaryo, 797 01:11:18,380 --> 01:11:24,410 ito upang gamitin ang diksyunaryo file ng teksto, malaking 798 01:11:24,410 --> 01:11:27,920 sa folder ng mga cs50/pset5/dictionaries. 799 01:11:27,920 --> 01:11:32,760 Na may higit sa 100,000 salita. 800 01:11:32,760 --> 01:11:37,950 Mayroon ding isang maliit na diksyunaryo na lubha mas salita 801 01:11:37,950 --> 01:11:40,730 na CS50 ay ginawa para sa iyo. 802 01:11:40,730 --> 01:11:44,050 Gayunpaman, maaari mong napaka madaling lang gawin ang iyong sariling diksyunaryo 803 01:11:44,050 --> 01:11:47,150 kung gusto mo lang na nagtatrabaho sa mga maliliit na mga halimbawa - 804 01:11:47,150 --> 01:11:51,140 halimbawa, kung nais mong gamitin ang gdb at alam mo ang tiyak na halaga 805 01:11:51,140 --> 01:11:53,560 na nais mo ang iyong hash talahanayan upang i-map sa. 806 01:11:53,560 --> 01:12:00,430 Kaya lamang ka maaaring gumawa ng iyong sariling text file na may bar, BAZ, FOO, at FOOBAR, 807 01:12:00,430 --> 01:12:04,860 gumawa na sa isang file ng teksto, paghiwalayin ang mga bawat isa ay may 1 linya, 808 01:12:04,860 --> 01:12:12,670 at pagkatapos ay gawin ang iyong sariling teksto file na literal ay naglalaman lamang ng mga siguro 1 o 2 salita 809 01:12:12,670 --> 01:12:15,950 kaya na alam mo kung ano mismo ang output dapat. 810 01:12:15,950 --> 01:12:21,870 Ang ilan sa ang mga file ng halimbawang teksto na Ang Big Board na kapag nagpatakbo ka ng hamon ay suriin 811 01:12:21,870 --> 01:12:25,580 Digmaan at Kapayapaan at isang nobelang ng Jane Austen o isang bagay tulad na. 812 01:12:25,580 --> 01:12:30,450 Kaya kapag ikaw ay nagsisimula out, ito ng maraming mas madali upang gumawa ng iyong sariling mga file ng teksto 813 01:12:30,450 --> 01:12:34,160 na naglalaman lamang ng ilang mga salita o maaaring 10 814 01:12:34,160 --> 01:12:38,280 sa gayon ay maaari mong hulaan kung ano ang kalalabasan ay dapat na 815 01:12:38,280 --> 01:12:42,880 at pagkatapos ay suriin ito kumpara na, kaya higit pa ng isang kinokontrol na halimbawa. 816 01:12:42,880 --> 01:12:45,820 At kaya dahil kami ay pagharap sa predicting at pagguhit ng mga bagay sa paligid, 817 01:12:45,820 --> 01:12:48,690 muli gusto ko hinihikayat ka upang gamitin ang pen at papel 818 01:12:48,690 --> 01:12:50,700 dahil talagang ito ay pagpunta upang makatulong sa iyo sa isang ito - 819 01:12:50,700 --> 01:12:55,620 pagguhit ang mga arrow, kung paano ang hash table o kung paano ang iyong trie mukhang, 820 01:12:55,620 --> 01:12:57,980 kapag ikaw ay pagbabakante ng isang bagay na kung saan ang mga arrow ay pumunta sa, 821 01:12:57,980 --> 01:13:01,730 mo na may hawak na sa sapat, huwag mong makita ang anumang mga link mawala 822 01:13:01,730 --> 01:13:05,750 at bumabagsak sa kailaliman ng leaked memory. 823 01:13:05,750 --> 01:13:11,070 Kaya mangyaring, mangyaring subukan upang gumuhit ng mga bagay kahit bago makakuha ng sa iyo sa pagsulat ng code pababa. 824 01:13:11,070 --> 01:13:14,520 Gumuhit ng mga bagay na ang upang maunawaan mo kung paano ang mga bagay ay pagpunta sa trabaho 825 01:13:14,520 --> 01:13:22,750 dahil pagkatapos ko magagarantiya makikita mo tumakbo sa mas muddles pointer doon. 826 01:13:24,270 --> 01:13:25,910 >> Ayos lang. 827 01:13:25,910 --> 01:13:28,780 Gusto kong nais mong ang pinakamahusay na ng luck sa ito pset. 828 01:13:28,780 --> 01:13:31,980 Ito ay marahil ang hardest isa. 829 01:13:31,980 --> 01:13:40,360 Kaya subukang agahan, gumuhit ng mga bagay ang, gumuhit ng mga bagay ang, at good luck. 830 01:13:40,360 --> 01:13:42,980 Ito walkthrough 5. 831 01:13:45,160 --> 01:13:47,000 >> [CS50.TV]