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.