[Tónlist spila] DAVID J. MALAN: Allt í lagi. Þetta er CS50. Þetta er vika fimm áfram, og við hafa góðar fréttir og slæmar fréttir. Svo er góð fregn að CS50 kynnir föstudaginn. Ef þú vildi eins og til að tengja okkur, höfuð við venjulega slóðina hér. Jafnvel betri fréttir, ekki fyrirlestur þetta kemur mánudagur 13.. Nokkuð minna betri fréttir, quiz núll er næsta miðvikudag. Fleiri upplýsingar má finna á þessari vefslóð hér. Og á næstu dögum Við munum vera að fylla í eyðurnar með tilliti til herbergjunum að við munum hafa pantað. Betri fréttir er að það munt vera námskeið-breiður endurskoðun fundur þetta koma Mánudagur í kvöld. Fylgstu námskeiðið er heimasíðu fyrir staðsetningu og upplýsingar. Köflum jafnvel þó að það er frí, mun einnig mæta eins og heilbrigður. Besta fréttir, fyrirlestur næsta föstudag. Þannig að þetta er hefð sem við hafa, eins og á kennsluáætlun. Just-- það er að fara að vera ótrúlegt. Þú munt sjá hlutina eins fasti tími gögn uppbygging og kjötkássa borð og tré og reynir. Og við munum tala um afmæli vandamál. A heild búnt af efni bíður næsta föstudag. OK. Einhvern veginn. Svo muna að við höfum verið áherslu á þessa mynd af því sem er inni minni tölvunnar okkar. Svo minni eða RAM er þar forrit til á meðan þú ert að keyra þá. Ef þú tvöfaldur-smellur sem táknið til að keyra eitthvað forrit eða tvöfaldur-smellur sem táknið til að opna einhverja skrá, það er hlaðinn úr harður aka eða storkuhamur ökuferð í RAM, Random Access Memory, þar það býr til vald fer í burtu, laptop loki lokast, eða þú hætta forritið. 

Nú þegar minni, að sem þú hefur sennilega 1 gígabæti þessa dagana, 2 gígabæta, eða jafnvel miklu meira, er almennt sett fram fyrir tiltekið program í þessari tegund af rétthyrningslaga hugmyndafræðilegs líkan þar sem við höfum stafla neðst og fullt af öðrum hlutum efst. Málið á mjög toppur við höfum séð á þessari mynd áður en aldrei talað um er svokölluð texta hluti. Texti hluti er bara fínt leið að segja þeim núll og sjálfur að semja raunverulegan unnin program. 

Svo þegar þú tvöfaldur-smellur Microsoft Word á Mac eða PC, eða þegar þú keyrir punktur rista Mario á a Linux tölva á flugstöðinni glugga, núllin og þau sem mynda Orð eða Mario eru geymd tímabundið í RAM tölvunnar í svokölluðum texta hluti fyrir tiltekna program. Hér að neðan sem fer frumstilla og forsniðinn gögn. Þetta er efni eins og alþjóðlegum breytur, að við höfum ekki notað mörg, en stundum höfum við hafði alheims breytur eða statically skilgreind strengi sem er harður á dulmáli orð eins og "halló" sem eru ekki tekin frá notanda sem eru harður-dulmáli í forritinu. 

Nú, niður á botn og við hafa svokallaða stafla. Og stafla, svona langt, við höfum verið nota fyrir hvers konar tilgangi? Hvað er að stafla verið notað? Já? 

Áhorfendur: Aðgerðir. 

DAVID J. MALAN: Fyrir aðgerðir? Í hvaða skilningi á störfum? 

Áhorfendur: Þegar hringt er virka, rök eru afrituð á stafla. 

DAVID J. MALAN: Einmitt. Þegar hringt er aðgerð, þess rök eru afrituð á stafla. Svo allir X eða Y er eða A eða B er að þú ert að fara frá aðgerð eru tímabundið sett á svokallaða stafla, bara eins og einn af the Annenberg Borðstofan stæði, og einnig hluti eins staðbundnar breytur. Ef foo virka eða skipti þinn virka hafa staðværar breytur, eins afleysingamanneskja, þessir tveir endað á mánudaginn. Nú munum við ekki tala of mikið um þá, en þessir umhverfi breytur neðst sáum á meðan síðan þegar Ég var futzing á lyklaborðinu einn dag og ég byrjaði að fá aðgang hlutina eins argv 100 eða argv 1000, bara elements-- ég gleymi að Numbers en áttu ekki að vera skoðuð af mér. Við byrjuðum að sjá sum angurvær tákn á skjánum. Þeir voru svo-kölluð Breytur eins alþjóðlegum stillingar fyrir minn forrit eða fyrir tölvuna mína, ekki óskyld nýleg galla sem við ræddum, ShellShock, sem hefur verið plága alveg nokkrar tölvur. 

Nú loksins, í fókus í dag Við munum að lokum vera á hrúga. Þetta er annar klumpur af minni. Og í grundvallaratriðum allt þetta minni er sama efni. Það er sama vélbúnaði. Það nægir að taka svoleiðis meðhöndla mismunandi klasa bæti fyrir mismunandi tilgangi. The hrúga er einnig að fara að vera þar sem breytur og minni að þú biður frá stýrikerfi er tímabundið geymdur. 

En það er góður af vandamál hér, eins og myndin gefur til kynna. Við svoleiðis hafa tvo skipum um að rekast. Því eins og þú nota meira og meira á mánudaginn, og eins og við sjáum í dag áfram, eins og þú nota meira og meira af því hrúga, vafalaust slæmir hlutir gætu gerst. Og reyndar, við getum valdið að viljandi eða óviljandi. Þannig að cliffhanger síðasta tíma var þetta forrit, sem ekki þjóna allir hagnýtur tilgangur annar en að sýna hvernig þér eins slæmur strákur getur raunverulega taka Kosturinn við galla í forriti einhvers og taka yfir forrit eða jafnvel allt kerfið tölva eða miðlara. Svo bara til að sýn í stuttu máli, þér taka að helsta neðst tekur í skipanalínu rök, eins og á argv. Og það hefur hringja í fallinu f, fyrst og fremst á nafnlaus aðgerð sem heitir m, og það er farið í argv [1]. 

Svo hvað sem orð sem notandinn slær í á að hvetja eftir nafni þessari áætlun er, og þá er þetta handahófskennt virka upp efst, f, tekur í streng, AKA char *, eins og við höfum byrjað að ræða, og það kallar bara "bar." En við gætum kalla það hvað sem er. Og þá segir hún, inni f, fjölda af stöfum kallað c-- 12 slíkum stöfum. 

Nú, af sögunni sem ég var að segja áðan, þar sem í minni er c, eða eru slíkar 12 stafir að fara að enda? Bara til að vera skýr. Já? 

Áhorfendur: Á mánudaginn. 

DAVID J. MALAN: Á mánudaginn. Svo er c heimamaður breytu. Við erum að biðja fyrir 12 stafir eða 12 bæti. Þeir eru að fara að enda á svokölluðu stafla. Nú er loksins þetta önnur aðgerð það er reyndar mjög gagnlegur, en við höfum í raun ekki notað það sjálf, strncopy. Það þýðir band eintak, en aðeins n bréf, n stafi. Svo n stafir verða afrita af bar í c. Og hversu margir? Lengd bar. Svo í öðrum orðum að ein lína, strncopy, er að fara að afrita raun bar inn í c. 

Nú, bara til að svona sjá Boðskapur þessarar sögu, hvað er hugsanlega erfitt hér? Jafnvel þó að við erum að athuga lengd af bar og liggur það í strncopy, hvað er magi þinn segja þér er enn brotinn um þetta forrit? Já? 

Áhorfendur: Er ekki fela í Herbergi til núll staf. DAVID J. MALAN: Felur ekki í sér Herbergi til núll staf. Hugsanlega, ólíkt í framhjá æfa við gerum ekki einu sinni hafa svo mikið sem plús 1 til móts að núll staf. En það er jafnvel enn verra en það. Hvað annað eigum við ekki að gera? Já? 

Áhorfendur: [inaudible] DAVID J. MALAN: Perfect. Við höfum harður á dulmáli 12 ansi geðþótta. Það er ekki svo mikið vandamál, en staðreyndin að við erum ekki einu sinni að athuga hvort lengd bar er minna en 12, í þeim tilvikum er að fara að vera óhætt að setja það inn í minni heitir c sem við höfum úthlutað. Reyndar, ef bar er eins 20 stafir að lengd, þessi aðgerð virðist vera afritun 20 stafir úr bar í c, þar með taka að minnsta kosti 8 bæti að það ætti ekki að vera. Það er vísbendingu hér. 

Svo í stuttu máli, brotinn program. Ekki svo stór samningur. Kannski þú færð skiptingu kenna. Við höfum öll haft galla í forritum. Við öll gæti hafa galla í áætlunum núna. En hvað er vísbendingu? Jæja, hér er aðdregna-í útgáfu þessi mynd af minni tölvu minnar. Þetta er neðst á stafla minni. Og reyndar, nema alveg við botn er það sem er kallast foreldri venja stakkur, ímynda sér vegur að segja það er aðal. Svo að hver sá sem kallast virka m að við erum að tala um. Þannig að þetta er neðst á stafla. Aftur heimilisfang er eitthvað nýtt. Það er alltaf verið þarna, alltaf verið í myndinni. Við kölluð bara aldrei athygli á því. Vegna þess að það kemur í ljós hvernig c virkar að þegar eitt virka símtöl annan, ekki bara rök til að virka fá ýtt á stafla, ekki aðeins staðbundin fallið er breytur fá ýtt á stafla, eitthvað sem kallast aftur heimilisfang Einnig fær setja á mánudaginn. Sérstaklega ef helstu símtöl Foo, helstu er eigin heimilisfang í minni, ekki uxa eitthvað, raun fær setja á mánudaginn þannig að þegar m er gert framkvæmd það veit hvar á að hoppa aftur í texta hluti í því skyni að halda áfram að framkvæma. 

Þannig að ef við erum hér hugtök, í helstu, þá m fær kallað. Hvernig virkar m vita hver að hönd stjórn aftur? Jæja, þetta litla breadcrumb í rauðu hér, kallað aftur heimilisfang, það bara eftirlit, hvað er það aftur heimilisfang? Ó, láttu mig hoppa til baka í helstu hér. Og það er svolítið af einföldun, vegna þess að núllum og sjálfur fyrir helstu eru tæknilega upp hér í tækni hluti. En það er hugmynd. m bara þarf að vita hvað að þar stjórna að lokum fer aftur. 

En hvernig tölvur hafa lengi lagt út hlutina eins staðbundnar breytur og rök er eins og þetta. Svo í ofan á mynd í blár er stafla ramma fyrir f, þannig að allir af minni að f sérstaklega er að nota. Svo samkvæmt því, eftir að bar er á þessari mynd. Bar var rök hennar. Og við haldið fram að rök að aðgerðir fá ýtt á stafla. Og C, að sjálfsögðu, er Einnig í þessari mynd. 

Og bara fyrir notational tilgangi, taka efst í vinstra horni er hvað væri c krappi 0 og þá örlítið niður til hægri er c krappi 11. Svo í öðrum orðum, getur þú ímyndað þér að það er rist bæti þar, fyrst af, sem er Efst til vinstri, neðst sem er síðasta af þeim 12 bæti. 

En nú reyna að spóla áfram. Hvað er að gerast ef við framhjá í streng súlu sem er lengri en c? Og við erum ekki að stöðva ef það er örugglega lengur en 12. Hvaða hluti af þessari mynd er að fara að fá skrifuð yfir bæti 0, 1, 2, 3, punktur punktur punktur, 11, og þá slæmt, 12, 13 í 19? Hvað er að fara að gerast hér, ef þú álykta frá röðun að c krappi 0 er efst og c krappi 11 er tegund af niður til hægri? Já? 

Áhorfendur: Jæja, það er að fara að skrifa yfir char * bar. 

DAVID J. MALAN: Já, það lítur út eins og þú ert að fara að skrifa char * bar. Og verri, ef þú sendir í mjög langan band, þú gætir jafnvel skrifa það? The aftur heimilisfang. Sem aftur, er bara eins og breadcrumb að segja program þar að fara til baka þegar m er gert að vera kölluð. 

Svo hvað slæmur krakkar yfirleitt gert er ef þeir rekast a program að þeir ert forvitinn hvort er virkjanlegur, þrjótur á þann hátt að hann eða hún getur tekið Kosturinn við þessa galla, yfirleitt gera þeir fá ekki þetta rétt í fyrsta skipti. Þeir byrja bara að senda, til dæmis, handahófi strengir í forritinu, hvort sem er á lyklaborðinu, eða hreinskilnislega þeir sennilega skrifa smá forrit til bara sjálfkrafa mynda strengir, og byrja að lemja á forritinu með senda í fullt af mismunandi aðföngum á mismunandi lengdum. 

Um leið og áætlun hrun þinn, það er furðulegur hlutur. Vegna þess að það þýðir að hann eða hún hefur uppgötvað hvað er líklega örugglega galla. Og þá geta þeir fengið fleiri snjall og byrja að einbeita meira þröngt um hvernig á að nýta þessi villu. Einkum það sem hann eða hún gæti gera er að senda, í besta tilfelli, halló. Ekkert stórmál. Það er band sem er nægilega stutt. En hvað ef hann eða hún sendir, og við munum alhæfa það sem, árás code-- svo núllum og þau sem gera það eins RM-rf, sem fjarlægja allt frá disknum eða senda ruslpóst eða einhvern veginn að ráðast á vélina? 

Þannig að ef hvert þessara Stafirnir A táknar bara, hugtök, árás, árás, árás, árás, slæmar kóða að einhver annar skrifaði, en ef þessi manneskja er sviði nógur að ekki aðeins eru allar af þeim RM-lifunar án endurkomu sjúkdóms, en einnig hafa undanfarna bæti sín vera tala sem samsvarar á heimilisfang hans eða hennar eigin árás númer að hann eða hún fór í bara með því að veita það á að hvetja, þú getur í raun bragð tölvuna í að taka eftir þegar f er gert framkvæmd, ó, það er kominn tími fyrir mig að stökkva aftur til rauðu aftur heimilisfang. En vegna þess að hann eða hún hefur á einhvern hátt skarast að skila tölu með eigin númer þeirra, og þeir ert sviði nógur að hafa stillt að númer til að vísa, eins og þú sjá í ofur efst vinstri-hönd horn þar, raunverulegt heimilisfang í the tölva ' minni sum árás númer þeirra, slæmur strákur getur bragð tölva í framkvæmd hans eða hennar eigin kóða. 

Og það númer aftur, getur verið hvað sem er. Það er almennt kallað skel kóða, sem er bara leið til að segja að það er ekki almennt eitthvað eins einfalt og RM-rf. Það er í raun eitthvað eins Bash, eða í raun forrit sem gefur honum eða forritanlegur stjórn hennar til að framkvæma eitthvað annað sem þeir vilja. Svo í stuttu máli, þetta allt stafar af þeirri einföldu staðreynd að þessi padda þátt ekki stöðva mörk array þínu. Og vegna þess að á leiðinni tölvur vinna er að þeir nota stafla af á áhrifaríkan hátt, eðli, botn á upp, en þá þætti þú ýta á stafla vaxa topp niður, þetta er ótrúlega erfitt. Nú, það eru leiðir til að vinna í kringum þetta. Og hreinskilnislega, það eru tungumál sem að vinna í kringum þetta. Java er ónæmur, til dæmis, þessum tiltekna mál. Vegna þess að þeir gefa þér ekki ábendingum. Þeir gefa þér ekki bein netföng minni. Svo með þetta vald sem við höfum að snerta neitt í minni Við viljum koma að vísu mikil áhætta. 

Svo að hafa auga út. Ef hreinskilnislega, á næstu mánuðum eða ár að koma, hvenær sem þú lesið um einhvern nýtingu af a program eða miðlara, ef þú alltaf að sjá vott um eitthvað eins biðminni flæða árás, eða stakkur flæða er annar tegund árás, svipað í anda, mikið og hvetur vefsíða er nafn, ef þú veist það, það er allt að tala um bara barmafullur stærð einhverjum staf fylki eða sumir array almennt. Einhverjar spurningar, þá á þetta? Ekki reyna þetta heima. 

Allt í lagi. Svo malloc hingað til hefur verið ný okkar vinur í að við getum tekið frá minni að við gerum ekki endilega vita fyrirfram að við viljum svo við þurfum ekki á harða kóða inn í okkar program tölur eins 12. Þegar notandi segir okkur hversu mikið gögn sem hann eða hún vill inntak, getum við malloc það mikið minni. 

Svo malloc það kemur í ljós, að því marki sem við höfum verið að nota það, sérstaklega síðasta sinn, og þá þið hafið verið að nota það fyrir getstring óafvitandi fyrir nokkrar vikur, allt að minni malloc er kemur frá svokölluðum hrúga. Og þetta er ástæðan getstring, til dæmis, getur tekið frá minni virk án þess að vita hvað þú ert að fara að slá í fyrirfram, hönd þér aftur bendi til þess minni, og að minni er enn þinn til að halda, jafnvel eftir getstring ávöxtun. Vegna muna eftir allt að stakkur er stöðugt að fara upp og niður, upp og niður. Og um leið og það fer niður, sem merkir minni þessi aðgerð er notað ætti ekki að nota með neinum öðrum. Það er sorp gildi núna. 

En hrúga er upp hér. Og hvað er gott um malloc er að þegar malloc úthlutar minni hér, það er ekki fyrir áhrifum fyrir mestu, með stafla. Og svo allir virka geta nálgast minni sem hefur verið malloc'd, jafnvel eftir fall eins getstring, jafnvel eftir að það er skilað. 

Nú er spjallað um malloc er ókeypis. Og reyndar, reglan þér þarf að byrja að taka er einhver, einhver, hvenær þú notar malloc þú verður sjálfur að nota ókeypis, að lokum, á sama músina. Allan þennan tíma sem við höfum verið að skrifa þrjótur, þrjótur kóða, af mörgum ástæðum. En einn sem hefur verið nota CS50 bókasafn, sem sjálft er vísvitandi þrjótur, lekur hún minni. Í hvert sinn sem þú hefur kallað getstring á undanförnum vikum við erum að spyrja rekstri kerfi, Linux, fyrir minni. Og þú hefur aldrei einu sinni gefið það aftur. Og þetta er ekki í æfa, gott. 

Og Valgrind, einn af þeim verkfæri kynnt í Pset 4, er allt um að hjálpa þér nú finna galla eins og þessi. En sem betur fer fyrir Pset 4 þú þarft ekki að nota CS50 bókasafn eða getstring. Svo einhverjar villur sem tengjast minni eru lokum að fara til vera þinn eigin. 

Svo er malloc meira en bara þægilegt í þessum tilgangi. Við getum í raun nú leyst grundvallaratriðum mismunandi vandamál, og grundvallaratriðum að leysa vandamál meira raun eins og á viku núll er loforð. Hingað er þetta kynjamisrétti gagnagrind sem við höfum haft. Og með því að gögn uppbygging ég meina bara leið conceptualizing minni á þann hátt sem fer út bara að segja, þetta er int, þetta er char. Við getum byrjað á að þyrping hluti saman. 

Svo fylki leit út eins og þetta. Og hvað var inni í um array er að það gefur þér bak-til-bak klumpur af minni, sem hver um sig er að fara að vera af sömu gerð, int, int, int, int, eða bleikju, bleikju, bleikju, bleikju. En það er nokkur downsides. Þetta til dæmis, er fylki í stærð sex. Segjum að þú fyllir þetta array með sex tölur og þá fyrir hvað ástæðum, þinn notandi vill gefa þú sjöund tala. Hvar þú setur það? 

Hver er lausnin ef þú ert búið til fylki á mánudaginn, til dæmis, bara með viku tveir ritháttur sem við kynnt, af hornklofum við fjölda inni? Jæja, hefur þú fengið sex tölur í þessum kassa. Hvað myndi eðlishvöt þín að vera? Hvar myndir þú vilja að setja það? 

Áhorfendur: [inaudible] 

DAVID J. MALAN: Fyrirgefðu? 

Áhorfendur: Settu það á endanum. 

DAVID J. MALAN: Settu það á endanum. Svo bara yfir til hægri, utan þennan reit. Sem væri gott, en það snýr út að þú getur ekki gert það. Vegna þess að ef þú hefur ekki spurt fyrir þessa klumpur af minni, það gæti verið af tilviljun að þessi er notað af einhverjum öðrum breytu að öllu leyti. Hugsaðu til baka í viku eða svo þegar við lagði út nöfn Zamyla og Davin og Gabe er í minni. Þeir voru bókstaflega aftur til baka til baka. Svo við getum ekki endilega treysta því að hvað sem er hérna er í boði fyrir mig að nota. 

Svo hvað annað gætir þú gert? Jæja, einu sinni að átta sig á þig þarf fjölda af stærð sjö, þú gætir bara búið að array stærð sjö þá nota for lykkju eða meðan lykkja, afrita það inn í nýja fylking, og þá einhvern veginn bara að losna við þetta fylki eða bara hætta að nota það. En það er ekki sérstaklega duglegur. Í stuttu máli, ekki fylki láta þú búa virk. 

Svo annars vegar að fá handahófi aðgangur, sem er ótrúlegt. Vegna þess að það leyfir okkur að gera hlutina eins skipta og sigra, tvöfaldur leit, allt sem við höfum talaði um á skjánum hér. En þú mála þig út í horn. Um leið og þú högg enda fylking þinni, þú þarft að gera mjög dýr aðgerð eða skrifa a heild búnt af kóða að nú takast á við þessi vandamál. 

Svo hvað ef í staðinn höfðum við eitthvað sem kallast lista, eða tengdur lista sérstaklega? Hvað ef í stað þess að hafa ferhyrninga baka til baka til baka, Við höfum ferhyrninga sem yfirgefa smá hluti af wiggle herbergi í milli þeirra? Og jafnvel þó að ég hef dregið þetta mynd eða lagað þessa mynd frá einum af texta hér að vera kominn aftur til aftur til baka mjög reglusamur, í raun, einn af þeim ferhyrninga gæti verið hér í minni. Einn af þeim gæti verið allt hér. Einn af þeim gæti verið upp hér, hérna, og svo framvegis. 

En hvað ef við brá, í þessu tilfelli, örvar sem á einhvern hátt tengjast þessum rétthyrninga saman? Reyndar höfum við séð tæknilega holdgun ör. Hvað höfum við notað í nýlegri daga að undir hetta, er dæmigert ör? A músina, ekki satt? 

Svo hvað ef, í stað þess að bara að geyma tölur, eins og 9, 17, 22, 26, 34, hvað ef við geymd ekki bara tala en bendi við hliðina á öllum þeim fjölda? Svo að mikið eins og þú vilt þræði a nálinni í gegnum a heild búnt af efni, einhvern veginn binda hlutir saman, á sama hátt getur við með ábendingum, sem incarnated með örvum hér, konar fléttast saman þessi einstaklingur ferhyrninga með raun að nota músina við hliðina á hvert númer sem bendir að einhverju næstu tala, sem bendir til, aftur á móti, sumir næsta tala? Svo í öðrum orðum, hvað ef við vildum í raun að innleiða eitthvað eins og þetta? Jæja því miður, þessi ferhyrninga, að minnsta kosti einn með 9, 17, 22, og svo framvegis, eru þessar ekki lengur ágætur ferningar með stakar tölur. The botn, rétthyrningur hér að neðan 9, til dæmis, táknar það ætti vera músina, 32 bita. Nú, ég er ekki enn kunnugt um hvaða gögn gerð í C sem gefur þér ekki aðeins við int en bendillinn að öllu leyti. 

Svo er það lausnin ef við viljum að finna eigin svar okkar við þetta? Já? 

Áhorfendur: [inaudible] 

DAVID J. MALAN: Hvað er það? 

Áhorfendur: Nýtt skipulag. 

DAVID J. MALAN: Já, svo hvers vegna eigum við ekki að búa til nýtt skipulag, eða í C, a strúktúrinn? Við höfum séð structs áður, ef stuttlega, þar sem við fjallað nemandi uppbyggingu eins og þetta, sem hafði nafn og hús. Í Pset 3 Brot þú notaðir í heild fullt af structs-- GRect og GOvals að Stanford búin til þyrping upplýsingar saman. Svo hvað ef við tökum þessa sömu hugmynd leitarorð "typedef" og "strúktúr", og þá sumir nemandi sérstakar efni, og þróast þetta í eftirfarandi: typedef strúktúr node-- og hnúturinn er bara mjög almenn tölvunarfræði tíma fyrir eitthvað í gögn uppbygging, ílát í gögnum byggingu. Hnútur ég kröfu er að fara að hafa int n, algerlega augljóst, og þá aðeins meira cryptically, þessi seinni lína, struct hnút * næst. En í minna tæknilegur skilmálar, hvað er það annað lína af kóða inni í hrokkið axlabönd? Já? 

Áhorfendur: [inaudible] DAVID J. MALAN: A músina til annars hnút. Svo að vísu, setningafræði svolítið dulinn. En ef þú lest það bókstaflega, Næsta er nafn á breytu. Hvað er gögn tegund þess? Það er lítið fjölorður í þetta sinn, en það er af gerðinni struct hnút *. Í hvert sinn sem við höfum séð eitthvað stjörnu, sem þýðir að það er bendi til þess gögn tegund. Svo er næsta víst að músina til struct hnút. 

Nú, hvað er struct hnút? Jæja, eftir að sjá þá sömu orð á efst til hægri. Og reyndar, þú sérð líka orðið "Hnút" niður hér neðst til vinstri. Og þetta er í raun bara þægindi. Takið eftir að í skilgreiningu nemenda okkar það er orðið "nemandi" aðeins einu sinni. Og það er vegna þess að nemandi hlut var ekki sjálf-vísun. Það er ekkert inni á nemanda sem þarf að benda á aðra nemanda, persay. Það væri eins konar undarlegt í hinum raunverulega heimi. 

En með hnút í tengdur lista, gera við viljum hnút til að vera referential til á svipaðan hlut. Og svo eftir breytingu hér er ekki bara er það inni í hrokkið axlabönd. En við bætum við orðinu "hnútur" efst sem og bæta því við botn í stað "nemandi". Og þetta er aðeins tæknileg smáatriði svo að, aftur, gögn uppbygging getur verið sjálf-vísun, þannig að hnút getur bent til annars slíks hnút. 

Svo er það þetta að lokum að fara að þýða fyrir okkur? Jæja, einn, þetta dót inni er innihald hnút okkar. Þessi hlutur hér, efst til hægri, er bara svo sem, aftur, getum við átt að okkur. Og þá ysta efni, jafnvel þótt hnútur er nýtt hugtak, kannski er það enn sama og nemanda og hvað var undir hetta í SPL. 

Þannig að ef við vildum nú til að byrja framkvæmd þessarar tengdan lista, hvernig gætum við þýða eitthvað eins og þetta til að kóða? Jæja, við skulum sjá bara Dæmi um forrit sem reyndar notar tengda lista. Meðal dreifingu kóða dag er forrit sem heitir Listi Zero. Og ef ég keyra þetta ég bjó til frábær einföld GUI, Myndræn User Interface, en það er í raun bara printf. Og nú hef ég gefið mér nokkur matseðill options-- Eyða, Bæta í, leit, og Traverse. Og hætta. Þetta eru bara algengar aðgerðir á a gagnagrind þekktur eins og a hlekkur lista. 

Nú, Eyða er að fara til eyða númeri af listanum. Innskotið er að fara að bæta við fjölda á listann. Leit er að fara að horfa fyrir númer í listanum. Og Traverse er bara fínt leið að segja, ganga í gegnum listann, prenta það út, en það er það. Ekki breyta því ekki á nokkurn hátt. 

Svo skulum reyna þetta. Við skulum fara á undan og sláðu inn 2. Og þá er ég að fara að settu númerið segja 9. Enter. Og nú er áætlun mín bara forrita til að segja, listi er nú 9. Nú, ef ég fer á undan og Setjið aftur, láta mér að fara á undan og þysja út og slá í 17. Nú er minn listi 9, þá 17. Ef ég setja aftur skulum sleppa einn. Í stað þess að 22, eins og á myndinni sem við höfum verið að horfa á hér, láta mig hoppa á undan og setja 26 næst. Þannig að ég ætla að fara að slá 26. Listinn er sem eg ætla. En nú, bara til að sjá hvort þessum kóða er að fara að vera sveigjanlegur, láta mig nú tegund 22, þar sem að minnsta kosti eðli, ef við erum halda þessu raðað, sem er örugglega að fara að vera annar markmið núna, ætti að fara í á milli 17 og 26. Svo ég högg á Enter. Reyndar, það virkar. Og svo nú láta mig settu síðast, á myndinni, 34. 

Allt í lagi. Svo nú láta mig kveða á um að Eyða og Traverse og Leita gera, í raun, vinna. Í staðreynd, ef ég keyri Search, við skulum leita að númer 22, Enter. Það fundust 22. Svo er það það sem þetta Forritið Listi Zero gerir. 

En hvað er í raun að fara á sem útfærir þetta? Jæja, fyrst ég gæti hafa, og raunar Ég hef, að skrá sem heitir list0.h. Og einhvers staðar er þetta lína, typedef, struct hnút, þá hef ég hrokkið axlabönd mínum, int n og þá struct-- hvað var skilgreining? Struct hnút næst. Þannig að við þurfum stjörnuna. Nú tæknilega fáum við í að venja af að teikna það hér. Þú gætir séð kennslubækur og online tilvísanir gera það þar. Það er virkni jafngildir. Í raun er þetta lítið meira dæmigerður. En ég ætla að vera í samræmi við það sem við gerðum síðasta tíma og gera þetta. Og svo loks, ég ætla að gera þetta. 

Svo í haus skrá einhvers staðar, í list0.h í dag er þetta struct skilgreining, og kannski einhver önnur efni. Á sama tíma í list0c það er að fara að vera nokkur atriði. En við erum að fara að bara byrja og ekki klára þetta. List0.h er skrá sem ég vil að fela í C skrá minn. Og þá á einhverjum tímapunkti sem ég er fara að hafa int, helstu, ógilt. Og þá er ég að fara að hafa sumir að-gera er hér. Ég er líka að fara að hafa frumgerð, eins ógilt, leit, int, n, en tilgangur í lífinu er til að leita að frumefni. Og þá hérna ég kröfu á númer í dag, tóm, leit, int, n, engin semíkommu en opna hrokkið axlabönd. Og nú vil ég að einhvern veginn leita fyrir í framhaldi þennan lista. En við höfum ekki nóg Upplýsingar á skjánum enn. Ég hef í raun ekki fulltrúa lista sjálft. Svo ein leið að við gætum framkvæma tengdur listi í forriti er ég vil konar að gera eitthvað eins lýsi tengd lista upp hér. Fyrir einfaldleiki, ég ætla að gera þetta alheims, þótt almennt vér ætti ekki að gera þetta of mikið. En það mun einfalda þetta dæmi. Þannig að ég vil lýsa því yfir tengdur listi hér. Nú, hvernig gæti ég það? 

Hér er mynd af tengdum lista. Og ég í raun ekki veit í augnablikinu hvernig Ég ætla að fara um hönd svo margt með bara einn breyta í minni. En hugsa aftur í smá stund. Allan þennan tíma sem við höfum haft strengir, sem vér þá ljós að fylki af stafir, sem vér þá ljós að bara vera bendillinn að fyrsta staf í fjölmörgum stöfum það er null slitið. Svo eftir að rökfræði, og með þetta mynd konar sáningu hugsanir þínar, hvað þurfum við að skrifa í raun í okkar kóða til að tákna tengdan lista? Hversu mikið af þessum upplýsingum þurfum að fanga í C kóða, myndir þú segja? Já? 

Áhorfendur: Við þurfum bendi til hnút. DAVID J. MALAN: A bendi til hnút. Einkum, sem tengipunktur myndi þína eðlishvöt vera að halda bendi á? 

Áhorfendur: Fyrsta hnút. 

DAVID J. MALAN: Já, sennilega bara það fyrsta. Og eftir, fyrsta tengipunktur er mismunandi lögun. Það er aðeins helmingur the stærð af the strúktúr, vegna þess að það er örugglega bara músina. Svo það sem þú getur örugglega gera er að lýsa tengdur listi að vera af gerðinni hnút *. Og við skulum bara kalla það fyrst og frumstilla hana til núll. Svo null, aftur, er að koma inn í myndina hér. Ekki aðeins er null notað sem eins sérstakt skilagildi fyrir hluti eins getstring og malloc, null er einnig núll músina, skortur á músina, ef þú vilt. Það þýðir bara ekkert er enn hér. Nú fyrst, ég hefði getað kallað þetta hvað sem er. Ég hefði getað kallað það "lista" eða allir tala af öðrum hlutum. En ég ætla að kalla það "fyrsta" þannig að það línur upp með þessa mynd. Svo bara eins og band er hægt að fulltrúa með heimilisfang fyrstu bæti þess, svo getur tengdur listi. Og við munum sjá önnur gögn mannvirki að fulltrúa með aðeins eitt músina, 32-bita ör sem bendir á fyrstu hnút í uppbyggingu. 

En nú skulum sjá vandamál. Ef ég er bara að muna í áætlun mína að tölu af fyrsta hnút, fyrsta rétthyrnings í þessum gögnum uppbyggingu, hvað hafði betur að vera málið um að framkvæmd af the hvíla af listanum mínum? Hvað er lykillinn smáatriði sem er að gerast til að tryggja þetta í raun virkar? Og með því að "í raun virkar" Ég meina, eins og band, leyfir okkur að fara úr fyrsta staf í nafni Davin er til annað, í þriðja, til að fjórða, allt til enda, hvernig vitum við þegar við erum í lok af tengdum lista sem lítur svona út? Þegar það er null. Og ég hef fulltrúa svona eins eins og rafmagns verkfræðingur gæti, með litla jarðtengingu tákn, nokkurs konar. En það bara þýðir null í þessu tilfelli. Þú getur teiknað það allir tala um leiðir, en þessi höfundur varð að nota þetta tákn hér. 

Svo lengi sem við erum að stringing öll þessi tengipunkta saman, Aðeins muna hvar sá fyrsti er, svo lengi eins og við leggja sérstaka tákn á mjög síðasta hnút á listanum, og við munum nota null, því það er það sem við höfum í boði fyrir okkur, þessi listi er lokið. Og jafnvel ef ég bara gefa þér bendi til fyrsta frumefni, þú, sem forritari, getur vissulega fá aðgang að henni. En við skulum láta huga þinn reika svolítið, ef þeir eru ekki nú þegar alveg wandered-- hvað er að fara að vera í gangi tími finna neitt í þessum lista? Fjandinn það, er það stór O n, sem er ekki slæmt, í sanngirni. En það er línulegt. Við höfum gefið upp hvaða lögun af fylki með því að færa meira til þessa mynd af virk ofið saman eða tengd hnúður? Við höfum gefið upp handahófi aðgang. An array er gott vegna þess að stærðfræðilega allt er aftur til baka til baka til baka. Jafnvel þótt þessari mynd lítur falleg, og jafnvel þó það lítur út eins og þessi hnúður eru vel aðskildar, í raun þeir gætu verið hvar sem er. OX1, Ox50, Ox123, Ox99, þessir hnúður gæti verið hvar sem er. Vegna malloc er tekið frá minni frá hrúga, en hvar í hrúga. Þú þarft ekki endilega að vita að það er að fara að vera aftur til baka til baka. Og svo þessi mynd í veruleika er ekki að fara að vera alveg þetta nokkuð. 

Svo það er að fara að taka a hluti af vinna til að framkvæma þessa aðgerð. Svo skulum framkvæma leit nú. Og við munum sjá hvers konar a sniðug leið til að gera þetta. Svo ef ég er að leita virka og Ég gefa breytilega, heiltala n að leita að, ég þarf að vita Ný setningafræði fyrir að leita inni af byggingu sem er benti til, að finna n. Svo skulum gera þetta. 

Svo fyrst ég er að fara að fara undan og lýsa hnút *. Og ég ætla að kalla það músina, bara með því að venju. Og ég ætla að frumstilla hana fyrst. Og nú get ég gert þetta í fjölda vegu. En ég ætla að taka sameiginlega nálgun. Þó að bendi er ekki jafnt null, og það er gild setningafræði. Og það þýðir bara að gera eftirfarandi, svo lengi sem þú ert ekki að benda á neitt. Hvað vil ég að gera? 

Ef bendillinn punktur n, láttu mig aftur til að equals-- jafnt hvað? Hvaða gildi á ég að leita að? Raunveruleg n sem var samþykkt í. Svo er hér annar þáttur C og mörgum tungumálum. Jafnvel þótt uppbyggingu kallast hnút hefur gildi n, algerlega lögmæta einnig hafa a heimamaður rök eða breytu sem heitir n. Því jafnvel við, með manna augum, geta greint að þessi n er væntanlega frábrugðið þessu n. Þar sem setningafræði er öðruvísi. Þú hefur fengið punkt og bendi, en this einn hefur ekkert sem heitir. Svo er þetta í lagi. Það er í lagi að kalla þá sömu hlutina. 

Ef ég að þú finnur þetta, ég er að fara að vilja til að gera eitthvað eins tilkynna að við fundum n. Og við munum fara að sem comment eða sauðakóðanum kóða. Annars, og hér er áhugaverður hluti, hvað ég vil gera ef núverandi hnút er ekki með n sem ég þykir vænt um? Hvernig get ég ná eftirfarandi? Ef fingur minn á að augnablik er PTR, og það er benda á hvað Fyrsta er að benda á, hvernig færi ég fingur minn að næsta hnút í númerið? Jæja, hvað er að breadcrumb við erum að fara að fylgja í þessu tilviki? Áhorfendur: [inaudible]. DAVID J. MALAN: Já, svo næst. Svo ef ég fer aftur til mín númer hérna, reyndar er ég að fara á undan og segja músina, sem er bara tímabundin variable-- það skrýtið nafn, PTR, en það er bara eins og temp-- Ég ætla að setja músina jafnt hvað bendillinn is-- og aftur, þetta er að fara til vera a litla þrjótur fyrir moment-- punkt næsta. Í öðrum orðum, ég er að fara að taka minn fingur sem er að benda á þetta hnút hér og ég ætla að segja, þú veist hvað, taka a líta á næsta sviði og færa fingurinn til hvað sem það er að benda á. Og þetta er að fara til endurtaka, endurtaka, endurtaka. En þegar er fingur minn hætta að gera neitt á öllum? Eins fljótt og hvaða línu af kóða ánægja í? Áhorfendur: [inaudible] DAVID J. MALAN: Ef lið á meðan bendillinn er ekki jafn null. Á einhverjum tímapunkti fingur er mitt að fara að benda á null og ég ætla að gera sér grein fyrir það er í lok þessa lista. Nú, þetta er svolítið hvítur lygi fyrir einfaldleika. Það kemur í ljós að jafnvel þótt við bara lært þetta punktur tákn fyrir mannvirki, bendillinn er ekki strúktúr. PTR er hvað? Bara til að vera meira nitpicky. Það er bendi á hnút. Það er ekki hnút sig. Ef ég hefði ekkert stjörnu hérna, bendi absolutely-- það er hnútur. Þetta er eins og viku einum yfirlýsing um breytu, jafnvel þótt orðið "hnútur" er nýr. 

En um leið og við kynna a stjörnu, það er nú bendi til hnút. Og því miður er ekki hægt að nota punktur ritháttur fyrir bendi. Þú þarft að nota örina ritháttur, sem sláandi, er í fyrsta sinn allir stykki af setningafræði lítur innsæi. Þetta lítur bókstaflega eins og ör. Og svo er það gott. Og hérna bókstaflega lítur út eins og ör. Þannig að ég held að það er að la-- ég ekki held ég yfir-fremja here-- ég held það er síðasta nýja stykki af setningafræði sem við erum að fara að sjá. Og sem betur fer, það er örugglega svolítið meira innsæi. 

Nú, fyrir þá sem gæti verið gott gamla leiðin, þú getur samt notað punktur tákn. En eins og á Mánudagur samtal, við fyrst þarf að fara þangað, fara til að takast, og þá opna reitinn. Svo er þetta líka rétt. Og hreinskilnislega, þetta er lítið meira smámunasamur. Þú ert bókstaflega að segja, dereference bendillinn og fara þangað. Þá grípa .n, á sviði sem kallast n. En hreinskilnislega, enginn vill að slá eða lesa þetta. Og svo að heimurinn fundin örin ritháttur, sem jafngildir, eins, það er bara nokkur dæmi um setningarleg sykur. Svo fínt leið til að segja þetta lítur betur, eða lítur einfaldara. 

Svo nú er ég að fara að gera eitt annað hlutur. Ég ætla að segja "hlé" þegar ég hef fann það svo að ég halda ekki útlit fyrir það. En þetta er GIST af a leita virka. En það er mun auðveldara, í endir, ekki að ganga í gegnum kóðann. Þetta er örugglega formleg framkvæmd af leit í dreifingu kóða dag. Ég þori að segja að innskotið er ekki sérstaklega gaman að ganga í gegnum sjónrænt, né er eytt, jafnvel þó í lok dags þeir sjóða niður í nokkuð einföld leitandi. 

Svo skulum gera þetta. Ef þú munt húmor mig hingað, gerði ég koma fullt af streitu kúlur. Ég kom með fullt af tölum. Og gætum við fengið bara nokkra sjálfboðaliða að tákna 9, 17, 20, 22, 29, og 34? Svo í raun allir sem er hér í dag. Það var einn, tveir, þrír, fjórir, fimm, sex manns. Og ég hef verið beðin um að go-- sjá, nei einn í bak vekur hendur. OK, einn, tveir, þrír, fjórir, five-- láta mig hlaða balance-- sex. OK, þú sex koma upp. Við þurfum aðra. Við tókum auka streitu kúlur. Og ef þú gætir, að bara smá stund, lína ykkur upp bara svona mynd hér. 

Allt í lagi. Við skulum sjá, hvað er nafnið þitt? 

Áhorfendur: Andrew. 

DAVID J. MALAN: Andrew, þú ert númer 9. Gaman að hitta þig. Hér þú fara. Áhorfendur: Jen. DAVID J. MALAN: Jen. David. Númer 17. Já? 

Áhorfendur: Ég er Julia. 

DAVID J. MALAN: Julia, David. Númer 20. Áhorfendur: Christian. DAVID J. MALAN: Christian, David. Númer 22. Og? 

Áhorfendur: JP. DAVID J. MALAN: JP. Númer 29. Svo fara á undan og fá in-- Uh oh. Uh oh. Biðstaða. 20. Hefur einhver hafa a merkið? Áhorfendur: Ég hef fengið Sharpie. DAVID J. MALAN: Áttu Sharpie? OK. Og er einhver hafa a stykki af pappír? Vistaðu fyrirlestur. Komdu á. Áhorfendur: Við höfum það. DAVID J. MALAN: Við fengum það? Allt í lagi, þakka þér. Hér förum. Var þetta frá þér? Þú spara bara daginn. Svo 29. Allt í lagi. Ég rétt stafað 29, ​​en allt í lagi. Fara á undan. Allt í lagi, ég skal gefa þér pennann aftur eftir augnablik. Þannig að við höfum þessar fólkinu hér. Við skulum hafa eitt annað. Gabe, viltu leika fyrsta þáttur hér? Við þurfum þig til að benda á þessum fínu fólkinu. Svo 9, 17, 20, 22, flokka af 29, og þá 34. Did við missa einhvern? Ég lendi í 34. Hvar did-- lagi, sem vill vera 34? OK, komdu upp, 34. Allt í lagi, þetta verður vel þess virði að hápunktur. Hvað er nafn þitt? 

Áhorfendur: Pétur. 

DAVID J. MALAN: Pétur, komdu upp. Allt í lagi, þannig að hér er allt fullt af hnúður. Hvert ykkur táknar einn af þessum ferhyrnda. Og Gabe, pínu skrýtið maður út, táknar fyrst. Svo er bendillinn hans lítið minni á skjánum en allir aðrir. Og í þessu tilfelli, hver vinstri Hendur er að fara að annaðhvort benda niður, þannig fulltrúi null, svo bara skortur á bendi, eða það er að fara að vera að benda á hnút við hliðina á þér. 

Svo núna ef þú adorn yður eins og á myndinni hér fara á undan og benda hvert á annað, með Gabe einkum benda á númer 9 til að tákna listann. OK, og fjölda 34, vinstri hönd þín ætti bara að vera að benda á gólfið. 

Allt í lagi, svo þetta er tengda listanum. Þannig að þetta er atburðarás sem um ræðir. Og reyndar, þetta er dæmigert á bekknum á vandamálum að þú gætir reynt að leysa með kóða. Þú vilt að lokum að setja ný þáttur í listanum. Í þessu tilfelli erum við að fara að reyna að setja númer 55. En það er að fara að vera mismunandi tilvik í huga. Og reyndar, þetta er að fara að vera einn af stór-mynd Takeaways hér, er, hvað eru mismunandi tilvikum. Hvað eru mismunandi ef aðstæður eða útibú að kerfið þitt gæti hafa? 

Jæja, númerið sem þú ert að reyna að settu, sem við vitum nú að vera 55, en ef þú did ekki vita fyrirfram, eflaust allt fellur inn í að minnsta kosti þremur mögulegar aðstæður. Hvar gæti nýtt frumefni að vera? Áhorfendur: Og enda eða miðju. DAVID J. MALAN: Í lokin á miðju, eða í upphafi. Svo ég kröfu að það er að minnsta kosti þrjú vandamál sem við þurfum að leysa. Við skulum velja það sem er kannski að öllum líkindum einfaldasta einn, þar sem nýja þáttur tilheyrir í upphafi. Þannig að ég ætla að hafa kóðann alveg eins leita, sem ég skrifaði bara. Og ég ætla að hafa PTR, sem Ég tákna hér með fingri mínum, eins og venjulega. 

Og muna, hvaða gildi gerði við frumstilla PTR að? Þannig að við frumstilla hana til núll í upphafi. En þá hvað gerði við gerum þegar við voru inni leita virka okkar? Við setjum það jafn fyrst, sem þýðir ekki að gera þetta. Ef ég sett PTR jafnan fyrst, hvað ætti hönd mín raunverulega vera að benda á? Rétt. Svo ef Gabe og ég erum að fara að vera jafnir gildi hér, við þurfum bæði að benda á númer 9. 

Svo var þetta upphafið af sögu okkar. Og nú er þetta bara einfalt, jafnvel þótt setningafræði er nýtt. Hugmyndalega er þetta bara línuleg leit. Er 55 jafnt 9? Eða frekar, segjum minna en 9. Þar sem ég er að reyna að reikna út hvar á að setja 55. Minna en 9, minna en 17, minna en 20, færri en 22, færri en 29, minna en 34, nr. Svo nú erum við í tilfelli einn af amk þremur. 

Ef ég vil að setja 55 yfir hér, hvað línur af kóða þarf að fá fram? Hvernig virkar þetta mynd af menn þurfa að breyta? Hvað á ég að gera með vinstri hendi minni? Þetta ætti að vera núll í upphafi, vegna þess að ég er í lok listanum. Og hvað ætti að gerast hér með Pétri, var það? Hann er augljóslega að fara að benda á mig. Svo ég kröfu að það er að minnsta kosti tvær línur af kóða í dæmi um kóða frá í dag það er að fara að framkvæma þetta atburðarás bæta 55 við sporðinn. Og gæti ég hafa einhver hop upp og bara tákna 55? Allt í lagi, þú ert nýja 55. 

Svo nú hvað ef næsta atburðarás kemur með, og við viljum að setja að minnsta hefst eða yfirmaður þessum lista? Og hvað er nafnið þitt, númer 55? 

Áhorfendur: Jack. 

DAVID J. MALAN: Jack? Allt í lagi, gaman að hitta þig. Velkomin um borð. Svo nú erum við að fara að setja, segjum talan 5. Hér er annað mál af þrír við komum upp með áður. Þannig að ef 5 tilheyrir í upphafi, við skulum sjá hvernig við að finna það út. Ég frumstilla PTR minn bendillinn til fjölda 9 aftur. Og ég ljóst, ó, 5 er minna en 9. Svo festa þessa mynd fyrir okkur. Hvers hendur, Gabe er eða David or-- hvað er númer 9 er nafn? 

Áhorfendur: Jen. 

DAVID J. MALAN: hands-- Jen er sem höndum okkar þarf að breyta? Allt í lagi, svo Gabe bendir á hvað nú? Á mig. Ég er nýr hnút. Svo ég ætla bara svona færa hér til að sjá það sjónrænt. Og á meðan hvað ég benda það? Enn þar sem ég er að benda. Svo er það það. Svo bara virkilega ein lína af kóða fastur þetta tiltekna mál, það virðist. Allt í lagi, svo það er gott. Og getur einhver verið staðgengill fyrir 5? Komdu upp. Við munum fá þér næst. 

Allt í lagi, svo now-- og Sem innskot, nöfn Ég ætla ekki að gera skýr minnst á hægri nú, pred músina, forvera músina og ný músina, það er bara nöfn gefin í dæmi um kóða til ábendingum eða hendur mínar sem er eins konar vísa í kring. Hvað er nafn þitt? 

Áhorfendur: Christine. 

DAVID J. MALAN: Christine. Velkomin um borð. Allt í lagi, þannig að við skulum nú íhuga örlítið meira pirrandi atburðarás, þar sem ég vil setja inn eitthvað eins og 26 í þessu. 20? Hvað? Þetta are-- gott við höfum pennann. Allt í lagi, 20. Ef einhver gæti fengið annað stykki af pappír tilbúinn, bara í case-- allt í lagi. Ó, áhugavert. Jæja þetta er dæmi af fyrirlestri galla. Allt í lagi svo er það nafnið þitt aftur? Áhorfendur: Julia. DAVID J. MALAN: Julia, getur þú skjóta út og láta sem þú varst aldrei þarna? OK, þetta gerðist aldrei. Þakka þér. Svo býst við viljum setja Julia í þessu tengda listanum. Hún er fjöldi 20. Og auðvitað er hún að fara að tilheyra að minnsta begin-- ekki benda á neitt ennþá. Svo hönd þín getur konar vera niður null eða einhver sorp gildi. Skulum segja fljótleg saga. Ég benti á númer 5 í þetta sinn. Þá er ég að athuga 9. Þá er ég að athuga 17. Þá er ég að athuga 22. Og átta sig á, ooh, Julia þarf að fara áður en 22. Svo þarf það að gerast? Hvers hendur þarf að breyta? Julia er, minn, or-- hvað er nafnið þitt aftur? 

Áhorfendur: Christian. 

DAVID J. MALAN: Christian eða? 

Áhorfendur: Andy. 

DAVID J. MALAN: Andy. Christian eða Andy? Andy þarf að benda á? Julia. Allt í lagi. Svo Andy, viltu benda á Julia? En bíddu í eina mínútu. Í sögunni svona langt, Ég er the tegund af einn í forsvari, í þeim skilningi að bendillinn er hlutur sem er flytja í gegnum listann. Við gætum hafa nafn fyrir Andy, en það er engin breytu sem heitir Andy. Eina önnur breytan sem við höfum er fyrst, sem er táknað með Gabe. 

Svo er þetta í raun hvers vegna því langt að við höfum ekki þörf á þessu. En nú á skjánum er nefna aftur að pred músina. Svo láta mig vera skýrari. Ef þetta er bendillinn, ég hafði betur fá smá meira greindur um endurtekning mína. Ef þú dont 'hugur ekki að fara minn hérna aftur, sem bendir hér, bendir hér. En láta mig hafa pred músina, forvera músina, það er konar benda á að þáttur sem ég var bara á. Svo þegar ég fer hér, nú vinstri hönd mína uppfærslur. Þegar ég fer hér vinstri hönd mína uppfærslur. Og nú hef ég ekki aðeins bendi til þáttur sem fer eftir Julia, Ég er enn með músina til Andy, þátturinn áður. Svo þú hefur aðgang, í meginatriðum, breadcrumbs, ef þú vilt, að öllum tilskildum ábendingum. 

Þannig að ef ég er að benda á Andy og ég er líka að benda á Christian, sem hendur ætti nú að benda annars staðar? Svo Andy getur nú benda á Julia. Julia geta nú benda á Christian. Vegna þess að hún er að afrita minn hægri hönd er bendi. Og það í raun setur þig aftur inn í þennan stað hér. Svo í stuttu máli, jafnvel þótt það er að taka okkur svona að eilífu að í raun og veru að uppfæra a tengd lista, átta sig að rekstri eru tiltölulega einföld. Það er einn, tveir, þrír línur af kóða á endanum. En vafinn í kringum þá línur af kóða væntanlega er hluti af rökfræði sem í raun spyr hvar eru við spurningunni? Erum við í upphafi, miðju eða hætta? 

Nú, það eru vissulega nokkrar aðrar Rekstur gætum framkvæma. Og þessar myndir hér bara sýna það sem við gerðum rétt með mönnum. Hvað um að fjarlægja? Ef ég vil, til dæmis, fjarlægja númer 34 eða 55, Ég gæti hafa sams konar kóða, en ég ætla að fara að þurfa einn eða tvo skref. Vegna þess að það er nýtt? Ef ég fjarlægja einhvern á endanum, eins og fjölda 55 og síðan 34, hvað hefur einnig að breytast þar sem ég gera það? Ég verð að ekki evict-- hvað er nafnið þitt aftur? 

Áhorfendur: Jack. 

DAVID J. MALAN: Jack. Ég verð að ekki aðeins evict-- frjáls Jack, svo bókstaflega að hringja ókeypis Jack, eða að minnsta kosti bendillinn þar líka, en nú hvað þarf að breyta með Pétri? Hönd hans betra að byrja að benda niður. Því eins fljótt og ég kalla frjáls á Jack, ef Peter er enn benda á Jack og ég að halda því að fara yfir lista og aðgangur þessu músina, það er þegar okkar gamli vinur skiptingu kenna gæti raunverulega sparka í. Vegna þess að við höfum gefið minni aftur til Jack. 

Þú getur dvöl þar vandræðalega fyrir aðeins augnablik. Vegna þess að við höfum bara nokkra endanlegar aðgerðir til að íhuga. Fjarlægi höfuð listanum, eða beginning-- og þetta er smá pirrandi. Þar sem við verðum að vita að Gabe er eins konar sérstakt í þessari áætlun. Vegna reyndar hefur hann eigin bendi hans. Hann er ekki bara verið að benda á, sem er næstum allir aðrir hér. 

Svo þegar höfuð á listanum er fjarlægð, sem hendur þarf að breyta núna? Hvað er nafn þitt aftur? 

Áhorfendur: Christine. 

DAVID J. MALAN: Ég er hræðilegt á nöfn, greinilega. Svo Christine og Gabe, sem hendur þarf til að breyta þegar við reynum að fjarlægja Christine, númer 5, á myndinni? Allt í lagi, þannig að við skulum gera Gabe. Gabe er að fara að benda á, væntanlega, á númer 9. En hvað næsta ætti að gerast? Áhorfendur: Christine ætti vera núll [inaudible]. DAVID J. MALAN: OK, eigum við líklega make-- Ég heyrði "null" einhvers staðar. Áhorfendur: Null og frjáls hana. DAVID J. MALAN: Null hvað? Áhorfendur: Null og frjáls hana. DAVID J. MALAN: Null og frjáls hana. Svo er þetta mjög auðvelt. Og það er fullkomin að þú ert nú að raða að standa þarna, ekki tilheyra. Þar sem þú hefur verið aftengdir frá listanum. Þú hefur í raun verið munaðarlaus úr listanum. Og svo við höfðum betur að hringja frítt nú á Christine að gefa sem minni aftur. Annars hvert skipti sem við eyða hnút úr listanum við gætum verið að gera lista styttri, en í raun ekki minnkandi stærð í minni. Og svo ef við höldum að bæta og bæta, bæta hluti á listann, tölvan mín gæti fengið hægar og hægari og hægari, vegna þess að ég er að keyra út af minni, jafnvel ef ég er ekki í raun nota bæti Christine er af minni lengur. 

Svo í lok eru aðrar atburðarás, sem course-- flutningur í miðju, flutningur í lok, eins og við sáum. En meira áhugavert Áskorunin er nú að fara að vera að íhuga nákvæmlega hvað gangi tíminn er kominn. Svo ekki bara hægt að halda þinn stykki af pappír, ef Gabe, þú myndi ekki huga að gefa allir streitu boltanum. Þakka þér svo mikið að tengda listanum okkar sjálfboðaliða hér, ef þú gætir. 

[Applause] 

DAVID J. MALAN: Allt í lagi. Svo a par af greiningar spurningar þá, ef ég gæti. Við höfum séð þetta tákn áður, stór O og ómega, efri mörk og lægri mörk á því hlaupandi tími sumra reiknirit. Svo skulum íhuga bara a par af spurningum. 

Eitt, og við sögðum henni áður, hvað er í gangi tími leit er listi í skilmálar af stór O? Hvað er efri á gangi tími leita tengda lista eins framkvæmd af sjálfboðaliðum okkar hér? Það er stór O n, línuleg. Vegna þess að í versta tilfelli, þátturinn, eins 55, við gætum verið að leita gæti verið þar Jack var, alla leið á enda. Og því miður, ólíkt array við getum ekki fengið ímynda þessu sinni. Jafnvel þótt öllum mönnum okkar voru raðað frá litlum þætti, 5, alla leið upp að stærri frumefni, 55, það er yfirleitt gott. En hvað þýðir það forsendu ekki lengur leyfa okkur að gera? Áhorfendur: [inaudible] DAVID J. MALAN: Segja aftur? Áhorfendur: Random aðgangur. DAVID J. MALAN: Random aðgangur. Og síðan sem þýðir að við getum ekki lengur notað veikburða núll, innsæi, og Sjálfsagðar að nota tvöfaldur leita og skipta og sigra. Því jafnvel þótt við menn gátu vitanlega sjá að Andy eða Christian voru u.þ.b. í miðjum listanum, við vitum bara að sem tölva með ofanfleytingu lista frá upphafi. Þannig að við höfum gefist upp að handahófi aðgangur. 

Svo stór O n er nú efri bundið á leit okkar tíma. Hvað um omega af leit okkar? Hvað er lægra bundið á að leita fyrir sumir tala í þessum lista? Áhorfendur: [inaudible] DAVID J. MALAN: Segja aftur? Áhorfendur: Einn. DAVID J. MALAN: Einn. Svo stöðug skipti. Í besta tilfelli, Christine er örugglega í upphafi listanum. Og við erum að leita að númer 5, þannig að við fundum hana. Svo ekki máli. En hún fékk að vera á hefst í skránni í þessu tilfelli. Hvað um eitthvað eins og Eyða? Hvað ef þú vilt eyða stak? Hvað er efri og neðri á að eyða eitthvað af tengdur lista? Áhorfendur: [inaudible] DAVID J. MALAN: Segja aftur? Áhorfendur: n. DAVID J. MALAN: n er örugglega efri. Vegna þess að í versta tilfelli við reynum að eyða Jack, eins og við gerðum bara. Hann er alla leið á enda. Tekur okkur að eilífu, eða n skref til að finna hann. Svo er að efri. Það er línulegt, viss. Og það besta mál að keyra tíma, eða lægri mörk í besta tilfelli væri stöðug skipti. Vegna þess að þá reynum við að eyða Christine, og við fáum bara heppin hún er í upphafi. Nú bíddu í eina mínútu. Gabe var einnig í upphafi, og við þurftum líka að uppfæra Gabe. Svo það var ekki bara eitt skref. Svo er það örugglega stöðug tíma, í besta tilfelli, að fjarlægja minnstu frumefni? Það er, jafnvel þó það gæti verið tvær, þrjú, eða jafnvel 100 línur af kóða, ef það er sama fjölda línur, ekki í einhverju lykkju, og óháð stærð á listanum, algerlega. Eyða þáttur í upphaf listanum, jafnvel þótt við þurfum að takast á við Gabe, er enn fasti tími. 

Svo virðist þetta eins og gegnheill skref aftur á bak. Og hvað er tímasóun ef í viku eitt og viku núll við höfðum ekki aðeins sauðakóðanum kóða en raunverulegt númer að innleiða eitthvað sem er Log stöð n, eða log, frekar, í eru N, stöð 2, í skilmálar af hlaupandi tími til þess. Svo hvers vegna Heck myndum við vilja til að byrja nota eitthvað eins og tengda listanum? Já. 

Áhorfendur: Svo er hægt að bæta við þættir til fylkisins. DAVID J. MALAN: Svo þú getur bæta þætti til fylkisins. Og þetta er líka þema. Og við munum halda áfram að sjá þetta, þetta málamiðlun, mikið eins og við höfum séð málamiðlun með sameiningu tagi. Við gætum í raun flýta leita eða flokka, heldur, ef við eyða aðeins meira pláss og hafa frekari klumpur af minni eða fylki til að sameiningu tagi. En við eyðum meira rúm, en við að spara tíma. Í þessu tilviki, við erum gefa upp tíma, en við erum öðlast sveigjanleika, kraftur ef þú vilt, sem er að öllum líkindum jákvæð lögun. 

Við erum einnig að eyða pláss. Í hvaða skilningi er tengdur lista dýrari hvað varðar pláss en fjölda? Hvar er auka pláss koma frá? Já? 

Áhorfendur: [inaudible] músina. 

DAVID J. MALAN: Já, við Einnig hafa músina. Svo er þetta minorly pirrandi í að ekki lengur am Ég geyma bara á int til að tákna int. Ég geyma við int og a músina, sem er einnig 32 bita. Þannig að ég ætla bókstaflega tvöföldun pláss að ræða. Svo er það málamiðlun, en það er um er að ræða Int. Segjum sem svo að þú sért ekki að geyma int, En geri ráð fyrir hvert þessara rétthyrninga eða hver af þessum mönnum var fulltrúi orð, ensku orð sem gæti verið fimm stafir, 10 stafir, kannski jafnvel meira. Þá bæta bara 32 fleiri bita gæti verið minna af a stór samningur. 

Hvað ef hver af þeim nemendum í mótmælum voru bókstaflega nemandi structs sem hafa nöfn og hús og kannski símanúmer og Twitter handföng og þess háttar. Svo öllum sviðum við byrjuðum að tala um um daginn, miklu minna af a stór samningur sem hnúður okkar fá meira áhugavert og stór til að eyða, ha, til viðbótar bendi bara á að tengja þá saman. En reyndar er það málamiðlun. Og reyndar, kóðinn er flóknari, eins og þú munt sjá með ofanfleytingu gegnum sem einkum dæmi. En hvað ef það voru sumir Gral hér. Hvað ef við ekki að taka skref aftur á bak en gegnheill skref fram og innleiða gögn uppbygging í gegnum sem við getur fundið þætti eins Jack eða Christine eða önnur atriði í þessu fylki í sanna föstu tíma? Leit er fasti. Eyða er fasti. Setja er fasti. Öll þessi starfsemi er fasti. Það væri okkar gral. Og það er þar sem við vilja ná upp næst. Sjáumst þá.