[Powered by Google Translate] [Oddelek 6: Manj udobno] [Nate Hardison] [Harvard University] [To je CS50.] [CS50.TV] V redu. Dobrodošli v oddelku 6. Ta teden bomo lahko govorili o podatkovnih struktur v oddelku, predvsem zato, ker ta teden problem, nastavljeno na spellr pa cel kup različnih podatkov raziskovanja strukture. Obstaja kup različnih načinov, kako lahko gredo s problemskega sklopa, in več kot podatkovne strukture poznate, bolj kul stvari, ki jih lahko storite. 

Torej, začnimo. Najprej bomo govorili o skladih, Sveženj in vrsta podatkovne strukture, da bomo govorili o. Skladovnice in vrste so res v pomoč, ko bomo začeli govoriti o grafih, ki nismo naredili toliko prav zdaj. Ampak oni so res dobro razumeti enega od velikih temeljnih podatkovnih struktur CS. Opis v opredelitvi težave set, če ga dvigni, govori o skladih so podobna Kup jedilnico pladnjev, da imate v kavarni na jedilnih dvorane če, ko je osebje prihaja jedilnico in restavracij postavlja pladnje od dneva, ko ste jih očisti, so jim nalagajo eden na drugega. In potem, ko otroci pridejo, da bi dobili hrano, vlečejo pladnje off, prvi vrh 1, potem tisti pod njim, potem pa tisti, ki v nadaljevanju. Torej, v bistvu, prvi pladenj, da je osebje, jedilnica odložil je zadnja, ki dobi vzletelo. Zadnji je, da je jedilnica zaposlene delavce in je prva, ki dobi vzletelo za večerjo. V določilu je problem podloga, ki jo lahko prenesete, če tega še niste storili, govorimo o modeliranje stucture žetonov podatkov z uporabo te vrste struct. 

Torej, kaj imamo tukaj, to je podoben temu, kar je bilo predstavljeno v predavanju razen v predavanju smo predstavili to z ints v nasprotju z char * s. To se bo sveženj, ki shranjuje kaj? Daniel? Kaj pa shranjevanje v tem kupu? [Daniel] Strings? >> Smo shranjevanje nize v tem kupu, točno. Vse, kar morate imeti, da bi ustvarili sveženj je matrika določene zmogljivosti, ki je v tem primeru, Zmogljivost se bo v vseh kape, ker je konstantna. In potem poleg matrike, vse, kar potrebujete za sledenje je sedanja velikost matrike. Ena stvar, ki sem seznanjen, da je nekako kul je, da smo ustvariti podatkovno strukturo zložene na vrhu druge strukture podatkov, array. Obstajajo različni načini za izvajanje nizov. Tega ne bo naredil še čisto, vendar upam, da po tem, ko delaš povezanost seznam težav, boste videli, kako lahko enostavno izvajati sveženj na vrhu seznama povezan tudi. Ampak za zdaj se bomo lotili z nizi. Torej, še enkrat, vse, kar potrebujete, je polje in smo morali slediti velikost matrike. [Sam] Žal mi je, kako to, da ste rekli, da je sklad na vrhu strune? To se mi zdi kot niza sta v dimnik. [Hardison] Ja. Ustvarjamo, smo ob naši strukturo niza podatkov - To je veliko vprašanje. Torej, vprašanje je, zakaj je za ljudi, ki so gledali to na spletu, Zato smo pravi, da je sveženj na vrhu nizov, ker tukaj izgleda niza sta v notranjosti kup? Kar je popolnoma res. Kaj sem mislil, da je bila, da smo dobili strukturo niza podatkov. Imamo celo vrsto char * s, ta polja nizov, in se bomo dodati, da je za ustvarjanje zložene podatkovno strukturo. 

Torej sklad je nekoliko bolj zapletena, kot matriko. Mi lahko uporabite niz za izgradnjo dimnika. Torej, to je, če rečemo, da je sklad, zgrajena na vrhu matrike. Prav tako, kot sem že dejal, smo lahko zgradili kup na vrhu seznama povezan. Namesto s paleto, da imajo naše elemente, da bi nam povezan seznam, da imajo svoje elemente in graditi dimnika okoli tega. Sprehodimo se skozi nekaj primerov, ki si ogleduje nekatere oznake, videli, kaj se dejansko dogaja tukaj. Na levi strani, sem vrgel dol, kaj bi to kup struct videti v spomin če bi bila kapaciteta # opredeljen kot štiri. Imamo svojo 4-element char * niz. Imamo strune [0] strune [1], strune [2], strune [3] in potem zadnji prostor za našo velikost celo število. Ali je to smiselno? Ok. To je tisto, kar se zgodi, če kaj naredim na desni strani, ki bo moja koda, je le razglasi struct, zložene struct imenovan s. To je tisto, kar smo dobili. Določa to sled v spominu. Prvo vprašanje je, kaj je vsebina tega dimnika struct? Zdaj oni nič, ampak oni niso popolnoma nič. Oni te vrste smeti. Nimamo pojma, kaj je v njih. Ko smo se ugotovi dimnih s, smo šele metanje navzdol, da na vrhu pomnilnika. To je nekako tako kot razglasitvi int i in ne inicializira. Saj ne vem, kaj je notri. Si lahko preberete, kaj je notri, a ne bi bilo super pomoč. Ena stvar, ki jo želite, da se vedno spomnim na to, kar je inicializirati treba inicializirati. V tem primeru bomo za inicializacijo velikosti nič, ker to se bo izkazalo, da je za nas zelo pomembno. Mi lahko gredo naprej in inicializacijo vse napotke, vse char * i, da so nekateri razumljivo vrednost, verjetno ničen. Ampak to ni povsem nujno, da to storimo. 

Zdaj, dve glavni dejavnosti na kupih so? Vsakdo spomnite iz predavanja, kaj storiti s nizov? Ja? [Stella] Potiskanje in živahen? >> Točno tako. Potiskanje in živahen sta dve glavni dejavnosti na dimnikih. In kaj storiti, pritisk? >> Postavlja nekaj na vrhu iz dimnika, nato pa popping ga sname. [Hardison] Točno tako. Torej pritiskom potisne nekaj na vrhu dimnika. To je kot dajanje osebja jedilnico jedilni pladenj na pultu. In živahen je ob jedilni pladenj off dimnika. Sprehodimo se skozi nekaj primerov, kaj se bo zgodilo ko smo potisnite stvari v sklad. Če bi push niz "zdravo" na naši dimnika, To je tisto, kar bi naša slika izgleda kot zdaj. Oglejte si, kaj se zgodi? Prizadevali smo si v prvem elementu matrike našega godala in smo upped naše večje število za 1. Torej, če pogledamo razliko med stranmi, tu je bil 0, tu je pred pritiskom. Tu je po pritisku. Pred pritiskom, po pritisku. In zdaj imamo samo en element v našem dimnika. To je niz "zdravo", in to je to. Vse ostalo v polju, v naši paleto godala, je še vedno smeti. Nismo ga inicializirati. Recimo, potiskanje drugega niza na naši dimnika. Bomo push "svet" na tem času. Tako lahko vidite, "svet" tu gre na vrhu "zdravo", Število in velikost gre do 2. Sedaj lahko push "CS50", in da bom šel na vrhu. Če se vrnemo, lahko vidite, kako smo potiskajo stvari na vrhu dimnika. In zdaj pridemo do pop. Ko smo izstrelil nekaj off na kupu, kaj se je zgodilo? Je kdo videl razliko? To je zelo subtilna. [Študent] velikost. >> Ja, velikost spremenila. 

Kaj pa bi ti bodo spremenili? [Študent] Strune, preveč. >> Desno. Strune preveč. Izkazalo se je, da če delaš na ta način, saj nismo kopiranje elementov v našem odvodnik, smo dejansko ne bi bilo treba storiti ničesar, lahko samo uporabo velikost spremljati števila stvari v naši matriki tako da, ko smo pop znova, spet sva padanje naše velikosti do 1. Nobene potrebe ni, da bi dejansko šel in prepisati ničesar. Nekako funky. Izkazalo se je, da smo običajno pusti stvari pri miru, ker je manj dela za nas. Če nam ne bi bilo treba iti nazaj in prepisati nekaj, zakaj potem to? Torej, ko smo dvakrat pop off dimnika, vse, kar počne, je padanje da velikost nekajkrat. In spet je to samo zato, ker nismo kopiranje stvari v našem dimnika. Ja? Pojdi. [Študent, nerazumljiv] >> In kaj se zgodi, ko boste pritisnili kaj spet? Ko pritisnete nekaj več, če ne gre? Če ne gre, Basil? >> Into strune [1]? >> Desno. Zakaj ne gre v nizih [3]? [Bazilika] Ker je pozabil, da je bilo kaj v nizih [1] in [2]? [Hardison] Točno tako. Naš sklad, v bistvu "pozabil", da je bilo gospodarstvo na nič v nizih [1] in godala [2], tako da, ko smo push "woot", to šele postavlja, da v elementu na strune [1]. Ali obstaja kakršna koli vprašanja o tem, kako to deluje, na osnovni ravni? [Sam] Torej to ni dinamično na kakršen koli način, v smislu količine ali glede na velikost kup? [Hardison] Točno tako. To je - točka je bila, da to ni bil dinamično growning sklad. To je sveženj, ki lahko imajo, kvečjemu 4 * char s, največ štiri stvari. Če bi poskusil in iztisnite 1/5 stvar, kaj misliš, da naj bi se zgodilo? [Študenti, nerazumljivi] [Hardison] Točno tako. Obstaja več stvari, ki bi se lahko zgodilo. To bi lahko seg napako, odvisno od tega, kaj smo - kako točno smo izvajanje back-end. To bi lahko prepisali. To bi lahko imelo to buffer overflow, da sva se pogovarjala v razredu. Kaj bi bilo najbolj očitno stvar, ki se lahko prepišejo če bomo poskušali push dodatno stvar na našem kup? Torej ste omenili buffer overflow. Kaj je lahko stvar, ki se bo prepisati ali stomped na če je prekoračil po naključju trudili, da bi dodatno stvar? [Daniel, nerazumljiv] >> mogoče. Ampak najprej bi lahko kaj zgodi? Kaj če bi poskušali push 1/4 stvar? Morda bi prepišite velikost, vsaj s tem, da je spomin diagram imamo. 

V opredelitvi težave množico, ki je tisto, kar bomo izvedbeni danes, kaj si želimo narediti je, da vrne false. Naša potisni način vrača boolean vrednost, in da bo logična vrednost true, če potisni uspe in lažno, če ne more vsiliti ničesar več, ker sklad je poln. Sprehodimo se skozi malo tega zakonika zdaj. Tukaj je naša funkcija potisne. Naša funkcija za zagon kup bo trajalo v nizu, da dajo na kup. To se dogaja, da se vrnete res, če je niz uspešno potisnil na kup in lažno drugače. Vse predloge o tem, kaj bi bilo dobro prva stvar, ki sem storil? [Sam] Če površina je enaka zmogljivost potem vrne false? [Hardison] Bingo. Lepo opravljeno. Če je velikost zmogljivosti, bomo vrne false. Ne moremo dati ničesar več v naši dimnika. Sicer pa želimo dati nekaj na vrh dimnika. Kaj je "na vrhu dimnika," na začetku? [Daniel] Velikost 0? Velikost 0 >>. Kaj je vrh dimnika po eno stvar na kup? Missy, veš? [Missy] One. >> Velikost je 1, točno. Kar naprej tako, da se velikost, in vsakič, ko ste dajanje v novi element v velikosti indeks v matriki. To lahko storimo s takšnim ene podlage, če je to smiselno. Tako smo dobili našo paleto strune, da bomo do nje dostopajo na velikost indeksa, in smo le, da bo za shranjevanje naše char * tam. Opazuj, kako da ni niz kopiranje tukaj dogaja, ne dinamično dodeljevanje pomnilnika? In potem Missy odraščali, kaj moramo zdaj narediti, ker smo shranili niz v ustreznem mestu v matriki, in ona je rekla, da smo morali prirastek velikosti enega, tako da smo pripravljeni za naslednjo pritiskom. Tako bomo lahko storite, da z s.size + +. Na tej točki smo potisnili v naši matriki. Kaj je zadnja stvar, moramo storiti? [Študent] Vrnitev res. Vrnitev >> res. Torej, to je zelo preprosta, zelo preprosto kodo. Ne preveč. Ko ste oviti okrog glave, kako deluje sklad, to je zelo preprosta za uporabo. 

Zdaj, naslednji del tega je živahen niz off dimnika. Jaz bom dal vidva nekaj časa za delo na tem malo. To je skoraj v bistvu nasprotno, kar smo storili tukaj pritiskom. Kar sem naredil, je pravzaprav - ojej. Sem zažene z naprave tukaj in naprave, Sem potegnil problem iz 5 specifikacijo. Če bomo povečali tukaj, lahko vidimo, da sem v cdn.cs50.net/2012/fall/psets/pset5.pdf. Ste vi prenesli to kodo, ki se tu nahajajo, section6.zip? V redu. Če tega še niste storili, stori to zdaj, res hitro. Jaz bom to naredil v moji terminalskem oknu. Pravzaprav sem to naredil tukaj. Ja. Ja, Sam? >> Imam vprašanje o tem, zakaj ste rekli s.string s razredih velikosti = str? Kaj je str? Ali je to opredeljeno nekje videl, ali - oh, v char * Str? [Hardison] Da, točno tako. To je bil argument. >> V redu. Žal mi je. [Hardison] smo podrobno niz za uveljavitev noter Drugo vprašanje, ki bi lahko prišli do, da v resnici ne govori o tem je bil smo za samoumevno, da smo imeli to spremenljivko, imenovano s da je bila po obsegu in dostopen za nas. Mi je samoumevno, da je bil ta sklad struct. Tako se ozremo nazaj na to potisni kodo boste videli, da delamo stvari, s tem, da imam niz, sprejeto leta potem pa kar naenkrat, bomo dostop s.size, kot so, kje je prišel? V kodi, ki ga bomo pogledati v oddelku arhiv in potem stvari, ki jih boste opravljali na vašo težavo določa, smo naredili naš sklad struct globalno spremenljivko tako da bomo imeli dostop do njega v vseh naših različnih funkcijah ne da bi ročno prenesti okoli in ga prenesti s sklicevanjem, storiti vse, da se vrste stvari z njim. Saj se samo malo goljufali, če hočete, da bi stvari lepše. In to je nekaj, kar smo tukaj zato, ker je za zabavo, je lažje. Pogosto boste videli, ljudje to, če imajo eno veliko podatkovno strukturo da se je operirana v svojem programu. 

Vrnimo se prenesejo v napravo. Ali so vsi uspešno dobil section6.zip? Vsi razširite z unzip section6.zip? Če greste v oddelku 6 imenik - aah, po vsem mestu - in si seznam, kaj je notri, boste videli, da imaš tri različne datoteke. c. Imaš čakalno vrsto, SLL, ki je vezana na posamezno seznam, in kup. Če odpreš stack.c, boste videli, da imamo to opredeljeno struct za nas, točno struct, da smo pravkar govorili v diapozitivih. Imamo našo globalno spremenljivko za sklad, imamo našo naročeno funkcijo, in potem imamo našo pop funkcijo. Jaz bom dal kodo za potiskanje nazaj na diapozitivu tukaj, ampak kaj bi rad vi storiti, je, da svojih najboljših močeh, pojdi in izvajanje pop funkcijo. Ko ste jo uporabili, jo lahko prevedete to s ti dimnika, in nato zaženite posledičnega izvedljivo žetonov, in da bo teči vse te oznake preskusa dol, da je v glavnem. In glavno skrbi za dejansko izdelavo push in pop klicev in zagotoviti, da bo šlo vse skozi vso pravico. Prav tako inicializira stack velikosti tukaj tako da vam ni treba skrbeti, da inicializacijo. Lahko domnevamo, da je bilo pravilno inicializiran s časom, ki ga imate dostop v pop funkcije. Ima to smisel? Torej, gremo. Tukaj je pritisk kodo. Dam ti fantje 5 ali 10 minut. In če imate kakršno koli vprašanje v vmesnem času, ko ste kodiranje, prosite naglas. Torej, če prideš do vbodne rane, kar vprašaj. Naj vedo, kaj vsi ostali vedo. Delo s svojim bližnjim preveč. [Daniel] Midva samo izvedbo pop prav zdaj? >> Samo pop. Čeprav lahko kopirate izvajanje pritiskom, če želite tako da bo testiranje delovalo. Ker je težko preizkusiti stvari dobili v - ali, da je težko preveriti živahen stvari iz dimnika, če ni nič v sklad za začetek. 

Kaj je pop naj bi se vrnil? Element od vrha dimnika. To naj bi se element off vrhu dimnika in potem padanje velikost dimnika, in zdaj ste izgubili element na vrhu. In potem se vrne element na vrhu. [Študent, nerazumljiv] [Hardison] Torej, kaj se zgodi, če si to naredil? [Študent, nerazumljiv] Kaj se dogaja konča, je, da ste verjetno dostop bodisi element, ki ni bil inicializiran še, da vaš izračun od katerih je zadnji element je izklopljen. Torej tukaj, če opazite, pri pritisku, smo dostop do nizov na s.size elementa ker je novi indeks. To je nova vrh dimnika. Ker v pop, s.size se bo naslednji prostor, prostor, ki je na vrhu vseh elementov v vaših žetonov. Torej top-najbolj element sploh ni s.size, ampak, to je pod njo. 

Druga stvar, ki jo storite, ko ste - v pop, se imate za zmanjšaj velikost. Če se spomnite nazaj na našo malo diagram tukaj, Res je edina stvar, ki smo jih videli dogaja, ko smo poklicali pop je bilo, da je ta velikost padel, najprej 2, nato 1. Potem, ko smo potisnil nov element na bi šlo za na ustrezno mesto. [Bazilika] Če s.size je 2, potem ne bi šel v elementu 2, in potem bi radi, da pop ta element off? Torej, če smo šli v - >> Torej, poglejmo še enkrat. Če je to naš dimnik na tej točki in rečemo pop, na katerih indeks je najbolj top-element? [Bazilika] Na 2, vendar pa se bo pop 3. >> Desno. Tako da je, kjer je naš znaša 3, vendar želimo, da pop element na indeksu 2. To je značilno, da je nekako off za tistega, ki ga imajo z ničelno indeksiranje polj. Torej, če res želite, da pop tretji element, ampak tretji element ni v indeksu 3. In razlog, nimamo narediti to minus 1, ko smo potiskanje ker je zdaj, boste opazili, da je večina od zgoraj element, če smo bili pritisniti na nekaj drugega svežnja na tej točki, mi bi želeli, da ga potisnite v indeksu 3. In prav tako se zgodi, da velikost in indeksi line up, ko ste potiskanje. 

Kdo ima delovno žetonov izvajanja? Imaš delovno sklad 1. Ali ste pop dela še? [Daniel] Da. Mislim, da. >> Program teče in ne seg izjalovljen, to je tiskanje? Ali natisniti "uspeh", ko ga zaženete? Ja. Naredite kup, ga zaženite, če se izpiše "uspeh", in ne presega razcvet, potem je vse v redu. V redu. Greva na aparat res hitro, in bomo sprehod skozi to. Če pogledamo, kaj se dogaja z pop, Daniel, kaj je bila prva stvar, ki si naredila? [Daniel] Če je s.size večji od 0. [Hardison] Ok. In zakaj ste to storili? [Daniel] Če se želite prepričati, da je nekaj notri dimnika. [Hardison] desno. Če želite preizkusiti, se prepričajte, da je s.size večje od 0; drugače, kaj želiš, da se zgodi? [Daniel] Return null? Nazaj >> null, točno. Torej, če s.size večji od 0. Torej, kaj bomo storili? Kaj bomo naredili, če sklad ni prazen? [Stella] Vi vzroka velikost? Vi >> padanje višine, v redu. Torej, kako si to naredil? >> S.size--. [Hardison] Čudovito. In potem, kaj si naredil? [Stella] In potem sem rekel donos s.string [s.size]. [Hardison] Čudovito. V nasprotnem primeru se vrne null. Ja, Sam? [Sam] Zakaj ni treba s.size + 1? [Hardison] Plus 1? >> Ja. >> Razumem. [Sam] Mislil sem, ker ste prevzeli 1 out, potem boste, da se ne bo vrnil tistega, ki so zaprosile. [Hardison] In to je samo tisto, kar smo govorili z vsem tem vprašanjem 0 indeksov. Torej, če želimo povečati nazaj sem. Če pogledamo ta tip tukaj, lahko vidite, da ko smo pop, smo živahen element na indeksu 2. 

Tako smo zmanjšali našo velikost, potem naša velikost ustreza naši indeks. Če ne bomo zmanjšaj velikost, potem moramo velikost -1 in nato padanje. Čudovito. Vse v redu? Vsa vprašanja o tem? Obstaja več različnih načinov, da bi napisal, da je to dobro. V bistvu, lahko naredimo še nekaj - kar lahko naredimo na enem plast. Mi lahko naredimo eno vrstico donos. Torej si lahko dejansko upade, preden se vrnemo s tem. Tako dajanje - pred s.size. To naredi linija res gosto. Če je razlika med. - Velikost in s.size, - je, da to postfix - pravijo, da zato, ker postfix - prihaja po s.size, - pomeni, da se s.size ocenili za ugotavljanje indeksa kot je zdaj, ko se izvaja ta linija, in potem je to - se zgodi, ko postane izvajajo line. Ko je naložena element pri s.size indeksa. In to ni tisto, kar želimo, ker hočemo, da padanje najprej zgodilo. Othewise, da bomo lahko dostop do matriko, učinkovito izven igrišča. Mi bomo za dostop do elementa nad tisto, ki ga dejansko želijo dostopati. Ja, Sam? >> Je hitreje in porabi manj pomnilnika, da bi v eni vrstici, ali ne? [Hardison] Odkrito povedano, res je odvisno. [Sam, nerazumljiv] >> Ja, to je odvisno. To lahko storite prevajalnikov trike da se prevajalnik zavedati, da običajno, mislim. 

Tako smo omenili nekaj o tej stvari prevajalnik za optimizacijo , ki jih lahko naredite v pripravi, in to je vrsta stvari, ki bi prevajalnik lahko ugotovimo, kot oh, hej, morda lahko naredim to vse v eni operaciji, v nasprotju z nalaganjem večje spremenljivko iz RAM-a, to nižanje, jo shranite nazaj in ga nato nazaj na prvotno mesto nakladanja obdelati preostanek te operacije. Ampak ponavadi, ne, to ni reč da se dogaja, da se vaš program bistveno hitreje. Vse več vprašanj o skladih? 

Torej, potiskanje in živahen. Če vi želite, da preizkusite hacker izdaja, kaj smo naredili v hacker različico je dejansko šlo in je ta kup raste dinamično. Izziv je predvsem tukaj v potisni funkciji, da ugotovimo, kako narediti, da zaporedje narašča kot vi vztrajati potiska vse več elemente na kupu. Pravzaprav ni preveč dodatna oznaka. Samo klic - moraš vedeti, da bi dobili pozive za knjižnične funkcije malloc tam pravilno, in nato ugotovimo, kdaj boš poklical realloc. To je zabavno, izziv, če ste zainteresirani. 

Ampak za zdaj, gremo naprej, in kaj je govoril o čakalnih vrst. Pomikajte se tukaj. Čakalna vrsta je blizu sibling od dimnika. Torej, v plasteh, so stvari, ki naj v zadnji so bile prve stvari, ki bi jih morale nato umakniti. Imamo ta zadnji noter, prvi ven, ali LIFO, naročanje. Ker je v čakalni vrsti, kot ste pričakovali od takrat, ko stojiš v vrsti, prva oseba, ki se v skladu, je prva stvar, da se v čakalni vrsti, je prva stvar, ki jo dobi pridobljeni iz čakalne vrste. Čakalne vrste se pogosto uporabljajo tudi, kadar imamo opravka z grafi, kot sva se pogovarjala na kratko s policami in čakalne vrste so tudi priročen za kup drugih stvari. Ena stvar, ki pride pogosto poskuša ohraniti, na primer, razporejene seznam elementov. In lahko to storite z matriko. Lahko vzdrževati urejen seznam stvari, ki v matriki, vendar je ta postane težavno je potem moraš vedno najti primerno mesto, da vstavite naslednjo stvar. Torej, če imate niz številk, 1 do 10, in potem želite razširiti, da vse številke od 1 do 100, in ste dobili te številke v naključnem vrstnem redu, in poskuša obdržati vse razvrščenih kot greš skozi, boste na koncu morali storiti veliko premika. Pri nekaterih vrstah čakalnih vrst in nekatere vrste osnovnih podatkovnih struktur, lahko dejansko ostane dokaj preprost. Nimaš kaj dodati in nato prerazporedi celotno stvar vsak čas. Prav tako ne boste morali storiti veliko premika notranjih elementov okrog. Ko se ozremo na vrsti, boste videli, da je - tudi v queue.c v oddelku kode - struct, ki smo vam ga je dal, je res podoben struct, ki si jo dobila za dimnik. 

Obstaja ena izjema, in da je ena izjema je, da imamo te dodatne celo število, ki se imenuje glava, in tu je glava sledenja vodje čakalni vrsti, ali prvi element v vrsti. Z dimnika, smo lahko spremljali element, ki smo bili na tem pridobiti, ali zgornji del dimnika, z uporabo samo na velikost, ker je s čakalno vrsto, bomo morali ukvarjati z nasprotnih koncih. Poskušamo tack stvari na koncu, potem pa se vrne stvari od spredaj. Tako učinkovito, z glavo, imamo indeks začetku čakalne vrste, in velikost nam daje indeks koncu čakalne vrste tako da bomo lahko naložite stvari iz glave in dodali stvari na repu. Ker v plasteh, smo bili vedno samo ukvarjajo z vrha dimnika. Nikoli nismo imeli dostop do dna dimnika. Mi samo dodal stvari na vrh in vzel stvari off vrhu tako da mi ni bilo treba, da se dodatno polje znotraj našega struct. Ali to splošno smisel? V redu. Da, Charlotte? [Charlotte, nerazumljiv] [Hardison] To je veliko vprašanje, in to je bil tisti, ki je prišel v predavanju. Mogoče bo sprehod skozi nekaj primerov ponazarjajo, zakaj ne želimo uporabljati strings [0] kot vodja čakalne vrste. 

Tako si predstavljam, da imamo vrsto, bomo rekli čakalne vrste. Na začetku, ko smo šele zaženejo, Ko smo ravno jo je razglasila, da nismo ničesar inicializiran. To je vse smeti. Torej, seveda želimo zagotoviti, da bomo inicializirati tako velikost in glavo polja na 0, kar razumen. Lahko bi tudi šel naprej in null določeni elementi v naši vrsti. In da bi to diagram prileganje, opazite, da se zdaj lahko naša vrsta ima samo tri elemente; ker se lahko naše sklad ima 4, lahko naša vrsta ima samo tri. In to je samo, da je diagram fit. Prva stvar, ki se dogaja, je, da smo enqueue niz "hi". In tako kot smo z kup, nič strašno drugačna tukaj, vržemo vrvico na strune na [0] in prirastek naše velikosti do 1. Mi enqueue "adijo", dobi je dana. Torej, to je videti kot kup za večino del. Začeli smo tukaj, novost, nov element, velikost ohranja gredo gor. Kaj se dogaja v tem trenutku, ko želimo dequeue kaj? Ko smo želeli dequeue, ki je element, ki ga želimo dequeue? [Bazilika] Strings [0]. >> Zero. Točno, Basil. Želimo, da se znebite prvega niza, je ta, "živjo". Torej, kaj je druga stvar, ki je spremenil? Obvestilo, ko je izstrelil nekaj off na kupu, smo samo spremenili velikost, ampak tukaj, imamo nekaj stvari, ki se spremenijo. Ne samo spremembo velikosti, vendar mora ravnatelj spremembe. To sega nazaj do točke Charlotte je prej: Zakaj imamo to glavo, pa tudi? Ali je smiselno zdaj, Charlotte? >> Nekako. [Hardison] Nekako? Torej, kaj se je zgodilo, ko smo dequeued? Kaj je vodja to, da je zdaj zanimivo? [Charlotte] Oh, saj je spremenilo - v redu. Vidim. Ker je glava - če je glava kaže na spremembe v smislu lokacije. To ni več vedno nič kazalo 1. >> Ja, točno tako. Kaj se je zgodilo, če dequeueing visoko element je bilo storjeno, in nismo imeli te glave polje ker smo bili vedno kliče ta niz na 0 indeksa vodja našega vrsti, potem bi morali preusmeriti preostalo vrsti navzdol. Morali bi premik "adijo" od od nizov [1], da se strune [0]. In godala [2] določa, da strune [1]. In bi kar moramo storiti, je to za celoten seznam elementov, celoten nabor elementov. In ko to počnemo z vrsto, da postane zelo drago. Torej, tukaj, to ni nič takega. Pravkar smo imeli tri elemente v naši matriki. Ampak, če bomo imeli čakalno vrsto za tisoč elementov ali milijon elementov, in potem kar naenkrat smo začeli delati cel kup dequeue poziva vse v zanki stvari se res dogaja, da bi to upočasnilo, saj prenaša vse navzdol stalno. Veš, premik za 1, premik za 1, premik z 1, premik do 1. Namesto tega uporabite glavo, ga imenujemo "kazalec", čeprav v resnici ni kazalec v ožjem smislu, to ni kazalec tipa. To ni int * ali char * ali kaj podobnega. Ampak to kaže ali prikazuje glavo naši vrsti. Ja? 

[Študent] Kako dequeue vem, da samo pop off vse, kar je v glavi? [Hardison] Kako dequeue vem, kako pop off vse, kar je v glavi? >> Ja, ja. >> Kaj to gleda le glede na glavo polje nastavljeno na. Torej, v tem prvem primeru, če gledamo tukaj, Naša glava je 0, 0 indeks. >> Desno. [Hardison] Torej je samo pravi redu, dobro, je element na indeksu 0, niz "hi" je element, na čelu naše vrste. Torej bomo dequeue tega tipa. In to bo tisti element, ki dobi vrnjen klicatelja. Da, Saad? >> Torej v bistvu glava nastavi - če boš to kazalo? To je začetek tega? >> Ja. >> Redu. [Hardison] To je postal nov začetek za našo matriko. Torej, ko dequeue nekaj, vse, kar morate storiti, je dostop do elementa na indeks q.head, in bo to element, ki ga želite dequeue. Imate tudi padanje višine. Bomo videli v nekaj, kjer se stvari malce težavno s tem. Mi dequeue, in zdaj, če bomo spet enqueue, kje smo enqueue? Kam je šel naslednji element v naši vrsti? Povejte želimo enqueue niz "CS". V katerega indeks bo šlo? [Dijaki] Strings [2]. >> Dva. Zakaj 2 in ne 0? [Bazilika] Ker zdaj je glava 1, tako da je kot na začetku seznama? [Hardison] desno. In kaj pomeni konec seznama? Kaj smo z uporabo, ki označuje konec našega čakalne vrste? Glava je vodja naše čakalno vrsto, začetek naše vrste. Kaj je konec naše čakalne vrste? [Dijaki] Velikost. Velikost >> točno. Torej, naši novi elementi iti na velikost, in elemente, ki jih bomo sprejeli off sname na glavo. Ko smo enqueue naslednji element, mi ga je dala ob velikosti. [Študent] Preden vložite, da, čeprav, je bila velikost 1, kajne? [Hardison] desno. Torej ni čisto pri velikosti. Velikost +, ne 1, vendar + glava. Ker smo vse, kar je premaknilo z glavo zneska. Torej, tukaj, zdaj imamo čakalne vrste za velikosti 1, ki se začne pri indeksu 1. Rep je indeks 2. Ja? 

[Študent] Kaj se zgodi, ko ste dequeue strings [0], in strune "reže v spomin Samo se izpraznijo, v bistvu, ali pa pozabil? [Hardison] Ja. V tem smislu smo jih kar pozabili. Če smo bili shranjevanje kopij njimi - veliko podatkovne strukture se pogosto shranjujejo svoje kopije elementov tako, da oseba, ki upravlja podatkovno strukturo ni treba skrbeti o tem, kje so vsi ti kazalci se dogaja. Struktura podatkov drži za vse, ima na vseh izvodih, zagotoviti, da vse ostaja ustrezno. Vendar je v tem primeru te podatkovne strukture le zaradi enostavnosti, niso izdelavo kopije vsega, kar smo shranjevanje v njih. [Študent] Torej je to stalen nabor -? >> Da. Če pogledamo nazaj, kaj je definicija te strukture je. To je samo standardni niz, kot ste videli, niz char * s. Ali to -? >> Ja, jaz sem samo spraševala Če boste na koncu zmanjkalo spomina, do neke mere, če imate vse te prazne lise v vašem array? [Hardison] Ja, to je dobro izhodišče. 

Če pogledamo, kaj se dogaja sedaj na tem mestu, smo napolnili našo vrsto, kot je videti. Vendar pa smo v resnici ne napolni naše čakalne vrste saj imamo čakalno vrsto, ki je velikost 2, vendar pa se začne pri indeksu 1, kajti tam naš vodja kazalec. Kot ste rekli, da je ta element na strune [0], v indeksu 0, je v resnici ni. To ni v naši vrsti več. Samo ni motilo, da gredo v in prepisati, ko smo ga dequeued. Torej, čeprav izgleda, da smo zmanjka pomnilnika, res ne. To mesto je na voljo za nas, za uporabo. Primerno vedenje, če bi poskusil kaj 1. dequeue kot so "adijo", da bi se poslovil pop off. Zdaj naša vrsta se začne pri indeksu 2 in velikosti 1. In zdaj, če poskušamo enqueue nekaj več, recimo 50, 50 mora iti v to mesto na indeksu 0 ker je še vedno na voljo za nas. Da, Saad? [Saad] Ali je to zgodilo samodejno? [Hardison] To se ne zgodi kar samodejno. Kar morate storiti math da bi bilo delo, ampak predvsem tisto, kar smo naredili, je, da smo le ovije okrog. [Saad] In to je v redu, če ima to luknjo v sredini tega? [Hardison] To je, če lahko naredimo math deluje pravilno. 

In izkazalo se je, da je to pravzaprav ni tako težko storiti z mod operaterja. Tako kot sva s Cezarjem in šifriranega stvari, s mod, lahko pridemo stvari do ovijte okoli in nadaljuj okoli in okoli in okoli z našo vrsto, vodenje, da glava kazalec premika. Obvestilo, da je velikost vedno spoštuje število elementov dejansko v čakalni vrsti. In to je samo za glavo kazalec, ki ohranja kolesarjenje skozi. Če pogledamo, kaj se je tu zgodilo, če se vrnemo na začetek, in si ogledate, kaj se zgodi v glavi ko smo enqueue kaj, nič se ni zgodilo v glavo. Ko smo enqueued nekaj drugega, nič se ni zgodilo v glavo. Takoj ko smo dequeued nekaj, glava se dvigne za eno. Mi enqueued kaj ne zgodi nič v glavo. Ko smo dequeue nekaj, kar naenkrat postane poveča za glavo. Ko smo enqueue kaj ne zgodi nič v glavo. 

Kaj bi se zgodilo v tem trenutku, če bi dequeue kaj spet? Vsak misli? Kaj bi se zgodilo z glavo? Kaj bi se zgodilo z glavo če bi dequeue kaj drugega? Glava sedaj je na indeksu 2, kar pomeni, da je vodja vrsti je strings [2]. [Študent], ki vrne 0? >> Treba je vrniti na 0. Morala bi zaviti nazaj okoli, tako je. Do sedaj, vsakič, ko smo poklicali dequeue, smo se doda 1 v glavo, dodate na glavo, dodamo eno v glavo, dodamo eno v glavo. Takoj, ko glavo, da kazalec pride do zadnjega indeksa v naši matriki, potem moramo ga ovijte okoli nazaj na začetek, pojdi nazaj na 0. [Charlotte] Kaj določa storilnost čakalni vrsti na kup? [Hardison] V tem primeru, smo ravnokar z # opredeljena konstantna. >> Redu. [Hardison] V dejanski datoteke. C, lahko greš v muck in z njo tudi nekaj in da bo tako velika ali malo, kot želite. [Charlotte] Torej, ko delaš to vrsto, kako bo računalnik vedel kako velik želite sklad je? [Hardison] To je odlično vprašanje. Obstaja nekaj načinov. Eden od njih je, da šele določiti vnaprej in reči, to se bo čakalna vrsta, ki ima 4 elemente ali elemente 50 ali 10.000. Drugi način je, da to, kaj ljudje počnejo izdaja hekerjev in ustvariti funkcije imajo svoje čakalne vrste rastejo kot dinamično dobili več stvari dodal noter 

[Charlotte] Torej iti s prvo možnostjo, kaj skladnja ne uporabljate povedati program, kaj je velikost čakalne vrste? [Hardison] Ah. Torej gremo ven iz tega. Še vedno sem v stack.c tukaj, tako da sem šele tekoč, da se pomaknete do vrha tukaj. Ali lahko vidite to tukaj? To je # define zmogljivosti 10. In to je skoraj popolnoma enaka sintaksa, da imamo v čakalni vrsti. Razen v vrsti, smo dobili, da ekstra struct polje tukaj. [Charlotte] Mislil sem, da je zmogljivost pomenilo zmogljivosti za niz. [Hardison] Ah. >> To je največja dolžina besede. >> Razumem. Ja. Zmogljivost tukaj - to je odlična točka. In to je nekaj, kar je zapleteno ker tisto, kar smo tukaj prijavljeni niz char * s. Paleto kazalcev. To je niz znakov. To je verjetno tisto, kar ste videli, ko ste bili razglasitvi svoje rezerve za datoteko I / O, Ko sem bil ustvarjanje niza ročno na kupu. Toda tisto, kar smo dobili, je tu niz char * s. Torej, to je niz kazalcev. Pravzaprav, če smo povečali nazaj in pogledamo, kaj se dogaja v predstavitvi, boste videli, da so dejanske elemente, znakovni podatki niso shranjeni v matriki same. Kaj je shranjen v naši matriki tukaj so kazalci na znakovnih podatkov. Ok. Tako smo videli, kako je velikost čakalne vrste je tako kot v plasteh, velikost vedno upošteva število elementov, ki so trenutno v čakalni vrsti. Po tem, ko enqueues 2, velikost je 2. Po izdelavi dequeue velikost je trenutno 1. Po tem, ko še enqueue velikost je nazaj do 2. Torej je velikost vsekakor upošteva število elementov v vrsti, nato pa glavo samo ohranja kolesarjenja. To gre z 0-1-2, 0-1-2, 0-1-2. In vsakič, ko pravimo dequeue, postane vodja kazalec poveča na naslednjo indeks. In če je glava je približno iti čez, da zanke nazaj okoli 0. Torej s tem, lahko zapišemo dequeue funkcijo. In bomo zapustili enqueue funkcijo za fantje namesto izvajati. 

Ko smo dequeue element iz naše vrsti, Kaj je bila prva stvar, ki Daniel naredili, ko smo začeli pisati pop funkcijo skladih? Naj slišim od nekoga, ki je še ne govori. Poglejmo, Saad, se spomniš, kaj si Daniel, kot prvo stvar, ko jo je napisal pop? [Saad] je bil, da je - >> Preizkusil je za nekaj. [Saad] Če je velikost večja od 0. >> Točno tako. In kaj je bilo to testiranje? [Saad] To je bilo testiranje, da vidim, če je kaj notri polje. [Hardison] Ja. Točno tako. Torej, ne morete pop bo kaj kupu, če je prazna. Prav tako ne morete ničesar dequeue iz čakalne vrste, če je prazna. Kaj je prva stvar, moramo storiti v naši dequeue funkcije tukaj, ti misliš? [Saad] Če je velikost večja od 0? >> Ja. V tem primeru, sem dejansko samo preskušene, da vidim, če je 0. Če je 0, se lahko vrnemo null. Ampak točno ista logika. In kaj je še s tem. Če velikost ni 0, če je element, ki ga želimo dequeue? [Saad] Na čelu? >> Točno tako. Mi lahko samo potegnite prvi element v naši vrsti z dostopom do elementa na glavi. Nič noro. Po tem, kaj naj storimo? Kaj se je zgodilo? Kaj je bila druga stvar, ki smo govorili v dequeue? Dve stvari, da se zgodi, ker se je naša vrsta spremenilo. [Daniel] Zmanjšanje velikosti. >> Moramo zmanjšati velikost in povečati glavo? Točno tako. Za povečanje glavo, ne moremo kar slepo poveča glavo, se spomnite. Ne moremo narediti queue.head + +. Moramo tudi to mod po zmogljivosti. In zakaj mod z zmogljivostjo, Stella? [Stella] Ker je ovijte okoli. >> Točno tako. Mi mod z zmogljivostjo, saj ima za zavijanje nazaj okoli 0. Torej, zdaj, v tem trenutku lahko naredimo tisto, Daniel je rekel. Mi lahko padanje višine. In potem bomo lahko samo vrne element, ki je bil na vrhu čakalne vrste. To izgleda nekako Čvornovat na prvi. Morda imate vprašanje. Prosim? 

[Sam] Zakaj je prvi na vrhu čakalne vrste? Če ne gre? [Hardison] Izhaja iz četrti vrstici od spodaj. Ko smo test, da se prepriča, da je naša vrsta ni prazna, smo izvlecite char * prvi, smo izvlekli element, ki je sedel na sedežu indeksa naše polje, naše godala diod, in zahtevajo, da >> 1.? [Hardison] In smo rekli prej. Ja. Samo, da spremlja, da, zakaj misliš, da bi moral to storiti? [Sam] Vsak, ki je prvo pravkar vrnil q.strings [q.head]? >> Ja. >> Ker delamo to spreminjanja q.head z mod funkcijo, in ni način za to, da se v povratni vod tudi. [Hardison] Točno tako. Si spot on. Sam je popolnoma spot on. Zato smo morali potegniti ven prvi element v naši vrsti in ga shrani v spremenljivko Kajti to vrstico, kjer smo pravkar q.head, obstaja mod operater ni nekaj, kar lahko storimo in se ne začne veljati na glavo, ne da bi - v eni vrstici. Tako smo dejansko morali potegniti ven prvi del, nato nastavite glavo, prilagoditi velikost, in nato vrne element, ki ga potegnil ven. In to je nekaj, kar boste videli bomo prišli kasneje s povezani seznam, kot smo igral z njimi. Pogosto, ko ste sprostitve ali odstranjevanje, povezanih seznamov se morate zavedati, naslednji element, naslednji kazalec na povezanem seznamu Pred odstranjevanjem sedanjega. Ker drugače si vrgel proč informacije o tem, kaj je ostalo na seznamu. Zdaj pa, če greš na vaši napravi, morate odpreti queue.c-X-ven iz tega. Torej, če sem odprl queue.c, naj povečaj tukaj, boste videli, da imate podobne usmerjeno datoteko. Podobno usmerjen datoteka s tem, kar smo imeli prej s stack.c. Imamo našo struct za določeno vrsto tako, kot smo videli na diapozitivih. 

Imamo enqueue funkcijo, ki je za vas. In imamo dequeue funkcijo tukaj. The dequeue funkcija v datoteki je mrtva črka na papirju, ampak ga bom dal nazaj gor na PowerPointu, tako da ga lahko vnesete v, če želite. Torej, za naslednjih 5 minut ali tako, fantje delajo na enqueue kar je skoraj ravno nasprotno od dequeue. Če ne bi bilo treba prilagoditi glavo, ko ste enqueueing, ampak kaj imaš prilagoditi? Velikost. Torej, ko enqueue, ostane nedotaknjeno glavo, dobi spremenili velikost. Vendar pa se malo - imeli boste igral s tem mod da ugotovimo, kaj indeks je treba nov element vstavi. Tako da bom dal vidva malo, dal dequeue nazaj na diapozitivu, in kot fantje so vprašanja, ki jih zakričal, da bomo lahko Vsi govorijo o njih kot skupina. Tudi pri velikosti, Ne - če nastavite velikost, lahko vedno le - imaš mod velikost kdaj? [Daniel] No >> Nimaš mod velikost, prav. Ker bo velikost vedno, če Menda - ob predpostavki, da ste vodenje stvari ustrezno, velikost bo vedno med 0 in 3. Če imate mod, ko delaš enqueue? [Študent] Samo za glavo. >> Samo za glavo, točno. In zakaj moraš mod sploh enqueue? Ko je situacija, v kateri bi si morali mod? [Študent] Če imate stvari na prostorih, kot je prostori 1 in 2, in potem si moral nekaj dodati na 0. [Hardison] Ja, točno. Torej, če tvoja glava kazalec na samem koncu, ali, če je vaša velikost plus glavo večji, oziroma, da se bo ovijte okoli čakalne vrste. 

Torej, v tem primeru, da imava tukaj na diapozitivu prav zdaj, če želim enqueue nekaj prav zdaj, želimo enqueue nekaj na indeksu 0. Torej, če pogledaš na katerih gre 50 in pozivam enqueue 50, gre tam doli na dnu. To gre v 0 indeksa. Ta nadomešča "hi", ki je bil že dequeued. [Daniel] Ne boste poskrbeli, da dequeue že? Zakaj je to naredil z glavo v enqueue? [Hardison] Oh, tako da ne boste spremenili glavo, mi je žal. Vendar pa boste morali uporabiti mod operaterja, ko boste dostop element, ki ga želite enqueue, ko boste dostop Naslednji element v vaši vrsti. [Bazilika] nisem storil, in sem dobil "uspeh" na tam. [Daniel] Oh, jaz razumem, kaj govoriš. [Hardison] Torej Nisi ti - pravkar naredil na q.size? [Basil] Ja. Pravkar sem spremenil straneh, nisem storil ničesar z glavo. [Hardison] Vi ne dejansko imajo ponastaviti glavo, da je karkoli, ko pa indeks v matriki godala, ste dejansko imajo, da gredo naprej in izračunati, če je naslednji element, ker withe sveženj, naslednji element v vaših žetonov je bil vedno V indeksu, ki ustreza velikosti. Če se ozremo nazaj na našo funkcijo dimnika pritiskom, smo lahko vedno Prebirati v naši novi element desno na velikost indeksa. Ker v čakalni vrsti, ne moremo narediti, da ker če smo že pri tem primeru, če bi 50 enqueued naš nov niz desno na strune [1] ki jih ne želite storiti. Radi bi imeli nov niz iti na indeksu 0. 

Ali kdo - ja? [Študent] Imam vprašanje, vendar to ni res povezana. Kaj pomeni, če nekdo kliče le nekaj podobnega PRED kazalca? Kaj je to ime kratica za? Vem, da je samo ime. [Hardison] PRED kazalec? Pa poglejmo. V kakšnem kontekstu? [Študent], je bil za vložek. Lahko vas kasneje, če hočeš ker to ni res povezana, vendar sem - [Hardison] Od kodo vstaviti Davida iz predavanja? Mi lahko potegnite navzgor in da je govoriti o tem. O tem bomo govorili, da je poleg, ko bomo prišli do povezanih seznamov. 

Torej, kaj je res hitro pogledati, kaj enqueue funkcija izgleda. Kaj je bila prva stvar, da ljudje poskušali narediti v vašem enqueue vrsti? V tej vrsti? Podobno kot tisto, kar si naredil za potiskanje dimnik. Kaj si naredil, Stella? [Stella, nerazumljiv] [Hardison] Točno tako. Če je (q.size == SPOSOBNOSTI) - Moram dati svoje naramnice na pravem mestu - vrne false. Povečaj malo. Ok. Zdaj, kaj je naslednja stvar, ki smo morali narediti? Tako kot pri plasteh, in se vstavi na pravem mestu. In kaj je pravi kraj za vključitev tega? V svežnju je bil indeks velikost, s tem, da ni čisto tako. [Daniel] Imam q.head--ali - >> q.strings? >> Ja. q.strings [q.head + q.size mod ZMOGLJIVOSTI]? [Hardison] Verjetno smo želeli postaviti oklepaje okoli tega tako da smo dobili ustrezno prednost in da je cleart vsem. In določiti, da je enaka? >> Za Str? >> Za Str. Čudovito. In zdaj, kaj je zadnja stvar, ki jo moramo narediti? Tako kot smo to storili v sklad. >> Prirastek velikost? >> Prirastek velikosti. Boom. In potem, ker je za zagon kode pravkar vrnil false privzeto želimo spremeniti to res, če bo šlo vse skozi in vse gre dobro. V redu. To je veliko informacij za oddelek. Nismo čisto mimo. Želimo govoriti o zelo hitro posamezno povezanih seznamov. Bom dal to gor, tako da se lahko vrnete na kasneje. Toda vrnimo k naši predstavitvi za samo nekaj več diapozitivov. Torej je enqueue TODO, zdaj smo to naredili. 

Zdaj pa si oglejte na posamezno povezanih seznamov. Pogovarjala sva se o njih malo bolj v predavanju. Koliko od vas videl demo, kjer smo imeli ljudi nerodno obrnjena drug drugega in gospodarstvo številke? >> Bil sem v to. >> Kaj si vi mislite? Je to, upajmo, da demistificirati te malo? S seznama, se je izkazalo, da imamo opravka s tem tipom, da bomo lahko pokličete vozlišče. Ker je s čakalno vrsto in s sklada smo imeli konstrukti, da bi pravimo vrsto v plasteh, smo imeli te nove vrsto v odvodnikom vrst, Tukaj je seznam res tako sestavljen iz kup vozlišč. Na enak način, kot so strune le kup znakov, vse se vrstijo drug poleg drugega. Povezani seznam je samo vozlišče in drugo vozlišče in drugo vozlišče in drugo vozlišče. In ne razbije vsa vozlišča med seboj in jih shranite contiguously Vse je v redu druga ob drugi v spominu, ob tem poleg kazalec nam omogoča, da shranite vozlišča kadar koli naključno. In potem nekako žice jih vse skupaj na točko od enega do drugega. 

In kaj je velika prednost, da je to že več kot matriko? Več shranjevanje vsega, kar contiguously samo zaljubljen drug poleg drugega? Se spomniš? Ja? >> Dinamično dodeljevanje pomnilnika? >> Dinamično dodeljevanje pomnilnika, v kakšnem smislu? [Študent] V da lahko obdržite tako da je večji in vam ni treba premakniti vaš celoten niz? [Hardison] Točno tako. Torej, z vrsto, če želite, da bi nov element v sredini, boste morali preusmeriti vse, da bo prostor. In kot smo govorili s čakalno vrsto, zato se držimo za glavo, da kazalec, tako da ne bomo ves čas premika stvari. Ker to postane drago, če imaš velik nabor in ste ves čas počne teh naključnih vstavitve. Ker s seznamom, vse, kar morate storiti, je vrgel na novo vozlišče, prilagoditi kazalci, in ste končali. Kaj je zanič to? Ne glede na dejstvo, da to ni tako enostavno delati kot matriko? Ja? [Daniel] No, mislim, da je veliko težje pridejo do določenega elementa v povezanem seznamu? [Hardison] Ne moreš skočiti na poljuben element v sredini svojega povezanega seznama. Kako boste morali to storiti namesto tega? >> Moraš stopiti skozi celotno stvar. [Hardison] Ja. Moraš iti skozi enega naenkrat, eno za drugo. To je ogromna - to je bolečina. Kaj drugega - tam je še en propad s tem. [Bazilika] Saj ne more iti naprej in nazaj? Moraš iti v eno smer? [Hardison] Ja. Torej, kako bomo rešili, da je včasih? [Bazilika] dvojno povezani seznam? >> Točno tako. Obstaja dvojno povezani seznam. Obstajajo tudi - žal? 

[Sam] Ali je to enako kot z PRED stvar, ki - Pravkar sem se spomnil, kaj ni to tisto, kar PRED stvar je za? Ali ni to v času med dvakrat in posamično? [Hardison] Oglejmo si, kaj točno počne. Torej, gremo. Tukaj je seznam kodo. Tukaj imamo predptr, tukaj. Je to tisto, kar si govorila? Torej, to je - on je sprostilo seznam in hoče za shranjevanje kazalec na njej. To ni dvakrat, posamično povezani seznami. Lahko govorimo več o tem kasneje, ker to govorim o sprostitvi seznam in želim pokazati nekatere druge stvari prvi. ampak to je samo - to je spomnil na vrednost PTR [Študent] Oh, to je Prejššnji kazalec? >> Ja. Tako da bomo lahko nato prirastek PTR sam, preden smo nato brezplačno, kar je predptr. Ker ne moremo brez ptr in nato razpis ptr = ptr drugega, kajne? To bi bilo slabo. Torej, da vidimo, nazaj z njim. 

Druga slaba stvar je, da medtem seznamov z vrsto imamo samo vse elemente sami zloženi drug poleg drugega, Tukaj smo uvedli tudi ta kazalec. Torej je dodaten kos pomnilnika, ki ga bomo morali uporabiti za vsak element, ki smo hranjenje v našem seznamu. Smo dobili prilagodljivost, vendar pa prihaja v ceno. Na voljo je s tem obdobju stroške, in gre s tem spomina stroškov preveč. Čas, v smislu, da se moramo zdaj iti skozi vsak element v matriki da bi našli enega na indeksu 10, ali da bi bil indeks 10 v matriko. 

Samo res hitro, ko smo načrt iz teh seznamov, Običajno imamo na čelu seznama ali prvi kazalec seznama in ne pozabite, da je to pravi kazalec. To je samo 4 bajte. To ni dejanski Vozel sama. Torej vidite, da nima int vrednost v njem, ne naslednji kazalec v njem. To je dobesedno le kazalec. To se dogaja, da kažejo na nekaj, kar je dejansko vozlišče struct. [Sam] Kazalec se imenuje vozel? >> To je - ne. To je pokazatelj, kaj vozlišča tipa. To je kazalec na vozlišče struct. >> V redu. Graf na levi, na desni strani kode. Lahko jo nastavite na nič, kar je dober način za začetek. Ko ga diagram, ali boste napisali, da za nično, ali si dal črto skozi to všeč. 

Eden izmed najlažjih načinov za delo s seznami, in vas prosimo, ne tako pripnite in dodajte videti razlike med obema, vendar prepending je vsekakor lažje. Ko pripnite, to je, če boste - če prepend (7), greš in ustvariti vozlišča struct in nastavite najprej opozoriti na to, ker zdaj, saj smo jo pripeta, to se dogaja, da se na začetku seznama. Če bomo prepend (3), ki ustvari novo vozlišče, zdaj pa je pred 3 7. Torej smo v bistvu potiska stvari na našem seznamu. Sedaj lahko vidite, da prepend, včasih ljudje pravijo potiskanje, ker si prizadeva za nov element na seznamu. To je tako enostavno, da se črta na sprednji strani seznama. Tako bodo ljudje pogosto imenujejo, da pop. In na ta način, lahko posnemajo sveženj z uporabo povezani seznam. Ops. Žal mi je, zdaj smo dobili v za dodajanje. Torej, tukaj smo pripeta (7), zdaj smo prepend (3). Če želimo nekaj drugega, pripeta na tem seznamu, če bomo pripeta (4), potem bi imeli 4, nato 3, nato 7. Torej, potem bi lahko pop in odstranite 4, odstrani 3, 7 odstraniti. Pogosto bolj intuitiven način, da razmišljajo o tem, je z dodati. Tako sem grafično, kaj bo to videti z dodati tukaj. Tu priložen (7) ne izgleda nič drugače zato, ker je samo en element v seznamu. In dodajo (3) ocenjuje, da je konec. Mogoče si lahko ogledate sedaj trik z append je, da ker smo samo vedeti, kje je začetek seznama je priložiti k seznamu boste morali hoditi vso pot skozi seznam priti do konca, se ustavite, nato pa graditi svoje vozlišče in Prebirati vse navzdol. Žice vse stvari gor. Torej, z prepend, kot smo pravkar ripped skozi to res hitro, Ko pripnite na seznam, je dokaj preprost. 

Naredite svojo novo vozlišče, vključuje nekaj dinamično dodeljevanje pomnilnika. Torej, tukaj delamo vozlišče struct z malloc. Tako smo z malloc, saj boste, da razveljavi spomin za nas, za kasneje saj ne želimo, da ta - želimo, da ta spomin prisotna že dolgo časa. In smo dobili kazalec prostora v pomnilniku, ki smo ga pravkar dodeljena. Mi uporabljamo velikost vozlišča, ne bomo povzeli polja. Ne ročno ustvarjanje število bajtov, namesto tega uporabite sizeof, tako da vemo, da ste dobili ustrezno število bajtov. Mi se prepričajte, da preizkusite, da je naš klic malloc uspelo. To je nekaj, kar si želim početi v splošno. V sodobnih strojev, zmanjkuje pomnilnika ni nekaj, kar je preprosto razen če ste dodeljevanje tono stvari in kar ogromen seznam, ampak, če ste izgradnjo stvari za, recimo, kot iPhone ali Android, ti imajo omejene vire spomin, še posebej, če delaš nekaj hudo. Zato je dobro, da se v praksi. 

Obvestilo, da sem uporabljal nekaj različnih funkcij tukaj ki ste jih videli, da so nekako novo. Torej ovrednotenj je tako kot printf razen prvi trditvi je tok, ki ga želite natisniti. V tem primeru želimo tiskati na standardni niz napak ki se razlikuje od standardne outstream. Privzeto se pokaže na istem mestu. Prav tako natisne na terminal, vendar je to mogoče - uporabo teh ukazov ste se naučili o tem, preusmeritve tehnike ste se naučili o Tommy v videu za sklop 4 problem, ga lahko neposredno na različnih področjih, zaprite, tukaj, zapusti svoj program. To je v bistvu kot vrnitvi iz glavnega, razen uporabimo izhod, ker sem vrnitev ne bo naredil ničesar. Nismo v glavnem, da se ne vračajo zapreti program, kot si želimo. Zato bomo uporabili za izhod iz funkcije in mu kodo napake. Potem tukaj smo postavili novega vozlišča vrednost polja, njegov i polje, enaka i, potem pa ga priključite gor. Postavili smo novega vozlišča poleg kazalec, da kaže na eni strani, in potem najprej bo zdaj kaže na novo vozlišče. Te prve vrstice kode, smo dejansko gradnjo novega vozlišča. Ni zadnji dve vrstici te funkcije, vendar prvimi. Lahko dejansko potegnite v funkciji, v helper funkcije. To je pogosto kaj naredim je, da sem jo potegnil ven v funkciji I call it nekaj takega kot vozlišče gradnje, in da ohranja prepend funkcija precej majhen, je le 3 vrstice takrat. Sem klicati na mojo funkcijo vozlišče graditi, potem pa sem vse žice gor. 

Zadnja stvar, želim, da vam pokaže, in jaz bom ti dovolil dodajati in vse to na svoje, Ponovil je, kako v seznam. Obstaja kup različnih načinov, da izbirate preko seznama. V tem primeru, bomo našli dolžino seznama. Tako smo začeli z dolžino = 0. To je zelo podoben pisanju strlen v nizu. To je tisto, kar sem hotel pokazati, ta zanka se tukaj. To izgleda nekako funky, to ni običajna int i = 0, i <karkoli, i + +. Namesto tega se pri inicializaciji našo spremenljivko n, da je začetek seznama. In potem ko smo iterator spremenljivka ni nič, bomo naprej. To je zato, ker je po dogovoru, bo konec našega seznama je nična. In potem prirastek, namesto da delaš + +, povezani seznam ekvivalent + + je n = n-> next. 

Povedal ti bom, zapolniti vrzeli, saj smo tukaj zmanjkalo časa. Ampak to v mislih, kot delate na vašem spellr psets. Povezani seznami, če ste izvajanju razpršene tabele, bo zagotovo prišel zelo prav. In ob tem govorico za večkratno več stvari narediti življenje veliko lažje, upam. Vsa vprašanja, hitro? [Sam] boste poslali izpolnjen SLL in SC? [Hardison] Ja. Jaz bom poslal izpolnjenih diapozitivov in izpolnjeno SLL sklad in queue.cs. [CS50.TV]