>> Kevin Schmid: Minsan, kapag pagbuo ng isang programa, baka gusto mong ayusin ang isang
istraktura ng data na kilala bilang isang diksiyunaryo.
Ang isang diksyunaryo ng mga mapa susi, na mga karaniwang mga string, sa mga halaga, ints,
char, isang pointer sa ilang mga bagay, kahit anong gusto namin.
Ito ay tulad lamang ordinaryong mga diksyunaryo mga salita na mapa sa pamamagitan ng mga kahulugan.
>> Bigyan kami Diksyunaryo sa kakayahang mag-imbak ng impormasyon
na nauugnay sa isang bagay at tumingin ito up sa ibang pagkakataon.
Kaya paano ko talaga naming ipatupad ang diksyunaryo sa, sabihin nating, C code na aming makakaya
gamitin sa isa sa aming mga programa?
Well, may mga maraming paraan na maaari naming ipatupad ang isang diksiyunaryo.
>> Para sa isa, maaari kaming gumamit ng isang array na namin pabago-bago muling laki o maaari naming gamitin ang isang
naka-link na listahan, hash talahanayan o isang binary tree.
Ngunit namin ang kahit anong piliin, dapat namin maging maingat sa kahusayan at
pagganap ng pagpapatupad.
Dapat nating isipin ang tungkol sa algorithm na ginamit upang ipasok at maghanap ng mga item sa mga
ang aming istraktura ng data.
>> Para sa ngayon, ipagpalagay na namin sa nais na gumamit ng mga string bilang susi.
Usapan natin ang tungkol sa isa posibilidad Hayaan, isang istraktura ng data na tinatawag na isang trie.
Kaya narito ang isang visual na representasyon ng isang trie.
>> Tulad ng sa larawan nagmumungkahi, isang trie ay isang puno istraktura ng data sa
node na naka-link nang sama-sama.
Makita naming may malinaw na isang root node na may ilang mga link pagpapalawig sa
iba pang mga node.
Ngunit ano ang ibig Binubuo ang bawat node ng?
Kung ipinapalagay namin na kami ay nag-iimbak ng mga susi may lamang pang-abakada character, at
hindi namin pakialam tungkol sa paggamit ng malaking titik, narito ang isang kahulugan ng isang node na
ay magkasiya.
>> Ang isang bagay na kung saan ang uri ay struct na node ay may dalawang bahagi
tinatawag na data at mga bata.
Iniwan namin na ang mga bahagi ng data bilang isang komento upang mapalitan sa pamamagitan ng isang component
deklarasyon kapag struct node ay Pinagsama-sama sa isang program na C.
Ang bahagi ng isang node data ay maaaring maging isang Boolean halaga upang ipahiwatig kung ang o
hindi ang node ay kumakatawan sa pagkumpleto sa isang key diksyunaryo o maaari itong maging isang
na kumakatawan sa mga kahulugan string ng isang salita sa diksyunaryo.
>> Gagamitin namin ang isang SMILEY mukha upang ipahiwatig kapag data ay naroroon sa isang node.
May mga 26 mga elemento sa aming mga bata array, isa index
sa bawat pang-abakada character.
Susubukan naming makita ang kabuluhan ng ito sa lalong madaling panahon.
>> Hayaan ang makakuha ng mas malapitan naming tingnan ng root node sa aming diagram, na walang data
na nauugnay dito, bilang ipinahiwatig ng kawalan ng SMILEY mukha sa
bahagi ng data.
Ang mga arrow pagpapalawak ng mula sa mga bahagi ng ang mga anak ng array ay kumakatawan non-node
pointer sa iba pang mga node.
Halimbawa, ang arrow sa pagpapalawak ng mula sa ang pangalawang elemento ng mga bata
kumakatawan sa sulat B sa isang pangunahing diksyunaryo.
At sa mas malaking diagram lagyan ng label namin ito sa isang B.
>> Tandaan na sa mas malaking diagram, kung kailan namin gumuhit ng isang pointer sa isa pang node, ito
Hindi mahalaga kung saan ang unahan ng pana natutugunan na ang ibang node.
Ang aming trie sample diksyunaryo ay naglalaman ng dalawang salita, iyon at pag-zoom.
Ni maglakad sa pamamagitan ng isang halimbawa ng Hayaan hinahanap ang data para sa isang key.
>> Ipagpalagay na gusto naming tumingin hanggang ang kaukulang halaga para sa key bath.
Sisimulan namin ang aming hitsura up sa root node.
Pagkatapos ay isasaalang-alang namin ang unang titik ng aming key, B, at hanapin ang mga kaukulang
makita sa ating mga anak ng array.
Pansinin na mayroong eksaktong 26 spot sa array, isa para sa bawat titik ng
ang alpabeto.
At kakailanganin naming ay kumakatawan sa mga spot ang titik ng alpabeto sa order.
>> Susubukan naming tumingin sa ikalawang index pagkatapos, index ng isa, para sa B. Sa pangkalahatan, kung namin
kumuha ng pang-abakada ng character C namin maaaring matukoy ang nararapat na lugar
sa mga bata array gamit isang kalkulasyon tulad nito.
Maaaring namin ang ginamit ng mas malaking mga bata array kung gusto naming mag-alok hitsura up ng
mga susi sa isang mas malawak na hanay ng mga character, gaya ng buong
Itakda ang mga ASCII na character.
>> Sa kasong ito, ang pointer sa ating mga anak array sa
index isa ay hindi null.
Kaya ipagpapatuloy namin ang pagtingin up ang key bath.
Kung sakaling aming nakatagpo ng isang null pointer sa tamang lugar sa mga bata
array habang kami traversed ang nodes, pagkatapos ay kakailanganin naming sabihin na tayo
Hindi mahanap ang anumang bagay para sa na key.
>> Ngayon, isasaalang-alang namin ang pangalawang titik ng ang aming key, A, at magpatuloy sumusunod
mga payo sa paraang ito hanggang namin maabot ang dulo ng aming key.
Kung naabot namin ang dulo ng key nang walang pagpindot ng anumang patay na magwakas, null pointer,
tulad ng kaso dito, pagkatapos namin lamang mayroon upang suriin ang isa pang bagay.
Ay ang key na ito talaga sa diksyunaryo?
>> Kung gayon, dapat naming mahanap ang isang halaga, na rin ng isang icon SMILEY mukha sa aming mga diagram kung saan
Nagtatapos ang salita.
Kung mayroong isang bagay pa ang naka-imbak sa ang data, pagkatapos ay maaari naming ibalik ito.
Halimbawa, ang key zoo ay wala sa diksyonaryo, kahit na maaari kaming magkaroon
Naabot ang dulo ng ang key na ito nang hindi kailanman pagpindot ng isang null pointer, habang kami
umulit sa pamamagitan ng trie.
>> Kung sinubukan naming upang tumingin up ang key bath, ang pangalawang sa array index ng huling node ni,
naaayon sa titik H, magiging na gaganapin isang null pointer.
Kaya bath ay wala sa diksyonaryo.
At kaya isang trie ay natatangi sa na ang mga key ay hindi kailanman tahasang naka-imbak sa
ang istraktura ng data.
Kaya paano ko isingit kami ng isang bagay sa isang trie?
>> Magpasok ng key Hayaan zoo sa aming trie.
Alalahanin na ang isang SMILEY mukha sa isang node maaaring Tumutugon sa code sa isang simpleng
Boolean halaga upang isaad na zoo ay nasa diksyunaryo o ng dati
ay tumutugma sa higit pang impormasyon na aming nais i-uugnay sa mga key zoo,
tulad ng mga kahulugan ng mga salita o iba pang dahilan.
Sa ilang mga paraan, ang proseso upang ipasok isang bagay sa isang trie ay katulad ng
hinahanap ang isang bagay sa isang trie.
>> Sisimulan naming muli gamit ang root node, sumusunod na pointer naaayon sa
ang mga titik sa aming mga key.
Sa kabutihang-palad, hindi namin magagawang sundan pointer ang lahat ng paraan hanggang naabot namin
sa dulo ng key.
Dahil zoo ay isang unlapi ng salitang zoom, na kung saan ay isang miyembro ng
diksyonaryo, hindi namin kailangan upang magtalaga ng anumang bagong mga node.
>> Maaari naming baguhin ang node upang isaad na ang landas ng mga character na humahantong sa
ito ay kumakatawan sa isang susi sa aming diksiyunaryo.
Ngayon, Subukan nating pagpasok hayaan ang key bath sa trie.
Sisimulan naming sa root node at sundin ang mga payo muli.
Ngunit sa sitwasyong ito, pindutin namin ang isang patay tapusin bago namin magawang upang makakuha ng sa
dulo ng key.
Ngayon, kailangan namin upang maglaan ng ilang bagong node na kailangang maglaan ng isang bagong
na node para sa bawat natitirang sulat ng aming key.
>> Sa kasong ito, kailangan namin lamang upang magtalaga ng isang bagong node.
Pagkatapos ay kakailanganin naming gawin ang index H isangguni ang bagong node.
Muli, maaari naming baguhin ang node sa magpahiwatig na ang landas ng mga character
na humahantong sa ito ay kumakatawan sa isang susi sa aming diksiyunaryo.
Ni Dahilan tungkol sa asymptotic Hayaan kasalimuotan ng aming mga pamamaraan para sa mga
dalawang mga operasyon.
>> Napansin namin na sa parehong mga sitwasyon ang bilang ng steps aming algorithm kinuha ay
proporsyonal sa bilang ng mga mga titik sa keyword.
Tama iyon.
Kapag nais mong maghanap ng isang salita sa isang trie kailangan mo lamang upang umulit sa pamamagitan ng
ang mga titik ng isa sa pamamagitan ng isa hanggang mong alinman sa maabot ang dulo ng salita o
hit ang isang patay na dulo sa trie.
>> At kapag nais mo upang magpasok ng isang key halaga ng pareho sa isang trie gamit ang
pamamaraan namin tinalakay, ang pinakamasama kaso Magkakaroon ka paglaan ng isang bagong node
para sa bawat titik.
At makikita naming ipagpalagay na laang-gugulin ay patuloy na operasyon ng panahon.
Kaya kung ipinapalagay namin na ang mga key na haba ay bounded sa pamamagitan ng isang nakapirming pare-pareho, parehong
pagpapasok at tumingin up ay pare-pareho mga pagpapatakbo ng oras para sa isang trie.
>> Kung hindi kami gumawa ito palagay na ang haba ng pindutan ay bounded sa pamamagitan ng isang nakapirming
pare-pareho, pagkatapos ay pagpapasok at tumingin up, sa pinakamasama kaso, ay linear sa
haba ng key.
Pansinin na ang bilang ng mga item na naka-imbak sa trie ay hindi nakakaapekto sa hitsura up
o oras pagpapasok.
Ito ay naapektuhan lamang ng haba ng key.
>> Sa pamamagitan ng kaibahan, ang pagdaragdag ng mga entry sa, sabihin nating, isang hash talahanayan ay may gawi na gumawa
hinaharap maghanap ng mas mabagal.
Habang ito ay maaaring tunog akit sa una, dapat naming panatilihin sa isip na ang isang
kanais-nais na asymptotic pagiging kumplikado ay hindi ibig sabihin na sa pagsasanay ang data
istraktura ay kinakailangang lampas pagsisi.
Dapat din namin isaalang-alang na mag-imbak ng isang salita sa isang trie kailangan namin, sa pinakamalala
kaso, ang isang bilang ng mga node proporsyonal sa haba ng salita mismo.
>> Pagsusubok na may posibilidad na gumamit ng maraming espasyo.
Iyon ay sa kabilang banda sa isang hash talahanayan, kung saan kailangan lamang namin ang isa bagong node sa
mag-imbak ng ilang mga pangunahing pares halaga.
Ngayon, muli sa teorya, malaking puwang pagkonsumo ay hindi tila tulad ng isang malaking
harapin, lalo na ibinigay na modernong mga computer mayroon gigabytes at
gigabytes ng memorya.
Ngunit ito ay lumiliko out na mayroon pa rin namin upang mag-alala tungkol sa paggamit ng memory at
samahan alang-alang sa pagganap, dahil ang mga modernong mga computer
mayroon mekanismo sa lugar sa ilalim ng hood upang mapabilis ang memory access.
>> Ngunit ang mga mekanismo ang pinakamahusay na gumagana kapag uma-access ng memory ay gawa sa compact
rehiyon o lugar.
At ang mga node ng isang trie maaaring manirahan kahit saan sa na magbunton.
Ngunit ang mga ito ay mga trade-off na kailangan naming isaalang-alang.
>> Tandaan na, kapag pumipili ng data istraktura para sa isang tiyak na gawain, kami
dapat isipin ang tungkol sa kung anong mga uri ng pagpapatakbo kailangan ng istraktura ng data sa
suporta at kung magkano ang pagganap ng bawat isa sa mga
mga usapin pagpapatakbo sa amin.
Ang mga pagpapatakbo ay maaaring kahit na mapalawak nang higit lamang
pangunahing hitsura up at pagpapasok.
Ipagpalagay na gusto naming ipatupad ang uri ng auto-complete-andar, magkano
tulad ng Google search engine na gumagana.
Iyon ay, bumalik ang lahat ng mga pindutan at mga potensyal na mga halaga na
magkaroon ng isang naibigay na prefix.
>> Ang isang trie ay katangi-tangi kapaki-pakinabang para sa operasyong ito.
Ito ay tuwiran upang umulit sa pamamagitan ng ang trie para sa bawat katangian ng
ang prefix.
Tulad ng isang tumingin hanggang operasyon, maaari naming sundin ang mga payo
ng character ng character.
Pagkatapos, kapag dumating kami sa dulo ng prefix, maaari kaming umulit sa pamamagitan ng
natitirang bahagi ng istraktura ng data dahil alinman sa ang mga key na lampas
puntong ito ay may prefix.
>> Ito ay madali ring upang makuha ang listahan na ito sa alpabetong pagkakasunud-sunod mula noong
mga elemento ng mga bata array ay nakaayos ayon sa alpabeto.
Kaya sana ay makikita mo isaalang-alang pagbibigay sinusubukan ng isang try.
Ako Kevin Schmid, at ito ay CS50.
>> Ah, ito ang simula ng pagtanggi.
Sorry.
>> Strike apat.
Ako out.
Sorry.
Paumanhin para sa paggawa ng mga taong nag- May upang i-edit ito mabaliw.
>> Sorry.
Sorry.
>> Tagapagsalita 1: Magaling.
Iyon ay talagang magaling.