Cainteoir 1: Ceart go leor, mar sin tá sé seo CS50 é seo an deireadh seachtaine cúig. Agus cuimhne go uair dheireanach linn a Thosaigh ag féachaint ar an sonraí fancier struchtúir a thosaigh a réiteach fadhbanna, a thosaigh a thabhairt isteach fadhbanna nua, ach an eochair seo bhí an saghas snáithiú go bhfuil muid Thosaigh a dhéanamh ó nód dtí nód. Mar sin, tá sé seo ar ndóigh liosta nasctha ina n-aonar. Agus ag nasctha ina n-aonar, Ciallaíonn mé níl ach ceann amháin snáithe idir gach ceann de na nóid. Casadh amach féidir leat a dhéanamh fancier rudaí cosúil le liostaí nasctha doubly ina bhfuil tú saighead dul sa dá threo, a Is féidir le cabhrú le éifeachtúlachtaí áirithe. Ach réiteach seo an fhadhb? Cén fhadhb raibh seo a réiteach? Cén fáth go raibh muid cúram ar an Luan? Cén fáth, go teoiriciúil, raibh muid cúram ar an Luan? Cad a dhéanann sé? 

LUCHT ÉISTEACHTA: Is féidir linn Athraigh dinimiciúil é. 

Cainteoir 1: OK, mar sin is féidir linn dinimiciúil Athraigh é. Maith thú dá de tú. Mar sin, is féidir leat Athraigh dinimiciúil seo struchtúr sonraí, cé go le sraith, chun cuimhne, caithfidh tú a fhios priori cé mhéad spás is mian leat agus más gá tú níos beag spás, tá tú de chineál ar as luck. Tá tú a chruthú sraith iomlán nua. Tá tú a bogadh ar fad do sonraí ó cheann go ceann eile, sa deireadh saor in aisce leis an eagar d'aois más féidir leat, agus ansin dul ar aghaidh. A díreach mothaíonn an-chostasach agus an- mí-éifeachtach, agus go deimhin is féidir é a. Ach nach bhfuil sé seo go léir go maith. Íocaimid ar phraghas, bhí an méid amháin de na praghsanna níos soiléire a chuirimid íoc trí úsáid a bhaint liosta nasctha? 

LUCHT ÉISTEACHTA: Ní mór dúinn úsáid a bhaint as spás dúbailte do gach ceann. Cainteoir 1: Yeah, sin ní mór dúinn ar a laghad dhá uair chomh spás i bhfad. Go deimhin, shíl mé an pictiúr ar fiú beag míthreorach, mar gheall ar IDE CS50 i go leor de nua-aimseartha ríomhairí, pointeoir nó seoladh Níl i ndáiríre ceithre bytes. Tá sé an-minic ar na lá ocht bytes, a ciallaíonn an bun an chuid is mó dronuilleoga ann i ndáiríre Tá de chineál ar dhá oiread mór le cad tá mé a tharraingt, rud a chiallaíonn go bhfuil tú ag baint úsáide as trí huaire chomh mhéad spás mar a d'fhéadfadh muid a bheith ar shlí eile. Anois ag an am céanna, tá muid fós ag caint bytes, ceart? Ní bhíonn muid ag caint gá go meigibheart nó ghigibheart, mura rud é na sonraí a fháil struchtúir móra. 

Agus mar sin lá atá inniu ann tús a chur orainn a mheas conas a d'fhéadfadh muid a iniúchadh a dhéanamh ar na sonraí níos éifeachtaí más rud é i Go deimhin faigheann na sonraí níos mó. Ach a ligean ar iarracht a caighdeánaigh na hoibríochtaí ar dtús gur féidir leat a dhéanamh ar na cineálacha struchtúir sonraí. Mar sin, rud éigin cosúil le nasctha Tacaíonn an liosta ginearálta Is maith le hoibríochtaí a scriosadh, cuir isteach, agus cuardach a. Agus cad féidir liom a chiallaíonn ag? Ciallaíonn sin go díreach de ghnáth, má tá daoine ag baint úsáide as an liosta nasctha, siad nó duine éigin eile a chur i bhfeidhm Tá feidhmeanna cosúil le scriosadh, cuir isteach, agus cuardach a dhéanamh, ionas gur féidir leat a dhéanamh i ndáiríre rud éigin úsáideach leis an struchtúr sonraí. Mar sin a ligean ar ghlacadh le breathnú tapaidh ar conas a d'fhéadfadh muid a chur i bhfeidhm roinnt cód le haghaidh liosta nasctha mar seo a leanas. 

Mar sin, tá sé seo ach cuid cód C, ní fiú clár iomlán go bhfuil mé i ndáiríre bhuailtí suas go tapa. Níl sé ar líne i ndáileadh cód, mar ní bheidh sé ar siúl i ndáiríre. Ach faoi deara Tá mé díreach tar éis le nóta tráchta a dúirt, ponc dot ponc, tá rud éigin ann, dot ponc ponc, rud éigin ann. Agus a ligean ar breathnú díreach ar cad iad na codanna juicy. Mar sin, ar líne trí, a thabhairt chun cuimhne go bhfuil sé seo anois beartaithe táimid ag dhearbhú nód caite am, ar cheann de na cuspóirí sin dronuilleogach. Tá sé ina slánuimhir go beidh muid ag glaoch N, ach d'fhéadfadh muid a ghlaoch air rud ar bith, agus ansin le réalta nód struct dtugtar chugainn. Agus díreach a bheith soiléir, go bhfuil an dara líne, ar líne sé, cad é sin? Cad atá á dhéanamh sé dúinn? Mar tá sé cinnte níos mó cryptic ná ár athróga mar is gnách. 

LUCHT ÉISTEACHTA: Déanann sé é a aistriú níos mó ná aon. 

Cainteoir 1: Déanann sé é a aistriú níos mó ná aon. Agus a bheith níos cruinne, beidh sé a stóráil an seoladh an nód go gceist a bheith semantically aice leis é, ceart? Mar sin, níl sé ag dul go dtí gá go bogadh rud ar bith. Tá sé seo ag dul díreach a luach a stóráil, a bhfuil ag dul a bheith ar an seoladh de nód éigin eile, agus sin an fáth atá againn a dúirt struct réalta nód, an réalta á thaispeáint pointeoir nó seoladh. OK, mar sin anois má glacadh tú go bhfuil muid an N fáil dúinn, agus a ligean ar glacadh leis go bhfuil duine éigin eile a cuireadh isteach a bunch iomlán de slánuimhreacha i liosta nasctha. Agus is é sin an liosta nasctha léirigh ag pointe éigin athróg liosta a dtugtar go bhfuil ritheadh ​​i anseo mar pharaiméadar, conas is féidir liom dul faoi ag teacht Cuardach 14 a chur i bhfeidhm? I bhfocail eile, má tá mé a chur i bhfeidhm fheidhm arb é is cuspóir sa saol Is a ghlacadh ina slánuimhir agus ansin an ag tosú de liosta nasctha, go bhfuil pointeoir leis an liosta nasctha. Cosúil dtús, a cheapann liom David bhí ár oibrithe deonacha ar an Luan, bhí sé ag cur in iúl ag an liosta iomlán nasctha, tá sé mar cé go bhfuil muid ag dul thar David in mar ár argóint anseo. Conas is féidir linn dul faoi traversing an liosta seo? Bhuel, casadh sé amach, áfach, cé Tá leideanna réasúnta nua anois dúinn, Is féidir linn é seo a réasúnta díreach é. 

Tá mé ag dul chun dul ar aghaidh agus dhearbhú athróg sealadach a de réir an ghnáis ag dul díreach ar a dtabharfar pointeoir, nó PTR, ach d'fhéadfaí tú glaoch air aon rud is mian leat. Agus mé ag dul a thúsú sé leis an tús an liosta. Mar sin, is féidir leat de chineál ar smaoineamh ar seo mar dom an múinteoir an lá eile, de chineál ar dírithe ar dhuine i measc ár ndaoine mar oibrithe deonacha. Mar sin, tá mé athróg sealadach go ach ag cur in iúl ag an rud céanna go bhfuil ár ainmnithe coincidentally oibrithe deonacha David bhí ag cur in iúl freisin. Anois cé go bhfuil pointeoir Ní null, mar gheall ar cuimhne is é sin null roinnt luach fairtheora speisialta an demarcates deireadh an liosta, mar sin cé nach bhfuil mé ag cur in iúl ag an talamh cosúil ár deonacha seo caite Bhí, a ligean ar dul ar aghaidh agus a dhéanamh ar an méid seo a leanas. Má pointer-- agus anois mé chineál ar mian a dhéanamh cad a rinne muid leis an mac léinn structure-- má pointeoir ponc chugainn equals-- in áit, má bhíonn pointeoir dot N ionann an athróg N, an argóint go bhfuil rite i, ansin ba mhaith liom a dul ar aghaidh agus a rá ar ais fíor. Tá mé aimsithe an líon N taobh istigh de ar cheann de na nóid ar mo liosta nasctha. Ach an ponc a thuilleadh ag obair sa chomhthéacs seo, mar gheall ar pointeoir, PTR é, go deimhin, ar pointeoir, aitheasc, is féidir linn i ndáiríre iontach úsáid ar deireadh píosa error gur de chineál ar a dhéanann ciall iomasach agus ar ndóigh, úsáid saighead anseo, rud a chiallaíonn dul ó seoladh sin go dtí an tslánuimhir ann i. Mar sin tá sé an-chosúil i spiorad don oibreoir ponc, ach toisc nach bhfuil pointeoir pointeoir agus ní struct iarbhír féin, linn a úsáid ach an arrow. 

Mar sin, má tá an nód atá ann faoi láthair go bhfuil mé, an athróg sealadach, táim ag cur in iúl ag nach N, cad is féidir liom ag iarraidh a dhéanamh? Bhuel, le mo deonacha go raibh muid anseo an lá eile, más rud é nach bhfuil mo chéad duine an ceann mé Ba mhaith, agus b'fhéidir nach bhfuil an dara duine an ceann is mian liom, agus an tríú, mé Ní mór a choinneáil go fisiciúil ag gluaiseacht. Cosúil le conas is féidir liom céim trí liosta? Nuair a bhí againn le sraith, tú díreach cosúil rinne mé móide móide. Ach sa chás seo, suffices sé a pointeoir, faigheann, pointeoir a dhéanamh, seo chugainn. I bhfocail eile, an réimse seo chugainn Is cosúil gach ceann de na lámha ar chlé go bhfuil ár deonacha ar an Luan Bhí ag baint úsáide as a chur in iúl ar nód éigin eile. Bhí na a gcomharsana chugainn. 

Mar sin, más mian liom a chéim tríd an liosta seo, Ní féidir liom a dhéanamh díreach tar éis mé móide móide níos mó, Tá mé ina ionad sin a rá I, pointeoir, ag dul a comhionann is cuma cad é an réimse seo chugainn, Tá, tá an réimse seo chugainn an réimse seo chugainn, tar éis gach ceann de na lámha ar chlé go raibh muid ar an stáitse dírithe le roinnt luachanna ina dhiaidh sin. Agus má fhaigheann mé tríd go atriall ar fad, agus ar deireadh, bhuail mé null nach bhfuil Fuair ​​N fóill, mé ar ais díreach tar bréagach. Mar sin arís, go léir go bhfuil muid ag déanamh anseo, de réir an pictiúr nóiméad ó shin, ag tosú ag cur in iúl ag an ag tosú ar an liosta dócha. Agus ansin mé ag seiceáil go bhfuil, an luach Táim ag lorg cothrom le naoi? Má tá, ar ais mé fíor agus tá mé a rinneadh. Mura bhfuil, mé suas chun dáta mo lámh, Aka pointeoir, a chur in iúl ag suíomh an arrow chugainn, agus ansin an arrow suíomh seo chugainn, agus an chéad cheann eile. Tá mé ag simplí ag siúl tríd an eagar. 

Mar sin arís, a cares? Cosúil cad é seo chomhábhar do? Bhuel, chun cuimhne go thugamar isteach an nóisean de Stack, a Is sonraí teibí cineál a mhéid a bhfuil sé Ní rud C, nach bhfuil sé an rud CS50, tá sé ina smaoineamh teibí, an smaoineamh seo de rudaí a cruachta ar bharr a chéile is féidir a chur i bhfeidhm i bunches de bhealaí éagsúla. Agus bhí bealach amháin mhol muid leis sraith, nó le liosta nasctha. Agus casadh sé amach go canonically, a Tacaíonn Stack ar a laghad dhá oibríochtaí. Agus tá na focail Buzz bhrú, go rud éigin a bhrú isteach ar an chairn, cosúil le tráidire nua sa halla bia, nó pop, rud a chiallaíonn a bhaint as an mbarr an tí tráidire as an chairn sa bia halla, agus ansin b'fhéidir roinnt oibríochtaí eile chomh maith. Mar sin, conas a d'fhéadfadh muid a shainiú ar an struchtúr go bhfuil muid ag iarraidh anois Stack? 

Bhuel, ní mór dúinn gach ceann de na riachtanach error ar fáil dúinn i C. rá liom, a thabhairt dom sainmhíniú cineál a struct taobh istigh de Stack, Tá mé ag dul a rá go bhfuil sraith, de bunch iomlán na n-uimhreacha agus ansin méid. Mar sin, i bhfocail eile, más mian liom a chur i bhfeidhm seo i cód, lig dom dul agus díreach de chineál ar tharraingt cad é seo a rá. Mar sin, tá sé seo ag rá, a thabhairt dom struchtúr a fuair sraith, agus níl a fhios agam cad é cumas, tá sé cosúil le roinnt tairiseach go Tá mé sainithe in áiteanna eile, agus go bhfuil fíneáil. Ach is dócha tá sé ach ceann amháin, dhá, trí, ceithre, cúig. Dá bhrí sin tá cumas 5. Seo gné taobh istigh de mo Beidh struchtúr a dtugtar uimhreacha. Agus ansin is gá mé amháin athróg eile cosúil ar a dtugtar méid sin i dtús báire mé ag dul a leagan síos tá sé initialized go nialas. Má níl aon rud i is é an chairn, méid náid, agus tá sé luachanna truflais i líon. Tá mé aon smaoineamh cad atá i ann ach go fóill. 

Mar sin, más mian liom a bhrú rud éigin isteach ar an chairn, Is dócha Iarraim an bhrú fheidhm, agus Rá liom a bhrú 50, cosúil leis an uimhir 50, i gcás ina mbeadh tú a mholadh Tharraingt mé é sa eagar? Níl cúig freagraí is féidir éagsúla. Sa chás go bhfuil tú ag iarraidh a bhrú ar an uimhir 50? Má tá an sprioc anseo, arís, glaoigh ar an bhrú fheidhm, pas i argóint de 50, i gcás ina is féidir liom a chur air? Cúig possible-- 20% faill de guessing i gceart. Yes? 

LUCHT ÉISTEACHTA: Far ceart. 

Cainteoir 1: Far ceart. Tá seans 25% ann anois de guessing i gceart. Mar sin, bheadh ​​a bheith i ndáiríre fíneáil. De réir an ghnáis, beidh mé a rá le sraith, ba mhaith linn tús a chur go ginearálta ar thaobh na láimhe clé, ach d'fhéadfadh muid cinnte tús a chur ag an ceart. Mar sin, bheadh ​​an spoiler anseo tá mé is dócha dul a tharraingt ar thaobh na láimhe clé, díreach cosúil i sraith gnáth áit Tús mé ag dul ó chlé go deas. Ach más féidir leat smeach an uimhríocht, fíneáil. Tá sé díreach nach bhfuil traidisiúnta. OK, is gá dom a dhéanamh amháin níos mó ar athrú cé. Anois go bhfuil mé rud éigin a bhrú isteach ar an chairn, cad eile? 

Gach ceart, tá mé chun incrimint an méid. Mar sin, lig dom dul ar aghaidh agus díreach thabhairt cothrom le dáta seo, a bhí nialas. Agus ina ionad sin anois, tá mé ag dul a chur i luach amháin. Agus anois is dócha a bhrú mé eile uimhir isteach ar an chairn, cosúil le 51. Bhuel, tá mé a dhéanamh amháin níos mó athrú, a bhfuil suas go dtí an méid a dó. Agus ansin is dócha a bhrú mé ceann níos mó uimhir isteach ar an chairn cosúil le 61, anois is gá dom a thabhairt cothrom le dáta ar an méid amháin níos mó am, agus a fháil ar an luach 3 leis an méid. Agus anois is dócha Iarraim pop. Anois pop, de réir an ghnáis, ní a chur argóint. Le Stack, an t-iomlán pointe de na meafar tráidire is é sin nach mian leat go bhfuil rogha ag chun dul a fháil go tráidire, is féidir go léir a dhéanamh Tá pop an ceann topmost ó an chairn, ach mar gheall ar. Sin an méid a dhéanann an struchtúr seo sonraí. 

Amhlaidh ag an loighic má mé Deir pop, cad a thagann amach? Mar sin, 61. Mar sin, cad é i ndáiríre an ríomhaire ag dul a dhéanamh i gcuimhne? Cad a dhéanann mo cód a dhéanamh? Cad ba mhaith leat a mholadh athrú againn ar an scáileán? Cad ba chóir a athrú? Tá brón orm? Mar sin, a fháil againn réidh 61. Mar sin, is féidir liom a dhéanamh cinnte go. Agus is féidir liom a fháil réidh 61. Agus ansin cad eile Ní mór-athrú a tharlóidh? Tá méid is dócha dul ar ais go dtí dhá. Agus mar sin go bhfuil fíneáil. Ach fan nóiméad, méid nóiméad a bhí trí shin. A ligean ar a dhéanamh ach seiceáil sanity tapaidh. Cén chaoi a raibh a fhios againn go bhfuil muid a theastaigh chun fáil réidh le 61? Mar gheall orainn ag popping. Agus mar sin tá mé an dara méid maoine. 

Fan nóiméad, tá mé ag smaoineamh ar ais go dtí seachtain dhá nuair a thosaigh muid ag caint faoi arrays, áit a raibh an suíomh náid, ba é seo áit amháin, ba é seo suíomh dhá, tá an suíomh trí, ceithre, tá sé cosúil leis an gaol idir méid agus an eilimint gur mhaith liom a bhaint ó na eagar cosúil go díreach cad? Méid lúide ceann amháin. Agus mar sin tá go conas mar dhaoine tá a fhios againn 61 túisce. Conas atá an ríomhaire ag dul go mbeadh a fhios? Nuair a bheidh do chód, áit a bhfuil tú is dócha ag iarraidh a dhéanamh ar mhéid lúide amháin, mar sin tá trí lúide amháin dhá, agus go Ciallaíonn ba mhaith linn a fháil haitheantas coibhneasta de 61. Agus ansin is féidir linn a thabhairt cothrom le dáta go deimhin an méid sin a méid anois Téann ó thrí go ach dhá. Agus díreach a bheith pedantic, tá mé ag dul a mholadh go bhfuil mé ag déanamh, ceart? Mhol tú intuitively i gceart ba chóir dom a fháil haitheantas coibhneasta de 61. Ach tá ní mé cineál saghas gotten réidh 61? Tá mé dearmad go héifeachtach go bhfuil sé i ndáiríre. Agus is dóigh ar ais go dtí PSET4, má tá tú ag léamh an t-alt faoi forensics, an PDF go raibh muid tú guys a léamh, nó is féidir leat Beidh léamh an tseachtain seo le haghaidh PSET4. Thabhairt chun cuimhne go bhfuil sé seo i ndáiríre germane le an smaoineamh ar fad de forensics ríomhaire. Cad a dhéanann go ginearálta go bhfuil ar ríomhaire dearmad sé ach sa chás go bhfuil rud éigin, ach ní théann sé i agus is maith iarracht a scratch sé amach nó shárú na píosaí le nialais agus cinn nó roinnt patrún randamach eile ach amháin má tú a dhéanamh duit féin mar sin d'aon turas. Mar sin, bhí do intuition ceart, a ligean ar a fháil haitheantas coibhneasta de 61. Ach i ndáiríre, nach bhfuil againn a bodhraigh. Ní mór dúinn ach a dearmad go tá sé ann trí athrú a ár méid. 

Anois tá fadhb leis an chairn. Má mé a choinneáil ag brú rudaí isteach ar an chairn, cad atá ar ndóigh ag dul a tharlóidh i díreach cúpla nóiméad am? Táimid ag dul a rith amach as an spás. Agus cad a dhéanaimid? Táimid ag de chineál ar screwed. Ní dhéanann an cur i bhfeidhm a ligean linn Athraigh an eagar, mar gheall ar úsáid a bhaint as an error, má tá tú I mo thuairimse, ar ais go dtí seachtain dhá, nuair atá tú a dhearbhú an méid de eagar, nach bhfuil feicthe againn meicníocht fóill i gcás Is féidir leat athrú ar an méid de na eagar. Agus go deimhin nach bhfuil C bhfuil go gné. Má deir tú a thabhairt dom cúig Nths, glaoch orthu uimhreacha, sin uile tú ag dul chun é a fháil. Mar sin, a dhéanann muid anois mar de Dé Luain, tá an cumas chun teacht ar réiteach a chur in iúl áfach, ní mór dúinn ach a tweak an sainmhíniú ar ár chairn a bheith ar roinnt sraith crua-códaithe, ach amháin a stóráil ar seoladh. 

Anois cén fáth go bhfuil seo? Anois, ní mór dúinn ach a bheith compordach leis ar an bhfíric go nuair a ritheann mo chlár, Tá mé ag dul dócha go a iarraidh ar an duine, cé mhéad uimhir ar mhaith leat a stóráil? Mar sin, tá an t-ionchur atá le teacht ó áit éigin. Ach nuair a tá a fhios agam go uimhir, ansin is féidir liom ach úsáid an méid fheidhm a thabhairt dom le smután de chuimhne? Is féidir liom a úsáid malloc. Agus is féidir liom a rá aon líon na bytes Ba mhaith liom ar ais do na Nths. Agus go léir caithfidh mé a stóráil i líon athróg anseo taobh istigh den struct Ba chóir go mbeadh cad é? Cad a théann i ndáiríre isteach sa huimhreacha sa chás seo? Yera yeah, pointeoir chuig an chéad beart den smután de chuimhne, nó níos mó go sonrach, an seoladh de chéad bhliain de na bytes. Nach cuma má tá sé ar cheann beart nó billiún bytes, Ní mór mé díreach tar éis a cúram faoi an gcéad. Mar gheall ar cad ráthaíochtaí malloc agus mo ráthaíochtaí córas oibriúcháin, is é sin an smután de chuimhne I a fháil, tá sé ag dul a bheith tadhlach. Níl dul a bheith bearnaí. Mar sin, má tá d'iarr mé ar feadh 50 bytes nó 1,000 bytes, tá siad ag dul go léir a bheith ar ais go dtí ar ais go dtí ar ais. Agus fad a bheidh cuimhin liom cé chomh mór, conas i bhfad iarr mé, go léir is gá dom a fhios Is é an chéad seoladh den sórt sin. 

Mar sin, anois ní mór dúinn an cumas i cód. Cé gur costas, tá sé ag dul a ghlacadh chugainn níos mó ama a scríobh seo suas, d'fhéadfadh muid a ath-leithdháileadh anois go cuimhne ag ach a stóráil ar ainm difriúil ann más mian linn a níos mó nó fiú le smután níos lú de chuimhne. Mar sin, anseo le amach trádála. Anois, a fháil againn dinimiceas. Tá muid go fóill contiguousness Tá mé ag éileamh. Toisc go mbeidh malloc a thabhairt dúinn le smután tadhlach de chuimhne. Ach tá sé seo ag dul a bheith ina pian i an muineál dúinn, an Ríomhchláraitheoir, chun cód iarbhír suas. Tá sé díreach níos mó oibre. Ní mór dúinn cód akin leis an méid a bhí mé banging amach ach nóiméad ó shin. An-doable, ach cuireann sé castacht. Agus mar sin am forbróir, Ríomhchláraitheoir Tá am fós acmhainn eile go mb'fhéidir go mbeadh gá dúinn a chaitheamh roinnt ama a fháil gnéithe nua. Agus ansin ar ndóigh tá scuaine. Ní féidir linn dul isteach sa ceann amháin i oiread sonraí. Ach tá sé an-chosúil i spiorad. Raibh mé in ann a chur i bhfeidhm scuaine, agus chuid oibríochtaí comhfhreagracha, Enqueue nó Díchiúáil, cosúil le chur leis nó a bhaint, tá sé ach ar bhealach fancier rá é, Enqueue nó Díchiúáil, mar seo a leanas. Is féidir liom a thabhairt ach mé féin a struct go arís Tá roinnt ar eagar, go arís tá méid, ach cén fáth a bhfuil de dhíth orm anois súil a choinneáil ar an os comhair scuaine a choinneáil? Ní raibh mé gá go mbeadh a fhios an os comhair mo chairn. Bhuel, má tá mé arís ar feadh queue-- ligean ar díreach crua chódú sé mar a bhfuil cosúil le cúig slánuimhreacha i anseo d'fhéadfadh a. Mar sin, tá sé seo náid, ceann amháin, dhá, trí, ceithre. Tá sé seo ag dul a bheith ar a dtugtar uimhreacha arís. Agus beidh sé seo ar a dtugtar méid. 

Cén fáth go bhfuil sé ní leor go bhfuil ach méid? Bhuel, a ligean ar a bhrú na huimhreacha céanna ar. Mar sin, pushed-- mé enqueued mé, nó duine a bhrú. Anois, beidh mé a Enqueue 50, agus ansin 51, agus ansin 61, agus dot ponc ponc. Mar sin, tá go Enqueue. Enqueued mé 50, ansin 51, ansin 61. Agus tá sin comhionann go Stack go dtí seo, ach amháin gá dom a dhéanamh athrú amháin. Is gá dom a thabhairt cothrom le dáta mhéid seo, mar sin dul mé ó náid ceann go 2:58 anois. Conas is féidir liom a Díchiúáil? Cad a tharlaíonn leis Díchiúáil? Cé ba chóir teacht amach an liosta seo an chéad má tá sé ar an líne ag an Store Apple? Mar sin, 50. Mar sin, tá sé de chineál trickier an am seo. De bharr an méid uair dheireanach a bhí sé Super éasca a dhéanamh ach méid lúide amháin, A fháil mé go dtí an deireadh mo eagar go héifeachtach áit a bhfuil na huimhreacha, go mbainfidh sé 61. Ach níl mé ag iarraidh a bhaint 61. Ba mhaith liom a ghlacadh 50, a bhí ann ag 05:00 go dtí an líne suas le haghaidh an iPhone nó whatnot nua. Agus mar sin a fháil haitheantas coibhneasta de 50, mé nach féidir a dhéanamh ach seo, ceart? Is féidir liom a tras amach 50. Ach dúirt muid ach táimid ag nach bhfuil a bheith chomh anal mar a scratch amach nó a cheilt ar na sonraí. Is féidir linn dearmad go díreach i gcás ina bhfuil sé. 

Ach má athraím mo méid anois go dhá, is é an t-eolas leordhóthanach a fháil amach cad atá ar siúl i mo scuaine? Níl i ndáiríre. Cosúil le go bhfuil mo méid dhá, ach i gcás ina ndéanfaidh an scuaine tús a chur, go háirithe má tá mé fós na huimhreacha céanna i gcuimhne. 50, 51, 61. Mar sin, is gá dom a mheabhrú anois i gcás ina bhfuil an tosaigh. Agus mar sin mar a mhol mé suas ann, beidh orainn a bheith ar a dtugtar ach Tosaigh nú, a bhfuil a tosaigh Ba chóir go mbeadh luach a bheith cad é? Zero, ach an tús an liosta. Ach anois chomh maith le decrementing an méid, táimid ag incrimint ach an tosaigh. Anois tá anseo fadhb eile. Mar sin, aon uair amháin a choinneáil mé ag dul. Is dócha é seo an líon cosúil le 121, 124, agus ansin, dammit, Tá mé amach as an spás. Ach fan nóiméad, nach bhfuil mé. Mar sin, ag an bpointe seo sa scéal, Is dócha go bhfuil an méid amháin, dhá, trí, ceithre, mar sin is dócha go mbeidh an Tá méid ceithre, is é an tosaigh amháin, mar sin tá 51 ag an tosaigh. Ba mhaith liom a chur ar uimhir eile anseo, ach, dammit, tá mé amach as an spás. Ach níl mé i ndáiríre, ceart? I gcás ina raibh mé in ann a chur ar roinnt luach breise, cosúil le 171? Yeah, d'fhéadfadh mé díreach de chineál ar dul ar ais thar ann, ceart? Agus ansin tras amach an 50, nó ach scríobh air le 171. Agus má tá tú ag wondering cén fáth ár n-uimhreacha a fuair chomh randamach, seo a ghlacadh go coitianta ríomhaire Cúrsaí eolaíochta ag Harvard i ndiaidh CS50. Ach bhí go maith leas iomlán a bhaint, mar anois nach bhfuil mé ag wasting spás. Tá mé fós ag cuimhneamh cé chomh mór is atá an rud iomlán. Tá sé cúig-iomlán. Toisc nach bhfuil mé ag iarraidh a tús a overwriting 51. Mar sin, anois tá mé fós amach as an spás, mar sin an fhadhb chéanna is a bhíodh. Ach is féidir leat a fheiceáil conas anois i do chód, is dócha a scríobh beagán níos mó castacht a dhéanamh a tharlaíonn. Agus go deimhin, cén oibreoir i C ligeann dócha leat é seo a magically an ciorclú? Yeah an t-oibreoir modulo, an comhartha céatadáin. Mar sin, cad atá de chineál ar fionnuar faoi scuaine, cé a choinneáil orainn arrays líníocht mar na línte díreacha mhaith, má tá tú de chineál ar smaoineamh faoi seo mar curving timpeall mar ciorcal, ansin ach intuitively cineál oibríonn sé meabhrach I mo thuairimse, beagán níos mó cleanly. Ba mhaith leat fós a chur i bhfeidhm go múnla meabhrach i cód. Mar sin, ní go crua, ar deireadh thiar, a chur i bhfeidhm, ach caillfidh muid fós ar an size-- in áit, an cumas a athrú, ach amháin má dhéanaimid é seo. 

Ní mór dúinn a fháil haitheantas coibhneasta de na eagar, táimid ag ionad le pointeoir amháin, agus ansin áit éigin i mo cód fuair mé a ghlaoch cad fheidhm a chruthú i ndáiríre an eagar ar a dtugtar uimhreacha? Malloc, nó roinnt den chineál céanna fheidhm, go díreach. Ceisteanna ar bith ar stoic nó scuainí. Yeah? Ceist mhaith. Cad modulo mbeadh tú a úsáid anseo. Mar sin, go ginearálta, nuair a úsáid mod, ba mhaith leat é a dhéanamh leis an méid de na struchtúr sonraí ar fad. Mar sin, rud éigin cosúil le cúig nó cumas, más rud é tá sé tairiseach, tá baint dócha. Ach amháin ag déanamh modulo cúig is dócha nach bhfuil go leor, mar is gá dúinn a fhios a dhéanaimid timfhillteach anseo nó anseo nó anseo. Mar sin, tá tú is dócha freisin dul go dtí gur mian chun páirt an méid de na rud, nó an athróg tosaigh chomh maith. Mar sin, tá sé ach seo réasúnta léiriú uimhríochtúil simplí, ach bheadh ​​modulo a bheith ar an príomh-chomhábhar. 

Scannán chomh gearr más maith leat. Beochan go bhfuil roinnt folks ag ollscoil eile a chur le chéile go tá muid in oiriúint do phlé seo. Baineann sé Jack ag foghlaim na fíricí mar gheall ar scuainí agus stats. 

SCANNÁN: Nuair ar am, bhí Guy ainmnithe Jack. Nuair a tháinig sé chun cairde a dhéanamh, Ní raibh Jack bhfuil knack. Mar sin, chuaigh Jack chun labhairt leis an an chuid is mó tóir Guy a fhios aige. Chuaigh sé go dtí Lou agus d'iarr, Cad a dhéanfaidh mé? Lou chonaic go raibh a chara a bhí i ndáiríre bponc. Bhuel, thosaigh sé, ach cuma conas a bhfuil tú ag gléasta. Ná tá aon éadaí le breathnú difriúil? Yes, a dúirt Jack. Liom a dhéanamh cinnte. Tar go dtí mo theach agus Feicfidh mé iad a thaispeáint duit. Mar sin, chuaigh siad amach go Sheáin. Agus léirigh Jack Lou an bosca áit a choinnigh sé go léir a léinte, agus a pants, agus a chuid stocaí. Lou dúirt, féach mé go bhfuil tú gach do chuid éadaí i carn. Cén fáth nach bhfuil tú a chaitheamh roinnt daoine eile uair amháin i awhile? 

Jack dúirt, go maith, nuair mé éadaí agus stocaí a bhaint, Nigh mé iad agus a chur iad a choinneáil amach sa bhosca. Ansin tá an chéad maidin, agus suas mé hop. Téim go dtí an bosca agus a fháil mo chuid éadaigh as an barr. Lou thuig go tapa an fhadhb le Jack. Choimeád sé éadaí, dlúthdhioscaí, agus leabhair sa chairn. Nuair a shroich sé do rud éigin a léamh nó a chaitheamh, bhfuigheadh ​​sé a roghnú an leabhar barr nó fo-éadaí. Ansin, nuair a bhí déanta aige, sé Bheadh ​​a chur ceart ar ais. Ar ais go mbeadh sé dul, ar bharr an chairn. Tá a fhios agam an réiteach, dúirt Loud buadhach. Ní mór duit a fhoghlaim chun tosú ag baint úsáide scuaine. Lou ghlac éadaí Sheáin agus crochadh iad sa closet. Agus nuair a bhí fholmhú sé an bosca, tossed sé ach é. 

Ansin dúirt sé, anois Jack, ag deireadh na an lá, a chur ar do chuid éadaí ar thaobh na láimhe clé nuair a chuir tú iad a choinneáil amach. Ansin maidin amárach nuair a dhéanann tú féach ar an solas na gréine, a fháil do chuid éadaí ar an gceart, ó dheireadh na líne. Nach bhfeiceann tú? Dúirt Lou. Beidh sé chomh deas. Feicfidh tú gach rud a chaitheamh uair amháin sula chaitheann tú rud éigin faoi dhó. Agus le gach rud i scuainí ina closet agus seilf, Jack thosaigh a bhraitheann go leor cinnte de féin. Gach a bhuíochas sin do Lou agus a scuaine iontach. Cainteoir 1: Ceart go leor, tá sé adorable. Mar sin, an méid atá bainte ag dul i ndáiríre ar thíos an cochall anois? Go bhfuil muid leideanna, go bhfuil muid malloc, go bhfuil muid ar an cumas a chruthú smután de chuimhne dúinn féin dinimiciúil. Mar sin, tá sé seo le linn a pictiúr glimpsed ach an lá eile. Ní raibh muid dwell i ndáiríre ar sé, ach tá sé seo pictiúr Tá ag dul ar thíos an cochall haghaidh seachtain anois. Agus mar sin léiríonn sé seo, ach dronuilleog go atá againn a tharraingt, gcuimhne do ríomhaire. Agus b'fhéidir do ríomhaire, nó CS50 ID, tá gigabyte de chuimhne RAM nó nó dhá ghigibheart nó ceithre. Ní chuireann sé ábhar i ndáiríre. Do chóras oibriúcháin Windows nó Mac OS nó Linux, go bunúsach is féidir do chlár chun smaoineamh go bhfuil rochtain leis an iomlán gcuimhne do ríomhaire, cé go dtiocfadh leat a bheith ag rith Cláir il ag an am céanna. Mar sin, i ndáiríre, nach bhfuil ag obair i ndáiríre. Ach tá sé de chineál ar illusion a thugtar do gach ceann de do chláir. Mar sin, má bhí tú dhá gigs de RAM, seo Is conas a d'fhéadfadh an ríomhaire a smaoineamh ar é. 

Anois coincidentally, ar cheann de na rudaí, ar cheann de na codanna de chuimhne, Tugtar Stack. Agus go deimhin aon am go dtí seo i scríbhinn cód go bhfuil tú ar a dtugtar fheidhm, mar phríomh shampla. Thabhairt chun cuimhne go am ar bith Tá mé gcuimhne ríomhaire tharraingt ar, Tharraingt mé i gcónaí saghas leath de dronuilleog anseo agus nach bodhraigh ag caint faoi ​​cad atá thuas. Toisc nuair a mó ar a dtugtar, Éilím go bhfaigheann tú an sliver de chuimhne go Téann síos anseo. Agus más mó ar a dtugtar feidhm cosúil le babhtála, go maith téann babhtála anseo. Agus casadh sé amach, go bhfuil i gcás ina tá sé ag críochnú suas. Ar rud ar a dtugtar Stack taobh istigh de do ríomhaire a chuimhne. Anois ag an deireadh an lae, tá sé seo ach seoltaí. Tá sé cosúil le beart náid, beart amháin, beart 2 billiún. Ach má cheapann tú faoi mar an réad dronuilleogach, gach tá muid ag déanamh gach am tugaimid is feidhm layering slice nua de chuimhne. Táimid ag tabhairt feidhme sin a slice dá chuimhne féin a bheith ag obair leis. 

Agus a thabhairt chun cuimhne anois go bhfuil sé seo tábhachtach. Toisc má bhfuil againn rud éigin cosúil le babhtála agus dhá athróg áitiúla ar nós A agus B agus athraíonn muid na luachanna ó cheann amháin agus dhá le dhá agus ceann amháin, chun cuimhne go nuair a fhilleann babhtála, tá sé mar cé seo slice de chuimhne imithe díreach. I ndáiríre, tá sé fós ann fóiréinseach. Agus rud éigin fós ann i ndáiríre. Ach choincheapa de, tá sé mar cé go tá sé imithe go hiomlán. Agus mar sin ní dhéanann príomh fhios ag aon cheann de na hoibre go ndearnadh i feidhme sin babhtála, ach amháin má tá sé rite iarbhír sna argóintí trí pointeoir nó trí thagairt. Anois, an réiteach bunúsach leis fadhb le babhtála Tá rudaí ag dul i ag seoladh. Ach casadh sé amach, freisin, cad atá ag dul ar os cionn an gcuid sin na dronuilleoige is léir an am seo ach níl níos mó cuimhne suas ann. Agus nuair a dhéanann tú dinimiciúil leithdháileadh cuimhne, bíodh sé taobh istigh de GetString, a tá muid ag déanamh leat sa CS50 leabharlann, nó má tá tú guys glaoch malloc agus a iarraidh an córas oibriúcháin ar feadh smután de chuimhne, ní chuireann sé teacht as an chairn. Tagann sé ó áit eile i gcuimhne do ríomhaire go dtugtar an gcarn. Agus ní ar sin aon éagsúla. Tá sé an RAM céanna. Tá sé an chuimhne chéanna. Tá sé díreach an RAM go bhfuil suas ann in ionad síos anseo. 

Agus mar sin cad a chiallaíonn? Bhuel, má tá do ríomhaire méid teoranta de chuimhne agus tá an chairn ag fás suas, mar sin a labhairt, agus an gcarn, de réir a ghabhann leis an arrow, ag fás síos. I bhfocail eile, gach am a ghlaonn tú malloc, tá tú ag á thabhairt slice de chuimhne ó thuas, ansin b'fhéidir beagán níos ísle, ansin beagán níos ísle, gach uair a ghlaonn tú malloc, an gcarn, tá sé úsáide, Tá cineál ag fás, ag fás níos dlúithe agus níos cóngaraí do cad é? An chairn. Mar sin, hionann sin is cosúil mhaith smaoineamh maith? Ciallaíonn mé, i gcás nach bhfuil sé i ndáiríre soiléir cad eile is féidir leat a dhéanamh má tá tú ach go mbeadh méid teoranta de chuimhne. Ach tá sé seo surely dona. Tá na dhá saighde ar tuairteála cúrsa ar a chéile. 

Agus casadh sé amach go Guy olc, folks a Tá maith go háirithe leis an gclárú, agus ag iarraidh a hack isteach ríomhairí, Is féidir leas a bhaint as an réaltacht. Go deimhin, a ligean ar a mheas Blúire beag. Mar sin, is é seo sampla is féidir leat léamh faoi ​​níos mionsonraithe ar Wikipedia. Beidh muid pointe tú ag an earra dá aisteach. Ach níl ionsaí ginearálta ar a dtugtar Maolán thar maoil go bhí ann chomh fada agus is daoine bhí an cumas a ionramháil gcuimhne ríomhaire, go háirithe i C. Mar sin, tá sé seo le clár an-treallach, ach a ligean ar é a léamh ó bhun aníos. Príomhbhunaíochta a dhul isteach réalta argC ruabhric argV. Mar sin, tá sé ina clár a thógann argóintí orduithe. Agus a dhéanann go léir príomh cosúil glaoch feidhm, ghlaoch air F le haghaidh simplíocht. Agus Gabhann sé i cad é? ArgV amháin. Mar sin, Gabhann sé isteach F cuma cad Is é an focal go bhfuil an t-úsáideoir clóscríofa ag an pras tar éis an ainm chláir ar chor ar bith. Mar sin, i bhfad ar nós Caesar nó Vigenere, a go dtiocfadh leat a thabhairt chun cuimhne a dhéanamh le argV. 

Mar sin, cad é F? F Bíonn i teaghrán mar a argóint amháin, Aka réalta Char, céanna rud, mar theaghrán. Agus tá sé ar a dtugtar treallach barra sa sampla seo. Agus ansin char c 12, díreach i dtéarmaí layman, cad é char c lúibín 12 dhéanamh dúinn? Cad atá sé? Leithdháileadh cuimhne, go sonrach 12 bytes ar feadh 12 chars. Go díreach. Agus ansin an líne dheireanach, stir agus cóip, ní tá tú ag feiceáil dócha. Is é seo cóip teaghrán fheidhm arb é is cuspóir sa saol is é sin le cóip a dhara argóint isteach ina chéad argóint, ach amháin suas go dtí líon áirithe de bytes. Mar sin, deir an tríú argóint, cé mhéad bytes ba chóir duit a chóipeáil? An fad barra, is cuma cad an t-úsáideoir clóscríofa i. Agus an t-ábhar barra, go teaghrán, tá chóipeáil isteach an chuimhne Léirigh ag ag C. 

Mar sin, is cosúil seo de chineál ar dúr, agus tá sé. Tá sé ina sampla bréige, ach tá sé ionadaíoch d'aicme de veicteoirí ionsaí, ar bhealach de ionsaí ar chlár. Gach Tá go fíneáil agus maith má tá an t-úsáideoir cineálacha i bhfocal sin 11 carachtair nó níos lú, móide an cúlslais nialas. Cad a tharlaíonn má na cineálacha úsáideoir i níos mó ná 11 nó 12 nó 20 nó 50 carachtair? Cad é seo clár ag dul a dhéanamh? Locht d'fhéadfadh a seg. Tá sé ag dul a chóipeáil blindly gach rud i bar suas a fhad, a bhfuil literally gach rud i barra, isteach an seoladh chuir ar C. Ach C Tá ach preemptively thabhairt mar 12 bytes. Ach níl aon seiceáil breise. Níl aon má coinníollacha. Níl aon earráid seiceáil anseo. 

Agus mar sin cad é an clár seo ag dul a dhéanamh ná díreach blindly rud amháin a chóipeáil leis an duine eile. Agus mar sin má táimid a tharraingt seo mar pictiúr, anseo ach sliver ar an spás chuimhne. Mar sin, faoi deara ag an mbun, táimid ag tá an mbarra athróg áitiúil. Mar sin, go pointeoir go bhfuil dul chun store-- seachas sin argóint áitiúil go dul a stóráil an mbarra teaghrán. Agus ansin faoi deara ach os a chionn i Stack, mar gheall ar gach uair a iarrann tú do chuimhne ar an chairn, téann sé le beagán os a chionn go pictiúrtha, Fógra go againn fuair 12 bytes ann. Is é an ceann is fearr ar chlé C lúibín nialas agus Is é an ceann ceart bun C lúibín 11. Sin díreach cé na ríomhairí ag dul a leagan sé amach. Mar sin, ach intuitively, má tá barra níos ná 12 carachtair san iomlán, lena n-áirítear an cúlslais náid, áit a bhfuil an 12 nó an lúibín C 12 dul chun dul? Nó in áit i gcás an 12ú carachtar nó an 13ú charachtar, an carachtar céadú ag dul a deireadh suas sa phictiúr? Os cionn nó faoi bhun? 

Ceart, mar gheall ar fiú cé go Fásann an chairn féin aníos, nuair atá tú stuif a chur i é, é a ar chúiseanna dearaidh, cuireann an chuimhne ó bhun go barr. Mar sin, má tá tú bhí níos mó ná 12 bytes, bhfuil tú ag dul chun tús a barra a fhorscríobh. Anois go bhfuil a bug, ach tá sé ní i ndáiríre le déileáil go mór. Ach tá sé le déileáil go mór, mar níl níos mó stuif ar siúl i gcuimhne. Mar sin, anseo conas a d'fhéadfadh muid a chur hello, a bheith soiléir. Má chlóscríobh mé i Dia duit ag an pras. H-E-L-L-O cúlslais náid thagann deireadh, ar bun laistigh iad siúd 12 bytes, agus tá muid Super sábháilte. Tá gach rud go maith. Ach má cineál mé rud éigin níos faide, d'fhéadfadh sé ag dul a creep isteach i spás bar. Ach níos measa fós, casadh sé amach gach am seo, cé riamh againn Labhair faoi é, is é an chairn a úsáidtear le haghaidh rudaí eile. Nach bhfuil sé ach athróga áitiúla. 

C Is teanga leibhéal an-íseal. Agus é saghas rúnda Úsáideann an chairn freisin a mheabhrú nuair a Tá feidhm dtugtar, cad Is é an seoladh na feidhme roimhe sin, ionas gur féidir é a léim ar ais go dtí feidhme sin. Mar sin, nuair is mó glaonna babhtála, i measc na rudaí a bhrú isteach ar an chairn Nach bhfuil babhtálacha ach athróga áitiúla, nó a argóintí, bhrúigh freisin rúnda isteach ar an chairn mar ionadaithe ag an slice dearg anseo, Is é an seoladh ar mó go fisiciúil i gcuimhne do ríomhaire, ionas gur nuair a babhtála a rinneadh, an ríomhaire Fhios gá dom dul ar ais go to main chríochnú agus forghníomhaitheach an fheidhm is mó. Mar sin, is é seo contúirteach anois, mar má na cineálacha úsáideoir i go maith níos mó ná Dia duit, den sórt sin go clobbers ionchur an úsáideora nó overwrites alt sin dearg, go loighciúil má tá an ríomhaire ach ag dul chun glacadh blindly go bhfuil na bearta sa slice dearg an seoladh ar cheart dó ar ais, cad má tá an adversary cliste go leor nó ádh go leor chun a chur ar ord na bytes ann go Breathnaíonn cosúil le seoladh, ach tá sé an seoladh an cód gur mian leis nó léi an ríomhaire a fhorghníomhú in ionad phríomh? 

I bhfocail eile, más rud é cad é an Tá úsáideoir clóscríobh ag an pras, Níl ach rud éigin cosúil le innocuous Dia duit, ach tá sé i ndáiríre go coibhéiseach cód a scriosadh comhaid seo úsáideora go léir? Nó a n-phasfhocal ríomhphost chugam? Nó tús logáil gcuid keystrokes, ceart? Tá bealach, a ligean ar a ordú lá atá inniu ann, go bhféadfadh siad cineál i ní hamháin Dia duit domhan nó a n-ainm, d'fhéadfadh siad go bunúsach pas a fháil i cód, agus nialais cinn, go bhfuil an ríomhaire botúin haghaidh cód agus seoladh araon. Mar sin, cé beagán abstractly, más rud é an cineálacha úsáideoir i go leor cód sáraíochta go beidh orainn a ghinearálú anseo mar A. A ionsaí nó adversaries. Stuif mar sin ach dona. Ní chuirimid cúram faoi na uimhreacha nó na nialais nó cinn lá atá inniu ann, den sórt sin go deireadh tú suas overwriting alt sin dearg, faoi ​​deara go ord na mbeart. O 835 C náid ocht náid. Agus anois mar Wikipedia article anseo Tá sé molta ag, má tá tú anois tús a chur i ndáiríre lipéadú na bearta i do ríomhaire le chuimhne, cad é an t-alt Wikipedia Is tairisceana sin, cad má an seoladh den bheart barr chlé 80 C 0 3508. 

I bhfocail eile, má tá an Guy dona cliste go leor lena thoiliú nó lena cód a chur i ndáiríre a PO anseo go fhreagraíonn an seoladh an cód ghann sé nó sí isteach sa ríomhaire, tú Is féidir trick an ríomhaire isteach ag déanamh rud ar bith. Comhaid a bhaint de, ríomhphost a sheoladh rudaí, sniffing do thrácht, literally D'fhéadfadh rud ar bith a bheith ghann isteach sa ríomhaire. Agus mar sin a thar maoil maolán ionsaí ag a chroí bhfuil ach dúr, dúr sáraitheach le sraith go Ní raibh a teorainneacha sheiceáil. Agus is é seo an méid is Super contúirteach agus go comhuaineach Super cumhachtach i C é go bhfuil againn go deimhin rochtain ar aon áit sa chuimhne. Tá sé suas le linn, na ríomhchláraitheoirí, a scríobh an cód bunaidh a sheiceáil leis an fad darn aon arrays go bhfuil muid ag ionramháil. Mar sin, a bheith soiléir, cad é an shocrú? Má rolla muid ar ais go dtí an cód, ní chóir mé díreach tar éis athrú ar an fad barra, cad eile ba chóir dom a bheith a sheiceáil? Cad eile ba chóir dom a bheith á dhéanamh go cosc a chur ar an ionsaí go hiomlán? Níl mé ag iarraidh a rá blindly ach gur chóir duit cóip mar go leor beart mar go bhfuil an fad barra. Ba mhaith liom a rá, a chóipeáil mar Tá a lán bytes mar atá i barra suas go dtí an leithdháileadh chuimhne, nó 12 maximally. Mar sin, is gá dom roinnt de chineál ar choinníoll más rud é go ndéanann seiceáil fad na barra, ach má théann sé thar 12, linn a cód ach go crua 12 mar an t-achar is mó is féidir. Seachas sin an maolán sin ar a dtugtar Is féidir le ionsaí thar maoil tarlú. Ag bun na n sleamhnáin, má tá tú aisteach chun tuilleadh a léamh Is é an t-alt bunaidh iarbhír más mian leat a chur le breathnú. 

Ach anois, i measc na praghsanna a íocadh anseo bhí mí-éifeachtúlachtaí. Mar sin, bhí go mear breathnú leibhéal íseal ar an méid Is féidir le fadhbanna chun cinn anois go bhfuil muid rochtain a fháil gcuimhne ríomhaire. Ach fadhb eile táimid ag stumbled cheana ar an Luan raibh ach an neamhéifeachtacht de liosta nasctha. Tá muid ar ais go dtí am líneach. Táimid a thuilleadh raon tadhlach. Ní chuirimid bhfuil rochtain randamach. Ní féidir linn a úsáid nodaireacht lúibín cearnach. Ní mór dúinn literally a úsáid lúb tamaill cosúil leis an ceann a scríobh mé nóiméad ó shin. Ach ar an Luan, d'éiligh muid go féidir linn creep ar ais isteach sa réimse na héifeachtachta rud éigin go bhfuil a bhaint amach logartamach b'fhéidir, nó is fearr go fóill, b'fhéidir fiú rud éigin go mar a thugtar air am tairiseach. Mar sin, conas is féidir linn é sin a dhéanamh trí úsáid a bhaint na nua uirlisí, na seoltaí, na leideanna, agus rudaí ar ár gcuid féin snáithiú? Bhuel, is dócha go anseo, is iad seo a bunch uimhreacha gur mhaith linn a stóráil i Struchtúr sonraí agus cuardaigh go héifeachtach. Is féidir linn a athchasadh go hiomlán go seachtain dhá, caith seo i sraith, agus cuardach a iad a úsáid cuardaigh dénártha. Roinn agus conquer. Agus go deimhin scríobh tú cuardaigh dénártha i PSET3, nuair a chur i bhfeidhm tú an clár a aimsiú. Ach tá a fhios agat cad. Níl de chineál ar níos bhealach cliste é seo a dhéanamh. Tá sé beagán níos mó sofaisticiúla agus b'fhéidir ligeann dúinn a fheiceáil cén fáth dénártha Tá cuardach mar sin i bhfad níos tapúla. Gcéad dul síos, a ligean ar thabhairt isteach an coincheap de chrann. A cé i crainn réaltacht de chineál ar fás mar seo, i saol na ríomhaireachta eolaíocht siad de chineál ar fás síos cosúil le crann teaghlaigh, áit a bhfuil tú do sheantuismitheoirí nó sheantuismitheoirí mór nó whatnot ag an mbarr, an patriarch agus an matriarch an teaghlaigh, ach amháin mar a thugtar air fréimhe, nód, thíos a bhfuil a chuid leanaí, faoi ​​bhun a bhfuil a chuid leanaí, nó a sliocht níos ginearálta. Agus duine ar bith crochta amach an bun an teaghlach crann, seachas a bheith ar an is óige sa teaghlach, Is féidir freisin a bheith díreach cineálach ar a dtugtar na duilleoga an chrainn. 

Mar sin, tá sé seo ach a bunch de na focail agus sainmhínithe as rud éigin ar a dtugtar crann i ríomhaire eolaíocht, i bhfad nós crann teaghlaigh. Ach níl incarnations fancier na gcrann, ceann acu ar a dtugtar crann cuardaigh dénártha. Agus is féidir leat de chineál ar tease ar leith cad a dhéanann an rud. Bhuel, tá sé dénártha i cén chiall? Nuair a dhéanann an dénártha thagann ó anseo? Tá brón orm? Níl sé sin i bhfad ar nó go. Tá sé níos mó nach bhfuil aon le gach ceann de na nóid níos mó ná beirt leanbh, mar a fheicimid anseo. Go ginearálta, tá tree-- agus do thuismitheoirí agus do sheantuismitheoirí is féidir a bheith mar go leor páistí nó grandkids mar is mian leo i ndáiríre, agus mar sin mar shampla ann ní mór dúinn trí páistí amach go nód láimhe deise, ach i gcrann dénártha, tá nód náid, ceann amháin, nó beirt leanaí maximally. Agus sin ar mhaoin deas, mar má tá sé teorainn dhá, táimid ag dul a bheith in ann a fháil bonn logáil beag dhá gníomh ar siúl anseo ar deireadh thiar. Mar sin, ní mór dúinn rud éigin logartamach. Ach níos mó ar sin i láthair. Ciallaíonn Cuardach crann go bhfuil na huimhreacha shocraigh den sórt sin go an leanbh chlé ar Tá luach níos mó ná an fhréamh. Agus is é a leanbh ceart níos mó ná an fhréamh. I bhfocail eile, má ghlacann tú aon cheann de na nóid, na ciorcail sa phictiúr seo, agus tá ag a chlé leanbh agus a leanbh ceart, Ba chóir go mbeadh an chéad a bheith níos lú ná, Ba chóir go mbeadh an dara bheith níos mó ná. Mar sin, sanity seiceáil 55. Tá sé seo d'fhág leanbh 33. Tá sé níos lú ná. 55, is é a leanbh ceart 77. Tá sé níos mó ná. Agus sin sainmhíniú athchúrsach. D'fhéadfadh muid a sheiceáil gach ceann de na nóid agus an patrún céanna a bheadh ​​a shealbhú. 

Mar sin, cad atá deas i Tá crann cuardaigh dénártha, sin amháin, is féidir linn a chur i bhfeidhm le struct, ach mar seo. Agus cé go bhfuil muid ag caitheamh go leor de na struchtúir ag do, tá siad beagán iomasach anois tá súil againn. Is é an error fós arcane do cinnte, ach an t-ábhar ar nód sa context-- agus a choinneáil orainn ag baint úsáide as an nód focal, bíodh sé ina dronuilleog ar an scáileán nó ciorcal, tá sé ach cuid coimeádán cineálach, sa chás seo de chrann, cosúil leis an gceann chonaic muid, ní mór dúinn slánuimhir i ngach ceann de na nóid agus ansin is gá mé dhá threo dírithe leis an leanbh ar chlé agus an leanbh ceart, faoi ​​seach. Mar sin, go conas a d'fhéadfadh muid a a chur chun feidhme go i struct. Agus conas a d'fhéadfadh mé a chur i bhfeidhm i cód? Bhuel, a ligean ar ghlacadh mear breathnú ar an sampla beag bídeach. Níl sé feidhmiúil, ach tá mé chóipeáil agus a ghreamú go struchtúr. Agus más rud é mo fheidhm feadh dénártha Tá crann cuardaigh dtugtar cuardaigh, agus tógann sé seo dhá argóint, slánuimhir N agus pointeoir go nód, mar sin pointeoir chun an crann nó pointeoir chun an fhréamh de chrann, conas is féidir liom dul faoi ag cuardach do N? Bhuel, ar an gcéad, mar go bhfuil mé ag déileáil le leideanna, Tá mé ag dul a dhéanamh le seiceáil sanity. Má ionann ionann crann null é, N sa crann nó nach bhfuil san an crann? Ní féidir é a bheith, ceart? Má tá mé anuas null, níl rud ar bith ann. Mé go d'fhéadfadh chomh maith ach Deir blindly ar ais bréagach. Má thugann tú dom rud ar bith, ní féidir liom surely teacht ar aon uimhir N. Mar sin, cad eile a d'fhéadfadh mé seiceáil anois? Tá mé ag dul a rá go maith eile má tá N níos lú ná cuma cad é ag an nód crann go bhfuil mé ag láimh N luach. I bhfocail eile, má tá an uimhir tá mé lorg, N, níos lú ná an nód go bhfuil mé ag féachaint ar. Agus an nód tá mé ag lorg ag a dtugtar crann, agus a thabhairt chun cuimhne as an sampla roimhe a fháil ar an luach i pointeoir, Úsáid mé an nodaireacht arrow. Mar sin, má tá N lú ná arrow crann N, ba mhaith liom dul coincheapúil clé. Conas is féidir sainráite mé ag cuardach ar chlé? Chun a bheith soiléir, má tá sé seo an pictiúr atá i gceist, agus tá mé rite go topmost arrow go dírithe síos. Sin mo pointeoir chrann. Tá mé ag cur in iúl ag an fhréamh an chrainn. Agus tá mé ag lorg a rá, le haghaidh an uimhir 44, treallach. Is 44 níos lú ná nó níos mó ná 55 ar ndóigh? Mar sin, tá sé níos lú ná. Agus mar sin seo má tá feidhm riocht. Mar sin choincheapa de, cad is mé ag iarraidh a cuardaigh romhainn má tá mé ag lorg 44? Yeah? 

Go díreach, ba mhaith liom cuardaigh an leanbh ar chlé, nó an fo-crann clé den phictiúr seo. Agus go deimhin, lig dom trí an pictiúr síos anseo do díreach nóiméad, ós rud é Ní féidir liom scratch seo amach. Má thosaíonn mé anseo ag 55, agus Tá a fhios agam go bhfuil an luach 44 Táim ag lorg é sin le thaobh na láimhe clé, tá sé de chineál de cosúil tearing an leabhar teileafóin i leath nó tearing an crann i leath. Mé a thuilleadh a cúram faoi an leath ar fad an chrainn. Agus fós, curiously i dtéarmaí an struchtúr, an rud thar anseo go thosaíonn le 33, go féin Is crann cuardaigh dénártha. Dúirt mé an focal recursive roimh mar gheall ar go deimhin, tá sé seo le struchtúr sonraí a de réir sainmhínithe is Athchúrsach. D'fhéadfá a bheith crann go bhfuil sé seo mór, ach gach ceann dá leanaí Is ionann crann ach beagán níos lú. In ionad sé grandpa á nó grandma, anois tá sé ach mam or-- ní féidir liom say-- mam nó daidí, a bheadh ​​aisteach. Ina áit sin an bheirt leanaí ann Bheadh ​​a bheith cosúil le deartháir agus deartháir nó deirfiúr. Tá glúin nua de an crann teaghlaigh. Ach struchtúir de, tá sé an smaoineamh céanna. Agus casadh sé amach go bhfuil mé feidhm leis ar féidir liom a chuardach le cuardach dhénártha crann. Sé ar a dtugtar cuardaigh. Cuardaigh mé N i chlé arrow crann eile má tá níos mó ná an luach N go bhfuil mé faoi láthair ag. 55 sa scéal nóiméad ó shin. Tá mé ar a dtugtar feidhm cuardaigh gur féidir liom ach pas N seo agus hathchúrsach cuardaigh an fo-crann agus díreach ar ais is cuma cad go freagra. Else tá fuair mé roinnt cás bonn deiridh anseo. 

Cad é an cás deiridh? Is crann ceachtar null. Is é an luach Táim ag lorg ceachtar do níos lú ná nó níos mó ná sin nó cothrom le dó. Agus d'fhéadfadh liom a rá comhionann cothrom, ach tá sé go loighciúil coibhéiseach go dtí díreach ag rá eile anseo. Mar sin, fíor conas a fhaigheann mé rud éigin. Mar sin tá súil againn go bhfuil sé seo fiú sampla níos láidre ná an fheidhm sigme dúr rinne muid cúpla léachtaí ar ais, áit a raibh sé díreach chomh furasta a úsáid lúb a chomhaireamh suas go léir na huimhreacha ó cheann N. Anseo le struchtúr sonraí atá déanta de mheascán hathchúrsach sainithe agus hathchúrsach tharraingt, anois táimid ag bhfuil an cumas a chur in iúl dúinn féin i cód go bhfuil féin Athchúrsach. Mar sin, is é seo an cód ceannann céanna anseo. 

Mar sin, cad fadhbanna eile is féidir linn a réiteach? Mar sin, céim mear ar shiúl ó crainn ar feadh nóiméad ach. Anseo is é sin, a rá, an bhratach na Gearmáine. Agus níl go soiléir patrún a ghabhann leis an bhratach. Agus níl go leor de bratacha ar fud an domhain go Is iad chomh simplí sin i dtéarmaí ar a n-dathanna agus patrúin. Ach is dócha go bhfuil sé seo stóráilte mar GIF, nó JPEG, nó bitmap, nó ping, aon formáid comhaid grafacha lena bhfuil tú eolach, cuid acu a bhfuil muid ag imirt le i PSET4. Ní bhaineann sé seo cosúil go fiú a stóráil picteilín dubh, dubh picteilín, picteilín dubh, ponc, ponc, ponc, a bunch iomlán de pixel dubh don chéad scanline, nó a chéile, ansin a bunch iomlán de mar an gcéanna, ansin a bunch iomlán de na céanna, agus ansin bunch iomlán de pixel dearg, pixel dearg, pixel dearg, ansin ina n-iomláine bunch pixel buí, buí, ceart? 

Níl neamhéifeachtacht den sórt sin anseo. Conas a bheadh ​​tú intuitively compress an bhratach na Gearmáine más chur chun feidhme mar chomhad? Cosúil le cén t-eolas is féidir linn nach bodhraigh a stóráil ar dhiosca in ord a laghdú ar ár méid comhaid ó mhaith a mheigibhirt ar cilibheart, rud éigin níos lú? Wherein luíonn an iomarcaíocht anseo a bheith soiléir? Cad a d'fhéadfá a dhéanamh? Yeah? Go díreach. Cén fáth nach bhfuil in áit cuimhneamh an dath de gach picteilín darn díreach cosúil tú ag déanamh i PSET4 leis an fhormáid comhaid bitmap, cén fáth nach bhfuil ionadaíocht a dhéanamh leat ach an colún leftmost de pixel, mar shampla a bunch de pixel dubh, a bunch de dearg, agus a bunch de buí, agus ansin ach ionchódú bhealach an smaoineamh arís seo 100 uair nó arís an 1,000 uair? I gcás ina 100 nó 1,000 Tá ach slánuimhir, mar sin leat Is féidir a fháil amach le ach uimhir amháin in ionad na céadta mílte nó pixel breise. Agus go deimhin, go conas táimid ag D'fhéadfadh compress an bhratach na Gearmáine. Agus Anois, cad mar gheall ar an bhratach na Fraince? Agus beagán éigin de a fheidhmiú meabhrach, a bratach Is féidir a comhbhrúite níos mó ar dhiosca? An bhratach na Gearmáine nó na Fraince bratach, má táimid a bhfuil cur chuige? An bhratach na Gearmáine, mar níl iomarcaíochta níos cothrománach. Agus ag dearadh, comhad grafach go leor go deimhin a dhéanamh formáidí obair línte chomh scanadh cothrománach. D'fhéadfadh siad ag obair hingearach, ach daonnachta blianta ó shin go beidh orainn cinneadh I mo thuairimse, go ginearálta na rudaí a chéile de réir a chéile in ionad an colún ag colún. Mar sin, go deimhin, má bhí tú chun breathnú ar an gcomhad méid bratach na Gearmáine agus na Fraince bratach, fad a bheidh an rún mar an gcéanna, an leithead céanna agus airde, an ceann seo anseo ag dul a bheith níos mó, toisc go bhfuil tú a athdhéanamh féin trí huaire. Tá tú a shonrú gorm, arís féin, bán, arís tú féin, dearg, arís duit féin. Ní féidir leat dul ach go léir an mbealach chun an ceart. Agus mar leataobh, a dhéanamh soiléir ar an comhbhrú Is i ngach áit, má tá na ceithre frámaí ó video-- tú D'fhéadfadh cuimhne go scannán nó go bhfuil físeán go ginearálta cosúil le 29 nó 30 frámaí in aghaidh an dara. Tá sé cosúil le leabhar smeach beag áit a bhfuil tú ach féach íomhá, íomhá, íomhá, íomhá, íomhá ach Super tapaidh sin tá sé cosúil na haisteoirí ar an scáileán ag bogadh. Seo beach bumble ar barr an bunch na bláthanna. Agus cé go bhféadfadh sé a bheith de chineál ar deacair a fheiceáil ar an gcéad amharc, an rud amháin ag gluaiseacht i is é an scannán an bheach. 

Cad é balbh faoi stóráil físeán neamh-chomhbhrúite? Tá sé de chineál cur amú físeáin a stóráil mar ceithre íomhánna beagnach mar an gcéanna go difriúil ach amháin sa mhéid ina bhfuil an beach. Is féidir leat a caith amach an chuid is mó na faisnéise sin agus cuimhneamh ach, mar shampla, an chéad fráma agus an fráma seo caite, frámaí eochair má tá tú chuala riamh an focal, agus díreach a stóráil sa lár áit a bhfuil an beach. Agus ní gá duit a a stóráil ar fad de na bándearg, agus an gorm, agus an Luachanna glas chomh maith. Mar sin, is é seo a rá ach go Is comhbhrú i ngach áit. Tá sé mar theicníc linn a úsáid go minic nó a ghlacadh maidir le deonú na laethanta. 

Ach conas a dhéanann tú compress téacs? Conas a dhéanann tú dul faoi compressing téacs? Bhuel, gach ceann de na carachtair i Tá ascii beart amháin, nó ocht giotán. Agus sin de chineál ar balbh, ceart? Toisc is dócha tú cineál A agus E agus mé agus O agus U ar a lán níos minice ná mar W nó Q nó Z, ag brath ar an teanga ina bhfuil tú ag scríobh cinnte. Agus mar sin cén fáth táimid ag baint úsáide as ocht giotán le haghaidh gach litir, lena n-áirítear an laghad litreacha tóir, ceart? Cén fáth nach bhfuil úsáid níos lú giotán le haghaidh na litreacha Super tóir, cosúil E, na rudaí buille faoi thuairim tú den chéad uair i Roth de Fortune, agus a úsáid giotán níos mó le haghaidh na litreacha níos lú tóir? Cén fáth? Mar gheall orainn ag dul díreach a iad a úsáid chomh minic. 

Bhuel, casadh sé amach go bhfuil bhfuil curtha iarrachtaí a rinneadh chun é seo a. Agus má tá tú chun cuimhne ó ghrád scoil nó scoil ard, Morse cód. Tá poncanna cód Morse agus dashes gur féidir a bheith tharchuirtear feadh sreang mar fuaimeanna nó comharthaí de chineál éigin. Ach tá Morse cód glan Super. Tá sé de chineál córas dénártha i go bhfuil tú poncanna nó daiseanna. Ach má fheiceann tú, mar shampla, dhá poncanna. Nó má cheapann tú ar ais go dtí an t-oibreoir a théann cosúil le bíp, bíp, bíp, bíp, ag bualadh a spreagadh beag go tharchuireann comhartha, má tá tú, an faighteoir Faigheann, dhá poncanna, cén teachtaireacht a fuair tú? Go hiomlán treallach. 

I? I? Nó cad about-- nó mé? B'fhéidir go raibh sé ach dhá gceart E s? Mar sin níl an fhadhb seo de decodability le Morse cód, trína mura rud duine a sheoladh tú an teachtaireacht sosanna i ndáiríre ionas gur féidir leat a shórtáil de fheiceáil nó na bearnaí idir litreacha a chloisteáil, nach bhfuil sé go leor ach a seol sruth de nialais agus cinn, nó poncanna agus dashes, mar níl athbhrí. Is E ponc amháin, mar sin má tá tú féach ar dhá poncanna nó a chloisteáil dhá poncanna, b'fhéidir go bhfuil sé dhá E nó b'fhéidir go bhfuil sé ar cheann I. Mar sin, ní mór dúinn córas go bhfuil beagán níos cliste ná sin. Mar sin, fear darbh ainm bliain Huffman ó shin tháinig suas le díreach seo. Mar sin, táimid ag dul díreach a ghlacadh Sracfhéachaint ar mear ar conas atá crainn germane leis seo. Má ghlactar leis go bhfuil sé seo roinnt teachtaireacht dúr ba mhaith leat a sheoladh, comhdhéanta de díreach A, B, C agus E ar D's s, ach níl a lán de iomarcaíochta anseo. Tá sé seo ag ní i gceist a bheith i mBéarla. Nach bhfuil sé criptithe. Tá sé ach teachtaireacht dúr le go leor de athrá. Mar sin, má tá tú ag comhaireamh go hiarbhír amach na A s, B, C, D's, agus E s, anseo an mhinicíocht. Tá 20% de na litreacha A s, 45% de na litreacha Tá E, agus trí minicíochtaí eile. Chomhaireamh muid suas ann de láimh agus díreach a rinne an mata. 

Mar sin, tharlaíonn sé go raibh Huffman, tamall ó shin, thuig go, tá a fhios agat cad, má tús mé foirgneamh crann, nó foraoise de chrainn, más maith leat, mar seo a leanas, is féidir liom a dhéanamh ar an méid seo a leanas. Tá mé ag dul a thabhairt ar an nód le gach de na litreacha go bhfuil cúram mé faoi agus tá mé ag dul a stóráil taobh istigh den nód na minicíochtaí mar phointe ar snámh luach, nó d'fhéadfaí tú a úsáid ar N, freisin, ach beidh orainn a úsáid ach snámhphointe anseo. Agus an algartam go mhol sé é go bhfuil tú an deis seo a foraoise de nód amháin crainn torthaí, crainn sin Super gearr, agus a thosaíonn tú ag nascadh iad le grúpaí nua, tuismitheoirí nua, más maith leat. Agus a dhéanann tú é seo trí roghnú an dhá minicíochtaí is lú ag an am. Mar sin, ghlac mé 10% agus 10%. Chruthú mé nód nua. Agus glaoch mé an nód nua 20%. 

Cén dá nóid chéile mé seo chugainn? Tá sé ina beagán débhríoch. Mar sin, níl roinnt cásanna cúinne a mheas, ach a choinneáil ar rudaí go leor, Tá mé ag dul a roghnú 20% - Neamhaird agam anois ar na páistí. Tá mé ag dul a roghnú 20% agus 15% agus a tharraingt ar dhá imill nua. Agus anois a dhá nóid is féidir liom a chur le chéile go loighciúil? Déan neamhaird na páistí go léir, go léir na chlann clainne, ach breathnú ar na fréamhacha anois. Cén dá nóid is féidir liom cheangal le chéile? Pointe dhá agus 0.35. Mar sin, lig dom a tharraingt ar dhá imill nua. Agus ansin tá fuair mé ach ar chlé amháin. Mar sin tá anseo crann. Agus tá sé curtha le chéile d'aon ghnó chun breathnú cineál go leor, ach faoi deara go bhfuil an imill curtha lipéadú freisin nialas agus ceann amháin. Mar sin, tá gach ceann de na imill chlé náid treallach, ach go seasta. Tá na himill ceart cinn. 

Agus mar sin cad atá beartaithe Hoffman é sin, más mian leat chun ionadaíocht a dhéanamh B, seachas ar son an 66 mar ar ASCII atá ocht giotán fad, a fhios agat cad, a stóráil ach an patrún náid, náid, náid, náid, mar gheall ar go bhfuil an cosán ó mo chrann, crainn tUasal Huffman ar, leis an duilleog ó na fréamhacha. Más mian leat a stóráil ar E, ag gcodarsnacht leis sin, ní dhéanann seol ocht giotán a léiríonn an E. Ina áit sin, seol cén patrún na giotán? One. Agus cad atá deas faoi seo is é sin E an litir is coitianta, agus go bhfuil tú ag baint úsáide as an cód giorra chun é. An chéad chuid is mó tóir Breathnaíonn litir maith liom é Bhí A. Agus mar sin cé mhéad giotán raibh sé togra a úsáid le haghaidh sin? Zero, ceann amháin. 

Agus mar tá sé curtha i bhfeidhm mar an crann, do anois lig dom a ordú níl aon athbhrí mar atá i Morse cód, mar gheall ar gach ceann de na litreacha cúram tú ar tí Is iad ag deireadh na himill. Mar sin, go díreach ceann amháin iarratas ó chrann. Seo is-- agus beidh mé tonn mo lámh ag an conas tú D'fhéadfadh a chur i bhfeidhm seo mar struchtúr C. Ní mór dúinn ach a chur le chéile siombail, cosúil le ruabhric, agus minicíocht i chlé agus ar dheis. Ach a ligean ar breathnú ar dhá samplaí deiridh go mbainfidh tú fháil eolach go maith leis tar éis tráth na gceist náid i fhadhb a leagtar cúig. 

Mar sin, tá an struchtúr sonraí ar a dtugtar tábla hash. Agus is é tábla hash ar chineál an fionnuar sa mhéid is go bhfuil sé buicéid. Agus Is dócha níl ceithre buicéid anseo, ach ceithre spás bán. Seo ar deic na cártaí, agus anseo tá club, spád, club, diamaint, club, diamaint, club, diamaint, clubs-- sin is é seo an randamach. Hearts, hearts-- sin tá mé bucketizing gach ceann de na hionchuir anseo. Agus riachtanais tábla hash chun breathnú ar do ionchur, agus ansin é a chur i leith áit atá bunaithe ar an méid a fheiceann tú. Tá sé an algartam. Agus bhí mé ag baint úsáide as Super algartam amhairc simplí. An chuid is deacra a raibh cuimhneamh ar cad a bhí na pictiúir. Agus ansin níl ceithre rud iomlán. 

Anois bhí na cruacha atá ag fás, a Is é an rud deartha d'aon ghnó anseo. Ach cad eile a d'fhéadfadh liom a dhéanamh? Mar sin, i ndáiríre anseo ní mór dúinn a bunch de leabhair scrúdaithe d'aois scoile. Má ghlactar leis go a bunch de Tá ainmneacha na mic léinn ar anseo. Seo tábla hash níos mó. In ionad ceithre buicéid, Tá mé, a ligean le rá 26. Agus ní raibh muid ag iarraidh dul ar iasacht 26 rudaí ó lasmuigh [? Annenberg?], Agus mar sin anseo tá cúig léiríonn A trí Z. Agus má mé féach ar mac léinn a bhfuil a thosaíonn le A-ainm, Tá mé ag dul a chur nó a tráth na gceist ann. Má thosaíonn duine le C, thar ann, A-- ndáiríre, ní raibh ag iarraidh a dhéanamh sin. Téann B thar anseo. Mar sin, fuair mé A agus B agus C. Agus anois tá anseo mac léinn eile. Ach má tá an tábla hash i bhfeidhm le sraith, Tá mé de chineál ar screwed ag an bpointe seo, ceart? Cineál I gá a chur ar an áit éigin. 

Mar sin, tá bealach amháin is féidir liom a réiteach seo, go léir ceart, A gnóthach, B gnóthach, tá C gnóthach. Tá mé ag dul a chur air i D. Mar sin, ag an chéad, tá rochtain láithreach randamach mé le gach ceann de na buicéid do na scoláirí. Ach anois tá sé de chineál ar cineachta i rud éigin líneach, mar má ba mhaith liom a chuardach le haghaidh duine éigin Tosaíonn ainm a bhfuil a le A, a sheiceáil mé anseo. Ach más rud é nach é seo an A mac léinn Táim ag lorg, Cineál I a bheith chun tús a sheiceáil na buicéid, mar gheall ar cad a rinne mé Bhí saghas líneach probe an struchtúr sonraí. Bealach dúr rá ach breathnú don chéad oscailt fáil, agus a chur mar phlean B, mar a déarfá, nó plean D sa chás seo, an luach sa mhéid is go suíomh ina ionad. Tá sé seo ach mar sin go má tá tú Fuair ​​26 suíomh agus aon mhic léinn leis an ainm Q nó Z, nó rud éigin cosúil le go bhfuil, ar a laghad, go bhfuil tú ag baint úsáide as an spás. 

Ach tá muid le feiceáil cheana féin níos mó réitigh cliste anseo, ceart? Cad ba mhaith leat ina ionad má tá tú imbhualadh? Má tá beirt daoine an t-ainm A, cad a bheadh a bheith ina níos cliste nó réiteach iomasach ná díreach cur A áit a bhfuil D ceaptha a bheith? Cén fáth nach dtéann mé díreach tar éis taobh amuigh [? Annenberg?], cosúil le malloc, nód eile, é a chur anseo, agus ansin a chur go mac léinn anseo. Mar sin, go bhfuil mé go bunúsach de shaghas éigin le sraith, nó b'fhéidir níos galánta mar tá muid ag tosú a fheiceáil liosta nasctha. 

Agus mar sin tá tábla hash struchtúr d'fhéadfadh breathnú díreach cosúil le seo, ach níos cleverly, rud ar a dtugtar tú shlabhrú ar leith, trína tábla hash Is leor ach le sraith, gach ceann de a bhfuil a eilimintí nach bhfuil roinnt, é féin liosta nasctha. Ionas go bhfaigheann tú rochtain Super tapa cinneadh cén áit a hash do luach a. Mórán mar an sampla cártaí, Rinne mé cinneadh Super tapaidh. Hearts Téann anseo, diamaint Téann anseo. Céanna anseo, Téann anseo, D Téann anseo, B Téann anseo. Mar sin, Super tapa breathnú-ups, agus más rud é tharlaíonn tú a reáchtáil i gcás imbhuailtí nuair atá tú a fuair, dhá daoine a bhfuil an t-ainm céanna, go maith ansin dtosaíonn tú díreach ag nascadh iad le chéile. Agus b'fhéidir tú a choinneáil curtha in eagar iad ord aibítre, b'fhéidir nach bhfuil tú. Ach ar a laghad anois táimid tar éis an dinimiceas. Mar sin, ar an taobh amháin atá againn Super tapa am tairiseach, agus de chineál ar am líneach baint acu má tá na liostaí nasctha tús a fháil beagán fada. 

Mar sin, den chineál seo a amaideach, bliain joke geeky ó shin. Ag an CS50 hack-a-thon, nuair mic léinn seiceáil i, roinnt TF nó CA gach bliain cuí tá sé greannmhar a chur suas comhartha mar seo, áit a bhfuil sé ach Ciallaíonn má thosaíonn do ainm le A, dul ar an mbealach. Má thosaíonn d'ainm le B, téigh this-- OK, tá sé greannmhar b'fhéidir níos déanaí sa seimeastar. Ach níl ceann eile bhealach é seo a dhéanamh, freisin. Tar ar ais go dtí go. 

Mar sin, níl an struchtúr. Agus is é seo ár deireanach Struchtúr don lá atá inniu, a bhfuil rud éigin a dtugtar Trie. T-R-I-E, atá ar chúis éigin is gearr le haghaidh aisghabhála, ach tá sé ar a dtugtar Trie. Mar sin, tá Trie eile suimiúil amalgam de ar a lán de na smaointe. Tá sé ina crann, a againn le feiceáil roimh. Níl sé ina crann cuardaigh dénártha. Tá sé ina crann le haon líon na leanaí, ach gach ceann de na páistí i Trie Is eagar. Le sraith de mhéid, a rá, 26 nó b'fhéidir 27 más mian leat chun tacú ainmneacha hyphenated nó uaschamóga in ainmneacha na ndaoine. 

Agus mar sin tá sé seo le struchtúr sonraí. Agus má fhéachann tú ó bharr go bun, mar má tú breathnú ar an nód barr ann, M, dírithe ar an rud leftmost ann, atá ansin A, X, W, E, L, L. Tá an ach struchtúr sonraí a treallach Is stóráil ainmneacha daoine. Agus is é Maxwell stóráilte ag díreach tar éis chonair na eagar go eagar do eagar. Ach cad atá iontach faoi é Trie go, cé go liosta nasctha agus fiú , is é an chuid is fearr againn gotten riamh le sraith am líneach nó logartamach lorg am duine éigin suas. I struchtúr seo sonraí de Trie, más rud é Tá mo struchtúr sonraí ainm amháin ann agus tá mé ag lorg Maxwell, tá mé ag dul a fháil dó go leor go tapa. Táim díreach tar éis do M-A-X-W-E-L-L. Má struchtúr seo sonraí, ag gcodarsnacht leis sin, má tá N milliún, má tá ann milliún ainmneacha i struchtúr seo sonraí, Maxwell é fós ag dul a bheith discoverable amháin tar éis M-A-X-W-E-L-L céimeanna. Agus céimeanna David-- D-A-V-I-D. I bhfocail eile, trí thógáil struchtúr sonraí go Fuair ​​gach ceann de na arrays, gach ceann acu iad féin a tacú le rochtain randamach, Is féidir liom tosú ag lorg suas daoine ainm ag baint úsáide as méid ama go bhfuil i gcomhréir leis an uimhir na rudaí i struchtúr sonraí, cosúil le milliún ainmneacha atá ann cheana féin. An méid ama a thógann sé dom a fháil M-A-X-W-E-L-L i struchtúr seo sonraí is comhréireach gan an méid de na struchtúr sonraí, ach le fad an t-ainm. Agus go réalaíoch an ainmneacha beimid ag féachaint suas Tá riamh ag dul a bheith craiceáilte fada. B'fhéidir go bhfuil duine éigin a charachtar 10 ainm, 20 ainm carachtar. Tá sé cinnte críochta, ceart? Tá an duine ar an Domhan a Tá an t-ainm is faide agus is féidir, ach tá an t-ainm tairiseach luach fhad, ceart? Ní chuireann sé athrú in aon chiall. Mar sin, ar an mbealach seo, tá muid a bhaint amach struchtúr sonraí is é sin am tairiseach breathnú-suas. Déanann sé a ghlacadh roinnt céimeanna ag brath ar fhad an ionchur, ach nach bhfuil an líon na n-ainm i struchtúr sonraí. Mar sin má dúbailte a chuirimid ar líon na n-ainmneacha an bhliain seo chugainn ó billiún go dtí dhá billiún, chinneadh Maxwell ag dul a ghlacadh an líon beacht céanna seacht céimeanna a fháil dó. Agus mar sin is cosúil go bhfuil bainte amach ár Soitheach Naofa de am ag rith. 

Mar sin, cúpla fógraí tapaidh. Tá tráth na gceist náid ag teacht suas. Níos mó ar sin ar an gcúrsa ar an láithreán gréasáin thar an chéad chúpla lá. Dé Luain lecture-- tá sé ina lá saoire anseo ag Harvard ar an Luan. Níl sé i New Haven, mar sin táimid ag cur an rang go Haven nua do léacht ar an Luan. Beidh gach rud a bheith scannánú agus sruthaithe beo mar is gnách, ach ligean ar deireadh lá atá inniu ann le dara gearrthóg 30 ar a dtugtar "Smaointe Deep" ag Daven Farnham, a Bhí spreag an bhliain seo caite ag Dé Sathairn "Smaointe Deep" Night Live ar Jack Handy, a ba chóir a dhéanamh anois ciall. 

SCANNÁN: Agus anois, "Deep Smaointe "ag Daven Farnham. Tábla hash. 

Cainteoir 1: Ceart go leor, sin é do anois. Beidh orainn a fheiceann tú an tseachtain seo chugainn. 

DOUG: Chun féachaint air i ngníomh. Mar sin, a ligean ar ghlacadh le breathnú ar an gceart sin anois. Mar sin anseo, ní mór dúinn le sraith neamhshórtáilte. 

Ian: Doug, is féidir leat dul ar aghaidh agus atosú seo le haghaidh amháin dara, le do thoil. Ceart go leor, tá ceamaraí rollta, mar sin gníomh nuair a bhíonn tú réidh, Doug, ceart go leor? DOUG: Ceart go leor, mar sin cad againn tá anseo tá sraith neamhshórtáilte. Agus tá mé daite gach ceann de na heilimintí dearg a chur in iúl go bhfuil sé, i ndáiríre, neamhshórtáilte. Mar sin, chun cuimhne go bhfuil an chéad rud a dhéanann muid Is muid a shórtáil an leath clé den eagar. Ansin, táimid ag shórtáil an ceart leath de na eagar. Agus ya-da, ya-da, ya-da, táimid ag merge le chéile iad. Agus ní mór dúinn raon hiomlán sórtáilte. Mar sin tá go conas a chumasadh saghas oibreacha. 

Ian: Whoa, whoa, whoa, gearrtha, gearrtha, gearrtha, gearrtha. Doug, ní féidir leat ach ya-da, ya-da, ya-da, do bhealach a dhéanamh tríd merge saghas. 

DOUG: Rinne mé díreach tar éis. Tá sé ceart go leor. Tá muid go maith chun dul. A ligean ar a choimeád ach rollta. Mar sin, mar sin féin, 

Ian: Tá tú a mhíniú sé níos iomláine ná sin. Sin ní hamháin go leor. DOUG: Ian, ní dhéanaimid Ní mór dul ar ais le ceann amháin. Tá sé ceart go leor. Mar sin féin, má leanaimid le merge-- Ian, tá muid i lár an scannánú. 

Ian: Tá a fhios agam. Agus ní féidir linn ach ya-da, ya-da, ya-da, tríd an bpróiseas iomlán. Tá tú a mhíniú conas an dá thaobh a fháil chumasc le chéile. 

DOUG: Ach tá muid cheana Mhínigh conas an dá sides-- 

Ian: Tá tú a thaispeántar ach iad sraith chumasadh. DOUG: Tá a fhios acu ar an bpróiseas. Tá siad breá. Táimid tar éis imithe níos mó ná é deich n-uaire. 

Ian: ndearna tú díreach ceart níos mó ná é. Táimid ag dul ar ais go dtí ceann amháin, is féidir leat Ní féidir leat ya-da, ya-da níos mó ná é. Ceart go leor, ar ais go dtí ceann amháin. 

DOUG: Caithfidh mé dul ar ais trí gach ceann de na sleamhnáin? Mo Dhia. Tá sé cosúil leis an séú am, Ian. Tá sé ceart go leor. 

Ian: Gach ceart. Tú réidh? Mór. Gníomh.