1 00:00:00,000 --> 00:00:00,500 2 00:00:00,500 --> 00:00:03,340 [Tónlist spila] 3 00:00:03,340 --> 00:00:11,020 4 00:00:11,020 --> 00:00:14,010 >> DAVID MALAN: Þetta er CS50. 5 00:00:14,010 --> 00:00:18,090 Og þetta er bæði byrjun og end-- eins literally-- næstum lok 6 00:00:18,090 --> 00:00:18,825 vikunnar sex. 7 00:00:18,825 --> 00:00:20,030 8 00:00:20,030 --> 00:00:22,640 >> Ég hélt ég myndi deila svolítið um skemmtilegt staðreynd. 9 00:00:22,640 --> 00:00:25,370 Ég hef dregið þetta upp úr gögn Past önn er sett. 10 00:00:25,370 --> 00:00:29,710 Þú getur muna að við biðjum þig á hverjum p sett mynd ef þú hefur horft á netinu 11 00:00:29,710 --> 00:00:31,580 eða ef þú hefur sótt í eigin persónu. 12 00:00:31,580 --> 00:00:33,020 Og hér eru gögnin. 13 00:00:33,020 --> 00:00:34,710 Svo í dag var mjög mikill fyrirsjáanleg. 14 00:00:34,710 --> 00:00:37,126 En við vildum að eyða svolítið tíma með þér engu að síður. 15 00:00:37,126 --> 00:00:40,599 Ætti einhver vilja að álykta hvers vegna þetta línurit er svo jaggy, upp niður, upp niður, 16 00:00:40,599 --> 00:00:41,265 svo stöðugt? 17 00:00:41,265 --> 00:00:42,980 18 00:00:42,980 --> 00:00:45,130 Hvað gera hvert toppa og dalir tákna? 19 00:00:45,130 --> 00:00:46,005 >> Áhorfendur: [inaudible] 20 00:00:46,005 --> 00:00:47,002 21 00:00:47,002 --> 00:00:47,835 DAVID MALAN: Reyndar. 22 00:00:47,835 --> 00:00:50,900 23 00:00:50,900 --> 00:00:55,480 Og meira skemmtilega, guð forði, við halda eina fyrirlestur á föstudegi 24 00:00:55,480 --> 00:00:58,960 í upphafi misseris, það er það sem við sjáum gerast. 25 00:00:58,960 --> 00:01:03,430 Svo í dag, taka þátt við í smá meira um uppbyggingu gagna. 26 00:01:03,430 --> 00:01:06,660 Og til að gefa þér meira af a solid andlegt líkan fyrir vandamál í fimm, 27 00:01:06,660 --> 00:01:07,450 sem er nú út. 28 00:01:07,450 --> 00:01:10,817 Stafsetningarvillur, þar sem, við munum afhenda þér textaskrá sumir 100.000 29 00:01:10,817 --> 00:01:12,650 auk ensk orð og þú ert að fara að hafa 30 00:01:12,650 --> 00:01:17,770 að reikna út hvernig á að snjall hlaða þeim í minni, í RAM, með nokkur gögn 31 00:01:17,770 --> 00:01:19,330 uppbyggingu vali. 32 00:01:19,330 --> 00:01:22,470 >> Nú ein slík gögn uppbygging gæti vera, en sennilega ætti ekki að vera, 33 00:01:22,470 --> 00:01:25,630 jafnvel nokkuð einfalt tengd lista, sem við kynnt síðast. 34 00:01:25,630 --> 00:01:29,220 Og tengist lista hafði amk Einn kostur yfir fylki. 35 00:01:29,220 --> 00:01:32,096 Hvað er einn kostur af a tengda listanum öllum líkindum? 36 00:01:32,096 --> 00:01:32,950 >> Áhorfendur: ísetningu. 37 00:01:32,950 --> 00:01:33,908 >> DAVID MALAN: ísetningu. 38 00:01:33,908 --> 00:01:34,155 39 00:01:34,155 --> 00:01:35,196 Hvað meinarðu með því? 40 00:01:35,196 --> 00:01:37,872 >> Áhorfendur: Anywhere eftir Listinn [inaudible]. 41 00:01:37,872 --> 00:01:38,770 >> DAVID MALAN: Good. 42 00:01:38,770 --> 00:01:42,090 Svo er hægt að setja inn stak þar sem þaà þú vilt í the miðja af the listi 43 00:01:42,090 --> 00:01:45,490 án þess að þurfa að stokka neitt, sem við lauk, í flokkun okkar 44 00:01:45,490 --> 00:01:47,630 umræður, er ekki endilega gott, 45 00:01:47,630 --> 00:01:51,200 því það tekur tíma til að raunverulega færa allar þessar menn til vinstri eða hægri. 46 00:01:51,200 --> 00:01:55,540 Og svo með tengda listanum, þú getur bara úthluta með malloc, ný hnút, 47 00:01:55,540 --> 00:01:58,385 og þá uppfæra nokkra pointers-- tveir, þrír aðgerðir max-- 48 00:01:58,385 --> 00:02:01,480 og við erum fær um að rifa einhvern í hvar í lista. 49 00:02:01,480 --> 00:02:03,550 >> Hvað annað var hagstæður um tengda listanum? 50 00:02:03,550 --> 00:02:04,980 51 00:02:04,980 --> 00:02:05,659 Já? 52 00:02:05,659 --> 00:02:06,534 >> Áhorfendur: [inaudible] 53 00:02:06,534 --> 00:02:07,538 54 00:02:07,538 --> 00:02:08,413 DAVID MALAN: Perfect. 55 00:02:08,413 --> 00:02:10,590 56 00:02:10,590 --> 00:02:11,090 Perfect. 57 00:02:11,090 --> 00:02:12,070 Það er mjög breytilegt. 58 00:02:12,070 --> 00:02:15,100 Og að þú ert ekki að fremja, fyrirfram, að einhverju föstu stærð 59 00:02:15,100 --> 00:02:18,750 klumpur af minni, eins og þú vildi hafa til með fjölda vegar kosti sem 60 00:02:18,750 --> 00:02:22,455 er að þú getur tekið hnúta aðeins á eftirspurn þannig að nota aðeins eins mikið pláss 61 00:02:22,455 --> 00:02:23,330 eins og þú þarft í raun og veru. 62 00:02:23,330 --> 00:02:26,830 By mótsögn við fjölda, þú gætir óvart úthluta of lítið. 63 00:02:26,830 --> 00:02:28,871 Og þá er það bara að fara að vera með verk í hálsi 64 00:02:28,871 --> 00:02:32,440 að endurúthluta nýja stærri array, afrita allt yfir, losa gamla array, 65 00:02:32,440 --> 00:02:33,990 og fara svo um fyrirtækið þitt. 66 00:02:33,990 --> 00:02:37,479 Eða verra, gætir þú tekið hátt meira minni en þú þarft í raun og veru, 67 00:02:37,479 --> 00:02:40,520 og svo þú ert að fara að hafa mjög dreifður-byggð array, svo að segja. 68 00:02:40,520 --> 00:02:44,350 >> Svo tengd listi gefur þér þessar Kostir krafti og sveigjanleika 69 00:02:44,350 --> 00:02:46,080 með ísetningar og úrfellingum. 70 00:02:46,080 --> 00:02:48,000 En örugglega það verður að vera verð greitt. 71 00:02:48,000 --> 00:02:50,000 Í raun einn af þeim þemum kanna á spurningakeppni núll 72 00:02:50,000 --> 00:02:52,430 var par af málamiðlanir við höfum séð hingað til. 73 00:02:52,430 --> 00:02:56,161 Svo er það verð greitt eða hæðir á tengda listanum? 74 00:02:56,161 --> 00:02:56,660 Já. 75 00:02:56,660 --> 00:02:57,560 >> Áhorfendur: No handahófi aðgang. 76 00:02:57,560 --> 00:02:58,809 >> DAVID MALAN: No handahófi aðgang. 77 00:02:58,809 --> 00:02:59,540 En hver blíðuhót? 78 00:02:59,540 --> 00:03:01,546 Random aðgangur ekki hljóð sannfærandi. 79 00:03:01,546 --> 00:03:02,421 >> Áhorfendur: [inaudible] 80 00:03:02,421 --> 00:03:04,865 81 00:03:04,865 --> 00:03:05,740 DAVID MALAN: Einmitt. 82 00:03:05,740 --> 00:03:07,580 Ef þú vilt hafa ákveðinn algorithm-- 83 00:03:07,580 --> 00:03:10,170 og láta mig leggja í raun Tvíundarleit einkum, sem 84 00:03:10,170 --> 00:03:12,600 er eitt sem við höfum notað nokkuð bit-- ef þú ert ekki af handahófi aðgang, 85 00:03:12,600 --> 00:03:15,516 þú getur ekki gert það einföld stærðfræði að finna eins miðju frumefni 86 00:03:15,516 --> 00:03:16,530 og stökk rétt við það. 87 00:03:16,530 --> 00:03:20,239 Þú hefur þess í stað að byrja á fyrsta frumefni og línulega leita frá vinstri 88 00:03:20,239 --> 00:03:22,780 til hægri ef þú vilt að finna miðju eða önnur frumefni. 89 00:03:22,780 --> 00:03:24,410 >> Áhorfendur: Það tekur sennilega meira minni. 90 00:03:24,410 --> 00:03:25,040 >> DAVID MALAN: Tekur meira minni. 91 00:03:25,040 --> 00:03:27,464 Hvar er þessi viðbótar kosta að koma frá í minni? 92 00:03:27,464 --> 00:03:28,339 >> Áhorfendur: [inaudible] 93 00:03:28,339 --> 00:03:32,566 94 00:03:32,566 --> 00:03:33,440 DAVID MALAN: Einmitt. 95 00:03:33,440 --> 00:03:35,679 Í þessu tilfelli hér, við höfðum a tengda listanum fyrir heiltölur, 96 00:03:35,679 --> 00:03:37,470 og enn erum við tvöföldun fjárhæð minni 97 00:03:37,470 --> 00:03:39,680 þurfum við einnig að geyma þessum ábendingum. 98 00:03:39,680 --> 00:03:42,090 Nú minna af a stór samningur sem structs þínir fá stærri 99 00:03:42,090 --> 00:03:45,320 og þú ert að geyma ekki tala en kannski nemandi eða einhver annar hlutur. 100 00:03:45,320 --> 00:03:46,880 En punkturinn er vissulega. 101 00:03:46,880 --> 00:03:49,421 Og svo a tala af starfsemi á tengdum listum voru kallaðir 102 00:03:49,421 --> 00:03:50,570 voru stór O í N- línuleg. 103 00:03:50,570 --> 00:03:54,730 Hluti eins ísetningu eða leit eða eyða ef stak 104 00:03:54,730 --> 00:03:57,720 varð að vera aftast á Listinn hvort sem það er flokkað eða ekki. 105 00:03:57,720 --> 00:04:01,167 >> Stundum þú might fá heppinn og svo lægri mörk á þessum aðgerðum 106 00:04:01,167 --> 00:04:04,250 gæti líka verið stöðug tími ef þú ert alltaf að horfa á fyrstu frumefni, 107 00:04:04,250 --> 00:04:05,070 til dæmis. 108 00:04:05,070 --> 00:04:09,360 En að lokum, lofaði við að ná Gral 109 00:04:09,360 --> 00:04:12,630 gögn mannvirki, eða sumir nálgun þess, 110 00:04:12,630 --> 00:04:14,290 með því föstu tíma. 111 00:04:14,290 --> 00:04:17,579 Getum við fundið þætti eða bæta þætti eða fjarlægja atriði úr lista? 112 00:04:17,579 --> 00:04:19,059 Við skulum sjá alveg fljótlega. 113 00:04:19,059 --> 00:04:21,100 Og það kemur í ljós að einn á ferli sem við erum 114 00:04:21,100 --> 00:04:23,464 að fara að byrja að nota í dag, árleg notkun í p setja fimm, 115 00:04:23,464 --> 00:04:24,630 er reyndar nokkuð kunnuglegt. 116 00:04:24,630 --> 00:04:27,430 Fyrir dæmi, ef þetta er fullt af exam bókum, sem hver um sig 117 00:04:27,430 --> 00:04:29,660 hefur nemandi fyrst Nafn og eftirnafn á það, 118 00:04:29,660 --> 00:04:31,820 og ég ná þeim upp úr í lok prófi 119 00:04:31,820 --> 00:04:33,746 og þeir eru allir frekar mikið í handahófi 120 00:04:33,746 --> 00:04:36,370 og við viljum að fara um flokkun þessum prófum þannig að þegar farið 121 00:04:36,370 --> 00:04:38,661 það er bara mikið auðveldara og hraðar til hendinni þá aftur út 122 00:04:38,661 --> 00:04:40,030 nemendum í stafrófsröð. 123 00:04:40,030 --> 00:04:42,770 Hvað myndi eðlishvöt yðar séu fyrir haug af prófum eins og þetta? 124 00:04:42,770 --> 00:04:45,019 >> Jæja, ef þú ert eins og mig, þú gæti séð að þetta er m, 125 00:04:45,019 --> 00:04:48,505 þannig að ég ætla að raða í setja þetta inn, ef þetta er mitt borð eða gólf minn þar 126 00:04:48,505 --> 00:04:50,650 Ég er að breiða það out-- eða array minn really-- 127 00:04:50,650 --> 00:04:52,210 Ég gæti sett alla MS þar. 128 00:04:52,210 --> 00:04:52,710 Oh. 129 00:04:52,710 --> 00:04:55,020 Hér er A. Svo ég gæti setja As hérna. 130 00:04:55,020 --> 00:04:55,520 Oh. 131 00:04:55,520 --> 00:04:57,980 Hér er önnur A. Ég ætla að setja það hérna. 132 00:04:57,980 --> 00:05:02,490 Hér er a Z. Hér er annar M. Og svo Ég gæti byrjað að gera hrúgur svona. 133 00:05:02,490 --> 00:05:06,620 Og þá kannski myndi ég fara í síðar og svoleiðis mjög nitpicky-Ly konar 134 00:05:06,620 --> 00:05:07,710 einstök hrúgur. 135 00:05:07,710 --> 00:05:11,300 En punkturinn er að ég myndi líta á inntak að ég er hönd 136 00:05:11,300 --> 00:05:14,016 og ég myndi gera sumir reiknað ákvörðun byggist á þeirri inntak. 137 00:05:14,016 --> 00:05:15,640 Ef það byrjar með A, setja það þarna. 138 00:05:15,640 --> 00:05:18,980 Ef það byrjar með Z, setja það yfir þar, og allt þar á milli. 139 00:05:18,980 --> 00:05:22,730 >> Þannig að þetta er tækni sem er almennt þekktur sem hashing-- H-A-S-H-- 140 00:05:22,730 --> 00:05:26,550 sem yfirleitt þýðir að taka eins inntak og nota þessi inntak að reikna 141 00:05:26,550 --> 00:05:30,940 gildi, yfirleitt tala, og að talan er vísitalan í geymslu 142 00:05:30,940 --> 00:05:32,260 gámur, eins fylki. 143 00:05:32,260 --> 00:05:35,490 Svo í öðrum orðum, gæti ég hafa kjötkássa virka, eins og ég geri í höfðinu á mér, 144 00:05:35,490 --> 00:05:37,940 að ef ég sé einhver er nafn sem byrjar á A, 145 00:05:37,940 --> 00:05:40,190 Ég ætla að kortleggja það að núll í höfðinu á mér. 146 00:05:40,190 --> 00:05:44,160 Og ef ég sé einhvern með Z, ég er fara að kortleggja þessi til 25 í höfðinu á mér 147 00:05:44,160 --> 00:05:46,220 og þá setja það inn í síðasta mest stafli. 148 00:05:46,220 --> 00:05:50,990 >> Nú, ef þú hugsa um ekki heilinn minn en C program, hvaða tölur gætu 149 00:05:50,990 --> 00:05:53,170 þú treyst á að ná þessu sömu niðurstöðu? 150 00:05:53,170 --> 00:05:55,594 Með öðrum orðum, ef þú hafði ASCII staf A, 151 00:05:55,594 --> 00:05:57,510 hvernig ákveða hvað fötu til að setja það í? 152 00:05:57,510 --> 00:05:59,801 Þú vilt sennilega ekki að setja það inn fötu 65, sem 153 00:05:59,801 --> 00:06:01,840 myndi vera eins þarna fyrir neitun góður ástæða. 154 00:06:01,840 --> 00:06:04,320 Hvar viltu setja hvað varðar ASCII gildi þess? 155 00:06:04,320 --> 00:06:05,600 156 00:06:05,600 --> 00:06:08,920 Hvar viltu gera til ASCII hennar gildi til að koma upp með a snjallari skóflu 157 00:06:08,920 --> 00:06:09,480 að setja það í? 158 00:06:09,480 --> 00:06:10,206 >> Áhorfendur: Minus A. 159 00:06:10,206 --> 00:06:10,956 >> DAVID MALAN: Já. 160 00:06:10,956 --> 00:06:13,190 Svo mínus A eða mínus sérstaklega 65 ef það er 161 00:06:13,190 --> 00:06:18,240 höfuðborg A. Or 98 ef það er lágstafir a. 162 00:06:18,240 --> 00:06:21,300 Og svo sem myndi gera okkur kleift að, mjög einfaldlega og mjög arithmetically, 163 00:06:21,300 --> 00:06:23,260 setja eitthvað í fötu eins og þessi. 164 00:06:23,260 --> 00:06:26,010 Svo kemur í ljós við gerum í raun þetta eins vel, jafnvel með Skyndipróf. 165 00:06:26,010 --> 00:06:29,051 >> Svo þú gætir muna að þú hring þinn Nafn Kennslu náungi er á forsíðu. 166 00:06:29,051 --> 00:06:32,270 Og nöfn TF voru skipulögð í þessum dálkum í stafrófsröð, 167 00:06:32,270 --> 00:06:34,400 Jæja, þá trúið því eða ekki, þegar öll 80 plús okkur 168 00:06:34,400 --> 00:06:37,800 komu saman um daginn til bekk, síðasta skrefið í einkunnakerfi ferli okkar 169 00:06:37,800 --> 00:06:41,830 er að kjötkássa á Skyndipróf í stór rými hæð í [inaudible] 170 00:06:41,830 --> 00:06:45,110 og að leggja Skyndipróf allra út í nákvæmlega röð TF sinna 171 00:06:45,110 --> 00:06:47,700 nöfn á lokinu, Vegna þá er það mun auðveldara fyrir okkur 172 00:06:47,700 --> 00:06:51,290 að leita í gegnum það að nota línulega leita eða einhvers konar bragðvísi 173 00:06:51,290 --> 00:06:54,050 fyrir TF að finna hans eða Skyndipróf nemenda sinna. 174 00:06:54,050 --> 00:06:56,060 >> Þannig þessi hugmynd um hass að þú munt sjá er 175 00:06:56,060 --> 00:07:00,520 alveg öflugur er í raun nokkuð hversdagsleg og mjög leiðandi, 176 00:07:00,520 --> 00:07:03,000 líkt kannski skipta og Conquer var í viku núll. 177 00:07:03,000 --> 00:07:05,250 I Fljótur Áfram til hackathon a par af ár síðan. 178 00:07:05,250 --> 00:07:08,040 Þetta var Zamyla og a par af aðrir nemendur starfsfólk kveðja 179 00:07:08,040 --> 00:07:09,030 eins og þeir komu inn. 180 00:07:09,030 --> 00:07:12,680 Og við höfðum a heild búnt af leggja saman borðið með nafni tags. 181 00:07:12,680 --> 00:07:15,380 Og héldum merkjum skipulögð með eins og yfir það 182 00:07:15,380 --> 00:07:16,690 og ZS þarna. 183 00:07:16,690 --> 00:07:20,350 Og svo einn af TFS mjög snjall skrifaði þetta sem leiðbeiningar 184 00:07:20,350 --> 00:07:21,030 fyrir daginn. 185 00:07:21,030 --> 00:07:24,480 Og í 12. viku annarinnar þessa allt gert fullkominn skilningarvit og alla 186 00:07:24,480 --> 00:07:25,310 vissi hvað ég á að gera. 187 00:07:25,310 --> 00:07:27,900 En hvenær sem þú hef bið á sama hátt, 188 00:07:27,900 --> 00:07:30,272 þú ert að innleiða Sama hugmynd um kjötkássa. 189 00:07:30,272 --> 00:07:31,730 Svo skulum móta það svolítið. 190 00:07:31,730 --> 00:07:32,890 Hér er fylki. 191 00:07:32,890 --> 00:07:36,820 Það er vakin á að vera svolítið breiður bara að sýna, sjónrænt, 192 00:07:36,820 --> 00:07:38,920 að við gætum sett strengi í eitthvað eins og þetta. 193 00:07:38,920 --> 00:07:41,970 Og þetta fylki er augljóslega stærð 26. samtals. 194 00:07:41,970 --> 00:07:43,935 Og málið er kallað Tafla geðþótta. 195 00:07:43,935 --> 00:07:48,930 En þetta er bara flutningur flytjanda um hvað kjötkássa borð væri. 196 00:07:48,930 --> 00:07:52,799 >> Svo kjötkássa borð nú er að fara að vera hærra stigi gagnagrind. 197 00:07:52,799 --> 00:07:54,840 Í lok dagsins við erum að fara að sjá að þú 198 00:07:54,840 --> 00:07:58,700 getur innleiða kjötkássa borð, sem er mikill eins og innritun í línu 199 00:07:58,700 --> 00:08:02,059 á hackathon mikið eins og þetta Tafla notað fyrir flokkun exam bækur. 200 00:08:02,059 --> 00:08:03,850 En kjötkássa borð er Raða þessa háu stigi 201 00:08:03,850 --> 00:08:08,250 hugtak sem gæti nota array undir hetta til að framkvæma það, 202 00:08:08,250 --> 00:08:11,890 eða það væri hægt að nota lengd lista, eða jafnvel kannski nokkrar aðrar gögn uppbygging. 203 00:08:11,890 --> 00:08:15,590 Og nú er að theme-- taka sumir af þessum grundvallar innihaldsefni 204 00:08:15,590 --> 00:08:18,310 eins fjölda og þessari byggingu loka nú að lengd lista 205 00:08:18,310 --> 00:08:21,740 og sjá hvað við getum byggt ofan á þeim, eins og innihaldsefni 206 00:08:21,740 --> 00:08:26,550 í uppskrift, gera meira og meira áhugaverðar og gagnlegar endanlegar niðurstöður. 207 00:08:26,550 --> 00:08:28,680 >> Svo með kjötkássa borð við gætum framkvæma það 208 00:08:28,680 --> 00:08:32,540 í minni myndrænan svona, en hvernig gæti það í raun vera á dulmáli upp? 209 00:08:32,540 --> 00:08:33,789 Jæja, kannski er eins einfaldlega þetta. 210 00:08:33,789 --> 00:08:38,270 Ef getu á öllum húfur, er bara sumir constant-- til dæmis 26, 211 00:08:38,270 --> 00:08:42,030 í 26 bókstafir alphabet-- Ég gæti hringt breytilega mitt borð, 212 00:08:42,030 --> 00:08:45,630 og ég gæti haldið því fram að ég ætla að setja char stjörnur í það, eða band. 213 00:08:45,630 --> 00:08:49,880 Svo það er eins einfalt eins og þetta ef þú vilja innleiða kjötkássa töflunni. 214 00:08:49,880 --> 00:08:51,490 Og enn, þetta er í raun bara fylki. 215 00:08:51,490 --> 00:08:53,198 En aftur, tæti borð er nú það sem við munum 216 00:08:53,198 --> 00:08:57,470 kalla fræðilega gögn gerð sem er bara konar huglægu layering ofan 217 00:08:57,470 --> 00:09:00,780 um eitthvað meira mundane nú eins fylki. 218 00:09:00,780 --> 00:09:02,960 >> Nú, hvernig eigum við að fara um að leysa vandamál? 219 00:09:02,960 --> 00:09:06,980 Jæja, áðan hafði lúxus af því að hafa nóg borð pláss hér 220 00:09:06,980 --> 00:09:09,460 þannig að ég gæti sett Skyndipróf hvar ég vildi. 221 00:09:09,460 --> 00:09:10,620 Svo eins gæti farið hér. 222 00:09:10,620 --> 00:09:12,100 Zs gæti farið hér. 223 00:09:12,100 --> 00:09:13,230 Ms gæti farið hér. 224 00:09:13,230 --> 00:09:14,740 Og svo ég hafði smá auka pláss. 225 00:09:14,740 --> 00:09:18,740 En þetta er hluti af a svindla hægri nú vegna þess að þetta borð, ef ég virkilega 226 00:09:18,740 --> 00:09:22,720 hugsaði um það sem fylki, er bara fara að vera eitthvað fast stærð. 227 00:09:22,720 --> 00:09:25,380 >> Svo tæknilega, ef ég toga upp spurningakeppni annars nemandans 228 00:09:25,380 --> 00:09:28,490 og sjá, ó, þessi manneskja er nafn byrjar með A líka, 229 00:09:28,490 --> 00:09:30,980 Ég vil konar að setja það þar. 230 00:09:30,980 --> 00:09:34,740 En um leið og ég setti hana þar, ef Þessi tafla sýnir örugglega fylki, 231 00:09:34,740 --> 00:09:37,840 Ég ætla að vera hnekkir eða clobbering sá quiz þessa nemanda er. 232 00:09:37,840 --> 00:09:38,340 Hægri? 233 00:09:38,340 --> 00:09:41,972 Ef þetta er fylki, aðeins eitt getur fara í hvert af þessum frumum eða þætti. 234 00:09:41,972 --> 00:09:43,680 Og svo ég hef svona að velja og velja. 235 00:09:43,680 --> 00:09:45,735 >> Nú áðan konar sviknir og gerðu þetta eða I 236 00:09:45,735 --> 00:09:47,526 bara svona staflað þá er hér að ofan hvert annað. 237 00:09:47,526 --> 00:09:49,170 En það er ekki að fara að fljúga í kóða. 238 00:09:49,170 --> 00:09:52,260 Svo gæti ég setti annað nemandi hét 239 00:09:52,260 --> 00:09:54,964 er A ef allt sem ég þurfti er þetta boði borð pláss? 240 00:09:54,964 --> 00:09:57,880 Og ég hef notað þrjár rifa og það lítur út eins og það er bara nokkrum öðrum. 241 00:09:57,880 --> 00:09:58,959 Hvað gætir þú gert? 242 00:09:58,959 --> 00:09:59,834 Áhorfendur: [inaudible] 243 00:09:59,834 --> 00:10:00,565 244 00:10:00,565 --> 00:10:01,315 DAVID MALAN: Já. 245 00:10:01,315 --> 00:10:02,370 Kannski skulum halda bara það einfalt. 246 00:10:02,370 --> 00:10:02,660 Hægri? 247 00:10:02,660 --> 00:10:04,243 Það passar ekki þar sem ég vil að setja það. 248 00:10:04,243 --> 00:10:07,450 Þannig að ég ætla að setja það tæknilega þar sem B myndi fara. 249 00:10:07,450 --> 00:10:09,932 Nú, auðvitað, ég byrja að mála mig út í horn. 250 00:10:09,932 --> 00:10:11,890 Ef ég fæ að nemandi en nafn er í raun B, 251 00:10:11,890 --> 00:10:14,840 nú B er að fara að vera flutt smá áfram, sem gæti gerzt, Já, 252 00:10:14,840 --> 00:10:17,530 ef þetta er B, nú hefur það að fara hér. 253 00:10:17,530 --> 00:10:20,180 >> Og svo þetta mjög fljótt gæti orðið erfið, 254 00:10:20,180 --> 00:10:23,850 en það er tækni sem raunverulega er vísað til sem línuleg leit, 255 00:10:23,850 --> 00:10:26,650 þar sem þú telur bara þín array að vera meðfram línu. 256 00:10:26,650 --> 00:10:29,680 Og þú bara svona rannsaka eða skoða hvert laus frumefni 257 00:10:29,680 --> 00:10:31,360 leita laust staðnum. 258 00:10:31,360 --> 00:10:34,010 Og um leið og þú finnur einn, falla þér það þar. 259 00:10:34,010 --> 00:10:38,390 >> Nú, en verðið er greitt núna fyrir þessa lausn er það? 260 00:10:38,390 --> 00:10:41,300 Við erum með fasta stærð array, og þegar ég setja nöfn 261 00:10:41,300 --> 00:10:44,059 inn í það, að minnsta kosti í upphafi, hvað er Keyrslutíminn ísetningar 262 00:10:44,059 --> 00:10:46,350 fyrir að setja stúdent Skyndipróf í rétta fötu? 263 00:10:46,350 --> 00:10:48,710 264 00:10:48,710 --> 00:10:50,002 Big O hvað? 265 00:10:50,002 --> 00:10:51,147 >> Áhorfendur: n. 266 00:10:51,147 --> 00:10:52,480 DAVID MALAN: Ég heyrði stór O á n. 267 00:10:52,480 --> 00:10:53,530 268 00:10:53,530 --> 00:10:54,300 Ekki satt. 269 00:10:54,300 --> 00:10:56,490 En við munum stríða sundur hvers vegna í aðeins augnablik. 270 00:10:56,490 --> 00:10:57,702 Hvað annað gæti það verið? 271 00:10:57,702 --> 00:10:58,755 >> Áhorfendur: [inaudible] 272 00:10:58,755 --> 00:11:00,380 DAVID MALAN: Og láta mig gera það sjónrænt. 273 00:11:00,380 --> 00:11:04,720 Svo Segjum þetta er bókstafurinn S. 274 00:11:04,720 --> 00:11:05,604 >> Áhorfendur: Það er eitt. 275 00:11:05,604 --> 00:11:06,520 DAVID MALAN: Það er eitt. 276 00:11:06,520 --> 00:11:06,710 Hægri? 277 00:11:06,710 --> 00:11:08,950 Þetta er fylki, sem þýðir að við höfum handahófi aðgang. 278 00:11:08,950 --> 00:11:11,790 Og ef við hugsum um þetta núll og þetta sem 25, 279 00:11:11,790 --> 00:11:13,800 og við skiljum að, ó, hér er inntak S mitt, 280 00:11:13,800 --> 00:11:16,350 Ég get vissulega umbreyta S, sem ASCII staf, 281 00:11:16,350 --> 00:11:18,540 til samsvarandi fjölda milli núll og 25 282 00:11:18,540 --> 00:11:20,910 og þá strax setja það þar sem það tilheyrir. 283 00:11:20,910 --> 00:11:26,120 >> En auðvitað, um leið og ég kem á annar maður, sem er nafn er A eða B eða C 284 00:11:26,120 --> 00:11:29,300 lokum, ef ég hef notað línuleg leit og lausnin mín, 285 00:11:29,300 --> 00:11:31,360 Keyrslutíminn af innsetning í versta tilfelli 286 00:11:31,360 --> 00:11:33,120 er í raun að fara að flytjast í það? 287 00:11:33,120 --> 00:11:34,270 288 00:11:34,270 --> 00:11:36,045 Og ég gerði heyra það hér rétt snemma. 289 00:11:36,045 --> 00:11:36,920 Áhorfendur: [inaudible] 290 00:11:36,920 --> 00:11:41,620 DAVID MALAN: Svo það er n örugglega einu þú ert nægilega stór gögn sett. 291 00:11:41,620 --> 00:11:44,410 Svo, annars vegar, ef array er nógu stór 292 00:11:44,410 --> 00:11:48,287 og gögn er dreifður nóg, þú fá þessa fallegu stöðugt sinn. 293 00:11:48,287 --> 00:11:50,620 En um leið og þú byrjar að fá fleiri og fleiri þætti, 294 00:11:50,620 --> 00:11:53,200 og bara tölfræðilega þú færð fleiri einstaklingar með bréfi 295 00:11:53,200 --> 00:11:56,030 A eins og nafn þeirra eða bréf B, gæti það hugsanlega 296 00:11:56,030 --> 00:11:57,900 flytjast í fúlustu línuleg. 297 00:11:57,900 --> 00:11:59,640 Svo ekki alveg fullkominn. 298 00:11:59,640 --> 00:12:00,690 Svo gætum við gert betur? 299 00:12:00,690 --> 00:12:03,210 >> Jæja, hvað var okkar lausn fyrir þegar við 300 00:12:03,210 --> 00:12:06,820 langar að hafa meiri kraft en eitthvað eins og array leyft? 301 00:12:06,820 --> 00:12:08,085 302 00:12:08,085 --> 00:12:08,960 Áhorfendur: [inaudible] 303 00:12:08,960 --> 00:12:10,030 DAVID MALAN: Hvað gerði við kynna? 304 00:12:10,030 --> 00:12:10,530 Já. 305 00:12:10,530 --> 00:12:11,430 Svo tengd lista. 306 00:12:11,430 --> 00:12:14,430 Jæja, við skulum sjá hvað tengdur listi gæti gert fyrir okkur í staðinn. 307 00:12:14,430 --> 00:12:17,630 Jæja, láttu mig leggja til að vér teikna myndina sem hér segir. 308 00:12:17,630 --> 00:12:19,620 Nú er þetta öðruvísi mynd frá dæmi 309 00:12:19,620 --> 00:12:24,750 frá mismunandi texta, reyndar, að er í raun að nota fjölbreytta stærð 31. 310 00:12:24,750 --> 00:12:28,220 Og þessi höfundur einfaldlega ákvað að kjötkássa strengi 311 00:12:28,220 --> 00:12:32,430 ekki byggð á nöfn viðkomandi, en byggt á birthdates sínum. 312 00:12:32,430 --> 00:12:35,680 Óháð mánaðarins, mynstrağur þeir Ef þú ert fæddur á fyrsta mánuði 313 00:12:35,680 --> 00:12:39,580 eða 31. mánuð, höfundur mun kjötkássa við þann verðmæti, 314 00:12:39,580 --> 00:12:44,154 svo sem til að dreifa nöfnum út smá meira en bara 26 blettur gæti leyfa. 315 00:12:44,154 --> 00:12:47,320 Og kannski er það svolítið jafnari en að fara með stafrófsröð bréf, 316 00:12:47,320 --> 00:12:50,236 því að sjálfsögðu að það er sennilega fleiri fólk í heiminum með nöfn 317 00:12:50,236 --> 00:12:54,020 að byrja með A en vissulega nokkrar aðrar bókstafir. 318 00:12:54,020 --> 00:12:56,380 Svo kannski er þetta svolítið jafnari, miðað 319 00:12:56,380 --> 00:12:58,640 jafnri dreifingu barna yfir mánuð. 320 00:12:58,640 --> 00:12:59,990 >> En, auðvitað, þetta er enn ófullkomin. 321 00:12:59,990 --> 00:13:00,370 Hægri? 322 00:13:00,370 --> 00:13:01,370 Við erum með árekstra. 323 00:13:01,370 --> 00:13:04,680 Margfeldi fólk í þessu gagnagrind eru enn 324 00:13:04,680 --> 00:13:08,432 með sama fæðingardag að minnsta kosti þú ert óháð mánuði. 325 00:13:08,432 --> 00:13:09,640 En hvað hefur höfundur gert? 326 00:13:09,640 --> 00:13:13,427 Jæja, það lítur út eins og við höfum fjölda á vinstri hönd hlið dregin lóðrétt, 327 00:13:13,427 --> 00:13:15,010 en það er bara flutningur flytjanda. 328 00:13:15,010 --> 00:13:18,009 Það skiptir ekki máli hvað átt þú draga fylki, það er samt array. 329 00:13:18,009 --> 00:13:20,225 Hvað er þetta fylki af virðist? 330 00:13:20,225 --> 00:13:21,500 >> Áhorfendur: tengda listanum. 331 00:13:21,500 --> 00:13:21,650 >> DAVID MALAN: Já. 332 00:13:21,650 --> 00:13:23,490 Það lítur út eins og það er array af tengda listanum. 333 00:13:23,490 --> 00:13:26,490 Svo aftur, að þessum tímapunkti af tagi að nota þessi gögn uppbygging nú 334 00:13:26,490 --> 00:13:28,550 sem hráefni til fleiri áhugaverðar lausnir, 335 00:13:28,550 --> 00:13:30,862 þú getur alveg tekið grundvallaratriði, eins og fjölda, 336 00:13:30,862 --> 00:13:33,320 og þá taka eitthvað meira áhugavert eins tengda listanum 337 00:13:33,320 --> 00:13:36,660 og jafnvel sameina þær í enn áhugaverðari gagnagrind. 338 00:13:36,660 --> 00:13:39,630 Og reyndar, þetta of myndi vera kölluð kjötkássa borð, 339 00:13:39,630 --> 00:13:42,610 þar sem array er virkilega kjötkássa borð, 340 00:13:42,610 --> 00:13:45,600 en það kjötkássa borð hefur keðjur, svo að segja, 341 00:13:45,600 --> 00:13:50,220 sem geta vaxið eða skreppa byggt á fjöldi staka sem þú vilt setja inn. 342 00:13:50,220 --> 00:13:52,990 >> Nú, í samræmi við það, hvað er Keyrslutíminn núna? 343 00:13:52,990 --> 00:13:58,030 Ef ég vil setja einhvern sem afmæli er 31. október, 344 00:13:58,030 --> 00:13:59,040 hvar hann eða hún að fara? 345 00:13:59,040 --> 00:14:00,530 346 00:14:00,530 --> 00:14:01,030 Allt í lagi. 347 00:14:01,030 --> 00:14:02,819 Á mjög botn þar sem það segir 31. 348 00:14:02,819 --> 00:14:03,610 Og það er fullkominn. 349 00:14:03,610 --> 00:14:05,060 Það var stöðug skipti. 350 00:14:05,060 --> 00:14:08,760 En hvað ef við finnum einhvern annan sem afmæli er, við skulum sjá, 351 00:14:08,760 --> 00:14:10,950 Október, nóvember, desember 31? 352 00:14:10,950 --> 00:14:12,790 Hvar er hann eða hún að fara? 353 00:14:12,790 --> 00:14:13,290 Sami hlutur. 354 00:14:13,290 --> 00:14:13,970 Tvö skref þó. 355 00:14:13,970 --> 00:14:15,303 Það er stöðug þó er það ekki? 356 00:14:15,303 --> 00:14:16,360 357 00:14:16,360 --> 00:14:16,860 Allt í lagi. 358 00:14:16,860 --> 00:14:17,840 Á því augnabliki sem það er. 359 00:14:17,840 --> 00:14:20,570 En í almennu tilfelli, fleira fólk við að bæta við, 360 00:14:20,570 --> 00:14:23,790 probabilistically, ætlum við að fara að fá fleiri og fleiri árekstrar. 361 00:14:23,790 --> 00:14:26,820 >> Nú er þetta svolítið betra því tæknilega 362 00:14:26,820 --> 00:14:34,580 nú keðjur mín gæti verið í versta hversu lengi? 363 00:14:34,580 --> 00:14:38,890 Ef ég set inn n fólk í þetta meira háþróuð gagnagrind, n fólk, 364 00:14:38,890 --> 00:14:41,080 í versta tilfelli það er að fara að vera n. 365 00:14:41,080 --> 00:14:41,815 Hvers vegna? 366 00:14:41,815 --> 00:14:43,332 >> Áhorfendur: Vegna þess að ef allir hefur sömu afmæli, 367 00:14:43,332 --> 00:14:44,545 þeir eru að fara að vera ein lína. 368 00:14:44,545 --> 00:14:45,420 DAVID MALAN: Perfect. 369 00:14:45,420 --> 00:14:47,480 Það gæti verið svolítið háttuð, en sannarlega í versta tilfelli, 370 00:14:47,480 --> 00:14:50,117 ef allir eru með sama afmæli, ljósi inntak sem þú hefur, 371 00:14:50,117 --> 00:14:51,950 þú ert að fara að hafa a gegnheill löng keðja. 372 00:14:51,950 --> 00:14:54,241 Og svo, þú kalla það kjötkássa borð, en í raun er það 373 00:14:54,241 --> 00:14:56,810 bara gegnheill tengda listanum með a heild einhver fjöldi af sóa pláss. 374 00:14:56,810 --> 00:15:00,460 En almennt, ef við gerum ráð fyrir að amk afmælisdagar eru uniform-- 375 00:15:00,460 --> 00:15:01,750 og það er sennilega ekki. 376 00:15:01,750 --> 00:15:02,587 Ég er að gera það upp. 377 00:15:02,587 --> 00:15:04,420 En ef við gerum ráð fyrir, að sakir umræðu 378 00:15:04,420 --> 00:15:07,717 að þeir eru, þá í orði, ef þetta er lóðrétt framsetning 379 00:15:07,717 --> 00:15:11,050 í fylkinu, og þá vonandi þú ert fara að fá keðjur sem eru, þú veist, 380 00:15:11,050 --> 00:15:15,880 um það bil sama lengd þar sem hver af þessarra dagur mánaðarins. 381 00:15:15,880 --> 00:15:19,930 >> Nú ef það er 31 dagar í mánuðinum, sem þýðir hlaupandi tíma minn raunverulega 382 00:15:19,930 --> 00:15:25,230 er stór O n yfir 31, sem finnst betra en línuleg. 383 00:15:25,230 --> 00:15:27,950 En hvað var einn af okkar skuldbindingar a par af vika 384 00:15:27,950 --> 00:15:31,145 síðan þegar það kom til að tjá Keyrslutíminn af reiknirit? 385 00:15:31,145 --> 00:15:33,450 386 00:15:33,450 --> 00:15:35,190 Bara aðeins að líta á öfluga tíma. 387 00:15:35,190 --> 00:15:35,690 Hægri? 388 00:15:35,690 --> 00:15:37,400 31 er örugglega gagnlegt. 389 00:15:37,400 --> 00:15:39,610 En þetta er samt stór O á n. 390 00:15:39,610 --> 00:15:41,730 En einn af þeim þemum af Heimadæmi fimm 391 00:15:41,730 --> 00:15:43,950 er að fara að vera að viðurkenna að algerlega, 392 00:15:43,950 --> 00:15:47,320 aðfellu, fræðilega þessi gögn uppbygging 393 00:15:47,320 --> 00:15:50,470 er ekki betri en bara einn gegnheill tengda listanum. 394 00:15:50,470 --> 00:15:53,550 Og reyndar, í versta tilfelli, þetta kjötkássa borð gæti flytjast inn í það. 395 00:15:53,550 --> 00:15:57,620 >> En í hinum raunverulega heimi, með okkur menn að eigin Macs eða tölvur eða hvað 396 00:15:57,620 --> 00:16:01,240 og eru í gangi raunverulega heimi hugbúnaður á alvöru World Data, 397 00:16:01,240 --> 00:16:03,260 sem reiknirit ætlar þú að kjósa? 398 00:16:03,260 --> 00:16:09,180 Sá sem tekur enda sporin eða einn sem tekur n deilt með 31. skrefum 399 00:16:09,180 --> 00:16:12,900 að finna einhverja stykki af gögnum eða að líta upp einhverjar upplýsingar? 400 00:16:12,900 --> 00:16:16,580 Ég meina, endilega 31 gerðum munur á hinum raunverulega heimi. 401 00:16:16,580 --> 00:16:18,540 Það er 31 sinnum hraðar. 402 00:16:18,540 --> 00:16:20,880 Og við mennirnir eru vissulega fara að þakka það. 403 00:16:20,880 --> 00:16:23,004 >> Svo átta sig á slag þar á milli í raun 404 00:16:23,004 --> 00:16:25,920 tala um hluti fræðilega og aðfellu sem vissulega 405 00:16:25,920 --> 00:16:28,760 hefur gildi eins og við höfum séð, en í hinum raunverulega heimi, 406 00:16:28,760 --> 00:16:32,930 Ef þér þykir vænt um bara gera manna ánægður fyrir almenna inntak, 407 00:16:32,930 --> 00:16:36,010 þú might mjög vel vilja til að samþykkja Sú staðreynd að, já, þetta er línuleg, 408 00:16:36,010 --> 00:16:38,360 en það er 31 sinnum hraðar en línulegur væri. 409 00:16:38,360 --> 00:16:41,610 Og enn betra, við ekki bara að gera eitthvað handahófskennt eins afmælisdeginum, 410 00:16:41,610 --> 00:16:44,030 við gætum eytt smá meiri tíma og slungin 411 00:16:44,030 --> 00:16:47,140 og hugsa um hvað við gætum gert, gefið nafn einstaklingsins og kannski 412 00:16:47,140 --> 00:16:50,130 fæðingardegi þeirra að sameina þá efni til að reikna út eitthvað 413 00:16:50,130 --> 00:16:52,720 sem er sannarlega meira samræmda og minna jaggy, 414 00:16:52,720 --> 00:16:56,250 svo að segja en þessa mynd nú bendir það gæti verið. 415 00:16:56,250 --> 00:16:57,750 Hvernig gætum við innleiða þetta í kóða? 416 00:16:57,750 --> 00:17:00,280 Jæja, láttu mig leggja til að vér bara láni sumir setningafræði við höfum 417 00:17:00,280 --> 00:17:01,799 notað nokkrum sinnum hingað til. 418 00:17:01,799 --> 00:17:03,590 Og ég ætla að skilgreina hnút, sem aftur 419 00:17:03,590 --> 00:17:06,812 er almenn orð fyrir bara gámur fyrir sumir gögn uppbygging. 420 00:17:06,812 --> 00:17:09,020 Ég ætla að leggja til að a band er að fara í það. 421 00:17:09,020 --> 00:17:11,369 En við erum að fara að byrja að taka þá þjálfun hjól burt núna. 422 00:17:11,369 --> 00:17:13,230 >> Ekkert meira CS50 bókasafn raun, nema þú viljir 423 00:17:13,230 --> 00:17:15,230 að nota það til endanlegrar þína Verkefnið, sem er fínn, 424 00:17:15,230 --> 00:17:18,569 en nú erum við að fara að draga til baka fortjald og segja að það er bara bleikju stjarna. 425 00:17:18,569 --> 00:17:22,069 Þannig að orði að það sé að fara að nafn viðkomandi ræðir. 426 00:17:22,069 --> 00:17:25,079 Og nú hef ég tengil hér í næsta hnút 427 00:17:25,079 --> 00:17:28,170 þannig að þetta tákna hver af tengipunkta 428 00:17:28,170 --> 00:17:30,950 í keðjunni, hugsanlega, af tengdum lista. 429 00:17:30,950 --> 00:17:34,090 >> Og nú hvernig ég lýsa kjötkássa borð sjálft? 430 00:17:34,090 --> 00:17:36,660 Hvernig get ég lýsa alla þessa múra? 431 00:17:36,660 --> 00:17:40,960 Jæja, í raun, eins og ég notaði músina við bara fyrsta þáttur lista 432 00:17:40,960 --> 00:17:44,510 áður, á sama hátt get ég sagt bara Ég þarf bara fullt af ábendingum 433 00:17:44,510 --> 00:17:46,270 að framkvæma þetta allt kjötkássa töflunni. 434 00:17:46,270 --> 00:17:49,484 Ég ætla að hafa array kallað borð fyrir kjötkássa borð. 435 00:17:49,484 --> 00:17:50,900 Það er að fara að vera af stærð getu. 436 00:17:50,900 --> 00:17:52,525 Það er hversu margir þættir geta passa í það. 437 00:17:52,525 --> 00:17:56,180 Og hver af þeim þáttum í þessari array er að fara til vera a hnút stjarna. 438 00:17:56,180 --> 00:17:56,810 Hvers vegna? 439 00:17:56,810 --> 00:18:00,160 Jæja, og á þessari mynd, það sem ég er framkvæmd kjötkássa borð eins 440 00:18:00,160 --> 00:18:04,330 raun í byrjun er bara Fylkið sem við höfum dregið lóðrétt, 441 00:18:04,330 --> 00:18:06,820 hvert sem ferninga táknar bendi. 442 00:18:06,820 --> 00:18:09,170 Að þau sem hafa skástrik gegnum þá eru bara null. 443 00:18:09,170 --> 00:18:11,410 Og þau sem hafa Örvar að fara til hægri 444 00:18:11,410 --> 00:18:16,140 eru raunveruleg ábendingum að raunverulegum hnúður, Ergo upphaf tengda listanum. 445 00:18:16,140 --> 00:18:19,050 >> Svo hér, þá er, hvernig við gætum innleiða kjötkássa töflu sem 446 00:18:19,050 --> 00:18:21,580 útfærir aðskilda chaining. 447 00:18:21,580 --> 00:18:22,840 Nú getum við gert betur? 448 00:18:22,840 --> 00:18:25,632 Allt í lagi ég lofaði síðasta skipti sem við gætum náð föstu tíma. 449 00:18:25,632 --> 00:18:27,381 Og ég konar gaf þér föstu tíma hér, 450 00:18:27,381 --> 00:18:29,850 en þá sagði í raun ekki föstu tíma því það er enn 451 00:18:29,850 --> 00:18:31,890 háð allra fjöldi staka 452 00:18:31,890 --> 00:18:34,500 þú ert inputting inn gögn uppbygging. 453 00:18:34,500 --> 00:18:35,980 En geri ráð fyrir að við gerðum þetta. 454 00:18:35,980 --> 00:18:39,550 Leyfðu mér að fara aftur á skjáinn hérna. 455 00:18:39,550 --> 00:18:44,520 Leyfðu mér einnig verkefni þessu upp hér, tær skjáinn og býst ég gerði þetta. 456 00:18:44,520 --> 00:18:49,300 Segjum að ég vildi setja nafn Daven í inn gögn uppbygging minn. 457 00:18:49,300 --> 00:18:52,100 >> Þannig að ég vil að setja band Daven í gagnagrind. 458 00:18:52,100 --> 00:18:54,370 Hvað ef ég nota ekki kjötkássa borð, en ég nota 459 00:18:54,370 --> 00:18:56,980 eitthvað sem er meira tré-eins eins ættartré, þar 460 00:18:56,980 --> 00:18:59,670 þið hafið einhverjar rót á hafið efst og þá hnúður og blöð 461 00:18:59,670 --> 00:19:01,440 að fara niður og út á við. 462 00:19:01,440 --> 00:19:04,450 Segjum svo, að ég langar að setja inn Daven er 463 00:19:04,450 --> 00:19:06,430 í hvað er nú tómt listi. 464 00:19:06,430 --> 00:19:09,780 Ég ætla að gera eftirfarandi: Ég er fara að búa til hnút í þessari fjölskyldu 465 00:19:09,780 --> 00:19:15,170 tré-eins og gögn uppbygging sem lítur svolítið eins og þetta, sem hver um sig 466 00:19:15,170 --> 00:19:19,640 ferhyrninga hefur, segjum, Fyrir nú 26 þættir í henni. 467 00:19:19,640 --> 00:19:21,650 Og hver af frumunum í þessu fylki er að fara 468 00:19:21,650 --> 00:19:23,470 að tákna stafinn af stafrófinu. 469 00:19:23,470 --> 00:19:28,190 >> Sérstaklega, ég er að fara að meðhöndla þetta er A, þá B, þá C, þá D, 470 00:19:28,190 --> 00:19:29,310 þetta hér. 471 00:19:29,310 --> 00:19:32,940 Þannig að þetta er að fara að í raun tákna stafinn D. 472 00:19:32,940 --> 00:19:36,040 En að setja alla Daven er nafn ég þarf að gera aðeins meira. 473 00:19:36,040 --> 00:19:37,840 Þannig að ég ætla fyrst að fara til kjötkássa, svo að segja. 474 00:19:37,840 --> 00:19:41,049 Ég ætla að horfa á fyrsta staf í Daven, sem er augljóslega D, 475 00:19:41,049 --> 00:19:42,840 og ég ætla að úthluta hnút sem lítur 476 00:19:42,840 --> 00:19:45,570 eins this-- stórt rétthyrning stór nóg að passa allt stafrófið. 477 00:19:45,570 --> 00:19:47,140 >> Nú D er gert. 478 00:19:47,140 --> 00:19:49,720 Nú er A. D-A-V-E-N markmiðið. 479 00:19:49,720 --> 00:19:51,220 Svo nú hvað ég ætla að gera er þetta. 480 00:19:51,220 --> 00:19:54,027 Um leið og ég byrjaði D tilkynningu það er engin bendi þar. 481 00:19:54,027 --> 00:19:56,860 Það er sorp gildi um þessar mundir, eða ég gæti frumstilla það að núll. 482 00:19:56,860 --> 00:19:59,630 En láta mig halda áfram með þessi hugmynd um að byggja upp tré. 483 00:19:59,630 --> 00:20:04,260 Leyfðu mér að úthluta annað af þessum hnúður sem eru 26 einingar í henni. 484 00:20:04,260 --> 00:20:05,150 >> Og þú veist hvað? 485 00:20:05,150 --> 00:20:09,130 Ef þetta er bara hnútur í minni sem Ég búin með malloc, með strúktúr 486 00:20:09,130 --> 00:20:11,240 eins og við munum fljótlega sjá, Ég ætla að gera this-- 487 00:20:11,240 --> 00:20:14,450 Ég ætla að draga ör úr hlutur sem fulltrúi D niður 488 00:20:14,450 --> 00:20:15,860 þessa nýju hnút. 489 00:20:15,860 --> 00:20:19,240 Og nú, fyrst næst stafurinn í nafni Daven er, 490 00:20:19,240 --> 00:20:24,150 V-- D-A-V-- ég ætla að fara á undan og draga annað hnút eins og þetta, 491 00:20:24,150 --> 00:20:30,150 þar, V þætti hér, sem við munum draga fyrir instance-- Úpps. 492 00:20:30,150 --> 00:20:31,020 Við munum ekki draga það. 493 00:20:31,020 --> 00:20:31,936 Það er að fara að fara hér. 494 00:20:31,936 --> 00:20:32,890 495 00:20:32,890 --> 00:20:35,712 >> Svo ætlum við að telja þetta vera V. 496 00:20:35,712 --> 00:20:44,920 Og svo niður hér við erum að fara að kemba niður úr V í það sem við munum íhuga E. 497 00:20:44,920 --> 00:20:50,100 Og síðan frá hér við erum að fara að fara hafa einn af þessum hnúður hér. 498 00:20:50,100 --> 00:20:52,930 Og nú erum við með spurningu til að svara. 499 00:20:52,930 --> 00:20:57,840 Ég þarf einhvern veginn til kynna að við erum í lok band Daven. 500 00:20:57,840 --> 00:20:59,490 Svo ég gæti bara láta það null. 501 00:20:59,490 --> 00:21:02,670 >> En hvað ef við höfum Daven er fullt nafn líka, sem 502 00:21:02,670 --> 00:21:04,280 er, eins og við höfum sagt, Davenport? 503 00:21:04,280 --> 00:21:06,970 Svo hvað ef Daven er raun hlutstreng, 504 00:21:06,970 --> 00:21:08,960 Forskeyti af miklu lengri streng? 505 00:21:08,960 --> 00:21:11,450 Við getum ekki bara varanlega segja ekkert er að fara 506 00:21:11,450 --> 00:21:14,410 að fara þangað, vegna þess að við gátum aldrei að setja inn orð eins Davenport 507 00:21:14,410 --> 00:21:15,840 í þessum gögnum uppbyggingu 508 00:21:15,840 --> 00:21:19,560 >> Svo það sem við gætum gert er í staðinn meðhöndla hvert þessara þátta 509 00:21:19,560 --> 00:21:22,170 eins kannski að hafa tvö þættir innra með þeim. 510 00:21:22,170 --> 00:21:24,810 Eitt er bendillinn, örugglega, eins og ég hef verið að gera. 511 00:21:24,810 --> 00:21:27,100 Svo hver af þessum kassa er ekki bara einn klefi. 512 00:21:27,100 --> 00:21:29,855 En hvað ef efst one-- botn einn er 513 00:21:29,855 --> 00:21:32,230 fara að vera núll, því það er engin Davenport bara ennþá. 514 00:21:32,230 --> 00:21:34,197 Hvað ef efst einn er einhver sérstakur gildi? 515 00:21:34,197 --> 00:21:36,530 Og það er að fara til vera a lítill erfitt að draga það þessari stærð. 516 00:21:36,530 --> 00:21:38,130 En geri ráð fyrir að það er bara merkið. 517 00:21:38,130 --> 00:21:38,920 Athuga. 518 00:21:38,920 --> 00:21:44,230 D-A-V-E-N er band í þessum gögnum uppbyggingu. 519 00:21:44,230 --> 00:21:48,350 >> Sama tíma, ef ég hefði meira pláss hér, gæti ég gert P-O-R-T, 520 00:21:48,350 --> 00:21:52,650 og ég gæti sett stöðva í hnút sem hefur stafinn T aftast. 521 00:21:52,650 --> 00:21:55,460 Þannig að þetta er gegnheill flókin-útlit gögn uppbygging. 522 00:21:55,460 --> 00:21:57,210 Og rithönd mín vissulega ekki hjálpa. 523 00:21:57,210 --> 00:22:00,043 En ef ég vildi setja eitthvað annað, íhuga hvað við myndum gera. 524 00:22:00,043 --> 00:22:03,370 Ef við vildum að setja Davíð í, viljum við fylgja sömu rökfræði, D-A-V, 525 00:22:03,370 --> 00:22:08,802 en nú ég myndi benda á næsta þáttur ekki frá E, en frá I til D. 526 00:22:08,802 --> 00:22:10,760 Þannig að það er að fara að vera fleiri hnútar í þessu tré. 527 00:22:10,760 --> 00:22:12,325 Við ætlum að hafa hringt malloc meira. 528 00:22:12,325 --> 00:22:14,700 En ég vil ekki að gera a Heill skipta um þessa mynd. 529 00:22:14,700 --> 00:22:17,710 Svo skulum staðinn líta á einn sem hefur verið fyrirfram mótuð 530 00:22:17,710 --> 00:22:21,810 svona með ekki punktur, punktur, punktar, en bara skammstafanir fylki. 531 00:22:21,810 --> 00:22:23,950 En hver af hnúður í þessu tré upp hér 532 00:22:23,950 --> 00:22:26,700 táknar sömu thing-- fylki Ray stærð 26. 533 00:22:26,700 --> 00:22:28,860 >> Eða ef við viljum vera virkilega réttur nú, hvað 534 00:22:28,860 --> 00:22:30,790 ef nafn einhvers sem úrfellingarmerki, skulum 535 00:22:30,790 --> 00:22:35,560 gera ráð fyrir að hver hnútur hefur í raun eins 27 Vísitölur í henni, ekki bara 26. 536 00:22:35,560 --> 00:22:42,020 Þannig að þetta nú er að fara til vera a gögn uppbygging kallast trie-- T-R-I-E. 537 00:22:42,020 --> 00:22:46,120 A trie, sem er talið sögulega snjall nafn fyrir tré 538 00:22:46,120 --> 00:22:49,040 sem er bjartsýni fyrir sókn, sem að sjálfsögðu, 539 00:22:49,040 --> 00:22:50,870 er stafsett með I-E svo það er trie. 540 00:22:50,870 --> 00:22:52,710 En það er saga af trie. 541 00:22:52,710 --> 00:22:55,860 >> Svo er a trie Þetta tré-eins og gögn uppbyggingu eins ættartré 542 00:22:55,860 --> 00:22:57,510 að lokum hegðar sér eins og þessi. 543 00:22:57,510 --> 00:23:00,890 Og hér er bara annað dæmi um a allt fullt af nöfnum annarra. 544 00:23:00,890 --> 00:23:03,540 En spurningin núna hendi er hvað hefur 545 00:23:03,540 --> 00:23:08,070 við fengið með því að kynna öllum líkindum meira flókið gagnagrind, og einn, 546 00:23:08,070 --> 00:23:09,870 hreinskilnislega, sem notar mikið minni. 547 00:23:09,870 --> 00:23:11,703 >> Því jafnvel þó, í augnablikinu, ég er bara 548 00:23:11,703 --> 00:23:15,050 nota D's músina og A og V og Es og Ns, 549 00:23:15,050 --> 00:23:16,700 Ég er að sóa Heck fullt af minni. 550 00:23:16,700 --> 00:23:18,030 551 00:23:18,030 --> 00:23:22,660 En þar sem ég eyða eitt úrræði, ÉG hafa tilhneigingu til að gera ná til baka annað. 552 00:23:22,660 --> 00:23:26,020 Svo ef ég ætla að eyða meira pláss, hvað er líklega von? 553 00:23:26,020 --> 00:23:27,407 Að ég er að eyða minna það? 554 00:23:27,407 --> 00:23:28,240 Áhorfendur: Minni tíma. 555 00:23:28,240 --> 00:23:28,990 DAVID MALAN: Time. 556 00:23:28,990 --> 00:23:30,320 Nú hvers vegna gæti það verið? 557 00:23:30,320 --> 00:23:33,880 Jæja, hvað er innsetning tíma, í skilmálar af stór O nú, 558 00:23:33,880 --> 00:23:37,660 um nafn eins Daven eða Davenport eða David? 559 00:23:37,660 --> 00:23:39,340 Jæja, Daven var fimm skrefum. 560 00:23:39,340 --> 00:23:42,350 Davenport væri níu skref, svo það væri nokkur atriði. 561 00:23:42,350 --> 00:23:44,250 David yrði fimm spöl. 562 00:23:44,250 --> 00:23:47,230 Þannig að þeir eru steypu tölur, en örugglega er það 563 00:23:47,230 --> 00:23:49,550 skilgreina efri mörk á lengd nafni einhvers. 564 00:23:49,550 --> 00:23:52,240 Og reyndar, í því vandamáli sett af fimm forskrift, 565 00:23:52,240 --> 00:23:54,050 við erum að fara að leggja að það er eitthvað 566 00:23:54,050 --> 00:23:55,470 það er 40-sumir-stakur persónur. 567 00:23:55,470 --> 00:23:58,180 >> Raunhæft, enginn hefur óendanlega lengi nafn, 568 00:23:58,180 --> 00:24:01,542 sem er að segja að lengd a nafn eða lengd streng við gæti 569 00:24:01,542 --> 00:24:03,750 hafa viss ástand uppbygging er að öllum líkindum hvað? 570 00:24:03,750 --> 00:24:05,550 571 00:24:05,550 --> 00:24:06,250 Það er stöðug. 572 00:24:06,250 --> 00:24:06,430 Hægri? 573 00:24:06,430 --> 00:24:09,310 Það gæti verið stór fasti eins 40-eitthvað, en það er stöðug. 574 00:24:09,310 --> 00:24:13,752 Og það hefur engin ánauðar á hversu margar önnur nöfn eru í þessum gögnum uppbyggingu. 575 00:24:13,752 --> 00:24:15,460 Með öðrum orðum, ef I vildi nú setja 576 00:24:15,460 --> 00:24:20,540 Colton eða Gabriel eða Rob eða Zamyla eða Alison eða Belinda eða einhver önnur nöfn 577 00:24:20,540 --> 00:24:23,940 frá starfsfólki í þessum gögnum uppbygging, er í gangi tími 578 00:24:23,940 --> 00:24:26,750 að setja önnur nöfn að fara að vera á öllum áhrifum 579 00:24:26,750 --> 00:24:30,220 því hversu mörgum öðrum þáttum eru í gögn uppbygging þegar? 580 00:24:30,220 --> 00:24:31,040 Það er ekki. 581 00:24:31,040 --> 00:24:31,540 Hægri? 582 00:24:31,540 --> 00:24:36,150 Vegna þess að við erum í raun að nota þetta multi-lag kjötkássa töflunni. 583 00:24:36,150 --> 00:24:38,280 Og gangi tími eitthvað af þessum aðgerðum 584 00:24:38,280 --> 00:24:41,510 er háð ekki á fjölda þættir sem eru í gögn uppbygging 585 00:24:41,510 --> 00:24:43,090 eða sem eru loksins að fara að vera í gögn uppbygging, 586 00:24:43,090 --> 00:24:44,714 en á lengd hvað sérstaklega? 587 00:24:44,714 --> 00:24:46,500 588 00:24:46,500 --> 00:24:49,200 >> Strengurinn vera sett, sem gerir 589 00:24:49,200 --> 00:24:52,580 þetta aðfellu fasti time-- stór O einn. 590 00:24:52,580 --> 00:24:54,720 Og hreinskilnislega, bara í hinum raunverulega heimi, þetta 591 00:24:54,720 --> 00:24:58,380 þýðir að setja nafn Daven tekur eins og fimm skref, eða Davenport níu 592 00:24:58,380 --> 00:25:00,100 skref, eða David fimm skrefum. 593 00:25:00,100 --> 00:25:03,071 Það er laglegur fjári lítil gangi sinnum. 594 00:25:03,071 --> 00:25:05,320 Og reyndar, það er mjög gott, sérstaklega þegar 595 00:25:05,320 --> 00:25:08,126 það er ekki háð allra fjöldi staka í þar. 596 00:25:08,126 --> 00:25:10,500 Svo hvernig gæti við innleiða þetta konar uppbyggingu í kóða? 597 00:25:10,500 --> 00:25:12,900 Það er a lítill fleiri flókið, en samt er það 598 00:25:12,900 --> 00:25:15,050 bara beitingu undirstöðu kubbar. 599 00:25:15,050 --> 00:25:17,830 Ég ætla að endurskilgreina US hnút eins og hér segir: 600 00:25:17,830 --> 00:25:21,100 bool kallaði word-- og þetta mætti ​​nefna neitt. 601 00:25:21,100 --> 00:25:23,970 En bool táknar það sem ég dró sem hakað. 602 00:25:23,970 --> 00:25:24,490 Já. 603 00:25:24,490 --> 00:25:26,720 Þetta er í lok streng í þessum gögnum uppbyggingu. 604 00:25:26,720 --> 00:25:30,702 >> Og, auðvitað, hnúturinn stjörnu það er að vísa til barna. 605 00:25:30,702 --> 00:25:32,410 Og reyndar rétt eins fjölskyldu tré, þú 606 00:25:32,410 --> 00:25:34,370 myndi íhuga hnúður sem eru hangandi burt 607 00:25:34,370 --> 00:25:36,920 af the botn af einhverjum foreldri þáttur til að vera börn. 608 00:25:36,920 --> 00:25:40,510 Og svo börnin er að fara að vera fylki af 27, 27 einn 609 00:25:40,510 --> 00:25:41,680 bara að vera fyrir úrfellingarmerki. 610 00:25:41,680 --> 00:25:43,390 Við erum að fara að raða sérstakt tilfelli að. 611 00:25:43,390 --> 00:25:45,400 Svo þú getur haft viss nöfn með úrfellingarmerki. 612 00:25:45,400 --> 00:25:47,399 Kannski jafnvel bandstrik ættu fara í það, en þú munt 613 00:25:47,399 --> 00:25:50,330 sjá í p sett 5. við aðeins umönnun um bréfum og úrfellingarmerki. 614 00:25:50,330 --> 00:25:52,990 >> Og þá hvernig þú ert í forsvari gögnin uppbyggingu sig? 615 00:25:52,990 --> 00:25:56,454 Hvernig gera þú tákna rót þessarar trie, svo að segja? 616 00:25:56,454 --> 00:25:59,620 Jæja, bara eins og með tengda listanum, þú þurfa bendi á fyrstu frumefni. 617 00:25:59,620 --> 00:26:04,270 Með trie þú þarft bara einn bendi á rót þessa trie. 618 00:26:04,270 --> 00:26:07,290 Og þaðan sem þú getur kjötkássa leið niður dýpra og dýpra 619 00:26:07,290 --> 00:26:10,460 að öll önnur hnút í uppbyggingu. 620 00:26:10,460 --> 00:26:13,440 Svo einfaldlega með þetta getur að tákna að strúktúr. 621 00:26:13,440 --> 00:26:15,877 >> Nú Meanwhile-- Oh, spurningu. 622 00:26:15,877 --> 00:26:17,220 >> Áhorfendur: Hvað er bool orð? 623 00:26:17,220 --> 00:26:20,490 >> DAVID MALAN: Bool orð er bara þetta C holdgun 624 00:26:20,490 --> 00:26:22,920 af því sem ég lýsti í þessum kassa hér, þegar 625 00:26:22,920 --> 00:26:26,000 Ég byrjaði að skipta hvert af þættir í tveimur stykki Array er. 626 00:26:26,000 --> 00:26:27,600 Eitt er bendillinn í næsta hnút. 627 00:26:27,600 --> 00:26:30,280 The annar þarf að vera eitthvað eins og kassann 628 00:26:30,280 --> 00:26:33,770 að segja já, það er a Orðið Daven sem endar hér, 629 00:26:33,770 --> 00:26:35,610 vegna þess að við viljum ekki, Á því augnabliki, Dave. 630 00:26:35,610 --> 00:26:39,320 >> Jafnvel þótt Dave er að fara til vera a lögmæt orð, hann er ekki í trie 631 00:26:39,320 --> 00:26:39,830 enn. 632 00:26:39,830 --> 00:26:40,950 Og D er ekki orð. 633 00:26:40,950 --> 00:26:42,770 Og D-A er ekki orð eða nafn. 634 00:26:42,770 --> 00:26:45,020 Þannig að hakað sýnir aðeins einu sinni þig 635 00:26:45,020 --> 00:26:48,190 högg þessi hnútur er Fyrri slóð af stöfum 636 00:26:48,190 --> 00:26:50,700 raun band sem þú hefur sett inn. 637 00:26:50,700 --> 00:26:53,660 Svo er það allt bool það er að gera fyrir okkur. 638 00:26:53,660 --> 00:26:55,500 >> Allar aðrar spurningar um reynir? 639 00:26:55,500 --> 00:26:56,215 Já. 640 00:26:56,215 --> 00:26:58,035 >> Áhorfendur: Hvað er skarast? 641 00:26:58,035 --> 00:26:59,945 Hvað ef þú ert með Dave og Daven? 642 00:26:59,945 --> 00:27:00,820 DAVID MALAN: Perfect. 643 00:27:00,820 --> 00:27:02,580 Hvað ef þú ert með Dave og Daven? 644 00:27:02,580 --> 00:27:06,240 Þannig að ef við setja, segja gælunafni fyrir David-- Dave-- D-A-V-E? 645 00:27:06,240 --> 00:27:07,370 646 00:27:07,370 --> 00:27:08,700 Þetta er í raun frábær einfalt. 647 00:27:08,700 --> 00:27:10,325 Þannig að við erum bara að fara að taka fjögur skref. 648 00:27:10,325 --> 00:27:11,042 649 00:27:11,042 --> 00:27:15,847 D-A-V-E. Og hvað þarf ég að gera þegar ég lenti sem fjórða hnút? 650 00:27:15,847 --> 00:27:16,680 Bara að fara til að athuga. 651 00:27:16,680 --> 00:27:18,000 Við erum nú þegar gott að fara. 652 00:27:18,000 --> 00:27:18,840 Lokið. 653 00:27:18,840 --> 00:27:19,750 Fjögur skref. 654 00:27:19,750 --> 00:27:21,590 Constant tími aðfellu. 655 00:27:21,590 --> 00:27:26,300 Og nú höfum við til kynna að bæði Dave og Daven eru strengir á skipulagi. 656 00:27:26,300 --> 00:27:27,710 Svo ekki vandamál. 657 00:27:27,710 --> 00:27:30,200 Og taka eftir hvernig tilvist af Daven ekki gera það 658 00:27:30,200 --> 00:27:34,750 taka allir meiri tíma eða minna tími fyrir Dave og öfugt. 659 00:27:34,750 --> 00:27:36,000 >> Svo hvað annað getum við gert núna? 660 00:27:36,000 --> 00:27:40,680 Við höfum notað þessa samlíking áður bakka fulltrúi eitthvað. 661 00:27:40,680 --> 00:27:43,380 En það kemur í ljós að stafla af stæði er í raun 662 00:27:43,380 --> 00:27:47,187 sýnileg annars abstrakt gögnum type-- hærra stigi gögn uppbygging 663 00:27:47,187 --> 00:27:49,770 að í lok daginn er bara eins fjölda eða tengdan lista 664 00:27:49,770 --> 00:27:50,970 eða eitthvað meira mundane. 665 00:27:50,970 --> 00:27:53,270 En það er meira áhugavert hugmyndafræðilegs hugtak. 666 00:27:53,270 --> 00:27:56,440 A stafla, eins og þessir Bakkar hér í Mather, 667 00:27:56,440 --> 00:27:58,750 eru yfirleitt kallaðir bara that-- stafla. 668 00:27:58,750 --> 00:28:02,540 >> Og í þessari tegund af gögn uppbygging þú hefur tvær operations-- 669 00:28:02,540 --> 00:28:05,880 þú ert einn sem heitir ýta bæta eitthvað að stafla, 670 00:28:05,880 --> 00:28:08,320 eins og að setja annan bakka aftur á toppur af stafla. 671 00:28:08,320 --> 00:28:11,350 Og þá skjóta, sem þýðir að þú taka hæstur bakki burt. 672 00:28:11,350 --> 00:28:16,210 En hvað er lykillinn um stafla er að það er got this forvitinn eiginleika. 673 00:28:16,210 --> 00:28:19,560 Eins matsalur starfsfólk eru endurskipuleggja stæði fyrir næsta máltíð, 674 00:28:19,560 --> 00:28:21,380 hvað er að fara að vera satt um hvernig nemendur 675 00:28:21,380 --> 00:28:22,856 samskipti við þessum gögnum uppbyggingu? 676 00:28:22,856 --> 00:28:24,480 Áhorfendur: Þeir eru að fara að skjóta einn burt. 677 00:28:24,480 --> 00:28:26,550 DAVID MALAN: Hann ætlar að skjóta einn burt, vonandi á toppinn. 678 00:28:26,550 --> 00:28:28,910 Annars er það bara svona heimskur að fara alla leið til botns. 679 00:28:28,910 --> 00:28:29,070 Hægri? 680 00:28:29,070 --> 00:28:31,620 Gögnin uppbygging er í raun ekki að leyfa þér að grípa botn bakki amk 681 00:28:31,620 --> 00:28:32,520 auðveldlega. 682 00:28:32,520 --> 00:28:35,040 Svo er það þetta forvitinn eign til stafla 683 00:28:35,040 --> 00:28:39,730 að síðasta atriði í er fara til vera the fyrstur einn út. 684 00:28:39,730 --> 00:28:43,400 Og tölva vísindamenn kalla þetta LIFO-- varað í, fyrst út. 685 00:28:43,400 --> 00:28:45,540 Og það í raun er að hafa áhugavert forrit. 686 00:28:45,540 --> 00:28:50,090 Það er ekki endilega eins augljóst eins og sumir aðrir, en það getur reyndar verið gagnlegt, 687 00:28:50,090 --> 00:28:54,040 og það getur reyndar verið útfærð í nokkra mismunandi vegu. 688 00:28:54,040 --> 00:28:58,550 >> Svo einn, og í raun, láta mér ekki að kafa inn í það. 689 00:28:58,550 --> 00:28:59,860 Við skulum gera þetta í staðinn. 690 00:28:59,860 --> 00:29:03,700 Við skulum líta á eitt sem er nánast Sama hugmynd, en það er a lítill sanngjarnari. 691 00:29:03,700 --> 00:29:04,200 Hægri? 692 00:29:04,200 --> 00:29:07,560 Ef þú ert einn af þessum aðdáandi drengja eða stelpur sem raunverulega finnst Apple vörur 693 00:29:07,560 --> 00:29:10,130 og þú vaknaðir í 03:00 að stilla upp á einhverjum verslun 694 00:29:10,130 --> 00:29:14,150 að fá mjög nýjustu iPhone, þú gæti hafa bið svona. 695 00:29:14,150 --> 00:29:15,800 >> Nú biðröð er mjög vísvitandi heitir. 696 00:29:15,800 --> 00:29:18,190 Það er lína vegna þess að það er sumir sanngirni við það. 697 00:29:18,190 --> 00:29:18,690 Hægri? 698 00:29:18,690 --> 00:29:21,690 Það myndi konar sogast ef þú hefur fékk það fyrst á Apple Store 699 00:29:21,690 --> 00:29:25,700 en þú ert í raun að bottommost bakki vegna Apple starfsmenn þá 700 00:29:25,700 --> 00:29:28,189 skjóta síðasta manneskja sem reyndar fékk í línu. 701 00:29:28,189 --> 00:29:31,230 Svo stöflum og biðröðum, jafnvel þó virkni þeir eru eiginlega same-- 702 00:29:31,230 --> 00:29:33,105 það er bara þetta safn auðlinda sem er 703 00:29:33,105 --> 00:29:36,210 að fara að vaxa og shrink-- there ' þessi sanngirni þáttur að það, 704 00:29:36,210 --> 00:29:39,634 að minnsta kosti í hinum raunverulega heimi, þar sem aðgerðir sem þú hreyfir 705 00:29:39,634 --> 00:29:40,800 eru í grundvallaratriðum ólík. 706 00:29:40,800 --> 00:29:43,360 A stack-- biðröð rather-- er sagður hafa 707 00:29:43,360 --> 00:29:45,320 tvær aðgerðir: n biðröð og d biðröð. 708 00:29:45,320 --> 00:29:46,341 709 00:29:46,341 --> 00:29:48,090 Eða þú getur hringt í þá allir tala um hlutina. 710 00:29:48,090 --> 00:29:50,770 En þú vilt bara til að handtaka sú hugmynd að einn er að bæta 711 00:29:50,770 --> 00:29:53,230 og einn er á endanum að draga. 712 00:29:53,230 --> 00:29:58,840 >> Nú undir hetta, bæði stafla og biðröð hægt væri að útfæra hvernig? 713 00:29:58,840 --> 00:30:01,390 Við munum ekki fara inn í kóða það vegna þess að hærra stigi 714 00:30:01,390 --> 00:30:03,387 Hugmyndin er tegund af meira augljóst. 715 00:30:03,387 --> 00:30:04,470 Ég meina, hvað menn gera? 716 00:30:04,470 --> 00:30:07,030 Ef ég er fyrsta manneskjan á Apple Geyma og þetta er framan dyrnar, 717 00:30:07,030 --> 00:30:08,130 þú veist, ég er að fara að standa hér. 718 00:30:08,130 --> 00:30:09,750 Og næsta manneskja er að fara að standa hér. 719 00:30:09,750 --> 00:30:11,500 Og næsta manneskja er að fara að standa hér. 720 00:30:11,500 --> 00:30:13,792 Svo hvaða gögn uppbygging lánar sig til biðröð? 721 00:30:13,792 --> 00:30:14,542 >> Áhorfendur: A biðröð. 722 00:30:14,542 --> 00:30:15,667 DAVID MALAN: Jæja, biðröð. 723 00:30:15,667 --> 00:30:16,390 Jú. 724 00:30:16,390 --> 00:30:16,920 Hvað annað? 725 00:30:16,920 --> 00:30:17,600 >> Áhorfendur: A tengda listanum. 726 00:30:17,600 --> 00:30:18,990 >> DAVID MALAN: A tengd lista sem þú gætir framkvæma. 727 00:30:18,990 --> 00:30:22,500 Og tengist listi er ágætur því þá getur það að vaxa geðþótta lengi öfugt 728 00:30:22,500 --> 00:30:24,880 að hafa nokkur ákveðinn fjölda af fólki í versluninni. 729 00:30:24,880 --> 00:30:27,030 En kannski a föst tala stöðum er lögmætur. 730 00:30:27,030 --> 00:30:30,350 Vegna þess að ef þeir hafa aðeins eins og 20 iPhone á fyrsta degi, kannski 731 00:30:30,350 --> 00:30:33,930 þeir þurfa aðeins á fjölbreytta stærð 20 til að tákna að biðröð, sem 732 00:30:33,930 --> 00:30:37,070 er aðeins að segja nú þegar við byrjum að tala um þessar hærri stigi vandamál, 733 00:30:37,070 --> 00:30:38,890 þú getur innleiða hana í allir tala af lifnaðarhættir. 734 00:30:38,890 --> 00:30:42,030 Og það er líklega bara að fara að vera a viðskipti burt í tíma og rúmi 735 00:30:42,030 --> 00:30:43,950 eða bara í eigin kóða flókið þinn. 736 00:30:43,950 --> 00:30:45,380 >> Hvað um reykháf? 737 00:30:45,380 --> 00:30:48,190 Jæja, stafla, höfum við séð of gæti bara verið þessi stæði. 738 00:30:48,190 --> 00:30:50,007 Og þú gætir framkvæma þetta fylki. 739 00:30:50,007 --> 00:30:53,090 En á einhverjum tímapunkti ef þú notar array, hvað er að fara að gerast á bökkunum 740 00:30:53,090 --> 00:30:54,173 þú ert að reyna að setja niður? 741 00:30:54,173 --> 00:30:55,170 742 00:30:55,170 --> 00:30:55,670 Allt í lagi. 743 00:30:55,670 --> 00:30:57,490 Þú ert bara að fara að vera fær um að fara svo hátt. 744 00:30:57,490 --> 00:31:00,156 Og ég held að í Mather þeir eru reyndar Innfelld í þeirri opnun. 745 00:31:00,156 --> 00:31:01,950 Svo reyndar er það nánast eins Mather notar 746 00:31:01,950 --> 00:31:03,783 fylki á fasta stærð, vegna þess að þú getur aðeins 747 00:31:03,783 --> 00:31:08,302 passa svo mörg stæði í þeirri opnun í vegg niður fyrir hné fólks. 748 00:31:08,302 --> 00:31:10,010 Og svo að gæti verið sagður vera array, 749 00:31:10,010 --> 00:31:14,300 en við gátum vissulega innleiða það almennt með tengda listanum. 750 00:31:14,300 --> 00:31:16,390 >> Jæja, hvað um annars gögn uppbygging? 751 00:31:16,390 --> 00:31:18,760 Leyfðu mér að draga upp eitt annað sjón hér. 752 00:31:18,760 --> 00:31:24,710 Eitthvað eins og hvernig óður í this einn hér? 753 00:31:24,710 --> 00:31:28,920 Hvers vegna gæti það verið gagnlegt að hafa ekki eitthvað eins ímynda sem trie, sem 754 00:31:28,920 --> 00:31:32,370 við sáum var þessi mjög breiður hnúður, sem hver um sig er í fylki? 755 00:31:32,370 --> 00:31:35,740 En hvað ef við gerum eitthvað meira einfaldlega, eins og gamlan skóla ættartré, 756 00:31:35,740 --> 00:31:38,110 hver af sem hnútar hér er bara að geyma númer. 757 00:31:38,110 --> 00:31:42,180 Í stað þess að nafn eða afkomandi er bara að geyma fjölda svona. 758 00:31:42,180 --> 00:31:45,250 >> Jæja, hrognamál við notum í gögn uppbygging er bæði reynir 759 00:31:45,250 --> 00:31:49,510 og tré, þar sem trie, aftur, er bara einn sem hnútar eru fylki, 760 00:31:49,510 --> 00:31:51,680 er enn það sem þú gætir nota frá grunnskóla 761 00:31:51,680 --> 00:31:53,860 þegar þú gerðir fjölskyldu tree-- lauf og rót 762 00:31:53,860 --> 00:31:57,250 af trénu og barna foreldri og systkini þeirra. 763 00:31:57,250 --> 00:32:03,670 Og við gætum innleiða tré, til dæmis, eins og einfaldlega þar sem þetta. 764 00:32:03,670 --> 00:32:07,420 A tré, ef það sem hnút, einn af þessum hringjum sem hefur a tala, 765 00:32:07,420 --> 00:32:09,947 það er ekki að fara að hafa einn músina, en tveir. 766 00:32:09,947 --> 00:32:11,780 Og um leið og þú bætir annað músina, þú 767 00:32:11,780 --> 00:32:13,905 geta reyndar nú gera Raða af tvívíð gögn 768 00:32:13,905 --> 00:32:14,780 mannvirki í minni. 769 00:32:14,780 --> 00:32:16,660 Líkt og tveggja vídda array, þú getur 770 00:32:16,660 --> 00:32:18,904 hafa konar tvívíð tengd listum en sjálfur 771 00:32:18,904 --> 00:32:20,820 að fylgja mynstri þar er engin hringrás. 772 00:32:20,820 --> 00:32:24,487 Það er sannarlega tré með einum afa leið upp hér og þá 773 00:32:24,487 --> 00:32:27,320 sumir foreldrar og börn og barnabörn og barnabarnabörn. 774 00:32:27,320 --> 00:32:28,370 og svo framvegis. 775 00:32:28,370 --> 00:32:32,390 >> En hvað er í raun sniðugt um þetta líka, bara til að stríða þér með smá kóða, 776 00:32:32,390 --> 00:32:35,370 Muna endurkvæmni frá stund aftur, þar 777 00:32:35,370 --> 00:32:38,220 þú skrifa fall sem kallar sig. 778 00:32:38,220 --> 00:32:41,140 Þetta er falleg tækifæri að innleiða eitthvað 779 00:32:41,140 --> 00:32:42,920 eins endurkvæmni, vegna íhuga þetta. 780 00:32:42,920 --> 00:32:43,860 >> Þetta er tré. 781 00:32:43,860 --> 00:32:48,040 Og ég hef verið lítið endaþarms með hvernig Ég setti heiltölur í götu. 782 00:32:48,040 --> 00:32:51,020 Svo mikið svo að það hefur sérstaka name-- tvíleitartré. 783 00:32:51,020 --> 00:32:53,460 Nú höfum við heyrt um tvöfaldur leita, en þú getur 784 00:32:53,460 --> 00:32:55,180 vinna aftur á bak frá nafni þetta er? 785 00:32:55,180 --> 00:32:59,280 Hvað er mynstur af hvernig ég sett á heiltölur í þessu tré? 786 00:32:59,280 --> 00:33:00,696 Það er ekki handahófskennt. 787 00:33:00,696 --> 00:33:01,570 There 'sumir mynstur. 788 00:33:01,570 --> 00:33:02,090 Já. 789 00:33:02,090 --> 00:33:03,370 >> Áhorfendur: Smærri sjálfur á vinstri. 790 00:33:03,370 --> 00:33:03,690 >> DAVID MALAN: Já. 791 00:33:03,690 --> 00:33:05,062 Smærri ríkin eru á vinstri. 792 00:33:05,062 --> 00:33:06,270 Stærri eru til hægri. 793 00:33:06,270 --> 00:33:12,940 Þannig að a satt staðhæfing er a foreldri er meiri en vinstri barn hennar, 794 00:33:12,940 --> 00:33:14,850 en minna en hægri barn hennar. 795 00:33:14,850 --> 00:33:17,750 Og það eitt og sér er jafnvel endurkvæma munnleg skýring 796 00:33:17,750 --> 00:33:20,500 vegna þess að þú getur sótt það Sama rökfræði hverjum hnút 797 00:33:20,500 --> 00:33:23,080 og það aðeins botn út, grunnur tilfelli ef þú 798 00:33:23,080 --> 00:33:25,740 mun, þegar þú högg einn af lauf, svo að segja, 799 00:33:25,740 --> 00:33:28,580 þar laufblað hefur engin börn frekar. 800 00:33:28,580 --> 00:33:30,614 >> Nú hvernig gætir þú fundið númerið 44? 801 00:33:30,614 --> 00:33:32,280 Þú myndir byrja á rót og segja, HM. 802 00:33:32,280 --> 00:33:35,690 55 er ekki 44 Svo ég vil að fara hægri eða ég vil að fara til vinstri? 803 00:33:35,690 --> 00:33:37,190 Jæja, augljóslega þú vilt að fara til vinstri. 804 00:33:37,190 --> 00:33:40,060 Og svo er það bara eins og í símanum bók dæmi í tvöfaldur leit 805 00:33:40,060 --> 00:33:41,099 almennt. 806 00:33:41,099 --> 00:33:43,390 En við erum að útfæra hana nú lítið meira virk 807 00:33:43,390 --> 00:33:45,339 en fylki gæti leyfa. 808 00:33:45,339 --> 00:33:48,130 Og í raun, ef þú vilt að líta á kóðann, við fyrstu sýn viss. 809 00:33:48,130 --> 00:33:49,671 Það lítur út eins og a heild búnt af línum. 810 00:33:49,671 --> 00:33:51,220 En það er fallegur einfalt. 811 00:33:51,220 --> 00:33:54,490 Ef þú vilt að framkvæma aðgerð kölluð Leita tilgangur í lífinu 812 00:33:54,490 --> 00:33:57,290 er að leita að verðmæti eins og n, heil tala, 813 00:33:57,290 --> 00:34:01,756 og þú ert leidd í einum pointer-- bendi á hnút rótum, 814 00:34:01,756 --> 00:34:04,380 Frekar, trés sem þú getur fengið aðgang að allt annað, 815 00:34:04,380 --> 00:34:08,850 eftir hversu einfaldur þú getur innleiða rökfræði. 816 00:34:08,850 --> 00:34:10,880 Ef tré er null, augljóslega er það ekki þar. 817 00:34:10,880 --> 00:34:11,880 Skulum aftur bara rangar. 818 00:34:11,880 --> 00:34:12,000 Hægri? 819 00:34:12,000 --> 00:34:14,040 Ef þú lætur það ekkert, það er ekkert þar. 820 00:34:14,040 --> 00:34:17,900 >> Annars, ef n er minna en tré arrow n- nú arrow n, 821 00:34:17,900 --> 00:34:20,670 muna við kynntum super stuttlega um daginn, 822 00:34:20,670 --> 00:34:25,100 og það bara þýðir de-tilvísun á músina og líta á sviði sem kallast n. 823 00:34:25,100 --> 00:34:27,690 Svo það þýðir að fara þangað og líta á sviði sem kallast n. 824 00:34:27,690 --> 00:34:33,810 Svo ef n er gildið sem þú ert að gefa, er minna en verðmæti í trjánum heiltala, 825 00:34:33,810 --> 00:34:35,449 Hvar viltu að fara? 826 00:34:35,449 --> 00:34:36,389 Til vinstri. 827 00:34:36,389 --> 00:34:37,780 >> Svo taka endurkvæmni. 828 00:34:37,780 --> 00:34:39,860 Ég ætla returning-- ekki satt. 829 00:34:39,860 --> 00:34:40,989 Ekki rangar. 830 00:34:40,989 --> 00:34:45,670 Ég ætla að skila hvað svarið er frá símtali við sjálfan mig, liggur 831 00:34:45,670 --> 00:34:50,100 N aftur, sem er óþarfi, En hvað er nú örlítið öðruvísi? 832 00:34:50,100 --> 00:34:51,989 Hvernig er ég að gera vandamálið minna? 833 00:34:51,989 --> 00:34:54,920 Ég er brottför í sem annað rök, ekki rót af trénu, 834 00:34:54,920 --> 00:34:59,616 en vinstri barn í þessu tilfelli. 835 00:34:59,616 --> 00:35:00,990 Þannig að ég ætla að brottför í vinstri barn. 836 00:35:00,990 --> 00:35:04,720 >> Á meðan, ef n er stærra en hnúturinn Ég er nú að horfa á, 837 00:35:04,720 --> 00:35:06,690 Ég leita á hægri hlið. 838 00:35:06,690 --> 00:35:10,880 Annars, ef tré er ekki null, og ef þátturinn er ekki til vinstri 839 00:35:10,880 --> 00:35:13,240 og það er ekki til hægri, hvað er frábærlega raunin? 840 00:35:13,240 --> 00:35:14,630 841 00:35:14,630 --> 00:35:18,440 Við höfum reyndar fundið hnút í spurning, og svo við aftur satt. 842 00:35:18,440 --> 00:35:21,490 >> Þannig að við höfum bara klóra yfirborðið nú sumir af þessum gögn uppbygging. 843 00:35:21,490 --> 00:35:24,370 Í Heimadæmi fimm þú munt kanna þetta enn frekar, 844 00:35:24,370 --> 00:35:27,250 og þú munt gefa hönnun val um hvernig á að fara um þetta. 845 00:35:27,250 --> 00:35:30,250 Það sem ég vil að gera á er bara a 30 second Teaser 846 00:35:30,250 --> 00:35:32,080 hvað bíður í næstu viku og víðar. 847 00:35:32,080 --> 00:35:35,390 >> Eins og við begin-- betur fer þú gætir think-- umskipti okkar rólega 848 00:35:35,390 --> 00:35:38,680 úr heimi C og lægra stigi framkvæmd upplýsingar, 849 00:35:38,680 --> 00:35:42,090 að heimi þar sem við getum tekið fyrir veitt að einhver annar hefur loksins 850 00:35:42,090 --> 00:35:44,010 framkvæmda þessara gagna mannvirki fyrir okkur, 851 00:35:44,010 --> 00:35:47,570 og við munum byrja að skilja raunverulega heimi þýðir að innleiða 852 00:35:47,570 --> 00:35:50,560 vefur-undirstaða forrit og vefsíður almennt 853 00:35:50,560 --> 00:35:52,910 og einnig mjög öryggi afleiðingar sem við höfum aðeins 854 00:35:52,910 --> 00:35:54,850 farnir að klóra yfirborð. 855 00:35:54,850 --> 00:35:57,320 Hér er það sem bíður okkar á næstu dögum koma. 856 00:35:57,320 --> 00:36:00,480 >> [VIDEO Spilun] 857 00:36:00,480 --> 00:36:03,432 858 00:36:03,432 --> 00:36:12,780 >> -Hann Kom með skilaboðum með siðareglur alla sína eigin. 859 00:36:12,780 --> 00:36:26,110 860 00:36:26,110 --> 00:36:30,894 Hann kom til a veröld af grimmur eldveggir, uncaring leið, 861 00:36:30,894 --> 00:36:33,368 og hættum miklu verra en dauðinn. 862 00:36:33,368 --> 00:36:35,280 863 00:36:35,280 --> 00:36:36,236 Hann er fljótur. 864 00:36:36,236 --> 00:36:37,980 Hann er sterkur. 865 00:36:37,980 --> 00:36:42,830 Hann er TCP / IP, og hann fékk netfangið þitt. 866 00:36:42,830 --> 00:36:45,290 867 00:36:45,290 --> 00:36:48,074 "Warriors á Netinu." 868 00:36:48,074 --> 00:36:49,660 [END vídeó spilun] 869 00:36:49,660 --> 00:36:50,910 DAVID MALAN: Tilkoma næstu viku. 870 00:36:50,910 --> 00:36:51,880 Við munum sjá þig þá. 871 00:36:51,880 --> 00:36:54,615 872 00:36:54,615 --> 00:36:56,060 [VIDEO Spilun] 873 00:36:56,060 --> 00:36:59,240 -Og Nú, "Deep Thoughts" eftir Daven Farnham. 874 00:36:59,240 --> 00:37:02,030 875 00:37:02,030 --> 00:37:05,820 -David Byrjar alltaf fyrirlestrar með, "Allt í lagi." 876 00:37:05,820 --> 00:37:08,750 Hvers vegna ekki, "Hér er lausnin til þessa viku Heimadæmi " 877 00:37:08,750 --> 00:37:12,180 eða "Við erum að gefa ykkur að A?" 878 00:37:12,180 --> 00:37:13,380 [Book] 879 00:37:13,380 --> 00:37:15,530 [END vídeó spilun]