KEVIN Schmid: Pafwa, lè bati yon pwogram nan, ou ta ka vle itilize yon estrikti done li te ye kòm yon diksyonè. Yon kat diksyonè kle yo, ki se anjeneral strings, nan valè, antye, charaktèr, yon konsèy nan kèk objè, tou sa nou vle. Li nan jis tankou diksyonè òdinè kat jeyografik ke mo nan definisyon. 

Dictionaries bay nou ak nan kapasite nan magazen enfòmasyon ki asosye avèk yon bagay epi gade l 'pita. Se konsa, kouman nou aktyèlman aplike yon diksyonè nan, di, C kòd ki nou kapab sèvi ak nan youn nan pwogram nou an? Oke, gen yon anpil nan fason ki nou te ka aplike yon diksyonè. 

Pou youn, nou te ka sèvi ak yon etalaj ke nou dynamique re-gwosè oswa nou te ka sèvi ak yon lis lye, tab hash oswa yon pye bwa binè. Men, tou sa nou chwazi, nou ta dwe dwe konsyan de efikasite yo ak pèfòmans nan aplikasyon an. Nou ta dwe reflechi sou algorithm a te itilize insert epi gade anwo atik nan done nou an estrikti. 

Pou kounye a, se pou yo asime ke nou vle sèvi ak strings kòm kle. Se pou nou pale sou yon sèl posiblite, yon estrikti done yo te rele yon trye. Se konsa, isit la nan yon reprezantasyon vizyèl nan yon trye. 

Kòm foto an sijere, yon trye se yon pye bwa done estrikti ak nœuds lye ansanm. Nou wè ke gen nan byen klè yon rasin ne ak kèk lyen yo pwolonje lòt ne. Men, sa ki chak ne konpoze de? Si nou asime ke nou ap estoke kle ak sèlman karaktè alfabetik, ak nou pa pran swen sou lèt majiskil, isit la nan yon definisyon yon ne ki ap sifi. 

Yon objè ki gen kalite a se konstri ne gen de pati rele done ak timoun yo. Nou te kite pati nan done kòm yon kòmantè yo dwe ranplase pa yon eleman deklarasyon lè konstri ne se enkòpore nan yon pwogram C. Pati nan done nan yon ne ta kapab yon Boolean valè nan endike si wi ou pa ne a reprezante fini an nan yon kle diksyonè oswa li ta kapab yon fisèl reprezante definisyon an nan yon mo an nan diksyonè a. 

Nou pral sèvi ak yon figi Smiley ki endike lè done ki prezan nan yon ne. Gen 26 eleman nan nou an timoun etalaj, youn endèks pou chak karaktè alfabetik. Nou pwal wè siyifikasyon an nan sa a byento. 

Se pou nou jwenn yon gade pi pre nan ne la rasin nan dyagram nou an, ki pa gen okenn done ki asosye avèk li, jan sa endike nan la absans nan fè fas a Smiley nan la done pòsyon. Flèch yo pwolonje soti nan pati pyès sa yo nan timoun yo etalaj reprezante ki pa ne endikasyon nan lòt ne. Pou egzanp, flèch la pwolonje soti nan eleman nan dezyèm nan timoun reprezante lèt la B nan yon kle diksyonè. Apre sa, nan dyagram nan pi gwo nou mete lejann sou li ak yon B. 

Remake byen ke nan dyagram nan pi gwo, lè nou trase yon konsèy nan yon lòt ne, li pa gen pwoblèm ki kote Arrowhead la satisfè ke lòt ne. Diksyonè echantiyon trye nou an gen de mo, se sa ak rale. Se pou nou mache nan yon egzanp sou leve je l 'done pou yon kle. 

Sipoze nou te vle gade nan ki koresponn valè pou benyen nan kle. Nou pral kòmanse gade nou moute nan ne an rasin. Lè sa a, nou pral pran premye lèt nan nou an kle, B, epi jwenn ki koresponn a tach nan timoun nou yo etalaj. Avi ki di ke gen yo se egzakteman 26 tach nan etalaj la, yonn pou chak lèt alfabè an. Epitou, n ap gen tach yo reprezante nan lèt nan alfabè a nan lòd. 

Nou pral gade nan dezyèm endèks la lè sa a, endèks, yonn pou B. An jeneral, si nou gen kèk alfabetik karaktè C nou te kapab detèmine plas ki koresponn lan nan timoun etalaj la lè l sèvi avèk yon kalkil tankou sa a. Nou te kapab te itilize yon pi gwo timoun etalaj si nou te vle ofri gade leve nan kle ak yon seri pi laj de karaktè yo, tankou tout la N. ASCII mete. 

Nan ka sa a, konsèy la nan timoun nou yo etalaj nan endèks se yon sèl pa nil. Se konsa, nou pral kontinye kap moute benyen nan kle. Si nou tout tan tout tan rankontre yon konsèy nil nan plas ki kòrèk nan timoun yo etalaj pandan ke nou travèse nœuds yo, Lè sa a, nou pral oblije di ke nou pa t 'kapab jwenn anyen pou sa kle. 

Koulye a, nou ap pran lèt nan dezyèm nan kle nou an, A a, epi kontinye sa yo endikasyon nan fason sa a jiskaske nou rive nan fen an nan kle nou yo. Si nou rive nan fen an nan kle a san yo pa , frape nenpòt ki fini mouri endikasyon nil, kòm se ka a isit la, Lè sa a, nou sèlman gen yo tcheke yon sèl bagay plis ankò. Se kle sa a aktyèlman an nan diksyonè a? 

Si se konsa, nou ta dwe jwenn yon valè, byen yon Smiley icon figi nan dyagram nou an kote pawòl Bondye a fini. Si gen yon lòt bagay ki estoke ak done yo, Lè sa a, nou ka retounen li. Pou egzanp, zou a kle se pa nan la diksyonè, menm si nou te ka gen rive jwenn nan fen kle sa a san yo pa janm frape nan yon konsèy nil, pandan ke nou repňte nan trye la. 

Si nou te eseye gade benyen nan kle yo, nan dezyèm endèks etalaj dènye ne a, ki koresponn ak lèt ​​H la, ta yo te ki te fèt yon konsèy nil. Se konsa, benyen se pa an nan diksyonè a. Se konsa, yon trye se inik nan ki kle yo pa janm gen klèman ki estoke nan estrikti a done. Se konsa, ki jan nou insert yon bagay nan yon trye? 

Se pou yo insert kle a zou nan trye nou an. Sonje ke yon figi Smiley nan yon ne te kapab koresponn nan kòd nan yon senp Boolean valè nan endike ke zou se an nan diksyonè a oswa li te kapab koresponn ak plis enfòmasyon ke nou vle asosye ak zou a kle yo, tankou definisyon an nan la mo oswa yon lòt bagay. Nan kèk fason, pwosesis la insert yon bagay nan yon trye se menm jan ak leve je yon bagay nan yon trye. 

Nou pral kòmanse ak ne nan rasin ankò, endikasyon yo ki koresponn a lèt yo nan kle nou yo. Chans, nou te kapab swiv endikasyon tout wout la jouk nou rive nan fen kle a. Depi zou se yon prefiks nan pawòl Bondye a rale, ki se yon manm nan la diksyonè, nou pa bezwen asiyen nenpòt nouvo ne. 

Nou ka modifye ne a endike ke chemen an nan karaktè ki mennen ale nan li reprezante yon kle nan diksyonè nou an. Koulye a, se pou yo eseye yo mete nan BATH kle nan trye la. Nou pral kòmanse nan ne la rasin epi swiv endikasyon ankò. Men, nan sitiyasyon sa a, nou frape yon moun mouri fini anvan nou ap kapab pou li ale nan nan nan fen kle a. Koulye a, nou pral bezwen asiyen kèk nouvo nœuds ap bezwen asiyen yon nouvo ne pou chak rete lèt de kle nou yo. 

Nan ka sa a, nou jis bezwen asiyen yon nouvo ne. Lè sa a, nou pral bezwen fè endèks la H referans nouvo ne sa a. Yon fwa ankò, nou ka modifye ne a endike ke chemen an nan karaktè ki mennen ale nan li reprezante yon kle nan diksyonè nou an. Se pou yo rezone sou asenptotik la konpleksite nan pwosedi nou an pou sa yo de operasyon yo. 

Nou remake ke nan tou de ka nimewo a nan etap algorithm nou an te pran te pwopòsyonèl ak kantite lèt nan mo kle a. Sa a dwat. Lè ou vle gade yon mo nan yon trye ou jis bezwen repňte nan lèt yo youn pa youn jiskaske ou swa rive nan fen an gen mo a oubyen frape yon fen mouri nan trye la. 

Men, lè ou vle mete yon kle valè pè nan yon trye lè l sèvi avèk la pwosedi nou diskite, ka ki pi mal pral gen ou allocation yon nouvo ne pou chak lèt. Epitou, n ap sipoze alokasyon ki se yon operasyon tan konstan. Se konsa, si nou sipoze ke longè a kle a se limite pa yon konstan fiks, tou de ensèsyon epi gade anwo yo konstan operasyon tan pou yon trye. 

Si nou pa fè sipozisyon sa a ki se longè a kle limite pa yon fiks konstan, Lè sa a, ensèsyon ak gade leve, nan ka ki pi mal la, yo lineyè nan la longè kle a. Remake ki kantite atik ki estoke nan trye la pa afekte gade nan moute oswa tan ensèsyon. Li sèlman ntre nan pa la longè kle a. 

Nan kontras, pandan l ajoute antre a, di, yon tab hash gen tandans fè tan kap vini gade pi dousman. Pandan ke sa a pouvwa son fè apèl kont an premye, nou ta dwe kenbe nan tèt ou ke yon favorab konpleksite asenptotik fè sa ki pa vle di ke nan pratik done a estrikti a se nesesèman pi lwen pase wont. Nou dwe konsidere ke tou nan magazen yon mo nan yon trye nou bezwen, nan pi move a ka, yon nimewo nan nœuds pwopòsyonèl longè a nan pawòl Bondye a tèt li. 

Ap eseye yo gen tandans sèvi ak yon anpil nan espas. Sa a nan kontra a yon tab hash, kote nou sèlman bezwen yon nouvo ne magazen kèk valè kle pè. Koulye a, ankò nan teyori, gwo espas konsomasyon pa sanble tankou yon gwo fè fas, espesyalman bay yo ke modèn òdinatè gen jigokte ak jigokte nan memwa. Men, li sanble ke nou toujou gen enkyete sou itilizasyon memwa ak òganizasyon pou dedomajman pou la pèfòmans, depi òdinatè modèn yo gen mekanis nan plas anba a kapo pi vit aksè memwa. 

Men, mekanis sa yo travay pi byen lè aksèd memwa yo te fè nan kontra enfòmèl ant rejyon oswa zòn nan. Apre sa, nœuds yo nan yon trye te kapab abite nenpòt kote nan ki miray. Men, sa yo, se komès-konpwomi ke nou dwe konsidere. 

Sonje ke, lè w ap chwazi yon done estrikti pou yon travay sèten, nou ta dwe reflechi sou ki kalite operasyon estrikti nan done bezwen sipò ak ki kantite pèfòmans nan nan chak nan sa yo operasyon zafè yo ban nou. Operasyon sa yo ka menm pwolonje pi lwen pase jis debaz gade leve, li ensèsyon. Sipoze nou te vle aplike yon kalite nan oto-ranpli fonctionnalités, anpil tankou Google motè rechèch fè. Ki se, retounen tout kle yo ak potansyèlman valè ki gen yon prefiks bay yo. 

Yon trye se inikman itil pou operasyon sa a. Li nan dwat yo repňte nan trye a pou chak karaktè nan prefiks la. Jis tankou yon gade operasyon an, nou te ka swiv endikasyon N. pa karaktè. Lè sa a, lè nou rive nan fen an prefiks, nou te ka repňte nan la rete pòsyon nan estrikti a done depi nenpòt nan kle yo pi lwen pase pwen sa a gen prefiks la. 

Li la tou fasil jwenn lis sa a nan alfabetik lòd depi nan eleman nan etalaj la timoun yo te bay lòd avèk lèt ​​alfabè. Se konsa, èspere ke ou pral konsidere bay ap eseye yon eseye. Mwen se Kevin Schmid, e sa se CS50. 

Ah, sa a se nan konmansman an nan bès la. Mwen regrèt. M regrèt. M regrèt. M regrèt. 

Grèv kat. Mwen se deyò. M regrèt. M regrèt. M regrèt. Padon pou fè moun ki te te modifye sa a ale fou. 

M regrèt. M regrèt. M regrèt. M regrèt. 

Oratè 1: Bon fè. Sa ki te vrèman byen fè.