1 00:00:00,000 --> 00:00:11,460 2 00:00:11,460 --> 00:00:12,250 >> DAVID Malan: Allt í lagi. 3 00:00:12,250 --> 00:00:13,860 Velkomin aftur til CS50. 4 00:00:13,860 --> 00:00:16,190 Þetta er upphaf 8. viku. 5 00:00:16,190 --> 00:00:21,320 Og muna að Heimadæmi 5 lauk með smá áskorun. 6 00:00:21,320 --> 00:00:25,210 Svo miðað við að þú batna öllum þínum kennslu Fellows og ljósmyndir CA 7 00:00:25,210 --> 00:00:30,480 í card.raw skrá, þú ert rétt að nú finna alla þá fólks, og 8 00:00:30,480 --> 00:00:34,510 einn heppinn sigurvegari vilja ganga heim með einn af þessum hlutum, sem stökk hreyfing 9 00:00:34,510 --> 00:00:37,450 tæki sem þú getur notað til endanlegrar verkefni, til dæmis. 10 00:00:37,450 --> 00:00:39,860 >> Þetta, á hverju ári, leiðir til smá creepiness. 11 00:00:39,860 --> 00:00:43,480 Og svo það sem ég hélt að ég myndi gera er að deila með þér nokkrum af þeim athugasemdum sem hafa 12 00:00:43,480 --> 00:00:47,370 farið fram og til baka yfir starfsfólk lista á síðkastið. 13 00:00:47,370 --> 00:00:51,110 Til dæmis, vitna bara í gærkvöldi Unquote, frá einu af the staff 14 00:00:51,110 --> 00:00:55,000 meðlimir, "Ég hafði bara nemandi högg á hurðina mína til að taka mynd með mér. 15 00:00:55,000 --> 00:00:59,020 Stalkers, ég segi þér. "Byrjaði nokkuð lýsandi og þá við fluttum 16 00:00:59,020 --> 00:01:02,830 á, klukkutíma eða svo síðar, "ég átti nemandi að bíða eftir mér eftir hluta 17 00:01:02,830 --> 00:01:06,080 og hann hafði allt af nöfnum okkar og myndir á sumum blöð. "Allt í lagi. 18 00:01:06,080 --> 00:01:09,230 Sem skipuleggja, en ekki allt sem enn hrollvekjandi. 19 00:01:09,230 --> 00:01:12,520 >> Þá, "ég var út úr bænum um helgina, og þegar ég kom aftur, það var einn í 20 00:01:12,520 --> 00:01:12,630 minn 21 00:01:12,630 --> 00:01:16,740 svefnherbergi. "[hlátur] 22 00:01:16,740 --> 00:01:20,410 DAVID Malan: Næsta tilvitnun úr starfsfólki félagi, "nemandi kom til mín á 23 00:01:20,410 --> 00:01:25,330 Somerville á 4:00 í morgun. "Næsta starfsfólk, "ég fékk að hótelinu mínu í San 24 00:01:25,330 --> 00:01:30,016 Francisco og nemandi var að bíða eftir mig á móttöku með þremur DSLRs. " 25 00:01:30,016 --> 00:01:31,510 Tegund af myndavél. 26 00:01:31,510 --> 00:01:34,980 "Ég er ekki einu sinni á starfsfólki þessari önn, en nemandi braut inn í hús mitt þetta 27 00:01:34,980 --> 00:01:40,480 morgun og skráð í heild hlutur með Google Glass. "Og svo loks, 28 00:01:40,480 --> 00:01:43,650 "Að minnsta kosti 12 manns voru ákaft bíða fyrir mig þegar ég fékk út af mínum 29 00:01:43,650 --> 00:01:44,800 Eðalvagn, og þá er ég 30 00:01:44,800 --> 00:01:46,970 vaknaði. "Allt í lagi. 31 00:01:46,970 --> 00:01:57,690 Svo meðal ljósmyndum, eins og þú getur muna, eru þessi náungi hér, sem þú 32 00:01:57,690 --> 00:02:01,850 gæti vita sem Milo Banana, sem býr við Lauren Carvalho, yfirmaður okkar 33 00:02:01,850 --> 00:02:02,905 kennslu náungi. 34 00:02:02,905 --> 00:02:05,170 Milo, Milo, komdu hingað drengur. 35 00:02:05,170 --> 00:02:06,320 Milo. 36 00:02:06,320 --> 00:02:08,650 Milo. 37 00:02:08,650 --> 00:02:12,230 Mind þér, hann þreytandi Google Glass, svo við munum sýna þér þetta allt eftir. 38 00:02:12,230 --> 00:02:16,190 Svo er þetta Milo ef þú vildi eins og til taka mynd með honum síðan. 39 00:02:16,190 --> 00:02:18,240 Ef þú vilt líta út á áhorfendur þar. 40 00:02:18,240 --> 00:02:19,430 OK. 41 00:02:19,430 --> 00:02:20,200 Það er gott myndefni. 42 00:02:20,200 --> 00:02:22,556 Jæja, Milo Banana. 43 00:02:22,556 --> 00:02:23,941 Ó, gera það ekki. 44 00:02:23,941 --> 00:02:29,020 >> [Hlátur] 45 00:02:29,020 --> 00:02:29,470 >> OK. 46 00:02:29,470 --> 00:02:34,550 Svo orði þá á hvað er framundan, því eins og við byrjum að umskipti, 47 00:02:34,550 --> 00:02:38,410 í þessari viku sérstaklega, úr C í a stjórn lína umhverfi til PHP og 48 00:02:38,410 --> 00:02:42,720 JavaScript og SQL og HTML og CSS í A vefur-undirstaða umhverfi, munum við vera 49 00:02:42,720 --> 00:02:44,490 útbúnað þér allar meiri þekkingu fyrir 50 00:02:44,490 --> 00:02:46,010 hugsanlega lokaverkefni. 51 00:02:46,010 --> 00:02:49,240 Undir því skyni, að sjálfsögðu hefur hefð að halda námskeið sem 52 00:02:49,240 --> 00:02:50,950 eru á snertifleti efni að sjálfsögðu. 53 00:02:50,950 --> 00:02:54,330 Mjög mikið sem tengjast forritun og app þróun og svo framvegis, en 54 00:02:54,330 --> 00:02:57,010 ekki endilega kanna með eigin Námskeiðið er kennsluáætlun. 55 00:02:57,010 --> 00:03:00,250 >> Svo ef þú gætir haft áhuga á einu eða meira af námskeiðum á þessu ári, 56 00:03:00,250 --> 00:03:02,530 Skráning er á cs50.net/seminar. 57 00:03:02,530 --> 00:03:06,170 Það eru eldri námskeið á cs50.net/seminars. 58 00:03:06,170 --> 00:03:10,620 Og á verkefnaskrá Hingað á þessu ári eru ótrúlega Apps vefur með Ruby á 59 00:03:10,620 --> 00:03:13,580 Teinar, sem er val tungumál til PHP. 60 00:03:13,580 --> 00:03:14,900 Tölvumálvísindum. 61 00:03:14,900 --> 00:03:18,710 Inngangur að IOS, sem er pallur sem er notað fyrir iPhone og 62 00:03:18,710 --> 00:03:19,850 iPad þróun. 63 00:03:19,850 --> 00:03:22,890 JavaScript til að Web Apps, munum við ná að, en í þessu námskeiði, munt þú fara 64 00:03:22,890 --> 00:03:24,070 inn í fleiri smáatriði. 65 00:03:24,070 --> 00:03:27,390 >> Stökk Motion, svo við munum í raun hafa sumir af vinum okkar frá Motion Leap, 66 00:03:27,390 --> 00:03:29,160 fyrirtækið sjálft, tengja okkur. 67 00:03:29,160 --> 00:03:31,800 Á morgun, í raun, að veita a snertið ekki-á námskeið, ef 68 00:03:31,800 --> 00:03:33,320 áhugaverð fyrir þig. 69 00:03:33,320 --> 00:03:38,770 Meteor.js, val aðferð fyrir nota JavaScript ekki í vafra 70 00:03:38,770 --> 00:03:39,970 en á netþjóni. 71 00:03:39,970 --> 00:03:42,110 Node.js, sem er mjög mikið í því bláæð og vel. 72 00:03:42,110 --> 00:03:43,650 Sléttur Android Design. 73 00:03:43,650 --> 00:03:46,990 Android vera mjög vinsæll valkostur til IOS og Windows Sími 74 00:03:46,990 --> 00:03:48,790 og annar hreyfanlegur pallur. 75 00:03:48,790 --> 00:03:51,180 Og Web Security Active Defense. 76 00:03:51,180 --> 00:03:54,590 >> Svo í raun, ef þú vilt að taka þátt í þessu, láttu mig 77 00:03:54,590 --> 00:03:55,840 gera mið af þessu. 78 00:03:55,840 --> 00:03:57,790 Við erum mjög ánægð að segja að vinir okkar á Leap 79 00:03:57,790 --> 00:03:59,140 Hreyfing, sem er gangsetning - 80 00:03:59,140 --> 00:04:01,300 þetta tæki virkilega bara kom út nokkrum mánuðum síðan - 81 00:04:01,300 --> 00:04:05,960 hefur vingjarnlega gaf 30 slík tæki á bekknum fyrir eins margra nemenda, ef 82 00:04:05,960 --> 00:04:08,670 þú vilt að láni vélbúnað að lok hverrar annar og nota það til 83 00:04:08,670 --> 00:04:10,390 í raun lokaverkefni. 84 00:04:10,390 --> 00:04:11,890 Þeir styðja takmarkaðan fjölda tungumála. 85 00:04:11,890 --> 00:04:16,040 Ekkert af þeim C, enginn þeirra PHP, svo gera sér grein fyrir einn eða fleiri af þessum málstofum 86 00:04:16,040 --> 00:04:16,899 gæti reynst áhugaverð. 87 00:04:16,899 --> 00:04:19,730 Og öllum þeim verður tekið í ef að þú ert ekki fær 88 00:04:19,730 --> 00:04:21,380 að mæta í eigin persónu. 89 00:04:21,380 --> 00:04:25,000 Dagskráin verið tilkynnt um email og við styrkja herbergi. 90 00:04:25,000 --> 00:04:28,460 >> Og loks, ef þú ferð til projects.cs.50.net, þetta er vefsíða 91 00:04:28,460 --> 00:04:31,450 við höldum á hverju ári sem við bjóðum gott fólk frá samfélaginu, kennara 92 00:04:31,450 --> 00:04:36,420 deildir, starfsfólk, og bæði í utan CS50 til 93 00:04:36,420 --> 00:04:37,730 leggja verkefni hugmyndir. 94 00:04:37,730 --> 00:04:39,050 Things af áhuga að námsmenn. 95 00:04:39,050 --> 00:04:40,600 Atriði af áhugi til deilda. 96 00:04:40,600 --> 00:04:43,990 Svo snú þar ef þú ert í erfiðleikum með óvissu um hvað þú 97 00:04:43,990 --> 00:04:46,700 sjálfur langar að glíma við. 98 00:04:46,700 --> 00:04:51,760 >> Svo síðast þegar við kynntum að öllum líkindum flóknari gögn uppbygging en við myndum 99 00:04:51,760 --> 00:04:53,300 séð í vikum áður. 100 00:04:53,300 --> 00:04:56,550 Við höfðum verið að nota fylki nokkuð hamingjusöm eins gagnlegt ef 101 00:04:56,550 --> 00:04:58,160 einföldu gögn uppbygging. 102 00:04:58,160 --> 00:05:00,570 Þá kynntum þetta, sem auðvitað eru tengd listum. 103 00:05:00,570 --> 00:05:05,470 Og hvað var einn af motivations fyrir kynna þessi gögn uppbygging? 104 00:05:05,470 --> 00:05:06,930 Já? 105 00:05:06,930 --> 00:05:07,250 Hvað er það? 106 00:05:07,250 --> 00:05:08,080 >> Áhorfendur: Dynamic stærð. 107 00:05:08,080 --> 00:05:09,040 >> DAVID Malan: Dynamic stærð. 108 00:05:09,040 --> 00:05:11,890 Svo þar í fylki, þú þarft að vita stærð sína fyrirfram þegar 109 00:05:11,890 --> 00:05:12,740 þú úthluta því. 110 00:05:12,740 --> 00:05:14,380 Í tengda listanum, þarftu ekki að vita það. 111 00:05:14,380 --> 00:05:17,610 Þú getur bara malloc eða fleiri almennt, úthluta til viðbótar 112 00:05:17,610 --> 00:05:20,720 hnút, svo að segja, hvenær sem þú langar að setja inn fleiri upplýsingar. 113 00:05:20,720 --> 00:05:22,670 Og hnút hefur ekki fyrirfram merkingu. 114 00:05:22,670 --> 00:05:25,580 Það er bara almenn orð sem lýsa einhvers konar ílát sem við erum 115 00:05:25,580 --> 00:05:29,610 nota í uppbyggingu okkar gögn til að geyma einhver atriði af áhugi, sem í þessu 116 00:05:29,610 --> 00:05:31,750 Málið verður að vera heiltölur. 117 00:05:31,750 --> 00:05:33,160 >> En það er alltaf tradeoff. 118 00:05:33,160 --> 00:05:38,070 Svo við fáum öflugt stærðir af gögnum uppbyggingu, en hvaða verð borga við? 119 00:05:38,070 --> 00:05:40,040 Hvað er hæðir af tengdum listum? 120 00:05:40,040 --> 00:05:41,006 Já? 121 00:05:41,006 --> 00:05:41,980 >> Áhorfendur: þarf meira minni. 122 00:05:41,980 --> 00:05:44,240 >> DAVID Malan: Það þurfa fleiri minni, hvernig nákvæmlega? 123 00:05:44,240 --> 00:05:46,440 >> Áhorfendur: [inaudible]. 124 00:05:46,440 --> 00:05:47,050 >> DAVID Malan: Einmitt. 125 00:05:47,050 --> 00:05:50,460 Svo nú höfum við ábendingum taka upp fleiri minni sem við áður 126 00:05:50,460 --> 00:05:53,040 þarf ekki, vegna þess að kostur um fjölda, að sjálfsögðu, er að 127 00:05:53,040 --> 00:05:54,860 allt er samliggjandi, aftur til aftur til baka, sem 128 00:05:54,860 --> 00:05:56,380 gefur þér af handahófi aðgang. 129 00:05:56,380 --> 00:06:00,710 Því bara með því að nota veldi krappi ritháttur eða meira tæknilega músina 130 00:06:00,710 --> 00:06:03,580 tölur, mjög einfalt viðbót, getur þú fengið aðgang að hvaða 131 00:06:03,580 --> 00:06:05,700 þættir í föstu tíma. 132 00:06:05,700 --> 00:06:08,975 Og í raun, það er eins konar vísbending um annað verð sem við erum að borga með 133 00:06:08,975 --> 00:06:09,760 tengda listanum. 134 00:06:09,760 --> 00:06:13,890 >> Hvað gerist í gangi tíma eitthvað eins og leit, ef ég vil 135 00:06:13,890 --> 00:06:17,270 finna nokkur gildi og inni um tengda lista? 136 00:06:17,270 --> 00:06:20,290 Hvað þýðir að keyra minn tími orðið? 137 00:06:20,290 --> 00:06:21,560 Big O n. 138 00:06:21,560 --> 00:06:24,060 Ef það er raðað í? 139 00:06:24,060 --> 00:06:25,440 Hvað ef gögn uppbygging er raðað? 140 00:06:25,440 --> 00:06:28,640 Get ég gert betur en stór O n til að leita? 141 00:06:28,640 --> 00:06:31,700 Nei, vegna þess að í versta tilfelli gæti mjög vel að vera flokkaður, en fjöldi 142 00:06:31,700 --> 00:06:32,950 þú ert að leita að gæti verið stór. 143 00:06:32,950 --> 00:06:35,370 Það gæti verið númer 100, sem gæti gerst að vera allt 144 00:06:35,370 --> 00:06:36,410 leið á endanum. 145 00:06:36,410 --> 00:06:39,950 Og vegna þess að þú getur aðeins opna tengd lista í þessari framkvæmd með því 146 00:06:39,950 --> 00:06:42,690 leið fyrsta hnút hennar, þú ert enn svona út af heppni. 147 00:06:42,690 --> 00:06:47,450 Þú þarft að fara yfir allt hlutur frá fyrstu til varað í því skyni að finna 148 00:06:47,450 --> 00:06:49,150 að stór gildi eins 100 manns. 149 00:06:49,150 --> 00:06:51,350 Eða til að ákvarða hvort það er ekki einu sinni það. 150 00:06:51,350 --> 00:06:55,960 >> Svo við getum ekki gert það reiknirit í gögnum uppbyggingu sem lítur svona út? 151 00:06:55,960 --> 00:06:59,460 Við getum ekki gert tvöfaldur leit, því tvöfaldur leita þarf að við höfðum 152 00:06:59,460 --> 00:07:00,740 handahófi aðgangur. 153 00:07:00,740 --> 00:07:04,500 Við gætum bara stökk frá stað til stað án þess að fylgja 154 00:07:04,500 --> 00:07:07,080 þessar brauð mola í formi af öllum þessum ábendingum. 155 00:07:07,080 --> 00:07:08,300 >> Nú, hvernig var við að framkvæma þetta? 156 00:07:08,300 --> 00:07:12,830 Jæja, ef við förum á skjáinn hér, ef við getum fljótlega reimplement þessi gögn 157 00:07:12,830 --> 00:07:13,440 uppbygging - 158 00:07:13,440 --> 00:07:15,670 rithönd mín er ekki allt sem mikill hér, en við munum reyna. 159 00:07:15,670 --> 00:07:22,030 Svo typedef strúktúr, og hvað gerði ég vilt hringja þetta upp hér? 160 00:07:22,030 --> 00:07:22,960 Hnút. 161 00:07:22,960 --> 00:07:24,580 Svo ég næ okkur byrjaði. 162 00:07:24,580 --> 00:07:27,860 Og nú, hvað þarf að vera inni gögn uppbygging fyrir að ein 163 00:07:27,860 --> 00:07:28,430 tengd lista? 164 00:07:28,430 --> 00:07:29,950 Hversu mörgum sviðum? 165 00:07:29,950 --> 00:07:30,450 >> Svo tveir. 166 00:07:30,450 --> 00:07:31,570 Einn er nokkuð auðvelt. 167 00:07:31,570 --> 00:07:33,050 Svo int n. 168 00:07:33,050 --> 00:07:35,930 Og við gætum hringt n hvað sem við viljum, en það ætti að vera int ef við erum 169 00:07:35,930 --> 00:07:37,660 framkvæmd tengda lista fyrir ints. 170 00:07:37,660 --> 00:07:41,920 Og nú er það annað sviði að vera? 171 00:07:41,920 --> 00:07:43,460 Strúktúr hnút *. 172 00:07:43,460 --> 00:07:50,570 Svo ef ég strúktúr hnút *, og svo ég getur hringt í þetta líka hvað ég vil, 173 00:07:50,570 --> 00:07:53,510 en bara til að vera skýr Ég hringi það næsta, eins og við höfum verið að gera. 174 00:07:53,510 --> 00:07:55,270 Og þá ég loka hrokkið axlabönd mínum. 175 00:07:55,270 --> 00:08:00,700 >> Og nú, eins og síðasta sinn, Ég setti hnút niður hér. 176 00:08:00,700 --> 00:08:03,830 En ef ég er að lýsa þessu er sem hnút, af hverju gerði ég nennir að vera svo 177 00:08:03,830 --> 00:08:07,320 fjölorður hér í að lýsa strúktúr tengipunktur * næst, öfugt 178 00:08:07,320 --> 00:08:09,210 til bara hnút * er? 179 00:08:09,210 --> 00:08:09,904 Já? 180 00:08:09,904 --> 00:08:12,810 >> Áhorfendur: [inaudible]. 181 00:08:12,810 --> 00:08:14,050 >> DAVID Malan: Einmitt. 182 00:08:14,050 --> 00:08:14,530 Einmitt. 183 00:08:14,530 --> 00:08:18,320 Vegna C tekur virkilega bókstaflega og aðeins sér skilgreiningu á hnút 184 00:08:18,320 --> 00:08:21,230 leið niður hér, getur þú ekki átt við það upp hér. 185 00:08:21,230 --> 00:08:24,760 Þannig að við höfum svona sjáum yfirlýsingu hér, sem er að vísu 186 00:08:24,760 --> 00:08:25,390 meira fjölorður. 187 00:08:25,390 --> 00:08:27,810 Strúktúr hnút, sem þýðir við getum nú nálgast hana 188 00:08:27,810 --> 00:08:29,760 innan við gögn uppbygging. 189 00:08:29,760 --> 00:08:33,370 >> Og eins og til hliðar, því þetta er verða aðeins meira huglægt nú, 190 00:08:33,370 --> 00:08:36,230 stjarnan geta tæknilega farið hér, það getur farið hér, getur það 191 00:08:36,230 --> 00:08:37,179 jafnvel fara í miðju. 192 00:08:37,179 --> 00:08:39,890 Við höfum samþykkt, í stíl fylgja fyrir Námskeiðið, sem venju að setja 193 00:08:39,890 --> 00:08:42,299 stjarnan við hliðina á þeim gögnum gerð, sem í þessu tilfelli, 194 00:08:42,299 --> 00:08:43,460 væri strúktúr hnút. 195 00:08:43,460 --> 00:08:46,620 En átta sig í fullt af kennslubókum og netinu tilvísanir, gætir þú örugglega 196 00:08:46,620 --> 00:08:48,450 sjá það á hinni hliðinni. 197 00:08:48,450 --> 00:08:52,200 En bara grein fyrir því að báðir vilja raunverulega vinna og þú ættir einfaldlega að vera 198 00:08:52,200 --> 00:08:52,970 stöðug. 199 00:08:52,970 --> 00:08:53,580 >> Allt í lagi. 200 00:08:53,580 --> 00:08:55,630 Svo sem var yfirlýsing okkar á hnút strúktúrinn. 201 00:08:55,630 --> 00:08:59,430 En þá erum við byrjaði að gera meira háþróuð hlutir. 202 00:08:59,430 --> 00:09:03,410 Til dæmis ákváðum við að kynna eitthvað eins og kjötkássa töflunni. 203 00:09:03,410 --> 00:09:08,160 Svo hér er kjötkássa borð af n stærð, verðtryggð frá 0 á efst til vinstri til n 204 00:09:08,160 --> 00:09:09,690 mínus 1 á neðst til vinstri. 205 00:09:09,690 --> 00:09:11,640 Þetta gæti verið kjötkássa borð fyrir neitt. 206 00:09:11,640 --> 00:09:15,340 En hvað konar hluti gerði við tölum um að nota kjötkássa borð fyrir? 207 00:09:15,340 --> 00:09:18,370 Geymsla hvað? 208 00:09:18,370 --> 00:09:18,800 >> Nöfn. 209 00:09:18,800 --> 00:09:20,870 Við gætum gert nöfn eins við gerðum síðast. 210 00:09:20,870 --> 00:09:22,200 Og í raun er hægt að geyma neitt. 211 00:09:22,200 --> 00:09:24,640 Og við munum sjá þetta aftur í PHP og JavaScript. 212 00:09:24,640 --> 00:09:28,550 A kjötkássa borð er ágætur konar Swiss Army hnífur sem leyfir þér að vista 213 00:09:28,550 --> 00:09:33,690 nánast hvað sem þú vilt inni það með því að tengja takkana með gildum. 214 00:09:33,690 --> 00:09:34,770 Lyklar með gildin. 215 00:09:34,770 --> 00:09:37,800 >> Nú í þessari einföldu tilfelli, okkar lyklar eru bara tölur. 216 00:09:37,800 --> 00:09:40,380 Við erum að innleiða kjötkássa borð sem fylki. 217 00:09:40,380 --> 00:09:43,500 Og svo takkarnir eru 0, 1, 2, og svo framvegis. 218 00:09:43,500 --> 00:09:47,200 Og svo við, eins og menn, ákvað síðasta viku sem þú veist hvað, ef við erum 219 00:09:47,200 --> 00:09:50,410 fara að geyma nöfn, við skulum bara geðþótta, en nokkuð sæmilega, 220 00:09:50,410 --> 00:09:54,680 ráð fyrir að Alice, A nafn, mun bara vera verðtryggð í 0. 221 00:09:54,680 --> 00:09:58,030 Og Bob, B nafn, verða verðtryggð í 1, og svo framvegis. 222 00:09:58,030 --> 00:10:02,490 Svo höfðum við kortlagning á milli aðfanga, sem eru strengir, og tætið 223 00:10:02,490 --> 00:10:04,560 stöðum, sem eru tölur. 224 00:10:04,560 --> 00:10:07,740 >> Svo þessi aðferð er almennt þekktur eins og kjötkássa virka, og þú getur sannarlega 225 00:10:07,740 --> 00:10:09,130 innleiða hana í kóða. 226 00:10:09,130 --> 00:10:12,080 Ef ég vildi framkvæma kjötkássa virka sem er einmitt það sem við 227 00:10:12,080 --> 00:10:17,070 bara lýst frá síðasta tíma, gæti ég lýsa aðgerð sem tekur, eins og 228 00:10:17,070 --> 00:10:18,330 inntak til dæmis - 229 00:10:18,330 --> 00:10:22,190 og við skulum gera þetta á þetta skjár hérna. 230 00:10:22,190 --> 00:10:26,180 Ef ég vildi innleiða kjötkássa virka, gæti ég sagt 231 00:10:26,180 --> 00:10:27,410 eitthvað eins og this. 232 00:10:27,410 --> 00:10:29,030 >> Það er að fara að skila int. 233 00:10:29,030 --> 00:10:33,600 Það er að fara að vera kölluð kjötkássa, og það er að fara að taka sem rök fyrir 234 00:10:33,600 --> 00:10:38,920 band, eða við getum verið meira viðeigandi nú, og segja char *, munum við kalla það s. 235 00:10:38,920 --> 00:10:43,840 Og þá hefur allt þetta aðgerð til að gera, lokum, er skila int. 236 00:10:43,840 --> 00:10:45,990 Nú, hvernig það virkar sem gæti ekki að vera svo skýr. 237 00:10:45,990 --> 00:10:49,510 Ég ætla að framkvæma þetta án þess að allir Form villuprófun núna. 238 00:10:49,510 --> 00:10:55,740 Ég ætla bara að fara að blindni segja, aftur hvað er á s þrepi 0, mínus, 239 00:10:55,740 --> 00:10:58,850 skulum segja, höfuðborg semíkommu. 240 00:10:58,850 --> 00:10:59,960 >> Algjörlega brotinn. 241 00:10:59,960 --> 00:11:02,620 Það er ekki fullkominn því einn, hvað ef s er núll? 242 00:11:02,620 --> 00:11:04,000 Slæmir hlutir eru að fara að gerast. 243 00:11:04,000 --> 00:11:07,940 Tveir, hvað ef fyrsti stafurinn í þessu nafn er ekki höfuðborg bréf? 244 00:11:07,940 --> 00:11:09,860 Það er ekki að fara að snúa vel heldur. 245 00:11:09,860 --> 00:11:11,970 Það gæti verið lágstafir bréf eða ekki bréf yfirleitt. 246 00:11:11,970 --> 00:11:15,520 Svo algerlega pláss fyrir framfarir hér, en þetta er grundvallar hugmynd. 247 00:11:15,520 --> 00:11:19,010 >> Það sem við sem lýst er í síðustu viku munnlega og bara ferli að kortleggja Lísa til 248 00:11:19,010 --> 00:11:23,360 0 og Bob til 1 er hægt að sýna vissulega meira formulaically sem C 249 00:11:23,360 --> 00:11:24,320 virka hér. 250 00:11:24,320 --> 00:11:28,630 Kallaði aftur kjötkássa, tekur streng sem inntak, og þá er á einhvern hátt eitthvað 251 00:11:28,630 --> 00:11:31,020 með því inntak að framleiða framleiðsla. 252 00:11:31,020 --> 00:11:34,130 Ekki ólíkt svartur kassi lýsingu okkar sem við höfum lengi gert. 253 00:11:34,130 --> 00:11:36,550 Ég veit ekki hvernig þetta gæti verið vinna undir hetta. 254 00:11:36,550 --> 00:11:40,120 >> Fyrir sett Dæmi 6., einn af þeim áskorunum er fyrir þig að ákveða hvað 255 00:11:40,120 --> 00:11:41,920 mun kjötkássa virka þín? 256 00:11:41,920 --> 00:11:45,760 Hvað er að fara að vera inni að svart kassi, og væntanlega verður það að vera 257 00:11:45,760 --> 00:11:50,380 lítið meira áhugavert en þetta, og örugglega hættara við villa 258 00:11:50,380 --> 00:11:53,180 stöðva en þetta tiltekna framkvæmd. 259 00:11:53,180 --> 00:11:54,580 >> En vandamál geta komið upp, ekki satt? 260 00:11:54,580 --> 00:11:57,760 Ef við höfum gögn uppbygging eins og þessa einn, hvað er eitt af þeim vandamálum 261 00:11:57,760 --> 00:12:01,600 þú getur keyrt inn í tímanum sem þú setur fleiri og fleiri nöfn inn í 262 00:12:01,600 --> 00:12:02,880 kjötkássa borð? 263 00:12:02,880 --> 00:12:04,630 Þú færð árekstra, ekki satt? 264 00:12:04,630 --> 00:12:07,560 Hvað ef þú ert með Alice og Aron, tvær manneskjur sem nöfn gerðist 265 00:12:07,560 --> 00:12:08,190 til að byrja með? 266 00:12:08,190 --> 00:12:11,660 Það bidur spurningin, þar sem þú setja annað svo nafn? 267 00:12:11,660 --> 00:12:15,050 >> Jæja, þú might naively bara setja það þar sem Bubbi tilheyrir, en þá er Bob 268 00:12:15,050 --> 00:12:17,300 konar ruglaður ef þú reynir að setja nafnið hans næsta og 269 00:12:17,300 --> 00:12:18,240 það er ekkert pláss fyrir hann. 270 00:12:18,240 --> 00:12:21,400 Svo þú gætir sett Bob þar Charlie er, og þú getur ímyndað þetta mjög fljótt 271 00:12:21,400 --> 00:12:23,020 devolving inn í a hluti af a sóðaskapur. 272 00:12:23,020 --> 00:12:25,600 Eitthvað línuleg á endanum, þar sem þú bara að leita á allri 273 00:12:25,600 --> 00:12:28,190 leita Alice eða Bob eða Aron eða Charlie. 274 00:12:28,190 --> 00:12:33,230 >> Þeirra í stað lagt, í staðinn af réttlátur línulega leit fyrir opin rými 275 00:12:33,230 --> 00:12:36,450 og plopping nöfn þarna, við Lagt áhugamaður nálgun. 276 00:12:36,450 --> 00:12:41,740 A kjötkássa borð til framkvæmda enn með array af vísitölum, en gögnin gerð 277 00:12:41,740 --> 00:12:44,500 þessir vísitölur voru nú ábendingum. 278 00:12:44,500 --> 00:12:47,360 Ábendingum til hvaða? 279 00:12:47,360 --> 00:12:48,730 Ábendingum til tengd listum. 280 00:12:48,730 --> 00:12:53,330 >> Vegna muna að tengjast listi er raun bara bendi á hnút, og 281 00:12:53,330 --> 00:12:57,110 hnúturinn hefur næsta reit, og að hnút hefur næsta reit, og svo framvegis. 282 00:12:57,110 --> 00:13:00,690 Svo þú getur nú hugsa um þetta fylki á vinstri-hönd hlið af kjötkássa töflu sem 283 00:13:00,690 --> 00:13:01,820 leiðir til tengda listanum. 284 00:13:01,820 --> 00:13:07,000 Kosturinn sem er ef þú færð árekstur milli Alice og Aron, 285 00:13:07,000 --> 00:13:09,300 hvað gerir þú með önnur slík manneskja? 286 00:13:09,300 --> 00:13:14,150 Þú hengja bara hann eða hana til endir, eða jafnvel í byrjun 287 00:13:14,150 --> 00:13:15,490 þess tengda listanum. 288 00:13:15,490 --> 00:13:17,340 >> Og reyndar, við skulum bara núðla gegnum að fyrir bara annað. 289 00:13:17,340 --> 00:13:18,640 Hvar myndi gera sem mest vit? 290 00:13:18,640 --> 00:13:22,060 Ef ég setja Lísa og hún endar á fyrsta location, þá reyni ég að 291 00:13:22,060 --> 00:13:25,310 setja nafn Arons, og það er augljóslega árekstur, ætti ég að setja 292 00:13:25,310 --> 00:13:27,400 honum í upphafi á tengda lista? 293 00:13:27,400 --> 00:13:30,944 Það er á þeim fyrsta stað, eða í lok? 294 00:13:30,944 --> 00:13:31,440 >> Áhorfendur: [inaudible]. 295 00:13:31,440 --> 00:13:31,990 >> DAVID Malan: OK. 296 00:13:31,990 --> 00:13:32,490 Ég heyrði byrjun. 297 00:13:32,490 --> 00:13:33,903 Hvers vegna í upphafi? 298 00:13:33,903 --> 00:13:34,750 >> Áhorfendur: [inaudible]. 299 00:13:34,750 --> 00:13:34,940 >> DAVID Malan: OK. 300 00:13:34,940 --> 00:13:36,520 Það er stafrófsröð, svo það er gott. 301 00:13:36,520 --> 00:13:37,330 Það er góð eign. 302 00:13:37,330 --> 00:13:39,335 Það mun spara mér tíma mögulega. 303 00:13:39,335 --> 00:13:43,290 Það mun ekki láta mig gera tvöfaldur leit, en ég gæti að minnsta kosti að vera fær um að brjóta út 304 00:13:43,290 --> 00:13:47,340 af lykkju ef ég grein, vel, ég leið framhjá voru Aaron myndi vera í þessari 305 00:13:47,340 --> 00:13:48,310 raðað tengda listanum. 306 00:13:48,310 --> 00:13:50,360 Ég þarf ekki að eyða tíma mínum að leita alla leið til enda. 307 00:13:50,360 --> 00:13:51,530 Svo er það sanngjarnt. 308 00:13:51,530 --> 00:13:54,710 Hvers vegna í ósköpunum getur þú vilt setja að rekast nafn á því 309 00:13:54,710 --> 00:13:56,660 upphafið af listanum? 310 00:13:56,660 --> 00:13:57,397 Hvað er það? 311 00:13:57,397 --> 00:13:58,680 >> Áhorfendur: [inaudible]. 312 00:13:58,680 --> 00:14:00,820 >> DAVID Malan: Það gæti tekið langan tíma til að fá til the endir af listanum. 313 00:14:00,820 --> 00:14:02,490 Og í raun, lengri og lengri. 314 00:14:02,490 --> 00:14:04,920 Því fleiri nöfnum þú setja það Byrja með, því lengur sem 315 00:14:04,920 --> 00:14:06,280 keðja er að fara að fá. 316 00:14:06,280 --> 00:14:07,890 Því lengur sem tengd Listinn er að fara að fá. 317 00:14:07,890 --> 00:14:09,420 Svo þú ert í raun bara að sóa tíma þínum. 318 00:14:09,420 --> 00:14:14,070 Kannski þú ert betur að viðhalda stöðug innsetningu sinni, stór O 1, 319 00:14:14,070 --> 00:14:18,470 því alltaf að setja rekast nafn á upphaf tengda lista, 320 00:14:18,470 --> 00:14:21,230 og ekki hafa áhyggjur eins mikið um flokkun. 321 00:14:21,230 --> 00:14:22,600 >> Hvað er besta svarið? 322 00:14:22,600 --> 00:14:23,320 Það er óljóst. 323 00:14:23,320 --> 00:14:26,140 Það konar veltur á hvað dreifing er, hvað mynstur er 324 00:14:26,140 --> 00:14:27,850 af nöfnum sem þú ert að setja. 325 00:14:27,850 --> 00:14:29,430 Það er ekki endilega augljóst svar. 326 00:14:29,430 --> 00:14:33,100 En hér, aftur er, hönnun tækifæri. 327 00:14:33,100 --> 00:14:37,220 >> Þannig að við fórum síðan á þetta, sem er í raun annar stór tækifæri 328 00:14:37,220 --> 00:14:38,180 p-setja 6. 329 00:14:38,180 --> 00:14:41,770 Og átta sig á, ef þú hefur ekki nú þegar, Zamyla kafar í báðum þessum, kjötkássa 330 00:14:41,770 --> 00:14:43,260 borðum og reynir, nánar. 331 00:14:43,260 --> 00:14:45,630 Og vídeó walkthrough er fellt í p-setja sérstakur. 332 00:14:45,630 --> 00:14:46,590 Þetta var Trie - 333 00:14:46,590 --> 00:14:51,670 T-R-I-E. Og hvað var áhugavert um þetta var að keyra tími 334 00:14:51,670 --> 00:14:59,510 að leita að nafni, eins og Maxwell síðasta sinn, var stór O hvað? 335 00:14:59,510 --> 00:15:01,040 Hvað er það? 336 00:15:01,040 --> 00:15:01,920 >> Áhorfendur: Fjöldi bréfa. 337 00:15:01,920 --> 00:15:02,550 >> DAVID Malan: Fjöldi bréfa. 338 00:15:02,550 --> 00:15:03,210 Ég heyrði tvennt. 339 00:15:03,210 --> 00:15:04,630 Fjöldi bréfa og föstu tíma. 340 00:15:04,630 --> 00:15:05,540 Svo skulum við fara með það fyrst. 341 00:15:05,540 --> 00:15:06,410 Fjölda af bréfum. 342 00:15:06,410 --> 00:15:10,195 Jæja, þessi gögn uppbygging, muna, er eins og tré, fjölskyldu tré, hvert af 343 00:15:10,195 --> 00:15:12,860 hnúður Hvers samanstanda af fylki. 344 00:15:12,860 --> 00:15:16,300 Og þeir fylki eru ábendingar til aðrar slíkar hnúður eða önnur slík 345 00:15:16,300 --> 00:15:17,670 fylki í trénu. 346 00:15:17,670 --> 00:15:22,890 >> Þannig að ef við vildum að þá ákveða hvort Maxwell er í hér, ég gæti farið 347 00:15:22,890 --> 00:15:26,890 til fyrsta array, á mjög toppur af tré, svokallaða rót, efst 348 00:15:26,890 --> 00:15:30,521 The Trie, og þá fylgja m músina, þá bendillinn, þá x, 349 00:15:30,521 --> 00:15:31,710 w, E, I, l. 350 00:15:31,710 --> 00:15:34,910 Og svo þegar ég sé einhverjum sérstökum tákn, táknað hér eins og þríhyrningur. 351 00:15:34,910 --> 00:15:38,480 Í merkjamál þú munt sjá að við leggjum til að þú framkvæmda sem bool, bara segja já 352 00:15:38,480 --> 00:15:40,540 eða nei, orð hættir hér. 353 00:15:40,540 --> 00:15:45,270 >> Jæja, þegar við höfum farið til M-A-X-W-E-L-L, líður eins og sjö, kannski 354 00:15:45,270 --> 00:15:48,910 átta ef við förum einn framhjá henni, átta Leiðir til að finna Maxwell. 355 00:15:48,910 --> 00:15:53,050 Eða við skulum kalla það K. En muna síðustu tími, hélt ég að ef það er 356 00:15:53,050 --> 00:15:57,540 raunhæft að hámarki lengd í orð, eins og 40-sumir-stakur persónur, sem 357 00:15:57,540 --> 00:16:00,810 Hámarkslengd felur stöðug gildi. 358 00:16:00,810 --> 00:16:05,770 Svo í raun, já, það er tæknilega stór O frá 8. eða 7, eða mjög stór O K. En 359 00:16:05,770 --> 00:16:09,420 ef það er endanlegt hettu á hvað K gæti verið, það er stöðug. 360 00:16:09,420 --> 00:16:12,080 Og svo er það stór O 1 á í lok dagsins. 361 00:16:12,080 --> 00:16:13,040 >> Ekki í hinum raunverulega heimi. 362 00:16:13,040 --> 00:16:15,960 Ekki þegar þú byrjar í raun að horfa á klukka sem hlaupandi program þíns. 363 00:16:15,960 --> 00:16:20,690 Það er alveg að fara að vera svolítið hægari en sannarlega fasti 364 00:16:20,690 --> 00:16:21,840 tíma með einu skrefi. 365 00:16:21,840 --> 00:16:25,540 Það er að fara að vera sjö eða átta skref, en samt er það miklu, miklu betra 366 00:16:25,540 --> 00:16:30,080 en reiknirit eins stór O í n að fer eftir stærð á því hvað er í 367 00:16:30,080 --> 00:16:31,220 gögn uppbygging. 368 00:16:31,220 --> 00:16:34,970 >> Tilkynning um kosti hér er að við getum sett milljón fleiri nöfn í þessu 369 00:16:34,970 --> 00:16:38,170 gögn uppbygging, en hversu margir fleiri skref er það að fara að taka okkur að finna 370 00:16:38,170 --> 00:16:40,480 Maxwell í því tilviki? 371 00:16:40,480 --> 00:16:40,780 Ekkert. 372 00:16:40,780 --> 00:16:41,820 Hann er óbreytt. 373 00:16:41,820 --> 00:16:45,480 Og hingað til, ég held ekki að við höfum séð dæmi um gögn uppbygging eða 374 00:16:45,480 --> 00:16:48,560 reiknirit sem var alveg óháð ytri 375 00:16:48,560 --> 00:16:50,040 hegðun eins og þessi. 376 00:16:50,040 --> 00:16:51,160 En þetta getur ekki verið magnað. 377 00:16:51,160 --> 00:16:52,900 Þetta getur ekki verið eina lausnin fyrir p-setja 378 00:16:52,900 --> 00:16:53,570 >> Og það er ekki. 379 00:16:53,570 --> 00:16:55,980 Þetta er ekki endilega gögnin uppbygging þú ættir sökkva til, 380 00:16:55,980 --> 00:16:58,220 því eins og kjötkássa matskeið, tradeoff. 381 00:16:58,220 --> 00:17:00,500 Hvað er það verð sem þú borgar hér? 382 00:17:00,500 --> 00:17:00,940 Minni. 383 00:17:00,940 --> 00:17:02,890 Ég meina, þetta er grimmilegur magn af minni. 384 00:17:02,890 --> 00:17:05,569 Og þú getur ekki alveg séð það hér því höfundur þessarar mynd 385 00:17:05,569 --> 00:17:09,420 augljóslega stytt öllum fylki, og við erum ekki að sjá fullt af A og 386 00:17:09,420 --> 00:17:12,700 Er b og s C og Spurningar og svör er Y og er Z í þessum fylki. 387 00:17:12,700 --> 00:17:13,630 En þeir eru þar. 388 00:17:13,630 --> 00:17:17,660 >> Hver af þessum hnúta er í heild array sumra 26 eða fleiri bæti, hvert um 389 00:17:17,660 --> 00:17:19,170 sem táknar bréf. 390 00:17:19,170 --> 00:17:22,920 27 í okkar tilviki, svo að við getum styðja úrfellingarmerki í Heimadæmi. 391 00:17:22,920 --> 00:17:27,030 Þannig að þetta gögn uppbygging er í raun, mjög þéttur og breiður. 392 00:17:27,030 --> 00:17:30,880 Og það eitt og sér gæti endað hægur það niður, eða að minnsta kosti kosta þig 393 00:17:30,880 --> 00:17:32,240 miklu meira pláss. 394 00:17:32,240 --> 00:17:34,020 En aftur, getum við dregið samanburð hér. 395 00:17:34,020 --> 00:17:39,190 >> Muna á meðan bak, náð við mikið meira spennandi hlaupandi tíma í flokkun 396 00:17:39,190 --> 00:17:42,880 þegar við notum Mergesort, en verðið við greitt að ná n log n fyrir sameiningu 397 00:17:42,880 --> 00:17:46,930 Raða þarf að við eyða meira hvað auðlind? 398 00:17:46,930 --> 00:17:47,690 Meira pláss. 399 00:17:47,690 --> 00:17:50,530 Við þurftum öðru fylki til afrita fólk inn, rétt eins og 400 00:17:50,530 --> 00:17:51,620 við gerðum hér á sviðinu. 401 00:17:51,620 --> 00:17:55,880 Svo aftur, engin skýr sigurvegari, en bara huglæg hönnun 402 00:17:55,880 --> 00:17:57,710 ákvarðanir um að vera. 403 00:17:57,710 --> 00:17:58,060 >> Allt í lagi. 404 00:17:58,060 --> 00:17:59,130 Svo hvernig um þetta? 405 00:17:59,130 --> 00:18:02,050 Hver kannast sem D-Hall? 406 00:18:02,050 --> 00:18:02,440 OK. 407 00:18:02,440 --> 00:18:03,170 Svo þrír af okkur að gera. 408 00:18:03,170 --> 00:18:03,750 Mather House. 409 00:18:03,750 --> 00:18:05,070 Svo er þetta fyrir veitingastöðum Mather er. 410 00:18:05,070 --> 00:18:09,650 Ég veðja alla veitingastöðum sölum hafa stafla af bakka svona. 411 00:18:09,650 --> 00:18:11,950 Og þetta er í raun fulltrúi um eitthvað sem við höfum 412 00:18:11,950 --> 00:18:13,050 augljóslega séð nú þegar. 413 00:18:13,050 --> 00:18:14,850 Við kölluð það bókstaflega stafla. 414 00:18:14,850 --> 00:18:18,970 Og stafla, í skilmálar af þinn minni tölva ', er þar gögn fer 415 00:18:18,970 --> 00:18:20,460 en aðgerðir eru kallaðir. 416 00:18:20,460 --> 00:18:23,410 >> Til dæmis, fara hvaða tegundir af hlutum á mánudaginn með tilliti til 417 00:18:23,410 --> 00:18:27,420 minni skipulag sem við höfum rætt í vikur síðustu? 418 00:18:27,420 --> 00:18:28,736 Hvað er það? 419 00:18:28,736 --> 00:18:29,670 >> Áhorfendur: Símtöl til aðgerða. 420 00:18:29,670 --> 00:18:30,260 >> DAVID Malan: Fyrirgefðu. 421 00:18:30,260 --> 00:18:31,210 >> Áhorfendur: Símtöl til aðgerða. 422 00:18:31,210 --> 00:18:33,590 >> DAVID Malan: Símtöl til aðgerða, en sérstaklega, hvað er inni hvers 423 00:18:33,590 --> 00:18:35,340 þessir rammar? 424 00:18:35,340 --> 00:18:37,220 Hvers konar hlutum? 425 00:18:37,220 --> 00:18:37,460 Já. 426 00:18:37,460 --> 00:18:38,500 Svo staðbundnar breytur. 427 00:18:38,500 --> 00:18:43,080 Hvenær sem við vantaði staðbundna geymslu, eins rifrildi, eða int ég, eða int 428 00:18:43,080 --> 00:18:45,940 Hitastig, eða hvað á staðnum breyta er, höfum við verið 429 00:18:45,940 --> 00:18:47,210 setja það á mánudaginn. 430 00:18:47,210 --> 00:18:49,610 Og við köllum það stafla því þess layering hugmynd. 431 00:18:49,610 --> 00:18:52,940 Bara svona passar upp við raunveruleikann, hugtakið stað. 432 00:18:52,940 --> 00:18:56,650 >> En það kemur í ljós að stafla getur einnig talist gögn uppbygging, sem 433 00:18:56,650 --> 00:19:00,110 val til fjölda, val til tengda lista. 434 00:19:00,110 --> 00:19:02,770 Eitthvað eðli meira áhugavert sem getur samt verið 435 00:19:02,770 --> 00:19:06,030 útfærð með annaðhvort þeirra hlutir, en það er önnur tegund af 436 00:19:06,030 --> 00:19:09,140 gögn uppbygging styðja, virkilega, aðeins tvær aðgerðir. 437 00:19:09,140 --> 00:19:11,000 En þú getur bætt á áhugamaður lögun en þessir. 438 00:19:11,000 --> 00:19:12,180 En þetta eru grundvallaratriði - 439 00:19:12,180 --> 00:19:13,510 ýta og skjóta. 440 00:19:13,510 --> 00:19:19,240 >> Og hugmyndin með stafla er að ef ég hér hafa, með eða án Annenberg 441 00:19:19,240 --> 00:19:22,880 vitund, bakki úr næsta húsi með númer 9 á það. 442 00:19:22,880 --> 00:19:23,870 Svo bara int. 443 00:19:23,870 --> 00:19:26,990 Og ég vil að ýta þessu á gögnum uppbygging, sem nú er tómur. 444 00:19:26,990 --> 00:19:28,790 Hugleiddu þetta neðst á stafla. 445 00:19:28,790 --> 00:19:33,150 Ég myndi ýta þetta númer 9 inn á stafla, og nú er það rétt þar. 446 00:19:33,150 --> 00:19:36,040 >> En áhugaverður hlutur óður í stafla er að ef ég vil nú að ýta 447 00:19:36,040 --> 00:19:40,210 einhver önnur gildi, eins og 17, og ég ýta þetta á mánudaginn, ég er að fara að gera 448 00:19:40,210 --> 00:19:43,290 eina leiðandi hlutur, ég ætla bara að fara Til að setja það rétt þar sem við mennirnir 449 00:19:43,290 --> 00:19:45,180 myndi vera hneigðist að setja það á toppinn. 450 00:19:45,180 --> 00:19:48,850 En hvað er áhugavert nú er, hvernig fæ ég á 9? 451 00:19:48,850 --> 00:19:50,670 Þú veist, ég er ekki án einhverrar vinnu. 452 00:19:50,670 --> 00:19:54,070 >> Svo hvað er áhugavert um stafla er að við hönnun, 453 00:19:54,070 --> 00:19:56,330 það er LIFO gögn uppbygging. 454 00:19:56,330 --> 00:19:59,680 Kjánalegt leið til að lýsa síðast í, fyrst út. 455 00:19:59,680 --> 00:20:03,280 Svo í síðasta númer í á þessum tíma var 17. 456 00:20:03,280 --> 00:20:07,540 Svo ef ég vil skjóta eitthvað af á mánudaginn, það geta aðeins verið 17. 457 00:20:07,540 --> 00:20:11,890 Þannig að það er nauðsynlegur til þess starfsemi hér, þar sem síðasta atriði 458 00:20:11,890 --> 00:20:14,260 í að vera sá fyrsti út. 459 00:20:14,260 --> 00:20:16,440 Þess vegna skammstöfun, LIFO. 460 00:20:16,440 --> 00:20:19,160 >> Svo hvers vegna gæti þetta verið gagnlegt? 461 00:20:19,160 --> 00:20:22,690 Eru aðstæður þeirra sem þú vilt að vilja gögn uppbygging eins og þetta? 462 00:20:22,690 --> 00:20:24,810 Jæja, það er verið vissulega gagnlegt inni í tölvunni. 463 00:20:24,810 --> 00:20:29,050 Svo stýrikerfi nota skýrt þetta konar uppbyggingu gagna í stöflum. 464 00:20:29,050 --> 00:20:32,800 Við munum einnig sjá sömu hugmynd þegar það kemur að því að vefur blaðsíða. 465 00:20:32,800 --> 00:20:35,890 Svo í þessari viku og í næstu viku og utan, og eins og þú byrja að innleiða vefnum 466 00:20:35,890 --> 00:20:39,490 síður á tungumáli kallast HTML, getur þú reyndar nota gögn uppbygging eins 467 00:20:39,490 --> 00:20:42,690 þetta til að ákvarða hvort síða er rétt sniðinn. 468 00:20:42,690 --> 00:20:47,170 Vegna þess að við munum sjá allar vefsíður fylgja eins konar stigveldi, sem inndrátt 469 00:20:47,170 --> 00:20:52,030 sem mun, í lok dagsins, verið tré uppbyggingu undir hetta. 470 00:20:52,030 --> 00:20:53,620 Svo meira um það í bara smá. 471 00:20:53,620 --> 00:20:56,560 >> En nú skulum við leggja fyrir stund, hvernig gætum við farið um 472 00:20:56,560 --> 00:20:58,830 alþingismaður hvað stakkur er? 473 00:20:58,830 --> 00:21:03,370 Leyfðu mér að leggja til að við framkvæmd stafla með kóða eins og þetta. 474 00:21:03,370 --> 00:21:07,990 Svo stafla er að fara að hafa innan þess tvennt, fylki, sem kallast stæði, 475 00:21:07,990 --> 00:21:09,510 bara til að vera í samræmi við kynningu. 476 00:21:09,510 --> 00:21:12,660 Og hvert atriði í þeirri fylking er að fara til vera a tegund int. 477 00:21:12,660 --> 00:21:14,740 Og getu er væntanlega hvað? 478 00:21:14,740 --> 00:21:18,796 Vegna þess að ég hef ekki skrifað fullur skýring hér. 479 00:21:18,796 --> 00:21:21,535 >> Það er líklega hámark stærð fylkisins. 480 00:21:21,535 --> 00:21:25,150 Og það er líklega skilgreind sem mikil define efst á skránni, sumir 481 00:21:25,150 --> 00:21:28,450 konar fasti skyn eins með eingöngu hástafi. 482 00:21:28,450 --> 00:21:32,250 Svo einhvers staðar getu er skilgreint eins og hæsta mögulega stærð. 483 00:21:32,250 --> 00:21:35,590 Á sama tíma, innan við gögn uppbygging þekktur sem stafla það verður 484 00:21:35,590 --> 00:21:38,630 að vera heiltala bara þekkt einfaldlega sem stærð. 485 00:21:38,630 --> 00:21:43,400 >> Þannig að ef ég væri að tákna þetta núna pictorially, skulum gera ráð fyrir að þetta 486 00:21:43,400 --> 00:21:48,070 heild svartur kassi táknar stafla mitt. 487 00:21:48,070 --> 00:21:50,070 Innan þess er tvær breytur. 488 00:21:50,070 --> 00:21:54,780 Þannig að ég ætla að draga fyrsta sem stærð. 489 00:21:54,780 --> 00:21:57,420 Og annað sem ég ætla að draga eins og fylki. 490 00:21:57,420 --> 00:22:01,060 >> En bara til að halda hlutum skipulegan, venjulega myndi ég draga fylki eins 491 00:22:01,060 --> 00:22:04,910 þetta, en það er góður af gaman ef við passa veruleika, eða 492 00:22:04,910 --> 00:22:06,230 passa andlega fyrirmynd. 493 00:22:06,230 --> 00:22:12,880 Svo láta mig draga stað array lóðrétt, sem er bara, aftur, 494 00:22:12,880 --> 00:22:13,840 listamannsins flutningur. 495 00:22:13,840 --> 00:22:16,610 Skiptir ekki máli hvað það er undir hetta. 496 00:22:16,610 --> 00:22:20,350 Og við munum segja að við vanræksla, getu er að fara að vera þrír. 497 00:22:20,350 --> 00:22:23,480 Þannig að þetta verður staðsetning 0, þetta verður staðsetning 1, þessi 498 00:22:23,480 --> 00:22:25,740 verður staðsetning 2. 499 00:22:25,740 --> 00:22:29,330 >> Ef ég mútur með streitu boltanum, myndi einhver vilja koma upp og keyra 500 00:22:29,330 --> 00:22:30,870 borð hér fyrir réttlátur a augnablik? 501 00:22:30,870 --> 00:22:31,960 OK, sá hönd þína fyrst. 502 00:22:31,960 --> 00:22:33,950 Komdu upp. 503 00:22:33,950 --> 00:22:36,500 Allt í lagi. 504 00:22:36,500 --> 00:22:38,760 Svo ég held að það sé Steven. 505 00:22:38,760 --> 00:22:40,035 Komdu upp. 506 00:22:40,035 --> 00:22:40,770 Allt í lagi. 507 00:22:40,770 --> 00:22:46,760 >> En geri ráð fyrir að við nú til baka til fyrstu ástand í heiminum þar sem ég 508 00:22:46,760 --> 00:22:52,180 hafa bara lýst stafla, og það er að fara að vera á getu þrjú. 509 00:22:52,180 --> 00:22:54,470 En stærð hefur ekki enn verið ákveðinn. 510 00:22:54,470 --> 00:22:56,100 Stæði hefur ekki enn verið ákveðinn. 511 00:22:56,100 --> 00:22:57,300 Svo a par af spurningum fyrst. 512 00:22:57,300 --> 00:23:01,310 Og láta mig gefa þér mic svo þú getur þátt virkari í þessu. 513 00:23:01,310 --> 00:23:05,190 >> Svo hvað er inni á stærð á þessari stundu í tíma ef allt sem ég hef gert er 514 00:23:05,190 --> 00:23:09,340 lýst stafla með ein lína af kóða? 515 00:23:09,340 --> 00:23:10,100 >> STEVEN: Ekki mikið. 516 00:23:10,100 --> 00:23:12,080 >> DAVID Malan: OK, ekki mikið. 517 00:23:12,080 --> 00:23:14,410 Vitum við hvað er inni stærð, vitum við hvað er inni 518 00:23:14,410 --> 00:23:16,330 af þessu fylki hér? 519 00:23:16,330 --> 00:23:18,630 >> STEVEN: Bara handahófi númer, ekki satt? 520 00:23:18,630 --> 00:23:20,220 Bara - 521 00:23:20,220 --> 00:23:23,230 >> DAVID Malan: Já, ég ætla að kalla það númer, en handahófi - 522 00:23:23,230 --> 00:23:23,820 >> STEVEN: Things. 523 00:23:23,820 --> 00:23:28,290 >> DAVID Malan: Hluti eins handahófi 524 00:23:28,290 --> 00:23:28,870 >> STEVEN: Bits. 525 00:23:28,870 --> 00:23:29,530 >> DAVID Malan: Bits, ekki satt? 526 00:23:29,530 --> 00:23:31,190 Svo gildum sorp, ekki satt? 527 00:23:31,190 --> 00:23:33,470 Svo permutations af 0 og 1 er. 528 00:23:33,470 --> 00:23:35,920 Leifar af fyrri málnotkun þessa minni. 529 00:23:35,920 --> 00:23:38,150 Og við í raun ekki vita hvað gildin eru, svo við draga yfirleitt þá 530 00:23:38,150 --> 00:23:38,930 sem spurningarmerkjum. 531 00:23:38,930 --> 00:23:41,990 >> Svo það fyrsta sem við erum væntanlega fara til að vilja gera hér - 532 00:23:41,990 --> 00:23:46,630 og láta mig gefa þessu sviði inni þarna nafn - stæði. 533 00:23:46,630 --> 00:23:49,540 Hvað eigum við að frumstilla væntanlega stærð til ef við viljum 534 00:23:49,540 --> 00:23:51,040 byrjað að nota þessa stafla? 535 00:23:51,040 --> 00:23:53,070 >> STEVEN: Bakki er undir 3. 536 00:23:53,070 --> 00:23:53,910 >> DAVID Malan: Svo, OK. 537 00:23:53,910 --> 00:23:56,710 Til að vera skýr, er getu lýst annars staðar eins og þrjú. 538 00:23:56,710 --> 00:23:58,570 Og það er það sem ég hef notað að úthluta array. 539 00:23:58,570 --> 00:24:03,535 Stærð er að fara að vísa til hversu margir stæði eru nú á mánudaginn. 540 00:24:03,535 --> 00:24:03,880 >> STEVEN: Zero. 541 00:24:03,880 --> 00:24:04,460 >> DAVID Malan: Svo það ætti að vera núll. 542 00:24:04,460 --> 00:24:07,760 Svo fara á undan, og með hvaða fingri, draga núll að stærð. 543 00:24:07,760 --> 00:24:08,440 Allt í lagi. 544 00:24:08,440 --> 00:24:10,920 Svo nú, hvað er inni í þessu Hér vitum við ekki. 545 00:24:10,920 --> 00:24:12,160 Þetta eru í raun bara sorp gildi. 546 00:24:12,160 --> 00:24:14,800 Svo við gætum draga spurningarmerki, en skulum halda stjórn hreint fyrir nú 547 00:24:14,800 --> 00:24:16,300 því það skiptir ekki máli hvað er þarna. 548 00:24:16,300 --> 00:24:19,130 Við þurfum ekki að frumstilla array við neitt, því ef við vitum að 549 00:24:19,130 --> 00:24:23,100 the stærð af the stakkur er núll, vel, við ætti ekki að vera að horfa á neitt í 550 00:24:23,100 --> 00:24:25,590 þetta array samt á þessum tímapunkti. 551 00:24:25,590 --> 00:24:29,970 >> Svo nú ætla ég að ýta á númer 9 á mánudaginn. 552 00:24:29,970 --> 00:24:33,750 Hvernig ættum við að uppfæra gögn uppbygging inni af þessu svarta kassanum? 553 00:24:33,750 --> 00:24:35,540 Hvaða gildi þarf að breyta? 554 00:24:35,540 --> 00:24:36,200 >> STEVEN: Innan - 555 00:24:36,200 --> 00:24:37,400 stærð? 556 00:24:37,400 --> 00:24:37,650 >> DAVID Malan: OK. 557 00:24:37,650 --> 00:24:38,770 Stærð ætti að verða hvað? 558 00:24:38,770 --> 00:24:39,580 >> STEVEN: Stærð vildi vera einn. 559 00:24:39,580 --> 00:24:39,870 >> DAVID Malan: OK. 560 00:24:39,870 --> 00:24:41,110 Svo stærð ætti að verða eitt. 561 00:24:41,110 --> 00:24:42,540 Svo þú getur gert þetta á nokkra vegu. 562 00:24:42,540 --> 00:24:46,920 Leyfðu mér að gefa þér, nú þinn fingur er strokleður. 563 00:24:46,920 --> 00:24:47,260 Allt í lagi. 564 00:24:47,260 --> 00:24:49,960 Þá er nú fingurinn bursta. 565 00:24:49,960 --> 00:24:50,330 Allt í lagi. 566 00:24:50,330 --> 00:24:52,820 Og nú hefur það annað að breyta, augljóslega, í gögn uppbygging? 567 00:24:52,820 --> 00:24:57,060 >> STEVEN: Við erum að fara frá botn allt að 9. 568 00:24:57,060 --> 00:24:57,760 >> DAVID Malan: 9. 569 00:24:57,760 --> 00:24:58,420 OK, Good. 570 00:24:58,420 --> 00:25:01,550 Svo enn skiptir ekki máli hvað er á Staðsetning einn eða tveir af því að þeir eru 571 00:25:01,550 --> 00:25:04,520 sorp gildi, en við ættum ekki að nenna leita þar vegna stærð er 572 00:25:04,520 --> 00:25:07,540 segja okkur að aðeins fyrsti þáttur er í raun lögmætur. 573 00:25:07,540 --> 00:25:10,400 Svo nú er ég að ýta 17 á listanum. 574 00:25:10,400 --> 00:25:11,830 Hvað gerist við þessa mynd? 575 00:25:11,830 --> 00:25:14,720 >> STEVEN: Svo stærð er að fara að fara til tveggja. 576 00:25:14,720 --> 00:25:15,300 >> DAVID Malan: OK. 577 00:25:15,300 --> 00:25:16,070 Þú ert Strokleður - 578 00:25:16,070 --> 00:25:16,810 Úps. 579 00:25:16,810 --> 00:25:18,026 Þú ert strokleður. 580 00:25:18,026 --> 00:25:18,840 >> STEVEN: Strokleður. 581 00:25:18,840 --> 00:25:19,720 >> DAVID Malan: Þú ert bursta. 582 00:25:19,720 --> 00:25:20,560 >> STEVEN: Brush. 583 00:25:20,560 --> 00:25:20,920 >> DAVID Malan: OK. 584 00:25:20,920 --> 00:25:21,600 Og hvað annað? 585 00:25:21,600 --> 00:25:22,600 >> STEVEN: Og þá erum við - 586 00:25:22,600 --> 00:25:22,915 >> DAVID Malan: Við ýtt 17. 587 00:25:22,915 --> 00:25:24,760 >> STEVEN: Við fast 17 ofan, svo - 588 00:25:24,760 --> 00:25:25,710 >> DAVID Malan: OK, gott. 589 00:25:25,710 --> 00:25:27,040 >> STEVEN: - falla því niður. 590 00:25:27,040 --> 00:25:27,530 >> DAVID Malan: Allt í lagi. 591 00:25:27,530 --> 00:25:27,940 Það er að fá auðvelt. 592 00:25:27,940 --> 00:25:29,300 Ég ætla ekki að hjálpa þér í þetta sinn. 593 00:25:29,300 --> 00:25:30,510 Ýta 22. 594 00:25:30,510 --> 00:25:31,720 >> STEVEN: Lokið. 595 00:25:31,720 --> 00:25:34,870 Becoming strokleður. 596 00:25:34,870 --> 00:25:37,340 Ég er að verða bursta. 597 00:25:37,340 --> 00:25:39,340 Og þá er ég að setja 22. 598 00:25:39,340 --> 00:25:40,100 >> DAVID Malan: 22. 599 00:25:40,100 --> 00:25:40,620 Excellent. 600 00:25:40,620 --> 00:25:41,380 Svo einu sinni enn. 601 00:25:41,380 --> 00:25:44,280 Ég ætla nú að fara að ýta á mánudaginn 26.. 602 00:25:44,280 --> 00:25:46,350 >> STEVEN: Ooh. 603 00:25:46,350 --> 00:25:50,278 Ó gosh. 604 00:25:50,278 --> 00:25:52,520 Þú lent virkilega mig burt vörður. 605 00:25:52,520 --> 00:25:53,703 >> DAVID Malan: Þú varst ekki sjá þetta koma? 606 00:25:53,703 --> 00:25:55,930 >> STEVEN: Ég vissi ekki að sjá þetta koma. 607 00:25:55,930 --> 00:25:58,756 Gætum við aftur fyrstu getu? 608 00:25:58,756 --> 00:25:59,790 >> DAVID Malan: Það er góð spurning. 609 00:25:59,790 --> 00:26:02,360 Þannig að við höfum konar máluð okkur í horninu hér. 610 00:26:02,360 --> 00:26:06,740 Það raunverulega er ekki gott út fyrir Steven vegna þess að við höfum úthlutað þessu fylki 611 00:26:06,740 --> 00:26:09,130 statically, svo að segja, inni af gögn uppbygging. 612 00:26:09,130 --> 00:26:12,170 Og við höfum í raun erfitt dulmáli það að vera af stærð þrjú. 613 00:26:12,170 --> 00:26:14,170 Svo við getum í raun ekki endurúthluta því. 614 00:26:14,170 --> 00:26:20,020 >> Við gætum ef við fórum aftur í, við skilgreina stæði að vera bendill sem 615 00:26:20,020 --> 00:26:22,300 við notum þá malloc að hönd minni til. 616 00:26:22,300 --> 00:26:25,050 Vegna þess að ef við fengum minni frá hrúga gegnum malloc, við 617 00:26:25,050 --> 00:26:26,430 gæti þá losa hana. 618 00:26:26,430 --> 00:26:29,630 En áður en frjáls það, gætum við endurúthluta stærri klumpur af minni, 619 00:26:29,630 --> 00:26:31,330 uppfæra músina, og svo framvegis. 620 00:26:31,330 --> 00:26:33,500 En nú, er þetta virkilega besta sem við getum gert. 621 00:26:33,500 --> 00:26:36,360 Ýta og skjóta eru væntanlega að fara að þurfa að merki sumir villa. 622 00:26:36,360 --> 00:26:40,270 >> Svo til dæmis, framkvæmd okkar af ýta gæti skila bool sem 623 00:26:40,270 --> 00:26:42,390 áður skilað satt, satt, satt. 624 00:26:42,390 --> 00:26:48,390 En í fjórða sinn, það er að fara að hafa að aftur ósatt, til dæmis. 625 00:26:48,390 --> 00:26:48,540 Allt í lagi. 626 00:26:48,540 --> 00:26:49,540 Mjög vel gert. 627 00:26:49,540 --> 00:26:50,060 Til hamingju. 628 00:26:50,060 --> 00:26:52,160 Þú hefur unnið streitu boltanum í dag. 629 00:26:52,160 --> 00:26:53,110 >> [Applause] 630 00:26:53,110 --> 00:26:54,382 >> STEVEN: Þakka þér. 631 00:26:54,382 --> 00:26:55,680 >> DAVID Malan: Þakka þér. 632 00:26:55,680 --> 00:26:59,740 OK, svo virðist þetta vera ekki mikið um skref fram á við, ekki satt? 633 00:26:59,740 --> 00:27:01,410 Við lýst þessari gögn uppbygging. 634 00:27:01,410 --> 00:27:02,320 Það hefur verið sannfærandi, ekki satt? 635 00:27:02,320 --> 00:27:03,200 Stýrikerfi eins og það. 636 00:27:03,200 --> 00:27:06,360 Virðist vefnum geta nýtt þetta, og önnur forrit enn. 637 00:27:06,360 --> 00:27:10,870 En hvað heimskulegt takmörkun sem við erum aftur til að raða í viku tvö mörk 638 00:27:10,870 --> 00:27:12,880 þar sem við höfum fasta stærð fylki. 639 00:27:12,880 --> 00:27:15,010 >> Þannig að það eru örugglega nokkrar leiðir sem við gætum leyst þetta. 640 00:27:15,010 --> 00:27:18,750 Við gætum virk úthluta array, ekki af harður erfðaskrá það sem ég hef 641 00:27:18,750 --> 00:27:22,600 gert hér, heldur aftur lýsa þetta, bara til að vera skýr, og 642 00:27:22,600 --> 00:27:23,830 eitthvað eins og this. 643 00:27:23,830 --> 00:27:29,040 Int * stæði, ekki ákveða á afkastagetu enn. 644 00:27:29,040 --> 00:27:35,460 En þegar ég lýsa stafla annars staðar í númerið mitt, gæti ég þá kalla malloc, 645 00:27:35,460 --> 00:27:38,250 fá veffang klumpur minni, og ég gat tengt 646 00:27:38,250 --> 00:27:39,980 að tölu til stæði. 647 00:27:39,980 --> 00:27:43,340 >> Og þá, því það er bara klumpur af minni, gæti ég haldið áfram að nota veldi 648 00:27:43,340 --> 00:27:45,450 krappi sýndur á hefðbundinn hátt. 649 00:27:45,450 --> 00:27:49,020 Því aftur, það er tegund af þessu hagnýtur jafngildi fylki og 650 00:27:49,020 --> 00:27:50,820 klumpur af minni sem koma baka frá malloc. 651 00:27:50,820 --> 00:27:53,090 Við getum meðhöndla einn sem hin nota músina tölur eða 652 00:27:53,090 --> 00:27:54,440 ferningur krappi tákn. 653 00:27:54,440 --> 00:27:55,660 Svo er það ein aðferð. 654 00:27:55,660 --> 00:28:00,120 >> En hvernig annars gætum við framkvæma þetta Sama gögn uppbygging, hugsanlega? 655 00:28:00,120 --> 00:28:00,280 Ekki satt? 656 00:28:00,280 --> 00:28:04,530 Mér finnst eins og við leyst bara þetta vandamál eins og fyrir viku síðan. 657 00:28:04,530 --> 00:28:08,860 Hvað var lausn á þessu vandamáli sem Steven hljóp inn? 658 00:28:08,860 --> 00:28:10,370 Svo tengd listum, ekki satt. 659 00:28:10,370 --> 00:28:13,410 >> Ef vandamálið er að við erum að mála okkur út í horn með því að úthluta 660 00:28:13,410 --> 00:28:17,580 fyrirfram of lítið minni að við þá hafa einhvern veginn tekist á við, vel, 661 00:28:17,580 --> 00:28:19,880 hvers vegna ekki bara að forðast það gefa með öllu? 662 00:28:19,880 --> 00:28:26,170 Hvers vegna ekki bara að lýsa stæði til að vera bendi á hnút, Ergo tengda lista, 663 00:28:26,170 --> 00:28:30,740 og þá einfaldlega úthluta nýja hnúta hvert skipti Steven þarf að passa 664 00:28:30,740 --> 00:28:32,400 númer í gögn uppbygging. 665 00:28:32,400 --> 00:28:34,200 >> Svo myndin þyrfti að breyta. 666 00:28:34,200 --> 00:28:38,220 Það er ekki að fara að vera eins hrein og eins einfalt og bara fjölda þremur ints. 667 00:28:38,220 --> 00:28:42,970 Nú það er að fara til vera a bendi til a strúktúr, og að struct er að fara að 668 00:28:42,970 --> 00:28:44,830 hafa int og næsta músina. 669 00:28:44,830 --> 00:28:47,670 Það er að fara að leiða í gegnum þessi bendillinn til annars svo strúktúr til 670 00:28:47,670 --> 00:28:48,600 annars slíks strúktúr. 671 00:28:48,600 --> 00:28:50,560 Svo myndin væri í raun fá smá Messier. 672 00:28:50,560 --> 00:28:52,950 Og við myndum hafa örvarnar binda allt saman. 673 00:28:52,950 --> 00:28:55,280 >> En það er allt í lagi, ekki satt, vegna þess að við höfum séð hvernig á að gera þetta. 674 00:28:55,280 --> 00:28:58,180 Og þegar þú færð ánægð innleiða eitthvað eins tengt 675 00:28:58,180 --> 00:29:01,450 lista, sem þú þarft að gera ef þú valið að innleiða kjötkássa borð með 676 00:29:01,450 --> 00:29:05,120 aðskilin chaining fyrir p-setja 6, getur þú nota hana sem byggja blokk, eða 677 00:29:05,120 --> 00:29:08,870 efni, eða í grunni tala, sem aðferð, eitthvað sem þú setur, þér 678 00:29:08,870 --> 00:29:12,560 búið til eigin þraut stykki sem þú getur þá endurnýta. 679 00:29:12,560 --> 00:29:17,090 Svo Tradeoffs, en hugsanlega lausnir að við höfum í raun séð áður. 680 00:29:17,090 --> 00:29:20,560 >> Svo oft, sérð þú þetta á hverjum ár eða tvö þegar Apple gefa út 681 00:29:20,560 --> 00:29:23,060 eitthvað nýtt, og allt klikkaði fólk lína upp fyrir utan Apple 682 00:29:23,060 --> 00:29:27,050 geyma að kaupa lélegur þeirra uppfærsla á vélbúnaði. 683 00:29:27,050 --> 00:29:30,420 Ég segi þetta, það er allt í lagi, vegna þess að Ég er einn af þeim. 684 00:29:30,420 --> 00:29:35,140 Svo hvers konar gögn uppbygging gæti tákna þessa veruleika? 685 00:29:35,140 --> 00:29:36,980 >> Jæja, við skulum kalla það biðröð, línu. 686 00:29:36,980 --> 00:29:40,270 Svo British myndi kalla það yfirleitt biðröð samt, svo það er gott nafn. 687 00:29:40,270 --> 00:29:44,960 Og tvær aðgerðir sem biðröð skal styðja við munum hringja í e, 688 00:29:44,960 --> 00:29:48,900 rekstur og dequeue rekstur, sem eru svipaðar í 689 00:29:48,900 --> 00:29:50,120 andi að ýta og skjóta. 690 00:29:50,120 --> 00:29:54,060 Það er bara svona mismunandi í venju, hvað við köllum þetta. 691 00:29:54,060 --> 00:29:57,680 En til e, eitthvað þýðir að bæta eða setja það til the gögn uppbygging. 692 00:29:57,680 --> 00:29:59,570 Til dequeue þýðir að fjarlægja það. 693 00:29:59,570 --> 00:30:05,170 En þar stafla var LIFO gögn uppbyggingu, biðröð er fyrst í 694 00:30:05,170 --> 00:30:06,740 fyrst út gögn uppbygging. 695 00:30:06,740 --> 00:30:10,050 >> Ef þú ert fyrsta manneskjan í línu, þú verður að vera fyrsta manneskjan til að fá 696 00:30:10,050 --> 00:30:12,420 af línu og kaupa nýja tækið. 697 00:30:12,420 --> 00:30:18,070 Ímyndaðu þér hvernig uppnámi þetta fólk væri ef Apple staðinn notað stafla, fyrir 698 00:30:18,070 --> 00:30:21,250 dæmi, til að hrinda samtíningur upp á nýja leikfangið þitt. 699 00:30:21,250 --> 00:30:24,310 Svo biðraðir skynsamleg, vissulega, og við getum hugsað um alls konar 700 00:30:24,310 --> 00:30:27,480 forrit, væntanlega, að biðröð, sérstaklega þegar þú vilt sanngirni. 701 00:30:27,480 --> 00:30:30,040 Svo hvernig gæti við framkvæmd þessara sem gögn uppbygging? 702 00:30:30,040 --> 00:30:33,680 >> Jæja, leggja ég að við gætum þarf að gera það með þessum hætti. 703 00:30:33,680 --> 00:30:35,225 Þannig að ég ætla að nú hafa númer. 704 00:30:35,225 --> 00:30:38,190 Þannig að við munum halda þetta einfalt og ekki endilega tala hvað varðar bakka. 705 00:30:38,190 --> 00:30:40,220 Bara tölur sem fólk af fengið. 706 00:30:40,220 --> 00:30:43,760 Getu er að fara að, aftur, laga um heildarfjöldi fólks sem getur verið í 707 00:30:43,760 --> 00:30:46,900 Þessi lína, sem þrír eða hvað annað gildi. 708 00:30:46,900 --> 00:30:50,760 >> En ég leggja til að ég þarf að halda utan ekki aðeins að stærð sem 709 00:30:50,760 --> 00:30:52,370 biðröð, hversu margir hlutir í henni. 710 00:30:52,370 --> 00:30:56,310 Svo er stærð núverandi stærð, getu er hámarks stærð. 711 00:30:56,310 --> 00:30:58,540 Bara aftur, tegundaheiti með því að venju. 712 00:30:58,540 --> 00:31:03,680 Hvers vegna þarf ég til viðbótar int inni af biðröð að halda utan um hver er í 713 00:31:03,680 --> 00:31:05,365 framan á línu? 714 00:31:05,365 --> 00:31:07,930 715 00:31:07,930 --> 00:31:10,910 Hvers vegna þarf ég að gera það í þessu tilfelli? 716 00:31:10,910 --> 00:31:14,750 717 00:31:14,750 --> 00:31:16,190 >> Jæja, hvernig er þetta mynd að fara að breyta? 718 00:31:16,190 --> 00:31:19,280 Ég get sennilega endurnýta mest á þessari mynd. 719 00:31:19,280 --> 00:31:21,480 Leyfðu mér að fara á undan og eyða hvað er hér. 720 00:31:21,480 --> 00:31:24,580 Við munum gefa þessu örlítið mismunandi nafn upp hér. 721 00:31:24,580 --> 00:31:28,930 Skulum losna við 17, skulum losna af 9, skulum losna við 3. 722 00:31:28,930 --> 00:31:30,410 Og við skulum bæta einn annar hlutur. 723 00:31:30,410 --> 00:31:34,710 Ég leggja til að ég þarf að halda utan um framan á listanum, sem er bara 724 00:31:34,710 --> 00:31:35,570 að fara að vera int eins vel. 725 00:31:35,570 --> 00:31:36,550 Og við erum að fara að halda það einfalt. 726 00:31:36,550 --> 00:31:37,740 Engin tengd lista fyrir nú. 727 00:31:37,740 --> 00:31:40,900 >> Við munum viðurkenna að við erum að fara að högg upp á móti þessum mörkum. 728 00:31:40,900 --> 00:31:43,720 En hvað ég vil sjá gerast í þetta sinn? 729 00:31:43,720 --> 00:31:47,240 Svo ætla ég að fara á undan og fyrsta maður kemur upp í línu, og 730 00:31:47,240 --> 00:31:48,560 það er númer 9. 731 00:31:48,560 --> 00:31:49,680 Við höfum streitu kúlur. 732 00:31:49,680 --> 00:31:51,330 Get ég stela, segja, tveir eða þrír gestir? 733 00:31:51,330 --> 00:31:52,690 Einn, tveir, þrír? 734 00:31:52,690 --> 00:31:53,120 Komdu upp. 735 00:31:53,120 --> 00:31:56,022 Réttur frá the andlit, því við munum gera þetta einn fljótur. 736 00:31:56,022 --> 00:31:59,415 >> Hver ykkar er nú að fara að vera aðdáandi drengur í samræmi við Apple. 737 00:31:59,415 --> 00:32:03,970 738 00:32:03,970 --> 00:32:06,210 Þú munt ekki vera að fá Apple vélbúnað í lok þessarar þó. 739 00:32:06,210 --> 00:32:06,500 Allt í lagi. 740 00:32:06,500 --> 00:32:09,430 Svo þú ert númer 9, þú ert númer 17, númer 22.. 741 00:32:09,430 --> 00:32:12,130 Þetta eru handahófskennt tölur, eins og nemandi auðkenni eða whatnot. 742 00:32:12,130 --> 00:32:14,550 Og á aðeins augnablik, við skulum byrja að byrja að bæta hlutina. 743 00:32:14,550 --> 00:32:16,000 Og ég keyrt stjórn hér í þetta sinn. 744 00:32:16,000 --> 00:32:19,570 >> Svo í þessu tilfelli, ég hef frumstilla framan til að vera - 745 00:32:19,570 --> 00:32:22,380 Ég reyndar ekki alveg sama hvað framan er, vegna þess að stærð er núll. 746 00:32:22,380 --> 00:32:24,480 Þannig að þetta gæti eins vel bara vera spurningarmerki. 747 00:32:24,480 --> 00:32:26,170 Þetta eru allt spurningarmerki. 748 00:32:26,170 --> 00:32:29,880 Svo nú munum við byrja að raunverulega sjá sumir fólk fóður upp í búð. 749 00:32:29,880 --> 00:32:33,320 >> Þannig að ef númer 9, þú ert sá fyrsti þar á 5:00, fara fram í tímann og stilla upp, 750 00:32:33,320 --> 00:32:34,210 eða kvöldið áður. 751 00:32:34,210 --> 00:32:34,580 OK. 752 00:32:34,580 --> 00:32:35,940 Svo er nú 9 hér. 753 00:32:35,940 --> 00:32:37,940 Svo 9 er í framan á listanum. 754 00:32:37,940 --> 00:32:41,440 Þannig að ég ætla að fara á undan og uppfæra Stærð þessa núverandi gögn 755 00:32:41,440 --> 00:32:44,740 uppbyggingu að ekki vera 0 lengur, en til að vera 1.. 756 00:32:44,740 --> 00:32:47,630 Ég ætla að setja 9 á á framan á listanum. 757 00:32:47,630 --> 00:32:51,020 Leyfðu mér að fara á undan og skipta skjánum svo við getum séð framhjá okkur hér. 758 00:32:51,020 --> 00:32:53,220 >> Og nú hvað ég vil að setja að framan? 759 00:32:53,220 --> 00:32:56,240 Ég ætla að halda utan um að framan biðröð núna 760 00:32:56,240 --> 00:32:58,570 er á stað 0. 761 00:32:58,570 --> 00:33:00,510 Vegna þess að það er næst að fara að gerast? 762 00:33:00,510 --> 00:33:03,000 Jæja, ætla nú ég e, 17 eins vel. 763 00:33:03,000 --> 00:33:04,510 Svo step í línu þar. 764 00:33:04,510 --> 00:33:07,060 Og aftur, eins konar dyr til verslun er að fara að vera hér. 765 00:33:07,060 --> 00:33:08,700 Svo nú hef ég bætt 17. 766 00:33:08,700 --> 00:33:10,810 Og jafnvel þó þessir krakkar eru að blokka skjánum, það er allt í lagi, 767 00:33:10,810 --> 00:33:12,300 vegna þess að við getum séð það allt hér. 768 00:33:12,300 --> 00:33:12,910 Því miður. 769 00:33:12,910 --> 00:33:13,810 >> Áhorfendur: Við getum fært - 770 00:33:13,810 --> 00:33:14,660 >> DAVID Malan: Nei, það er allt í lagi. 771 00:33:14,660 --> 00:33:16,000 Það er mikið þarna. 772 00:33:16,000 --> 00:33:18,580 Svo er 17 nú inni í biðröð. 773 00:33:18,580 --> 00:33:21,332 Ég þarf að uppfæra sem reitir nú þó? 774 00:33:21,332 --> 00:33:23,210 OK, örugglega stærð. 775 00:33:23,210 --> 00:33:26,430 Og hvernig óður í framan? 776 00:33:26,430 --> 00:33:27,040 OK, nei. 777 00:33:27,040 --> 00:33:30,200 Framan ætti ekki að breyta því ólíkt stafla, við 778 00:33:30,200 --> 00:33:31,370 vilja til að viðhalda sanngirni. 779 00:33:31,370 --> 00:33:35,150 Þannig að ef 9 kom fyrst, viljum við 9 til að vera fyrsta af línunni 780 00:33:35,150 --> 00:33:36,420 og inn í búðina. 781 00:33:36,420 --> 00:33:37,220 >> Í staðreynd, við skulum sjá það. 782 00:33:37,220 --> 00:33:42,235 Áður en við setja 22, við skulum fara á undan og dequeue 9. 783 00:33:42,235 --> 00:33:42,970 Hvað heitirðu aftur? 784 00:33:42,970 --> 00:33:43,680 >> Áhorfendur: Jake. 785 00:33:43,680 --> 00:33:45,440 >> DAVID Malan: Jake er að fara að dequeued núna. 786 00:33:45,440 --> 00:33:48,050 Þannig að þú færð að ganga inn í búðina. 787 00:33:48,050 --> 00:33:49,880 Og þykjast að geyma er þarna. 788 00:33:49,880 --> 00:33:51,970 Svo nú hvað þarf - dit-dit-dit! 789 00:33:51,970 --> 00:33:53,400 Hvað þarf að gerast núna? 790 00:33:53,400 --> 00:33:54,490 Hönnun ákvörðun. 791 00:33:54,490 --> 00:33:56,825 Svo ekki slæmur eðlishvöt, en - hvað er nafnið þitt aftur? 792 00:33:56,825 --> 00:33:57,090 >> Áhorfendur: David. 793 00:33:57,090 --> 00:33:57,500 >> DAVID Malan: David. 794 00:33:57,500 --> 00:33:58,810 Svo hvað gerði Davíð að gera? 795 00:33:58,810 --> 00:34:02,590 Hann var að reyna að raða á festa gögn uppbyggingu og færa frá staðsetningu hans 796 00:34:02,590 --> 00:34:04,100 í fyrrum stað Jake. 797 00:34:04,100 --> 00:34:06,740 Og það er allt í lagi ef við erum tilbúin að taka því sem að 798 00:34:06,740 --> 00:34:08,199 framkvæmd smáatriði. 799 00:34:08,199 --> 00:34:11,100 En fyrst skulum uppfæra gögn uppbyggingu áður en við gerum það. 800 00:34:11,100 --> 00:34:14,139 Því ég er ekki mætur hugmynd allra fólk breytast í þessari línu. 801 00:34:14,139 --> 00:34:17,360 >> Það er ekki máli ef Davíð gerir það með eitt skref, en aftur, hugsa til baka til 802 00:34:17,360 --> 00:34:20,360 þegar við höfum haft átta sjálfboðaliða á stigi og við höfum gert eins innsetningu 803 00:34:20,360 --> 00:34:22,600 tegund, þar sem við þurftum að byrja færa alla í kringum. 804 00:34:22,600 --> 00:34:23,790 Sem fékk dýr, ekki satt? 805 00:34:23,790 --> 00:34:28,330 Það gerir mig cringe um stór O af N, stór O af n veldi aftur. 806 00:34:28,330 --> 00:34:30,650 Það er ekki tilfinning eins tilvalið niðurstaða. 807 00:34:30,650 --> 00:34:32,080 >> Þannig að við skulum bara uppfæra þetta. 808 00:34:32,080 --> 00:34:35,120 Þannig að stærð biðröð er ekki lengur 2. 809 00:34:35,120 --> 00:34:37,090 Það er nú einfaldlega 1. 810 00:34:37,090 --> 00:34:40,360 En ég get nú uppfæra eitthvað Ég vissi ekki að uppfæra fyrr 811 00:34:40,360 --> 00:34:41,130 framan á listanum. 812 00:34:41,130 --> 00:34:45,420 Ég gæti bara sagt, er þessi staðsetning 1? 813 00:34:45,420 --> 00:34:49,770 Svo nú höfum við sorp gildi hér, sorp gildi hér, og Davíð í 814 00:34:49,770 --> 00:34:51,469 miðja rusli. 815 00:34:51,469 --> 00:34:54,980 En gögn uppbygging er enn óbreytt. 816 00:34:54,980 --> 00:34:58,540 >> Og í raun, ég er ekki einu sinni að breyta fyrrum númer Jake 817 00:34:58,540 --> 00:35:00,460 9, því hver blíðuhót. 818 00:35:00,460 --> 00:35:04,470 Ég hef nægar upplýsingar nú í stærð sem ég veit að það er einn maður í 819 00:35:04,470 --> 00:35:05,030 þetta biðröð. 820 00:35:05,030 --> 00:35:08,340 Og ég veit að þessi manneskja er á staðsetningu 1, ekki 0. 821 00:35:08,340 --> 00:35:09,760 Ég ætla ekki að telja. 822 00:35:09,760 --> 00:35:11,300 Sem 1 eins vel. 823 00:35:11,300 --> 00:35:13,410 Svo er gögn uppbygging enn OK. 824 00:35:13,410 --> 00:35:14,330 >> Jæja, hvað gerist næst? 825 00:35:14,330 --> 00:35:15,010 Skulum e, - 826 00:35:15,010 --> 00:35:15,370 hvað er nafn þitt? 827 00:35:15,370 --> 00:35:16,160 >> Áhorfendur: Callen. 828 00:35:16,160 --> 00:35:16,580 >> DAVID Malan: Callen. 829 00:35:16,580 --> 00:35:20,770 Skulum e, a Callen, og 22 er nú í biðröð. 830 00:35:20,770 --> 00:35:22,300 Svo nú er það að breytast hér? 831 00:35:22,300 --> 00:35:24,380 Framan er ekki að fara að breyta, vitanlega. 832 00:35:24,380 --> 00:35:27,160 Stærð er að fara að breyta til að vera 2 aftur. 833 00:35:27,160 --> 00:35:31,590 Og 22 endar hér, 9 er enn til staðar, en það er í raun að 834 00:35:31,590 --> 00:35:32,600 sorp gildi núna. 835 00:35:32,600 --> 00:35:35,910 Það er bara leifar af Jake fortíð. 836 00:35:35,910 --> 00:35:39,200 >> Svo nú hvað gerist ef Ég dequeue Davíð? 837 00:35:39,200 --> 00:35:41,560 Einn síðastur aðgerð, dequeue David. 838 00:35:41,560 --> 00:35:46,070 Við gætum skipta, en ég leggja skulum gera eins litla vinnu og mögulegt er. 839 00:35:46,070 --> 00:35:50,280 Nú fer gögn uppbygging minn aftur í stærð 2-1. 840 00:35:50,280 --> 00:35:53,730 En framan biðröð nú verður 2.. 841 00:35:53,730 --> 00:35:56,640 Ég þarf ekki að breyta þessum númerum bara enn, því þeir eru 842 00:35:56,640 --> 00:35:58,230 bara sorp gildi. 843 00:35:58,230 --> 00:35:59,720 >> En nú gerist það? 844 00:35:59,720 --> 00:36:03,280 Býst ég e, mig, 26? 845 00:36:03,280 --> 00:36:05,890 Mér finnst eins og ég tilheyri hérna. 846 00:36:05,890 --> 00:36:06,890 Þannig að ég hef verið enqueued. 847 00:36:06,890 --> 00:36:08,760 Svo ég tilheyri konar hér. 848 00:36:08,760 --> 00:36:11,300 Og jafnvel þó að þú ert ekki alveg þakka þetta sjónrænt á sviðinu, 849 00:36:11,300 --> 00:36:15,075 vegna þess að við höfum nóg pláss, ætti ég ekki að standa hér, hvers vegna? 850 00:36:15,075 --> 00:36:16,290 >> Áhorfendur: Þú ert út af mörk. 851 00:36:16,290 --> 00:36:16,370 >> DAVID Malan: Hægri. 852 00:36:16,370 --> 00:36:16,940 Ég er út af mörk. 853 00:36:16,940 --> 00:36:19,330 Ég hef verðtryggð utan mörk af þessu fylki. 854 00:36:19,330 --> 00:36:23,420 I raun ætti að vera í einu af þrjár mögulegar staðsetningar. 855 00:36:23,420 --> 00:36:25,150 Nú, hvar er eðlilegast að fara? 856 00:36:25,150 --> 00:36:27,760 Ég leggja til við skuldsett í viku eitt bragð. 857 00:36:27,760 --> 00:36:30,150 Unga fólkið rekstraraðila, hlutfall. 858 00:36:30,150 --> 00:36:36,850 Því ég er tæknilega standa á Staðsetning 3, en ég 3 unga fólkið getu, 859 00:36:36,850 --> 00:36:40,250 svo 3, sem er prósentumerkið, 3 - 860 00:36:40,250 --> 00:36:40,970 getu er 3. 861 00:36:40,970 --> 00:36:41,720 Hvað er það? 862 00:36:41,720 --> 00:36:43,700 Hvað er afgangurinn þegar þú skiptir 3 um 3? 863 00:36:43,700 --> 00:36:44,070 0. 864 00:36:44,070 --> 00:36:48,140 >> Svo sem setur mig voru Jake var, sem er í raun gott. 865 00:36:48,140 --> 00:36:50,370 Svo nú framkvæmd þetta hlutur er að fara að 866 00:36:50,370 --> 00:36:51,250 vera hluti af höfuðverk. 867 00:36:51,250 --> 00:36:53,740 Það er í raun bara ein lína höfuðverkur, af kóða. 868 00:36:53,740 --> 00:36:56,580 En að minnsta kosti nú er það sorp gildi hér, en það er tveir 869 00:36:56,580 --> 00:36:57,910 lögmæt ints hér. 870 00:36:57,910 --> 00:37:04,160 Og ég halda því fram að nú höfum við gert nákvæmlega það sem við þurfum að gera svo lengi sem 871 00:37:04,160 --> 00:37:08,600 við að breyta því sem er Jake gildi var að vera 26.. 872 00:37:08,600 --> 00:37:12,110 >> Við höfum nú nægar upplýsingar ennþá að viðhalda heilleika 873 00:37:12,110 --> 00:37:13,060 af þessum gögnum uppbyggingu. 874 00:37:13,060 --> 00:37:17,160 Við erum enn eins konar út af heppni þegar við langar að setja fjögur eða fleiri samtals 875 00:37:17,160 --> 00:37:20,740 þættir, en ég get að minnsta kosti að gera nokkuð skilvirka notkun þessa föstu 876 00:37:20,740 --> 00:37:21,740 tíma, í raun. 877 00:37:21,740 --> 00:37:27,150 Ég þarf ekki að hafa áhyggjur af að breytast allir, sem halla Davíðs var. 878 00:37:27,150 --> 00:37:30,816 >> Einhverjar spurningar um stafla, eða þetta biðröð? 879 00:37:30,816 --> 00:37:32,184 >> Áhorfendur: Er ástæðan þú þarft stærð svo þú veist 880 00:37:32,184 --> 00:37:34,010 þar sem að hafa mann? 881 00:37:34,010 --> 00:37:34,770 >> DAVID Malan: Einmitt. 882 00:37:34,770 --> 00:37:38,230 Ég þarf að vita stærð fylkisins vegna þess að ég þarf að vita nákvæmlega hvernig 883 00:37:38,230 --> 00:37:41,940 margir af þessum gildum er lögmætur, og svo að ég geti fundið hvar á að setja 884 00:37:41,940 --> 00:37:42,800 á næsta mann. 885 00:37:42,800 --> 00:37:43,300 Einmitt. 886 00:37:43,300 --> 00:37:44,580 Stærð er - 887 00:37:44,580 --> 00:37:46,360 Reyndar höfum vér ekki að uppfæra þetta enn. 888 00:37:46,360 --> 00:37:48,380 Ég bætti mig í 26. 889 00:37:48,380 --> 00:37:51,760 The stærð er nú, ekki 1, en 2. 890 00:37:51,760 --> 00:37:57,780 Svo nú hjálpar þetta örugglega mér að finna höfuð á listanum, sem er ekki 0, ekki 891 00:37:57,780 --> 00:37:59,250 1, en er 2. 892 00:37:59,250 --> 00:38:01,665 Framan af listanum er örugglega númer 22.. 893 00:38:01,665 --> 00:38:05,120 Vegna þess að hann kom í fyrsta, svo hann ætti að fá í búðina fyrir mig, 894 00:38:05,120 --> 00:38:08,780 jafnvel þó sjónrænt ég stend nær út í búð. 895 00:38:08,780 --> 00:38:09,220 >> Allt í lagi? 896 00:38:09,220 --> 00:38:12,410 A umferð af lófaklapp fyrir þessar krakkar og við munum láta þá út þaðan. 897 00:38:12,410 --> 00:38:17,090 >> [Applause] 898 00:38:17,090 --> 00:38:18,150 >> DAVID Malan: ég gæti látið þú halda bakkanum. 899 00:38:18,150 --> 00:38:20,760 Við gátum séð hvað gerist ef þú vilt, en kannski ekki. 900 00:38:20,760 --> 00:38:21,590 Allt í lagi. 901 00:38:21,590 --> 00:38:25,380 Svo hvað nú er að yfirgefa okkur? 902 00:38:25,380 --> 00:38:28,900 Jæja, láttu mig leggja til að það er Nokkur önnur mannvirki gögn við gátum 903 00:38:28,900 --> 00:38:33,810 byrja að bæta við verkfærasett okkar sem raun vera alveg, alveg eins viðeigandi og 904 00:38:33,810 --> 00:38:35,270 við kafa inn í vefsíðu efni. 905 00:38:35,270 --> 00:38:38,150 Sem aftur hefur einhvers konar tengslum til tre i formi 906 00:38:38,150 --> 00:38:40,550 eitthvað sem kallast DOM, skjal mótmæla líkan. 907 00:38:40,550 --> 00:38:42,370 En við munum sjá meira af að áður en langur. 908 00:38:42,370 --> 00:38:46,260 >> Leyfðu mér að leggja skilgreiningar sem við kalla tré nú hvað þú might vita sem 909 00:38:46,260 --> 00:38:48,820 meira af fjölskyldu tré, þar sem þú hafa sumir forfaðir á the 910 00:38:48,820 --> 00:38:49,790 rætr trésins. 911 00:38:49,790 --> 00:38:54,480 A rutt eða matriarch á the mjög toppur af trénu. 912 00:38:54,480 --> 00:38:56,700 Án maka þeirra, í þessu tilfelli. 913 00:38:56,700 --> 00:39:00,940 En við höfum nú það sem við munum kalla Börn, sem eru hnútar sem hanga 914 00:39:00,940 --> 00:39:05,480 burt vinstri barn eða hægri barn, Örvarnar sem lýst hér. 915 00:39:05,480 --> 00:39:10,490 >> Með öðrum orðum, í gögn tré uppbyggingu í tölvunni, tré hefur núll 916 00:39:10,490 --> 00:39:11,480 eða fleiri hnútar. 917 00:39:11,480 --> 00:39:13,500 Ef það hefur að minnsta kosti einn tengipunktur sem er kallað rót. 918 00:39:13,500 --> 00:39:15,700 Það er það sjónrænt sem við drögum efst. 919 00:39:15,700 --> 00:39:20,280 Og það hnút, eins og allir aðrir hnút, getur hafa núll, einn, eða tveir, eða þrír, 920 00:39:20,280 --> 00:39:23,600 eða hvernig sem mörg börn sem gögn uppbygging styður. 921 00:39:23,600 --> 00:39:29,150 Í þessu tilfelli er rót, geyma gildi einu, á tvö börn, 2 og 3, 922 00:39:29,150 --> 00:39:33,020 svo við köllum yfirleitt 2 á vinstri barn og 3 hægri barn. 923 00:39:33,020 --> 00:39:36,940 >> Og svo þegar við komum niður í 5, 6, og 7, 6 mætti ​​kalla miðju barnið. 924 00:39:36,940 --> 00:39:38,940 Ef þú hefur fjögur börn, það fær ruglingslegt. 925 00:39:38,940 --> 00:39:42,260 Þannig að við hætta að nota svona á flýtileið munnlega. 926 00:39:42,260 --> 00:39:44,580 En það er í raun bara fjölskyldu tré. 927 00:39:44,580 --> 00:39:48,880 Og blöðin hér eru hnútar sem sjálfir hafa engin börn. 928 00:39:48,880 --> 00:39:52,540 Þeir hanga á the botn af trénu. 929 00:39:52,540 --> 00:39:56,940 >> Svo hvernig gæti við innleiða tré sem hefur bara tvö börn hámarks? 930 00:39:56,940 --> 00:39:58,410 Við munum kalla það tvöfaldur tré. 931 00:39:58,410 --> 00:40:00,960 Bi þýðir aftur tvær, í þessu ræða, eins og tvöfaldur. 932 00:40:00,960 --> 00:40:04,830 Og svo það getur haft núll, einn, eða tvö börn hámarks. 933 00:40:04,830 --> 00:40:08,650 >> Ég leggja til að við framkvæmd hnút fyrir að uppbygging með int n, 934 00:40:08,650 --> 00:40:11,910 og þá tveir ábendingum, kallaði einn vinstri, kallaði einn rétt. 935 00:40:11,910 --> 00:40:14,830 En þeir eru bara nice handahófskennt samninga. 936 00:40:14,830 --> 00:40:18,170 Og hvað er gott núna, sérstaklega ef þú konar barátta eðli með 937 00:40:18,170 --> 00:40:21,300 endurkvæmni, eða hélt að það væri ekki raunverulega lausn á neinu, 938 00:40:21,300 --> 00:40:23,120 sérstaklega ef þú gætir hlaupa út af minni. 939 00:40:23,120 --> 00:40:26,600 Nú þegar við erum að tala um gögn mannvirki og reiknirit sem leyfa 940 00:40:26,600 --> 00:40:31,030 okkur að fara og vinna þá, kemur í ljós að endurkvæmni kemur aftur í 941 00:40:31,030 --> 00:40:34,240 miklu meira sannfærandi ef ekki falleg leið. 942 00:40:34,240 --> 00:40:38,670 >> Þannig að þetta sem ég leggja er framkvæmd á leit virka. 943 00:40:38,670 --> 00:40:39,870 Gefið tvær inntak - 944 00:40:39,870 --> 00:40:41,570 svo hugsa um þetta sem svartur kassi. 945 00:40:41,570 --> 00:40:46,560 Gefið tvær inntak, N, int, og bendi á tré, bendi til að 946 00:40:46,560 --> 00:40:50,020 hnút, eða í raun rót á tré, ég halda því fram að þessi aðgerð getur skilað 947 00:40:50,020 --> 00:40:53,530 satt eða ósatt, sem gildi n er inni í þessu tré. 948 00:40:53,530 --> 00:40:55,210 >> Hvað er inni í þessum svarta kassa? 949 00:40:55,210 --> 00:40:57,440 Jæja, fjórar deildir. 950 00:40:57,440 --> 00:40:58,385 Fyrsta bara tékka. 951 00:40:58,385 --> 00:41:00,490 Ef tré er null, bara return false. 952 00:41:00,490 --> 00:41:04,580 Ef það er engin hnút, það er engin n, það er ekkert númer skaltu bara aftur ósatt. 953 00:41:04,580 --> 00:41:12,330 Ef þó n, gildi sem þú ert að leita fyrir, er minna en tree arrow n, og 954 00:41:12,330 --> 00:41:15,180 bara til að vera skýr, hvað þýðir það þegar Ég skrifa tré og síðan á örina 955 00:41:15,180 --> 00:41:18,150 merki, n? 956 00:41:18,150 --> 00:41:18,690 Einmitt. 957 00:41:18,690 --> 00:41:21,970 Það þýðir dereference að bendillinn heitir tré. 958 00:41:21,970 --> 00:41:26,750 Fara þangað, og þá fá inni í því hnút og fá sínu sviði kallast n. 959 00:41:26,750 --> 00:41:30,810 Og þá bera saman raunverulegan n sem var lentu í Leita gegn henni. 960 00:41:30,810 --> 00:41:35,390 >> Þannig að ef n er minna en, í n value í tré Hnútur sig vel, 961 00:41:35,390 --> 00:41:36,720 hvað þýðir það? 962 00:41:36,720 --> 00:41:40,690 Það þýðir ekkert við fyrstu sýn. 963 00:41:40,690 --> 00:41:40,900 Ekki satt? 964 00:41:40,900 --> 00:41:45,560 Bara eins og þegar þú ert með fjölbreytta gildi, þú might eins og til að sækja tvöfaldur 965 00:41:45,560 --> 00:41:48,290 leita eins og a mynd af skipta og sigra. 966 00:41:48,290 --> 00:41:51,790 En hvað forsendu höfum vér þurfum að gera Fyrir tvöfaldur leita að vinna á öllum 967 00:41:51,790 --> 00:41:54,510 í símaskránni og fyrri dæmi? 968 00:41:54,510 --> 00:41:55,530 >> Hvernig á að vera flokkaður. 969 00:41:55,530 --> 00:41:59,490 Svo skulum betrumbæta skilgreiningu tré hér ekki að vera bara tré, sem getur 970 00:41:59,490 --> 00:42:00,880 hafa allir tala um börn. 971 00:42:00,880 --> 00:42:04,700 Ekki bara tvöfaldur tré, sem getur have 0, 1, eða 2 hámarks. 972 00:42:04,700 --> 00:42:09,700 En eins og a tvöfaldur leita tré eða BST, sem er bara fínt leið til að segja að 973 00:42:09,700 --> 00:42:15,430 tvöfaldur tré svo að sérhver hnútur er vinstri barn, ef til staðar, er 974 00:42:15,430 --> 00:42:16,830 minna en í hnút. 975 00:42:16,830 --> 00:42:20,170 Og hægri hverjum hnút er barn, ef til staðar, er meiri 976 00:42:20,170 --> 00:42:21,740 en hnút sjálft. 977 00:42:21,740 --> 00:42:25,200 >> Svo í öðrum orðum, ef þú varst að teikna tré út, eru allar tölur 978 00:42:25,200 --> 00:42:30,620 vandlega jafnvægi svona þannig að ef þú hefur 55 sem rót, 33 getur farið 979 00:42:30,620 --> 00:42:33,090 til vinstri þar sem hún er minna en 55. 980 00:42:33,090 --> 00:42:36,430 77 getur farið til hægri þess vegna það er meiri en 55. 981 00:42:36,430 --> 00:42:40,750 En nú taka, sama skýring, það er endurkvæma skilgreiningu munnlega, 982 00:42:40,750 --> 00:42:42,600 þarf að sækja um 33. 983 00:42:42,600 --> 00:42:47,610 Vinstri barn 33 verður að vera minna en það, og hægri barn 33 er, 44, verður að vera 984 00:42:47,610 --> 00:42:48,580 stærri en það. 985 00:42:48,580 --> 00:42:51,670 >> Þannig að þetta er tvöfaldur leita tré, og Ég leggja til, með smá 986 00:42:51,670 --> 00:42:53,910 endurkvæmni, getum við nú fundið n. 987 00:42:53,910 --> 00:42:59,160 Þannig að ef n er minna en gildið n sem er núverandi hnút, ég ætla að fara 988 00:42:59,160 --> 00:43:04,090 undan og Punt, svo að segja, og bara aftur hvað svarið er 989 00:43:04,090 --> 00:43:08,470 leita n á vinstri glugganum er barn. 990 00:43:08,470 --> 00:43:11,370 Tilkynning aftur, þessi aðgerð bara væntir hnút Star, 991 00:43:11,370 --> 00:43:12,780 bendi á hnút. 992 00:43:12,780 --> 00:43:17,360 Svo örugglega ég get bara gert tré arrow vinstri, sem mun leiða 993 00:43:17,360 --> 00:43:18,400 mér annan hnút. 994 00:43:18,400 --> 00:43:19,480 En hvað er að hnútur? 995 00:43:19,480 --> 00:43:22,820 >> Jæja, samkvæmt þessari yfirlýsingu, vinstri er bara músina, þannig að bara 996 00:43:22,820 --> 00:43:27,090 þýðir að ég er liggur við leit virka annað músina, þ.e. 997 00:43:27,090 --> 00:43:30,750 sá sem stendur Vinstri barnsins míns tré. 998 00:43:30,750 --> 00:43:36,040 Þannig að í þessu tilfelli, the músina til 33, ef þetta er dæmi um inntak okkar sama tíma, ef 999 00:43:36,040 --> 00:43:40,740 n er meiri en gildi n AT THE núverandi hnút í trénu, þá er ég 1000 00:43:40,740 --> 00:43:43,370 að fara á undan og Punt í öðrum stefnu og bara segja, ég er ekki 1001 00:43:43,370 --> 00:43:47,280 vita ef þetta gildi n er í trénu, en ég veit ef það er, er það niður mín 1002 00:43:47,280 --> 00:43:49,090 rétt grein, svo að segja. 1003 00:43:49,090 --> 00:43:53,120 Svo láta mig símtali leita endurkvæmt, standast n aftur, en farið í 1004 00:43:53,120 --> 00:43:54,580 bendillinn hægra barnið mitt. 1005 00:43:54,580 --> 00:44:00,020 >> Með öðrum orðum, ef ég er nú á 55 og ég er að leita að 99, ég veit að 99 1006 00:44:00,020 --> 00:44:04,270 er meiri en 55, þannig að alveg eins og ég rifu Símaskrárstillingar vikum og við 1007 00:44:04,270 --> 00:44:07,140 fór rétt, eru álíka við að fara hérna. 1008 00:44:07,140 --> 00:44:11,960 Og ég veit ekki hvort það er á hægri hönd barn, og það er ekki, 77 er þar, en 1009 00:44:11,960 --> 00:44:13,210 Ég veit að það er í þessa átt. 1010 00:44:13,210 --> 00:44:18,770 Svo ég kalla leit á hægri barnið mitt, 77, og láta leita reikna út frá 1011 00:44:18,770 --> 00:44:24,950 þar ef 99 í þessu handahófskennt dæmi er í raun þar. 1012 00:44:24,950 --> 00:44:26,900 >> Annars, hvað er það sem kemur síðas málið? 1013 00:44:26,900 --> 00:44:28,620 Ef tré er null er eitt mál. 1014 00:44:28,620 --> 00:44:31,890 Ef n er minna en núverandi hnút er gildi er annað mál. 1015 00:44:31,890 --> 00:44:35,120 Ef n er stærra en núverandi gildi Hnútur er þriðja mál. 1016 00:44:35,120 --> 00:44:38,250 Hvað er fjórða og síðasta málið? 1017 00:44:38,250 --> 00:44:39,480 Ég held að við séum út af málum, ekki satt? 1018 00:44:39,480 --> 00:44:44,690 Það verður að vera að n sé á núverandi hnút sem ég er á. 1019 00:44:44,690 --> 00:44:49,640 >> Þannig að ef ég er að leita að 55 á þessum tímapunkti í sögunni, að útibú á 1020 00:44:49,640 --> 00:44:51,780 tré myndi skila satt. 1021 00:44:51,780 --> 00:44:55,380 Svo er það sem er áhugavert hér að við reyndar, ólíkt vikum áður, góður við 1022 00:44:55,380 --> 00:44:56,740 af hafa tvö grunn tilvikum. 1023 00:44:56,740 --> 00:44:58,300 Og þeir þurfa ekki að vera allt að ofan. 1024 00:44:58,300 --> 00:45:01,390 Efsta er undirstaða tilfelli vegna þess að ef Tréð er null, það er ekkert að gera. 1025 00:45:01,390 --> 00:45:03,410 Bara aftur a harður dulmáli Verðmæti rangar. 1026 00:45:03,410 --> 00:45:07,400 >> The botn útibú er tegund af sjálfgefið, þar ef við höfum athugað fyrir 1027 00:45:07,400 --> 00:45:11,550 null, höfum við kannað hvort það ætti að vera vinstri, en það ætti ekki að vera, við höfum 1028 00:45:11,550 --> 00:45:14,640 hakað ef það ætti að vera rétt, en það ætti ekki að vera, greinilega hefur það að vera 1029 00:45:14,640 --> 00:45:15,870 rétt þar sem við erum. 1030 00:45:15,870 --> 00:45:16,780 Það er grunn tilfelli. 1031 00:45:16,780 --> 00:45:19,920 Svo er það tvö endurkvæma tilvikum samloka þarna í miðjunni. 1032 00:45:19,920 --> 00:45:21,630 En ég gæti hafa skrifað þetta í hvaða röð sem er. 1033 00:45:21,630 --> 00:45:24,520 Ég hélt bara að það var svona eðlilegt fyrst að athuga fyrir hugsanleg mistök, 1034 00:45:24,520 --> 00:45:28,340 þá stöðva vinstri, þá stöðva rétt, þá gera ráð fyrir að þú ert í hnút 1035 00:45:28,340 --> 00:45:30,630 þú ert í raun að leita að. 1036 00:45:30,630 --> 00:45:36,240 >> Svo hvers vegna gæti þetta verið gagnlegt? 1037 00:45:36,240 --> 00:45:37,910 Svo kemur í ljós - 1038 00:45:37,910 --> 00:45:42,110 og láta mig hoppa til beitu hér er það á vefnum. 1039 00:45:42,110 --> 00:45:44,920 Við erum að fara að byrja að nota ekki Forritunarmál í fyrstu, en 1040 00:45:44,920 --> 00:45:46,030 Markup Language. 1041 00:45:46,030 --> 00:45:48,740 A Markup Language vera einn sem er svipuð í anda að forritun 1042 00:45:48,740 --> 00:45:51,715 tungumál, en það þýðir ekki að gefa þér hæfni til að tjá þig rökrétt. 1043 00:45:51,715 --> 00:45:55,070 Það gefur aðeins þér möguleika á að tjá þig byggingu. 1044 00:45:55,070 --> 00:45:57,960 >> Hvar viltu setja eitthvað á síðunni, heimasíðu? 1045 00:45:57,960 --> 00:45:59,200 Hvaða litur viltu gera það? 1046 00:45:59,200 --> 00:46:00,950 Hvaða leturstærð viltu gera það? 1047 00:46:00,950 --> 00:46:02,970 Orð hvað gerir þú í raun vilt á vefsíðu? 1048 00:46:02,970 --> 00:46:04,060 Svo er að Markup Language. 1049 00:46:04,060 --> 00:46:07,690 En þá munum við mjög fljótlega kynna JavaScript, sem er a fullur-viðvaningur 1050 00:46:07,690 --> 00:46:08,560 forritunarmál. 1051 00:46:08,560 --> 00:46:12,530 Mjög svipuð setningafræðilega í útliti til C, en það mun hafa sumir 1052 00:46:12,530 --> 00:46:15,200 nice, öflugri, meira notandi vingjarnlegur lögun. 1053 00:46:15,200 --> 00:46:18,050 >> Og einn af óánægju í þessu benda á önn er að við munum 1054 00:46:18,050 --> 00:46:22,065 fljótt innleiða Speller í mun færri línur af kóða með önnur tungumál 1055 00:46:22,065 --> 00:46:25,580 en C sjálft gerir, en er ástæða við munum brátt skilja. 1056 00:46:25,580 --> 00:46:27,750 Þetta verður fyrsta vefsíðan. 1057 00:46:27,750 --> 00:46:30,120 Það verður alveg underwhelming, sá fyrsti sem við tökum. 1058 00:46:30,120 --> 00:46:31,400 Það verður einfaldlega að segja halló heimur. 1059 00:46:31,400 --> 00:46:34,010 En ef þú hefur aldrei séð það áður, þetta er HTML, 1060 00:46:34,010 --> 00:46:35,670 HyperText Markup Language. 1061 00:46:35,670 --> 00:46:39,310 >> Ef þú ferð að ákveðnu matseðill valkostur í flest allir flettitæki, á hvaða vefsíðu á 1062 00:46:39,310 --> 00:46:43,160 internetið getur þú séð HTML að sumir skrifaði 1063 00:46:43,160 --> 00:46:44,400 Búa þessi vefur blaðsíða. 1064 00:46:44,400 --> 00:46:47,850 Og það sennilega ekki líta út eins og stutt eða eins snyrtilegur og þetta. 1065 00:46:47,850 --> 00:46:51,400 En það mun fylgja mynstri þessara opna sviga og rista og 1066 00:46:51,400 --> 00:46:53,660 bókstafir og hugsanlega númer. 1067 00:46:53,660 --> 00:46:56,770 >> Ég hélt ég myndi gefa þér beitu af því sem þú munt vera fær um að gera 1068 00:46:56,770 --> 00:46:57,950 eftir að taka CS50. 1069 00:46:57,950 --> 00:47:02,620 Leyfðu mér að fara til cs.harvard.edu / ræna, Heimasíðan eigin Rob Bowden okkar. 1070 00:47:02,620 --> 00:47:06,080 Hann gerði þetta fyrir okkur. 1071 00:47:06,080 --> 00:47:07,490 Svo þú munt bráðum vera fær til gera þessi. 1072 00:47:07,490 --> 00:47:10,660 Og einnig, hvað þú heyrt í morgun - 1073 00:47:10,660 --> 00:47:12,480 hvað þú heyrt í morgun - 1074 00:47:12,480 --> 00:47:13,780 >> [Hömstrum DANCE MUSIC] 1075 00:47:13,780 --> 00:47:15,702 >> - You'Ll vera fær um að gera þetta. 1076 00:47:15,702 --> 00:47:16,790 Það bíður okkar á miðvikudag. 1077 00:47:16,790 --> 00:47:17,791 Við munum sjá þig þá. 1078 00:47:17,791 --> 00:47:22,950 >> [Hömstrum DANCE MUSIC] 1079 00:47:22,950 --> 00:47:24,300 DAVID Malan: Á næsta CS50 - 1080 00:47:24,300 --> 00:47:31,670