1 00:00:00,000 --> 00:00:11,860 2 00:00:11,860 --> 00:00:13,120 >> Tagapagsalita 1: Ang lahat ng mga karapatan, kaya hindi namin pabalik. 3 00:00:13,120 --> 00:00:14,480 Maligayang pagdating sa CS50. 4 00:00:14,480 --> 00:00:16,510 Ito ang katapusan ng linggo pitong. 5 00:00:16,510 --> 00:00:20,200 Kaya isipin ang na huling panahon, nagsimula kaming tumitingin sa bahagyang mas sopistikadong 6 00:00:20,200 --> 00:00:21,100 data istraktura. 7 00:00:21,100 --> 00:00:25,110 Dahil hanggang ngayon, ang lahat ng nagkaroon kami talaga sa aming pagtatapon ay ito, isang array. 8 00:00:25,110 --> 00:00:29,340 >> Ngunit bago namin itapon ang mga array bilang hindi lahat ng mga kagiliw-giliw na, na sa katunayan ito 9 00:00:29,340 --> 00:00:33,570 talaga ay, kung ano ang ilan sa mga plus ito ng simpleng data 10 00:00:33,570 --> 00:00:34,560 istraktura kaya ngayon? 11 00:00:34,560 --> 00:00:36,110 Ano ang mahusay na ito sa? 12 00:00:36,110 --> 00:00:39,450 Sa ngayon bilang namin ang iyong nakita? 13 00:00:39,450 --> 00:00:42,540 Ano ang nakukuha mo? 14 00:00:42,540 --> 00:00:44,028 Walang anuman. 15 00:00:44,028 --> 00:00:45,020 >> MAG-AARAL: [hindi marinig]. 16 00:00:45,020 --> 00:00:45,395 >> Tagapagsalita 1: Ano iyon? 17 00:00:45,395 --> 00:00:46,410 >> MAG-AARAL: [hindi marinig]. 18 00:00:46,410 --> 00:00:47,000 >> Tagapagsalita 1: Fixed laki. 19 00:00:47,000 --> 00:00:51,260 OK, kaya kung bakit ay nakapirming laki mahusay na bagaman? 20 00:00:51,260 --> 00:00:53,180 >> MAG-AARAL: [hindi marinig]. 21 00:00:53,180 --> 00:00:56,240 >> Tagapagsalita 1: OK, kaya mahusay sa ang pakiramdam na maaari kang magtalaga ng isang 22 00:00:56,240 --> 00:01:00,070 nakapirming halaga ng puwang, na sana ay ay tumpak na bilang magkano 23 00:01:00,070 --> 00:01:01,180 space hangga't gusto mo. 24 00:01:01,180 --> 00:01:02,720 Kaya na maaaring maging ganap ng plus. 25 00:01:02,720 --> 00:01:06,530 >> Ano ang isa pang up bahagi ng isang array? 26 00:01:06,530 --> 00:01:07,610 Oo? 27 00:01:07,610 --> 00:01:08,750 >> MAG-AARAL: [hindi marinig]. 28 00:01:08,750 --> 00:01:09,550 >> Tagapagsalita 1: Lahat ng mga - paumanhin? 29 00:01:09,550 --> 00:01:11,270 >> MAG-AARAL: [hindi marinig]. 30 00:01:11,270 --> 00:01:13,620 >> Tagapagsalita 1: Ang lahat ng mga kahon sa memory o sa tabi ng bawat isa. 31 00:01:13,620 --> 00:01:15,220 At iyan ay kapaki-pakinabang - bakit? 32 00:01:15,220 --> 00:01:15,970 Iyan ay medyo totoo. 33 00:01:15,970 --> 00:01:18,611 Ngunit paano namin maningning na tagumpay na katotohanan? 34 00:01:18,611 --> 00:01:21,500 >> MAG-AARAL: [hindi marinig]. 35 00:01:21,500 --> 00:01:24,490 >> Tagapagsalita 1: Mismong, maaari naming subaybayan ang mga kung saan lahat ng bagay ay sa pamamagitan lamang ng pag-alam 36 00:01:24,490 --> 00:01:28,560 isang address, lalo na sa address ng unang byte ng na tipak ng memory. 37 00:01:28,560 --> 00:01:30,420 O sa kaso ng mga string, ang address ng unang 38 00:01:30,420 --> 00:01:31,460 pansamantalang trabaho sa na string. 39 00:01:31,460 --> 00:01:33,330 At mula doon, maaari naming makita sa dulo ng string. 40 00:01:33,330 --> 00:01:35,710 Maaari naming mahanap ang pangalawang elemento, ang ikatlong elemento, at iba pa. 41 00:01:35,710 --> 00:01:38,740 >> At kaya ang magarbong paraan ng naglalarawan na tampok ay na array bigyan kami ng 42 00:01:38,740 --> 00:01:40,020 random access. 43 00:01:40,020 --> 00:01:44,330 Lamang sa pamamagitan ng paggamit ng mga square bracket pagtatanda at isang numero, maaari mong tumalon sa 44 00:01:44,330 --> 00:01:48,070 isang tukoy na elemento sa array sa pare-pareho ang oras, malaki O 45 00:01:48,070 --> 00:01:49,810 ng isa, kaya na magsalita. 46 00:01:49,810 --> 00:01:51,080 >> Ngunit mayroong nangyaring ng ilang mga downsides. 47 00:01:51,080 --> 00:01:53,110 Ano ang isang array hindi gawin napaka madali? 48 00:01:53,110 --> 00:01:55,810 49 00:01:55,810 --> 00:01:57,170 Ano itong hindi magandang sa? 50 00:01:57,170 --> 00:01:58,810 >> MAG-AARAL: [hindi marinig]. 51 00:01:58,810 --> 00:01:59,860 >> Tagapagsalita 1: Ano iyon? 52 00:01:59,860 --> 00:02:00,530 >> MAG-AARAL: [hindi marinig]. 53 00:02:00,530 --> 00:02:01,460 >> Tagapagsalita 1: Pagpapalawak sa laki. 54 00:02:01,460 --> 00:02:04,800 Kaya ang downsides ng array ay tumpak ang katapat ng kung ano ang 55 00:02:04,800 --> 00:02:05,540 upsides ay. 56 00:02:05,540 --> 00:02:07,610 Kaya ang isa sa mga downsides ay na ito ay isang nakapirming laki. 57 00:02:07,610 --> 00:02:09,400 Kaya hindi ikaw talaga ay maaaring lumaki ito. 58 00:02:09,400 --> 00:02:13,510 Maaari mong reallocate ng mas malaking tipak ng memorya, at pagkatapos ay ilipat ang mga lumang mga elemento 59 00:02:13,510 --> 00:02:14,460 sa bagong array. 60 00:02:14,460 --> 00:02:18,060 At pagkatapos ay libre sa lumang array, para sa Halimbawa, sa pamamagitan ng paggamit malloc o isang katulad na 61 00:02:18,060 --> 00:02:21,180 function na tinatawag na realloc, na reallocates memory. 62 00:02:21,180 --> 00:02:25,490 >> Realloc, bilang isang tabi, sinusubukan upang bigyan ka ng memorya na katabi ng array 63 00:02:25,490 --> 00:02:26,610 na mayroon ka. 64 00:02:26,610 --> 00:02:28,740 Ngunit maaari itong ilipat ang mga bagay sa paligid nang sama-sama. 65 00:02:28,740 --> 00:02:30,710 Ngunit sa maikling salita, na mahal, tama? 66 00:02:30,710 --> 00:02:33,440 Dahil kung mayroon kang isang tipak ng memorya ng sukat na ito, ngunit gusto mo talagang isa 67 00:02:33,440 --> 00:02:36,710 na ganito ang laki, at nais mong panatilihin ang ang orihinal na mga elemento, mayroon kang 68 00:02:36,710 --> 00:02:40,510 halos isang oras linear proseso ng pagkopya na kailangang mangyari mula sa 69 00:02:40,510 --> 00:02:41,900 lumang array sa bagong. 70 00:02:41,900 --> 00:02:44,630 At ang katotohanan ay humihingi sa operating sistema muli at muli at 71 00:02:44,630 --> 00:02:48,340 muli para malaki chunks ng memorya maaaring magsimula upang magdulot sa iyo ng ilang oras pati na rin. 72 00:02:48,340 --> 00:02:52,250 Kaya ito ay pareho ng isang pagpapala at isang sumpa sa magkaila, ang katunayan na ang mga array 73 00:02:52,250 --> 00:02:53,860 ng mga nakapirming laki. 74 00:02:53,860 --> 00:02:56,790 Ngunit kung namin ipakilala sa halip ng isang bagay tulad nito, na kung saan namin na tinatawag na naka-link 75 00:02:56,790 --> 00:03:00,580 listahan, kumuha kami ng ilang upsides at ang ilang mga downsides dito pati na rin. 76 00:03:00,580 --> 00:03:05,780 >> Kaya naka-link na listahan ay isang simpleng data istraktura na binubuo ng C structs ito sa 77 00:03:05,780 --> 00:03:09,850 kaso, kung saan ang isang struct, isipin ang, ay lamang isang lalagyan para sa isa o higit pang mga tiyak na 78 00:03:09,850 --> 00:03:11,100 mga uri ng variable. 79 00:03:11,100 --> 00:03:16,110 Sa kasong ito, kung ano ang ginagawa ng mga uri ng data lumitaw na maging sa loob ng struct na 80 00:03:16,110 --> 00:03:17,600 huling beses namin na tinatawag na node? 81 00:03:17,600 --> 00:03:19,380 Ang bawat isa sa mga parihaba ay isang node. 82 00:03:19,380 --> 00:03:22,660 At bawat isa sa mga mas maliit na parihaba sa loob nito ay isang uri ng data. 83 00:03:22,660 --> 00:03:25,300 Anong mga uri ay sinasabi namin sila ay sa Lunes? 84 00:03:25,300 --> 00:03:26,478 Oo? 85 00:03:26,478 --> 00:03:27,870 >> MAG-AARAL: [hindi marinig]. 86 00:03:27,870 --> 00:03:30,721 >> Tagapagsalita 1: Ang isang variable at isang pointer, o higit na partikular, sa isang int, para sa n, 87 00:03:30,721 --> 00:03:32,180 at isang pointer sa ibaba. 88 00:03:32,180 --> 00:03:35,360 Pareho sa mga mangyari na maging 32 bit, sa hindi bababa sa isang computer tulad nito CS50 89 00:03:35,360 --> 00:03:37,980 Appliance, at sa gayon ang mga ito ay iguguhit nang pantay-pantay sa laki. 90 00:03:37,980 --> 00:03:42,260 >> Kaya kung ano ang ginagamit mo ang pointer kahit na para sa malas? 91 00:03:42,260 --> 00:03:47,690 Bakit idagdag ang arrow na ngayon kapag array ay kaya maganda at malinis at simple? 92 00:03:47,690 --> 00:03:50,460 Ano ang pointer ng paggawa para sa sa amin sa bawat isa sa mga node? 93 00:03:50,460 --> 00:03:52,160 >> MAG-AARAL: [hindi marinig]. 94 00:03:52,160 --> 00:03:52,465 >> Tagapagsalita 1: Mismong. 95 00:03:52,465 --> 00:03:54,120 Ito ay nagsasabi sa iyo kung saan sa susunod na isa ay. 96 00:03:54,120 --> 00:03:57,350 Kaya ako uri ng gamitin ang pagkakatulad ng gamit ang isang thread upang ayusin ng 97 00:03:57,350 --> 00:03:59,180 Thread mga node magkasama. 98 00:03:59,180 --> 00:04:01,760 At iyon mismo kung anong ginagawa namin sa payo dahil bawat isa sa mga 99 00:04:01,760 --> 00:04:06,360 chunks ng memorya ay maaaring o hindi maaaring magkadikit, bumalik upang i-back-back 100 00:04:06,360 --> 00:04:09,500 sa loob ng RAM, dahil sa bawat oras na tumawag malloc sinasabi, akong bigyan ng sapat na 101 00:04:09,500 --> 00:04:12,510 bytes para sa isang bagong node, maaari itong maging dito o maaari itong maging dito. 102 00:04:12,510 --> 00:04:13,120 Maaaring maging dito. 103 00:04:13,120 --> 00:04:13,730 Maaaring maging dito. 104 00:04:13,730 --> 00:04:14,640 Ikaw lamang ay hindi alam. 105 00:04:14,640 --> 00:04:17,880 >> Ngunit gamit ang mga payo sa mga address ng mga mga node, maaari mong tahiin ang mga ito 106 00:04:17,880 --> 00:04:22,370 magkasama sa isang paraan na mukhang biswal tulad ng isang listahan kahit na ang mga bagay na ito ay 107 00:04:22,370 --> 00:04:26,770 lahat maikalat sa buong iyong isa o iyong dalawa o apat ang iyong gigabytes ng RAM 108 00:04:26,770 --> 00:04:28,760 sa loob ng iyong sariling computer. 109 00:04:28,760 --> 00:04:33,230 >> Kaya ang downside, pagkatapos, ng isang naka-link na ang listahan ng kung ano? 110 00:04:33,230 --> 00:04:34,670 Ano ang isang presyo na namin tila nagbabayad? 111 00:04:34,670 --> 00:04:36,010 >> MAG-AARAL: [hindi marinig]. 112 00:04:36,010 --> 00:04:36,920 >> Tagapagsalita 1: Higit pang mga puwang, tama? 113 00:04:36,920 --> 00:04:39,340 Kami, sa kasong ito, Dinoble ang halaga ng espasyo dahil hindi namin nawala 114 00:04:39,340 --> 00:04:43,500 mula sa 32 bits para sa bawat node, para sa bawat int, kaya ngayon 64 bits dahil mayroon kaming upang 115 00:04:43,500 --> 00:04:45,050 panatilihin sa paligid ng isang pointer pati na rin. 116 00:04:45,050 --> 00:04:48,860 Makakuha ka ng mas maraming kahusayan kung ang iyong struct ay mas malaki kaysa ito simpleng bagay. 117 00:04:48,860 --> 00:04:52,020 Kung ang iyong aktwal na magkaroon ng isang mag-aaral sa loob na kung saan ay isang pares ng mga string para sa 118 00:04:52,020 --> 00:04:55,430 pangalan at bahay, marahil ng isang ID number, marahil ilang mga iba pang mga patlang sama-sama. 119 00:04:55,430 --> 00:04:59,000 >> Kaya kung mayroon kang isang malaking sapat struct, pagkatapos siguro ang gastos ng pointer ay 120 00:04:59,000 --> 00:05:00,010 Hindi tulad ng isang malaking pakikitungo. 121 00:05:00,010 --> 00:05:03,570 Ito ay isang bit ng isang kaso sa sulok na kami ay pag-iimbak tulad ng isang simpleng primitive 122 00:05:03,570 --> 00:05:04,760 sa loob ng nakaugnay sa listahan. 123 00:05:04,760 --> 00:05:05,790 Ngunit ang punto ay pareho. 124 00:05:05,790 --> 00:05:08,230 Talagang ka gumagastos higit pa memorya, ngunit nakakakuha ka ng 125 00:05:08,230 --> 00:05:08,990 kakayahang umangkop. 126 00:05:08,990 --> 00:05:12,280 Dahil ngayon kapag gusto kong magdagdag ng isang elemento sa simula ng listahan na ito, 127 00:05:12,280 --> 00:05:14,340 Mayroon akong upang magtalaga ng isang bagong node. 128 00:05:14,340 --> 00:05:17,180 At mayroon akong upang i-update lamang ang mga mga arrow sa paanuman lamang sa pamamagitan ng paglipat ng 129 00:05:17,180 --> 00:05:17,980 ilang mga payo sa paligid. 130 00:05:17,980 --> 00:05:20,580 >> Kung gusto kong magpasok ng isang bagay sa gitna ng listahan, hindi ko kailangang mag- 131 00:05:20,580 --> 00:05:24,410 itulak lahat ng tao bukod tulad ng ginawa namin sa linggo 'nakaraan sa aming mga boluntaryo sino 132 00:05:24,410 --> 00:05:25,700 kinakatawan ng isang array. 133 00:05:25,700 --> 00:05:29,470 Maaari ko lang ang magtalaga ng isang bagong node at pagkatapos lamang ituro ang mga arrow sa 134 00:05:29,470 --> 00:05:32,290 iba't ibang direksyon dahil ito ay hindi kailangang manatili sa aktwal na 135 00:05:32,290 --> 00:05:35,670 memorya ng tunay na linya tulad ko na iginuhit ito dito sa screen. 136 00:05:35,670 --> 00:05:38,400 >> At pagkatapos ay bilang wakas, kung gusto mong isingit isang bagay sa dulo ng listahan, ito ay 137 00:05:38,400 --> 00:05:39,210 mas madali. 138 00:05:39,210 --> 00:05:43,320 Ito ay isang uri ng arbitrary notation, ngunit 34 ang pointer, kumuha nang isang hula. 139 00:05:43,320 --> 00:05:46,710 Ano ang halaga ng kanyang pinaka-pointer malamang iginuhit uri ng tulad ng isang lumang 140 00:05:46,710 --> 00:05:47,700 paaralan antena doon? 141 00:05:47,700 --> 00:05:48,920 >> MAG-AARAL: [hindi marinig]. 142 00:05:48,920 --> 00:05:49,900 >> Tagapagsalita 1: Ito ay marahil null. 143 00:05:49,900 --> 00:05:52,710 At tunay nga na isang may-akda representasyon ng null. 144 00:05:52,710 --> 00:05:56,310 At ito ay walang bisa dahil kung talagang kailangan mong malaman kung saan ang dulo ng isang naka-link na 145 00:05:56,310 --> 00:06:00,050 ang listahan, baka panatilihin kang sumusunod at pagsunod at pagsunod sa mga arrow na ito 146 00:06:00,050 --> 00:06:01,170 sa ilang mga basura na halaga. 147 00:06:01,170 --> 00:06:06,230 Kaya null ay magpahiwatig na walang higit pang mga nodes sa kanan ng numero 34, 148 00:06:06,230 --> 00:06:07,200 sa kasong ito. 149 00:06:07,200 --> 00:06:10,270 >> Kaya naming imungkahi na maaari naming ipatupad ito node sa code. 150 00:06:10,270 --> 00:06:12,130 At nakakita kami uri na ito syntax ng bago. 151 00:06:12,130 --> 00:06:15,090 Typedef lamang tumutukoy sa isang bagong uri para sa amin, nagbibigay sa amin ng isang kasingkahulugan tulad ng 152 00:06:15,090 --> 00:06:17,100 string ay para sa pansamantalang trabaho *. 153 00:06:17,100 --> 00:06:21,030 Sa kasong ito, ito ay pagpunta sa magbibigay sa amin shorthand notation sa gayon ay struct node 154 00:06:21,030 --> 00:06:24,010 Maaari lamang sa halip na nakasulat bilang node, na kung saan ay marami mas malinis. 155 00:06:24,010 --> 00:06:25,360 Ito ay isang maraming mas mababa maligoy. 156 00:06:25,360 --> 00:06:30,080 >> Sa loob ng isang node ay tila isang int tinatawag n, at pagkatapos ay isang struct node * 157 00:06:30,080 --> 00:06:34,670 na nangangahulugan nang eksakto kung ano ang gusto namin ang mga arrow upang sabihin, isang pointer sa isa pang 158 00:06:34,670 --> 00:06:36,940 na node ng ang eksaktong parehong uri ng data. 159 00:06:36,940 --> 00:06:40,300 At ipanukala ko na kami maaaring ipatupad ang search function na tulad nito, na sa 160 00:06:40,300 --> 00:06:41,890 unang sulyap ay maaaring mukhang medyo kumplikado. 161 00:06:41,890 --> 00:06:43,330 Ngunit sabihin makita ito sa konteksto. 162 00:06:43,330 --> 00:06:45,480 >> Hayaan akong pumunta sa ibabaw ng mga appliance dito. 163 00:06:45,480 --> 00:06:48,460 Hayaan akong magbukas ng isang file na tinatawag na listahan zero tuldok h. 164 00:06:48,460 --> 00:06:53,950 At na naglalaman lamang ang kahulugan namin Nakita lamang ng ilang sandali ang nakalipas para sa data na ito 165 00:06:53,950 --> 00:06:55,390 uri ng tinatawag na node. 166 00:06:55,390 --> 00:06:57,350 Kaya namin inilagay ang mga iyon sa isang file na tuldok h. 167 00:06:57,350 --> 00:07:01,430 >> At bilang isang tabi, kahit na ito programa na ikaw ay tungkol sa upang makita ang 168 00:07:01,430 --> 00:07:05,410 hindi lahat na kumplikado, ito ay sa katunayan convention kapag sumusulat ng isang programa sa 169 00:07:05,410 --> 00:07:10,270 maglagay ng mga bagay tulad ng mga uri ng data, upang hilahin constants minsan, sa loob ng iyong 170 00:07:10,270 --> 00:07:13,210 header na file at hindi kinakailangan sa ang iyong mga file C, tiyak na kapag ang iyong 171 00:07:13,210 --> 00:07:17,370 mga programa makakuha ng mas malaki at mas malaki, sa gayon ay alam mo kung saan upang tumingin para sa kapwa 172 00:07:17,370 --> 00:07:20,840 dokumentasyon sa ilang mga kaso, o para sa mga pangunahing kaalaman tulad nito, ang 173 00:07:20,840 --> 00:07:22,360 kahulugan ng ilang mga uri. 174 00:07:22,360 --> 00:07:25,680 >> Kung ako ngayon buksan up listahan zero na tuldok c, mapapansin ang ilang mga bagay. 175 00:07:25,680 --> 00:07:29,090 Kabilang dito ang ilang mga file header, pinaka- ng kung saan nasaksihan namin dati. 176 00:07:29,090 --> 00:07:31,980 Kabilang dito ang kanyang sariling header file. 177 00:07:31,980 --> 00:07:35,200 >> At bilang isang bukod, bakit na double quotes dito, bilang kabaligtaran sa mga anggulo 178 00:07:35,200 --> 00:07:38,340 bracket sa linya na Ako nai-highlight doon? 179 00:07:38,340 --> 00:07:39,180 >> MAG-AARAL: [hindi marinig]. 180 00:07:39,180 --> 00:07:40,460 >> Tagapagsalita 1: Oo kaya ito ay isang lokal na file. 181 00:07:40,460 --> 00:07:44,300 Kaya kung ito ay isang lokal na file ng iyong sarili dito on line 15, halimbawa, gamitin mo 182 00:07:44,300 --> 00:07:46,570 ang double quote sa halip ng angled bracket. 183 00:07:46,570 --> 00:07:48,270 >> Ngayon ito ay uri ng kawili-wiling. 184 00:07:48,270 --> 00:07:51,830 Pansinin na aking ipinahayag isang pandaigdigang variable sa programang ito sa linya 18 185 00:07:51,830 --> 00:07:55,910 tinatawag na unang, ang ideya pagiging ito ay pagpunta sa maging isang pointer sa unang 186 00:07:55,910 --> 00:07:59,190 node sa aking naka-link na listahan, at ako ay nag nasimulan ito sa null, dahil nag ko 187 00:07:59,190 --> 00:08:02,310 hindi inilaan anumang aktwal mga node pa lamang. 188 00:08:02,310 --> 00:08:07,570 >> Kaya ito ay kumakatawan, pictorially, kung ano ang aming Nakita ng ilang sandali ang nakalipas sa larawan bilang 189 00:08:07,570 --> 00:08:10,090 na pointer sa malayong iniwan bahagi. 190 00:08:10,090 --> 00:08:12,260 Kaya ngayon, na pointer Walang isang arrow. 191 00:08:12,260 --> 00:08:14,590 Ito ay sa halip lamang null. 192 00:08:14,590 --> 00:08:17,880 Ngunit ito ay kumakatawan sa kung ano ang magiging address ng unang aktwal 193 00:08:17,880 --> 00:08:19,480 node sa listahang ito. 194 00:08:19,480 --> 00:08:22,120 Kaya naipatupad ko na ito ay isang pandaigdigang dahil, bilang makikita mo, ang lahat ng ito 195 00:08:22,120 --> 00:08:25,310 programa ay sa buhay ay ipatupad naka-link na listahan para sa akin. 196 00:08:25,310 --> 00:08:27,050 >> Ngayon Mayroon akong ilang mga modelo dito. 197 00:08:27,050 --> 00:08:31,190 Ko nagpasya upang ipatupad ang mga tampok tulad ng pagtanggal, pagpapasok, paghahanap, at 198 00:08:31,190 --> 00:08:31,740 traversal - 199 00:08:31,740 --> 00:08:35,210 ang huling lamang pagiging lakad sa buong listahan, pag-print out nito elemento. 200 00:08:35,210 --> 00:08:36,750 At ngayon, narito ang aking pangunahing routine. 201 00:08:36,750 --> 00:08:39,890 At hindi namin gastusin ng masyadong maraming panahon sa dahil ang mga ito ay isang uri ng, sana 202 00:08:39,890 --> 00:08:41,780 lumang sumbrero sa pamamagitan ng ngayon. 203 00:08:41,780 --> 00:08:45,370 >> Pupunta ako sa gawin ang mga sumusunod, habang gumagamit ang cooperates. 204 00:08:45,370 --> 00:08:47,300 Kaya isa, pupuntahan ko i-print out sa menu na ito. 205 00:08:47,300 --> 00:08:49,420 At ko na format ito bilang nang malinis bilang ako ng dati. 206 00:08:49,420 --> 00:08:52,240 Kung gumagamit ang mga uri sa isa, na nangangahulugan na gusto nilang tanggalin ang isang bagay. 207 00:08:52,240 --> 00:08:54,560 Kung gumagamit ang mga uri sa dalawa, na nangangahulugan na gusto nilang magpasok ng isang bagay. 208 00:08:54,560 --> 00:08:55,930 At iba pa. 209 00:08:55,930 --> 00:08:58,270 Pupuntahan ko pagkatapos ay i-prompt pagkatapos ay para sa isang command. 210 00:08:58,270 --> 00:08:59,300 At pagkatapos ay ako pagpunta sa gamitin GetInt. 211 00:08:59,300 --> 00:09:02,790 >> Kaya ito ay isang talagang simple menuing interface kung saan mo na lang ay i-type ang 212 00:09:02,790 --> 00:09:05,270 isang numero ng pagma-map sa isa ng mga utos. 213 00:09:05,270 --> 00:09:08,730 At ngayon, mayroon akong isang masarap na malinis ang switch pahayag na pupuntahan lumipat sa 214 00:09:08,730 --> 00:09:10,090 ano ang gumagamit na nai-type in 215 00:09:10,090 --> 00:09:12,180 At kung sila ay nag-type ng isa, idedetalye ko call na tanggalin at masira. 216 00:09:12,180 --> 00:09:14,380 Kung sila ay nag-type ng dalawa, idedetalye ko tumawag isingit at masira. 217 00:09:14,380 --> 00:09:16,490 >> At ngayon mapansin Naglagay ako sa bawat sa mga ito sa parehong linya. 218 00:09:16,490 --> 00:09:18,360 Ito ay lamang ng isang pangkakanyahan desisyon. 219 00:09:18,360 --> 00:09:20,210 Karaniwan nakakita kami ng isang bagay ganito. 220 00:09:20,210 --> 00:09:23,260 Ngunit ko lang napagpasyahan, lantaran, ang aking mga programa Tiningnan pa nababasa dahil 221 00:09:23,260 --> 00:09:25,980 ito ay lamang apat na mga kaso sa maglista lamang ito tulad nito. 222 00:09:25,980 --> 00:09:28,360 Ganap lehitimong paggamit ng estilo. 223 00:09:28,360 --> 00:09:31,480 At ako pagpunta sa gawin ito hangga't ang gumagamit ay hindi nai-type zero, na kung saan ako 224 00:09:31,480 --> 00:09:33,910 Nagpasya ang kahulugan ng nais nilang tumigil. 225 00:09:33,910 --> 00:09:36,630 >> Kaya ngayon mapansin kung ano ako pagpunta sa gawin dito. 226 00:09:36,630 --> 00:09:38,650 Pupunta ako sa magbakante ang listahan sa malas. 227 00:09:38,650 --> 00:09:40,230 Ngunit higit pa sa na sa loob lamang ng ilang sandali. 228 00:09:40,230 --> 00:09:41,640 Sabihin unang patakbuhin ang program na ito. 229 00:09:41,640 --> 00:09:45,250 Kaya hayaan mo akong gumawa ng mas malaking terminal window, dot slash listahan 0. 230 00:09:45,250 --> 00:09:49,510 Pupuntahan ko sige at ipasok sa pamamagitan ng pag-type ng dalawa, isang numero tulad ng 50, at ngayon 231 00:09:49,510 --> 00:09:51,590 makikita mo ang listahan na ngayon 50. 232 00:09:51,590 --> 00:09:53,380 At ang aking mga teksto lamang scrolled up ng isang bit. 233 00:09:53,380 --> 00:09:55,940 Kaya ngayon mapansin ang listahan ay naglalaman ng ang bilang 50. 234 00:09:55,940 --> 00:09:58,220 >> Natin gawin isa pang insert sa pamamagitan ng pagsasagawa ng dalawang. 235 00:09:58,220 --> 00:10:01,630 Sabihin type ka sa numero tulad ng isa. 236 00:10:01,630 --> 00:10:03,940 Listahan na ngayon ang isa, na sinusundan ng 50. 237 00:10:03,940 --> 00:10:06,020 Kaya ito ay lamang ng isang tekstuwal representasyon ng listahan. 238 00:10:06,020 --> 00:10:10,550 At sabihin magpasok ng isa pang numero tulad ng ang bilang 42, na sana ay 239 00:10:10,550 --> 00:10:14,620 pagpunta sa mga end up sa gitna, dahil ang program na ito sa mga partikular na uri ito 240 00:10:14,620 --> 00:10:16,320 elemento tulad ng mga pagpapasok sa kanila. 241 00:10:16,320 --> 00:10:17,220 Kaya doon kami ay may ito. 242 00:10:17,220 --> 00:10:20,730 Super simpleng programa na maaari talagang ginamit ang isang array, ngunit ko 243 00:10:20,730 --> 00:10:23,280 nangyari mang gamit ang isang naka-link na listahan kaya lang ang maaari kong pabago-bago 244 00:10:23,280 --> 00:10:24,610 lumalaki at pag-urong ito. 245 00:10:24,610 --> 00:10:28,470 >> So sabihin kumuha ng isang hitsura para sa paghahanap, kung ako magpatakbo ng command tatlo, gusto kong maghanap 246 00:10:28,470 --> 00:10:31,040 para sa, sabihin nating, ang bilang 43. 247 00:10:31,040 --> 00:10:34,190 At walang ay tila natagpuan, dahil Nakatanggap ako pabalik walang tugon. 248 00:10:34,190 --> 00:10:35,010 Kaya sabihin gawin ito muli. 249 00:10:35,010 --> 00:10:35,690 Maghanap. 250 00:10:35,690 --> 00:10:39,520 Sabihin sa paghahanap para sa 50, o sa halip maghanap para sa 42, na may isang maganda 251 00:10:39,520 --> 00:10:40,850 maliit na banayad na kahulugan. 252 00:10:40,850 --> 00:10:42,610 At nakita ko ang kahulugan ng buhay doon. 253 00:10:42,610 --> 00:10:44,990 Number 42, kung hindi mo alam ang sanggunian, ang Google ito. 254 00:10:44,990 --> 00:10:45,350 Ayos lang. 255 00:10:45,350 --> 00:10:47,130 Kaya kung ano ang program na ito tapos para sa akin? 256 00:10:47,130 --> 00:10:50,660 Ito lamang ang pinapayagan sa akin upang ipasok kaya malayo at paghahanap para sa mga sangkap. 257 00:10:50,660 --> 00:10:53,650 >> Sabihin fast forward, pagkatapos, upang na function na namin glanced sa 258 00:10:53,650 --> 00:10:55,360 sa Monday bilang isang teaser. 259 00:10:55,360 --> 00:10:59,620 Kaya ito function, inaangkin ko, mga paghahanap para sa isang elemento sa listahan sa pamamagitan ng unang 260 00:10:59,620 --> 00:11:03,830 isa, pagdikta sa gumagamit at pagkatapos ay pagtawag GetInt upang makakuha ng isang aktwal na int 261 00:11:03,830 --> 00:11:05,060 na nais mong maghanap para sa. 262 00:11:05,060 --> 00:11:06,460 >> Pagkatapos mapansin ito. 263 00:11:06,460 --> 00:11:10,690 Pupunta ako upang lumikha ng isang pansamantalang variable sa line 188 pointer na tinatawag na - 264 00:11:10,690 --> 00:11:11,270 PTR - 265 00:11:11,270 --> 00:11:12,440 sana tinatawag na ito kahit ano. 266 00:11:12,440 --> 00:11:16,140 At ito ay isang pointer sa isang node dahil sinabi ko node * doon. 267 00:11:16,140 --> 00:11:19,900 At ako Sinisimulan ito upang maging katumbas ng una kaya ko na epektibo ang aking 268 00:11:19,900 --> 00:11:22,860 daliri, kaya na magsalita, sa pinakadulo unang elemento ng listahan. 269 00:11:22,860 --> 00:11:27,460 Kaya kung ang aking kanang kamay dito ay PTR ako pagturo sa parehong bagay na una 270 00:11:27,460 --> 00:11:28,670 ay tumuturo sa. 271 00:11:28,670 --> 00:11:31,430 >> Kaya ngayon bumalik sa code, kung ano ang susunod na mangyayari - 272 00:11:31,430 --> 00:11:35,070 ito ay isang pangkaraniwang tularan kapag iterating sa ibabaw ng isang istraktura tulad ng isang 273 00:11:35,070 --> 00:11:35,970 naka-link na listahan. 274 00:11:35,970 --> 00:11:40,410 Pupunta ako sa gawin ang mga sumusunod habang pointer ay hindi katumbas ng null Kaya habang 275 00:11:40,410 --> 00:11:47,530 ang aking daliri ay hindi tumuturo sa ilang mga null halaga, kung ang pointer ng arrow n katumbas n. 276 00:11:47,530 --> 00:11:52,290 Susubukan naming mapansin muna na n ay kung ano ang gumagamit na nai-type sa bawat GetInts tumawag dito. 277 00:11:52,290 --> 00:11:54,280 >> At pointer arrow n ibig sabihin kung ano? 278 00:11:54,280 --> 00:11:59,020 Well kung pumunta kami pabalik sa mga larawan dito, kung mayroon akong isang daliri na nakaturo sa 279 00:11:59,020 --> 00:12:02,960 na unang node na naglalaman ng siyam, ang arrow mahalagang ay nangangahulugan na pumunta sa na 280 00:12:02,960 --> 00:12:08,860 node at grab ang mga halaga sa lokasyon n, sa kasong ito, ang data ng patlang na tinatawag n. 281 00:12:08,860 --> 00:12:14,120 >> Bilang isang tabi - at nakita natin ito ng ilang ng mga linggo na nakalipas kapag may isang taong nagtanong - 282 00:12:14,120 --> 00:12:18,840 syntax na ito ay bago, ngunit hindi bigyan kami ng mga kapangyarihan na namin 283 00:12:18,840 --> 00:12:20,040 ay hindi mayroon. 284 00:12:20,040 --> 00:12:25,325 Ano ang katumbas na parirala sa paggamit dot notation at bituin ng dalawang 285 00:12:25,325 --> 00:12:29,490 ng mga linggo na nakalipas kapag kami peeled likod ang layer na ito ng kaunti maaga? 286 00:12:29,490 --> 00:12:31,780 >> MAG-AARAL: [hindi marinig]. 287 00:12:31,780 --> 00:12:38,880 >> Tagapagsalita 1: Mismong, ito ay bituin, at pagkatapos ito ay bituin tuldok n, may 288 00:12:38,880 --> 00:12:41,930 panaklong dito, na kamukha, lantaran, tingin ko ng maraming 289 00:12:41,930 --> 00:12:43,320 mas misteriyoso na basahin. 290 00:12:43,320 --> 00:12:46,270 Ngunit star pointer, gaya ng lagi, Nangangahulugan ang pumunta doon. 291 00:12:46,270 --> 00:12:49,090 At sa sandaling nandoon ka, kung ano ang data field ang gusto mong i-access? 292 00:12:49,090 --> 00:12:52,730 Well mong gamitin ang tuldok notasyon upang ma-access structs isang patlang ng data, at ako 293 00:12:52,730 --> 00:12:54,140 partikular, gusto n. 294 00:12:54,140 --> 00:12:56,240 >> Nang tapat, Gusto ko magtaltalan na ito lamang ang mas mahirap basahin. 295 00:12:56,240 --> 00:12:58,080 Ito ay mas mahirap matandaan kung saan huwag ang mga panaklong pumunta, ang 296 00:12:58,080 --> 00:12:59,030 bituin at lahat ng iyon. 297 00:12:59,030 --> 00:13:02,150 Kaya mundo ang nagpatibay ng ilang mga sintaktik asukal, kaya na magsalita. 298 00:13:02,150 --> 00:13:04,740 Lamang ng isang sexy paraan ng sinasabi, ito ay katumbas ng, at 299 00:13:04,740 --> 00:13:05,970 marahil mas madaling maunawaan. 300 00:13:05,970 --> 00:13:09,600 Kung pointer ay talagang isang pointer, ang arrow pagtatanda paraan pumunta doon at mahanap 301 00:13:09,600 --> 00:13:11,890 ang patlang sa kasong ito na tinatawag n. 302 00:13:11,890 --> 00:13:13,660 >> Kaya kung makita ko ito, mapapansin kung ano ang ginagawa ko. 303 00:13:13,660 --> 00:13:17,430 Ko lang i-print out, nakita akong porsiyento i, i-plug in ang halaga para sa na int. 304 00:13:17,430 --> 00:13:20,730 Tinatawag kong matulog para sa isang segundo lamang sa uri i-pause ng mga bagay sa screen upang 305 00:13:20,730 --> 00:13:22,900 bigyan ang gumagamit ng isang pangalawang na maunawaan kung ano lamang ang nangyari. 306 00:13:22,900 --> 00:13:24,290 At pagkatapos ay ako masira. 307 00:13:24,290 --> 00:13:26,330 Kung hindi, ano ang gagawin ko? 308 00:13:26,330 --> 00:13:30,960 I-update ang pointer sa pantay na pointer ng arrow sa tabi. 309 00:13:30,960 --> 00:13:35,840 >> Kaya lamang maging malinaw, ang ibig sabihin nito pumunta doon, gamit ang aking lumang-paaralan pagtatanda. 310 00:13:35,840 --> 00:13:39,580 Kaya ito ay nangangahulugan lamang na pumunta sa kahit anong ka na tumuturo sa, na sa pinakasentro 311 00:13:39,580 --> 00:13:43,660 unang kaso ay ako na nakaturo sa ang struct may siyam sa loob nito. 312 00:13:43,660 --> 00:13:44,510 Kaya ko na nawala doon. 313 00:13:44,510 --> 00:13:47,880 At pagkatapos ay ang tuldok ay nangangahulugan notation, makuha ang halaga sa susunod. 314 00:13:47,880 --> 00:13:50,470 >> Ngunit ang halaga, kahit na ito ay iguguhit bilang isang makitid, lamang ang isang numero. 315 00:13:50,470 --> 00:13:51,720 Ito ay isang numerong address. 316 00:13:51,720 --> 00:13:55,670 Kaya ang isang linya ng code, kung nakasulat na tulad nito, mas misteriyoso 317 00:13:55,670 --> 00:14:00,190 paraan, o ganito, ang bahagyang higit pa madaling gamitin na paraan, nangangahulugan lamang ilipat ang aking mga kamay 318 00:14:00,190 --> 00:14:03,460 mula sa unang node sa susunod na isa, at pagkatapos ay sa susunod na isa, at pagkatapos ay ang 319 00:14:03,460 --> 00:14:05,320 susunod na isa, at iba pa. 320 00:14:05,320 --> 00:14:09,920 >> Kaya hindi namin tumira sa kabilang pagpapatupad ng isingit at tanggalin 321 00:14:09,920 --> 00:14:14,030 at traversal, ang unang dalawa sa na kung saan ay medyo kasangkot. 322 00:14:14,030 --> 00:14:17,010 At sa tingin ko ito ay medyo madali upang makakuha ng mawawala kapag ginagawa ito sa bibig. 323 00:14:17,010 --> 00:14:19,890 Ngunit kung ano ang maaari naming gawin dito ay subukan upang matukoy kung paano 324 00:14:19,890 --> 00:14:21,640 pinakamahusay na gawin ito biswal. 325 00:14:21,640 --> 00:14:24,800 Dahil nais kong imungkahi na kung namin nais upang ipasok elemento sa ito 326 00:14:24,800 --> 00:14:26,680 umiiral na listahan, na May limang mga sangkap - 327 00:14:26,680 --> 00:14:29,530 9, 17, 22, 26, at 33 - 328 00:14:29,530 --> 00:14:33,300 kung saan ako pagpunta sa ipatupad ito sa code, kailangan ko upang isaalang-alang kung paano pumunta 329 00:14:33,300 --> 00:14:34,160 tungkol sa paggawa nito. 330 00:14:34,160 --> 00:14:37,720 >> At Gusto ko iminumungkahi ng pagkuha hakbang na sanggol kung saan, sa kasong ito Ibig kong sabihin, kung ano ang mga 331 00:14:37,720 --> 00:14:41,090 ang mga posibleng mga sitwasyon na namin maaaring makaharap sa pangkalahatan? 332 00:14:41,090 --> 00:14:44,120 Kapag ang pagpapatupad ng insert para sa isang naka-link na listahan, ito lamang ang mangyayari na maging isang 333 00:14:44,120 --> 00:14:46,090 tiyak na halimbawa ng laki ng limang. 334 00:14:46,090 --> 00:14:50,420 Well kung gusto mong ipasok ang isang numero, gustong sabihin ang bilang ng isa, at 335 00:14:50,420 --> 00:14:53,380 pagpapanatili pinagsunod-sunod-sunod, kung saan malinaw naman ang ipinapakita ng numero ng isa upang 336 00:14:53,380 --> 00:14:55,686 pumunta sa ang partikular na halimbawa? 337 00:14:55,686 --> 00:14:56,840 Nagustuhan sa simula. 338 00:14:56,840 --> 00:15:00,030 >> Ngunit kung ano ang kawili-wiling mayroong na kung gusto mong isingit ang isa sa na ito 339 00:15:00,030 --> 00:15:04,100 listahan, kung ano ang mga espesyal na pangangailangan pointer ma-update sa malas? 340 00:15:04,100 --> 00:15:04,610 Una. 341 00:15:04,610 --> 00:15:07,830 Kaya Gusto ko magtaltalan, ito ang unang kaso na maaari naming isaalang-alang, isang 342 00:15:07,830 --> 00:15:11,140 sitwasyong kinasasangkutan ng pagpasok sa sa simula ng listahan. 343 00:15:11,140 --> 00:15:15,400 >> Sabihin pumitas off siguro bilang isang madaling o kahit mas madali ang kaso, relatibong pagsasalita. 344 00:15:15,400 --> 00:15:18,110 Ipagpalagay na gusto kong ipasok ang numero 35 sa pinagsunod-sunod-sunod. 345 00:15:18,110 --> 00:15:20,600 Ito ay malinaw naman ay kabilang banda roon. 346 00:15:20,600 --> 00:15:25,320 Kaya kung ano ang pointer ay malinaw naman pagpunta sa kailangang ma-update sa na sitwasyon? 347 00:15:25,320 --> 00:15:30,060 34 pointer ng pagiging hindi null ngunit ang mga address ng struct 348 00:15:30,060 --> 00:15:31,800 na naglalaman ng mga numero 35. 349 00:15:31,800 --> 00:15:32,750 Kaya iyon ang kaso dalawa. 350 00:15:32,750 --> 00:15:36,190 Kaya pa, ako uri ng quantizing kung magkano gumana kailangan kong gawin dito. 351 00:15:36,190 --> 00:15:39,880 >> At sa wakas, ang kaso halata gitna ay sa katunayan, sa gitna, kung gusto kong 352 00:15:39,880 --> 00:15:45,870 magpasok ng isang bagay tulad ng halimbawa 23, na napupunta sa pagitan ng 23 at 26 ang, ngunit 353 00:15:45,870 --> 00:15:48,680 ngayon ang mga bagay makakuha ng kaunti pa kasangkot dahil ano 354 00:15:48,680 --> 00:15:52,800 payo kailangang baguhin? 355 00:15:52,800 --> 00:15:56,680 Kaya 22 malinaw naman kailangang mabago dahil hindi siya maaaring tumuro sa 26 na ngayon. 356 00:15:56,680 --> 00:16:00,320 Siya ay kailangang ituro sa bagong node na Kukuha ako upang maglaan sa pamamagitan ng pagtawag 357 00:16:00,320 --> 00:16:01,770 malloc ilan o katumbas. 358 00:16:01,770 --> 00:16:05,990 >> Ngunit pagkatapos ay ako din kailangan na bagong node, 23 sa kasong ito, upang magkaroon nito pointer 359 00:16:05,990 --> 00:16:07,870 pagturo sa kanino? 360 00:16:07,870 --> 00:16:08,560 26. 361 00:16:08,560 --> 00:16:10,380 At mayroong pagpunta sa maging isang pagkakasunud-sunod ng mga operasyon dito. 362 00:16:10,380 --> 00:16:13,410 Dahil kung gagawin ko ito maloko, at ako halimbawa simula sa simula ng 363 00:16:13,410 --> 00:16:16,040 ang listahan, at ang aking layunin ay upang ipasok 23. 364 00:16:16,040 --> 00:16:18,610 At check ko, ang ibig nabibilang dito, malapit siyam? 365 00:16:18,610 --> 00:16:18,950 Hindi. 366 00:16:18,950 --> 00:16:20,670 Gumagana ba ito nabibilang dito, sa tabi ng 17? 367 00:16:20,670 --> 00:16:20,940 Hindi. 368 00:16:20,940 --> 00:16:22,530 Gumagana ba ito ay kabilang dito sa tabi ng 22? 369 00:16:22,530 --> 00:16:23,300 Oo. 370 00:16:23,300 --> 00:16:26,400 >> Ngayon kung ako ungas dito, at hindi pag-iisip na ito sa pamamagitan, maaari ko 371 00:16:26,400 --> 00:16:28,320 magtalaga ng aking bagong node para sa 23. 372 00:16:28,320 --> 00:16:32,080 Maaari kong i-update ang pointer mula sa node ang tinatawag na 22, na nakaturo 373 00:16:32,080 --> 00:16:33,080 ito sa bagong node. 374 00:16:33,080 --> 00:16:36,140 At pagkatapos ay kung ano ang kailangan kong i-update pointer sa bagong node upang maging? 375 00:16:36,140 --> 00:16:38,120 >> MAG-AARAL: [hindi marinig]. 376 00:16:38,120 --> 00:16:38,385 >> Tagapagsalita 1: Mismong. 377 00:16:38,385 --> 00:16:39,710 Pagturo sa 26. 378 00:16:39,710 --> 00:16:45,590 Ngunit dammit kung hindi ko na-update 22 ni pointer upang ituro sa tao na ito, at 379 00:16:45,590 --> 00:16:48,260 ngayon Mayroon akong orphan, ang natitira ng listahan, kaya na magsalita. 380 00:16:48,260 --> 00:16:52,140 Kaya pagkakasunud-sunod ng mga operasyon dito ay magiging mahalaga. 381 00:16:52,140 --> 00:16:55,100 >> Upang gawin ito kaya kong magnakaw, sabihin nating, anim na mga boluntaryo. 382 00:16:55,100 --> 00:16:57,650 At sabihin makita kung hindi namin maaaring gawin ito biswal sa halip ng code-matalino. 383 00:16:57,650 --> 00:16:59,330 At kami ay may ilang mga kaibig-ibig ng stress bola para sa iyo ngayong araw. 384 00:16:59,330 --> 00:17:02,510 OK, kung paano tungkol sa isa, dalawa, sa bumalik - sa dulo doon. 385 00:17:02,510 --> 00:17:04,530 tatlo, apat, pareho ng sa iyo guys sa dulo. 386 00:17:04,530 --> 00:17:05,579 At lima, anim. 387 00:17:05,579 --> 00:17:05,839 Oo naman. 388 00:17:05,839 --> 00:17:06,450 Limang at anim. 389 00:17:06,450 --> 00:17:08,390 Ang lahat ng mga karapatan at kami ay sa iyo guys susunod na pagkakataon. 390 00:17:08,390 --> 00:17:09,640 Ang lahat ng mga karapatan, dumating sa up. 391 00:17:09,640 --> 00:17:12,010 392 00:17:12,010 --> 00:17:14,819 >> Ang lahat ng mga karapatan, dahil ikaw ay hanggang dito muna, Gusto mo bang maging ang isa awkwardly 393 00:17:14,819 --> 00:17:16,119 sa Google Glass dito? 394 00:17:16,119 --> 00:17:19,075 Ang lahat ng mga karapatan, sa gayon, OK, Glass, record ng video. 395 00:17:19,075 --> 00:17:22,720 396 00:17:22,720 --> 00:17:24,589 OK, ikaw ay handa na upang patakbuhin. 397 00:17:24,589 --> 00:17:27,950 >> Ang lahat ng mga karapatan, kaya kung ikaw guys ay maaaring dumating sa ibabaw dito, ako handa nang maaga 398 00:17:27,950 --> 00:17:30,110 ilang numero. 399 00:17:30,110 --> 00:17:31,240 Ang lahat ng mga karapatan, darating sa paglipas dito. 400 00:17:31,240 --> 00:17:33,440 At bakit hindi ka pumunta ng kaunti higit na paraan. 401 00:17:33,440 --> 00:17:35,520 At sabihin makita, kung ano ang iyong pangalan, gamit ang Google Glass? 402 00:17:35,520 --> 00:17:35,910 >> MAG-AARAL: Ben. 403 00:17:35,910 --> 00:17:36,230 >> Tagapagsalita 1: Ben? 404 00:17:36,230 --> 00:17:38,380 OK, Ben, ikaw ang magiging unang, literal. 405 00:17:38,380 --> 00:17:40,580 Kaya kami ay pagpunta sa magpadala sa iyo sa dulo ng entablado. 406 00:17:40,580 --> 00:17:41,670 Ang lahat ng mga karapatan, at ang iyong pangalan? 407 00:17:41,670 --> 00:17:41,990 >> MAG-AARAL: Jason. 408 00:17:41,990 --> 00:17:44,530 >> Tagapagsalita 1: Jason, OK bibigyan ka maging numero siyam. 409 00:17:44,530 --> 00:17:46,700 Kaya kung nais mong sundin Ben na paraan. 410 00:17:46,700 --> 00:17:47,010 >> MAG-AARAL: Jill. 411 00:17:47,010 --> 00:17:49,630 >> Tagapagsalita 1: Jill, ikaw ay pagpunta sa maging 17, na kung Gusto ko nagawa ito nang higit pa 412 00:17:49,630 --> 00:17:51,260 intelligently, nais kong magkaroon Magsimula sa kabilang dulo. 413 00:17:51,260 --> 00:17:52,370 Pumunta ka na paraan. 414 00:17:52,370 --> 00:17:53,030 22. 415 00:17:53,030 --> 00:17:53,670 At ikaw? 416 00:17:53,670 --> 00:17:53,980 >> MAG-AARAL: Mary. 417 00:17:53,980 --> 00:17:56,130 >> Tagapagsalita 1: Mary, magiging 22. 418 00:17:56,130 --> 00:17:58,420 At ang iyong pangalan ay? 419 00:17:58,420 --> 00:17:58,810 >> MAG-AARAL: Chris. 420 00:17:58,810 --> 00:18:00,100 >> Tagapagsalita 1: Chris, magiging 26. 421 00:18:00,100 --> 00:18:00,740 At bilang wakas pagkatapos. 422 00:18:00,740 --> 00:18:01,400 >> MAG-AARAL: Diana. 423 00:18:01,400 --> 00:18:02,670 >> Tagapagsalita 1: Diana, magiging 34. 424 00:18:02,670 --> 00:18:03,920 Kaya dumating ka sa paglipas dito. 425 00:18:03,920 --> 00:18:06,360 >> Ang lahat ng mga karapatan, kaya maperpekto pinagsunod-sunod mag-order na. 426 00:18:06,360 --> 00:18:09,600 At sabihin sige at gawin ito sa gayon maaari naming talaga - 427 00:18:09,600 --> 00:18:11,720 Ben handa ka lamang uri ng hinahanap out sa wala kahit saan doon. 428 00:18:11,720 --> 00:18:15,670 OK, kaya sabihin sige at ilarawan ito paggamit ng mga armas, tulad ng ako ay, eksakto, 429 00:18:15,670 --> 00:18:16,250 ano ang nangyayari sa. 430 00:18:16,250 --> 00:18:19,540 Kaya't sige at bigyan ang inyong sarili ng isang paa o dalawang sa pagitan ng inyong sarili. 431 00:18:19,540 --> 00:18:22,900 At sige at ituro sa isa kamay upang kung sinuman ang dapat mong i-pagturo sa 432 00:18:22,900 --> 00:18:23,470 batay sa mga ito. 433 00:18:23,470 --> 00:18:25,890 At kung ikaw ay walang bisa lamang ituro ang diretso pababa sa sahig. 434 00:18:25,890 --> 00:18:27,690 OK, kaya mabuti. 435 00:18:27,690 --> 00:18:32,290 >> Kaya ngayon kami ay may isang naka-link na listahan, at ipaalam sa akin ipanukala na kailangan ko i-play ang papel na ginagampanan ng 436 00:18:32,290 --> 00:18:35,110 PTR, kaya hindi ako ay mag-abala nagdadala ito sa paligid. 437 00:18:35,110 --> 00:18:37,830 At pagkatapos ay - isang tao nakababagod convention - Maaari kang tumawag ito anumang bagay na gusto mo - 438 00:18:37,830 --> 00:18:39,800 hinalinhan pointer, pointer pred - 439 00:18:39,800 --> 00:18:43,930 ito lamang ay ang palayaw na binigay namin sa aming sample code sa aking kaliwang kamay. 440 00:18:43,930 --> 00:18:47,240 Ang iba pang mga kamay na pagpunta sa ma-pagpapanatiling subaybayan ng kung sino sino ay sa 441 00:18:47,240 --> 00:18:48,400 sumusunod na mga sitwasyon. 442 00:18:48,400 --> 00:18:52,390 >> Kaya ipagpalagay, una, gusto kong i-off ang lakas ng loob na ang unang halimbawa ng pagpasok, sabihin 443 00:18:52,390 --> 00:18:54,330 20, sa listahan. 444 00:18:54,330 --> 00:18:57,160 Kaya pupuntahan ko kailangan ng isang tao upang isama ang numero ng 20 para sa amin. 445 00:18:57,160 --> 00:18:58,950 Kaya kailangan kong mag-malloc isang tao mula sa madla. 446 00:18:58,950 --> 00:18:59,380 Halika sa up. 447 00:18:59,380 --> 00:19:00,340 Ano ang inyong pangalan? 448 00:19:00,340 --> 00:19:01,300 >> MAG-AARAL: Brian. 449 00:19:01,300 --> 00:19:05,270 >> Tagapagsalita 1: Brian, lahat ng karapatan, kaya mo ang magiging node na naglalaman ng 20. 450 00:19:05,270 --> 00:19:06,810 Ang lahat ng mga karapatan, darating sa paglipas dito. 451 00:19:06,810 --> 00:19:10,025 At malinaw naman, kung saan Brian ay nabibilang? 452 00:19:10,025 --> 00:19:12,190 Kaya, sa gitna ng - talaga, maghintay ng isang minuto. 453 00:19:12,190 --> 00:19:13,420 Ginagawa namin ito out sa pagkakasunud-sunod. 454 00:19:13,420 --> 00:19:17,170 Gumagawa kami ng ito ng maraming mas mahirap kaysa sa kinakailangan nito upang maging sa unang. 455 00:19:17,170 --> 00:19:21,210 OK, kami ay pagpunta sa libreng Brian at realloc Brian bilang lima. 456 00:19:21,210 --> 00:19:23,680 >> OK, kaya ngayon gusto naming isingit Brian bilang lima. 457 00:19:23,680 --> 00:19:25,960 Kaya dumating sa paglipas dito sa tabi ng Ben para lamang ng ilang sandali. 458 00:19:25,960 --> 00:19:28,250 At maaari mong marahil sabihin kuwento kung saan ito ay pagpunta. 459 00:19:28,250 --> 00:19:30,500 Ngunit sabihin isip-isipin ang pagkakasunud-sunod ng mga operasyon. 460 00:19:30,500 --> 00:19:32,880 At ito ay tiyak ang visual na pupuntahan pumila 461 00:19:32,880 --> 00:19:34,080 may sample na code. 462 00:19:34,080 --> 00:19:40,120 Kaya dito ko pa PTR pagturo sa una hindi sa Ben, per se, ngunit sa kahit anong 463 00:19:40,120 --> 00:19:43,245 Pinahahalagahan siya ay naglalaman, na sa kasong ito ay - kung ano ang iyong pangalan muli? 464 00:19:43,245 --> 00:19:43,670 >> MAG-AARAL: Jason. 465 00:19:43,670 --> 00:19:47,350 >> Tagapagsalita 1: Jason, kaya pareho Ben at ako ay tumuturo sa Jason sa panahon na ito. 466 00:19:47,350 --> 00:19:49,700 Kaya ngayon mayroon akong upang matukoy, kung saan ay Brian nabibilang? 467 00:19:49,700 --> 00:19:53,500 Kaya ang tanging bagay Mayroon akong access sa ngayon ay ang kanyang mga item n data. 468 00:19:53,500 --> 00:19:58,280 Kaya pupuntahan ko check, ay Brian mas mababa sa Jason? 469 00:19:58,280 --> 00:19:59,770 Ang sagot ay totoo. 470 00:19:59,770 --> 00:20:03,680 >> Kaya kung ano ngayon ay kailangang mangyari, sa tamang pagkakasunud-sunod? 471 00:20:03,680 --> 00:20:07,120 Kailangan kong i-update ang kung gaano karaming mga payo sa kabuuan sa kuwentong ito? 472 00:20:07,120 --> 00:20:10,720 Saan ang aking mga kamay ay pa rin sa pagturo Jason, at ang iyong mga kamay - kung nais mong 473 00:20:10,720 --> 00:20:12,930 ilagay ang iyong mga kamay tulad ng, uri ng, ko hindi alam, isang tandang pananong. 474 00:20:12,930 --> 00:20:14,070 OK, mabuti. 475 00:20:14,070 --> 00:20:15,670 >> Ang lahat ng mga karapatan, sa gayon mayroon kang ng ilang mga kandidato. 476 00:20:15,670 --> 00:20:20,500 Alinman sa Ben o ako o Brian o Jason o ang iba, na 477 00:20:20,500 --> 00:20:21,370 payo kailangang baguhin? 478 00:20:21,370 --> 00:20:23,260 Gaano karaming sa kabuuang? 479 00:20:23,260 --> 00:20:24,080 >> OK, kaya dalawa. 480 00:20:24,080 --> 00:20:27,090 Aking pointer ay hindi talagang mahalaga ngayon dahil ako lamang pansamantalang. 481 00:20:27,090 --> 00:20:31,370 Kaya ito ay ang dalawang guys, siguro, parehong Ben at Brian. 482 00:20:31,370 --> 00:20:34,410 Kaya ipaalam sa akin imungkahi na-update namin Ben, dahil siya ang unang. 483 00:20:34,410 --> 00:20:36,350 Ang unang elemento ng listahang ito ngayon ay pagpunta sa maging Brian. 484 00:20:36,350 --> 00:20:38,070 Kaya Ben punto sa Brian. 485 00:20:38,070 --> 00:20:39,320 OK, ngayon kung ano? 486 00:20:39,320 --> 00:20:41,950 487 00:20:41,950 --> 00:20:43,460 >> Sino ang makakakuha ng tulis sa kanino? 488 00:20:43,460 --> 00:20:44,710 >> MAG-AARAL: [hindi marinig]. 489 00:20:44,710 --> 00:20:46,180 >> Tagapagsalita 1: OK kaya Brian ay upang ituro sa Jason. 490 00:20:46,180 --> 00:20:48,360 Ngunit na Nawala ko ang track na ng pointer? 491 00:20:48,360 --> 00:20:49,980 Ko alam kung saan ay Jason? 492 00:20:49,980 --> 00:20:50,790 >> MAG-AARAL: [hindi marinig]. 493 00:20:50,790 --> 00:20:52,620 >> Tagapagsalita 1: gagawin ko, dahil ako ang pansamantalang pointer. 494 00:20:52,620 --> 00:20:55,110 At siguro, hindi ko pa nabago upang ituro sa mga bagong node. 495 00:20:55,110 --> 00:20:58,300 Kaya maaari naming simpleng Brian punto sa kung sinuman ako na tumuturo sa. 496 00:20:58,300 --> 00:20:59,000 At tapos na kami. 497 00:20:59,000 --> 00:21:01,890 Kaya isa kaso, sa pagpapasok ng simula ng listahan. 498 00:21:01,890 --> 00:21:02,950 Mayroong dalawang pangunahing mga hakbang. 499 00:21:02,950 --> 00:21:06,750 Ang isa, mayroon kaming upang i-update Ben, at pagkatapos ay kami ay mayroon ding upang i-update Brian. 500 00:21:06,750 --> 00:21:09,230 At pagkatapos ay hindi ko na kailangang mag-abala traipsing sa pamamagitan ng ang natitirang bahagi ng 501 00:21:09,230 --> 00:21:12,680 listahan, dahil kami ay natagpuan ang kanyang lokasyon, dahil siya ay pag-aari ng 502 00:21:12,680 --> 00:21:14,080 kaliwa ng unang elemento. 503 00:21:14,080 --> 00:21:15,400 >> Ang lahat ng mga karapatan, kaya medyo tuwiran. 504 00:21:15,400 --> 00:21:18,110 Sa katunayan, tulad ng pakiramdam ng hindi namin halos paggawa ito masyadong kumplikadong. 505 00:21:18,110 --> 00:21:20,240 Kaya natin ngayon pumitas off ang dulo ng listahan, at makita kung saan 506 00:21:20,240 --> 00:21:21,380 ang pagiging kumplikado ng mga pagsisimula. 507 00:21:21,380 --> 00:21:24,560 Kaya kung ngayon, ako alloc mula sa madla. 508 00:21:24,560 --> 00:21:25,540 Sinuman na nais upang i-play 55? 509 00:21:25,540 --> 00:21:26,700 Ang lahat ng mga karapatan, Nakita ko ang iyong unang kamay. 510 00:21:26,700 --> 00:21:29,620 Halika sa up. 511 00:21:29,620 --> 00:21:30,030 Oo. 512 00:21:30,030 --> 00:21:31,177 Ano ang inyong pangalan? 513 00:21:31,177 --> 00:21:32,310 >> MAG-AARAL: [hindi marinig]. 514 00:21:32,310 --> 00:21:33,240 >> Tagapagsalita 1: Habata. 515 00:21:33,240 --> 00:21:33,890 OK, dumating sa up. 516 00:21:33,890 --> 00:21:35,730 Ikaw ang numero 55. 517 00:21:35,730 --> 00:21:37,820 Kaya mo, siyempre, nabibilang sa dulo ng listahan. 518 00:21:37,820 --> 00:21:41,850 Kaya natin i-replay ang simulation sa akin pagiging PTR para lamang ng ilang sandali. 519 00:21:41,850 --> 00:21:44,050 Kaya unang pupuntahan ko ituro sa kahit anong Ben ay tumuturo sa. 520 00:21:44,050 --> 00:21:45,900 Kami ay parehong nagtuturo ngayon sa Brian. 521 00:21:45,900 --> 00:21:48,420 Kaya 55 ay hindi mas mababa sa limang. 522 00:21:48,420 --> 00:21:52,510 Kaya ako ng pagpunta sa i-update ang sarili ko sa pamamagitan ng tumuturo sa susunod na pointer ni Brian, na 523 00:21:52,510 --> 00:21:54,450 ngayon ay siyempre Jason. 524 00:21:54,450 --> 00:21:57,310 55 ay hindi mas mababa sa siyam, kaya Pupunta ako sa i-update ang PTR. 525 00:21:57,310 --> 00:21:58,890 Pupunta ako sa i-update ang PTR. 526 00:21:58,890 --> 00:22:02,290 Pupunta ako sa i-update ang PTR Ako pagpunta sa i-update ang PTR. 527 00:22:02,290 --> 00:22:05,060 At pupuntahan ko - Hmm, kung ano ang ang iyong pangalan muli? 528 00:22:05,060 --> 00:22:05,560 >> MAG-AARAL: Diana. 529 00:22:05,560 --> 00:22:09,190 >> Tagapagsalita 1: Diana ay pagturo, siyempre, sa null sa kanyang kaliwang kamay. 530 00:22:09,190 --> 00:22:13,030 Kaya kung saan ang ibig Habata talaga nabibilang malinaw? 531 00:22:13,030 --> 00:22:15,050 Sa kaliwa, dito. 532 00:22:15,050 --> 00:22:19,460 Kaya paano ko malaman upang ilagay ang kanyang Dito Sa tingin ko ko na screwed up. 533 00:22:19,460 --> 00:22:22,420 Dahil kung ano ang PTR art sandaling ito sa oras? 534 00:22:22,420 --> 00:22:23,240 Null. 535 00:22:23,240 --> 00:22:25,580 Kaya kahit na, biswal, aming makakaya malinaw naman makita ang lahat ng mga 536 00:22:25,580 --> 00:22:26,610 guys dito sa entablado. 537 00:22:26,610 --> 00:22:29,680 Hindi ko na pinananatiling track ng dating tao sa listahan. 538 00:22:29,680 --> 00:22:33,210 Hindi ko magkaroon ng isang daliri pagturo out, sa kasong ito, ang node bilang 34. 539 00:22:33,210 --> 00:22:34,760 >> Kaya sabihin talagang simulan ito sa paglipas ng. 540 00:22:34,760 --> 00:22:37,560 Kaya ngayon ko talagang kailangan isang pangalawang lokal na variable. 541 00:22:37,560 --> 00:22:40,980 At ito ay kung ano ang makikita mo sa aktwal na sample C code, kung saan bilang pumunta ko, 542 00:22:40,980 --> 00:22:45,860 kapag ako ay nag-update ang aking kanang kamay upang ituro Jason, at dahil doon umaalis Brian sa likod, ko 543 00:22:45,860 --> 00:22:51,440 mas mahusay na simulan ang paggamit ng aking kaliwang kamay upang update kung saan ako ay, sa gayon ay bilang pumunta ko 544 00:22:51,440 --> 00:22:52,700 sa pamamagitan ng listahan na ito - 545 00:22:52,700 --> 00:22:55,040 higit pa kaysa awkwardly ko nilalayon ngayon dito biswal - 546 00:22:55,040 --> 00:22:56,740 Pupuntahan ko na makuha ang dulo ng listahan. 547 00:22:56,740 --> 00:23:00,020 >> Kamay na ito ay pa rin walang bisa, na kung saan ay medyo walang silbi, maliban sa upang ipahiwatig 548 00:23:00,020 --> 00:23:02,980 Ako ay malinaw na sa dulo ng listahan, ngunit ngayon ay hindi bababa sa Mayroon akong ito 549 00:23:02,980 --> 00:23:08,270 hinalinhan pointer na nakaturo dito, kaya ngayon kung ano ang mga kamay at kung ano ang payo kailangan 550 00:23:08,270 --> 00:23:10,150 ma-update? 551 00:23:10,150 --> 00:23:13,214 Kaninong mga kamay ang nais mong i-reconfigure ang unang? 552 00:23:13,214 --> 00:23:15,190 >> MAG-AARAL: [hindi marinig]. 553 00:23:15,190 --> 00:23:16,220 >> Tagapagsalita 1: OK, kaya ni Diana. 554 00:23:16,220 --> 00:23:21,110 Saan mo gustong upang ituro Kaliwa pointer ni Diana sa? 555 00:23:21,110 --> 00:23:23,620 Sa 55, siguro, kaya na kami ipinasok doon. 556 00:23:23,620 --> 00:23:25,560 At kung saan dapat 55 pointer pumunta? 557 00:23:25,560 --> 00:23:27,000 Down, na kumakatawan null. 558 00:23:27,000 --> 00:23:28,890 At ang aking mga kamay, sa puntong ito, hindi magawa mahalaga dahil sila ay lamang 559 00:23:28,890 --> 00:23:30,070 pansamantalang variable. 560 00:23:30,070 --> 00:23:31,030 Kaya ngayon tapos na kami. 561 00:23:31,030 --> 00:23:34,650 >> Kaya ang karagdagang kumplikado doon - at ito ay hindi mahirap na ipatupad, 562 00:23:34,650 --> 00:23:38,660 ngunit kailangan namin ng isang pangalawang variable upang gawing Siguraduhin na bago ilipat ko ang aking karapatan 563 00:23:38,660 --> 00:23:42,140 banda, i-update ko ang halaga ng aking kaliwa banda, pred pointer sa kasong ito, kaya 564 00:23:42,140 --> 00:23:45,860 na mayroon akong isang trailing pointer upang masubaybayan kung saan ako ay. 565 00:23:45,860 --> 00:23:49,360 Ngayon bilang isang bukod, kung pinag-iisipan mo ito sa pamamagitan ng, ito nararamdaman tulad ng ito ay isang 566 00:23:49,360 --> 00:23:51,490 maliit na nakakainis na magkaroon upang panatilihing subaybayan ito ng kaliwang kamay. 567 00:23:51,490 --> 00:23:54,015 >> Ano ang gagawin ng isa pang solusyon upang ang problemang ito ay naging? 568 00:23:54,015 --> 00:23:56,500 Kung nakukuha mo sa disenyo ng data Istraktura ng pinag-uusapan natin 569 00:23:56,500 --> 00:23:59,630 sa pamamagitan ng ngayon? 570 00:23:59,630 --> 00:24:02,690 Kung ito lamang ang uri ng pakiramdam ng isang maliit na nakakainis na magkaroon, i, dalawang payo 571 00:24:02,690 --> 00:24:08,430 pagpunta sa pamamagitan ng mga listahan, sino pa ang maaaring pa, sa isang perpektong mundo, pinananatili 572 00:24:08,430 --> 00:24:10,160 impormasyon na kailangan namin? 573 00:24:10,160 --> 00:24:11,360 Oo? 574 00:24:11,360 --> 00:24:12,610 >> MAG-AARAL: [hindi marinig]. 575 00:24:12,610 --> 00:24:15,160 576 00:24:15,160 --> 00:24:16,150 >> Tagapagsalita 1: Mismong. 577 00:24:16,150 --> 00:24:19,130 Right kaya walang aktwal na isang kawili-wiling mikrobiyo ng isang ideya. 578 00:24:19,130 --> 00:24:22,470 At ito ideya ng isang nakaraang pointer, pagturo sa nakaraang elemento. 579 00:24:22,470 --> 00:24:25,580 Paano kung ko lang na katawanin sa loob ng listahan mismo? 580 00:24:25,580 --> 00:24:27,810 At ito ay pagpunta sa maging mahirap upang mailarawan ang ito nang walang ang lahat ng mga papel 581 00:24:27,810 --> 00:24:28,830 pagbagsak sa sahig. 582 00:24:28,830 --> 00:24:31,860 Ngunit ipagpalagay na ang mga guys ginamit ang parehong ng kanilang mga kamay upang magkaroon ng isang nakaraang 583 00:24:31,860 --> 00:24:35,950 pointer, at ng susunod na pointer, at dahil doon pagpapatupad ng kung ano ang makikita namin tumawag sa isang doble 584 00:24:35,950 --> 00:24:36,830 naka-link na listahan. 585 00:24:36,830 --> 00:24:41,090 Iyon ay magpapahintulot sa akin upang ayusin ng rewind, mas madali nang hindi sa akin, ang 586 00:24:41,090 --> 00:24:43,800 programmer, pagkakaroon upang panatilihing subaybayan nang mano-mano - 587 00:24:43,800 --> 00:24:44,980 tunay na mano-manong - 588 00:24:44,980 --> 00:24:47,280 ng kung saan ako ay naging dati sa listahan. 589 00:24:47,280 --> 00:24:48,110 Kaya hindi namin gawin iyon. 590 00:24:48,110 --> 00:24:50,950 Susubukan naming panatilihin itong simple dahil iyon ang pagpunta sa dumating sa isang presyo, dalawang beses bilang 591 00:24:50,950 --> 00:24:53,450 magkano ang space para sa mga payo, kung gusto mo ng pangalawang isa. 592 00:24:53,450 --> 00:24:55,760 Ngunit iyon sa katunayan ng isang karaniwang istraktura ng data na kilala bilang isang 593 00:24:55,760 --> 00:24:57,410 doble na naka-link listahan. 594 00:24:57,410 --> 00:25:01,310 >> Tayo'y gawin ang panghuling halimbawa dito at ilagay mga guys out ng kanilang paghihirap. 595 00:25:01,310 --> 00:25:03,270 Kaya malloc 20. 596 00:25:03,270 --> 00:25:05,320 Halika sa up mula sa pasilyo doon. 597 00:25:05,320 --> 00:25:06,280 Ang lahat ng mga karapatan, kung ano ang iyong pangalan? 598 00:25:06,280 --> 00:25:07,440 >> MAG-AARAL: [hindi marinig]. 599 00:25:07,440 --> 00:25:07,855 >> Tagapagsalita 1: Paumanhin? 600 00:25:07,855 --> 00:25:08,480 >> MAG-AARAL: [hindi marinig]. 601 00:25:08,480 --> 00:25:09,410 >> Tagapagsalita 1: Demeron? 602 00:25:09,410 --> 00:25:10,230 OK dumating sa up. 603 00:25:10,230 --> 00:25:11,910 Ikaw ay magiging 20. 604 00:25:11,910 --> 00:25:14,720 Ikaw ay malinaw naman pagpunta sa nabibilang sa pagitan ng 17 at 22. 605 00:25:14,720 --> 00:25:16,150 Kaya hayaan mo akong malaman ang aking mga aralin. 606 00:25:16,150 --> 00:25:18,150 Pupunta ako upang simulan ang pointer pagturo sa Brian. 607 00:25:18,150 --> 00:25:21,190 At pupuntahan ko ang aking kaliwang kamay i-update lamang sa Brian bilang ilipat ko sa 608 00:25:21,190 --> 00:25:23,600 Jason, checking ang ibig 20 mas mababa sa siyam? 609 00:25:23,600 --> 00:25:24,060 Hindi. 610 00:25:24,060 --> 00:25:25,430 20 Ay mas mababa sa 17? 611 00:25:25,430 --> 00:25:25,880 Hindi. 612 00:25:25,880 --> 00:25:27,450 20 Ay mas mababa sa 22? 613 00:25:27,450 --> 00:25:28,440 Oo. 614 00:25:28,440 --> 00:25:34,070 Kaya kung ano ang payo o mga kamay kailangang baguhin kung saan sila nagtuturo ngayon? 615 00:25:34,070 --> 00:25:37,070 >> Kaya maaari naming gawin 17 na tumuturo sa 20. 616 00:25:37,070 --> 00:25:37,860 Kaya na fine. 617 00:25:37,860 --> 00:25:40,080 Saan nagpupunta ang mga nais naming ituro ang iyong pointer ngayon? 618 00:25:40,080 --> 00:25:41,330 Sa 22. 619 00:25:41,330 --> 00:25:45,410 At alam namin kung saan 22 ay, muli salamat sa aking pansamantalang pointer. 620 00:25:45,410 --> 00:25:46,760 Kaya hindi namin OK doon. 621 00:25:46,760 --> 00:25:49,440 Kaya dahil sa ito pansamantalang imbakan Ko na pinananatiling track ng kung saan ang lahat ng tao ay. 622 00:25:49,440 --> 00:25:55,055 At ngayon maaari mong biswal pumunta sa kung saan nabibilang mo, at ngayon ay kailangan naming 1, 2, 3, 623 00:25:55,055 --> 00:25:58,410 4, 5, 6, 7, 8, 9 ng stress ball, at isang ikot ng papuri para sa 624 00:25:58,410 --> 00:25:59,770 mga guys, kung magagawa namin. 625 00:25:59,770 --> 00:26:00,410 Maayos na Natapos. 626 00:26:00,410 --> 00:26:05,320 >> [Palakpakan] 627 00:26:05,320 --> 00:26:06,330 >> Tagapagsalita 1: Ang lahat ng mga karapatan. 628 00:26:06,330 --> 00:26:09,860 At maaari mong panatilihin ang mga piraso ng papel bilang mementos. 629 00:26:09,860 --> 00:26:15,930 >> Ang lahat ng mga karapatan, sa gayon, nagtitiwala sa akin ito ng maraming mas madaling maglakad sa pamamagitan ng na may 630 00:26:15,930 --> 00:26:17,680 mga kawani na tao kaysa ito ay may aktwal na code. 631 00:26:17,680 --> 00:26:22,690 Ngunit kung anong makikita mo sa loob lamang ng ilang sandali ngayon, ay ang parehong - oh, salamat sa iyo. 632 00:26:22,690 --> 00:26:23,630 Salamat sa iyo - 633 00:26:23,630 --> 00:26:29,360 ay na makikita mo na ang parehong data istraktura, isang naka-link na listahan, maaari talaga 634 00:26:29,360 --> 00:26:33,200 magamit bilang isang gusali block sa kahit na higit pa sopistikadong mga istraktura ng data. 635 00:26:33,200 --> 00:26:37,620 >> At napagtanto masyado ang tema dito ay na talagang ipinakilala namin ang higit pa 636 00:26:37,620 --> 00:26:40,060 pagiging kumplikado sa pagpapatupad ng algorithm na ito. 637 00:26:40,060 --> 00:26:43,940 Insertion, at kung namin nagpunta sa pamamagitan nito, pagtanggal at searching, ay isang maliit na 638 00:26:43,940 --> 00:26:46,660 mas komplikado kaysa ito ay may isang array. 639 00:26:46,660 --> 00:26:48,040 Ngunit kami makakuha ng ilang dynamism. 640 00:26:48,040 --> 00:26:50,180 Kumuha kami ng isang agpang istraktura ng data. 641 00:26:50,180 --> 00:26:54,010 >> Ngunit muli, babayaran namin ang isang presyo ng pagkakaroon ng ilang mga karagdagang kumplikado, parehong sa 642 00:26:54,010 --> 00:26:54,910 pagpapatupad ng mga ito. 643 00:26:54,910 --> 00:26:56,750 At kami ay ibinigay up random access. 644 00:26:56,750 --> 00:27:00,450 At upang maging matapat, mayroong ilang mga hindi magaling linisin slide ang maaari kong bigyan ka na 645 00:27:00,450 --> 00:27:03,120 sabi dito ay kung bakit ang isang naka-link na listahan ay mas mahusay kaysa sa isang array. 646 00:27:03,120 --> 00:27:04,100 At iwanan ito sa na. 647 00:27:04,100 --> 00:27:07,520 Dahil ang tema reoccurring ngayon, kahit na higit pa kaya sa mga darating na linggo, ay 648 00:27:07,520 --> 00:27:10,200 na mayroong hindi kinakailangang isang tamang sagot. 649 00:27:10,200 --> 00:27:13,830 >> Ito ay kung bakit mayroon kaming ang nakahiwalay axis ng disenyo para sa mga hanay ng problema. 650 00:27:13,830 --> 00:27:17,700 Ito ay magiging lubhang konteksto sensitive kung nais mong gamitin ang data na ito 651 00:27:17,700 --> 00:27:21,750 istraktura o na ang isa, at kalooban ito depende sa kung ano ang mahalaga sa iyo sa mga tuntunin 652 00:27:21,750 --> 00:27:24,620 ng mga mapagkukunan at kumplikado. 653 00:27:24,620 --> 00:27:28,830 >> Ngunit ipaalam sa akin imungkahi na ang perpektong data istraktura, ang banal na Kopita, ay magiging 654 00:27:28,830 --> 00:27:32,200 isang bagay na pare-pareho ang oras, hindi isinasaalang-alang ng kung magkano ang mga bagay-bagay ay 655 00:27:32,200 --> 00:27:36,940 sa loob nito, hindi magiging kahanga-hangang kung ang isang data istraktura ibinalik na sagot sa 656 00:27:36,940 --> 00:27:37,920 pare-pareho ang panahon. 657 00:27:37,920 --> 00:27:38,330 Oo. 658 00:27:38,330 --> 00:27:40,110 Salita na ito ay nasa iyong napakalaking diksyunaryo. 659 00:27:40,110 --> 00:27:41,550 O wala na, ang salitang ito ay hindi. 660 00:27:41,550 --> 00:27:43,270 O anumang katulad na problema doon. 661 00:27:43,270 --> 00:27:46,360 Well sabihin makita kung hindi namin maaari nang hindi bababa sa kumuha ng isang hakbang patungo sa na. 662 00:27:46,360 --> 00:27:50,190 >> Hayaan akong magpanukala ng isang bagong istraktura ng data na maaaring gamitin para sa iba't ibang mga bagay, 663 00:27:50,190 --> 00:27:52,260 sa kasong ito na tinatawag na hash table. 664 00:27:52,260 --> 00:27:55,590 At sa gayon kami ay talagang pabalik sa glancing sa isang array, sa kasong ito, at 665 00:27:55,590 --> 00:28:00,550 medyo mang, ko ang iginuhit na ito hash talahanayan bilang isang array na may isang uri ng isang 666 00:28:00,550 --> 00:28:02,810 dalawang-dimensional array - 667 00:28:02,810 --> 00:28:05,410 o sa halip ito ay itinatanghal dito bilang isang dalawang dimensional array - ngunit ito lamang ang 668 00:28:05,410 --> 00:28:10,770 isang array ng size 26, tulad na kung namin tawagan ang array talahanayan, table bracket 669 00:28:10,770 --> 00:28:12,440 zero ay ang rektanggulo sa tuktok. 670 00:28:12,440 --> 00:28:15,090 Table 25 bracket ay ang parihaba sa ibaba. 671 00:28:15,090 --> 00:28:18,620 At ito ay kung paano ako gumuhit ng data istraktura na kung saan gusto kong mag-imbak 672 00:28:18,620 --> 00:28:19,790 tao pangalan. 673 00:28:19,790 --> 00:28:24,370 >> Kaya halimbawa, at hindi ko ay gumuhit ang buong bagay dito sa overhead, kung ako 674 00:28:24,370 --> 00:28:29,160 nagkaroon ito array, na sa ngayon ay pupuntahan ko tawagan ng hash talahanayan, at ito ay muli 675 00:28:29,160 --> 00:28:31,360 lokasyon zero. 676 00:28:31,360 --> 00:28:34,840 Ito dito ay lokasyon isa, at iba pa. 677 00:28:34,840 --> 00:28:37,880 Inaangkin ko na gusto kong gamitin ang data na ito istraktura, alang-alang sa talakayan, 678 00:28:37,880 --> 00:28:42,600 mag-imbak ng mga tao mga pangalan, Alice at Bob at Charlie at ibang tulad ng mga pangalan. 679 00:28:42,600 --> 00:28:46,110 Kaya sa tingin ng mga ito ngayon bilang ang Beginnings ng, sabihin nating, isang diksyunaryo 680 00:28:46,110 --> 00:28:47,520 na may maraming mga salita. 681 00:28:47,520 --> 00:28:49,435 Mangyari ang mga ito upang maging pangalan sa aming mga halimbawa dito. 682 00:28:49,435 --> 00:28:52,560 At ito ay ang lahat ng masyadong dyermeyn, marahil, upang pagpapatupad ng isang spell checker, bilang namin 683 00:28:52,560 --> 00:28:54,400 Maaaring para sa problema itakda anim. 684 00:28:54,400 --> 00:28:59,300 >> Kaya kung kami ay may isang array ng kabuuang sukat na 26 kaya na ito ang ika-25 ng lokasyon 685 00:28:59,300 --> 00:29:03,390 sa ibaba, at i-claim ko na Alice ay ang unang salita sa diksyunaryo ng 686 00:29:03,390 --> 00:29:07,260 mga pangalan na gusto kong ipasok sa RAM, sa ang istraktura ng data, kung nasaan 687 00:29:07,260 --> 00:29:12,480 instincts nagsasabi sa iyo na ni Alice pangalan dapat pumunta sa array na ito? 688 00:29:12,480 --> 00:29:13,510 >> Mayroon kaming 26 na mga pagpipilian. 689 00:29:13,510 --> 00:29:14,990 Kung saan gusto naming ilagay ang kanyang? 690 00:29:14,990 --> 00:29:16,200 Gusto naming siya sa mga bracket zero, tama? 691 00:29:16,200 --> 00:29:18,280 Isang para sa Alice, sabihin call na zero. 692 00:29:18,280 --> 00:29:20,110 At B ay magiging isa, at C ay magiging dalawang. 693 00:29:20,110 --> 00:29:22,600 Kaya kami ay pagpunta sa isulat Alice ang pangalan up dito. 694 00:29:22,600 --> 00:29:24,890 Kung kami pagkatapos ay ipasok Bob, ang kanyang pangalan ay pupunta dito. 695 00:29:24,890 --> 00:29:27,280 Charlie ay pumunta dito. 696 00:29:27,280 --> 00:29:30,500 At iba pa pababa sa pamamagitan ng ang data na istraktura. 697 00:29:30,500 --> 00:29:32,090 >> Ito ay isang kahanga-hangang istraktura ng data. 698 00:29:32,090 --> 00:29:32,730 Bakit? 699 00:29:32,730 --> 00:29:37,460 Well kung ano ang oras ng paggana ng pagpasok ng pangalan ng isang tao ay sa ito 700 00:29:37,460 --> 00:29:39,850 data istraktura ngayon? 701 00:29:39,850 --> 00:29:43,702 Given na talahanayan na ito ay ipinatupad, tunay, bilang isang array. 702 00:29:43,702 --> 00:29:44,940 Well ito ay pare-pareho ang panahon. 703 00:29:44,940 --> 00:29:45,800 Ito ay sunod ng isa. 704 00:29:45,800 --> 00:29:46,360 Bakit? 705 00:29:46,360 --> 00:29:48,630 >> Well paano mo matutukoy kung saan nabibilang ang Alice? 706 00:29:48,630 --> 00:29:51,000 Tumingin ka sa kung aling mga titik ng kanyang pangalan? 707 00:29:51,000 --> 00:29:51,490 Ang unang. 708 00:29:51,490 --> 00:29:54,350 At maaari kang makakuha ng doon, kung ito ay isang string, sa pamamagitan lamang ng pagtingin sa string 709 00:29:54,350 --> 00:29:55,200 bracket zero. 710 00:29:55,200 --> 00:29:57,110 Kaya ang 0 karakter ng string. 711 00:29:57,110 --> 00:29:57,610 Iyon ay madali. 712 00:29:57,610 --> 00:30:00,350 Aming ginawa na sa crypto pagtatalaga linggo na ang nakaraan. 713 00:30:00,350 --> 00:30:05,310 At pagkatapos ay sa sandaling alam mo na ni Alice titik ay capital A, maaari naming ibawas 714 00:30:05,310 --> 00:30:08,160 off 65 o capital A mismo, na nagbibigay sa amin ng zero. 715 00:30:08,160 --> 00:30:10,940 Kaya namin ngayon malaman na nabibilang Alice lokasyon sa zero. 716 00:30:10,940 --> 00:30:14,240 >> At ibinigay na isang pointer upang ang data na ito istraktura, ng ilang mga uri, kung gaano katagal ang ibig 717 00:30:14,240 --> 00:30:18,840 tumagal sa akin upang mahanap ang lokasyon zero sa isang array? 718 00:30:18,840 --> 00:30:22,080 Lamang isang hakbang, kanan Ito ay pare-pareho ang oras dahil sa mga random access namin 719 00:30:22,080 --> 00:30:23,780 ipinanukalang ay isang tampok ng isang array. 720 00:30:23,780 --> 00:30:28,570 Kaya sa maikling salita, ang pag-uunawa kung ano ang index ng Alice ni ang pangalan, na kung saan ay, sa 721 00:30:28,570 --> 00:30:32,610 kasong ito, ay A, o sabihin lamang malutas na sa zero, kung saan ang B ay isa at C ay 722 00:30:32,610 --> 00:30:34,900 dalawa, pag-uunawa na out ay pare-pareho ang panahon. 723 00:30:34,900 --> 00:30:38,510 Ko na lang ay upang tumingin sa kanyang mga unang titik, ang pag-uunawa kung saan zero ay isang 724 00:30:38,510 --> 00:30:40,460 array ay din pare-pareho ang panahon. 725 00:30:40,460 --> 00:30:42,140 Kaya technically na tulad ng dalawang hakbang na ito ngayon. 726 00:30:42,140 --> 00:30:43,330 Ngunit iyon pa rin pare-pareho. 727 00:30:43,330 --> 00:30:46,880 Kaya tinatawag namin na malaki O ng isa, kaya na namin Ipinasok Alice sa talahanayan na ito sa 728 00:30:46,880 --> 00:30:48,440 pare-pareho ang panahon. 729 00:30:48,440 --> 00:30:50,960 >> Ngunit siyempre, ako pagiging walang muwang dito, tama? 730 00:30:50,960 --> 00:30:53,240 Paano kung mayroong isang Aaron sa klase? 731 00:30:53,240 --> 00:30:53,990 O Alicia? 732 00:30:53,990 --> 00:30:57,230 O anumang iba pang mga pangalan na nagsisimula sa A. Saan na tayo ng pagpunta sa ilagay 733 00:30:57,230 --> 00:31:00,800 ang taong iyon, tama? 734 00:31:00,800 --> 00:31:03,420 Ibig kong sabihin, sa ngayon mayroon lamang tatlong mga tao na nasa mesa, kaya siguro namin 735 00:31:03,420 --> 00:31:07,490 dapat ilagay Aaron sa lokasyon zero isa dalawa tatlo. 736 00:31:07,490 --> 00:31:09,480 >> Kanan, maaari ko bang ilagay ang isang dito. 737 00:31:09,480 --> 00:31:13,350 Ngunit pagkatapos, kung susubukan namin upang ipasok David sa listahan na ito, kung saan ay pumunta David? 738 00:31:13,350 --> 00:31:15,170 Ngayon, ang aming system ay nagsisimula pagsira pababa, tama? 739 00:31:15,170 --> 00:31:19,210 Dahil ngayon si David ay nagtatapos up dito kung Aaron ay talagang dito. 740 00:31:19,210 --> 00:31:23,060 At kaya ngayon ang buong ideya ng pagkakaroon ng malinis na istraktura ng data na nagbibigay sa amin 741 00:31:23,060 --> 00:31:28,010 pare-pareho ang mga pagpapasok ng oras ay wala na pare-pareho ang oras, dahil mayroon akong upang 742 00:31:28,010 --> 00:31:31,240 check, oh, damnit, may isang taong na- sa Alice ng lokasyon. 743 00:31:31,240 --> 00:31:35,320 >> Hayaan akong suriin ang natitirang bahagi ng ang data na ito istraktura, hinahanap ang isang lugar upang ilagay 744 00:31:35,320 --> 00:31:37,130 may isang taong katulad ni Aaron pangalan. 745 00:31:37,130 --> 00:31:39,390 At nang sa gayon ay masyadong ay nagsisimula gumawa ng linear oras. 746 00:31:39,390 --> 00:31:42,710 Dagdag pa rito, kung ikaw ngayon ay nais upang mahanap ang Aaron sa istraktura ng data, at ikaw 747 00:31:42,710 --> 00:31:45,430 suriin, at Aaron ang pangalan ay hindi dito. 748 00:31:45,430 --> 00:31:47,960 May perpektong, gusto mo lamang ang sinasabi ni Aaron wala sa istraktura ng data. 749 00:31:47,960 --> 00:31:51,530 Ngunit kung gagawin mo nang kumita ng room para sa Aaron kung saan dapat ay naging isang D 750 00:31:51,530 --> 00:31:55,600 o isang E, mo, pinakamasama kaso, mayroon upang suriin ang buong istraktura ng data, sa 751 00:31:55,600 --> 00:31:59,480 Kung saan ito devolves sa isang bagay linear sa laki ng table. 752 00:31:59,480 --> 00:32:00,920 >> Kaya ang lahat ng karapatan, makikita ko aayusin ito. 753 00:32:00,920 --> 00:32:04,200 Ang problema dito ay na ako ay nagkaroon 26 mga elemento sa array na ito. 754 00:32:04,200 --> 00:32:05,000 Hayaan akong baguhin ito. 755 00:32:05,000 --> 00:32:06,010 Oops. 756 00:32:06,010 --> 00:32:10,600 Hayaan akong baguhin ito nang sa gayon ay sa halip ng pagiging size 26 sa kabuuan, mapapansin sa ibaba 757 00:32:10,600 --> 00:32:12,720 index ay pagpunta upang baguhin n minus 1. 758 00:32:12,720 --> 00:32:16,610 Kung 26 ay malinaw na masyadong maliit para sa mga kawani na tao ' mga pangalan, dahil mayroong libu-libong mga 759 00:32:16,610 --> 00:32:20,830 mga pangalan ng mundo, sabihin lang gumawa sa 100 o 1,000 o 10,000. 760 00:32:20,830 --> 00:32:22,960 Sabihin lamang maglaan ng maraming mas maraming espasyo. 761 00:32:22,960 --> 00:32:27,230 >> Well na ay hindi kinakailangang bawasan ang posibilidad na hindi namin ay magkakaroon ng dalawang 762 00:32:27,230 --> 00:32:31,510 mga taong may mga pangalan na nagsisimula sa A, at gayon, ikaw ay pagpunta sa subukan upang ilagay ang isang 763 00:32:31,510 --> 00:32:33,120 mga pangalan ng lokasyon sa zero pa rin. 764 00:32:33,120 --> 00:32:36,850 Pa rin ang mga ito ay pagpunta sa nagbanggaan, na Nangangahulugan pa rin namin kailangan ng isang solusyon upang ilagay 765 00:32:36,850 --> 00:32:41,020 Alice at Aaron at Alicia at iba pang mga mga pangalan na nagsisimula sa A sa ibang lugar. 766 00:32:41,020 --> 00:32:43,460 Ngunit kung magkano ng isang problema ito? 767 00:32:43,460 --> 00:32:46,870 Ano ang posibilidad na ikaw may banggaan sa isang data 768 00:32:46,870 --> 00:32:48,240 kaayusan tulad ng mga ito? 769 00:32:48,240 --> 00:32:52,570 >> Well, ipaalam sa akin - ipapakita namin bumalik sa na pinag-uusapan dito. 770 00:32:52,570 --> 00:32:55,530 At tumingin sa kung paano maaari naming malutas muna ito. 771 00:32:55,530 --> 00:32:58,480 Hayaan akong hilahin pataas ang panukalang ito dito. 772 00:32:58,480 --> 00:33:02,020 Ano inilarawan namin ay isang algorithm, isang hyuristiko tinatawag na linear 773 00:33:02,020 --> 00:33:05,030 probing kung saan, kung sinubukan mong isingit isang bagay dito sa data na ito 774 00:33:05,030 --> 00:33:08,920 istraktura, na kung saan ay tinatawag na hash table, at mayroong walang room doon, mo 775 00:33:08,920 --> 00:33:12,000 tunay na suriin ang data ng istraktura pagsusuri, ito ay magagamit? 776 00:33:12,000 --> 00:33:13,430 Ay ito Magagamit na ito ay magagamit? 777 00:33:13,430 --> 00:33:13,980 Ba ito magagamit? 778 00:33:13,980 --> 00:33:17,550 At kapag ito ay sa wakas, ipasok mo ang pangalanan na iyong orihinal na nilalayon 779 00:33:17,550 --> 00:33:19,370 sa ibang lugar sa lokasyong iyon. 780 00:33:19,370 --> 00:33:23,360 Ngunit sa pinakamasama kaso, ang tanging lugar maaaring ang pinakailalim ng data 781 00:33:23,360 --> 00:33:25,090 istraktura, pinakadulo ng array. 782 00:33:25,090 --> 00:33:30,130 >> Kaya linear probing, sa pinakamasama kaso, devolves sa isang linear algorithm kung saan 783 00:33:30,130 --> 00:33:34,500 Aaron, kung siya ang mangyayari sa mga na ipasok ang huling sa ganitong istraktura ng data, maaari siya 784 00:33:34,500 --> 00:33:39,540 sumalungat sa mga ito unang lokasyon, ngunit pagkatapos magtapos sa pamamagitan ng malas sa pinakadulo. 785 00:33:39,540 --> 00:33:43,940 Kaya ito ay hindi isang constant oras banal na Kopita para sa amin. 786 00:33:43,940 --> 00:33:47,650 Ang diskarte ng pagpasok ng mga elemento sa isang istraktura ng data na tinatawag na hash 787 00:33:47,650 --> 00:33:52,050 talahanayan ay hindi tila na maging pare-pareho ang oras hindi bababa sa hindi sa pangkalahatang kaso. 788 00:33:52,050 --> 00:33:54,000 Maaari itong malipat sa isang bagay linear. 789 00:33:54,000 --> 00:33:56,970 >> Kaya kung ano malutas namin banggaan medyo naiiba? 790 00:33:56,970 --> 00:34:00,740 Kaya narito ang isang mas sopistikadong lapitan sa kung ano pa rin 791 00:34:00,740 --> 00:34:02,800 tinatawag na hash table. 792 00:34:02,800 --> 00:34:05,890 At sa pamamagitan ng hash, bilang isang tabi, kung ano Ibig kong sabihin ay ang index na 793 00:34:05,890 --> 00:34:07,070 Ako refer sa mas maaga. 794 00:34:07,070 --> 00:34:09,810 Upang mag-hash ng isang bagay na maaaring maging naisip ng bilang isang pandiwa. 795 00:34:09,810 --> 00:34:13,690 >> Kaya't kung ikaw hash Alice ang isang pangalan, isang hash, kaya na magsalita, 796 00:34:13,690 --> 00:34:14,710 dapat ibalik ang isang numero. 797 00:34:14,710 --> 00:34:18,199 Sa kasong ito ay zero kung siya ay kabilang sa lokasyon zero, isa kung siya ay kabilang sa 798 00:34:18,199 --> 00:34:20,000 isa lokasyon, at iba pa. 799 00:34:20,000 --> 00:34:24,360 Kaya ang aking hash kaya ngayon ay naging sobrang simple, lamang ng pagtingin sa mga 800 00:34:24,360 --> 00:34:26,159 unang titik sa pangalan ng isang tao. 801 00:34:26,159 --> 00:34:29,090 Ngunit isang hash tumatagal ng bilang input ng ilang mga piraso ng data, isang 802 00:34:29,090 --> 00:34:30,210 string, isang int, kahit anong. 803 00:34:30,210 --> 00:34:32,239 At ito spits out karaniwang isang numero. 804 00:34:32,239 --> 00:34:35,739 At bilang na kung saan ang data na iyon elemento nabibilang sa isang istraktura ng data 805 00:34:35,739 --> 00:34:37,800 Kilala dito bilang isang hash table. 806 00:34:37,800 --> 00:34:41,400 >> Kaya lamang intuitively, ito ay isang bahagyang naiiba konteksto. 807 00:34:41,400 --> 00:34:44,170 Ito talaga ay nagre-refer sa isang halimbawa kinasasangkutan ng mga kaarawan, kung saan 808 00:34:44,170 --> 00:34:46,850 maaaring magkaroon ng maraming mga bilang 31 araw sa buwan. 809 00:34:46,850 --> 00:34:52,239 Ngunit kung ano ang taong ito upang magpasya gawin sa kaganapan ng isang banggaan? 810 00:34:52,239 --> 00:34:55,304 Konteksto ngayon pagiging, hindi isang banggaan ng mga pangalan, ngunit isang banggaan ng kaarawan, 811 00:34:55,304 --> 00:35:00,760 kung ang dalawang tao ay may parehong kaarawan sa ang Oktubre 2, halimbawa. 812 00:35:00,760 --> 00:35:02,120 >> MAG-AARAL: [hindi marinig]. 813 00:35:02,120 --> 00:35:05,010 >> Tagapagsalita 1: Oo, kaya dito mayroon kami ang paggamit ng mga naka-link na mga listahan. 814 00:35:05,010 --> 00:35:07,830 Kaya ito hitsura ng kaunti naiiba kaysa namin iginuhit mo ito nang mas maaga. 815 00:35:07,830 --> 00:35:10,790 Ngunit lumitaw namin na magkaroon ng sa isang array sa kaliwang bahagi. 816 00:35:10,790 --> 00:35:13,230 Iyon ang isa index, para sa walang partikular na dahilan. 817 00:35:13,230 --> 00:35:14,630 Ngunit ito pa rin isang array. 818 00:35:14,630 --> 00:35:16,160 Ito ay isang array ng mga payo. 819 00:35:16,160 --> 00:35:20,670 At sa bawat isa sa mga elementong iyon, ang bawat isa ng mga lupon o slashes - ang slash 820 00:35:20,670 --> 00:35:23,970 na kumakatawan sa null - bawat isa sa mga pointer ay tila na tumuturo sa 821 00:35:23,970 --> 00:35:25,730 kung ano ang data kaayusan? 822 00:35:25,730 --> 00:35:26,890 Ang isang naka-link na listahan. 823 00:35:26,890 --> 00:35:30,530 >> Kaya ngayon kami ay may mga kakayahan na matapang na code sa aming programa 824 00:35:30,530 --> 00:35:32,010 ang laki ng table. 825 00:35:32,010 --> 00:35:35,360 Sa kasong ito, alam namin mayroong hindi kailanman higit sa 31 araw sa isang buwan. 826 00:35:35,360 --> 00:35:38,480 Kaya mahirap coding ng halaga tulad ng 31 ay makatwirang sa na konteksto. 827 00:35:38,480 --> 00:35:42,700 Sa konteksto ng mga pangalan, hard coding 26 ay hindi wala sa katwiran ito tao 828 00:35:42,700 --> 00:35:46,340 mga pangalan lamang magsimula sa, halimbawa, ang alpabeto na kinasasangkutan A sa pamamagitan ng Z. 829 00:35:46,340 --> 00:35:50,180 >> Maaari naming siksikin ang lahat ng ito sa data na iyon istraktura hangga't, kapag kami makakuha ng isang 830 00:35:50,180 --> 00:35:55,330 banggaan, hindi namin ilagay ang mga pangalan dito, namin sa halip sa tingin ng mga cell na ito 831 00:35:55,330 --> 00:36:00,270 hindi bilang mga string ang kanilang mga sarili, ngunit bilang payo upang, halimbawa, Alice. 832 00:36:00,270 --> 00:36:03,660 At pagkatapos ay Alice ay maaaring magkaroon ng isa pang pointer sa ibang pangalan na nagsisimula sa 833 00:36:03,660 --> 00:36:06,150 A. At Bob talagang napupunta sa paglipas dito. 834 00:36:06,150 --> 00:36:10,850 >> At kung mayroong ibang pangalan nagsisimula may B, siya ay nagtatapos up sa paglipas dito. 835 00:36:10,850 --> 00:36:15,070 At sa gayon ang bawat isa sa mga elemento ng ito dalawang talahanayan, kung dinisenyo namin ito ng 836 00:36:15,070 --> 00:36:17,350 kaunti pa cleverly - 837 00:36:17,350 --> 00:36:18,125 dumating sa - 838 00:36:18,125 --> 00:36:22,950 kung dinisenyo namin ito ng kaunti pa cleverly, na ngayon ay nagiging isang agpang data 839 00:36:22,950 --> 00:36:27,720 istraktura, kung saan walang mahirap na limitasyon sa kung paano maraming mga sangkap na maaari mong isingit 840 00:36:27,720 --> 00:36:30,700 sa ito dahil sa kung mayroon kang mga isang banggaan, na fine. 841 00:36:30,700 --> 00:36:34,690 Lang sige at ikabit ito sa kung ano ang nakita natin ng kaunti ang nakalipas noon ay 842 00:36:34,690 --> 00:36:38,290 kilala bilang isang naka-link na listahan. 843 00:36:38,290 --> 00:36:39,690 >> Well sabihin i-pause para lamang ng ilang sandali. 844 00:36:39,690 --> 00:36:42,570 Ano ang posibilidad ng isang banggaan sa unang lugar? 845 00:36:42,570 --> 00:36:45,480 Right, siguro sa paglipas ako nag-iisip, siguro Ako ay mahigit sa engineering ang problemang ito, 846 00:36:45,480 --> 00:36:46,370 dahil alam mo kung ano? 847 00:36:46,370 --> 00:36:49,070 Oo, maaari ba akong makabuo ng mga di-makatwirang halimbawa off sa tuktok ng aking ulo tulad ng 848 00:36:49,070 --> 00:36:52,870 Allison at Aaron, ngunit sa katotohanan, ibinigay na isang pare-parehong pamamahagi ng 849 00:36:52,870 --> 00:36:56,990 input, na ang ilang mga random na mga pagpapasok ng sa isang istraktura ng data, kung ano talaga ang 850 00:36:56,990 --> 00:36:58,580 ang posibilidad ng isang banggaan? 851 00:36:58,580 --> 00:37:01,670 Well lumiliko out, ito ay talagang sobrang mataas. 852 00:37:01,670 --> 00:37:03,850 Hayaan akong magbigay ng tuntuning panlahat na ito problema ay ang bilang na ito. 853 00:37:03,850 --> 00:37:08,890 >> Kaya sa isang kuwarto ng n CS50 mga mag-aaral, kung ano ang ang posibilidad na hindi bababa sa 854 00:37:08,890 --> 00:37:11,010 dalawang mag-aaral sa kuwarto magkaroon ng parehong kaarawan? 855 00:37:11,010 --> 00:37:13,346 Kaya mayroong kung ano. Ilang hund - 856 00:37:13,346 --> 00:37:16,790 200, 300 mga tao dito at ilang daang mga tao sa bahay ngayon. 857 00:37:16,790 --> 00:37:20,670 Kaya kung nais mong hilingin sa ating sarili kung ano ang ang posibilidad ng dalawang tao 858 00:37:20,670 --> 00:37:23,930 sa kuwartong ito ang pagkakaroon ng parehong kaarawan, maaari naming malaman ito out. 859 00:37:23,930 --> 00:37:26,250 At inaangkin ko ang aktwal na mayroong dalawang mga tao na may parehong kaarawan. 860 00:37:26,250 --> 00:37:29,560 >> Halimbawa, ang sinuman may kaarawan ngayon? 861 00:37:29,560 --> 00:37:31,340 Kahapon? 862 00:37:31,340 --> 00:37:32,590 Bukas? 863 00:37:32,590 --> 00:37:35,980 Ang lahat ng mga karapatan, kaya ito nararamdaman tulad ng pupuntahan ko upang magkaroon upang gawin ito 363 o kaya higit pa 864 00:37:35,980 --> 00:37:39,500 beses upang aktwal na malaman kung mayroon kaming isang banggaan. 865 00:37:39,500 --> 00:37:42,350 O maaari naming lamang gawin ito mathematically sa halip na tediously 866 00:37:42,350 --> 00:37:43,200 ginagawa ito. 867 00:37:43,200 --> 00:37:44,500 At ipanukala ang mga sumusunod na. 868 00:37:44,500 --> 00:37:48,740 >> Kaya ko magpanukala na maaari kaming gawing modelo ang posibilidad ng dalawang tao ang pagkakaroon ng 869 00:37:48,740 --> 00:37:55,320 parehong kaarawan bilang ang posibilidad ng 1 minus ang posibilidad ng hindi pagkakaroon ng isa 870 00:37:55,320 --> 00:37:56,290 ang parehong kaarawan. 871 00:37:56,290 --> 00:37:59,960 Kaya upang makakuha ng mga ito, at ito ay lamang ang magarbong paraan ng pagsulat na ito, para sa mga 872 00:37:59,960 --> 00:38:03,090 unang tao sa kuwarto, siya ay maaaring magkaroon ng kahit isa sa mga posibleng 873 00:38:03,090 --> 00:38:07,370 kaarawan ipagpalagay na 365 araw sa taon, may pasensiya sa mga taong may 874 00:38:07,370 --> 00:38:08,760 ang kaarawan Pebrero 29. 875 00:38:08,760 --> 00:38:13,470 >> Kaya ang unang tao sa kuwartong ito ay libre upang magkaroon ng anumang bilang ng mga kaarawan 876 00:38:13,470 --> 00:38:18,280 sa labas ng 365 mga posibilidad upang ang gagawin namin na 365 na hinati sa pamamagitan ng 365, 877 00:38:18,280 --> 00:38:18,990 na kung saan ay isa. 878 00:38:18,990 --> 00:38:22,700 Ang susunod na tao sa kuwarto, kung ang layunin ay upang maiwasan ang isang banggaan, maaari lamang 879 00:38:22,700 --> 00:38:26,460 magkaroon ng kanyang kaarawan sa kung paano maraming iba't ibang posibleng mga araw? 880 00:38:26,460 --> 00:38:27,610 364. 881 00:38:27,610 --> 00:38:31,430 Kaya ang ikalawang termino sa expression na ito ay mahalagang paggawa na matematika para sa amin 882 00:38:31,430 --> 00:38:33,460 sa pamamagitan ng pagbabawas off ang isa posibleng araw. 883 00:38:33,460 --> 00:38:36,390 At pagkatapos ay ang susunod na araw, sa susunod na araw, ang susunod na araw pababa sa kabuuang bilang 884 00:38:36,390 --> 00:38:38,100 ng mga tao sa kuwarto. 885 00:38:38,100 --> 00:38:41,290 >> At kung namin pagkatapos isaalang-alang, kung ano pagkatapos ay ang posibilidad ng hindi pagkakaroon ng lahat ng tao 886 00:38:41,290 --> 00:38:45,265 natatanging kaarawan, ngunit muli minus 1 na, kung ano ang nakukuha namin ay isang expression 887 00:38:45,265 --> 00:38:47,810 na maaari napaka fancifully ganito ang hitsura. 888 00:38:47,810 --> 00:38:50,330 Ngunit ito ay mas kawili-wiling tumingin sa mga biswal. 889 00:38:50,330 --> 00:38:55,120 Ito ay isang tsart kung saan sa x-axis ay ang bilang ng mga tao sa kuwarto, ang 890 00:38:55,120 --> 00:38:56,180 bilang ng mga kaarawan. 891 00:38:56,180 --> 00:38:59,840 Sa y-axis ay ang probabilidad ng isang banggaan, dalawang tao 892 00:38:59,840 --> 00:39:01,230 nagkakaroon ng parehong kaarawan. 893 00:39:01,230 --> 00:39:05,020 >> At ang mga takeaway mula sa curve ay na sa lalong madaling makakuha ka upang gustuhin 40 894 00:39:05,020 --> 00:39:11,110 mga mag-aaral, ikaw ay hanggang sa isang 90% posibilidad combinatorically ng dalawang 895 00:39:11,110 --> 00:39:13,550 mga tao o higit pa sa pagkakaroon ang parehong kaarawan. 896 00:39:13,550 --> 00:39:18,600 At sa sandaling makakuha ka upang gustuhin 58 taong ito halos 100% ng isang pagkakataon ang dalawang 897 00:39:18,600 --> 00:39:21,310 mga tao sa kuwarto ay pagpunta sa may parehong kaarawan, kahit na mayroong 898 00:39:21,310 --> 00:39:26,650 365 o 366 posibleng mga bucket, at lamang 58 mga tao sa kuwarto. 899 00:39:26,650 --> 00:39:29,900 Lamang-istatistika ikaw ay malamang na makakuha ng banggaan, na sa maikling 900 00:39:29,900 --> 00:39:31,810 motivates ang talakayang ito. 901 00:39:31,810 --> 00:39:35,890 Na kahit na makuha namin magarbong dito, at simulan ang pagkakaroon ng mga chain, hindi namin pa rin 902 00:39:35,890 --> 00:39:36,950 pagpunta sa magkaroon ng banggaan. 903 00:39:36,950 --> 00:39:42,710 >> Kaya na begs ang tanong, ano ang gastos ng paggawa ng mga pagpapasok at pagtanggal 904 00:39:42,710 --> 00:39:44,850 sa isang data na istraktura tulad nito? 905 00:39:44,850 --> 00:39:46,630 Well ipaalam sa akin imungkahi - 906 00:39:46,630 --> 00:39:51,570 at hayaan mo akong bumalik sa screen sa ibabaw dito - kung kami n mga elemento sa 907 00:39:51,570 --> 00:39:56,330 listahan, sa gayon kung sinusubukan naming isingit n elemento, at mayroon kami 908 00:39:56,330 --> 00:39:58,050 kung gaano karaming mga kabuuang mga bucket? 909 00:39:58,050 --> 00:40:03,450 Sabihin nating 31 kabuuang mga bucket sa kaso ng mga kaarawan. 910 00:40:03,450 --> 00:40:09,240 Ano ang maximum na haba ng isa ng mga potensyal na chain? 911 00:40:09,240 --> 00:40:12,670 >> Kung muli mayroong 31 posible kaarawan sa isang ibinigay na buwan. 912 00:40:12,670 --> 00:40:14,580 At lang kami clumping lahat ng tao - 913 00:40:14,580 --> 00:40:15,580 tunay na isang bobo halimbawa. 914 00:40:15,580 --> 00:40:16,960 Natin gawin 26 sa halip. 915 00:40:16,960 --> 00:40:20,890 Kaya kung mayroon talagang mga tao ang mga pangalan magsimula sa pamamagitan ng A Z, sa gayong paraan ng pagbibigay 916 00:40:20,890 --> 00:40:22,780 sa amin 26 mga posibilidad. 917 00:40:22,780 --> 00:40:25,920 At kami gumagamit ka ng data kaayusan tulad ng ang isa pa lang namin nakita, kung saan mayroon kaming 918 00:40:25,920 --> 00:40:30,210 isang array ng mga payo, ang bawat isa mga punto sa isang naka-link na listahan kung saan ang 919 00:40:30,210 --> 00:40:32,360 muna ang listahan ng lahat ng tao may pangalan Alice. 920 00:40:32,360 --> 00:40:35,770 Ang pangalawang listahan ay tuwing may mga pangalanan na nagsisimula sa A, simula 921 00:40:35,770 --> 00:40:36,980 may B, at iba pa. 922 00:40:36,980 --> 00:40:41,020 >> Ano ang malamang haba ng bawat isa sa mga listahan ng kung ipinapalagay namin gandang malinis 923 00:40:41,020 --> 00:40:45,410 pamamahagi ng mga pangalan ng A sa pamamagitan ng Z sa buong istraktura ng data? 924 00:40:45,410 --> 00:40:50,210 Mayroong n tao sa mga istraktura ng data hinati sa 26, kung ang mga ito ay mabuti 925 00:40:50,210 --> 00:40:52,110 maikalat sa buong istraktura ng data. 926 00:40:52,110 --> 00:40:54,970 Kaya ang haba ng bawat isa sa mga chain ay N na hinati sa pamamagitan ng 26. 927 00:40:54,970 --> 00:40:57,380 Ngunit sa malaking O notation, ano iyon? 928 00:40:57,380 --> 00:41:00,100 929 00:41:00,100 --> 00:41:02,440 Ano na ba talagang? 930 00:41:02,440 --> 00:41:04,150 Kaya ito ay talagang lamang n, tama? 931 00:41:04,150 --> 00:41:06,620 Dahil namin ang sinabi sa nakaraan, na he hatiin mo sa pamamagitan ng 26. 932 00:41:06,620 --> 00:41:08,710 Oo, sa katotohanan ito ay mas mabilis. 933 00:41:08,710 --> 00:41:12,720 Ngunit sa teorya, ito ay hindi sa panimula lahat na mas mabilis. 934 00:41:12,720 --> 00:41:16,040 >> Kaya hindi namin mukhang lahat na magkano mas malapit sa ito Kopita banal. 935 00:41:16,040 --> 00:41:17,750 Sa katunayan, ito lamang ang linear oras. 936 00:41:17,750 --> 00:41:20,790 Ano ba, sa puntong ito, kung bakit hindi namin lamang gamitin ang isa sa malaking naka-link listahan? 937 00:41:20,790 --> 00:41:23,510 Bakit hindi namin lamang gamitin ang isa sa malaking array na mag-imbak ng mga pangalan ng 938 00:41:23,510 --> 00:41:25,010 lahat ng tao sa room? 939 00:41:25,010 --> 00:41:28,280 Well, ay doon pa rin ng isang bagay nakahihimok tungkol sa isang hash talahanayan? 940 00:41:28,280 --> 00:41:30,810 Mayroon bang pa rin ng isang bagay na nakakahimok tungkol sa isang istraktura ng data 941 00:41:30,810 --> 00:41:33,940 na ganito ang hitsura? 942 00:41:33,940 --> 00:41:35,182 Ito. 943 00:41:35,182 --> 00:41:37,050 >> MAG-AARAL: [hindi marinig]. 944 00:41:37,050 --> 00:41:39,840 >> Tagapagsalita 1: I-right, at muli kung ito lamang isang linear algorithm oras, at isang 945 00:41:39,840 --> 00:41:42,780 linear oras data istraktura, bakit hindi ko lamang mag-imbak pangalan ng lahat sa isang malaking 946 00:41:42,780 --> 00:41:44,210 array, o sa isang malaking naka-link listahan? 947 00:41:44,210 --> 00:41:47,010 At tumigil sa paggawa ng CS kaya mas mahirap kaysa ito ay kailangang maging? 948 00:41:47,010 --> 00:41:49,600 949 00:41:49,600 --> 00:41:53,190 Ano ang tungkol sa nakahihimok na ito, kahit na bagaman ako scratched ito out? 950 00:41:53,190 --> 00:41:54,930 >> MAG-AARAL: [hindi marinig]. 951 00:41:54,930 --> 00:41:57,040 >> Tagapagsalita 1: Ipinasok ang hindi? 952 00:41:57,040 --> 00:41:58,140 Mahal na ngayon. 953 00:41:58,140 --> 00:42:03,390 Kaya pagpapasok ng potensyal pa rin ng dati maging pare-pareho ang oras, kahit na ang iyong data 954 00:42:03,390 --> 00:42:07,910 istraktura mukhang ganito, isang array ng payo, ang bawat isa ay tumuturo sa 955 00:42:07,910 --> 00:42:09,550 potensyal na isang naka-link na listahan. 956 00:42:09,550 --> 00:42:15,220 Paano mong makamit ang pare-pareho oras ng pagpapasok ng mga pangalan? 957 00:42:15,220 --> 00:42:16,280 Dumikit ito sa harap, tama? 958 00:42:16,280 --> 00:42:19,290 >> Kung namin isakripisyo ang isang disenyo ng layunin mula sa mas maaga, kung saan gusto naming panatilihing 959 00:42:19,290 --> 00:42:22,650 pangalan ng lahat, halimbawa, pinagsunod-sunod, o lahat ng mga numero sa entablado pinagsunod-sunod, 960 00:42:22,650 --> 00:42:25,020 ipagpalagay na kami ay may isang unsorted naka-link listahan. 961 00:42:25,020 --> 00:42:29,960 Ito lamang ay nagkakahalaga sa amin ng isa o dalawang hakbang, gusto sa kaso ng Ben at Brian 962 00:42:29,960 --> 00:42:32,750 mas maaga, sa magpasok ng isang elemento sa sa simula ng listahan. 963 00:42:32,750 --> 00:42:36,090 Kaya kung hindi namin pakialam tungkol sa pagbubukod-bukod ng lahat ng mga pangalan na nagsisimula sa A o lahat 964 00:42:36,090 --> 00:42:39,660 ang mga pangalan na nagsisimula sa B, maaari pa rin namin makamit ang pare-pareho ang oras sa pagpapasok. 965 00:42:39,660 --> 00:42:43,900 Ngayon hinahanap ang Alice o Bob o anumang pangalan higit pa sa pangkalahatan ay pa rin kung ano? 966 00:42:43,900 --> 00:42:48,100 Ito ay malaki ng O n hinati sa 26, sa tamang-tama kaso kung saan ang lahat ng tao ay pantay 967 00:42:48,100 --> 00:42:51,190 ibinahagi, kung saan mayroong maraming bilang A bilang mayroong Z, na kung saan ay marahil 968 00:42:51,190 --> 00:42:52,220 hindi makatotohanang. 969 00:42:52,220 --> 00:42:53,880 Ngunit iyon pa rin linear. 970 00:42:53,880 --> 00:42:57,120 >> Ngunit dito, dumating kami pabalik sa punto ng asymptotic pagtatanda ng pagiging 971 00:42:57,120 --> 00:42:58,600 theoretically totoo. 972 00:42:58,600 --> 00:43:02,960 Ngunit sa tunay na mundo, kung i-claim ko na ang aking mga programa ay maaaring gawin ang isang bagay 26 beses 973 00:43:02,960 --> 00:43:06,210 mas mabilis kaysa sa iyo, na ang program ay mo pagpunta sa mas gusto ginagamit? 974 00:43:06,210 --> 00:43:09,660 Taos-pusong o minahan, na ay 26 beses na mas mabilis? 975 00:43:09,660 --> 00:43:14,320 Realistically, ang mga tao na kung saan ay 26 beses nang mas mabilis, kahit na theoretically 976 00:43:14,320 --> 00:43:18,790 ang aming mga algorithm tumakbo sa parehong asymptotic tumatakbo oras. 977 00:43:18,790 --> 00:43:20,940 >> Hayaan akong magpanukala ng ibang solusyon sama-sama. 978 00:43:20,940 --> 00:43:24,380 At kung ito ay hindi pumutok ang iyong isip, Ikinalulungkot namin out ng mga istraktura ng data. 979 00:43:24,380 --> 00:43:27,420 Kaya ito ay ito ng isang trie - 980 00:43:27,420 --> 00:43:28,520 uri ng isang ugok pangalan. 981 00:43:28,520 --> 00:43:32,880 Nagmumula ito sa retrievals, at ang salita ay naisulat trie, t-r-i-e, dahil sa 982 00:43:32,880 --> 00:43:34,450 Siyempre pagbawi Mukhang trie. 983 00:43:34,450 --> 00:43:36,580 Ngunit iyon ang kasaysayan ng salitang trie. 984 00:43:36,580 --> 00:43:40,980 >> Kaya isang trie talaga ang ilang mga uri ng puno, at ito ay din ng isang pag-play sa salitang iyon. 985 00:43:40,980 --> 00:43:46,330 At kahit na hindi pa ninyo ang maaaring makakita nito may ganitong visualization, trie isang ay isang 986 00:43:46,330 --> 00:43:50,790 puno nakaayos, tulad ng isang puno ng pamilya sa isa ninuno sa tuktok at maraming 987 00:43:50,790 --> 00:43:54,530 ng mga inapo at mahusay na inapo bilang nag-iiwan sa ibaba. 988 00:43:54,530 --> 00:43:58,100 Subalit ang bawat node sa isang trie ay isang array. 989 00:43:58,100 --> 00:44:00,680 At ito ay sa isang array - at sabihin oversimplify para sa isang sandali - ito ay isang 990 00:44:00,680 --> 00:44:04,600 array, sa kasong ito, laki ng 26, kung saan bawat node muli ay isang hanay ng mga laki 991 00:44:04,600 --> 00:44:09,000 26, kung saan ang 0 sangkap sa na array ay kumakatawan sa A, at ang huling 992 00:44:09,000 --> 00:44:11,810 sangkap sa bawat tulad array ay kumakatawan Z. 993 00:44:11,810 --> 00:44:15,520 >> Kaya ko magpanukala, pagkatapos, na ang data na ito istraktura, na kilala bilang isang trie, maaaring maging 994 00:44:15,520 --> 00:44:17,600 ginagamit din upang mag-imbak salita. 995 00:44:17,600 --> 00:44:21,740 Nakakita kami ng ilang sandali ang nakalipas kung paano kami maaaring mag-imbak salita, o sa mga pangalan ng kaso, at kami 996 00:44:21,740 --> 00:44:25,440 Nakita mas maaga kung paano namin maaaring iimbak ng mga numero, ngunit kung namin tumutok sa mga pangalan o mga string 997 00:44:25,440 --> 00:44:27,460 dito, mapapansin kung ano ang kawili-wili. 998 00:44:27,460 --> 00:44:32,210 Inaangkin ko na ang pangalan ay Maxwell sa loob ng data na ito istraktura. 999 00:44:32,210 --> 00:44:33,730 Saan mo makita Maxwell? 1000 00:44:33,730 --> 00:44:35,140 >> MAG-AARAL: [hindi marinig]. 1001 00:44:35,140 --> 00:44:36,240 >> Tagapagsalita 1: Sa kaliwang. 1002 00:44:36,240 --> 00:44:39,910 Kaya kung ano ang mga kagiliw-giliw na may data na ito istraktura ay sa halip na tindahan ng 1003 00:44:39,910 --> 00:44:46,200 string M-A-X-W-E-L-L backslash zero, ang lahat ng contiguously, kung ano ang iyong gagawin sa halip 1004 00:44:46,200 --> 00:44:46,890 Sumusunod. 1005 00:44:46,890 --> 00:44:50,510 Kung ito ay isang trie tulad ng data ng istraktura, sa bawat isa sa kung saan ang mga node ay muli isang array, 1006 00:44:50,510 --> 00:44:54,650 at nais mong iimbak Maxwell, mo munang index at kaya node sa root ng, sa gayon 1007 00:44:54,650 --> 00:44:57,810 upang makipag-usap, ang kataas-taasan node, sa lokasyon M, kanan, sa gayon 1008 00:44:57,810 --> 00:44:59,160 humigit-kumulang sa gitna. 1009 00:44:59,160 --> 00:45:03,740 At pagkatapos ay mula doon, sundin mo ang isang pointer sa isang node bata, kaya na magsalita. 1010 00:45:03,740 --> 00:45:06,150 Kaya sa kamalayan family tree, sundin mo ito pababa. 1011 00:45:06,150 --> 00:45:09,030 At na humahantong sa iyo sa isa pang node sa kaliwa doon, na kung saan ay 1012 00:45:09,030 --> 00:45:10,540 lamang ng isa pang array. 1013 00:45:10,540 --> 00:45:14,710 >> At pagkatapos ay kung nais mong iimbak Maxwell, mahanap mo ang pointer na kumakatawan 1014 00:45:14,710 --> 00:45:16,430 A, na kung saan ay ang isang ito dito. 1015 00:45:16,430 --> 00:45:17,840 Pagkatapos mong pumunta sa susunod na node. 1016 00:45:17,840 --> 00:45:20,100 At notice - ito ay kung bakit ang larawan ni medyo deceiving - 1017 00:45:20,100 --> 00:45:21,990 node na ito hitsura sobrang napakaliit. 1018 00:45:21,990 --> 00:45:26,050 Ngunit sa kanan ng ito ay Y at Z. Lamang Ito ay ang may-akda ay pinutol ang 1019 00:45:26,050 --> 00:45:27,630 larawan sa gayon ikaw talaga makita ang mga bagay. 1020 00:45:27,630 --> 00:45:30,400 Kung hindi man ang larawang ito magiging hugely lapad. 1021 00:45:30,400 --> 00:45:36,180 Kaya ngayon mo sa index ng lokasyon X, pagkatapos ay W, E Pagkatapos, pagkatapos ay i-L, pagkatapos L. Pagkatapos ay kung ano ang 1022 00:45:36,180 --> 00:45:37,380 ang pag-usisa? 1023 00:45:37,380 --> 00:45:41,250 >> Well, kung ginagamit namin ang ganitong uri ng mga bagong kumuha sa kung paano i-imbak ang isang string sa isang 1024 00:45:41,250 --> 00:45:44,500 istraktura ng data, kailangan mo pa ring mahalagang suriin off sa data 1025 00:45:44,500 --> 00:45:47,250 istraktura na ang isang salita ay nagtatapos dito. 1026 00:45:47,250 --> 00:45:50,830 Sa ibang salita, ang bawat isa sa mga ito ang mga node kahit paano ay may na tandaan na namin 1027 00:45:50,830 --> 00:45:53,500 talagang sinundan ang lahat ng mga payo at ay umaalis ng kaunti 1028 00:45:53,500 --> 00:45:58,370 tinapay mumo sa ilalim dito ng mga ito istraktura upang ipahiwatig M-A-X-W-E-L-L ay 1029 00:45:58,370 --> 00:46:00,230 sa katunayan sa data na ito istraktura. 1030 00:46:00,230 --> 00:46:02,040 >> Kaya maaari naming gawin ito tulad ng sumusunod. 1031 00:46:02,040 --> 00:46:06,810 Ang bawat isa sa mga node sa larawan lang namin Nakita ay may isa, ang isang hanay ng mga sukat 27. 1032 00:46:06,810 --> 00:46:10,550 At ngayon 27, dahil sa p-set anim, ipapakita namin talagang magbibigay sa iyo ng isang kudlit, 1033 00:46:10,550 --> 00:46:13,590 upang maaari naming magkaroon ng mga pangalan tulad ng O'Reilly at iba pa na may apostrophes. 1034 00:46:13,590 --> 00:46:14,820 Ngunit parehong ideya. 1035 00:46:14,820 --> 00:46:17,710 Ang bawat isa sa mga elemento sa array mga punto sa isang struct 1036 00:46:17,710 --> 00:46:19,320 node, kaya lang ang isang node. 1037 00:46:19,320 --> 00:46:21,430 Kaya ito ay napaka nakapagpapagunita sa aming mga naka-link na listahan. 1038 00:46:21,430 --> 00:46:24,550 >> At pagkatapos ay mayroon akong isang Boolean, na kung saan bibigyan ko call na salita, na kung saan ay lamang ng pagpunta sa maging 1039 00:46:24,550 --> 00:46:29,120 totoo kung ang isang salita ay nagtatapos sa node sa tree. 1040 00:46:29,120 --> 00:46:32,870 Ito ay epektibong ay kumakatawan sa mga maliit tatsulok nakita namin ng ilang sandali ang nakalipas. 1041 00:46:32,870 --> 00:46:37,190 Kaya kung ang isang salita ay nagtatapos sa na node sa tree, ang salitang iyon patlang ay magiging totoo, 1042 00:46:37,190 --> 00:46:41,990 na kung saan ay conceptually check off, o kami ay pagguhit ng tatsulok na ito, yes doon 1043 00:46:41,990 --> 00:46:44,080 ay isang salita dito. 1044 00:46:44,080 --> 00:46:45,120 >> Kaya ito ay isang trie. 1045 00:46:45,120 --> 00:46:48,540 At ngayon, ang tanong ay, kung ano ang ay nito tumatakbo oras? 1046 00:46:48,540 --> 00:46:49,930 Ito ba ay malaki O ng n? 1047 00:46:49,930 --> 00:46:51,410 Ito ba ay iba pang dahilan? 1048 00:46:51,410 --> 00:46:57,330 Well, kung mayroon kang n pangalan sa data na ito istraktura, Maxwell pagiging isa lamang sa 1049 00:46:57,330 --> 00:47:02,330 mga ito, ano ang oras ng paggana ng pagpapasok o paghahanap ng Maxwell? 1050 00:47:02,330 --> 00:47:06,230 1051 00:47:06,230 --> 00:47:09,050 Ano ang pagtakbo ng oras ng pagpasok ng Maxwell? 1052 00:47:09,050 --> 00:47:11,740 Kung mayroong n iba pang mga pangalan na sa table? 1053 00:47:11,740 --> 00:47:12,507 Oo? 1054 00:47:12,507 --> 00:47:15,429 >> MAG-AARAL: [hindi marinig]. 1055 00:47:15,429 --> 00:47:17,550 >> Tagapagsalita 1: Oo, ito ay ang haba ng pangalan, tama? 1056 00:47:17,550 --> 00:47:24,420 Kaya M-a-x-w-e-l-l kaya palagay ng ganito algorithm ay malaki O ng pito. 1057 00:47:24,420 --> 00:47:26,580 Ngayon, siyempre, ang pangalan ay mag-iiba sa haba. 1058 00:47:26,580 --> 00:47:27,380 Siguro ito ay isang maikling pangalan. 1059 00:47:27,380 --> 00:47:28,600 Marahil, ito ay isang mas mahabang pangalan. 1060 00:47:28,600 --> 00:47:33,390 Ngunit kung ano ang key dito ay na ito ay isang hindi nagbabagong numero. 1061 00:47:33,390 --> 00:47:36,810 At marahil ito ay hindi talaga pare-pareho, ngunit diyos, kung realistically, sa isang 1062 00:47:36,810 --> 00:47:41,570 diksyonaryo, doon ay marahil ilang mga limitasyon sa bilang ng mga titik sa isang 1063 00:47:41,570 --> 00:47:43,820 pangalan ng taong ito sa isang partikular na bansa. 1064 00:47:43,820 --> 00:47:46,940 >> At sa gayon ay maaari naming ipagpalagay na ang halaga ay isang pare-pareho. 1065 00:47:46,940 --> 00:47:47,750 Hindi ko alam kung ano ito ay. 1066 00:47:47,750 --> 00:47:50,440 Marahil ay mas malaki kaysa sa sa tingin namin ito ay. 1067 00:47:50,440 --> 00:47:52,720 Dahil mayroong palaging ng ilang mga sulok kaso may isang nakatutuwang mahaba pangalan. 1068 00:47:52,720 --> 00:47:56,360 Kaya sabihin call ito k, ngunit ito ay pa rin ng isang pare-pareho siguro, dahil bawat 1069 00:47:56,360 --> 00:48:00,190 pangalanan sa mundo, hindi bababa sa isang partikular na bansa, ay ang haba o 1070 00:48:00,190 --> 00:48:01,780 maikli, upang mas pare-pareho. 1071 00:48:01,780 --> 00:48:04,490 Ngunit kapag namin ang sinabi ng isang bagay ay malaki O ng isang pare-pareho ang halaga, kung ano ang na 1072 00:48:04,490 --> 00:48:07,760 talaga katumbas? 1073 00:48:07,760 --> 00:48:10,420 Iyon ay talaga ang parehong bagay tulad ng sinasabi ng pare-pareho ang panahon. 1074 00:48:10,420 --> 00:48:11,530 >> Ngayon kami ay uri ng pagdaraya, tama? 1075 00:48:11,530 --> 00:48:15,340 Humihingi kami ng uri ng pagdaragdag ng ilang mga teorya dito upang sabihin na rin, pagkakasunud-sunod ng k ay 1076 00:48:15,340 --> 00:48:17,450 talaga lang mag-order ng isa, at ito ay pare-pareho ang panahon. 1077 00:48:17,450 --> 00:48:18,200 Ngunit ito ay talagang. 1078 00:48:18,200 --> 00:48:22,550 Dahil ang mga key pananaw dito ay na kung kami n mga pangalan na ito sa 1079 00:48:22,550 --> 00:48:26,010 istraktura ng data, at insert namin Maxwell, ay ang halaga ng oras na aabutin upang amin 1080 00:48:26,010 --> 00:48:29,530 isingit Maxwell sa lahat ng mga apektadong sa pamamagitan ng kung gaano karaming mga iba pang mga tao 1081 00:48:29,530 --> 00:48:31,100 ay nasa istraktura ng data? 1082 00:48:31,100 --> 00:48:31,670 Mukhang hindi maging. 1083 00:48:31,670 --> 00:48:36,280 Kung ako ay nagkaroon ng isang bilyong higit pang mga elemento na ito sa trie, at pagkatapos ay ipasok Maxwell, ay 1084 00:48:36,280 --> 00:48:38,650 siya sa lahat ng apektado? 1085 00:48:38,650 --> 00:48:39,050 Hindi. 1086 00:48:39,050 --> 00:48:42,950 At iyan ay hindi tulad ng alinman sa mga araw ng data kaayusan nasaksihan namin kaya sa ngayon, kung saan 1087 00:48:42,950 --> 00:48:46,820 ang oras ng paggana ng iyong mga algorithm ay ganap na independiyenteng ng kung magkano 1088 00:48:46,820 --> 00:48:51,430 bagay-bagay ay o hindi pa sa data na istraktura. 1089 00:48:51,430 --> 00:48:54,650 >> At kaya may ito affords mo ngayon ay isang pagkakataon para p set anim, na kalooban 1090 00:48:54,650 --> 00:48:58,310 muli kasangkot sa pagpapatupad ng iyong sariling spell checker, pagbabasa sa 150,000 1091 00:48:58,310 --> 00:49:01,050 mga salita, kung paano pinakamahusay na mag-imbak na ay hindi nangangahulugang halata. 1092 00:49:01,050 --> 00:49:04,030 At bagaman ko na aspired upang mahanap ang ang banal na Kopita, gagawin ko hindi 1093 00:49:04,030 --> 00:49:05,330 i-claim na ang isang trie ay. 1094 00:49:05,330 --> 00:49:09,810 Sa katunayan, isang hash talahanayan maaari nang napakahusay patunayan na maging lubos na mas mahusay. 1095 00:49:09,810 --> 00:49:10,830 Ngunit iyon lamang ang - 1096 00:49:10,830 --> 00:49:14,620 ito lamang ay isa sa mga pagpapasya disenyo magkakaroon ka ng gumawa. 1097 00:49:14,620 --> 00:49:18,920 >> Ngunit sa pagsasara sabihin tumagal ng 50 o kaya segundo upang kumuha ng isang silip sa kung ano ang namamalagi 1098 00:49:18,920 --> 00:49:22,190 Magpatuloy sa susunod na linggo at lampas namin transition mula sa command line 1099 00:49:22,190 --> 00:49:26,220 mundo kung C programa sa mga bagay web batay at mga wika tulad ng PHP at 1100 00:49:26,220 --> 00:49:30,350 JavaScript at sa internet mismo, mga protocol tulad ng HTTP, na kung saan ikaw ay 1101 00:49:30,350 --> 00:49:32,870 kinuha para sa ipinagkaloob ng maraming taon ngayon, at nai-type na pinaka-araw- 1102 00:49:32,870 --> 00:49:34,440 araw, marahil, o nakikita. 1103 00:49:34,440 --> 00:49:37,420 At magsisimula kami upang alisan ng balat pabalik ang patong ng kung ano ay ang internet. 1104 00:49:37,420 --> 00:49:40,650 At kung ano ay ang code na underlies tool ngayon. 1105 00:49:40,650 --> 00:49:43,230 Kaya 50 segundo ng teaser na ito dito. 1106 00:49:43,230 --> 00:49:46,570 Ako magbibigay sa iyo ng Warriors ng Net. 1107 00:49:46,570 --> 00:49:51,370 >> [Video playback] 1108 00:49:51,370 --> 00:49:56,764 >> -Siya ay dumating sa isang mensahe. 1109 00:49:56,764 --> 00:50:00,687 Gamit ang isang protocol ang lahat ng kanyang sariling. 1110 00:50:00,687 --> 00:50:13,370 1111 00:50:13,370 --> 00:50:19,780 Siya ay dumating sa isang mundo ng malupit na firewall, uncaring router, at panganib sa ngayon 1112 00:50:19,780 --> 00:50:22,600 mas masahol pa kaysa kamatayan. 1113 00:50:22,600 --> 00:50:23,590 Siya ay mabilis. 1114 00:50:23,590 --> 00:50:25,300 Siya ay malakas. 1115 00:50:25,300 --> 00:50:27,700 Siya ay TCPIP. 1116 00:50:27,700 --> 00:50:30,420 At siya ay nakuha ang iyong address. 1117 00:50:30,420 --> 00:50:32,920 1118 00:50:32,920 --> 00:50:34,590 Mandirigma ng Net. 1119 00:50:34,590 --> 00:50:35,290 >> [END-playback ng video] 1120 00:50:35,290 --> 00:50:38,070 >> Tagapagsalita 1: Iyon ay kung paano ang internet ay dapat gumana tulad ng susunod na linggo. 1121 00:50:38,070 --> 00:50:40,406