[Powered by Google Translate] [Nädal 6] [David J. Malan] [Harvardi Ülikool] [See on CS50.] [CS50.TV] 

See on CS50, ja see on alguse 6. nädalal nii paar uut vahendid on nüüd olemas, kus saab ära kasutada, millest esimene on nn CS50 Stiil. Koefitsiendid on, kui sa oled nagu mina või mõni õpetamise stipendiaatide olete ilmselt näinud programmi, kelle stiil paistab pisut midagi sellist. Ehk hakkate lõikamine mõned nurgad hilja õhtul, või saad sellega tegeleda hiljem ja siis TF või CA tuleb üle tööajal. Siis on meil raske lugeda. Noh, see kood on süntaktiliselt õige, ja see kompileerib, ja see reaalselt sõita. Aga see on kindlasti mitte 5 stiil. 

Aga nüüd, kui me astume sellesse kataloogi- ja märkate, et mul on conditions2.c- ja ma saan selle uue käsu, style50, seda faili conditions2.c, Enter, märgata, et see on mind informeerinud, et ta on olnud stiliseeritud. Gedit märganud, et fail on muutunud kettal, ja kui ma nuppu reload, kõik teie probleemid on nüüd automatiseeritud. [Aplaus] See on üks asju, mida me tegime sel nädalavahetusel. Aru, et see on puudulik, sest seal on mingi kood et see lihtsalt ei saa Tyylitellä ideaalselt, aga aru, et see on nüüd vahend, mida saab ära kasutada kui ainult koristama mõned rohkem errantly paigutatud looksulg jms. 

Aga selgem nüüd on CS50 Kontrolli. Mis CS50 Kontrolli, saab tegelikult teha samu õigsuse testid ise koodi, et õpetamise stipendiaatide suudavad. See on käsurea utiliit, mis tuleb nüüd seadme niipea kui sa update50 ühe pset 4 näitajad, ja te kasutate seda sisuliselt niimoodi. Sa käivitada käsk check50. Siis viiakse käsurea argument, või üldisemalt tuntud kui lüliti või lipp. Üldiselt asjad, mis on sidekriipsud nimetatakse lüliti et käsurea programm, nii-c täpsustatakse kontrollide kohta, mida soovite käivitada. 

Teste, mida soovite käivitada identifitseeritakse individuaalselt selle stringi, 2012/pset4/resize. Teisisõnu, see on lihtsalt suvaline, kuid unikaalne string et me kasutame üheselt identifitseerida pset 4 őigsuse testid. Ja siis täpsustada tühikutega eraldatud loetelu faili, mida soovite üles laadida kuni CS50 Kontrolli analüüsiks. Näiteks, kui ma minema minu lahendus siin resize.c- lubage mul avada suurem terminaliakent- ja ma edasi minna ja käivitada oletame check50-c 2012/pset4/resize, ja siis ma minna ja täpsustada failide nimed, resize.c ja siis Enter, see surub, see lisatud, siis kontrolli, ja ma lihtsalt ei suutnud terve hunnik teste. Üks punane top vasakule ütleb, et resize.c ja bmp olemas. See oli test. See oli küsimus palusime. Ja see on õnnetu, sest vastus oli vale. Valge tekst ütleb oodata bmp.h olemas, ja see on lihtsalt minu süü. Ma unustasin laadida selle, et mul on vaja üles laadida nii faile, resize.c ja bmp.h. Aga nüüd tähele kõik teised testid on kollane, sest nad ei jookse, ja nii naerusuu on vertikaalne, sest ta on kumbki õnnelik ega kurb, kuid me peame hüvitamise et küsimus punane enne nende muude kontrollide kestab. 

Las ma lahendan selle. Lubage mul välja suumida ja uuesti seda, seekord bmp.h ka kohta käsurealt, Enter, ja nüüd, kui kõik hästi läheb, see saab vaadata ja siis tagasi tänu-hoidke hinge- kõik roheline, mis tähendab, ma teen tõesti hästi pset 4 siiani. Võite näha ja järeldada kirjeldav tekst siia Just see on meil testitud. Me kõigepealt katsetada ei failid on olemas? Siis katsetatakse ei resize.c kompileerida? Siis me katsetatud see ei resize 1x1 piksli BMP kui n, resize tegur, 1. Nüüd, kui te ei tea, mida n on, siis kui sa sukelduda pset 4, kuid see lihtsalt on meelerahu veenduge, et te ei ole saneerimist pilt üldse, kui resize tegur on 1. Kui seevastu seda suurust muuta 1x1 piksli 1x1 pixel BMP 2x2 õigesti kui n on 2, siis samamoodi minu moodustab vastavalt. 

Lühidalt, see on mõeldud ühe, võtab ületamisel sõrmed välja võrrandi paremale enne kui saadate oma pset. Te teate täpselt, mida teie TF varsti teada kui lähete umbes esitades mõned neist probleemi komplekti, ja ka pedagoogiline motivatsioon on tõesti panna võimalus teie ees, nii et kui sa tead priori et seal on vigu koodi ja katsed, et ei jõua, võite panna tõhusam aega, kuni ees, et nende probleemide lahendamiseks mitte kaotada punkte, saada tagasisidet oma TF, ja siis minna, "Ahh," nagu ma oleks pidanud seda taipama. Nüüd vähemalt seal on vahend, mis aitab leida seda. Ta ei kavatse märkida, kus viga on, kuid ta ütleb sulle Mis on iseloomulik see. 

Nüüd mõistame testid ei ole tingimata ammendav. Lihtsalt, sest sa saad ekraan täis roheline smiley nägu ei tähenda, et teie kood on täiuslik, kuid see ei tähenda et ta on läbinud teatud analüüsid ettenähtud spec. Vahel me ei vabasta kontrolli. Näiteks Dekkari, üks aspekte pset 4, on selline pettumus, kui anname vastus küsimusele, mis see on, ja seal on mitmeid viise, kuidas paljastada kes inimene on, et punane müra. Spec alati täpsustada tulevikus pset 5 edasi mida kontrollib olemas sinu jaoks. Märkad seal on see valge link allosas. Sest nüüd, see on lihtsalt diagnostika väljund. Kui külastad et URL, saad terve hunnik hull, salasõnumeid et sa oled teretulnud vaatama läbi, aga see on enamasti töötajad nii et me saame diagnoosida ja siluda vigu check50 ise. 

Ilma jututa, liigume edasi, kus pooleli jäime. CS50 raamatukogu võtsime ette antud mõned nädalad, aga siis eelmisel nädalal alustasime rebides üks kiht seda. Alustasime jätma kõrvale string kasuks mida mitte? [Õpilased] Char. Char *, mis on char * kogu see aeg, aga nüüd me ei pea teesklema, et see on tegelik andmetüüp String. Pigem on see olnud sünonüümiks kehvasti char *, ja string on märgijada, miks see loogiline esindama stringe nagu char * s? Mis char * esindama kontekstis see mõiste string? Jah. >> [Student] esimene märk. Hea, esimene märk, kuid mitte päris esimene märk. See-[õpilased] Aadress. Hea, aadress esimene märk. Kõik see on vajalik, et esindada stringi arvuti mällu on lihtsalt aadressi oma väga esimene bait. Sa isegi ei pea teadma, kui kaua see on sest kuidas sa saad aru, et läbi dünaamiliselt? [Student] String pikkusega. Teil on võimalik helistada stringi pikkus, suurepärased, aga kuidas stringi pikkuse töö? Mida see teeb? Jah. [Student] Liigu edasi kuni jõuad null iseloomu. Jah, täpselt, see lihtsalt kordab koos loop, samas silmus, mis iganes alates * lõpuni, ja lõpuks on esindatud poolt \ 0, nn nul iseloomu, nul, ei tohi segi ajada null, mis on pointer, mis tulevad üles vestlus täna jälle. 

Me kooritud tagasi kiht GetInt ja siis võtsime pilk getString, ja meenutada, et need mõlemad ülesanded või tõesti, GetString, oli kasutades teatud funktsiooni tegelikult sõeluda, et on, lugeda ja analüüsida, kasutaja sisendit. Ja mis see oli uus funktsioon? Scanf või sscanf. See tegelikult jõuab mõne erineva maitsega. Seal on scanf, seal on sscanf, seal on fscanf. Praegu, kuigi, olgem keskenduda üks kõige kergemini illustreeritud ja las ma edasi minna ja avada ka seadme faili niimoodi, scanf1.c. See on super lihtne programm, kuid mis teeb midagi, et me pole kunagi teinud abita CS50 raamatukogu. See saab int alates kasutaja. Kuidas see toimib? Noh, rida 16 seal, märgata, et me kuulutame int nimetatakse x ja siinkohal lugu, Mis on x väärtus? [Kuuldamatu õpilase vastus] [David M.] Just, kes teab, mõned prügi väärtus potentsiaalselt nii 17, me lihtsalt öelda kasutaja anna mulle number, palun, ja 18. samm läheb asi huvitavaks. Scanf tundub laenata idee printf, et ta kasutab neid vormingu tähistamine jutumärkides. % D on muidugi kümnendmurruna. Aga miks ma möödaminnes & x asemel lihtsalt x? Esimene neist on õige. Jah. [Kuuldamatu õpilase vastus] Täpselt, kui eesmärk on see programm, nagu funktsioon GetInt ise, on saada int kasutaja ma ei liigu funktsioonid kõik muutujad ma tahan, aga kui ma ei liigu need tooted või aadressi või pointer, kõik sünonüümid tänapäeva eesmärkidel, siis see funktsioon puudub võime muuta sisu, et muutuja. See viiakse koopia nagu lollakas versioon swap et me rääkisime paar korda nüüd. 

Kuid selle asemel, tehes & x, ma sõna otseses mõttes möödaminnes mida? [Student] aadress. >> Aadress x. See on nagu joonistus kaardi funktsioon nimega scanf ja ütlen, need suunad patakas mälu arvuti et võid minna salvestada mõned täisarv sisse Et sscanf et nüüd seda teha mis operaator, mis tükk süntaks see saab olema kasutada kuigi me seda ei näe, sest keegi teine ​​kirjutas selle funktsioon? Teisisõnu - mis see on? [Student] X lugeda. Seal saab olema mõned lugemine, kuid ainult seoses x siin. Kui scanf on läbinud aadress x, süntaktiliselt, mida ettevõtja on kohustatud olemas kuskil sees scanf rakendamise, nii et scanf saab tegelikult kirjutada number 2 selle aadressi? Jah, nii *. Tuletame meelde, et * Meie dereference operaator, mis tähendab sisuliselt seda sinna minna. 

Kui olete antud ettevõttele aadress, nagu see siin, scanf on ilmselt-kui me tegelikult vaatasin ringi oma lähtekoodi- teeb * x või samaväärne tegelikult minna sellele aadressile ja panna mõned raha olemas. Nüüd on vaja teada kui scanf saab sisend klaviatuur, me laine oma käsi välja täna. Oletame, et operatsioonisüsteem võimaldab sscanf rääkida kasutaja klaviatuur, kuid siinkohal nüüd kooskõlas 19. kui me lihtsalt välja printida x näib, et antud juhul et scanf on pannud int X. See on täpselt, kuidas scanf töötab, ja meenutada möödunud nädalal see on täpselt, kuidas getString ja GetInt ja oma teiste pere funktsioonid lõpuks töötab, kuigi veidi dispersioon nagu sscanf, mis tähendab skaneerida stringi asemel klaviatuuri. Aga võtame pilk veidi vastuolus käesoleva. Aastal scanf2, ma tegelikult silmamunad. Mis on valesti ja ma varjata kommentaar, mis seletab nii palju- Mis on valesti selle programmi versioon 2? Ole nii tehnilise kui võimalik seekord. Tundub päris hea. See on kenasti liigendatud, kuid- Olgu, kuidas olgem ploomi see allapoole lühem küsimusi? Line 16. Mis on line 16 teed täpne, kuid tehniline inglise keelt? Kuidas veidi ebamugav. Jah, Michael. [Student] See osutab esimene täht string. 

Okei, lähedal. Las ma näpistama, et natuke. Osutades esimene täht string, siis kuulutame muutuja nimega puhver mis suunavad esimese aadress string, või pigem, mis suunavad täpsemalt char. Teade see ei ole tegelikult suunatud kuhugi, sest seal ei ole loovutamise operaator. Ei ole võrdusmärk, et kõik me teeme, on eraldades muutuja nimega puhver. See juhtub olema 32 bitti, sest see on pointer, ja sisu puhver ilmselt lõpuks sisaldab aadress char, kuid nüüd, mida see puhver sisaldab? Lihtsalt mõned võlts, kes teab, mõned prügi väärtus, sest me ei ole selgesõnaliselt käivitub see, et me ei tohiks endale midagi. Okei, nii et nüüd joon 17-mida see rida 17 teha? Võibolla see on soe see üles. Ta prindib string, eks? Ta prindib String palun. 

Rida 18 on kuidagi tuttav nüüd, et me just nägime vastuolus käesoleva kuid erineva vormi koodi, nii et liin 18, Me ütleme scanf siin on aadress patakas mälu. Ma tahan, et sa helisema string, nagu võiks eeldada% s, kuid probleem on selles, et me ei ole teinud paar asja siin. Mis on üks probleemidest? [Student] Ta püüab dereference nullviida. Hea, null või lihtsalt muidu teadmata suunanäitajaks. Sa teisaldus scanf aadress, kuid sa lihtsalt ütles hetk tagasi et see on aadress on mõned prügi väärtus, sest me tegelikult ei anna see midagi, ja nii sa räägid scanf tõhusalt minema panna stringi siin, kuid me ei tea, kus siin veel on, nii et me ei ole tegelikult eraldatud mälu puhver. Lisaks, mida sa ka ei ole isegi öelnud scanf? Oletame, et see oli patakas mälu, ja see ei olnud prügi väärtus, kuid sa ikka ei ütle scanf midagi olulist. [Student] Kui see tegelikult on, ampersand. Ampersand, nii sel juhul, see on okei. Sest puhver on juba deklareeritud pointer koos * tükk süntaks, meil ei ole vaja kasutada ampersand sest see on juba aadress, kuid ma arvan, et ma kuulsin seda siin. [Student] Kui suur see on? Hea, et me ei räägi scanf kui suur see puhver on, mis tähendab, isegi kui puhver oli pointer, me ütleme scanf, pane nöör siin, kuid siin võiks olla 2 baiti, see võiks olla 10 baiti, see võiks olla megabaidi. Scanf pole aimugi, ja kuna see on patakas mälu arvatavasti, see ei ole string veel. See on ainult stringi kui sa kirjutada märke ja \ 0 et patakas mälu. Nüüd on vaid mõned patakas mälu. Scanf ei tea, millal lõpetada kirjalikult, et aadress. 

Kui te mäletate mõned näited viimase, kus ma juhuslikult tipitud klaviatuuri üritab ülevoolu puhver, ja me rääkisime reedel umbes just nii. Kui vastane kuidagi süstib oma programmi palju suurem sõna või lause või fraas siis ootasid saab ületatud patakas mälu, mis võib olla halbu tagajärgi, nagu võttes kogu programm ise. Meil on vaja määrata see kuidagi. Lubage mul välja suumida ja lähevad versioon 3 on see programm. See on natuke parem. Selles versioonis, märka erinevust. Kooskõlas 16, ma olen jälle kuulutab muutuja nimega puhver, aga mis siis nüüd? See on array 16. tähemärki. See on hea, sest see tähendab ma saan nüüd öelda scanf siin on tegelik patakas mälu. Te saate peaaegu mõelda massiivid nagu oleks osuti nüüd, kuigi nad ei ole tegelikult samaväärne. Nad käituvad erinevalt erinevates kontekstides. Aga see on kindlasti nii, et puhver on viitamine 16 külgnevas tähemärki sest see on, mida massiiv on ja on nüüd mõne nädala jooksul. 

Siin ma räägin scanf siin on patakas mälu. Seekord see on tegelikult tüki mälu, kuid miks on see programm ikka kasutatavuse? Mis viga ikka? Ma olen öelnud mulle 16 baiti vaid- [Student] Mis siis kui nad kirjuta rohkem kui 16? Täpselt, mis siis, kui kasutaja liigid 17 tähemärki või 1700 tähemärki? Tegelikult vaatame, kui me ei saa komistada seda viga nüüd. On parem, kuid mitte täiuslik. Lubage mul minna ja joosta teha scanf3 koostada selle programmi. Ma jooksen scanf3, String palun: tere, ja me ilmselt kõik korras. Las ma proovin veidi pikem, Tere. Okei, teeme Tere, kuidas sul täna, Enter. Kuidas selline õnnelik siin, ütleme Tere kuidas läheb. Kurat. Okei, nii et meil vedas. Vaatame, kas me ei saa seda parandada. Ei, see ei lase mind kopeerida. Proovime seda uuesti. Olgu, valmis olla. Eks näis, kui kaua ma ei pretendeeri keskenduma samas teevad seda. Kurat. See on pigem sobiv, tegelikult. Nii juba läheb. Point tehtud. 

See, piinlik küll see ka on, see on ka üks allikatest suur segadus kirjutamise ajal programme, mis on vigu, sest nad avalduvad ainult üks kord samal ajal mõnikord. Reaalsus on see, et isegi kui teie kood on täiesti katki, see võib ainult täiesti katki kord samal ajal sest mõnikord sisuliselt mis juhtub on operatsioonisüsteem eraldab natuke rohkem mälu kui sa tegelikult vaja mingil põhjusel ja nii et keegi teine ​​kasutab mälu kohe pärast oma patakas 16 märki, nii et kui te lähete 17, 18, 19, mis iganes, see ei ole nii suur asi. Nüüd arvuti, isegi kui see ei ole viga selles punktis, võib lõpuks kasutada baidi number 17 või 18 või 19 midagi muud, mille ületamisel oma andmed, et sa paned sinna, kuigi liiga pikk, ei hakka kirjutatakse potentsiaalselt mõne muu funktsiooni. See ei ole tingimata positiivsed jääma puutumata, kuid see ei pruugi põhjustada SEG süü. Aga sel juhul, ma lõpuks ette piisavalt tähemärki et ma sisuliselt ületas minu segment mälu, ja bam, operatsioonisüsteemi ütles: "Vabandust, et pole hea, killustatust süü." 

Ja vaatame nüüd, kui see, mis jääb siin minu kataloog- märgata, et mul on see fail siin, tuum. Pange tähele, et see on taas kutsutud krahh tabab. See on sisuliselt fail, mis sisaldab sisu oma programmi mällu kohas, kus ta kukkus, ja lihtsalt proovida veidi näide lase mul minna siin ja joosta gdb kohta scanf3 ja seejärel määrata kolmas argument nimega tuum, ja teate siin, et kui lisan koodi, me suutma nagu tavaliselt koos gdb alustada jalgsi läbi selle programmi, ja ma saan käivitada see ja niipea, kui ma tabanud-nagu samm käsk gdb- niipea kui ma tabanud potentsiaalselt lollakas rida pärast kirjutama tohutu jada, Ma saaks tegelikult tuvastada siit. Veel selle, kuigi punktis poolest tuum puistab ja meeldib nii, et saate tegelikult tuhnima sees krahh tabab ja vaata mida line programm sind alt vedanud. Kõik küsimused siis suunanäitajaks ja aadressid? Sest täna me ei kavatse hakata võtma enesestmõistetavana, et need asjad on olemas ja me teame täpselt, mida nad on. Jah. 

[Student] Miks sa ei pea panna märk kõrval osa- Hea küsimus. Miks ma ei pea panna märk kõrval iseloomu array nagu mina tegin varem enamik meie näiteid? Lühike vastus on, massiivid on veidi eriline. Te saate peaaegu arvan puhver kui tegelikult on aadress, ja see just nii juhtub olema nii, et nurksulg märke on mugavuse nii et me saame minna sulg 0, 1 rühma, Rühma 2, ilma et peaksid kasutama * märke. See on natuke hädavale sest massiivid ja viiteid on tegelikult natuke teistsugune, kuid need võivad sageli, kuid mitte alati kasutada sünonüümidena. Ühesõnaga, kui funktsioon ootab kursor patakas mälu, võite edastada see aadress, mis tagastati malloc, ja me näeme malloc uuesti enne pikk, või saate andke seda nime massiivi. Sa ei pea tegema ampersand massiivid, sest nad on juba sisuliselt nagu aadressid. See on üks erand. Nurksulgudes need erilist. 

Kas paned märgi kõrval puhver? Mitte selles asjas. See ei tööta, sest jällegi, selle nurga korral kus massiivid ei ole päris tegelikult aadresse. Aga me võib-olla tagasi tulla, et enne pikka teiste näidetega. Proovime lahendada probleem. Meil on andmestruktuur, et oleme kasutanud juba mõnda aega tuntud kui massiiv. Asjas, seda me lihtsalt pidin. Aga massiivid on mõned plussid ja miinused. Massiivid on kena, miks? Mis on üks asi, mis sulle meeldib-ulatuses soovite massiivid-umbes massiivid? Mis mugav nendega on? Mis on kaalukad? Miks me tutvustada neid üldse? Jah. [Student] Neid saab salvestada palju andmeid, ja sa ei pea kasutama kogu asi. Võite kasutada jagu. Hea, massiivi saab salvestada palju andmeid, ja sa ei pea kasutama kõiki see, et saaksite overallocate, mis võiks olla mugav, kui te ei tea ette, kui palju midagi oodata. 

GetString on suurepärane näide. GetString, kirjutada meile, pole aimugi, kui palju tähemärki oodata, nii et saame eraldada tükkideks sidusmäluplokki on hea. Massiivid ka lahendada probleemi nägime paar nädalat tagasi nüüd kus oma koodi hakkab vaimule midagi väga halvasti projekteeritud. Tuletame meelde, et olen loonud õpilane struktuuri nimetatakse David, ja siis see oli tegelikult alternatiiv, kuigi võttes muutuja nimega nimi ja teise muutuja nimega, ma arvan, maja, ja teise muutuja nimega ID, sest seda lugu ma siis tahtnud midagi muud nagu Rob võetud programm, nii siis otsustasin oota üks hetk, Mul on vaja ümber nimetada need muutujad. Kutsume kaevanduse NAME1, ID1, house1. Kutsume Rob nimi2, house2, ID2. Aga siis oota natuke, kuidas Tommy? Siis oli meil veel kolm muutujat. Me tutvustas keegi teine, neljal muutujad. Maailm hakkas saada räpane väga kiiresti, nii et me tutvustas structs, ja mis mõjuvad umbes struct? Mis C struct lase sul teha? See on tõesti ebamugav täna. Mida? >> [Kuuldamatu õpilase vastus] Jah, just, typedef võimaldab teil luua uus andmetüüp, ja struktuure, struct märksõna, saab kapseldada kontseptuaalselt seotud tükki andmeid koos ja seejärel kutsume neid midagi üliõpilane. 

See oli hea, sest nüüd saame modelleerida palju omamoodi põhimõtteliselt samad mõiste üliõpilane muutuja mitte meelevaldselt võttes üks string, üks ID ja nii edasi. Massiivid on tore, sest nad võimaldavad meil alustada puhastamisega meie kood. Aga milline on negatiivsed nüüd massiivi? Mida saab mitte teha? Jah. [Student] Sa pead teadma, kui suur see on. Sa pead teadma, kui suur see on, nii see on selline valu. Neile, kellel eelnev programmeerimise kogemus teame, et palju keeli, nagu Java, võite küsida tüki mälu, konkreetselt massiiv, kui suur sa oled, pikkus, kinnisvara, nii et rääkida, ja see on tõesti mugav. C, siis ei saa isegi helistada strlen üldistel massiivi sest strlen, kuna sõna tähendab, on ainult stringe, ja saate aru saada, pikkus string, sest see inimeste konventsiooni võttes \ 0, kuid massiivi, rohkem üldmõistena, on vaid patakas mälu. Kui see on massiiv ints, seal ei kavatse olla mõned erimärgi aasta lõpus ootab sind. Te peate meeles pidama pikkus massiivi. Teine negatiivne külg massiivi kasvatatud oma pea getString ise. Mis on teine ​​negatiivne külg massiivi? Sir, ainult sina ja mina täna. [Kuuldamatu õpilase vastus] >> See on see mida? See on deklareeritud pinu. Okei, deklareeritud pinu. Miks sa ei meeldi? [Student] sest see läheb uuesti. Läheb uuesti. Okei, kui te kasutada massiivi eraldada mälu, sa ei saa näiteks tagasi, sest see on edasi pinu. Okei, see on kahjuks. Ja kuidas üks teine ​​massiiv? Kui sa jaotada see, et sa oled selline kruvitud, kui vajate rohkem ruumi kui massiiv on. 

Siis tutvustasime, mäletate, malloc, mis andis meile võime dünaamiliselt mälu eraldada. Aga kui me püüdsime erinevate maailma kokku? Mis siis, kui me tahtsime lahendada paar neist probleemidest nii me selle asemel, minu pliiats on magama jäänud siin- Mis siis, kui me selle asemel tahtis sisuliselt luua maailma, mis on enam niimoodi? See on massiiv, ja muidugi selline halveneb kui me tabas lõpuks massiiv, ja ma nüüd ei pea enam ruumi veel täisarv või teise iseloomu. Mis siis, kui me justkui ennetavalt öelda ka, miks me ei puhata see nõue, et kõik need tükkideks mälu olema kõrvuti seljad, ja miks mitte, kui mul on vaja int või char, anna mulle ruumi üks neist? Ja kui mul on veel vaja, anna mulle veel üks ruum, ja kui mul on veel vaja, anna mulle veel ruumi. Ära, mis nüüd on, et kui keegi teine võtab mälu siin, pole hullu. Ma võtan selle täiendava patakas mälu siin ja siis see üks. 

Nüüd, ainult saagi siin selles, et peaaegu tundub, nagu mul on terve hunnik erinevaid muutujaid. See tunne on viie erineva muutujad potentsiaalselt. Aga kui me varastada idee stringid millega me kuidagi siduda need asjad kokku kontseptuaalselt, ja mis siis, kui ma tegin seda? See on minu väga halvasti koostatud nool. Aga oletame, et kõik need tükkideks mälu osutas teisele ning see kutt, kes ei ole vend et tal on õigus, ei ole sellist nool. See on tegelikult see, mida nimetatakse seotud nimekirja. See on uus andmestruktuur, mis lubab meil eraldada tüki mälu, siis teine, siis teine, siis teine, iga kord kui me tahame jooksul programmi, ja me mäletame, et nad on kõik kuidagi seotud sõna otseses mõttes Aheldamise need kokku ja me tegime seda piltlikult siin noolega. Aga kood, mis oleks mehhanism, mille kaudu sa võiksid kuidagi ühendada, peaaegu nagu Scratch, üks patakas teise patakas? Me võiksime kasutada pointer, eks? Sest tõesti nool, mis läheb ülevalt vasakult ruut, see kutt siin see võiks sisaldada sees see ruut mitte ainult mõned ints, mitte ainult mõned char, kuid mis siis, kui ma tegelikult eraldatud natuke lisaruumi nii et nüüd, iga mu tükkideks mälu, kuigi see läheb mulle maksma, nüüd paistab pisut rohkem ristkülikukujuline kus üks mäluhulka kasutatakse mitmeid, nagu number 1, ja siis, kui see kutt salvestab number 2, see teine ​​patakas mälu kasutatakse nool, või konkreetsemalt, pointer. Ja arvan, et ma salvestada number 3 siin samas ma kasutan seda juhtida seda kutti, ja nüüd see mees, oletame, ma tahan ainult kolm sellist mäluhulka. Ma joonistan läbiv joon, et näitab null. Ei ole täiendavaid iseloomu. 

Tõepoolest, see on see, kuidas me saame minna rakendamisel midagi, mis kutsus seotud nimekirja. Seotud nimekirja on uus andmestruktuur, ja see on vahepealse poole palju Kasvataja andmestruktuurid et alustada probleemide lahendamiseks sarnaselt Facebook-tüüpi probleemide ja Google tüüpi probleeme kui sul on tohutu andmekogumid, ja see ei ole enam lõikab ta salvestada kõik contiguously ja kasutada midagi lineaarne otsing või isegi midagi binaarne otsing. Sa tahad veel parem töötab korda. Tegelikult üks Püha Grails me räägime hiljem sel nädalal või järgmisel on algoritm, kelle tööaeg on konstantne. Teisisõnu, see võtab alati sama ajaga ükskõik kui suur panus on, ja et oleks tõesti kaalukad, isegi rohkem kui midagi logaritmiline. Mis see on ekraanil siin? Kõik ristkülikud on täpselt, mida ma just joonistasin käsitsi. Aga asi kogu tee vasakul on eriline muutuja. See saab olema üks pointer, kuna üks gotcha koos seotud nimekirja, kuna need asjad on kutsutud, on see, et sa pead riputada peale üks ots seotud nimekirja. 

Just nagu string, sa pead teadma, aadress algustäht. Sama lahendust lingitud nimekirjad. Sa pead teadma, aadress esimese tüki mälu sest sealt saab jõuda iga teine. Negatiivne. Mis hinnaga me maksame selle eest mitmekülgsus võttes dünaamiliselt suurt andmestruktuur, et kui me üldse vajame rohkem mälu, peen, lihtsalt eraldada veel üks patakas ja juhtida kursorit alates vana uus saba nimekirja? Jah. [Student] See võtab umbes kaks korda nii palju ruumi. See võtab kaks korda nii palju ruumi, nii et kindlasti negatiivne külg, ja me oleme näinud seda Miinuseks enne vahelise aja ja ruumi ja paindlikkust kus nüüd, me ei pea 32 bitti iga nende numbrid. Meil on tõesti vaja 64, 32 numbrit ja 32 pointer. Aga hei, Mul on 2 GB RAM. Lisades veel 32 bitti siin ja siin ei tundu, et suur ja lahendamiseks. Aga suure andmekogumi, siis kindlasti lisab kuni sõna otseses mõttes kaks korda nii palju. Mis on veel negatiivsed nüüd, või mis funktsioon me loobuma, kui me esindame nimekirjad asjad seotud nimekirja ja ei massiivi? [Student] Sa ei saa läbida seda tahapoole. Sa ei saa läbida seda tahapoole, nii et sa oled natuke kruvitud kui oled jalgsi vasakult paremale kasutades loop või samas loop ja siis sa mõistad, "Oh, ma tahan minna tagasi algusesse nimekirja." Sa ei saa, sest neid viiteid minna ainult vasakult paremale nagu nooled näitavad. 

Nüüd sa ei mäleta algust nimekirja teise muutuja, kuid see keerukus meeles pidada. Massiiv, ükskõik kui kaugele sa lähed, sa võid alati teha miinus miinus miinus miinus ja lähevad tagasi sinna, kust sa tulid. Mis Teine negatiivne külg? Jah. [Kuuldamatu õpilane küsimus] Sa võiksid, nii et sa oled tegelikult lihtsalt ettepanek andmestruktuur nimetatakse kahekordselt seotud nimekirja, ja tõesti, sa oleks lisada veel kursor iga ristkülik mis läheb teises suunas, tagurpidi millest Nüüd saate läbida edasi-tagasi, negatiivne külg, mis on nüüd te kasutate kolm korda rohkem mälu kui me harjunud ja ka keerulisemaks poolest kood teil on kirjutada, et saan seda paremale. Aga need on kõik võib-olla väga mõistlik kompromissidega, kui pöördumise on tähtsam. Jah. [Student] Sa ka ei saa 2D seotud nimekirja. Hea, siis ei saa tõesti 2D seotud nimekirja. Sa võiksid. See ei ole kaugeltki nii lihtne kui massiivi. Nagu massiiv, sa sulg, suletud sulg, sulg, suletud sulg, ja siis saaksin 2-mõõtmeline struktuur. Sa võiksid rakendada 2-mõõtmeline seotud nimekirja kui sa add-kui ettepanek-1/3 pointer kõik need asjad, ja kui sa mõtled teisele nimekiri tulevad sind 3D stiil alates ekraani meile kõigile, mis on lihtsalt üks kett mingisugune. Me võiksime seda teha, kuid see ei ole nii lihtne kui kirjutades sulg, square bracket. Jah. [Kuuldamatu õpilane küsimus] Hea, et see on tõeline kicker. 

Need algoritmid, et oleme pined üle, nagu oh, binaarne otsing, saate otsida massiivi numbrid laual või telefoniraamatust nii palju kiiremini, kui te kasutate jaga ja valitse ja binaarne otsing algoritm, kuid Kahendotsingupuu vaja kahte eeldust. Üks, et andmed on järjestatud. Nüüd saame ilmselt hoida seda sorteeritud, nii et võibolla see ei ole probleem, kuid Kahendotsingupuu ka eeldada et sul oli ligi pääsema nimekiri numbrid, ja array võimaldab teil ligi pääsema ning muutmälu, Ma mõtlen, kui sa oled antud massiiv, kui palju aega see võtab teid saada sulg 0? Üks töö, sa lihtsalt kasutada [0] ja sa oled seal. Mitu sammu läheb aega, et saada asukoht 10? Üks samm, siis minge [10] ja sa oled seal. Seevastu kuidas sa saad 10. täisarv seotud nimekirja? Sa pead alustama alguses, sest sa oled ainult meeles aasta algusest seotud nimekirja, nagu string on meeles pidada, poolt aadressi oma algustäht ja leida, et 10. Väravavahi või et 10. iseloomu string, teil on otsida kogu kuraditki. 

Jällegi, me ei lahenda kõiki meie probleeme. Tutvustame Sulle uusi, aga see tõesti sõltub sellest, mida sa üritad disain. Seoses rakendamisel, saame laenata idee, et õpilane struktuur. Süntaks on väga sarnane, välja arvatud nüüd, idee on veidi abstraktsem kui maja ja nimi ja ID. Aga teen ettepaneku, et me võiks olla andmestruktuur C mida nimetatakse sõlme, kui viimane sõna slaid näitab, sees sõlm ja sõlme on lihtsalt üldine konteiner infotehnoloogia. See on tavaliselt joonistatud ring või ruut või ristkülik nagu me oleme teinud. Ja selles andmestruktuur, meil on int n, nii et see number ma tahan salvestada. Aga milline on see teine ​​rida, struct tipp * edasi? Miks on see õige, või mis rolli see asi mängida, kuigi see on veidi segasena esmapilgul? Jah. [Kuuldamatu õpilase vastus] Täpselt nii * omamoodi rikneb, et see on osuti mingisugune. Nime see osuti on omavoliliselt kõrval, kuid võinuks me seda kõike tahame, aga mida see osuti käsk? [Student] Teine sõlme. >> Täpselt, osutab ta teise sellise sõlme. 

Nüüd on see omamoodi uudishimu C. Tuletame meelde, et C on lugeda kompilaator ülevalt alla, vasakult paremale, mis tähendab kui-see on natuke erinev sellest, mida tegime koos üliõpilane. Kui me määratletud õpilane, me tegelikult ei pane sõna seal. See lihtsalt ütles typedef. Siis oli meil int id, String nimi, String maja, ja siis üliõpilane allosas struct. See deklaratsioon on veidi erinev, sest uuesti, C kompilaator on natuke tobe. See on ainult loen ülevalt alla, nii et kui ta jõuab 2. rida siin kus järgmine on deklareeritud ja ta näeb, oh, siin on muutuja nimega kõrval. See on kursor struct tipp. Kompilaator läheb mõistad, mida on struct tipp? Ma pole kunagi kuulnud seda asja enne, sest sõna sõlme muidu ei kuvata kuni põhja, seega on see ülearune. Sa pead ütlema struct tipp siin, mis saab siis lühendada hiljem tänu typedef siia alla, kuid selle põhjuseks on me viitamine struktuur ise sees struktuuri. See on üks gotcha seal. 

Mõned huvitavad probleemid hakkavad tekkima. Meil on nimekiri numbrid. Kuidas lisada see? Kuidas otsida seda? Kuidas kustutada seda? Eriti nüüd, et me peame hakkama kõiki neid viiteid. Sa arvasid, et osuti oli omamoodi Hallutsinatsioone kui sul oli üks neist lihtsalt üritan lugeda int ta. Nüüd on meil manipuleerida kogu nimekirja väärt. Miks me ei võta meie 5-minutilise pausi siin, ja siis me tuua mõned inimesed lavale teha just nii. 

C on palju lõbusam, kui ta on tegutsenud läbi. Kes oleks sõna otseses mõttes meeldib olla esimene? Okei, tulge siia. Olete esimene. Kes tahaks olla 9? Okei, 9. Kuidas umbes 9? 17? Väike kildkond siin. 22 ja 26, et esireas. Ja siis kuidas keegi seal on osutanud. Olete 34. Okei, 34, tulge siia. Esiteks on seal. Okei, kõik neli kutid. Ja kes me siis ütleme 9? Hetkel meie 9? Kes tõesti tahab olla 9? Olgu, tule, on 9. Läheb lahti. 34, me sinuga kohtuda seal. Esimene osa on teha ise näeb välja selline. 26, 22, 17, hea. Kui te ei saa seista välja, et pool, sest me ei kavatse malloc teile kohe. 

Hea, hea. Okei, väga hea, niiet küsida paar küsimust siin. Ja tegelikult, mis su nimi on? >> Anita. Anita, okei, tule siia. Anita ei aita meid omamoodi lahendada üks üsna lihtne küsimus esiteks, mis on, kuidas sa teada, kas raha on nimekirjas? Nüüd märkate, et esimene, keda esindab siin Lucas on natuke erinev, ja nii ta paberile on tahtlikult külili sest see ei ole päris nii pikk ja ei võta nii palju bitti, kuigi tehniliselt ta on sama suurusega paberile lihtsalt keerutada. Aga ta on veidi teistsugune, kuna ta on vaid 32-bitise pointer, ja kõik need kutid on 64 bitti, millest pool on number, millest pool on osuti. Aga osuti ei ole kujutatud, nii et kui te poisid võiks veidi kohmakalt kasutada oma vasaku käe juhtida tähelepanu inimene sinu kõrval. Ja sina oled number 34. Mis su nimi on? Ari. Ari, et tegelikult, hoidke paberit oma parema käe ja vasaku käe läheb otse alla. Te esindate null vasakul. 

Nüüd on meie inimeste pilt on väga järjekindel. See on tegelikult kuidas osuti tööta. Ja kui sa ei krigin natuke nii et ma ei ole oma teel. Anita siin, leia mind number 22, aga eeldada piirang ei inimeste hoidmine paberitükke, kuid see on nimekiri, ja sul on ainult Lucas alustada sest ta on sõna otseses mõttes esimene pointer. Oletame, et te ise ei pointer, ja et sa liiga on võime juhtida midagi. Miks sa ei alusta osutades täpselt, mida Lucas on osutavad? Hea ja lubage mul kehtestama seda läbi siin. Lihtsalt huvides arutelu, las ma tõmba tühi leht siin. Kuidas seda kirjutada oma nime? >> Anita. Okei, Anita. Oletame sõlme * Anita = Lucas. Noh, me ei tohiks helistada Lucas. Me peaksime kutsuma teid esimesena. Miks see tegelikult kooskõlas reaalsus siin? Üks esimene on juba olemas. Esiteks on eraldatud arvatavasti kuskil siin. Sõlme * esimene, ja see on eraldatud nimekiri kuidagi. Ma ei tea, kuidas see juhtus. See juhtus enne klassi algust. See on seotud nimekirja inimestel on loodud. Ja nüüd siinkohal lugu-see kõik läheb Facebookis ilmselt hiljem- siinkohal lugu, Anita on lähtestatud olema võrdne esimese, mis ei tähenda, et Anita punkte Lucas. Pigem Ta juhib seda, mida ta osutab sest sama aadress, mis on seestpoolt Lucase 32 bitti - 1, 2, 3 - Nüüd on ka sees Anita 32 bitti - 1, 2, 3. 

Nüüd uuri 22. Kuidas te minna seda teed? Mis see on? >> Pointi iganes. Osutage iganes, nii et edasi minna ja tegutseda selle välja nii hästi kui võimalik siin. Hea, hea, ja nüüd sa viitaksid-mis su nimi on 22? Ramon. >> Ramon, nii Ramon hoiab kuni 22. Sul on nüüd tehtud kontroll. Kas Ramon == 22, ja kui on, siis näiteks me saame naasta tõsi. Lubage mul-samas need kutid siin seista mõnevõrra kohmakalt- las ma teen midagi kiiresti nagu bool leida. Ma lähen edasi minna ja öelda (node ​​* nimekirja, int n). Ma tulen kohe tagasi koos teiega. Ma lihtsalt pean kirjutama mingi kood. Ja nüüd ma lähen edasi minna ja teha seda, sõlme * Anita = nimekirja. Ja ma lähen edasi minna ja öelda, et kui (Anita! = NULL). 

Metafoor siin muutub vähe venitatud, kuid samas (Anita! = NULL), mida ma tahan teha? Ma pean kuidagi viitamine täisarv, et Anita on osutavad. Varem, kui meil oli struktuure, mis sõlme on, me kasutasime dot märke, ja me ütleks midagi anita.n, kuid probleem on selles, et Anita ei ole struct iseenesest. Mis ta on? Ta on osuti, nii tõesti, kui me tahame seda kasutada dot märke- ja see läheb otsima sihilikult veidi segasena- me peame midagi tegema, nagu minema iganes Anita vasak käsi vastakuti ja siis saad Väli n. Anita on viit, aga mis on * Anita? Mida sa leida, kui lähete mida Anita on osutavad? Struct, sõlm ja sõlme, mäletate, on väli nimega n sest see on, meenutavad need 2 välja kõrval ja n et me nägime hetk tagasi siin. 

Et tegelikult imiteerida seda koodi, me võiks seda teha ja öelda if ((* Anita). n == n), n et ma otsin. Pange tähele, et funktsioon võeti vastu mitmeid ma hoolin. Siis ma saan minna ja teha midagi tagasi tõsi. Else, kui see ei ole, mida ma tahan teha? Kuidas tõlkida koodi mida Anita tegi seda intuitiivselt jalgsi läbi nimekirja? Mida ma peaksin tegema siin simuleerida Anita võttes, et samm vasakule, et samm vasakule? [Kuuldamatu õpilase vastus] >> Mis see on? [Kuuldamatu õpilase vastus] Hea, ei ole halb mõte, kuid varem, kui oleme seda teinud, oleme teinud Anita + + sest et lisaksin number 1, Anita, mis tavaliselt osutavad järgmisele inimesele, nagu Ramon, või isik tema kõrval, või tema kõrval inimene sätestatakse rida. Aga see ei ole päris hea siin, sest mida see asi välja nägema mälu? Mitte seda. Meil on keelata seda. See näeb välja selline mälu, ja kuigi olen juhtinud 1 ja 2 ja 3 lähestikku, kui me tõesti simuleerida see-Kas te poisid, samas rõhutades samal inimesi, saab mõned te võtate juhuslikult sammu tagasi, mõned teist juhuslik samm edasi? 

See jama on ikka seotud nimekirja, kuid need kutid võiks olla kuskil mälus, nii Anita + + ei kavatse töötada miks? Mis kell asukoha Anita + +? Kes teab. See on mingit muud väärtust, et just nii juhtub olema interposed kõigi nende sõlmede juhus, sest me ei kasuta massiivi. Me eraldatud kõik need sõlmed iseseisvalt. Okei, kui te võite puhastada ennast varundada. Las ma ettepaneku, et selle asemel, et Anita + +, me mitte teha Anita saab- Noh, miks me ei võiks minna mis iganes Anita on osutavad ja tehke. edasi? Teisisõnu, me läheme Ramon, kes hoiab arv 22, ja siis. kõrval on justkui Anita oleks kopeerimine vasaku käega osuti. Aga ta ei läheks kaugemale kui Ramon, sest me leidsime 22. Aga see oleks mõte. Nüüd on see Kalama jama. Ausalt, keegi ei mäleta seda süntaksit ja nii õnneks see on tegelikult natuke tahtlik-oh, sa tegelikult ei vaata, mida ma kirjutasin. See oleks selgem, kui sa saaksid. Voila! 

Kulisside taga, olin probleemi lahendamiseks nii. Anita, selle sammu vasakule, Esiteks, me minna aadress, et Anita on osutavad ja kui ta leiad mitte ainult n, mida me lihtsalt kontrollida võrdlus küll, aga sa leiad ka järgmine - sel juhul Ramon vasaku käega osutades järgmise sõlme nimekirja. Aga see on Kalama jama millele viitasin varem aga tuleb välja, C laseb meil seda lihtsustada. Selle asemel, et kirjalikult (* Anita), saame selle asemel lihtsalt kirjutada anita-> n, ja see on täpselt sama asi funktsionaalselt, kuid see on palju intuitiivsem, ja see on palju rohkem kooskõlas pilt, et oleme olnud joonistus Kogu selle aja jooksul, kasutades nooli. 

Lõpuks, mida me peame tegema lõpus selle programmiga? Seal on üks rida koodi alles. Tagasi mida? Vale, sest kui me saame läbi kogu samas loop ja Anita on tegelikult null, mis tähendab, et ta läks kõik viis lõpuks nimekirja kus ta vastakuti-mis su nimi oligi? Ari. >> Ari vasak käsi, mis on null. Anita on nüüd null, ja ma mõistan, et sa lihtsalt seisad siin kohmakalt segadusse sest ma lähen maha monoloogi siin, kuid me kaasata teid jälle üks hetk. Anita on null sellel hetkel lugu, et samal ajal loop lõpeb, ja me peame tagasi false, sest kui ta sai kõik viis Ari nullviit siis ei olnud number, et ta otsis nimekirjas. Me ei korista see ära ka, aga see on päris hea rakendamise siis ja läbipääsusüsteemid funktsioon, leida funktsiooni seotud nimekirja. See on ikka lineaarne otsing, kuid see ei ole nii lihtne kui + + pointer või + + i muutuja sest nüüd me ei saa vist kus kõik need sõlmed on mälu. Me peame sõna otseses mõttes järgida rada riivsai või täpsemalt suunanäitajaks, et saada ühest tipust teise. 

Nüüd proovime veel ühe. Anita, sa tahad siia tagasi tulla? Miks me ei võiks minna edasi ja eraldada veel üks inimene saalist? Malloc-mis su nimi on? >> Rebecca. Rebecca. Rebecca on malloced publik, ja ta on nüüd ladustamiseks number 55. Ja eesmärk käepärast nüüd on Anita lisada Rebecca arvesse seotud nimekirja siin oma õige koht. Tule siia hetkeks. Ma olen teinud midagi sellist. Olen teinud sõlme *. Ja mis su nimi oligi? Rebecca. >> Rebecca, eks. Rebecca saab malloc (sizeof (node)). Just nagu oleme eraldanud asjad õpilased ja tühi-tähi minevikus, peame suurus sõlm, nii et nüüd Rebecca on osutavad mida? Rebecca on kaks valdkonda tema sees, millest üks on 55. Teeme mida, rebecca-> = 55. Aga siis rebecca-> next tuleb-nagu praegu, käsi on selline, kes teab? See osutavad mõned prügi väärtus, nii et miks mitte hea meede me vähemalt seda teha nii, et vasak käsi on nüüd tema kõrval. Nüüd Anita, võtke see siit. Sul on Rebecca kellele on määratud. Mine ja leia, kus me peaks Rebecca. Hea, väga hea. Okei, hea, ja nüüd me peame teile pakkuda natuke suunda, nii olete jõudnud Ari. Tema vasak käsi on null, kuid Rebecca selgelt kuulub õigus, Niisiis, kuidas me peame muutma seda, mis on seotud nimekirja et lisada Rebecca õigesse kohta? Kui võid sõna otseses mõttes liigutada inimeste vasak käsi ümber kui vaja, me probleemi lahendada nii. Okei, hea, ja vahepeal Rebecca vasak käsi on nüüd tema kõrval. 

See oli liiga lihtne. Proovime eraldamise-oleme peaaegu valmis, 20. Okei, tulge siia. 20 on eraldatud, seega lubage mul minna ja öelda jälle siin me oleme lihtsalt teinud sõlme * Saad. Meil on malloc (sizeof (node)). Me tehke sama täpne süntaks nagu tegime enne 20, ja ma teen next = NULL, ja nüüd on see kuni Anita lisada sind seotud nimekirja, kui sa võiksid mängida, et täpselt sama rolli. Execute. Olgu, hästi. Nüüd mõelge hoolikalt enne kui hakkate liikuma vasakule käed ümber. Sa kaugelt sai kõige ebamugav roll täna. Kelle poolt tuleb viia esimesena? Okei, oota, ma kuulen mõned ei oma. Kui mõned inimesed oleks viisakalt tahan aidata lahendada ebamugav olukord siin. Kelle vasaku käe tuleks ajakohastada 1. ehk? Jah. [Student] Saad oma. Okei, Saad-ndatel, miks küll? [Kuuldamatu õpilase vastus] Hea, sest kui me liigume-mis su nimi on? >> Marshall. Marshall, kui me liigume oma käe esimese alla null, nüüd oleme sõna otseses mõttes orvuks neli inimest selles nimekirjas sest ta oli ainus asi, mis viitaksid Ramon ja kõik vasakule, nii ajakohastamine, et osuti Esimene oli halb. Olgem undo seda. Hea ja nüüd minna ja liikuda asjakohased vasakul osutades Ramon. See tundub natuke ülearune. Nüüd on kaks inimest osutades Ramon, kuid sellest pole midagi sest nüüd, kuidas muidu me ajakohastab nimekirja? Mis muud käsi liigub? Suurepärane, nüüd on meil kaotanud mälu? Ei, nii hea, vaatame, kui me ei suuda murda seda veel korra. 

Mallocing viimast korda, number 5. Kõik viis tagasi, tule alla. See on väga põnev. [Aplaus] Mis su nimi on? >> Ron. Ron, okei, sa oled malloced kui number 5. Me oleme lihtsalt täide kood, mis on peaaegu identne need lihtsalt teine ​​nimi. Suurepärane. Nüüd, Anita, õnne sisestamist number 5 esitatud loetellu nüüd. Hea ja? Suurepärane, nii et see on tõesti üks kolmest kõigist juhtudest. Meil oli esimest korda keegi lõpus, Rebecca. Siis tuli keegi keskel. Nüüd on meil keegi alguses, ja selles näites nüüd tuli uuendada Lucas esimest korda sest esimene element nimekirjas on nüüd punkti juures uus sõlm, kes omakorda on suunaga sõlme number 9. 

See oli väga ebamugav meeleavaldus, ma olen kindel, nii suur aplaus on need kutid, kui te saaksite. Ilusti tehtud. See on kõik. Sa võid hoida oma paberitükke kui vähe mälu. Selgub, et teed seda koodi ei ole päris nii lihtne kui lihtsalt liiguvad käed ümber ja juhtides viiteid eri asjad. Aga mõistan, et kui on aeg rakendada midagi seotud nimekirja või variant see, kui teil keskenduda tõesti neid põhilisi alustalasid, hammustada suurusega probleeme mul aru saada, see on selle poolt või selle küljest aru, et mida on muidu üsna keeruline programm võib tegelikult vähendada üsna lihtne ehitusplokkide niimoodi. 

Võtame asju keerulisemaks suunas ikka. Meil on nüüd mõiste seotud nimekirja. Meil on ka-tänu ettepanek tagasi seal-kahekordselt seotud nimekirja, mis näeb välja peaaegu sama, kuid nüüd on meil kaks suunanäitajaks sees struct ühe asemel, ja me võiks ilmselt helistada nendele viiteid eelmise ja järgmise või vasakule või paremale, kuid me tegelikult vaja kahte neist. Kood oleks natuke rohkem kaasatud. Anita oleks pidanud tegema rohkem tööd siin laval. Aga me võiks kindlasti rakendada sellist struktuuri. Seoses sõiduaega, aga milline oleks sõiduaega Anita leida mitmeid n seotud nimekirja nüüd? Ikka suur O n, seega pole parem kui lineaarne otsing. Me ei saa Kahendotsingupuu, aga uuesti. Miks oli nii? Sa ei saa hüpata ringi. Kuigi me ilmselt näha kõiki inimesi laval, ja Anita oleks eyeballed ta ja ütles: "Siin on keset nimekirja," ta ei tea, et kui ta oleks arvutiprogrammi sest ainus asi, ta pidi jtk alguses stsenaariumi oli Lucas, kes oli esimene pointer. Ta oleks tingimata peavad järgima neid sidemeid, lugedes tema viis kuni ta leidis umbes keskel, ja isegi siis, ta ei kavatse tea, millal ta jõudis keskel kui ta läheb kõik viis lõpuks aru saada, kui palju seal on, siis Backtracks, ja et liiga oleks raske, kui sul oli kahekordselt seotud nimekirja mingisugune. 

Lahendada mõned probleemid täna, kuid kasutusele teised. Aga eri andmestruktuuri kokku? See on foto plaate Ema House, ja sel juhul on meil andmestruktuur oleme ka omamoodi juba rääkinud. Me rääkisime korstnat kontekstis mälu, ja see on omamoodi tahtlikult nime, sest virna nii mälu on tõhusalt andmestruktuur, mis on rohkem ja rohkem asju kihiti ta. Aga huvitav asi korstnat, nagu see tegelikult et see on eriline andmestruktuur. See on andmestruktuur, mille esimene element on viimane osa välja. Kui te olete esimene plaat tuleb lasta peale virna, sa lähed olema kahjuks viimane plaat võetakse välja korstnat ja mis ei ole tingimata hea asi. Samas võite mõelda teistpidi, viimane on esimene välja. 

Nüüd ei ühtegi stsenaariumi pähe tulevad, kui võttes virna andmestruktuur, kus sa pead, et vara viimase sisse, esimesena välja, on tegelikult mõjuvad? Kas see on hea asi? Kas see halb? See on kindlasti halb, kui plaate ei olnud kõik ühesugused Ja nad olid kõik eri eri värvi või tühi-tähi, ja soovitud värvi on kõik viis põhjas. Muidugi, sa ei saa, et ilma suuri pingutusi. Sul on alustada tipust ja tööd teed alla. Samamoodi kui sa olid üks neist fänn poistele kes ootab terve öö üritavad iPhone ja read üles kohas nagu see on? Kas poleks tore, kui Apple Store olid virnas andmestruktuur? Jee? Ei? See on ainult hea, et inimesed, kes näitavad üles viimsel võimalik hetke ja siis saad kiskunud maha järjekorda. Ja tegelikult see, et ma olin nii valmis ütlema järjekorda on tegelikult kooskõlas sellega, mida me nimetame sellist andmestruktuur, üks reaalsus, kus selleks ei asja, ja sa tahad esimene üks olla esimene, kes välja kui ainult huvides inimeste õiglus. Me tavaliselt nimetame seda järjekorda andmestruktuur. 

Selgub, lisaks seotud nimekirjad, saame hakata kasutama neid samu ideid ja alustada luua uusi ja erinevaid lahendusi probleemidele. Näiteks juhul, kui korstna, me võiks olla korstnat kasutades andmestruktuur meeldib see, ma teen ettepaneku. Sel juhul olen deklareeritud struct, ja ma olen öelnud sees selle struktuuri on array numbrite ja siis muutuja nimega suurus, ja ma nimetan seda asja pinu. Nüüd, miks see tegelikult toimib? Juhul virna, ma võiksin teha seda tõhusalt ekraanile massiiv. Siin on minu stack. Need on minu numbrid. Ja me juhtida neid see, see, see, see, see. Ja siis mul on mõned muud andmed liige siin, mida nimetatakse suurust, nii et see on suurus, ja see on numbrid, ja kollektiivselt, kogu iPad siin on üks korstnat struktuur. Nüüd, vaikimisi suurus on arvatavasti pead olema vormindatud 0, ja mis seal sees on array numbrite esialgu kui ma esimest eraldada massiivi? Prügi. Kes teab? Ja see ei ole tegelikult oluline. See ei ole tähtis, kas see on 1, 2, 3, 4, 5, täiesti juhuslikult poolt halb õnn salvestatud minu struktuuri, sest nii kaua, kui ma tean, et suurus pakk on 0, siis ma tean, programmiliselt, ei vaata ühtegi massiivi elementide. Ei ole oluline, mis seal on. Ära vaata neid, nagu oleks tähendus suurus 0. 

Aga oletame nüüd ma edasi minna ja sisestada midagi korstnat. Ma tahan sisestada number 5, panin number 5 siin, ja siis mis ma panen siia alla? Nüüd ma tegelikult panema 1 suurus, ja nüüd stack on suurus 1. Aga kui ma edasi minna ja sisestada number, oletame, 7 järgmine? See siis saab ajakohastada 2, ja siis me teeme 9, ja siis see saab ajakohastada 3. Aga huvitav omadus nüüd selle virna, et Ma peaksin eemaldada mis element kui ma tahan pop midagi välja virna, nii rääkida? 9 oleks esimene asi minna. Kuidas peaks pilt muutuma, kui ma tahan pop element ära pinu, meelega salve Ema? Jah. >> [Student] Seadistage suurus 2. Täpselt, kõik, mida ma tegema, on määrata suurus 2, ja mida ma teha massiivi? Ma ei pea midagi tegema. Ma võiks lihtsalt olla anal, pane 0 leidub või -1 või midagi tähendama et see ei ole legit raha, kuid see ei ole oluline, sest Võin salvestada väljaspool massiiv ise, kui kaua see on nii et ma tean ainult pilk esimese kahe elemendi käesolevas massiivi. Nüüd, kui ma olen läinud ja lisada number 8 selle massiivi, kuidas pilt muutub järgmisel? See muutub 8, ja see muutub 3. Ma lõigates mõned nurgad siin. Nüüd on meil 5, 7, 8, ja me oleme tagasi suurusega 3. See on üsna lihtne rakendada, aga kui me hakkame kahetsema disain otsuse? Millal asjad hakkavad minema väga, väga valesti? Jah. [Kuuldamatu õpilase vastus] Kui sa tahad minna tagasi ja saada esimene element paned sisse 

Tuleb välja, siin isegi virna on massiiv all kapuuts, Nende andmestruktuurid oleme hakanud rääkima ka üldiselt tuntakse abstraktne andmestruktuurid mille kuidas nad ellu on täiesti kõrval punkti. Andmestruktuuri nagu pinu peaks lisama toetust toiminguid nagu push, mis lükkab salve peale virna, ja pop, mis eemaldab elemendi korstnat, ja ongi kõik. Kui sa alla laadida kellegi teise koodi, kes juba rakendatud see asi, mida nimetatakse kuhja, et inimene oleks kirjutanud ainult kaks funktsiooni teile, push ja pop, kelle ainus eesmärk elus oleks teha just nii. Sa või teda kes teostas seda programmi oleks olnud täielikult see, kes otsustab, kuidas rakendada semantika surudes ja popping all kapuuts või funktsionaalsust surudes ja popping. Ja ma olen teinud veidi lühinägelik otsus siin rakendades mu stack seda lihtne andmestruktuur miks? Millal see andmestruktuur murda? Mis hetkest ma pean tagasi viga kui kasutaja nõuab lükkamiseks, näiteks? [Student] Kui ei ole enam ruumi. Täpselt, kui pole enam ruumi, kui olen ületanud võimsuse mis on kõik mütsid, sest see näitab, et see on mingisugune ülemaailmne pidevalt. Noh, siis ma lihtsalt lähen on öelda: "Vabandust, ma ei saa suruda teisele väärtusele peale virna, "palju meeldib Ema. 

Mingil hetkel, nad ei kavatse tabanud ülaosa et vähe kapis. Pole veel ruumi või mahu pakis, kus punkt seal on mingi viga. Nad on panna element kusagil mujal, salve kusagil mujal, või kuskil üldse. Nüüd, kus järjekorda, saame rakendada seda natuke teistmoodi. Järjekord on veidi teistsugune, kuna all kapuuts, seda saab rakendada massiivina, kuid miks, sel juhul ma ettepaneku et ka pea element esindab juhataja nimekiri, ees nimekiri, kes esimesena joone Apple poest, lisaks suurus? Miks ma pean veel tükk andmed siin? Mõtle tagasi sellele, mida numbrid on kui olen ära, järgmiselt. Oletame, et see on nüüd järjekorda asemel virna, Vahe on selles, nagu Apple Store-järjekord on õiglane. Esimene inimene kooskõlas alguses nimekirja, number 5 antud juhul ta läheb lase poodi esimesena. Teeme seda. Oletame, et see on riigi oma järjekorda selles ajahetkel, ja nüüd Apple Store Avaneb esimene inimene, number 5 on viinud poodi. Kuidas muuta pilti nüüd, et ma olen de-sabas esimene inimene ees rida? Mis see on? >> [Student] Muuda järjekorda. Muutus pea, nii 5 kaob. Tegelikult, see on justkui-kuidas seda teha? Tegelikult, see on nagu see kutt kaob. Mis oleks number 7 teha tegeliku hoida? Nad võtta suur samm edasi. 

Aga mida me hakanud hindama, kui tegemist on massiivid ja liikudes asju ümber? See on selline raiskamine oma aega, eks? Miks sa pead olema nii anaal on esimene inimene alguses joone füüsiliselt algust patakas mälu? See on täiesti tarbetu. Miks? Mida ma lihtsalt mäletan asemel? >> [Kuuldamatu õpilase vastus] Täpselt, ma lihtsalt mäletan seda lisaandmed liige peaga et nüüd eesotsas nimekirja ei ole enam 0, mis ta oli hetk tagasi. Nüüd on tegelikult number 1. Sel moel, saan kerge optimeerimine. Lihtsalt sellepärast, et ma olen de-sabas keegi line alguses liin kell Apple Store ei tähenda, igaüks peab minema, mis meenutavad on lineaarne operatsioon. Võin asemel kulutama pidevalt aega ainult ja saavutada siis palju kiiremat reageerimist. Aga hind ma maksan on see, mida saada, et täiendava tõhususe ja ei ole vaja suunata kõigile? Jah. >> [Kuuldamatu õpilase vastus] Kas lisada rohkem inimesi, noh, see probleem on ortogonaalne asjaolust, et me ei suunates inimeste ümber. See on ikka massiivi, nii kas muudame kõik või mitte- oh, ma näen, mida sa mõtled, eks. Tegelikult olen nõus, mida sa räägid, et see on peaaegu nagu me nüüd ei kavatse kasutada alustada selle massiivi enam sest kui ma eemaldan 5, siis ma eemaldan 7. Aga ma panna ainult inimesed õige. 

Tundub, nagu ma olen raiskab ruumi, ja lõpuks minu järjekord laguneb midagi, nii et me võiks lihtsalt inimesed Kietaisu, ja me võiks mõelda selle massiivi tõesti nagu mingi ümmarguse struktuuri, aga me kasutame mida operaator C teha, et omamoodi Kietaisu? [Kuuldamatu õpilase vastus] >> moodul operaator. Oleks veidi tüütu, et mõelda läbi, kuidas sa teed Kietaisu, kuid me ei tee seda, ja me võiksime alustada seab inimesed mida varem joone ees, kuid me lihtsalt mäletan seda pea muutuja kes tegelikult juht rida tegelikult on. Mis siis, kui selle asemel, meie eesmärk lõppkokkuvõttes, kuigi oli otsida numbreid, nagu tegime siin laval Anita, kuid me tõesti tahame kõige parem need maailmad? Me tahame rohkem rafineeritumalt kui massiivi võimaldab sest me tahame võime dünaamiliselt kasvada andmestruktuur. Aga me ei taha olla abiks, et midagi, mis me märkisime Esimeses loengus ei olnud optimaalne algoritm, et lineaarne otsing. Selgub, et saate tegelikult saavutada või vähemalt lähedal pidevalt aega, mille keegi nagu Anita, kui ta seadistab oma andmestruktuur mitte olla seotud nimekirja, ei oleks pinu, et tegu pole järjekorda, võib tegelikult tulla andmestruktuur, mis võimaldab teda otsida asju, isegi sõnu, mitte ainult numbreid, mida me kutsume pidevalt aega. 

Ja tegelikult eesolevaid üks psets selles klassis on peaaegu alati rakendamise õigekirja, mille anname jälle mõned 150000 ingliskeelsed sõnad ja eesmärk on laadige need mällu ja kiiresti suutma vastata küsimustele vormi on see sõna õigesti kirjutatud? Ja see oleks tõesti imeda, kui sa pidid itereerima läbi kõik 150.000 sõnad sellele vastama. Aga tegelikult me ​​näeme, et me saame seda teha väga, väga kiire aeg. Ja see läheb kaasata rakendamise midagi, mida nimetatakse hash tabelit, ja kuigi esmapilgul see asi nimega hash tabelit saab lase meil saavutada need super kiire reageerimise aega, selgub, et seal on tegelikult probleem. Kui on aeg rakendada seda asja nimetatakse-jälle, ma teen seda uuesti. Ma olen siin ainuke. Kui on aeg rakendada seda asja nimetatakse hash tabelit, me lähed on teha otsus. Kui suur peaks see asi tegelikult on? Ja kui hakkame lisades numbrid sellesse hash tabelit, kuidas me hoida neid nii et me saame nad tagasi viia nii kiiresti kui saime neid? Aga me näeme peagi, et see küsimus kui kõik sünnipäev on klass on üsna Sobiv. Selgub, et selles toas on meil paarsada inimest, nii tõenäosus, et kaks meist on sama sünnipäev on ilmselt päris suur. Mis siis, kui seal oli ainult 40 meist siin ruumis? Mis on tõenäosus kaks inimest, kellel on sama sünnipäev? [Õpilased] Üle 50%. Jah, üle 50%. Tegelikult ma isegi tõi diagrammi. Selgub-ja see on tõesti ainult vargsi eelvaade- kui seal on ainult 58 meist siin ruumis, tõenäosus 2 juures millel on sama sünnipäev on väga kõrge, peaaegu 100%, ja et läheb põhjustada terve hunnik haiget meile kolmapäeval. 

Olles seda öelnud, lähme edasi lükata siin. Näeme kolmapäeval. [Aplaus] [CS50.TV]