[Muzikos grojimo] David J. Malan: Gerai. Tai CS50. Tai yra penki savaitę tęsiamas, ir mes turi gerų naujienų ir blogų naujienų. Taigi gera naujiena yra ta, kad CS50 pradeda šį penktadienį. Jei norėtumėte prisijungti prie mūsų, galvą į įprastą URL čia. Dar geriau žinia, ne paskaita tai ateina pirmadienis 13. Šiek tiek mažiau geresnės naujienos, viktorina nulis kitą trečiadienį. Išsamesnė informacija gali būti rasti šiuo URL čia. Ir per ateinančius porą dienų mes būti užpildyti ruošiniai Kalbant apie kambariuose kad turėsime saugomos. Geriau naujienos yra tai, kad ten bus būti žinoma pasaulyje apžvalga sesijos ateinančiais Pirmadienį vakare. Stay tuned į aikštyno svetainės vietą ir duomenis. Skyriai, nors ji yra atostogų, taip pat susitiks su taip pat. Geriausia naujiena, paskaita kitą penktadienį. Taigi tai yra tradicija, mes turi, kaip už mokymo programas. Just-- tai bus nuostabu. Jūs matote tokius dalykus pastovus laiko duomenų struktūros ir maišos lentelės ir medžiai ir bando. Ir mes kalbame apie gimtadienio problemų. Visa krūva daiktų laukia kitą penktadienį. Gerai. Šiaip ar taip. Taigi prisiminti, kad mes buvome sutelkiant dėmesį į šį, kas paveikslėlyje viduje mūsų kompiuterio atmintyje. Taigi atmintis arba RAM Kai programos egzistuoja, o jūs dirbate juos. Jei dukart spustelėkite piktograma paleisti kai programa arba dukart spustelėkite icon atidaryti tam tikrą failą, jis pakrautas iš standžiojo vairuoti ar kietojo disko į RAM, Random Access Memory, kur jis gyvena, kol galios užgęsta, nešiojamas dangtis užsidaro, ar jums išeiti iš programos. 

Dabar, kad atmintis, iš kuris tikriausiai turite 1 gigabaitą šių dienų, 2 gigabaitų, arba net daug daugiau, paprastai išdėstyti už tam tikrą programą Šiame stačiakampius rūšiuoti koncepcinis modelis , kai mes turime krūvą apačioje ir kitų daiktų krūva viršuje. Pačiame viršuje dalykas mes matėme šioje nuotraukoje anksčiau, bet niekada kalbėjo apie yra vadinamasis teksto daliai. Tekstas segmentas yra tik išgalvotas būdas sakydamas nuliai ir tie, kurie kurti savo tikrąjį parengta programa. 

Taigi, kai jūs dukart spustelėkite "Microsoft Word" ant jūsų Mac arba PC, arba kai paleidžiate dot slash Mario ant "Linux" kompiuteris jūsų terminalo langą, kad nuliai ir tie, kurie sudaro Žodis arba Mario laikinai saugomi į kompiuterio RAM vadinamasis teksto segmentas tam tikrą programą. Žemiau kad eina inicializuoti ir niezainicjowanymi duomenys. Tai stuff like globalių kintamųjų, kad mes ne naudoti daug, bet kartais mes turėjo globalių kintamųjų arba statiškai nustatyta eilutes, kuriose yra sunkiai koduojami žodžius, pavyzdžiui, "labas" kad nėra atsižvelgiama į nuo naudotojo kurie sunkiai koduojami į savo programą. 

Dabar, žemyn apačioje mes turi vadinamąjį kamino. Ir kamino, iki šiol mes buvome naudodamas Kokias tikslais? Kas kamino buvo naudojamas? Taip? 

Auditorija: funkcijos. 

David J. Malan: Dėl funkcijų? Kokia prasme funkcijas? 

PUBLIKA: Kai Jūs skambinate funkciją, argumentai yra nukopijuojami ant kamino. 

David J. Malan: Būtent. Kai Jūs skambinate funkciją, jos argumentai yra nukopijuojami ant kamino. Taigi bet kokie X arba Y s arba s arba B s kad jūs artimųjų į funkciją laikinai įdėti vadinamasis kamino, kaip vieną iš Annenberg valgykla padėklai, taip pat dalykų, kaip lokalūs kintamieji. Jei jūsų foo funkcija arba jūsų apsikeitimo funkcija turi lokalių kintamųjų, kaip temp, tie du baigti ant kamino. Dabar, mes ne kalbėti per daug apie juos, bet šie aplinkos kintamieji apačioje matėme, o kai prieš Buvau futzing prie klaviatūros vieną dieną ir aš pradėjau susipažinimo dalykus kaip argv 100 ar argv 1000, tiesiog elements-- aš pamiršiu numbers-- bet nebuvo manoma, kad būti atvertas mane. Mes pradėjome matyti kai funky simbolių ekrane. Tai buvo vadinamasis aplinkos kintamieji kaip pasaulio nustatymų mano programa ar mano kompiuteryje, o ne nesusijęs su neseniai klaida, aptarėme, Shellshock, kad manimi buvo kamuojančios gana keletą kompiuterių. 

Dabar galiausiai, šiandienos dėmesys mes galiausiai ant krūvos. Tai dar viena atminties riekė. Ir iš esmės visa tai atmintis pati medžiaga. Tai pats aparatūros. Užtenka tik rūšiuoti gydant įvairias grupes baitų skirtingais tikslais. Krūva taip pat bus kur kintamieji ir atmintis, kad prašote iš operacinės sistemos laikinai saugomi. 

Bet ten rūšies problema čia kaip paveikslėlį reiškia. Mes tarsi turime du laivai apie susidūrimui. Kadangi, kaip jūs naudojate daugiau ir daugiau iš kamino, ir, kaip matome šiandien pirmyn, kaip jūs naudojate daugiau ir daugiau krūva, tikrai blogi dalykai gali atsitikti. Ir iš tiesų, mes galime sukelti, kad tyčia ar netyčia. Taigi Cliffhanger paskutinio laikas buvo ši programa, kurie netarnavo bet funkcinis išskyrus įrodyti tikslas kaip jus kaip blogiukas iš tiesų gali imtis privalumas klaidas kažkieno programos ir perimti programą ar net Visa kompiuterinė sistema ar serveryje. Taigi tiesiog pažvelgti trumpai jums pastebėti, kad apačioje main trunka komandinėje eilutėje argumentai, kaip už argv. Ir ji turi ryšį su funkcija f, iš esmės vadinamas bevardis funkcija f, ir tai einančios argv [1]. 

Taigi nepriklausomai žodis vartotojas rūšys ne greitai po šios programos pavadinimas, ir tada šis savavališkas funkcija iki viršuje, f, trunka eilutę, AKA char * kaip mes pradėjo diskutuoti, ir jis tiesiog vadina jį "baras". Tačiau mes galime jį vadinti nieko. Ir tada jis pareiškia, viduje iš F, kurio simbolių masyvas vadinamas c-- 12 tokių simbolių. 

Dabar, pagal istoriją, aš sakau, prieš momentas, kur į atmintį yra C, arba tie, 12 simbolių ketina baigti? Tiesiog kad būtų aišku. Taip? 

PUBLIKA: Ant kamino. 

David J. Malan: Ant kamino. Taigi, c yra vietos kintamąjį. Mes prašome 12 simbolių arba 12 baitų. Tie, kurie ketina baigti apie vadinamąjį kamino. Dabar pagaliau tai kitas funkcijas, kad tikrai gana naudingas, bet mes ne iš tikrųjų naudoti tai patys, strncopy. Tai reiškia, string kopiją, tačiau tik n raides, n simbolių. Taigi n simbolių bus nukopijuoti iš baro į c. Ir kiek? Iš strypo ilgis. Taigi, kitaip tariant, kad viena eilutė, strncopy, ketina kopijuoti efektyviai uždrausti į c. 

Dabar, tik rūšies numatyti Šios istorijos moralas, kas potencialiai problematiškas čia? Nors mes patikrinti ilgio Baro ir perduoti ją į strncopy, Kokia jūsų žarnų pasakoja jums yra dar suskaidytas apie šią programą? Taip? 

PUBLIKA: Neapima kambarys null pobūdžio. David J. Malan: Neapima kambarys null pobūdžio. Potencialiai, skirtingai nei praeityje buvo taikoma praktika, mes net ne turi tiek, kiek pliuso nuo 1 iki prisitaikyti, kad null charakterį. Bet tai dar blogiau nei tai. Ką dar mes nesugeba padaryti? Taip? 

PUBLIKA: [nesigirdi] David J. Malan: Perfect. Mes sunkiai koduojami 12 gana savavališkai. Tai nėra tiek daug problema, tačiau tai, kad mes net ne, jei tikrinant baro ilgis yra mažesnis kaip 12, tokiu atveju jis bus saugu jį į atmintį vadinama c, kad mes skiriama. Iš tiesų, jei baras yra tarsi 20 simbolių ilgio, Atrodo, ši funkcija turi būti nukopijuoti 20 simbolių iš baro į c, taip atsižvelgiant bent 8 baitus kad ji neturėtų būti. Štai potekstė čia. 

Taigi trumpai tariant, skaldytų programą. Ne toks big deal. Gal jums segmentavimo kaltės. Mes visi turėjo klaidas programose. Mes visi gali turėti klaidų programose dabar. Bet kas problema? Na, čia Priartinti portalo kad mano kompiuterio atmintyje nuotrauka. Tai mano kamino apačioje. Ir iš tiesų, pačioje apačioje yra kas vadinamas tėvų rutina kamino, išgalvotas būdas pasakyti, kad pagrindinis. Taigi, kad kas vadinama funkcija f, kad mes kalbame apie. Taigi tai iš kamino apačioje. Grįžti adresas yra kažkas naujo. Tai visada buvo ten, visada buvo toje nuotraukoje. Mes tiesiog niekada atkreipė dėmesį į jį. Nes paaiškėja, būdas c veikia, yra kad kai viena funkcija ragina kitas, ne tik tai, į argumentus, kad funkcija gauti stumiama ant kamino, ne tik padaryti funkcija vietinis kintamieji gauti stumiama ant kamino, kažkas vadinamas atgalinis adresas taip pat gauna įdėti ant kamino. Tiksliau, jeigu pagrindinis skambučiai foo pagrindiniai s savo adresą atmintyje, jautis, ką, efektyviai pasireiškia įdėti į kaminą kad, kai f yra padaryta, kad vykdant žino, kur šokti atgal į tekstą segmentas, siekiant tęsti vykdymą. 

Taigi, jei mes čia konceptualiai, į Pagrindinis, tada f iškviečiamas. Kaip veikia f žinoti, kas rankose kontrolės nugaros? Na, tai tiek tinklalapio raudonai čia vadinamas atgalinis adresas, jis tiesiog patikrinimai, kas tai yra atgalinis adresas? O, leiskite man šokti atgal į pagrindinį čia. Ir tai šiek tiek kurio supaprastinimas, nes nulių ir pagrindiniam yra techniškai čia į technologijų segmente. Bet tai idėja. f tiesiog turi žinoti, ką kur kontrolė galiausiai nueina. 

Bet kaip kompiuterių jau seniai išdėstyti dalykus kaip lokalūs kintamieji ir argumentai yra tokia. Taigi šio paveikslėlio viršuje mėlyna kamino rėmas f, todėl visi iš atminties, kad f specialiai naudoja. Taigi atitinkamai, pastebėsite, kad baras šiame paveikslėlyje. Baras buvo jo argumentas. Ir mes teigė, kad argumentai funkcijos gauti stumiama ant kamino. Ir C, be abejo, yra Taip pat šiame paveikslėlyje. 

Ir tik notacijos tikslais, pastebėti viršutiniame kairiajame kampe yra tai, ką būtų c laikiklio 0 ir tada šiek tiek žemyn į dešinę is c laikiklis 11. Taigi, kitaip tariant, jūs galite įsivaizduoti, kad ten baitų tinklelis ten, iš kurių pirmasis yra viršuje, kairėje, apačioje, iš kurių yra paskutinis iš tų 12 baitų. 

Bet dabar pabandykite pirmyn. Kas yra bręsti, jei mes pereiti į styginių juostoje, kad ilgesnio nei c? Ir mes ne, jei tikrinant tai tikrai ilgiau nei 12. Kuris iš šioje nuotraukoje ketina gauti perrašyti baitų 0, 1, 2, 3, dot dot dot, 11, ir tada blogai, 12, 13 per 19? Kas nutiks čia, jei išvesti iš užsakymo kad c laikiklis 0 yra ant viršaus ir c laikiklis 11 yra tarsi žemyn į dešinę? Taip? 

PUBLIKA: Na, tai vyksta perrašyti char * juostą. 

David J. Malan: Taip, atrodo, kad jūs ketinate perrašyti char * juostą. Ir dar blogiau, jei jūs siųsti tikrai ilgai eilutę, galbūt net perrašyti ką? Atgalinis adresas. Kuris vėl yra kaip tinklalapio pasakyti programa, kur grįžti į kai f daroma vadinamas. 

Taigi, kas blogi vaikinai paprastai padaryti yra, jei jie susiduria programos kad jie yra smalsūs, ar yra naudoti, Buggy tokiu būdu kad jis arba ji gali imtis privalumas tame klaidą, paprastai jie negauna ši teisė pirmą kartą. Jie tiesiog pradėti siųsti, pavyzdžiui, atsitiktinių stygos į savo programą, ar prie klaviatūros, ar atvirai jie tikriausiai rašyti mažai programa tiesiog automatiškai generuoti stygos, ir pradėti beldžiasi į jūsų programą siunčiant daug įvairių žaliavų skirtingų ilgių. 

Kai tik jūsų programos avarijos, tai nuostabus dalykas. Nes tai reiškia, kad jis ar ji atrado kas tikriausiai iš tikrųjų klaida. Ir tada jie gali gauti daugiau protingas ir pradėti daugiau dėmesio siaurai apie tai, kaip išnaudoti tą klaidą. Visų pirma, tai, ką jis arba ji gali padaryti, tai atsiųsti, geriausiu atveju, labas. Nėra baisi. Tai styginių tai pakankamai trumpas. Bet kas, jei jis ar ji siunčia, ir mes apibendrinti kaip, ataka code-- taip nuliai ir tie, kurie daryti dalykus kaip rm-rf, kad pašalinti viską iš kietojo disko arba siųsti šlamštas ar kažkaip pulti mašiną? 

Taigi, jei kiekvienas iš jų laiškai tiesiog reiškia, konceptualiai, ataka, puolimas, ataka, ataka, kai blogas kodas kad kažkas parašė, bet jei tas asmuo yra pakankamai protingas, ne tik apima visas tų RM-RFS, bet taip pat jo arba jos paskutinius kelis baitus būti numerį, kuris atitinka į adreso jo ar jos pačios ataka kodas kad jis ar ji praėjo tik teikiant jį greitai, jūs galite efektyviai apgauti kompiuterį į pastebiu, kai f yra daroma vykdant, oh, tai laikas man pereiti atgal į raudoną atgalinį adresą. Bet kadangi jis ar ji turi kažkaip sutapo, kad atgalinį adresą su savo numeriu, ir jie pakankamai protingas, į sukonfigūravote, kad skaičius remtis, kaip jums pamatyti super viršuje kairiajame kampe ten, Faktinis adresas kompiuterio atminties kai jų atakos kodą, blogas vaikinas gali apgauti kompiuterį į vykdančiosios savo paties kodą. 

Ir tai kodas, vėlgi, gali būti bet kas. Tai paprastai vadinama apvalkalas kodas, kuris yra tik pasakyti, kad tai ne būdas paprastai kažkas taip paprasta, kaip rm-rf. Tai tikrai kažkas panašaus Bash, arba faktinis programa, kuri suteikia jam ar jos programinis valdymas vykdyti dar ką nors, kad jie nori. Taigi trumpai tariant, visa tai kilęs iš paprasto fakto, kad ši klaida dalyvauja ne tikrinti kad jūsų masyvo ribos. Ir todėl, kaip kompiuteriai darbą yra tai, kad jie naudoti nuo kamino efektyviai, konceptualiai, Apačia up, bet tada elementai Paspaudus ant kamino auga iš viršaus į apačią, tai yra neįtikėtinai sudėtinga. Dabar, yra būdų, kaip išspręsti šią. Ir tiesą sakant, yra kalbos , su kuria dirbti aplink tai. Java yra imuninės, pavyzdžiui, šiuo konkrečiu klausimu. Kadangi jie neturi duoti jums patarimų. Jie nesuteikia jums tiesioginės atminties adresai. Taigi su tokia galia, kad mes turime liesti nieko atmintyje Mes norime, kad ateina, tiesa, didelė rizika. 

Taigi stebėkite. Jei atvirai, mėnesiais ar ateinančių metų, kada perskaityti apie kai išnaudojimo iš programos ar serverio, jei jūs kada nors pamatyti kažką užuominą kaip buferio perpildymo atakos arba kamino perpildymo yra kito tipo ataka, panaši dvasia, kiek įkvepia interneto svetainės pavadinimas, jei jį žinote, visa tai kalbame tik apie perpildyta su kai kurių charakterio dydį masyvas ar kai masyvas apskritai. Turite klausimų, tuomet apie tai? Nebandykite to namuose. 

Viskas gerai. Taigi malloc šiol buvo mūsų naujas draugas, kad mes galime paskirstyti atmintį kad mes nebūtinai žinoti iš anksto, kad mes norime, kad mes neturime į kietąjį kodą į mūsų programos numerius, pavyzdžiui, 12. Kai vartotojas pasako kiek duomenys, jis ar ji nori įvesti, mes galime malloc kad daug atminties. 

Taigi malloc it turns out, kad Kiek mes jau jį naudojant, aiškiai paskutinį kartą, ir tada vaikinai buvo naudojant jį už getstring nežinodami už keletą savaičių, visi malloc atminties kilęs iš vadinamųjų krūvą. Ir tai, kodėl getstring, pavyzdžiui, gali paskirstyti atmintį dinamiškai nežinant, ką jūs ketina įvesti iš anksto, perduoti jums atgal žymiklį į tą atmintį, ir kad atmintis vis dar tavo išlaikyti, net po getstring grąžą. Kadangi priminti juk, kad kamino nuolat vyksta aukštyn ir žemyn, aukštyn ir žemyn. Ir kuo greičiau, kaip jis eina žemyn, tai reiškia, kad bet kokios atminties ši funkcija naudojama turėtų negali būti naudojama niekam kitam. Tai šiukšlių vertybes dabar. 

Bet krūva yra čia. Ir kas malonu apie malloc yra tai, kad kai malloc paskirsto atmintį iki čia, tai ne įtakos, nes didžioji dalis, kurią kamino. Ir taip bet funkcija gali naudotis atmintis, buvo malloc'd, net panašaus getstring funkcija, net po to, kai jis grįžo. 

Dabar, iš malloc Converse yra nemokama. Ir iš tiesų, ši taisyklė jums reikia pradėti priimti yra bet, bet, bet kuriuo metu jūs naudojate malloc turite sau naudoti nemokamai, galiausiai, tą pačią rodyklę. Visą šį laiką mes buvome raštu Buggy, Buggy kodas, dėl daugelio priežasčių. Tačiau vienas iš jų buvo naudojant CS50 biblioteką, kuri pati yra sąmoningai Buggy, ji nutekėjo atminties. Bet koks laikas, jūs vadinamas getstring Per pastaruosius keletą savaičių Mes prašome operacinės sistema, Linux, už atmintį. Ir jūs niekada kartą atidavė jį atgal. Ir tai ne, ir praktika, yra geras dalykas. 

Ir Valgrind, vienas iš įvestos Pset 4 įrankiai yra visa informacija apie Jums padėti dabar radote klaidų, pavyzdžiui, kad. Bet laimei Pset 4 nereikia naudoti CS50 biblioteką ar getstring. Taigi bet kokie klaidų, susijusių su atminties yra galiausiai bus jūsų pačių. 

Taigi malloc yra daugiau nei tiesiog patogu šiam tikslui. Mes iš tikrųjų dabar gali išspręsti iš esmės skirtingos problemos, ir iš esmės spręsti problemas daugiau veiksmingai, kaip per savaitę nulis pažadą. Iki šiol tai yra seksualiausia duomenų struktūra, mes turėjome. Ir duomenų struktūros Aš tiesiog reiškia, iš konceptualizavimo atminties būdas tokiu būdu, kuris peržengia tiesiog pasakyti, tai int, tai char. Mes galime pradėti klasterio dalykų kartu. 

Taigi masyvas atrodė taip. Ir tai, kas buvo raktas apie masyvas yra tai, kad ji suteikia jums back-to-back gabaliukus atmintis, iš kurių kiekvienas bus to paties tipo, int int, int, int arba char, char, char, char. Tačiau yra keletas praradimas. Tai, pavyzdžiui, yra dydžio šešių masyvo. Tarkime, jūs užpildyti šią masyvas su šešių Skaičiai ir tada, dėl kokių nors priežasčių, Jūsų vartotojas nori suteikti Jūs septintojo skaičius. Kur jūs įdėti jį? 

Kas sprendimas, jei turite sukurta masyvą į kaminą, Pavyzdžiui, tik su savaitės du žymėjimas, kurį mes pristatėme, iš laužtiniuose skliaustuose su numeriu viduje? Na, jūs turite šešis Skaičiai šiose dėžėse. Ką jūsų instinktai būti? Kur gi jūs norite įdėti jį? 

PUBLIKA: [nesigirdi] 

David J. Malan: Atsiprašome? 

PUBLIKA: Padėkite jį ant galo. 

David J. Malan: Padėkite jį ant galo. Taigi šiek tiek daugiau nei į dešinę, už šį bloką. Kuris būtų malonu, bet tai Pasirodo, jūs negalite padaryti. Nes jei jūs neprašė Šio atminties riekė, tai gali būti sutapimas, kad šioje yra naudojamas kitu kintamuoju apskritai. Prisiminkite savaitę arba tiek, kai mes nustatyti iš Zamyla and Davin and Gabe s pavadinimų atmintyje. Jie buvo tiesiog atgal atgal į nugarą. Taigi, mes ne visada gali pasitikėti, kad visada kas per čia galima man naudoti. 

Taigi, ką dar gali padaryti? Na, kai supranta jus reikia iš dydžio septynių masyvą, galite tiesiog sukurti masyvas dydžio septynių tada naudokite už linijos arba while cikle, nukopijuokite jį į naują masyvą, ir tada kažkaip tik atsikratyti tai masyvas arba tiesiog nustoti jį naudoti. Bet tai nėra labai veiksminga. Trumpai tariant, matricas neleiskite Jūs dinamiškai keisti. 

Taigi, viena vertus, jūs gaunate laisvosios kreipties, kuri yra nuostabi. Nes ji leidžia mums daryti tai, ko kaip skaldyk ir valdyk, Dvejetainis paieškos, ir visa tai mes kalbėjo apie ekrane čia. Bet jūs dažų save į kampą. Kai paspausite Jūsų masyvo pabaigos, jūs turite padaryti labai brangus eksploatavimas arba rašyti visa krūva kodas dabar spręsti šią problemą. 

Taigi ką daryti, jei vietoj to mes turėjome kažkas vadinamas sąrašą, arba susiję sąrašą visų pirma? Ką daryti, jei vietoj to, kad stačiakampiai atgal atgal atgal, turime stačiakampiai, kad palieka mažai tiek kraipymas kambarį tarp jų? Ir nors aš sudarytas šis paveikslėlį ar pritaikyti šį paveiksliuką vieną iš tekstų čia grįžti į atgal atgal labai tvarkingai, iš tikrųjų, vienas iš tų stačiakampių gali būti čia atmintyje. Vienas iš jų gali būti čia. Vienas iš jų galėtų būti čia, per čia, ir taip toliau. 

Bet kas, jei mes padarė, šiuo atveju, strėlės kad kažkaip susieti juos stačiakampių kartu? Iš tiesų, mes matėme techninis įsikūnijimas rodykle. Ką mes naudojamas neseniai dienų, kad po gaubtu, atvaizduoja rodykle? Žymeklis, tiesa? 

Taigi ką daryti, jei, užuot tiesiog laikyti numerius, kaip 9, 17, 22, 26, 34, Ką daryti, jei mes saugomi ne tik skaičius, bet žymeklis šalia kiekvieno tokio skaičiaus? Taigi, kad panašiai kaip jūs sriegis adatą per visa krūva audinio, kažkaip susiejimas dalykai kartu, panašiai gali mes su rodyklėmis, kaip įsikūnijęs rodyklėmis čia rūšies pynimo kartu šie atskiri stačiakampiai efektyviai naudojant žymiklį šalia kiekvieno numerio, kad atkreipia dėmesį į tam tikrą kitą skaičių, kad atkreipia dėmesį į, savo ruožtu, kai šalia skaičius? Taigi, kitaip tariant, jei mes iš tikrųjų norėjo įgyvendinti kažką panašaus į tai? Na, deja, šie stačiakampiai, Bent jau vienas su 9, 17, 22, ir taip toliau, tai jau nebėra gražūs kvadratėliai su atskirais numeriais. Apačioje, stačiakampio Toliau 9, pavyzdžiui, atitinka tai, ką turėtų būti žymeklis, 32 bitai. Dabar, aš dar nežino apie bet duomenų tipas C, kuris suteikia jums ne tik int bet žymeklis apskritai. 

Taigi, kas yra sprendimas, jei norime sugalvoti savo atsakymo į šį klausimą? Taip? 

PUBLIKA: [nesigirdi] 

David J. Malan: Kas tai? 

PUBLIKA: Naujoji struktūra. 

David J. Malan: Taip, taip, tai kodėl ne mes sukurti naują struktūrą, arba C, struct? Mes matėme structs anksčiau, jei trumpai, kur mes buvo susiję su studento struktūra kaip tai, kas ir turėjo pavadinimą ir namą. Be Pset 3 Breakout naudojote visa krūva structs-- GRect ir GOvals kad Stanfordo sukurta klasteris informacija kartu. Taigi ką daryti, jei mes priimsime tą pačią idėją raktiniai žodžiai "Typedef" ir "struct", ir tada kai studentas konkrečių dalykų, ir vystytis į šiuos taip: Typedef konstrukto node-- ir mazgas yra tik labai bendro pobūdžio informatikos Terminas kažko duomenų struktūros, į duomenų struktūrą konteineris. Mazgas galiu reikalauti teks int n, visiškai nesudėtingas, ir tada šiek tiek daugiau cryptically, tai antra linija, konstrukto mazgas * šalia. Tačiau mažiau techninių terminų, kas tai yra antroji linija kodo viduje klamrami? Taip? 

PUBLIKA: [nesigirdi] David J. Malan: žymiklį į kitą mazgą. Taigi reikia pripažinti, sintaksės tiek paslaptingas. Bet jei jūs jį skaityti pažodžiui, šalia yra kintamojo vardas. Kas yra jo duomenų tipas? Tai šiek tiek kalbantys, šį kartą, bet tai tipo struct mazgas *. Bet koks laikas, mes matėme kažką žvaigždė, kad reiškia, kad jis žymiklį į tą duomenų tipą. Taigi, kitą, matyt, Rodyklė į struct mazgas. 

Dabar, kas yra konstrukto mazgas? Na, pastebėsite, pamatysite tuos, tie patys žodžiai viršuje dešinėje. Ir iš tiesų, jūs taip pat pamatysite žodį "Mazgas" žemyn čia, apačioje, kairėje. Ir iš tikrųjų tai yra tik patogumo. Atkreipkite dėmesį, kad mūsų studentų apibrėžimo ten žodis "studentas" tik vieną kartą. Ir tai todėl, kad studentas objektas buvo ne subjektyviais kriterijais. Nėra nieko viduje studentas kad reikia atkreipti dėmesį į kitą studentas, persay. Tai būtų tarsi keista realiame pasaulyje. 

Bet su per mazgas susieti sąrašas, mes norime mazgas būti Godbijīgs panašiu daiktu. Ir taip pastebėsite čia kaita nėra tik tai, kas viduje garbanotas petnešomis. Bet mes pridėti žodį "mazgas" viršuje, taip pat pridedant jį į apačią vietoj "studentas". Ir tai yra tik techninė detalė taip, kad vėl, jūsų duomenų struktūra gali tik savimi, kad mazgas gali nurodyti kitas toks mazgas. 

Taigi, kas tai yra galiausiai ketina reikšti mus? Na, vienas, ši medžiaga viduje yra mūsų mazgas turinys. Šis dalykas čia, viršuje dešinėje, yra tik tiek kad, vėlgi, galime kreiptis į save. Ir tada atokiausiuose dalykų, nors mazgas yra naujas terminas, tai, kad jis vis dar pats, kaip studentų ir ką buvo po į SPL gaubtu. 

Taigi, jei mes dabar norėjau pradėti Įgyvendinant šią susietą sąrašą, kaip gali mes verčiame kažkas panašaus į tai kodas? Na, tegul tik pamatyti pavyzdys programos, faktiškai naudoja susietą sąrašą. Tarp šiandienos platinimo kodą yra programa, vadinama Sąrašas nulis. Ir jei aš paleisti tai aš sukūriau super paprastas GUI, Graphical User Interface, bet tai tikrai tik printf. Ir dabar aš jau davė sau keletą meniu options-- Ištrinti, Įterpti, Paieška, ir Traverse. Ir Baigti. Tai yra tik bendros operacijos duomenų struktūra vadinama nuoroda, sąrašą. 

Dabar Ištrinti ketina ištrinti iš sąrašo numerį. Įdėkite ketina pridėti skaičius į sąrašą. Paieška atrodys už numerį sąraše. Ir ėjimas yra tik išgalvotas būdas sakydamas, vaikščioti per sąrašą, atspausdinti jį, bet viskas. Negalima pakeisti jį bet kokiu būdu. 

Taigi pabandykime tai. Vykime į priekį ir 2 tipo. Ir tada aš ruošiuosi įterpti numerį, pasakyti 9. Įveskite. Ir dabar mano programa yra tik užprogramuotas pasakyti, sąrašas dabar yra 9. Dabar, jei aš einu į priekį ir do Įdėkite vėl, leiskite man eiti į priekį ir nutolinti ir įveskite 17. Dabar mano sąraše yra 9, o po to 17. Jei aš įdėti vėl praleiskime vieną. Vietoj 22, kaip už paveikslėlyje mes ieškau ne čia, leiskite man šokti į priekį ir įdėkite 26 sekantis. Taigi, aš ruošiuosi 26 tipo. Sąrašas, kaip aš tikėtis. Bet dabar, tik pamatyti, jei šio kodekso bus lankstus, leiskite man dabar 22 tipas, kuris bent konceptualiai, jei mes Tęsdami šią rūšiuojamos, kuris yra iš tikrųjų bus dar vienas tikslas dabar, turėtų eiti tarp 17 ir 26. Taigi, aš paspauskite Enter. Iš tiesų, tai veikia. Ir todėl dabar leiskite man įdėti paskutinis, už nuotrauką, 34. 

Viskas gerai. Taigi dabar leiskite man nustatyta, kad Ištrinti ir Travers ir paieška padaryti, iš tiesų, dirbti. Iš tiesų, jei aš paleisti paiešką, tegul ieškoti skaičiaus 22, Enter. Jis nustatė 22. Taigi, kad yra tai, kas tai programa Sąrašas nulis daro. 

Bet ką iš tikrųjų vyksta apie tai įgyvendina tai? Na, visų pirma aš gali turėti ir iš tiesų Aš turiu, failas, vadinamas list0.h. Ir kažkur ten tai linija, Typedef, konstrukto mazgas, tada turiu garbanotas petnešos, int n, ir tada struct-- kas apibrėžimas? Kapitalo struktūra mazgas šalia. Taigi, mes turime žvaigždė. Dabar techniškai mes į piešimo čia įprotis. Jūs galite pamatyti vadovėlius ir Prisijungę nuorodos daryti ten. Tai funkciškai lygiavertės. Tiesą sakant, tai yra šiek tiek daugiau tipiškas. Bet aš būsiu atitinka tai, ką mes padarėme paskutinį kartą ir tai padaryti. Ir tada galiausiai, aš ruošiuosi tai padaryti. 

Taigi antraštės failą kažkur į list0.h šiandien tai konstrukto apibrėžimą, o gal kai kurių kitų dalykų. Tuo tarpu list0c ten bus keletas dalykų. Tačiau mes ketiname tik pradėti, o ne užbaigti tai. List0.h yra failas Noriu įtraukti į mano C failą. Ir tada tam tikru momentu aš teks int, pagrindinis, negalioja. Ir tada aš ruošiuosi turi keletą darbų čia. Aš taip pat teks prototipas, kaip tuščia, paiešką, int, N, kurio gyvenimo tikslas yra ieškoti elemento. Ir tada žemyn čia galiu reikalauti iš Šiandienos kodas, negaliojančiu, ieškoti, int n, ne kabliataškis, bet atviros garbanotieji petnešų. Ir dabar aš noriu kažkaip ieškoti už šio sąrašo elementas. Tačiau mes neturime pakankamai informacija ekrane dar. Turiu ne iš tikrųjų atstovavo pats sąrašas. Taigi vienas iš būdų mes galime įgyvendinti susiję sąrašas programą yra I rūšies nori kažką daryti kaip Pareiškiu susiję sąrašą čia. Kad būtų paprasčiau, aš ruošiuosi padaryti tai pasaulinė, nors apskritai mes neturėtų daryti tai per daug. Bet tai bus supaprastinti šį pavyzdį. Taigi noriu paskelbti susiję sąrašas čia. Dabar, kaip galėčiau tai padaryti? 

Štai iš susietą sąrašo nuotraukos. Ir aš tikrai ne žinoti metu how Aš ruošiuosi eiti apie atstovaujantis tiek daug dalykų, tik su vienu kintamasis atmintyje. Bet prisiminkite akimirką. Visą šį laiką mes turėjome stygos, kurį mes tada atskleidė, kad matricos simbolių, kuriuos mes tada atskleidė tiesiog rodyklė į pirmąjį požymį į simbolių masyvas Štai null nutrauktas. Taigi, šia logika, ir su šiuo nuotrauka rūšies sėti savo mintis, ką mums reikia iš tikrųjų parašyti mūsų kodas atstovauti susietą sąrašą? Kiek šios informacijos mums reikia, užfiksuoti C kodą, galėtumėte pasakyti? Taip? 

PUBLIKA: Mums reikia žymiklį į mazgą. David J. Malan: Rodyklė į mazgą. Visų pirma, kuris mazgas norėtų jūsų instinktai būti išlaikyti žymiklį? 

PUBLIKA: pirmasis mazgas. 

David J. Malan: Taip, tikriausiai tik pirmą kartą. Ir atkreipkite dėmesį, pirmiausia mazgas yra skirtingos formos. Tai tik pusė iš struct dydis, nes tai iš tiesų tik žymeklis. Taigi, ką jūs iš tiesų gali padaryti, tai paskelbti susijęs sąrašas, kad būtų tipo mazgas *. Ir tegul tiesiog vadina jį pirmą kartą inicijuoti ir ją null. Taigi null, vėlgi, yra dar į nuotrauką čia. Ne tik null naudojamas kaip kaip speciali Grąžina reikšmę dalykų, pavyzdžiui, getstring ir malloc, niekinis, taip pat nulis žymeklis, iš rodyklės stoka, jei bus. Tai tiesiog reiškia, nieko dar čia. Dabar pirmą kartą, aš galėtų jau pavadino tai nieko. Galėjau jį pavadino "sąrašas" arba bet kitų dalykų skaičius. Bet aš pavadino jį "pirmas", kad IT linijos su šiame paveikslėlyje. Taigi kaip eilutę gali būti atstovaujama su savo pirmojo baito adresas, todėl gali susieti sąrašas. Ir mes pamatyti kitus duomenis struktūros atstovauja tik su vienu rodykle, 32 bitų rodyklė, nukreipta tuo pat pirmojo mazgo struktūrą. 

Bet dabar tegul numatyti problemų. Jei aš tik prisiminti mano programos adreso pirmojo mazgo, pirmasis Stačiakampis šios duomenų struktūros, kas turėjo būti geriau apie bylą įgyvendinimas mano sąrašo poilsio? Kas yra raktas detalė, kuri vyksta Siekiant užtikrinti tai tikrai veikia? Ir "iš tiesų veikia" Aš reiškia, panašiai kaip eilutę, leidžia mums pereiti nuo pirmojo pobūdžio į Davin vardo į antrąjį, į trečia, ketvirta, iki galo, kaip mes žinome, kai mes pabaigoje Susietos sąrašą, kuris atrodo taip? Kai jis tuščias. Ir aš atstovavo šį kaip rūšiuoti kaip elektromechanikas jėgomis, su mažai įžeminimo simbolis, dvasia. Bet tai tik reiškia, kad niekinis ir šiuo atveju. Galite piešti tai bet koks skaičius būdų, bet šis autorius čia nutiko naudoti šį simbolį. 

Kol mes apjuostame visų šių mazgų kartu, tik prisiminti, kur Pirmasis yra, kol kaip mes įdėti specialų simbolį labai paskutinis mazgas sąraše, ir mes naudosime null, nes tai ką mes turime mums prieinama, šis sąrašas yra išsamus. Ir net jei tik aš jums žymeklį į Pirmasis elementas, jūs, programuotojas, tikrai gali prieiti prie jo pailsėti. Bet leiskim savo protus Brody truputį, jei jie nėra jau gana wandered-- kas bus rodomi laikas rasti nieko šiame sąraše? Velnias ji, tai didelis O n, kuris nėra blogai, tiesą sakant. Bet tai yra linijinė. Prašėme tai, ką funkcija iš matricos juda daugiau link šio dinamiškai paveikslėlyje austi kartu ar susiję mazgai? Mes atsisakė laisvą prieigą. Masyvas yra gražus, nes matematiškai viskas atgal atgal atgal į nugarą. Nors šioje nuotraukoje atrodo gana ir net nors atrodo, kad šiais mazgais gražiai išdėstyti vienas nuo kito, iš tikrųjų jie gali būti bet kur. OX1, Ox50, Ox123, Ox99, tai mazgai gali būti bet kur. Kadangi malloc daro paskirstyti atmintį iš krūvos, tačiau bet kurioje krūvą. Jūs nebūtinai žino, kad tai bus grįžti atgal į nugarą. Ir taip šis vaizdas į tikrovės nesiruošia būti gana tai gana. 

Taigi ji ketina imtis šiek tiek dirbti siekiant įgyvendinti šią funkciją. Taigi leiskite įgyvendinti paiešką dabar. Ir mes pamatysime rūšies protingas būdas tai padaryti. Taigi, jei aš esu paieškos funkcija ir Aš davė kintančiais sveikasis skaičius n ieškoti, reikia žinoti nauja sintaksė ieškote viduje statinio ŠTAI nurodė, kad, norint rasti n. Taigi leiskite tai padaryti. 

Taigi, pirmiausia aš ruošiuosi eiti į priekį ir paskelbti mazgas *. Ir aš ruošiuosi jį vadiname žymeklis, tik pagal susitarimą. Ir aš ruošiuosi inicijuoti ją pirmą kartą. Ir dabar aš galiu tai padaryti į įvairiais būdais. Bet aš ruošiuosi laikytis vienodo požiūrio. Nors žymeklis nėra lygūs null, ir tai galioja sintaksė. Ir tai tiesiog reiškia, atlikite šiuos veiksmus, kad Tol, kol jūs nesate nukreipta į nieką. Ką norite daryti? 

Jei žymeklis taškas n, leiskite man grįžti į tą, equals-- lygi, ką? Kokią vertę aš ko ieškote? Tikrasis n, kuris buvo priimtas. Taigi čia yra kita funkcija C ir daug kalbų. Nors struktūros vadinamas mazgu turi vertę n, visiškai teisėtas taip pat turėti vietos argumentą arba kintamas vadinamas n. Nes net mes, su žmogaus akis gali atskirti kad tai n yra turbūt skiriasi nuo šio n. Kadangi sintaksė skiriasi. Jūs turite dot ir rodyklę, kadangi šis vieną neturi tokio dalyko. Taigi, tai yra gerai. Tai gerai, kad juos vadina tuos pačius dalykus. 

Jei aš jums rasti tai, aš tikiu, ketinate nori kažką daryti kaip pranešti, kad mes nustatėme, n. Ir mes palikti, kad komentarą arba Pseudocode kodas. Kita, ir čia įdomiausia dalis, tai, ką aš noriu daryti, jei dabartinės mazgo yra turintis ne n, kad man rūpi? Kaip man pasiekti šių sričių? Jei mano pirštas ne momentas yra PTR, ir tai nukreipta į ką Pirmasis yra nukreipta ne, kaip man perkelti mano pirštą į kitą mazgas kodą? Na, kas tinklalapio mes ketina vadovautis šioje byloje? PUBLIKA: [nesigirdi]. David J. Malan: Taip, todėl kitą. Taigi, jei aš einu atgal į savo kodas čia, tiesą sakant, aš ketina eiti į priekį ir pasakyti žymeklį, kuris yra tik laikinas variable-- tai Keistas vardas, PTR, bet tai tiesiog kaip temp-- Aš ruošiuosi nustatyti žymeklį lygios kokios rodyklės is-- ir vėl, tai bus tiek Buggy už moment-- tašku kitą. Kitaip tariant, aš ruošiuosi pasiimti savo pirštu, kad manimi nukreipta į šio mazgo čia, ir aš ruošiuosi pasakyti, žinote, ką, pažvelgti į kitą lauką išvaizdą ir judinkite pirštą kokia ji nukreipta ne. Ir tai vyksta kartoju, kartoju, pakartokite. Bet kai daro savo pirštą nustoti daryti ką nors ne visi? Kaip tik tai, ką linija kodų smūgių į? PUBLIKA: [nesigirdi] David J. Malan: Jei taškas, o žymeklis nėra lygus nuliui. Tam tikru momentu mano piršto bus nukreipta į null ir aš ruošiuosi suvokti tai šio sąrašo pabaigoje. Dabar, tai yra šiek tiek baltas melas paprastumo. Pasirodo, kad nors mes ką tik sužinojau šį dot žymėjimą struktūroms, žymeklis nėra konstrukto. PTR yra kas? Tiesiog daugiau nitpicky. Tai rodyklė mazgas. Tai nėra pats mazgas. Jeigu aš neturėjo žvaigždę čia, žymeklis absolutely-- tai mazgas. Tai kaip savaitę vienu deklaracija kintamojo, nors žodis "mazgas" yra nauja. 

Bet kaip tik mes pristatome žvaigždė, tai dabar žymiklį į mazgą. Ir, deja, jūs negalite naudoti dot notacijos už rodykle. Jūs turite naudoti rodyklę žymėjimas, kuris, stulbinamai, yra pirmas kartas, bet gabalas sintaksė atrodo intuityvus. Tai tiesiog atrodo kaip strėlė. Ir taip, kad tai geras dalykas. Ir žemyn čia pažodžiui atrodo kaip strėlė. Taigi, aš manau, kad tai la-- aš ne manau, kad aš per įsipareigojant here-- aš manau, kad tai paskutinis naujasis kūrinys Sintaksės mes ketiname pamatyti. Ir laimei, tai iš tiesų šiek tiek daugiau intuityvus. 

Dabar, tiems iš jūsų, kurie norėti senas būdas, Jūs vis dar galite naudoti taškinę notacijos. Bet kaip už pirmadienį pokalbis, mes pirmiausia reikia eiti ten, eikite į, kad spręsti, o tada prisijungti prie lauką. Taigi tai taip pat teisinga. Ir tiesą sakant, tai yra šiek tiek daugiau pedantiškas. Jūs tiesiog sakydamas, dereference žymeklis ir ten. Tada patraukti .n, laukas vadinamas n. Bet tiesą sakant, niekas nenori tipo ar skaityti. Ir taip pasaulis išrado rodyklė žymėjimas, kuris yra lygiavertis, vienodi, tai tik sintaksinė cukrus. Taigi išgalvotas būdas pasakyti tai atrodo geriau, arba atrodo paprastesnis. 

Taigi, dabar aš ruošiuosi daryti vieną kitą dalyką. Aš ruošiuosi pasakyti "pertrauką", kai aš radau, kad aš ne nuolat ieško už jį. Bet tai esmė iš paieškos funkcija. Bet tai daug lengviau, ir pabaigos, o ne vaikščioti per kodą. Tai iš tiesų oficialus įgyvendinimas Paieškos šiandienos platinimo kodas. Drįstu pasakyti, kad įterpti nėra ypač smagu pasivaikščioti vizualiai, nei trinti, net nors ne dienos pabaigoje jie skliautais į gana paprasti euristika. 

Taigi leiskite tai padaryti. Jei jūs humoras man čia, aš pareikšti streso kamuoliukus krūva. Aš išvedžiau numerių krūva. Ir mes galėtume gauti tik keletą savanorių atstovauti 9, 17, 20, 22, 29 ir 34? Taigi, iš esmės visi kas čia šiandien. Tai buvo vienas, du, trys, keturių, penkių, šešių žmonių. Ir aš buvo paprašyta go-- pamatyti, ne vienas gale kelia savo rankas. Gerai, vienas, du, trys, keturi five-- leiskite įkelti balance-- šešis. Gerai, jūs šešių ateiti iki. Mums reikia kitų žmonių. Mes atnešė papildomų streso kamuolius. Ir jei galėtų, tiesiog akimirka, linija patys sukuria tik kaip pavaizduota šiame paveikslėlyje čia. 

Viskas gerai. Pažiūrėkime, koks tavo vardas? 

PUBLIKA: Andrew. 

David J. Malan: Andriejus, Jūs esate numeris 9. Nice to meet you. Čia jūs einate. PUBLIKA: Jen. David J. Malan: Jen. Davidas. Number 17. Taip? 

PUBLIKA: Aš Julija. 

David J. Malan: Julija, David. Numeris 20. PUBLIKA: krikščionis. David J. Malan: Christian David. Numeris 22. Ir? 

PUBLIKA: JP. David J. Malan: JP. Numeris 29. Taigi pirmyn ir gauti in-- Uh oh. Uh oh. Budėjimo. 20. Ar kas nors turite žymeklį? PUBLIKA: Aš turiu Sharpie. David J. Malan: Tu turi Sharpie? Gerai. Ir ar kas nors turi popierėlį? Išsaugoti paskaitą. Nagi. PUBLIKA: Mes gavo jį. David J. Malan: Mes jį gavo? Gerai, ačiū. Here we go. Ar tai buvo pas jus? Jūs tiesiog išgelbėjo dieną. Taigi 29. Viskas gerai. Aš klaidomis 29, bet gerai. Eiti į priekį. Gerai, aš duosiu jums švirkštimo atgal trumpam. Taigi, mes turime šie žmonės čia. Leiskite turėti vieną kitą. Gabe, tu nori žaisti Pirmasis elementas čia? Mes turime jums atkreipti Šiuose smulkių žmonės. Taigi 9, 17, 20, 22, tarsi 29, ir tada 34. Ar mes prarasti ką nors? Aš turiu 34. Kur did-- Gerai, kas nori būti 34? Gerai, nagi iki 34. Gerai, tai bus verta kulminacija. Koks tavo vardas? 

PUBLIKA: Petras. 

David J. Malan: Petras, nagi iki. Gerai, kad čia visa krūva mazgų. Kiekvienas iš jūsų vaikinai yra vienas iš šių stačiakampių. Ir Gabe, šiek tiek keista, žmogus iš, atstovauja pirmasis. Taigi jo žymeklis tiek mažesnis ant nei visi kiti ekrane. Ir šiuo atveju kiekviena kaire rankos ketina arba atkreipti žemyn, taip atstovaujanti nuliui, todėl tik iš rodyklės nebuvimas, ar ji bus nukreipta ne mazgas šalia jūsų. 

Taigi dabar, jei jūs puošia patys, kaip paveikslėlyje čia, eikite į priekį ir taškas vienas į kitą, su Gabe ypač nukreipta į numeris 9 atstovauti sąrašą. Gerai, numeris 34, jūsų kairė ranka tiesiog reikia būti nukreipta į grindis. 

Gerai, kad tai yra susiję sąrašas. Taigi tai yra tas scenarijus. Ir iš tiesų, tai yra atstovas iš problemų klasei kad jūs galite pabandyti išspręsti su kodu. Jūs norite, kad galiausiai įterpti naujas elementas į sąrašą. Tokiu atveju, mes ketiname pabandykite įdėti skaičių 55. Bet ten bus skirtingus atvejus apsvarstyti. Ir iš tiesų, tai bus vienas iš didelis-picture takeaways čia yra, kas yra skirtingų atvejų. Kas yra, jei sąlygomis arba skirtingi filialai, kad jūsų programa gali turėti? 

Na, numeris, kurį bandote įterpti, kurį mes dabar žinome, kad 55, bet jei jūs nežinote, iš anksto, aš Manyti patenka į mažiausiai trijų galimi atvejai. Jeigu naujasis elementas gali būti? PUBLIKA: Ir pabaigoje ar viduryje. David J. Malan: Tuo tikslu, viduryje ar pradžioje. Taigi galiu reikalauti ten bent trys problemos turime spręsti. Leiskite pasirinkti tai, kas galbūt be abejo, paprasčiausias vienas, kur naująjį elementą priklauso pradžioje. Taigi, aš ruošiuosi kodą gana kaip ieškoti, kurį aš ką tik parašė. Ir aš ruošiuosi PTR, kuris Aš atstovauti čia su mano pirštu, kaip įprasta. 

Ir atminkite, kas vertė Ar mes inicijuoti PTR prie? Taigi, mes inicializuoti jį null pradžių. Bet tada ką gi mes darome, kai mes buvo viduje mūsų paieškos funkcija? Mes nustatėme, kad lygi pirma, tačiau tai nereiškia, tai daryti. Jei aš nustatyti PTR lygią, pirma, ką turėtų mano ranka tikrai nukreipta į? Teisė. Taigi, jei Gabe ir aš ketinate būti lygios vertės čia turime tiek taško numeris 9. 

Taigi, tai buvo mūsų istorijos pradžia. O dabar tai tik paprasta, nors sintaksė yra nauja. Konceptualiai tai tik linijinis paieška. Ar 55 lygi 9? Arba, o, tarkime, mažiau nei 9. Nes aš bandau išsiaiškinti, kur dėti 55. Mažiau nei 9, yra mažesnis kaip 17, mažiau kaip 20 ir mažiau kaip 22 ir mažiau kaip 29, mažesnis kaip 34, Nr. Taigi dabar mes atveju viena iš mažiausiai trijų. 

Jei aš noriu įterpti 55 per čia, ką kodo eilutes reikia gauti įvykdytas? Kaip veikia šį paveikslėlį žmonės turi keisti? Ką man daryti su savo kaire ranka? Tai turėtų būti niekinis pradžių, nes aš ne sąrašo pabaigoje. Ir kas turėtų atsitikti, čia su Petru, tai buvo? Jis akivaizdžiai ketina atkreipti dėmesį į mane. Taigi galiu reikalauti ten bent dvi eilutės kodo mėginio kodą iš šiandien kad ketina įgyvendinti šį scenarijus pridedant 55 ne uodega. Ir aš galėčiau ką nors hop aukštyn ir tik atstovauti 55? Gerai, jūs esate nauja 55. 

Taigi dabar ką daryti, jei šalia scenarijus ateina kartu, ir mes norime įterpti ne pradedant arba šio sąrašo galva? Ir koks tavo vardas, numeris 55? 

PUBLIKA: Džekas. 

David J. Malan: Jack? Gerai, nice to meet you. Sveiki atvykę į laivą. Taigi dabar mes ketiname įdėti, tarkim, skaičius 5. Štai antras atvejis trijų mes atėjo su anksčiau. Taigi, jei 5 priklauso pradžioje, pažiūrėkime, kaip mes matome, kad iš. Aš inicijuoti savo PTR rodyklė numeris 9 kartą. Ir aš supratau, oi, 5 yra mažesnis kaip 9. Taigi nustatyti šią nuotrauką mums. Kieno rankos, Gabe s ar Dovydo or-- kas numeris 9 vardas? 

PUBLIKA: Jen. 

David J. Malan: Jen hands-- kuris iš mūsų rankų reikia pakeisti? Gerai, kad Gabe nurodo ne tai, ką dabar? Tuo mane. Esu naujas mazgas. Taigi aš tiesiog rūšies perkelti Čia matyti vizualiai. Ir tuo tarpu ką man atkreipti, kad? Vis kur aš nukreipta. Taigi, kad viskas. Taigi tiesiog tikrai viena eilutė kodo pataisymai šis konkretus klausimas, atrodo. Gerai, kad tai gerai. Ir gali kas nors būti dėl 5 vietos rezervavimo ženklas? Nagi iki. Mes jums kitą kartą. 

Gerai, kad now-- ir kaip panaikinti, pavadinimų Aš ne padaryti aiškų paminėti teisės dabar pred žymeklis, žymeklis pirmtakas ir naujos žymeklis, tai tik pavadinimai suteikta mėginio kodą į rodyklės arba mano rankos, kad manimi rūšies nukreipta aplink. Koks tavo vardas? 

PUBLIKA: Christine. 

David J. Malan Christine. Sveiki atvykę į laivą. Visos teisės, todėl aptarkime dabar šiek tiek labiau erzina scenarijus, , kuriuo noriu įterpti kažkas panašaus į 26 į tai. 20? Ką? Tai are-- geras dalykas, mes turime šį rašiklį. Visos teisės 20. Jei kas nors galėtų gauti kitą gabalas popieriaus pasiruošę, tik case-- viskas gerai. O, įdomu. Na tai pavyzdys iš paskaitų klaidą. Gerai, kad tai, kas tavo vardas? PUBLIKA: Julija. David J. Malan: Julija, jūs galite pop iš ir apsimesti, jūs niekada nebuvo ten? Gerai, tai niekada neįvyko. Ačiū. Taigi tarkime, kad mes norime įterpti Julija į šią susietą sąrašą. Ji yra skaičius 20. Ir, žinoma, ji ketina priklausyti ne begin-- nenukreipkite į ką nors dar. Taigi jūsų ranka gali rūšies būti žemyn null arba kai šiukšlių vertė. Leiskite papasakoti greitai istoriją. Aš nukreipta į 5 numeriu šį kartą. Tada aš patikrinti 9. Tada aš patikrinti 17. Tada aš patikrinti 22. Ir aš suprantu,, ooh, Julia turi eiti prieš 22. Taigi, kas turi įvykti? Kieno rankos reikia pakeisti? Julija, mano, or-- koks tavo vardas dar kartą? 

PUBLIKA: krikščionis. 

David J. Malan: Christian arba? 

PUBLIKA: Andy. 

David J. Malan Andy. Krikščionių ar Andy? Andy reikia atkreipti dėmesį į? Julija. Viskas gerai. Taigi Andy norite atkreipti dėmesį į Julia? Bet palauk. Į istoriją iki šiol, Aš vienokį atsakingas, ta prasme, kad žymeklis yra dalykas, kad juda per sąrašą. Mes gali turėti Andy vardą, bet ten ne kintamasis vadinamas Andy. Vienintelis kitas kintamasis mes turime, yra pirma, kas atstovauja Gabe. 

Taigi iš tikrųjų tai yra, kodėl taip šiol mes nereikia tai. Bet dabar ekrane yra paminėti vėl pred rodyklė. Taigi leiskite man būti aiškesnis. Jei tai yra žymeklis, turėjau geriau gauti šiek tiek daugiau protingas apie mano iteracijos. Jei jūs neprieštaraujate, mano išgyvena čia vėl, nurodydama čia, rodydamas čia. Bet leiskite man turėti pred žymeklį, pirmtakas žymeklis, tai rūšies nukreipta į elementas buvau tiesiog ne. Taigi, kai aš einu čia, dabar mano kairė ranka atnaujinimai. Kai aš einu čia mano kairė ranka atnaujinimus. Ir dabar turiu ne tik žymiklį į elementas, kuris eina po Julija Aš vis dar turiu žymiklį į Andy, elementas anksčiau. Taigi, jūs turite prieigą, iš esmės, džiūvėsėliai, jei norite, visiems būtinų patarimų. 

Taigi, jei aš nukreipta į Andy ir aš taip pat nukreipta ne krikščionis, kurio rankos dabar reikėtų pažymėti kitur? Taigi Andy dabar gali nurodyti ne Julija. Julija, dabar gali būti nukreiptas krikščionis. Nes ji gali nukopijuoti mano dešinė yra žymeklis. Ir, kad būtų veiksmingai suteikia jums atgal į šitą vietą čia. Taigi trumpai tariant, nors tai veda mus rūšies amžinai faktiškai atnaujinti susiję sąrašą, reikia suprasti, kad operacijos yra gana paprasta. Tai vienas, du, trys eilučių kodo galiausiai. Bet apvyniotas aplink tie eilučių kodo greičiausiai tai yra logikos tiek, kad būtų veiksmingai klausia, kur mes esame? Ar mes iš pradžių, viduryje arba pabaigoje? 

Dabar yra žinoma, kai kurie kiti operacijos, mes galime įgyvendinti. Ir šios nuotraukos čia tik vaizduoja ką tik padarė su žmonėmis. Ką apie pašalinimo? Jei aš noriu, pavyzdžiui, pašalinti numerį 34 arba 55, Aš gali turėti tos pačios rūšies kodas, bet aš ruošiuosi reikia vieną ar du žingsnius. Nes tai, kas naujo? Jei aš pašalinti ką nors pabaigoje, kaip skaičius 55 ir tada 34, kas taip pat turi keistis, nes aš tai darau? Turiu ne evict-- koks tavo vardas dar kartą? 

PUBLIKA: Džekas. 

David J. Malan: Džekas. Turiu ne tik evict-- nemokamai Jack taip tiesiog skambinti nemokamai Jack, arba bent jau ten žymeklis taip pat, bet dabar ką reikia keisti su Petru? Jo ranka geriau pradėti nukreipta žemyn. Nes kaip tik aš skambinti nemokamai Džekas, jei Petro dar nukreipta į Jack ir aš, todėl išlaikyti važiuojantiems sąrašas ir galimybė tai žymeklis, kad, kai mūsų senas draugas segmentavimas kaltės iš tiesų gali mesti į. Kadangi mes jau davė atminties atgal į Jack. 

Galite likti čia nerangiai tik už akimirką. Kadangi mes turime tik pora baigiamosios operacijos apsvarstyti. Pašalinus sąraše galvą, arba beginning-- ir tai vienas s šiek tiek erzina. Kadangi mes turime žinoti, kad Gabe rūšies specialius šios programos. Nes iš tiesų, jis turi savo žymeklį. Jis ne tik yra nurodė, kaip beveik visi kiti čia. 

Taigi, kai sąrašo galva pašalinti, kurios rankos reikia keisti dabar? Koks tavo vardas dar kartą? 

PUBLIKA: Christine. 

David J. Malan: Aš baisu ne pavadinimus, matyt. Taigi Christine ir Gabe, kieno rankas reikia pakeisti kai mes bandome pašalinti Christine, skaičius 5, nuo paveikslėlyje? Gerai, kad galime padaryti Gabe. Gabe vyksta į tašką, matyt, numeriu 9. Bet ką kitą turėtų atsitikti? PUBLIKA: Christine turėtų yra niekinis [nesigirdi]. David J. Malan: Gerai, mes tikriausiai turėtų make-- išgirdau "nulis" kažkur. PUBLIKA: Null ir be jos. David J. Malan: NULL ką? PUBLIKA: Null ir be jos. David J. Malan: Null ir be jos. Taigi, tai yra labai lengva. Ir tai puikus, kad jūs dabar tarsi Nuolatinių ten, nepriklausančios. Kadangi jūs buvote atsietas nuo sąrašo. Jūs efektyviai buvo našlaičiai iš sąrašo. Ir todėl mes turėjome geriau skambinti nemokamai dabar Christine duoti tą atmintį atgal. Priešingu atveju, kiekvieną kartą mes trinti mazgas iš sąrašo mes galime būti padaryti sąrašą trumpesnis, bet ne iš tikrųjų mažėja atminties dydis. Ir taip, jei mes nuolat pridedant ir pridurdamas, kad pridedant dalykų sąrašą, mano kompiuteris gali gauti lėčiau ir lėčiau ir lėčiau, nes aš senka atminties, net jei aš ne iš tikrųjų naudojant Christine baitų atminties nebėra. 

Taigi, galų gale, yra ir kitų scenarijai, kurių course-- šalinimas viduryje, šalinimas pabaigoje, kaip mes matėme. Bet įdomiau Dabar iškilęs uždavinys yra bus apsvarstyti tiksliai ką veikia laikas yra. Taigi ne tik jūs galite išsaugoti savo popieriaus lapų, jei Gabe, jūs neprieštaraujate suteikiant kiekvienas stresas kamuoliukas. Labai ačiū mūsų susietą sąrašą Savanorių čia, jei galėtų. 

[Plojimai] 

David J. Malan: Gerai. Taigi iš analitinė pora klausimai Tada, jei galėčiau. Mes matėme šį žymėjimą anksčiau, didelis O ir omega, viršutinių ribų ir apatinė ribos dėl važiavimo laikas kai kurių algoritmas. Taigi aptarkime tik klausimų pora. 

Vienas iš jų, ir mes jį sakė prieš, o kas veikia laikas ieškoti sąrašas pagal stambiojo O? Kas viršutinė riba nuo važiavimo laikas ieškoti susietą sąrašą kaip įgyvendinamos mūsų savanoriai čia? Tai didelis O n, linijinė. Nes blogiausiu atveju, elementas, kaip ir 55, mes galime būti ieškote gali būti ten, kur Džekas buvo visa pabaigoje būdas. Ir, deja, skirtingai nuo masyvo mes negalime gauti išgalvotas šį kartą. Nors visi mūsų žmonėms buvo rūšiuoti nuo mažų elementų, 5, visą kelią iki didesnio elemento, 55, tai paprastai yra geras dalykas. Bet ką daro šią prielaidą nebėra leidžia mums daryti? PUBLIKA: [nesigirdi] David J. Malan: Pasakykite naujo? PUBLIKA: Laisvosios kreipties. David J. Malan: Laisvosios kreipties. Ir, savo ruožtu tai reiškia, kad mes galime ne ilgiau naudoti silpną nuliai, intuicija, ir akivaizdumas naudojant dvejetainę ieškoti ir padalinti ir užkariauti. Nes nors mes žmonės gali akivaizdžiai matyti, kad Andy ir krikščionių buvo maždaug viduryje sąrašo mes tik žinome, kad kompiuteris nugriebus sąrašą nuo pat pradžių. Taigi mes atsisakė tą laisvą prieigą. 

Taigi didelis O n metu yra viršutinis laikytis mūsų paieškos laiką. Ką apie omega mūsų paieškos? Kas apatinė ant paieškos dėl tam tikrų į šį sąrašą skaičius? PUBLIKA: [nesigirdi] David J. Malan: Pasakykite naujo? PUBLIKA: Vienas. David J. Malan: Vienas. Taigi pastovus laikas. Geriausiu atveju, Christine tikrai ne sąrašo pradžioje. Ir mes ieškome skaičius 5, todėl mes radome ją. Taigi ne big deal. Bet ji turiu būti ne pradžioje šioje byloje, sąrašą. Ką apie kažką panašaus Delete? Ką daryti, jei norite ištrinti elementą? Kas viršutinė ir apatinė ant išbraukiant kažką iš susijęs sąrašą? PUBLIKA: [nesigirdi] David J. Malan: Pasakykite naujo? PUBLIKA: n. David J. Malan: n Iš tiesų viršutinė riba. Nes blogiausiu atveju, mes stengiamės ištrinti Jack, kaip mes ką tik padarė. Jis visa pabaigoje būdas. Priima su mumis amžinai, arba n žingsnių jį surasti. Štai viršutinė riba. Štai linijinė, tikrai. Ir geriausias atvejis bėgančio laiko, arba žemesnės ribos geriausiu atveju būtų pastovus laikas. Nes gal mes stengiamės ištrinti Christine, ir mes tiesiog gauti pasisekė ji pradžioje. Dabar palauk. Gabe taip pat buvo pradžioje, ir mes taip pat turėjo atnaujinti Gabe. Taigi, tai buvo ne tik vienas žingsnis. Taigi tai iš tiesų nuolat laikas, geriausiu atveju, pašalinti mažiausias elementas? Tai, nors tai gali būti du, trys, ar net 100 eilučių kodo, jei jis pats skaičius linijos, o ne kai kilpa, ir nepriklauso nuo dydžio sąrašo, absoliučiai. Trynimas esant elementą Sąrašo pradžioje, net jei mes turime elgtis su Gabe vis dar pastovus laikas. 

Taigi tai atrodo masinis žingsnis atgal. Ir ką laiko švaistymas , jeigu per savaitę vieną ir savaitę nulis mes turėjome ne tik Pseudocode kodas, tačiau tikrasis kodas įgyvendinti kažką, kad žurnalas bazė n arba prisijunkite, o, n, pagrindas 2, atsižvelgiant į jos veikimo laiką. Taigi, kodėl gi būtų mes norime pradėti naudojant kažką panašaus į susietą sąrašą? Taip. 

PUBLIKA: Taigi jūs galite pridėti elementai masyvo. David J. Malan: Taigi jūs galite pridėti elementus į masyvą. Ir tai taip pat yra teminis. Ir mes toliau matyti tai šis kompromisas, daug kaip mes matėme kompromisą su merge rūšiuoti. Mes tikrai gali paspartinti ieškoti arba rūšiavimą, o, jei mes praleisti šiek tiek daugiau vietos ir turėti papildomą riekė atminties arba už merge rūšiuoti masyvo. Bet mes praleidžiame daugiau erdvė, bet mes sutaupyti laiko. Tokiu atveju, mes mesti laiką, bet mes įgyti lankstumo, dinamiškumas, jei bus, kuris yra neabejotinai teigiamas bruožas. 

Mes taip pat išleidžia erdvę. Kokia prasme yra susijęs sąrašą brangesnis erdvės požiūriu nei masyvo? Kur yra papildomos vietos tiekiamos iš? Taip? 

PUBLIKA: [nesigirdi] žymeklis. 

David J. Malan: Taip, mes taip pat turi rodyklę. Taigi tai yra minorly erzina tuo, kad nebėra esu Aš saugoti tik int atstovauti int. Aš saugoti int ir A žymeklis, kuris taip pat yra 32 bitai. Taigi, aš tiesiog dvigubai Tarpas dalyvauja. Štai kompromisą, tačiau tai į int atveju. Tarkime, kad jūs ne saugoti int, bet manau, kad kiekvienas iš šių stačiakampių ar kiekvienas iš šių žmonių buvo atstovaujanti žodis, anglų kalbos žodis, kad gali būti penkių simbolių, 10 simbolių, o gal net daugiau. Tada pridedant tik 32 bitai daugiau gali būti mažiau baisi. 

Ką daryti, jei kiekvienas iš mokinių į demonstraciją buvo pažodžiui studentų structs kad turi vardus ir namus, o gal ir telefono numerius ir "Twitter" rankenos ir pan. Taigi visus laukus mes pradėjome kalbame apie kitą dieną, daug mažiau baisi kaip mūsų mazgai gauti įdomiau ir didelis praleisti, eh, papildomas žymeklis tiesiog susieti juos kartu. Bet iš tikrųjų, tai kompromisas. Ir iš tiesų, kodas yra sudėtingesnė, nes jūs matyti nugriebus per kad visų pirma pavyzdys. Bet kas, jei ten buvo kai Gralis čia. Ką daryti, jei mes neturime žengti žingsnį atgal bet masinis žingsnis į priekį ir įgyvendinti duomenų struktūra, per kurią mes rasite elementų, tokių kaip Jack arba Christine arba visi kiti elementai, šiame masyve tiesa nuolat laiku? Paieška yra pastovus. Ištrinti yra pastovus. Įdėkite yra pastovus. Visi šių operacijų yra pastovus. Tai būtų mūsų Gralis. Ir tai yra, kai mes pasiimti kitą kartą. Pasimatysime vėliau.