>> ZVUČNI 1: U redu, tako da smo se vratiti.
Dobrodošli na CS50.
Ovo je kraj tjedna sedam.
Dakle podsjetiti da je posljednji put, počeli smo gleda na nešto sofisticiraniji
strukture podataka.
Budući da do sada, sve što smo imali jako na raspolaganju je to, niz.
>> No, prije nego što bacite niz kako ne sve što je zanimljivo, što doista
zapravo, ono što su neke od pluses ove jednostavne podataka
struktura do sada?
Što je to dobro?
Do sada kao što smo vidjeli?
Što ti imaš?
Ništa.
>> STUDENT: [nečujno].
>> ZVUČNI 1: Što je to?
>> STUDENT: [nečujno].
>> ZVUČNI 1: Fiksna veličina.
OK, pa zašto je fiksna veličina dobro ipak?
>> STUDENT: [nečujno].
>> ZVUČNI 1: U redu, tako da je učinkovita u Osjećaj da mogu izdvojiti
Fiksni iznos prostora, koji će, nadamo Upravo onoliko koliko
Prostor kao što želite.
Tako da bi mogao biti apsolutno plus.
>> Što je još gore strana niz?
Da?
>> STUDENT: [nečujno].
>> ZVUČNI 1: All - žao?
>> STUDENT: [nečujno].
>> ZVUČNI 1: Svi su kutije u memoriji ili jedna pored druge.
I to je korisno - zašto?
To je sasvim točno.
Ali kako možemo iskoristiti tu istinu?
>> STUDENT: [nečujno].
>> ZVUČNI 1: Točno, možemo pratiti gdje je sve samo znajući
Prva adresa, odnosno adresa Prvi bajt taj komad memorije.
Ili u slučaju niza, adresa prva
char u tom nizu.
A od tamo, možemo naći kraj niza.
Možemo pronaći drugi element, Treći element, i tako dalje.
>> I tako fancy način opisuje kako značajka je da nizovi nam
s izravnim pristupom.
Samo pomoću uglata zagrada oznake i broj, možete prijeći na
određeni element u polju u konstantnom vremenu, big O
jedne, da tako kažem.
>> No, tu nije bilo neke mane.
Što polje ne učiniti vrlo jednostavno?
Što je to nije dobro?
>> STUDENT: [nečujno].
>> ZVUČNI 1: Što je to?
>> STUDENT: [nečujno].
>> ZVUČNI 1: Širenje u veličini.
Tako su Nedostaci polja su Upravo suprotno od onoga
upsides se.
Pa je jedan od nedostataka je da je fiksna veličina.
Tako da stvarno ne mogu ga rastu.
Možete preraspodijeliti veći komad memorije, a zatim premjestiti staru elemente
u novi niz.
A onda bez stara polje, za Primjerice, pomoću malloc ili sličnu
Funkcija zove realloc, koji reallocates pamćenje.
>> Realloc, kao stranu, pokušava dobiti memorije koja je pored niza
koje već imate.
No, to bi moglo premjestiti stvari oko uopce.
No, ukratko, to je skupo, zar ne?
Jer, ako imate komad memorije ove veličine, ali stvarno želite jedan
ove veličine, a vi želite sačuvati izvorni elementi, imate
otprilike linearno vrijeme kopiranja koji se treba dogoditi s
stara polje za novo.
A stvarnost je molba operativnog Sustav opet i opet i
opet za velike komade memorije može početi na trošak vam neko vrijeme kao dobro.
Tako da je i blagoslov i prokletstvo u prikrilo, činjenicu da ti nizovi
su fiksne veličine.
Ali ako ćemo predstaviti nešto umjesto kao što je ovaj, koji smo nazvali linked
Popis smo dobili nekoliko odlika i nekoliko loših strana i ovdje.
>> Tako povezani popis je jednostavno podataka Struktura se sastoji od C tvorevina, u ovom
slučaj, gdje je rekonstruirati, podsjetimo, samo je Spremnik jedne ili više specifičnih
vrste varijabli.
U ovom slučaju, ono što učinite vrste podataka Čini se da unutar struct da
Posljednji put smo se naziva čvor?
Svaka od tih pravokutnika je čvor.
I svaki od manjih pravokutnika unutar nje je tip podataka.
Koje vrste nije kažemo su u ponedjeljak?
Da?
>> STUDENT: [nečujno].
>> ZVUČNI 1: promjenjiva i pokazivač, ili točnije, int, za n,
i kazaljke na dnu.
Obje od onih dogoditi da se 32 bita, na Barem na računalu kao što je ovaj CS50
Appliance, i tako su izvučeni podjednako u veličini.
>> Dakle, ono što su pomoću pokazivača iako za očito?
Zašto dodali ovaj strelicu sada kad su nizovi tako lijepo i čisto i jednostavno?
Što je pokazivač radi za nas u svakom od tih čvorova?
>> STUDENT: [nečujno].
>> ZVUČNI 1: Točno.
To vam reći gdje je Sljedeći je.
Tako sam vrsta koristiti analogiju koristite konac za sortiranje mjesta
nit tih čvorova zajedno.
A to je upravo ono što mi radimo s pokazivače jer svaki od tih
komadi memorije ne mogu ili mogu biti susjednih, vratio se natrag na leđa
unutar RAM-a, jer svaki put kad poziva malloc govoreći, daj mi dovoljno
bajtova za novi čvor, to bi moglo biti ovdje i to bi moglo biti ovdje.
To bi moglo biti ovdje.
Vi jednostavno ne razumijete.
>> No, korištenje pokazivača na adrese ti čvorovi, možete ih bod
zajedno na način koji izgleda vizualno kao popis, čak i ako su te stvari
Svi raširi cijelom jednom ili Vaši dvije ili četiri svoje gigabajta RAM-a
unutar svoje računalo.
>> Dakle downside, a zatim, povezani popis je ono?
Što je cijena koju smo očito plaćati?
>> STUDENT: [nečujno].
>> ZVUČNI 1: Više mjesta, zar ne?
Mi smo, u ovom slučaju, udvostručen je iznos prostora jer smo otišli
od 32 bita za svaki čvor, za svaku int, tako da sada 64 bita, jer moramo
držati oko pokazivača kao dobro.
Možete dobiti više učinkovitosti ako vaš struct je veća od ove jednostavne stvari.
Ako doista imate studenta unutar od kojih je nekoliko nizova za
Ime i kuća, možda i ID broj, možda i neke druge stavke uopce.
>> Dakle, ako imate dovoljno veliku struct, onda možda cijena od pokazivačem
nije tako velika stvar.
To je malo kornera u slučaju da je mi smo pohranu, kao jednostavna primitivna
unutar povezanoj popisa.
Ali stvar je ista.
Ti si definitivno troše više memorije, ali ste dobivanje
fleksibilnost.
Jer sad ako želim dodati element na početku ovog popisa
Moram izdvojiti novi čvor.
I moram samo ažurirati onima Strelice nekako samo pomicanjem
neke naputke oko.
>> Ako želim da ubacite nešto u sredinu ljestvice, ja ne moram
gurati sve na stranu kao što smo učinili u Posljednjih tjedana s našim volonterima koji su
predstavljao niz.
Ja samo mogu izdvojiti novi čvor i onda samo ukazati na strelice u
različitim smjerovima, jer ona ne moraju ostati u stvarni
memorije istina linije kao da sam nacrtana je ovdje na zaslonu.
>> I onda na kraju, ako želite umetnuti nešto na kraju popisa, to je
čak i lakše.
To je vrsta proizvoljnog zapisu, ali 34 je pointer, uzeti pogodak.
Što je vrijednost njegove pokazivač najviše vjerojatno izvući nešto kao stara
Škola ima antenu?
>> STUDENT: [nečujno].
>> ZVUČNI 1: To je vjerojatno null.
I doista, to je jedna autora zastupljenost null.
A to je zato što apsolutno null morate znati gdje je kraj linked
Popis je, da ne bi i sljedeće slijedi i nakon ove strelice
na neko smeće vrijednosti.
Dakle null će značiti da ne postoji više čvorova desno od broja 34,
u ovom slučaju.
>> Dakle, mi predlažemo da možemo provesti ovaj čvor u kodu.
I mi smo vidjeli ovakvu sintakse prije.
Typedef jednostavno definira novi tip za nas, daje nam sinonim kao što je
string je za char *.
U ovom slučaju, to će nam dati stenogram notacija kako struct node
može umjesto toga samo se zapisati kao čvor, što je mnogo čistiji.
To je puno manje rječit.
>> Unutar od čvora je očito int pod nazivom n, a zatim struct čvor *
što znači da je točno ono što smo htjeli strelice značiti, pokazivač na drugo
čvor isti tip podataka.
I sam predložio da smo mogli provesti Nova funkcija kao što je ovaj, koji je u
prvi pogled može činiti malo složeniji.
No, da vidimo što se u kontekstu.
>> Pusti me preko aparata ovdje.
Dopustite mi otvoriti datoteku pod nazivom Popis nula dot h.
I to samo da sadrži definiciju mi Vidjela sam maloprije za ove podatke
Vrsta naziva čvor.
Tako smo stavili da je u datoteku dot h.
>> I kao na stranu, iako to program koji ste upravo vidjeti je
nije sve što je složeno, to je istina Konvencija prilikom pisanja programa
staviti stvari kao što su vrste podataka, da će se povući Konstante ponekad, unutar vašeg
header file, a ne nužno u Vaš C datoteku, osobito kad vaše
Programi dobiti veći i veći, tako da je znate gdje se mogu pogledati i za
Dokumentacija u nekim slučajevima, ili za osnove kao što su to,
definicija nekog tipa.
>> Ako ja sada otvoriti popis nultu točku c, primijetiti nekoliko stvari.
On uključuje nekoliko zaglavlje datoteke, najviše koje smo vidjeli prije.
To uključuje vlastiti zaglavlje datoteke.
>> I kao stranu, zašto je to bračni citati ovdje, za razliku od kuta
nosači na liniju koja Ja sam istaknuo postoji?
>> STUDENT: [nečujno].
>> ZVUČNI 1: Da, tako je lokalna datoteka.
Dakle, ako je lokalni file od vlastite ovdje na liniji 15, primjerice, koristite
dvostruke navodnike umjesto od kutnih zagrada.
>> Sada je to vrsta zanimljiva.
Obavijest da sam proglasio globalnom varijabla u ovom programu na liniji 18
Prvi se zove, ideja da je ovo će biti pointer na prvi
čvor u mom povezanom popisu, a ja sam inicijaliziraju se na nulu, jer sam
Nije bilo dodijeljeno stvarna čvorovi samo još.
>> Dakle, to predstavlja, slikovito, ono što smo Vidio maloprije na slici kao
da je kazaljka na daleko lijevoj strani.
Pa sad, da pokazivač nema strijelu.
Ona umjesto da je samo null.
No, on predstavlja ono što će biti adresa prva stvarna
čvor u ovom popisu.
Tako sam implementiran je globalni jer, kao što ćete vidjeti, sve ovo
Program se provodi u životu povezani popis za mene.
>> Sada sam dobio nekoliko prototipova ovdje.
Odlučio sam provesti značajke kao što su brisanje, umetanje, pretraživanje i
obuhvaćanje -
Posljednji samo kao šetnja Popis, ispis njene elemente.
A sad evo moj glavni rutinu.
I nećemo trošiti previše vremena na to jer je to vrsta, nadamo
stari šešir do sada.
>> Ja ću učiniti sljedeće, dok je korisnik surađuje.
Dakle, jednom, idem za ispis iz ovog izbornika.
I ja sam ga oblikovati kao čisto kao što sam mogao.
Ako korisnik upiše u jednoj, to znači da oni žele izbrisati nešto.
Ako korisnik upiše u dva, to znači da oni žele staviti nešto.
I tako dalje.
Idem onda zatražiti onda za naredbe.
A onda ću koristiti GetInt.
>> Dakle, ovo je stvarno jednostavan menuing sučelje gdje jednostavno morate tipkati
broj preslikavanje jednog od tih naredbi.
I sada imam lijep čist prekidač izjava da će se uključiti
sve što korisnik unese
A ako su upisali jedan, ja ću nazovite izbrisati i break.
Ako su upisali dva, ja ću nazovite umetanje i break.
>> I sad sam stavio obavijest jedni od ovih na istoj liniji.
Ovo je samo stilska odluka.
Obično smo vidjeli nešto kao što je ovaj.
Ali sam odlučio da, iskreno rečeno, moj program Pogledao više čitati, jer
to je bio samo četiri slučaja do samo ga navesti kao što je ovaj.
Totalno legitimno korištenje stilu.
I ja ću to učiniti, tako dugo dok korisnik nije upisali nulu, što sam
odlučila će značiti žele prestati.
>> Tako sada primijetiti što sam će to učiniti ovdje.
Idem na slobodan popis očito.
No, više o tome u samo trenutak.
Neka prvi pokrenuti ovaj program.
Pa neka mi napraviti veći terminal prozor, dot slash Lista 0.
Ja ću ići naprijed i umetnite strane tipkanje dva, broj kao što je 50, a sada
vidjet ćete popis je sada 50.
I moj tekst jednostavno prebacite se malo.
Tako sada primjetiti popis sadrži broj 50.
>> Idemo napraviti još jedan umetak uzimanjem dva.
Idemo upisati u broju kao jedan.
Popis je sada jedan, nakon čega slijedi 50.
Dakle, ovo je samo tekstualni prikaz popisa.
I neka je umetnite još jedan broj kao broj 42, koji je izgledno
će završiti u sredini, jer je Ovaj program posebno je vrsta
elemente kao što im umetci.
Tako da smo ga.
Super jednostavan program koji bi mogao Apsolutno smo koristili niz, ali ja
dogoditi da se pomoću povezanu popis samo tako mogu dinamički
rasti i smanjivati.
>> Tako ćemo pogledati za pretraživanje, ako sam pokrenuti naredbu tri, želim pretraživanje
za, recimo, u broju 43.
I ništa navodno je pronađena, jer sam dobio natrag nikakav odgovor.
Tako ćemo to opet.
Traži.
Neka je potraga za 50, odnosno traženje u 42, koji ima nice
malo suptilnije značenje.
I sam pronašao smisao života tamo.
Broj 42, ako ne znate reference, to Googleu.
U redu.
Dakle, ono što je ovaj program učinio za mene?
To je samo dopustio da ubacite taj način daleko i potraga za elementima.
>> Idemo brzo naprijed, a zatim, kako bi koji funkcioniraju smo pogledala
u ponedjeljak je kao teaser.
Dakle, ove funkcije, ja tvrdim, traži element u popisu tako da se prvo
jedan, pitajući korisnika, a zatim pozivom GetInt doći do stvarnih int
koju želite potražiti.
>> Zatim primijetiti.
Ja ću stvoriti privremenu varijablu u skladu 188. zove pokazivač -
PTR -
mogli su ga zvali ništa.
I to je pointer na čvoru zato sam rekao čvora * postoji.
I ja sam inicijalizacije da bude jednak prvi, tako da sam učinkovito imaju my
prstom, da tako kažemo, na samom Prvi element popisa.
Dakle, ako mi je desna ruka ovdje je PTR sam pokazujući na isto koji je prvi
je pokazivao.
>> Tako sada natrag u kodu, što će se dogoditi -
to je čest paradigma kada iterating preko strukture kao
povezani popis.
Ja ću učiniti sljedeće dok Pokazivač nije jednak null Dakle, dok
moj prst nije pokazivao neku null vrijednost, ako pointer strelica n jednak n.
Mi ćemo primjetiti da je prvi n je ono korisnik upisao u po GetInts ovdje zovu.
>> I pointer strelica n znači što?
Pa ako se vratimo na slici ovdje, ako imam prst pokazujući na
koji je prvi čvor koji sadrži devet, na Strelica u osnovi znači da je ići na
čvora i iskoristite vrijednost na mjesto n, u ovom slučaju, polje podataka naziva n.
>> Kao na stranu - a vidjeli smo ovaj par tjedana kada je netko pitao -
Ova sintaksa je novo, ali to ne daj nam snage da mi
nije već imate.
Ono što je ovaj izraz jednak pomoću dot oznake i star par
tjedana kada smo oguljen ovaj sloj malo prerano?
>> STUDENT: [nečujno].
>> ZVUČNI 1: Točno, to je bio star, a onda bio star dot n, s
zagrade ovdje, što izgleda, iskreno, mislim da je puno
više zagonetan čitati.
No zvijezda pointer, kao i uvijek, znači otići tamo.
A kad ste tamo, koje podatke Polje želite pristupiti?
Pa što koristite dot oznake za pristup Polje tvorevina podataka, i ja
posebno želim n.
>> Iskreno, ja bih rekao ovo samo je teže čitati.
To je teže sjetiti gdje da su zagrade ide,
zvijezda i sve to.
Dakle, svijet donijela neke sintaktičke šećera, da se tako izrazim.
Samo seksi način da se kaže, to je ekvivalent, a
možda i intuitivnije.
Ako je doista pointer pokazivač, strelica zapis znači otići tamo i naći
polje u ovom slučaju zove n.
>> Dakle, ako sam ga pronaći, primijetiti što mi je činiti.
Ja jednostavno isprintati, otkrio sam posto, uključivanjem u vrijednosti za taj int.
Pozivam spavati jednu sekundu samo da vrste pauze stvari na zaslonu za
daju upute Drugi apsorbirati ono što se upravo dogodilo.
A onda sam se probiti.
Inače, što da radim?
Ja ažurirali pokazivač na jednake Pokazivač strelicu pored.
>> Dakle, samo da bude jasno, to znači ići postoji, koristeći moje stare škole zapis.
Dakle, to samo znači da ide na sve što ste pokazujući na, koji je u vrlo
Prvi slučaj je sam pokazujući na struct s devet u njemu.
Tako sam otišao tamo.
A onda dot oznake znači, dobili vrijednost na sljedeći.
>> Ali vrijednost, iako je nacrtana kao uska, je samo broj.
To je brojčana adresa.
Dakle, ovo jedna linija koda, bilo napisano ovako više zagonetan
način, ili kao što je ovaj, nešto više intuitivan način, samo znači mičem ruku
od prvog čvora do sljedećeg, , a zatim sljedeći, a zatim
Sljedeći jedan, i tako dalje.
>> Tako nećemo razmišljati o drugima implementacije umetanje i brisanje
i obuhvaćanje, prva dva od koji su prilično uključeni.
I mislim da je to prilično lako dobiti izgubljen kada to rade verbalno.
No, ono što možemo učiniti je da se ovdje pokušati utvrditi kako
najbolje je to učiniti vizualno.
Jer ja bih predložio da, ako smo želite umetnuti elemente u ovo
postojeći popis, koji ima pet elemenata -
9, 17, 22, 26, i 33 -
ako su išli za provedbu ove u broj, moram razmisliti o tome kako ići
o to.
>> I ja bih predložio poduzimanje koraka beba pri čemu, u ovom slučaju mislim, ono se
mogućih scenarija koji smo naići u cjelini?
Pri provedbi umetak za linked Popis, to jednostavno dogodi da se
specifičan primjer veličine pet.
Pa ako želite umetnuti broj, vole reći broj jedan, a
održavanje sortiraju bi, u kojoj Očito ne broj jedan morate
ići u konkretnom primjeru?
Na primjer na početku.
>> No, ono što je zanimljivo je da je Ako želite umetnuti jedan u ovo
Popis, ono treba posebna pointer biti ažurirana očito?
Prvo.
Dakle, ja bih rekao, ovo je prvi slučaj da smo možda želite uzeti u obzir,
Scenarij uključuje ugurate početak popisa.
>> Idemo ugrabiti off možda tako lako, pa čak i jednostavniji slučaj, relativno govoreći.
Pretpostavimo da želite umetnuti Broj 35 u sortiraju bi.
Očito spada tamo.
Dakle, ono što je očito pokazivač će moraju biti ažurirana u tom scenariju?
34 je pokazivač postane nije null ali adresa struct
sadrži broj 35.
Dakle, to je slučaj dvoje.
Tako je već, ja sam nekako kvantiziranje koliko posla moram učiniti ovdje.
>> I na kraju, očito srednje slučaj Doista, u sredini, ako želim
ubacite nešto poput recimo 23, koji ide između 23 i 26 godina, a
Sada se stvari malo više uključena, jer ono
pokazivače treba mijenjati?
Dakle, 22 očito treba mijenjati jer on se ne može ukazati na 26. više.
On treba ukazati na novi čvor koji Morat ću izdvojiti pozivom
malloc ili neki ekvivalent.
>> Ali onda sam također potrebno da se novi čvor, 23 u ovom slučaju, imati svoj pokazivač
pokazujući na koga?
26.
I tu će biti Redoslijed operacija ovdje.
Jer ako ja to glupo, i ja , na primjer, na početku od
popis, a moj cilj je da ubacite 23.
I sam provjeriti, to pripadaju Ovdje, kod devet?
Ne.
Da li to pripada ovdje, uz 17?
Ne.
Znači li to spada ovdje pokraj 22.?
Da.
>> Sada, ako sam glupo ovdje, a ne promisli, mogao bih
izdvojiti moj novi čvor za 23.
Ja bi ažurirali pokazivač iz čvora zove 22, ukazujući
je na novi čvor.
I što onda moram ažurirati novi čvor je pointer biti?
>> STUDENT: [nečujno].
>> ZVUČNI 1: Točno.
Ukazujući na 26.
Ali, k vragu, ako nisam već ažurirali 22 je pokazivač ukazati na ovom čovjeku, i
sada imam siročadi, ostatak popisa, da se tako izrazim.
Dakle, redoslijed operacija ovdje će biti važno.
>> Za to sam mogao ukrasti, recimo, šest volontera.
I neka je vidjeti ako mi to ne može učiniti vizualno, umjesto kod-mudar.
I mi imamo neke lijepe stres loptice za vas danas.
OK, o tome kako jedan, dva, u natrag - na kraju tamo.
tri, četiri, obje dečki na kraju.
I pet, šest.
Svakako.
Pet i šest.
U redu, a mi ćemo doći da ti dečki sljedeći put.
U redu, daj se.
>> U redu, budući da ste ovdje prvi put, bi li htjeli biti onaj nezgodno
u Google Glass ovdje?
U redu, tako da, OK, staklo, snimanje videa.
OK, ti si dobar to ići.
>> U redu, pa ako ti dečki mogu doći Evo, ja sam unaprijed pripremljen
neki brojevi.
U redu, dođi ovamo.
A zašto ne odeš malo dodatno na taj način.
I da vidimo, što je vaše ime, s Google Glass?
>> STUDENT: Ben.
>> ZVUČNI 1: Ben?
OK, Ben, što će biti prvi put, doslovno.
Tako ćemo vam poslati na kraju faze.
U redu, a vaše ime?
>> STUDENT: Jason.
>> ZVUČNI 1: Jason, OK vi ćete se broj devet.
Dakle, ako želite slijediti Ben taj način.
>> STUDENT: Jill.
>> ZVUČNI 1: Jill, ti si idući u biti 17, koji, ako bih to učinio više
inteligentno, ja bi upis na drugom kraju.
Možete ići na taj način.
22.
A vi ste?
>> STUDENT: Marija.
>> ZVUČNI 1: Marija, vi ćete biti u 22.
A tvoje ime je?
>> STUDENT: Chris.
>> ZVUČNI 1: Chris, vi ćete biti u 26.
I onda na kraju.
>> STUDENT: Diana.
>> ZVUČNI 1: Diana, vi ćete biti u 34.
Tako ste došli ovamo.
>> U redu, tako da usavršite razvrstani Već naručiti.
I idemo naprijed i to tako da možemo stvarno -
Ben ti si samo vrsta potrazi van u nigdje ne postoji.
U redu, tako da idemo naprijed i prikazati ovaj pomoću ruke, baš kao što sam bio, točno,
što se događa.
Dakle, ići naprijed i dati sebi stopu ili dvije od sebe.
I ići naprijed i ukazati s jedne strane na tko bi trebali biti okrenuti
na temelju toga.
A ako ste null uperi ravno na pod.
U redu, tako dobro.
>> Tako sada imamo povezana popis, i neka mi predlažu da ću igrati ulogu
PTR, pa neću gnjaviti Knjigovodstvena ovo oko.
A onda - netko je glupo konvencije - možete nazvati ovo sve što želite -
prethodnik pokazivač, pokazivač Pred -
to je samo nadimak mi je dao u naš primjer koda s moje lijeve strane.
S druge strane da će se vođenje evidenciju o tome tko je tko u
nakon scenarija.
>> Dakle pretpostavljam, prvo, želim trgati off da je prvi primjer umetanjem, kažu
20, u popisu.
Tako da ću morati nekoga na utjeloviti broj 20 za nas.
Dakle, trebam nekoga malloc iz publike.
Dođi gore.
Koje je tvoje ime?
>> STUDENT: Brian.
>> ZVUČNI 1: Brian, u redu, tako da će biti čvor koji sadrži 20.
U redu, dođi ovamo.
I očito, u kojoj Brian ne pripadaju?
Dakle, u sredini - zapravo, čekaj malo.
Činimo to iz reda.
Učinili smo to puno teže nego to treba biti na prvom mjestu.
U redu, idemo u slobodnom Brian realloc i Brian su pet.
>> U redu, tako da sada želimo umetnuti Brian i pet.
Pa hajde ovamo pokraj Ben samo na trenutak.
A ti vjerojatno može reći gdje je ova priča se događa.
Ali neka je dobro razmisliti o tome Redoslijed operacija.
I to je upravo ovaj vizualni koji će se postroje
s tom primjeru koda.
Dakle, ovdje sam PTR ukazujući na početku Ne, na Bena, per se, ali bez obzira na
Cijenimo ga sadrži, što u ovom slučaju je - ono zoveš?
>> STUDENT: Jason.
>> ZVUČNI 1: Jason, tako i Ben i ja smo pokazujući na Jasona u ovom trenutku.
Pa sad moram odrediti, gdje se Brian pripadaju?
Dakle, jedino što imam pristup sada je njegov n podaci stavku.
Dakle, idem provjeriti, je Brian manje od Jasona?
Odgovor je istina.
>> Dakle, ono što se sada treba dogoditi, u ispravnom redoslijedu?
Trebam li ažurirati koliko pokazivače Ukupno je u ovoj priči?
Gdje mi je ruka još uvijek je pokazivao Jason, a tvoja ruka - ako želite
stavi svoju ruku kao što je, na neki način, sam Ne znam, Upitnik.
OK, dobro.
>> U redu, tako da imate nekoliko kandidata.
Ili Ben ili ja ili Brian ili Jason ili svi drugi, koji
pokazivače trebate promijeniti?
Koliko je ukupno?
>> U redu, tako da dvojica.
Moj pokazivač zapravo ne smeta više jer ja sam samo privremeno.
Tako da je ove dvije dečki, vjerojatno, i Ben i Brian.
Pa neka mi predložiti da se ažurirati Ben, budući da je prvi put.
Prvi element ovog popisa sada će se Brian.
Dakle Ben točka na Briana.
OK, što sad?
>> Tko dobiva ukazao na koga?
>> STUDENT: [nečujno].
>> ZVUČNI 1: U redu, tako je Brian ukazati na Jasona.
Ali sam izgubio pojam o tom pokazivač?
Znam gdje je Jason?
>> STUDENT: [nečujno].
>> ZVUČNI 1: radim, jer sam privremena pointer.
A vjerojatno, ja se nisam promijenio ukazati na novi čvor.
Dakle, mi jednostavno možete imati Brian točku po tko sam pokazujući na.
I mi smo gotovi.
Tako je jedan slučaj, uneseni u početak popisa.
Dva su ključna koraka.
Jedan, moramo ažurirati Bena, a zatim imamo i ažurirati Briana.
I onda ja ne moram se gnjaviti traipsing kroz ostatak
Popis, jer mi je već našao svoje položaj, jer je on pripadao
lijevo od prvog elementa.
>> U redu, tako da prilično jednostavan.
Zapravo, osjeća se kao da smo gotovo što je ovo previše komplicirano.
Tako ćemo sada trgati off kraj popisa, i vidjeti gdje je
složenosti počinje.
Dakle, ako sada, ja alloc iz publike.
Svatko želi igrati 55?
U redu, vidjela sam svoju ruku prvo.
Dođi gore.
Da.
Koje je tvoje ime?
>> STUDENT: [nečujno].
>> ZVUČNI 1: Habata.
OK, daj se.
Vi ćete biti broj 55.
Tako da, naravno, pripadaju na kraju popisa.
Tako ćemo ponovno simulacija sa mnom što PTR samo na trenutak.
Tako sam prvi put idem ukazati na god Ben je pokazivao.
Mi oboje upućuju sada na Briana.
Tako da 55 je ne manje od pet.
Pa ću ja ažurirati ukazujući na Brianovi sljedeći pokazivač, koji je
Sada je, naravno, Jason.
55 je ne manje od devet, tako Ja ću ažurirati PTR.
Ja ću ažurirati PTR Ja ću ažurirati PTR.
A ja ću se - hm, što je zoveš?
>> STUDENT: Diana.
>> ZVUČNI 1: Diana pokazuje, naravno, na null s njezine lijeve strane.
Dakle, gdje se zapravo Habata pripadaju jasno?
S lijeve strane, ovdje.
Dakle, kako da znam da joj stavi ovdje Mislim da sam zeznuo.
Jer, što je PTR umjetnost ovaj trenutak u vremenu?
Null.
Dakle, iako je vizualno, možemo Očito vidjeti u svemu ovome
Dečki ovdje na pozornici.
Nisam pratila od prethodnih Osoba u popisu.
Ja nemam prst ističući, u ovom slučaju, broj 34 čvora.
>> Tako ćemo zapravo početi ovaj iznad.
Pa sad ja zapravo trebam Drugi lokalni promjenjiva.
I to je ono što ćete vidjeti u Stvarni broj uzorak C, gdje je kao idem,
kad sam ažurirati moj desnu ruku do točke Jason, čime je Brian iza sebe, sam
bolje početi koristiti lijevu ruku na ažurirati gdje sam bio, tako da kao idem
kroz ovaj popis -
više nespretno nego što sam namjeravao Sada ovdje vizualno -
Ja ću doći do kraj popisa.
>> Ova ruka je još uvijek null, što je prilično beskorisno, osim za označavanje
Ja sam jasno na kraju popisa ali sada barem imam ovu
prethodnik pointer pokazuje ovdje, pa Sada ono ruke i ono što je potrebno upućuje
biti ažuriran?
Čija ruka želite za preustroj prvi?
>> STUDENT: [nečujno].
>> ZVUČNI 1: U redu, tako Dijane.
Gdje želiš istaknuti Dianina lijeva kazaljka na?
U 55 godina, vjerojatno, tako da je smo umetnuta postoji.
A gdje bi trebao ići 55 pokazivač?
Dolje, što predstavlja null.
I moje ruke, u ovom trenutku, ne važno, jer oni su jednostavno
privremene varijable.
Dakle, sada smo gotovi.
>> Dakle dodatni složenosti postoji - i nije da je teško provesti,
ali moramo sekundarnu varijablu kako bi sigurni da je prije mičem pravo
S druge strane, sam ažurirati vrijednost mi je lijeva S druge strane, Pred pokazivač u ovom slučaju, tako da
da imam prateći pokazivač pratiti gdje sam bio.
Sada su na stranu, ako ste mislili na ovo putem, to se osjeća kao da je
malo neugodno da su zadržati pratite ove lijeve strane.
>> Što bi drugo rješenje na ovaj problem bio?
Ako imaš za redizajn podatke Struktura pričamo
do sada?
Ako je to samo vrsta osjeća malo neugodno da su, kao, dva pokazivače
ide kroz popis, tko bi drugi mogao su, u idealnom svijetu, održava
Informacije koje trebamo?
Da?
>> STUDENT: [nečujno].
>> ZVUČNI 1: Točno.
Točno tako da je zapravo zanimljiva klica ideje.
A ova ideja o prethodnoj pokazivač, pokazuje na prethodni element.
Što ako sam samo da je utjelovljena unutar samom popisu?
I to će biti teško vizualizirati to bez svih papira
pada na pod.
Ali pretpostavimo da su ti dečki koristiti i njihovih ruku imati prethodna
pokazivač, a pored pokazivač, čime se provedbi onoga što ćemo nazvati dvostruko
povezani popis.
To bi omogućilo mi je da vrsta unatrag puno lakše i bez mene,
programer, da se zadrži pratili ručno -
doista ručno -
mjesta gdje sam bio prije na popisu.
Dakle, nećemo to učiniti.
Držat ćemo ga jednostavno zato jer je to će doći na cijenu, dvostruko
puno prostora za pokazivače, ako želite drugu.
Ali to je doista česta struktura podataka poznat kao
dvostruko povezani popis.
>> Idemo napraviti konačni primjer ovdje i staviti ovi momci iz njihove bijede.
Dakle malloc 20.
Hajde se iz prolaz tamo.
U redu, što je vaše ime?
>> STUDENT: [nečujno].
>> ZVUČNI 1: Žao mi je?
>> STUDENT: [nečujno].
>> ZVUČNI 1: Demeron?
OK daj se.
Ti će se 20.
Vi očito će pripadaju između 17 i 22.
Pa neka mi naučili svoju lekciju.
Ja ću početi pokazivač pokazujući na Briana.
A ja ću imati svoju lijevu ruku Samo ažurirajte Briana kao što sam premjestiti na
Jason, provjera radi 20 manje od devet?
Ne.
Je 20 manje od 17?
Ne.
Je 20 manje od 22?
Da.
Dakle, što upućuje ili šake morati promijeniti gdje se pokazuje sada?
>> Dakle, možemo napraviti 17 pokazujući na 20..
Dakle, to je u redu.
Gdje želimo ukazati pokazivač sada?
Na 22..
A znamo gdje je 22, opet hvala na moj privremenog pokazivač.
Tako smo u redu tamo.
Dakle, zbog ovog privremenog skladištenja Ja sam pratila gdje je svatko.
A sada možete vizualno može ići u kojoj spadate, a sada trebamo 1, 2, 3,
4, 5, 6, 7, 8, 9 stres loptice, i krug pljeskom
ovi dečki, ako smo mogli.
Lijepo učinili.
>> [PLJESAK]
>> ZVUČNI 1: U redu.
A možda bi komada papira, kao uspomena.
>> U redu, tako da, vjeruj mi to je puno lakše prolaziti kroz koje s
ljudi nego što je s aktualnom kodu.
No, ono što ćete pronaći u samo trenutak Sada, je li to ista - Oh, hvala ti.
Hvala vam -
je da ćete uvidjeti da je iste podatke Struktura, povezani popis, može zapravo
se koristiti kao građevinski blok još sofisticirane strukture podataka.
>> I shvatite previše tema ovdje je da Apsolutno smo uveli više
složenosti u provedbi ovog algoritma.
Ubacivanje, a ako smo prošli kroz njega, brisanje i pretraživanje, je malo
složeniji od njega bio s nizom.
No, mi dobiti neke dinamizam.
Mi smo dobili adaptivni strukturu podataka.
>> Ali opet, plaćamo cijenu što neke Dodatni složenosti, kako u
njegovu provedbu.
I mi smo odustali slučajni pristup.
A da budem iskren, ne postoji neki lijep očistite slajd Mogu vam dati da
Ovdje piše da je razlog zašto povezani popis je bolje nego niz.
I ostaviti ga na to.
Budući da je tema ponovno pojavljivanje sada, čak i više u narednim tjednima, je
da nije nužno točan odgovor.
>> To je razlog zašto imamo zasebnu os dizajna za problematična setovima.
To će biti vrlo osjetljiva na kontekst želite li koristiti ove podatke
strukture ili da je jedan, i to će ovisi o tome što je važno za vas u smislu
resursa i složenosti.
>> No, dopustite mi predložiti da se idealni podataka Struktura, sveti gral, bio bi
nešto što je stalno vremena, bez obzira na to koliko je stvari
unutar njega, ne bi bilo iznenađujuće ako se struktura podataka vratio odgovore u
stalno vrijeme.
Da.
Ova riječ je u svom velikom rječniku.
Ili ne, to znači da je nema.
Ili bilo koji takav problem postoji.
Pa ćemo vidjeti, ako ne možemo barem uzeti jedan korak prema tome.
>> Dopustite mi da predloži novu strukturu podataka koji može se koristiti za različite stvari,
u ovom slučaju zove hash tablicu.
I tako smo zapravo natrag pogledavši na polju, u ovom slučaju, i
nešto samovoljno, ja sam izvući ovu hash tablicu kao polje s vrstom
dvodimenzionalno polje -
odnosno to je prikazano ovdje kao dva dimenzionalni niz - ali to je samo
niz veličine 26, tako da ako se nazovite polje stol, stolni nosač
nula pravokutnik na vrhu.
Tablica nosač 25 je pravokutnik na dnu.
A to je, kako sam mogao nacrtati podatke struktura u kojoj želim pohraniti
Imena osoba.
>> Tako, primjerice, i neću povući Cijela stvar ovdje na pretek, ako sam
je ovaj niz, što ja sada idem nazovite hash tablicu, a to je opet
Mjesto na nuli.
Ovo ovdje je location jedan, i tako dalje.
Ja tvrdim da želim koristiti ove podatke Struktura, radi rasprave,
za pohranu imena ljudi, Alice i Bob i Charlie i ostali takvi nazivi.
Tako da je to sada, kao počeci od, recimo, u rječniku
s puno riječi.
Oni se dogoditi da se imena u našem primjeru ovdje.
I to je sve previše povezan, možda, provodi provjeru pravopisa, kao i mi
Možda za postavljanje šest problema.
>> Dakle, ako imamo niz ukupne veličine 26 , tako da je ovo 25. Mjesto
na dnu, i tvrde da je Alice Prva riječ u rječniku
imena koje se želim umetnuti u RAM, u ovu strukturu podataka, gdje su
instinkt vam govori da je Alice-a Naziv bi trebao ići u tom polju?
>> Imamo 26 opcija.
Gdje želimo ju staviti?
Mi joj želimo u zagradi nula, zar ne?
Za Alice, nazovimo tu nulu.
A B će biti jedan, i C će biti dva.
Tako ćemo pisati Alice je ime ovdje.
Ako smo onda ubacite Bob, njegov Ime će ići tamo.
Charlie će ići tamo.
I tako dalje dolje kroz ova struktura podataka.
>> Ovo je divno struktura podataka.
Zašto?
Pa ono je vrijeme rada Umetanje ljudski ime u ovo
Podaci o strukturi upravo sada?
S obzirom da je ova tablica je proveden, doista, kao polje.
Pa to je konstantna vrijeme.
To bi jednog.
Zašto?
>> Pa kako ste utvrdili Alice kojoj pripada?
Možete pogledati na koje slovo njenog imena?
Prvi.
I možete doći, ako je string, samo gleda na žici
Nosač nuli.
Dakle nultoga karakter niza.
To je jednostavno.
To smo učinili u kripto Raspored tjedna.
I onda kada znate da je Alice Pismo je kapital, možemo oduzimati
65 off ili grada A sama, koji nam daje nulu.
Dakle, sada znamo da je Alice spada na mjestu nula.
>> I dao pokazivač do tih podataka Struktura, neke vrste, koliko dugo traje
to mi se pronaći mjesto nuli u niz?
Samo jedan korak, pravo je vrijeme konstanta zbog slučajnog pristupa smo
Predloženi je značajka niz.
Tako je u kratkom, figuring out ono što indeksa Alice je ime, što je, u
ovaj slučaj je, ili ćemo jednostavno riješiti da je na nulu, gdje je B je jedan i C je
dva, računajući da se Vrijeme je konstanta.
Samo moram gledati na svom prvom pismu, figuring out gdje je nula
Niz je također konstantna vrijeme.
Dakle, to je tehnički kao dva koraka sada.
Ali to je uvijek konstantna.
Dakle, mi zovemo taj veliki O jednog, pa smo umetnuta Alisa u ovoj tablici u
stalno vrijeme.
>> Ali, naravno, ja sam se naivna ovdje, zar ne?
Što ako je Aaron u razredu?
Ili Alicia?
Ili bilo koji drugi nazivi počinju sa A. Gdje ćemo staviti
ta osoba, zar ne?
Mislim, upravo sada ima samo tri ljudi na stolu, pa možda smo
treba staviti na mjesto Aarona nula jedan, dva, tri.
>> Točno, mogao sam staviti ovdje.
Ali onda, ako ćemo pokušati umetanje Davida u ovaj popis, u kojem nema Davida gdje?
Sada naš sustav počne rješava prema dolje, zar ne?
Jer sada je David završava ovdje ako je Aron je zapravo ovdje.
I sad je cijela ova ideja da čist struktura podataka koje nam daje
stalne vrijeme ubacivanja više nije stalno vrijeme, jer moram
ček, oh, dovraga, netko je već na Alice mjesto.
>> Dopustite mi da provjerite ostatak ove podatke Struktura, u potrazi za mjesto staviti
netko poput Aaronovoj ime.
I tako to previše počinje da se linearno vrijeme.
Štoviše, ako se sada želite pronaći Aaron je u ovom strukturom podataka, a vi
provjeriti i Aronov ime nije ovdje.
U idealnom slučaju, samo bih rekao Aronu Ne u strukturu podataka.
Ali ako to početak stvaranje prostora za Aaron tamo gdje je trebao biti D
ili E, da, najgorem slučaju, morate provjeriti Cijela struktura podataka, u
kojem slučaju to prerasta u nešto linearno u veličini stola.
>> Pa dobro, ja ću to popraviti.
Problem je što sam imala 26 elemenata u tom polju.
Dopustite mi da ga promijeniti.
Ups.
Dopustite mi da ga promijeniti, tako da radije bude mjesta veličina 26 ukupno, primijetit dno
Indeks će se promijeniti na n minus jedan.
Ako 26 je očito premali za ljude ' imena, jer ima na tisuće
Imena svijeta, hajdemo napraviti po 100 ili 1000 ili 10000.
Ajmo izdvojiti puno više prostora.
>> Pa to ne mora nužno smanjiti vjerojatnost da nećemo imati dva
ljudi s imenima počevši, i tako, da ćeš pokušati staviti
imena na mjesto nule još uvijek.
Oni još uvijek će se sudariti, koji znači da smo još uvijek je potrebno rješenje staviti
Alice i Aron i Alicia i druge nazivi počinju s A na drugom mjestu.
No, koliko je problem je to?
Koja je vjerojatnost da ima sudara u podacima
struktura kao što je ovaj?
>> Pa, neka mi - mi ćemo se vratiti na to pitanje ovdje.
A pogledajte kako bismo mogli Prvi ga riješiti.
Dopustite mi povući ovaj prijedlog ovdje.
Ono što smo upravo opisali je algoritam, heuristička zove linearno
sondiranje pri čemu, ako ste pokušali umetanje nešto ovdje u ove podatke
struktura, koja se zove hash tablicu, i tu nema mjesta tamo,
doista ispitati strukturu podataka ček, je li to dostupno?
Je li to Dostupan je to dostupno?
Je li to dostupno?
I kad je konačno, umetanja ime koje ste prvotno namijenjen
na drugom mjestu na toj lokaciji.
No, u najgorem slučaju, samo mjesto može biti samo dno podataka
struktura, sami kraj niza.
>> Dakle, linearno sondiranje, u najgorem slučaju, prerasta u linearni algoritam gdje
Aaron, ako se dogodi da se umeće posljednja u ovom strukturom podataka, mogao bi
sudaraju s ovom prvom mjestu, ali onda na kraju od strane peh na samom kraju.
Dakle, to nije stalna Vrijeme sveti gral za nas.
Ovaj pristup umetanje elemenata u struktura podataka zove hash
Tablica se ne čini da se stalno Vrijeme barem ne u općem slučaju.
To može prenijeti u nešto linearno.
>> Pa što ako smo riješili sudara nešto drugačije?
Dakle, ovdje je sve sofisticiraniji pristup na ono što je još uvijek
zove hash tablicu.
I mljeveno meso, kao stranu, što Mislim da je indeks
Ja tekstu ranije.
Za hash nešto može biti misao kao glagol.
>> Dakle, ako ste hash Alice je ime, hash funkciju, da tako kažemo,
trebao vratiti broj.
U ovom slučaju je nula, ako je ona spada u Mjesto na nuli, ako je jedan zaposlen na
Mjesto jedan, i tako dalje.
Dakle, moj hash funkcija je do sada bio super jednostavna, samo gleda
prvo slovo u nečije ime.
Ali hash funkcija uzima kao Ulaz neki komad podataka,
string, int, što god.
I to ispljune u pravilu donosi niz.
A taj broj je gdje da se podaci Element pripada u strukturu podataka
poznat ovdje kao hash tablicu.
>> Dakle, samo intuitivno, to je malo drugačiji kontekst.
To zapravo se odnosi na primjer uključuju rođendane, gdje
Tu bi moglo biti čak 31 dana u mjesecu.
No, ono što je ova osoba odlučiti učiniti u slučaju sudara?
Kontekst sada se, ne sudar imena, ali sudar rođendane,
ako dvije osobe imaju isti rođendan 2. listopada, na primjer.
>> STUDENT: [nečujno].
>> ZVUČNI 1: Da, pa ovdje imamo dugovima povezanim listama.
Tako to izgleda malo drugačije nego što smo to ranije nacrtao.
Ali mi se čini da moraju niz na lijevoj strani.
To je jedan indeks, jer nema poseban razlog.
Ali to je još uvijek niz.
To je niz pokazivača.
A svaki od tih elemenata, a svaki od ti krugovi ili kose crte - Slash
predstavlja null - svaki od tih pokazivače očito pokazuje da
što je struktura podataka?
Popis povezani.
>> Tako sada imamo mogućnost za Teško kod u našem programu
veličina tablice.
U ovom slučaju, znamo da je nikada nije više od 31 dana u mjesecu.
Dakle, teško kodiranje vrijednost kao 31. je razumni u tom kontekstu.
U kontekstu imena, tvrdi kodiranja 26 Nije nerazumno da Narodna
samo nazivi početi s, primjerice, abeceda uključuje do Z.
>> Mi može strpati ih sve u tim podacima Struktura tako dugo dok, kada smo dobili
sudara, mi ne stavi imena ovdje, smo, umjesto da od tih stanica
ne kao nizovi sami, već kao upućuje na, primjerice, Alice.
A onda je Alice može imati još jedan pokazivač na drugo ime počinje sa
A. I Bob zapravo ide ovamo.
>> A ako postoji drugi naziv počinje sa B, on završi tamo.
I tako svaki od elemenata ove stol dva, ako smo ovu
malo više pametno -
dođi -
Ako smo ovu malo više pametno, sada postaje adaptivna podatke
struktura, u kojoj ne postoji ograničenje tvrdi o tome koliko elemente možete umetnuti
u nju, jer ako imate sudara, to je u redu.
Samo ići naprijed i dodati u ono što smo vidjeli malo prije bio
poznat kao povezane liste.
>> Pa neka je pauzu za samo trenutak.
Koja je vjerojatnost sudara u prvom redu?
Točno, možda sam više razmišljam, možda Ja sam preko inženjering ovaj problem,
jer znaš što?
Da, ja mogu smisliti proizvoljna Primjeri off vrhu moje glave poput
Allison i Aaron, ali u stvarnosti, dao ravnomjerniji
ulaza, to je neki slučajni ubacivanja u strukturu podataka, što je stvarno
vjerojatnost sudara?
Pa ispada, to je zapravo super visoka.
Dopustite mi generalizirati ovo Problem je što je ovaj.
>> Dakle, u prostoriji od n CS50 učenika, što je vjerojatnost da je barem
dva učenika u sobi imaju isti rođendan?
Tako da je ono što. Nekoliko Hund -
200, 300 ljudi ovdje i nekoliko sto ljudi kod kuće i danas.
Dakle, ako ste htjeli da se zapitamo što je vjerojatnost dvije osobe
U ovoj sobi ima isti rođendan, možemo to shvatiti.
A ja tvrdim zapravo postoje dvije ljudi s istim rođendan.
>> Na primjer, bilo tko ima danas rođendan?
Jučer?
Sutra?
U redu, tako da se osjeća kao da ću se morati učiniti ovaj 363 ili tako više
puta zapravo shvatiti Ako imamo sudar.
Ili smo samo mogli to učiniti matematički umjesto dosadnog
to.
I predložiti sljedeće.
>> Tako sam predložio da smo mogli modelirati Vjerojatnost da dvije osobe imaju
Isti rođendan kao vjerojatnost od 1 minus vjerojatnost nitko ima
isti rođendan.
Dakle, da biste dobili ovaj, a to je samo fancy način pisanja ovog, za
Prva osoba u sobi, on ili ona može imati jednu od moguće
rođendana uz pretpostavku 365 dana u godini, s isprike osoba s
29. veljače rođendan.
>> Dakle, prva osoba u ovoj sobi je besplatan imati bilo koji broj rođendane
od 365 mogućnosti, tako da mi ćemo to učiniti 365 podijeljeno sa 365,
što je jedan.
Sljedeća osoba u sobi, ako je cilj je izbjeći sudar, mogu samo
ima njegov ili njezin rođendan o tome mnogi različiti mogući dana?
364.
Dakle Drugi član u ovom izrazu je u biti radiš tu matematiku za nas
oduzimanjem off jedan mogući dan.
A onda sljedeći dan, sljedeći dan, Sljedeći dan do ukupnog broja
ljudi u sobi.
>> A ako smo onda razmislite, što je onda Vjerojatnost ne svi imaju
jedinstvene rođendana, ali opet minus 1 da, ono što smo dobili je izraz
koji može vrlo maštovito izgledati ovako.
No, to je zanimljivije gledati na vizualno.
To je shema gdje je na x-osi je broj ljudi u sobi,
broj rođendane.
Na y-osi je vjerojatnost od sudara, dvoje ljudi
ima isti rođendan.
>> I takeaway iz ove krivulje da čim dođete do nekih 40
studentima, ti si se na 90% vjerojatnosti combinatorically od dva
ljudi ili više imaju isti rođendan.
A kad dođete do sviđa 58 ljudi to je gotovo 100% od priliku dva
ljudi u sobi će imati Isti rođendan, iako postoji
365 ili 366 moguće kante i samo 58 ljudi u sobi.
Samo statistički vjerojatno ćete dobili sudara, koji se u kratkom
motivira ovu raspravu.
To čak i ako mi se sviđa ovdje, a početi s ovih lanaca, mi smo još uvijek
će imati sudara.
>> Tako da moli pitanje, što je Trošak radi umetanja i brisanja
u strukture podataka kao što je ovaj?
Pa neka mi predložiti -
i neka mi se vratiti na zaslonu tijekom ovdje - ako smo n elemenata u
popis pa ako nastojimo umetnuti n elemenata, a mi smo
koliko je ukupno kante?
Recimo 31 Ukupno kante u slučaju rođendane.
Što je maksimalno trajanje jedne od tih lanaca potencijalno?
>> Ako opet postoji 31 ​​moguće rođendana u određenom mjesecu.
I mi smo samo nakupina svima -
zapravo to je glupo primjer.
Učinimo 26 umjesto.
Dakle, ako su zapravo ljudi čija su imena početi s do Z, dajući
nas 26 mogućnosti.
I mi smo pomoću strukture podataka kao što su jednom smo upravo vidjeli, pri čemu smo
niz pokazivača, od kojih svaki ukazuje na povezanoj liste, gdje je
Prvi popis je svatko s imenom Alice.
Drugi popis je svaka s ime počinje sa A, s početkom
s B, i tako dalje.
>> Što je vjerojatno duljina svakog od ti popisi ako pretpostavimo lijepo čisti
distribucija imena kroz Z u cijeloj strukturi podataka?
Tu je n ljudi u strukturi podataka podijeljeno 26., ako su lijepo
rasporediti tijekom cijele struktura podataka.
Tako da je duljina svakog od tih Lanci je n podijeljen 26..
No, u velikom O zapisu, što je to?
Što je to zapravo?
Dakle, to je stvarno samo n, zar ne?
Zato što smo rekli u prošlosti, uh kako ste podijeliti po 26 godina.
Da, u stvarnosti to je brži.
No, u teoriji, to nije bitno sve što brži.
>> Dakle, mi se ne čini da se sve to puno bliže tom sveti gral.
U stvari, to je samo linearno vrijeme.
Zapravo, u ovom trenutku, zašto ne bismo samo koristiti jedan ogroman povezanog popisa?
Zašto ne samo koristiti jedan veliki Niz za pohranu imena
svi u prostoriji?
Pa, postoji li još uvijek nešto uvjerljiv o hash tablicu?
Ima li još nešto uvjerljiv o strukturi podataka
da izgleda ovako?
Ovo.
>> STUDENT: [nečujno].
>> ZVUČNI 1: Točno, i opet ako je samo linearni vremenski algoritam, te
linearni vremenski struktura podataka, zašto ne ja Samo pohraniti svačije ime u big
polje, ili u velikom povezan popisu?
I prestani raditi CS tako puno teže nego što treba biti?
Što je uvjerljiv o tome, čak i iako sam ga izgrebao out?
>> STUDENT: [nečujno].
>> ZVUČNI 1: uguravanje nisu?
Skupo više.
Dakle ubacivanje potencijalno mogla dalje biti konstantna vrijeme, čak i ako vaše podatke
struktura izgleda ovako, niz pokazivače, od kojih je svaki pokazuje na
potencijalno linked list.
Kako bi ste postigli konstantna Vrijeme umetanje imena?
Staviti ga u prednjem, zar ne?
>> Ako ćemo žrtvovati pogodak dizajn iz ranije, u kojoj smo htjeli zadržati
svačija ime, primjerice, sortirati, ili sve od brojeva na pozornici razvrstani,
Pretpostavimo da imamo nerazvrstani povezani popis.
To košta samo nam jedan ili dva koraka, kao u slučaju Ben i Briana
ranije, umetnuti element na početak popisa.
Dakle, ako mi nije stalo sortiranja sve od nazivima koji počinju ili sve
nazivi počinju sa B, možemo dalje postigla konstantna umetanje vrijeme.
Sada se gleda Alice ili Bob ili bilo koje ime općenito je još uvijek ono?
To je velika O n podijeljeno 26., u idealan slučaj u kojem su svi ravnomjerno
distribuira, gdje je kao i mnogi ih jer postoji Z-, što je vjerojatno
nerealno.
Ali to je uvijek linearno.
>> Ali ovdje smo došli natrag do točke od asimptotičke zapis bića
teoretski istina.
No, u stvarnom svijetu, ako ja tvrdim da je moj program može učiniti nešto 26 puta
brže od tvoje, čiji je program ćete radije koristite?
Tvoje ili moje, što je 26 puta brže?
Realno, osoba čije je 26. puta brže, čak i ako je teorijski
naši algoritmi izvoditi u isto asimptotičnu prikazivati ​​vrijeme.
>> Dopustite mi da predlaže drugačije Rješenje uopce.
A ako to ne blow your mind, smo iz strukture podataka.
Dakle, to je to trie -
vrsta glupo ime.
Ona dolazi iz retrievals, a riječ precizirao trie, t-r-I-e, zbog
Tečaj dohvat zvuči kao trie.
Ali to je povijest od riječi trie.
>> Dakle trie je doista neka vrsta drveta, i to je također igrati na tom riječju.
I iako ne sasvim mogu vidjeti s ovim prikazom, trie je
Stablo strukturiran, poput obiteljskog stabla s jedan predak na vrhu i puno
unučadi i praunuci što je lišće na dnu.
No, svaki čvor u trie je polje.
I to je u niz - i neka je pojednostavljuju za trenutak - to je
polje, u ovom slučaju, na veličinu 26, gdje je svaki čvor je opet niz veličine
26, u kojoj se nultoga element u koji polje predstavlja, a posljednji
element u svaki takav Niz predstavlja Z.
>> Dakle, ja predlažem, a zatim, da su ti podaci Struktura, poznat kao trie, može biti
Također se koristi za pohranu riječi.
Vidjeli smo trenutak prije kako bismo mogli pohraniti riječi, ili u ovom slučaju imena, a mi
ranije vidjeli kako možemo pohraniti brojeve, ali ako ćemo se usredotočiti na imena ili nizovi
ovdje, ono što je zanimljivo primijetiti.
Ja tvrdim da je ime Maxwell unutar ove strukture podataka.
Gdje vidite Maxwell?
>> STUDENT: [nečujno].
>> ZVUČNI 1: Na lijevoj strani.
Dakle, ono što je zanimljivo s ovim podacima Struktura je umjesto trgovine na
string M-A-X-W-E-L-L backslash nula, sve contiguously, što ste to učiniti umjesto
slijedi.
Ako je ovo trie kao i strukture podataka, svaki od čvorova čija je ponovno polje,
i želite pohraniti Maxwell, najprije Indeks pa je korijen u čvor, tako da
govoriti, najviši čvor, na licu mjesta M, desno, tako
otprilike u sredini.
A onda od tamo, slijedite pokazivač na dijete čvorova, da se tako izrazim.
Dakle, u smislu obiteljskog stabla, slijedite ga prema dolje.
I da vas dovesti do drugog čvora na lijevoj strani, koji je
samo još jedan niz.
>> A onda, ako želite pohraniti Maxwell, vam pokazivač koji predstavlja
, Što je ovaj ovdje.
Zatim idete na sljedeći čvor.
I napomena - to je razlog zašto je slika Malo obmanjuje -
ovaj čvor izgledaju super maleni.
No, s desne strane je ovo Y i Z. To je samo autor je odrezan
slika tako da možete zapravo vidjeti stvari.
Inače ovu sliku će biti jako široka.
Dakle, sada ste indeksa na mjesto X, a zatim W, A E, onda L, zatim L. Onda što je
znatiželja?
>> Pa, ako ćemo koristiti ovu vrstu new preuzmu kako pohraniti string u
struktura podataka, još uvijek je potrebno suštini prekrižite u podacima
struktura koja riječ završava ovdje.
Drugim riječima, svaki od tih čvorova nekako mora zapamtiti da smo
zapravo slijedi sve ove naputke i ostavljajući malo
prezla na dolje ovdje ove Struktura ukazati M-A-X-W-E-l-L
Upravo u tom strukture podataka.
>> Tako bismo mogli napraviti na sljedeći način.
Svaka od čvorova u slici samo mi pila ima jedan, niz veličine 27.
I to je sada 27, jer se u p postavili šest, mi zapravo ću ti apostrof,
tako da možemo imati nazive poput O'Reilly i drugi sa apostrofe.
No, ista ideja.
Svaki od tih elemenata u niz ukazuje na struct
čvora, pa samo čvor.
Dakle, ovo je jako podsjeća našeg povezanog popisa.
>> I onda imam Boolean, kojoj ću nazovite riječ, koja samo što će biti
Istina, ako riječ završava na ovo čvor u stablu.
To je učinkovito predstavlja malo Trokut smo vidjeli maloprije.
Dakle, ako je riječ završava na taj čvor u stabla, to polje će riječ biti istina,
koji je koncepcijski provjere off, ili mi smo izradu ovog trokuta, da postoji
je riječ ovdje.
>> Dakle, ovo je trie.
I sad je pitanje, što je njegova prikazivati ​​vrijeme?
Je li to veliki O n?
Je li to nešto drugo?
Pa, ako ste n imena u ove podatke Struktura, Maxwell-a samo jedan od
ih, što je dužina trajanja umetanja ili pronalaženje Maxwell?
Što je trajanje umetanja Maxwell?
Ako postoji n druga imena Već u tablici?
Da?
>> STUDENT: [nečujno].
>> ZVUČNI 1: Da, to je duljina Ime je, zar ne?
Tako da M-a-X-W-e-l-l tako da se osjeća kao što je ovaj Algoritam je velika O od sedam.
Sada, naravno, ime će biti različite duljine.
Možda je to kratko ime.
Možda to nije ime.
No, ono što je ključno je da To je stalni broj.
A možda to zapravo nije konstantna, Ali Bog, ako je realno, u
rječnik, vjerojatno postoji neki limit o broju slova u
ime osobe u određenoj zemlji.
>> I tako možemo pretpostaviti da vrijednost je konstantna.
Ja ne znam što je to.
To je vjerojatno veći od mislimo da je.
Budući da uvijek postoji neki kutak Slučaj s ludim dugo ime.
Dakle, nazovimo ga k, ali to je još uvijek konstantna prilici, jer svaka
ime u svijetu, barem u određenoj zemlji, je da dužina ili
kraći, tako da je stalna.
No, kad smo rekli nešto veliko O konstantne vrijednosti, što je to
stvarno odgovara?
To je stvarno ista stvar kako kaže stalnu vrijeme.
>> Sada smo vrsta varanja, zar ne?
Mi smo vrsta utjecati neke teorije Ovdje je reći da je dobro, kako je od k
zapravo samo naručiti od jedne, i to je stalno vremena.
Ali to je stvarno.
Budući da je ključ uvid ovdje je da ako smo n imena već u to
struktura podataka, a mi insert Maxwell, je količina vremena koje je potrebno da nam
umetnite Maxwell uopće zahvaćena po tome koliko drugi ljudi
u strukturi podataka?
Ne čini se.
Ako sam imala milijardu više elemenata ove trie, a zatim umetnite Maxwell, je
on uopće utjecati?
Ne.
I to je za razliku od bilo kojeg od podataka dan Strukture koje smo vidjeli do sada, gdje je
vrijeme trajanja svog algoritma je posve neovisno o tome koliko
stvar je ili nije već u toj strukturi podataka.
>> I tako s tim pruža vam je sada Prilika za p set šest, što će
ponovno uključiti provedbu svom alat za provjeru pravopisa, čitanje u 150.000
Riječi, kako najbolje pohraniti da nije nužno očito.
I iako sam težio pronaći Sveti Gral, ja ne
tvrde da je trie.
U stvari, hash tablicu može vrlo dobro dokazati da će biti puno učinkovitiji.
Ali oni su samo -
to je samo jedan od dizajnerskih odluka ćete morati napraviti.
>> No, u zatvaranju uzmimo 50-ak sekundi za zaviriti u ono što se nalazi
uoči sljedećeg tjedna i dalje smo tranziciji iz ovog naredbenog retka
svijeta, ako C programe na stvari webu temelji i jezici poput PHP i
JavaScript i internet sama, protokole kao što su HTTP, što ste
uzeti zdravo za gotovo već godinama Sada, i upisali najviše svaki
dan, možda, ili vidjeli.
A mi ćemo početi guliti natrag slojevi što je internet.
A ono što je kod koji pozadini današnji alata.
Tako 50 sekundi ovog teaser ovdje.
Dajem vam ratnicima Net.
>> [Video reprodukciju]
>> -On je došao s porukom.
Uz protokola samo njegov.
On je došao na svijet okrutne firewall, nemarne routera, i opasnosti daleko
gora od smrti.
On je brz.
On je jak.
On je TCPIP.
I on je dobio svoju adresu.
Ratnici Net.
>> [END video reprodukciju]
>> ZVUČNI 1: Tako je internet radit će od sljedećeg tjedna.