[Tónlist spila] 

ROB BOWDEN: Hæ. Ég er Rob. Og við skulum þessa lausn út. Svo hér erum við að fara að innleiða almenn borð. Við sjáum að strúktúr hnút af okkar Taflan er að fara að líta svona út. Svo það er að fara að hafa bleikju orð Fylki af stærðinni LENGD + 1. Ekki gleyma + 1, þar sem hámark orð í orðabókinni er 45 stafir. Og þá erum við að fara að þurfa einn auka eðli fyrir sviga núll. 

Og þá Hashtable okkar í hvert fötu er að fara að geyma tengda listanum hnúta. Við erum ekki að gera línuleg leit hér. Og svo í röð til að tengja við næsta þáttur í fötu, þurfum við að struct node * næst. OK. Svo er það sem hnúturinn lítur út. 

Nú er hér yfirlýsingin af Hashtable okkar. Það er að fara að hafa 16.834 fötunum. En þessi tala er í raun ekki máli. Og að lokum, við erum að fara að hafa Global breyta Hashtable stærð, sem er að fara að byrja á núll. Og það er að fara að halda utan um hvernig mörg orð eru í orðabók okkar. 

Þannig að við skulum taka a líta á hleðslu. Taka eftir því að hlaða, skilar það sér bool. Þú skilar true ef það var með góðum árangri hlaðinn og ósönn annars. Og það tekur const char * orðabók, sem er orðabókinni að við viljum að opna. Svo er það fyrsta sem við erum að fara að gera. 

Við erum að fara að fopen á orðabók fyrir lestur. Og við erum að fara til verða að gera viss um að það tókst. Þannig að ef það skilaði engu, svo við gerðum ekki tókst að opna orðabók. Og við þurfum að skila falskur. En miðað við að það gerði með góðum árangri opinn, þá viljum við að lesa orðabók. Svo halda lykkja þar til við að finna nokkrar ástæða til að brjótast út úr þessu lykkju, sem við munum sjá. Svo halda lykkja. 

Og nú erum við að fara að malloc einum hnút. Og auðvitað þurfum við að loft athuga aftur. Svo ef mallocing ekki tekist, þá við viljum að afferma allir hnút sem við gerðist að malloc áður, loka orðabók og aftur ósatt. En hunsa það, miðað við tekist, þá viljum við nota fscanf til að lesa eitt orð frá okkar orðabók í hnút okkar. Svo muna að Entry> orð er bleikjan orð biðminni stærð LENGHTH + 1 að við erum að fara að geyma orð inn 

Svo fscanf er að fara að skila 1, svo lengi eins og það var fær til giftusamlega lesa orð úr skrá. Ef annað hvort villa kemur, eða við ná sambandi við lok skrárinnar, það mun ekki skila 1. Í því tilviki er það ekki aftur 1, við erum loksins að fara að brjótast út úr þetta á meðan lykkja. Svo við sjáum að þegar við höfum tekist lesa orð í innganga> orð, þá erum við að fara að því orð með kjötkássa virka okkar. 

Láta 'taka a líta á kjötkássa virka. Svo þú þarft ekki raunverulega þörf að skilja þetta. Og reyndar við dregið bara þessa hass virka af internetinu. Það eina sem þú þarft að viðurkenna er að þetta tekur const char * orð. Svo það tekur a band sem inntak, og aftur óundirritaður INT sem framleiðsla. Svo er það allt a kjötkássa virka er, er það tekur í inntak og gefur þér Vísitala inn Hashtable. 

Takið eftir að við erum moding með NUM_BUCKETS, þannig að gildi aftur reyndar er vísitölu í Hashtable og ekki vísitölu handan mörk í fylkinu. Svo í ljósi þess virka, við erum að fara til kjötkássa orð sem við lesum orðabók. Og þá erum við að fara að nota sem kjötkássa að settu Gildistaka Hashtable. 

Nú Hashtable kjötkássa er núverandi tengda listanum í töflunni. Og það er mjög líklegt að það er bara NÚLL. Við viljum setja færslu okkar á byrjun þessa tengda listanum. Og svo við erum að fara að hafa núverandi okkar innganga benda á það sem Hashtable nú bendir til. Og þá erum við að fara að geyma, í Hashtable á að hass, núverandi færslu. Svo þessar tvær línur tókst setja færslunnar í upphafi að tengda listanum á vísitölunni í Hashtable. 

Þegar við erum búin með það, við vitum að við fundum annað orð í orðabók, og við stighækkun aftur. Svo við höldum að gera það fyrr en fscanf að lokum skilað eitthvað non-1 á sem lið muna að við þurfum að losa færslu. Svo upp hér við malloced færslu. Og við reyndum að lesa eitthvað úr orðabókinni. Og við fengum ekki tekist að lesa eitthvað úr orðabókinni, í en þá þurfum við að losa færslu sem við aldrei raunverulega setja inn í Hashtable, og að lokum brjóta. 

Þegar við brjótast út við þurfum að sjá, vel, höfum vér brjótast út vegna þess að það var að villa við lestur úr skránni? Eða höfum vér brjótast út vegna þess að við náð í lok skrárinnar? Ef það kom upp villa, þá við viljum return false. Vegna hlaða tókst ekki. Og í því ferli sem við viljum að afferma öll þau orð, sem við lesum í, og loka orðabók skrá. 

Miðað við hafi tekist, þá erum við bara enn þurft að loka orðabók skrá, og að lokum aftur satt þar sem við Það tókst að hlaða orðabókinni. Og það er það að hlaða. Svo nú athugað, í ljósi hlaðinn Hashtable, er að fara að líta svona út. Svo stöðva það skilar bool, sem er fara til kynna hvort liðið í char * orði, hvort liðin í band er í orðabók okkar. Þannig að ef það er í orðabókinni, ef það er í Hashtable okkar, við munum fara aftur satt. Og ef það er ekki, munum við aftur ósatt. 

Í ljósi þessa samþykkt í orði, við erum fara að kjötkássa orðið. Nú er mikilvægt að viðurkenna að í álagi við vissum að allir sem orð sem við ætlum að vera lágstöfum. En hér erum við ekki svo viss. Ef við lítum á kjötkássa virka okkar, kjötkássa virka okkar í raun er lægra hlíf hvert eðli orðsins. Svo óháð fjármögnun orð, kjötkássa virka okkar er aftur sama vísitölu hvað sem hástafanotkun er, eins og það myndi hafa aftur fyrir alveg lágstafir útgáfa af orðinu. Allt í lagi. Það er vísitala okkar er inn í Hashtable fyrir þetta orð. 

Nú þetta fyrir lykkja er að fara að iterate yfir tengda listanum sem var á vísitölunni. Svo taka við erum Frumstilli færslu til að benda á vísitölunni. Við erum að fara að halda áfram en innganga = null. Og muna að uppfæra músina í tengda listanum innganga okkar = færsla> næst. Svo hafa núverandi innganga okkar benda til Í næsta atriði í tengda listanum. 

Svo fyrir hverja færslu í tengda listanum, við erum að fara að nota strcasecmp. Það er ekki strcomp. Því enn og aftur, við viljum gera hlutina mál insensitively. Svo við notum strcasecmp að bera saman Orðið sem var samþykkt í gegnum þetta virka gegn orði sem er í þessari færslu. Ef það skilar núll, sem þýðir að það var leik, en í því tilviki sem við viljum return true. Við fundum tókst að orð í Hashtable okkar. 

Ef það var ekki passa, þá erum við fara að lykkja aftur og líta á Next Entry. Og við munum halda áfram að lykkja á meðan það eru færslur í þessum tengda listanum. Hvað gerist ef við brjóta út af þessu fyrir lykkju? Það þýðir að við vildum ekki fundið færslu sem samþykkt þetta orð, en í því tilviki við aftur ósatt að benda að okkar Hashtable ekki innihalda þetta orð. Og það er ávísun. 

Þannig að við skulum taka a líta á stærð. Nú stærð er að fara að vera nokkuð einfalt. Þar muna í álag, fyrir hvert orð við fundum, við hækkaða alþjóðlegt breytu Hashtable stærð. Þannig að stærð virka er bara að fara til að fara aftur alþjóðlegum breytu. Og það er það. 

Nú loksins, þurfum við að afferma orðabók þegar allt er gert. Svo hvernig eigum við að fara að gera það? Hérna erum við lykkja yfir allar fötunum borðinu okkar. Þannig að það eru NUM_BUCKETS fötunum. Og fyrir hvert tengda listanum í okkar Hashtable, þá ætlum við að lykkja yfir heild á tengda listanum, frjáls hvert frumefni. 

Nú þurfum við að fara varlega. Svo hér höfum við tímabundna breytu sem er að geyma músina til næsta þáttur í tengda listanum. Og þá erum við að fara að losa núverandi þáttur. Við þurfum að vera viss um að við gerum þetta því vér getur ekki bara losa Opin ELEMENT og reyna svo að sjá næsta músina, síðan þegar við höfum frelsi það, minni verður öryrki. 

Þannig að við þurfum að halda í kring bendi á næsta þátt, þá getum við frjálsari núverandi þáttur, og þá getum við uppfært Núverandi þáttur okkar til að benda á næsta þátt. Við munum lykkja en það eru þættir í þessu tengda listanum. Við munum gera það fyrir alla tengda listum Hashtable. Og þegar við erum búin með það, höfum við alveg skipað Hashtable og við erum búin. Svo það er ómögulegt fyrir afferma að alltaf return false. Og þegar við erum búin, við bara aftur satt. 

Við skulum gefa þessa lausn a reyna. Þannig að við skulum taka a líta á það sem okkar struct hnút mun líta út. Hér sjáum við að við erum að fara að hafa bool orð og strúktúr node * börn krappi stafrófinu. Svo það fyrsta sem þú gætir verið spá, hvers vegna er ALPHABET Ed skilgreint sem 27? Jæja, muna að við erum að fara að þurfa að vera meðhöndlun úrfellingarmerki. Svo það er að fara að vera nokkuð sérstakt tilfelli í þessari áætlun. 

Nú man hvernig trie í raun virkar. Segjum að við erum flokkun orð "kettir." Þá frá rót trie, við erum að fara að horfa á börnin array, og við erum að fara að líta á Vísitala sem svarar til bréf C. Svo að verða verðtryggð 2. Svo í ljósi þess, sem mun gefa okkur nýja hnút. Og þá munum við vinna úr þeim hnút. 

Svo í ljósi þess hnút, erum við enn og aftur fara að horfa á börnin fylkisins. Og við erum að fara að horfa á vísitölu núll að vinna í samræmi við A í cat. Svo þá erum við að fara að fara til hnút, og í ljósi þess að hnúturinn við erum að fara að líta á the endir það er sem a til T. og færa til þess hnút, Að lokum, höfum við alveg leit gegnum orð okkar "köttur." Og nú bool Orðið er ætlað að gefa til kynna hvort þetta gefið orð er í raun orð. 

Svo hvers vegna þurfum við að sérstakt tilfelli? Jæja hvað um orðið "stórslys" er í orðabók okkar, en Orðið "köttur" er það ekki? Svo og að leita að sjá hvort orðið "köttur" er í orðabók okkar, við erum fara að tókst að líta í gegnum Vísitölurnar C-A-T í svæðinu hnút. En það er einungis vegna þess að stórslys gerðist að búa hnútar á leiðinni úr C-A-T, alla leið til enda orðsins. Svo bool orðið er notað til að gefa til kynna hvort þetta tiltekna staðsetningu reyndar táknar orð. 

Allt í lagi. Svo nú er að við vitum hvað það trie er að fara að líta út eins og, við skulum líta á hlaða virka. Svo álag er að fara að skila bool fyrir hvort við góðum árangri eða árangurslaust hlaðinn orðabókin. Og þetta er að fara til vera the orðabók að við viljum að hlaða. 

Svo fyrsta sem við erum að gera er opinn upp þessi orðabók fyrir lestur. Og við verðum að ganga úr skugga um við gerðum ekki mistakast. Þannig að ef orðabók væri ekki tókst opnaði, það mun skila null, í því tilviki sem við erum fara að skila falskur. En miðað við að það tókst opnaði, þá getum við í raun lesið gegnum orðabókina. 

Svo fyrsta sem við erum að fara að vilja til að gera er að við höfum þetta Global breyta rót. Nú rót er að fara til vera a node *. Það er efst á trie okkar sem við erum að fara að iterating gegnum. Svo the fyrstur hlutur sem við erum að fara til að vilja gera er að úthluta minni rót okkar. Takið eftir að við erum að nota calloc virka, sem er í grundvallaratriðum það sama sem malloc virka, nema það er tryggingu til að fara aftur eitthvað sem er alveg zeroed út. Þannig að ef við notuðum malloc, vildi að við þurfum að fara í gegnum öll ábendingum í okkar hnút, og ganga úr skugga um að þeir eru allir null. Svo calloc mun gera það fyrir okkur. 

Nú bara eins malloc, þurfum við að gera úr skugga um að úthlutun var í raun vel. Ef þetta aftur null, þá erum við þurft að loka eða orðabók skrá og aftur ósatt. Svo miðað við að úthlutun var vel, við erum að fara að nota hnút * bendilinn iterate gegnum trie okkar. Svo rætur okkar aldrei að fara að breyta, en við erum að fara að nota bendilinn til reyndar fara frá hnút í hnút. 

Svo í þetta fyrir lykkju við erum að lesa gegnum orðabók skrá. Og við erum að nota fgetc. Fgetc er að fara að grípa einn eðli úr skrá. Við erum að fara að halda áfram grabbing stafir á meðan við ná ekki lok skrárinnar. 

Það eru tvö tilvik sem við þurfum að sinna. Fyrsta, ef eðli var ekki ný lína. Þannig að við vitum ef það væri ný lína, þá við erum að fara að hreyfa á til nýtt orð. En miðað við það var ekki ný línu, þá Hér viljum við að reikna út vísitölu sem við erum að fara að kemba í í börnin fylkingu sem við skoðuðum áður. 

Svo, eins og ég sagði áður, þurfum við að sérstakt tilfelli úrfellingarmerki. Taka við erum með ternary Rekstraraðili hér. Þannig að við erum að fara að lesa þetta eins og, ef eðli sem við lesum í var úrfellingarmerki, þá erum við að fara að setja Vísitala = "ALPHABET" -1, sem mun vera vísitala 26. 

Annars, ef það var ekki úrfellingarmerki, þar við erum að fara að setja vísitölu jöfn c - a. Svo man aftur frá áður p-setur, c - a er að fara að gefa okkur stafrófsröð stöðu C. Svo ef C er bókstafurinn A, þetta verður gefa okkur vísitölu núll. Fyrir stafinn B, mun það gefa okkur vísitalan 1, og svo framvegis. 

Svo það gefur okkur vísitölu inn í börn array sem við viljum. Nú ef þessi vísitala er nú null í börnin, sem þýðir að hnúturinn ekki fyrir hendi frá þeirri braut. Þannig að við þurfum að úthluta hnút í þeirri braut. Það er það sem við munum gera hér. 

Þannig að við erum að fara að aftur nota calloc virka, þannig að við þurfum ekki að núll út allar ábendingar. Og við þurfum aftur að athuga að calloc ekki mistakast. Ef calloc gerði ekki, þá þurfum við að afferma allt, loka okkar orðabók, og return false. Svo miðað við að það var ekki mistakast, þá þetta mun búa til nýtt barn fyrir okkur. Og þá munum við fara til barnsins. Bendillinn okkar mun kunnugt er niður til að barnið. 

Nú ef þetta var ekki null til að byrja með, þá bendillinn getur bara iterate niður til að barnið án þess að raunverulega að þurfa að úthluta neitt. Þetta er raunin þar sem við gerðist fyrst úthluta orðið "köttur". Og sem þýðir að þegar við förum að úthluta "Stórslys," við þurfum ekki að búa til hnúta fyrir C-A-T aftur. Þeir eru fyrir hendi nú þegar. 

Hvað er þetta annað? Þetta er ástand þar sem C, var sviga n, þar sem C, var nýja línu. Þetta þýðir að við höfum tekist lokið orð. Nú hvað við viljum gera þegar við lokið orð? Við erum að fara að nota þetta orð reit inni strúktúr hnút okkar. Við viljum að setja það satt. Svo gefur til kynna að þessi hnútur sýnir vel orð, í raun orðið. 

Nú setja það satt. Við viljum að endurstilla bendilinn okkar lið að upphafi trie aftur. Og að lokum, vöxtur orðabók okkar stærð, þar sem við fundið aðra vinnu. Þannig að við erum að fara að halda að gera það, lestur í staf með staf, byggja nýja hnúta í trie okkar og fyrir hvert orð í orðabók, þar við náum loks C! = EOF, þar sem ræða við brjótast út úr skránni. 

Nú eru tvö tilvik undir sem við gætum hafa högg EOF. Fyrsta er ef það var villa lesa úr skrá. Þannig að ef það var villa, við þarft að gera dæmigerð. Afferma allt, nærri skráin, return false. Miðað við að það var ekki villa, að bara þýðir að við högg í raun enda skráin, í því tilviki, nálægt við á skrá og skila satt þar sem við tókst hlaðinn orðabók í trie okkar. 

Svo nú skulum kíkja stöðva. Útlit á the stöðva virka, sjáum við að stöðva er að fara að skila bool. Það skilar satt ef þetta orð að það er berist er í trie okkar. Það skilar ósönn annars. Svo hvernig ætlar þú að ákveða hvort þetta orð er í trie okkar? 

Við sjáum hér að, rétt eins og áður, við erum að fara að nota bendilinn til iterate gegnum trie okkar. Nú hér erum við að fara að iterate yfir öllu orð okkar. Svo iterating yfir orð sem við erum fortíð, við erum að fara að ákveða Vísitala í börnin fylkingu sem samsvarar orðinu krappi I. Þannig að þetta er að fara að líta nákvæmlega eins og álag, þar sem ef orð [i] er úrfellingarmerki, þá viljum við að nota vísitölu "stafrófi" - 1. Vegna þess að við ákveðið að það er þar sem við erum að fara að geyma úrfellingarmerki. 

Annað sem við erum að fara að nota tvær minni orð krappi I. Svo muna að orð getur hafa handahófi fjármögnun. Og svo við viljum tryggja að við erum nota lágstafir útgáfa af hlutum. Og þá draga úr því að 'a' til einu sinni aftur gefa okkur í stafrófsröð stöðu að eðli. Svo það er að fara að vera vísitölu okkar í Börnin fylkisins. 

Og nú ef að vísitalan í börnin array er núll, sem þýðir að við getur ekki lengur haldið áfram iterating niður trie okkar. Ef það er málið, þetta orð er ekki hægt hugsanlega verið í trie okkar. Síðan ef það væri, sem myndi meina það væri leið niður að því orði. Og þú myndi aldrei lenda null. Svo hitta null aftur við rangar. Er orðið ekki í orðabókinni. Ef það væri ekki null, þá erum við fara að halda áfram iterating. 

Þannig að við erum að fara út þar bendilinn til að benda á að einkum hnút á vísitölunni. Við halda að gera það í gegn allt orðið, miðað við aldrei högg null. Það þýðir að við gátum til að komast í gegnum allt orð og finna hnút í okkar reyna. En við erum ekki alveg búin ennþá. 

Við viljum ekki bara koma aftur satt. Við viljum skila bendilinn> Word. Þar sem man aftur, er "köttur" er ekki í orðabók okkar, og "stórslys" er, þá munum við vel okkur fá gegnum orðið "köttur". En bendillinn orð mun vera rangar og ekki satt. Þannig að við aftur bendilinn orð til að sýna hvort þetta hnútur er í raun orð. Og það er það að athuga. 

Þannig að við skulum kíkja stærð. Svo stærð er að fara að vera nokkuð auðvelt síðan, man í álag, við erum incrementing orðabók stærð fyrir hvert orð sem við lendum. Svo stærð er bara að fara að aftur orðabók stærð. Og það er það. 

Svo loksins við höfum afferma. Svo afferma, við erum að fara að nota endurkvæma virka til raunverulega gera allt af vinnu fyrir okkur. Svo virka okkar er að fara að kallað á Unloader. Hvað er Unloader að fara að gera? Við sjáum hér að Unloader er að fara að iterate yfir öll börn á Þetta tiltekna hnút. Og ef barnið hnút er ekki null, þá erum við að fara að afferma barn hnút. 

Svo er þetta sem þú afferma endurkvæmt öll börnin okkar. Þegar við erum viss um að öll börn okkar hafa verið skipað, þá erum við geta losa okkur, svo afferma okkur. Þetta mun vinna endurkvæmt afferma alla trie. Og síðan einu sinni það er gert, getum við bara aftur satt. Afferma getur ekki mistekist. Við erum bara frjáls hluti. Svo þegar við erum búin frjáls allt aftur satt. Og það er það. Mitt nafn er Rob. Og þetta var Speller. 

[Tónlist spila]