>> [Glazbom]
>> ANDI PENG: Dobrodošli u tjednu 6. poglavlju.
Odstupili smo od našeg standarda Odjeljak vrijeme utorak
Poslijepodne na ovu lijepu nedjelju ujutro.
Hvala vam svima koji mi se pridružio i danas, ali ozbiljno,
okrugli pljesak.
>> To je prilično velika truda.
Ja gotovo da nije ni to napraviti na vrijeme, ali to je u redu.
Dakle, znam da svi vi Upravo to je napravio na kvizu.
Prije svega, dobrodošli na Druga strana toga.
>> Drugo, mi ćemo govoriti o tome.
Razgovarat ćemo o kvizu.
Razgovarat ćemo o tome radite u razredu.
Vi ćete biti u redu.
Imam svoje kvizova za što na kraju ovdje
pa ako ti dečki žele uzeti pogledajte ga, potpuno u redu.
>> Tako brzo prije nego što počnemo je program za danas je kako slijedi.
Kao što možete vidjeti, mi smo osnovi brzo plamena
kroz cijelu hrpa strukture podataka jako, jako, jako brzo.
Dakle, kao takva, ona neće biti super interaktivne danas.
To ću biti ja vrsta vikanje stvari koje, i ako sam vas zbuniti,
ako idem prebrzo, javite mi.
Oni su samo različite podatke strukture, a kao dio
Vaše pset za to nadolazeći tjedan, vi ćete
biti zatraženo da provede jedan od njih, možda dva them-- dvije od njih
u svom pset.
U redu, tako da sam samo ću početi s nekim najavama.
Mi ćemo ići preko dimnjaka i redovima više u Dubina od onoga što smo učinili prije kvizu.
Mi ćemo ići preko povezan popis opet, još jednom,
više u dubinu nego što smo imali prije kvizu.
A onda ćemo razgovarati o hash stolovi, drveće i napad, koji se
su svi prilično je potrebno za vaš pset.
A onda ćemo ići preko neke korisne savjete za pset5.
>> U redu, tako kviz 0.
Prosječna je 58%.
To je bio vrlo nizak, pa vi svi učinio jako, jako dobro u skladu
s tim.
>> Prilično mnogo, pravilo je, ako ste unutar standardnog odstupanja od srednje vrijednosti
pogotovo jer smo u manje udoban poglavlje, ti si potpuno u redu.
Vi ste na pravom putu.
Život je dobar.
>> Znam da je to zastrašujuće misliti da Dobio sam kao 40% na ovom kvizu.
Idem uspjeti ovaj razred.
Obećavam ti, ti nisi neće uspjeti razred.
Ti si potpuno u redu.
>> Za one od vas koji je dobio više srednja, impresivna, impresivno,
kao, ozbiljno i učinio.
Ja ih imati sa mnom.
Dodite ih dobiti na kraju sekcije.
Pustiti mene znati ako imate bilo pitanja, pitanja s njima.
Zbrojimo li vaš rezultat krivo, javite nam.
>> U redu, tako da pset5, ovo je stvarno čudno tjedan za Yale u smislu
da je naš pset je zbog Srijeda u podne, uključujući
pokojni dan, tako da je zapravo teoretski zbog utorak u podne.
Vjerojatno nitko nije završen u utorak u podne.
To je sasvim u redu.
Mi ćemo imati radno vrijeme Večeras, kao i ponedjeljak navečer.
A sve dijelove ovog tjedna će zapravo se pretvorio u radionicama,
pa slobodno ubacite bilo poglavlje želite,
i oni će biti neka vrsta mini-pset radionice za pomoć na to.
Dakle, kao takav, to je jedini odjeljak gdje smo gradivo.
Svi ostali dijelovi će se usredotočiti isključivo na pomoć za pset.
Da?
>> PUBLIKA: Gdje su uredski vrijeme?
>> ANDI PENG: Radno vrijeme tonight-- oh, dobro pitanje.
Mislim uredski večeras vrijeme u Teal ili Commons.
Ako ste provjerili online CS50 i idete na uredovno vrijeme,
tamo bi trebao biti raspored koji govori gdje su svi od njih su.
>> Znam, bilo večeras ili sutra je Teal,
i mislim da možemo imati zajednička za druge noći.
Nisam siguran.
Dobro pitanje.
Provjerite na CS50.
>> Cool, bilo kakvih pitanja u vezi s raspored za sljedeća tri dana kao što je?
Obećavam vam dečki poput Davida rekao, ovo je vrh brda.
Vi ste gotovo tamo.
Samo još tri dana.
Doći, a onda ćemo svi doći.
Mi ćemo imati lijepo CS-slobodan pauzu.
Dobrodosao natrag.
Mi ćemo zaroniti u web programiranje i razvoj,
stvari koje su vrlo zabavna odnosu na neke druge psets.
I to će biti hladan, a ćemo imati puno zabave.
Imat ćemo više slatkiša.
Žao nam je zbog slatkiša.
Zaboravio sam slatkiše.
Bilo je grubo jutro.
Dakle, vi ste gotovo tamo, i ja sam jako ponosna na vas momci.
>> U redu, tako da gomila.
Tko je ljubio pitanje o Jacku i njegova odjeća na kvizu?
Nitko?
U redu, to je u redu.
>> Dakle, u biti kao što možete slika Jack, ovaj tip ovdje,
voli uzeti odjeću iz vrha dimnjaka,
i on ga stavlja natrag na stog nakon što je učinio.
Dakle, na ovaj način, on nikada Čini se da je dobivanje
na dnu od stog u svojoj odjeći.
Dakle, ova vrsta opisuje osnovna struktura podataka
kako stog se provodi.
>> U biti, misliti na stog kao bilo stog objekata
gdje staviti stvari na vrhu, a onda ih pop iz vrha.
Dakle, LIFO je akronim volimo da use-- posljednji u, prvi van.
I tako trajati se na vrhu stog je prvi onaj koji izlazi.
I tako su dva pojma smo željeli povezati
s koje se zove guranje i pop.
Kada gurnuti nešto na stog, a ti ga pop natrag gore.
>> I tako mislim da je ovo neka vrsta apstraktan pojam za one od vas
koji žele vidjeti se poput stvarna provedba ovog
u stvarnom svijetu.
Koliko ste napisali esej možda kao sat prije nego što je zbog,
a ti slučajno izbrisane ogromna komad od toga, kao što je slučajno?
I što onda učiniti upravljač koristimo ga vratiti?
Kontrola-Z, zar ne?
Kontrola-Z, tako da je količina vremena da Control-Z je spasio moj život,
je spasio moju guzicu, svaki put koji je proveden kroz dimnjak.
>> U suštini sve informacije to je na svom Word dokument,
to dobiva gurnuti i skinuti po volji.
I tako u biti, kad god vas izbrisati sve, što ga pop natrag gore.
A onda, ako vam je potrebna leđa, te gurnuti ga, što je ono što Control-C radi.
I tako u stvarnom svijetu funkcija koliko jednostavne strukture podataka
može pomoći u svakodnevnom životu.
>> Tako struct je način na koji mi zapravo stvoriti hrpu.
Mi upišite definirati struct, a zatim zovemo ga stog na dnu.
A unutar dimnjaka, imamo dva parametra
da smo u biti može manipulirati, tako da imamo char kapacitet žice zvijezda.
>> Sve što se radi stvara niz
da možemo pohraniti što god želite koje možemo odrediti svoj kapacitet.
Kapacitet je samo max iznos Stavke možemo staviti u ovaj niz.
Veličina int je brojač koji čuva pjesma o tome kako mnoge stvari trenutno
u snopu.
Pa onda možemo pratiti, A, i koliko je velika stvarna stog,
a, B, koliko to stog ispunjen smo jer ne želimo
da se prelijevati preko onoga što je naš kapacitet je.
>> Tako, na primjer, ovu lijepu Pitanje je bilo na svom kvizu.
U biti kako ćemo gurnuti na vrhu dimnjaka.
Prilično jednostavan.
Ako na to gledate, ćemo provesti kroz to.
Ako [nečujan] size-- zapamtite, kad god
želite pristupiti bilo parametar unutar STRUCT,
radite ime struct.parameter.
>> U tom slučaju, s je naziv naše stog.
Želimo pristupiti veličinu od toga, pa mi s.size.
Tako dugo dok je veličina nije jednak kapacitet ili dok
što je manje od kapaciteta, bilo bi raditi ovdje.
>> Želite pristupiti iznutra Vaše stog, tako s.strings,
i ti ćeš staviti da novi broj koje želite umetnuti u tamo.
Recimo samo da će htjeti umetnite int n na stog,
smo mogli učiniti s.strings, zagrade, s.size jednak n.
Budući da je veličina gdje smo Trenutno u snopu
ako ćemo gurati što dalje, samo mi pristupiti
gdje god je veličina je trenutna punina stog,
a mi gurnuti int n na njega.
A onda želimo biti sigurni da Mi smo također povećavati veličinu n,
tako da možemo pratiti imamo dodaje dodatni stvar na stog.
Sada imamo veću veličinu.
Je li ovo ovdje smisla svatko, koliko je logično to radi?
To je vrsta brzo.
PUBLIKA: Možete li ići preko su s.stringss.strings [s.size] opet?
ANDI PENG: Naravno, tako što se s.size trenutno nam dati?
PUBLIKA: To je trenutna veličina.
ANDI PENG: Točno, tako da je Trenutni indeks da je naša veličina je u,
pa želimo staviti novi cijeli broj da želimo umetnuti u s.size.
Ima li to smisla?
Jer s.strings, sve što je naziv polja.
Sve to je pristup Niz unutar naše STRUCT,
pa ako želimo stavite n u tom indeksu,
mi samo može pristupiti koriste zagrade s.size.
Cool.
>> U redu, pop, to pseudokod sam za vas momci, ali sličan koncept.
Ima li to smisla?
Ako je veličina veća od nule, onda ste
znam da želiš da se nešto , jer ako se veličina nije
veći od nule, onda ste nemam ništa u dimnjaku.
>> Dakle, želite samo izvršiti ovaj kod, to može samo
pop, ako postoji nešto za pop.
Dakle, ako je veličina veća od 0, što minus veličina.
Dekrementirati smo veličinu, a zatim se vratiti ono što je u njoj, jer
iskakanje, želimo Pristup god je pohranjena
indeksa na vrhu dimnjaka.
Sve smisla?
Ako sam ti dečki napisati ovo, bi ti dečki biti u mogućnosti to napisati?
U redu, vi možete poigrati s njom.
Bez brige, ako ga ne dobijete.
Nemamo vremena za kodiranje to se i danas, jer imamo
ima puno tih struktura proći, ali u suštini
pseudokod, vrlo, vrlo slične gurnuti.
Samo slijedite duž logike.
Provjerite jeste li pristupate sve značajke vašeg STRUCT ispravno.
Da?
>> PUBLIKA: Hoće li ove slajdove i ova cijela stvar bude još danas-ish?
ANDI PENG: Uvijek, Yep.
Ja ću pokušati staviti ovo gore kao sat poslije.
Ja ću e-mail Davida, David će pokušati stavite ga kao sat nakon toga.
>> OK, onda smo preseliti u taj drugi Lijep struktura podataka se zove red.
Kako vi vidite tu, red, za Britance među nama,
sve je to je linija.
Dakle, suprotno onome što mislite stog je,
red je upravo ono što logično mislite da je.
To je održana po pravilima FIFO, koji je prvi u, prvi van.
Ako ste prvi jedna u nizu, ti si
prvi koji dolazi iz linije.
>> Dakle, ono što smo željeli nazvati to je dequeueing i enqueueing.
Ako želite dodati nešto našem redu, enqueue smo.
Ako želimo dequeue, ili se nešto dalje, dequeue smo.
>> Tako isto osjećaj da smo vrsta stvaranje fiksne veličine elemenata koje
može pohraniti sigurno stvari, ali možemo
promijeniti gdje smo stavljanje Parametri unutar njih
na temelju onoga što vrste Funkcionalnost želimo.
Dakle dimnjaka, htjeli smo posljednji jedan, N biti prvi van.
Red je želimo prva stvar u biti prva stvar van.
>> Tako je struct tipa definirati, kao što možete vidjeti,
to je malo drugačije od onoga što je snop
jer ne samo da moramo zadržati trag gdje je veličina trenutačno je,
želimo pratiti glave kao i gdje smo trenutno.
Zato mislim da je lakše ako sam izraditi ovaj gore.
Dakle, zamislimo da imamo red, pa recimo glava je upravo ovdje.
Čelnik linije, neka je samo reći da je to trenutno postoji,
i želimo umetnuti nešto u redu.
Idem zvati veličinu bitno je ista stvar kao i rep,
kraj gdje god je vaš red je.
Recimo samo veličina je upravo ovdje.
>> Pa kako se jedan feasibly ubacite nešto u redu?
Što Indeks želimo staviti gdje želimo umetnuti u.
Ako je ovo početak svoje red i to je kraj nje
ili veličina njega, u kojima radimo Želite dodati sljedeći objekt?
>> PUBLIKA: [nečujan]
ANDI PENG: Točno, želite dodati to ovisi o si ga napisao.
Ili je to prazan ili da je prazno.
Dakle, želite ga dodati vjerojatno ovdje jer ako veličina is--
ako su svi puni, što želite to dodati ovdje, zar ne?
>> I tako je to, a vrlo, vrlo jednostavno, ne sasvim uvijek točno
jer glavne razlike između red i stog
da je red može zapravo se manipulira
tako da su promjene glavu ovisno o tome gdje želite
početak vašeg znak za početak.
I kao rezultat toga, vaš rep također će se promijeniti.
I tako pogledati ovaj kod upravo sada.
Kao što ti dečki su također zamoljeni da pisati na kvizu, u red.
Možda ćemo razgovarati kroz zašto odgovor je bio ono što je bilo.
>> Nisam mogao sasvim stane tu liniju na jedan, ali u suštini to dio koda
bi trebao biti na jednoj liniji.
Provedite se kao 30 sekundi.
Pogledajte i uvjerite se zašto to je način na koji je to.
>> Vrlo, vrlo sličan struct, vrlo, vrlo Slična struktura kao prethodna
stog osim možda jedna linija koda.
I to jedan redak koda određuje funkcionalnost.
I to stvarno razlikuje red iz dimnjaka.
>> Svatko želi uzeti ubod na objašnjavanje zašto si
nema tu kompliciranu stvar ovdje?
Vidimo povratak naših prekrasan prijatelj modul.
Kao što ti dečki će uskoro doći prepoznati u programiranju,
gotovo bilo vam je potrebno nešto omotati oko bilo čega,
Modul će biti onako kako to učiniti.
Dakle, znajući da, bilo tko želite pokušati objašnjavajući da je linija koda?
Da, svi su odgovori prihvaćena i dobrodošla.
PUBLIKA: Jeste li u razgovoru sa mnom?
ANDI PENG: Da.
PUBLIKA: Oh, ne ispričavam.
ANDI PENG: OK, neka je hoda kroz ovaj kod.
Dakle, kada pokušavate dodati nešto na red,
u lijepom slučaju da je glava događa da se upravo ovdje, to je vrlo lako za nas
samo otići do kraja ubacite nešto, zar ne?
No, cijela točka red je da je glava zapravo može dinamički
mijenjati ovisno o tome gdje smo Želite početak naše q da bude,
i kao takav, rep također će se promijeniti.
>> I tako zamisliti da to nije bilo red, nego je to bio red.
Recimo glava je upravo ovdje.
Recimo da je naš red izgledao ovako.
Ako smo htjeli prebaciti u kojoj početak linije,
recimo mi pomaknuo glavu na taj način i veličina ovdje.
>> Sada želimo dodati nešto ovaj red, ali kako vi vidite,
to nije tako jednostavno kao samo dodaj ono što je nakon veličini
jer tada smo ponestane granica našeg stvarnog polja.
Gdje smo stvarno želite dodati ovdje.
To je ljepota red je da je za nas, vizualno
Izgleda da je linija ide ovako, a ako je pohranjena u strukture podataka,
oni daju kao kao ciklus.
To je vrsta omata na prednjem isti način
da linija može omotati oko ovisno o gdje god vas
želite početku retka biti.
I tako, ako uzmemo pogledajte ovdje, neka je
reći da smo htjeli stvoriti funkcija zove enqueue.
Željeli smo dodali int n u taj q.
Ako q.size q-- ćemo nazvati naše podatke structure-- ako naš queue.size ne
jednak kapacitet ili ako to je manje od kapaciteta,
q.strings je niz unutar naše q.
Idemo postaviti koja je jednaka q.heads,
što je upravo ovdje, plus q.size modul kapacitetom, koji
zamotajte nas natrag ovdje.
>> Dakle, u ovom primjeru, indeks glave je 1, zar ne?
Indeks veličine je 0, 1, 2, 3, 4.
Dakle, što možemo učiniti 1 plus 4 modul naš kapacitet koji je 5.
Što to nam dati?
Što je indeks koji dolazi iz toga?
>> PUBLIKA: 0.
>> ANDI PENG: 0, koji se događa da se upravo ovdje,
i tako želimo biti u mogućnosti umetnuti u ovdje.
I tako ta jednadžba ovdje vrste samo radi s bilo kojim brojevima
ovisno o tome gdje svoje Glava i tvoja veličina su.
Ako znate što oni stvari, znate
točno gdje želite umetnuti sve što je nakon čekanja.
Znači li to da smisla svima?
>> Znam kakve mozga teaser pogotovo jer to
došao je nakon kviza.
No, nadamo se svi Sada možete razumjeti
zašto je to rješenje ili ovaj Funkcija je način na koji je to.
Svatko malo nejasno o tome?
U REDU.
>> I tako sad, ako vas htjela dequeue, ovaj
gdje je naš voditelj će biti pomicanja jer ako bismo dequeue,
mi ne skinu kraj q.
Želimo da skinu glavu, zar ne?
Dakle, kao rezultat, glava će se promijeniti, i zato kada enqueue,
moraš pratiti gdje vam je glava i tvoj veličina
su da bi mogli umetnuti u ispravan položaj.
>> I tako kad dequeue, Također sam ga pseudokod van.
Slobodno ako želite pokušati kodiranja ovo.
Želite premjestiti glavu, zar ne?
Ako sam htjela dequeue, ja bi premjestiti nad glavom.
To će biti glava.
>> I naš sadašnji broj bi oduzimati jer više ne
imaju četiri elementa u nizu.
Imamo samo tri, a onda želimo da se vrati ono što je pohranjena u
glave, jer želimo da se to vrijednost se tako vrlo slična dimnjaka.
Samo ste uzimajući iz različitih mjesta,
i morate preraspodijeliti pokazivač na drugom mjestu kao rezultat.
Logično, svi slijediti?
Veliki.
>> U redu, pa ćemo razgovarati malo više u dubinu o povezanim popisima
jer će biti vrlo, vrlo vrijedan za vas u toku ovog tjedna je
psets.
Povezani popisi, kao što ste vi sjećam se, svi su oni
su čvorovi koji su čvorovi sigurno vrijednosti obje vrijednosti i pokazivač
koji su međusobno povezani tim upućuje.
I tako struct o tome mi stvaramo čvor ovdje smo
ima int n, što je bilo vrijednost u trgovini ili string n
ili što god želite ga nazivaju, char zvijezda nje.
Struct čvor zvijezda, što je pokazivač koje želite imati u svakom čvoru,
ti si idući u morati da Pokazivač točka prema sljedećoj.
Vi ćete imati glavu popisa koji je povezan
će ukazati na ostatak tako dalje i tako dalje vrijednosti
dok na kraju doći do kraja.
A ovaj zadnji čvor je samo će ne imati pokazivač.
To će ukazati na null, a to je kada
znate da ste hit kraj svog popisa povezan
kada je vaša posljednja pokazivač ne ukazuju na ništa.
>> Tako ćemo ići malo više u Dubina o tome kako jedan bi eventualno
Pretražite popis povezane.
Sjeti se što su neke od Nedostaci povezanim popisima
stihova niz vezi pretraživanja.
Niz možete binarno pretraživanje, ali zašto ne možete to učiniti na popisu povezane?
>> PUBLIKA: Zato što su svi povezani, ali ne znam točno gdje
[NEČUJAN].
>> ANDI PENG: Da, upravo tako zapamtiti da sjaj niz
bila je činjenica da smo imali memorija s izravnim pristupom, gdje
ako sam htjela vrijednost iz indeksa šest, samo sam mogao reći indeks šest,
daj mi tu vrijednost.
A to je zato jer su nizovi razvrstani u susjednom prostoru memorije
na jednom mjestu, dok je vrsta povezanih popisa
su nasumično mjestimice diljem, a jedini način na koji možete naći jedan
je kroz pokazivač koji vam govori adresu gdje da sljedeći čvor.
>> Pa kao rezultat toga, jedini način za pretraživanje kroz popis povezanih
linearna pretraživanja.
Jer ja ne znam točno gdje 12. Vrijednost na popisu povezan je,
Moram proći u cijelosti tog povezanog popisa jednom
jedan od glave do prvog čvora, na drugi čvor, do trećeg čvora,
sve na putu prema dolje dok sam napokon dobiti gdje da čvor tražim je.
I tako u tom smislu, traži na popisu povezan je uvijek n.
To je uvijek n.
To je uvijek u linearnom vremenu.
>> I tako je broj na koji implementiramo to, i to
je malo novo za vas dečki Budući da dečki nisu stvarno razgovarali o ili nikad
vidi naputke u tome kako pretraživanje pokazivače,
pa ćemo šetati Ovo je vrlo, vrlo sporo.
Dakle bool pretraživanje, pravo, neka je zamisliti da želimo
stvoriti funkciju pod nazivom traži da se vraća true
Ako ste pronašli vrijednost unutar povezani popis, a false inače.
Popis Čvor zvijezda je Trenutno samo pokazivač
na prvu stavku na popisu povezane.
int n vrijednost koju ste traži u tom popisu.
>> Dakle čvor zvijezda pokazivač jednaka popis.
To znači da smo postavljanje i stvaranje pokazivač
na taj prvi čvor unutar popisa.
Svatko sa mnom?
Dakle, ako smo ići ovamo, ja bi
inicijalizira pokazivač koji ukazuje na glava god da je popis.
>> I onda jednom kada se ovdje, dok pokazivač nije jednak null,
tako da je petlja u kojoj smo će biti naknadno poprijeko
ostatak našeg popisa, jer ono što događa kada pokazivač jednak null?
Znamo da smo have--
>> PUBLIKA: [nečujan]
>> ANDI PENG: Točno, tako da znamo da je smo došli do kraja popisa, zar ne?
Ako se vratite ovdje, svaki čvor Treba ukazujući na drugi čvor
i tako dalje i tako dalje sve dok ne dosegnete kraju
rep vašeg popisa povezani, koja ima pokazivač koji samo
ne pokazuje nigdje osim br.
I tako vi zapravo znate da Vaš popis je još uvijek tamo
dok pokazivač nije jednak null jer jednom je jednak null,
znate da postoji više nema stvari.
>> Tako da je petlja u kojoj smo će imati stvarnu potragu.
A ako pointer-- vidiš koja vrsta strelice funkcije tamo?
Dakle, ako pokazivač upućuje na n, ako je pokazivač na n jednak jednak n,
pa to znači da ako pokazivač da ste
traže na kraju svakog Čvor je zapravo jednaka vrijednosti
što tražite, a zatim Želite li vratiti istinito.
Tako je u osnovi, ako ste na čvoru koji ima vrijednost koju tražite,
znate da ste bili mogli uspješno traženje.
>> Inače, želite postaviti pokazivač na sljedeći čvor.
To je što to crta ovdje radi.
Pointer jednak pokazivač sljedeći.
Svatko vidi kako se to radi?
>> A u biti da ćeš samo proći cjelinu popisa,
resetiranja pokazivač svaki put do što na kraju pogodio kraj popisa.
I znate da ne postoje više čvorova za pretraživanje,
a onda možete return false jer znate da je, oh, dobro,
ako sam bio u mogućnosti to traženje kroz cijelosti popisa.
Ako se u ovom primjeru, ako sam htjela tražiti vrijednosti od 10,
i ja početi na glavi, a Tražim sve na putu prema dolje,
i na kraju sam dobio za to, što pokazivač koji ukazuje na null,
Znam da, sranje, valjda 10 nije u ovaj popis jer nisam mogao naći.
I ja sam na kraju liste.
I u tom slučaju znate Idem return false.
>> Neka to potopiti u za malo.
To će biti prilično važan za vaše pset.
Logika je vrlo jednostavno, možda sintaktički samo ga provoditi.
Vi želite učiniti sigurni da ste razumjeli.
Cool.
>> OK, pa kako ćemo biti umetanje čvorova, pravo,
u popisu, jer ne zaboravite što su ono od prednosti
vlasništvo povezana popis odnosu niz u smislu čuvanja?
>> PUBLIKA: To je dinamičan, tako da je lakše to--
>> ANDI PENG: Točno, tako da je dinamičan, što
znači da se može proširiti i smanjiti ovisno o potrebama korisnika.
I tako, u tom smislu, ne moramo trošiti nepotrebno memorije jer sam
ako ja ne znam koliko vrijednosti želim do trgovine, to nema smisla za mene
stvoriti niz, jer ako želim pohraniti 10 vrijednosti
i ja stvoriti niz 1000, to je puno izgubljenog pamćenja, dodijelili.
Zato želimo koristiti povezani Popis se može dinamički
promijeniti ili smanjiti našu veličinu.
>> I tako to čini umetanje malo više komplicirano.
Budući da ne možemo nasumično pristupiti elemente način na koji bismo od niza.
Ako želim umetnuti element u sedmom indeksa,
Upravo sam ga možete umetnuti u sedmom indeksa.
Na popisu povezani, to ne dosta raditi kao jednostavno,
pa ako smo htjeli umetnuti jedan ovdje u popisu povezane,
vizualno, to je vrlo lako vidjeti.
Mi samo želimo da ga ubacite pravo postoji, odmah na početku popisa,
odmah nakon glavu.
>> No, način na koji moramo preraspodijeliti se upućuje je malo savijen
ili, logično, to ima smisla, ali Želite li biti sigurni da ste ga
sasvim dolje, jer posljednja stvar koju želite
je preraspodijeliti pokazivač Način na koji radimo ovdje.
Ako vas dereference pokazivač od glave do 1,
zatim sve iznenada ostatak svog popisa povezan
izgubljen jer niste zapravo stvorio privremeni ništa.
To je ukazao na 2.
Ako preraspodijeliti pokazivač, a zatim Ostatak svog popisa potpuno je izgubljen.
Dakle, želite biti vrlo, vrlo oprezni ovdje
najprije dodijeliti Pokazivač iz bilo kojeg vas
želite umetnuti u gdje god što želite, a zatim vas
Možete dereference ostatak svog popisa.
>> Dakle, to vrijedi i za gdje god što pokušavate umetnuti u.
Ako želite umetnuti Na glava, ako želite odgovoriti ovdje,
Ako želite umetnuti u kraj, dobro, na kraju sam
Pretpostavljam da bi samo nemaju pokazivač, ali
želite biti sigurni da ne izgubiti ostatak svog popisa.
Vi uvijek želite biti sigurni Vaš novi čvor ukazuje
prema god želite umetnuti u,
a zatim možete dodati ulančavanje dalje.
Svatko jasno?
>> To će biti jedan od stvarnih problema.
Jedan od najvažnijih glavnih pitanja ti si idući u imati na svom pset
je da ćeš pokušati stvoriti je povezani popis i stavite stvari
ali onda samo izgubiti ostatak svog popisa povezane.
I vi ćete biti kao ja ne znam zašto se to događa?
I to je bol proći i traži sve svoje pokazivače.
>> A ja vam jamčim ovaj pset, pisanje i crtanje te čvorova iz
će biti vrlo, vrlo korisno.
Tako da u potpunosti možete pratiti gdje sve svoje pokazivače su,
što se događa u krivu, gdje su svi vaši čvorovi,
ono što trebate učiniti za pristup ili umetnuti ili izbrisati ili bilo koji od njih.
Svatko dobro s tim?
Cool.
>> Dakle, ako smo htjeli pogledati šifru?
Oh, ja ne znam da li smo možete vidjeti the-- redu, tako da
na vrhu sve što je funkcija nazvana umetak gdje želimo
umetnuti int n u popisu povezane.
Idemo u šetnju kroz ovo.
To je puno koda, puno novih sintakse.
Mi ćemo biti u redu.
>> Tako se na vrhu, kad god želimo stvoriti nešto
Što trebamo učiniti, osobito ako vas žele da neće biti pohranjeni na stogu
ali u hrpi?
Idemo na malloc, zar ne?
Tako ćemo stvoriti pokazivač.
Čvor, pokazivač, novi jednaki malloc veličine čvora
jer želimo da se čvor biti stvoren.
Želimo količinu memorije koja čvor zauzima
se dodjeljuju za Stvaranje novog čvora.
>> A onda ćemo provjeriti je li nova jednaki jednaka nuli.
Sjećaš se što smo rekli?
Što god vam malloc, što moraš uvijek raditi?
Uvijek morate provjeriti da se vidi da li ili ne to je null.
>> Na primjer, ako vaš operativni Sustav je potpuno pun,
ako je nema više memorije na sve i pokušate malloc,
to bi se vratiti null za vas.
I tako, ako pokušate ga koristiti kada je pokazujući na null,
ti nećeš moći pristupiti te podatke.
I tako, kao što smo htjeli napraviti jeste da kad god ste mallocing,
ti si uvijek provjeru je li da memorija tebi je null.
A ako nije, onda možemo pomaknuti na sa ostatkom našeg koda.
>> Tako ćemo inicijalizirati novi čvor.
Idemo napraviti novi je n = n.
A onda ćemo napraviti postaviti novi pokazivač na novo
na nulu, jer sada mi ne Želite ništa za to ukazati.
Mi nemamo pojma gdje to će vas,
a onda, ako želimo umetnite ga u glavu,
onda možemo dodijeliti pokazivač na glavu.
Da li su svi slijede logiku gdje to događa?
>> Sve što radite stvara novi čvor, postavljanje pokazivača na nulu,
a zatim prenamjene je u glavu ako mi
znate što želite umetnuti u glavi.
A onda je glava ide usmjerite prema tom novom čvor.
Svatko u redu s tim?
>> Dakle, to je proces u dva koraka.
Moraš prvo Dodijeli sve što stvarate.
Postavite pokazivač na taj referenca, a onda vam
Možete vrsta dereference prvi pokazivač
i usmjerite prema novom čvor.
Gdje god ga želite umetnuti, da logika ide vrijede.
>> To je vrsta kao dodjeljivanje privremene varijable.
Sjeti se, imaš kako bi bili sigurni da vas
nemojte izgubiti trag ako ste zamjene.
Vi želite biti sigurni da imate privremena varijabla koja vrsta čuva
Staza gdje tu stvar se pohranjuje tako da
ne izgubiti bilo koju vrijednost u tijeku poput messing oko s njom.
>> U redu, tako da kod će biti ovdje.
Vi pogledati nakon dijelu.
To će biti tamo.
>> Pa valjda kako se to razlikuje ako smo htjeli
umetnuti u sredini ili na kraju?
Se bilo tko imati ideju o tome što je pseudokod kao logičan referenca
da bi se, ako smo htjeli umetnite ga u sredini?
Dakle, ako smo htjeli da ga ubacite Na Glava, sve što radimo je stvoriti novi čvor.
Postavili smo pokazivač toga novi čvor na bilo glave,
a zatim smo postavili glavu na novi čvor, zar ne?
Ako smo htjeli da ga ubacite u sredini popisa, što bi mi moramo učiniti?
>> PUBLIKA: on će i dalje biti sličan proces
poput dodjele pokazivač i onda dodjeljivanje da pokazivač,
ali će morati pronaći tamo.
>> ANDI PENG: Točno, tako da je točno isti proces, osim tebe
moraju pronaći gdje točno Želite da novi pokazivač ići u,
pa ako želim umetnuti u sredina povezani list-- redu,
recimo da je naš popis povezani.
Ako želite umetnuti ovdje, ćemo stvoriti novi čvor.
Idemo malloc.
Ćemo stvoriti novi čvor.
Idemo dodijeliti pokazivač ovog čvora ovdje.
>> No, problem koji se razlikuje odakle je glava
je da smo točno znali gdje je glava.
Bilo je to pravo na prvi, zar ne?
No, ovdje moramo pratiti gdje smo ubacivanja u.
Ako se umetanjem naš čvor ovdje imamo
kako bi bili sigurni da je jedan prethodni ovom čvoru
je onaj koji reassigns pokazivač.
Pa onda morate vrsta pratiti dvije stvari.
Ako vam pratiti gdje se to čvor trenutno umetanja.
Također morate pratiti gdje prethodna čvor koji gledate
je također bio tamo.
Svatko dobro s tim?
U REDU.
>> Kako o umetanja u kraj?
Ako sam htjela dodati here-- ako sam htjela dodati novi čvor na kraj popisa,
kako bih mogao ići oko radiš to?
PUBLIKA: Pa trenutno je Posljednji je ukazao na nulu.
ANDI PENG: Da.
Točno, tako da je ovo jedan Trenutno je istakao da zna,
pa mislim, u tom smislu, to je vrlo lako dodati na kraj popisa.
Sve što trebate učiniti je postaviti jednak null a onda bum.
Upravo tamo, vrlo jednostavno.
Vrlo jednostavno.
>> Vrlo sličan glavu, ali logično vas
želite biti sigurni da su koraci što se prema radili bilo što od toga,
ste sljedeće zajedno.
To je vrlo lako, u sredini vašeg koda, dobiti uhvaćen na,
oh, imam toliko naputke.
Ne znam gdje sve ukazuje na.
Ne znam ni što čvor sam na.
Što se događa?
>> Opustite se, smiri se, duboko udahnite.
Nacrtaj svoj popis povezane.
Ako kažem, ja znam gdje je točno Moram umetnuti to u
i znam točno kako preraspodijeliti moj pokazivače, mnogo, mnogo lakše zamisliti
out-- mnogo, mnogo lakše ne izgubiti u bugova vašeg koda.
Svatko u redu s tim?
U REDU.
>> Pa valjda koncept koji nemamo stvarno razgovarali o do sada,
i ja ti valjda vjerojatno neće naići na mnogo yet--
to je vrsta naprednog concept-- je da mi zapravo imaju podatke
Struktura naziva popisa za dvostruko povezani.
Dakle, kao što vi vidite, sve što radite je da stvarate
stvarna vrijednost, dodatni pokazivač na svaki od naših čvorova
koja također ukazuje na prethodni čvor.
Dakle, ne samo da mi imamo čvorovi upućuju na sljedeću.
Oni također ukazuju na prethodni.
Idem ignorirati ta dva sada.
>> Pa onda imate lanac koji može kretati u oba smjera,
a onda je malo lakše logički slijediti zajedno.
Kao i ovdje, umjesto praćenje, oh,
moraju znati da je ovaj čvor onaj koji moram preraspodijeliti,
Ja samo mogu ići ovdje i Samo povucite prethodni.
Tada znam točno gdje da je, a onda vam
ne moraju proći cjelokupnost popisa povezane.
To je malo lakše.
>> Ali kao takva, imate dvostruko iznos pokazivača,
to je dvostruka količina memorije.
To je puno naputke za praćenje.
To je malo složeniji, ali to je malo više user friendly, ovisno
na ono što pokušavate postići.
>> Dakle, ova vrsta podataka Struktura totalno postoji,
a struktura je vrlo, vrlo Jednostavan osim sve što imate je,
umjesto samo pokazivač na sljedeći, imate i pokazivač na prethodni.
To je sve što je razlika je.
Svatko dobro s tim?
Cool.
>> U redu, sada sam stvarno provesti vjerojatno
kao i 15 do 20 minuta ili skupno ostatka vremena u dijelu
govori o hash tablica.
Koliko od vas Pročitao pset5 spec?
Dobro, dobro.
To je veći od 50% normalno.
Uredu je.
>> Dakle, kao što će ti dečki vide, ti si izazov u pset5
će provesti rječnik gdje se učitati preko 140.000 riječi
da ćemo vam dati i provjere pravopisa je protiv svih teksta.
Mi ćemo vam dati slučajni komada književnosti.
Mi ćemo vam dati Odiseji.
Mi ćemo vam dati Ilijadi.
Mi ćemo vam dati Austin Powers.
>> I vaš izazov bit će da provjere pravopisa
svaka riječ u svemu od onih rječnika
u biti s našim provjeru pravopisa.
I tako postoji nekoliko dijelova stvaranja ovog pset,
Prvi želite biti mogućnosti da se zapravo učitavanje
sve riječi u svoj rječnik, a onda vam
želite biti u mogućnosti provjeru pravopisa sve njih.
I tako kao takva, ti si idući u zahtijevaju data struktura koja može učiniti brzo
i učinkovito i dinamično.
>> Pa valjda najlakše način da to učinite, te
vjerojatno stvoriti niz, zar ne?
Najlakši način za pohranu je vas može stvoriti niz 140.000 riječi
i samo ih stavite tamo i zatim ih poprijeko po binarnom pretraživanje
ili selekcija ili not-- žao da je razvrstavanje.
Možete ih sortirati, a zatim ih poprijeko binarnim pretraživanje ili jednostavno linearno pretraživanje
i samo završne riječi, no to ima veliku količinu memorije,
i to ne jako učinkovit.
>> I tako ćemo početi govorimo o načinima izrade
naša trčanje vrijeme učinkovitije.
A naš cilj je dobiti konstanta vrijeme u kojem
to je gotovo kao polja, gdje imate trenutačan pristup.
Da sam htio tražiti bilo što, Želim biti u mogućnosti jednostavno,
bum, pronašli ga baš i izvucite ga.
I tako je struktura u kojoj ćemo postati vrlo blizu
da bi mogli pristupiti konstanta Vrijeme, taj sveti gral
u programiranju konstanta Vrijeme se naziva hash tablicu.
I tako David ranije spomenuo [Nečujan] malo u predavanju,
ali ćemo stvarno zaronite duboko u ovom tjednu
na komad koji je u vezi kako hash tablicu radi.
>> Dakle, na način da se rasprsne stol djela, primjerice,
ako sam htjela spremiti hrpa riječima, hrpa riječi na engleskom jeziku,
Ja teoretski mogao staviti banane, jabuke, kivi, mango, par,
i dinja sve na samo polje.
Svi su mogli uklopiti i biti pronaći.
Bilo bi vrsta boli pretraživanje i pristup,
ali lakši način za to je da možemo stvoriti zapravo struktura
naziva hash tablicu gdje smo razmotrili.
Mi pokrenuti sve naše tipke kroz hash funkcija, jednadžba,
da ih sve pretvara u nekakva vrijednost
kako onda možemo pohraniti na u biti niz povezanih popisa.
>> I tako ovdje, ako smo htjeli pohraniti engleske riječi,
smo mogli potencijalno jednostavno, ja ne Znaš, uključiti sve prva slova
u nekakvu nizu.
I tako, na primjer, ako želim A do sinonim apple--
ili s indeksom od 0, i B sinonim 1,
možemo imati 26 unose samo da može pohraniti
sva slova abeceda da ćemo početi s.
A onda možemo imati Apple na indeks 0.
Možemo imati bananu na indeks 1, dinja na indeks 2,
i tako dalje i tako dalje.
I tako, ako sam htjela za pretraživanje moj hash tablicu i pristup jabuka,
Znam Apple počinje s A klase, i znam točno
da to mora biti i ljestve stol u indeksu 0 zato
funkcije prethodno dodijeljen.
>> Pa ne znam, mi smo user program u kojem
ćete biti optužen arbitrarily-- ne proizvoljno,
pokušaj zamišljeno mislim dobrih jednadžbi
se moći širiti iz sve svoje vrijednosti
na način da se lako može pristupiti što kasnije s poput jednadžbe
da tebe, sebe, znate.
Dakle, u tom smislu, ako sam htjela ići mango, znam, oh, to počinje s m.
To mora biti u indeksu od 12 godina.
Ja ne moram tražiti kroz sve.
Znam exactly-- samo sam mogao ići na indeks 12 i povucite da van.
>> Svatko jasno kako Funkcija hash tablicu djela?
To je vrsta samo složenije polje.
To je sve što je.
U REDU.
>> Dakle, mislim da naletimo ovo pitanje o tome što
dogoditi ako imate više stvari da vam dati isti indeks?
Tako kažu naše djelovanje, a sve to učinio je poduzeti prvi pismo
i da se uključite u Dotični 0 do 25 indeks.
To je sasvim u redu, ako imate samo jedan od svakog.
Ali drugi počnete ima više, ti si
će imati ono što se zove sudara.
>> Dakle, ako ja pokušati umetnuti zakopati u hash Tablica koja već ima bananu na njega,
što će se dogoditi kada pokušate umetnuti to?
Loše stvari jer banane već postoji u indeksu
da želite ga pohraniti u.
Berry vrsta je kao, ah, što da radim?
Ne znam gdje da ide.
Kako riješiti ovo?
>> I tako vi vrsta volje vidjet ćemo učiniti škakljivo
Gdje možemo vrsta zapravo stvoriti povezani popis u našim poljima.
I tako je najlakše razmišljati o tome,
Sve hash tablica je niz povezanih liste.
I tako, u tom smislu, imate ovaj lijepi niz pokazivača,
i onda svaki pokazivač u da se vrijednost, u tom indeksu,
zapravo može ukazati na druge stvari.
I tako imate sve ove odvojene lanci dolaze izvan jedan veliki niz.
>> I tako ovdje, ako sam htjela umetnuti bobica,
Znam, u redu, ja idem za unos je kroz moje hash funkcije.
Idem završiti s indeksom 1, a onda ću biti u mogućnosti da imaju
samo manji podskup toga div rječnik 140.000-riječ.
A onda ja samo mogu gledati kroz 1/26 toga.
>> I tako onda sam jednostavno možete umetnuti bobica bilo prije ili poslije banana
u ovom slučaju?
Nakon, zar ne?
I tako idete želite umetnite ovaj čvor nakon banani,
pa ti si idući umetnuti na repu tog vezanog popisa.
Idem se vratiti ovaj prethodni slajd,
tako da vi možete vidjeti kako hash funkcija radi.
>> Dakle hash funkcija je ova jednadžba da radite kakve vašeg unosa
do dobiti sve što indeksa Želite li ga dodijeliti prema.
I tako, u ovom primjeru, sve što smo htjeli učiniti je uzeti prvo pismo,
da se uključite u indeks, onda smo može pohraniti da u našem hash funkcije.
Sve što radite ovdje smo pretvaranje prvo slovo.
Dakle keykey [0] je samo prvo slovo bez obzira na niz koju smo ima,
mi prolaze.
Mi smo pretvaranja da se gornji i mi smo oduzimanjem od verzalnog A,
tako da sve što radi daje nam broj
u kojem možemo hash naše vrijednosti na.
>> A onda ćemo povratak hash modul čvrstoće veličine.
Budite vrlo, vrlo oprezni jer, teoretski, ovdje
Vaš hash vrijednost može biti beskonačan.
To može samo ići na i na i na.
To bi mogao biti neki jako, stvarno velika vrijednost,
ali zbog vaše hash tablicu koja ste stvorili ima samo 26 indeksa,
želite biti sigurni da vaš modulusing tako da
ne run-- to isto stvar kao queue--
tako da ne pokrenuti off Dno vašeg hash funkcije.
>> Želite zamotati natrag oko na isti način u [nečujan] kada
ste imali kao vrlo, vrlo velika slova, što
nije želio da se samo pokrenuti off kraj.
Ista stvar ovdje, želite da biste bili sigurni ne trude kraj omatanje
oko vrha stola.
Dakle, ovo je samo vrlo Jednostavan hash funkcija.
Sve što je učinio je poduzeti prvi pismo bilo naše ulaz je
i da se uključite u indeksu koji možemo staviti u našem hash tablicu.
>> Da, pa kao što sam rekao prije, način na koji smo riješili sudara
u našem hash su tablice s, Ono što mi zovemo, ulančavanje.
Dakle, ako pokušate umetnuti višestruki Riječi koje počinju s iste stvari,
ti si idući u imati jedan hash vrijednosti.
Avokado i jabuke, ako ste pokrenite ga kroz naše hash funkcija,
će vam dati Isti broj, broj 0.
I tako je način na koji smo riješili da je da zapravo možemo vrsta ih povezati
zajedno preko povezanih liste.
>> I tako u tom smislu, vi možete vidjeti kakav
kako strukture podataka koje smo postavljanje prethodno
poput grožđica povezani popis vrsta od mogu udružiti u jedan.
A onda možete stvoriti daleko učinkovitije strukture podataka
koja se može nositi veće količine podataka, koja dinamički promijeniti veličinu ovisno
o Vašim potrebama.
Svatko jasno?
Svatko vrsta jasan na ono što se događa ovdje?
>> Ako sam htjela insert-- što je voće koje počinje s, ne znam,
B, osim bobica, banane.
>> PUBLIKA: BlackBerry.
>> ANDI PENG: BlackBerry, BlackBerry.
Gdje kupina ide ovdje?
Pa, mi zapravo nisu razvrstani to još, ali teoretski
ako smo htjeli da se ovaj abecednim redom,
gdje bi BLACKBERRY ići?
>> PUBLIKA: [nečujan]
>> ANDI PENG: Točno, nakon što se ovdje, zar ne?
No, budući da je vrlo teško reorder-- Mislim da je do vas dečki.
Vi možete u potpunosti provesti što god želite.
Učinkovitiji način za to možda
bi se razvrstati vaš povezani popis u abecednom redu,
pa kad si umetanja stvari, što želite
biti sigurni da ih stavite u abecednom redu
pa onda kada ste pokušavajući ih traži,
ne morate proći sve.
Znaš točno gdje je, i to je lakše.
>> Ali, ako ste vrsta ima stvari mjestimice slučajno,
i dalje ćeš imati to proći ionako.
I tako, ako sam htjela samo umetnite kupina ovdje
i ja sam htjela za pretragu da, znam, oh, kupina
mora započeti s indeksom 1, pa sam znam trenutačno samo traži na 1.
I onda ja mogu nekako prošli popis povezan
dok sam se na BlackBerry, i then-- da?
>> PUBLIKA: Ako pokušavate create-- Mislim da kao što je to vrlo jednostavna hash
funkcija.
A ako smo htjeli napraviti višestruke razine da kao,
U redu, želimo odvojiti u kao i svi znakovi abecede
a onda opet voljeti drugu set od abecednom slova unutar koje,
smo stavljajući se kao hash Tablica u hash tablici,
ili poput funkcije u funkciju?
Ili je that--
>> ANDI PENG: Pa vašem hash function-- svoj hash tablicu
može biti tako velika kao što želite da.
Dakle, u tom smislu, mislio sam to je vrlo jednostavno, vrlo
jednostavno mi se samo vrsta temelji na slova prve riječi.
I tako postoji samo 26 opcija.
Ja mogu samo dobiti 26 opcija 0 do 25, jer oni mogu samo
početi od A do Z. Ali ako ste željeli dodati, možda, više složenosti
ili brži trčanje vremena da svoje hash tablicu, apsolutno
mogu učiniti sve i svašta.
Možete napraviti svoj vlastiti jednadžba koja vam daje
više distribucija u svom Riječi, onda kada se traži,
to će biti brže.
>> To je totalno do vas dečki kako želite provesti to.
Razmislite o tome kako je samo kante.
Da sam htio imati 26 kante, idem
sortiranje stvari u te kante.
Ali ja ću imati hrpu stvari u svakoj ćeliji,
pa ako želite to učiniti brže i učinkovitije,
neka mi se sto kante.
>> Ali onda morate shvatiti način za sortiranje stvari, tako da su
u pravilnom kantu oni bi trebali biti u.
Ali onda zapravo kada želite pogledati tu kantu,
to je puno brže, jer postoji manje stvari u svakoj ćeliji.
I tako, da, to je zapravo trik za vas dečki u pset5
je da ćete biti izazov da samo stvoriti
bilo je najučinkovitiji Funkcija možete sjetiti da se
mogli pohraniti i provjeriti te vrijednosti.
>> Totalno do vas dečki Međutim želite to učiniti,
ali to je stvarno dobra stvar.
To je vrsta logike koju želim početi razmišljati o
je, dobro, zašto ne bih napraviti još kante.
I onda moram tražiti manje stvari, a onda možda sam
imaju različite hash funkcije.
>> Da, postoji mnogo načina za to pset, neki su brži od drugih.
Ja sam totalno ću samo vidjeti kako brzo je bio najbrži vi ćete
biti u mogućnosti da biste dobili vaše funkcionira na posao.
U redu, svi dobro na ulančavanje i hash tablice?
To je zapravo kao vrlo jednostavan koncept ako mislite o tome.
Sve to je odvajanje bilo Vaši ulaza u kante,
ih sortiranje, a zatim u potrazi navodi da je povezana s.
>> Cool.
U redu, sada imamo različite vrste strukture podataka koji se zove stablo.
Idemo dalje i pričati o pokušaja koji su izrazito različiti,
ali u istoj kategoriji.
U suštini, sve drvo je umjesto organiziranja podataka na linearni način
da hash tablicu vas does-- Znate, to je dobio vrh i dno
i onda nekako povezati off it-- u Stablo ima top koji nazoveš korijen,
a onda je sve lišće oko njega.
>> I tako sve što imamo ovdje je samo vrh čvor
koji ukazuje na druge čvorove, koji ukazuje na više čvorova, i tako dalje i tako dalje.
I tako ste upravo cijepanje grane.
To je samo drugačiji način organiziranja podataka, i zato što je to stablo poziv,
vi just-- to je samo po uzoru na izgleda kao drvo.
Zato smo ga nazvati stabala.
>> Hash tablicu izgleda kao stol.
Stablo samo izgleda kao drvo.
Sve je to je zasebna način organiziranja čvorova
ovisno o tome što su vaše potrebe.
>> Dakle, imate korijen i onda imate lišće.
Način na koji možemo posebno mislim o tome je binarno stablo,
binarno stablo je samo specifična vrsta drveta
gdje svaki čvor samo točke da, na max, druga dva čvora.
I tako ovdje imate različita simetrija u vašem stablo
koji olakšava vrsta izgleda na ono vrijednosti ste jer onda
ima uvijek lijevo ili desno.
Tu je nikad kao lijevoj trećini od lijevi ili četvrti s lijeva.
To je samo imate lijevo i pravo i možete tražiti bilo koji od ta dva.
A zašto je to korisno?
Način na koji je to korisno je ako ste u potrazi
pretraživati ​​vrijednosti, zar ne?
Umjesto provedbe binarni traži u polje pogreške,
ako ste htjeli biti u mogućnosti da ubacite čvorova i oduzeti čvorova po volji i
sačuvati pretraživanje Kapaciteti binarnog pretraživanja.
Dakle, na ovaj način, mi smo vrsta tricking-- sjećam se kad smo
rekao povezani popisi ne mogu binarno pretraživanje?
Mi smo vrsta stvarajući strukturu podataka da imate to u radi.
>> I zato povezani popisi su linearni, oni povezuju samo jedan za drugim.
Možemo vrsta ima različita vrsta pokazivača
koji ukazuju na različitim čvorovima koji nam mogu pomoći u traženju.
I tako ovdje, ako sam htjela imaju pretraživanje po binarnom stablu,
Znam da moje sredine, ako 55.
Samo ću napraviti da kao moj sredini, kao moj korijen,
a onda ću imati Vrijednosti spin off od njega.
>> Dakle ovdje, ako ću tražiti vrijednost od 66, mogu započeti u 55.
To je 66 veći od 55?
Da je to tako znam da mus pretragu ja n pravo pokazivač ovog stabla.
Idem na 77.
Dobro je manji od 66 ili više od 77?
To je manje nego, tako da znate, oh, to mora biti lijevo čvor.
>> I tako ovdje smo vrsta očuvanja sve velike stvari o polja,
pa kao dinamičke promjene veličine objekata, što
mogućnosti za umetanje i brisanje po volji, bez brige o fiksnoj
Količina prostora.
Još uvijek čuvaju sve one čudesa
a također je u mogućnosti sačuvati prijavite i traži vrijeme binarnog pretraživanja
da mi je samo prije mogućnosti da biste dobili izraz.
>> Cool struktura podataka, vrsta Kompleks provesti, čvor.
Kao što možete vidjeti, sve to je struct čvora
je da imate lijevo i pravo pokazivač.
To je sve što je.
Dakle, umjesto da samo ima x ili prethodni.
Imate lijevu ili pravo, a zatim što vrste ih može povezati zajedno
No tako odlučite.
>> U redu, mi zapravo ide samo potrajati nekoliko minuta.
Tako ćemo se vratiti ovdje.
Kao što sam rekao ranije, Nekako sam objasnio
logika iza kako smo će tražiti kroz to.
Idemo pokušati pseudocoding ovo vidjeti
ako možemo vrsta vrijedi Ista logika binarnog pretraživanja
na drugu vrstu strukture podataka.
Ako vi želite uzeti kao par minuta da samo razmišljam o tome.
U REDU.
U redu, ja ću zapravo samo dati the-- ne,
ćemo razgovarati o pseudokod prvi.
Tako se bilo tko želite dati ubosti na ono što
prva stvar koju želite učiniti kada ste početku potrazi je?
Ako ste se u potrazi za vrijednost od 66, što je
prva stvar koju želite učiniti ako želimo binarnog pretraživanja ovo drvo?
>> PUBLIKA: Želite izgleda dobro i gledati lijevo i vidjet [nečujan]
veći broj.
>> ANDI PENG: Da, točno.
Dakle, ti ćeš gledati na korijenu.
Postoji mnogo načina na koje možete nazvati da, tvoj roditelj čvor ljudi kažu.
Volim reći, jer korijen to je kao korijen stabla.
Ideš pogledati vaša root čvor, a vi ste
idući u vidjeti je 66 veći od ili manje od 55.
A ako je veći od, dobro, to je veći od, na kojem želimo gledati?
Gdje želimo tražiti, zar ne?
Želimo za pretraživanje Pravo polovica tog stabla.
>> Tako smo, jednostavno, A pokazivač koji pokazuje na desno.
I tako onda možemo postaviti naš novi korijen se 77.
Mi samo možemo ići gdje god pokazivač pokazuje.
Pa, oh, ovdje mi počinjemo na 77, a možemo samo
to rekurzivno opet i opet.
Na ovaj način, možete vrsta od imati funkciju.
Imate način traži da ti mogu samo ponoviti iznova i iznova i iznova,
ovisno o tome gdje želite pogledati dok na kraju dobiti na vrijednosti
da ste u potrazi za.
Ima smisla?
>> Ja sam o to pokazivanje stvarni broj, a to je puno koda.
Nema potrebe da se paliti.
Razgovarat ćemo kroz njega.
>> Zapravo, ne.
To je bio samo pseudokod.
U redu, to je bio samo pseudokod, što je malo složen,
ali to je potpuno u redu.
Svatko slijedi ovdje zajedno?
Ako je korijen je null, povratak netočno, jer to znači
vi ne morate ništa tamo.
>> Ako korijen n vrijednost, pa ako je to se događa da se jedan gledaš,
onda ćeš se vratiti istina jer vi znate da ga pronašli.
No, ako je vrijednost manja od korijena n, ti si
idući za pretraživanje lijevu dijete ili lijevi list,
što god želite nazvati.
A ako je vrijednost veća od korijena, idete tražiti pravo drvo,
onda samo pokrenuti funkciju kroz potragu opet.
>> I ako je korijen null, da je znači što ste došli do kraja?
To znači da nemaju više više listova za pretraživanje,
onda znate, oh, Pretpostavljam da nije ovdje
jer nakon što sam pogledao kroz cijela stvar i nije ovdje,
to jednostavno ne može biti ovdje.
>> Znači li to da smisla svima?
Dakle, to je kao binarnog pretraživanja konzerviranje sposobnosti povezanih popisa.
Cool, pa drugi tip Strukture podataka što dečki
možete pokušati provedbu na svom pset, imate samo odabrati jedan način.
No, možda alternativna metoda za hash tablicu je ono što mi nazivamo Trie.
>> Sve što je Trie je specifična vrsta drveta koje
ima vrijednosti koje idu na drugim vrijednostima.
Dakle, umjesto da binarni stablo u smislu da je samo jedan
što može ukazati na dva, možete imati jedna stvar točka za mnoge, mnoge stvari.
Vi zapravo imate nizove unutar koje pohranjujete
upućuje da ukazuju na druge polja.
>> Tako je čvor kako smo će definirati Trie
je želimo imati Boolean, c riječ, zar ne?
Dakle, čvor je Booleova kao istinite ili lažne,
prije svega na čelu to polje, je li to riječ?
Drugo, želite imati pokazivače na ono što od njih su.
Malo kompleks, malo apstraktno, ali Ja ću objasniti što to sve znači.
>> Dakle, ovdje, na vrhu, ako vas ima niz proglasio je već,
čvor u kojoj imate Boolean vrijednost spremljena na prednjem
koji kaže da je to riječ?
Nije li to riječ?
I onda imate ostatak svog polja koja
zapravo pohranjuje sve mogućnosti što bi to moglo biti.
Tako je, na primjer, kao što je na vrhu imate
prva stvar koja govori istina ili lažna, da ili ne, to je riječ.
>> I onda imate 0 do 26. slova koje možete pohraniti.
Ako sam htjela potražiti ovdje za šišmiša, idem na vrh
i ja tražiti B. nađem B u mom niz, pa znam, u redu je B riječ?
B nije riječ, pa time i Moram nastaviti pretraživanje.
Idem iz B, a sam pogled na Pokazivač da B upućuje
i vidim još niz podataka, ista struktura koje smo imali prije.
>> I here-- oh, sljedeći pismo u [nečujan] je A.
Tako gledamo u tom nizu.
Nalazimo osmi vrijednosti, a onda gledamo vidjeti, oh,
hej, je da je riječ je B-A riječ?
Nije riječ.
Moramo se držati obličje.
>> I tako onda gledamo gdje kazaljka A točaka,
a to ukazuje na neki drugi način u što imamo više vrijednost pohranjena.
I na kraju, možemo doći do B-A-T, što je riječ.
I tako sljedeći put pogledate, idete
da se taj ček od, da, ovo Booleova funkcija je istina.
I tako, u smislu da smo ljubazni vlasništvo stablo s polja.
>> Pa onda možete vrsta pretraživati ​​prema dolje.
Umjesto raspršivanja funkcije i dodjeljivanje vrijednosti od povezanog popisa,
možete jednostavno implementirati Trie koji pretražuje downwords.
Stvarno, stvarno komplicirano stvari.
Nije lako razmišljati jer sam se kao pljuvanje toliko strukture podataka iz
na vas, ali ne sve vrste razumjeti kako logika ovo radi?
>> OK super.
Tako B-A-T, te ideš tražiti.
Sljedeći put kad idete vidjeti, oh, hej, to je istina,
Tako znam da to mora biti riječ.
>> Ista stvar za zoološki vrt.
Dakle ovdje je stvar sada, ako smo htio tražiti zoološkom vrtu, upravo sada,
Trenutno zoo nije Riječ u našem rječniku
jer, kao što vi vidite, Prvo mjesto koje imamo Boolean
povratak istina je na kraju zoom.
Imamo Z-O-O-M.
>> I tako ovdje, ne zapravo imaju riječ, zoološki vrt, u našem rječniku
jer ovaj potvrdni okvir nije označen.
Tako se računalo ne znam da zoološki vrt je riječ
jer način na koji smo spremio, samo zoom ovdje
zapravo ima Boolean vrijednost koji je bio uključen istina.
Dakle, ako želimo umetnuti Riječ, zoološki vrt, u naš rječnik,
kako bi smo ići oko radiš to?
Što moramo učiniti kako bi bili sigurni da naš Računalo zna da je Z-O-O je riječ
a ne prva riječ Z-O-O-M?
>> PUBLIKA: [nečujan]
>> ANDI PENG: Točno, mi želite biti sigurni da je to
ovdje, da Boolean vrijednost provjeriti off da je to istina.
Z-O-O, tada ćemo provjeriti da je, tako da točno znamo, hej, zoološki vrt je riječ.
Idem reći Računalo koje je riječ, tako
je li računalo provjerava, ona zna da zoološki vrt je riječ.
>> Zato ne zaboravite sve ove podatke strukture, to je vrlo lako za nas
reći, oh, šišmiš je riječ.
Zoo je riječ.
Zoom je riječ.
Ali kad ste ga zgrada, računalo nema pojma.
>> Dakle, morate ga točno reći U kojem trenutku je to riječ?
U kojem trenutku je da nije riječ?
I na kojoj točki ne ja morati tražiti stvari,
i na kojoj točki trebam ići dalje?
Svatko jasno kako?
Cool.
>> I tako onda dolazi problem kako bi mi
ići oko umetanja nešto to je zapravo ne postoji?
Pa recimo samo želimo umetnuti riječ, kada, u našu Trie.
Kao što dečki mogu vidjeti kao trenutno sve što imamo je B-A-T,
i ovaj novi struktura podataka Postoji imao pivo koje
ukazao na nulu, jer pretpostavljamo da, oh, nema riječi nakon B-A-T,
zašto nam je potrebna da bi ima stvari nakon toga T.
>> No, problem nastaje ako vam se Želite imati riječ koja dolazi nakon
T-a.
Ako imate kadu, ti si ide žele H pravo.
I tako je način na koji ćemo učiniti da je ćemo stvoriti zaseban čvor.
Nećemo dodijeliti bilo koji iznos memorije za ovaj novi niz,
i mi ćemo preraspodijeliti naputke.
>> Idemo dodijeliti H, Prije svega, to null,
ćemo riješiti.
Mi ćemo imati je H točke prema dolje.
Ako vidimo H, želimo ga ići na neko drugo mjesto.
>> Ovdje, možemo onda prekrižite da.
Ako udario H nakon T, oh, onda znamo da je to riječ.
Logički će vratiti istinito.
Svatko jasno kako se to dogodilo?
U REDU.
>> Pa u biti, sve ove strukture podataka
da smo otišli preko danas, imam otišao preko njih jako, jako brzo
i ne previše detalj, a to je u redu.
Jednom kada počnete petljaju s njim, vi ćete biti
praćenje gdje sve pokazivače su,
što se događa u vašem strukture podataka, i tako dalje.
Oni će biti vrlo korisno, i to je do vas
Dečki potpuno shvatiti kako Želite li provesti stvari.
>> I tako pset4, od 5-- oh, to je u redu.
Pset5 je pravopisne pogreške.
Kao što sam rekao prije, ti si idući u jednom opet preuzeti izvorni kod od nas.
Tu će biti tri glavna stvari koje će biti preuzimanje.
Vi ćete preuzeti rječnike, cima i tekstovi.
>> Sve te stvari su se bilo rječnici riječi
da želimo da provjerite ili test podataka
da želimo da provjere pravopisa.
I tako rječnici dajemo idete
vam dati stvarne riječi koje želimo možete pohraniti nekako na način koji je
učinkovitiji od niza.
A onda se tekstovi će biti ono što smo
vas da čarolija provjerite je li sve riječi postoje stvarne riječi.
>> I tako tri bloka programi koji ćemo vam dati
nazivaju dictionary.c, dictionary.h i speller.c.
I tako sve dictionary.c čini se što ste pitali za provedbu.
To učitava riječi.
To čarolija provjerava ih, i to čini da da je sve ispravno umetnut.
>> diction.h je samo knjižnica datoteke da proglasi sve te funkcije.
I speller.c, ćemo vam dati.
Ne morate mijenjati ništa od toga.
Sve speller.c se je uzeti, opterećenja, provjerava brzinu njega,
ispituje mjerilo poput kako brzo ste u mogućnosti to učiniti stvari.
>> To je bukvar.
Samo nemojte igrati s njim, ali bi jeste li razumjeli što to radiš.
Mi koristimo funkciju zove getrusage da testovi performanse vašeg čarolija
provjeru.
Sve je to ipak u osnovi testirati Vrijeme svega u svom rječniku,
tako da bi bili sigurni da ga razumijemo.
Budite oprezni da ne igrati s njim ili drugo stvari neće raditi ispravno.
>> I većina ovog izazov je za ti dečki stvarno izmijeniti dictionary.c.
Mi ćemo vam dati 140.000 riječi u rječniku.
Mi ćemo vam dati tekst datoteku koja ima te riječi,
i želimo da budete u mogućnosti organizirati ih u hash tablicu ili Trie
jer kad smo vas da čarolija check-- zamislite ako ste čarolija
provjeru poput Homerovih Odyssey.
To je kao što je ovaj ogroman, ogroman test.
>> Zamislite da svaki riječ koju je morao gledati
kroz niz 140.000 vrijednosti.
To bi se zauvijek za vaš stroj radi.
Zato želimo organizirati naše podataka u učinkovitijih struktura podataka
kao što je hash tablicu ili Trie.
I onda vi možete vrsta kada se traži pristup
stvari lakše i brže.
>> I stoga budite oprezni u rješavanju sudara.
Ti si idući u dobiti hrpu riječi tog starta s A.
Ti si idući u dobiti hrpu riječi kako početi s B. Do tebe
Dečki kako želite to riješiti.
Možda ima još učinkovita funkcija mljeveno meso
nego samo prvo slovo nešto, i to tako da je na vama
dečki vrsta učiniti što god želite.
>> Možda želite dodati sva slova zajedno.
Možda želite željeli raditi čudne stvari na račun broj slova,
kako god.
Do vama kako želite raditi.
Ako želite napraviti hash tablicu, ako ste želite probati Trie, potpuno na vama.
Ja ću vas upozoriti ispred vremena koje je Trie je obično malo teže
samo zato što je puno više upućuje pratiti.
Ali totalno do vas dečki.
To je daleko učinkovitiji u većini slučajeva.
Vi stvarno želite biti u mogućnosti to držati praćenje svih vaših upućuje.
Kao učiniti istu stvar da radim ovdje.
Kada pokušavate umetnuti vrijednosti u hash tablicu ili izbrisati,
pobrinite se da ste stvarno praćenje
gdje je sve jer je to je stvarno lako za ako sam
pokušavate umetnuti poput riječi, Andy.
Recimo samo da je Pravi riječ, riječ, Andy,
u diva popis A riječi.
>> Ako sam slučajno preraspodijeliti pokazivač krivo, ups,
tu ide cjelokupnost ostatak mog popisa povezane.
Sada je samo riječ koju imam je Andy, a sada
sve ostale riječi u rječnik su izgubljeni.
I tako želite biti sigurni da pratiti sve svoje pokazivače
inače si idući u dobiti veliki problemi u kodu.
Nacrtaj stvari pažljivo korak po korak.
To ga čini mnogo lakše misliti.
>> I na kraju, želite biti u mogućnosti testirati svoje performanse vašeg programa
na velikom brodu.
Ako vi uzeti pogledajte CS50 upravo sada,
imamo ono što se zove velika odbora.
To je rezultat list najbrže Provjera pravopisa puta u svim CS50
upravo sada, mislim da je vrh kao 10 puta mislim osam ih je osoblje.
Mi doista želite li vi da nas tuku.
>> Svi od nas su pokušali provesti najbrži kod moguće.
Želimo ti dečki pokušati osporiti nas i provesti brže od svih nas
može.
I tako je to stvarno prvi put da smo
traži dečki napraviti pset da zaista možete učiniti u bilo kojoj metodi
ti želiš.
>> Uvijek kažem, to je više moj u stvarnom životu rješenje, zar ne?
Kažem, hej, moram li to učiniti.
Graditi program koji radi ovo za mene.
Učinite to kako god želite.
Ja samo znam da želim postiti.
To je tvoj izazov za ovaj tjedan.
Vi, idemo vam dati zadatak.
Mi ćemo vam dati izazov.
A onda je na vama potpuno jednostavno shvatiti
što je najbrži i najviše učinkovit način za provedbu ovoga.
Da?
>> PUBLIKA: Jesmo li dopušteno htio istražiti brže načine
učiniti hash tablice line, možemo učiniti to i navode tuđe šifru?
ANDI PENG: Da, potpuno u redu.
Dakle, ako vi pročitali spec, postoji linija
u spec koji kaže da dečki su potpuno besplatni za istraživanje mljeveno meso
funkcionira na ono što su neki od brže hash funkcija
pokrenuti stvari kroz što dok vam citirati taj kod.
Dakle, neki ljudi su već shvatio brze načine
radiš za provjeru pravopisa, brzim načini pohrane podataka.
Totalno do vas dečki, ako vas žele samo uzeti to, zar ne?
Provjerite jeste li navodeći.
Izazov ovdje stvarno da smo pokušava testirati
biti sigurni da znate svoj put okolo naputke.
Koliko provedbi stvarna hash funkcija
i dolaze s kao math to učiniti,
vi možete istražiti sve što Metode online dečki žele.
Da?
>> PUBLIKA: Možemo citirati samo pomoću [nečujan]?
>> ANDI PENG: Da.
Možete samo u svoj komentar, možete navesti kao, oh,
preuzet iz BLA, Yada, Yada, hash funkcija.
Bilo tko imati bilo kakvih pitanja?
Mi zapravo breezed kroz sekcije danas.
Ja ću biti ovdje da se odgovoriti na pitanja kao dobro.
>> Također, kao što sam rekao, uredski sati večeras i sutra.
Spec ovaj tjedan je zapravo super jednostavno i super kratke čitati.
JA će predlagati uzimanje pogledati, samo pročitajte cjelinu njega.
>> I Zamyla zapravo šetnje preko svake funkcije
morate provesti, pa je vrlo, vrlo jasno kako to učiniti sve.
Samo kako bi bili sigurni da ste praćenje upućuje.
To je vrlo izazovna pset.
>> Nije zahtjevna, jer kao što je, oh, pojmovi su mnogo
teško, ili morate naučiti toliko Novi sintaksa način
što si učinio za posljednji pset.
To je teško jer pset ima toliko naputke,
a onda je vrlo, vrlo lako jednom imate bug u kodu neće moći
pronaći gdje da bug.
>> I tako potpuni i izustiti vjera u vama dečki biti u mogućnosti da tuku naše [nečujan]
pravopisa.
Ja zapravo nemam nikakav pisani mina još, ali ću pisati moje.
Dakle, dok ste pisanja tvoje, ja ću pisati moje.
Idem probati napraviti moja brže od tvoje.
Vidjet ćemo tko ima najbrži jedan.
>> I da, ja ću vidjeti sve vi ovdje u utorak.
Ja ću pokrenuti vrste poput pset radionici.
Sve ove sekcije tjedan su pset radionice,
tako da dečki imaju puno mogućnosti za pomoć, radno vrijeme, kao i uvijek,
i ja stvarno gledati prema naprijed čitajući sve vaše momci 'kod.
Imam kvizovi ovdje ako vas dečki žele doći po njih.
To je sve.