[Ag seinm ceoil] 

Andi Peng: Fáilte go dtí seachtain 6 d'alt. Imigh muid ó ár gcaighdeán alt am Dé Máirt tráthnóna a ghabhann leis an álainn maidin Dé Domhnaigh. Go raibh maith agat do gach duine go Chuaigh mé inniu, ach dáiríre, babhta de bualadh bos. 

Sin iarracht go leor mór. Mé beagnach ní raibh a dhéanamh fiú é suas in am, ach bhí sé ceart go leor. Mar sin a fhios agam go bhfuil ar fad agat rinne ach é a chur ar an tráth na gceist. Gcéad dul síos, fáilte roimh a an taobh smeach de sin. 

Dara dul síos, beidh muid ag labhairt faoi. Beidh muid ag labhairt faoi an tráth na gceist. Beidh muid ag labhairt faoi conas bhfuil tú ag déanamh sa rang. Feicfidh tú breá. Tá mé do tráth na gceist do tú ag an deireadh anseo, mar sin más mian leat guys a ghlacadh a breathnú ar sé, go hiomlán fíneáil. 

Mar sin, go tapa sula dtosaíonn againn, an Tá clár oibre don lá atá inniu mar seo a leanas. Mar a fheiceann tú, tá muid lámhaigh bunúsach tapa trí a bunch iomlán de struchtúir sonraí i ndáiríre, i ndáiríre, i ndáiríre go tapa. Mar sin, mar shampla, ní bheidh sé lá atá inniu ann Super idirghníomhach. Beidh sé a bheith ach dom de chineál ar shouting rudaí a bhfuil tú, agus má amú agam ort, má tá mé ag dul ró-tapa, in iúl dom. Tá siad na sonraí díreach éagsúla Struchtúir, agus mar chuid de do pset seo seachtain le teacht, beidh tú go n-iarrfaí a chur i bhfeidhm ar cheann acu, b'fhéidir dhá cheann de them-- dhá cheann acu i do pset. OK, mar sin tá mé ag dul díreach a tús a chur le roinnt fógraí. Beidh muid ag dul thar stoic agus scuainí níos mó i doimhne ná an méid a rinne muid roimh an tráth na gceist. Beidh muid ag dul thar nasctha liosta arís, arís eile, níos mó sa domhain ná an méid bhí againn roimh an tráth na gceist. Agus ansin beidh muid ag labhairt faoi hash táblaí, crainn agus iarracht, a tá gach go leor riachtanach do do pset. Agus ansin beidh muid ag dul thar roinnt Leideanna cabhrach do pset5. 

OK, mar sin quiz 0. Bhí 58% ar an meán. Bhí sé an-íseal, agus mar sin tú guys go léir Rinne an-, go han-mhaith i gcomhréir leis sin. 

Go leor i bhfad, tá riail an ordóg má tá tú laistigh de dhiall caighdeánach an meán go háirithe ós rud go bhfuil muid i níos lú alt comfy, tá tú go hiomlán fíneáil. Tá tú ar an mbóthar. Tá an saol go maith. 

Tá a fhios agam go bhfuil sé scary chun smaoineamh go Fuair ​​mé mar a bheadh ​​40% ar an tráth na gceist. Tá mé ag dul a theipeann aicme seo. Geallaim duit, ní bhíonn tú dul a theipeann ar an rang. Tá tú go hiomlán fíneáil. 

Dóibh siúd agaibh a fuair os cionn an meán, go hiontach, go hiontach, cosúil le, a rinneadh go mór go maith. Tá mé iad le liom. Thig leat chun teacht leo a fháil ag deireadh an ailt. Bíodh a fhios agam má tá aon saincheisteanna, ceisteanna leo. Má chur linn suas ar do scór mícheart, in iúl dúinn. 

OK, mar sin pset5, tá sé seo i ndáiríre tseachtain aisteach don Yale sa chiall go bhfuil ár pset dlite Dé Céadaoin ag meán lae lena n-áirítear an lá déanach, mar sin tá sé i ndáiríre teoiriciúil dlite Dé Máirt ag meán lae. Is dócha aon duine críochnaithe ag Dé Máirt ag meán lae. Sin go hiomlán fíneáil. Táimid ag dul a bheith acu uaireanta oifige anocht chomh maith le oíche Dé Luain. Agus beidh gach ceann de na hailt seachtaine seo a iompú go hiarbhír i ceardlanna, mothaím saor in aisce a pop i aon alt is mian leat, agus beidh siad a bheith de chineál ar mion-pset ceardlanna chun cabhair ar sin. Mar sin, mar shampla, is é seo an t-alt amháin i gcás ina muid ag ábhar teagaisc. Beidh gach na rannóga eile a bheith ag díriú go heisiach ar cabhrú le haghaidh an pset. Yeah? 

LUCHT ÉISTEACHTA: Cá bhfuil uaireanta oifige? 

Andi Peng: Uaireanta Oifige tonight-- ó, ceist mhaith. I mo thuairimse, uaireanta oifige anocht atá i Teal nó ag Commons. Má leat a sheiceáil ar líne CS50 agus a théann tú chuig uaireanta oifige, ba chóir go mbeadh sceideal a insíonn tú i gcás ina bhfuil gach ceann acu. 

Tá a fhios agam ceachtar anocht nó go bhfuil amárach teal, agus sílim go féidir linn a bheith commons don oíche eile. Níl mé cinnte. Ceist mhaith. Seiceáil ar CS50. 

Cool, aon cheist agat maidir leis an sceideal le haghaidh an chéad cheann eile cosúil le trí lá? Geallaim duit guys cosúil le David dúirt, is é seo an barr an chnoic. Tá tú guys beagnach ann. Just a trí lá níos mó. Fháil ann, agus ansin beidh muid ag teacht gach síos. Beidh orainn a bheith sos deas CS-saor in aisce. Beidh muid ag teacht ar ais. Beidh muid Léim isteach ngréasán cláir agus forbairt, rudaí a bhfuil an-spraoi i gcomparáid chun roinnt de na psets eile. Agus beidh sé a bheith Chill, agus beidh orainn go leor spraoi. Beidh orainn níos mó candy. Gabh ár leithscéal as candy. Rinne mé dearmad candy. Bhí sé ina mhaidin garbh. Mar sin, tá tú guys beagnach ann, agus tá mé i ndáiríre bródúil as tú guys. 

OK, mar sin cruacha. A grá an cheist faoi Jack agus a chuid éadaigh ar an tráth na gceist? Duine ar bith? OK, go breá. 

Mar sin, go bunúsach is féidir leat pictiúr Jack, an Guy anseo, Is breá a chur ar an éadaí amach as an barr an chairn, agus cuireann sé é ar ais isteach ar an chairn tar éis sé ar a rinneadh. Mar sin, ar an mbealach seo, sé riamh cosúil le bheith ag dul go bun an Stack ina éadaí. Mar sin, seo de chineál ar cur síos an struchtúr sonraí bunúsacha gcaoi a bhfuil Stack i bhfeidhm. 

Go bunúsach, smaoineamh ar Stack mar aon chairn de rudaí nuair a chuir tú rudaí isteach ar an barr, agus ansin pop tú iad amach ó bharr. Dá bhrí sin tá LIFO an acrainm is maith linn a use-- In caite, An Chéad Amach. Agus mar sin go deireanach i go dtí an barr an Is é Stack an chéad cheann a thagann amach. Agus mar sin an dá thaobh is maith linn a chomhlachú leis go bhfuil ar a dtugtar a bhrú agus pop. Nuair a bheidh tú a bhrú isteach ar an rud éigin Stack, agus tú pop sé ar ais ar bun. 

Agus mar sin buille faoi thuairim mé é seo de chineál ar coincheap teibí dóibh siúd agaibh mian leo a fheiceáil cosúil le a chur chun feidhme iarbhír seo ar fud an domhain fíor. Cé mhéad de tú a scríobh aiste b'fhéidir cosúil le uair an chloig sula raibh sí dlite, agus scrios tú thaisme ollmhór smután de, cosúil le thaisme? Agus ansin cad a dhéanann rialú úsáidimid é a chur ar ais? Rialú-Z, yeah? Rialú-Z, mar sin an méid na n-amanna go bhfuil Control-Z shábháil mo shaol, Tá shábháil mo thóin, gach uair go feidhme trí Stack. 

Go bunúsach an t-eolas go léir sin ar do doiciméad Word, Faigheann sé bhrú agus popped ag a bheidh. Agus mar sin go bunúsach aon uair is tú rud ar bith a scriosadh, pop tú ar ais ar bun. Agus ansin más gá duit é ar ais ar, tú a bhrú, a bhfuil cad a dhéanann Rialú-C. Agus feidhm domhan chomh fíor struchtúr sonraí conas simplí Is féidir le cabhrú le do shaol laethúil. 

Mar sin, is struct ar an mbealach go linn a chruthú i ndáiríre Stack. Cineál táimid ag struct shainiú, agus ansin tugaimid Stack ar bun an leathanaigh. Agus laistigh den chairn, tá dhá paraiméadair gur féidir linn a ionramháil go bunúsach, ionas go mbeidh muid Char cumas teaghráin réalta. 

Gach go bhfuil sé ag déanamh ag cruthú sraith gur féidir linn a stóráil bith is mian leat ar féidir linn a chinneadh a cumas. Cumas An bhfuil ach an méid max de míreanna féidir linn a chur isteach sa eagar. Is é méid slánuimhir an gcuntar go gcoinníonn Tá súil a choinneáil ar cé mhéad míreanna i láthair na huaire sa an chairn. Mar sin, ansin is féidir linn súil a choinneáil ar, A, dá conas mór é an chairn iarbhír, agus, B, cé mhéad den chairn Líonadh linn a toisc nach bhfuil muid ag iarraidh thar maoil thar a bhfuil ár n-acmhainn. 

Mar sin, mar shampla, an álainn Bhí ceist ar do tráth na gceist. Go bunúsach conas a bhrú linn a isteach ar an barr an chairn. Simplí go leor. Má fhéachann tú ar sé, beidh orainn siúl tríd an. Má [inaudible] size-- cuimhnigh, aon uair is tú ag iarraidh rochtain a fháil ar aon paraiméadar laistigh de struct, a dhéanann tú an t-ainm ar an struct.parameter. 

Sa chás seo, tá s ainm ár chairn. Is mian linn a rochtain a fháil ar an méid de, agus mar sin a dhéanann muid s.size. Mar sin, chomh fada is nach bhfuil an méid cothrom le cumas nó chomh fada mar tá sé níos lú ná acmhainn, ceachtar bheadh ​​ag obair anseo. 

Ba mhaith leat rochtain a fháil ar an taobh istigh de do Stack, mar sin s.strings, agus tá tú ag dul a chur ar go bhfuil uimhir nua gur mian leat a chur isteach i ann. Ligean le rá ach go mbeidh muid ag iarraidh a cuir isteach slánuimhir n isteach ar an chairn, d'fhéadfadh muid a s.strings a dhéanamh, lúibíní, ionann s.size n. Toisc go bhfuil an méid nuair a muid atá faoi láthair i an chairn má táimid ag dul a bhrú sé ar, táimid ag teacht go díreach cibé áit a bhfuil an méid, an fullness reatha an chairn, agus a bhrú muid an slánuimhir n ar sé. Agus ansin ba mhaith linn a dhéanamh cinnte go tá muid ag incriminteach freisin méid an n, ionas gur féidir linn súil a choinneáil ar tá muid Chuir an rud breise go dtí an chairn. Anois, ní mór dúinn a méid níos mó. An bhfuil sé seo ciall a dhéanamh anseo gach duine, cé go loighciúil a oibríonn sé? Bhí sé de chineál ar tapaidh. LUCHT ÉISTEACHTA: An féidir leat dul thar na s.stringss.strings [s.size] arís? Andi Peng: Cinnte, mar sin cad a dhéanann s.size thabhairt dúinn i láthair na huaire? LUCHT ÉISTEACHTA: Tá sé an méid atá ann faoi láthair. Andi Peng: Go díreach, agus mar sin an Innéacs reatha go bhfuil ár méid ag, agus mar sin ba mhaith linn a chur ar an slánuimhir nua gur mhaith linn a chur isteach i s.size. Bhfuil ciall? Mar gheall ar s.strings, go léir go Is é an t-ainm ar an eagar. Léir go bhfuil sé go bhfuil rochtain ar an eagar laistigh dár struct, agus mar sin más mian linn a cuir n isteach sa innéacs, Is féidir linn a rochtain a fháil ach é ag baint úsáide as lúibíní s.size. Cool. 

Gach ceart, pop, pseudocode mé amach é ar do shon guys, ach coincheap den chineál céanna. Bhfuil ciall? Má tá an méid níos mó ná náid, ansin tú tá a fhios gur mian leat rud éigin a ghlacadh amach toisc mura bhfuil an méid níos mó ná náid, ansin tú tá aon rud sa chairn. 

Mar sin, ba mhaith leat ach a fhorghníomhú gcód seo, is féidir é ach pop má tá rud éigin a pop. Mar sin, má tá an méid níos mó ná 0, táimid ag lúide an méid. Decrement muid an méid agus ansin ar ais is cuma cad é taobh istigh de sé mar gheall ar trí popping, ba mhaith linn a Rochtain cuma cad stóráiltear san innéacs de bharr an chairn. Ciall gach rud a dhéanamh? Má rinne mé tú guys scríobh seo amach, mbeadh tú guys a bheith in ann a scríobh sé amach? OK, is féidir leat guys imirt ar fud leis. Uimh imní mura bhfuil tú é a fháil. Ní chuirimid ag am chun cód sé amach sa lá atá inniu mar gheall ar tá muid bhí a lán de na struchtúir chun dul tríd, ach go bunúsach pseudocode, an-, an-chosúil leis bhrú. Just a leanúint ar feadh an loighic. Bí cinnte go bhfuil tú ag teacht ar go léir an gnéithe de do struct i gceart. Yeah? 

LUCHT ÉISTEACHTA: An mbeidh na sleamhnáin agus an rud ar fad a bheith suas lá atá inniu ann-ish? Andi Peng: I gcónaí, yep. Tá mé ag dul chun iarracht a dhéanamh a chur ar seo suas cosúil le uair an chloig tar éis. Feicfidh mé ríomhphost David, beidh David iarracht a é a chur ar bun cosúil le uair an chloig tar éis seo. 

OK, mar sin ansin bogadh muid isteach seo eile struchtúr sonraí álainn ar a dtugtar scuaine. Mar is féidir leat guys a fheiceáil anseo, a scuaine, le haghaidh na Breataine i measc linn, léir go bhfuil sé go bhfuil líne. Mar sin, contrártha leis an méid cheapann tú go bhfuil Stack, Is scuaine díreach cad logically cheapann tú go bhfuil sé. Tá sé seo i seilbh na rialacha FIFO, a bhfuil First In, First Out. Má tá tú an chéad ceann sa líne, tá tú an chéad cheann a a thagann amach as an líne. 

Mar sin, cad is maith linn a ghlaoch seo Tá dequeueing agus enqueueing. Más mian linn rud éigin a chur chun ár scuaine, Enqueue muid. Más mian linn a Díchiúáil, nó a thógáil rud éigin ar shiúl, Díchiúáil againn. 

Ciall mar sin céanna go bhfuil muid de chineál ar gnéithe seasta-mhéid chruthú go bhfuil muid Is féidir le stóráil áirithe rudaí, ach is féidir linn freisin athrú i gcás ina bhfuil muid ag chur paraiméadair taobh istigh acu bunaithe ar cén cineál feidhmiúlacht ba mhaith linn. Mar sin, stacks, bhíomar ag iarraidh na deireanach amháin, N a bheith ar an chéad amach amháin. Is Queue ba mhaith linn an chéad rud isteach chun bheith ar an chéad rud amach. 

Mar sin, an struct-cineál shainiú, mar is féidir leat a fheiceáil, tá sé le beagán difriúil as an méid a bhí an chairn toisc nach bhfuil ach ní mór dúinn a choinneáil ar súil a choinneáil ar áit a bhfuil an méid faoi láthair, ba mhaith linn freisin súil a choinneáil ar an ceann a choinneáil chomh maith le áit a bhfuil muid i láthair na huaire. Mar sin, Sílim go bhfuil sé níos éasca má tá mé a tharraingt suas seo. Mar sin, a ligean ar a shamhlú againn fuair scuaine, mar sin a ligean le rá go bhfuil an ceann ceart anseo. An ceann an líne, a ligean ar ach a rá go bhfuil i láthair na huaire ann, agus ba mhaith linn a chur isteach rud éigin isteach sa scuaine. Tá mé ag dul chun glaoch go bunúsach méid is é an rud céanna mar eireaball, an deireadh cibé áit a bhfuil do scuaine. Let a rá ar díreach é méid ceart anseo. 

Mar sin, conas a dhéanann feasibly amháin cuir isteach ar rud éigin isteach i scuaine? Cad innéacs ar mhaith linn a chur áit ar mhaith linn a chur isteach i. Más é seo an tús do scuaine agus is é seo an deireadh sé nó an méid de sé, i gcás ina dhéanaimid ag iarraidh a chur ar an réad seo chugainn? 

LUCHT ÉISTEACHTA: [inaudible] Andi Peng: Go díreach, ba mhaith leat a chur sé ag brath ar tú scríobh sé. Ceachtar tá sé seo bán nó go bhfuil bán. Mar sin ba mhaith leat a chur dócha anseo mar gheall más rud é an méid is-- má tá na ar fad iomlán, ba mhaith leat chun é a chur ar dheis anseo, ceart? 

Agus mar sin go, cé an-, an- simplí, ceart go leor i gcónaí ní mar gheall ar an difríocht is mó idir scuaine agus Stack is é gur féidir an scuaine a manipulated i ndáiríre ionas go mbeidh na hathruithe ceann brath ar an áit is mian leat an tús do CUE chun tús a chur. Agus mar thoradh air sin, do eireaball ag dul freisin a athrú. Agus mar sin chur le breathnú ar an cód ceart anois. Mar go raibh tú guys iarr freisin chun scríobh amach ar an tráth na gceist, Enqueue. B'fhéidir go mbainfidh muid ag labhairt trí cén fáth an freagra a bhí cad a bhí sé. 

Ní raibh mé in ann oiriúnach go maith an líne seo ar cheann amháin, ach go bunúsach an píosa de chód Ba chóir go mbeadh ar líne amháin. Caith cosúil le 30 soicind. A chur le breathnú, agus a fheiceáil cén fáth is é seo an bealach go bhfuil sé. 

An-, struct an-chosúil, an-, an- Struchtúr chineál céanna mar an roimhe Stack ach amháin i gcás b'fhéidir líne amháin de chód. Agus go líne amháin de chód Cinneann an fheidhmiúlacht. Agus idirdhealú sé i ndáiríre scuaine as Stack. 

Duine ar bith ag iarraidh a chur ar stab ag míniú cén fáth a tá tú Fuair ​​an rud casta i anseo? Feicimid ar ais ár modulus cara iontach. Mar a bheidh tú guys teacht go luath a aithint i gcláir, beagnach ag am ar bith is gá duit rud éigin a wrap timpeall rud ar bith, Tá modulus ag dul a bheith ar an mbealach chun é a dhéanamh. Mar sin a fhios agam go, duine ar bith ag iarraidh a dhéanann chun iarracht a mhíniú go líne de chód? Yeah, tá gach freagraí inghlactha agus fáilte roimh chách. LUCHT ÉISTEACHTA: An bhfuil tú ag caint liom? Andi Peng: Yeah. LUCHT ÉISTEACHTA: Ó, gan aon leithscéal. Andi Peng: OK, mar sin a ligean ar siúl trí gcód seo. Mar sin, nuair tú ag iarraidh a add rud éigin isteach ar scuaine, sa chás álainn a tharlaíonn an ceann a bheith ar dheis anseo, tá sé an-éasca dúinn chun dul díreach chuig an deireadh cuir isteach rud éigin, ceart? Ach tá an pointe iomlán de scuaine go bhfuil an ceann is féidir dinimiciúil i ndáiríre athrú ag brath ar nuair a muid Ba mhaith an tús ár q a bheith, agus mar sin, an t-eireaball ag dul freisin a athrú. 

Agus mar sin a shamhlú go bhfuil an raibh sé seo scuaine, ach ba é seo an scuaine. Ligean le rá go bhfuil an ceann ceart anseo. Ligean le rá ar ár scuaine d'fhéach sé mar seo. Má bhíomar ag iarraidh a athrú i gcás is é an tús an líne, ligean le rá bhog muid a ceann Ar an mbealach seo agus méideanna anseo. 

Anois, ba mhaith linn rud éigin a chur leis an scuaine, ach de réir mar is féidir leat a fheiceáil guys, nach bhfuil sé chomh simplí agus is díreach cuir cuma cad é tar éis an méid mar gheall ar ansin reáchtáil againn as Rá dár sraith iarbhír. Sa chás go ba mhaith linn a chur i ndáiríre anseo. Sin an áilleacht scuaine is é sin le linn, amhairc sé Breathnaíonn an nós téann an líne mar seo, ach nuair a stóráiltear i struchtúr sonraí, a thugann siad é mar nós timthriall. De chineál ar wraps sé thart chun tosaigh ar an mbealach céanna gur féidir le líne wrap freisin timpeall ag brath ar cibé áit tú ag iarraidh a tús na líne a bheith. Agus mar sin má táimid a breathnú síos anseo, a ligean ar Deir bhíomar ag iarraidh a chruthú fheidhm a dtugtar Enqueue. Bhíomar ag iarraidh a chur int n isteach q. Más rud é q-- q.size linn a mbainfidh glaoch go ár sonraí structure-- mura bhfuil ár queue.size cothrom le cumas nó má tá sé níos lú ná acmhainn, Is q.strings an eagar laistigh dár q. Táimid ag dul a shocrú go cothrom le q.heads, atá ar dheis anseo, chomh maith le q.size modulus trí chumas, a wrap dúinn ar ais thart anseo. 

Mar sin, sa sampla seo, innéacs de ceann is 1, ceart? Is é an t-innéacs de mhéid 0, 1, 2, 3, 4. Mar sin, is féidir linn a dhéanamh 1 móide 4 modulus ag ár n-acmhainn a bhfuil 5. Cad a bhfuil a thabhairt dúinn? Cad é an t-innéacs a a thagann as seo? 

LUCHT ÉISTEACHTA: 0. 

Andi Peng: 0, a tharlaíonn a bheith ar dheis anseo, agus mar sin ba mhaith linn a bheith in ann a chur isteach i gceart anseo. Agus mar sin an chothromóid anseo chineál de oibríonn go díreach le haon huimhreacha brath ar an áit do ceann agus do mhéid atá. Má tá a fhios agat cad iad siúd Tá rudaí, tá a fhios agat go díreach áit ar mhaith leat a chur isteach is cuma cad é tar éis do scuaine. An bhfuil a dhéanamh le gach duine ciall? 

Tá a fhios agam de chineál ar inchinn teaser go háirithe ós rud é seo Tháinig i ndiaidh do tráth na gceist. Ach tá súil againn gach duine is féidir a thuiscint anois cén fáth seo a réiteach nó an Is é feidhm an mbealach go bhfuil sé. Duine ar bith le beagán doiléir ar sin? OK. 

Agus mar sin anois, má tá tú ag iarraidh a Díchiúáil, seo Is i gcás ina mbeadh ár ceann a aistriú mar má bhí muid a Díchiúáil, ní féidir linn éirí de thalamh an deireadh an q. Is mian linn a éirí de thalamh an ceann, ceart? Mar sin, mar thoradh air sin, tá ceann ag dul a athrú, agus is é sin an fáth nuair Enqueue tú, atá tú a fuair súil a choinneáil ar i gcás ina do cheann agus do mhéid atá le bheith in ann a chur isteach isteach sa suíomh ceart. 

Agus mar sin nuair Díchiúáil tú, Pseudocode mé freisin sé amach. Thig leat a más mian leat chun iarracht códaithe seo amach. Ba mhaith leat chun bogadh an ceann, ceart? Má bhí mé a Díchiúáil, mé Bheadh ​​bogadh an ceann os a chionn. Bheadh ​​sé seo a bheith ar an ceann. 

Agus bheadh ​​ár méid atá ann faoi láthair dhealú mar gheall orainn a thuilleadh ceithre eilimintí sa eagar. Ní mór dúinn ach trí, agus ansin ba mhaith linn a thabhairt ar ais cuma cad a bhí stóráilte taobh istigh an ceann mar ba mhaith linn an deis seo a luach amach mar sin an-chosúil leis an chairn. Just a bhfuil tú ag cur ó áit eile, agus tá tú chun a athshannadh do pointeoir go dtí áit eile mar thoradh air. Logically, gach duine a leanúint? Mór. 

OK, mar sin táimid ag dul chun labhairt le beagán níos mó sa domhain faoi liostaí nasctha toisc go mbainfidh siad a bheith an-, an-luachmhar ar do shon i gcúrsa seachtaine seo psets. Liostaí nasctha, mar atá tú guys Is féidir le cuimhneamh, gach go bhfuil siad Tá nóid go bhfuil nóid áirithe luachanna araon luach agus pointeoir atá nasctha le chéile ag na leideanna. Agus mar sin an struct ar an gcaoi chruthú dúinn go bhfuil nód anseo táimid ag tá slánuimhir n, a bhfuil cuma cad an luach i siopa nó teaghrán n nó is cuma cad ba mhaith leat a ghlaoch air, an réalta char n. Struct réalta nód, a bhfuil an pointeoir gur mian leat a bheith acu i ngach nód, tú ag dul a bheith acu go pointe pointeoir i dtreo chugainn. Feicfidh tú an ceann de liosta nasctha go dul a chur in iúl don chuid eile den na luachanna mar sin de agus mar sin de dtí go sroicheann tú ar deireadh thiar an deireadh. Agus tá sé seo nód seo caite ach dul chun nach bhfuil pointeoir. Tá sé ag dul a chur in iúl go dtí null, tá agus nuair tá a fhios agat atá tú a bhuail an deireadh na bliana do liosta nasctha Is nuair do pointeoir caite Ní iúl le rud ar bith. 

Mar sin, táimid ag dul chun dul le beagán níos mó i doimhneacht maidir le conas a bheadh ​​ceann amháin, b'fhéidir, cuardaigh liosta nasctha. Cuimhnigh cad iad cuid de na míbhuntáistí de na liostaí nasctha véarsaí eagar maidir cuardaigh. Sraith is féidir leat cuardach a dhéanamh ar dénártha, ach cén fáth nach féidir a dhéanann tú sin i liosta nasctha? 

LUCHT ÉISTEACHTA: Mar gheall ar a bhíonn siad go léir nasctha, ach níl a fhios agat go maith nuair a [Inaudible]. 

Andi Peng: Yeah, go díreach cuimhneamh mar sin go bhfuil an brilliance de eagar ba é an bhfíric go raibh muid cuimhne rochtain randamach áit má bhí mé an luach ó innéacs sé, d'fhéadfadh liom a rá ach innéacs sé, a thabhairt dom go luach. Agus sin mar gheall ar arrays atá curtha in eagar i spás tadhlach de chuimhne in aon áit amháin, de bhrí de chineál ar liostaí nasctha Tá interspersed randamach go léir ar fud, agus an t-aon bhealach is féidir leat ceann a fháil Is trí pointeoir a insíonn tú an seoladh an áit ina bhfuil an nód seo chugainn. 

Agus mar sin mar thoradh air sin, an t-aon bhealach chun cuardach trí liosta nasctha Tá cuardaigh líneach. Mar níl a fhios agam go díreach i gcás Is é an luach 12ú ar an liosta nasctha, Caithfidh mé a lean an iomlán an liosta sin amháin a nasctha trí cheann amháin as an ceann go dtí an chéad nód, leis an dara nód, chuig an tríú nód, léir ar an mbealach síos go dtí go rachaidh mé ar deireadh don áit a mbeidh nód Táim ag lorg. Agus mar sin sa chiall seo, cuardaigh ar liosta nasctha i gcónaí n. Tá sé i gcónaí n. Tá sé i gcónaí in am líneach. 

Agus mar sin an cód ina táimid ag a chur chun feidhme seo, agus tá sé seo Is le beagán nua duit guys ó tú Nach bhfuil guys Labhair ndáiríre faoi nó riamh leideanna le feiceáil i conas a cuardach a dhéanamh tríd leideanna, mar sin beidh orainn siúl trí seo an-, an-mhall. Mar sin, cuardaigh bool, ceart, a ligean ar a shamhlú ba mhaith linn a chruthú feidhm a dtugtar cuardach a tuairisceáin fíor má fuair tú luach taobh istigh den nasctha liosta, agus tuairisceáin sé bréagach ar shlí eile. Tá liosta de na réalta nód i láthair na huaire ach an pointeoir go dtí an chéad mhír i do liosta nasctha. Is slánuimhir n an luach go bhfuil tú cuardach le haghaidh sa liosta sin. 

Mar sin, is ionann pointeoir réalta nód liosta. Ciallaíonn sin táimid ag leagan síos agus ag cruthú pointeoir leis go bhfuil an chéad nód taobh istigh an liosta. Tá ag gach duine liom? Mar sin, má bhí muid chun dul ar ais anseo, ba mhaith liom a initialized pointeoir go pointí go de is cuma cad é an liosta sin an ceann. 

Agus ansin nuair a fhaigheann tú síos anseo, cé nach bhfuil pointeoir null comhionann, ionas go bhfuil an lúb ina bhfuil muid ag dul a bheith ina dhiaidh sin traversing an chuid eile den ár liosta mar gheall ar cad a tharlaíonn nuair a ionann pointeoir null? Tá a fhios againn go bhfuil have-- linn a 

LUCHT ÉISTEACHTA: [inaudible] 

Andi Peng: Go díreach, agus mar sin tá a fhios againn go tá muid bainte amach faoi dheireadh na an liosta, ceart? Má théann tú ar ais anseo, gach nód Ba chóir a bheith dírithe go nód eile agus mar sin de agus mar sin de go dtí go bhuail tú ar deireadh thiar an eireaball do liosta nasctha, a bhfuil pointeoir go díreach Ní pointe eile in áit ar bith ná aon. Agus mar sin a fhios agat go bunúsach go tá do liosta fós ann suas go dtí go ndéanann pointeoir cothrom null mar aon uair cothrom le sé null, tá a fhios agat go níl aon stuif níos mó. 

Mar sin, tá go bhfuil an lúb ina bhfuil muid ag dul go bhfuil an cuardach iarbhír. Agus má dhéanann an pointer-- a fheiceann tú chineál sin de fheidhm arrow ann? Mar sin má pointí pointeoir chuig n, más rud é an pointeoir ar n ionann ionann n, ionas Ciallaíonn sé sin go má an pointeoir go bhfuil tú cuardach le haghaidh ar an deireadh gach Tá nód comhionann iarbhír leis an luach bhfuil tú ag lorg, ansin ba mhaith leat a thabhairt ar ais fíor. Sin, go bunúsach, má tá tú ag nód a Tá an luach a bhfuil tú ag lorg, tá a fhios agat go atá tú in ann a chuardach go rathúil. 

Seachas sin, ba mhaith leat a chur ar bun do pointeoir leis an nód seo chugainn. Sin é an rud go bhfuil líne anseo a dhéanamh. Pointeoir ionann pointeoir seo chugainn. Tá ag gach duine a fheiceáil conas tá go obair? 

Agus go bunúsach go bhfuil tú ag dul go dtí díreach Traverse an iomlán an liosta, resetting do pointeoir gach uair go dtí go bhuail tú ar deireadh thiar deireadh an liosta. Agus tá a fhios agat nach bhfuil aon nóid níos mó chun cuardach a trí, agus ansin is féidir leat filleadh bréagach mar a fhios agat go bhfuil, ó, go maith, má bhí mé in ann a chuardach trí iomláine an liosta. Más rud é sa sampla seo, má bhí mé a lorg ar an luach de 10, agus tús a chur mé ag ceann, agus Cuardaigh mé go léir ar an mbealach síos, agus fuair mé faoi dheireadh go dtí seo, a pointeoir go pointí a margadh saothair, Tá a fhios agam go bhfuil, cacamas, buille faoi thuairim mé nach bhfuil i 10 an liosta seo toisc nach raibh mé in ann é a aimsiú. Agus tá mé ag deireadh an liosta. Agus sa chás sin a fhios agat Tá mé ag dul a thabhairt ar ais bréagach. 

Lig go soak i haghaidh píosa beag. Beidh sé seo deas tábhachtach do do pset. Is é an loighic sé an-simplí, b'fhéidir syntactically ach feidhme. Guys tú ag iarraidh a dhéanamh cinnte go dtuigeann tú. Cool. 

OK, mar sin conas ba mhaith linn a bheith nóid a chur isteach, ar dheis, i liosta cuimhneamh mar gheall ar cad iad na cén de na sochair a bhfuil liosta nasctha i gcoinne sraith i dtéarmaí stórála? 

LUCHT ÉISTEACHTA: Tá sé dinimiciúil, mar sin tá sé níos éasca to-- 

Andi Peng: Go díreach, mar sin tá sé dinimiciúil, a a chiallaíonn gur féidir é a leathnú agus a Laghdaigh ag brath ar riachtanais an úsáideora. Agus mar sin, sa chiall seo, ní féidir linn gá le dramhaíl cuimhne neamhriachtanach mar gheall mé más rud é nach bhfuil a fhios agam cé mhéad Ba mhaith liom luachanna a stóráil, ní dhéanann sé ciall a dhéanamh dom a chruthú le sraith gheall más mian liom a stóráil 10 luachanna agus a chruthú mé le sraith de 1,000, go a lán de chuimhne amú, Leithroinnte. Sin an fáth ba mhaith linn a úsáid nasctha liosta a bheith in ann dinimiciúil athrú nó Laghdaigh ár méid. 

Agus mar sin go ndéanann leanas a chur isteach le beagán níos casta. Ós rud é nach féidir linn a rochtain a fháil ar go randamach eilimintí an mbealach go mbeadh muid de le sraith. Más mian liom a chur isteach gné isteach sa seachtú innéacs, Is féidir liom a chur isteach ach é isteach sa seachtú innéacs. Ar liosta nasctha, ní dhéanann sé go leor ag obair chomh héasca, agus mar sin má bhíomar ag iarraidh a chur isteach an ceann anseo ar an liosta nasctha, amhairc, tá sé an-éasca a fheiceáil. Ba mhaith linn ach a chur isteach sé ceart ann, ar dheis ag an tús an liosta, ceart tar éis ceann. 

Ach an bealach ina ní mór dúinn a athshannadh na leideanna go bhfuil beagán convoluted nó, go loighciúil, a dhéanann sé ciall, ach ba mhaith leat a dhéanamh cinnte go bhfuil tú é go hiomlán síos mar gheall an rud deireanach mian leat is é sin le athshannadh pointeoir an bhealach go bhfuil muid ag déanamh anseo. Má tá tú téigh i an pointeoir ó cheann go 1, ansin ar fad ar tobann na chuid eile de do liosta nasctha Tá caillte toisc go bhfuil tú nach i ndáiríre chruthaigh rud ar bith sealadach. Sin in iúl do na 2. Má tá tú athshannadh an pointeoir, ansin an Tá eile de do liosta caillte go hiomlán. Mar sin, ba mhaith leat a bheith an-, an-chúramach anseo a shannadh ar dtús leis an pointeoir ó cibé tú ag iarraidh a chur isteach i cibé áit is mian leat, agus ansin tú Is féidir dereference téigh an chuid eile de do liosta. 

Mar sin, baineann sé seo le cibé áit bhfuil tú ag iarraidh a chur isteach i. Más mian leat a chur isteach ar an ceann, más mian leat a fhreagairt anseo, más mian leat a chur isteach ar an deireadh, go maith, an deireadh I buille faoi thuairim a bheadh ​​agat ach nach bhfuil aon pointeoir, ach tú ag iarraidh a dhéanamh cinnte nach bhfuil tú chailleann an chuid eile de do liosta. Ba mhaith leat i gcónaí chun a chinntiú tá do nód nua ag cur in iúl i dtreo is cuma cad tú ag iarraidh a chur isteach i, agus ansin is féidir leat a chur ar an shlabhrú ar. Tá ag gach duine soiléir? 

Tá sé seo ag dul a bheith ar cheann de na saincheisteanna fíor. Ceann de na ceisteanna is mór- tú ag dul a bheith ar do pset is é sin bhfuil tú ag dul chun iarracht a chruthú liosta nasctha agus rudaí isteach ach ansin chailleann ach an chuid eile de do liosta nasctha. Agus tú ag dul a bheith cosúil le, I níl a fhios cén fáth go bhfuil seo ag tarlú? Agus tá sé ina pian chun dul tríd agus cuardach gach ceann de do threo. 

Agus ráthaíocht mé tú ar an pset, scríobh agus ag tarraingt na nóid amach a bheith an-, an-chabhrach. Mar sin, is féidir leat a choinneáil go hiomlán rian an áit ina bhfuil gach do leideanna, cad atá ar siúl mícheart, i gcás ina bhfuil gach do nóid, an méid is gá duit a dhéanamh chun rochtain a fháil nó chur isteach nó a scriosadh nó aon cheann acu. Tá ag gach duine maith leis sin? Cool. 

Mar sin má bhíomar ag iarraidh chun breathnú ar an cód? Ó, níl a fhios agam má táimid Is féidir a fheiceáil the-- OK, mar sin ag barr is léir go bhfuil sé feidhm isteach ainmnithe áit ar mhaith linn a a chur isteach slánuimhir n isteach ar an liosta nasctha. Táimid ag dul chun siúl tríd an. Tá sé a lán de chód, a lán de chomhréir nua. Beidh orainn a bheith ceart go leor. 

Mar sin, suas ag an mbarr, aon uair ba mhaith linn rud ar bith a chruthú cad is gá dúinn a dhéanamh, go háirithe má tú ag iarraidh gan a é a stóráil ar an chairn ach sa gcarn? Téimid go dtí malloc, ceart? Mar sin, táimid ag dul a chruthú pointeoir. Nód, pointeoir, ionann nua malloc an méid de nód mar ba mhaith linn go nód a chruthú. Ba mhaith linn an méid cuimhne a thógann nód suas le leithroinnt don a chruthú ar an nód nua. 

Agus ansin táimid ag dul a sheiceáil chun fheiceáil má ionann ionann nua null. Cuimhneamh ar cad a dúirt muid? Cibé rud a tú malloc, cad ní mór duit a dhéanamh i gcónaí? Ní mór duit seiceáil i gcónaí a fheiceáil cibé acu atá nó nach bhfuil null. 

Mar shampla, má tá do oibriúcháin Bhí córas go hiomlán go hiomlán, má bhí tú nach bhfuil níos mó cuimhne ag go léir agus tú iarracht a dhéanamh malloc, go mbeadh sé ar ais null duit. Agus mar sin má tá tú iarracht é a úsáid nuair a bhí sé dírithe ar null, nach bhfuil tú ag dul go dtí in ann rochtain a fháil ar an bhfaisnéis sin. Agus mar sin, mar shampla, bhíomar ag iarraidh a dhéanamh cinnte go bhfuil aon uair a bhfuil tú ag mallocing, bhfuil tú ag seiceáil i gcónaí a fheiceáil má is é sin chuimhne a thug tú null. Agus más rud é nach bhfuil sé, ansin is féidir linn bogadh ar leis an gcuid eile d'ár cód. 

Mar sin, táimid ag dul chun thúsú an nód nua. Táimid ag dul a dhéanamh n nua ionann n. Agus ansin tá muid ag dul a dhéanamh leagtar nua an pointeoir ar nua go null mar gheall ar ceart anois ní dhéanaimid iarraidh rud ar bith chun é a chur in iúl chun. Tá aon smaoineamh nuair tá sé ag dul chun tú a chur, agus ansin más mian linn a cuir isteach é ag ceann, ansin is féidir linn a athshannadh an pointeoir chun an ceann. An bhfuil gach duine a leanúint ar an loighic de i gcás ina bhfuil sin ag tarlú? 

Gach tá muid ag déanamh go bhfuil a chruthú nua nód, ag leagan an pointeoir a margadh saothair, agus ansin a athshannadh sé leis an ceann má táimid tá a fhios ba mhaith linn a chur isteach ag an ceann. Agus ansin tá an ceann ag dul go dtí pointe i dtreo go nód nua. Tá ag gach duine ceart go leor leis sin? 

Mar sin, tá sé ina phróiseas dhá chéim. Tá sé agat a chéad shannadh is cuma cad tá tú ag a chruthú. Socraigh go pointeoir chuig an tagartha, agus ansin tú Is féidir de chineál ar téigh i an chéad pointeoir agus pointe sé i dtreo an nód nua. Pé áit is mian leat a chur isteach air, Tá go loighic ag dul a shealbhú fíor. 

Tá sé cineál cosúil shannadh athróga sealadacha. Cuimhnigh, tá tú bhí chun a chinntiú go bhfuil tú nach gcaillfidh súil a choinneáil ar má tá tú ag swapping. Ba mhaith leat a dhéanamh cinnte go bhfuil tú athróg sealadach chineál sin de gcoinníonn súil a choinneáil ar an áit ina bhfuil rud stóráilte ionas go mbeidh tú nach gcaillfidh aon luach i gcúrsa de cosúil messing ar fud leis é. 

OK, mar sin beidh cód a bheith anseo. Guys tú a chur le breathnú i ndiaidh alt. Beidh sé a bheith ann. 

Mar sin, buille faoi thuairim mé conas a dhéanann seo difriúil má bhíomar ag iarraidh a chur isteach i lár nó an deireadh? An bhfuil aon duine ag smaoineamh ar cad é an pseudocode mar an tagairt loighciúil go mbeadh muid a chur dá bhíomar ag iarraidh a chur isteach sé i lár? Mar sin má bhíomar ag iarraidh a chur isteach ag an ceann, tá gach a dhéanaimid a chruthú nód nua. A leag muid an pointeoir sin nód nua le cibé an ceann, agus ansin leag muid an ceann leis an nód nua, ceart? Má bhíomar ag iarraidh a chur isteach sé i lár an liosta, cad atá againn a dhéanamh? 

LUCHT ÉISTEACHTA: Bheadh ​​sé fós a bheith ina phróiseas den chineál céanna de cosúil le pointeoir a shannadh agus ansin shannadh go pointeoir, ach ba mhaith linn a aimsiú ann. 

Andi Peng: Go díreach, agus mar sin go díreach an bpróiseas céanna ach amháin agat ní mór a aimsiú i gcás go díreach leat ag iarraidh go pointeoir nua chun dul isteach, mar sin más mian liom a chur isteach i lár nasctha list-- OK, ligean le rá go bhfuil ar ár liosta nasctha. Más mian linn a chur isteach sé ceart anseo, táimid ag dul a chruthú nód nua. Táimid ag dul a malloc. Táimid ag dul a chruthú nód nua. Táimid ag dul a shannadh ar an pointeoir ar an nód anseo. 

Ach an fhadhb atá ann go difriúil ó áit a bhfuil an ceann Is go raibh a fhios againn go díreach áit a bhfuil an ceann. Bhí sé ar dheis ag an gcéad, ceart? Ach anseo tá muid fuair a choinneáil ar rian ar an áit ina bhfuil muid ag chur isteach sé isteach. Má tá muid ag chur isteach ar ár nód anseo, tá muid fuair chun a chinntiú go bhfuil an ceann roimhe a ghabhann leis an nód is é an ceann a reassigns an pointeoir. Mar sin, ansin caithfidh tú a de chineál ar súil a choinneáil ar dhá rud a choinneáil. Má tá tú a choinneáil súil a choinneáil ar an áit seo nód faoi láthair a chur isteach i. Caithfidh tú freisin súil a choinneáil ar an áit a choinneáil ar an nód roimhe go bhfuil tú ag féachaint ar Bhí freisin ann. Tá ag gach duine maith leis sin? OK. 

Cad é faoi chur isteach isteach sa deireadh? Má bhí mé a chur air here-- má bhí mé a chur ar nód nua go dtí deireadh an liosta, conas a d'fhéadfadh liom dul faoi á dhéanamh sin? LUCHT ÉISTEACHTA: Mar sin, i láthair na huaire, an ceann deireanach ar aird null. Andi Peng: Yeah. Go díreach, agus mar sin an ceann seo Tá Léirigh láthair go mbeadh a fhios, agus mar sin buille faoi thuairim mé, sa chiall seo, tá sé an-éasca a chur go dtí deireadh an liosta. Gach bhfuil tú a dhéanamh ná a leagtar sé cothrom le margadh saothair agus ansin borradh. Ceart ann, an-éasca. An-simplí. 

An-chosúil leis an ceann, ach go loighciúil tú iarraidh a dhéanamh cinnte go bhfuil na céimeanna ghlacann tú i dtreo a dhéanamh aon cheann de seo, bhfuil tú ag a leanas chomh maith. Tá sé an-éasca a, i lár de do chód, a bheith gafa suas ar, ó, tá fuair mé an oiread sin leideanna. Níl a fhios agam nuair Tá rud ar bith dírithe. Níl a fhios agam fiú a nód tá mé ar. Cad atá ar súil? 

Tóg go bog é, calma síos, a chur ar anáil domhain. Tarraing amach do liosta nasctha. Má deir tú, tá a fhios agam i gcás go díreach Is gá dom a chur isteach seo i agus tá a fhios agam go cruinn conas a athshannadh mo leideanna, i bhfad, i bhfad níos éasca chun pictiúr out-- bhfad, i bhfad níos éasca a ní caillte i an bugs de do chód. Tá ag gach duine ceart go leor leis sin? OK. 

Mar sin, buille faoi thuairim mé coincheap nach bhfuil muid i ndáiríre labhair faoi roimh anois, agus buille faoi thuairim mé tú is dócha Ní bheidh bhíonn yet-- bhfad tá sé de chineál ar concept-- cinn Is go bhfuil muid i ndáiríre sonraí Struchtúr a dtugtar liosta nasctha doubly. Mar sin, mar is féidir leat a fheiceáil guys, gach táimid ag déanamh is cruthú an luach iarbhír, breise pointeoir ar gach ceann dár nóid go pointí chomh maith leis an nód roimhe sin. Mar sin ní amháin go bhfuil ní mór dúinn ár pointe nóid dtí an ceann eile. Pointe siad freisin leis an gceann roimhe. Tá mé ag dul neamhshuim a dhéanamh dá ceart anois. 

Mar sin, ansin tá tú slabhra is féidir a bhogadh an dá bhealach, agus ansin tá sé le beagán níos éasca a leanúint go loighciúil chomh maith. Cosúil anseo, in ionad súil a choinneáil ar, ó, mé ní mór go mbeadh a fhios go bhfuil an nód an ceann a bhfuil mé a athshannadh, Is féidir liom dul díreach anseo agus ach tharraingt ar an roimhe sin. Ansin tá a fhios agam go díreach i gcás is é sin, agus ansin tú nach bhfuil a lean an iomláine an liosta nasctha. Tá sé rud beag níos éasca. 

Ach mar sin, tá tú doubly méid na leideanna, go dhá oiread an méid chuimhne. Tá sé a lán de leideanna súil a choinneáil. Tá sé rud beag níos casta, ach tá sé le beagán níos cairdiúla don úsáideoir ag brath ar an méid a bhíonn tú ag iarraidh a chur i gcrích. 

Mar sin, an cineál seo sonraí ann struchtúr go hiomlán, agus is é an struchtúr do an-, an- simplí amháin go léir tú ag a bhfuil, seachas díreach pointeoir go chugainn, caithfidh tú freisin pointeoir a roimhe sin. Sin a bhí go léir an difríocht. Tá ag gach duine maith leis sin? Cool. 

Ceart go leor, mar sin anois tá mé a chaitheamh i ndáiríre is dócha cosúil le 15 go 20 nóiméad nó an chuid is mó an chuid eile den am in alt ag caint faoi táblaí hash. Cé mhéad de tú guys léite spec pset5? Gach ceart, go maith. Sin níos airde ná an 50% de ghnáth. Tá sé ceart go leor. 

Mar sin, mar go mbeidh tú guys a fheiceáil, tá tú dúshlán i pset5 Beidh a chur i bhfeidhm foclóir áit a luchtú tú os cionn 140,000 focail go bhfaighidh tú, agus litriú a sheiceáil sé i gcoinne gach ceann de na téacs. Beidh muid a thabhairt duit randamach píosaí litríochta. Beidh muid a thabhairt duit ag an Odyssey. Beidh muid a thabhairt duit ag an Iliad. Beidh muid a thabhairt duit Cumhachtaí Austin. 

Agus do dúshlán Beidh seiceáil a litriú gach focal amháin i ngach de na foclóirí go bunúsach lenár litreoir. Agus mar sin níl a roinnt codanna a chruthú ar an pset, ar dtús ba mhaith leat a bheith in ann a luchtú iarbhír na focail go léir i do Foclóir, agus ansin tú ag iarraidh a bheith in ann litriú a sheiceáil ar fad iad. Agus mar sin, mar shampla, tá tú ag dul chun a cheangal struchtúr sonraí is féidir a é seo a dhéanamh go tapa agus go héifeachtach agus dinimiciúil. 

Mar sin, is dócha an éasca bhealach chun é seo a, tú Bheadh ​​a chruthú is dócha le sraith, ceart? Is é an bealach is éasca stórála tú Is féidir a chruthú le sraith de 140,000 focal agus díreach ar siúl iad go léir ann agus ansin lean iad ag cuardach dhénártha nó trí roghnúcháin nó not-- brón orm ar sin sórtáil. Is féidir leat iad a shórtáil agus ansin lean iad ag cuardach dénártha nó cuardach díreach líneach agus díreach deiridh na focail, ach go Bíonn méid ollmhór de chuimhne, agus nach bhfuil sé an-éifeachtach. 

Agus mar sin táimid ag dul chun tús a chur ag caint faoi na bealaí a dhéanamh ár gcuid ama ag rith níos éifeachtaí. Agus is é ár sprioc a fháil am tairiseach áit tá sé beagnach cosúil le arrays, i gcás ina tá rochtain mheandarach. Má bhí mé a chuardach le haghaidh rud ar bith, Ba mhaith liom a bheith in ann díreach, borradh, a aimsiú go díreach, agus é a tharraingt amach. Agus mar sin struchtúr ina bhfuil beidh orainn a bheith ag éirí an-dlúth a bheith in ann rochtain leanúnach am, an iomaíocht don duais mhór i gcláir de tairiseach Tá am dtugtar tábla hash. Agus mar sin a luadh cheana an David [Inaudible] le beagán i léacht, ach táimid ag dul chun i ndáiríre Léim i domhain an tseachtain seo ar phíosa go maidir conas a oibríonn tábla hash. 

Mar sin, an mbealach go hash oibreacha tábla, mar shampla, má bhí mé a stóráil a bunch de na focail, ar bunch de na focail sa Bhéarla, Raibh mé in ann a chur teoiriciúil banana, úll, kiwi, mango, péire, agus cantaloupe fad ar díreach le sraith. D'fhéadfaidís go léir oiriúnach i agus a bheith a fháil. Ba é a bheith de chineál ar pian a cuardach a dhéanamh trí agus rochtain, ach is é an bealach níos éasca é seo a dhéanamh gur féidir linn a chruthú i ndáiríre struchtúr ar a dtugtar tábla hash ina hash againn. Reáchtáil againn i ngach ceann dár eochracha trí feidhm hash, cothromóid, gur casadh iad go léir i éigin de luach go ansin is féidir linn a stóráil ar go bunúsach le sraith de liosta nasctha. 

Agus mar sin anseo, má bhíomar ag iarraidh a stóráil focail Béarla, d'fhéadfadh muid d'fhéadfadh a bheith díreach, ní féidir liom Tá a fhios, cas go léir an chéad litreacha i éigin de roinnt. Agus mar sin, mar shampla, má bhí mé A bheith shamhlaítear le apple-- nó leis an innéacs de 0, agus B a bheith shamhlaítear le 1, Is féidir linn a bheith 26 iontrálacha is féidir a stóráil go díreach gach ceann de na litreacha an aibítir go beidh orainn a tús a chur leis. Agus ansin is féidir linn a bheith úll ag an innéacs de 0. Is féidir linn a bheith banana ar an t-innéacs de 1, cantaloupe ag an t-innéacs de 2, agus mar sin de agus mar sin de. Agus dá bhrí sin má bhí mé chun cuardach a mo tábla agus rochtain úll hash, Tá a fhios agam úll thosaíonn le ar A, agus tá a fhios agam go díreach go gcaithfidh sé a bheith agus an hash tábla ag innéacs 0 gheall na feidhme a shanntar cheana. 

Mar sin níl a fhios agam, tá muid clár úsáideoir go mbainfidh tú a mhuirearú le arbitrarily-- ní treallach, leis ag iarraidh a thoughtfully smaoineamh ar cothromóidí maith a bheith in ann a scaipeadh amach gach ceann de do chuid luachanna ar bhealach gur féidir leo teacht go héasca níos déanaí le nós cothromóid go bhfuil tú, tú féin, tá a fhios. Mar sin, sa chiall má bhí mé chun dul go dtí mango, tá a fhios agam, ó, a thosaíonn sé le m. Caithfidh sé a bheith ar an t-innéacs de 12. Ní féidir liom a cuardach a dhéanamh trí rud ar bith. Tá a fhios agam exactly-- raibh mé in ann dul go díreach tar éis a an t-innéacs de 12 agus tarraingt go amach. 

Tá ag gach duine soiléir maidir leis an gcaoi a Oibríonn feidhm tábla hash ar? Tá sé de chineál díreach le sraith níos casta. Sin go léir a bhfuil sé. OK. 

Mar sin, buille faoi thuairim mé a reáchtáil muid isteach an gceist seo ar an méid a tharlaíonn má tá tú rudaí éagsúla go dtugann tú an t-innéacs céanna? Mar sin, a rá ár bhfeidhm, gach sé Rinne Ba ghlacadh go chéad litir agus cas go isteach i faoi ​​seach 0 trí 25 innéacs. Sin go hiomlán breá má tá tú ach ceann amháin de gach ceann acu. Ach an dara thosaíonn tú a bhfuil níos mó, tá tú ag dul go bhfuil cad atá ar a dtugtar imbhualadh. 

Mar sin, má tá tú iarracht mé a chur isteach bury isteach i hash tábla go bhfuil banana cheana féin ar sé, cad atá ar siúl a tharlóidh nuair a iarracht tú a chur isteach go? Rudaí dona mar gheall ar banana ann cheana laistigh den t-innéacs gur mian leat a stóráil i. Berry cineál cosúil, ah, cad is féidir liom a dhéanamh? Níl a fhios agam cá háit le dul. Conas is féidir liom a réiteach seo? 

Agus mar sin beidh tú guys chineál féach ar dhéanaimid an rud tricky áit ar féidir linn a de chineál ar i ndáiríre liosta nasctha inár arrays a chruthú. Agus mar sin an bealach is éasca chun smaoineamh faoi seo, Tá gach tábla hash ar sraith de liostaí nasctha. Agus mar sin, sa chiall sin, tá tú seo sraith álainn de leideanna, agus ansin gach pointeoir i an luach sin, sa mhéid is go innéacs, Is féidir le pointe iarbhír chun rudaí eile. Agus mar sin go bhfuil tú go léir na leithligh slabhraí teacht amach ar eagar ceann mór. 

Agus mar sin anseo, má tá mé Theastaigh sméar a chur isteach, Tá a fhios agam, ceart go leor, tá mé ag dul go dtí ionchur sé trí mo fheidhm hash. Tá mé ag dul go dtí deireadh suas leis an innéacs de 1, agus ansin mé ag dul a bheith in ann a bhfuil ach fo-thacar níos lú de seo fathach foclóir 140,000-focal. Agus ansin is féidir liom breathnú díreach trí 1/26 de sin. 

Agus mar sin ansin is féidir liom a chur isteach díreach sméar ceachtar roimh nó tar éis banana sa chás seo? Tar éis, ceart? Agus mar sin tá tú ag dul a iarraidh a cuir isteach an nód tar éis banana, agus mar sin tá tú ag dul a chur isteach ag an eireaball an liosta sin nasctha. Tá mé ag dul chun dul ar ais a ghabhann leis an sleamhnán roimhe seo, ionas gur féidir leat guys a fheiceáil conas Oibríonn feidhm hash. 

Mar sin, tá an fheidhm hash an chothromóid go bhfuil tú ag rith de chineál ar do ionchur trí a fháil is cuma cén innéacs ba mhaith leat a shannadh sé i dtreo. Agus mar sin, sa sampla seo, theastaigh go léir táimid ag a dhéanamh a bhí a chur ar an chéad litir, cas go isteach innéacs, ansin dúinn Is féidir a stóráil go inár fheidhm hash. Gach táimid ag déanamh anseo é go bhfuil muid athrú ar an chéad litir. Mar sin, keykey [0] Is é ach an chéad litir de cibé teaghrán táimid ag, táimid ag dul i. Táimid ag athrú go dtí uachtarach, agus táimid ag a dhealú ag chás uachtair A, mar sin go léir atá ag déanamh Tá a thabhairt dúinn a PO inar féidir linn ár gcuid luachanna hash isteach. 

Agus ansin táimid ag dul chun ar ais MÉID modulus hash. Bí an-, an-chúramach mar gheall ar, go teoiriciúil, anseo d'fhéadfadh do luach hash bheith gan teorainn. D'fhéadfadh sé dul díreach ar aghaidh agus ar aghaidh agus ar. D'fhéadfadh sé a bheith roinnt i ndáiríre, i ndáiríre luach mór, ach mar gheall ar do tábla hash go tú tar éis a cruthaíodh Tá 26 innéacsanna amháin, ba mhaith leat a dhéanamh cinnte go bhfuil do modulusing ionas go mbeidh tú Ní gá run-- tá sé mar an gcéanna rud mar do queue-- ionas nach bhfuil tú ag rith amach an bun do fheidhm hash. 

Ba mhaith leat a wrap ar ais timpeall ar an mbealach céanna i [inaudible] nuair bhí tú mar a bheadh ​​an-, litir an-mhór, tá tú Ní raibh ag iarraidh é sin le ach reáchtáil as an deireadh. Rud céanna anseo, ba mhaith leat a dhéanamh cinnte ní chuireann sé ar siúl as an deireadh ag timfhilleadh timpeall go dtí an barr an tábla. Mar sin, tá sé seo ach an- feidhm hash simplí. Gach go raibh raibh a chur ar an chéad Bhí litir cibé dár n-ionchur agus cas go isteach innéacs a D'fhéadfadh muid a chur isteach inár tábla hash. 

Yeah, agus mar sin mar a dúirt mé cheana, an bealach go bhfuil muid ag imbhuailtí réiteach inár hash táblaí ag a bhfuil, rud ar a dtugaimid, shlabhrú. Mar sin, má tá tú iarracht a chur isteach iolrach focail a tús a chur leis an rud céanna, tú ag dul a bheith acu luach hash amháin. Avocados agus úll, má tá tú rith sé tríd ár fheidhm hash, ag dul a thabhairt duit ar an líon céanna, tá líon na 0. Agus mar sin an bealach linn a réiteach go bhfuil gur féidir againn i ndáiríre de chineál ar a nascadh iad le chéile trí liostaí nasctha. 

Agus mar sin sa chiall seo, is féidir leat a fheiceáil de chineál guys ar conas struchtúir sonraí a tá muid ag leagan síos roimhe cosúil le raisin nasctha liosta de chineál Is féidir teacht ar chéile i amháin. Agus ansin is féidir leat a chruthú i bhfad struchtúir sonraí níos éifeachtaí gur féidir déileáil méideanna níos mó de sonraí, go dinimiciúil Athraigh brath ar do chuid riachtanas. Tá ag gach duine soiléir? Tá ag gach duine de chineál soiléir ar cad a tharlaíonn anseo? 

Má bhí mé a insert-- cad atá ar torthaí a thosaíonn le, níl a fhios agam, B, seachas caora, banana. 

LUCHT ÉISTEACHTA: Blackberry. 

Andi Peng: Blackberry, sméar dubh. I gcás nach sméar dubh go here? Bhuel, ní mór dúinn a curtha in eagar i ndáiríre seo go fóill, ach teoiriciúil má bhíomar ag iarraidh a bheith acu seo in ord aibítre, áit ar cheart sméar dubh dul? 

LUCHT ÉISTEACHTA: [inaudible] 

Andi Peng: Go díreach, tar éis anseo, ceart? Ach ós rud é tá sé an-deacair a reorder-- Buille faoi thuairim mé tá sé suas chun tú guys. Is féidir guys tú go hiomlán a chur i bhfeidhm is cuma cad ba mhaith leat. An bealach níos éifeachtaí seo a dhéanamh b'fhéidir bheadh ​​a shórtáil do nasctha liosta i ord aibítre, agus mar sin nuair a bhíonn tú rudaí a chur isteach, ba mhaith leat a bheith cinnte a chur isteach orthu i ord aibítre ionas go mbeidh ansin nuair a bhíonn tú ag iarraidh a chuardach dóibh, ní gá duit gach rud a Traverse. Tá a fhios agat go díreach nuair bhfuil sé, agus tá sé níos éasca. 

Ach má tá tú de chineál ar go bhfuil rudaí a interspersed randamach, tú ag dul go fóill go bhfuil a lean sé anyways. Agus mar sin má bhí mé go dtí díreach cuir isteach sméar dubh anseo agus theastaigh uaim chun cuardach a dhéanamh sé, tá a fhios agam, ó, sméar dubh Ní mór tús a chur leis an innéacs de 1, mar sin mé Tá a fhios instantaneously ach cuardaigh ar 1 pm. Agus ansin is féidir liom de chineál ar Traverse an liosta nasctha go dtí go rachaidh mé chun sméar dubh, agus then-- yera yeah? 

LUCHT ÉISTEACHTA: Má tá tú ag iarraidh a create-- Buille faoi thuairim mé mar tá sé seo le hash-simplí fheidhm. Agus má bhíomar ag iarraidh a dhéanamh ciseal amháin d'sin cosúil le, OK, ba mhaith linn a scaradh isteach cosúil le gach na litreacha aibítre agus ansin arís go maith liom sraith eile litreacha aibítre laistigh, tá muid ag cur nós hash tábla laistigh tábla hash, nó mar a bheadh ​​feidhm laistigh feidhm? Nó an bhfuil that-- 

Andi Peng: Mar sin, do hash function-- do tábla hash Is féidir a bheith chomh mór agus is mian leat é a. Mar sin, sa chiall seo, shíl mé bhí sé an-éasca, an- simplí dom a bunaithe go díreach saghas ar litreacha an chéad fhocal. Agus mar sin níl ach 26 roghanna. Is féidir liom a fháil ach 26 roghanna ó 0-25 mar is féidir leo ach tús ó A go Z. Ach Má bhí tú a chur leis, b'fhéidir, castacht níos mó nó níos tapúla a reáchtáil am chun do tábla hash, tú go hiomlán is féidir a dhéanamh gach cineál rudaí. Is féidir leat a dhéanamh do chuid féin chothromóid a thugann tú dáileadh níos mó i do focail, ansin nuair a chuardaíonn tú, sé ag dul a bheith níos tapúla. 

Tá sé go hiomlán suas chun tú guys conas ba mhaith leat a chur i bhfeidhm go. Cuimhnigh ar sé mar ach buicéid. Má bhí mé a bheith acu 26 buicéid, tá mé ag dul chun rudaí a isteach na buicéid shórtáil. Ach tá mé ag dul go bhfuil a bunch de rudaí i ngach buicéad, mar sin más mian leat a dhéanamh níos tapúla agus níos éifeachtaí, in iúl dom céad buicéid. 

Ach ansin caithfidh tú a figiúr amach bhealach chun rudaí a shórtáil ionas go mbeidh siad i an buicéad cuí ba chóir iad a bheith i. Ach ansin nuair a dhéanann tú i ndáiríre ag iarraidh chun breathnú ar sin buicéad, tá sé a lán níos tapúla mar níl stuif níos lú i ngach buicéad. Agus mar sin, yeah, go hiarbhír an cleas ar do shon guys i pset5 is é sin beidh tú dúshlán a chruthú go díreach is cuma cad é an is éifeachtaí fheidhm is féidir leat smaoineamh ar a bheith in ann a stóráil agus a sheiceáil na luachanna. 

Totally suas chun tú guys áfach, ba mhaith leat é a dhéanamh, ach is é sin go pointe gur maith. Go ndéanfar an cineál loighic tú ag iarraidh a smaoineamh ar is é, go maith, cén fáth nach féidir liom a dhéanamh níos mó buicéid. Agus ansin caithfidh mé a chuardach rudaí níos lú, agus ansin b'fhéidir mé go mbeadh feidhm hash éagsúla. 

Yeah, níl a lán bealaí chun é seo a pset, tá roinnt níos tapúla ná daoine eile. Tá mé ag dul go hiomlán a fheiceáil ach conas Ba an tapúla tú guys go tapa go mbeidh a bheith in ann a fháil do fheidhmeanna a bheith ag obair. OK, gach duine maith ar shlabhrú agus hash táblaí? Tá sé i ndáiríre mar a bheadh ​​an-simplí coincheap má cheapann tú faoi. Léir go bhfuil sé go bhfuil scaradh cuma cad bhfuil do ionchur i buicéid, sórtáil leo, agus ansin cuardach ar an liostaí go bhfuil a bhaineann le. 

Cool. Ceart go leor, anois ní mór dúinn a saghas difriúil de struchtúr sonraí go dtugtar crann. A ligean ar dul ar aghaidh agus labhairt faoi iarracht atá distinctly difriúil, ach sa chatagóir céanna. Go bunúsach, tá gach crann ina ionad na sonraí a eagrú ar an mbealach líneach go tábla hash does-- tú fhios, tá sé fuair a barr agus bun agus ansin tú de chineál ar nasc uaire de it-- a Tá crann barr a ghlaonn tú ar an fhréamh, agus ansin tá sé duilleoga ar fad timpeall air. 

Agus mar sin go léir a bhfuil tú anseo ach an nód barr go pointí le nóid eile, go pointí le nóid níos mó, agus mar sin de agus mar sin de. Agus mar sin tá tú díreach brainsí scoilteadh. Tá sé díreach ar bhealach difriúil a eagrú sonraí, agus mar gheall ar tugaimid crann, tú guys just-- tá sé ach bunaithe ar mhúnla amach chun breathnú cosúil le crann. Sin an fáth a tugaimid crainn. 

Breathnaíonn an tábla Hash cosúil le tábla. Breathnaíonn A crann díreach cosúil le crann. Léir go bhfuil sé go bhfuil ar leithligh mhodh nóid eagrú ag brath ar cad iad do riachtanais. 

Mar sin, tá tú fréimhe agus ansin caithfidh tú duilleoga. An bealach gur féidir linn go háirithe smaoineamh go bhfuil sé ar chrann dhénártha, Is crann dhénártha ach cineál sonrach crann i gcás gach nód pointí ach amháin chun, ag max, dhá nóid eile. Agus mar sin anseo tá tú ar leith siméadrachta i do chrann go ndéanann sé níos éasca a de chineál ar breathnú ar an méid a luachanna a bhfuil tú mar gheall ar ansin tú bhfuil ar chlé nó ceart i gcónaí. Níl ní cosúil an tríú clé ó an taobh clé nó ceathrú as na láimhe clé. Tá sé díreach tá tú ar chlé agus ar ceart agus is féidir leat cuardach ceachtar den dá. Agus mar sin an fáth go bhfuil sé seo úsáideach? An bealach go bhfuil sé seo Is úsáideach má tá tú ag lorg chun cuardach trí luachanna, ceart? In áit a bheith a chur chun feidhme dénártha cuardach a dhéanamh i sraith earráid, má raibh tú a bheith in ann a chur isteach nóid agus a chur amach nóid ag toil agus freisin an cuardach a chaomhnú cumais cuardaigh dénártha. Mar sin, ar an mbealach seo, tá muid de chineál ar tricking-- cuimhneamh nuair a muid a dúirt nach féidir le liostaí nasctha cuardaigh dénártha? Táimid ag de chineál ar a chruthú struchtúr sonraí go cleasanna go isteach ag obair. 

Agus tá liostaí sin mar gheall ar nasctha líneach, nasc siad ach i ndiaidh a chéile. Is féidir linn a de chineál ar go bhfuil saghas difriúil leideanna go pointe chun nóid éagsúla gur féidir cabhrú linn le cuardach. Agus mar sin anseo, má bhí mé a tá crann cuardaigh dénártha, Tá a fhios agam go bhfuil mo lár más rud é 55. Tá mé ag dul díreach tar éis a chruthú go mar mo lár, mar mo fhréamh, agus ansin tá mé ag dul a bheith acu Luachanna casadh uaire de. 

Mar sin anseo, má tá mé ag dul chun cuardach a an luach de 66, is féidir liom tosú ag 55. Tá sé 66 níos mó ná 55? Tá go bhfuil sé, mar sin tá a fhios agam mus agam cuardaigh i n an pointeoir ceart an crann. Téim go dtí 77. OK, 66 níos lú ná nó níos mó ná 77? Tá sé níos lú ná, mar sin a fhios agat, ó, go bhfuil a bheith ar an nód chlé. 

Agus mar sin anseo tá muid de chineál ar chaomhnú gach ceann de na rudaí is fearr faoi arrays, mar sin cosúil méid a athrú dinimiciúil de rudaí, a bheith in ann a chur isteach agus a scriosadh ag a bheidh, gan a bheith buartha faoi na seasta méid spáis. Táimid ag a chaomhnú fós gach ceann de na na rudaí iontacha cé chomh bheith in ann a chaomhnú an logáil agus am cuardaigh dénártha cuardaigh go raibh muid ach roimhe in ann a fháil ar frása. 

Struchtúr sonraí Cool, de chineál ar casta a chur i bhfeidhm, an nód. Mar is féidir leat a fheiceáil, go léir sé Is é an struct an nód Is go tá tú ar chlé agus pointeoir ceart. Sin go léir a bhfuil sé. Mar sin, seachas díreach a bhfuil x nó roimhe sin. Tá tú ar chlé nó ceart, agus ansin Is féidir leat de chineál ar iad a nascadh le chéile áfach, a roghnaíonn tú mar sin. 

OK, táimid ag dul i ndáiríre a ghlacadh ach cúpla nóiméad. Mar sin, táimid ag dul chun dul ar ais anseo. Mar a dúirt mé cheana, Cineál I mhínigh an loighic taobh thiar conas a Bheadh ​​cuardaigh tríd an. Táimid ag dul chun iarracht a dhéanamh pseudocoding seo amach a fheiceáil más féidir linn cineál feidhm ag na loighic céanna cuardaigh dénártha le cineál éagsúla de struchtúr sonraí. Más mian leat guys a ghlacadh cosúil le lánúin nóiméad chun smaoineamh ar díreach faoi seo. OK. Ceart go leor, tá mé ag dul go dtí i ndáiríre a thabhairt ach tú the-- bith, beidh muid ag labhairt faoi an pseudocode ar dtús. Mar sin, duine ar bith a iarraidh dhéanann a thabhairt ar an stab ar an méid an chéad rud is mian leat a dhéanamh nuair a bhfuil tú ag tosú amach cuardach? Má tá muid ag lorg an luach de 66, cad atá an chéad rud ba mhaith linn a dhéanamh má ba mhaith linn a dénártha cuardaigh an crann? 

LUCHT ÉISTEACHTA: Ba mhaith leat chun breathnú ar dheis agus táim ag ar chlé agus a fheiceáil [inaudible] líon níos mó. 

Andi Peng: Yeah, go díreach. Mar sin, tá tú ag dul chun breathnú ar do root. Níl go leor de na bealaí is féidir leat glaoch sé, a rá do dhaoine nód tuismitheoir. Is maith liom fhréamh a rá mar gheall ar go cosúil leis an fhréamh an chrainn. Tá tú ag dul chun breathnú ar do nód fréimhe, agus an bhfuil tú ag dul a fheiceáil go bhfuil 66 níos mó ná nó níos lú ná 55. Agus má tá sé níos mó ná, go maith, tá sé níos mó ná, i gcás ina bhfuil mhaith linn chun breathnú? Cá háit ar mian linn a chuardach anois, ceart? Is mian linn a chuardach leath ceart an crann. 

Mar sin, ní mór dúinn, conveniently, a pointeoir go pointí do cheart. Agus mar sin ansin is féidir linn a leagtar ár fhréamh nua a bheith 77. Is féidir linn dul go dtí cibé áit go díreach Tá an pointeoir dírithe. Bhuel, ó, anseo táimid ag tosú ag 77, agus is féidir linn ach é seo a hathchúrsach arís agus arís. Ar an mbealach seo, tá tú de chineál ar de go bhfuil feidhm. Tá tú ar bhealach a chuardach go bhfuil tú Is féidir arís díreach os cionn agus os a chionn agus os a chionn, brath ar an áit is mian leat chun breathnú go dtí go tú a fháil sa deireadh leis an luach go bhfuil tú ag cuardach do. Ciall? 

Tá mé ar tí é a thaispeáint duit an iarbhír cód, agus tá sé a lán de chód. Níl gá a anchúinse amach. Beidh muid ag labhairt tríd. 

I ndáiríre, uimh. Ba é sin ach pseudocode. OK, go raibh ach an pseudocode, a bhfuil casta beagán, ach tá sé go hiomlán fíneáil. Tá ag gach duine a leanas chomh maith anseo? Má tá an fhréamh null, ar ais bréagach mar gheall ar sin ciallaíonn Ní gá duit fiú rud ar bith ann. 

Má tá fréimhe n an luach, mar sin má tá sé tharlaíonn a bheith ar an duine go bhfuil tú ag féachaint ar, ansin tá tú ag dul a thabhairt ar ais fíor mar a fhios agat fuair tú é. Ach má tá an luach níos lú ná fhréamh n, tá tú dul chun cuardach ar an taobh clé leanbh nó an duilleog ar chlé, bith is mian leat a ghlaoch air. Agus má tá an luach níos mó ná fréimhe, tú ag dul a chuardach ar an crann ceart, ansin reáchtáil díreach an fheidhm trí chuardach a dhéanamh arís. 

Agus má tá fréimhe null, go go ciallaíonn atá tú bainte amach an deireadh? Ciallaíonn tá tú aon níos mó duilleoga níos mó chun cuardach, ansin a fhios agat, ó, mé buille faoi thuairim nach bhfuil sé i anseo mar gheall ar tar éis tá mé d'fhéach sé trí an rud ar fad agus nach bhfuil sé anseo, Ní fhéadfadh sé a bheith díreach anseo. 

An bhfuil a dhéanamh le gach duine ciall? Mar sin, tá sé cosúil le cuardaigh dhénártha chaomhnú na cumais liostaí nasctha. Cool, agus mar sin an dara cineál de shonraí struchtúr tú guys Is féidir iarracht a chur i bhfeidhm ar do pset, tá tú ach a roghnú modh amháin. Ach b'fhéidir modh malartach chun Is é an tábla hash cad tugaimid Trie. 

Tá gach a Trie is cineál sonrach crann a Tá na luachanna a théann chun luachanna eile. Mar sin, in ionad a bheith ar dénártha crann sa chiall go bhfuil ach amháin Is féidir le rud pointe go dtí dhá, is féidir leat a bheith pointe rud amháin go leor, a lán rudaí. Tá tú go bunúsach arrays taobh istigh a stóráil tú leideanna a pointe ar arrays eile. 

Mar sin, an nód ar conas linn a Bheadh ​​shainiú Trie Is ba mhaith linn a bheith acu Boole, c focal, ceart? Mar sin, leis an nód Boole cosúil le fíor nó bréagach, an gcéad de gach ag ceann is é sin eagar, an focal? Dara dul síos, ba mhaith leat a bheith acu leideanna cibé atá an chuid eile acu. A casta beagán, le teibí beagán, ach Beidh mé ag míniú cad a gach uile bhealach. 

Mar sin anseo, ag an mbarr, má tá tú tá sraith dearbhaithe cheana, nód áit a bhfuil tú a Boole luach a stóráil ag an tosaigh a insíonn is tú an focal? An é seo nach bhfuil focal? Agus ansin tá tú ar an chuid eile de do eagar go Siopaí i ndáiríre go léir an féidearthachtaí cad a d'fhéadfadh sé a bheith. Mar sin, mar shampla, cosúil le ag an mbarr a bhfuil tú an chéad rud a deir fíor nó bréagach, yes nó gan aon, tá sé seo le focal. 

Agus ansin caithfidh tú 0 trí 26 de na litreacha gur féidir leat a stóráil. Má bhí mé a chuardach anseo do bat, Téim go dtí an barr agus Táim ag do B. bhfaighidh mé B i mo eagar, agus mar sin tá a fhios agam, OK, B focal? Ní B focal, mar sin dá bhrí sin Caithfidh mé a choinneáil a chuardach. Téim ó B, agus táim mé go dtí an pointeoir go pointí B i dtreo agus féach mé sraith eile de eolais, an struchtúr céanna a bhí againn roimhe seo. 

Agus here-- ó, an chéad cheann eile Tá litir i [inaudible] A. Mar sin, táimid sa eagar. Teacht againn ar an luach ochtú, agus ansin táimid a fheiceáil, ó, hug, is é sin focal, is é B-A focal? Nach bhfuil sé ina focal. Táimid tar éis a fuair a choinneáil ag lorg. 

Agus mar sin ansin táimid go dtí an áit an pointeoir ar A pointí, agus pointí sé le ar bhealach eile i a bhfuil againn luach níos mó a stóráil. Agus ar deireadh thiar, a fháil againn chun B-A-T, a bhfuil focal. Agus mar sin an chéad uair eile fhéachann tú, tá tú ag dul go ndéanfaí an seic de, yes, tá sé seo an fheidhm Boole fíor. Agus mar sin sa chiall táimid de chineál ar a bhfuil crann le arrays. 

Mar sin, ansin is féidir leat cuardach a dhéanamh de chineál ar síos. In áit a bheith hashing feidhm agus luachanna a shannadh de réir an liosta nasctha, is féidir leat a chur i bhfeidhm ach Trie a chuardaíonn downwords. Really, i ndáiríre casta stuif. Níl sé éasca chun smaoineamh ar mar go bhfuil mé cosúil le spitting an oiread sin struchtúir sonraí amach ag tú, ach a dhéanann gach duine de chineál ar tuiscint a fháil ar conas a oibríonn an loighic seo? 

OK, cool. Mar sin, B-A-T, agus ansin tú ag dul a chuardach. An chéad uair eile tú ag dul a fheiceáil, ó, hug, tá sé fíor, dá bhrí sin tá a fhios agam ní mór é seo a bheith ina focal. 

Rud céanna le haghaidh zú. Mar sin, tá anseo an rud ceart anois, má táimid ag iarraidh a chuardach le haghaidh zú, ceart anois, faoi ​​láthair nach bhfuil zú a focal i ár foclóir toisc, mar is féidir leat a fheiceáil guys, an chéad áit gur féidir linn an Boole Is ar ais fíor ag deireadh an súmáil. Ní mór dúinn Z-O-O-M. 

Agus mar sin anseo, nach bhfuil againn i ndáiríre an focal, zú, i ár foclóir toisc nach bhfuil an ticbhosca sheiceáil. Mar sin, ní dhéanann an ríomhaire Tá a fhios go bhfuil zú focal mar gheall ar an mbealach go bhfuil muid stóráil sé, ach súmáil anseo i ndáiríre tá luach Boole go atá iompaithe fíor. Mar sin, más mian linn a chur isteach ar an focal, zú, isteach inár foclóir, conas ba mhaith linn dul faoi sin a dhéanamh? Cad a dhéanann mór dúinn a dhéanamh chun a chinntiú ár n- fhios ag ríomhaire go Z-O-O focal agus nach bhfuil an chéad fhocal Z-O-O-M? 

LUCHT ÉISTEACHTA: [inaudible] 

Andi Peng: Go díreach, ní mór dúinn iarraidh a dhéanamh cinnte go bhfuil an anseo, is é sin luach Boole Sheiceáil amach go bhfuil sé fíor. Z-O-O, ansin táimid ag dul a sheiceáil go bhfuil, sin a fhios againn go díreach, hug, tá zú focal. Tá mé ag dul a rá leis an ríomhaire a tá sé ina focal sin go nuair na seiceálacha ríomhaire, fhios sé go bhfuil zú focal. 

Mar gheall ar cuimhnigh ar na sonraí go léir struchtúir, tá sé an-éasca dúinn a rá, OH, tá bat focal. Zú tá focal. Zoom Tá focal. Ach nuair a bhíonn tú ag tógáil air, Tá an ríomhaire aon smaoineamh. 

Mar sin, caithfidh tú a insint sé go díreach an méid atá pointe tá sé seo le focal? An méid atá pointe nach bhfuil sé focal? Agus an méid atá pointe is féidir liom Ní mór chun rudaí a chuardach, agus an méid atá pointe is gá dom a An chéad chéim eile Tá ag gach duine soiléir ar sin? Cool. 

Agus mar sin ansin a thagann an fhadhb ar conas ba mhaith linn dul faoi chur isteach rud éigin go i ndáiríre ní ann? Mar sin, a ligean le rá ach ba mhaith linn a chur isteach an focal, folctha, isteach inár Trie. Mar is féidir leat guys a fheiceáil cosúil le láthair gach ní mór dúinn anois gurb é B-A-T, agus an struchtúr sonraí nua go raibh pionta go Luaigh null gheall glacaimid go, ó, níl aon focal i ndiaidh B-A-T, cén fáth nach gá dúinn a choinneáil a bhfuil rudaí tar éis an T. 

Ach éiríonn an fhadhb má dhéanann tusa ag iarraidh a bheith acu focal a thagann i ndiaidh an T s. Má tá tú folctha, tá tú ag dul a iarraidh ceart H. Agus mar sin is é an bealach táimid ag dul chun é sin a táimid ag dul a chruthú nód ar leith. Nach bhfuil muid ag allot is cuma cén méid de chuimhne ar an eagar nua, agus táimid ag dul a leideanna a athshannadh. 

Táimid ag dul a shannadh ar an H, Gcéad dul síos, an null, táimid ag dul chun fáil réidh. Táimid ag dul a bheith acu na anuas pointe H. Má fheiceann muid ar H, ba mhaith linn é chun dul go dtí áit éigin eile. 

I anseo, is féidir linn a sheiceáil ansin amach yes. Má bhuaileann muid H i ndiaidh an T, ó, ansin a fhios againn go bhfuil sé seo le focal. An Boole ag dul a thabhairt ar ais fíor. Tá ag gach duine soiléir ar an gcaoi a tharla? OK. 

Mar sin go bunúsach, gach ceann de na struchtúir sonraí go atá againn imithe thar lá atá inniu ann, tá mé imithe os a gcionn i ndáiríre, i ndáiríre go tapa agus ní i bhfad mion, agus sin ceart go leor. Chomh luath agus a thosaíonn tú ag messing leis é, beidh tú a bheith súil a choinneáil ar an áit tá gach na leideanna, cad atá ar siúl i do struchtúir sonraí, et cetera. Beidh siad a bheith an-úsáideach, agus tá sé suas chun tú guys chun an figiúr amach conas go hiomlán ba mhaith leat chun rudaí a chur i bhfeidhm. 

Agus mar sin pset4, de 5-- OH, is é sin mícheart. Is Pset5 misspellings. Mar a dúirt mé cheana, tá tú ag dul chun, aon uair amháin arís, a íoslódáil cód foinse ó dúinn. Tá ag dul a bheith trí phríomh rudaí a mbainfidh tú a bheith a íoslódáil. Feicfidh tú foclóirí a íoslódáil, Kers, agus téacsanna. 

Tá gach na rudaí atá ceachtar de na focail foclóirí go ba mhaith linn tú a sheiceáil nó tástáil na faisnéise go ba mhaith linn tú seic a litriú. Agus mar sin na foclóirí a thabhairt duit ag dul a thabhairt duit focail iarbhír a ba mhaith linn leat a stóráil ar bhealach ar bhealach go bhfuil níos éifeachtaí ná eagar. Agus ansin tá na téacsanna ag dul a bheith cad tá muid ag iarraidh ort a litriú a sheiceáil chun a chinntiú gach ceann de na focail tá focail fíor. 

Agus mar sin na trí bloic de cláir a beidh orainn a thabhairt duit Tugtar dictionary.c, dictionary.h, agus speller.c. Agus mar sin ní gach dictionary.c é cad tá tú ag iarradh a chur i bhfeidhm. Ualaí a eascraíonn sé focail. Sé litriú seiceálacha iad, agus déanann sé cinnte go go bhfuil gach rud a cuireadh isteach i gceart. 

Is diction.h ach comhad leabharlainne go ndearbhaíonn na feidhmeanna sin go léir. Agus speller.c, táimid ag dul a thabhairt duit. Ní gá duit a mhodhnú ar bith de sé. Dhéanann gach speller.c é a ghlacadh go, ualaí sé seiceálacha, an luas de, tástálacha an tagarmharc na cosúil le conas tapa tá tú in ann chun rudaí a dhéanamh. 

Tá sé ina speller. Just a nach bhfuil praiseach leis, ach a dhéanamh cinnte go dtuigeann tú cad atá á dhéanamh. Bainimid úsáid as feidhm ar a dtugtar getrusage go tástálacha ar fheidhmíocht do litriú seiceálaí. Gach a dhéanann sé é a thástáil go bunúsach ar an am de gach rud i do bhfoclóir, mar sin déan cinnte go dtuigeann tú é. Bí cúramach praiseach a ní leis nó Ní bheidh rudaí eile rith mar is cuí. 

Agus is é an chuid is mó den dúshlán seo le haghaidh tú guys a mhodhnú i ndáiríre dictionary.c. Táimid ag dul a thabhairt duit 140,000 focal i bhfoclóir. Táimid ag dul a thabhairt duit téacs comhad go bhfuil na focail sin, agus ba mhaith linn duit a bheith in ann a eagrú iad i dtábla hash nó Trie mar nuair a iarraimid ort a litriú check-- shamhlú má tá tú seal seiceáil cosúil Odaisé le Hóiméar. Tá sé mar seo ollmhór, tástáil ollmhór. 

Samhlaigh más rud é gach aon focal a bhí tú chun breathnú trí sraith de 140,000 luachanna. Bheadh ​​sin a ghlacadh go deo as do mheaisín a rith. Sin é an fáth ba mhaith linn a eagrú ar ár sonraí i struchtúir sonraí níos éifeachtaí mar shampla tábla hash nó Trie. Agus ansin is féidir leat guys chineál de nuair a chuardaíonn tú rochtain rudaí níos éasca agus níos tapúla. 

Agus mar sin a bheith cúramach chun imbhuailtí a réiteach. Tú ag dul a fháil ar a bunch de na focail sin tús le A. Tú ag dul a fháil ar a bunch focail go tús a chur le B. Go dtí tú guys conas ba mhaith leat a réiteach é. B'fhéidir níl níos mó fheidhm hash éifeachtach ná díreach an chéad litir de rud éigin, agus mar sin tá go bhfuil suas le leat guys a de chineál ar cibé rud is mian leat. 

B'fhéidir gur mhaith leat a chur na litreacha le chéile. B'fhéidir gur mhaith leat chun mhaith a dhéanamh rudaí aisteach cuntas a dhéanamh ar líon na litreacha, cibé. Suas chun tú guys conas ba mhaith leat a dhéanamh. Más mian leat a dhéanamh tábla hash, má tá tú ba mhaith chun iarracht a Trie, go hiomlán suas chun tú. Beidh mé rabhadh duit roimh an am go bhfuil an Is Trie de ghnáth le beagán níos deacra díreach toisc níl a lán níos mó leideanna súil a choinneáil. Ach go hiomlán suas chun tú guys. Tá sé i bhfad níos éifeachtaí i bhformhór na gcásanna. Ba mhaith leat a bheith i ndáiríre in ann a choimeád súil a choinneáil ar gach ceann de do threo. Mar a dhéanann an rud céanna go raibh mé ag déanamh anseo. Nuair a bheidh tú ag iarraidh a chur isteach luachanna isteach i dtábla hash nó a scriosadh, déan cinnte go bhfuil tú i ndáiríre súil a choinneáil de ina bhfuil gach rud mar gheall ar tá sé i ndáiríre éasca do má tá mé ag iarraidh a chur isteach cosúil leis an focal, Andy. Ligean le rá ach go bhfuil focal fíor, an focal, Andy, i liosta ollmhór de A focail. 

Má tharlaíonn mé díreach tar éis a athshannadh a mícheart pointeoir, Oops, tá téann an iomlán an chuid eile de mo liosta nasctha. Anois an focal amháin agam tá Is andy, agus anois gach ceann de na focail eile sa Foclóir bheith caillte. Agus mar sin ba mhaith leat a dhéanamh cinnte go bhfuil tú súil a choinneáil ar gach ceann de do threo a choinneáil nó eile go bhfuil tú ag dul a fháil fadhbanna ollmhóra i do cód. Rudaí a tharraingt amach go cúramach céim ar chéim. A dhéanann sé sé i bhfad níos éasca chun smaoineamh ar. 

Agus ar deireadh, ba mhaith leat a bheith in ann tástáil do fheidhmíocht do chláir ar an mbord mór. Má ghlacann tú guys a féachaint ar CS50 ceart anois, ní mór dúinn cad atá ar a dtugtar an mbord mór. Tá sé an leathán scór de na tapúla litriú amanna seiceáil ar fud na CS50 ceart anois, Sílim go bhfuil an barr cosúil le 10 amanna is dóigh liom go bhfuil ochtar acu foirne. Ba mhaith linn i ndáiríre tú guys chun buille dúinn. 

Gach duine againn a bhí ag iarraidh a chur i bhfeidhm an cód tapúla is féidir. Ba mhaith linn tú guys chun iarracht chun dúshlán linn agus a chur i bhfeidhm níos tapúla ná gach duine againn Is féidir. Agus mar sin tá sé seo i ndáiríre an chéad uair a bhfuil muid iarraidh ort guys a dhéanamh pset sin Is féidir leat a dhéanamh i ndáiríre is cuma cén modh i ba mhaith leat. 

Rá liom i gcónaí, tá sé seo níos cosúla chun réiteach fíor-saoil, ceart? Rá liom, hug, is gá dom duit é seo a dhéanamh. Tóg clár a mbaineann sé seo dom. An bhfuil sé, áfach, is mian leat. Tá a fhios agam ach gur mhaith liom go tapa. Sin do dúshlán don tseachtain seo. Tú guys, táimid ag dul a thabhairt duit tasc. Táimid ag dul a thabhairt duit dúshlán. Agus ansin tá sé suas chun tú guys chun go hiomlán figiúr díreach amach cad é an tapúla agus is bhealach éifeachtach a chur i bhfeidhm seo. Yeah? 

LUCHT ÉISTEACHTA: An bhfuil muid cead má theastaigh chun taighde a bhealaí níos tapúla a dhéanamh ar táblaí hash ar líne, is féidir linn a dhéanamh go agus cite duine eile cód? Andi Peng: Yeah, go hiomlán fíneáil. Mar sin, má léann tú guys an spec, níl líne sa spec a deir tú guys Tá hiomlán saor in aisce hash chun taighde feidhmeanna ar cad iad roinnt de na feidhmeanna hash níos tapúla chun rudaí a reáchtáil trí mheán mar fada agus luann tú go cód. Mar sin, tá roinnt daoine cheana figured amach ar bhealaí go tapa dhéanamh seiceálaithe litrithe, de tapa bealaí faisnéise a stóráil. Totally suas chun tú guys má tá tú ag iarraidh a chur go díreach, ceart? Bí cinnte go bhfuil tú ag lua. Is é an dúshlán i ndáiríre anseo go bhfuil muid ag iarraidh a thástáil Tá ag déanamh cinnte go bhfuil a fhios agat do bhealach a dhéanamh timpeall threo. Chomh fada agus is a chur i bhfeidhm agat an fheidhm hash iarbhír agus teacht suas le nós an mata a dhéanamh sin, Is féidir leat guys taighde is cuma cad Modhanna líne Ba mhaith leat guys. Yeah? 

LUCHT ÉISTEACHTA: An féidir linn a lua díreach ag baint úsáide as an [inaudible]? 

Andi Peng: Yeah. Is féidir leat ach, i do chuid tuairimí, is féidir leat a cite cosúil le, ó, tógtha ó Yada, yada, yada, feidhm hash. Duine ar bith tá aon cheist? Thairis sin táimid i ndáiríre trí alt inniu. Beidh mé a bheith suas anseo ceisteanna a fhreagairt chomh maith. 

Chomh maith leis sin, mar a dúirt mé, oifig uaireanta anocht agus amárach. An spec is an tseachtain seo i ndáiríre Super éasca agus Super gearr a léamh. Ba mhaith liom fios ag cur le breathnú, ach léigh tríd an iomláine de. 

Agus siúlóidí Zamyla iarbhír tú trí gach ceann de na feidhmeanna is gá duit a chur i bhfeidhm, agus mar sin tá sé an-, an-soiléir conas gach rud a dhéanamh. Ach chun a chinntiú go bhfuil tú ar súil a choinneáil ar leideanna. Is é seo an pset an-dúshlánach. 

Níl sé dúshlánach mar gheall ar cosúil le, OH, is iad na coincheapa sin i bhfad níos mó deacair, nó a bhfuil tú ag foghlaim an oiread sin error nua ar an mbealach go ndearna tú don pset seo caite. Tá an pset deacair toisc tá an oiread sin leideanna, agus ansin tá sé an-, an-éasca a thabhairt tar tá tú fabht i do chód a bheith in ann a fháil i gcás ina bhfuil fabht. 

Agus mar sin a chomhlánú agus creideamh utter i tú guys a bheith in ann buille ar ár [inaudible] litriú. Tá mé i ndáiríre ní aon mhianach i scríbhinn go fóill, ach tá mé ar tí é mianach a scríobh. Mar sin, fad a bhíonn tú ag scríobh mise, beidh mé ag scríobh mianach. Tá mé ag dul chun iarracht a dhéanamh mianach tapúla ná mise. Beidh orainn a fheiceáil a bhfuil an ceann is tapúla. 

Agus yeah, beidh mé a fheiceáil gach ceann de na tú guys anseo ar an Máirt. Beidh mé a reáchtáil ar chineál nós ceardlann pset. Gach ceann de na hailt seo a Tá seachtain ceardlanna pset, ionas go mbeidh tú guys go leor de na deiseanna chun cabhair a fháil, uaireanta oifige mar i gcónaí, agus táim ag súil go mór leis léamh gach ceann de do guys cód '. Tá mé tráth na gceist suas anseo má tá tú guys ag iarraidh teacht a fháil dóibh siúd. Sin é an méid.