>> [MIZIK jwe]
>> Andi Peng: Byenveni nan semèn 6 nan seksyon.
Nou sekarte soti nan estanda nou an seksyon lè nan Madi
apremidi nan sa a bèl dimanch maten.
Mèsi pou tout moun ke Joined m 'jodi a, men seryezman,
yon wonn nan aplodisman.
>> Sa se yon trè gwo efò.
Mwen prèske pa t 'menm fè l' moute nan tan, men Li te OK.
Se konsa, mwen konnen ke tout nan nou gen sèlman te fè li nan egzamen an.
Premye a tout, akeyi nan bò la baskile nan sa.
>> Dezyèmman, nou pral pale sou sa.
Nou pral pale sou egzamen an.
Nou pral pale sou fason w ap fè nan klas la.
Ou pral amann.
Mwen gen ti tès ou a pou ou nan fen a nan isit la,
Se konsa, si ou nèg vle pran yon gade nan li, totalman amann.
>> Se konsa, byen vit anvan nou kòmanse a, ajanda pou jodi a se jan sa a.
Kòm ou ka wè, nou ap tire fondamantalman rapid
atravè yon pakèt antye nan estrikti done reyèlman, reyèlman, reyèlman byen vit.
Se konsa, jan sa yo, li pa pral super entèaktif jodi a.
Li pral jis pou m 't'ap rele byen fò kalite bagay sa yo ke ou, epi si mwen konfonn ou,
si mwen pral twò vit, kite m 'konnen.
Yo ap jis divès kalite done estrikti, ak kòm yon pati
a pset ou pou sa a semèn kap vini, ou pral
ap mande yo aplike youn nan yo, petèt de nan them-- de nan disip yo
nan pset ou yo.
OK, se konsa mwen jis ale nan kòmanse ak kèk anons.
Nou pral ale sou pil ak ke moun kap kriye plis ankò nan pwofondè pase sa nou te fè anvan egzamen an.
Nou pral ale sou lye lis ankò, yon fwa ankò,
plis nan pwofondè pase sa nou te gen anvan egzamen an.
Lè sa a, nou pral pale sou regle tab, pye bwa ak ap eseye, ki
, yo tout bèl nesesè pou pset ou yo.
Lè sa a, nou pral ale sou kèk konsèy itil pou PSET5.
>> OK, se konsa egzamen 0.
Mwayèn a te yon 58%.
Li te trè ba, e konsa ou nèg tout te fè trè, trè byen nan akò
ak sa.
>> Bèl anpil, règ nan gwo pous se si w ap ki nan yon devyasyon estanda nan vle di la
espesyalman depi nou ap nan yon mwens confortable seksyon, w ap totalman amann.
Ou se sou track.
Lavi se bon.
>> Mwen konnen li nan pè panse ke Mwen te resevwa tankou yon% 40 sou egzamen sa a.
Mwen pral fail klas sa a.
Mwen te pwomèt ou, ou pa ap ale nan fail klas la.
Ou se totalman amann.
>> Pou moun nan nou ki te resevwa plis pase vle di a, enpresyonan, enpresyonan,
tankou, seryezman byen fèt.
Mwen gen yo avè m '.
Santi yo lib yo vini jwenn yo nan fen seksyon.
Kite m 'konnen si ou gen nenpòt pwoblèm, kesyon ak yo.
Si nou ajoute jiska nòt ou sa ki mal, fè nou konnen.
>> OK, se konsa PSET5, sa a se yon vrèman semèn etranj pou Yale nan sans
ki pset nou an, se akòz Mèkredi a midi ki gen ladan
an reta jou a, se konsa li la aktyèlman teyorikman akòz Madi nan midi.
Pwobableman pa gen yon fini a Madi nan midi.
Sa a totalman amann.
Nou ap ale nan gen lè biwo aswè a menm jan tou Lendi swa.
Apre sa, tout nan seksyon yo ki nan semèn sa a pral aktyèlman pral tounen atelye,
se konsa santi yo lib yo pòp nan nenpòt seksyon ou vle,
epi yo pral kalite mini-pset atelye pou èd sou sa.
Se konsa, jan sa yo, sa a se seksyon nan sèlman kote n ap anseye materyèl.
Tout lòt seksyon yo ki pral konsantre sèlman sou èd pou pset la.
Yeah?
>> ODYANS: Ki kote yo lè biwo?
>> Andi Peng: èdtan Biwo tonight-- oh, bon kesyon.
Mwen panse ke lè biwo aswè a se nan Teal oswa nan Commons.
Si ou tcheke sou entènèt CS50 epi ou ale nan biwo heures,
ta dwe gen yon orè ki di ou kote tout nan yo se.
>> Mwen konnen swa aswè a oswa demen se Teal,
e mwen panse nou ka gen Commons pou lòt nwit la la.
Mwen pa si.
Bon kesyon.
Tcheke sou CS50.
>> Cool, nenpòt kesyon konsènan nan orè pou pwochen an tankou twa jou?
Mwen te pwomèt ou nèg tankou David di, sa a se tèt la nan mòn lan.
Ou nèg yo se prèske la.
Jis twa plis jou.
Jwenn la, ak Lè sa a nou pral tout vini desann.
Nou pral gen yon bèl ti repo CS-gratis.
Nou pral tounen.
Nou pral plonje nan entènèt pwogram ak devlopman,
bagay ki trè amizan konpare nan kèk nan lòt psets yo.
Epi, se pral fredi, ak nou pral gen anpil bagay nan plezi.
Nou pral gen plis sirèt.
Padon pou sirèt.
Mwen bliye sirèt.
Se te yon maten ki graj.
Se konsa, ou nèg yo se prèske gen, ak mwen se reyèlman fyè de ou nèg.
>> OK, se konsa pil.
Ki moun ki te renmen kesyon an sou Jack ak rad l 'sou egzamen an?
Pa gen moun ki?
OK, sa a, se amann.
>> Se konsa, esansyèlman menm jan ou kapab foto Jack, sa a Guy isit la,
renmen pran rad la soti nan tèt la nan chemine a,
epi li mete l 'tounen sou chemine a apre li te fè.
Se konsa, nan fason sa a, li pa janm sanble ap resevwa
nan fon an nan la pile nan rad l 'yo.
Se konsa, sa a kalite dekri estrikti nan done debaz
nan ki jan se yon pil aplike.
>> Esansyèlman, panse a yon pile kòm nenpòt pil nan objè
kote ou mete bagay sa yo sou tèt la, epi Lè sa a, ou pòp yo soti nan tèt la.
Se konsa, LIFO se akwonim a nou renmen use-- Dènye nan, Premye Out.
Se konsa, dire an nan tèt la nan la chemine a se youn nan premye ki vini soti.
Se konsa, de kondisyon ki nou renmen asosye
ak sa yo rele pouse ak pòp.
Lè ou pouse yon bagay sou la pile, epi ou pòp l 'tounen moute.
>> Se konsa, mwen devine sa a se kalite yon abstrè konsèp pou moun nan nou
ki vle wè tankou yon aplikasyon aktyèl la nan sa a
nan mond lan reyèl.
Konbyen nan ou te ekri yon redaksyon petèt tankou yon èdtan anvan li te dwe,
ak aksidantèlman ou efase yon gwo ti moso nan li, tankou aksidantèlman?
Lè sa a, ki sa fè kontwòl nou itilize yo mete l 'tounen ankò?
Kontwòl-Z, yeah?
Kontwòl-Z, se konsa kantite lajan an nan fwa ki kontwòl-Z te sove lavi m ',
te sove manman bourik mwen an, chak fwa ki nan aplike nan yon pil.
>> Esansyèlman tout enfòmasyon ki sa a, se sou dokiman Pawòl ou,
li vin pouse ak déja nan volonte.
Se konsa, esansyèlman chak fwa ou efase anyen, ou pòp l 'tounen moute.
Lè sa a, si ou bezwen l 'tounen sou, ou pouse l ', ki se sa ki kontwòl-C fè.
Ak fonksyon mond se konsa reyèl nan ki jan senp estrikti done
ka ede ak lavi chak jou ou yo.
>> Se konsa, yon struct se yon fason a ki nou aktyèlman kreye yon chemine.
Nou tape defini struct, ak Lè sa nou rele li pile nan fon.
E nan lespas de chemine a, nou gen de paramèt
ke nou ka esansyèlman manipile, konsa nou gen Char zetwal strings kapasite.
>> Tout sa ki li se fè ap kreye yon etalaj
ke nou ka magazen tou sa ou vle ki nou ka detèmine kapasite li yo.
Kapasite Èske jis kantite lajan an nan max atik nou ka mete nan sa a etalaj.
gwosè int se kontwa an ki kenbe tras nan konbyen atik se kounye a
nan chemine a.
Se konsa, Lè sa a, nou ka kenbe tras nan, A, tou de ki jan gwo pil aktyèl la se,
epi, B, Ki jan anpil nan ki chemine nou te plen paske nou pa vle
debòde sou sa ki kapasite nou an, se.
>> Se konsa, pou egzanp, sa a bèl kesyon te sou egzamen ou yo.
Esansyèlman ki jan nou pouse sou tèt la nan yon pil.
Trè senp.
Si ou gade nan li, nou pral mache nan sa a.
Si [fèbl] size-- sonje, chak fwa ou
vle jwenn aksè nenpòt paramèt ki nan yon struct,
ou fè non an nan struct.parameter la.
>> Nan ka sa a, a se non an nan chemine nou an.
Nou vle jwenn aksè nan gwosè a nan li, se konsa nou fè s.size.
Se konsa, osi lontan ke gwosè a se pa egal a kapasite oswa osi lontan
kòm li nan mwens pase kapasite, swa ta travay isit la.
>> Ou vle jwenn aksè nan anndan an nan chemine ou, se konsa s.strings,
ak w ap ale nan mete sa nouvo nimewo ke ou vle insert nan la.
Se pou nou jis di nou pral vle Insert int n sou chemine a,
nou ta ka fè s.strings, parantèz, s.size egal n.
Paske gwosè se kote nou kounye a se nan chemine a
si nou ap ale nan pouse l 'sou, nou jis jwenn aksè nan
tout kote gwosè a se, nan gonfleman aktyèl la nan chemine a,
epi nou pouse n nan int sou li.
Lè sa a, nou vle asire w ke nou ap tou incrementing gwosè nan n nan,
pou nou ka kenbe tras nan nou te te ajoute yon bagay siplemantè nan pil la.
Koulye a, nou gen yon gwosè pi gwo.
Sa a isit la fè sans nan tout moun, ki jan lojikman li fonksyone?
Li te kalite rapid.
ODYANS: Èske ou ka ale sou s.stringss.strings yo [s.size] ankò?
Andi Peng: Asire w, Se konsa, sa fè s.size kounye a ban nou?
ODYANS: Li nan gwosè aktyèl la.
Andi Peng: Egzakteman, se konsa nan endèks aktyèl ki gwosè nou an, se nan,
epi pou nou vle mete nonb antye ki pè nan nouvo ke nou vle insert nan s.size.
Ki fè sans?
Paske s.strings, tout sa ki se se non an nan etalaj la.
Tout li se se aksè nan etalaj nan struct nou an,
Se konsa, si nou vle mete N nan ki endèks,
nou ka jis jwenn aksè li lè l sèvi avèk parantèz s.size.
Fre.
>> Tout dwa, pòp, mwen pseudocode li soti pou ou nèg, men konsèp menm jan an.
Ki fè sans?
Si gwosè a gen plis pouvwa pase zewo, lè sa a ou
konnen ke ou vle pran yon bagay soti paske si gwosè a se pa
pi gran pase zewo, lè sa a ou pa gen anyen nan chemine a.
>> Se konsa, ou sèlman vle al touye Kòd sa a, li ka sèlman
pòp si gen yon bagay nan pòp.
Se konsa, si gwosè a gen plis pouvwa pase 0, nou mwens gwosè a.
Nou dekrwasans gwosè a ak Lè sa a retounen tou sa se andedan nan li paske
pa eklate, nou vle aksè tou sa se ki estoke
nan endèks la nan tèt la nan chemine a.
Tout fè sans?
Si m 'te fè ou nèg ekri sa a soti, ta ou nèg pral kapab ekri li soti?
OK, ou nèg ka jwe otou ak li.
Pa gen enkyetid si ou pa jwenn li.
Nou pa gen tan nan kòd li soti jodi a paske nou te
te resevwa yon anpil nan sa yo estrikti yo ale nan, men esansyèlman
pseudocode, trè, trè menm jan ak pouse.
Jis swiv ansanm lojik la.
Pou pi si w ap gen aksè nan nan tout karakteristik nan struct ou kòrèkteman.
Yeah?
>> ODYANS: Èske glisad sa yo ak sa a tout antye bagay dwe moute jodi a-ich?
Andi Peng: Toujou, YEP.
Mwen pral eseye mete moute sa a tankou yon èdtan apre.
Mwen pral voye yon imèl ba David, David pral eseye mete l 'kanpe tankou yon èdtan apre sa a.
>> OK, se konsa lè sa a nou deplase ale nan sa a lòt bèl estrikti done yo te rele yon keu.
Kòm ou nèg ka wè isit la, yon keu, pou Britanik yo pami nou,
tout li se se yon liy.
Se konsa, kontreman a sa ou panse yon pil se,
yon keu se egzakteman sa lojikman ou panse li ye.
Li nan ki te fèt nan règleman yo nan FIFO, ki se Premye nan, Premye Out.
Si ou se premye moun yon sèl nan liy nan, w ap
youn nan premye ki soti nan jwèt la.
>> Se konsa, sa nou renmen yo rele sa a se dequeueing ak enqueueing.
Si nou vle ajoute yon bagay nan keu nou yo, nou enqueue.
Si nou vle dequeue, oswa pran yon bagay lwen, nou dequeue.
>> Se konsa, menm sans ke nou ap kalite kreye eleman fiks-gwosè ke nou
ka magazen sèten bagay sa yo, men nou kapab tou
chanje kote n ap mete paramèt andedan nan yo
ki baze sou ki kalite fonctionnalités nou vle.
Se konsa, pil, nou te vle dènye a yon sèl, N yo dwe premye yon sèl soti nan.
Keu se nou vle nan premye bagay nan yo dwe premye bagay la deyò.
>> Sa yo kalite nan struct defini, jan ou ka wè,
li nan yon ti jan ti kras diferan soti nan sa ki chemine a te
paske se pa sèlman fè nou gen kenbe tras nan kote gwosè a kounye a se,
nou menm tou nou vle kenbe tras nan tèt la osi byen ke kote nou kounye a ye.
Se konsa, mwen panse ke li nan pi fasil si mwen trase sa a leve.
Se konsa nou imajine nou te gen yon keu, kidonk kite pou nou di tèt la se dwa isit la.
Tèt la nan jwèt la, se pou yo jis di sa a, se kounye a gen,
epi nou vle insert yon bagay nan keu la.
Mwen pral rele gwosè esansyèlman se menm bagay la kòm ke,
nan fen tout kote keu ou se.
Se pou nou jis di gwosè se dwa isit la.
>> Se konsa, kouman fè yon sèl feasibly Insert yon bagay nan yon keu?
Ki sa ki endèks fè nou vle mete kote nou vle insert nan.
Si sa a se nan konmansman an nan ou nat ak sa a se nan fen li
oswa gwosè a nan li, kote nou fè vle ajoute objè a vin apre a?
>> ODYANS: [fèbl]
Andi Peng: Egzakteman, ou vle ajoute li depann sou ou ekri li.
Swa sa a se vid oswa ki vid.
Se konsa, ou vle ajoute li pwobableman isit la paske si gwosè a is--
si sa yo, yo tout plen, ou vle ajoute li dwa isit la, dwa?
>> Se konsa, sa a, se, pandan y ap trè, trè senp, pa byen toujou kòrèk
paske diferans lan prensipal ant yon keu ak yon pil
se ke keu la kapab aktyèlman ap manipile
se konsa ke chanjman sa yo tèt tou depann de ki kote ou vle
nan konmansman an nan Replik ou a kòmanse.
E kòm yon rezilta, ke ou se tou ale nan chanje.
Se konsa, pran yon gade nan kòd sa a kounye a.
Kòm ou nèg yo te tou mande yo ekri soti sou egzamen an, enqueue.
Petèt nou pral pale nan poukisa repons lan se sa ki te sa te pase.
>> Mwen pa te kapab byen anfòm liy sa a sou yon sèl, men esansyèlman sa a moso nan Kòd
yo ta dwe sou yon sèl liy.
Pase tankou 30 segonn.
A, voye je, ak wè poukisa sa se yon fason a ke li se.
>> Trè, trè menm jan struct, trè, trè menm jan estrikti kòm anvan an
pile eksepte pou petèt yon sèl liy nan kòd.
Epi sa yon sèl liy nan kòd detèmine fonctionnalités a.
Apre sa, li vrèman diferans yon keu soti nan yon pil.
>> Nenpòt moun ki vle pran yon koud a eksplike poukisa ou te
te resevwa bagay sa a konplike nan isit la?
Nou wè retounen nan nou an bèl bagay zanmi Modil.
Kòm ou nèg pral byento vini yo rekonèt nan pwogram,
prèske nenpòt lè ou bezwen yon bagay yo vlope alantou anyen,
Modil a pwal wout la nan fè li.
Se konsa, konnen ke, nenpòt moun vle eseye eksplike ke liy nan kòd?
Yeah, tout repons yo aksepte ak akeyi.
ODYANS: Èske ou ap pale ak m 'konsa?
Andi Peng: Yeah.
ODYANS: Oh, pa gen okenn regrèt.
Andi Peng: OK, se konsa kite a mache nan Kòd sa a.
Se konsa, lè w ap eseye ajoute yon bagay sou yon keu,
nan ka a bèl ke tèt la k ap pase yo dwe gen dwa isit la, li la trè fasil pou nou
jis ale nan fen a Insert yon bagay, dwa?
Men, pwen an antye nan yon keu se ke tèt la kapab aktyèlman dynamique
chanje tou depann de kote nou vle kòmanse nan q nou an yo dwe,
ak jan sa yo, ke a se tou ale nan chanje.
>> Se konsa, imajine ke sa a pa la te nat, men pito sa a te keu la.
Se pou nou di tèt la se dwa isit la.
Se pou nou di keu nou an te sanble ak sa a.
Si nou te vle chanjman kote nan konmansman an nan jwèt la se,
kite a di nou deplase tèt fason sa a ak tout gwosè isit la.
>> Koulye a, nou vle ajoute yon bagay yo keu sa a, men kòm ou nèg ka wè,
li nan pa konsa pou sa senp tankou jis ajoute tou sa se apre gwosè a
paske lè sa a nou kouri soti nan limit nan etalaj aktyèl nou yo.
Ki kote nou vle vrèman ajoute se isit la.
Sa a bote nan yon keu se ke ak nou, vizyèlman li
sanble liy la ale tankou sa a, Men, lè ki estoke nan yon estrikti done,
yo bay li kòm tankou yon sik.
Li kalite vlope alantou nan devan an menm jan an
ki yon liy kapab tou vlope alantou tou depann de tout kote ou
vle kòmansman nan jwèt la yo dwe.
Se konsa, si nou pran yon gade desann isit la, se pou yo
di nou te vle kreye yon fonksyon rele enqueue.
Nou te vle ajoute int n nan ki q.
Si q.size q nou pral rele ke done nou an structure-- si queue.size nou an pa fè sa
egal a kapasite oswa si li nan mwens pase kapasite,
q.strings se etalaj la nan q nou an.
Nou pral mete ki egal a q.heads,
ki se dwa isit la, plis q.size Modil pa kapasite la, ki
vlope nou tounen alantou isit la.
>> Se konsa, nan egzanp sa a, endèks nan tèt se 1, dwa?
Endèks la nan gwosè se 0, 1, 2, 3, 4.
Se konsa, nou kapab fè plis 1 4 Modil pa kapasite nou ki se 5.
Ki sa ki bay nou?
Ki sa ki se endèks la ki vini soti nan sa a?
>> ODYANS: 0.
>> Andi Peng: 0, ki k ap pase yo dwa isit la,
e konsa nou vle kapab insert nan dwa isit la.
Se konsa, isit la kalite ekwasyon sa a nan jis travay ak nenpòt ki nimewo
depann de kote ou tèt li ak gwosè ou ye.
Si ou konnen ki sa moun bagay sa yo yo, ou konnen
egzakteman ki kote ou vle insert tou sa se apre keu ou yo.
Ki fè sans nan tout moun?
>> Mwen konnen kalite yon sèvo kol espesyalman depi sa a
te vini nan a konsekans egzamen ou yo.
Men, èspere ke tout moun kounye a ka konprann
poukisa sa a oswa sa a solisyon fonksyon se yon fason a ke li se.
Nenpòt moun ki yon ti jan klè sou sa?
OK.
>> Se konsa, kounye a, si ou te vle dequeue, sa a
se kote tèt nou ta dwe déplacement paske si nou te dequeue,
nou pa pou yo wete tout nan fen q la.
Nou vle pou yo wete tout tèt la, dwa?
Se konsa, kòm yon rezilta, ki an tèt ki pral chanje, e se pou sa lè ou enqueue,
ou te gen nan kenbe tras nan kote tèt ou ak gwosè ou
se pou kapab Insert nan pozisyon ki kòrèk la.
>> Se konsa, lè ou dequeue, Mwen menm mwen te pseudocode li soti.
Santi yo lib yo si ou vle eseye kodaj sa a soti.
Ou vle pou avanse pou pi tèt la, dwa?
Si mwen te vle dequeue, mwen ta deplase tèt la sou.
Sa a ta dwe tèt la.
>> Ak gwosè nou an ki ajou ta fè soustraksyon paske nou pa gen okenn ankò
gen kat eleman nan etalaj la.
Nou gen sèlman twa, ak Lè sa nou vle retounen tou sa te estoke andedan
nan tèt la paske nou vle pran sa a valè soti pou trè menm jan ak chemine a.
Jis ou ap pran soti nan yon kote diferan,
epi ou gen yo mute konsèy ou nan diferan plas kòm yon rezilta.
Lojikman, tout moun swiv?
Great.
>> OK, se konsa nou ap ale nan pale yon ti plis nan pwofondè sou lis lye
paske yo pral trè, trè ki gen anpil valè pou ou nan kou a nan semenn sa a
psets.
Lis lye, kòm ou nèg ka sonje, tout sa yo se
yo nœuds ki nœuds nan sèten valè nan tou de se yon valè ak yon konsèy
ke yo lye ansanm pa moun endikasyon.
Se konsa, struct an sou kòman nou kreye yon ne isit la se nou
gen int n, ki se tou sa valè a nan yon magazen oswa fisèl N
oswa kèlkeswa sa ou vle rele l ', n nan zetwal Char.
Struct ne zetwal, ki se konsèy la ke ou vle gen nan chak ne,
w ap ale nan gen sa pwen konsèy nan direksyon pou kap vini an.
Ou ap gen tèt la nan yon lis lye sa a, se
ale nan lonje dwèt sou rès la nan valè yo sou sa ak pou fè
jiskaske ou evantyèlman rive nan fen an.
Lè sa a se jis ne dènye ale pa gen yon konsèy.
Li nan ale nan lonje dwèt sou nil, e ke sa a lè
ou konnen ou te frape a nan fen lis lye ou
se lè dènye konsèy ou pa lonje dwèt sou anyen.
>> Se konsa, nou ap ale nan ale yon ti jan pi plis nan pwofondè konsènan ki jan yon sèl ta pètèt
rechèch yon lis lye.
Sonje sa yo se kèk nan la dezavantaj nan lis yo lye
vèsè yon etalaj konsènan fouy.
Yon etalaj ou kapab rechèch binè, men poukisa yo pa ou ka fè sa nan yon lis lye?
>> ODYANS: Paske yo ap tout konekte, men ou pa byen konnen ki kote
[Fèbl].
>> Andi Peng: Yeah, egzakteman konsa sonje ki klere nan yon etalaj
te lefèt ke nou te gen aksè o aza memwa kote
si mwen te valè a soti nan endèks sis, mwen te kapab jis di endèks sis,
ban m 'ki valè.
Epi sa a, paske ranje yo ranje nan yon espas vwazen nan memwa
nan yon sèl kote, tandiske kalite lis lye
yo owaza antremele tout otou, ak wout la sèlman ou ka jwenn youn
se nan yon konsèy ki di ou adrès ki nan kote ki ne pwochen se.
>> Se konsa, kòm yon rezilta, yon fason a sèlman nan rechèch nan yon lis lye
se rechèch lineyè.
Paske mwen pa egzakteman konnen ki kote valè a 12yèm nan lis la lye se,
Mwen gen yo Traverse antye a nan ki lye youn lis
pa youn nan tèt la ne la an premye, nan dezyèm ne a, bay twazyèm ne la,
tout wout la desann jouk tan mwen finalman jwenn nan kote ki ne M 'ap chache se.
Se konsa, nan sans sa a, rechèch sou yon lis lye se toujou n.
Li nan toujou n.
Li nan toujou nan tan lineyè.
>> Se konsa, kòd a nan ki nou aplike sa a, ak sa a
se yon ti jan nouvo pou ou nèg depi ou mesye pa t 'reyèlman te pale osijè de tout tan tout tan oswa
wè endikasyon nan ki jan yo rechèch nan endikasyon,
se konsa nou pral mache nan sa a trè, trè dousman.
Se konsa, rechèch bouleen, dwa, kite a imajine nou vle
yo kreye yon fonksyon rele rechèch ki retounen vre
si ou jwenn yon valè andedan lye nan lis, epi li retounen fo otreman.
Lis zetwal neu se kounye a jis konsèy la
nan atik la premye nan lis lye ou yo.
int n se valè a ke w ap pou chèche nan ki lis.
>> Se konsa, zetwal ne konsèy egal lis.
Sa vle di nou ap mete ak kreye yon konsèy
ak sa yo ki premye ne andedan nan lis la.
Tout moun avè m '?
Se konsa, si nou te ale tounen isit la, mwen ta gen
inisyalizèd yon konsèy ki lonje dwèt nan tèt la nan tou sa ke lis se.
>> Lè sa a, yon fwa ou jwenn desann isit la, pandan y ap konsèy pa fè sa egal nil,
se konsa ke se bouk la nan ki nou yo se pral fè imedyatman Travelers
rès la nan lis nou an paske sa k ap pase lè konsèy egal nil?
Nou konnen nou en-
>> ODYANS: [fèbl]
>> Andi Peng: Egzakteman, se konsa nou konnen ke nou te rive jwenn nan fen lis, dwa?
Si ou ale tounen isit la, chak ne yo ta dwe lonje dwèt nan yon lòt ne
ak sou sa ak pou fè jiskaske ou frape evantyèlman
ke a nan lis lye ou, ki te gen yon konsèy ki jis
pa pwen nenpòt kote lòt pase pa gen okenn.
Se konsa, ou fondamantalman konnen ke lis ou a se toujou la moute
jouk konsèy pa fè sa egal nil paske yon fwa li egal nil,
ou konnen ke gen nan pa gen bagay plis.
>> Se konsa, se sa ki riban an nan ki nou ap ale nan gen rechèch la vrè.
Men, si pointer-- yo fè ou wè ki kalite fonksyon flèch la?
Se konsa, si pwen konsèy nan n, si konsèy la nan n egal egal n,
se konsa ke vle di ke si konsèy la ke w ap
pou chèche sou fen a nan chak ne se aktyèlman egal a valè a
w ap chèche pou, lè sa a ou vle retounen vre.
Se konsa, fondamantalman, si w ap nan yon ne ki gen valè nan ke w ap chèche pou yo,
ou konnen ke ou ve yo te kapab avèk siksè rechèch.
>> Sinon, ou vle yo mete konsèy ou nan ne kap vini an.
Se pou sa ke ke liy isit la ap fè.
Pointer egal konsèy kap vini an.
Tout moun wè ki jan ki nan travay?
>> Apre sa, esansyèlman w ap ale nan jis Traverse antye a nan lis la,
re konsèy ou chak fwa jiskaske ou evantyèlman frape nan fen lis la.
E ou konnen ke pa gen okenn plis nœuds nan rechèch nan,
ak Lè sa a ou ka retounen fo paske ou konnen ke, o, byen,
si mwen te kapab fè rechèch a antye a nan lis la.
Si nan egzanp sa a, si mwen te vle yo gade pou valè a nan 10,
ak mwen kòmanse nan plas tèt la, epi Mwen rechèch tout wout la desann,
ak mwen evantyèlman te rive nan sa a, ki yon konsèy ki lonje dwèt nan nil,
Mwen konnen ke, krap, mwen devine 10 se pa nan lis sa a paske mwen pa t 'kapab jwenn li ankò.
Apre sa, mwen se nan fen lis la.
Ak nan ka sa a ou konnen Mwen pral retounen fo.
>> Se pou ki tranpe nan pou yon ti jan ti kras.
Sa a pral trè enpòtan pou pset ou yo.
Lojik la nan li se trè senp, petèt syntactically jis mete ann aplikasyon li.
Ou nèg vle fè asire w ke ou konprann.
Fre.
>> OK, se konsa ki jan nou ta dwe mete nœuds, dwa,
nan yon lis paske sonje ki sa yo sa ki nan nan benefis ki genyen
ki gen yon lis lye kont yon etalaj nan tèm nan depo?
>> ODYANS: Li nan dinamik, se konsa li pi fasil to--
>> Andi Peng: Egzakteman, se konsa li a dinamik, ki
vle di ke li ka elaji ak retresi depann sou bezwen itilizatè a la.
Se konsa, nan sans sa a, nou pa bezwen nan fatra memwa nesesè paske mwen
si mwen pa konnen ki jan anpil valè mwen vle nan magazen, li pa fè sans pou m '
yo kreye yon etalaj paske si mwen vle nan magazen 10 valè
ak mwen kreye yon etalaj de 1,000, sa a, se yon anpil nan gaspiye memwa, an.
Se poutèt sa nou vle sèvi ak yon lye lis pou kapab dynamique
chanje oswa retresi gwosè nou an.
>> Se konsa, ki fè ensèsyon yon ti jan pi konplike.
Depi nou pa ka jwenn aksè eleman owaza wout la ke nou ta nan yon etalaj.
Si m 'vle insert yon eleman nan setyèm endèks la,
Mwen jis ka insert li nan setyèm endèks la.
Sou yon lis lye, li fè sa pa byen travay kòm fasil,
ak Se konsa, si nou te vle insert yon sèl la isit la nan lis la lye,
vizyèlman, li la trè fasil yo wè.
Nou jis vle insert li dwat la, dwa nan konmansman an nan lis la,
dwa apre tèt yo.
>> Men, wout la nan ki nou dwe mute endikasyon yo se yon ti jan konplitché
oswa, lojikman, li fè sans, men ou vle asire w ke ou genyen li
konplètman desann paske bagay la pase ou vle
se mute yon konsèy nan fason ki n ap fè isit la.
Si ou dèreferans a konsèy nan tèt nan 1,
Lè sa a, tout nan yon toudenkou nan rès lis lye ou
se pèdi paske ou gen pa aktyèlman kreye yon anyen pou yon ti tan.
Sa a pwente nan 2 a.
Si ou mute konsèy la, lè sa a nan se rès nan lis ou a totalman pèdi.
Se konsa, ou vle yo dwe trè, trè atansyon isit la
nan premye asiyen nan konsèy soti nan tou sa ou
vle insert nan tout kote ou vle, ak Lè sa a ou
kapab dèreferans rès la nan lis ou a.
>> Se konsa, sa a aplike pou tout kote w ap eseye insert nan.
Si ou vle insert nan la tèt, si ou vle reponn isit la,
si ou vle insert nan fen a, byen, fen I
devine ou ta jis pa gen okenn konsèy, men ou
vle asire w ke ou pa fè sa pèdi rès la nan lis ou a.
Ou toujou vle asire w ke nouvo ne nou an, ap lonje dwèt
nan direksyon pou tou sa ou vle insert nan,
ak Lè sa a ou ka ajoute Anchènman la sou.
Tout moun klè?
>> Sa a se pral yo dwe youn nan pwoblèm yo ki reyèl.
Youn nan pwoblèm ki pi gwo w ap ale nan gen sou ou pset
se ke ou ap ale nan eseye kreye yon lis lye ak bagay sa yo insert
men Lè sa a jis pèdi nan rès lis lye ou yo.
Apre sa, w ap ale nan dwe tankou, mwen pa konnen poukisa sa a sa k ap pase?
Lè li nan yon doulè yo ale nan ak rechèch tout nan endikasyon ou yo.
>> Apre sa, mwen garanti ou sou pset sa a, ekri ak desen nœuds sa yo soti
pral trè, trè itil.
Se konsa, ou ka konplètman kenbe tras a kote tout endikasyon ou yo,
sa k ap pase sa ki mal, kote tout nœuds ou yo,
ki sa ou bezwen pou fè pou jwenn aksè oswa Insert ou efase oswa nenpòt nan yo.
Tout moun bon ak sa?
Fre.
>> Se konsa, si nou te vle fè yon gade nan kòd la?
Oh, mwen pa konnen si nou ka wè the-- OK, se konsa
nan tèt la tout li se se yon fonksyon yo te rele insert kote nou vle
insert int n nan lis la lye.
Nou pral mache nan sa a.
Li se yon anpil nan kòd, yon anpil nan nouvo sentaks.
Nou pral OK.
>> Se konsa, moute nan tèt la, chak fwa nou vle yo kreye anyen
ki sa nou bezwen fè, espesyalman si w vle li nan pa dwe estoke sou pil la
men nan pil wòch la?
Nou ale nan yon malok, dwa?
Se konsa, nou ap ale nan kreye yon konsèy.
Ne, konsèy, nouvo egal malok gwosè a nan yon ne
paske nou vle ak sa yo ki ne dwe kreye.
Nou vle kantite lajan an nan memwa ki yon ne pran moute
yo dwe attribué pou a kreyasyon ne nan nouvo.
>> Lè sa a, nou ap ale nan tcheke yo wè si nouvo egal egal nil.
Sonje sa nou te di?
Tou sa ou malok, kisa pou ou toujou fè?
Ou dwe toujou tcheke yo wè si wi ou non se sa ki nil.
>> Pou egzanp, si opere ou sistèm te konplètman plen,
si ou te gen pa plis memwa a tout ak ou eseye malok,
li ta retounen nil pou ou.
Se konsa, si ou eseye sèvi ak li lè li te lonje dwèt nan nil,
ou pa ap ale nan kapab jwenn aksè nan enfòmasyon sa a.
Se konsa, jan sa yo, nou te vle fè asire w ke chak fwa w ap mallocing,
ou toujou ap tcheke yo wè si ke memwa ban nou se nil.
Men, si li pa, lè sa a nou kapab deplase sou ak rès la nan kòd nou an.
>> Se konsa, nou ap ale nan inisyalize ne nan nouvo.
Nou ap pral fè nouvo n egal n.
Lè sa a, nou ap ale nan fè mete nouvo konsèy la sou nouvo
nil paske kounye a nou pa fè sa vle anyen pou li nan pwen nan.
Nou pa gen okenn lide kote li k ap pase yo mete ou,
ak Lè sa a si nou vle insert l nan plas tèt la,
Lè sa a, nou ka mute konsèy la nan tèt la.
Tout moun swiv lojik la nan kote ki nan k ap pase?
>> Tout sa nou ap fè se kreye yon nouvo ne, mete konsèy la nil,
ak Lè sa a reafèktasyon li nan tèt la si nou
konnen nou vle insert li nan tèt la.
Lè sa a, tèt la ki pral pwen nan direksyon pou ke nouvo ne.
Tout moun OK ak sa?
>> Se konsa, li yon pwosesis de-etap.
Ou te gen nan premye asiyen tou sa ou ap kreye.
Mete ki konsèy nan la referans, ak lè sa a ou
kapab kalite dèreferans konsèy la premye
ak pwen li nan direksyon pou ne nan nouvo.
Kèlkeswa kote ou vle insert li, ki lojik ki pral kenbe vre.
>> Li nan kalite tankou plase varyab tanporè.
Sonje byen, ou te gen a asire w ke ou
pa pèdi tras nan si w ap échanjé.
Ou vle asire w ke ou gen yon varyab tanporè ki kalite kenbe
tras nan kote ke bagay se ki estoke pou ke ou
pa pèdi nenpòt valè nan kou a de tankou pitye otou ak li.
>> OK, se konsa Kòd yo pral isit la.
Ou nèg pran yon gade apre seksyon.
Li pral dwe la.
>> Se konsa, mwen devine ki jan fè sa a diferan si nou te vle
insert nan mitan an oswa nan fen a?
Nenpòt moun ki gen yon lide sou sa ki nan la pseudocode kòm referans a lojik
ke nou ta pran si nou te vle insert l 'nan mitan an?
Se konsa, si nou te vle insert l nan la tèt, tout sa nou fè se kreye yon nouvo ne.
Nou mete konsèy sa a nan nouvo ne mèt fè tout sa tèt la,
ak Lè sa a nou mete tèt la ne nan nouvo, dwa?
Si nou te vle insert l nan mitan an nan lis la, sa ki ta nou dwe fè?
>> ODYANS: Li ta toujou gen yon pwosesis ki sanble
de tankou plase konsèy ak Lè sa a, plase ki konsèy,
men nou ta gen jwenn a.
>> Andi Peng: Egzakteman, se konsa egzakteman pwosesis la menm eksepte ou
gen jwenn kote egzakteman ou vle ke nouvo konsèy yo ale nan,
Se konsa, si mwen vle insert nan mitan an nan lye list-- OK,
kite a di sa a, se lis lye nou an.
Si nou vle insert l dwa isit la, nou ap ale nan kreye yon nouvo ne.
Nou pral malok.
Nou pwal kreye yon nouvo ne.
Nou pral bay nan konsèy nan ne sa a isit la.
>> Men, pwoblèm nan ki diferan ki soti nan kote tèt la se
se ke nou te konnen egzakteman kote tèt la se.
Li te dwa nan premye a, dwa?
Men, isit la nou te gen nan kenbe tras a kote n ap mete l 'nan.
Si nou ap mete nou an ne isit la, nou te gen
a asire w ke nan youn anvan Ki jan yo ne sa a
se youn nan ki reassigns konsèy la.
Se sak fè ou gen kalite kenbe tras nan de bagay sa yo.
Si ou kenbe tras nan kote sa a ne kounye a mete nan.
Ou gen tou nan kenbe tras nan kote ne a anvan ke w ap chèche a
te tou a.
Tout moun bon ak sa?
OK.
>> Kouman sou mete an fen a?
Si mwen te vle ajoute li isit lan-- si mwen te ajoute yon nouvo ne nan fen a nan yon lis,
ki jan mwen ta ka ale sou fè sa?
ODYANS: Se konsa, kounye a, nan pwente yon dènye a nil.
Andi Peng: Yeah.
Egzakteman, se konsa yon sèl sa a kounye a pwente nan konnen,
Se poutèt sa mwen devine, nan sans sa a, li nan trè fasil pou ajoute pou nan fen yon lis.
Tout sa ou dwe fè se mete l ' egal a nil ak Lè sa a boom.
Dwa a, trè fasil.
Trè senp.
>> Sanble anpil ak nan tèt, men lojikman ou
vle asire w ke etap sa yo ou pran nan direksyon pou fè nenpòt nan sa a,
w ap yo ansanm.
Li trè fasil yo, nan mitan an nan kòd ou a, jwenn kenbe moute sou li a,
oh, mwen te gen anpil endikasyon.
Mwen pa konnen ki kote se anyen montre nan.
Mwen pa menm konnen ki ne mwen se sou.
Sa k pase?
>> Rilaks, kalme, pran yon gwo souf.
Trase soti lis lye ou yo.
Si ou di, mwen konnen ki kote egzakteman Mwen bezwen insert sa a nan
e mwen konnen egzakteman ki jan yo mute mwen endikasyon, anpil, anpil pi fasil yo foto
out-- anpil, pi fasil yo pa jwenn pèdi nan pinèz yo nan kòd ou a.
Tout moun OK ak sa?
OK.
>> Se konsa, mwen devine yon konsèp ke nou pa gen reyèlman te pale osijè de anvan kounye a,
ak mwen devine ou pwobableman pa pral kontre anpil yet--
li nan kalite yon concept-- avanse se ke nou gen aktyèlman yon done
estrikti rele yon lis doubl lye.
Se konsa, kòm ou nèg ka wè, tout sa nou ap fè se kreye
yon valè aktyèl, yon siplemantè konsèy sou chak nan nœuds nou an
ki tou lonje dwèt nan ne a anvan yo.
Se konsa, pa sèlman a nou gen nou an nœuds lonje dwèt sou youn nan pwochen.
Yo menm tou yo lonje dwèt sou yon sèl anvan an.
Mwen pral inyore sa yo de kounye a.
>> Se konsa, Lè sa a, ou gen yon chèn ki ka deplase tou de fason,
ak Lè sa a li nan yon ti jan pi fasil lojikman swiv ansanm.
Fè tankou isit la, olye pou yo kenbe tras nan, o, mwen
gen konnen ki ne sa a se yon sèl la ki mwen gen yo mute,
Mwen ka jis ale isit la ak jis rale anvan an.
Apre sa, mwen konnen egzakteman ki kote se sa ki, ak Lè sa a ou
pa bezwen Traverse a antye nan lis la lye.
Li yon ti jan pi fasil.
>> Men, jan sa yo, ou gen doubl kantite lajan an nan endikasyon,
sa a, se doub kantite lajan an nan memwa.
Li se yon anpil nan endikasyon nan kenbe tras nan.
Li se yon ti jan pi plis konplèks, men li la yon ti jan plis itilizatè zanmitay depann
sou sa ki w ap eseye akonpli.
>> Se konsa, sa a ki kalite done estrikti totalman egziste,
ak estrikti a pou se trè, trè senp eksepte tout sa ou ap gen se,
olye pou yo jis yon konsèy nan pwochen, ou gen tou yon konsèy nan anvan yo.
Sa a tout diferans lan te ye a.
Tout moun bon ak sa?
Fre.
>> Tout dwa, se konsa kounye a mwen se reyèlman depanse pwobableman
tankou 15 a 20 minit oswa èstime nan rès la nan tan an nan seksyon
ap pale de tab regle.
Konbyen nan ou nèg te li PSET5 espèk?
Tout dwa, bon.
Sa a pi wo pase 50% nan nòmalman.
Li nan OK.
>> Se konsa, kòm ou nèg pral wè, w ap defi nan PSET5
yo pral aplike yon diksyonè kote ou chaje sou 140,000 mo
ke nou ba ou ak eple chèk li kont tout nan tèks la.
Nou pral ba ou o aza moso nan literati.
Nou pral ba ou Odyssey la.
Nou pral ba ou Iliad a.
Nou pral ba ou Austin Powers.
>> Apre sa, defi ou yo pral eple chèk
tout pawòl sèl nan tout nan tout sa yo diksyonè
esansyèlman ak korektè période nou an.
Se konsa, gen nan yon pati kèk pou kreye pset sa a,
premye ou vle yo dwe kapab aktyèlman chaje
tout mo sa yo nan ou diksyonè, ak lè sa a ou
vle pou kapab eple tcheke tout nan yo.
Se konsa, jan sa yo, w ap ale nan mande pou yon estrikti done ki ka fè sa vit
epi avèk efikasite ak dynamique.
>> Se konsa, Mwen ta kwè pi fasil la fason yo fè sa, ou
ta pwobableman kreye yon etalaj, dwa?
Fason ki pi fasil nan depo se ou kapab kreye yon etalaj de 140,000 Mo
ak jis mete yo tout gen ak Lè sa a, Traverse yo pa rechèch binè
oswa pa seleksyon oswa not-- regrèt ki nan klasman.
Ou ka sòt yo ak Lè sa a Traverse yo pa rechèch binè oswa rechèch jis lineyè
ak jis final mo sa yo, men sa pran yon kantite lajan gwo memwa,
epi li pa trè efikas.
>> Se konsa, nou ap ale nan kòmanse ap pale de fason pou fè
tan kouri nou an pi efikas.
Apre sa, objektif nou se yo ka resevwa tan konstan kote
li nan prèske tankou ranje, kote ou gen aksè enstantane.
Si mwen te vle pou fè rechèch pou yon bagay, Mwen vle pou kapab jis,
boom, jwenn li egzakteman, e ki rale li soti.
Se konsa, yon estrikti nan ki nou pral vin trè pre
yo dwe kapab jwenn aksè nan konstan tan, grail apa pou Bondye sa a
nan pwogram nan konstan se tan rele yon tab regle.
Se konsa, David te deja mansyone nan [Fèbl] yon ti jan ti kras nan konferans,
men nou ap ale nan reyèlman plonje nan gwo twou san fon nan semèn sa a
sou yon moso ki nan konsènan ki jan yon tab regle travay.
>> Se konsa, fason ke yon regle travay tab, pou egzanp,
si mwen te nan magazen yon pakèt moun sou mo, yon pakèt moun sou mo nan lang angle a,
Mwen te kapab teyorikman mete fig, pòm, kiwi, mango, pè,
ak Kantaloup tout sou jis yon etalaj.
Yo te kapab tout anfòm nan yo epi yo dwe jwenn.
Li ta dwe kalite yon doulè yo rechèch nan ak aksè,
men wout la pi fasil pou fè sa a se ke nou kapab kreye yon estrikti aktyèlman
rele yon tab regle kote nou regle.
Nou kouri tout nan kle nou yo atravè yon fonksyon regle, yon ekwasyon,
ki vin yo tout nan kèk sòt de se yon valè
ki lè sa a nou ka magazen sou esansyèlman yon etalaj de lis lye.
>> Se konsa, isit la, si nou te vle nan magazen mo angle,
nou te kapab potansyèlman jis, mwen pa fè sa konnen, vire tout lèt yo an premye
nan kèk sòt de yon kantite.
Se konsa, pou egzanp, si mwen te vle Yon yo dwe synonyme ak apple--
oswa avèk endèks la nan 0, ak B yo dwe synonyme ak 1,
nou ka gen 26 antre ki ka jis magazen
tout nan lèt yo nan a alfabè ke nou pral kòmanse avèk yo.
Lè sa a, nou ka gen pòm nan endèks la nan 0.
Nou ka gen bannann nan endèks la nan 1, Kantaloup nan endèks la nan 2,
ak sou sa ak pou fè.
Epi konsa, si mwen te vle rechèch tab ak aksè pòm regle m 'yo,
Mwen konnen pòm kòmanse ak yon A, epi mwen konnen egzakteman
ke li dwe dwe ak regle nan tab nan endèks 0 paske
nan fonksyon an deja asiyen.
>> Se konsa, mwen pa konnen, nou se yon pwogram itilizatè kote
ou pral chaje avèk arbitrarily-- pa abitrèman,
ak ap eseye reflechi byen panse a ekwasyon bon
pou kapab gaye soti tout nan valè ou
nan yon fason yo ka byen fasil jwenn aksè nan li pita sou ak tankou yon ekwasyon
ke ou, tèt ou, konnen.
Se konsa, nan sans nan si mwen te vle ale nan mango, mwen konnen, o, li kòmanse ak m.
Li dwe fèt nan endèks la nan 12.
Mwen pa gen nan rechèch nan anyen.
Mwen konnen exactly-- mwen te kapab jis ale nan endèks la nan 12 ak rale ki soti.
>> Tout moun klè sou ki jan yon fonksyon regle tab la travay?
Li nan kalite jis yon etalaj pi konplike.
Sa a tout li ye.
OK.
>> Se konsa, mwen devine nou kouri antre nan pwoblèm sa a nan sa ki
k ap pase si ou gen plizyè bagay ki ba ou endèks la menm?
Se konsa, di fonksyon nou an, tout li te fè te pran ki premye lèt
epi y'a vire ki nan yon respektif 0 a 25 endèks.
Sa a totalman amann si ou gen sèlman youn nan chak.
Men, dezyèm lan ou kòmanse gen plis, w ap
ale nan gen sa ki rele yon kolizyon.
>> Se konsa, si mwen eseye insert antere nan yon regle tab ki deja gen fig sou li,
sa ki pwal rive lè ou eseye insert sa?
Bagay move paske fig deja egziste nan endèks la
ke ou vle nan magazen l 'nan.
Berry kalite, se tankou, ah, ki sa mwen fè?
Mwen pa konnen ki kote yo ale.
Kouman pou mwen rezoud sa a?
>> Se konsa, ou nèg pral kalite wè nou fè sa sa a difisil
kote nou kapab kalite aktyèlman kreye lis lye nan ranje nou an.
Se konsa, fason ki pi fasil yo reflechi sou sa a,
tout tab regle se yon etalaj de lis lye.
Se konsa, nan sans sa, ou gen sa a etalaj bèl nan endikasyon,
ak Lè sa a chak konsèy nan ki valè, nan ki endèks,
ka aktyèlman lonje dwèt sou lòt bagay.
Se konsa, ou gen tout bagay sa yo apa chenn vini sou nan yon sèl gwo etalaj.
>> Se konsa, isit la, si mwen te vle insert Berry,
Mwen konnen, OK, mwen pral D ' li nan fonksyon regle m 'yo.
Mwen pral fini ak endèks la nan 1, ak Lè sa a, mwen pral kapab gen
jis yon sou ki pi piti nan sa a jeyan diksyonè 140,000-mo.
Lè sa a, mwen kapab jis gade a 1/26 nan sa.
>> Se konsa, Lè sa a, mwen ka jis Insert Berry swa anvan oubyen apre bannann
nan ka sa?
Apre, dwa?
Se konsa, w ap ale nan vle Insert ne sa a apre fig,
e konsa w ap ale nan Insert a ke a nan ke lis lye.
Mwen pral tounen nan sa a glise anvan,
se konsa ou nèg ka wè ki jan fonksyon regle travay.
>> Se konsa, fonksyon regle se ekwasyon sa a ke w ap kouri kalite opinyon ou
a yo ka resevwa tou sa endèks ou vle bay li nan direksyon pou.
Se konsa, nan egzanp sa a, tout nou te vle fè te pran lèt la an premye,
vire ki nan yon endèks, lè sa a nou ka magazen ki nan fonksyon regle nou an.
Tout sa nou ap fè isit la se nou ap konvèti lèt la an premye.
Se konsa, keykey [0] se jis lèt la premye nan tou sa fisèl nou ap fè,
nou ap pase nan.
Nou ap konvèti ke yo anwo kay la, ak nou ap soustraksyon pa majuskul A,
se konsa tout sa ki ap fè an, ap ban nou yon nimewo
nan ki nou ka Hash valè nou sou.
>> Lè sa a, nou ap ale nan retounen regle SIZE Modil.
Dwe pran anpil, anpil prekosyon paske, teyorikman, isit la
valè regle ou ta ka enfini.
Li ta jis ale sou yo ak sou sou yo ak sou sou.
Li ta ka gen kèk reyèlman, reyèlman gwo valè,
men paske tab regle ou a, ki ou te kreye sèlman gen 26 endis,
ou vle asire w ke ou modulusing pou ke ou
pa run-- li nan menm bagay la tou bagay tankou queue-- ou
pou ke ou pa kouri ale nan anba nan fonksyon regle ou yo.
>> Ou vle vlope l 'tounen bò kote menm jan an nan [fèbl] lè
ou te gen tankou yon anpil, gwo anpil lèt, ou
pa t 'vle ke yo jis kouri nan fen an.
Menm bagay isit la, ou vle asire w ke li pa kouri ale nan fen a pa vlope
alantou nan tèt la nan tab la.
Se konsa, sa a se jis yon trè senp fonksyon regle.
Tout sa ki te fè te pran premye a lèt nan tou sa D 'nou an te
epi y'a vire ki nan yon endèks ki nou te ka mete nan tab regle nou yo.
>> Yeah, epi konsa jan mwen te di anvan, fason a ke nou rezoud kolizyon
nan regle nou an tab yo gen, sa nou rele, Anchènman.
Se konsa, si ou eseye insert miltip mo ki kòmanse ak menm bagay la,
w ap ale nan gen yon sèl valè regle.
Zaboka ak pòm, si ou te kouri l 'nan fonksyon regle nou an,
yo ale nan bay la ou menm nonb, ki kantite 0.
Se konsa, fason nou rezoud ki se ke nou ka aktyèlman kalite lyen yo
ansanm via lis lye.
>> Se konsa, nan sans sa a, ou nèg ka wè kalite
nan ki jan done estrikti ki nou ve yo te mete deja
tankou yon rezen lye kalite lis a ka vini ansanm nan yon sèl.
Lè sa a, ou kapab kreye byen lwen estrikti done pi efikas
ki ka okipe pi gwo kantite done, ki dynamique rdimansyonman depann
sou bezwen ou yo.
Tout moun klè?
Tout moun nan klè kalite sou sa k ap pase isit la?
>> Si mwen te vle insert sa ki nan yon fwi ki kòmanse ak, mwen pa konnen,
B, lòt pase Berry, bannann.
>> ODYANS: Blackberry.
>> Andi Peng: Blackberry, blackberry.
Ki kote blackberry ale isit la?
Oke, nou aktyèlman pa gen Ranje sa a ankò, men teyorikman
si nou te vle gen sa a yo nan lòd alfabetik,
kote yo ta dwe blackberry ale?
>> ODYANS: [fèbl]
>> Andi Peng: Egzakteman, apre yo fin isit la, dwa?
Men, depi li nan trè difisil yo reorder-- Mwen devine li a jiska ou guys.
Ou nèg ka totalman aplike tou sa ou vle.
Fason ki pi efikas pou fè sa a petèt
ta dwe sòt lye ou lis nan lòd alfabetik,
ak pou lè w ap mete bagay sa yo, ou vle
yo dwe asire insert yo nan lòd alfabetik
se konsa ke Lè sa a, lè w ap ap eseye rechèch yo,
ou pa bezwen Traverse tout bagay.
Ou konnen egzakteman ki kote li se, ak li a pi fasil.
>> Men, si ou kalite gen bagay antremele owaza,
w ap toujou ale nan gen Traverse li aniwe.
Se konsa, si mwen te vle jis Insert blackberry isit la
epi mwen te vle rechèch pou li, mwen konnen, o, blackberry
dwe kòmanse ak endèks la nan 1, se konsa mwen konnen enstantane jis rechèch nan 1.
Lè sa a, mwen kapab kalite Traverse lis la lye
jouk tan mwen li ale nan mur, ak then-- yeah?
>> ODYANS: Si w ap eseye create-- Mwen devine tankou sa a se yon regle trè senp
fonksyon.
Men, si nou te vle fè kouch miltip nan ki tankou,
OK, nou vle separe nan tankou tout lèt yo alfabetik
ak Lè sa a ankò nan renmen yon lòt seri nan lèt alfabetik nan sa,
yo nou mete tankou yon regle tab ki nan yon tab regle,
oswa tankou yon fonksyon ki nan yon fonksyon?
Oubyen èske that--
>> Andi Peng: Se konsa, regle ou fonksyon-tab regle ou
ka kòm gwo tankou ou vle l 'bay.
Se konsa, nan sans sa a, mwen te panse li te trè fasil, trè
senp pou mwen pou m jis sòt ki baze sou lèt nan pawòl Bondye a an premye.
Se konsa, gen nan sèlman 26 opsyon.
Mwen ka sèlman jwenn 26 opsyon soti nan 0 a 25 paske yo kapab sèlman
kòmanse soti nan A jiska Z. Men, Si ou te ajoute, petèt, plis konpleksite
oswa pi vit nan ou kouri tan tab regle, ou absoliman
ka fè tout kalite bagay sa yo.
Ou kapab fè pwòp ou a ekwasyon ki ba ou
plis distribisyon nan ou mo, Lè sa a, lè ou rechèch,
li nan pral fè pi vit.
>> Li nan totalman jiska ou nèg ki jan ou vle aplike sa.
Panse a li kòm jis bokit.
Si m 'te vle gen 26 bokit, mwen pral
sòt bagay sa yo nan sa yo bokit.
Men, mwen pral gen yon pakèt moun nan bagay nan chak bokit,
Se konsa, si ou vle fè l ' pi vit ak pi efikas,
kite m 'gen yon santèn bokit.
>> Men, lè sa a ou gen figi konnen yon fason yo sòt bagay sa yo sa yo ke yo yo se
nan bokit la apwopriye yo ta dwe a.
Men, Lè sa lè ou aktyèlman vle gade nan ki bokit,
li nan yon anpil pi vit paske gen nan mwens bagay nan chak bokit.
Se konsa, yeah, sa a, se aktyèlman jwe fent la pou ou nèg nan PSET5
se ke ou pral defye yo jis kreye
tou sa se pi efikas nan fonksyon ou ka panse a yo dwe
kapab nan magazen epi tcheke valè sa yo.
>> Totalman jiska ou nèg sepandan ou vle fè l ',
men sa a yon pwen reyèlman bon.
Sa kalite a nan lojik ou vle kòmanse panse sou
se, byen, poukisa pa mwen fè plis bokit.
Lè sa a, mwen gen fè rechèch mwens bagay sa yo, ak Lè sa a petèt mwen
gen yon fonksyon regle diferan.
>> Yeah, gen nan yon anpil nan fason yo fè sa pset, gen kèk ki pi vit pase lòt moun.
Mwen totalman ale nan jis wè ki jan vit te ou mesye yo pi rapid pral
pral kapab jwenn fonksyon ou nan travay.
OK, tout moun bon sou Anchènman ak regle tab?
Li nan aktyèlman tankou yon trè senp konsèp si ou panse sou li.
Tout li se se separe tou sa entrain ou yo nan bokit,
Fouye yo, ak Lè sa a chèche nan bay lis ki gen nan ki asosye avèk yo.
>> Fre.
Tout dwa, kounye a nou gen yon sòt diferan nan estrikti done ki yo rele yon pye bwa.
Se pou nou ale sou yo ak sou ap eseye pale ki se klerman diferan,
men nan menm kategori a.
Esansyèlman, tout yon pye bwa se olye pou òganize done nan wout la lineyè
ki yon tab regle does-- ou konnen, li nan te resevwa yon tèt ak yon anba
ak Lè sa a ou kalite lyen koupe nan yon l-- pyebwa gen yon tèt ki ou rele rasin nan,
ak Lè sa a li gen fèy tout bò kote l '.
>> Se konsa, tout sa ou gen isit la se jis ne nan tèt
ki pwen nan lòt nœuds, ki pwen nan plis nœuds, ak sou sa ak pou fè.
Se konsa, ou jis gen branch divize.
Se jis nan yon fason diferan pou òganize done, epi paske nou rele li yon pye bwa,
ou nèg just-- li nan jis modelize soti nan gade tankou yon pyebwa.
Se poutèt sa nou rele li pye bwa.
>> Tab regle sanble yon tab.
Yon pye bwa jis sanble yon pye bwa.
Tout li se se yon separe fason pou òganize nœuds
depann sou sa ki bezwen ou yo ye.
>> Se konsa, ou gen yon rasin ak Lè sa a, ou gen fèy bwa.
Fason ki ke nou kapab patikilyèman panse sou li se yon pye bwa binè,
yon pye bwa binè se jis yon kalite espesifik nan yon pye bwa
kote chak ne sèlman pwen a, nan max, de lòt nœuds.
Se konsa, isit la ou gen distenk simetri nan pye bwa ou
ki fè li pi fasil yo kalite gade nan sa ki valè ou se paske lè sa a ou
gen toujou yon bò gòch oswa yon dwa.
Genyen pa janm tankou yon twazyèm soti nan bò gòch gòch la oswa yon katriyèm soti nan bò gòch la.
Se jis ou gen yon kite la ak yon dwa epi ou kapab fè rechèch swa nan tout sa yo de.
Se konsa, poukisa se sa a itil?
Fason ki ke sa a se itil se si w ap chèche
nan rechèch nan valè, dwa?
Olye ke mete ann aplikasyon binè rechèch nan yon etalaj erè,
si ou te vle pou kapab Insert nœuds ak pran nœuds nan volonte epi tou
prezève rechèch la kapasite nan binè rechèch.
Se konsa, nan fason sa a, nou ap kalite tricking-- sonje lè nou
di lis lye pa kapab rechèch binè?
Nou ap kalite kreye yon estrikti done ki ke trik nouvèl ki an ap travay.
>> E li bay lis sa paske lye yo lineyè, yo te sèlman lyen youn apre lòt la.
Nou ka kalite gen diferan sòt de endikasyon
ki pwen nan nœuds diferan ki ka ede nou ak rechèch.
Se konsa, isit la, si mwen te vle gen yon pye bwa rechèch binè,
Mwen konnen ke mitan mwen si 55.
Mwen jis ale nan kreye ki kòm mwayen mwen, kòm rasin mwen,
ak Lè sa a, mwen pral gen valè vire koupe nan li.
>> Se konsa, isit la, si mwen pral pou fè rechèch pou valè a nan 66, mwen ka kòmanse nan 55.
Li nan 66 pi gran pase 55?
Wi li se, se konsa mwen konnen mwen MUS rechèch m n konsèy nan dwa nan pye bwa sa a.
M 'ale nan 77.
OK, se 66 mwens pase oswa pi gran pase 77?
Li nan pi piti pase, se konsa ou konnen, o, ki gen yo dwe ne nan kite.
>> Se konsa, isit la nou ap kalite prezève tout nan anpil bèl bagay yo sou ranje,
se konsa tankou dinamik rèsizin nan objè, yo te
kapab Insert ak efase nan volonte, san yo pa gen enkyete sou fiks nan
kantite lajan pou espas.
Nou toujou prezève tout nan bagay sa yo bèl bagay
pandan y ap tou ke yo te kapab prezève a ouvri sesyon ak rechèch lè nan rechèch binè
ke nou te sèlman te deja kapab jwenn yon fraz.
>> Cool done estrikti, kalite konplèks aplike, ne la.
Kòm ou ka wè, tout li se struct a nan ne la
se ke ou gen yon bò gòch ak yon konsèy dwat.
Sa a tout li ye.
Se konsa, olye ke sèlman gen yon x oswa yon anvan yo.
Ou gen yon bò gòch oswa yon dwa, ak Lè sa a ou ka kalite lyen yo ansanm
sepandan ou se konsa chwazi.
>> OK, nou ap aktyèlman pral jis pran yon kèk minit.
Se konsa, nou ap ale nan ale tounen isit la.
Kòm mwen te di deja, Mwen kalite eksplike
lojik la dèyè ki jan nou ta rechèch nan sa a.
Nou pral eseye pseudocoding soti sa a yo wè
si nou ka aplike nan kalite menm lojik nan rechèch binè
nan yon kalite diferan nan estrikti done.
Si ou nèg vle pran tankou yon koup minit nan jis panse sou sa a.
OK.
Tout dwa, mwen pral aktyèlman jis ba ou the-- pa gen okenn,
nou pral pale sou pseudocode a an premye.
Se konsa, nenpòt moun ki vle bay yon koud nan sa ki
premye bagay la ou vle fè lè w ap kòmanse soti chache se?
Si nou ap chèche pou valè a nan 66, sa ki nan
premye bagay la nou vle fè si nou vle rechèch binè pye bwa sa a?
>> ODYANS: Ou vle gade dwat epi gade bò gòch ak wè [fèbl]
pi gwo kantite.
>> Andi Peng: Yeah, egzakteman.
Se konsa, w ap ale nan gade nan rasin ou yo.
Genyen anpil bagay nan fason ou ka rele li, moun ki ne paran ou yo di.
Mwen renmen di rasin paske sa a, se tankou rasin lan nan pyebwa sa a.
W ap ale nan gade nan ne rasin ou, epi w ap
pral wè se 66 pi gwo pase oswa mwens pase 55.
Men, si li la pi gran pase, byen, li se pi gran pase, kote nou vle gade?
Ki kote fè nou vle fè rechèch kounye a, dwa?
Nou vle fè rechèch la dwat mwatye nan pye bwa sa a.
>> Se konsa, nou gen, yon bon, yon konsèy ki pwen a dwat la.
Se konsa, lè sa a nou ka mete rasin nouvo nou an yo dwe 77.
Nou ka jis ale nan tout kote konsèy la ap montre.
Oke, oh, isit la nou ap kòmanse a 77, epi nou ka jis
fè sa recursive ankò e ankò.
Nan fason sa a, ou kalite a gen yon fonksyon.
Ou gen yon fason pou chèche ke ou ka jis repete sou yo ak sou yo ak sou,
tou depann de ki kote ou vle gade jiskaske ou evantyèlman jwenn nan valè a
ke w ap chèche pou.
Fè sans?
>> Mwen se sou yo montre w aktyèl la kòd, ak li nan yon anpil nan kòd.
Pa bezwen sovaj deyò.
Nou pral pale atravè li.
>> Aktyèlman, pa gen okenn.
Sa ki te jis pseudocode.
OK, sa ki te jis pseudocode a, ki se yon konplèks ti jan,
men li la totalman amann.
Tout moun sa yo ansanm isit la?
Si rasin lan se nil, retounen fo paske sa vle di
ou pa menm gen anyen la.
>> Si n rasin se valè a, se konsa si li k ap pase yo yon sèl la w ap chèche a,
Lè sa a, w ap ale nan retounen vre paske ou konnen ou te jwenn li.
Men, si valè a ki pi piti a pase rasin nan n, ou se
ale nan rechèch bò gòch la timoun oswa fèy la gòch,
tou sa ou vle yo rele li.
Men, si valè a gen plis pouvwa pase rasin, w ap ale nan rechèch pye bwa a dwat,
Lè sa a, jis kouri fonksyon an a rechèch ankò.
>> Men, si rasin se nil, ki ki vle di ou te rive nan fen a?
Sa vle di ou pa gen okenn plis plis fèy nan rechèch,
Lè sa a, ou konnen, oh, mwen devine li pa nan isit la
paske apre mwen te gade nan tout bagay la epi li pa isit la,
li jis pa ta kapab isit la.
>> Ki fè sans nan tout moun?
Se konsa, li tankou rechèch binè prezève kapasite yo nan lis lye.
Cool, e konsa kalite a dezyèm nan done estrikti ou nèg
ka eseye mete ann aplikasyon sou pset ou, ou sèlman gen yo chwazi yon metòd.
Men, petèt yon metòd altènativ a tab la regle se sa nou rele yon trye.
>> Tout yon trye se se yon kalite espesifik nan pye bwa ki
gen valè ki ale nan lòt valè.
Se konsa, olye pou yo gen yon binè pyebwa ki nan sans ke sèlman yon sèl
bagay ka lonje dwèt sou de, ou ka gen pwen yon sèl bagay yo anpil, anpil bagay sa yo.
Ou esansyèlman gen ranje andedan nan yo ki ou sere
endikasyon ki lonje dwèt sou lòt ranje.
>> Se konsa, ne a nan ki jan nou ta defini yon trye
se nou vle gen yon Boolean, mo c, dwa?
Se konsa, ne a se Boolean tankou vre oubyen fo,
premye a tout moun nan plas tèt la nan ki etalaj, se sa a yon mo?
Dezyèmman, ou vle gen endikasyon mèt fè tout sa rès la nan yo se.
Yon konplèks ti jan, yon abstrè ti jan, men Mwen pral eksplike tout sa ki vle di.
>> Se konsa, isit la, nan tèt la, si ou gen yon etalaj deklare deja,
yon ne kote ou gen yon Boolean valè ki estoke nan devan an
ki di ou se sa a yon mo?
Èske sa se pa di yon mo?
Lè sa a, ou gen nan rès nan etalaj ou a, ki
aktyèlman estoke tout nan posiblite nan sa ki li te kapab fè.
Se konsa, pou egzanp, tankou nan tèt la ou gen
premye bagay la ki di vre oubyen fo, repons lan se wi oswa ki pa gen, sa a se yon mo.
>> Lè sa a, ou gen 0 a 26 nan lèt yo ke ou ka magazen.
Si m 'te vle fè rechèch isit la pou baton, m 'ale nan tèt la
ak mwen gade pou B. Mwen jwenn B a nan yon m ' etalaj, Se poutèt sa mwen konnen, OK, se B yon mo?
B se pa di yon mo, se konsa konsa Mwen dwe kenbe chache.
M 'ale soti nan B, ak mwen gade nan an konsèy ki B pwen nan direksyon pou
ak mwen wè yon lòt etalaj de enfòmasyon, estrikti nan menm ke nou te anvan.
>> Apre sa, isit lan-- oh, pwochen an lèt nan [fèbl] se A.
Se konsa, nou gade nan ki etalaj.
Nou jwenn valè a wityèm, ak Lè sa a nou gade yo wè, oh,
hey, se ke yon mo, se B-A yon mo?
Li se pa yon mo.
Nou te gen kenbe kap.
>> Se konsa, Lè sa a, nou gade nan kote konsèy la nan A pwen,
epi li lonje dwèt nan yon lòt fason nan ki nou gen plis valè ki estoke.
Apre sa, evantyèlman, nou jwenn yo B-A-T, ki se yon mo.
Se konsa, lè a pwochen ou gade, w ap ale
gen ke chèk nan, se wi, fonksyon sa a Boolean se verite.
Se konsa, nan sans nou ap kalite ki gen yon pye bwa ak ranje.
>> Se konsa, Lè sa a, ou ka kalite rechèch desann.
Olye ke achin yon fonksyon ak plase valè pa lis lye,
ou ka jis aplike yon trye ki fouy downwords.
Reyèlman, reyèlman konplike bagay.
Pa fasil yo reflechi sou paske mwen se tankou voye krache done anpil estrikti soti
nan ou, men fè sa ki tout moun kalite konprann ki jan lojik nan sa a ap travay?
>> OK, fre.
Se konsa, B-A-T, ak Lè sa a w ap ale nan rechèch.
Tan nan pwochen w ap ale yo wè, oh, hey, li nan vre,
konsa mwen konnen sa a dwe yon mo.
>> Menm bagay pou zou.
Se konsa, isit la nan bagay la kounye a, si nou te vle pou fè rechèch pou zou, kounye a,
kounye a zou a se pa yon mo nan diksyonè nou an
paske, jan ou nèg ka wè a, premye plas ke nou gen yon Boolean
retounen vre se nan fen rale.
Nou gen Z-O-O-M.
>> Se konsa, isit la, nou pa gen aktyèlman pawòl Bondye a, zou, nan diksyonè nou an
paske bwat chèk sa a pa w tcheke yo.
Se konsa, òdinatè a pa fè sa konnen ke zou se yon mo
paske wout la ke nou te estoke li, se sèlman yon rale isit la
aktyèlman te gen yon valè Boolean sa a te tounen vre.
Se konsa, si nou vle insert nan mo, zou, nan diksyonè nou an,
ki jan nou ta ale sou fè sa?
Ki sa nou gen pou fè pou asire w nou an òdinatè konnen ke Z-O-O se yon mo
epi yo pa pawòl Bondye a premye se Z-O-O-M?
>> ODYANS: [fèbl]
>> Andi Peng: Egzakteman, nou vle asire w ke sa a
isit la, ke valè Boolean se tcheke nan ke li nan vre.
Z-O-O, lè sa a nou ap ale nan tcheke sa, se konsa nou konnen egzakteman, hey, zou se yon mo.
Mwen pral di la òdinatè ke li nan yon mo se konsa
ke lè chèk yo òdinatè, li konnen ke zou se yon mo.
>> Paske sonje tout done sa yo estrikti, li trè fasil pou nou
vle di, oh, baton nan yon mo.
Zou a yon mo.
Zoom nan yon mo.
Men, lè w ap bati li, òdinatè a pa gen okenn lide.
>> Se konsa, ou oblije di li egzakteman nan pwen sa se sa a yon mo?
Nan ki pwen se li pa di yon mo?
Apre sa, nan sa ki pwen mwen bezwen nan rechèch bagay sa yo,
ak nan sa ki pwen mwen bezwen ale kap vini yo?
Tout moun klè nan sa?
Fre.
>> Se konsa, Lè sa a, vini nan pwoblèm nan ki jan ta nou
ale sou mete yon bagay sa a, se aktyèlman pa genyen?
Se konsa, kite yo jis di nou vle insert pawòl Bondye a, benyen, nan trye nou an.
Kòm ou nèg ka wè tankou kounye a tout sa nou gen koulye a, se B-A-T,
ak sa a nouvo done estrikti gen te gen yon pent ki
pwente nan nil paske nou sipoze ki, o, gen nan pa gen mo apre B-A-T,
poukisa nou bezwen kenbe gen bagay apre sa T.
>> Men, pwoblèm nan rive si nou fè ou vle gen yon mo ki vin apre
T a.
Si ou gen benyen, w ap ale nan vle yon H dwat.
Se konsa, wout la nou ap ale nan fè sa se nou ap ale nan kreye yon ne ki apa a.
Nou pa ap lote tou sa kantite lajan nan memwa pou sa a etalaj nouvo,
epi nou ap ale nan mute endikasyon.
>> Nou pral bay nan H, Premye a tout, nil sa a,
nou ap ale nan debarase m de.
Nou ap ale nan gen H pwen bès yo.
Si nou wè yon H, nou vle li pou yo ale nan yon lòt kote.
>> Nan isit la, nou ka Lè sa a tcheke nan wi.
Si nou frape yon H apre T a, oh, Lè sa a, nou konnen ke sa a se yon mo.
Boolean a ki pral retounen vre.
Tout moun klè sou kòman sa ki te rive?
OK.
>> Se konsa, esansyèlman, nan tout sa yo estrikti done
ke nou te ale sou jodi a, mwen te ale sou yo reyèlman, reyèlman byen vit
epi yo pa nan nan anpil detay, e ke sa a OK.
Yon fwa ou kòmanse pitye ak li, ou pral
kenbe tras nan kote tout endikasyon yo se,
sa k ap pase nan ou estrikti done, et setra.
Yo pral trè itil, ak li a jiska ou
mesye totalman konnen ki jan ou vle aplike bagay sa yo.
>> Se konsa, pset4, nan 5-- oh, se sa ki mal.
PSET5 se Misspellings.
Kòm mwen te di anvan, w ap ale nan, yon fwa ankò, download kòd sous nan men nou.
Gen k ap pase yo dwe twa prensipal bagay ou pral Téléchargez.
Ou ap download diksyonè, Kers, ak tèks.
>> Tout bagay sa yo sa yo se yo swa diksyonè nan mo
ke nou vle ou yo tcheke oswa egzamen sou enfòmasyon
ke nou vle ou eple chèk la.
Se konsa, diksyonè yo nou ba ou yo ale
l 'ban nou pawòl aktyèl ke nou vle ou nan magazen yon jan kanmenm nan yon fason sa a, se
pi efikas pase yon etalaj.
Lè sa a, tèks yo yo se pral fè sa nou ap
mande w eple tcheke a asire w tout nan mo sa yo gen pawòl reyèl.
>> Se konsa, twa blòk yo nan pwogram ki nou pral ba ou
yo rele dictionary.c, dictionary.h, ak speller.c.
Se konsa, tout dictionary.c fè se ki sa w ap mande yo aplike.
Li charj mo yo.
Li eple chèk yo, epi li fè asire w ke tout bagay se eleman byen.
>> diction.h se jis yon dosye bibliyotèk ki deklare tout moun sa yo fonksyon.
Apre sa, speller.c, nou ap ale nan ba ou.
Ou pa bezwen modifye nenpòt nan li.
Tout speller.c se pran sa, charj li, chèk vitès la nan li,
tès referans a tankou ki jan byen vit w ap kapab fè bagay sa yo.
>> Li se yon ortograf.
Jis pa fè sa dezòd ak li, men asire w ke ou konprann ki sa li la fè a.
Nou itilize yon fonksyon rele getrusage ki tès pèfòmans nan période ou
korektè.
Tout li fè sa se fondamantalman teste nan lè nan tout bagay nan diksyonè ou a,
se konsa asire w ke ou konprann li.
Fè atansyon pa dezòd ak li oswa bagay lòt moun pa pral kouri byen.
>> Apre sa, èstime nan defi sa a se pou ou nèg reyèlman modifye dictionary.c.
Nou pral ba ou 140,000 mo nan yon diksyonè.
Nou pral ba ou yon tèks dosye ki gen pawòl sa yo,
e nou vle ou yo dwe kapab òganize yo nan yon tab regle oswa yon trye
paske lè nou mande w eple check-- imajine si w ap eple
tcheke tankou Odyssey Homer a.
Se tankou sa a gwo, gwo egzamen an.
>> Imajine si chak yon sèl mo ou te gen fè yon gade
nan yon etalaj de 140,000 valè.
Sa ta pran pou tout tan pou machin ou a kouri.
Se pou rezon sa nou vle yo òganize nou an done nan estrikti done pi efikas
tankou yon tab regle oswa yon trye.
Lè sa a, ou nèg ka kalite a lè ou rechèch aksè
bagay ki pi fasil ak pi vit.
>> Se konsa, dwe fè atansyon yo rezoud kolizyon.
W ap ale nan jwenn yon pakèt moun nan mo a ki kòmanse ak A.
W ap ale nan jwenn yon pakèt moun mo ki kòmanse ak B. Jiska ou
mesye ki jan ou vle rezoud li.
Petèt gen nan plis fonksyon regle efikas
pase jis premye lèt nan yon bagay, e konsa sa a, se jiska ou
mesye kalite fè tou sa ou vle.
>> Petèt ou vle ajoute tout lèt yo ansanm.
Petèt ou vle fè bagay sa yo etranj renmen nan kont ki kantite lèt,
kèlkeswa sa.
Jiska ou nèg ki jan ou vle yo fè.
Si ou vle fè yon tab regle, si ou vle eseye yon trye, totalman jiska ou.
Mwen pral avèti ou devan yo nan tan an ki trye se tipikman yon ti jan pi difisil
jis paske gen nan yon anpil plis endikasyon nan kenbe tras nan.
Men, totalman jiska ou guys.
Li nan byen lwen plis efikas nan pifò ka.
Ou vle reyèlman kapab kenbe tras nan tout nan endikasyon ou yo.
Fè tankou fè menm bagay la ke mwen te fè isit la.
Lè w ap eseye insert valè nan yon tab regle ou efase,
asire w ke w ap reyèlman kenbe tras
a kote tout bagay se paske li vrèman fasil pou si mwen
ap eseye insert tankou pawòl Bondye a, Andy.
Se pou nou jis di ke sa a yon reyèl mo, pawòl Bondye a, Andy,
nan yon lis jeyan nan Yon mo yo.
>> Si m 'jis rive mute yon mal konsèy, Wouch,
gen ale antye a nan rès la nan lis lye m 'yo.
Koulye a, pawòl Bondye a sèlman mwen genyen se Andy, epi kounye a
tout nan lòt mo yo nan la diksyonè yo te pèdi.
Se konsa, ou vle asire w ke ou kenbe tras nan tout nan endikasyon ou
oswa lòt moun ou ap ale nan jwenn pwoblèm gwo nan kòd ou a.
Trase bagay sa yo soti ak anpil atansyon etap pa etap.
Li fè li yon anpil pi fasil yo panse a.
>> Epi anfen, ou vle pou kapab tès pèfòmans ou nan pwogram ou an
sou tablo a gwo.
Si ou nèg pran yon gade nan CS50 kounye a,
nou gen sa ki rele tablo a gwo.
Li se fèy la pwen de pi rapid la eple tcheke fwa atravè tout nan CS50
kounye a, mwen panse ke tèt la tankou 10 fwa mwen panse ke uit nan yo se anplwaye yo.
Nou vrèman vle ou nèg yo bat nou.
>> Tout moun nan nou t ap eseye aplike Kòd ki pi rapid ke posib.
Nou vle ou nèg pou yo eseye defi nou epi mete an aplikasyon pi vit pase tout moun nan nou
kapab.
Se konsa, sa a se reyèlman premye fwa a ke nou ap
mande ou nèg fè yon pset ki ou ka reyèlman fè tou sa metòd an
ou vle.
>> Mwen toujou di, sa a se pi plis analogue nan yon solisyon lavi reyèl, dwa?
M 'ap di, hey, mwen bezwen ou fè sa a.
Bati yon pwogram ki fè bagay sa a pou mwen.
Fè l 'sepandan ou vle.
Mwen jis konnen ke mwen vle fè jèn.
Sa a defi ou pou semèn sa a.
Ou nèg, nou ap ale l 'ban nou yon travay.
Nou pral ba ou yon defi.
Lè sa a, li a jiska ou nèg konplètman jis konnen
sa ki nan pi rapid la ak pi fason efikas aplike sa a.
Yeah?
>> ODYANS: Èske nou pèmèt yo si te vle fè rechèch sou pi vit fason
fè tab regle sou entènèt, nou ka fè sa ki epi site Kòd yon lòt moun nan?
Andi Peng: Yeah, totalman amann.
Se konsa, si ou nèg li a espèk, gen nan yon liy
nan espèk a ki di ou nèg se totalman lib fè rechèch sou regle
fonksyon sou sa ki yo se kèk nan fonksyon yo regle pi vit
nan kouri bagay sa yo nan kòm lontan ke ou site ki kòd.
Se konsa, gen kèk moun ki te deja kalkile konnen fason vit
pou fè dam période, nan vit fason pou estoke enfòmasyon.
Totalman jiska ou nèg si ou vle jis pran ki, dwa?
Pou pi si w ap site.
Defi a isit la reyèlman ke nou ap ap eseye teste
se fè si ke ou konnen wout ou ozalantou endikasyon.
Osi lwen ke ou mete ann aplikasyon fonksyon an regle aktyèl
ak vini ak tankou matematik la fè sa,
ou nèg ka rechèch sou tou sa metòd sou entènèt ou nèg vle.
Yeah?
>> ODYANS: Èske nou ka site jis lè l sèvi avèk [fèbl a]?
>> Andi Peng: Yeah.
Ou ka jis, nan kòmantè ou, ou ka site tankou, oh,
te pran nan men Yada, Yada, Yada, fonksyon regle.
Nenpòt moun ki gen nenpòt kesyon?
Nou aktyèlman breezed nan seksyon jodi a.
Mwen pral moute la a yo reponn kesyon yo tou.
>> Epitou, jan mwen te di, biwo èdtan aswè a ak demen.
Espèk nan semèn sa a se aktyèlman super fasil ak super kout li.
Mwen ta sijere pran yon gade, jis li nan antye a nan li.
>> Apre sa, Zamyla aktyèlman mache ou nan chak nan fonksyon yo
ou bezwen aplike, e konsa li a trè, trè klè ki jan fè tout bagay.
Jis asire w ke ou ap kenbe tras nan pwent.
Sa a se yon pset trè difisil.
>> Li pa nan defi paske tankou, oh, konsèp yo yo, se pou pi plis
difisil, oswa ou gen yo aprann anpil nouvo sentaks wout la
ke ou te fè pou dènye pset la.
Pset Sa a se difisil paske gen anpil endikasyon,
ak Lè sa a li a trè, trè fasil yo yon fwa ou gen yon ensèk nan kòd ou a pa kapab
jwenn kote ki ensèk se.
>> Se konsa, nèt sou tout pwen ak lafwa nan ou prononcée mesye yo dwe kapab bat nou an [fèbl]
òtograf.
Mwen gen aktyèlman pa nenpòt m ekri ankò, men mwen se sou yo ekri mwen yo ye.
Se konsa, pandan w ap ekri pou ou, mwen pral ekri mwen yo ye.
Mwen pral pou yo eseye fè m pi vit pase ou.
Nou pral wè ki moun ki gen yon sèl ki pi rapid.
>> Apre sa, yeah, mwen pral wè tout nan ou nèg isit la nan Madi.
Mwen pral kouri yon kalite tankou yon atelye pset.
Tout moun nan seksyon yo ki sa a semèn yo atelye pset,
se konsa ou nèg gen anpil bagay nan opòtinite pou èd, lè biwo tankou toujou,
ak Mwen vrèman gade pou pi devan pou lekti tout nan kòd mesye ou a.
Mwen gen ti tès moute isit la si ou mesye vle vin jwenn sa yo.
Sa a tout.