>> [Predvaja glasba]
>> ANDI PENG: Dobrodošli v 6. tednu oddelka.
Oddaljil smo iz našega standarda Čas sekcija torek
popoldne na to lepo nedeljo zjutraj.
Hvala za vse, ki se mi je pridružila danes, ampak resno,
krog aplavz.
>> To je kar velik napor.
Sem skoraj niti ni uspelo v času, vendar je bilo v redu.
Zato vem, da vas vse so jo samo na kvizu.
First of all, dobrodošli v druga plat tega.
>> Drugič, bomo govorili o tem.
O tem bomo govorili v kvizu.
Bomo govorili o tem, kako delaš v razredu.
Boste v redu.
Imam svoje kvize za si na koncu tod
tako da, če hočete, da bi poglej na njej, popolnoma v redu.
>> Tako hitro, preden začnemo se agenda za danes je, kot sledi.
Kot lahko vidite, smo v bistvu hitro streljanje
skozi cel kup podatkovnih struktur res, res, res hitro.
Tako kot tak ne bo super interactive danes.
To bo samo se mi nekako kričali stvari, ki jih, in če sem vas zmedlo,
če grem prehitro, povej mi.
Oni so samo različne podatke strukture, in kot del
vašega pset za to prihajajoči teden, boste
morali izvajati enega od njih, morda dve them-- dva od njih
V vašem pset.
OK, tako da sem le, da bo začeti z nekaj objav.
Mi bomo šli čez nizov in čakalnih vrst več v globina od tistega, kar smo storili pred kviz.
Mi bomo šli čez povezana Seznam enkrat, še enkrat,
bolj poglobljeno kot kaj smo imeli pred kviz.
In potem bomo govorili o hash mize, drevesa in poskuša, ki
so vsi zelo potrebno za vašo pset.
In potem bomo šli čez nekaj koristnih nasvetov za pset5.
>> OK, tako kviz 0.
Povprečna bil 58%.
To je bila zelo nizka, in tako vidva vse naredila zelo, zelo dobro, v skladu
s tem.
>> Precej, pravilo palca je, če ste v standardni odmik od srednje vrednosti
še posebej, ker smo v manj udoben oddelek, ste popolnoma v redu.
Si na pravi poti.
Življenje je dobro.
>> Vem, da je strašljivo, da misliš, da Imam kot 40% na tem kvizu.
Grem na neuspeh ta razred.
Obljubljam vam, da niste dogaja, da ne razred.
Vi ste popolnoma v redu.
>> Za tiste med vami, ki je dobil več kot srednja, impresivna, impresivno,
kot resno dobro opravljeno.
Sem jih imel z mano.
Vas prosimo, da pridejo jih dobite Na koncu dela.
Dovolite mi, da vem, če imate vprašanja, vprašanja z njimi.
Če bomo dodali svoj rezultat narobe, nam to sporočite.
>> OK, tako pset5, da je to res čudno teden Yale v smislu
da je naša pset zaradi Sreda opoldne vključno
pozno dan, tako da je dejansko teoretično zaradi torek opoldne.
Verjetno nihče ni končana v torek opoldne.
To je povsem v redu.
Bomo imeli uradnih ur Nocoj kot tudi v ponedeljek zvečer.
In vsi oddelki ta teden bo dejansko spremenila v delavnicah,
zato vas prosimo, da v pop vsaka sekcija hočeš,
in oni bodo vrste mini-pset Delavnice za pomoč pri tem.
Tako kot tak, to je samo odsek kjer smo učno gradivo.
Vsi ostali oddelki bodo poudarkom izključno na pomoč za pset.
Ja?
>> OBČINSTVO: Kje so uradne ure?
>> ANDI PENG: Govorilne ure tonight-- oh, dobro vprašanje.
Mislim, da uradne ure nocoj so v Teal ali na Commons.
Če preverite spletno CS50 in greste na uradnih ur,
ne bi smelo biti časovni razpored, ki vas, kjer so vse od njih pove.
>> Vem, da nocoj bodisi ali jutri je teal,
in mislim, da smo lahko commons za drugo noč.
Nisem prepričan.
Dobro vprašanje.
Preverite na CS50.
>> Cool, vsa vprašanja v zvezi z urnik za naslednji kot tri dni?
Obljubim vam fantje, kot Davidova je dejal, da je to vrh hriba.
Vidva sta skoraj tam.
Samo še tri dni.
Tja, in potem bomo vsi prišli dol.
Bomo imeli lepo CS-premor.
Se bomo vrnili.
Bomo potopite v spletu načrtovanje in razvoj,
Stvari, ki so zelo zabavno primerjavi za nekatere druge psets.
In to bo chill, in bomo imeli veliko zabave.
Bomo imeli več sladkarij.
Žal mi je za sladkarije.
Pozabil sem sladkarije.
Grobo jutro je bilo.
Torej, fantje so skoraj tam, in res sem ponosen na vaju.
>> OK, tako nizov.
Kdo je ljubil vprašanje o Jacku in njegova oblačila na kvizu?
Nihče?
OK, da je v redu.
>> Torej, v bistvu, kot si lahko slika Jack, ta tip tukaj,
ljubi vzeti oblačila od vrha dimnika,
in on ga postavi nazaj na Sveženj, potem ko je to storjeno.
Torej, na ta način, da nikoli ne Zdi se, da postaja
na dnu kup v njegovi oblačila.
Tako da je ta vrsta opisuje osnovna struktura podatkov
o tem, kako se izvaja kup.
>> V bistvu, pomislite kup vsaka skladu predmetov
kjer si dal stvari na vrhu, in potem jih pop ven iz vrha.
Torej LIFO je kratica želimo da use-- Zadnji noter, prvi ven.
In tako zadnji noter na vrhu Sveženj je prvi, da pride ven.
In tako oba izraza smo želeli povezati
s tem se imenujejo potiskanje in pop.
Ko potisnete nekaj na kup in ga pop nazaj gor.
>> In zato mislim, da je to nekakšna abstrakten pojem za tiste med vami
ki želijo videti kot dejansko izvajanje te
v resničnem svetu.
Koliko od vas je napisal esej morda kot eno uro, preden je bila posledica,
in ste pomotoma izbrisali velik kos njem, kot po naključju?
In potem, kaj storiti nadzor bomo uporabili, da ga proda nazaj?
Control-Z, ja?
Control-Z, tako da je količina roki da je Control-Z mi je rešil življenje,
je rešil rit, vsakič ki je izvajal prek dimnika.
>> V bistvu vse informacije da je na vašem Wordov dokument,
da dobi potiska in izstrelil po volji.
In tako v bistvu vsakič, ko vas izbrisati ničesar, ga pop nazaj gor.
In potem, če jo potrebujete nazaj na vas ga potisnite, ki je tisto, kar Control-C ne.
In tako v realnem svetu funkcija kako enostavno strukturo podatkov
lahko pomaga pri vašem vsakdanjem življenju.
>> Torej struct je način, da smo dejansko ustvarili kup.
Tip definiramo struct, in nato pravimo, da kup na dnu.
In v skladovnice, imamo dva parametra
da bomo lahko v bistvu manipulirati, tako da imamo char zvezdic strune zmogljivosti.
>> Vse to počne ustvarja niz
da bomo lahko shranite kar hočeš ki jih lahko določi svoje zmogljivosti.
Kapaciteta je samo max znesek Predmeti, ki jih lahko postavimo v to paleto.
Velikost int je števec, ki ohranja tir koliko predmetov so trenutno
v plasteh.
Torej, potem bomo lahko spremljate, A, tako, kako velika je dejansko dimnika je,
in, B, koliko tega skladovnice smo napolnjena, ker ne želimo,
overflow nad tem, kaj je naša zmogljivost.
>> Tako, na primer, to čudovito Vprašanje je bilo na kvizu.
V bistvu, kako bomo potisnite na vrhu kupa.
Zelo preprosta.
Če pogledaš na to, bomo sprehod skozi to.
Če [neslišno] size-- se spomnite, ko ste
želijo dostop do kateregakoli parameter v struct,
vam ime struct.parameter.
>> V tem primeru je s ime našega dimnika.
Želimo, da za dostop do velikosti od tega, da naredimo s.size.
Torej, dokler je velikost ne enako kapaciteto ali dokler
kot je manjša od prostornine, bodisi bi delo tukaj.
>> Želite dostopati do notranjosti žetonov, tako s.strings,
in boš dal, da novo številko da želite vstaviti v tam.
Recimo samo, da bomo želeli vstavite int n na stack,
kar lahko storimo s.strings, nosilci, s.size enaka n.
Ker velikost je kje smo Trenutno so v plasteh
če bomo za potiskanje je on, smo pravkar dostop
povsod, kjer je velikost, Sedanji polnost dimnika,
in smo potisnite int n nanjo.
In potem smo se želeli prepričati, da smo tudi povečevanje velikosti n,
tako da bomo lahko spremljate smo jih dodal dodatno stvar dimnika.
Zdaj imamo večjo velikost.
Ali to tukaj smiselno vsakdo, kako logično deluje?
Bilo je nekako hitro.
OBČINSTVO: Lahko greš čez se s.stringss.strings [s.size] spet?
ANDI PENG: Seveda, pa kaj počne s.size trenutno nam dali?
OBČINSTVO: To je sedanja velikost.
ANDI PENG: Točno, zato je tekoči indeks, da je naša velikost na,
in tako smo želeli postaviti nov celo število da želimo vstaviti v s.size.
Ali to smiselno?
Ker s.strings, vse, se je ime array.
Vse to se je dostopom do Niz v naši struct,
in zato, če želimo, da postavite n v ta indeks,
bomo lahko le dostop do njega uporabljajo nosilci s.size.
Cool.
>> Vredu, pop, sem ga psevdokoda ven za vas, ampak podoben koncept.
Ali to smiselno?
Če je velikost večja od nič, potem ste
veš, da si želiš, da bi nekaj ven, ker če je velikost ne
večja od nič, potem ste nimajo nič dimnika.
>> Torej si le želite izvesti Ta koda, ki lahko samo to
pop če obstaja nekaj, da pop.
Torej, če je velikost večja od 0, smo minus velikost.
Pojemanje smo velikost in se nato vrnite vse, kar je znotraj njega, ker
jih popping, želimo Dostop kar je shranjena
v indeksu vrhu kupa.
Vse, kar je smiselno?
Če sem ti fantje napisali tole, bi vidva lahko to napisali?
OK, lahko vidva igral z njim.
Brez skrbi, če ga ne bi dobili.
Nimamo časa, da kodo ven danes, ker smo jih
dobil veliko teh struktur da gredo skozi, vendar v bistvu
psevdokoda, zelo, zelo podobno kot potiskanje.
Samo sledite skupaj z logiko.
Prepričajte se, da dostop do vseh značilnosti vašega struct pravilno.
Ja?
>> OBČINSTVO: Bo ta diapozitivov in ta stvar lahko še danes-ish?
ANDI PENG: Vedno, ja.
Bom poskusil, da dajo to gor, kot eno uro kasneje.
Bom email Davida, bo David poskušali ga dal gor, kot eno uro po tem.
>> OK, potem pa gremo v to drugo Lep podatkovno strukturo, imenovano čakalno vrsto.
Kot lahko vi vidite tukaj, A Čakalna vrsta za Britancev med nami,
vse, kar je, je črta.
Torej, v nasprotju s tem, kar misliš, da stack,
čakalna vrsta je natanko tisto, logično mislite, da je.
To je potekalo po pravilih FIFO, ki je prvi noter, prvi ven.
Če ste prvi eden v vrsti, da ste
prvi, ki prihaja iz vrste.
>> Torej, kaj mi je všeč, da to imenujemo je dequeueing in enqueueing.
Če želimo dodati nekaj za našo vrsto, smo enqueue.
Če želimo dequeue, ali pa nekaj proč, smo dequeue.
>> Torej enak občutek, da smo nekako ustvarjanje fiksne velikosti elementov, ki smo
lahko shranite nekatere stvari, vendar smo lahko tudi
spremeniti, kjer smo dajanje parametri znotraj njih
temelji na kakšnem tipu funkcionalnost želimo.
Torej nizov, smo želeli zadnji on, N, da je prva ven.
Čakalna vrsta je želimo, je prva stvar, v biti prva stvar ven.
>> Torej je struct-type opredeliti, kot lahko vidite,
to je malo drugačna od tistega, kar je bilo kup
ker ne samo, da moramo hraniti tir, kjer trenutno je velikost,
želimo tudi, da spremljate glave kakor tudi, kjer smo trenutno so.
Zato mislim, da je lažje če sem to pripraviti.
Torej, kaj je zamisliti imamo čakalno vrsto, tako recimo glava je tukaj.
Vodja linije, dajmo samo povem, da je trenutno tam,
in želimo, da vstavite nekaj v čakalno vrsto.
Bom poklical velikost bistvu je ista stvar kot rep,
konec kjerkoli vaša čakalna vrsta je.
Naj samo povem, velikost je tukaj.
>> Torej, kako en izvedljiv vstavite nekaj v čakalno vrsto?
Kaj indeks želimo postaviti kjer želimo vstaviti v.
Če je to začetek vašega čakalno vrsto in to je konec tega
ali velikost njej, kjer počnemo želite dodati naslednjo predmeta?
>> OBČINSTVO: [neslišno]
ANDI PENG: Točno, ki jih želite dodati je odvisno od tega, ki ste ga napisali.
Ali je to polje prazno ali da je prazen.
Torej hočeš, da ga dodate verjetno tukaj, ker če velikost is--
če so ti vse polno, ki jih želite da jo dodate tukaj, kajne?
>> In tako, da je, medtem ko je zelo, zelo preprosto, ne čisto vedno pravilna
ker glavni razliki med čakalno vrsto in dimnika
je, da je čakalna vrsta dejansko manipulira
tako da so te spremembe glave odvisno od tega, kje želite
začetek vašega iztočnico za začetek.
In kot rezultat, svoj rep se tudi dogaja, da spremenite.
In tako si oglejte ta koda prav zdaj.
Ker so fantje tudi zahteva, da se izpišite na kvizu, enqueue.
Mogoče bomo govorili skozi zakaj odgovor je bil, kaj je bilo.
>> Nisem mogel povsem fit to vrstico na eni, ampak v bistvu je ta del kode
mora biti v eni vrstici.
Preživite kot 30 sekund.
Oglejte si, in zakaj to je način, da je.
>> Zelo, zelo podobna struct, zelo zelo podobno strukturo kot prejšnja
kup razen morda ena vrstica kode.
In da eno vrstico kode določa funkcionalnosti.
In res razlikuje čakalne vrste iz dimnika.
>> Kdo želel vzeti stab pri pojasnjevanju, zakaj ste
dobil to zapleteno stvar tukaj?
Vidimo vrnitev naših čudovit prijatelj modul.
Ker bo vidva kmalu prepoznati v programiranju,
skoraj kadarkoli boste potrebovali nekaj da ovijte okoli nič,
modul se bo pot, da to storite.
Torej, vedoč, da se kdo hotel da bi poskušali razložiti to vrstico kode?
Ja, vsi odgovori so sprejeta in dobrodošla.
OBČINSTVO: Ali ste v pogovoru z mano?
ANDI PENG: Ja.
OBČINSTVO: Oh, ne opravičujem.
ANDI PENG: OK, tako da je sprehod skozi to oznako.
Torej, ko ste poskušali kaj dodati na čakalno vrsto,
v lepem primeru, da glava zgodi da je prav tukaj, je zelo enostaven za nas
samo iti do konca vstavite nekaj, kajne?
Toda bistvo čakalno vrsto je da vodja lahko dejansko dinamično
spreminjajo glede na to, kje smo želijo začetek našega q biti,
in kot tak, repa se tudi dogaja, da spremenite.
>> In tako si predstavljam, da to ni bil čakalne vrste, temveč je bila ta čakalna vrsta.
Recimo, glava je tukaj.
Recimo, da je naša čakalne videti takole.
Če bi želeli preusmeriti, kjer začetek liniji,
recimo, da smo premaknilo glavo Na ta način in velikosti tukaj.
>> Sedaj želimo dodati nekaj to čakalne vrste, ampak kot lahko vi vidite,
to ni tako enostavno, kot da samo dodamo kar je po velikosti
ker potem mi zmanjka Meje našega dejanskega paleto.
Kjer želimo res dodati je tukaj.
To je lepota čakalno vrsto je, da je za nas, vizualno pa
Izgleda, da je linija gre takole, toda, če je shranjena v podatkovno strukturo,
jim ga dal kot kot cikel.
To nekako ovije spredaj na enak način,
da lahko črta tudi zaviti okoli odvisno od kjerkoli vas
želijo začetku vrstice biti.
In tako, če vzamemo poglej tukaj, dajmo
rekli, da smo želeli ustvariti Funkcija se imenuje enqueue.
Želeli smo dodati int n v tem q.
Če q.size -Q- bomo pokličem, da naše podatke structure-- če naša queue.size ne
enako kapaciteto ali če to je manj kot zmogljivosti,
q.strings je matrika v naši q.
Gremo nastaviti ki je enaka q.heads,
ki je tukaj, plus q.size modul s kapaciteto, ki je
zaviti nas spet tukaj.
>> Torej, v tem primeru, indeksa glave je 1, kajne?
Indeks velikosti 0, 1, 2, 3, 4.
Torej ne moremo storiti 1 plus 4 modul jih naše zmogljivosti, ki je 5.
Kaj nam daje?
Kaj je indeks, ki prihaja iz tega?
>> OBČINSTVO: 0.
>> ANDI PENG: 0, kar zgodi, da se prav tu,
in zato želimo, da bi lahko da vstavite tukaj.
In zato je ta enačba tukaj vrsta za preprosto deluje z vsemi številkami
odvisno od tega, kje si glava in vaše velikosti so.
Če veste, kaj tisti, so stvari, veste
točno tam, kjer želite vstaviti kar je po vašem čakalno vrsto.
Ali, da je smiselno, da vse?
>> Vem vrste možganov teaser še posebej, ker je to
prišel v odpravljanju posledic svojega kviza.
Ampak upajmo, da vsakdo Zdaj lahko razumemo,
zakaj ta rešitev ali je to funkcija je, da ga je.
Vsakdo nekoliko nejasno o tem?
V REDU.
>> In zdaj, če vas želel dequeue, to
je, če bi bila naša glava premika ker če bi dequeue,
nimamo vzlet konec q.
Želimo, da za vzlet glavo, kajne?
Tako kot rezultat, glava se bo spremenilo, in da je razlog, zakaj, ko ste enqueue,
moraš slediti kjer sta vaša glava in tvoja velikost
morajo biti sposobni vstaviti v pravilen položaj.
>> In tako, ko dequeue, Prav tako sem psevdokoda ven.
Vas prosimo, da, če hočeš poskus kodiranje to.
Želite premakniti glavo, kajne?
Če sem želel dequeue sem bi se premaknite nad glavo.
To bi bila glava.
>> In bi naša sedanja velikost odštejemo, ker ne bomo več
ima štiri elemente v matriki.
Imamo samo tri, nato pa želimo vrniti, kar je bila shranjena v notranjosti
glave, ker želimo, da bi to Vrednost ven tako zelo podobna dimnika.
Pravkar ste ob iz druge destinacije,
in boste morali znova dodelite kazalec na drugo mesto, kot rezultat.
Logično je, da vsi sledimo?
Great.
>> OK, tako da bomo govorili malo bolj poglobljeno o povezanih seznamih
ker se bo zelo, zelo dragocen za vas v teku ta teden je
psets.
Povezani seznam, kot vidva spomnim se, vsi so
so vozlišča, ki so vozlišča nekaterih Vrednosti obeh vrednost in kazalcem
ki so med seboj povezani s temi kazalci.
In tako struct o tem, kako smo ustvarili vozlišče tu smo
imajo int n, ki je glede na vrednost v trgovini ali niza n
ali karkoli želite pravijo, char zvezda n.
Struct vozlišče zvezda, ki je kazalec ki želite imeti v vsakem vozlišču,
boste morali, da kazalec točka v smeri naprej.
Imeli boste glavo iz povezanega seznama, ki je
dogaja, da opozarjajo na preostalo vrednosti tako naprej in tako naprej
dokler ne boste sčasoma do konca.
In to zadnje vozlišče je le bo še kazalec.
To se dogaja, da kažejo na null, in da je, ko
veste, da ste zadeli konec vaše povezanega seznama
je, ko tvoj zadnji kazalec ne kaže na nič.
>> Tako smo šli malo bolj v Globina o tem, kako bi bila ena od možnosti
iskati povezani seznam.
Spomnite se, kaj so nekateri od slabosti povezanih seznamov
prehladna paleto zvezi iskanj.
Matrika lahko binarno iskanje, vendar zakaj ne morete storiti, da je v povezanem seznamu?
>> OBČINSTVO: Ker oni so vsi povezani, vendar ne povsem vedeli, kje
[Neslišno].
>> ANDI PENG: Ja, točno tako, ne pozabite da sijaj array
je dejstvo, da smo imeli bralno-pisalnega pomnilnika, kjer
če sem hotel vrednost iz indeksa šest, jaz lahko samo rečem indeks šest,
daj mi te vrednosti.
In to zato, ker so nizi razporejene v sosednjem prostoru pomnilnika
na enem mestu, medtem ko je vrsta povezanih seznamov
so naključno posejani po vsem, in edini način, boste lahko našli enega
je s kazalcem, ki vam pove naslov, kjer je ta dostavo vozlišče.
>> In tako posledično edini način iskanje po povezanem seznamu
linearna iskanje.
Ker mi ni točno vedel, kje 12. Vrednost v povezanem seznamu je,
Moram prečkanje celoto od tega povezanega z enim seznamom
eden od glave do prvega vozla, Na drugo vozlišče, na tretje vozlišče,
vso pot navzdol, dokler sem končno dobil da, kjer je to vozlišče iščem.
In tako v tem smislu, iskanje na povezane seznamu vedno n.
Vedno je n.
To je vedno v linearnem času.
>> In tako je koda, v katerem izvajamo to, kar
je malo novega za vas, saj ste Fantje so se res ne govorili ali kdaj
videl kazalci v tem, kako iskanje po kazalci,
tako da bomo sprehod skozi To je zelo, zelo počasi.
Torej iskanje bool, desno, Predstavljajmo si želimo
ustvariti funkcijo imenovano Iskanje, ki vrne true
Če ste našli vrednost znotraj povezano seznam, in ga vrne false drugače.
Seznam Node zvezdicami Trenutno samo kazalec
na prvi element v vašem povezani seznam.
int n je vrednost, ki ste išče na tem seznamu.
>> Torej vozlišče zvezda kazalec enak seznam.
To pomeni, da smo nastavitev in ustvarjanje kazalec
v tem prvim vozliščem znotraj seznama.
Vsakdo z mano?
Torej, če smo bili, da gredo nazaj, bi moral
inicializiran kazalec, ki kaže na glava, kar je ta seznam.
>> In potem, ko boste dobili tukaj, medtem ko je kazalec ni enak null,
tako, da je zanka, v kateri smo bo nato prečkajo
preostali del našega seznama ker tisto, se zgodi, ko kazalec enaka null?
Vemo, da smo have--
>> OBČINSTVO: [neslišno]
>> ANDI PENG: Točno, zato smo vedeli, da smo prišli do konca seznama, kajne?
Če greš nazaj, vsako vozlišče Treba je poudariti, da drugo vozlišče
in tako naprej in tako naprej dokler si udaril na koncu
rep vašega povezanega seznama, ki ima kazalec, ki le
ne kaže nikamor, razen št.
In tako ste v bistvu vedeti, da Vaš seznam je še vedno tam gor
dokler se kazalec ne enaka null, ker ko je enak null,
saj veš, da ni več stvari.
>> Tako, da je zanka, v kateri smo dogaja, da imajo dejansko iskanje.
In če pointer-- vidiš da vrsta arrow funkcijo tam?
Torej, če je kazalec točk, n, če kazalec na n enako enako n,
To pomeni, da če kazalec, da ste
iskanje na koncu vsakega vozlišče dejansko enaka vrednosti
iščete, potem želite vrniti true.
Torej v bistvu, če ste na vozlišču, ki je vrednost, ki jo iščete,
veste, da ste bili uspešno iskanje.
>> V nasprotnem primeru, da želite nastaviti vaš kazalec na naslednje vozlišče.
To je tisto, ki črta tu počne.
Pointer enak kazalec zraven.
Vsi videli, kako je to delovalo?
>> In v bistvu boš samo prečkanje celotne seznamu
ponastavitev kazalec vsakič, dokler sčasoma dvignil konec seznama.
In veš, da ne obstajajo več vozlišč za iskanje skozi,
in potem se lahko vrnete false saj veš, da, oh, no,
če sem bil sposoben za iskanje preko celotne seznama.
Če se v tem primeru, če bi hotel iskati vrednosti 10,
in začnem na čelu, in Iščem vso pot navzdol,
in sem na koncu prišel do tega, kar kazalec, ki kaže na ničlo,
Vem, da je sranje, mislim, da 10 ni ta seznam, ker nisem mogel najti.
In jaz sem na koncu seznama.
In v tem primeru veš Bom vrnil false.
>> Dovolite, da namakate v za malo.
To bo lepa pomembna za vašo pset.
Logika je zelo preprosta, morda skladenjsko le njeno izvajanje.
Vidva želite prepričani, da razumete.
Cool.
>> OK, tako, kako bi bili vstavljanje vozlišč, desno,
v seznam, saj se spomnite kaj so, kaj koristi
da imajo povezani seznam versus niz v smislu skladiščenja?
>> OBČINSTVO: To je dinamičen, tako da je lažje to--
>> ANDI PENG: Točno, tako da je dinamičen, kar
pomeni, da se lahko razširi in skrči glede na potrebe uporabnika.
In tako, v tem smislu, da ne potrebujemo zapravljati nepotrebnih spomin, ker sem
če ne vem, koliko vrednosti želim za trgovino, pa nima smisla za mene
ustvariti array, ker je če želim shraniti 10 vrednosti
in sem ustvaril niz 1.000, to je veliko zapravlja spomina, dodeljen.
Zato želimo, da uporabite povezan seznam, da bi lahko dinamično
spremeniti ali skrči svojo velikost.
>> In tako, da omogoča vstavljanje malo bolj zapletena.
Ker ne moremo naključno dostop elemente način, da bi iz nabora.
Če želim vstaviti element v sedmi indeksa,
Jaz lahko samo vstavite v sedmi indeks.
Na povezanega seznama, le-ta ne čisto delo tako enostavno,
in tako, če smo želeli, da vstavite ena tukaj v povezanem seznamu
vizualno, to je zelo težko videti.
Pravkar smo želeli, da ga vstavite tam, takoj na začetku seznama,
takoj po glavi.
>> Ampak način, na katerega moramo prerazporediti so kazalci je nekoliko zapletena
ali, logično, je smiselno, ampak želite poskrbite, da ga imate
povsem dol, ker zadnja stvar, ki jo želite
se prerazporedijo kazalec način, da delamo tukaj.
Če vas dereference kazalec od glave do 1,
nato pa vse nenadoma preostanek svojega povezanega seznama
se izgubi, ker moraš dejansko ne ustvaril začasno ničesar.
Ki je opozoril na 2.
Če znova kazalec, nato Preostanek vašem seznamu je popolnoma izgubljen.
Torej hočeš biti zelo, zelo previdni tukaj
najprej dodelite pointer iz Karkoli
želite vstaviti v kjerkoli hočeš, nato pa vas
lahko dereference preostanek svojega seznama.
>> Torej to velja za kamorkoli skušate vstavite.
Če želite vstaviti Na glava, če želite, da tu odgovoriti,
Če želite vstaviti v konec, no, na koncu sem
Verjetno bi le nimajo kazalec, vendar boste
želite poskrbite, da ne boste izgubijo preostanek svojega seznama.
Vedno si želite zagotoviti vaš novi vozlišče je obrnjena
proti karkoli želite vstaviti v,
in potem si lahko dodate veriženje naprej.
Vsakdo jasno?
>> To se bo eden izmed pravih vprašanj.
Eden od najbolj pomembnih vprašanj boste imeli na vašem pset
je, da greš, da bi poskušali ustvariti med sabo povezan seznam in vstavite stvari
potem pa samo izgubili preostanek svojega povezanega seznama.
In ti bo všeč, sem Ne vem, zakaj se to dogaja?
In to je bolečina, da gredo skozi in iskanje vseh vaših nasvetov.
>> In zagotavljam vam na tem pset, pisanje in risanje teh vozlišč ven
bo zelo, zelo koristno.
Tako boste lahko popolnoma spremljate kje so vsi vaši kazalci,
kaj je šlo narobe, kjer so vsi vaši vozlišča,
kaj morate storiti, da bi dostopali ali vstavite ali izbrišete ali kateri koli od njih.
Vsakdo dobro s tem?
Cool.
>> Torej, če smo želeli, da pogled na kodo?
Oh, ne vem, če smo lahko vidite the-- OK, tako
Na vrhu vsega je funkcija imenovan vložek, kjer želimo
vstaviti int n v povezano seznamu.
Gremo na sprehod skozi to.
To je veliko kode, veliko novega sintakse.
Mi bo v redu.
>> Torej na vrhu, kadar želimo ustvariti ničesar
Kaj moramo storiti, še posebej, če vas želim, da bi se ne shranjujejo na kupu
vendar v kup?
Gremo na knjižnične funkcije malloc, kajne?
Tako bomo ustvarili kazalec.
Vozlišče, kazalec, novi Ene malloc velikosti vozlišču
ker želimo, da je vozlišče, ki bo ustvaril.
Želimo količino spomin, da je vozlišče zavzame
bodo dodeljene za Ustanovitev novega vozlišča.
>> In potem bomo preverite vidim, če novi Ene enaka null.
Spomni se, kaj smo rekli?
Karkoli vam malloc, Kaj morate vedno narediti?
Morate vedno preverite, ali je, da nič.
>> Na primer, če je vaš operacijski Sistem je bil povsem poln,
če bi imeli nič več pomnilnika na vse in poskusite knjižnične funkcije malloc,
da bi se vrnil null zate.
In tako, če boste poskušali uporabiti ko je bila obrnjena na ničlo,
ti ne boš mogel za dostop do teh informacij.
In tako, kot smo želeli, da bi prepričani, da ko ste mallocing,
ste vedno preverjanje, da vidim, če da spomin dal je nična.
In če je ni, potem lahko gremo o s preostalim naše kode.
>> Torej bomo inicializacijo novo vozlišče.
Bomo storili nov n enak n.
In potem bomo storili nastaviti nov kazalec na novo
na nič, ker zdaj ne bomo želim ničesar za to, da kaže.
Nimamo pojma, kje to se dogaja, da si dal,
in potem, če želimo ga vstavite na čelu,
potem bomo lahko znova dodelite kazalec z glavo.
Ali vsi sledimo logiki kje, da se dogaja?
>> Vsi delamo ustvarja nova vozlišče, ki določa kazalec na ničlo,
in nato prerazporeditev je v glavo, če bomo
vem, želimo, da ga vstavite v glavo.
In potem glava se bo kažejo na to novo vozlišče.
Vsakdo v redu s tem?
>> Torej, to je dvostopenjski postopek.
Imaš do prvega Dodeli kar ste ustvarili.
Nastavite, da kazalec na reference, nato pa vas
lahko vrsta ciljne datoteke Prvi kazalec
in kažejo na novo vozlišče.
Kjerkoli jo želite vstaviti, da logika se dogaja, da drži.
>> To je nekako kot dodeljevanje začasne spremenljivke.
Zapomnite si, da imaš se prepričajte, da vas
ne bo zmanjkalo, če ste zamenjavo.
Želite, da se prepričajte, da imate začasna spremenljivka, ki nekako ohranja
tir, kjer je to stvar se shranijo, tako da boste
ne izgubijo katerokoli vrednost med podobnega mesijanski okrog z njim.
>> OK, tako da koda bo tukaj.
Vidva si oglejte po oddelku.
To bo tam.
>> Torej, mislim, kako deluje To je drugačna, če smo želeli
vstaviti v sredini ali na koncu?
Ima kdo idejo, kaj je psevdokoda kot logično referenca
da bomo, če bomo želeli da jo vstavite v sredini?
Torej, če bi želeli, da ga vstavite Na glava, vse moramo storiti, je ustvariti novo vozlišče.
Postavili smo kazalec, ki novo vozlišče na kakršnikoli glavo,
in potem smo postavili glavo na novo vozlišče, kajne?
Če bomo želeli, da ga vstavite v sredini seznama, kaj bi morali storiti?
>> OBČINSTVO: To bi še vedno Podobna Postopek
podobnega dodeljevanje kazalec in nato dodelite ta kazalec,
vendar bi morali tam poiskati.
>> ANDI PENG: Točno tako natanko enak postopek, razen tebe
morali poiskati, kje ste želijo, da novi kazalec, da gredo v,
tako da, če hočem, da vstavite Sredi povezana list-- OK,
recimo, da je naša povezani seznam.
Če želimo, da jo vstavite tukaj, bomo ustvarili novo vozlišče.
Bomo knjižnične funkcije malloc.
Bomo ustvarili novo vozlišče.
Bomo dodelite kazalec tega vozlišča tukaj.
>> Vendar je problem, ki se razlikuje od koder je glava
je, da smo vedeli, točno kjer je glava.
Bilo je prav na prvi, kajne?
Ampak tukaj imamo slediti kje smo jo vstavite.
Če smo vstavljanje naše node tukaj, imamo
se prepričajte, da ena od prejšnjih za to vozlišče
je tista, ki reassigns kazalec.
Torej moraš nekako spremljate dveh stvari.
Če spremljate, kjer je to vozlišče trenutno vstavite.
Prav tako morajo slediti, kje prejšnja vozlišče, da gledaš
je tudi tam.
Vsakdo dobro s tem?
V REDU.
>> Kako približno vstavite do konca?
Če bi želel, da ga dodate here-- če sem hotel dodati novo vozlišče na konec seznama,
kako bi jaz šel o tem?
OBČINSTVO: Torej, trenutno je zadnja je opozoril na nič.
ANDI PENG: Ja.
Točno, tako da je to ena Trenutno je poudaril, da vedo,
in tako mislim, v tem smislu, da je Zelo enostavno dodajanje na konec seznama.
Vse kar morate storiti je, da jo nastavite enaka NULL in potem bum.
Prav tam, zelo enostavno.
Zelo preprosto.
>> Zelo podobna glavo, vendar je logično vas
želite zagotoviti, da ukrepi jemljete proti delaš vse to,
ste po skupaj.
To je zelo enostavno, v sredini vaše kode, ujeli na,
oh, sem dobil toliko nasvetov.
Ne vem, kje vse kaže na.
Sploh ne vem, katero vozlišče sem na.
Kaj se dogaja?
>> Pomiri se, pomiri se, globoko vdihni.
Potegnili svoje povezani seznam.
Če rečeš, vem, kje točno Moram vstaviti to v
in točno vem, kako prerazporediti my kazalci, veliko, veliko lažje sliko
out-- veliko, veliko lažje, da se ne izgubijo v hroščev v kodi.
Vsakdo v redu s tem?
V REDU.
>> Tako da mislim, koncept, ki ga imamo, ne res govoril o pred zdaj,
in ti veš verjetno ne bodo imeli veliko yet--
to je nekako napredno concept-- je, da smo dejansko imeli podatke
struktura se imenuje dvojno povezani seznam.
Tako da lahko vi vidite, vse, kar počnete, je ustvarjanje
dejanska vrednost, dodatno kazalec na vsakega od naših vozlišč
ki kaže tudi s predhodnim vozliščem.
Torej, ne samo, da imamo vozlišča kaže na naslednjega.
Prav tako opozarjajo, da prejšnji.
Grem prezreti teh dveh prav zdaj.
>> Torej imate verigo ki se lahko premika v obe smeri,
in potem je nekoliko lažje logično sledijo vzdolž.
Kot tod namesto sledenja, oh, jaz
morali vedeti, da je to vozlišče tisti, ki moram prerazporedijo,
Jaz lahko samo iti tu in samo potegnite prejšnji.
Potem vem, kje da je, nato pa vas
nimajo za prečkanje celota povezanega seznama.
To je nekoliko lažje.
>> Ampak kot taka, imate dvakrat količina kazalcev,
da je dvojna količina pomnilnika.
To je veliko nasvetov za sledenje.
To je malo bolj zapleteno, vendar je malo bolj prijazen do uporabnika, odvisno
o tem, kaj poskušate doseči.
>> Tako da je ta vrsta podatkov struktura povsem obstaja,
in struktura je zelo, zelo preprosta razen vse, kar imaš, je,
namesto samo kazalec na naslednjo, imate tudi kazalec na prejšnji.
To je vse, kar je bila razlika.
Vsakdo dobro s tem?
Cool.
>> Vse je v redu, tako da zdaj sem res porabili verjetno
kot 15 do 20 minut, ali pa bo večji preostalega časa v oddelku
govorimo o hash tabel.
Koliko od vas fantov Prebral pset5 spec?
Dobro, dobro.
To je višja od 50% normalno.
To je v redu.
>> Tako da bodo fantje videli, ste izziv pset5
bo izvajala slovar kjer si naložiti preko 140.000 besed
da smo vam in preverjanje črkovanja je proti vsem besedilu.
Mi vam bomo naključno kosov literature.
Mi vam bomo Odiseje.
Mi vam bomo Iliadi.
Mi vam bomo Austin Powers.
>> In vaš izziv bo preverjanje črkovanja
vsak beseda v vseh od teh slovarjev
v bistvu z našo črkovalnik.
In tako obstaja nekaj delov ustvarjanja to pset,
Prvi hočeš biti lahko dejansko obremenitev
vse besede v vašo slovar, nato pa vas
želijo biti sposobni črkovati ček vse od njih.
In tako, kot je na primer, da boš zahtevajo podatkovna struktura, ki lahko to stori hitro
ter učinkovito in dinamično.
>> Torej, mislim, da je najlažje način, da to storite, vas
Verjetno bi ustvarili niz, kajne?
Najlažji način shranjevanja je vas lahko ustvarite niz 140.000 besed
in jih vse samo mesto tam in jih nato prečkala s binarnega iskanja
ali z izborov ali not-- Žal mi je, da je razvrščanje.
Lahko jih uredite in jih nato prečkala s binarnega iskanja ali pa samo linearno iskanje
in samo končne besede, temveč da potrebnega ogromno pomnilnika,
in to ni zelo učinkovito.
>> In tako bomo za začetek govorimo o načinih izdelave
naš čas teče bolj učinkovito.
In naš cilj je, da bi dobili konstanten čas, kjer
to je skoraj tako kot nizi, kjer imate takojšen dostop.
Če sem hotel iskati karkoli, Želim, da bi lahko le,
boom, da bi našli točno, in ga izvlecite.
In tako strukturo, v kateri bomo lahko postali zelo blizu
da se lahko dostop konstantna Tokrat je to sveti gral
v programiranju konstanta Čas se imenuje hash tabelo.
In tako je David že prej omenjeno [Neslišno] malo v predavanju,
ampak bomo res potop v globokem tem tednu
na kos, ki je v zvezi s kako hash tabela deluje.
>> Torej, na način, da je hašiš namizno dela, na primer,
če sem hotel, da shranite kup besedami, kup besed v angleškem jeziku,
Jaz bi teoretično dal banana, jabolko, kivi, mango, par,
in melone vse na samo paleto.
Lahko bi prilegajo in jih je najti.
To bi bilo nekako v bolečinah iskanje po in dostop,
vendar je lažji način za to je, da bomo lahko ustvarili dejansko strukturo
imenuje hash tabele, kjer smo izbrskali.
Vodimo vse naše ključev prek funkcija hash, enačba,
ki jih vse spremeni v nekakšna vrednosti
da potem bomo lahko shranite na v bistvu paleto povezani seznam.
>> In tako sem, če bomo želeli za shranjevanje angleške besede,
smo lahko potencialno samo, jaz ne Veš, pa vse prve črke v
v neke vrste številko.
In tako, na primer, če sem hotel A sinonim apple--
ali z indeksom od 0, in B sinonim z 1,
imamo lahko 26 vnose da lahko samo shranite
vse črk alphabet, da bomo začeli z.
In potem bomo lahko imeli jabolko na indeks 0.
Imamo lahko banano na indeksu 1, melone na indeksu 2,
in tako naprej in tako naprej.
In zato, če sem hotel iskati moj hash tabele in dostop jabolko,
Vem, jabolko začne z A, in točno vem,
da mora biti in razpršitve miza na indeksu 0 zato ker
funkcije predhodno dodeljena.
>> Torej, ne vem, mi smo program uporabniški kadar
vam bomo zaračunali z arbitrarily-- ne samovoljno,
s poskušajo premišljeno mislim dobrih enačb
da se lahko širi iz vseh vaših vrednot
na način, ki jih lahko enostavno dostopate je kasneje s podobno enačbo
da vas, sami, vem.
Torej, v tem smislu, če sem hotel iti mango, vem, oh, se začne z m.
Mora biti v indeksu 12.
Nimam iskati skozi karkoli.
Vem exactly-- sem lahko samo iti indeks 12 in potegnite, da ven.
>> Vsakdo jasno, kako Funkcija hash tabele se deluje?
To je nekako le bolj kompleksno paleto.
To je vse, kar je.
V REDU.
>> Torej, mislim, da smo zašli v to vprašanje o tem, kaj
se zgodi, če imate več stvari da vam isti indeks?
Tako pravijo naše delovanje, vse to naredil je bilo to prvi dopis
in nato da na A Ustrezni 0 do 25 indeks.
To je povsem v redu, če ste le eden od vsakega.
Ampak drugi začnete ki imajo več, ste
dogaja, da imajo, kaj se ti trčenja.
>> Torej, če sem poskusil vstaviti pokopati v hash tabela, ki ima že banano na njem,
kaj se bo zgodilo, ko poskusite vstaviti to?
Slabe stvari, ker banana že obstaja v indeksu
ki jo želite shraniti v.
Berry vrsta je všeč, ah, kaj naj storim?
Ne vem, kam iti.
Kako rešiti to?
>> In tako bo vidva vrste glej delamo to težavno stvar
kjer bomo lahko nekako dejansko ustvariti povezan seznam iz naših polj.
In tako najlažje razmišljati o tem,
Vse hash tabela je array povezanih seznamov.
In tako, v tem smislu, imate to lepo niz kazalcev,
in nato vsak kazalec v da vrednost, v tem indeksu,
lahko dejansko kažejo na druge stvari.
In tako imaš vse te ločene verige prihajajo off enega velikega polja.
>> In tako sem, če sem želel vstaviti jagodami,
Vem, OK, bom vhod je po mojem hash funkcijo.
Grem na koncu z indeksom 1, in potem bom lahko, da imajo
le manjši podmnožica to velikan 140.000 besedo slovar.
In potem sem lahko samo pogled skozi 1/26 tega.
>> In tako potem bom lahko samo vstavite berry bodisi pred ali po banana
v tem primeru?
Potem, kajne?
In tako boste želeli vstavite to vozlišče po banana,
in tako boste, da vstavite na repu tega povezanega seznama.
Jaz bom šel nazaj s tem prejšnjo prosojnico,
tako da vidva lahko vidite, kako hash funkcija deluje.
>> Torej hash funkcija je ta enačba da delate neke vrste vaš prispevek
skozi, da bi dobili, kar indeks Jo želite dodeliti smeri.
In tako, v tem primeru, vse, kar smo želeli storiti je vzeti prvo pismo,
obrnejo, da v indeksu, nato pa smo lahko shranite, da je v našem hash funkcijo.
Vsi delamo tu smo pretvorbo prvo pismo.
Torej keykey [0], je le prva črka ne glede na niz imava,
smo poteka v.
Mi smo pretvarjanje, da zgornji del, in smo se odšteje s velikimi črkami A,
zato vse, kar počne nam daje številne
v katerem bomo lahko izbrskali naše vrednote na.
>> In potem bomo vrne hash VELIKOST modul.
Bodite zelo, zelo previdni ker, teoretično, tu
tvoj hash vrednost je lahko neskončno.
To lahko samo pojdi naprej in naprej in naprej.
To bi bilo nekaj res, Res velika vrednost,
ampak zato, ker vaše hash tabelo, ki ki ste jo ustvarili ima samo 26 indeksov,
želite, da vaš modulusing tako da boste
ne run-- je isto stvar kot vaš queue--
tako da vam ne zmanjka off dno vašega hash funkcijo.
>> Hočeš, da ga ovijte nazaj okoli na enak način, v [neslišno], če
ste imeli kot zelo, zelo velika črka, ki jih
niso želeli, da bi Samo nogama konec.
Ista stvar tukaj, boste želeli, da poskrbite, ne nogama konec embaliranje
približno na vrhu tabele.
Torej, to je samo zelo preprosto funkcijo razpršitve.
Vse, kar si je vzeti prvi pismo o kakršnikoli našega vhoda je
in pa, da je v indeksu, ki lahko bi dal v naše hash tabelo.
>> Ja, tako kot sem rekel prej, način, da bomo rešili trčenja
v našem hash so mize, ki ima, kaj pravimo, veriženje.
Torej, če boste poskušali vstaviti multipla Besede, ki se začnejo z isto stvar,
boste morali en hash vrednost.
Avokado in jabolko, če ste ga vodijo skozi našo hash funkcijo,
se dogaja, da bi vam enako število, število 0.
In tako način, kako rešiti, da je da bomo lahko dejansko nekako povežejo
skupaj preko povezanih seznamov.
>> In tako v tem smislu, vidva lahko vidite vrste
kako podatkovne strukture, ki smo bili predhodno nastavitev
kot rozin povezan seznam naravi za lahko pridejo skupaj v eno.
In potem si lahko ustvarite daleč bolj učinkovite podatkovne strukture
da zmorem večje količine Podatki, ki dinamično spreminjanje velikosti, odvisno
na vaše potrebe.
Vsakdo jasno?
Vsakdo nekako jasno, o tem, kaj se dogaja tukaj?
>> Če sem želel insert-- kaj je sadje, ki se začne z, ne vem,
B, razen jagod, banana.
>> OBČINSTVO: Blackberry.
>> ANDI PENG: Blackberry, blackberry.
Kje blackberry gre tukaj?
No, pravzaprav niso razporejene še to, vendar teoretično
če bi želeli imeti to po abecednem vrstnem redu,
kje naj blackberry iti?
>> OBČINSTVO: [neslišno]
>> ANDI PENG: Točno, potem tukaj, kajne?
Ampak, ker je zelo težko reorder-- Mislim, da je do vas.
Vidva lahko popolnoma izvajati, kar hočeš.
Bolj učinkovit način to početje morda
bi bilo razvrstiti vaše povezana seznam v abecednem vrstnem redu,
in tako, ko ste vstavljanje stvari, ki jih želite
biti prepričani, da jih vstavite v abecednem vrstnem redu
tako da potem, ko ste poskušam jih iskati,
nimate za prečkanje vse.
Točno tam, kjer veš, je, in to je lažje.
>> Ampak, če boste nekako morali Stvari vrinjeni naključno,
ste še vedno dogaja, da imajo da je prečkanje nekako.
In zato, če sem hotel samo vstavite blackberry tukaj
in sem hotel iskati da, vem, oh, blackberry
se mora začeti z indeksom 1, tako da sem vem, sprašuje samo iskanje na 1.
In potem sem lahko nekako prečkala povezan seznam
dokler ne pridem do BlackBerry, in then-- ja?
>> OBČINSTVO: Če ste poskušali create-- Mislim, da, kot je to zelo preprost hash
funkcija.
In če smo želeli storiti več plasti te všeč,
OK, želimo ločiti v kot vse abecedne črk na
in potem spet rad še en niz abecednih črk znotraj, da
smo dajanje kot hash miza v hash tabele,
ali kot funkcije v odvisnosti?
Ali je that--
>> ANDI PENG: Torej vaš hash function-- svoje razpršene tabele
lahko tako velika, kot si želite, da bi.
Torej, v tem smislu sem mislil je bilo zelo enostavno, zelo
enostavno za mene, da nekako temelji na črkami prvo besedo.
In tako da je le 26 možnosti.
Lahko dobim samo 26 možnosti od Od 0 do 25 let, saj lahko le
začeti od A do Ž, ampak če si hotel dodati, morda, več kompleksnosti
ali hitreje teči čas, da vaš hash tabele, morate nujno
lahko storite vse vrste stvari.
Lahko naredite sami enačba, ki vam daje
več distribucija v vašem besede, potem ko iščete,
to se dogaja, da se hitreje.
>> To je povsem odvisno od vas fantje kako želite izvesti to.
Pomislite na to kot samo vedri.
Če sem hotel imeti 26 žlice, jaz grem
razvrstiti stvari v teh vedri.
Ampak jaz grem, da imajo kup stvari v posamezne segmente,
tako da, če želite, da jo hitrejše in učinkovitejše,
Naj imajo sto veder.
>> Ampak potem moraš razbrati način, da razvrstite stvari, tako da so
v ustrezno vedro morajo biti.
Ampak potem, ko ste dejansko želeli videti na tej vedro,
to je veliko hitreje, ker obstaja manj stvari v posamezne segmente.
In tako, ja, to je dejansko trik za vas v pset5
je, da se boste izzvani, da samo ustvariti
karkoli je najučinkovitejši Funkcija si lahko zamislite, da bi
lahko shranite in preverite te vrednote.
>> Popolnoma do vaju pa hočeš to storiti,
ampak to je res dobra točka.
Ta vrsta logike želim, da začnete razmišljati o
je tudi, zakaj ne naredim več veder.
In potem moram iskati zmanjšane za stvari, in potem pa sem
imajo drugačno funkcijo razpršitve.
>> Ja, tam je veliko načinov, da to storijo pset, nekateri so hitrejši od drugih.
Jaz sem popolnoma bomo šele videli, kako hiter je bil najhitrejši vidva bo
lahko dobili svoje funkcije za delo.
OK, vsi dobro na veriženje in hash tabele?
To je dejansko všeč zelo preprosta koncept, če mislite o tem.
Vse, kar je, je ločevanje karkoli vaši vložki so v vedra,
njihovo razvrščanje in preiskujejo navaja, da je tam povezana s.
>> Cool.
V redu, sedaj imamo različne vrste strukture podatkov, ki se imenuje drevo.
Pojdimo naprej in govori o poskusih ki so izrazito drugačen,
vendar pa v isti kategoriji.
V bistvu, vse je drevo namesto organizacije podatkov v linearno
da ste hash tabela does-- Veste, to je dobil top in dno
in potem si nekako povezati off it-- a Drevo ima top, ki ga imenujemo koren,
in potem ima liste vse okoli njega.
>> In tako vse, kar imamo tukaj je samo vrh vozlišče
ki kaže na drugih vozlišč, da točke na več vozlišč, in tako naprej in tako naprej.
In tako boste morali delitev vej.
To je samo drugačen način organiziranja podatkov, in ker smo to drevo klic,
vidva just-- je samo vzoru ven videti kot drevesa.
To je razlog, zakaj ga imenujemo drevesa.
>> Hash tabela izgleda mizo.
Drevo samo izgleda kot drevo.
Vse, kar je še posebna način organiziranja vozlišč
odvisno od tega, kakšne so vaše potrebe.
>> Torej imate korenine in potem imate liste.
Tako, da smo lahko še posebej pomislite, da je binarno drevo,
binarno drevo je samo posebna vrsta drevesa
kjer vsako vozlišče le točke da, na max, dva druga vozlišča.
In tako da tukaj imate razlikuje simetrija v drevo
ki omogoča lažje nekako pogledati po kakšni ceni ste, ker potem ste
še vedno levo ali desno.
Nikoli ni kot levi tretjina od levo ali četrti z leve.
To je samo imate levo in pravico in lahko iščete eno od teh dveh.
In zakaj je to koristno?
Tako, da je to koristno je, če iščete
iskanje po vrednotah, kajne?
Namesto izvajanju binarno iskanje v vrsto napak,
če boste želeli, da bi lahko vstavite vozlišč in odnese vozlišč po svoji volji in tudi
ohranitev iskanje Zmogljivosti binarnega iskanja.
Torej, na ta način, da smo nekako tricking-- se spomniš, ko smo
je dejal, povezani seznami ne more binarno iskanje?
Mi smo nekako ustvariti podatkovno strukturo da trikov, da v delovni.
>> In zato, ker povezani seznami so linearne, so le povezati eno za drugo.
Lahko vrste imajo drugačna vrsta kazalcev
ki kažejo na različnih vozlišč ki nam lahko pomaga pri iskanju.
In tako sem, če sem hotel imajo binarno iskalno drevo,
Vem, da je moj sredini, če 55 let.
Jaz sem le, da bo ustvaril, da kot moj sredini, kot je moj koren,
in potem bom imel Vrednosti spin off od tega.
>> Torej, tukaj, če grem za iskanje vrednost 66, lahko začnem pri 55.
To je 66 večja od 55?
Ja je, zato sem vedel, da sem mus iskanje i n pravica kazalec tega drevesa.
Grem do 77.
OK, je 66 manj kot ali večji od 77?
To je manj kot, tako da boste vedeli, oh, da mora biti v levo vozlišče.
>> In tako da tukaj smo nekako ohranjanja vse od velikih stvari o nizi,
tako kot dinamično spreminjanje velikosti predmetov, pri čemer je
lahko vstavite in brisanje po svoji volji, ne da bi morali skrbeti fiksni
Količina prostora.
Še vedno ohraniti vse te čudovite stvari
hkrati pa lahko, da se ohrani log in iskanje čas binarnega iskanja
da smo bili prej samo lahko dobili besedno zvezo.
>> Cool podatkovna struktura, vrsta zapletene za izvajanje, vozlišče.
Kot lahko vidite, vse to je struct vozlišča
je, da imate levo in pravica kazalec.
To je vse, kar je.
Torej, ne samo ima x ali prejšnja.
Imate levo ali desno, in nato jih lahko nekako povezati
Vendar pa se tako odločijo.
>> OK, smo dejansko dogaja vzemite nekaj minut.
Tako smo šli nazaj.
Kot sem že rekel, Nekako sem razložil
logika, kako smo bi preiskava skozi to.
Bomo poskušali pseudocoding to gledat
če bomo lahko nekako velja Ista logika binarnega iskanja
za drugačno vrsto podatkovne strukture.
Če hočete, da bi kot par minut, da le razmišljati o tem.
V REDU.
V redu, bom dejansko samo vam the-- ne,
bomo govorili o psevdokoda prvi.
Torej, ali ima kdo rad dati stab, kaj
prva stvar, ki jo želite storiti, ko ste začeli ven Iskanje je?
Če iščemo vrednost 66, kar je
prva stvar, ki jo želite storiti, če želimo binarno iskati to drevo?
>> OBČINSTVO: Želite videti v redu in poglej levo in videli [neslišno]
večje število.
>> ANDI PENG: Ja, točno.
Torej boš pogled na vaše korenine.
Obstaja veliko načinov, kako lahko kličete to, vaši starša ljudje pravijo.
Rad bi rekel, koren, ker da je kot koren drevesa.
Greš pogledati svoj koren vozlišče, in vi ste
bomo videli, je 66 večja ali manjša od 55.
In če je večji od, dobro, da je večja kot, kjer ne želimo iskati?
Kje želimo iskati zdaj, kajne?
Želimo, da iskanje po Desna polovica tega drevesa.
>> Torej imamo priročno, A kazalec, ki kaže na desno.
In tako potem lahko nastavite naš novi koren, da bo 77.
Mi lahko samo iti kamorkoli kazalec je obrnjena.
No, oh, tu začenjamo na 77, in bomo lahko samo
To storite tako rekurzivno znova in znova.
Na ta način se nekako od imajo funkcijo.
Imate način iskanja, ki vas Lahko samo ponovim znova in znova in znova,
odvisno od tega, kje želite iskati dokler ne boste na koncu dobili z vrednostjo
ki iščete.
Ima smisel?
>> Sem približno razkazati vi dejansko kodo, in to je veliko kode.
Ni potrebe, da znorela.
Pogovorila se bova skozi to.
>> Pravzaprav ne.
To je bila samo psevdokoda.
OK, to je bil šele psevdokoda, ki je nekoliko zapletena,
ampak to je povsem v redu.
Vsakdo po skupaj tukaj?
Če je korenina je nična, vrnitev false saj to pomeni
nimate ničesar, tudi tam.
>> Če koren je n vrednost, tako da, če je zgodi, da je tista, ki jo gledaš,
potem boš vrnil true saj veste, da ste jo našli.
Ampak, če je vrednost manjša od korena n, ste
gre za iskanje levo otrok ali levo krilo,
karkoli hočeš, da ga pokličete.
In če je vrednost večja od korena, boš poiskati pravo drevo,
potem samo zaženite funkcijo z iskanjem znova.
>> In če je korenina null, da je ta pomeni, ko ste prišli do konca?
To pomeni, da nimate več več listov za iskanje,
potem veste, oh, jaz Verjetno je ni tukaj
ker ko sem pogledal skozi cela stvar in je ni tukaj,
da le ne bi bilo tukaj.
>> Ali, da je smiselno, da vse?
Torej, to je kot binarnem iskanju ohranjanje Zmogljivosti povezanih seznamov.
Ohladimo in tako drugi tip od vas strukture podatkov fantje
Lahko poskusite izvajanju na vašem pset, morate le izbrati eno metodo.
Toda morda alternativna metoda za hash tabele je tisto, čemur pravimo trie.
>> Vse je trie je je posebna vrsta drevesa, ki
ima vrednote, ki gredo do drugih vrednot.
Torej, namesto da binarna drevo v smislu, da je samo eden
stvar, ki se lahko kaže na dvoje, lahko imate ena stvar, ki kažejo na mnogo, mnogo stvari.
Vi v bistvu imajo nize znotraj katerega shranite
kazalci, ki kažejo na druge nizi.
>> Torej vozlišče, kako smo bi definirati Trie
se hočemo imeti Boolean, c beseda, kajne?
Torej je vozlišče Boolean kot resnična ali neresnična,
najprej na čelu da matrika, je to beseda?
Drugič, želite imeti kazalce da karkoli so ostali od njih.
Le malce zapleteno, malo abstraktno, ampak Bom razložil, kaj to vse pomeni.
>> Torej tod na vrhu, če ti imajo niz razglašena že,
vozlišče, kjer imate Boolean Vrednost shranjene na prednjem
da vam pove, je to beseda?
Ali to ni beseda?
In potem imate preostanek svojega polja, ki
dejansko shranjuje vse možnosti, kaj bi lahko bilo.
Tako, na primer, kot na vrhu imate
prva stvar, ki pravi, resnična ali false, da ali ne, to je beseda.
>> In potem imate 0 do 26 pisma, ki jih lahko shranite.
Če bi želel, da tu iskanje za bat, grem na vrh
in iščem B. najdem B v moji matrika, in zato vem, OK, je B beseda?
B ni beseda, tako da s tem Moram naprej iskati.
Grem od B, in gledam na kazalec, da je B opozarja proti
in vidim še eno vrsto informacij, enako strukturo, da smo imeli prej.
>> In here-- oh, naslednji pismo, v [neslišno] je A.
Torej gledamo v tej matriki.
Najdemo osmo vrednost, in potem pogledamo, da vidim, oh,
hej, je, da je beseda, B-A beseda?
To ni beseda.
Moramo ohraniti videti.
>> In tako potem pogledamo, kje kazalec točk A,
in kaže na drug način v ki imamo več vrednost shranjena.
In na koncu smo prišli do B-A-T, ki je beseda.
In tako naslednjič, ko pogledaš, boš
so, da je pregled, ja, to Boolova funkcija je res.
In tako v tem smislu, da sva nekako imajo drevo z nizi.
>> Torej potem lahko nekako iskanje navzdol.
Namesto razprševanja funkcijo in pripisovanje vrednosti, ki jih povezani seznam,
lahko samo izvaja načrt trie, ki išče downwords.
Res, res zapleteno stvari.
Ni enostavno, da razmišljajo o tem, ker sem kot pljuvanje toliko podatkovne strukture ven
na vas, vendar ne vse vrste razumeti, kako logika to deluje?
>> OK kul.
Torej B-A-T, in nato boš iskati.
Naslednjič, ko boš da vidim, oh, hej, to je res,
Tako vem, da to mora biti beseda.
>> Ista stvar za živalski vrt.
Torej, tukaj je stvar prav zdaj, če bomo želel iskati živalskem vrtu, prav zdaj,
Trenutno zoo ni Beseda v našem slovarju
saj, kot lahko vi vidite, prvo mesto, da imamo Boolean
return true, je na koncu zoom.
Imamo Z-O-O-M.
>> In zato je tu, ne bomo dejansko beseda, živalski vrt, v našem slovarju
ker je to polje se ne preverja.
Torej računalnik ne vemo, da je živalski vrt beseda
ker je način, ki smo jih ga shranijo, le zoom tukaj
dejansko ima logično vrednost ki je bila obrnil res.
Torej, če želimo, da vstavite beseda, zoo, v našem slovarju,
Kako bi šel o tem?
Kaj moramo storiti, da poskrbite, da naši Računalnik ve, da je Z-O-O beseda
in ne prva beseda je Z-O-O-M?
>> OBČINSTVO: [neslišno]
>> ANDI PENG: Točno, smo želite zagotoviti, da ta
tukaj, da Boolova vrednost odkljukali, da je res.
Z-O-O, potem bomo, da preveri, tako da smo točno vedeli, hej, zoo je beseda.
Bom povedati računalnik, da je beseda tako
da ko pregledi računalniške, ve, da je živalski vrt beseda.
>> Ker se spomniš vseh teh podatkov strukture, je zelo enostaven za nas
reči, oh, bat je beseda.
Zoo je beseda.
Zoom je beseda.
Toda, ko ste ga gradi, računalnik nima pojma.
>> Tako da boste morali natančno povedati v katerem trenutku je to beseda?
Na kateri točki je ni beseda?
In na kateri točki storiti I morali iskati stvari,
in na kateri točki moram iti naprej?
Vsakdo jasno, da je?
Cool.
>> In tako potem pride problem, kako bomo
iti okoli vstavljanje nekaj da je dejansko ni tam?
Torej, kaj je pravkar rekel želimo vstaviti beseda, kopel, v naši trie.
Kot lahko Vi vidite kot sedaj vse, kar imamo zdaj, je B-A-T,
in ta nova struktura podatkov tam imela vrček, ki
opozoril na nič, ker smo prevzeti da, oh, ni besed po B-A-T,
zakaj moramo ohraniti ob stvari po tem T.
>> Ampak problem nastane, če vas bomo storili želijo imeti besedo, ki prihaja po
T-jev.
Če imate kopel, ste dogaja, da želijo pravico H.
In tako pot bomo za to, da je bomo ustvarili ločen vozlišče.
Nismo dodeli ne glede na količino pomnilnika za to novo paleto,
in bomo prerazporedijo kazalce.
>> Bomo dodelite H, First of all, to null,
bomo znebili.
Bomo imeli navzdol, se točka H.
Če vidimo H, smo ga želeli iti kam drugam.
>> In tukaj, lahko nato preverite off ja.
Če bomo zadeli H po T, oh, potem vemo, da je ta beseda.
Boolean se bo vrnil res.
Vsakdo jasno, o tem, kako se je to zgodilo?
V REDU.
>> Torej v bistvu vse Te podatkovne strukture
da smo šli čez danes, nimam res, res hitro šli nad njimi
in ne za veliko podrobnost, in to je v redu.
Ko začnete zajebavam z njo, boste
sledenja, kjer vsi kazalci so,
kaj se dogaja v vašem podatkovne strukture, et cetera.
Ti bo zelo koristno, in to je do vas,
fantje popolnoma ugotovimo, kako želite izvajati stvari.
>> In tako pset4, od 5--, da je oh narobe.
Pset5 je pravopisne napake.
Kot sem že prej povedal, da boš, ko spet prenesete izvorno kodo od nas.
Tam se dogaja, da so tri glavne Stvari boste prenesli.
Boste prenos slovarjev, lenih in besedil.
>> Vse te stvari so se bodisi slovarji besed
da želimo, da preverite ali testiranje informacij
da želimo, da preverjanje črkovanja.
In tako slovarji smo vam gredo
da vam dejanske besede, ki jih želimo da si nekako shranite na način, ki je
bolj učinkovita kot array.
In potem besedila so bo tisto, kar smo
vas prosim, da natančno preverite, vse besede so resnične besede.
>> In tako so trije bloki programi, ki vam bomo dajejo
se imenujejo dictionary.c, dictionary.h in speller.c.
In tako vse dictionary.c pa je kaj ste morali izvajati.
To obilje besed.
To črkovati ček njih, in omogoča, da da vse, kar je pravilno vstavljen.
>> diction.h je le knjižnica datoteka da izjavlja, vse te funkcije.
In speller.c, bomo, da vam.
Vam ni treba spremeniti katerega od njega.
Vse speller.c pa je vzel, obremenitve je, nadzira hitrost njej,
testi merilo všeč, kako hitro ste sposobni narediti stvari.
>> To je Speller.
Samo ne igraš z njim, vendar se prepričani, da boste razumeli, kaj to počne.
Mi uporabljamo funkcijo imenovano getrusage da testira učinkovitost vašega urok
skladiščnik.
Vse to pa je v bistvu preskusu z Čas vsega v vašem slovarju,
zato poskrbite, da boste razumeli.
Bodite previdni, da se ne igraš z njim, ali drugje stvari ne bo deloval pravilno.
>> In večino tega izziva je za vidva res spremeniti dictionary.c.
Bomo, da vam 140.000 besed v slovarju.
Bomo, da vam tekst datoteka, ki ima te besede,
in želimo si, da bi lahko organizirali jim v hash tabele ali trie
ker ko smo vas prosimo, da urok check-- zamisliti, če ste urok
preverjanje, kot Homerjeve Odiseje.
To je kot ta velik, velik test.
>> Predstavljajte si, če vsak beseda, ki jo je moral pogledati
skozi paleto 140.000 vrednot.
To bi trajalo celo večnost za vaš stroj teči.
To je razlog, zakaj želimo organizirali Podatki v bolj učinkovitih podatkovnih struktur
kot je hash tabele ali trie.
In potem vidva lahko nekako kdaj iščete dostop
stvari lažje in hitreje.
>> In zato bodite previdni, da se odpravite trčenja.
Boš dobil kup od besed, ki se začnejo z A.
Boš dobil kup besed ki se začnejo z B. Do vas
Fantje, kako želite, da ga rešiti.
Morda je še več učinkovite funkcije razpršitve
kot samo prvo črko nekaj, in da je do vas
fantje nekako storiti karkoli hočeš.
>> Morda želite dodati vse črke skupaj.
Morda boste želeli, da je všeč delati čudne stvari da se upošteva število črk,
karkoli.
Do vaju kaj želite storiti.
Če želite narediti hash tabelo, če vas želeli poskusiti Trie, povsem odvisno od vas.
Jaz vas bo opozoril pred časom, da je trie je običajno nekoliko težje
samo zato, ker tam je veliko več kazalci slediti.
Ampak popolnoma do vas.
To je veliko bolj učinkovito v večini primerov.
Hočeš, da res lahko obdržali Spremljajte vse vaše napotke.
Tako kot to isto stvar da sem delal tu.
Ko poskušate vstaviti Vrednosti v hash tabele ali izbrisati,
se prepričajte, da ste Res sledenja
kje je vse, ker to je res enostavno, če sem
poskušajo vriniti kot besede, Andy.
Naj samo povem, da je to resnična beseda, beseda, andy,
v ogromen seznam A besed.
>> Če sem slučajno prerazporedijo kazalec narobe, oops,
tam gre celoto preostanek mojega povezani seznam.
Zdaj je edina beseda, I imeti, je andy, in zdaj
vseh ostalih besed v slovar je izgubila.
In tako želite poskrbite, da boste slediti vse vaše napotke
ali pa boš dobil velike težave v kodi.
Draw stvari previdno, korak za korakom.
To omogoča veliko lažje razmišljati.
>> In nenazadnje, želite, da bi lahko preizkusite svoje delovanje vašega programa
na veliki plošči.
Če vidva traja poglej CS50 prav zdaj,
imamo, kar se imenuje veliki svet.
To je ocena stanja najhitreje črkovalnik krat čez vse CS50
zdaj, mislim, da je vrh 10 krat Mislim, osem od njih so zaposleni.
Res želimo vama, da nas premagati.
>> Vse nas so poskušali izvesti najhitrejši kodo, kot je mogoče.
Želimo vama, da bi poskušali izzvati nas in izvajati hitreje od vseh nas
lahko.
In zato je to res prvič, da smo
vas prosi fantje narediti pset da lahko res v kakršni koli metodo
ti hočeš.
>> Vedno pravim, da je to bolj podobno k rešitvi resničnega življenja, kajne?
Sem rekel, hej, moraš to storiti.
Zgradite program, ki počne to za mene.
Ali jo pa hočeš.
Jaz samo vem, da želim na hitro.
To je vaš izziv za ta teden.
Vi fantje, gremo da vam nalogo.
Bomo, da vam izziv.
In potem je do vaju popolnoma samo ugotovimo,
kaj je najhitrejši in najbolj učinkovit način za izvedbo tega.
Ja?
>> OBČINSTVO: Ali smo dovolili, da če želel raziskovati hitrejše načine
narediti hash tabele na spletu, lahko storimo da, in navajajo številko nekoga drugega?
ANDI PENG: Ja, popolnoma v redu.
Torej, če vi prebrati spec, tam je linija
v spec, ki pravi, da fantje so popolnoma brezplačno za raziskave hash
Funkcije o tem, kaj so nekateri od hitrejše hash funkcij
teči stvari skozi kot Dokler si citirati to kodo.
Torej imajo nekateri ljudje že pogruntal hitre načine
početje črkovalniki, hitrega načini shranjevanja podatkov.
Popolnoma odvisno od vas, fantje, če vas želijo vzemite, kajne?
Prepričajte se, da ste navajanja.
Izziv tu res da smo poskušali preizkusiti
je zagotoviti, da veste svojo pot okoli kazalca.
Kolikor izvajanje dejanska funkcija hash
in prihaja do podobnih matematika za to,
vidva lahko raziskave karkoli Načini spletu hočete.
Ja?
>> OBČINSTVO: Lahko navedemo samo s pomočjo [neslišno]?
>> ANDI PENG: Ja.
Lahko samo v svoj komentar, lahko navedemo, kot so, oh,
vzeta iz bla, bla, bla, razpršilna funkcija.
Kdo še kakšna vprašanja?
Mi dejansko breezed skozi odsek danes.
Bom tukaj do odgovoriti na vprašanja, kot dobro.
>> Prav tako, kot sem rekel, za pisarne ure nocoj in jutri.
Spec ta teden, je dejansko super enostavno in zelo kratko, da se glasi.
Jaz bi predlagal ob poglej, samo prebrati skozi celoto njo.
>> In Zamyla dejansko vas popelje skozi vsako izmed funkcij
morate izvesti, in zato je zelo, zelo jasno, kako narediti vse.
Samo se prepričajte, da ste sledenja kazalcev.
To je zelo zahtevna pset.
>> To ni zahtevna, saj, kot so, oh, koncepti so toliko bolj
težko, ali pa boste morali naučiti toliko novih sintaksa pot
da si naredil za zadnje pset.
To pset je težko, ker obstaja toliko kazalci,
in potem je to zelo, zelo enostaven za enkrat imate napako v kodi ne bi mogli
najti, če je to bug.
>> In tako popolna in popolna vera v vas fantje, da bi lahko premagal našo [neslišno]
člankih.
Pravzaprav nimam nobenega pisnega rudnik še, ampak sem pisati mine.
Torej, medtem ko pišete tvoja, bom pisal rudnik.
Bom poskusil, da bi mine hitreje kot tvoje.
Bomo videli, kdo ima najhitrejši enega.
>> In ja, bom videl vse vidva tukaj v torek.
Bom teči nekakšno podobnega delavnici pset.
Vse to odsekov teden so pset delavnice,
tako da fantje imeli veliko priložnosti za pomoč, uradne ure kot vedno,
in res se veselim branje vseh kodo fantje.
Imam kvizi tukaj, če vas gor fantje želijo, da pride tistim.
To je vse.