>> ROB BOWDEN: Sveiki.
Aš Robas, ir tegul maišos šis sprendimas iš.
Taigi čia mes ketiname įgyvendinti Apskritai maišos lentelė.
Mes matome, kad struct mazgas mūsų maišos lentelė atrodys tai.
Taigi jis ketina turėti char žodį masyvo dydis ilgis plius 1.
Nepamirškite 1 nuo didžiausios žodis žodyne yra 45
simbolių, tada mes ketiname reikia vieną papildomą požymį
Backslash 0.
>> Ir tada mūsų maišos lentelė kiekvienoje kibiras ketina saugoti
susijęs sąrašas mazgų.
Mes nedarome linijinė zondavimo čia.
Ir todėl, kad rodo į kitą elementas kibirą, mes turime
struct mazgas * šalia.
Štai ką mazgas atrodo.
Dabar čia yra deklaracija mūsų maišos lentelėje.
Ji ketina turėti 16.384 kibirus, bet šis skaičius tikrai ne klausimas.
Ir pagaliau, mes ketiname turėti pasaulinį kintamąjį hashtable_size, kuris
ketina pradėti ne kaip 0, ir tai ketina sekti kiek žodžių
buvo mūsų žodyną.
Gerai.
>> Taigi galime pažvelgti apkrovos išvaizdą.
Taigi pastebėti, kad apkrovos, jis grįžta bool.
Jūs grąžina true, jei ji buvo sėkmingai pakrauta ir false kitaip.
Ir tai trunka const char * žvaigždę žodyną, kuris yra žodynas
kad mes norime atidaryti.
Štai pirmas dalykas, mes ketiname daryti.
Mes ketiname fopen į žodyną skaityti, o mes ketiname turėti
įsitikinkite, kad ji pavyko todėl, jei jis grįžo NULL, tada mes ne
sėkmingai atidaryti žodyną ir mes turime grįžti klaidinga.
>> Tačiau darant prielaidą, kad jis sėkmingai padarė atidaryti, tada mes norime skaityti
žodynas.
Taigi neišmeskite apsisukimo kol mes radote priežastis išeiti iš šio
kilpa, kuri matysime.
Taigi neišmeskite kilpų, ir dabar mes ketiname į malloc vieną mazgą.
Ir, žinoma, mes turime patikrinti klaidų vėl todėl, jei mallocing nepavyko
ir mes norime iškrauti bet kokį mazgą, kad mes atsitiko malloc prieš, uždarykite
žodynas ir return false.
>> Tačiau ignoruojant, kad, darant prielaidą, mes pavyko, tada mes norite naudoti fscanf
skaityti vieną žodį iš mūsų žodyną į mūsų mazgas.
Taigi prisiminti, kad pradinio> žodis yra char Žodis buferio dydis ilgis plius
vienas, kad mes ketiname laikyti žodį in
Taigi fscanf ketina grįžti 1 tol, kol kaip ji galėjo sėkmingai skaityti
Žodis iš failo.
>> Jei kuri nors klaida įvyksta, ar mes pasiekiame failo pabaiga, jis nebus
grįžti 1 tokiu atveju, jei jis nėra grįžti 1, mes pagaliau suluš
iš šio while cikle.
Taigi matome, kad kai mes sėkmingai skaityti žodis į
pradinio> žodis, tada mes ketiname maišos kad žodis naudojant mūsų maišos funkciją.
Paimkime pažvelgti maišos funkcija.
>> Taigi jums nereikia tikrai reikia tai suprasti.
Ir iš tiesų, mes tiesiog iškedentas tai maišos funkciją iš interneto.
Vienintelis dalykas, kurį reikia pripažinti, kad tai mano const char * žodį
todėl imsis eilutę kaip įvesties ir grąžinant unsigned int kaip produkcija.
Taigi, kad viskas maišos funkcija, tai trunka įvesties, ji suteikia jums
rodyklė į maišos lentelėje.
Atkreipkite dėmesį, kad mes modding pagal NUM_BUCKETS taip maišos vertė sugrįžo
iš tikrųjų yra į hash lentelę, indeksas ir neindeksuoja už
Ribas masyvo.
>> Taigi, turint omenyje, kad maišos funkcija, mes ketiname maišos žodį, kad mes skaityti
iš žodyno ir tada mes ketiname naudoti, kad yra įterpti
įsigaliojimas maišos lentelėje.
Dabar Hashtable maišos yra dabartinė susijęs sąrašas maišos lentelės ir
tai labai gali būti, kad yra tik NULL.
Mes norime įterpti mūsų bendrovėms patekti į rinką pradžioje šio susijęs sąrašo, ir taip
mes ketiname turėti savo esamą įrašą atkreipia dėmesį į tai, kas maišos lentelė šiuo metu
punktų ir tada mes ketiname saugoti maišos lentelės prie maišos
dabartinis įrašas.
>> Taigi šios dvi linijos sėkmingai įterpti prie pradžios įrašas
susijęs sąrašas tuo indeksą maišos lentelėje.
Kai baigsime su tuo, mes žinome, kad mes rasti kitą žodį
žodynas ir mes prieaugio dar kartą.
Taigi, mes nuolat tai daryti, kad iki fscanf pagaliau grįžta kažką ne 1 metu
kuris taškas prisiminti, kad turime įėjimas nemokamas, todėl čia mes malloced
įrašas ir bandėme skaityti kažką iš žodyno.
Ir mes ne sėkmingai skaityti kažkas iš žodyno, kuriame
atveju turime išlaisvinti įrašą, kad mes niekada iš tikrųjų įdėti į maišos lentelė
ir galiausiai lūžta.
>> Kai mes išeiti, mes turime pamatyti, gerai, Ar mes išeiti, nes
buvo klaida skaitant iš failo, arba Ar mes išeiti, nes mes pasiekėme
failo pabaiga?
Jei ten buvo klaida, tada mes norime return false, nes krovinys nebuvo
sėkmės, ir į šį procesą, norime iškrauti visus žodžius, kad mes skaityti
ir uždaryti žodyno failą.
Darant prielaidą, kad mes iš tikrųjų pavyko, tada mes tiesiog vis dar reikia uždaryti žodyną
failą, ir galiausiai grąžina true, nes mes sėkmingai įkeltas
žodynas.
Štai ir viskas kroviniu.
>> Taigi, dabar patikrinti, nes pakrautas maišos lentelė, ketina atrodyti taip.
Taigi patikrinti, jis grįžta bool, kuris ketina nurodyti, ar
praėjo laikas char * žodžiu, ar praėjo laikas eilutė yra mūsų žodyną.
Taigi, jei tai yra žodyne, jei ji yra mūsų maišos lentelės, grįšime
tiesa, ir jei taip nėra, grįšime klaidinga.
Atsižvelgiant į tai praėjo laikas žodis, mes ketina koduoti žodį.
>> Dabar svarbiausias dalykas pripažinti, kad apkrovos, mes žinojome, kad visi
žodžiai buvo bus mažosios raidės, bet čia mes ne tokie tikri.
Jei mes atsižvelgti į mūsų maišos funkcija atrodo, mūsų maišos funkcija faktiškai
yra lowercasing kiekvieną simbolį žodžio.
Taigi, nepriklausomai nuo kapitalizacijos žodis, mūsų maišos funkcija ketina
grįžti tą patį indeksą kokia kapitalizacija yra taip, kaip turėtų
grąžinama visiškai mažosiomis raidėmis portalo žodį.
Gerai.
>> Štai mūsų indeksas.
Tai maišos lentelė šiuo žodžiu.
Dabar, tai for ciklas vyksta iki daugiau kaip susietą sąrašą
kad buvo tuo indeksu.
Taigi pastebėsite mes Inicijuojama įrašą atkreipti dėmesį į šio indekso.
Mes ketiname tęsti, o įrašo nėra nėra lygus NULL, ir prisiminti, kad
atnaujinti žymiklį mūsų susietą sąrašą įrašas Lygu įrašas-> kitas, todėl turi
dabartinis mūsų įvažiavimo į Kitas darbotvarkės punktas yra susijęs sąrašą.
Gerai.
>> Taigi kiekvieno susieto sąrašo įrašą, mes ketiname naudoti strcasecmp.
Tai ne strcmp nes vėlgi, mes noriu daryti tai, ko bylą insensitively.
Taigi mes naudojame strcasecmp palyginti žodį kad buvo perduota ši funkcija
prieš žodį, yra šio įrašo.
Jei ji grąžina 0, tai reiškia, kad buvo rungtynės, tokiu atveju mes norime
return true.
Mes sėkmingai surado žodis mūsų maišos lentelėje.
>> Jei ten buvo ne rungtynės, tada mes ketina kilpos ir vėl pažvelgti
Kitas įrašas.
Ir mes ir toliau Looping nors yra Įrašų šiame susijęs sąrašą.
Kas atsitiks, jei mes pertrauka iš čia už linijos?
Tai reiškia, kad mes ne rasti įrašą, atitiko šį žodį, tokiu atveju
mes return false nurodyti, kad mūsų maišos lentelė nebuvo šį žodį.
Štai ir viskas registruotis.
Gerai.
>> Taigi galime pažvelgti dydžio išvaizdą.
Dabar, dydis bus gana paprasta nes prisiminti, apkrova, už kiekvieną žodį
mes pastebėjome padidinamas pasaulio kintamasis hashtable_size.
Taigi dydis funkcija yra tik ketina grįžti, kad visuotinis
kintamasis, ir viskas.
>> Dabar pagaliau turime iškrauti žodynas kartą viskas daroma.
Taigi, kaip mes ketiname daryti?
Štai čia mes apsisukimo per visus kibirai mūsų maišos lentelėje.
Taigi yra NUM_BUCKETS kibirai.
Ir kiekvieną susietą sąrašą mūsų maišos stalas, mes ketiname kilpa per
visuma susietą sąrašą išlaisvina kiekvieną elementą.
Dabar, mes turime būti atsargūs, kad čia mes turėti laikiną kintamąjį, kad yra
saugoti žymiklį į kitą elementas susijęs sąrašą.
Ir tada mes ketiname nemokamai dabartinis elementas.
>> Mes turime būti tikri, kad mes darome tai, nes mes gali ne tik atlaisvinti einamųjų elemento
ir tada bandykite ir atidarykite kitą žymeklį nes kai mes išlaisvino jį
atmintis tampa negaliojančiu.
Taigi, mes turime išlaikyti aplink rodyklę į Kitas elementas, tada mes galime nemokamai
dabartinis elementas, ir tada mes galime atnaujinti mūsų dabartinis elementas rodo
kitas elementas.
>> Mes kilpa nors yra elementai Šiame susijęs sąrašą.
Mes padarysime, kad visais su sąrašais maišos lentelė, ir kai baigsime
su tuo, mes visiškai iškraunamas maišos lentelė, ir baigsime.
Todėl neįmanoma iškrauna kada return false, o kai baigsime mes
tiesiog grąžina true.