>> ROB Bowden: Bok.
Ja sam Rob, i neka je mljeveno meso ovo rješenje se.
Dakle, ovdje ćemo provesti Općenito hash tablicu.
Vidimo da struct node našeg mljeveno meso Stol će izgledati ovako.
Dakle, to će imati char riječ Niz duljine veličine plus jedan.
Nemojte zaboraviti jedan jer je najduže Riječ u rječniku je 45
likovi, a onda idemo u treba mi jedan dodatni znak za
backslash 0.
>> I onda naš hash tablicu u svakoj kanta će pohraniti
povezani popis čvorova.
Ne radimo linearnu sondiranja ovdje.
I tako, kako bi se povezati na sljedećoj element u kantu, trebamo
struct node * next.
Dakle, to je ono što čvor izgleda.
Sada, ovdje je deklaracija našeg hash tablicu.
To će imati 16.384 kante, ali taj broj zapravo ne smeta.
I na kraju, da ćemo imati Globalna varijabla hashtable_size, koji
će krenuti kao 0, a to je će pratiti koliko riječi
bili su u našem rječniku.
U redu.
>> Tako ćemo pogledati na teret.
Dakle, primijetite da je opterećenje, to vraća bool.
Vraćate li istina da je uspješno učitan i lažno drugi način.
I to traje const char * zvijezdu rječnik, koji je rječnik
da želimo otvoriti.
Dakle, to je prva stvar idemo raditi.
Idemo u fopen rječnik za čitanje, a mi ćemo imati
kako bi bili sigurni da je to uspjelo pa ako je vratio NULL, onda nismo
Uspješno otvaranje rječnik i moramo se 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 da se probijemo iz toga
Petlja koja ćemo vidjeti.
Dakle, imajte petlje, a sada idemo na malloc jedan čvor.
I naravno, moramo pogrešaka ček opet pa ako mallocing nisu uspjeli
i ž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.
Dakle, ne zaboravite da je ulazak-> riječ je char Riječ tampon duljine veličine plus
onaj koji ćemo pohraniti riječ u.
Dakle fscanf će vratiti 1 dokle kao što je bio u mogućnosti uspješno pročitati
Riječ iz spisa.
>> Ako je bilo pogrešaka dogodi ili ne stignemo kraj datoteke, to neće
vratiti jedan u kojem slučaju, ako se to ne dogodi povratak 1, napokon smo idemo razbiti
iz ovog while petlje.
Dakle, vidimo da je jednom uspješno smo pročitati riječ u
entry-> riječ, onda idemo u hash da je riječ pomoću naše hash funkciju.
Idemo pogledati hash funkcija.
>> Tako da stvarno ne treba razumjeti to.
I doista, samo mi je izvukao ovo hash funkciju s interneta.
Jedino što morate prepoznati je da to traje const char * riječ,
pa to je uzimanje niz kao ulaz i povratka nepotpisani int kao izlaz.
Dakle, to je sve hash funkcija, je li to Potrebno je u ulazu, to vam daje
indeks u hash tablicu.
Uočite da smo modding by NUM_BUCKETS pa hash vrijednost vratio
zapravo je indeks u hash tablicu a ne indeks izvan
Granica u nizu.
>> Dakle, s obzirom da je hash funkcija, idemo hash riječ da čitamo
iz rječnika, a potom idemo koristiti da ima za umetanje
Ulazak u hash tablicu.
Sada, hashtable hash je trenutna povezani popis u hash tablici, a
to je vrlo moguće da je samo NULL.
Mi želimo umetnuti naš ulazak u Početkom ovog popisa povezane, i tako
ćemo imati naš trenutni unos ukazuju na ono što je hash tablicu trenutno
bodovi se i onda ćemo pohraniti u hash tablicu na mljeveno meso
tekući zapis.
>> Dakle, ove dvije linije Uspješno umetanje Ulazak na početku
povezani popis u tom indeksu u hash tablicu.
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 konačno vrati nešto ne 1 na
kojem trenutku ne zaboravite da moramo ulaz slobodan, tako da se ovdje, malloced smo
Ulazak i mi pokušali pročitati nešto iz rječnika.
I nismo uspješno pročitati nešto iz rječnika u kojoj
Slučaj moramo osloboditi zapis koji smo Nikad zapravo staviti u hash tablicu
i na kraju slomiti.
>> Nakon što smo izbijati, moramo vidjeti, dobro, nije mi izbije jer postoji
bila pogreška čitanja iz datoteke, ili nije mi izbije jer smo postigli
kraj datoteke?
Ako je došlo do pogreške, onda želimo povratak false, jer teret nije
uspjeti, a u tom procesu, želimo iskrcati sve riječi koje smo čitali
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 se vratiti točno jer smo uspješno ste učita
rječnik.
I to je to za opterećenja.
>> Tako sada provjeriti, obzirom učita hash tablicu, će izgledati ovako.
Dakle, provjerite, to vraća bool, koji će se naznačiti je li
prošlo-u char * riječ, je li prošlo-u niz je u našem rječniku.
Dakle, ako je to u rječniku, ako je to u našem hash tablicu, mi ćemo se vratiti
istina, a ako to nije, vratit ćemo se lažna.
S obzirom na to prošli-u riječ, da smo će hash riječ.
>> Sada, važna stvar je da prepoznaju da u opterećenju, znali smo da su sve
riječi su idući u biti manji slučaj, ali ovdje, nismo tako sigurni.
Ako ćemo se pogled na naše hash funkcije, naš hash funkcija zapravo
je lowercasing svaki lik od riječi.
Dakle, bez obzira na kapitalizaciju Riječ, naša hash funkcija će
vratiti istu indeks za sve što kapitalizacija je kao da će to imati
vratio za potpuno slovu Verzija od riječi.
U redu.
>> Dakle, to je naš indeks.
To je hash tablicu za tu riječ.
Sada, to za petlje ide na više popisa povezan
koji je bio na tom indeksu.
Dakle, primijetit ćemo se inicijalizacije unos ukazati na taj indeks.
Mi ćemo nastaviti dok ne entry nije jednak NULL, i sjetite se da
ažuriranje pokazivač na našem popisu povezanom Ulazak jednako entry-> next, tako da su
Naš trenutni polazna točka za Sljedeća točka u povezanim popisu.
U redu.
>> Dakle, za svaki unos u popisu povezana, ćemo koristiti strcasecmp.
Nije strcmp, jer opet, mi želite učiniti stvari slučaj insensitively.
Dakle, mi koristimo strcasecmp usporediti riječ koji je donesen na ovu funkciju
protiv riječi koje je u tom ulasku.
Ako se vrati 0, to znači da je utakmicu, u kojem slučaju želimo
povratak istina.
Uspješno smo se našli Riječ u našem hash tablicu.
>> 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š hash tablica ne sadrži tu riječ.
I to je to za provjeru.
U redu.
>> Tako ćemo pogledati veličini.
Sada, veličina će biti prilično jednostavno jer zapamtite u opterećenjem, za svaku riječ
našli smo mi porastao globalni promjenjiva hashtable_size.
Tako je funkcija veličine je samo će se vratiti da je globalno
varijabla, i to je to.
>> Sada napokon, moramo rasteretiti rječnik odjednom se sve to radi.
Pa kako ćemo to učiniti?
Upravo ovdje, mi smo petlje preko svega kante našeg hash tablicu.
Dakle, postoje NUM_BUCKETS kante.
A za svaki povezan popisu u našoj mljeveno meso Stol, idemo na petlji preko
Sveukupna popisu povezanom oslobađajući svaki element.
Sada, moramo biti oprezni, pa ovdje smo imaju privremenu varijablu koja 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č jer kad smo ga oslobodili
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 vezane liste u hash tablicu, a kad smo gotovi
s tim, mi u potpunosti smo iskrcali hash tablicu, i mi smo gotovi.
Tako da je nemoguće da izbacuje ikada povratak false, a kad smo gotovi, mi
Samo povratak istina.