>> ZAMYLA Chan: Tehdään oikeinkirjoituksen tarkistus.
Jos avaat speller.c, niin näet että useimmat toiminnot
tarkkailun tekstitiedosto vastaan sanakirja on jo tehty sinulle.
. / Speller, ohimennen sanakirjassa teksti tiedoston ja sitten toinen tekstitiedosto,
tarkistaa, että tekstitiedoston vastaan ​​sanakirja.
>> Nyt, sanakirja tekstitiedostoja sisältää voimassa sanaa, yksi kullekin riville.
Sitten speller.c soittaa Load on sanakirja tekstitiedosto.
Se soitan toiminto nimeltään tarkastaminen jokainen sana syötetyn tekstitiedosto,
tulostaa kaikki väärin kirjoitetut sanat.
>> Speller.c myös soittaa koko- määrittää sanojen määrä
sanakirja ja soita Unload vapauttaa muistia.
speller.c myös seurata, kuinka paljon aikaa avulla tehdään näiden
prosesseja, mutta me päästä siihen myöhemmin.
>> Joten mitä meidän pitää tehdä?
Meidän täytyy täyttää dictionary.c.
Vuonna dictionary.c, meillä on auttaja toiminto Load, joka lataa
sanakirja.
Toimintojen tarkistus, joka tarkistaa, jos tiettyä sanaa on sanakirjassa.
Funktio Koko palauttaa luvun sanoja sanakirjasta.
Ja lopuksi, olemme Pura, joka vapauttaa sanakirja muistista.
>> Joten ensin on puuttua Load.
Jokaisen sanan sanakirjasta tekstissä tiedosto, Load tallentaa näitä sanoja
sanakirjassa tietorakenne valitsemaltasi joko
hash taulukon tai triellä.
Menen aikana sekä Tämän kulkea.
>> Katsotaanpa ensin puhua hash taulukoita.
Sano sinä olisit säästänyt 10 biljardi pallot ja halusit tallentaa ne.
Saatat laittaa ne kaikki ämpäri, ja kun tarvitaan tietyn
numeroitu pallo, ottaisit yhden ulos ämpäri kerrallaan
etsivät että pallo.
Ja vain 10 palloa, sinun pitäisi olla pystyä löytämään pallo kohtuullisen
aikaa.
>> Mutta mitä jos sinulla olisi 20 pallot?
Se saattaa kestää hieman kauemmin nyt.
Entä 100?
1000?
Nyt, se olisi paljon helpompaa, jos sinulla oli useita kauhat.
Ehkä yksi ämpäri palloja numeroitu nolla yhdeksään, toinen kauha
numeroitua palloa 10 kautta 19, ja niin edelleen.
>> Nyt kun sinun piti etsiä tiettyjä pallo, voisit automaattisesti
mene johonkin tiettyyn ämpäri ja etsiä että ämpäri.
Ja jos jokainen ämpäri on noin 10 pallot, niin voit helposti etsiä
läpi.
>> Nyt, koska olemme tekemisissä sanakirjoja, yhden kauhan
kaikki sanat sanakirja todennäköisesti aivan liian vähän kauhat.
Joten katsotaanpa katsomaan hash taulukoita.
>> Ajattele sitä erilaisia ​​kauhoja.
Ja tässä tapauksessa, kauhat ovat meidän linkitettyjä listoja.
Ja jaamme kaikki sanamme näiden joukossa useita linkitettyjä luettelot
järjestäytyneesti käyttäen tiivistefunktiota, joka kertoo meille, mitkä
ämpäri tietyn avaimen, tietyn sana, kuuluu.
>> Katsotaanpa edustamaan tätä kaavamaisesti.
Siniset laatikot tässä on arvoja, ja punainen laatikot paikasta toiseen arvoon
osoitin pari.
Me kutsumme näitä paria solmuja.
Nyt jokainen ämpäri, kuten sanoin aikaisemmin, on linkitetty lista.
Vuonna linkitettyjä listoja, jokainen solmu on arvo, sekä osoitin
seuraavan arvon.
>> Nyt tekemisissä liittyvät luettelot, se on erittäin tärkeää, että
älä hävitä linkkejä.
Ja toinen tosiasia on muistaa, että viime solmu, jos se ei osoita
toisen solmun, viittaa null.
>> Miten siis edustamaan tätä C?
Määrittelemme struct täällä.
Ja arvo on tässä tapauksessa char array pituuden.
Pituus plus 1, jossa pituus on Pisin tahansa sana, plus 1
null terminaattori.
Ja sitten meillä on osoitin toisen solmun nimeltä Next.
>> Joten tehdä pienen linkitetty lista.
Ensinnäkin, sinun kannattaa malloc teidän solmuun, jotka luovat tilaa muistissa
kokoa solmun tyyppiä.
Ja tee uusi solmu, jälleen mallocing.
>> Nyt jos haluat antaa arvoa sana, niin voisimme sanoa node1 arrow
sana vastaa "Hei." Tämä nuoli operaattori dereferences osoitin ja
sisäänkäyntien struct: n muuttujia.
Näin meidän ei tarvitse käyttää molempia dot ja tähti operaattori.
>> Niin sitten minulla on node2 nuoli sana vastaa "Maailmassa." Ja siellä, arvot ovat
asutuilla minun solmut.
Jotta linkkejä, minä kulkea node1 nuolta, saatavuuden että solmu tähti,
että solmu osoitin, vastaa node2, osoittaa node1 to node2 kaksi.
Ja siellä meillä on linkitetty lista.
>> Joten se oli vain yksi linkitetty lista, mutta tiiviste on koko joukon
linkitettyjä listoja.
No, meillä on sama solmu rakenne kuin ennen.
Mutta jos halusimme todellinen tiiviste, voimme vain tehdä solmu osoitin
array täällä.
Esimerkiksi koko 500.
>> Nyt ilmoitusta, siellä tulee olemaan kaupan pois välillä kokoa
tiiviste ja koko oman linkitettyjä listoja.
Jos sinulla on todella suuri määrä kauhat, kuvitellen ottaa juosta takaisin
ja esiin linja löytää ämpäri.
Mutta et myöskään halua pieni määrä kauhat, koska silloin olemme takaisin
alkuperäinen ongelma, miten ottaa liian monta palloa meidän ämpäri.
>> OK, mutta mistä meidän pallo mennä?
No, meidän on ensin on pallo, eikö?
Joten malloc solmu jokaista uusi sana, että meillä on.
solmu * new_node tasavertaisina malloc (sizeof (solmu)).
>> Nyt kun meillä on tämä rakenne, me voi skannata funktion
fscanf, string meidän tiedoston, jos se on sanakirja-tiedosto,
new_node nuoli sana, jossa new_node nuoli sana on meidän
määränpää tämä sana.
>> Seuraavaksi me haluamme hash että sana käyttämällä hash-funktiota.
Hajautusfunktio vie merkkijonon ja palauttaa indeksin.
Tässä tapauksessa indeksi on olla pienempi kuin määrä
kauhat, että sinulla on.
>> Nyt hajautusfunktioita, kun yrität löytää ja luoda yksi
oman, muista, että ne täytyy olla deterministinen.
Tämä tarkoittaa, että sama arvo on kartta samaan ämpäri joka kerta
että olet hash sitä.
>> Se on tavallaan kuin kirjasto.
Kun otat kirjan, joka perustuu kirjailija, tiedät mikä hylly pitääkin
mennä, onko se hyllynumero yksi, kaksi tai kolme.
Ja että kirja kuuluvat aina päällä joko hylly yksi, kaksi tai kolme.
>> Joten, jos new_node nuoli sanalla on sanan sanakirjaa sitten
hajautusta new_node arrow sana antaa meille indeksi
ämpäri tiiviste.
Ja sitten me lisätä, että tuohon erityiset linkitetty lista merkitty
palata arvoa meidän hajautusfunktio.
>> Katsotaanpa esimerkki lisäämällä solmun
alussa linkitetyn listan.
Jos pää on solmu osoitin, joka ilmaisee alussa linkitetty
luettelosta ja new_node osoittaa uusi solmu, joka haluat päästä sisälle, vain
osoitetaan pään new_node menettäisi linkki muuhun luettelosta.
Joten emme halua tehdä tätä.
>> Pikemminkin haluamme varmistaa että pidämme kiinni jokaiseen
yhden solmun ohjelmaamme.
Joten käynnissä new_node nuolta tasavertaisina pää ja sitten pää vastaa new_node
säilyttää kaikki linkkejä ja menetä mitään.
>> Mutta entä jos haluat luettelon olevan lajiteltu, koska ottaa lajiteltu linkitetty
lista saattaa olla helpompi etsimällä sen myöhemmin?
No, että sinun täytyy tietää miten kulkea linkitettyjä listoja.
>> Kulkemaan linkitetty lista, otetaanpa solmun osoitin, solmu *, toimimaan
kohdistin, mitkä solmuun olet alkaen
ensimmäisen elementin.
Silmukoiden kunnes kohdistin on null, voimme suorittaa tiettyjä prosesseja ja sitten
etukäteen kohdistin kun tarvitsemme käyttäen kursorin nuolen arvoa.
>> Muista, että tämä on sama asia kuin sanomalla tähden kursori, dereferencing
kohdistin, sitten käyttämällä dot operaattorin arvo.
Joten päivittäminen kursori on nimeämällä kohdistin kursorin nuolta.
>> Sano saat selville, että D tulee vuonna välillä C ja E. Jos haluat lisätä solmun,
on new_node D kohta solmu E, joka on kursorin vieressä.
Ja sitten C, kursori, voidaan osoittaa D. Näin voit ylläpitää luetteloa.
Varo menettää linkit siirtämällä kursorin nuolen vieressä D
heti.
>> Selvä.
Niin, että miten voit lisätä solmuja, lataa ne, kuorma sanat noihin
solmut, ja aseta ne omaan tiiviste.
Joten nyt katsokaamme yrittää.
>> Vuonna trie, jokainen solmu sisältää joukko solmun osoittimia, yksi jokaista
kirjain aakkosissa plus heittomerkki.
Ja jokainen alkio tulee kohta toiseen solmuun.
Jos tämä solmu on null, niin että kirje ei tule olemaan seuraava kirjeellä
tahansa sana järjestyksessä, koska jokainen sana osoittaa, mikäli kyseessä on viimeinen
luonnetta sanan tai ei.
>> Katsotaanpa kaavio.
Toivottavasti asiat olla hieman selkeämpi.
Tässä kaaviossa, näemme, että vain tiettyjen kirjainten ja tiettyjen osamerkkijonoihin
ollaan lueteltu ulos.
Joten voit seurata tiettyjä polkuja, ja kaikki nämä polut johtaa sinut
eri sanoja.
>> Miten siis edustamaan tätä C?
No, jokainen solmu nyt joutuu Boolean ilmaisee, onko
, että solmu on lopussa tiettyä sanaa vai ei.
Ja niin se tulee myös joukko solmu viitteitä lapsen nimen, ja
siellä tulevat olemaan 27 heistä.
Ja muista, sinun kannattaa myös seurata oman ensimmäisen solmun.
Aiomme soittaa että juuri.
>> Niin, että rakenne triellä.
Miten me edustamme tätä sanakirjana?
No, ladata sanoja, jokaiselle sanakirja sana, olet menossa haluavat
iteroitava triessä.
Ja jokaisen elementin lapsia vastaa eri kirjain.
>> Joten tarkistaa arvoa lapsille indeksin i, missä i edustaa
-indeksi kirjeestä, jonka yrität lisätä.
No, jos se on nolla, niin sinun kannattaa malloc uusi solmu ja saada lapsia
Osoitan, että solmu.
>> Jos se ei ole tyhjä, niin se tarkoittaa, että että koska sivuliikkeen, että annetaan
alimerkkijono, on jo olemassa.
Joten Tulet siirtymällä haluamaasi uusi solmu ja jatkaa.
Jos olet lopussa sana, joka yrität ladata vuonna
sanakirja, voit asettaa, että nykyisen solmun että olet tosi.
>> Joten katsokaamme esimerkki lisäämällä sana "kettu" meidän
sanakirja.
Teeskennellä aloitamme tyhjä sanakirja.
Ensimmäinen kirjain, F, tulee sijaitsemaan lapsilla indeksi viisi juuret
lasten array.
Niin lisäämme, että sisään
>> O-kirjain on sitten lapsilla indeksi 15, jonka jälkeen F. Ja sitten X
on jopa alle, että aluevaltaus pois O lapsia.
Ja sitten, koska X on viimeinen kirjain sanan "kettu", niin aion
väri, vihreänä, se on sanan lopussa.
C, että vaihtoehto olisi Is Sana Boolean arvoon totta.
>> Nyt mitä jos seuraava sana, että olet lastausta on sana "foo"?
No, sinun ei tarvitse malloc enää tilaa F tai O, koska
jo olemassa.
Mutta viimeinen O foo?
Että yksi, sinun täytyy malloc.
Tee uusi solmu, että asetus Onko Word Boolen totta.
>> Joten Nyt lisätä "koira." Koira aloittaa indeksi kolme juuret
lapsia, koska D ei ole vielä luotu.
Niin otamme samanlainen prosessi kuin ennen, luoda osamerkkijonon koira,
Missä G on väriltään vihreä, koska se on sanan lopussa.
>> Nyt, mitä jos haluamme lisätä "tehdä"?
No, tämä on alimerkkijono koira, joten meidän ei tarvitse malloc enää.
Mutta meidän on ilmoitettava, missä olemme lopussa tuo sana.
Joten O on väriltään vihreä.
Jatkuvat että prosessi joka ikinen sanan sanakirjaa, olet
ladattu ne osaksi joko hash table tai triellä.
>> speller.c välitän jousille dictionary.c tarkistaa ne.
Nyt Tarkista toiminto on toimittava alle tapauksessa välinpitämättömyys.
Tämä tarkoittaa, että isoja kirjaimia ja pieniä kirjaimia ja sekoitus molempia
kaikkien pitäisi rinnastaa arvoksi true, jos mitään yhdistelmä, joka on
sanakirja.
Voit myös olettaa, että kielet ovat vain menossa sisältää aakkosjärjestyksessä
merkkejä tai heittomerkit.
>> Joten katsotaanpa miten voisit tarkistaa kanssa hash taulukon rakenne.
No, jos sana on olemassa, niin se löytyvät tiiviste.
Niin sitten voit yrittää löytää, että sana asiaa ämpäri.
>> Joten mikä ämpäri olisi, että sana olla?
No, saat luultavasti numero, että indeksi kauhan, hajautusrakenteissa tämä sana
ja sitten hakuja että linkitetty lista, liikkumisesta läpi koko
linkitetty lista, käyttäen String Vertaa toiminto.
>> Jos pää linkitetty lista on saavutettu, mikä tarkoittaa, että kohdistin
saavuttaa null, niin sana ei ole joka löytyy sanakirjasta.
Se ei ole missään muussa ämpäri.
Joten tässä, saatat nähdä, miten siellä pitää olla kompromisseja, joilla on joko
lajiteltu linkitetyt tai lajittelemattoman niistä.
Joko vie enemmän aikaa aikana lastata tai enemmän aikana tarkistaa.
>> Miten voisit tarkistaa trie rakenne?
Aiomme matkustaa alaspäin triessä.
Jokaisen kirjeen syötetty sana että me tarkastamme, menemme että
vastaava osa lapsia.
>> Jos tämä elementti on tyhjä, niin se tarkoittaa, että ei ole olemassa merkkijonoa
sisältävät meidän tulosana, joten sana on kirjoitettu väärin.
Jos se ei ole nolla, voimme siirtyä seuraava kirjain sanan, että olemme
tarkkailun ja jatkaa tätä prosessia kunnes pääsemme loppuun
tulo-sana.
Ja sitten voimme tarkistaa If on Sana on totta.
Jos se on, niin hienoa.
Sana on oikein.
Mutta jos ei, vaikka tämä alimerkkijono olemassa triessä, sana on
kirjoitettu väärin.
>> Kun toiminto Koko kutsutaan, koko pitäisi palata sanojen määrästä
ovat teidän annetaan sanakirjassa tietorakenne.
Joten jos käytät hash-taulukon voi joko mennä läpi joka ikinen
linkitetty lista jokaisessa ämpäri laskemalla
sanoista on siellä.
Jos käytät triellä, voit käytävä läpi ei null
polku teidän triessä.
Tai kun lataat sanakirja vuonna, ehkä voit seurata, kuinka
monta sanaa lataat sisään
>> Kun speller.c lopettaa tarkkailun tekstitiedosto vastaan ​​sanakirja, sitten
se on tehty ja niin se vaatii Unload, jossa sinun tehtäväsi on vapauttaa mitään
että olet malloced.
Joten jos käytät hash table, sinun täytyy olla erityisen varovainen, jotta vältetään
muisti vuodot eivät vapauttamalla mitään ennenaikaisesti ja pitää kiinni joka
single link ennen teidät vapaiksi.
>> Joten jokaisen elementin tiiviste ja jokaisen solmun linkitetyn listan,
sinun kannattaa vapauttaa, että solmu.
Miten te sitten vapauttaa linkitetty lista?
Asettaminen solmu osoittimen kohdistin pää, alkuun
linkitetty lista, sitten kun kohdistin ei ole nolla, voit asettaa tilapäisen
solmu osoitin kohdistin.
Siirry sitten kursori.
Ja sitten voit vapauttaa että väliaikainen arvo samalla tilalla
kaiken jälkeenpäin.
>> Mitä jos käytät triellä?
Niin paras tapa tehdä tämä on purkaa aivan
alhaalta ylöspäin.
Matkustamalla mahdollisimman solmu, voit vapaasti kaikkia viitteitä
että lapset ja sitten perääntyä ylöspäin, vapauttaa kaikki elementit kaikissa
lasten ryhmät, kunnes osut alkuun juurisolmuun.
Tässä missä Rekursio tulee kätevä.
>> Varmista, että olet todennäköisesti vapautettu kaiken, olet malloced,
voit käyttää Valgrind.
Juoksu Valgrind ajaa oman ohjelman laskemalla, kuinka monta tavua muistia
käytät ja varmistaa, että olet vapautti heidät kaikki, kerron
jos saatat olla unohtanut ilmaiseksi.
Niin ajelu että ja kun Valgrind kertoo ja antaa sinulle mennä eteenpäin, niin
olet valmis purkaa.
>> Nyt, pari vinkkiä ennen lähtöä pois ja alkaa toteuttaa oman
sanakirja.
Suosittelen kulkea pienempi sanakirjassa kun yrität testata
asioita ja testaajat BKT.
Käyttö Speller. / Speller, valinnainen sanakirja, ja sitten teksti.
>> Oletuksena se lataa vuonna suuri sanakirja.
Joten kannattaa kulkea pieni sanakirja, tai ehkä jopa tehdä
oma, muokkaamalla sanakirja ja tekstitiedosto.
>> Ja lopulta, olisin myös suositella ottaa kynä ja paperia ja piirrä
asioita ennen, sen aikana ja sen jälkeen olet kirjoittanut kaikki koodi.
Vain varmista, että sinulla näitä viitteitä juuri oikea.
>> Toivotan teille onnea.
Ja kun olet valmis, jos haluat haastaa iso board ja
kuinka nopeasti ohjelman verrataan luokkatoverit ", niin kehotan
voit tarkistaa, että ulos.
>> Kanssa, että olet lopettanut speller PSET.
Nimeni on Zamyla, ja tämä on CS50.