1 00:00:00,000 --> 00:00:00,500 2 00:00:00,500 --> 00:00:05,120 [Musika sa pag-play] 3 00:00:05,120 --> 00:00:12,026 4 00:00:12,026 --> 00:00:12,900 Tagapagsalita 1: Ang lahat ng karapatan. 5 00:00:12,900 --> 00:00:14,600 Ang bawat tao'y maligayang pagdating pabalik sa seksyon. 6 00:00:14,600 --> 00:00:18,660 Umaasa ako mo ang lahat ng mga matagumpay na nakuhang muli galing sa iyong pagsusulit 7 00:00:18,660 --> 00:00:19,510 mula noong nakaraang linggo. 8 00:00:19,510 --> 00:00:22,564 Alam ko ito nang kaunti mabaliw minsan. 9 00:00:22,564 --> 00:00:25,230 Tulad ng sinasabi ko dati, kung ikaw ay sa loob ng karaniwang lihis, 10 00:00:25,230 --> 00:00:28,188 hindi talaga mag-alala tungkol dito, lalo na para sa isang mas kumportable na seksyon. 11 00:00:28,188 --> 00:00:30,230 Iyon ang tungkol sa kung saan mo na dapat. 12 00:00:30,230 --> 00:00:32,850 >> Kung ginawa mo mahusay, pagkatapos ay kahanga-hanga. 13 00:00:32,850 --> 00:00:33,650 Paggalang sa iyo. 14 00:00:33,650 --> 00:00:36,149 At kung sa palagay mo bang kailangan mo Medyo sa karagdagang tulong, mangyaring 15 00:00:36,149 --> 00:00:38,140 huwag mag-atubiling makipag-ugnay out sa alinman sa mga TFs. 16 00:00:38,140 --> 00:00:40,030 Kami lahat dito upang makatulong. 17 00:00:40,030 --> 00:00:40,960 >> Iyon ang dahilan kung bakit namin magturo. 18 00:00:40,960 --> 00:00:44,550 Iyon ang dahilan kung bakit ako dito tuwing Lunes para sa iyo guys at sa tanggapan ng oras sa Huwebes. 19 00:00:44,550 --> 00:00:48,130 Kaya mangyaring huwag mag-atubiling ipaalam sa akin kung ikaw ay nag-aalala tungkol sa anumang bagay 20 00:00:48,130 --> 00:00:52,450 o kung mayroong anumang bagay sa pagsusulit na nais mo ba talagang i-matugunan. 21 00:00:52,450 --> 00:00:56,940 >> Kaya ang agenda para sa araw ay ang lahat tungkol sa mga istraktura ng data. 22 00:00:56,940 --> 00:01:01,520 Ang ilan sa mga ito ay lamang ng pagpunta sa maging lamang upang makakuha ka familiarized sa mga ito. 23 00:01:01,520 --> 00:01:04,870 Maaari mong hindi kailanman ipatupad ang mga ito sa klase na ito. 24 00:01:04,870 --> 00:01:08,690 Ang ilan sa kanila habilin sa iyo, tulad ng para sa iyong speller pset. 25 00:01:08,690 --> 00:01:11,380 >> Magkakaroon ka ng iyong mga pagpipilian sa pagitan ng hash table at pagsubok. 26 00:01:11,380 --> 00:01:13,680 Kaya makikita talagang kami ay pagpunta sa ibabaw ng mga iyon. 27 00:01:13,680 --> 00:01:18,690 Ito ay magiging talagang higit pa sa mga uri ng isang mataas na antas ng seksyon ngayon, bagaman, 28 00:01:18,690 --> 00:01:22,630 dahil mayroong maraming mga ito, at kung nagpunta kami sa mga detalye ng pagpapatupad 29 00:01:22,630 --> 00:01:26,490 sa lahat ng mga ito, kami ng gagawin hindi kahit na makakuha sa pamamagitan ng naka-link na mga listahan 30 00:01:26,490 --> 00:01:28,520 at marahil ng kaunting hash talahanayan. 31 00:01:28,520 --> 00:01:31,200 >> Kaya makisama sa akin. 32 00:01:31,200 --> 00:01:33,530 Hindi namin pagpunta sa ginagawa ng maraming coding oras na ito. 33 00:01:33,530 --> 00:01:36,870 Kung mayroon kang anumang mga katanungan tungkol dito o gusto mong makita ito ipinatupad 34 00:01:36,870 --> 00:01:39,260 o subukan ito sa iyong sarili, Ako siguradong inirerekumenda 35 00:01:39,260 --> 00:01:44,250 pagpunta sa study.cs50.net, na May mga halimbawa ng lahat ng mga ito. 36 00:01:44,250 --> 00:01:46,400 Magkakaroon ito ng aking PowerPoints sa mga tala na aming 37 00:01:46,400 --> 00:01:50,860 ay may posibilidad na gamitin pati na rin ang ilang mga programming pagsasanay, lalo na para sa mga bagay 38 00:01:50,860 --> 00:01:55,250 tulad ng naka-link na mga listahan at binary puno stack at mga pahiwatig. 39 00:01:55,250 --> 00:01:59,590 Kaya kaunti pa mataas na antas, na Maaaring maging maganda para sa iyo guys. 40 00:01:59,590 --> 00:02:01,320 >> Kaya sa na, magpapadala kami makapagsimula. 41 00:02:01,320 --> 00:02:03,060 At din, yes-- pagsusulit. 42 00:02:03,060 --> 00:02:06,550 Sa tingin ko ang karamihan sa iyo kung sino ang nasa ang aking mga seksyon ng iyong mga maikling pagsusulit, 43 00:02:06,550 --> 00:02:12,060 ngunit sinuman ay sa o sa ilang mga dahilan kung bakit mo hindi, ang mga ito ay dito mismo sa harap. 44 00:02:12,060 --> 00:02:12,740 >> Kaya naka-link na mga listahan. 45 00:02:12,740 --> 00:02:15,650 Alam ko ang uri na ito ng pupunta upang i-back bago ang iyong pagsusulit. 46 00:02:15,650 --> 00:02:17,940 Iyon ay ang linggo bago na natutunan namin tungkol dito. 47 00:02:17,940 --> 00:02:21,040 Ngunit sa kasong ito, kami ay lamang pumunta Medyo mas malalalim na. 48 00:02:21,040 --> 00:02:25,900 >> Kaya bakit maaari naming pumili ng isang listahan na naka-link sa isang array? 49 00:02:25,900 --> 00:02:27,130 Ano Tinutukoy ang mga ito? 50 00:02:27,130 --> 00:02:27,630 Oo? 51 00:02:27,630 --> 00:02:30,464 >> Madla: Maaari mong palawakin ang isang naka-link ilista kumpara sa nakapirming laki ng array na. 52 00:02:30,464 --> 00:02:31,171 Tagapagsalita 1: I-right. 53 00:02:31,171 --> 00:02:33,970 Isang array ay naayos na laki samantalang ang isang naka-link na listahan ay may laki na variable. 54 00:02:33,970 --> 00:02:36,970 Kaya kung hindi namin alam kung paano magkano ang gusto namin upang mag-imbak, 55 00:02:36,970 --> 00:02:39,880 naka-link na listahan ay nagbibigay sa amin ng mahusay na paraan upang gawin iyon dahil kami maaari lamang 56 00:02:39,880 --> 00:02:43,730 idagdag sa isa pang node at idagdag sa isa pang node at idagdag sa isa pang node. 57 00:02:43,730 --> 00:02:45,750 Ngunit kung ano ang maaaring maging isang kalakalan-off? 58 00:02:45,750 --> 00:02:49,521 Tandaan ang sinuman sa trade-off sa pagitan ng array at naka-link listahan? 59 00:02:49,521 --> 00:02:50,020 Mmhmm? 60 00:02:50,020 --> 00:02:51,460 >> Madla: Mayroon kang sa pumunta sa lahat ng mga paraan 61 00:02:51,460 --> 00:02:53,738 sa pamamagitan ng naka-link na listahan makahanap ng isang elemento sa isang listahan. 62 00:02:53,738 --> 00:02:55,570 Sa isang array, maaari mong hanapin lamang ang isang elemento. 63 00:02:55,570 --> 00:02:56,278 >> Tagapagsalita 1: I-right. 64 00:02:56,278 --> 00:02:57,120 Kaya sa arrays-- 65 00:02:57,120 --> 00:02:58,500 >> Madla: [hindi marinig]. 66 00:02:58,500 --> 00:03:01,090 >> Tagapagsalita 1: Sa array, mayroon kaming kung ano ang tinatawag na random na pag-access. 67 00:03:01,090 --> 00:03:04,820 Nangangahulugan itong kung gusto namin kung ano ang kailanman ikalimang punto ng isang listahan 68 00:03:04,820 --> 00:03:07,230 o ang ika-limang puntos sa aming mga array, maaari naming grab lamang ito. 69 00:03:07,230 --> 00:03:10,440 Kung ito ay isang naka-link na listahan, mayroon kaming upang umulit sa pamamagitan ng, tama? 70 00:03:10,440 --> 00:03:14,020 Kaya pag-access sa isang elemento sa isang array ay pare-pareho ang oras, 71 00:03:14,020 --> 00:03:19,530 samantalang may naka-link na listahan ng gagawin ito pinaka-malamang na maging linear oras dahil siguro 72 00:03:19,530 --> 00:03:21,370 ang aming elemento ay ang lahat ng mga paraan sa dulo. 73 00:03:21,370 --> 00:03:23,446 Mayroon kaming upang maghanap sa lahat ng bagay. 74 00:03:23,446 --> 00:03:25,320 Kaya sa lahat ng mga data na ito kaayusan kami ng pagpunta 75 00:03:25,320 --> 00:03:29,330 na paggastos ng konting oras sa, ano ang mga plus at negatibo. 76 00:03:29,330 --> 00:03:31,480 Kapag Maaaring gusto naming gamitin ang isa sa ibabaw ng iba pang? 77 00:03:31,480 --> 00:03:34,970 At iyon ang uri ng mas malaking bagay na kumuha ang layo. 78 00:03:34,970 --> 00:03:40,140 >> Kaya mayroon kaming dito ang kahulugan ng isang node. 79 00:03:40,140 --> 00:03:43,040 Ito ay tulad ng isang elemento sa ang aming listahan na naka-link, i-right? 80 00:03:43,040 --> 00:03:46,180 Kaya kami ay lahat ng mga pamilyar sa aming typedef structs, 81 00:03:46,180 --> 00:03:47,980 kung saan nagpunta kami sa paglipas ng pagsusuri sa huling beses. 82 00:03:47,980 --> 00:03:53,180 Ito ay isa lamang lamang paglikha isa pang uri ng data na maaaring naming gamitin. 83 00:03:53,180 --> 00:03:57,930 >> At sa kasong ito, ito ang ilang node iyon ay hawak ng ilang integer in. 84 00:03:57,930 --> 00:04:00,210 At pagkatapos ay kung ano ang ikalawang bahagi dito? 85 00:04:00,210 --> 00:04:03,192 86 00:04:03,192 --> 00:04:05,677 Sinuman? 87 00:04:05,677 --> 00:04:06,680 >> Madla: [hindi marinig]. 88 00:04:06,680 --> 00:04:07,020 >> Tagapagsalita 1: Oo. 89 00:04:07,020 --> 00:04:08,400 Ito ay isang pointer sa susunod na node. 90 00:04:08,400 --> 00:04:12,610 Kaya ito ay dapat na tunay na maging up dito. 91 00:04:12,610 --> 00:04:18,790 Ito ay isang pointer ng uri node sa susunod na bagay. 92 00:04:18,790 --> 00:04:22,410 At iyon ang kung ano ang kanilang sumasaklaw sa aming mga node. 93 00:04:22,410 --> 00:04:24,060 Ayos. 94 00:04:24,060 --> 00:04:29,390 >> Ang lahat ng mga karapatan, kaya sa paghahanap, bilang namin lamang sinasabi bago banda, kung ikaw ay 95 00:04:29,390 --> 00:04:31,840 pagpunta upang maghanap sa pamamagitan ng, mayroon kang upang aktwal na umulit 96 00:04:31,840 --> 00:04:33,660 sa pamamagitan ng iyong listahan ng naka-link. 97 00:04:33,660 --> 00:04:38,530 Kaya kung kaming naghahanap ng para sa bilang 9, gusto naming magsimula sa aming ulo 98 00:04:38,530 --> 00:04:41,520 at na tumuturo sa amin sa simula sa aming mga naka-link na listahan, i-right? 99 00:04:41,520 --> 00:04:44,600 At sabihin namin, OK, ginagawa ito node naglalaman ng mga numero ng 9? 100 00:04:44,600 --> 00:04:45,690 Walang? 101 00:04:45,690 --> 00:04:47,500 >> Ang lahat ng mga karapatan, pumunta sa susunod na isa. 102 00:04:47,500 --> 00:04:48,312 Sundin ito. 103 00:04:48,312 --> 00:04:49,520 Ito ay naglalaman ng mga numero ng 9? 104 00:04:49,520 --> 00:04:50,570 Hindi. 105 00:04:50,570 --> 00:04:51,550 Sundin ang mga susunod na isa. 106 00:04:51,550 --> 00:04:55,490 >> Kaya mayroon kaming upang aktwal na umulit sa pamamagitan ng aming listahan na naka-link. 107 00:04:55,490 --> 00:05:00,070 Hindi namin lamang pumunta nang direkta sa kung saan 9 ay. 108 00:05:00,070 --> 00:05:05,860 At kung talagang nais mong guys sa makakita ng ilang palsipikado-code up doon. 109 00:05:05,860 --> 00:05:10,420 Mayroon kaming ilang mga pag-andar ng paghahanap dito na tumatagal in-- kung ano ang aabutin sa? 110 00:05:10,420 --> 00:05:13,110 111 00:05:13,110 --> 00:05:14,320 Ano ang iyong palagay? 112 00:05:14,320 --> 00:05:15,960 Kaya madaling isa. 113 00:05:15,960 --> 00:05:17,784 Ano ito? 114 00:05:17,784 --> 00:05:18,700 Madla: [hindi marinig]. 115 00:05:18,700 --> 00:05:20,366 Tagapagsalita 1: Ang dami kaming naghahanap ng para sa. 116 00:05:20,366 --> 00:05:20,980 Mag-right? 117 00:05:20,980 --> 00:05:22,875 At kung ano ay tumutugma ito sa? 118 00:05:22,875 --> 00:05:25,020 Ito ay isang pointer sa? 119 00:05:25,020 --> 00:05:26,000 >> Madla: Isang node. 120 00:05:26,000 --> 00:05:28,980 >> Tagapagsalita 1: Isang node sa listahan na kaming naghahanap sa, i-right? 121 00:05:28,980 --> 00:05:33,700 Kaya mayroon kaming ilang mga node ay pointer dito. 122 00:05:33,700 --> 00:05:37,240 Ito ay isang punto na pupuntahan aktwal na umulit sa pamamagitan ng aming listahan. 123 00:05:37,240 --> 00:05:39,630 Itinakda namin ito katumbas ng ilista dahil iyon lamang 124 00:05:39,630 --> 00:05:44,380 pagtatakda dito katumbas ng simulan sa aming listahan na naka-link. 125 00:05:44,380 --> 00:05:50,660 >> At habang hindi null, habang mayroon pa rin kaming mga bagay sa aming listahan, 126 00:05:50,660 --> 00:05:55,580 suriin upang makita kung na node ay may ang bilang kaming naghahanap ng para sa. 127 00:05:55,580 --> 00:05:57,740 Nagbabalik ng tunay. 128 00:05:57,740 --> 00:06:01,070 Kung hindi man, i-update ito, i-right? 129 00:06:01,070 --> 00:06:04,870 >> Kung ito ay walang bisa, lumabas namin ang aming habang loop at return false 130 00:06:04,870 --> 00:06:08,340 dahil ibig sabihin nito ay hindi pa kami nakakahanap ito. 131 00:06:08,340 --> 00:06:11,048 Lahat ng tao makakuha ba kung paano na gumagana? 132 00:06:11,048 --> 00:06:11,548 OK. 133 00:06:11,548 --> 00:06:14,940 134 00:06:14,940 --> 00:06:20,260 >> Kaya may mga pagpapasok, mo May tatlong iba't ibang paraan. 135 00:06:20,260 --> 00:06:25,250 Maaari mong i-prepend, maaari mong ikabit ang at maaari mong ipasok sa sari-sari. 136 00:06:25,250 --> 00:06:28,215 Sa kasong ito, hindi namin pagpunta sa gawin ang isang i-prepend. 137 00:06:28,215 --> 00:06:33,380 Sinuman Alam ba ng kung paano mga ay maaaring maiba tatlong mga kaso? 138 00:06:33,380 --> 00:06:36,920 >> Kaya i-prepend nangangahulugan na inilagay mo ito sa harap ng iyong listahan. 139 00:06:36,920 --> 00:06:39,770 Kaya na nangangahulugan na hindi mahalaga ano ang iyong mga node ay, hindi mahalaga 140 00:06:39,770 --> 00:06:43,160 kung ano ang halaga ay, na iyong pupuntahan upang ilagay ito dito mismo sa harap, OK? 141 00:06:43,160 --> 00:06:45,160 Ito ay pagpunta sa maging una sangkap sa iyong listahan. 142 00:06:45,160 --> 00:06:49,510 >> Kung isama mo ito, ito ay pagpunta upang pumunta sa likod ng iyong listahan. 143 00:06:49,510 --> 00:06:54,010 At ipasok sa sari-sari ibig sabihin ikaw ay pagpunta sa ilagay sa lugar na aktwal 144 00:06:54,010 --> 00:06:57,700 kung saan ito ay nagpapanatili pinagsunod-sunod sa iyong listahan ng naka-link. 145 00:06:57,700 --> 00:07:00,810 Muli, kung paano gamitin mo mga at kapag ginagamit mo ang 146 00:07:00,810 --> 00:07:02,530 ang mga ito ay nag-iiba depende sa iyong kaso. 147 00:07:02,530 --> 00:07:05,834 148 00:07:05,834 --> 00:07:07,750 Kung hindi ito kailangang ay pinagsunod-sunod, i-prepend ay may gawi 149 00:07:07,750 --> 00:07:10,460 upang maging kung ano ang karamihan ng mga tao gamitin dahil hindi mo 150 00:07:10,460 --> 00:07:15,680 kailangang pumunta sa pamamagitan ng buong listahan upang mahanap ang dulo upang idagdag ito sa, i-right? 151 00:07:15,680 --> 00:07:17,720 Maaari mong ilagay lang ito sa mismong. 152 00:07:17,720 --> 00:07:21,930 >> Kaya magpapatuloy kami sa pamamagitan ng isang pagpapasok 1 ngayon. 153 00:07:21,930 --> 00:07:26,360 Kaya isang bagay na pupuntahan ko lubos na inirerekomenda sa pset 154 00:07:26,360 --> 00:07:29,820 ay upang gumuhit ng mga bagay out, tulad ng nakasanayan. 155 00:07:29,820 --> 00:07:35,130 Napakahalaga na i-update ka ang iyong mga payo sa tamang pagkakasunod-sunod 156 00:07:35,130 --> 00:07:38,620 dahil kung i-update mo ang mga ito bahagyang out sa pagkakasunud-sunod, 157 00:07:38,620 --> 00:07:42,210 na iyong pupuntahan ay napupunta pagkawala ng mga bahagi ng iyong listahan. 158 00:07:42,210 --> 00:07:49,680 >> Kaya halimbawa, sa kasong ito, hindi namin na nagsasabi sa pinuno sa punto lamang sa 1. 159 00:07:49,680 --> 00:07:56,070 Kung gagawin lamang namin na walang pag-save ito ng 1, 160 00:07:56,070 --> 00:07:58,570 wala kaming ideya kung ano ang 1 ay dapat tumuro sa ngayon 161 00:07:58,570 --> 00:08:02,490 dahil nawalan kami kung ano ang ulo itinuturo sa. 162 00:08:02,490 --> 00:08:05,530 Kaya isa bagay na dapat tandaan kapag gumawa ka ng isang i-prepend 163 00:08:05,530 --> 00:08:09,630 ay upang i-save ang kung ano ang ulo punto upang una, 164 00:08:09,630 --> 00:08:15,210 pagkatapos ay i-reassign ito, at pagkatapos ay i-update ano ang dapat tumuro sa iyong bagong node. 165 00:08:15,210 --> 00:08:20,870 166 00:08:20,870 --> 00:08:22,560 Sa kasong ito, ito ay isang paraan upang gawin ito. 167 00:08:22,560 --> 00:08:25,440 >> Kaya kung tapos na kami ay ito sa ganitong paraan kung saan kami reassigned lang ulo, 168 00:08:25,440 --> 00:08:30,320 mawalan kami talaga ang aming buong listahan, i-right? 169 00:08:30,320 --> 00:08:38,000 Ang isang paraan upang gawin ito ay ang magkaroon ng 1 punto upang susunod na, at pagkatapos ay magkaroon ng ulo punto upang 1. 170 00:08:38,000 --> 00:08:42,650 O maaari mong gawin uri ng tulad ng pansamantalang imbakan, na usapan ko ang tungkol. 171 00:08:42,650 --> 00:08:45,670 >> Ngunit reassigning iyong mga payo sa tamang pagkakasunod-sunod 172 00:08:45,670 --> 00:08:48,750 ay magiging napaka, napaka mahalaga para sa pset. 173 00:08:48,750 --> 00:08:53,140 Kung hindi man, na iyong pupuntahan ay may hash talahanayan o isang try na lang magiging 174 00:08:53,140 --> 00:08:56,014 lamang ng bahagi ng mga salita na gusto at pagkatapos ay you're-- mmhmm? 175 00:08:56,014 --> 00:08:58,930 Madla: Ano ang pansamantalang storage bagay na iyong pinag-uusapan? 176 00:08:58,930 --> 00:09:00,305 Tagapagsalita 1: Ang pansamantalang imbakan. 177 00:09:00,305 --> 00:09:02,760 Kaya isa lamang ng isa pang paraan na maaari mong gawin ito 178 00:09:02,760 --> 00:09:07,650 ay iimbak ang pinuno ng isang bagay, tulad ng iimbak ito ang pansamantalang variable. 179 00:09:07,650 --> 00:09:11,250 Magtalaga ito sa 1 at pagkatapos ay i-update ang 1 upang tumuro 180 00:09:11,250 --> 00:09:13,830 sa anumang ulo ginamit upang tumuro sa. 181 00:09:13,830 --> 00:09:16,920 Sa paraang ito ay malinaw naman higit pa eleganteng dahil sa iyo 182 00:09:16,920 --> 00:09:20,770 hindi na kailangan ng pansamantalang halaga, ngunit nag-aalok lamang ng isa pang paraan upang gawin ito. 183 00:09:20,770 --> 00:09:23,999 184 00:09:23,999 --> 00:09:25,790 At talagang namin ang mayroon ang ilang mga code para sa na ito. 185 00:09:25,790 --> 00:09:28,080 Kaya para sa naka-link na listahan, namin aktwal na magkaroon ng ilang code. 186 00:09:28,080 --> 00:09:31,930 Kaya ipasok dito, ito ay prepending. 187 00:09:31,930 --> 00:09:34,290 Kaya ito ay pumasok ito sa ulo. 188 00:09:34,290 --> 00:09:38,820 >> Kaya unang bagay, kailangan mong lumikha ng iyong bagong node, siyempre, 189 00:09:38,820 --> 00:09:40,790 at suriin para sa null. 190 00:09:40,790 --> 00:09:43,250 Palaging mabuti. 191 00:09:43,250 --> 00:09:47,840 At pagkatapos ay kailangan mo upang magtalaga ng mga halaga. 192 00:09:47,840 --> 00:09:51,260 Tuwing kang lumikha ng isang bagong node, mo hindi malaman kung ano ang nagtuturo sa susunod, 193 00:09:51,260 --> 00:09:54,560 kaya gusto mong i-initialize ito sa null. 194 00:09:54,560 --> 00:09:58,760 Kung ito ay nagtatapos up na tumuturo sa isang bagay tao, maipo-reassigned at ito ay multa. 195 00:09:58,760 --> 00:10:00,740 Kung ito ang unang bagay sa listahan, kailangan nito 196 00:10:00,740 --> 00:10:04,270 upang tumuro sa null dahil iyon ang katapusan ng listahan. 197 00:10:04,270 --> 00:10:12,410 >> Kaya pagkatapos ay upang ipasok ito, makikita natin dito namin ay magtatalaga sa susunod na halaga ng aming mga node 198 00:10:12,410 --> 00:10:17,380 upang maging anumang head ay, na kung saan ay kung ano ang namin ay may dito. 199 00:10:17,380 --> 00:10:19,930 Iyon ay kung ano ang ginawa namin lamang. 200 00:10:19,930 --> 00:10:25,820 At pagkatapos kami ay nagtatalaga ng ulo papunta sa puntong sa aming bagong node, dahil tandaan, 201 00:10:25,820 --> 00:10:31,090 bagong ay ilang pointer sa isang node, at iyon mismo ang ulo ay. 202 00:10:31,090 --> 00:10:34,370 Iyon ay eksakto kung bakit namin Mayroon na ito arrow accessor. 203 00:10:34,370 --> 00:10:37,030 204 00:10:37,030 --> 00:10:37,530 Cool? 205 00:10:37,530 --> 00:10:38,130 Mmhmm? 206 00:10:38,130 --> 00:10:41,100 >> Madla: Mayroon kaming pagsisimula ng bagong tabi ng unang null, 207 00:10:41,100 --> 00:10:44,240 o maaari naming initialize lang ito sa magtungo? 208 00:10:44,240 --> 00:10:48,210 >> Tagapagsalita 1: Bagong susunod Kailangang maging null upang magsimulang 209 00:10:48,210 --> 00:10:53,760 dahil hindi mo alam kung saan ito magiging. 210 00:10:53,760 --> 00:10:56,100 Gayundin, ito ay uri ng gusto lang tularan. 211 00:10:56,100 --> 00:10:59,900 Itakda mo ito katumbas ng null upang gumawa lamang Siguraduhin na ang lahat ng iyong mga bases ay sakop 212 00:10:59,900 --> 00:11:04,070 bago mo gawin ang anumang reassignment upang ang Palagi ka katiyakan na ito 213 00:11:04,070 --> 00:11:08,880 ay nagtuturo sa isang tukoy na halaga kumpara tulad ng isang halaga ng basura. 214 00:11:08,880 --> 00:11:12,210 Dahil, oo, magtalaga namin bagong susunod na awtomatiko, 215 00:11:12,210 --> 00:11:15,420 ngunit higit pa tulad ng isang mahusay na kasanayan i-initialize ito 216 00:11:15,420 --> 00:11:19,270 sa paraang iyon at pagkatapos ay i-reassign. 217 00:11:19,270 --> 00:11:23,420 >> OK, kaya doble naka-link na mga listahan ngayon. 218 00:11:23,420 --> 00:11:24,601 Ano ang palagay namin? 219 00:11:24,601 --> 00:11:26,350 Ano ang naiiba sa doble naka-link na listahan? 220 00:11:26,350 --> 00:11:30,750 221 00:11:30,750 --> 00:11:34,300 >> Kaya sa aming mga listahan na naka-link, maaari naming ilipat lamang sa isa direksyon, i-right? 222 00:11:34,300 --> 00:11:35,270 Mayroon susunod na lamang kami. 223 00:11:35,270 --> 00:11:36,760 Maaari lamang kami pumunta pasulong. 224 00:11:36,760 --> 00:11:40,300 >> Sa isang doble naka-link na listahan, Maaari din namin ilipat pabalik. 225 00:11:40,300 --> 00:11:44,810 Kaya mayroon kaming hindi lamang ang numero na nais naming mag-imbak, 226 00:11:44,810 --> 00:11:50,110 mayroon kaming kung saan ito tumuturo sa tabi at kung saan lamang kami nanggaling. 227 00:11:50,110 --> 00:11:52,865 Kaya ito ay nagbibigay-daan para sa ilang mas mahusay na traversal. 228 00:11:52,865 --> 00:11:56,620 229 00:11:56,620 --> 00:12:01,240 >> Kaya doble naka-link node, halos katulad na, i-right? 230 00:12:01,240 --> 00:12:05,000 Pagkakaiba lamang ay na namin ngayon May susunod at nakaraang. 231 00:12:05,000 --> 00:12:06,235 Ito ay ang pagkakaiba lamang. 232 00:12:06,235 --> 00:12:09,570 233 00:12:09,570 --> 00:12:14,790 >> Kaya kung kami ay upang i-prepend o append-- namin walang anumang code para sa hanggang here-- 234 00:12:14,790 --> 00:12:17,830 ngunit kung ikaw ay upang subukan at ipasok ito, ang mga mahalagang bagay 235 00:12:17,830 --> 00:12:19,980 ay kailangan mong gumawa ng mga sigurado ka sa pagtatalaga 236 00:12:19,980 --> 00:12:23,360 pareho sa iyong nakaraang at ang iyong susunod na pointer tama. 237 00:12:23,360 --> 00:12:29,010 Kaya sa kasong ito, nais mong hindi lamang simulan ang susunod, 238 00:12:29,010 --> 00:12:31,820 initialize mo nakaraang. 239 00:12:31,820 --> 00:12:36,960 Kung hindi namin sa ulo ng listahan, namin gagawin ulo katumbas bagong hindi lamang, 240 00:12:36,960 --> 00:12:41,750 ngunit ang aming mga bagong dating dapat tumuturo sa ulo, tama? 241 00:12:41,750 --> 00:12:43,380 >> Iyan ang pagkakaiba lamang. 242 00:12:43,380 --> 00:12:47,200 At kung gusto mong higit pang mga kasanayan sa ang mga may naka-link na listahan, na may Pagpasok, 243 00:12:47,200 --> 00:12:49,900 sa pagtanggal, na may insert sa isang sari-sari listahan, 244 00:12:49,900 --> 00:12:52,670 mangyaring tingnan ang study.cs50.net. 245 00:12:52,670 --> 00:12:54,870 Mayroong isang bungkos ng mahusay na pagsasanay. 246 00:12:54,870 --> 00:12:55,870 Masidhing kong inirerekumenda ang mga ito. 247 00:12:55,870 --> 00:12:59,210 Gusto ko namin ay may oras upang pumunta sa pamamagitan ng mga ito ngunit maraming mga istraktura ng data 248 00:12:59,210 --> 00:13:01,530 upang makakuha ng sa pamamagitan ng. 249 00:13:01,530 --> 00:13:02,650 >> OK, kaya hash talahanayan. 250 00:13:02,650 --> 00:13:07,070 Ito ay malamang na ang karamihan kapaki-pakinabang na bit para sa iyong pset 251 00:13:07,070 --> 00:13:11,090 dito dahil ka pagpunta sa maging pagpapatupad ng isa sa mga ito, o isang try. 252 00:13:11,090 --> 00:13:12,200 Talagang gusto ko ng hash talahanayan. 253 00:13:12,200 --> 00:13:13,110 Ang mga ito ay medyo cool. 254 00:13:13,110 --> 00:13:17,080 >> Kaya kung ano talaga ang mangyayari ay isang hash talahanayan 255 00:13:17,080 --> 00:13:22,050 ay kapag talagang kailangan naming mabilis pagpapasok ng, pagtanggal, at lookup. 256 00:13:22,050 --> 00:13:25,010 Iyon ang mga bagay na hindi namin prioritizing sa isang hash table. 257 00:13:25,010 --> 00:13:29,500 Maaari silang makakuha ng medyo malaki, ngunit bilang namin makita sa pagsubok, 258 00:13:29,500 --> 00:13:33,040 may mga bagay na magkano ang mas malaking. 259 00:13:33,040 --> 00:13:38,330 >> Ngunit talaga, ang lahat ng hash talahanayan ay isang hash 260 00:13:38,330 --> 00:13:47,215 na nagsasabi sa iyo kung aling mga bucket upang ilagay ang bawat ng iyong data, bawat isa sa iyong mga elemento sa. 261 00:13:47,215 --> 00:13:51,140 Ang isang simpleng paraan upang i-isip ng isang hash talahanayan ay tumutulong ito lamang bucket ng mga bagay, 262 00:13:51,140 --> 00:13:51,770 tama? 263 00:13:51,770 --> 00:13:59,720 Kaya kapag naka-uuri-uri ng mga bagay sa pamamagitan ng tulad ng unang titik ng kanilang pangalan, 264 00:13:59,720 --> 00:14:01,820 na uri ng tulad ng isang hash talahanayan. 265 00:14:01,820 --> 00:14:06,180 >> Kaya kung ako ay sa pangkat na iyong guys ay sa mga grupo ng kahit sino ay nagsisimula sa pangalan 266 00:14:06,180 --> 00:14:11,670 may isang paglipas dito, o kung sinuman ang kaarawan Nasa Enero, Pebrero, Marso, 267 00:14:11,670 --> 00:14:15,220 anumang, na epektibong paglikha ng isang hash table. 268 00:14:15,220 --> 00:14:18,120 Ay lamang paglikha ito bucket na mong ayusin ang mga elemento sa 269 00:14:18,120 --> 00:14:19,520 nang sa gayon ay maaari kang makahanap ng mas madali ang mga ito. 270 00:14:19,520 --> 00:14:22,300 Kaya sa ganitong paraan kapag kailangan ko upang mahanap ang isa sa iyo, 271 00:14:22,300 --> 00:14:24,680 Hindi ko na kailangang maghanap sa pamamagitan ng bawat isa sa iyong pangalan. 272 00:14:24,680 --> 00:14:29,490 Maaari ko bang maging tulad ng, oh, alam ko na Kaarawan Danielle ay in-- 273 00:14:29,490 --> 00:14:30,240 Madla: --April. 274 00:14:30,240 --> 00:14:30,948 Tagapagsalita 1: Abril. 275 00:14:30,948 --> 00:14:33,120 Kaya tumingin ako sa aking Abril bucket, at sa sinumang swerte, 276 00:14:33,120 --> 00:14:38,270 Makikita niya maging ang isa lamang doon at ang aking oras ay pare-pareho sa na-unawa, 277 00:14:38,270 --> 00:14:41,230 samantalang kung mayroon akong upang tumingin sa pamamagitan ng isang buong bungkos ng mga tao, 278 00:14:41,230 --> 00:14:43,090 ito ay pagpunta sa tumagal ng mas matagal. 279 00:14:43,090 --> 00:14:45,830 Kaya hash talahanayan ay talagang lamang bucket. 280 00:14:45,830 --> 00:14:48,630 Madaling paraan upang isipin ang mga ito. 281 00:14:48,630 --> 00:14:52,930 >> Kaya isang napaka-mahalagang bagay tungkol sa isang hash talahanayan ay isang hash. 282 00:14:52,930 --> 00:14:58,140 Kaya ang mga bagay lamang usapan ko, tulad ng ang iyong unang titik ng iyong unang pangalan 283 00:14:58,140 --> 00:15:01,450 o ang iyong mga buwan petsa ng kapanganakan, ang mga ito ay mga ideya na 284 00:15:01,450 --> 00:15:03,070 talagang kaugnayan sa isang hash. 285 00:15:03,070 --> 00:15:08,900 Ito ay lamang ng isang paraan ng pagpapasya kung aling mga Bucket ka elemento napupunta sa, OK? 286 00:15:08,900 --> 00:15:14,850 Kaya para sa pset, maaari kang tumingin up halos anumang hash na gusto mo. 287 00:15:14,850 --> 00:15:16,030 >> Hindi na kailangang maging ang iyong sariling. 288 00:15:16,030 --> 00:15:21,140 Mayroong ilang mga talagang cool na mga out doon na gawin ang lahat ng uri ng mga nakatutuwang matematika. 289 00:15:21,140 --> 00:15:25,170 At kung nais mong gumawa ng iyong napakabilis na spellchecker, 290 00:15:25,170 --> 00:15:27,620 Gagawin ko talaga tumingin sa isa sa mga iyon. 291 00:15:27,620 --> 00:15:32,390 >> Ngunit may mga din ang simpleng na, tulad ng tayahin 292 00:15:32,390 --> 00:15:39,010 ang kabuuan ng salita, tulad ng bawat titik na may isang numero. 293 00:15:39,010 --> 00:15:39,940 I-compute ang kabuuan. 294 00:15:39,940 --> 00:15:42,230 Na tumutukoy sa bucket. 295 00:15:42,230 --> 00:15:45,430 Mayroon din nila ang mga madaling mga iyon ay tulad lang ng lahat ng mga A dito, 296 00:15:45,430 --> 00:15:47,050 lahat ng mga B meron dito. 297 00:15:47,050 --> 00:15:48,920 Anumang isa sa mga iyon. 298 00:15:48,920 --> 00:15:55,770 >> Talaga, sinasabi lang ito sa iyo kung aling array index ay dapat pumunta sa iyong elemento. 299 00:15:55,770 --> 00:15:58,690 Pagpapasya lamang ang bucket-- lahat ng ito ay isang hash ay. 300 00:15:58,690 --> 00:16:04,180 Kaya dito mayroon kaming isang halimbawa kung saan ay lang ang unang titik ng string 301 00:16:04,180 --> 00:16:05,900 na ako ay pakikipag-usap lamang tungkol. 302 00:16:05,900 --> 00:16:11,900 >> Kaya mayroon kang ilang mga hash na lang ang unang titik ng iyong string minus A, 303 00:16:11,900 --> 00:16:16,090 na kung saan ay magbibigay sa iyo ng ilang mga numero sa pagitan ng 0 at 25. 304 00:16:16,090 --> 00:16:20,790 At ano ang gusto mong gawin ay tiyakin na ito ay kumakatawan sa 305 00:16:20,790 --> 00:16:24,110 sa laki ng iyong hash table-- kung gaano karaming mga bucket mayroong. 306 00:16:24,110 --> 00:16:25,860 Sa marami sa mga hash function, ang mga ito ay 307 00:16:25,860 --> 00:16:31,630 pagpunta na bumabalik na halaga na maaari maging malayo sa itaas ng mga numero ng mga bucket 308 00:16:31,630 --> 00:16:33,610 na iyong aktwal na mayroon sa iyong talahanayan ng hash, 309 00:16:33,610 --> 00:16:37,240 kaya kailangan mong gumawa ng mga Tiyaking at mod sa pamamagitan ng mga iyon. 310 00:16:37,240 --> 00:16:42,190 Kung hindi man, ito ay pagpunta sa sabihin, naku, dapat itong maging sa bucket 5,000 311 00:16:42,190 --> 00:16:46,040 ngunit mayroon 30 ka lang mga bucket sa iyong talahanayan ng hash. 312 00:16:46,040 --> 00:16:49,360 At siyempre, namin ang lahat ng alam na pagpunta sa magresulta sa ilang mga nakatutuwang mga error. 313 00:16:49,360 --> 00:16:52,870 Kaya tiyaking i-mod ng laki ng iyong talahanayan ng hash. 314 00:16:52,870 --> 00:16:58,430 315 00:16:58,430 --> 00:16:58,930 Ayos. 316 00:16:58,930 --> 00:17:00,506 Kaya collisions. 317 00:17:00,506 --> 00:17:02,620 Mabuti ay lahat ng tao sa ngayon? 318 00:17:02,620 --> 00:17:03,120 Mmhmm? 319 00:17:03,120 --> 00:17:05,900 >> Madla: Bakit gagawin ito bumalik tulad ng napakalaking halaga? 320 00:17:05,900 --> 00:17:09,210 >> Tagapagsalita 1: Depende sa mga algorithm na ang iyong hash gumagamit. 321 00:17:09,210 --> 00:17:12,270 Ang ilan sa kanila ay gawin basag ang pula pagpaparami. 322 00:17:12,270 --> 00:17:16,270 At lahat ng ito ay tungkol sa pagkuha ng isang pantay na pamamahagi, 323 00:17:16,270 --> 00:17:18,490 kaya ginagawa nila ang ilang mga talagang minsan na nakatutuwang bagay. 324 00:17:18,490 --> 00:17:20,960 Iyon lang. 325 00:17:20,960 --> 00:17:22,140 Ano pa? 326 00:17:22,140 --> 00:17:22,829 OK. 327 00:17:22,829 --> 00:17:24,480 >> Kaya collisions. 328 00:17:24,480 --> 00:17:29,270 Talaga, tulad ng mga naunang sinabi ko, sa pinakamahusay na sitwasyon kaso, 329 00:17:29,270 --> 00:17:32,040 anumang mga bucket tumingin ako sa ay pagpunta sa magkaroon ng isang bagay, 330 00:17:32,040 --> 00:17:34,160 kaya wala akong upang tumingin sa lahat, tama? 331 00:17:34,160 --> 00:17:37,040 Ako alinman alam ito doon o ito Hindi, at iyon ang kung ano ang namin talagang gusto. 332 00:17:37,040 --> 00:17:43,960 Ngunit kung mayroon kaming libu-libong mga data point at mas mababa sa numero na 333 00:17:43,960 --> 00:17:48,700 ng mga bucket, kami ay pagpunta sa may collisions kung saan huli ay isang bagay na 334 00:17:48,700 --> 00:17:54,210 ay pagpunta sa may upang tapusin up sa isang bucket na mayroon isang elemento. 335 00:17:54,210 --> 00:17:57,390 >> Kaya ang tanong ay, kung ano ang huwag namin gawin sa kasong iyon? 336 00:17:57,390 --> 00:17:58,480 Ano ang naming gawin? 337 00:17:58,480 --> 00:17:59,300 Kami ay mayroon ng isang bagay doon? 338 00:17:59,300 --> 00:18:00,060 Huwag magtapon namin lamang ito? 339 00:18:00,060 --> 00:18:00,700 >> Hindi. 340 00:18:00,700 --> 00:18:01,980 Mayroon kaming upang panatilihing pareho sa mga ito. 341 00:18:01,980 --> 00:18:06,400 Kaya ang paraan na aming Karaniwang gawin iyon ay kung ano? 342 00:18:06,400 --> 00:18:08,400 Ano ang istraktura ng data usapan lang namin tungkol sa? 343 00:18:08,400 --> 00:18:09,316 Madla: Naka-link na listahan. 344 00:18:09,316 --> 00:18:10,500 Tagapagsalita 1: Isang naka-link na listahan. 345 00:18:10,500 --> 00:18:16,640 Kaya ngayon, sa halip na bawat isa sa mga mga bucket lamang pagkakaroon ng isang elemento, 346 00:18:16,640 --> 00:18:24,020 ito ay pagpunta sa maglaman ng isang naka-link na listahan ng mga ang mga elemento na-hash na ito. 347 00:18:24,020 --> 00:18:27,588 OK, ang lahat uri ng makakuha na ideya? 348 00:18:27,588 --> 00:18:30,546 Dahil hindi namin maaaring magkaroon ng isang array dahil hindi namin alam kung gaano karaming mga bagay 349 00:18:30,546 --> 00:18:31,730 ay magiging doon. 350 00:18:31,730 --> 00:18:36,540 Ay nagbibigay-daan sa amin ang isang naka-link na listahan upang Mayroon lamang ang eksaktong numero na 351 00:18:36,540 --> 00:18:38,465 ay na-hash na sa bucket, tama? 352 00:18:38,465 --> 00:18:42,260 353 00:18:42,260 --> 00:18:50,500 >> Kaya linear probing ay talaga ito idea-- 354 00:18:50,500 --> 00:18:52,300 ito ay isang paraan upang harapin ang isang banggaan. 355 00:18:52,300 --> 00:18:58,010 Ano ang maaari mong gawin ay kung, sa kaso, isang itlog ng isda ay na-hash sa 1 356 00:18:58,010 --> 00:19:01,130 at kami ay mayroon ng isang bagay doon, lamang sa iyo 357 00:19:01,130 --> 00:19:04,840 panatilihin ang pagpunta pababa hanggang sa mahanap ka ng isang walang laman na slot. 358 00:19:04,840 --> 00:19:06,370 Iyon ay isang paraan upang mahawakan ito. 359 00:19:06,370 --> 00:19:09,020 Ang iba pang mga paraan upang mahawakan ito ay may kung ano ang namin lamang 360 00:19:09,020 --> 00:19:12,280 called-- sa naka-link listahan ay tinatawag na chaining. 361 00:19:12,280 --> 00:19:20,510 >> Kaya gumagana sa ideya na ito kung sa iyong talahanayan ng hash sa tingin mo 362 00:19:20,510 --> 00:19:24,150 ay mas malaki kaysa ang iyong data set o kung 363 00:19:24,150 --> 00:19:28,870 gusto mong subukan at i-minimize chaining hanggang sa ito ay talagang kinakailangan. 364 00:19:28,870 --> 00:19:34,050 Kaya ang isang bagay ay linear probing malinaw naman ay nangangahulugan 365 00:19:34,050 --> 00:19:37,290 na ang iyong mga hash ay hindi masyadong kapaki-pakinabang 366 00:19:37,290 --> 00:19:42,200 dahil ka pagpunta sa mga end up gamit ang iyong hash, nakakakuha sa isang punto, 367 00:19:42,200 --> 00:19:46,400 linear mong suriin pababa sa ang ilang mga lugar na iyon ay magagamit. 368 00:19:46,400 --> 00:19:49,670 Ngunit ngayon, siyempre, kahit ano tao na nagtatapos up doon, 369 00:19:49,670 --> 00:19:52,050 ka ng pagpunta sa mayroon sa maghanap ng kahit na sa mas ibaba pa. 370 00:19:52,050 --> 00:19:55,650 >> At maraming higit pa gastos sa paghahanap na 371 00:19:55,650 --> 00:19:59,820 Naging inputting isang elemento sa iyong talahanayan ng hash ngayon, tama? 372 00:19:59,820 --> 00:20:05,640 At ngayon kapag kang pumunta at subukan at maghanap ng isang itlog ng isda muli, na iyong pupuntahan hash ito, 373 00:20:05,640 --> 00:20:07,742 at ito ay pagpunta sa sabihin, oh, tumingin sa bucket 1, 374 00:20:07,742 --> 00:20:09,700 at ito ay hindi magiging sa bucket 1, kaya ikaw ay 375 00:20:09,700 --> 00:20:11,970 pagpunta sa may upang tumawid sa pamamagitan ng natitirang bahagi ng mga ito. 376 00:20:11,970 --> 00:20:17,720 Kaya minsan ito ay kapaki-pakinabang, ngunit sa karamihan ng mga kaso, 377 00:20:17,720 --> 00:20:22,660 kami ay pagpunta sa sabihin na chaining ay kung ano ang gusto mong gawin. 378 00:20:22,660 --> 00:20:25,520 >> Kaya usapan natin ang tungkol na ito nang mas maaga. 379 00:20:25,520 --> 00:20:27,812 Nakakuha ako ng isang maliit na mas maaga sa kanilang sarili ko. 380 00:20:27,812 --> 00:20:33,560 Ngunit chaining ay isa na sa bawat bucket sa iyong talahanayan ng hash 381 00:20:33,560 --> 00:20:36,120 lamang ang naka-link na listahan. 382 00:20:36,120 --> 00:20:39,660 >> Kaya isa pang paraan, o mga teknikal na paraan, mag-isip ng isang hash talahanayan 383 00:20:39,660 --> 00:20:44,490 ay tumutulong ito lamang ay isang array ng naka-link na mga listahan, na 384 00:20:44,490 --> 00:20:49,330 kapag sumusulat ka sa iyong diksyunaryo at sinusubukan mong i-load ito, 385 00:20:49,330 --> 00:20:52,070 iniisip ito bilang isang hanay ng mga naka-link na mga listahan 386 00:20:52,070 --> 00:20:54,390 Gagawing mas madali para sa iyo na simulan ang. 387 00:20:54,390 --> 00:20:57,680 >> Madla: Kaya hash talahanayan May isang paunang natukoy na laki, 388 00:20:57,680 --> 00:20:58,980 tulad ng isang [hindi marinig] ng mga bucket? 389 00:20:58,980 --> 00:20:59,220 >> Tagapagsalita 1: I-right. 390 00:20:59,220 --> 00:21:01,655 Kaya ito ay may isang hanay na bilang ng mga mga bucket na determine-- mo 391 00:21:01,655 --> 00:21:03,530 kung saan mo guys dapat huwag mag-atubiling i-play sa. 392 00:21:03,530 --> 00:21:05,269 Maaari itong maging medyo cool upang makita kung ano ang mangyayari 393 00:21:05,269 --> 00:21:06,810 bilang baguhin mo ang iyong numero ng mga bucket. 394 00:21:06,810 --> 00:21:09,410 395 00:21:09,410 --> 00:21:11,510 Ngunit oo, ito ay may itakda ang numero ng mga bucket. 396 00:21:11,510 --> 00:21:15,360 Ano ay nagbibigay-daan sa iyo upang magkasya bilang maraming mga sangkap na kailangan mo 397 00:21:15,360 --> 00:21:19,350 ay ang nakahiwalay na chaining kung saan mo na mga listahan na naka-link sa bawat bucket. 398 00:21:19,350 --> 00:21:22,850 Iyon ay nangangahulugang ang iyong talahanayan ng hash ay eksakto ang laki 399 00:21:22,850 --> 00:21:25,440 na kakailanganin mo ito upang maging, tama? 400 00:21:25,440 --> 00:21:27,358 Iyan ang buong punto ng naka-link na mga listahan. 401 00:21:27,358 --> 00:21:30,850 402 00:21:30,850 --> 00:21:32,480 Ayos. 403 00:21:32,480 --> 00:21:38,780 >> Kaya OK lahat doon? 404 00:21:38,780 --> 00:21:39,801 Lahat ng karapatan. 405 00:21:39,801 --> 00:21:40,300 Ah. 406 00:21:40,300 --> 00:21:41,860 Ano lamang ang nangyari? 407 00:21:41,860 --> 00:21:42,960 Talagang ngayon. 408 00:21:42,960 --> 00:21:45,250 Hulaan ang isang tao ay pagpatay sa akin. 409 00:21:45,250 --> 00:21:52,060 >> OK kami ng pagpunta sa pumunta sa pagsubok, na kung saan ay isang maliit na mabaliw. 410 00:21:52,060 --> 00:21:53,140 Gusto ko ng hash talahanayan. 411 00:21:53,140 --> 00:21:54,460 Sa tingin ko ang mga ito ay talagang cool. 412 00:21:54,460 --> 00:21:56,710 Pagsubok ay cool na, masyadong. 413 00:21:56,710 --> 00:21:59,590 >> Kaya ang sinuman tandaan kung ano ang isang try ay? 414 00:21:59,590 --> 00:22:01,740 Dapat mo na nawala na sa paglipas ng ito sa madaling sabi sa aralin? 415 00:22:01,740 --> 00:22:04,570 416 00:22:04,570 --> 00:22:06,377 Tandaan mo ba ang uri ng kung paano ito gumagana? 417 00:22:06,377 --> 00:22:08,460 Madla: lamang ako nodding na namin pumunta sa paglipas ng ito. 418 00:22:08,460 --> 00:22:09,626 Tagapagsalita 1: namin pumunta sa paglipas ng ito. 419 00:22:09,626 --> 00:22:13,100 OK, talagang kami ng pagpunta sa pumunta sa paglipas dito ngayon ay kung ano ang sinasabi namin. 420 00:22:13,100 --> 00:22:14,860 >> Madla: Iyon ay para sa isang punong kahoy na pagbawi. 421 00:22:14,860 --> 00:22:15,280 >> Tagapagsalita 1: Oo. 422 00:22:15,280 --> 00:22:16,196 Ito ay isang punong kahoy na pagbawi. 423 00:22:16,196 --> 00:22:16,960 Kahanga-hanga. 424 00:22:16,960 --> 00:22:23,610 Kaya isang bagay na mapansin dito ay na namin ay tumitingin sa indibidwal na mga character 425 00:22:23,610 --> 00:22:24,480 dito, tama? 426 00:22:24,480 --> 00:22:29,710 >> Kaya bago sa aming hash, namin ay tumitingin sa mga salita bilang isang buo, 427 00:22:29,710 --> 00:22:32,270 at ngayon naghahanap kami ng higit pa sa mga character, tama? 428 00:22:32,270 --> 00:22:38,380 Kaya mayroon kaming Maxwell sa paglipas dito at Mendel. 429 00:22:38,380 --> 00:22:47,840 Kaya isa lamang try-- isang paraan upang tingin tungkol sa ito ay na ang bawat antas dito 430 00:22:47,840 --> 00:22:49,000 ay isang hanay ng mga titik. 431 00:22:49,000 --> 00:22:53,310 432 00:22:53,310 --> 00:22:55,790 Kaya ito ay ang iyong root node dito, tama? 433 00:22:55,790 --> 00:23:01,980 Ito ay ang lahat ng mga character ng alpabeto para sa simula ng bawat salita. 434 00:23:01,980 --> 00:23:06,480 >> At ano ang gusto mong gawin ay sabihin nating, OK, mayroon kaming ilang mga M salita. 435 00:23:06,480 --> 00:23:10,590 Kami ay pagpunta sa hitsura para sa Maxwell, kaya pumunta kami sa M. At M punto sa kabuuan 436 00:23:10,590 --> 00:23:14,800 iba pang isang array kung saan ang bawat salita, hangga't mayroong 437 00:23:14,800 --> 00:23:17,044 ay isang salita na may isang bilang ikalawang sulat, 438 00:23:17,044 --> 00:23:19,460 hangga't mayroong isang salita na May B bilang ikalawang sulat, 439 00:23:19,460 --> 00:23:24,630 magkakaroon ito ng pointer pagpunta sa ilang mga susunod na array. 440 00:23:24,630 --> 00:23:29,290 >> May malamang na hindi salita na MP ang isang bagay, 441 00:23:29,290 --> 00:23:32,980 kaya sa posisyon P sa array, magiging walang bisa lamang. 442 00:23:32,980 --> 00:23:38,840 Ito ay sabihin, OK, walang salita na M sinusundan ng isang P, OK? 443 00:23:38,840 --> 00:23:43,100 Kaya kung sa tingin namin tungkol dito, ang bawat isa ang isa sa mga mas maliliit na bagay 444 00:23:43,100 --> 00:23:47,990 ay talagang isa sa mga malaking array mula sa isang sa pamamagitan ng Z. 445 00:23:47,990 --> 00:23:55,064 Kaya kung ano ang maaaring maging isa sa mga bagay na uri ng isang sagabal ng isang subukan? 446 00:23:55,064 --> 00:23:56,500 >> Madla: Isang maraming memory. 447 00:23:56,500 --> 00:23:59,940 >> Tagapagsalita 1: Ito ay isang tonelada ng memorya, i-right? 448 00:23:59,940 --> 00:24:08,750 Ang bawat isa sa mga bloke dito kumakatawan sa 26 mga puwang, 26 element ng array. 449 00:24:08,750 --> 00:24:13,680 Kaya pagsusubok na makakuha ng mga hindi kapani-paniwalang espasyo mabigat. 450 00:24:13,680 --> 00:24:17,100 >> Ngunit ay napakabilis nila. 451 00:24:17,100 --> 00:24:22,540 Kaya hindi mapaniniwalaan o kapani-paniwala mabilis pero talagang hindi mabisa espasyo. 452 00:24:22,540 --> 00:24:24,810 Uri ng kailangang malaman kung alin ang gusto mo. 453 00:24:24,810 --> 00:24:29,470 Ang mga ito ay talagang cool na para sa iyong pset, ngunit ginagawa nila tumagal ng hanggang ng maraming memorya, 454 00:24:29,470 --> 00:24:30,290 kaya Trade-off mo. 455 00:24:30,290 --> 00:24:31,480 Oo? 456 00:24:31,480 --> 00:24:34,300 >> Madla: Gusto posible -set up ng try at pagkatapos ay 457 00:24:34,300 --> 00:24:37,967 sa sandaling mayroon ka ng lahat ng data sa loob nito na need-- mo 458 00:24:37,967 --> 00:24:39,550 Hindi ko alam kung na saysay. 459 00:24:39,550 --> 00:24:42,200 Nagsisimula ako ay mapupuksa ng lahat ng mga Null character, ngunit pagkatapos ay 460 00:24:42,200 --> 00:24:42,910 hindi mo magagawang i-index them-- 461 00:24:42,910 --> 00:24:43,275 >> Tagapagsalita 1: Kailangan mo pa rin ang mga ito. 462 00:24:43,275 --> 00:24:44,854 >> Madla: - sa parehong paraan sa bawat oras. 463 00:24:44,854 --> 00:24:45,520 Tagapagsalita 1: Oo. 464 00:24:45,520 --> 00:24:50,460 Kailangan mo ang null na character upang ipaalam alam mo kung mayroong hindi isang salita doon. 465 00:24:50,460 --> 00:24:52,040 Ben ay mayroon kang isang bagay na gusto mo? 466 00:24:52,040 --> 00:24:52,540 OK. 467 00:24:52,540 --> 00:24:54,581 Ang lahat ng mga karapatan, kaya kami ay pagpunta upang pumunta nang kaunti nang higit pa 468 00:24:54,581 --> 00:24:58,920 sa mga teknikal na detalye sa likod ng isang subukan at gumagana sa pamamagitan ng isang halimbawa. 469 00:24:58,920 --> 00:25:01,490 >> OK, kaya ito ay ang parehong bagay. 470 00:25:01,490 --> 00:25:06,290 Sapagkat sa isang naka-link na listahan, ang aming pangunahing uri of-- ano ang salita na gusto ko? - 471 00:25:06,290 --> 00:25:08,350 tulad ng pagbuo bloke ay isang node. 472 00:25:08,350 --> 00:25:12,280 Sa isang try, mayroon din kami ng isang node, ngunit ito ay tinukoy sa ibang paraan. 473 00:25:12,280 --> 00:25:17,000 >> Kaya mayroon kaming ilang bool na Kinakatawan kung ang isang salita talaga 474 00:25:17,000 --> 00:25:23,530 nang nasa lokasyong ito, at pagkatapos ay mayroon kaming ilang mga array here-- o sa halip, 475 00:25:23,530 --> 00:25:27,840 ito ay isang pointer sa isang array ng 27 mga character. 476 00:25:27,840 --> 00:25:33,339 At ito ay para sa, sa kasong ito, ito 27-- ako na ang lahat ng sa iyo ay tulad, maghintay, 477 00:25:33,339 --> 00:25:34,880 may 26 titik sa alpabeto. 478 00:25:34,880 --> 00:25:36,010 Bakit mayroon kaming 27? 479 00:25:36,010 --> 00:25:37,870 >> Kaya depende sa paraan mong ipatupad ito, 480 00:25:37,870 --> 00:25:43,240 ito ay mula sa isang pset na pinapayagan para sa kudlit. 481 00:25:43,240 --> 00:25:46,010 Kaya na ang dahilan kung bakit ang mga extrang isa. 482 00:25:46,010 --> 00:25:50,500 Magkakaroon ka rin sa ilang kaso ang null Terminator 483 00:25:50,500 --> 00:25:53,230 ay kasama bilang isa sa mga mga character na ito ay pinapahintulutan upang maging, 484 00:25:53,230 --> 00:25:56,120 at iyon ang kung paano sila suriin upang makita kung ito ay sa dulo ng salita. 485 00:25:56,120 --> 00:26:01,340 Kung interesado ka, tingnan ang Video Kevin sa study.cs50, 486 00:26:01,340 --> 00:26:04,790 pati na rin ang Wikipedia ay ang ilang mga mahusay na mga mapagkukunan doon. 487 00:26:04,790 --> 00:26:09,000 >> Ngunit kami ay pagpunta sa pumunta sa pamamagitan ng uri lamang ng kung paano mo maaaring gumana sa pamamagitan ng isang try 488 00:26:09,000 --> 00:26:11,010 kung bibigyan ka ng isa. 489 00:26:11,010 --> 00:26:16,230 Kaya mayroon kaming isang napaka-simpleng isa dito na May mga salitang "bat" at "pag-zoom" sa kanila. 490 00:26:16,230 --> 00:26:18,920 At tulad ng nakikita namin dito, ang maliit na espasyo dito 491 00:26:18,920 --> 00:26:22,560 Kinakatawan ng aming bool na sabi, oo, ito ay isang salita. 492 00:26:22,560 --> 00:26:27,060 At pagkatapos na ito ay ang aming array ng mga character, tama? 493 00:26:27,060 --> 00:26:33,480 >> Kaya kami ay pagpunta sa pumunta sa pamamagitan ng paghahanap ng "bat" sa try. 494 00:26:33,480 --> 00:26:38,340 Kaya magsimula sa itaas, tama? 495 00:26:38,340 --> 00:26:46,290 At alam namin na b tumutugon sa ang pangalawang index, ang pangalawang elemento 496 00:26:46,290 --> 00:26:47,840 sa array, dahil ang isang at b. 497 00:26:47,840 --> 00:26:51,340 Kaya humigit-kumulang sa ikalawang isa. 498 00:26:51,340 --> 00:26:58,820 >> At sinasabi nito, OK, cool, sundin na sa sa susunod na array, dahil kung tandaan namin, 499 00:26:58,820 --> 00:27:02,160 hindi ito ang bawat isa sa mga aktwal na naglalaman ng mga elemento. 500 00:27:02,160 --> 00:27:07,110 Ang bawat isa sa mga array ay naglalaman ng isang pointer, tama? 501 00:27:07,110 --> 00:27:10,030 Ito ay isang mahalagang pagkakaiba upang gumawa. 502 00:27:10,030 --> 00:27:13,450 >> Alam ko na ito ay pagpunta sa be-- pagsubok ay talagang mahirap upang makakuha ng sa unang pagkakataon, 503 00:27:13,450 --> 00:27:15,241 kaya kahit na ito ay ang pangalawa o pangatlong beses 504 00:27:15,241 --> 00:27:18,370 at ito ay uri pa rin ng tila mahirap, 505 00:27:18,370 --> 00:27:21,199 Nangangako ako kung pumunta ka sa panonood ang maikling muli bukas, 506 00:27:21,199 --> 00:27:22,740 Makikita ito marahil gumawa ng maraming higit pang mga kahulugan. 507 00:27:22,740 --> 00:27:23,890 Inaabot ng maraming upang digest. 508 00:27:23,890 --> 00:27:27,800 Ako minsan am pa rin tulad ng, maghintay, ano ay isang try? 509 00:27:27,800 --> 00:27:29,080 Paano ko gagamitin ito? 510 00:27:29,080 --> 00:27:33,880 >> Kaya namin b sa kasong ito, na kung saan ay ang aming ikalawang index. 511 00:27:33,880 --> 00:27:40,240 Kung nagkaroon kami, sabihin nating, c o d o anumang iba pang sulat, 512 00:27:40,240 --> 00:27:45,810 kailangan namin upang i-map na bumalik sa index sa aming mga array na na tumutugon sa. 513 00:27:45,810 --> 00:27:56,930 Kaya gusto naming maglaan tulad ng rchar at kami lamang ibawas-off ang isang upang i-map ito sa 0-25. 514 00:27:56,930 --> 00:27:58,728 Bawat tao magandang kung paano namin -map ang aming mga character? 515 00:27:58,728 --> 00:28:00,440 OK. 516 00:28:00,440 --> 00:28:05,980 >> Kaya pumunta kami sa ikalawang isa at kami makita na, oo, ito ay hindi na wasto. 517 00:28:05,980 --> 00:28:07,780 Maaari naming lumipat sa susunod na ito array. 518 00:28:07,780 --> 00:28:12,300 Kaya pumunta kami sa sa susunod na array dito. 519 00:28:12,300 --> 00:28:15,500 >> At sabihin namin, OK, ngayon namin Kailangan upang makita kung ang isang ay dito. 520 00:28:15,500 --> 00:28:18,590 Null ay A o ang ginagawa nito aktwal na sumulong? 521 00:28:18,590 --> 00:28:21,880 Kaya isang aktwal na gumagalaw ipasa sa array. 522 00:28:21,880 --> 00:28:24,570 At sabihin namin, OK, hindi ang ating huling titik. 523 00:28:24,570 --> 00:28:27,580 Kaya pumunta kami sa t sa index. 524 00:28:27,580 --> 00:28:30,120 At pagkatapos ay ilipat naming inaabangan ang panahon dahil mayroong isa pa. 525 00:28:30,120 --> 00:28:38,340 At ang isang ito talaga sabi na, oo, sinasabi nito na mayroong isang salita here-- 526 00:28:38,340 --> 00:28:41,750 na kung mong sundin ito landas, dumating ka pa 527 00:28:41,750 --> 00:28:43,210 sa isang salita, na alam namin ay "bat." 528 00:28:43,210 --> 00:28:43,800 Oo? 529 00:28:43,800 --> 00:28:46,770 >> Madla: ba ito standard na magkaroon na bilang index ng 0 at pagkatapos ay magkaroon ng isang pag-uuri sa 1 530 00:28:46,770 --> 00:28:47,660 o magkaroon ng sa dulo? 531 00:28:47,660 --> 00:28:48,243 >> Tagapagsalita 1: Hindi. 532 00:28:48,243 --> 00:28:55,360 Kaya't kung tiningnan namin pabalik sa aming mga pagpapahayag dito, ito ay isang bool, 533 00:28:55,360 --> 00:28:59,490 kaya sarili nitong sangkap sa iyong node. 534 00:28:59,490 --> 00:29:03,331 Kaya ito ay hindi bahagi ng array. 535 00:29:03,331 --> 00:29:03,830 Ayos. 536 00:29:03,830 --> 00:29:08,370 Kaya kapag tapos na kami sa aming mga salita at nagpapaumanhin kami sa ito array, kung ano ang gusto naming gawin 537 00:29:08,370 --> 00:29:12,807 ay gawin ang isang tseke para ay ito isang salita. 538 00:29:12,807 --> 00:29:14,390 At sa kasong ito, ito ay bumalik yes. 539 00:29:14,390 --> 00:29:17,220 540 00:29:17,220 --> 00:29:24,090 >> Kaya sa na tala, alam namin na "zoo" - alam namin bilang mga tao na "zoo" ay isang salita, 541 00:29:24,090 --> 00:29:24,820 tama? 542 00:29:24,820 --> 00:29:28,990 Ngunit subukan dito ay sabihin, hindi, hindi. 543 00:29:28,990 --> 00:29:33,980 At gusto itong sabihin na dahil namin hindi itinalaga ito bilang isang salita dito. 544 00:29:33,980 --> 00:29:40,440 Kahit na maaari naming bagtasin sa pamamagitan ng sa array, 545 00:29:40,440 --> 00:29:43,890 ito try ang sasabihin iyon, hindi, zoo ay wala sa iyong diksyunaryo 546 00:29:43,890 --> 00:29:47,070 dahil mayroon kaming hindi itinalaga ito bilang tulad. 547 00:29:47,070 --> 00:29:52,870 >> Kaya isang paraan upang gawin that-- naku, paumanhin, ang isang ito. 548 00:29:52,870 --> 00:29:59,450 Kaya sa kasong ito, "zoo" ay hindi isang salita, ngunit ito ay nasa aming try. 549 00:29:59,450 --> 00:30:05,690 Ngunit sa isang ito, sabihin natin na gusto namin ito ipakilala ang salitang "bath," kung ano ang mangyayari 550 00:30:05,690 --> 00:30:08,260 ay sinusunod namin ang through-- b, a, t. 551 00:30:08,260 --> 00:30:11,820 Humihingi kami sa array, at pumunta kami upang maghanap para sa h. 552 00:30:11,820 --> 00:30:15,220 >> Sa kasong ito, kapag namin tingnan ang pointer h, 553 00:30:15,220 --> 00:30:17,890 ito ay tumuturo sa null, OK? 554 00:30:17,890 --> 00:30:20,780 Kaya maliban kung ito ay hayagang na tumuturo sa isa pang array, 555 00:30:20,780 --> 00:30:25,000 ipagpalagay mo na ang lahat ng mga payo sa array ay tumuturo sa null. 556 00:30:25,000 --> 00:30:28,270 Kaya sa kasong ito, h nakaturo sa null kaya't hindi natin kailangang gawin, 557 00:30:28,270 --> 00:30:31,540 kaya ito ay bumalik din false, "bath" ay hindi in dito. 558 00:30:31,540 --> 00:30:34,102 559 00:30:34,102 --> 00:30:35,810 Kaya ngayon kami ay talagang pagpunta sa pumunta sa pamamagitan ng 560 00:30:35,810 --> 00:30:39,790 kung paano namin talagang sabihin na "zoo" ay nasa aming try. 561 00:30:39,790 --> 00:30:42,920 Paano kami magpasok ng "zoo" sa aming try? 562 00:30:42,920 --> 00:30:47,810 Kaya sa parehong paraan na aming pagsisimula sa ang aming listahan na naka-link, sisimulan namin sa root. 563 00:30:47,810 --> 00:30:50,600 Kapag may pagdududa, magsimula sa ang root ng mga bagay na ito. 564 00:30:50,600 --> 00:30:53,330 >> At kami sabihin, OK, z. 565 00:30:53,330 --> 00:30:55,650 z umiiral sa ito, at ginagawa nito. 566 00:30:55,650 --> 00:30:58,370 Kaya nagpapalipat-lipat ka sa sa ang inyong susunod na array, OK? 567 00:30:58,370 --> 00:31:01,482 At pagkatapos ay sa susunod na isa, sabihin namin, OK, umiiral o? 568 00:31:01,482 --> 00:31:03,000 Ginagawa nito. 569 00:31:03,000 --> 00:31:04,330 Ito muli. 570 00:31:04,330 --> 00:31:08,670 >> At kaya sa aming susunod na isa, na sinabi namin, OK, "zoo" Umiiral dito. 571 00:31:08,670 --> 00:31:12,440 Lahat ng kailangan naming gawin ay itakda ito katumbas sa totoo, na may isang salita doon. 572 00:31:12,440 --> 00:31:15,260 Kung si sinundan ang lahat ng bagay hanggang sa bago sa puntong iyon, 573 00:31:15,260 --> 00:31:17,030 ito ay isang salita, kaya lamang itakda ito katumbas ng tulad. 574 00:31:17,030 --> 00:31:17,530 Oo? 575 00:31:17,530 --> 00:31:22,550 >> Madla: ang Kaya pagkatapos na nangangahulugan na "BA" ay salita rin? 576 00:31:22,550 --> 00:31:24,120 >> Tagapagsalita 1: Hindi. 577 00:31:24,120 --> 00:31:28,870 Kaya sa kasong ito, ang "BA" naming makakuha ng dito, gusto naming sabihin ay ito ang isang salita, 578 00:31:28,870 --> 00:31:31,590 at ito ay pa rin walang. 579 00:31:31,590 --> 00:31:32,822 OK? 580 00:31:32,822 --> 00:31:33,740 Mmhmm? 581 00:31:33,740 --> 00:31:36,360 >> Madla: Kaya sa sandaling ito ng salita at sabihin ninyo ang oo, pagkatapos ito 582 00:31:36,360 --> 00:31:38,380 Maglalaman upang pumunta sa m? 583 00:31:38,380 --> 00:31:42,260 >> Tagapagsalita 1: Kaya ito ay may upang gawin with-- ka sa paglo-load ito sa. 584 00:31:42,260 --> 00:31:43,640 Sinabi mo ang "zoo" ay salita. 585 00:31:43,640 --> 00:31:47,020 Kapag pumunta ka sa check-- tulad ng, sabihin nating nais mong sabihin, 586 00:31:47,020 --> 00:31:49,400 ang "zoo" umiiral sa diksyunaryo ito? 587 00:31:49,400 --> 00:31:54,200 Ka lamang ng pagpunta sa paghahanap para sa "zoo," at pagkatapos ay suriin upang makita kung ito ay isang salita. 588 00:31:54,200 --> 00:31:57,291 Hindi ka pagpunta sa ilipat sa pamamagitan ng m dahil hindi iyon 589 00:31:57,291 --> 00:31:58,290 kung ano ang iyong hinahanap. 590 00:31:58,290 --> 00:32:02,690 591 00:32:02,690 --> 00:32:08,070 >> Kaya kung talagang namin nais na idagdag ang "bath" sa ito try, 592 00:32:08,070 --> 00:32:11,390 Gusto naming gawin ang parehong bagay tulad ng ginawa namin sa "zoo," 593 00:32:11,390 --> 00:32:15,380 maliban gusto naming makita na kapag namin subukan at makapunta sa h, ito ay hindi umiiral. 594 00:32:15,380 --> 00:32:20,090 Kaya maaari mong isipin na ito bilang pagsubok upang magdagdag ng bagong node sa isang naka-link na listahan, 595 00:32:20,090 --> 00:32:27,210 kaya gusto naming kailangan upang magdagdag ng isa pang ang isa sa mga array, tulad ng sa gayon. 596 00:32:27,210 --> 00:32:35,670 At pagkatapos ay kung ano ang namin ang naka-set lang namin ang h elemento ng array na tumuturo sa ito. 597 00:32:35,670 --> 00:32:39,430 >> At pagkatapos ay kung ano ang gusto naming gawin dito? 598 00:32:39,430 --> 00:32:43,110 Idagdag ito katumbas ng totoo dahil ito ay isang salita. 599 00:32:43,110 --> 00:32:46,350 600 00:32:46,350 --> 00:32:48,150 Ayos. 601 00:32:48,150 --> 00:32:48,700 Alam ko. 602 00:32:48,700 --> 00:32:51,170 Pagsubok ay hindi ang pinaka-kapana-panabik. 603 00:32:51,170 --> 00:32:54,250 Pagkatiwalaan sa akin, alam ko. 604 00:32:54,250 --> 00:32:58,040 >> Kaya isang bagay upang mapagtanto na may pagsubok, Sinabi ko, ang mga ito ay napaka-epektibo. 605 00:32:58,040 --> 00:33:00,080 Kaya nakita namin ang mga ito tumagal nang hanggang isang tonelada ng espasyo. 606 00:33:00,080 --> 00:33:01,370 Ang mga ito ay uri ng nakalilito. 607 00:33:01,370 --> 00:33:03,367 Kaya bakit namin kailanman gamitin ang mga ito? 608 00:33:03,367 --> 00:33:05,450 Ginagamit namin ang mga dahil ang mga ito ay hindi mapaniniwalaan o kapani-paniwala mahusay. 609 00:33:05,450 --> 00:33:08,130 >> Kaya kung sakaling ang iyong hinahanap up ng isang salita, ikaw lamang 610 00:33:08,130 --> 00:33:10,450 bounded sa pamamagitan ng haba ng salita. 611 00:33:10,450 --> 00:33:15,210 Kaya kung naghahanap ka para sa isang salita na haba ng limang, 612 00:33:15,210 --> 00:33:20,940 ka kailanman lamang ng pagpunta sa mayroon sa gumawa ng hindi hihigit sa limang mga paghahambing, OK? 613 00:33:20,940 --> 00:33:25,780 Kaya ginagawang ito isa lamang pare-pareho. 614 00:33:25,780 --> 00:33:29,150 Tulad ng pagpapasok at lookup ay isa lamang pare-pareho ang oras. 615 00:33:29,150 --> 00:33:33,750 >> Kaya kung maaari kang makakuha ng kailanman isang bagay sa pare-pareho ang oras, 616 00:33:33,750 --> 00:33:35,150 na kasing ganda ng ito ay nakakakuha. 617 00:33:35,150 --> 00:33:37,990 Hindi ka maaaring makakuha ng mas mahusay kaysa sa pare-pareho ang oras para sa mga bagay na ito. 618 00:33:37,990 --> 00:33:43,150 Kaya na ay isa sa mga malaking plus ng pagsubok. 619 00:33:43,150 --> 00:33:46,780 >> Ngunit ito ay isang maraming espasyo. 620 00:33:46,780 --> 00:33:50,380 Kaya mo uri ng kailangang magpasya kung ano ang mas mahalaga sa iyo. 621 00:33:50,380 --> 00:33:54,700 At sa mga computer ngayon, ang puwang na iyon ng try maaaring tumagal ng hanggang 622 00:33:54,700 --> 00:33:57,740 siguro ay hindi nakakaapekto sa iyo na magkano, ngunit marahil 623 00:33:57,740 --> 00:34:01,350 ka pagharap sa isang bagay na may malayo, malayo higit pang mga bagay, 624 00:34:01,350 --> 00:34:02,810 at isang try lang ay hindi makatwirang. 625 00:34:02,810 --> 00:34:03,000 Oo? 626 00:34:03,000 --> 00:34:05,610 >> Madla: Maghintay, kaya mayroon kang 26 mga titik sa bawat solong isa? 627 00:34:05,610 --> 00:34:07,440 >> Tagapagsalita 1: Mmhmm. 628 00:34:07,440 --> 00:34:08,570 Oo, mayroon kang 26. 629 00:34:08,570 --> 00:34:16,984 Mayroon kang ilang mga marker ay salita at pagkatapos ay mayroon kang 26 na pointer sa bawat isa. 630 00:34:16,984 --> 00:34:17,775 At sila ay point-- 631 00:34:17,775 --> 00:34:20,280 >> Madla: At sa bawat 26, ang mga ito ay may 26? 632 00:34:20,280 --> 00:34:21,500 >> Tagapagsalita 1: Oo. 633 00:34:21,500 --> 00:34:27,460 At iyon ang dahilan kung bakit, bilang maaari mong makita, ito ang lilitaw pa masyadong mabilis. 634 00:34:27,460 --> 00:34:28,130 Lahat ng karapatan. 635 00:34:28,130 --> 00:34:32,524 Kaya kami ay pagpunta upang makakuha ng sa mga puno, na Sa palagay ko ay mas madali at magpo marahil 636 00:34:32,524 --> 00:34:36,150 maging isang magandang maliit na ipagpaliban ang pagbitay mula sa pagsubok doon. 637 00:34:36,150 --> 00:34:39,620 Kaya sana karamihan sa iyo nakakita ng isang puno bago. 638 00:34:39,620 --> 00:34:41,820 Hindi gusto ng mga kaakit-akit mga nasa labas, na aking 639 00:34:41,820 --> 00:34:44,340 hindi alam kung sinuman nagpunta labas kamakailan. 640 00:34:44,340 --> 00:34:49,230 Nagpunta ako sa pagpili ng mansanas na ito katapusan ng linggo, at oh aking sus, ito ay maganda. 641 00:34:49,230 --> 00:34:52,250 Hindi ko alam kung dahon maaaring tumingin na kaakit-akit. 642 00:34:52,250 --> 00:34:53,610 >> Kaya ito ay isang puno lamang, tama? 643 00:34:53,610 --> 00:34:56,790 Ito ay ilan lang na node, at ito tumuturo sa isang bungkos ng iba pang mga node. 644 00:34:56,790 --> 00:34:59,570 Tulad ng iyong nakikita dito, ito ay uri ng isang umuulit na tema. 645 00:34:59,570 --> 00:35:03,720 Node pagturo sa node ay uri ng ang kakanyahan ng maraming mga istraktura ng data. 646 00:35:03,720 --> 00:35:06,670 Depende lang ito sa kung paano namin Mayroon ituro ang mga ito sa isa't isa 647 00:35:06,670 --> 00:35:08,600 at kung paano namin tumawid sa pamamagitan ng mga ito at kung paano namin 648 00:35:08,600 --> 00:35:14,500 magpasok ng mga bagay na tinutukoy ang kanilang mga iba't ibang mga katangian. 649 00:35:14,500 --> 00:35:17,600 >> Kaya ilan lang terminolohiya, na ginagamit ko na dati. 650 00:35:17,600 --> 00:35:20,010 Kaya ugat ay anumang ay nasa tuktok napaka. 651 00:35:20,010 --> 00:35:21,200 ito ay kung saan palagi naming magsimula. 652 00:35:21,200 --> 00:35:23,610 Maaari mong isipin na ito bilang pinuno rin. 653 00:35:23,610 --> 00:35:28,750 Ngunit para sa mga puno, may posibilidad namin upang sumangguni sa ito bilang root. 654 00:35:28,750 --> 00:35:32,820 >> Anumang bagay sa ilalim here-- sa pinakadulo, napaka-bottom-- 655 00:35:32,820 --> 00:35:34,500 ay itinuturing na dahon. 656 00:35:34,500 --> 00:35:37,210 Kaya mangyaring hindi kasama ang buong puno bagay, tama? 657 00:35:37,210 --> 00:35:39,860 Dahon ay nasa gilid ng iyong tree. 658 00:35:39,860 --> 00:35:45,820 >> At pagkatapos ay mayroon din kami ng ilang mga mga termino upang makipag-usap tungkol sa mga node na may kaugnayan 659 00:35:45,820 --> 00:35:46,680 sa isa't isa. 660 00:35:46,680 --> 00:35:49,700 Kaya mayroon kaming magulang, mga anak, at kapatid. 661 00:35:49,700 --> 00:35:56,260 Kaya sa kasong ito, 3 ay ang magulang ng 5, 6, at 7. 662 00:35:56,260 --> 00:36:00,370 Kaya ang magulang ay anumang ay isang hakbang sa itaas ng kahit anupamang ikaw ay 663 00:36:00,370 --> 00:36:02,940 nagre-refer sa, kaya lamang tulad ng isang pamilya tree. 664 00:36:02,940 --> 00:36:07,090 Sana, ito ay ang lahat ng kaunti bit mas magaling kaysa sa pagsubok. 665 00:36:07,090 --> 00:36:10,970 >> Kapatid ay ang anuman na mayroon ang parehong magulang, tama? 666 00:36:10,970 --> 00:36:13,470 Ang mga ito ay nasa parehong antas dito. 667 00:36:13,470 --> 00:36:16,960 At pagkatapos, bilang ako ay sinasabi, ang mga bata ay lamang 668 00:36:16,960 --> 00:36:22,630 anumang ay isang hakbang sa ibaba ang node na pinag-uusapan, OK? 669 00:36:22,630 --> 00:36:23,470 Ayos. 670 00:36:23,470 --> 00:36:25,610 Kaya isang binary tree. 671 00:36:25,610 --> 00:36:31,450 Maaari sinuman Hazard ng hula sa isa sa ang mga katangian ng binary puno? 672 00:36:31,450 --> 00:36:32,770 >> Madla: Max dalawang dahon. 673 00:36:32,770 --> 00:36:33,478 >> Tagapagsalita 1: I-right. 674 00:36:33,478 --> 00:36:34,640 Kaya max ng dalawang dahon. 675 00:36:34,640 --> 00:36:39,730 Kaya sa isang ito bago, nagkaroon kami ng isang ito na nagkaroon ng tatlong, ngunit sa isang binary puno, 676 00:36:39,730 --> 00:36:45,000 mayroon kang isang max ng dalawang mga bata sa bawat magulang, tama? 677 00:36:45,000 --> 00:36:46,970 Mayroong isa pang kagiliw-giliw na katangian. 678 00:36:46,970 --> 00:36:51,550 Sinuman Alam ba iyon? 679 00:36:51,550 --> 00:36:52,620 Binary tree. 680 00:36:52,620 --> 00:37:00,350 >> Kaya isang binary puno ay magkakaroon ng lahat ng bagay sa the-- ang isang ito ay hindi sorted-- 681 00:37:00,350 --> 00:37:05,320 ngunit sa isang pinagsunod-sunod binary tree, lahat ng bagay sa kanan 682 00:37:05,320 --> 00:37:08,530 ay mas malaki sa magulang, at lahat ng nasa kaliwa 683 00:37:08,530 --> 00:37:10,035 ay mas mababa sa magulang. 684 00:37:10,035 --> 00:37:15,690 At iyon ay isang pagsusulit tanong bago, kaya magandang malaman. 685 00:37:15,690 --> 00:37:19,500 Kaya ang paraan tukuyin namin ito, muli, mayroon kaming isa pang node. 686 00:37:19,500 --> 00:37:21,880 Ito ay mukhang katulad na katulad sa kung ano? 687 00:37:21,880 --> 00:37:28,336 688 00:37:28,336 --> 00:37:28,836 Doble 689 00:37:28,836 --> 00:37:29,320 >> Madla: Naka-link na mga listahan 690 00:37:29,320 --> 00:37:31,100 >> Tagapagsalita 1: Isang double naka-link na listahan, i-right? 691 00:37:31,100 --> 00:37:33,690 Kaya kung papalitan namin ito sa nakaraan at susunod, 692 00:37:33,690 --> 00:37:35,670 ito ay magiging isang doble naka-link na listahan. 693 00:37:35,670 --> 00:37:40,125 Ngunit sa kasong ito, kami talaga Mayroon pakaliwa at pakanan at iyon ito. 694 00:37:40,125 --> 00:37:41,500 Kung hindi man, ito ay eksaktong kapareho. 695 00:37:41,500 --> 00:37:43,374 Mayroon pa kaming mga elemento hinahanap mo, 696 00:37:43,374 --> 00:37:45,988 at mayroon kang lamang ng dalawang mga payo pagpunta sa kahit anong susunod. 697 00:37:45,988 --> 00:37:49,210 698 00:37:49,210 --> 00:37:51,870 Oo, kaya binary paghahanap tree. 699 00:37:51,870 --> 00:37:57,665 Kung napansin namin, lahat ng bagay sa dito mismo ay mas malaki than-- 700 00:37:57,665 --> 00:37:59,850 o lahat agad sa kanan dito 701 00:37:59,850 --> 00:38:02,840 ay mas malaki kaysa sa, lahat ng bagay dito ay mas mababa. 702 00:38:02,840 --> 00:38:06,980 703 00:38:06,980 --> 00:38:14,000 >> Kaya kung kami ay upang maghanap sa pamamagitan ng, ito dapat mukhang masyado nang malapit sa binary paghahanap 704 00:38:14,000 --> 00:38:14,910 dito, tama? 705 00:38:14,910 --> 00:38:17,640 Maliban sa halip na naghahanap sa kalahati ng array, 706 00:38:17,640 --> 00:38:21,720 kami ay lamang ng pagtingin sa alinman sa kaliwa gilid o sa kanang bahagi ng tree. 707 00:38:21,720 --> 00:38:24,850 Kaya ito ay nakakakuha ng kaunti mas simple, sa tingin ko. 708 00:38:24,850 --> 00:38:29,300 >> Kaya kung ang iyong mga ugat ay null, Malinaw na ito ay hindi totoo lang. 709 00:38:29,300 --> 00:38:33,470 At kung ito ay doon, malinaw naman ito totoo. 710 00:38:33,470 --> 00:38:35,320 Kung ito ay mas mababa, maghanap namin sa kaliwa. 711 00:38:35,320 --> 00:38:37,070 Kung ito ay mas malaki kaysa sa, maghanap namin ang karapatan. 712 00:38:37,070 --> 00:38:39,890 Ito ay eksakto tulad ng binary paghahanap, lamang ng ibang istraktura ng data 713 00:38:39,890 --> 00:38:40,600 na ginagamit namin. 714 00:38:40,600 --> 00:38:42,790 Sa halip na isang array, ito lamang ay isang binary tree. 715 00:38:42,790 --> 00:38:45,820 716 00:38:45,820 --> 00:38:48,090 >> OK, stack. 717 00:38:48,090 --> 00:38:51,550 At din, mukhang namin Maaaring magkaroon ng kaunting oras. 718 00:38:51,550 --> 00:38:54,460 Kung gagawin namin, Ikinagagalak kong pumunta sa paglipas ng alinman sa mga ito muli. 719 00:38:54,460 --> 00:38:56,856 OK, kaya stack. 720 00:38:56,856 --> 00:39:02,695 Sinuman tandaan ba kung ano stacks-- anumang mga katangian ng isang stack? 721 00:39:02,695 --> 00:39:05,550 722 00:39:05,550 --> 00:39:10,400 >> OK, kaya ang karamihan sa atin, sa palagay ko, kumain sa dining halls-- 723 00:39:10,400 --> 00:39:13,100 hangga't maaaring hindi namin nais na. 724 00:39:13,100 --> 00:39:16,900 Ngunit malinaw naman, maaari mong isipin ang isang stack Literal na lamang bilang isang stack ng mga trays 725 00:39:16,900 --> 00:39:18,460 o isang stack ng mga bagay. 726 00:39:18,460 --> 00:39:21,820 At kung ano ang mahalaga upang mapagtanto ay na ito 727 00:39:21,820 --> 00:39:26,850 something-- ang katangian na tinatawag namin itong by-- ay LIFO. 728 00:39:26,850 --> 00:39:28,450 Sinuman Alam ba kung ano na ang ibig sabihin ay? 729 00:39:28,450 --> 00:39:29,070 Mmhmm? 730 00:39:29,070 --> 00:39:30,650 >> Madla: Huling in, unang out. 731 00:39:30,650 --> 00:39:32,250 >> Tagapagsalita 1: I-right, tatagal sa, out muna. 732 00:39:32,250 --> 00:39:36,585 Kaya kung alam namin, kung kami ay stacking bagay up, ang pinakamadaling bagay upang grab off-- 733 00:39:36,585 --> 00:39:39,570 at marahil ang tanging bagay na maaari naming grab -off kung ang aming stack ay malaki enough-- 734 00:39:39,570 --> 00:39:40,850 ay ang nangungunang elemento. 735 00:39:40,850 --> 00:39:43,460 Kaya kahit anong ay ilagay sa last-- tulad ng nakikita namin dito, 736 00:39:43,460 --> 00:39:46,370 anumang ay hunhon sa karamihan ng mga recently-- ay 737 00:39:46,370 --> 00:39:51,160 pagpunta sa maging una bagay na pop-off namin, OK? 738 00:39:51,160 --> 00:39:56,324 >> Kaya kung ano ang mayroon kami dito ay isa pang typedef struct. 739 00:39:56,324 --> 00:39:58,740 Ito ay talagang gusto lamang Siyempre crash sa istraktura ng data, 740 00:39:58,740 --> 00:40:01,650 kaya maraming itinapon sa iyo guys. 741 00:40:01,650 --> 00:40:02,540 Alam ko. 742 00:40:02,540 --> 00:40:04,970 Kaya isa pang struct. 743 00:40:04,970 --> 00:40:06,740 Ayos para sa mga istraktura. 744 00:40:06,740 --> 00:40:16,660 >> At sa kasong ito, ito ang ilang pointer sa isang array na may ilang mga kapasidad. 745 00:40:16,660 --> 00:40:20,830 Kaya ito ay kumakatawan sa aming mga stack dito, tulad ng ating mga aktwal na array 746 00:40:20,830 --> 00:40:22,520 na may hawak na aming elemento. 747 00:40:22,520 --> 00:40:24,850 At pagkatapos dito mayroon kaming ilang mga laki. 748 00:40:24,850 --> 00:40:31,170 >> At karaniwan, ang gusto mong panatilihing track ng kung gaano kalaki ang iyong stack ay 749 00:40:31,170 --> 00:40:36,180 dahil kung ano ang pagpunta sa payagan mo lang gawin ay kung alam mo ang laki, 750 00:40:36,180 --> 00:40:39,170 Nagbibigay-daan ito sa iyo na sabihin, OK, ako sa kapasidad? 751 00:40:39,170 --> 00:40:40,570 Maaari ba akong magdagdag ng ano pa? 752 00:40:40,570 --> 00:40:44,650 At nagsasabi rin ito sa iyo kung saan sa tuktok ng iyong stack 753 00:40:44,650 --> 00:40:48,180 ay gayon alam mo kung ano ang Maaari aktwal na lumipad. 754 00:40:48,180 --> 00:40:51,760 At na aktwal na pagpunta sa maging isang maliit na mas malinaw dito. 755 00:40:51,760 --> 00:40:57,350 >> Kaya para sa push, isang bagay, kung ay kailanman upang ipatupad ang push, 756 00:40:57,350 --> 00:41:01,330 tulad ng ako ay sinasabi, ang iyong stack ay may limitadong laki, tama? 757 00:41:01,330 --> 00:41:03,990 Ang aming mga array ay may ilang mga kapasidad. 758 00:41:03,990 --> 00:41:04,910 Ito ay isang array. 759 00:41:04,910 --> 00:41:08,930 Ito ay isang nakapirming laki, kaya kailangan namin upang tiyakin na hindi kami naglalagay ka ng higit pa 760 00:41:08,930 --> 00:41:11,950 sa aming array kaysa namin talaga may espasyo para sa. 761 00:41:11,950 --> 00:41:16,900 >> Kaya kapag lumilikha ka ng isang push function, ang unang bagay na ginawa mo ay sabihin nating, OK, 762 00:41:16,900 --> 00:41:18,570 ang mayroon ako espasyo sa aking stack? 763 00:41:18,570 --> 00:41:23,330 Dahil kung gagawin ko hindi, paumanhin, Hindi ko ma-imbak ang iyong mga elemento. 764 00:41:23,330 --> 00:41:28,980 Kung gagawin ko, pagkatapos ay nais mong iimbak ito sa tuktok ng stack, tama? 765 00:41:28,980 --> 00:41:31,325 >> At ito ang dahilan kung bakit mayroon kaming upang masubaybayan ang aming laki. 766 00:41:31,325 --> 00:41:35,290 Kung hindi namin masubaybayan ang aming mga sukat, hindi namin alam kung saan upang ilagay ito. 767 00:41:35,290 --> 00:41:39,035 Hindi namin alam kung gaano karaming mga bagay ay nasa aming array na. 768 00:41:39,035 --> 00:41:41,410 Tulad ng malinaw naman may mga paraan na siguro maaari mong gawin ito. 769 00:41:41,410 --> 00:41:44,610 Maaari mong simulan ang lahat ng bagay sa null at pagkatapos suriin para sa pinakabagong null, 770 00:41:44,610 --> 00:41:47,950 ngunit isang mas madaling bagay lamang sasabihin, OK, subaybayan ang laki. 771 00:41:47,950 --> 00:41:51,840 Tulad ng alam ko Mayroon akong apat na mga elemento sa aking array, kaya ang susunod na bagay 772 00:41:51,840 --> 00:41:55,930 na inilalagay namin sa, kami ay pagpunta upang mag-imbak sa index 4. 773 00:41:55,930 --> 00:42:00,940 At pagkatapos ay, siyempre, nangangahulugan ito na matagumpay mong na-hunhon isang bagay 774 00:42:00,940 --> 00:42:03,320 papunta sa iyong stack, mo nais na dagdagan ang laki 775 00:42:03,320 --> 00:42:08,880 kaya na alam mo kung nasaan ka kaya na maaari mong itulak higit pang mga bagay sa. 776 00:42:08,880 --> 00:42:12,730 >> Kaya kung namin na sinusubukan mong i-pop isang bagay off ang stack, 777 00:42:12,730 --> 00:42:16,072 kung ano ang maaaring maging unang bagay na gusto naming suriin para sa? 778 00:42:16,072 --> 00:42:18,030 Sinusubukan mong gumawa ng isang bagay off ang iyong stack. 779 00:42:18,030 --> 00:42:21,710 780 00:42:21,710 --> 00:42:24,781 Sigurado ka bang mayroong isang bagay sa iyong stack? 781 00:42:24,781 --> 00:42:25,280 Hindi. 782 00:42:25,280 --> 00:42:26,894 Kaya kung ano ang maaaring gusto naming suriin? 783 00:42:26,894 --> 00:42:27,810 >> Madla: [hindi marinig]. 784 00:42:27,810 --> 00:42:29,880 Tagapagsalita 1: I-check para sa laki? 785 00:42:29,880 --> 00:42:31,840 Laki. 786 00:42:31,840 --> 00:42:38,520 Kaya gusto naming suriin upang makita kung ang aming laki ay mas malaki kaysa sa 0, OK? 787 00:42:38,520 --> 00:42:44,970 At kung ito ay, pagkatapos ay nais naming bawasan ang aming laki sa pamamagitan ng 0 at ibalik iyon. 788 00:42:44,970 --> 00:42:45,840 Bakit? 789 00:42:45,840 --> 00:42:49,950 >> Sa unang isa namin panunulak, matutulak namin ito 790 00:42:49,950 --> 00:42:52,460 sa laki at pagkatapos ay i-update ang laki. 791 00:42:52,460 --> 00:42:57,850 Sa kasong ito, kami ay decrementing laki at pagkatapos ay pagkuha off ito, plucking ito 792 00:42:57,850 --> 00:42:58,952 mula sa aming mga array. 793 00:42:58,952 --> 00:42:59,826 Bakit maaaring gawin namin iyon? 794 00:42:59,826 --> 00:43:04,800 795 00:43:04,800 --> 00:43:11,811 Kaya kung mayroon akong isang bagay sa aking stack, kung ano ang magiging aking mga laki sa puntong iyon? 796 00:43:11,811 --> 00:43:13,140 1. 797 00:43:13,140 --> 00:43:15,180 >> At kung saan ay elemento 1 na naka-imbak? 798 00:43:15,180 --> 00:43:17,621 Sa anong index? 799 00:43:17,621 --> 00:43:18,120 Madla: 0. 800 00:43:18,120 --> 00:43:19,060 Tagapagsalita 1: 0. 801 00:43:19,060 --> 00:43:22,800 Kaya sa kasong ito, kami laging kailangan upang gumawa ng sure-- 802 00:43:22,800 --> 00:43:27,630 sa halip ng pagbabalik laki ng minus 1, dahil kami 803 00:43:27,630 --> 00:43:31,730 alam na ang aming elemento ay pagpunta sa ay naka-imbak sa 1 mas mababa 804 00:43:31,730 --> 00:43:34,705 anumang aming laki ay, ito lamang tumatagal ng pag-aalaga ng mga ito. 805 00:43:34,705 --> 00:43:36,080 Ito ay isang bahagyang higit pa eleganteng paraan. 806 00:43:36,080 --> 00:43:41,220 At pagbawas lamang namin ang aming laki at pagkatapos ay bumalik ang laki. 807 00:43:41,220 --> 00:43:42,330 Mmhmm? 808 00:43:42,330 --> 00:43:45,300 >> Madla: hulaan ko pa lang sa pangkalahatan, bakit gagawin ito istraktura ng data 809 00:43:45,300 --> 00:43:47,800 maging kapaki-pakinabang? 810 00:43:47,800 --> 00:43:50,660 >> Tagapagsalita 1: Depende ito sa iyong konteksto. 811 00:43:50,660 --> 00:43:57,420 Kaya para sa ilan sa mga teorya, kung nagtatrabaho ka with-- OK, 812 00:43:57,420 --> 00:44:02,750 hayaan mo akong makita kung mayroong ay isang kapaki-pakinabang na kapaki-pakinabang sa higit pa sa labas 813 00:44:02,750 --> 00:44:05,420 ng CS. 814 00:44:05,420 --> 00:44:15,780 Sa stack, anumang oras na kailangan mo upang subaybayan ang mga bagay na 815 00:44:15,780 --> 00:44:20,456 ay ang pinaka-kamakailang idinagdag ay kapag ka ng pagpunta sa nais na gumamit ng stack. 816 00:44:20,456 --> 00:44:24,770 >> At hindi ako makapag-isip ng isang magandang halimbawa ng na ngayon. 817 00:44:24,770 --> 00:44:29,955 Ngunit sa tuwing ang pinakabagong bagay ay pinakamahalaga sa iyo, 818 00:44:29,955 --> 00:44:31,705 na kapag ang isang stack ay magiging kapaki-pakinabang. 819 00:44:31,705 --> 00:44:35,797 820 00:44:35,797 --> 00:44:39,330 Sinusubukan kong mag-isip kung mayroong isang magandang isa para sa ito. 821 00:44:39,330 --> 00:44:43,720 Kung sa tingin ko ng isang magandang halimbawa sa susunod na 20 minuto, talagang ay ko bang sabihin sa iyo. 822 00:44:43,720 --> 00:44:49,455 >> Ngunit sa pangkalahatan, kung mayroong anumang bagay, tulad ng sinabi ko sa karamihan, kung saan ang pinaka-kamakailang 823 00:44:49,455 --> 00:44:52,470 ang pinaka-mahalaga, na kung saan isang stack ay sa pag-play. 824 00:44:52,470 --> 00:44:58,860 Sapagkat ang queues ay uri ng ng kabaligtaran. 825 00:44:58,860 --> 00:44:59,870 At ang lahat ng mga maliit na aso. 826 00:44:59,870 --> 00:45:00,890 Ay hindi ito mahusay na, tama? 827 00:45:00,890 --> 00:45:03,299 Nararamdaman kong dapat kong mayroon lamang isang kuneho video 828 00:45:03,299 --> 00:45:05,090 karapatan sa gitna ng na seksyon para sa iyo guys 829 00:45:05,090 --> 00:45:08,870 dahil ito ay isang malakas na seksyon. 830 00:45:08,870 --> 00:45:10,480 >> Kaya isang queue. 831 00:45:10,480 --> 00:45:12,710 Isa lamang queue ay tulad ng isang linya. 832 00:45:12,710 --> 00:45:15,780 Ikaw guys ako bang gamitin ang araw-araw, gusto lang sa aming dining hall. 833 00:45:15,780 --> 00:45:18,160 Kaya mayroon kaming upang pumunta sa at kumuha ng aming mga trays, ako ay 834 00:45:18,160 --> 00:45:21,260 Tiyaking mayroon kang maghintay sa linya upang mag-swipe o kunin ang iyong pagkain. 835 00:45:21,260 --> 00:45:24,650 >> Kaya ang pagkakaiba dito ay na ito ay FIFO. 836 00:45:24,650 --> 00:45:30,090 Kaya kung huling sa LIFO ay, unang out, FIFO unang in, unang out. 837 00:45:30,090 --> 00:45:33,400 Kaya ito ay kung saan ang anumang ilagay mo sa una ay ang iyong pinakamahalagang. 838 00:45:33,400 --> 00:45:35,540 Kaya kung ikaw ay naghihintay sa isang line-- maaari kang 839 00:45:35,540 --> 00:45:39,130 isipin kung napunta ka sa pumunta makuha ang bagong iPhone 840 00:45:39,130 --> 00:45:42,800 at ito ay isang stack na kung saan ang nakuha ko huling tao sa linya una, 841 00:45:42,800 --> 00:45:44,160 mga tao na gusto pumatay sa bawat isa. 842 00:45:44,160 --> 00:45:49,800 >> Kaya FIFO, hindi namin ang lahat ng masyadong pamilyar may sa tunay na mundo dito, 843 00:45:49,800 --> 00:45:54,930 at ang lahat ng ito ay gagawin sa aktwal uri ng nililikha ang buong linya 844 00:45:54,930 --> 00:45:56,900 at queuing istraktura. 845 00:45:56,900 --> 00:46:02,390 Kaya samantalang may stack, mayroon kaming push at mga pop. 846 00:46:02,390 --> 00:46:06,440 Sa isang pila, mayroon kaming I-enqueue at dequeue. 847 00:46:06,440 --> 00:46:10,910 Kaya I-enqueue talaga ang ibig sabihin ilagay ito sa likod, 848 00:46:10,910 --> 00:46:13,680 at dequeue paraan tumagal -off mula sa front. 849 00:46:13,680 --> 00:46:18,680 Kaya aming mga istraktura ng data ay isang Medyo higit pang kumplikado. 850 00:46:18,680 --> 00:46:21,060 Mayroon kaming ikalawang bagay upang masubaybayan. 851 00:46:21,060 --> 00:46:25,950 >> Kaya walang ulo, ito ay eksaktong isang stack, tama? 852 00:46:25,950 --> 00:46:27,900 Ito ay ang parehong istraktura bilang isang stack. 853 00:46:27,900 --> 00:46:32,480 Ang tanging bagay ibang ngayon ay namin may ito ulo, na kung ano sa tingin mo 854 00:46:32,480 --> 00:46:34,272 Mawawala upang masubaybayan? 855 00:46:34,272 --> 00:46:35,510 >> Madla: Ang una. 856 00:46:35,510 --> 00:46:38,685 >> Tagapagsalita 1: I-right, ang unang bagay na aming inilagay sa. 857 00:46:38,685 --> 00:46:41,130 Ang ulo ng aming queue. 858 00:46:41,130 --> 00:46:42,240 Sinumang unang nasa linya. 859 00:46:42,240 --> 00:46:45,300 860 00:46:45,300 --> 00:46:49,420 Ang lahat ng mga karapatan, kaya kung gawin namin enqueue. 861 00:46:49,420 --> 00:46:52,720 862 00:46:52,720 --> 00:46:55,920 Muli, gamit ang alinman sa mga kayarian ng data, 863 00:46:55,920 --> 00:46:59,760 dahil kami ay pagharap sa isang array, kailangan namin upang suriin kung mayroon kaming espasyo. 864 00:46:59,760 --> 00:47:03,290 >> Ito ay uri ng tulad ng sa akin na nagsasabi mo guys, kung nagbukas ka ng isang file, 865 00:47:03,290 --> 00:47:04,760 kailangan mong i-check para sa null. 866 00:47:04,760 --> 00:47:08,330 Gamit ang anuman sa mga stack at queues, kailangan mong 867 00:47:08,330 --> 00:47:13,420 upang makita kung mayroong espasyo dahil kami pagharap sa isang nakapirming laki ng array, 868 00:47:13,420 --> 00:47:16,030 tulad ng nakikita namin here-- 0, 1 lahat ng hanggang 5. 869 00:47:16,030 --> 00:47:20,690 Kaya kung ano ang ginagawa namin sa kasong iyon ay check upang makita kung mayroon pa rin kaming espasyo. 870 00:47:20,690 --> 00:47:23,110 Ay ang aming laki mas mababa sa kapasidad? 871 00:47:23,110 --> 00:47:28,480 >> Kung gayon, kailangan namin upang mag-imbak ito sa ang buntot at i-update namin ang aming laki. 872 00:47:28,480 --> 00:47:30,250 Kaya kung ano ang maaaring ang buntot na sa kasong ito? 873 00:47:30,250 --> 00:47:32,360 Ito ay hindi tahasang nakasulat out. 874 00:47:32,360 --> 00:47:33,380 Paano namin iimbak ito? 875 00:47:33,380 --> 00:47:34,928 Ano ang magiging buntot? 876 00:47:34,928 --> 00:47:38,600 877 00:47:38,600 --> 00:47:40,190 >> Kaya sabihin maglakad sa pamamagitan ng halimbawa na ito. 878 00:47:40,190 --> 00:47:44,590 Kaya ito ay isang hanay ng mga laki 6, tama? 879 00:47:44,590 --> 00:47:49,220 At mayroon kaming ngayon, ang aming laki ay 5. 880 00:47:49,220 --> 00:47:55,240 At kapag inilalagay namin ito, ito ay pagpunta pumunta sa ikalimang index, tama? 881 00:47:55,240 --> 00:47:57,030 Kaya mag-imbak sa likod o hulihan. 882 00:47:57,030 --> 00:48:05,600 >> Ang isa pang paraan upang isulat ang buntot gagawin lamang maging, i-right aming array sa index ng laki? 883 00:48:05,600 --> 00:48:07,560 Ito ay laki 5. 884 00:48:07,560 --> 00:48:11,490 Susunod na bagay ay pagpunta sa pumunta sa 5. 885 00:48:11,490 --> 00:48:12,296 Cool? 886 00:48:12,296 --> 00:48:13,290 OK. 887 00:48:13,290 --> 00:48:16,350 Ito ay makakakuha ng bahagyang mas komplikado kapag sinimulan namin ang panggugulo sa ulo. 888 00:48:16,350 --> 00:48:17,060 Oo? 889 00:48:17,060 --> 00:48:20,090 >> Madla: Nangangahulugan ba na na namin sana ay ipinahayag na isang array na 890 00:48:20,090 --> 00:48:23,880 ay limang elemento ng mahaba at pagkatapos naming idinadagdag sa ito? 891 00:48:23,880 --> 00:48:24,730 >> Tagapagsalita 1: Hindi. 892 00:48:24,730 --> 00:48:27,560 Kaya sa kasong ito, ito ay isang stack. 893 00:48:27,560 --> 00:48:31,760 Ito ay ipinahayag bilang isang hanay ng mga laki 6. 894 00:48:31,760 --> 00:48:37,120 At sa kasong ito, kami mayroon lamang isang puwang kaliwa. 895 00:48:37,120 --> 00:48:42,720 >> OK, kaya ang isang bagay ay nasa ito kaso, kung ang aming ulo ay sa 0, 896 00:48:42,720 --> 00:48:45,270 pagkatapos ay ito lamang namin ay maaaring magdagdag sa laki. 897 00:48:45,270 --> 00:48:51,020 Ngunit ito ay nakakakuha ng kaunti trickier dahil aktwal na, ang mga ito 898 00:48:51,020 --> 00:48:52,840 walang slide para sa na ito, kaya ako pupunta 899 00:48:52,840 --> 00:48:56,670 upang gumuhit ng isang dahil hindi ito medyo na simple sa sandaling 900 00:48:56,670 --> 00:48:59,230 simulan inaalis ng mga bagay. 901 00:48:59,230 --> 00:49:03,920 Kaya samantalang may stack lamang kailanman mayroon kang 902 00:49:03,920 --> 00:49:08,920 mag-alala tungkol sa kung ano ang laki ay kapag nagdadagdag ka ng isang bagay sa, 903 00:49:08,920 --> 00:49:15,710 may isang queue kailangan mo rin gawin Tiyakin na ang iyong ulo ay accounted para sa, 904 00:49:15,710 --> 00:49:20,760 dahil ang isang cool na bagay tungkol sa queues ay kung wala ka sa kapasidad, 905 00:49:20,760 --> 00:49:23,040 Maaari mong aktwal na gawin itong balutin sa paligid. 906 00:49:23,040 --> 00:49:28,810 >> OK, kaya isa thing-- oh, ito ay kahila-hilakbot na tisa. 907 00:49:28,810 --> 00:49:31,815 Ang isang bagay upang isaalang-alang ang kaso. 908 00:49:31,815 --> 00:49:35,514 909 00:49:35,514 --> 00:49:37,140 Makikita lang namin gawin lima. 910 00:49:37,140 --> 00:49:41,810 OK, kaya kami ay pagpunta sa ang sinasabi ng mga pinuno ay dito. 911 00:49:41,810 --> 00:49:46,140 Ito ay 0, 1, 2, 3, 4. 912 00:49:46,140 --> 00:49:54,210 >> Ulo ang naroon, at mangyaring magkaroon ng mga bagay sa kanila. 913 00:49:54,210 --> 00:49:58,340 At gusto naming idagdag ang isang bagay sa, i-right? 914 00:49:58,340 --> 00:50:01,170 Kaya ang bagay na kailangan namin upang alam na ang ulo ay laging 915 00:50:01,170 --> 00:50:05,620 pagpunta sa ilipat ang paraan at pagkatapos ay i-loop pabalik sa paligid, OK? 916 00:50:05,620 --> 00:50:10,190 >> Kaya may mga puwang na ito queue, i-right? 917 00:50:10,190 --> 00:50:13,950 Mayroon itong puwang sa pinakadulo simula, uri ng tapat ng ito. 918 00:50:13,950 --> 00:50:17,920 Kaya kung ano ang kailangan naming gawin ay namin Kailangan upang makalkula ang buntot. 919 00:50:17,920 --> 00:50:20,530 Kung alam mo na ang iyong Hindi inilipat ulo, buntot 920 00:50:20,530 --> 00:50:24,630 lamang ang iyong mga array sa sa index ng laki. 921 00:50:24,630 --> 00:50:30,000 >> Ngunit sa katotohanan, kung gumagamit ka ng isang pila, ang iyong ulo ay malamang na ina-update. 922 00:50:30,000 --> 00:50:33,890 Kaya kung ano ang kailangan mong gawin ay aktwal na kalkulahin ang buntot. 923 00:50:33,890 --> 00:50:39,990 Kaya kung ano ang ginagawa namin ay ang formula dito, na kung saan ako pupunta upang ipaalam sa iyo 924 00:50:39,990 --> 00:50:42,680 guys isipin ang tungkol sa, at pagkatapos ay gagamitin namin makipag-usap tungkol dito. 925 00:50:42,680 --> 00:50:49,567 926 00:50:49,567 --> 00:50:50,400 Kaya ito ay kapasidad. 927 00:50:50,400 --> 00:50:55,890 928 00:50:55,890 --> 00:50:59,660 >> Kaya na ito ay talagang magbibigay sa iyo ng isang paraan upang gawin ito. 929 00:50:59,660 --> 00:51:03,205 930 00:51:03,205 --> 00:51:04,330 Dahil sa kasong ito, ano? 931 00:51:04,330 --> 00:51:09,205 Ang aming mga pinuno ay nasa 1, ang aming laki ay 4. 932 00:51:09,205 --> 00:51:11,760 933 00:51:11,760 --> 00:51:18,490 Kung mod namin na sa pamamagitan ng 5, makuha namin ang 0, na kung saan ay dapat namin pag-input na ito. 934 00:51:18,490 --> 00:51:23,320 935 00:51:23,320 --> 00:51:26,080 >> Kaya pagkatapos ay sa susunod na kaso, kung kami ay upang gawin ito, 936 00:51:26,080 --> 00:51:33,390 sabihin namin, OK, dequeue ng isang bagay na ipaalam. 937 00:51:33,390 --> 00:51:34,390 Dequeue namin ito. 938 00:51:34,390 --> 00:51:37,740 Kumuha namin ang elementong ito, i-right? 939 00:51:37,740 --> 00:51:47,930 >> At ngayon ang aming mga ulo nakaturo dito, at gusto naming idagdag sa isa pang bagay. 940 00:51:47,930 --> 00:51:52,470 Ito ay isa lamang sa pabalik sa aming mga linya, tama? 941 00:51:52,470 --> 00:51:55,450 Queues maaari wrap sa paligid ng array. 942 00:51:55,450 --> 00:51:57,310 Iyon ang isa sa mga pangunahing pagkakaiba. 943 00:51:57,310 --> 00:51:58,780 Stack, hindi mo maaaring gawin ito. 944 00:51:58,780 --> 00:52:01,140 >> Sa queues, maaari mong dahil ang lahat na mahalaga 945 00:52:01,140 --> 00:52:03,940 ay na-alam sa iyo kung ano ang Idinagdag ang pinaka-kamakailang. 946 00:52:03,940 --> 00:52:10,650 Dahil ang lahat ng bagay ay pagpunta na idaragdag sa ito pakaliwa direksyon, sa kasong ito, 947 00:52:10,650 --> 00:52:16,480 at pagkatapos ay i-wrap sa paligid, maaari kang magpatuloy paglalagay sa mga bagong elemento 948 00:52:16,480 --> 00:52:18,830 sa harap ng array dahil hindi ito talaga 949 00:52:18,830 --> 00:52:20,640 sa harap ng array na ngayon. 950 00:52:20,640 --> 00:52:26,320 Maaari mong isipin na ang simula ng array ng kung saan ang iyong ulo talaga. 951 00:52:26,320 --> 00:52:29,710 >> Kaya ito formula ay kung paano makalkula mo ang iyong buntot. 952 00:52:29,710 --> 00:52:32,780 953 00:52:32,780 --> 00:52:35,610 Sinusuportahan ba na saysay? 954 00:52:35,610 --> 00:52:36,110 OK. 955 00:52:36,110 --> 00:52:39,400 956 00:52:39,400 --> 00:52:44,040 OK, dequeue, at pagkatapos ay ka guys ay may 10 minuto 957 00:52:44,040 --> 00:52:48,840 upang hilingin sa akin ang anumang mga tanong pagpapaliwanag gusto mo, dahil alam kong ito'y mabaliw. 958 00:52:48,840 --> 00:52:51,980 >> Ang lahat ng mga karapatan, kaya sa parehong way-- Hindi ko alam kung napansin mo guys, 959 00:52:51,980 --> 00:52:53,450 ngunit CS ay tungkol sa mga pattern. 960 00:52:53,450 --> 00:52:57,370 Mga bagay ay medyo magkano ang parehong, lamang sa mga maliliit na pag-aayos. 961 00:52:57,370 --> 00:52:58,950 Kaya parehong bagay dito. 962 00:52:58,950 --> 00:53:04,040 Kailangan naming suriin upang makita kung kami talaga May isang bagay sa aming queue, i-right? 963 00:53:04,040 --> 00:53:05,960 Sabihing, OK, ang aming laki mas malaki kaysa sa 0? 964 00:53:05,960 --> 00:53:06,730 Ayos. 965 00:53:06,730 --> 00:53:10,690 >> Kung gagawin namin, pagkatapos ay ilipat namin ang aming mga pinuno, na ay kung ano lamang ang nagpakita ko dito. 966 00:53:10,690 --> 00:53:13,870 -Update namin ang aming ulo upang maging isa pa. 967 00:53:13,870 --> 00:53:18,390 At pagkatapos ng pagbawas namin ang aming laki at ibalik ang mga elemento. 968 00:53:18,390 --> 00:53:21,000 969 00:53:21,000 --> 00:53:26,250 >> May mas kongkreto code sa study.cs50.net, 970 00:53:26,250 --> 00:53:29,440 at lubos na inirerekomenda ko ng pagpunta sa pamamagitan nito kung mayroon kang panahon, 971 00:53:29,440 --> 00:53:30,980 kahit na ito ay isang palsipikado-code lamang. 972 00:53:30,980 --> 00:53:35,980 At kung gusto mong guys na makipag-usap sa pamamagitan ng na sa akin ng isa sa isa, mangyaring ipaalam sa akin 973 00:53:35,980 --> 00:53:37,500 alam. 974 00:53:37,500 --> 00:53:38,770 Gusto ko ay magiging masaya na. 975 00:53:38,770 --> 00:53:42,720 Mga istraktura ng data, kung Dadalhin ka ng CS 124, ikaw ay 976 00:53:42,720 --> 00:53:47,830 malaman na ang mga istraktura ng data makakuha ng napaka masaya at ito ay nagsisimula pa lang. 977 00:53:47,830 --> 00:53:50,350 >> Kaya alam ko mahirap. 978 00:53:50,350 --> 00:53:51,300 Ito ay ang OK. 979 00:53:51,300 --> 00:53:52,410 Nagpupumilit namin. 980 00:53:52,410 --> 00:53:53,630 Ko pa rin gawin. 981 00:53:53,630 --> 00:53:56,660 Kaya huwag mag-alala masyadong maraming tungkol dito. 982 00:53:56,660 --> 00:54:02,390 >> Ngunit iyon ay isa lamang ang iyong Siyempre pag-crash sa mga istraktura ng data. 983 00:54:02,390 --> 00:54:03,400 Alam ko ito ng maraming. 984 00:54:03,400 --> 00:54:06,860 Mayroon bang anumang bagay na namin gustong pumunta muli? 985 00:54:06,860 --> 00:54:09,400 Anumang bagay na gusto naming makipag-usap sa pamamagitan? 986 00:54:09,400 --> 00:54:10,060 Oo? 987 00:54:10,060 --> 00:54:16,525 >> Madla: Halimbawa iyon, kaya ang bagong buntot ay nasa 0 ibabaw iyon? 988 00:54:16,525 --> 00:54:17,150 Tagapagsalita 1: Oo. 989 00:54:17,150 --> 00:54:18,230 Madla: OK. 990 00:54:18,230 --> 00:54:24,220 Kaya pagkatapos ng pagpunta sa pamamagitan ng, kailangan mong 1 plus 4 or-- 991 00:54:24,220 --> 00:54:27,671 >> Tagapagsalita 1: Kaya ay nagsasabi sa iyo, kung kailan namin gustong pumunta gawin ito muli? 992 00:54:27,671 --> 00:54:28,296 Madla: Oo. 993 00:54:28,296 --> 00:54:38,290 Kaya kung ikaw ay pag-uunawa ng out-- kung nasaan mo pagkalkula ng buntot mula sa iyon? 994 00:54:38,290 --> 00:54:44,260 >> Tagapagsalita 1: Kaya ang buntot ay in-- Nabago ko na ito. 995 00:54:44,260 --> 00:54:52,010 Kaya sa halimbawa dito, ito ay ang array kaming naghahanap sa, OK? 996 00:54:52,010 --> 00:54:54,670 Kaya mayroon kaming mga bagay sa loob ng 1, 2, 3, at 4. 997 00:54:54,670 --> 00:55:05,850 Kaya mayroon namin ang aming mga ulo ay katumbas ng 1 sa puntong ito, at ang aming laki ay katumbas ng 4 998 00:55:05,850 --> 00:55:07,050 sa puntong ito, tama? 999 00:55:07,050 --> 00:55:08,960 >> Mo ang lahat ng sumang-ayon na ang kaso? 1000 00:55:08,960 --> 00:55:14,620 Kaya ang ginagawa namin ang ulo kasama ang laki, na Binibigyan kami ng 5, at pagkatapos ay i-mod namin sa pamamagitan ng 5. 1001 00:55:14,620 --> 00:55:20,690 Makuha namin ang 0, na nagsasabi sa amin na ang 0 ay kung saan ay ang aming buntot, kung saan mayroon kaming espasyo. 1002 00:55:20,690 --> 00:55:22,010 >> Madla: Ano ang isang cap? 1003 00:55:22,010 --> 00:55:23,520 >> Tagapagsalita 1: kapasidad Ang. 1004 00:55:23,520 --> 00:55:24,020 Sorry. 1005 00:55:24,020 --> 00:55:29,640 Kaya na ay ang laki ng iyong array. 1006 00:55:29,640 --> 00:55:35,210 1007 00:55:35,210 --> 00:55:36,047 Oo? 1008 00:55:36,047 --> 00:55:39,210 >> Madla: [hindi marinig] bago bumalik namin ang elemento? 1009 00:55:39,210 --> 00:55:46,270 >> Tagapagsalita 1: Kaya ilipat namin ang magtungo o bumalik sa sandaling ito? 1010 00:55:46,270 --> 00:55:52,680 Kaya kung ililipat namin ang isa, ng pagbawas sa laki? 1011 00:55:52,680 --> 00:55:54,150 Sandali. 1012 00:55:54,150 --> 00:55:55,770 Siguradong Nakalimutan ko ang isa pa. 1013 00:55:55,770 --> 00:56:00,646 1014 00:56:00,646 --> 00:56:01,990 Hindi na bale. 1015 00:56:01,990 --> 00:56:04,980 Walang ibang formula. 1016 00:56:04,980 --> 00:56:09,980 Oo, gusto mo upang bumalik ang ulo at pagkatapos ay ilipat ito pabalik. 1017 00:56:09,980 --> 00:56:13,270 >> Madla: OK, dahil Sa na ito point, ang ulo ay sa 0, 1018 00:56:13,270 --> 00:56:18,452 at pagkatapos ay gusto mong bumalik index ng 0 at pagkatapos ay gumawa ng ulo 1? 1019 00:56:18,452 --> 00:56:19,870 >> Tagapagsalita 1: I-right. 1020 00:56:19,870 --> 00:56:22,820 Sa tingin ko mayroong isa pang formula uri ng ganito. 1021 00:56:22,820 --> 00:56:26,970 Wala akong ito sa tuktok ng aking ulo bilang Hindi ko nais upang mabigyan ka ng isang mali. 1022 00:56:26,970 --> 00:56:35,470 Ngunit tingin ko ito ay ganap na wasto upang sabihin nating, OK, iimbak ang element-- anumang 1023 00:56:35,470 --> 00:56:40,759 elemento ng ulo ni is-- ng pagbawas sa iyong laki, ilipat ang iyong ulo sa ibabaw, at return 1024 00:56:40,759 --> 00:56:41,800 anumang elemento na. 1025 00:56:41,800 --> 00:56:44,760 Iyon ang perpektong wastong. 1026 00:56:44,760 --> 00:56:45,260 OK. 1027 00:56:45,260 --> 00:56:48,360 1028 00:56:48,360 --> 00:56:53,560 Pakiramdam ko ay tulad nito ay hindi tulad ng most-- hindi ka 1029 00:56:53,560 --> 00:56:55,740 pagpunta sa walk out sa dito tulad ng, oo, alam ko pagsubok. 1030 00:56:55,740 --> 00:56:56,880 Mayroon akong lahat ng ito. 1031 00:56:56,880 --> 00:56:57,670 Iyon ang OK. 1032 00:56:57,670 --> 00:57:00,200 Nangangako ako. 1033 00:57:00,200 --> 00:57:05,240 Ngunit mga istraktura ng data ay isang bagay na gumugugol ito ng maraming oras upang masanay. 1034 00:57:05,240 --> 00:57:10,010 Malamang na isa sa mga hardest mga bagay, sa tingin ko, sa kurso. 1035 00:57:10,010 --> 00:57:15,330 >> Kaya nga tumatagal ito pag-uulit at naghahanap at-- ko 1036 00:57:15,330 --> 00:57:20,050 ay hindi talaga alam na naka-link listahan hanggang ginawa ko sa ngayon labis sa kanila, 1037 00:57:20,050 --> 00:57:22,550 sa parehong paraan na aking ginawa hindi talagang nauunawaan na pointer 1038 00:57:22,550 --> 00:57:27,040 hanggang sa nagkaroon ako magturo ito para sa dalawang taon at ang aking sariling psets dito. 1039 00:57:27,040 --> 00:57:28,990 Inaabot ng maraming pag-uulit at oras. 1040 00:57:28,990 --> 00:57:32,600 At sa huli, ito uri ng click. 1041 00:57:32,600 --> 00:57:36,320 >> Ngunit pansamantala, kung mayroon kang uri ng isang mataas na antas ng pag-unawa kung ano ang 1042 00:57:36,320 --> 00:57:39,321 mga gagawin, ang kanilang mga pro at cons-- na kung ano ang 1043 00:57:39,321 --> 00:57:41,820 kami talaga ay may posibilidad upang bigyan ng diin, lalo na sa intro course. 1044 00:57:41,820 --> 00:57:45,511 Tulad ng, kung bakit naming gamitin isang subukan sa isang array? 1045 00:57:45,511 --> 00:57:48,010 Tulad ng, ano ang mga positibo at mga negatibo ng bawat isa sa mga? 1046 00:57:48,010 --> 00:57:51,610 >> At pag-unawa sa mga trade-off sa pagitan ng bawat isa sa mga kaayusan 1047 00:57:51,610 --> 00:57:54,910 ay kung ano ang mas mahalaga sa ngayon. 1048 00:57:54,910 --> 00:57:58,140 Maaaring may isa mabaliw tanong o dalawang na 1049 00:57:58,140 --> 00:58:03,710 pagpunta sa hilingin sa iyo upang ipatupad ang push o ipatupad ang mga pop o enqueue at dequeue. 1050 00:58:03,710 --> 00:58:07,340 Ngunit para sa pinaka-bahagi, nagkakaroon na mas mataas na antas ng pag-unawa at higit pa 1051 00:58:07,340 --> 00:58:09,710 ng isang intuitive hawakang mahigpit ay mas mahalaga kaysa sa aktwal 1052 00:58:09,710 --> 00:58:11,250 kawalan ng kakayahang ipatupad ito. 1053 00:58:11,250 --> 00:58:14,880 >> Gusto ito ay talagang kahanga-hangang kung ang lahat ng sa iyo maaaring lumabas at pumunta ipatupad ang try, 1054 00:58:14,880 --> 00:58:19,720 ngunit naiintindihan namin ito ay hindi kinakailangan ang pinaka-makatwirang bagay ngayon. 1055 00:58:19,720 --> 00:58:23,370 Ngunit maaari mo sa iyong pset, kung nais mong sa, at pagkatapos ay makakakuha ka ng mga kasanayan, 1056 00:58:23,370 --> 00:58:27,200 at pagkatapos ay marahil ikaw ay talagang maunawaan ito. 1057 00:58:27,200 --> 00:58:27,940 Oo? 1058 00:58:27,940 --> 00:58:30,440 >> Madla: OK, kaya kung alin ang mga namin sinadya upang gamitin sa pset? 1059 00:58:30,440 --> 00:58:31,916 Kailangan ko bang gamitin ang isa sa mga ito? 1060 00:58:31,916 --> 00:58:32,540 Tagapagsalita 1: Oo. 1061 00:58:32,540 --> 00:58:34,199 Kaya mayroon kang ang iyong pinili. 1062 00:58:34,199 --> 00:58:36,740 Sa tingin ko sa kasong ito, maaari naming makipag-usap tungkol sa pset Medyo 1063 00:58:36,740 --> 00:58:40,480 dahil nagpatakbo ako sa pamamagitan ng mga ito. 1064 00:58:40,480 --> 00:58:47,779 Kaya sa iyong pset, mayroon kang iyong pagpili ng pagsubok o hash talahanayan. 1065 00:58:47,779 --> 00:58:49,570 Ang ilang mga tao ay subukan at gamitin ang pamumulaklak ng mga filter, 1066 00:58:49,570 --> 00:58:51,840 ngunit ang mga technically ay hindi tama. 1067 00:58:51,840 --> 00:58:55,804 Dahil sa kanilang probabilistic likas na katangian, bigyan sila maling positibo minsan. 1068 00:58:55,804 --> 00:58:57,095 Ang mga ito ay cool na hitsura sa, bagaman. 1069 00:58:57,095 --> 00:58:59,030 Lubos na inirerekomenda hinahanap sa mga ito ng hindi bababa sa. 1070 00:58:59,030 --> 00:59:03,260 Ngunit mayroon kang iyong pinili sa pagitan ng isang hash table at try. 1071 00:59:03,260 --> 00:59:06,660 At na pupuntahan maging kung saan -load mo sa iyong diksyunaryo. 1072 00:59:06,660 --> 00:59:09,230 >> At kailangan mong pumili ang iyong hash, 1073 00:59:09,230 --> 00:59:13,420 kakailanganin mong piliin kung gaano karaming mga bucket na mayroon ka, at ito ay mag-iiba. 1074 00:59:13,420 --> 00:59:17,440 Tulad ng kung mayroon kang higit bucket, marahil ito ay tumakbo nang mas mabilis. 1075 00:59:17,440 --> 00:59:22,790 Pero siguro ka pag-aaksaya ng maraming espasyo na paraan, bagaman. 1076 00:59:22,790 --> 00:59:26,320 Kailangan mong malaman ito. 1077 00:59:26,320 --> 00:59:27,140 Mmhmm? 1078 00:59:27,140 --> 00:59:29,875 >> Madla: Sinabi mo dati na Maaari naming gamitin ang iba pang mga pag-andar ng hash, 1079 00:59:29,875 --> 00:59:31,750 na hindi namin kailangang lumikha ng isang hash? 1080 00:59:31,750 --> 00:59:32,666 >> Tagapagsalita 1: Oo, tama. 1081 00:59:32,666 --> 00:59:38,150 Kaya literal para sa iyong hash, tulad ng google "hash" 1082 00:59:38,150 --> 00:59:40,770 at hanapin para sa ilang mga magandang mga bago. 1083 00:59:40,770 --> 00:59:43,250 Hindi mo ay inaasahan na bumuo ng ang iyong sariling mga pag-andar ng hash. 1084 00:59:43,250 --> 00:59:46,100 Gastusin mga tao ang kanilang theses sa mga bagay na ito. 1085 00:59:46,100 --> 00:59:50,250 >> Kaya huwag mag-alala tungkol sa pagbuo ng iyong sariling. 1086 00:59:50,250 --> 00:59:53,350 Hanapin ang isa sa mga online na magsimula sa. 1087 00:59:53,350 --> 00:59:56,120 Ang ilan sa mga ito ay mong manipulahin Medyo 1088 00:59:56,120 --> 00:59:59,430 upang gawin tumugma bang uri ng return up at watnat, kaya sa simula, 1089 00:59:59,430 --> 01:00:02,420 Gusto ko inirerekomenda ang paggamit ng isang bagay talagang madali na siguro lang 1090 01:00:02,420 --> 01:00:04,680 hash sa unang titik. 1091 01:00:04,680 --> 01:00:08,760 At pagkatapos ay sa sandaling mayroon ka na sa pagtatrabaho, nagsasama ng mas cool na function na hash. 1092 01:00:08,760 --> 01:00:09,260 Mmhmm? 1093 01:00:09,260 --> 01:00:13,020 >> Madla: Gusto ng subukang maging o mahusay na ngunit mas mahirap lamang sa, like-- 1094 01:00:13,020 --> 01:00:15,880 >> Tagapagsalita 1: Kaya isang try, sa palagay ko, ay intuitively mahirap na ipatupad 1095 01:00:15,880 --> 01:00:18,310 ngunit ito ay napakabilis. 1096 01:00:18,310 --> 01:00:20,620 Gayunpaman, tumatagal ng mas maraming espasyo. 1097 01:00:20,620 --> 01:00:25,270 Muli, maaari mong i-optimize ang parehong mga nasa iba't ibang paraan at may mga paraan to-- 1098 01:00:25,270 --> 01:00:26,770 Madla: Paano kami ay namarkahan sa ito? 1099 01:00:26,770 --> 01:00:27,540 Ito ay matter-- 1100 01:00:27,540 --> 01:00:29,164 >> Tagapagsalita 1: Kaya ka namarkahan ang normal na paraan. 1101 01:00:29,164 --> 01:00:31,330 Na iyong pupuntahan ay namarkahan sa disenyo. 1102 01:00:31,330 --> 01:00:36,020 Alinmang paraan gagawin mo, nais mong tiyakin na ito ay bilang eleganteng bilang maaari itong maging 1103 01:00:36,020 --> 01:00:38,610 at bilang mahusay na bilang maaari itong maging. 1104 01:00:38,610 --> 01:00:41,950 Ngunit kung pumili ka ng isang pagsubok o hash talahanayan, hangga't ito gumagana, 1105 01:00:41,950 --> 01:00:45,350 kami ay masaya na iyon. 1106 01:00:45,350 --> 01:00:48,370 At kung gumagamit ka ng isang bagay na hash sa unang titik, na multa, 1107 01:00:48,370 --> 01:00:51,410 tulad siguro tulad ng disenyo-matalino. 1108 01:00:51,410 --> 01:00:53,410 Kami ay pag-abot din ang point sa semester-- 1109 01:00:53,410 --> 01:00:55,340 Hindi ko alam kung guys noticed-- kung ikaw ay 1110 01:00:55,340 --> 01:00:58,780 grado pset tanggihan Medyo dahil sa disenyo at watnat, 1111 01:00:58,780 --> 01:00:59,900 na ganap na multa. 1112 01:00:59,900 --> 01:01:02,960 Nagiging sa isang punto kung saan ang iyong programa ay nakakakuha ng mas komplikado. 1113 01:01:02,960 --> 01:01:04,830 Mayroong higit pang mga lugar maaari mong pagbutihin sa. 1114 01:01:04,830 --> 01:01:06,370 >> Kaya ito ay ganap na normal. 1115 01:01:06,370 --> 01:01:08,810 Ito ay hindi na ikaw ay paggawa ng mas masahol pa sa iyong pset. 1116 01:01:08,810 --> 01:01:11,885 Ito ay lamang namin ang pagiging mahirap sa iyo ngayon. 1117 01:01:11,885 --> 01:01:13,732 Kaya lahat ay pakiramdam ito. 1118 01:01:13,732 --> 01:01:14,940 Ko lang namarkahan ang lahat ng iyong mga psets. 1119 01:01:14,940 --> 01:01:16,490 Alam ko ang lahat ay pakiramdam ito. 1120 01:01:16,490 --> 01:01:19,600 >> Kaya huwag maging nag-aalala tungkol na iyon. 1121 01:01:19,600 --> 01:01:23,580 At kung mayroon kang anumang mga tanong tungkol sa bago psets o mga paraan na maaari mong pagbutihin, 1122 01:01:23,580 --> 01:01:27,760 Ako subukan at magkomento sa mga partikular na mga lugar, ngunit minsan ito ay huli na 1123 01:01:27,760 --> 01:01:30,840 at makakakuha ng pagod. 1124 01:01:30,840 --> 01:01:34,885 Mayroon bang anumang iba pang mga bagay tungkol sa data na kaayusan? 1125 01:01:34,885 --> 01:01:37,510 Ako ba mo guys ay hindi talaga nais na makipag-usap tungkol sa mga ito, 1126 01:01:37,510 --> 01:01:42,650 ngunit kung mayroong, Ikinagagalak kong pumunta sa ibabaw ng mga ito, pati na rin ang anumang bagay 1127 01:01:42,650 --> 01:01:45,580 mula sa aralin na ito nakalipas linggo o noong nakaraang linggo. 1128 01:01:45,580 --> 01:01:51,580 >> Alam ko noong nakaraang linggo ay ang lahat ng pagsusuri, kaya Maaaring namin nilaktawan sa paglipas ng ilang mga review 1129 01:01:51,580 --> 01:01:54,190 mula sa aralin. 1130 01:01:54,190 --> 01:01:58,230 Anumang iba pang mga katanungan maaari kong sagutin? 1131 01:01:58,230 --> 01:01:59,350 OK, ang lahat ng karapatan. 1132 01:01:59,350 --> 01:02:02,400 Well, mo guys makakuha ng out ng 15 minutong maaga. 1133 01:02:02,400 --> 01:02:08,370 >> Umaasa ako na ito ay semi-kapaki-pakinabang na hindi bababa sa, at ako ay nakikita mo guys sa susunod na linggo, 1134 01:02:08,370 --> 01:02:12,150 o oras ng opisina Huwebes. 1135 01:02:12,150 --> 01:02:15,285 Mayroon bang humiling para sa mga meryenda para sa susunod na linggo, ito ang bagay? 1136 01:02:15,285 --> 01:02:17,459 Dahil nakalimutan ko ang kendi ngayon. 1137 01:02:17,459 --> 01:02:19,750 At dinala ako candy huling linggo, ngunit ito ay Columbus Day, 1138 01:02:19,750 --> 01:02:25,400 kaya mayroong tulad ng anim na taong Nagkaroon ng apat na mga bag ng kendi sa kanilang mga sarili. 1139 01:02:25,400 --> 01:02:28,820 Maaari ko bang magdala ng Starbursts muli kung nais mo. 1140 01:02:28,820 --> 01:02:29,580 Starbursts? 1141 01:02:29,580 --> 01:02:32,250 OK, Maganda iyan. 1142 01:02:32,250 --> 01:02:35,050 Mayroon ba kayong dakilang araw, guys. 1143 01:02:35,050 --> 01:02:39,510