[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]