[Powered by Google Translate] [Ġimgħa 6]
[David J. Malan] [Università ta 'Harvard]
[Dan huwa CS50.] [CS50.TV]
>> Dan huwa CS50, u dan huwa l-bidu tal-Ġimgħa 6,
hekk koppja ta 'għodod ġodda issa huma disponibbli għalik biex jieħdu vantaġġ minn,
l-ewwel waħda minnhom huwa msejjaħ CS50 Style.
Odds huma jekk int simili me jew kwalunkwe mill-fellows tagħlim,
inti stajt probabbilment jidhru programm li stil jistenna ftit xi ħaġa bħal din.
Forsi inti tibda qtugħ xi kantunieri tard bil-lejl, jew tkun taf jittrattaw dan aktar tard,
u mbagħad TF jew CA jidħol fuq matul ħinijiet tal-uffiċċju.
Imbagħad huwa diffiċli għalina biex jinqara.
Ukoll, din il-kodiċi huwa sintattikament korrett, u se tiġbor, u se tmexxi effettivament.
Iżda huwa definittivament mhux 5 għall-istil.
>> Imma issa, jekk immorru fis dan id-direttorju hawn 'il
u tinnota li għandi conditions2.c-
u I run dan il-kmand ġdid, style50, fuq din conditions2.c fajl, Ikteb,
avviż li huwa infurmani li kien stilizzata.
Gedit ndunat li l-fajl ġie mibdul fuq diska,
u jekk I ikklikkja jerġgħu jitgħabbew, il-problemi kollha tiegħek huma issa awtomatizzati.
[Applause]
Dik hija waħda mill-affarijiet għamilna dan il-weekend.
Jirrealizzaw li huwa imperfett minħabba li hemm xi kodiċi
li sempliċement mhux se tkun kapaċi li stylize perfettament,
imma tirrealizza dan huwa issa għodda inti tista 'tieħu vantaġġ ta'
jekk biss biex tiċċara xi wħud mill-ċineg kaboċċi aktar errantly mqiegħda u simili.
>> Iżda aktar konvinċenti issa huwa CS50 Iċċekkja.
Bil CS50 Iċċekkja, inti tista 'attwalment twettaq it-testijiet korrettezza istess
fuq kodiċi tiegħek stess li l-inkarigati mir tagħlim huma kapaċi.
Dan huwa utilità linja tal-kmand li taqa issa fl-appliance
hekk kif inti tagħmel update50 bħala kull
pset 4 ispeċifikazzjonijiet, u inti tużaha essenzjalment bħal dan.
Inti tmexxi l-check50 kmand.
Imbagħad inti tgħaddi fil argument linja tal-kmand, jew aktar ġeneralment magħrufa bħala swiċċ jew tal-bandiera.
Ġeneralment, l-affarijiet li għandhom b'sinkijiet huma msejħa 'swiċċ
għal programm linja tal-kmand, hekk c jispeċifika
il-kontrolli li inti tixtieq li jiddekorri.
>> It-testijiet li inti tixtieq li jiddekorri huma identifikati unikament minn din spag,
2012/pset4/resize.
Fi kliem ieħor, li jinsab biss string arbitrarja iżda uniku
li nużaw biex jidentifika unikament testijiet korrettezza 4 pset s.
U allura inti tispeċifika lista spazju separata tal-fajls li inti tixtieq li upload
li CS50 Iċċekkja għall-analiżi.
Per eżempju, jekk immur fis-soluzzjoni tiegħi hawn għall resize.c-
let me tiftaħ terminal akbar tieqa
u I jimxi 'l quddiem u run ejja ngħidu check50-c 2012/pset4/resize,
u mbagħad I jimxi 'l quddiem u jispeċifika l-ismijiet tal-fajls,
resize.c, u mbagħad hit Ikteb, huwa Kompressi,
hija uploads, hija għandha tivverifika, u I biss naqset mazz sħiħ ta 'testijiet.
Il-waħda bl-aħmar fuq quċċata xellug jgħid li resize.c u BMP jeżistu.
Dan kien it-test. Dan kien il-kwistjoni staqsejna.
U huwa kuntent għaliex it-tweġiba kienet falza.
It-test abjad taħt jgħid mistenni bmp.h teżisti, u li sempliċiment tort tiegħi.
I nesa li upload, so I bżonn biex ittella żewġ fajls,
resize.c u bmp.h.
Imma issa avviż-testijiet kollha l-oħra huma sofor għaliex ikunu għadhom ma run,
u għalhekk il-wiċċ smiley hija vertikali għaliex huwa la kuntenti lanqas imdejjaq,
imma rridu rimedju din il-kwistjoni fl-aħmar qabel dawn il-kontrolli l-oħra se jibqa 'għaddej.
>> Let me jiffissaw dan.
Let me zoom out u terġa 'ssir din, din id-darba ma' bmp.h wkoll
fuq il-linja tal-kmand, Ikteb, u issa jekk kollox imur sew,
li għaddej biex jiċċekkjaw u mbagħad tirritorna riżultat ta 'l-istiva tiegħek nifs
kollha aħdar, li jfisser li qed nagħmel verament tajjeb fuq pset 4 s'issa.
Tista 'tara u jiddeduċu mit-test deskrittiv hawn
eżattament dak li huwa aħna ttestjati.
Aħna ttestjati 1 ma l-fajls jeżistu?
Aħna mbagħad ittestjati ma jikkompilaw resize.c?
Imbagħad aħna ttestjati ma jkunx resize a BMP 1x1-pixel meta n, il-fattur resize, hija l-1.
Issa, jekk għandek l-ebda idea dak li n huwa, inti ser ladarba inti adsa fis pset 4,
iżda li sempliċiment huwa sanità jivverifika sabiex ikun żgur li int mhux resizing
immaġni fil-livelli kollha jekk il-fattur resize huwa 1.
Jekk, għall-kuntrarju, hija resizes pixel 1x1 għal BMP pixel 1x1 2x2 lill korrett
meta n hija 2, imbagħad bl-istess mod, minjiera jifforma xieraq.
>> Fil-qosor, dan huwa maħsub biex, wieħed, jieħu l-qsim-swaba
barra mill-ekwazzjoni dritt qabel ma tissottometti pset tiegħek.
Inti se tkun taf eżattament liema TF tiegħek dalwaqt se tkun taf
meta inti tmur dwar sottomissjoni xi wħud minn dawn is-settijiet problema,
u wkoll il-motivazzjoni pedagoġika huwa verament li tpoġġi
l-opportunità fuq quddiem tal inti hekk li meta inti taf a priori
li hemm bugs fil-kodiċi tiegħek u testijiet li mhumiex jiġu mgħoddija,
inti tista 'tpoġġi fil-ħin effettiv aktar bil-quddiem biex isolvu dawn il-problemi
aktar milli jitilfu punti, jiksbu rispons mill-TF tiegħek,
u mbagħad mur, "Ahh," bħal I għandu jkollhom dehret li out.
Issa mill-inqas hemm għodda biex jgħinek issib li.
Mhuwiex ser tfakkar meta l-bug hija, iżda se jgħidlek
dak li huwa sintomatiku ta 'dan.
>> Issa jirrealizzaw it-testijiet mhumiex neċessarjament eżawrjenti.
Sempliċiment għax ikollok full screen ta 'uċuħ smiley aħdar
ma jfissirx kodiċi tiegħek hija perfetta, iżda dan ma jfissirx
li jkun għadda ċertu testijiet preskritti mil-spec.
Kultant aħna mhux se rilaxx kontrolli.
Per eżempju, whodunit, wieħed mill-aspetti ta 'pset 4,
huwa tip ta 'diżappunt jekk aħna nagħtuk
ir-risposta dwar dak li hi, u hemm numru ta 'modi biex jikxfu
li l-persuna hija fil dak l-istorbju aħmar.
Il spec dejjem se tispeċifika fil-futur għall-pset 5 onward
dak kontrolli jeżistu għalik.
Int ser ikollok avviż hemm dan il-URL abjad fil-qiegħ.
Għal issa, dan huwa biss l-output dijanjostiku.
Jekk inti żżur dan URL, int ser tingħata mazz sħiħ ta 'crazy, messaġġi cryptic
li inti qed jilqgħu biex tfittex permezz ta ', imma hija l-aktar għall-persunal
sabiex inkunu nistgħu djanjosi u debug bugs fil check50 innifsu.
>> Mingħajr dewmien, ejja jimxu fuq fejn aħna jitħalla 'off.
CS50 librerija ħadna għall mogħtija għal xi ġimgħat,
iżda mbagħad ġimgħa li għaddiet, bdejna tqaxxir lura waħda mill-saffi ta 'dan.
Bdejna jitwarrbu sensiela favur dak minflok?
[Studenti] Char.
* Char, li kien * char dan il-ħin,
iżda issa aħna ma jkollhomx biex nippretendu li huwa ta 'sekwenza attwali tip tad-data.
Pjuttost, huwa kien sinonimu ta 'tip għal * char,
u string hija sekwenza ta 'karattri,
hekk għaliex ma jagħmilx sens li jirrappreżentaw kordi bħala * char s?
Xi jfisser * char jirrappreżentaw fil-kuntest ta 'dan il-kunċett ta' sekwenza?
Yeah. >> [Student] L-ewwel karattru.
Tajba, l-ewwel karattru, iżda pjuttost mhux l-ewwel karattru.
Huwa the-[istudenti] Indirizz.
Tajba, l-indirizz ta 'l-ewwel karattru.
Kollha li huwa meħtieġ biex jirrappreżentaw string fil-memorja tal-kompjuter
huwa biss l-indirizz unika ta 'byte ewwel tagħha.
Inti ma għandekx tkun taf kemm żmien huwa
għaliex kif inti tista figura li out dinamiku?
[Student] tul String.
Tista 'sejħa tul string, eċċellenti, imma kif jaħdem tul string?
X'tikkontrolla do? Yeah.
[Student] Żomm għaddejjin sakemm ikollok l-karattru null.
Yeah, eżattament, hija biss ttenni ma 'għall-loop, filwaqt loop,
kwalunkwe minn * sa l-aħħar, u l-aħħar huwa rappreżentat
billi \ 0, il-karattru hekk imsejħa Nul, Nul,
ma tridx tiġi konfuża ma 'null, li huwa pointer,
li se toħroġ fil-konverżazzjoni mill-ġdid illum.
>> Aħna imqaxxar lura saff ta 'GetInt, u mbagħad aħna ħa ħarsa lejn GetString,
u jfakkru li kemm ta 'dawk il-funzjonijiet, jew verament,
GetString, kien bl-użu ta 'funzjoni partikolari
li fil-fatt parse, jiġifieri, taqra jew tanalizza, input l-utent.
U dak li kien dik il-funzjoni l-ġdida?
Scanf jew sscanf. Hija fil-fatt taqa 'fi togħmiet differenti ftit.
Hemm scanf, hemm sscanf, hemm fscanf.
Għal issa, għalkemm, ejja tiffoka fuq l-aktar wieħed faċli illustrati,
u let me jimxi 'l quddiem u tiftaħ fl-appliance
fajl bħal dan, scanf1.c.
Dan huwa programm sempliċi super,
iżda li ma xi ħaġa li aħna stajt qatt sar
mingħajr l-għajnuna tal-librerija CS50.
Dan gets int minn utent. Kif taħdem?
Ukoll, fil-linja 16 hemmhekk,
avviż li aħna tiddikjara x int imsejħa, u f'dan il-punt fl-istorja,
dak li huwa l-valur ta 'x?
[Rispons istudent inaudible]
[David M.] Dritt, li jaf, xi valur żibel potenzjalment, hekk 17, aħna biss tell-utent
tagħti me numru, jekk jogħġbok, u l-pass 18 huwa fejn jiġrilha interessanti.
Scanf jidher li jissellef idea minn printf fis-sens li tuża dawn il-kodiċijiet format fil-kwotazzjonijiet.
D% huwa ta 'kors numru deċimali.
Iżda għaliex jien tgħaddi fl & x minflok ftit x?
L-ewwel hija korretta. Yeah.
[Rispons istudent inaudible]
Eżattament, jekk l-għan ta 'dan il-programm, bħall-GetInt funzjoni hija stess,
huwa biex tikseb int mill-utent I jista 'jgħaddi l-funzjonijiet
il-varjabbli kollha nixtieq, imma jekk jien ma jgħaddihom b'referenza
jew minn l-indirizz jew minn pointer, kollha sinonimu għal skopijiet tal-lum,
allura dik il-funzjoni għandha l-ebda abbiltà li jibdlu l-kontenut ta 'din varjabbli.
Dan se jgħaddi f'kopja bħad-verżjoni Buggy ta swap
li konna tkellimna dwar għal xi ftit drabi issa.
>> Iżda minflok, billi tagħmel & x, jien litteralment jgħaddi fil liema?
[Student] L-indirizz. >> L-indirizz ta 'x.
Huwa simili tpinġija ta 'mappa għall-funzjoni msejħa scanf u qal hawn,
dawn huma direzzjonijiet għal blokki ta 'memorja fil-kompjuter
li inti tista 'tmur taħżen xi numru sħiħ pulzieri
Sabiex sscanf li issa jagħmlu dan
dak l-operatur, liema biċċa ta 'sintassi huwa se jkollhom jużaw
anke jekk aħna ma tistax tara għaliex xi ħadd ieħor kiteb din il-funzjoni?
Fi kliem ieħor - dak li?
[Student] X jinqara.
Hemm għaddej biex tkun xi qari, iżda biss fir-rigward x hawnhekk.
Jekk scanf qed għadda l-indirizz ta 'x,
sintattiku, liema operatur huwa marbut li jeżisti x'imkien
ġewwa ta 'l-implimentazzjoni scanf hekk li scanf
jistgħu attwalment tikteb numru 2 ta 'dak l-indirizz?
Yeah, sabiex il-*.
Ifakkar li l-* huwa dereference operatur tagħna, li essenzjalment ifisser jmorru hemm.
>> Ladarba inti ħadthom ġiet mogħtija l-indirizz, kif inhu l-każ hawnhekk,
scanf huwa probabbilment-jekk irridu verament stenna madwar sors tagħha ta 'code-
qed tagħmel * x jew l-ekwivalenti li fil-fatt tmur f'dak l-indirizz u jqajjem xi valur hemmhekk.
Issa, kif dwar kif scanf gets input mill-tastiera,
aħna ser mewġa idejn tagħna out għal-lum.
Just wieħed jassumi li s-sistema operattiva jippermetti sscanf biex jitkellmu
lill keyboard 'l-utent, imma f'dan il-punt issa fil-linja 19,
meta aħna sempliċiment jistampa x, jidher li jkun il-każ
li scanf poġġa l int fil x.
Li eżattament kif taħdem scanf, u tfakkar ġimgħa li għaddiet
dan huwa eżattament kif GetString u GetInt u l-familja l-oħra tal-funzjonijiet tagħha
finalment xogħlijiet, għalkemm varjazzjoni żgħira bħal sscanf,
li jfisser scan sensiela minflok il-keyboard.
Iżda ejja tagħti ħarsa lejn varjanza ftit ta 'dan.
Fil scanf2, I attwalment invitat up.
Dak li hu ħażin u jien ser jaħbu l-kumment li jispjega kemm-
dak li hu ħażin ma 'dan il-programm, verżjoni 2?
Jkun teknika possibbli f'dan il-ħin.
Huwa jistenna pretty tajba.
Huwa nicely inċiża, imma-
okay, kif madwar ejja prune l-isfel għall-mistoqsijiet iqsar?
Linja 16. X'hemm linja 16 tagħmel bl-Ingliż preċiż iżda teknika?
Getting ftit skomdi. Iva, Michael.
[Istudenti] Huwa tipponta lejn l-ewwel ittra ta 'sekwenza.
>> Okay, qrib. Let me tweak li ftit.
Li tipponta lejn l-ewwel ittra ta 'spag, inti tiddikjara buffer varjabbli imsejjaħ
li se jindika l-indirizz ewwel string,
jew pjuttost, li se punt iktar speċifikament ma 'char.
Avviż mhuwiex attwalment tipponta kullimkien għaliex hemm l-ebda operatur assenjazzjoni.
M'hemm l-ebda sinjal ugwali, hekk kollox aħna qed tagħmel huwa allokat l-buffer imsejħa varjabbli.
Dan jiġri li jkun 32 bits għaliex dan huwa pointer,
u l-kontenut ta buffer preżumibbilment eventwalment
se jkollu l-indirizz ta 'char, iżda għal issa, dak li jkun fihom buffer ma?
Just xi fittizji, li jaf, xi valur żibel,
għaliex aħna ma espliċitament initialized dan, hekk aħna ma għandha tassumi xejn.
Okay, hekk issa linja 17 huwa 'x'jinkludi linja 17 do?
Forsi li se sħun dan up.
Hija prints string, id-dritt?
Hija prints String jekk jogħġbok.
>> Linja 18 huwa tip ta 'familjari issa li aħna biss raw varjazzjoni ta' dan
iżda ma 'kodiċi format differenti, sabiex fil-linja 18,
aħna qed javżak scanf hawnhekk huwa l-indirizz ta 'blokki ta' memorja.
Nixtieq li ring fi string, kif implikat% s,
iżda l-problema hija li aħna ma għamlu ftit affarijiet hawn.
X'hemm waħda mill-problemi?
[Istudenti] Huwa tipprova dereference pointer null.
Tajba, pointers nulla jew biss inkella mhux magħruf.
Int għoti scanf indirizz, iżda inti biss qal mument ilu
li dan l-indirizz huwa xi valur żibel għaliex aħna ma attwalment tassenja din għal xejn,
u hekk int tgħidilhom scanf effettivament imorru tpoġġi string hawn,
imma ma nafux fejn hawn s'issa hija,
hekk aħna ma attwalment allokati memorja għall-buffer.
Barra minn hekk, dak li huma inti wkoll ma anki javżak scanf?
Ejja ngħidu li dan kien ta 'blokki ta' memorja, u ma kienx ta 'valur żibel,
iżda int xorta ma javżak scanf xi ħaġa importanti.
[Student] Fejn fil-fatt huwa, l-ampersand.
Ampersand, hekk f'dan il-każ, huwa okay.
Minħabba buffer hija diġà ddikjarat bħala indikatur
mal-biċċa * ta sintassi, aħna ma bżonn l-użu ampersand
għaliex dan huwa diġà l-indirizz, iżda naħseb smajt hawnhekk.
[Student] Kif big huwa?
Tajba, aħna mhux qed javżak scanf kemm hu kbir dan buffer hija,
li jfisser anki jekk buffer kienu pointer,
aħna qed tgħid scanf, poġġi string hawn,
iżda hawnhekk jista 'jkun 2 bytes, jista' jkun ta '10 bytes, din tista' tkun megabyte.
Scanf m'għandha l-ebda idea, u minħabba li din hija blokki ta 'memorja
preżumibbilment, mhuwiex string s'issa.
Huwa biss string ladarba inti tikteb karattri u 0 \ 'dik blokki ta' memorja.
Issa huwa biss ftit blokki ta 'memorja.
Scanf mhux se tkun taf meta tieqaf bil-miktub għal dak l-indirizz.
>> Jekk inti recall xi eżempji fil-passat fejn I saltwarjament ittajpjat fuq it-tastiera
jippruvaw overflow buffer, u tkellimna fuq il-ġimgħa dwar eżattament dak.
Jekk avversarju b'xi mod jinjetta fil-programm tiegħek kelma ħafna akbar
jew sentenza jew frażi allura inti kienu qed jistennew inti tista 'qbiż
blokki ta 'memorja, li jista' jkollha konsegwenzi ħżiena,
bħal li jieħdu fuq il-programm kollu innifsu.
Għandna bżonn biex jiffissaw dan b'xi.
Let me zoom out u jmorru fil-verżjoni 3 ta 'dan il-programm.
Li ftit aħjar.
F'dan il-verżjoni, avviż-differenza.
F'konformità 16, jien darb'oħra tiddikjara buffer varjabbli imsejħa,
imma dak li hu issa?
Huwa ta 'firxa ta' 16 Chars.
Dan huwa tajjeb għaliex dan ifisser I issa jistgħu tell scanf
hawnhekk hija chunk attwali ta 'memorja.
Tista 'kważi taħseb arrays bħala pointers issa,
anki jekk dawn mhux qed attwalment ekwivalenti.
Huma ser jaġixxi b'mod differenti f'kuntesti differenti.
Iżda huwa ċertament il-każ li buffer hija referenzar
16 Chars kontigwi għaliex dan huwa dak firxa hija
u kienet għal ftit ġimgħat issa.
>> Hawnhekk, I am javżak scanf hawn blokki ta 'memorja.
Din id-darba, huwa attwalment ta 'blokki ta' memorja,
iżda għaliex huwa dan il-programm għadu sfruttat?
X'hemm ħażin għadu?
Stajt qal tagħti me 16 bytes imma-
[Student] X'jiġri jekk dawn it-tip f'aktar minn 16?
Eżattament, jekk dak l-utent tipi fil-17 karattri jew karattri 1700?
Fil-fatt, ejja ara jekk ma nistgħux vjaġġ fuq dan l-iżball issa.
Huwa aħjar iżda mhux perfetta.
Let me imorru quddiem u run jagħmlu scanf3 li jiġbor dan il-programm.
Let me run scanf3, String jekk jogħġbok: bonjour, u aħna jidhru li huma okay.
Let me jippruvaw waħda kemmxejn itwal, bonjour hemm.
Okay, ejja do bonjour hemm kif int illum, Ikteb.
Getting tip ta 'xxurtjati hawn, ejja ngħidu bonjour hemm kif inti.
Kkritikat dan.
Okay, hekk aħna ltqajna xxurtjati. Ejja naraw jekk aħna ma jistgħux jistabbilixxu dan.
Le, mhuwiex ser let me kopja.
Ejja nippruvaw dan mill-ġdid.
Kull dritt, stand mill.
Ser naraw kemm nista nippretendu li tiffoka filwaqt li xorta tagħmel dan.
Kkritikat dan. Li pjuttost xieraq, fil-fatt.
Hemm immorru.
Punt magħmula.
>> Dan, embarrassing għalkemm huwa wkoll huwa, huwa wkoll wieħed mis-sorsi ta 'konfużjoni kbira
meta tikteb programmi li għandhom bugs għaliex jimmanifestaw ruħhom
biss darba fil-waqt kultant.
Il-verità hija li anki jekk il-kodiċi tiegħek huwa kompletament imkisser,
jista 'biss jiġi kompletament imkisser darba fil-waqt
għaliex kultant, essenzjalment dak li jiġri huwa l-talloka sistema operattiva
memorja ftit aktar minn inti fil-fatt bżonn għal kwalunkwe raġuni,
u għalhekk ħadd qed tuża l-memorja dritt wara blokki tiegħek ta '16 karattri,
hekk jekk inti tmur sa 17, 18, 19, tkun xi tkun, mhuwiex tali big deal.
Issa, il-kompjuter, anki jekk ma crash f'dak il-punt,
jista 'eventwalment jużaw numru byte 17 jew 18 jew 19 għal xi ħaġa oħra,
fejn punt tad-data tiegħek li inti tpoġġi hemm, għalkemm eċċessivament twil,
hija se tikseb jinkiteb fuqhom potenzjalment minn xi funzjoni oħra.
Mhuwiex neċessarjament se jibqgħu intatti,
iżda mhux neċessarjament se jikkawża ħsara seq.
Iżda f'dan il-każ, I finalment sakemm karattri biżżejjed
li jien essenzjalment jinqabżu segment tiegħi ta 'memorja, u BAM,
is-sistema operattiva qal, "Jiddispjacini, li l-ebda tort tajba segmentazzjoni,."
>> U ejja ara issa jekk dak li jibqa hawn fil tiegħi direttorju-
avviż li għandi dan il-fajl hawn, qalba.
Avviż li dan jerġa 'jissejjaħ dump qalba.
Huwa essenzjalment fajl li fih l-kontenut tal-memorja programm tiegħek
fil-punt li fih ġġarraf,
u biss tipprova eżempju ftit hawn let me go fil hawn
u run GDB dwar scanf3 u mbagħad jispeċifika tielet argument imsejjaħ qalba,
u avviż hawnhekk li jekk I jelenka l-kodiċi,
aħna ser ikunu jistgħu bħas-soltu mal-GDB biex tibda mixi permezz ta 'dan il-programm,
u nista run u malli I hit-as mal-kmand pass fil GDB-
malli I hit-linja potenzjalment Buggy wara ittajpjar fl string enormi,
I ser tkun kapaċi biex effettivament jidentifikaw hawnhekk.
Aktar dwar dan, għalkemm, fis-sezzjoni f'termini ta 'miżbliet ewlenin
u simili sabiex inti tista 'attwalment poke madwar ġewwa tal-miżbla qalba
u ara fuq liema linja l-programm naqset inti.
Kwalunkwe mistoqsijiet imbagħad fuq pointers u dwar l-indirizzi?
Minħabba llum fuq, aħna qed tmur biex tibda tieħu għall mogħtija li dawn l-affarijiet jeżistu
u nafu eżattament x'inhuma.
Iva.
>> [Student] Kif come inti ma jkollu jpoġġi l ampersand jmiss għall-part-
Good kwistjoni.
Kif come I ma jkollu jpoġġi l ampersand jmiss għall-firxa karattru kif għamilt qabel
mal-maġġoranza ta 'eżempji tagħna?
Ir-risposta qasira hija arrays huma ftit speċjali.
Tista 'kważi think a buffer bħala fatt li l-indirizz,
u huwa biss hekk jiġri li jkun il-każ li l-notazzjoni kwadru bracket
huwa konvenjenza sabiex inkunu tista 'tmur fil parentesi 0, parentesi 1,
parentesi 2, mingħajr ma jkollu jintuża l-notazzjoni *.
Li l-daqsxejn ta 'gidba abjad minħabba arrays u indikaturi
huma, fil-fatt, ftit differenti, iżda jistgħu spiss, imma mhux dejjem jintużaw minflok xulxin.
Fil-qosor, meta funzjoni qiegħda tistenna pointer għal blokki ta 'memorja,
inti tista 'jew tgħaddiha indirizz li kienet irritornata mid malloc,
u aħna ser tara malloc mill-ġdid qabel twil, jew inti tista 'tgħaddi l-isem ta' firxa.
Inti ma għandekx tagħmel ampersand ma 'arrays għaliex diġà huma
essenzjalment simili indirizzi.
Dik hija l-unika eċċezzjoni.
Il-parentesi kwadri jagħmluhom speċjali.
>> Tista tpoġġi ampersand jmiss għall-buffer?
Mhux f'dan il-każ.
Li ma tkunx taħdem minħabba li, għal darb'oħra, ta 'dan il-każ kantuniera
fejn arrays huma pjuttost mhux attwalment indirizzi.
Iżda aħna ser forsi terga 'lura għal li qabel twil mal eżempji oħra.
Ejja jippruvaw isolvu problema hawn.
Għandna struttura data li aħna kont qed tuża għal xi żmien magħrufa bħala firxa.
Kawża fil-punt, dan huwa dak li aħna biss kellhom.
Iżda arrays għandhom xi upsides u negattivi.
Arrays huma għaliex sbieħ?
X'hemm ħaġa waħda li inti tixtieq-sal-punt li tixtieq arrays-dwar arrays?
X'hemm konvenjenti dwarhom? X'hemm konvinċenti?
Għaliex ma aħna jintroduċu lilhom fl-ewwel post?
Yeah.
[Student] Huma jista 'jaħżen ħafna ta' data, u inti ma għandekx tuża l-ħaġa sħiħa.
Tista 'tuża taqsima.
Tajba, ma 'firxa tista' taħżen ħafna ta 'data,
u inti ma neċessarjament ikollhom l-użu kollha ta 'dan, sabiex inti tista overallocate,
li jista 'jkun konvenjenti jekk inti ma taf minn qabel kemm ta' xi ħaġa li jistennew.
>> GetString huwa eżempju perfett.
GetString, miktub minn us, m'għandha l-ebda idea kif ħafna Chars li tistenna,
għalhekk il-fatt li nistgħu jallokaw biċċiet ta 'memorja kontigwi hija tajba.
Arrays wkoll isolvu problema rajna ftit ġimgħat ilu issa
fejn il-kodiċi tiegħek tibda biex tittrasferixxi fis xi ħaġa ferm imfassla ħażin.
Ifakkar li I ħolqot struttura student imsejjaħ David,
u mbagħad li kien effettivament alternattiva, għalkemm,
li jkollhom l-isem varjabbli msejħa u ieħor varjabbli imsejħa, I think, dar,
u ieħor varjabbli msejħa ID għaliex f'dak l-istorja I mbagħad ried jintroduċi xi ħaġa oħra
bħall Rob fil-programm, hekk allura I iddeċieda stenna minuta,
I-ħtieġa li tibdel isem dawn il-varjabbli.
Ejja sejħa mini name1, ID1, house1.
Ejja sejħa Rob name2, house2, ID2.
Iżda mbagħad stenna minuta, dak dwar Tommy?
Imbagħad kellna tliet varjabbli aktar.
Aħna introdotti xi ħadd ieħor, erba 'settijiet ta' varjabbli.
Id-dinja bdiet tikseb messy malajr ħafna,
hekk aħna introdotti structs, u x'hemm konvinċenti dwar Struct?
Xi jfisser Struct C let you do?
Huwa tassew strambi illum.
X'inhu? >> [Rispons istudent inaudible]
Yeah, speċifikament, tippermetti typedef inti toħloq tip ta 'data ġdida,
u Struct, l-keyword Struct, jippermettilek li jirrappreżentaw
biċċiet kunċettwali relatati ta 'data flimkien
u wara jsejħulhom xi ħaġa bħal student.
>> Dan kien tajjeb għax issa nistgħu mudell
tip ħafna aktar ta konċettwalment koerenti l-kunċett ta 'student fi varjabbli
aktar milli arbitrarju li wieħed għal string, wieħed għal ID, u oħrajn.
Arrays huma sbieħ għaliex jippermettu magħna biex jibdew tindif kodiċi tagħna.
Imma dak li hu żvantaġġ issa ta 'firxa?
X'tista inti ma tagħmel? Yeah.
[Student] Inti għandek tkun taf kemm hu kbir huwa.
Inti għandek tkun taf kemm hu kbir huwa, hekk huwa tip ta 'uġigħ.
Dawk tal inti ma esperjenza ta 'programmazzjoni preċedenti tkun taf li fil-lott ta' lingwi,
bħal Java, inti tista 'titlob blokki ta' memorja, speċifikament firxa,
kemm hu kbir inti, b'tul, proprjetà, biex ngħidu hekk, u li verament konvenjenti.
Fl C, inti ma tistax anki sejħa strlen fuq firxa ġeneriku
għaliex strlen, kif il-kelma timplika, huwa biss għall kordi,
u inti tista figura l-tul ta 'sekwenza minħabba din il-konvenzjoni tal-bniedem
li jkun ta '0 \, iżda l-firxa, aktar ġeneriku, huwa biss blokki ta' memorja.
Jekk huwa firxa ta 'ints, hemm mhux se jkun hemm xi karattru speċjali
fl-aħħar għalikom.
Int għandek tiftakar it-tul ta 'firxa.
Tnaqqis ieħor ta 'firxa imrobbija prinċipali tagħha GetString innifsu.
X'hemm ieħor tnaqqis ta 'firxa?
Sinjur, biss int u jien illum.
[Rispons istudent inaudible] >> Huwa dak?
Huwa ddikjarat fuq il-munzell.
Okay, iddikjarat fuq il-munzell. Għaliex ma inti tixtieq li?
[Student] Minħabba jiġrilha użat mill-ġdid.
Hija gets użati mill-ġdid.
Okay, jekk tuża firxa li talloka memorja,
inti ma tistax, per eżempju, jirritornaha għaliex dan huwa fuq il-munzell.
Okay, li l-iżvantaġġ.
U kif madwar ieħor ma 'firxa?
Ladarba inti jallokaw dan, int tip ta 'invitat jekk għandek bżonn iktar spazju
minn dak array jkun.
>> Imbagħad aħna introdotti,, irtirar malloc, li tana l-abbiltà li dinamikament talloka memorja.
Imma x'jiġri jekk aħna ppruvaw dinja differenti għal kollox?
X'jiġri jekk ridna biex issolvi ftit dawk il-problemi
hekk aħna minflok 'tiegħi pinna tkun raqdu hawn' il
dak jekk aħna minflok riedu essenzjalment joħolqu dinja li ma jibqax bħal din?
Dan huwa firxa, u, naturalment, dan it-tip ta 'tiddeterjora ladarba aħna laqat il-tarf ta' l-array,
u jien issa m'għadx għandhom spazju għall-ieħor numru sħiħ jew karattru ieħor.
X'jiġri jekk aħna xorta ta 'preemptively jgħidu tajjeb, għaliex ma we jirrilassaw
dan ir-rekwiżit li dawn il-biċċiet ta 'memorja jkun kontigwu lura lura,
u għaliex ma, meta I bżonn int jew char,
biss jagħtu me spazju għal wieħed minnhom?
U meta I bżonn ieħor, agħti lili ieħor ispazju,
u meta I bżonn ieħor, agħti lili ieħor ispazju.
Il-vantaġġ ta 'liema issa hija li jekk xi ħadd ieħor
jieħu l-memorja hawn fuq, no big deal.
I ser jieħdu din blokki addizzjonali ta 'memorja hawn u allura dan wieħed.
>> Issa, il-qabda biss hawnhekk hija li din kważi jħoss simili jien
mazz sħiħ ta 'varjabbli differenti.
Dan iħoss bħal 5 fatturi varjabbli differenti potenzjalment.
Imma x'jiġri jekk aħna steal idea minn spag
fejn aħna b'xi mod link dawn l-affarijiet flimkien kunċettwali, u jekk dak I ma 'dan?
Dan huwa vleġġa ħafna ħażin mfassla tiegħi.
Iżda jissoponi li kull wieħed minn dawn biċċiet ta 'memorja
indika l-oħra, u dan Guy, li m'għandha l-ebda parentela għal-lemin tiegħu,
m'għandha l-ebda vleġġa bħal din.
Dan huwa fil-fatt dak li sejjaħ lista marbuta.
Din hija struttura tad-data ġdida li tippermetti magħna biex jallokaw blokki ta 'memorja,
imbagħad ieħor, imbagħad ieħor, imbagħad ieħor, kwalunkwe ħin irridu
matul programm, u aħna ftakar li dawn qed kollha b'xi mod relatati
billi litteralment ikkatenar flimkien, u aħna ma li pictorially hawn bi vleġġa.
Iżda fil-kodiċi, x'għandhom ikunu l-mekkaniżmu li permezz tagħha inti tista 'b'xi mod jikkonnettjaw,
kważi simili Scratch, wieħed blokki għall-ieħor fi blokki?
Aħna jistgħu jużaw pointer, id-dritt?
Minħabba li verament il-vleġġa li għaddej mill-kwadru fuq tax-xellug,
dan Guy hawn biex dan wieħed, jista 'jkun fihom ġewwa ta' dan il-kwadru
mhux biss xi ints, mhux biss xi char, imma dak jekk I attwalment allokati
spazju ftit extra biex issa,
kull biċċiet tiegħi ta 'memorja, anke jekk dan se jiswieli,
issa jistenna ftit aktar rettangolari fejn wieħed mill-biċċiet tal-memorja
huwa użat għal numru, bħall-numru 1,
u mbagħad jekk dan Guy ħwienet n-numru 2,
din blokki oħra ta 'memorja huwa użat għall-vleġġa,
jew aktar konkret, pointer.
U suppose I jaħżen in-numru 3 hawn fuq I filwaqt li jużaw dan il-punt f'dak il-Guy,
u issa dan Guy, ejja nassumu I jridux biss 3 biċċiet bħal dawn ta 'memorja.
I ser jiġbed linja permezz ta 'dan, jindikaw null.
M'hemm l-ebda karattru addizzjonali.
>> Tabilħaqq, dan huwa kif aħna tista 'tmur dwar implimentazzjoni
xi ħaġa li sejjaħ lista marbuta.
Lista marbuta hija struttura tad-data ġdida, u huwa sies lejn
Strutturi ħafna fancier data li jibdew sabiex isolvu problemi
skond il-linji ta 'Facebook tat-tip problemi u Google tat-tip problemi
fejn inti jista 'jkollhom settijiet enormi ta' dejta, u ma għadux qatgħat li
li jaħżen kollox contiguously u l-użu xi ħaġa bħal tfittxija lineari
jew saħansitra xi ħaġa bħal tfittxija binarja.
Inti tixtieq drabi anki aħjar running.
Fil-fatt, wieħed mill-Grails Mqaddsa aħna ser nitkellmu dwar aktar tard din il-ġimgħa d-dieħla jew
huwa algoritmu li taħdem il-ħin huwa kostanti.
Fi kliem ieħor, dejjem jieħu l-istess ammont ta 'ħin ebda kwistjoni
kemm hu kbir l-input huwa, u dan ikun jikkostitwixxi tabilħaqq konvinċenti,
aktar minn hekk xi ħaġa logaritmika.
X'inhu dan fuq l-iskrin hawn?
Kull wieħed mill-rettangoli huwa eżattament dak I biss ġibdet bl-idejn.
Imma l-ħaġa-triq kollha fuq ix-xellug hija varjabbli speċjali.
Huwa ser tkun pointer wieħed minħabba li l-gotcha 1
ma 'lista marbuta, kif dawn l-affarijiet huma msejħa,
huwa li inti għandek hang fuq tarf wieħed tal-lista marbuta.
>> Eżatt bħal ma string, inti għandek tkun taf l-indirizz ta 'l-char-ewwel.
Jittrattaw Istess għal listi marbuta.
Inti għandek tkun taf l-indirizz ta 'l-blokki 1 ta' memorja
minħabba li minn hemm, inti tista 'tilħaq kull wieħed ieħor.
Negattivi.
Dak prezz huma aħna jħallsu għal dan versatilità li jkun dinamiku
mdaqqsa struttura tad-data li jekk aħna qatt bżonn memorja aktar,, multa
biss jallokaw 1 blokki aktar u jiġbed pointer minn
l-qadima lill-tail-ġdid tal-lista?
Yeah.
[Istudenti] Huwa jieħu l-ispazju madwar darbtejn daqs.
Huwa jieħu spazju doppju, b'tali mod li definittivament żvantaġġ, u Rajna dan
tradeoff qabel bejn il-ħin u l-ispazju u l-flessibilità
fejn minn issa, għandna bżonn mhux 32 bits għal kull wieħed minn dawn in-numri.
Aħna verament bżonn 64, 32 għan-numru u 32 għall-pointer.
Imma ħej, I għandhom 2 gigabytes ta 'RAM.
Żieda oħra bits 32 hawn u hawn ma jidhirx li kbar ta 'ftehim.
Iżda għal settijiet ta 'dejta kbar, huwa definittivament żżid sa litteralment doppju.
X'hemm ieħor tnaqqis issa, jew dak karatteristika nistgħu jieqfu,
jekk aħna jirrappreżentaw listi ta 'affarijiet ma' lista marbuta u mhux firxa?
[Student] Inti ma tistax travers dan lura.
Inti ma tistax travers dan lura, hekk int tip ta 'invitat jekk int mixi
mix-xellug għal-lemin bl-użu ta loop għal jew loop filwaqt
u allura inti tirrealizza, "Oh, nixtieq li jmorru lura għall-bidu tal-lista."
Inti ma tistax għaliex dawn pointers biss jmorru mix-xellug għal-lemin bħala l-vleġeġ jindikaw.
>> Issa, inti tista 'tiftakar il-bidu tal-lista ma' varjabbli,
iżda li l-kumplessità li wieħed iżomm f'moħħu.
Firxa, ma jimpurtax kemm inti tmur, inti tista 'dejjem tagħmel minus, minus, nieqes, nieqes
u jmorru lura minn fejn ikun ġej iċ inti daħal.
X'hemm ieħor isfel hawn? Yeah.
[Kwistjoni student inaudible]
Inti tista ', sabiex inti ħadthom attwalment biss ipproponiet struttura tad-data msejħa lista doppjament marbut,
u fil-fatt, inti żid ieħor pointer għal kull wieħed minn dawn rettangoli
li tmur-direzzjoni oħra, l-rasu li
huwa issa inti tista 'travers quddiem u lura,
l-tnaqqis ta 'li issa inti qed tuża tliet darbiet kemm memorja kif aħna użati biex
u wkoll żżid il-kumplessità f'termini tal-kodiċi għandek tikteb biex tikseb dan id-dritt.
Iżda dawn huma kollha forsi kompromessi raġonevoli ħafna, jekk il-qlib hija aktar importanti.
Yeah.
[Student] Inti wkoll ma tistax jkollhom lista marbuta 2D.
Tajba, inti ma tistax verament jkollhom lista 2D marbuta.
Inti tista '. Mhuwiex kważi faċli kif firxa.
Bħal firxa, inti parentesi miftuħa, parentesi magħluqa, parentesi miftuħa, magħluqa parentesi,
u ikollok xi struttura 2-dimensjonali.
Inti tista 'timplimenta lista 2-dimensjonali marbuta
jekk inti tagħmel add-kif inti propost-pointer 3 għal kull wieħed minn dawn l-affarijiet,
u jekk taħseb dwar lista oħra li ġejjin fil int stil 3D
mill-iskrin li lkoll, li huwa biss ieħor katina ta 'xi tip.
Nistgħu nagħmlu dan, iżda mhux sempliċi kemm ittajpjar parentesi miftuħa, parentesi kwadri. Yeah.
[Kwistjoni student inaudible]
Tajba, għalhekk din hija kicker reali.
>> Dawn algoritmi li konna pined fuq, bħall-oh, tfittxija binarja,
inti tista 'tfittex firxa ta' numri fuq il-bord
jew ktieb tat-telefon tant aktar malajr jekk inti tuża taqsam u conquer
u algoritmu tfittxija binarja, iżda tfittxija binarja meħtieġa żewġ assunzjonijiet.
Wieħed, li d-data kienet magħżula.
Issa, nistgħu preżumibbilment żżomm din magħżula,
hekk forsi li mhux ta 'tħassib, iżda tfittxija binarja wkoll preżunt
li kellek l-aċċess bl-addoċċ għal-lista ta 'numri,
u l-firxa jippermettilek li jkollhom aċċess bl-addoċċ, u billi l-aċċess bl-addoċċ,
I tfisser jekk inti qed tingħata firxa, kemm ħin ma tieħu inti
biex jiksbu l parentesi 0?
Operazzjoni waħda, inti biss użu [0] u int hemm dritt.
Kemm passi ma jieħdu biex jiksbu l-post 10?
Pass, inti biss tmur [10] u int hemm.
B'kuntrast, kif tista 'tikseb l-eqreb numru sħiħ 10 f'lista marbut?
Int għandek tibda fil-bidu għax int biss ftakar
il-bidu ta 'lista marbuta, bħal string qed mfakkar
mill-indirizz ta 'char ewwel, u tikkonstata li int 10
jew li l-karattru 10 fil string, inti għandek tfittex l-ħaġa kkritikat kollu.
>> Għal darb'oħra, aħna mhux qed jsolvu l-problemi tagħna.
Aħna introdotti oħrajn ġodda, iżda huwa verament jiddependi fuq dak li qed tipprova li disinn għall.
F'termini ta 'implimentazzjoni ta' dan, nistgħu jissellef idea minn dik l-istruttura student.
Is-sintassi hija simili ħafna, ħlief issa, l-idea hija ftit aktar astratti
minn dar u l-isem u l-ID.
Imma jiena nipproponi li jista 'jkollna struttura tad-data fis-C
li huwa msejjaħ node, kif l-aħħar kelma fuq il-pjastra jissuġġerixxi,
ġewwa ta 'node, u node huwa biss kontenitur ġeneriku fix-xjenza tal-kompjuter.
Huwa ġeneralment imfassal bħala ċirku jew kwadra jew rettangolari kif aħna ghamilt.
U f'din l-istruttura tad-data, għandna int, n,
b'tali mod li n-numru Irrid li taħżen.
Imma dak li huwa dan it-tieni linja, Struct node * jmiss?
Għaliex dan korretta, jew liema rwol ma dan play ħaġa,
anki jekk huwa ftit cryptic ewwel daqqa t'għajn?
Yeah.
[Rispons istudent inaudible]
Eżattament, sabiex il-tip ta '* gamgmu li huwa pointer ta' xi tip.
L-isem ta 'dan il-werrej huwa arbitrarju li jmiss,
iżda nistgħu qalu li din ħaġa li rridu, imma dak ma dan il-punt pointer li?
[Student] Ieħor node. >> Eżattament, hija tirreferi għall-ieħor node bħal din.
>> Issa, dan huwa tip ta 'kurżità ta' C.
Ifakkar li C tinqara minn top kompilatur għal isfel, xellug għal-lemin,
li jfisser li jekk 'dan huwa xi ftit differenti minn dak li għamilna mal-istudent.
Meta aħna definit student, aħna fil-fatt ma poġġiex kelma hemmhekk.
Hija biss qal typedef.
Imbagħad kellna int id, spag isem, spag dar,
u mbagħad student fil-qiegħ ta 'l-Struct.
Din id-dikjarazzjoni huwa xi ftit differenti għaliex,
għal darb'oħra, il-kompilatur C hija ftit mutu.
Huwa biss ser jaqra fuq għal isfel,
hekk jekk jilħaq il-linja 2 hawn
fejn jmiss huwa ddikjarat u jara, oh, hawnhekk varjabbli imsejjaħ jmiss.
Huwa pointer għal node Struct.
Il-kompilatur se realizzata dak li huwa node Struct?
Stajt qatt semgħu dan il-ħaġa qabel,
minħabba li l-node kelma ma jista 'inkella jidhru
sakemm il-qiegħ, sabiex ikun hemm din redundancy.
Int għandek tgħid node Struct hawn, li inti tista 'mbagħad tqassar aktar tard
grazzi għall typedef isfel hawn, iżda dan huwa minħabba
aħna referenzar l-istruttura nnifisha ġewwa tal-istruttura.
Dik hija l-gotcha waħda hemm.
>> Xi problemi interessanti ser jinqalgħu.
Imxejna ltqajna lista ta 'numri. Kif nistgħu daħħal fis dan?
Kif nistgħu tfittxija dan? Kif nistgħu tħassar minnha?
Speċjalment issa li għandna biex jimmaniġġjaw kollha ta 'dawn pointers.
Int ħsibt pointers kienu tip ta 'mind-liwi
meta kellek waħda minnhom biss tipprova li jaqra int lilha.
Issa għandna biex jimmanipulaw jiswew lista sħiħa tal.
Għaliex ma nieħdu 5-minuta break tagħna hawn, u allura aħna ser iġibu
xi folks sa fuq il-palk biex jagħmlu eżattament dan.
>> C hu gost ħafna aktar meta huwa aġixxa out.
Min litteralment jixtieq li jkun l-ewwel?
Okay, come fuq up. Inti l-ewwel.
Min jixtieq li jkun 9? Okay, 9.
Kif dwar 9? 17?
A clique ftit hawn. 22 u 26 f'dak ringiela ta 'quddiem.
U allura kif madwar xi ħadd hemmhekk li qed mfakkar fil.
You are 34. Okay, 34, come fuq up.
L-ewwel huwa hemmhekk. Okay, l-erba 'inti guys.
U li ma aħna ngħidu għal 9?
Min hu 9 tagħna?
Min verament jixtieq li jkun 9? Kull dritt, jaqgħu fuq, ikunu 9.
Here we go.
34, aħna ser jissodisfaw inti hemmhekk.
L-ewwel parti hija tagħmel infuskom look bħal dik.
26, 22, 17, tajba.
Jekk inti tista 'toqgħod barra għall-ġenb, għaliex aħna qed tmur biex malloc inti fil-mument.
>> Tajba, tajba.
Okay, eċċellenti, sabiex ejja jistaqsu ftit mistoqsijiet hawn.
U fil-fatt, dak l-isem tiegħek? >> Anita.
Anita, okay, come fuq matul hawn.
Anita se tgħinna tip ta issolvi mistoqsija waħda pjuttost sempliċi fl-ewwel,
li hija kif taħseb li ssib jekk jew le il-valur huwa fil-lista?
Issa, avviż li l-ewwel, irrappreżentata hawn minn Lucas,
huwa xi ftit differenti, u għalhekk il-biċċa tiegħu ta 'karta hija deliberatament ġenb
għaliex mhuwiex daqshekk twil u ma jieħu bħala bits ħafna,
anke jekk teknikament huwa għandu l-istess daqs ta 'karta biss jiddawwar.
Imma hu ftit differenti li hu biss 32 bits għal pointer,
u kollha ta 'dawn guys huma 64 bits, nofs li hija l-għadd, li nofshom huwa pointer.
Iżda l-pointer ma jkunx mpinġi, hekk jekk inti guys tista kemmxejn awkwardly
użu tax-xellug tiegħek għall-punt lejn il-persuna li jmiss lilek.
U int numru 34. X'hemm isem tiegħek?
Ari.
Ari, hekk fil-fatt, żomm il-karta fil-lemin tiegħek, u naħa tax-xellug tmur dritta stabbiliti.
Inti jirrappreżentaw null fuq ix-xellug.
>> Issa stampa bniedem tagħna huwa ferm konsistenti.
Dan huwa attwalment kif pointers jaħdmu.
U jekk inti tista scrunch ftit b'dan il-mod hekk jien mhux fil-mod tiegħek.
Anita hawn, issib lili n-numru 22,
iżda tassumi limitu ta 'mhux bnedmin impriża agrikola tiegħu sal biċċiet tal-karti,
iżda din hija lista, u inti biss għandek Lucas li tibda bil
minħabba li hu litteralment l-pointer ewwel.
Ejja ngħidu inti stess huma pointer, u għalhekk inti wisq għandhom il-ħila għall-punt fuq xi ħaġa.
Għaliex ma tibda bil tipponta lejn eżattament dak Lucas hija li tipponta lejn?
Tajba, u let me jippromulgaw din out hawn fuq.
Biss għall-fini ta 'diskussjoni, let me pull up paġna vojta hawn.
Kif inti jespliċitaw isem tiegħek? >> Anita.
Okay, Anita.
Ejja ngħidu node * Anita = Lucas.
Ukoll, aħna ma għandhom sejħa inti Lucas. Għandna sejħa inti l-ewwel.
Għaliex dan fil-fatt konsistenti mar-realtà hawn?
Wieħed, l-ewwel diġà jeżisti.
L-ewwel ġie allokat preżumibbilment x'imkien up here.
Node * 1, u huwa kien allokat lista b'xi.
I do not know kif dan ġara. Dan ġara beda klassi qabel.
Din il-lista marbuta mill-bnedmin ġiet maħluqa.
U issa f'dan il-punt fl-istorja-din hija kollha għaddej fuq Facebook apparentement iktar tard
f'dan il-punt fl-istorja, Anita kienet initialized li jkun daqs l-ewwel,
li ma jfissirx li l-punti Anita fuq Lucas.
Pjuttost, hija tindika fuq liema huwa jinnota bi
minħabba li l-istess indirizz li l-ġewwa ta 'Lucas s 32 bit - 1, 2, 3 -
huwa issa wkoll ġewwa tal Anita s 32 bit - 1, 2, 3.
>> Issa isibu 22. Kif inti tmur dwar kif isir dan?
X'hemm li Point? >> Għal dak kollu.
Punt li kwalunkwe, sabiex jimxi 'l quddiem u jaġixxu out bħala l-aħjar tista' hawn.
Tajba, tajba, u issa int tipponta lejn 'x'hemm isem tiegħek bi 22?
Ramon. >> Ramon, hekk Ramon qed tirnexxi 22.
Inti issa għamlu verifika.
Ma Ramon == 22, u jekk iva, per eżempju, nistgħu ritorn vera.
Let me-waqt li dawn guys stand hawn kemmxejn awkwardly-
let me tagħmel xi ħaġa malajr bħal bool ssib.
Jien ser jimxi 'l quddiem u ngħid (node ​​* lista, int n).
I ser tkun dritt lura miegħek guys. I biss għandhom jiktbu xi kodiċi.
U issa jien se jimxi 'l quddiem u jagħmlu dan, node * Anita = lista.
U jien ser jimxi 'l quddiem u ngħid filwaqt li (Anita! = NULL).
>> Il-metafora hawn huwa jkollna ftit stirati, iżda filwaqt li (Anita! = NULL), dak li nixtieq do?
I bżonn xi mod ta 'referenzar
l-eqreb numru sħiħ li Anita hija li tipponta lejn.
Fil-passat, meta kellna l-istrutturi, li node huwa,
użajna l-notazzjoni dot, u aħna ngħid xi ħaġa simili
anita.n, iżda l-problema hawn hija li Anita mhix Struct per se.
X'inhu hi?
Hi tal pointer, sabiex verament, jekk irridu li jużaw dan dot notazzjoni-
u dan se tħares deliberatament ftit cryptic-
għandna nagħmlu xi ħaġa simili tmur xellug kwalunkwe Anita hija li tipponta lejn
u mbagħad jiksbu l-qasam imsejħa n.
Anita huwa pointer, imma dak li hu * Anita?
What do issib meta inti tmur għal dak Anita hija li tipponta lejn?
A Struct, node, u node, lura, għandha kamp msejħa n
minħabba li, wieħed jiftakar, f'dawn l-oqsma 2, li jmiss u n-
li rajna mument ilu dritt hawn.
>> Biex attwalment jimitaw dan il-kodiċi,
stajna nagħmlu dan u jgħidu jekk ((* Anita). n == n), il-n li jien infittxu.
Avviż li l-funzjoni kienet għaddiet fl-għadd I jimpurtahom.
Imbagħad I tista 'tmur quddiem u tagħmel xi ħaġa simili ritorn vera.
Inkella, jekk dan mhux il-każ, dak li nixtieq do?
Kif nista jissarraf kodiċi dak Anita għamlu dan intuwittivament bil-mixi permezz tal-lista?
X'għandi nagħmel up hawn biex jissimulaw Anita tieħu dak il-pass lejn ix-xellug, dak il-pass lejn ix-xellug?
[Inaudible student rispons] >> X'hemm li?
[Rispons istudent inaudible]
Tajba, mhux idea ħażina, iżda fil-passat, meta aħna ghamilt dan, aħna ghamilt Anita + +
minħabba li jżid in-numru 1 sa Anita,
li tipikament punt fuq il-persuna li jmiss, bħal Ramon,
jew il-persuna li jmiss lilu, jew dak li jmiss lilu persuna tistabbilixxi l-linja.
Iżda li mhux pjuttost tajba hawn għax dan xi ħaġa look like fil-memorja?
Mhux li. Irridu jiskonnettja dak.
Jidher qisu dan fil-memorja, u anki jekk stajt mfassla 1 u 2 u 3 qrib xulxin,
jekk aħna verament simulata din tista 'inti guys-, waqt li jkunu għadhom tipponta lejn l-istess nies,
jista 'xi wħud minnkom tieħu lura pass każwali, xi wħud minnkom pass każwali quddiem?
>> Dan mess għadu lista marbuta,
imma dawn guys jista 'jkun kullimkien fil-memorja,
hekk Anita + + mhux sejjer jaħdem għaliex?
X'hemm fil-post Anita + +?
Min jaf.
Huwa xi valur ieħor li biss hekk jiġri li jkun tintervjeni
fost kollha ta 'dawn in-nodi b'kumbinazzjoni għaliex aħna ma tkunx qed tużah firxa.
Aħna allokat kull wieħed minn dawn in-nodi individwalment.
Okay, jekk inti guys tista 'tnaddaf infuskom back up.
Let me tipproponi li minflok Anita + +, aħna minflok nagħmlu Anita gets-
ukoll, għaliex ma immorru kwalunkwe Anita hija li tipponta lejn u mbagħad do. jmiss?
Fi kliem ieħor, immorru Ramon, li l-azjenda in-numru 22,
u mbagħad. hija li jmiss bħallikieku Anita ikun ikkupjar pointer tiegħu naħa tax-xellug.
Iżda hi ma tmurx aktar il-bogħod minn Ramon għaliex sibna 22.
Imma dan ikun l-idea. Issa, dan huwa mess god-orribbli.
Onestament, ħadd qatt ser jiftakar dan sintassi, u għalhekk Thankfully,
huwa attwalment ftit deliberat-oh, inti ma attwalment tara dak I kiteb.
Dan ikun aktar konvinċenti jekk inti tista '. Voila!
>> Wara l-kwinti, I kien isolvi l-problema b'dan il-mod.
Anita, li tieħu dak il-pass lejn ix-xellug,
1, nagħmlu mur l-indirizz li Anita hija li tipponta lejn
u fejn hi ser issib mhux biss n, li aħna biss ċċekkjati għall-finijiet paragun, l-
imma se ssib ukoll jmiss - f'dan il-każ,
Naħa tax-xellug Ramon s tipponta lejn il-node li jmiss fil-lista.
Iżda dan huwa l-mess god-orribbli li għalih irreferejt qabel,
iżda jirriżulta C tikri us jissimplifikaw dan.
Minflok tal-kitba (* Anita), nistgħu minflok biss jiktbu Anita-> n,
u huwa l-istess ħaġa eżatt funzjonalment, iżda huwa ħafna aktar intuwittiv,
u huwa ħafna aktar konsistenti ma 'l-istampa li aħna kont qed tfassal
dan iż-żmien bl-użu vleġeġ.
>> Fl-aħħar nett, dak li għandna bżonn tagħmel fl-aħħar ta 'dan il-programm?
Hemm linja waħda tal-kodiċi li jifdal.
Ritorn liema?
Foloz, għaliex jekk irridu jiksbu permezz-sħiħ filwaqt loop
u Anita, fil-fatt, null, dan ifisser hija marret it-triq kollha sa l-aħħar tal-lista
fejn kienet tipponta lejn 'x'hemm isem tiegħek mill-ġdid?
Naħa tax-xellug Ari. >> Ari, li huwa null.
Anita issa hija nulla, u I realizzata int biss permanenti hawn awkwardly fil-limbu
għaliex jien ser off fuq monologue hawn,
iżda aħna ser jinvolvu inti ġdid fi ftit mument.
Anita huwa null f'dak il-punt fl-istorja, hekk il-linja waqt itemm,
u għandna biex jirritorna foloz għaliex jekk qabbdet triq kollha lejn pointer null Ari s
allura ma kien hemm ebda numru li hi mfittxija fil-lista.
Nistgħu tnaddaf dan up wisq, iżda dan huwa implimentazzjoni pjuttost tajba allura
ta 'funzjoni traversal, a isibu funzjoni għal lista marbuta.
Huwa għadu tfittxija lineari, iżda mhux sempliċi kemm + + pointer
jew + + varjabbli i għaliex issa ma nistgħux raden
fejn kull wieħed minn dawn in-nodi huma fil-memorja.
Irridu litteralment isegwu l-traċċa ta 'frak tal-ħobż jew, b'mod iktar speċifiku,
pointers, biex jiksbu minn node għall-ieħor.
>> Issa ejja pprova ieħor. Anita, tridu li jiġu lura hawn?
Għaliex ma we imorru quddiem u jallokaw persuna waħda oħra mill-udjenza?
Malloc-x'hemm isem tiegħek? >> Rebecca.
Rebecca. Rebecca ġie malloced mill-udjenza,
u hija issa ħażna n-numru 55.
U l-għan fil-idejn issa huwa għall Anita li daħħal
Rebecca fil-lista marbuta hawn fil-post xieraq tagħha.
Come fuq matul hawn għal mument.
I għamlu xi ħaġa bħal din.
I għamlu * node. U x'hemm isem tiegħek mill-ġdid?
Rebecca. >> Rebecca, okay.
Rebecca gets malloc (sizeof (node)).
Eżatt bħal għandna allokati affarijiet simili studenti u whatnot fil-passat,
għandna bżonn l-daqs tal-node, hekk issa Rebecca
hija li tipponta lejn dak?
Rebecca għandha żewġ oqsma ġewwa tal tagħha, li waħda minnhom hija 55.
Ejja nagħmlu dak, Rebecca '> = 55.
Iżda mbagħad Rebecca '> jmiss għandu jkun-like dritt issa, minn naħa tagħha hija tip ta' min jaf?
Huwa tipponta lejn xi valur żibel, hekk għaliex ma għal miżura tajba
aħna l-inqas jagħmlu dan b'tali mod li naħa tax-xellug hija issa fil-ġenb tagħha.
Issa Anita, teħodha minn hawn.
Inti għandek Rebecca li ġew allokati.
Jimxi 'l quddiem u ssib fejn għandna jitqiegħdu Rebecca.
Tajba, tajba ħafna.
Okay, tajba, u issa għandna bżonn li inti tipprovdi daqsxejn ta 'direzzjoni,
sabiex inti ħadthom laħaq Ari.
Naħa tax-xellug tiegħu huwa null, iżda Rebecca b'mod ċar jappartjeni għad-dritt,
hekk kif nistgħu jkollhom ibiddlu din il-lista marbuta
sabiex jiddaħħal Rebecca fil-post xieraq?
Jekk inti tista litteralment jimxu idejk xellug tan-nies madwar kif meħtieġ,
aħna ser tiffissa l-problema li mod.
Okay, tajba, u sadanittant, naħa tax-xellug Rebecca huwa issa minn naħa tagħha.
>> Dan kien faċli wisq.
Ejja nippruvaw allokazzjoni-we're kważi isir, 20.
Okay, come fuq up.
20 tkun ġiet allokata, so let me imorru quddiem u ngħid għal darb'oħra hawn
konna biss isir Saad * node.
Għandna malloc (sizeof (node)).
Aħna mbagħad tagħmel l-sintassi eżatt l-istess kif għamilna qabel għal 20,
u jien ser tagħmel li jmiss = NULL, u issa huwa sa Anita
li daħħal inti fil-lista marbuta, jekk inti tista 'tilgħab l-irwol istess eżatt.
Teżegwixxi.
Okay, tajba.
Issa taħseb sew qabel tibda miexja l-idejn xellug madwar.
Inti bil-bosta ltqajna l-irwol aktar strambi illum.
Li idejn għandhom ikunu mċaqilqa ewwel?
Okay, stenna, jien seduta xi s no.
Jekk xi folks se politely tixtieq tgħin issolvi sitwazzjoni skomda hawn.
Naħa tax-xellug Li għandhom jiġu aġġornati 1 forsi? Yeah.
[Student] s Saad.
Okay, l-Saad, għaliex, għalkemm?
[Rispons istudent inaudible]
Tajba, għaliex jekk nimxu 'dak l-isem tiegħek? >> Marshall.
Marshall, jekk nimxu naħa tiegħu l-ewwel sa null,
issa għandna litteralment orfni erba 'persuni f'din il-lista
għaliex kien l-unika ħaġa li tipponta lejn Ramon u kulħadd lejn ix-xellug,
sabiex taġġorna l pointer ewwel kienet ħażina.
Ejja teqred dan.
Tajba, u issa imorru quddiem u jimxu l-naħa tax-xellug xieraq tipponta lejn Ramon.
Dan tħoss żejda ftit.
Issa hemm żewġ persuni li tipponta lejn Ramon, iżda li l-multa
għaliex issa kif inkella nistgħu taġġorna l-lista?
Liema naħa l-oħra trid timxi?
Eċċellenti, issa għandhom aħna mitlufa xi memorja?
Le, hekk tajjeb, ejja ara jekk ma nkunux nistgħu jiksru dan darba aktar.
>> Mallocing aħħar darba, numru 5.
It-triq kollha fil-dahar, jaqgħu fuq l isfel.
Huwa ferm eċċitanti.
[Applause]
X'hemm isem tiegħek? >> Ron.
Ron, okay, inti malloced bħala numru 5.
Imxejna biss esegwiti kodiċi li kważi identiċi għal dawn
biss bi isem differenti.
Eċċellenti.
Issa, Anita, Xorti tajba ddaħħal numru 5 fil-lista issa.
Tajba, u?
Eċċellenti, għalhekk dan huwa verament l-tielet tliet każijiet kollha.
Aħna l-ewwel kellhom xi ħadd fl-aħħar, Rebecca.
Aħna mbagħad kellhom xi ħadd fin-nofs.
Issa għandna xi ħadd fil-bidu, u f'dan l-eżempju,
aħna issa kellhom taġġorna Lucas għall-ewwel darba
minħabba li l-ewwel element fil-lista issa għandha jindikaw lejn node ġdid,
li, imbagħad, hija li tipponta lejn numru node 9.
>> Dan kien dimostrazzjoni immensament skomdi, jien ċert,
hekk rawnd kbir ta 'applause għal dawn guys jekk inti tista'.
Nicely jsir.
Li kollox. Inti tista 'żżomm biċċiet tiegħek ta' karta bħala memorja ftit.
Jirriżulta li tagħmel dan fil-kodiċi
mhux daqshekk sempliċi kemm biss jiċċaqalqu l-idejn madwar
u tipponta pointers fuq affarijiet differenti.
Imma tirrealizza li meta niġu żmien biex jimplimentaw xi ħaġa bħal
lista marbuta jew varjant ta 'dan jekk inti tiffoka fuq verament
dawn fundamentali bażiċi, il-problemi gidma daqs għandi biex insemmu,
huwa dan idejn jew dan idejn, tirrealizza li dak li huwa altrimenti programm pjuttost kumpless
jistgħu, fil-fatt, titnaqqas għal blokki pjuttost sempliċi bini bħal dan.
>> Ejja jieħdu l-affarijiet fid-direzzjoni aktar sofistikati għadhom.
Issa għandna l-idea tal-lista marbuta.
Aħna wkoll ikollhom-grazzi għall-suġġeriment lura hemm 'lista doppjament marbut,
li jistenna kważi l-istess, iżda issa għandna żewġ pointers ġewwa tal-Struct
minflok waħda, u nistgħu probabbilment jagħmlu sejħa lil dawk pointers preċedenti u li jmiss
jew tax-xellug jew, iżda nagħmlu, fil-fatt, jeħtieġ tnejn minnhom.
Il-kodiċi se jkun ftit aktar involuti.
Anita kien ikollha tagħmel xogħol aktar hawn fix-xena.
Iżda nistgħu ċertament jimplimentaw dan it-tip ta 'struttura.
F'termini ta 'running time, għalkemm, x'għandha tkun il-ħin qed taħdem
għall Anita ta 'sejba ta n-numru fil-lista marbuta issa?
O Still kbira ta 'n, għalhekk l-ebda aħjar minn tfittxija lineari.
Aħna ma tistax tagħmel tfittxija binarja, għalkemm, għal darb'oħra.
Għaliex kien li l-każ? Inti ma tistax jaqbżu madwar.
Anki jekk aħna ovvjament tara l-bnedmin fuq il-palk,
u Anita setgħet eyeballed dan u qal, "Hawn hu l-nofs tal-lista,"
hi ma jkunux jafu li jekk hi kienu l-programm tal-kompjuter
minħabba li l-unika ħaġa hija kellha lukkett fuq fil-bidu tax-xenarju
kien Lucas, li kien l-pointer ewwel.
Hija bilfors ikollhom isegwu dawk ir-rabtiet,
għadd mod tagħha sakemm hija sabet madwar l-nofs,
u anke dakinhar, hi mhux ser tkun taf meta hi laħqet-nofs
sakemm hi tmur it-triq kollha sa l-aħħar figura kemm hemm,
imbagħad backtracks, u li wisq se jkun diffiċli sakemm inti kienu
lista doppjament marbut ta 'xi tip.
>> Solving xi problemi tal-lum, iżda jintroduċi oħrajn.
Xi ngħidu dwar struttura data differenti għal kollox?
Dan huwa ritratt ta 'l-trejs fil Mather House,
u f'dan il-każ, aħna għandna istruttura tad-data konna wkoll tip ta 'diġà jitkellem dwar.
Aħna tkellimna dwar munzell fil-kuntest tal-memorja,
u li l-tip ta 'deliberatament imsejjaħ minħabba munzell fit-termini tal-memorja
huwa effettivament struttura tad-data li għandha Jittieħed aktar u aktar ub'saffi fuq quċċata ta 'dan.
Imma l-ħaġa interessanti dwar munzell, kif inhu l-każ fir-realtà,
hija li huwa tip speċjali ta 'data istruttura.
Hija struttura tad-data fejn l-ewwel element fil-
huwa l-aħħar element out.
Jekk inti l-trej ewwel li jitqiegħdu fuq il-munzell,
int se tkun sfortunatament l-trej aħħar li għandhom jittieħdu barra l-munzell,
u li mhux neċessarjament ħaġa tajba.
Bil-maqlub, inti tista 'taħseb dwar dan il-mod ieħor madwar,
l-aħħar huwa l-l-ewwel.
>> Issa, ma 'xi xenarji jiġu f'moħħna meta jkollhom munzell
istruttura tad-data fejn għandek dik il-proprjetà
ta 'l-aħħar, l-ewwel, huwa attwalment konvinċenti?
Hija li xi ħaġa tajba? Hija li xi ħaġa ħażina?
Huwa definittivament xi ħaġa ħażina jekk l-trejs ma kinux kollha identiċi
u dawn kienu kollha kuluri differenti speċjali jew whatnot,
u l-kulur li trid huwa it-triq kollha fil-qiegħ.
Of course, inti ma tistax tikseb li mingħajr sforz kbir.
Int għandek tibda mill-quċċata u x-xogħol tiegħek mod isfel.
Bl-istess mod, dak li jekk inti kienu wieħed minn dawn subien fann
li tistenna sa l-lejl tipprova tikseb iPhone u l-linji up
f'post bħal dan?
Ma Ikun sbieħ jekk il-maħżen tat-tuffieħ
kienu struttura tad-data munzell?
Yay? Nay?
Huwa biss tajjeb għall-persuni li juru up fil-minuta possibbli aħħar
u mbagħad nikseb mnittfa off-kju.
U fil-fatt, il-fatt li I kien tant inklinati li jgħidu kju
huwa attwalment konsistenti ma 'dak li aħna kieku ssejjaħ dan it-tip ta' struttura tad-data,
1 fir-realtà meta l-ordni ma jimpurtax,
u trid li l-ewwel wieħed fl biex tkun l-ewwel waħda minn
jekk biss għall-raġunijiet ta 'ġustizzja umana.
Aħna ser ġeneralment sejħa li struttura tad-data kju.
>> Jirriżulta barra minn hekk listi relatati, nistgħu tibda tuża dawn l-ideat bażiċi istess
u tibda ħolqien ta 'tipi ġodda u differenti ta' soluzzjonijiet għall-problemi.
Per eżempju, fil-każ ta 'ċumnija, nistgħu jirrappreżentaw munzell
permezz ta 'struttura tad-data bħal dan, nixtieq nipproponi.
F'dan il-każ, stajt ddikjarat Struct, u stajt qal ġewwa ta 'din l-istruttura
huwa firxa ta 'numri u mbagħad daqs varjabbli imsejħa,
u jiena ser sejħa dan ħaġa munzell.
Issa, għaliex ma dan attwalment jaħdmu?
Fil-każ ta 'ċumnija, I jista' jiġbed dan b'mod effettiv fuq l-iskrin bħala firxa.
Hawnhekk huwa munzell tiegħi. Dawn huma numri tiegħi.
U aħna ser tiġbed minnhom kif dan, dan, dan, dan, dan.
U mbagħad I għandhom xi membru ieħor tad-data hawn,
li tissejjaħ id-daqs, għalhekk dan huwa daqs, u dan huwa numri,
u kollettivament, l-iPad kollu hawn jirrappreżenta struttura munzell wieħed.
Issa, fil-kontumaċja, id-daqs ikun preżumibbilment ltqajna biex jiġu initialized għal 0,
u x'hemm ġewwa tal-firxa ta 'numri inizjalment
meta I ewwel talloka firxa?
Żibel. Min jaf? U din attwalment ma jimpurtax.
Ma jimpurtax jekk dan huwa 1, 2, 3, 4, 5, kompletament bl-addoċċ
billi xortih ħażina maħżuna fl-istruttura tiegħi għaliex sakemm naf li d-daqs tal-munzell
huwa 0, allura naf programmatically, ma nħarsu lejn xi wieħed mill-elementi fil-firxa.
Ma jimpurtax x'hemm hemmhekk.
Ma tħares lejn lilhom, kif ikun il-implikazzjoni ta 'daqs ta' 0.
>> Imma ejja ngħidu issa I jimxi 'l quddiem u daħħal xi ħaġa fil-munzell.
Irrid li daħħal in-numru 5, so I tpoġġi numru 5 hawn,
u mbagħad dak li għandi jħott hawn?
Issa nixtieq attwalment jħott 1 għall-qies,
u issa l-munzell huwa ta 'daqs 1.
X'jiġri jekk I jimxi 'l quddiem u daħħal in-numru, ejja ngħidu, 7 jmiss?
Dan imbagħad gets aġġornata għal 2, u mbagħad aħna ser nagħmlu 9,
u allura dan gets aġġornati sa 3.
Iżda l-karatteristika interessanti issa 'dan munzell hu li
Jien suppost biex jitneħħew liema element jekk irrid li pop
xi ħaġa off tal-munzell, biex ngħidu hekk?
9 tkun l-ewwel ħaġa li tmur.
Kif għandha l-istampa tinbidel jekk irrid pop element off-munzell,
ħafna bħal trej fil Mather?
Yeah. >> [Student] Issettja d-daqs sa 2.
Eżattament, kollha nagħmel huwa stabbilit daqs għal 2, u x'għandi nagħmel mal-firxa?
I ma jkollhom jagħmlu xi ħaġa.
I jistgħu, biss sabiex ikunu anali, poġġi 0 hemmhekk jew -1 jew xi ħaġa li turi
li din mhix valur leġittimu, iżda ma jimpurtax għax
I tista 'tirreġistra barra mill-firxa innifsu kemm hu
hekk li naf biss ħarsa lejn l-ewwel żewġ elementi f'dan firxa.
Issa, jekk immur u żid in-numru 8 għal dan il-array, kif ma l-istampa tinbidel jmiss?
Dan isir 8, u dan isir 3.
Jien qtugħ ta 'kantunieri ftit hawn.
Issa għandna 5, 7, 8, u aħna qed lura għal daqs ta '3.
Dan huwa pjuttost sempliċi biex wieħed jimplimentah,
iżda meta aħna se dispjaċir din id-deċiżjoni tad-disinn?
Meta do affarijiet jibdew imorru ferm, ħażina ħafna? Yeah.
[Rispons istudent inaudible]
Meta inti tixtieq li tmur lura u jiksbu l-ewwel element inti tpoġġi pulzieri
>> Jirriżulta hawnhekk għalkemm munzell huwa firxa taħt il-barnuża,
dawn l-istrutturi tad-data konna beda jitkellem dwar huma wkoll ġeneralment magħrufa bħala
Strutturi astratti data li biha kif dawn qed implimentata
huwa kompletament minbarra l-punt.
Struttura tad-data bħal munzell suppost li żżid l-appoġġ
Operazzjonijiet bħal push, li timbotta trej fuq il-munzell,
u pop, li tneħħi element mill-munzell, u li hu.
Jekk ġejt biex tniżżel kodiċi xi ħadd ieħor li diġà implimentat
dan ħaġa imsejħa 'ċumnija, dik il-persuna kienet miktuba
biss żewġ funzjonijiet għalik, timbotta u pop, li l-uniku skop fil-ħajja
tkun li tagħmel eżattament dan.
Inti jew lilu jew lilha li implimentat dan il-programm
kien ikun totalment il-wieħed li jiddeċiedi kif għandhom jiġu implimentati
l-semantika ta 'imbuttar u popping minn taħt il-barnuża
jew il-funzjonalità ta 'imbuttar u popping.
U jien għamlu deċiżjoni kemmxejn shortsighted hawn
bl-implimentazzjoni munzell tiegħi ma 'din l-istruttura tad-data sempliċi għaliex?
Meta tagħmel dan waqfa istruttura tad-data?
Fuq liema punt għandi lura żball meta l-utent sejħiet timbotta, per eżempju?
[Student] Jekk ma jkun hemm l-ebda aktar spazju.
Eżattament, jekk hemm spazju aktar, jekk stajt maqbuża kapaċità,
li hija kollha caps minħabba li tissuġġerixxi li huwa xi tip ta 'kostanti globali.
Well, allura jien biss se jkollhom jgħidu, "Skużani jien ma tistax push valur ieħor
fuq il-munzell, "ferm simili fl Mather.
>> F'xi punt, dawn qed tmur biex jolqtu l-parti ta 'fuq ta' dak kabinett ftit.
M'hemm l-ebda spazju aktar jew kapaċità fis-munzell, f'liema punt hemm xi tip ta 'żball.
Huma għandhom jitqiegħdu l-element x'imkien ieħor, il-trej x'imkien ieħor,
jew imkien fil-livelli kollha.
Issa, bil-kju, nistgħu jimplimentawha ftit differenti.
A kju huwa xi ftit differenti f'dak taħt il-barnuża, tista 'tiġi implimentata
bħala firxa, iżda għaliex, f'dan il-każ, am I tipproponi
li għandhom ukoll element ras li jirrappreżenta l-kap tal-lista,
quddiem tal-lista, l-ewwel persuna fil-linja fil-maħżen tat-tuffieħ, minbarra l-daqs?
Għaliex għandi bżonn biċċa ta 'dejta addizzjonali hawn?
Think lura għal dak numri huwa
jekk stajt mfassla dan kif ġej.
Ejja ngħidu li dan huwa issa kju minflok munzell,
id-differenza tkun 'biss bħall-Apple store-kju huwa ġust.
L-ewwel persuna fil-linja fil-bidu tal-lista, numru 5 f'dan il-każ,
hu jew hi se tkun let fil-maħżen ewwel.
Ejja nagħmlu dan.
Ejja ngħidu li dan huwa l-istat ta 'kju tiegħi f'dan il-mument fil-ħin, u issa l-maħżen tat-tuffieħ
jiftaħ u l-ewwel persuna, numru 5, hija mmexxija fil-maħżen.
Kif nista jibdlu l-istampa issa li jien de-kju l-ewwel persuna
fuq quddiem tal-linja?
X'hemm li? >> [Student] Ibdel il-kju.
Ibdel il-kap, hekk 5 tisparixxi.
Fir-realtà, huwa bħallikieku 'kif l-aħjar biex tagħmel dan?
Fir-realtà, huwa daqs li kieku dan Guy tisparixxi.
X'għandu numru 7 jagħmlu f'każ ta 'maħżen attwali?
Huma ser tieħu pass kbir 'il quddiem.
>> Imma dak li aħna niġu biex japprezzaw meta niġu għall-arrays
u li jiċċaqalqu madwar l-affarijiet?
Dak it-tip ta 'ħela ta' ħin tiegħek, id-dritt?
Għaliex inti għandek tkun hekk anali mod li jkollhom l-ewwel persuna
fil-bidu tal-linja fil fiżikament l-bidu tal-blokki ta 'memorja?
Dak kompletament bla bżonn. Għaliex?
Liema jista I biss ftakar minflok? >> [Rispons istudent inaudible]
Eżattament, I jistgħu biss ftakar dan il-kap membru addizzjonali tad-data
li issa l-kap tal-lista ma għadhiex 0, li kien mument ilu.
Issa huwa attwalment in-numru 1. B'dan il-mod, niġi ottimizzazzjoni żgħira.
Just għaliex stajt de-kju xi ħadd mill-linja fil-bidu tal-linja fil-maħżen tat-tuffieħ
ma jfissirx li kulħadd irid bidla, li recall huwa operazzjoni lineari.
I jistgħu minflok jqattgħu ħin kostanti biss
u jiksbu mbagħad rispons ħafna aktar mgħaġġla.
Iżda l-prezz jien ħlas huwa dak li jiksbu li l-prestazzjoni addizzjonali
u ma jkollhom bidla kulħadd?
Yeah. >> [Rispons istudent inaudible]
Tista 'żżid aktar nies, ukoll, li l-problema hija ortogonali
għall-fatt li aħna mhux qed ċaqliq nies madwar.
Huwa għadu firxa, iva jekk jew le aħna bidla kulħadd jew le-
oh, I ara dak li jfisser, okay.
Fil-fatt, jiena naqbel ma 'dak li qed tgħid f'dik huwa kważi daqs li kieku
aħna qed issa qatt ser tuża l-bidu ta 'dan array aktar
għaliex jekk jien tneħħi 5, imbagħad I neħħi 7.
Imma I biss tpoġġi lin-nies lejn il-lemin.
>> Hija tħoss bħal jien ħela l-ispazju, u eventwalment kju tiegħi disintegrates fis xejn,
hekk nistgħu biss ikollhom nies trembil,
u nistgħu naħsbu ta 'dan array verament bħala xi tip ta' struttura ċirkolari,
imma nużaw dak l-operatur fir C biex tagħmel dan it-tip ta wraparound?
[Rispons istudent inaudible] >> L-operatur modulo.
Ikun tedjanti ftit biex jaħsbu permezz kif taħseb li tagħmel il-trembil,
imma stajna nagħmlu dan, u aħna tista 'tibda tħaddim ta' nies fuq dak użat biex jiġi-quddiem tal-linja,
iżda aħna biss tiftakar ma 'dan varjabbli ras li l-kap attwali tal-linja fil-fatt hu.
X'jiġri jekk, minflok, l-għan tagħna finalment, għalkemm,
kien li wieħed ifittex numri, kif għamilna hawn fuq il-palk mal-Anita,
iżda aħna verament irridu l-aħjar ta 'dawn Dinjiet?
Irridu sofistikazzjoni aktar tippermetti firxa minn
għaliex irridu l-ħila li dinamikament jikber l-istruttura tad-data.
Iżda aħna ma rridux li jkollhom jirrikorru għal xi ħaġa li aħna enfasizzat
fl-ewwel lecture kienx algoritmu ottimali,
dak ta 'tfittxija lineari.
Jirriżulta li inti tista ', fil-fatt, jinkiseb
jew għall-inqas qrib ħin kostanti, fejn xi ħadd bħal Anita,
jekk hi configures istruttura tad-data tagħha ma tkunx lista marbuta,
m'għandhomx ikunu munzell, m'għandhomx ikunu kju, jistgħu, fil-fatt,
toħroġ bi struttura tad-data li tippermetti tagħha biex tfittex up affarijiet,
anki kliem, mhux biss numri, fil dak li aħna ser sejħa ħin kostanti.
>> U fil-fatt, b'ħarsa 'l quddiem, wieħed mill-psets f'din il-klassi hija kważi dejjem
implimentazzjoni ta 'spellchecker, fejn
aħna nagħtuk terġa 'xi kliem Ingliż 150.000 u l-għan huwa li
tagħbija dawk fil-memorja u malajr tkun kapaċi twieġeb il-mistoqsijiet tal-formola
huwa din il-kelma spjegati b'mod korrett?
U verament terda jekk inti kellha jtenni permezz kliem kollha 150.000 tingħata risposta għal din.
Iżda, fil-fatt, aħna ser tara li nistgħu nagħmlu dan fil-ħin ħafna, malajr ħafna.
U li għaddej biex jinvolvu xi ħaġa implimentazzjoni imsejħa tabella hash,
u anki jekk ewwel daqqa t'għajn dan ħaġa tissejjaħ tabella hash se
ejjew jintlaħqu dawn iż-żminijiet super rispons rapidu,
jirriżulta li hemm fil-fatt problema.
Meta niġu żmien biex jimplimentaw dan ħaġa imsejħa għal darb'oħra, jien tagħmel dan mill-ġdid.
Jien l-unika waħda hawn.
Meta niġu żmien biex jimplimentaw dan ħaġa tissejjaħ tabella hash,
aħna qed tmur biex ikollhom biex jagħmlu deċiżjoni.
Kif big jekk dan ħaġa fil-fatt tkun?
U meta nibdew in-numri ddaħħal fis din it-tabella hash,
kif ser nieħdu biex jaħżinhom b'tali mod
li nistgħu tikseb minnhom lura malajr kemm aħna ltqajna magħhom fil-?
Iżda aħna ser tara qabel twil li din il-kwistjoni ta '
meta birthday kulħadd huwa fil-klassi se jkun pjuttost germane.
Jirriżulta li f'din il-kamra, konna ltqajna ftit mijiet ta nies,
sabiex l-odds li tnejn minna għandna l-birthday istess huwa probabbilment pjuttost għoli.
X'jiġri jekk kien hemm biss 40 minna f'din il-kamra?
X'inhuma l-odds ta 'żewġ persuni li jkollhom l-birthday istess?
[Studenti] Aktar minn 50%.
Yeah, aktar minn 50%. Fil-fatt, I anke miġjuba chart.
Jirriżulta 'u dan huwa verament ftit Sneak preview-
jekk hemm biss 58 minna f'din il-kamra, il-probabbiltà ta '2 minna
wara li l-birthday istess huwa immensament għoli, kważi 100%,
u li għaddej biex jikkawża mazz sħiħ ta 'iweġġgħu għalina nhar l-Erbgħa.
>> Ma 'dak imsemmi, ejja jaġġorna hawn. Aħna ser tara inti nhar l-Erbgħa.
[Applause]
[CS50.TV]