[Powered by Google Translate] [Vika 6]
[David J. Malan] [Harvard University]
[Þetta er CS50.] [CS50.TV]
>> Þetta er CS50, og þetta er upphaf viku 6,
svo a par af nýjum verkfærum eru nú í boði fyrir þig að taka kostur af,
fyrst sem heitir CS50 stíl.
Stuðlar eru ef þú ert eins og mig eða einhverju kennslu félagar,
þú hefur sennilega séð forrit sem lét stíl lítur svolítið eitthvað eins og this.
Kannski þú byrjar að skera nokkrar horn seint í nótt, eða þú munt takast á við það síðar,
og þá kemur TF CA yfir á skrifstofutíma.
Þá er það erfitt fyrir okkur að lesa.
Jæja, þetta númer er setningafræðilega rétt, og það mun þýða, og það mun í raun að keyra.
En það er örugglega ekki a 5 fyrir stíl.
>> En ef við förum inn í þessa skrá hér-
og eftir að ég hef conditions2.c-
og ég að keyra þessa nýju stjórn, style50 á þessari skrá conditions2.c, Enter,
eftir að það er upplýst mig um að það hefur verið stílfærð.
Gedit eftir að skrá hefur verið breytt á diski,
og ef ég smelli endurhlaða, eru öll vandamál nú sjálfvirk.
[Lófaklapp]
Það er eitt af því sem við gerðum um helgina.
Gera sér grein fyrir að það er ófullkomin vegna þess að það eru sumir kóða
að það einfaldlega mun ekki vera fær um að stylize fullkomlega,
en átta sig á þessu er nú tól sem þú getur nýtt sér
ef aðeins til snyrtilegu upp sumir af the fleiri errantly sett hrokkið axlabönd og þess háttar.
>> En meira sannfærandi er nú CS50 Athuga.
Með CS50 athuga, getur þú í raun að framkvæma sömu prófanir misskilning
eigin kóðann þinn að kennslu styrkþegar geta.
Þetta er a stjórn lína tól sem kemur nú í tækið
eins fljótt og þú gerir að update50 eins og á
pset 4 forskriftir, og þú notar það í raun svona.
Þú keyra skipunina check50.
Þá fara í stjórn lína rifrildi, eða fleiri almennt þekktur eins og a rofi eða fána.
Almennt eru það sem hafa bandstrik kallað skipta
að lína forrit, svo-C skilgreinir
þær athuganir sem þú vilt keyra.
>> Prófin sem þú vilt keyra er bent einstaklega með þessum streng,
2012/pset4/resize.
Með öðrum orðum, það er bara handahófskennt en einstakt band
sem við notum til einstaklega þekkja réttmæti próf pset 4 er.
Og þá tilgreina rúm aðskilin lista yfir skrár sem þú vilt hlaða inn
til CS50 stöðva fyrir greiningu.
Fyrir dæmi, ef ég fer í lausn mína hér fyrir resize.c-
láta mig opna stærri flugstöðinni glugga-
og ég fara á undan og keyra segjum check50-C 2012/pset4/resize,
og þá skal ég fara á undan og tilgreina nöfn á skrám,
resize.c, og þá högg inn, það samþjappaður,
Það hleður, tékka það og ég brást bara allt fullt af prófum.
Einn í rauðu efst til vinstri segir að resize.c og BMP til.
Það var próf. Það var spurningin sem við spurði.
Og það er óánægður vegna þess að svarið var falskur.
The hvítur texti fyrir neðan það segir gert ráð bmp.h að vera til, og það er einfaldlega mér að kenna.
Ég gleymdi að senda það, þannig að ég þarf að hlaða bæði skrár,
resize.c og bmp.h.
En nú taka öllum öðrum prófum eru í gular vegna þess að þeir hafa keyra,
og svo er broskalla andlit lóðrétt vegna þess að hann er hvorki ánægður né leiður,
en við verðum að ráða bót þessi mál í rautt áður en hin fer að hlaupa.
>> Leyfðu mér að laga þetta.
Leyfðu mér að minnka og endursýning þetta, í þetta sinn með bmp.h einnig
á the stjórn lína, inn, og nú ef allt fer vel,
það er að fara að athuga og svo aftur vegna-halda þinn andardráttur-
allt grænt, sem þýðir að ég er að gera mjög vel á pset 4 svo langt.
Þú getur séð og álykta af lýsandi texta hér
nákvæmlega hvað það er sem við höfum prófað.
Við prófuð fyrst að gera skrár til?
Við prófuð þá er resize.c þýða?
Þá erum við prófa er það ekki búa til 1x1 pixla BMP þegar n er Resize þáttur, er 1.
Nú, ef þú hefur ekki hugmynd um hvað n er, verður þú að þegar kafa í pset 4,
en það er einfaldlega geðheilbrigði athuga til að tryggja að þú sért ekki að breyta stærð
mynd á öllum ef Resize þáttur er 1.
Ef, hins vegar resizes það 1x1 pixla til a 1x1 pixla BMP til 2x2 rétt
þegar n er 2, þá álíka eyðublöð, mitt í samræmi við það.
>> Í stuttu máli, þetta er ætlað til, einn, gera The Crossing fingur
út af the jafna rétt áður en þú sendir pset þínu.
Þú vilja vita nákvæmlega hvað TF mun brátt vita
Þegar þú ferð um að senda inn nokkrar af þessum vandamál setur,
og einnig er kennslufræðilegt hvatning virkilega að setja
tækifæri í framan þig þannig að þegar þú veist fyrirfram
að það er villur í kóðanum þínum og prófanir sem eru ekki liðin,
þú getur sett í skilvirkari tími upp að framan til að leysa þau vandamál
frekar en að missa stig, fá viðbrögð frá TF þinni,
og þá fara, "ahh," eins og ég ætti að hafa mynstrağur það út.
Nú að minnsta kosti það er tól til að hjálpa þér að finna það.
Það er ekki að fara að benda á hvar villan er, en það mun segja þér
hvað er einkenni af því.
>> Nú átta sig á próf eru ekki endilega tæmandi.
Bara vegna þess að þú fá a skjár fullur af grænu broskalla andlit
þýðir ekki að númerið þitt sé fullkominn, en það þýðir
að það hefur staðist ákveðnar prófanir sem mælt er með því að sérstakur.
Stundum við munum ekki gefa út ávísanir.
Fyrir dæmi, whodunit, einn af þeim þáttum pset 4,
er eins konar vonbrigðum ef við gefa þér
svar um hvað það er, og það er a tala af lifnaðarhættir til að sýna
hver maður er í þeirri rauðu hávaða.
The sérstakur verður alltaf tilgreina í framtíðinni fyrir pset 5 og áfram
það eftirlit til fyrir þig.
Þú munt taka eftir að það er þetta hvíta URL neðst.
Fyrir nú, þetta er bara sjúkdómsgreiningar framleiðsla.
Ef þú heimsækir þessi slóð, munt þú fá a heild búnt af brjálaður, dulinn skilaboð
að þú ert velkomin til að horfa í gegnum, en það er að mestu leyti fyrir starfsfólk
svo að við getum greina og kemba galla í check50 sjálfu.
>> Án fjaðrafok, við skulum fara til þar sem við var horfið.
CS50 bókasafn tókum sem sjálfsagðan hlut í nokkrar vikur,
en svo í síðustu viku, við byrjuðum flögnun aftur einn af lögum hennar.
Við byrjuðum að setja hliðar band í hag hvað í staðinn?
[Nemendur] Char.
Char *, sem hefur verið char * allan þennan tíma,
en nú að við þurfum ekki að láta sem það er í raun gögn tegund band.
Fremur, það er verið samheiti nokkurs konar fyrir char *,
og band er röð af stöfum,
Svo hvers vegna er það skynsamleg að tákna strengi eins char * s?
Hvað er a char * tákna í samhengi við þessa hugmynd um streng?
Já. >> [Nemandi] Fyrsta staf.
Gott, fyrsta staf, en ekki alveg í fyrsta staf.
Það er-[Nemendur] Address.
Gott, heimilisfang fyrstu persónu.
Allt sem er nauðsynlegt til að tákna streng í minni í tölvu
er bara einstakt heimilisfang fyrstu bæti þess.
Þú þarft ekki einu sinni að vita hversu lengi það er
því hvernig er hægt að reikna það út virk?
[Nemandi] String lengd.
Þú getur hringt í band lengd, framúrskarandi, en hvernig er band lengd vinna?
Hvað þýðir það að gera? Já.
[Nemandi] Halda áfram þar til þú færð núll staf.
Já, nákvæmlega iterates, það bara með for lykkju, en lykkja,
hvað frá * til enda, og endirinn er fulltrúa
með \ 0, svokölluð nul eðli, nul,
ekki að rugla saman við null, sem bendi,
sem mun koma upp í samræðum aftur í dag.
>> Við skrældar aftur lag af GetInt, og þá tókum við a líta á GetString,
og muna að bæði í þessum aðgerðum, eða í raun,
GetString, var með ákveðna aðgerð
í raun flokka, það er að lesa eða greina, inntak notandans.
Og hvað var það nýtt hlutverk?
Scanf eða sscanf. Það kemur reyndar í nokkrum mismunandi bragði.
Það er scanf, það er sscanf, það fscanf.
Fyrir nú, þó, við skulum leggja áherslu á einn auðveldlega sýnd,
og láta mig fara á undan og opna upp í tækinu
skrá eins og þetta, scanf1.c.
Þetta er frábær einfalt forrit,
en það er eitthvað sem við höfum aldrei gert
án aðstoð CS50 bókasafn.
Þetta fær int frá notanda. Hvernig virkar það?
Jæja, í línu 16 þar,
eftir að við lýsa int heitir X, og á þessum tímapunkti í sögunni,
hvað er gildi x?
[Inaudible nemandi svar]
[David M.] Einmitt, hver veit, sumir sorp gildi hugsanlega, svo í 17, segja okkur bara notanda
gefa mér númer, skaltu og skref 18 er þar sem það fær áhugavert.
Scanf virðist láni hugmynd frá printf á að það notar þessi snið númer innan gæsalappa.
% D er auðvitað heiltala.
En hvers vegna er ég komið í & X í staðinn fyrir bara x?
Hið fyrra er rétt. Já.
[Inaudible nemandi svar]
Einmitt, ef markmið þessarar áætlunar, eins og virka GetInt sig,
er að fá int frá notanda ég get framhjá aðgerðir
allar breytur sem ég vil, en ef ég má gefa þeim með tilvísun
eða heimilisfang eða músina, allt samheiti fyrir tilgangi í dag,
þá hefur þessi aðgerð ekki getu til að breyta the innihald af þessi breytu.
Þetta myndi fara í eintaki bara eins og buggy útgáfu skipti
sem við höfum talað um nokkrum sinnum núna.
>> En í staðinn, með því að gera & x, ég bókstaflega farið í það?
[Námsmaður] Heimilisfangið. >> Heimilisfang x.
Það er eins og að teikna kort fyrir virka heitir scanf og segja hér,
Þetta eru leiðbeiningar til a klumpur af minni í tölvunni
að þú getur farið geymt einhverja heiltölu inn
Í röð fyrir sscanf að nú gera það
hvaða rekstraraðili, hvaða stykki af setningafræði er það að fara til verða að nota
jafnvel þó við getum ekki séð það vegna þess að einhver annar skrifaði þessa aðgerð?
Með öðrum orðum - hvað er það?
[Nemandi] X lesa.
Það er að fara að vera einhver lestur, en aðeins með tilliti til x hér.
Ef scanf er framhjá heimilisfang X,
setningafræðilega, hvaða rekstraraðila er skylt að vera til staðar
inni í framkvæmd scanf þannig að scanf
getur í raun skrifa númer 2 á þetta netfang?
Já, þannig að *.
Muna að * er dereference stjórnandi okkar, sem í raun þýðir að fara þangað.
>> Þegar þú hefur verið afhent netfang, eins og raunin er hér,
scanf er líklega, ef við skoðuðum í raun í kringum uppruna sínum kóða-
er að gera * x eða jafngildi í raun að fara á þetta netfang og setja nokkrar gildi þar.
Nú, eins og fyrir því hvernig scanf fær inntak af lyklaborði,
við munum veifa höndum okkar út í dag.
Bara gera ráð fyrir því að stýrikerfi gerir sscanf að tala
á lyklaborði notandans, en á þessum tímapunkti nú í línu 19,
þegar við prenta einfaldlega út x, virðist það vera raunin
að scanf hefur sett int í x.
Það er nákvæmlega hvernig scanf virkar, og muna í síðustu viku
það er einmitt hvernig GetString og GetInt og önnur fjölskylda hans aðgerðir
endanum virkar, að vísu með smá breytileika eins sscanf,
sem þýðir grannskoða band í staðinn á lyklaborðinu.
En við skulum kíkja á smá dreifni þetta.
Árið scanf2, ruglaður ég reyndar upp.
Hvað er rangt-og ég mun fela athugasemd sem útskýrir allt-
hvað er athugavert við þetta kerfi, útgáfa 2?
Vertu eins tæknileg og kostur er.
Það lítur mjög vel út.
Það er fallega indented, en-
Jæja, hvernig um skulum prune það niður styttri spurningum?
Line 16. Hvað er lína 16 gera í nákvæmum en tæknilega ensku?
Getting a lítill óþægilega. Já, Michael.
[Nemandi] Það er að benda á fyrsta staf í streng.
>> Allt í lagi, nálægt. Leyfðu mér að klip að svolítið.
Bendir á fyrsta staf í streng, þú ert að lýsa breytilega heitir biðminni
sem benda til að fyrstu heimilisfang streng,
eða frekar, sem mun benda nánar tiltekið í a bleikju.
Takið það er í raun ekki benda hvar vegna þess að það er engin verkefni rekstraraðila.
Það er ekkert jafn merki, svo allt sem við erum að gera er að úthlutun breytu kallað biðminni.
Það verður að vera 32 bita því það bendi,
og innihald biðminni væntanlega að lokum
mun innihalda veffang bleikju, en nú, hvað þýðir biðminni innihalda?
Bara sumir svikinn, hver veit, sumir sorp gildi,
vegna þess að við höfum ekki beinlínis frumstilla hana, þannig að við ættum ekki að gera ráð fyrir neinu.
Jæja, svo nú lína 17 er-hvað er lína 17 að gera?
Kannski sem mun hita þetta upp.
Það prentar band, ekki satt?
Það prentar String þóknast.
>> Lína 18 er eins konar þekki nú í að við sáum bara dreifni þessa
en með mismunandi sniði kóða, svo í línu 18,
við erum að segja scanf hér er heimilisfang klumpur af minni.
Ég vil að þú hringi í band, eins og gefið í skyn af% s,
en vandamálið er að við höfum ekki gert nokkra hluti hér.
Það er eitt af þeim vandamálum?
[Nemandi] Það er að reyna að dereference núll músina.
Gott, NULL eða bara annars óþekkt ábendingum.
Þú ert fötlun scanf netfang, en þú sagðir bara í smá stund síðan
að það netfang er einhver sorp gildi vegna þess að við ekki í raun að framselja það til nokkuð,
og svo að þú ert að segja scanf raun að fara að setja streng hér
en við vitum ekki hvar hér er enn,
þannig að við höfum ekki í raun úthlutað minni fyrir biðminni.
Þar að auki er það líka ekki einu sinni að segja scanf?
Segjum þetta var klumpur af minni, og það var ekki sorp gildi,
en þú ert samt ekki að segja scanf eitthvað mikilvægt.
[Nemandi] Þar sem það er í raun, að merkið.
Merkið, þannig að í þessu tilfelli, það er allt í lagi.
Þar TAG er þegar lýst sem bendillinn
við * stykki af setningafræði, þurfum við ekki að nota merkið
því það er nú þegar með netfang, en ég held að ég heyrði það hér.
[Nemandi] Hversu stór er það?
Gott, erum við ekki að segja scanf hversu stórt þetta biðminni er,
sem þýðir að jafnvel þótt biðminni væri músina,
við erum að segja scanf, setja streng hér
en hér gæti verið 2 bæti, það gæti verið 10 bytes, gæti það verið megabæti.
Scanf hefur ekki hugmynd um, og vegna þess að þetta er klumpur af minni
væntanlega er það ekki band enn.
Það er bara band þegar þú skrifar stafi og \ 0 til að klumpur af minni.
Nú er það bara einhver klumpur af minni.
Scanf mun ekki vita hvenær á að hætta að skrifa á þetta netfang.
>> Ef þú manst nokkur dæmi á liðnum árum þar sem ég slóst handahófi á lyklaborðinu
reyna að flæða í biðminni, og við ræddum á föstudaginn um einmitt það.
Ef að andstæðingurinn sprauta einhvern veginn inn í forritinu miklu stærri orð
eða setningu eða setningu þá var von þú getur umframmagn
a klumpur af minni, sem hægt er að hafa slæm áhrif,
eins og að taka yfir allt kerfið sjálft.
Við þurfum að laga þetta einhvern veginn.
Leyfðu mér að súmma út og fara í útgáfu 3 af þessu forriti.
Það er a lítill hluti betri.
Í þessari útgáfu, taka mismuninn.
Í línu 16, er ég aftur að lýsa yfir breytilega heitir biðminni,
en hvað er það núna?
Það er óákveðinn greinir í ensku fylking af 16 tákn.
Þetta er gott vegna þess að þetta þýðir að ég get nú sagt scanf
hér er raunveruleg klumpur af minni.
Þú getur næstum hugsa um fylki sem vera ábendingum nú,
jafnvel þótt þeir séu ekki í raun jafngildir.
Þær haga sér á annan hátt í mismunandi samhengi.
En það er vissulega raunin að biðminni vísar
16 samliggjandi chars því það er það fylki er
og hefur verið í nokkrar vikur núna.
>> Hér er ég að segja scanf hér er klumpur af minni.
Í þetta sinn, það er í raun a klumpur af minni,
en hvers vegna er þetta forrit enn virkjanlegur?
Hvað er rangt samt?
Ég hef sagt að gefa mér 16 bæti en-
[Nemandi] Hvað ef þeir slá í meira en 16?
Einmitt, hvað ef notandinn slær inn 17 stafi eða 1700 stafi?
Í staðreynd, við skulum sjá hvort við getum ekki ferð yfir þetta mistök núna.
Það er betra en ekki fullkominn.
Leyfðu mér að fara á undan og keyra gera scanf3 að þýða þetta forrit.
Leyfðu mér að hlaupa scanf3, String takk: Halló, og við virðast vera í lagi.
Leyfðu mér að reyna örlítið lengur einn, Hello there.
Jæja, við skulum gera Hello there hvernig ert þú í dag, Enter.
Getting konar heppin hér, við skulum segja halló það hvernig þú ert.
Damn það.
Jæja, svo við fengum heppinn. Við skulum sjá hvort við getum ekki lagað þetta.
Nei, það er ekki að fara að láta mig afrita.
Við skulum reyna þetta aftur.
Allt í lagi, að standa við.
Við munum sjá hversu lengi ég get þykjast að einblína á meðan enn að gera þetta.
Damn það. Það er frekar við, reyndar.
Svona.
Point gert.
>> Þetta vandræðaleg en það er líka, það er einnig einn af heimildum miklu rugli
þegar þú skrifar forrit sem hafa galla vegna þess að þeir vart sjálfir
aðeins einu sinni í a á meðan stundum.
Staðreyndin er að jafnvel ef númerið er alveg brotinn,
það gæti bara verið alveg brotinn einu sinni í a á meðan
því stundum, í raun er það sem gerist stýrikerfi úthlutar
aðeins meira minni en þú þarft í raun fyrir hvað sem ástæða,
og svo enginn annar er að nota minni rétt eftir klumpur þinn 16 stafi,
þannig að ef þú ferð í 17, 18, 19, hvað sem er, það er ekki svo stór samningur.
Nú, tölva, jafnvel ef það er ekki hrun á þeim tímapunkti,
gæti hugsanlega notað bæti númer 17 eða 18 eða 19 fyrir eitthvað annað,
á hvaða tímapunkti gögn sem þú setur þarna, að vísu of langur,
er að fara að fá plága hugsanlega af einhverjum öðrum virka.
Það er ekki endilega að fara að standa í stað,
en það mun ekki endilega valda seg kenna.
En í þessu tilfelli, enda ég loksins nóg stafi
sem ég farið í raun hluti mína af minni og bam,
stýrikerfið sagði, "Því miður, það er ekki gott, skiptingu kenna."
>> Og við skulum sjá nú ef það er hér í mínum skrá-
eftir að ég hef þessa skrá hér, algerlega.
Takið eftir að þetta er aftur kallað algerlega sorphaugur.
Það er í raun skrá sem inniheldur efni af minni forritsins þíns
á þeim stað þar sem hún hrundi,
og bara að reyna smá dæmi hér láta mig fara hér
og keyra gdb á scanf3 og þá tilgreina þriðja rök kallast algerlega,
og taka hér að ef ég lista kóðann,
við munum vera fær eins og venjulega með gdb til að byrja að ganga í gegnum þetta forrit,
og ég get keyrt það og um leið og ég högg-eins með skref stjórn í GDB-
um leið og ég högg the hugsanlega gallaðir línu eftir að slá í mikið band,
Ég skal vera fær til raunverulega þekkja það hér.
Meira um þetta, þó, í kafla varðar hugarangur algerlega
og þess háttar þannig að þú getur í raun pota í kring inni í kjarna sorphaugur
og sjá hvaða línu program mistókst þér.
Einhverjar spurningar þá á ábendingum og heimilisföng?
Því í dag um, við erum að fara að byrja að taka sem sjálfsögðum hlut að þessir hlutir eru
og við vitum nákvæmlega hvað þeir eru.
Já.
>> [Nemandi] Hvernig kemur þú ekki að setja merkið við hliðina á hluta-
Góð spurning.
Hvernig kem ég þurfti ekki að setja merkið við hliðina á eðli array eins og ég gerði áður
með flest dæmi okkar?
Stutta svarið er fylki er svolítið sérstakt.
Þú getur næstum hugsa biðminni sem raunverulega vera heimilisfang,
og það bara gerist svo að vera raunin að veldi krappi tákn
er þægindi svo að við getum farið inn krappi 0, krappi 1,
krappi 2, án þess að þurfa að nota * tákn.
Það er hluti af hvítri lygi því fylki og ábendingum
eru í raun svolítið öðruvísi, en þeir geta oft en ekki alltaf að nota jöfnum höndum.
Í stuttu máli, þegar aðgerð er von bendi til klumpur af minni,
þú getur annaðhvort fara framhjá það netfang sem var skilað með malloc,
og við munum sjá malloc aftur áður en langt, eða þú geta fara framhjá það nafn fylki.
Þú þarft ekki að gera merkið og fylki þar sem þeir eru
raun eins og viðtakandi.
Það er ein undantekning.
The hornklofum gera þá sérstaka.
>> Væri hægt að setja merkið við hliðina á biðminni?
Ekki í þessu tilfelli.
Það myndi ekki virka vegna þess, aftur, á þessu horni tilfelli
þar fylki eru ekki alveg í raun heimilisföng.
En við munum kannski koma aftur til að áður en langt með öðrum dæmum.
Við skulum reyna að leysa vandamál hér.
Við höfum gögn uppbygging sem við höfum verið að nota í nokkurn tíma þekkt sem fylki.
Tilfelli í benda, það er það sem við áttum bara.
En fylki hafa sumir upsides og downsides.
Fylki er ágætur af hverju?
Hvað er einn hlutur sem þú vilt-að því marki sem þú vilt fylki-um fylki?
Hvað er hentugt um þá? Hvað er sannfærandi?
Af hverju gerði við kynna þær í fyrsta sæti?
Já.
[Nemandi] Þeir geta geymt mikið af gögnum, og þú þarft ekki að nota allt hlutur.
Hægt er að nota hluta.
Gott, með fjölda sem þú getur geymt mikið af gögnum,
og þú þarft ekki endilega að nota allt það, þannig að þú getur overallocate,
sem gæti verið hentugt ef þú veist ekki fyrirfram hversu margir eitthvað að búast við.
>> GetString er fullkomið dæmi.
GetString, skrifað af okkur, hefur ekki hugmynd um hversu margir chars til að ætla,
svo er staðreynd að við getum tekið klumpur af samfelldu minni gott.
Fylki leysa einnig vandamál við sáum par vikum nú
þar sem númerið þitt byrjar að flytjast í eitthvað mjög illa hönnuð.
Muna að ég bjó til nemenda uppbyggingu heitir David,
og þá var það í raun og veru val, þó,
að hafa breytilega nefndi og aðra breytu sem heitir, að ég held, hús,
og annar breytu sem heitir ID vegna þess að í þeirri sögu sem ég vildi þá að kynna eitthvað annað
eins og Rob í the program, þannig að þá ákvað ég að bíða í eina mínútu,
Ég þarf að endurnefna þessar breytur.
Við skulum kalla mitt NAME1 ID1, house1.
Við skulum kalla er Rob NAME2 house2, ID2.
En bíddu í eina mínútu, hvað um Tommy?
Þá höfðum við þrjár breytur.
Við kynntum einhver annar, fjórum breytum.
Heimurinn byrjaði að fá sóðalegur mjög fljótt,
þannig að við kynntum structs, og hvað er sannfærandi um strúktúr?
Hvað er a C struct láta þig gera?
Það er í raun óþægilega dag.
Hvað? >> [Inaudible nemandi svar]
Já, sérstaklega typedef leyfir þér að búa til nýjar upplýsingar tegund,
og struct er struct leitarorð, gerir þér kleift að þjappa
hugtök sem tengjast stykki af gögnum saman
og eftir það kalla þá eitthvað eins nemanda.
>> Það var gott því að nú getum við sitja
miklu fleiri tegund af eðli samræmi hugtakið nemanda í breytu
fremur en geðþótta hafa einn fyrir band, eitt að kenni, og svo framvegis.
Fylki er gott vegna þess að þeir leyfa okkur að byrja að þrífa upp númerið okkar.
En það er ókostur nú af fjölda?
Hvað er hægt að gera ekki? Já.
[Nemandi] Þú þarft að vita hversu stór hún er.
Þú þarft að vita hversu stór hún er, svo það er góður af a sársauki.
Þessir af þú með fyrri forritun reynslu vita að í fullt af tungumálum,
eins og Java, getur þú beðið klumpur af minni, sérstaklega fylki,
hversu stór þú ert og að lengd, eign, svo að segja, og það er mjög þægilegt.
Í C, getur þú ekki einu sinni kalla strlen á almenna fjölbreytta
því strlen, sem orðið gefur til kynna, er aðeins fyrir strengi,
og er hægt að reikna út lengd band vegna þessa manna samningi
að hafa \ 0, en fylki, fleiri generically, er bara klumpur af minni.
Ef það er fylki af ints, það er ekki að fara að vera einhver sérstakur karakter
lok að bíða eftir þér.
Þú verður að muna lengd fylki.
Annar ókostur af fjölda alin höfuð sitt í GetString sig.
Hvað er annar hæðir af fylki?
Herra, bara þú og ég í dag.
[Inaudible nemandi svar] >> Það er það?
Það er lýst á mánudaginn.
Jæja, lýsti á mánudaginn. Af hverju ertu ekki eins og það?
[Nemandi] Vegna þess að það verður endurnýtt.
Það verður endurnýtt.
Jæja, ef þú notar array til að úthluta minni,
þú getur ekki, til dæmis, á að skila því það er á mánudaginn.
Jæja, það er ókostur.
Og hvernig óður í annar með fjölda?
Þegar þú skiptir það, þú ert svona ruglaður ef þú þarft meira pláss
en það fylki hefur.
>> Þá kynntum við, muna, malloc, sem gaf okkur möguleika á að breytilega úthluta minni.
En hvað ef við reyndum annar heimur með öllu?
Hvað ef við vildum leysa nokkra af þessum vandamálum
svo við stað-minn penni er sofnaður hér-
hvað ef við vildum stað að í raun búa til heim sem er ekki lengur eins og þetta?
Þetta er fylki, og, að sjálfsögðu, af þessu tagi versnar þegar við högg enda fylking,
og ég er ekki lengur pláss fyrir aðra heiltölu eða annan staf.
Hvað ef við segjum konar preemptively vel, hví ekki við slaka
Þessi krafa um að allar þessar klumpur af minni að vera samliggjandi aftur til baka,
og hvers vegna ekki, þegar ég þarf að int eða á char,
bara gefa mér pláss fyrir einn af þeim?
Og þegar ég þarf annað, gefa mér annað rúm,
og þegar ég þarf annað, gefa mér annað rúm.
Kosturinn sem nú er að ef einhver annar
tekur minni hérna, ekki máli.
Ég tek þetta viðbótar klumpur af minni hér og svo þetta.
>> Nú, aðeins grípa hér er að nánast er eins og ég hef
a heild búnt af mismunandi breytum.
Þetta er eins og fimm mismunandi breytum hugsanlega.
En hvað ef við stela hugmynd frá strengi
þar sem við tengja einhvern veginn þetta saman hugtök, og hvað ef ég gerði þetta?
Þetta er mjög illa gerður ör mín.
En geri ráð fyrir að hver þessara klumpur af minni
benti til annars, og þessi strákur, sem hefur ekkert systkini til hægri handar,
hefur ekki svo ör.
Þetta er í raun það sem er kallað tengda listanum.
Þetta er ný gögn uppbygging sem gerir okkur kleift að úthluta klumpur af minni,
þá annað, þá annað, þá annað, hvenær sem við viljum
á dagskrá, og við muna að þeir eru allir einhvern veginn tengjast
við bókstaflega chaining þá saman, og við gerðum það pictorially hér með ör.
En í kóða, hvað væri vélbúnaður með sem þú getur einhvern veginn að tengja,
næstum eins og grunni, einn klumpur til annars klumpur?
Við gætum notað músina, ekki satt?
Vegna raun ör sem er að gerast í vinstra veldi,
þessi strákur hér til þessa, gæti innihaldið innan þessa torginu
ekki bara ints, ekki bara bleikju, en hvað ef ég úthlutað í raun
smá auka pláss svo að nú,
hvert klumpur mín minni, jafnvel þótt það sé að fara að kosta mig,
nú lítur svolítið meira rétthyrnd þar einn klumpur af minni
er notað til að tala, eins og númer 1,
og þá ef þetta strákur geymir númer 2,
Þessi annar klumpur af minni er notað fyrir örina,
eða fleiri concretely, bendi.
Og ætla ég að geyma númer 3 hérna á meðan ég nota þetta til að benda á að þessi strákur,
og nú þessi strákur, við skulum gera ráð fyrir að ég vil aðeins þrjár slíkar klumpur af minni.
Ég draga línu í gegnum að kynna null.
Það er engin viðbótar staf.
>> Reyndar, þetta er hvernig við getum farið um framkvæmd
eitthvað sem er kallað tengda listanum.
A tengda listanum er ný gögn uppbygging, og það er a stepping steinn til
miklu áhugamaður gögn uppbygging sem byrja að leysa vandamál
sömu nótum og Facebook-gerð vandamál og Google-gerð vandamál
þar sem þú hefur mikið gagnagrunna, og það ekki lengur sker það
að geyma allt contiguously og nota eitthvað eins og línuleg leit
eða jafnvel eitthvað eins og tvöfaldur leit.
Þú vilt jafnvel betri gangi sinnum.
Í raun einn af heilögum Grails við munum tala um síðar í þessari viku eða næstu
er reiknirit sem keyra tími fasti.
Með öðrum orðum, það tekur alltaf sama tíma sama
hversu stór inntak er, en það myndi örugglega vera sannfærandi,
jafnvel meira svo en eitthvað lógaritmískum.
Hvað er þetta á skjánum hér?
Hver ferhyrninga er einmitt það sem ég teiknaði bara með höndunum.
En málið alla leið til vinstri er sérstök breyta.
Það er að fara að vera einn músina því einn Gotcha
með tengda lista, sem þessir hlutir eru kallaðir,
er að þú þarft að hanga á öðrum enda tengda listanum.
>> Rétt eins og með streng, þú þarft að vita um heimilisfang fyrstu bleikju.
Sami samningur fyrir tengd listum.
Þú þarft að vita um heimilisfang fyrsta klumpur af minni
því þaðan, getur þú náð í hvert hitt.
Hæðir.
Hvaða verð erum við að borga fyrir þessa fjölhæfni að hafa breytilega
umtalsverðar gögn uppbygging að ef við þurfum alltaf meira minni, allt í lagi,
bara úthluta eitt klumpur og draga músina frá
gamla í nýja hala á listanum?
Já.
[Nemandi] Það tekur um það bil tvöfalt mikið pláss.
Það tekur tvöfalt meira pláss, svo það er örugglega ókostur, og við höfum séð þetta
tradeoff fyrir milli tíma og rúmi og sveigjanleika
Þegar nú þurfum við ekki 32 bita fyrir hvert af þessum tölum.
Við þurfum í raun 64, 32 fyrir fjölda og 32 fyrir músina.
En hey, ég hef 2 gígabæta vinnsluminni.
Bæta við öðru 32 bita hér og hér virðist ekki það stór af a samningur.
En stóra gagnagrunna, bætir það örugglega allt að bókstaflega tvöfalt meira.
Hvað er annar hæðir nú, eða hvað lögun gefa okkur upp,
Ef við komum fram lista af hlutum með tengda listanum og ekki array?
[Nemandi] Þú getur ekki fara yfir það aftur.
Þú getur ekki fara yfir það aftur, þannig að þú ert góður af ruglaður ef þú ert að ganga
frá vinstri til hægri með því að nota a for lykkju eða meðan lykkja
og þá átta sig, "Oh, ég vil fara aftur til the byrjun af the listi."
Þú getur ekki vegna þess að þessar ábendingar fara aðeins frá vinstri til hægri eins og örvarnar sýna.
>> Nú, getur þú manst upphaf listann við aðra breytu,
en það er flókið að hafa í huga.
An array, sama hversu langt þú ferð, þú getur alltaf gert mínus, mínus, mínus, mínus
og fara aftur þaðan sem þú komst.
Hvað er annar hæðir hér? Já.
[Inaudible nemandi spurning]
Þú getur, svo þú hefur í raun bara lagt til gögn uppbygging kallast tvöfalt tengist lista,
og örugglega, myndir þú bæta við öðru bendi öllum þessum ferhyrninga
það fer hina áttina, að kosti þeirra
er nú hægt að fara fram og til baka,
hæðir sem er þú nú ert að nota þrisvar sinnum eins mikið minni og áður
og einnig að bæta flókið í skilmálar af kóða sem þú þarft að skrifa til að fá það rétt.
En þetta eru allt kannski mjög sanngjarn Tradeoffs, ef viðsnúningur er enn mikilvægara.
Já.
[Nemandi] Þú getur líka ekki 2D tengda listanum.
Gott, getur þú í raun ekki hafa a 2D tengda listanum.
Þú gætir. Það er ekki nærri eins auðvelt og fylki.
Eins og fjölda, þú opna krappi, lokað BRACKET, opið krappi, lokuð krappi,
og þú færð smá 2-víddar uppbygging.
Þú getur innleiða 2-víddar tengda listanum
ef þú bæta við-eins og þú lagt-þriðja bendi öllum þessum hlutum,
og ef þú hugsa um annan lista sem koma á þig 3D stíl
frá skjánum til að okkur öllum, sem er bara önnur keðja af einhverju tagi.
Við gætum gert það, en það er ekki eins einfalt og slá opinn krappi, ferningur krappi. Já.
[Inaudible nemandi spurning]
Gott, þannig að þetta er alvöru kicker.
>> Þetta reiknirit sem við höfum pined yfir, eins og ó, leit tvöfaldur,
þú getur leitað að fjölda tölur á borð
eða símaskránni svo miklu hraðar ef þú notar skipta og sigra
og tvöfaldur leit reiknirit, en tvöfaldur leita þarf tvær forsendur.
Einn, sem gagna var raðað.
Nú getum við væntanlega halda þessu raðað,
svo kannski það er ekki áhyggjuefni, en tvöfaldur leita einnig gert ráð fyrir
að þú hefðir handahófi aðgang að lista yfir númer,
og fylki leyfa þér að hafa handahófi aðgang, og af handahófi aðgang,
Ég meina ef þú ert að gefa fylki, hversu mikinn tíma tekur það þig
að fá að krappi 0?
Eina aðgerð, þú notar bara [0] og þú ert rétt þar.
Hversu mörg skref tekur það að fá að stað 10?
Eitt skref, fara bara að [10] og að þú ert þarna.
Á hinn bóginn, hvernig gera þú fá til 10 heiltölu í tengda listanum?
Þú þarft að byrja á byrjun þar sem að þú ert bara að muna
upphafið að tengist lista, rétt eins og streng er minnst
með heimilisfang fyrstu bleikju þess, og til að finna þessi 10 int
eða að 10 staf í streng, þú þarft að leita á öllum fjandinn hlutur.
>> Aftur, við erum ekki að leysa öll vandamál okkar.
Við erum að kynna nýjar, en það fer alveg eftir hvað þú ert að reyna að hanna fyrir.
Hvað varðar framkvæmd þessa getum við lánað hugmynd frá að nemandi uppbyggingu.
The setningafræði er mjög svipuð, en nú er hugmyndin er svolítið abstrakt
en hús og nafn og kt.
En ég leggja til að við gætum haft gögn uppbygging í C
sem kallast hnút, og síðasta orð á mynd gefur til kynna,
inni í hnút, og hnúturinn er bara almenn gámur í tölvunarfræði.
Það er venjulega dregin sem hring eða ferning eða rétthyrning sem við höfum gert.
Og í þessum gögnum uppbyggingu, höfum við int, N,
þannig að fjöldi ég vil geyma.
En hvað er þetta annað lína, struct hnút * næst?
Hvers vegna er þetta rétt, eða hvaða hlutverk er þetta sem spila,
jafnvel þó að það sé svolítið dulinn við fyrstu sýn?
Já.
[Inaudible nemandi svar]
Einmitt, þannig að * konar gleðispillir að það bendi á einhvers konar.
Nafn þessa bendillinn er geðþótta næst,
en við hefðum getað kallað það eitthvað sem við viljum, en hvað hefur þetta bendillinn benda til?
[Nemandi] Annar hnútur. >> Einmitt, bendir það til annars slíks hnút.
>> Nú, þetta er tegund af forvitni C.
Muna að C er lesið af þýðanda toppur til botn, vinstri til hægri,
sem þýðir ef-þetta er lítið annað en það sem við gerðum við nemanda.
Þegar við skilgreint nemanda, í raun við ekki setja orð þarna.
Það sagði bara typedef.
Þá höfðum við int id, String nafn, band hús,
og þá nemandi neðst á strúktúr.
Þessi yfirlýsing er svolítið öðruvísi vegna þess,
aftur, C þýðandi er dálítið heimsk.
Það er bara að fara að lesa toppur til botn,
þannig að ef það nær 2 línu hér
þar næst er lýst og það sér, ó, hér er breytu sem heitir Next.
Það bendi til að strúktúrinn hnút.
The þýðanda er að fara að átta sig á hvað er struct hnút?
Ég hef aldrei heyrt um þetta verk áður,
vegna þess að orðið hnút gæti ekki annað birtast
þar til botn, svo það er þetta offramboð.
Þú þarft að segja struct hnút hér, sem þú getur þá stytt síðar
takk typedef niður hér, en þetta er vegna þess að
við erum að vísa uppbyggingu sig inni í byggingu.
Það er einn Gotcha þar.
>> Nokkrar áhugaverðar vandamál eru að fara að koma.
Við höfum fengið lista yfir númer. Hvernig setja okkur inn í það?
Hvernig leita við það? Hvernig eyði við af því?
Sérstaklega nú að við verðum að stjórna öllum þessum ábendingum.
Þú hélt ábendingar voru konar hugur-beygja
þegar þú hefðir einn af þeim að reyna bara að lesa int til þess.
Nú verðum við að vinna virði heilan lista er.
Hvers vegna eigum við ekki að taka 5-mínútna hlé okkar hér, og þá munum við koma
sumir gott fólk upp á svið til að gera einmitt það.
>> C er miklu skemmtilegra þegar það er aðhafst út.
Hver myndi bókstaflega eins og að vera fyrstur?
Jæja, koma upp. Þú ert fyrst.
Hver vill vera 9? Allt í lagi, 9.
Hvernig óður í 9? 17?
Smá klíku hér. 22 og 26 í þeirri fremstu röð.
Og þá hvernig um einhvern þarna verið bent á.
Þú ert 34. Jæja, 34, koma upp.
Fyrst er þarna. Jæja, allir fjórir ykkur.
Og hver var við að segja fyrir 9?
Hver er 9 okkar?
Hver vill í raun að vera 9? Allt í lagi, komdu, vera 9.
Hér förum.
34, munum við hitta þig þarna.
Í fyrsta hluta er að þér að líta svona.
26, 22, 17, gott.
Ef þú getur staðið á til hliðar, vegna þess að við erum að fara að malloc þér í smá stund.
>> Gott, gott.
Jæja, frábært, þannig að við skulum spyrja nokkrar spurningar hér.
Og í raun, hvað er nafnið þitt? >> Anita.
Anita, allt í lagi, komdu hérna.
Anita er að fara að hjálpa okkur að leysa svona eitt nokkuð einfaldri spurningu í fyrsta,
sem er hvernig þú finnur hvort tala er á listanum?
Nú, eftir að fyrsta, fulltrúi hér með Lucas,
er svolítið öðruvísi, og svo er stykki hans pappír vísvitandi hliðar
því það er ekki alveg eins mikill og ekki taka upp eins margar bita,
jafnvel þótt tæknilega hefur hann sömu stærð af pappír bara snúið.
En hann er svolítið öðruvísi því að hann er aðeins 32 bita fyrir músina,
og allir þessir gaurar eru 64 bitar, helmingur sem er fjöldi, helmingur sem er bendi.
En bendillinn er ekki lýst, þannig að ef þið gætu nokkuð awkwardly
nota vinstri hendina til að benda á mann við hliðina á þér.
Og þú ert númer 34. Hvað er nafn þitt?
Ari.
Ari, svo í raun, halda pappír í hægri hendi þinni, og vinstri hönd fer beint niður.
Þú tákna null vinstri.
>> Nú er mönnum mynd okkar mjög stöðug.
Þetta er í raun hvernig ábendingum vinna.
Og ef þú getur scrunch svolítið með þessum hætti þannig að ég er ekki í vegi þínum.
Anita hér, finna mér númer 22,
en gera ráð fyrir þvingun af ekki menn halda upp stykki af pappír,
en þetta er listi, og þú hefur aðeins Lucas til að byrja með
vegna þess að hann er bókstaflega fyrsta músina.
Segjum að þú sjálfur ert músina, og svo þú hefur líka möguleika á að benda á eitthvað.
Af hverju ertu ekki að byrja á því að benda á nákvæmlega hvað Lucas er að benda á?
Gott, og láta mig enact þetta út hérna.
Bara fyrir sakir umræðu, láta mig draga upp auða síðu hérna.
Hvernig stafa þú nafnið þitt? >> Anita.
Allt í lagi, Anita.
Segjum hnút * Anita = Lucas.
Jæja, eigum við ekki að hringja í þig Lucas. Við ættum að hringja fyrst.
Hvers vegna er þetta í raun í samræmi við raunveruleikann hér?
Einn, fyrsta er þegar til.
Fyrst hefur verið úthlutað væntanlega einhvers staðar hérna.
Hnútur * fyrst, og það hefur verið úthlutað til lista einhvern veginn.
Ég veit ekki hvernig það gerðist. Það gerðist áður en flokkur byrjaði.
Þetta tengist listi af mönnum hefur verið búin til.
Og nú á þessum tímapunkti í sögunni-þetta er allt að fara á Facebook virðist síðar-
á þessum tímapunkti í sögunni, hefur Anita verið frumstilla að vera jöfn fyrstu,
sem þýðir ekki að Anita stig á Lucas.
Frekar bendir hún á það sem hann bendir á
vegna þess að sama netfang sem er innan 32 bita Lucas er - 1, 2, 3 -
er nú einnig innan 32 bita Anita er - 1, 2, 3.
>> Nú finna 22. Hvernig myndir þú fara að gera þetta?
Hvað er það? >> Point til hvað.
Benda á hvað, svo fara á undan og starfa það út eins og besta sem þú getur hér.
Gott, gott, og nú þú ert að benda á-hvað er nafnið þitt með 22?
Ramon. >> Ramon, svo Ramon er að halda upp 22.
Þú hefur nú gert ávísun.
Er Ramon == 22, og ef svo er, til dæmis, við getum aftur satt.
Leyfðu mér-en þessir krakkar standa hér nokkuð awkwardly-
Leyfðu mér að gera eitthvað fljótt eins bool finna.
Ég ætla að fara á undan og segja (hnút * listi, int n).
Ég kem aftur með ykkur. Ég er bara að skrifa nokkur númer.
Og nú ætla ég að fara á undan og gera þetta, hnúturinn * Anita = lista.
Og ég ætla að halda áfram og segja að á meðan (Anita! = NULL).
>> The samlíking hér að hafa smá strekkt, en á meðan (Anita! = NULL), hvað ég vil gera?
Mig vantar leið til að vísa
er heiltala sem Anita er að benda á.
Í the fortíð, þegar við höfðum mannvirki, sem hnúturinn er,
við notuðum punktur tákn, og við myndum segja eitthvað eins og
anita.n, en vandamálið hér er að Anita er ekki strúktúr í sjálfu.
Hvað er hún?
Hún er músina, svo í raun, ef við viljum nota þetta punktur tákn-
og þetta er að fara að líta vísvitandi smá Cryptic-
við verðum að gera eitthvað eins og að fara til vinstri handar hvað Anita er að benda á
og þá fá á sviði sem kallast n.
Anita er músina, en það er * Anita?
Hvað finnst þér þegar þú ferð til hvað Anita er að benda á?
A struct, hnút, og hnút, muna, er reit sem heitir N
vegna þess að það er, man, þessar 2 svið, við hliðina og n,
sem við sáum í smá stund síðan hérna.
>> Til að í raun líkja þessu í kóða,
við gætum gert þetta og segja að ef ((* Anita). N == N) N sem ég er að leita að.
Takið eftir að fallið var samþykkt í fjölda mér þykir vænt um.
Þá get ég farið á undan og gera eitthvað eins og aftur sanna.
Annars, ef það er ekki málið, hvað ég vil gera?
Hvernig þýða ég að kóða það Anita gerði svo innsæi með því að ganga í gegnum listann?
Hvað ætti ég að gera upp hér til að líkja Anita taka þessi skref til vinstri, þessi skref til vinstri?
[Inaudible nemandi svar] >> Hvað er það?
[Inaudible nemandi svar]
Gott, ekki slæm hugmynd, en í fortíðinni, þegar við höfum gert þetta, höfum við gert Anita + +
vegna þess að það myndi bæta númer 1 til Anita,
sem myndi gjarnan benda á næsta mann, eins og Ramon,
eða sá sem við hliðina á honum, eða við hliðina á honum maður niður línu.
En það er ekki alveg gott hér vegna þess að það er þetta sem líta út eins og í minni?
Ekki. Við verðum að gera það.
Það lítur út eins og þetta í minni, og jafnvel þó að ég hef dregið 1 og 2 og 3 nálægt hvort öðru,
ef við líkja virkilega þetta-getur þú krakkar, en samt benda á sama fólkið,
geta sumir ykkar taka af handahófi skref til baka, sumir af þú að handahófi skref fram?
>> Þessi sóðaskapur er enn tengd lista,
en þessir krakkar gætu verið hvar sem er í minni,
svo Anita + + er ekki að fara að vinna af hverju?
Hvað er á staðsetningu Anita + +?
Hver veit.
Það er einhver önnur gildi sem bara gerist svo að vera milligöngu
meðal allra þessara hnúður fyrir tilviljun vegna þess að við erum ekki með fylki.
Við úthlutað hvert þessara tengipunkta sig.
Jæja, ef þú krakkar geta hreinsa ykkur aftur upp.
Leyfðu mér að leggja til að í stað þess að Anita + +, við gerum í staðinn Anita fær-
Jæja, af hverju ekki við að fara til hvað Anita er að benda á og þá gera. næst?
Með öðrum orðum, förum við í Ramon, sem er að halda fjölda 22,
og þá. næsta er eins og Anita væri afritun vinstri músina sína.
En hún vildi ekki fara lengra en Ramon því við fundum 22.
En það væri hugmynd. Nú, þetta er Guð-hræðilegt sóðaskapur.
Heiðarlega, enginn mun nokkru sinni muna þessa setningafræði, og svo sem betur fer,
það er í raun lítið vísvitandi-ó, þú ekki raunverulega sjá hvað ég skrifaði.
Það væri meira sannfærandi ef þú gætir. Voila!
>> Á bak við tjöldin, ég var að leysa vandamál með þessum hætti.
Anita, að taka þessi skref til vinstri,
fyrst, eigum við að fara á það heimilisfang sem Anita er að benda á
og þar sem hún finnur ekki aðeins N, sem við köflóttur bara fyrir sakir samanburður er,
en þú verður einnig að finna næsta - í þessu tilviki,
Vinstri hönd Ramon er að benda á næsta hnút á listanum.
En þetta er Guð-hræðilegt sóðaskapur sem ég vísað áðan,
en það kemur í ljós C leyfir okkur að einfalda þetta.
Í stað þess að skrifa (* Anita), getum við í staðinn bara skrifa Anita-> n,
og það er nákvæmlega sama virka, en það er miklu meira innsæi,
og það er mikið meira í samræmi við mynd sem við höfum verið að teikna
allan þennan tíma með því að nota örvarnar.
>> Loks gera það sem við þurfum að gera í lok þessarar áætlunar?
Það er ein lína af kóða sem eftir er.
Return hvað?
False, því ef við komumst í gegnum allt á meðan lykkja
og Anita er í raun, null, það þýðir að hún fór alla leið til the endir af the listi
þar sem hún var að benda á-hvað heitirðu aftur?
Vinstri Ari. >> Ara er hönd, sem er null.
Anita er nú null, og ég grein fyrir að þú ert bara að standa hér awkwardly í Limbó
því ég er að fara burt á eintal hérna,
en við munum taka þig aftur í bara smá stund.
Anita er núll á þeim tímapunkti í sögunni, þannig að á meðan lykkja lýkur,
og við verðum að fara aftur rangt því ef hún fékk alla leið til null músina Ari er
þá var engin tala sem hún leitaði í listanum.
Við getum hreinsa þetta upp líka, en þetta er mjög góð framkvæmd þá
á traversal virka, finna virka fyrir tengda listanum.
Það er enn línuleg leit, en það er ekki eins einfalt eins og + + bendi
eða + + sem ég breyta því að nú getum við ekki giska
þar sem hver þessara hnútar eru í minni.
Við verðum að bókstaflega fylgja slóð af breadcrumbs eða, nánar tiltekið,
ábendingum, til að komast frá einum hnút til annars.
>> Nú skulum reyna annað. Anita, viltu koma aftur hingað?
Hvers vegna eigum við ekki að fara á undan og veita einn viðmælandann frá áhorfendum?
Malloc-hvað er nafnið þitt? >> Rebecca.
Rebecca. Rebecca hefur verið malloced frá áhorfendum,
og hún er nú að geyma fjölda 55.
Og markmiðið á móti er nú að Anita að setja
Rebecca í tengda listanum hér í viðeigandi stað.
Komdu hérna í smástund.
Ég hef gert eitthvað eins og this.
Ég hef gert hnút *. Og hvað er nafnið þitt aftur?
Rebecca. >> Rebecca, allt í lagi.
Rebecca fær malloc (sizeof (hnút)).
Rétt eins og við höfum úthlutað hluti eins og nemendur og whatnot í fortíðinni,
við þurfum að stærð hnút, svo nú Rebecca
er að benda á það?
Rebecca hefur tvær sviðum inni í henni, einn sem er 55.
Við skulum gera það, Rebecca-> = 55.
En svo Rebecca-> Næsta ætti að-eins núna, hönd hennar er góður hver veit?
Það er að benda á einhverjum sorp gildi, svo hvers vegna ekki gott mál
við gerum amk þetta þannig að vinstri hönd er nú við hlið hennar.
Nú Anita, taka það áfram.
Þú hefur Rebecca hafði verið úthlutað.
Fara á undan og finna hvar við ættum að setja Rebecca.
Gott, mjög gott.
Jæja, gott, og nú þurfum við að bjóða upp á smá leiðsögn,
svo að þú hafir náð Ari.
Vinstri hönd hans er núll, en Rebecca greinilega tilheyrir hægri,
svo hvernig verðum við að breyta þessu tengda listanum
í því skyni að setja Rebecca í viðeigandi stað?
Ef þú gætir bókstaflega færa vinstri hendur fólks í kring eins og þörf er á,
Við munum laga vandamál þannig.
Jæja, gott, og á meðan, vinstri hönd Rebekku er nú við hlið hennar.
>> Það var of auðvelt.
Við skulum reyna að úthlutun-we're næstum búin, 20.
Jæja, koma upp.
20 hefur verið úthlutað, svo látið mig fara á undan og segja aftur hér
við höfum bara gert hnút * Saad.
Við höfum malloc (sizeof (hnút)).
Við gerum þá sama nákvæmlega setningafræði eins og við gerðum áður en fyrir 20,
og ég ætla að gera næst = NULL, og nú er komið að Anita
að setja þig inn í tengda listanum, ef þú gætir spilað það nákvæmlega sama hlutverki.
Keyra.
Allt í lagi, gott.
Nú hugsa vandlega áður en þú byrjar að færa vinstri hönd í kring.
Þú fékk langmest óþægilega hlutverk í dag.
Skal hvers hönd flutt fyrst?
Jæja, bíddu, ég er að heyra sumir ekki er.
Ef sumir gott fólk myndi kurteislega eins og að hjálpa til að leysa óþægilega ástand hér.
Vinstri hönd Hvers ætti að uppfæra fyrst kannski? Já.
[Nemandi] er Saad.
Jæja, er Saad, hvers vegna, þó?
[Inaudible nemandi svar]
Gott, vegna þess að ef við færa-hvað er nafnið þitt? >> Marshall.
Marshall, ef við færa höndina fyrst niður að núll,
nú höfum við bókstaflega munaðarlaus fjóra menn á þessum lista
því að hann var sá eini sem bendir á Ramon og allir til vinstri,
svo að uppfæra það bendi fyrst var slæmt.
Við skulum losa það.
Gott, og nú fara á undan og færa viðeigandi vinstri hönd sem vísar á Ramon.
Þetta finnst smá óþarfi.
Nú er það tveir menn benda á Ramon, en það er allt í lagi
því nú hvernig annars er hægt að uppfæra við listann?
Hvað hins vegar þarf að færa?
Excellent, nú höfum við tapað öllum minni?
Nei, svo gott, við skulum sjá hvort við getum ekki bætt þetta einu sinni enn.
>> Mallocing eitt síðasta skipti, númer 5.
Alla leið í bakið, koma niður.
Það er mjög spennandi.
[Lófaklapp]
Hvað er nafn þitt? >> Ron.
Ron, allt í lagi, þú ert malloced sem númer 5.
Við höfum bara keyrð kóða sem er nánast eins og þessi
með bara öðru nafni.
Excellent.
Nú, Anita, gangi þér vel að setja númer 5 í listanum núna.
Gott, og?
Frábært, þannig að þetta er í raun þriðja þriggja öllum tilvikum.
Við áttum fyrst einhver í árslok, Rebecca.
Við fórum svo í einhvern í miðju.
Nú höfum við einhvern í upphafi, og í þessu dæmi,
við þurftum nú að uppfæra Lucas í fyrsta sinn
vegna þess að fyrsti þáttur á listanum nú að benda á nýjan hnút,
sem aftur á móti, er að benda á hnút númer 9..
>> Þetta var gríðarlega óþægilega sýning, ég er viss,
svo stór umferð lófaklapp fyrir þessar krakkar ef þú gætir.
Fallega gert.
Það er allt. Þú getur haldið stykki af pappír sem lítið minni.
Það kemur í ljós að gera þetta í kóða
er ekki alveg eins einfalt og bara að færa allt í kring
og bendir ábendingum á mismunandi hlutum.
En átta sig á að þegar það kemur tími til að framkvæma eitthvað eins og
a tengda listanum eða afbrigði af henni ef þú leggir áherslu á mjög
þessar helstu grundvallaratriði, að bit-stærð vandamál ég þarf að reikna út,
er það þessi hönd eða þetta vegar grein fyrir því að það sé annars nokkuð flókið forrit
getur í raun að minnka nokkuð einföld byggja blokkir eins og þetta.
>> Við skulum taka það í flóknari átt enn.
Við höfum nú hugmyndina um tengda lista.
Vér-takk fyrir tillögu þangað aftur-a tvöfalt tengist lista,
sem lítur nánast eins, en nú höfum við tvo punkta inni á strúktúr
í staðinn fyrir eitt, og við gætum líklega kalla þær ábendingar fyrri og næsta
eða til vinstri eða hægri, en við gerum, í raun þarf tvær þeirra.
Kóðinn myndi vera a lítill fleiri þátt.
Anita hefði þurft að gera meiri vinnu hér á sviðinu.
En við gætum vissulega innleiða svona byggingu.
Hvað varðar að keyra tíma, þó, hvað væri í gangi tíma
fyrir Anita að finna númer n í tengda listanum núna?
Enn stór O n, þannig að það er ekkert betra en línuleg leit.
Við getum ekki gert tvöfaldur leita, þó, aftur.
Hvers vegna var það málið? Þú getur ekki hoppað í kring.
Jafnvel þó að við sjáum augljóslega alla menn á sviðinu,
og Anita gæti hafa eyeballed það og sagði: "Hér er um miðja lista,"
hún myndi ekki vita að ef hún væri tölvuforrit
vegna þess að eina sem hún þurfti að latch á að í upphafi atburðarás
var Lucas, sem var fyrsta músina.
Hún vildi endilega að fylgja þessum tenglum,
telja leið hennar þangað til hún fann það bil í miðju,
og jafnvel þá, er hún ekki að fara að vita þegar hún er komin á miðju
nema hún fer alla leið til enda til að reikna út hversu margir eru,
þá backtracks, og að of væri erfitt nema þú hefðir
a tvöfalt tengdur listi af einhverju tagi.
>> Leysa nokkur vandamál í dag, en kynna öðrum.
Hvað um mismunandi gögn uppbygging samtals?
Þetta er mynd af stæði í Mather House,
og í þessu tilfelli, við höfum gögn uppbygging við höfum konar einnig verið að tala um.
Við ræddum um stafla í tengslum við minni,
og það er tegund af vísvitandi hét því að stafla í skilmálar af minni
er í raun gögn uppbygging sem hefur fleiri og fleiri efni lagskipt ofan á það.
En áhugaverður hlutur óður í stafla, eins og raunin er í raun og veru,
er að það er sérstakt konar gögn uppbygging.
Það er gögn uppbygging þar sem fyrsti þáttur í
er síðasta þáttur út.
Ef þú ert í fyrsta bakki til að setja inn á mánudaginn,
þú ert að fara að vera því miður síðasta bakkanum til að taka burt á mánudaginn,
og það er ekki endilega gott.
Hins vegar er hægt að hugsa um það á hinn veginn,
síðast í er fyrsta út.
>> Nú, ekki allir aðstæður koma upp í hugann þar sem hafa stafla
gögn uppbygging þar sem þú ert að eign
af síðasta, fyrst út, er í raun sannfærandi?
Er það góður hlutur? Er það slæmt?
Það er ákveðið a slæmur hlutur ef stæði væru ekki allir eins
og þeir voru allir sérstakar mismunandi litum eða whatnot,
og liturinn sem þú vilt er alveg neðst.
Auðvitað getur þú ekki fengið það án mikillar fyrirhafnar.
Þú þarft að byrja efst og vinna þig niður.
Á sama hátt, hvað ef þú værir einn af þessum aðdáandi stráka
sem bíður upp alla nóttina að reyna að fá iPhone og línur upp
á stað eins og þetta?
Væri ekki gaman ef Apple Store
voru gögn stakkur uppbyggingu?
Yay? Nay?
Það er bara gott fyrir fólk sem mæta á síðustu mögulegt mínútu
og þá fá grænt af biðröð.
Og í raun, sú staðreynd að ég var svo hneigðist að segja biðröð
er í raun í samræmi við það sem við myndum kalla þessa tegund af gögn uppbygging,
einn í raun, þar sem röð skiptir máli,
og þú vilt að fyrsta til að vera sá fyrsti úr
ef aðeins fyrir sakir manna sanngirni.
Við munum almennt kalla að gögn biðröð uppbygging.
>> Það kemur í ljós að auki tengd listum, getum við byrjað að nota þessar sömu undirstöðu hugmyndir
og byrja að búa til ný og mismunandi gerðir af lausnum á vandamálum.
Til dæmis, í tilviki stafla, gætum við hönd stafla
nota gögn uppbygging eins og þetta, myndi ég leggja til.
Í þessu tilfelli, hef ég lýst struct, og ég hef sagt innan þessa uppbyggingu
er fylki af númerum og þá breytu sem heitir stærð,
og ég er að fara að kalla þetta sem stafla.
Nú, af hverju virkar þetta í raun?
Í tilviki stafla, gæti ég draga þetta í raun á skjánum sem fylki.
Hér er stakkur minn. Þeir eru númer.
Og við munum draga þá eins og þetta, þetta, þetta, þetta, þetta.
Og þá hef ég eitthvað annað gögn meðlimur hér,
sem heitir stærð, þannig að þetta er stærð, og það er númer,
og sameiginlega, allt iPad hér er ein stakkur uppbyggingu.
Nú, við vanræksla, stærð hefur væntanlega fengið að frumstilla til 0,
og hvað er inni í array af tölum í upphafi
þegar ég úthluta fyrsta fylki?
Sorp. Hver veit? Og það skiptir í raun ekki máli.
Það skiptir ekki máli hvort það er 1, 2, 3, 4, 5, alveg af handahófi
með óheppni geymd í uppbyggingu minni vegna þess að svo lengi sem ég veit að stærð stafla
er 0, svo ég veit programmatically, ekki horfa á einhver atriði í fylki.
Það skiptir ekki máli hvað er þarna.
Ekki líta á þá, eins og væri vísbendingu um stærð 0.
>> En býst nú ég fara á undan og setja eitthvað inn í stafla.
Mig langar til að setja númer 5, þannig að ég setti númer 5 hér,
og hvað þá set ég hérna?
Nú myndi ég reyndar setja niður 1 fyrir stærð,
og nú er stafla stærð 1.
Hvað ef ég fer á undan og setja númerið, við skulum segja, 7 næst?
Þetta þá verður uppfærð til 2, og þá munum við gera 9,
og þá verður uppfærð 3.
En áhugaverður lögun nú þessa stafla er að
Ég ætlast til að fjarlægja hvaða þáttur ef ég vil skjóta
eitthvað burt af á mánudaginn, svo að segja?
9 myndi vera the fyrstur hlutur til að fara.
Hvernig ætti myndin að breyta ef ég vil skjóta stak af á mánudaginn,
Líkt og bakka í Mather?
Já. >> [Nemandi] Stilla stærð til 2.
Einmitt, er allt sem ég set stærð við 2, og hvað á ég að gera með fjölda?
Ég þarf ekki að gera neitt.
Ég gæti, bara til að vera anal, setja 0 þar eða a -1 eða eitthvað til að signify
að þetta er ekki legit gildi, en það skiptir ekki máli því
Ég get tekið utan fylkisins sig hversu lengi hún er
þannig að ég veit aðeins líta á fyrstu tvö atriði í þessu fylki.
Nú, ef ég fer og bæta númer 8 við þennan fjölda, hvernig virkar myndin breytist næst?
Þetta verður 8, og þetta verður 3.
Ég er að skera nokkrar horn hér.
Nú höfum við 5, 7, 8, og við erum aftur í stærð 3.
Þetta er frekar einfalt að framkvæma,
en þegar við erum að fara að sjá þessa hönnun ákvörðun?
Hvenær byrjar það að fara mjög, mjög rangt? Já.
[Inaudible nemandi svar]
Þegar þú vilt fara til baka og fá fyrsta þáttur sem þú setur inn
>> Það kemur í ljós hérna þó stafla er fylki undir hetta,
þessi gögn uppbygging sem við höfum byrjað að tala um eru einnig almennt þekktur sem
abstract gagnauppbyggingu þar hvernig þeir eru til framkvæmda
er alveg fyrir utan lið.
A gögn uppbygging eins og stafla er ætlað að bæta við stuðning
starfsemi eins og ýta, sem ýtir á bakka inn á mánudaginn,
og popp, sem fjarlægir stak af á mánudaginn, og það er það.
Ef þú varst að sækja kóða einhvers annars sem nú þegar innleitt
þetta hlutur sem kallast stafla, sem maður hefði skrifað
aðeins tvo valkosti fyrir þig, ýta og popp, sem tilgangurinn í lífinu
væri að gera einmitt það.
Þú eða hann eða hana, sem framkvæmd þessi forrit
hefði verið alveg einn að ákveða hvernig á að framkvæma
merkingarfræði þrýsta og pabbi undir hetta
eða virkni þrýsta og pabbi.
Og ég hef gert nokkuð skammsýn ákvörðun hér
með því að innleiða stafla mitt við þessari einföldu gögn uppbygging hvers vegna?
Hvenær þessi gögn uppbyggingu brot?
Á hvaða atriði þarf ég að skila villu þegar notandi kallar ýta, til dæmis?
[Nemandi] Ef það er ekki meira pláss.
Einmitt, ef það er ekki meira pláss, ef ég hef farið yfir getu,
sem er öllum húfur því það bendir til þess að það er einhvers konar alheims fasti.
Jæja, þá er ég bara að fara að segja, "Því miður, ég get ekki ýta annað gildi
inn á mánudaginn, "mikið eins og í Mather.
>> Á einhverjum tímapunkti, þá eru þeir að fara til högg the toppur hluti af þeim litla skáp.
Það er ekkert meira pláss eða getu á mánudaginn, á hver benda að það er einhvers konar villa.
Þeir verða að setja á hluti annars staðar, bakkanum annars staðar,
eða hvergi á öllum.
Nú, með biðröð, gætum við koma það er öðruvísi lítið.
A biðröð er svolítið öðruvísi í því undir hetta, það getur verið hrint í framkvæmd
sem fjölda, en hvers vegna, í þessu tilfelli er ég að leggja
einnig hafa höfuð þáttur tákna höfuð listanum
framan á listanum, fyrsta manneskjan í samræmi við Apple verslun, auk stærð?
Hvers vegna þarf ég að viðbótar gögnum og hér?
Hugsaðu til baka hvað númer er
ef ég hef dregið það sem hér segir.
Segjum þetta er nú biðröð stað mánudaginn,
Munurinn er-bara eins og Apple Store-biðröð er sanngjörn.
Fyrsti maður í samræmi við upphaf listanum, númer 5 í þessu tilviki,
hann eða hún er að fara að láta inn í búðina fyrst.
Við skulum gera það.
Segjum að þetta sé ástand biðröð mínum á þessari stundu í tíma, og nú er Apple Store
opnast og fyrsta manneskjan, númer 5, er leitt inn í búðina.
Hvernig breyti ég mynd nú að ég hef de-biðröð fyrsta manneskjan
á the andlit af the lína?
Hvað er það? >> [Nemandi] Breyttu biðröð.
Breyttu höfuðið, svo hverfur 5.
Í raun og veru, það er eins og-hvernig best sé að gera þetta?
Í raun og veru, það er eins og þessi strákur hverfur.
Hvað myndi númer 7 gera í raun verslun?
Þeir myndu taka stórt skref fram á við.
>> En það hafa komið við að meta þegar það kemur að því að fylki
og færa það í kring?
Það er góður af sóa tíma þínum, ekki satt?
Af hverju þarftu að vera svo anal að hafa fyrsta manneskjan
á the byrjun af the lína í líkamlega upphaf klumpur af minni?
Það er alveg óþarfi. Hvers vegna?
Hvað gæti ég man bara í staðinn? >> [Inaudible nemandi svar]
Einmitt, ég gat bara muna með þessari frekari gögn félagi höfuð
að nú er yfirmaður lista ekki lengur 0, þar sem það var smá stund síðan.
Nú það er í raun númer 1. Á þennan hátt, fæ ég smá fínstillingu.
Bara vegna þess að ég hef de-biðröð einhver úr línu í upphafi línu á Apple Store
þýðir ekki allir að skipta, sem muna er línuleg aðgerð.
Ég get í staðinn eyða stöðugt skipti
og ná svo miklu hraðari svörun.
En verð ég að borga er það að fá að auka árangur
og ekki þurfa að skipta öllum?
Já. >> [Inaudible nemandi svar]
Get bætt við fleiri fólk, vel að vandinn er þverstæðum
til þess að við erum ekki að breytast fólk í kring.
Það er samt fylki, svo hvort við vakt alla eða ekki-
ó, ég sé hvað þú átt við, allt í lagi.
Reyndar er ég sammála því sem þú ert að segja í því að það er nánast eins og
við erum nú ekki að fara að nota upphaf þessa array lengur
því ef ég fjarlægja 5, þá skal ég taka 7.
En ég setti bara fólk til hægri.
>> Mér finnst eins og ég sé að sóa rúm, og að lokum biðröð minn disintegrates í neitt,
þannig að við gátum bara hafa fólk wraparound,
og við gætum hugsa um þessa array raun nokkurs konar hringlaga byggingu,
en við notum hvað rekstraraðila í C til að gera þessi tegund af wraparound?
[Inaudible nemandi svar] >> The modulo rekstraraðila.
Það væri svolítið pirrandi að hugsa um hvernig þú gera wraparound,
en við gætum gert það, og við gætum byrjað að setja fólk á hvað er notað til að vera andlit af the lína,
en við bara muna með þessum höfuð breytu sem í raun höfuð af the lína í raun er.
Hvað ef, í staðinn, markmið okkar að lokum, þó,
var að horfa upp tölur, eins og við gerðum hér á sviðinu með Anita,
en við viljum í raun það besta af öllum þessum heimum?
Við viljum meiri fágun en array gerir
vegna þess að við viljum að getu við breytilega vaxa gögn uppbygging.
En við viljum ekki að þurfa að grípa til einhvers sem við bent á
í fyrsta fyrirlestrinum var ekki ákjósanlegur reiknirit,
sem línuleg leit.
Það kemur í ljós að þú getur í raun að ná
eða að minnsta kosti nálægt stöðugum tíma, þar sem einhver eins og Anita,
ef hún stillir gögn uppbygging hennar ekki að vera tengd lista,
ekki að vera stafla, ekki að vera biðröð, gæti í raun
koma upp með gögn uppbygging sem gerir hana að horfa upp hluti,
jafnvel orð, ekki bara tölur, á því sem við munum kalla stöðugt tíma.
>> Og í raun, að leita á undan, einn af psets í þessum flokki er nánast alltaf
sem framkvæmd Villupúki, þar
við gefa þér aftur sumir 150.000 ensk orð og markmiðið er að
hlaða þær inn minni og hratt að geta svarað spurningum á forminu
er þetta orð stafsett rétt?
Og það væri virkilega sjúga ef þú hefðir til að iterate gegnum allar 150.000 orð til að svara því.
En í raun, munum við sjá að við getum gert það í mjög fljótur tíma.
Og það er að fara að taka að innleiða eitthvað sem kallast a kjötkássa borð,
og jafnvel þó að við fyrstu sýn þessi hlutur sem kallast kjötkássa borð er að fara til
skulum ná þessum frábær hraður svar sinnum,
það kemur í ljós að það er í raun vandamál.
Þegar það kemur tími til að framkvæma þetta í heitir-aftur, er ég að gera það aftur.
Ég er sá eini hérna.
Þegar það kemur tími til að framkvæma þetta verk kallað kjötkássa borð,
við erum að fara að þurfa að taka ákvörðun.
Hversu stór ætti þessi hlutur að vera í raun og veru?
Og þegar við byrjum að setja tölur inn í þetta kjötkássa töflunni
hvernig ætlum við að geyma þá á þann hátt
að við getum fengið þá aftur út eins fljótt og við fengum þá í?
En við munum sjá áður en langt að þessi spurning
þegar afmæli allra í bekknum verður alveg germane.
Það kemur í ljós að í þessu herbergi, höfum við fengið nokkur hundruð manns,
þannig líkurnar að tveir af okkur hafa sama afmæli er sennilega nokkuð há.
Hvað ef það voru aðeins 40 af okkur í þessu herbergi?
Hverjar eru líkurnar á að tvær manneskjur hafa sama afmæli?
[Nemendur] Yfir 50%.
Já, yfir 50%. Í staðreynd, ég kom einu sinni töflu.
Það kemur í ljós og þetta er í raun bara laumast forsýning-
Ef það er aðeins 58 af okkur í þessu herbergi, en líkurnar á að 2 af okkur
hafa sama afmæli er gríðarlega mikil, nánast 100%,
og það er að fara að valda a heild búnt af skaða fyrir okkur á miðvikudag.
>> Með því að segja, við skulum fresta hér. Við munum sjá þig á miðvikudag.
[Lófaklapp]
[CS50.TV]