[Powered by Google Translate] [Walkthrough - Problem Set 5]
[Zamyla Chan - Harvard University]
[To je CS50. - CS50.TV]
>> V redu. Pozdravljeni, vsi, in dobrodošli Walkthrough 5.
>> Pset5 je napačno črkovane besede, v kateri bomo izdelavo črkovalnik.
Črkovanje dama zelo pomembna.
Se je to že kdaj zgodilo?
Delaš zelo, zelo depoju na papir za spopad
in potem še na koncu dobili zelo svetijo Rade kot D ali D =
in zato, ker ste liverwurst spojler na kita široko besedo.
Ja, lektoriranje vaše paprike je stvar, izredno impotenca.
To je problem, ki vpliva na Manly, Manly študentov.
Bil sem nekoč povedal moj mučitelja razreda Sith, da ne bi prišli v dobri kolega.
In to je vse, kar sem si želela, da je vse, vsak otrok želi v moji starosti,
samo da bi prišel v dobri kolega.
In ne samo kakršne koli kolega. Ne želim iti v pravni kolega Slonokoščena.
Torej, če nisem izboljšanja, bi šel lahko moje sanje gre na Harvard,
Jale, ali zapor - saj veste, v zaporu, New Jersey.
Tako sem dobil sam črkovalnik.
To je malo odlomek iz enega od mojih najljubših umetnikov govorjene besede, Taylor Mali.
Kakorkoli že, kot pravi, treba imeti črkovalnika je zelo pomembno.
>> Torej, dobrodošli na Walkthrough 5, v kateri bomo govorili o pset5: zatipkanih besed,
v katerem bomo lahko kar samega črkovalnika.
Toolbox za ta teden, distribucija kodo, se bo treba pogledati
Samo razumeti različne funkcije, ki jih vaš slovar bo imel.
Mi smo dejansko dogaja, da se ob več. Files C, ki skupaj tvorijo naše pset.
In tako je videti skozi različne vidike, čeprav smo dejansko ne urejanje
eno od datotek, speller.c, ne vedo, kako se dela z zvezi z dictionary.c,
kar bomo pisali, se bo zelo pomemben.
Spec pset vsebuje tudi veliko koristnih informacij
glede stvari, ki jih lahko predvidevamo, pravila in stvari, kot je ta,
zato se prepričajte, da se glasi pset spec skrbno za nasvete.
In ko ste v dvomih norme ali kaj podobnega, potem pa se vedno sklicujejo na pset spec
ali Razprava.
Ta pset bo zelo odvisna od kazalcev,
zato želimo zagotoviti, da bomo razumeli razliko med dodajanjem zvezdic
pred imenom kazalca in ampersands, kako jih osvoboditi, itd
Torej bi kapitan kazalcev se bo zelo koristno za ta problem nizu.
Gremo pogledati v povezanih seznamih malo več,
kjer imamo elemente, ki ji pravimo vozlišča, ki imajo tako vrednost kot tudi kazalec
na naslednje vozlišče, in tako v bistvu povezuje različne elemente, enega za drugim.
Obstaja nekaj različnih možnosti izvajanja vašo dejansko slovar.
Gremo pogledati v dveh glavnih metod, ki so razpršene tabele, nato pa poskuša.
V obeh tistih, gre za neke vrste pojmom povezani seznam
kjer ste elemente povezane med seboj.
In tako bomo pogled nad tem, kako bi lahko bili sposobni delovati okoli povezanih seznamov,
jih ustvarjajo, upravljajo v smislu, kako se, na primer, vstavite vanj vozlišče
ali brez vseh vozliščih, kot tudi.
V smislu sprostitve vozlišč, da je zelo pomembno
da ko smo malloc pomnilnika, potem smo ga rešil.
Zato želimo zagotoviti, da poteka noben kazalec unfreed, da nimamo nobenih spomin razpoka.
Bomo uvesti orodje, imenovano Valgrind, ki teče svoj program
in preveri, ali vse pomnilnika, ki ga dodeli nato osvobodil.
Vaš pset le končana, ko deluje in ima polno funkcionalnost,
ampak Valgrind vam pove, da niste našli nobenih spomin razpoka.
Končno, pri tem pset, želim poudariti -
Mislim, kot ponavadi, sem definitivno zagovornik uporabe svinčnik in papir za tvoj problem sklopov,
ampak za tole, mislim, da je pero in papir, se bo še posebej pomembno,
če želite, da se pripravi puščice, da stvari, in razumeti, kako stvari delujejo.
Torej vsekakor poskušali uporabiti svinčnik in papir, da pripravi stvari, preden boste dobili kodiranje
saj bi lahko dobil malo grdo.
>> Najprej gremo v povezanih seznamih malo.
Povezani seznami so sestavljeni iz vozlišč, kjer je vsako vozlišče ima vrednost, povezano z njim,
kot tudi kazalec na naslednji vozel po njej.
Nekaj ​​stvari pomembnih povezanih s seznamov, da moramo zapomniti
kjer je naša prva vozlišče, nato pa, ko bomo vedeli, kje je prvi vozlišče,
na ta način lahko dostopate do vozlišča, ki so prvi vozlišče kaže na
in potem eno za to in tisto po tem.
In potem zadnji element v vašem seznamu je povezana vozlišča na kazalec
je vedno tekoč, da kaže na NULL.
Ko vozlišče točk na NULL, potem veste, da ste prišli do konca seznama,
vozlišče, da je zadnja, da ni nič po tem.
Tu v tem shematično, boste videli, da so puščice so kazalci,
in modri del, kjer je shranjena vrednost,
nato pa rdeče polje s kazalcem, to je vozlišče je kazalec
kaže na naslednje vozlišče po njej.
In tako si lahko ogledate tukaj, bi vozlišče D kaže na NULL, ker je zadnji element na seznamu.
>> Oglejmo si, kako lahko definiramo struct za vozlišče.
In ker želimo imeti več vozlišč,
to se dogaja, da postane typedef struct
v katerem bomo imeli več različnih primerkov vozlišč.
In tako smo jo opredeljuje kot novo vrsto podatkov.
Tu imamo typedef struct vozlišče.
V tem primeru imamo opravka s celo število vozlišč,
tako da imamo celoštevilsko vrednost imenom in potem imamo še kazalec,
in v tem primeru, je kazalec na vozlišče, tako da imamo struct * vozlišče, imenovano drugo.
In potem kličeš ta stvar vozlišče.
Poskrbite, da boste sledili tem sintakso.
Obvestilo, da vozlišče je pravzaprav navaja tam zgoraj, kot tudi pod zavitih oklepajih.
Potem, da bi spremljali, kje moj prvi vozlišče je v tem povezanega seznama,
potem imam vozlišče, imenovano kazalec glava in sem malloc prostora dovolj za velikost vozlišča.
Obvestilo pa je, da je vodja dejansko vozlišče kazalec v nasprotju z dejanskim vozlišču sama.
Torej glava dejansko ne vsebuje nobene vrednosti,
samo kar kaže na prvi vozel v mojem seznamu je povezano.
>> Da bi dobili boljšo predstavo o povezanih seznamov, saj je zelo pomembno,
slediti pazite, da boste ohranili verige,
Rad pomislim, da je ljudi v skladu držala za roke,
kjer je vsaka oseba, ki se držijo za roke z naslednjo.
Ne morete videti v tej risbi, ampak v bistvu oni kažejo na naslednjo osebo
, ki je v svoji verigi.
In tako, če želite, da prečkanje povezan seznam, kjer so ti ljudje -
predstavljate vse te ljudi, ki so vrednote, povezane z njimi
in opozarjajo tudi na naslednjo osebo v liniji -
Če želite prečkanje povezani seznam, na primer, bodisi urediti vrednosti
ali poiščite vrednosti ali kaj podobnega,
potem boste želeli, da kazalec na določeno osebo.
Torej bomo imeli podatkov kazalec tipa vozlišča.
Za ta primer, recimo, da kazalec.
Drug pogost način poimenovati to bi iterator ali kaj podobnega
ker je ponavljanjem več in dejansko premika, ki vozlišče, da je obrnjena k.
To bo tukaj naš kazalec.
Our kazalec se bo najprej opozoriti, da prvi element v našem seznamu.
In kaj želimo storiti, je, da bomo v bistvu se nadaljuje kazalec,
se gibljejo od strani do strani.
V tem primeru želimo, da se premaknete na naslednji element v seznamu.
Z nizi, kaj bi naredil, je, da bomo samo rekli, da smo povečali z indeksom 1.
V tem primeru, kaj moramo storiti, je dejansko bil oseba, ki je to trenutno kaže, da je oseba,
in da se bo naslednja vrednost.
Torej, če je kazalec le kazalec vozlišče, potem tisto, kar želimo narediti
je, da smo želeli, da bi dobili na vrednost, ki je kazalec kaže na.
Želimo, da pridete do te vozlišče in potem, ko smo že pri tem vozlišču, kjer je bil, da je obrnjena k.
Da bi prišli do dejanske vozlišču, da je kazalec kaže na,
Ponavadi jo kažejo z (* kazalec).
To bi vam dejansko vozlišče, ki je kazalec, ki kaže na.
In potem po tem, kaj želimo storiti, je, da smo želeli dostop
karkoli že to vozlišče prihodnjo vrednost.
To storite tako, da omogočajo dostop do vrednosti notranjost struct, imamo dot operaterja.
Torej bi bilo (* kazalec). Naslednjo.
Ampak to je malo grdo, v smislu, da imajo nosilce okoli * kazalec,
in tako smo zamenjati vso to izjavo z kazalec->.
To je pomišljaj in nato več kot znak, da postanejo puščico.
Kazalec-> naslednji.
To bo dejansko dobili vozlišče, da se kazalec kaže. Ta vrednost je naslednje.
Torej, namesto da bi zvezdo in piko, ti nadomešča s puščico.
Bodite zelo previdni, da se prepričajte, da ste poskušali uporabiti to sintakso.
>> Zdaj, ko imamo kazalec, če želimo dostopati do vrednosti,
preden smo imeli kazalec-> naslednji,
ampak za dostop do vrednosti na vozlišču, da je kazalec, ki kaže, da smo samo preprosto reči,
vozlišče-> vrednost.
Od tam je tipa podatkov Karkoli smo opredelili vrednote in vozlišč biti.
Če je int vozlišče, nato pa kazalec-> vrednost je le, da bo treba število.
Tako lahko naredimo delovati, da preverite equalities, mu dodelite različne vrednosti, itd
Torej, kaj želite storiti, če želite premakniti kazalec na naslednjo osebo,
ste dejansko spremembo vrednosti kazalca.
Ker je kazalec kazalec vozlišče, spremenite dejansko kazalec naslov
na naslov naslednjega vozlišča na vašem seznamu.
To je samo del kode, kjer lahko izbirate.
Če imam komentar nekaj storiti,
to je, če ste verjetno, da bo za dostop do vrednosti
ali pa kaj opraviti s tem posebnem vozlišču.
Če ga začnete, lahko rečem, da je moj kazalec na začetku
se dogaja, da kaže na prvi element v povezanem seznamu.
In tako se naprej, mi je opredeljeno kot vodja vozlišča.
>> Kot sem že omenil, sprostitev, je zelo pomembno.
Hočeš, da poskrbite, da boste sprostili vsak element na seznamu, ko ste končali z njo.
Ko vam ni treba, da sklicevanje koli od teh kazalcev več,
želite poskrbite, da boste sprostili vseh teh kazalcev.
Ampak hočeš biti zelo previdni tukaj, da želite izogniti spomin razpoka.
Če ste brez ena oseba predčasno, potem vse napotke, ki kaže na vozlišče, da se
se bodo izgubljeni.
Če se vrnemo k osebi, na primer, da bi bilo malo bolj high stakes,
imejmo teh ljudi, razen v tem primeru so lebdi nad jezerom s pošastjo.
Želimo zagotoviti, da ko smo sprostili, ne bomo izgubili
in spustite vseh vozlišč, preden smo jih dejansko osvobodil.
Na primer, če ste bili, da preprosto pokličite brezplačno na tega tipa tukaj,
potem bi ga osvobodili, potem pa bi bili vsi ti ljudje potem lahko izgubijo
in bi odtavaš in padel na tla.
Zato želimo zagotoviti, da namesto tega, da želimo ohraniti povezavo do ostalih.
Naš glavni kazalec, ki kaže na prvi element na seznamu.
To je nekako kot vrv, sidranje prvo osebo.
Kaj boste morda želeli storiti, ko sprostite seznam so se -
Če želite sprostiti prvi del, potem imate lahko začasno kazalec
, ki kaže, da ne glede na prvi element je.
Torej imate vaše začasno kazalec kaže tukaj.
Na ta način imamo drži prvo vozlišče.
In potem, saj vemo, da je prvi vozel se bo sprostil,
potem lahko gremo to vrv, to sidro, naše glave,
dejansko kažejo, da ne glede na prvi kaže, da.
Torej je to dejansko glava opozarja na drugem elementu zdaj.
Zdaj smo lahko osvobodi vse, kar je shranjeno v temp,
in da bomo lahko izbriše, da ne da bi ogrožali vseh drugih vozlišč v našem seznamu.
Drug način, da bi vam to lahko
vsakič, ko se le sprostiti zadnji element na seznamu
ker si zagotoviti, da ne bi opozoril na karkoli.
Torej bi lahko samo sprostiti tole, potem prosta 1, nato pa brez tega.
To vsekakor deluje, vendar je nekoliko počasneje, ker ga je narava povezanih seznamov,
ne moremo kar takoj skočiti na zadnji.
Moramo prečkati vsak element v povezanem seznamu
in preverite, ali da ena kaže na NULL, preverite vsakič,
in potem, ko pridemo do konca, nato pa brez tega.
Če ste bili do tega procesa, bi dejansko lahko tukaj preverjanje,
preverjanje, potem pa se preveri tukaj, je osvoboditev,
potem grem nazaj, preverjanje tukaj, preverjanje tukaj, je osvoboditev,
preverjanje tukaj, in ga nato sprostiti.
To traja malo več časa. Ja.
>> [Študent] Bi bilo možno, da bi povezani seznam, ki shranjuje izhodne kazalec do konca?
To bi vsekakor bilo mogoče.
Če želite ponoviti vprašanje, ali je mogoče, da so povezanega strukturo seznam
tako da imate kazalec, ki kaže na konec seznama, povezano?
Jaz bi rekel, da je to možno, in vsakič, ko nekaj vstavili v svojo povezano seznam
bi morali posodobiti, da kazalec in podobno.
Ti bi morali vozlišče * rep, na primer.
Toda, ko ste izvajanju te funkcije, boste morali razmišljati o kompromisov,
všeč, kolikokrat bom se ponavljanjem nad tem,
kako težko se bo slediti repa kot tudi glavo
kot tudi moja iterator, in stvari, kot je ta.
Ali to -? >> [Študent] Ja.
Možno je, ampak v smislu oblikovanja sklepov, morate pretehtati možnosti.
>> Tukaj je okostje kodo, da bi vam omogočajo, da osvobodi vse elemente v povezanem seznamu.
Še enkrat, ker sem ponavljanjem v povezanem seznamu, bom želijo imeti neke vrste kazalca
ali iterator.
Mi smo ponavljanjem, dokler kazalec NULL.
Vi ne želite, da izbirate, ko je kazalec NULL
ker to pomeni, da ni nič na seznamu.
Torej tukaj sem, da začasno vozlišče *
kaže na to, kar Razmišljam je prvi mojem seznamu,
in potem sem premakniti kazalko pred 1 in nato brezplačno, kar sem imela v začasnem skladišču.
>> Zdaj smo prišli do vstavite v povezanih seznamih.
Imam tri vozlišča v mojem povezanem seznamu in pojdimo z preprostem primeru
kjer želimo vstaviti drugo vozlišče ob koncu našega povezani seznam.
Da bi to dosegli, vse kar bi naredil, je pa bi prečkala
najti, kje trenutno konec povezanega seznama je, da kar vozlišče kaže na NULL -
da je to ena -
in potem pravijo, pravzaprav, ta ne bo zadnji vozel;
smo dejansko dogaja, da imajo še enega.
Tako bi imeli to trenutno eno točko za karkoli smo vstavljanje.
Torej, zdaj je to rdeča oseba, tukaj postane zadnji vozel v povezanem seznamu.
In tako je značilnost zadnjega vozlišča v povezanem seznamu je, da opozarja na NULL.
Torej kaj bi morali storiti, je nastaviti ta rdeča tip je kazalec NULL. Tukaj.
>> Toda kaj, če želimo vstaviti v vozlišče med drugim in tretjim enega?
Ta je ni tako preprosto, saj želimo zagotoviti,
da ne opustite vse vozlišča v našem povezani seznam.
Kaj bi morali storiti, je zagotoviti, da bomo zasidrali na vsakega.
Na primer, recimo to, da drugega.
Če si rekel, druga pa zdaj trdi, da to novo
in si je kazalec tam, da bi povzročila ta človek izgublja
ker ni nobene povezave z njim.
Namesto tega - bom pripraviti še enkrat. Oprostite mi umetniške sposobnosti.
Vemo, da ne moremo kar neposredno povezavo 2 na novo.
Moramo zagotoviti, da imamo na zadnjega.
Kaj lahko storite, je, da imajo začasni kazalec
elementu, ki se dogaja, da se doda naprej.
Torej imamo začasno kazalec tam.
Ker vemo, da je to tretji pa se hranijo spremljali,
2 Zdaj lahko povežete na našo novo.
In če ta novi rdeči fant se bo v času med 2 in 3,
potem kaj je ta tip je kazalec gre izpostaviti? >> [Študent] Temp.
Temp. Ja.
Torej ta rdeča tip je naslednja vrednost se bo temp.
Ko ste vstavite v povezanih seznamih, smo videli, da bi se
preprosto dodate nekaj do konca z ustvarjanjem začasno niz,
ali če bi želel dodati nekaj v sredini našega niza,
potem bi lahko malo bolj shuffling okoli.
Če želite, na primer, imajo urejen povezani seznam,
potem moraš nekako pretehtati stroške in koristi, ki
ker če želimo imeti urejen niz, to pomeni, da vsakič, ko vstavite vanj,
to bo trajalo malo več časa.
Vendar, če želite kasneje, kot bomo našli bomo želeli,
iskanje prek povezanega seznama, potem bi bilo lažje, če veš, da je vse v redu.
Torej boste morda želeli primerjati stroške in koristi tega.
>> Drug način, da vstavite v povezan seznam je vstaviti v samem začetku seznama.
Če potegnemo našo sidro tukaj - to je naša glava -
in potem so ti ljudje povezani z njim,
in potem imamo novo vozlišče, ki se vstavi v začetku,
potem, kaj bi radi, da naredim?
Kaj bi bilo narobe s samo povedati hočem povezati rdečo modro,
ker je to prva?
Kaj bi se zgodilo tukaj?
Vse od teh treh se bo izgubil.
Zato ne želimo storiti.
Spet smo se naučili, da moramo imeti neke vrste začasno kazalca.
Naj odločijo za začasno točko do tega tipa.
Potem lahko imamo modro eno točko za začasno
in nato rdeča točka za modro.
Razlog, zakaj sem s pomočjo ljudi tukaj, ker smo prepričani, da želite vizualizirati
zadrževanje ljudi in zagotoviti, da imajo povezavo do njih
preden se znebimo drugo roko ali kaj podobnega.
>> Zdaj, ko imamo občutek, povezanih seznamov - kako bi lahko ustvarili povezano seznam
in oblikovanje struktur za to je sestavljena iz vrste opredelitve za vozlišče
nato pa se prepričajte, da imamo kazalec na čelu te povezane seznam -
ko bomo imeli to in vemo, kako za prečkanje pričajo,
dostop do različnih elementov, vemo, kako vstaviti, in vemo, kako se osvoboditi,
potem bomo lahko v pravopisne napake.
Kot ponavadi, smo del vprašanj, ki se boste uporabili za poslovanje s povezanimi seznami
in različne strukture, kot so čakalne vrste in lonce.
Potem lahko gremo v napačno zapisanih.
>> Pravopisnih je v distribucijski oznako nekaj datotek pomena.
Najprej opazimo, da imamo to Makefile tukaj,
ki nismo zares prišlo prej.
Če bi pogledali v notranjost pset5 mapo, ki ste jo opazili, da imate datoteko. H,
potem imate dve c datoteke..
Kaj to Makefile pa je prej, bi lahko samo tip in nato ime programa
in potem bomo videli vse te trditve in zastav sprejet v prevajalnik.
Kaj Makefile pa je, nam omogoča, da zbere več datotek hkrati
in prenesti v zastavami, ki jih želimo.
Tukaj smo videli tam glavo datoteke tukaj.
Potem smo dejansko imajo dva izvornih datotek.
Imamo speller.c in dictionary.c.
Vabimo vas, da uredite Makefile, če želite.
Obvestilo, da tukaj, če vnesete čisto, kaj potem počne, je dejansko odstrani ničesar
da je jedro.
Če imaš Napaka pri razčlenjenosti, v bistvu si dobil njegove posmrtne ostanke.
Tako bo ta grdi mali datoteka se pojavi v vašem imeniku, imenovano jedro.
Boste želeli odstraniti, da bi bilo čisto.
To odstrani vse exe datoteke in. O datoteke.
>> Oglejmo si v dictionary.h.
Ta pravi, da razglasi zbirko funkcionalnost.
Imamo največjo dolžino za vsako besedo v slovarju.
Pravimo, da se bo najdaljša možna beseda. To je dolžine 45.
Torej mi ne bo imela nobenih besed, ki presegajo to dolžino.
Tukaj imamo samo funkcijskih prototipov.
Nimamo dejansko izvajanje, ker to je tisto, kar bomo lahko delaš za to pset.
Toda kaj to počne, je, ker imamo opravka z večjimi datotekami tukaj
funkcionalnost in v večjem obsegu, je koristno imeti h datoteko.
tako da se lahko nekdo bere ali z uporabo kode razumeti, kaj se dogaja.
In morda želijo izvajati poskusi, če si hash tabele ali obratno.
Potem bi rekel moj obremenitve funkcijo,
dejansko izvajanje bo razlikujejo, vendar to prototip ne bo spremenila.
Tukaj smo preveriti, ki vrne true, če je dana beseda v slovarju.
Potem imamo tovor, ki v bistvu traja v slovarju datoteke
in ga naloži v neko strukturo podatkov.
Imamo velikosti, ki je, ko je poklical, vrne velikost slovar
koliko besed so shranjene v njej,
in potem razkladanje, ki sprosti vse pomnilnika, ki ste jih prevzeli
pri tem pa svoj slovar.
>> Oglejmo si dictionary.c.
Vidimo, da je videti zelo podobna dictionary.h, razen zdaj pa le ima vse te todos v njej.
In da je tvoje delo. Sčasoma boste izpolnite speller.c z vso to kodo.
Dictionary.c, ko se izvaja, v resnici ni storila ničesar,
tako da se ozremo speller.c za prikaz dejanskega izvajanja črkovalnik.
Čeprav vam ne bo treba urejati vse te oznake,
je pomembno, da brati, razumeti, ko je obremenitev poklicala, ko kličem pregled,
samo da bi razumeli, ga načrtovati, kako funkcija deluje.
Vidimo, da je preverjanje za pravilno uporabo.
V bistvu, ko nekdo teče speller, to pomeni, da je to neobvezno
za njih, da preide v slovarju datoteke, ker se bo v privzeti slovar datoteko.
In potem je treba iti v besedilu, da je črkovanja preveriti.
rusage se ukvarja s časom, saj je del tega pset ki ukvarjali se bomo s kasneje
ne samo pridobivanje delovanje črkovalnika delo
ampak dejansko dobili, da bi bilo hitro.
In tako je to, če rusage se dogaja, da pridejo noter
Tukaj smo videli prvi klic na enega od naših dictionary.c datoteke, ki je tovor.
Obremenitev vrne resnična ali neresnična - res odvisna od uspeha, lažnih ob izpadu.
Torej, če je slovar ni pravilno vstavljen, se bo vrnil speller.c 1 in zaprete.
Toda, če ne obremenitve pravilno, nato pa se bo nadaljevalo.
Še naprej in vidimo nekaj datoteko I / O tukaj,
kjer se dogaja, da se ukvarjajo z odpiranjem besedilno datoteko.
Tukaj je, kaj to počne, je črkovanja preveri vsako posamezno besedo v besedilu.
Torej, kaj speller.c počne tukaj je nad vsakim ponavljanjem besed v besedilno datoteko
in jih nato preveri v slovarju.
Tu imamo logičnim napačno črkovano, da bodo videli, če prijava vrne resnična ali ne.
Če je beseda dejansko v slovarju, potem se bo prijava return true.
To pomeni, da beseda ni napačno črkovana.
Zato bi bilo napačno zapisano napačno, in zato imamo pok, navedba.
Mi naprej dogaja, potem pa beleži, koliko napačno črkovane besede
obstajajo v datoteki.
Še naprej je na in arhivira.
Potem sem pa poroča, koliko napačno črkovane besede, ki jih je imela.
Komisija je izračunala, koliko časa je trajalo, da naložiti slovar,
koliko časa je trajalo, da preveri,
koliko časa je trajalo, da izračun velikosti,
ki morajo biti, bomo šli naprej, je zelo majhna,
in nato, koliko časa je trajalo, da raztovarjanje slovar.
Tukaj gor nad vidimo poziv tukaj raztovoriti.
Če želimo preveriti velikost tukaj,
potem vidimo, da je tukaj poziv velikosti, kjer se določa velikost slovarja.
Neverjetno.
>> Naša naloga za to pset je izvajanje obremenitev, ki bo nalaganje slovar
Struktura podatkov - kar boste izbrali, bo to razpršena tabela ali poskusiti -
z besedami iz slovarja datoteke.
Potem imate velikosti, ki vrne število besed v slovarju.
In če se izvaja tovor v pameten način, potem bi morali biti velikost precej enostavno.
Potem ste preverjanje, ki bo preveril, če je dana beseda v slovarju.
Torej speller.c prehaja v nizu, nato pa boste morali preveriti, ali je ta niz
se nahaja v vašem slovarju.
Opazimo, da smo na splošno imajo standardne slovarjev,
vendar v tem pset, v bistvu vse slovar sprejet v katerem koli jeziku.
Torej ne moremo preprosto sklepati, da beseda je notri.
Beseda foobar je lahko opredeljen v določenem slovarju, ki se peljemo noter
In potem smo raztovoriti, ki osvobaja zbirko iz spomina.
>> Prvič, rad bi šel čez haše metodo tabele
o tem, kako bi morali izvajati vseh teh štirih funkcij,
in potem bom šel čez poskuša način, kako se izvajajo te štiri funkcije,
in na koncu govori o nekaj splošnih nasvetov, če ste izdelavo pset
in tudi, kako bi lahko bili lahko uporabila Valgrind za preverjanje pomnilnika pušča.
>> Pojdimo v razpršitve metodo tabele.
Razpršena tabela zajema seznam segmentov.
Vsaka vrednost, vsako besedo, da bo šel v eno od teh segmentov.
Razpršena tabela idealno enakomerno porazdeli vse te vrednosti, da ste potujejo
in jih nato napolni v vedro, kot da vsak žlica
ima približno enako število vrednosti v njem.
Struktura za hash tabelo, imamo niz povezanih seznamov.
Kaj moramo storiti, je, ko se peljemo v vrednosti, potrebno preveriti, če je ta vrednost pripada,
ki žlica pripada, nato pa jo postavite v povezano seznamu povezano s tem vedro.
Tukaj, kar imam, je hash funkcija.
To je int razpršena tabela.
Torej, za prvega segmenta, vse cela pod 10 šel v prvo vedro.
Vse cela nad 10, vendar pod 20 šel v drugo,
in potem tako naprej in tako naprej.
Zame je vsaka žlica zastopa te številke.
Vendar pa je rekel, da je bilo treba iti 50, na primer.
Zdi se, kot da prvi trije vsebuje vrsto 10 številk.
Ampak jaz želim, da bi moja razpršena tabela, da se v kakršnikoli cela števila,
tako da bi potem morala tudi, da izločijo vse številke nad 30 v zadnjem vedro.
In tako potem bi to imelo za posledico neke vrste neuravnovešenega hash tabele.
Če ponovimo, razpršena tabela je le niz žlic
kjer je vsak žlica povezani seznam.
In tako ugotoviti, kje vsako vrednost gre, kar gre v vedro,
boste želeli, kar se imenuje funkcijo razpršitve
da se vrednost, nato pa pravi, da je ta vrednost ustreza določenemu vedro.
Torej, tam zgoraj, v tem primeru moj hash funkcija je vsako vrednost.
Zato je preverila, ali je bilo manj kot 10.
Če bi bil, bi ga dal v prvo vedro.
Preveri, ali je manj kot 20, ga spravlja v 2. če je to res,
preveri, če je manj kot 30 let, nato pa ga spravlja v tretjem vedro,
in potem vse ostalo samo pade na četrto vedro.
Torej, ko ste vrednost, vaša funkcijo razpršitve
bo potekala to vrednost v ustrezno vedro.
Razpršilna funkcija v bistvu mora vedeti, koliko žlic imate.
Vaš razpršena tabela velikost, število segmentov, ki jih imate,
da se bo določeno število, ki je odvisno od vas, da se odločite,
vendar pa se dogaja, da se določeno število.
Torej vaš razpršilna funkcija se bo zanašal na to, da določi, katere žlica vsak ključ gre v
tako, da je ni enakomerno porazdeljeno.
Podobno kot pri našem izvajanju povezanih seznamov, zdaj vsako vozlišče v hash tabelo
se dejansko dogaja, da ima tip sloj.
Torej imamo char niz imenovano besedo in nato še kazalec na naslednje vozlišče,
kar je smiselno, saj bo v povezani seznam.
Se spomniš, ko smo povezani seznami, naredil sem vozlišče * imenovano glavo
, ki je kazal na prvo vozlišča v povezanem seznamu.
Toda za naš hash tabele, saj imamo več povezanih seznamov,
hočemo želimo naša razpršena tabela, da bi izgledal "Kaj je vedro?"
Žlica je samo seznam vozlišč kazalcev,
in zato je vsak element v vedru je dejansko kaže na njeno ustrezno povezani seznam.
Če se želite vrniti na to shematično, boste videli, da so same žlice puščice,
ne dejanska vozlišča.
Ena od bistvenih last hash funkcij, ki si jih deterministična.
To pomeni, da vsakič, ko hash številka 2,
mora vedno vrne isto vedro.
Vsak znesek, ki gre v hash funkcijo, če bi se ponovil,
je, da se isti indeks.
Torej vaš hash funkcija vrne indeks niz
kadar ta vrednost pripada.
Kot sem že omenil, se določi število veder,
in tako bo indeks, da se vrnete mora biti manjše od števila segmentov
vendar večji od 0.
Razlog, zakaj imamo hash funkcijo, namesto da samo z enim samim povezan seznam
ali en sam niz je, da želimo, da bi lahko skočil do določene točke najlažje
če vemo, značilne vrednosti -
namesto da bi morali iskati po celotnega slovar
da lahko skoči na določen del tega.
Vaš hash funkcijo je treba upoštevati, da je idealno,
vsaka žlica ima približno enako število tipk.
Ker je razpršena tabela je serija povezanih seznamov,
potem povezani seznam sami pa bodo morali več kot eno vozlišče.
V prejšnjem primeru dveh različnih številk, čeprav niso bili enaki,
ko je zgoščen bi vrnili isti indeks.
Torej, če ste se ukvarjajo z besedami, eno besedo, ko zgoščen
bi bila enaka vrednost razpršitve, kot drugo besedo.
To je tisto, čemur pravimo trčenja, ko imamo vozlišče, da se pri zgoščene,
povezani seznam v tem vedru ni prazna.
Tehnika, ki jo imenujemo ni linearna sondiranje,
če greš v povezanem seznamu in poiščite mesto, kamor želite vstaviti, da je vozlišče
ker imaš trčenje.
Vidite lahko, da bi lahko prišlo do kompromisa, kajne?
Če imate zelo malo razpršene tabele, zelo majhno število veder,
potem boste imeli veliko trčenj.
Ampak potem, če ste se zelo veliko razpršene tabele,
ste verjetno, da bo zmanjšanje trkov,
vendar bo še zelo velika struktura podatkov.
Prišlo bo kompromisi s tem.
Torej, ko delaš svoje pset, poskusite igral
Mogoče bi med manjše razpršene tabele
potem pa se zavedamo, da bo trajalo nekoliko dlje, da prečkanje različne elemente
od teh povezanih seznamov.
>> Kaj obremenitev bo naredil, je ponovitev čez vsako besedo v slovarju.
Poteka v kazalec na datoteko slovarju.
Torej boš izkoristil spisa I / O funkcije, ki jih obvlada v pset4
Ponovil in nad vsako besedo v slovarju.
Hočeš vsako besedo iz slovarja, da postane novo vozlišče,
in ti boš, da se vsak od teh vozlišč znotraj vašega strukture slovarju podatkov.
Vsakič, ko dobite novo besedo, veste, da se dogaja, da postane vozlišče.
Torej, lahko greš takoj in malloc vozlišče kazalec za vsako novo besedo, ki jo imate.
Tukaj bom poklical mojo new_node vozlišča kazalca in sem mallocing kaj? Velikost vozlišče.
Nato se glasi dejansko niz iz datoteke, ker je dejansko skladiščena slovar
z besedo in nato novo linijo, kar lahko izkoristimo
je funkcija fscanf,
pri čemer je datoteka slovar datoteka, ki smo opravili v,
tako da skenira datoteko za niz in kraji, ki vrvice v zadnji argument.
Če se spomnim nazaj na enem od predavanj, ko smo se odpravili v
in vrsta olupljen plasti nazaj v knjižnico CS50,
smo videli izvajanje fscanf tam.
Če se želite vrniti fscanf, imamo datoteko, ki smo branje iz,
iščemo niz v tej datoteki, nato pa smo, da ga postavite v
Tukaj imam new_node-> besedo, ker new_node je vozlišče kazalec,
Ne dejansko vozlišče.
Potem sem rekel new_node, želim iti na vozlišče, da se kaže, da
in nato določite, da vrednost besedo.
Želimo, da bi potem to besedo in jo vstavite v hash tabelo.
Zavedam se, da smo new_node vozlišče kazalec
ker bomo želeli vedeti, kaj je naslov tega vozlišča je
ko ga vstavite v ker je struktura vozlišč samih, o struct,
je, da imajo kazalec na novo vozlišče.
Torej, kaj je naslov tega vozlišča dogaja izpostaviti?
Ta naslov se bo new_node.
Ali ima to smisel, zakaj delamo new_node vozlišče * za razliko od vozlišča?
Ok.
Imamo besedo. Ta vrednost je new_node-> beseda.
, Ki vsebuje besedo iz slovarja, ki ga želite vhodu.
Torej, kaj želimo narediti, je, da smo želeli poklicati svojo funkcijo razpršitve na tem nizu
saj je naš hash funkcija se v nizu in se nato vrne nam celo število,
če to celo, če je indeks Hashtable na ta indeks predstavlja, da vedro.
Želimo, da to kazalo, nato pa pojdite na to indeksu hash tabele
in nato uporabite, da povezani seznam dodati vozlišče v new_node.
Ne pozabite, da pa se odločite, da vstavite vaše vozlišče,
ali je v sredini, če želite, da ga rešiti
ali na začetku ali na koncu, le poskrbite, da vaše zadnje vozlišče vedno obrnjen na NULL
ker je to edini način, da bomo vedeli, kje je zadnji element našega seznama je povezano.
>> Če je velikost, ki predstavlja celo število besed v slovarju,
Nato eden od načinov za to je, da kadar se imenuje velikost
gremo skozi vsak element v našem hash tabele
in potem Ponovil skozi vse povezano seznam v tabeli razpršitve
in nato izračunati, koliko, da povečuje našo števec 1 do 1.
Ampak vsakič, ko se imenuje velikost, da se bo to trajalo dlje časa
saj bomo linearno biti sondiranje vsak povezani seznam.
Namesto tega se bo veliko lažje, če bi spremljali, koliko besed so opravili noter
Torej, če ste tudi števec v vašem obremenitve funkcijo
da posodobitve, kot je potrebno, potem števec, če jo nastavite na globalne spremenljivke,
bodo mogli dostopati po velikosti.
Torej, kaj lahko naredite enostavno velikost je v eni vrstici, le vrne protivrednost,
velikost slovarja, ki ste jih že obravnava v breme.
To je tisto, kar sem mislil, ko sem rekel, če izvajajo obremenitev na koristen način,
potem velikost se bo zelo enostavno.
>> Torej, zdaj smo dobili pregled.
Zdaj imamo opravka z besedami iz vhodne datoteke z besedilom,
in tako bomo lahko preverili, ali vse te besede vhodnih
dejansko v slovarju ali ne.
Podobno Scramble, želimo, da se omogoči neobčutljivosti primera.
Hočeš, da poskrbite, da po vseh besedah ​​sprejet, čeprav si malimi črkami,
ko je klical z primerjanje nizov, sta enakovredna.
Besede v slovarju besedilne datoteke so dejansko vse male črke.
Druga stvar je, da lahko predpostavimo, da je vsaka beseda izrečena, vsak niz,
se bo bodisi po abecedi ali vsebujejo opuščaje.
Opuščaje se bodo veljavni besede v našem slovarju.
Torej, če govorim z opuščajem S, ki je dejansko legitimno beseda v vašem slovarju
da se dogaja, da je eden od vozlišč v vašem hash tabele.
Preverite, če deluje z besedo ne obstaja, potem je dobil, da je v naši hash tabele.
Če je beseda v slovarju, potem pa vse besede v slovarju so v hash tabele,
tako da je pogled na te besede v hash tabelo.
Vemo, da je, odkar smo izvajali svojo funkcijo razpršitve
tako, da je vsak edinstven beseda vedno zgoščen na enako vrednost,
potem vemo, da namesto da bi iskali s pomočjo našega celotnega hash tabele,
lahko dejansko našli povezan seznam, da bi ta beseda pripada.
Če bi bilo v slovarju, potem bi bilo v tem vedru.
Kaj lahko storimo, če je beseda ime našega niza, sprejeto leta,
smo lahko le hašiš, da beseda in pogled na povezanem seznamu
na vrednost Hashtable [razpršitve (beseda)].
Od tam, kaj lahko storimo je, da imamo manjše podmnožice vozlišč za iskanje te besede,
in da bomo lahko prečkala povezanega seznama z uporabo primera iz prej v walkthrough,
nato pa klic niz primerjati na besedo, kjer je kazalec kaže na,
ta beseda, in videli, ali so primerjati.
Glede na način, ki ga organizira svojo funkcijo razpršitve,
če je to razporejene, bi morali imeti možnost, da vrne false nekoliko prej,
če pa je neurejeno, potem pa želite še naprej vozijo prek povezanega seznama
dokler ne boste našli zadnji element seznama.
In če še vedno niste našli besedo, ko ste zaključili povezanem seznamu
To pomeni, da vaša beseda ne obstaja v slovarju,
in da beseda ni pravilna,
in bi morala prijava vrne false.
>> Zdaj smo prišli do raztovoriti, če želimo, da osvobodi vse vozlišča, ki smo malloc'd,
tako brez vseh vozlišč znotraj našega hash tabele.
Bomo želeli ponoviti čez vse, povezanih seznamov in brez vseh vozlišč v to.
Če pogledaš zgoraj v walkthrough na primer takrat, ko smo sprostili povezan seznam,
potem boste želeli ponoviti ta postopek za vsak element v hash tabelo.
In jaz bom šel čez to proti koncu walkthrough,
ampak Valgrind je orodje, kjer lahko vidite, če ste pravilno osvobodili
vsako vozlišče, ki ste jih malloc'd ali karkoli drugega, ki ste jih malloc'd, katero koli drugo kazalec.
Torej, to je razpršene tabele, kjer imamo končno število segmentov
in razpršilna funkcija, ki bo vrednost in nato določite, da vrednost določenega segmenta.
>> Zdaj smo prišli do poskusa.
Poskuša vrste zgleda takole, jaz pa bom tudi potegnili zgled.
V bistvu, imate celo paleto možnih črk,
in potem, ko ste izgradnjo besedo,
ta dopis je mogoče povezati v slovarju za široko paleto možnosti.
Nekaj ​​besed začeti s C, nato pa še z,
drugi pa še z O, na primer.
Trie je način za ponazoritev vse možne kombinacije teh besed.
Trie bo slediti zaporedja črk, ki sestavljajo besede,
odcepil, če je to potrebno, če se lahko ena črka sledi večkratnik pisem,
in na koncu kažejo na vsaki točki, ali je ta beseda veljavna ali ne,
ker če ste črkovanje besedo MAT, MA Ne verjamem, da je veljavna beseda, ampak MAT.
In tako v vašem Trie, bi bilo navedeno, da po tem, ko MAT, da je dejansko veljavna beseda.
Vsako vozlišče v naši Trie se dejansko dogaja, da vsebuje niz vozlišč kazalcev,
in bomo imeli, še posebej, 27 od teh vozlišč kazalcev,
ena za vsako črko v abecedi, kot tudi Opuščaj značaja.
Vsak element v tem polju se bo sama, da kaže na drugo vozlišče.
Torej, če je vozlišče NULL, če ni nič po tem,
potem vemo, da ni nobenih nadaljnjih pisem v ta besedna zveza.
Ampak če je vozlišče ni NULL, kar pomeni, da obstaja več črk v tem dopisu zaporedju.
In potem prav, vsak vozel označuje, ali je to zadnji znak v besedi ali ne.
>> Pojdimo v primer za Trie.
Najprej moram prostor za 27 vozlišč v tem polju.
Če imam besedo BAR -
Če imam besedo BAR in želim dodati, da,
prva črka je B, tako da če mi Trie je prazna,
B je druga črka v abecedi, zato bom odločite, da to tukaj na tem indeksu.
Jaz bom imel B tukaj.
B se bo vozlišče, ki kaže na drugo paleto vseh mogočih likov
, ki lahko sledijo po pisnem B.
V tem primeru, sem se ukvarjajo z napisom BAR, tako da bo tukaj gre.
Ko imam pismo R, potem je zdaj točke za svojo kombinacijo,
in potem bo R tukaj.
BAR je popolna beseda, zato pa bom, da imajo raziskave kažejo na drugo vozlišče
, ki pravi, da je ta beseda velja.
To vozlišče se tudi dogaja, da imajo niz vozlišč,
vendar pa bi bilo tistih NULL.
Ampak v bistvu, lahko še naprej tako.
To bo malo bolj jasno, ko bomo šli v drug primer,
tako da samo tam nosijo s seboj.
Zdaj imamo BAR znotraj našega slovarja.
Zdaj pravijo, da imamo besedo BAZ.
Začeli smo z B, in že imamo B, kot eno izmed pisem, ki jih je v našem slovarju.
To je sledila z A. Imamo že.
Potem pa namesto tega imamo Z naslednjo.
Torej element v našem polju se bo Z,
in tako potem bo nihče izpostaviti drugo veljavno koncu besede.
Tako vidimo, da ko bomo nadaljevali z B, nato pa,
obstajata dve različni možnosti trenutno v našem slovarju za besede, ki se začnejo s črko B in A.
Povejte smo želeli vstaviti besedo foobar.
Potem bi naredimo vstop na F.
F je vozlišče, ki opozarja na celo vrsto.
Radi bi našli O, pojdite na O, O, nato povezave do celotnega seznama.
Mi bi morali B in nato nadaljujte, bi imeli, nato pa R.
Torej foobar prehaja vso pot navzdol, dokler ne foobar ni prava beseda.
In tako potem bi to bila veljavna beseda.
Zdaj pravijo, naša naslednja beseda v slovarju, je pravzaprav beseda FOO.
Mi bi rekli, F. Kaj sledi F?
Pravzaprav sem že prostor za O, tako da bom še naprej.
Ne rabim, da bi novo. Nadaljuj.
FOO je veljavna beseda v tem slovarju, tako da potem bom navesti
, da je veljavna.
Če se ustavim svoj zaporedje tam, bi bilo to pravilno.
Ampak, če bomo nadaljevali zaporedje od Foo do B
in prav je FOOB, FOOB ni beseda, ki je ni navedena kot veljaven.
V Trie, ki ste jih vsako vozlišče pove, ali je beseda velja ali ne,
in nato vsak vozel ima tudi niz 27 vozlov kazalcev
ki pokažite na vozlišč sami.
>> Tukaj je način, kako bi želeli določiti to.
Vendar pa, tako kot v primeru hash tabele, kjer smo imeli vozlišče * glavo
, ki označuje začetek naše povezan seznam, bomo tudi dogaja, da želijo
nek način vedeli, kje začetek našega Trie je.
Nekateri ljudje pravijo poskuša drevesa, in to je, če prihaja od korena.
Zato želimo naše korenine drevesa, se prepričajte, da bomo ostali ozemljeni
povsod, kjer smo Trie je.
Smo že nekako šla čez
Tako boste lahko mislil nakladanje vsako besedo v slovar.
V bistvu, za vsako besedo, ki jo boste želeli ponoviti skozi Trie
in vemo, da vsak element pri otrocih - smo poklicani, da otroci v tem primeru -
ustreza drugo pismo, boste želeli preveriti te vrednote
v tistem indeksa, ki ustreza dopisu.
Tako razmišljanje vso pot nazaj k cesarju in Vigenere,
vedoč, da ima vsaka črka, ki jo lahko nekako zemljevidu nazaj na indeks abecednem,
Zagotovo A do Z se bo zelo enostavno preslikati v abecednem pismu,
ampak na žalost, opuščaje tudi sprejet znak v besedi.
Nisem prepričan, kaj ASCII vrednost,
tako da za to, če želite, da bi našli kazalo, da odloči, ali želite, da je bodisi prvi
ali zadnja, boste morali, da bi težko kodirane ček, ki
, nato pa, da je v indeksu 26, na primer.
Torej ste preverjanje vrednosti otroke [i]
kjer je [i], kar ustreza črka ste.
Če je to NULL, kar pomeni, da trenutno ni na morebitne črke
izhajajo iz tega zaporedja prejšnjega, tako da boste želeli, da malloc
in narediti novo vozlišče in imate, da otroci [i] opozarjajo na to
tako da boste ustvarili - ko smo vstavili pismo v pravokotniku -
ki otrokom ne NULL in točka v tej novi vozlišče.
Ampak, če to ni NULL, kot v našem primeru foo
ko smo že foobar, bomo še naprej,
in smo se nikoli ne bi novo vozlišče, ampak le določa, da res is_word
Na koncu te besede.
>> Torej tako kot prej, saj tu imate opravka z vsakim pismom, v času,
to bo lažje za vas, za velikost, namesto da bi izračun
in iti skozi celotno drevo in izračunajte, koliko otrok imam
in potem odcepil, se spomnimo, koliko so na levi in ​​na desni strani
in take stvari, to se dogaja, da je veliko lažje za vas
če ste le slediti, koliko besed ste ga dodali v
ko imate opravka s tovorom.
In tako potem lahko na ta način velikost samo vrnitev globalno spremenljivko velikosti.
>> Zdaj smo prišli preveriti.
Enakimi standardi, kot prej, ko želimo omogočiti neobčutljivosti primera.
Kot je dobro, predpostavimo, da so strune le črki ali opuščaje
ker otrok je niz 27 dolgo,
tako da vse črke abecede plus Opuščaj.
Za preverite, kaj boste želeli storiti, je, da boste želeli, da začnete pri korenu
ker bo koren kažejo na matriko, ki vsebuje
vseh možnih začetnih črk besede.
Boš tam začeti,
in potem boš preverite to vrednost NULL ali ne,
ker če je vrednost NULL, kar pomeni, da je slovar nima vrednosti
, ki vsebujejo ta dopis, v tem posebnem vrstnem redu.
Če je NULL, potem to pomeni, da je beseda napačno črkovana takoj.
Ampak, če to ni NULL, potem pa lahko nadaljujete,
pravijo, da je prva črka je možna prva črka v besedi,
tako da zdaj hočem, da preverite, če je druga črka, da zaporedje, je v mojem slovarju.
Torej boš šel z indeksom otrok prvega vozla
in preverite, ali je to drugo pismo obstaja.
Nato ponovite ta postopek za preverjanje, ali je to zaporedje veljavna ali ne,
v vašem Trie.
Kadar so otroci v vozlišče, ki indeksnih točkah na NULL,
veš, da zaporedje ne obstaja,
potem pa, če pridete do konca besede, ki ste jih vnesejo,
potem boste želeli preveriti, zdaj sem končal to zaporedje
in ugotovil, da je v moji Trie je, da beseda velja ali ne?
In tako potem želite preveriti, in takrat, če ste ugotovili, da je zaporedje
potem boste želeli preveriti, ali je ta beseda veljavna ali ne,
saj se spomnite nazaj v prejšnjem primeru, ki sem narisal, kjer smo imeli FOOB,
da je veljavna zaporedna ki smo jo našli, vendar ni bila dejansko veljavna beseda sama.
>> Podobno velja za raztovarjanje v poskusih, ki jih želite razkladanje vseh vozlišč v vašem Trie.
Žal mi je. Podobno kot hash tabele kjer raztovarjanje smo osvobojeni vseh vozlišč,
V poskusih, ki jih želimo tudi osvobodi vse vozlišč.
Razbremenite se bo dejansko delajo najlažji od spodaj navzgor
ker so v bistvu povezani seznam.
Zato želimo zagotoviti, da imamo na vseh vrednot
in brez vseh njih eksplicitno.
Kaj boste želeli storiti, če delate z Trie
je, da potujejo na dnu in prosti najnižjo možno vozlišče 1.
in nato šel na vse tiste otroke, nato pa brez vseh tistih,
pojdi gor in nato brezplačno, itd
Nekako tako kot se ukvarjajo s spodnjim plasti Trie 1.
nato pa bo do vrha, ko ste osvobodili vse.
To je dober primer, kjer bi lahko rekurzivna funkcija prišla prav.
Ko ste osvobodili spodnja plast vašega Trie,
potem pokličete na razkladanje ostalega območja,
pazite, da boste sprostili vsak mini -
Lahko nekako vizualiziramo, da kot mini poskusih.
Torej imate korenine tukaj.
Jaz sem samo to poenostavi tako da mi ni bilo treba poseči 26 izmed njih.
Torej imate to, potem ti predstavljajo zaporedja besed
če vse te majhnih krogih so črke, ki so veljavni zaporedja črk.
Naj še samo malo več.
Kaj boste želeli storiti, je brezplačna dno tukaj in nato prosta 1
in nato brezplačno ta na dnu, preden si brezplačno vrhnjo 1 tukaj
ker če vas brezplačno nekaj v drugem nivoju tukaj,
potem bi dejansko izgubil to vrednost tukaj.
To je razlog, zakaj je pomembno za razkladanje Trie in se prepričajte, da boste sprostili na dnu prve.
Kaj boste morda želeli storiti, je rekel za vsako vozlišče
Želim razložiti vse otroke.
>> Zdaj, ko smo šli čez raztovoriti za hash metodo mizo, kot tudi način Trie,
bomo želeli videti na Valgrind.
Valgrind zaženete z naslednjimi ukazi.
Imate valgrind-V.
Saj kontrolo za vse puščanja pri zagonu speller saj je to določeno besedilo
ker speller potrebuje v besedilno datoteko.
Tako bo Valgrind zaženete program, vam povedati, koliko bajtov se dodelijo,
koliko bajtov se sprosti, in to vam bo povedal, ali ste osvobodili ravno dovolj
ali pa nisi dovolj prosto,
včasih lahko celo preveč svobodno, kot je brezplačen vozlišče, ki je že osvobojena
in tako se bo vrnil vam napake.
Če uporabljate Valgrind, se vam bo nekaj sporočil
navedbo, ali ste osvobojeni ali manj kot dovolj, ravno dovolj,
ali več kot dovolj časa.
>> Del tega pset, je opcija za izpodbijanje veliko tablo.
Toda, ko imamo opravka s temi podatkovnih struktur
to je zabavno videti, kako hitro in kako učinkovito bi bilo vaše podatkovne strukture.
Ali vaš hash funkcija za posledico veliko trčenj?
Ali je vaš obseg podatkov zelo velika?
Ali je potrebno veliko časa za prečkanje?
V dnevniku speller, za pisanje, koliko časa boste uporabili za nalaganje,
Za preverjanje, vodenje velikosti in razkladanje,
in tako so tisti, objavljene v velikem svetu,
kjer lahko tekmujejo sošolci
in nekateri uslužbenci bi videli, kdo je najhitrejši črkovalnik.
Ena stvar, ki bi rad vedite o hash tabele
je, da obstaja nekaj zelo preprostih zgostitvene funkcije, ki bi lahko mislimo.
Na primer, da imate 26 veder, in zato je vsaka žlica
ustreza prvo črko v besedi,
ampak da se bo to povzročilo precej neuravnotežen hash tabele
ker obstaja veliko manj besed, ki se začnejo z X od začetka z M, na primer.
Eden od načinov, da gredo o speller je, če želite, da bi dobili vse druge funkcionalnosti navzdol
potem pa uporabite preprosto funkcijo razpršitve, da bi lahko dobili kodo teče
nato pa pojdite nazaj in spremeni velikost razpršilne tabele in opredelitev.
Obstaja veliko virov na spletu za hash funkcij,
in tako za to pset si dovoliti, da raziskave hash funkcije na internetu
Za nekaj namigov in navdih, dokler ste prepričani, da navedejo kje ste jo dobili od.
Vabljeni, da si razlagajo in nekaj funkcijo razpršitve, ki ga najdete na internetu.
Nazaj, da boste morda lahko videli, če je nekdo uporabil Trie
ali je njihovo izvajanje hitreje kot vaš hash tabelo ali ne.
Lahko pošljete na veliko tablo večkrat.
To bo posneti zadnji vnos.
Mogoče ste spremenili funkcijo razpršitve in nato ugotovili, da je dejansko veliko hitreje
ali veliko počasneje kot prej.
To je malo na zabaven način.
Vedno je 1 ali 2 uslužbenci, ki poskušajo narediti čim najpočasneje zbirko,
tako da je vedno zabavno gledati.
>> Uporaba za pset je naletite speller z dodatnim slovarju
in potem obvezno besedilna datoteka.
Privzeto, ko zaženete speller s samo besedilne datoteke in ne določajo zbirko,
to se dogaja, da uporabite datoteko slovarja besedila, velik 1
v mapi cs50/pset5/dictionaries.
To je ena je več kot 100.000 besed.
Imajo tudi majhno zbirko, ki ima precej manj besed
da CS50 je za vas.
Vendar pa je lahko zelo enostavno samo, da svojo zbirko
Če si želite, da bodo delali v manjših primerov -
na primer, če želite uporabljati gdb in veš posebne vrednosti
, ki želite, da vaš razpršena tabela začrtati k.
Tako si lahko naredite svojo besedilno datoteko samo z barom, Baz, Foo, in foobar,
da to v besedilno datoteko, ločiti tiste, vsak z 1 linijo,
in nato naredite svojo besedilno datoteko, ki vsebuje le dobesedno morda 1 ali 2 besedi
tako da boste točno vedeli, kaj bi bilo izhod.
Nekatere besedilne datoteke vzorcev, da bo Veliki svet je ob zagonu preverite izziv
so Vojna in mir ter roman Jane Austen ali nekaj takega.
Torej, če ste začeli ven, je to veliko lažje narediti svoje besedilne datoteke
ki vsebujejo le nekaj besed ali morda 10
tako da lahko napovedati, kaj bi rezultat
nato pa preverite pred, da je to bolj nadzorovano primer.
In zato, ker imamo opravka z predvidevanje in risanje stvari okoli,
Ponovno bi rad, da uporabite svinčnik in papir
ker se v resnici dogaja, da vam pomaga s tem 1 -
risanje puščic, kako hash tabele ali kako Trie izgleda,
ko boš sprostila nekaj, kjer puščice se dogaja,
se držiš na dovolj, vidiš vse povezave izginjajo
in ki spadajo v brezno ušli spominu.
Zato vas prosimo, poskusite pripraviti stvari, še preden prideš do pisanja kode navzdol.
Risanje stvari, tako da boste razumeli, kako stvari gredo na delo
ker potem vam zagotavljam, da boste naleteli na manj pokvari kazalec tam.
>> V redu.
Želim vam želim veliko sreče s tem pset.
To je verjetno najtežje.
Torej, poskusite začeti zgodaj, pripravi stvari, pripravi stvari, in veliko sreče.
To je bilo Walkthrough 5.
>> [CS50.TV]