DAVID Malan: U redu. Dobrodošli natrag u CS50. Ovo je početak tjedna 8.. I sjećam taj problem set završio 5. s malo izazov. Dakle, uz pretpostavku da oporavio sve vaše nastavnih Fellows i tvrtke CA fotografije u card.raw datoteke, imate pravo Sada se nalaze svi ti ljudi, i jedan sretan dobitnik će hodati s jednom od ovih stvari, skok motion uređaj koji možete koristiti za konačni projekte, na primjer. 

To, svake godine, dovodi do malo creepiness. I tako ono što sam mislio da ću učiniti je podijeliti s vama neke od obveza koje otišao natrag i naprijed preko Osoblje popis kasno. Primjerice, samo prošle noći, citat Citat završen, iz jednog od osoblja Članovi: "Upravo sam imao studentsku kucanje na mojim vratima da biste snimili fotografiju sa mnom. Stalkers, kažem vam. "Započeli prilično opisno i onda smo se preselili na, sat vremena kasnije, "morao sam Student me čeka nakon sekciji i on je imao sve naše imenima i fotografijama na neke listove papira. "U redu. Dakle, organizirao, ali ne sve to jezivo još. 

Zatim, "bio sam izvan grada ovaj vikend, i kad sam se vratio, bio je jedan u moj spavaća soba. "[smijeh] DAVID Malan: Sljedeći citat je iz osoblja Član, "student došao u moju kuću, na Somerville u 4:00 jutros. "Sljedeća osoblja, "dobio sam u moj hotel u San Francisco i student je čekao ja u predvorju s tri DSLR. " Tip kamere. "Ja nisam ni na osoblje ovaj semestar, , ali učenik je provalio u moju kuću ovo ujutro i snimio cijelu stvar sa Google stakla. "I onda na kraju, "Najmanje 12 ljudi željno čeka na mene kad sam dobio iz moje limo, a onda se probudio. "U redu. Tako među fotografijama, kao što svibanj Podsjetimo, taj momak se ovdje, tko si Možda znate što Mila Banana, koji živi s Lauren Carvalho, naše glave demonstrator. Milo Milo, dođi ovamo dječaka. Milo. Milo. Da se podsjetimo, on je nosio Google Glass, tako mi ćemo vam pokazati sve to poslije. Dakle, ovo je Milo ako bi željeli fotografirati s njim nakon toga. Ako želite paziti na publiku tamo. OK. To je dobra snimka. Pa, Milo Banana. Oh, ne radite to. 

[Smijeh] 

OK. Dakle, riječ onda o tome što je pred nama, jer kao što smo početi tranziciju, ovaj tjedan konkretno, iz C u naredbenog retka okruženje za PHP i JavaScript i SQL i HTML i CSS u web-based okruženju, mi ćemo biti u te opremanje sa svim više znanja za potencijalni konačne projekte. Prema tom cilju, kolegij ima tradicija održavanja seminara koji su na tangencijalno teme u tijeku. Jako puno se odnose na programiranje i na app razvoj i tako dalje, ali ne nužno istražiti tijek vlastiti nastavni plan i program. 

Dakle, ako ste možda zainteresirani za jedan ili više od ovogodišnjih seminara, Registrirajte se na cs50.net/seminar. Postoje stariji seminari na cs50.net/seminars. I na određeno dosadašnjem za ovu godinu Nevjerojatne su Web Apps s Ruby na Tračnice, što je alternativa jezik za PHP. Računalno jezikoslovlje. Uvod u IOS, što je platforme koja se koristi za iPhone, a iPad razvoj. JavaScript za Web Apps, mi ćemo pokriti da, ali u ovom seminaru, vi ćete ići u više detalja. 

Leap Motion, tako da smo zapravo ćete imati neke od naših prijatelja iz Leap Motion, Sama tvrtka, pridružite nam se. Sutra, u stvari, pružiti kazaljka-na seminaru, ako od interesa za vas. Meteor.js, alternativna tehnika za Ne koristite JavaScript u pregledniku ali na poslužitelju. Node.js, što je jako puno U tom smislu, kao dobro. Elegantan dizajn Android. Android se vrlo popularna alternativa za iOS i Windows Phone i druge mobilne platforme. I Web Security aktivnu obranu. 

Dakle, u stvari, ako želite da se uključe u to, neka mi zabilježite ovo. Mi smo jako sretni reći da našim prijateljima u Leap Gibanja, što je početak - ovaj uređaj zapravo samo došao od prije nekoliko mjeseci - je velikodušno donirao 30 takvih uređaja u klasi za što više studenata, ukoliko što bih posuditi hardvera prema semestra kraja i koristiti ga za Stvarni konačni projekt. Oni podržavaju brojne jezike. Nitko od njih C, nitko od njih nije PHP, tako da napraviti jedan ili više od tih seminara moglo pokazati interes. I svi će biti sniman u događaj koji niste u mogućnosti osobno prisustvovati. Raspored biti objavljen putem e kako smo se zgusnuo sobe. 

I na kraju, ako idete u projects.cs.50.net, ovo je web stranica Držimo da je svake godine pozivamo ljudi iz zajednice, fakulteta, odjela, osoblje, i oba u izvan CS50 na predlaže projektne ideje. Stvari od interesa za studentske grupe. Stvari od interesa za odjela. Dakle, ne pojaviti tamo, ako ste bore s nesigurnošću o tome što ste sebi bih se borila. 

Dakle, zadnji put smo uveli nedvojbeno složenije strukture podataka nego što bih vidio u posljednjih nekoliko tjedana. Mi bi bili pomoću polja lijepa sretno kao korisno ako jednostavna struktura podataka. Onda smo uveli to, što Naravno povezane liste. A što je bio jedan od motiva za uvođenjem ovog strukturu podataka? Da? Što je to? 

PUBLIKA: Dinamički Veličina. 

DAVID Malan: Dinamički Veličina. Dakle, dok je u polju, morate znate svoju veličinu prije kad što ga izdvojiti. U povezana popisu, ne znaš Morate znati da. Možete jednostavno malloc, ili općenitije, izdvojiti dodatna čvora, takoreći, svaki put kad želite umetnuti više podataka. I čvor nema unaprijed određenih značenja. To je samo generički pojam koji opisuje nekakav kontejner koji smo koriste u našem strukturu podataka za pohranu Neki predmet interesa, koji je u to Slučaj se dogoditi da se cijeli brojevi. 

No, tu je uvijek tradeoff. Tako smo dobili dinamičke veličine podataka struktura, ali ono što mi platiti cijenu? Što je downside povezane liste? Da? 

PUBLIKA: zahtijeva više memorije. 

DAVID Malan: To zahtijeva više memorije, kako točno? 

PUBLIKA: [nečujno]. 

DAVID Malan: Točno. Dakle, sada smo pokazivače uzimam Dodatna memorija koje smo prethodno nije potrebno, jer je prednost od niza, naravno, da je sve što je granično, vratiti se natrag na leđa, što daje vam slučajni pristup. Jer samo pomoću uglata zagrada oznake, ili više tehnički pokazivač aritmetika, vrlo jednostavan dodatak, možete pristupiti bilo elementi u stalnom vrijeme. A u stvari, to je vrsta aludirati na još jedna cijena koju smo plaćati s povezani popis. 

Što se događa u trajanju od nešto poput pretraživanja, ako želim pronašli neke vrijednosti i iznutra povezanog popisa? Što znači moje trčanje vrijeme postali? Big O n. Ako je to riješeno u? Što ako struktura podataka je riješeno? Mogu li to učiniti bolje od big O n za traženje? Ne, jer u najgorem slučaju to bi moglo vrlo dobro biti riješeno, ali je broj tražiš moglo biti velika. To bi moglo biti broj 100, koji moglo se dogoditi da se sve je na kraju. I zato možete pristupiti jedino linked Popis u ovom provedbe od strane način svom prvom čvoru, ti si još uvijek vrsta od sreće. Morate proći cijelu stvar od prve do posljednje kako bi se pronašli da je velika vrijednost kao 100.. Ili kako bi se utvrdilo je li to Nije ni tamo. 

Dakle, ne možemo učiniti ono algoritma u podacima struktura koja izgleda ovako? Mi ne možemo učiniti binarna, jer binary search potrebna da smo imali s izravnim pristupom. Mi smo samo mogli skok od mjesta do Mjesto bez slijediti ove krušne mrvice u obliku od svih tih pokazivače. 

Sada, kako smo to provesti? Pa, ako ćemo ići na zaslonu ovdje, ako možemo brzo reimplement ove podatke Struktura - moj rukopis nije sve što je lijepo ovdje, ali pokušat ćemo. Dakle typedef rekonstruirati i što sam želite nazvati ovu stvar ovdje? Čvora. Tako ću počnemo. A sada, ono što treba da bude unutar struktura podataka za koje pojedinačno povezani popis? Koliko stavke? 

Dakle, dva. Jedan je prilično jednostavan. Dakle, int n. A mogli bismo nazvati n sve što želimo, ali to bi trebao biti int, ako smo provedbi povezane popis za Ints. A sada što se drugi Polje moraju biti? Struct čvor *. Dakle, ako mi je činiti struct čvor *, a onda sam mogu staviti i što god želim, ali samo da bude jasno da ću zvati Sljedeći je, kao što smo radili. A onda ću zatvorim vitičastim zagradama. 

I sada, kao i zadnji put, Stavio sam čvor ovdje. Ali ako sam izjavljujući kako je to čvora, zašto se uopće trudim se tako verbose ovdje u izjavi struct čvora * iduće, za razliku od na samo čvora * sljedeći? Da? 

PUBLIKA: [nečujno]. 

DAVID Malan: Točno. Točno. Zbog C stvarno vam se doslovno i vidi samo definiciju čvora put ovdje, ne možete odnosi se na to ovdje. Dakle, imamo ovu vrstu preventivni Izjava ovdje, što je doduše mnogo opširnije. Struct čvor, to znači da sada možemo pristupiti unutar strukture podataka. 

I kao na stranu, jer je to postaje malo više subjektivna sada, star tehnički može ići ovdje, to može ići ovdje, to može čak i ići u sredini. Mi smo usvojili, u stilu vodič za Tečaj, Konvencija o stavljanju Zvijezda tik do podataka Vrsta, koja je u ovom slučaju, bi se rekonstruirati čvor. Ali shvatite u puno udžbenika i online reference, možda je doista vidjeti na drugoj strani. No, samo shvatiti da će oba zapravo rad i jednostavno bi trebao biti dosljedni. 

U redu. Dakle, to je bio naš izjava od struct čvor. Ali onda smo počeli raditi više sofisticirane stvari. Na primjer, odlučili smo uvesti nešto kao hash tablicu. Dakle, ovdje je hash tablicu veličine n, indeksirane od 0 na gornjem lijevom do n minus 1 na dnu lijevo. To bi mogao biti hash stol za ništa. No, ono što vrste stvari koje smo razgovarati o korištenju hash tablicu? Pohranjivanje što? 

Imena. Mogli bismo napraviti imena kao što su smo prošli put. I doista, možete pohraniti ništa. A mi ćemo to opet vidjeti u PHP i JavaScript. Hash tablica je lijepa vrsta Švicarski Vojska nož koji vam omogućuje pohranu skoro sve što želite unutar to pridružujući tipke s vrijednostima. Tipke sa vrijednostima. 

Sada u ovom jednostavnom slučaju, naš Tipke su samo brojevi. Mi smo provedbi hash Tablica kao polje. I tako su tipke 0, 1, 2, i tako dalje. I tako smo, kao ljudi, odlučio je prošlog tjedan da znate što, ako smo ide za pohranu imena, hajdemo proizvoljno, ali prilično razumno, Pretpostavljam da je Alice, ime, Samo će se indeksiraju u 0. I Bob, B ime, bit će indeksirana u 1, i tako dalje. Tako smo imali mapiranje između inputa, koji su nizovi i hash mjesta, koje su brojevi. 

Tako da je proces općenito je poznat kao hash funkcija, a možete istinski implementirati ga u kodu. Ako sam htjela provesti hash funkcije koji radi upravo ono što smo Upravo opisani na posljednji put, mogao bih proglasiti funkciju koja uzima, kao ulaz za primjer - i neka je to učiniti na ovaj Zaslon ovamo. Ako sam htjela provesti hash funkcija, mogao bih reći nešto poput ovoga. 

To će se vratiti int. To će se zvati mljeveno meso, i to je će prihvatiti kao argument u string, ili možemo biti pravilno sada, i reći char *, nazvat ćemo ga s. I onda sve to ima funkciju učiniti, u konačnici, je vratiti int. Sada, kako se to radi da bi mogli Nije se tako jasno. Ja ću provesti to bez bilo oblik kontrole pogrešaka upravo sada. Samo ću reći da se slijepo, vratite sve što je na konzoli s 0, minus, recimo, grad-zarezom. 

Totalno slomljena. To nije idealno, jer jedan, što ako je null? Loše stvari će se dogoditi. Dvije, što ako prvo slovo u ovom ime nije slovo? To se neće pretvoriti iz dobro bilo. To bi moglo biti malo slovo ili ne pismo na sve. Dakle, potpuno prostora za poboljšanje ovdje, ali to je osnovna ideja. 

Ono što smo prošlog tjedna opisao kao verbalno Upravo proces mapiranje Alice se 0 Bob i do 1 može se izraziti sigurno više formulaically kao C funkcionirala. Nazvan ponovno hash, ima niz kao ulaza, a onda nekako čini nešto s tim input za proizvodnju izlaz. Nije za razliku od naše crne kutije opisa da smo dugo ste učinili. Ja ne znam kako bi to moglo biti rade ispod poklopca motora. 

Za problema set 6, jedan od izazova je za vas da odlučite što će vaš hash funkcija biti? Što se događa da se unutar tako crno box, i vjerojatno, to će biti malo zanimljivije od ove, i definitivno više skloni pogrešci ček od toga posebno Provedba. 

No, problemi mogu nastati, zar ne? Ako imamo strukturu podataka kao što je to jedan, što je jedan od problema možete izvoditi u tijekom vremena kao što ste umetnuli sve više i više imena u hash tablicu? Vi se sudari, zar ne? Što ako imate Alice i Arona, Dvije osobe čija imena se dogodilo za početak? To postavlja pitanje, gdje se staviti drugi takav naziv? 

Pa, što naivno možda samo ga stavi Bob kojoj pripada, ali onda je Branimir vrsta pijan ako pokušate ubacite svoje ime, a sljedeći nema mjesta za njega. Dakle, možda mu Boba gdje je Charlie, a možete zamisliti vrlo brzo devolving u malo nered. Nešto linearno na kraju, gdje se Samo morate tražiti cijelu stvar u potrazi za Alice ili Bob ili Aaron ili Charlie. 

Dakle, umjesto da smo predložili, umjesto da samo linearno sondiranje za otvorene prostore i plopping imena postoji, mi predložio ljubitelj pristup. Hash tablicu provodi još uvijek s Niz indeksa, ali Tip podataka ti indeksi sada su pokazivače. Kazaljke na što? Kazaljke na povezane liste. 

Budući da je opoziv vezan popis zapravo samo pointer na čvoru, a čvor ima sljedeće polje i na taj čvor ima sljedeći polje, i tako dalje. Dakle, sada možete misliti na ovom polju lijeva strana od hash tablicu kao i što dovodi do povezane popisa. Prednost što je, ako dobijete sudara između Alice i Arona, Što ćete učiniti s Druga takva osoba? Vi samo ga spojiti ili joj na kraju, ili čak početak te povezane liste. 

I doista, neka je samo kroz rezance da je samo na sekundu. Gdje bi najviše smisla? Ako ubacim Alice i ona završi u prvo mjesto, onda ću pokušati umetnite Aronov ime, a tu je Očito sudara, trebao sam staviti ga je na početku vezanog popisu? To je u tom prvom mjestu, ili na kraju? 

PUBLIKA: [nečujno]. 

DAVID Malan: OK. Čuo sam počinjao. Zašto na početku? 

PUBLIKA: [nečujno]. 

DAVID Malan: OK. To je po abecedi, tako da je lijepo. To je dobro svojstvo. To će uštedjeti me neko vrijeme potencijalno. Neće mi dopustiti binarna, ali ja možda barem biti u mogućnosti to break out od petlje ako shvaćam, dobro, ja sam smjer Posljednjih su Aron bi se u ovo razvrstani povezanu popis. Ja ne moram gubiti svoje vrijeme u potrazi sve do kraja. Dakle, to je razumno. Zašto bi inače možda želite umetnuti sudaraju ime po počevši od popisa? Što je to? 

PUBLIKA: [nečujno]. 

DAVID Malan: To bi moglo potrajati dugo vremena da bi se na kraju popisa. A u stvari, sve dulje i dulje. Što više imena ulažete kako početi s, više ne da Lanac će doći. Duže da povezana Popis će doći. Pa ti si zapravo samo troši svoje vrijeme. Možda ste bolji od održavanju konstantna umetanja vrijeme, big O od 1, strane uvijek stavljajući u sudaru na ime početak povezanoj popisu a ne brinući se koliko o razvrstavanje. 

Koji je najbolji odgovor? To je nejasno. To je vrsta ovisi o tome što distribucija, ono što je obrazac od imena što su umetanja. To nije nužno Očigledan odgovor. No, ovdje se, opet, Dizajn priliku. 

Pa smo zatim pogleda na tu stvar, koja stvarno druga velika prilika za p-set 6. I shvatite, ako već niste, Zamyla uranja u obje ove, hash Stolovi i napad, u više detalja. I videoupute je ugrađen u p-set spec.. Ovo je trie - T-R-I-E. I ono što je zanimljivo kod to je da se trajanje u potrazi za ime, kao što je Maxwell zadnji put, bio je veliki O čega? Što je to? 

PUBLIKA: broj pisama. 

DAVID Malan: Broj slova. Čuo sam dvije stvari. Broj pisama i stalne vrijeme. Dakle, idemo s tim prvi put. Broj pisama. Pa, ova struktura podataka, podsjetimo, je poput stabla, obiteljsko stablo, svaki od čiji čvorovi su sastavljene od polja. I oni su nizovi pokazivači ostali takvi čvorovi, ili druge kao što nizovi u stablo. 

Dakle, ako smo htjeli onda odrediti Maxwell je li ovdje, mogao bih otići u prvi niz, na samom vrhu stabla, tzv korijena, vrh trie, a zatim će slijediti pokazivač m, zatim pokazivač, a zatim x, w, e, l, l. I onda kad vidim neki posebni simbol, označava se kao trokut. U kodu vidjet ćete predlažemo da implementiran kao bool, samo kaže da ili ne, riječ prestaje ovdje. 

Pa, kad smo otišli na M-A-X-W-E-L-L, osjeća kao sedam, možda osam ako idemo jedan mimo njega osam koraka kako pronaći Maxwell. Ili nazovimo ga K. Ali sjećam posljednja Tada sam tvrdio da, ako postoji realno Maksimalna duljina na Riječ, kao što je 40-neke-ak likova, Maksimalna duljina podrazumijeva konstantna vrijednost. Pa stvarno, da, to je veliki tehnički O od 8 ili 7, odnosno uistinu velikom izlaznom K. But ako postoji konačna kapu na ono što K može biti, to je konstanta. I to je velika O od 1 na kraju dana. 

Nije u stvarnom svijetu. Ne kada zapravo početi gledati vaš sat kao svoga programa trčanja. To apsolutno će biti malo sporije nego što doista konstantna vrijeme s jednim korakom. To će biti sedam ili osam koraka, ali još uvijek je to puno, puno bolje od algoritma poput velikog O n te ovisi o veličini ono što je u struktura podataka. 

Obavijest upside ovdje možemo ubaciti milijun više imena u to struktura podataka, no koliko još koraka je li će nas odvesti pronaći Maxwell je u tom slučaju? Nitko. On je nepromijenjen. I do sada, ja ne mislim da smo vidjeli Primjer podataka strukture ili algoritam koji je bio kompletno nepromijenjen prema vanjskim ponašanja kao što je to. No, to ne može biti nevjerojatna. To ne može biti jedino rješenje za p-set 

I to nije. To nije nužno podatke Struktura trebali težiti ka, jer kao što je hash tablica, tradeoff. Koja je cijena koju plaćaju ovdje? Memorije. Mislim, ovo je grozno količinu memorije. I ne mogu sasvim ga vidjeti ovdje, jer Autor ove slike očito odrezan sve polja, i mi ne vidimo puno ih i B-a i C-ih i Qa i Y-a i Z-ih u tim polja. No, oni su tu. 

Svaka od tih čvorova je cijeli niz nekih 26 ili više bajtova, svaki od što predstavlja pismo. 27 u našem slučaju, tako da možemo podržati apostrofe u setu problema. Dakle, ovo je stvarno struktura podataka, jako gusta i široka. I to samo može završiti usporavanje stvari dolje, ili barem da košta puno više prostora. Ali opet, možemo izvući Usporedbe ovdje. 

Podsjetimo, a leđa, postigli smo mnogo više uzbudljivo vrijeme rada u rješavanju kada koristimo spajanje vrsta, ali cijena platili smo za postizanje n log n za spajanje sortiranje zahtijeva da trošimo više što je resurs? Više prostora. Trebali smo srednju polje za kopirati ljudi u, baš kao i jesmo ovdje na pozornici. Pa opet, nema jasnih pobjednika, ali samo subjektivni design odluke donose. 

U redu. Pa kako o tome? Svatko prepoznaje koji D-Hall? OK. Dakle, tri od nas učiniti. Mather House. Dakle, ovo je za Mather je blagovanje. Kladim se da svi imaju blagovaonice hrpe ladicama ovako. A to je zapravo prikazuje nečega što smo Očito već vidjeli. Mi ga zove doslovno hrpu. I stog, u smislu svoje memorije računala, gdje podaci ide dok je funkcija se zove. 

Na primjer, ono Å¡to vrste stvari idu na stog u odnosu na Raspored memorije smo razgovarali u posljednjih nekoliko tjedana? Å to je to? 

PUBLIKA: Pozivi na funkcijama. 

DAVID Malan: Žao mi je. 

PUBLIKA: Pozivi na funkcijama. 

DAVID Malan: Pozivi na funkcijama, ali Naime, ono što je unutar svake od ti okviri? Koje vrste stvari? Da. Dakle lokalnim varijablama. Bilo mi je potrebno neko lokalnu pohranu, kao argument, ili sam int, int ili temp, ili što god lokalnim varijabla, mi smo bili stavljanjem na stog. I mi to zovemo, jer stog tog raslojavanje ideje. Samo vrsta utakmice sa stvarnošću, Koncept tome. 

No, ispostavilo se da je snop također mogu se vidjeti kao strukture podataka, alternativa niz, alternativna povezanog popisa. Nešto konceptualno zanimljiviji da još uvijek može biti provodi ili pomoću onih stvari, ali to je drugačiji tip struktura podataka podržava, uistinu, samo dvije operacije. No, možete dodati na fancier obilježja od tih. No, to su osnove - push i pop. 

A ideja s hrpom je da ako sam ima ovdje, sa ili bez uzivo znajući, pladanj iz susjedstva s brojem 9 na njemu. Dakle, samo int. I želim gurnuti ovo na podacima struktura, koja trenutno je prazna. Razmotrite ovo dno stoga. Ja bi gurnuti taj broj 9 na stog, a sada je tamo. 

Ali zanimljiva stvar o hrpi je da ako ja sada želim gurati neke druge vrijednosti, kao što su 17, a ja sam gurati ovo na stog, ja ću učiniti Samo intuitivno stvar, samo ću Da bi se to upravo tamo gdje mi ljudi će biti skloni da ga stavite na vrh. No, ono što je zanimljivo sada je, kako mogu dobiti na 9? Znate, ja to ne bez nekog napora. 

Dakle, ono što je zanimljivo kod stog je da je po dizajnu, to je struktura LIFO podataka. Glup način opisuje posljednja u, prvi van. Dakle, zadnji broj u u to vrijeme imao 17 godina. Dakle, ako želim nešto pop off iz dimnjaka, to može biti samo 17. Dakle, postoji obvezni redoslijed operacija ovdje, gdje je zadnja stavka u mora biti prvi van. Dakle akronim, LIFO. 

Pa zašto bi to bilo korisno? Jesu li njihove situacije u kojima bih Želite strukturu podataka kao što je ovaj? Pa, sigurno je bio koristan unutar računala. Dakle, operativni sustavi očito koristite ovu vrsta podataka strukture za dimnjake. Također ćemo vidjeti istu ideju kada je u pitanju web stranica. Dakle, ovaj tjedan i sljedeći tjedan i izvan nje, i kao što ste početi provoditi weba stranice u jeziku zove HTML, možete zapravo koristiti podatkovnu strukturu kao ovo bi se utvrdilo je li stranica pravilno formatiran. Budući da ćemo vidjeti sve web stranice pratite vrst hijerarhije, udubljenje da će se, na kraju dana, se Stablo struktura ispod haube. Dakle, više o tome u samo malo. 

Ali za sada, neka je predloži za Trenutak, kako bismo mogli ići o predstavlja ono što je stog? Dopustite mi predložiti da realiziramo stog s kodom kao što je ovaj. Dakle, stog će imati unutar nje dvije stvari, Array, nazivaju pladnjevi, Samo treba biti u skladu s demo. A svaki od stavke u tom polju će biti tipa int. A kapacitet je valjda ono? Budući da sam nije zapisano puna definicija ovdje. 

To je vjerojatno najveća Veličina polja. I to je vjerojatno proglašen oštra definirati na vrhu datoteke, neki vrsta konstante kao implicira Sama kapitalizacije. Dakle, negdje kapacitet definira kao najveću moguću veličinu. U međuvremenu, unutar strukture podataka poznat kao stog postoji volja biti cijeli samo poznat jednostavno kao veličinu. 

Dakle, ako mi je ovo sada predstavljaju slikovito, pretpostavimo da je to Cijeli crna kutija predstavlja moju hrpu. Unutar nje je dvije varijable. Tako ću se izvući Prvi su veličine. I drugi ću crtati kao polje. 

No, samo da bi stvari uredno, normalno ja bi privući niz poput to, ali to je vrsta lijepo ako mi odgovarati stvarnosti, ili odgovarati mentalni model. Pa neka mi umjesto nacrtati niz vertikalno, što je samo, opet, umjetničko tumačenje. Da li stvarno ne smeta što se ispod poklopca motora. A mi ćemo reći da je, po defaultu, Kapacitet će biti tri. Dakle, ovo će biti location 0, ovo će biti mjesto 1, ova će se 2. Mjesto. 

Ako sam podmititi sa stresom loptu, bi netko kao da se i pokrenite ukrcaju ovdje samo na trenutak? OK, vidjela tvoja ruka prvi. Dođi gore. U redu. Dakle, ja vjerujem da je Steven. Dođi gore. U redu. 

Ali sada pretpostavimo da premotati na početno stanje svijeta u kojem sam Samo su proglasili hrpu, a to je će biti kapaciteta tri. No, veličina još nije utvrđena. Posude još nije utvrđena. Dakle, nekoliko pitanja na prvom mjestu. I neka mi vam mikrofon tako da možete aktivnije sudjelovati u tome. 

Dakle, ono što je unutar veličine u ovom trenutku u vremenu ako sve sam učinio je proglašen stog s jedna linija koda? 

STEVEN: Ne mnogo. 

DAVID Malan: OK, nije puno. Znamo li Å¡to je unutar dimenzija, Ne znamo Å¡to je unutra ovog polja ovdje? 

STEVEN: Samo slučajni broj, zar ne? Samo - 

DAVID Malan: Da, idem nazvati broj, ali slučajni - 

STEVEN: Stvari. 

DAVID Malan: Stvari kao slučajna 

STEVEN: Bits. 

DAVID Malan: Bits, zar ne? Dakle smeće vrijednosti, zar ne? Dakle permutacije od 0-a i 1-a. Ostaci prethodne uzance ove memorije. I mi zapravo ne znaju što su vrijednosti su, pa smo obično ih privući kao upitnicima. 

Dakle, prva stvar koju smo valjda će se želite učiniti ovdje - i neka mi daju ovo polje unutar odatle naziv - ladice. Što bi mi vjerojatno započeti Veličina se, ako želimo početi koristiti ovu hrpu? 

STEVEN: Ladica je pod 3. 

DAVID Malan: Pa, OK. Da bude jasno, kapaciteti se proglasio drugdje tri. I to je ono što sam koristiti kako bi se alocirao niz. Veličina se događa da se odnosi na koliko je ladice su trenutno na stog. 

STEVEN: Zero. 

DAVID Malan: Pa to bi trebalo biti nula. Dakle, ići naprijed, i sa bilo prstom, povući nulu u veličini. U redu. Tako sada, što je unutar ove ovdje, mi ne znamo. To su zapravo samo smeće vrijednosti. Tako smo mogli izvući upitnike, ali neka je zadržati odbora za sada čisto jer to nije važno što je tamo. Ne trebamo li pokrenuti niz na bilo što, jer ako znamo da je veličina stog je nula, pa, Ne treba se gleda bilo što u Taj niz svejedno, na ove točke u vremenu. 

Dakle, pretpostavimo da sada sam gurati broj 9 na stog. Kako bismo trebali ažurirati strukturu podataka unutar ove crne kutije? Koje vrijednosti treba promijeniti? 

STEVEN: U - Veličina? 

DAVID Malan: OK. Veličina trebao postati ono? 

STEVEN: Veličina bi biti jedan. 

DAVID Malan: OK. Dakle, veličina trebala bi postati jedan. Dakle, možete to učiniti na nekoliko načina. Dopustite mi da vam dati, sada vaša Prst je gumica. U redu. Tada je sada prst je četkica. U redu. I sad ono što drugi ne mora mijenjati, Očito, u strukturi podataka? 

STEVEN: Idemo na dna do 9. 

DAVID Malan: 9. OK, dobro. Dakle, još uvijek ne smeta što je na Mjesto na jedan ili dva, jer oni su Kante vrijednosti, ali mi ne bi trebali zamarati upravo tamo, jer je veličina nam govori da je samo prvi element je zapravo legitimna. Dakle, sada sam gurati 17 na popisu. Što se događa s ovom slikom? 

STEVEN: Dakle, veličina će ići u dva. 

DAVID Malan: OK. Ti si gumicu - Ups. Ti si gumicu. 

STEVEN: Eraser. 

DAVID Malan: Ti si četkica. 

STEVEN: Četka. 

DAVID Malan: OK. A Å¡to drugo? 

STEVEN: I onda mi - 

DAVID Malan: Mi gurnula 17. 

STEVEN: Držimo 17 na vrhu, tako da - 

DAVID Malan: OK, dobro. 

STEVEN: - to pasti. 

DAVID Malan: U redu. To je sve lako. Neću vam pomoći da ovaj put. Push 22. 

STEVEN: Done. Postati gumicu. Ja sam sve četke. A onda sam stavljajući 22. 

DAVID Malan: 22. Izvrsno. Dakle, još jednom. Ja sad idem na guranje na stog 26. 

STEVEN: Ooh. Oh Bože. Stvarno mi je uhvaćen off straže. 

DAVID Malan: Nije ti vidjeti ovaj dolazak? 

STEVEN: Nisam vidio ovaj dolazak. Možemo ponovno Početni kapacitet? 

DAVID Malan: To je dobro pitanje. Tako smo vrsta sebe naslikao u kutu ovdje. Zapravo ne postoji dobra strana za Stjepana jer smo dodijeljen ovaj niz statički, da se tako izrazim, unutar strukture podataka. I mi smo u biti teško kodirano da bude od veličine tri. Dakle, ne možemo ga preraspodijeliti. 

Mogli bismo, ako smo se vratili u, mi redefinirati ladice da se pokazivač koji smo zatim koristiti malloc u ruku memorije. Jer ako mi je sjećanje na heap putem malloc, mi mogao zatim ga osloboditi. No, prije nego što ga oslobađa, što smo mogli preraspodijeliti veći komad memorije, ažurirali pokazivač, i tako dalje. Ali za sada, ovo je stvarno najbolje što možemo učiniti. Push i pop vjerojatno se ide se moraju signalizirati neke pogreške. 

Tako, primjerice, ostvarenju push mogao vratiti bool koji prije vratio istina, istina, istina. No, četvrti put, to će imati vratiti false, primjerice. U redu. Vrlo dobro učinio. Čestitamo. Vi ste zaradili svoj stres loptu i danas. 

[PLJESAK] 

STEVEN: Hvala vam. 

DAVID Malan: Hvala vam. U redu, tako da to izgleda kao da se nije puno od korak naprijed, zar ne? Mi opisao ovu strukturu podataka. To je bio uvjerljiv, zar ne? Operacijski sustavi se svidjeti. Navodno web može iskoristiti ovu, i druge aplikacije još uvijek. No, ono glupo ograničenje da smo natrag na svojevrsni tjedan dvije granice gdje smo fiksne veličine polja. 

Dakle, zbilja postoji par načina možemo riješiti ovo. Mi dinamički mogao dodijeliti niz, ne tvrdi to kodiranja kao što sam obaviti ovdje, ali umjesto toga ponovno izjavljuje ovo, samo da bude jasno, kao nešto poput ovoga. Int * ladice, ne odluči na kapacitetom još. Ali kad sam proglasiti stog negdje drugdje u mom kodu, onda sam mogao nazvati malloc, dobiti adresu od sitna memorije, i ja mogao dodijeliti koji se odnose na pladnjevima. 

A onda, jer to je samo komad memorije, mogao sam nastaviti koristiti trgu Nosač zapis na uobičajeni način. Jer opet, postoji neka vrsta ove funkcionalni ekvivalent polja i komadi sjećanja koje dolaze natrag na malloc. Mi možemo tretirati kao jedan drugi pomoću pokazivača aritmetike ili uglata zagrada zapis. Dakle, to je jedan pristup. 

No, kako se drugi možda smo implementirati ovaj ista struktura podataka, potencijalno? Točno? Osjećam se kao da smo upravo riješili ove problem kao što je prije tjedan dana. Što je rješenje za ovaj problem da je Steven naletjeli? Dakle povezane liste, desno. 

Ako je problem što smo slikanja sami u kutu dodjelom unaprijed premalo memorije koja smo onda su na neki način bave, dobro, Zato ne samo da bi se izbjeglo izdati uopce? Zašto ne samo izjaviti da se ladice pokazivač na čvor, Ergo povezani popis, i onda jednostavno izdvojiti novih čvorova svaki put Steven potrebno da stane Broj u strukturu podataka. 

Dakle, slika će morati promijeniti. To neće biti čist i kao jednostavan kao samo niz od tri Ints. Sada će biti pokazivač rekonstruirati, te da će se rekonstruirati imate int i pored upustvo. To će dovesti, preko tog pokazivača na neko drugo takvo struct se Još jedan takav rekonstruirati. Dakle, slika bi zapravo dobiti Messier bitni. I mi bismo strelice vezanje sve zajedno. 

Ali to je u redu, zar ne, jer se Vidjeli smo kako to učiniti. I jednom kada se udobno provedbi nešto poput linked Popis, koji ćete morati učiniti ako odlučite provesti hash tablicu s odvojeni ulančavanje za p-set 6, možete ga koristiti kao građevinski blok, ili na sastojak, ili u nule govoriti, Postupak, nešto što ste stavili, ti stvorili svoj vlastiti slagalice koji onda možete ponovno koristiti. Dakle kompromise, ali mogućih rješenja da smo zapravo prije nisam vidjela. 

Dakle, vrlo često, vidiš ovo svaki godinu ili dvije kad Apple releases nešto novo, a svi su ludi ljudi ravnini izvan Apple pohraniti kupiti njihov marginalni nadogradnju na hardveru. Kažem to, to je u redu, jer je Ja sam jedan od tih ljudi. Pa kakav strukture podataka moglo predstavljati ovu stvarnost? 

Pa, nazovimo je red, red. Tako će Britanci zovu obično red svejedno, tako da je lijepo ime. A dvije operacije koje queue će podržati ćemo pozvati enqueue rad i dequeue operacije, koje su slične u Duh gurati i pop. To je samo neka vrsta razlikuje u Konvencija, što mi to zove. No, kako bi enqueue nešto znači dodati ili ga stavite na strukturu podataka. Za dequeue znači da biste ga uklonili. No, dok je snop LIFO podataka struktura, red je prvo u, Prvi iz strukture podataka. 

Ako ste prva osoba u liniji, što će biti prva osoba koja se iz linije i kupiti novi uređaj. Zamislite koliko je uzrujan ti ljudi bi se ako Apple umjesto da se koristi snop, za Primjerice, za provedbu te preuzimaju do vašeg novom igračkom. Dakle redovi smisla, svakako, i možemo sjetiti svih vrsta aplikacija, vjerojatno, za redove, pogotovo kada želite pravičnost. Dakle, kako bismo mogli provesti te kao struktura podataka? 

Pa, predlažem da bismo mogli trebate napraviti na ovaj način. Tako da ću sada imati brojeve. Tako ćemo zadržati jednostavan i ne nužno govoriti u smislu ladice. Samo brojevi koji narod stečen. Kapacitet će se, opet, riješiti Ukupan broj ljudi koji mogu biti u ova linija, tri ili god druga vrijednost. 

No, predlažem da moram pratiti ne samo na veličinu red, koliko su stvari u njemu. Dakle, veličina je trenutna veličina, kapacitet je maksimalna veličina. Samo jednom, nomenklatura po konvenciji. Zašto mi je potrebna dodatna int unutar o redu za pratiti tko je u ispred linije? Zašto trebam to učiniti u ovom slučaju? 

Pa, kako je ova slika će se promijeniti? Ja vjerojatno može ponovno najviše ove slike. Dopustite mi da ide naprijed i izbrisati ono što je ovdje. Mi ćemo dati to malo drugačije ime ovdje. Da biste dobili osloboditi od 17, neka riješi od 9., idemo dobiti osloboditi od tri. I dodajmo još jednu stvar. Predlažem da moram pratiti Prednji dio popisa, što je samo će biti int, kao dobro. I mi ćemo ga zadržati jednostavan. Nema povezani popis za sada. 

Mi ćemo priznati da smo idući u naletjeti na ove granice. No, ono što želim vidjeti dogoditi ovaj put? Dakle, pretpostavimo da idem naprijed i prva Osoba dolazi u liniji, a to je broj 9. Mi nemamo stres loptice. Mogu li kradu, recimo, dvije ili tri osobe? Jedan, dva, tri? Dođi gore. Desno sprijeda, jer ćemo napraviti ovo brzo. 

Svaki od vas sada će biti fan Dječak u redu na Apple. Nećete biti primanje Apple hardvera na kraju ove ipak. U redu. Dakle, ti si broj 9, ti si broj 17, broj 22. To su proizvoljne brojeve, kao što su studentske iskaznice ili sitnica. I u samo trenutak, započnimo za početak dodajući stvari. I ja ću pokrenuti matičnu ovdje ovaj put. 

Dakle, u ovom slučaju, ja sam inicijalizacije Prednji se - Ja sam zapravo stvarno ne briga što Prednji je, jer je veličina nula. Dakle, to možda i samo se Upitnik. To su sve upitnika. Dakle, sada ćemo početi vidjeti neke stvari ljudi podstava gore u trgovini. 

Dakle, ako je broj 9, ti si prvi tamo u 05:00, ići naprijed i postroje, ili večer prije. OK. Tako sada 9 je ovdje. Tako 9 je u prednjem dijelu popisa. Dakle, ja ću ići naprijed i ažurirati Veličina ovog aktualnih podataka struktura ne bi se više 0, , ali da se 1. Ja ću staviti na 9 Prednji dio popisa. Dopustite mi da ide naprijed i prebacivati ​​zaslon tako možemo vidjeti kraj nas ovdje. 

A sada što želim staviti na prednjoj strani? Ja ću pratiti da Pročelje red sada nalazi se na mjestu 0. Zato što je sljedeće što će se dogoditi? Pa, recimo sad sam enqueue 17, kao dobro. Dakle hop u skladu tamo. I opet, vrsta vrata Trgovina će biti ovdje. Dakle, sada sam dodao 17. I iako ti dečki su blokiranja zaslon, to je u redu, jer ga možemo vidjeti ovdje. Žao nam je. 

PUBLIKA: Možemo se - 

DAVID Malan: Ne, to je u redu. To je ogromna gore. Dakle, 17 je sada unutar reda. Trebam li ažurirati koja Polja sada ipak? OK, definitivno veličina. A što je ispred? OK, nema. Prednji ne bi trebalo mijenjati, jer za razliku od hrpe, mi Želite održavati pravičnosti. Dakle, ako je 9 osvojilo prvo, želimo 9 biti prvi iz reda te u trgovini. 

U stvari, da vidimo kako. Prije nego što stavite 22, hajdemo ići naprijed i dequeue 9. Koje je vaše ime? 

PUBLIKA: Jake. 

DAVID Malan: Jake ide da se dequeued sada. Tako ćete dobiti hodati u dućan. I praviti se da trgovine je tamo. I što sad treba - dit-dit-dit! Što se treba dogoditi sada? Dizajn odluka. Pa nije loša instinkt, ali - ono zoveš? 

PUBLIKA: David. 

DAVID Malan: David. Dakle, što je David učiniti? Pokušavao je svojevrsni popraviti podatke Struktura i premjestiti iz svoje mjesto u Jakeovo bivše mjesto. I to je u redu, ako smo spremni prihvatiti da je kao Provedba detalja. Ali prvo, neka je ažurirati podatke strukturu prije nego što to učinimo. Jer ja ne sviđa ideja o svima narod kreće u toj liniji. 

To nije velika stvar, ako je David to čini s jedan korak, ali opet, sjetim kada smo imali osam volontera na pozornici, a mi smo radili, ubacivanje sortiranje, gdje smo morali početi kreće svima okolo. To ih je skupo, zar ne? To čini mi dodvoravanje o velikim O n, veliki O n kvadrat ponovno. To se ne osjeća kao idealno ishod. 

Pa neka je samo ažurirati taj. Dakle, veličina red više nije 2. Sada je jednostavno 1. Ali ja sad mogu ažurirati nešto Nisam ažuriraju prije, Prednji dio popisa. Ja samo mogu reći, da je mjesto 1? Tako sada imamo smeće vrijednost ovdje, Vrijednost ovog smeća, a David u Sredinom ovog smeća. No, struktura podataka je još uvijek netaknut. 

A u stvari, ja uopće ne trebaju Jake promijeniti bivši broj 9, jer koga briga. Imam dovoljno informacija sada u Veličina Znam da postoji jedna osoba koja je u ovaj red. I znam da je ta osoba nalazi se na mjestu 1, a ne 0. Ja se ne brojim. Dakle 1, kao dobro. Dakle, struktura podataka je još uvijek u redu. 

Pa, što se događa sljedeće? Idemo Postavi u red - kako se ti zoveš? 

PUBLIKA: Callen. 

DAVID Malan: Callen. Idemo enqueue je Callen, i 22 je sada u redu. Dakle, ono što se sada mora promijeniti ovdje? Prednji se neće promijeniti, očito. Veličina će se promijeniti da bude 2 ponovno. I 22 završi ovdje, 9 je još uvijek prisutna, ali to je učinkovitije smeća vrijednost sada. To je samo ostatak prošlosti Jake. 

Dakle, sada što će se dogoditi ako se Ja dequeue Davida? Jedan posljednja operacija, dequeue David. Mogli bismo pomak, ali predlažem neka se učinite što manje posla što je više moguće. Sada mi je struktura podataka prolazi natrag u veličini 2-1. No, prednji red Sada postaje 2. Ne trebate promijeniti te brojeve samo još, jer su samo smeće vrijednosti. 

Ali sada što se događa? Pretpostavimo da sam enqueue, 26? Osjećam se kao da pripadam ovdje. Tako sam se enqueued. Tako nekako sam pripadam ovdje. A čak i ako to nije dosta Cijenim to vizualno na pozornici, jer imamo dosta prostora, trebao bih Ne mogu stajati ovdje, zašto? 

PUBLIKA: Ti si izvan granica. 

DAVID Malan: Točno. Ja sam izvan granica igrališta. Ja sam indeksirane izvan Granica u ovom polju. Stvarno bi trebali biti u jednom od tri moguće lokacije. Sada, gdje je najprirodnije ići? Predlažem da utjecati Tjedan je jedan trik. Mod operatera, postotak. Jer ja stojim na tehnički Mjesto na 3, ali ja to 3 mod sposobnosti, pa 3, znak za postotak, 3 - kapacitet je 3. Što je to? Što je ostatak pri podijelite 3 za 3? 0. 

Tako da me stavlja su Jake je, što je zapravo dobro. Tako sada implementacije za to što se događa s biti malo glavobolje. To je zapravo samo jedna linija glavobolje, koda. Ali barem sada postoji smeća Vrijednost ovog mjesta, ali ima dvije legitimne Ints ovdje. A ja tvrdim da je sada smo učinili upravo ono što trebamo učiniti tako dugo dok možemo promijeniti ono Jake vrijednosti biti 26. 

Mi sada imamo dovoljno informacija dalje održavanje integriteta ove strukture podataka. Mi smo još uvijek vrsta od sreće kad smo želite umetnuti četiri ili više ukupno elementi, ali mogu barem napraviti lijepa učinkovito korištenje ove konstantna Vrijeme, u stvari. Ne morate brinuti o tome prebacuje svatko, kao Davidova sklonosti bio. 

Bilo kakva pitanja na hrpe, ili ovaj red? 

PUBLIKA: Je li razlog morate veličinu tako da znate gdje je imati osobu? 

DAVID Malan: Točno. Moram znati veličinu polja jer moram znati točno kako mnogi od tih vrijednosti su legitimna, i tako da mogu naći gdje staviti Sljedeća osoba. Točno. Veličina je - Zapravo, nismo ažurirali ovaj još. Ja sam dodao na 26. Veličina je sada, a ne 1, nego 2. Dakle, sada je to doista pomaže mi da nađem Glava lista, koji nije 0, a ne 1, ali je 2. Prednji dio popisa je doista broj 22. Jer on je došao u prvi, tako da je on trebao biti dopušteno u trgovini prije mene, iako vizualno stojim bliže u trgovini. 

U redu? Pljesak za ove dečke a mi ćemo ih pustiti van. 

[PLJESAK] 

DAVID Malan: Mogao bih neka držite ladicu. Mogli smo vidjeti što će se dogoditi ako se želite, ali možda i nije. U redu. I što sad to nam preostaje? Pa, neka mi predlažemo da postoji Nekoliko druge strukture podataka mogli bismo početi dodajući da naš paket alata koji će zapravo biti vrlo, vrlo relevantni kao smo zaroniti u web stvari. Koji opet, ima neku vrstu priključka na stabla u obliku nešto što se zove DOM, dokument objektni model. No, vidjet ćemo više da ne zadugo. 

Dopustite mi predlažemo da smo preko definicija nazovite stablo sada ono što možda znate, kao Više od obiteljskog stabla, gdje se imaju neki predak u korijenje stabla. Patrijarhalnih ili matrijarh u samom vrhu stabla. Bez svog bračnog druga, u ovom slučaju. No, mi sada imamo ono što ćemo nazvati Djeca, koja su čvorovi koji vise off na lijevoj ili desnoj dijete dijete, strelice kao što je prikazano ovdje. 

Drugim riječima, u strukturi stabla podataka u računalo, stablo ima nulu ili više čvorova. Ako je barem jedan čvor to se zove korijen. To su stvari koje vizualno skrećemo na vrhu. I to čvora, kao i svaki drugi čvor, može imaju nula, jedan ili dva, ili tri, ili ipak mnogo djece struktura podataka podržava. U ovom slučaju, korijen, spremanje Vrijednost jednog, ima dvoje djece, 2 i 3, tako da mi općenito zovemo dvije lijeve Dijete i 3. pravo dijete. 

I onda kad dođemo do 5., 6., i 7, 6 bi se moglo nazvati srednje dijete. Ako imate četvero djece, to dobiva zbunjujuće. Tako ćemo prestati koristiti tu vrstu od prečac usmeno. Ali to je zapravo samo obiteljsko stablo. I lišće ovdje su čvorovi koji i sami nemaju djece. Oni družiti s dna stabla. 

Dakle, kako bismo mogli provesti taj stablo ima samo dvoje djece maksimalno? Zvat ćemo je binarno stablo. Bi opet znači dvije, u ovom slučaj, kao što je s binarnim. I tako to može imati nula, jedan, ili dvoje djece najvi. 

Ja ću predložiti da se implementirati čvor za tu strukturu s int n, a zatim dva pokazivače, jedan se zove lijevo, jedan se zove pravo. No, to su samo lijepo proizvoljne konvencije. A što je lijepo sada, pogotovo ako vrsta borili s konceptualno rekurzija, ili misli da nije Stvarno rješenje za bilo što, pogotovo ako bi ponestane memorije. Sada kada govorimo o podacima strukture i algoritmi koji omogućuju nas poprijeko i njima manipulirati, Ispada da je rekurzija vrati u mnogo uvjerljiviji ako ne i lijep način. 

Dakle, to predlažem je provedba od Search funkciju. S obzirom dva ulaza - tako da mislim ovo kao crnu kutiju. Dati dva ulaza, n, int i pointer na stablu, pokazivač čvora, ili stvarno korijen stabla, sam tvrdnja da je ova funkcija može vratiti Istina ili laž, da je vrijednost n je unutar ovog stabla. 

Ono što je unutar ove crne kutije? Pa, četiri grane. Prvi upravo provjerava. Ako stablo je null, samo povratak false. Ako nema čvora, nema n, ne postoji broj, samo povratak false. Ako ipak, n, vrijednost koju tražite za, je manje od stabla strelice n i samo da bude jasno, što to znači kada se Pišem stablo, a zatim strelicu zapis, n? Točno. To znači da je dereference Pokazivač se zove stablo. Idi tamo, a zatim ući u to čvora i dobiti svoje područje pod nazivom n. A onda usporedite stvarni n koji je bio prešao u pretraživanju protiv njega. 

Dakle, ako je n manji od, n vrijednosti u čvor stabla sama, dobro, Što to znači? To znači ništa na prvi pogled. Točno? Baš kao kad imate niz Vrijednosti, možda bih se prijaviti binarni pretraživanje kao oblik podjele i osvajanje. No, ono što je pretpostavka moramo napraviti za binary search uopće raditi u telefonskom imeniku i raniji primjeri? 

Kako biti riješeno. Tako ćemo precizirati definiciju stabla Ovdje ne da se samo stablo, što može imati bilo koji broj djece. Ne samo binarno stablo, što može imaju 0, 1, ili 2 maksimalno. Ali kao binarni pretraživanje stabla, ili BST, koji je samo fancy način govoreći: binarna stabla tako da svaki čvor lijevo dijete, ako je prisutan, je manje od čvora. I Svaki čvor je pravo dijete, ako je prisutan, je veći od čvora sama. 

Dakle, drugim riječima, ako ste bili na izvlačenje Stablo se, svi brojevi su Pažljivo uravnotežena ovako, tako da ako imate 55 kao korijen, 33 može ići na svojoj lijevoj strani, jer to je manje od 55 godina. 77 može ići u svom pravu jer to je veća od 55 godina. Ali sada primjetiti, istu definiciju, to je rekurzivna definicija verbalno, mora podnijeti zahtjev za 33. 33 je lijevo dijete mora biti manji od njega, , a 33 je pravo dijete, 44, moraju biti veći od njega. 

Dakle, ovo je binarna stabla, i Predlažem, koristite malo rekurzija, sada možemo naći n. Dakle, ako je n manji od vrijednosti n koji je trenutni čvor, ja ću otići naprijed i čamac, da tako kažemo, i samo vratite god odgovor je potrazi za n na Stablo lijevo dijete. Obavijest opet, ova funkcija jednostavno očekuje čvor zvijezda, pokazivač na čvor. Pa evo, ja samo mogu napraviti stablo Strelica ulijevo, što će dovesti ja na drugi čvor. No, ono što je taj čvor? 

Pa, prema ovoj izjavi, lijeva je samo pokazivač, tako da je samo znači da sam prolazi na funkciju pretraživanja drugačija pointer, naime onaj koji predstavlja Moje lijevo djeteta stabla. Dakle, u ovom slučaju, kazaljka na 33, ako je ovo je naš uzorak ulazna U međuvremenu, ako je n je veći od vrijednosti n u trenutni čvor u stablu, onda sam ići naprijed i čamac u drugi Smjer i samo reći, ja ne znam je li ova vrijednost je n u stablu, ali znam ako je to, to je dolje my desnim krakom, da se tako izrazim. Pa neka mi rekurzivno poziva traženje, položenog n opet, ali prolaze pokazivač na desnoj djeteta. 

Drugim riječima, ako sam trenutno na 55 i ja sam u potrazi za 99, znam da 99 je veći od 55, tako da baš kao što sam poderao telefonskog imenika tjedana, a mi otišao desno, slično smo mi ići ovdje. I ne znam je li to kod mene prava djeteta, a to nije, 77 je tu, ali Znam da je u tom smjeru. Dakle, pozivam pretraživanje na mom desnom djeteta, 77, i neka pretragu lik iz postoji li 99 u to proizvoljno Primjer je zapravo tamo. 

Inače, ono što je konačno slučaj? Ako je stablo null je jedan slučaj. Ako je n manji od struje čvora Vrijednost je još jedan slučaj. Ako je n veći od struje čvora vrijednost je treći slučaj. Što je četvrti i posljednji slučaj? Mislim da smo od slučajeva, zar ne? Bit će da n je trenutni čvor da sam na. 

Dakle, ako sam u potrazi za 55 u ovom trenutku u priči, da je grana Stablo će se vratiti točno. Dakle, ono što je zanimljivo je da smo Zapravo, za razliku od tjedna prošlosti, onda smo mjesta imaju dva osnovna scenarija. A oni ne moraju biti sve na vrhu. Najbolje je osnovni scenarij, jer ako Stablo je nula, nema ništa učiniti. Samo se vratili tvrdi kodirani vrijednost false. 

Dno grana vrsta default, pri čemu se ako smo provjeriti za null, mi smo provjeriti da li bi trebao biti lijevo, ali to ne bi trebalo biti, mi smo provjeriti da li bi trebao biti u pravu, ali to Ne bi trebalo biti, jasno da mora biti tu gdje smo. To je osnovni scenarij. Dakle, postoje dvije rekurzivni slučajevi sendviču ovdje u sredini. Ali sam mogao pisati to u bilo kojem redoslijedu. Samo sam mislio to vrsta, prirodno prvo provjeriti za moguće pogreške, zatim provjerite lijevo, a zatim provjerite desno, a zatim Pretpostavljamo da ste na čvoru što zapravo tražite. 

Pa zašto bi to bilo korisno? Tako ispada - i neka mi skočiti na zadirkivač Ovdje je to na webu. Mi ćemo početi koristiti ne programskog jezika, na prvi pogled, ali Markup Language. Jezik za bitak onaj koji je slični u duhu programiranje jezik, ali to vam ne daje Sposobnost da se izraze logično. To samo da daje vam mogućnost da izraziti sebe strukturalno. 

Gdje želiš staviti nešto na stranici, web stranica? Koje je boje želite to učiniti? Što veličinu fonta želite to učiniti? Koje riječi ti to zapravo Želite na web stranici? Dakle, to je jezik za označavanje. No, onda ćemo vrlo brzo uvesti JavaScripta, što je punopravni programskom jeziku. Vrlo slično sintaktički u izgledu do C, ali to će imati neke Lijepo, snažnije, više user friendly značajke. 

A jedan od frustracije na ovaj točka u semestru je da ćemo Uskoro provedbu Speller u daleko manje linija koda koriste druge jezike od C sama dopušta, ali razlog je uskoro ćemo shvatiti. To će biti prva takva web stranica. To će biti potpuno underwhelming, Prvi smo napraviti. Ona će jednostavno reći, Hello World. Ali, ako ste nikada nije vidio prije, ovo je HTML, HyperText Markup Language. 

Ako idete na određenu opciju izbornika u najviše bilo kojeg preglednika, na bilo koju web stranicu na internet, možete vidjeti HTML da su neki ljudi pisali stvorili tu web stranicu. I to vjerojatno ne izgleda kao kratki ili kao uredan kao i ovaj. No, to će slijediti obrazac njih otvorene zagrade i kose crte i slova i potencijalno brojevi. 

Mislio sam da bih vam teaser o tome što ćete biti u mogućnosti to učiniti nakon uzimanja CS50. Pusti me da cs.harvard.edu / opljačkati, Naš vlastiti Rob Bowden je internetska stranica. Bio je to za nas. Tako ćete uskoro biti u mogućnosti to učiniti. I također, ono što ste čuli Jutros - ono što ste čuli jutros - 

[Hrčak DANCE MUSIC] 

- You'll biti u mogućnosti kako bi se to. To nas čeka u srijedu. Vidjet ćemo se tada. 

[Hrčak DANCE MUSIC] DAVID Malan: Na sljedećem CS50 -