Doug LLOYD: All right, tako da po tej točki ste ga verjetno precej pozna z nizi in povezanih seznamov ki je dve primarni podatkovne strukture, ki smo jih je govoril o za vodenje sklopov podatkov o podobnih podatkovnih tipov organizirani. Zdaj bomo govorili o nekaj sprememb o nizi in povezanih seznamov. V tem video bomo govoriti o nizov. Natančneje bomo govorili o struktura podatkov, ki se imenuje sklad. Odpoklic iz prejšnjih razprav o kazalci in spominu, da je sklad tudi ime za segment pomnilnika kjer statično razglasila memory-- spomin, ki vas ime, spremenljivke, ki si ime, et cetera in funkcija okvirji, ki smo tudi obstajajo klic konzoli okvirji. Torej, to je struktura podatkov kup ne kup segment pomnilnika. V REDU. 

Toda kaj je kup? Torej, to je precej samo posebna vrsta strukture da vzdržuje podatke na organiziran način. In tam je dva zelo pogosti načini za izvajanje nizov z uporabo dveh podatkovnih struktur da smo že poznajo, nizi in povezani seznam. Kaj naredi kup posebno je Način, na katerega smo dal podatke v dimnik, in način, kako odstrani podatke iz dimnika. Zlasti s skladovnice pravilo je le najbolj Nedavno se doda element možno odstraniti. 

Torej, razmišljam o tem, kot da je to kup. Mi smo piling informacije na vrhu sebi in samo stvar na vrhu kupa se lahko odstrani. Mi stvar ne more odstraniti pod ker vse ostalo bi kolaps in se prevrne. Torej smo res se gradi sklad, ki bomo potem morali odstraniti kos za kosom. Zaradi tega smo pogosto sklicuje na kupu kot strukturo LIFO, zadnji noter, prvi ven. LIFO, zadnji noter, prvi ven. 

Zato, ker te omejitve na kako se lahko dodajajo podatki in odstrani iz dimnika, da je res le dve stvari, ki jih lahko naredite z dimnika. Lahko potiskanje, ki je Izraz uporabljamo za dodajanje nov element na vrhu kup, ali če je sklad ne obstaja in smo ga ustvarili iz nič, ustvarjanje snop na prvem mestu bi potiska. In potem pop, da je nekako CS Izraz uporabljamo za odstranitev nazadnje dodamo element z vrha dimnika. 

Torej gremo pogledati na obe izvedb, ki temelji tako niz in povezani seznam, ki temelji. In bomo začnete s paleto temelji. Torej, tukaj je osnovna ideja o tem, kaj array temelji struktura podatkov kup bi izgledal. Imamo definicijo tipkani tukaj. Znotraj da imamo dva člana ali področja strukture. Imamo celo paleto. In spet sem z uporabo poljubna vrsta podatkov vrednost. 

Torej, to je lahko katera koli vrsta podatkov, int char ali nekatere druge podatke tip ste prej ustvarili. Torej imamo paleto velikosti zmogljivosti. Kapaciteta se funt definirana konstanta, morda nekje drugje v našem spisu. Torej opazili že s tem zlasti Izvajanje smo se povezuje sami, kot je bilo običajno na primer z nizi, ki je ne moremo dinamično spreminjanje velikosti, kjer je določeno število za največ elementov, ki bomo lahko v našem dimnika. V tem primeru je to elemente zmogljivosti. 

Prav tako spremljate vrh dimnika. Kaj element je najbolj Nedavno doda skladovnice? In tako smo spremljate da spremenljivo imenujemo vrh. In vse to dobi zaokrožila skupaj v novo vrsto podatkov, imenovano kup. In ko smo ustvarili Ta nova vrsta podatkov jo lahko obravnavajo kot katera koli druga vrsta podatkov. Mi lahko razglasi dimnika ov, prav tako kot kar lahko storimo int x, ali char y. In ko rečemo kup ov, dobro, kaj se zgodi se dobimo niz pomnilnika v prahi za nas. 

V tem primeru zmogljivosti Sem očitno odločil, 10, ker sem dobil enojna variabilna tipa skladovnice ki vsebuje dve polji odpokličejo. Matrika, v tem primeru se bo da bo niz števil kot je to primer v večini mojih primerov. In še celo spremenljivka lahko shrani vrha, Najbolj nedavno dodane element dimnika. Torej en kup, kar smo Samo opredeljena izgleda takole. To je škatla, ki vsebuje niz 10, kar bo cela v tem primeru in drugo število spremenljivka je v zeleni barvi navesti vrh dimnika. 

Če želite nastaviti vrhu Sveženj smo pravkar rekel s.top. To je, kako smo dostopite do polje strukture odpoklica. s.top enak 0 učinkovito pa to, da naši dimnika. Torej, spet imamo dve operaciji da bomo lahko sedaj opravljam. Mi lahko push in bomo lahko pop. Začnimo s pritiskom. Again, potiskanje je dodal nov element na vrhu kupa. 

Torej, kaj moramo storiti v Ta matrika izvedba temelji? No, na splošno funkcija Push se dogaja bi morali sprejeti kazalec na sklad. Sedaj vzemite drugega in razmišljati o tem. Zakaj bi si želeli, da sprejme kazalec na kupu? Odpoklic iz prejšnjih videov na spremenljivka obseg in kazalci, kaj bi se zgodilo, če bomo le poslal Sveženj, s precej v kot parameter? Kaj bi se dejansko prenesejo tja? Ne pozabite, da smo ustvarili kopijo ko smo jo prenese na funkcijo če bomo uporabili kazalce. In tako je ta funkcija potisnite potrebe da sprejme kazalec na kupu tako da smo dejansko spreminja Sveženj nameravamo spremeniti. 

Druga stvar, potisni verjetno želi sprejeti je podatkovni element tipa vrednosti. V tem primeru spet, celo število, ki bomo dodali na vrhu dimnika. Torej imamo naše dva parametra. Kaj bomo zdaj počnejo push? No, samo, da smo šele tekoč, da dodate ta element na vrhu kupa in nato spremenite kje na vrh Sveženj je, da S dot top vrednost. Torej, to je, kaj je funkcija Izjava Pritisni lahko izgledal v diod, ki temelji izvajanje. 

Tudi to ni težko in hitro pravilo da bi lahko to spremenili in imajo se med seboj razlikujejo. Morda se je razglasila globalno. In tako sploh ne potrebujemo da prenese je kot parameter. To je spet le splošno velja za pritiskom. In tam so drugačni načini za njeno izvajanje. Toda v tem primeru naše Pritisni in bo trajalo dva argumenta, kazalec na kup in podatkovni element tipa vrednosti, integer v tem primeru. 

Tako smo razglasila ov smo dejal s.top enak 0. Zdaj pa potisnite Številka 28 na kupu. No, kaj to pomeni? No, trenutno Vrh dimnika je 0. In kaj je v bistvu se bo zgodilo, je bomo držijo številko 28 v matrično mestu 0. Precej enostavno, kajne, da je bil najboljši in zdaj smo na dobri poti. In potem moramo spremeniti, kaj vrh dimnika bo. Tako da naslednjič, ko smo potiskanje element, bomo, da jo shranite v lokacija matrika, verjetno ni 0. Mi ne želimo prepisati kaj smo pravkar dal tam. In tako bomo samo premaknete vrha do 1. To je verjetno smiselna. 

Zdaj, če želimo postaviti še en element na kupu, recimo želimo potiskanje 33, tudi zdaj smo šele bo trajalo 33 in jo dal na matrično lokaciji številko 1, in nato spremenite vrhu našega kup da je matrika lokacija številka dve. Torej, če naslednjič, ko želimo potisni element na stack, ga bom dal v matrično mestu 2. In kaj je to naredil še enkrat. Bomo potisnite 19 off od nizov. Bomo dal 19 v matriki mestu 2 in spremenite vrh našega dimnika da je matrika mesto 3 tako da, če v naslednjem času smo morali narediti Pritisni smo na dobri poti. 

OK, tako da se potiska na kratko. Kaj popping? Tako živahen je neke vrste kolegom za potiskanje. To je, kako odstraniti podatke iz dimnika. In splošne potrebe pop storiti naslednje. Potrebuje, da sprejme kazalec na kup, spet v splošnem primeru. V nekem drugem primeru boste morda so izjavili, da sklad v svetovnem merilu, V tem primeru vam ni treba dajati V saj že ima dostop do njega kot globalne spremenljivke. Ampak potem, kaj storiti moramo storiti? Pa smo povečevanje na vrhu kupa v pritiskom, tako da bomo verjetno želeli da pojemanje vrh dimnika v pop, kajne? In potem seveda smo tudi dogaja, da želijo vrne vrednost, ki smo odstraniti. Če smo dodajanjem elementov, želimo dobiti elemente ven kasneje, bomo verjetno dejansko jih želite shraniti, zato smo jih ne šele izbrisati iz kup in potem ni z njimi. Na splošno, če smo potiskanje in popping tukaj želimo, da shranite to informacije na razumljiv način in zato tudi ne občutek, da samo ga zavrzite. Torej ta funkcija bi morala Verjetno vrne vrednost k nam. 

Torej, to je, kaj deklaracijo za pop morda videti, kot da v zgornjem levem kotu. Ta funkcija vrne Podatki o vrsti vrednosti. Spet smo bili z uporabo cela števila v celotnem besedilu. In to sprejme kazalec na kupu, kot njen edini argument ali edini parameter. Torej, kaj je pop boš naredil? Recimo, da želimo zdaj pop element off s. Torej, ne pozabite, sem rekel, da so nizov zadnji noter, prvi ven, LIFO podatkovnih struktur. Kateri element se dogaja, da odstrani iz skladovnice? Ali uganete, 19? Ker bi morali biti v redu. 19 je bil zadnji element smo dodali k kup, ko smo bili potiska elementov na, in tako se dogaja, da je prvi element, da postane odstraniti. To je, kot če bi rekli, 28, in potem smo dal 33 na vrhu je, in mi dal 19 na vrhu, da. Edini element moremo vzleteti, je 19. 

Zdaj v diagramu tukaj kaj sem naredil je nekako črta 19 iz matrike. To dejansko ni kaj bomo storili. Mi smo le, da bo vrste od pretvarjati, da ni tam. To je še vedno tam v da spominsko lokacijo, vendar smo šele tekoč, da ga ignorirati s spreminjanjem vrh našim skladovnice od tega 3 na 2. Torej, če smo bili do zdaj potiskanje en element na stack, da bi čez pisati 19. 

Ampak ne gredo skozi težave izbrišete 19 iz dimnika. Mi lahko samo pretvarjamo, da je ni tam. Za namene dimnika je to šlo, če spremenimo zgornji znaša 2 namesto 3. Vse je v redu, tako da je bilo precej bilo. To je vse, kar moramo storiti pop element off. Dajmo še enkrat. Tako sem ga v rdeči barvi tukaj kažejo, da smo kar en klic. Bomo narediti isto stvar. 

Torej, kaj se bo zgodilo? No, bomo za shranjevanje 33 vx in gremo spremeniti vrhu kupa 1. Tako da če smo bili zdaj potiskanje element v plasteh, ki sva storili zdaj, kaj se bo zgodilo se greva Prepiši matrika lokacija številka 1. Tako da je 33, ki je bil nekako levo zadaj, da smo samo pretvarjal ni več tam, da smo le, da bo da jo clobber in namesto tega dal 40 tam. In potem seveda, saj smo naredili potiskanje, bomo prirastek vrh dimnika od 1 do 2 tako da če smo zdaj dodali še en element, da bomo iti v matrično lokaciji številka dve. 

Zdaj povezani seznami so še en način za izvajanje nizov. In če te opredelitve na Zaslon tukaj izgleda znano za vas, to je zato, ker je videti skoraj popolnoma enako, v bistvu, je precej, je natanko Enako kot posamezno povezani seznam, če se spomnimo iz naše razprave posamezno povezana sezname v drugem videu. Edina omejitev tukaj je za nas kot programerji, smo ni dovoljeno vstavite ali izbrišete naključno od enkrat povezani seznam ki bi lahko že prej storiti. Mi lahko šele zdaj vstaviti in izbrisati iz sprednji ali na vrhu povezana seznam. To je res edina Razlika čeprav. To je sicer za enkrat povezani seznam. To je edina omejitev zamenjava na nas kot programerjev, ki ga spremeni v kup. 

Pravilo tukaj je, da vedno vzdržuje kazalec na čelu povezani seznam. To je seveda splošno Pomembno pravilo prvič. Za posamezno povezani seznam nekako vam potrebujete le kazalec na glavo z namenom, da ima to veriga lahko nanašajo za vsakega drugega elementa v povezanem seznamu. Ampak to je še posebej pomembna z dimnika. In tako na splošno, da ste bo dejansko želijo Ta kazalec bi lahko globalna spremenljivka. To je verjetno, da bo še lažje na ta način. Torej, kaj so analogi Pritisni in popa? Prav. Torej, spet potiska je dodal nov element dimnika. V povezanem seznamu pomeni, da bomo imeli ustvariti novo vozlišče, da smo bom dodal v povezanem seznamu in sledite skrbno korakom da smo že prej opisali v posamezno povezanih seznamov, da jo dodate veriga ne da bi poškodovali verigo in izgube ali orphaning koli elementi povezani seznam. In to je v bistvu tisto, ki Malo blob besedila tam povzema. In dajmo si oglejte na to kot diagram. 

Torej, tukaj je naša povezani seznam. To hkrati vsebuje štiri elemente. In še več popolnoma Tukaj je naš kup, ki vsebuje štiri elemente. In recimo, da hočemo sedaj potisnite nov element na tem kupu. In želimo, da potisnite nov postavka, katere podatki vrednost je 12. No, kaj bomo storili? No, najprej se bomo malloc prostor, dinamično dodeli prostor za novo vozlišče. In seveda takoj smo klic, da smo malloc vedno se prepričajte, da preverite, ali null, ker če imamo null nazaj je bil neke vrste problem. Nočemo, da dereference tem null kazalec ali pa boste trpeli napako SEG. To ni dobro. Torej smo malloced vozlišča. Bomo domnevati, da smo imeli uspeh tukaj. Bomo dal 12 v podatkovno polje vozlišča. Zdaj pa se spomnite, kateri od naših nasvetov premika zraven tako ne bomo prekinili verigo? Imamo nekaj možnosti tukaj, ampak edini, ki se dogaja, da je varna je določiti novice naslednji kazalec na točka na stari glavo seznama ali kaj bo kmalu bo stari vodja seznama. In zdaj, da so vsi naši Elementi so priklenjen skupaj, bomo lahko samo premaknete seznam za točko na istem mestu, da nova ne. In zdaj smo dejansko potisne Novost na sprednji strani skladovnice. 

Pop Pravkar smo želeli izbrisati to prvi element. In tako v bistvu tisto, moramo narediti tukaj, dobro se bomo morali najti drugega elementa. Sčasoma, da bo postala nova glavo, ko smo izbrisati prvo. Zato smo morali začeti iz začetek, premakniti eno naprej. Ko bomo dobili držite na enem naprej, kje smo trenutno smo lahko varno izbrisati prvo in potem bomo lahko samo premaknete glavo opozoriti na to, kar je bilo Drugi mandat in nato zdaj je prva po tem vozlišče je bil izbrisan. 

Torej še enkrat, ob poglej na njej kot diagram smo želijo zdaj pop element off tega dimnika. Torej, kaj naj naredimo? Pa smo prvič dogaja, da ustvarite nov kazalec, ki se dogaja da kaže na istem mestu kot konica. Bomo, da ga premaknete za eno mesto naprej z besedami trav enaka trav Naslednji primer, ki bi vnaprej trav kazalec eno na položaj naprej. Zdaj, ko imamo imajo na prvem elementu s kazalcem imenuje seznamu, in drugi element s kazalcem imenuje trav, bomo lahko varno izbrisati, da Prvi element iz skladovnice brez izgube ostalo verige, ker mi so način, da se sklicujem na drugi element posreduje preko izmed Kazalec se imenuje trav. 

Torej, zdaj smo lahko osvobodi tega vozlišča. Mi lahko osvobodi seznam. In potem vse, kar morate storiti, je zdaj premakniti seznam točke na istem mestu da trav počne, in smo nekako nazaj kjer smo začeli, preden smo potisnilo 12 na na prvem mestu, desno. To je točno tam, kjer smo bili. Imela sva štiri element dimnika. Dodali smo petino. Zavzeli smo petino element na, nato pa smo izstrelil da v zadnjem času Dodana element nazaj off. 

To je res precej vse, kar je nizov. Lahko jih izvajajo kot nizi. Lahko jih izvajajo kot povezanih seznamov. Obstajajo seveda druge načine za njihovo izvajanje, kot tudi. V bistvu razlog, da bi uporabili skladovnic je ohranjanje podatkov na tak način, da je nedavno dodane element je prva stvar, ki smo dogaja, da želijo, da bi dobili nazaj. Sem Doug Lloyd, to je CS50.