>> ROB BOWDEN: Hi.
Es esmu Rob, un pieņemsim hash Šis risinājums out.
Tāpēc šeit mēs ejam, lai īstenotu Kopumā hash tabulu.
Mēs redzam, ka struktūrai mezgla mūsu hash tabula gatavojas izskatās šādi.
Tātad, tas notiek, lai būtu char vārds masīvs izmēra garumu plus 1.
Neaizmirstiet 1 kopš maksimāli vārdu vārdnīcā ir 45
rakstzīmes, un tad mēs ejam uz vajag vienu papildus rakstzīmi
slīpsvītru 0.
>> Un tad mūsu hash tabulu katrā kauss ir gatavojas glabāt
saistīts saraksts mezglu.
Mēs nedarām lineāra zondēšana šeit.
Un tāpēc, lai saite uz nākamā elements spainī, mums ir nepieciešams
struct mezglā * nākamo.
Tātad, tas ir tas, ko mezglā izskatās.
Tagad šeit ir deklarācija mūsu hash tabulu.
Tas nāksies 16384 kausi, bet šis numurs nav īsti jautājums.
Un visbeidzot, mēs esam nāksies globālo mainīgo hashtable_size, kas
gatavojas sākt ar 0, un tas ir būs izsekot, cik daudz vārdu
bija mūsu vārdnīcā.
Labi.
>> Tātad, pieņemsim to apskatīt slodzes.
Tāpēc ievērosiet, ka slodze, tā atgriež bool.
Jūs atgrieztos taisnība, ja tas bija veiksmīgi piekrauts un viltus citādi.
Un tas notiek const char * zvaigzne vārdnīcā, kas ir vārdnīcā
ka mēs vēlamies, lai atvērtu.
Tā ka ir pirmā lieta, mēs gatavojamies darīt.
Mēs ejam, lai fopen vārdnīcu, lai lasījumā, un mēs esam nāksies
lai pārliecinātos, ka tas ir izdevies, tādēļ, ja tas atgriezās NULL, tad mēs neesam
veiksmīgi atvērt vārdnīcu un mums ir nepieciešams, lai atgrieztos nepatiesa.
>> Bet, pieņemot, ka tā veiksmīgi atvērt, tad mēs vēlamies, lai izlasītu
vārdnīca.
Lai saglabātu looping kamēr mēs atrodam kādu iemesls, lai izkļūt no šīs
cilpa, ko mēs redzēsim.
Tāpēc saglabājiet looping, un tagad mēs ejam lai malloc vienu mezglu.
Un, protams, mums ir nepieciešams, lai kļūdu pārbaude vēlreiz, tāpēc, ja mallocing neizdevās
, un mēs vēlamies, lai izkrautu jebkuru mezglu, ko mēs notika ar malloc pirms slēgt
vārdnīcu un atgriezties viltus.
>> Bet ignorējot, ka, pieņemot, ka mēs izdevies, tad mēs vēlamies izmantot fscanf
lasīt vienu vārdu no mūsu vārdnīca mūsu mezglā.
Tātad, atcerieties, ka ieejas-> vārds ir char vārdu bufera izmēra garumu plus
viens, ka mēs ejam uzglabāt vārdu iekšā
Tāpēc fscanf gatavojas atgriezties 1 tik ilgi jo tas varēja veiksmīgi nolasīt
vārdu no lietas materiāliem.
>> Ja nu kļūda notiek, vai mēs sasniegsim faila beigas, tas nav
return 1 tādā gadījumā, ja tā nav atgriezties 1, mēs beidzot gatavojas lauzt
no šīs kamēr cilpa.
Tātad mēs redzam, ka tad, kad mēs esam veiksmīgi lasīt vārdu uz
Ierakstu-> vārdu, tad mēs ejam uz hash šis vārds, izmantojot mūsu hash funkciju.
Pieņemsim to apskatīt hash funkciju.
>> Tātad jums nav tiešām ir nepieciešams saprast.
Un patiesībā, mēs vienkārši velk to hash funkciju no interneta.
Vienīgais, kas jums ir nepieciešams atzīt, ka tas aizņem const char * vārdu,
tāpēc tas ir ņemot virkni kā priekšnodokli un atgriešanās neparakstītu int kā produkciju.
Tātad tas viss hash funkciju, tas ir uzņem ieejas, tas dod jums
indekss par hash tabulu.
Ievērojiet, ka mēs esam modding ar NUM_BUCKETS tāpēc hash vērtība atgriezās
patiesībā ir rādītājs uz hash tabulu un nav rādītājs pārsniedz
robežas no masīva.
>> Tāpēc, ka hash funkciju, mēs ejam hash vārdu, ka mēs lasām
No vārdnīcas, un tad mēs ejam izmantot, kas ir, lai ievietotu
stāšanās hash tabulu.
Tagad, Hashtable hash ir pašreizējā saistīts saraksts hash tabulā, un
tas ir ļoti iespējams, ka ir tikai NULL.
Mēs vēlamies, lai ievietotu savu ienākšanu sākot no šīs saistīta saraksta, un tā
Mēs ejam, lai būtu mūsu pašreizējo ierakstu norāda uz to, ko hash tabulā šobrīd
punkti, un tad mēs ejam, lai saglabātu hash tabulu, hash
pašreizējais ieraksts.
>> Tātad šīs divas līnijas veiksmīgi ievietot ieraksts sākumā
saistīts saraksts šajā indeksā hash tabulā.
Pēc tam, kad mēs esam darīts ar to, ka mēs zinām, ka mēs atradām vēl vienu vārdu
vārdnīcu un mēs solis vēlreiz.
Tāpēc mēs turpinām darām līdz fscanf beidzot atgriežas kaut kas nav 1 pie
Kurā brīdī atcerēties, ka mums ir nepieciešams, lai bezmaksas ieeja, tāpēc šeit mēs malloced
ierakstu, un mēs mēģinājām lasīt kaut ko no vārdnīcas.
Un mēs neesam veiksmīgi nolasīt kaut kas no vārdnīcas, kurā
gadījumā mums ir nepieciešams, lai atbrīvotu ierakstu, ka mēs nekad faktiski laisti hash tabulu
un beidzot pauze.
>> Kad mēs izcelties, mums ir nepieciešams, lai redzētu, labi, mēs esam izcelties, jo tur
bija kļūda lasot no lietas materiāliem, vai mēs esam izcelties, jo mēs nonācām
faila beigas?
Ja tur bija kļūda, tad mēs vēlamies atgriezties viltus jo slodze nebija
panākumus, un šajā procesā, mēs vēlamies izkraut visus vārdus, ka mēs lasām
iekšā un aizveriet vārdnīcas faila.
Pieņemot, ka mums izdosies, tad mēs vienkārši joprojām ir nepieciešams, lai aizvērtu vārdnīcu
failu, un visbeidzot atgriezties taisnība, jo mēs esam veiksmīgi ielādēta
vārdnīca.
Un tas ir tas, lai slodze.
>> Tāpēc tagad pārbaudiet, ņemot piekrauts hash tabulu, gatavojas izskatās šādi.
Lai pārbaudītu, tas atgriež bool, kas gatavojas, lai norādītu, vai
pagājis-in char * vārdu, vai pagājis-in virkne ir mūsu vārdnīcā.
Tātad, ja tas ir norādīts vārdnīcā, ja tas ir mūsu hash tabulu, mēs atgriezīsimies
taisnība, un, ja tā nav, mēs atgriezīsimies nepatiesa.
Ņemot vērā šo pagājis-in vārdu, mēs esam gatavojas hash vārdu.
>> Tagad svarīga lieta atzīt, ka slodzes, zinājām, ka visi
vārdi bija būs mazie burti, bet šeit, mēs neesam tik pārliecināts.
Ja mēs to apskatīt mūsu hash funkciju, mūsu hash funkcija faktiski
ir lowercasing katru rakstzīmi vārda.
Tāpēc neatkarīgi no kapitalizācijas Vārds, mūsu hash funkcija būs
atpakaļ to pašu indeksu neatkarīgi kapitalizācija ir tā, kā būtu
atpakaļ uz pavisam mazie burti versija vārda.
Labi.
>> Tātad tas ir mūsu indeksa.
Tas ir hash tabulu par šo vārdu.
Tagad šis cilpa notiek lai pār to saistīts saraksts
tas bija šajā indeksā.
Tāpēc paziņojums mums ir inicializēta ierakstu , lai norādītu uz minētā indeksa.
Mēs turpināsim, bet ieraksts nav nav vienāds NULL, un atcerieties, ka
atjauninot rādītāju mūsu saistīts sarakstā ieraksts ir vienāds ieraksts-> blakus, tāpēc ir
Mūsu pašreizējais sākumpunkts Nākamais punkts saistītajā sarakstā.
Labi.
>> Tātad uz katru ierakstu saistītajā sarakstā, mēs ejam, lai izmantotu strcasecmp.
Tas nav strcmp jo atkal mēs gribu darīt lietas lietu insensitively.
Tāpēc mēs izmantojam strcasecmp salīdzināt vārdu , kas tika pieņemts, lai šo funkciju
pret vārdu, kas ir šajā ierakstā.
Ja tas atgriež 0, tas nozīmē, ka tur bija spēles, un tādā gadījumā mēs vēlamies
atgriezties true.
Mēs veiksmīgi atraduši vārdu mūsu hash tabulā.
>> Ja nebija spēle, tad mēs esam dodas uz cilpu atkal un apskatīt
Nākamais ieraksts.
Un mēs turpināsim looping, bet tur Ir ieraksti šajā saistīta sarakstā.
Kas notiek, ja mēs pārkāpjam no šīs cilpa?
Tas nozīmē, ka mēs neesam atrast ierakstu, kas saskaņota šo vārdu, tādā gadījumā
mēs atgriežamies viltus, lai norādītu, ka mūsu hash tabulu neietvēra šo vārdu.
Un tas ir tas, lai pārbaudi.
Labi.
>> Tātad, pieņemsim to apskatīt lieluma.
Tagad lielums būs diezgan vienkāršs jo atceros, slodzes, katram vārdam
mēs noskaidrojām, mēs palielina globālās mainīgais hashtable_size.
Tā lielums funkcija ir tikai gatavojas atgriezties, ka globālās
mainīgs, un tas arī viss.
>> Beidzot, mums ir nepieciešams, lai izkrautu vārdnīca, kad viss ir izdarīts.
Tātad, kā mēs gatavojamies darīt?
Tieši šeit, mēs esam looping visā spaiņi mūsu hash tabulu.
Tāpēc ir NUM_BUCKETS kausi.
Un katram, kas saistīta saraksta mūsu hash galda, mēs ejam, lai cilpa pār
veselums saistītā saraksta atbrīvojot katru elementu.
Tagad, mums ir jābūt uzmanīgiem, tāpēc šeit mēs ir pagaidu mainīgo, kas ir
uzglabāšanas rādītāju uz nākamā elements saistītajā sarakstā.
Un tad mēs ejam uz brīvu pašreizējais elements.
>> Mums ir nepieciešams, lai pārliecinātos, mēs to darām, jo ​​mēs var ne tikai brīvi Pašlaik skatītās elements
un tad mēģināt piekļūtu nākamajai rādītāju jo, kad mēs atbrīvojušies to
atmiņa kļūst nederīgs.
Tāpēc mums ir nepieciešams, lai saglabātu apmēram rādītāju uz nākamais elements, tad mēs varam brīvi
strāvas elements, un pēc tam, mēs var atjaunināt Mūsu pašreizējais elements, lai norādītu
nākamais elements.
>> Mēs cilpas, bet tur ir elementi Šajā saistīts sarakstā.
Mēs darīsim, ka visiem, kas saistīti sarakstos hash tabulu, un pēc tam, kad mēs esam darījuši
ar to, ka mēs esam pilnīgi izkrauts hash tabulu, un mēs esam darījuši.
Tātad, tas ir neiespējami izkrauj kādreiz atgriezties viltus, un, kad mēs esam darīts, mēs
vienkārši atgriezties true.