[Powered by Google Translate] [6. szakasz: Kevesebb Comfortable] [Nate Hardison] [Harvard Egyetem] [Ez a CS50.] [CS50.TV] Rendben van. Üdvözöljük a 6. szakasz. Ezen a héten, mi lesz beszélni adatszerkezetek szakaszban, elsősorban azért, mert az e heti problémája beállított spellr nem egy csomó különböző adatszerkezet feltárása. Van egy csomó különböző módon lehet menni a probléma halmaz, és minél több adatszerkezetek tudsz, annál több jó dolog, amit tehetünk. 

Tehát kezdjük. Először fogunk beszélni halom, a köteget, és sorban adatszerkezetek hogy fogunk beszélni. Stacks és a sorok nagyon hasznos, amikor elkezdünk beszélni grafikonok, amely nem fogunk csinálni annyi most. De ők nagyon jó, hogy megértsék az egyik nagy alapvető adatszerkezeteket a CS. A leírás a probléma set specifikáció, ha húzza fel, arról beszél, halom, mint rokon a halom étkezési tálcák, hogy van a kávézóban a étkező amennyiben ha az étkezési staff jön, és hozza az étkező tálcák után ők már tisztítani őket, ők verem őket egymás tetejére a többi. És akkor, amikor a gyerekek jönnek, hogy az élelmiszer, hogy húzza ki a tálca le, először a felső 1, akkor az egyik alatta, akkor az egyik alá. Tehát, valójában az első tálcát, hogy az étkező személyzete letette az utolsó, hogy lesz levették. Az utolsó, hogy az étkező személyzete hozott az első, hogy lesz levették vacsorára. A probléma meg a spec, ami letölthető, ha még nem tette meg, beszélünk modellezve egy halom adat struktúrájának használja ezt a fajta struktúra. 

Szóval, mi van itt, ez hasonló ahhoz, amit bemutatott előadás, kivéve az előadásban bemutatta ezt ints szemben char * s. Ez lesz a verem, hogy tárolja mi? Daniel? Mit tárolja a stack? [Daniel] Strings? >> Mi tárolja húrok ebben stack, pontosan. Minden, amire szüksége van annak érdekében, hogy a verem egy tömb egy adott kapacitás, ami ebben az esetben, kapacitás lesz minden sapkák, mert ez egy állandó. És amellett, hogy a tömb minden, amit meg kell követni az aktuális méret a tömb. Egy dolog megjegyezni, hogy ez a fajta jó az, hogy mi hozzuk létre az halmozott adatstruktúrája tetejére másik adatszerkezet, a tömb. Vannak különböző módon végrehajtani stack. Mi nem is elég még, de remélhetőleg elvégzése után a linkelt lista problémák, látni fogja, hogyan lehet könnyen végre egy halom tetején egy láncolt lista is. De most, akkor ragaszkodj a tömbök. Tehát újra, minden van szükségünk egy tömb, és csak meg kell követni a méret a tömb. [Sam] Bocs, hogy miért van az, hogy azt mondta, ez a halom tetején a húrok? Számomra úgy tűnik, mintha a húrok belül a köteget. [Hardison] Igen. Mi létre, mi vesz a tömb adatszerkezetet - ez egy nagy kérdés. Tehát a kérdés, hogy miért, mert az emberek, akik figyelnek az online, miért vagyunk azzal, hogy a verem tetején a húrok, mert itt úgy néz ki, mint a húrok belül vannak a stack? Ami teljesen a helyzet. Amit utaltam az volt, hogy már van egy tömb adatszerkezet. Van egy sor char * s ez a tömb vonósok, és mi lesz hozzá, hogy annak érdekében, hogy megteremtse a halmozott adatok szerkezetét. 

Tehát egy stack valamivel bonyolultabb, mint egy tömb. Tudjuk használni egy tömböt, hogy építsenek egy verem. Szóval, ez az, ahol azt mondjuk, hogy a kémény épült a tetején egy tömb. Hasonlóképpen, mint korábban mondtam, tudunk építeni egy halom tetején egy láncolt lista. Ahelyett, hogy egy tömb, hogy tartsa meg a elemet, tudtuk használni a láncolt lista, hogy tartsa meg a elemek és építeni a verem körül, hogy. Sétáljunk át néhány példát, látszó néhány kód, hogy lássa, mi történik itt valójában. A bal oldalon, amit dobott le, hogy mi struct stack nézne ki a memóriában Ha a kapacitást # definiáljuk négy. Megvan a négy elem char * tömb. Van strings [0], strings [1], strings [2], strings [3], majd, hogy az utolsó helyet a méret egész. Van ennek értelme? Oké. Ez történik, ha az, amit csinálok a jobb oldalon, melyik lesz a kód, hogy csak nyilvánítson egy struct, a halmozott struct nevű s. Ez az, amit kap. Megállapítja a lábnyom a memóriában. Az első kérdés az, mi a tartalma struct stack? Most ők semmit, de ők nem teljesen semmit. Ők ezt a fajta szemetet. Fogalmunk sincs, mi van velük. Amikor állapítsa stack s, mi csak dobott, hogy le a tetején memória. Ez olyan, mint nyilvánító int i, és nem inicializálása meg. Nem tudod, mi van benne. Tudod olvasni, mi van ott, de lehet, hogy nem lesz szuper hasznos. Az egyik dolog, amit szeretnénk, hogy mindig emlékezni kell tennie inicializálni amit inicializálni kell. Ebben az esetben fogjuk inicializálni a méret nulla, mert ez fog kiderülhet, hogy nagyon fontos a számunkra. Mi is megy előre, és inicializálja az összes mutató, az összes char * s, érthető, hogy néhány érték, valószínűleg null. De ez nem teljesen szükséges, hogy ezt tesszük. 

Most, a két fő műveletek stack? Mindenki emlékszik az előadás, amit csinálni stack? Igen? [Stella] megnyomásával és popping? >> Pontosan. Pushing és popping a két fő műveletek stack. És mit nyomógomb csinálni? >> A helyezi valamit rá a felső A verem, majd pukkanó veszi le. [Hardison] Pontosan. Így nyomja tolja valamit a köteg tetején. Ez olyan, mint az étkező személyzete üzembe étkező tálcát a pultra. És popping vesz egy étkező tálca le a verem. Sétáljunk át néhány példát, hogy mi történik amikor nyomja a dolgokat a verem. Ha volt, hogy nyomja a húr "hello"-ra a verem, ez az, amit mi diagram nézne most. Nézze meg, mi történik? Mi tolta az első eleme a húrok array és mi növelte a méret számít, hogy 1. Tehát, ha megnézzük a különbséget a két diák, itt 0 volt, itt, mielőtt a push. Itt van azután a push. Mielőtt a push, miután a push. És most van egy eleme a verem. Ez a string "hello", és ennyi. Minden más a tömbben, a mi húrok tömb, még szemét. Még nem inicializált meg. Mondjuk tolja egy húr rá a stack. Megyünk, hogy álljon "világ" erre az időre. Így lásd a "világ" itt megy a tetején "hello", és a méret gróf felmegy 2-re. Most nyomja meg a "CS50", és hogy megyek a tetején újra. Ha visszamegyünk, akkor láthatja, hogy mi nyomja a dolgokat a tetején a verem. És most kap a pop. Amikor valami bukkant ki a köteg, mi történt? Látta valaki a különbséget? Elég finom. [Student] A méretét. >> Ja, a méret változott. 

Mi mást kíván volna várható, hogy változni? [Student] A vonósok is. >> Rendben. A vonósok is. Kiderült, hogy amikor csinálod ezt így, mert mi nem másol az elemek a mi verem, valójában nem kell tennie semmit, akkor csak használja a méret nyomon követni, hogy hány dolog a tömbben annak érdekében, hogy amikor újra felbukkan, megint csak csökkentse a méretét le 1-re. Nem kell, hogy ténylegesen megy, és felülírja semmit. Fajta funky. Kiderült, hogy általában csak hagyjuk a dolgokat csak azért, mert ez kevesebb munkát nekünk csinálni. Ha nem kell, hogy menjen vissza, és felülírja valami, akkor miért csináljuk? Így, amikor a pop kétszer le a stack, minden, ami nem is csökkentjük a mérete egy-két alkalommal. És megint, ez csak azért, mert nem vagyunk másolás dolgokat a stack. Igen? Rajta. [Diák, érthetetlen] >> És akkor mi történik, ha valami nyomja meg újra? Ha valami nyomja meg újra, ha nem megy? Ha nem is megy, Basil? >> Into strings [1]? >> Rendben. Miért nem megy strings [3]? [Basil] Mert elfelejtettem, hogy volt bármi strings [1] és [2]? [Hardison] Pontosan. A verem, lényegében "megfeledkezett", hogy a kezében tartott be semmit A strings [1] vagy strings [2], így mikor nyomja meg a "woot" ez csak hozza, hogy az elem a strings [1]. Van bármilyen kérdése, hogy hogyan is működik ez, egy alap szinten? [Sam] Tehát ez nem dinamikus semmilyen módon, tekintve összeg , vagy jelentősen a méretét a stack? [Hardison] Pontosan. Ez - a lényeg az volt, hogy ez nem volt egy dinamikusan growning verem. Ez egy olyan verem, hogy fér, legfeljebb 4 char * s, legfeljebb négy dolog. Ha volt, hogy megpróbálja, és nyomja meg 1/5 dolog, mit gondolsz, meg kell történnie? [Diákok, érthetetlen] [Hardison] Pontosan. Van néhány dolog, ami történhet. Ez esetleg seg hiba, attól függően, mi volt - pontosan hogyan voltunk végrehajtására back-end. Ez lehet felülírni. Volna, hogy a buffer overflow, hogy beszélgettünk az osztályban. Mi lenne a legkézenfekvőbb dolog, hogy lehet felülírni ha megpróbálták betolni egy extra dolog, a mi stack? Szóval említette puffer túlcsordulást. Mi lehet az a dolog, ami kap felülírni vagy taposták a ha túlcsordult véletlenül próbálják nyomni egy extra dolog? [Daniel, érthetetlen] >> Lehetséges. De kezdetben, mi fog történni? Mi lenne, ha megpróbálta, hogy álljon egy negyedik dolog? Lehet, hogy felülírják a méret, legalábbis ez a memória diagram hogy megvan. 

A probléma set előírás, amit mi fogunk végrehajtó ma, amit akarok csinálni éppen visszatér hamis. A gombnyomásos módszer megy vissza boolean érték, és hogy a logikai érték lesz, igaz, ha a push sikerül és hamis, ha nem tudunk semmit, nyomja inkább, mivel a verem megtelt. Sétáljunk egy kicsit, hogy a kód most. Itt a push-funkció. A Push funkció egy halom fog tartani a húr, hogy terjesszen a verem. Ez lesz return true ha a string sikeresen tolta A stack és hamis egyébként. Minden arra vonatkozóan, hogyan lehet egy jó első dolog itt? [Sam] Ha a méret megegyezik kapacitás majd vissza hamis? [Hardison] Bingo. Szép munka. Ha a méret a kapacitás, megyünk vissza hamis. Nem tudunk tenni semmit többet a verem. Egyébként, szeretnénk tenni valamit a tetején a verem. Mit jelent a "a tetején a verem," az elején? [Daniel] Méret 0? >> Size 0. Mi a legjobb a verem után van egy dolog, a stack? Missy, tudod? [Missy] One. >> Size egy, pontosan. Tartsd hozzátéve, hogy a méret, és minden alkalommal, amikor üzembe az új elemet az index méretét a tömbben. Meg tudjuk csinálni azt a fajta egysoros, ha van értelme. Szóval megvan a húrok tömb fogjuk elérni azt a méret index, és mi csak úgy, hogy tárolja a char * ott. Figyeljük meg, hogy nincs szöveg másolás folyik itt, nincs dinamikus elosztása a memória? Aztán Missy nevelkedett, amit most csinálni, mert már tárolt a húr a megfelelő helyre a tömbben, , és azt mondta, hogy meg kellett növelni a méretét az egyik, hogy készen állunk a következő push. Így nem tehetünk, hogy a s.size + +. Ezen a ponton, már szorult a tömb. Mi az utolsó dolog, amit meg kell tennünk? [Student] Vissza igaz. >> Vissza igaz. Szóval ez elég egyszerű, egy nagyon egyszerű kódot. Nem túl sok. Miután tekert a feje köré, hogy a kémény működik, ez elég könnyen megvalósítható. 

Most, a következő része ez popping egy sor le a verem. Fogok adni nektek egy kis időt, hogy a munka ezen egy kicsit. Ez majdnem olyan, alapvetően a fordítottja, mit tettünk itt push. Amit tettem valójában - oops. Már elindult ki a készüléket ide, és a készüléket, Már húzta fel a problémát készlet 5 előírás. Ha Nagyításhoz itt látjuk vagyok cdn.cs50.net/2012/fall/psets/pset5.pdf. Már srácok le ezt a kódot, ami itt található, section6.zip? Rendben van. Ha még nem tette meg, hogy csinálni most, nagyon gyorsan. Megcsinálom az én terminál ablakban. Igazából tettem fel ide. Igen. Igen, Sam? >> Lenne egy kérdésem, hogy miért mondtad s.string 's zárójelben size = str? Mi az str? Az, hogy a megadott valahol, vagy - ó, a char * str? [Hardison] Igen, pontosan. Ez volt az az érv. >> Ó, oké. Bocsánat. [Hardison] Mi meghatározza a húr, hogy álljon be A másik kérdés, hogy jöhet ki, hogy nem igazán beszél itt volt vettünk értetődőnek tekinti, hogy mi volt ez a változó nevű s volt hatályát és hozzáférhető számunkra. Vettünk értetődőnek tekinti, hogy s volt ez a struct stack. Így nézett vissza most ezt a push-kódot, láthatod, hogy csinálunk dolgokat, hogy ennek az, hogy a kapott karakterlánc ben elfogadott de aztán hirtelen, mi hozzáférés s.size, mint, hol s származik? A kódot fogunk nézni a következő részben archívumban majd a dolog, hogy akkor csinál a probléma készletek, tettük a struct stack egy globális változót hogy mi férhet hozzá minden különböző funkciók anélkül, hogy kézzel adja át a környéken, és adja át a hivatkozással, tegyenek meg mindent, hogy ilyen dolgokat is. Mi csak csaló egy kicsit, ha úgy tetszik, hogy a dolgok szebb. És ez az, amit csinálunk itt, mert ez a móka kedvéért, ez könnyebb. Gyakran látni fogod ember ezt, ha van egy nagy adatstruktúra ez alatt üzemeltetett saját program. 

Menjünk vissza a készüléket. Vajon mindenki sikeresen kap a section6.zip? Mindenki csomagolja ki a unzip section6.zip? Ha bemegy a 6. szakasz könyvtár - Ááá, az egész hely - és felsorolja, hogy mi van itt, látod, hogy van három különböző. c fájlokat. Van egy sorban, egy sll, amely egyszeres linkelt listát, és a verem. Ha nyit stack.c, láthatod, hogy megvan ez a struktúra meghatározott számunkra, a pontos struct, hogy mi csak beszélgettünk a diákat. Megvan a globális változó a stack, megvan a push-funkció, és akkor megvan a pop funkciót. Beteszem a kódot nyomja vissza a dián itt, de amit szeretnék nektek kell tennie, hogy a legjobb az a képesség, megy, és hajtsák végre a pop funkciót. Miután végre, akkor lehet fordítani ezt teszi verem, majd futtassa a kapott stack futtatható, és hogy futni fog mindez teszt kód ide, hogy ez a fő. És a fő gondoskodik ténylegesen hogy a push és pop hívások és gondoskodjanak arról, hogy minden megy keresztül minden rendben. Azt is inicializálja a stack mérete itt így nem kell aggódni, hogy inicializálása. Azt feltételezhetjük, hogy ez már megfelelően inicializálva az az idő, hogy érheti azt a pop funkciót. Van ennek értelme? Szóval itt vagyunk. Ott van a push-kódot. Adok nektek 5 vagy 10 perc. És ha bármilyen kérdése van az időközi közben kódolás, kérd meg őket, hangosan. Tehát, ha kap egy szúrás, csak kérdez. Hadd tudja, hadd mindenki tudja. Dolgozz a szomszéd is. [Daniel] Épp végrehajtási pop most? >> Just pop. Bár tudja másolni végrehajtását push ha szeretné annak érdekében, hogy a vizsgálat fog működni. Mert nehéz tesztelni a dolgokat bekerülni - vagy nehéz tesztelni felbukkanó dolgokat egy köteg, ha nincs semmi a stack kezdeni. 

Mit pop kellene vissza? Az elem a tetején a verem. Állítólag, hogy az elem le a tetején a verem és majd csökkentjük a méret a verem, és most már elvesztette az elem a tetején. És akkor vissza az elem a tetején. [Diák, érthetetlen] [Hardison] Szóval, mi történik, ha nem ezt? [Diák, érthetetlen] Mi végül is történik akkor valószínűleg elérésével sem olyan elem, amely nem került még inicializálva, így a számítás Az, ahol az utolsó elem ki van kapcsolva. Tehát itt, ha azt veszi észre, hogy push, vagyunk hozzáférés húrok a s.size elem mert ez egy új index. Ez az új tetején a verem. Mivel a pop, s.size lesz a következő hely, a tér, ami a tetején az összes elemet a verem. Tehát a legfelső elem nem s.size, hanem ez alatta. 

A másik dolog, ha - a pop, van akkor kell csökkentse a méretet. Ha emlékszel vissza a mi kis diagram itt, valóban, az egyetlen dolog, amit láttam történik, amikor az úgynevezett pop volt, hogy ez a méret csökkent, először 2, akkor 1-re. Aztán amikor tolt egy új elemet, akkor megy a megfelelő helyre. [Basil] Ha a s.size 2, akkor nem lenne menni elem 2, és akkor azt szeretné, hogy a pop ez az elem le? Tehát, ha mentünk - >> Akkor nézzük meg újra. Ha ez a mi stack ezen a ponton és felhívjuk pop, ahol index a legfelső elem? [Basil] A 2, de ez lesz a pop 3. >> Rendben. Szóval ez az, ahol a mérete 3, de azt szeretnénk, hogy a pop az elemet az index 2. Ez az a tipikus fajta le az egyik, hogy van a zéró indexelésének tömbök. Szóval nem szeretné, hogy a pop a harmadik elem, de a harmadik elem nem index 3. És az ok, amiért nem kell tennie, hogy a mínusz 1, ha mi nyomja azért van, mert most azt tapasztalja, hogy a legfelső elem, ha mi voltunk, hogy álljon ki valami mást a verembe ezen a ponton, mi lenne akarja nyomni azt index 3. És ez csak azért történik, hogy a méret és az indexek sorban, ha éppen nyomva. 

Kinek van egy működő stack végrehajtását? Van egy működő stack egyet. Van pop dolgozik még? [Daniel] Igen. Azt hiszem, igen. >> Program fut, és nem seg Hibás, ez kinyomtatott? Vajon ki kell nyomtatni a "siker", amikor elindul? Igen. Győződjön verem, futtassa, ha kinyomtatja a "siker", és nem megy boom, akkor minden jó. Rendben van. Menjünk át a készülék nagyon gyorsan, és megyünk keresztül. Ha megnézzük, hogy mi folyik itt, pop, Daniel, mi volt az első dolog, amit tett? [Daniel] Ha s.size nagyobb, mint 0-ra. [Hardison] Oké. És miért csináltad ezt? [Daniel] A győződjön meg arról, hogy van valami benne a papírköteget. [Hardison] Rendben. Azt akarod, hogy teszteljék, hogy győződjön meg arról, hogy s.size nagyobb, mint 0; egyébként, mit akarsz, hogy megtörténjen? [Daniel] Return null? >> Return null, pontosan. Tehát, ha s.size nagyobb, mint 0-ra. Akkor mit fogunk csinálni? Mit tegyünk, ha a verem nem üres? [Stella] You csökkentse a méret? >> A csökkentjük a méretet, oké. Hogy csináltad ezt? >> S.size--. [Hardison] Nagy. És akkor mit csináltál? [Stella] És akkor azt mondtam vissza s.string [s.size]. [Hardison] Nagy. Ellenkező esetben vissza null. Igen, Sam? [Sam] Miért nem kell s.size + 1? [Hardison] Plus 1? >> Igen. >> Megvan. [Sam] Azt hittem, azért, mert szedi 1 kimenet, akkor leszel vissza nem az egyik, hogy kértek. [Hardison] És ez volt az, mit beszéltünk ezzel az egész kérdéssel 0-indexek. Tehát ha Nagyításhoz vissza ide. Ha megnézzük ezt a fickót itt látható, hogy amikor a pop, mi popping az elemmel index 2. 

Így csökken a méret az első, akkor a mérete egyezik az index. Ha nem csökkentjük a méret az első, majd meg kell tennünk Méret -1 és majd csökkentő. Remek. Minden jó? Van még kérdése ezzel kapcsolatban? Van számos különböző módon írja ezt is. Tény, hogy tehetünk valamit, akár - tehetünk egy bélés. Tehetünk egy-line vissza. Tehát ténylegesen csökkentse, mielőtt vissza az csinálja. Így helyezi a - előtt s.size. Ez teszi a vonal nagyon sűrű. Amennyiben a közötti különbség - s. Méret és s.size-- hogy ez a postfix - hívják postfix, mert az - után jön a s.size-- azt jelenti, hogy s.size értékelése céljából a megállapítás az index mivel ez jelenleg amikor ez a vonal végrehajtásra kerül, majd ezt - történik a vonal lesz végrehajtva. Miután az elemét index s.size hozzáférni. És ez nem az, amit mi akarunk, mert azt akarjuk, hogy megtörténjen a Csökkentés először. Othewise, fogunk férni a tömb, hatékonyan, a határokat. Fogunk férni az elem felett az egyik, hogy mi valóban szeretnénk elérni. Igen, Sam? >> Van gyorsabban vagy kevesebb RAM van abban, hogy egy sorban, vagy sem? [Hardison] Őszintén szólva, ez tényleg attól függ. [Sam, érthetetlen] >> Igen, ez attól függ. Meg tudod csinálni compiler trükkök , hogy a fordító, hogy ismerje el, hogy általában, gondolom. 

Így már említettük egy kicsit erről a fordítóprogram optimalizálás stuff hogy meg tudod csinálni összeállításában, és ez a fajta dolog, hogy a fordító képes lehet kitalálni, mint oh, hé, talán meg tudom csinálni ezt minden egy műveletben szemben betöltése mérete változó RAM-ból, csökkenő azt, tárolására vissza ki, majd berakodás vissza újra feldolgozni a többi ezt művelet. De általában, nem, ez nem az a fajta dolog ez megy, hogy a program lényegesen gyorsabb. Minden további kérdésre stack? 

Szóval toló és popping. Ha akartok, hogy próbálja ki a hacker kiadás, mit tettünk a hacker kiadás valójában emelkedett és tette ezt a stack dinamikusan növekszik. A kihívás abban áll elsősorban itt, a push funkció , hogy kitaláljuk, hogyan lehet, hogy a tömb nő ahogy folyamatosan nyomva több és több elemet a veremből. Ez valójában nem túl sok kiegészítő kódot. Csak egy hívás - meg kell emlékezni, hogy a hívások malloc ott megfelelően, majd kitaláljuk, mikor fogsz hívni realloc. Ez egy szórakoztató kihívás, ha érdekel. 

De egyelőre, menjünk tovább, és beszéljünk sorok. Lapozzunk végig itt. A sorban a közeli testvére a verem. Így a stack, dolgok kerültek utolsó volt az első dolog, akkor lehet lekérni. Van ez az utolsó, először ki, vagy LIFO, megrendelés. Mivel a sorban, ahogy elvárható, amikor sorban állás, az első, aki kap a sorban, az első dolog, hogy bekerüljön a sorba, az első dolog, hogy lesz található a sorból. Sorok is gyakran használják, ha van dolgunk grafikonok, mint beszéltünk röviden stack, és sorok is hasznos egy csomó más dolog. Egy dolog, hogy jön fel gyakran próbál fenntartani, például rendezett lista elemeit. És akkor ezt egy tömb. Ha tud fenntartani egy rendezett listát azokról a dolgokról egy tömb, de ha ez lesz trükkös van, akkor mindig meg kell találni a megfelelő hely, hogy helyezze be a következő dolog. Tehát, ha van egy sor számok 1 és 10 között, majd bővíteni szeretné, hogy az összes a számokat 1-től 100, és te, hogy ezeket a számokat véletlen sorrendben, és próbálják tartani mindent rendezve, ahogy megy át, akkor a végén kelljen sokat változik. Bizonyos típusú sorok és bizonyos típusú alapul szolgáló adatstruktúrák, akkor valóban tartani meglehetősen egyszerű. Nem kell, hogy adjunk valamit, majd átszervezés az egész dolog minden egyes alkalommal. Nem kell neked sokat változó, a belső elemek körül. Ha megnézzük a sorban, akkor láthatjuk, hogy - szintén queue.c fejezetében kód - A struct, hogy már adott Önnek valóban hasonló a struct, hogy adott neked egy verem. 

Van egy kivétel ez alól, és egy kivételével hogy van e kiegészítő integer fejnek nevezett és a fej itt a nyomon követése a fejét a sorban, vagy az első elem a sorban. A verem, tudtuk nyomon követni az elem, amely voltunk letölteni, vagy a felső a verem, a csak a méret, mivel a sorban, mi kelljen foglalkozni ellentétes végei. Próbálunk tack dolgokat a végén, de aztán vissza a dolgokat a fronton. Így hatékonyan, a fej, már az index elején a sorban, és a méret ad az index a végén a sor hogy mi lehet letölteni dolgokat a fejét, és add a dolgokat, hogy a farok. Mivel a stack voltunk, mindig csak foglalkozik a tetején a verem. Sosem volt hozzáférni az alján a verem. Csak hozzá dolgokat a felső és vette a dolgokat le a felső így nem volt szükség, hogy az extra terület belsejében a struct. Van, hogy általában van értelme? Rendben van. Igen, Charlotte? [Charlotte, érthetetlen] [Hardison] Ez egy nagy kérdés, és ez volt az egyik, hogy jött fel előadás. Lehet, séta néhány példa jól szemlélteti, miért nem akarjuk használni strings [0], mint a feje a sorból. 

Tehát elképzelhető, hogy már a sorban, fogjuk nevezni sorban. Az elején, amikor már csak példányosított azt, amikor már csak úgy ítélte meg, még nem inicializált semmit. Ez az egész szemetet. Így természetesen szeretnénk, hogy győződjön meg arról, hogy mi inicializálása mind a méret és a fej mezőket értéke 0, valami ésszerű. Azt is megy előre, és null ki az elemeket a sorban. És hogy ez a diagram megfelelő, észreveheti, hogy most a várólista csak tartani három elem; mivel a stack tarthatna négy, a várólista csak tartani három. És ez csak az, hogy a diagram illeszkedést. Az első dolog, ami történik, itt is sorba állításához a string "szia". És ahogy tettük a verem, semmi szörnyen más itt, dobjuk a húr bekapcsolva strings [0] és növelni a méretét 1-gyel. Mi sorba állításához "bye", nem lesz hozott. Szóval ez úgy néz ki, mint egy verem a legtöbb. Kezdtük el itt, az új elem, új elem, mérete folyamatosan megy fel. Mi történik ezen a ponton, ha azt akarjuk, hogy dequeue valamit? Ha azt akarjuk, hogy dequeue, amely az elem, hogy szeretnénk dequeue? [Basil] Strings [0]. >> Zero. Pontosan jobbra, Basil. Szeretnénk megszabadulni az első string, ez egy, "szia". Szóval, mi volt a másik dolog, ami változott? Figyeljük meg, amikor beugrott valami le a verem, csak változott a méret, de itt van egy pár dolgot, hogy a változás. Nem csak a méret megváltoztatását, de a feje változásokat. Ez megy vissza Charlotte szempontjából korábban: miért van ez a fej is? Van-e értelme most, Charlotte? >> Fajtája. [Hardison] Fajta? Szóval, mi történt, amikor dequeued? Mit tett a feje tenni most érdekes? [Charlotte] Oh, mert megváltozott - rendben. Értem. Mivel a fej -, ahol a fej mutat változások szempontjából a helyét. Ez nem mindig a nulla index 1. >> Igen, pontosan. Mi történt, ha dequeueing a nagy elem történt, és mi nem ezt a fejet a területen mert mi mindig hívja ezt a fonalat és 0 index élén a sorban, akkor volna váltani a többi sorban lefelé. Meg kéne váltani "bye"-ból származó strings [1], hogy a húrok [0]. És strings [2] le strings [1]. És mi volna, hogy ezt a teljes lista elemek, az egész tömb elemei. És amikor mi ezt egy tömböt, hogy lesz igazán költséges. Tehát itt, ez nem egy nagy dolog. Csak három elem a tömbben. De ha volt egy sorban ezer elemek vagy egy millió elemet, majd hirtelen, kezdjük, hogy egy csomó dequeue hívásokat egy hurok, a dolgok igazán fog lassulni, mivel eltolódások mindent le folyamatosan. Tudod, a váltott műszakban 1, műszak 1-jéig, a váltott műszakban 1, műszak 1-gyel. Ehelyett használja ezt a fejet, hívjuk a "pointer", bár ez nem igazán egy mutató a szigorúan vett, ez nem egy mutató típus. Ez nem egy int * vagy a char *, vagy ilyesmi. De ez mutat, illetve jelzi a feje a sorban. Igen? 

[Student] Hogyan dequeue tudja, hogy csak elsül függetlenül áll a feje? [Hardison] Hogyan dequeue tudja, hogyan kell elsül bármi van a fejed? >> Igaz, igen. >> Mi ez nézi most csak amit a fej mező beállítása. Tehát ebben az első esetben, ha megnézzük itt, fejünk 0, index 0. >> Rendben. [Hardison] Szóval csak azt mondja rendben, nos, az elem az index 0, akkor a string "hi" az elem élén a sorban. Így fogunk dequeue azt a fickót. És ez lesz az az elem, hogy adja vissza a hívónak. Igen, Saad? >> Tehát a fej alapvetően határozza meg -, hová megy az index meg? Ez a kezdete ez? >> Igen. >> Oké. [Hardison] Ez lett az új kezdetet a tömb. Tehát, ha dequeue valamit, csak annyit kell tennie, hogy hozzáférhet a elemét index q.head, és ez lesz az elem kívánt dequeue. Azt is, hogy csökkentse a méretet. Meglátjuk egy kicsit, amikor a dolgok egy kicsit trükkös ezzel. Mi dequeue, és most, ha sorba állításához ismét hol sorba állításához? Ha ez a következő elem menni a sorban? Mondja el akarjuk sorba állításához a húr "CS". Into amely index fog menni? [Diákok] Strings [2]. >> Kettő. Miért 2 és nem 0-ra? [Basil] Mert most a fej 1, annak érdekében, hogy olyan, mint a kezdete a listát? [Hardison] Rendben. És mi jelöli a lista végére? Miről is használja jelölésére végéig a sorban? A fej a feje a sorban, az elején a mi sorban. Mi a vége a mi sorban? [Diákok] Méret. >> Size, pontosan. Tehát az új elemeket megy a méret és az elemeket, hogy a felszállás jön le a fejét. Amikor sorba állításához a következő elem, mi üzembe azt a méretben. [Student] Mielőtt fel, hogy bár mérete 1. volt, ugye? [Hardison] Rendben. Tehát nem elég a mérete. Size + nem +1, hanem + fej. Mert tolódott mindent a feje összeget. Szóval itt, most már van egy sorban méret 1, hogy kezdődik index 1. A farok index 2. Igen? 

[Student] Mi történik, ha dequeue strings [0] és a húrok "nyílások memória csak kap kiürült, alapjában véve, vagy csak elfelejtetted? [Hardison] Igen. Ebben az értelemben, mi csak elfelejtik őket. Ha arra tárolására másolatát őket - Sok adatstruktúrák gyakran tárolja a saját példányát az elemek úgy hogy a vezető személy az adatszerkezet nem kell aggódnia arról, hogy hol valamennyi mutató megy. Az adatszerkezet tartja be mindent, kapaszkodik az összes példány, , hogy győződjön meg arról, hogy minden továbbra is fennáll megfelelően. Azonban, ebben az esetben, ezek az adatok csak struktúrákat, az egyszerűség kedvéért, nem készít másolatokat semmit, hogy mi tárolja őket. [Student] Tehát ez egy folyamatos tömb -? >> Igen. Ha visszatekintünk, mit meghatározása volt ez a szerkezet, ez az. Ez csak egy standard tömb, mint láttad, tömb char * s. Van, hogy a -? >> Igen, csak gondoltam, ha akkor végül elfogy a memória, bizonyos mértékig, Ha mindezen üres foltok a tömb? [Hardison] Igen, ez egy jó pont. 

Ha megnézzük, hogy mi történt ma ezen a ponton, most már megtelt a sort, úgy néz ki. De nem igazán töltötte fel a sort mert van egy sorban, ami 2-es méret, de kezdődik index 1, mert ez az, ahol a feje mutató. Ahogy mondták, ez az elem a strings [0], a mutató értéke 0, nem igazán van. Ez nem a mi sorban többé. Csak nem zavarta, hogy menjen, és írja át, amikor dequeued azt. Így annak ellenére, hogy úgy néz ki, mintha már elfogyott a memória, tényleg nem. Ez a hely nem elérhető a számunkra, hogy használja. A megfelelő viselkedés, ha mi voltunk, hogy megpróbálja, és az első dequeue valamit mint a "bye", amely pop bye ki. Most sorban kezdődik index 2 és úgy 1-es méretű. És most, ha megpróbáljuk sorba állításához, és valami újra, mondjuk 50, 50 kell menni ezen a helyszínen index 0 mert még mindig elérhető számunkra. Igen, Saad? [Saad] Ez azt automatikusan történik? [Hardison] Ez nem történik meg teljesen automatikusan. Meg kell csinálni a matek hogy ez a munka, de lényegében az, amit tettünk az imént köré. [Saad] És ez baj, ha ez egy lyuk a közepén? [Hardison] Ez, ha tudjuk, hogy a matematikai dolgozzanak ki megfelelően. 

És kiderül, hogy ez valójában nem olyan nehéz, hogy köze van a mod operátor. Szóval, ahogy tettük Caesar és a crypto stuff, használatával mod, akkor a dolgokat, hogy lezárja a környéken, és folyamatosan megy körbe-körbe-körbe a mi sorban, tartani, hogy a fej mutató körül mozog. Figyeljük meg, hogy a méret mindig tiszteletben tartva az elemek száma ténylegesen a sorban. És ez még csak a feje pointer, hogy megtartja a kerékpározás keresztül. Ha megnézzük, hogy mi történt itt, ha visszamegyünk a kezdetekhez, és csak nézni, hogy mi történik a fej amikor sorba állításához valamit, semmi sem történt a fejét. Amikor enqueued valami mást, nem történt semmi a fejét. Amint dequeued valamit, a fej felmegy egy. Mi enqueued valamit, semmi sem történik a fejét. Amikor dequeue valamit, hirtelen a fej lesz eggyel. Amikor sorba állításához valamit, semmi sem történik a fejét. 

Mi lenne, ha ezen a ponton voltunk, hogy dequeue valami újra? Minden gondolat? Mi történne a fejed? Mi történne a fej ha volt, hogy dequeue valami mást? A fej most van index 2, ami azt jelenti, hogy a fej a sorban strings [2]. [Student] Melyik értéke 0? Meg kell >> vissza 0-ra. Meg kell tekerje vissza körül, pontosan. Eddig minden alkalommal hívtuk dequeue, mi már hozzá egyet a fej, hozzá egy a fejét, adjunk hozzá egy a fejét, hozzá egy a fejét. Amint a fejet mutató lesz az utolsó index a tömbben, akkor meg kell tekerje vissza körül az elején, menj vissza 0-ra. [Charlotte] Mi határozza meg a kapacitás a várólista a stack? [Hardison] Ebben az esetben, már most is használnak a # definiált konstans. >> Oké. [Hardison] A tényleges. C file, akkor megy és piszok vele egy kicsit és ez olyan nagy, vagy kicsi, amennyit csak akar. [Charlotte] Tehát, ha te így sorban, hogyan, hogy a számítógép tudja mekkora szeretné, hogy a stack lenni? [Hardison] Ez egy jó kérdés. Van egy pár módon. Az egyik, hogy csak definiálja elöl és azt mondják, ez lesz a sorban, amely a 4 elem, vagy 50 elemek vagy 10.000. A másik módszer az, hogy amit a hacker verzió emberek csinálnak és hozzon létre funkciókat, hogy a sorban növekszik dinamikusan látna dolgok adunk be 

[Charlotte] Szóval, hogy menjen el az első lehetőség, milyen szintaxist használsz megmondani a program mekkora a sor? [Hardison] Ah. Akkor menjünk ki ebből. Én mindig stack.c itt, így én csak megy felfelé a csúcsra itt. Látod ezt itt? Ez a # define befogadóképessége 10. És ez majdnem pontosan ugyanazt a szintaxist, hogy van a sorban. Kivéve sorban, megvan az extra struct területen van. [Charlotte] Ó, azt hittem, a kapacitás jelentette kapacitását a húr. [Hardison] Ah. >> Hogy ez a maximális hossza a szó. >> Megvan. Igen. A kapacitás itt - ez egy jó pont. És ez egy olyan dolog, ami bonyolult mert amit mi már bejelentett itt egy tömb char * s. Egy sor mutató. Ez egy sor karakter. Ez valószínűleg mit láttál, amikor már nyilvánításáról a pufferek a fájl I / O, ha már létre húrok kézzel a köteget. Azonban, mi van itt egy tömb char * s. Szóval ez egy sor mutató. Igazából, ha zoom vissza, és nézzük meg, mi folyik itt a bemutató, akkor láthatjuk, hogy az aktuális elemek, a karakteres adat nem tárolódik a tömb is. Mi tároljuk a mi tömb itt rámutatnak a karakteres adat. Oké. Tehát láttuk, hogy mekkora a várólista olyan, mint a verem, a méret mindig tiszteletben tartja az elemek száma jelenleg a sorban. Miután 2 enqueues, a mérete 2. Miután a dequeue mérete jelenleg 1. Miután egy másik sorba állítása a méret vissza 2-re. Tehát a méret határozottan tiszteletben tartja az elemek száma a sorban, majd a fejét, csak folyamatosan kerékpározás. Ez megy 0-1-2, 0-1-2, 0-1-2. És minden alkalommal hívjuk dequeue, a fej mutató kerül növekszik a következő index. És ha a fej arról szól, hogy menjen át, hogy hurkokat vissza mintegy 0-ra. Tehát azt tudjuk írni a dequeue funkciót. És mi lesz, hogy elhagyja a sorba állítása funkció srácok végrehajtása helyett. 

Amikor dequeue eleme a mi sorban, mi volt az első dolog, hogy Daniel volt, amikor elkezdtük írni a pop funkció stack? Hadd hallani valakit, aki még nem beszélt még. Lássuk, Saad, emlékszel, mit Daniel úgy tett, ahogy az első dolog, amikor azt írta, pop? [Saad] Ott volt, ez volt - >> Ő vizsgálni valamit. [Saad] Ha a mérete nagyobb, mint 0-ra. >> Pontosan. És mi volt, hogy a vizsgálatra? [Saad] Ez volt tesztelés, hátha van valami benne a tömbben. [Hardison] Igen. Pontosan. Tehát nem lehet pop semmit a verem, ha ez üres. Hasonlóképpen, nem tudsz dequeue semmit a sorból, ha ez üres. Mi az első dolog, amit meg kell tennünk a mi dequeue funkció itt, mit gondolsz? [Saad] Ha a méret nagyobb, mint 0? >> Igen. Ebben az esetben, amit valójában csak tesztelt, hogy ha ez a 0-ra. Ha az értéke 0, akkor vissza null. De pontosan ugyanaz a logika. És hadd folytassa ezt. Ha a méret nem 0, hol van az elem, hogy szeretnénk dequeue? [Saad] A fej? >> Pontosan. Mi is csak húzza ki az első eleme a sorban elérésével az elem a fejét. Semmi őrült. Után, mit tegyünk? Mi kell történnie? Mi volt a másik dolog, hogy beszélgettünk dequeue? Két dolog is történik, mert a várólista megváltozott. [Daniel] méretének csökkentése. >> Meg kell csökkenteni a méretét, és növeli a fej? Pontosan. Ha növelni szeretné a fejét, hogy nem lehet csak vakon növeli a fej, emlékszem. Nem csak tedd queue.head + +. Meg kell még ezt a mod a kapacitást. És miért mod a kapacitás, Stella? [Stella] Mert kell köré. >> Pontosan. Mi a mod a képesség, mert, hogy lezárja vissza mintegy 0-ra. Tehát most, ezen a ponton, azt tehet, amit Daniel mondott. Mi lehet csökkentjük a méretet. És akkor is csak vissza az elemet, hogy volt a tetején a sorban. Úgy néz ki, a fajta csomós elején. Lehet, hogy a kérdést. Tessék? 

[Sam] Miért van először a felső sorban? Hova vezet ez megy? [Hardison] Jön a negyedik sort az alján. Miután tesztelni, hogy győződjön meg arról, hogy a várólista nem üres, húzzuk ki char * először húzzuk ki az elemet, hogy ül az élén index a mi tömb, a mi vonósok tömb, >> és a hívás az első? [Hardison] És hívjuk először. Igen. Csak, hogy kövesse nyomon, hogy miért gondolom, hogy meg kellett csinálni? [Sam] Minden elsőt csak visszatér q.strings [q.head]? >> Igen. >> Mert mi ezt változó a q.head a mod funkcióval, és nincs módja, hogy a visszatérő ág is. [Hardison] Pontosan. Te helyszínen. Sam teljesen folt. Ennek az az oka kellett, hogy húzza ki az első eleme a sorban, és tárolja azt egy változó azért van, mert ez a vonal, ahol az imént q.head, ott van a mod operátor nincs valami, amit tehetünk és azt lép hatályba, a fej nélkül - egy sorban. Tehát valójában, hogy húzza ki az első elemet, majd állítsa be a fejét, állítsa be a méretet, majd vissza az elemet, amit kihúzott. És ez egy olyan dolog, hogy majd meglátjuk, jön később kapcsolódó listák, ahogy játszunk körül őket. Gyakran, amikor felszabadítása vagy ártalmatlanítása kapcsolt listák meg kell emlékezni a következő elem, a következő mutató egy láncolt lista kidobása előtt a jelenlegi. Mert különben dobja az információt, hogy mi maradt a listán. Most, ha megy a készülék, akkor nyissa meg queue.c--x ki ebből. Szóval, ha én nyit queue.c, hadd zoom itt, látni fogja, hogy van egy hasonló kinézetű fájlt. Hasonló kinézetű fájlt mi volt korábban stack.c. Megvan a struct a queue meghatározott ahogy láttuk a diákat. 

Megvan a sorba állítása funkció, ami az Ön számára csinálni. És mi van a dequeue funkciója van. A dequeue funkciót a fájl nem implementált, de majd helyezze vissza a PowerPoint, így írja azt, ha szeretné. Így a következő 5 percig, vagy úgy, srácok dolgozni sorba állítása amely majdnem éppen az ellenkezője dequeue. Nem kell beállítani head amikor enqueueing, de mit kell beállítani? Méret. Tehát, ha sorba állítása, a fej marad érintetlen, a mérete lesz megváltozott. De ez nem vesz egy kicsit - akkor a játék körül, hogy a mod hogy kitaláljuk, pontosan mi az index új elem kell beilleszteni. Szóval Adok nektek egy kicsit, tedd dequeue vissza a dián, és ahogy ti kérdései vannak, kiabálni őket, hogy mi lehet minden beszélni velük, mint egy csoport. Továbbá, a méret nem - amikor állítsuk be a méretét, akkor mindig csak - Mit kell mod mérete valaha? [Daniel] Nem >> Nem kell mod mérete, jobbra. Mivel a méret mindig, ha készen is - feltéve, te irányító dolgokat megfelelően, a méret mindig 0 és 3 közé. Hol kell mod ha csinálsz sorba állítása? [Student] Csak a fejét. >> Csak a fejét, pontosan. És miért kell mod egyáltalán sorba állítása? Ha egy olyan helyzet, amelyben azt kellett mod? [Student] Ha cucc terek, mint a terek 1 és 2, és akkor van szükség, hogy adjunk valamit 0. [Hardison] Igen, pontosan. Tehát, ha a fejed mutató a legvégén, vagy ha a méret és a fej nagyobb, vagy inkább fog köré a sorban. 

Tehát ebben a helyzetben, hogy mi van ide a dián most, ha akarok sorba állításához valamit most, azt akarjuk, hogy sorba állításához valamit index 0-ra. Tehát, ha megnézzük, ha az 50 megy, és arra kérem sorba állítása 50, megy ott alul. Magától index 0. Ez helyettesíti a "hi", hogy már dequeued. [Daniel] Ne vigyázni, hogy a dequeue már? Miért csinál semmit a fejét sorba állítása? [Hardison] Oh, szóval nem módosítja a fejét, sajnálom. De meg kell, hogy használja a mod operátor amikor eléréséhez az elem kívánt sorba állításához, amikor eléréséhez A következő elem a sorban. [Basil] nem tettem ezt, és kaptam "siker" ott. [Daniel] Ó, értem, amit mondasz. [Hardison] Szóval Nem mondta - csak tette q.size? [Basil] Igen. Én csak átállt, én nem csináltam semmit a fejét. [Hardison] Te valójában nem kell állítani a fejét, hogy bármi lehet, de ha index a húrok tömb, valóban el kell menni előre, és kiszámítja, ahol a következő elem, mert withe a verem, a következő elem a verem mindig -nél az index megfelelő méretűre. Ha megnézzük vissza a mi stack push-funkció, tudtunk mindig pengetés a mi új elem jobbra index méretét. Mivel a sorban, nem tehetjük, hogy a mert ha már itt vagyunk ezen a helyzeten, ha enqueued 50 új karakterlánc menne jobbra strings [1] amit nem akarok. Azt szeretnénk, hogy az új szöveg megy az index 0-ra. 

Van valaki - igen? [Diák] Nekem van egy kérdés, de ez nem igazán kapcsolódik. Mit jelent az, ha valaki csak felhívja ilyesmi pred pointer? Mi az, hogy a név rövid? Tudom, hogy ez csak egy név. [Hardison] Pred pointer? Lássuk. Milyen összefüggésben? [Student] Ez volt a betét. Megkérdezhetem később, ha szeretné mert ez nem igazán kapcsolódik, de én csak - [Hardison] A Dávid betét kódot előadás? Mi lehet húzni, hogy az, és beszélni. Megbeszéljük, hogy legközelebb, ha egyszer eljutunk linkelt listákat. 

Szóval nagyon gyorsan nézd meg mi a sorba állítása funkció néz ki. Mi volt az első dolog, hogy az emberek próbálkozott a sorba állítása sorban? Ebbe a sorba? Hasonló a mit tettél verem rámenős. Mit csináltál, Stella? [Stella, érthetetlen] [Hardison] Pontosan. Ha a (q.size == kapacitás) - Meg kell tenni a zárójelek a megfelelő helyen - return false. Nagyítás egy kicsit. Oké. Most mi lesz a következő dolog, amit meg kellett tennie? Csakúgy, mint a verem, és ki a legjobb helyen. És mi volt a jó helyen beszúrni ezt? A verem volt index méretét, ezzel ez nem ennyire. [Daniel] Van q.head--vagy - >> q.strings? >> Igen. q.strings [q.head + q.size mod KAPACITÁS]? [Hardison] Valószínűleg szeretnénk, hogy ez a zárójelek hogy mi vagyunk egyre a megfelelő elsőbbséget, és hogy ez cleart mindenkinek. És állítsa be, hogy egyenlő? >> To str? >> To str. Remek. És most mi az utolsó dolog, amit meg kell csinálni? Csakúgy, mint tettük a veremben. >> Lépésköz a méret? >> Lépésköz a méretet. Boom. És aztán, mivel az indító kódot csak vissza false alapértelmezés szerint, szeretnénk megváltoztatni ezt true ha minden megy keresztül, és minden jól megy. Rendben van. Ez rengeteg információ részben. Nem vagyunk teljesen vége. Azt akarjuk, hogy beszélni nagyon gyorsan mintegy egyszeres linkelt listákat. Majd, hogy ezt ki, így mehetünk vissza később. De menjünk vissza a bemutatót, mindössze néhány diák. Tehát sorba állítása a TODO, most megcsináltuk. 

Most vessünk egy pillantást egyszeres linkelt listákat. Beszéltünk ezekről egy kicsit több előadás. Hányan vagytok látta, hogy a demo, ahol volt az emberek félszegen mutat egymással és gazdaság számokat? >> Voltam ebben. >> Mit gondoltok, srácok? Vajon, hogy remélhetőleg demisztifikálják ezek egy kicsit? A listát, kiderül, hogy kezeljük az ilyen típusú, hogy fogunk hívni egy csomópont. Mivel a sorban, és a verem volt struktúrákat, hogy mi lenne szükséges sorban verem, mi volt ezen új sorban stack típusú, itt egy lista tényleg csak épül fel egy csomó csomópont. Ugyanilyen módon, hogy a húrok csak egy csomó karakter összes sorakoznak egymás mellett. A láncolt lista csak egy csomópont egy másik csomópont és egy másik csomópont és egy másik csomópont. És ahelyett, szétzúzva az összes csomópont össze, és tárolja őket összefüggően rendben egymás mellett a memóriában, tekintettel a következő mutató lehetővé teszi számunkra, hogy tárolja a csomópontok bárhol, véletlenszerűen. És akkor milyen huzal őket össze, hogy pont az egyik a másikra. 

És mi volt az a nagy előnye, hogy ez már több mint egy tömb? Over tároló minden összefüggően csak megragadt egymás mellett? Emlékszel? Igen? >> Dinamikus memória kiosztás? >> Dinamikus memória kiosztás milyen értelemben? [Student] Az, hogy tudja, hogy ez nagyobb és nem kell mozgatni az egész tömb? [Hardison] Pontosan. Tehát egy sor, ha azt szeretné, hogy egy új elem a közepén, meg kell váltani mindent, hogy helyet. És ahogy beszélgettünk a sorban, ezért tartjuk, hogy a fej mutató, úgy, hogy nem vagyunk állandóan változó dolgokat. Mert ez lesz drága, ha van egy nagy tömb és te állandóan csinál ilyen véletlen beszúrások. Mivel a listáját, mindössze annyit kell tennie, hogy dobja azt egy új csomópontot, állítsa be a mutató, és kész. Mi a szar van ezzel? Eltekintve attól a ténytől, hogy ez nem olyan könnyű vele dolgozni, mint egy tömb? Igen? [Daniel] Nos, azt hiszem, hogy ez sokkal nehezebb elérni egy adott elem a láncolt lista? [Hardison] Nem lehet csak ugrani egy tetszőleges elem a közepén a láncolt lista. Hogyan kell csinálni helyette? >> Meg kell lépni az egész dolog. [Hardison] Igen. Meg kell, hogy menjen át egy olyan időpontban, az egyik egy időben. Ez egy hatalmas - ez a fájdalom. Mi a másik - van még egy bukás e. [Basil] Nem mehetsz előre és hátra? El kell menni egy irányba? [Hardison] Igen. Szóval hogyan lehet megoldani, hogy néha? [Basil] Kétszer kapcsolt listák? >> Pontosan. Vannak kétszeresen láncolt listák. Vannak - Tessék? 

[Sam] Ez ugyanaz, mint a pred dolog, hogy - Csak eszembe jutott, nem az, hogy mi a pred dolog? Hát nem között kétszeresen és egyedül? [Hardison] Nézzük meg, mit csinál. Szóval itt vagyunk. Itt a lista kódot. Itt van predptr, itt. Ez mit beszélsz? Szóval ez volt - ő felszabadítja a listát, és ő próbál tárolni egy mutatót is. Ez nem a kétszeresen, egyenként kapcsolt listák. Beszélhetünk többet erről később, mivel ez beszél felszabadítja a lista és én meg akarom mutatni néhány más dolgot először. de ez csak - ez emlékezés értékét ptr [Student] Ó, ez elõzõ mutató? >> Igen. Ahhoz, hogy meg tudjuk majd növelni ptr magát, mielőtt majd ingyen, mi predptr van. Mert nem tudunk szabad ptr majd hívja ptr = ptr következő, ugye? Ez rossz lenne. Tehát lássuk, vissza ezt a fickót. 

A másik rossz dolog listákat, hogy míg egy sor már csak mind maguk az elemek halmozott egymás mellett, Itt mi is bevezette ezt a mutatót. Szóval van egy újabb darab a memória, hogy mi, hogy használja minden eleme, hogy mi tárolja a listában. Kapunk rugalmasságot, de jön áron. Jön ezúttal költséget, és jön-val ezt a memóriát költséget is. Az idő abban az értelemben, hogy most megy keresztül minden elem a tömbben hogy megtalálja az egyik az index 10, vagy lett volna index 10 egy tömbben. 

Csak nagyon gyorsan, amikor diagram ki ezeket a listákat, tipikusan tartjuk be a fejét a lista vagy az első mutató a lista és vegye figyelembe, hogy ez egy igazi mutató. Ez csak 4 byte. Ez nem a tényleges csomópont is. Így látod, hogy nem int értékkel benne, nincs jövő pointer benne. Ez szó szerint csak egy mutató. Meg fog mutatni valamit, ami a tényleges csomópont struct. [Sam] A mutató az úgynevezett csomópont? >> Ez - no. Ez a mutató valamit típusú csomópont. Ez a mutató egy node struct. >> Ó, oké. Diagram a bal oldalon, kód a jobb oldalon. Mi meg azt, hogy null, ami egy jó módja annak, hogy kezdeni. Ha a diagram, akkor sem írni, mint nulla, vagy teszel egy sort rajta tetszik. 

Az egyik legegyszerűbb módja, hogy dolgozni listákat, és kérünk még mind a előtag és hozzáfűzni, hogy a különbség a kettő között, de elé rakva határozottan könnyebb. Ha a neve elé, ez az, ahol - ha előtag (7), megy, és hozza létre a node struct és állítsa először mutasson rá, mert most, hiszen fűz azt, ez lesz az a lista elején. Ha előtag (3), hogy létrehoz egy másik csomópont, de most 3 jön 7-e előtt. Szóval lényegében toló dolgokat rá a listára. Most láthatjuk, hogy előtag, néha az emberek hívják push, mert te rámenős új elem rá a listára. Ez is könnyen törölheti elején egy listát. Így az emberek gyakran hívják, hogy a pop. És ily módon, akkor emulálni egy köteg segítségével láncolt lista. Hoppá. Sajnáljuk, de most mi bekerülni append. Tehát itt fűz (7), most előtag (3). Ha fűz valami mást fel ezt a listát, ha fűz (4), akkor volna 4, majd 3, majd 7. Akkor tudnánk pop és távolítsa el a 4-eltávolítás 3, 7 eltávolítás. Gyakran inkább intuitív módon gondolni ezt a hozzáfűző. Szóval ábrázolt ki, milyen lenne kinézni a hozzáfűzni itt. Itt mellékelt (7) nem néz másképp mert csak egy elem a listában. És hozzáfűző (3) mondja a végén. Talán láthatjuk most a trükköt append az, hogy mivel csak annyit tudunk, ha a lista elején van, hozzáfűzni egy listát kell járni végig a listán hogy a végére, megáll, majd építeni a csomópontot és pengetés le mindent. Kösse be az összes dolgot fel. Tehát előtag, mint mi csak szakadt ezen keresztül nagyon gyorsan, ha neve elé egy listát, ez elég egyszerű. 

Azt, hogy az új csomópont, magában néhány dinamikus memória kiosztás. Tehát itt vagyunk, hogy egy csomópont struct használatával malloc. Szóval malloc mi használ, mert ez lesz félretett memória nekünk a későbbi mert nem akarjuk, hogy ez - azt szeretné, hogy ez memóriát fennmaradhatnak hosszú ideig. És kapunk egy mutatót a helyet a memóriában, hogy csak különítettek el. Az általunk használt méretű csomópont nem összeadja a mezőket. Nem kézzel létre a byte-ok száma, ehelyett használjuk sizeof, hogy tudjuk, mi rá a megfelelő számú bájt. Gondoskodunk arról, hogy tesztelje, hogy a malloc hívás sikerült. Ez az, amit akarsz általában. A modern gépek, kifogy a memória nem valami könnyű hacsak nem kiosztása egy csomó dolgot, és így egy hatalmas lista, de ha építünk dolgokat, mondjuk, mint egy iPhone vagy Android, Önnek korlátozott memória-erőforrásokat, különösen, ha csinálsz valamit intenzív. Szóval ez jó, hogy a gyakorlatban. 

Figyeljük meg, hogy én is használtam egy pár különböző funkciók ide , amit láttam, hogy a fajta új. Szóval fprintf olyan, mint printf kivéve az első argumentum a patak, amelyre át szeretnénk nyomtatni. Ebben az esetben szeretnénk nyomtatni a standard hiba húr amely eltér a szabványos outstream. Alapértelmezés szerint ez azt mutatja fel, ugyanazon a helyen. Azt is kiírja a terminál, de akkor - használja ezeket a parancsokat értesült, az átirányítás technikák Ön értesült a Tommy videót a problémája készlet 4, tudod irányítani különböző területeit, majd kilép, itt, kilép a program. Ez lényegében, mint a visszatérő fő, kivéve az általunk használt exit mert itt visszatérés nem fog csinálni semmit. Nem vagyunk a fő, így a visszatérés nem jön ki a program, mint szeretnénk. Ezért használjuk a kilépés funkciót és adja meg a hibakódot. Akkor itt mi meg az új csomópont értékét területén, annak i mező megegyezik i, és aztán kösse fel. Mi meg az új csomópont mellett mutatót pont az első, majd az első lesz most mutatnak az új csomópontot. Ezek az első sornyi kódot, mi valójában építése az új csomópontot. Nem az utolsó két sor a funkció, hanem az első is. Tudod valójában húzza ki egy funkciót, egy segítő funkció. Ez gyakran, amit csinálok, azt húzza ki egy funkciót, Úgy hívom valami ilyesmit épít csomópont, és hogy tartja a előtag funkció elég kicsi, csak 3 sor majd. Azt, hogy a hívás az én épít csomópont funkciót, aztán drót mindent. 

Az utolsó dolog, amit szeretnék megmutatni neked, és én hagyom, hogy ezt append és minden, ami a saját, hogy hogyan navigálhat egy listát. Van egy csomó különböző módon navigálhat egy listát. Ebben az esetben fogjuk találni a hosszú lista. Szóval kezdjük hossz = 0. Ez nagyon hasonlít az írásban strlen egy string. Ez az, amit akarok mutatni neked, ez a for ciklus itt. Úgy néz ki, kicsit funky, ez nem a szokásos int i = 0, i <függetlenül, i + +. Ehelyett ez inicializálja a változót n, hogy az elején a listán. És míg a iterator változó nem nulla, akkor folytasd. Ennek oka, hogy megegyezés, a végén a mi lista null lesz. És akkor a növekmény helyett csinál + +, A láncolt lista megfelelője + + n = n-> next. 

Elárulok töltse ki a hézagokat itt, mert kifogytunk az időből. De ezt tartsd szem előtt, ahogy dolgozik a spellr psets. Csatolt listák, ha végrehajtása hash tábla, biztosan jön nagyon praktikus. És miután ezt a kifejezést a ciklusok alatt a dolgok, hogy az élet sokkal könnyebb, remélhetőleg. Bármilyen kérdése van, gyorsan? [Sam] Fogsz küldje el a kitöltött sll és sc? [Hardison] Igen. Küldök ki kitöltött diák és befejezett sll stack és queue.cs. [CS50.TV]