>> Ræðumaður 1: Við skulum gefa Þessi lausn að reyna.
Þannig að við skulum taka a líta á það sem okkar Strúktúr hnút mun líta út.
Hér sjáum við að við erum að fara að hafa Bool Word og Struct hnút stjörnu
Börn krappi stafrófið.
Svo fyrsta sem þú gætir verið að spá, hvers vegna er stafrófið kjötkássa skilgreind 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 allt til þessarar áætlunar.
>> OK, nú, muna hvernig Trie virkar í raun.
Segjum að við erum flokkun á orð ketti, þá frá rót Trie okkar,
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ð væri Vísitala tvö.
Svo í ljósi þess, sem mun gefa okkur ný 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 fylking,
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út, við erum að fara
að líta á vísitölu sem svarar til T. og færa til þess hnút,
Að lokum, höfum við alveg leit gegnum orð kötturinn okkar, 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ð ef orðið stórslys er í orðabók okkar, en
orðið köttur er það ekki?
Svo í að leita að sjá hvort orð kötturinn er í orðabók okkar, við erum að fara að
tókst að líta í gegnum skránna C-A-T og ná hnút, en það er
aðeins vegna stórslys gerðist að búa til hnútar á leiðinni frá C-A-T allan
leið til the endir af the orð.
Svo bool Word er notað til kynna hvort þetta tiltekna staðsetningu raun
táknar orð.
>> Allt í lagi, svo nú að við vitum hvað Trie er að fara að líta út eins og, við skulum líta
á álaginu virka.
Svo Load er að fara að skila bool fyrir hvort við góðum árangri eða
árangurslaust hlaðinn orðabók og þetta er að fara til vera the orðabók
að við viljum að hlaða.
Svo fyrsta sem við ætlum að gera er að opna upp þessi orðabók fyrir lestur.
Við verðum að tryggja að við ekki mistakast, þannig að ef orðabók væri ekki
tókst opnaði, það mun skila Nei, en í því tilviki sem við erum að fara að
return false.
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 hnút stjörnu.
Það er efst á Trie okkar sem við erum að fara að iterating gegnum.
Svo fyrsta sem við erum að fara til að vilja gera er að úthluta minni fyrir 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 tryggja að þeir eru allir null.
Svo Calloc mun gera það fyrir okkur.
>> Nú, rétt eins og Malloc, þurfum við að gera úr skugga um að úthlutun er í raun
vel.
Ef þetta aftur null, þá erum við þarf að loka orðabók okkar
skrá og skila False.
Svo miðað við úthlutun var vel, við erum að fara að nota hnút
stjörnu bendilinn til iterate gegnum Trie okkar.
Svo rót okkar er aldrei að fara að breytast, en við erum að fara að nota bendilinn til
reyndar fara frá hnút í hnút.
>> Allt í lagi, svo í þetta fyrir lykkju, við erum lesa í gegnum orðabók skrá,
og við erum að nota á fgetc.
Svo 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, þannig að það eru tveimur tilvikum við þurfum að sinna.
Fyrsta, ef eðli var ekki Ný lína, þannig að við vitum hvort það var ný
lína, þá erum við 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 í í barna 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ðila hér, þannig að við erum að fara að lesa
þetta eins og ef eðli við lesið í var úrfellingarmerki, þá erum við að fara að
setja vísitölu jöfn stafrófið mínus 1, sem verður vísitala 26.
Annars, ef það var ekki úrfellingarmerki, þá erum við að fara að láta vísitölu
jafnt c mínus.
Svo man aftur frá fyrri p setur, c mínus er að fara að gefa okkur
stafrófsröð staða c, þannig að ef c er bókstafurinn A, þetta mun
gefa okkur vísitölu núll.
Fyrir stafinn B, það myndi gefa okkur vísitalan 1, og svo framvegis.
>> Svo það gefur okkur vísitölu inn í Börn array sem við viljum.
Nú, ef þetta vísitölu er nú null í the Children array, sem þýðir að
hnút ekki fyrir hendi úr sem leið, þannig að við þurfum að úthluta
hnút í þeirri braut.
Það er það sem við gerum hér.
Þannig að við ætlum að, aftur, nota Calloc virka þannig að við höfum ekki
til núll út allar ábendingum, og við, aftur, þarf 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 að ú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.
>> OK, 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ð á True, svo að gefur til kynna að þetta hnútur táknar
vel orðið raunveruleg orð.
Nú, setja það til True.
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ð fundum annað orð.
>> Allt í lagi, þannig að við erum að fara að halda að gera að lesa í staf með
eðli, byggingu nýja hnúta í Trie okkar og fyrir hvert orð í
orðabók, þangað til við komum að lokum c jafngildir EOF, í því tilviki, brot við
út af skránni.
Nú, það 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, þurfum við að gera dæmigerð afferma allt, loka skrá,
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.
>> Allt í lagi, svo nú skulum kíkja stöðva.
Þegar litið er á the stöðva virka, sjáum við að stöðva er að fara að skila bool.
Það skilar True ef þetta orð að það er berist er í Trie okkar.
False annað.
>> Svo hvernig eigum við að fara 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 liðin, 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ð krappi ég er
úrfellingarmerki, þá viljum við nota vísitölu stafrófið mínus 1 vegna þess að við ákveðin
það er þar sem við erum að fara að geyma úrfellingarmerki.
>> Annað sem við erum að fara að nota tolower Orðið krappi i.
Svo muna að orð geta haft handahófskennt fjármögnun, og svo við
vilja til að ganga úr skugga um að við erum að nota A lágstafir útgáfa af hlutum.
Og þá draga úr því lágstafir a til að, enn og aftur, gefa okkur
stafrófsröð staða þeirrar persónu.
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, því ef það
voru, sem myndi þýða að það væri Slóðin niður í þessi orð, og þú myndir
aldrei lenda null.
Svo hitta null aftur við False.
Er orðið ekki í orðabókinni.
Ef það væri ekki null, þá erum við að fara að áfram iterating, þannig að við erum að fara
að uppfæra bendilinn okkar til að benda á að einkum hnút í vísitölunni.
>> Svo við höldum að gera það í gegn allt orðið.
Miðað við högg aldrei null, sem þýðir við gátum til að komast í gegnum allt
heimurinn og finna hnút í Trie okkar, en við erum ekki alveg búin ennþá.
Við viljum ekki bara koma aftur True.
Við viljum skila bendilinn villa orð síðan, man aftur, ef kötturinn er ekki
í orðabók okkar og stórslys er, þá munum við tekist að komast í gegnum
orðið köttur, en bendillinn orð verður falskur 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ð fara aftur orðabók stærð, og það er það.
>> Allt í lagi, svo loksins, höfum við 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ð vera kölluð 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ð tengipunktur er ekki núll, þá erum við að fara að
afferma barn hnút.
>> Þannig að þetta er að fara til endurkvæmt afferma ö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 sjálf.
Þannig að þetta verður endurkvæmt afferma Öllu Trie, og þá einu sinni sem er
gert, getum við bara aftur True.
Afferma getur ekki mistekist, við erum bara frjáls hluti.
Svo þegar við erum búin frjáls allt aftur True.
Og það er það.
Mitt nafn er Rob, og þetta var [inaudible].