[Powered by Google Translate] [6 skirsnis: mažiau patogūs] [Nate Hardison] [Harvardo universiteto] [Tai CS50.] [CS50.TV] Gerai. Sveiki atvykę į 6 skyriuje. Šią savaitę, mes ketiname kalbėti apie duomenų struktūras skyriuje, visų pirma dėl to šią savaitę problema spellr ar visa krūva įvairių duomenų struktūros tirti. Yra krūva įvairių būdų, galite eiti su problema, rinkinį, ir daugiau duomenų struktūros, tu žinai apie daugiau įdomių dalykų, kuriuos galite padaryti. 

Taigi, galime pradėti. Pirmiausia mes ketiname kalbėti apie kaminai, kamino ir eilės duomenų struktūras, kad mes ketiname kalbėti apie. Vamzdžiai ir eilės yra tikrai naudinga, kai mes pradedame kalbėti apie grafikų, mes neketiname padaryti daug ir dabar. Bet jie tikrai gerai suprasti vieną iš didžiųjų pagrindinių duomenų struktūrų CS. Problemą, specifikacijos aprašymas, jei jūs traukite jį, pasakoja apie kaminai, panašus į maitinimo įstaigų padėklai krūva, kad turite kavinėje valgyklose kur, kai valgomasis darbuotojai ateina ir kelia valgomojo padėklai po to, kai jie valomi, jie sukrauti juos vieną ant kito. Ir tada, kai vaikai ateina gauti maisto, jie traukti dėklus pakilti, pirmiausia viršutinis, tada vienas po juo, tada žemiau, kad vienas. Taigi, tiesą sakant, pirmasis dėklas, kad valgomojo darbuotojai pribaigti yra paskutinė, kad bus nurašomas. , Naujausia, kad valgomojo darbuotojai įdėti yra pirmoji, kuri bus nurašomas vakarienė. Problemą, spec, kurią galite atsisiųsti, jei jūs neturite jau, mes kalbame apie modeliavimo naudojant šios rūšies struct kamino duomenų struktūrą ». 

Taigi, ką mes turime čia, tai yra panašus į tai, kas buvo pristatyta paskaita, išskyrus paskaitą mes pristatėme tai int, o ne char * s. Tai bus kamino, kad parduotuvėse, ką? Daniel? Ką mes saugojimo ši grandinė? [Daniel] Stygos? >> Mes saugome eilutes šioje kamino, tiksliai. Viskas, ką jums reikia, siekiant sukurti kamino yra masyvas tam tikro pajėgumų, kurie šiuo atveju, talpa bus didžiosiomis raidėmis, nes jis pastovus. Ir tada be masyvo, visi mes turime sekti, yra Dabartinis dydis masyvo. Vienas dalykas, reikia pažymėti, kad čia tipo kietas yra tai, kad mes sukurti sukrauti ant kitos duomenų struktūros, masyvas duomenų struktūrą. Yra įvairių būdų įgyvendinti kaminai. Mes ne padaryti jį gana dar, bet tikiuosi, atlikę nurodomi sąrašas problemų, pamatysite, kaip galite lengvai įgyvendinti susietą sąrašo viršuje taip pat kamino. Bet dabar, mes laikytis masyvų. Taigi dar kartą, visi mes turime yra masyvas, ir mes tiesiog reikia sekti masyvo dydį. [Sam] Atsiprašome, kodėl tai, kad jūs sakėte, kamino ant stygos? Man tai atrodo, kad stygos per kaminą. [Hardison] Taip. Mes kuriame, mes mūsų masyvo duomenų struktūrą - tai puikus klausimas. Taigi kyla klausimas, kodėl tiems žmonėms, kurie žiūri šį internete kodėl mes sakydamas, kad lapų krūva yra ant stygos, nes čia atrodo, kad stygos yra kamino viduje? Kuris yra visiškai netiesa. Ką aš turėjo omenyje, kad mes turime Masyvo duomenų struktūrą. Mes turime char * s, masyvas, tai eilučių masyvo, ir mes ketiname pridėti, kad, siekiant sukurti sukrauti duomenų struktūrą. 

Taigi krūva yra šiek tiek sudėtingesnis nei masyvo. Mes galime naudoti masyvą sukurti kamino. Taip, kad, kai mes sakome, kad kamino yra pastatytas ant masyvo. Lygiai taip pat, kaip aš sakiau anksčiau, mes galime statyti kamino susietą sąrašo viršuje. Vietoj to, naudojant masyvą turėti elementus, mes galime naudoti susietą sąrašą, turėti savo elementus ir sukurti aplink, kad kamino. Leiskite eiti per porą pavyzdžių, žiūri tam tikrą kodą, pamatyti, kas čia iš tikrųjų vyksta. Kairėje, aš mesti, ką atrodys, kad kamino struct atmintyje jeigu talpa buvo # apibrėžiamas būti keturi. Mes turime mūsų keturių elementų char * Array. Mes turime stygos [0], styginiams [1], styginiams [2], stygos [3], ir tada, kad paskutinis vietos mūsų dydžio sveikasis skaičius. Ar tai prasminga? Gerai. Tai, kas atsitiks, jei tai, ką darau dešinėje, kuri bus mano kodas, yra tiesiog paskelbti struct, sukrauti struct vadinamas ai. Tai, ką mes gauname. Ji nustato šią atminties pėdsaką. Pirmas klausimas čia yra, kas yra ši grandinė struct turinys? Dabar jie nieko, bet jie nėra visiškai nieko. Jie tokia šiukšlių. Mes neturime jokio supratimo, kas yra jų. Kai mes skelbiame kamino s, mes tiesiog mesti, kad ant atminties. Tai tipo kaip skelbiantis int i, o ne jį Inicijuojama. Jūs nežinote, kas ten. Galite skaityti, kas ten, tačiau ji gali būti itin naudinga. Vienas dalykas, kurį norite visada atsiminti, kad yra inicijuoti, kokia turi būti inicializuoti. Šiuo atveju, mes ketiname inicijuoti dydis lygus nuliui, dėl to, kad ketina pasirodyti mums labai svarbi. Mes galime eiti į priekį, inicijuoti ir rodykles, char * s, kai suprantama vertė, tikriausiai null. Bet tai nėra visiškai būtina, kad mes darome, kad. 

Dabar yra dvi pagrindinės operacijos kaminai? Kas nors prisiminti iš paskaitos, ką jūs darote su kaminai? Taip? [Stella] Pushing ir Popping? >> Būtent. Stumti ir Popping yra dvi pagrindinės operacijos kaminai. Ir ką stumti daryti? >> Joje kažką ant viršaus kamino, tada Popping pasiima jį išjungti. [Hardison] Būtent. Taigi stumia stumia kažką ant kamino. Tai kaip apmokestinti valgomasis padėklą ant prekystalio valgomojo darbuotojų. Ir Popping ir valgomojo dėklą kamino. Leiskite eiti per porą pavyzdžių, kas atsitinka, kai mes nužengti į kaminą. , Jei mes paspauskite eilutę "Hello" į mūsų kamino, tai, kas mūsų diagrama atrodys dabar. Žiūrėkite, kas atsitinka? Mes stumiama į mūsų styginiams masyvo pirmojo elemento ir mes rezervavimo mūsų dydžio skaičius turi būti 1. Taigi, jei pažvelgsime į skirtumo tarp dviejų skaidrių, čia buvo 0, čia prieš paspaudimu. Čia yra po tiesioginio. Prieš stumti, po tiesioginio. Ir dabar mes turime vieną elementą mūsų kamino. Tai eilutė "labas", ir viskas. Visa kita masyve, mūsų styginiams masyvo, vis dar yra šiukšlių. Mes Nepaleista. Tarkime, mes stumti kitą eilutę į mūsų kamino. Mes ketiname stumti "Pasaulis" šiuo metu. Todėl jūs galite pamatyti, "pasaulis" čia eina ant "labas", ir dydis skaičius pakyla iki 2. Dabar mes galime stumti "CS50", ir kad eisiu vėl ant. Jei mes einame atgal, jūs galite pamatyti, kaip mes stumti dalykų ant kamino. Ir dabar mes pop. Kai mes popped ką nors ne iš kamino, kas atsitiko? Kas nors matote skirtumą? Tai gana subtilus. [Studentų] dydis. >> Taip, dydis pakeistas. 

Ką dar galėtumėte tikėtis pakeisti? [Studentų] Styga, taip pat. >> Teisė. Stygos taip pat. Pasirodo, kad, kai jūs darote ją tokiu būdu, nes mes ne kopijuoti elementus į mūsų kamino, mes iš tikrųjų nereikia nieko daryti, mes galime tiesiog naudokite dydį sekti dalykų mūsų masyvas , kad kai mes pop vėl ir vėl mes tiesiog Mažėja mūsų dydį iki 1. Nereikia, faktiškai eiti ir perrašyti nieko. Natūra funky. It turns out, kad mes paprastai tiesiog palikti ką vien, nes tai mažiau darbo mums daryti. Jei mes neturime grįžti atgal ir perrašyti kažką, tai kodėl tai daryti? Taigi, kai mes pop du kartus išjungti kamino, kad tai yra Mažėja SIZE porą kartų. Ir vėl, tai tik todėl, kad mes ne kopijuoti dalykų į mūsų kamino. Taip? Eiti į priekį. [Studentas, nesuprantamas] >> Ir tada, kas atsitinka, kai jūs stumti kažką vėl? Kai jūs stumti kažką vėl, kur jis dabar yra? Kur jis dabar yra, Bezili? >> Į styginiams [1]? >> Teisė. Kodėl aš negaliu eiti į stygos [3]? [Bazilikas] Kadangi jis pamiršo, kad ten buvo kas nors tinkleliuose [1] ir [2]? [Hardison] Būtent. Mūsų kamino, iš esmės, "pamiršo", kad ji laikė, kad nieko tinkleliuose [1] arba stygos [2], todėl, kai mes stumti "running", jis tiesiog nurodo, kad į elemento stygos [1]. Ar yra kokių nors klausimų, kaip tai veikia, baziniu lygiu? [Sam] Taigi, tai nėra dinamiška, bet kokiu būdu, sumas arba kamino dydis? [Hardison] Būtent. Tai - klausimas buvo, kad tai buvo ne dinamiškai growning kamino. Tai kamino, kuris gali turėti ne daugiau, keturi char * s, ne daugiau kaip keturių dalykų. Jeigu mes buvo, kad pabandyti ir stumti penktą dalykas, ką jūs manote turėtų atsitikti? [Studentai, nesuprantami] [Hardison] Būtent. Yra daug dalykų, kad gali atsitikti. Jis galėtų seg kaltės, priklausomai nuo to, ką mes buvome kaip tiksliai vykdė back-end. Tai gali perrašyti. Tai gali turėti, kad buferio perpildymą, kad mes kalbėjome apie klasėje. Koks būtų pats akivaizdžiausias dalykas, kad gali būti perrašyti jei mes bandė stumti papildomą dalyką mūsų kamino? Taigi, jūs paminėjote buferio perpildymą. Koks gali būti dalykas, kad būtų gauti raštu per arba stomped apie jei mes netyčia krantų bando stumti papildomą dalyką? [Daniel, nesuprantamas] >> Galima. Bet iš pradžių, kas gali atsitikti? Ką daryti, jei mes bandė stumti ketvirtąjį patį? Jis gali perrašyti dydį, bent jau šią atminties schema, kad mes turime. 

Problemą, specifikaciją, kuri yra tai, ką mes ketiname būti įgyvendinta šiandien, tai, ką mes norime padaryti, tai tiesiog grįžti klaidinga. Mūsų eksporto metodas ketina grįžti vertė logiška, ir kad Būlio vertė bus teisinga, jei stumti pavyksta ir false, jei mes negalime stumti nieko daugiau,, nes kamino yra pilnas. Leiskite šiek tiek vaikščioti per šio kodekso dabar. Štai mūsų stumti funkcija. Mūsų stumti funkcija kamino ketina imtis į eilutę įdėti į steką. Ji ketina grįžti tiesa, jei eilutė buvo sėkmingai stumiama kamino ir klaidingas kitaip. Apie tai, kokiu pasiūlymai gali būti geras pirmasis dalykas, kurį reikia padaryti čia? [Sam] Jei dydis lygus talpa tada gražins false? [Hardison] Bingo. Gražus darbas. Jei dydis yra talpa, mes ketiname grįžti klaidinga. Mes negalime pateikti nieko daugiau mūsų kamino. Priešingu atveju, mes norime daryti kažką ant kamino viršaus. Kas yra "kamino viršų", iš pradžių? [Daniel] Dydis 0? >> Dydis 0. Kas yra po to, kai yra vienas dalykas, kamino kamino viršų? Missy, jūs žinote? [Missy] Vienas. >> Dydis yra vienas, tiksliai. Jūs nuolat pridedant dydžio, ir kiekvieną kartą esate išleidimą į naują indekso dydis elemento masyve. Mes galime tai padaryti tokio vieno-LINER, jei tai turi prasmę. Taigi, mes turime mūsų stygos masyvo, mes ketiname jį pasiekti dydžio indeksas, ir mes ten tik ketina saugoti mūsų char *. Atkreipkite dėmesį, kaip ten vyksta čia ne eilutė kopijavimas, ne dinaminis atminties paskirstymas? Ir tada Missy išvedė tai, ką dabar turi padaryti, , nes mes saugomi eilutę į tinkamą vietą masyve, ir ji pasakė, kad mes turėjome prieaugio dydį, vienas, kad mes pasiruošę į kitą stumti. Taigi, mes galime padaryti, kad su s.size + +. Šiuo metu, mes stumiama į mūsų masyvas. Kas yra paskutinis dalykas, kurį mes turime padaryti? [Studentų] Grįžti tiesa. >> Grįžti tiesa. Taigi, tai gana paprasta, gana paprastas kodas. Ne per daug. Sukūrę suvynioti savo galvos aplink, kaip veikia kamino, tai yra gana paprasta įdiegti. 

Dabar, kitą dalį tai yra Popping eilutę kamino. Aš einu duoti jums, vaikinai, tam tikrą laiką dirbti šioje šiek tiek. Tai beveik iš esmės, ką mes padarėme čia stumti reverse. Ką aš padariau, yra iš tikrųjų - Oi. Aš įkrautas iki prietaisą per čia, ir prietaiso, Aš iškedentas iki problema 5 specifikacija. Jei mes padidinti čia, mes galime pamatyti, aš ne cdn.cs50.net/2012/fall/psets/pset5.pdf. Ar jus vaikinai atsisiųsti šį kodą, kuris yra čia, section6.zip? Gerai. Jei to dar nepadarėte, kad tai padaryti dabar, tikrai greitai. Aš tai padaryti mano terminalo lange. Aš iš tikrųjų čia. Taip. Taip, Inga? >> Turiu klausimą apie tai, kodėl jūs sakote s.string "dydžio skliausteliuose = g? Kas yra g? Yra tai, kad nustatytų kažkur anksčiau, arba - oi, char * str? [Hardison] Taip, būtent. Tai buvo argumentas. >> O, gerai. Atsiprašau. [Hardison] Mes nurodant eilutę stumti. Kitas klausimas, kad gali sugalvoti, kad mes ne iš tikrųjų kalbėti apie čia mes priėmėme, savaime suprantama, kad mes tai kintamasis vadinamas ai taikymo sritis ir mums prieinamoje. Mes priėmėme, savaime suprantamu dalyku, kad buvo toks struct kamino. Taigi, žvelgdamas atgal šiuo stumti kodą, jūs galite pamatyti, ką mes darome, stuff su šios eilutės, kad gavo praėjo bet tada visi staiga, mes susipažinimo s.size, kaip, kur ai atsirado? Kodą, kad mes ketiname pažvelgti skyrelyje Archyvas ir tada nustato dalykų, kad jums daryti jūsų problemą, mes padarėme mūsų kamino Struct pasaulinį kintamąjį taip, kad mes galime turėti prieigą prie visų mūsų skirtingas funkcijas be būtinybės rankiniu būdu perduoti jį aplink ir perduoti jį atsižvelgiant, padaryti viską, kad daiktų į jį natūra. Mes tiesiog apgaudinėja šiek tiek, jei norite, kad viskas gražiau. Ir tai yra kažkas, ką mes darome čia, nes tai for fun, tai lengviau. Dažnai, jūs pamatysite, žmonės tai padaryti, jei jie turi vieną didelį duomenų struktūrą kad operuojama po savo programą. 

Grįžkime į prietaiso. Ar visi sėkmingai gauti section6.zip? Visi išpakuokite jį naudojant išpakuokite section6.zip? Jeigu jūs einate į 6 skirsnis kataloge - AAH, visur - ir jums sąrašą, kas yra čia, matote, kad jūs turite tris skirtingus C failus. Jūs turite eilę, SLL, kuri yra atskirai susieta sąrašas ir kamino. Jei atidarote stack.c, galite matyti, kad mes turime šį struct apibrėžtas mus tiksli struct, kad mes tiesiog kalbėjomės apie skaidres. Mes turime savo pasaulinį kintamąjį kamino, mes turime mūsų stumti funkciją, ir tada mes turime mūsų pop funkciją. Aš įdėti kodą stumti atgal skaidrę, bet tai, ką aš norėčiau jus vaikinai daryti, savo galimybes, eiti ir įgyvendinti pop funkciją. Kai jūs ją įgyvendino, jūs galite sudaryti tai padaryti krūvą, ir paleiskite gautą kamino vykdomąjį ir kad bus paleisti visus šio bandymo kodas žemyn čia tai pagrindinis. Ir pagrindinis rūpinasi iš tikrųjų stumti ir pop skambučių ir įsitikinkite, kad viskas eina per visą teisę. Ji taip pat inicijuoja kamino dydis čia todėl jūs neturite jaudintis dėl Inicijuojama, kad. Galite manyti, kad tai buvo tinkamai inicializuoti iki to laiko, kad jūs į jį pop funkcija. Ar tai prasminga? Taigi čia mes einame. Yra push kodas. Aš duosiu jums, vaikinai, 5 ar 10 minučių. Ir jei turite kokių nors klausimų tarpu, o jūs kodavimo, paprašykite, kad garsiai. Taigi, jei jūs gaunate nesutarimų, tiesiog paprašykite. Leiskite man žinoti, tegul visi kiti žino. Dirbti su savo kaimyną. [Daniel] Mes tik įgyvendinimo pop dabar? >> Tiesiog pop. Nors galite kopijuoti tiesioginio įgyvendinimą, jei norite kad bandymai veiks. Nes sunku išbandyti dalykus, nepatektų į arba, sunku patikrinti, Popping dalykų iš kamino, jei įrenginyje nėra nieko pradėti. 

Kas yra pop turėtų grįžti? Iš kamino viršuje elementas. Jis turėjo gauti elementą iš kamino viršuje ir tada Mažėja kamino dydis, ir dabar jūs praradote ant viršaus elementas. Ir tada jums grįžti elementą į viršų. [Studentų, nesuprantamas] [Hardison] Taigi, kas atsitiks, jei jūs darote, kad? [Studentų, nesuprantamas] Kas galų gale vyksta, yra jūs tikriausiai susipažinimo arba elementas, kuris dar nebuvo inicializuoti, kad jūsų skaičiavimas kur pastarasis elementas yra išjungtas. Taigi čia, jei pastebėjote, stumti, mes prieigą prie eilutes tuo s.size elementas , nes tai naujas puslapis. Tai naujas kamino viršuje. Kadangi pop s.size bus kitą erdvę, vietos, kad ant visų savo kamino elementų. Taigi iš viršaus labiausiai elementas nėra stovėjimo s.size, o, tai po juo. 

Kitas dalykas daryti, kai jūs - pop, yra jūs turite Mažėja dydį. Jei prisimenate, atgal į mūsų mažai diagrama čia, tikrai, vienintelis dalykas, kad mes matėme vyksta, kai mes vadinami pop buvo tai, kad šis dydis sumažėjo, visų pirma iki 2, tada 1. Tada, kai mes stumti naują elementą, jis būtų eiti tinkamu vietoje. Bazilikas] Jei s.size yra 2, tada nebūtų it go elementas 2 ir tada jūs norėtumėte, kad pop šis elementas? Taigi, jei mes nuvyko į >> Taigi pažvelkime į tai dar kartą. Jei tai yra mūsų kamino šiuo metu ir mes vadiname pop, indeksas, kuriame yra iš viršaus labiausiai elementas? [Bazilikas] 2, bet jis vyksta, kad pop-3. >> Teisė. Taip, kad kur mūsų dydis yra 3, bet mes norime, pop elemento indeksu 2. Tai, kad tipiškas rūšies išjungti, kad jūs turite su nulinės indeksavimo masyvų. Taigi, jūs norite pop trečiąjį elementą, bet Trečiasis elementas yra ne indeksu 3. Ir priežastis, mes neturime daryti, kad minus 1, kai mes stumti yra todėl, kad dabar, jūs pastebėsite, kad iš viršaus labiausiai elementas, , jei šiuo metu mes buvome nustumti kažką kita ant kamino, mes norime stumti jį indeksuoti 3. Ir ji tiesiog taip atsitinka, kad dydis ir indeksai išsirikiuoti, kai jūs stumti. 

Kas turi darbo kamino įgyvendinimą? Jūs turite darbo sukrauti vieną. Ar turite pop veikia dar? [Daniel] Taip. Manau, kad taip. >> Programos veikia, o ne seg kraigo, tai spausdinti? Ji atsispausdinti "sėkmę", kai jį paleisti? Taip. Padaryti sukrauti, paleisti jį, jei jis spausdina "sėkmę", ir jame nenumatyta jokių bumas, tada viskas gerai. Gerai. Eikime per prietaiso tikrai greitai, ir mes vaikščioti per šį. Jei pažvelgsime į tai, kas vyksta čia su pop, Daniel, kas buvo pirmas dalykas, kad jums padarė? [Daniel] Jei s.size yra didesnis už 0. [Hardison] Gerai. Ir kodėl tu taip padarei? [Daniel] Norėdami įsitikinti, kad ten buvo kažkas viduje kamino. [Hardison] Teisė. Norite patikrinti, įsitikinkite, kad s.size yra didesnis už 0; kitaip, ko tu nori, kad atsitiktų? [Daniel] Grįžti null? >> Grįžti null, tiksliai. Taigi, jei s.size yra didesnis už 0. Tada tai, ką mes ketiname daryti? Ką mes darome,, jei kamino nėra tuščias? [Stella] Mažėja dydį? >> Mažėja dydį, gerai. Taigi, kaip tu tai padarei? >> S.size -. [Hardison] Didysis. Ir tada, ką jūs darote? [Stella] Ir tada aš pasakiau grąža s.string [s.size]. [Hardison] Didysis. Priešingu atveju jums grąžina NULL. Taip, Inga? [Sam] Kodėl ji turi būti s.size + 1? [Hardison], pridėjus 1? >> Taip. >> Supratau. [Sam] Maniau, kad dėl to, kad jūs vartojate 1 iš tada jūs ketinate būti grąžinama ne vieną, kad jie paprašė. [Hardison] Ir tai buvo tik tai, ką mes kalbame apie visą šią išdavimo 0 indeksų. Taigi, jei mes padidinti čia. Jei pažvelgsime į šį vaikiną čia, galite matyti, kad, kai mes pop, mes Popping elementą indeksu 2. 

Taigi, mes sumažinti savo dydį, tada mūsų dydis atitinka mūsų rodyklę. Jei mes neturime Mažėja dydį, tada mes turime padaryti, dydis -1 ir tada silpnėjimas. Didysis. Viskas gerai? Klausimų apie tai? Yra įvairių būdų, rašyti tai, kaip gerai. Iš tiesų, mes galime padaryti kažką dar - mes galime padaryti vieną-LINER. Mes galime padaryti vienos eilutės grąžą. Taigi, mes galime iš tikrųjų Mažėja prieš tai, kad mes grįžtame. Todėl pradėti - prieš s.size. Kad daro linija tikrai tankus. Jeigu skirtumas tarp - S dydžio ir s.size - kad ši postfix - jie vadina tai postfix, nes ateina po s.size - reiškia, kad s.size Vertinamas rasti indeksą nes ji yra šiuo metu, kai ši eilutė yra vykdomas, ir tada tai atsitinka po linija paleidžiama vykdyti. Po to, kai indeksas s.size elementas yra prieinama. Ir tai ne tai, ką norime, nes mes norime Mažėja atsitikti pirmą kartą. Othewise, mes ketiname gauti masyvo, efektyviai, iš ribų. Mes ketiname gauti elementą, kad mes iš tikrųjų norite pasiekti didesnį nei. Taip, Inga? >> Ar greičiau arba naudotų mažiau RAM, kad vienoje eilutėje, ar ne? [Hardison] Sąžiningai, tai tikrai priklauso. [Sam nesuprantamas] >> Taip, jis priklauso. Tai galite padaryti gudrybės kompiliatoriaus gauti kompiliatorius pripažinti, kad, paprastai, aš įsivaizduoti. 

Taigi, mes paminėti šiek tiek apie šį sudarytojas PDA , kad jūs galite padaryti rengiant, ir štai koks dalykas, kad sudarytojas galėtų išsiaiškinti, kaip Oh, hey, gal galite padaryti visa tai per vieną operaciją, o ne pakrovimo kintamąjį dydį iš atminties, decrementing, saugoti jį atgal, ir tada pakrauti jį atgal įvykdyti šios operacijos poilsio. Tačiau paprastai ne, tai ne dalykai kad manimi vyksta gerokai greičiau padaryti savo programą. Turite klausimų kaminai? 

Taip stumti ir Popping. Jei jus vaikinai nori išbandyti programišiaus leidimas, ką mes padarėme hacker leidinyje yra iš tikrųjų dingo ir padarė tai kamino dinamiškai auga. Pagrindinis uždavinys yra visų pirma čia stumianćia funkcija, išsiaiškinti, kaip padaryti, kad masyvas augti kaip jūs nuolat stumia daugiau ir daugiau elementų, kamino. Tai tikrai ne per daug papildomas kodas. Tik skambutis - jūs turite prisiminti, kad gauti skambučius į malloc ten tinkamai, , o tada, kai jūs ketinate skambinti realloc. Tai įdomus iššūkis, jei jus domina. 

Tačiau šiuo metu, galime pereiti ir pakalbėkime apie eiles. Pereikite per čia. Eilė arti kamino Giminystės. Taigi, kamino, tai, kad buvo pateikti praėjusių buvo pirmųjų dalykų, tada būti atgautas. Mes turime tai paskutinė, pirmoji iš arba LIFO, užsakant. Kadangi eilėje, kaip jūs tikitės, kai esate stovėjo eilėje, pirmasis asmuo, gauti linija, pirmas dalykas, kad gauti į eilę, yra pirmas dalykas, kad bus atgautas iš eilės. Eilės taip pat dažnai naudojama, kai mes susiduriame su diagramomis, kaip mes kalbėjome apie trumpai kaminai, ir eilės krūva kitų dalykų taip pat patogu. Vienas dalykas, kad ateina dažnai bando išlaikyti, pavyzdžiui, surūšiuoti elementų sąrašas. Ir jūs galite tai padaryti su masyvo. Galite išlaikyti surūšiuoti sąrašą dalykų, masyvo, bet kur, kad bus sudėtinga, tada jūs visada turite rasti tinkama vieta įterpti į kitą dalyką. Taigi, jei turite skaičių masyvą, nuo 1 iki 10, ir tada jūs norite išplėsti, kad visus numerius 1 per 100, ir jūs gaunate šiuos numerius atsitiktine tvarka ir bando išlaikyti viską surūšiuoti kaip jūs einate per, jūs galų gale padaryti daug perkelia. Eilėse tam tikrų rūšių ir tam tikrų rūšių pagrindinių duomenų struktūrų, jūs iš tikrųjų galite laikyti, kad tai yra gana paprasta. Jūs neturite pridėti kažką ir tada perskirstyti visa tai kiekvieną kartą. Nei jūs turite padaryti daug perkeliant vidaus elementų aplink. Kai mes žiūrime į eilę, jūs pamatysite, kad - taip pat queue.c kodo skirsnyje - struct, kad mes davė jums yra labai panašus į struct, kad mes davė jums kamino. 

Yra viena išimtis, ir kad viena išimtis yra tai, kad mes turime šį papildomą sveikasis skaičius, vadinama galva, ir galva čia yra sekti iš eilės galvą, arba pirmasis elementas eilėje. Su kamino, mes galėjome sekti elementą, kad mes buvo gauti, ar kamino viršaus, naudojant tik dydį, kadangi eilėje, mes susidoroti su galuose. Mes stengiamės pabaigoje pakeisti halsą dalykų, bet tada grįžti dalykų iš priekio. Taip efektyviai, su galva, mes turime eilės pradžioje indeksą, ir dydis mums suteikia eilės galą indeksas taip, kad mes galime gauti dalykų, nuo galvos ir pridėti dalykų prie uodegos. Kadangi, kamino, mes tik kada nors buvo susijusios su kamino viršuje. Mes niekada neturėjo ir atidarykite kamino apačioje. Mes tik daiktus į viršų ir paėmė ko ne viršuje todėl mes nereikėjo kad viduje mūsų struct papildomą lauką. Ar tai apskritai turi prasmę? Gerai. Taip, Charlotte? [Charlotte, nesuprantamas] [Hardison] Tai puikus klausimas, ir tai buvo viena, kad atėjo į paskaitą. Gal vaikščioti per keletą pavyzdžių bus paaiškinta, kodėl mes nenorime naudoti Strings [0] kaip galvos eilės. 

Taigi, įsivaizduokite, kad mes turime eilę, mes ketiname ją vadina eilė. Pradžioje, kai mes ką tik instantiated jį, kai mes ką tik paskelbė jį, mes negalime inicijuoti nieko. Visa tai yra šiukšlių. Todėl, žinoma, mes norime įsitikinti, kad mes inicijuoti dydis ir galvos laukai turi būti 0, kažkas protinga. Mes taip pat galėtų eiti į priekį ir nulis elementus mūsų eilėje. Ir padaryti Ši diagrama tinka, pastebėsite, kad dabar mūsų eilė gali turėti tik tris elementus; kadangi mūsų kamino gali turėti keturis, mūsų eilė gali turėti tik tris. Ir tai tik padaryti diagrama tinka. Pirmas dalykas, kad kas čia vyksta, tai mes į eilę eilutę "labas". Ir kaip mes padarėme su kamino, nieko baisiai skiriasi čia, mes išmetame eilutę stygos [0] ir prieaugio mūsų dydį 1. Mes į eilę "bye", jis bus įdėti. Taigi, tai atrodo, kad didžioji dalis kamino. Mes prasidėjo čia, naujas elementas, naujas elementas, dydis nuolat didėja. Kas vyksta šiuo metu, kai norime dequeue kažką? Kai mes norime dequeue, kuris yra elementas, kad mes norime dequeue? [Bazilikas] Stygos [0]. >> Nulis. Visiškai teisus, bazilikas. Mes norime atsikratyti pirmą eilutę, tai vienas, "Labas". Taigi, kas buvo kitas dalykas, kad pasikeitė? Atkreipkite dėmesį, kai mes popped ką nors ne iš kamino, mes tiesiog pakeičiau dydį, bet čia, mes turime keletą dalykų, kad pokyčiams. Ne tik dydžio keitimą, bet pagrindinis pokyčius. Tai grįžta į Charlotte taško ankstesniu: kodėl mes turime šiuo pagrindu taip pat? Ar tai prasminga dabar, Charlotte? >> Rūšies. [Hardison] rūšis? Taigi, kas atsitiko kai mes dequeued? Ką galva dabar tai yra įdomu? [Charlotte] O, nes ji pasikeitė - gerai. Suprantu. Nes galvos - kur galva yra nukreipta į vietą pokyčius. Tai jau ne nulinis indeksas vienas. >> Taip, tiksliai. Kas atsitiko, jei dequeueing aukštą elementas buvo padaryta ir mes neturėjome Ši galva lauką nes mes visada skambina šią eilutę 0 indeksą mūsų eilėje galvos tada mes turėsime perkelti likusią eilėje. Mes norime turėti perkelti "bye" nuo nuo styginių [1] stygos [0]. Ir styginiams [2], kad stygos [1]. Ir mes norime tai padaryti visą sąrašą elementų, visas masyvo elementų. Ir kai mes tai darome su masyvo, kad bus tikrai brangus. Taigi čia, tai ne big deal. Mes tiesiog turime tris elementus mūsų masyvas. Bet jei mes turėjome tūkstančio elementų eilę arba milijono elementų, ir tada visi staiga, mes pradedame krūva dequeue ragina visus į kilpą, dalykai yra tikrai ketina sulėtinti, nes jo dėka viskas žemyn nuolat. Žinote, perkelti į 1, 1, pamainos poslinkį į 1, perėjimas iš 1. Vietoj to, mes naudojame šią galvą, mes jį vadiname "rodyklė", nors tai tikrai ne rodyklė siaurąja prasme, tai nėra žymeklis tipas. Tai ne int * arba char * ar kas nors panašaus. Bet tai nukreipta arba apie mūsų eilėje galvą. Taip? 

[Studentų] Kaip dequeue žinoti, tiesiog nusibaigti viską, kas į galvą? [Hardison] Kaip dequeue žinoti, kaip nusibaigti viską, kas į galvą? >> Teisė, taip. >> Tai, ką jis žiūri tik kokia galva laukas yra nustatytas. Taigi šiame Pirmuoju atveju, jei pažvelgsime čia, mūsų galvos yra 0, indeksas 0. >> Teisė. [Hardison] Taigi, jis tiesiog sako Gerai, gerai, indeksuoti 0 elementas, eilutė "labas", yra elementas mūsų eilėje galvos. Taigi, mes ketiname dequeue, kad vaikinas. Ir tai bus elementas, kuris bus grąžintas skambinančiajam. Taip, Saad? >> Taigi galva iš esmės nustato - kai jūs ketinate indeksuoti,? Štai ji paleisti? >> Taip. >> Gerai. [Hardison] Tai tampa nauja pradžia mūsų masyvas. Taigi,, kai jums dequeue kažką, viskas, ką jums reikia padaryti yra gauti indeksuoti q.head elementas, ir kad bus elementas, kad norite dequeue. Jūs taip pat turite Mažėja dydį. Mes pamatysime šiek tiek vėliau, kai ko gauti šiek tiek sudėtinga su šia. Mes dequeue, o dabar, jei mes į eilę dar kartą, kur mes į eilę? Kur gi kitas elementas mūsų eilėje? Tarkime, mes norime į eilę eilutę "CS". , Į kurią indeksas bus eiti? [Studentai] Stygos [2]. >> Du. Kodėl 2, o ne 0? [Bazilikas] Nes dabar galva yra 1, todėl, kad kaip sąrašo pradžioje? [Hardison] Teisė. Ir ką žymi sąrašo pabaigą? Ką mes buvome naudojant pažymėti mūsų eilėje pabaiga? Galva yra mūsų eilėje galva, mūsų eilėje pradžia. Kas yra mūsų eilėje pabaiga? [Studentai] Dydis. >> Dydis, tiksliai. Taigi, mūsų nauji elementai eiti dydis ir elementai, kad mes priimame išjungti pleiskanoti galvos. Kai mes į eilę kitą elementą, mes dedame ne dydis. [Studentų] Prieš įdėdami, kad nors dydis buvo 1, į dešinę? [Hardison] Teisė. Taigi, ne visai dydžio. Dydis +, o ne 1, bet + galvos. Kadangi mes persikėlė viską galvos sumą. Taigi čia, dabar mes turime 1 dydžio eilę, kad prasideda indeksas 1. Uodega 2 rodyklėje. Taip? 

[Studentų] Kas atsitinka, kai jūs dequeue stygos [0], ir stygos atminties lizdus tiesiog gauti ištuštinti, iš esmės, arba tiesiog pamiršote? [Hardison] Taip. Šia prasme, mes tiesiog užmiršimo. Jei mes saugoti jų kopijas - daug duomenų struktūras, dažnai saugo savo kopijas elementų valdyti duomenų struktūrą taip, kad asmuo neturi jaudintis apie tai, kur visi tie rodykles. Duomenų struktūra turi, kad viskas, turi visas kopijas, įsitikinti, kad viskas tęsiasi tinkamai. Tačiau šiuo atveju šios duomenų struktūros tiesiog, paprastumo, yra ne todėl, kad mes ją saugoti jų kopijas nieko. [Studentų] Taigi tai yra nuolatinis masyvas? >> Taip. Jei pažvelgsime atgal apibrėžimas buvo šios struktūros, ji yra. Tai tiesiog standartinis masyvas, kaip jūs mačiau, char * s masyvas. Ar tai - >> Aha, man buvo tiesiog įdomu , jei jūs galų gale paleisti iš atminties, tam tikru mastu, , jei turite visus šiuos tuščius dėmės jūsų masyvo? [Hardison] Taip, tai gera vieta. 

Jei pažvelgsime į tai, kas nutiko dabar, šiuo metu, mes užpildyti mūsų eilėje, jis atrodo. , Bet mes tikrai ne užpildyti mūsų eilę nes mes turime eilę, kad 2 dydis, bet ji prasideda indeksas 1, nes tai kur mūsų galvos rodyklė. Kaip jums sakydamas, kad stygos elemento [0], indeksuoti kaip 0, tai tikrai ne ten. Tai ne mūsų eilėje nebėra. Mes tiesiog nesivargino eiti ir ją perrašyti kai mes dequeued. Taigi, nors atrodo, kad mes paleisti iš atminties, mes tikrai ne. Kad vietoje mums naudoti. Tinkamas elgesys, jei mes buvo išbandyti ir pirmasis dequeue kažką patinka "bye", kad pop-bye išjungtas. Dabar mūsų eilė prasideda indeksu 2 ir 1 dydžio. Ir dabar, jei mes stengiamės ir į eilę vėl kažką, tarkim, 50, 50 turėtų eiti šioje vietoje indeksuoti 0 , nes jis vis dar pasiekiamas mums. Taip, Saad? [Saad] Ar, kad taip atsitiktų? [Hardison] Ji nėra atsitikti gana automatiškai. Jūs turite padaryti matematiką padaryti jį dirbti, tačiau iš esmės, ką mes padarėme, mes tiesiog suvynioti aplink. [Saad] Ir tai gerai, jei tai turi skylę jos viduryje? [Hardison] Tai jei mes galime padaryti matematikos dirbti tinkamai. 

Ir paaiškėja, kad tai iš tikrųjų ne tai, kad sunku padaryti su mod operatoriumi. Taigi, tiesiog, kaip mes padarėme su Cezario ir šifravimo stuff naudojant mod, mes galime gauti dalykų, į kuriuos vyniojami aplink ir nesustoti aplink ir aplink ir aplink su mūsų eilėje, kad galva rodyklė juda. Pastebėti, kad dydis yra visada atsižvelgiant į faktiškai elementų skaičių eilėje. Ir tai tik galva rodyklę, kad toliau važiuoti dviračiu per. Jei pažvelgsime, kas čia nutiko, jei mes einame atgal į pradžią, ir jūs tiesiog žiūrėti, kas atsitinka į galvą kai mes į eilę kažką, nieko neatsitiko į galvą. Kai mes enqueued ką nors kita, nieko neatsitiko į galvą. Greitai, kaip mes dequeued kažką, galva eina vieną. Mes enqueued kažką, nieko neįvyksta į galvą. ,, Kai mes dequeue kažką, visi staiga galva bus padidinamas. Kai mes į eilę kažką, nieko neįvyksta į galvą. 

Kas nutiktų, šiuo metu, jei mes kažką vėl dequeue? Bet mintis? Kas nutiktų, į galvą? , Kas turėtų atsitikti į galvą jei mes dequeue ką nors kita? Galva dabar yra indeksu 2, , o tai reiškia,, kad eilėje galva stygos [2]. [Studentų] Kuris grąžina 0? >> Jis turėtų grįžti iki 0. Jis turi zawijać atgal aplink, tiksliai. Iki šiol, kiekvieną kartą, kai mes vadinami dequeue, mes jau pridedant vieną į galvą, pridėti į galvą, pridėti vieną į galvą, pridėti vieną į galvą. Kuo greičiau, kad galva rodyklė gauna iki paskutinės indekso mūsų masyvas, tada mes turime wrap jį atgal aplink į pradžią, grįžkite į 0. [Charlotte] Kas lemia gebėjimus kamino eilėje? Šiuo atveju [Hardison], mes ką tik naudoju # apibrėžta konstanta. >> Gerai. [Hardison] faktinis c failas, galite eiti ir mėžti su juo šiek tiek ir padaryti jį tokie dideli, arba kiek norite. [Šarlotės "] Taigi, kai jūs darote eilę, kaip jūs, kad kompiuteris žinoti kaip didelis norite kamino? [Hardison] Tai puikus klausimas. Yra keletas būdų. Vienas iš jų yra tiesiog nustatyti jį iš anksto ir pasakyti, kad tai bus eilė, kuri turi 4 elementus arba 50 elementų arba 10.000. Kitas būdas yra daryti tai, ką įsilaužėlių leidimas žmonės daro ir sukurti funkcijas jūsų eilė dinamiškai auga daugiau dalykų, gauti papildomas. 

[Šarlotės "] Taigi eiti su pirmąjį variantą, ką sintaksė naudoti pasakyti programą, kas yra eilėje dydis? [Hardison] Ah. Taigi galime gauti iš to. Aš vis dar stack.c čia, todėl aš tik ketina slinkite aukštyn į viršų. Jūs galite pamatyti šią teisę? Tai # define capacity 10. Ir tai yra beveik tiksliai sintaksė, kad mes turime eilę. Išskyrus eilėje, čia mes turime, kad papildomų struct lauką. [Charlotte] O, aš maniau, talpa reiškė styginių gebėjimus. [Hardison] Ah. >> Kad tai didžiausias ilgis žodžio. >> Supratau. Taip. Pajėgumai čia - tai puikus taškas. Ir tai yra kažkas, kad sudėtinga , nes tai, ką mes nurodomas čia yra char * s masyvas. Patarimų masyvas. Tai simbolių masyvas. Tai tikriausiai yra tai, ką mačiau, kai jūs buvote, skelbiantis savo buferius failui I / O, kai jūs buvo sukurti eilutes rankiniu būdu ant kamino. Tačiau tai, ką mes turime čia, yra char * s matrica. Todėl masyvas rodykles. Tiesą sakant, jei mes padidinti atgal ir mes pažvelgti į tai, kas vyksta čia į pateiktį, pamatysite, kad faktinius elementus, simbolis duomenų nėra saugomas pačiame masyve. Kas saugomi mūsų masyvas rodykles į simbolių duomenis. Gerai. Taigi mes matėme, kaip eilės dydis kaip ir su kamino, dydis visada gerbia elementų skaičių eilėje. Atlikę 2 enqueues, dydis 2. Po priėmimo dequeue dydis yra dabar 1. Atlikę kitą į eilę dydis yra iki 2. Taigi dydis tikrai gerbia elementų skaičių eilėje, ir tada galva tiesiog išlaiko dviračiu. Ji eina nuo 0-1-2, 0-1-2, 0-1-2. Ir kiekvieną kartą, mes vadiname dequeue, galva žymeklis bus padidinamas iki kito indekso. Ir jei galva yra apie eiti per, kilpos atgal apie 0. Taigi su tuo, mes galime rašyti dequeue funkciją. Ir mes ketiname išvykti į eilę funkciją jus vaikinai įgyvendinti vietoj. 

Kai mes dequeue elementą iš mūsų eilėje, tai, kas buvo pirmas dalykas, kad Danielis, kai mes pradėjome rašyti pop funkcija kaminai? Leiskite man išgirsti ką nors, kas dar nebuvo kalbama. Pažiūrėkime, Saad, ar tu prisimeni, ką Daniel padarė taip, kaip pirmas dalykas, kai jis rašė pop? [Saad] Taip, tai buvo - >> Jis išbandyti ko nors. [Saad] Jei dydis yra didesnis už 0. >> Būtent. Ir kas buvo, kad bandymai? [Saad] Tai buvo bandymai, norėdami pamatyti, jei nėra nieko viduje masyvo. [Hardison] Taip. Tiksliai. Todėl jūs negalite jų pop nieko iš kamino, jei ji tuščia. Be to, galite ne dequeue nieko iš eilės, jei ji tuščia. Koks yra pirmas dalykas, kurį turėtume daryti mūsų dequeue funkciją čia, jūs manote? [Saad] Jei dydis yra didesnis nei 0? >> Taip. Šiuo atveju, aš iš tikrųjų tiesiog išbandyti, kad pamatyti, jei ji yra 0. Jei jis yra 0, mes galime grąžina NULL. Bet patį logika. Ir tegul toliau su šiuo. Jei dydis yra ne 0, kur yra elementas, kad mes norime dequeue? [Saad] į galvą? >> Būtent. Mes galime tiesiog ištraukite pirmasis elementas mūsų eilėje gauti elementą į galvą. Nieko iš proto. Po to, ką mes turėtume daryti? Kas turi atsitikti? Koks buvo kitas dalykas, kad mes kalbėjome apie dequeue? Du dalykai, kuriuos turi įvykti, nes mūsų eilė pasikeitė. [Daniel] sumažinti dydį. >> Mes turime sumažinti dydį ir padidinti galvą? Tiksliai. Norėdami padidinti galvą, mes galime ne tik aklai didinti galvą, prisiminti. Mes galime ne tik padaryti queue.head + +. Mes taip pat įtraukti šį pajėgumų mod. Ir kodėl mes mod pajėgumų, Stella? [Stella] Nes ji turi į kuriuos vyniojami aplink. >> Būtent. Mes mod pajėgumų, nes ji turi, į kuriuos vyniojami aplink 0. Taigi dabar, šiuo metu, mes galime daryti tai, ką Danielius sakė. Mes galime Mažėja dydį. Ir tada mes galime tiesiog grįžti elementas, kuris buvo į eilę viršuje. Atrodo mielas nesukalbamas ne pirmas. Jums gali tekti klausimą. Sorry? 

[Sam] Kodėl pirmą į eilę viršuje? Kur tai eiti? [Hardison] Jis kilęs iš ketvirtoje eilutėje nuo apačios. Po to, kai mes išbandyti, įsitikinti, kad mūsų eilė nėra tuščias, mes ištraukti char * pirma, mes ištraukti elementas, kuris sėdi prie galvos indeksas mūsų masyvas, mūsų styginiams masyvo, >> ir skambučiu, kuris pirmą kartą? [Hardison] Ir mes vadiname ji pirmą kartą. Taip. Tik imtis tolesnių veiksmų, kad, kodėl manote, kad mes turėjome padaryti, kad? [Sam] kiekvieną pirmą tik grįžau q.strings [q.head]? >> Taip. >> Kadangi mes darome, tai, kad q.head mod funkcija keičiasi, ir nėra jokio būdo tai padaryti, kad grįžtamosios linijos, taip pat. [Hardison] Būtent. Jūs esate vietoje. Sam visiškai vietoje. Priežastis, kodėl mes turėjome ištraukti pirmasis elementas mūsų eilėje ir laikyti jį į kintamąjį nes šią eilutę, jei mes ką tik q.head ten mod operatorius ten nėra kažkas, kad mes galime padaryti ir kad jis įsigalioja ant galvos be - vienoje eilutėje. Taigi, mes iš tikrųjų turime ištraukti pirmąjį elementą, tada koreguoti galvą, reguliuoti dydį, o tada grįžti elementą, kad mes ištraukė. Ir tai yra kažkas, kad mes pamatysime sugalvoti vėliau su susiję sąrašai, kaip mes pažaisti su jais. Dažnai, kai jūs atlaisvinti arba šalinimo sujungtų sąrašų jums reikia prisiminti kitą elementą, kitą žymiklį susietą sąrašą Prieš išmesdami dabartinės. , Nes priešingu atveju jūs išmesti informaciją apie tai, kas liko sąraše. Dabar, jei jūs einate į savo prietaiso, jums atverti queue.c--x tai. Taigi, jei aš atverti queue.c, leiskite man padidinti čia, pamatysite, kad jūs turite panašios išvaizdos failą. Panašios išvaizdos failą, ką turėjome anksčiau su stack.c. Mes turime mūsų struct eilėje apibrėžta tiesiog kaip matėme skaidres. 

Mes turime į eilę funkciją, kuri jums reikia padaryti,. Ir mes turime dequeue funkciją čia. Neįgyvendintos dequeue faile yra funkcija, bet aš įdėti ją atgal į viršų į "PowerPoint", taip, kad jūs galite įvesti jį, jei norite. Taigi per ateinančius 5 minučių arba tiek, jus vaikinai dirbti į eilę kuris yra beveik tik, priešais dequeue. Jūs neturite reguliuoti galvą, kai jūs enqueueing, bet ką turite koreguoti? Dydis. Taigi, kai jums į eilę, galva lieka nepaliesti, dydis bus pakeistas. Tačiau ji šiek tiek - galėsite pažaisti su tuo mod išsiaiškinti tiksliai indeksas naujasis elementas turi būti įrašomas. Taigi, aš duosiu jums, vaikinai, šiek tiek, įdėti dequeue atgal skaidrę, ir kaip jūs vaikinai turite klausimų, šaukti juos taip, kad galėtume visi apie juos kalbėti, kaip grupė. Be to, su dydžio jums NeraŠykiTe - kai jūs reguliuoti dydį, visada galite tiesiog jūs turite mod dydį kada nors? [Daniel] L. >> Jūs neturite mod dydį, teisė. Nes dydis visada bus, jei Tu - darant prielaidą, kad jūs valdymo dalykus tinkamai, dydis visada bus tarp 0 ir 3. Kur jūs turite mod, kai jūs darote į eilę? [Studentų] Tik už galvos. >> Tik už galvos, tiksliai. Ir kodėl jūs turite mod visi į eilę? Kai yra situacija, kurioje jūs turite mod? [Studentų] Jei turite stuff tarpų, pavyzdžiui, patalpos 1 ir 2 dalių, ir tada jums reikia pridėti kažką esant 0. [Hardison] Taip, būtent. Taigi, jei jūsų pagrindinė žymeklis yra pačioje pabaigoje, arba, jei jūsų dydis plius jūsų galva yra didesnis arba, tiksliau, į kuriuos vyniojami aplink eilėje. 

Taigi, šioje situacijoje, kad mes atsikėlė čia skaidrėje dabar, jei aš noriu į eilę kažką dabar, mes norime į eilę kažką indeksuoti kaip 0. Taigi, jei jums pažvelgti į kai 50 eina, ir aš skambinti į eilę 50, jis eina ten apačioje. Jis eina indekso 0. Ji pakeičia "Labas", kuri jau buvo dequeued. [Daniel] Ar ne jūs rūpintis, kad dequeue jau? Kodėl tai nieko daryti su į eilę galvos? [Hardison] Oi, todėl jūs ne keisti galvą, atsiprašau. Bet jūs turite naudoti mod operatorių, kai bandote pasiekti elementas, kad jūs norite į eilę, kai bandote pasiekti kitas elementas į savo eilę. [Bazilikas] aš ne daryti, kad ir aš "sėkmę" ten. [Daniel] O, aš suprantu, ką jūs sakote. [Hardison] Taigi jums didn't - tiesiog padarė gresia q.size? [Bazilikas] Taip. Aš tik pasikeitė pusių, aš ne daryti nieko su galva. [Hardison] Jūs neturite iš tikrųjų turi iš naujo galvą į ką nors, bet kai jūs puslapis į styginiams masyvo, jūs iš tikrųjų eiti į priekį ir apskaičiuoti, kur kito elemento, nes vytelė kitas elementas Jūsų žetonų krūvą, visada buvo indekso atitinkamu dydžio. Jei pažvelgsime atgal į viršų mūsų kamino stumti funkcija, mes visada galėtų Nogāzt mūsų naują elementą į dešinę indekso dydis. Kadangi eilėje, mes negalime padaryti, kad nes jei mes šioje situacijoje, jei mes enqueued 50 mūsų nauja eilutė būtų eiti į dešinę stygos [1] , kurios mes nenorime daryti. Mes norime, kad naujos eilutės eiti indeksuoti kaip 0. 

Ar kas nors taip? [Studentų] Turiu klausimą, bet tai tikrai nėra susiję su. Ką tai reiškia, kai kažkas tiesiog reikia kažką panašaus pred rodyklė? Kas yra tas pavadinimas, trumpas? Aš žinau, tai tik pavadinimas. [Hardison] Pred žymiklis? Pažiūrėkime. Kokiame kontekste? [Studentų] Tai buvo įterptos sekos. Galiu paprašyti jus, jei tik norėsite , nes jis nėra iš tikrųjų susijęs su, bet aš tiesiog - [Hardison] Nuo Dovydo įterpti kodą iš paskaitos? Mes galime traukti kad ir kalbėti apie tai. Mes kalbame apie tai, kad kita, kai mes gauti susietų sąrašus. 

Todėl galime labai greitai pažvelgti ką į eilę funkcija atrodo. Koks buvo pirmas dalykas, kad žmonės bandė padaryti savo į eilę eilutėje? Į šią eilę? Panašus į tai, ką padarė kamino stumia. Ką jūs darėte, Stella? [Stela, nesuprantamas] [Hardison] Būtent. Jei (q.size == TALPA) Man reikia įdėti savo petnešos tinkamoje vietoje - return false. Šiek tiek padidinti. Gerai. Dabar, kas Kitas dalykas, kad mes turėjome daryti? Kaip ir su į steką, ir įterpiamos reikiamoje vietoje. Ir kas buvo tinkama vieta, įterpti, kad? Kamino indekso dydis, su šiuo, tai ne gana, kad. [Daniel] Turiu q.head--- >> q.strings? >> Taip. q.strings [q.head + q.size mod TALPA]? [Hardison] Mes tikriausiai norite įdėti skliaustus aplink kad mes gauti atitinkamą pirmenybę ir kad cleart visiems. Ir nustatyti, kad lygios? >> STR? >> G. Didysis. Ir dabar, kas yra paskutinis dalykas, kad mes turime padaryti? Tiesiog, kaip mes padarėme kamino. >> Prieaugio dydį? >> Prieaugio dydį. Bumas. Ir tada, nuo starterio kodą ką tik grįžo klaidinga pagal nutylėjimą, mes norime pakeisti tai tiesa, jei viskas praeina ir viskas bus gerai. Gerai. Tai yra daug informacijos skyriuje. Nesame visiškai per. Mes norime, kad tikrai greitai kalbėti apie atskirai susijusių sąrašus. Aš įdėti tai, kad mes galime grįžti į ją vėliau. Bet grįžkime tik keli mūsų pristatymo skaidres. Taigi į eilę yra TODO, dabar mes tai padarėme. 

Dabar galime imtis atskirai susijusių sąrašus išvaizdą. Mes kalbėjome apie tai šiek tiek daugiau paskaitą. Kiek iš jūsų vaikinai pamatė demo, kur mes turėjome žmonių nerangiai nukreipta vieni su kitais ir ūkis skaičių? >> Buvau, kad. >> Ką jūs manote? Ar, tikiuosi paprastai paaiškinti šias šiek tiek? Su sąrašu, paaiškėja, kad turime kovoti su tokio tipo, kad mes ketiname skambinti mazgas. Kadangi, eilėje ir dėklą mes turėjome structs, kad mes norime skambinti eilę kamino, mes turėjome šias naujas kamino tipų eilę, Čia sąrašas yra tikrai ką tik padarė mazgų krūva. Tuo pačiu būdu, kad eilutės yra tik simbolių krūva visi išsirikiavo viena šalia kitos. Susijęs sąrašas yra tik mazgas ir kitas mazgas ir kitas mazgas ir kitas mazgas. Ir, užuot Smashing visus mazgus kartu ir saugoti juos Kaimynystėje viskas gerai šalia vienas kito atmintyje, tai kitą žymeklį leidžia mums laikyti mazgai visais atvejais, kai atsitiktinai. Ir tada natūra vielos juos visus kartu, kad iš vieno į kitą. 

Ir kas buvo didelis privalumas, kad tai turėjo per masyvo? Kaimynystėje tiesiog pakimba per laikymo viskas vienas šalia kito? Jūs prisimenate? Taip? >> Dinaminis atminties paskirstymas? >> Dinaminis atminties paskirstymas, kokia prasme? [Studentų], kad galite laikyti, kad ji didesnė ir jūs neturite perkelti savo visą masyvą? [Hardison] Būtent. Taigi su masyvo, kai norite įdėti naują elementą į jo viduryje, jūs turite perkelti viską, kad vietos. Ir, kaip mes kalbėjome apie tai su eilės Štai kodėl mes išlaikyti, kad galvos žymeklį, todėl, kad mes ne nuolat kinta dalykų. , Nes tai tampa brangus, jei jūs turite didelis masyvas ir jūs nuolat daryti šiuos atsitiktinius įterpia. Kadangi su sąrašu, viskas, ką jums reikia padaryti, yra mesti jį į naujas mazgas, nustatyti patarimų, ir baigsite. Kas sucks apie tai? Be tai, kad tai nėra taip lengva dirbti su masyvo? Taip? [Daniel] Na, manau, tai daug sunkiau pasiekti tam tikrą elementą į susietą sąrašą? [Hardison] Jūs galite ne tik pereiti į savavališkai elementas susieta "sąrašą viduryje. Kaip jūs turite padaryti, vietoj to? >> Jūs turite žingsnis per visą dalykas. [Hardison] Taip. Jūs turite eiti per vieną vienu metu, vienu metu. Tai didžiulis - tai skausmas. Kas kita - yra dar vienas nuopuolis į. [Bazilikas] Tu negali eiti į priekį ir atgal? Jūs turite eiti viena kryptimi? [Hardison] Taip. Taigi, kaip mes sprendžiame, kad kartais? [Bazilikas] Dvigubai susijusi sąrašus? >> Būtent. Yra dvigubai susijusių sąrašai. Taip pat yra - Atsiprašau? 

[Sam] Ar tai tas pats, kaip ir naudojant pred dalykas, kad Aš tiesiog prisiminiau, yra ne tai, ko Pred dalykas yra? Yra ne tai, kad tarp dvigubai ir atskirai? [Hardison] Pažvelkime, ką tiksliai jis daro. Taigi čia mes einame. Štai jų sąrašas kodas. Čia mes turime predptr čia. Tai yra tai, ką mes kalbame apie? Taigi tai buvo - jis atlaisvinus sąrašą ir jis bando laikyti rodyklę į jį. Tai ne dvigubai, atskirai susijusias sąrašai. Mes galime kalbėti daugiau apie tai vėliau, nes tai kalbame apie atlaisvinus sąrašą ir aš noriu parodyti kai kurių kitų dalykų. bet tai tik - tai prisimindamas ptr vertę [Studentų] O, tai ankstesniuose rodyklė? >> Taip. , Kad galėtume tada prieaugio PTR pati, kol mes tada laisvai, ką predptr. Kadangi mes negalime laisvai PTR ir tada paskambinti ptr = PTR kitą, tiesa? , Kad bus blogai. Taigi pažiūrėkime, šis vaikinas. 

Kitas blogas dalykas apie sąrašus, yra tas, kad su masyvo mes tiesiog turime visus elementus patys sukrauti vienas šalia kito, čia mes taip pat įvedė šį žymeklį. Taigi ten papildoma atminties riekė, kad mes naudoti kiekvieno elemento, kad mes ją saugoti mūsų sąraše. Mes gauname lankstumą, tačiau jis ateina į sąnaudas. Jis ateina su šio laiko sąnaudų, ir ji ateina su šią atminties sąnaudos. Laikas ta prasme, kad dabar mes turime pereiti per kiekvieno elemento masyve rasti 10 indeksuoti vieną, arba kad būtų buvę 10 puslapis masyvo. 

Tiesiog tikrai greitai, kai mes schema šiuos sąrašus, paprastai mes laikomės to sąrašo vadovo arba pirmą sąrašo rodyklė ir atkreipkite dėmesį, kad tai yra tiesa, rodyklė. Tai tik 4 baitų. Tai nėra tikrasis mazgas pati. Taigi, kaip matote, kad jis neturi int vertę, be kita žymiklį į jį. Tiesiogine prasme tai tiesiog rodyklė. Ji ketina atkreipti dėmesį į kažką, kad yra tikrasis mazgas struct. [Sam] rodyklė vadinama mazgas? >> Tai - ne. Tai yra rodyklė į kažką tipo mazgas. Tai yra rodyklė į struct mazgas. >> O, gerai. Diagrama kairėje dešinėje, kodas. Mes galime nustatyti NULL, kuris yra geras būdas pradėti. Kai jūs diagrama jį, jūs arba rašyti netekusiais arba jūs įtraukėte liniją per jį, kaip kad. 

Vienas iš paprasčiausių būdų, kaip dirbti su sąrašais, ir mes prašome, jūs tiek pridėkite ir prie pamatyti skirtumus tarp dviejų, bet prieš atitinkamai yra tikrai lengviau. Pridėkite iki keliu ženklas, tai kur jūs - kai jūs pridėkite (7), jūs einate ir sukurti mazgas struct ir jūs pirmiausia reikia priminti tai, nes dabar, nes mes jį pridėtas pradžioje, tai bus sąrašo pradžioje. Jei mes pridėkite (3), kuri sukuria kitą mazgą, bet dabar 3 ateina iki 7. Taigi mes iš esmės stumti dalykų į mūsų sąrašą. Dabar, jūs galite pamatyti, kad pridėkite, kartais žmonės ją vadina stumti, nes jūs stumti naują elementą į savo sąrašą. Tai taip pat lengva ištrinti sąrašo priekyje. Todėl žmonės dažnai skambinti, kad pop. Ir tokiu būdu, jūs galite rungtyniauti kamino, naudojant susietą sąrašą. Šūksniais. Atsiprašome, dabar mes vis į APPEND. Taigi čia mes pridėtas pradžioje (7), dabar mes pridėkite (3). Jei mes pridėtas pradžioje kažką kita į šį sąrašą, jei mes pridėtas pradžioje (4), tada mes norime turėti 4 ir 3 ir 7. Taip, tada mes galėtume pop ir pašalinti 4 3, pašalinti, pašalinti 7. Dažnai labiau intuityvus būdas galvoti apie tai su papildymo. Taigi aš diagrammed, ką jis atrodys su pridėti čia. Čia, pridedama (7) neturi atrodo kitoks nes ten yra tik vienas elementas sąraše. Ir papildymo (3) pradedančiam jį pabaigoje. Gal galite pamatyti dabar triuką su papildymo yra tai, kad, nes mes tik žinoti, kur sąrašo pradžioje, pridėti į sąrašą, jūs turite vaikščioti visą kelią per sąrašą gauti iki galo, sustabdyti, tada sukurti savo mazgas ir Nogāzt viskas žemyn. Viela visų dalykų. Taigi su Dėti mes tiesiog neveikiančių tikrai greitai, pridėkite iki keliu ženklas į sąrašą, tai gana paprasta. 

Jums padaryti jūsų naują mazgas, įtraukti tam tikrą dinaminį atminties paskirstymas. Taigi čia mes darome mazgo struct naudojant malloc. Taigi malloc mes naudojame, nes tai bus atidėta atminties mus ateičiai nes mes nenorime, kad tai - mes norime, kad ši atmintis išlieka ilgą laiką. Ir mes gauti žymiklį į atminties erdvę, kad mes tiesiog skirtos. Mes naudojame mazgo dydį, mes neturime susumuoja laukus. Mes neturime rankiniu būdu generuoti baitų skaičių, vietoj to, mes naudojame sizeof, kad mes žinome, kad gaunate atitinkamą skaičių baitų. Mes įsitikinkite, kad patikrinti, kad mūsų malloc skambutis pavyko. Tai yra kažkas, ką norite daryti apskritai. Modernios mašinos, nėra kažkas, kad lengva iš atminties , nebent esate skirti daiktų toną ir didžiulis sąrašas, tačiau, jei esate pastate dalykų, tarkim, kaip "iPhone" ar "Android", jūs turite ribotą atminties išteklių, ypač jei jūs darote kažką intensyvus. Todėl gerai gauti į praktiką. 

Atkreipkite dėmesį, kad aš naudojamas keletą skirtingų funkcijų , kad jūs matėte, kad yra tam tikros naujos. Taigi fprintf yra kaip printf išskyrus pirmojo argumento yra srautas, į kurią norite spausdinti. Šiuo atveju, mes norime spausdinti į standartinį klaidų eilutę kuris yra skiriasi nuo standartinės outstream. Pagal nutylėjimą ji pasirodo toje pačioje vietoje. Ji taip pat spausdina į terminalą, bet jūs galite naudojant šias komandas jums sužinojau apie, peradresavimo metodus sužinojote apie Tommy vaizdo problemą, 4, galite nukreipti ją įvairių sričių, tada išeiti, čia, išėjimai jūsų programa. Tai iš esmės kaip grįžęs iš pagrindinių, išskyrus mes naudojame išėjimą nes čia grąža nebus nieko. Mes ne pagrindinis, todėl grįžti nėra išeiti iš programos, kaip mes norime. Todėl mes naudojame išėjimo funkciją ir suteikia jai klaidos kodą. Tada čia mes nustatome naujas mazgas lauke vertė "i lauko turi būti lygus i, ir tada mes vielos jį. Mes nustatėme naujas mazgas kitą žymiklį pirmiausia, ir tada pirma į naujas mazgas. Šie pirmieji eilučių kodo, mes iš tikrųjų sukurti naują mazgas. Ne paskutinis dvi eilutės šios funkcijos, tačiau pirmieji. Jūs iš tikrųjų galite ištraukti į funkciją, į pagalbininkas funkcija. Kad dažnai tai, ką darau, aš traukti ją į funkciją, Aš tai vadinu kažką panašaus statyti mazgo, ir kuri išlaiko pridėkite funkcija gana mažas, tai tik tada 3 linijos. Skambinti mano statyti mazgo funkciją, ir tada aš vielos viską aukštyn. 

Paskutinis dalykas, aš noriu parodyti jums, ir aš jums pridėti ir visa tai dėl savo, yra, kaip pakartoti per sąrašą. Yra daug įvairių būdų, kad paeiliui per sąrašą krūva. Šiuo atveju, mes ketiname rasti sąrašą ilgis. Taigi mes pradedame ilgio = 0. Tai yra labai panašus strlen raštu eilutę. Tai, ką aš noriu parodyti jums, tai už linijos čia. Atrodo kinda funky, tai nėra įprasta, int i = 0, i <kokia, aš + +. Vietoj to jis Inicijuojama mūsų kintama n turi būti sąrašo pradžioje. Ir tada, o mūsų iteratorius kintamasis nėra lygus nuliui, mes nuolat vyksta. Taip yra todėl, kaip įprasta, mūsų sąraše pabaiga bus niekinis. Ir tada prieaugio, o ne daro + + susijęs sąrašas atitikmuo + + n = n-> Kitas. 

Aš jums užpildyti spragas čia, nes mes iš laiko. Bet turėti tai omenyje, kaip jūs dirbate savo spellr psets. Susietos sąrašai, jei jūs įgyvendinimo maišos lentelę, tikrai ateis labai patogu. Ir šį tarmės kilpų užkliuvę, kad gyvenimas daug lengviau, tikiuosi. Bet kokių klausimų, greitai? [Sam] Ar galite atsiųsti užpildytą SLL ir SC? [Hardison] Taip. Aš atsiųsime užpildytus skaidres ir užpildytą SLL kamino ir queue.cs. [CS50.TV]