[Powered by Google Translate] [Walkthrough - Problemo Serio 5] [Zamyla Chan - Universitato Harvard] [Jen CS50. - CS50.TV] 

Bone. Saluton, ĉiuj, kaj bonvenon al Walkthrough 5. 

Pset5 estas fuŝo, en kiu ni estos preni literumilo. Literumi-kontroliloj estas ege grava. Ĉu ĉi tiu iam okazis al vi? Vi laboras tre, tre hoard sur papero por kolizio kaj tiam ankoraŭ fini atingi tre ardo Rade kiel D aŭ D = kaj ĉiuj ĉar vi estas la liverwurst spoiler en la baleno larĝa vorto. Jes, provlegado vian kapsikoj estas afero de la, la plej granda senpoveco. Tio estas problemo kiu tuŝas vireca, vireca studentoj. Mi iam diris per mia sith lernojaro torturador ke mi neniam en bonan kolego. Kaj tio estas ĉio, kion mi iam volis, ke ĉio ajn knabo volas en mia aĝo, nur por eniri bonan kolego. Kaj ne nur iu kolego. Ne, mi volis iri al Ebur Juraj kolego. Do, se mi ne plibonigo, foriris estus miaj sonĝoj de iri al Harvard, Jale, aŭ Malliberejo - vi scias, en malliberejo, New Jersey. Do mi atingis min literumilo. Tio estas iom ekstrakto de unu el miaj preferataj parolata vorto artistoj, Taylor Malio. Ĉiuokaze, kiel li diras, la graveco de havi literumilo estas tre grava. 

Do bonvena Walkthrough 5, en kiu ni parolos pri pset5: fuŝo, en kiu ni faros nian plej propra literumilo. La iloj por ĉi tiu semajno, la dissendo kodo, tuj estos grava por rigardi nur kompreni la malsamajn funkciojn, ke via vortaro tuj havos. Ni efektive tuj estos havi multnombraj. C dosierojn kiuj kune fari nian pset. Kaj tiel rigardante tra la diversaj aspektoj, kvankam ni fakte ne redaktado unu el la dosieroj, speller.c, sciante kiel ĝi funkcias kun rilato al dictionary.c, kiuj ni skribos, tuj estos bela grava. La pset spec ankaŭ enhavas multajn utilajn informojn en terminoj de aĵoj kiujn vi povas supozi, reguloj kaj aĵoj kiel tiu, tiel certe legis la pset spec zorgeme por konsiloj. Kaj kiam en dubo de regulo aŭ io simila, tiam ĉiam rilatas al la pset spec aŭ Discuss. Ĉi pset tuj fidas peze sur punteros, do ni volas certigi, ke ni komprenas la diferencon inter aldonante steloj antaŭ la puntero la nomon kaj ampersands, kiom por liberigi ilin, ktp Do estante mastro punteros tuj estos tre utila en ĉi tiu problemo aro. Ni tuj rigardi en ligitaj listoj iom pli, kie ni havas elementojn kiuj ni nomas nodoj kiuj havas ambaŭ valoro tiel kiel puntero al la sekvanta nodo, kaj tiel esence ligas malsamaj elementoj unu post la alia. Estas kelkaj malsamaj ebloj de apliko vian realan vortaro. Ni tuj serĉos en du ĉefaj manieroj, kiu estas hash tabloj kaj poste provas. En ambaŭ el tiuj, ili implicas ian nocion de ligitaj listo kie vi elementoj ligitaj unu al la alia. Kaj tial ni tuj serĉos pri kiel vi eble povus funkcii ĉirkaŭ ligitaj lertaj, krei ilin, navigi en terminoj de kiel, ekzemple, enŝovu nodo en ĝin aŭ libera ĉiuj nodoj tiel. En terminoj de liberigante nodoj, kiuj estas vere gravaj ke ĉiufoje kiam ni malloc memoro, poste ni liberigi ĝin. Do ni volas certigi, ke neniu puntero iras unfreed, ke ni ne havas ajnan memoro likas. Ni tuj enkonduki ilon nomata Valgrind kiu kuras via programo kaj ĉekojn ĉu ĉiuj memoro kiun vi destinis estas tiam liberigita. Via pset nur kompletigi kiam ĝi funkcias kaj ĝi havas tutajn funkciojn, sed ankaŭ, Valgrind informas vin, ke vi ne trovis ajnan memoro likas. Fine, por ĉi pset, mi vere volas substreki - Mi volas diri, kiel kutime, mi estas definitive subtenanto de uzi plumon kaj paperon por via problemo aroj, sed por ĉi tiu, mi kredas ke plumo kaj papero tuj estos speciale grava kiam vi volas esti desegnante sagojn por aĵoj kaj kompreni kiel aferoj funkcias. Do certe klopodos uzi plumon kaj paperon por desegni aferojn de antaŭ vi get kodigo ĉar ĝi povus akiri iom senorda. 

Unue, ni iru en ligitaj listoj iom. Ligitaj listoj konsistas nodoj, kie ĉiu vertico havas valoro asociita kun ĝi, tiel kiel sagon al la sekva nodo post tio. Paro de aferoj gravaj kun la ligitaj listoj estas ke ni devas memori kie nia unua nodo estas, kaj tiam iam ni scios kie la unua nodo estas, tiel ni povas konsenti la nodo kiu la unua nodo punktoj al kaj poste unu post tio kaj la post tio. Kaj tiam la lasta elemento en via ligitaj listo estas ke nodo puntero ĉiam tuj indikas nula. Kiam nodo punktoj al nula, tiam vi scias, ke vi atingis la finon de la listo, ke tiu nodo estas la lasta, kiu tie estas nenio post tio. Ĉi tie en ĉi esquemática, vi vidas ke la sagoj estas la punteros, kaj la blua sekcio kie la valoro estas stokita, kaj tiam la ruĝan skatolon kun la puntero al ĝi estas la nodo puntero montrante la sekva nodo post tio. Kaj tial vi vidas tie, la D nodo notus al nula ĉar ĝi estas la lasta elemento en la listo. 

Ni rigardu kiel ni povus difini struct por nodo. Kaj ĉar ni volas havi plurajn nodoj, ĉi tuj fariĝi typedef struct en kiu ni iras al havi kelkaj malsamaj kazoj de nodoj. Kaj tial ni difini ĝin kiel nova datumtipo. Tie, ni havas typedef struct nodo. En ĉi tiu ekzemplo, ni pritraktas entjero nodoj, do ni havos entjero nomata valoro kaj tiam ni havas alian pointer, kaj en ĉi tiu kazo, ĝi estas puntero al nodo, tial ni havas struct nodo * nomas proksima. Kaj tiam ni nomas ĉi tiu tuta afero nodo. Certiĝu, ke vi sekvu tiun sintakson. Rimarku ke nodo estas reale referenciado super tiel kiel sub la frizita krampoj. Tiam teni spuro de kie mia unua nodo estas en ĉi ligillisto, tiam mi havas nodo puntero nomita kapo, kaj mi malloc spaco sufiĉa por la grandeco de nodo. Rimarki, tamen, ke kapo estas fakte nodo puntero kontraste al efektiva nodo mem. Do la kapo fakte ne enhavas ajnan valoron, nur notas al kiom la unua nodo en mia ligitaj listo estas. 

Por havi pli bonan senson de ligitaj listoj, ĉar ĝi estas tre grava teni spuro de certigante ke vi subtenas la ĉeno, Mi ŝatas pensi pri tio kiel homoj en linio tenante manojn, kie ĉiu persono estas tenante manojn kun la proksima. Vi ne povas vidi en ĉi desegno, sed esence ili estas montrante al la sekvanta persono kio estas sur ilia ĉeno. Kaj do se vi volas trairi ligillisto kie tiuj homoj - imagi ĉiuj el tiuj homoj havas valorojn asociita kun ili kaj ankaŭ indikas la proksiman personon en la linio - se vi volas trairi la ligillisto, ekzemple, al ĉu redakti la valoroj aŭ serĉu valoro aŭ io simila, tiam vi volas havi sagon al la specifa persono. Do ni tuj havos datumtipo nodo puntero. Por ĉi tiu kazo, ni nomas ĝin kursoro. Alia komuna maniero nomi tiun estus iterator aŭ io simila ĉar ĝi estas ripetanta super kaj efektive movante kiu nodo ĝi estas indikante. Ĉi tie estos nia kursoro. Nia kursoro estos unuaj indikas la unua elemento en nia listo. Kaj tiel kion ni volas fari estas ni esence esti kontinuado de la kursoro, movi ĝin de flanko al flanko. En ĉi tiu kazo, ni volas movi ĝin al la sekva elemento en la listo. Kun tabeloj, kion ni devus fari estas ni nur diras, ke ni pliigos la indekso de 1. En ĉi tiu kazo, kion ni bezonas por fari estas fakte trovi kiu persono tiu fluo persono indikante, kaj ke tuj estos la venonta valoro. Do se kursoro estas nur nodo pointer, tiam kion ni volas fari estas ni volas atingi la valoron kiu la kursoro montrante. Ni volas atingi ke nodo kaj tiam, iam ni estas en tiu nodo, trovi kie ĝi estas indikante. Por atingi la realan nodo ke la kursoro estas indikante, kutime ni indiki ĝin (* kursoro). Tio donus al vi la reala nodo ke la kursoro montrante. Kaj tuj poste, kion ni volas fari estas ni volas atingi kion ajn kiun nodo La sekva valoro estas. Por fari tion, por aliri la valoroj ene de la struct, ni havas la skalara operatoro. Tial do tio estus (* kursoro). Proksima. Sed ĉi tiu estas iom senorda en terminoj de havi la krampoj ĉirkaŭ la * kursoro, kaj tiel ni anstataŭigi ĉi tiu tuta frazo kun kursoro->. Tio ĉi estas streko kaj poste iu pli granda ol signo, tiel farante sago. kursoro-> proksima. Kiu reale preni al vi la nodo ke la kursoro punktoj al. Ke valoro estas de alia. Do anstataŭ havi la stelo kaj la skalara, vi anstataŭante ke kun sago. Esti tre zorgema por certigi ke vi provas uzi tiun sintakson. 

Nun ke ni havas niajn kursoro, se ni volas atingi la valoron, antaŭe, ni havis kursoro-> proksima, sed por aliri la valoro je la nodo ke la kursoro estas indikante, ni nur simple diras nodo-> valoro. De tie, ĝi estas de datumtipo ajn ni difinis la valoroj kaj la nodoj esti. Se temas pri int nodo, tiam kursoro-> valoro estas nur tuj estos entjero. Do ni povas fari operaciojn sur tiu, kontrolu egalecoj, atribui ĝin malsamaj valoroj, ktp Tial, kion vi volas fari se vi volas movi vian kursoron al la sekvanta persono, vi fakte ŝanĝi la valoron de la kursoro. Ekde kursoro estas nodo pointer, vi ŝanĝas la efektiva puntero adreso al la adreso de la venonta vertico en via listo. Tiu estas nur iom da kodo, kie vi povus persisti. Kie mi havas la komento fari ion, tie estas kie vi probable tuj aliri la valoro aŭ fari ion por fari kun tiu specifa nodo. Por ekigi ĝin, mi diras, ke mia kursoro komence tuj indikas la unuan elementon en la ligitaj listo. Kaj tial ĉe antaŭen, mi difinis kiel la kapo de la nodo. 

Kiel mi menciis antaŭe, liberigante estas vere grava. Vi volas certigi ke vi liberigi ĉiun eron en la listo iam vi finis kun ĝi. Kiam vi ne bezonas referenci iun el tiuj indikoj plu, vi volas certigi ke vi liberigi ĉiuj el tiuj indikoj. Sed vi volas esti tre zorgema tie en kiun vi volas eviti ajnan memoro likas. Se vi libera persono antaŭtempe, tiam ĉiuj el la punteros ke tiu nodo punktoj al tuj estos perdita. Irante al la persono ekzemple por fari ĝin iom pli altaj palisoj, ni havas ĉi tiujn personojn, krom en tiu kazo ili ŝvebis super lago kun monstro. Ni volas certigi ke ĉiufoje kiam ni liberigos, ni ne perdu kaj lasi iri ajna nodoj antaux ni efektive liberigis ilin. Ekzemple, se vi estus al simple nomas libera sur ĉi ulo ĉi tie, tiam li estus liberigita, sed tiam ĉiuj el ĉi tiuj infanoj devus tiam perdiĝos kaj ili derivas off kaj falos. Do ni volas certigi, ke anstataŭ, ni volas subteni ligon al la ceteraj. Nia kapo pointer, kiu notas al la unua ero en la listo. Estas ia kiel ŝnuro ankrumante la unua persono. Kion vi volus fari, kiam vi liberigi listo estas havi - Se vi volas liberigi la unua elemento unue, tiam vi povas havi portempa puntero ke antaŭ al kiom la unua elemento estas. Do vi havas vian temporal puntero montrante tie. Tiel, ni havas regadon de la unua nodo. Kaj poste, kiam ni scias ke la unua nodo tuj estos liberigita, tiam ni povas movi ĉi ŝnuro, ĉi ankro, nia kapo, por fakte indikas kion ajn la unua estas indikante. Do tiu kapo vere notas al la dua elemento nun. Nun ni estas permesita por liberigi ajn stokas en temp, kaj tiel ni povas viŝi ke sen ĝi endanĝerigi ĉiuj aliaj verticoj en nia listo. Alia maniero, ke vi povus fari tion eblis ĉiufoje kiam vi simple liberigi la lasta elemento en la listo ĉar ili estas garantiitaj ne esti indikis nenion. Do vi povus simple liberigi ĉi tiu, tiam liberaj ĉi tiu, tiam liberaj ĉi tiu. Tio definitive funkcias sed estas iom pli malrapida pro la naturo de la ligitaj lertaj, ni ne povas simple tuj salti al la lasta. Ni devas trairi ĉiu elemento en la ligitaj listo kaj kontrolu ĉu tio estas atentigo pri nula, kontrolu ĉiufoje, kaj tiam iam ni atingos la finon, tiam liberaj tio. Se vi estus fari ĉi procezo, vi vere estas kontrolanta tie, kontrolanta tie, tiam kontroli tie, liberigante ĝin, tiam tuj reen, kontrolanta tie, kontrolanta tie, liberigante ĝin, kontrolanta tie, kaj tiam liberigas ĝin. Kiu prenas iom pli da tempo. Yeah. 

[Studento] Ĉu ĝi estas ebla fari ligitaj listo kiu stokas eliron sagon al la fino? Tio definitive eblus. Ripeti la demandon, ĉu eblas havi ligitaj listo strukturo tia, ke vi havas puntero indikante la finon de la ligitaj listo? Mi dirus ke estas ebla, kaj ĉiufoje, ke vi enmetas ion en vian ligitaj listo vi devus aktualigi ke puntero kaj aĵoj tiel. Vi havus nodo * vosto, ekzemple. Sed kiam vi apliki ĉi tiun funkcion, oni devas pensi pri la komerca-offs, kiel kiomfoje mi tuj iros ripetanta super tio, kiel malfacile estas ĝin tuj estos al konservi trako de la vosto kaj ankaŭ la kapo tiel kiel mia iterator, kaj aferojn tiel. Ĉu tio -? >> [Studento] Yeah. Estas ebla, sed en terminoj de dezajno decidoj, vi devas pesi la ebloj. 

Jen skeleto de kodo kiu permesus vin liberigi ĉiu ero en ligitaj listo. Denove, ekde mi ripetanta super ligillisto, mi tuj volas havi ian kursoro aŭ iterator. Ni ripetanta ĝis la kursoro estas NULL. Vi ne volas persisti kiam via kursoro estas NULL ĉar tio signifas ke ne estas nenio en la listo. Tial jen mi fari portempan nodo * indikante kion mi konsideras estas la unua de mia listo, kaj tiam mi movi mian kursoro antaŭen 1 kaj tiam senpaga, kion ajn mi havis en la provizora stokado. 

Nun ni venas al la enmeto en ligitaj listoj. Mi havas tri nodoj en mia ligillisto, kaj ni iru al la simpla kazo kie ni volas enmeti alian nodon al la fino de nia ligitaj listo. Por fari tion, ĉiuj ni devus fari estas ni trairi trovi kie la nuna termino de la ligitaj listo estas, do ajn nodo estas indikante nula - jen ĉi tiu - kaj tiam diras, fakte, ĉi tiu estas ne tuj estos la lasta nodo; ni vere havos alian. Do ni devus tiu fluo unu punkto al kiom ni enmeto. Do nun tiu ruĝa persono tie igas la lasta nodo en la ligitaj listo. Kaj tial la trajton de la lasta nodo en la ligitaj listo estas kiu notas al nula. Tial, kion ni devus fari estas metita ĉi ruĝa ulo la puntero al nula. Tie. 

Sed kion se ni volis enmeti nodo inter la dua kaj tria? Tiu ne estas tiom simpla, ĉar ni volas certigi ke ni ne lasu iri de iu ajn nodo en nia ligitaj listo. Kion ni devus fari estas certiĝi ke ni ankrumi nin al ĉiu. Ekzemple, ni nomas tion la dua. Se vi diris la dua nun notas al ĉi nova kaj vi ĵus faris puntero tie, tiam tiu okazigus ĉi ulo perdas ĉar tie ne estas neniu ligo al li. Anstataŭe - Mi desegni ĉi denove. Pardonu mian artan kapablojn. Ni scias ke ni ne povas simple rekte ligi 2 al la nova. Ni devas certigi ke ni tenadi la lasta. Kion ni volus fari estas havi temporal puntero al la elemento kiu tuj estos aldonita plu. Tial ni havas portempan puntero tie. Ĉar ni scias, ke ĉi tiu tria estas tenis spuro de, 2 povas nun ligilon al nia nova. Kaj se tiu nova ruĝa ulo tuj estos en inter 2 kaj 3, tiam kio estas tiu ulo estas puntero tuj indikas? >> [Studento] Temp. Temp. Yeah. Tial ĉi ruĝa ulo La sekva valoro tuj estos temp. Kiam vi enmeto en ligitaj listoj, ni vidis, ke ni povus facile aldoni ion al la fino por krei portempan tabelo, aŭ se ni volis aldoni ion al la mezo de nia tabelo, tiam necesus iom pli miksanta ĉirkaŭe. Se vi volas, ekzemple, havas ordo ligillisto, tiam vi devas ia pesas la kostoj kaj profitoj de tiu ĉar se vi volas havi ordo tabelo, tio signifas ke ĉiu tempo kiu vi enmetas en ĝin, ĝi estas tuj prenos iom pli da tempo. Tamen, se vi volas poste, kiel ni trovos ni volas, serĉante tra ligitaj listo, tiam ĝi eble estus pli facile se vi scias, ke ĉio estas en ordo. Do eble vi volas pesas la kostoj kaj profitoj de tiu. 

Alia maniero por enmeti en ligitaj listo estas por enmeti en la komenco de listo. Se ni desegni nian ankron tie - ĉi tiu estas nia kapo - kaj tiam tiuj homoj ligitaj al ĝi, kaj poste ni havas novan nodon esti enmetita en la komenco, tiam kio povus ni volas fari? Kio estus malbona nur diras mi volas ligi la ruĝa al la blua, ĉar tio estas la unua? Kio okazus tie? Ĉiuj de ĉi tiuj tri estus perdiĝos. Do ni ne volas fari tion. Denove, ni lernis ke ni bezonas havi ian temporal puntero. Ni elektas havi temporal punkto al ĉi tiu viro. Tiam ni povas havi la blua punkto al la provizora kaj tiam la ruĝan punkton al la bluo. La kialo kial Mi uzas homoj ĉi tie estas ĉar ni vere volas bildigi tenante al la homo kaj certigante ke ni havas ligon al ili antaŭ ol ni lasis iri de alia mano aŭ io kiel tio. 

Nun ke ni havas la senton de ligitaj listoj - kiel ni povus krei ligillisto kaj krei la strukturoj por tiu konsistanta de la tipo difino por nodo kaj tiam certigi ke ni havas sagon al la kapo de tiu ligitaj listo - iam ni havas tion kaj ni scias kiel trairi tra tabelo, aliro diversaj elementoj, ni scias kiel enigi kaj ni scias kiel liberigi ilin, tiam ni povas eniri en fuŝo. Kiel kutime, ni havas sekcion de demandoj kiuj get vi uzis por mastruma kun ligitaj listoj kaj malsamaj strukturoj kiel vostoj kaj piloj. Tiam ni povas movi en fuŝo. 

Fuŝo havas en la dissendo kodo kelkaj dosieroj de graveco. Unue ni rimarkas ke ni havas ĉi Makefile tie, kiuj ni ne vere renkontis antaŭe. Se vi rigardis interne de la pset5 dosierujo, vi volas rimarki ke vi havas. H dosiero, tiam vi havas du. c dosierojn. Kio ĉi Makefile faras estas antaŭe, ni simple tajpi fari kaj tiam la programo nomo kaj tiam ni vidus ĉiuj tiuj argumentoj kaj flagoj pasis en la tradukilo. Kion la Makefile faras estas ni permesas kompili plurajn dosierojn multope kaj pasi en la flagoj kiujn ni deziras. Ĉi tie ni nur vidas tie estas kapdosiero tie. Tiam ni efektive havis du fontaj dosieroj. Ni havas speller.c kaj dictionary.c. Vi bonvenigas redaktanton la Makefile se vi deziras. Rimarku, ke ĉi tie se vi tajpas pura, tiam kio faras estas vere forigas ion tio estas la kerno. Se vi havas segmentación kulpo, esence vi ricevas kernan dump. Do tiu malbela iom dosiero aperos en via dosierujo nomita kerno. Vi volas forigi tiun por fari ĝin purigi. Ĝi forigas ajna exe kaj. O dosierojn. 

Ni rigardu en dictionary.h. Ĉi tio diras, ke ĝi deklaras vortaro de funkciojn. Ni havas maksimuman longon por ajna vorto en la vortaro. Ni diru ke tiu tuj estos la plej longa ebla vorto. Estas de longo 45. Do ni ne tuj havas vortojn kiuj superas tiu longa. Ĉi tie ni nur havas la funkcion prototipoj. Ni ne havas la aktuala efektivigo ĉar tion ni faros por ĉi pset. Sed kio estas tiu faras estas ekde ni pritraktas pli grandaj dosieroj tie kaj funcionalidad sur pli granda skalo, ĝi estas utila havi. h dosieron por ke iu alia legis aŭ uzante vian kodo povas kompreni kio okazas. Kaj eble ili volas apliki provas se vi faris hash tabloj aŭ inverse. Tiam ili dirus mia ŝarĝo funkcio, la reala aplikado tuj diferencas, sed ĉi tiu prototipo ne ŝanĝos. Jen ni kontrolu, kiu revenas vera se donita vorto estas en la vortaro. Tiam ni havas ŝarĝon, kiu esence prenas en vortaro dosieron kaj poste ŝarĝas ĝin en iu datumstrukturo. Ni havas grandecon, kiu, kiam vokis, revenas la grandeco de via vortaro, kiom da vortoj estas stokitaj en ĝi, kaj tiam malŝarĝi, kiu liberigas la tutan memoron, ke vi povus esti formovita dum farante vian vortaron. 

Ni rigardu dictionary.c. Ni vidas, ke ĝi aspektas tre simila al dictionary.h, krom nun nur havas ĉiujn el tiuj todos en ĝi. Kaj tiel tio estas via laboro. Fine, vi povas plenigi ekster speller.c kun ĉiuj de ĉi tiu kodo. Dictionary.c, kiam kuri, ne vere volas fari nenion, do ni rigardu al speller.c vidi la reala realigo de la literumilo. Kvankam vi ne tuj povas redakti iun el ĉi tiu kodo, gravas legi, kompreni kiam ŝarĝo vokis, kiam mi vokas ĉeko, nur por kompreni, mapaj ĝin, vidi kiel la funkcio funkcias. Ni vidas, ke ĝi estas kontrolanta por la ĝusta uzado. Esence, kiam iu kuras Speller, ĉi indikas ke ĝi estas nedeviga por ili pasi en vortaro dosieron ĉar tuj esti defaŭlte vortaro dosiero. Kaj tiam ili devas pasi en la teksto esti literumilo kontrolis. rusage traktas tempo ĉar parto de ĉi pset kiuj ni pritrakti poste ne nur duumaj funkciadon literumilo laborante sed fakte atingi ĝin esti rapida. Kaj tiel do estas kie rusage tuj eniri Tie, ni vidas la unua alvoko al unu el niaj dictionary.c dosieroj, kiuj estas ŝarĝo. Laŭdu revenas vera aŭ malvera - vera sur sukceso, falsa sur fiasko. Do, se la vortaro ne estas ŝarĝita pozitive, tiam la speller.c revenos 1 kaj quit. Sed se ĝi faras ŝarĝo ĝuste, tiam ĝi tuj daŭrigi. Ni daŭrigu, kaj ni vidas iun dosieron / S tie, kie tuj povas trakti kun malfermante la teksta dosiero. Jen, kion tiu faras, estas literumilo kontrolas ĉiun vorton en la teksto. Do kio speller.c faras ĉi tie estas ripetanta super cxiu el la vortoj en la teksto dosieron kaj tiam kontroli ilin en la vortaron. Tie, ni havas Bulea misspelled kiu vidos se ĉeko revenas veraj aŭ ne. Se la vorto estas vere en la vortaro, tiam ĉeko revenos vera. Tio signifas ke la vorto ne estas misspelled. Do misspelled estus falsa, kaj tial ni havas la bang tie, la indiko. Ni daŭre iras, kaj poste ĝi tenas spuro de kiom da misspelled vortoj estas en la dosiero. Ĝi daŭrigas kaj fermas la dosiero. Tiam ĉi tie, ĝi informas kiom da misspelled vortoj vi havis. Ĝi kalkulas kiom da tempo ĝi prenis por ŝarĝi la vortaron, kiom da tempo ĝi prenis por kontroli ĝin, kiom da tempo ĝi prenis al kalkuli la grandecon, kiu, kiel ni iros plu, devus esti tre malgranda, kaj tiam kiom da tempo ĝi prenis por malŝarĝi la vortaro. Jen super ni vidas la alvoko por malŝarĝi tie. Se ni kontroli grandecon ĉi tie, tiam ni vidos, ke tie estas la alvoko al grandeco kie determinas la grandeco de la vortaro. Awesome. 

Nia tasko por ĉi pset estas apliki ŝarĝo, kiu ŝarĝas la vortaro datumstrukturo - kiom vi elektas, estu ĝi hash tablo aŭ provu - kun vortoj de la vortaro dosiero. Tiam vi havas grandecon, kiu redonos la nombro de vortoj en la vortaro. Kaj se vi apliki ŝarĝo en inteligenta maniero, tiam grandeco devas esti bela facila. Tiam vi kontrolu, kiu kontrolu se donita vorto estas en la vortaro. Do speller.c pasas en kordoj, kaj tiam vi devas kontroli cxu tio kordoj estas enhavita en via vortaro. Rimarku ke ni ĝenerale havas norma vortaroj, sed en ĉi pset, esence ajna vortaro pasis en en ajna lingvo. Do ni ne povas simple supozi ke la vorto LA estas ene. La vorto FOOBAR povus esti difinita en iu vortaro kiun ni pasas in Kaj tiam ni malŝarĝi, kiu liberigas la vortaron de memoro. 

Unue, mi ŝatus iri super la hash tablo metodo pri kiel ni povus efektivigi ĉiuj el tiuj kvar funkciojn, kaj tiam mi iros sur la provas metodon, kiel ni apliki tiujn kvar funkciojn, kaj fine diskuto pri iuj ĝeneralaj konsiloj kiam vi faras la pset kaj ankaŭ kiel vi eble povus uzi Valgrind por kontroli por memoro likas. 

Ni eniras en la hash tablo metodo. Al hash tablo konsistas el listo de siteloj. Ĉiu valoro, ĉiu vorto, tuj iros en unu el tiuj siteloj. Al hash tablo ideale egale disdonas ĉiuj tiuj valoroj, ke vi pasis en kaj tiam popolas ilin en la rubujon tiaj ke ĉiu rubujo havas ĉirkaŭ egala nombro de valoroj en ĝi. La strukturo di hash tablo, ni havas aron da ligitaj listoj. Kion ni faras estas kiam ni pasas en valoro, ni kontrolu kie tiu valoro devas aparteni, kiuj balde apartenas al, kaj tiam metu ĝin en la ligillisto asociita kun tiu rubujo. Jen, kion mi havas estas hash funkcio. Ĝi estas int hash tablo. Do por la unua rubujo, ajna entjeroj sub 10 eniru la unuan sitelon. Ajna entjeroj super 10 sed sub 20 go en la dua, kaj poste tiel plu kaj tiel plu. Por mi, ĉiu rubujo estas reprezentanto tiuj nombroj. Tamen, diru mi estus pasi en 50, ekzemple. Ĝi aperas kvazaŭ la tri unuaj enhavas serion de dek numeroj. Sed mi volas permesi mia hash tablo por preni en ajna speco de entjeroj, do tiam mi devus filtri ĉiuj nombroj super 30 en la lastaj rubujo. Kaj tiel do, ke rezultos en speco de desequilibrado hash tablo. Ripeti, hash tablo estas nur tabelo de siteloj kie ĉiu rubujo estas ligillisto. Kaj tiel por determini kie ĉiu valoro iras, kiu kondutas iras enen, vi tuj volas kio nomiĝas hash funkcio kiu prenas valoron kaj tiam diras ĉi valoro korespondas al iu sitelo. Do supren supre ĉe ĉi tiu ekzemplo, miaj hash funkcio prenis ĉiu valoro. Ĝi kontrolis ĉu ĝi estis malpli ol 10. Se ĝi estis, ĝi metus ĝin en la unua rubujo. Ĝi kontrolas ĉu ĝi estas malpli ol 20, metas ĝin en la dua, se vera, ĉekojn se estas malpli ol 30, kaj poste metas ĝin en la tria rubujo, kaj tiam ĉio simple falas en la kvara rubujo. Do kiam ajn vi havas valoro, via hash funkcio metos tiun valoron en la taŭgan rubujo. La krada funkcio esence bezonas scii kiom da siteloj vi havas. Via hash tablo grandeco, la nombro de siteloj havas, ke tuj estos fiksita nombro, kiu estas de ci, al vi decidi, sed tuj estos fiksita nombro. Do, via hash funkcio estos dependi sur tiu determini kiuj balde singla ŝlosilo eniras en tia, ke ĝi estas egale distribuita. Simila al nia apliko de ligitaj listoj, nun ĉiu nodo en la hash tablo Efektive oni tuj havas tipo char. Do ni havas char tabelo nomis vorto kaj tiam alia sagon al la sekva nodo, kiu havas sencon ĉar tuj esti ligitaj listo. Memoru kiam ni estis ligitaj listoj, mi faris nodon * nomita kapo kiu indikante la unuan nodon en la ligitaj listo. Sed por nia hash tablo, ĉar ni havas plurajn ligitaj lertaj, kion ni volas estas ni volas nian hash tablo esti kiel, "Kio estas rubujo?" Al rubujo estas nur listo de nodo punteros, kaj tiel ĉiu ero en la rubujo estas vere indikante lia responda ligitaj listo. Reiru al ĉi esquemática, vi vidas ke la siteloj mem estas la sagojn, Ne realaj nodoj. Unu esenca propraĵo de kradaj funkcioj estas ke ili estas determina. Tio signifas ke kiam vi hash la nombro 2, ĝi devus redoni la sama rubujo. Ĉiu unuopa valoro kiu iras en la krada funkcio, se ripetis, devas preni la sama indico. Do, via hash funkcio redonas la indekso de la tabelo kie tiu valoro apartenas. Kiel mi menciis antaŭe, la nombro de siteloj estas fiksa, kaj tiel viaj indekso ke vi revenos devas esti malpli ol la nombro de siteloj sed pli granda ol 0. La kialo kial ni havas kradaj funkcioj anstataŭ nur unu sola ligitaj listo aŭ unu sola tabelo estas ke ni volas esti kapabla salti al iu sekcio plej facile se ni konas la karakterizo de valoro - anstataŭ devi serĉi tra la tuta tuta vortaro, povi salti al iu sekcio de ĝi. Via hash funkcio devus konsideri ke ideale, ĉiu rubujo havas proksimume la sama nombro de klavoj. Ekde la hash tablo estas serio de ligitaj lertaj, tiam la ligitaj lertaj sin tuj havas pli ol unu nodo. En la antaŭa ekzemplo, du malsamaj nombroj, kvankam ili ne estis egalaj, kiam hashed, denove la sama indico. Do kiam vi traktas kun vortoj, unu vorton, kiam hashed estus la sama hash valoro kiel alia vorto. Tion ni nomas kolizio, kiam ni havas nodo ke, kiam hashed, la ligitaj listo en tiu sitelo ne estas malplena. La tekniko kiu ni nomas estas lineara tuŝoprobado, kie vi eniru la ligitaj listo kaj poste trovi, kie vi volas enmeti ke nodo ĉar vi havas kolizio. Vi povas vidi, ke povus esti komerca-off here, right? Se vi havas tre malgrandan hash tablo, tre malgranda nombro de siteloj, tiam vi havos multe da kolizioj. Sed tiam, se vi faras tre grandan hash tablo, vi probable tuj minimumigi la kolizioj, sed tuj estos tre granda datumstrukturo. Tie tuj estos komerco-offs kun tio. Do kiam vi faras vian pset, provu ludi ĉirkaŭ inter eble farante pli malgranda hash tablo sed tiam sciante ke ĝi estas tuj prenos iom pli longa tra la diversaj elementoj de tiuj ligitaj listoj. 

Kio ŝarĝo tuj fari estas persisti sur cxiu vorto en la vortaro. Ĝi pasas en puntero la vortaro dosiero. Do vi iras por utiligi la dosiero / S funkcioj kiuj vi majstris en pset4 kaj persisti sur cxiu vorto en la vortaro. Vi volas ĉiu vorto en la vortaro por igi nova nodo, kaj vi tuj meti ĉiu el tiuj nodoj ene de via vortaro datumstrukturo. Kiam ajn vi ricevas novan vorton, vi scias ke ĝi tuj fariĝis nodo. Do vi povas iri straightaway kaj malloc nodo puntero por ĉiu nova vorto, kiun vi havas. Jen Mi vokas mian nodo puntero new_node kaj mi mallocing kio? La grandeco de vertico. Tiam legi la reala linio de dosiero, ĉar la vortaro estas vere stokita per vorto kaj tiam nova linio, kion ni povas utiligi estas la funkcio fscanf, per dosiero estas la vortaro dosiero ni pasis en, tiel skanu la dosieron por kordoj kaj lokoj kiuj kordoj en la lasta argumento. Se vi rememoras reveni al unu el la prelegoj, kiam ni iris super kaj tipon de senŝeligita la manteloj denove sur la CS50 biblioteko, ni vidis efektivigo de fscanf tie. Reiri al fscanf, ni havas la dosieron kiu ni legas de, ni serĉas ĉenon en tiu dosiero, kaj tiam ni metante gxin en tie mi havas new_node-> vorton ĉar new_node estas nodo pointer, ne estas reala nodo. Tial Mi diris new_node, mi volas iri al la nodo ke ĝi estas indikante kaj poste atribui tiun valoron al vorto. Ni volas tiam preni tiun vorton kaj enmeti ĝin en la hash tablo. Realigi ke ni faris new_node nodo puntero ĉar ni tuj volas scii kion la adreso de tiu nodo estas kiam ni enŝovu ĝin en ĉar la strukturo de la nodoj sin, de la struct, estas ke ili havas puntero al nova nodo. Tial kio estas la adreso de tiu nodo tuj indikas? Tio adreso tuj estos new_node. Ĉu tio havas sencon, kial ni fari new_node nodo * kontraste al nodo? Okay. Ni havas unu vorton. Ke valoro estas new_node-> vorton. Kiu enhavas la vorton el la vortaro, ke ni volas enigo. Do kion ni volas fari estas ni volas nomi nian hash funkcio sur tiu linio cxar nia hash funkcio prenas en ĉenon kaj poste revenas al ni entjero, kie tiu entjero estas la indekso kie hashtable en tiu indico reprezentas tiun rubujon. Ni volas preni tiun indekso kaj poste iru al tiu indekso de la hash tablo kaj poste uzas tiun ligitaj listo por enigi la nodo ĉe new_node. Memoru ke tamen vi decidas enŝovu vian nodo, ĉu ĝi estas en la mezo, se vi volas ordigi ĝin aŭ komence aŭ fine, nur certigi ke via lasta nodo ĉiam notas al nula ĉar tio estas la sola maniero por ke ni scias, kie la lasta elemento de nia ligitaj listo estas. 

Se grandeco estas entjero kiu reprezentas la nombro de vortoj en vortaro, tiam unu maniero fari tion estas ke kiam ajn grandeco estas nomita ni iru tra ĉiu ero en nia hash tablo kaj tiam persisti tra ĉiu ligitaj listo ene de la hash tablo kaj poste kalkuli la longon de tiu, kreskanta nia nombrilo 1 per 1. Sed ĉiufoje tiu grandeco estas vokitaj, por ke tuj prenas longan tempon ĉar ni tuj estos lineare tuŝoprobado ĉiu unuopa ligitaj listo. Anstataŭe, ĝi tuj estos multe pli facile se vi observos spuro de kiom da vortoj estas pasitaj in Se do vi inkludas nombrilo inter viaj ŝarĝo funkcio ke ĝisdatigoj kiel necesa, tiam vendotablo, se vi starigis gxin al suma variablo, povos aliri por grandeco. Do kio grandeco povus simple fari estas en unu linio, ĝuste redoni la vendotablo valoro, la grandeco de la vortaro, kiun vi jam traktis en ŝarĝo. Tion mi volis diri kiam mi diris se vi apliki ŝarĝo en helpema maniero, tiam grandeco tuj estos bela facila. 

Do nun ni preni por kontroli. Nun ni pritraktas vortojn el la eniga teksto-dosiero, kaj tiel ni tuj estos kontroli ĉu ĉiuj tiuj enigo vortoj estas vere en la vortaro aŭ ne. Simila al Scramble, ni volas enkalkuli kazo insensibilidad. Vi volas certigi, ke ĉiuj de la vortoj pasis en, kvankam ili estas miksitaj kazo, kiam nomas kun linia kompari, estas ekvivalento. La vortoj en la vortaro tekstaj dosieroj estas fakte ĉiuj minuskla. Alia afero estas ke oni povas supozi, ke ĉiu vorto pasis en, ĉiu linio, tuj estos ĉu alfabeta aŭ enhavi apostrofoj. Apostrofoj tuj estos valida vortoj en nia vortaro. Do se vi havas vorton kun apostrofo S, jen reala leĝa vorto en via vortaro ke tuj estos unu el la nodoj en via hash tablo. Kontrolu operacias kun se la vorto ekzistas, tiam ĝi estas alvenis al esti en nia hash tablo. Se la vorto estas en la vortaro, tiam ĉiuj el la vortoj en la vortaro estas en la hash tablo, do ni serĉas ĉi vorto en la hash tablo. Ni scias ke ekde ni implementado nia hash funkcio tia, ke ĉiu sola vorto estas ĉiam hashed al la sama valoro, tiam ni scias ke en loko de serĉado tra nia tuta tuta hash tablo, ni povas efektive trovi la ligillisto, ke tiu vorto devus aparteni al. Se estis en la vortaro, tiam ĝi estus en tiu sitelo. Kion ni povas fari, se vorto estas la nomo de nia string pasis en, ni povas nur hash tiun vorton kaj rigardu la ligitaj listo en la valoro de hashtable [hash (vorto)]. De tie, kion ni povas fari estas ni havas pli malgrandan subaro de nodoj al serĉi ĉi tiun vorton, kaj tiel ni povas trairi la ligillisto, uzante ekzemplo de pli frue en la walkthrough, kaj tiam nomita string kompari sur la vorto kien la kursoro estas indikante, tiun vorton, kaj vidi, cxu tiuj kompari. Depende de la maniero kiun vi organizos vian hash funkcio, se ĝi estas ordo, vi eble povos reveni falsa iom pli frue, sed se estas unsorted, tiam vi volas daŭrigi lauxiris tra viaj ligitaj listo ĝis vi trovas la lasta elemento de la listo. Kaj se vi ankoraŭ ne trovis la vorton de la tempo vi atingis la finon de la ligitaj listo, tio signifas, ke via vorto ne ekzistas en la vortaro, kaj por ke vorto estas nevalida, kaj ĉeko devus reveni falsaj. 

Nun ni venas al malŝarĝi, kie ni volas liberigi ĉiujn nodoj kiuj ni malloc'd, tiel libera ĉiuj nodoj ene de nia hash tablo. Ni tuj volas persisti super ĉiuj el la ligitaj lertaj kaj libera ĉiuj nodoj en tio. Se vi rigardas supre en la walkthrough al la ekzemplo kie ni liberigi lerta kunligita, tiam vi volas ripeti tiun procezon por ĉiu elemento en la hash tablo. Kaj mi iros sur oriento al la fino de la walkthrough, sed Valgrind estas ilo, kie vi povas kontroli ĉu vi bone liberigitaj ĉiu nodo ke vi malloc'd aŭ io ajn alia ke vi malloc'd, ajna alia puntero. Do jen hash tabloj, kie ni havas finia nombro de siteloj kaj hash funkcio kiu prenos valoron kaj poste atribui tiun valoron al iu sitelo. 

Nun ni venas al provoj. Provas speco de rigardo kiel ĉi tiu, kaj mi ankaŭ nudigos ekzemplo. Esence, vi havas tuta tabelo de potenciala literoj, kaj poste kiam ajn vi konstrui vorton, tiu litero povas esti ligitaj por vortaro por doni abundan gamon de ebloj. Iuj vortoj starti kun C sed tiam daŭrigas kun A, sed aliaj daŭrigi kun O, ekzemple. Al trie estas vojo de bildiganta ĉiuj eblaj kombinoj de tiuj vortoj. Al trie tuj konservi trako de la sekvenco de literoj kiuj formas parton vortoj, debranĉo kiam necesa, kiam unu litero povas esti sekvata de oblo de literoj, kaj fine indiki je ĉiu punkto ĉu tiu vorto estas valida aŭ ne ĉar se vi literumas la vorton MAT, MA Mi ne kredas estas valida vorto, sed MAT estas. Kaj tiel en via trie, ĝi indikus ke post MAT tio fakte validas vorto. Ĉiu nodo en nia trie vere tuj enhavas aron de nodo punteros, kaj ni tuj havas, specife, 27 el tiuj nodo punteros, unu por ĉiu litero en la alfabeto tiel kiel la apostrofo karaktero. Ĉiu elemento en tiu tabelo estas mem tuj atentigi al alia nodo. Do se tiu nodo estas NULL, se ne estas nenio post tio, tiam ni scias ke ne estas pliaj leteroj en tiu vorto sekvenco. Sed se tiu nodo estas ne NULL, tio signifas ke estas pli literojn en tiu letero sekvenco. Kaj tiam plue, ĉiu nodo indikas ĉu ĝi estas la lasta karaktero de vorto, aŭ ne. 

Ni iru en ekzemplo de trie. Unue mi havas spacon por 27 nodoj en ĉi tabelo. Se mi havas la vorton TRINKEJO - Se mi havas la vorton TRINKEJO kaj mi volas enmeti ke en, la unua litero estas B, do se mia trie estas malplena, B estas la dua litero de la alfabeto, do mi tuj deziras enmeti ĉi tie en ĉi tiu indekso. Mi tuj devos B tie. B estas tuj estos nodo kiu notas al alia tabelo de ĉiuj eblaj signoj kiu povas sekvi post la litero B. En ĉi tiu kazo, mi traktas la vorton TRINKEJO, do A iros tien. Post A, mi havas la literon R, do tiam A nun notas al lia propra kombinaĵo, kaj tiam R estos ĉi tie. TRINKEJO estas kompleta vorto, do tiam mi havos R punkto al alia nodo kiu diras, ke tiu vorto estas valida. Ke nodo ankaŭ havos aron de nodoj, sed tiuj povus esti NULL. Sed esence, povas daŭrigi tiel. Kiu igos iom pli klara kiam ni iros al malsama ekzemplo, tiel simple toleras min tie. Nun ni havas TRINKEJO ene de nia vortaro. Nun supozu ke ni havas la vorton Baz. Ni komencu per B, kaj ni jam havas B kiel unu el la literoj kiuj estas en nia vortaro. Tio sekvis kun A. Ni havas A jam. Sed tiam anstataŭe, ni havas Z jeno. Tial ero en nia tabelo tuj estos Z, kaj tiel do oni tuj indikas alian valida fino de la vorto. Do ni vidas, ke kiam ni daŭrigas tra B kaj tiam A, estas du malsamaj ebloj nuntempe en nia vortaro por vortoj kiuj komencas kun B kaj A. Diras, ke ni volis enmeti la vorton FOOBAR. Tiam ni farus eniro en F. F estas nodo kiu notas al tuta tabelo. Ni trovus ho, iru al O, ho tiam Ligiloj al tuta listo. Ni havus B kaj tiam daŭrigas, ni havus A kaj tiam R. Tial FOOBAR trairas la tutan vojon malsupren ĝis FOOBAR estas korekta vorto. Kaj tiel do ĉi tio estus valida vorto. Nun diru nian proksiman vorton en la vortaro estas vere la vorto FOO. Ni dirus F. Kio sekvas F? Mi vere jam havos spacon por O, do mi tuj daŭrigi. Mi ne bezonas fari novan. Daŭrigi. FOO estas valida vorto en ĉi vortaro, do tiam mi iros por indiki ke tio estas valida. Se mi haltas mian sekvenco tie, tio estus ĝusta. Sed se ni daŭrigas nian vico de FOO malsupren al B kaj nur havis FOOB, FOOB ne estas vorto, kaj tio ne indikis kiel valida. En trie, vi ĉiun nodon indikante ĉu ĝi estas valida vorto aŭ ne, kaj tiam ĉiu nodo havas ankaŭ tabelo de 27 nodo punteros kiu tiam punkto al nodoj sin. 

Jen estas maniero de kiel vi eble volas difini ĉi. Tamen, ĝuste kiel en la hash tablo ekzemple, kie ni havis nodon * kapo por indiki la komenco de nia ligitaj listo, ni ankaŭ tuj volis iel scii kie la komenco de nia trie estas. Iuj personoj alvoko provas arboj, kaj tie estas kie radiko devenas. Do ni volas ke la radiko de nia arbo por certigi ke ni restu bazite al kie ajn nia trie estas. Ni jam ia transiris la vojo vi povus pensi ŝarĝas ĉiu vorto en la vortaro. Esence, por ĉiu vorto kiun vi tuj volas persisti per via trie kaj sciante, ke ĉiu elemento en la infanoj - ni nomas ĝin infanoj en ĉi tiu kazo - korespondas al malsama litero, vi tuj volas kontroli tiujn valorojn en tiu aparta indekso kiu respondas al la litero. Do pensante la tutan vojon reen al Cezaro kaj Vigenère, sciante, ke ĉiu litero oni povas ia mapo reen al alfabeta indekso, definitive A tra Z tuj estos bela facila por mapi al alfabeta leteron, sed bedaŭrinde, apostrofoj estas ankaŭ akceptita karaktero en vortoj. Mi eĉ ne certas kion la ASCII valoro estas, tiel por ke, se vi volas trovi indekson por decidi ĉu vi volas ĝin al esti ĉu la unua aŭ la lasta, vi devos fari malfacilan kodita ĉeko por ke kaj tiam metis tiun en indekso 26, ekzemple. Tial vi kontroli la valoron al infanoj [i] kie [i] respondas al kiom letero vi estas en. Se tio NULL, tio signifas ke ne estas aktuale ajna ebla literoj devenaj de tiu antaŭa vico, do vi tuj volas malloc kaj fari novan nodon kaj havas ke infanoj [i] punkto al ĝi por ke vi kreas - kiam ni insertos leteron en la rektangulo - farante infanoj ne-NULL kaj punkto en tiu nova nodo. Sed se tiu ne estas NULL, kiel en nia petskribo de FOO kiam ni havis jam FOOBAR, ni daŭrigos, kaj ni ne estas iam farante nova nodo sed prefere nur opcio is_word al vera fine de tiu vorto. 

Tial, kiel antaŭe, ĉar ĉi tie vi pritraktas ĉiun literon samtempe, ĝi tuj estos pli facile por vi por grandeco, anstataŭ devi kalkuli kaj iru tra la tuta arbo kaj kalkuli kiom da infanoj mi havas kaj tiam debranĉo, memorante kiom estas sur la maldekstra flanko kaj sur la dekstra flanko kaj aĵoj kiel tiu, ĝi tuj estos multe pli facile por vi se vi nur konservi trako de kiom da vortoj vi aldonante en kiam vi kontraktanta kun ŝarĝo. Kaj tiel do tiel grandeco povas simple reveni al monda variablo de grandeco. 

Nun ni venas por kontroli. Samaj normoj kiel antaŭe, kie ni volas enkalkuli kazo insensibilidad. Tiel, ni supozas, ke la kordoj estas nur alfabeta karakteroj aŭ la apostrofoj ĉar infanoj estas tabelo de 27 longaj, tiel ĉiuj leteroj de la alfabeto plus la apostrofo. Por kontroli kion vi volas fari estas vi volas komenci ĉe la radiko ĉar la radiko indikas tabelo kiu enhavas ĉiuj eblaj startanta literoj de vorto. Vi tuj komenci tie, kaj tiam vi tuj kontroli estas tiu valoro NULL aŭ ne, ĉar se la valoro estas NULL, tio signifas ke la vortaro ne havas neniun valoroj kie troviĝas la leteron en tiu aparta ordo. Se ĝi estas NULL, tiam tiu signifas ke la vorto estas malbone skribita tuj. Sed se ĝi ne estas NULL, tiam vi povas daŭrigi, diri ke unua litero estas ebla unua litero en vorto, do nun mi volas kontroli ĉu la dua letero, ke vico, estas en mia vortaro. Do vi tuj iru al la indekso de la filoj de la unua nodo kaj kontrolu ĉu tiu dua letero ekzistas. Tiam vi ripeti tiun procezon por kontroli ĉu tiu vico estas valida aŭ ne inter viaj trie. Krom se la nodo infanoj en tiu indekso punktoj al nula, vi scias, ke tiu vico ne ekzistas, sed tiam, se vi atingas la fino de la vorto, kiun vi inputted, tiam vi volas kontroli nun ke mi kompletigis ĉi vico kaj trovis ĝin en mia trie, estas ke vorto valida aŭ ne? Kaj tiel do vi volas kontroli tion, kaj tio estas kiam se vi trovis ke vico, tiam vi volas kontroli, ĉu tiu vorto estas valida aŭ ne ĉar memori reen en la antaŭa kazo kiun mi tiris kie ni havis FOOB, kiu estis valida sekvenco kiu ni trovis, sed ne estis reala valida vorto mem. 

Simile, por malŝarĝi en la klopodoj vi volas malŝarĝi ĉiuj nodoj en via trie. Pardonu. Simila al la hash tabloj kie en malŝarĝi ni liberigxis ĉiuj nodoj, en la klopodoj ni volas ankaŭ liberigi ĉiujn nodoj. Malŝarĝi efektive funkcias plej facila el fundo supren ĉar ĉi tiuj estas esence ligitaj listoj. Do ni volas certigi, ke ni tenas al ĉiuj de la valoroj kaj libera ĉiuj ili eksplicite. Kion vi tuj volas fari se vi laboras kun trie estas vojaĝi al la fundo kaj libera la plej malalta ebla nodo unua kaj poste iru al ĉiuj el tiuj infanoj kaj tiam senpaga ĉiuj el tiuj, iru kaj tiam senpaga, ktp Ia kiel trakti kun la fundo tavolo de la trie unua kaj poste irante supren supro iam vi liberigita ĉion. Ĉi tiu estas bona ekzemplo de kie rekursia funkcio povus veni en oportuna. Kiam vi liberigis la fundo tavolo de via trie, tiam vi nomas malŝarĝi en la resto de ĝi, certigante ke vi liberigi ĉiun mini - Vi povas ia bildigi lin kiel mini provoj. Do vi havas vian radikon tie. Mi ĵus simplificadora ĝi do mi ne devas desegni 26 el ili. Do vi havas ĉi tiuj, kaj tiam ĉi tiuj reprezentas sekvencoj de vortoj kie ĉiuj el ĉi tiuj malgranduloj rondoj estas literoj kiuj estas validaj sekvencoj de literoj. Ni daŭrigos nur iom pli. Kion vi tuj volas fari estas libera la fundo tie kaj tiam senpaga ĉi tiu kaj poste liberaj ĉi tiu malsupre antaŭ vi liberigi la plej supra tien ĉar se vi liberan ion en la dua nivelo tie, tiam vi vere perdus tiun valoron tie. Tial ĝi estas grava en malŝarĝi por trie por certigi ke vi liberigos la fundo unua. Kion vi volus fari estas diri por ĉiu nodo Mi volas malŝarĝi ĉiuj de la infanoj. 

Nun kiam ni iris trans malŝarĝi la hash tablo metodo tiel kiel la trie metodo, nin tuj volas rigardi Valgrind. Valgrind vi kuras kun jenaj ordonoj. Vi havas valgrind-v. Vi kontrolanta por ĉiuj filtras kiam vi kuros Speller donita ĉi certaj teksto ĉar Speller bezonas preni en teksta dosiero. Do Valgrind kuros via programo, diros al vi, kiom da bitokoj vi destinis, kiom da bitokoj vi liberigas, kaj diros al vi ĉu vi liberigita nur tiom da aŭ ĉu vi ne liveris sufiĉe, aŭ kelkfoje vi povas eĉ tro libera, kiel libera nodo ke tio jam estas liberigitaj kaj tiel ĝi revenos al vi erarojn. Se vi uzas Valgrind, ĝi donos al vi mesaĝojn indikante ĉu vi liberigita ĉu malpli ol sufiĉa, nur sufiĉe, aŭ pli ol sufiĉa fojoj. 

Parto de tiu pset, estas laŭvola defii The Big Estraro. Sed kiam ni pritraktas tiujn datumstrukturoj ĝi estas speco de amuze vidi kiel rapide kaj kiel efika vian datumstrukturoj eblus. Ĉu viaj hash funkcio rezulto en tereno de kolizioj? Aŭ via datumoj grandeco vere granda? Ĉu ĝi prenas multan tempon por trairi? En la log'o da Speller, ĝi eligas kiom da tempo vi uzas por ŝarĝi, por kontroli, por efektivigi grandeco, kaj malŝarĝi, kaj tiel tiuj estas eldonitaj en The Big Estraro, kie vi povas konkurenci kontraŭ viaj samklasanoj kaj iuj stabanojn por vidi kiu havas la plej rapida literumilo. Unu afero, kiun mi ŝatus noti pri la hash tabloj estas, ke estas kelkaj belaj simpla kradaj funkcioj, ke ni povus pensi. Ekzemple, vi havas 26 siteloj, kaj tiel cxiu rubujo respondas al la unua litero en vorto, sed tio okazas al rezulti en belan desequilibrado hash tablo ĉar estas multe malpli da vortoj kiuj komencas kun ikso ol komenci kun M, ekzemple. Unu vojo por iri sur Speller estas se vi volas ricevi ĉiujn aliajn funkciojn sube, tiam simple uzi simplan hash funkcion por povi ricevi la kodo kurante kaj poste reiri kaj ŝanĝi la grandecon de via hash tablo kaj la difino. Estas multe da rimedoj en la Interreto por kradaj funkcioj, kaj tiel por tiu ĉi pset vi rajtas enketi kradaj funkcioj en la Interreto por iuj aludoj kaj inspiro tiel longe kiel vi certigi por citi kie vi ricevis ĝin de. Vi estas bonvena por rigardi kaj interpreti iuj hash funkcio kiu vi trovas en Interreto. Reen al tio, vi eble povus vidi se iu uzis trie ĉu ilia efektivigo estas pli rapida ol via hash tablo aŭ ne. Vi povas submetiĝi al The Big Estraro plurfoje. Ĝi gravuros via plej freŝaj eniro. Do eble vi ŝanĝos vian hash funkcio kaj tiam rimarkas ke fakte multe pli rapida aŭ multe pli malrapida ol antaŭe. Tio estas iom da amuza maniero. Ĉiam 1 aŭ 2 stabanojn, kiuj klopodas fari la plej malrapida ebla vortaro, por ke ĉiam amuze rigardi. 

La uzado dum la pset estas vi kuras Speller kun laŭvola vortaro kaj tiam deviga teksta dosiero. Implicite, kiam vi kuris Speller kun nur teksta dosiero kaj ne specifi vortaro, ĝi tuj uzi la vortaron teksta dosiero, la granda unu en la cs50/pset5/dictionaries dosierujo. Ke oni havas pli ol 100.000 vortojn. Ili ankaŭ havas malgrandan vortaron kiu havas konsiderinde malpli da vortoj ke CS50 faris por vi. Tamen, vi povas tre facile simple vian propran vortaro se vi volas nur esti laborante en malgrandaj ekzemploj - ekzemple, se vi volas uzi gdb kaj vi konas la specifan valoroj ke vi deziras ke viaj hash tablo por mapi al. Do vi povas simple fari vian propran teksta dosiero nur kun TRINKEJO, Baz, FOO, kaj FOOBAR, fari ke en teksto-dosiero, apartigi tiujn ĉiu kun 1 linio, kaj tiam fari vian propran teksta dosiero kiu laŭvorte nur enhavas eble 1 aŭ 2 vortojn por ke vi sciu precize kion la eligo devus esti. Kelkaj el la specimeno tekstaj dosieroj ke La Granda Estraro kiam vi kuros defio kontrolos estas Milito kaj Paco kaj Jane Austen romano aŭ io kiel tio. Do kiam vi komencante, estas multe pli facile fari vian propran tekstaj dosieroj kiuj enhavas nur kelkajn vortojn aŭ eble 10 por ke vi povas aŭguri kio la rezulto devus esti kaj tiam kontroli ĝin kontraŭ tio, tiom pli kontrolita ekzemplo. Kaj tiel ekde ni pritraktas antaŭdirante kaj desegno aferojn ĉirkaŭe, denove mi volas kuraĝigi vin uzi plumon kaj paperon ĉar ĝi estas vere helpos al vi kun ĉi tiu - desegnaĵo la sagoj, kiel la hash tablo aŭ kiel via trie aspektas, kiam vi liberigante io kie la sagoj iras, vi tenas al sufiĉas, ĉu vi vidas neniun ligiloj malaperi kaj fali en la abismo de filtrita memoro. Do bonvolu, bonvolu provi desegni aferojn eĉ antaŭ ol vi atingos skribi kodo sube. Desegni aferojn por ke vi komprenu kiel la aferoj iras labori ĉar tiam Mi garantias al vi kuros en malpli puntero muddles tie. 

Bone. Mi volas deziri al vi la plej bona el sorton kun tiu pset. Estas probable la plej malfacila unu. Do provu komenci frue, desegni aferojn, desegni aferojn, kaj bona sorto. Tio estis Walkthrough 5. 

[CS50.TV]