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.