1 00:00:00,000 --> 00:00:11,860 2 00:00:11,860 --> 00:00:13,120 >> SPEAKER 1: Id-dritt, hekk aħna lura. 3 00:00:13,120 --> 00:00:14,480 Merħba għall CS50. 4 00:00:14,480 --> 00:00:16,510 Dan huwa l-aħħar ta 'seba' ġimgħa. 5 00:00:16,510 --> 00:00:20,200 Allura ifakkar li l-aħħar darba, bdejna tħares lejn ftit aktar sofistikati 6 00:00:20,200 --> 00:00:21,100 strutturi ta 'dejta. 7 00:00:21,100 --> 00:00:25,110 Peress sa issa, kollha kellna verament għad-dispożizzjoni tagħna kienet din, firxa. 8 00:00:25,110 --> 00:00:29,340 >> Iżda qabel we jarmi l-array li ma dak kollu li interessanti, li tabilħaqq 9 00:00:29,340 --> 00:00:33,570 attwalment hija, liema huma wħud mill- pluses ta 'din id-data sempliċi 10 00:00:33,570 --> 00:00:34,560 istruttura s'issa? 11 00:00:34,560 --> 00:00:36,110 X'hemm tajba fi? 12 00:00:36,110 --> 00:00:39,450 S'issa kif aħna stajt tidher? 13 00:00:39,450 --> 00:00:42,540 What do inti ltqajna? 14 00:00:42,540 --> 00:00:44,028 Xejn. 15 00:00:44,028 --> 00:00:45,020 >> STUDENT: [inaudible]. 16 00:00:45,020 --> 00:00:45,395 >> SPEAKER 1: X'hemm li? 17 00:00:45,395 --> 00:00:46,410 >> STUDENT: [inaudible]. 18 00:00:46,410 --> 00:00:47,000 >> SPEAKER 1: Daqs fiss. 19 00:00:47,000 --> 00:00:51,260 OK, hekk għaliex huwa d-daqs fiss tajba għalkemm? 20 00:00:51,260 --> 00:00:53,180 >> STUDENT: [inaudible]. 21 00:00:53,180 --> 00:00:56,240 >> SPEAKER 1: OK, dan huwa effiċjenti fl -sens li inti tista 'talloka 22 00:00:56,240 --> 00:01:00,070 ammont fiss ta 'l-ispazju, li nisperaw huwa preċiżament kemm 23 00:01:00,070 --> 00:01:01,180 ispazju kif tixtieq. 24 00:01:01,180 --> 00:01:02,720 Allura li tista 'tkun assolutament plus. 25 00:01:02,720 --> 00:01:06,530 >> X'hemm ieħor ġenb minn firxa? 26 00:01:06,530 --> 00:01:07,610 Yeah? 27 00:01:07,610 --> 00:01:08,750 >> STUDENT: [inaudible]. 28 00:01:08,750 --> 00:01:09,550 >> SPEAKER 1: L-- sorry? 29 00:01:09,550 --> 00:01:11,270 >> STUDENT: [inaudible]. 30 00:01:11,270 --> 00:01:13,620 >> SPEAKER 1: Il-kaxxi fil-memorja jew ħdejn xulxin. 31 00:01:13,620 --> 00:01:15,220 U hu utli - għaliex? 32 00:01:15,220 --> 00:01:15,970 Li pjuttost veru. 33 00:01:15,970 --> 00:01:18,611 Iżda kif nistgħu jisfruttaw li l-verità? 34 00:01:18,611 --> 00:01:21,500 >> STUDENT: [inaudible]. 35 00:01:21,500 --> 00:01:24,490 >> SPEAKER 1: Eżattament, nistgħu jżommu rekord ta ' fejn kollox huwa biss billi jkun jaf 36 00:01:24,490 --> 00:01:28,560 indirizz wieħed, jiġifieri l-indirizz tal- ewwel byte ta 'dik blokki ta' memorja. 37 00:01:28,560 --> 00:01:30,420 Jew fil-każ tas-sekwenza, l-indirizz ta 'l-ewwel 38 00:01:30,420 --> 00:01:31,460 char f'dak sekwenza. 39 00:01:31,460 --> 00:01:33,330 U minn hemm, nistgħu nsibu l-aħħar tas-sekwenza. 40 00:01:33,330 --> 00:01:35,710 Nistgħu nsibu t-tieni element, l- tielet element, u oħrajn. 41 00:01:35,710 --> 00:01:38,740 >> U għalhekk l-mod fancy ta 'jiddeskrivi dik karatteristika hija li arrays tagħtina 42 00:01:38,740 --> 00:01:40,020 aċċess bl-addoċċ. 43 00:01:40,020 --> 00:01:44,330 Biss bl-użu tal-parentesi kwadri notazzjoni u numru, inti tista 'tiżdied għal 44 00:01:44,330 --> 00:01:48,070 element speċifiku fil-firxa fil-ħin kostanti, big O 45 00:01:48,070 --> 00:01:49,810 ta 'wieħed, biex ngħidu hekk. 46 00:01:49,810 --> 00:01:51,080 >> Iżda hemm kien xi effetti negattivi. 47 00:01:51,080 --> 00:01:53,110 Liema firxa ma tagħmel faċilment? 48 00:01:53,110 --> 00:01:55,810 49 00:01:55,810 --> 00:01:57,170 X'hemm mhux tajba fil? 50 00:01:57,170 --> 00:01:58,810 >> STUDENT: [inaudible]. 51 00:01:58,810 --> 00:01:59,860 >> SPEAKER 1: X'hemm li? 52 00:01:59,860 --> 00:02:00,530 >> STUDENT: [inaudible]. 53 00:02:00,530 --> 00:02:01,460 >> SPEAKER 1: Espansjoni fid-daqs. 54 00:02:01,460 --> 00:02:04,800 Allura l-aspetti negattivi tal-firxa huma preċiżament l-oppost ta 'dak l- 55 00:02:04,800 --> 00:02:05,540 upsides huma. 56 00:02:05,540 --> 00:02:07,610 Allura wieħed mill-aspetti negattivi huwa li huwa daqs fiss. 57 00:02:07,610 --> 00:02:09,400 Allura inti ma tistax verament jikbru. 58 00:02:09,400 --> 00:02:13,510 Tista 'jalloka mill-ġdid ta' blokki akbar ta ' memorja, u mbagħad jimxu l-elementi qodma 59 00:02:13,510 --> 00:02:14,460 fil-firxa ġdida. 60 00:02:14,460 --> 00:02:18,060 U allura free-firxa qodma, għal Pereżempju, bl-użu malloc jew simili 61 00:02:18,060 --> 00:02:21,180 funzjoni msejħa realloc, li reallocates memorja. 62 00:02:21,180 --> 00:02:25,490 >> Realloc, bħala twarrib, tipprova li jtik memorja li jmiss għall-firxa 63 00:02:25,490 --> 00:02:26,610 li diġà għandek. 64 00:02:26,610 --> 00:02:28,740 Iżda jista affarijiet jimxu madwar għal kollox. 65 00:02:28,740 --> 00:02:30,710 Iżda fil-qosor, li għali, id-dritt? 66 00:02:30,710 --> 00:02:33,440 Għaliex jekk għandek blokki ta 'memorja ta' dan id-daqs, iżda inti verament irridu wieħed 67 00:02:33,440 --> 00:02:36,710 ta 'dan id-daqs, u inti tixtieq li jippreservaw l-elementi oriġinali, għandek 68 00:02:36,710 --> 00:02:40,510 bejn wieħed u ieħor ta 'proċess lineari ikkupjar ħin li jeħtieġ li jiġri minn 69 00:02:40,510 --> 00:02:41,900 array qadima lill ġdida. 70 00:02:41,900 --> 00:02:44,630 U r-realtà qed titlob lill operattiva sistema għal darb'oħra u għal darb'oħra u 71 00:02:44,630 --> 00:02:48,340 għal darb'oħra għal biċċiet kbar ta 'memorja tista' tibda jiswik xi żmien ukoll. 72 00:02:48,340 --> 00:02:52,250 Allura huwa kemm barka u curse fl jaħbi, il-fatt li dawn arrays 73 00:02:52,250 --> 00:02:53,860 huma ta 'daqs fiss. 74 00:02:53,860 --> 00:02:56,790 Imma jekk aħna jintroduċu minflok xi ħaġa bħal dan, li aħna imsejħa linked 75 00:02:56,790 --> 00:03:00,580 lista, irridu jiksbu upsides u ftit ftit negattivi hawnhekk ukoll. 76 00:03:00,580 --> 00:03:05,780 >> Allura lista marbut huwa sempliċement data struttura ffurmata minn structs C f'dan 77 00:03:05,780 --> 00:03:09,850 każ, fejn Struct, recall, huwa biss kontenitur għal wieħed jew aktar speċifiċi 78 00:03:09,850 --> 00:03:11,100 tipi ta 'varjabbli. 79 00:03:11,100 --> 00:03:16,110 F'dan il-każ, liema do tip ta 'data jidhru li huma ġewwa tal-Struct li 80 00:03:16,110 --> 00:03:17,600 aħħar darba aħna tissejjaħ node? 81 00:03:17,600 --> 00:03:19,380 Kull wieħed minn dawn rettangoli huwa node. 82 00:03:19,380 --> 00:03:22,660 U kull wieħed mill-rettangoli iżgħar ġewwa ta 'dan huwa tip ta' data. 83 00:03:22,660 --> 00:03:25,300 Liema tipi aħna ma jgħidu kienu nhar it-Tnejn? 84 00:03:25,300 --> 00:03:26,478 Yeah? 85 00:03:26,478 --> 00:03:27,870 >> STUDENT: [inaudible]. 86 00:03:27,870 --> 00:03:30,721 >> SPEAKER 1: A varjabbli u werrej, jew b'mod aktar speċifiku, l-int, għal n, 87 00:03:30,721 --> 00:03:32,180 u werrej fil-qiegħ. 88 00:03:32,180 --> 00:03:35,360 Kemm ta 'dawk jinzertaw 32 bits, fil inqas fuq il-kompjuter bħal dan CS50 89 00:03:35,360 --> 00:03:37,980 Appliance, u allura jkunu mfassla ugwalment fid-daqs. 90 00:03:37,980 --> 00:03:42,260 >> Allura dak qed jużaw il-pointer għalkemm għal apparentement? 91 00:03:42,260 --> 00:03:47,690 Għaliex żid din vleġġa issa meta arrays kienu hekk sbieħ u nodfa u sempliċi? 92 00:03:47,690 --> 00:03:50,460 X'inhu l-pointer tagħmel għal us f'kull wieħed minn dawn lymph? 93 00:03:50,460 --> 00:03:52,160 >> STUDENT: [inaudible]. 94 00:03:52,160 --> 00:03:52,465 >> SPEAKER 1: Eżattament. 95 00:03:52,465 --> 00:03:54,120 Huwa javżak fejn inti il-wieħed li jmiss huwa. 96 00:03:54,120 --> 00:03:57,350 So I sort tal-użu l-analoġija ta ' użu ta 'ħajt li sort ta' 97 00:03:57,350 --> 00:03:59,180 ħajt dawn lymph flimkien. 98 00:03:59,180 --> 00:04:01,760 U dan huwa eżattament dak li aħna qed tagħmel mal- pointers għax kull wieħed minn dawn 99 00:04:01,760 --> 00:04:06,360 biċċiet ta 'memorja tista' jew ma jistgħux ikunu kontigwa, lura lura lura 100 00:04:06,360 --> 00:04:09,500 ġewwa ta 'RAM, minħabba li kull darba li inti sejħa malloc qal, agħti lili biżżejjed 101 00:04:09,500 --> 00:04:12,510 bytes għal node ġdid, dan jista 'jkun jkun hawn jew jista 'jkun hawn. 102 00:04:12,510 --> 00:04:13,120 Jista 'jkun hawn. 103 00:04:13,120 --> 00:04:13,730 Jista 'jkun hawn. 104 00:04:13,730 --> 00:04:14,640 Inti biss ma nafx. 105 00:04:14,640 --> 00:04:17,880 >> Iżda bl-użu pointers fl-indirizzi ta ' ta'dawk il-lymph, inti tista stitch minnhom 106 00:04:17,880 --> 00:04:22,370 flimkien b'mod li jistenna viżwalment bħal lista anke jekk dawn l-affarijiet huma 107 00:04:22,370 --> 00:04:26,770 kollha mifruxa matul wieħed tiegħek jew tnejn tiegħek jew erba gigabytes ta 'RAM tiegħek 108 00:04:26,770 --> 00:04:28,760 ġewwa tal-kompjuter tiegħek. 109 00:04:28,760 --> 00:04:33,230 >> Allura l-tnaqqis, allura, lista marbut huwa dak? 110 00:04:33,230 --> 00:04:34,670 X'hemm prezz aħna qed apparentement ħlas? 111 00:04:34,670 --> 00:04:36,010 >> STUDENT: [inaudible]. 112 00:04:36,010 --> 00:04:36,920 >> SPEAKER 1: aktar spazju, id-dritt? 113 00:04:36,920 --> 00:04:39,340 Imxejna, f'dan il-każ, rdoppja l-ammont ta 'spazju għax konna marret 114 00:04:39,340 --> 00:04:43,500 minn 32 bits għal kull node, għal kull int, hekk issa 64 bits għaliex għandna biex 115 00:04:43,500 --> 00:04:45,050 iżommu madwar pointer ukoll. 116 00:04:45,050 --> 00:04:48,860 Ikollok aktar effiċjenza jekk Struct tiegħek hija akbar minn dan il-ħaġa sempliċi. 117 00:04:48,860 --> 00:04:52,020 Jekk inti fil-fatt ikollhom student ġewwa tagħhom huwa ftit kordi għall 118 00:04:52,020 --> 00:04:55,430 isem u d-dar, forsi numru ta 'ID, forsi xi oqsma oħra għal kollox. 119 00:04:55,430 --> 00:04:59,000 >> Mela jekk għandek Struct kbir biżżejjed, allura forsi l-ispiża ta 'l-pointer huwa 120 00:04:59,000 --> 00:05:00,010 mhux tali big deal. 121 00:05:00,010 --> 00:05:03,570 Dan huwa daqsxejn ta 'każ kantuniera f'dak aħna qed jaħżnu tali sempliċi primitive 122 00:05:03,570 --> 00:05:04,760 ġewwa tal-lista marbuta. 123 00:05:04,760 --> 00:05:05,790 Imma l-punt huwa l-istess. 124 00:05:05,790 --> 00:05:08,230 Int żgur infiq aktar memorja, imma int jkollna 125 00:05:08,230 --> 00:05:08,990 flessibilità. 126 00:05:08,990 --> 00:05:12,280 Għaliex issa jekk irrid li jiżdied element fil-bidu ta din il-lista, 127 00:05:12,280 --> 00:05:14,340 I jridu jallokaw node ġdid. 128 00:05:14,340 --> 00:05:17,180 U I għandhom jaġġornaw biss dawk vleġeġ b'xi bi ftit li jiċċaqalqu 129 00:05:17,180 --> 00:05:17,980 xi indikazzjonijiet madwar. 130 00:05:17,980 --> 00:05:20,580 >> Jekk irrid li daħħal xi ħaġa fil- nofs tal-lista, I ma jkollhom 131 00:05:20,580 --> 00:05:24,410 imbotta kulħadd aside bħal għamilna fl passat ġimgħat ma 'voluntiera tagħna li 132 00:05:24,410 --> 00:05:25,700 rrappreżentaw firxa. 133 00:05:25,700 --> 00:05:29,470 I tista 'biss jalloka node ġdid u allura biss il-punt l-vleġeġ fil 134 00:05:29,470 --> 00:05:32,290 direzzjonijiet differenti minħabba li ma għandhom jibqgħu fl attwali 135 00:05:32,290 --> 00:05:35,670 memorja linja vera bħal stajt mfassla dan hawn fuq l-iskrin. 136 00:05:35,670 --> 00:05:38,400 >> U mbagħad fl-aħħar, jekk inti tixtieq li daħħal xi ħaġa fl-aħħar tal-lista, huwa 137 00:05:38,400 --> 00:05:39,210 anke eħfef. 138 00:05:39,210 --> 00:05:43,320 Dan huwa tip ta 'notazzjoni arbitrarja, iżda 34 ta pointer, tieħu raden. 139 00:05:43,320 --> 00:05:46,710 X'inhu l-valur tal-pointer tagħha aktar probabbli tip mislut ta qisni antik 140 00:05:46,710 --> 00:05:47,700 antenna iskola hemmhekk? 141 00:05:47,700 --> 00:05:48,920 >> STUDENT: [inaudible]. 142 00:05:48,920 --> 00:05:49,900 >> SPEAKER 1: Huwa probabbilment null. 143 00:05:49,900 --> 00:05:52,710 U fil-fatt li hija awtur wieħed rappreżentazzjoni ta null. 144 00:05:52,710 --> 00:05:56,310 U huwa null għaliex inti assolutament bżonn tkun taf fejn it-tmiem ta 'linked 145 00:05:56,310 --> 00:06:00,050 lista hija, lest inti żżomm ġejjin u wara u wara dawn vleġeġ 146 00:06:00,050 --> 00:06:01,170 li xi valur żibel. 147 00:06:01,170 --> 00:06:06,230 Allura null ikun ifisser li hemm l-ebda aktar lymph għad-dritt ta numru 34, 148 00:06:06,230 --> 00:06:07,200 f'dan il-każ. 149 00:06:07,200 --> 00:06:10,270 >> Allura aħna nipproponu li nistgħu jimplimentaw dan node fil-kodiċi. 150 00:06:10,270 --> 00:06:12,130 U aħna stajt tidher dan it-tip ta 'sintassi qabel. 151 00:06:12,130 --> 00:06:15,090 Typedef biss jiddefinixxi tip ġdid għall us, tagħtina sinonimu bħal 152 00:06:15,090 --> 00:06:17,100 string kien għal char *. 153 00:06:17,100 --> 00:06:21,030 F'dan il-każ, li għaddej biex tagħtina notazzjoni shorthand sabiex node Struct 154 00:06:21,030 --> 00:06:24,010 jistgħu minflok biss jinkiteb bħala node, li hija nadifa ħafna. 155 00:06:24,010 --> 00:06:25,360 Huwa ħafna inqas verbose. 156 00:06:25,360 --> 00:06:30,080 >> Ġewwa ta 'node huwa apparentement int imsejħa n, u mbagħad Struct node * 157 00:06:30,080 --> 00:06:34,670 li jfisser eżattament dak li ridna l- vleġeġ li jfisser, a pointer għall-ieħor 158 00:06:34,670 --> 00:06:36,940 node tal-istess tip data eżatta. 159 00:06:36,940 --> 00:06:40,300 U nipproponi li nistgħu jimplimentaw funzjoni ta 'tfittxija bħal dan, li minnhom mill- 160 00:06:40,300 --> 00:06:41,890 ewwel daqqa t'għajn jista 'jidher ftit kumplessi. 161 00:06:41,890 --> 00:06:43,330 Imma ejja tara li fil-kuntest. 162 00:06:43,330 --> 00:06:45,480 >> Let me go fuq l-appliance hawn. 163 00:06:45,480 --> 00:06:48,460 Let me jiftħu fajl imsejjaħ lista zero dot h. 164 00:06:48,460 --> 00:06:53,950 U li fih biss id-definizzjoni aħna biss raw mument ilu għal din id-data 165 00:06:53,950 --> 00:06:55,390 tip imsejħa node. 166 00:06:55,390 --> 00:06:57,350 Allura konna li jitqiegħdu fis-fajl h dot. 167 00:06:57,350 --> 00:07:01,430 >> U bħala twarrib, anke jekk din programm li int ser tara hija 168 00:07:01,430 --> 00:07:05,410 mhux kollha li kumplessi, huwa tabilħaqq konvenzjoni meta tikteb programm biex 169 00:07:05,410 --> 00:07:10,270 tpoġġi affarijiet simili tipi ta 'data, għal pull kostanti kultant, ġewwa ta 'tiegħek 170 00:07:10,270 --> 00:07:13,210 fajl tal-header u mhux neċessarjament fajl C tiegħek, ċertament meta tiegħek 171 00:07:13,210 --> 00:07:17,370 programmi tikseb akbar u akbar, sabiex inti taf fejn tfittex kemm għall 172 00:07:17,370 --> 00:07:20,840 dokumentazzjoni f'xi każijiet, jew għal affarijiet bażiċi bħal dan, il- 173 00:07:20,840 --> 00:07:22,360 definizzjoni ta 'xi tip. 174 00:07:22,360 --> 00:07:25,680 >> Jekk I issa jiftħu lista zero dot c, avviż ftit affarijiet. 175 00:07:25,680 --> 00:07:29,090 Dan jinkludi fajls header ftit, ħafna li konna rajna qabel. 176 00:07:29,090 --> 00:07:31,980 Dan jinkludi fajl header tagħha stess. 177 00:07:31,980 --> 00:07:35,200 >> U bħala twarrib, għaliex dan huwa doppju kwotazzjonijiet hawn, għall-kuntrarju l-angolu 178 00:07:35,200 --> 00:07:38,340 parentesi fuq il-linja li Stajt enfasizzat hemmhekk? 179 00:07:38,340 --> 00:07:39,180 >> STUDENT: [inaudible]. 180 00:07:39,180 --> 00:07:40,460 >> SPEAKER 1: Yeah dan huwa fajl lokali. 181 00:07:40,460 --> 00:07:44,300 Mela jekk huwa fajl lokali tal tiegħek hawn fuq il-linja 15, per eżempju, tuża 182 00:07:44,300 --> 00:07:46,570 il-kwotazzjonijiet doppja minflok ta 'l-parentesi angolati. 183 00:07:46,570 --> 00:07:48,270 >> Issa dan huwa tip ta 'interessanti. 184 00:07:48,270 --> 00:07:51,830 Avviż li stajt ddikjarat globali varjabbli f'dan il-programm fuq il-linja 18 185 00:07:51,830 --> 00:07:55,910 imsejħa ewwel, l-idea hija li dan huwa se tkun pointer għall-ewwel 186 00:07:55,910 --> 00:07:59,190 node fil-lista linked tiegħi, u stajt initialized li null, għaliex stajt 187 00:07:59,190 --> 00:08:02,310 mhux allokat ebda attwali lymph biss s'issa. 188 00:08:02,310 --> 00:08:07,570 >> Allura dan jirrappreżenta, pictorially, dak li aħna raw mument ilu fl-istampa kif 189 00:08:07,570 --> 00:08:10,090 li pointer fuq il-bogħod xellug naħa. 190 00:08:10,090 --> 00:08:12,260 Allura issa dritt, li pointer ma jkollux vleġġa. 191 00:08:12,260 --> 00:08:14,590 Huwa minflok huwa biss null. 192 00:08:14,590 --> 00:08:17,880 Imma jirrappreżenta x'se jkunu l- indirizz ta 'l-ewwel attwali 193 00:08:17,880 --> 00:08:19,480 node f'din il-lista. 194 00:08:19,480 --> 00:08:22,120 Allura stajt implimentati hija globali għaliex, kif tkun taf tara, dan kollu 195 00:08:22,120 --> 00:08:25,310 programm ma fil-ħajja huwa implimentat lista marbuta għalija. 196 00:08:25,310 --> 00:08:27,050 >> Issa stajt ltqajna prototipi ftit hawn. 197 00:08:27,050 --> 00:08:31,190 I iddeċieda li jimplimenta karatteristiċi simili tħassir, inserzjoni, it-tiftix, u 198 00:08:31,190 --> 00:08:31,740 traversal - 199 00:08:31,740 --> 00:08:35,210 l-aħħar walk sempliċement madwar il- lista, stampar elementi tagħha. 200 00:08:35,210 --> 00:08:36,750 U issa hawnhekk rutina prinċipali tiegħi. 201 00:08:36,750 --> 00:08:39,890 U aħna mhux se jqattgħu wisq ħin fuq dawn peress li dan huwa tip ta ', wieħed jittama 202 00:08:39,890 --> 00:08:41,780 hat qodma minn issa. 203 00:08:41,780 --> 00:08:45,370 >> Jien ser tagħmel dan li ġej, filwaqt li l-utent tikkoopera. 204 00:08:45,370 --> 00:08:47,300 Allura wieħed, jien ser jistampaw out dan il-menu. 205 00:08:47,300 --> 00:08:49,420 U stajt formattjati bħala nadif kif stajt. 206 00:08:49,420 --> 00:08:52,240 Jekk tipi l-utent fil-wieħed, dan ifisser huma jridu li jitħassar xi ħaġa. 207 00:08:52,240 --> 00:08:54,560 Jekk tipi l-utent fi tnejn, li jfisser li jkunu jridu xi ħaġa daħħal. 208 00:08:54,560 --> 00:08:55,930 U oħrajn. 209 00:08:55,930 --> 00:08:58,270 Jien ser imbagħad fil-pront imbagħad għal kmand. 210 00:08:58,270 --> 00:08:59,300 U allura jien ser tuża GetInt. 211 00:08:59,300 --> 00:09:02,790 >> Allura dan huwa verament sempliċi menuing interface fejn inti sempliċiment għandek tip 212 00:09:02,790 --> 00:09:05,270 immappjar numru li wieħed ta 'dawk jikkmanda. 213 00:09:05,270 --> 00:09:08,730 U issa għandi swiċċ nadif sbieħ dikjarazzjoni li għaddej biex jaqilbu fuq 214 00:09:08,730 --> 00:09:10,090 ikun x'ikun l-utent ittajpjat pulzieri 215 00:09:10,090 --> 00:09:12,180 U jekk dawn ittajpjat waħda, I ser sejħa iħassru u break. 216 00:09:12,180 --> 00:09:14,380 Jekk dawn ittajpjat tnejn, I ser sejħa daħħal u kisser. 217 00:09:14,380 --> 00:09:16,490 >> U issa avviż stajt jitqiegħdu f'kull ta 'dawn fuq l-istess linja. 218 00:09:16,490 --> 00:09:18,360 Din hija biss deċiżjoni stilistiċi. 219 00:09:18,360 --> 00:09:20,210 Tipikament Rajna xi ħaġa bħal dan. 220 00:09:20,210 --> 00:09:23,260 Imma I biss iddeċieda, franchement, program tiegħi ħares aktar tinqara minħabba 221 00:09:23,260 --> 00:09:25,980 kien erba 'każijiet biss biss lista hija bħal dan. 222 00:09:25,980 --> 00:09:28,360 Użu Totally leġittimu ta 'stil. 223 00:09:28,360 --> 00:09:31,480 U jien se tagħmel dan sakemm il- user ma ittajpjat żero, li jiena 224 00:09:31,480 --> 00:09:33,910 iddeċieda se jfisser li jixtiequ jieqfu. 225 00:09:33,910 --> 00:09:36,630 >> Allura issa avviż dak li jien se nagħmlu hawnhekk. 226 00:09:36,630 --> 00:09:38,650 Jien ser tillibera l-lista apparentement. 227 00:09:38,650 --> 00:09:40,230 Iżda aktar fuq li fi ftit mument. 228 00:09:40,230 --> 00:09:41,640 Ejja ewwel run dan il-programm. 229 00:09:41,640 --> 00:09:45,250 So let me tagħmel terminal akbar tieqa, dot lista slash 0. 230 00:09:45,250 --> 00:09:49,510 Jien ser jimxi 'l quddiem u daħħal minn ittajpjar tnejn, numru bħall 50, u issa 231 00:09:49,510 --> 00:09:51,590 int ser tara l-lista issa huwa 50. 232 00:09:51,590 --> 00:09:53,380 U t-test tiegħi biss impress up a bit. 233 00:09:53,380 --> 00:09:55,940 Allura issa avviż-lista fiha in-numru 50. 234 00:09:55,940 --> 00:09:58,220 >> Ejja nagħmlu daħħal ieħor billi tieħu tnejn. 235 00:09:58,220 --> 00:10:01,630 Ejja tip fil-numru wieħed bħal. 236 00:10:01,630 --> 00:10:03,940 Lista issa huwa wieħed, segwit minn 50. 237 00:10:03,940 --> 00:10:06,020 Allura din hija biss rappreżentazzjoni testwali tal-lista. 238 00:10:06,020 --> 00:10:10,550 U ejja jdaħħal waħda aktar numru simili in-numru 42, li huwa wieħed jittama 239 00:10:10,550 --> 00:10:14,620 ser jispiċċaw fin-nofs, għax dan il-programm xorta partikolari li 240 00:10:14,620 --> 00:10:16,320 elementi kif huwa introduċa minnhom. 241 00:10:16,320 --> 00:10:17,220 Allura hemm aħna għandna hija. 242 00:10:17,220 --> 00:10:20,730 Programm sempliċi super li jistgħu assolutament użaw firxa, iżda I 243 00:10:20,730 --> 00:10:23,280 jiġri li tkun qed tuża lista linked biss hekk nista dinamiku 244 00:10:23,280 --> 00:10:24,610 jikbru u tiċkien dan. 245 00:10:24,610 --> 00:10:28,470 >> Mela ejja tagħti ħarsa għal tfittxija, jekk I run kmand tlieta, I trid tfittex 246 00:10:28,470 --> 00:10:31,040 għal, ngħidu aħna, in-numru 43. 247 00:10:31,040 --> 00:10:34,190 U xejn jidher li kien sab, minħabba I marret lura ebda risposta. 248 00:10:34,190 --> 00:10:35,010 Mela ejja jagħmlu dan mill-ġdid. 249 00:10:35,010 --> 00:10:35,690 Fittex. 250 00:10:35,690 --> 00:10:39,520 Ejja tfittxija għal 50, jew pjuttost tfittxija għal 42, li għandha sbieħ 251 00:10:39,520 --> 00:10:40,850 ftit tifsira sottili. 252 00:10:40,850 --> 00:10:42,610 U sibt it-tifsira tal-ħajja hemmhekk. 253 00:10:42,610 --> 00:10:44,990 Numru 42, jekk ma tafx ir-referenza, Google dan. 254 00:10:44,990 --> 00:10:45,350 Kull dritt. 255 00:10:45,350 --> 00:10:47,130 Allura dak li dan il-programm isir għalija? 256 00:10:47,130 --> 00:10:50,660 Huwa biss permessi me daħħal b'hekk bogħod u tfittxija għal elementi. 257 00:10:50,660 --> 00:10:53,650 >> Ejja fast quddiem, imbagħad, li dik il-funzjoni aħna glanced fi 258 00:10:53,650 --> 00:10:55,360 nhar it-Tnejn bħala teaser. 259 00:10:55,360 --> 00:10:59,620 Allura din il-funzjoni, nitlob, tfittxijiet għal element fil-lista b'nota ewwel 260 00:10:59,620 --> 00:11:03,830 waħda, li wassal lill-utent u mbagħad sejħa GetInt biex tikseb int attwali 261 00:11:03,830 --> 00:11:05,060 li inti trid tfittex għal. 262 00:11:05,060 --> 00:11:06,460 >> Imbagħad Avviż dan. 263 00:11:06,460 --> 00:11:10,690 Jien ser toħloq varjabbli temporanju f'konformità 188 imsejjaħ pointer - 264 00:11:10,690 --> 00:11:11,270 PTR - 265 00:11:11,270 --> 00:11:12,440 setgħet hija imsejħa xejn. 266 00:11:12,440 --> 00:11:16,140 U huwa pointer għal node minħabba I qal node * hemmhekk. 267 00:11:16,140 --> 00:11:19,900 U jien initializing li jkun ugwali għal ewwel sabiex I effettivament jkollhom tiegħi 268 00:11:19,900 --> 00:11:22,860 swaba ', biex ngħidu hekk, fuq il-ħafna ewwel element tal-lista. 269 00:11:22,860 --> 00:11:27,460 Mela jekk lemin tiegħi hawnhekk huwa PTR jien tipponta lejn l-istess ħaġa li l-ewwel 270 00:11:27,460 --> 00:11:28,670 hija li tipponta lejn. 271 00:11:28,670 --> 00:11:31,430 >> Allura issa lura fil-kodiċi, dak li jiġri li jmiss - 272 00:11:31,430 --> 00:11:35,070 din hija paradigma komuni meta iterazzjoni fuq struttura bħal 273 00:11:35,070 --> 00:11:35,970 lista marbuta. 274 00:11:35,970 --> 00:11:40,410 Jien ser jagħmlu dan li ġej waqt li pointer mhuwiex ugwali għal null Għalhekk, filwaqt li 275 00:11:40,410 --> 00:11:47,530 finger tiegħi mhix tipponta lejn uħud null valur, jekk pointer vleġġa n ugwali n. 276 00:11:47,530 --> 00:11:52,290 Aħna ser ikollok avviż l-ewwel li n huwa dak li l- utent ittajpjat fil kull GetInts sejħa hawn. 277 00:11:52,290 --> 00:11:54,280 >> U pointer vleġġa n ifisser liema? 278 00:11:54,280 --> 00:11:59,020 Ukoll jekk immorru lura għall-istampa hawn, jekk ikolli saba tipponta lejn 279 00:11:59,020 --> 00:12:02,960 li l-ewwel node fih disa ', l- vleġġa essenzjalment tfisser tmur f'dak 280 00:12:02,960 --> 00:12:08,860 node u grab l-valur fil-lokalità n, f'dan il-każ, il-kaxxa tad-dejta imsejħa n. 281 00:12:08,860 --> 00:12:14,120 >> Bħala twarrib - u aħna raw dan koppja ta 'ġimgħat ilu meta xi ħadd talab - 282 00:12:14,120 --> 00:12:18,840 dan sintassi huwa ġdid, iżda ma agħtina poteri li aħna 283 00:12:18,840 --> 00:12:20,040 ma diġà għandhom. 284 00:12:20,040 --> 00:12:25,325 Liema kienet din il-frażi ekwivalenti għall-użu dot notazzjoni u star koppja 285 00:12:25,325 --> 00:12:29,490 ta 'ġimgħat ilu meta aħna imqaxxar lura dan is-saff daqsxejn prematur? 286 00:12:29,490 --> 00:12:31,780 >> STUDENT: [inaudible]. 287 00:12:31,780 --> 00:12:38,880 >> SPEAKER 1: Eżattament, kien star, u mela kien star dot n, ma 288 00:12:38,880 --> 00:12:41,930 parentesi hawn, li jistenna, franchement, I think ħafna 289 00:12:41,930 --> 00:12:43,320 aktar cryptic biex jinqara. 290 00:12:43,320 --> 00:12:46,270 Iżda star pointer, bħal dejjem, mezzi jmorru hemm. 291 00:12:46,270 --> 00:12:49,090 U ladarba int hemm, liema data qasam tridu taċċessaha? 292 00:12:49,090 --> 00:12:52,730 Well inti tuża l-notazzjoni dot għall-aċċess qasam ta 'data structs, u I 293 00:12:52,730 --> 00:12:54,140 tixtieq speċifikament n. 294 00:12:54,140 --> 00:12:56,240 >> Franchement, nixtieq jargumentaw li dan huwa biss aktar diffiċli biex jinqara. 295 00:12:56,240 --> 00:12:58,080 Huwa diffiċli li tiftakar fejn jagħmlu l-parentesi go, l- 296 00:12:58,080 --> 00:12:59,030 star u kollha ta 'dak. 297 00:12:59,030 --> 00:13:02,150 Allura l-dinja adottata xi sintattika zokkor, biex ngħidu hekk. 298 00:13:02,150 --> 00:13:04,740 Biss mod ta 'tgħid sexy, dan huwa ekwivalenti, u 299 00:13:04,740 --> 00:13:05,970 forsi aktar intuwittivi. 300 00:13:05,970 --> 00:13:09,600 Jekk pointer huwa tabilħaqq pointer, l- vleġġa mezzi notazzjoni jmorru hemm u jsibu 301 00:13:09,600 --> 00:13:11,890 il-qasam f'dan il-każ imsejjaħ n. 302 00:13:11,890 --> 00:13:13,660 >> Mela jekk jien jsibuha, avviż dak I do. 303 00:13:13,660 --> 00:13:17,430 I sempliċiment jistampa, sibt fil-mija i, fejn jitwaħħal fil-valur għal dak int. 304 00:13:17,430 --> 00:13:20,730 I call irqad għat-tieni waħda biss biex tip ta 'affarijiet nieqaf fuq l-iskrin biex 305 00:13:20,730 --> 00:13:22,900 jagħti lill-utent t-tieni biex jassorbu dak li ġara biss. 306 00:13:22,900 --> 00:13:24,290 U mbagħad I break. 307 00:13:24,290 --> 00:13:26,330 Inkella, x'għandi nagħmel? 308 00:13:26,330 --> 00:13:30,960 I taġġorna pointer li ugwali pointer vleġġa li jmiss. 309 00:13:30,960 --> 00:13:35,840 >> Hekk biss li jkun ċar, dan ifisser go hemm, bl-użu notazzjoni qodma l-iskola tiegħi. 310 00:13:35,840 --> 00:13:39,580 Allura dan ifisser biss li jmorru għal dak kollu li int tipponta lejn, li fil-ħafna 311 00:13:39,580 --> 00:13:43,660 ewwel każ huwa jien li tipponta lejn l Struct b'disa fiha. 312 00:13:43,660 --> 00:13:44,510 Allura stajt marret hemmhekk. 313 00:13:44,510 --> 00:13:47,880 U allura l-notazzjoni dot jfisser, jiksbu l-valur li jmiss. 314 00:13:47,880 --> 00:13:50,470 >> Iżda l-valur, anki jekk huwa mfassal bħala dejqa, huwa biss numru. 315 00:13:50,470 --> 00:13:51,720 Huwa indirizz numeriku. 316 00:13:51,720 --> 00:13:55,670 Allura din il-linja waħda tal-kodiċi, jekk bil-miktub bħal dan, l-aktar cryptic 317 00:13:55,670 --> 00:14:00,190 mod, jew bħal dan, il-ftit aktar mod intuwittivi, ifisser biss jiċċaqalqu naħa tiegħi 318 00:14:00,190 --> 00:14:03,460 mill-ewwel node għal dak li jmiss, u allura l-waħda li jmiss, u mbagħad l- 319 00:14:03,460 --> 00:14:05,320 jmiss waħda, u ibqa 'sejjer hekk. 320 00:14:05,320 --> 00:14:09,920 >> Allura aħna mhux se nitkellem fuq l-oħra implimentazzjonijiet tal daħħal u ħassar 321 00:14:09,920 --> 00:14:14,030 u traversal, l-ewwel tnejn li huma involuti b'mod ġust. 322 00:14:14,030 --> 00:14:17,010 U naħseb huwa pjuttost faċli li tinkiseb mitluf meta tagħmel dan verbalment. 323 00:14:17,010 --> 00:14:19,890 Imma dak li nistgħu nagħmlu hawnhekk huwa jippruvaw jiddeterminaw kif 324 00:14:19,890 --> 00:14:21,640 aħjar li tagħmel dan viżwalment. 325 00:14:21,640 --> 00:14:24,800 Minħabba Nixtieq nipproponi li jekk irridu tixtieq li daħħal elementi fis dan 326 00:14:24,800 --> 00:14:26,680 elenku eżistenti, li għandha ħames elementi - 327 00:14:26,680 --> 00:14:29,530 9, 17, 22, 26, u 33 - 328 00:14:29,530 --> 00:14:33,300 jekk jien kienu se jimplimentaw dan kodiċi, I bżonn li jiġi kkunsidrat kif imorru 329 00:14:33,300 --> 00:14:34,160 dwar kif isir dan. 330 00:14:34,160 --> 00:14:37,720 >> U jiena nipproponi tieħu passi tarbija fejn, f'dan il-każ I mean, liema huma 331 00:14:37,720 --> 00:14:41,090 ix-xenarji possibbli li aħna tista 'tiltaqa b'mod ġenerali? 332 00:14:41,090 --> 00:14:44,120 Meta jimplimentaw daħħal għal linked lista, dan jiġri biss li jkun 333 00:14:44,120 --> 00:14:46,090 eżempju speċifiku ta 'daqs ħamsa. 334 00:14:46,090 --> 00:14:50,420 Ukoll jekk inti tixtieq li daħħal numru, bħall jgħidu n-numru wieħed, u 335 00:14:50,420 --> 00:14:53,380 żamma tal-ordni magħżula, fejn ovvjament ma l-numru wieħed jeħtieġ li 336 00:14:53,380 --> 00:14:55,686 jmorru f'dan l-eżempju speċifiku? 337 00:14:55,686 --> 00:14:56,840 Bħal fil-bidu. 338 00:14:56,840 --> 00:15:00,030 >> Imma x'hemm interessanti hemm li jekk inti tixtieq li daħħal wieħed fis dan 339 00:15:00,030 --> 00:15:04,100 lista, liema pointer speċjali jeħtieġ li jiġu aġġornati apparentement? 340 00:15:04,100 --> 00:15:04,610 Ewwel. 341 00:15:04,610 --> 00:15:07,830 Hekk nixtieq jargumentaw, dan huwa l-ewwel każ li aħna tista 'tixtieq li jikkunsidraw, għal 342 00:15:07,830 --> 00:15:11,140 xenarju li jinvolvi ddaħħal fil il-bidu tal-lista. 343 00:15:11,140 --> 00:15:15,400 >> Ejja ġewwieni off forsi bħala faċli jew saħansitra każ aktar faċli, relattivament speaking. 344 00:15:15,400 --> 00:15:18,110 Jissoponi Irrid li daħħal il- numru 35 sabiex magħżula. 345 00:15:18,110 --> 00:15:20,600 Ovvjament jappartjeni hemmhekk. 346 00:15:20,600 --> 00:15:25,320 Allura dak pointer ovvjament se għandhom jiġu aġġornati f'dak ix-xenarju? 347 00:15:25,320 --> 00:15:30,060 34 ta pointer ssir mhux null iżda l-indirizz tal-Struct 348 00:15:30,060 --> 00:15:31,800 bin-numru 35. 349 00:15:31,800 --> 00:15:32,750 Allura dak il-każ tnejn. 350 00:15:32,750 --> 00:15:36,190 Allura diġà, jien tip ta 'quantizing kemm ix-xogħol li nagħmel hawn. 351 00:15:36,190 --> 00:15:39,880 >> U fl-aħħarnett, il-każ tan-nofs huwa ovvju tabilħaqq, fin-nofs, jekk irrid 352 00:15:39,880 --> 00:15:45,870 daħħal xi ħaġa simili jgħidu 23, li tmur bejn il-23 u l-26, iżda 353 00:15:45,870 --> 00:15:48,680 issa l-affarijiet jiksbu ftit aktar involuti għaliex dak 354 00:15:48,680 --> 00:15:52,800 pointers jeħtieġ li jinbidlu? 355 00:15:52,800 --> 00:15:56,680 Allura ovvjament 22 teħtieġ li tinbidel għaliex ma jista 'jiġbed l-26 jibqgħalu. 356 00:15:56,680 --> 00:16:00,320 Hu għandu bżonn biex jindikaw il-node ġdida li I ser ikollhom jallokaw billi ċċempel 357 00:16:00,320 --> 00:16:01,770 malloc jew xi ekwivalenti. 358 00:16:01,770 --> 00:16:05,990 >> Imma mbagħad I wkoll bżonn li node ġdid, 23 f'dan il-każ, li jkollha pointer tagħha 359 00:16:05,990 --> 00:16:07,870 tipponta lejn min? 360 00:16:07,870 --> 00:16:08,560 26. 361 00:16:08,560 --> 00:16:10,380 U hemm għaddej biex tkun ordni ta 'operazzjonijiet hawn. 362 00:16:10,380 --> 00:16:13,410 Għaliex jekk nagħmel dan foolishly, u I per eżempju bidu fil-bidu ta ' 363 00:16:13,410 --> 00:16:16,040 il-lista, u l-għan tiegħi huwa li daħħal 23. 364 00:16:16,040 --> 00:16:18,610 And I check, ma jappartjenix hawn, ħdejn disa? 365 00:16:18,610 --> 00:16:18,950 No 366 00:16:18,950 --> 00:16:20,670 Ma jagħmlu parti minn hawn, li jmiss 17? 367 00:16:20,670 --> 00:16:20,940 No 368 00:16:20,940 --> 00:16:22,530 Ma jappartjeni hawn jmiss 22? 369 00:16:22,530 --> 00:16:23,300 Iva. 370 00:16:23,300 --> 00:16:26,400 >> Issa jekk jien foolish hawn, u mhux ħsieb dan permezz, I jista 371 00:16:26,400 --> 00:16:28,320 jallokaw node ġdida tiegħi għal 23. 372 00:16:28,320 --> 00:16:32,080 I tista 'taġġorna l-pointer minn l-node imsejħa 22, tipponta 373 00:16:32,080 --> 00:16:33,080 huwa fil-node ġdid. 374 00:16:33,080 --> 00:16:36,140 U allura dak li għandi jkollhom jaġġornaw pointer l-node ġdid li jkun? 375 00:16:36,140 --> 00:16:38,120 >> STUDENT: [inaudible]. 376 00:16:38,120 --> 00:16:38,385 >> SPEAKER 1: Eżattament. 377 00:16:38,385 --> 00:16:39,710 Tipponta lejn 26. 378 00:16:39,710 --> 00:16:45,590 Imma Dammit jekk I ma diġà taġġorna Pointer 22 għall-punt fuq dan Guy, u 379 00:16:45,590 --> 00:16:48,260 issa għandi orfni, l-bqija tal-lista, biex ngħidu hekk. 380 00:16:48,260 --> 00:16:52,140 Allura ordni ta 'operazzjonijiet hawn se tkun importanti. 381 00:16:52,140 --> 00:16:55,100 >> Biex tagħmel dan jista I steal, jiġifieri, sitt voluntiera. 382 00:16:55,100 --> 00:16:57,650 U ejja ara jekk aħna ma tistax tagħmel dan viżwalment minflok kodiċi għaqli. 383 00:16:57,650 --> 00:16:59,330 U aħna għandna xi stress sabiħ blalen għalik illum. 384 00:16:59,330 --> 00:17:02,510 OK, kif madwar wieħed, tnejn, fil- lura - fuq l-aħħar hemmhekk. 385 00:17:02,510 --> 00:17:04,530 tlieta, erba, tnejn inti guys fuq l-aħħar. 386 00:17:04,530 --> 00:17:05,579 U ħamsa, sitta. 387 00:17:05,579 --> 00:17:05,839 Sure. 388 00:17:05,839 --> 00:17:06,450 Ħames u sitt. 389 00:17:06,450 --> 00:17:08,390 Kull dritt u aħna ser jiġu lilek guys ħin li jmiss. 390 00:17:08,390 --> 00:17:09,640 Kull dritt, come fuq up. 391 00:17:09,640 --> 00:17:12,010 392 00:17:12,010 --> 00:17:14,819 >> Kull dritt, peress li int up here ewwel, kieku inti tixtieq li jkun il-wieħed awkwardly 393 00:17:14,819 --> 00:17:16,119 fil-Google Glass hawn? 394 00:17:16,119 --> 00:17:19,075 Kull dritt, hekk, OK, ħġieġ, jirreġistra video. 395 00:17:19,075 --> 00:17:22,720 396 00:17:22,720 --> 00:17:24,589 OK, int tajba biex tmur. 397 00:17:24,589 --> 00:17:27,950 >> Kull dritt, hekk jekk inti guys jista 'jidħol fuq hawn, I ippreparat bil-quddiem 398 00:17:27,950 --> 00:17:30,110 xi numri. 399 00:17:30,110 --> 00:17:31,240 Kull dritt, come fuq matul hawn. 400 00:17:31,240 --> 00:17:33,440 U għaliex ma inti tmur ftit wkoll li mod. 401 00:17:33,440 --> 00:17:35,520 U ejja ara, x'hemm isem tiegħek, mal-Google Glass? 402 00:17:35,520 --> 00:17:35,910 >> STUDENT: Ben. 403 00:17:35,910 --> 00:17:36,230 >> SPEAKER 1: Ben? 404 00:17:36,230 --> 00:17:38,380 OK, Ben, inti ser tkun l-ewwel, litteralment. 405 00:17:38,380 --> 00:17:40,580 Allura aħna qed tmur biex inti tibgħat sat-tmiem tal-istadju. 406 00:17:40,580 --> 00:17:41,670 Kull dritt, u l-isem tiegħek? 407 00:17:41,670 --> 00:17:41,990 >> STUDENT: Jason. 408 00:17:41,990 --> 00:17:44,530 >> SPEAKER 1: Jason, OK inti ser jkun in-numru disgħa. 409 00:17:44,530 --> 00:17:46,700 Mela jekk inti tixtieq li ssegwi Ben mod. 410 00:17:46,700 --> 00:17:47,010 >> STUDENT: Jill. 411 00:17:47,010 --> 00:17:49,630 >> SPEAKER 1: Jill, int ser tkun 17, li jekk I d ​​jsir dan aktar 412 00:17:49,630 --> 00:17:51,260 intelliġenti, I jkollhom bdiet fl-aħħar oħra. 413 00:17:51,260 --> 00:17:52,370 Inti tmur il-mod. 414 00:17:52,370 --> 00:17:53,030 22. 415 00:17:53,030 --> 00:17:53,670 U inti? 416 00:17:53,670 --> 00:17:53,980 >> STUDENT: Mary. 417 00:17:53,980 --> 00:17:56,130 >> SPEAKER 1: Mary, inti ser tkun ta '22. 418 00:17:56,130 --> 00:17:58,420 U l-isem tiegħek huwa? 419 00:17:58,420 --> 00:17:58,810 >> STUDENT: Chris. 420 00:17:58,810 --> 00:18:00,100 >> SPEAKER 1: Chris, inti ser tkun 26. 421 00:18:00,100 --> 00:18:00,740 U mbagħad fl-aħħar. 422 00:18:00,740 --> 00:18:01,400 >> STUDENT: Diana. 423 00:18:01,400 --> 00:18:02,670 >> SPEAKER 1: Diana, inti ser tkun 34. 424 00:18:02,670 --> 00:18:03,920 Allura inti come fuq matul hawn. 425 00:18:03,920 --> 00:18:06,360 >> Kull dritt, hekk perfetta magħżula tordna diġà. 426 00:18:06,360 --> 00:18:09,600 U ejja imorru quddiem u tagħmel dan sabiex inkunu nistgħu verament - 427 00:18:09,600 --> 00:18:11,720 Ben int biss tip ta 'tħares barra fil mkien hemmhekk. 428 00:18:11,720 --> 00:18:15,670 OK, so ejja imorru quddiem u juru dan użu l-armi, simili ħafna I kien, eżattament, 429 00:18:15,670 --> 00:18:16,250 x'inhu għaddej. 430 00:18:16,250 --> 00:18:19,540 Allura aqbad u jagħtu yourselves a sieq jew tnejn bejn yourselves. 431 00:18:19,540 --> 00:18:22,900 U jimxi 'l quddiem u l-punt b'id waħda biex min inti għandek tkun tipponta lejn 432 00:18:22,900 --> 00:18:23,470 ibbażata fuq dan. 433 00:18:23,470 --> 00:18:25,890 U jekk int null biss il-punt straight isfel sa l-art. 434 00:18:25,890 --> 00:18:27,690 OK, hekk tajjeb. 435 00:18:27,690 --> 00:18:32,290 >> Allura issa għandna lista marbuta, u let me jipproponi li jien ser jkollhom rwol ta ' 436 00:18:32,290 --> 00:18:35,110 PTR, so I mhux se jolqot jġorru dan madwar. 437 00:18:35,110 --> 00:18:37,830 U mbagħad - konvenzjoni stupid xi ħadd - inti tista 'sejħa dan xi ħaġa li trid - 438 00:18:37,830 --> 00:18:39,800 predeċessur pointer, pointer Pred - 439 00:18:39,800 --> 00:18:43,930 huwa biss l-laqam aħna taw fl kodiċi kampjun tagħna biex naħa tax-xellug tiegħi. 440 00:18:43,930 --> 00:18:47,240 Naħa l-oħra li se tkun żamma kont ta 'min huwa min fil- 441 00:18:47,240 --> 00:18:48,400 wara xenarji. 442 00:18:48,400 --> 00:18:52,390 >> Allura suppose, l-ewwel, nixtieq li ġewwieni off li l-ewwel eżempju ta 'ddaħħal, jgħidu 443 00:18:52,390 --> 00:18:54,330 20, fil-lista. 444 00:18:54,330 --> 00:18:57,160 Hekk jien ser bżonn xi ħadd li titlaħħam in-numru 20 għalina. 445 00:18:57,160 --> 00:18:58,950 So I bżonn xi ħadd malloc mill-udjenza. 446 00:18:58,950 --> 00:18:59,380 Come fuq up. 447 00:18:59,380 --> 00:19:00,340 X'hemm isem tiegħek? 448 00:19:00,340 --> 00:19:01,300 >> STUDENT: Brian. 449 00:19:01,300 --> 00:19:05,270 >> SPEAKER 1: Brian, id-dritt, sabiex inti għandu jkun l-node li jkun fiha 20. 450 00:19:05,270 --> 00:19:06,810 Kull dritt, come fuq matul hawn. 451 00:19:06,810 --> 00:19:10,025 U ovvjament, fejn ma Brian jappartjenu? 452 00:19:10,025 --> 00:19:12,190 Għalhekk, fin-nofs ta '- fil-fatt, stenna minuta. 453 00:19:12,190 --> 00:19:13,420 Aħna qed tagħmel dan out of order. 454 00:19:13,420 --> 00:19:17,170 Aħna qed jagħmlu dan ħafna aktar diffiċli milli jeħtieġ li jkun fl-ewwel. 455 00:19:17,170 --> 00:19:21,210 OK, aħna qed tmur biex ħielsa Brian u realloc Brian bħala ħamsa. 456 00:19:21,210 --> 00:19:23,680 >> OK, hekk issa irridu li daħħal Brian bħala ħamsa. 457 00:19:23,680 --> 00:19:25,960 Allura ġejjin fuq matul hawn jmiss Ben għal ftit mument. 458 00:19:25,960 --> 00:19:28,250 U inti tista 'tgħid preżumibbilment fejn din l-istorja huwa għaddej. 459 00:19:28,250 --> 00:19:30,500 Imma ejja jaħseb sew dwar l-ordni ta 'operazzjonijiet. 460 00:19:30,500 --> 00:19:32,880 U huwa preċiżament dan viżwali li għaddej biex line up 461 00:19:32,880 --> 00:19:34,080 ma dan il-kodiċi tal-kampjun. 462 00:19:34,080 --> 00:19:40,120 So here I PTR tipponta inizjalment mhux fil Ben, per se, iżda fi kwalunkwe 463 00:19:40,120 --> 00:19:43,245 valur huwa fih, li f'dan il-każ hu - dak l-isem tiegħek mill-ġdid? 464 00:19:43,245 --> 00:19:43,670 >> STUDENT: Jason. 465 00:19:43,670 --> 00:19:47,350 >> SPEAKER 1: Jason, hekk kemm Ben u I huma tipponta lejn Jason f'dan il-mument. 466 00:19:47,350 --> 00:19:49,700 Allura issa għandi biex jiddeterminaw, fejn ma Brian jappartjenu? 467 00:19:49,700 --> 00:19:53,500 Allura l-unika ħaġa I jkollhom aċċess għal dritt issa huwa tiegħu partita data n. 468 00:19:53,500 --> 00:19:58,280 Hekk jien ser jiċċekkja, huwa Brian inqas minn Jason? 469 00:19:58,280 --> 00:19:59,770 It-tweġiba hija veru. 470 00:19:59,770 --> 00:20:03,680 >> Allura dak li issa jeħtieġ li jiġri, fl-ordni korretta? 471 00:20:03,680 --> 00:20:07,120 I bżonn jaġġornaw kemm pointers b'kollox f'din l-istorja? 472 00:20:07,120 --> 00:20:10,720 Fejn naħa tiegħi għadu tipponta lejn Jason, u l-idejn tiegħek - jekk inti tixtieq li 473 00:20:10,720 --> 00:20:12,930 idek simili, tip ta ', I ma jafux, kwistjoni mark. 474 00:20:12,930 --> 00:20:14,070 OK, tajba. 475 00:20:14,070 --> 00:20:15,670 >> Kull dritt, hekk ikollok xi kandidati ftit. 476 00:20:15,670 --> 00:20:20,500 Jew Ben jew I jew Brian jew Jason jew kulħadd, li 477 00:20:20,500 --> 00:20:21,370 pointers bżonn għall-bidla? 478 00:20:21,370 --> 00:20:23,260 Kemm b'kollox? 479 00:20:23,260 --> 00:20:24,080 >> OK, hekk tnejn. 480 00:20:24,080 --> 00:20:27,090 Pointer My ma verament kwistjoni jibqgħalu għaliex jien biss temporanju. 481 00:20:27,090 --> 00:20:31,370 Allura huwa dawn iż-żewġ guys, preżumibbilment, kemm Ben u Brian. 482 00:20:31,370 --> 00:20:34,410 So let me tipproponi li aħna aġġornament Ben, peress li huwa l-ewwel. 483 00:20:34,410 --> 00:20:36,350 L-ewwel element ta 'din il-lista issa se tkun Brian. 484 00:20:36,350 --> 00:20:38,070 Allura punt Ben fuq Brian. 485 00:20:38,070 --> 00:20:39,320 OK, issa liema? 486 00:20:39,320 --> 00:20:41,950 487 00:20:41,950 --> 00:20:43,460 >> Min gets mfakkar fil min? 488 00:20:43,460 --> 00:20:44,710 >> STUDENT: [inaudible]. 489 00:20:44,710 --> 00:20:46,180 >> SPEAKER 1: OK hekk Brian għandha jindikaw lejn Jason. 490 00:20:46,180 --> 00:20:48,360 Imma I tilfu rekord ta 'dak pointer? 491 00:20:48,360 --> 00:20:49,980 Inkun naf fejn Jason hu? 492 00:20:49,980 --> 00:20:50,790 >> STUDENT: [inaudible]. 493 00:20:50,790 --> 00:20:52,620 >> SPEAKER 1: I do, peress li jien il-pointer temporanju. 494 00:20:52,620 --> 00:20:55,110 U preżumibbilment, I ma nbidlux għall-punt fil-node ġdid. 495 00:20:55,110 --> 00:20:58,300 Allura nistgħu sempliċiment punt Brian fil min jien tipponta lejn. 496 00:20:58,300 --> 00:20:59,000 U aħna qed isir. 497 00:20:59,000 --> 00:21:01,890 Allura f'każ wieħed, inserzjoni fil- bidu tal-lista. 498 00:21:01,890 --> 00:21:02,950 Kien hemm żewġ passi. 499 00:21:02,950 --> 00:21:06,750 Wieħed, għandna biex jaġġornaw Ben, u mbagħad irridu wkoll biex taġġorna Brian. 500 00:21:06,750 --> 00:21:09,230 U allura jien ma għandekx li jolqot traipsing permezz tal-bqija tal- 501 00:21:09,230 --> 00:21:12,680 lista, għaliex aħna diġà sabet tiegħu post, minħabba li jappartjeni lill- 502 00:21:12,680 --> 00:21:14,080 xellug tal-ewwel element. 503 00:21:14,080 --> 00:21:15,400 >> Kull dritt, hekk pjuttost sempliċi. 504 00:21:15,400 --> 00:21:18,110 Fil-fatt, iħoss bħal aħna qed kważi jagħmlu dan wisq ikkumplikat. 505 00:21:18,110 --> 00:21:20,240 Mela ejja issa ġewwieni off-aħħar tal-lista, u ara fejn 506 00:21:20,240 --> 00:21:21,380 il-kumplessità jibda. 507 00:21:21,380 --> 00:21:24,560 Mela jekk issa, I alloc mill-udjenza. 508 00:21:24,560 --> 00:21:25,540 Kull min jixtiequ li jilagħbu 55? 509 00:21:25,540 --> 00:21:26,700 Kull dritt, I raw idejn tiegħek l-ewwel. 510 00:21:26,700 --> 00:21:29,620 Come fuq up. 511 00:21:29,620 --> 00:21:30,030 Yeah. 512 00:21:30,030 --> 00:21:31,177 X'hemm isem tiegħek? 513 00:21:31,177 --> 00:21:32,310 >> STUDENT: [inaudible]. 514 00:21:32,310 --> 00:21:33,240 >> SPEAKER 1: Habata. 515 00:21:33,240 --> 00:21:33,890 OK, come fuq up. 516 00:21:33,890 --> 00:21:35,730 Int ser tkun in-numru 55. 517 00:21:35,730 --> 00:21:37,820 Allura inti, naturalment, jappartjenu fl-aħħar tal-lista. 518 00:21:37,820 --> 00:21:41,850 Mela ejja replay-simulazzjoni miegħi huwa l-PTR għal ftit mument. 519 00:21:41,850 --> 00:21:44,050 Hekk jien ser ewwel punt fuq kwalunkwe Ben tipponta lejn. 520 00:21:44,050 --> 00:21:45,900 Aħna kemm tipponta issa fil Brian. 521 00:21:45,900 --> 00:21:48,420 Allura 55 ma jkunx inqas minn ħamsa. 522 00:21:48,420 --> 00:21:52,510 Hekk jien ser taġġorna myself mill tipponta lejn pointer li jmiss Brian, li 523 00:21:52,510 --> 00:21:54,450 issa huwa ta 'kors Jason. 524 00:21:54,450 --> 00:21:57,310 55 ma jkunx inqas minn disa ', sabiex Jien ser taġġorna PTR. 525 00:21:57,310 --> 00:21:58,890 Jien ser taġġorna PTR. 526 00:21:58,890 --> 00:22:02,290 Jien ser taġġorna PTR I ser taġġorna PTR. 527 00:22:02,290 --> 00:22:05,060 U jien ser - hmm, x'hemm isem tiegħek mill-ġdid? 528 00:22:05,060 --> 00:22:05,560 >> STUDENT: Diana. 529 00:22:05,560 --> 00:22:09,190 >> SPEAKER 1: Diana hija li tipponta, naturalment, fil null mal-xellug tagħha. 530 00:22:09,190 --> 00:22:13,030 Għalhekk, fejn ma Habata attwalment jappartjenu b'mod ċar? 531 00:22:13,030 --> 00:22:15,050 Biex ix-xellug, hawnhekk. 532 00:22:15,050 --> 00:22:19,460 Allura kif inkun naf li jitqiegħdu tagħha Here I think stajt invitat up. 533 00:22:19,460 --> 00:22:22,420 Għaliex dak li hu PTR art dan il-mument fil-ħin? 534 00:22:22,420 --> 00:22:23,240 Null. 535 00:22:23,240 --> 00:22:25,580 Allura anke jekk, viżwalment, nistgħu ovvjament tara kollha ta 'dawn 536 00:22:25,580 --> 00:22:26,610 guys hawn fuq il-palk. 537 00:22:26,610 --> 00:22:29,680 Stajt ma żammitx rekord ta 'qabel persuna fil-lista. 538 00:22:29,680 --> 00:22:33,210 I ma jkollhom finger tipponta out, f'dan il-każ, in-numru node 34. 539 00:22:33,210 --> 00:22:34,760 >> Mela ejja attwalment jibdew dan fuq. 540 00:22:34,760 --> 00:22:37,560 Allura issa I attwalment do bżonn varjabbli lokali tieni. 541 00:22:37,560 --> 00:22:40,980 U dan huwa dak li inti ser tara fil- kampjun kodiċi attwali C, fejn kif mmur, 542 00:22:40,980 --> 00:22:45,860 meta I taġġorna lemin tiegħi għall-punt Jason, b'hekk tħalli Brian lura, I 543 00:22:45,860 --> 00:22:51,440 aħjar tibda tuża naħa tax-xellug tiegħi biex jaġġornaw fejn I kien, tant li bħala mmur 544 00:22:51,440 --> 00:22:52,700 permezz din il-lista - 545 00:22:52,700 --> 00:22:55,040 aktar awkwardly minn I maħsuba issa hawn viżwalment - 546 00:22:55,040 --> 00:22:56,740 Jien ser tikseb l- aħħar tal-lista. 547 00:22:56,740 --> 00:23:00,020 >> Dan idejn għadu null, li huwa pjuttost inutli, jekk mhux biex tindika 548 00:23:00,020 --> 00:23:02,980 Jien b'mod ċar fl-aħħar tal-lista, iżda issa mill-inqas I jkollhom din 549 00:23:02,980 --> 00:23:08,270 predeċessur pointer tipponta hawn, so issa dak idejn u dak pointers bżonn 550 00:23:08,270 --> 00:23:10,150 li jiġu aġġornati? 551 00:23:10,150 --> 00:23:13,214 Li naħa tridu jikkonfiguraw mill-ewwel? 552 00:23:13,214 --> 00:23:15,190 >> STUDENT: [inaudible]. 553 00:23:15,190 --> 00:23:16,220 >> SPEAKER 1: OK, so tal Diana. 554 00:23:16,220 --> 00:23:21,110 Fejn tridu punt Pointer xellug Diana fi? 555 00:23:21,110 --> 00:23:23,620 Fil-55, preżumibbilment, b'tali mod li konna jiddaħħal hemmhekk. 556 00:23:23,620 --> 00:23:25,560 U fejn għandhom 55 pointer tmur? 557 00:23:25,560 --> 00:23:27,000 Down, li jirrappreżentaw null. 558 00:23:27,000 --> 00:23:28,890 U l-idejn tiegħi, f'dan il-punt, ma jimpurtax għax kienu biss 559 00:23:28,890 --> 00:23:30,070 varjabbli temporanji. 560 00:23:30,070 --> 00:23:31,030 Allura issa aħna qed isir. 561 00:23:31,030 --> 00:23:34,650 >> Allura l-kumplessità addizzjonali hemmhekk - u mhuwiex li diffiċli biex tiġi implimentata, 562 00:23:34,650 --> 00:23:38,660 imma għandna bżonn varjabbli sekondarji li jagħmlu żgur li qabel I jiċċaqalqu lemin tiegħi 563 00:23:38,660 --> 00:23:42,140 idejn, I taġġorna l-valur tal tax-xellug tiegħi idejn, pointer Pred f'dan il-każ, hekk 564 00:23:42,140 --> 00:23:45,860 li għandi pointer batuta li jżommu rekord ta 'fejn I kien. 565 00:23:45,860 --> 00:23:49,360 Issa bħala aside, jekk inti qed jaħsbu dan permezz, dan iħoss bħal din hija 566 00:23:49,360 --> 00:23:51,490 ftit annoying li jkollhom biex iżommu track ta 'din id ix-xellugija. 567 00:23:51,490 --> 00:23:54,015 >> X'għandu soluzzjoni oħra li din il-problema kienu? 568 00:23:54,015 --> 00:23:56,500 Jekk inti ltqajna biex disinn mill-ġdid l-informazzjoni istruttura aħna qed jitkellem 569 00:23:56,500 --> 00:23:59,630 permezz dritt issa? 570 00:23:59,630 --> 00:24:02,690 Jekk dan it-tip biss ta iħoss ftit annoying li jkollhom, bħal, żewġ pointers 571 00:24:02,690 --> 00:24:08,430 għaddejjin mill-lista, li inkella jista ' jkunu, f'dinja ideali, miżmuma 572 00:24:08,430 --> 00:24:10,160 informazzjoni li għandna bżonn? 573 00:24:10,160 --> 00:24:11,360 Yeah? 574 00:24:11,360 --> 00:24:12,610 >> STUDENT: [inaudible]. 575 00:24:12,610 --> 00:24:15,160 576 00:24:15,160 --> 00:24:16,150 >> SPEAKER 1: Eżattament. 577 00:24:16,150 --> 00:24:19,130 Dritt hekk hemm attwalment interessanti nibbieta ta 'idea. 578 00:24:19,130 --> 00:24:22,470 U din l-idea ta 'pointer preċedenti, tipponta lejn l-element ta 'qabel. 579 00:24:22,470 --> 00:24:25,580 X'jiġri jekk I biss inkorporati li ġewwa tal-lista nfisha? 580 00:24:25,580 --> 00:24:27,810 U li għaddej biex tkun diffiċli biex Ħares dan mingħajr il-karta 581 00:24:27,810 --> 00:24:28,830 jaqgħu l-art. 582 00:24:28,830 --> 00:24:31,860 Iżda jissoponi li dawn guys użat kemm ta 'l-idejn tagħhom li jkollhom preċedenti 583 00:24:31,860 --> 00:24:35,950 pointer, u werrej li jmiss, u b'hekk implimentazzjoni dak li aħna inneħħu sejħa doppjament 584 00:24:35,950 --> 00:24:36,830 lista marbuta. 585 00:24:36,830 --> 00:24:41,090 Dan jippermetti me biex issolvi ta kontrina, ħafna aktar faċilment mingħajr me, il- 586 00:24:41,090 --> 00:24:43,800 programmer, li jżommu track manwalment - 587 00:24:43,800 --> 00:24:44,980 verament manwalment - 588 00:24:44,980 --> 00:24:47,280 ta 'fejn I kien qabel fil-lista. 589 00:24:47,280 --> 00:24:48,110 Allura aħna mhux se tagħmel dan. 590 00:24:48,110 --> 00:24:50,950 Aħna ser jżommha sempliċi minħabba li l se jaqgħu fil-prezz, darbtejn 591 00:24:50,950 --> 00:24:53,450 ħafna spazju għall-pointers, jekk inti tixtieq tieni waħda. 592 00:24:53,450 --> 00:24:55,760 Imma dak li tassew komuni struttura tad-data magħrufa bħala 593 00:24:55,760 --> 00:24:57,410 doppjament marbuta lista. 594 00:24:57,410 --> 00:25:01,310 >> Ejja nagħmlu l-eżempju finali hawn u mqiegħda dawn guys 'miżerja tagħhom. 595 00:25:01,310 --> 00:25:03,270 Allura malloc 20. 596 00:25:03,270 --> 00:25:05,320 Come fuq up mill-aisle hemm. 597 00:25:05,320 --> 00:25:06,280 Kull dritt, x'hemm isem tiegħek? 598 00:25:06,280 --> 00:25:07,440 >> STUDENT: [inaudible]. 599 00:25:07,440 --> 00:25:07,855 >> SPEAKER 1: Jiddispjacini? 600 00:25:07,855 --> 00:25:08,480 >> STUDENT: [inaudible]. 601 00:25:08,480 --> 00:25:09,410 >> SPEAKER 1: Demeron? 602 00:25:09,410 --> 00:25:10,230 OK come fuq up. 603 00:25:10,230 --> 00:25:11,910 You għandhom ikunu 20. 604 00:25:11,910 --> 00:25:14,720 Inti ovvjament tmur jappartjenu bejn 17 u 22. 605 00:25:14,720 --> 00:25:16,150 So let me jitgħallmu lezzjoni tiegħi. 606 00:25:16,150 --> 00:25:18,150 Jien ser tibda pointer tipponta lejn Brian. 607 00:25:18,150 --> 00:25:21,190 U jien ser ikollhom naħa tax-xellug tiegħi jaġġornaw biss Brian bħala I jiċċaqalqu lejn 608 00:25:21,190 --> 00:25:23,600 Jason, verifika ma 20 inqas minn disa? 609 00:25:23,600 --> 00:25:24,060 No 610 00:25:24,060 --> 00:25:25,430 Hija 20 inqas minn 17? 611 00:25:25,430 --> 00:25:25,880 No 612 00:25:25,880 --> 00:25:27,450 Huwa inqas minn 20 22? 613 00:25:27,450 --> 00:25:28,440 Iva. 614 00:25:28,440 --> 00:25:34,070 Allura dak pointers jew idejn bżonn għall-bidla fejn dawn qed tipponta issa? 615 00:25:34,070 --> 00:25:37,070 >> Allura nistgħu nagħmlu 17 tipponta lejn 20. 616 00:25:37,070 --> 00:25:37,860 Allura li l-multa. 617 00:25:37,860 --> 00:25:40,080 Fejn irridu punt pointer tiegħek issa? 618 00:25:40,080 --> 00:25:41,330 Fuq 22. 619 00:25:41,330 --> 00:25:45,410 U nafu fejn 22 hija, għal darb'oħra grazzi biex pointer temporanju tiegħi. 620 00:25:45,410 --> 00:25:46,760 Allura aħna qed OK hemmhekk. 621 00:25:46,760 --> 00:25:49,440 Allura minħabba din il-ħażna temporanja Stajt jinżammu kont ta 'fejn kulħadd huwa. 622 00:25:49,440 --> 00:25:55,055 U issa inti tista 'viżwalment tmur fis fejn inti jappartjenu, u issa għandna bżonn 1, 2, 3, 623 00:25:55,055 --> 00:25:58,410 4, 5, 6, 7, 8, 9 blalen stress, u rawnd ta 'applause għall 624 00:25:58,410 --> 00:25:59,770 dawn guys, jekk nistgħu. 625 00:25:59,770 --> 00:26:00,410 Nicely jsir. 626 00:26:00,410 --> 00:26:05,320 >> [Applause] 627 00:26:05,320 --> 00:26:06,330 >> SPEAKER 1: Id-dritt. 628 00:26:06,330 --> 00:26:09,860 U inti tista 'żżomm il-biċċiet ta 'karta kif mementos. 629 00:26:09,860 --> 00:26:15,930 >> Kull dritt, hekk, trust me huwa ħafna aktar faċli biex jimxu permezz li ma 630 00:26:15,930 --> 00:26:17,680 bnedmin milli huwa bil-kodiċi attwali. 631 00:26:17,680 --> 00:26:22,690 Imma dak li inti ser issib fi ftit mument issa, huwa l-istess - oh, nirringrazzjak. 632 00:26:22,690 --> 00:26:23,630 Grazzi - 633 00:26:23,630 --> 00:26:29,360 hija li inti ser issib li l-istess data istruttura, il-lista marbuta, jistgħu attwalment 634 00:26:29,360 --> 00:26:33,200 jintuża bħala element fil-bini biex saħansitra aktar strutturi ta 'dejta sofistikati. 635 00:26:33,200 --> 00:26:37,620 >> U jirrealizzaw wisq it-tema hawnhekk hija li konna assolutament introdotti aktar 636 00:26:37,620 --> 00:26:40,060 kumplessità fl-implimentazzjoni ta 'dan algoritmu. 637 00:26:40,060 --> 00:26:43,940 Inserzjoni, u jekk aħna marru permezz tagħha, tħassir u tiftix, huwa xi ftit 638 00:26:43,940 --> 00:26:46,660 aktar ikkumplikata milli kien ma 'firxa. 639 00:26:46,660 --> 00:26:48,040 Iżda aħna jiksbu xi dinamiżmu. 640 00:26:48,040 --> 00:26:50,180 Nikbru struttura data adattivi. 641 00:26:50,180 --> 00:26:54,010 >> Iżda għal darb'oħra, li nħallsu prezz ta 'wara xi kumplessità addizzjonali, kemm fl- 642 00:26:54,010 --> 00:26:54,910 implimentazzjoni tiegħu. 643 00:26:54,910 --> 00:26:56,750 U aħna qed jingħataw l-aċċess bl-addoċċ. 644 00:26:56,750 --> 00:27:00,450 U biex ikunu onesti, hemm mhux xi sbieħ nadif slide I jistgħu jagħtuk li 645 00:27:00,450 --> 00:27:03,120 jgħid hawnhekk huwa għaliex lista marbuta huwa aħjar minn firxa. 646 00:27:03,120 --> 00:27:04,100 U jitilqu minnu f'dik. 647 00:27:04,100 --> 00:27:07,520 Minħabba li l-tema reoccurring issa, anke iktar hekk fil-ġimgħat li ġejjin, huwa 648 00:27:07,520 --> 00:27:10,200 li hemm mhux neċessarjament risposta korretta. 649 00:27:10,200 --> 00:27:13,830 >> Dan huwa għaliex għandna l-assi separata ta 'disinn għal settijiet problema. 650 00:27:13,830 --> 00:27:17,700 Dan se jkun ferm kuntest sensittivi jekk inti tixtieq li tuża din id-data 651 00:27:17,700 --> 00:27:21,750 struttura jew li wieħed, u se jiddependu fuq liema materji lilek f'termini 652 00:27:21,750 --> 00:27:24,620 ta 'riżorsi u l-kumplessità. 653 00:27:24,620 --> 00:27:28,830 >> Iżda let me jipproponi li d-data ideali istruttura, l-Grail qaddis, ikun 654 00:27:28,830 --> 00:27:32,200 xi ħaġa li wasal iż-żmien kostanti, irrispettivament ta 'kemm għalf huwa 655 00:27:32,200 --> 00:27:36,940 ġewwa fih, ma kienx ikun aqwa jekk struttura tad-data lura tweġibiet fil- 656 00:27:36,940 --> 00:27:37,920 żmien kostanti. 657 00:27:37,920 --> 00:27:38,330 Iva. 658 00:27:38,330 --> 00:27:40,110 Din il-kelma hija fil enormi dizzjunarju tiegħek. 659 00:27:40,110 --> 00:27:41,550 Jew l-ebda, din il-kelma mhix. 660 00:27:41,550 --> 00:27:43,270 Jew kull problema simili hemmhekk. 661 00:27:43,270 --> 00:27:46,360 Well ejja ara jekk ma nistgħux inqas tieħu pass lejn dan. 662 00:27:46,360 --> 00:27:50,190 >> Let me tipproponi struttura ġdida data li jista 'jintuża għal affarijiet differenti, 663 00:27:50,190 --> 00:27:52,260 f'dan il-każ jissejjaħ tabella hash. 664 00:27:52,260 --> 00:27:55,590 U hekk aħna qed attwalment lura għall glancing fi array, f'dan il-każ, u 665 00:27:55,590 --> 00:28:00,550 kemmxejn arbitrarju, stajt mfassla dan tabella hash bħala firxa ma tip ta ' 666 00:28:00,550 --> 00:28:02,810 firxa żewġ dimensjonijiet - 667 00:28:02,810 --> 00:28:05,410 jew pjuttost huwa mpinġi hawn bħala żewġ firxa tridimensjonali - iżda dan huwa biss 668 00:28:05,410 --> 00:28:10,770 firxa ta 'daqs 26, b'tali mod li jekk aħna sejħa tal-mejda array, parentesi tabella 669 00:28:10,770 --> 00:28:12,440 żero hija l-rettangolu fil-quċċata. 670 00:28:12,440 --> 00:28:15,090 Bracket Tabella 25 hija l-rettangolu fil-qiegħ. 671 00:28:15,090 --> 00:28:18,620 U dan huwa kif I jista 'jiġbed data istruttura li nixtieq li jaħżen 672 00:28:18,620 --> 00:28:19,790 tan-nies ismijiet. 673 00:28:19,790 --> 00:28:24,370 >> Allura per eżempju, u jien mhux ser jiġbed l- ħaġa sħiħa hawn fuq il-overhead, jekk I 674 00:28:24,370 --> 00:28:29,160 kellha din array, li jien issa ser sejħa tabella hash, u dan huwa għal darb'oħra 675 00:28:29,160 --> 00:28:31,360 post żero. 676 00:28:31,360 --> 00:28:34,840 Dan hawnhekk huwa post waħda, u ibqa 'sejjer hekk. 677 00:28:34,840 --> 00:28:37,880 I jsostnu li nixtieq li jużaw din id-data istruttura, għall-fini ta 'diskussjoni, 678 00:28:37,880 --> 00:28:42,600 li jaħżen ismijiet tan-nies, Alice u Bob u Charlie u ismijiet oħra bħal dawn. 679 00:28:42,600 --> 00:28:46,110 Allura taħseb ta 'dan issa bħala l-bidu ta ', ngħidu aħna, dizzjunarju 680 00:28:46,110 --> 00:28:47,520 ma 'lottijiet ta' kliem. 681 00:28:47,520 --> 00:28:49,435 Ikunu jinzertaw ismijiet fl-eżempju tagħna hawn. 682 00:28:49,435 --> 00:28:52,560 U dan huwa wisq germane, forsi, li implimentazzjoni jespliċitaw kontrollur, kif aħna 683 00:28:52,560 --> 00:28:54,400 tista għal problema stabbiliti sitt. 684 00:28:54,400 --> 00:28:59,300 >> Hekk jekk għandna firxa ta 'daqs totali 26 għalhekk dan huwa l-post 25 685 00:28:59,300 --> 00:29:03,390 fil-qiegħ, u I jsostnu li Alice huwa l-ewwel kelma fid-dizzjunarju ta ' 686 00:29:03,390 --> 00:29:07,260 ismijiet li nixtieq li daħħal fis RAM, fis din l-istruttura tad-data, fejn huma 687 00:29:07,260 --> 00:29:12,480 instincts tghidlek li Alice isem għandhom imorru f'dan firxa? 688 00:29:12,480 --> 00:29:13,510 >> Għandna 26 għażliet. 689 00:29:13,510 --> 00:29:14,990 Fejn irridu jitqiegħdu tagħha? 690 00:29:14,990 --> 00:29:16,200 Aħna tixtieq tagħha fil-bracket żero, id-dritt? 691 00:29:16,200 --> 00:29:18,280 A għall Alice, ejja sejħa li żero. 692 00:29:18,280 --> 00:29:20,110 U B se tkun waħda, u C se jkun tnejn. 693 00:29:20,110 --> 00:29:22,600 Allura aħna qed tmur biex jiktbu Isem Alice up here. 694 00:29:22,600 --> 00:29:24,890 Jekk aħna imbagħad daħħal Bob, tiegħu isem se jmorru hawn. 695 00:29:24,890 --> 00:29:27,280 Charlie se jmorru hawn. 696 00:29:27,280 --> 00:29:30,500 U oħrajn stabbiliti permezz din l-istruttura tad-data. 697 00:29:30,500 --> 00:29:32,090 >> Din hija struttura data wunderbare. 698 00:29:32,090 --> 00:29:32,730 Għaliex? 699 00:29:32,730 --> 00:29:37,460 Ukoll dak huwa l-ħin tmexxija ta ' ddaħħal l-isem ta 'bniedem fis dan 700 00:29:37,460 --> 00:29:39,850 data istruttura dritt issa? 701 00:29:39,850 --> 00:29:43,702 Peress li din it-tabella tiġi implimentata, verament, bħala firxa. 702 00:29:43,702 --> 00:29:44,940 Ukoll huwa żmien kostanti. 703 00:29:44,940 --> 00:29:45,800 Huwa ordni ta 'wieħed. 704 00:29:45,800 --> 00:29:46,360 Għaliex? 705 00:29:46,360 --> 00:29:48,630 >> Well kif taħseb li jiddeterminaw fejn Alice jappartjeni? 706 00:29:48,630 --> 00:29:51,000 Inti tħares lejn liema ittra ta 'isem tagħha? 707 00:29:51,000 --> 00:29:51,490 L-ewwel. 708 00:29:51,490 --> 00:29:54,350 U inti tista 'tikseb hemm, jekk huwa string, billi biss tħares lejn string 709 00:29:54,350 --> 00:29:55,200 bracket żero. 710 00:29:55,200 --> 00:29:57,110 Allura l-karattru 0 tas-sekwenza. 711 00:29:57,110 --> 00:29:57,610 Li faċli. 712 00:29:57,610 --> 00:30:00,350 Aħna ma li fil-kripto ġimgħat ilu assenjazzjoni. 713 00:30:00,350 --> 00:30:05,310 U allura ladarba inti taf li l-Alice ittra huwa l-kapital A, nistgħu naqqas 714 00:30:05,310 --> 00:30:08,160 off 65 jew kapital A innifsu, li jagħtina żero. 715 00:30:08,160 --> 00:30:10,940 Allura aħna issa jkunu jafu li Alice jappartjeni fil-post żero. 716 00:30:10,940 --> 00:30:14,240 >> U jingħataw pointer li din id-data istruttura, ta 'xi tip, kemm ma 717 00:30:14,240 --> 00:30:18,840 jieħdu me biex isibu post żero fil-firxa? 718 00:30:18,840 --> 00:30:22,080 Just pass wieħed, dritt Wasal iż-żmien kostanti minħabba l-aċċess bl-addoċċ aħna 719 00:30:22,080 --> 00:30:23,780 proposta kienet karatteristika ta 'firxa. 720 00:30:23,780 --> 00:30:28,570 Għalhekk fil-qosor, jidhru dak l-indiċi ta 'isem Alice huwa, li huwa, fil- 721 00:30:28,570 --> 00:30:32,610 F'dan il-każ, huwa A, jew ejja biss issolvi li għal żero, fejn B hija waħda u C hija 722 00:30:32,610 --> 00:30:34,900 tnejn, jidhru li minn huwa żmien kostanti. 723 00:30:34,900 --> 00:30:38,510 I sempliċiment għandek tfittex fl-ewwel ittra tagħha, jidhru fl fejn żero huwa 724 00:30:38,510 --> 00:30:40,460 array huwa wkoll żmien kostanti. 725 00:30:40,460 --> 00:30:42,140 Allura teknikament li l- bħal żewġ passi issa. 726 00:30:42,140 --> 00:30:43,330 Imma dak li għadu kostanti. 727 00:30:43,330 --> 00:30:46,880 Allura aħna sejħa li O kbir ta 'wieħed, hekk aħna ħadthom mdaħħal Alice fis din it-tabella fl 728 00:30:46,880 --> 00:30:48,440 żmien kostanti. 729 00:30:48,440 --> 00:30:50,960 >> Iżda naturalment, jien qed naive hawn, id-dritt? 730 00:30:50,960 --> 00:30:53,240 X'jiġri jekk hemm xi Aaron fil-klassi? 731 00:30:53,240 --> 00:30:53,990 Jew Alicia? 732 00:30:53,990 --> 00:30:57,230 Jew xi ismijiet oħra li tibda bil A. Fejn huma aħna se tpoġġi 733 00:30:57,230 --> 00:31:00,800 dik il-persuna, id-dritt? 734 00:31:00,800 --> 00:31:03,420 I mean, id-dritt issa hemm biss tlieta nies fuq il-mejda, hekk forsi aħna 735 00:31:03,420 --> 00:31:07,490 għandhom ipoġġu Aaron fuq post zero wieħed tnejn tlieta. 736 00:31:07,490 --> 00:31:09,480 >> Dritt, I tista 'tpoġġi A hawn. 737 00:31:09,480 --> 00:31:13,350 Iżda mbagħad, jekk nippruvaw li daħħal fis David din il-lista, fejn ma David imorru? 738 00:31:13,350 --> 00:31:15,170 Issa sistema tagħna jibda tkissir isfel, id-dritt? 739 00:31:15,170 --> 00:31:19,210 Minħabba li issa David jispiċċa here jekk Aaron huwa attwalment hawn. 740 00:31:19,210 --> 00:31:23,060 U hekk issa din l-idea kollu li jkun hemm struttura tad-data nadif li jagħtina 741 00:31:23,060 --> 00:31:28,010 inserzjonijiet ħin kostanti m'għadux ħin kostanti, minħabba I jkollhom 742 00:31:28,010 --> 00:31:31,240 jivverifikaw, oh, damnit, xi ħadd li diġà fil-post Alice. 743 00:31:31,240 --> 00:31:35,320 >> Let me sonda il-bqija ta 'din id-data istruttura, tfittex għal post biex 744 00:31:35,320 --> 00:31:37,130 xi ħadd bħall-isem Aaron. 745 00:31:37,130 --> 00:31:39,390 U għalhekk li wisq qed tibda li tieħu ħin lineari. 746 00:31:39,390 --> 00:31:42,710 Barra minn hekk, jekk inti issa tixtieq li ssib l- Aaron f'din l-istruttura tad-data, u inti 747 00:31:42,710 --> 00:31:45,430 jivverifikaw, u l-isem Aaron mhix hawn. 748 00:31:45,430 --> 00:31:47,960 Idealment, inti biss jgħidu li Aaron mhux fl-istruttura tad-data. 749 00:31:47,960 --> 00:31:51,530 Imma jekk inti tagħmel tibda tagħmel spazju għall- Aaron fejn kellu jkun hemm a D 750 00:31:51,530 --> 00:31:55,600 jew E, inti, agħar każ, għandhom jiċċekkjaw l-istruttura tad-data sħiħ, 751 00:31:55,600 --> 00:31:59,480 f'liema każ jaqa 'xi ħaġa lineari fid-daqs tat-tabella. 752 00:31:59,480 --> 00:32:00,920 >> Allura kull dritt, jien ser jiffissaw dan. 753 00:32:00,920 --> 00:32:04,200 Il-problema hawn hija li kelli 26 Elementi f'dan array. 754 00:32:04,200 --> 00:32:05,000 Let me jibdlu. 755 00:32:05,000 --> 00:32:06,010 Whoops. 756 00:32:06,010 --> 00:32:10,600 Let me bidla hekk li pjuttost li jkunu ta ' daqs 26 b'kollox, avviż-qiegħ 757 00:32:10,600 --> 00:32:12,720 indiċi huwa se jibdlu għal n minus 1. 758 00:32:12,720 --> 00:32:16,610 Jekk 26 huwa ċertament limitat wisq għall-bnedmin " ismijiet, għaliex hemm eluf ta ' 759 00:32:16,610 --> 00:32:20,830 ismijiet tad-dinja, ejja biss tagħmel f'100 jew 1,000 jew 10,000. 760 00:32:20,830 --> 00:32:22,960 Ejja biss jallokaw spazju ħafna aktar. 761 00:32:22,960 --> 00:32:27,230 >> Ukoll li ma mhux neċessarjament jonqsu il-probabbiltà li aħna mhux se jkollhom żewġ 762 00:32:27,230 --> 00:32:31,510 nies bl-ismijiet li jibda bl A, u hekk, inti kienu se tipprova tpoġġi A 763 00:32:31,510 --> 00:32:33,120 ismijiet fuq post żero għadhom. 764 00:32:33,120 --> 00:32:36,850 Dawn għadhom qed tmur biex jikkonfliġġu, li ifisser għad għandna bżonn soluzzjoni biex 765 00:32:36,850 --> 00:32:41,020 Alice u Aaron u Alicia u oħrajn ismijiet li jibda bl A x'imkien ieħor. 766 00:32:41,020 --> 00:32:43,460 Imma kemm ta 'problema hija din? 767 00:32:43,460 --> 00:32:46,870 X'hemm-probabbiltà li inti jkollhom kolliżjonijiet f'sett ta 'data 768 00:32:46,870 --> 00:32:48,240 istruttura bħal din? 769 00:32:48,240 --> 00:32:52,570 >> Well, let me - aħna ser terga 'lura għal din id-domanda hawn. 770 00:32:52,570 --> 00:32:55,530 U ħarsa lejn kif nistgħu issolvi l-ewwel. 771 00:32:55,530 --> 00:32:58,480 Let me pull up din il-proposta hawn. 772 00:32:58,480 --> 00:33:02,020 Dak li aħna biss deskritt huwa algoritmu, a heuristic imsejjaħ lineari 773 00:33:02,020 --> 00:33:05,030 probing fejn, jekk inti ppruvaw daħħal xi ħaġa hawn f'dan data 774 00:33:05,030 --> 00:33:08,920 istruttura, li tissejjaħ tabella hash, u hemm ebda kamra hemm, inti 775 00:33:08,920 --> 00:33:12,000 verament sonda tal-istruttura tad-data verifika, hija din disponibbli? 776 00:33:12,000 --> 00:33:13,430 Huwa dan Disponibbli huwa dan disponibbli? 777 00:33:13,430 --> 00:33:13,980 Huwa dan disponibbli? 778 00:33:13,980 --> 00:33:17,550 U meta finalment huwa, inti daħħal il- isem li inti oriġinarjament maħsub 779 00:33:17,550 --> 00:33:19,370 x'imkien ieħor f'dak il-post. 780 00:33:19,370 --> 00:33:23,360 Iżda fl-agħar każ, l-uniku post jista 'jkun il-qiegħ ħafna tad-dejta 781 00:33:23,360 --> 00:33:25,090 istruttura, l-aħħar nett tal-firxa. 782 00:33:25,090 --> 00:33:30,130 >> Allura lineari probing, fl-agħar każ, jaqa 'fi algoritmu lineari fejn 783 00:33:30,130 --> 00:33:34,500 Aaron, jekk jiġri li jiddaħħal aħħar f'din l-istruttura tad-data, huwa jista 784 00:33:34,500 --> 00:33:39,540 jikkonfliġġu ma 'dan l-ewwel post, imma mbagħad jispiċċaw minn xortih ħażina fl-aħħar ħafna. 785 00:33:39,540 --> 00:33:43,940 Allura dan mhux kostanti żmien qaddis grail għalina. 786 00:33:43,940 --> 00:33:47,650 Dan l-approċċ ta 'elementi li jdaħħlu fis struttura data msejħa hash 787 00:33:47,650 --> 00:33:52,050 it-tabella ma jidhirx li jkun żmien kostanti inqas mhux fil-każ ġenerali. 788 00:33:52,050 --> 00:33:54,000 Hija tista jaqgħu fis xi ħaġa lineari. 789 00:33:54,000 --> 00:33:56,970 >> Allura dak jekk aħna isolvu kolliżjonijiet kemmxejn differenti? 790 00:33:56,970 --> 00:34:00,740 Allura hawnhekk aktar sofistikati approċċ għall x'hemm għadu 791 00:34:00,740 --> 00:34:02,800 imsejħa tabella hash. 792 00:34:02,800 --> 00:34:05,890 U billi hash, bħala twarrib, liema I medja hija l-indiċi li 793 00:34:05,890 --> 00:34:07,070 I imsemmi qabel. 794 00:34:07,070 --> 00:34:09,810 Għal xi ħaġa hash jistgħu jkunu meqjusa bħala verb. 795 00:34:09,810 --> 00:34:13,690 >> Mela jekk inti hash Alice l-isem, funzjoni hash, biex ngħidu hekk, 796 00:34:13,690 --> 00:34:14,710 għandhom imorru lura numru. 797 00:34:14,710 --> 00:34:18,199 F'dan il-każ huwa żero jekk hi jappartjeni fil post żero, wieħed jekk hi jappartjeni fil 798 00:34:18,199 --> 00:34:20,000 post wieħed, u oħrajn. 799 00:34:20,000 --> 00:34:24,360 Allura funzjoni hash tiegħi s'issa kien super sempliċi, tħares biss lejn l- 800 00:34:24,360 --> 00:34:26,159 ewwel ittra fl-isem ta 'xi ħadd. 801 00:34:26,159 --> 00:34:29,090 Iżda funzjoni hash jieħu bħala input xi biċċa ta 'data, ta' 802 00:34:29,090 --> 00:34:30,210 string, l-int, ikun x'ikun. 803 00:34:30,210 --> 00:34:32,239 U spits out numru tipikament. 804 00:34:32,239 --> 00:34:35,739 U dak in-numru huwa fejn dik id-data element jappartjeni fi struttura data 805 00:34:35,739 --> 00:34:37,800 magħrufa hawnhekk bħala tabella hash. 806 00:34:37,800 --> 00:34:41,400 >> Hekk biss intuwittivament, dan huwa kuntest kemmxejn differenti. 807 00:34:41,400 --> 00:34:44,170 Dan fil-fatt hija tirreferi għal eżempju jinvolvu għeluq, fejn 808 00:34:44,170 --> 00:34:46,850 jista 'jkun hemm kemm 31 jum fix-xahar. 809 00:34:46,850 --> 00:34:52,239 Imma dak li ma din il-persuna tiddeċiedi li jagħmlu fil-każ ta 'ħabta? 810 00:34:52,239 --> 00:34:55,304 Kuntest issa qed, mhux ħabta ta ' ismijiet, iżda ħabta ta 'għeluq is-snin, 811 00:34:55,304 --> 00:35:00,760 jekk żewġ persuni jkollhom l-istess birthday fuq -2 ta 'Ottubru, per eżempju. 812 00:35:00,760 --> 00:35:02,120 >> STUDENT: [inaudible]. 813 00:35:02,120 --> 00:35:05,010 >> SPEAKER 1: Yeah, hekk hawn għandna l-lieva ta 'listi marbuta. 814 00:35:05,010 --> 00:35:07,830 Allura jidher ftit differenti milli fassalna qabel. 815 00:35:07,830 --> 00:35:10,790 Iżda aħna jidhru li jkollhom firxa fuq in-naħa tax-xellug. 816 00:35:10,790 --> 00:35:13,230 C'est indiċi waħda, għall-ebda partikolari raġuni. 817 00:35:13,230 --> 00:35:14,630 Iżda huwa għadu firxa. 818 00:35:14,630 --> 00:35:16,160 Huwa ta 'firxa ta' indikaturi. 819 00:35:16,160 --> 00:35:20,670 U kull wieħed minn dawk l-elementi, kull wieħed dawn ċrieki jew slashes - l-mmejla 820 00:35:20,670 --> 00:35:23,970 jirrappreżenta null - kull wieħed minn dawn pointers li apparentament huwa tipponta lejn 821 00:35:23,970 --> 00:35:25,730 liema struttura tad-data? 822 00:35:25,730 --> 00:35:26,890 Lista marbuta. 823 00:35:26,890 --> 00:35:30,530 >> Allura issa għandna l-ħila li kodiċi hard fil-programm tagħna 824 00:35:30,530 --> 00:35:32,010 id-daqs tat-tabella. 825 00:35:32,010 --> 00:35:35,360 F'dan il-każ, nafu hemm qatt aktar minn 31 jum fix-xahar. 826 00:35:35,360 --> 00:35:38,480 Tant diffiċli kodifikazzjoni valur bħal 31 huwa raġonevoli f'dak il-kuntest. 827 00:35:38,480 --> 00:35:42,700 Fil-kuntest ta 'ismijiet, iebsa kodifikazzjoni 26 mhuwiex irraġonevoli huwa poplu 828 00:35:42,700 --> 00:35:46,340 ismijiet tibda biss ma ', pereżempju, l-alfabett li jinvolvi A permezz Z. 829 00:35:46,340 --> 00:35:50,180 >> Nistgħu CRAM lilhom kollha fis li d-data istruttura sakemm, meta irridu jiksbu 830 00:35:50,180 --> 00:35:55,330 kolliżjoni, aħna ma tpoġġi l-ismijiet hawn, aħna minflok jaħsbu dawn iċ-ċelluli 831 00:35:55,330 --> 00:36:00,270 mhux bħala kordi nfushom, iżda bħala pointers għal, per eżempju, Alice. 832 00:36:00,270 --> 00:36:03,660 U allura Alice tista 'jkollha pointer ieħor għal isem ieħor li tibda bil 833 00:36:03,660 --> 00:36:06,150 A. U Bob fatt tmur minn hawn. 834 00:36:06,150 --> 00:36:10,850 >> U jekk hemm isem ieħor li jibda ma B, huwa jispiċċa hawn fuq. 835 00:36:10,850 --> 00:36:15,070 U għalhekk kull wieħed mill-elementi ta 'din tabella tnejn, jekk aħna ddisinjati dan 836 00:36:15,070 --> 00:36:17,350 ftit aktar cleverly - 837 00:36:17,350 --> 00:36:18,125 come fuq - 838 00:36:18,125 --> 00:36:22,950 jekk aħna mfassla dan aktar ftit cleverly, issa isir data adattivi 839 00:36:22,950 --> 00:36:27,720 struttura, fejn hemm ebda limitu hard fuq kemm elementi tista 'daħħal 840 00:36:27,720 --> 00:36:30,700 fis dan għaliex jekk inti do jkollhom ħabta, li l-multa. 841 00:36:30,700 --> 00:36:34,690 Just jimxi 'l quddiem u tehmeż lill dak rajna daqsxejn ilu kien 842 00:36:34,690 --> 00:36:38,290 magħrufa bħala lista marbuta. 843 00:36:38,290 --> 00:36:39,690 >> Well ejja nieqaf għal ftit mument. 844 00:36:39,690 --> 00:36:42,570 X'inhu l-probabbiltà ta 'ħabta fl-ewwel post? 845 00:36:42,570 --> 00:36:45,480 Dritt, forsi jien fuq ħsieb, forsi Jien fuq inġinerija din il-problema, 846 00:36:45,480 --> 00:36:46,370 għaliex inti taf liema? 847 00:36:46,370 --> 00:36:49,070 Iva, I tista 'toħroġ bi arbitrarja eżempji off-quċċata tar-ras tiegħi bħal 848 00:36:49,070 --> 00:36:52,870 Allison u Aaron, iżda fir-realtà, mogħtija distribuzzjoni uniformi ta ' 849 00:36:52,870 --> 00:36:56,990 inputs, jiġifieri xi inserzjonijiet każwali fi struttura tad-data, dak li huwa verament 850 00:36:56,990 --> 00:36:58,580 il-probabbiltà ta 'ħabta? 851 00:36:58,580 --> 00:37:01,670 Ukoll jirriżulta, huwa attwalment super għolja. 852 00:37:01,670 --> 00:37:03,850 Let me jiġġeneralizza din problema hija kif dan. 853 00:37:03,850 --> 00:37:08,890 >> Allura fil-kamra ta 'n CS50 istudenti, x'hemm il-probabbiltà li mill-inqas 854 00:37:08,890 --> 00:37:11,010 żewġ studenti fil-kamra jkollhom l-istess birthday? 855 00:37:11,010 --> 00:37:13,346 Allura hemm dak. a hund ftit - 856 00:37:13,346 --> 00:37:16,790 200, 300 nies hawn u diversi mijiet ta 'nies fid-dar illum. 857 00:37:16,790 --> 00:37:20,670 Mela jekk int riedu li jistaqsu lilna nfusna x'hemm il-probabbiltà ta 'żewġ persuni 858 00:37:20,670 --> 00:37:23,930 f'din il-kamra li l-istess birthday, nistgħu figura dan. 859 00:37:23,930 --> 00:37:26,250 U nitlob attwalment hemm żewġ nies bl-istess birthday. 860 00:37:26,250 --> 00:37:29,560 >> Per eżempju, ħadd ma jkollhom birthday illum? 861 00:37:29,560 --> 00:37:31,340 Bieraħ? 862 00:37:31,340 --> 00:37:32,590 Għada? 863 00:37:32,590 --> 00:37:35,980 Kull dritt, hekk jħoss simili jien ser ikollhom jagħmlu dan 363 jew hekk aktar 864 00:37:35,980 --> 00:37:39,500 drabi biex attwalment insemmu jekk għandna ħabta. 865 00:37:39,500 --> 00:37:42,350 Jew nistgħu biss tagħmel dan matematikament minflok tediously 866 00:37:42,350 --> 00:37:43,200 tagħmel dan. 867 00:37:43,200 --> 00:37:44,500 U tipproponi dan li ġej. 868 00:37:44,500 --> 00:37:48,740 >> So nipproponi li nistgħu mudell l- probabbiltà ta 'żewġ persuni li jkollhom l- 869 00:37:48,740 --> 00:37:55,320 birthday istess bħall-probabbiltà ta '1 nieqes l-probabbiltà ta 'ebda wieħed li jkollu 870 00:37:55,320 --> 00:37:56,290 l-istess birthday. 871 00:37:56,290 --> 00:37:59,960 Allura biex tikseb dan, u dan huwa biss l- mod fancy ta 'din il-kitba, għall- 872 00:37:59,960 --> 00:38:03,090 ewwel persuna fil-kamra, hu jew hi jista 'jkollhom kwalunkwe waħda mill-possibbli 873 00:38:03,090 --> 00:38:07,370 għeluq ta 'snin jekk wieħed jassumi 365 jum fis-sena, ma apologies għal persuni 874 00:38:07,370 --> 00:38:08,760 il-birthday 29 Frar. 875 00:38:08,760 --> 00:38:13,470 >> Allura l-ewwel persuna f'din il-kamra huwa b'xejn li jkollha kwalunkwe numru ta 'għeluq ta' snin 876 00:38:13,470 --> 00:38:18,280 barra mill-365 possibiltajiet kollha sabiex aħna ser tagħmel dan 365 diviża 365, 877 00:38:18,280 --> 00:38:18,990 li hija waħda. 878 00:38:18,990 --> 00:38:22,700 Il-persuna li jmiss fil-kamra, jekk l-għan huwa biex tevita kolliżjoni, tista 'biss 879 00:38:22,700 --> 00:38:26,460 jkollhom birthday tiegħu jew tagħha dwar kif ħafna ġranet differenti possibbli? 880 00:38:26,460 --> 00:38:27,610 364. 881 00:38:27,610 --> 00:38:31,430 Allura it-tieni terminu fil din l-espressjoni hija tagħmel essenzjalment li matematika għalina 882 00:38:31,430 --> 00:38:33,460 billi jitnaqqas off jum wieħed possibbli. 883 00:38:33,460 --> 00:38:36,390 U allura l-jum li jmiss, il-jum li jmiss, il- jum li jmiss sa l-għadd totali 884 00:38:36,390 --> 00:38:38,100 ta 'nies fil-kamra. 885 00:38:38,100 --> 00:38:41,290 >> U jekk aħna mbagħad tikkunsidra, liema allura huwa il-probabbiltà mhux ta 'kulħadd li 886 00:38:41,290 --> 00:38:45,265 għeluq uniku, iżda għal darb'oħra 1 nieqes li, dak li nagħmlu huwa espressjoni 887 00:38:45,265 --> 00:38:47,810 li jistgħu ħafna fancifully teżamina bħal dan. 888 00:38:47,810 --> 00:38:50,330 Iżda huwa aktar interessanti li tħares lejn viżwalment. 889 00:38:50,330 --> 00:38:55,120 Din hija chart fejn fuq l-assi x hu in-numru ta 'nies fil-kamra, l- 890 00:38:55,120 --> 00:38:56,180 numru ta 'għeluq ta' snin. 891 00:38:56,180 --> 00:38:59,840 Fuq il-y-axis hija l-probabilità ta 'ħabta, żewġ persuni 892 00:38:59,840 --> 00:39:01,230 jkollhom l-istess birthday. 893 00:39:01,230 --> 00:39:05,020 >> U l-takeaway minn din il-kurva huwa li hekk kif ikollok biex simili 40 894 00:39:05,020 --> 00:39:11,110 istudenti, int up fuq probabbiltà 90% combinatorically ta 'żewġ 895 00:39:11,110 --> 00:39:13,550 persuni jew aktar li jkollhom l-istess birthday. 896 00:39:13,550 --> 00:39:18,600 U ladarba ikollok biex simili '58 persuni huwa kważi 100% ta 'opportunità it-tnejn 897 00:39:18,600 --> 00:39:21,310 nies fil-kamra huma se jkollhom l- birthday istess, għalkemm hemm 898 00:39:21,310 --> 00:39:26,650 365 jew 366 bramel possibbli, u biss 58 nies fil-kamra. 899 00:39:26,650 --> 00:39:29,900 Just statistikament int x'aktarx li tikseb kolliżjonijiet, li fil-qosor 900 00:39:29,900 --> 00:39:31,810 jimmotiva din id-diskussjoni. 901 00:39:31,810 --> 00:39:35,890 Li anke jekk irridu jiksbu fancy hawn, u tibda jkollhom dawn il-ktajjen, aħna qed għadhom 902 00:39:35,890 --> 00:39:36,950 ser ikollhom kolliżjonijiet. 903 00:39:36,950 --> 00:39:42,710 >> Allura li iqajjem il-kwistjoni, liema huwa l- ispiża biex tagħmel inserzjonijiet u tħassir 904 00:39:42,710 --> 00:39:44,850 fi struttura data bħal din? 905 00:39:44,850 --> 00:39:46,630 Well let me tipproponi - 906 00:39:46,630 --> 00:39:51,570 u let me jmorru lura għall-iskrin fuq hawn - jekk għandna n-elementi fil- 907 00:39:51,570 --> 00:39:56,330 lista, hekk jekk aħna qed tipprova daħħal Elementi n, u għandna 908 00:39:56,330 --> 00:39:58,050 kemm bramel totali? 909 00:39:58,050 --> 00:40:03,450 Ejja ngħidu 31 bramel totali fil-każ ta 'għeluq ta' snin. 910 00:40:03,450 --> 00:40:09,240 X'hemm-tul massimu ta ' ta 'dawn il-ktajjen potenzjalment? 911 00:40:09,240 --> 00:40:12,670 >> Jekk darb'oħra hemm 31 possibbli għeluq fi żmien xahar partikolari. 912 00:40:12,670 --> 00:40:14,580 U aħna qed biss tagħqid kulħadd - 913 00:40:14,580 --> 00:40:15,580 attwalment li huwa eżempju stupid. 914 00:40:15,580 --> 00:40:16,960 Ejja nagħmlu 26 minflok. 915 00:40:16,960 --> 00:40:20,890 Mela jekk fil-fatt ikollhom nies li isimhom tibda bil A permezz Z, biex b'hekk 916 00:40:20,890 --> 00:40:22,780 us 26 possibbiltajiet. 917 00:40:22,780 --> 00:40:25,920 U aħna qed tuża struttura tad-data bħal l-waħda aħna biss raw, fejn għandna 918 00:40:25,920 --> 00:40:30,210 firxa ta 'pointers, li kull wieħed minnhom jindika lista linked fejn il- 919 00:40:30,210 --> 00:40:32,360 ewwel lista hija kulħadd bl-isem Alice. 920 00:40:32,360 --> 00:40:35,770 It-tieni lista hija kull ma 'l- isem li tibda bil A, li jibda 921 00:40:35,770 --> 00:40:36,980 ma B, u oħrajn. 922 00:40:36,980 --> 00:40:41,020 >> X'hemm-tul probabbli ta 'kull dawn il-listi jekk nassumu nadif sbieħ 923 00:40:41,020 --> 00:40:45,410 distribuzzjoni ta 'ismijiet A sa Z madwar l-istruttura kollha tad-data? 924 00:40:45,410 --> 00:40:50,210 Hemm nies fl-istruttura n data diviż b'26, jekk dawn qed nicely 925 00:40:50,210 --> 00:40:52,110 mifruxa fuq il-sħiħ struttura tad-data. 926 00:40:52,110 --> 00:40:54,970 Allura l-tul ta 'kull wieħed minn dawn ktajjen huwa n diviż bil 26. 927 00:40:54,970 --> 00:40:57,380 Iżda fil notazzjoni O big, dak huwa li? 928 00:40:57,380 --> 00:41:00,100 929 00:41:00,100 --> 00:41:02,440 X'inhu li verament? 930 00:41:02,440 --> 00:41:04,150 Allura huwa verament ftit n, id-dritt? 931 00:41:04,150 --> 00:41:06,620 Għaliex aħna stajt qal fil-passat, li ugh inti iddividi 26. 932 00:41:06,620 --> 00:41:08,710 Iva, fir-realtà huwa aktar mgħaġġel. 933 00:41:08,710 --> 00:41:12,720 Iżda fit-teorija, mhuwiex fondamentalment dak kollu li aktar mgħaġġel. 934 00:41:12,720 --> 00:41:16,040 >> Allura aħna ma jidhirx li tkun kollha li ħafna eqreb lejn dan Grail qaddis. 935 00:41:16,040 --> 00:41:17,750 Fil-fatt, dan huwa biss darba lineari. 936 00:41:17,750 --> 00:41:20,790 Heck, f'dan il-punt, għaliex ma we biss użu wieħed lista enormi marbuta? 937 00:41:20,790 --> 00:41:23,510 Għaliex ma aħna biss użu wieħed enormi array biex jaħżnu l-ismijiet ta ' 938 00:41:23,510 --> 00:41:25,010 kulħadd fil-kamra? 939 00:41:25,010 --> 00:41:28,280 Ukoll, għad hemm xi ħaġa konvinċenti dwar tabella hash? 940 00:41:28,280 --> 00:41:30,810 Għad hemm xi ħaġa konvinċenti dwar struttura data 941 00:41:30,810 --> 00:41:33,940 li tidher bħal dan? 942 00:41:33,940 --> 00:41:35,182 Dan. 943 00:41:35,182 --> 00:41:37,050 >> STUDENT: [inaudible]. 944 00:41:37,050 --> 00:41:39,840 >> SPEAKER 1: Dritt, u għal darb'oħra jekk huwa biss żmien algoritmu lineari, u 945 00:41:39,840 --> 00:41:42,780 struttura tad-data ħin lineari, għaliex ma I biss taħżen isem kulħadd fit big 946 00:41:42,780 --> 00:41:44,210 array, jew lista kbir marbut? 947 00:41:44,210 --> 00:41:47,010 U tieqaf tagħmel CS tant diffiċli milli jeħtieġ li jkun? 948 00:41:47,010 --> 00:41:49,600 949 00:41:49,600 --> 00:41:53,190 X'inhu konvinċenti dwar dan, anke għalkemm I scratched it out? 950 00:41:53,190 --> 00:41:54,930 >> STUDENT: [inaudible]. 951 00:41:54,930 --> 00:41:57,040 >> SPEAKER 1: inserzjonijiet mhumiex? 952 00:41:57,040 --> 00:41:58,140 Għaljin aktar. 953 00:41:58,140 --> 00:42:03,390 Allura inserzjonijiet potenzjalment setgħet ukoll jkun żmien kostanti, anki jekk id-data tiegħek 954 00:42:03,390 --> 00:42:07,910 istruttura tidher bħal dan, firxa ta ' pointers, kull wieħed minnhom huwa li tipponta lejn 955 00:42:07,910 --> 00:42:09,550 potenzjalment lista linked. 956 00:42:09,550 --> 00:42:15,220 Kif tista 'tikseb kostanti inserzjoni ħin ta 'ismijiet? 957 00:42:15,220 --> 00:42:16,280 Stick fl-quddiem, id-dritt? 958 00:42:16,280 --> 00:42:19,290 >> Jekk aħna sagrifiċċju għan disinn mill qabel, fejn aħna riedu jżommu 959 00:42:19,290 --> 00:42:22,650 isem ta 'kulħadd, per eżempju, magħżula, jew kollha tal-numri fuq il-palk magħżula, 960 00:42:22,650 --> 00:42:25,020 jissoponi li għandna lista marbuta mhux magħżul. 961 00:42:25,020 --> 00:42:29,960 Hija biss l-ispejjeż us stadju wieħed inkella tnejn, bħal fil-każ ta 'Ben u Brian 962 00:42:29,960 --> 00:42:32,750 qabel, li daħħal element fil il-bidu tal-lista. 963 00:42:32,750 --> 00:42:36,090 Allura jekk aħna ma jimpurtahom dwar issortjar kollha ta 'l-ismijiet li jibda bl A jew kollha 964 00:42:36,090 --> 00:42:39,660 l-ismijiet li jibda bl B, nistgħu xorta jinkiseb inserzjoni ta 'żmien kostanti. 965 00:42:39,660 --> 00:42:43,900 Issa qed ifittxu up Alice jew Bob jew kull isem b'mod aktar ġenerali għadu dak? 966 00:42:43,900 --> 00:42:48,100 Huwa big O ta 'n diviż b'26, fil- każ ideali fejn kulħadd huwa uniformi 967 00:42:48,100 --> 00:42:51,190 mqassma, fejn hemm kif ħafna A tal kif hemm tal Z, li huwa probabbilment 968 00:42:51,190 --> 00:42:52,220 realistika. 969 00:42:52,220 --> 00:42:53,880 Imma dak li għadu lineari. 970 00:42:53,880 --> 00:42:57,120 >> Iżda hawnhekk, aħna jerġgħu lura għall-punt ta 'notazzjoni asintotiku jkunu 971 00:42:57,120 --> 00:42:58,600 teoretikament veru. 972 00:42:58,600 --> 00:43:02,960 Iżda fid-dinja reali, jekk I jsostnu li programm tiegħi tista 'tagħmel xi ħaġa 26 darba 973 00:43:02,960 --> 00:43:06,210 aktar mgħaġġel minn tiegħek, li programm inti se jippreferu jużaw? 974 00:43:06,210 --> 00:43:09,660 Dejjem jew mini, li huwa 26 darbiet aktar mgħaġġla? 975 00:43:09,660 --> 00:43:14,320 Realistikament, il-persuna li hija s-26 darbiet aktar mgħaġġla, anke jekk teoretikament 976 00:43:14,320 --> 00:43:18,790 algoritmi tagħna jimxu fl-istess asintotiku running time. 977 00:43:18,790 --> 00:43:20,940 >> Let me tipproponi differenti soluzzjoni għal kollox. 978 00:43:20,940 --> 00:43:24,380 U jekk dan ma blow moħħok, aħna qed barra ta 'strutturi ta' dejta. 979 00:43:24,380 --> 00:43:27,420 Allura dan huwa minnu a trie - 980 00:43:27,420 --> 00:43:28,520 tip ta 'isem stupid. 981 00:43:28,520 --> 00:43:32,880 Dan ġej mill retrievals, u l-kelma spjegat trie, t-r-i-e, minħabba 982 00:43:32,880 --> 00:43:34,450 irkupru kors ħsejjes simili trie. 983 00:43:34,450 --> 00:43:36,580 Iżda li l-istorja tal-trie kelma. 984 00:43:36,580 --> 00:43:40,980 >> Allura trie huwa tabilħaqq xi tip ta 'siġra, u huwa wkoll play fuq din il-kelma. 985 00:43:40,980 --> 00:43:46,330 U anki jekk inti ma tistax pjuttost tara ma 'dan viżwalizzazzjoni, a trie huwa 986 00:43:46,330 --> 00:43:50,790 siġra strutturat, bħal siġra tal-familja ma ' antenat wieħed fil-quċċata u l-lottijiet 987 00:43:50,790 --> 00:43:54,530 ta 'neputijiet u neputijiet kbira bħala tħalli fuq il-qiegħ. 988 00:43:54,530 --> 00:43:58,100 Iżda kull node fil trie huwa array. 989 00:43:58,100 --> 00:44:00,680 U huwa fil-firxa - u ejja oversimplify għal mument - huwa ta ' 990 00:44:00,680 --> 00:44:04,600 array, f'dan il-każ, ta 'daqs 26, fejn kull node darb'oħra huwa firxa ta 'daqs 991 00:44:04,600 --> 00:44:09,000 26, fejn l-element 0 f'dik array jirrappreżenta A, u l-aħħar 992 00:44:09,000 --> 00:44:11,810 element f'kull tali firxa tirrappreżenta Z. 993 00:44:11,810 --> 00:44:15,520 >> So nipproponi, allura, li din id-data istruttura, magħrufa bħala trie, jista 'jkun 994 00:44:15,520 --> 00:44:17,600 jintuża wkoll biex jaħżnu kliem. 995 00:44:17,600 --> 00:44:21,740 Rajna mument ilu kif nistgħu taħżen kliem, jew f'dan il-każ ismijiet, u aħna 996 00:44:21,740 --> 00:44:25,440 raw qabel kif nistgħu taħżen numri, imma jekk aħna niffukaw fuq ismijiet jew kordi 997 00:44:25,440 --> 00:44:27,460 hawn, avviż x'hemm interessanti. 998 00:44:27,460 --> 00:44:32,210 I jsostnu li l-isem huwa Maxwell ġewwa ta 'din l-istruttura tad-data. 999 00:44:32,210 --> 00:44:33,730 Fejn tara Maxwell? 1000 00:44:33,730 --> 00:44:35,140 >> STUDENT: [inaudible]. 1001 00:44:35,140 --> 00:44:36,240 >> SPEAKER 1: Fuq ix-xellug. 1002 00:44:36,240 --> 00:44:39,910 Allura x'hemm interessanti ma din id-data istruttura hija pjuttost milli maħżen tal- 1003 00:44:39,910 --> 00:44:46,200 string backslash zero M-A-X-W-E-L-L, kollha contiguously, dak li inti minflok tagħmel 1004 00:44:46,200 --> 00:44:46,890 qed isegwi. 1005 00:44:46,890 --> 00:44:50,510 Jekk dan huwa trie bħall-istruttura tad-data, kull lymph li hija għal darb'oħra firxa, 1006 00:44:50,510 --> 00:44:54,650 u inti tixtieq li taħżen Maxwell, inti l-ewwel indiċi u għalhekk node l-għerq tal-hekk 1007 00:44:54,650 --> 00:44:57,810 biex jitkellmu, l-node topmost, fil-post M, tajjeb, sabiex 1008 00:44:57,810 --> 00:44:59,160 bejn wieħed u ieħor fis-nofs. 1009 00:44:59,160 --> 00:45:03,740 U mbagħad minn hemm, inti ssegwi pointer lil lymph tfal, biex ngħidu hekk. 1010 00:45:03,740 --> 00:45:06,150 Allura fis-sens siġra tal-familja, inti ssegwi dan l isfel. 1011 00:45:06,150 --> 00:45:09,030 U li inti twassal għal ieħor node fuq ix-xellug hemm, li hija 1012 00:45:09,030 --> 00:45:10,540 biss array ieħor. 1013 00:45:10,540 --> 00:45:14,710 >> U mbagħad jekk inti tixtieq li taħżen Maxwell, issib il-pointer li tirrappreżenta 1014 00:45:14,710 --> 00:45:16,430 A, li huwa dan wieħed hawn. 1015 00:45:16,430 --> 00:45:17,840 Imbagħad inti tmur għall-node li jmiss. 1016 00:45:17,840 --> 00:45:20,100 U avviż - dan huwa għaliex l-istampa tal- iqarraq ftit - 1017 00:45:20,100 --> 00:45:21,990 dan node ħarsa super ċkejkna. 1018 00:45:21,990 --> 00:45:26,050 Iżda għad-dritt ta 'dan huwa Y u Z. Huwa biss l-awtur maqtugħ il- 1019 00:45:26,050 --> 00:45:27,630 stampa sabiex inti fil-fatt jara l-affarijiet. 1020 00:45:27,630 --> 00:45:30,400 Inkella din l-istampa tkun immensament wiesgħa. 1021 00:45:30,400 --> 00:45:36,180 Allura issa inti indiċi fis lokazzjoni X, imbagħad W, Imbagħad E, allura L, imbagħad L. Imbagħad x'hemm 1022 00:45:36,180 --> 00:45:37,380 dan kurżità? 1023 00:45:37,380 --> 00:45:41,250 >> Ukoll, jekk aħna qed jużaw dan it-tip ta 'ġodda tieħu dwar kif taħżen string fil- 1024 00:45:41,250 --> 00:45:44,500 struttura tad-data, inti xorta jkollok bżonn li essenzjalment check off fid-dejta 1025 00:45:44,500 --> 00:45:47,250 istruttura li kelma tispiċċa hawnhekk. 1026 00:45:47,250 --> 00:45:50,830 Fi kliem ieħor, kull wieħed minn dawn in-nodi b'xi mod irid jiftakar li aħna 1027 00:45:50,830 --> 00:45:53,500 jseħħx kollha ta 'dawn pointers u huma jitilqu ftit 1028 00:45:53,500 --> 00:45:58,370 Frak tal-ħobż fil-qiegħ hawn 'din istruttura li jindika M-A-X-W-E-L-L huwa 1029 00:45:58,370 --> 00:46:00,230 tabilħaqq f'din l-istruttura tad-data. 1030 00:46:00,230 --> 00:46:02,040 >> Allura nistgħu nagħmlu dan kif ġej. 1031 00:46:02,040 --> 00:46:06,810 Kull wieħed mill-lymph fl-istampa aħna biss serrieq għandha wieħed, firxa ta 'daqs 27. 1032 00:46:06,810 --> 00:46:10,550 U huwa issa 27, għaliex p stabbiliti sitt, aħna ser attwalment jagħtuk apostrophe, 1033 00:46:10,550 --> 00:46:13,590 hekk aħna jista 'jkollhom ismijiet bħal O'Reilly u oħrajn bi apostrophes. 1034 00:46:13,590 --> 00:46:14,820 Iżda istess idea. 1035 00:46:14,820 --> 00:46:17,710 Kull waħda minn dawn l-elementi fil- punti firxa għal Struct 1036 00:46:17,710 --> 00:46:19,320 node, hekk biss node. 1037 00:46:19,320 --> 00:46:21,430 Allura dan huwa ħafna reminixxenti tal-lista marbuta tagħna. 1038 00:46:21,430 --> 00:46:24,550 >> U mbagħad I jkollhom Boolean, li jiena ser sejħa kelma, li huwa biss se jkun 1039 00:46:24,550 --> 00:46:29,120 minnu jekk kelma jintemm dan node fil-siġra. 1040 00:46:29,120 --> 00:46:32,870 Hija effettivament jirrappreżenta l-ftit trijangolu rajna mument ilu. 1041 00:46:32,870 --> 00:46:37,190 Mela jekk kelma tispiċċa f'dak node fil- siġra, dak il-qasam se kelma ikunu vera, 1042 00:46:37,190 --> 00:46:41,990 li hija kunċettwalment iċċekkjar off, jew aħna qed tpinġija dan il-trijanglu, iva hemm 1043 00:46:41,990 --> 00:46:44,080 hija kelma hawn. 1044 00:46:44,080 --> 00:46:45,120 >> Allura dan huwa trie. 1045 00:46:45,120 --> 00:46:48,540 U issa l-kwistjoni hija, dak huwa running time tiegħu? 1046 00:46:48,540 --> 00:46:49,930 Huwa big O ta 'n? 1047 00:46:49,930 --> 00:46:51,410 Huwa xi ħaġa oħra? 1048 00:46:51,410 --> 00:46:57,330 Ukoll, jekk għandek n ismijiet f'dan data istruttura, Maxwell huwa biss wieħed ta ' 1049 00:46:57,330 --> 00:47:02,330 minnhom, dak li huwa l-ħin tmexxija ta ' ddaħħal jew sejba Maxwell? 1050 00:47:02,330 --> 00:47:06,230 1051 00:47:06,230 --> 00:47:09,050 X'hemm-running time ta 'ddaħħal Maxwell? 1052 00:47:09,050 --> 00:47:11,740 Jekk hemm ismijiet oħra n diġà fit-tabella? 1053 00:47:11,740 --> 00:47:12,507 Yeah? 1054 00:47:12,507 --> 00:47:15,429 >> STUDENT: [inaudible]. 1055 00:47:15,429 --> 00:47:17,550 >> SPEAKER 1: Yeah, huwa t-tul l-isem, id-dritt? 1056 00:47:17,550 --> 00:47:24,420 Allura M-a-x-w-e-l-l għalhekk iħoss bħal dan algoritmu huwa kbir O ta 'seba. 1057 00:47:24,420 --> 00:47:26,580 Issa, naturalment, l-isem se ivarjaw fit-tul. 1058 00:47:26,580 --> 00:47:27,380 Forsi huwa l-isem qasir. 1059 00:47:27,380 --> 00:47:28,600 Forsi huwa l-isem itwal. 1060 00:47:28,600 --> 00:47:33,390 Imma x'hemm prinċipali hawnhekk hija li huwa numru kostanti. 1061 00:47:33,390 --> 00:47:36,810 U forsi mhuwiex verament kostanti, imma alla, jekk realistikament, b'mod 1062 00:47:36,810 --> 00:47:41,570 dizzjunarju, hemm probabilment xi limitu fuq in-numru ta 'ittri fil- 1063 00:47:41,570 --> 00:47:43,820 isem persuna f'pajjiż partikolari. 1064 00:47:43,820 --> 00:47:46,940 >> U hekk nistgħu nassumu li valur huwa kostanti. 1065 00:47:46,940 --> 00:47:47,750 I do not know dak li hu. 1066 00:47:47,750 --> 00:47:50,440 Huwa probabbilment akbar minn aħna naħsbu li hu. 1067 00:47:50,440 --> 00:47:52,720 Għaliex hemm dejjem xi kantuniera każ ma 'isem twil crazy. 1068 00:47:52,720 --> 00:47:56,360 Mela ejja sejħa hija k, iżda huwa għadu kostanti preżumibbilment, għaliex kull 1069 00:47:56,360 --> 00:48:00,190 isem fid-dinja, mill-inqas fil- pajjiż partikolari, huwa li tul jew 1070 00:48:00,190 --> 00:48:01,780 iqsar, dan huwa kostanti. 1071 00:48:01,780 --> 00:48:04,490 Imma meta aħna ħadthom qal xi ħaġa hija kbira O ta 'valur kostanti, x'hemm li 1072 00:48:04,490 --> 00:48:07,760 verament ekwivalenti għal? 1073 00:48:07,760 --> 00:48:10,420 Dik hija verament l-istess ħaġa kif qal ħin kostanti. 1074 00:48:10,420 --> 00:48:11,530 >> Issa aħna qed tip ta 'qerq, right? 1075 00:48:11,530 --> 00:48:15,340 Aħna tip ta 'lieva xi teorija hawn biex ngħid li tajjeb, ordni ta 'k huwa 1076 00:48:15,340 --> 00:48:17,450 verament ftit ordni ta 'wieħed, u wasal iż-żmien kostanti. 1077 00:48:17,450 --> 00:48:18,200 Imma verament huwa. 1078 00:48:18,200 --> 00:48:22,550 Minħabba l-għarfien prinċipali hawnhekk hija li jekk aħna n ismijiet diġà f'dan 1079 00:48:22,550 --> 00:48:26,010 struttura tad-data, u aħna daħħal Maxwell, huwa l-ammont ta 'ħin li tieħu magħna biex 1080 00:48:26,010 --> 00:48:29,530 daħħal Maxwell fil-livelli kollha affettwati minn kif in-nies ħafna oħrajn 1081 00:48:29,530 --> 00:48:31,100 huma fl-istruttura tad-data? 1082 00:48:31,100 --> 00:48:31,670 Ma jidhirx li jkun. 1083 00:48:31,670 --> 00:48:36,280 Jekk I kellhom biljun aktar elementi ta 'dan trie, u mbagħad daħħal Maxwell, hija 1084 00:48:36,280 --> 00:48:38,650 hu fil-livelli kollha affettwati? 1085 00:48:38,650 --> 00:48:39,050 No 1086 00:48:39,050 --> 00:48:42,950 U li b'differenza kwalunkwe data kuljum istrutturi Rajna s'issa, fejn 1087 00:48:42,950 --> 00:48:46,820 l-running time ta 'algoritmu tiegħek huwa kompletament indipendenti ta 'kemm 1088 00:48:46,820 --> 00:48:51,430 għalf huwa jew ma jkunx diġà f'dak istruttura tad-data. 1089 00:48:51,430 --> 00:48:54,650 >> U hekk ma 'dan joffri inti issa huwa opportunità għal p sett sitt, li se 1090 00:48:54,650 --> 00:48:58,310 darb'oħra jinvolvu implimentazzjoni tiegħek jespliċitaw kontrollur, qari 150,000 1091 00:48:58,310 --> 00:49:01,050 kliem, kif l-aħjar biex jaħżnu dik mhuwiex neċessarjament ovvja. 1092 00:49:01,050 --> 00:49:04,030 U għalkemm stajt jaspira biex isibu l-Grail qaddis, jien ma 1093 00:49:04,030 --> 00:49:05,330 jsostnu li trie hu. 1094 00:49:05,330 --> 00:49:09,810 Fil-fatt, tabella hash jistgħu tajjeb ħafna juru li huma ħafna aktar effiċjenti. 1095 00:49:09,810 --> 00:49:10,830 Iżda dawn huma biss - 1096 00:49:10,830 --> 00:49:14,620 li jinsab biss waħda mid-deċiżjonijiet tad-disinn inti se jkollu jagħmel. 1097 00:49:14,620 --> 00:49:18,920 >> Iżda fl-għeluq ejja ħu 50 jew hekk sekondi biex tieħu Peek fuq dak li jinsab 1098 00:49:18,920 --> 00:49:22,190 quddiem ġimgħa d-dieħla u lil hinn aħna transizzjoni minn din il-linja ta 'kmand 1099 00:49:22,190 --> 00:49:26,220 dinja jekk C-programmi għall-affarijiet web ibbażata u lingwi bħal PHP u 1100 00:49:26,220 --> 00:49:30,350 JavaScript u l-internet innifsu, protokolli bħal HTTP, li inti stajt 1101 00:49:30,350 --> 00:49:32,870 meħuda għall mogħtija għas-snin issa, u ittajpjat aktar minn darba kull 1102 00:49:32,870 --> 00:49:34,440 jum, forsi, jew li jidhru. 1103 00:49:34,440 --> 00:49:37,420 U aħna ser tibda titqaxxar lura l- saffi ta 'dak li huwa l-internet. 1104 00:49:37,420 --> 00:49:40,650 U dak huwa l-kodiċi li huwa l-bażi għodod tal-lum. 1105 00:49:40,650 --> 00:49:43,230 Allura 50 sekondi ta 'dan teaser hawn. 1106 00:49:43,230 --> 00:49:46,570 I jagħtuk Warriors tal-Net. 1107 00:49:46,570 --> 00:49:51,370 >> [Daqq video] 1108 00:49:51,370 --> 00:49:56,764 >> -Huwa daħal bil-messaġġ. 1109 00:49:56,764 --> 00:50:00,687 Bil-protokoll kollu tiegħu stess. 1110 00:50:00,687 --> 00:50:13,370 1111 00:50:13,370 --> 00:50:19,780 Huwa daħal għal dinja ta 'firewalls krudili, routers uncaring, u l-perikli ferm 1112 00:50:19,780 --> 00:50:22,600 agħar minn mewt. 1113 00:50:22,600 --> 00:50:23,590 Huwa mgħaġġel. 1114 00:50:23,590 --> 00:50:25,300 Hu b'saħħtu. 1115 00:50:25,300 --> 00:50:27,700 Hu TCPIP. 1116 00:50:27,700 --> 00:50:30,420 U hu ltqajna indirizz tiegħek. 1117 00:50:30,420 --> 00:50:32,920 1118 00:50:32,920 --> 00:50:34,590 Ġellieda tal-Net. 1119 00:50:34,590 --> 00:50:35,290 >> [Daqq video END] 1120 00:50:35,290 --> 00:50:38,070 >> SPEAKER 1: Din hija kif l-internet għandhom jaħdmu mill-ġimgħa d-dieħla. 1121 00:50:38,070 --> 00:50:40,406