>> KEVIN Schmid: Uaireanta, nuair a thógáil clár, b'fhéidir gur mhaith leat a úsáid a bhaint as
struchtúr sonraí ar a dtugtar foclóir.
A eochracha léarscáileanna foclóir, atá teaghráin de ghnáth, do luachanna, ints,
carachtair, pointeoir le roinnt réad, is cuma cad ba mhaith linn.
Tá sé díreach cosúil le foclóirí ngnáthnós focail léarscáil trí shainmhínithe.
>> A chur ar fáil Foclóirí dúinn leis an cumas chun faisnéis a stóráil
bhaineann le rud éigin agus é a breathnú suas níos déanaí.
Mar sin, conas is féidir linn a chur i bhfeidhm i ndáiríre foclóir i, a rá, C cód gur féidir linn
úsáid i gceann dár gcláir?
Bhuel, tá a lán de na bealaí gur d'fhéadfadh muid foclóir a chur i bhfeidhm.
>> I gcás amháin, d'fhéadfadh muid a úsáid le sraith go bhfuil muid dinimiciúil ath-mhéid nó a d'fhéadfadh muid a úsáid
liosta nasctha, tábla hash nó crann dénártha.
Ach is cuma cad a roghnaíonn againn, ba chóir dúinn a bheith aireach ar an éifeachtúlacht agus
feidhmíocht chur chun feidhme.
Ba chóir dúinn smaoineamh ar an algartam a úsáidtear a chur isteach agus a breathnú suas míreanna i
ár struchtúr sonraí.
>> Chun anois, a ligean ar glacadh leis go bhfuil muid ag ag iarraidh a teaghráin a úsáid mar eochracha.
A ligean ar labhairt faoi an bhféidearthacht amháin, struchtúr sonraí a dtugtar trie.
Mar sin, tá anseo dearc de trie.
>> Mar a léiríonn an pictiúr, le trie Tá struchtúr crann le sonraí a
nóid nasctha le chéile.
Feicimid go bhfuil fhréamh ann go soiléir nód le roinnt naisc a leathnú go dtí
nóid eile.
Ach cad a dhéanann gach nód comhdhéanta de?
Má glacaimid go bhfuil muid eochracha a stóráil le carachtair aibítreacha amháin, agus
ní féidir linn cúram faoi caipitlithe, anseo tá sainmhíniú ar nód a
is leor.
>> Tá réad a bhfuil a gcineál struct Tá nód dhá chuid
ar a dtugtar sonraí agus leanaí.
Táimid tar éis d'fhág an chuid sonraí mar a comment a chur in ionad comhpháirt
dearbhú nuair a bhíonn nód struct ionchorprú i gclár C.
D'fhéadfadh an chuid sonraí de nód a bheith ina Luach Boole a chur in iúl cibé acu atá nó
Léiríonn nach bhfuil an nód críochnú de eochair foclóir nó d'fhéadfadh sé a bheith ina
teaghrán ionadaíonn an sainmhíniú de focal san fhoclóir.
>> Beidh muid úsáid ar aghaidh smiley a chur in iúl nuair a bhíonn sonraí i láthair i nód.
Tá 26 eilimintí i ár páistí sraith, innéacs amháin
in aghaidh an litir.
Beidh muid a fheiceáil ar an tábhacht seo go luath.
>> A ligean ar a fháil breathnú níos dlúithe ar an nód fréimhe inár léaráid, nach bhfuil aon sonraí
a bhaineann leis, mar atá léirithe ag an éagmais an duine smiley sa
chuid sonraí.
Na saigheada a shíneann ó na codanna den Léiríonn na páistí sraith neamh-nód
leideanna le nóid eile.
Mar shampla, an arrow a shíneann ó an dara gné de leanaí
Léiríonn an litir B i eochair fhoclóir.
Agus sa léaráid níos mó lipéad dúinn é le B.
>> Tabhair faoi deara gur sa léaráid mó, nuair a muid tharraingt pointeoir chuig nód eile, é a
nach ábhar i gcás an rinn saighde Buaileann an nód eile.
Tá ár sampla foclóir trie dhá fhocal, go agus súmáil.
A ligean ar siúl trí shampla de breathnú suas sonraí le haghaidh eochair.
>> Cuir bhíomar ag iarraidh chun breathnú suas ar an luach comhfhreagrach don folctha eochair.
Beidh muid tús a chur lenár breathnú suas ag an nód fhréamh.
Ansin, beidh muid a chur ar an chéad litir ar ár eochair, B, agus teacht ar an comhfhreagrach
láthair in ár sraith bpáistí.
Tabhair faoi deara go bhfuil go díreach 26 spotaí in eagar, ceann amháin do gach litir
an aibítir.
Agus beidh orainn ionadaíocht a dhéanamh ar spotaí an litreacha na haibítre in ord.
>> Beidh muid ag breathnú ar an dara innéacs ansin, innéacs amháin, do B. Go ginearálta, má táimid
go bhfuil roinnt aibítreach carachtar C againn D'fhéadfadh a chinneadh an láthair comhfhreagrach
in eagar leanaí ag baint úsáide ríomh mar seo.
D'fhéadfadh muid a bheith in úsáid le páistí níos mó eagar má bhíomar ag iarraidh a thairiscint breathnú suas ar
eochracha le raon níos leithne de charachtair, mar shampla an fad
Carachtar ASCII a leagan síos.
>> Sa chás seo, an pointeoir in ár sraith páistí ag
Ní innéacs amháin null.
Mar sin, beidh muid ag leanúint ar aghaidh ag lorg suas an folctha eochair.
Má bhíonn muid riamh pointeoir nialasach ag an láthair ceart i do na páistí
eagar cé trasnaithe againn ar an nóid, ansin beidh orainn a rá go bhfuil muid
Ní fhéadfaí aon rud don eochair sin a aimsiú.
>> Anois, beidh orainn a chur ar an dara litir ár n-eochair, A, agus leanúint ar aghaidh a leanas
leideanna ar an mbealach seo go dtí go againn teacht ar an deireadh ár eochair.
Má shroicheann muid deireadh an eochair gan ag bualadh aon foircinn marbh, leideanna null,
mar go bhfuil an cás anseo, ansin dúinn ach a sheiceáil ach rud amháin níos mó.
An bhfuil an eochair i ndáiríre san fhoclóir?
>> Más amhlaidh, ba chóir dúinn a fháil ar luach, go maith le icon aghaidh smiley inár léaráid ina
Críochnaíonn an focal.
Má tá rud éigin eile a stóráil le na sonraí, ansin is féidir linn a thabhairt ar ais é.
Mar shampla, nach bhfuil an zú eochair sa foclóir, cé go raibh muid ábalta a bheith
shroich an deireadh an eochair gan riamh bualadh le pointeoir null, agus muid
iterate trí trie.
>> Má iarracht muid chun breathnú suas ar an folctha eochair, an dara nód seo caite innéacs eagar,
a fhreagraíonn do na litir H, bheadh a bhí i seilbh pointeoir null.
Mar sin, nach bhfuil folctha san fhoclóir.
Agus mar sin tá trie uathúil sa mhéid is go na heochracha Tá riamh stóráil go sainráite sna
an struchtúr sonraí.
Mar sin, conas is féidir linn rud éigin a chur isteach isteach i trie?
>> A ligean ar chur isteach an eochair zú isteach inár trie.
Cuimhnigh go bhfuil ar aghaidh smiley ag nód D'fhéadfadh freagairt cód le simplí
Luach Boole a chur in iúl go zú Is san fhoclóir nó d'fhéadfadh sé
Comhfhreagróidh tuilleadh eolais a fháil go bhfuil muid ar mian leo a chomhlachú leis an zú eochair,
cosúil leis an sainmhíniú ar an focal nó rud éigin eile.
I roinnt bealaí, an próiseas a chur isteach Tá rud éigin i trie cosúil leis
ag breathnú suas rud éigin i trie.
>> Beidh muid tús a chur leis an nód fréimhe arís, leideanna seo a leanas a fhreagraíonn do
na litreacha ar ár eochair.
Luckily, bhí muid in ann leideanna a leanúint léir ar an mbealach go dtí gur shroich muid
an deireadh an eochair.
Ós rud é zú réimír an focal súmáil, atá ina bhall den
foclóir, ní mór dúinn a leithdháileadh aon nóid nua.
>> Is féidir linn a mhodhnú ar an nód a chur in iúl go an chonair na carachtair as a
léiríonn sé ár foclóir eochair.
Anois, a ligean ar iarracht tríd an eochair folctha isteach sa trie.
Beidh muid ag tosú ag an nód fréimhe agus leideanna a leanúint arís.
Ach sa chás seo, bhuail muid marbh deireadh sula bhfuil muid in ann a fháil chun an
deireadh an eochair.
Anois, beidh orainn gá a leithdháileadh roinnt nua Beidh gá nóid a nua amháin a leithdháileadh
nód le haghaidh gach eile litir ár eochair.
>> Sa chás seo, ní mór dúinn ach a leithdháileadh nód nua amháin.
Ansin, beidh orainn gá a dhéanamh ar an innéacs H tagairt an nód nua seo.
Arís eile, is féidir linn a mhodhnú an nód a le fios go an chonair na carachtair
as a dtiocfaidh sé ionann eochair i ár foclóir.
A ligean ar réasúnú faoin asymptotic chastacht ár nósanna imeachta chun na
dá n-oibríochtaí.
>> Faoi deara go sa dá chás ar an líon d'céimeanna ár algartam thóg a bhí
comhréireach leis an líon litreacha sa eochairfhocal.
Sin ceart.
Nuair is mian leat chun breathnú suas le focal i trie is gá duit ach a iterate trí
na litreacha ceann ar cheann go dtí go tú ceachtar teacht ar an deireadh an fhocail nó
bhuail ar deireadh marbh sa trie.
>> Agus nuair is mian leat a chur isteach eochair luach péire isteach trie baint úsáide as an
imeachta a phlé againn, an cás is measa beidh tú a leithdháileadh nód nua
do gach litir.
Agus beidh muid ag glacadh leis go bhfuil leithdháileadh Is oibríocht am tairiseach.
Mar sin, má glacadh againn go bhfuil an fad eochrach atá teorantach le tairiseach seasta, déantar na
Tá isteach agus breathnú suas tairiseach oibríochtaí ama le haghaidh trie.
>> Más rud é nach bhfuil muid a dhéanamh ar an toimhde go Is é an fad eochrach atá teorantach le seasta
tairiseach, ansin a chur isteach agus a breathnú suas, i gcás is measa, tá líneach i
fad an eochair.
Fógra go bhfuil líon na n-ítimí a stóráil sa trie ní dhéanann sé difear an cuma ar bun
nó am a chur isteach.
Tá sé tionchar ach amháin ag an fad an eochair.
>> I gcodarsnacht leis sin, iontrálacha a chur leis, a rá, Is nós le tábla hash a dhéanamh
amach anseo breathnú suas níos moille.
Cé go d'fhéadfadh sé seo fuaime achomharc ar dtús, ba chóir dúinn a choinneáil i gcuimhne go bhfuil
Ní dhéanann castacht asymptotic fabhrach chiallaíonn go bhfuil i gcleachtas na sonraí
Tá struchtúr gá thar reproach.
Ní mór dúinn a mheas freisin go bhfuil a stóráil ar focal i trie is gá dúinn, i an ceann is measa
cás, roinnt nóid comhréireach le fad an focal féin.
>> Claonadh iarracht a úsáid a lán de spás.
Sin i gcodarsnacht le tábla hash, nuair is gá dúinn ach nód nua amháin
stóráil roinnt péire eochair luach.
Anois, arís go teoiriciúil, spás mór Ní tomhaltas cosúil mhaith mór
déileáil, go háirithe ós rud é go nua-aimseartha Tá ríomhairí ghigibheart agus
ghigibheart de chuimhne.
Ach casadh sé amach go bhfuil muid fós a bheith buartha faoi úsáide cuimhne agus
eagraíocht ar mhaithe le feidhmíocht, ós rud é ríomhairí nua-aimseartha
Tá meicníochtaí i bhfeidhm faoi na cochall chun dlús a chur le rochtain chuimhne.
>> Ach oibríonn na meicníochtaí is fearr nuair a rochtana cuimhne a dhéantar i dhlúth
réigiúin nó ceantair.
Agus d'fhéadfadh na nóid a trie cónaí áit ar bith sa gcarn.
Ach tá na trádáil-dícheangail nach mór dúinn a mheas.
>> Cuimhnigh go bhfuil, nuair a roghnú na sonraí struchtúr do thasc áirithe, ní mór dúinn
Ba chóir smaoineamh ar cad é cineál na oibríochtaí is gá an struchtúr sonraí a
tacaíocht agus cé mhéad an fheidhmíocht gach ceann de na
nithe oibríochtaí a chur chugainn.
Féadfaidh na hoibríochtaí fiú leathnú níos faide ná díreach
breathnú bunúsach suas agus a chur isteach.
Cuir bhíomar ag iarraidh a chineál a chur i bhfeidhm na feidhmiúlachta auto-iomlán, i bhfad
mar a dhéanann Google inneall cuardaigh.
Is é sin, ar ais go léir na heochracha agus d'fhéadfadh a luachanna
Tá réimír tugtha.
>> Is trie uathúil úsáideach don oibríocht seo.
Tá sé éasca a iterate trí an trie do gach carachtar ar
an réimír.
Díreach cosúil le breathnú suas oibríocht, d'fhéadfadh muid leideanna a leanúint
carachtar le carachtar.
Ansin, nuair a thagann muid ag deireadh na réimír, d'fhéadfadh muid a iterate trí na
chuid eile den struchtúr sonraí ós rud é aon cheann de na heochracha níos faide
an bpointe seo tá an réimír.
>> Tá sé éasca freisin a fháil seo a liostú in ord aibítre ó
eilimintí den eagar leanaí curtha in ord aibítre.
Mar sin tá súil againn go mbainfidh tú a mheas iarracht a thabhairt triail a bhaint.
Tá mé Kevin Schmid, agus tá sé seo CS50.
>> Ah, is é seo an tús an meath.
Tá brón orm.
>> Stailc ceithre.
Tá mé amach.
Tá brón orm.
Tá brón orainn le haghaidh a dhéanamh ar an duine a Tá a chur in eagar seo a dul ar mire.
>> Tá brón orm.
Tá brón orm.
>> Cainteoir 1: Maith thú.
Sin a rinneadh i ndáiríre go maith.