DUGSDAGS LOIDS: Labi, tāpēctātad šajā brīdī jūs, iespējams, jau labi
pārzināt masīvus un saistītos sarakstus, kas ir divas primārās datu
struktūras, par kurām mēs runājām, lai sakārtotu līdzīga veida datu
kopas.
Tagad mēs runāsim par pāris masīvu un saistīto sarakstu variācijām.
Šajā video mēs runāsim par skursteņiemstekiem.
Konkrēti, mēs runāsim par datu struktūru, ko sauc par steku.
AtgādinietAtcerieties no iepriekšējām diskusijām par rādītājiem un
atmiņu, ka kaudzesteks ir arī nosaukums atmiņas segmentam, kurā
statiski deklarēta atmiņa — jūsu nosauktā atmiņa, jūsu nosauktie
mainīgie utt., un funkciju rāmji, kurus mēs arī saucam par steka
kadriem/rāmjiem/ietvariem.
Tātad šī ir steka datu struktūra, nevis atmiņas steka segments.
Labi.
Bet kas ir kaudzesteks?
Tātad tā ir gandrīz tikai īpaša veida struktūra, kas organizētā veidā
uztur datus.
Un ir divi ļoti izplatīti veidi, kā ieviest stekus, izmantojot divas
mums jau zināmas datu struktūras — masīvus un saistītos sarakstus.
Tas, kas padara steku īpašu, ir veids, kā mēs ievietojam informāciju
stekā, un veids, kā mēs noņemam informāciju no steka.
Jo īpaši ar skursteņiemAttiecībā uz stekiem noteikums ir tāds, ka var
noņemt tikai pēdējo pievienoto elementu.
Tāpēc domājiet par to tā, it kā tas būtu kaudzesteks.
Mēs sakrājam informāciju sev virsūvienu uz otras, un var noņemt tikai
to, kas atrodas kaudzessteka augšpusē.
Mēs nevaram noņemt apakšā esošo lietu, jo viss pārējais sabruktu un
apgāztos.
Tātad mēs patiešām veidojam kaudzisteku, kas mums pēc tam ir jāizņem
pa gabalufragmentam.
Šī iemesla dēļ mēs parasti saucam par steku kāsteku par LIFO
struktūru, pēdējais iekšā, pirmais ārā.
LIFO, pēdējais iekšā, pirmais ārā.
Tāpēc šī ierobežojuma dēļ, kā informāciju var pievienot stekam un
izņemt no tāstā, ar steku mēs varam darīt tikai divas lietas.
Mēs varam pushpush, ko mēs lietojam, lai pievienotu jaunu elementu
steka augšpusē, vai arī, ja stekasteks nepastāv un mēs to veidojam no
nulles, steka izveide vispirms būtu stumšanaievietošana.
Un tad pop, tāds ir CS termins, ko mēs izmantojam, lai noņemtu pēdējo
pievienoto elementu no steka augšdaļas.
Tāpēc mēs apskatīsim abas ieviešanas — gan uz masīvu, gan uz saistīto
sarakstu bāzes.
Un mēs sāksim ar masīvu bāzesbāzi.
Tātad, lūk, pamatideja par to, kā izskatītos uz masīvu balstīta steka
datu struktūra.
Šeit mums ir drukāta definīcija.
Tajā mums ir divi struktūras locekļielementi vai lauki.
Mums ir masīvs.
Un atkal es izmantoju patvaļīgu datu tipa vērtību.
Tātad tas varētu būt jebkurš datu tips, int char vai kāds cits datu
tips, ko iepriekš izveidojāt.
Tātad mums ir dažādu izmēru jaudasizmēra ietilpības masīvs.
JaudaIetilpība ir mārciņajaucējzīmes noteikta konstante, iespējams,
kaut kur citur mūsu failā.
Tāpēc ņemiet vērā, ka jau ar šo konkrēto ieviešanu mēs ierobežojam
sevi, kā tas parasti notika ar masīviem, kuru izmērus nevaram
dinamiski mainīt, kur ir noteikts maksimālais elementu skaits, ko
varam ievietot savā kaudzēstekā.
Šajā gadījumā tie ir jaudasietilpības elementi.
Mēs arī sekojam līdzi kaudzessteka augšdaļai.
Kurš elements ir pēdējo reizipēdējais, kas pievienots stekam?
Un tāpēc mēs tam sekojam līdzi mainīgajā, ko sauc par top.
Un tas viss tiek apvienots jaunā datu tipā, ko sauc par kaudzisteku.
Kad esam izveidojuši šo jauno datu tipu, mēs varam to apstrādāt tāpat
kā jebkuru citu datu tipu.
Mēs varam deklarēt kaudzistack s, tāpat kā mēs varētu darīt ar int x
vai char y.
Un, kad mēs sakām kaudzestack s, tad notiek tā, ka mēs iegūstam
atmiņas kopu, kas mums ir paredzēta.
Šajā gadījumā es acīmredzot esmu nolēmis, ka ietilpība ir 10, jo man
ir viens steka tipa mainīgais, kas satur divus laukusdivu lauku
atsaukšanu.
Masīvs, šajā gadījumā būs veselu skaitļu masīvs, kā tas ir lielākajā
daļā manu piemēru.
Un vēl viens veselsvesela skaitļa mainīgais, kas spēj saglabāt
augšējo daļu, kas ir pēdējais pievienotais elements kaudzīteistekam.
Tātad viena mūsu tikko definētā kaudzeviens mūsu tikko definētais
steks izskatās šādi.
Tas ir lodziņš, kurā ir 10 masīvs, kas šajā gadījumā būs veseli
skaitļi, un vēl viens veselsvesela skaitļa mainīgais zaļā krāsā, lai
norādītu kaudzessteka augšdaļu.
Lai iestatītu kaudzessteka augšdaļu, mēs vienkārši sakām s.top.
Tādā veidā mēs piekļūstam struktūras atsaukšanas laukam.
s.top ir vienāds arequals 0 efektīvi to dara mūsu kaudzeistekā.
Tātad atkal mums ir divas darbības, kuras mēs varam veikt tagad.
Mēs varam spiestpush un mēs varam poppop.
Sāksim ar grūdienuievietošanu.
Atkal stumšanaievietošana ir jauna elementa pievienošana kaudzessteka
augšdaļai.
Tātad, kas mums jādara šajā masīva īstenošanā?
Kopumā push funkcijaifunction būs jāpieņem rādītājs uz steku.
Tagad nedaudz padomājiet par to.
Kāpēc mēs vēlamies pieņemt rādītāju uz steku?
AtgādinātAtcerieties no iepriekšējiem videoklipiem par mainīgo
tvērumu un norādēm, kas notiktu, ja mēs vienkārši nosūtītu steku, s
drīzāk kā parametru?
Kas tur īsti tiktu nodots?
Atcerieties, ka mēs veidojam kopiju, kad to nododam funkcijai, ja
vien neizmantojam norādesrādītājus.
Un tāpēc šai funkcijai ir jāpieņem rādītājs uz steku, lai mēs
faktiski mainītu steku, kuru plānojam mainīt.
Otra lieta, ko pushpush, iespējams, vēlas pieņemt, ir datu elements
ar tipa vērtību.
Šajā gadījumā atkal vesels skaitlis, ko mēs pievienosim kaudzessteka
augšdaļai.
Tātad mums ir divi parametri.
Ko mēs tagad darīsim grūdienaievietošanas iekšpusē?
VienkāršiNu, mēs vienkārši pievienosim šo elementu kaudzessteka
augšdaļai un pēc tam mainīsim to, kur atrodas kaudzessteka augšdaļa,
šī punktveidas dot top vērtībavērtību.
Tātad šādi varētu izskatīties funkcijas deklarācija push uz masīvu
balstītā implementācijāimplementēšanā.
Atkal šis nav stingrs noteikums, ka varat toko varētu mainīt un
mainītkas atšķirtos dažādos veidos.
Varbūt s ir deklarēts globāli.
Un tāpēc jums pat nav nepieciešams to nokārtotnodot kā parametru.
Šis atkal ir tikai vispārējs grūdienapush gadījums.
Un ir dažādi veidi, kā to īstenot.
Bet šajā gadījumā mūsu pushpush izmantos divus argumentus, rādītāju
uz steku un datu elementu ar tipa vērtību, šajā gadījumā vesels
skaitlisveselu skaitli.
Tātad mēs deklarējām s, mēs teicām, ka s.top ir vienāds arequals 0.
Tagad uzspiedīsim uz kaudzes numuruievietosim stekā skaitli 28.
Nu, ko tas nozīmē?
Šobrīd steka augšdaļa ir 0.
Tātad būtībā notiks tas, ka mēs ielīmēsimievietosim skaitli 28 masīva
vietā 0.
Diezgan vienkārši, labi, tā bija virsotneaugšdaļa, un tagad mēs varam
iet.
Un tad mums ir jāmaina, kāda būs kaudzessteka augšdaļa.
Lai nākamreiz, kad ievietosim elementu, mēs to saglabāsim masīva
vietā, iespējams, nevisvisticamāk, ne 0.
Mēs nevēlamies pārrakstīt to, ko tikko ievietojām.
Tāpēc mēs tikai pārvietosim augšdaļu uz 1.
TasTam droši vien ir jēga.
Tagad, ja mēs vēlamies ievietot kaudzēstekā vēl vienu elementu,
sakiet, kateiksim, mēs vēlamies nospiestievietot 33, tagad mēs
vienkārši paņemsim 33 un ievietosim to masīva vietā ar numuru 1 un
pēc tam mainīsim steka augšdaļu uz masīva atrašanās vietu. numur
divi.
Tātad, ja nākamreiz mēs vēlamies ievietot elementu stekā, tas tiks
ievietots masīva 2. vietā 2.
Un darīsim to vēl vienu reizi.
Mēs izspiedīsimizņemsim 19 no skursteņiemstekiem.
Mēs ievietosim 19. masīva 2. vietā19 masīva vietā 2 un mainīsim mūsu
kaudzessteka augšdaļu uz 3. masīva atrašanās vietu 3, tāpēc, ja
nākamreiz mums būs jāveic grūdiensievietošana, mēs esam gatavi.
Labi, tātad tā ir ievietošana īsumā.
Kā ar poppingpopping?
Tātad poppingizņemšana ir sava veida līdzinieks
grūstīšanaiievietošanai.
Tādā veidā mēs noņemam datus no steka.
Un vispār poppop ir jādara šādi.
Tai ir jāpieņem rādītājs uz steku, atkal vispārīgā gadījumā.
Citā gadījumā jūs, iespējams, esat deklarējis steku globāli, un tādā
gadījumā jums tas nav jānodod, jo tai jau ir piekļuve kā globālajam
mainīgajam.
Bet kas tad vēl mums jādara?
Mēs palielinājām steka augšdaļu stumšanaspush režīmā, tāpēc mēs,
iespējams, vēlēsimies samazināt steka augšējo daļu poppop
spēlērežīmā, vai ne?
Un tad, protams, mēs arī vēlēsimies atgriezt noņemto vērtību.
Ja mēs pievienojam elementus, mēs vēlamies tos iegūt vēlāk, mēs,
iespējams, vēlamies tos saglabāt, lai mēs vienkārši neizdzēstu tos no
steka un pēc tam ar tiem neko nedarītu.
Parasti, ja mēs šeit spiežam un uzspiežamizmantojam pushing un
popping, mēs vēlamies šo informāciju glabāt jēgpilnā veidā, tāpēc nav
jēgas to vienkārši izmest.
Tāpēc šai funkcijai, iespējams, mums vajadzētu atgriezt vērtību.
Tātad šādi varētu izskatīties popmūzikaspop deklarācija augšējā
kreisajā stūrī.
Šī funkcija atgriež datus ar tipa vērtību.
Mēs atkal esam izmantojuši veselus skaitļus.
Un tas pieņem rādītāju uz steku kā vienīgo argumentu vai vienīgo
parametru.
Ko tad popspop darīs?
Pieņemsim, ka tagad vēlamies izceltizņemt elementu no s.
Tāpēc atcerieties, ka es teicu, ka steki ir pēdējie iekšā, pirmie
ārā, LIFO datu struktūras.
Kurš elements tiks noņemts no kaudzessteka?
Vai tu uzminējiuzminējāt 19?
Jo tevjums būtu taisnība.
19 bija pēdējais elements, ko pievienojām skursteistekam, kad
uzspiežāmpievienojām elementus, un tādējādi tas attiecas uz pirmo
elementu, kas tiek noņemts.
Tas ir tā, it kā mēs teicām 28, un tad mēs tam uzlikām 33 uz tā, un
mēs uzliekam 19 uz tā.
Vienīgais elements, ko varam paceltiesnoņemt, ir 19.
Tagad šajā diagrammā tas, ko esmu izdarījis, ir it kā izdzēsts 19 no
masīva.
Tas patiesībā nav tas, ko mēs darīsim.
Mēs tikai izliksimies, ka tā tur nav.
Tas joprojām atrodas šajā atmiņas vietā, taču mēs to vienkārši to
ignorēsim, mainot mūsu kaudzessteka augšdaļu no 3 uz 2.
Tātad, ja mēs tagad ievietotu citu elementu kaudzēstekā, tas
pārrakstītu 19.
Bet nepiedzīvosim problēmas ar 19 dzēšanu no steka.
Mēs varam izlikties, ka tā tur nav.
KaudzītesSteka vajadzībām tas vairs nebūs, ja augšējo daļu mainām uz
2, nevis 3.
Labi, tātad gandrīz viss tas bija gandrīz viss.
Tas ir viss, kas mums jādara, lai noņemtu kādu elementu.
Darīsim to vēlreiz.
Tāpēc šeit esmu to iezīmējis sarkanā krāsā, lai norādītu, ka mēs
veicam vēl vienu zvanuizsaukumu.
Mēs darīsim to pašu.
Kas tad notiks?
Nu, mēs saglabāsim 33 x un mainīsim kaudzessteka augšdaļu uz 1.
Tātad, ja mēs tagad ievietosim elementu kaudzēstekā, tas, ko mēs
tūlīt darīsim, mēs pārrakstīsim masīva atrašanās vietas
numuruskaitli 1.
Tā, ka 33, kas palika aiz mugurasTā kā 33 tika atstāts, mēs
izlikāmies, ka tā vairs nav, mēs to vienkārši noplēsimnoņemsim un
ievietosim 40.
Un tad, protams, tā kā mēs veicām grūdienuievietošanu, mēs
palielināsim kaudzessteka augšdaļu no 1 līdz 2, lai, ja tagad
pievienosim vēl vienu elementu, tas nonāktu masīva otrajā vietā divi.
Tagad saistītie saraksti ir vēl viens veids, kā ieviest stekus.
Un, ja šī ekrānā redzamā definīcija jums šķiet pazīstama, tas ir
tāpēc, ka tā izskatās gandrīz tieši tāda pati, patiesībā tā ir
gandrīz tāda pati kā atsevišķi saistītais saraksts, ja atceraties no
mūsu diskusijas par atsevišķi saistītajiem sarakstiem citā. video.
Vienīgais ierobežojums šeit attiecas uz mums kā programmētājiem, mēs
nedrīkstam ievietot vai dzēst nejauši no atsevišķi saistītā saraksta,
ko mēs varējām darīt iepriekš.
Mēs varam ievietot un dzēst tikai saistītā saraksta priekšpusē vai
augšpusē.
Tomēr tā patiešām ir vienīgā atšķirība.
Citādi šis ir atsevišķi saistīts saraksts.
Tas ir tikai ierobežojums, kas aizstāj mūs kā programmētājus, kas to
pārvērš kaudzēstekā.
Noteikums šeit ir vienmēr saglabāt rādītāju uz saistītā saraksta
galvgaligalvu.
Tas, protams, vispirms ir vispārīgi svarīgs noteikums.
Atsevišķi saistītam sarakstam jebkurā gadījumā ir nepieciešams
rādītājs tikai uz galvu, lai šī ķēde varētu atsaukties uz katru citu
saistītā saraksta elementu.
Bet tas ir īpaši svarīgi ar kaudzisteku.
Tātad kopumā jūs patiešām vēlaties, lai šis rādītājs būtu globāls
mainīgais.
Iespējams, ka šādā veidā būs vēl vieglāk.
Tātad, kādi ir push un pop analogi?
Pareizi.
Tātad atkārtota spiešanapushing nozīmē jauna elementa pievienošanu
kaudzīteistekam.
Saistītajā sarakstā tas nozīmē, ka mums būs jāizveido jauns mezgls,
ko pievienosim saistītajam sarakstam, un pēc tam veiciet rūpīgās
darbības, kuras iepriekš aprakstījām atsevišķi saistītajos sarakstos,
lai to pievienotu ķēdiķēdei, nepārraujot ķēdi un
pazaudējotnepazaudējot vai nepadarot par bāreņiemneiznīcinot
saistītos saraksta elementus.
Un tas būtībā ir tas, ko tā mazā teksta lāsetas nelielais teksts tur
apkopo.
Un aplūkosim to kā diagrammu.
Tātad, šeit ir mūsu saistītais saraksts.
Tajā vienlaikus ir četri elementi.
Un vēl perfektāklabāk šeit ir mūsu kaudzesteks, kurā ir četri
elementi.
Un pieņemsim, ka mēs tagad vēlamies ievietot jaunu vienumu šajā
kaudzēstekā.
Un mēs vēlamies nosūtītievietot jaunu vienumu, kura datu vērtība ir
12.
Nu, ko mēs darīsim?
Vispirms mēs izmantosim mallocizvēlēsimies vietu, dinamiski
piešķirsim vietu jaunam mezglam.
Un, protams, tūlīt pēc zvanīšanas uz malloc izsaukuma mēs vienmēr
pārliecināmies, vai nav nulles, jo, ja mēs saņemam nulli, radās kāda
veida problēma.
Mēs nevēlamies atsaukties uz šo nulles rādītāju, pretējā gadījumā jūs
cietīsit seg kļūdu.
Tas nav labi.
Tātad mēs esam novirzījušies no mezglaizveidojuši mezglu.
Mēs pieņemsim, ka mums šeit ir panākumi.
Mēs ievietosim 12 šī mezgla datu laukā.
Vai atceraties, kurš no mūsu rādītājiem virzās tālāk, lai mēs
nepārrautu ķēdi?
Šeit ir dažas iespējas, taču vienīgā drošadrošā ir iestatīt ziņu
nākamo rādītāju, lai norādītu uz veco saraksta galveni vai to, kas
drīzumā būs vecā saraksta galvgalīgalvene.
Un tagad, kad visi mūsu elementi ir savienoti kopā, mēs varam
vienkārši pārvietot sarakstu, lai norādītu uz to pašu vietu, kur to
darauz kuru norāda jaunais.
Tagad mēs esam efektīvi ievietojuši jaunu elementu kaudzessteka
priekšpusē.
Lai parādītuizmantotu pop, mēs vienkārši vēlamies izdzēst pirmo
elementu.
Un tāpēc būtībā tas, kas mums šeit ir jādara, mums ir jāatrod otrais
elements.
Galu galā tas kļūs par jauno galvu pēc tam, kad mēs izdzēsīsim pirmo.
Tāpēc mums vienkārši jāsāk no sākuma, jāvirzās uz priekšu.
Kad esam sapratušiieguvuši vienu uz priekšu, kur mēs pašlaik
atrodamies, varam droši dzēst pirmo, un tad mēs varam vienkārši
pārvietot galvu, lai norādītu uz to, kas bija otrais termins, un
tagad ir pirmais pēc šī mezgla dzēšanas. .
Tātad vēlreiz, aplūkojot to kā diagrammu, mēs tagad vēlamies noņemt
elementu no šīs kaudzesšī steka.
Tātad, ko mēs darām?
Vispirms mēs izveidosim jaunu rādītāju, kas norādīs uz to pašu vietu,
kur galva.
Mēs to pārvietosim par vienu pozīciju uz priekšu, piemēram, sakot, ka
trav ir vienāds ar trav nākamotrav equals trav , kas virzīs trav
rādītāju par vienu pozīciju uz priekšu.
Tagad, kad esam noturējušiieguvuši pirmo elementu, izmantojot
rādītāju, ko sauc par sarakstu, un otro elementu, izmantojot rādītāju
trav, mēs varam droši izdzēst šo pirmo elementu no steka, nezaudējot
pārējo ķēdes daļu, jo mums ir veids, kā lai atsauktosatsaukties uz
otro elementu uz priekšu, izmantojot rādītāju trav.
Tātad tagad mēs varam atbrīvot šo mezglu.
Mēs varam brīviatbrīvot sarakstu.
Un tad viss, kas mums tagad jādara, ir jāpārvieto saraksts, lai
norādītu uz to pašu vietu, kur to dara trav, un mēs esam atgriezušies
tur, kur sākām, pirms 12. virsmas palielinājāmievietojām 12 pirmajā
vietā, pareizi.
Tieši šeit mēs bijām.
Mums bija šīšis četru elementu kaudzesteks.
Mēs pievienojām piekto.
Mēs uzspiedāmievietojām piekto elementu un pēc tam atslēdzāmizņemām
pēdējo pievienoto elementu.
Tas tiešām ir gandrīz viss, kas saistīts ar skursteņiemstekiem.
Jūs varat tos ieviest kā masīvus.
Varat tos ieviest kā saistītos sarakstus.
Protams, ir arī citi veidi, kā tos īstenot.
Būtībā iemesls, kāpēc mēs izmantotu skursteņusstekus, ir datu
uzturēšana tā, lai pēdējais pievienotais elements būtu pirmais, ko
mēs vēlamies atgūt.
Es esmu Dags Loids, šis ir cs50.