Davidas Malan: Gerai. Sveiki sugrįžę į CS50. Tai yra 8 savaitės pradžia. Ir priminti, kad problema rinkinys 5 baigėsi su šiek tiek iššūkis. Taigi, jei jūs atsigavo Visi jūsų mokymo draugijų ir CA nuotraukos į card.raw failą, jūs turite teisę iki dabar rasti visus tuos žmones, ir vienas laimingasis nugalėtojas bus eiti namo su vienu iš šių dalykų, šuolis judesio prietaisas, galite naudoti galutinis projektai, pavyzdžiui. 

Tai kiekvienais metais veda prie iš creepiness tiek. Ir taip, ką aš maniau aš padaryti, tai dalis su jumis kai kurių pastabų, kurios dingo pirmyn ir atgal per Darbuotojų sąrašas vėlai. Pavyzdžiui, praeitą naktį, citata kabutės, viena iš darbuotojų prisijungę: "Aš tiesiog turėjo studento trankyti mano duris imtis su manimi nuotrauką. Medžiotojai, aš pasakysiu. "Pradėtas išjungti gana aprašomasis ir tada mes persikėlė į, valandą arba tiek vėliau, "Aš turėjau studentas manęs laukia po skyriuje ir jis turėjo visas mūsų vardus ir nuotraukas kai popieriaus lapų. "Gerai. Organizuojamas taip, bet ne visa tai Creepy dar. 

Tada "Aš buvau iš miesto Šį savaitgalį, ir kai aš gavau atgal, ten buvo vienas mano miegamasis. "[Juokas] Davidas Malan: Kitas citata iš darbuotojų narys, "studentas atėjo į mano namus Somerville ne 4:00 šį rytą. "Kitas darbuotojai, "Aš turiu mano viešbučiuose Francisco studentas laukia man ne su trijų DSLR fojė. " Tipas fotoaparatu. "Aš nesu net personalui šį semestrą, bet studentas įsiveržė į mano namus tai ryte ir įrašė visą dalykas Google stiklo. "Ir tada galiausiai, "Ne mažiau kaip 12 žmonių buvo nekantriai laukia manęs, kai aš gavau iš mano Limuzinų, ir tada aš prabudau. "Gerai. Taigi tarp nuotraukomis, kaip jūs galite pamenu, yra šitas čia kas jūs Galbūt žinote, kaip Milo Banana, kuris gyvena su Lauren Carvalho, mūsų galvos mokymo bendradarbis. Milo, Milo, čia berniukas. Milo. Milo. Žinai, jis dėvi Google Stiklas, todėl mes jums parodysime, visa tai po to. Taigi tai yra Milo jei norite imtis nuotrauką su juo vėliau. Jei norite atkreipti dėmesį į auditoriją ten. Gerai. Tai gerai filmuota medžiaga. Na, Milo bananų. O, nedaryk to. 

[Juokas] 

Gerai. Taigi žodžio tada kas laukia, nes, kaip mes pradėti perėjimo Šią savaitę Konkrečiau, nuo C komandinės eilutės aplinka PHP ir "JavaScript" ir "SQL ir HTML ir CSS internetinė aplinka, mes būsime įrengti jums visiems daugiau žinios galimus galutinius projektus. Link šio tikslo, kursas turi tradicija rengti seminarus, kurie yra tangentinių pranešimus į kursą. Labai glaudžiai susijęs su programavimą ir app plėtra ir tt, bet nebūtinai tyrinėję Kursas savo programa. 

Taigi, jei jums gali būti domina vienas ar daugiau Šių metų seminarų, užsiregistruoti cs50.net/seminar. Yra vyresni seminarai ne cs50.net/seminars. Ir į registrą iki šiol šiais metais yra nuostabi Web Apps su Ruby on Bėgiai, kuris yra alternatyva kalba PHP. Kompiuterinė lingvistika. Įvadas į iOS, kuris yra platforma, kuri naudojama "iPhone" ir "iPad plėtra. "JavaScript" Web Apps ", mes padengti kad, bet šiame seminare, jums eiti į išsamiau. 

Keliamieji Pasiūlymas, todėl mes iš tikrųjų turi tam tikrų mūsų draugais iš Leap Motion, Pati įmonė prisijungti prie mūsų. Rytoj, tiesą sakant, teikti rankas dėl seminaro, jei Jus sudominti. Meteor.js, alternatyvus būdas naudojant "JavaScript" ne naršyklėje, bet serveryje. Node.js, kuris yra labai toje veną taip pat. Elegantiškas "Android" dizainas. "Android" yra labai populiari alternatyva iOS ir Windows Phone ir kiti mobiliosios platformos. Ir interneto saugumo aktyvios gynybos. 

Taigi, iš tiesų, jei norite įsitraukti į tai, leiskite man atkreipkite dėmesį į tai. Mes labai laimingas, galėdamas pasakyti, kad mūsų draugai šuolis Pasiūlymas, kuris yra paleidimo - šis prietaisas tikrai tik atėjo iš prieš kelis mėnesius - buvo maloningai paaukojo 30 tokius prietaisus su kuo daugiau moksleivių klasę, jei norite skolintis įranga link semestro pabaigos ir ją naudoti faktinis galutinis projektas. Jie paremti keliomis kalbomis. Nė vienas iš jų C, nė vienas iš jų PHP, todėl pasiekti vieną arba daugiau iš šių seminarų gali pasirodyti naudinga. Ir visi jie bus filmuojamas renginys, jūs negalite dalyvauti asmeniškai. Tvarkaraštis bus paskelbtas per rašykite kaip mes sukietėti kambariai. 

Ir galiausiai, jei jūs einate į projects.cs.50.net, tai svetainė mes išlaikyti kasmet, kad mes kviečiame žmonės iš Bendrijos, fakulteto, departamentai, personalo, ir abu darant CS50 į išorę pasiūlyti projekto idėjas. Ką interesų į studentų grupių. Ką interesų departamentams. Taigi nereikia pasukti ten, jei esate kovoja netikrumo, ką jūs savarankiškai norėtumėte spręsti. 

Taigi, paskutinį kartą pristatėme tikriausiai daugiau sudėtingų duomenų struktūra, nei mes norime matyti savaites praeityje. Mes norime naudoju matricos gana laimingai naudinga, jei paprasta duomenų struktūra. Tada mes pristatėme tai, kuris Žinoma, yra susiję sąrašus. Ir kas buvo viena iš motyvacijos įvedant šią duomenų struktūrą? Taip? Kas tai? 

PUBLIKA: Dinaminis dydis. 

Davidas Malan: Dinaminis dydis. Taigi, o masyvas, jūs turite sužinoti savo dydį iš anksto, kai Jums skirti jį. Susijusiame sąrašą, nereikia turite žinoti, kad. Jūs galite tiesiog malloc, arba apskritai, skirti papildomą mazgas, taip sakant, bet kuriuo metu galite norite įterpti daugiau duomenų. Ir mazgas yra iš anksto nustatytas prasmę. Tai tiesiog bendrinis terminas, apibūdinantis kai konteinerio natūra, kad mes naudojant mūsų duomenų struktūros laikyti kai palūkanų elementą, kuris šiuo atveju atsitiktų būti sveikasis skaičius. 

Bet visada kompromisas. Taigi mes dinaminius dydžių duomenų struktūra, bet kokia kaina mes mokėti? Kas sujungtų sąrašų neigiama? Taip? 

Auditorija: reikia daugiau atminties. 

Davidas Malan: Jis reikalauja daugiau atmintis, kaip tiksliai? 

Auditorija: [nesigirdi]. 

Davidas Malan: Būtent. Taigi dabar mes turime patarimų pradėjimo papildoma atmintis, kad mes anksčiau nereikėjo, nes privalumas masyvo, žinoma, yra tai, kad viskas greta, atgal atgal į nugaros, kuri suteikia jums laisvą prieigą. Nes tik naudojant kvadratinės laikiklis žymėjimas, ar daugiau techniškai rodyklė aritmetika, labai paprastas papildymas, galite prieiti prie bet elementai nuolat laiko. Ir iš tiesų, tai tipo užuomina kita kaina, kurią mokame su susijęs sąrašą. 

Kas atsitinka su važiavimo metu kažkas panašaus Paieška, jei noriu radote vertę ir viduje Susietos sąraše? Ką mano važiavimo laikas tapti? Didelės O n. Jei jis surūšiuoti? Ką daryti, jei duomenų struktūra manimi rūšiuoti? Ar galiu padaryti geriau nei didelis O n ieškoti? Ne, nes blogiausiu atveju ji gali labai gerai būti rūšiuojami, bet skaičius jūs ieškote gali būti didelis. Tai gali būti numeris 100, kuris gali atsitikti, kad visi pabaigoje būdas. Ir todėl jums gali prieiti tik prie Tinkliniai sąrašas šio įgyvendinimo būdas pirmojo mazgo, jūs dar tipo nesiseka. Jūs turite išanalizuoti visą dalykas nuo pradžios iki pat pabaigos, siekiant rasti kad didelę vertę kaip 100. Arba nustatyti, jei tai net ten. 

Taigi, mes galime daryti tai, ką algoritmas į duomenų struktūra, kuri atrodo taip? Mes negalime daryti dvejetainis paieškos, nes dvejetainis paieškos reikalaujama, kad mes turėjome laisvosios kreipties. Mes galime tik šuolis iš vietos į Vieta nereikia sekti šios duonos trupinius į formą visų šių patarimų. 

Dabar, kaip mes įgyvendinti šį? Na, jei mes einame į ekraną čia, jeigu mes galime greitai reimplement šiuos duomenis struktūra - mano rašysena yra ne visi, kad puikus čia, bet mes stengsimės. Taigi Typedef struct, ir ką aš padariau norite skambinti tai, ką čia? Mazgas. Taigi aš gausiu mums pradėti. Ir dabar, kas turi būti viduje duomenų struktūra, kad atskirai susijęs sąrašą? Kiek laukai? 

Taigi du. Vienas iš jų yra gana lengva. Taigi, int n. Ir galėtume vadinti n ką norime, tačiau ji turėtų būti int jei mes įgyvendinant susietą sąrašą Ints. O dabar ką antras laukas turi būti? Konstrukto mazgas *. Taigi, jei aš struct mazgas *, ir tada aš galite skambinti tai taip pat ką noriu, bet tiesiog turi būti aišku, aš tau paskambinsiu jį šalia, nes mes jau darome. Ir tada aš užmerkiu vingiuotus skliaustus. 

Ir dabar, kaip paskutinį kartą, Aš įdėti mazgas čia. Bet jei aš skelbiantis tai kaip mazgas, kodėl aš nerimauti yra taip išsami čia deklaruojant struct mazgas * kito, o ne tiesiog mazgas * kito? Taip? 

Auditorija: [nesigirdi]. 

Davidas Malan: Būtent. Būtent. Kadangi C tikrai pateksite tiesiogine prasme ir tik mato mazgas apibrėžimą kelią žemyn čia, jūs negalite kreiptis į jį čia. Taigi, mes turime šią pirmumo rūšiuoti deklaracija čia tai tiesa daugiau išsami. Konstrukto mazgas, tai reiškia, kad dabar mes galime jį pasiekti viduje duomenų struktūra. 

Ir kaip žemę, nes tai yra vis tiek daugiau subjektyvus dabar žvaigždučių techniniu požiūriu gali eiti čia jis gali eiti čia, tai gali net eiti per vidurį. Mes tvirtinamos stiliaus vadove kursas, išleidžia konvencija žvaigždučių šalia duomenų tipas, kuris šiuo atveju būtų konstrukto mazgas. Bet suprasti, į vadovėlių daug ir Prisijungę nuorodos, jūs iš tiesų gali jį pamatyti iš kitos pusės. Bet tik suprasti, kad tiek tikrai bus dirbti ir jums turėtų būti tiesiog nuoseklūs. 

Gerai. Taigi, tai buvo mūsų deklaracija iš struct mazgas. Bet tada mes pradėjome daryti daugiau sudėtingų dalykų. Pavyzdžiui, mes nusprendėme pristatyti kažkas panašaus į maišos lentelė. Taigi čia yra maišos lentelėje dydžio n, indeksuojami nuo 0 viršutiniame kairiajame iki n atėmus 1 apačioje kairėje. Tai gali būti maišos lentelė nieko. Bet kas rūšių dalykų padarė kalbame apie naudojant maišos lentelę? Sandėliavimas, ką? 

Vardai. Mes galime padaryti tokius pavadinimus mes padarėme paskutinį kartą. Ir tikrai, jūs galite laikyti nieko. Ir mes matome tai vėl PHP ir JavaScript. Maišos lentelė yra gražus tarsi Šveicarijos Armijos peilis, kuri leidžia jums išsaugoti gana daug, ką norite viduje tai susiejant raktus su vertybėmis. Raktai su vertybėmis. 

Dabar į šį paprastą atveju, mūsų raktai yra tik skaičiai. Mes įgyvendinimo maišos lentelė pateikiama masyvo. Ir taip raktai yra 0, 1, 2, ir taip toliau. Ir todėl mes, kaip žmonės, nusprendė paskutinis savaitę, kad jūs žinote ką, jei mes ketina parduotuvių pavadinimų, galime tik savavališkai, tačiau gana pagrįstai, manyti, kad Alisa, pavadinimas, tiesiog būti indeksuojami į 0. Ir Bobas, B pavadinimą, bus indeksuojami į 1 ir kt. Taigi mes turėjome tarp sąnaudų žemėlapių, kurios stygos, ir maišos vietose, kurios yra numeriai. 

Taigi šis procesas paprastai vadinamas maišos funkcija, ir jūs galite tikrai įgyvendinti kode. Jei aš norėjau įgyvendinti maišos funkcija kad tai, ką mes ką tik aprašytos nuo paskutinio karto, galiu paskelbti funkcija, kad mano, kaip įėjimas pavyzdžiui - ir tegul tai padaryti apie tai ekranas čia. Jei aš norėjau įgyvendinti maišos funkcija, galiu pasakyti, kažkas panašaus į tai. 

Ji ketina grįžti int. Jis bus vadinamas maišos, ir tai ketina priimti kaip argumentas yra eilutę, ar mes galime būti labiau tinkamas dabar ir pasakyti, char *, mes jį vadiname s. Ir tada visa ši funkcija turi daryti, galiausiai yra grąžinti int. Dabar, kaip tai veikia, kad galėtų ne toks aiškus. Aš ruošiuosi įgyvendinti tai be jokių sudaryti iš klaidų tikrinimas dabar. Aš tik aklai pasakyti, grįžti kokia yra 0 laikiklio s, minusas, tarkime, kapitalo kabliataškiais. 

Visiškai neveikia. Ji nėra tobula, nes viena ką daryti, jei ai yra niekinis? Blogi dalykai yra nesiruošia atsitikti. Du, ką daryti, jei pirmoji raidė šioje pavadinimas nėra didžioji raidė? Kad nesiruošia kreiptis iš gerai arba. Tai gali būti mažoji raidė ar ne visai laiškas. Taigi visiškai tobulinti čia bet tai yra pagrindinė idėja. 

Ką mes aprašyta praėjusią savaitę žodžiu kaip tiesiog fiksuoti Alice procesas 0 ir Bob 1 gali būti išreikštas tikrai daugiau formulaically kaip C veikti čia. Vadinamas vėl maišos, priima eilutę kaip įėjimas, tada kažkaip daro kažką su tuo sąnaudų gaminti išėjimo. Ne kitaip nei mūsų juodosios dėžės aprašymas kad mes seniai padaryta. Aš nežinau, kaip tai gali būti darbo po gaubtu. 

Dėl problemą, 6, vienas iš iššūkių yra jums nuspręsti, ką bus jūsų maišos funkcija bus? Kas bus viduje, kad juoda dėžutė, ir matyt, tai bus šiek tiek įdomesnis nei tai, ir tikrai labiau linkę į klaidos tikrinti, nei tai ypač įgyvendinimas. 

Tačiau gali kilti problemų, tiesa? Jei mes turime duomenų struktūrą, tokių kaip šis viena, kas viena iš problemų, galite paleisti į laikui bėgant, kaip jums įterpti vis daugiau ir daugiau vardus į maišos lentelė? Jūs gaunate susidūrimų, tiesa? Ką daryti, jei turite Alice ir Aaroną, du žmonės, kurių vardai atsitiko pradėti? Tai kyla klausimas, kur įdėti antrą tokį pavadinimą? 

Na, galbūt naiviai tiesiog įdėti jį kur Bobas priklauso, bet tada Bob rūšies prisukamas jei bandysite įterpti savo vardą kitą ir nėra jam vietos. Todėl jūs galite įdėti Bob kur Čarlis, ir jūs galite įsivaizduoti, tai labai greitai perduodant į itin tvarkinga. Kažkas linijinis, galų gale, kur tiesiog turi ieškoti visa tai ieško Alisa arba Bob arba Aaronas arba Čarlis. 

Taigi vietoj to mes pasiūlėme, o ne tik tiesiškai zondavimo atvirų erdvių ir uždėjus pavardes ten, mes pasiūlė mėgėjas požiūrį. Maišos lentelė įgyvendinti dar su masyvo indeksų, bet duomenų tipas tie rodikliai dabar buvo rodyklės. Pointeriai į ką? Pointeriai susijusių sąrašų. 

Nes primena, kad susijęs sąrašas tikrai tik rodyklė mazgas, ir mazgas turi kitą sritis, kurios mazgas turi kitą lauką ir pan. Taigi dabar galite galvoti apie šiame masyve ant kairėje pusėje maišos lentelę todėl susietą sąrašą. Kurių privalumas yra tai, jei jūs gaunate susidūrimas tarp Alice ir Aaronui: ką daryti su antras toks žmogus? Jūs tiesiog prijunkite jį arba ją pabaigoje ar net pradžia tos susijęs sąrašą. 

Ir iš tikrųjų, tegul tiesiog makaronų per kad tik sekundę. Kur kuo daugiau prasmės? Jei aš įterpti Alice ir ji baigiasi ne pirmoji vieta, tada bandau įterpti Aarono vardą, ir ten Akivaizdu, susidūrimo, turėčiau pateikti jam pradžioje skirtas susieto sąrašo? Štai tuo pirmąją vietą, ar pabaigoje? 

Auditorija: [nesigirdi]. 

Davidas Malan: Gerai. Girdėjau pradžia. Kodėl pradžioje? 

Auditorija: [nesigirdi]. 

Davidas Malan: Gerai. Tai abėcėlės tvarka, kad malonu. Štai geras nuosavybė. Tai sutaupys man šiek tiek laiko potencialiai. Jis nebus leiskite man padaryti dvejetainis paieškos, bet aš gali bent jau sugebėti išeiti iš kilpos, jei aš suprantu, gerai, aš būdas praeityje buvo Aaronas galėtų būti tai rūšiuoti susietą sąrašą. Aš neturiu gaišti savo laiką ieško visą kelią iki pabaigos. Taigi, kad protinga. Kodėl dar gali norite įterpti susidūrimo pavardė pradžioje sąraše? Kas tai? 

Auditorija: [nesigirdi]. 

Davidas Malan: Tai gali užtrukti ilgą laiką patekti į sąrašo pabaigą. Ir iš tiesų, vis ilgiau ir ilgiau. Kuo daugiau vardų įdėsite kad pradėti su, ilgiau nei grandinės ketina gauti. Ilgiau, kad susiję sąrašas ketina gauti. Taigi jūs tikrai tik eikvoti savo laiką. Gal jūs geriau išlaikyti nekintamo įstatymo laikas, didelis O iš 1, , visuomet išleidimą susidūrimo pavardę skirtas susieto sąrašo pradžioje, o ne nerimauti tiek daug apie rūšiavimą. 

Kas geriausias atsakymas? Neaišku. Jis rūšies priklauso nuo to, pasiskirstymas, kas modelis pavadinimų jūs įdėti. Tai nebūtinai Akivaizdus atsakymas. Bet čia, vėlgi, yra dizainas galimybė. 

Taigi, mes tada pažvelgė į šio dalyko, kuris yra tikrai kita didelė galimybė p-rinkinys 6. Ir suprasti, jei jūs dar neturite, Zamyla neria į abu, maišos stalai ir bando, išsamiau. Ir vaizdo Walkthrough nematomas p nustatytą spec. Tai buvo trie - T-R-I-El. Ir tai, kas buvo įdomu buvo ta, kad važiavimo laikas tyrinėtą vardą, kaip Maksvelo paskutinį kartą, buvo didelis O ką? Kas tai? 

Auditorija: Raidžių skaičius. 

Davidas Malan: Taškų raidėmis. Aš girdėjau du dalykus. Daug laiškų ir nuolat laiko. Taigi eikime su tuo pirmas. Raidžių skaičius. Na, tai duomenų struktūra, išėmimą iš apyvartos, yra kaip medis, šeimos medis, kiekvienas , kurių mazgai yra sudaryta iš matricos. Ir tie matricos yra rodyklės į kiti tokie mazgai, ar kita masyvų medžio. 

Taigi, jei mes norėjome tada nustatyti ar Maxwell čia, galiu eiti į pirmą masyvo, ne pačiame viršuje medis, vadinamasis šaknis, viršuje trie ir vykdykite M rodyklė, tada rodyklė, tada x m, e, l, l. Ir tada, kai matau tam tikras specialias simbolį, žymimas čia kaip trikampis. Kodu pamatysite siūlome, kad jūs įgyvendinama kaip bool, tiesiog sako "taip" ar ne, žodis sustoja čia. 

Na, kai mes atvyko į M-A-X-W-E-L-L, jaučiasi septynių, o gal aštuonių jei mes einame vieną pro jį aštuonios veiksmai ieškant Maksvelas. Arba tegul bus K. Bet prisiminti paskutinis kartą, aš teigė, kad, jei yra realiai maksimalus ilgis nuo žodis, pavyzdžiui, 40-kai nelyginis simbolių, Ilgiausias reiškia konstantos reikšmę. Taigi tikrai, taip, tai techniškai didelis O 8 arba 7, arba tikrai didelis Ö K. Bet jei yra baigtinė riba, ką K gali būti, tai konstanta. Ir todėl didelis O nuo "1", dienos pabaigoje. 

Ne realiame pasaulyje. Ne, kai jūs iš tikrųjų pradėti žiūrėti Jūsų laikrodis kaip savo programos veikia. Tai visiškai bus šiek tiek lėčiau nei tikrai pastovus laikas nuo vieno žingsnio. Tai bus septynis ar aštuonis žingsnius, bet vis tiek tai daug, daug geriau nei kaip didelis O n šio algoritmo priklauso nuo to, kas yra dydžio duomenų struktūra. 

Pranešimas aukštyn kojom čia mes galime įterpti milijono daugiau vardų į tai duomenų struktūros, bet kiek daugiau žingsniai ji ketina priimti mus rasti Maksvelo tokiu atveju? Nėra. Jis neturi jokios įtakos. Ir iki šios dienos, aš nemanau, kad mes matėme iš duomenų struktūros ar pavyzdys algoritmas, kuris buvo visiškai neveikia išorės elgesys, pavyzdžiui, kad. Bet tai negali būti nuostabi. Tai gali būti ne vienintelė išeitis už p-rinkinys 

Ir tai ne. Tai nebūtinai duomenis struktūra turėtumėte veržtis, nes kaip ir maišos lenteles, kompromisas. Kas yra kaina, kurią mokate čia? Atmintis. Aš turiu galvoje, tai yra žiaurus atminties kiekis. Ir jūs galite ne visai pamatyti čia, nes Šio paveikslėlio autorius akivaizdžiai sutrumpintas visų masyvų, ir mes nematome daug "ir Pusryčiai ir C atsargiam ir Y ir Z šių masyvų. Bet jie ten. 

Kiekviena iš šių mazgų yra visas masyvas kai 26 ar daugiau baitų, kiekvienas iš kuris yra baigęs laišką. 27 mūsų atveju, kad mes galime padėti kabutes šia problema rinkinys. Taigi tai duomenų struktūra yra tikrai, tikrai tankus ir platus. Ir tai tik gali baigtis lėtėja dalykų žemyn, arba bent jau jums kainuos daug daugiau vietos. Bet vėl, galime daryti palyginimai čia. 

Prisiminkite, o atgal, mes pasiekėme daug įdomesnis veikimo laikas rūšiavimas kai mes naudojame suliejimo rūšiuoti, o kaina mes sumokėjome pasiekti n log n už suliejimą rūšiuoti reikalaujama, kad mes praleidžiame daugiau ką išteklių? Daugiau vietos. Mums reikia vidurinį masyvo kopijuoti žmones, kaip mes padarėme čia ant scenos. Taigi dar kartą, jokių aiškių laimėtojų, bet tik subjektyvus dizainas sprendimai turi būti pateikta. 

Gerai. Taigi, kaip apie tai? Kiekvienas pripažinti, kurios D-Hall "? Gerai. Taigi trys iš mūsų padaryti. Mather namai. Taigi tai yra Mather "valgomajame. Lažinuosi visi valgomuosiuose turi kaminai padėklai, kaip šis. Ir tai iš tikrųjų atstovas iš kažkas, ką mes akivaizdžiai matyti jau. Mes pavadino jį tiesiog kamino. Ir kamino, atsižvelgiant į jūsų kompiuterio atmintyje, kai duomenys eina o funkcijos yra vadinamas. 

Pavyzdžiui, kokių rūšių dalykų eiti ant atžvilgiu kaminą Atminties išdėstymas mes aptarė savaitėmis anksčiau? Kas tai? 

Auditorija: Skambučiai į funkcijas. 

Davidas Malan: aš atsiprašau. 

Auditorija: Skambučiai į funkcijas. 

Davidas Malan: Skambučiai į funkcijas, bet Tiksliau, tai, kas viduje kiekvieno tie rėmai? Kokius dalykus? Taip. Taigi vietiniai kintamieji. Kada mums reikia šiek tiek vietos saugojimo, kaip argumentas, arba int i, int arba temperatūros, ar kas vietos kintamasis, mes jau išleisti, kad kamino. Ir mes jį vadiname kamino, nes tos sluoksniavimasis idėja. Tiesiog rūšies atitikmenų su realybe, sąvoką ir jos. 

Tačiau paaiškėja, kad kamino taip pat gali būti vertinamas kaip duomenų struktūros, alternatyva masyvo, alternatyva į susietą sąrašą. Kažkas konceptualiai įdomiau kad vis dar gali būti įgyvendinama naudojant vieną iš šių dalykų, bet tai skirtingo tipo duomenų struktūros remia, tikrai, tik dvi operacijos. Bet jūs galite pridėti mėgėjas funkcijų nei jie. Tačiau tai yra pagrindai - stumti ir pop. 

Ir su kamino idėja yra ta, kad jei aš turime čia, su arba be Annenberg žinant, iš šalia durų dėklą su 9 numerio ant jo. Taigi tik int. Ir aš noriu stumti tai į duomenų struktūrą, kuri šiuo metu yra tuščias. Apsvarstykite šį iš kamino apačioje. Aš stumti šį skaičių 9 ant sukrauti, o dabar tai tiesiai ten. 

Bet įdomus dalykas, apie kamino yra ta, kad jei aš dabar noriu stumti kitu vertė, kaip ir 17, ir aš stumti tai ant kamino, aš ruošiuosi daryti tik intuityvus dalykas, aš tik ketina Norėdami įdėti ją ten, kur mes, žmonės būčiau linkęs jį, viršuje. Bet kas įdomu dabar yra, kaip aš galiu gauti ne 9? Jūs žinote, aš ne be tam tikrų pastangų. 

Taigi, kas įdomu kamino yra tai, kad dizainas, tai LIFO duomenų struktūra. Kvailas būdas aprašyti Paskutinis in, first out. Taigi paskutinis skaičius tuo metu buvo 17. Taigi, jei aš noriu, kad pop ką nors ne į kaminą, tai gali būti tik 17. Taigi nėra privaloma tvarka operacijos čia, kur paskutinis punktas ir turi būti pirmasis iš. Taigi akronimas, LIFO būdą. 

Tad kodėl tai galėtų būti naudinga? Ar jų situacijas, kuriose norite noriu duomenų struktūros, kaip tai? Na, tai tikrai buvo naudinga viduje kompiuterio. Taigi operacinės sistemos aiškiai naudoti šį tipo duomenų struktūrą kaminus. Mes taip pat matome tą pačią idėją kai jis ateina į interneto puslapius. Taigi šią savaitę ir kitą savaitę ir už jos ribų, ir kaip jums pradėti įgyvendinti internete puslapiai kalba vadinama HTML, galite iš tikrųjų naudoti duomenų struktūrą, kaip tai nustatyti, jei puslapis yra teisingai suformatuotas. Kadangi mes pamatysime visi interneto puslapiai sekti hierarchijos rūšiuoti, įspaudas kad bus, bent dienos pabaigoje, bus medžio struktūra po gaubtu. Taigi daugiau, kad tik šiek tiek. 

Bet dabar, galime pasiūlyti momentas, kaip galėtume eiti apie atstovaujanti ką kamino? Leiskite man pasiūlyti, kad mes įgyvendinti kodu, kaip tai kamino. Taigi kamino teks viduje ji du dalykai, masyvas, vadinamas padėklai, tiesiog, kad būtų suderinta su demo. Ir kiekvienas iš masyvo, daiktų bus tipo int. Ir talpa yra tikriausiai kas? Kadangi aš ne parašyta pilnas apibrėžimas čia. 

Tai turbūt didžiausia dydis masyvo. Ir tai tikriausiai deklaruoti kaip aštrus apibrėžti prie failo viršuje, kai kokios pastovios, kaip numatoma pagal Vien kapitalizacija. Taigi kažkur galia yra apibrėžiama kaip didžiausią galimą dydį. Tuo tarpu viduje duomenų struktūros žinomas kaip kamino ten bus būti sveikasis tik žinomas tiesiog kaip dydžio. 

Taigi, jei aš būčiau atstovauti tai dabar pavaizduotomis piktogramo, galime manyti, kad ši Visas "black box" yra mano kamino. Viduje ji yra dviejų kintamųjų. Taigi, aš ruošiuosi daryti Pirmasis, dydžio. O antrasis aš ruošiuosi atkreipti kaip masyvo. 

Bet tik, kad viskas būtų tvarkingai, paprastai norėčiau atkreipti masyvą kaip , bet tai savotiškas gražus jei mes atitikti tikrovę, arba atitiktų psichikos modelis. Taigi leiskite man vietoj atkreipti masyvo vertikaliai, kuri yra tik, vėlgi, Menininko perdavimų. Tikrai ne klausimas, ką jis yra po gaubtu. Ir mes pasakyti, kad, pagal nutylėjimą, talpa bus trys. Taigi, tai bus vieta 0, tai bus 1 vieta, tai bus 2 vieta. 

Jei aš papirkti su streso kamuolys, būtų žmogus kaip sugalvoti ir paleisti įlipti čia tik akimirką? Gerai, pamačiau ranką pirmas. Ateik iki. Gerai. Taigi manau, kad Stevenas. Ateik iki. Gerai. 

Bet tarkime, kad dabar mes atgal į pradinį pasaulio valstybė, kur aš ką tik paskelbė krūvą, tai bus pajėgumų trijų. Bet dydis dar nenustatytas. Padėklai dar nebuvo nustatyta. Taigi klausimų pora pirmas. Ir leiskite man duoti jums mikrofoną, todėl jūs galite dalyvauti aktyviau šioje srityje. 

Taigi, kas yra viduje dydžio šiuo metu laiku, jei visa, ką padariau yra paskelbė krūvą viena eilutė kodo? 

STEVEN: Ne per daug. 

Davidas Malan: Gerai, nėra daug. Ar žinome, kas yra viduje dydžio, mes žinome, kas viduje Šio masyvo čia? 

STEVEN: Tiesiog atsitiktinis kodas, tiesa? Tiesiog - 

Davidas Malan: Taip, aš ruošiuosi jį vadiname kodas, o atsitiktiniai - 

STEVEN: daiktai. 

Davidas Malan: Dalykų, pavyzdžiui, atsitiktinis 

STEVEN: bitai. 

Davidas Malan: Bitai, tiesa? Taigi šiukšlių vertybėmis, tiesa? Taigi kombinacijomis 0 ir 1-aisiais. Likusių ankstesniais papročius Šios atminties. Ir mes tikrai nežino, ką reiškia šios reikšmės yra, todėl mes paprastai padaryti juos kaip klaustukais. 

Taigi pirmas dalykas, mes turbūt ketinate norite padaryti čia - ir leiskite man duoti šį lauką viduje ten pavadinimas - padėklai. Ką turėtume matyt inicijuoti dydis, jei norime pradėdami vartoti šį krūvą? 

STEVEN: dėklas yra sub 3. 

Davidas Malan: Taigi, Gerai. Kad būtų aišku, talpa yra paskelbta kitur kaip trys. Ir tai, ką aš naudojamas skirti masyvą. Dydis ketina kreiptis į kiek padėklai metu ant kamino. 

STEVEN: nulis. 

Davidas Malan: Taigi jis turėtų būti lygus nuliui. Taigi pirmyn, ir su bet pirštu, atkreipti į nulinio dydžio. Gerai. Taigi dabar, kas viduje tai čia mes nežinome. Tai yra tikrai tik šiukšlių vertybes. Taigi, mes galime atkreipti klaustukų, bet galime laikyti lenta švarus dabar nes nesvarbu kas ten. Mums nereikia inicijuoti masyvas nieko, nes jei mes žinome, kad iš kamino dydis yra lygus nuliui, gerai, mes neturėtų būti žiūri nieko tai masyvas vistiek ne šis punktas laiku. 

Taigi dabar manau, kad aš stumti ant kamino 9 skaičius. Kaip mes turėtume atnaujinti duomenų struktūrą viduje šios juodosios dėžės? Kas vertes reikia pakeisti? 

STEVEN: per - dydis? 

Davidas Malan: Gerai. Dydis turėtų tapti tuo, ką? 

STEVEN: Dydis būtų vienas. 

Davidas Malan: Gerai. Taigi dydis turėtų tapti vienas. Taigi, jūs galite tai padaryti per kelias būdais. Leiskite man duoti jums, dabar jūsų pirštas trintukas. Gerai. Tada dabar jūsų pirštas šepetys. Gerai. Ir dabar kas nors turi pakeisti, Akivaizdu, kad duomenų struktūros? 

STEVEN: Mes ketiname nuo iš apačios į viršų iki 9. 

Davidas Malan: 9. Gerai, gerai. Taigi vis dar nesvarbu kas ne vieta vienas ar du, nes jie šiukšlių vertės, bet mes neturėtume nerimauti ieško ten, nes dydis yra mums sako, kad tik pirmasis elementas yra iš tikrųjų teisėtas. Taigi, dabar aš stumti 17 į sąrašą. Kas nutinka šioje nuotraukoje? 

STEVEN: Taigi dydis ketina eiti iki dviejų. 

Davidas Malan: Gerai. Jūs esate trintukas - Oi. Jūs esate trintukas. 

STEVEN: Trintukas. 

Davidas Malan: Jūs šepetys. 

STEVEN: teptukas. 

Davidas Malan: Gerai. Ir kas dar? 

STEVEN: Ir tada mes - 

Davidas Malan Mes siekėme 17. 

STEVEN: Mes laikomės 17 ant viršaus, taip - 

Davidas Malan: Gerai, gerai. 

STEVEN: - lašas žemyn. 

Davidas Malan: Gerai. Tai vis lengva. Aš nesiruošia padėti jums šiuo metu. Push 22. 

STEVEN: Atlikta. Tapimas trintukas. Aš vis šepetys. Ir tada aš esu išleidimą 22. 

Davidas Malan: 22. Puikus. Taigi dar kartą. Aš dabar ketina stumti ant kamino 26. 

STEVEN: Ooh. O GOSH. Jūs tikrai sugauti mane užklupti. 

Davidas Malan: Jūs nepadarė pamatyti tai ateina? 

STEVEN: aš nemačiau tai ateina. Ar galėtume vėl pradinis pajėgumas? 

Davidas Malan: Tai geras klausimas. Taigi mes rūšies dažytos save kampe čia. Ten tikrai nieko gero iš Steven nes mes skiriama šio masyvo statiškai, taip sakant, viduje duomenų struktūrą. Ir mes iš esmės sunku koduojami kad jis būtų dydžio trijų. Taigi mes tikrai negali perskirstyti. 

Mes galime, jei mes grįžo į, mes naujo padėklai būti žymeklis, kad mes tada naudokite malloc į rankas atminties į. Nes jei mes turime atmintį nuo per malloc krūvą, mes galėtų laisvai jį. Bet prieš išlaisvina jį, mes galime perskirstyti didesnę riekė atminties, atnaujinti žymiklį ir kt. Bet dabar, tai tikrai Geriausia, ką galime padaryti. Push ir pop, matyt, vyksta turi parodyti tam tikrą paklaidą. 

Taigi, pavyzdžiui, mūsų įgyvendinimas Push gali grįžti bool kuris anksčiau grįžo tiesa, tiesa, tiesa. Tačiau ketvirtą kartą, tai teks grįžti klaidinga, pvz. Gerai. Labai gerai padaryta. Sveikiname. Jūs uždirbote savo streso kamuolys šiandien. 

[Plojimai] 

STEVEN: Ačiū. 

Davidas Malan: Ačiū. Gerai, kad tai atrodo ne daug iš žingsnį į priekį, tiesa? Mes aprašė šį duomenų struktūrą. Tai buvo įtikinamas, tiesa? Operacinės sistemos patinka. Matyt interneto gali pasinaudoti šia, ir kitas programas, vis dar. Bet kas kvailas apribojimas, kad mes atgal į rūšiuoti savaitės dvi ribos kur mes fiksuoto dydžio masyvus. 

Taigi iš tiesų yra pora būdų, kaip galėtume išspręsti šią problemą. Mes galime dinamiškai paskirstyti masyvą, ne sunku kodavimo kaip aš padaryti čia, bet vietoj naujo paskelbti tai, tiesiog, kad būtų aišku, kaip kažkas panašaus į tai. Int * padėklai, o ne sprendžiant dėl pajėgumų dar. Bet kai aš pareiškiu, kamino kitur mano kodą, galėčiau tada skambinti malloc, gauti iš riekė adresą atmintis, ir aš galėčiau priskirti kad adresas, padėklai. 

Ir tada, nes tai tik riekė atminties, galėjau ir toliau naudoti aikštė laikiklis žymėjimas įprastu būdu. Nes vėl, ten tarsi tai funkcinis ekvivalentas matricos ir gabaliukus atminties, kad ateis atgal iš malloc. Mes galime gydyti vieną, nes kita naudojant rodyklę aritmetinį ar kvadratas laikiklis žymėjimas. Štai vienas požiūris. 

Bet kaip kitaip galėtume įgyvendinti šį pati duomenų struktūra, potencialiai? Teisė? Jaučiu, kaip mes tiesiog išspręsti šią problema kaip ir prieš savaitę. Koks buvo šios problemos sprendimas kad Stevenas įvažiavo į? Taigi susiję sąrašai, į dešinę. 

Jei problema yra ta, kad mes tapyba save į kampą, skiriant iš anksto per mažai atminties, kad mes tada jau kažkaip spręsti, gerai, kodėl ne tik išvengti, kad išduoti apskritai? Kodėl gi ne tiesiog paskelbti padėklai būti rodyklė mazgas ERGO susijęs sąrašą, ir tada tiesiog skirti naujų mazgų kiekvieną kartą, kai Stevenas reikia, kad tilptų skaičius į duomenų struktūrą. 

Taigi vaizdas būtų pakeisti. Jis nesiruošia būti kuo švaresnis ir kaip paprasta, kaip tik yra trijų Ints masyvo. Dabar tai bus rodyklė konstrukto ir kad konstrukto ketina turi int ir kitą rodyklę. Ji ketina sukelti per tą rodyklė kitas toks struct į kitas toks konstrukto. Taigi vaizdas būtų iš tikrųjų gauti šiek tiek Mesje. Ir būtume rodyklės susiejimas viskas kartu. 

Bet tai gerai, teisingai, nes mes matėme, kaip tai padaryti. Ir kai jums patogu įgyvendinti kažką panašaus Tinkliniai Sąrašas, kuriame jūs turite padaryti, jei nuspręsti įgyvendinti maišos lentelę atskiras Grupavimo p-rinkinys 6, galite naudoti jį kaip statybinis blokas, arba sudedamoji dalis, arba nulio kalbėti, procedūra, kažkas, kad jūs įdėti, jums sukūrėte savo įspūdį , tada galite naudoti pakartotinai. Taigi kompromisų, tačiau galimi sprendimai kad mes iš tikrųjų matęs. 

Taigi gana dažnai, kaip matote tai kiekvieną metus ar du, kai "Apple spaudai kažkas naujo, ir visi išprotėję žmonės liniją iki ne Apple parduotuvę pirkti jų ribinė atnaujinti aparatūros. Aš tai sakau, tai gerai, nes Aš esu vienas iš tų žmonių. Taigi, kokios duomenų struktūros gali atstovauti šią tikrovę? 

Na, tegul bus eilėje, linija. Taigi Britų vadinčiau tai paprastai eilė vistiek, todėl gražus vardas. Ir dvi operacijos, kurios eilės remia mes vadiname į eilę veikimas ir dequeue operacija, kurios yra panašios dvasia stumti ir pop. Tai tiesiog tarsi skiriasi konvencija, ką mes skambinti šių. Bet į eilę kažką reiškia pridėti arba įdėkite jį į duomenų struktūra. Norėdami dequeue tai jį pašalinti. Bet kadangi kamino buvo LIFO duomenys struktūra, eilė pirmas, Pirmasis iš duomenų struktūra. 

Jei esate pirmasis asmuo linija, jums bus pirmasis asmuo, gauti iš linijos ir pirkti naują įrenginį. Įsivaizduokite, kaip nusiminusi šie žmonės būtų jei "Apple" vietoj to naudojo kamino, už Pavyzdžiui, įgyvendinti skynimas iki savo naują žaislą. Taigi eilės prasmės, be abejonės, mes galime galvoti apie visų rūšių programas, matyt, už eiles, ypač jei norite sąžiningumą. Taigi, kaip galėtume įgyvendinti šias kaip duomenų struktūros? 

Na, aš siūlau, kad mes galime reikia tai padaryti tokiu būdu. Taigi, aš ruošiuosi dabar turi numerius. Taigi mes keep it simple, o ne nebūtinai kalbame požiūriu padėklai. Tik skaičiai, kad žmonės Dotarłeś. Talpa ketina vėl nustatyti bendras skaičius žmonių, kurie gali būti ši eilutė, nes tris ar kokia kita reikšmė. 

Bet aš siūlau, kad man reikia sekti ne tik dėl dydžio eilė, kiek daug yra juo. Taigi dydis yra srovės dydis, pajėgumas yra maksimalus dydis. Tiesiog vėl nomenklatūra pagal susitarimą. Kodėl aš turiu papildomą int viduje iš eilės sekti, kas į priekinėje linijoje? Kodėl aš turiu daryti, kad šiuo atveju? 

Na, kaip yra šį paveiksliuką keisis? Galiu tikriausiai pakartotinai labiausiai Šio paveikslėlio. Leiskite man eiti į priekį ir ištrinti, kas čia. Mes padėsime tai šiek tiek kitą pavadinimą čia. Leiskite atsikratyti 17, galime atsikratyti iš 9, galime atsikratyti 3. Ir tegul pridėti vieną kitą dalyką. Aš siūlau, kad man reikia sekti sąrašo priekyje, kuris yra tik bus int taip pat. Ir mes ketiname keep it simple. Nėra susieta sąrašas dabar. 

Mes pripažinti, kad mes ketiname guzas nuo šios ribos. Bet ką aš noriu pamatyti įvykti šį kartą? Taigi, tarkime, aš einu į priekį ir pirmoji žmogus ateina linija, ir tai numeris 9. Mes turime streso kamuoliukus. Ar galiu pavogti, tarkim, du ar trys žmonės? Vienas, du, trys? Ateik iki. Teisė iš priekio, nes mes padaryti tai vienas greitai. 

Kiekvienas iš jūsų dabar bus ventiliatorius berniukas eilėje prie "Apple". Jums nebus gauti Apple Hardware prie šio nors pabaigoje. Gerai. Taigi jūs numeris 9, esate numeris 17, numeris 22. Tai yra savavališkai skaičiai, pavyzdžiui, studentas ID arba Plauktiņš. Ir tik akimirką, pradėkime pradėti pridedant dalykų. Ir aš paleisti lenta čia šį kartą. 

Taigi, šiuo atveju, aš inicializuoti priekis būti - Aš iš tikrųjų nerūpi, ką priekyje, nes dydis yra lygus nuliui. Taigi tai taip pat tiesiog būti klaustukas. Tai yra visų klaustukų. Taigi dabar mes pradėsime iš tikrųjų matyti, kai žmonės rikiuojasi į parduotuvę. 

Taigi, jei numeris 9, esate pirmasis ten 05:00, eiti į priekį ir išsirikiuoti arba naktį prieš. Gerai. Taigi dabar 9 yra čia. Taigi 9 yra sąrašo priekyje. Taigi, aš ruošiuosi eiti į priekį ir atnaujinti Šios srovės duomenų dydis struktūra nėra 0 nebėra, bet turi būti 1. Aš ruošiuosi įdėti 9 metu priekyje sąrašo. Leiskite man eiti į priekį ir perjungti ekraną todėl mes galime pamatyti paskutinius mūsų čia. 

O dabar ką aš noriu įdėti į priekyje? Aš einu sekti, kad priekinėje eilėje dabar yra 0 vietoje. Nes tai, kas yra šalia nutiks? Na, tarkime, dabar aš į eilę 17, taip pat. Taigi hop atitinka ten. Ir vėl, durų rūšiuoti parduotuvė bus čia. Taigi dabar aš pridėjo 17. Ir nors šie vaikinai blokavimas ekranas, tai gerai, nes mes galime jį pamatyti čia. Atsiprašau. 

Auditorija: Mes galime judėti - 

Davidas Malan: Ne, viskas gerai. Tai didžiulis ten. Taigi 17 dabar viduje eilėje. Man reikia atnaujinti, kuri laukai dabar nors? Gerai, tikrai dydis. Ir kaip apie priekyje? Gerai, Nr. Priekinis neturėtų keistis, nes skirtingai nuo kamino, mes nori išlaikyti teisingumą. Taigi, jei 9 atėjo pirma, mes norime 9 bus pirmasis iš linijos ir į parduotuvę. 

Iš tiesų, galime pamatyti, kad. Prieš mes įterpti 22, galime eiti į priekį ir dequeue 9. Kas tavo vardas? 

Auditorija: Jake. 

Davidas Malan: Jake vyksta būti dequeued dabar. Taigi jums vaikščioti į parduotuvę. Ir apsimesti, kad parduotuvė yra ten. Taigi dabar, ką reikia - DIT-DIT-dit! Kas turi įvykti dabar? Dizainas sprendimas. Taigi nėra blogai instinktas, bet - kas tavo vardas? 

Auditorija: Davidas. 

Davidas Malan: David. Taigi, ką Dovydas daryti? Jis bando rūšiuoti nustatyti duomenis struktūra ir judėti iš savo vietos į Jake buvusio vietą. Ir tai gerai, jei mes pasirengę pripažinti, kad, kaip įgyvendinimas išsamiai. Bet pirmiausia, galime atnaujinti duomenis struktūrą, kol mes tai padaryti. Kadangi aš ne mylėti visų idėją žmonės keičiasi šioje eilutėje. 

Tai ne big deal, jei Davidas jis su vienas žingsnis, bet vėlgi, prisiminkite kai mes turėjo aštuonis savanorių etapas ir mes padarėme kaip budas rūšiuoti, kur mes turėjo pradėti perkelti visus aplink. Kad gavau brangus, tiesa? Tai verčia mane šliaužioti apie Didelės O n, didelis O n kvadratu dar kartą. Tai ne jausmas, kaip idealus rezultatas. 

Taigi galime tik atnaujinti šiuo klausimu. Taigi iš eilės dydis nebėra 2. Tai dabar tiesiog 1. Bet dabar aš galiu atnaujinti kažką Aš ne atnaujinti anksčiau, priekyje sąrašo. Galėčiau tik pasakyti, yra tai, kad 1 vieta? Taigi dabar mes turime šiukšlių vertę čia šiukšlių vertė čia, ir Dovydas viduryje šio atliekomis. Tačiau duomenų struktūros vis dar yra nesugadintos. 

Ir iš tiesų, aš net nereikia pakeisti Jake buvusią numeris 9, nes who cares. Turiu pakankamai informacijos dabar dydžio, kad aš žinau, yra vienas žmogus tai eilė. Ir aš žinau, kad tas asmuo yra vieta 1, o ne 0. Nesu skaičiavimas. Taigi 1, taip pat. Taigi, duomenų struktūros vis dar Gerai. 

Na, kas bus toliau? Leiskite į eilę - koks tavo vardas? 

Auditorija: Callen. 

Davidas Malan: Callen. Leiskite į eilę tam Callen ir 22 dabar eilėje. Taigi dabar, kas turi pakeisti čia? Priekinis nesiruošia pakeisti, žinoma. Dydis ketina keisti ir 2 dar kartą. Ir 22 baigiasi čia, 9 vis dar yra, bet tai efektyviai šiukšlių vertė dabar. Tai tiesiog Jake praeities atgyvena. 

Taigi dabar kas atsitiks, jei Aš dequeue Dovydą? Vienas paskutinės operacijos, dequeue Davidas. Mes galime pakeisti, bet siūlau tegul tai kaip tiek darbo, kiek įmanoma. Dabar mano duomenų struktūros eina atsargines dydis nuo 2 ir 1. Tačiau nuo eilės priekyje dabar tampa 2. Man nereikia pakeisti šiuos numerius tik dar, nes jie tik šiukšlių vertės. 

Bet dabar, kas atsitinka? Tarkime, aš į eilę save, 26? Aš jaučiuosi kaip aš priklausau čia. Taigi, aš vis enqueued. Taigi I rūšies priklauso čia. Ir nors jūs ne visai vertinu tai vizualiai ant scenos, nes mes turime daug galimybių, turėčiau ne stovėti čia, kodėl? 

Auditorija: Jūs iš ribų. 

Davidas Malan: Teisingai. Aš iš ribų. Aš indeksuojami ne tik Ribas šiame masyve. Aš tikrai turėtų būti viena iš galimi trys vietos. O dabar, kur labiausiai natūralus eiti? Siūlau mes skolintomis savaitę vienas triukas. Mod operatorius, procentais. Kadangi aš techniškai stovėjo 3 vieta, bet aš 3 mod pajėgumus, taigi 3 proc ženklas, 3 - pajėgumas yra 3. Kas tai? Kas likutį jums padalinti 3 iš 3? 0. 

Taigi, kad iškelia mane buvo Jake buvo kuri yra tikrai gera. Taigi dabar įgyvendinimas tai dalykas vyksta būti galvos skausmas šiek tiek. Tai tikrai tik viena eilutė galvos skausmas, kodo. Bet bent jau dabar yra šiukšlių vertė ne čia, o ten du teisėtų ints čia. Ir aš teigia, kad dabar mes padarėme ką mes turime padaryti, kol mes pakeisime ką Jake vertė turėjo būti 26. 

Mes dabar turime pakankamai informacijos, dar išlaikyti vientisumą Šios duomenų struktūra. Mes vis dar natūra iš laimės, kai mes norite įterpti keturis ar daugiau viso elementai, bet aš bent jau gali padaryti gana efektyviau naudoti ši konstanta laikas, iš tikrųjų. Aš neturiu jaudintis keičiasi Kiekvienas žmogus, kaip Dovydo polinkis buvo. 

Bet koks šūsnis klausimų, ar tai eilė? 

Auditorija: Ar priežastis jums reikia dydžio, kad žinote kur yra žmogus? 

Davidas Malan: Būtent. Man reikia žinoti, iš masyvo dydį nes man reikia tiksliai žinoti, kaip daugelis šių vertybių yra teisėtas, ir taip, kad galiu rasti kur dėti kitas asmuo. Būtent. Dydis - Tiesą sakant, mes ne atnaujinti šį dar. Aš pridėjo save ne 26. Dydis yra dabar, o ne 1, bet 2. Taigi, dabar tai tikrai padeda man rasti galvos sąraše, kuris yra ne 0, o ne 1, bet 2. Sąrašo priekyje iš tiesų yra skaičius 22. Kadangi jis atėjo pirmas, todėl jis turėtų būti leidžiama į parduotuvę prieš mane, nors vizualiai aš stoviu arčiau parduotuvės. 

Viskas gerai? Ar plojimų šių vaikinai ir mes galime juos iš ten. 

[Plojimai] 

Davidas Malan: galėčiau leisti jūs nuolat dėklą. Mes galime pamatyti, kas atsitiks, jei norite, bet gal ir ne. Gerai. Taigi, kas dabar, kad palikti mums? Na, leiskite man pasiūlyti, kad yra keletas kitų duomenų struktūros galėtume pradėti pridedant mūsų įrankių rinkinys, kad bus tikrųjų gali būti gana, gana aktualus, nes mes pasinerti į interneto stuff. Kuris vėl turi pobūdžio ryšį į medžių formos kažkas vadinamas DOM, dokumentų objekto modelį. Bet mes pamatysime daugiau kad prieš ilgas. 

Leiskite man pasiūlyti definitionally, kad mes skambinti medį dabar ką gali žinoti, kaip daugiau šeimos medį, kur kažkiek protėvį šaknys medžio. Patriarchalinės ar matriarch ne pačiame viršuje medžių. Be savo sutuoktinio, šiuo atveju. Bet dabar mes turime tai, ką mes vadiname vaikai, kurie mazgai, kad pakabinti nuo kairiojo vaiko ar teisinga vaikui, rodykles kaip parodyta čia. 

Kitaip tariant, medis duomenų struktūros kompiuterių, medis turi nulį ar daugiau mazgų. Jei jis turi bent vieną mazgą, tai vadinama šaknis. Tai, ką vizualiai, kad mes atkreipiame viršuje. Ir tai mazgas, kaip bet kuris kitas mazgas, galite yra lygus nuliui, vieną, ar du, ar trys, ar vis dėlto daug vaikų duomenų struktūra palaiko. Šiuo atveju, šaknis, saugojimas vertė viena, turi du vaikus, 2 ir 3 dalis, todėl mes paprastai vadiname 2 kairę vaikas ir 3 dešinėje vaikas. 

Ir tada, kai mes gauti iki 5, 6, ir 7, 6 gali būti vadinamas vidurinis vaikas. Jei turite keturis vaikus, ji tampa paini. Taigi mes nustoti naudoti tokio pobūdžio sparčiųjų žodžiu. Bet tai tikrai tik šeimos medis. Ir lapai čia yra mazgai, kad patys neturi vaikų. Jie pakabinti išbrauktas iš medžio apačioje. 

Taigi, kaip galėtume įgyvendinti medį, kad turi tik du vaikus maksimaliai? Mes jį vadiname dvejetainis medis. Patinka vėl reiškia du, šiuo atveju, kaip dvejetainiu. Ir todėl jis gali turėti nulis, vienas, arba du vaikai maksimaliai. 

Aš siūlau, kad mes įgyvendinti mazgas tos su int n struktūrą, ir tada dvi rodyklės, vienas vadinamas į kairę, vienas vadinamas teisus. Tačiau tai tik gražus savavališkai konvencijomis. Ir kas malonu dabar, ypač jei rūšies kovojo konceptualiai su rekursija, arba manoma, kad tai buvo ne tikrai sprendimas nieko, ypač, jei galėtumėte paleisti iš atminties. Dabar, kad mes kalbame apie duomenų struktūros ir algoritmai, kurie leidžia mums išanalizuoti ir jais manipuliuoti, Pasirodo, kad rekursija grįžta daug įtikinamų jei ne gražus būdas. 

Taigi tai aš siūlau yra įgyvendinimas Apie Search funkcija. Kadangi du įėjimai - todėl galvoti apie tai, kaip juodąją dėžę. Kadangi du įėjimai, N, int ir Rodyklė į medį, rodyklė mazgas, ar tikrai iš medžio šaknis, aš teigia, kad ši funkcija gali grįžti true arba false, kad vertė n yra viduje šio medžio. 

Kas viduje šios juodosios dėžės? Na, keturi filialai. Pirmasis tik tikrina. Jei medis yra niekinis, tiesiog grįžti klaidinga. Jei nėra mazgas, nėra n nėra skaičius, tiesiog grįžti klaidinga. Jei nors n, vertė ieškote Nes yra mažesnis nei medžio rodyklės n ir tiesiog, kad būtų aišku, ką tai reiškia, kai Aš rašau medį ir tada rodyklę žymėjimas, n? Būtent. Tai reiškia, kad dereference rodyklė vadinamas medį. Eiti ten, ir tada gauti viduje, kad mazgas ir gauti savo lauką, vadinamą n. Ir tada palyginti faktinį n, kad buvo perėjo į paieškos prieš jį. 

Taigi, jei n yra mažesnis nei n vertę Medyje mazgas pati, gerai, Ką tai reiškia? Tai reiškia, kad nieko iš pirmo žvilgsnio. Teisė? Tiesiog patinka, kai jūs turite masyvas vertės, galbūt jūs norėtumėte taikyti dvejetainis ieškoti kaip atskirties forma ir užkariauti. Bet kas prielaida buvo mums reikia, kad komponentų paiešką dirbti ne visi telefonų knygoje ir ankstesni pavyzdžiai? 

Kaip turi būti išspręstos. Taigi, galime patobulinti medžio apibrėžimas čia negali būti tik medis, kuris gali turite vaikų skaičių. Ne tik dvejetainis medis, kuris gali turi 0, 1, arba 2 maksimaliai. Bet kaip dvejetainis paieškos medis, arba BST kuri yra tik išgalvotas būdas pasakyti dvejetainis medis, pavyzdžiui, kad kiekvienas mazgas kairėje vaikas, jei yra, yra mažiau nei mazgas. Ir kiekvienas mazgas teisė vaikas, jei yra, yra didesnis nei mazgas pati. 

Taigi, kitaip tariant, jei jums buvo atkreipti medis iš, visus numerius yra tinkamai subalansuoti taip, kad jei jūs turite 55 kaip šaknis, 33 gali eiti jo kairėje, nes ji yra mažiau nei 55. 77 galite pereiti į savo teisę, nes tai didesnis nei 55. Bet dabar pastebėti, tą patį apibrėžimą, tai rekursinis apibrėžimas žodžiu, turi taikyti 33. 33 kairės pusės vaikas turi būti mažesnis nei tai, ir 33 teisė vaikas, 44, turi būti didesnis nei jo. 

Taigi tai yra dvejetainis paieškos medis, ir Aš siūlau, naudojant šiek tiek rekursija, dabar mes galime rasti n. Taigi, jei n yra mažesnis nei reikšmė N, kad yra dabartinis mazgas, aš ruošiuosi eiti į priekį ir kamuolio išmušimas iš rankų, taip sakant, ir tik grįžti bet atsakymas yra ieškoti n nuo medžio kairėje vaikas. Pranešimas vėl, ši funkcija tiesiog tikisi mazgas STAR ženklu, rodyklė mazgas. Taigi tikrai galiu tik daryti medį rodyklė į kairę, kuris bus mane į kitą mazgą. Bet kas tai yra mazgas? 

Na, pagal šią deklaraciją, Kairėje pusėje yra tiesiog rodyklė, kad tik tai aš einančios į paieškos funkcija skiriasi rodyklė, ty vienas, kad yra mano kairę vaiko medį. Taigi šiuo atveju, rodyklė į 33, jei tai yra mūsų pavyzdys įvesties Tuo tarpu, jei n yra didesnė už vertę n, dabartinis mazgas medžio, tada aš ketina eiti į priekį ir kamuolio išmušimas iš rankų į kitas kryptis ir tiesiog pasakyti, aš ne žinoti, jei ši vertė n yra medyje, bet aš žinau, jei ji yra, tai žemyn mano teisė filialas, taip sakant. Taigi leiskite man skambučių rekursyviai ieškoti, Praėję n vėl, bet einančios rodyklė mano dešinėje vaikui. 

Kitaip tariant, jei aš šiuo metu 55 ir aš ieškau už 99, aš žinau, kad 99 yra didesnis nei 55, taip kaip aš persiplėšė telefonų knyga savaites ir mes nuskriejo tiesiai, panašiai mes esame ketina eiti čia. Ir aš nežinau, jei tai ne mano dešinėje vaikas, ir tai ne, 77 yra, bet Žinau, kad ta kryptimi. Taigi aš vadinu paiešką mano dešinėje vaikas, 77, ir tegul paieškos paveikslą iš ten, jei 99 tai savavališkas pavyzdys yra iš tikrųjų ten. 

Kitur, kas galutinis atveju? Jei medis yra niekinis yra vienas atvejis. Jei n yra mažesnis nei dabartinis mazgas vertė yra kitas atvejis. Jei n yra didesnis nei dabartinis mazgas vertė yra Trečiasis atvejis. Kas ketvirtas ir paskutinis atvejis? Manau, kad mes iš atvejų, tiesa? Jis turi būti, kad n yra dabartinis mazgas, kad aš ant. 

Taigi, jei aš ieškoti 55 šiuo metu į istoriją, kad filialas medis sugrįš tiesa. Taigi, kas įdomu tai, kad mes iš tikrųjų, skirtingai nuo savaitėmis anksčiau, mes natūra iš turi dvi pagrindo atvejus. Ir jie neturi būti visi viršuje. Viršuje yra bazinį scenarijų, nes jei medis yra niekinis, nieko daryti. Tiesiog grįžti sunkiai koduojami vertė neteisinga. 

Apačioje filialas yra tarsi pagal nutylėjimą, pagal kurią, jei mes tikrinamas null, mes patikrino, ar ji turėtų būti į kairę, bet tai neturėtų būti, mes patikrino, ar ji turėtų būti gerai, bet jis neturėtų būti, aiškiai jis turi būti ten, kur mes esame. Štai bazinį scenarijų. Taigi, čia yra du pasikartojantys atvejai įtvirtinta ten viduryje. Bet aš galėjo parašyti tai bet kokia tvarka. Aš tiesiog pagalvojau, kad rūšies jaučiamas natūralus pirmiausia patikrinti dėl galimos klaidos, tada patikrinkite, ar į kairę, tada patikrinkite, ar teisinga, tada manyti, kad esate ne mazgas jūs iš tikrųjų ieško. 

Tad kodėl tai galėtų būti naudinga? Taigi paaiškėja - ir leiskite man pereiti į kibinimas čia tai į internetą. Mes ketiname pradėti naudoti ne programavimo kalba per pirmąjį, tačiau žymėjimo kalba. Žymėjimo kalba yra viena, kad panašios dvasios programavimo kalba, bet tai nesuteikia Jums gebėjimas išreikšti save logiškai. Ji tik suteikia jums galimybę išreikšti save struktūriškai. 

Jeigu norite įdėti kažką puslapyje, interneto puslapis? Kokios spalvos norite padaryti? Kas šrifto dydį jūs norite padaryti? Kokiais žodžiais jūs iš tikrųjų noriu tinklalapyje? Štai žymėjimo kalba. Bet tada mes labai greitai pristatyti Javaskriptą, kuris yra pilnavertis programavimo kalba. Labai panašus sintaksiškai išvaizda iki C, bet teks kai gražus, galingesnis, daugiau patogios funkcijos. 

Ir vienas iš nusivylimų į tai taškas semestrą yra tai, kad mes atsiųsime greičiau įgyvendinti speller kur kas mažiau eilučių kodo, naudojant kitas kalbas nei C leidžia daryti, bet priežastis ųjų mes greitai suprasti. Tai bus pirmasis toks tinklalapis. Tai bus visiškai underwhelming, Pirmasis mes darome. Tai bus tiesiog pasakyti, hello world. Bet jei jūs niekada matė jį anksčiau, tai yra, HTML, Hypertext Markup Language. 

Jeigu jūs einate į tam tikrą meniu pasirinkties labiausiai bet kokia naršykle, bet interneto puslapyje interneto, jūs galite pamatyti HTML kad kai kurie žmonės rašė sukurti, kad interneto puslapyje. Ir tai tikriausiai neatrodo taip trumpas arba tvarkingas, kaip šis. Bet tai bus sekti jų pavyzdį atviros gembės ir nerijos ribos ir raidės ir galimai numeriai. 

Aš maniau aš jums kibinimas nuo to, ką galėsite padaryti po to, kai CS50. Leiskite man eiti į cs.harvard.edu / Rob, mūsų pačių Rob Bowden puslapį. Jis padarė tai už mus. Taigi, jūs netrukus galės tai padaryti. Ir taip pat, ką girdėjote šį rytą - ką girdėjote šį rytą - 

[Hamster ŠOKIŲ MUZIKA] 

- Ty jūs galėsite padaryti tai. Kad mūsų laukia trečiadienį. Pamatysime jums tada. 

[Hamster ŠOKIŲ MUZIKA] Davidas Malan: Kitame CS50 -