KEVIN SCHMID: Wakati mwingine, wakati kujenga mpango, unaweza kutaka kutumia muundo data inayojulikana kama dictionary. ramani kamusi funguo, ambayo ni kawaida masharti, kwa maadili, ints, chars, pointer kwa baadhi kitu, chochote tunataka. Ni kama tu kamusi kawaida maneno ramani kwamba kwa ufafanuzi. 

Dictionaries kutupatia uwezo wa kuhifadhi habari kuhusishwa na kitu na kuangalia ni juu baadaye. Hivyo ni jinsi gani sisi kweli kutekeleza kamusi katika, kusema, C kificho kwamba tunaweza kutumia katika moja ya mipango yetu? Naam, kuna mengi ya njia ambazo tunaweza kutekeleza dictionary. 

Kwa moja, tunaweza kutumia safu kwamba sisi dynamically re ya kawaida au tunaweza kutumia orodha wanaohusishwa, hash meza au mti binary. Lakini chochote sisi kuchagua, sisi lazima kukumbuka ya ufanisi na utendaji wa utekelezaji. Tunapaswa kufikiri juu ya algorithm kutumika kuingiza na kuangalia vitu ndani ya data muundo wetu. 

Kwa sasa, hebu kudhani kwamba sisi wanataka kutumia masharti kama funguo. Hebu majadiliano juu ya uwezekano moja, muundo data aitwaye trie. Hivyo hapa ni Visual uwakilishi ya trie. 

Kama picha unaonyesha, trie ni data muundo mti na nodes wanaohusishwa pamoja. Tunaona kwamba kuna wazi mzizi node na baadhi ya viungo kupanua nodes nyingine. Lakini ni nini kila nodi na wajumbe? Kama tukidhani kuwa sisi ni hifadhi funguo na wahusika kialfabeti tu, na sisi hawajali mtaji, hapa ni ufafanuzi wa nodi kwamba itakuwa inatosha. 

kitu ambaye ni aina struct node ina sehemu mbili aitwaye data na watoto. Tumekuwa kushoto data sehemu kama maoni kubadilishwa na sehemu tamko wakati struct node ni kuingizwa katika C mpango. data sehemu ya node inaweza kuwa Thamani Boolean kuonyesha kama si node inawakilisha kukamilika ya kamusi muhimu au inaweza kuwa kamba anayewakilisha ufafanuzi ya neno katika kamusi. 

Tutaweza kutumia smiley uso zinaonyesha wakati data ni sasa katika node. Kuna mambo 26 katika yetu watoto safu, moja index kwa kialfabeti tabia. Tutaweza kuona umuhimu hii hivi karibuni. 

Hebu kupata kuangalia kwa karibu mizizi node katika mchoro yetu, ambayo haina data yanayohusiana na hayo, kama unahitajika kwa kukosekana kwa uso smiley katika data sehemu. mishale kupanua kutoka sehemu ya watoto safu ya kuwakilisha mashirika yasiyo ya node kuyatumia kwa nodes nyingine. Kwa mfano, arrow kupanua kutoka hiki pili ya watoto inawakilisha barua B katika muhimu dictionary. Na katika mchoro kubwa sisi studio ni pamoja na B. 

Kumbuka kuwa katika mchoro kubwa, wakati sisi kuteka pointer kwa node mwingine, Haijalishi ambapo kigumba hukutana kwamba node nyingine. Sampuli kamusi yetu trie ina maneno mawili, kuwa na zoom. Hebu kutembea kwa njia ya mfano wa kuangalia juu data kwa ajili ya muhimu. 

Tuseme sisi alitaka kuangalia up sambamba thamani kwa ajili ya umwagaji muhimu. Tutaweza kuanza kuangalia yetu up mizizi nodi. Kisha tutaweza kuchukua barua ya kwanza ya yetu muhimu, B, na kupata sambamba doa katika watoto wetu safu. Taarifa kuwa kuna hasa 26 matangazo katika safu, moja kwa kila herufi ya alfabeti. Na sisi itabidi matangazo ya kuwakilisha wa alfabeti katika utaratibu. 

Tutaangalia index pili basi, index moja, kwa B. Kwa ujumla, kama sisi na baadhi kialfabeti tabia C sisi inaweza kuamua doa sambamba kwa watoto safu kutumia hesabu kama hii. Tunaweza wametumia watoto kubwa safu kama sisi alitaka kutoa kuangalia juu ya funguo na pana mbalimbali ya wahusika, kama vile nzima Tabia ya ASCII kuweka. 

Katika kesi hiyo, pointer kwa watoto safu yetu index moja ni si null. Hivyo tutaweza kuendelea kuangalia up umwagaji muhimu. Kama sisi milele yaliyojitokeza null pointer katika doa sahihi kwa watoto safu wakati sisi yamepitia nodes, basi tutaweza kusema kwamba sisi hakuweza kupata chochote kwa kuwa muhimu. 

Sasa, tutaweza kuchukua barua ya pili ya muhimu yetu, A, na kuendelea zifuatazo kuyatumia kwa njia hii mpaka sisi kufikia mwisho wa muhimu yetu. Kama sisi kufikia mwisho wa muhimu bila kupiga ncha waliokufa, null kuyatumia, kama ilivyo hapa, basi sisi tu kuwa na kuangalia jambo moja zaidi. Ni muhimu hii kwa kweli katika kamusi? 

Kama ni hivyo, tunapaswa kupata thamani, pamoja na a smiley uso icon katika mchoro yetu ambapo neno mwisho. Kama kuna kitu kingine kuhifadhiwa na data, basi tunaweza kurudi. Kwa mfano, zoo ni muhimu si katika kamusi, ingawa tunaweza kuwa na kufikiwa mwisho wa hii muhimu bila hata kupiga null pointer, wakati sisi iterate kupitia trie. 

Kama sisi alijaribu kuangalia juu umwagaji muhimu, pili kwa mwisho node ya safu index, sambamba na barua H, bila uliofanyika null pointer. Hivyo umwagaji ni si katika kamusi. Na hivyo trie ni ya kipekee kwa kuwa funguo kamwe wazi kuhifadhiwa katika data muundo. Hivyo ni jinsi gani sisi kuingiza kitu ndani ya trie? 

Hebu kuingiza muhimu zoo katika trie yetu. Kumbuka kwamba uso smiley katika node inaweza yanahusiana katika kanuni kwa rahisi Thamani Boolean zinaonyesha zoo kwamba ni katika kamusi au inaweza yanahusiana na habari zaidi kwamba sisi unataka kujiunga na zoo muhimu, kama ufafanuzi wa neno au kitu kingine. Katika baadhi ya njia, mchakato wa kuingiza kitu katika trie ni sawa na kuangalia juu kitu katika trie. 

Tutaweza kuanza na mzizi node tena, kuyatumia zifuatazo sambamba na barua ya yetu muhimu. Kwa bahati nzuri, tulikuwa na uwezo wa kufuata kuyatumia njia yote hadi tulipofika mwisho wa muhimu. Tangu zoo ni kiambishi awali ya neno zoom, ambayo ni mwanachama wa kamusi, hatuna haja ya kutenga nodes yoyote mpya. 

Tunaweza kurekebisha node zinaonyesha kwamba njia ya wahusika na kusababisha inawakilisha muhimu katika kamusi yetu. Sasa, hebu jaribu kuingiza BATH muhimu katika trie. Tutaweza kuanza mizizi node na kufuata kuyatumia tena. Lakini katika hali hii, sisi kugonga wafu mwisho kabla ya sisi ni uwezo wa kupata mwisho wa muhimu. Sasa, sisi itabidi kutenga baadhi ya mwezi nodes unahitaji kutenga mwezi mmoja node kwa kila iliyobaki barua ya yetu muhimu. 

Katika kesi hiyo, sisi tu haja ya kutenga moja node mpya. Kisha tutaweza haja ya kufanya H index kumbukumbu node hii mpya. Mara nyingine tena, tunaweza kurekebisha node kwa zinaonyesha kwamba njia ya wahusika kuongoza kwa inawakilisha muhimu katika kamusi yetu. Hebu sababu kuhusu asymptotic utata wa taratibu zetu kwa ajili ya haya shughuli mbili. 

Tunaona kwamba katika hali zote mbili idadi ya hatua algorithm wetu alichukua ilikuwa sawia na idadi ya barua katika keyword. Hiyo ni haki. Wakati unataka kuangalia juu ya neno katika trie wewe tu haja ya iterate kupitia barua moja kwa moja ama mpaka kufikia mwisho wa neno au hit maiti ya mwisho katika trie. 

Na wakati unataka kuingiza muhimu jozi thamani katika trie kutumia utaratibu sisi kujadiliwa, kesi mbaya itakuwa na wewe kugawa nodi mpya kwa kila herufi. Na tutaweza kudhani mgao kwamba ni mara kwa mara wakati wa operesheni. Hivyo kama sisi kudhani kwamba urefu ni muhimu imepakana na fasta mara kwa mara, wote kuingizwa na kuangalia juu ni mara kwa mara shughuli wakati kwa trie. 

Kama hatuwezi kufanya dhana hii kwamba urefu muhimu imepakana na fasta mara kwa mara, kisha kuingizwa na kuangalia juu, katika hali mbaya zaidi, ni linear katika urefu wa muhimu. Taarifa kwamba idadi ya vitu kuhifadhiwa katika trie haiathiri kuangalia up au kuingizwa wakati. Ni tu wanashikiliwa na urefu wa muhimu. 

Kwa upande mwingine, na kuongeza entries, kusema, meza hash huelekea kufanya baadaye kuangalia juu polepole. Wakati hii inaweza kuonekana rufaa kwa mara ya kwanza, tunapaswa kukumbuka kwamba asymptotic nzuri utata haina maana kwamba katika mazoezi data muundo ni lazima zaidi ya aibu. Sisi lazima pia kuzingatia kwamba kuhifadhi neno katika trie, tunahitaji katika hali mbaya zaidi kesi, idadi ya nodes sawia na urefu wa neno lenyewe. 

Inajaribu huwa na matumizi mengi ya nafasi. Hiyo ni tofauti na meza hash, ambapo sisi tu haja moja node mpya kuhifadhi baadhi ya jozi ufunguo thamani. Sasa, tena katika nadharia, nafasi kubwa matumizi ya haionekani kama kubwa mpango huo, hasa kutokana na kuwa ya kisasa kompyuta na gigabytes na gigabytes ya kumbukumbu. Lakini zinageuka kuwa bado tuna na wasiwasi juu ya matumizi ya kumbukumbu na shirika kwa ajili ya utendaji, tangu kompyuta za kisasa na taratibu zilizopo chini ya kofia ili kuharakisha upatikanaji wa kumbukumbu. 

Lakini njia hizi kazi bora wakati wanapata kumbukumbu ni kufanywa katika Compact mikoa au maeneo. Na nodes ya trie inaweza kuishi mahali popote katika chungu. Lakini hizi ni biashara awamu ya pili kwamba ni lazima kuzingatia. 

Kumbuka kwamba, wakati wa kuchagua data utaratibu kwa ajili ya kazi fulani, sisi wanapaswa kufikiri juu ya ni aina gani ya shughuli muundo data mahitaji ya msaada na kiasi gani utendaji ya kila moja ya hizo mambo shughuli kwetu. Shughuli hizo huenda hata kupanua zaidi tu msingi kuangalia up na kuingizwa. Tuseme sisi alitaka kutekeleza aina ya auto-kamili utendaji, kiasi kama Google search engine gani. Yaani, kurudi funguo zote na uwezekano wa maadili ambayo na kiambishi awali huo. 

trie ni ya kipekee muhimu kwa operesheni hii. Ni moja kwa moja kwa iterate kupitia trie kwa kila tabia ya kiambishi awali. Tu kama kuangalia juu ya kazi, tunaweza kufuata kuyatumia tabia kwa tabia. Basi, wakati sisi kuwasili mwishoni mwa kiambishi awali, tunaweza iterate kupitia sehemu iliyobaki ya muundo data tangu yoyote ya funguo ya zaidi ya hatua hii na kiambishi awali. 

Ni pia rahisi kupata orodha hii katika herufi tangu mambo ya watoto safu ni amri alphabetically. Hivyo hopefully itabidi kuzingatia kutoa anajaribu kujaribu. Mimi nina Kevin Schmid, na hii ni CS50. 

Ah, huu ni mwanzo ya kushuka. Mimi nina sorry. Sorry. Sorry. Sorry. 

Mgomo nne. Mimi nina nje. Sorry. Sorry. Sorry. Sorry kwa ajili ya kufanya mtu ambaye ina hariri hii kwenda mambo. 

Sorry. Sorry. Sorry. Sorry. 

SPIKA 1: Vema. Hiyo ilikuwa kweli vizuri.