>> ZAMYLA CHAN: Naredimo črkovalnik.
Če odprete speller.c, potem boste videli da je večina Funkcionalnost
preverjanje besedilno datoteko proti Slovar je že za vami.
. / Speller, ki poteka v slovarju besedilu datoteko in nato še besedilna datoteka,
bo preveril, ali besedilno datoteko proti slovarju.
>> Zdaj bo slovarja besedilne datoteke vsebujejo veljavnih besede, enega v vsako vrstico.
Potem speller.c bo poklical Load v slovarju besedilno datoteko.
To bom poklical funkcijo imenovano Preveri vsaka beseda v vnesenega besedilno datoteko,
tiskanje vseh napačno črkovane besede.
>> Speller.c bo tudi pokličete na velikost določitev števila besed
slovar in pokličite raztovoriti da sprostite pomnilnik.
speller.c bodo tudi spremljali, kako koliko časa se uporablja za izvajanje teh
procesi, vendar bomo to kasneje.
>> Torej, kaj moramo storiti?
Moramo izpolniti dictionary.c.
V dictionary.c, imamo pomočnika Funkcija Load, ki naloži
Slovar.
Preverite delovanje, ki preveri, če dana beseda v slovarju.
Funkcija Velikost vrne število besed v slovarju.
In končno, smo raztovoriti, ki osvobodi slovar iz spomina.
>> Torej, najprej, kaj je reševanje breme.
Za vsako besedo v slovarju besedilu Datoteka bo Load shranite te besede v
slovar struktura podatkov po vaši izbiri, bodisi
hash tabelo ali Trsta.
Jaz bom šel čez, tako v ta sprehod skozi.
>> Najprej pogovoriva o hash tabel.
Povejte, da ste imeli 10 biljard krogle in si želel, da jih shranite.
Vi bi jih lahko dal vse v vedro, in ko boste potrebovali specifično
oštevilčene žogo, ki ste jo vzeli eno iz vedra hkrati
je videti, da za žogo.
In s samo 10 žog, bi morali biti možnost, da bi našli svojo žogico v razumnem
časa.
>> Toda kaj, če si imel 20 jajc?
To lahko traja malo dlje zdaj.
Kaj pa 100?
1000?
Zdaj, bi bilo veliko lažje, če boste imeli več vedra.
Mogoče eno vedro žogic za oštevilčene nič skozi devet, drugi vedro za
kroglice oštevilčene 10 skozi 19, in tako naprej.
>> Zdaj, ko je potrebno poiskati specifične žoga, bi lahko samodejno
pojdite na eno posebno vedro in iskanje po tisto vedro.
In če ima vsaka žlica približno 10 žoge, potem lahko enostavno iskanje
skozenj.
>> Zdaj, ker imamo opravka z slovarji, ena žlica za
vse besede v slovarju bo Verjetno je veliko premalo vedra.
Tako da je lahko pogled na hash tabel.
>> Think of it kot niz vedrih.
In v tem primeru, vedra so naši povezani seznam.
In bomo razdelili vseh naših besed med temi več povezanih sezname
organiziran način s funkcijo razpršitve, ki nam bo povedal,
vedro določen ključ, saj beseda pripada.
>> Oglejmo predstavljajo to shematično.
Modre škatle tu vsebuje vrednosti in rdeče škatle na drugo točko vrednosti
kazalec par.
Poklicali bomo teh parov vozlišč.
Zdaj, vsak vedro, kot sem rekel, prej, je povezani seznam.
V povezanih seznamov, vsako vozlišče ima svojo vrednost, kot tudi kazalec
Naslednji vrednost.
>> Zdaj, ki se ukvarjajo s povezanimi sezname to je zelo pomembno, da
ne izgubijo nobenih povezav.
In še dejstvo, da se spomnimo, da zadnje vozlišče, če ne kažejo na
drugo vozlišče, kaže na null.
>> Torej, kako bomo to predstavljajo v C?
Definiramo našo zgradimo tukaj.
In vrednost je v tem primeru char array dolžine.
Dolžina plus 1, kjer je dolžina Največja dolžina katerokoli besedo, plus 1 za
null terminator.
In potem imamo kazalec drugo vozlišče se imenuje Naprej.
>> Torej, dajmo narediti majhen povezani seznam.
Najprej boste želeli malloc svoje vozlišče, ki ustvarjajo prostor v pomnilniku
velikost vašega tipa vozlišča.
In da drugo vozlišče, spet mallocing.
>> Zdaj, če želite dodeliti vrednost beseda, potem bi lahko rekli, node1 puščico
Beseda je enako "Hello". Ta puščica operater dereferences kazalec in
dostopi spremenljivke struct je.
Na ta način ne bomo morali uporabiti oboje dot in operater zvezda.
>> Torej imam Node2 arrow beseda je enaka »Svet«. In tam, da so vrednosti
poseljena v mojih vozlišč.
Če želite, da povezave, bom mimo v node1 puščico, dostop do vozlišča zvezdo,
da vozlišče kazalec, enaka Node2, kaže node1 za Node2 dva.
In tam imamo povezan seznam.
>> Tako da je bila le ena povezani seznam, vendar hash tabela je cela paleta
povezani seznam.
No, bomo imeli enako vozlišče strukturirati kot prej.
Ampak, če bi želeli dejansko razpršene tabele, potem bomo lahko le, da vozlišča kazalec
matrika tukaj.
Na primer, velikost 500.
>> Zdaj obvestilo, da se bo trgovanje off med velikostjo vašega
hash table in velikost vaših povezanih seznamov.
Če imate res veliko število vedra, si predstavlja, da bi morali teči nazaj
in tja v skladu z našli vedro.
Ampak tudi vi ne želite majhno število žlic, ker potem smo nazaj
prvotna problem, kako ob Preveč žog v naši vedro.
>> OK, ampak kje pa je naša žoga šla?
No, moramo najprej imajo žogo, kajne?
Torej, kaj je malloc vozlišče za vsako Nova beseda, ki jo imamo.
vozlišče * new_node Rezult malloc (sizeof (vozlišče)).
>> Sedaj, ko imamo to strukturo, smo Lahko skeniranje, s funkcijo
fscanf, niz iz naše dokumentacije, če to je slovar datoteka, v
new_node arrow beseda, kjer new_node arrow beseda je naša
cilj te besede.
>> Naprej bomo želeli, da hash Beseda uporabo funkcijo razpršitve.
Hash funkcijo prevzame niz in vrne indeks.
V tem primeru je indeks mora manj od števila
žlice, ki jih imate.
>> Zdaj, zgoščevalne funkcije, ko poskušate da bi našli enega, in ustvarili enega
svoje, ne pozabite, da so biti deterministična.
To pomeni, da ista vrednost mora preslika v žlico vsakič
da jo hash.
>> To je nekako tako kot v knjižnici.
Ko boste vzeli knjigo, ki temelji na avtor, veste, kateri polici bi morala
pojdi na to, ali je to število polica en, dva ali tri.
In da bo knjiga vedno spadajo na bodisi polica enega, dva ali tri.
>> Torej, če new_node arrow ima beseda Beseda iz svojega slovarja, potem
hašiš new_node arrow Beseda bo nam dajejo indeks
vedro razpršene tabele.
In potem bomo vstaviti, da v to specifično povezani seznam z navedeno
vrne vrednost našega hash funkcijo.
>> Oglejmo si primer vstavimo vozlišče v
začetek povezanega seznama.
Če glava je kazalec vozlišče, ki označuje začetek povezan
Seznam in new_node označuje novo vozlišče, ki ga želite vnesti v, samo
dodeljevanje glavo new_node bi izgubili Povezava na preostanek seznama.
Tako da ne želimo, da to storijo.
>> Namesto tega želimo zagotoviti da imamo na vsaki
single vozlišče v našem programu.
Torej teče new_node puščico Rezult glava in nato vodja enaka new_node
bodo ohranili vse povezave in ne izgubijo.
>> Toda kaj, če želite, da vaš seznam, ki bo razporejene, ker ima razporejene povezan
Seznam bi bilo lažje za ga iščejo kasneje?
No, za to, boste morali vedeti, kako za prečkanje povezanih seznamov.
>> Prečkanje povezan seznam, imejmo kazalec vozlišče, vozlišče *, da deluje kot
kazalec, ki označuje ki vozlišče ste na, začenši
na prvem elementu.
Zanka, dokler kazalec je nična, ne moremo izvajati določene procese in nato
napredovanje kazalec, ko moramo S pomočjo smernih arrow vrednost.
>> Ne pozabite, da je to ista stvar kot rekoč zvezda kazalec, Dereferenciranje
kurzor, nato pa z uporabo dot vrednost operater.
Torej posodobitev kazalec se z dodelitvijo kazalec na kazalec puščico.
>> Povejte, da ste ugotovili, da je D postane v med C in E. Če želite vstaviti vozlišče,
imajo new_node D pokažite vozlišče E, ki je kazalec dostavo.
In potem C, kazalec, lahko pokažite do D. Na ta način vzdržuje seznam.
Bodite previdni, da ne bi izgubili svoje povezave, ki jih premikanje kurzorja puščico D
takoj.
>> Vse je v redu.
Torej, to je, kako si lahko vstavite vozlišč, jih naložite, nalaganje besed na tiste,
vozlišč, in jih vstavite v vašem razpršene tabele.
Sedaj si oglejmo poskusih.
>> V Trsta, bo vsako vozlišče vsebuje matrika vozlišč kazalcev, enega za vsak
črka v abecedi plus opuščaj.
In vsak element v matriki bo opozorila na drugo vozlišče.
Če je to vozlišče je nična, potem to pismo se ne bo naslednja črka
vsaka beseda v zaporedju, ker vsak Beseda označuje, ali je to zadnji
značaj besedo ali ne.
>> Oglejmo shemo.
Upajmo, da se bodo stvari biti malo bolj jasno.
V tem diagramu vidimo, da le nekatere črke in nekatere podrejene
se navedeni ven.
Tako da lahko sledijo določenim poti, in vse te poti vas bo vodil do
različne besede.
>> Torej, kako bomo to predstavljajo v C?
No, vsako vozlišče sedaj se dogaja, da imajo Logična vrednost, ki pove, ali
da vozlišče konec dana beseda ali ne.
In potem bomo imeli tudi niz vozlišče kazalci se imenujejo otroci in
tam se bo 27 od njih.
In ne pozabite, da boste prav tako želeli slediti vaš prvi vozlišče.
Gremo na klic, da korenine.
>> Tako da je struktura Trsta.
Kako bomo to predstavljajo kot slovar?
No, preračunavanja besede v, za vsak slovar besedo, boste želeli
za ponovitev prek Trsta.
In vsak element pri otrocih ustreza drugačen pisma.
>> Torej, da preverja vrednost pri otrocih indeks i, kjer je i predstavlja
specifični indeks pismu, ki poskušate vstaviti.
No, če je nična, potem boste želeli, da malloc novo vozlišče in imeti otroke
i kažejo na to vozlišče.
>> Če ni nič, potem to pomeni, da da glede na podružnico, da je glede
podniz, že obstaja.
Torej boste le, da se premaknete na novo vozlišče in naprej.
Če ste na koncu besede, ki skušate naložiti v
slovar, potem lahko nastavite, da Sedanji vozlišče, da ste na true.
>> Zato si oglejmo primer vstavljanja Beseda "lisica" v našem
Slovar.
Pretvarjaj se, da začnemo z prazen slovar.
Prva črka F, ki se nahajata V indeksu otrok pet od korenin
otroci matrika.
Tako smo, da vstavite noter
>> Črka O bo nato pri otrocih indeks 15, po tem F. In potem X
bo še nižja, razvejane off otrok na Ö je.
In zato, ker potem X je zadnja črka besede "lisice", potem bom
zeleno barvo, ki kaže, da to je konec besedi.
V C, da bo nastavitev je Beseda boolean vrednosti prave.
>> Zdaj, kaj če Naslednja beseda, ki ste vložite v je beseda "foo"?
No, vam ni treba malloc več Prostor za F ali O, saj
tistih, ki že obstajajo.
Toda zadnja O v foo?
Tista, boste morali malloc.
Naredite novo vozlišče za to, v katerem Word Boolean, da res.
>> Torej, zdaj pa doda "psa." Pes bo začeti z indeksom treh korenin
otroci, ker je D ne še ni bila ustvarjena.
In bomo sledili podoben proces kot pred oblikovanjem podniz psa,
kjer je G zelene barve, saj to je konec besedi.
>> Zdaj, kaj, če želimo vstaviti "ne"?
No, to je podniz psa, tako da nam ni treba več malloc.
Vendar pa je treba navesti, kje smo že dosegel konec te besede.
Torej bo O zelene barve.
Nadaljevanje tega procesa za vsak beseda v vašem slovarju, ki ste jih
jih v naloženi v obeh vašem hash tabelo ali vaše Trsta.
>> speller.c bo minilo v kito za dictionary.c za njihovo preverjanje.
Zdaj Preverite delovanje mora delovati v skladu s sodno neobčutljivosti.
To pomeni, da tiskane črke in male črke in mešanica obojega
bi morali vsi enačijo true če sploh kombinacija, ki je v
Slovar.
Prav tako lahko sklepamo, da so strune samo še vsebuje abecedni
znakov ali opuščaj.
>> Zato si oglejmo, kako lahko preverite, s strukturo hash tabele.
Torej, če obstaja beseda, potem je mogoče najti v razpršene tabele.
Torej, potem lahko poskusite najti, da beseda v ustreznem vedru.
>> Torej, ki bucket bi ta beseda v?
No, boš dobil številko, da indeks vedra, s hašiš to besedo
in nato iskati v tem povezan seznam, prehaja skozi celoten
povezani seznam, s pomočjo String Funkcijo primerjavo.
>> Če konec povezani seznam je dosegel, kar pomeni, da je vaš kazalec
doseže nič, potem beseda ni lahko najdemo v slovarju.
To ne bo v katerikoli drugi vedru.
Torej tu lahko vidite, kako bi lahko obstajal je kompromis med tem, ali
razvrščena povezani seznami ali nesortirane tisti.
Bodisi bo potrebno več časa med naložiti ali več časa med preverjanjem.
>> Kako bi lahko prijavijo Trie struktura?
Gremo navzdol potovati v Trsta.
Za vsako črko v besedi vnesenega da smo kontrolo, bomo šli na to
ustreza element pri otrocih.
>> Če ta element je nična, potem to pomeni, da ni nukleotidov
vsebuje našo vhodno besedo, tako da beseda napačno črkovana.
Če to ni nič, lahko gremo na naslednja črka besede, da smo
preverjanje in nadaljevati ta proces dokler ne pridete do konca
vhodne besede.
In potem bomo lahko preverite Če je Beseda je res.
Če je, potem super.
Beseda je pravilno.
Če pa ne, čeprav se ta podniz obstaja v Trsta, beseda
napačno.
>> Ko je funkcija Velikost imenuje, velikost mora vrniti število besed, ki
so v danem slovar struktura podatkov.
Torej, če ste z uporabo hash tabelo, lahko bodisi iti skozi vsak
povezani seznam v vsak bucket štetjem
besed so tam.
Če boste uporabljali Trsta, lahko iti skozi vse prepovedi null
Pot v vašem Trsta.
Ali pa, ko ste nalaganju slovar leta, morda lahko spremljate, kako
veliko besed ste loading prijavite
>> Ko speller.c konča preverjanje besedilna datoteka, proti slovarju, potem
to je storil, in zato poziva, razkladanje, kjer vaša naloga je, da osvobodi vse
da ste malloced.
Torej, če uporabljate razpršene tabele, nato pa morajo biti še posebej previdni, da se prepreči
pomnilniške uhajanje ne osvoboditev ničesar prezgodaj in držite vsak
enojna vez, preden brezplačno.
>> Torej za vsak element v razpršene tabele in za vsako vozlišče v povezanem seznamu,
boste želeli sprostiti, da vozlišče.
Kako greste o sproščanju povezani seznam?
Nastavitev vozlišča kazalec kazalec glava, do začetka
povezani seznam, potem ko je vaš kazalec ni nič, lahko nastavite začasno
vozlišče kazalec kazalca.
Potem vnaprej kazalec.
In potem se lahko sprostite, da se začasna vrednost, medtem ko še vedno držite na
vse kasneje.
>> Kaj pa, če boste uporabljali Trsta?
Potem je najboljši način za to je za raztovarjanje iz zelo
spodaj navzgor.
S potovanjem na najnižjo možno vozlišče, lahko osvobodi vse napotke v
da otroci in nato Vrniti navzgor, sprostitev vse elemente v vseh
otrok nizi, dokler si se udaril v top korenskega vozlišča.
Tu Rekurzija bo prišel prav.
>> Se prepričajte, da ste verjetno osvobodil vse, kar ste malloced,
lahko uporabite Valgrind.
Tek Valgrind bo potekal svoj program Računam, koliko bajtov pomnilnika
ki ga uporabljate, in pazite, da ste Vse jih osvobodil, ti
, kjer boste morda morali pozabili brezplačno.
Tako, da teče in ko Valgrind vam pove in vam gredo naprej, nato pa
ste končali razkladanje.
>> Zdaj, nekaj nasvetov, preden greste off in začeti izvajati svoj
Slovar.
Želel priporočamo, da prenese v manjši slovar, ko ste poskušali preizkusiti
stvari in razhroščevanje z BDP.
Uporaba speller je. / Speller, neobvezno slovar, nato pa besedilo.
>> Privzeto je, da se naloži v Velik slovar.
Tako da boste morda želeli, da prenese v majhno slovar, ali morda celo vaše
lastno, prilagajanje vaše slovar in vaše besedilne datoteke.
>> In potem končno, Jaz bi tudi priporočamo vzeti svinčnik in papir in sestaviti
Stvari pred, med in po Saj si napisal vse svoje kode.
Samo poskrbite, da ste dobili ti kazalci ravno prav.
>> Želim vam veliko sreče.
In ko ste končali, če želite za izpodbijanje veliko desko in
videli, kako hitro se vaš program v primerjavi s sošolci, nato pa spodbujam
vam, da preverite to.
>> S tem, ko ste končali speller PSet.
Ime je Zamyla, in to je CS50.