>> [Glazba svira]
>> ROB Bowden: Bok.
Ja sam Rob.
I neka je ovo rješenje out.
Dakle, ovdje ćemo provesti Općenito stol.
Vidimo da struct node od naših Stol će izgledati ovako.
Dakle, to će imati char riječ Niz veličine duljina + 1.
Ne zaboravite + 1, od maksimalno Riječ u rječniku je 45
likovi.
I onda ćemo morati jedan pomoćni znakova za znak obrnute kose nulu.
>> I onda naš hashtable u svakoj kanta će pohraniti
povezani popis čvorova.
Mi ne radimo linearnu sondiranja ovdje.
I tako, kako bi se povezati na sljedećoj element u kantu, trebamo
struct node * next.
OK.
Dakle, to je ono što čvor izgleda.
>> Sada ovdje je deklaracija našeg hashtable.
To će imati 16.834 kante.
No, taj broj nije važno.
I na kraju, da ćemo imati Globalna varijabla veličine hashtable, koji
će krenuti kao nulu.
I to će se pratiti kako mnogi su riječi u našem rječniku.
>> Tako ćemo pogledati na teret.
Primijetimo da je opterećenje, to vraća bool.
Vraćate li istina da je uspješno učita, a lažna inače.
I to traje const char * rječnik, što je rječnik
da želimo otvoriti.
Dakle, to je prva stvar idemo raditi.
>> Idemo u fopen rječnik za čitanje.
A mi ćemo morati napraviti sigurni da je uspio.
Dakle, ako se vrati NULL, onda nismo Uspješno otvaranje rječnika.
I moramo vratiti false.
No, uz pretpostavku da je uspješno učinio otvoren, onda želimo čitati
rječnik.
Dakle, imajte petlje dok ne nađemo neki Razlog pobjeći iz ove petlje,
što ćemo vidjeti.
Dakle, imajte petlje.
>> A sad idemo na malloc jedan čvor.
I, naravno, trebamo emitirati ponovno provjeriti.
Dakle, ako mallocing nisu uspjeli, a zatim želimo rasteretiti bilo čvor koji smo
dogodilo malloc prije, zatvorite rječnik i povratak false.
No, ignoriranje da, pod pretpostavkom da uspjeli, onda želimo koristiti fscanf
čitati jednu riječ iz naše Rječnik u našu čvora.
Pa sjetite se da zapis> riječ je char Riječ tampon od veličine LENGHTH + 1
da ćemo pohraniti riječ u.
>> Dakle fscanf će vratiti 1, dokle kao što je u stanju uspješno
pročitati riječ iz spisa.
Ako bilo dogodi pogreška, ili ćemo do kraja datoteke, to
neće vratiti jedan.
U tom slučaju se ne vraća 1, smo konačno ćemo izaći iz
ovo while petlja.
Dakle, vidimo da je jednom uspješno smo pročitati riječ u
entry> riječ, onda ćemo to Riječ pomoću naše hash funkciju.
>> Idemo pogledati hash funkcija.
Tako da stvarno ne treba razumjeti to.
A zapravo smo samo izvukao ovaj hašiš funkcionirati s interneta.
Jedino što morate prepoznati je da to traje const char * riječ.
Dakle, to je uzimanje niz kao ulaz, a povratka nepotpisani int kao izlaz.
Dakle, to je sve hash funkcija, je li to vodi u ulaz i daje vam
indeks u hashtable.
>> Uočite da smo MODING by NUM_BUCKETS, tako da vrijednost vratio
zapravo je indeks u hashtable a ne indeks izvan
Granica u nizu.
Dakle, s obzirom da je funkcija, idemo hash riječ da čitamo
rječnik.
A onda ćemo koristiti da hash umetnuti
Ulazak u hashtable.
>> Sada hashtable hash je trenutna povezana popisa u tablici.
A vrlo je moguće da je to samo NULL.
Mi želimo umetnuti naš ulazak u Početkom ovog popisa povezane.
I tako ćemo imati naše struje polazna točka za ono hashtable
Trenutno ukazuje.
A onda ćemo se spremiti, u hashtable na
mljeveno meso, tekući zapis.
Dakle, ove dvije linije Uspješno umetanje Ulazak na početku
povezani popis u tom indeksu u hashtable.
>> Nakon što završimo s tim, znamo da smo pronašli još jednu riječ u
rječnik, a mi opet povećavati.
Tako smo zadržati taj događaj dok fscanf napokon se vratio nešto ne-1 na
kojem trenutku ne zaboravite da moramo besplatan ulaz.
Dakle ovdje smo malloced unosa.
I mi smo pokušali pročitati nešto iz rječnika.
I nismo uspješno pročitati nešto iz rječnika, u
kojem slučaju moramo osloboditi unos da mi nikada zapravo staviti u
hashtable, i na kraju slomiti.
>> Nakon što smo izbiju moramo vidjeti, dobro, nije mi izbije jer postoji
bila pogreška čitanja iz datoteke?
Ili smo se probiti van jer smo do kraja datoteke?
Ako je došlo do pogreške, a zatim želimo vratiti false.
Zbog opterećenja nisu uspjeli.
I u tom procesu želimo rasteretiti sve ono što smo pročitali u, i
zatvoriti rječničku datoteku.
>> Pod pretpostavkom da smo uspjeli, onda mi samo Još uvijek je potrebno zatvoriti rječnik
podnijeti, i na kraju povratak istina jer smo Uspješno učitava rječnik.
I to je to za opterećenja.
Tako sada provjeriti, obzirom učita hashtable, će izgledati ovako.
Dakle, provjerite, to vraća bool, koji je će pokazati da li je prošao
u char * riječ, je li prošao u nizu je u našem rječniku.
Dakle, ako je to u rječniku, ako je to u našoj hashtable,
vratit ćemo istinito.
A ako to nije, mi ćemo se vratiti false.
>> S obzirom na to prošlo u riječi, mi smo će hash riječ.
Sada Važno je prepoznati je da u opterećenju smo znali da je sve
Riječi mi ćemo biti mala slova.
Ali ovdje smo baš siguran.
Ako ćemo se pogled na naše hash funkcije, naš hash funkcija zapravo
niža kućište svaki lik od riječi.
Dakle, bez obzira na kapitalizaciju Riječ, naša hash funkcija je povratak
Isti indeks za sve kapitalizacija je, kao što će imati
vratio za potpuno slovu Verzija od riječi.
U redu.
To je naš indeks je u hashtable za tu riječ.
>> Sada je to za petlje će se ponoviti na popis povezana
koji je bio na tom indeksu.
Dakle, primijetit ćemo se inicijalizacije unos ukazati na taj indeks.
Mi idemo dalje dok je ulaz! = NULL.
I ne zaboravite da je ažuriranje pokazivač u naš povezani entry Popis = entry> next.
Tako su naše trenutne polazna točka za sljedeće stavke na popisu povezane.
>> Dakle, za svaki unos u popisu povezana, ćemo koristiti strcasecmp.
Nije strcomp.
Zato još jednom, želimo rade stvari slučaj insensitively.
Dakle, mi koristimo strcasecmp usporediti Riječ koja je prošla kroz to
Funkcija protiv riječi da je u tom ulasku.
Ako se vraća na nulu, to znači da je utakmicu, u kojem slučaju želimo
povratak istina.
Uspješno smo se našli Riječ u našem hashtable.
>> Da nije bilo utakmica, onda smo ide na petlju i opet pogledati
sljedeći unos.
I mi ćemo nastaviti petlje dok postoji su upisi u ovom popisu povezana.
Što će se dogoditi ako se lomimo iz toga za petlje?
To znači da nisu pronašli zapis koji uskladiti tu riječ, u kojem slučaju
vraćamo lažno ukazuje da je naš hashtable ne sadrži tu riječ.
I to je kontrola.
>> Tako ćemo pogledati veličini.
Sada veličina će biti prilično jednostavno.
Budući da zapamtite u opterećenjem, za svaku riječ smo našli, mi porastao globalni
promjenjiva veličina hashtable.
Dakle funkcija veličine samo ide da se vrate globalnu varijablu.
I to je to.
>> Sada napokon, moramo rasteretiti rječnik odjednom se sve to radi.
Pa kako ćemo to učiniti?
Upravo ovdje smo petlje preko sve kante za naš stol.
Dakle, postoje NUM_BUCKETS kante.
A za svaki povezan popis u našem hashtable, idemo na petlji preko
Cjelina popisu povezana, oslobađajući svaki element.
>> Sada moramo biti oprezni.
Dakle, ovdje imamo privremenu varijablu koji je spremanje pokazivača na sljedećoj
Element u popisu povezane.
A onda ćemo besplatno trenutna elementa.
Moramo biti sigurni da smo to učinili jer smo mi Ne mogu samo osloboditi trenutne element
a zatim pokušati pristupili sljedećoj pokazivač, budući da se nakon što ga je oslobodio,
memorije postaje nevažeći.
>> Zato nam je potrebno da bi oko pokazivač na Sljedeći element, onda možemo osloboditi
Trenutna je element, a onda smo se ažurirati Naš trenutni element ukazuju na
Sljedeći element.
Mi ćemo petlju dok postoje elementi na ovom popisu povezane.
Učinit ćemo to za sve povezane popisi u hashtable.
I jednom kada smo gotovi s tim, mi smo potpuno rastovarale hashtable, a
smo gotovi.
Tako da je nemoguće za istovariti ikada vratiti false.
A kad smo gotovi, mi Samo povratak istina.
>> Dajmo ovo rješenje probati.
Tako ćemo pogledati što naši struct node će izgledati.
Ovdje vidimo da ćemo imati Bool Riječ i struct node * djeca
Nosač abecede.
Dakle, prva stvar koju bi moglo biti pitate, zašto je ALPHABET
ed definira kao 27.?
Pa, sjetite se da ćemo morati biti rukovanja apostrof.
Tako da će to biti nešto poseban slučaj u cijelom ovom programu.
>> Sad se sjećam kako trie zapravo radi.
Recimo da smo indeksiranje riječ "mačke". Zatim iz korijena trie,
idemo gledati na djecu polje, a mi ćemo gledati na
indeks koji odgovara na pisma C. Dakle, koja će biti indeksirana 2.
Dakle, s obzirom da je, kako će daju nam novi čvor.
A onda ćemo raditi s tom čvoru.
>> Dakle, s obzirom da je čvor, mi smo još jednom ide gledati na djecu polje.
I mi ćemo gledati na indeks nula odgovarati A Cat.
Pa onda ćemo ići u tom čvoru, as obzirom da je čvor idemo
gledati na kraju da je to odgovara na T. i kreće na tom čvoru,
Konačno, potpuno smo gledali kroz naša riječ "mačka". I sada Bool
Riječ je trebao naznačiti da li to dao riječ je zapravo riječ.
>> Pa zašto nam je potrebna da poseban slučaj?
Pa što je s riječju "katastrofa" je u našem rječniku, ali
Riječ "mačka" nije?
Zato i traže da se vidi je li riječ "mačka" je u našem rječniku, mi smo
će uspješno gledati kroz indeksi C--T u regiji čvor.
No, to je samo zato što je katastrofa dogodilo stvoriti čvorove na putu
od C-A-T, sve do kraj riječi.
Dakle bool riječ se koristi za označavanje li ovo posebno mjesto
zapravo ukazuje na riječi.
>> U redu.
Dakle, sada znamo da je ono što je trie kako će izgledati, pogledajmo
učitati funkciju.
Dakle, teret će se vratiti Bool za li uspješno ili
neuspješno učitava rječnik.
A to će biti rječnik da želimo učitati.
>> Dakle, prva stvar koju smo učiniti je otvoriti do tog rječnik za čitanje.
A imamo kako bi bili sigurni nismo uspjeti.
Dakle, ako rječnik nije bio uspješno je otvorio, ona će se vratiti
null, u kojem slučaju nismo će se vratiti false.
No, uz pretpostavku da je uspješno otvorila, onda zapravo možemo čitati
kroz rječniku.
>> Dakle, prva stvar koju ćemo želite učiniti je da imamo ovo
Globalna varijabla korijena.
Sada korijen će biti čvor *.
To je vrh naše trie da smo će biti iterating putem.
Dakle, prva stvar koju ćemo to želim učiniti je dodijeliti
Memorija za naš korijen.
Uočite da smo pomoću calloc funkcija, što je u osnovi isti
kao funkcija malloc, osim što je jamčiti da se vrati nešto što je
potpuno nulu out.
Dakle, ako ćemo koristiti malloc, mi bi trebao proći kroz sve naputke u našim
čvora, i pobrinite se da oni su svi null.
Dakle calloc će to učiniti za nas.
>> Sad baš kao malloc, moramo napraviti sigurni da je dodjela bila je zapravo
uspješna.
Ako se to vrati null, onda smo morati zatvoriti ili rječnik
podnijeti i vratiti false.
Dakle, uz pretpostavku da je dodjela uspješna, idemo koristiti čvor *
kursor na ponoviti kroz naše trie.
Tako su naši korijeni nikada neće promijeniti, ali ćemo koristiti kursor na
zapravo ići od čvora do čvora.
>> Tako je u to za petlje čitamo kroz rječniku datoteku.
I mi koristimo fgetc.
Fgetc će zgrabite jednu lik iz spisa.
Mi ćemo nastaviti grabbing likovi, dok se ne postigne
završetak datoteke.
>> Postoje dva slučaja moramo nositi.
Prvi, ako je znak nije bila nova linija.
Tako ćemo znati je li to nova linija, a zatim smo o tome da se presele na novi riječ.
No, pod pretpostavkom da nije nova linija, a zatim Ovdje želimo shvatiti
Indeks ćemo indeksa u u djece niz koji
Gledali smo i prije.
>> Dakle, kao što sam već rekao, moramo Poseban slučaj apostrof.
Obavijest koristimo ternarnom operatera ovdje.
Dakle, idemo čitati ovo kao, ako lik čitamo u bilo
apostrof, onda ćemo postaviti index = "alfabet" -1, što će
biti indeks 26.
>> Inače, da nije bilo apostrof, postoji ćemo postaviti indeksa
jednaka c -.
Pa sjetite se vratio iz prethodno p-seta, c - će nam dati
abecedni položaj C. Dakle, ako C je pismo, to će
daju nam indeks nula.
Za slovom B, to će dati us indeks 1, i tako dalje.
>> Dakle, to nam daje indeks u djeca polje koje želimo.
Sada, ako je ovaj indeks trenutno null u djeca, to znači da je čvor
trenutno ne postoji s toga puta.
Zato nam je potrebno izdvojiti čvor za taj put.
To je ono što ćemo učiniti ovdje.
>> Dakle, idemo ponovno koristiti calloc funkcija, tako da mi ne moramo
nulirati sve upućuje.
I opet je potrebno provjeriti da calloc nije propustio.
Ako calloc doživio neuspjeh, onda moramo iskrcati sve, zatvoriti
rječnik, a povratak false.
Dakle, pod pretpostavkom da ne uspiju, onda to će stvoriti novo dijete za nas.
A onda ćemo ići u tom djetetu.
Naš kursor će ponoviti do tog djeteta.
>> Sada, ako to nije bilo null za početak, zatim kursor mogu samo ponoviti
do tog djeteta, bez zapravo moraju izdvojiti ništa.
Ovo je slučaj gdje smo prvi put se dogodilo dodijeliti riječ "mačka". I
to znači da kad idemo na dodjelu "Katastrofa", ne moramo stvoriti
čvorovi za C-A-T opet.
Oni već postoje.
>> Što je to drugo?
To je stanje u kojem je c backslash n, gdje je c je nova linija.
To znači da smo uspješno završio je riječ.
Sada ono što želimo učiniti, kada smo Uspješno završen riječ?
Mi ćemo koristiti ove riječi polje unutar našeg struct čvor.
Želimo postaviti da se istina.
Tako da ukazuje da je ovaj čvor pokazuje uspješan
Riječ, stvarna riječ.
>> Sada postaviti da se istina.
Želimo resetirati našu kursor na točku na početku trie ponovno.
I na kraju, povećava, naš rječnik veličina, jer smo pronašli još jedan posao.
Tako ćemo zadržati taj događaj, čitanje u slovo po slovo,
izgradnje novih čvorova u našem trie i Za svaku riječ u rječniku, dok
smo konačno doći C! = EOF, u kojem Slučaj smo izaći iz spisa.
>> Sada postoje dvije slučajeve u što smo mogli pogoditi EOF.
Prvi je, ako je došlo do pogreške čitanje iz datoteke.
Dakle, ako je došlo do pogreške, mi trebate učiniti tipični.
Posuda za sve, u neposrednoj blizini datoteka, vratiti false.
Pod pretpostavkom da nije bilo pogrešaka, da samo znači da mi zapravo pogodio kraj
file, u kojem slučaju, možemo zatvoriti podnijeti i vratiti točno jer smo
Uspješno učitava rječnik u našu trie.
>> Pa sad idemo provjeriti ček.
Gledajući na check funkciju, vidimo da je provjera će vratiti bool.
Ona vraća true ako je to riječ koja je bude donesen je u našoj trie.
To false inače.
Pa, kako se utvrdilo je li ova riječ u našem trie?
>> Ovdje vidimo da je, baš kao i prije, ćemo koristiti kursor se ponoviti
kroz naše trie.
Sada ovdje ćemo ponoviti tijekom cijele naše riječi.
Dakle iterating iznad riječi smo prošli, ćemo odrediti
indeks u djece niz koji odgovara riječi bracket I. Dakle, ovo
će izgledati točno kao opterećenja, gdje li riječ [i]
je apostrof, onda želimo koristiti Index "Abeceda" - 1.
Budući da smo utvrdili da je taj je mjesto gdje ćemo pohraniti
apostrofe.
>> Inače ćemo koristiti dva niža riječ Nosač I. Tako zapamtite tu riječ može
ima proizvoljnog kapitalizaciju.
I tako mi želimo biti sigurni da smo pomoću malim slovom verziju stvari.
I onda oduzmite od toga '"na jednom Ponovno nam dati Abecedi
položaj taj lik.
Tako da će to biti naš index u djece niz.
>> A sad, ako je indeks u djece Niz je nula, da mi znači
više ne može nastaviti iterating niz naše trie.
Ako je to slučaj, ta riječ ne može možda se u našem trie.
Budući da je, kako bi se znači da bi put
na tu riječ.
I nikad ne bi naići na null.
Tako nailazi null, vraćamo lažna.
Riječ je nema u rječniku.
Da nije bilo null, onda smo će Ponavljanje nastaviti.
>> Dakle, idemo vani kursor ukazati na to posebno
čvor u tom indeksu.
Mi zadržati taj događaj u cijeloj Cijeli riječi, uz pretpostavku
mi nikada pogodio null.
To znači da smo bili u mogućnosti da se kroz Cijeli riječ i pronaći
čvora u našem pokušaju.
Ali nismo sasvim gotova.
>> Mi ne želimo samo povratak istina.
Želimo da se vrati kursor> riječ.
Budući da zapamtite opet, je "mačka" se ne u našem rječniku, i "katastrofa"
je, onda ćemo uspješno smo dobili kroz riječ "mačka". Ali kursor
Riječ će biti lažna i nije istina.
Tako smo se vratili kursor riječ za označavanje je li to čvor je zapravo riječ.
I to je to za provjeru.
>> Tako ćemo provjeriti veličinu.
Dakle, veličina će biti prilično jednostavan jer, ne zaboravite na teret, mi smo
povećavanjem rječnik veličinu svaka riječ koju susrećemo.
Dakle, veličina tek će se povratak rječnik veličinu.
I to je to.
>> Dakle, na kraju smo rasteretiti.
Dakle iskrcati, idemo koristiti rekurzivna funkcija zapravo učiniti sve
dio posla za nas.
Tako je naša funkcija će zvati na desiliranje.
Što se desiliranje će učiniti?
Ovdje vidimo da desiliranje će ponoviti tijekom sva djeca na
ovaj čvor.
A ako dijete čvor nije null, onda ćemo
iskrcati dijete čvora.
>> Dakle, ovo je li rekurzivno iskrcati sve naše djece.
Jednom smo bili sigurni da su sva djeca su iskrcali, onda smo
možemo osloboditi, tako iskrcati se.
To će raditi rekurzivno iskrcati cijeli trie.
I onda kada to bude učinjeno, mi samo možemo vratiti istinito.
Iskrcati se ne može uspjeti.
Mi samo oslobađajući stvari.
Dakle, nakon što smo gotovi oslobađajući sve, povratak istina.
I to je to.
Moje ime je Rob.
A to je bukvar.
>> [Glazba svira]