Doug LLOYD: Labi, tāpēc šajā brīdī jūs esat
iespējams, ir diezgan pazīstams ar masīvu un saistīti saraksti
kas ir divi galvenais datu struktūras mēs esam
runāja par glabāšanai komplekti dati par līdzīgiem datu tipu organizēta.
>> Tagad mēs runāsim par pāris izmaiņu
par masīvu un saistītiem sarakstiem.
Šajā video mēs ejam runāt par skursteņi.
Konkrēti mēs runāsim par datu struktūra sauc kaudze.
Atsaukt no iepriekšējām diskusijām par norādes un atmiņu,
ka kaudze ir arī nosaukumu segmentā atmiņas
kur statiski deklarētā memory-- atmiņas, kas jūs
nosaukt, mainīgie, jūs nosaukums, et tā tālāk un funkciju rāmji, ko mēs arī
zvanu kaudze rāmji pastāvēt.
Tātad šī ir kaudze datu struktūra nevis kaudze segments atmiņas.
LABI.
>> Bet kas ir kaudze?
Tātad, tas ir diezgan daudz tikai īpaša veida struktūra
kas saglabā datus organizētā veidā.
Un tur ir divas ļoti kopīgas veidus, lai īstenotu
skursteņi, izmantojot divus datu struktūras ka mēs esam jau iepazinušies ar,
bloki un saistīti saraksti.
Kas padara kaudze īpašs ir veids, kādā mēs ievietot informāciju
uz kaudze, un to, kā mēs izņemt informāciju no skursteņa.
Jo īpaši ar skursteņi noteikums ir tikai pats
Nesen pievienotās elements var noņemt.
>> Tāpēc domāju par to, kā tad, ja tas ir kaudze.
Mēs saliekot informāciju virsū sevi,
un tikai lieta augšpusē kaudzes var noņemt.
Mēs nevaram noņemt lieta zem jo viss pārējais būtu
sabrukt un apgāzties.
Tātad mēs tiešām veidojam kaudze, kas mums tad ir noņemt gabalu pa gabalu.
Šī iemesla dēļ mēs parasti attiecas uz kaudze kā LIFO struktūru,
pēdējais iekšā, pirmais ārā.
LIFO, pēdējais iekšā, pirmais ārā.
>> Tāpēc, ka šī ierobežojuma kā informācija var pievienot
un noņem no skursteņiem, tur tiešām tikai divas lietas, ko mēs varam darīt ar kaudzīti.
Mēs var virzīt, kas ir termins mēs izmantojam, lai pievienotu
jauns elements, lai augšpusē kaudze, vai ja kaudze neeksistē
un mēs esam izveidojot to no nulles, radot kaudzīti pirmajā vietā
būtu stumšanas.
Un tad pop, tas ir sava veida CS Termins mēs izmantojam, lai novērstu nesen
pievienots elements no augšas kaudze.
>> Tātad mēs ejam apskatīt gan realizācijas, gan masīvs balstīta
un saistīts saraksts pamatā.
Un mēs ejam sākt ar masīvu pamatā.
Tātad, šeit ir pamatideja, ko masīvs balstīta kaudze datu struktūra
izskatās.
Mums ir drukāti definīcija šeit.
Iekšpusē, ka mums ir divi locekļi vai lauki struktūru.
Mums ir masīvs.
Un atkal es esmu, izmantojot patvaļīga datu tips vērtība.
>> Tātad tas varētu būt jebkurš datu tips, int char vai kādu citu datu
ierakstiet jūs iepriekš izveidojis.
Tāpēc mums ir masīvs lieluma jaudu.
Capacity tiek mārciņu noteikta nemainīga, varbūt kaut kur citur mūsu failā.
Tātad paziņojums jau ar šo konkrēto īstenošana mēs iesiešana
paši kā parasti bija gadījums ar masīviem,
ko mēs nevaram mainīt dinamiski, ja tur ir noteikts skaits
maksimāli elementus, kas mēs varam nodot mūsu kaudze.
Šajā gadījumā tas ir jaudas elementus.
>> Mēs arī sekot līdzi top skursteņa.
Kas elements ir visvairāk nesen pievienota krāvuma?
Un tā mēs sekot līdzi, kas ar mainīgo sauc augšas.
Un tas viss izpaužas apkopoja kopā uz jaunu datu tipu sauc kaudze.
Un, kad mēs esam radīti Šī jaunā datu tips
mēs varam pret to kā jebkādu citu datu tipu.
Mēs varam atzīt kaudze s, tāpat kā mēs varētu darīt int x, vai char vec.
Un, kad mēs sakām kaudze s, arī to, kas notiek
ir mēs iegūt komplektu atmiņa atcelt mums.
>> Šajā lietā statusā Esmu acīmredzot nolēmis
ir 10, jo es esam ieguvuši single mainīgo tipa kaudze
kas satur divus laukus atcerēties.
Masīvs, šajā gadījumā notiek būt masīvs integers
kā tas ir lielākajā daļā no maniem piemēriem.
Un vēl viens skaitlis mainīgs spējīga uzkrāt top,
visvairāk nesen pievienoti elements uz krāvuma.
Tātad viena kaudze, ko mēs tāpat definē izskatās šādi.
Tas ir kārba, kas satur masīvs 10, ko
būs veseli skaitļi šajā gadījumā, un cits skaitlis mainīgs tur zaļā krāsā
lai norādītu augšējās.
>> Lai uzstādītu augšpusē kaudze mēs tikai teikt s.top.
Tas, kā mēs piekļūt lauks būves atsaukšanu.
s.top vienāds ar 0 efektīvi to dara mūsu kaudze.
Tātad atkal mums ir divas operācijas ka mēs varam veikt tagad.
Mēs varam virzīt, un mēs varam pop.
Sāksim ar push.
Atkal, spiežot ir pievienojot jaunu elements uz augšu kaudze.
>> Tātad, ko darīt, mums vajag darīt šis masīvs balstīta īstenošana?
Nu kopumā push funkcija notiek
uz nepieciešamību pieņemt rādītāju uz skursteņa.
Tagad veikt otru un domāt par to.
Kāpēc mēs vēlamies pieņemt rādītāju uz skursteņa?
Atsaukt no iepriekšējiem video par Mainīgais joma un norādes,
kas notiktu, ja mēs vienkārši nosūtīts kaudze, s drīzāk kā parametrs?
Kas faktiski nodots tur?
Atcerieties, mēs radītu kopiju kad mēs iet to funkciju
ja vien mēs izmantojam norādes.
Un tāpēc šī funkcija push vajadzībām pieņemt rādītāju uz skursteņa
tāpēc, ka mēs faktiski mainās kaudze mēs plānojam mainīt.
>> Otra lieta, push, iespējams, vēlas pieņemt ir datu elements no tipa vērtības.
Šajā gadījumā, atkal, vesels skaitlis, kas mēs ejam, lai pievienotu uz augšu kaudze.
Tātad, mēs esam ieguvuši mūsu divi parametri.
Ko mēs gatavojamies tagad darīt iekšpusē push?
Nu, vienkārši, mēs esam tikai gatavojas pievienot ka elements uz augšējās
un tad mainīt kur aug kaudze ir, ka s dot top vērtību.
Tātad, tas ir tas, ko funkcija deklarācija par push
varētu izskatīties izturēties masīvs bāzes ieviešana.
>> Atkal tas nav grūti un ātri noteikums ka jūs varētu mainīt šo un
tas atšķiras dažādos veidos.
Varbūt s ir deklarēti visā pasaulē.
Un tāpēc jums nav pat nepieciešams iziet tas ir kā parametru.
Tas ir atkal tikai Kopumā gadījumā push.
Un tur ir dažādi veidi, kā to īstenot.
Bet šajā gadījumā mūsu push gatavojas veikt
divi argumenti, rādītāju uz kaudze un datu elements tipa vērtību, skaitlim
šajā gadījumā.
>> Tātad mēs deklarēta s, mēs teica s.top vienāds ar 0.
Tagad pieņemsim push numuru 28 uz skursteņa.
Nu ko tas nozīmē?
Nu pašlaik top no skursteņa ir 0.
Un tā, kas ir būtībā gatavojas notikt, ir
mēs ejam, lai stick skaitu 28 uz masīvu atrašanās vietā 0.
Diezgan vienkārši, labi, ka bija top, un tagad mēs esam labi iet.
Un tad mums ir jāmaina, ko top no kaudze būs.
Tā, ka nākamreiz, kad mēs push elements,
mēs spēsim saglabāt to masīvs vieta, iespējams, nav 0.
Mēs nevēlamies pārrakstīt Ko mēs tikai izvirzīti tur.
Un tāpēc mēs vienkārši pārvietot augšas uz 1.
Tas droši vien ir jēga.
>> Tagad, ja mēs gribam, lai citu elementu uz steku, teikt, ka mēs vēlamies virzīt 33,
Nu tagad mēs esam tikai gatavojas veikt 33 un nodot to masīva vietas numurs
1, un pēc tam mainīt augšā mūsu kaudze būt masīvs vietas numurs divi.
Tātad, ja nākamajā reizē mēs vēlamies push elementu uz steku,
tas būs likts masīva vietā 2.
Un pieņemsim darīt, ka vēl vienu reizi.
Mēs push 19 nost no skursteņi.
Mēs nolikšu 19 masīva vietā 2 un mainīt top mūsu kaudze
būt masīva vieta 3 Tātad, ja nākamo reizi, kad mēs
nepieciešams, lai push mēs esam labi iet.
>> Labi, tā ka ir stumšanas īsumā.
Kas par popping?
Tātad popping ir sava veida partnere stumšanas.
Tā kā mēs noņemt datus no skursteņa.
Un vispār pop vajadzībām darīt šādi.
Tas nepieciešams pieņemt rādītāju uz kaudze, atkal vispārējā gadījumā.
Kādā citā gadījumā jūs varētu ir paziņojuši kaudze globāli,
tādā gadījumā jums nav nepieciešams nodot in, jo tas jau ir piekļuve tam
kā globālu mainīgo.
Bet tad ko vēl darīt, mums jādara?
Nu mēs bijām palielināšanai top kaudze ar push,
tāpēc mēs esam droši vien vēlaties lai Samazināt augšpusē kaudze
pop, vai ne?
Un tad, protams, mēs arī gatavojas vēlaties
lai atgrieztu vērtību ka mēs noņemam.
Ja mēs esam pievienojot elementus, mēs gribam iegūt elementus, kas vēlāk,
mēs, iespējams, faktiski vēlaties saglabāt tos, lai mēs
ne tikai izdzēst tos no kaudze un tad darīt neko ar tiem.
Parasti, ja mēs esam stumšana un popping šeit
mēs vēlamies saglabāt šo informāciju jēgpilnā veidā
un tāpēc tas nepadara jēga tikai atbrīvoties.
Tātad šī funkcija būtu iespējams atgriež vērtību pie mums.
>> Tātad tas ir tas, ko iesniegt deklarāciju par pop varētu izskatīties tur augšējā kreisajā stūrī.
Šī funkcija atgriež datu tipa vērtības.
Atkal mēs esam bijuši, izmantojot veseli skaitļi visā.
Un tā pieņem rādītāju uz kaudze kā tā vienīgais arguments vai vienīgais parametrs.
Tātad, kas ir pop gatavojas darīt?
Teiksim, mēs vēlamies, lai tagad pop elementu nost no s.
Tik atceros, es teicu, ka skursteņi ir pēdējais iekšā, pirmais ārā, LIFO datu struktūras.
Kurš elements gatavojas jāizņem no skursteņa?
Vai varat uzminēt, 19?
Tāpēc, ka tu būsi taisnība.
19 bija pēdējā elements mēs pievieno pie kaudze, kad mums bija stumšanas elementus uz,
Un tā tas notiek, lai pirmais elements, kas izpaužas noņemts.
Tas ir tā, it kā mēs teicām 28, un tad mēs ieliekam 33 uz augšu no tā,
un mēs ieliekam 19 virsū, ka.
Vienīgais elements, mēs varam pacelties ir 19.
>> Tagad diagrammā šeit to, ko es esmu darījusi ir sava veida svītro 19 no masīva.
Tas nav reāli ko mēs gatavojamies darīt.
Mēs esam tikai gatavojas veida no izlikties tā tur nav.
Tas joprojām ir tur ka vieta atmiņā,
bet mēs esam tikai gatavojas to ignorēt mainot top mūsu kaudze
no tā 3: 2.
Tātad, ja mēs tagad push vēl viens elements uz steku,
tas būtu vairāk nekā uzrakstīt 19.
>> Bet pieņemsim nav iet caur trouble svītrojot 19 no skursteņa.
Mēs varam tikai izlikties, ka tur nav.
Nolūkā skursteņa tas ir pagājis, ja mēs mainīt top būt 2, nevis 3.
Labi, tā ka bija diezgan daudz to.
Tas ir viss, kas mums jādara pop elementu off.
Darīsim to vēlreiz.
Tāpēc es esmu uzsvērusi to sarkanu šeit norāda mēs nesam citu zvanu.
Mēs ejam, lai darīt to pašu.
>> Tātad, kas notiek varētu notikt?
Nu, mēs ejam, lai saglabātu 33 X, un mēs ejam
mainīt augšējās 1.
Tā ka, ja mēs tagad ir virzīt elementu kaudze, kas mums esi
gatavojas darīt tieši tagad, kas notiek varētu notikt
ir mēs ejam pārrakstīt masīvs vietas numurs 1.
Tā, ka 33, kas bija sava veida atstāja aiz ka mēs tikai izlikās
nav tur vairs, mēs esam tikai gatavojas to clobber to un nodot 40 tur vietā.
Un tad, protams, jo mēs, push,
mēs ejam izmainiet augšējā mala no 1, lai 2
tā ka, ja mēs tagad pievienot vēl viens elements, tas būs
iedziļināties masīvu vietas divām skaits.
>> Tagad saistīti saraksti ir vēl viens veids, kā īstenot skursteņi.
Un, ja šajā definīcijā par tematu ekrāns šeit izskatās pazīstams ar jums,
tas ir tāpēc, ka tas izskatās gandrīz tieši tas pats, patiesībā,
tas diezgan daudz ir tieši tāds pats kā atsevišķi saistīta sarakstā,
Ja jūs atceraties no mūsu diskusijas par atsevišķi saistīts sarakstus citā video.
Vienīgais ierobežojums šeit ir mums kā programmētājiem,
mēs esam nav atļauts ievietot vai dzēst nejauši
No atsevišķi saistīta sarakstā ko mēs varētu darīt agrāk.
Tikai tagad mēs varam ievietot un dzēst no priekšējā vai augšpusē saistīta
saraksts.
Tas ir tiešām vienīgais Atšķirība gan.
Tas ir citādi atsevišķi saistīts saraksts.
Tas ir tikai ierobežojums aizstāt ar sevi
kā programmētāji, kas maina to kaudze.
>> Noteikums šeit ir vienmēr uzturēt rādītāju uz galvas saistītā saraksta.
Tas, protams, ir vispār Svarīgs noteikums pirmais.
Par atsevišķi saistīts saraksts vienalga jums tikai nepieciešams rādītāju uz galvas
lai būtu kas ķēde var nodot
uz jebkuru citu elementu kas saistīts sarakstā.
Bet tas ir īpaši svarīgi ar kaudzīti.
Un tā vispār esat gatavojas tiešām vēlaties
šis rādītājs ir globāla mainīga.
Tas iespējams, gatavojas būt vēl vienkāršāk, ka veidā.
Tātad, kādi ir analogi push un pop?
Tiesības.
Tātad spiežot atkal ir pievienojot jauns elements kaudze.
In saistītajā sarakstā, kas nozīmē, ka mēs esam nāksies
lai izveidotu jaunu mezglu, ka mēs esam gatavojas pievienot uz saistīts sarakstā,
un pēc tam izpildiet rūpīgu darbības ka mēs esam minēts iepriekš
jo atsevišķi saistītas sarakstos, lai pievienotu to ķēdi, nesalaužot ķēdi
un zaudēt vai orphaning jebkurš elementi, kas saistīti sarakstā.
Un tas būtībā, ko tas maz lāse teksta tur apkopoti.
Un pieņemsim to apskatīt pie tā kā diagrammā.
>> Tātad, šeit ir mūsu saistīts saraksts.
Tas vienlaikus ir četri elementi.
Un vēl pilnīgi šeit ir mūsu kaudze, kas satur četrus elementus.
Un pieņemsim, ka mēs tagad gribam push jaunu posteni uz šo kaudze.
Un mēs vēlamies, lai push jaunu priekšmetus, kuru dati vērtība ir 12.
Nu ko mēs gatavojamies darīt?
Nu, pirmkārt, mēs spēsim malloc telpu, dinamiski
piešķirt vietu jaunu mezglu.
Un, protams, uzreiz pēc mēs piezvanītu malloc mēs vienmēr
pārliecinieties, lai pārbaudītu null, jo, ja mēs saņēmām null atpakaļ
tur bija daži no problēmas veida.
Mēs nevēlamies, lai dereference šo null rādītāju vai jūs cietīs SEG vaina.
Tas nav labi.
Tātad, mēs esam malloced mezgla.
Mēs pieņemam, mēs esam bija panākumi šeit.
Mēs ejam, lai likt 12 uz datu lauks šajā mezglā.
Tagad jūs atcerēties, kurš no mūsu norādes pārceļas nākamais tāpēc mums nav pārtraukumu ķēdi?
Mums ir pāris iespējas, šeit, bet vienīgais, kas notiek, lai būtu droši
ir noteikt jaunumus nākamo rādītāju punkts uz veco galvas saraksta
vai ko drīz būs vecais vadītājs saraksta.
Un tagad, ka visi mūsu elementi tiek chained kopā,
mēs varam vienkārši pārvietot sarakstu norādīt uz to pašu vietu, kas jauns dara.
Un tagad mēs esam faktiski uzstājām jauns elements uz priekšu no skursteņa.
>> Pop mēs vienkārši vēlamies dzēst šo pirmo elementu.
Un tā būtībā kas mums ir jādara šeit,
arī mums ir jāatrod uz otro elementu.
Galu galā, kas kļūs par jauno galvu, kad mēs dzēst pirmo.
Tāpēc mums ir nepieciešams, lai sāktu no sākums, pārvietot vienu priekšu.
Kad mēs esam ieguvuši turēt uz vienu uz priekšu, kur mēs šobrīd
mēs varam izdzēst pirmā droši un tad mēs varam vienkārši pārvietot galvu
norādīt uz to, kas bija otrais termins, un tad tagad
ir pirmais pēc ka mezgls ir izdzēsta.
>> Tātad vēlreiz, ņemot apskatīt uz to kā diagrammā mums
gribu tagad pop elements pie šīs kaudze.
Tātad, ko mēs darām?
Nu mēs esam pirmais gatavojas izveidot jauns rādītājs, kas notiek
norādīt uz tajā pašā vietā kā galvas.
Mēs ejam, lai to pārvietotu vienu pozīciju priekšu, sakot Trav Vienāds
Trav blakus piemēram, kas varētu sekmēt Trav rādītāju vienu
pozīciju uz priekšu.
Tagad, ka mēs esam ieguvuši turēt uz pirmā elementa
caur rādītāja sauc saraksts, un Otrs elements caur rādītājs sauc
Trav, mēs varam droši izdzēst, ka Pirmais elements no skursteņa
nezaudējot pārējo ķēdes, jo mēs
ir veids, kā atsaukties otrajam elementam
nosūta, kas paredzētas ar rādītājs sauc trav.
>> Tāpēc tagad mēs varam atbrīvot šo mezglu.
Mēs varam brīvajā sarakstā.
Un tad viss, kas mums ir jādara tagad pārvietot sarakstu norādīt uz to pašu vietu
ka Trav dara, un mēs esam veida atpakaļ kur mēs sākām pirms mēs uzstājām 12
par pirmo vietu, pa labi.
Tas ir tieši tas, kur mēs bijām.
Mums bija šo četru elementu kaudze.
Mēs pievienoja piekto.
Mēs uzstājām piekto elements uz, un pēc tam mēs
popped ka nesen pievienots elements atpakaļ off.
>> Tas ir tiešām diezgan daudz visi ir skursteņi.
Jūs varat tos īstenot, kā masīvi.
Jūs varat tos īstenot kā saistīti sarakstus.
Ir, protams, citi veidi, kā tos īstenot, kā arī.
Būtībā iemesls, mēs varētu izmantot stacks ir, lai saglabātu datus tādā veidā,
ka nesen pievienotās elements ir pirmā lieta, ko mēs esam
gatavojas vēlaties, lai saņemtu atpakaļ.
Es esmu Doug Lloyd, tas ir CS50.