1 00:00:00,000 --> 00:00:11,460 2 00:00:11,460 --> 00:00:12,250 >> DAVID Malan: Olgu. 3 00:00:12,250 --> 00:00:13,860 Tere tulemast tagasi CS50. 4 00:00:13,860 --> 00:00:16,190 See on algus 8. nädalal. 5 00:00:16,190 --> 00:00:21,320 Ja meenutada, et probleem set 5 lõppes koos natuke väljakutse. 6 00:00:21,320 --> 00:00:25,210 Seega eeldades, et sa tagasi kõik oma õpetamise stipendiaatide ja KA fotod 7 00:00:25,210 --> 00:00:30,480 aastal card.raw fail, teil on õigus et nüüd kõik need inimesed, ja 8 00:00:30,480 --> 00:00:34,510 üks õnnelik võitja kõnnime koju ühe need asjad, hüpe motion 9 00:00:34,510 --> 00:00:37,450 seade, mida saab kasutada lõpliku projekte, näiteks. 10 00:00:37,450 --> 00:00:39,860 >> Seda igal aastal viib natuke tontlikkus. 11 00:00:39,860 --> 00:00:43,480 Ja nii ma mõtlesin, et ma teha, on jagada teiega mõned märkused, mis on 12 00:00:43,480 --> 00:00:47,370 läinud edasi ja tagasi üle töötajate nimekirja lõpus. 13 00:00:47,370 --> 00:00:51,110 Näiteks just eelmisel õhtul, tsiteerin lõppeb, ühest töötajate 14 00:00:51,110 --> 00:00:55,000 kohal, "Mul oli just üliõpilane knock mu uksele pildistama minuga. 15 00:00:55,000 --> 00:00:59,020 Varitsejad, ma ütlen teile. "Alustasin üsna kirjeldav ja siis kolisime 16 00:00:59,020 --> 00:01:02,830 edasi, tund aega hiljem, "Mul oli üliõpilane ootab mind pärast jagu 17 00:01:02,830 --> 00:01:06,080 ja ta oli kõik meie nimed ja fotod mõned paberilehed. "Olgu. 18 00:01:06,080 --> 00:01:09,230 Nii organiseeritud, kuid mitte kõik, et jube veel. 19 00:01:09,230 --> 00:01:12,520 >> Siis: "Ma olin linnast välja sel nädalavahetusel, ja kui ma sain tagasi, seal oli üks 20 00:01:12,520 --> 00:01:12,630 minu 21 00:01:12,630 --> 00:01:16,740 magamistoas. "[naer] 22 00:01:16,740 --> 00:01:20,410 DAVID Malan: Järgmine tsitaat personal liige, "õpilane tuli minu maja 23 00:01:20,410 --> 00:01:25,330 Somerville kell 4:00 hommikul. "Next personal "Sain oma hotell San 24 00:01:25,330 --> 00:01:30,016 Francisco ja õpilane ootas mind fuajees kolm DSLRs. " 25 00:01:30,016 --> 00:01:31,510 Tüüpi kaamera. 26 00:01:31,510 --> 00:01:34,980 "Ma ei ole isegi töötajate see semester, kuid õpilane murdis mu majja see 27 00:01:34,980 --> 00:01:40,480 hommikul ja registreeritakse kogu asi Google klaas. "Ja siis lõpuks, 28 00:01:40,480 --> 00:01:43,650 "Vähemalt 12 inimest olid innukalt ootavad mind, kui ma välja sain 29 00:01:43,650 --> 00:01:44,800 limusiin, ja siis ma 30 00:01:44,800 --> 00:01:46,970 ärkasin. "Olgu. 31 00:01:46,970 --> 00:01:57,690 Nii hulgas fotod, kuna te mäletan, on see mehe siin, kes te 32 00:01:57,690 --> 00:02:01,850 tunneksite kui Milo Banana, kes elab Lauren Carvalho, meie peas 33 00:02:01,850 --> 00:02:02,905 õpetamine Fellow. 34 00:02:02,905 --> 00:02:05,170 Milo, Milo, tule siia poiss. 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 you, ta kannab Google Klaas, nii näitame teile, see kõik pärast. 38 00:02:12,230 --> 00:02:16,190 Nii et see on Milo kui soovite pildistada koos temaga hiljem. 39 00:02:16,190 --> 00:02:18,240 Kui soovite, et vaadata läbi kell publik olemas. 40 00:02:18,240 --> 00:02:19,430 OK. 41 00:02:19,430 --> 00:02:20,200 See on hea materjali. 42 00:02:20,200 --> 00:02:22,556 Noh, Milo Banana. 43 00:02:22,556 --> 00:02:23,941 Oh, ära tee seda. 44 00:02:23,941 --> 00:02:29,020 >> [Naer] 45 00:02:29,020 --> 00:02:29,470 >> OK. 46 00:02:29,470 --> 00:02:34,550 Nii sõna siis mis ootab, sest kui me hakkame üleminekust 47 00:02:34,550 --> 00:02:38,410 Sel nädalal konkreetsemalt alates C käsurea keskkond PHP ja 48 00:02:38,410 --> 00:02:42,720 JavaScript ja SQL ja HTML ja CSS veebipõhine keskkond, me oleme 49 00:02:42,720 --> 00:02:44,490 varustada teile kõik rohkem teadmisi 50 00:02:44,490 --> 00:02:46,010 võimalikke lõplikke projekte. 51 00:02:46,010 --> 00:02:49,240 Toward Selleks on muidugi traditsioon seminaride mis 52 00:02:49,240 --> 00:02:50,950 olete tangentsiaalne teemasid et muidugi. 53 00:02:50,950 --> 00:02:54,330 Väga palju on seotud programmitöö ja app areng ja nii edasi, kuid 54 00:02:54,330 --> 00:02:57,010 pruugi uurivad Loomulikult enda õppekava. 55 00:02:57,010 --> 00:03:00,250 >> Nii et kui sa võiksid olla huvitatud ühe või rohkem käesoleva aasta seminaride 56 00:03:00,250 --> 00:03:02,530 registreerida cs50.net/seminar. 57 00:03:02,530 --> 00:03:06,170 On vanemad seminarid kell cs50.net/seminars. 58 00:03:06,170 --> 00:03:10,620 Ja nimekirja seni sel aastal on hämmastav Web Apps Ruby on 59 00:03:10,620 --> 00:03:13,580 Rööpad, mis on alternatiiviks keele PHP. 60 00:03:13,580 --> 00:03:14,900 Computational Linguistics. 61 00:03:14,900 --> 00:03:18,710 Sissejuhatus iOS, mis on platvorm, mida kasutatakse iPhone ja 62 00:03:18,710 --> 00:03:19,850 iPad arengut. 63 00:03:19,850 --> 00:03:22,890 JavaScript Web Apps, me katame , kuid selles seminar, lähete 64 00:03:22,890 --> 00:03:24,070 üksikasjalikumalt. 65 00:03:24,070 --> 00:03:27,390 >> Hüpe Motion, nii et me tegelikult mõned Meie sõbrad hüpe Motion, 66 00:03:27,390 --> 00:03:29,160 ettevõte ise, meiega liituda. 67 00:03:29,160 --> 00:03:31,800 Homme, tegelikult anda käed-seminar, kui 68 00:03:31,800 --> 00:03:33,320 Teile huvi pakkuda. 69 00:03:33,320 --> 00:03:38,770 Meteor.js, alternatiivse tehnika kasutades JavaScript ei ole brauser, 70 00:03:38,770 --> 00:03:39,970 kuid server. 71 00:03:39,970 --> 00:03:42,110 Node.js, mis on väga palju Seega märgib samuti. 72 00:03:42,110 --> 00:03:43,650 Sleek Android Design. 73 00:03:43,650 --> 00:03:46,990 Android on väga populaarne alternatiiv iOS ja Windows Phone 74 00:03:46,990 --> 00:03:48,790 ja muude mobiilsete platvormide. 75 00:03:48,790 --> 00:03:51,180 Ja Web Security Active Defense. 76 00:03:51,180 --> 00:03:54,590 >> Nii et tegelikult, kui soovite osalema selles, andke 77 00:03:54,590 --> 00:03:55,840 teha selle teadmiseks. 78 00:03:55,840 --> 00:03:57,790 Oleme väga hea meel öelda, et meie sõprade hüpe 79 00:03:57,790 --> 00:03:59,140 Motion, mis on startup - 80 00:03:59,140 --> 00:04:01,300 see seade tõesti lihtsalt tuli välja paar kuud tagasi - 81 00:04:01,300 --> 00:04:05,960 on lahkelt annetatud 30 selliste seadmete et klassis on palju õpilasi, kui 82 00:04:05,960 --> 00:04:08,670 soovite laenata riistvara poole semestri lõpus ja seda kasutada 83 00:04:08,670 --> 00:04:10,390 tegelik lõplik projekt. 84 00:04:10,390 --> 00:04:11,890 Nad toetavad mitmeid keeli. 85 00:04:11,890 --> 00:04:16,040 Ükski neist C, ükski neist PHP, nii viia ühte või mitut neist seminarid 86 00:04:16,040 --> 00:04:16,899 võib osutuda huvi. 87 00:04:16,899 --> 00:04:19,730 Ja kõik nad on filmitud Juhul, kui Teil ei ole võimalik 88 00:04:19,730 --> 00:04:21,380 isiklikult kohale ilmuda. 89 00:04:21,380 --> 00:04:25,000 Ajakava kuulutatakse kaudu emaili me tahkuma toad. 90 00:04:25,000 --> 00:04:28,460 >> Ja lõpuks, kui sa lähed projects.cs.50.net on see veebileht 91 00:04:28,460 --> 00:04:31,450 meil säilitada igal aastal, et me kutsume inimesed ühendusest, õppejõud, 92 00:04:31,450 --> 00:04:36,420 osakondade töötajad, ja nii aastal väljaspool CS50 et 93 00:04:36,420 --> 00:04:37,730 ettepaneku projektiideid. 94 00:04:37,730 --> 00:04:39,050 Asjad huvi rühmades. 95 00:04:39,050 --> 00:04:40,600 Asjad huvi osakonnad. 96 00:04:40,600 --> 00:04:43,990 Nii et ärge keerake seal kui sa oled hädas määramatuse, et mida sa 97 00:04:43,990 --> 00:04:46,700 ise tahaks tegeleda. 98 00:04:46,700 --> 00:04:51,760 >> Nii eelmisel korral tutvustasime väidetavalt keerulisem andmestruktuur kui olime 99 00:04:51,760 --> 00:04:53,300 näinud nädalat varem. 100 00:04:53,300 --> 00:04:56,550 Olime kasutades massiive päris õnneks on kasulik, kui 101 00:04:56,550 --> 00:04:58,160 lihtsustatud andmete struktuuri. 102 00:04:58,160 --> 00:05:00,570 Siis kehtestati need, mis muidugi on seotud nimekirju. 103 00:05:00,570 --> 00:05:05,470 Ja mis oli üks põhjusi kehtestatakse käesoleva andmete struktuur? 104 00:05:05,470 --> 00:05:06,930 Jah? 105 00:05:06,930 --> 00:05:07,250 Mis see on? 106 00:05:07,250 --> 00:05:08,080 >> Publik: Dynamic suurus. 107 00:05:08,080 --> 00:05:09,040 >> DAVID Malan: Dynamic suurus. 108 00:05:09,040 --> 00:05:11,890 Nii et massiivi, pead tean oma suurust ette kui 109 00:05:11,890 --> 00:05:12,740 sa jaotada see. 110 00:05:12,740 --> 00:05:14,380 In seotud nimekirja, siis ei ole pead teadma, et. 111 00:05:14,380 --> 00:05:17,610 Sa võid malloc või üldisemalt eraldada täiendavaid 112 00:05:17,610 --> 00:05:20,720 sõlm, nii et rääkida, iga kord, kui soovite lisada rohkem andmeid. 113 00:05:20,720 --> 00:05:22,670 Ja sõlm pole etteantud tähendus. 114 00:05:22,670 --> 00:05:25,580 See on lihtsalt üldine termin, mis kirjeldab mingi konteiner, et me oleme 115 00:05:25,580 --> 00:05:29,610 kasutades meie andmestruktuur salvestada mõned punktis huvi, mis käesolevas 116 00:05:29,610 --> 00:05:31,750 juhul juhtub olema täisarvud. 117 00:05:31,750 --> 00:05:33,160 >> Aga seal on alati kompromiss. 118 00:05:33,160 --> 00:05:38,070 Nii saame dünaamiline suurused andmed struktuur, kuid millise hinnaga me maksma? 119 00:05:38,070 --> 00:05:40,040 Mis on negatiivsed ahelloendid? 120 00:05:40,040 --> 00:05:41,006 Jah? 121 00:05:41,006 --> 00:05:41,980 >> Publik: nõuab rohkem mälu. 122 00:05:41,980 --> 00:05:44,240 >> DAVID Malan: See nõuab rohkem mälu, kuidas täpselt? 123 00:05:44,240 --> 00:05:46,440 >> Publik: [kuuldamatu]. 124 00:05:46,440 --> 00:05:47,050 >> DAVID Malan: Täpselt. 125 00:05:47,050 --> 00:05:50,460 Nüüd oleme suunanäitajaks asumist lisamälu, mida me varem 126 00:05:50,460 --> 00:05:53,040 ei pea, sest ära massiiv, muidugi, on see, et 127 00:05:53,040 --> 00:05:54,860 kõik on terviklik, tagasi kuni seljad, mis 128 00:05:54,860 --> 00:05:56,380 annab teile muutmälu. 129 00:05:56,380 --> 00:06:00,710 Sest just abil nurksulg märke või rohkem tehniliselt pointer 130 00:06:00,710 --> 00:06:03,580 aritmeetika, väga lihtne Lisaks saate juurdepääsu mis tahes 131 00:06:03,580 --> 00:06:05,700 elementide konstantse ajaga. 132 00:06:05,700 --> 00:06:08,975 Ja tegelikult, see on omamoodi vihjab teine ​​hind, mida me maksame koos 133 00:06:08,975 --> 00:06:09,760 seotud nimekirja. 134 00:06:09,760 --> 00:06:13,890 >> Mis juhtub sõiduaega midagi Search, kui ma tahan 135 00:06:13,890 --> 00:06:17,270 leida mingi väärtus ja sees on seotud nimekirja? 136 00:06:17,270 --> 00:06:20,290 Mis minu tööaeg muutunud? 137 00:06:20,290 --> 00:06:21,560 Big O n. 138 00:06:21,560 --> 00:06:24,060 Kui see on sorteeritud? 139 00:06:24,060 --> 00:06:25,440 Mida teha, kui andmestruktuur on järjestatud? 140 00:06:25,440 --> 00:06:28,640 Kas ma saan teha paremini kui suur O n otsida? 141 00:06:28,640 --> 00:06:31,700 Ei, sest halvimal juhul võib see väga hästi välja sorteerida, aga number 142 00:06:31,700 --> 00:06:32,950 otsite võib olla suur. 143 00:06:32,950 --> 00:06:35,370 See võib olla number 100, mis võib juhtuda, et kõik 144 00:06:35,370 --> 00:06:36,410 tee lõpus. 145 00:06:36,410 --> 00:06:39,950 Ja kuna saad avada ainult investeerimisriskiga nimekiri selles rakendamist 146 00:06:39,950 --> 00:06:42,690 viis oma esimese sõlme, oled ikka omamoodi õnne. 147 00:06:42,690 --> 00:06:47,450 Sul on läbida kogu asja Kogu aeg, et leida 148 00:06:47,450 --> 00:06:49,150 et suur väärtus nagu 100. 149 00:06:49,150 --> 00:06:51,350 Või kas see on isegi mitte seal. 150 00:06:51,350 --> 00:06:55,960 >> Nii et me ei saa teha seda, mida algoritm andmed struktuur, mis näeb välja nagu see on? 151 00:06:55,960 --> 00:06:59,460 Me ei saa seda teha binaarne otsing, sest binaarne otsing nõutav, et meil oli 152 00:06:59,460 --> 00:07:00,740 muutmälu. 153 00:07:00,740 --> 00:07:04,500 Me võiksime lihtsalt hüpe asukoht asukoha ilma järgima 154 00:07:04,500 --> 00:07:07,080 need leivapuru kujul kõiki neid näitajaid. 155 00:07:07,080 --> 00:07:08,300 >> Nüüd, kuidas me rakendada seda? 156 00:07:08,300 --> 00:07:12,830 Noh, kui me läheme ekraan siin, kui saame kiiresti implementeerid neid andmeid 157 00:07:12,830 --> 00:07:13,440 struktuur - 158 00:07:13,440 --> 00:07:15,670 mu käekiri pole veel kõik, mis suur siin, aga me proovime. 159 00:07:15,670 --> 00:07:22,030 Nii typedef struktuure, ja mis ma tegin soovite helistada seda asja siin? 160 00:07:22,030 --> 00:07:22,960 Sõlme. 161 00:07:22,960 --> 00:07:24,580 Nii et ma saan meile hakkas. 162 00:07:24,580 --> 00:07:27,860 Ja nüüd, mis peab olema sees andmestruktuuri et üksikult 163 00:07:27,860 --> 00:07:28,430 seotud nimekirja? 164 00:07:28,430 --> 00:07:29,950 Kuidas paljudes valdkondades? 165 00:07:29,950 --> 00:07:30,450 >> Nii kaks. 166 00:07:30,450 --> 00:07:31,570 Üks on päris lihtne. 167 00:07:31,570 --> 00:07:33,050 Nii int n. 168 00:07:33,050 --> 00:07:35,930 Ja me võiksime kutsuda n midagi tahame, kuid see peaks olema int kui me oleme 169 00:07:35,930 --> 00:07:37,660 rakendamisel, mis on seotud nimekirja ints. 170 00:07:37,660 --> 00:07:41,920 Ja nüüd, mida teeb teine valdkonnas olema? 171 00:07:41,920 --> 00:07:43,460 Struct sõlme *. 172 00:07:43,460 --> 00:07:50,570 Nii et kui ma teen struct tipp * ja siis ma võib helistada ka see, mida tahan, 173 00:07:50,570 --> 00:07:53,510 vaid lihtsalt olema selge ma helistan ta järgmisena, kui me oleme seda teinud. 174 00:07:53,510 --> 00:07:55,270 Ja siis ma sulen looksulg. 175 00:07:55,270 --> 00:08:00,700 >> Ja nüüd, kui viimane kord, Panin sõlme siin. 176 00:08:00,700 --> 00:08:03,830 Aga kui ma olen kuulutanud on sõlme, miks ma vaeva on nii 177 00:08:03,830 --> 00:08:07,320 lobise siin deklareerimisel struct sõlme *, vastandina 178 00:08:07,320 --> 00:08:09,210 lihtsalt sõlme * edasi? 179 00:08:09,210 --> 00:08:09,904 Jah? 180 00:08:09,904 --> 00:08:12,810 >> Publik: [kuuldamatu]. 181 00:08:12,810 --> 00:08:14,050 >> DAVID Malan: Täpselt. 182 00:08:14,050 --> 00:08:14,530 Täpselt. 183 00:08:14,530 --> 00:08:18,320 Kuna C tegelikult viib teid sõna otseses mõttes ja vaid näeb mõiste sõlme 184 00:08:18,320 --> 00:08:21,230 siia alla, siis ei saa vaadake seda siin. 185 00:08:21,230 --> 00:08:24,760 Nii et meil on selline ennetav avaldus siin, mis on küll 186 00:08:24,760 --> 00:08:25,390 rohkem paljusõnaline. 187 00:08:25,390 --> 00:08:27,810 Struct sõlme, mis tähendab, saame seda kasutada 188 00:08:27,810 --> 00:08:29,760 sees andmestruktuur. 189 00:08:29,760 --> 00:08:33,370 >> Ja kõrvale, sest see on muutub veidi subjektiivne nüüd, 190 00:08:33,370 --> 00:08:36,230 star saab tehniliselt minna siin, see ei lähe siin, võib see 191 00:08:36,230 --> 00:08:37,179 isegi minna keskel. 192 00:08:37,179 --> 00:08:39,890 Me oleme vastu, stiilis juhend Loomulikult konventsioon paneb 193 00:08:39,890 --> 00:08:42,299 star kõrval andmed tüüp, mis antud juhul 194 00:08:42,299 --> 00:08:43,460 oleks struct sõlme. 195 00:08:43,460 --> 00:08:46,620 Aga realiseerida palju õpikuid ja online-viited, võite tõepoolest 196 00:08:46,620 --> 00:08:48,450 vaata seda teisel pool. 197 00:08:48,450 --> 00:08:52,200 Aga mõistan, et mõlemad tegelikult töö ja sa peaksid lihtsalt olema 198 00:08:52,200 --> 00:08:52,970 järjepidev. 199 00:08:52,970 --> 00:08:53,580 >> Hea küll. 200 00:08:53,580 --> 00:08:55,630 Nii et oli meie deklaratsioon kohta struct sõlme. 201 00:08:55,630 --> 00:08:59,430 Aga siis hakkasime tegema rohkem keerulisi asju. 202 00:08:59,430 --> 00:09:03,410 Näiteks oleme otsustanud võtta kasutusele midagi hash tabelis. 203 00:09:03,410 --> 00:09:08,160 Nii et siin on hash tabelis suuruse n, indekseeritud 0 peal vasakult n 204 00:09:08,160 --> 00:09:09,690 miinus 1 all vasakul. 205 00:09:09,690 --> 00:09:11,640 See võiks olla hash tabel midagi. 206 00:09:11,640 --> 00:09:15,340 Aga milliseid asju me räägime kuidas kasutada hash tabel? 207 00:09:15,340 --> 00:09:18,370 Salvestamine mis? 208 00:09:18,370 --> 00:09:18,800 >> Nimed. 209 00:09:18,800 --> 00:09:20,870 Me saaksime nimed nagu me tegime viimane kord. 210 00:09:20,870 --> 00:09:22,200 Ja tõesti, võite salvestada midagi. 211 00:09:22,200 --> 00:09:24,640 Ja me näeme seda jälle PHP ja JavaScript. 212 00:09:24,640 --> 00:09:28,550 Hash tabel on ilus omamoodi Šveitsi Armee nuga, mis võimaldab teil salvestada 213 00:09:28,550 --> 00:09:33,690 päris palju iganes sa tahad sees see, seostades võtmed väärtused. 214 00:09:33,690 --> 00:09:34,770 Keys väärtustega. 215 00:09:34,770 --> 00:09:37,800 >> Nüüd see lihtne juhtum, meie Võtmed on lihtsalt numbrid. 216 00:09:37,800 --> 00:09:40,380 Me rakendamisel hash tabel massiivina. 217 00:09:40,380 --> 00:09:43,500 Ja nii võtmed on 0, 1, 2, ja nii edasi. 218 00:09:43,500 --> 00:09:47,200 Ja nii meil, inimestel, otsustas viimane nädalal, et sa tead, mida, kui me oleme 219 00:09:47,200 --> 00:09:50,410 läheb poodi nimed, lähme lihtsalt omavoliliselt, kuid üsna mõistlikult, 220 00:09:50,410 --> 00:09:54,680 eeldada, et Alice, nimi, lihtsalt olla indekseeritud 0. 221 00:09:54,680 --> 00:09:58,030 Ja Bob, B nimi, indekseeritakse arvesse 1, ja nii edasi. 222 00:09:58,030 --> 00:10:02,490 Seega oli meil kaardistamise vahel sisendite mis on stringid ja räsi 223 00:10:02,490 --> 00:10:04,560 kohtades, kus on numbrid. 224 00:10:04,560 --> 00:10:07,740 >> Nii et protsess on üldiselt tuntud räsifunktsiooni ning te saate tõeliselt 225 00:10:07,740 --> 00:10:09,130 rakendab seda koodi. 226 00:10:09,130 --> 00:10:12,080 Kui ma tahtsin rakendada räsifunktsiooni mis teeb täpselt seda, mida me 227 00:10:12,080 --> 00:10:17,070 just kirjeldatud alates viimane kord, ma võin kuulutada funktsioon, mis võtab, kui 228 00:10:17,070 --> 00:10:18,330 sisend näiteks - 229 00:10:18,330 --> 00:10:22,190 ja teeme seda selles ekraan siin. 230 00:10:22,190 --> 00:10:26,180 Kui ma tahtsin rakendada hash funktsioon, ma võiks öelda, 231 00:10:26,180 --> 00:10:27,410 midagi sellist. 232 00:10:27,410 --> 00:10:29,030 >> See läheb tagasi int. 233 00:10:29,030 --> 00:10:33,600 See saab nimeks hash, ja see on kavatse nõustuda argumendina 234 00:10:33,600 --> 00:10:38,920 string, või saame olla õige nüüd, ja öelda, char *, me kutsume seda s. 235 00:10:38,920 --> 00:10:43,840 Ja siis kõik see funktsioon on teha, lõppkokkuvõttes on tagasi int. 236 00:10:43,840 --> 00:10:45,990 Nüüd, kui see, mis võiks ei ole nii selge. 237 00:10:45,990 --> 00:10:49,510 Ma lähen, et rakendada seda ilma moodustavad viga kontrollides kohe. 238 00:10:49,510 --> 00:10:55,740 Ma lihtsalt pimesi öelda, tagasi mis iganes on s sulg 0, miinus, 239 00:10:55,740 --> 00:10:58,850 oletame, kapitali semikooloniga. 240 00:10:58,850 --> 00:10:59,960 >> Täiesti katki. 241 00:10:59,960 --> 00:11:02,620 See ei ole täiuslik, sest üks, mis siis, kui s on null? 242 00:11:02,620 --> 00:11:04,000 Halvad asjad hakkavad juhtuma. 243 00:11:04,000 --> 00:11:07,940 Kaks, mis siis, kui esimene täht selles nimi pole suurtäht? 244 00:11:07,940 --> 00:11:09,860 See ei kavatse pöörduda välja ka kas. 245 00:11:09,860 --> 00:11:11,970 See võib olla väike täht või kirja üldse. 246 00:11:11,970 --> 00:11:15,520 Seega täiesti võimalik teha edusamme, kuid see on peamine idee. 247 00:11:15,520 --> 00:11:19,010 >> Mida me kirjeldatud eelmisel nädalal suuliselt kui lihtsalt kaardistamise protsessi Alice 248 00:11:19,010 --> 00:11:23,360 0 ja Bob 1 saab väljendada kindlasti rohkem formulaically kui C 249 00:11:23,360 --> 00:11:24,320 toimi siin. 250 00:11:24,320 --> 00:11:28,630 Helistas uuesti räsi, võtab stringi sisend ja siis kuidagi ei midagi 251 00:11:28,630 --> 00:11:31,020 selle sisendi toota toodangut. 252 00:11:31,020 --> 00:11:34,130 Ei erinevalt meie musta kasti kirjeldus et me oleme kaua tehtud. 253 00:11:34,130 --> 00:11:36,550 Ma ei tea, kuidas see võiks olla töö all kapuuts. 254 00:11:36,550 --> 00:11:40,120 >> Sest probleem komplekt 6, üks väljakutseid on teil otsustada, millist 255 00:11:40,120 --> 00:11:41,920 on oma räsifunktsiooni olema? 256 00:11:41,920 --> 00:11:45,760 Mis saab olema sees, et must kast ja arvatavasti, see saab olema 257 00:11:45,760 --> 00:11:50,380 veidi huvitavam kui see, ja kindlasti rohkem altid viga 258 00:11:50,380 --> 00:11:53,180 kontroll kui selle konkreetse rakendamist. 259 00:11:53,180 --> 00:11:54,580 >> Kuid võib tekkida probleeme, eks ole? 260 00:11:54,580 --> 00:11:57,760 Kui meil on andmete struktuur, nagu see üks, mis on üks probleeme 261 00:11:57,760 --> 00:12:01,600 sa võid joosta rohkem aega kui sisestate rohkem nimesid 262 00:12:01,600 --> 00:12:02,880 hash tabel? 263 00:12:02,880 --> 00:12:04,630 Sa saad kokkupõrkeid, eks? 264 00:12:04,630 --> 00:12:07,560 Mida teha, kui teil on Alice ja Aaron, kaks inimest, kelle nimed juhtus 265 00:12:07,560 --> 00:12:08,190 alustada? 266 00:12:08,190 --> 00:12:11,660 See tekitab küsimuse, kuhu pane teine ​​selline nimi? 267 00:12:11,660 --> 00:12:15,050 >> Noh, sa võiksid naiivselt lihtsalt pane see kus Bob kuulub, kuid siis Bob on 268 00:12:15,050 --> 00:12:17,300 liiki kruvitud kui üritate sisestada oma nime kõrval ja 269 00:12:17,300 --> 00:12:18,240 Siin pole ruumi tema jaoks. 270 00:12:18,240 --> 00:12:21,400 Nii võite panna Bob kus Charlie on ja võite ette kujutada, see väga kiiresti 271 00:12:21,400 --> 00:12:23,020 läinud sisse natuke jama. 272 00:12:23,020 --> 00:12:25,600 Midagi lineaarne lõpuks, kui sa lihtsalt otsida kogu asi 273 00:12:25,600 --> 00:12:28,190 otsin Alice või Bob või Aaron või Charlie. 274 00:12:28,190 --> 00:12:33,230 >> Nii et selle asemel tegime ettepaneku, mitte ainult lineaarselt katsetamine avatud ruumid 275 00:12:33,230 --> 00:12:36,450 ja plopping nimed seal, me ettepaneku Kasvataja lähenemine. 276 00:12:36,450 --> 00:12:41,740 Hash tabelit rakendada ikka koos massiivi indeksid, kuid andmete tüüp 277 00:12:41,740 --> 00:12:44,500 need indeksid nüüd olid lähtekohtadeks. 278 00:12:44,500 --> 00:12:47,360 Näiturid mida? 279 00:12:47,360 --> 00:12:48,730 Näiturid seotud nimekirju. 280 00:12:48,730 --> 00:12:53,330 >> Sest meenutavad seotud nimekirja on tegelikult lihtsalt kursor sõlme, ja 281 00:12:53,330 --> 00:12:57,110 sõlm on järgmine väli ja et sõlm on järgmine väli ja nii edasi. 282 00:12:57,110 --> 00:13:00,690 Nii saab nüüd mõtlema selle massiivi vasakul servas hash tabelit 283 00:13:00,690 --> 00:13:01,820 viivad seotud nimekirja. 284 00:13:01,820 --> 00:13:07,000 Ära, mis on, kui saad kokkupõrge Alice ja Aaron, 285 00:13:07,000 --> 00:13:09,300 mida te teete Teine selline inimene? 286 00:13:09,300 --> 00:13:14,150 Sa lihtsalt lisada teda lõppu või isegi alguses 287 00:13:14,150 --> 00:13:15,490 Selle seotud nimekirja. 288 00:13:15,490 --> 00:13:17,340 >> Ja tegelikult, olgem lihtsalt makaron kaudu et just teine. 289 00:13:17,340 --> 00:13:18,640 Kus oleks kõige mõttekam? 290 00:13:18,640 --> 00:13:22,060 Kui ma sisestan Alice ja ta jõuab kell esimene asukoht, siis ma püüan 291 00:13:22,060 --> 00:13:25,310 sisestada Aaroni nimi, ja seal on ilmselt kokkupõrge, ma peaksin 292 00:13:25,310 --> 00:13:27,400 teda alguses on seotud nimekirja? 293 00:13:27,400 --> 00:13:30,944 See on see esimene asukoht, või lõpus? 294 00:13:30,944 --> 00:13:31,440 >> Publik: [kuuldamatu]. 295 00:13:31,440 --> 00:13:31,990 >> DAVID Malan: OK. 296 00:13:31,990 --> 00:13:32,490 Kuulsin hakanud. 297 00:13:32,490 --> 00:13:33,903 Miks alguses? 298 00:13:33,903 --> 00:13:34,750 >> Publik: [kuuldamatu]. 299 00:13:34,750 --> 00:13:34,940 >> DAVID Malan: OK. 300 00:13:34,940 --> 00:13:36,520 See on tähestikulises, et on tore. 301 00:13:36,520 --> 00:13:37,330 See on hea omadus. 302 00:13:37,330 --> 00:13:39,335 See säästab mind mõnda aega olla. 303 00:13:39,335 --> 00:13:43,290 Ta ei lase mul seda teha binaarne otsing, aga ma võiksid vähemalt suutma välja murda 304 00:13:43,290 --> 00:13:47,340 of loop kui ma mõistan, ma olen viis varem olid Aaron oleks see 305 00:13:47,340 --> 00:13:48,310 järjestatud seotud nimekirja. 306 00:13:48,310 --> 00:13:50,360 Ma ei pea raiska oma aega otsin kõik viis lõpuks. 307 00:13:50,360 --> 00:13:51,530 Nii et see mõistlik. 308 00:13:51,530 --> 00:13:54,710 Miks muidu võib soovite lisada kokkupõrkamise nime 309 00:13:54,710 --> 00:13:56,660 loetelu alguses? 310 00:13:56,660 --> 00:13:57,397 Mis see on? 311 00:13:57,397 --> 00:13:58,680 >> Publik: [kuuldamatu]. 312 00:13:58,680 --> 00:14:00,820 >> DAVID Malan: See võib võtta kaua aega saada nimekirja lõppu. 313 00:14:00,820 --> 00:14:02,490 Ja tegelikult, enam ja enam. 314 00:14:02,490 --> 00:14:04,920 Rohkem nimesid kui sisestate et alustada, seda pikem on 315 00:14:04,920 --> 00:14:06,280 kett ei hakka. 316 00:14:06,280 --> 00:14:07,890 Enam, et seotud nimekiri ei hakka. 317 00:14:07,890 --> 00:14:09,420 Nii et sa oled tõesti lihtsalt raiskad oma aega. 318 00:14:09,420 --> 00:14:14,070 Võibolla sa oled parem säilitada pidev sisestamise ajal suur O 1, 319 00:14:14,070 --> 00:14:18,470 poolt alati paneb põrgata nime algusega seotud nimekirja, 320 00:14:18,470 --> 00:14:21,230 ja mitte murettekitav, sest palju umbes sorteerimist. 321 00:14:21,230 --> 00:14:22,600 >> Milline on parim lahendus? 322 00:14:22,600 --> 00:14:23,320 See on selge. 323 00:14:23,320 --> 00:14:26,140 See liik sõltub sellest, mida jaotus on, mida struktuuris on 324 00:14:26,140 --> 00:14:27,850 nimed olete sisestamist. 325 00:14:27,850 --> 00:14:29,430 See ei ole tingimata Selge vastus. 326 00:14:29,430 --> 00:14:33,100 Aga siin jälle on disain võimalus. 327 00:14:33,100 --> 00:14:37,220 >> Nii me siis vaatasin seda asja, mis tegelikult on teine ​​suur võimalus 328 00:14:37,220 --> 00:14:38,180 p-set 6. 329 00:14:38,180 --> 00:14:41,770 Ja mõistma, kui te ei ole juba, Zamyla sukeldub mõlemad, hash 330 00:14:41,770 --> 00:14:43,260 tabelid ja katseid üksikasjalikumalt. 331 00:14:43,260 --> 00:14:45,630 Ja video läbikäiguks on varjatud p-set spec. 332 00:14:45,630 --> 00:14:46,590 See oli Prefiksipuu - 333 00:14:46,590 --> 00:14:51,670 T-R-I-E. Ja mis oli huvitav see oli, et sõiduaega 334 00:14:51,670 --> 00:14:59,510 otsivad nimi, nagu Maxwell Viimane kord oli suur O mida? 335 00:14:59,510 --> 00:15:01,040 Mis see on? 336 00:15:01,040 --> 00:15:01,920 >> Publik: tähtede arv. 337 00:15:01,920 --> 00:15:02,550 >> DAVID Malan arv tähti. 338 00:15:02,550 --> 00:15:03,210 Kuulsin kahte asja. 339 00:15:03,210 --> 00:15:04,630 Tähtede arv ja konstant korda. 340 00:15:04,630 --> 00:15:05,540 Lähme koos, et esimene. 341 00:15:05,540 --> 00:15:06,410 Tähtede arv. 342 00:15:06,410 --> 00:15:10,195 Noh, see andmestruktuur, mäletate, on nagu puu, sugupuu, iga 343 00:15:10,195 --> 00:15:12,860 kelle sõlmed koosnevad massiivid. 344 00:15:12,860 --> 00:15:16,300 Ja need massiivid on viiteid muud sellised sõlmede või muu selline 345 00:15:16,300 --> 00:15:17,670 massiivid puus. 346 00:15:17,670 --> 00:15:22,890 >> Nii et kui me tahame, et seejärel otsustada, kas Maxwell on siin, ma võiks minna 347 00:15:22,890 --> 00:15:26,890 esimese massiivi päris tippu puu, nn root tippu 348 00:15:26,890 --> 00:15:30,521 Prefiksipuu ja järgige m pointer, siis pointer, siis x, 349 00:15:30,521 --> 00:15:31,710 w, e, l, l. 350 00:15:31,710 --> 00:15:34,910 Ja siis, kui ma näen mõningaid erilisi sümbol, tähistatakse siin kolmnurk. 351 00:15:34,910 --> 00:15:38,480 In kood näete teeme ettepaneku, et sa rakendatakse bool, lihtsalt ütlen jah 352 00:15:38,480 --> 00:15:40,540 või ei, sõna peatub siin. 353 00:15:40,540 --> 00:15:45,270 >> Noh, kui oleme läinud M--X-W-E-L-L, tundub seitse, võibolla 354 00:15:45,270 --> 00:15:48,910 kaheksa, kui me läheme ühe minevikus, kaheksa samme, et teada Maxwell. 355 00:15:48,910 --> 00:15:53,050 Või ütleme K. Aga mäletate viimast aega, ma väita, et kui seal on 356 00:15:53,050 --> 00:15:57,540 realistlikult maksimaalne pikkus on Ühesõnaga, nagu 40-mõned-paaritu tähtedega 357 00:15:57,540 --> 00:16:00,810 maksimaalne pikkus tähendab püsiv väärtus. 358 00:16:00,810 --> 00:16:05,770 Nii et tõesti, jah, see on tehniliselt suur O 8 või 7 või tõesti suur O K. Aga 359 00:16:05,770 --> 00:16:09,420 kui seal on piiratud kate mida K võib olla, see on pidev. 360 00:16:09,420 --> 00:16:12,080 Ja nii see on suur O 1 juures Päeva lõpuks. 361 00:16:12,080 --> 00:16:13,040 >> Mitte reaalses maailmas. 362 00:16:13,040 --> 00:16:15,960 Mitte siis, kui sa tegelikult alustada vaadates oma kella oma programmi algust. 363 00:16:15,960 --> 00:16:20,690 See on absoluutselt läheb natuke aeglasem kui tõesti pidev 364 00:16:20,690 --> 00:16:21,840 aega üks samm. 365 00:16:21,840 --> 00:16:25,540 See saab olema seitse või kaheksa samme, kuid see on palju, palju parem 366 00:16:25,540 --> 00:16:30,080 kui algoritmi nagu suur O n, et sõltub suurusest, mis on sisse 367 00:16:30,080 --> 00:16:31,220 andmestruktuur. 368 00:16:31,220 --> 00:16:34,970 >> Märka pea siin saame sisestada miljonit rohkem nimesid sellesse 369 00:16:34,970 --> 00:16:38,170 andmete struktuuri, kuid kui palju samme see läheb meid leida 370 00:16:38,170 --> 00:16:40,480 Maxwell sel juhul? 371 00:16:40,480 --> 00:16:40,780 Ei ole. 372 00:16:40,780 --> 00:16:41,820 Ta on muutunud. 373 00:16:41,820 --> 00:16:45,480 Ja siiani, ma ei usu, et me oleme näinud näiteks andmete struktuuri või 374 00:16:45,480 --> 00:16:48,560 algoritm, mis oli täiesti mõjutanud välised 375 00:16:48,560 --> 00:16:50,040 käitumist niimoodi. 376 00:16:50,040 --> 00:16:51,160 Kuid see ei saa olla hämmastav. 377 00:16:51,160 --> 00:16:52,900 See ei saa olla ainus lahendus jaoks p-set 378 00:16:52,900 --> 00:16:53,570 >> Ja see ei ole. 379 00:16:53,570 --> 00:16:55,980 See ei pruugi andmed struktuur, mida peaks vajuma, 380 00:16:55,980 --> 00:16:58,220 sest nagu hash tabeleid kompromissiga. 381 00:16:58,220 --> 00:17:00,500 Mis on hind, mida maksate here? 382 00:17:00,500 --> 00:17:00,940 Mälu. 383 00:17:00,940 --> 00:17:02,890 Ma mõtlen, et see on jõle mälu. 384 00:17:02,890 --> 00:17:05,569 Ja sa ei saa päris näha siin, sest autor seda pilti 385 00:17:05,569 --> 00:17:09,420 ilmselt kärbitud kõik massiivid ja me ei näe palju on ja 386 00:17:09,420 --> 00:17:12,700 B-ja C-ja Q-ja Y ja Z on nendes massiivid. 387 00:17:12,700 --> 00:17:13,630 Aga nad on olemas. 388 00:17:13,630 --> 00:17:17,660 >> Kõik need sõlmed on terve rida mõned 26 või rohkem baite iga 389 00:17:17,660 --> 00:17:19,170 mis kujutab endast kirjas. 390 00:17:19,170 --> 00:17:22,920 27 meie puhul nii, et me ei toeta ülakomade sisse lahendamist. 391 00:17:22,920 --> 00:17:27,030 Nii et see andmestruktuur on tõesti, tõesti tihe ja lai. 392 00:17:27,030 --> 00:17:30,880 Ja üksi sattuda aeglustub asju ette, või vähemalt maksab teile 393 00:17:30,880 --> 00:17:32,240 palju rohkem ruumi. 394 00:17:32,240 --> 00:17:34,020 Aga jälle, saame teha võrdlused siin. 395 00:17:34,020 --> 00:17:39,190 >> Meenuta aega tagasi, oleme saavutanud palju põnevam sõiduaega sorteerimine 396 00:17:39,190 --> 00:17:42,880 kui me kasutame Tarkvaraprojekteerimise, kuid hind pöörasime saavutada n log n ühendamist 397 00:17:42,880 --> 00:17:46,930 sort vaja, et me kulutame rohkem, mida ressurss? 398 00:17:46,930 --> 00:17:47,690 Rohkem ruumi. 399 00:17:47,690 --> 00:17:50,530 Meil oli vaja teisese massiivi kopeerida inimesi, just nagu 400 00:17:50,530 --> 00:17:51,620 tegime siin laval. 401 00:17:51,620 --> 00:17:55,880 Nii et taas, ei ole selge, võitjad, aga lihtsalt subjektiivne disain 402 00:17:55,880 --> 00:17:57,710 otsuseid teha. 403 00:17:57,710 --> 00:17:58,060 >> Hea küll. 404 00:17:58,060 --> 00:17:59,130 Niisiis, kuidas see on? 405 00:17:59,130 --> 00:18:02,050 Igaüks, kumb D-Hall? 406 00:18:02,050 --> 00:18:02,440 OK. 407 00:18:02,440 --> 00:18:03,170 Nii me kolmekesi tegema. 408 00:18:03,170 --> 00:18:03,750 Ema House. 409 00:18:03,750 --> 00:18:05,070 Nii see on Ema söögisaalis. 410 00:18:05,070 --> 00:18:09,650 Vean kihla, et kõik söögisaali olema korstnad plaate niimoodi. 411 00:18:09,650 --> 00:18:11,950 Ja see on tegelikult esindaja midagi me oleme 412 00:18:11,950 --> 00:18:13,050 ilmselt näinud juba. 413 00:18:13,050 --> 00:18:14,850 Me kutsusime seda sõna otseses mõttes pinu. 414 00:18:14,850 --> 00:18:18,970 Ja stack nii oma arvuti mälu, kus info läheb 415 00:18:18,970 --> 00:18:20,460 samas funktsioone kutsutakse. 416 00:18:20,460 --> 00:18:23,410 >> Näiteks milliseid asju minema stack suhtes 417 00:18:23,410 --> 00:18:27,420 mälupaigutuse oleme arutanud nädalates varem? 418 00:18:27,420 --> 00:18:28,736 Mis see on? 419 00:18:28,736 --> 00:18:29,670 >> Publik: Kõned funktsioone. 420 00:18:29,670 --> 00:18:30,260 >> DAVID Malan: Mul on kahju. 421 00:18:30,260 --> 00:18:31,210 >> Publik: Kõned funktsioone. 422 00:18:31,210 --> 00:18:33,590 >> DAVID Malan: Kõned funktsioone, kuid Täpsemalt, milline on sees iga 423 00:18:33,590 --> 00:18:35,340 need raamid? 424 00:18:35,340 --> 00:18:37,220 Milliseid asju? 425 00:18:37,220 --> 00:18:37,460 Jah. 426 00:18:37,460 --> 00:18:38,500 Nii kohalikud muutujad. 427 00:18:38,500 --> 00:18:43,080 Anytime me vajas kohalike ladustamine, nagu argument, või int I või int 428 00:18:43,080 --> 00:18:45,940 temp, või mis iganes kohalike muutuja, oleme olnud 429 00:18:45,940 --> 00:18:47,210 pannes, et korstnat. 430 00:18:47,210 --> 00:18:49,610 Ja me nimetame seda virna sest selle kihilisus idee. 431 00:18:49,610 --> 00:18:52,940 Just selline sobitab reaalsusega, kontseptsiooni kohta. 432 00:18:52,940 --> 00:18:56,650 >> Aga selgub, et stack saab ka vaadelda kui andmestruktuur, 433 00:18:56,650 --> 00:19:00,110 Alternatiivina massiiv, alternatiivne et seotud nimekirja. 434 00:19:00,110 --> 00:19:02,770 Midagi sisuliselt huvitavamaks mis saab veel 435 00:19:02,770 --> 00:19:06,030 rakendada, kasutades kas nende asju, aga see on teist tüüpi 436 00:19:06,030 --> 00:19:09,140 andmestruktuur toetamine, tõesti, ainult kaks tegevust. 437 00:19:09,140 --> 00:19:11,000 Aga sa võid lisada Kasvataja funktsioone kui need. 438 00:19:11,000 --> 00:19:12,180 Aga need on põhitõed - 439 00:19:12,180 --> 00:19:13,510 push ja pop. 440 00:19:13,510 --> 00:19:19,240 >> Ja idee stack on, et kui ma on siin, koos või ilma Annenberg 441 00:19:19,240 --> 00:19:22,880 teades, salv kõrvalmajas arvuga 9 peal. 442 00:19:22,880 --> 00:19:23,870 Nii lihtsalt int. 443 00:19:23,870 --> 00:19:26,990 Ja ma tahan, et lükata see peale andmed struktuur, mis praegu on tühi. 444 00:19:26,990 --> 00:19:28,790 Mõelge sellele põhja pinu. 445 00:19:28,790 --> 00:19:33,150 Ma tõstaks see number 9 peale korstnat, ja nüüd on see siin. 446 00:19:33,150 --> 00:19:36,040 >> Aga huvitav asi korstnat on see, et kui ma nüüd tahan suruda 447 00:19:36,040 --> 00:19:40,210 muu väärtus, nagu 17 ja ma push Selle peale virna, ma lähen tegema 448 00:19:40,210 --> 00:19:43,290 ainult intuitiivne asi, ma lihtsalt läheb pane see õige, kui meie, inimesed 449 00:19:43,290 --> 00:19:45,180 kalduks panna see peal. 450 00:19:45,180 --> 00:19:48,850 Aga mis on huvitav nüüd on, kuidas ma saan kell 9? 451 00:19:48,850 --> 00:19:50,670 Tead, ma ei ole ilma mõned pingutust. 452 00:19:50,670 --> 00:19:54,070 >> Mis on huvitav stack on, et projekteerimise, 453 00:19:54,070 --> 00:19:56,330 see on LIFO andmestruktuur. 454 00:19:56,330 --> 00:19:59,680 Rumal viis kirjeldada viimane esimene välja. 455 00:19:59,680 --> 00:20:03,280 Seega viimane number sel ajal oli 17. 456 00:20:03,280 --> 00:20:07,540 Nii et kui ma tahan pop midagi maha virna, see saab olla ainult 17. 457 00:20:07,540 --> 00:20:11,890 Nii et seal on kohustuslik järjekorras operatsioonide siin, kus viimane punkt 458 00:20:11,890 --> 00:20:14,260 aastal peab olema esimene välja. 459 00:20:14,260 --> 00:20:16,440 Seega akronüüm, LIFO. 460 00:20:16,440 --> 00:20:19,160 >> Miks võib see olla kasulik? 461 00:20:19,160 --> 00:20:22,690 Kas nende konteksti, milles soovite tahad andmestruktuuri nagu see on? 462 00:20:22,690 --> 00:20:24,810 Noh, see on kindlasti kasu olnud sees arvuti. 463 00:20:24,810 --> 00:20:29,050 Nii operatsioonisüsteemide selgelt seda objekti andmestruktuur korstnad. 464 00:20:29,050 --> 00:20:32,800 Me näeme ka sama mõte kui tegemist on veebilehtedel. 465 00:20:32,800 --> 00:20:35,890 Nii et see nädal ja järgmisel nädalal ja kaugemalgi ja kui hakkad rakendamise web 466 00:20:35,890 --> 00:20:39,490 lehekülgede keeles nimetatakse HTML, võite tegelikult kasutada andmestruktuuri nagu 467 00:20:39,490 --> 00:20:42,690 Selle määramiseks, kas lehekülg on õigesti vormindatud. 468 00:20:42,690 --> 00:20:47,170 Sest me näeme, kõik veebilehti järgima omamoodi hierarhia, taandus 469 00:20:47,170 --> 00:20:52,030 mis, lõpus päeval, siis puu struktuuri all kapuuts. 470 00:20:52,030 --> 00:20:53,620 Nii enam edasi, et vaid veidi. 471 00:20:53,620 --> 00:20:56,560 >> Aga nüüd, lähme ettepaneku kohta hetk, kuidas me saaksime minna 472 00:20:56,560 --> 00:20:58,830 esindavad mida stack on? 473 00:20:58,830 --> 00:21:03,370 Las ma ettepaneku, et me ellu stack koodiga niimoodi. 474 00:21:03,370 --> 00:21:07,990 Nii stack läheb on sees on kaks asja, array nimega plaate, 475 00:21:07,990 --> 00:21:09,510 lihtsalt olla kooskõlas demo. 476 00:21:09,510 --> 00:21:12,660 Ja iga toodet, mis massiivi saab olema tüüpi int. 477 00:21:12,660 --> 00:21:14,740 Ja võimsus on oletatavasti? 478 00:21:14,740 --> 00:21:18,796 Sest ma ei ole kirjutatud täielik määratlus siin. 479 00:21:18,796 --> 00:21:21,535 >> See on ilmselt suurim suurusest massiivist. 480 00:21:21,535 --> 00:21:25,150 Ja see on ilmselt deklareeritud terav define ülaosas faili, mõned 481 00:21:25,150 --> 00:21:28,450 selline pidev, kui sellele viitab Ainuüksi kapitaliseeritust. 482 00:21:28,450 --> 00:21:32,250 Nii kuskil maht on määratletud maksimaalne võimalik suurus. 483 00:21:32,250 --> 00:21:35,590 Vahepeal sees andmestruktuur tuntud stack seal 484 00:21:35,590 --> 00:21:38,630 olema täisarv lihtsalt teada lihtsalt suurus. 485 00:21:38,630 --> 00:21:43,400 >> Nii et kui ma oleks esindada seda nüüd piltlikult oletame, et see 486 00:21:43,400 --> 00:21:48,070 kogu must kast esindab minu stack. 487 00:21:48,070 --> 00:21:50,070 Toas on kaks muutujat. 488 00:21:50,070 --> 00:21:54,780 Ma lähen, et juhtida Esimene on suurus. 489 00:21:54,780 --> 00:21:57,420 Ja teine ​​ma lähen juhtida massiivina. 490 00:21:57,420 --> 00:22:01,060 >> Aga lihtsalt, et hoida asjad korrapärane, tavaliselt Juhin massiivi nagu 491 00:22:01,060 --> 00:22:04,910 , kuid see on selline kena kui me mängu reaalsus, või 492 00:22:04,910 --> 00:22:06,230 sobitada vaimne mudel. 493 00:22:06,230 --> 00:22:12,880 Nii et lubage mul vaid teha massiivi vertikaalselt, mis on vaid jällegi 494 00:22:12,880 --> 00:22:13,840 Kunstniku üleviimise. 495 00:22:13,840 --> 00:22:16,610 Ei ole tegelikult oluline, mida see on alla kapuuts. 496 00:22:16,610 --> 00:22:20,350 Ja me ütleme, et vaikimisi, võimsus saab olema kolm. 497 00:22:20,350 --> 00:22:23,480 Nii et see saab olema asukoha 0, siis on asukoht 1, see 498 00:22:23,480 --> 00:22:25,740 on koht 2. 499 00:22:25,740 --> 00:22:29,330 >> Kui ma altkäemaksu koos stressi pall, eks keegi meeldib tulla ja käivitada 500 00:22:29,330 --> 00:22:30,870 pardale siin hetkeks? 501 00:22:30,870 --> 00:22:31,960 OK, nägin oma käsi esimene. 502 00:22:31,960 --> 00:22:33,950 Tule üles. 503 00:22:33,950 --> 00:22:36,500 Hea küll. 504 00:22:36,500 --> 00:22:38,760 Nii et ma usun, et see on Steven. 505 00:22:38,760 --> 00:22:40,035 Tule üles. 506 00:22:40,035 --> 00:22:40,770 Hea küll. 507 00:22:40,770 --> 00:22:46,760 >> Aga oletame nüüd me tagasikerimiseks esialgse riik maailmas, kus ma 508 00:22:46,760 --> 00:22:52,180 äsja kuulutatud virna, ja see on kavatse olla läbilaskevõime kolm. 509 00:22:52,180 --> 00:22:54,470 Aga suurus ei ole veel kindlaks määratud. 510 00:22:54,470 --> 00:22:56,100 Plaate ei ole veel kindlaks määratud. 511 00:22:56,100 --> 00:22:57,300 Nii paar küsimust esimene. 512 00:22:57,300 --> 00:23:01,310 Ja lubage mul anda teile mic, nii et saate Nautida aktiivsemalt selles. 513 00:23:01,310 --> 00:23:05,190 >> Mis on sees suurus praegu ajal, kui ma olen teinud on 514 00:23:05,190 --> 00:23:09,340 deklareeritud korstnat üks rida koodi? 515 00:23:09,340 --> 00:23:10,100 >> Steven: Mitte palju. 516 00:23:10,100 --> 00:23:12,080 >> DAVID Malan: OK, ei ole palju. 517 00:23:12,080 --> 00:23:14,410 Kas me teame, mis seal sees on suurus, me teame, mis seal sees on 518 00:23:14,410 --> 00:23:16,330 Selle massiivi siin? 519 00:23:16,330 --> 00:23:18,630 >> Steven: Just juhusliku koodi, eks? 520 00:23:18,630 --> 00:23:20,220 Just - 521 00:23:20,220 --> 00:23:23,230 >> DAVID Malan: Jah, ma lähen nimetame seda koodi, kuid juhuslik - 522 00:23:23,230 --> 00:23:23,820 >> Steven: asjad. 523 00:23:23,820 --> 00:23:28,290 >> DAVID Malan: Asjad juhuslik 524 00:23:28,290 --> 00:23:28,870 >> Steven: Bits. 525 00:23:28,870 --> 00:23:29,530 >> DAVID Malan: Bits, eks? 526 00:23:29,530 --> 00:23:31,190 Nii prügi väärtused, eks? 527 00:23:31,190 --> 00:23:33,470 Nii permutatsiooni 0-ja 1 aasta. 528 00:23:33,470 --> 00:23:35,920 Jäänused eelmine tavasid Selle mälu. 529 00:23:35,920 --> 00:23:38,150 Ja me ei tea, mis väärtused on, et me tavaliselt juhtida neid 530 00:23:38,150 --> 00:23:38,930 nagu küsimärgid. 531 00:23:38,930 --> 00:23:41,990 >> Nii et esimene asi, mida me arvatavasti lähed tahan teha siin - 532 00:23:41,990 --> 00:23:46,630 ja las ma annan selle valdkonna sees seal nimi - plaate. 533 00:23:46,630 --> 00:23:49,540 Mida me peaksime ilmselt initsialiseerida suurus, kui tahame 534 00:23:49,540 --> 00:23:51,040 alustada, kasutades seda korstnat? 535 00:23:51,040 --> 00:23:53,070 >> Steven: Tray on sub 3. 536 00:23:53,070 --> 00:23:53,910 >> DAVID Malan: Niisiis, OK. 537 00:23:53,910 --> 00:23:56,710 Et oleks selge, võimsus on välja kuulutatud mujal kui kolm. 538 00:23:56,710 --> 00:23:58,570 Ja see, mida ma olen kasutanud jaotada massiivi. 539 00:23:58,570 --> 00:24:03,535 Suurus läheb vaadake, kui palju plaate on praegu pinu. 540 00:24:03,535 --> 00:24:03,880 >> Steven: Zero. 541 00:24:03,880 --> 00:24:04,460 >> DAVID Malan: Seega peaks olema null. 542 00:24:04,460 --> 00:24:07,760 Nii et laske käia ja iga sõrme, juhtida null suurusega. 543 00:24:07,760 --> 00:24:08,440 Hea küll. 544 00:24:08,440 --> 00:24:10,920 Nüüd, mis on sees see siin, me ei tea. 545 00:24:10,920 --> 00:24:12,160 Need on tõesti lihtsalt prügi väärtused. 546 00:24:12,160 --> 00:24:14,800 Nii et me võime joonistada küsimärke, kuid Hoidkem pardal puhas nüüd 547 00:24:14,800 --> 00:24:16,300 sest see ei ole oluline mis seal on. 548 00:24:16,300 --> 00:24:19,130 Meil ei ole vaja initsialiseerida array midagi, sest me teame, et 549 00:24:19,130 --> 00:24:23,100 suurus stack on null, noh, me ei tohiks olla vaadates midagi 550 00:24:23,100 --> 00:24:25,590 Selle massiivi niikuinii juures ajahetkel. 551 00:24:25,590 --> 00:24:29,970 >> Nüüd oletame, et ma suruge number 9 peale virna. 552 00:24:29,970 --> 00:24:33,750 Kuidas me peaksime uuendama andmestruktuur sees see must kast? 553 00:24:33,750 --> 00:24:35,540 Mis väärtused on vaja muuta? 554 00:24:35,540 --> 00:24:36,200 >> Steven: jooksul - 555 00:24:36,200 --> 00:24:37,400 suurus? 556 00:24:37,400 --> 00:24:37,650 >> DAVID Malan: OK. 557 00:24:37,650 --> 00:24:38,770 Suurus peaks saama mis? 558 00:24:38,770 --> 00:24:39,580 >> Steven: Suurus oleks üks. 559 00:24:39,580 --> 00:24:39,870 >> DAVID Malan: OK. 560 00:24:39,870 --> 00:24:41,110 Nii suurus peaks olema üks. 561 00:24:41,110 --> 00:24:42,540 Nii saate teha seda paar võimalust. 562 00:24:42,540 --> 00:24:46,920 Annan teile, nüüd oma sõrm on kustutuskumm. 563 00:24:46,920 --> 00:24:47,260 Hea küll. 564 00:24:47,260 --> 00:24:49,960 Siis nüüd sõrm on pintsel. 565 00:24:49,960 --> 00:24:50,330 Hea küll. 566 00:24:50,330 --> 00:24:52,820 Ja nüüd, mida teised on muuta, Ilmselt andmete struktuur? 567 00:24:52,820 --> 00:24:57,060 >> Steven: Me läheme alates põhja kuni 9. 568 00:24:57,060 --> 00:24:57,760 >> DAVID Malan: 9. 569 00:24:57,760 --> 00:24:58,420 OK, hea. 570 00:24:58,420 --> 00:25:01,550 Nii ikka ei ole oluline, mis kell Asukoht üks või kaks, sest nad on 571 00:25:01,550 --> 00:25:04,520 prügi väärtused, kuid me ei peaks vaeva nägema otsin seal, sest suurus on 572 00:25:04,520 --> 00:25:07,540 ütleb meile, et ainult esimene element on tegelikult õigustatud. 573 00:25:07,540 --> 00:25:10,400 Nüüd ma push 17 peale nimekirja. 574 00:25:10,400 --> 00:25:11,830 Mis juhtub seda pilti? 575 00:25:11,830 --> 00:25:14,720 >> Steven: Nii suurus läheb minema kaks. 576 00:25:14,720 --> 00:25:15,300 >> DAVID Malan: OK. 577 00:25:15,300 --> 00:25:16,070 Sa oled kustutuskumm - 578 00:25:16,070 --> 00:25:16,810 oops. 579 00:25:16,810 --> 00:25:18,026 Sa oled kustutuskumm. 580 00:25:18,026 --> 00:25:18,840 >> Steven: Eraser. 581 00:25:18,840 --> 00:25:19,720 >> DAVID Malan: Sa oled pintsliga. 582 00:25:19,720 --> 00:25:20,560 >> Steven: Võsa. 583 00:25:20,560 --> 00:25:20,920 >> DAVID Malan: OK. 584 00:25:20,920 --> 00:25:21,600 Ja mis veel? 585 00:25:21,600 --> 00:25:22,600 >> Steven: Ja siis - 586 00:25:22,600 --> 00:25:22,915 >> DAVID Malan: nõudsime 17. 587 00:25:22,915 --> 00:25:24,760 >> Steven: Me jääda 17 peal, nii et - 588 00:25:24,760 --> 00:25:25,710 >> DAVID Malan: OK, hea. 589 00:25:25,710 --> 00:25:27,040 >> Steven: - tilk maha. 590 00:25:27,040 --> 00:25:27,530 >> DAVID Malan: Olgu. 591 00:25:27,530 --> 00:25:27,940 See muutub lihtne. 592 00:25:27,940 --> 00:25:29,300 Ma ei kavatse teid aidata seekord. 593 00:25:29,300 --> 00:25:30,510 Push 22. 594 00:25:30,510 --> 00:25:31,720 >> Steven: Valmis. 595 00:25:31,720 --> 00:25:34,870 Saades kustutuskumm. 596 00:25:34,870 --> 00:25:37,340 Olen muutumas pintsliga. 597 00:25:37,340 --> 00:25:39,340 Ja siis ma panen 22. 598 00:25:39,340 --> 00:25:40,100 >> DAVID Malan: 22. 599 00:25:40,100 --> 00:25:40,620 Suurepärane. 600 00:25:40,620 --> 00:25:41,380 Nii et üks rohkem aega. 601 00:25:41,380 --> 00:25:44,280 Ma nüüd sunnin peale virna 26. 602 00:25:44,280 --> 00:25:46,350 >> Steven: Ooh. 603 00:25:46,350 --> 00:25:50,278 Oh jumal. 604 00:25:50,278 --> 00:25:52,520 Sa tõesti püütud mind välja kaitsepiire. 605 00:25:52,520 --> 00:25:53,703 >> DAVID Malan: sa ei ole see peaks toimuma? 606 00:25:53,703 --> 00:25:55,930 >> Steven: Ma ei näinud seda tulemas. 607 00:25:55,930 --> 00:25:58,756 Võiks me uuesti algne maht? 608 00:25:58,756 --> 00:25:59,790 >> DAVID Malan: See on hea küsimus. 609 00:25:59,790 --> 00:26:02,360 Nii et me oleme omamoodi värvitud end nurgas siin. 610 00:26:02,360 --> 00:26:06,740 Seal tõesti ei ole hea välja Steven sest me oleme eraldatud selle massiivi 611 00:26:06,740 --> 00:26:09,130 staatiliselt, niiöelda sees andmete struktuuri. 612 00:26:09,130 --> 00:26:12,170 Ja me oleme sisuliselt kõva kodeeritud see olevat suurus kolm. 613 00:26:12,170 --> 00:26:14,170 Nii et me ei saa tõesti suunata see. 614 00:26:14,170 --> 00:26:20,020 >> Võiksime kui läksime tagasi, me uuesti kandikud olla pointer et 615 00:26:20,020 --> 00:26:22,300 me siis kasuta malloc kätte mälu. 616 00:26:22,300 --> 00:26:25,050 Sest kui meil on mälu hunnik kaudu malloc oleme 617 00:26:25,050 --> 00:26:26,430 võiks siis vabastada ta. 618 00:26:26,430 --> 00:26:29,630 Aga enne vabastades ta, võiksime suunata suurem patakas mälu 619 00:26:29,630 --> 00:26:31,330 uuendada pointer, ja nii edasi. 620 00:26:31,330 --> 00:26:33,500 Aga nüüd, see on tõesti Parim, mida me teha saame. 621 00:26:33,500 --> 00:26:36,360 Push ja pop on arvatavasti läheb et anda märku mõni viga. 622 00:26:36,360 --> 00:26:40,270 >> Nii näiteks meie rakendamise push võib naasta bool mis 623 00:26:40,270 --> 00:26:42,390 varem tagastatakse true, true, true. 624 00:26:42,390 --> 00:26:48,390 Aga neljandat korda, see läheb on tagasi false, näiteks. 625 00:26:48,390 --> 00:26:48,540 Hea küll. 626 00:26:48,540 --> 00:26:49,540 Väga hästi tehtud. 627 00:26:49,540 --> 00:26:50,060 Palju õnne. 628 00:26:50,060 --> 00:26:52,160 Olete teeninud oma stressi pall täna. 629 00:26:52,160 --> 00:26:53,110 >> [APLAUS] 630 00:26:53,110 --> 00:26:54,382 >> Steven: Aitäh. 631 00:26:54,382 --> 00:26:55,680 >> DAVID Malan: Aitäh. 632 00:26:55,680 --> 00:26:59,740 OK, nii see tundub olevat mitte palju on samm edasi, eks? 633 00:26:59,740 --> 00:27:01,410 Meil on kirjeldatud käesoleva andmete struktuuri. 634 00:27:01,410 --> 00:27:02,320 See on olnud veenvad, eks? 635 00:27:02,320 --> 00:27:03,200 Operatsioonisüsteemide nagu see. 636 00:27:03,200 --> 00:27:06,360 Ilmselt web saab kasutada seda, ja muid rakendusi veel. 637 00:27:06,360 --> 00:27:10,870 Aga mis loll piirang, et me oleme Tagasi omamoodi nädal kaks piirmäära 638 00:27:10,870 --> 00:27:12,880 kus meil on fikseeritud suurus massiivid. 639 00:27:12,880 --> 00:27:15,010 >> Seega on tõepoolest paar kuidas me võiksime lahendada. 640 00:27:15,010 --> 00:27:18,750 Võiksime dünaamiliselt jaotab massiivi mitte raske kodeerimine see nagu ma olen 641 00:27:18,750 --> 00:27:22,600 teha siin, vaid uuesti kuulutatakse see lihtsalt peab olema selge, kui 642 00:27:22,600 --> 00:27:23,830 midagi sellist. 643 00:27:23,830 --> 00:27:29,040 Int * plaate ei otsusta edasi maht veel. 644 00:27:29,040 --> 00:27:35,460 Aga kui ma tunnistada stack mujal minu kood, ma võiks siis kutsuda malloc, 645 00:27:35,460 --> 00:27:38,250 saada aadress tüki mälu, ja ma ei anna 646 00:27:38,250 --> 00:27:39,980 et aadressi plaate. 647 00:27:39,980 --> 00:27:43,340 >> Ja siis, kuna see on lihtsalt kamakas mälu, ma võiks jätkuvalt kasutada ruudu 648 00:27:43,340 --> 00:27:45,450 sulg märke tavalisel viisil. 649 00:27:45,450 --> 00:27:49,020 Kuna jällegi on omamoodi see funktsionaalne ekvivalent massiivid ja 650 00:27:49,020 --> 00:27:50,820 tükkideks mälu, mis tulevad tagasi malloc. 651 00:27:50,820 --> 00:27:53,090 Me võime ravida üks kui teine kasutades pointer aritmeetika või 652 00:27:53,090 --> 00:27:54,440 nurksulg märke. 653 00:27:54,440 --> 00:27:55,660 Nii et see on üks võimalusi. 654 00:27:55,660 --> 00:28:00,120 >> Aga kuidas muidu võiks me rakendada seda samade andmete struktuuri, potentsiaalselt? 655 00:28:00,120 --> 00:28:00,280 Õigus? 656 00:28:00,280 --> 00:28:04,530 Ma tunnen, et me just lahendasime selle probleem nagu nädal tagasi. 657 00:28:04,530 --> 00:28:08,860 Milline oli lahendus sellele probleemile et Steven sattus? 658 00:28:08,860 --> 00:28:10,370 Nii ahelloendid, eks. 659 00:28:10,370 --> 00:28:13,410 >> Kui probleem on selles, et me oleme värvimine end nurka, eraldades 660 00:28:13,410 --> 00:28:17,580 ette liiga vähe mälu, et meil siis on kuidagi tegeleda, noh, 661 00:28:17,580 --> 00:28:19,880 miks mitte lihtsalt vältida asi üldse? 662 00:28:19,880 --> 00:28:26,170 Miks mitte lihtsalt kuulutada kandikud olla kursor sõlme, ergo seotud nimekirja, 663 00:28:26,170 --> 00:28:30,740 ja siis lihtsalt eraldada uusi tippe iga kord Steven vaja sobitada 664 00:28:30,740 --> 00:28:32,400 number paigutatakse andmestruktuur. 665 00:28:32,400 --> 00:28:34,200 >> Nii pilt oleks muuta. 666 00:28:34,200 --> 00:28:38,220 Ta ei kavatse olla nii puhas ja lihtne kui lihtsalt massiivi kolm ints. 667 00:28:38,220 --> 00:28:42,970 Nüüd saab olema viit struktuure ning et struct läheb 668 00:28:42,970 --> 00:28:44,830 on int ja järgmise pointer. 669 00:28:44,830 --> 00:28:47,670 See saab viia läbi, et pointer teise sellise struct et 670 00:28:47,670 --> 00:28:48,600 teise sellise struktuure. 671 00:28:48,600 --> 00:28:50,560 Nii pilt tegelikult natuke segasemaks. 672 00:28:50,560 --> 00:28:52,950 Ja me oleme nooled sidumine kõik koos. 673 00:28:52,950 --> 00:28:55,280 >> Aga see on hea, õige, sest oleme näinud, kuidas seda teha. 674 00:28:55,280 --> 00:28:58,180 Ja kui sa saad mugav rakendamisel midagi seotud 675 00:28:58,180 --> 00:29:01,450 nimekiri, mida sa pead tegema kui sa soovi korral rakendada hash tabel 676 00:29:01,450 --> 00:29:05,120 eraldi Aheldamise p-set 6, saate seda kasutada ehituskivi, või 677 00:29:05,120 --> 00:29:08,870 koostisosa või Scratch rääkima, kord, midagi, et paned, siis 678 00:29:08,870 --> 00:29:12,560 loonud oma puzzle tükk mis saab siis uuesti. 679 00:29:12,560 --> 00:29:17,090 Nii kompromissidega, kuid võimalikke lahendusi et me oleme tegelikult näinud. 680 00:29:17,090 --> 00:29:20,560 >> Nii sageli, sa näed seda iga aasta või kaks, kui Apple releases 681 00:29:20,560 --> 00:29:23,060 midagi uut ja kõik hullud inimesed rivistama väljaspool Apple 682 00:29:23,060 --> 00:29:27,050 poest osta oma marginaalne uuendada riistvara. 683 00:29:27,050 --> 00:29:30,420 Ma ütlen seda, et see on OK, sest Ma olen üks neist inimestest. 684 00:29:30,420 --> 00:29:35,140 Nii et millist andmestruktuuri võib esindada see reaalsus? 685 00:29:35,140 --> 00:29:36,980 >> Noh, ütleme järjekorda, joon. 686 00:29:36,980 --> 00:29:40,270 Nii Briti kutsuksin ta tavaliselt järjekorda niikuinii, nii et see on kena nimi. 687 00:29:40,270 --> 00:29:44,960 Ja need kaks toimingut, mis järjekorras toetab me kutsume Lisa järjekorda 688 00:29:44,960 --> 00:29:48,900 töö ja dequeue operatsiooni mis on sarnased 689 00:29:48,900 --> 00:29:50,120 vaim push ja pop. 690 00:29:50,120 --> 00:29:54,060 See on lihtsalt omamoodi erinev konventsioon, mida me kutsudes neid. 691 00:29:54,060 --> 00:29:57,680 Aga Lisa järjekorda midagi tähendab, lisada või paigaldage see andmestruktuur. 692 00:29:57,680 --> 00:29:59,570 Et dequeue vahendid kustutada. 693 00:29:59,570 --> 00:30:05,170 Aga arvestades, et stack oli LIFO andmed struktuur, järjekord on esimene, 694 00:30:05,170 --> 00:30:06,740 kõigepealt välja andmestruktuur. 695 00:30:06,740 --> 00:30:10,050 >> Kui oled esimene inimene liin, siis esimene inimene saada 696 00:30:10,050 --> 00:30:12,420 kohatu ja osta uus seade. 697 00:30:12,420 --> 00:30:18,070 Kujutage ette, kuidas ärritunud need inimesed oleksid kui Apple asemel kasutatakse korstna jaoks 698 00:30:18,070 --> 00:30:21,250 Näiteks rakendada korjamine üles oma uus mänguasi. 699 00:30:21,250 --> 00:30:24,310 Nii järjekorrad mõtet, kindlasti, ja me ei mõtle igasuguseid 700 00:30:24,310 --> 00:30:27,480 rakendusi, arvatavasti, sest järjekorrad eriti kui sa tahad õiglust. 701 00:30:27,480 --> 00:30:30,040 Niisiis, kuidas võiks siis rakendada neid kui andmestruktuur? 702 00:30:30,040 --> 00:30:33,680 >> Noh, ma teen ettepaneku, et me võiksime vaja teha seda nii. 703 00:30:33,680 --> 00:30:35,225 Nii et ma lähen nüüd on numbrid. 704 00:30:35,225 --> 00:30:38,190 Nii et me hoiame see lihtne ja ei tingimata rääkida nii plaate. 705 00:30:38,190 --> 00:30:40,220 Just numbrid, et inimesed on saanud. 706 00:30:40,220 --> 00:30:43,760 Maht läheb taas määrata inimeste koguarv, mis võib olla 707 00:30:43,760 --> 00:30:46,900 seda joont, kui kolm või mis iganes muu väärtus. 708 00:30:46,900 --> 00:30:50,760 >> Aga pakun, et mul on vaja jälgida mitte ainult nende suuruse 709 00:30:50,760 --> 00:30:52,370 järjekorda, kuidas paljud asjad on seal. 710 00:30:52,370 --> 00:30:56,310 Nii suur on praegune suurus, võimsus on maksimaalne suurus. 711 00:30:56,310 --> 00:30:58,540 Lihtsalt jälle, nomenklatuur kokkuleppeliselt. 712 00:30:58,540 --> 00:31:03,680 Miks ma pean veel int sees of järjekorda jälgida, kes on sisse 713 00:31:03,680 --> 00:31:05,365 ees rida? 714 00:31:05,365 --> 00:31:07,930 715 00:31:07,930 --> 00:31:10,910 Miks ma pean tegema, et see nii on? 716 00:31:10,910 --> 00:31:14,750 717 00:31:14,750 --> 00:31:16,190 >> Noh, kuidas on see pilt muutu? 718 00:31:16,190 --> 00:31:19,280 Ma ilmselt uuesti kõige Selle pildi. 719 00:31:19,280 --> 00:31:21,480 Lubage mul minna ja kustutada, mida on siin. 720 00:31:21,480 --> 00:31:24,580 Me anname seda veidi teine ​​nimi siin. 721 00:31:24,580 --> 00:31:28,930 Olgem vabaneda 17, lähme vabaneda of 9, lähme vabaneda 3. 722 00:31:28,930 --> 00:31:30,410 Ja olgem lisada veel üks asi. 723 00:31:30,410 --> 00:31:34,710 Pakun, et mul on vaja jälgida ees nimekirja, mis on just 724 00:31:34,710 --> 00:31:35,570 saab olema int samuti. 725 00:31:35,570 --> 00:31:36,550 Ja me ei kavatse hoida lihtsa. 726 00:31:36,550 --> 00:31:37,740 No seotud nimekirja nüüd. 727 00:31:37,740 --> 00:31:40,900 >> Me tunnistama, et me ei kavatse Tõstab vastu selle piiri. 728 00:31:40,900 --> 00:31:43,720 Aga mida ma tahan näha juhtub sel ajal? 729 00:31:43,720 --> 00:31:47,240 Seega arvan, et ma minna ja esimene isik kerkib rida ja 730 00:31:47,240 --> 00:31:48,560 see on number 9. 731 00:31:48,560 --> 00:31:49,680 Meil on stress pallid. 732 00:31:49,680 --> 00:31:51,330 Kas ma varastama, ütleme, kaks või kolm inimest? 733 00:31:51,330 --> 00:31:52,690 Üks, kaks, kolm? 734 00:31:52,690 --> 00:31:53,120 Tule üles. 735 00:31:53,120 --> 00:31:56,022 Right eestpoolt, sest teeme seda ühe kiire. 736 00:31:56,022 --> 00:31:59,415 >> Igaühel teist on nüüd olla fan boy joone Apple. 737 00:31:59,415 --> 00:32:03,970 738 00:32:03,970 --> 00:32:06,210 Sa ei saanud Apple riistvara lõpus see küll. 739 00:32:06,210 --> 00:32:06,500 Hea küll. 740 00:32:06,500 --> 00:32:09,430 Nii et sa oled number 9, oled number 17, number 22. 741 00:32:09,430 --> 00:32:12,130 Need on meelevaldne arv, nagu üliõpilane ID või tühi-tähi. 742 00:32:12,130 --> 00:32:14,550 Ja hetk, alustagem alustada lisades asju. 743 00:32:14,550 --> 00:32:16,000 Ja ma joosta juhatuse siin seekord. 744 00:32:16,000 --> 00:32:19,570 >> Nii et kui ma olen vormindatud ees olema - 745 00:32:19,570 --> 00:32:22,380 Ma tegelikult tõesti ei huvita, mida ees on, sest suurus on null. 746 00:32:22,380 --> 00:32:24,480 Nii et see võib ka lihtsalt olema küsimärk. 747 00:32:24,480 --> 00:32:26,170 Need kõik on küsimärke. 748 00:32:26,170 --> 00:32:29,880 Nüüd hakkame tegelikult näha mõningaid inimesed vooder üles poodi. 749 00:32:29,880 --> 00:32:33,320 >> Nii et kui number 9, sa oled esimene, seal juures 05:00, edasi minna ja rivistama, 750 00:32:33,320 --> 00:32:34,210 või õhtul. 751 00:32:34,210 --> 00:32:34,580 OK. 752 00:32:34,580 --> 00:32:35,940 Nüüd 9 on siin. 753 00:32:35,940 --> 00:32:37,940 Nii 9 on ees nimekirja. 754 00:32:37,940 --> 00:32:41,440 Nii et ma lähen edasi minna ja uuendada kui suur see praeguste andmete 755 00:32:41,440 --> 00:32:44,740 struktuur ei ole 0 enam vaid olla 1. 756 00:32:44,740 --> 00:32:47,630 Ma panen 9 juures ees nimekirja. 757 00:32:47,630 --> 00:32:51,020 Lubage mul minna ja vahelduvad ekraanil nii me näeme viimase meid siia. 758 00:32:51,020 --> 00:32:53,220 >> Ja nüüd, mida ma tahan, lauda ees? 759 00:32:53,220 --> 00:32:56,240 Ma lähen, et jälgida, et ees järjekorda kohe 760 00:32:56,240 --> 00:32:58,570 on asukoha 0. 761 00:32:58,570 --> 00:33:00,510 Sest see, mis järgmisena juhtub? 762 00:33:00,510 --> 00:33:03,000 Noh, oletame, nüüd ma Lisa järjekorda 17 samuti. 763 00:33:03,000 --> 00:33:04,510 Nii hop liin seal. 764 00:33:04,510 --> 00:33:07,060 Ja jälle omamoodi uks pood saab olema siin. 765 00:33:07,060 --> 00:33:08,700 Nüüd olen lisanud 17. 766 00:33:08,700 --> 00:33:10,810 Ja kuigi need kutid blokeerimine ekraan, see on OK, 767 00:33:10,810 --> 00:33:12,300 sest me näeme seda siin. 768 00:33:12,300 --> 00:33:12,910 Vabandust. 769 00:33:12,910 --> 00:33:13,810 >> Publik: me saame liikuda - 770 00:33:13,810 --> 00:33:14,660 >> DAVID Malan: Ei, see on OK. 771 00:33:14,660 --> 00:33:16,000 See on suur seal. 772 00:33:16,000 --> 00:33:18,580 Nii 17 on nüüd sees järjekorda. 773 00:33:18,580 --> 00:33:21,332 Mul on vaja uuendada, mis valdkondades nüüd küll? 774 00:33:21,332 --> 00:33:23,210 OK, kindlasti suurus. 775 00:33:23,210 --> 00:33:26,430 Ja kuidas on ees? 776 00:33:26,430 --> 00:33:27,040 OK, ei. 777 00:33:27,040 --> 00:33:30,200 Front ei tohiks muuta, sest erinevalt stack oleme 778 00:33:30,200 --> 00:33:31,370 tahavad säilitada õiglus. 779 00:33:31,370 --> 00:33:35,150 Nii et kui 9 tuli esimene, tahame 9 olla esimene välja rida 780 00:33:35,150 --> 00:33:36,420 ja poodi. 781 00:33:36,420 --> 00:33:37,220 >> Tegelikult, vaatame seda. 782 00:33:37,220 --> 00:33:42,235 Enne kui me sisestada 22, lähme minna ja dequeue 9. 783 00:33:42,235 --> 00:33:42,970 Mis su nimi oligi? 784 00:33:42,970 --> 00:33:43,680 >> Publik: Jake. 785 00:33:43,680 --> 00:33:45,440 >> DAVID Malan: Jake läheb tuleb dequeued nüüd. 786 00:33:45,440 --> 00:33:48,050 Nii saad kõndida poest. 787 00:33:48,050 --> 00:33:49,880 Ja teeselda, et kaupluse on seal. 788 00:33:49,880 --> 00:33:51,970 Nüüd, mida on vaja - dit-dit-dit! 789 00:33:51,970 --> 00:33:53,400 Mis peab juhtuma nüüd? 790 00:33:53,400 --> 00:33:54,490 Design otsus. 791 00:33:54,490 --> 00:33:56,825 Nii ei ole halb instinkt, aga - mis su nimi oligi? 792 00:33:56,825 --> 00:33:57,090 >> Publik: David. 793 00:33:57,090 --> 00:33:57,500 >> DAVID Malan: David. 794 00:33:57,500 --> 00:33:58,810 Mida tegi David teha? 795 00:33:58,810 --> 00:34:02,590 Ta püüdis omamoodi määrata andmed ning viia oma asukohta 796 00:34:02,590 --> 00:34:04,100 arvesse Jake endine asukoht. 797 00:34:04,100 --> 00:34:06,740 Ja see on hea, kui me oleme valmis nõustuda, et kui 798 00:34:06,740 --> 00:34:08,199 rakendamise üksikasjalikud. 799 00:34:08,199 --> 00:34:11,100 Aga kõigepealt, lähme andmeid värskendada struktuur, enne kui me seda teha. 800 00:34:11,100 --> 00:34:14,139 Sest ma ei meeldi idee kõik inimesed suunates seda joont. 801 00:34:14,139 --> 00:34:17,360 >> See ei ole suur asi, kui David see koos üks samm, kuid jällegi mõtlen tagasi 802 00:34:17,360 --> 00:34:20,360 kui meil on olnud kaheksa vabatahtlike etapis ja me oleme teinud nagu sisestamise 803 00:34:20,360 --> 00:34:22,600 sort, kus me pidime alustama liigub kõik ümber. 804 00:34:22,600 --> 00:34:23,790 See sai kallis, eks? 805 00:34:23,790 --> 00:34:28,330 See teeb mind roomama umbes suur O n, suur O n ruudus uuesti. 806 00:34:28,330 --> 00:34:30,650 See ei tunne ideaalne tulemus. 807 00:34:30,650 --> 00:34:32,080 >> Teeme lihtsalt uuendada seda. 808 00:34:32,080 --> 00:34:35,120 Nii suuruse järjekorras ei ole enam 2. 809 00:34:35,120 --> 00:34:37,090 Nüüd on lihtsalt 1. 810 00:34:37,090 --> 00:34:40,360 Aga ma ei saa nüüd uuendama midagi Ma ei uuenda enne, 811 00:34:40,360 --> 00:34:41,130 ees nimekirja. 812 00:34:41,130 --> 00:34:45,420 Ma võiks lihtsalt öelda, on see, et kohale 1? 813 00:34:45,420 --> 00:34:49,770 Nüüd on meil prügi väärtus siin, prügi väärtus siin, ja Taavet 814 00:34:49,770 --> 00:34:51,469 Keset seda prügi. 815 00:34:51,469 --> 00:34:54,980 Aga andmestruktuur on veel puutumata. 816 00:34:54,980 --> 00:34:58,540 >> Ja tegelikult, ma ei pea isegi muuta Jake endine number 817 00:34:58,540 --> 00:35:00,460 9, sest kes hoolib. 818 00:35:00,460 --> 00:35:04,470 Mul on piisavalt teavet praegu suurus, et ma tean, et seal on üks inimene 819 00:35:04,470 --> 00:35:05,030 seda järjekorda. 820 00:35:05,030 --> 00:35:08,340 Ja ma tean, et ta on asukoht 1, mitte 0. 821 00:35:08,340 --> 00:35:09,760 Ma ei lugedes. 822 00:35:09,760 --> 00:35:11,300 Nii 1. kui ka. 823 00:35:11,300 --> 00:35:13,410 Nii andmete struktuur on ikka OK. 824 00:35:13,410 --> 00:35:14,330 >> Noh, mis järgmisena juhtub? 825 00:35:14,330 --> 00:35:15,010 Teeme Lisa järjekorda - 826 00:35:15,010 --> 00:35:15,370 Mis su nimi on? 827 00:35:15,370 --> 00:35:16,160 >> Publik: Callen. 828 00:35:16,160 --> 00:35:16,580 >> DAVID Malan: Callen. 829 00:35:16,580 --> 00:35:20,770 Olgem Lisa järjekorda Callen ja 22 on nüüd järjekorras. 830 00:35:20,770 --> 00:35:22,300 Nüüd mis peab muutuma here? 831 00:35:22,300 --> 00:35:24,380 Front ei kavatse muuta, ilmselt. 832 00:35:24,380 --> 00:35:27,160 Suurus on muutu olema 2 uuesti. 833 00:35:27,160 --> 00:35:31,590 Ja 22 jõuab siia, 9 on endiselt olemas, aga see on tegelikult 834 00:35:31,590 --> 00:35:32,600 prügi raha nüüd. 835 00:35:32,600 --> 00:35:35,910 See on lihtsalt jäänuk Jake minevikust. 836 00:35:35,910 --> 00:35:39,200 >> Nüüd mis juhtub, kui Ma dequeue David? 837 00:35:39,200 --> 00:35:41,560 Üks viimase operatsiooni dequeue David. 838 00:35:41,560 --> 00:35:46,070 Me võiks liikuda, kuid pakun olgem teha nii vähe tööd kui võimalik. 839 00:35:46,070 --> 00:35:50,280 Nüüd minu andmestruktuur läheb tagasi suurus 2-1. 840 00:35:50,280 --> 00:35:53,730 Aga ees järjekorras nüüd saab 2. 841 00:35:53,730 --> 00:35:56,640 Mul ei ole vaja muuta need numbrid lihtsalt veel, sest nad on 842 00:35:56,640 --> 00:35:58,230 lihtsalt prügi väärtused. 843 00:35:58,230 --> 00:35:59,720 >> Aga nüüd, mis juhtub? 844 00:35:59,720 --> 00:36:03,280 Oletame I Lisa järjekorda ise, 26? 845 00:36:03,280 --> 00:36:05,890 Ma tunnen, et ma kuulun siia. 846 00:36:05,890 --> 00:36:06,890 Nii et ma olen seda enqueued. 847 00:36:06,890 --> 00:36:08,760 Nii et ma mingi kuulu siia. 848 00:36:08,760 --> 00:36:11,300 Ja kuigi sa ei ole päris hindan seda visuaalselt laval, 849 00:36:11,300 --> 00:36:15,075 sest meil on piisavalt ruumi, et ma peaksin ei seisaks siin, siis miks? 850 00:36:15,075 --> 00:36:16,290 >> Publik: Sa oled audis. 851 00:36:16,290 --> 00:36:16,370 >> DAVID Malan: Õigus. 852 00:36:16,370 --> 00:36:16,940 Ma olen audis. 853 00:36:16,940 --> 00:36:19,330 Olen indekseeritud kaugemale piire see massiiv. 854 00:36:19,330 --> 00:36:23,420 Ma tõesti peaks olema üks kolm võimalikku asukohta. 855 00:36:23,420 --> 00:36:25,150 Nüüd, kus on kõige loomulikum minna? 856 00:36:25,150 --> 00:36:27,760 Teen ettepaneku võimendatud nädal üks trikk. 857 00:36:27,760 --> 00:36:30,150 Mod operaatori protsent. 858 00:36:30,150 --> 00:36:36,850 Sest ma tehniliselt seisvat asukoht 3, aga ma 3 mod võimsus, 859 00:36:36,850 --> 00:36:40,250 nii 3 protsenti märk, 3 - 860 00:36:40,250 --> 00:36:40,970 võimsus on 3. 861 00:36:40,970 --> 00:36:41,720 Mis see on? 862 00:36:41,720 --> 00:36:43,700 Mis on ülejäänud kui sa jagad 3 3? 863 00:36:43,700 --> 00:36:44,070 0. 864 00:36:44,070 --> 00:36:48,140 >> Nii et paneb mind olid Jake oli, mis on tegelikult hea. 865 00:36:48,140 --> 00:36:50,370 Nüüd rakendamise see asi läheb 866 00:36:50,370 --> 00:36:51,250 olla natuke peavalu. 867 00:36:51,250 --> 00:36:53,740 See on tõesti lihtsalt üks rida peavalu, koodi. 868 00:36:53,740 --> 00:36:56,580 Aga vähemalt nüüd on prügi väärtus siin, kuid seal on kaks 869 00:36:56,580 --> 00:36:57,910 õigustatud ints siin. 870 00:36:57,910 --> 00:37:04,160 Ja ma väita, et nüüd me oleme teinud täpselt, mida me peame tegema nii kaua, kui 871 00:37:04,160 --> 00:37:08,600 me muuta seda, mis Jake väärtus pidi olema 26. 872 00:37:08,600 --> 00:37:12,110 >> Nüüd on meil piisavalt informatsiooni veel säilitada terviklikkuse 873 00:37:12,110 --> 00:37:13,060 Selliste andmete struktuuri. 874 00:37:13,060 --> 00:37:17,160 Me oleme ikka veel sellist õnne, kui me soovite lisada neli või rohkem kokku 875 00:37:17,160 --> 00:37:20,740 elemente, kuid võin vähemalt teha päris tõhus kasutamine see pidev 876 00:37:20,740 --> 00:37:21,740 aeg, tegelikult. 877 00:37:21,740 --> 00:37:27,150 Ma ei pea muretsema, suunates igaüks, kui Taaveti kalle oli. 878 00:37:27,150 --> 00:37:30,816 >> Kõik küsimused on korstnad, või see järjekord? 879 00:37:30,816 --> 00:37:32,184 >> Publik: on põhjus, miks pead suurus, et sa tead 880 00:37:32,184 --> 00:37:34,010 kus on inimene? 881 00:37:34,010 --> 00:37:34,770 >> DAVID Malan: Täpselt. 882 00:37:34,770 --> 00:37:38,230 Ma pean teadma, suurusest massiivist sest mul on vaja teada, kuidas täpselt 883 00:37:38,230 --> 00:37:41,940 paljud need väärtused on õigustatud, ja nii, et ma ei leia, kuhu panna 884 00:37:41,940 --> 00:37:42,800 järgmisele inimesele. 885 00:37:42,800 --> 00:37:43,300 Täpselt. 886 00:37:43,300 --> 00:37:44,580 Suurus - 887 00:37:44,580 --> 00:37:46,360 tegelikult, me ei uuenda seda veel. 888 00:37:46,360 --> 00:37:48,380 Lisasin ennast kell 26. 889 00:37:48,380 --> 00:37:51,760 Suurus on nüüd, mitte 1, vaid 2. 890 00:37:51,760 --> 00:37:57,780 Nüüd see tõesti aitab mul leida eesotsas nimekirja, mis ei ole 0, ei 891 00:37:57,780 --> 00:37:59,250 1, kuid on 2. 892 00:37:59,250 --> 00:38:01,665 Ees nimekiri on tõesti number 22. 893 00:38:01,665 --> 00:38:05,120 Kuna ta tuli esimene, nii et ta peaks lubatakse poodi enne mind, 894 00:38:05,120 --> 00:38:08,780 kuigi visuaalselt Ma seisan lähemale poest. 895 00:38:08,780 --> 00:38:09,220 >> Olgu? 896 00:38:09,220 --> 00:38:12,410 Aplausi need kutid ja me anname neid välja sealt. 897 00:38:12,410 --> 00:38:17,090 >> [APLAUS] 898 00:38:17,090 --> 00:38:18,150 >> DAVID Malan: ma võiks lasta hoiate salve. 899 00:38:18,150 --> 00:38:20,760 Võiksime vaadata, mis juhtub siis, kui sa tahad, aga võib-olla mitte. 900 00:38:20,760 --> 00:38:21,590 Hea küll. 901 00:38:21,590 --> 00:38:25,380 Mis siis nüüd ei, mis jätavad meid? 902 00:38:25,380 --> 00:38:28,900 Noh, las ma ettepaneku, et seal on mõned muud andmestruktuurid võiksime 903 00:38:28,900 --> 00:38:33,810 alustada lisades meie tööriistakomplekt, mis tegelikult olla üsna, üsna oluline, sest 904 00:38:33,810 --> 00:38:35,270 me sukelduda web kraam. 905 00:38:35,270 --> 00:38:38,150 Mis jällegi on mingi seos et puude kujul 906 00:38:38,150 --> 00:38:40,550 midagi, mida nimetatakse DOM, dokument objekti mudeli. 907 00:38:40,550 --> 00:38:42,370 Aga me näeme rohkem et enne pikk. 908 00:38:42,370 --> 00:38:46,260 >> Lubage mul pakkuda definitionally et me kutsuvad puu nüüd, mida sa võiksid teada, kui 909 00:38:46,260 --> 00:38:48,820 rohkem sugupuu, kuhu mõned esivanem juures 910 00:38:48,820 --> 00:38:49,790 puu juurtele. 911 00:38:49,790 --> 00:38:54,480 Patriarhaalne või matriarh juures väga tipus. 912 00:38:54,480 --> 00:38:56,700 Ilma oma abikaasa, käesoleval juhul. 913 00:38:56,700 --> 00:39:00,940 Aga meil on nüüd see, mida me kutsume lapsed, kes on sõlmed, et riputada 914 00:39:00,940 --> 00:39:05,480 ära vasaku lapse või paremale laps, nooled on kujutatud siin. 915 00:39:05,480 --> 00:39:10,490 >> Teisisõnu, on puu andmestruktuur arvuti, puu on null 916 00:39:10,490 --> 00:39:11,480 või rohkem tippe. 917 00:39:11,480 --> 00:39:13,500 Kui see on vähemalt üks sõlm, seda nimetatakse root. 918 00:39:13,500 --> 00:39:15,700 On asju visuaalselt, et juhime ülaosas. 919 00:39:15,700 --> 00:39:20,280 Ja et sõlm, nagu mis tahes muu sõlme, saab on null, üks või kaks või kolm, 920 00:39:20,280 --> 00:39:23,600 või siiski palju lapsi andmestruktuur toetab. 921 00:39:23,600 --> 00:39:29,150 Sel juhul root, säilitades väärtus üks, on kaks last, 2 ja 3, 922 00:39:29,150 --> 00:39:33,020 nii me tavaliselt nimetame 2 vasakul laps ja 3 õigus laps. 923 00:39:33,020 --> 00:39:36,940 >> Ja siis, kui me alla 5, 6, ja 7, 6 võib nimetada keskel laps. 924 00:39:36,940 --> 00:39:38,940 Kui teil on neli last, ta saab segane. 925 00:39:38,940 --> 00:39:42,260 Nii et me lõpetada selline otsetee suuliselt. 926 00:39:42,260 --> 00:39:44,580 Aga see on tõesti ainult sugupuu. 927 00:39:44,580 --> 00:39:48,880 Ja lehed on siin sõlmede et ise ei ole lapsi. 928 00:39:48,880 --> 00:39:52,540 Nad riputada off põhja puu. 929 00:39:52,540 --> 00:39:56,940 >> Niisiis, kuidas võiks siis rakendada puu on ainult kaks last maksimaalselt? 930 00:39:56,940 --> 00:39:58,410 Me nimetame seda kahendpuu. 931 00:39:58,410 --> 00:40:00,960 Bi jälle tähendab kaks sellega juhul, nagu binaarse. 932 00:40:00,960 --> 00:40:04,830 Ja nii see võib olla null, üks, või kaks last maksimaalselt. 933 00:40:04,830 --> 00:40:08,650 >> Ma ettepaneku, et me rakendada sõlme selle struktuuri int n, 934 00:40:08,650 --> 00:40:11,910 ja siis kaks suunanäitajaks, üks nn vasakule, üks nn õige. 935 00:40:11,910 --> 00:40:14,830 Aga need on vaid kena suvalise konventsioonidega. 936 00:40:14,830 --> 00:40:18,170 Ja mis kena nüüd, eriti kui teil liiki võidelnud kontseptuaalselt koos 937 00:40:18,170 --> 00:40:21,300 rekursioon, või arvatakse, et see ei olnud tõesti lahendus midagi, 938 00:40:21,300 --> 00:40:23,120 eriti kui sa saaksid otsa mälu. 939 00:40:23,120 --> 00:40:26,600 Nüüd, kui me räägime andmed struktuure ja algoritme, mis võimaldavad 940 00:40:26,600 --> 00:40:31,030 meil läbida ja manipuleerida neid, Selgub, et rekursioon tuleb tagasi 941 00:40:31,030 --> 00:40:34,240 palju ahvatlevamaks kui mitte ilus viis. 942 00:40:34,240 --> 00:40:38,670 >> Nii et see pakun on rakendamise of Search funktsiooni. 943 00:40:38,670 --> 00:40:39,870 Arvestades kahe sisendi - 944 00:40:39,870 --> 00:40:41,570 seega mõtle seda kui musta kasti. 945 00:40:41,570 --> 00:40:46,560 Arvestades kahe sisendi, n, int, ja kursor puu pointer 946 00:40:46,560 --> 00:40:50,020 sõlme, või tõesti puu juurt, I väide, et seda funktsiooni saab tagasi 947 00:40:50,020 --> 00:40:53,530 õige või vale, et väärtus n on sees seda puud. 948 00:40:53,530 --> 00:40:55,210 >> Mis seal sees on selle musta kasti? 949 00:40:55,210 --> 00:40:57,440 Noh, neli haru. 950 00:40:57,440 --> 00:40:58,385 Esimene lihtsalt kontrollib. 951 00:40:58,385 --> 00:41:00,490 Kui puu on null, siis tagastab false. 952 00:41:00,490 --> 00:41:04,580 Kui seal ei ole sõlme, pole n, pole number, vaid tagastab false. 953 00:41:04,580 --> 00:41:12,330 Kui aga n, väärtus, mida otsid eest, on vähem kui puu nool n ja 954 00:41:12,330 --> 00:41:15,180 lihtsalt olla kindel, mida see tähendab, kui Ma kirjutan puu ja siis nool 955 00:41:15,180 --> 00:41:18,150 märke, n? 956 00:41:18,150 --> 00:41:18,690 Täpselt. 957 00:41:18,690 --> 00:41:21,970 See tähendab dereference et pointer nimega puu. 958 00:41:21,970 --> 00:41:26,750 Minge sinna ja siis saad sisse selle sõlm ja saada oma ala nimetatakse n. 959 00:41:26,750 --> 00:41:30,810 Ja siis võrrelda tegelikke n, mis oli läks Otsi selle vastu. 960 00:41:30,810 --> 00:41:35,390 >> Nii et kui n on väiksem n väärtus puus tipu ennast hästi, 961 00:41:35,390 --> 00:41:36,720 Mida see tähendab? 962 00:41:36,720 --> 00:41:40,690 See tähendab, et midagi esimesel pilgul. 963 00:41:40,690 --> 00:41:40,900 Õigus? 964 00:41:40,900 --> 00:41:45,560 Just nagu siis, kui sul on array väärtused, et teile soovida kohaldada binaarne 965 00:41:45,560 --> 00:41:48,290 otsida nii vormis lõhe ja vallutada. 966 00:41:48,290 --> 00:41:51,790 Aga milline oletus ei peame jaoks binaarne otsing tööd üldse 967 00:41:51,790 --> 00:41:54,510 aastal telefoniraamatust ja varasemaid näiteid? 968 00:41:54,510 --> 00:41:55,530 >> Kuidas sorteerida. 969 00:41:55,530 --> 00:41:59,490 Niisiis olgem täpsustada mõiste puu siin ei oleks lihtsalt puu, mis võib 970 00:41:59,490 --> 00:42:00,880 mingit laste arvu. 971 00:42:00,880 --> 00:42:04,700 Mitte ainult kahendpuu, mis võib on 0, 1 või 2 maksimaalselt. 972 00:42:04,700 --> 00:42:09,700 Aga kui Kahendotsingupuu või BST mis on lihtsalt fancy viis öelda 973 00:42:09,700 --> 00:42:15,430 kahendpuu nii, et iga sõlme vasak laps, kui seda esineb, on 974 00:42:15,430 --> 00:42:16,830 vähem kui sõlme. 975 00:42:16,830 --> 00:42:20,170 Ja iga sõlme õigust lapse kui seda esineb, on suurem 976 00:42:20,170 --> 00:42:21,740 kui sõlm ise. 977 00:42:21,740 --> 00:42:25,200 >> Nii teisisõnu, kui sa olid juhtida puu välja kõik numbrid on 978 00:42:25,200 --> 00:42:30,620 hoolikalt tasakaalustada niimoodi, et kui teil on 55 root, 33 minna 979 00:42:30,620 --> 00:42:33,090 oma vasakule, sest see on vähem kui 55. 980 00:42:33,090 --> 00:42:36,430 77 võib minna selle õige, sest see on suurem kui 55. 981 00:42:36,430 --> 00:42:40,750 Aga nüüd teate, sama määratlust, see on rekursiivne definitsioon verbaalselt, 982 00:42:40,750 --> 00:42:42,600 taotlema 33. 983 00:42:42,600 --> 00:42:47,610 33 vasak laps peab olema väiksem kui see, ja 33 õigus laps, 44, peab olema 984 00:42:47,610 --> 00:42:48,580 suurem kui see. 985 00:42:48,580 --> 00:42:51,670 >> Nii et see on Kahendotsingupuu ja Pakun, kasutades natuke 986 00:42:51,670 --> 00:42:53,910 rekursioon, saame nüüd leida n. 987 00:42:53,910 --> 00:42:59,160 Nii et kui n on väiksem kui väärtus n, mis on aktiivse sõlme, ma lähen 988 00:42:59,160 --> 00:43:04,090 käia ja punt niiöelda, ja lihtsalt tagasi iganes vastus on 989 00:43:04,090 --> 00:43:08,470 otsides n kohta puu vasakule laps. 990 00:43:08,470 --> 00:43:11,370 Teade jälle see funktsioon lihtsalt loodab sõlme star, 991 00:43:11,370 --> 00:43:12,780 kursor sõlme. 992 00:43:12,780 --> 00:43:17,360 Seega kindlasti ma ei saa lihtsalt teha puu nool vasakule, mis viib 993 00:43:17,360 --> 00:43:18,400 mind teise sõlme. 994 00:43:18,400 --> 00:43:19,480 Aga mis on see, et sõlm? 995 00:43:19,480 --> 00:43:22,820 >> Noh, vastavalt käesoleva deklaratsiooniga, Vasakul on lihtsalt kursor, nii et lihtsalt 996 00:43:22,820 --> 00:43:27,090 tähendab, et ma panen selle otsingu funktsiooni erinevad pointer, nimelt 997 00:43:27,090 --> 00:43:30,750 üks, mis tähistab mu vasak lapse puu. 998 00:43:30,750 --> 00:43:36,040 Nii et sel juhul kursorit 33, kui see on meie proovi sisend Vahepeal kui 999 00:43:36,040 --> 00:43:40,740 n on suurem kui väärtus n aasta aktiivse sõlme puu, siis ma olen 1000 00:43:40,740 --> 00:43:43,370 läheb minna ja punt teistes suunas ja lihtsalt öelda, ma ei 1001 00:43:43,370 --> 00:43:47,280 tea, kas see väärtus n on puus, kuid ma tean, et see on, see on ette minu 1002 00:43:47,280 --> 00:43:49,090 õige haru, nii rääkida. 1003 00:43:49,090 --> 00:43:53,120 Nii et lubage mul kõne rekursiivselt otsida, kulgeb n uuesti, kuid kulgeb 1004 00:43:53,120 --> 00:43:54,580 kursor minu õigus laps. 1005 00:43:54,580 --> 00:44:00,020 >> Teisisõnu, kui ma olen praegu 55 ja ma otsin 99, ma tean, et 99 1006 00:44:00,020 --> 00:44:04,270 on suurem kui 55, nii nagu ma rebis telefoniraamatust nädalat tagasi ja me 1007 00:44:04,270 --> 00:44:07,140 läks otse, samamoodi on meil lähen siin. 1008 00:44:07,140 --> 00:44:11,960 Ja ma ei tea, kas see on minu õigus laps, ja see ei ole, 77 on olemas, kuid 1009 00:44:11,960 --> 00:44:13,210 Ma tean, et see on selles suunas. 1010 00:44:13,210 --> 00:44:18,770 Nii et ma kutsun otsing minu õige laps, 77, ja lase otsing joonis välja 1011 00:44:18,770 --> 00:44:24,950 seal kui 99 selles meelevaldne Näiteks on tegelikult olemas. 1012 00:44:24,950 --> 00:44:26,900 >> Else, mis on viimane juhtum? 1013 00:44:26,900 --> 00:44:28,620 Kui puu on null on ühel juhul. 1014 00:44:28,620 --> 00:44:31,890 Kui n on väiksem kui praegune sõlme väärtus on teise puhul. 1015 00:44:31,890 --> 00:44:35,120 Kui n on suurem kui praegune node väärtus on olemas ka kolmas. 1016 00:44:35,120 --> 00:44:38,250 Mis on neljas ja viimane juhtum? 1017 00:44:38,250 --> 00:44:39,480 Arvan, et oleme välja juhul, eks? 1018 00:44:39,480 --> 00:44:44,690 See peab olema, et n on aktiivse sõlme, et ma olen. 1019 00:44:44,690 --> 00:44:49,640 >> Nii et kui ma olen otsivad 55 selles punktis lugu, et filiaal 1020 00:44:49,640 --> 00:44:51,780 puu Jõutakse tõsi. 1021 00:44:51,780 --> 00:44:55,380 Mis on huvitav on see, et me tegelikult erinevalt nädalat varem, oleme lahke 1022 00:44:55,380 --> 00:44:56,740 kohta on kaks baasi juhtudel. 1023 00:44:56,740 --> 00:44:58,300 Ja nad ei pea olema kõik ülaosas. 1024 00:44:58,300 --> 00:45:01,390 Top on aluspõhimõtted, sest kui Puu on null, pole midagi teha. 1025 00:45:01,390 --> 00:45:03,410 Lihtsalt tagasi kõva kodeeritud väärtuse false. 1026 00:45:03,410 --> 00:45:07,400 >> Alumine haru on omamoodi default, kusjuures kui oleme kontrollinud 1027 00:45:07,400 --> 00:45:11,550 null, me kontrollida, kas see peaks olema jäänud, kuid see ei peaks olema, oleme 1028 00:45:11,550 --> 00:45:14,640 kontrollida, kas see peaks olema õige, kuid see ei tohiks olla, kindlasti peab see olema 1029 00:45:14,640 --> 00:45:15,870 õigus, kus me oleme. 1030 00:45:15,870 --> 00:45:16,780 See on tugipunkt. 1031 00:45:16,780 --> 00:45:19,920 Nii et seal on kaks rekursiivne juhtudel asuvast seal keskel. 1032 00:45:19,920 --> 00:45:21,630 Aga ma oleks kirjutanud see mis tahes järjekorras. 1033 00:45:21,630 --> 00:45:24,520 Ma lihtsalt arvasin, et see omamoodi tunda loomulik kõigepealt kontrollida võimalik viga, 1034 00:45:24,520 --> 00:45:28,340 siis vaadake vasakule, siis vaadake paremale, seejärel eeldada, et sa oled sõlme 1035 00:45:28,340 --> 00:45:30,630 sa oled tegelikult otsivad. 1036 00:45:30,630 --> 00:45:36,240 >> Miks võib see olla kasulik? 1037 00:45:36,240 --> 00:45:37,910 Nii selgub - 1038 00:45:37,910 --> 00:45:42,110 ja andke mulle hüpata teaser siin see on veebis. 1039 00:45:42,110 --> 00:45:44,920 Me läheme hakata ei programmeerimiskeel alguses, kuid 1040 00:45:44,920 --> 00:45:46,030 märgistuskeel. 1041 00:45:46,030 --> 00:45:48,740 Märgistuskeel on üks, mis on sarnase sisuga programmeerimine 1042 00:45:48,740 --> 00:45:51,715 keel, kuid see ei anna teile suutlikkus väljendada ennast loogiliselt. 1043 00:45:51,715 --> 00:45:55,070 See ainult annab teile võime ennast väljendada struktuuriga. 1044 00:45:55,070 --> 00:45:57,960 >> Kui sa tahad lisada midagi lehel veebilehele? 1045 00:45:57,960 --> 00:45:59,200 Mis värvi sa tahad teha? 1046 00:45:59,200 --> 00:46:00,950 Mida kirjasuuruse sa tahad teha? 1047 00:46:00,950 --> 00:46:02,970 Mis sõnu sa tegelikult tahan veebilehelt? 1048 00:46:02,970 --> 00:46:04,060 Nii et märgistuskeel. 1049 00:46:04,060 --> 00:46:07,690 Aga siis me väga kiiresti kasutusele JavaScript, mis on täieõiguslik 1050 00:46:07,690 --> 00:46:08,560 programmeerimiskeelt. 1051 00:46:08,560 --> 00:46:12,530 Väga sarnane süntaktiliselt välimusega Lisa C, kuid see saab olema mõned 1052 00:46:12,530 --> 00:46:15,200 kena, võimsam, rohkem kasutajasõbralikud omadused. 1053 00:46:15,200 --> 00:46:18,050 >> Ja üks pettumusi selles mõtet semester on see, et paneme 1054 00:46:18,050 --> 00:46:22,065 kiiresti rakendada veerija palju vähem rida koodi kasutades teistes keeltes 1055 00:46:22,065 --> 00:46:25,580 kui C ise lubab, kuid põhjus on me varsti aru. 1056 00:46:25,580 --> 00:46:27,750 See on esimene selline veebileht. 1057 00:46:27,750 --> 00:46:30,120 See on täiesti underwhelming, Esimene teeme. 1058 00:46:30,120 --> 00:46:31,400 See lihtsalt tähendab, tere. 1059 00:46:31,400 --> 00:46:34,010 Aga kui sa oled kunagi näinud seda enne, see on HTML, 1060 00:46:34,010 --> 00:46:35,670 Hypertext Markup Language. 1061 00:46:35,670 --> 00:46:39,310 >> Kui te lähete teatud menüü valik Kõige iga brauseriga, mis tahes veebilehe 1062 00:46:39,310 --> 00:46:43,160 internet, näete HTML et mõned inimesed kirjutasid 1063 00:46:43,160 --> 00:46:44,400 luua, et veebilehel. 1064 00:46:44,400 --> 00:46:47,850 Ja see ilmselt ei ole nii lühike või kui puhas nagu see. 1065 00:46:47,850 --> 00:46:51,400 Aga ta jälgib muster neist lahtised sulud ja kaldkriipsud ja 1066 00:46:51,400 --> 00:46:53,660 kirjad ja potentsiaalselt numbrid. 1067 00:46:53,660 --> 00:46:56,770 >> Ma arvasin, et sulle teaser mida saate teha 1068 00:46:56,770 --> 00:46:57,950 pärast pildistamist CS50. 1069 00:46:57,950 --> 00:47:02,620 Lubage mul minna cs.harvard.edu / Rob, meie enda Rob Bowden kodulehelt. 1070 00:47:02,620 --> 00:47:06,080 Ta tegi seda meie eest. 1071 00:47:06,080 --> 00:47:07,490 Nii saate kohe võimalik teha. 1072 00:47:07,490 --> 00:47:10,660 Ja ka see, mida te olete kuulnud täna hommikul - 1073 00:47:10,660 --> 00:47:12,480 mida te olete kuulnud täna hommikul - 1074 00:47:12,480 --> 00:47:13,780 >> [HAMSTER TANTSUMUUSIKAT] 1075 00:47:13,780 --> 00:47:15,702 >> - You'Ll teha seda. 1076 00:47:15,702 --> 00:47:16,790 See ootab meid kolmapäeval. 1077 00:47:16,790 --> 00:47:17,791 Näeme siis. 1078 00:47:17,791 --> 00:47:22,950 >> [HAMSTER TANTSUMUUSIKAT] 1079 00:47:22,950 --> 00:47:24,300 DAVID Malan: Järgmisel CS50 - 1080 00:47:24,300 --> 00:47:31,670