[MUZIKO Ludanta] 

ROB Bowden: Hi. Mi Rob. Kaj ni ĉi solvo eksteren. Do jen ni tuj apliki ĝenerala tabelo. Ni vidas, ke la struct nodo de nia tablo tuj aspekti kiel ĉi tio. Do ĝi estas tuj havos char vorto tabelo de grandeco kanton + 1. Ne forgesu la + 1, ekde la maksimuma vorton en la vortaro estas 45 karakteroj. Kaj tiam ni tuj bezonas unu ekstra karaktero por la backslash nulo. 

Kaj tiam nia hashtable en ĉiu sitelo tuj butika ligillisto de nodoj. Ni ne faras lineara sondado tie. Kaj do, por ligi al la sekva elemento en la sitelo, ni bezonas struct nodo * proksima. OK. Do, tio estas kion nodo aspektas. 

Nun tie estas la deklaro de nia hashtable. Ĝi tuj devos 16.834 siteloj. Sed tiu nombro ne vere gravas. Kaj fine, ni tuj havos la malloka variablo hashtable grandeco, kiu tuj dividi kiel nulo. Kaj ĝi tuj sekvigi kiel multaj vortoj estas en nia vortaro. 

Do ni rigardu ŝarĝo. Rimarku ke ŝarĝo, ĝi redonas bool. Vi revenu vera se gxi sukcese ŝarĝitaj, kaj falsaj alie. Kaj ĝi prenas const char * vortaron, kiu estas la vortaro ke ni volas malfermi. Do jen la unua afero ni tuj faros. 

Ni iras al fopen la vortaro por legado. Kaj ni tuj devas fari certas ke gxi sukcesis. Do, se ĝi revenis NULL, tiam ni ne sukcese malfermi la vortaron. Kaj ni bezonas reveni falsaj. Sed supozante, ke ŝi faris sukcese malfermita, tiam ni deziras legi la vortaro. Observu do looping ĝis ni trovos iun tial rompi el tiu ciklo, kiun ni vidos. Observu do looping. 

Kaj nun ni iras al malloc sola vertico. Kaj kompreneble ni bezonos eldiri kontrolu denove. Do se mallocing ne sukcesos, tiam ni volas malŝarĝi ajna nodo, ke ni okazis malloc antaŭ, fermi la vortaro kaj revenas falsaj. Sed ignorante ke, alprenanta ni sukcesis, do ni volas uzi fscanf legi unu vorton el nia vortaro en nia nodo. Do memoru, ke eniro> vorto estas la signo vorto bufro de grandeco LENGHTH +1 ke ni iras al butiko la vorto in 

Do fscanf tuj revenos 1, kiel longe kiel ĝi povis sukcese legu vorto de la dosiero. Se ĉu eraro okazas, aŭ ni atingi la finon de la dosiero, ĝi ne revenos 1. En kiu kazo ĝi ne revenos 1, ni fine tuj rompi tiu dum buklo. Do ni vidas, ke iam ni havos sukcese legu vorto en entry> vorton, tiam ni tuj, ke vorton uzante nian hash funkcio. 

Ni rigardu la krada funkcio. Do vi ne vere bezonas por kompreni tion. Kaj fakte ni nur tiris ĉi hash funkcio de la interreto. La sola afero, vi devas rekoni estas ke tio prenas const char * vorto. Do ĝi estas prenante ĉeno kiel enigo, kaj reveninte sensigna _int_ kiel eligo. Do tio estas ĉiuj la krada funkcio estas, ĉu preno en enigo kaj donas al vi indekso en la hashtable. 

Rimarku ke ni moding per NUM_BUCKETS, por ke valoro revenis efektive estas indico en la hashtable kaj ne indekso preter la limojn de la tabelo. Do pro tio ke la funkcio, ni iras al hash la vorto, kiun ni legis la vortaro. Kaj tiam ni tuj uzi ke hash por enmeti la eniro en la hashtable. 

Nun hashtable hash estas la nuna ligillisto en la tabelo. Kaj ĝi estas tre ebla ke ĝi estas nur NULL. Ni volas enmeti nian eniron en la komencante de tiu ligillisto. Kaj tial ni tuj havos niajn aktuala enirpunkto al kio la hashtable Nuntempe antaŭ to. Kaj poste ni iras al stoki, en la hashtable ĉe la Baldaux, la nuna ero. Do tiuj du linioj sukcese enigi la eniro en la komenco de la ligillisto en tiu indekso en la hashtable. 

Iam ni faris per tio ni scias kiun ni trovis alian vorton en la vortaro, kaj ni pliigo denove. Do ni observu la fari tion ĝis fscanf fine revenis io ne-1, je kiu punkto memoras ke ni bezonas por liberigi eniro. Do ĝis ĉi tie ni malloced eniro. Kaj ni provis legi iun el la vortaro. Kaj ni ne sukcese legas ion de la vortaro, en tiaokaze ni bezonas por liberigi la enskribo ke ni neniam vere meti en la hashtable, kaj fine rompi. 

Iam ni ekflamu ni bezonas vidi, bone, ni ekflamu pro tie Estis eraro legado de la dosiero? Aux cxu ni ekflamu pro ni atingis la finon de la dosiero? Se tie estis eraro, tiam ni volas redoni malvera. Ĉar ŝarĝo ne sukcesos. Kaj en la procezo ni volas malŝarĝi cxiujn vortojn, kiujn ni legas en, kaj fermi la vortaro dosiero. 

Supozante ni sukcesos, tiam ni ĵus ankoraŭ bezonas fermi la vortaro fajliloj, kaj fine revenas vera ekde ni sukcese alŝutis la vortaro. Kaj tio estas por ŝarĝo. Do nun kontroli, donita ŝarĝita hashtable, tuj aspekti kiel ĉi tio. Do kontrolu, ĝi redonas bool, kiu estas iri por indiki ĉu la pasinta en char * vorto, ĉu la pasinta en cxeno estas en nia vortaro. Do, se ĝi estas en la vortaro, se estas en nia hashtable, ni revenos vera. Kaj se tio ne estas, ni revenos falsaj. 

Donita ĉi pasis en vorto, ni estas tuj hash la vorto. Nun grava afero por agnoski estas ke en ŝarĝo ni sciis, ke ĉiuj el la vortojn ni tuj estu minuskloj. Sed ĉi tie ni ne estas tiel certa. Se ni rigardu nian hash funkcion, nia hash funkcio reale estas suba envolvaĵo ĉiu karaktero de la vorto. Do sendistinge de la majusklado de vorto, nia krada funkcio estas la reveno la sama indekso por kiaj la majusklado estas, kiel ĝi havus revenis por tute minuskle versio de la vorto. Alright. Tio estas nia indico estas en la hashtable por tiu vorto. 

Nun tion ĉi por buklo tuj persisti super la ligillisto kiu estis en tiu indekso. Do rimarki ni inicializar enskribo atentigi al tiu indekso. Ni tuj daŭrigi dum eniro! = NULL. Kaj memoru, ke la ĝisdatigo de la montrilo en nia ligillisto entry = entry> proksima. Do havi nian aktualan enirpunkto al la sekva listero en ligillisto. 

Do por ĉiu enskribo en la ligillisto, Ni tuj uzi strcasecmp. Ĝi ne estas strcomp. Ĉar refoje, ni volas fari aferojn kazo insensitively. Do ni uzu strcasecmp kompari la vorto, kiu estis aprobita per tiu funkcio kontraŭ la vorto kiu estas en ĉi tiu enskribo. Se li revenas nulon, tio signifas ne estis alumeto, en kiu okazo ni volas return true. Ni sukcese trovis la vorto en nia hashtable. 

Se tie ne estis batalo, tiam ni estas tuj buklo denove kaj rigardi la sekvanta eniro. Kaj ni vidos daŭrigi looping, dum ekzistas Estas enskriboj en tiu ligillisto. Kio okazas se ni rompu el tio por buklo? Tio signifas ke ni ne trovis eniron ke kongruis tiun vorton, en kiu kazo ni revenos malvera por indiki, ke nia hashtable ne enhavas tiun vorton. Kaj tio estas ĉekon. 

Do ni rigardu grandeco. Nun grandecon tuj estos sufiĉe simpla. Ekde memoras en ŝarĝo, ĉar ĉiu vorto ni trovis, ni incremented tutmonda variablo hashtable grandeco. Do la grandeco funkcio estas simple irante reveni malloka variablo. Kaj tio estas ĝi. 

Nun fine, ni devas malŝarĝi la vortaro unufoje ĉio estas farita. Do kiel ni faros tion? Ĝuste ĉi tie ni looping super ĉiuj siteloj de nia tablo. Do estas NUM_BUCKETS siteloj. Kaj por ĉiu ligillisto en nia hashtable, ni iras al buklo super La tuteco de la ligillisto, liberigante ĉiu elemento. 

Nun ni bezonas atenti. Do ĉi tie ni havas provizoran variablo tio estas stoki la montrilon al la sekva elemento en la ligillisto. Kaj poste ni iras al libera la nuna ero. Ni devas esti certa ke ni faru tion, kiam ni povas ne nur liberigi la aktualan elementon kaj tiam provi aliri la sekvanta montrilon, ĉar iam ni jam liberigitaj ĝi, La memoro iĝas malvalida. 

Do ni devas teni ĉirkaŭ montrilon al la sekva elemento, tiam ni povas liberigi la aktuala elemento, kaj tiam ni povos ĝisdatigi nia nuna ero atentigi al la sekva elemento. Ni buklo dum ekzistas elementoj en ĉi ligillisto. Ni faras tion por ĉiuj ligita lertaj en la hashtable. Kaj unufoje ni faris kun tio, ni tute malŝarĝis la hashtable, kaj ni faris. Do ĝi estas neebla por malŝarĝas por iam reveni falsaj. Kaj kiam ni faris, ni nur redoni vera. 

Ni donu tiun solvon provu. Do ni rigardu kion niaj struct nodo aspektos. Ĉi tie ni vidas ni tuj havos bool vorto kaj struct nodo * infanoj krampo alfabeto. Do la unua afero, vi povus esti scivolante, kial estas alfabeto ed difinita kiel la 27? Nu, memoru, ke ni tuj bezonas esti la uzado de la apostrofo. Do tiu tuj estos iom da speciala kazo laŭlonge de ĉi tiu programo. 

Nun memoru, kiamaniere oni trie efektive funkcias. Diru ni indeksante vorto "Katoj." Tiam el la radiko de trie, Ni tuj rigardi la infanoj tabelo, kaj ni iras por rigardi la indekso kiu respondas al la letero C. Por ke estos indeksita 2. Do pro tio ke, tiu volo donu al ni novan nodon. Kaj tiam ni devos labori el tiu nodo. 

Do pro tio ke nodo, ni estas denove iri por rigardi la infanojn tabelo. Kaj ni iras rigardi indekso nulo respondi al la A en katon. Tial do ni tuj iru al tiu nodo, kaj donita ke nodo ni iras rigardi la fino ĝi estas respondas al T. Kaj movanta al tiu nodo, fine, ni tute rigardis tra nia vorto "cat". Kaj nun bool vorto supozas indiki ĉu tiu vorto donita estas fakte unu vorto. 

Do kial ni bezonas ke speciala kazo? Nu, kion la vorto "katastrofo" Estas en nia vortaro, sed la vorto "kato", ne? Do rigardante vidi se la vorto "kato" Estas en nia vortaro, ni estas tuj sukcese trarigardi la indeksoj C-A-T en regiono nodo. Sed tio estas nur ĉar katastrofo okazis por krei nodojn sur la vojo de C-A-T, la tutan vojon al la fino de la vorto. Do bool vorto estas uzata por indiki ĉu tiu aparta situo fakte indikas vorton. 

Ĉiuj pravas. Do nun, kiam ni scias kio trie estas tuj aspekti, ni rigardu la ŝarĝi funkcio. Do ŝarĝo tuj resendas bool cxar se ni sukcese aŭ sensukcese ŝarĝis la vortaro. Kaj ĉi tiu tuj estos la vortaro ke ni volas ŝarĝi. 

Do unue ni devas fari estas malferma ĝis tiu vortaro por legado. Kaj ni devas certigi ni ne maltrafis. Do, se la vortaro ne estis sukcese malfermiĝis, ĝi revenos nula, en kiu kazo ni estas tuj revenos falsaj. Sed supozante, ke ŝi sukcese malfermita, tiam ni povas efektive legas tra la vortaro. 

Do unue ni tuj volas fari estas ni havas ĉi malloka variablo radiko. Nun radikon tuj estos nodo *. Ĝi estas la supera parto de nia trie, ke ni estas tuj estos ripetanta tra. Do la unua afero, kiun ni iras voli fari estas destini memoro por nia radiko. Rimarku ke ni uzas la calloc funkcio, kiu estas esence la sama kiel la malloc funkcion, escepte ĝi estas garantiita redoni iun kiu estas tute zeroed eksteren. Do, se ni uzas malloc, ni bezonus iri tra ĉiuj el la montriloj en nia nodo, kaj certigi ke ili estas ĉiu nula. Do calloc faros tion por ni. 

Nun nur kiel malloc, ni bezonas por fari certas, ke la atribuo estis efektive sukcesa. Se tiu revenis null, tiam ni bezonas fermi aŭ vortaro Arkivo kaj redoni malvera. Do supozante ke atribuo estis sukcesa, ni tuj uzi nodon * kursoro persisti per nia trie. Do niaj radikoj neniam tuj ŝanĝos, sed ni tuj uzi kursoron al efektive iros de nodo al nodo. 

Do en tiu buklo ni legas tra la vortaro dosiero. Kaj ni uzas fgetc. Fgetc tuj grab sola karaktero de la dosiero. Ni tuj daŭrigi grabbing karakteroj dum ni ne atingos la fino de la dosiero. 

Ekzistas du kazoj ni devas elteni. La unua, se la karaktero ne estis nova linio. Do ni scias se ĝi estis nova linio, tiam ni estas proksimume pluveturi al nova vorto. Sed supozante ke ne estis nova linio, tiam ĉi tie ni volas eltrovi la indekso ni tuj indekson en en la infanoj tabelo tiu ni rigardis antaŭe. 

Do, kiel mi diris antaŭe, ni bezonas speciala kazo la apostrofo. Rimarku ni uzas la triargumenta operatoro tie. Do ni tuj legas tion kiel, se la karaktero ni legas en Estis apostrofo, tiam ni tuj starigu indekso = "alfabeto" -1, kiu volas, esti la indekso 26. 

Alie, se ĝi ne estis apostrofo, tie ni tuj starigu la indekso egala al c - a. Do memoru revenis el la antaŭe p-aroj, c - oni tuj donu al ni la alfabeta pozicio de C. Do, se C estas la litero A, tiu volo donu al ni indekso nulo. Por la litero B, gxi donos ni la indekso 1, kaj tiel plu. 

Do tio donas al ni la indekson en la infanoj tabelo, ke ni volas. Nu, se tiu indekso estas aktuale nula en la infanoj, tio signifas ke nodo nuntempe ne ekzistas de tiu vojo. Tial oni devas destini nodo por tiu vojo. Tio estas kion ni faros ĉi tie. 

Do ni tuj denove uzi la calloc funkcio, por ke ni ne devas nulo al cxiuj el la montriloj. Kaj ni denove bezonas kontroli ke calloc ne maltrafis. Se calloc tute mankis, do ni bezonas malŝarĝi ĉio, fermu niajn vortaro, kaj revenas falsaj. Do supozante ke ĝi ne maltrafis, tiam tio kreos novan infanon por ni. Kaj tiam ni iros al tiu infano. Nia kursoro persisti malsupren al tiu infano. 

Nu, se tio ne estis nula komenci kun, tiam la kursoro povas simple persisti malsupren al tiu infano sen reale devi destini ion. Tiu estas la kazo, kie ni unue okazis atribui la vorto "kato". Kaj tio signifas, kiam ni iros al destini "Katastrofo", ni ne bezonas krei nodojn por C-A-T denove. Ili jam ekzistas. 

Kio estas ĉi tiu alia? Tio estas la kondiĉo, kie c estis backslash n, kie c estis nova linio. Tio signifas ke ni devas sukcese kompletigita vorto. Nun kion ni volas fari, kiam ni sukcese kompletigis vorto? Ni tuj uzas tiun vorton kampo ene de nia struct nodo. Ni volas fiksi, ke al vera. Do kiu indikas ke tiu nodo indikas sukcesan vorto, realan vorton. 

Direktu do nun, ke al vera. Ni volas reagordi nia kursoron al punkto al la komenco de la trie denove. Kaj fine, pliigo nia vortaro grandeco, ĉar ni trovis alian laboron. Do ni tuj daŭre fari tion, legante en karaktero de karaktero, konstrui novajn nodojn en nia trie kaj por ĉiu vorto en la vortaro, ĝis ni finfine atingos C! = EOF, en kiu kazo ni rompi la dosieron. 

Nun ekzistas du kazojn sub kion ni povus bati EOF. La unua estas, se tie estis eraro legado de la dosiero. Do, se tie estis eraro, ni bezonas fari la tipa. Malŝarĝi ĉio, proksime la dosieron, revenu falsaj. Supozante ke ne estis eraro, ke nur signifas, ke ni reale batis la finon de la dosieron, en kiu kazo, ni fermis la Arkivo kaj redoni vera ekde ni sukcese ŝarĝita vortaro en nian trie. 

Do nun ni kontrolu ĉekon. Rigardante la ĉekon funkcio, ni vidas ke ĉekon tuj resendas bool. Ĝi redonas vera se tiu vorto, ke ĝi estas aprobotaj estas en nia trie. Denove falsa alie. Do kiel vi determinas, cxu tiu vorto estas en nia trie? 

Oni vidas ĉi tie ke, samkiel antaŭ, Ni tuj uzi kursoro persisti tra nia trie. Nun tie oni iras al persisti super nia tuta vorto. Do ripetanta super la vorto ni estas pasinta, Ni tuj determinas la indekso en la infanoj tabelo tiu korespondas al vorto krampo I. Do tiu tuj serĉos ekzakte kiel ŝarĝo, kie se vorto [i] estas apostrofo, ĉar ni volas uzi indekson "alfabeto" - 1. Ĉar ni determinis, ke tiu Tie estas kie ni iras stoki apostrofoj. 

Alie, ni tuj uzi du malsupra vorto krampo I. Do memoru, ke vorto povas havas ajnaj majuskloj. Kaj tial ni volas certigi, ke ni estas uzante minusklajn versio de aferoj. Kaj tiam subtrahi el tiu 'a' al fojo denove doni al ni la alfabeta pozicio de tiu signo. Do tiu tuj estos nia indekso en la infanoj tabelo. 

Kaj nun, se tio indekson en la infanoj tabelo estas nula, tio signifas ke ni ne plu povas daŭrigi ripetanta malsupren niaj trie. Se tio estas la kazo, tiu vorto ne povas eble esti en nia trie. Ekde se gxi estis, kiuj volas signifas ne estus pado malsupren al tiu vorto. Kaj vi neniam renkontas nula. Do malhelpi nulaj, ni revenos falsaj. La vorto ne estas en la vortaro. Se ĝi ne estis nula, tiam ni estas tuj daŭrigi ripetanta. 

Do ni iras tie kursoro atentigi al tiu aparta nodo en tiu indekso. Ni daŭre fari ke la tuta la tutan vorton, supozante ni neniam batis nula. Tio signifas ke ni sukcesis trairi la tutan vorton kaj trovas nodo en nia provo. Sed ni ne tute farita ankoraŭ. 

Ni ne volas ĝuste redoni vera. Ni volas reveni kursoro> vorto. Ekde memoras denove, estas "kato" estas ne en nia vortaro, kaj "katastrofo" Estas, tiam ni estos sukcese ni preni tra la vorto "kato". Sed kursoro vorto estos falsa kaj ne vera. Do ni revenu kursoron vorto por indiki ĉu ĉi tiu nodo estas reale vorto. Kaj tio estas por ĉekon. 

Do ni kontrolu grandeco. Do grandecon tuj esti sufiĉe facila ĉar rememoru en ŝarĝo, ni estas pliigante vortaro grandeco por ĉiu vorto, kiun ni renkontas. Do grandeco estas ĝuste tuj revenu vortaro grandeco. Kaj tio estas ĝi. 

Do, laste ni malŝarĝi. Do malŝarĝi, ni tuj uzi rekursia funkcio por fakte plenumos cxiujn de la laboro por ni. Do nia funkcio tuj tuŝi unloader. Kio estas unloader faros? Oni vidas ĉi tie ke unloader tuj persisti super ĉiuj el la infanoj en tiu aparta nodo. Kaj se la infano nodo estas ne nula, poste ni iras al malŝarĝi la infano nodo. 

Do tiu estas vi rekursie malŝarĝi ĉiuj niaj infanoj. Iam ni estas certa, ke ĉiuj niaj infanoj estis malŝarĝitaj, ĉar ni povas liberigi nin, tiel malŝarĝi ni mem. Tio funkcios rekursie malŝarĝi la tutan trie. Kaj tiam tuj ke estas farita, ni povas simple reveni vera. Malŝarĝi ne povas malsukcesi. Ni nur liberigante aferojn. Do iam ni faris liberigante ĉio, revenu vera. Kaj tio estas ĝi. Mia nomo estas Rob. Kaj tio estis Speller. 

[MUZIKO Ludanta]