[Powered by Google Translate] [Hét 6] [David J. Malan] [Harvard Egyetem] [Ez a CS50.] [CS50.TV] 

Ez CS50, és ez a kezdete Hét 6, így egy pár új eszközök már elérhető az Ön számára, hogy kihasználják, melyek közül az első az úgynevezett CS50 Style. Valószínű, ha te, mint én, vagy a tanítás ösztöndíjasok, akkor már valószínűleg látott egy programot, amelynek stílusa egy kicsit úgy néz ki, valami ilyesmi. Talán kezd vágás néhány sarkok késő este, vagy akkor foglalkozni vele később, majd egy TF vagy CA átjön munkaidőben. Akkor nehéz nekünk olvasni. Nos, ez a kód szintaktikailag helyes, és ez le, és ez lesz a ténylegesen megtett. De ez egyáltalán nem egy 5 a stílus. 

De most, ha bemegy ebbe a könyvtárba a továb- , és vegyük észre, hogy van conditions2.c- és Én vezetem ezt az új parancs style50, az ezt a fájlt conditions2.c, az Enter, észre, hogy ez közölte velem, hogy ez már stilizált. Gedit észrevette, hogy a fájl megváltozott a lemezen, és ha újra kattint, az összes problémát már automatizált. [Taps] Ez az egyik dolog, amit tett ezen a hétvégén. Ismerd fel, hogy ez a tökéletlen, mert vannak olyan kódot hogy egyszerűen nem lesz képes, hogy stilizál tökéletesen, de észre ez most egy eszköz csak akkor veheti igénybe a ha csak rendet néhány látna errantly elhelyezett kapcsos zárójelek és hasonlók. 

De még kényszerítő most CS50 megtekintése. A CS50 Check, akkor valóban végezze el ugyanazt a helyességét vizsgálatok a saját kódját, hogy a tanítási fickók képesek. Ez egy parancssori segédprogram, ami most a készülék amint te egy update50, mint egy Pset 4 előírásokat, és használja azt lényegében, mint ez. Azt a parancsot check50. Akkor át egy parancssori argumentum, vagy még általánosabban ismert kapcsolóval vagy a zászló. Általában, a dolgok, amelyek kötőjelek hívják kapcsoló egy parancssori program, így a-c meghatározza az ellenőrzések, hogy a futtatni kívánt. 

A teszteket futtatni kívánt azonosítja egyedileg ez string, 2012/pset4/resize. Más szóval, ez csak egy tetszőleges, de egyedi karaktersorozat hogy az általunk használt, amely egyedileg azonosítja Pset 4-es helyességét vizsgálatok. És akkor meg egy szóközzel elválasztott lista a kívánt fájlokat feltölteni A CS50 Check elemzésre. Például, ha elmegyek az én megoldás itt resize.c- hadd nyit egy nagyobb terminál ablak és úgy megy előre, és fuss mondjuk check50-c 2012/pset4/resize, aztán megy előre, és adja meg a nevét a fájlokat, resize.c, majd Enter, azt tömöríti, azt feltöltve, ellenőrzi, és én csak nem sikerült egy csomó tesztet. Az egyik piros a bal felső sarokban azt mondja, hogy resize.c és bmp létezik. Ez volt a vizsgálat. Ez volt az a kérdés, amit feltett. És ez szomorú, mert a válasz hamis. A fehér alábbi szöveg azt mondja, várható, bmp.h létezik, és ez csak az én hibám. Elfelejtettem feltölteni, így azt kell feltölteni a két kép, resize.c és bmp.h. De most észre minden egyéb vizsgálatok vannak sárga, mert nem fut, és így a mosolygó arc függőleges, mert ő sem boldog, sem szomorú, de van, hogy orvosolja ezt a kérdést, mielőtt a piros egyéb ellenőrzéseket fog futni. 

Hadd erősít ez. Hadd kicsinyítés és futtassa újra ezt ezúttal is bmp.h a parancssorban, Enter, és most, ha minden jól megy, ez megy, hogy ellenőrizze, majd visszatér eredményeként, tartsa vissza a lélegzetét, minden zöld, ami azt jelenti, csinálok nagyon jól Pset 4 eddig. Láthatjuk és következtethetett a leíró szöveget ide Pontosan mi az teszteltük. Megvizsgáltuk 1. nem a fájlok léteznek? Ezután teszteltük fejti resize.c fordítás? Aztán tesztelt jelent ez nem átméretezni egy 1x1 pixeles BMP ha n, az átméretezés tényező 1 lehet. Most, ha fogalmad sincs, mi n, akkor egyszer belevetik magukat Pset 4, de ez egyszerűen a józan győződjön meg róla, hogy te nem átméretezés képet egyáltalán, ha az átméretezés tényező 1 lehet. Ha viszont, hogy átméretezi a 1x1 pixel egy 1x1 pixel BMP 2x2 helyesen ha n értéke 2, akkor hasonlóan, enyém formák megfelelően. 

Röviden, ez azt jelentette, hogy az egyik, hogy a keresztezési az ujjak ki az egyenlet jobb, mielőtt be Pset. Ön pontosan tudja, mi a TF hamarosan tudni ha megy a benyújtása néhány ilyen probléma készletek, valamint a pedagógiai motiváció valóban tenni lehetőséget elé úgy, hogy amikor tudod a priori hogy van hiba a kódban és vizsgálatokat, amelyeket még nem telt el, akkor tegye a hatékonyabb időben előre, hogy megoldja ezeket a problémákat ahelyett veszít pontokat, kap visszajelzést a TF, és aztán megy, "Ó," mint kellett volna gondoltam, hogy ki. Most legalább van egy eszköz, amely segít megtalálni azt. Ez nem fog rámutatni, hol van a hiba, de ez fogja mondani milyen tünete is. 

Most már észre a tesztek nem feltétlenül teljes. Csak azért, mert kapsz egy teljes képernyős zöld smiley arcok nem azt jelenti, a kód nem tökéletes, de ez nem jelenti azt, hogy átment bizonyos tesztek által előírt spec. Néha mi nem mentesíti ellenőrzéseket. Például, detektívregény egyik aspektusa Pset 4, az a fajta kiábrándító, ha Önnek a választ, hogy mi az, és van számos módon, hogy felfedje aki az érintett személy, hogy a piros a zajt. A spec mindig meghatározza a jövőben Pset 5-től kezdődően milyen ellenőrzi létezik az Ön számára. Észre fogod venni, van ez a fehér URL alján. Most, ez csak a diagnosztikai kimenet. Ha felkeresi az URL, akkor kap egy csomó őrült, rejtélyes üzenetek hogy te szívesen, hogy nézze át, de ez leginkább a személyzet hogy tudjuk diagnosztizálni és hibakeresést hibákat check50 magát. 

Felhajtás nélkül, menjünk tovább, ahol abbahagytuk. CS50 könyvtár vettük adottnak néhány hétig, de aztán a múlt héten kezdtük bontsa fel az egyik réteg is. Elkezdtünk félretéve húr mellett mi helyett? [Diákok] Char. Char *, amely már a char *, egész idő alatt, de most már nem kell úgy tenni, mintha ez egy tényleges adatok string típusú. Inkább ez egy szinonimája a fajta a char *, és egy sor olyan karaktersorozat, miért van értelme, hogy képviselje karakterláncokat char * s? Mit jelent a char * képviselik az összefüggésben ez a fogalom egy string? Aha. >> [Student] Az első karakter. Jó, az első karakter, de nem egészen az első karakter. Ez a [Diákok] Cím. Jó, a cím az első karaktert. Minden, ami van szükség ahhoz, hogy egy string a számítógép memóriájában csak egyedi címét legelső bájt. Még csak nem is kell tudni, hogy meddig van mert hogyan lehet kitalálni, hogy ki dinamikusan? [Student] karakterlánc hosszát. Hívhatja string hossza, a kiváló, de hogyan működik string hossza működik? Mit tegyek? Igen. [Student] Folytasd, amíg nem kap a null karakter. Igen, pontosan, csak megismétli a for ciklus, míg a hurok, függetlenül a * a végéig, és a végén képviselteti magát a \ 0, az úgynevezett nul karakter, NUL, nem szabad összetéveszteni a null, amely egy mutató, ami jön a beszélgetés ma ismét. 

Mi hámozott vissza egy réteg getInt, aztán vett egy pillantást getString, és emlékeztetnek arra, hogy a két említett funkció, vagy tényleg, GetString volt egy bizonyos funkció hogy ténylegesen értelmezni, azaz, olvasni vagy elemezni, a felhasználó bemenet. És mi volt, hogy az új funkció? Scanf vagy sscanf. Valójában jön néhány különböző ízek. Van scanf, ott sscanf, ott fscanf. Most azonban nézzük összpontosítanak az egyik legkönnyebben látható, és hadd menjen előre, és nyissa fel a készüléket egy fájlt, mint ez, scanf1.c. Ez egy szuper egyszerű program, de ez nem olyasmi, amit soha nem csináltam segítsége nélkül a CS50 könyvtár. Ez kap egy int a felhasználó. Hogyan működik? Nos, sorban 16 van, észre, hogy állapítsa int hívott x, és ezen a ponton a történet, mi az x értéke? [Hallhatatlan hallgatói válasz] [David M.] Jobb, ki tudja, néhány szemét érték lehetséges, tehát a 17, csak mondd a felhasználó adjon nekem egy számot, kérem, és a 18 lépésben, ahol nem lesz érdekes. Scanf úgy tűnik, hogy kölcsön egy ötlet printf annyiban, hogy használja ezeket a formátumot kódokat idézetek. % D természetesen egy decimális szám. De miért vagyok halad és x helyett csak x? Az előbbi helyes. Igen. [Hallhatatlan hallgatói válasz] Pontosan, ha a cél a program, mint a funkció getInt maga van, hogy kap egy int a felhasználói tudom átadni funkciók az összes változót akarok, de ha nem adja át őket hivatkozással vagy a cím vagy a mutató, Az összes szinonim a mai célra, akkor ez a funkció nem képes megváltoztatni a tartalmát a változó. Ez át egy példányát, mint a buggy verzió csere hogy már beszéltünk néhányszor most. 

De ahelyett, ezzel & x, én szó szerint halad, mi? [Student] A cím. >> A címe x. Ez olyan, mint rajz egy térkép a nevezett funkció scanf és azt mondja: itt, ezek irányokat egy darab memória a számítógép hogy mehetsz tárolni néhány integer be Annak érdekében, hogy sscanf, hogy most csinálni mi üzemeltető milyen darab szintaxis fog ez kell használni bár nem látjuk, mert valaki más írta ezt a funkciót? Más szóval - mi az? [Student] X olvasni. Ott lesz némi olvasás, de csak tekintettel x itt. Ha a scanf kerül át a címét x, szintaktikailag, mi üzemeltető köteles létezik valahol belül scanf végrehajtásának érdekében, hogy scanf ténylegesen írjon egy számot 2 és ezt a címet? Igen, a *. Emlékezzünk vissza, hogy a * mi dereference operátor, ami lényegében azt jelenti, hogy ott. 

Miután átadták a címet, mint a jelen esetben, scanf valószínűleg, ha tényleg körülnézett forráskódját, csinál * x vagy az azzal egyenértékű, hogy valóban megy, hogy a cím és a némi értéket is. Most, hogy mennyi scanf kapja bemenet a billentyűzet, akkor hullám kezünket ki ma. Csak feltételezzük, hogy az operációs rendszer lehetővé teszi, hogy beszéljen sscanf a felhasználó billentyűzet, de ezen a ponton már sorban 19, amikor egyszerűen csak ki kell nyomtatni, x, úgy tűnik, hogy a helyzet hogy a scanf hozta int x-ben. Pontosan hogyan scanf működik, és emlékszem a múlt héten hogy pontosan hogyan getString és getInt és más családi feladatok végül is működik, bár némi eltérés, mint a sscanf, ami azt jelenti, beolvasni egy sor helyett a billentyűzetet. De vessünk egy pillantást egy kis variancia ezt. Az scanf2, én tényleg elcsesztem. Mi lehet a baj, és én leszek elrejteni a megjegyzést, hogy magyarázza a sok- mi a baj ezzel a programmal, version 2? Légy technikai lehető ebben az időben. Úgy néz ki, nagyon jó. Ez szépen tagolt, but- Oké, mit szólnál mondjuk szilva le rövidebb kérdése? Vonal 16. Mit csinál sor 16 pontos, de a műszaki angolul? Kicsit kínos. Igen, Michael. [Student] Ez mutat az első betű a string. 

Oké, közeli. Hadd csípés, hogy egy kicsit. Rámutatva, hogy az első betű egy string, akkor nyilvánító nevű változó puffer hogy fog mutatni az első címe string, vagy inkább, hogy fog mutatni, pontosabban a karakter. Értesítés ez valójában nem mutat sehova, mert nincs értékadó operátor. Nincs egyenlőségjel, így minden, amit csinálsz, az elosztási változó hívott puffer. Előfordul, hogy 32 bitre, mert ez egy mutató, és a tartalmát puffer feltehetőleg végül tartalmazni fog egy címet a char, de most, mit jelent puffert tartalmaz? Csak egy hamis, ki tudja, néhány szemét érték, mert nem kifejezetten inicializálva, ezért nem szabad feltételezni semmit. Oké, most sor a 17-mit 17. sor csinálni? Lehet, hogy fog felmelegedni ezt. Ez nyomtat egy string, ugye? Ez kinyomtatja Karakterlánc kérem. 

18. sor a fajta ismerős most, hogy csak láttam egy variancia e de egy másik formátumot kódot, így 18. sor, azt mondod scanf itt a címét egy darab memória. Azt akarom, hogy cseng egy szövegben, mint vélelmezett% s, de a probléma az, hogy nem tettél egy pár dolgot itt. Mi az az egyik probléma? [Student] Meg próbál dereference egy null pointer. Jó, null vagy csak egyébként ismeretlen mutatók. Te átadása scanf egy címet, de most mondta egy perccel ezelőtt hogy erre a címre van némi szemét érték, mert valójában nem rendelheti el semmit, és így mondod scanf hatékonyan megy, hogy egy húr van, de nem tudjuk, hol van mégis, így valójában nem kiosztott memória puffer. Sőt, mit is nem is mond scanf? Tegyük fel, hogy ez egy darab memória, és nem volt szemét érték, de te még mindig nem mond scanf valami fontosat. [Student] Ahol amilyen valójában, a jelet. Jelet, így ebben az esetben, ez rendben van. Mivel a puffer már bejelentett egy mutatót a * darab szintaxis, nem kell használni ampersand mert ez már egy címet, de azt hiszem hallottam itt. [Student] Milyen nagy ez? Jó, hogy nem mondasz scanf milyen nagy ez a puffer, ami azt jelenti, még akkor is, ha volt egy puffer mutató, azt mondjuk scanf, hogy egy húr van, de itt lehet 2 byte, lehet, hogy 10 byte, ez lehet egy megabájt. Scanf fogalma sincs, és mivel ez egy darab memória feltehetőleg ez nem egy karakterlánc még. Ez csak egy szöveg, ha írsz karaktereket és a \ 0-tól, hogy a darab a memória. Most már csak néhány darab memória. Scanf nem fogja tudni, hogy mikor hagyja abba írásban, hogy a címet. 

Ha visszaemlékeznek néhány példát a múltban, ahol véletlenszerűen gépelt a billentyűzeten próbál egy puffer túlcsordulás, és beszélgettünk pénteken arról, hogy pontosan. Ha egy ellenség valahogy fecskendezi be a programba egy sokkal nagyobb szó vagy mondat vagy kifejezés, akkor várta is túllépték egy darab memória, ami rossz következményei, mint átveszi az egész programot is. Meg kell erősít ez valahogy. Hadd kicsinyítés és bemegy 3-as verzióját a program. Ez egy kicsit jobban. Ebben a verzióban észre a különbséget. A vonal 16, én megint nyilvánító változó nevű puffer, de mi van most? Ez egy sor 16 karakter. Ez jó, mert ez azt jelenti, hogy most mondani scanf itt van egy valódi darabja a memóriát. Akkor szinte gondolni tömbök, hogy a mutató most, annak ellenére, hogy valójában nem egyenértékűek. Majd másként viselkednek a különböző helyzetekben. De ez minden bizonnyal a helyzet, hogy puffer hivatkozás 16 összefüggő karakter, mert ez az, ami egy tömb és már néhány hete. 

Itt mondom scanf itt egy darab memória. Ez alkalommal, ez valójában egy darab memória, de miért van ez a program még kitermelhető? Mi a baj még? Mondtam adj 16 byte but- [Student] Mi történik, ha nem írják be a több mint 16? Pontosan, mi van, ha a felhasználó típus 17 karakter vagy 1700 karaktereket? Tény, hogy lássuk, mi nem utazásként át ezt a hibát most. Jobb, de nem tökéletes. Hadd menjek előre, és futtasd a make scanf3 összeállításához ezt a programot. Hadd futni scanf3, String kérem: hello, és úgy tűnik, hogy rendben lesz. Hadd próbáljam meg egy kicsit hosszabb, hello there. Oké, akkor hello there hogy van ma, az Enter billentyűt. Első ilyen szerencsés itt, mondjuk hello there hogy van. A francba. Oké, tehát szerencsénk volt. Lássuk, ha nem tudjuk kijavítani ezt. Nem, nem hagyom, hogy engem másolni. Próbáljuk meg újra. Rendben, készenlétbe. Meglátjuk, meddig tudok tettetni, hogy összpontosítson, miközben továbbra is ezt. A francba. Ez inkább a megfelelő, valóban. Ott vagyunk. Point készült. 

Ez kínos, bár ez is, ez is egyik forrása a nagy zűrzavar írásakor programok, amelyek a hibákat, mert mutatkoznak Csak néha néha. A valóság az, hogy még ha a kód teljesen megtört, lehet, hogy csak a teljesen megtört néha mert néha, alapvetően mi történik, az operációs rendszer oszt egy kicsit több memóriát, mint valóban szüksége van bármilyen okból, és így senki más nem használja a memória jobb után darab 16 karakter, így ha megy 17, 18, 19, mindegy, ez nem is olyan nagy ügy. Most, hogy a számítógép, akkor is, ha ez nem lezuhan ezen a ponton, esetlegesen használja byte szám 17 vagy 18 vagy 19 valami mást, ekkor az adatok, hogy tegye oda, de túl hosszú, fog kapni felülírja esetleg valamilyen más funkció. Ez nem feltétlenül fog érintetlenek maradnak, de ez nem feltétlenül okoz seg hiba. De ebben az esetben, végül bocsátott rendelkezésre elegendő karaktert hogy lényegében meghaladta a részes memória, és bumm, Az operációs rendszer azt mondta: "Sajnálom, hogy nem jó, szegmentálási hibát okozott." 

És lássuk most, ha mi marad itt a könyvtárban, észre, hogy én ezt a fájlt itt, mag. Figyeljük meg, hogy ez ismét hívják core dump. Ez lényegében egy fájl, amely tartalmazza a tartalmát a program memóriájában azon a ponton, ahol lezuhant, és csak hogy megpróbálja egy kis példa erre engedj ide és fuss gdb szóló scanf3 majd adja meg a harmadik érv az úgynevezett mag, , és vegyük észre, hogy itt, ha felsorolom a kódot, képesek leszünk a szokásos módon gdb kezdeni séta ezt a programot, és tudok futni, és amint hit-mint a lépés parancsot gdb- amint megüt a potenciálisan hibás sor beírása után egy hatalmas string, Én képes lesz azonosítani a ténylegesen itt. Többet erről, bár szakaszában szempontjából core dump és hasonlók, így valóban piszkálni körül belül a core dump és nézd meg, hogy mi sorban a program nem neked. Van még kérdése majd a mutató és a címeket? Mert ma, megyünk elkezdi magától értetődőnek, hogy ezek a dolgok léteznek és pontosan tudjuk, mik azok. Igen. 

[Student] Hogyhogy nem kellett volna véget jelet közvetlenül a part- Jó kérdés. Hogy lehet, hogy nem kellett, hogy véget jelet közvetlenül a karakter tömb, mint én tettem korábban A legtöbb példát? A rövid válasz tömbök egy kicsit különleges. Akkor szinte gondolja puffer ténylegesen, hogy egy címet, és ez csak azért történik, hogy a helyzet, hogy a szögletes zárójel jelölés a kényelem, hogy mi is bemegy konzol 0, konzol 1, konzol 2, anélkül, hogy használja a * jelölést. Ez egy kicsit a fehér hazugság, mert tömbök és mutatók vannak, sőt, egy kicsit más, de ezek gyakran, de nem mindig felcserélhetők. Röviden, ha egy funkció vár egy mutatót egy darab memória, akkor sem adja át a címet, hogy visszatért a malloc, és meglátjuk malloc előtt ismét hosszú, vagy tudod átadni a nevét egy tömb. Nem kell tennie jelet a tömbök, mert már lényegében hasonló címek. Ez az egyetlen kivétel. A szögletes zárójelek teszi őket különlegessé. 

Tudna tenni egy jelet közvetlenül a puffer? Nem ebben az esetben. Ez nem működik, mert újra, ezen sarok ügy ahol a tömbök nem egészen valójában címeket. De majd talán jön vissza, hogy nemsokára más példákkal. Próbáljuk meg megoldani a problémát itt. Van egy adatstruktúra, hogy már használ egy ideje ismert, mint egy tömb. Case pont ez az, amit mi csak volt. De tömbök néhány upsides és hátrányai. A tömbök szép miért? Mi az az egy dolog, hogy tetszik-a, amennyiben tetszik tömbök-körülbelül tömbök? Mi van a kényelmes róluk? Mi vonzó? Miért bemutatjuk őket az első helyen? Igen. [Student] Ez lehet tárolni egy csomó adat, és nem kell használni az egész dolog. Használhatja a szakaszt. Jó, egy sor tudod tárolni egy csomó adat, és nem feltétlenül kell használni az egészet, így overallocate, ami lehet kényelmes, ha nem tudja előre, hogy hány valami számíthat. 

GetString egy tökéletes példa. GetString, írta nekünk, fogalma sincs, hogy hány karakter lehet várni, így az a tény, hogy mi lehet kiosztani darabokat összefüggő memóriaterületet jó. Array is megoldani a problémát láttunk egy pár héttel ezelőtt már ha a kód elkezd ruházni valami nagyon rosszul tervezték. Emlékezzünk vissza, hogy hoztam létre egy diák struktúrát nevű David, és akkor ez valójában egy alternatív, mégis, hogy miután egy változó nevű nevet és egy másik változó nevű, azt hiszem, ház, és egy másik nevű változó ID mert az ilyen történet, amit aztán akartam bemutatni valami mást mint Rob a program, így aztán úgy döntöttem, várj egy percet, Meg kell nevezni ezeket a változókat. Hívjuk az enyém name1, ID1, house1. Hívjuk Rob name2, house2, ID2. De aztán várj egy percet, mi van Tommy? Aztán volt még három változó. Bemutattuk valaki más, négy készlet változók. A világ elkezdett rendetlen nagyon gyorsan, így bevezetett struktúrákat, és mi kényszerítő egy struct? Mit jelent a C struct segítségével csinálni? Ez tényleg kínos ma. Mi az? >> [Hallhatatlan tanulói válasz] Igen, konkrétan typedef lehetővé teszi, hogy hozzon létre egy új adattípus, és struct, a struct kulcsszó lehetővé teszi, hogy magukba fogalmilag kapcsolódó darab adatokra majd hívja őket valami, mint egy diák. 

Ez jó volt, mert most már tudjuk modellezni sokkal inkább egyfajta fogalmi következetes fogalma egy diák egy változó ahelyett önkényesen, amely egy egy húr, egy pedig az azonosítót, és így tovább. A tömbök szép, mert lehetővé teszi, hogy indítsa el a tisztítási kódot. De mi a hátránya már egy tömb? Mit nem? Igen. [Student] Tudnod kell, milyen nagy. Tudnod kell, milyen nagy, tehát ez egyfajta fájdalom. Akik ezt a korábbi programozási tapasztalattal tudjuk, hogy sok nyelven, mint a Java, akkor kérheti egy darab memória, konkrétan egy tömb, milyen nagy vagy te, hossza, vagyoni helyzet, hogy úgy mondjam, és ez nagyon kényelmes. A C-ben, akkor nem is szükséges strlen egy generikus tömb mert strlen, ahogy a szó is mutatja, csak a húrok, és tudod kitalálni, hogy a string hossza, mert ez az emberi egyezmény létrehozandó \ 0, hanem egy sor, több általánosságban, csak egy darab memória. Ha ez egy sor ints, ott nem lesz néhány speciális karakter a végén vár rád. Meg kell emlékezni a hossza egy tömb. Másik hátránya a tömb nevelt a fejét getString magát. Mi van a másik hátránya egy tömb? Uram, csak te és én ma. [Hallhatatlan diák válasza] >> Ez mi? Ez nyilvánította a verem. Oké, kijelentette, a verem. Miért nem tetszik? [Student] Mert ez lesz újra. Ez lesz újra. Oké, ha használ egy tömböt a memóriát, nem lehet, például vissza, mert ez a verem. Oké, ez a hátrány. És mi a helyzet egy másik egy sor? Ha fel kell osztaniuk azt, te milyen csavaros, ha több helyre van szüksége mint a tömb. 

Aztán bevezette visszahívás, malloc, amely alkalmat adott nekünk a lehetőséget, hogy dinamikusan memóriát. De mi van, ha próbált egy másik világ összesen? Mi lenne, ha volna megoldani egy pár e problémák így ahelyett, tollam elaludt a továb- mi lenne, ha inkább akart lényegében létrehozni egy olyan világban, ami már nincs, mint ez? Ez egy tömb, és, természetesen, ez a fajta rontja, ha elérjük a végén a tömb, és most már nincs hely a másik integer vagy egy másik karaktert. Mi lenne, ha valami megelőző jellegű jól mondjátok, miért nem megyünk pihenni ez a követelmény, hogy mindezek darabokat memória legyen szomszédos háttal, és miért nem, amikor szükség van egy int vagy char, csak adj helyet közülük? És amikor szükségem van egy másik, adj még egy hely, és amikor szüksége van egy másik, adj még egy helyet. Az előnye, hogy ami most van, hogy ha valaki más veszi a memória ide, nem nagy ügy. Elviszem ezt a kiegészítő darab memória van, majd ezt. 

Most, az egyetlen fogás az, hogy ez majdnem olyan, mint én egy csomó különböző változók. Ez olyan, mintha öt különböző változók potenciálisan. De mi van, ha lopni egy ötlet húrok amely valahogy kapcsolni ezeket a dolgokat együtt fogalmilag, és mi van, ha én ezt? Ez az én nagyon rosszul húzott nyíl. De tegyük fel, hogy minden ilyen darabokat memória rámutatott arra, hogy a másik, és ez a fickó, aki nem az ő testvére van, nincs ilyen nyíl. Ez valójában az úgynevezett láncolt listát. Ez egy új adatszerkezet, amely lehetővé teszi számunkra, hogy fordítsanak egy darab memória, aztán egy másik, aztán egy másik, majd egy másik, bármikor szeretnénk közben a program, és ne feledjük, hogy mindannyian valahogy kapcsolódó szó szerint láncolás őket, és mi tette ezt piktogramokat ábrázoló itt egy nyíllal. De kódot, mi lenne a mechanizmus, amelyen keresztül meg tudná valahogy kapcsolódni, majdnem olyan, mint Scratch, az egyik darab egy másik chunk? Jól jönne egy mutató, igaz? Mert valóban a nyíl, ami megy a bal felső négyzet, ez a fickó itt ezt, is tartalmazhatnak belül ezen a téren nem csak egy ints, nem csak néhány karakter, de mi van, ha ténylegesen kiosztott egy kis extra helyet úgy, hogy most, Minden az én darabokat a memória, annak ellenére, hogy ez fog kerülni nekem, Most úgy néz ki, egy kicsit több téglalap alakú, ahol az egyik a darabokat memória használják egy számot, mint az 1-es szám, és ha ez a fickó tárolja a 2-es szám, ez a másik darab memóriát használja a nyíl, vagy több konkrét, a mutató. És hiszem, tárolja a 3-as szám alatt van, míg én ezt hangsúlyozni azt a fickót, és most ez a fickó, tegyük fel, csak azt akarom, három ilyen darabokat memória. Majd húzzunk egy vonalat ezen keresztül, jelezve null. Nincs további karakter. 

Valóban, ez hogyan mehetünk végrehajtásával kapcsolatban valamit, hívják láncolt lista. A láncolt lista egy új adatszerkezetet, valamint ez egy lépcsőfok felé sok szakértő adatszerkezeteket kezdődő problémákat megoldani mentén Facebook-típusú problémák és a Google-típusú problémák ahol hatalmas adathalmazokat, és már nem vágja azt tárolni mindent összefüggően és használja valami ilyesmit lineáris keresés vagy akár valami hasonló bináris keresés. Akarsz még jobb üzemidő. Sőt, az egyik a Szent Grails fogunk beszélni később ezen a héten, vagy a következő egy algoritmus, amelynek futási ideje állandó. Más szóval, azt mindig veszi az ugyanannyi ideig nem számít mekkora a bemenet, és ez valóban lenyűgöző, sokkal inkább, mint valami logaritmikus. Mi ez a képernyőn itt? Minden egyes téglalapok pontosan én csak rajzoltam kézzel. De a dolog egészen a bal oldalon egy speciális változó. Ez lesz az egyetlen mutató, mert az egyik megvagy egy láncolt lista, mert ezeket a dolgokat nevezik, az, hogy meg kell ragaszkodni egyik végét a csatolt listán. 

Csakúgy, mint a húr, akkor tudja a címet az első karakter. Ugyanez a helyzet a linkelt listákat. Meg kell tudni, hogy a címe az első darab memória mert onnan, el lehet jutni minden más egy. Downside. Milyen árat fizetünk erre sokoldalúságát, amelyek egy dinamikusan méretes adatszerkezet, hogy ha valaha is szüksége több memóriát, finom, csak kiosztani még egy darab, és rajzoljon egy mutatót A régi és az új farok a lista? Igen. [Student] Ez körülbelül kétszer annyi helyet. Beletelik kétszer annyi helyet, így ez biztosan egy hátránya, és láttuk ezt kompromisszum előtt közötti időben és térben és rugalmasság ahol az most már nem kell 32 bit minden egyes ezeket a számokat. Tényleg szükségünk van 64, 32 és 32 a száma a mutatót. De hé, van 2 GB RAM. Hozzáadása egy 32 bit itt és itt nem úgy tűnik, hogy nagy ügy. De a nagy adathalmazok, akkor biztosan tesz ki szó szerint kétszer annyi. Mi van a másik hátránya most, vagy mi a funkció nem adjuk fel, ha az általunk képviselt listák dolgok egy láncolt lista, és nem egy tömb? [Student] Nem lehet keresztezik visszafelé. Nem lehet, hogy visszafelé haladnak, szóval egyfajta csavaros ha séta balról jobbra egy for ciklus vagy while majd rájössz, hogy "Ó, azt akarom, hogy menjen vissza az elején a listát." Nem lehet, mert ezek a mutatók csak megy balról jobbra, mint a nyilak jelzik. 

Most vissza tudott emlékezni a kezdete a lista egy másik változó, de ez egy bonyolult, hogy tartsa szem előtt. Egy tömb, nem számít, milyen messze megy, akkor mindig mínusz, mínusz, mínusz, mínusz és menj vissza, ahonnan jöttél. Mi van még egy hátránya itt? Igen. [Hallhatatlan diák a kérdéshez] Lehet, így már valójában csak javasolta adatszerkezetet úgynevezett kétszeresen láncolt lista, és valóban, akkor újabb mutatót minden egyes ilyen téglalap hogy megy a másik irányba, a fejjel, amely most akkor keresztezik oda-vissza, a hátránya, amely most az Ön által használt háromszor annyi memóriát szoktuk és fokozza a rendszer bonyolultságát tekintve a kódot kell írni, hogy ez jobb. De ezek mind talán nagyon ésszerű kompromisszumok, ha a visszaírás fontosabb. Igen. [Student] Azt is nem egy 2D linkelt listát. Jó, akkor nem igazán van a 2D láncolt lista. Te igen. Ez közel sem olyan egyszerű, mint egy tömb. Mint egy tömb, te nyitva tartó, zárt konzol, nyitó zárójel, zárt konzol, és egy kis 2-dimenziós szerkezet. Lehet végre a 2-dimenziós láncolt lista ha nem a kiegészítő, amit javasolt, 1/3 mutatót minden egyes ezeket a dolgokat, és ha belegondolsz másik lista jön rád 3D stílusú A képernyőn mindannyiunk, ami csak egy lánc valami. Tudnánk csinálni, de ez nem olyan egyszerű, mint gépelés nyitó zárójel, szögletes zárójel. Igen. [Hallhatatlan diák a kérdéshez] Jó, tehát ez egy igazi kicker. 

Ezek az algoritmusok, hogy már epekedett, ss felett, mint oh, bináris keresés, akkor kereshet egy sor számok a fedélzeten vagy egy telefonkönyv sokkal gyorsabban, ha használja oszd meg és uralkodj és a bináris keresés algoritmus, de bináris keresés szükséges két feltételezéseket. Az egyik, hogy az adatok rendezve. Most már valószínűleg tartani ezt a rendezett, így talán ez nem ad okot aggodalomra, hanem bináris keresés is feltételezik hogy volt véletlen elérésű a számokat tartalmazó listát, és egy sor lehetővé teszi, hogy véletlen hozzáférést, és véletlenszerű hozzáférés, Úgy értem, ha adott egy tömb, mennyi időbe telik Önnek hogy a konzol 0-ra? Egy művelet, csak a [0], és igazad van. Hány lépést tart, hogy a hely 10? Egy lépés, csak menjen a [10], és ott vagy. Ezzel szemben, hogyan kap a 10. egész egy láncolt lista? Meg kell kezdeni az elején, mert te csak az emlékezés az elején egy láncolt lista, mint egy string kerül emlékeznek a címe az első karakter, és megtalálják, hogy a 10. int vagy 10. karakter egy string, meg kell keresni az egész átkozott dolgot. 

Ismét nem vagyunk megoldani az összes problémánkat. Mi újak bevezetésével, de valójában attól függ, hogy mit akarsz, hogy tervezzen számára. Ami a végrehajtására, akkor kölcsönt egy olyan elképzelést, hogy a diákok szerkezet. A szintaxis nagyon hasonló, kivéve most, az ötlet egy kicsit elvont mint a ház és neve és azonosítója. De azt javaslom, hogy volna egy adatstruktúra a C hogy az úgynevezett csomópont, az utolsó szó a dián sugallja, belül egy csomópont, és a csomópont csak egy általános tároló számítógép-tudomány. Ez általában húzott, mint egy kör vagy négyzet vagy téglalap, ahogy tettem. És ebben adatszerkezet, van egy int-, n, annak érdekében, hogy ez a szám szeretnék tárolni. De mi ez a második sorban, struct node * a következő lépés? Miért van ez így helyes, vagy milyen szerepet tölt be ez a dolog játék, annak ellenére, hogy egy kicsit rejtélyes első pillantásra? Igen. [Hallhatatlan hallgatói válasz] Pontosan, így a * fajta zsákmány, hogy ez a mutató valami. A neve ennek a mutató önkényesen következő, de mi volna neveztük, amit akarunk, de mit jelent ez a mutató pont? [Student] Egy másik csomópont. >> Pontosan, rámutat egy másik ilyen csomópont. 

Nos, ez egyfajta kíváncsiság C. Emlékezzünk vissza, hogy a C olvas egy fordító felülről lefelé, balról jobbra, ami azt jelenti, ha-ez egy kicsit más, mint amit tettünk a diák. Amikor meghatározta a hallgató, mi valójában nem tettem egy szót is. Csak azt mondta typedef. Aztán volt int id, string name, string ház, majd a diák alján a struct. Ez a nyilatkozat egy kicsit más, mert ismét a C fordító egy kicsit buta. Ez csak akkor fog olvasni fentről lefelé, így ha az eléri a 2. vonalat itt ahol a következő nyilvánították, és lát, ó, itt van egy változó neve mellett. Ez egy mutató egy struct csomópont. A fordító fog megvalósítani, ami egy struct csomópont? Még soha nem hallottam ezt a dolgot korábban, mert a szó csomópont egyébként nem jelenik meg amíg az alsó, így van ez a redundancia. Azt kell, hogy mondjam struct node itt, amit aztán rövidebb később köszönhetően typedef ide, de ez azért van, mert mi hivatkozó maga a szerkezet belsejében a szerkezet. Ez az egyetlen megvagy ott. 

Néhány érdekes problémákat megy fel. Van egy listát a számok. Hogyan helyezze bele? Hogyan keressük meg? Hogyan törölni belőle? Különösen most, hogy kell kezelni az összes ilyen mutató. Azt hitted mutatópálcák valamiféle pszichedelikus mikor volt az egyik közülük csak próbál olvasni int rá. Most, hogy manipulálják az egész listát ér. Miért nem vesszük 5-perces szünet van, és aztán, hogy Egyes emberek a színpadon, pontosan erre. 

C sokkal szórakoztatóbb, ha ez cselekedett. Ki szó lenni az első? Oké, gyere fel. Te itt először. Ki szeretne lenni 9? Oké, 9. Mit szólnál 9? 17? Egy kis klikk ide. 22 és 26, hogy első sorban. És akkor mi van valaki ott van mutatott. Te itt 34. Oké, 34, gyere fel. Először is ott van. Oké, mind a négy srácok. És ki nem mondjuk a 9? Ki az a 9? Aki igazán akar lenni 9? Rendben, gyerünk, légy 9. Itt vagyunk. 34, akkor találkozunk ott. Az első rész magatokat kinézni. 26, 22, 17, jó. Ha tud állni ki az oldalra, mert fogunk malloc téged egy pillanatra. 

Jó, jó. Oké, kitűnő, úgyhogy feltenni néhány kérdést itt. És valóban, mi a neve? >> Anita. Anita, oké, gyere ide. Anita fog segíteni nekünk a fajta megoldja az egyik viszonylag egyszerű kérdésre az első, ami hogyan találja-e vagy sem egy érték szerepel a listán? Most, észre, hogy az első, képviseli itt Lucas, egy kicsit más, és így a papírt szándékosan oldalra mert nem annyira magas, és nem vesz fel annyi bit, annak ellenére műszakilag ő az azonos méretű papír csak forog. De ő egy kicsit más, hogy ő csak a 32 bit a mutató, és minden ezek a srácok 64 bit, amelynek a fele a szám, amelynek a fele a mutató. De a mutató nem látható, így ha ti is kissé esetlenül használja a bal oldali pont a személy, melletted. És te száma 34. Mi a neve? Ari. Ari, így valójában, tartsa a papírt a jobb, és a bal oldali egyenesen lefelé. Ön képviseli null a bal oldalon. 

Most a mi emberi kép nagyon következetes. Ez valójában milyen mutatókat dolgoznak. És ha szétmorzsol egy kicsit így, nem vagyok az utat. Anita itt találja meg a szám 22, de feltételezik a kényszer nem emberek feltartotta darab papír, de ez a lista, és már csak Lucas kezdeni azért, mert szó szerint az első mutatót. Tegyük fel, hogy te magad vagy a mutató, és így is van a képessége, hogy mutasson valamit. Miért nem indul el a mutatott pontosan Lucas mutat? Jó, és hadd hozzanak ezt meg itt. Csak kedvéért vita, hadd húzza fel egy üres oldal van. Hogyan pontosan a nevét? >> Anita. Oké, Anita. Mondjuk node * anita = Lucas. Nos, nem kell hívni Lucas. Meg kell hívni az első. Miért van ez valójában összhangban a valósággal itt? Az egyik első már létezik. Gyártási különítettek feltehetően valahol itt. Node * az első, és ez már kiosztott egy listát valahogy. Nem tudom, hogyan történt. Ez történt óra előtt kezdődött. A láncolt lista az emberek hoztak létre. És most, ezen a ponton a történet, ez minden megy a Facebook látszólag később Ezen a ponton a történet, Anita már inicializálva meg kell egyeznie az első, ami nem jelenti azt, hogy Anita pontokat Lucas. Inkább, ő mutat, hogy mit is mutat a mivel az ugyanazt a címet, ami belül Lucas 32 bit - 1, 2, 3 - most is belül Anita 32 bit - 1, 2, 3. 

Most találni 22. Hogyan megy a csinálod ezt? Mi ez? >> Point mindegy. Mutasson mindegy, így megy előre, és úgy járnak ki a lehető legjobban tudod itt. Jó, jó, és most mutat, mi a neve, 22? Ramon. >> Ramon, így Ramon is feltartotta 22. Most már végeztek ellenőrzést. E Ramon == 22, és ha igen, például, meg tudjuk vissza igaz. Hadd, míg ezek a srácok itt állni kissé félszegen, hadd tegyen valamit gyorsan, mint a bool találni. Én megyek előre, és azt mondják (node ​​* lista, int n). Mindjárt vissza srácok. Csak ki kell írni egy kódot. És most megyek előre, és ezt, node * anita = listáját. És én megyek előre, és azt mondják while (anita! = NULL). 

A metafora itt egy kicsit feszített, de míg a (anita! = NULL), mit szeretnél csinálni? Kell valamilyen módon hivatkozás az egész, hogy az Anita mutat. A múltban, mikor volt struktúrákra, és amely egy csomópont, használtuk a dot jelölést, és azt mondanám, valami ilyesmit anita.n, de a probléma az, hogy Anita nem egy struct önmagában. Mi ő? Ő egy mutató, tehát tényleg, ha azt akarjuk, hogy ezt a dot-jelölést és ez fog nézni szándékosan egy kicsit rejtélyes, tennünk kell valamit, mint megy, amit Anita bal keze mutat és akkor kap a mező nevű n. Anita egy mutató, de mi * anita? Mit talál, ha megy, amit Anita is mutat? A struct, egy csomópont és egy csomópont, visszahívás, egy mező nevű n mert, emlékszem, ezek a 2 területen, a következő és az n, hogy láttunk egy pillanattal ezelőtt itt. 

Ahhoz, hogy ténylegesen utánozni ezt a kódot, tudtuk ezt, és azt mondják if ((* anita). n == n), n, hogy én keresem. Figyeljük meg, hogy a függvény vezetünk be a számot törődöm. Aztán lehet menni előre, és valami ilyesmit vissza igaz. Különben, ha nem ez a helyzet, mit szeretnél csinálni? Hogyan fordíthatom a kódot, amit Anita megtette intuitív gyalog végig a listát? Mit kell tennem ide, hogy szimulálják Anita megtegyék ezt a lépést a bal oldalon, hogy a lépés a bal? [Hallhatatlan diák válasza] >> Mi ez? [Hallhatatlan hallgatói válasz] Jó, nem egy rossz ötlet, de a múltban, amikor csináltam ezt, tettünk anita + + mert ez növelné az 1-es számot Anita, ami jellemzően pont a következő személy, mint Ramon, vagy az a személy mellé, vagy a mellé személynek le a pályáról. De ez nem elég jó itt, mert mit jelent ez a dolog néz ki, mint a memória? Nem. Meg kell tiltani, hogy a. Úgy tűnik ez a memóriában, és bár én már húzott 1-es és 2 és 3 egymáshoz közel, ha valóban ez-szimulálni lehet nektek, miközben mutatva ugyanazok az emberek, lehet néhány veszel egy véletlen lépést hátra, néhányan egy véletlenszerű előrelépést? 

Ez a káosz még mindig láncolt lista, de ezek a srácok bárhol lehet a memóriában, így anita + + nem fog dolgozni, miért? Mi van a helyszínen anita + +? Ki tudja. Ez valami más értéket, hogy csak azért történik, hogy közbelépett az összes ilyen csomópont véletlenül, mert mi nem használ egy tömböt. Mi kiosztott mindegyik csomópont külön-külön. Oké, ha ti is tiszta magatokat vissza. Hadd javaslom, hogy ahelyett, hogy anita + +, akkor inkább nem anita kap- jól, miért nem megyünk, amit Anita mutat meg, majd tegye. következő? Más szóval, megyünk Ramon, aki tartja a szám 22, majd. következőig mintha Anita lenne másolás bal keze mutató. De ő nem megy tovább, mint Ramon, mert találtunk 22. De ez lenne az ötlet. Nos, ez egy istenverte rendetlenség. Őszintén szólva, soha senki nem fog emlékezni a szintaxist, és így szerencsére ez valójában egy kicsit szándékos-oh, akkor valójában nem lát, amit írtam. Ez lenne vonzóbb, ha lehet. Voila! 

A színfalak mögött, én oldja meg a problémát így. Anita, hogy ezt a lépést a bal oldalon, először, mi megy a cím Anita mutat a és hol fog találni nem csak n, amit csak ellenőrizni összehasonlítás kedvéért, de akkor is talál next - ebben az esetben, Ramon bal keze mutató a következő csomópont a listában. De ez az isten, szörnyű rendetlenség, amelyre utaltam korábban, de kiderül, C lehetővé teszi számunkra, egyszerűsítése. Ahelyett, hogy az írás (* anita), akkor helyette csak annyit írj anita-> n, és ez pontosan ugyanaz a dolog funkcionálisan, de ez sokkal intuitívabb, és ez sokkal inkább összhangban van a kép, hogy mi már rajz Mindez időt nyilak. 

Végül, mit kell tennünk a végén ez a program? Van egy sor kódot maradt. Vissza mi? Hamis, mert ha megkapjuk az egész while ciklus és Anita valójában, null, ez azt jelenti, ment egészen a végén a jegyzék ahol ő volt mutatva, mi a neved? Ari. >> Ari bal keze, amely a null. Anita most null, és rájövök te csak itt állok félszegen bizonytalanságban mert én megyek ki egy monológ itt, de majd vonni újra egy pillanat. Anita null ezen a ponton a történet, így a while ciklus befejeződik, és mi vissza hamis, mert ha megkapta egészen Ari null pointer akkor nem volt több, hogy ő kérte a listán. Mi lehet tisztítani az egészet is, de ez egy nagyon jó végrehajtás, akkor A bejárás függvény, a függvény megtalálja a láncolt lista. Még mindig lineáris keresés, de ez nem olyan egyszerű, mint + + egy mutatót + + vagy egy i változó, mert most nem tudunk kitalálni ahol mindegyik csomópont a memóriában. Meg kell, hogy szó szerint követni a nyomát zsemlemorzsa, vagy még pontosabban, mutatók, hogy kap egy csomópont a másikkal. 

Most próbáljuk egy másikat. Anita, nem jössz vissza? Miért nem megyünk előre, és hozzá egy másik személy a közönség? Malloc-mi a neve? >> Rebecca. Rebecca. Rebecca már malloced a közönség, és ő most tárolja a számot 55. És a cél kéznél most az, hogy Anita beszúrni Rebecca a csatolt lista itt a megfelelő helyen. Gyere ide egy pillanatra. Tettem ilyesmit. Én megtettem node *. És mi a neved? Rebecca. >> Rebecca, oké. Rebecca kap malloc (sizeof (node)). Csakúgy, mint az általunk kiosztott dolgok, mint a diákok és miegymás a múltban, szükségünk van a méret a csomópont, így most Rebecca mutat, hogy milyen? Rebecca két területen belül vele, amelyek közül az egyik 55. Mit csináljunk, Rebecca-> = 55. De aztán rebecca-> next kellene-mint most, a kezét a fajta, ki tudja? Ez mutat néhány szemetet értéket, így miért nem jó intézkedés mi legalábbis ezt úgy, hogy a bal oldali most mellette. Most Anita, vegye innen. Van Rebecca miután kiosztották. Menj előre, és talál, ahol meg kell oldania Rebecca. Jó, nagyon jó. Oké, jó, és most szükségem van rád, hogy egy kicsit irányt, így elérte Ari. A bal kéz null, de Rebecca egyértelműen tartozik a jobb oldalon, tehát hogyan kell megváltoztatni ezt a láncolt lista annak érdekében, hogy be Rebecca a megfelelő helyet? Ha lehetne szó mozgatni ember bal keze körül, mint szükséges, fogjuk oldani a problémát így. Oké, jó, és közben, Rebecca bal keze már a lány mellett. 

Ez túl könnyű. Próbáljuk elosztásának haladhat-mi majdnem kész, 20. Oké, gyere fel. 20 került felosztásra, ezért hadd menjen előre, és megismétlem itt imént tett node * Saad. Van malloc (sizeof (node)). Ezután ugyanezt pontos szintaxist ahogy azelőtt 20, és én megteszem next = NULL, és most ez akár Anita beszúrni Önt a láncolt lista, ha játszhat, hogy pontosan ugyanazt a szerepet. Execute. Oké, jó. Most, gondolom, mielőtt elkezdené mozog bal kéz körül. Te messze van a leginkább kínos szerep ma. Kinek a keze kell helyezni az első? Oké, várj, hallok valami nincs években. Ha egyes emberek azt udvariasan szeretné, hogy segítsen megoldani egy kínos helyzet. Kinek a bal oldali frissíteni kell 1. talán? Igen. [Student] Saad években. Oké, Saad azon, miért, igaz? [Hallhatatlan hallgatói válasz] Jó, mert ha mozgunk, mi a neve? >> Marshall. Marshall, ha mozog a kezét first down null, most már szó szerint árva négy ember ebben a listában mert ő volt az egyetlen dolog, amit mutat Ramon és mindenki balra, úgy, hogy a frissítés mutató első volt rossz. Nézzük, hogy a visszavonás. Jó, és most megy előre, és mozgassa a megfelelő bal oldali mutatva Ramon. Ez úgy érzi, egy kicsit felesleges. Most van két ember mutatott Ramon, de ez rendben van mert most, hogy mást is frissíti a listát? Milyen más kéz mozogni? Nagyszerű, most már elvesztette memória? Nem annyira jó, lássuk, ha nem tudjuk megtörni ezt még egyszer. 

Mallocing egyszer, utoljára, 5-ös szám. Minden utat vissza, gyere le. Ez nagyon izgalmas. [Taps] Mi a neve? >> Ron. Ron, oké, akkor malloced mint 5-ös szám. Épp végrehajtandó kód, ami csaknem azonos e csak egy másik nevet. Kiváló. Most, Anita, sok szerencsét behelyezésénél 5-ös szám a lista most. Jó, és? Kiváló, így ez tényleg a harmadik három teljes esetben. Először volt valaki a végén, Rebecca. Meg aztán valaki a közepén. Most már valaki az elején, és ebben a példában, most frissíteni kellett Lucas először mivel az első elem a lista most pont egy új csomópont, aki viszont mutat at node szám 9. 

Ez egy rendkívül kínos tüntetés, biztos vagyok benne, így egy nagy tapsot ezeket a fickókat, ha lehet. Szép munka. Ez minden. Lehet, hogy tartsa a darab papírt egy kis memória. Kiderült, hogy ezt a kódot nem annyira egyszerű, mint csak mozgó kéz körül és rámutat mutatók különböző dolgokat. De észre, hogy amikor eljön az ideje, hogy végre valami hasonló egy csatolt lista vagy egy változata, ha Ön összpontosítani igazán Ezen alapvető fundamentumok, a harapás méretű problémát nekem kell kitalálni, ez a kéz vagy a kéz, rájönnek, hogy mi egyébként meglehetősen komplex program lehet, valójában, csökkenthető meglehetősen egyszerű építőelemek ilyen. 

Nézzük a dolgokat egy kifinomultabb irányba is. Most már fogalma a csatolt listán. Mi is, köszönhetően a javaslatot vissza-a kétszeresen láncolt lista, amely úgy néz ki, közel azonos, de most van két pointers belül a struct egy helyett, és valószínűleg hívni e mutatók előző és a következő vagy balra vagy jobbra, de mi valójában szüksége van kettő. A kód lenne egy kicsit nagyobb szerepet. Anita kellett volna több munkát itt a színpadon. De minden bizonnyal végre ezt a fajta szerkezet. Ami a működési idő, bár, mi lenne a futási idő az Anita találni számos n egy láncolt lista most? Még mindig nagy O n, így nem jobb, mint a lineáris keresés. Nem tehetünk bináris keresés, bár, újra. Miért volt ez a helyzet? Nem lehet ugrani. Annak ellenére, hogy nyilvánvalóan megtekinthet minden ember a színpadon, és Anita volna eyeballed, és azt mondta: "Itt van a közepén a lista" ő nem tudja, hogy ha ő volt a számítógépes program mert az egyetlen dolog, amit meg kellett reteszt, hogy az elején a forgatókönyv Lucas volt, aki az első mutatót. Ő feltétlenül követni ezek a kapcsolatok, számlálás a maga módján, amíg rájött nagyjából a közepén, és még akkor is, ő nem fogja tudni, hogy mikor ő érte el a középső hacsak nem megy egészen a végéig, hogy kitaláljuk, hogy hány van, akkor backtracks, és hogy túl nehéz lenne, ha nem volt kétszeresen láncolt lista valami. 

Egyes problémák megoldása ma, de bevezetése mások. Mi a helyzet a másik adatszerkezet összesen? Ez a fénykép a tálcákat Mather House, és ebben az esetben, hogy van egy adatstruktúra általunk is ilyen már beszélt. Beszéltünk egy köteg keretében memória, és ez a fajta szándékosan nevezték, mert egy halom feltételeiben memória gyakorlatilag egy adatszerkezet, amely egyre több és több dolgot rakott a tetején. De az érdekes dolog a verem, mint ahogy az a valóságban, az, hogy ez egy különleges fajta adatszerkezet. Ez egy adatstruktúra ahol az első elem az utolsó elem ki. Ha te vagy az első tálcát kell helyezni a verembe, te lesz sajnos az utolsó tálcát le kell venni a stack, és ez nem feltétlenül jó dolog. Ezzel szemben, akkor gondolj bele a másik irányba, az utolsó az első ki. 

Nos, akkor bármilyen forgatókönyv jöhetnek szóba, ahol amelynek stack adatstruktúra, ahol van, hogy az ingatlan Az utolsó, először ki, valójában lenyűgöző? Ez egy jó dolog? Ez egy rossz dolog? Ez feltétlenül egy rossz dolog, ha a tálcák nem voltak egyformák és ők minden speciális különböző színeket vagy miegymás, és a szín, amit szeretnék, végig az alján. Természetesen, ha nem tud, hogy a nagy erőfeszítés nélkül. Meg kell kezdeni a felső és a munka az utat lefelé. Hasonlóképpen, mi lenne, ha egy ilyen rajongó fiúk aki vár egész éjszaka próbál egy iPhone és egy vonalba egy olyan helyen, mint ez? Nem lenne jó, ha az Apple store volt egy halom adatszerkezetet? Yay? Nay? Ez csak arra jó, az emberek, akik megjelennek az utolsó lehetséges pillanatban majd kap kopasztott le a sorban. És valóban, az a tény, hogy én annyira hajlandó mondani queue valójában összhangban áll azzal, amit szeretnénk hívni az ilyen adatok struktúrája, egy a valóságban, ha a rendelés nem mindegy, és azt szeretné, az elsőt, hogy az első egyet ha csak a kedvéért az emberi tisztesség. Majd általában véve, hogy egy sort adatszerkezet. 

Kiderült mellett kapcsolódó listák, kezdhetjük ezekkel azonos alapvető elképzeléseket és meg kell kezdeni új és a különböző megoldásokat. Például abban az esetben, egy verem, akkor jelenthet egy verem egy adatstruktúra, mint ez, azt javaslom. Ebben az esetben, már bejelentett egy struct, és mondtam belül e struktúra egy tömb a számok, majd a változó nevű méret, és fogom hívni ezt a dolgot egy verem. Nos, miért ez tényleg működik? Abban az esetben, ha a verem, nem tudtam felhívni ezt hatékonyan meg a képernyőn, mint egy tömb. Itt van a verem. Azok az én szám. És mi lesz felhívni őket, mint ez, ez, ez, ez, ez. És aztán van néhány egyéb adat tagja van, amely az úgynevezett mérete, tehát ez a méret, és ez számok, és együttesen az egész iPad itt az egyik stack struktúrát. Most, alapértelmezés szerint mérete feltehetően kapott inicializálni kell 0-ra, és mi van benne a tömb a számok eredetileg amikor először osztja tömb? Garbage. Ki tudja? És ez valójában nem számít. Nem számít, hogy ez az 1, 2, 3, 4, 5, teljesen véletlenszerűen a balszerencse tárolt saját szerkezete, mert mindaddig, amíg tudom, hogy a méret a verem 0, akkor tudom, hogy programozottan, ne nézd meg bármelyik elem a tömbben. Nem számít, hogy mi van ott. Ne nézz rájuk, mint lenne a következménye, a mérete 0-ra. 

De tegyük fel, most megy előre, és helyezze valamit a verem. Azt akarom, hogy tegye be a 5-ös szám, ezért tettem 5-ös szám van, aztán mit tettem le ide? Most valójában letettem 1 a méret, és most a verem mérete 1. Mit tegyek, ha megy előre, és illessze be a számot, mondjuk 7 következő? Ez akkor frissül, 2 és aztán megteszem 9, és akkor ez frissül 3-ra. De az érdekes funkció már e verem, hogy a Kéne eltávolítani melyik eleme, ha azt szeretnénk, hogy a pop valamit le a verem, hogy úgy mondjam? 9 lenne az első dolog, hogy menjen. Hogyan kell a kép változik, ha azt akarom, hogy a pop egy elemet a veremből, sokkal, mint egy tálcát Mather? Aha. >> [Student] Teljes méret 2-re. Pontosan, minden, amit csinál van beállítva, méret 2, és mit tegyek a tömb? Nem kell tennie semmit. Tudtam, csak hogy anális, hogy egy 0 ott, vagy a -1 vagy valamit jelent , hogy ez nem egy legit érték, de ez nem számít, mert Tudok rögzíteni kívül magát a tömböt, hogy mennyi ideig van úgy, hogy tudom, csak nézd meg az első két eleme ezt a tömböt. Most, ha elmegyek és adjuk hozzá a 8-as szám az e tömb, hogyan változik a kép a következő lépés? Ez akkor válik 8, és ez lesz 3. Én egy pár vágás sarkok itt. Most már 5., 7., 8., és vagyunk vissza a mérete a 3. Ez elég könnyen megvalósítható, de mikor fogjuk bánni ezt a tervezési döntés? Mikor a dolgok kezdenek menni nagyon, nagyon rossz? Igen. [Hallhatatlan hallgatói válasz] Ha azt szeretné, hogy menjen vissza, és kap az első elemet teszel be 

Kiderült, hogy itt annak ellenére, hogy egy halom egy tömb, a motorháztető alatt, Ezen adatszerkezetek általunk elkezdett beszélni is általánosan ismert absztrakt adatszerkezetek amellyel hogyan ők végre teljesen kívül a lényeg. Egy adatszerkezet, mint egy köteg állítólag hozzá support műveletek, mint a push, ami emeli a tálcát a verembe, és a pop, amely eltávolítja az elemet a veremből, és ennyi. Ha úgy döntesz, hogy letölthető valaki más kódját, aki már megvalósult ezt a dolgot nevezett verem, ez a személy írt volna Csak a két funkciót az Ön számára, és nyomja meg a pop, amelynek egyetlen célja az életben lenne pontosan erre. Te vagy neki, aki végre, hogy a program lett volna teljesen az, aki dönt arról, hogyan kell a szemantika tolás és popping a motorháztető alatt vagy működésének toló és popping. És tettem egy kissé rövidlátó döntés ide végrehajtási én verem ezzel az egyszerű adatszerkezettel miért? Ha működik ez adatstruktúra szünetet? Mely pontján kell még egy hibaüzenet, amikor a felhasználó kéri push, például? [Student] Ha nincs több hely. Pontosan, ha nincs több hely, ha már túllépett kapacitásnak, amely a nagybetűs, mert azt sugallja, hogy ez valamiféle globális állandó. Nos, akkor én most megyek, hogy meg kell mondani, hogy "Sajnálom, nem tudok nyomja másik értéket a verembe, "nagyon hasonló a Mather. 

Egy bizonyos ponton, mennek, hogy elérje a felső része a kis szekrény. Nincs több hely vagy kapacitás a stack, mely ponton van valamilyen hiba. Meg kell tenni az elemet valahol máshol, a tálca valahol máshol, vagy sehol egyáltalán. Most, egy sorban, sikerült végre egy kicsit másképp. A sorban egy kicsit más, hogy a motorháztető alatt, akkor végre kell hajtani tömbként, de miért, ebben az esetben én javaslatot hogy is van fejelem képviselő a fejét a lista az első a listán, az első ember a sorban az Apple bolt, továbbá a méret? Miért van szükség egy további adat itt? Gondolj vissza, hogy milyen számok ha már lehívott az alábbiak szerint. Tegyük fel, hogy ez most a várólista helyett verem, a különbség, mint az Apple store-queue igazságos. Az első, aki sorban elején a jegyzék, 5. számú ebben az esetben, ő is fog beengedni a boltba először. Csináljuk ezt. Tegyük fel, hogy ez az állam az én sorban ebben a pillanatban, és most az Apple store megnyílik, és az első személy, 5-ös, vezetik be a boltba. Hogyan változtathatom meg a képet, most, hogy megszüntetjük sorban az első ember elején a vonal? Mi ez? >> [Student] Módosítsa a sorban. Változtassuk meg a fejét, így 5 eltűnik. Valójában, ez mintha-hogyan kell ezt csinálni? Valójában, ez mintha ez a fickó eltűnik. Mi lenne 7-es számú teendő tényleges boltban? Ők, hogy egy nagy lépést előre. 

De mit értünk jött, hogy értékeljék, amikor a tömbök és a mozgó dolgok körül? Ez egyfajta hulladék az idejét, ugye? Miért kell ilyen anális, mint hogy az első ember elején a vonal fizikailag kezdetét a darab memória? Ez teljesen felesleges. Miért? Mi lehet Csak arra emlékszem, helyette? >> [Hallhatatlan tanulói válasz] Pontosan tudtam, csak emlékszem, hogy ennek további adatokkal member fej hogy most a fejét a lista már nem 0, ami nem volt egy perce. Most tulajdonképpen az 1-es szám. Ily módon kapok egy kis optimalizálás. Csak azért, mert én már megszüntetjük sorban valaki a vonal elején a határvonalat az Apple store nem azt jelenti, mindenkinek váltani, ami recall lineáris művelet. Én inkább tölteni konstans idő csak és elérni, majd egy sokkal gyorsabb választ. De az árat én fizetem, amit szerezni, hogy a teljesítménnyel kapcsolatos további , és nem kell váltani mindenkinek? Aha. >> [Hallhatatlan tanulói válasz] Lehet hozzá több ember, valamint, hogy a probléma ortogonális arra, hogy nem vagyunk változó emberek. Ez még mindig egy tömb, így függetlenül attól, hogy mi váltani mindenkinek, vagy nem- oh, értem, mire gondolsz, oké. Igazából egyetértek, amit mondasz, hogy ez majdnem olyan, mintha mi most soha nem fog használni a kezdete ennek a tömb többé mert ha eltávolítani 5, aztán vegye ki 7. De én csak fel az embereket, hogy a jobb oldalon. 

Olyan, mintha én kiesik hely, és végül a sort esik szét semmit, így is csak az emberek wraparound, és mi is úgy gondolja, az e tömb valóban valamiféle körkörös szerkezet, de mit használ üzemeltető C kell csinálni, hogy a fajta wraparound? [Hallhatatlan diák válasza] >> A modulo operátor. Ez egy kicsit bosszantó, hogy gondolja át, hogyan csinálod a wraparound, de nem tudtunk csinálni, és mi lehetne kezdeni üzembe az emberek, hogy mi szokott lenni az első a sorban, de ne feledd, hogy ennek vezetője a változó, hogy ki a tényleges vezetője a vonal valójában. Mi lenne, ha ahelyett, hogy célunk, végül, bár, az volt, hogy néz ki a számokat, mint mi itt a színpadon Anita, de mi igazán akarjuk, hogy a legjobb az összes e világok? Azt akarjuk, hogy több, mint a tömb kifinomultságát teszi mert azt akarjuk, hogy a képesség, hogy dinamikusan növekszik a adatszerkezet. De mi nem akarjuk, hogy kénytelen valami, amit rámutatott Az első előadás nem volt optimális algoritmust, hogy a lineáris keresés. Kiderült, hogy lehet, sőt, elérése vagy legalábbis közel konstans időt, amelyben valaki, mint Anita, ha ő úgy konfigurálja neki adatstruktúra, hogy nem a láncolt lista, nem, hogy egy verem, nem, hogy egy sor, tudott, sőt, felér egy adatszerkezetet, amely lehetővé teszi neki, hogy nézzen ki a dolgokat, akár szóval, nem csak számok, milyen hívjuk konstans idő. 

És valóban, előretekintve, az egyik psets ebben az osztályban szinte mindig a megvalósítása spellchecker, ahol adunk ismét néhány 150.000 angol szavak és a cél az, hogy betölteni ezeket a memóriába, és gyorsan képes legyen válaszolni a kérdésekre a forma a szóval helyesen írta? És ez tényleg szívás, ha kellett navigálhat végig 150.000 szó válaszolni. De valójában, akkor láthatjuk, hogy meg tudjuk csinálni nagyon, nagyon gyors idő. És ez fog bevonni végrehajtása egy úgynevezett hash tábla, és bár első pillantásra ez a dolog úgynevezett hash tábla fog hadd elérni ezeket szuper gyors reakcióidő, kiderül, hogy van valójában egy probléma. Amikor eljön az ideje, hogy végre ezt a dolgot nevezett, ismét csinálom újra. Én vagyok itt az egyetlen. Amikor eljön az ideje, hogy végrehajtja ezt a dolgot hívják hash tábla, mi kell majd döntést hozni. Mekkora kell, ez a dolog valójában? És amikor elkezdünk behelyezésekor számokat ebbe hash tábla, hogyan fogjuk tárolni őket oly módon, hogy lehet kapni őket vissza, amilyen gyorsan csak mi van velük? De majd meglátjuk nemsokára, hogy ez a kérdés amikor mindenki születésnapja van, az osztály lesz elég jelentősége. Kiderült, hogy ebben a szobában, van néhány száz ember, így az esélye, hogy mi ketten van egyforma születésnapja valószínűleg elég magas. Mi van, ha csak 40 vagyunk ebben a szobában? Mi az esélye, hogy két ember azonos születésnap? [Diákok] Több mint 50%. Igen, több mint 50%. Sőt, én is hozott egy táblázatot. Kiderült, és ez tényleg csak egy settenkedik sajtóbemutató, ha már csak 58-en vagyunk ebben a teremben, annak valószínűsége, 2 velünk azonos születésnapja kiemelkedően magas, közel 100%-os, és ez fog okozni egy csomó árthat nekünk szerdán. 

Ezzel azt mondta, menjünk elnapolására itt. Találkozunk szerdán. [Taps] [CS50.TV]