Doug LLOYD: Gerai, taip šiuo klausimu esate
tikriausiai gana susipažinę su matricomis ir susijusių sąrašus
kuris yra du pirminės duomenų struktūros mes
kalbėjo apie laikymo rinkiniai duomenys panašių duomenų tipų organizuotas.
>> Dabar mes ketiname kalbėti apie keletą variacijų
ant matricos ir susijusių sąrašus.
Šiame vaizdo mes ketiname kalbėti apie šūsnis.
Tiksliau, mes ketiname kalbėti apie duomenų struktūra vadinama kamino.
Prisiminkite iš ankstesnių diskusijų apie nurodymus ir atminties,
kad kamino yra taip pat vardą kaip atminties segmentą
kur statiškai paskelbė memory-- atminties, kuri jus
pavadinimą, kintamieji, kad jūs Vardas et Cetera ir funkcijų rėmai kurią mes taip pat
Skambučių kamino rėmai egzistuoja.
Taigi tai yra kamino duomenų struktūra nėra kamino segmentas atmintį.
GERAI.
>> Bet kas yra kamino?
Taigi, tai gana daug tik specialios rūšies struktūros
kad palaiko duomenis organizuotu būdu.
Ir ten du labai paplitusių būdų įgyvendinti
kaminai, naudojant du duomenų struktūras kad mes jau esate susipažinę su,
matricas ir susiję sąrašus.
Ką daro kamino ypatingą yra būdas, kuriuo mes įdėti informaciją
į krūvą, kaip mes pašalinti informaciją iš kamino.
Visų pirma su kaminai taisyklė yra tik labiausiai
neseniai pridėta elementas gali būti pašalintas.
>> Taigi manau, apie tai, kaip jei tai kamino.
Mes polių informacija ant savaime,
ir tik viršuje dalykas krūva gali būti pašalintas.
Mes negalime pašalinti dalykas po nes visa kita būtų
žlugti ir nukristi.
Taigi mes tikrai statome krūvą, kad tada mes turime pašalinti gabalėlį.
Dėl šios priežasties mes dažniausiai nurodo į krūvą, kaip LIFO struktūrą,
paskutinis in, first out.
LIFO, paskutinis, pirmasis iš.
>> Taigi dėl šio apribojimo kaip informacija gali būti įtraukta į
ir pašalinti iš kamino, ten tikrai Tik du dalykai, ką galime padaryti su kamino.
Mes gali stumti, kuris yra Terminas mes naudojame pridedant
naujas elementas į viršų sukrauti, arba jei kamino neegzistuoja
ir mes jį kurti nuo nulio, sukurti į pirmąją vietą krūvą
būtų stumti.
Ir tada pop, tai CS Rūšiuoti Terminas mes naudojame pašalinti labiausiai neseniai
pridėta elementą iš kamino viršuje.
>> Taigi mes ketiname pažvelgti tiek diegimas, tiek masyvo remiantis
ir susijusi sąrašas pagrįstas.
Ir mes ketiname pradėti su masyvo pagrįstos.
Taigi čia yra pagrindinė idėja, ką masyvo remiantis kamino duomenų struktūra
atrodys.
Mes turime įvedėte apibrėžimą čia.
Viduje, kad mes turime du narius laukai ar struktūros.
Mes turime masyvą.
Ir vėl aš, naudojant savavališkai duomenų tipas vertė.
>> Taigi, tai gali būti bet koks duomenų tipas, int char arba kai kiti duomenys
įrašykite anksčiau sukurta.
Taigi, mes turime nuo jų dydžio pajėgumus masyvo.
Talpa yra svaras apibrėžta pastovus, gal kažkur kitur mūsų faile.
Taigi pastebėti jau su šio įgyvendinimas mes aprėpties
save, kaip buvo paprastai atveju matricos,
kurių mes negalime dinamiškai keisti dydį, kur yra tam tikras skaičius
elementų daugiau, kad mes galime įdėti mūsų kamino.
Šiuo atveju tai gebėjimas elementus.
>> Mes taip pat sekti rietuvės viršaus.
Tai, kas elementas yra labiausiai neseniai pridėta prie kamino?
Ir todėl mes sekti, kad kintamu vadinamas viršuje.
Ir visa tai bus suvynioti kartu į naują duomenų tipą, vadinamą kamino.
Ir kai mes sukūrėme Ši nauja duomenų tipas
galime traktuoti kaip bet koks kitas duomenų tipas.
Mes galime paskelbti kamino s, kaip mes galime padaryti int x, arba char m.
Ir kai sakome sukrauti ai, gerai, kas atsitinka,
yra mes gauti rinkinį atminties atidėta mus.
>> Šiuo atveju talpos Aš, matyt, nusprendė
10 nes aš turiu vieno kintamojo tipo kamino
kuriame yra du laukai prisiminti.
Masyvas, šiuo atveju vyksta turi būti iš sveikųjų skaičių masyvas
kaip yra daugumoje mano pavyzdžių atveju.
Ir dar vienas sveikasis skaičius kintamasis gali saugoti viršų,
labiausiai neseniai papildė elementas prie kamino.
Taigi vienas kamino, ką mes tik apibrėžta atrodo taip.
Tai dėžutė, kurioje yra kaip 10 matrica, kas
bus sveikieji šiuo atveju ir kitą kintamąjį, ten žalia
nurodyti rietuvės viršuje.
>> Norėdami nustatyti viršutinio kamino mes tiesiog pasakyti s.top.
Štai kaip mes prieiti prie srityje statinio atšaukimo.
s.top lygus 0 efektyviai tai daro mūsų kamino.
Taigi dar kartą mes turime dvi operacijas kad mes galime atlikti dabar.
Mes galime stumti, ir mes galime pop.
Pradėkime paspaudimu.
Vėlgi, stūmimas yra pridėti naują elementas kamino viršuje.
>> Taigi, ką mes turime daryti, šio masyvo remiantis įgyvendinimas?
Na apskritai Push funkcija vyksta
to reikia priimti rodyklę į krūvą.
Dabar imtis antrą ir galvoti apie jį.
Kodėl mes norime priimti rodyklė į krūvą?
Prisiminkite iš ankstesnių video apie kintamasis apimtis ir patarimų,
kas nutiktų, jei mes tiesiog atsiuntė kamino, s, o į kaip parametras?
Ką iš tikrųjų praėjo ten?
Įsiminti mes sukurti kopiją kai mes pereiname jį funkcija
nebent mes naudojame patarimų.
Ir taip ši funkcija stumti poreikius priimti žymeklį į rietuvę
taip, kad mes iš tikrųjų keičiasi kamino mes ketiname pakeisti.
>> Kitas dalykas, stumti tikriausiai nori priimti yra duomenų elementas tipo vertės.
Šiuo atveju, vėl, yra sveikas skaičius, kad mes ketiname pridėti prie kamino viršaus.
Taigi mes turime mūsų du parametrus.
Ką mes ketiname dabar daryti viduje stumti?
Na, tiesiog, mes tiesiog ketiname pridėti kad elementas, kamino viršuje
ir tada pakeisti, kur viršuje kamino yra, kad ai dot viršų vertę.
Taigi tai yra tai, ką funkcija deklaracija paspaudimu
gali atrodyti nurodytame masyvo pagrindu įgyvendinimas.
>> Vėlgi, tai nėra sunku ir greitai taisyklės , kad galėtumėte pakeisti tai ir
jis gali skirtis skirtingais būdais.
Galbūt s pareiškė visame pasaulyje.
Ir todėl jūs net nereikia praeiti ji yra, kaip parametras.
Tai vėl tik Apskritai dėklas paspaudimu.
Ir yra skirtingi būdų, kaip jį įgyvendinti.
Bet šiuo atveju mūsų stumti ketina imtis
du argumentai, rodyklė į krūvą ir duomenų elemento tipo verte, sveikasis skaičius
tokiu atveju.
>> Taigi, mes paskelbė s, mes sakė s.top lygus 0.
Dabar galime stumti numeris 28 ant kamino.
Na, ką tai reiškia?
Na šiuo metu Į viršų kamino yra 0.
Ir kas taip iš esmės nutiks tai
mes ketiname laikytis numerį 28 į masyvą vietoje 0.
Gana paprasta, tiesa, kad buvo viršuje, o dabar mes gerai eiti.
Ir tada mes turime pakeisti tai, ką rietuvės viršaus bus.
Taip, kad kitą kartą mes stumti in elementas,
mes ketiname laikyti jį masyvas vietą, tikriausiai ne 0.
Mes nenorime, kad perrašyti Ką mes tiesiog įdėti ten.
Ir todėl mes tiesiog perkelti viršaus į 1.
Tai tikriausiai turi prasmę.
>> Dabar, jei mes norime įdėti kitą elementą ant kamino, sako, kad mes norite stumti 33,
Na, dabar mes tik ketina imtis 33 ir įdėti jį masyvo vietos numerį
1, ir tada pakeisti viršuje mūsų kamino turi būti masyvas vietą numeris du.
Taigi, jei kitą kartą mes norime stumti elementą ant kamino,
Tai bus įdėti į masyvą vietoje 2.
Ir darykime, kad vienas daugiau laiko.
Mes stumti 19 off rietuvių.
Mes įdėti 19 masyvo vietoje 2 ir pakeisti mūsų kamino viršų
būti masyvas vieta 3 Taigi, jei kitą kartą mes
reikia padaryti push mes gera eiti.
>> Gerai, kad manimi stumia trumpai.
Ką apie Popping?
Taigi Popping yra tarsi priešinys stumia.
Tai, kaip mes pašalinti duomenis iš kamino.
Ir apskritai pop poreikius daryti toliau.
Reikia sutikti rodyklę į kamino, vėl bendruoju atveju.
Kai kuriose kitu atveju jums gali pareiškė kamino visame pasaulyje,
Tokiu atveju jums nereikia perduoti jį į, nes jis jau turi prieigą prie jo
kaip pasaulio kintamasis.
Bet tada ką dar mes turime daryti?
Na mes buvome incrementing Iš Tiesioginio kamino viršaus,
todėl mes tikriausiai norės į Mažėja kamino viršų
pop, tiesa?
Ir tada, žinoma, mes taip pat norės
grąžinti vertę, kad mes pašalinti.
Jei mes pridėti elementus, mes norime gauti elementus iš vėliau,
mes tikriausiai iš tikrųjų nori laikyti juos, kad mes
ne tiesiog ištrinti juos iš sukrauti ir tada nieko su jais.
Apskritai, jei mes stumti ir Popping čia
norime laikyti šį informacija prasmingai
ir taip tai nereiškia, kad jausmas tiesiog jį išmeskite.
Taigi ši funkcija turėtų tikriausiai grąžina reikšmę mums.
>> Taigi tai, kas deklaracija pop gali atrodyti kaip ten viršuje kairėje.
Ši funkcija grąžina duomenų tipo vertės.
Vėlgi mes buvome naudojant sveikieji skaičiai visoje.
Ir ji priima žymiklį į kamino kaip jos vienintelis argumentas ar vienintelis parametras.
Taigi, kas yra pop ketinate daryti?
Tarkime, mes norime dabar pop elementas off s.
Taigi nepamirškite pasakiau, kad kaminai paskutinis in, first out, LIFO duomenų struktūras.
Kuris elementas ketina būti pašalintas iš kamino?
Ar galite atspėti, 19?
Kadangi jūs norite būti teisus.
19 buvo paskutinis elementas mes pridėjome į kamino, kai mes buvome stumia elementus,,
ir todėl ji ketina pirmas elementas, kuris pašalinamas.
Tai tarsi mes sakėme, 28, ir tada mes įdėti 33 ant jo,
ir mes įdėti 19 viršuje, kad.
Vienintelis elementas mes galime pakilti yra 19.
>> Dabar diagramoje čia, ką aš padariau yra tarsi ištrinta nuo 19 masyvo.
Tai ne iš tikrųjų ką mes ketiname daryti.
Užtenka tik ketina rūšies iš apsimesti, kad nėra.
Jis vis dar ten kad atminties vietą,
bet mes tik ketina jį ignoruoti keičiant mūsų kamino viršų
gražu 3 2.
Taigi, jei mes dabar stumti kita ant kamino elementas,
tai per parašyti 19.
>> Bet tegul ne eiti per bėdų ištrynę 19 iš kamino.
Mes galime tik apsimesti, kad nėra.
Taikant kamino jis dingo, jei mes pakeisti viršuje, kad būtų 3 2, o ne.
Gerai, kad buvo gana daug.
Tai viskas, ką reikia padaryti pop elementas išjungtas.
Darom dar kartą.
Taigi aš pabrėžė, kad raudona spalva čia rodo, mes darome kitą skambutį.
Mes ketiname padaryti tą patį.
>> Taigi, kas nutiks?
Na, mes ketiname saugoti 33 X ir mes ketiname
pakeisti kamino viršaus iki 1.
Taigi, kad jei mes dabar stumti elementas į krūvą, kuri mes
ketina daryti dabar, kas nutiks
yra mes ketiname perrašymo masyvas vietą numeris 1.
Taigi, kad 33, kuris buvo tarsi liko atsilieka, kad mes tik apsimetė
ten nėra daugiau, mes tik ketina į Clobber ją ir įdėti 40 ten vietoj.
Ir tada, žinoma, nes mes padarė stumti,
mes ketiname prieaugio top rietuvės 1-2
taip, kad jei dabar mes pridėti Kitas elementas jis bus
eiti į masyvo vietos numeris du.
>> Dabar susiję sąrašai kitą būdas įgyvendinti kaminai.
Ir jei tai apibrėžimo ekranas čia atrodo pažįstamas,
tai todėl, kad jis atrodo beveik lygiai taip pat,, iš tikrųjų,
tai gana daug yra tiksliai toks pat, kaip pavieniui susietą sąrašo,
Jei prisimenate iš mūsų diskusija atskirai susijęs sąrašus kitoje vaizdo.
Vienintelis apribojimas čia yra mums, programuotojams,
mes neleidžiama įterpti ar ištrinti atsitiktinai
iš pavieniui susietą sąrašą kuriuos mes anksčiau galėjo daryti.
Mes tik dabar galite įterpti ir pašalinti iš priekinis arba susietą viršų
sąrašas.
Tai tikrai tik Skirtumas nors.
Tai kitaip atskirai susijusi sąrašas.
Tai tik apribojimas pakeisti savyje
programuotojais, kad keičia jį į rietuvę.
>> Taisyklė čia yra visada išlaikyti žymiklį į susietą sąrašą galvos.
Tai, žinoma, visuotinai svarbi taisyklė pirmas.
Dėl pavieniui susiję sąrašą vistiek tik reikia žymiklį į galvą
siekiant turėti, kad grandinės galėtų kreiptis
kiekvienam kito elemento susijusioje sąrašą.
Bet tai ypač svarbus kamino.
Ir taip paprastai esate vyksta iš tikrųjų nori
Ši rodyklė būti pasaulio kintamasis.
Tai tikriausiai bus dar lengviau, kad taip.
Taigi, kas yra push ir pop analogai?
Teisė.
Taigi stumia vėl pridedant naujas elementas prie kamino.
Be susietą sąrašą, kad reiškia, kad mes ketiname turėti
sukurti naują mazgą, kad mes ketiname pridėti į susietą sąrašą
ir vykdykite veiksmus atidžiai kad mes sukūrėme anksčiau
į vieną, susijusių sąrašus įtraukti jį į grandinė nesulaužant grandinę
ir prarasti arba orphaning bet elementai iš susietų sąrašą.
Ir tai iš esmės, ką tai mažai BLOB teksto ten apibendrina.
Ir tegul pažvelgti ne tai, kaip schemoje.
>> Taigi čia mūsų susijusi sąrašas.
Tai kartu yra keturi elementai.
Ir dar puikiai Štai mūsų kamino, kuriame yra keturi elementai.
Ir tarkim dabar mes norime stumti naują elementą į šį steką.
Ir mes norime stumti nauja daiktai, kurių duomenys vertė yra 12.
Na, ką mes ketiname daryti?
Na pirmiausia mes ketiname malloc erdvė, dinamiškai
skirti vietos naują mazge.
Ir, žinoma, iš karto po mes paskambinti malloc mes visada
įsitikinkite, kad patikrinti for null, nes jei mes turime null Atgal
ten buvo keletas problema rūšiuoti.
Mes nenorime, kad dereference to null Rodyklė arba jūs kenčia SEG gedimą.
Tai nėra gerai.
Taigi mes malloced mazgas.
Tarkime, mes turėjo sėkmę čia.
Mes ketiname įdėti į 12 duomenys laukas tos mazgas.
Dabar jūs prisiminti, kuris iš mūsų patarimų juda kitas todėl mes negalime nutraukti grandinę?
Mes turime keletą galimybių, bet čia tik viena, kad ketina būti saugus
yra nustatyti naujienas šalia Rodyklė taškas senosios galvos sąrašo
ar kas greičiau bus senas vadovas sąrašo.
Ir dabar, kad visi mūsų elementai yra grandinės kartu,
mes galime tiesiog perkelti sąrašą atkreipti į tą pačią vietą, kad naujos daro.
Ir mes dabar efektyviai stumti naujas elementas ant iš kamino priekyje.
>> Pop Mes tik norime ištrinti tą pirmąjį elementą.
Ir todėl iš esmės ką mes turime padaryti čia
Na mes turime rasti antrą elementą.
Kad ilgainiui taps nauja galvą, kai mes ištrinti pirmasis.
Taigi mes tiesiog reikia pradėti nuo pradžia, perkelti vieną į priekį.
Kai mes turime griebtis dėl vieno Persiųsti kur mes šiuo metu
mes galime ištrinti pirmasis saugiai ir tada mes galime tiesiog perkelti galvą
atkreipti dėmesį į tai, kas buvo antroji kadencija, o tada dabar
yra pirmasis, kad po to, kai mazgas buvo ištrintas.
>> Taigi dar kartą, atsižvelgiant išvaizdą ne tai, kaip schemoje mes
noriu dabar pop elementas išjungti šio kamino.
Taigi, ką mes galime padaryti?
Na mes pirmą kartą ketina sukurti naujas žymeklis, kad vyksta
iki punkto pačioje vietoje kaip ir galvos.
Mes ketiname perkelti jį vieną poziciją Persiųsti sakydamas Trav dydžiu neprilygstami
Trav šalia kurios, pavyzdžiui, būtų iš anksto į Trav rodyklę vieną
pozicija į priekį.
Dabar, mes turime turėti ant pirmojo elemento
per rodykle vadinamas, sąrašą ir Antrasis elementas per žymeklis vadinamas
Trav, mes galime saugiai ištrinti, kad Pirmasis elementas iš kamino
neprarasdamas likusios grandinės, nes mes
turi būdą, kaip perduoti prie antrojo elemento
perduoti būdu iš žymeklis vadinamas Trav.
>> Taigi, dabar mes galime išlaisvinti tą mazgą.
Galime nemokamai sąrašą.
Ir tada viskas, ką reikia padaryti dabar judėti sąrašą taško į tą pačią vietą
kad Trav daro, ir mes tarsi atgal kur mes pradėjome prieš mums stumiama 12
ant į pirmąją vietą, į dešinę.
Tai yra būtent tai, kur buvome.
Mes turėjome šį keturių elementų kamino.
Mes pridėjo penktadalį.
Mes stumti penktadalį elementas, ir tada mes
popped, kad pastaruoju įtraukta elementą atgal išjungti.
>> Tai tikrai gana daug visi yra kaminai.
Galite jas įgyvendinti, kaip matricos.
Galite jas įgyvendinti kaip susijusios sąrašus.
Yra, žinoma, kita būdų, kaip jas įgyvendinti, taip pat.
Iš esmės todėl mes būtų naudoti rietuvės yra išlaikyti duomenis tokiu būdu,
kad neseniai pridėta elementas yra pirmas dalykas, kurį mes
norės grįžti.
Aš Doug Lloyd, tai CS50.