[Seinm ceoil] DAVID MALAN: Is é seo an CS50. Agus is é seo an dá an tús agus an end-- mhaith literally-- beagnach an deireadh na seachtaine sé. 

Shíl mé gur mhaith liom a roinnt a beagán de rud spraoi. Tá mé ceirteacha tarraingthe sin suas ó Sonraí seimeastar seo caite a leagan síos. Is féidir leat a thabhairt chun cuimhne go iarraimid ort ar gach fhoirm a leagtar p má tá tú ag faire ar líne nó má tá tú i láthair go pearsanta. Agus is é anseo ar na sonraí. Mar sin, bhí lá atá inniu ann go mór intuartha. Ach bhíomar ag iarraidh a chaitheamh le beagán ama a bhfuil tú mar sin féin. An mbeadh duine ar bith a thuairim cén fáth seo Tá graf chomh jaggy, suas síos, suas síos, chomh comhsheasmhach? Cad a dhéanann gach ceann de na beanna agus umair ionadaíocht? 

LUCHT ÉISTEACHTA: [inaudible] DAVID MALAN: Go deimhin. Agus níos amusingly, Dia forbid, atá againn léacht amháin ar an Aoine ag tús an tseimeastair, go bhfuil an méid a fheiceann muid a tharlóidh. Mar sin lá atá inniu ann, páirt a ghlacadh againn i le beagán níos mó faoi struchtúir sonraí. Agus a thabhairt duit níos mó de soladach samhail intinne d'fhadhbanna ar a cúig, atá anois amach. Misspellings, wherein, beidh muid lámh tú comhad téacs éigin 100,000 móide focail Béarla, agus bhfuil tú ag dul a bheith acu chun an figiúr amach conas a luchtú cleverly iad i gcuimhne, i RAM, ag baint úsáide as cuid de na sonraí struchtúr de do rogha. 

Anois, d'fhéadfadh struchtúr sonraí den sórt sin amháin a bheith, ach is dócha nach chóir go mbeadh, an liosta nasctha go cothrom saonta, lenar tugadh isteach againn uair dheireanach. Agus bhí liosta nasctha ar a laghad, buntáiste amháin thar eagar. Cad é buntáiste amháin de liosta nasctha fhéadfaí a rá? 

LUCHT ÉISTEACHTA: chur isteach. 

DAVID MALAN: chur isteach. Cad atá i gceist agat leis sin? 

LUCHT ÉISTEACHTA: Áit ar bith chomh maith an liosta [inaudible]. 

DAVID MALAN: Maith. Mar sin, is féidir leat a chur isteach eilimint cibé áit ba mhaith leat i lár an liosta gan rud ar bith a Suaitheadh, a tháinig chun críche againn, inár sórtáil díospóireachtaí nach bhfuil, gá gur rud maith, mar a thógann sé am chun bogadh i ndáiríre gach ceann de na daoine ar chlé nó ceart. Agus mar sin le liosta nasctha, is féidir leat ach a leithdháileadh le malloc, nód nua, agus ansin cúpla thabhairt cothrom le dáta pointers-- dhá, trí oibríochtaí max-- agus tá muid in ann duine éigin a sliotán i áit ar bith i liosta. 

Cad eile a bhí buntáiste faoi ​​liosta nasctha? Yeah? 

LUCHT ÉISTEACHTA: [inaudible] DAVID MALAN: Perfect. Perfect. Tá sé i ndáiríre dinimiciúil. Agus nach bhfuil tú ag cion, roimh ré, le roinnt méid seasta smután de chuimhne, mar a bheadh ​​agat go bhfuil sraith, an bun os cionn a é gur féidir leat nóid leithdháileadh ach ar t-éileamh sa tslí sin a úsáid ach amháin mar spás i bhfad mar is gá duit i ndáiríre. I gcodarsnacht le sraith, d'fhéadfadh tú thaisme leithdháileadh ró-beag. Agus ansin tá sé ag dul ach a bheith ina pian i muineál a athdháileadh sraith nua níos mó, cóip gach rud níos mó, saor in aisce ar an eagar d'aois, agus ansin bogadh faoi do ghnó. Nó níos measa, d'fhéadfá a dháileadh ar bhealach cuimhne níos mó ná de dhíth ort i ndáiríre, agus mar sin tá tú ag dul a bheith acu an- tearc-daonra eagar, mar a déarfá. 

Mar sin, tugann liosta nasctha tú na buntáistí a bhaineann le dinimiceas agus solúbthacht le insertions agus scriosadh. Ach surely ní mór go mbeadh phraghas a íocadh. Go deimhin, ar cheann de na téamaí iniúchadh ar tráth na gceist náid Bhí cúpla ar an trádáil-dícheangail againn le feiceáil go dtí seo. Mar sin, cad é ar phraghas a íocadh nó a taobh thíos de liosta nasctha? Yeah. 

LUCHT ÉISTEACHTA: No rochtain randamach. 

DAVID MALAN: No rochtain randamach. Ach a cares? Ní rochtain randamach fuaime láidir. 

LUCHT ÉISTEACHTA: [inaudible] DAVID MALAN: Go díreach. Más mian leat a bheith acu a algorithm-- áirithe agus lig dom a mholadh i ndáiríre Cuardach dhénártha go háirithe, ina tá sé ar cheann muid úsáid as go leor le bit-- más rud é nach bhfuil tú rochtain randamach, Ní féidir leat a dhéanamh uimhríochtúil simplí aimsiú ar cosúil leis an eilimint lár agus léim ceart dó. Tá tú ina ionad sin chun tús a chur ag an gcéad eilimint agus líneach cuardach ó chlé go deas más mian leat a aimsiú lár nó aon eilimint eile. 

LUCHT ÉISTEACHTA: Bíonn sé dócha níos mó cuimhne. 

DAVID MALAN: Glacann cuimhne níos mó. Cá bhfuil sé sin sa bhreis costas ag teacht ó i gcuimhne? 

LUCHT ÉISTEACHTA: [inaudible] DAVID MALAN: Go díreach. Sa chás seo anseo, bhí againn liosta nasctha do slánuimhreacha, agus fós tá muid ag dúbailt an méid chuimhne ní mór dúinn ag freisin a stóráil ar na leideanna. Anois níos lú de le déileáil go mór mar do structs fháil níos mó agus go bhfuil tú ag a stóráil gan uimhir ach b'fhéidir mac léinn nó rud éigin eile. Ach tá an pointe cinnte. Agus mar sin roinnt de na n-oibríochtaí ar liostaí nasctha bhí ar a dtugtar Bhí O mór líneach n--. Rudaí cosúil a chur isteach nó cuardach nó a scriosadh i gcás gné tharla a bheith ag an deireadh an- an liosta cibé an bhfuil sé curtha in eagar nó nach bhfuil. 

Uaireanta, d'fhéadfadh tú a fháil ádh agus i bounds mar sin níos ísle ar na hoibríochtaí D'fhéadfadh a bheith chomh maith am tairiseach má tá tú i gcónaí ag féachaint ar an chéad eilimint, mar shampla. Ach sa deireadh thiar, geallta againn a bhaint amach ar an iomaíocht don duais mhór na struchtúir sonraí, nó roinnt díobh a chomhfhogasú, trí am tairiseach. An féidir linn teacht ar eilimintí nó eilimintí a chur nó eilimintí ó liosta a bhaint? Beidh muid a fheiceáil go leor go luath. Agus casadh sé amach go bhfuil ceann na meicníochtaí bhfuil muid dul chun tús a úsáid sa lá atá inniu, úsáid bliantúil i p leagtar cúig, Tá i ndáiríre ar an eolas go leor. Mar shampla, má tá sé seo a bunch leabhair scrúdaithe, gach ceann acu Tá an mhic léinn den chéad uair ainm agus ainm seo caite ar sé, agus roghnaigh mé iad suas ó ag deireadh an scrúdú, agus tá siad ar fad go leor i bhfad in ord randamach, agus ba mhaith linn a dul faoi sórtáil na scrúduithe ionas go mbeidh aon uair amháin grádaithe tá sé ach i bhfad níos éasca agus níos tapúla chun iad a thabhairt ar ais amach do mhic léinn in ord aibítre. Cad é a bheadh ​​do instincts a le carn de scrúduithe mar seo? 

Bhuel, má tá tú cosúil liomsa, tá tú D'fhéadfadh a fheiceáil go bhfuil sé seo m, mar sin tá mé ag dul go dtí saghas seo a chur isteach, má tá sé seo mo tábla nó mo urlár i gcás Tá mé ag rudaí a leathadh out-- nó mo eagar really-- D'fhéadfadh liom a chur ar gach ceann de na Ms i ann. Oh. Seo A. Mar sin, d'fhéadfadh mé a chur ar an mar a thar anseo. Oh. Seo A. eile Tá mé ag dul a chur ar go bhfuil níos mó anseo. Seo Z. Seo M. eile Agus mar sin D'fhéadfadh mé tús chairn mar seo a dhéanamh. Agus ansin b'fhéidir gur mhaith liom dul i níos déanaí agus saghas an-nitpicky-ú saghas na chairn aonair. Ach tá an pointe ba mhaith liom breathnú ag an ionchur go bhfuil mé láimh agus ba mhaith liom a dhéanamh ar roinnt a ríomh cinneadh bunaithe ar an ionchur. Má thosaíonn sé le A, é a chur thar ann. Má thosaíonn sé le Z, é a chur os cionn ann, agus gach rud idir eatarthu. 

Mar sin, tá sé seo mar theicníc go ar a dtugtar de ghnáth mar hashing-- H-A-S-H-- rud a chiallaíonn go ginearálta ag cur mar ionchur agus ag úsáid an ionchur a ríomh luach, go ginearálta ar roinnt, agus go Is é uimhir an t-innéacs i stóráil coimeádán, cosúil le sraith. Mar sin, i bhfocail eile, d'fhéadfadh liom a bheith fheidhm hash, mar is féidir liom i mo cheann, go má fheiceann mé duine éigin Tá An t-ainm a thosaíonn le A, Tá mé ag dul a mhapáil go a náid i mo cheann. Agus má fheiceann agam ar dhuine a bhfuil Z, tá mé ag dul a mhapáil go dtí 25 i mo cheann agus ansin a chur go i an carn seo caite mó. 

Anois, má cheapann tú faoi mo inchinn ach d'fhéadfadh clár C, cén uimhreacha tú ag brath ar a bhaint amach an toradh céanna? I bhfocail eile, má tá tú Bhí an ASCII carachtar A, conas a dhéanann tú a chinneadh cad buicéad a chur i? Tá tú dócha nach bhfuil ag iarraidh a é a chur i buicéad 65, a Bheadh ​​a bheith cosúil le níos mó ann gan aon chúis mhaith. Cá bhfuil tú ag iarraidh a chur ar A i dtéarmaí a luach ASCII? Cá bhfuil tú ag iarraidh a dhéanamh ar a ASCII luach chun teacht suas le buicéad níos cliste é a chur i? 

LUCHT ÉISTEACHTA: Lúide A. 

DAVID MALAN: Yeah. Mar sin, lúide A nó lúide go sonrach 65 má tá sé a A. caipitil Nó 98 más rud é tá sé ina litreacha beaga a. Agus mar sin a thabharfadh deis dúinn, an- simplí agus an-arithmetically, rud éigin a chur isteach i buicéad mar sin. Mar sin, casadh sé amach a dhéanann muid i ndáiríre seo chomh maith fiú leis an tráth na gceist. 

Mar sin, d'fhéadfadh tú cuimhne circled tú do An t-ainm chomhbhaill teagaisc ar an gclúdach. Agus bhí ainmneacha na TF eagraithe isteach sna colúin ord aibítre, go maith, chreideann sé nó nach bhfuil, nuair gach 80 móide dúinn fuair le chéile an oíche eile a grád, an chéim dheireanach in ár bpróiseas grádaithe is é sin le hais na tráth na gceist i mór spás urláir ag an [inaudible] agus a leagan ar gach duine tráth na gceist amach i díreach mar an ord a TF ar ainmneacha ar an gclúdach, mar gheall ar ansin tá sé a lán níos éasca dúinn chun cuardach a dhéanamh tríd an úsáid a bhaint as líneach cuardach nó de shaghas éigin de cleverness le haghaidh TF chun teacht ar a chuid nó a cuid mac léinn 'tráth na gceist. 

Mar sin, an smaoineamh seo de hashing go mbainfidh tú a fheiceáil go bhfuil Tá go leor cumhachtach i ndáiríre deas coitianta agus an-iomasach, i bhfad cosúil le roinnt b'fhéidir agus Conquer bhí i seachtain nialas. Tá mé ag súil go tapa ar an hackathon cúpla bliain ó shin. Bhí sé seo Zamyla agus cúpla mic léinn eile Beannacht foirne mar a tháinig siad i. Agus bhí againn a bunch iomlán de fillte táblaí ann le tags ainm. Agus bhí againn ar an clibeanna ainm atá eagraithe leis cosúil leis an Chomh thar ann agus an ZS thar ann. Agus mar sin ar cheann de na TFS an-cleverly Scríobh seo mar na treoracha don lá. Agus i seachtain 12 den seimeastar seo ar fad déanta ciall foirfe agus gach duine Bhí a fhios cad atá le déanamh. Ach ag am ar bith atá tú ciúáilte ar an mbealach céanna, bhfuil tú ag cur chun feidhme an coincheap céanna a hash. Mar sin a ligean foirmiúil sé le beagán. Seo eagar. Tá sé tharraingt chun bheith beagán ar fud ach a léiriú, amhairc, go bhféadfaimis a chur teaghráin i rud éigin mar seo. Agus is é an eagar go soiléir ar mhéid 26 iomlán. Agus is é an rud ar a dtugtar tábla treallach. Ach tá sé seo ach ealaíontóra rendition cad a d'fhéadfadh tábla hash bheith. 

Mar sin, tábla hash anois ag dul go dtí a bheith ina struchtúr sonraí ar leibhéal níos airde. Ag deireadh an lae tá muid ar tí é a fheiceáil go bhfuil tú Is féidir le tábla hash, a chur i bhfeidhm a i bhfad cosúil leis an líne a sheiceáil-i ag hackathon i bhfad mar seo tábla a úsáidtear le haghaidh a shórtáil leabhair scrúdú. Ach tá tábla hash saghas seo leibhéal ard coincheap a d'fhéadfadh go n-úsáideann eagar thíos an cochall chur chun feidhme, nó d'fhéadfadh sé a úsáid liosta fad, nó fiú b'fhéidir roinnt struchtúir sonraí eile. Agus anois go bhfuil a thógáil theme-- cuid de na comhábhair bunúsacha cosúil le sraith agus an foirgneamh bloc anois ar liosta ar fad agus féachaint cad eile is féidir linn a thógáil ar bharr sin, ar nós comhábhair isteach i chos, a dhéanamh níos mó agus níos mó torthaí deiridh suimiúil agus úsáideach. 

Mar sin, leis an tábla hash d'fhéadfadh muid a chur i bhfeidhm é i gcuimhne go pictiúrtha mar seo, ach conas a d'fhéadfaí é a chódú i ndáiríre suas? Bhuel, b'fhéidir go bhfuil chomh simplí sin. Más rud é CUMAS i ngach caipíní é, ach roinnt constant-- mar shampla 26, ar feadh 26 litreacha an alphabet-- D'fhéadfadh liom glaoch ar mo tábla athraitheach, agus a d'fhéadfadh liom a éileamh go bhfuil mé ag dul go dtí chur réaltaí Char i ann, nó téad. Mar sin, tá sé chomh simplí sin má tá tú ag iarraidh a tábla hash a chur i bhfeidhm. Agus fós, tá sé seo i ndáiríre ach le sraith. Ach arís, a hash Tá tábla anois cad Feicfidh muid glaoch ar an gcineál sonraí teibí go díreach saghas layering choincheapúil ar bharr de rud éigin níos mundane Is maith anois le sraith. 

Anois, cén chaoi a théann muid maidir le fadhbanna a réiteach? Bhuel, níos luaithe a bhí mé ar an só a bhfuil go leor spáis tábla anseo ionas go bhféadfaí mé a chur ar an tráth na gceist in áit ar bith a bhí mé. Mar sin, d'fhéadfadh Mar go here. D'fhéadfadh ZS go here. D'fhéadfadh Ms go here. Agus ansin bhí mé roinnt spás breise. Ach tá sé seo le beagán de cheart cheat anois mar gheall ar an tábla seo, má tá mé i ndáiríre cumha air mar eagar é, ach ag dul a bheith ar roinnt méid seasta. 

Mar sin go teicniúil, má tá mé ag tarraingt suas tráth na gceist mac léinn eile agus a fheiceáil, ó, an duine seo Tosaíonn an t-ainm le A freisin, Mé de chineál ar iarraidh a chur sé ann. Ach chomh luath agus a chuir mé sé ann, más rud é Léiríonn an tábla seo go deimhin eagar, Tá mé ag dul a bheith sáraitheach nó clobbering whoever tráth na gceist seo scoláire. Ceart? Más é seo sraith, is féidir ach rud amháin dul i ngach ceann de na cealla nó eilimintí. Agus mar sin mé cineál a bheith a roghnú agus a roghnú. 

Anois níos luaithe mé cineál cheated agus rinne seo nó I ach de chineál ar Cruachta iad os cionn a chéile. Ach ní ar sin ag dul a eitilt i cód. Mar sin, nuair a d'fhéadfadh mé a chur ar an an dara mac léinn a bhfuil a ainm Tá más rud é go léir a bhí mé seo spás tábla atá ar fáil? Agus tá mé úsáid as trí sliotán agus é Breathnaíonn an nós níl ach cúpla daoine eile. Cad is féidir leat a dhéanamh? LUCHT ÉISTEACHTA: [inaudible] DAVID MALAN: Yeah. B'fhéidir ligean ar a choinneáil ach simplí é. Ceart? Ní chuireann sé oiriúnach nuair is mian liom a chur air. Mar sin, tá mé ag dul chun é a chur go teicniúil i gcás ina mbeadh B dul. Anois, ar ndóigh, tá mé ag tosú a phéinteáil mé féin isteach i gcúinne. Má fhaigheann mé le mac léinn a bhfuil a ainm i ndáiríre B, anois tá B ag dul a bheith ar athraíodh a ionad beagán ar aghaidh, d'fhéadfadh mar a tharlaíonn, yep, má tá sé seo le B, anois tá sé ag dul anseo. 

Agus mar sin go tapa an- D'fhéadfadh a bheith fadhbanna, ach tá sé mar theicníc go hiarbhír dá dtagraítear mar líneach tóraíochta, trína go measann tú díreach tar éis do eagar a bheith ar feadh na líne. Agus tú díreach de chineál ar probe nó gach eilimint atá ar fáil a iniúchadh lorg ar an láthair ar fáil. Agus chomh luath agus a fhaigheann tú amháin, scaoil tú é i ann. 

Anois, an praghas atá á íoc anois don réiteach seo cad é? Tá sraith méid seasta, agus nuair ainmneacha a chur isteach mé isteach ann, ar a laghad, i dtús báire, cad an t-am ag rith de chur isteach chun a chur ar an mac léinn ' tráth na gceist sna buicéid ceart? Big O ar cad? 

LUCHT ÉISTEACHTA: n. DAVID MALAN: Chuala mé O mór de n. Níl sé fíor. Ach beidh orainn a tease ar leith cén fáth i nóiméad ach. Cad eile a d'fhéadfadh sé a bheith? 

LUCHT ÉISTEACHTA: [inaudible] DAVID MALAN: Agus lig dom é a dhéanamh amhairc. Mar sin, Is dócha é seo an litir S. 

LUCHT ÉISTEACHTA: Tá sé ar cheann. DAVID MALAN: Tá sé ar cheann. Ceart? Is é seo an eagar, a Ciallaíonn bhfuil rochtain randamach dúinn. Agus má cheapann muid de seo mar nialas agus tá sé seo mar 25, agus tuigimid go, OH, a anseo ar mo ionchur S, Is féidir liom a thiontú cinnte S, carachtar ASCII, le líon comhfhreagrach idir nialas agus 25 agus ansin láithreach é a chur i gcás ina mbaineann sé leis. 

Ach ar ndóigh, chomh luath agus a fhaigheann mé go dtí an Is é an dara duine atá ar an t-ainm A nó B nó C sa deireadh, má tá mé úsáid as an líneacha deacra mar mo réiteach, an t-am ag rith de a chur isteach i gcás is measa ag dul i ndáiríre a chineachadh i cad? Agus raibh mé ag éisteacht anseo i gceart go luath ar. LUCHT ÉISTEACHTA: [inaudible] DAVID MALAN: Mar sin, tá sé go deimhin, aon uair amháin n tá tú sraith sonraí mór go leor. Mar sin, ar thaobh amháin, más rud é Is é do eagar mór go leor agus tá do shonraí tanaí go leor, tá tú a fháil ar an am seo leanúnach álainn. Ach chomh luath agus a thosaíonn tú ag fáil gnéithe níos mó agus níos mó, agus díreach go staitistiúil a gheobhaidh tú níos mó daoine leis an litir A mar a n-ainm nó an litir B, d'fhéadfadh sé d'fhéadfadh a bheith cineachfaidh isteach níos líneach rud éigin. Mar sin, ní foirfe leor. Mar sin, d'fhéadfadh muid a dhéanamh níos fearr? 

Bhuel, cad a bhí ár n- réiteach roimh nuair a muid ag iarraidh a bheith dinimiceas níos mó ná rud éigin cosúil le sraith a cheadaítear? LUCHT ÉISTEACHTA: [inaudible] DAVID MALAN: Cad a rinne muid isteach? Yeah. Mar sin, liosta nasctha. Bhuel, a ligean ar a fheiceáil cad a nasctha D'fhéadfadh an liosta a dhéanamh dúinn ina ionad. Bhuel, lig dom a mholadh go bhfuil muid tarraing an pictiúr mar seo a leanas. Anois tá sé seo difriúil pictiúr ó shampla as téacs éagsúla, i ndáiríre, go ag baint úsáide as i ndáiríre le sraith de mhéid 31. Agus an t-údar go simplí chinn teaghráin hash nach bhfuil bunaithe ar ainmneacha an duine, ach atá bunaithe ar a n-birthdates. Beag beann ar an mhí, figured siad má tá tú a rugadh ar an gcéad de mhí nó an 31ú de mhí, an t-údar Beidh hash bunaithe ar an luach, ionas a leagfadh an t-ainmneacha amach le beagán níos mó ná a d'fhéadfadh 26 spotaí a cheadú. Agus b'fhéidir tá sé ina aonfhoirmeach beag níos mó ná dul le litreacha aibítre, mar gheall ar ndóigh níl is dócha níos mó daoine ar fud an domhain le hainmneacha go tús le A ná cinnte roinnt litreacha eile den aibítir. Mar sin, b'fhéidir tá sé seo le beagán éide níos mó, ag glacadh leis dáileadh aonfhoirmeach de leanaí ar fud na míosa. 

Ach, ar ndóigh, tá sé seo fós neamhfhoirfe. Ceart? Táimid ag a bhfuil imbhuailtí. Daoine Il seo struchtúr sonraí fós a bhfuil an birthdate céanna ar a laghad, tá tú beag beann ar na míosa. Ach ar a bhfuil an t-údar a dhéanamh? Bhuel, tá sé cosúil ní mór dúinn le sraith ar thaobh na láimhe clé tharraingt go hingearach, ach sin amháin ealaíontóra rendition. Ní chuireann sé cuma cén treo agat tharraingt le sraith, tá sé fós le sraith. Cad é seo le sraith de réir dealraimh? 

LUCHT ÉISTEACHTA: liosta Nasctha. 

DAVID MALAN: Yeah. Breathnaíonn sé cosúil tá sé sraith de liosta nasctha. Mar sin arís, chun an pointe seo de chineál úsáid a bhaint as na struchtúir sonraí anois mar chomhábhair le níos mó réitigh suimiúil, Is féidir leat a chur go hiomlán ar bunúsach, cosúil le sraith, agus ansin rud éigin níos mó suimiúil cosúil le liosta nasctha agus fiú iad a chur le chéile isteach i fiú struchtúr sonraí níos suimiúla. Agus go deimhin, bheadh ​​sé seo freisin bheith ar a dtugtar tábla hash, trína bhfuil an eagar i ndáiríre an tábla hash, ach tá go tábla hash slabhraí, mar a déarfá, gur féidir fás nó a Laghdaigh bunaithe ar an roinnt gnéithe is mian leat a chur isteach. 

Anois, dá réir sin, cad am an rith anois? Más mian liom a chur isteach duine éigin Tá a bhfuil a lá breithe 31 Deireadh Fómhair, i gcás ina ndéanann sé nó sí ag dul? Gach ceart. Ag bun an-nuair a deir sé 31. Agus sin foirfe. Bhí an t-am i gcónaí. Ach cad má fhaighimid amach duine éigin eile a bhfuil a lá breithe é, a ligean ar féach, Deireadh Fómhair, Samhain, 31 Nollaig? Sa chás go bhfuil sé nó sí ag dul chun dul? Rud céanna. Dhá chéim cé. Sin tairiseach cé nach bhfuil sé? Gach ceart. I láthair na huaire tá sé. Ach i gcás go ginearálta, an níos mó daoine a chur againn, probabilistically, táimid ag dul a fháil imbhuailtí níos mó agus níos mó. 

Anois tá sé seo le beagán níos fearr mar go teicniúil anois d'fhéadfadh mo slabhraí a bheith i an cás is measa cé chomh fada? Má tá mé a chur isteach n daoine isteach seo níos mó struchtúr sonraí sofaisticiúla, n daoine, i gcás is measa atá sé ag dul a bheith n. Cén fáth? 

LUCHT ÉISTEACHTA: Toisc má gach duine Tá an lá breithe céanna, tá siad ag dul a bheith ag teacht ar cheann. DAVID MALAN: Perfect. D'fhéadfadh sé a bheith beagán suarach, ach fíor i gcás is measa, má tá gach duine an lá breithe céanna, mar gheall ar an ionchur atá agat, bhfuil tú ag dul a bheith acu slabhra massively fada. Agus mar sin, d'fhéadfaí tú glao sé Hais tábla, ach i ndáiríre tá sé ach liosta nasctha ollmhór ann le a lán iomlán de spás amú. Ach i gcoitinne, má glacadh againn go ar a laghad, iad breithlaethanta uniform-- agus nach bhfuil sé is dócha. Tá mé ag déanamh suas. Ach má glacadh againn, d' ar mhaithe le plé go bhfuil siad, ansin go teoiriciúil, más rud é is é seo an ionadaíocht ingearach den eagar, go maith ansin tá súil againn go bhfuil tú dul chun slabhraí go bhfuil, tá a fhios agat a fháil, thart ar an fad céanna i gcás gach ceann de Is ionann sin a lá den mhí. 

Anois, má tá 31 lá sa mhí, ciallaíonn sin mo chuid ama ag rith i ndáiríre Tá O mór de n os cionn 31, a mhothaíonn níos fearr ná líneach. Ach bhí an méid ar cheann dár gealltanais cúpla seachtain ó shin aon uair a tháinig sé chun a chur in iúl an t-am ag rith de algartaim? Just a breathnú ach amháin ag an téarma ordú ard. Ceart? Tá 31 cinnte cabhrach. Ach tá sé seo fós O mór de n. Ach ar cheann de na téamaí an fhadhb atá leagtha cúig ag dul a bheith go dtí aitheantas a thabhairt go hiomlán, asymptotically, teoiriciúil struchtúr seo sonraí aon níos fearr ná díreach liosta nasctha ceann ollmhór. Agus go deimhin, i gcás is measa, seo D'fhéadfadh tábla hash chineachadh isteach go. 

Ach ar fud an domhain fíor, le linn daoine go Macs nó ríomhairí pearsanta féin nó is cuma cad agus go bhfuil siad ag rith saol fíor bogearraí ar shonraí bhfíorshaol, a algartam bhfuil tú ag dul a fearr? An ceann a thógann céimeanna deiridh nó an ceann a thógann n arna roinnt 31 céimeanna a fháil ar roinnt píosa sonraí nó chun breathnú suas roinnt eolais? Ciallaíonn mé, go hiomlán ar an 31 a dhéanann difríocht sa saol dáiríre. Tá sé 31 uair níos tapúla. Agus tá muid daoine cinnte ag dul a thuiscint go. 

Mar sin, a bhaint amach an dichotomy ann idir iarbhír caint faoi rudaí teoiriciúil agus asymptotically a cinnte Tá luach de réir mar atá feicthe againn, ach ar fud an domhain fíor, má tá tú cúram faoi ach a dhéanamh ar an sona daonna do ionchuir ginearálta, b'fhéidir gur mhaith leat go han-mhaith a glacadh ar an bhfíric go bhfuil, yes, is é seo líneach, ach tá sé 31 uair níos tapa D'fhéadfadh ná líneach a bheith. Agus níos fearr fós, nach bhfuil againn ach a rud éigin treallach a dhéanamh cosúil le birthdate, d'fhéadfadh muid a chaitheamh beag níos mó ama agus cleverness agus smaoineamh ar cad a d'fhéadfadh linn a dhéanamh, tugadh ainm duine agus b'fhéidir a n-birthdate a chur le chéile leis na comhábhair a dhéanamh amach rud éigin go bhfuil fíor níos mó aonfhoirmeach agus níos lú jaggy, sin a labhairt ná an pictiúr le fios i láthair na huaire d'fhéadfadh sé a bheith. Conas is féidir linn a chur i bhfeidhm seo i cód? Bhuel, lig dom a mholadh go bhfuil muid ach a fháil ar iasacht ar roinnt error tá muid úsáid as cúpla uair go dtí seo. Agus mé ag dul a shainiú nód, a bhfuil arís Is téarma cineálach do ach cuid coimeádán do roinnt struchtúr sonraí. Tá mé ag dul a mholadh go Tá teaghrán ag dul i ann. Ach táimid ag dul chun tús a cur na rothaí oiliúna as anois. 

Uimh níos mó leabharlann CS50 i ndáiríre, mura mian leat é a úsáid le haghaidh do deiridh tionscadal, a bhfuil fíneáil, ach anois táimid ag dul a tharraingt ar ais ar an imbhalla agus a rá tá sé ach ina réalta Char. Mar sin, an focal tá dul chun bheith ainm an duine atá i gceist. Agus anois tá mé nasc anseo chun an nód eile ionas go mbeidh na son gach ceann de na nóid sa slabhra, d'fhéadfadh a bheith, de liosta nasctha. 

Agus anois conas is féidir Dearbhaím an tábla hash féin? Conas is féidir liom a dhearbhú an struchtúr ar fad? Bhuel, i ndáiríre, i bhfad mar a úsáidtear mé pointeoir go dtí díreach an chéad eilimint de liosta roimh, is féidir a rá mé díreach tar éis dul céanna Ní mór mé díreach tar éis a bunch leideanna leis an tábla hash ar fad a chur i bhfeidhm. Tá mé ag dul a bheith acu le sraith ar a dtugtar tábla don tábla hash. Tá sé seo ag dul a bheith ar acmhainn méid. Sin é an chaoi go leor gnéithe is féidir léi ann. Agus gach ceann de na heilimintí seo Tá eagar ag dul a bheith ina réalta nód. Cén fáth? Bhuel, in aghaidh an pictiúr, cad tá mé cur chun feidhme an tábla hash mar go héifeachtach i bhfuil an tús ach an eagar go atá againn tharraingt go hingearach, gach ceann de na cearnóga a bhfuil a Is ionann pointeoir. Go bhfuil na cinn slaiseanna trí iad go díreach null. Agus na cinn a bhfuil saigheada ag dul go dtí an gceart Tá leideanna iarbhír do nóid iarbhír, Ergo tús liosta nasctha. 

Mar sin anseo, ansin, conas a d'fhéadfadh muid tábla hash a chur i bhfeidhm go Cuireann shlabhrú ar leith. Anois is féidir linn a dhéanamh níos fearr? Gach ceart gheall mé uair dheireanach a d'fhéadfadh muid a bhaint amach am tairiseach. Agus mé cineál thug tú am tairiseach anseo, ach ansin ní dúirt i ndáiríre am tairiseach mar tá sé fós ag brath ar an iomlán roinnt gnéithe tú ag ionchur i an struchtúr sonraí. Ach is dócha a rinne muid sin. Lig dom dul ar ais go dtí an scáileán thar anseo. Ceadaigh dom an tionscadal seo chomh maith suas anseo, soiléir an scáileán, agus is dócha go rinne mé seo. Cuir Bhí mé a chur isteach an t-ainm Daven i isteach i mo struchtúr sonraí. 

Mar sin, ba mhaith liom a chur isteach ar shraith Daven isteach sa struchtúr sonraí. Cad a tharlaíonn má nach féidir liom a úsáid Hais tábla, ach úsáid mé rud éigin go bhfuil níos mó crann-mhaith cosúil le crann teaghlaigh, i gcás ina tá tú roinnt fréamh ag an nóid barr agus ansin agus duilleoga a théann síos agus amach. Cuir ansin, go bhfuil mé ag iarraidh a chur isteach Daven s i cad é liosta folamh faoi láthair. Tá mé ag dul a dhéanamh ar an méid seo a leanas: Tá mé ag dul a chruthú nód sa teaghlach crann-mhaith struchtúr sonraí go Breathnaíonn beag mar seo, gach ceann acu dronuilleoga bhfuil, a ligean le rá, do anois 26 eilimintí i sé. Agus gach ceann de na cealla sa eagar ag dul chun ionadaíocht a dhéanamh ar litir aibítir. 

Go sonrach, tá mé ag dul chun cóir leighis a Tá sé seo A, ansin B, ansin C, ansin D, an ceann seo anseo. Mar sin, tá sé seo ag dul a go héifeachtach ionadaíocht a dhéanamh ar litir D. Ach a chur isteach go léir de Daven ar ainm gá dom a dhéanamh le beagán níos mó. Mar sin, tá mé ag dul ar dtús hash, mar a déarfá. Tá mé ag dul chun breathnú ar an chéad litir i Daven ar a bhfuil ar ndóigh D, agus tá mé ag dul a leithdháileadh nód go Breathnaíonn cosúil le this-- dronuilleog mór mór go leor a d'oirfeadh an aibítir ar fad. 

Anois tá D dhéanamh. Anois tá F. D-A-V-E-N an sprioc. Mar sin, anois cad tá mé ag dul chun é seo. Chomh luath agus a thosaigh mé fógra D níl aon pointeoir ann. Tá sé luachanna truflais i láthair na huaire, nó a d'fhéadfadh liom a thúsú é a null. Ach lig dom a choinneáil ag dul le an smaoineamh a thógáil crann. Lig dom a leithdháileadh ar cheann eile de na nóid go bhfuil 26 eilimintí i sé. 

Agus tá a fhios agat cad é? Má tá sé seo ach nód i gcuimhne go Chruthaigh mé le malloc, ag baint úsáide as struct mar beidh orainn a fheiceáil go luath, Tá mé ag dul a dhéanamh this-- Tá mé ag dul a tharraingt saighead ó an rud a ionadaíocht D síos a ghabhann leis an nód nua seo. Agus anois, ar dtús leis an chéad litir in ainm Daven s, V-- D-A-V-- Tá mé ag dul chun dul ar aghaidh agus a tharraingt nód eile mar seo, trína, na heilimintí V anseo, a beidh orainn a tharraingt do whoops instance--. Ní bheidh muid a tharraingt ann. Tá sé seo ag dul chun dul anseo. 

Ansin, táimid ag dul go dtí mheas seo a bheith V. Agus ansin síos anseo táimid ag dul go dtí innéacs síos ó V i cad beidh muid ag smaoineamh E. Agus ansin ó anseo táimid ag dul go dtí dul a bheith ar cheann de na nóid anseo. Agus anois ní mór dúinn a ceist a fhreagairt. Gá dom a bhealach in iúl go táimid ag deireadh an teaghrán Daven. Mar sin, raibh mé in ann a fhágáil díreach tar null é. 

Ach cad má tá Daven ar againn ainm iomlán freisin, a Tá, mar atá againn a dúirt, Davenport? Mar sin, cad má tá Daven i ndáiríre bhfotheaghrán, réimír de shraith i bhfad níos faide? Ní féidir linn ach go buan a rá go bhfuil aon rud ag dul chun dul ann, toisc go bhféadfadh muid Riamh cuir isteach focal cosúil le Davenport i Struchtúr seo sonraí 

Mar sin, cad a d'fhéadfadh muid a dhéanamh ina ionad sin déileáil le gach ceann de na heilimintí mar b'fhéidir bhfuil dhá gnéithe taobh istigh díobh. Is é ceann pointeoir, go deimhin, mar tá mé ag déanamh. Mar sin, gach ceann de na boscaí Ní hamháin cill amháin. Ach cad má tá an barr one-- an ceann bun ar ag dul a bheith null, mar gheall ar níl aon Davenport ach go fóill. Cad a tharlaíonn má an ceann is fearr tá roinnt luach speisialta? Agus tá sé ag dul a bheith ina beagán go crua chun é a dhearadh méid seo. Ach is dócha tá sé ach le marc a sheiceáil. Seiceáil. Tá D-A-V-E-N teaghrán sa struchtúr seo sonraí. 

Idir an dá linn, más rud é go raibh mé níos mó spáis anseo, raibh mé in ann a dhéanamh P-O-R-T, agus raibh mé in ann a chur ar sheiceáil sa nód go bhfuil an litir T ag deireadh an-. Mar sin, tá sé seo le massively casta-lorg struchtúr sonraí. Agus mo scríbhneoireachta nach bhfuil cinnte cabhrú leat. Ach má bhí mé rud éigin a chur isteach eile, a mheas cad ba mhaith linn a dhéanamh. Má bhíomar ag iarraidh a chur ar David i, ba mhaith linn leanúint ar an loighic chéanna, D-A-V, ach anois ba mhaith liom pointe sa chéad eilimint ní ó E, ach ó I a ghabhann le D. Mar sin, tá dul chun bheith níos mó nóid sa gcrann. Táimid ag dul go bhfuil níos mó glaoch malloc. Ach níl mé ag iarraidh a dhéanamh praiseach iomlán ar an pictiúr. Mar sin, a ligean ar breathnú ina ionad sin ar cheann go atá curtha ar réamh-chéile mar seo le ní dot, ponc, poncanna, ach eagair amháin ghiorrú. Ach gach ceann de na nóid sa crann seo suas anseo Is ionann an thing-- céanna sraith Ray de mhéid 26. 

Nó más mian linn a bheith i ndáiríre ceart anois, cad má tá duine éigin a ainm mar apostrophe, a ligean glacadh leis go bhfuil gach nód iarbhír cosúil le 27 innéacsanna ann, ní hamháin 26. Mar sin, tá sé seo anois ag dul chun bheith ina sonraí struchtúr a dtugtar trie-- T-R-I-E. A trie, a bhfuil supposedly stairiúil ainm cliste ar feadh crann go atá optamaithe le haghaidh aisghabháil, atá ar ndóigh, Tá litrithe le I-E mar sin tá sé trie. Ach is é sin an stair an trie. 

Mar sin, Is trie seo sonraí crann-mhaith struchtúr cosúil le crann teaghlaigh go behaves deireadh thiar mar sin. Agus is é anseo ach sampla eile de bunch iomlán na n-ainmneacha daoine eile. Ach an cheist anois ar láimh an méid a bhfuil a fuarthas le linn a thabhairt isteach fhéadfaí a rá níos struchtúr sonraí casta, agus ceann amháin, frankly, úsáideann go bhfuil a lán de chuimhne. 

Mar gheall ar cé, i láthair na huaire, tá mé ach ag baint úsáide as D's pointeoir agus A agus V agus Es agus SN, Tá mé ag wasting a heck de a lán de chuimhne. Ach i gcás ina gcaithfidh mé an acmhainn amháin, Claonadh agam a a dhéanamh a fháil ar ais eile. Mar sin, má tá mé níos mó spáis a chaitheamh, cad is dócha an dóchas? Go bhfuil mé ag caitheamh níos lú cad é? LUCHT ÉISTEACHTA: Níos lú ama. DAVID MALAN: Am. Anois, cén fáth a d'fhéadfadh a bheith? Bhuel, cad é a chur isteach am, i dtéarmaí O mór anois, d'ainm ar nós Daven nó Davenport nó David? Bhuel, bhí Daven cúig céimeanna. Bheadh ​​Davenport a naoi céimeanna, mar sin bheadh ​​sé céimeanna cúpla níos mó. Bheadh ​​David cúig céimeanna chomh maith. Mar sin, tá na coincréite uimhreacha, ach surely níl ina cheangal uachtair ar an fad-ainm duine. Agus go deimhin, i an fhadhb tacair de chúig sonraíocht, táimid ag dul a mholadh go bhfuil sé rud éigin go carachtair 40-roinnt-corr. 

Réalaíoch, tá aon duine ainm infinitely fada, a bhfuil a rá go bhfuil an fad ainm nó an fad teaghrán fhéadfadh muid Tá áirithe ar staid Tá struchtúr fhéadfaí a rá cad é? Tá sé i gcónaí. Ceart? D'fhéadfadh sé a bheith ina tairiseach móra cosúil le 40-rud éigin, ach tá sé i gcónaí. Agus tá sé aon spleáchas ar cé mhéad Tá ainmneacha eile sa struchtúr seo sonraí. I bhfocail eile, má tá mé ag iarraidh a chur isteach anois Colton nó Gabriel nó Rob nó Zamyla nó Alison nó Belinda nó aon ainmneacha eile ón bhfoireann i na sonraí seo struchtúr, is é an t-am ag rith de chur isteach ainmneacha eile ag dul a bheith ar chor ar bith tionchar ag cé mhéad gnéithe eile i struchtúr sonraí cheana féin? Níl sé. Ceart? Mar gheall orainn ag baint úsáide as go héifeachtach tábla hash il-ciseal. Agus an t-am ag rith de aon cheann de na hoibríochtaí sin ag brath ní ar líon na n- heilimintí atá sa struchtúr sonraí nó atá ag dul sa deireadh a bheith sa struchtúr sonraí, ach ar fhad ar cad go sonrach? 

An teaghrán á a cuireadh isteach, a dhéanann a dhéanamh seo tairiseach asymptotically O mór time-- amháin. Agus frankly, ach i an saol fíor, seo Ciallaíonn isteach Bíonn an t-ainm Daven s cosúil le cúig céimeanna, nó Davenport naoi céimeanna, nó David cúig céimeanna. Sin go leor darn amanna rith beag. Agus, go deimhin, go bhfuil an- rud maith, go háirithe nuair a nach bhfuil sé ag brath ar an iomlán líon na n-eilimintí i ann. Mar sin, conas a d'fhéadfadh muid a chur i bhfeidhm seo de chineál ar struchtúr i cód? Tá sé beagán níos mó casta, ach fós tá sé ach i bhfeidhm bloic thógála bunúsach. Tá mé ag dul a ath-shainmhíniú Linn nód mar a leanas: bool dtugtar word-- agus tá sé seo d'fhéadfadh a bheith ar a dtugtar rud ar bith. Ach léiríonn an bool cad a tharraing mé mar marc a sheiceáil. Is ea. Is é seo an deireadh teaghrán sa struchtúr seo sonraí. 

Agus, ar ndóigh, an réalta nód níl a thagraíonn do leanaí. Agus, go deimhin, ach is maith crann teaghlaigh, tú Bheadh ​​a mheas an nóid atá crochta amach ar bun ar roinnt tuismitheoir eilimint a bheith leanaí. Agus mar sin go bhfuil na páistí ag dul go dtí a bheith ina sraith de 27, an ceann 27ú díreach a bheith do apostrophe. Táimid ag dul a shórtáil de chás speisialta sin. Mar sin, is féidir leat a bheith áirithe ainmneacha le huaschamóga. B'fhéidir gur chóir go fiú fleiscín dul i ann, ach beidh tú a fheiceáil i tacar lch 5 cúram againn ach faoi ​​litreacha agus uaschamóg. 

Agus ansin conas a dhéanann ionadaíocht a dhéanamh leat an struchtúr sonraí féin? Conas a dhéanann tú ionadaíocht a dhéanamh ar an fhréamh den trie, mar a déarfá? Bhuel, díreach cosúil le liosta nasctha, tú gá le pointeoir chuig an chéad eilimint. Le trie gá duit ach amháin pointeoir chun an fhréamh an trie. Agus ó ann is féidir leat Hash do bhealach síos níos doimhne agus níos doimhne le gach nód eile sa struchtúr. Mar sin, ach leis is féidir ionadaíocht againn go struct. 

Anois Meanwhile-- Ó, ceist. 

LUCHT ÉISTEACHTA: Cad focal bool? 

DAVID MALAN: Tá focal bool ach an incarnation C an méid a thuairiscítear mé sa bhosca seo anseo, nuair Thosaigh mé ag scoilteadh gach ceann de na eilimintí eagar isteach dhá phíosa. Is é ceann pointeoir leis an nód seo chugainn. Tá an eile a bheith rud éigin cosúil le ticbhosca a rá yes, níl a focal Daven go deireadh anseo, toisc nach bhfuil muid ag iarraidh, i láthair na huaire, Dave. 

Cé go bhfuil Dave ag dul a bheith ina focal dlisteanach, ní sé san trie go fóill. Agus nach bhfuil D focal. Agus nach bhfuil D-A focal nó ainm. Mar sin, an marc a sheiceáil Léiríonn ach aon uair amháin tú bhuail é an nód an cosán roimhe de charachtair i ndáiríre ar shraith go atá tú a chur isteach. Mar sin, sin uile an bool níl dhéanamh dúinn. 

Ceisteanna ar bith eile ar iarracht? Yeah. 

LUCHT ÉISTEACHTA: Cad é an forluí? Cad a tharlaíonn má tá tú Dave agus Daven? DAVID MALAN: Perfect. Cad a tharlaíonn má tá tú Dave agus Daven? Mar sin, má táimid a chur isteach, a rá leasainm, do David-- Dave-- D-A-V-E? Tá sé seo i ndáiríre Super simplí. Mar sin, táimid ag dul ach a ghlacadh ceithre chéim. D-A-V-E. Agus cad is gá dom a a dhéanamh nuair a bhuail mé go ceathrú nód? Just a ag dul a sheiceáil. Táimid go maith chun dul cheana féin. Arna dhéanamh. Ceithre céimeanna. Am Constant asymptotically. Agus anois tá muid in iúl go bhfuil an dá Dave agus tá Daven teaghráin i struchtúr. Mar sin, nach bhfuil fadhb. Agus faoi deara conas an láthair de Daven ní raibh a dhéanamh a ghlacadh ar bith níos mó ama nó níos lú am le haghaidh Dave agus vice versa. 

Mar sin, cad eile is féidir linn a dhéanamh anois? Táimid tar éis a úsáidtear an meafar roimh de tráidirí a ionadaíonn éigin. Ach casadh sé amach go bhfuil a Tá Stack na tráidirí iarbhír thaispeántach sonraí teibí eile type-- struchtúr sonraí ar leibhéal níos airde go bhfuil ag an deireadh an lae ach cosúil le sraith nó liosta nasctha nó rud éigin níos mundane. Ach tá sé ina níos suimiúla coincheap coincheapúil. A chairn, mar seo tráidire anseo i Mather, ar a dtugtar de ghnáth ach that-- Stack. 

Agus sa chineál seo de struchtúr sonraí Tá tú dhá operations-- tá ceann agat bhrú a dtugtar le haghaidh ag cur rud éigin ar an chairn, cosúil le cur tráidire eile ar ais ar bharr an chairn. Agus ansin pop, rud a chiallaíonn tú a chur ar an tráidire thalamh topmost. Ach cad eochair faoi é Stack go é a fuair an tréith aisteach. Mar an bhfoireann halla bia iad rearranging na tráidirí le haghaidh an béile seo chugainn, cad atá ag dul a bheith fíor faoi conas mac léinn idirghníomhú le struchtúr seo sonraí? LUCHT ÉISTEACHTA: Tá siad ag dul a pop aon uaire. DAVID MALAN: Tá siad ag dul go dtí pop amach amháin, tá súil againn an barr. Seachas sin tá sé ach de chineál ar dúr chun dul go léir ar an mbealach go bun. Ceart? Ní dhéanann an struchtúr sonraí a cheadú i ndáiríre tú a grab an tráidire bun ar a laghad, go héasca. Mar sin, níl sé seo aisteach maoin a Stack go bhfuil an mhír dheiridh i ag dul a bheith ar an chéad amach amháin. Agus glaoch eolaithe ríomhaireachta LIFO-- seo go deireanach sa, an chéad amach. Agus sé i ndáiríre an bhfuil hiarratais suimiúil. Níl sé gá chomh soiléir le roinnt daoine eile, ach is féidir é, go deimhin, a bheith úsáideach, agus is féidir é, go deimhin, a chur i bhfeidhm i cúpla bealaí éagsúla. 

Mar sin amháin, agus ar ndóigh,, a ligean dom gan Léim isteach sin. A ligean ar é seo a dhéanamh ina ionad. A ligean ar breathnú ar cheann go bhfuil beagnach an smaoineamh céanna, ach tá sé ina níos cothroime beag. Ceart? Má tá tú ceann de na buachaillí lucht leanúna nó cailíní go maith i ndáiríre táirgí Apple agus dhúisigh tú suas ag 03:00 go dtí an líne suas go éigin siopa a fháil ar an iPhone is déanaí, tá tú d'fhéadfadh a bheith ciúáilte suas mar seo. 

Anois tá scuaine ainmnithe an-aon ghnó. Tá sé ar líne mar níl roinnt cothroime dó. Ceart? Bheadh ​​sé de chineál ar sucked má tá tú fuair ann ar dtús ag an Store Apple ach go bhfuil tú go héifeachtach leis an bottommost tráidire gheall ar na fostaithe Apple ansin pop an duine deireanach a fuair i ndáiríre ag teacht. Mar sin, stacks agus scuainí, cé feidhmiúil tá siad de chineál ar an same-- tá sé a bhailiú díreach seo na n-acmhainní go tá dul chun fás agus shrink-- ag an ngné cothroime dó, ar a laghad, ar fud an domhain fíor, i gcás na n-oibríochtaí a fheidhmiú tú Tá go bunúsach difriúil. A stack-- scuaine rather-- deirtear go bhfuil dhá oibríochtaí: n scuaine agus d scuaine. Nó is féidir leat glaoch orthu aon líon na rudaí. Ach ba mhaith leat ach a ghabháil an nóisean go bhfuil duine ag cur agus tá sé ar cheann a dhealú ar deireadh thiar. 

Anois, thíos an cochall, idir an chairn agus d'fhéadfaí scuaine a chur i bhfeidhm conas? Ní féidir linn dul isteach ar an gcód sé mar gheall ar an leibhéal níos airde Tá smaoineamh saghas níos soiléire. Ciallaíonn mé, cad a dhéanann daoine a dhéanamh? Má tá mé an chéad duine ag an Apple Store agus is é seo an doras tosaigh, Tá a fhios agat, tá mé ag dul chun seasamh anseo. Agus an duine seo chugainn dul chun seasamh anseo. Agus an duine seo chugainn dul chun seasamh anseo. Mar sin, cad a struchtúr sonraí lends féin chun scuaine? 

LUCHT ÉISTEACHTA: A scuaine. DAVID MALAN: Bhuel, scuaine. Cinnte. Cad eile? 

LUCHT ÉISTEACHTA: Tá liosta nasctha. 

DAVID MALAN: A nasctha liosta d'fhéadfaí tú a chur i bhfeidhm. Agus is é liosta nasctha deas mar sin Is féidir é ag fás treallach fada le hais ar a bhfuil roinnt ar líon seasta de na daoine sa siopa. Ach b'fhéidir líon seasta na n-áiteanna atá dlisteanach. Toisc má tá siad ach cosúil le 20 iPhones ar an gcéad lá, b'fhéidir is gá iad ach le sraith de mhéid 20 chun ionadaíocht a dhéanamh go scuaine, a ach a rá anois nuair a thosaíonn muid ag caint faoi ​​na fadhbanna ar leibhéal níos airde, is féidir leat a chur i bhfeidhm in aon roinnt bealaí. Agus níl is dócha ag dul díreach a a bheith ina trádáil as i spás agus am nó díreach i do chastacht cód féin. 

Cad mar gheall ar Stack? Bhuel, Stack, atá feicthe againn freisin D'fhéadfadh a bheith díreach ar na tráidirí. Agus d'fhéadfadh tú a chur i bhfeidhm seo eagar. Ach ag pointe áirithe má úsáideann tú eagar, cad atá ar siúl chun a tharlóidh do na tráidirí bhfuil tú ag iarraidh a chur síos? Gach ceart. Tá tú ag dul ach amháin maidir le a bheith in ann dul chomh hard. Agus is dóigh liom i Mather tá siad cuasaithe iarbhír sa oscailt. Mar sin go deimhin, tá sé beagnach cosúil Mather ag baint úsáide as le sraith de mhéid seasta, mar is féidir leat ach oiriúnach oiread tráidirí sa oscailt i an balla síos thíos ndaoine knees. Agus mar sin d'fhéadfadh a bheith sin a bheith le sraith, ach d'fhéadfadh muid a chur i bhfeidhm go cinnte níos ginearálta le liosta nasctha. 

Bhuel, cad faoi struchtúr eile sonraí? Lig dom a tharraingt suas amháin eile amhairc anseo. Rud éigin cosúil le conas mar gheall ar an gceann seo anseo? Cén fáth a d'fhéadfadh sé a bheith úsáideach a bheith acu nach bhfuil rud éigin mar mhaisiúil mar trie, a chonaic bhí againn ar na nóid an-leathan, Tá gach ceann acu in eagar? Ach cad má dhéanann muid rud éigin níos mó simplí, cosúil le crann teaghlaigh scoile d'aois, gach ceann de a bhfuil nóid anseo bhfuil ach a stóráil ar uimhir. In ionad a ainm nó de shliocht bhfuil ach a stóráil ar roinnt mar seo. 

Bhuel, an béarlagair a úsáid againn i Tá struchtúir sonraí araon Déanann agus crainn, más rud é, arís is trie, ach ceann amháin a bhfuil a nóid iad eagair, tá sé fós an méid a d'fhéadfadh tú úsáid ón scoil ghrád nuair a rinne tú ag teaghlach duilleoga tree-- agus an fhréamh an chrainn agus leanaí ar an tuismitheoir agus deirfiúracha sin. Agus d'fhéadfadh muid a chur i bhfeidhm crann, mar shampla, chomh simplí agus is sin. A crann, má tá sé mar nód, ar cheann de na ciorcail go bhfuil uimhir, níl sé ag dul a bheith acu aon pointeoir, ach dhá. Agus chomh luath agus a cuir tú an dara pointeoir, tú Is féidir i ndáiríre a dhéanamh anois a shórtáil Sonraí dhá-thoiseach struchtúir i gcuimhne. I bhfad cosúil le dhá-thoiseach eagar, is féidir leat Tá de chineál ar dhá-thoiseach liostaí nasctha ach na cinn a leanann patrún i gcás ina níl aon timthriallta. Tá sé fíor crann le ceann amháin bhealach seantuismitheoir suas anseo agus ansin roinnt tuismitheoirí agus leanaí agus chlann clainne agus mór-chlann clainne. agus mar sin de. 

Ach cad atá i ndáiríre néata faoi seo freisin, ach a tease tú le beagán de chód, athchúrsáil cuimhne ó awhile ar ais, trína scríobhann tú feidhm a glaonna féin. Is deis álainn rud éigin a chur i bhfeidhm cosúil le athchúrsáil, mar a mheasann seo. 

Seo crann. Agus bhí mé ina anal beag leis an gcaoi Chuir mé na slánuimhreacha ar an tsráid. Mar sin, an oiread sin go bhfuil sé ar leith name-- crann cuardaigh dénártha. Anois, tá muid chuala dénártha cuardaigh, ach is féidir leat oibrigh siar as an rud ar an t-ainm? Cad é an patrún ar conas mé a cuireadh isteach leis na slánuimhreacha isteach sa gcrann? Níl sé treallach. Níl roinnt patrún. Yeah. 

LUCHT ÉISTEACHTA: na cinn níos lú ar an taobh clé. 

DAVID MALAN: Yeah. Tá na cinn níos lú ar an taobh clé. Tá na cinn Bigger ar dheis. Den sórt sin go bhfuil ráiteas fíor a Is tuismitheoir níos mó ná a leanbh ar chlé, ach níos lú ná a leanbh ceart. Agus go n-aonar is fiú sainmhíniú bhéal athchúrsach mar is féidir leat iarratas a dhéanamh go loighic chéanna le gach nód agus íochtair sé ach amach, cás bonn má tá tú Beidh, nuair a bhuail tú ar cheann de na na duilleoga, mar a déarfá, i gcás ina bhfuil cead aon leanaí a thuilleadh. 

Anois, conas a d'fhéadfá a fháil ar an uimhir 44? Ba mhaith leat tosú ag an fhréamh agus a rá, hm. Níl 44 55 Mar sin, ba mhaith liom dul ceart nó ar mhaith liom a dul ar chlé? Bhuel, ar ndóigh ba mhaith leat dul ar chlé. Agus mar sin tá sé díreach cosúil leis an teileafón Mar shampla leabhar i cuardaigh dénártha níos ginearálta. Ach táimid chun feidhme anois beagán níos dinimiciúil ná mar a d'fhéadfadh eagar a cheadú. Agus go deimhin, más mian leat chun breathnú ag an cód, ar an gcéad amharc cinnte. Breathnaíonn sé cosúil le bunch iomlán de línte. Ach tá sé go hálainn simplí. Más mian leat chun feidhm a chur i bhfeidhm ar a dtugtar cuardaigh arb é is cuspóir sa saol Tá a chuardach le haghaidh luach cosúil le n, slánuimhir, agus go bhfuil tú ag rith i pointer-- amháin pointeoir leis an nód na fréamhacha, in áit, den crann as a Is féidir leat rochtain a fháil ar gach rud eile, faoi ​​deara cé chomh straightforwardly is féidir leat a chur i bhfeidhm ar an loighic. Má tá crann nialasach, is léir nach bhfuil sé ann. A ligean ar ais ach bréagach. Ceart? Má láimh tú sé rud ar bith, níl rud ar bith ann. 

Eile, más rud é go n níos lú ná arrow crann n-- arrow anois n, cuimhne thugamar Super go hachomair ar an lá eile, agus ciallaíonn sin go díreach de-tagartha an pointeoir agus féach ar an réimse ar a dtugtar n. Mar sin, ciallaíonn sé dul ann agus ag féachaint ar an réimse ar a dtugtar n. Mar sin, má n, tá an luach a bhfuil tú ag a tugadh, níos lú ná an luach sa slánuimhreach crainn, nuair is mian leat dul? Chun na láimhe clé. 

Mar sin, faoi deara an athchúrsáil. Tá mé ag returning-- ní fíor. Níl sé bréagach. Tá mé ag filleadh ar cibé an freagra Is as glaoch go féin, ag dul ina n arís, atá iomarcach, ach cad beagán difriúil anois? Conas is mé ag déanamh an fhadhb níos lú? Tá mé ag dul i mar an dara argóint, nach bhfuil an fhréamh an chrainn, ach an leanbh clé sa chás seo. Mar sin, tá mé ag dul sa pháiste clé. 

Idir an dá linn, más rud é go n níos mó ná an nód Táim ag lorg faoi láthair ag, Cuardach mé ar thaobh na láimhe deise. Eile, más rud é nach bhfuil an crann nialasach, agus más rud é nach bhfuil an eilimint ar an taobh clé agus nach bhfuil sé leis an gceart, cad é iontach an cás? Táimid tar éis a fuair i ndáiríre an nód i ceist, agus mar sin táimid ar ais fíor. 

Mar sin, tá muid ach scríobtha an dromchla anois ar roinnt de na struchtúir sonraí. I fhadhb a leagtar cúig Feicfidh tú iniúchadh a dhéanamh ar na fós a thuilleadh, agus beidh tú a thabhairt do dhearadh rogha ar conas a théann faoi seo. Cad ba mhaith liom buíochas a thabhairt i gcrích ar bhfuil ach 30 an dara teaser ar cad awaits an tseachtain seo chugainn agus ina dhiaidh. 

Mar begin-- muid buíochas le Dia d'fhéadfadh tú think-- ár trasdul mall ó shaol an C agus níos ísle Sonraí i bhfeidhm ar leibhéal, ar domhan inar féidir linn a ghlacadh le haghaidh a deonaíodh go bhfuil duine éigin eile ar deireadh na sonraí seo i bhfeidhm struchtúir dúinn, agus beidh muid tús a chur chun tuiscint a fháil ar Ciallaíonn saol fíor a chur i bhfeidhm cláir bunaithe ar an ngréasán agus láithreáin ghréasáin níos ginearálta agus chomh maith leis an t-urrús an- himpleachtaí go atá againn ach tús curtha le scratch an dromchla. Seo an méid a fanacht linn sna laethanta atá le teacht. 

[VIDEO Archives] 

Tháinig -He le teachtaireacht, le prótacal ar fad a chuid féin. Tháinig sé go dtí ar domhan de éadrócaireach ballaí dóiteáin, ródairí uncaring, agus contúirtí i bhfad níos measa ná bás. Tá sé go tapa. Tá sé láidir. Tá sé TCP / IP, agus fuair sé do sheoladh. "Laochra ar an Idirlíon." [END VIDEO Archives] DAVID MALAN: Ag teacht an tseachtain seo chugainn. Leanfaimid orainn tú a fheiceáil ansin. [VIDEO Archives] -agus Anois, "Smaointe Deep" ag Daven Farnham. -David Thosaíonn i gcónaí léachtaí le, "Gach ceart." Cén fáth nach bhfuil, "Seo an réiteach chun an fhadhb a leagtar seachtaine seo " nó "Táimid ag tabhairt ar fad agat ar A?" [Gáire] [END VIDEO Archives]