>> 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.
>> Mgomo nne.
Mimi nina nje.
Sorry.
Sorry kwa ajili ya kufanya mtu ambaye ina hariri hii kwenda mambo.
>> Sorry.
Sorry.
>> SPIKA 1: Vema.
Hiyo ilikuwa kweli vizuri.