[Powered by Google Translate] [Kiirtutvustus - Ülesanded 5]
[Zamyla Chan - Harvardi Ülikool]
[See on CS50. - CS50.TV]
>> Hea küll. Tere kõigile ja tere tulemast kiirtutvustus 5.
>> Pset5 on õigekirjavead, mida me teeme õigekirja kontrollija.
Õigekirja-kabe on väga oluline.
Kas see sinuga on juhtunud?
Te töötate väga aare edasi paber kokkupõrge
ja siis veel lõpuks saada väga kuma Rade nagu D või D =
ja kõik, sest oled liverwurst tagaspoiler vaal lai sõna.
Jah, korrektuur oma paprika on küsimus, äärmiselt impotentsus.
See on probleem, mis mõjutab mehine, mehine õpilased.
Kord öeldi mulle minu Sithi klassi piinaja, et ma ei oleks kunagi sattuda hea kolleeg.
Ja see on kõik, mida ma kunagi tahtnud, et kõik on iga laps tahab minu eas,
lihtsalt sattuda hea kolleeg.
Ja mitte iga suvaline kolleeg. No ma tahtsin minna Elevandiluu Õiguslik kolleeg.
Nii et kui ma ei parandada, läinud oleks minu unistused lähevad Harvardi,
Jale või vangla - sa tead, vanglas, New Jersey.
Nii sain endale õigekirja kontrollija.
See on natuke väljavõte üks mu lemmik lausutud sõna kunstnike, Taylor Mali.
Igatahes, kui ta ütleb, et oluline on õigekirja kontrollija on väga oluline.
>> Nii et tere tulemast kiirtutvustus 5, kus me räägime pset5: õigekirjavead,
kus teeme meie oma õigekirja kontrollija.
Tööriistakasti sel nädalal, jaotus-koodi, saab olema oluline vaadata
lihtsalt mõista erinevaid funktsioone, et teie sõnaraamat läheb on.
Me tegelikult saab olema mitmiktundlike. C failid, mis kokku moodustavad meie pset.
Ja nii vaadates läbi eri aspekte, kuigi me tegelikult ei toimetamine
üks failid, speller.c, teades, kuidas see toimib seoses dictionary.c,
mis me kirjalikult, saab olema päris oluline.
Pset spec sisaldab ka palju kasulikku teavet
seisukohalt asju, mida saate endale reeglid ja asjad niimoodi,
seda kindlasti lugeda pset spec hoolikalt näpunäiteid.
Ja kui kahtled normi või midagi sellist, siis alati viidata pset spec
või arutada.
See pset läheb sõltuvad suuresti suunanäitajaks,
nii et me tahame veenduda, et me mõista erinevust lisades tärni
ees kursor nime ja sümboliga, kuidas vaba neist jne
Nii on kapten viiteid saab olema väga kasulik seda probleemi komplekti.
Me läheme vaatama lingitud nimekirjad natuke rohkem,
kus meil on elemendid, mida me nimetame sõlmed, mis on nii raha kui ka osuti
Järgmise sõlme, ja nii sisuliselt ühendab eri elemente üksteise järel.
Siin on mõned erinevad võimalused rakendada oma tegelikku sõnaraamat.
Me läheme vaatama kahte peamist meetodit, mis on hash tabeleid ning proovib.
Mõlemal neist, nendega kaasneb mingi mõiste seotud nimekirja
kus te olete elemendid omavahel seotud.
Ja nii me lähme vaatame üle kuidas te võite olla võimeline töötama ümber seotud nimekirju,
luua neile, navigeerida osas, kuidas näiteks sisestada sõlme sinna
või tasuta kõik sõlmed samuti.
Seoses vabastades sõlmed, mis on tõesti oluline
et kui me malloc mälu, hiljem me vabastada ta.
Nii et me tahame veenduda, et ükski osuti läheb unfreed, et meil ei ole mingit mälu lekkeid.
Me läheme sisse tööriista nimega Valgrind, mis töötab oma programmi
ja kontrolli kas kõik mälu, et sa eraldatakse seejärel vabastada.
Sinu pset on ainult lõpule viidud, kui see toimib ja see on kõik funktsioonid,
vaid ka Valgrind ütleb, et teil ei ole leidnud ühtegi mälu lekkeid.
Lõpuks, see pset, ma tõesti tahan rõhutada -
Ma mõtlen, et nagu tavaliselt, olen kindlasti toetaja pliiatsi ja paberi jaoks su probleem komplekti,
kuid see üks, ma arvan, et pliiats ja paber saab olema eriti oluline
kui sa tahad olla joonistus nooli asju ja mõista, kuidas asjad töötavad.
Nii et kindlasti proovida kasutada paberit ja pliiatsit teha asju enne kui sa kodeerimine
sest see võib natuke segane.
>> Esiteks, ärgem minna lingitud nimekirjad natuke.
Seotud nimekirjad koosnevad sõlmed, kus iga tipu väärtuse sellega seotud,
samuti kursor järgmisele sõlme pärast seda.
Paar asja tähtis seotud nimekirjad on, et me peame meeles pidama,
kus meie esimene sõlm on, ja siis kui me teame, kus esimese sõlme on,
Nii saame juurde sõlme, et esimese sõlme võrra
ja siis üksteise järel, et ja üks pärast seda.
Ja siis viimase elemendi oma lingitud nimekiri on, et sõlm pointer
alati saab viidata NULL.
Kui sõlme võrra null, siis sa tead, et olete jõudnud nimekirja lõppu,
et sõlm on viimane, et seal on midagi pärast seda.
Siin skeem, näed, et nooled on suunanäitajaks,
ja sinine osa on, kui väärtus on salvestatud,
ja siis punase kasti kursor on sõlm pointer
osutades järgmise sõlme pärast seda.
Ja nii sa näed siin, D sõlme viitaks NULL, sest see on viimase elemendi nimekirja.
>> Vaatame, kuidas me võiksime määratleda struct jaoks sõlme.
Ja kuna me tahame olla mitu tippu,
see saab muutuda typedef struktuure
kus me lähed on mitmeid erinevaid juhtumeid sõlmed.
Ja nii me defineerime seda kui uue andmetüübi.
Siin on meil typedef struktuure sõlme.
Selles näites me tegeleme täisarv tippu,
nii et meil on täisarv nimega väärtus ja siis on meil veel üks pointer,
ja sel juhul on see kursor sõlme, seega on meil struct tipp * nimega kõrval.
Ja siis me nõuame kogu see asi sõlme.
Veenduge, et te järgite seda süntaksit.
Pange tähele, et sõlm on tegelikult viidatud ülevalt kui ka allpool looksulg.
Siis jälgida, kus mu esimene sõlm on selles seotud nimekirja,
siis on mul sõlme osuti nimetatakse pea, ja ma malloc piisavalt ruumi suurust sõlme.
Pane tähele, et pea on tegelikult sõlme osuti mitte tegelik sõlme ise.
Nii pea tegelikult ei sisalda mingit väärtust,
see ainult viitab kumb esimese sõlme minu lingitud nimekiri on.
>> Et saada paremat tunnet seotud nimekirjades, sest see on väga oluline
jälgida ja veenduge, et teil säilitada kett,
Mulle meeldib mõelda sellest kui inimesed liini hoides käed,
kus iga inimene, kellel käed kõrval üks.
Te ei näe selles joonistus, kuid põhimõtteliselt nad osutades järgmisele inimesele
mis on nende kett.
Ja nii et kui soovite läbida seotud nimekirja, kus need inimesed -
kujutan ette, kõik need inimesed on väärtused nendega
ja siinkohal ka järgmisele inimesele rida -
kui soovite läbida seotud nimekirja, näiteks kas muuta väärtused
või leidke väärtus või midagi sellist,
siis sa tahad olla kursor konkreetse isikuga.
Nii et me lähed on andmetüüp sõlme pointer.
Sel juhul olgem kutsuvad seda kursor.
Teine levinud viis nimetada see oleks iteraatori või midagi sellist
sest see on itereerimise üle ja tegelikult liigub, mis sõlme see osutab.
See siin on meie kursor.
Meie kursor Kõigepealt esimene osa meie nimekirjas.
Ja nii me tahame teha, on meil oleks põhimõtteliselt võimalik jätkata kursori
liigutamine küljelt küljele.
Sellisel juhul me tahame liikuda selle järgmisele element nimekirjas.
Massiivid, mida me teeks on me lihtsalt ütleme, et me suurendada indeks 1.
Sel juhul, mida me peame tegema, on tegelikult leida mis inimene see praegune inimene on suunaga,
ja mis saab olema järgmine väärtus.
Nii et kui kursor on lihtsalt sõlme pointer, siis mida me tahame teha
on me tahame saada raha, et kursor osutab.
Me tahame saada selle sõlme ja siis, kui me oleme selle sõlme leida, kui see osutab.
Et saada tegelik sõlme, et kursor on suunaga,
tavaliselt me ​​näitama seda (* kursor).
See annaks sulle tegeliku sõlme, et kursor osutab.
Ja siis pärast seda, mida me tahame teha, on me tahame pääseda
mida iganes see sõlm järgmisel väärtus on.
Selleks, et pääseda väärtused sees struct, meil dot operaator.
Nii et siis oleks (* kursor). Kõrval.
Aga see on natuke räpane mõttes võttes sulgudes ümber * kursori
ja nii me asendada kogu see avaldus koos kursori->.
See on kriips ja siis üle kirjutada, muutes nõnda nool.
kursori-> next.
See tegelikult sulle sõlme, et kursor osutab. See väärtus on järgmine.
Nii et selle asemel, täht-ja täpp, sa oled asendades selle noolega.
Ole väga ettevaatlik veenduda, et sa püüad seda süntaksit kasutada.
>> Nüüd, kui meil on kursor, kui me tahame pääseda väärtus,
enne oli meil kursori-> next,
kuid juurdepääsu väärtus sõlme, et kursor on suunaga, me lihtsalt lihtsalt öelda
sõlm-> väärtus.
Sealt see andmete tüüp iganes oleme määratletud väärtused ja sõlmede olla.
Kui see on int sõlme, siis kursori-> väärtus on lihtsalt saab olema täisarv.
Nii et me saame teha operatsioone, et kontrollida võrdused, määrata selle erinevaid väärtusi jne
Nii siis mida sa teha tahad, kui soovite kursori järgmisele inimesele,
sa tegelikult väärtuse muutmiseks kursor.
Kuna kursor on sõlm pointer, muudad tegelikult osuti aadress
aadressile, järgmise sõlme oma nimekirja.
See on lihtsalt mingi kood, kuhu võiks itereerima.
Kui mul on Kommentaari midagi teha,
see on kui sa oled ilmselt läheb pääseda väärtus
või tegema midagi pistmist selle konkreetse sõlme.
Et alustada selle ära, ma ütlen, et minu kursor esialgu
läheb punkti esimese osa seotud nimekirja.
Ja nii kuni edasi, ma määratletud see juhina sõlme.
>> Nagu ütlesin, vabastades on tõepoolest oluline.
Sa tahad teha kindel, et te vabastama iga element nimekirjas, kui olete sellega lõpetanud.
Kui te ei vaja viidata ühelegi neist osuti enam
sa tahad teha kindel, et sa vabastama kõik need viiteid.
Aga sa tahad olla väga ettevaatlik siin, et sa tahad, et vältida mälu lekkeid.
Kui teil vaba üks inimene enneaegselt, siis on kõik suunanäitajaks, et sõlme võrra
hakkavad kaduma.
Tulles tagasi inimene näiteks selleks, et see natuke rohkem kõrgete panustega,
Olgu meil need inimesed, välja arvatud sel juhul nad varjutavad järve koletis.
Me tahame veenduda, et kui me vabad, me ei kaota
ja lase mõni sõlmede enne oleme tegelikult vabastas neile.
Näiteks, kui sa olid lihtsalt helistada tasuta see kutt siin,
siis ta vabastatakse, kuid siis kõik need kutid oleks siis kadunud
ja nad triiv maha ja kukuks.
Nii et me tahame veenduda, et selle asemel, me tahame säilitada link ülejäänud.
Meie pea osuti, mis näitab, et esimene element nimekirjas.
See on nagu köie siduda esimene inimene.
Mida sa tahad teha, kui sa vabaks nimekiri on -
Kui soovite vabastada esimese osa esimene, siis võib olla ajutine pointer
, mis osutab mis tahes Esimene element on.
Nii et teil on oma ajutise osuti osutab siin.
Nii, meil on kätte esimese sõlme.
Ja siis, kuna me teame, et esimese sõlme läheb vabastatakse,
siis saame edasi liikuda see köis, see ankur, meie pea,
tegelikult osutada ükskõik esimene osutab.
Nii et see pea tegelikult osutab teise elemendi nüüd.
Nüüd on lubatud vabastada iganes on salvestatud temp,
ja nii saame kustutada, et ilma selleta ohtu kõik teised sõlmed meie nimekirjas.
Teine võimalus, et sa võiksid seda teha võiks
iga kord, kui lihtsalt vaba viimane element nimekirja
sest nad ei tohi kindlasti märkida midagi.
Nii et võid lihtsalt vabastada see üks, siis tasuta see üks, siis tasuta seda.
See kindlasti töötab kuid on natuke aeglasem, sest iseloom seotud nimekirju,
me ei saa lihtsalt hüpata kohe viimane.
Meil on läbida iga element seotud nimekirja
ja kas, et üks on suunaga null, kontrollida iga kord,
ja siis kui jõuame lõpuks, siis vaba sellest.
Kui sa olid seda protsessi, siis oleks tegelikult kontrollida siin,
kontroll siin, siis kontrollides siin, vabastades ta,
siis lähen tagasi, kontroll siin, kontroll siin, vabastades ta,
kontroll siin, ja siis vabastades ta.
See võtab natuke rohkem aega. Jah.
>> [Üliõpilane] Kas oleks võimalik siduda nimekiri, mis salvestab väljumise kursor lõpus?
See oleks kindlasti võimalik.
Kordan küsimust, kas on võimalik olla seotud nimekirja struktuur
nii, et teil on osuti osutab lõppu seotud nimekirja?
Ma ütleks, et see on võimalik, ja iga kord, kui sisestad midagi oma seotud nimekirja
siis oleks uuendada, et osuti ja asjad niimoodi.
Sa oleks sõlme * saba, näiteks.
Aga kui sa rakendatakse seda funktsiooni, peate mõtlema kompromisse,
meeldib, kui mitu korda ma seda tuleb itereerimise üle selle,
kui raske see saab olema jälgida saba samuti pea
samuti minu iteraatori ja asjad niimoodi.
Kas see -? >> [Üliõpilane] Jah.
On võimalik, kuid nii disaini otsuseid, sa pead kaaluma võimalusi.
>> Siin on skelett kood, mis võimaldab teil vabastada iga element seotud nimekirja.
Jällegi, kuna ma olen itereerimise üle seotud nimekirja, ma lähen taha olla mingi kursor
või iteraatori.
Meil on itereerimise kuni kursor on NULL.
Sa ei taha kinnitada, kui kursor on NULL
sest see tähendab, et ei ole midagi nimekirjas.
Nii siis siin teen ajutine sõlme *
osutades mida ma arvestades on esimene minu nimekirjas
ja siis ma liikuda mu kursori ees 1 ja seejärel vaba iganes mul oli ajutine ladustamine.
>> Nüüd aga aku asetamist lingitud nimekirjad.
Mul on kolm tippe minu lingitud loendi ja lähme koos lihtsa puhul
kuhu me tahame lisada teise sõlme lõpus meie seotud nimekirja.
Selleks, et kõik me teeks on me läbida
leida, kui praegune lõppu lingitud nimekiri on, nii et kumb sõlme osutades null -
see on see üks -
ja siis öelda, tegelikult ei ole see saab olema viimane sõlm;
me tegelikult läheb on teine.
Nii oleks meil see praegune ühest punktist iganes me sisestamist.
Nii et nüüd see punane inimene siin saab viimase sõlme seotud nimekirja.
Ja nii iseloomulik viimase sõlme seotud nimekirja, et see viitab NULL.
Nii siis mida me peaks tegema, on määrata see punane mees on pointer on NULL. Seal.
>> Aga kui me tahame lisada sõlme vahel teine ​​ja kolmas?
See üks ei ole päris nii lihtne, sest me tahame veenduda
et me ei lase ühtegi sõlme meie seotud nimekirja.
Mida me peame tegema, on veenduge, et me kinnistada end igaüks.
Näiteks olgem nimetame seda teist.
Kui sa ütlesid teine ​​nüüd juhib seda uuega
ja just tehtud pointer seal, siis oleks tulemuseks see kutt on kadunud
sest seal ei ole mingit seost temaga.
Selle asemel - ma joonistan selle uuesti. Vabandage mu kunstiliste võimete.
Me teame, et me ei saa lihtsalt otse ühendada 2 uuega.
Me peame tagama, et me kinni hoida viimane.
Mida me võiksime teha tahad on olla ajutine pointer
element, mis saab olema maatriksi.
Siis on meil ajutine pointer seal.
Kuna me teame, et see kolmas on hoitakse silma peal,
2 saab nüüd link meie uus.
Ja kui see uus punane poiss saab olema vahemikus 2 ja 3,
siis mis on selle kuti osuti läheb osutada? >> [Üliõpilane] Temp.
Temp. Jah.
Nii et siis see punane kuti kõrval väärtus saab olema temp.
Kui olete aku asetamist lingitud nimekirjad nägime, et me võiksime
lihtsalt lisada midagi lõpuni, luues ajutine massiiv,
või kui me tahame midagi lisada keskele meie massiiv,
siis see võtaks natuke rohkem nohinat.
Kui soovite näiteks on järjestatud seotud nimekirja,
siis sa pead mingi kaaluma kulude ja tulude kohta, mis
sest kui sa tahad olla järjestatud hulga, mis tähendab, et iga kord, kui lisada see,
see aega võtab natuke rohkem aega.
Siiski, kui soovite hiljem, kui me leiame me tahame,
otsingu kaudu seotud nimekirja, siis oleks lihtsam, kui tead, et kõik on korras.
Nii et te võiksite kaaluda kulusid ja tulusid nii.
>> Teine võimalus lisada lingitud nimekiri on lisada algusest nimekirja.
Kui me võtame oma ankur siin - see on meie peas -
ja siis on need inimesed sellega seotud,
ja siis on meil uus sõlm, et lisada alguses,
siis milline võiks me tahame teha?
Mis oleks viga lihtsalt ütlen ma tahan siduda punane sinine,
sest see on esimene?
Mis juhtuks siin?
Kõik need kolm oleks eksida.
Nii et me ei taha seda teha.
Jällegi, me oleme õppinud, et me peame olema mingi ajutine kursor.
Valime on ajutine käsk see kutt.
Siis saame sinine ühest punktist ajutine
ja siis punane käsk sinine.
Põhjus, miks ma kasutan inimesed siin on, sest me tõesti tahame visualiseerida
ettevõttest inimesi ning tagada, et meil on link neile
enne kui me lasta minna teise käega või midagi sellist.
>> Nüüd, kui meil on mõttes seotud nimekirjad - kuidas me võiksime luua seotud nimekirja
ning luua struktuurid, mis koosnevad tüüp määratlus sõlme
ja siis veendudes, et meil on viit pea selle lingitud nimekiri -
kui meil on see ja me teame, kuidas läbida kaudu array,
juurdepääs erinevaid elemente, me teame, kuidas sisestada ja me teame, kuidas vaba neist,
siis saame võtta õigekirjavead.
Nagu tavaliselt, on meil osa küsimusi, mis sulle harjunud tegutsema koos lingitud nimekirjad
ja erinevate struktuuride nagu järjekorrad ja korstnad.
Siis saame liikuda õigekirjavead.
>> Õigekirjavead on jaotuse kood paar faili tähtsust.
Esiteks näeme, et meil on see Makefile siin,
mida me ei ole tegelikult varem kohanud.
Kui sa vaatasid sees pset5 kausta soovid teate, et teil on. H faili
siis on sul kaks. c faile.
Mis see Makefile ei ole enne, oleksime lihtsalt kirjuta teha ja siis programmi nimi
ja siis näeme kõik need argumendid ja lipud möödunud aastal, et kompilaator.
Mis Makefile ei ole võimaldab meil koostada mitu faili korraga
ja läbima lipud, et me tahame.
Siin me lihtsalt vaata seal päisefail siin.
Siis tegelikult on kaks allikas faile.
Meil on speller.c ja dictionary.c.
Olete oodatud redigeerida Makefile, kui soovite.
Pange tähele, et siin kui tipite puhas, siis mida ta teeb on tegelikult eemaldab midagi
mis on tuum.
Kui sul killustatust süü, põhimõtteliselt sa saad core dump.
Nii et see kole vähe faili ilmuvad kataloog nimega tuum.
Sa tahad eemaldama, et teha puhtaks.
See eemaldab kõik exe failid ja. O faile.
>> Võtame uurima dictionary.h.
See ütleb, et ta deklareerib sõnaraamat funktsionaalsust.
Meil on maksimaalne pikkus iga sõna sõnastikus.
Me ütleme, et see saab olema pikim võimalik sõna. See on pikkusega 45.
Nii et me ei kavatse olla mis tahes sõna, et ületa pikkus.
Siin me lihtsalt funktsiooni prototüüpe.
Meil ei ole tegelikku rakendamist, sest see on, mida me tegema selle pset.
Aga mida see teeb, on alates me tegeleme suuremate failide siin
ja funktsionaalsus suuremas mastaabis, on kasulik omada. h fail
nii et keegi teine ​​lugemine või kasutades oma koodi saab aru, mis toimub.
Ja võibolla nad soovivad rakendada üritab, kui sa tegid hash tabeleid või vastupidi.
Siis nad ütlevad minu koormus funktsioon,
tegeliku rakendamise läheb erinevad, kuid see prototüüp ei muutu.
Siin me oleme vaadata, mis tagastab true, kui antud sõna on sõnastikus.
Siis oleme koormus, mis põhimõtteliselt võtab sisse sõnastiku faili
ja seejärel laadib see mingi andmestruktuur.
Meil on suurus, mis, kui kutsutakse, tagastab suurust oma sõnaraamat,
kui palju sõnu on salvestatud see,
ja siis maha laadida, mis vabastab kõik mälu, et olete asunud
tehes oma sõnastikku.
>> Võtame pilk dictionary.c.
Me näeme, et see näeb välja väga sarnane dictionary.h, välja arvatud nüüd see lihtsalt on kõik need Todos ta.
Ja nii see on teie töö. Lõpuks saate täites speller.c kogu seda koodi.
Dictionary.c, kui joosta, ei ole tõesti midagi teha,
nii et me vaatame suunas speller.c näha tegelikku rakendamist õigekirja kontrollija.
Kuigi te ei kavatse olla redigeerimise tahes käesoleva seadustiku
see on oluline lugeda, mõista kui on koormus nimetatakse, kui ma helistades kontroll,
lihtsalt mõistetav map välja, kuidas toimib.
Me näeme, et see kontrollimine õige kasutamine.
Sisuliselt, kui keegi jookseb speller, näitab see, et see on vabatahtlik
neil läbida sõnastik faili, sest seal saab olla vaikimisi sõnastik faili.
Ja siis nad peavad sooritama tekstis olla õigekirja kontrollida.
rusage tegeleb aega, sest osa sellest pset mis me tegelema hiljem
ei ole ainult saada toimiv õigekirja kontrollija töö
kuid tegelikult saada see olema kiire.
Ja nii siis see on kui rusage on tulemas sisse
Siin näeme esimene kõne ühele meie dictionary.c failid, mis on koormust.
Laadi tagastab true või false - tõsi peale edu, vale jätmise korral.
Nii et kui sõnastik ei laadita korralikult, siis speller.c naaseb 1 ja lõpetan.
Aga kui see ei koorma korralikult, siis see saab jätkuda.
Jätkame, ja me näeme mõnda faili I / O siin,
kus see saab olema tegemist avamist tekstifaili.
Siin Mis see on õigekirja kontrolli iga sõna tekstis.
Mida speller.c teeb siin on itereerimise üle iga sõna tekstifaili
ja siis kontrollida neid sõnaraamat.
Siin on meil Boole'i ​​valesti, et näed, kui kontroll tagastab tõsi või mitte.
Kui sõna on tegelikult sõnastikus, siis kontrolli naaseb tõsi.
See tähendab, et sõna pole valesti kirjutatud.
Nii et valesti oleks vale, ja sellepärast on meil paugu seal märge.
Hoiame läheb, ja siis ta hoiab silma peal, kui palju valesti kirjutatud sõnad
seal on fail.
See jätkub ja sulgeb faili.
Siis siin, esitab ta mitu valesti kirjutatud sõnad, mida oli.
Ta arvutab, kui palju aega kulus laadida sõnastikku
kui palju aega kulus, et seda kontrollida,
kui palju aega kulus, et arvutada suurus,
mis, nagu me lähme, peaks olema väga väike,
ja siis kui palju aega kulus maha laadida sõnaraamat.
Siin kõrgemale näeme kõne maha laadida siit.
Kui me kontrollida suurus siin,
siis näeme, et siin on üleskutse suurus, kus see määrab suuruse sõnaraamat.
Awesome.
>> Meie ülesanne selles pset on rakendada koormust, mis laeb sõnaraamat
andmestruktuur - kumb valida, olgu see hash tabelit või proovida -
sõnade sõnaraamatust faili.
Siis on suurus, mis tagastab arvu sõnu sõnastikku.
Ja kui sa rakendada koormust nutikas viis, siis suurus peaks olema üsna lihtne.
Siis on näha, mis kontrollib, kas antud sõna on sõnastikus.
Nii speller.c möödub string, ja siis sa pead kontrollima, kas see string
sisalduvad oma sõnastikku.
Pange tähele, et me üldiselt standard sõnastikud,
kuid selles pset, põhimõtteliselt mis tahes sõnastik möödus mis tahes keeles.
Nii et me ei saa lihtsalt eeldada, et sõna on sees.
Sõna jura võiks määratleda teatud sõnaraamat et võtame sisse
Ja siis on meil maha laadida, mis vabastab sõnaraamat mälust.
>> Esiteks, ma tahaksin minna üle hash tabelit meetod
kuidas me võiksime rakendada kõik need neli funktsiooni,
ja siis ma lähen üle proovib meetod, kuidas me ellu need neli funktsiooni,
ja lõpus rääkida mõned üldised nõuanded, kui sa üritad pset
ja ka seda, kuidas sa võiksid kasutada Valgrind kontrollida mälu lekkeid.
>> Vali nüüd hash tabelit meetod.
Hash tabel koosneb nimekirja ämbrid.
Iga väärtus, iga sõna, läheb minema ühte nendest ämbrid.
Hash tabelit ideaalselt ühtlaselt jaotab kõik need väärtused, mida sa läbides
ja siis asustatakse neid ämber selline, et iga ämber
on umbes sama palju väärtusi ta.
Struktuuri hash tabelit, meil on massiiv seotud nimekirju.
Mida me teeme kui me läbima väärtus, me kontrollime, kui see väärtus peaks kuuluma,
mis ämber see kuulub, ja siis pannakse see seotud nimekirja seostab ämber.
Siin mis mul on räsifunktsiooniga.
See on int hash tabelit.
Nii esimene ämber kõik täisarvud alla 10 läheb esimene ämber.
Iga täisarvu üle 10, kuid alla 20 minna teise,
ja siis nii edasi ja nii edasi.
Minu jaoks on iga ämber esindab neid numbreid.
Kuid öelda, et ma ei liigu 50, näiteks.
Tundub, nagu oleks kolm esimest sisaldama erinevaid kümne numbrid.
Aga ma tahan, et lasta oma hash tabelit võtma mingit täisarvud,
et siis ma oleks välja filtreerida kõik numbrid üle 30 aasta viimases ämber.
Ja nii siis, et tulemuseks oleks selline tasakaalustamata hash tabelit.
Korrata, hash tabel on lihtsalt massiivi ämbrid
kus iga ämber on seotud nimekirja.
Ja nii kindlaks teha, kus iga väärtus läheb, mis ämber see läheb,
sa lähed tahan, mida nimetatakse räsifunktsiooniga
mis võtab väärtuse ja siis ütleb, et see väärtus vastab teatud ämber.
Nii et kuni eespool käesolevas Näiteks minu räsifunktsiooniga võttis iga väärtuse.
See kontrollida, kas see oli vähem kui 10.
Kui ta oli, see paneks see esimene ämber.
Ta kontrollib, kas see on vähem kui 20, paneb see teise, kui tõsi,
kontrolli, kui see on alla 30, siis paneb see kolmas kopp,
ja siis kõik muu lihtsalt langeb neljandas ämber.
Nii et kui teil on raha, oma räsifunktsiooniga
asetab selle väärtuse sobivasse ämbrisse.
Räsifunktsiooniga põhimõtteliselt peab teadma, kui palju kopad olete.
Sinu hash tabelit suurus, arv kopad teil on,
et see saab olema kindel arv, mis on sinust, teie otsustada,
kuid see saab olema kindel arv.
Nii et teie räsifunktsiooniga siis tuginedes, et teha kindlaks, millised ämber iga võti läheb
nii, et see ühtlaselt laiali.
Sarnaselt meie rakendamine seotud nimekirjades, nüüd iga sõlme hash tabelit
tegelikult läheb on tüüpi char.
Nii et meil on char massiiv nimega sõna ja siis teine ​​kursor järgmisele sõlme,
mis mõtet, sest see saab olema seotud nimekirja.
Mäletad, kui me olime seotud nimekirjades, tegin sõlme * nn peaga
mis oli suunatud esimese sõlme seotud nimekirja.
Aga meie hash tabelit, sest meil on mitu seotud nimekirju,
me tahame me tahame, et meie hash tabelis olla nagu, "Mis on ämber?"
Kopp on lihtsalt nimekiri sõlme suunanäitajaks,
ja nii iga element ämber on tegelikult osutab sellele vastava seotud nimekirja.
Tulles tagasi selle skemaatiline, näed, et ämbrid ise on nooled,
mitte päris tippu.
Üks oluline omadus hash funktsioonid on see, et nad on determineeritud.
See tähendab, et kui sa räsi number 2,
see peaks alati tagasi samasse ämbrisse.
Iga üksik väärtus, mis läheb räsifunktsiooniga, kui korrata,
on saada sama indeksit.
Nii et teie räsifunktsiooniga tagastab indeks array
kui see väärtus kuulub.
Nagu ütlesin, mitmed ämbrid on fikseeritud,
ja nii oma pealeht et naasete peab olema väiksem kui arv ämbrid
kuid suurem kui 0.
Põhjus, miks meil on hash funktsioonid, mitte ainult ühe seotud nimekirja
või ühe massiivi on see, et me tahame, et oleks võimalik hüpata teatud osa kõige lihtsam
kui me teame iseloomulik väärtus -
selle asemel et otsida vajalikud kogu sõnaraamat,
on võimalik hüpata teatud osa sellest.
Sinu räsifunktsiooniga tuleks arvesse võtta, et ideaalis
iga ämber on umbes sama palju võtmeid.
Kuna hash tabelis on rida seotud nimekirju,
siis seotud nimekirju ise ei kavatse olla rohkem kui üks sõlm.
Eelmise näiteks kaks erinevat arvu, kuigi nad ei olnud võrdsed,
kui räsitud, tagastab sama indeksit.
Nii et kui teil on tegemist sõnadega, üks sõna, kui räsitud
oleks sama räsi väärtus nagu teine ​​sõna.
See, mida me kutsume kokkupõrge, kui meil on sõlm, et kui räsitud,
seotud nimekirja sel kopp ei ole tühi.
Tehnikat, mida me nimetame on lineaarne katsetamine,
kus te lähete seotud nimekirja ja siis leida, kui soovite lisada, et sõlm
sest sa oled kokkupõrget.
Te näete, et seal võiks olla kompromiss siin, eks?
Kui teil on väga väike hash tabelit, väga väike arv kopad,
siis sa lähed on palju kokkupõrkeid.
Aga siis, kui sa teed väga suur hash tabelit,
sa oled ilmselt läheb vähendada kokkupõrkeid,
kuid see saab olema väga suur andmestruktuur.
Seal saab olema kompromisse sellega.
Nii et kui sa üritad oma pset, proovige mängida
vahel võibolla teha väiksemaid hash tabelit
aga siis teades, et see vőtab natuke kauem läbida erinevad elemendid
Nende lingitud nimekirjad.
>> Mis koormus läheb selleks vaja on itereerima üle iga sõna sõnastikus.
See möödub osuti sõnastikku fail.
Nii et sa lähed ära Faili I / O funktsioone, mida õppinud pset4
ja itereerima üle iga sõna sõnastikus.
Tahad iga sõna sõnastikku saada uus sõlm,
ja sa lähed panna iga üks neist sõlmed oma sõnaraamat andmestruktuur.
Kui sa saad uue sõna, sa tead, et see saab muutuda sõlme.
Nii et võite minna kohe ja malloc sõlme kursor iga uue sõna, mis teil on.
Siin ma helistan minu sõlme osuti new_node ja ma mallocing mida? Suurust sõlme.
Siis lugeda tegeliku stringi faili, sest sõnastik on tegelikult salvestatud
poolt sõna ja siis uus rida, mida me saame ära
on funktsioon fscanf,
mille fail on sõnastiku faili, mida me möödunud aastal,
nii see skaneerib faili stringi ja kohad, mis stringi viimane argument.
Kui te mäletate tagasi üks loenguid, kui me läksime üle
ja selline kooritud kihid tagasi CS50 raamatukogu,
nägime rakendamise fscanf seal.
Et minna tagasi fscanf, meil on fail, mida me lugemine,
me otsime stringi et faili, ja siis me pannes see
siin on mul new_node-> sõna, sest new_node on sõlm pointer,
ei tegelikult sõlme.
Nii siis ma räägin new_node, ma tahan minna sõlme, et see osutab
ja siis määrata, et väärtust sõna.
Soovime siis võta see sõna ja pistke see hash tabelit.
Aru, et tegime new_node sõlme pointer
sest me ei kavatse tahavad teada, mida aadressi, et sõlm on
kui me aseta sest struktuuri sõlmede iseennast, struct,
on see, et neil on kursor uus sõlm.
Nii siis mida on aadress, et sõlme läheb osutada?
See aadress saab olema new_node.
Kas on mõtet, miks me teeme new_node sõlme * mitte sõlme?
Okei.
Meil on sõna. See väärtus on new_node-> sõna.
See sisaldab sõna sõnaraamatust, et me tahame sisend.
Nii et see, mida me tahame teha, on me tahame helistada meie hash funktsiooni, et string
sest meie räsifunktsiooniga võtab on string ja tagastab meile täisarv,
kui see täisarv on indeks, kus Hashtable sel indeks kajastab, et kopp.
Me tahame võtta, et indeks ja seejärel minna, et indeks hash tabelit
ja siis kasutada, et siduda nimekirja lisada sõlme new_node.
Pea meeles, et aga te otsustate sisestada oma sõlme,
kas see on keskel, kui soovite sortida
või alguses või lõpus, veenduge, et teie viimane sõlm osutab alati on NULL
sest see on ainus viis, et me teame, kus viimane element meie lingitud nimekiri on.
>> Kui suurus on täisarv, mis tähistab arvu sõnu sõnastikku,
siis üks viis seda teha on, et kui suurus nimetatakse
me minna läbi iga element meie hash tabelit
ja siis itereerima läbi iga seotud nimekirja jooksul hash tabelit
ja siis arvutada pikkuse, et suurendada meie counter 1 1.
Aga iga kord, suurus nimetatakse, et läheb võtab kaua aega
sest me ei kavatse olla lineaarselt katsetamine iga seotud nimekirja.
Selle asemel, et see saab olema palju lihtsam, kui sa jälgida, kui palju sõnu on möödas sisse
Nii et siis, kui Te counter jooksul oma koormust funktsioon
et uuendused nagu vaja, siis loendur, kui sa määrad selle globaalse muutuja,
saab avada, kui suurus.
Mida suurus võiks lihtsalt teha, on ühes reas, lihtsalt tagasi leti väärtus,
suurust sõnastik, mis sa juba käsitletud koormus.
Seda ma mõtlesin, kui ütlesin, kui sa ellu lasti kasulik viis,
siis suurus saab olema üsna lihtne.
>> Nii et nüüd saame kontrollida.
Nüüd me tegeleme sõnu sisend tekstifail,
ja nii me lähme kontrollima, kas kõik need sisend sõnad
on tegelikult sõnastikus või mitte.
Sarnaselt rüselus, me tahame võimaldada juhul tundetus.
Sa tahad teha kindel, et kõik sõnad vastu võetud, kuigi nad on segatud juhul
kui kutsutakse nööriga Võrdle, on samaväärsed.
Sõnade sõnastik Tekstifailid on tegelikult kõik väiketähed.
Teine asi on see, et võite eeldada, et iga sõna vastu võetud, iga stringi,
saab olema kas tähestikulises järjekorras või sisaldada ülakomad.
Ülakomasid hakkavad kehtima sõnad meie sõnaraamatus.
Nii et kui teil on sõna ülakoma S, see on tegelik õigustatud sõna oma sõnaraamat
et see saab olema üks tippe oma hash tabelit.
Kontrollige töötab, kui sõna on olemas, siis see ju olema meie hash tabelit.
Kui sõna on sõnastikus olemas, siis on kõik sõnad sõnastikus on hash tabelit,
seega vaatame seda sõna hash tabelit.
Me teame, et kuna me ellu meie räsifunktsiooniga
nii et iga unikaalne sõna on alati räsitud sama väärtus,
siis me teame, et selle asemel, et otsida läbi kogu meie kogu hash tabelit,
saame tegelikult leida seotud nimekirja, et see sõna peaks kuuluma.
Kui see oleks sõnastikus, siis oleks selles ämber.
Mida me saame teha, kui sõna on nimi meie string möödunud aastal,
me võime lihtsalt räsi seda sõna ja pilk seotud nimekirja
väärtuse juures Hashtable [räsi (sõna)].
Sealt me ​​teha saame, on meil väiksem alagrupis sõlmede otsida sõna,
ja nii saame läbida seotud nimekirja, kasutades näiteks varem ülevaadet,
ja siis nimetame jada võrrelda peale sõna kus kursor on suunaga,
et sõna ja vaata, kas need võrrelda.
Sõltuvalt nii, et teil korraldada oma räsifunktsiooniga,
kui see on järjestatud, siis võite olla võimeline tagasi false veidi varem,
aga kui see on sorteerimata, siis soovite jätkata liiklevad läbi oma seotud nimekirja
kuni leiad viimane element nimekirja.
Ja kui sa ei ole veel leidnud sõna selleks ajaks olete jõudnud seotud nimekirja,
see tähendab, et teie sõna ei leidu,
ja nii, et sõna on vale,
ja kontroll peaks tagasi false.
>> Nüüd aga maha laadida, kuhu me tahame vabastada kõik sõlmed, et oleme malloc'd,
nii tasuta kõik sõlmed meie hash tabelit.
Me läheme taha itereerime kõik seotud nimekirju ja vaba kõik sõlmed, et.
Kui vaadata eespool liikudes, et näiteks kui me vabastama seotud nimekirja,
siis tahad korrata seda protsessi iga element hash tabelit.
Ja ma lähen üle käesoleva aasta lõpus ülevaadet,
kuid Valgrind on vahend, kus saab näha, kui olete korralikult vabanenud
iga sõlme, et olete malloc'd või midagi muud, et olete malloc'd, muu pointer.
Nii et hash tabeleid, kus meil on hulga kopad
ja räsifunktsiooniga mis võtab väärtuse ja seejärel määrata, et raha teatud ämber.
>> Nüüd aga üritab.
Proovib selline välimus meeldib see, ja ma ka venitama näiteks.
Põhimõtteliselt sul on terve rida võimalikke tähti,
ja siis kui sa ehitamisel sõna,
et kirja võib olla seotud jaoks sõnastiku mitmeid võimalusi.
Mõned sõnad algavad C, kuid seejärel jätkata,
aga teised jätkata O, näiteks.
Trie on viis visualiseerimise kõik võimalikud kombinatsioonid need sõnad.
Trie läheb jälgida rea ​​tähti, mis moodustavad sõna,
hargnevat kui vaja, kui üks täht võib järgneda mitu kirja,
ja lõpus tähistavad igas punktis kas see sõna on kehtiv või mitte
sest kui sa õigekirja sõna MAT, MA Ma ei usu, on kehtiv sõna, kuid MAT on.
Ja nii oma trie, see näitab, et pärast MAT, mis on tegelikult kehtiv sõna.
Iga sõlme meie trie tegelikult toimub sisaldavad hulgaliselt sõlme suunanäitajaks,
ja me lähed on konkreetselt 27 neist sõlme suunanäitajaks,
üks iga tähestiku tähe samuti ülakoma iseloomu.
Iga element selles massiivis on ise saab juhtida teise sõlme.
Nii et kui see sõlm on NULL, kui seal on midagi pärast seda,
siis me teame, et seal ei ole veel tähti selles fraasi.
Aga kui see sõlm ei ole null, mis tähendab, et seal on rohkem tähti, et tähekombinatsiooni.
Ja siis lisaks iga sõlm näitab, kas see on viimane märk, sõna või mitte.
>> Läheme näide trie.
Esiteks on mul toas 27 tippe selle massiivi.
Kui mul on sõna BAR -
Kui mul on sõna baari ja ma tahan lisada, et,
esimene täht on B, nii et kui minu trie on tühi,
B on teine ​​täht, nii et ma lähen valima panna see siin selles indeksis.
Ma lähen on B siin.
B saab olema sõlm, mis viitab teise massiivi kõik võimalikud märgid
et saab jälgida pärast kirja B.
Sel juhul ma tegelen sõna BAR, nii läheb siin.
Pärast Mul on R-täht, nii siis nüüd juhib oma kombinatsioon,
ja siis R on siin.
BAR on täielik sõna, et siis ma lähen on R punktist teise sõlme
mis ütleb, et see sõna on kehtiv.
See sõlm on ka plaanis teha mitmeid erinevaid sõlmi,
kuid need võivad olla NULL.
Aga põhimõtteliselt saab jätkata niimoodi.
See muutub natuke selgem, kui me läheme eri Näiteks
nii lihtsalt karu mind sinna.
Nüüd on meil baari sees meie sõnastikku.
Nüüd ütleme, et meil sõna BAZ.
Alustame B, ja meil on juba B üheks tähed, mis on meie sõnastikku.
See on jälginud A. Meil ​​on juba.
Aga siis selle asemel on meil Z järgmised.
Nii siis osa meie massiivi saab olema Z
ja nii siis, et keegi ei kavatse juhtida teise kehtiva sõna lõppu.
Nii näeme, et kui me jätkame läbi B ja siis,
seal on kaks erinevat võimalust praegu meie sõnastikust sõnu, mis algavad B ja A.
Ütle tahtsime lisada sõna jura.
Siis me oleks sisenemise F.
F on sõlm, mis osutab terve rida.
Soovime leida O, minge O, O siis lingid kogu nimekiri.
Oleksime B ja seejärel jätkake, me tahaks olla ja siis R.
Nii siis foobar läbib kogu tee alla kuni jura on õige sõna.
Ja nii siis see oleks kehtiv sõna.
Nüüd ütlevad meie järgmise sõna sõnastikus on tegelikult sõna foo.
Meil oleks öelda F. Mis järeldub F?
Ma tegelikult juba ruumi O, nii et ma lähen jätkata.
Ma ei pea tegema uue. Jätka.
SUVA on kehtiv sõna selles sõnastik, et siis ma lähen näitama
et see on kehtiv.
Kui ma saan oma järjestuse seal, et oleks õige.
Aga kui me jätkame meie järjestus SUVA alla B
ja lihtsalt pidin FOOB, FOOB ei ole sõna, ja see pole märgitud selle kehtivuse.
Aastal trie, olete iga sõlm näitab, kas tegemist on kehtiv sõna või mitte,
ja siis iga sõlm on ka massiivi 27. sõlme viiteid
et siis käsk sõlmed ise.
>> Siin on viis, kuidas te võiksite määrata see.
Kuid just nagu hash tabelit Näiteks kui meil oli sõlme * pea
näidata algusest meie seotud nimekirja, me ka kavatse tahavad
kuidagi võimalik teada, kus alguses meie trie on.
Mõned inimesed kutsuvad üritab puud, ja see on kui juur pärineb.
Nii et me tahame just meie puu veenduda, et me jääme maandatud
sinna, kus meie trie on.
Meil on juba selline läks üle
kuidas sa võiksid mõelda laadimist iga sõna sõnastikku.
Sisuliselt iga sõna sa lähed tahan kinnitada, läbi oma trie
ja teades, et iga element lapsed - me kutsusime seda last sel juhul -
vastab erinev täht, sa lähed tahan vaadata neid väärtusi
selle konkreetse indeks, mis vastab kirjale.
Nii mõtlesin kogu tee tagasi Caesar ja Vigenere,
teades, et iga täht saad mingi kaardi tagasi tähestikregistris,
kindlasti läbi Z saab olema üsna lihtne map üles tähestikulises kirja,
kuid kahjuks ülakomad on ka tunnustatud tegelane sõnu.
Ma pole isegi kindel, mida ASCII väärtus on
Nii et kui sa tahad leida indeks otsustada, kas sa tahad seda olla esimene
või viimane, sa pead tegema kõva kodeeritud tšeki, et
ja seejärel panna, et indeks 26, näiteks.
Siis te ei kontrolliks raha lastele [i]
kus [i] vastab ükskõik kirja sa oled.
Kui see on NULL, mis tähendab, et ei ole praegu võimaliku tähed
mis selles järjekorras, nii et sa lähed tahan malloc
ja teha uue sõlme ja on, et lapsed [i], et see
nii et loote - kui me sisestatud kirja arvesse ristküliku -
tegemisel laste mitte-null ja punkt arvesse, et uus sõlm.
Aga kui see ei ole null, nagu meie näiteks Foo
kui me juba jura, me jätkame,
ja me ei ole kunagi teha uus sõlm, vaid lihtsalt millega is_word tõeseks
aasta lõpus, et sõna.
>> Siis kui enne, sest siin olete tegelevad iga täht korraga,
see saab olema lihtsam suuruse, selle asemel, et arvutada
ja minna kogu puu ja arvutada, kui palju lapsi on mul
ja siis hargnevat, meenutades, kui palju on vasakul ja paremal küljel
ja asjad niimoodi, et see saab olema palju lihtsam
kui sa lihtsalt jälgida, kui palju sõnu sa lisades
kui olete tegelevad koormus.
Ja nii siis nii suurust saab lihtsalt tagasi globaalse muutuja suurus.
>> Nüüd aga kontrollida.
Samadele standarditele nagu enne, kui me tahame võimaldada juhul tundetus.
Samuti eeldame, et stringid on ainult tähti või ülakomade
sest lapsed on massiiv 27. pikk,
nii et kõik tähestiku tähti pluss ülakoma.
Sest kontrollida, mida sa teha tahad on, mida sa tahad alustada root
sest juur toob välja massiivi, mis sisaldab
kõik võimaliku alustades kirjas sõna.
Sa lähed, et alustada seal,
ja siis sa lähed, et kontrollida kas see väärtus NULL või mitte,
sest kui väärtus on NULL, mis tähendab, et sõnastikku ei ole mingit väärtust
mis sisaldavad selle kirja, et kindlas järjekorras.
Kui see on NULL, siis see tähendab, et sõna valesti kohe.
Aga kui see ei ole null, siis võite jätkata,
öelda, et esimene täht on võimalik esimese tähe sõna,
nii nüüd ma tahan vaadata, kas teine ​​kiri, et jada, jääb minu sõnaraamat.
Nii et sa lähed minema indeks laste esimese sõlme
ja kontrollima, kas see teine ​​täht on olemas.
Siis korrake seda protsessi kontrollida, kas seda jada on kehtiv või mitte
jooksul oma trie.
Kui sõlm lapsi, et indeks viitab null,
sa tead, et see jada ei ole olemas,
aga siis kui jõuad lõpuks sõna, et olete sisestanud,
siis sa tahad vaadata nüüd, et ma olen lõpetanud selle jada
ja leidis selle sees minu trie, on see, et sõna kehtib või mitte?
Ja nii siis sa tahad, et kontrollida, ja just siis, kui olete leidnud, et jada
siis sa tahad, et kontrollida, kas see sõna on kehtiv või mitte
sest mäletan tagasi eelmisel korral, et ma joonistasin, kus meil oli FOOB,
mis oli kehtiv jada, mis me leidsime, kuid ei olnud tegelikult kehtiv sõna ise.
>> Samamoodi lossimisõigusest üritab soovite maha kõik sõlmed oma trie.
Vabandust. Sarnaselt hash tabeleid, kus lossimiseks me vabastas kõik sõlmed,
aastal üritab tahame ka tasuta kõik sõlmed.
Unload tegelikult töötavad lihtsaim alt üles
sest need on peamiselt seotud nimekirju.
Nii et me tahame veenduda, et me kinni hoida kõiki väärtusi
ja tasuta neid kõiki otseselt.
Mis sa lähed tahan teha, kui te töötate trie
on sõita alt ja vaba madalaima võimaliku sõlme 1.
ja siis minna kuni kõik need lapsed ja siis vaba kõigile neile,
tõusevad ja siis vaba jne
Kind of like tegelevad alumine kiht trie 1.
ja siis läksime üles, kui olete vabanenud kõike.
See on hea näide sellest, kus rekursiivne funktsioon võib tulla käepärane.
Kui olete vabanenud alumine kiht oma trie,
siis helistada lossima kohta ülejäänud seda,
veenduge, et teil vabastada iga mini -
Võite liiki visualiseerida seda mini proovib.
Nii et teil on oma juur siin.
Ma lihtsalt lihtsustada see, et ma ei pea koostama 26 neist.
Nii et teil on need, ja siis need esindavad järjestused sõnad
kus kõik need väikesed ringid on kirjad, mis kehtivad tähejadad.
Jätkame lihtsalt natuke rohkem.
Mis sa lähed teha tahad on tasuta alt siin ja siis tasuta see üks
ja siis tasuta see üks allosas, enne kui vaba üks ülemine siin
sest kui sa tasuta midagi teine ​​tase siin,
siis tegelikult kaotaks see väärtus siin.
Sellepärast on oluline ka maha laadima jaoks trie veenduda, et sa vaba alt esimene.
Mida sa tahad teha, on öelda iga sõlme
Ma tahan maha laadida kõik lapsed.
>> Nüüd, kui oleme läinud üle lossimiseks jaoks hash tabelit meetod samuti trie meetod,
me ei kavatse soovite vaadata Valgrind.
Valgrind sa joosta järgmised käsud.
Sul on valgrind-v.
Sa kontrollimine kõik lekked, kui sa jooksed speller antud selle teatud teksti
sest speller peab võtma tekstifaili.
Nii Valgrind kestab oma programmi, ütleb teile, mitu baiti te eraldatud,
kui palju baite olete vabanenud, ja ta ütleb teile, kas te vabanenud lihtsalt piisavalt
või kas sa ei tasuta piisa,
või mõnikord saab isegi üle-vaba, nagu näiteks tasuta sõlme, mis on juba vabastatud
ja nii ta naaseb sa vead.
Kui te kasutate Valgrind, siis annan teile mõned teated
näitab, kas olete vabanenud kas alla piisavalt, lihtsalt piisavalt,
või rohkem kui piisavalt korda.
>> Osa sellest pset, see on vabatahtlik vaidlustada Big juhatus.
Aga kui me tegeleme nende andmete struktuurid
see on selline tore näha, kui kiiresti ja kuidas tõhus oma andmestruktuurid võiks olla.
Kas teie räsifunktsiooniga tulemus palju kokkupõrkeid?
Või on teie andmete suurus tõesti suur?
Kas see võtab palju aega, et läbida?
Aastal logi speller, see väljundid, kui palju aega te kasutate laadida,
et kontrollida, teostada suurus ja maha laadida,
ja nii need on postitatud Big Board,
kus saab võistelda oma klassikaaslastega
ja mõned töötajad, et näha, kes on kõige kiiremini õigekirja kontrollija.
Üks asi, mida ma tahaksin märkida, umbes hash tabeleid
on see, et seal on päris lihtne hash funktsioonid, et me võiksime mõelda.
Näiteks, teil on 26 kopad, ja nii iga ämber
vastab esimene täht sõna,
aga see läheb kaasa päris tasakaalustamata hash tabelit
sest seal on palju vähem sõnu, mis algavad X kui algab M näiteks.
Üks võimalus edasi minna speller on, kui soovite saada kõik muud funktsioonid alla
siis lihtsalt kasutada lihtsaid räsifunktsiooniga oleks võimalik saada oma koodi töötab
ja siis tagasi minna ja muuta suurust oma hash tabelit ja määratlus.
Seal on palju ressursse Internetis hash funktsioonid,
ja nii selle pset teil on lubatud uurida hash funktsioonid Internetis
mõned vihjed ja inspiratsiooni nii kaua, kui te veenduge, et tuua kus sul seda.
Sa oled teretulnud vaatama ja tõlgendama mõned räsifunktsiooniga et sa leiad internetist.
Tagasi, et sa võiksid näha, kui keegi kasutada trie
kas nende rakendamine on kiirem kui teie hash tabelit või mitte.
Võite esitada Big Board mitu korda.
See salvestab oma viimases sissekandes.
Nii et äkki sa muudad oma räsifunktsiooniga ja siis mõistad, et see on tegelikult palju kiiremini
või palju aeglasem kui enne.
See on natuke lõbusalt.
Seal on alati 1 või 2 töötajat, kes püüavad panna aeglaseim võimalik sõnastikku
nii et on alati lõbus vaadata.
>> Kasutamine pset on teil tekib speller koos vabatahtlik sõnaraamat
ja siis kohustuslik tekstifaili.
Vaikimisi, kui sa jooksed speller vaid tekstifaili ja ei täpsusta sõnastik
see saab kasutada sõnastikku tekstifail, suur üks
aastal cs50/pset5/dictionaries kausta.
Et üks on üle 100.000 sõnad.
Neil on ka väike sõnastik, mis on tunduvalt vähem sõnu
et CS50 on teinud teile.
Siiski saab väga lihtsalt lihtsalt teeb oma sõnaraamat
kui tahad lihtsalt töötavad väikest näidet -
Näiteks kui soovite kasutada gdb ja sa tead, konkreetsed väärtused
et sa tahad oma hash tabelit kaardistada välja.
Nii saate lihtsalt teha oma teksti faili lihtsalt baariga, BAZ, Foo ja jura,
teha, et tekstifail, eraldage need igaüks 1 rida,
ja siis teha oma tekstifail, sõna otseses mõttes sisaldab ainult võibolla 1 või 2 sõna
nii et sa tead täpselt, mida väljund peaks olema.
Mõned proovi tekstifailid, mis Big Board suorittaessasi väljakutse vaadata
on Sõda ja rahu ja Jane Austeni romaan või midagi sellist.
Nii et kui sa oled hakanud läbi, see on palju lihtsam teha oma tekstifaile
mis sisaldavad ainult paar sõna või võibolla 10
nii et võite aimata, millist tulemus peaks olema
ja siis vaadata seda vastu, et nii mitu kontrollitud näide.
Ja nii kuna me tegeleme ennustavad ja joonistus asju ümber,
jälle ma tahan teid julgustada kasutama pliiatsi ja paberi
sest see on tõesti aitab teil selle ühe -
juhtides nooled, kuidas hash tabelit või kuidas teie trie välja,
kui sa vabastades midagi kus nooled lähevad,
sa hoiad piisavalt, sa näed kõik seosed kaovad
ja langevad kuristikku lekkinud mälu.
Nii et palun, palun proovige juhtida asju isegi enne saate kirjutada koodi alla.
Joonista asju teha nii, et saate aru, kuidas asjad lähevad tööle
sest siis ma garanteerin, sa joosta vähem osuti muddles seal.
>> Hea küll.
Ma tahan soovida teile väga palju õnne, see pset.
See on ilmselt kõige raskema tee.
Nii et proovida alustada varakult, joonistada asju teha, joonistada asju teha, ja õnne.
See oli kiirtutvustus 5.
>> [CS50.TV]