>> [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.