1 00:00:00,000 --> 00:00:00,500 2 00:00:00,500 --> 00:00:11,137 [Musika nagpe-play] 3 00:00:11,137 --> 00:00:12,220 David J. MALAN: Lahat ng karapatan. 4 00:00:12,220 --> 00:00:13,950 Ito ay CS50. 5 00:00:13,950 --> 00:00:18,560 Ito ay linggo limang nagpatuloy, at kami may ilang mga mabuting balita at ilang masamang balita. 6 00:00:18,560 --> 00:00:21,140 Kaya mabuting balita ay na CS50 Ilulunsad ito Biyernes. 7 00:00:21,140 --> 00:00:24,430 Kung nais mong sumali sa amin, magtungo sa karaniwan URL dito. 8 00:00:24,430 --> 00:00:28,670 Kahit na mas mahusay na balita, walang mga panayam ito darating na Lunes ang ika-13. 9 00:00:28,670 --> 00:00:31,970 Bahagyang mas mas mahusay na balita, pagsusulit zero ay sa susunod na Miyerkules. 10 00:00:31,970 --> 00:00:33,840 Higit pang mga detalye ay maaaring maging makikita sa URL na ito dito. 11 00:00:33,840 --> 00:00:36,340 At sa ibabaw ng susunod na dalawang araw ipapakita namin ma-pagpuno sa blangko 12 00:00:36,340 --> 00:00:39,234 patungkol sa mga kuwarto na na nakalaan namin. 13 00:00:39,234 --> 00:00:41,400 Mas mahusay na balita ay na mayroong idedetalye maging isang pagsusuri kurso-wide 14 00:00:41,400 --> 00:00:43,570 session na ito darating Lunes sa gabi. 15 00:00:43,570 --> 00:00:46,270 Manatiling nakatutok sa kurso ng website para sa lokasyon at mga detalye. 16 00:00:46,270 --> 00:00:49,290 Mga seksyon, kahit na ito ay isang holiday, ay magkakaroon din ng matugunan pati na rin. 17 00:00:49,290 --> 00:00:50,490 18 00:00:50,490 --> 00:00:52,940 Pinakamahusay na mga balita, panayam sa tabi Biyernes. 19 00:00:52,940 --> 00:00:56,220 Kaya ito ay isang tradisyon namin mayroon, tulad ng bawat ang syllabus. 20 00:00:56,220 --> 00:00:58,100 Just-- ito ay magiging kahanga-hangang. 21 00:00:58,100 --> 00:01:02,510 Makakakita ka ng mga bagay tulad ng pare-pareho ang panahon mga istraktura ng data 22 00:01:02,510 --> 00:01:04,730 at hash table at mga puno at pagsusubok. 23 00:01:04,730 --> 00:01:07,150 At kami makipag-usap tungkol sa mga problema sa kaarawan. 24 00:01:07,150 --> 00:01:09,440 Ang isang buong bungkos ng mga bagay-bagay Naghihintay sa susunod na Biyernes. 25 00:01:09,440 --> 00:01:11,212 26 00:01:11,212 --> 00:01:12,200 OK. 27 00:01:12,200 --> 00:01:13,190 Anyhow. 28 00:01:13,190 --> 00:01:17,080 >> Kaya isipin na naging kami tumututok sa ang larawang ito ng kung ano ang 29 00:01:17,080 --> 00:01:18,980 sa loob ng memorya ng aming computer. 30 00:01:18,980 --> 00:01:22,875 Kaya memory o RAM ay kung saan programa umiiral habang nagpapatakbo ka ng mga ito. 31 00:01:22,875 --> 00:01:25,215 Kung nag-double-click ang isang icon upang tumakbo ang ilang mga programa 32 00:01:25,215 --> 00:01:27,520 o i-double-click ang isang na icon upang buksan ang ilang mga file, 33 00:01:27,520 --> 00:01:30,430 ito ay load mula sa iyong hard humimok o solid estado biyahe 34 00:01:30,430 --> 00:01:34,190 sa RAM, Random Access Memory, kung saan ito ay nabubuhay hanggang napupunta off ang kapangyarihan, 35 00:01:34,190 --> 00:01:36,700 ang laptop panakip nagsasara, o lumabas ka sa program. 36 00:01:36,700 --> 00:01:38,960 >> Ngayon na memorya, ng na marahil mayroon kang 37 00:01:38,960 --> 00:01:41,950 1 gigabyte mga araw na ito, 2 gigabytes, o kahit na higit pa, 38 00:01:41,950 --> 00:01:44,420 ay karaniwang inilatag out para sa isang naibigay na programa 39 00:01:44,420 --> 00:01:47,170 sa ganitong uri ng hugis-parihaba pangkonseptong modelo 40 00:01:47,170 --> 00:01:50,860 kung saan mayroon kaming ng stack sa ibaba at isang bungkos ng iba pang mga bagay-bagay sa itaas. 41 00:01:50,860 --> 00:01:53,140 Ang mga bagay sa tuktok napaka nasaksihan namin sa larawan na ito 42 00:01:53,140 --> 00:01:55,670 bago ngunit hindi usapan tungkol sa ay ang tinatawag na segment ng teksto. 43 00:01:55,670 --> 00:01:58,419 Segment ng Teksto lamang ang magarbong paraan ng sinasabi ng mga zero at mga na 44 00:01:58,419 --> 00:02:01,150 sumulat ng iyong aktwal na pinagsama-sama program. 45 00:02:01,150 --> 00:02:03,910 >> Kaya kapag nag-double-click Microsoft Word sa iyong Mac o PC, 46 00:02:03,910 --> 00:02:08,030 o kapag nagpatakbo ka ng tuldok iwa Mario sa isang Linux computer sa iyong terminal na window, 47 00:02:08,030 --> 00:02:12,460 ang mga zero at mga na gumawa ng sulat Word o Mario ay pansamantalang naka-imbak 48 00:02:12,460 --> 00:02:16,610 sa RAM ng iyong computer sa gayon tinatawag na segment ng teksto para sa isang partikular na programa. 49 00:02:16,610 --> 00:02:19,080 Sa ibaba na napupunta nasimulan at uninitialized data. 50 00:02:19,080 --> 00:02:22,655 Ito ay mga bagay-bagay tulad ng mga pangkalahatang variable, na hindi na namin ginagamit ang marami sa, 51 00:02:22,655 --> 00:02:24,910 ngunit sa okasyon hindi namin Nagkaroon mga pangkalahatang variable 52 00:02:24,910 --> 00:02:28,819 o statically tinukoy na string mahirap ay naka-code na mga salita gaya ng "kumusta" 53 00:02:28,819 --> 00:02:31,860 na hindi na kinunan sa mula sa gumagamit na ang na hard-code sa iyong programa. 54 00:02:31,860 --> 00:02:34,230 >> Ngayon, down sa ibaba namin mayroon ng tinatawag na stack. 55 00:02:34,230 --> 00:02:37,665 At ng stack, kaya sa ngayon, naging kami gamit para sa kung ano ang mga uri ng mga layunin? 56 00:02:37,665 --> 00:02:39,706 57 00:02:39,706 --> 00:02:40,997 Ano ang mga stack na ginagamit para sa? 58 00:02:40,997 --> 00:02:41,160 Oo? 59 00:02:41,160 --> 00:02:42,070 >> Madla: Mga Pag-andar. 60 00:02:42,070 --> 00:02:43,320 >> David J. MALAN: Para sa mga pag-andar? 61 00:02:43,320 --> 00:02:44,980 Sa anong mga kahulugan para sa mga pag-andar? 62 00:02:44,980 --> 00:02:48,660 >> Madla: Kapag tumawag ka ng isang function, ang mga argument ay kinopya papunta sa stack. 63 00:02:48,660 --> 00:02:49,660 >> David J. MALAN: Eksaktong. 64 00:02:49,660 --> 00:02:52,650 Kapag tumawag ka ng isang function, nito mga argument ay kinopya papunta sa stack. 65 00:02:52,650 --> 00:02:56,330 Kaya ang anumang mga X o Y o A o B na kayo ay pagpasa sa isang function 66 00:02:56,330 --> 00:02:58,680 Pansamantalang ilagay sa ng tinatawag na stack, 67 00:02:58,680 --> 00:03:02,000 tulad lamang ng isa sa mga Annenberg dining hall trays, at din bagay 68 00:03:02,000 --> 00:03:03,190 tulad ng mga lokal na variable. 69 00:03:03,190 --> 00:03:06,290 Kung ang iyong foo function na o ang iyong swap May mga lokal na variable function, 70 00:03:06,290 --> 00:03:08,602 tulad ng Temp, ang dalawang napupunta sa stack. 71 00:03:08,602 --> 00:03:11,560 Ngayon, hindi namin makipag-usap ng masyadong maraming tungkol sa ang mga ito, ngunit ang mga variable na kapaligiran 72 00:03:11,560 --> 00:03:15,690 sa ilalim Nakita namin ang isang habang ang nakalipas kapag Ako ay futzing sa keyboard ng isang araw 73 00:03:15,690 --> 00:03:20,050 at sinimulan ko pag-access sa mga bagay tulad ng argv 100 o argv 1,000, 74 00:03:20,050 --> 00:03:22,320 lamang elements-- ko makalimutan ang numbers-- ngunit na 75 00:03:22,320 --> 00:03:24,330 ay hindi dapat na ma-access sa pamamagitan ng akin. 76 00:03:24,330 --> 00:03:26,581 Sinimulan na naming nakikita ang ilang mga funky mga simbolo sa screen. 77 00:03:26,581 --> 00:03:28,330 Yaong ay tinatawag na kapaligiran variable 78 00:03:28,330 --> 00:03:32,390 tulad ng mga setting ng global para sa aking programa o para sa aking computer, hindi 79 00:03:32,390 --> 00:03:37,090 hindi nauugnay sa kamakailang bug na namin tinalakay, 80 00:03:37,090 --> 00:03:39,670 Shellshock, na naging plaguing lubos ng ilang mga computer. 81 00:03:39,670 --> 00:03:42,960 >> Ngayon Panghuli, sa focus ngayong araw magpapadala kami sa huli nasa heap. 82 00:03:42,960 --> 00:03:44,864 Ito ay isa pang chunk ng memorya. 83 00:03:44,864 --> 00:03:47,030 At fundamentally ang lahat ng ito memorya ay pareho bagay-bagay. 84 00:03:47,030 --> 00:03:48,040 Ito ay ang parehong hardware. 85 00:03:48,040 --> 00:03:49,956 Humihingi kami lamang ang uri ng pagpapagamot ng iba't ibang mga kumpol 86 00:03:49,956 --> 00:03:51,460 ng mga byte na para sa iba't ibang mga layunin. 87 00:03:51,460 --> 00:03:56,540 Heap Ang Pupunta rin upang maging kung saan variable at memory na hiniling mo 88 00:03:56,540 --> 00:03:58,810 mula sa operating system Pansamantalang naka-imbak. 89 00:03:58,810 --> 00:04:01,890 >> Ngunit mayroong uri ng problema dito, pati na nagpapahiwatig sa larawan. 90 00:04:01,890 --> 00:04:05,261 -Uri-uriin kami ng may dalawang ships tungkol sumalungat. 91 00:04:05,261 --> 00:04:08,010 Dahil habang ginagamit mo ang higit pa at higit pa ng stack, at bilang ating nakikita ngayon 92 00:04:08,010 --> 00:04:11,800 pasulong, habang ginagamit mo ang higit pa at higit pa sa mga heap, tiyak masamang bagay na maaaring mangyari. 93 00:04:11,800 --> 00:04:15,054 At sa katunayan, maaari naming humimok na sinasadya o hindi sinasadyang. 94 00:04:15,054 --> 00:04:16,970 Kaya ang cliffhanger huling oras ay program na ito, 95 00:04:16,970 --> 00:04:20,570 na hindi maghatid ng anumang functional layunin na iba sa upang ipakita 96 00:04:20,570 --> 00:04:24,750 kung paano mo bilang isang masamang tao ay maaaring aktwal na tumagal bentahe ng mga bug programa ng isang tao sa 97 00:04:24,750 --> 00:04:28,460 at angkinin ang isang programa o kahit isang buong sistema ng computer o server. 98 00:04:28,460 --> 00:04:31,660 Kaya lang sa sulyap panandalian, ikaw mapapansin na ang pangunahing sa ibaba 99 00:04:31,660 --> 00:04:34,510 tumatagal sa command line mga argument, bilang bawat argv. 100 00:04:34,510 --> 00:04:38,480 At ito ay isang tawag sa isang function f, mahalagang isang nameless function na tinatawag na 101 00:04:38,480 --> 00:04:40,250 f, at ito ay ang pagpasa sa argv [1]. 102 00:04:40,250 --> 00:04:43,960 >> Kaya kahit anong salita uri ng user sa sa ang prompt pagkatapos ng pangalan ng programa na ito, 103 00:04:43,960 --> 00:04:49,310 at pagkatapos ay ang di-makatwirang pag-andar up tuktok, f, tumatagal sa isang string, aka char *, 104 00:04:49,310 --> 00:04:51,720 bilang sinimulan namin ang pag-usapan, at pagtawag ito lang ito "bar." 105 00:04:51,720 --> 00:04:53,310 Ngunit maaari naming tumawag ito ng kahit ano. 106 00:04:53,310 --> 00:04:57,470 At pagkatapos nito declares, sa loob ng f, isang array ng mga character 107 00:04:57,470 --> 00:04:59,930 na tinatawag na c-- 12 tulad character. 108 00:04:59,930 --> 00:05:03,580 >> Ngayon, sa pamamagitan ng mga kuwento ako ay nagsasabi sa ng ilang sandali ang nakalipas, kung saan sa memory 109 00:05:03,580 --> 00:05:06,720 ay c, o ay ang mga 12 char ng pagpunta sa mga end up? 110 00:05:06,720 --> 00:05:07,570 Lamang na maging malinaw. 111 00:05:07,570 --> 00:05:08,070 Oo? 112 00:05:08,070 --> 00:05:08,590 >> Madla: Sa stack. 113 00:05:08,590 --> 00:05:09,420 >> David J. MALAN: Sa stack. 114 00:05:09,420 --> 00:05:10,720 Kaya c ay isang lokal na variable. 115 00:05:10,720 --> 00:05:14,079 Kami ay humihingi ng 12 na karakter o 12 bytes. 116 00:05:14,079 --> 00:05:16,120 Yaong ay pagpunta sa mga end up sa tinatawag na stack. 117 00:05:16,120 --> 00:05:18,530 Ngayon sa wakas ay ang iba pang mga pagpapaandar na talagang kaakit-akit na kapaki-pakinabang, 118 00:05:18,530 --> 00:05:20,571 ngunit kami ay hindi talaga ginamit ito ang ating mga sarili, strncopy. 119 00:05:20,571 --> 00:05:21,550 120 00:05:21,550 --> 00:05:25,200 Ito ay nangangahulugan string na kopya, ngunit lamang n titik, n character. 121 00:05:25,200 --> 00:05:31,990 Kaya n character ay magiging kinopya mula sa bar sa c. 122 00:05:31,990 --> 00:05:32,980 At kung gaano karaming? 123 00:05:32,980 --> 00:05:34,110 Ang haba ng bar. 124 00:05:34,110 --> 00:05:36,330 Kaya sa ibang salita, na isang linya, strncopy, 125 00:05:36,330 --> 00:05:39,500 ay pagpunta sa kopyahin epektibong humadlang in sa c. 126 00:05:39,500 --> 00:05:42,340 >> Ngayon, lamang sa uri ng inaasahan mga kapakanang moral ng mga kuwentong ito, 127 00:05:42,340 --> 00:05:44,750 ano ang potensyal na problema dito? 128 00:05:44,750 --> 00:05:49,710 Kahit na kami ay check ang haba ng bar at pagpasa ito sa strncopy, 129 00:05:49,710 --> 00:05:53,145 kung ano ang iyong GUT na nagsasabi sa iyo ay sira pa rin tungkol sa programang ito? 130 00:05:53,145 --> 00:05:54,410 131 00:05:54,410 --> 00:05:55,220 Oo? 132 00:05:55,220 --> 00:05:57,491 >> Madla: ba ang hindi isama room para sa mga null character. 133 00:05:57,491 --> 00:05:59,990 David J. MALAN: Hindi kinabibilangan ng room para sa mga null character. 134 00:05:59,990 --> 00:06:02,073 Potensyal na, hindi tulad ng sa nakalipas na kasanayan hindi namin kahit na 135 00:06:02,073 --> 00:06:04,810 may kaya magkano ang bilang ng plus 1 hanggang tumanggap na null character. 136 00:06:04,810 --> 00:06:06,649 Pero kahit na mas masahol kaysa iyon. 137 00:06:06,649 --> 00:06:07,940 Ano pa ang bagsak namin upang gawin? 138 00:06:07,940 --> 00:06:08,432 Oo? 139 00:06:08,432 --> 00:06:09,307 >> Madla: [INAUDIBLE] 140 00:06:09,307 --> 00:06:15,440 141 00:06:15,440 --> 00:06:16,440 David J. MALAN: Perpekto. 142 00:06:16,440 --> 00:06:18,490 Mahirap na naka-code na namin 12 medyo nagkataon. 143 00:06:18,490 --> 00:06:19,497 144 00:06:19,497 --> 00:06:21,330 Iyon ay hindi kaya magkano ang problema, ngunit ang katotohanan 145 00:06:21,330 --> 00:06:25,630 na hindi man lamang namin ang pagsuri kung ang haba ng bar ay mas mababa sa 12, 146 00:06:25,630 --> 00:06:28,530 sa kasong ito ay magiging Ligtas na ilagay ito papunta sa memorya ng 147 00:06:28,530 --> 00:06:30,260 tinatawag c na nai-inilalaan namin. 148 00:06:30,260 --> 00:06:32,960 Sa katunayan, kung ang bar ay tulad ng 20 character ang haba, 149 00:06:32,960 --> 00:06:39,010 Lumilitaw na ito ang function na pagkopya 20 na mga character mula sa bar c, at sa gayon 150 00:06:39,010 --> 00:06:41,310 pagkuha ng hindi bababa sa 8 bytes na hindi ito ay kailangang maging. 151 00:06:41,310 --> 00:06:42,690 Iyan ang implikasyon dito. 152 00:06:42,690 --> 00:06:44,347 >> Kaya sa maikling, putol na programa. 153 00:06:44,347 --> 00:06:45,180 Hindi tulad ng isang malaking deal. 154 00:06:45,180 --> 00:06:46,360 Siguro kang makakuha ng segmentation fault. 155 00:06:46,360 --> 00:06:47,651 Na ang lahat Nagkaroon kami ng mga bug sa programa. 156 00:06:47,651 --> 00:06:50,196 Namin ang lahat ng maaaring mayroon bug sa mga programa sa ngayon. 157 00:06:50,196 --> 00:06:51,320 Ngunit kung ano ang mga implikasyon? 158 00:06:51,320 --> 00:06:54,390 Well, narito ang isang naka-zoom-in na bersyon ng na larawan ng memorya aking computer. 159 00:06:54,390 --> 00:06:56,230 Ito ay sa ilalim ng aking stack. 160 00:06:56,230 --> 00:06:59,644 At sa katunayan, sa ilalim napaka ay kung ano ang tinatawag magulang routine stack, magarbong paraan 161 00:06:59,644 --> 00:07:00,560 ng na nagsasabi na ang pangunahing. 162 00:07:00,560 --> 00:07:03,772 Kaya kung sinuman na tinatawag na ang pag-andar f na pinag-uusapan natin ang tungkol. 163 00:07:03,772 --> 00:07:05,230 Kaya ito ay sa ilalim ng stack. 164 00:07:05,230 --> 00:07:06,640 Return address ay isang bagong bagay. 165 00:07:06,640 --> 00:07:08,810 Palaging Naging doon, palagi nang naging sa na larawan. 166 00:07:08,810 --> 00:07:10,440 Kami ay hindi kailanman lamang na tinatawag na pansin sa mga ito. 167 00:07:10,440 --> 00:07:15,290 Dahil ito ay lumiliko out ang paraan kung paano gumagana c ay na kapag tawag isa-andar sa isa pa, 168 00:07:15,290 --> 00:07:18,780 hindi lamang gawin ang mga argument na iyon function na makakuha ng matutulak papunta sa stack, 169 00:07:18,780 --> 00:07:22,470 hindi lamang gawin lokal na ang pag-andar ng variable makakuha matutulak papunta sa stack, 170 00:07:22,470 --> 00:07:26,820 isang bagay na tinatawag na return address din ay makakakuha ilagay papunta sa stack. 171 00:07:26,820 --> 00:07:33,330 Sa partikular, kung pangunahing tawag foo, ang pangunahing ng sariling address sa memory, baka may isang bagay, 172 00:07:33,330 --> 00:07:38,240 mabisa ay makakakuha ilagay papunta sa stack upang kapag f tapos na e-execute ito 173 00:07:38,240 --> 00:07:43,630 alam kung saan upang lumipat pabalik sa sa teksto segment upang magpatuloy na e-execute. 174 00:07:43,630 --> 00:07:47,760 >> Kaya, kung hindi kami dito conceptually, sa pangunahing, pagkatapos ay makakakuha ng f tinatawag. 175 00:07:47,760 --> 00:07:50,200 Paano gumagana ang f malalaman kung sino ang sa kamay control pabalik? 176 00:07:50,200 --> 00:07:52,020 Well, ito kaunti breadcrumb sa pula dito, 177 00:07:52,020 --> 00:07:54,978 na tinatawag na ang return address, ito lamang pagsusuri, ano ang na return address? 178 00:07:54,978 --> 00:07:57,039 Oh, hayaan mo akong lumipat pabalik sa pangunahing dito. 179 00:07:57,039 --> 00:07:59,080 At iyon ang ilang sandali ng isang oversimplification, 180 00:07:59,080 --> 00:08:00,750 dahil ang mga zero at mga para sa pangunahing ay technically 181 00:08:00,750 --> 00:08:01,967 hanggang dito sa tech segment. 182 00:08:01,967 --> 00:08:03,800 Ngunit iyon lamang ang mga ideya. f lamang ay may upang malaman kung ano 183 00:08:03,800 --> 00:08:06,680 upang kung saan kontrol sa huli napupunta bumalik. 184 00:08:06,680 --> 00:08:09,790 >> Subalit ang paraan computer na mahaba inilatag nang mga bagay 185 00:08:09,790 --> 00:08:12,320 tulad ng lokal na mga variable at mga argument ay tulad nito. 186 00:08:12,320 --> 00:08:17,180 Kaya sa tuktok ng larawan na ito sa asul ay ang stack frame para sa f, kaya ang lahat ng 187 00:08:17,180 --> 00:08:19,630 ng memorya na f partikular na ay ginagamit. 188 00:08:19,630 --> 00:08:22,990 Kaya nang naaayon, mapapansin na ang bar ay sa larawan na ito. 189 00:08:22,990 --> 00:08:23,980 Bar ay argumento nito. 190 00:08:23,980 --> 00:08:27,240 At namin na-claim na mga argumento upang mga function makakuha matutulak papunta sa stack. 191 00:08:27,240 --> 00:08:29,910 At c, siyempre, ay sa larawan na ito din. 192 00:08:29,910 --> 00:08:33,520 >> At para lamang sa mga layuning notational, mapansin sa kaliwang tuktok na sulok 193 00:08:33,520 --> 00:08:37,020 ay kung ano ang magiging c bracket 0 at pagkatapos ay bahagyang pababa sa kanan 194 00:08:37,020 --> 00:08:38,220 ay c bracket 11. 195 00:08:38,220 --> 00:08:41,240 Kaya sa ibang salita, maaari mong isipin na mayroong isang grid ng mga byte 196 00:08:41,240 --> 00:08:44,380 doon, una sa kung saan ay kaliwang tuktok, sa ilalim ng kung aling mga 197 00:08:44,380 --> 00:08:48,360 ay ang huling ng mga 12 bytes. 198 00:08:48,360 --> 00:08:49,930 >> Ngunit ngayon subukang i-fast forward. 199 00:08:49,930 --> 00:08:55,580 Ano ang tungkol sa mangyayari kung pumasa namin sa isang string bar na mas mahaba kaysa c? 200 00:08:55,580 --> 00:08:59,130 At hindi namin Sinusuri kung ito ay sa katunayan mas mahaba kaysa sa 12. 201 00:08:59,130 --> 00:09:03,146 Aling mga bahagi ng larawan na ito ay pagpunta sa makakuha-o-overwrite sa pamamagitan ng mga byte 0, 1, 2, 3, 202 00:09:03,146 --> 00:09:07,890 tuldok tuldok tuldok, 11, at pagkatapos ay masamang, 12, 13 sa pamamagitan ng 19? 203 00:09:07,890 --> 00:09:11,820 Ano ang nangyayari sa mangyari dito, kung infer ka mula sa pag-order 204 00:09:11,820 --> 00:09:14,790 na c bracket 0 ay nasa tuktok at c bracket 11 ay isang uri ng pababa 205 00:09:14,790 --> 00:09:15,812 sa kanan? 206 00:09:15,812 --> 00:09:16,796 Oo? 207 00:09:16,796 --> 00:09:19,260 >> Madla: Well, ito ay pagpunta patungan ang mga char * bar. 208 00:09:19,260 --> 00:09:22,260 >> David J. MALAN: Oo, mukhang ka ng pagpunta sa patungan char * bar. 209 00:09:22,260 --> 00:09:26,245 At mas masahol pa, kung magpadala sa iyo sa isang talagang mahaba string, maaari mong patungan kahit ano? 210 00:09:26,245 --> 00:09:27,460 211 00:09:27,460 --> 00:09:28,570 Ang return address. 212 00:09:28,570 --> 00:09:31,380 Aling muli, ay tulad ng isang breadcrumb upang sabihin sa programa kung saan ang 213 00:09:31,380 --> 00:09:34,060 upang bumalik sa kapag f tapos na tinatawag. 214 00:09:34,060 --> 00:09:37,140 >> Kaya kung ano ang karaniwang gawin masamang guys ay kung dumating sila sa isang programa 215 00:09:37,140 --> 00:09:41,290 na sila malaman kung ay exploitable, mayroong bug sa paraang 216 00:09:41,290 --> 00:09:43,550 na siya ay maaaring tumagal ng Samantalahin ang na bug, 217 00:09:43,550 --> 00:09:45,720 Sa pangkalahatan ay hindi sila makakuha ng karapatang ito sa unang pagkakataon. 218 00:09:45,720 --> 00:09:48,590 Simulan lang nila ang pagpapadala ng, halimbawa, random na string sa iyong programa, 219 00:09:48,590 --> 00:09:50,260 kung sa keyboard, o tapat nila marahil 220 00:09:50,260 --> 00:09:52,740 magsulat ng isang maliit na programa sa makatarungan awtomatikong bumuo ng mga string, 221 00:09:52,740 --> 00:09:55,430 at simulan ang banging sa iyong programa sa pamamagitan ng pagpapadala sa maraming iba't ibang input 222 00:09:55,430 --> 00:09:56,340 sa iba't ibang mga haba. 223 00:09:56,340 --> 00:09:58,990 >> Sa sandaling ang iyong mga pag-crash ng programa, na ang isang kamangha-manghang mga bagay. 224 00:09:58,990 --> 00:10:01,020 Dahil ito ay nangangahulugan na siya o siya ay natuklasan 225 00:10:01,020 --> 00:10:02,660 kung ano ay marahil sa katunayan ng isang bug. 226 00:10:02,660 --> 00:10:05,830 At pagkatapos ay maaari nilang makakuha ng higit pang matalino at simulan ang tumututok sa higit pang makitid 227 00:10:05,830 --> 00:10:07,420 kung paano samantalahin na bug. 228 00:10:07,420 --> 00:10:11,480 Sa partikular, kung ano siya ay maaari gawin ay magpadala ng, sa pinakamahusay na kaso, kumusta. 229 00:10:11,480 --> 00:10:12,210 Walang malaking deal. 230 00:10:12,210 --> 00:10:14,750 Ito ay isang string na may sapat na maikli. 231 00:10:14,750 --> 00:10:18,100 Ngunit kung ano kung siya ay nagpapadala, at kami ng tuntuning panlahat ito bilang, 232 00:10:18,100 --> 00:10:20,890 pag-atake code-- kaya zero at mga bago na gumawa ng mga bagay 233 00:10:20,890 --> 00:10:25,150 tulad ng Rm-rf, na alisin ang lahat ng bagay mula sa hard drive o magpadala ng spam 234 00:10:25,150 --> 00:10:27,000 o kahit papaano inaatake ang machine? 235 00:10:27,000 --> 00:10:29,570 >> Kaya kung bawat isa sa mga mga titik A lamang ay kumakatawan, 236 00:10:29,570 --> 00:10:32,380 conceptually, pag-atake, pag-atake, pag-atake, pag-atake, ang ilang mga masamang code 237 00:10:32,380 --> 00:10:36,410 na may ibang tao na sinulat, ngunit kung ang taong iyon ay sapat na smart 238 00:10:36,410 --> 00:10:40,790 hindi lamang isama ang lahat ng ng mga Rm-rfs, kundi pati na rin 239 00:10:40,790 --> 00:10:46,100 mayroon kanyang huling ilang mga byte ay isang numero na tumutugon 240 00:10:46,100 --> 00:10:50,540 sa address ng kanyang o ang kanyang sariling pag-atake code 241 00:10:50,540 --> 00:10:53,820 na siya ang pumasa sa mga in lamang sa pamamagitan ng pagbibigay ito sa prompt, 242 00:10:53,820 --> 00:10:58,760 mabisa mong linlangin ang computer sa makapansin kapag f tapos na e-execute, 243 00:10:58,760 --> 00:11:02,400 naku, oras na para sa akin upang lumaktaw pabalik sa pulang return address. 244 00:11:02,400 --> 00:11:06,070 Ngunit dahil siya ay may kahit papaano overlapped na return address 245 00:11:06,070 --> 00:11:09,602 sa kanilang sariling mga numero, at ang mga ito ay sapat na smart 246 00:11:09,602 --> 00:11:11,560 sa na-configure na numero na mag-refer, tulad ng sa iyo 247 00:11:11,560 --> 00:11:13,740 makita sa sobrang tuktok kaliwang sulok doon, 248 00:11:13,740 --> 00:11:18,020 ang aktwal na address sa computer memorya ng ilan sa kanilang mga pag-atake code, 249 00:11:18,020 --> 00:11:21,740 Maaari linlangin ang isang masamang tao ang computer sa pagpapatupad sa kanyang sariling code. 250 00:11:21,740 --> 00:11:23,700 >> At ang code na iyon, muli, ay maaaring maging kahit ano. 251 00:11:23,700 --> 00:11:26,120 Sa pangkalahatan ito ay tinatawag na shell code, na lamang 252 00:11:26,120 --> 00:11:29,030 isang paraan ng pagsabi na hindi kasing simple ng Rm-rf pangkalahatan ay isang bagay. 253 00:11:29,030 --> 00:11:32,340 Ito ay talagang isang bagay tulad Bash, o isang aktwal na programa na nagbibigay sa kanya 254 00:11:32,340 --> 00:11:37,230 o ang kanyang control program upang maisagawa anumang bagay na nais nilang. 255 00:11:37,230 --> 00:11:40,210 Kaya sa maikling, ito ang lahat ng derives mula sa simpleng katotohanan 256 00:11:40,210 --> 00:11:44,490 ang bug na ito kasangkot hindi pagsuri ang mga hangganan ng iyong array. 257 00:11:44,490 --> 00:11:47,250 At dahil sa paraan ng mga computer sa trabaho ay na sila 258 00:11:47,250 --> 00:11:49,430 gamitin ang stack mula sa mabisa, conceptually, 259 00:11:49,430 --> 00:11:54,830 ibaba sa up, ngunit pagkatapos ay ang elemento itulak mo papunta sa stack na palaguin itaas pababa, 260 00:11:54,830 --> 00:11:56,624 ito ay hindi kapani-paniwalang may problemang. 261 00:11:56,624 --> 00:11:58,290 Ngayon, may mga paraan upang gumawa sa paligid ito. 262 00:11:58,290 --> 00:12:00,800 At tapat, may mga wika kung saan upang gumawa sa paligid ito. 263 00:12:00,800 --> 00:12:03,100 Java ay immune, halimbawa, sa partikular na isyu. 264 00:12:03,100 --> 00:12:04,110 Dahil wala silang magbigay sa iyo ng payo. 265 00:12:04,110 --> 00:12:05,943 Hindi nila magbibigay sa iyo ng direct memory address. 266 00:12:05,943 --> 00:12:08,560 Kaya may mga kapangyarihan na ito na mayroon kami galawin ng kahit ano sa memorya 267 00:12:08,560 --> 00:12:11,580 kami ay nais, admittedly, mahusay na panganib. 268 00:12:11,580 --> 00:12:12,430 >> Kaya abangan. 269 00:12:12,430 --> 00:12:14,596 Kung, tapat, sa mga buwan ng o taon na dumating, anumang oras 270 00:12:14,596 --> 00:12:17,740 basahin mo ang tungkol sa ilang pagsasamantala ng isang programa o ng isang server, 271 00:12:17,740 --> 00:12:22,370 kung kailanman nakakita ka ng isang pahiwatig ng isang bagay tulad ng isang buffer overflow atake, 272 00:12:22,370 --> 00:12:25,390 o stack overflow ay isa pang uri ng pag-atake, katulad sa espiritu, 273 00:12:25,390 --> 00:12:28,770 magkano bilang inspirasyon ng website pangalanan, kung alam mo ito, 274 00:12:28,770 --> 00:12:33,170 lahat ng ito ay tungkol sa pakikipag-usap lamang overflowing ang laki ng ilang mga karakter 275 00:12:33,170 --> 00:12:36,200 array o ilang array sa mas pangkalahatang paraan. 276 00:12:36,200 --> 00:12:38,822 Ang anumang mga katanungan, pagkatapos, sa ito? 277 00:12:38,822 --> 00:12:39,780 Huwag subukan ito sa bahay. 278 00:12:39,780 --> 00:12:41,620 279 00:12:41,620 --> 00:12:42,300 >> Lahat ng karapatan. 280 00:12:42,300 --> 00:12:47,270 Kaya malloc kaya ngayon ay naging aming bagong kaibigan na maaari naming maglaan ng memorya 281 00:12:47,270 --> 00:12:50,540 na hindi naman namin alam kung sa sumulong na gusto naming kaya wala kaming 282 00:12:50,540 --> 00:12:52,920 sa hard code sa aming mga numero ng programa tulad ng 12. 283 00:12:52,920 --> 00:12:55,550 Sa sandaling Sinasabi sa amin ang user kung magkano data siya ay nais na input, 284 00:12:55,550 --> 00:12:58,000 maaari naming malloc na maraming memorya. 285 00:12:58,000 --> 00:13:01,484 >> Kaya malloc ito ay lumiliko out, sa lawak namin na ginagamit mo ito, 286 00:13:01,484 --> 00:13:03,900 tahasan huling beses, at pagkatapos ay ka guys ay nai-gamit ito 287 00:13:03,900 --> 00:13:08,160 para sa getstring hindi-para sa ilang mga linggo, ang lahat ng memory malloc ni 288 00:13:08,160 --> 00:13:09,820 ay mula sa tinatawag na heap. 289 00:13:09,820 --> 00:13:13,852 At ito ang dahilan kung bakit getstring, halimbawa, Maaari maglaan ng memorya pabagu-bagong 290 00:13:13,852 --> 00:13:16,060 nang walang pag-alam kung ano ang iyong pagpunta sa i-type nang maaga, 291 00:13:16,060 --> 00:13:21,520 ipasa mo pabalik tagaturo patungo sa na memorya, at na memory ay sa iyo pa rin upang panatilihin, 292 00:13:21,520 --> 00:13:24,080 kahit na matapos getstring babalik. 293 00:13:24,080 --> 00:13:27,450 Dahil pagpapabalik pagkatapos ng lahat na ang stack ay patuloy na pagpunta pataas at pababa, 294 00:13:27,450 --> 00:13:27,950 pataas at pababa. 295 00:13:27,950 --> 00:13:30,230 At sa lalong madaling pumupunta ito pababa, na nangangahulugang anumang memory 296 00:13:30,230 --> 00:13:33,030 ginagamit ang pagpapaganang ito dapat hindi dapat gamitin ng sinumang iba pa. 297 00:13:33,030 --> 00:13:34,570 Ito ay ngayon ang mga halaga ng basura. 298 00:13:34,570 --> 00:13:36,120 >> Subalit ang heap ay up dito. 299 00:13:36,120 --> 00:13:39,360 At kung ano ang magaling tungkol sa malloc ay na kapag malloc naglalaan ng memory up dito, 300 00:13:39,360 --> 00:13:42,070 hindi ito naapektuhan, para sa nakararaming bahagi, sa pamamagitan ng stack. 301 00:13:42,070 --> 00:13:46,000 At nang sa gayon ay ma-access ang anumang mga pag-andar memory na na-malloc'd, 302 00:13:46,000 --> 00:13:49,120 kahit na sa pamamagitan ng isang function tulad getstring, kahit na ito ay ibinalik. 303 00:13:49,120 --> 00:13:51,700 >> Ngayon, ang usap ng malloc ay libre. 304 00:13:51,700 --> 00:13:53,900 At sa katunayan, ang panuntunan mo kailangan upang simulan ang pagpapatibay 305 00:13:53,900 --> 00:13:58,950 ay anumang, anumang, anumang oras na gamitin mo malloc Dapat mo ang iyong sarili gamitin ang libreng, sa huli, 306 00:13:58,950 --> 00:14:00,280 sa na parehong pointer. 307 00:14:00,280 --> 00:14:03,289 Ang lahat ng mga oras na ito tayo ay sumusulat mayroong bug, mayroong bug code, para sa maraming mga dahilan. 308 00:14:03,289 --> 00:14:05,580 Ngunit isa sa kung saan ay gamit ang CS50 library, na 309 00:14:05,580 --> 00:14:09,010 mismo ay sadyang mayroong bug, paglabas nito memorya. 310 00:14:09,010 --> 00:14:11,410 Anumang oras na iyong na tinatawag na getstring sa nakalipas na ilang linggo 311 00:14:11,410 --> 00:14:13,870 hinihiling namin sa operating system, Linux, para sa memorya. 312 00:14:13,870 --> 00:14:15,780 At mo pa kailanman sa sandaling naibigay na ito pabalik. 313 00:14:15,780 --> 00:14:17,730 At hindi ito, sa pagsasanay, isang magandang bagay. 314 00:14:17,730 --> 00:14:20,330 >> At Valgrind, isa sa mga mga tool ipinakilala sa Pset 4, 315 00:14:20,330 --> 00:14:22,900 ay tungkol sa pagtulong sa iyo na ngayon ang bug tulad na. 316 00:14:22,900 --> 00:14:27,060 Ngunit thankfully para sa Pset 4 hindi mo kailangang gamitin ang CS50 library o getstring. 317 00:14:27,060 --> 00:14:31,220 Kaya ang anumang mga bug na may kaugnayan sa memorya ay sa huli pagpunta upang maging iyong sarili. 318 00:14:31,220 --> 00:14:34,060 >> Kaya malloc ay higit pa sa maginhawa para sa layuning ito. 319 00:14:34,060 --> 00:14:37,420 Maaari aktwal na namin ngayon malutas fundamentally iba't ibang mga problema, 320 00:14:37,420 --> 00:14:41,640 at fundamentally malutas ang problema nang higit pa epektibo tulad ng bawat linggo pangako ng zero. 321 00:14:41,640 --> 00:14:44,720 Kaya ngayon ito ay ang sexiest istraktura ng data mayroon kaming. 322 00:14:44,720 --> 00:14:47,804 At sa pamamagitan ng istraktura ng data ibig sabihin ko lang isang paraan ng conceptualizing memory 323 00:14:47,804 --> 00:14:50,720 sa isang paraan na napupunta lampas lamang sinasabi, ito ay isang int, ito ay isang char. 324 00:14:50,720 --> 00:14:52,930 Maaari naming magsimula sa kumpol ng mga bagay nang magkakasama. 325 00:14:52,930 --> 00:14:54,460 >> Kaya isang array ay tumingin tulad nito. 326 00:14:54,460 --> 00:14:57,270 At kung ano ang key sa tungkol sa isang array ay tumutulong ito ay nagbibigay sa iyo 327 00:14:57,270 --> 00:14:59,724 back-to-pabalik chunks ng memorya, ang bawat isa 328 00:14:59,724 --> 00:15:02,765 ay magiging ng parehong uri, int, int, int, int, o char, char, char, 329 00:15:02,765 --> 00:15:03,330 char. 330 00:15:03,330 --> 00:15:04,496 Ngunit mayroong ilang mga downsides. 331 00:15:04,496 --> 00:15:06,570 Ito halimbawa, ay isang hanay ng mga laki ng anim. 332 00:15:06,570 --> 00:15:10,650 Ipagpalagay mong punan ito ng array na may anim na mga numero at pagkatapos ay, para sa anumang kadahilanan, 333 00:15:10,650 --> 00:15:13,187 Nais ng iyong mga gumagamit upang bigyan ikaw 1/7 numero. 334 00:15:13,187 --> 00:15:14,020 Saan mo ilagay ito? 335 00:15:14,020 --> 00:15:15,490 336 00:15:15,490 --> 00:15:18,990 >> Ano ang solusyon kung mayroon kang Nalikha ang isang array sa stack, 337 00:15:18,990 --> 00:15:22,030 halimbawa, sa pamamagitan lamang ng linggo dalawang pagtatanda na ipinakilala namin, 338 00:15:22,030 --> 00:15:23,730 ng mga square bracket na may isang numero sa loob? 339 00:15:23,730 --> 00:15:25,160 340 00:15:25,160 --> 00:15:27,260 Well, mayroon ka ng anim na mga numero sa mga kahon. 341 00:15:27,260 --> 00:15:28,530 Ano ang gusto maging iyong instincts? 342 00:15:28,530 --> 00:15:29,973 Saan ninyo gustong ilagay ito? 343 00:15:29,973 --> 00:15:30,860 >> Madla: [INAUDIBLE] 344 00:15:30,860 --> 00:15:31,315 >> David J. MALAN: Paumanhin? 345 00:15:31,315 --> 00:15:32,380 >> Madla: Ilagay ninyo sa dulo. 346 00:15:32,380 --> 00:15:33,796 >> David J. MALAN: Ilagay ninyo sa dulo. 347 00:15:33,796 --> 00:15:35,880 Kaya sa ibabaw lamang sa kanan, sa labas ng ang kahon na ito. 348 00:15:35,880 --> 00:15:38,710 Aling ay magiging maganda, ngunit ito lumiliko out hindi mo maaaring gawin iyon. 349 00:15:38,710 --> 00:15:41,350 Dahil kung hindi mo hiniling para sa chunk ng memorya, 350 00:15:41,350 --> 00:15:44,490 maaaring ito ay sa pamamagitan ng pagkakataon na ito ay ginagamit sa pamamagitan ng ilang iba pang mga variable 351 00:15:44,490 --> 00:15:45,030 nang sama-sama. 352 00:15:45,030 --> 00:15:49,210 Isipin pabalik sa isang linggo o kaya kapag inilatag namin out Zamyla at Davin at Gabe ng mga pangalan 353 00:15:49,210 --> 00:15:49,930 sa memory. 354 00:15:49,930 --> 00:15:51,638 Sila ay literal pabalik upang i-back sa likod. 355 00:15:51,638 --> 00:15:53,550 Kaya hindi namin maaari kinakailangan pinagkakatiwalaan na kung ano ang 356 00:15:53,550 --> 00:15:55,800 sa paglipas dito ay magagamit para sa akin upang gamitin. 357 00:15:55,800 --> 00:15:56,990 >> Kaya ano pa ang maaari mong gawin? 358 00:15:56,990 --> 00:16:00,282 Well, sa sandaling napagtatanto mo Kailangan ng isang hanay ng mga laki ng pitong, 359 00:16:00,282 --> 00:16:02,490 maaari mo lamang lumikha ng isang na hanay ng mga sukat ng pitong pagkatapos ay gamitin ang 360 00:16:02,490 --> 00:16:05,950 isang para sa loop o isang habang loop, kopyahin ito sa bagong array, 361 00:16:05,950 --> 00:16:09,680 at pagkatapos ay kahit papaano lamang mapupuksa ang ito array itigil o lamang na gamitin ito. 362 00:16:09,680 --> 00:16:12,130 Ngunit iyon lamang ang hindi partikular na mahusay. 363 00:16:12,130 --> 00:16:15,340 Sa maikli, array huwag mong pabayaan dynamic na baguhin mo ang sukat. 364 00:16:15,340 --> 00:16:17,900 >> Kaya sa isa kamay kang makakuha ng random na pag-access, na kung saan ay kamangha-manghang. 365 00:16:17,900 --> 00:16:20,108 Dahil nagbibigay-daan ito sa amin gawin ang mga bagay tulad ng hatiin at lupigin, 366 00:16:20,108 --> 00:16:23,100 binary paghahanap, ang lahat ay hindi namin usapan tungkol sa screen dito. 367 00:16:23,100 --> 00:16:24,950 Ngunit mo ipinta ang iyong sarili sa isang sulok. 368 00:16:24,950 --> 00:16:27,810 Sa sandaling pindutin mo sa dulo ng iyong array, 369 00:16:27,810 --> 00:16:29,980 kailangan mo lang gawin ng isang napaka mahal na operasyon 370 00:16:29,980 --> 00:16:33,910 o magsulat ng isang buong bungkos ng code sa ngayon haharapin ang mga problema na iyon. 371 00:16:33,910 --> 00:16:36,680 >> Kaya kung ano kung sa halip ay may namin isang bagay na tinatawag na isang listahan, 372 00:16:36,680 --> 00:16:38,820 o ng isang listahan na naka-link sa mga partikular na? 373 00:16:38,820 --> 00:16:41,930 Paano kung sa halip ng pagkakaroon ng parihaba para i-back upang i-back upang i-back, 374 00:16:41,930 --> 00:16:45,730 mayroon kaming mga parihaba na mag-iwan ng kaunti bit ng wiggle room sa pagitan ng mga ito? 375 00:16:45,730 --> 00:16:49,670 At kahit na iginuhit ko na ito larawan o inangkop ang larawang ito 376 00:16:49,670 --> 00:16:54,696 mula sa isa sa ang mga teksto dito upang maging pabalik sa pabalik upang i-back napaka maayos, sa katotohanan, 377 00:16:54,696 --> 00:16:56,820 isa sa mga parihaba Maaaring maging hanggang dito sa memorya. 378 00:16:56,820 --> 00:16:58,028 Ang isa sa mga ito ay maaaring maging hanggang dito. 379 00:16:58,028 --> 00:17:00,420 Ang isa sa mga ito ay maaaring magkaroon ng hanggang dito, sa paglipas dito, at iba pa. 380 00:17:00,420 --> 00:17:02,910 >> Ngunit paano kung iginuhit namin, sa kasong ito, mga arrow 381 00:17:02,910 --> 00:17:05,650 na kahit papaano i-link ang mga parihaba magkasama? 382 00:17:05,650 --> 00:17:08,170 Sa katunayan, nasaksihan namin ang isang teknikal na incarnation ng isang arrow. 383 00:17:08,170 --> 00:17:09,839 384 00:17:09,839 --> 00:17:13,710 Ano pa namin ginamit sa kamakailang araw na iyon, sa ilalim ng hood, 385 00:17:13,710 --> 00:17:15,210 ay kinatawan ng isang arrow? 386 00:17:15,210 --> 00:17:16,290 387 00:17:16,290 --> 00:17:17,349 Ang isang pointer, tama? 388 00:17:17,349 --> 00:17:19,780 >> Kaya kung ano kung, sa halip ng pag-iimbak lamang ang mga numero, 389 00:17:19,780 --> 00:17:23,130 tulad ng 9, 17, 22, 26, 34, paano kung namin na naka-imbak hindi 390 00:17:23,130 --> 00:17:27,079 lamang ng isang numero ngunit isang pointer sa tabi ng bawat tulad number? 391 00:17:27,079 --> 00:17:30,690 Kaya na halos tulad ng gusto mo thread ng karayom ​​sa pamamagitan ng isang buong bungkos ng tela, 392 00:17:30,690 --> 00:17:32,950 kahit papaano tying bagay nang sama-sama, maaari kaparehong 393 00:17:32,950 --> 00:17:35,550 namin na may mga payo, pati na incarnated sa pamamagitan ng mga arrow dito, 394 00:17:35,550 --> 00:17:38,550 uri ng weave magkasama ang mga indibidwal na mga parihaba 395 00:17:38,550 --> 00:17:41,780 sa pamamagitan ng epektibong paggamit ng isang pointer sa tabi ng bawat numerong iyon 396 00:17:41,780 --> 00:17:46,065 tumuturo sa ilang mga susunod na numero, na tumuturo, siya namang, ang ilang mga susunod na numero? 397 00:17:46,065 --> 00:17:47,940 Kaya sa ibang salita, kung ano ang kung gusto naming aktwal 398 00:17:47,940 --> 00:17:49,820 upang ipatupad ang isang bagay tulad na ito? 399 00:17:49,820 --> 00:17:53,610 Well sa kasamaang-palad, ang mga ito ng mga parihaba, hindi bababa sa isa sa 9, 17, 22, 400 00:17:53,610 --> 00:17:57,040 at iba pa, ang mga ito ay hindi na Ang ganda ng mga parisukat na may iisang numero. 401 00:17:57,040 --> 00:17:59,960 Ang ibaba, parihaba 9 sa ibaba, halimbawa, 402 00:17:59,960 --> 00:18:04,330 kumakatawan sa kung ano ang dapat maging isang pointer, 32 bits. 403 00:18:04,330 --> 00:18:09,460 Ngayon, hindi ako pa kamalayan sa anumang uri ng data sa C na nagbibigay sa iyo ng hindi lamang sa isang int 404 00:18:09,460 --> 00:18:11,630 ngunit isang pointer nang sama-sama. 405 00:18:11,630 --> 00:18:15,020 >> Kaya ano ang solusyon kung gusto namin upang imbentuhin ating sariling sagot sa ito? 406 00:18:15,020 --> 00:18:15,760 Oo? 407 00:18:15,760 --> 00:18:16,640 >> Madla: [INAUDIBLE] 408 00:18:16,640 --> 00:18:17,360 >> David J. MALAN: Ano iyon? 409 00:18:17,360 --> 00:18:17,880 >> Madla: Bagong istraktura. 410 00:18:17,880 --> 00:18:19,590 >> David J. MALAN: Oo, kaya bakit huwag kaming lumikha ng bagong istraktura, 411 00:18:19,590 --> 00:18:20,920 o sa C, ang isang struct? 412 00:18:20,920 --> 00:18:25,990 Nakakita kami structs bago, kung panandalian, kung saan kami Aaksyunan isang mag-aaral ng istraktura 413 00:18:25,990 --> 00:18:27,780 tulad nito, sino ay nagkaroon ng isang pangalan at isang bahay. 414 00:18:27,780 --> 00:18:31,980 Sa Pset 3 breakout na ginamit mo sa kabuuan bungkos ng structs-- GRect at GOvals 415 00:18:31,980 --> 00:18:34,810 Stanford na nilikha sa cluster impormasyon nang magkakasama. 416 00:18:34,810 --> 00:18:38,580 Kaya kung ano kung gagawin namin ito parehong ideya ng ang mga keyword na "typedef" at "struct," 417 00:18:38,580 --> 00:18:42,890 at pagkatapos ay ang ilang mga bagay-bagay mag-aaral na tukoy, at magbabago ito sa mga sumusunod: 418 00:18:42,890 --> 00:18:46,210 typedef struct node-- at node ay lamang ng isang napaka generic computer science 419 00:18:46,210 --> 00:18:49,980 termino para sa isang bagay sa isang istraktura ng data, isang lalagyan sa isang istraktura ng data. 420 00:18:49,980 --> 00:18:53,900 Ang isang node inaangkin ko ay pagpunta sa may isang int n, ganap prangka, 421 00:18:53,900 --> 00:18:58,810 at pagkatapos ng kaunti pa cryptically, ito pangalawang linya, struct node * susunod. 422 00:18:58,810 --> 00:19:01,300 Ngunit sa mas teknikal na mga termino, ano ay ang pangalawang linya 423 00:19:01,300 --> 00:19:02,980 ng code sa loob ng kulot braces? 424 00:19:02,980 --> 00:19:03,737 Oo? 425 00:19:03,737 --> 00:19:04,851 >> Madla: [INAUDIBLE] 426 00:19:04,851 --> 00:19:06,600 David J. MALAN: Isang pointer sa isa pang node. 427 00:19:06,600 --> 00:19:09,910 Kaya admittedly, syntax ng kaunti cryptic. 428 00:19:09,910 --> 00:19:13,250 Ngunit kung ito na basahin mo literal, susunod ay ang pangalan ng isang variable. 429 00:19:13,250 --> 00:19:14,410 Ano ang uri nito data? 430 00:19:14,410 --> 00:19:18,206 Ito ay isang maliit na verbose oras na ito, subalit ito ay uri ng struct node *. 431 00:19:18,206 --> 00:19:22,960 Anumang oras na nakakita kami ng isang bagay na bituin, na Ang ibig sabihin ito ay isang pointer sa na uri ng data. 432 00:19:22,960 --> 00:19:26,810 Kaya susunod ay tila isang pointer sa isang struct node. 433 00:19:26,810 --> 00:19:28,310 >> Ngayon, kung ano ay isang struct node? 434 00:19:28,310 --> 00:19:31,044 Well, napansin makita mo ang mga parehong salita sa kanang itaas. 435 00:19:31,044 --> 00:19:33,960 At sa katunayan, mo ring makita ang mga salita "Node" down na dito sa kaliwang ibaba. 436 00:19:33,960 --> 00:19:35,640 At ito ay tunay na isang kaginhawahan lamang. 437 00:19:35,640 --> 00:19:39,930 Pansinin na sa aming kahulugan ng mag-aaral may mga salitang "mag-aaral" isang beses lamang. 438 00:19:39,930 --> 00:19:42,510 At iyon ay dahil sa isang mag-aaral object ay hindi self-referential. 439 00:19:42,510 --> 00:19:45,340 Wala sa loob ng isang mag-aaral ay na kailangan upang tumuro sa isa pang mag-aaral, 440 00:19:45,340 --> 00:19:45,610 persay. 441 00:19:45,610 --> 00:19:47,630 Iyon ay magiging isang uri ng kakaiba sa tunay na mundo. 442 00:19:47,630 --> 00:19:50,880 >> Ngunit sa isang node sa isang naka-link listahan, binabasa namin gusto ang isang node 443 00:19:50,880 --> 00:19:53,970 upang maging referential sa isang katulad na bagay. 444 00:19:53,970 --> 00:19:57,900 At kaya mapapansin ang pagbabago dito ay hindi kung ano lamang ang nasa loob ng mga kulot braces. 445 00:19:57,900 --> 00:20:00,800 Subalit idagdag namin ang salitang "node" sa pati na rin ang tuktok 446 00:20:00,800 --> 00:20:02,930 pagdaragdag nito sa ibaba sa halip ng "mag-aaral." 447 00:20:02,930 --> 00:20:06,000 At ito ay lamang ng isang teknikal na detalye kaya iyon, muli, ang iyong mga istraktura ng data 448 00:20:06,000 --> 00:20:11,380 ay maaaring maging self-referential, kaya na ang isang na node ay maaaring tumuro sa isa pang katulad na node. 449 00:20:11,380 --> 00:20:13,840 >> Kaya kung ano ito sa huli pagpunta sa ibig sabihin para sa amin? 450 00:20:13,840 --> 00:20:17,560 Well, isa, mga bagay na ito sa loob ng ay ang mga nilalaman ng aming mga node. 451 00:20:17,560 --> 00:20:19,360 Bagay na ito ng hanggang dito, kanang tuktok, sa gayon ay lamang 452 00:20:19,360 --> 00:20:20,860 na iyon, muli, maaari naming sumangguni sa ating sarili. 453 00:20:20,860 --> 00:20:23,401 At pagkatapos ay ang outermost bagay-bagay, kahit na node ay isang bagong term, 454 00:20:23,401 --> 00:20:25,500 marahil, ito ay pa rin ang katulad ng mag-aaral at kung ano ang 455 00:20:25,500 --> 00:20:27,520 ay sa ilalim ng hood sa SPL. 456 00:20:27,520 --> 00:20:31,095 >> Kaya kung gusto naming ngayon upang simulan pagpapatupad na ito na naka-link listahan, 457 00:20:31,095 --> 00:20:33,220 paano maaari naming isalin isang bagay na tulad nito sa code? 458 00:20:33,220 --> 00:20:35,350 Well, sabihin makita ni lamang ng isang halimbawa ng isang programa na 459 00:20:35,350 --> 00:20:36,840 talaga ay gumagamit ng isang naka-link na listahan. 460 00:20:36,840 --> 00:20:40,870 Kabilang sa pamamahagi code ngayong araw ay isang programa na tinatawag na Listahan Zero. 461 00:20:40,870 --> 00:20:44,980 At kung nagpatakbo ako ng ito nilikha ko ang isang napakabilis simpleng GUI, Graphical User Interface, 462 00:20:44,980 --> 00:20:46,460 ngunit ito ay talagang lamang printf. 463 00:20:46,460 --> 00:20:50,930 At ngayon Ibinigay ko sa sarili ko ng ilang menu options-- Tanggalin, Insert, Paghahanap, 464 00:20:50,930 --> 00:20:51,750 at Traverse. 465 00:20:51,750 --> 00:20:52,630 At quit. 466 00:20:52,630 --> 00:20:55,970 Ang mga ito ay karaniwang lamang pagpapatakbo sa isang istraktura ng data na kilala bilang isang listahan ng link. 467 00:20:55,970 --> 00:20:58,409 >> Ngayon, Tanggalin ang pagpunta sa tanggalin ang isang numero mula sa listahan. 468 00:20:58,409 --> 00:21:00,200 Ipasok ang nangyayari upang magdagdag ng isang numero sa listahan. 469 00:21:00,200 --> 00:21:02,181 Paghahanap ay pagpunta sa tumingin para sa numero sa listahan. 470 00:21:02,181 --> 00:21:04,930 At traverse lamang magarbong paraan ng sinasabi, maglakad sa pamamagitan ng mga listahan, 471 00:21:04,930 --> 00:21:06,245 i-print ito, ngunit iyan ay ito. 472 00:21:06,245 --> 00:21:07,720 Huwag baguhin ito sa anumang paraan. 473 00:21:07,720 --> 00:21:08,570 >> Kaya sabihin subukan ito. 474 00:21:08,570 --> 00:21:10,160 Sabihin sige at i-type 2. 475 00:21:10,160 --> 00:21:12,710 At pagkatapos ay pupuntahan ko ipasok ang numero ng, sabihin nating 9. 476 00:21:12,710 --> 00:21:13,620 Ipasok. 477 00:21:13,620 --> 00:21:17,480 At ngayon ang aking programa lamang -program upang sabihin, listahan 9 na ngayon. 478 00:21:17,480 --> 00:21:20,190 Ngayon, kung pumunta ako magpatuloy at huwag Ipasok ang muli, sabihin 479 00:21:20,190 --> 00:21:23,680 sa akin sige at mag-zoom out at i-type sa 17. 480 00:21:23,680 --> 00:21:25,770 Ngayon aking listahan ay 9, pagkatapos ay 17. 481 00:21:25,770 --> 00:21:27,750 Kung gagawin ko ipasok muli, ay laktawan ang isa ipaalam. 482 00:21:27,750 --> 00:21:32,400 Sa halip na 22, bilang bawat ang larawan hindi namin hinahanap-hanap sa dito, hayaan mo akong tumalon nang mas maaga 483 00:21:32,400 --> 00:21:34,630 at magpasok ng 26 susunod. 484 00:21:34,630 --> 00:21:36,230 Kaya pupuntahan ko type 26. 485 00:21:36,230 --> 00:21:37,755 Ang listahan ay tulad ng iyong inaasahan ko. 486 00:21:37,755 --> 00:21:40,630 Ngunit ngayon, upang makita lamang kung ang code na ito ay magiging may kakayahang umangkop, ipaalam sa akin ngayon 487 00:21:40,630 --> 00:21:43,520 uri 22, na hindi bababa sa conceptually, kung hindi kami 488 00:21:43,520 --> 00:21:46,520 ito pinagsunod-sunod pagpapanatiling, na kung saan ay sa katunayan pagpunta sa maging sa ngayon isa pang layunin, 489 00:21:46,520 --> 00:21:48,690 dapat pumunta sa pagitan ng 17 at 26. 490 00:21:48,690 --> 00:21:50,270 Kaya hit ko ang Enter. 491 00:21:50,270 --> 00:21:51,380 Sa katunayan, na gumagana. 492 00:21:51,380 --> 00:21:54,950 At kaya ngayon hayaan mo akong ipasok ang huling, alinsunod sa mga larawang ito, 34. 493 00:21:54,950 --> 00:21:55,450 >> Lahat ng karapatan. 494 00:21:55,450 --> 00:21:58,980 Kaya para sa ngayon hayaan mo akong stipulate na Tanggalin at Traverse at Paghahanap gawin, 495 00:21:58,980 --> 00:21:59,760 sa katunayan, gumana. 496 00:21:59,760 --> 00:22:04,180 Sa katunayan, kung ako magpatakbo ng Paghahanap, sabihin maghanap para sa numerong 22, ang Enter. 497 00:22:04,180 --> 00:22:05,010 Nag nahanap 22. 498 00:22:05,010 --> 00:22:07,580 Kaya iyon ay kung ano ito Listahan ng programa Zero ang gumagana. 499 00:22:07,580 --> 00:22:10,230 >> Ngunit kung ano ang aktwal na pagpunta sa na ipinapatupad ito? 500 00:22:10,230 --> 00:22:14,530 Well, una maaaring mayroon ako, at sa katunayan Akong, isang file na tinatawag list0.h. 501 00:22:14,530 --> 00:22:16,540 502 00:22:16,540 --> 00:22:20,690 At sa isang lugar sa may ito linya, typedef, struct node, 503 00:22:20,690 --> 00:22:24,850 pagkatapos ay mayroon ko ang aking kulot braces, int n, at pagkatapos struct-- kung ano ang naging kahulugan? 504 00:22:24,850 --> 00:22:26,530 505 00:22:26,530 --> 00:22:28,545 Struct node susunod. 506 00:22:28,545 --> 00:22:29,920 507 00:22:29,920 --> 00:22:31,045 Kaya kailangan namin ng mga bituin. 508 00:22:31,045 --> 00:22:33,420 Ngayon technically makuha namin sa ang ugali ng pagguhit ng ito dito. 509 00:22:33,420 --> 00:22:35,670 Maaari kang makakita ng mga aklat-aralin at online na mga sanggunian ito gagawin doon. 510 00:22:35,670 --> 00:22:36,660 Ito ay katumbas sa pagtakbo. 511 00:22:36,660 --> 00:22:37,980 Sa katunayan, ito ay isang kaunti pa tipikal. 512 00:22:37,980 --> 00:22:40,563 Ngunit kukunin ko na maging pare-pareho sa kung ano ginawa namin huling beses at gawin ito. 513 00:22:40,563 --> 00:22:42,350 At pagkatapos Panghuli, Pupunta ako upang gawin ito. 514 00:22:42,350 --> 00:22:45,550 >> Kaya sa isang header na file sa isang lugar, sa list0.h 515 00:22:45,550 --> 00:22:49,200 ngayon ay kahulugan struct na ito, at marahil ilang iba pang mga bagay-bagay. 516 00:22:49,200 --> 00:22:52,580 Samantala sa list0c mayroong pagpunta sa maging ang ilang mga bagay. 517 00:22:52,580 --> 00:22:54,740 Ngunit kami ay pagpunta sa makatarungan simulan at tapusin hindi na ito. 518 00:22:54,740 --> 00:22:59,690 List0.h ay isang file na gusto ko isama sa aking C file. 519 00:22:59,690 --> 00:23:03,910 At pagkatapos ay sa isang punto ako pagpunta sa mayroon int, pangunahing, walang bisa. 520 00:23:03,910 --> 00:23:06,530 At pagkatapos ay pupuntahan ko kumuha ng gagawin meron dito. 521 00:23:06,530 --> 00:23:10,620 Pupunta ako din upang magkaroon ng isang prototype, tulad ng walang silbi, paghahanap, int, 522 00:23:10,620 --> 00:23:13,610 n, na ang layunin sa buhay ay upang maghanap para sa isang elemento. 523 00:23:13,610 --> 00:23:18,310 At pagkatapos ay down na dito i-claim in ako code ngayon, walang bisa, paghahanap, int, n, 524 00:23:18,310 --> 00:23:21,020 walang semicolon ngunit bukas kulot braces. 525 00:23:21,020 --> 00:23:25,049 At ngayon nais ko upang kahit papaano maghanap para sa isang elemento sa listahang ito. 526 00:23:25,049 --> 00:23:27,340 Ngunit wala kaming sapat impormasyon sa screen pa. 527 00:23:27,340 --> 00:23:29,800 Mayroon akong hindi talaga kinakatawan ang listahan mismo. 528 00:23:29,800 --> 00:23:33,070 Kaya isang paraan na maaari kaming ipatupad naka-link na listahan sa isang programa 529 00:23:33,070 --> 00:23:37,520 ay uri ng ko nais upang gawin ang isang bagay tulad ng ipinahahayag listahan na naka-link dito. 530 00:23:37,520 --> 00:23:40,520 Para sa pagiging simple, ako ako pagpunta sa gawin ito global, kahit na sa pangkalahatan namin 531 00:23:40,520 --> 00:23:41,645 Hindi dapat gawin ito ng masyadong maraming. 532 00:23:41,645 --> 00:23:43,260 Ngunit ito padaliin ang halimbawang ito. 533 00:23:43,260 --> 00:23:45,890 Kaya gusto ko na idedeklara isang naka-link dito listahan up. 534 00:23:45,890 --> 00:23:47,010 Ngayon, kung paano maaaring gawin ko na? 535 00:23:47,010 --> 00:23:48,810 536 00:23:48,810 --> 00:23:50,750 >> Narito ang litrato ng isang naka-link na listahan. 537 00:23:50,750 --> 00:23:53,030 At gagawin ko hindi talaga alam sa sandaling ito kung paano 538 00:23:53,030 --> 00:23:56,710 Pupunta ako sa pumunta tungkol kumakatawan sa kaya maraming bagay na may isa lamang 539 00:23:56,710 --> 00:23:58,040 variable sa memorya. 540 00:23:58,040 --> 00:23:59,160 Ngunit sa tingin pabalik ng ilang sandali. 541 00:23:59,160 --> 00:24:00,830 Lahat ng oras na ito mayroon kaming mga string, na kung saan namin pagkatapos ay 542 00:24:00,830 --> 00:24:02,913 mailalahad sa maging array ng character, na kung saan namin pagkatapos ay 543 00:24:02,913 --> 00:24:05,740 mailalahad sa maging lamang isang pointer sa unang character 544 00:24:05,740 --> 00:24:08,890 sa isang array ng mga character na null winakasan. 545 00:24:08,890 --> 00:24:13,530 Kaya sa pamamagitan ng na logic, at may ito larawan uri ng seeding ang iyong mga pananaw, 546 00:24:13,530 --> 00:24:17,964 kung ano ang nangangailangan ng aktwal na namin isulat sa aming code sa kumakatawan sa isang naka-link na listahan? 547 00:24:17,964 --> 00:24:21,130 Magkano ng impormasyon na ito ang kailangan namin upang makuha sa C code, nais mong sabihin? 548 00:24:21,130 --> 00:24:22,654 549 00:24:22,654 --> 00:24:23,154 Oo? 550 00:24:23,154 --> 00:24:24,738 >> Madla: Kailangan namin ng isang pointer sa isang node. 551 00:24:24,738 --> 00:24:26,237 David J. MALAN: Ang isang pointer sa isang node. 552 00:24:26,237 --> 00:24:29,320 Sa partikular, na node ng ginagawa ng iyong instincts maging upang mapanatili ang isang pointer sa? 553 00:24:29,320 --> 00:24:30,026 >> Madla: Ang unang node. 554 00:24:30,026 --> 00:24:31,942 >> David J. MALAN: Oo, marahil lang ang unang. 555 00:24:31,942 --> 00:24:34,030 At napansin, ang unang na node ay isang iba't ibang mga hugis. 556 00:24:34,030 --> 00:24:37,690 Ito ay lamang sa kalahati ng laki ng struct, dahil ito ay sa katunayan lamang ng isang pointer. 557 00:24:37,690 --> 00:24:44,650 Kaya ano ang maaari mong gawin sa katunayan ay ipinahahayag naka-link na listahan upang maging ng uri ng node *. 558 00:24:44,650 --> 00:24:47,780 At tumawag lamang ni muna itong ipaalam at initialize ito sa null. 559 00:24:47,780 --> 00:24:49,910 Kaya null, muli, ay darating sa larawan dito. 560 00:24:49,910 --> 00:24:53,620 Hindi lamang ay null ginagamit bilang tulad ng isang espesyal na return halaga para sa mga bagay tulad ng getstring 561 00:24:53,620 --> 00:24:57,770 at malloc, null rin ang zero pointer, ang kakulangan ng isang pointer, 562 00:24:57,770 --> 00:24:58,430 kung gagawin mo. 563 00:24:58,430 --> 00:25:00,309 Ito lamang ay nangangahulugan na walang ay pa dito. 564 00:25:00,309 --> 00:25:02,100 Ngayon unang, kaya kong nai na tinatawag na ito ng kahit ano. 565 00:25:02,100 --> 00:25:04,200 Sana tinatawag ko ito "listahan" o anumang bilang ng iba pang mga bagay. 566 00:25:04,200 --> 00:25:06,960 Ngunit ako pagtawag ito "unang" upang ito linya up gamit ang larawang ito. 567 00:25:06,960 --> 00:25:10,280 Kaya tulad ng isang string maaaring katawanin may address ng kanyang unang byte, 568 00:25:10,280 --> 00:25:11,280 kaya maaari isang naka-link na listahan. 569 00:25:11,280 --> 00:25:13,480 At kami makita ang iba pang data kaayusan katawanin 570 00:25:13,480 --> 00:25:16,700 sa pamamagitan lamang ng isang pointer, 32-bit na arrow, na nakaturo 571 00:25:16,700 --> 00:25:18,740 sa pinakadulo unang node sa istraktura. 572 00:25:18,740 --> 00:25:20,340 >> Ngunit inaasahan problema ngayon hayaan. 573 00:25:20,340 --> 00:25:23,230 Kung lamang ako pagtanda sa aking mga programa sa address 574 00:25:23,230 --> 00:25:27,220 ng unang node, ang unang Parihaba sa istraktura ng data, 575 00:25:27,220 --> 00:25:31,760 kung ano ay nagkaroon ng mas mahusay na ang kaso tungkol sa pagpapatupad ng natitira sa aking mga listahan? 576 00:25:31,760 --> 00:25:35,820 Ano ang isang mahalagang detalye na nangyayari upang matiyak na ito talaga gumagana? 577 00:25:35,820 --> 00:25:39,250 At sa pamamagitan ng "talagang gumagana" ko ibig sabihin, halos tulad ng isang string, 578 00:25:39,250 --> 00:25:42,180 hinahayaan pumunta sa amin mula sa unang character sa pangalan Davin sa pangalawa, 579 00:25:42,180 --> 00:25:44,755 ang ikatlong, upang ang pang-apat, sa dulo napaka, 580 00:25:44,755 --> 00:25:47,880 paano ko malalaman namin kapag hindi namin sa dulo ng isang naka-link na listahan na ganito ang hitsura? 581 00:25:47,880 --> 00:25:50,035 582 00:25:50,035 --> 00:25:50,660 Kapag ito ay walang bisa. 583 00:25:50,660 --> 00:25:53,640 At ako kinakatawan na ang ganitong uri ng bilang tulad ng isang de-koryenteng inhinyero ay maaaring, 584 00:25:53,640 --> 00:25:56,420 may maliit na grounding simbolo, ng mga klase. 585 00:25:56,420 --> 00:25:58,246 Ngunit iyon lamang ay nangangahulugan na walang bisa sa kasong ito. 586 00:25:58,246 --> 00:26:00,370 Maaari mong iguhit ito sa anumang numero ng ng paraan, ngunit may-akdang ito 587 00:26:00,370 --> 00:26:02,800 Nangyari na gamitin ang simbolong ito dito. 588 00:26:02,800 --> 00:26:06,260 >> Kaya hangga't kami ay stringing lahat ng mga nodes magkasama, 589 00:26:06,260 --> 00:26:08,600 pag-alala lamang kung saan ang unang isa ay, sa gayon ang haba 590 00:26:08,600 --> 00:26:11,760 bilang inilalagay namin ang isang espesyal na simbolo sa pinakadulo huling node sa listahan, 591 00:26:11,760 --> 00:26:15,130 at gagamitin namin ang null, dahil iyon ang kung ano ang mayroon kaming magagamit sa amin, 592 00:26:15,130 --> 00:26:16,480 listahan na ito ay kumpleto na. 593 00:26:16,480 --> 00:26:20,190 At kahit na lamang ako magbibigay sa iyo ng isang pointer sa sa unang elemento, ikaw, ang programmer, 594 00:26:20,190 --> 00:26:22,486 Maaari tiyak access ang iba sa mga ito. 595 00:26:22,486 --> 00:26:24,360 Ngunit sabihin ang iyong isip ipaalam maglibot Medyo, 596 00:26:24,360 --> 00:26:26,140 kung sila ay hindi na medyo wandered-- kung ano ang 597 00:26:26,140 --> 00:26:28,723 pagpunta sa maging ang oras ng paggana ng paghahanap ng anumang bagay sa listahang ito? 598 00:26:28,723 --> 00:26:30,450 599 00:26:30,450 --> 00:26:33,470 Damn ito, ito ay malaki O ng n, na kung saan ay hindi masama, sa pagiging makatarungan. 600 00:26:33,470 --> 00:26:34,800 Ngunit ito ay linear. 601 00:26:34,800 --> 00:26:37,980 Nagbigay kami ng hanggang sa kung ano ang tampok ng array sa pamamagitan ng paggalaw nang higit pa 602 00:26:37,980 --> 00:26:43,130 patungo ang larawang ito ng pabagu-bagong pinagtagpi-sama o naka-link node? 603 00:26:43,130 --> 00:26:44,970 604 00:26:44,970 --> 00:26:46,687 Binigyan namin ang hanggang random na pag-access. 605 00:26:46,687 --> 00:26:48,770 Ang isang array ay maganda dahil mathematically ang lahat ng bagay 606 00:26:48,770 --> 00:26:50,340 ay bumalik upang i-back upang i-back sa likod. 607 00:26:50,340 --> 00:26:52,370 Kahit na ang larawang ito mukhang maganda, at kahit na 608 00:26:52,370 --> 00:26:55,830 bagaman mukhang mga node ay may pagitan ng mabuti ang pagitan, sa katotohanan 609 00:26:55,830 --> 00:26:56,830 maaari silang maging kahit saan. 610 00:26:56,830 --> 00:27:01,590 Ox1, Ox50, Ox123, Ox99, ang mga nodes ay maaaring maging kahit saan. 611 00:27:01,590 --> 00:27:05,960 Dahil malloc ang maglaan ng memorya mula sa heap, ngunit saanman sa heap. 612 00:27:05,960 --> 00:27:09,080 Ikaw ay hindi kinakailangang malaman na ito pagpunta sa na bumalik upang i-back sa likod. 613 00:27:09,080 --> 00:27:12,460 At gayon ang larawang ito sa katotohanan ni hindi pagpunta sa lubos na itong maganda. 614 00:27:12,460 --> 00:27:16,140 >> Kaya ito ay pagpunta sa tumagal ng kaunting gumagana upang ipatupad ang pag-andar. 615 00:27:16,140 --> 00:27:17,880 Kaya ipatupad sa paghahanap ngayon hayaan. 616 00:27:17,880 --> 00:27:20,250 At kami makita ang uri ng isang matalino na paraan ng paggawa nito. 617 00:27:20,250 --> 00:27:24,660 Kaya kung ako ay isang function ng paghahanap at Ako bibigyan ng variable, integer n 618 00:27:24,660 --> 00:27:28,490 upang tumingin para sa, kailangan kong malaman ang bagong syntax para sa naghahanap sa loob 619 00:27:28,490 --> 00:27:32,400 ng istruktura na itinuturo sa, upang makahanap ng n. 620 00:27:32,400 --> 00:27:33,210 Kaya sabihin gawin ito. 621 00:27:33,210 --> 00:27:36,030 >> Kaya unang pupuntahan ko pumunta Magpatuloy at ipinahahayag ang isang node *. 622 00:27:36,030 --> 00:27:39,400 At ako pagpunta sa tumawag ito pointer, sa pamamagitan lamang ng convention. 623 00:27:39,400 --> 00:27:41,710 At ako pagpunta sa initialize ito sa unang. 624 00:27:41,710 --> 00:27:43,770 At ngayon maaari kong gawin ito sa isang bilang ng mga paraan. 625 00:27:43,770 --> 00:27:45,436 Ngunit Pupunta ako sa tumagal ng isang karaniwang diskarte. 626 00:27:45,436 --> 00:27:50,180 Habang pointer ay hindi kapantay sa null, at iyon ang wastong syntax. 627 00:27:50,180 --> 00:27:54,550 At ito ay nangangahulugan lamang gawin ang mga sumusunod, kaya Hangga't hindi ka na tumuturo sa wala. 628 00:27:54,550 --> 00:27:55,800 Ano ang gusto kong gawin? 629 00:27:55,800 --> 00:28:01,939 >> Kung pointer tuldok n, hayaan mo akong bumalik upang iyon, equals-- ay katumbas ng kung ano? 630 00:28:01,939 --> 00:28:03,105 Ano ang halaga ng aking hinahanap? 631 00:28:03,105 --> 00:28:04,920 632 00:28:04,920 --> 00:28:06,590 Ang aktwal n na ipinasa sa. 633 00:28:06,590 --> 00:28:09,020 Kaya narito ang isa pang tampok ng C at maraming wika. 634 00:28:09,020 --> 00:28:13,705 Kahit na ang istraktura na tinatawag na node May halaga n, ganap lehitimong 635 00:28:13,705 --> 00:28:17,530 upang magkaroon din ng isang lokal na argumento o variable na tinatawag na n. 636 00:28:17,530 --> 00:28:20,085 Dahil kahit na namin, na pantao mga mata, maaari makilala 637 00:28:20,085 --> 00:28:22,087 na ito ay n baka iba mula sa n ito. 638 00:28:22,087 --> 00:28:23,420 Dahil ang syntax ay iba. 639 00:28:23,420 --> 00:28:26,211 Nakakuha ka ng isang tuldok at isang pointer, samantalang ang isang ito ay walang mga naturang bagay. 640 00:28:26,211 --> 00:28:27,290 Kaya ito ay OK. 641 00:28:27,290 --> 00:28:29,120 Iyon ang OK upang tawagan ang mga ito ng parehong mga bagay. 642 00:28:29,120 --> 00:28:32,380 >> Kung ko mahanap ito, ako pagpunta sa nais na gawin ang isang bagay 643 00:28:32,380 --> 00:28:35,000 tulad ng ipahayag na natagpuan namin n. 644 00:28:35,000 --> 00:28:37,930 At pababayaan namin na nakalabas na bilang isang magkomento o pseudocode code. 645 00:28:37,930 --> 00:28:40,190 Iba Pa, at narito ang kagiliw-giliw na bahagi, kung ano ang 646 00:28:40,190 --> 00:28:47,320 ang gusto kong gawin kung ang kasalukuyang node ay hindi naglalaman ng n na akong pakialam tungkol sa? 647 00:28:47,320 --> 00:28:50,700 Paano ko makamit ang sumusunod? 648 00:28:50,700 --> 00:28:53,710 Kung ang aking daliri sa sandali ay PTR, at ito ay 649 00:28:53,710 --> 00:28:55,920 na tumuturo sa kahit anong unang nakaturo sa, 650 00:28:55,920 --> 00:28:59,290 paano ko ililipat ang aking daliri sa susunod na node sa code? 651 00:28:59,290 --> 00:29:01,915 Well, ano ang breadcrumb kami pagpunta sa sundin sa kasong ito? 652 00:29:01,915 --> 00:29:03,464 653 00:29:03,464 --> 00:29:04,380 Madla: [INAUDIBLE]. 654 00:29:04,380 --> 00:29:05,630 David J. MALAN: Oo, kaya susunod. 655 00:29:05,630 --> 00:29:06,640 656 00:29:06,640 --> 00:29:09,824 Kaya kung pumunta ako pabalik sa aking code dito, sa katunayan, ako 657 00:29:09,824 --> 00:29:12,990 pagpunta sa sige at sabihin ang pointer, na ay isa lamang pansamantalang variable-- ito 658 00:29:12,990 --> 00:29:15,320 isang kakatwang mga pangalan, ptr, ngunit ito ay katulad lamang ng temp-- 659 00:29:15,320 --> 00:29:19,234 Pupunta ako upang i-set pointer katumbas ng kahit anong pointer is-- 660 00:29:19,234 --> 00:29:22,150 at muli, ito ay magiging isang maliit na mayroong bug para sa isang moment-- tuldok sa tabi. 661 00:29:22,150 --> 00:29:23,551 662 00:29:23,551 --> 00:29:26,550 Sa ibang salita, ako ako pagpunta sa tumagal ng aking daliri na tumuturo sa node na ito 663 00:29:26,550 --> 00:29:31,247 dito at pupuntahan ko sabihin, alam mo na ano, tingnan ang susunod na field 664 00:29:31,247 --> 00:29:33,330 at ilipat ang iyong daliri upang kahit anong ito ay tumuturo sa. 665 00:29:33,330 --> 00:29:35,163 At ito ay pagpunta sa ulitin, ulitin, ulitin. 666 00:29:35,163 --> 00:29:37,630 Ngunit kapag ang aking daliri itigil ang paggawa ng anumang bagay sa lahat? 667 00:29:37,630 --> 00:29:40,095 Sa lalong madaling kung ano ang linya ng code kicks in? 668 00:29:40,095 --> 00:29:40,970 Madla: [INAUDIBLE] 669 00:29:40,970 --> 00:29:43,060 David J. MALAN: Kung punto habang pointer ay hindi kapantay sa null. 670 00:29:43,060 --> 00:29:44,900 Sa ilang mga punto ang aking daliri ni pagpunta sa ay tumuturo sa null 671 00:29:44,900 --> 00:29:47,070 at pupuntahan ko maisip iyon ang katapusan ng listahang ito. 672 00:29:47,070 --> 00:29:48,910 Ngayon, ito ay isang maliit na puting kasinungalingan para sa pagiging simple. 673 00:29:48,910 --> 00:29:51,580 Ito ay lumiliko out na kahit na namin natutunan lamang ito tuldok pagtatanda 674 00:29:51,580 --> 00:29:55,220 para sa mga istraktura, pointer ay hindi isang struct. 675 00:29:55,220 --> 00:29:56,580 ptr ay kung ano? 676 00:29:56,580 --> 00:29:58,350 Lamang na maging mas nitpicky. 677 00:29:58,350 --> 00:29:59,720 678 00:29:59,720 --> 00:30:01,360 Ito ay isang pointer sa isang node. 679 00:30:01,360 --> 00:30:03,120 Ito ay hindi isang node mismo. 680 00:30:03,120 --> 00:30:06,650 Kung mayroon akong mga star dito, pointer absolutely-- ito ay isang node. 681 00:30:06,650 --> 00:30:08,650 Ito ay tulad ng isang linggo deklarasyon ng isang variable, 682 00:30:08,650 --> 00:30:10,120 kahit na ang salitang "node" ay bagong. 683 00:30:10,120 --> 00:30:13,860 >> Ngunit sa lalong madaling ipakilala kami ng isang bituin, ito ay isang pointer sa isang node ngayon. 684 00:30:13,860 --> 00:30:17,960 At sa kasamaang palad, hindi mo maaaring gamitin ang tuldok pagtatanda para sa isang pointer. 685 00:30:17,960 --> 00:30:21,070 Kailangan mong gamitin ang mga arrow pagtatanda, na kung saan, strikingly, 686 00:30:21,070 --> 00:30:23,470 ang unang pagkakataon na ang anumang mga piraso ng syntax mukhang madaling maunawaan. 687 00:30:23,470 --> 00:30:25,245 Ito literal mukhang isang arrow. 688 00:30:25,245 --> 00:30:26,370 At nang sa gayon ay isang magandang bagay. 689 00:30:26,370 --> 00:30:28,995 At pababa dito literal mukhang isang arrow. 690 00:30:28,995 --> 00:30:31,870 Kaya sa tingin ko na ang la-- gagawin ko hindi Sa tingin ko over-paggawa ng here-- ko 691 00:30:31,870 --> 00:30:34,120 Sa tingin iyon ang huling bagong piraso ng syntax kami ng pagpunta upang makita. 692 00:30:34,120 --> 00:30:36,500 At thankfully, ito ay sa katunayan mas madaling maunawaan ng kaunti. 693 00:30:36,500 --> 00:30:40,090 >> Ngayon, para sa mga ng sa iyo kung sino baka mas gusto ang lumang paraan, 694 00:30:40,090 --> 00:30:42,550 maaari mo pa ring gamitin ang pagtatanda na tuldok. 695 00:30:42,550 --> 00:30:45,380 Ngunit bilang bawat Lunes ni pakikipag-usap, muna namin 696 00:30:45,380 --> 00:30:50,530 kailangan upang pumunta doon, pumunta sa na tugunan, at pagkatapos ay i-access ang field. 697 00:30:50,530 --> 00:30:51,897 Kaya ito ay tama rin. 698 00:30:51,897 --> 00:30:53,730 At tapat, ito ay isang kaunti pa pedantic. 699 00:30:53,730 --> 00:30:56,530 Literal na iyong sinasabi, dereference ang pointer at pumunta doon. 700 00:30:56,530 --> 00:30:59,320 Pagkatapos grab .n, ang patlang na tinatawag n. 701 00:30:59,320 --> 00:31:01,370 Ngunit tapat, walang sinuman ang nais ni i-type o basahin ito. 702 00:31:01,370 --> 00:31:03,620 At kaya mundo imbento ang arrow pagtatanda, na 703 00:31:03,620 --> 00:31:06,980 ay katumbas, magkakahawig, ito lamang ay syntactic asukal. 704 00:31:06,980 --> 00:31:10,570 Kaya isang magarbong paraan ng pagsabi na ito mas mahusay ang hitsura, o mukhang mas simple. 705 00:31:10,570 --> 00:31:12,296 >> Kaya ngayon ako pagpunta sa gawin ang isa sa iba pang mga bagay. 706 00:31:12,296 --> 00:31:15,420 Pupunta ako sa sabihin ang "break" sa sandaling hindi ko Napag-alaman na kaya hindi ko panatilihin ang naghahanap para dito. 707 00:31:15,420 --> 00:31:17,620 Ngunit ito ay ang gist ng isang function ng paghahanap. 708 00:31:17,620 --> 00:31:21,710 Ngunit ito ay isang mas madaling, sa dulo, hindi upang maglakad sa pamamagitan ng code. 709 00:31:21,710 --> 00:31:25,570 Ito ay sa katunayan ang pormal na pagpapatupad ng paghahanap sa pamamahagi ng code sa araw na ito. 710 00:31:25,570 --> 00:31:30,530 Dare ko sabihin na insert ay hindi lalo na masaya upang maglakad sa pamamagitan ng 711 00:31:30,530 --> 00:31:33,180 biswal, at hindi rin tanggalin, kahit na bagaman sa pagtatapos ng araw 712 00:31:33,180 --> 00:31:35,460 pigsa sila pababa sa medyo simple heuristics. 713 00:31:35,460 --> 00:31:36,330 >> Kaya sabihin gawin ito. 714 00:31:36,330 --> 00:31:39,250 Kung ikaw katatawanan sa akin dito, ginawa ko magdala ng grupo ng mga bola ng stress. 715 00:31:39,250 --> 00:31:40,620 Dinala ako ng isang bungkos ng mga numero. 716 00:31:40,620 --> 00:31:46,562 At maaari naming makuha lamang ng ilang mga boluntaryo upang kumatawan 9, 17, 20, 22, 29, at 34? 717 00:31:46,562 --> 00:31:48,270 Kaya mahalagang lahat ng tao sino ang dito ngayon. 718 00:31:48,270 --> 00:31:50,170 719 00:31:50,170 --> 00:31:52,760 Iyon ay isa, dalawa, tatlo, apat, lima, anim na tao. 720 00:31:52,760 --> 00:31:55,740 At ako hilingin sa iyo na makita go--, walang isa sa likod itataas ang kanilang mga kamay. 721 00:31:55,740 --> 00:32:01,910 OK, isa, dalawa, tatlo, apat, five-- hayaan mo akong i-load balance-- anim. 722 00:32:01,910 --> 00:32:03,051 OK, ka ng anim na dumating sa up. 723 00:32:03,051 --> 00:32:04,050 Kakailanganin naming ibang tao. 724 00:32:04,050 --> 00:32:05,460 Dinala namin ang dagdag na mga bola ng stress. 725 00:32:05,460 --> 00:32:08,200 At kung maaari kang, lamang ng isang sandali, linya 726 00:32:08,200 --> 00:32:10,490 inyong sarili up lamang tulad ang larawang ito dito. 727 00:32:10,490 --> 00:32:15,200 728 00:32:15,200 --> 00:32:15,959 >> Lahat ng karapatan. 729 00:32:15,959 --> 00:32:17,125 Ni makita Hayaan, kung ano ang iyong pangalan? 730 00:32:17,125 --> 00:32:17,550 >> Madla: Andrew. 731 00:32:17,550 --> 00:32:18,800 >> David J. MALAN: Andrew, ang numero 9 sa iyo. 732 00:32:18,800 --> 00:32:19,540 Nice upang matugunan mo. 733 00:32:19,540 --> 00:32:20,400 Narito kang pumunta. 734 00:32:20,400 --> 00:32:21,593 735 00:32:21,593 --> 00:32:22,176 Madla: Jen. 736 00:32:22,176 --> 00:32:22,662 David J. MALAN: Jen. 737 00:32:22,662 --> 00:32:23,162 David. 738 00:32:23,162 --> 00:32:23,765 Numero 17. 739 00:32:23,765 --> 00:32:24,950 740 00:32:24,950 --> 00:32:25,450 Oo? 741 00:32:25,450 --> 00:32:26,400 >> Madla: Ako Julia. 742 00:32:26,400 --> 00:32:26,980 >> David J. MALAN: Julia, si David. 743 00:32:26,980 --> 00:32:27,545 Numero 20. 744 00:32:27,545 --> 00:32:28,507 745 00:32:28,507 --> 00:32:29,340 Madla: Kristiyano. 746 00:32:29,340 --> 00:32:30,715 David J. MALAN: Kristiyano, si David. 747 00:32:30,715 --> 00:32:31,541 Numero 22. 748 00:32:31,541 --> 00:32:32,040 At? 749 00:32:32,040 --> 00:32:32,649 >> Madla: JP. 750 00:32:32,649 --> 00:32:33,440 David J. MALAN: JP. 751 00:32:33,440 --> 00:32:34,880 Numero 29. 752 00:32:34,880 --> 00:32:37,080 Kaya sige lang at makakuha ng in-- Uh oh. 753 00:32:37,080 --> 00:32:38,486 754 00:32:38,486 --> 00:32:38,985 Uh oh. 755 00:32:38,985 --> 00:32:39,650 756 00:32:39,650 --> 00:32:40,150 Standby. 757 00:32:40,150 --> 00:32:41,360 758 00:32:41,360 --> 00:32:42,390 20. 759 00:32:42,390 --> 00:32:43,682 Magkaroon ng isang marker ba? 760 00:32:43,682 --> 00:32:44,890 Madla: Mayroon akong isang Sharpie. 761 00:32:44,890 --> 00:32:45,660 David J. MALAN: Nakakuha ka ng Sharpie? 762 00:32:45,660 --> 00:32:46,159 OK. 763 00:32:46,159 --> 00:32:47,577 764 00:32:47,577 --> 00:32:49,160 At mayroon ang isang piraso ng papel ang sinuman? 765 00:32:49,160 --> 00:32:51,562 766 00:32:51,562 --> 00:32:52,270 I-save ang lecture. 767 00:32:52,270 --> 00:32:53,810 768 00:32:53,810 --> 00:32:55,362 Halika sa. 769 00:32:55,362 --> 00:32:56,320 Madla: Mayroon kaming ito. 770 00:32:56,320 --> 00:32:57,600 David J. MALAN: Mayroon kaming ito? 771 00:32:57,600 --> 00:32:58,577 Ang lahat ng mga karapatan, salamat sa iyo. 772 00:32:58,577 --> 00:33:01,380 773 00:33:01,380 --> 00:33:02,520 Narito pumunta namin. 774 00:33:02,520 --> 00:33:03,582 Ay ito mula sa iyo? 775 00:33:03,582 --> 00:33:04,540 Lamang-save ka ng araw. 776 00:33:04,540 --> 00:33:05,670 777 00:33:05,670 --> 00:33:07,220 Kaya 29. 778 00:33:07,220 --> 00:33:10,510 779 00:33:10,510 --> 00:33:11,110 Lahat ng karapatan. 780 00:33:11,110 --> 00:33:13,360 781 00:33:13,360 --> 00:33:14,890 Maling nabaybay ko 29, ngunit ang OK. 782 00:33:14,890 --> 00:33:15,720 Sige. 783 00:33:15,720 --> 00:33:18,114 Ang lahat ng mga karapatan, Bibigyan kita ng ang panulat ninyo bumalik sa ilang sandali. 784 00:33:18,114 --> 00:33:19,280 Kaya mayroon kaming mga kasamahan dito. 785 00:33:19,280 --> 00:33:20,330 Mayroon ng isang iba pang Hayaang. 786 00:33:20,330 --> 00:33:23,750 Gabe, ang gusto mong i-play sa unang elemento dito? 787 00:33:23,750 --> 00:33:25,705 Kailangan mo kami upang tumuro sa mga masasarap na kakailanganin ng mga tao. 788 00:33:25,705 --> 00:33:26,930 789 00:33:26,930 --> 00:33:31,030 Kaya 9, 17, 20, 22, uri ng 29, at pagkatapos ay 34. 790 00:33:31,030 --> 00:33:32,160 791 00:33:32,160 --> 00:33:33,325 Mawala ba namin ang isang tao? 792 00:33:33,325 --> 00:33:33,950 Gagawin ko ay may 34. 793 00:33:33,950 --> 00:33:36,730 Saan did-- OK, na nagnanais na maging 34? 794 00:33:36,730 --> 00:33:37,605 OK, dumating sa up, 34. 795 00:33:37,605 --> 00:33:39,280 796 00:33:39,280 --> 00:33:41,220 Ang lahat ng mga karapatan, ito ay magiging mahusay nagkakahalaga ang rurok. 797 00:33:41,220 --> 00:33:41,550 Ano ang inyong pangalan? 798 00:33:41,550 --> 00:33:42,040 >> Madla: Peter. 799 00:33:42,040 --> 00:33:43,456 >> David J. MALAN: Pedro, dumating sa up. 800 00:33:43,456 --> 00:33:46,810 Ang lahat ng mga karapatan, kaya narito ang isang buong bungkos ng mga node. 801 00:33:46,810 --> 00:33:49,060 Ang bawat isa sa iyo guys kumakatawan isa sa mga parihaba. 802 00:33:49,060 --> 00:33:51,930 At Gabe, ang bahagyang kakaiba tao out, kumakatawan sa unang. 803 00:33:51,930 --> 00:33:54,850 Kaya ang kanyang pointer ay isang maliit na mas maliit sa screen kaysa sa iba pa. 804 00:33:54,850 --> 00:33:58,120 At sa kasong ito, sa bawat isa sa iyong kaliwa kamay ay magiging alinman sa ituro pababa, 805 00:33:58,120 --> 00:34:01,085 at sa gayon ay kumakatawan sa null, upang lamang ang kawalan ng isang pointer, 806 00:34:01,085 --> 00:34:03,210 o ito ang nangyayari na tumuturo sa isang susunod na node sa iyo. 807 00:34:03,210 --> 00:34:05,440 >> Kaya ngayon kung adorn mo inyong sarili tulad ng larawan 808 00:34:05,440 --> 00:34:07,585 dito, magpatuloy at punto sa isa't isa, na may Gabe 809 00:34:07,585 --> 00:34:11,030 sa partikular na tumuturo sa numero 9 upang kumatawan sa listahan. 810 00:34:11,030 --> 00:34:14,050 OK, at numero ng 34, ang iyong kaliwang kamay Dapat lamang na tumuturo sa sahig. 811 00:34:14,050 --> 00:34:15,750 >> OK, kaya ito ay naka-link na listahan. 812 00:34:15,750 --> 00:34:17,580 Kaya ito ang sitwasyon na pinag-uusapan. 813 00:34:17,580 --> 00:34:20,210 At sa katunayan, ito ay kinatawan ng isang klase ng mga problema 814 00:34:20,210 --> 00:34:21,929 na maaari mong subukan upang malutas gamit ang code. 815 00:34:21,929 --> 00:34:25,020 Gusto mong ipasok sa huli isang bagong elemento na ito sa listahan. 816 00:34:25,020 --> 00:34:27,494 Sa kasong ito, kami ay pagpunta sa subukan ang pagpapasok ng numero 55. 817 00:34:27,494 --> 00:34:28,500 818 00:34:28,500 --> 00:34:30,860 Ngunit may pupuntahan maging iba't ibang mga kaso upang isaalang-alang. 819 00:34:30,860 --> 00:34:34,409 At sa katunayan, ito ay magiging isa ng malaki-larawan takeaways dito, ay, 820 00:34:34,409 --> 00:34:35,659 ano ang iba't ibang mga kaso. 821 00:34:35,659 --> 00:34:39,120 Ano ang iba't ibang mga kundisyon kung o sangay na maaaring mayroon ang iyong programa? 822 00:34:39,120 --> 00:34:42,024 >> Well, ang bilang na sinusubukan mong insert, na alam natin ngayon upang maging 55, 823 00:34:42,024 --> 00:34:44,650 ngunit kung hindi mo alam nang maaga, daresay ko 824 00:34:44,650 --> 00:34:47,840 Nabibilang sa hindi bababa sa tatlong posibleng mga sitwasyon. 825 00:34:47,840 --> 00:34:49,717 Saan maaaring maging isang bagong elemento? 826 00:34:49,717 --> 00:34:51,050 Madla: At sa dulo o gitna. 827 00:34:51,050 --> 00:34:54,150 David J. MALAN: Sa katapusan, sa sa gitna, o sa simula. 828 00:34:54,150 --> 00:34:56,650 Kaya inaangkin ko mayroong hindi bababa sa tatlong mga problema na kailangan namin upang malutas. 829 00:34:56,650 --> 00:34:58,691 Sabihin pumili kung ano ang marahil arguably ang pinakasimpleng 830 00:34:58,691 --> 00:35:01,090 isa, kung saan ang mga bagong elemento Nabibilang sa simula. 831 00:35:01,090 --> 00:35:04,040 Kaya pupuntahan ko mayroon code masyadong tulad ng paghahanap, na kung saan ko lang ay nagsulat. 832 00:35:04,040 --> 00:35:07,670 At pupuntahan ko mayroon ptr, na Kukunin ko ay kumakatawan dito gamit ang aking daliri, 833 00:35:07,670 --> 00:35:08,370 gaya ng dati. 834 00:35:08,370 --> 00:35:12,430 >> At tandaan, kung ano ang halaga nag-initialize namin ptr sa? 835 00:35:12,430 --> 00:35:15,300 Kaya nasimulan namin ito sa null sa umpisa. 836 00:35:15,300 --> 00:35:16,410 837 00:35:16,410 --> 00:35:19,770 Ngunit pagkatapos ay kung ano ang ginagawa namin nang isang beses namin ay sa loob ng aming pag-andar ng paghahanap? 838 00:35:19,770 --> 00:35:20,940 839 00:35:20,940 --> 00:35:24,870 Unang Itinakda namin ito katumbas ng, na kung saan ay hindi nangangahulugan ng paggawa nito. 840 00:35:24,870 --> 00:35:25,890 841 00:35:25,890 --> 00:35:30,570 Kung una itinakda ko ptr katumbas ng, kung ano ang dapat ang aking kamay ba talagang maging tumuturo sa? 842 00:35:30,570 --> 00:35:31,070 I-right. 843 00:35:31,070 --> 00:35:33,290 Kaya kung Gabe at ako ay pumunta sa upang maging katumbas ng halaga dito, 844 00:35:33,290 --> 00:35:34,760 kailangan naming i-parehong punto sa numero 9. 845 00:35:34,760 --> 00:35:36,420 >> Kaya ito ay ang simula ng aming kuwento. 846 00:35:36,420 --> 00:35:38,700 At ngayon ito ay isa lamang prangka, kahit na ang syntax bago. 847 00:35:38,700 --> 00:35:40,580 Conceptually ito ay isa lamang linear paghahanap. 848 00:35:40,580 --> 00:35:42,750 Ay 55 na katumbas ng 9? 849 00:35:42,750 --> 00:35:45,559 O sa halip, sabihin nating mas mababa sa 9. 850 00:35:45,559 --> 00:35:47,600 Dahil sinusubukan ko upang malaman kung saan upang ilagay ang 55. 851 00:35:47,600 --> 00:35:51,270 Mas mababa sa 9, mas mababa sa 17, mas mababa sa 20, mas mababa sa 22, mas mababa sa 29, 852 00:35:51,270 --> 00:35:52,510 mas mababa sa 34, hindi. 853 00:35:52,510 --> 00:35:55,080 Kaya ngayon kami ay sa kasong isa sa hindi bababa sa tatlong. 854 00:35:55,080 --> 00:35:59,910 >> Kung gusto ko upang ipasok 55 sa paglipas dito, kung ano mga linya ng code na kailangan upang isagawa? 855 00:35:59,910 --> 00:36:01,890 Paano gumagana ang larawang ito ng kailangang baguhin ang mga tao? 856 00:36:01,890 --> 00:36:03,181 Ano ang gagawin ko sa aking kaliwang kamay? 857 00:36:03,181 --> 00:36:04,530 858 00:36:04,530 --> 00:36:07,360 Ito ay dapat na sa una null, dahil ako sa dulo ng listahan. 859 00:36:07,360 --> 00:36:09,318 At ano ang dapat mangyari dito sa Pedro, ay ito? 860 00:36:09,318 --> 00:36:10,520 861 00:36:10,520 --> 00:36:12,430 Malinaw na Siya'y pagpunta sa ituro sa akin. 862 00:36:12,430 --> 00:36:15,580 Kaya inaangkin ko mayroong hindi bababa sa dalawang linya ng code sa sample code mula ngayon 863 00:36:15,580 --> 00:36:18,570 na pupuntahan ipatupad ang Ang sitwasyong ng pagdaragdag ng 55 sa likod o hulihan. 864 00:36:18,570 --> 00:36:20,950 At maaari ba akong magkaroon ng isang tao hop up at kinakatawan lamang 55? 865 00:36:20,950 --> 00:36:22,200 Ang lahat ng mga karapatan, ikaw ang bagong 55. 866 00:36:22,200 --> 00:36:23,580 867 00:36:23,580 --> 00:36:27,054 >> Kaya ngayon kung ano kung ang susunod na Ang sitwasyong ito ay kasama, 868 00:36:27,054 --> 00:36:29,720 at gusto naming upang ipasok sa simula o ulo ng listahang ito? 869 00:36:29,720 --> 00:36:31,100 At kung ano ang iyong pangalan, numero ng 55? 870 00:36:31,100 --> 00:36:31,420 >> Madla: Jack. 871 00:36:31,420 --> 00:36:32,295 >> David J. MALAN: Jack? 872 00:36:32,295 --> 00:36:33,585 OK, mabait sa matugunan mo. 873 00:36:33,585 --> 00:36:34,210 Maligayang pagdating sakay. 874 00:36:34,210 --> 00:36:36,640 Kaya ngayon kami ay pagpunta sa magpasok ng, sabihin nating, ang bilang 5. 875 00:36:36,640 --> 00:36:39,840 Narito ang pangalawang kaso ng tatlong ay dumating up kami sa dati. 876 00:36:39,840 --> 00:36:43,050 Kaya kung 5 nabibilang sa simula, sabihin makita kung paano namin makita na ang out. 877 00:36:43,050 --> 00:36:46,310 Initialize ko ang aking ptr pointer sa numero muli 9. 878 00:36:46,310 --> 00:36:49,140 At ako natanto, oh, 5 ay mas mababa sa 9. 879 00:36:49,140 --> 00:36:50,880 Kaya ayusin ang larawang ito para sa amin. 880 00:36:50,880 --> 00:36:54,820 Kaninong mga kamay, Gabe o ni David ang or-- kung ano ang pangalan ng numero 9 ni? 881 00:36:54,820 --> 00:36:55,740 >> Madla: Jen. 882 00:36:55,740 --> 00:36:58,406 >> David J. MALAN: hands-- Jen ay kung alin sa aming mga kamay kailangang baguhin? 883 00:36:58,406 --> 00:36:58,905 884 00:36:58,905 --> 00:37:00,970 OK, kaya Gabe tumuturo sa kung ano ngayon? 885 00:37:00,970 --> 00:37:01,640 Sa akin. 886 00:37:01,640 --> 00:37:02,750 Ako ang bagong node. 887 00:37:02,750 --> 00:37:04,870 Kaya idedetalye ko lang ang uri ng paglipat dito upang makita ito biswal. 888 00:37:04,870 --> 00:37:06,435 At samantala ano ang gagawin ko ituro iyon? 889 00:37:06,435 --> 00:37:07,910 890 00:37:07,910 --> 00:37:09,020 Pa rin kung saan makakakuha ako ng pagturo. 891 00:37:09,020 --> 00:37:10,000 Kaya na ito. 892 00:37:10,000 --> 00:37:13,717 Kaya lamang talagang isang linya ng pag-aayos ng code sa partikular na isyu na ito, ay mukhang ito. 893 00:37:13,717 --> 00:37:14,800 Ang lahat ng mga karapatan, sa gayon ay maganda. 894 00:37:14,800 --> 00:37:17,580 At maaari isang tao maging isang placeholder para sa 5? 895 00:37:17,580 --> 00:37:18,080 Halika sa up. 896 00:37:18,080 --> 00:37:20,270 897 00:37:20,270 --> 00:37:21,320 Susubukan naming kumuha ka ng susunod na pagkakataon. 898 00:37:21,320 --> 00:37:24,280 >> Ang lahat ng mga karapatan, kaya now-- at bilang isang bukod, ang mga pangalan 899 00:37:24,280 --> 00:37:28,510 Hindi ako sa paggawa ng tahasang pagbanggit ng karapatan ngayon, pred pointer, predecessor pointer 900 00:37:28,510 --> 00:37:31,260 at mga bagong pointer, na na naibigay ang mga pangalan lamang 901 00:37:31,260 --> 00:37:35,280 sa sample code upang ang mga payo o ang aking mga kamay na uri ng pagturo sa paligid. 902 00:37:35,280 --> 00:37:36,060 Ano ang inyong pangalan? 903 00:37:36,060 --> 00:37:36,700 >> Madla: Christine. 904 00:37:36,700 --> 00:37:37,100 >> David J. MALAN: Christine. 905 00:37:37,100 --> 00:37:38,090 Maligayang pagdating sakay. 906 00:37:38,090 --> 00:37:42,180 Isaalang-alang natin ngayon ang lahat ng karapatan, kaya hayaan isang bahagyang higit pa nakakainis na sitwasyon, 907 00:37:42,180 --> 00:37:46,350 kung saan gusto kong magpasok ng mga isang bagay tulad ng 26 sa ito. 908 00:37:46,350 --> 00:37:47,090 20? 909 00:37:47,090 --> 00:37:47,590 Ano? 910 00:37:47,590 --> 00:37:50,510 Ang mga are-- magandang bagay na mayroon kami ito panulat. 911 00:37:50,510 --> 00:37:51,955 Ang lahat ng mga karapatan, 20. 912 00:37:51,955 --> 00:37:53,640 913 00:37:53,640 --> 00:37:57,570 Kung may isang tao ay maaaring makakuha ng isa piraso ng papel na handa na, lamang sa case-- ang lahat ng karapatan. 914 00:37:57,570 --> 00:37:58,370 Oh, kawili-wili. 915 00:37:58,370 --> 00:37:59,760 916 00:37:59,760 --> 00:38:02,390 Well ito ay isang halimbawa ng isang panayam bug. 917 00:38:02,390 --> 00:38:03,894 OK kaya kung ano muli ang inyong pangalan? 918 00:38:03,894 --> 00:38:04,560 Madla: Julia. 919 00:38:04,560 --> 00:38:07,559 David J. MALAN: Julia, maaari mong i-pop out at magpanggap na kayo ay hindi kailanman doon? 920 00:38:07,559 --> 00:38:09,040 OK, ito ay hindi kailanman nangyari. 921 00:38:09,040 --> 00:38:09,680 Salamat sa iyo. 922 00:38:09,680 --> 00:38:12,180 Kaya ipagpalagay na nais naming isingit Julia sa ito naka-link na listahan. 923 00:38:12,180 --> 00:38:13,780 Siya ay ang bilang 20. 924 00:38:13,780 --> 00:38:15,530 At syempre siya pagpunta sa nabibilang sa 925 00:38:15,530 --> 00:38:17,521 begin-- ay hindi tumuturo sa kahit ano pa. 926 00:38:17,521 --> 00:38:20,020 Kaya ang iyong mga kamay ay maaaring uri ng magiging down na null o ilang mga halaga ng basura. 927 00:38:20,020 --> 00:38:21,210 Sabihin natin ang kuwento mabilis Hayaan. 928 00:38:21,210 --> 00:38:22,980 Ako na tumuturo sa numero 5 oras na ito. 929 00:38:22,980 --> 00:38:23,880 Pagkatapos suriin ko 9. 930 00:38:23,880 --> 00:38:25,130 Pagkatapos suriin ko 17. 931 00:38:25,130 --> 00:38:26,247 Pagkatapos suriin ko 22. 932 00:38:26,247 --> 00:38:27,650 933 00:38:27,650 --> 00:38:32,485 At Napag-alaman kong, ooh, Julia Kailangang pumunta bago 22. 934 00:38:32,485 --> 00:38:33,580 935 00:38:33,580 --> 00:38:34,660 Kaya kung ano ang kailangang mangyari? 936 00:38:34,660 --> 00:38:35,786 937 00:38:35,786 --> 00:38:36,910 Kailangan Kaninong mga kamay upang baguhin? 938 00:38:36,910 --> 00:38:38,360 Julia, na mina, or-- kung ano muli ang inyong pangalan? 939 00:38:38,360 --> 00:38:39,230 >> Madla: Kristiyano. 940 00:38:39,230 --> 00:38:40,060 >> David J. MALAN: Christian o? 941 00:38:40,060 --> 00:38:40,560 >> Madla: Andy. 942 00:38:40,560 --> 00:38:40,905 >> David J. MALAN: Andy. 943 00:38:40,905 --> 00:38:41,654 Christian o Andy? 944 00:38:41,654 --> 00:38:44,280 945 00:38:44,280 --> 00:38:45,690 Kailangang ituro sa Andy? 946 00:38:45,690 --> 00:38:46,780 947 00:38:46,780 --> 00:38:47,341 Julia. 948 00:38:47,341 --> 00:38:47,840 Lahat ng karapatan. 949 00:38:47,840 --> 00:38:48,960 Kaya Andy, ang gusto mong ituro sa Julia? 950 00:38:48,960 --> 00:38:50,120 Ngunit maghintay ng isang minuto. 951 00:38:50,120 --> 00:38:53,260 Sa kuwento kaya sa ngayon, Ako ang uri ng isa 952 00:38:53,260 --> 00:38:56,800 sa pagsingil, sa kamalayan na pointer ay ang bagay na 953 00:38:56,800 --> 00:38:57,850 paglipat sa listahan. 954 00:38:57,850 --> 00:39:00,800 Maaaring mayroon kami ng isang pangalan para sa Andy, ngunit walang variable na tinatawag na Andy. 955 00:39:00,800 --> 00:39:04,320 Ang tanging iba pang mga variable na mayroon kami ay una, kung sino ang kinakatawan ng Gabe. 956 00:39:04,320 --> 00:39:07,690 >> Kaya ito ay talagang kung bakit kaya malayo hindi namin kinakailangan na ito. 957 00:39:07,690 --> 00:39:10,846 Ngunit ngayon sa screen mayroong banggitin muli ng pred pointer. 958 00:39:10,846 --> 00:39:11,970 Kaya hayaan mo akong maging mas tahasang. 959 00:39:11,970 --> 00:39:14,820 Kung ito ang pointer, nagkaroon ako ng mas mahusay na makakuha ng higit sa isang maliit na matalino 960 00:39:14,820 --> 00:39:15,950 tungkol sa aking iteration. 961 00:39:15,950 --> 00:39:19,580 Kung hindi mo bale ko ang aking pagpunta sa pamamagitan dito muli, na nakaturo dito, na nakaturo dito. 962 00:39:19,580 --> 00:39:22,500 Ngunit hayaan mo akong magkaroon ng isang pred pointer, predecessor pointer, na 963 00:39:22,500 --> 00:39:24,740 uri ng pagturo sa elemento ako ay isa lamang sa. 964 00:39:24,740 --> 00:39:27,330 Kaya kapag pumunta ko dito, ngayon ang aking mga pag-update pakaliwa kamay. 965 00:39:27,330 --> 00:39:29,370 Kailan ko pumunta dito ang aking mga pag-update ng kaliwang kamay. 966 00:39:29,370 --> 00:39:33,090 At ngayon Mayroon akong hindi lamang isang pointer sa ang elemento na pumupunta pagkatapos Julia, 967 00:39:33,090 --> 00:39:36,300 Mayroon pa rin ako ng pointer sa Andy, bago ang element. 968 00:39:36,300 --> 00:39:39,430 Kaya ikaw ay may access, tunay, breadcrumbs, kung gagawin mo, 969 00:39:39,430 --> 00:39:41,500 sa lahat ng mga kinakailangang mga payo. 970 00:39:41,500 --> 00:39:43,710 >> Kaya kung gumagamit ako ng pagturo sa Andy at ako rin ng pagturo 971 00:39:43,710 --> 00:39:47,105 sa Kristiyano, na ang mga kamay dapat na ngayon itinuturo sa ibang lugar? 972 00:39:47,105 --> 00:39:48,770 973 00:39:48,770 --> 00:39:51,960 Kaya Andy ay maaari na ngayong tumuturo sa Julia. 974 00:39:51,960 --> 00:39:54,460 Maaari na ngayong tumuturo sa Julia Kristiyano. 975 00:39:54,460 --> 00:39:56,950 Dahil maaari niyang kopyahin ang aking pointer kanang kamay ni. 976 00:39:56,950 --> 00:40:00,044 At na mabisang Binibigyan ka ng pabalik sa lugar na ito dito. 977 00:40:00,044 --> 00:40:02,460 Kaya sa maikling, kahit na ito nagtatagal sa amin uri ng magpakailanman 978 00:40:02,460 --> 00:40:04,510 upang aktwal na i-update ang isang listahan ng naka-link, Napagtanto 979 00:40:04,510 --> 00:40:06,580 na ang mga operasyon ay medyo simple. 980 00:40:06,580 --> 00:40:10,030 Ito'y ng isa, dalawa, tatlo linya ng code sa huli. 981 00:40:10,030 --> 00:40:12,780 Ngunit balot sa paligid ng mga linya ng code baka 982 00:40:12,780 --> 00:40:16,350 ay isang bit ng logic na mabisang itinatanong ang mga katanungan, kung saan tayo? 983 00:40:16,350 --> 00:40:18,970 Sigurado kami sa simula, sa gitna, o sa dulo? 984 00:40:18,970 --> 00:40:21,890 >> Ngayon, may mga tiyak na ang ilang mga iba pang mga pagpapatakbo na maaari naming ipatupad. 985 00:40:21,890 --> 00:40:24,880 At ang mga larawan dito ilarawan lamang kung ano ang ginawa lang namin sa mga tao. 986 00:40:24,880 --> 00:40:26,080 Paano ang tungkol sa pag-alis? 987 00:40:26,080 --> 00:40:30,650 Kung gusto kong, halimbawa, alisin ang numero ng 34 o 55, 988 00:40:30,650 --> 00:40:34,680 Maaaring mayroon ko ang mga parehong uri ng code, ngunit Pupunta ako sa kailangan ng isa o dalawang hakbang. 989 00:40:34,680 --> 00:40:36,110 Dahil kung ano ang bago? 990 00:40:36,110 --> 00:40:40,460 Kung aalisin ko ay may sa dulo, tulad ng numero ng 55 at pagkatapos ay 34, 991 00:40:40,460 --> 00:40:42,995 kung ano ay mayroon ding upang baguhin tulad ng ginagawa ko na? 992 00:40:42,995 --> 00:40:44,870 Kailangan ko bang hindi evict-- kung ano muli ang inyong pangalan? 993 00:40:44,870 --> 00:40:45,380 >> Madla: Jack. 994 00:40:45,380 --> 00:40:46,255 >> David J. MALAN: Jack. 995 00:40:46,255 --> 00:40:49,770 Mayroon akong hindi lamang evict-- libreng Jack, kaya Literal na tawagan libreng Jack, o hindi bababa sa 996 00:40:49,770 --> 00:40:53,530 ang pointer doon din, ngunit ngayon kung ano ang kailangang baguhin sa Peter? 997 00:40:53,530 --> 00:40:55,510 Kanyang kamay mas mahusay na magsimula na nakaturo pababa. 998 00:40:55,510 --> 00:40:59,300 Dahil sa lalong madaling tumawag ako ng libreng on Jack, kung pagturo pa rin ni Pedro sa Jack 999 00:40:59,300 --> 00:41:02,530 at samakatuwid ko panatilihin traversing sa listahan at i-access ang pointer, 1000 00:41:02,530 --> 00:41:05,650 na kapag ang aming lumang segmentation kaibigan Kasalanan maaaring aktwal na kick in. 1001 00:41:05,650 --> 00:41:07,860 Dahil binigyan ka namin ang memory pabalik sa Jack. 1002 00:41:07,860 --> 00:41:10,760 >> Maaari kang manatili doon awkwardly para sa sandali lamang. 1003 00:41:10,760 --> 00:41:13,410 Dahil mayroon kaming dalawang lamang huling mga pagpapatakbo upang isaalang-alang. 1004 00:41:13,410 --> 00:41:15,600 Pag-aalis ng mga ulo ng listahan, o ang beginning-- at ang isang ito ay 1005 00:41:15,600 --> 00:41:16,349 isang maliit na nakakainis. 1006 00:41:16,349 --> 00:41:19,640 Dahil mayroon kaming malaman na Gabe ay uri ng espesyal na sa programang ito. 1007 00:41:19,640 --> 00:41:21,440 Dahil sa katunayan, siya ay kanyang sariling pointer. 1008 00:41:21,440 --> 00:41:24,860 Siya'y hindi lamang ini-itinuturo sa, bilang ay halos ang lahat ng iba pa dito. 1009 00:41:24,860 --> 00:41:28,112 >> Kaya kapag ang pinuno ng listahan ay Inalis, na ang mga kamay kailangang baguhin ngayon? 1010 00:41:28,112 --> 00:41:29,070 Ano ulit ang inyong pangalan? 1011 00:41:29,070 --> 00:41:29,450 >> Madla: Christine. 1012 00:41:29,450 --> 00:41:31,408 >> David J. MALAN: Ako ay kahindik-hindik sa mga pangalan, tila. 1013 00:41:31,408 --> 00:41:34,011 Kaya Christine at Gabe, na ang mga kamay kailangang baguhin 1014 00:41:34,011 --> 00:41:36,510 kapag sinubukan naming alisin ang Christine, numero 5, mula sa larawan? 1015 00:41:36,510 --> 00:41:37,550 1016 00:41:37,550 --> 00:41:38,820 OK, na gawin Gabe kaya hayaan. 1017 00:41:38,820 --> 00:41:40,950 Gabe pupuntahan ituro, baka, sa numero 9. 1018 00:41:40,950 --> 00:41:42,230 1019 00:41:42,230 --> 00:41:44,642 Ngunit kung ano ang susunod na dapat mangyari? 1020 00:41:44,642 --> 00:41:46,600 Madla: Christine dapat maging null [INAUDIBLE]. 1021 00:41:46,600 --> 00:41:50,244 David J. MALAN: OK, dapat namin marahil make-- narinig ko "null" sa isang lugar. 1022 00:41:50,244 --> 00:41:51,410 Madla: Walang bisa at libreng kanya. 1023 00:41:51,410 --> 00:41:51,855 David J. MALAN: null ano? 1024 00:41:51,855 --> 00:41:53,074 Madla: Walang bisa at libreng kanya. 1025 00:41:53,074 --> 00:41:54,490 David J. MALAN: Walang bisa at libreng kanya. 1026 00:41:54,490 --> 00:41:55,422 Kaya ito ay napakadali. 1027 00:41:55,422 --> 00:41:58,380 At ito ay perpekto na ikaw ngayon uri ng nakatayo doon, na hindi kasali. 1028 00:41:58,380 --> 00:42:00,430 Dahil mo pa decoupled mula sa listahan. 1029 00:42:00,430 --> 00:42:02,820 Epektibo mong pa orphaned mula sa listahan. 1030 00:42:02,820 --> 00:42:07,770 At sa gayon mas mahusay na kami ay tumawag sa libreng ngayon Christine upang bigyan na memory pabalik. 1031 00:42:07,770 --> 00:42:10,240 Kung hindi man sa bawat oras na namin tanggalin ang isang node mula sa listahan 1032 00:42:10,240 --> 00:42:14,230 Maaaring ginagawa namin ang listahan mas maikli, ngunit hindi tunay na nagpapababa 1033 00:42:14,230 --> 00:42:15,096 sa laki sa memorya. 1034 00:42:15,096 --> 00:42:17,720 At kaya kung panatilihin namin ang pagdaragdag at pagdaragdag, pagdaragdag ng mga bagay sa listahan, 1035 00:42:17,720 --> 00:42:19,280 maaaring makakuha ng mas mabagal sa aking computer at mas mabagal at mas mabagal, 1036 00:42:19,280 --> 00:42:21,740 dahil Nauubusan na ako ng memorya, kahit na hindi ako talaga 1037 00:42:21,740 --> 00:42:25,580 gamit bytes Christine ni ng memorya na ngayon. 1038 00:42:25,580 --> 00:42:28,500 >> Kaya sa katapusan mayroong iba pang mga mga sitwasyon, ng course-- pag-alis 1039 00:42:28,500 --> 00:42:30,640 sa gitna, pag-alis sa dulo, tulad ng nakita natin. 1040 00:42:30,640 --> 00:42:32,348 Ngunit ang mas kawili-wiling Ang hamon ngayon ay 1041 00:42:32,348 --> 00:42:34,770 magiging upang isaalang-alang nang eksakto kung ano ang oras tumatakbo ang. 1042 00:42:34,770 --> 00:42:36,640 Kaya hindi lamang maaari mong panatilihin ang iyong piraso ng papel, kung, Gabe, 1043 00:42:36,640 --> 00:42:38,640 hindi mo nais na bale pagbibigay lahat ng bola ng stress. 1044 00:42:38,640 --> 00:42:42,100 Salamat sa iyo kaya magkano sa aming listahan na naka-link ng mga boluntaryo dito, kung dati mo. 1045 00:42:42,100 --> 00:42:45,320 >> [APPLAUSE] 1046 00:42:45,320 --> 00:42:46,700 >> David J. MALAN: Lahat ng karapatan. 1047 00:42:46,700 --> 00:42:51,110 Kaya ng ilang Analytical mga katanungan pagkatapos, kung maaari ko. 1048 00:42:51,110 --> 00:42:59,670 Nakakita kami pagtatanda na ito bago, O malaki at wakas, itaas na hangganan 1049 00:42:59,670 --> 00:43:02,520 at mas mababang mga hangganan sa oras ng paggana ng ilang mga algorithm. 1050 00:43:02,520 --> 00:43:04,950 Kaya isaalang-alang na lamang hayaan isang pares ng mga katanungan. 1051 00:43:04,950 --> 00:43:07,090 >> Ang isa, at sinabi namin ito bago, ano ang tumakbo 1052 00:43:07,090 --> 00:43:10,647 oras ng paghahanap para sa isang listahan sa mga tuntunin ng malaking O? 1053 00:43:10,647 --> 00:43:13,480 Ano ang isang pang-itaas nakatali sa pagtakbo oras ng naghahanap ang isang naka-link na listahan 1054 00:43:13,480 --> 00:43:16,340 bilang ipinatupad ng aming mga boluntaryo dito? 1055 00:43:16,340 --> 00:43:17,820 Ito ay malaking O ng n, linear. 1056 00:43:17,820 --> 00:43:20,630 Dahil sa ang pinakamasama kaso, ang elemento, tulad ng 55, 1057 00:43:20,630 --> 00:43:23,830 maaaring hinahanap namin para sa ay maaaring maging kung saan Jack ay, ang lahat ng mga paraan sa dulo. 1058 00:43:23,830 --> 00:43:28,250 At sa kasamaang-palad, hindi tulad ng isang array hindi namin maaaring makakuha ng magarbong oras na ito. 1059 00:43:28,250 --> 00:43:31,820 Kahit na ang lahat ng aming mga tao ay pinagsunod-sunod mula sa maliit na mga elemento, 5, 1060 00:43:31,820 --> 00:43:35,900 ang lahat ng mga paraan ng hanggang sa ang mas malaking elemento, 55, na kadalasan ay isang magandang bagay. 1061 00:43:35,900 --> 00:43:38,815 Ngunit ano ang ginagawa na palagay hindi na-daan sa amin upang gawin? 1062 00:43:38,815 --> 00:43:39,775 1063 00:43:39,775 --> 00:43:40,650 Madla: [INAUDIBLE] 1064 00:43:40,650 --> 00:43:40,920 David J. MALAN: Sabihing muli? 1065 00:43:40,920 --> 00:43:41,800 Madla: Random access. 1066 00:43:41,800 --> 00:43:43,049 David J. MALAN: Random access. 1067 00:43:43,049 --> 00:43:46,330 At siya namang ay nangangahulugan na maaari naming hindi na gagamitin ng mahina ng mga zero, Swersey, 1068 00:43:46,330 --> 00:43:49,365 at obviousness ng paggamit ng binary maghanap at hatiin at lupigin. 1069 00:43:49,365 --> 00:43:51,240 Dahil kahit na namin mga tao ay maaaring malinaw naman 1070 00:43:51,240 --> 00:43:54,610 makita na Andy o Kristiyano ay halos sa gitna ng listahan, 1071 00:43:54,610 --> 00:43:57,670 Alam namin na bilang lamang computer sa pamamagitan ng skimming sa listahan 1072 00:43:57,670 --> 00:43:59,029 mula sa napaka-simula. 1073 00:43:59,029 --> 00:44:00,570 Kaya binigyan up namin na random na pag-access. 1074 00:44:00,570 --> 00:44:04,380 >> Kaya malaking O ng n ay ngayon sa itaas mapasailalim sa aming oras ng paghahanap. 1075 00:44:04,380 --> 00:44:07,920 Paano ang tungkol sa wakas ng aming paghahanap? 1076 00:44:07,920 --> 00:44:11,535 Ano ang mas mababang nakatali sa paghahanap para sa ilang mga numero sa listahang ito? 1077 00:44:11,535 --> 00:44:12,410 Madla: [INAUDIBLE] 1078 00:44:12,410 --> 00:44:13,040 David J. MALAN: Sabihing muli? 1079 00:44:13,040 --> 00:44:13,420 Madla: Isa. 1080 00:44:13,420 --> 00:44:13,800 David J. MALAN: Isa. 1081 00:44:13,800 --> 00:44:14,760 Kaya tuluy-tuloy na oras. 1082 00:44:14,760 --> 00:44:17,020 Sa pinakamahusay na kaso, Christine ay sa katunayan sa simula ng listahan. 1083 00:44:17,020 --> 00:44:19,020 At kaming naghahanap ng para sa numero 5, kaya natagpuan namin sa kanya. 1084 00:44:19,020 --> 00:44:19,787 Kaya walang malaki deal. 1085 00:44:19,787 --> 00:44:22,370 Subalit siya nakuha upang maging sa simula ng listahan sa kasong ito. 1086 00:44:22,370 --> 00:44:23,745 Paano ang tungkol sa isang bagay tulad Tanggalin? 1087 00:44:23,745 --> 00:44:24,717 1088 00:44:24,717 --> 00:44:26,300 Paano kung gusto mong tanggalin ang isang elemento? 1089 00:44:26,300 --> 00:44:29,200 Ano ang itaas na nakatali at mas mababang mga hangganan sa pagtanggal ng isang bagay mula sa naka-link 1090 00:44:29,200 --> 00:44:29,699 ilista? 1091 00:44:29,699 --> 00:44:35,195 1092 00:44:35,195 --> 00:44:36,070 Madla: [INAUDIBLE] 1093 00:44:36,070 --> 00:44:36,420 David J. MALAN: Sabihing muli? 1094 00:44:36,420 --> 00:44:37,067 Madla: n. 1095 00:44:37,067 --> 00:44:38,900 David J. MALAN: n ay sa katunayan itaas na hangganan. 1096 00:44:38,900 --> 00:44:41,700 Dahil sa ang pinakamasama kaso subukan namin tanggalin Jack, tulad ng ginawa namin lamang. 1097 00:44:41,700 --> 00:44:43,050 Siya ay ang lahat ng mga paraan sa dulo. 1098 00:44:43,050 --> 00:44:45,419 Tumatagal magpakailanman sa amin, o n hakbang na ito upang mahanap sa kanya. 1099 00:44:45,419 --> 00:44:46,460 Kaya na ang isang itaas na hangganan. 1100 00:44:46,460 --> 00:44:47,430 Iyon ang linear, sigurado. 1101 00:44:47,430 --> 00:44:50,970 At ang pinakamahusay na kaso sa pagtakbo ang oras, o ang mas mababang mga hangganan sa pinakamahusay na kaso 1102 00:44:50,970 --> 00:44:51,975 ay magiging tuluy-tuloy na oras. 1103 00:44:51,975 --> 00:44:54,600 Dahil siguro sinusubukan naming tanggalin Christine, at makakuha pa lang namin masuwerteng 1104 00:44:54,600 --> 00:44:55,558 siya sa simula. 1105 00:44:55,558 --> 00:44:56,350 Ngayon maghintay ng isang minuto. 1106 00:44:56,350 --> 00:44:59,370 Gabe ay sa simula rin, at nagkaroon din namin na i-update ang Gabe. 1107 00:44:59,370 --> 00:45:01,150 Kaya na ay hindi isang hakbang lamang. 1108 00:45:01,150 --> 00:45:04,210 Kaya ito ay sa katunayan pare-pareho oras, sa pinakamahusay na kaso, 1109 00:45:04,210 --> 00:45:06,345 alisin ang pinakamaliit na elemento? 1110 00:45:06,345 --> 00:45:07,360 1111 00:45:07,360 --> 00:45:10,960 Ito ay, kahit na maaari itong maging dalawa, tatlo, o kahit na 100 mga linya ng code, 1112 00:45:10,960 --> 00:45:14,000 kung ito ay ang parehong bilang ng mga mga linya, hindi sa ilang mga loop, 1113 00:45:14,000 --> 00:45:16,577 at independiyenteng ng laki ng listahan, walang pasubali. 1114 00:45:16,577 --> 00:45:18,660 Tinatanggal ang elemento sa sa simula ng listahan, 1115 00:45:18,660 --> 00:45:21,940 kahit na mayroon kami upang harapin ang Gabe, ay pare-pareho ang oras pa rin. 1116 00:45:21,940 --> 00:45:24,220 >> Kaya ito ay tila tulad ng isang napakalaking hakbang paurong. 1117 00:45:24,220 --> 00:45:27,000 At kung ano ang isang pag-aaksaya ng panahon kung, sa linggo ng isa at linggo 1118 00:45:27,000 --> 00:45:30,250 zero namin ay may mga hindi lamang pseudocode code ngunit aktwal na code 1119 00:45:30,250 --> 00:45:35,780 upang ipatupad ang isang bagay na pag-log base n, o mag-log, sa halip, ng n, base 2, 1120 00:45:35,780 --> 00:45:37,150 sa mga tuntunin ng running time nito. 1121 00:45:37,150 --> 00:45:40,710 Kaya bakit ang heck ay nais naming simulan gamit ang isang bagay tulad ng isang naka-link na listahan? 1122 00:45:40,710 --> 00:45:41,517 Oo. 1123 00:45:41,517 --> 00:45:44,022 >> Madla: Kaya maaari mong idagdag mga elemento sa array. 1124 00:45:44,022 --> 00:45:46,230 David J. MALAN: Kaya maaari mong magdagdag ng mga elemento sa array. 1125 00:45:46,230 --> 00:45:47,550 At ito ay masyadong thematic. 1126 00:45:47,550 --> 00:45:49,740 At patuloy kaming makita ito, ito kalakalan-off, magkano 1127 00:45:49,740 --> 00:45:51,573 tulad ng nasaksihan namin ang isang kalakalan-off ang may-uri-merge. 1128 00:45:51,573 --> 00:45:54,606 Talaga namin mai-mapabilis maghanap o pag-uuri, sa halip, 1129 00:45:54,606 --> 00:45:57,480 kung gastusin namin ng kaunti pang espasyo at May dagdag na chunk ng isang memory 1130 00:45:57,480 --> 00:45:58,760 o isang array para sa uri merge. 1131 00:45:58,760 --> 00:46:01,270 Ngunit gastusin namin ng higit pang espasyo, ngunit i-save namin ang oras. 1132 00:46:01,270 --> 00:46:04,820 Sa kasong ito, hindi namin pagbibigay up oras ngunit kami ay 1133 00:46:04,820 --> 00:46:08,170 pagkakaroon ng kakayahang umangkop, dynamism kung gagawin mo, 1134 00:46:08,170 --> 00:46:10,280 na kung saan ay arguably ang positibong tampok na ito. 1135 00:46:10,280 --> 00:46:11,520 >> Din kami gumagasta ng espasyo. 1136 00:46:11,520 --> 00:46:13,710 Sa anong kahulugan ay naka-link ilista ang mas mahal 1137 00:46:13,710 --> 00:46:15,700 sa mga tuntunin ng espasyo kaysa sa isang array? 1138 00:46:15,700 --> 00:46:18,379 1139 00:46:18,379 --> 00:46:19,920 Saan nagmumula ang mga dagdag na espasyo mula sa? 1140 00:46:19,920 --> 00:46:20,460 Oo? 1141 00:46:20,460 --> 00:46:21,800 >> Madla: [INAUDIBLE] pointer. 1142 00:46:21,800 --> 00:46:23,310 >> David J. MALAN: Oo, namin Mayroon din ang pointer. 1143 00:46:23,310 --> 00:46:25,560 Kaya ito ay minorly nakakainis sa na hindi na am 1144 00:46:25,560 --> 00:46:27,780 Ako sa pag-iimbak lamang sa isang int kinakatawan ang isang int. 1145 00:46:27,780 --> 00:46:30,990 Ako sa pag-iimbak sa isang int at isang pointer, na kung saan ay 32 bits din. 1146 00:46:30,990 --> 00:46:33,470 Kaya ako literal pagdodoble ang halaga ng puwang ng kasangkot. 1147 00:46:33,470 --> 00:46:36,040 Kaya na ang isang kalakalan-off, ngunit na sa kaso ng int. 1148 00:46:36,040 --> 00:46:39,580 Ipagpalagay na hindi ka nag-iimbak ng int, ngunit ipagpalagay bawat isa sa mga parihaba 1149 00:46:39,580 --> 00:46:43,290 o bawat isa sa mga kawani na tao ay kumakatawan sa isang salita, isang salitang Ingles na 1150 00:46:43,290 --> 00:46:46,430 ay maaaring maging limang mga character, 10 character, siguro ay mas mabuti. 1151 00:46:46,430 --> 00:46:49,940 Pagkatapos ng pagdaragdag ng 32 lamang sa higit pang mga piraso ay maaaring maging mas mababa ng isang malaking deal. 1152 00:46:49,940 --> 00:46:52,160 >> Paano kung ang bawat isa sa mga mag-aaral sa demonstration 1153 00:46:52,160 --> 00:46:55,107 ay literal structs mag-aaral na May mga pangalang at bahay at siguro 1154 00:46:55,107 --> 00:46:57,065 mga numero ng telepono at Twitter humahawak at mga katulad. 1155 00:46:57,065 --> 00:46:59,564 Kaya ang lahat ng mga patlang na sinimulan namin pakikipag-usap tungkol sa iba pang araw, 1156 00:46:59,564 --> 00:47:02,410 higit na mas mababa ng isang malaking bilang deal ang aming mga node makakuha ng higit pang mga kawili-wiling 1157 00:47:02,410 --> 00:47:05,972 at malaki gastusin, eh, ang isang karagdagang pointer lamang i-link ang mga iyon nang magkakasama. 1158 00:47:05,972 --> 00:47:07,180 Ngunit sa katunayan, ito ay isang kalakalan-off. 1159 00:47:07,180 --> 00:47:09,560 At sa katunayan, ang code ay mas kumplikado, bilang ikaw 1160 00:47:09,560 --> 00:47:11,770 makita sa pamamagitan ng skimming sa pamamagitan ng na partikular na halimbawa. 1161 00:47:11,770 --> 00:47:14,302 Ngunit ano kung mayroong ang ilang mga banal grail dito. 1162 00:47:14,302 --> 00:47:17,010 Paano kung hindi kami gumawa ng isang hakbang paurong ngunit isang napakalaking hakbang pasulong 1163 00:47:17,010 --> 00:47:19,180 at ipatupad ang data istraktura sa pamamagitan ng kung saan namin 1164 00:47:19,180 --> 00:47:22,870 Maaari mahanap ang mga elemento tulad ng Jack o Christine o anumang iba pang mga elemento 1165 00:47:22,870 --> 00:47:25,870 sa array na ito sa tunay na pare-pareho ang oras? 1166 00:47:25,870 --> 00:47:26,920 Paghahanap ay pare-pareho. 1167 00:47:26,920 --> 00:47:28,320 Tanggalin ay pare-pareho. 1168 00:47:28,320 --> 00:47:29,570 Isingit ay pare-pareho. 1169 00:47:29,570 --> 00:47:32,260 Ang lahat ng mga pagpapatakbong ito ay pare-pareho. 1170 00:47:32,260 --> 00:47:33,750 Iyon ay magiging banal sa aming grail. 1171 00:47:33,750 --> 00:47:36,690 At iyon ay kung saan namin ay kukunin sa susunod na pagkakataon. 1172 00:47:36,690 --> 00:47:38,600 Tingnan mo pagkatapos. 1173 00:47:38,600 --> 00:47:39,371