Jason Hirschhorn: Fáilte gach duine chuig an Rannóg Seacht. Tá muid i seachtain seacht den chúrsa. Agus seo Déardaoin teacht Tá Oíche Shamhna mar sin tá mé gléasta suas mar Pumpkin. Ní raibh mé in ann crom os cionn agus a chur ar mo bhróga, ionas go mbeidh an fáth mé ach ag caitheamh stocaí. Tá mé chomh maith nach bhfuil ag caitheamh aon rud faoi seo, mar sin ní féidir liom é a ghlacadh amach má tá sé distracting a thabhairt duit. Mé leithscéal a ghabháil roimh ré le haghaidh sin. Ní gá duit a shamhlú cad atá ar siúl. Táim ag caitheamh dhornálaithe. Mar sin, tá sé ar fad go maith. 

Tá scéilín níos faide faoi cén fáth mé gléasta mar pumpkin, ach tá mé ag dul chun ach amháin go feadh déanaí sa chuid seo toisc go bhfuil mé ag iarraidh chun tús a chur. Tá a lán de na rudaí spreagúil chun dul thar an tseachtain seo. Chuid is mó acu a bhaineann go díreach leis an leagtha fhadhb na seachtaine, misspellings. Táimid ag dul a bheith ag dul thar nasctha liostaí agus táblaí hash as roinn an. Chuir mé an liosta seo suas gach seachtain, liosta de na acmhainní duit chun cabhrú leat le an t-ábhar ar an gcúrsa seo. Más rud é ag caillteanas nó má lorg roinnt tuilleadh eolais a fháil, féach ar cheann de na na hacmhainní seo. 

Arís, is é pset6 misspellings, na seachtaine seo pset. Agus spreagann sé chomh maith agat, agus mé spreagann tú, a úsáid roinnt eile acmhainní go sonrach le haghaidh an pset. Go háirithe, na trí Tá mé liostaithe suas ar an scáileán - gdb, a bhíomar eolach agus ag baint úsáide as ar feadh tamaill anois, ag dul a bheith an-cabhrach an tseachtain seo. Mar sin, chuir mé suas anseo. Ach aon uair a bhíonn tú ag obair le C, ba chóir duit a bheith i gcónaí ag baint úsáide as gdb a dífhabhtaigh do na cláir. An tseachtain seo valgrind freisin. An bhfuil fhios ag aon duine cad a dhéanann valgrind? 

LUCHT ÉISTEACHTA: Seiceálacha sé do leaks cuimhne? 

Jason Hirschhorn: Valgrind seiceálacha i gcomhair sceitheanna cuimhne. Mar sin, má tá tú rud éigin i do malloc clár, tá tú ag lorg chuimhne. Ag deireadh na bliana do chláir, tá tú a scríobh saor in aisce ar gach rud atá tú malloced a thabhairt ar an chuimhne ar ais. Más rud é nach bhfuil tú ag scríobh saor in aisce ag an deireadh agus Tagann do chlár chun críche, Beidh gach rud go huathoibríoch a freed. Agus do chláir beag, tá sé Ní go mór go leor. Ach má tá tú ag scríobh ag rith níos faide Clár nach scor, gá, i gceann cúpla nóiméad nó cúpla soicind, ansin leaks cuimhne Is féidir a bheith le déileáil go mór. 

Mar sin, le haghaidh pset6, táthar ag súil go beidh ort náid leaks cuimhne le do chlár. Chun seiceáil i gcomhair sceitheanna cuimhne, valgrind reáchtáil agus beidh sé a thabhairt duit roinnt deas aschur ligean ar cíos a fhios agat cé acu nó nach raibh gach rud saor in aisce. Beidh muid a chleachtadh leis níos déanaí lá atá inniu ann, tá súil againn. 

Ar deireadh, an t-ordú difr. Úsáid tú rud éigin cosúil leis i pset5 leis an uirlis peek. Ceadaíodh leat chun breathnú taobh istigh. Úsáid tú freisin difr, freisin, in aghaidh an fhadhb a leagtar spec. Ach i cheadaítear duit comparáid a dhéanamh idir dhá chomhad. D'fhéadfá comparáid a dhéanamh idir an comhad bitmap agus ceanntásca info de réiteach foirne agus do réiteach i pset5 má roghnaigh tú í a úsáid. Beidh LD ligfidh tú chun sin a dhéanamh, chomh maith. Is féidir leat a chur i gcomparáid leis an freagra ceart do fadhb na seachtaine seo leagtha chun do fhreagra agus a fheiceáil má línte sé suas nó a fheiceáil i gcás ina bhfuil na hearráidí. 

Mar sin, tá na trí uirlisí maith go ba chóir duit a úsáid le haghaidh an tseachtain seo, agus cinnte a sheiceáil le do chlár leis na trí uirlis roimh casadh sé isteach Arís, mar a bhfuil mé luaite gach seachtain, má tá aon aiseolas dom - araon dearfach agus cuiditheach - bhraitheann saor chun bheith mar cheannasaí ar an suíomh gréasáin ag bun an sleamhnán agus ionchur ann. Mé buíoch i ndáiríre ar bith agus gach aiseolas. Agus má thugann tú dom rudaí ar leith go Is féidir liom a dhéanamh chun feabhas a chur nó a bhfuil mé ag déanamh go maith go mhaith leat mé a leanúint ar aghaidh, a chur mé go dtí croí agus gur iarracht deacair a bheith ag éisteacht le do chuid aiseolais. Ní féidir liom gealltanas mé ag dul a dhéanamh gach rud, áfach, cosúil le caitheamh le pumpkin éadaí gach seachtain. 

Mar sin, táimid ag dul a chaitheamh an chuid is mó de alt, mar a luaigh mé, ag caint faoi liostaí nasctha agus táblaí hash, a beidh siad i bhfeidhm go díreach chuig an fhadhb a leagtar an tseachtain seo. Liostaí Nasctha beidh muid ag dul thar réasúnta go tapa mar tá muid chaith beagán cothrom ama ag dul thar in alt. Agus mar sin beidh orainn a fháil díreach isteach ar an fadhbanna códaithe le haghaidh liostaí nasctha. Agus ansin ag an deireadh beidh muid ag labhairt faoi táblaí hash agus conas a bhaineann siad leis an fhadhb na seachtaine leagtha. 

Tá tú le feiceáil cód seo roimhe seo. Is é seo an struct, agus tá sé a shainiú rud ar a dtugtar nua nód. Agus taobh istigh de nód tá slánuimhir ar dheis anseo, agus tá pointeoir a nód eile. Againn atá le feiceáil roimh seo. Tá sé seo ag teacht suas le haghaidh cúpla seachtain anois. Nascann sé leideanna, a tá muid ag obair le, agus structs, a ligeann dúinn a chur le chéile dhá éagsúla rudaí i gcineál amháin sonraí. 

Níl a lán ar siúl ar an scáileán. Ach ba chóir go léir go mbeadh sé réasúnta eolach leat. Ar an chéad líne, ní mór dúinn dhearbhú nód nua. Agus ansin taobh istigh an nód nua, leag mé an tslánuimhir sa nód le ceann amháin. Feicimid ar an chéad líne eile Tá mé ag déanamh printf ordú, ach tá mé grayed amach an t-ordú printf mar gheall ar an i ndáiríre Is cuid thábhachtach líne seo anseo - new_node.n. Cad a chiallaíonn an ponc? 

LUCHT ÉISTEACHTA: Téigh go dtí an nód agus measúnú a dhéanamh ar luach n chun é. 

Jason Hirschhorn: Sin go díreach ceart. Ciallaíonn Ponc rochtain a fháil ar an chuid n an nód nua. Dhéanann an chéad líne eile cad é? Michael. 

LUCHT ÉISTEACHTA: Cruthaíonn sé nód eile Beidh an bpointe sin go dtí an nód nua. 

Jason Hirschhorn: Mar sin, ní dhéanann sé a chruthú nód nua. Cruthaíonn sé cad é? 

LUCHT ÉISTEACHTA: A pointeoir. 

Jason Hirschhorn: A pointeoir chuig nód, mar atá léirithe ag nód seo * anseo. Mar sin, cruthaíonn sé pointeoir a nód. Agus a nód bhfuil dírithe go a, Micheál? 

LUCHT ÉISTEACHTA: nód Nua? 

Jason Hirschhorn: nód Nua. Agus tá sé ag cur in iúl ann mar gheall tá muid thug sé an seoladh an nód nua. Agus anois sa líne seo fheicimid dhá bhealach éagsúla in iúl an rud céanna. Agus bhí mé a chur in iúl conas na Tá dhá rud mar an gcéanna. Sa chéad líne, téigh i dúinn an pointeoir. Mar sin, théann muid go dtí an nód. Sin cad a chiallaíonn sé seo réalta. Againn atá le feiceáil go roimh le leideanna. Téigh go dtí an nód. Sin i lúibíní. Agus ansin teacht tríd an t-oibreoir ponc an ghné n an nód. 

Mar sin, go bhfuil ag cur an chomhréir chonaic muid ar dheis anseo agus anois as é a úsáid le pointeoir. Ar ndóigh, faigheann sé de chineál ar gnóthach má bhfuil tú ag scríobh leis na lúibíní - go réalta agus go ponc. Faigheann sé beagán gnóthach. Mar sin, ní mór dúinn roinnt shiúcra syntactic. Agus an líne seo ar dheis anseo - ptr_node-> n. Sin a dhéanann an rud céanna cruinn. Mar sin, iad siúd dá línte de chód coibhéiseach agus beidh a dhéanamh an rud ceannann céanna. 

Ach bhí mé a chur in iúl dóibh siúd amach roimh théann muid ar bith eile ionas go dtuigeann tú go bhfuil an rud ceart anseo i ndáiríre ach shiúcra syntactic chun dereferencing an pointeoir agus ansin dul chun an chuid den struct n. Ceisteanna ar bith faoi seo sleamhnán? OK. 

Mar sin, táimid ag dul chun dul trí cúpla oibríochtaí gur féidir leat a dhéanamh ar liostaí nasctha. Tá liosta nasctha, cuimhne, sraith de nóid go pointe chéile. Agus muid ag tús a chur go ginearálta le pointeoir ar a dtugtar ceann, go ginearálta, pointí sin le an chéad rud ar an liosta. Mar sin, ar an gcéad líne anseo, táimid ag Tá an chéad ár n-L bunaidh. Mar sin, go bhfuil rud is féidir leat smaoineamh ar - seo téacs ar dheis anseo is féidir leat smaoineamh ar mar a ach an pointeoir againn stóráil go bhfuil áit éigin pointí go dtí an chéad eilimint. Agus sa liosta seo nasctha ní mór dúinn ceithre nóid. Tá gach nód bosca mór. An bosca mó taobh istigh den mhór Tá an bosca ar an chuid slánuimhir. Agus ansin ní mór dúinn cuid pointeoir. 

Níl na boscaí a tharraingt le scála toisc cé chomh mór is slánuimhir i bytes? Cé chomh mór anois? Ceithre. Agus cé chomh mór atá pointeoir? Ceithre. Mar sin, i ndáiríre, má bhí muid a tharraingt seo de réir scála dá boscaí Bheadh ​​an méid céanna. Sa chás seo, ba mhaith linn a chur isteach rud éigin isteach ar an liosta nasctha. Mar sin, is féidir leat a fheiceáil síos anseo táimid ag chur isteach cúig Traverse muid tríd an liosta nasctha, a aimsiú i gcás cúig Téann, agus cuir isteach ansin é. 

A ligean ar bhriseadh síos agus dul le beagán níos moille. Tá mé ag dul a chur in iúl don bhord. Mar sin, ní mór dúinn ár n-nód cúig go táimid tar éis a cruthaíodh i mallocs. Cén fáth go bhfuil gach duine ag gáire? Just a kidding. OK. Mar sin, tá muid malloced cúig. Táimid tar éis a cruthaíodh an nód áit éigin eile. Tá sé réidh le dul. Tús a chur againn ar an tosach ár liosta le dhá. Agus ba mhaith linn a chur isteach ar bhealach curtha in eagar. 

Mar sin, má fheiceann muid beirt agus ba mhaith linn a chur ar i gcúig, cad a dhéanann muid nuair a fheiceann muid rud éigin níos lú ná dúinn? Cad é? Ba mhaith linn a chur isteach cúig isteach liosta nasctha, a choinneáil curtha in eagar é. Feicimid uimhir a dó. Mar sin, cad a dhéanaimid? Marcus? 

LUCHT ÉISTEACHTA: Cuir glaoch ar an pointeoir leis an nód seo chugainn. 

Jason Hirschhorn: Agus cén fáth a dhéanamh théann muid go dtí an chéad cheann eile? 

LUCHT ÉISTEACHTA: Toisc go bhfuil sé ar an nód seo chugainn ar an liosta. Agus tá a fhios againn ach go suíomh eile. 

Jason Hirschhorn: Agus is é cúig níos mó ná dhá, go háirithe. Mar ba mhaith linn a choinneáil in eagar. Mar sin, tá cúig mó ná dhá. Mar sin, sinn ag dul ar aghaidh go dtí an chéad cheann eile. Agus a bhaint amach againn anois ceithre. Agus cad a tharlaíonn nuair a shroicheann muid ceithre? 

Cúig is faide ná ceithre. Mar sin, linn a choinneáil ag dul. Agus anois tá muid ag sé cinn. Agus cad a dhéanann muid a fheiceáil ag sé? Sea, Carlos? 

LUCHT ÉISTEACHTA: Tá Sé níos mó ná cúig. 

Jason Hirschhorn: Tá Sé níos mó ná cúig. Mar sin, sin an áit ba mhaith linn a chur isteach cúig. Mar sin féin, a choinneáil i gcuimhne go má táimid ach go bhfuil pointeoir amháin anseo - is é seo ár pointeoir breise go traversing tríd an liosta. Agus tá muid ag cur in iúl go dtí sé. Táimid tar éis a rian caillte ar cad Tagann roimh sé. Mar sin, más mian linn rud éigin a chur isteach i an liosta seo a choinneáil in eagar, táimid ag gá is dócha cé mhéad leideanna? 

LUCHT ÉISTEACHTA: Dhá. 

Jason HIRSCHORN: Dó. Ceann riain an láthair a choinneáil amháin agus ceann amháin súil a choinneáil an ceann roimhe sin. Tá sé seo ach liosta nasctha ina n-aonar. Téann sé ach treo amháin. Má bhí againn liosta nasctha doubly, i gcás ina gach rud a bhí dírithe ar an rud tar éis dó agus an rud os a comhair, ansin Ní bheadh ​​gá dúinn a dhéanamh. Ach sa chás seo nach bhfuil muid ag iarraidh a chailleadh súil a choinneáil ar cad a tháinig ós ár gcomhair i gcás ní mór dúinn a chur isteach cúig áit éigin i lár. Abair bhí muid ag chur isteach naoi. Cad a tharlódh nuair a fuair muid go dtí a hocht? 

LUCHT ÉISTEACHTA: Gur mhaith leat a a fháil ar an bpointe null. In áit a bhfuil pointe null gur mhaith leat a bheith a chur eilimint agus ansin tá sé pointe a naoi. 

Jason HIRSCHORN: Go díreach. Mar sin, a fháil againn ocht. A bhaint amach againn an deireadh an liosta mar gheall ar seo dírithe ar margadh saothair. Agus anois, in ionad a bheith pointe sé a Eolas faoin margadh saothair ní mór dúinn é a pointe go dtí ár nód nua. Agus leag muid an pointeoir i ár n-nód nua a margadh saothair. An bhfuil aon cheist aon duine faoi ​​chur isteach? Cad a tharlaíonn má ní féidir liom cúram faoi a choinneáil ar an liosta in eagar? 

LUCHT ÉISTEACHTA: Bata ag an tús nó an deireadh. 

Jason HIRSCHORN: Bata ag an tús nó deireadh. Cén ceann ba chóir dúinn a dhéanamh? Bobby? Cén fáth an deireadh? 

LUCHT ÉISTEACHTA: Mar gheall ar an tús Tá líonta cheana féin. 

Jason HIRSCHORN: OK. Is é an tús cheana féin a líonadh. Cé atá ag iarraidh a argóint i gcoinne Bobby. Marcus. 

LUCHT ÉISTEACHTA: Bhuel Ba mhaith leat is dócha a bata sé ag an tús mar gheall ar a mhalairt má chuir tú é ag an deireadh gur mhaith leat a lean an liosta ar fad. 

Jason HIRSCHORN: Go díreach. Mar sin, má tá muid ag smaoineamh faoi runtime, ar an runtime de chur isteach ag an deireadh bheadh ​​n, an méid seo. Cad é an runtime O mór de chur isteach ag an tús? Am tairiseach. Mar sin, más rud é nach bhfuil tú faoi chúram faoi choimeád rud éigin curtha in eagar, i bhfad níos fearr go dtí díreach isteach ag tús an liosta seo. Agus is féidir a dhéanamh in am i gcónaí. 

OK. Tá oibríocht Aghaidh a aimsiú, a eile - tá muid phrased mar seo cuardaigh. Ach táimid ag dul chun breathnú tríd an liosta nasctha do roinnt réad. Guys Tá tú ag feiceáil cód le haghaidh cuardach a dhéanamh roimh i léacht. Ach rinne muid saghas díreach sé le isteach, nó ar a laghad a chur isteach rud curtha in eagar. Tá tú ag breathnú tríd, nód ag dul trí nód, go dtí go bhfaighidh tú an uimhir go bhfuil tú lorg. Cad a tharlaíonn má shroicheann tú an deireadh an liosta? Abair Táim ag lorg naoi agus mé teacht ar an deireadh an liosta. Cad a dhéanaimid? 

LUCHT ÉISTEACHTA: Fill ar ais bréagach? 

Jason HIRSCHORN: Fill ar ais bréagach. Ní raibh muid a aimsiú. Má shroicheann tú an deireadh an liosta agus nach raibh tú teacht ar an líon atá tú lorg, nach bhfuil sé in ann. Ceisteanna ar bith faoi a aimsiú? Má bhí an liosta sórtáilte, cad a bheadh a bheith difriúil le haghaidh ár chuardach? Yeah. 

LUCHT ÉISTEACHTA: Bheadh ​​sé teacht ar an chéad luach go bhfuil níos mó ná an ceann bhfuil tú ag lorg agus ansin ar ais bréagach. 

Jason HIRSCHORN: Go díreach. Mar sin, má tá sé liosta sórtáilte, má fhaigheann muid go dtí rud éigin go bhfuil níos mó ná an méid táimid ag lorg, ní mór dúinn a a choinneáil ag dul go dtí deireadh an liosta. Is féidir linn a ag an bpointe sin ar ais bréagach toisc nach bhfuil muid ag dul chun é a fháil. An cheist anois, tá muid Labhair faoi choinneáil liostaí nasctha curtha in eagar, iad a choinneáil neamhshórtáilte. Sin ag dul a bheith rud éigin go bhfuil tú is dócha ag dul a bheith acu chun smaoineamh ar nuair atá leagtha fhadhb códaithe cúig má tá tú roghnú tábla hash le ar leithligh chuige shlabhrú, a beidh muid ag labhairt faoi níos déanaí. 

Ach is fiú é a choinneáil ar an liosta sórtáilte agus ansin a bheith in ann a bhfuil b'fhéidir cuardaigh níos tapúla? Nó tá sé níos fearr a chur isteach go tapa rud éigin i runtime leanúnach ach ansin Tá cuardach a thuilleadh? Sin tradeoff ceart ann go bhfuil tú a fháil chun cinneadh a dhéanamh cad é níos oiriúnaí do do fhadhb ar leith. Agus ní níl gá amháin freagra go hiomlán ceart. Ach tá sé cinnte le cinneadh a gheobhaidh tú a dhéanamh, agus is dócha go maith a chosaint go i, a rá, nóta nó dhá cén fáth roghnaigh tú ceann amháin thar an gceann eile. 

Mar fhocal scoir, a scriosadh. Againn atá le feiceáil scriosadh. Tá sé cosúil le cuardach. Táimid an eilimint. Abair táimid ag iarraidh a scriosadh sé. Mar sin, feicimid sé ar dheis anseo. An rud atá againn a chinntiú go ndéanaimid dhéanamh ná go bhfuil cuma cad dírithe ar sé - mar a fheiceann muid sa chéim dhá síos anseo - is cuma cad atá dírithe ar shé riachtanais a skip sé anois agus a athrú go is cuma cad é sé dírithe ar. Nílimid ag iarraidh a dílleachta riamh an chuid eile den ár liosta dearmad ar a shocrú go pointeoir roimhe sin. Agus ansin uaireanta, ag brath ar an gclár, beidh siad díreach scriosadh an nód go hiomlán. Uaireanta beidh tú ag iarraidh a thabhairt ar ais an luach sin sa nód. Mar sin tá go conas a oibríonn scriosadh. Ceisteanna ar bith ar scriosadh? 

LUCHT ÉISTEACHTA: Mar sin, má tá tú ag dul a scriosadh sé, ba mhaith leat a úsáid ach saor in aisce mar is dócha go raibh sé malloced? 

Jason HIRSCHORN: Más mian leat saor in aisce rud éigin go díreach ceart agus tú malloced sé. Abair bhíomar ag iarraidh a thabhairt ar ais an luach. D'fhéadfadh muid ar ais sé agus ansin saor in aisce an nód agus saor in aisce glaoch ar sé. Nó ba mhaith linn glaoch dócha saor in aisce ar dtús agus ansin ar ais sé. 

OK. Mar sin, a ligean ar bogadh ar aghaidh a chleachtadh códaithe. Táimid ag dul chun cód thrí fheidhm. Is é an chéad cheann ar a dtugtar insert_node. Mar sin, tá tú cód gur Ríomhphost mé tú, agus má tá tú ag breathnú ar seo níos déanaí ar Is féidir leat rochtain a fháil ar an cód i linked.c ar an suíomh gréasáin CS50. Ach i linked.c, níl cuid Cód creatlach go bhfuil cheana féin scríofa ar do shon. Agus ansin níl a feidhmeanna cúpla is gá duit a scríobh. 

An Chéad táimid ag dul chun scríobh insert_node. Agus cad a dhéanann insert_node is é sin Ionsáigh slánuimhir. Agus tá tú ag tabhairt an tslánuimhir isteach i liosta nasctha. Agus go háirithe, is gá duit a choinneáil ar an liosta in eagar ón gceann is lú go dtí mó. Chomh maith leis sin, nach bhfuil tú ag iarraidh a isteach aon dúbailt ar. Mar fhocal scoir, is féidir leat a fheiceáil insert_node tuairisceáin bool. Mar sin, tá tú ag ceaptha chun ligean fhios ag an úsáideoir cibé acu atá nó nach raibh an iatán rathúil ag filleadh fíor nó bréagach. Ag deireadh an chláir seo - agus ar an gcéim seo nach gá duit a bheith buartha faoi rud ar bith a shaoradh. Mar sin, gach tú ag déanamh ag cur slánuimhir agus é a chur isteach i liosta. 

Is é sin cad tá mé ag iarraidh ort a dhéanamh anois. Arís, sa linked.c, a bhfuil tú go léir a bhfuil, is é an cód creatlach. Agus ba chóir duit a fheiceáil i dtreo an ghrinnill an dearbhú fheidhm sampla. Mar sin féin, roimh dul isteach códaithe é i C, mé a spreagadh go mór leat chun dul trí na céimeanna atá déanta againn ag cleachtadh gach seachtain. Táimid imithe cheana féin trí pictiúr de seo. Mar sin, ba chóir duit a bhfuil roinnt tuiscint conas a oibríonn sé seo. Ach ba mhaith liom tú a spreagadh chun scríobh roinnt pseudocode roimh tumadóireacht isteach Agus táimid ag dul chun dul thar pseudocode mar ghrúpa. Agus ansin nuair a tá tú atá scríofa do pseudocode, agus aon uair amháin againn i scríbhinn ar ár pseudocode mar ghrúpa, is féidir leat dul isteach códaithe i C. 

Mar cinnirí suas, an fheidhm insert_node Is dócha go bhfuil an trickiest de na trí táimid ag dul a scríobh mar gheall mé Chuir roinnt srianta breise a do chláir, go háirithe go nach bhfuil tú ag dul a chur isteach ar aon dúblaigh agus go bhfuil an liosta Ba chóir go bhfanfaidh sórtáilte. Mar sin, tá sé seo le clár neamh-fánach gur gá duit chun cód. Agus cén fáth nach bhfuil tú 06:55 nóiméad ach a fháil ag obair ar an pseudocode agus an cód. Agus ansin beidh muid ag tosú dul mar ghrúpa. Arís, má tá aon cheist agat ach ardaigh do lámh agus beidh mé ag teacht timpeall. . 

Déanann muid freisin go ginearálta ar na - nó nach féidir liom a rá go sainráite agat Is féidir obair le daoine. Ach ar ndóigh, a spreagadh mé go mór leat, má tá ceisteanna agat, a iarraidh ar an comharsa suí in aice leat nó fiú ag obair le duine éigin eile más mian leat a. Ní bhaineann sé seo a bheith duine aonair gníomhaíocht adh. 

Let tús le scríobh roinnt pseudocode ar an mbord. Cé atá in ann a thabhairt dom an chéad líne pseudocode don chlár seo? Chun an fheidhm seo, in áit - insert_node. Alden? 

LUCHT ÉISTEACHTA: Mar sin, bhí an chéad rud a rinne mé chruthú pointeoir nua chun an nód agus mé initialized ag cur in iúl dó chun an céanna rud go bhfuil an liosta dírithe ar. 

Jason HIRSCHORN: OK. Mar sin, tá tú ag a chruthú pointeoir nua leis an liosta, ní leis an nód. 

LUCHT ÉISTEACHTA: Ceart. Yeah. 

Jason HIRSCHORN: OK. Agus ansin cad ba mhaith linn a dhéanamh? Cad ina dhiaidh sin? Cad mar gheall ar an nód? Ní chuirimid bhfuil nód. Tá muid ach luach. Más mian linn a chur isteach nód, cad a dhéanann muid Ní mór a dhéanamh ar dtús sula féidir linn fiú smaoineamh ar chur isteach air? 

LUCHT ÉISTEACHTA: Ó, tá brón orainn. ní mór dúinn spás a malloc le haghaidh nód. 

Jason HIRSCHORN: Den scoth. A ligean ar a dhéanamh - OK. Ní féidir teacht ar an ard. OK. Táimid ag dul chun dul síos, agus ansin táimid ag baint úsáide as dhá cholún. Ní féidir liom dul go - OK. Cruthaigh nód nua. Is féidir leat a chruthú pointeoir eile a liostú nó is féidir leat é a úsáid ach liosta mar atá sé. Ní gá duit i ndáiríre a dhéanamh. 

Mar sin, a chruthú dúinn nód nua. Breataine. Sin an méid a dhéanaimid ar dtús. Cad é seo chugainn? 

LUCHT ÉISTEACHTA: Fan. Ar chóir dúinn a chruthú nód nua anois nó Ba chóir dúinn fanacht chun a chinntiú go níl aon dúblaigh den nód ar an liosta a chruthú sula againn é? 

Jason HIRSCHORN: Good question. A ligean ar a shealbhú gur le haghaidh níos déanaí mar gheall ar an chuid is mó den am a beidh orainn a bheith ag cruthú nód nua. Mar sin, beidh orainn a choinneáil go anseo. Ach tá go ceist mhaith. Má chruthaíonn muid é agus a fháil againn dúblach, cad ba cheart a dhéanann muid sular fhill? 

LUCHT ÉISTEACHTA: Saor in aisce é. 

Jason HIRSCHORN: Yeah. Is dócha saor in aisce é. OK. Cad a dhéanaimid tar éis dúinn a chruthú nód nua? Annie? 

LUCHT ÉISTEACHTA: Chuireamar an uimhir sa nód? 

Jason HIRSCHORN: Go díreach. Chuireamar an líon - malloc againn spás. Tá mé ag dul a fhágáil go ar fad mar líne amháin. Ach tá an ceart agat. Malloc muid spás, agus ansin chuir muid an líon isteach Is féidir linn a leagtar fiú an pointeoir chuid de a margadh saothair. Sin é go díreach ceart. Agus ansin cad mar gheall ina dhiaidh sin? Tharraing muid an pictiúr ar an mbord. Mar sin, cad a dhéanaimid? 

LUCHT ÉISTEACHTA: théann muid tríd an liosta. 

Jason HIRSCHORN: Téigh tríd an liosta. OK. Agus cad a dhéanann muid ag seiceáil ar gach nód. Kurt, cad a dhéanann muid a sheiceáil ar gach nód? 

LUCHT ÉISTEACHTA: Féach cé acu an luach na n is é sin nód níos mó ná an luach n ár n-nód. 

Jason HIRSCHORN: OK. Tá mé ag dul a dhéanamh - yera yeah, ceart go leor. Mar sin, tá sé n - Tá mé ag dul a rá má tá luach níos mó ná an nód, ansin cad a dhéanaimid? 

LUCHT ÉISTEACHTA: Bhuel, ansin dúinn isteach an rud ceart roimh sin. 

Jason HIRSCHORN: OK. Mar sin, má tá sé níos mó ná sin, ansin ba mhaith linn a chur isteach. Ach ba mhaith linn a chur isteach i gceart roimh mar ba mhaith linn gá freisin a bheith súil a choinneáil, ansin, ar an méid a bhí roimhe. Mar sin, cuir isteach roimh. Mar sin, chaill muid dócha rud éigin níos luaithe ar. Ní mór dúinn dócha a bheith a choinneáil súil a choinneáil ar cad atá ar siúl. Ach beidh orainn a fháil ar ais ann. Mar sin, cén luach atá níos lú ná? Kurt, cad a dhéanann muid a dhéanamh má Tá luach níos lú ná? 

LUCHT ÉISTEACHTA: Ansin tú a choinneáil ach ag dul amháin má tá sé an ceann deireanach. 

Jason HIRSCHORN: Is maith liom go bhfuil. Mar sin, téigh go dtí an nód seo chugainn. Mura bhfuil sé an ceann deireanach - táimid ag seiceáil dócha don i dtéarmaí riocht. Ach yeah, nód seo chugainn. Agus tá go bhfuil dul ró-íseal, mar sin beidh muid ag bogadh thar anseo. Ach más rud é - Is féidir le gach duine a fheiceáil seo? Má táimid comhionann cad a dhéanaimid? Má tá an luach táimid ag iarraidh a chur isteach is comhionann le luach an nód ar? Yeah? 

LUCHT ÉISTEACHTA: [inaudible]. 

Jason HIRSCHORN: Yeah. Mar gheall ar seo - Is Marcus ceart. D'fhéadfadh muid a bheith déanta b'fhéidir rud éigin difriúil. Ach ós rud go atá cruthaithe againn air, anseo ba chóir dúinn saor in aisce agus ansin ar ais. Ó buachaill. An bhfuil sin níos fearr? Conas is é sin? OK. Saor in aisce agus ansin cad a dhéanann muid ar ais, [inaudible]? OK. An bhfuil muid ag iarraidh rud ar bith? Mar sin, i gcás ina bhfuil a choinneáil orainn rian an nód roimh ré? 

LUCHT ÉISTEACHTA: Sílim go mbeadh sé dul tar éis a chruthú nód nua. 

Jason HIRSCHORN: OK. Mar sin, ag an tús beidh muid dócha - yera yeah, is féidir linn a chruthú pointeoir go dtí nua nód, cosúil le pointeoir nód roimhe sin agus pointeoir nód reatha. Mar sin, a ligean ar chur isteach go anseo. Cruthaigh reatha agus roimhe seo leideanna do na nóid. Ach nuair a dhéanann muid choigeartú siúd leideanna? Nuair a dhéanann muid é sin an cód? Jeff? 

LUCHT ÉISTEACHTA: - coinníollacha luacha? 

Jason HIRSCHORN: Cén amháin go háirithe? 

LUCHT ÉISTEACHTA: Tá mé ag dhaoine eatarthu díreach. Má tá luach níos mó ná an nód, ní chiallaíonn gur mian leat dul leis an nód seo chugainn? 

Jason Hirschhorn: Mar sin, má tá ár n-luach níos mó ná an luach an nód. 

LUCHT ÉISTEACHTA: Yeah, ansin gur mhaith leat a iarraidh a dul a thuilleadh síos ar an líne, ceart? 

Jason Hirschhorn: Ceart. Mar sin, ní féidir linn a cuir isteach é anseo. Má tá luach níos lú ná an nód, ansin théann muid go dtí an nód seo chugainn - nó ansin dúinn isteach roimh. 

LUCHT ÉISTEACHTA: Fan, a bhfuil sé seo Tá nód agus a luach? 

Jason Hirschhorn: Good question. Luach in aghaidh an sainmhíniú seo feidhm cad tá muid ag tugtha. Mar sin, is é luach an líon táimid tugtha. Mar sin, má tá an luach níos lú ná seo nód, ní mór dúinn am a chur isteach. Má tá luach níos mó ná an nód, théann muid go dtí an nód seo chugainn. Agus ar ais go dtí an cheist bhunaidh, áfach, i gcás - 

LUCHT ÉISTEACHTA: Má tá luach níos mó ná an nód. 

Jason Hirschhorn: Agus mar sin cad a dhéanann muid anseo? Sweet. Is é sin ceart. Tá mé ag dul ach a scríobh leideanna cothrom le dáta. Ach tá, leis an cheann reatha mbeadh tú sé cothrom le dáta a pointe go dtí an ceann eile. Rud ar bith eile táimid ag iarraidh? Mar sin, tá mé ag dul chun cineál seo cód an gedit isteach. Agus cé a dhéanfaidh mé seo, is féidir leat a bheith cúpla nóiméad níos mó a bheith ag obair ar códaithe seo i C. 

Mar sin, tá mé ionchur an pseudocode. Tá nóta mear sula bhfaigheann muid tús. Ní féidir linn a bheith in ann a fháil go hiomlán chríochnú seo i ngach trí cinn de na feidhmeanna sin. Tá réitigh chearta dóibh go mbeidh mé ríomhphost amach a thabhairt duit guys ndiaidh alt, agus beidh sé a chur sa phost ar CS50.net. Mar sin, ní féidir liom tú a spreagadh chun dul ag féachaint ar na hailt. Spreagadh mé leat chun iarracht seo ar do féin, agus ansin a bhaint as an cleachtas an fadhbanna le do chuid freagraí a sheiceáil. Tá siad go léir deartha chun go dlúth caidreamh agus cloí leis an méid Níl le déanamh agat ar an tsraith bhfadhb. Mar sin, is féidir liom a spreagadh duit a chleachtadh seo ar do chuid féin agus ansin a bhaint as an cód a seiceáil do chuid freagraí. Toisc bhfuil mé ag iarraidh a bogadh ar aghaidh go dtí hash táblaí ag pointe éigin sa rannóg. Mar sin, ní fhéadfadh muid a fháil tríd go léir. Ach beidh muid ag déanamh an oiread is féidir linn anois. 

OK. Lig dúinn tús a chur. Asam, conas is féidir linn a chruthú nód nua? 

LUCHT ÉISTEACHTA: Leat a dhéanamh struct *. 

Jason Hirschhorn: Mar sin, táimid Tá suas anseo. Ó, tá brón orainn. Bhí tú ag rá struct *. 

LUCHT ÉISTEACHTA: Agus ansin [? cineál?] nód nód nó c. 

Jason Hirschhorn: OK. Tá mé ag dul a ghlaoch air new_node ionas gur féidir linn fanacht comhsheasmhach. 

LUCHT ÉISTEACHTA: Agus ba mhaith leat a shocrú go go ceann, an chéad nód. 

Jason Hirschhorn: OK. Mar sin, anois an dírithe go - mar sin seo Ní chruthaigh nód nua go fóill. Tá sé seo dírithe ach leis an chéad nód ar an liosta. Conas is féidir liom a chruthú nód nua? Más gá mé spás a chruthú nód nua. Malloc. Agus cé chomh mór? 

LUCHT ÉISTEACHTA: An méid de na struct. 

Jason Hirschhorn: An méid an struct. Agus cad leis an struct ar a dtugtar? 

LUCHT ÉISTEACHTA: Nód? 

Jason Hirschhorn: Nód. Mar sin, malloc (deachúlach (nód)); Tugann sé seo dúinn spás. Agus is é an líne seo - Tá rud amháin mícheart ar an líne seo. An bhfuil new_node pointeoir le struct? Sin an t-ainm cineálach. Cad é - nód, go díreach. Tá sé ina nód *. Agus cad a dhéanaimid ceart tar éis malloc muid rud éigin, Asan? Cad é an chéad rud a dhéanann muid? Cad a tharlaíonn má nach ndéanann sé ag obair? 

LUCHT ÉISTEACHTA: Ó, seiceáil má tá sé pointí leis an nód? 

Jason Hirschhorn: Go díreach. Mar sin, má tá tú new_node ionann ionann Eolas faoin margadh saothair, cad a dhéanaimid? Tuairisceáin sé seo bool, an fheidhm seo. Go díreach. Breathnaíonn go maith. Rud ar bith a chur ann? Beidh muid rudaí a chur ag an deireadh. Ach go Breathnaíonn go maith go dtí seo. Cruthaigh leideanna reatha agus roimhe seo. Michael, conas is féidir liom é seo a dhéanamh? 

LUCHT ÉISTEACHTA: Ba mhaith leat a bheith a dhéanamh ar nód *. Gur mhaith leat a dhéanamh ní amháin do new_node ach le haghaidh an nóid atá againn cheana féin. 

Jason Hirschhorn: OK. Mar sin, an nód atá ann faoi láthair táimid ar. Feicfidh mé glaoch go Curr. Gach ceart. Táimid tar éis cinneadh ba mhaith linn a choinneáil dhá cheann mar is gá dúinn a fhios cad os a chomhair. Cad a dhéanann siad a fháil initialized leis? 

LUCHT ÉISTEACHTA: A luach ar ár liosta. 

Jason Hirschhorn: Mar sin, cad é an chéad rud ar ár liosta? Nó conas a bhfuil a fhios againn i gcás an ag tosú ar ár liosta é? 

LUCHT ÉISTEACHTA: Nach ritheadh ​​é isteach an fheidhm? 

Jason Hirschhorn: Ceart. Bhí sé a ritheadh ​​i gceart anseo. Mar sin, má tá sé gcuirfí isteach i fheidhm, an tús a chur ar an liosta, cad ba chóir dúinn leagtar reatha cothrom le? 

LUCHT ÉISTEACHTA: Liosta. 

Jason Hirschhorn: Liosta. Sin é go díreach ceart. Anois, tá sé an seoladh ar tús ár liosta. Agus cad faoi roimhe seo? 

LUCHT ÉISTEACHTA: Liosta lúide ceann amháin? 

Jason Hirschhorn: Níl níl aon rud roimhe. Mar sin, cad is féidir linn a dhéanamh aon rud a signify? 

LUCHT ÉISTEACHTA: Null. 

Jason Hirschhorn: Yeah. Go fuaimeanna cosúil le smaoineamh maith. Foirfe. Go raibh maith agat. Téigh tríd an liosta. Constantine, cé chomh fada is go bhfuil muid ag dul chun dul tríd an liosta? 

LUCHT ÉISTEACHTA: Go dtí teacht againn null. 

Jason Hirschhorn: OK. Mar sin, más rud é, agus, le haghaidh lúb. Cad atá á dhéanamh againn? 

LUCHT ÉISTEACHTA: B'fhéidir le haghaidh lúb? 

Jason Hirschhorn: Déanaimis a dhéanamh le haghaidh lúb. OK. 

LUCHT ÉISTEACHTA: Agus a rá againn - go dtí an pointeoir reatha Ní cothrom le Eolas faoin margadh saothair. 

Jason Hirschhorn: Mar sin, má tá a fhios againn ar an coinníoll, conas is féidir linn a scríobh lúb bunaithe ar thalamh an coinníoll sin. Cén cineál lúb ba chóir dúinn a úsáid? 

LUCHT ÉISTEACHTA: Cé. 

Jason Hirschhorn: Yeah. Sin a dhéanann ciall níos mó bunaithe ar uaire de cad a dúirt tú. Más mian linn ach dul isteach muid go mbeadh sé ach a fhios go bhfuil rud, bheadh ​​sé a dhéanamh ciall a dhéanamh lúb tamaill. Cé go bhfuil ann faoi láthair faoin margadh saothair cothrom, má tá luach níos lú ná an nód. Akshar, a thabhairt dom líne seo. 

LUCHT ÉISTEACHTA: Más reatha-> n n níos lú ná luach. Nó athrú go. Athraigh an lúibín. 

Jason Hirschhorn: Tá brón orm. 

LUCHT ÉISTEACHTA: Athraigh an lúibín. 

Jason Hirschhorn: Mar sin, má tá sé níos mó ná luach. Toisc go bhfuil mearbhall leis an trácht thuas, tá mé ag dul a dhéanamh sin. Ach tá. Má tá ár n-luach níos lú ná seo nód, cad a dhéanaimid? Ó. Tá mé sé ceart anseo. Ionsáigh roimh. OK. Conas is féidir linn é sin a dhéanamh? 

LUCHT ÉISTEACHTA: An bhfuil sé fós dom? 

Jason Hirschhorn: Yeah. 

LUCHT ÉISTEACHTA: Tá tú - new_node-> seo chugainn. 

Jason Hirschhorn: Mar sin, cad go bhfuil dul chun cothrom? 

LUCHT ÉISTEACHTA: Tá sé ag dul go dtí reatha comhionann. 

Jason Hirschhorn: Go díreach. Agus mar sin an ceann eile - céard eile is gá dúinn a thabhairt cothrom le dáta? 

LUCHT ÉISTEACHTA: Seiceáil más ionann caite null. 

Jason Hirschhorn: Má Roimhe Seo - mar sin is ionann má Dé null. 

LUCHT ÉISTEACHTA: Ciallaíonn sé ag dul a bheith ar an ceann. 

Jason Hirschhorn: Ciallaíonn tá sé a bheith ar an ceann. Mar sin, ansin cad a dhéanaimid? 

LUCHT ÉISTEACHTA: Déanann muid ceann ionann new_node. 

Jason Hirschhorn: Ceann is ionann new_node. Agus cén fáth ceann anseo, ní liostú? 

LUCHT ÉISTEACHTA: Toisc go bhfuil ceann domhanda athróg, a bhfuil an áit ag tosú. 

Jason Hirschhorn: Sweet. OK. Agus - 

LUCHT ÉISTEACHTA: Ansin a dhéanann tú eile rmh-> seo chugainn ionann new_node. Agus ansin tú ar ais fíor. 

Jason Hirschhorn: Cá a leag muid deireadh new_node? 

LUCHT ÉISTEACHTA: Ba mhaith liom - Leag mé go bhfuil ag an tús. 

Jason Hirschhorn: Mar sin, cad líne? 

LUCHT ÉISTEACHTA: Tar éis an dá ráiteas seiceáil má tá sé ar eolas. 

Jason Hirschhorn: Ceart anseo? 

LUCHT ÉISTEACHTA: Ba mhaith liom a dhéanamh new_node-> n is ionann luach. 

Jason Hirschhorn: Fuaimeanna maith. Is dócha a dhéanann sé ciall - ní dhéanaimid Ní mór a fháil amach cad liosta táimid ar toisc go bhfuil muid ag déileáil ach le liosta amháin. Mar sin, dearbhú feidhm níos fearr do tá sé seo ach chun fáil réidh le seo go hiomlán agus cuir isteach díreach luach i ceann. Ní gá fiú a fhios cad tá muid liosta isteach Ach beidh mé é a choimeád do anois agus ansin é a athrú ar thabhairt cothrom le dáta na sleamhnáin agus cód. Mar sin, go Breathnaíonn go maith do anois. Más luach - ar féidir leo a dhéanamh líne seo? Má - cad a dhéanann muid anseo, Noah. 

LUCHT ÉISTEACHTA: Má tá luach níos mó ná Curr-> n - 

Jason Hirschhorn: Conas a dhéanamh théann muid go dtí an nód seo chugainn? 

LUCHT ÉISTEACHTA: Curr-> Is n cothrom le new_node. 

Jason Hirschhorn: Mar sin, n Tá cén chuid den struct? An slánuimhir. Agus is é new_node pointeoir chuig nód. Mar sin, cén chuid den Curr ba chóir dúinn a thabhairt cothrom le dáta? Más rud é nach n, ansin cad é an chuid eile? Noah, cad é an chuid eile. 

LUCHT ÉISTEACHTA: Ó, seo chugainn. 

Jason Hirschhorn: Next, go díreach. Go díreach. Tá Next an ceann ceart. Agus céard eile is gá dúinn thabhairt cothrom le dáta, Noah? 

LUCHT ÉISTEACHTA: An leideanna. 

Jason Hirschhorn: Mar sin, suas chun dáta againn faoi láthair. 

LUCHT ÉISTEACHTA: Roimhe-> seo chugainn. 

Jason Hirschhorn: Yeah. OK, beidh orainn sos. Cé is féidir cabhrú linn amach anseo? Manu, cad ba cheart dúinn a dhéanamh? 

LUCHT ÉISTEACHTA: Tá sé agat a shocrú sé cothrom le Curr-> seo chugainn. Ach é sin a dhéanamh os comhair an líne roimhe seo. 

Jason Hirschhorn: OK. Rud ar bith eile? Akshar. 

LUCHT ÉISTEACHTA: Ní dóigh liom go bhfuil tú Chiallaigh Curr-> a athrú amach romhainn. Sílim go bhfuil tú i gceist a dhéanamh ionann Curr Curr-> seo chugainn chun dul go dtí an nód seo chugainn. 

Jason Hirschhorn: Mar sin, tá brón orainn, i gcás ina? Cén líne? An líne seo? 

LUCHT ÉISTEACHTA: Yeah. Déan ionann Curr Curr-> seo chugainn. 

Jason Hirschhorn: Mar sin tá go ceart toisc go bhfuil reatha pointeoir chuig nód. Agus ba mhaith linn é a chur in iúl go dtí an chéad nód ar cad atá ag dul faoi láthair Luaigh. Curr féin Tá chugainn. Ach má bhí muid curr.next thabhairt cothrom le dáta, táimid ag bheadh ​​cothrom le dáta an nóta iarbhír Ní féin, i gcás an Cuireadh pointeoir dírithe. Cad mar gheall ar an líne seo, cé. Avi? 

LUCHT ÉISTEACHTA: Roimhe-> seo chugainn ionann Curr. 

Jason Hirschhorn: Mar sin, arís, má Dé ina pointeoir chuig nód, Dé-> seo chugainn go bhfuil an pointeoir iarbhír sa nód. Mar sin, bheadh ​​sé seo a bheith cothrom le dáta le pointeoir i nód a Curr. Nílimid ag iarraidh a thabhairt cothrom le dáta pointeoir i nód. Is mian linn a thabhairt cothrom le dáta roimhe sin. Mar sin, conas is féidir linn é sin a dhéanamh? 

LUCHT ÉISTEACHTA: Bheadh ​​sé a bheith díreach Roimhe Seo. 

Jason Hirschhorn: Ceart. Is Roimhe pointeoir chuig nód. Anois, tá muid ag athrú go dtí pointeoir nua nód. OK Lig dúinn bogadh síos. Ar deireadh, an coinníoll seo caite. Jeff, cad a dhéanann muid anseo? 

LUCHT ÉISTEACHTA: Má tá luach cothrom le Curr-> n. 

Jason Hirschhorn: Tá brón orm. Oh mo maitheasa. Cad é? Luach == Curr-> n. Cad a dhéanaimid? 

LUCHT ÉISTEACHTA: Gur mhaith leat saor in aisce ar ár new_node, agus ansin gur mhaith leat a thabhairt ar ais bréagach. 

Jason Hirschhorn: Is é seo a ní mór dúinn i scríbhinn go dtí seo. An bhfuil aon duine aon rud a chur roimh a dhéanann muid? OK. A ligean ar iarracht é. Is féidir le Rialú a bheith ag an deireadh le feidhm neamh-neamhní. Avi, cad atá ar siúl? 

LUCHT ÉISTEACHTA: An bhfuil tú ceaptha ar ais a chur fíor lasmuigh den lúb fad? 

Jason Hirschhorn: Níl a fhios agam. Ar mhaith leat mé a? 

LUCHT ÉISTEACHTA: Ná bac leis. Uimh 

Jason Hirschhorn: Akshar? 

LUCHT ÉISTEACHTA: I mo thuairimse, i gceist agat a a chur tuairisceán bréige ag an deireadh an lúb fad. 

Jason Hirschhorn: Mar sin, i gcás ina ar mhaith leat é a dul? 

LUCHT ÉISTEACHTA: Cosúil lasmuigh den lúb fad. Mar sin, má tá tú scoir an lúb fad a modhanna go atá bainte amach agat ar an deireadh agus Tá rud ar bith a tharla. 

Jason Hirschhorn: OK. Mar sin, cad a dhéanann muid i anseo? 

LUCHT ÉISTEACHTA: ar ais ort bréagach ann chomh maith. 

Jason Hirschhorn: Ó, táimid ag dhéanamh sa dá áit? 

LUCHT ÉISTEACHTA: Yeah. 

Jason Hirschhorn: OK. Ar chóir dúinn dul? Oh mo maitheasa. Tá brón orm. I leithscéal as an scáileán. Tá sé de chineál ar freaking amach ar orainn. Mar sin, a roghnú rogha. Zero, in aghaidh an cód Éirigh, an clár. Ionsáigh amháin rud éigin. A ligean ar chur isteach trí. Ní raibh an iatán rathúil. Tá mé ag dul a phriontáil amach. Ní dóigh liom go bhfuil rud ar bith. OK. B'fhéidir go raibh ach phucháin. Ionsáigh amháin. Níl rathúil. OK. A ligean ar reáchtáil trí GDB i ndáiríre go tapa a sheiceáil amach cad atá ar siúl. 

Cuimhnigh gdb. / An t-ainm ar do Faigheann an clár sinn i GDB. An bhfuil go bhfuil a lán a láimhseáil? An flashing? Is dócha. Dún do shúile agus roinnt domhain breaths má fhaigheann tú tuirseach chun breathnú ar sé. Tá mé i GDB. Cad é an chéad rud a dhéanfaidh mé i GDB? Táimid agam chun an figiúr amach cad atá ar siúl anseo. A ligean ar a fheiceáil. Tá sé nóiméad chun an figiúr amach cad atá ar siúl. Briseadh mó. Agus ansin cad a dhéanfaidh mé? Carlos? Rith. OK. A ligean ar a roghnú rogha. Agus cad N dhéanamh? Ar Aghaidh. Yeah. 

LUCHT ÉISTEACHTA: Ní raibh tú a lua - Ní raibh tú ag rá go bhfuil an ceann, bhí sé initialized leis null ag an tús. Ach shíl mé a dúirt tú go raibh ceart go leor. 

Jason Hirschhorn: A ligean ar dul - a ligean ar breathnú i GDB, agus ansin beidh muid ag dul ar ais. Ach fuaimeanna sé cosúil go bhfuil tú cheana féin roinnt smaointe faoi cad atá ar siúl. Mar sin, ba mhaith linn rud éigin a chur isteach. OK. Táimid tar éis a chur isteach. Cuir isteach ina slánuimhir. Beidh muid isteach trí. Agus ansin tá mé ar an líne seo. Conas is féidir liom dul a thosú debugging an chur isteach a dtugtar fheidhm? Oh mo maitheasa. Sin a lán. An bhfuil go freaking amach a lán? 

LUCHT ÉISTEACHTA: Ó, a fuair bás sé. 

Jason Hirschhorn: mé díreach tar éis tharraing sé amach. OK. 

LUCHT ÉISTEACHTA: B'fhéidir go bhfuil sé an taobh eile na sreinge. 

Jason Hirschhorn: Wow. Mar sin, an líne bun - cad a rinne tú a rá? 

LUCHT ÉISTEACHTA: Dúirt mé an íoróin teicniúla deacrachtaí sa rang seo. 

Jason Hirschhorn: Tá a fhios agam. Más rud é ach bhí mé rialú thar an gcuid sin. [Inaudible] Sin fuaimeanna iontach. Cén fáth nach bhfuil tú guys tosú ag smaoineamh faoi cad a d'fhéadfadh muid a bheith déanta go mícheart, agus beidh muid ar ais i 90 soicind. 

Avica, tá mé ag dul a iarraidh ort conas a théann insert_node taobh istigh chun dífhabhtaithe air. Mar sin, is é seo nuair a d'fhág muid go deireanach amach. Conas is féidir liom dul taobh istigh insert_node, Avica, chun scrúdú a dhéanamh cad atá ar siúl? Cad ordú GDB? Ní bheadh ​​Sos thabhairt dom taobh istigh. An bhfuil a fhios Marquise? 

LUCHT ÉISTEACHTA: Cad é? 

Jason Hirschhorn: Cad ordú GDB Úsáid mé chun dul taobh istigh an fheidhm seo? 

LUCHT ÉISTEACHTA: Céim? 

Jason Hirschhorn: Céim trí S. Go ndéanfaidh mé taobh istigh. OK. New_node mallocing roinnt spáis. Go Breathnaíonn go léir mhaith a dul. A ligean ar scrúdú a dhéanamh ar new_node. Fuair ​​sé roinnt seoladh chuimhne. A ligean ar a sheiceáil - is é sin go léir ceart. Mar sin, is cosúil gach rud anseo chun a bheith ag obair i gceart. 

LUCHT ÉISTEACHTA: Cad é an difríocht idir P agus taispeáint? 

Seasann P don chló: JASON Hirschhorn. Agus mar sin go bhfuil tú ag iarraidh ar cad é an difríocht idir sin agus seo? Sa chás seo, rud ar bith. Ach go ginearálta tá roinnt difríochtaí. Agus ba chóir duit breathnú ar an lámhleabhar GDB. Ach sa chás seo, rud ar bith. Claonadh a bhíonn againn a phriontáil a úsáid, áfach, mar gheall ar Ní mór dúinn a dhéanamh i bhfad níos mó ná mar a luach amháin a phriontáil. 

OK. Mar sin, tá muid ar líne 80 ar ár cód, ag leagan nód * Curr cothrom le liosta. Lig dúinn a phriontáil amach Curr. Sé cothrom le liosta. Sweet. Fan. Is ionann sé rud éigin. Nach cosúil ceart. Tá muid ag dul. Tá sé mar gheall i GDB, ceart, má tá sé an líne go bhfuil tú ar sé nach bhfuil a fhorghníomhú fós. Mar sin, is gá duit a chlóscríobh i ndáiríre in aice leis an líne fhorghníomhú sula bhfaca a chuid torthaí. Mar sin anseo tá muid. Chun báis muid ach an líne seo, is ionann roimhe null. Mar sin, arís, má phriontáil againn roimhe seo Ní bheidh muid aon rud a fheiceáil aisteach. Ach má fhorghníomhú againn i ndáiríre go líne, ansin beidh muid a fheiceáil gur oibrigh an líne sin. 

Mar sin, ní mór dúinn Curr. Glacfar iad araon go maith. Ceart? Anois, tá muid ar an líne seo ar dheis anseo. Cé nach bhfuil Curr null comhionann. Bhuel, cad a dhéanann Curr comhionann? Chonaic muid ach cothrom sé Eolas faoin margadh saothair. Clóite againn sé amach. Feicfidh mé a phriontáil amach arís. Mar sin, is é sin cé lúb ag dul a fhorghníomhú? 

LUCHT ÉISTEACHTA: Uimh 

Jason Hirschhorn: Mar sin, nuair a chlóscríobh mé go líne, a fheiceann tú léim muid go léir ar an mbealach síos go dtí an bun, ar ais bréagach. Agus ansin tá muid ag dul a thabhairt ar ais bréagach agus dul ar ais go dtí ár gclár agus sa deireadh a phriontáil amach, cosúil le chonaic muid, Ní raibh an chur isteach rathúil. Mar sin, tá aon duine aon smaointe ar an méid ní mór dúinn a dhéanamh a shocrú seo? Tá mé ag dul chun fanacht go dtí a fheiceáil mé cúpla lámha dul suas. Ní raibh muid a fhorghníomhú seo. Coinnigh i gcuimhne, ba é seo an chéad Rud bhí á dhéanamh againn. Níl mé ag dul a dhéanamh cúpla. Tá mé ag dul a dhéanamh le cúpla. Toisc ciallaíonn cúpla dhá. Beidh mé ag fanacht ar feadh níos mó ná dhá. 

An chéad a chur isteach, Curr, ag cothrom réamhshocraithe null. Agus fhorghníomhú an lúb amháin más rud é nach bhfuil Curr null. Mar sin, conas is féidir liom a fháil ar fud é seo? Feicim trí lámha. Beidh mé ag fanacht ar feadh níos mó ná trí. Marcus, cad a cheapann tú? 

LUCHT ÉISTEACHTA: Bhuel, más gá duit é a fhorghníomhú níos mó ná uair amháin, tá tú díreach é a athrú go lúb dhéanamh-fad. 

Jason Hirschhorn: OK. An mbeidh a réiteach ar ár fhadhb, cé? 

LUCHT ÉISTEACHTA: Sa chás seo ní mar gheall ar ar an bhfíric go bhfuil an liosta folamh. Mar sin, ansin is dócha gá duit ach a chur leis ráiteas go má na bealaí amach lúb ansin caithfidh tú a bheith ag deireadh na an liosta, ag a pointe tú Is féidir a chur isteach ach é. 

Jason Hirschhorn: Is maith liom go bhfuil. Sin a dhéanann ciall. Má exits an lúb - toisc go mbainfidh sé ar ais bréagach anseo. Mar sin, má tá na bealaí amach lúb, ansin tá muid ag an deireadh an liosta, nó b'fhéidir an tús a chur ar liosta má tá aon rud i sé, a bhfuil mar an deireadh an gcéanna. Mar sin, anois, ba mhaith linn a chur isteach rud éigin anseo. Mar sin, ní conas an cód cuma, Marcus? 

LUCHT ÉISTEACHTA: Má fuair tú cheana féin ar an nód malloced, d'fhéadfá a rá go díreach new_node-> ionann chugainn null toisc tá sé le bheith ag an deireadh. Nó eile is ionann new_node-> Eolas faoin margadh saothair. 

Jason Hirschhorn: OK. Tá brón orm. New_node-> seo chugainn ionann null mar táimid ag an deireadh. Nach gcuireann sé isteach Conas is féidir linn é a chur ar an liosta? Ceart. Sin díreach a leagan sé cothrom le. Níl an chaoi a dhéanaimid i ndáiríre é a chur ar an liosta? Cad atá dírithe ar an deireadh an liosta? 

LUCHT ÉISTEACHTA: Ceann. 

Jason Hirschhorn: Tá brón orm? 

LUCHT ÉISTEACHTA: Ceann é dírithe go dtí deireadh an liosta. 

Jason Hirschhorn: Má níl rud ar bith i an liosta, tá ceann dírithe ar an deireadh an liosta. Mar sin, beidh go n-oibríonn an an chéad a chur isteach. Cad faoi má tá cúpla rudaí ar an liosta? Ná nach bhfuil muid ag iarraidh a shocrú ceann cothrom le new_node. Cad é ba mhaith linn a dhéanamh ann? Yeah? Is dócha roimhe sin. An mbeidh an obair sin? Thabhairt chun cuimhne go bhfuil roimhe seo ach pointeoir chuig nód. Agus is é roimhe athróg áitiúil. Mar sin, beidh an líne seo a leagtar athróg áitiúil, roimhe seo, atá cothrom le nó atá dírithe ar an nód nua seo. Ní bheidh an chur iarbhír sé i ár liosta, cé. Conas is féidir linn é a chur i ár liosta? Akchar? 

LUCHT ÉISTEACHTA: I mo thuairimse, tú dhéanamh faoi láthair-> seo chugainn. 

Jason Hirschhorn: OK. Curr-> seo chugainn. Mar sin, arís, ar an gcúis amháin go bhfuil muid síos anseo is é sin, cad a dhéanann acu arb ionann é? 

LUCHT ÉISTEACHTA: Chomhionannais null. 

Jason Hirschhorn: Agus mar sin cad a tharlaíonn má dhéanann muid null-> seo chugainn? Cad a dhéanann muid ag dul a fháil? Beidh muid a fháil ar locht deighilt. 

LUCHT ÉISTEACHTA: is ionann Ná Curr null. 

Jason Hirschhorn: Sin an rud céanna mar Dé, áfach, mar níl athróg áitiúil táimid ag leagan síos comhionann leis an nód nua seo. A ligean ar dul ar ais go dtí ár pictiúr de chur isteach rud éigin. Abair táimid a chur isteach ag an deireadh ar an liosta, mar sin ceart anseo. Tá pointeoir reatha go dírithe ar margadh saothair agus pointe roimhe seo go bhfuil dírithe ar 8. Mar sin, cad is gá dúinn a thabhairt cothrom le dáta, Avi? 

LUCHT ÉISTEACHTA: Roimhe-> seo chugainn? 

Jason Hirschhorn: Roimhe-> seo chugainn cad ba mhaith linn a thabhairt cothrom le dáta mar sin Beidh isteach i ndáiríre é ag an deireadh an liosta. Tá muid go fóill fabht amháin, áfach, go bhfuil muid ag dul a reáchtáil i. Cad é an bug? Yeah? 

LUCHT ÉISTEACHTA: Tá sé ag dul a thabhairt ar ais bréagach sa chás seo? 

Jason Hirschhorn: Oh, tá ag dul a thabhairt ar ais bréagach. Ach níl bug eile. Mar sin, beidh orainn gá a chur sa tuairisceán fíor. 

LUCHT ÉISTEACHTA: An roimhe comhionann fós Eolas faoin margadh saothair ag barr an liosta? 

Jason Hirschhorn: Mar sin, go fóill roimhe ionann null ag an tús an-. Mar sin, conas is féidir linn a fháil níos mó ná sin? Yeah? 

LUCHT ÉISTEACHTA: I mo thuairimse, is féidir leat a dhéanamh le seiceáil roimh an lúb fad a fheiceáil má tá sé liosta folamh. 

Jason Hirschhorn: OK. Mar sin, a ligean ar dul anseo. Déan seiceáil. Má - 

LUCHT ÉISTEACHTA: Mar sin, má tá ceann ionann is ionann null. 

Jason Hirschhorn: Má ceann ionann ionann null - beidh go insint dúinn má tá sé ar an liosta folamh. 

LUCHT ÉISTEACHTA: Agus ansin tú ionann dhéanamh ceann nua. 

Jason Hirschhorn: Ceann Is ionann new_node? Agus céard eile is gá dúinn a dhéanamh? 

LUCHT ÉISTEACHTA: Agus ansin tú ar ais fíor. 

Jason Hirschhorn: Ní leor. Táimid ag iarraidh ar céim amháin. 

LUCHT ÉISTEACHTA: New_node chugainn Tá go pointe a margadh saothair. 

Jason Hirschhorn: Go díreach, Alden. Agus ansin is féidir linn a thabhairt ar ais fíor. OK. Ach tá sé fós ag smaoineamh maith chun rudaí a dhéanamh ag deireadh an liosta, ceart? Gach ceart. D'fhéadfadh muid a fháil i ndáiríre fós go dtí deireadh an liosta. Mar sin, is é an cód fíneáil má tá muid ag an deireadh an liosta agus tá roinnt rudaí ar an liosta? Ceart? Toisc go bhfuil muid fós ag smaoineamh Marcus ar. D'fhéadfadh muid a scoir an lúb mar gheall ar táimid ag deireadh an liosta. Mar sin bhfuil muid ag iarraidh fós ar an cód an síos anseo? 

LUCHT ÉISTEACHTA: Is ea. 

Jason Hirschhorn: Yeah. Agus cad is gá dúinn a athrú seo a? Fíor. An bhfuil go maith fuaime do gach duine go dtí seo? Aon duine ar bith - Avi, an bhfuil tú rud éigin a chur leis? 

LUCHT ÉISTEACHTA: Uimh 

Jason Hirschhorn: OK. Mar sin, atá déanta againn le cúpla athruithe. Atá déanta againn seo seic roimh againn chuaigh i do liosta folamh. Mar sin, tá muid glacadh de chúram liosta folamh. Agus anseo thóg muid aire a chur isteach rud éigin ag deireadh an liosta. Mar sin, is cosúil sé cosúil le seo cur lúb fad aire a thabhairt rudaí i idir, áit éigin ar an liosta má tá Tá rudaí sa liosta. 

OK. Lig dúinn a reáchtáil an clár seo arís. Níl rathúil. 

LUCHT ÉISTEACHTA: Ní raibh tú é a dhéanamh. 

Jason Hirschhorn: Ó, Ní raibh mé é a dhéanamh. Pointe Dea, Micheál. A ligean ar add a dhéanamh nasctha. Líne 87 níl earráid. Líne 87. Alden, ba é seo an líne thug tú dom. Cad atá cearr? 

LUCHT ÉISTEACHTA: Tá sé a bheith a margadh saothair. 

Jason Hirschhorn: Den scoth. Go díreach ceart. Ba chóir go mbeadh null. A ligean ar a dhéanamh arís. A thiomsú. OK. A ligean ar chur isteach trí. Bhí an iatán rathúil. A ligean ar a phriontáil amach. Ó, más rud é amháin a d'fhéadfadh muid a sheiceáil. Ach nach bhfuil déanta againn ar an phriontáil feidhm go fóill. A ligean ar dul isteach rud éigin eile. Cad ba cheart dúinn dul isteach? 

LUCHT ÉISTEACHTA: Seacht. 

Jason Hirschhorn: Seacht? 

LUCHT ÉISTEACHTA: Is ea. 

Jason Hirschhorn: Tá locht seg. Mar sin, fuair muid ar cheann, ach ní mór dúinn go soiléir Ní féidir a fháil dó. Tá sé 05:07. Mar sin, d'fhéadfadh muid a debug seo ar feadh trí nóiméad. Ach tá mé ag dul a fhágáil linn anseo agus bogadh ar aghaidh go dtí táblaí hash. Ach arís, na freagraí do gcód seo Beidh mé é a ríomhphost a thabhairt duit i beagán. Táimid an-ghar dó. Spreagfainn mór leat chun an figiúr amach cad atá ar siúl anseo agus é a shocrú. Mar sin, beidh mé ríomhphost tú gcód seo maith móide an réiteach - dócha go bhfuil an réiteach níos déanaí. An Chéad cód seo. 

An rud eile ba mhaith liom a dhéanamh sula ndéanaimid Tá bailchríoch ní mór dúinn aon rud saor. Mar sin, ba mhaith liom a thaispeáint duit cad valgrind Breathnaíonn an nós. Má reáchtáil againn teorainneacha valgrind ar ár gclár,. / nasctha. Arís, de réir an sleamhnán, táimid ag ba chóir a reáchtáil valgrind le roinnt de chineál rogha, sa chás seo - Sceitheadh-seiceáil = iomlán. Mar sin, a ligean ar scríobh valgrind - Sceitheadh-seiceáil = iomlán. Mar sin, beidh sé seo ar siúl valgrind ar ár gclár. Agus anois ritheann an clár i ndáiríre. Mar sin, táimid ag dul a rith sé díreach cosúil roimh, rud éigin a chur isteach Tá mé ag dul a chur i dtrí. Go n-oibríonn. Níl mé ag dul chun iarracht a dhéanamh a chur i rud éigin eile toisc go bhfuil muid ag dul go dtí a fháil bhréagach seg sa chás sin. Mar sin, tá mé ag dul díreach tar éis a scor. 

Agus anois a fheiceann tú síos anseo sceite agus achoimre gcarn. Seo iad na rudaí maithe a ba mhaith leat a sheiceáil amach. Mar sin, an achoimre gcarn - a deir sé, in úsáid ag bealach amach - ocht beart san bhloc amháin. Is é sin ar cheann bloc an nód malloced againn. Michael, a dúirt tú roimh é nód ocht greamanna toisc go bhfuil sé an tslánuimhir agus an pointeoir. Mar sin, go bhfuil ár nód. Agus ansin deir sé a úsáid le linn malloc seacht n-uaire, agus freed muid rud éigin sé huaire. Ach ní ar a dtugtar againn saor in aisce, ionas go mbeidh mé aon smaoineamh a bhfuil sé seo ag caint faoi. 

Ach is leor a rá go bhfuil nuair a d' Ritheann an clár, tá malloc bheith ar a dtugtar i roinnt áiteanna eile againn ní gá a bheith buartha faoi. Mar sin, bhí ar a dtugtar is dócha malloc i roinnt áiteanna. Ní gá a bheith buartha nuair a. Ach tá sé seo i ndáiríre dúinn. Is é seo an chéad líne dúinn. D'fhág muid go bloc. Agus is féidir leat a fheiceáil go bhfuil anseo san achoimre sceitheadh. Fós reachable - ocht beart san bhloc amháin. Ciallaíonn sin go bhfuil cuimhne - ní mór dúinn a leaked go bhfuil cuimhne. Cinnte caillte - Tá rud éigin a chaill le haghaidh maith. Go ginearálta, ní bheidh tú aon rud a fheiceáil ann. Fós reachable go ginearálta sa chás Feicfidh tú rudaí a fheiceáil, i gcás ina mbainfidh tú ag iarraidh chun breathnú ar a fheiceáil cad cód cheart duit tá freed ach tú dearmad saor in aisce. 

Agus ansin más rud é nach raibh sé seo an cás, má rinne muid gach rud saor in aisce, is féidir linn a sheiceáil go. A ligean ar siúl ach an clár ní a chur i rud ar bith. Feicfidh tú a fheiceáil síos anseo in úsáid ag bealach amach - nialasach sa nialas bloic. Ciallaíonn bhí muid aon rud fágtha nuair sendmail an gclár seo. Mar sin, roimh casadh i pset6, valgrind reáchtáil agus a dhéanamh cinnte nach bhfuil tú leaks cuimhne ar bith i do chlár. Má tá aon cheist agat le valgrind agat, bhraitheann saor chun teagmháil a dhéanamh. Ach tá sé seo conas a úsáideann tú é. An-simplí - a fheiceáil má tú Tá sé in úsáid ag scoir - aon beart san aon bloic. 

Mar sin, bhí muid ag obair ar chur isteach nód. Bhí mé dhá feidhmeanna eile anseo - nóid nóid agus saor in aisce a phriontáil. Arís, tá na feidhmeanna atá ag dul a bheith go maith chun tú a chleachtadh mar go mbeidh siad cabhrú leat ní hamháin le na cleachtaí sampla ach freisin ar an bhfadhb a leagan síos. Léarscáil siad ar go leor go dlúth le rudaí tú ag dul a bheith le déanamh sa fhadhb a leagan síos. Ach mé ag iarraidh a dhéanamh cinnte go muid teagmháil ar gach rud. Agus tá táblaí hash ríthábhachtach freisin cad tá ag éirí linn san alt seo seachtain - nó i tacar bhfadhb. 

Mar sin, táimid ag dul a chríochnú an t-alt ag caint faoi táblaí hash. Má thugann tú rinne mé tábla hash beag. Ní hé sin cad tá muid ag caint faoi, áfach. Táimid ag caint faoi eile cineál táblaí hash. Agus ar a chroí, tábla hash aon rud níos mó ná sraith chomh maith le feidhm hash. Táimid ag dul a labhairt ar feadh beagán ach a a dhéanamh cinnte go dtuigeann gach duine cad a Is é feidhm hash. Agus mé ag rá leat anois go bhfuil sé rud ar bith níos mó ná dhá rud - eagar agus feidhm hash. Agus tá anseo na céimeanna trí ina n-oibríonn sé seo. 

Níl ár eagar. Níl ár bhfeidhm. Go háirithe, ní mór feidhmeanna hash a dhéanamh cúpla rudaí seo. Tá mé ag dul chun labhairt go sonrach faoin bhfadhb seo a leagan síos. Tá sé seo ag dul dócha a a ghlacadh i teaghrán. Agus cad atá sé ag dul a thabhairt ar ais? Cén cineál sonraí? Alden? Do fheidhm hash ar ais? Slánuimhir. Mar sin, is é seo cad é an hash Is éard atá tábla - tábla i bhfoirm eagar agus feidhm hash. Conas a oibríonn sé? Oibríonn sé i dtrí chéim. Tugaimid dó eochair. Sa chás seo, beidh orainn a thabhairt dó teaghrán. Glaoch orainn an fheidhm hash in aghaidh céim amháin ar an eochair agus a fháil againn luach. 

Go sonrach, beidh orainn a rá a fháil againn slánuimhir. Go slánuimhir, tá an-sonrach teorainneacha le cad is féidir a bheith slánuimhir. Sa sampla seo, ár eagar Tá an méid a trí. Mar sin, céard iad na huimhreacha gur féidir slánuimhir a bheith. Cad é an raon luachanna bailí ar feadh go slánuimhir, an cineál ais seo hash fheidhm? Nialais, ceann amháin agus dhá. Is é an pointe ar an fheidhm hash a figiúr amach an áit sa sraith áit a bhfuil ár n-eochair ag dul. Níl ach trí cinn is féidir áiteanna anseo - náid, ceann amháin, nó dhó. Mar sin, an fheidhm seo níos fearr ar ais náid, ceann amháin, nó dhó. Roinnt indice bailí sa eagar. 

Agus ansin ag brath ar an áit tuairisceáin sé, is féidir leat a fheiceáil go bhfuil eagar oscailte lúibín luach. Sin nuair a chuir muid an eochair. Mar sin, caith againn sa pumpkin, a fháil againn amach náid. Ag lúibín eagar 0, chuir muid Pumpkin. Caith againn i cait, a fháil againn amach ceann. Chuir muid cat ag amháin. Chuireamar i Spider. Againn a fháil amach dhá. Chuireamar Spider ag scriosaidh eagar dhá. Bheadh ​​sé a bheith chomh deas dá D'oibrigh sé mar sin. Ach ar an drochuair, mar beidh orainn a fheiceáil, tá sé beagán níos casta. 

Roimh a fháil againn ann, aon cheisteanna faoi ​​seo bhunúsach leagtha-suas de tábla hash? Is é seo an íomhá de díreach cad a tharraing muid ar an mbord. Ach ós rud é tharraing muid é ar an mbord, mé Nílim ag dul chun dul isteach ann a thuilleadh. Go bunúsach eochracha, an bosca dubh draíochta - nó sa chás seo, bosca teal - de cuireann feidhm hash iad i buicéid. Agus sa sampla seo táimid ní a chur an t-ainm. Táimid ag cur an teileafón a bhaineann líon an t-ainm ar an buicéad. Ach d'fhéadfaí tú go han-mhaith ach a chur ar an t-ainm sa buicéad. 

Is é seo ach pictiúr de cad Tharraing muid ar an mbord. Tá pitfalls féideartha, cé. Agus tá dhá go háirithe sleamhnáin gur mhaith liom dul os a chionn. Is é an chéad cheann faoi feidhm hash. Mar sin, d'iarr mé ar an cheist, cad Déanann feidhm hash maith? Tugaim dhá freagraí. Is é an chéad go bhfuil sé cinntitheach. I gcomhthéacs na feidhmeanna hash, cad a chiallaíonn sé? Is ea? 

LUCHT ÉISTEACHTA: Is féidir é a teacht ar an innéacs in am tairiseach? 

Jason Hirschhorn: Go nach bhfuil cad a chiallaíonn sé. Ach tá go buille faoi thuairim maith. Aon duine eile a bhfuil buille faoi thuairim cad a chiallaíonn sé seo? Go fheidhm hash maith Is deterministic? Annie? 

LUCHT ÉISTEACHTA: Gur féidir eochair a mhapáil amháin go dtí ionad amháin sa tábla hash. 

Jason Hirschhorn: Sin go díreach ceart. Gach uair a chuir tú i pumpkin, tuairisceáin sé i gcónaí nialas. Má chuir tú i Pumpkin agus do hash tuairisceáin feidhm náid ach tá dóchúlacht filleadh ar rud éigin eile níos mó ná náid - mar sin b'fhéidir gur féidir é a thabhairt ar ais ar cheann uaireanta nó dhá uair eile - nach bhfuil feidhm hash maith. Tá díreach ceart agat. Ba chóir do fheidhm hash ar ais ar an slánuimhir ceannann céanna, sa chás seo, d' an teaghrán céanna cruinn. 

B'fhéidir tuairisceáin sé an tslánuimhir ceannann céanna an teaghrán ceannann céanna beag beann ar caipitlithe. Ach sa chás sin tá sé fós deterministic mar gheall ar rudaí il mapáilte ar an luach céanna. Sin breá. Chomh fada is go bhfuil ceann ann ach aschur le haghaidh ionchur ar leith. 

OK. Is é an dara rud go bhfuil sé tuairisceáin innéacsanna bailí. Thug muid suas níos luaithe. An fheidhm hash - OH buachaill - Ba chóir feidhm hash ar ais innéacsanna bailí. Mar sin, a rá - a ligean ar dul ar ais go dtí an sampla seo. Comhaireamh Mo fheidhm hash suas na litreacha sa bhfocal. Sin an fheidhm hash. Agus tuairisceáin sin slánuimhir. Mar sin, má tá mé an focal A, tá sé ag dul ar ais amháin. Agus tá sé ag dul a chur ar dheis anseo. Cad a tharlaíonn má chuir mé i an focal bat? Tá sé ag dul a thabhairt ar ais trí. I gcás nach ialtóg dul? 

Ní chuireann sé oiriúnach. Ach ní mór é a dul áit éigin. Is é seo mo tábla hash tar éis an tsaoil, agus riachtanais gach rud a dul áit éigin. Mar sin, áit ar cheart ialtóg dul? Aon smaointe? Guesses? Guesses Dea? 

LUCHT ÉISTEACHTA: nialais. 

Jason Hirschhorn: Cén fáth náid? 

LUCHT ÉISTEACHTA: Mar gheall ar thrí Is modulo trí náid? 

Jason Hirschhorn: Trí Is modulo trí nialas. Is é sin buille faoi thuairim go hiontach, agus tá sin ceart. Mar sin, sa chás seo ba chóir dó dul dócha ag náid. Mar sin, ar bhealach maith chun a chinntiú go bhfuil an hash tuairisceáin fheidhm amháin innéacsanna bailí a modulo dó ag an méid de na tábla. Má modulo tú is cuma cad seo tuairisceáin trí, tá tú ag dul i gcónaí a fháil rud éigin idir nialas, ceann amháin, agus dhá. Agus má fhilleann sé seo i gcónaí ar seacht, agus tú modulo i gcónaí ag triúr, tá tú i gcónaí ag dul a fháil ar an rud céanna. 

Mar sin, tá sé fós deterministic má modulo tú. Ach a chinntiú go bhfuil tú riamh a fháil ar rud éigin - tionscal neamhbhailí. Go ginearálta, ba chóir go dtarlódh modulo taobh istigh do fheidhm hash. Mar sin, ní gá duit a bheith buartha faoi seo. Is féidir leat a chinntiú go díreach tá sé seo le indice bailí. Ceisteanna ar bith ar an pitfall féideartha? 

OK. Agus ansin a théann muid. Pitfall féideartha Aghaidh, agus is é seo an ceann mór. Cad a tharlaíonn má léarscáil dhá eochracha leis an luach céanna? Mar sin, tá dhá bhealach chun déileáil leis seo. Is é an chéad cheann ar a dtugtar líneach deacra, a bhfuil mé nach bhfuil ag dul chun dul os a chionn. Ach ba chóir duit a bheith eolach ar an gcaoi go n-oibríonn agus cad é sin. 

An dara ceann mé ag dul chun dul thar toisc go bhfuil an ceann a lán Beidh daoine a deireadh dócha suas cinneadh a úsáid ina leagtar bhfadhb. Ar ndóigh, ní gá duit a. Ach do na socraithe fhadhb, go leor daoine claonadh a roghnú chun a chruthú tábla hash le shlabhrú ar leith a chur i bhfeidhm n foclóir. Mar sin, táimid ag dul chun dul thar cad a chiallaíonn sé a chruthú tábla hash le shlabhrú ar leith. 

Mar sin, chuir mé i Pumpkin. Tuairisceáin sé nialas. Agus chuir mé Pumpkin anseo. Ansin, chuir mé i - cad rud eile Oíche Shamhna-téamaí? 

LUCHT ÉISTEACHTA: Candy. 

Jason Hirschhorn: Candy! Sin ceann iontach. Chuir mé i candy, agus candy chomh maith a thugann dom nialas. Cad a dhéanfaidh mé? Aon smaointe? Mar gheall ar gach saghas a fhios agat cad shlabhrú ar leith atá. Mar sin, aon smaointe cad atá le déanamh? Yeah. 

LUCHT ÉISTEACHTA: A chur ar an teaghrán iarbhír sa tábla hash. 

Jason Hirschhorn: Mar sin, táimid ag dul go dtí tharraingt ar an smaoineamh maith thar anseo. OK. 

LUCHT ÉISTEACHTA: An bhfuil an hashtable [Inaudible] an pointeoir a pointí a tús an liosta. Agus ansin tá pumpkin a bheith ar an gcéad luach sa liosta sin nasctha agus candy a bheith an dara luach sa liosta nasctha. 

Jason Hirschhorn: OK. Marcus, a bhí go gan íoc. Tá mé ag dul a bhriseadh síos go. Marcus é ag rá nach forscríobh Pumpkin. Bheadh ​​sé sin dona. Ná cuir candy áit éigin eile. Táimid ag dul chun iad a chur ar an dá ag náid. Ach táimid ag dul chun déileáil le iad a chur ag náid ag a chruthú liosta ag náid. Agus táimid ag dul a chruthú liosta de gach rud a mapáilte go nialas. Agus an bealach is fearr a d'fhoghlaim muid a chruthú liosta gur féidir fás agus Laghdaigh dinimiciúil nach bhfuil faoi eagar eile. Mar sin, ní sraith il-tríthoiseach. Ach a chruthú ach liosta nasctha. 

Mar sin, cad a mhol sé - Tá mé ag dul a fháil nua - Is chruthú sraith le leideanna, le sraith de leideanna. OK. Aon smaoineamh nó leid cad é an cineál Ba chóir an leideanna a bheith? Marcus? 

LUCHT ÉISTEACHTA: Leideanna do - 

Jason Hirschhorn: Mar gheall ar tú Dúirt liosta nasctha, mar sin - 

LUCHT ÉISTEACHTA: leideanna Nód? 

Jason Hirschhorn: leideanna Nód. Má tá an rudaí inár nasctha Tá liosta nóid ansin siad Ba chóir go mbeadh leideanna nód. Agus cad a dhéanann siad cothrom dtús? 

LUCHT ÉISTEACHTA: Null. 

Jason Hirschhorn: nialasacha. Mar sin, níl ár rud folamh. Tuairisceáin Pumpkin náid. Cad a dhéanaimid? Siúl liom trí é? I ndáiríre, thug Marcus dom cheana féin. Duine éigin eile ag siúl liom trí é. Cad a dhéanaimid nuair a muid - Breathnaíonn sé seo an-chosúil leis cad a bhí á dhéanamh againn ach. Avi. 

LUCHT ÉISTEACHTA: Tá mé ag dul a ghlacadh buille faoi thuairim. Mar sin, nuair a gheobhaidh tú candy. 

Jason Hirschhorn: Yeah. Bhuel, fuair muid Pumpkin. A ligean ar a fháil ar ár gcéad cheann. Fuair ​​muid Pumpkin. 

LUCHT ÉISTEACHTA: OK. Tuairisceáin Pumpkin náid. Mar sin, chuir tú é i sin. Nó i ndáiríre, chuir tú é ar an liosta nasctha. 

Jason Hirschhorn: Cén chaoi a dhéanaimid é a chur ar an liosta nasctha? 

LUCHT ÉISTEACHTA: Ó, an error iarbhír? 

Jason Hirschhorn: Just a siúl - a rá níos mó. Cad a dhéanaimid? 

LUCHT ÉISTEACHTA: cuir isteach tú díreach é mar an chéad nód. 

Jason Hirschhorn: OK. Mar sin, ní mór dúinn ár n-nód, Pumpkin. Agus anois conas is féidir liom a chur isteach air? 

LUCHT ÉISTEACHTA: shannadh tú sé leis an pointeoir. 

Jason Hirschhorn: Cén pointeoir? 

LUCHT ÉISTEACHTA: An pointeoir ag náid. 

Jason Hirschhorn: Mar sin, i gcás ina a dhéanann an bpointe seo? 

LUCHT ÉISTEACHTA: A margadh saothair ceart anois. 

Jason Hirschhorn: Bhuel, tá sé dírithe ar margadh saothair. Ach tá mé ag cur i Pumpkin. Mar sin, nuair ba chóir é a chur in iúl? 

LUCHT ÉISTEACHTA: A pumpkin. 

Jason Hirschhorn: Chuig Pumpkin. Go díreach. Mar sin, pointí sé seo go Pumpkin. Agus nuair a dhéanann an pointeoir i bpointe pumpkin? Chun 

LUCHT ÉISTEACHTA: Null. 

Jason Hirschhorn: A margadh saothair. Go díreach. Mar sin, cuireadh isteach againn ach rud éigin isteach ar an liosta nasctha. Scríobh muid ach an gcód seo a dhéanamh. Beagnach fuair muid beagnach sé go hiomlán scáinte. Anois táimid isteach candy. Téann ár candy freisin go nialas. Mar sin, cad a dhéanaimid le candy? 

LUCHT ÉISTEACHTA: Braitheann sé ar cibé acu atá nó nach bhfuil muid ag iarraidh a shórtáil sé. 

Jason Hirschhorn: Sin go díreach ceart. Braitheann sé ar cibé acu atá nó nach bhfuil táimid ag iarraidh a shórtáil sé. A ligean ar glacadh leis nach bhfuil muid dul a shórtáil sé. 

LUCHT ÉISTEACHTA: Bhuel ansin, mar a pléadh againn roimh, tá sé is simplí ach a chur air ar dheis ag an tús mar sin an pointeoir ó náid pointí a candy. 

Jason Hirschhorn: OK. Coinnigh ar. Lig dom a chruthú candy dheis anseo. Mar sin, seo pointeoir - 

LUCHT ÉISTEACHTA: Yeah chóir, anois a bheith dírithe ar candy. Ansin tá an pointeoir ó pointe candy Pumpkin. 

Jason Hirschhorn: Cosúil le sin? Agus a rá fuair muid eile rud a mhapáil go nialas? 

LUCHT ÉISTEACHTA: Bhuel, tá tú díreach dhéanamh ar an rud céanna? 

Jason Hirschhorn: Déan an rud céanna. Mar sin, sa chás seo, más rud é nach bhfuil muid ag iarraidh a choinneáil ar sorted sé é fuaimeanna sách simplí. Glacann muid an pointeoir sa indice tugtha ag ár fheidhm hash. Tá an bpointe sin go dtí ár nód nua. Agus ansin is cuma cad a bhí sé ag cur in iúl orthu roimhe seo - sa chás seo faoin margadh saothair, sa dara cás pumpkin - sin, is cuma cad tá sé dírithe ar roimhe sin, cuir isteach againn ar an chéad cheann eile de ár n-nód nua. Táimid ag a chur isteach i rud éigin ar dtús. Go deimhin, tá sé seo ar a lán níos simplí ná mar a ag iarraidh a choinneáil ar an liosta in eagar. Ach arís, beidh cuardach a níos casta ar anseo. Beidh muid i gcónaí chun dul go dtí an deireadh. 

OK. Ceisteanna ar bith faoi shlabhrú ar leith? Conas go n-oibríonn? Cuir ceist orthu anois. Ba mhaith liom i ndáiríre a dhéanamh cinnte go bhfuil tú go léir tuiscint a fháil ar seo roimh ceann againn amach. 

LUCHT ÉISTEACHTA: Cén fáth a bhfuil tú a chur Pumpkin agus candy isteach mar an gcéanna chuid den tábla hash? 

Jason Hirschhorn: Good question. Cén fáth go bhfuil muid iad a chur sa chéanna chuid den tábla hash? Bhuel, sa chás seo ar ár fheidhm hash tuairisceáin náid haghaidh an mbeirt acu. Mar sin, is gá iad chun dul ag náid indice toisc go bhfuil nuair a bhíonn muid ag dul go dtí lorg dóibh má táimid riamh ag iarraidh chun breathnú suas iad. Arís, le cur chuige líneach probing Ní bheadh ​​muid iad a chur sa nialas. Ach sa chur chuige slabhra ar leithligh, táimid ag dul chun iad a chur sa náid agus ansin a chruthú liosta de thalamh nialas. 

Agus nach bhfuil muid ag iarraidh pumpkin a fhorscríobh ach sin mar gheall ar ansin beidh muid glacadh leis go raibh Pumpkin riamh isteach. Má táimid a choinneáil ach rud amháin i suíomh bheadh ​​dona. Ansin ní bheadh ​​aon seans againn riamh - má bhí againn riamh dúblach, ansin dúinn Bheadh ​​scriosadh ach ár luach tosaigh. Mar sin tá sin an fáth a dhéanann muid an cur chuige seo. Nó sin an fáth a roghnaigh muid - ach arís, ní mór dúinn roghnaigh an cur chuige ar leith shlabhrú, a bhfuil cur chuige go leor eile D'fhéadfadh ceann amháin a roghnú. An bhfuil do cheist a fhreagairt? 

OK. Carlos. A bheadh ​​i gceist Líneach deacra - má fuair muid imbhualadh ag náid, ní mór dúinn Bheadh ​​breathnú ar an láthair seo chugainn a fheiceáil má bhí sé ar oscailt agus chuir sé ann. Agus ansin táimid sa spórt eile agus a fheiceáil más rud é go oscailte agus é a chur ann. Mar sin, teacht againn ar an chéad cheann eile ar fáil láthair oscailte agus é a chur ann. Ceisteanna ar bith eile? Yeah, Avi. 

LUCHT ÉISTEACHTA: Mar a leanúint suas go dtí sin, cad a dhéanann tú i gceist ag an láthair seo chugainn? Sa tábla hash no i liost nasctha. 

Jason Hirschhorn: Do líneach cláir, aon liostaí nasctha. An láthair eile ar an tábla hash. 

LUCHT ÉISTEACHTA: OK. Mar sin, bheadh ​​an tábla hash a bheith initialized leis an méid - cosúil leis an líon teaghráin go raibh tú a chur isteach? 

Jason Hirschhorn: Ba mhaith leat iarraidh é a bheith i ndáiríre mór. Tá. Seo pictiúr de cad tá muid Tharraing díreach ar an mbord. Arís, ní mór dúinn imbhualadh ceart anseo. ag 152. Agus beidh tú a fheiceáil cruthaithe againn liosta nasctha thalamh de. Arís, an shlabhrú tábla hash ar leith ní hé cur chuige an ceann agat a ghlacadh le haghaidh fadhbanna a leagtar sé ach ar cheann go bhfuil a lán de na claonadh mic léinn a ghlacadh. Mar sin, ar an nóta, in iúl dúinn labhairt go hachomair os comhair ceann muid amach faoi fhadhb sé, agus ansin beidh mé scéal a roinnt le leat. Tá trí nóiméad. 

Fadhb atá leagtha sé. Tá tú ceithre feidhmeanna - ualach, a sheiceáil, méid, agus Díluchtaigh. Luchtaigh - go maith, tá muid ag dul níos mó ná ualach díreach anois. Tharraing muid ualach ar an mbord. Agus thosaigh muid fiú códú a lán de na a chur isteach i liosta nasctha. Mar sin, nach bhfuil ualach i bhfad níos mó ná mar a cad tá muid díreach ag déanamh. 

Tá Seiceáil nuair a bhíonn tú rud éigin luchtaithe. Tá sé an próiseas céanna leis seo. An rud céanna chéad dá chuid ina chaitheann tú rud éigin ar an fheidhm hash agus a fháil ar a luach. Ach anois nach bhfuil muid ag chur isteach air. Anois, tá muid ag lorg chun é. Tá mé scríofa cód samplacha a aimsiú le haghaidh rud éigin i liosta nasctha. A spreagadh mé tú a chleachtadh go. Ach intuitively a aimsiú rud éigin a bhfuil leor den chineál céanna a chur isteach rud éigin. Go deimhin, tharraing muid pictiúr a aimsiú rud éigin i liosta nasctha, ag bogadh trí go dtí go bhfuair tú go dtí an deireadh. Agus má fuair tú go dtí an deireadh agus nach bhféadfadh é a fháil, ansin nach bhfuil sé ann. Mar sin, go bhfuil seic, go bunúsach. 

Next méid. A ligean ar skip méid. Ar deireadh tá tú Díluchtaigh. Tá Díluchtaigh amháin nach mór dúinn a tharraingt ar an chlár nó códaithe go fóill. Ach a spreagadh mé leat chun iarracht códaithe é in ár sampla nasctha, mar shampla liosta. Ach Díluchtaigh intuitively Is cosúil go saor in aisce - nó ciall agam tá sé cosúil a sheiceáil. Ach amháin i gcás anois gach uair a bhfuil tú ag dul tríd, nach bhfuil tú ag seiceáil go simplí chun fheiceáil má tá tú do luach ann. Ach tá tú ag glacadh go nód agus freeing sé, go bunúsach. Sin an méid a iarrann Díluchtaigh tú a dhéanamh. Gach rud saor in aisce tú malloced. Mar sin, tá tú ag dul tríd an liosta ar fad arís, ag dul tríd an hash ar fad tábla arís. Ní gá an t-am a sheiceáil a fheiceáil cad atá ann. Just a saor in aisce cad atá ann. 

Agus ar deireadh mhéid. Ba chóir Méid a chur i bhfeidhm. Mura bhfuil tú a chur i bhfeidhm ar mhéid - Beidh mé a rá mar seo. Mura bhfuil tú a chur i bhfeidhm méid i díreach líne amháin de chód n-áirítear an ar ais ráiteas, tá tú ag déanamh méid mícheart. Sin a dhéanamh cinnte méid, le dearadh iomlán pointí, tá tú ag déanamh sé i díreach amháin líne de chód, lena n-áirítear an tuairisceán ráiteas. 

Agus nach bhfuil pacáiste suas go fóill, Akchar. Bébhar fonn. Bhí mé a rá go raibh maith agat guys chun teacht alt. Bíodh Oíche Shamhna Shona. Is é seo mo éadaí. Feicfidh mé a bheith ag caitheamh seo ar an Déardaoin má fheiceann mé tú ag uaireanta oifige. Agus má tá tú aisteach faoi roinnt níos mó cúlra maidir le éadaí, a bhraitheann saor in aisce a sheiceáil amach 2011 alt do scéal ar cén fáth mé ag caitheamh an éadaí Pumpkin. Agus tá sé ina scéal brónach. Sin a dhéanamh cinnte go bhfuil tú roinnt fíocháin in aice láimhe. Ach ar sin, má tá aon ceisteanna Feicfidh mé bata timpeall taobh amuigh i ndiaidh alt. Ádh mór ar fhadhb atá leagtha sé. Agus mar i gcónaí, má tá aon ceisteanna, in iúl dom.