>> 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.
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 -