DOUG LLOYD: Mar sin, i CS50, tá muid clúdaithe a lán de na struchtúir éagsúla sonraí, ceart? Againn atá le feiceáil eagair, agus nasctha liostaí, agus táblaí hash, agus iarracht, stoic agus scuainí. Beidh muid ag foghlaim freisin beag faoi ​​chrainn agus heaps, ach i ndáiríre seo go léir deireadh ach suas a bheith athruithe ar théama. Tá i ndáiríre na de chineál ar cheithre smaointe bunúsacha gur féidir gach rud eile boil síos go dtí. Arrays, liostaí nasctha, táblaí hash, agus iarracht. Agus mar a dúirt mé, tá Tá éagsúlachtaí orthu, ach tá sé seo go leor i bhfad ag dul chun achoimre gach rud a táimid ag dul chun labhairt faoi ​​sa rang seo i dtéarmaí C. Ach conas a dhéanann seo go léir beart suas, ceart? Táimid tar éis Labhair faoi na buntáistí agus na míbhuntáistí de gach ceann i físeáin ar leith orthu, ach níl a lán de uimhreacha dul thrown timpeall. Níl a lán de ginearálta smaointe ag fáil thrown timpeall. A ligean ar iarracht a dhéanamh agus a chomhdhlúthú sé isteach ach áit amháin. A ligean ar weigh an son i gcoinne na míbhuntáistí, agus a mheas a struchtúr sonraí d'fhéadfadh a bheith ar na sonraí ceart Struchtúr le do staid faoi leith, is cuma cén cineál sonraí a bhfuil tú ag a stóráil. Ní gá duit gá go mór i gcónaí chun úsáid a bhaint as a chur isteach go tapa Super, scriosadh, agus Lookup de Trie má tá tú i ndáiríre nach cúram faoi a chur isteach agus a scriosadh an iomarca. Más gá duit ach randamach tapa rochtain, b'fhéidir go bhfuil sraith níos fearr. Mar sin, a ligean ar distill sin. A ligean ar labhairt faoi gach ceann de na ceithre cineálacha mór ar struchtúir sonraí go atá againn Labhair faoi, agus ach a fheiceáil nuair a d'fhéadfadh siad a bheith go maith, agus nuair nach bhféadfadh siad a bheith chomh maith. Sin a ligean le tús a chur le arrays. Mar sin, a chur isteach, go bhfuil de chineál ar dona. 

Is chur isteach ag deireadh na eagar OK, má tá muid ag tógáil sraith mar a théann muid. Ach má ní mór dúinn a chur isteach eilimintí isteach sa lár, I mo thuairimse, ar ais go dtí a chur isteach a shórtáil, níl a lán de aistriú a d'oirfeadh gné i ann. Agus mar sin má táimid ag dul a chur isteach áit ar bith ach an deireadh eagar, go dócha nach chomh mór sin. 

Mar an gcéanna, a scriosadh, ach amháin má tá muid scriosadh ó dheireadh na eagar, Is dócha freisin nach mór mar sin má nach bhfuil muid ag iarraidh a fhágáil bearnaí folamh, a ghnáth ní dhéanaimid. Is mian linn a bhaint gné, agus ansin saghas a dhéanamh snug sé arís. Agus mar sin a scriosadh eilimintí ó sraith, freisin nach mór mar sin. 

Lookup, cé go bhfuil, go hiontach. Ní mór dúinn rochtain randamach, Lookup am tairiseach. Táimid ag rá ach seacht, agus a théann muid go eagar athlonnú seacht. Deirimid 20, le dul chun eagar athlonnú 20. Nach bhfuil againn a iterate trasna. Sin maith go leor. 

Tá arrays freisin sách éasca a shórtáil. Gach uair a labhair muid faoi sórtáil algartam, ar nós saghas roghnú, saghas a chur isteach, mboilgeog a shórtáil, chumasadh a shórtáil, a úsáid le linn i gcónaí arrays chun é a dhéanamh, mar go bhfuil arrays furasta go leor a saghas, i gcomparáid leis an struchtúir sonraí againn le feiceáil go dtí seo. 

Tá siad freisin réasúnta beag. Ní Tá a lán de spás breise. Atá leagtha tú díreach leataobh díreach oiread agus mar is gá duit a shealbhú do shonraí, agus sin go leor i bhfad é. Mar sin, tá siad deas beag agus éifeachtach sa tslí sin. Ach downside eile, áfach, Is go bhfuil siad socraithe i méid. Ní mór dúinn a dhearbhú go cruinn conas mór, ba mhaith linn ár n-sraith a bheith, agus táimid ag a fháil ach amháin lámhaigh ar sé. Ní féidir linn ag fás agus Laghdaigh sé. 

Más gá dúinn chun fás nó a Laghdaigh sé, táimid ag Ní mór a dhearbhú le sraith iomlán nua, cóip gach ceann de na gnéithe de na an chéad sraith isteach sa dara sraith. Agus má miscalculated muid go am, ní mór dúinn a dhéanamh arís. Ní mór mar sin. Mar sin ní gá arrays a thabhairt dúinn an tsolúbthacht go bhfuil líon athróg na n-eilimintí. 

Le liosta nasctha, Tá a chur isteach éasca go leor. Táimid ag tack díreach isteach ar an tosaigh. Tá a scriosadh freisin éasca go leor. Ní mór dúinn teacht ar na heilimintí. A mbíonn baint éigin cuardach. 

Ach nuair a tá tú ag fáil an eilimint bhfuil tú ag lorg, go léir is gá duit a dhéanamh Is athrú pointeoir, b'fhéidir dhá má tá tú a nasctha list-- ar doubly liosta nasctha, rather-- agus ansin is féidir leat saor in aisce go díreach an nód. Ní gá duit a athrú gach rud timpeall. Leat athrú ach dhá threo, mar sin tá go leor tapaidh. 

Tá Lookup olc áfach, ceart? Chun go mbeimid chun teacht ar an eilimint i liosta nasctha, cibé acu gceann agus ina gceann nó doubly nasctha, ní mór dúinn a líneach cuardaigh sé. Ní mór dúinn tús a chur ag an tús agus bogadh an deireadh, nó tús a chur ag deireadh an t-aistriú go dtí an tús. Ní chuirimid bhfuil rochtain randamach níos mó. Mar sin, má táimid ag déanamh a a lán de chuardach, b'fhéidir Ní liosta nasctha go leor mar sin maith dúinn. 

Tá siad freisin i ndáiríre deacair a shórtáil, ceart? An bealach amháin is féidir leat i ndáiríre shórtáil liosta nasctha is a shórtáil sé mar thógáil tú é. Ach má tá tú shórtáil sé mar atá tú thógáil é, tá tú a thuilleadh ag déanamh insertions tapaidh níos mó. Nach bhfuil tú ag tacking ach rudaí isteach ar an tosaigh. Tá tú chun teacht ar an bhfód i gceart a chur air, agus ansin do chur isteach thiocfaidh chun bheith díreach faoi chomh dona mar leanas a chur isteach i eagar. Mar sin, nach bhfuil nasctha liostaí chomh mór le haghaidh sonraí a shórtáil. 

Tá siad freisin go leor beag, méid-ciallmhar. Liosta doubly nasctha beagán níos mó ná liostaí nasctha ina n-aonar, atá beagán níos mó ná arrays, ach nach bhfuil sé méid ollmhór de spás amú. Mar sin má tá an spás ar phréimh, ach Ní préimh i ndáiríre dian, D'fhéadfadh sé seo a bheith ar an mbealach ceart dul. 

Táblaí hash. A chur isteach i dtábla hash Is simplí go leor. Tá sé ina próiseas dhá chéim. An Chéad ní mór dúinn a rith ár sonraí trí feidhm hash a fháil cód hash, agus ansin táimid ag cuir isteach an eilimint isteach sa tábla hash ag an suíomh cód hash. 

Scriosadh, cosúil leis an liosta a nasctha, Is éasca aon uair amháin a fhaigheann tú an eilimint. Tá tú chun é a fháil ar dtús, ach ansin nuair a scriosadh tú é, is gá duit ach a mhalartú cúpla leideanna, má tá tú ag baint úsáide as shlabhrú ar leith. Má tú ag baint úsáide deacra, nó mura bhfuil tú ag baint úsáide as shlabhrú ar chor ar bith i do tábla hash, Tá a scriosadh i ndáiríre i ndáiríre éasca. Gach gá duit a dhéanamh ná hash an sonraí, agus ansin téigh go dtí an suíomh sin. Agus ag glacadh leis nach bhfuil tú tá aon imbhuailtí, beidh tú in ann a scriosadh go han-tapa. 

Anois, tá Lookup i gcás ina rudaí a fháil beagán níos casta. Tá sé ar an meán níos fearr ná liostaí nasctha. Má tú ag baint úsáide shlabhrú, tá tú fós le liosta nasctha, rud a chiallaíonn go bhfuil tú fós ar an cuardach aimhleasa liosta nasctha. Ach toisc go bhfuil tú ag cur do nasctha liosta agus scoilteadh sé os cionn 100 nó 1,000 nó n-eilimintí i do tábla hash, tá tú Tá liostaí nasctha go léir ar cheann nú an méid. Tá siad ar fad i bhfad níos lú. Tá tú liostaí nasctha n ina ionad de liosta nasctha ar cheann de mhéid n. 

Agus mar sin i gcónaí seo fíor-domhan fachtóir, a bhfuil muid go ginearálta nach labhairt faoi i gcastacht am, sé dhéanann a dhéanamh i ndáiríre difríocht a anseo. Mar sin, tá Lookup fós líneach cuardaigh má tá tú ag baint úsáide as shlabhrú, ach fad an liosta bhfuil tú ag cuardach trí Tá an-, an-ghearr i gcomparáid. Arís, má tá sórtáil do sprioc anseo, hash tábla ar is dócha nach bhfuil ar an mbealach ceart dul. Just a úsáid le sraith má sórtáil i ndáiríre tábhachtach a thabhairt duit. 

Agus is féidir leo a reáchtáil an gamut na méid. Tá sé deacair a rá cé acu a Tá tábla hash beag nó mór, toisc go mbraitheann sé i ndáiríre ar cé chomh mór é do tábla hash. Má tá tú ag dul ach a bheith stóráil cúig eilimintí i do tábla hash, agus tá tú tábla hash le 10,000 heilimintí ann, bhfuil tú ag wasting is dócha a lán de spás. Codarsnacht bheith féidir leat chomh maith tá táblaí hash an-dlúth, ach faigheann an níos lú do tábla hash, an níos faide gach ceann de na liostaí sin atá nasctha Faigheann. Agus mar sin aon bhealach a shainmhíniú ann i ndáiríre go díreach ar an méid de tábla hash, ach tá sé sábháilte is dócha a rá go bhfuil sé go ginearálta ag dul a bheith níos mó ná nasctha liosta a stóráil ar na sonraí céanna, ach níos lú ná Trie. 

Agus tá iarracht an ceathrú de na struchtúir go atá muid ag caint faoi. A chur isteach i i Trie is casta. Níl a lán de dinimiciúil leithdháileadh cuimhne, go háirithe ag an tús, mar atá tú ag tosú a thógáil. Ach tá sé in am tairiseach. Tá sé ach an eilimint dhaonna anseo go ndéanann tricky é. Ag a bhíonn pointeoir null, malloc spás, dul ann, spás, b'fhéidir malloc ó ann arís. An saghas fachtóir imeaglú leideanna i leithdháileadh cuimhne dinimiciúil Is é an hurdle a ghlanadh. Ach nuair a tá tú ag glanadh é, leanas a chur isteach iarbhír a thagann simplí go leor, agus tá sé cinnte am tairiseach. 

Is scriosadh éasca. Gach gá duit a dhéanamh ná nascleanúint síos cúpla leideanna agus saor in aisce ar an nód, mar sin tá go maith go leor. Tá Lookup freisin go leor go tapa. Tá sé seo bunaithe ach amháin ar an fad do chuid sonraí. Mar sin, má tá gach ceann de do shonraí cúig teaghráin carachtar, mar shampla, tá tú ag a stóráil cúig teaghráin carachtar i do Trie, thógann sé ach cúig céimeanna a teacht ar cad tá tú ag lorg. Is cúig ach ina fhachtóir tairiseach, mar sin arís, a chur isteach, scriosadh, agus a chuardach tá anseo am ar fad tairiseach, go héifeachtach. 

Tá rud eile go bhfuil do Trie iarbhír curtha in eagar de chineál ar cheana, ceart? De bhua an gcaoi bhfuil muid eilimintí a chur isteach, trí litir ag dul trí litir an eochair, nó trí dhigit dhigit an eochair, de ghnáth, chríochnaíonn do Trie suas a bheith de chineál ar curtha in eagar mar a thógáil tú é. Ní chuireann sé a dhéanann i ndáiríre ciall chun smaoineamh ar sórtáil ar an mbealach céanna a cheapann againn faoi sé le arrays, nó liostaí nasctha, nó táblaí hash. Ach i roinnt chiall, do Trie Tá curtha in eagar mar a théann tú. 

An downside, ar ndóigh, go a thiocfaidh chun bheith go tapa Trie ollmhór. Ó gach pointe acomhal, d'fhéadfadh tú have-- más é atá do eochair dhigit, tá tú 10 eile áiteanna is féidir leat dul, a Ciallaíonn sé sin gach nód Tá faisnéis faoi ​​na sonraí is mian leat a stóráil ag an nód, móide 10 leideanna. Cé acu, ar CS50 IDE é, 80 bytes. Mar sin tá sé ar a laghad 80 bytes le haghaidh gach nód a chruthú duit, agus ní ar sin comhaireamh fiú sonraí. Agus má tá do nóid litreacha in ionad na dhigit, anois tá tú 26 leideanna ó gach suíomh. Agus 26 uair 8 Is dócha 200 bytes, nó rud éigin mar sin. Agus tá tú caipitil agus lowercase-- is féidir leat a fheiceáil nuair mé ag dul leis seo, ceart? Is féidir le do nóid fháil i ndáiríre mór, agus mar sin an Trie féin, tríd is tríd is féidir, fháil i ndáiríre mór, freisin. Mar sin má tá an spás ar ard phréimh ar do chóras, ní a d'fhéadfadh a bheith ar Trie ar an mbealach ceart chun dul, cé na tairbhí eile a thagann i spraoi. Tá mé Doug Lloyd. Is é seo an CS50.