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