Koristimo sve naprednije programske jezike koji nam omogućuju pisanje manje koda i postizanje odličnih rezultata. Moraš platiti za ovo. Kako se sve rjeđe bavimo stvarima niske razine, normalno je da mnogi od nas ne razumiju baš što su hrpa i hrpa, kako kompilacija zapravo funkcionira, koja je razlika između statičkog i dinamičkog tipkanja itd. Ne kažem da svi programeri ne znaju za te koncepte - samo mislim da se ponekad isplati vratiti se takvim starim stvarima.
Danas ćemo govoriti samo o jednoj temi: hrpi i gomili. I stog i gomila odnose se na različite lokacije na kojima se odvija upravljanje memorijom, ali strategija za ovo upravljanje je radikalno drugačija.
Stog
Stog je područje RAM-a koje se stvara za svaku nit. Radi prema LIFO (Last In, First Out) redoslijedu, što znači da će posljednji komad memorije gurnut na stog biti prvi u redu koji će biti izbačen sa stoga. Svaki put kada funkcija deklarira novu varijablu, ona se dodaje na stog, a kada ta varijabla izađe iz opsega (na primjer, kada funkcija završi), automatski se uklanja sa stoga. Kada se varijabla steka oslobodi, to područje memorije postaje dostupno za druge varijable steka.
Zbog ove prirode hrpe, upravljanje memorijom je vrlo logično i jednostavno za CPU; ovo rezultira velikom brzinom, posebno zato što je vrijeme ciklusa ažuriranja bajta stoga vrlo kratko, tj. ovaj bajt je najvjerojatnije vezan za predmemoriju procesora. Međutim, postoje i nedostaci ovog strogog oblika upravljanja. Veličina stoga je fiksna vrijednost, a prekoračenje ograničenja memorije dodijeljenog stogu rezultirat će prekoračenjem stoga. Veličina se postavlja kada se stream kreira, a svaka varijabla ima maksimalnu veličinu ovisno o tipu podataka. To vam omogućuje da ograničite veličinu nekih varijabli (kao što su cijeli brojevi) i prisiljava vas da deklarirate veličinu složenijih tipova podataka (kao što su nizovi) unaprijed, budući da im stog neće dopustiti da je promijene. Osim toga, varijable koje se nalaze na stogu uvijek su lokalne.
U konačnici, stog vam omogućuje da upravljate memorijom na najučinkovitiji način - ali ako trebate koristiti dinamičke strukture podataka ili globalne varijable, trebali biste pogledati hrpu.
Hrpa
Hrpa je spremište memorije, također smješteno u RAM-u, koje omogućuje dinamičku dodjelu memorije i ne funkcionira kao stog: to je samo skladište za vaše varijable. Kada dodijelite dio memorije na gomili za pohranjivanje varijable, može joj se pristupiti ne samo u niti, već u cijeloj aplikaciji. Ovako se definiraju globalne varijable. Kada se aplikacija prekine, oslobađa se sva dodijeljena memorija. Veličina hrpe se postavlja kada se aplikacija pokrene, ali je, za razliku od stoga, samo fizički ograničena, a to vam omogućuje stvaranje dinamičkih varijabli.
S hrpom komunicirate putem referenci, koje se obično nazivaju pokazivači - to su varijable čije su vrijednosti adrese drugih varijabli. Kada kreirate pokazivač, pokazujete na memorijsku lokaciju na gomili, koja postavlja početnu vrijednost varijable i govori programu gdje da pristupi toj vrijednosti. Zbog dinamičke prirode hrpe, CPU ne sudjeluje u njenoj kontroli; U jezicima bez skupljača smeća (C, C++), programer mora ručno osloboditi područja memorije koja više nisu potrebna. Ako se to ne učini, može doći do curenja memorije i fragmentacije, što će značajno usporiti hrpu.
U usporedbi sa stogom, hrpa je sporija jer su varijable razbacane po memoriji umjesto da stoje na vrhu stoga. Neispravno upravljanje memorijom u gomili dovodi do usporavanja njezina rada; međutim, to ne umanjuje njegovu važnost - ako trebate raditi s dinamičkim ili globalnim varijablama, koristite gomilu.
IBM je napravio dramatičnu pogrešku ne osiguravši hardversku implementaciju stoga. Ova serija sadržavala je mnoga druga neuspješna rješenja, ali je, nažalost, kopirana u Sovjetskom Savezu pod imenom ES EVM (Unified Series), a svi njezini vlastiti razvoji su obustavljeni. Ovo je sovjetsku industriju vratilo mnogo godina unatrag u razvoju računala.Red
Red čekanja kao podatkovna struktura razumljiva je i osobama neupućenim u programiranje. Red sadrži elemente, kao da su poredani jedan za drugim u lancu. Red čekanja ima početak i kraj. Nove elemente možete dodati samo na kraj reda; elemente možete uzeti samo od početka. Za razliku od običnog reda čekanja, koji se po želji uvijek može napustiti, elementi se ne mogu brisati iz sredine programerovog reda čekanja.
Red se može zamisliti kao cijev. Možete dodati kuglice - elemente reda - na jedan kraj cijevi, a one se uklanjaju s drugog kraja. Elementi u sredini reda, tj. kuglice unutar cijevi su nedostupne. Kraj cijevi u koji se dodaju kuglice odgovara kraju reda, kraj s kojeg se vade odgovara početku reda. Dakle, krajevi cijevi nisu simetrični; kuglice unutar cijevi se kreću samo u jednom smjeru.
U načelu, mogli bismo dopustiti dodavanje elemenata na oba kraja reda i uzimanje s oba kraja. Takva struktura podataka postoji iu programiranju, naziv joj je “dec”, od engleskog. Dvostruki red čekanja, tj. red s dva kraja. Dec se koristi puno rjeđe nego red.
Korištenje reda u programiranju gotovo je identično njegovoj ulozi u svakodnevnom životu. Red čekanja je gotovo uvijek povezan sa zahtjevima za servisiranje u slučajevima kada se oni ne mogu odmah izvršiti. Red čekanja također održava redoslijed kojim se zahtjevi poslužuju. Razmotrite, na primjer, što se događa kada osoba pritisne tipku na tipkovnici računala. Dakle, osoba traži od računala da izvrši neku radnju. Na primjer, ako jednostavno upisuje tekst, radnja bi se trebala sastojati od dodavanja jednog znaka tekstu i može biti popraćena ponovnim crtanjem područja zaslona, pomicanjem prozora, preoblikovanjem odlomka itd.
Svaki, čak i najjednostavniji, operativni sustav uvijek je multitasking u jednoj ili drugoj mjeri. To znači da u trenutku pritiska tipke operativni sustav može biti zauzet nekim drugim poslom. Međutim, operativni sustav nema pravo ignorirati pritisak tipke u bilo kojoj situaciji. Stoga se rad računala prekida, ono pamti svoje stanje i prelazi na obradu pritisaka tipki. Ova obrada treba biti vrlo kratka kako ne bi ometala druge zadatke. Naredba izdana pritiskom tipke jednostavno se dodaje na kraj reda zahtjeva koji čekaju na izvršenje. Nakon toga prekid prestaje, računalo se vraća u stanje i nastavlja rad koji je prekinut pritiskom na tipku. Zahtjev u redu čekanja neće biti izvršen odmah, već tek kada dođe na red.
U sustavu Windows rad aplikacija s prozorima temelji se na porukama koje se šalju tim aplikacijama. Na primjer, postoje poruke o pritisku tipke miša, o zatvaranju prozora, o potrebi ponovnog crtanja područja prozora, o odabiru stavke izbornika itd. Svaki program ima red zahtjeva. Kada program primi svoj vremenski odsječak izvršenja, odabire sljedeći zahtjev s početka reda čekanja i izvršava ga. Dakle, rad prozorske aplikacije sastoji se, jednostavno rečeno, od sekvencijalnog izvršavanja zahtjeva iz njenog reda čekanja. Red čekanja održava operativni sustav.
Pristup programiranju koji se ne sastoji od izravnih poziva procedura, već od slanja poruka koje se u njih ubacuju red zahtjeva, ima mnoge prednosti i jedna je od značajki objektno orijentiranog programiranja. Tako, primjerice, ako se prozorski program iz nekog razloga treba ugasiti, bolje je ne pozivati odmah naredbu za isključivanje, što je opasno jer narušava logiku rada i može dovesti do gubitka podataka. Umjesto toga, program sam sebi šalje poruku da se isključi, koja će biti poslana red zahtjeva i izvršavaju se nakon ranije primljenih zahtjeva.
Implementacija reda čekanja temeljena na nizu
Kao što je već rečeno, programeru se odozgo daje niz, na temelju kojeg se trebaju implementirati sve ostale podatkovne strukture. Naravno, takva implementacija može biti višestupanjska, a niz ne djeluje uvijek kao neposredna baza implementacije. U slučaju reda čekanja, dvije najpopularnije implementacije su ona temeljena na kontinuiranom nizu, koja se također naziva implementacija temeljena na međuspremniku prstena, i referentna implementacija ili implementacija na temelju popisa. Referentne implementacije bit će riječi u nastavku.
Kod implementacije kontinuiranog reda čekanja, baza je niz fiksne duljine N, tako da je red ograničen i ne može sadržavati više od N elemenata. Indeksi elemenata niza kreću se od 0 do N-1. Osim niza, implementacija reda čekanja pohranjuje tri jednostavne varijable: indeks početka reda čekanja, indeks kraja reda čekanja i broj elemenata reda čekanja. Elementi reda sadržani su u segmentu niza od početnog indeksa do krajnjeg indeksa.
Prilikom dodavanja novog elementa na kraj reda, završni indeks se prvo povećava za jedan, zatim se novi element upisuje u ćeliju niza s tim indeksom. Slično, prilikom dohvaćanja elementa iz glave reda, sadržaj ćelije niza s indeksom glave reda pohranjuje se kao rezultat operacije, a zatim se indeks glave reda povećava za jedan. I početni i završni indeks reda čekanja pomiču se slijeva nadesno tijekom rada. Što se događa kada indeks kraja čekanja dosegne kraj niza, tj. N - 1?
Ključna ideja implementacije reda je da je niz mentalno uvezan u prsten. Smatra se da iza zadnjeg elementa niza slijedi njegov prvi element (podsjetimo se da posljednji element ima indeks N - 1, a prvi ima indeks 0). Kada se indeks kraja reda pomiče udesno, u slučaju da pokazuje na posljednji element niza, pomiče se na prvi element. Dakle, kontinuirani segment niza koji zauzimaju elementi reda može ići kroz kraj niza do njegovog početka.
Stog
Stog je najpopularnija i možda najvažnija struktura podataka u programiranju. Stog je uređaj za pohranu iz kojeg se elementi uklanjaju obrnutim redoslijedom od njihovog dodavanja. To je poput nepravilnog reda u kojem je prvi uslužen onaj koji je zadnji došao u red. U literaturi o programiranju općenito su prihvaćene kratice za označavanje discipline reda i stoga. Disciplina čekanja označena je kao FIFO, što znači prvi ušao prvi izašao. Disciplina slaganja označena je kao LIFO, posljednji ušao prvi izašao (Last In First Out).
Stog se može zamisliti kao cijev s dnom s oprugom, smještena okomito. Gornji kraj cijevi je otvoren, mogu se dodavati elementi, ili, kako se kaže, uguravati u njega. Uobičajeni engleski izrazi u tom pogledu vrlo su šareni; operacija dodavanja elementa u hrpu označava se kao push, što se prevodi kao "guranje, guranje". Novi element koji se dodaje gura elemente koji su prethodno postavljeni na hrpu jednu poziciju prema dolje. Kada se elementi iskaču iz hrpe, oni se guraju prema gore, na engleskom pop (“pucaj”).
Primjer hrpe bio bi plast sijena, hrpa papira na stolu, hrpa tanjura itd. Odatle dolazi naziv stack, što na engleskom znači hrpa. Ploče se uklanjaju iz hrpe obrnutim redoslijedom od dodavanja. Dostupna je samo gornja ploča, tj. tanjur na vrhu hrpe. Dobar primjer bi također bila željeznička slijepa ulica u kojoj se mogu slagati automobili.
Korištenje stoga u programiranju
Stog se koristi prilično često iu raznim situacijama. Ujedinjuje ih sljedeći cilj: trebate spremiti neki posao koji još nije dovršen, ako se trebate prebaciti na drugi zadatak. Stog se koristi za privremeno pohranjivanje stanja zadatka koji još nije dovršen. Nakon spremanja stanja računalo prelazi na drugi zadatak. Po završetku njegovog izvršenja, stanje odgođenog zadatka se vraća sa stoga, a računalo nastavlja prekinuti rad.
Zašto se stog koristi za spremanje stanja prekinutog posla? Pretpostavimo da računalo izvršava zadatak A. U procesu njegove provedbe javlja se potreba za dovršetkom zadatka B. Stanje zadatka A se pamti i računalo prelazi na izvršavanje zadatka B. Ali čak i kada izvršava zadatak B, računalo se može prebaciti na drugi zadatak C i morat će spremiti stanje zadatka B prije nego što prijeđe na C. Kasnije, nakon završetka C, prvo će se vratiti stanje zadatka B, zatim će se, nakon završetka B, vratiti stanje zadatka A. Dakle, restauracija se odvija obrnutim redoslijedom od spremanja, što odgovara disciplini hrpe.
Stog vam omogućuje organiziranje rekurzije, tj. potprogram poziva sam sebe, bilo izravno ili kroz lanac drugih poziva. Na primjer, neka rutina A izvrši algoritam koji ovisi o ulaznom parametru X i eventualno o stanju globalnih podataka. Za najjednostavnije vrijednosti X, algoritam se implementira izravno. Za složenije vrijednosti X, algoritam se implementira kao redukcija na primjenu istog algoritma za jednostavnije vrijednosti X. U ovom slučaju, potprogram A referira sam na sebe, prosljeđujući jednostavniju vrijednost X kao parametar. Ovim pristupom prethodna vrijednost parametra X, kao i sve lokalne varijable potprograma A, pohranjuju se na stog. Zatim se kreira novi skup lokalnih varijabli i varijabla koja sadrži novu (jednostavniju) vrijednost parametra X. Pozvana podrutina A radi na novom skupu varijabli bez uništavanja prethodnog skupa. Na kraju poziva, stari skup lokalnih varijabli i staro stanje ulaznog parametra X vraćaju se iz stoga, a rutina nastavlja tamo gdje je stala.
Zapravo, ne morate čak ni spremati vrijednosti lokalnih varijabli potprograma na stog na poseban način. Činjenica je da lokalne varijable potprograma (tj. njegove interne, operativne varijable, koji se stvaraju na početku njegovog izvođenja i uništavaju na kraju) postavljaju se na stog, implementiran u hardver temeljen na običnom RAM-u. Na samom početku svog rada potprogram grabi prostor na stogu za svoje lokalne varijable; ovo područje memorije u hardverskom stogu obično se naziva blok lokalne varijable ili na engleskom okvir("okvir"). U trenutku završetka rada, potprogram oslobađa memoriju uklanjanjem bloka svojih lokalnih varijabli sa stoga.
Uz lokalne varijable, povratne adrese za pozive potprograma pohranjene su na hardverskom stogu. Neka potprogram bude pozvan u nekom trenutku u programu A B. Prije nego što se pozove potprogram B, adresa instrukcije koja slijedi nakon instrukcije koja poziva B pohranjuje se na stog. Ovo je tzv Povratna adresa na program A. Kada završi s izvođenjem, podrutina B izbacuje povratnu adresu programa A iz stoga i vraća kontrolu na tu adresu. Dakle, računalo nastavlja izvršavati program A, počevši od instrukcije koja slijedi nakon instrukcije poziva. Većina procesora ima posebne instrukcije koje podržavaju pozivanje potprograma tako da prvo gurnu povratnu adresu na stog i vrate se iz potprograma na adresu izvađenu sa stoga. Obično se naredba poziva zove poziv, naredba povratka se zove povratak.
Parametri potprograma ili funkcije također se guraju na stog prije nego što se pozove. Redoslijed kojim su postavljeni na stog ovisi o konvencijama jezika visoke razine. Dakle, u jeziku C ili C++, prvi argument funkcije je na vrhu stoga, drugi je ispod njega, i tako dalje. U Pascalu je obrnuto: zadnji argument funkcije je na vrhu stoga. (Ovo je razlog zašto su, usput, funkcije s promjenjivim brojem argumenata, kao što je printf, moguće u C-u, ali ne i u Pascalu.)
U Fortran-4, jednom od najstarijih i najuspješnijih programskih jezika, argumenti se propuštaju kroz posebno memorijsko područje, koje se ne mora nalaziti na stogu, budući da su do kraja 70-ih godina 20. stoljeća još uvijek postojala računala poput IBM 360 ili ES računala bez sklopa implementacije hardvera. Povratne adrese također nisu bile pohranjene na stogu, već u memorijskim ćelijama fiksiranim za svaku podrutinu. Programeri takvu memoriju nazivaju statičkom u smislu da statičke varijable uvijek zauzimaju isto mjesto u memoriji u bilo koje vrijeme tijekom izvođenja programa. Kada se koristi samo statička memorija, rekurzija nije moguća jer se prethodne vrijednosti lokalnih varijabli uništavaju kada se napravi novi poziv. Referentni Fortran 4 koristio je samo statičke varijable, a rekurzija je bila zabranjena. Do sada se jezik Fortran široko koristi u znanstvenim i inženjerskim izračunima, međutim, moderni standard Fortran-90 već uvodi memoriju stogova, uklanjajući nedostatke ranijih verzija jezika.
Implementacija stoga temeljena na nizu
Implementacija stoga temeljena na nizu je klasik programiranja. Ponekad čak ni sam koncept hrpe nije potpuno ispravno identificiran s ovom implementacijom.
Osnova implementacije je niz veličine N, čime se implementira hrpa ograničene veličine, čija najveća dubina ne može premašiti N. Indeksi ćelija niza kreću se od 0 do N-1. Elementi steka pohranjuju se u nizu na sljedeći način: element na dnu niza nalazi se na početku niza, tj. u ćeliji s indeksom 0. Element iznad najnižeg elementa snopa pohranjuje se u ćeliju s indeksom 1, i tako dalje. Vrh hrpe je pohranjen negdje u sredini niza. Indeks elementa na vrhu stoga pohranjuje se u posebnu varijablu koja se obično naziva pokazivač N - 1 . Elementi niza zauzimaju kontinuirani dio niza, počevši od ćelije čiji je indeks pohranjen u pokazivaču niza i završava s posljednjom ćelijom niza. U ovoj opciji stog raste u smjeru pada indeksa. Ako je stog prazan, tada pokazivač stoga sadrži vrijednost N (koja je za jedan veća od indeksa zadnje ćelije u nizu).
Poštovani, student sam druge godine tehničkog sveučilišta. Nakon što sam iz zdravstvenih razloga propustio nekoliko satova programiranja, suočio sam se s nedostatkom razumijevanja tema kao što su Stack i Queue. Metodom pokušaja i pogrešaka, nakon nekoliko dana, konačno mi je sinulo što je to i s čime se jede. Kako vam razumijevanje ne bi oduzelo toliko vremena, u ovom ću članku govoriti o tome što je "skup", kako sam i uz koje primjere shvatio što je to. Ako vam se sviđa, napisat ću drugi dio, koji će se dotaknuti koncepta kao što je "Red"
Teorija
Na Wikipediji definicija hrpe glasi:
Stog (engleski stack - hrpa; čitaj hrpa) je apstraktni tip podataka, koji je popis elemenata organiziranih po LIFO principu (engleski last in - first out, “last in - first out”).
Prilično potpuna definicija, ali možda malo teška za razumijevanje početnicima.
Stoga, prva stvar na koju bih se želio usredotočiti je predstavljanje hrpe u obliku stvari iz života. Prvo tumačenje koje mi je palo na pamet bilo je u obliku hrpe knjiga, gdje je gornja knjiga vrh.
Zapravo, hrpa se može prikazati kao hrpa bilo kojih predmeta, bilo da se radi o hrpi listova, bilježnica, košulja itd., ali mislim da će primjer s knjigama biti najoptimalniji.
Dakle, od čega se sastoji stog?
Stog se sastoji od ćelija (u primjeru su to knjige), koje su predstavljene kao struktura koja sadrži neke podatke i pokazivač na vrstu te strukture na sljedeći element.
teško? Nema problema, idemo shvatiti.
Ova slika shematski prikazuje hrpu. Blok obrasca “Data/*next” je naša ćelija. *next, kao što vidimo, pokazuje na sljedeći element, drugim riječima, pokazivač *next pohranjuje adresu sljedeće ćelije. Pokazivač *TOP pokazuje na vrh steka, odnosno pohranjuje svoju adresu.
Završili smo s teorijom, idemo na praksu.
Praksa
Prvo moramo stvoriti strukturu koja će biti naša "stanica"
C++ kod
struct comp ( //Struktura nazvana comp (od riječi komponenta) int Podaci; //Neki podaci (mogu biti bilo koji, na primjer možete napisati int ključ; char Podaci; možete dodati i neke druge podatke) comp *next;/ /Comp tip pokazivač na sljedeći element);
Početnicima možda neće biti jasno zašto je naš pokazivač tipa comp, točnije, pokazivač tipa strukture comp. Dopustite mi da objasnim, kako bi pokazivač *next pohranio comp strukturu, treba naznačiti tip ove strukture. Drugim riječima, označite što će pokazivač pohraniti.
Nakon što smo postavili "Cell", prijeđimo na stvaranje funkcija.
Funkcije
Funkcija stvaranja "Snopa"/dodavanja elementa u "Snop"
Prilikom dodavanja elementa, imat ćemo dvije situacije:
- Stog je prazan i potrebno ga je kreirati
- Stog već postoji i samo mu trebate dodati novi element
C++ kod
void s_push(comp **top, int D) ( //funkcija tipa void (ne vraća ništa) koja uzima pokazivač na vrh steka i varijablu koja će biti zapisana u ćeliju comp *q; //Kreiraj novi pokazivač q tipa strukture comp. By U biti, ovo je naš novi element q = new comp(); //dodijelimo memoriju za novi element q->Data = D; //Upiši traženi broj u Data element if (vrh == NULL) ( //Ako nema vrha, tj. hrpa je prazna *vrh = q; //vrh hrpe bit će novi element) else //ako hrpa nije prazno ( q->next = *top; //Povlačimo vezu od novog elementa do vrha. To jest, stavljamo knjigu na vrh hrpe. *top = q; //Označavamo da je vrh sada novi element ))
Pogledajmo to malo detaljnije.
Prvo, zašto funkcija prihvaća **top, odnosno pokazivač na pokazivač, da bi vam bilo jasnije, ostavljam razmatranje ovog pitanja za kasnije. Drugo, razgovarajmo detaljnije o q->sljedeći = *vrh i o tome što to znači ->
.
-> znači da, grubo govoreći, ulazimo u našu strukturu i iz nje izvlačimo element te strukture. U redu q->sljedeći = *vrh Uzimamo pokazivač na sljedeći element *next iz naše ćelije i zamijenimo ga pokazivačem koji pokazuje na vrh stoga *top. Drugim riječima, uspostavljamo vezu od novog elementa do vrha steka. Ovdje nema ništa komplicirano, sve je kao s knjigama. Novu knjigu postavljamo točno na vrh hrpe, odnosno povlačimo vezu od nove knjige do vrha hrpe knjiga. Nakon toga, nova knjiga automatski postaje vrh, budući da hrpa nije hrpa knjiga, moramo naznačiti da je novi element vrh, za to pišemo: *vrh = q;.
Funkcija za uklanjanje elementa iz "Skupa" na temelju podataka
Ova funkcija će ukloniti element sa steka ako je broj podataka ćelije (q->Data) jednak broju koji ćemo sami odrediti.
Mogu postojati sljedeće opcije:
- Ćelija koju trebamo ukloniti je vrh hrpe
- Ćelija koju trebamo obrisati je na kraju, odnosno između dvije ćelije
C++ kod
void s_delete_key(comp **top, int N) (//funkcija koja uzima top top i broj za brisanje comp *q = *top; //stvori pokazivač tipa comp i izjednači (stavi) ga na vrh stack comp *prev = NULL;//kreiramo pokazivač na prethodni element, od početka će biti prazan while (q != NULL) (//dok pokazivač q nije prazan, izvršit ćemo kod u petlji, ako je još uvijek prazna petlja završava if (q-> Data == N) (//ako je Data elementa jednak broju koji trebamo ukloniti if (q == *top) ( //ako je takav pokazivač jednak vrhu, tada postoji element koji trebamo ukloniti - vrh *top = q- >next;//pomakni vrh na sljedeći element free(q);//očisti ćelija q->Data = NULL; //Dalje, kako bismo izbjegli pogreške, vraćamo varijable u udaljenoj ćeliji na nulu, budući da u nekim kompajlerima udaljena ćelija ima vrijednosti varijabli koje nisu NULL, ali doslovno "Čitanje memorije je nemoguće" ili brojevi "-2738568384" ili drugi, ovisno o kompajleru. q->next = NULL; ) else//ako je element posljednji ili je između dva druga elementa ( prev->next = q ->next;// Nacrtajte vezu od prethodnog elementa do sljedećeg free(q);//očistite ćeliju q->Data = NULL;//nulirajte varijable q->next = NULL; ) ) // ako Data elementa NIJE jednak broju koji trebamo ukloniti prev = q; //zapamti trenutnu ćeliju kao prethodnu q = q->sljedeća;//pomakni pokazivač q na sljedeći element ) )
Pokazivač q u ovom slučaju igra istu ulogu kao i pokazivač u bilježnici; kreće se kroz cijeli stog dok ne postane jednak NULL( dok (q != NULL)), drugim riječima, dok se stog ne potroši.
Da bismo bolje razumjeli uklanjanje elementa, povucimo analogiju s već poznatim hrpom knjiga. Ako trebamo maknuti knjigu odozgo, maknemo je, a knjiga ispod nje postaje gornja. Ovdje je isto, samo na početku moramo odrediti da će sljedeći element postati vrh *vrh = q->sljedeći; pa tek onda izbrisati element slobodan (q);
Ako je knjiga koju treba ukloniti između dvije knjige ili između knjige i stola, prethodna knjiga će pasti na sljedeću ili na stol. Kao što smo već shvatili, naša knjiga je ćelija, a tablica se ispostavlja kao NULL, odnosno nema sljedećeg elementa. Ispada isto kao i kod knjiga, označavamo da će prethodna ćelija biti povezana sa sljedećom prethodni->sljedeći = q->sljedeći;, vrijedi napomenuti da prethodna->sljedeća može biti jednako ćeliji ili nuli, ako q->sljedeće = NULL, odnosno nema ćelije (knjiga će ležati na stolu), nakon toga čistimo ćeliju besplatno (q).
Također je vrijedno napomenuti da ako se ova veza ne uspostavi, dio ćelija koji se nalazi nakon izbrisane ćelije postat će nedostupan, budući da će se sama veza koja povezuje jednu ćeliju s drugom izgubiti i ovaj odjeljak jednostavno biti izgubljen u memoriji
Funkcija prikaza hrpe
Najjednostavnija funkcija:
C++ kod
void s_print(comp *top) ( //prihvaća pokazivač na vrh stoga comp *q = top; //postavi q na vrh while (q) ( //sve dok q nije prazan (while(q) ) je ekvivalentno while(q != NULL )) printf_s("%i", q->Data);//prikaži podatke ćelije stoga q = q->next;//nakon prikaza, premjesti q na sljedeći element (ćelija) ) )
Ovdje mislim da je sve jasno, samo želim reći da q treba shvatiti kao klizač, on prolazi kroz sve ćelije od vrha gdje smo ga postavili na početku: *q = vrh;, do posljednjeg elementa.
Glavna funkcija
U redu, zapisali smo glavne funkcije za rad sa stogom i pozovite ih.
Pogledajmo kod:
C++ kod
void main() ( comp *top = NULL; //na početku programa nemamo red, dakle nema vrha, dajemo mu vrijednost NULL //Sljedeće počinjemo zbrajati brojeve od 1 do 5 u naš stog s_push(&top, 1); s_push (&top, 2); s_push(&top, 3); s_push(&top, 4); s_push(&top, 5); //nakon izvršavanja funkcija na stogu imat ćemo 54321 s_print(top);//ispis s_delete_key(&top, 4); //Tada brišemo 4, stog dobiva 5321 printf_s("\n");//prevedi s_print(top) u novi red;//sustav ispisa ("pauza");//pauza)
Vratimo se na ono zašto smo proslijedili pokazivač na pokazivač vrha na funkciju. Činjenica je da kada bismo u funkciju uveli samo pokazivač na vrh, onda bi se “Stop” kreirao i mijenjao samo unutar funkcije; u glavnoj funkciji vrh bi bio i ostao NULL. Prenošenjem pokazivača na pokazivač mijenjamo vrh *top u glavnoj funkciji. Ispada da ako funkcija mijenja stog, morate joj proslijediti vrh s pokazivačem na pokazivač, kao što smo učinili u funkciji s_push, s_delete_key. U funkciji s_print, “Stack” se ne bi trebao mijenjati, tako da jednostavno prolazimo pokazivačem na vrh.
Umjesto brojeva 1,2,3,4,5 možete koristiti i varijable tipa int.
Zaključak
Cijeli programski kod:
C++ kod
#uključi
Rezultat izvršenja
Budući da se elementi stalno dodaju na vrh hrpe, elementi će biti prikazani obrnutim redoslijedom.
Zaključno, želio bih vam zahvaliti na vremenu koje ste posvetili mom članku, stvarno se nadam da je ovaj materijal pomogao nekim programerima početnicima da shvate što je "Stog", kako ga koristiti, au budućnosti više neće imati problema. Napišite svoje mišljenje u komentarima, kao i kako mogu poboljšati svoje članke u budućnosti. Hvala vam na pažnji.
Oznake: Stog, stog u C-u, implementacija stoga, stog na nizu, dinamički rastući stog, stog na jednostruko povezanom sustavu
Stog
C stack je vjerojatno najjednostavnija struktura podataka koju ćemo stalno proučavati i koristiti. Stog je podatkovna struktura u kojoj elementi podržavaju LIFO ("Last in - first out") princip: zadnji ušao, prvi izašao. Ili prvi ušao, zadnji izašao.
Stog vam omogućuje pohranu elemenata i obično podržava dvije osnovne operacije:
- GURNUTI– stavlja element na vrh hrpe
- POP– uklanja element s vrha hrpe, pomičući vrh na sljedeći element
Također je uobičajena operacija PEEK, koja dobiva element na vrhu stoga, ali ga ne uklanja od tamo.
Stog je jedna od osnovnih struktura podataka i koristi se ne samo u programiranju, već iu dizajnu sklopova, jednostavno u proizvodnji, za provedbu tehnoloških procesa itd.; Stog se koristi kao pomoćna struktura podataka u mnogim algoritmima i drugim složenijim strukturama.
Neka, na primjer, imamo hrpu brojeva. Pokrenimo nekoliko naredbi. U početku je stog prazan. Vrh stoga je pokazivač na prvi element, ne pokazuje nigdje. U slučaju C, može biti jednako NULL.
Stog se sada sastoji od jednog elementa, broja 3. Vrh hrpe pokazuje na broj 3.
Stog se sastoji od dva elementa, 5 i 3, s vrhom hrpe koji pokazuje na 5.
Skup se sastoji od tri elementa, vrh niza pokazuje na 7.
Vratit će vrijednost 7, ostavljajući na stogu 5 i 3. Vrh će pokazivati na sljedeći element – 5.
Vraća 5, ostavljajući samo jedan element na stogu, 3, na koji će pokazivati vrh stoga.
Vraća 3, stog će biti prazan.
Hrpa se često uspoređuje s hrpom tanjura. Da biste dobili sljedeću ploču, morate ukloniti prethodne. Vrh hrpe je vrh hrpe tanjura.
Kada radimo sa stogom, moguće su dvije glavne i uobičajene pogreške:
- 1. Stack Underflow: Pokušaj izbacivanja elementa iz praznog niza
- 2. Stack Overflow: Pokušavate staviti novi element na stog koji više ne može rasti (na primjer, nema dovoljno RAM-a)
Implementacija softvera
Pogledajmo tri jednostavne implementacije snopa:
Stog fiksne veličine izgrađen na nizu
Izrazita značajka je jednostavnost implementacije i maksimalna brzina izvršenja. Takav stog se može koristiti kada je njegova najveća veličina unaprijed poznata ili se zna da je mala.
Prvo određujemo maksimalnu veličinu polja i vrstu podataka koji će biti pohranjeni u njemu:
#define STACK_MAX_SIZE 20 typedef int T;
Sada sama struktura
Typedef struct Stack_tag ( T podaci; veličina_t veličina; ) Stack_t;
Ovdje je veličina varijable broj elemenata, a ujedno i pokazivač na vrh steka. Vrh će pokazivati na sljedeći element niza koji će sadržavati vrijednost.
Stavili smo novi element na stog.
Void push(Stack_t *stack, const T value) ( stack->data = value; stack->size++; )
Jedini je problem što možete ići izvan niza. Stoga uvijek trebate provjeriti da nema grešaka preljeva stoga:
#define STACK_OVERFLOW -100 #define STACK_UNDERFLOW -101 void push(Stack_t *stack, const T value) ( if (stack->size >= STACK_MAX_SIZE) ( exit(STACK_OVERFLOW); ) stack->data = value; stack- >veličina++ ;)
Slično tome, definirajmo Pop operaciju koja vraća element s vrha i prelazi na sljedeći
T pop(Stack_t *stack) ( if (stack->size == 0) ( exit(STACK_UNDERFLOW); ) stack->size--; return stack->data; )
I funkcija peek koja vraća trenutni element s vrha
T peek(const Stack_t *stack) ( if (stack->size<= 0) { exit(STACK_UNDERFLOW); } return stack->podaci; )
Još jedna važna napomena - nemamo funkciju stvaranja hrpa, tako da morate ručno resetirati vrijednost veličine
Pomoćne funkcije za ispis elemenata hrpe
Void printStackValue(const T value) ( printf("%d", value); ) void printStack(const Stack_t *stack, void (*printStackValue)(const T)) ( int i; int len = stack- >veličina - 1; printf("skup %d > ", snop->veličina); za (i = 0; i< len; i++) { printStackValue(stack->podaci[i]); printf(" | "); ) if (stack->size != 0) ( printStackValue(stack->data[i]); ) printf("\n"); )
Imajte na umu da u funkciji ispisa koristimo int umjesto size_t jer len može postati negativan. Funkcija prvo ispisuje veličinu hrpe, a zatim njegov sadržaj, odvajajući elemente s |
Ispitivanje
Stog_t stog; stack.size = 0; guranje(&slaganje, 3); printStack(&stack, printStackValue); guranje(&slaganje, 5); printStack(&stack, printStackValue); guranje(&slaganje, 7); printStack(&stack, printStackValue); printf("%d\n", pop(&stack)); printStack(&stack, printStackValue); printf("%d\n", pop(&stack)); printStack(&stack, printStackValue); printf("%d\n", pop(&stack)); printStack(&stack, printStackValue); _getch();
Razmotrimo i situacije u kojima postoje pogreške u korištenju. Donji protok
Void main() ( Stack_t stack; stack.size = 0; push(&stack, 3); pop(&stack); pop(&stack); _getch(); )
Void main() ( Stack_t stack; size_t i; stack.size = 0; for (i = 0; i< 100; i++) { push(&stack, i); } _getch(); }
Dinamički rastući stog na nizu
Dinamički rastući stog koristi se kada broj elemenata može biti značajan i nije poznat u trenutku rješavanja problema. Maksimalna veličina stoga može biti ograničena nekim brojem ili veličinom RAM-a.
Stog će se sastojati od pokazivača na podatke, veličine niza (maksimum) i broja elemenata u nizu. Ovaj broj će također označavati vrh.
Typedef struct Stack_tag ( T *data; size_t size; size_t top; ) Stack_t;
Prvo, trebat će vam početna veličina niza, neka bude 10
#define INIT_SIZE 10
Algoritam radi ovako: provjeravamo je li vrijednost vrha premašila vrijednost veličine. Ako je vrijednost premašena, povećavamo veličinu niza. Ovdje postoji nekoliko opcija za povećanje niza. Možete dodati broj, možete pomnožiti s nekom vrijednošću. Koja je opcija bolja ovisi o specifičnostima zadatka. U našem slučaju, veličinu ćemo pomnožiti s brojem MNOŽITELJ
#definiraj MNOŽITELJ 2
Nećemo postaviti maksimalnu veličinu. Program će se srušiti ako dođe do prekoračenja ili nedostatka stoga. Implementirat ćemo isto sučelje (pop, push, peek). Osim toga, budući da je niz dinamičan, napravit ćemo neke pomoćne funkcije za stvaranje stoga, brisanje i čišćenje.
Prvo, funkcije za stvaranje i brisanje hrpe i nekoliko pogrešaka
#define STACK_OVERFLOW -100 #define STACK_UNDERFLOW -101 #define OUT_OF_MEMORY -102 Stack_t* createStack() ( Stack_t *out = NULL; out = malloc(sizeof(Stack_t)); if (out == NULL) ( exit(OUT_OF_MEMORY); ) out->size = INIT_SIZE; out->data = malloc(out->size * sizeof(T)); if (out->data == NULL) ( free(out); exit(OUT_OF_MEMORY); ) out- >top = 0; return out; ) void deleteStack(Stack_t **stack) ( free((*stack)->data); free(*stack); *stack = NULL; )
Sve je vrlo jednostavno i jasno, nema trikova. Stvaramo hrpu početne duljine i poništavamo vrijednosti.
Sada napišimo pomoćnu funkciju za promjenu veličine.
Void resize(Stack_t *stack) ( stack->size *= MULTIPLIER; stack->data = realloc(stack->data, stack->size * sizeof(T)); if (stack->data == NULL) ( izlaz(STACK_OVERFLOW); ) )
Ovdje imajte na umu da ako nije bilo moguće dodijeliti dovoljno memorije, izaći će sa STACK_OVERFLOW.
Funkcija push provjerava jesmo li izašli izvan granica niza. Ako da, povećajte njegovu veličinu
Void push(Stack_t *stack, T value) ( if (stack->top >= stack->size) ( resize(stack); ) stack->data = value; stack->top++; )
Funkcije pop i peek slične su onima koje se koriste za niz fiksne veličine
T pop(Stack_t *stack) ( if (stack->top == 0) ( exit(STACK_UNDERFLOW); ) stack->top--; return stack->data; ) T peek(const Stack_t *stack) ( if ( stog->vrh<= 0) { exit(STACK_UNDERFLOW); } return stack->podaci; )
Provjerimo
Void main() ( int i; Stack_t *s = createStack(); for (i = 0; i< 300; i++) { push(s, i); } for (i = 0; i < 300; i++) { printf("%d ", peek(s)); printf("%d ", pop(s)); } deleteStack(&s); _getch(); }
Napišimo još jednu funkciju, implode, koja reducira niz na veličinu jednaku broju elemenata u nizu. Može se koristiti kada se već zna da više neće biti umetnuti elementi, a može se djelomično osloboditi memorija.
Void implode(Stack_t *stack) ( stack->size = stack->top; stack->data = realloc(stack->data, stack->size * sizeof(T)); )
Možemo koristiti u našem slučaju
Za (i = 0; i< 300; i++) { push(s, i); } implode(s); for (i = 0; i < 300; i++) { printf("%d ", peek(s)); printf("%d ", pop(s)); }
Ova jednonitna implementacija stoga koristi malo pristupa memoriji, prilično je jednostavna i opće namjene, radi brzo i može se implementirati, ako je potrebno, za nekoliko minuta. Od sada se uvijek koristi osim ako nije drugačije navedeno.
Ima nedostatak koji se odnosi na metodu povećanja potrošnje memorije. Kod množenja faktorom 2 (u našem slučaju) potrebno je nekoliko pristupa memoriji, ali svako sljedeće povećanje može dovesti do greške, pogotovo ako je količina memorije u sustavu mala. Ako koristite nježniju metodu dodjele memorije (na primjer, dodavanje 10 svaki put), tada će se broj pristupa povećati, a brzina će pasti. Danas uglavnom nema problema s veličinom memorije, a upravitelji memorije i skupljači smeća (koji nisu u C-u) rade brzo, pa prevladavaju agresivne promjene (primjerice, implementacija cijele standardne biblioteke jezika Java).
Implementacija hrpe na jednostruko povezanoj listi
Što je jednostruko povezani popis? Ukratko: jednostruko povezani popis sastoji se od čvorova, od kojih svaki sadrži korisne informacije i vezu do sljedećeg čvora. Zadnji čvor se odnosi na NULL.
Nećemo imati nikakve maksimalne i minimalne veličine (iako ih u općem slučaju može biti). Svaki novi element stvara se iznova. Prvo, definirajmo strukturu čvora
#define STACK_OVERFLOW -100 #define STACK_UNDERFLOW -101 #define OUT_OF_MEMORY -102 typedef int T; typedef struct Node_tag ( T vrijednost; struct Node_tag *sljedeće; ) Node_t;
Funkcija umetanja prvog elementa je jednostavna: stvorite novi čvor. Sljedeći pokazivač bacamo na stari čvor. Zatim prenosimo pokazivač na vrh stoga na novostvoreni čvor. Vrh hrpe sada pokazuje na novi čvor.
Void push(Node_t **head, T value) ( Node_t *tmp = malloc(sizeof(Node_t)); if (tmp == NULL) ( exit(STACK_OVERFLOW); ) tmp->next = *head; tmp- >vrijednost = vrijednost; *glava = tmp; )
Funkcija pop uzima prvi element (onaj na koji pokazuje vrh), baca pokazivač na sljedeći element i vraća prvi. Ovdje postoje dvije opcije - možete vratiti čvor ili vrijednost. Ako vratimo vrijednost, morat ćemo izbrisati čvor unutar funkcije
Node_t* pop1(Node_t **head) ( Node_t *out; if ((*head) == NULL) ( exit(STACK_UNDERFLOW); ) out = *head; *head = (*head)->next; return out; )
T pop2(Node_t **head) ( Node_t *out; T value; if (*head == NULL) ( exit(STACK_UNDERFLOW); ) out = *head; *head = (*head)->next; value = out ->vrijednost; besplatno(out); povratna vrijednost; )
Sada, umjesto provjere duljine niza, posvuda se koristi provjera jednakosti vrha stoga s NULL.
Jednostavna funkcija zavirivanja
T peek(const Node_t* head) ( if (head == NULL) ( exit(STACK_UNDERFLOW); ) return head->value; )
Iteracija je vrlo zanimljiva. Samo se krećemo od jednog čvora do drugog dok ne dođemo do kraja
Void printStack(const Node_t* head) ( printf("stack >"); while (head) ( printf("%d ", head->value); head = head->next; ) )
I još jedan problem - sada ne možete samo gledati veličinu hrpe. Treba ići od početka do kraja i prebrojati sve elemente. Na primjer, ovako
Size_t getSize(const Node_t *head) ( size_t size = 0; while (head) ( size++; head = head->next; ) return size; )
Naravno, možete odvojeno pohraniti veličinu, možete omotati hrpu sa svim podacima u drugu strukturu itd. Razmotrimo sve ovo kada detaljnije proučavamo popise.
zadnji ušao - prvi izašao, "zadnji ušao - prvi izašao").Najčešće se princip rada hrpe uspoređuje s hrpom ploča: da biste uzeli drugu s vrha, morate ukloniti gornju.
U nekim jezicima (na primjer, Lisp, Python), bilo koji popis može se nazvati stogom, budući da su za njih dostupne pop i push operacije. U C++ standardna biblioteka ima klasu s implementiranom strukturom i metodama. itd.
Enciklopedijski YouTube
1 / 3
Informatika. Strukture podataka: Stog. Foxfordov centar za online učenje
#9. Stog / 1. Asembler i procedure / Programiranje od nule
Osnove podatkovnih mreža. OSI model i TCP IP protokol stack. Osnove Etherneta.
titlovi
Softverski skup
Organizacija u memoriji
Često se stog implementira kao jednosmjerna lista (svaki element na listi sadrži, osim informacija pohranjenih u stogu, pokazivač na sljedeći element niza).
Ali stog se također često nalazi u jednodimenzionalnom nizu s uređenim adresama. Ova organizacija hrpe je prikladna ako informacijski element zauzima fiksni broj riječi u memoriji, na primjer, 1 riječ. Time se eliminira potreba za pohranjivanjem eksplicitnog pokazivača na sljedeći element niza u elementu niza, što štedi memoriju. U ovom slučaju, pokazivač steka ( Pokazivač snopa, - SP) obično je registar procesora i pokazuje na adresu glave steka.
Na primjer, pretpostavimo da se glava steka nalazi na nižoj adresi, sljedeći elementi nalaze se na rastućim adresama. Svaki put kada se riječ gurne na stog, SP se prvo smanji za 1, a zatim se adresa iz SP-a zapisuje u memoriju. Svaki put kada se riječ izbaci iz stoga, ona prvo čita trenutnu adresu iz SP-a, a zatim povećava sadržaj SP-a za 1.
Kada se stog organizira kao jednosmjerna lista, vrijednost varijable steka je pokazivač na njegov vrh - adresu vrha. Ako je stog prazan, tada je vrijednost pokazivača NULL.
Primjer implementacije stoga u C-u:
struct stack (char * data; struct stack * next;);
Operacije snopa
Postoje tri moguće operacije na stogu: dodavanje elementa (tj. guranje), uklanjanje elementa (pop) i čitanje elementa glave (peek).
Prilikom guranja (guranja) dodaje se novi element, koji pokazuje na element koji je prethodno bio glava. Novi element sada postaje glavni element.
Prilikom brisanja elementa (pop), prvi se uklanja, a glavni postaje onaj na koji je ovaj objekt imao pokazivač (sljedeći element). U tom slučaju vraća se vrijednost uklonjenog elementa.
void push (STACK * ps, int x) // Dodavanje novog elementa u stog( if ( ps -> size == STACKSIZE ) // Je li stog prepun?( fputs ( "Pogreška: stack overflow \n ", stderr); abort (); ) else ( ps -> items [ ps -> size ++ ] = x ; ) ) int pop ( STACK * ps ) // Ukloni sa stoga(ako (ps -> veličina == 0) // Je li stog prazan?( fputs ( "Pogreška: stack underflow \n ", stderr); abort (); ) else ( return ps -> items [ -- ps -> size ]; ) )
Područje primjene
Programski prikaz hrpe koristi se za prelaženje podatkovnih struktura, poput stabla ili grafikona. Kod korištenja rekurzivnih funkcija također će se koristiti stog, ali u hardverskom obliku. Osim u ove svrhe, stog se koristi za organiziranje
Slični se procesi događaju tijekom hardverskog prekida (procesor X86 automatski sprema registar zastavica na stog tijekom hardverskog prekida). Osim toga, prevoditelji postavljaju lokalne varijable procedure na stog (ako procesor ima pristup nasumičnim lokacijama stoga).
Prije korištenja stog mora biti inicijaliziran tako da SS:ESP registri pokazuju na adresu glave stoga u području fizičkog RAM-a, a potreban broj memorijskih ćelija mora biti rezerviran za pohranu podataka na stog (očito, stog u ROM-u, naravno, ne može biti organiziran). Aplikacijski programi, u pravilu, od operacijskog sustava dobivaju snop spreman za korištenje. U zaštićenom načinu rada procesora, segment stanja zadatka sadrži četiri selektora segmenta stoga (za različite razine privilegija), ali se istovremeno koristi samo jedan stog.
