Funcție Gol: Boolean;
Dacă I = 0 atunci Goliți: = Altfel Necunoscut: = Fals;
Când efectuați o operație selectată din stivă, mai întâi trebuie să testați spațiul gol al stivei. Dacă este goală, atunci Empty returnează True. Dacă Empty returns False, înseamnă că stiva nu este goală și încă puteți selecta elemente din ea.
Procedură StackTop (var I: Integer; S: Stack);
2.4.2 Coadă
Conceptul de coadă este bine cunoscut de toată lumea din viața de zi cu zi. Elementele coadajului în cazul general sunt comenzi pentru un anumit serviciu.
În programare, există o structură de date numită coadă. Această structură de date este utilizată, de exemplu, pentru a simula cozile reale pentru a determina caracteristicile acestora în temeiul prezentei legi de primire a ordinelor și disciplina serviciului lor. În esența sa, coada este o structură semi-statică - în timp și lungimea coadă, iar compoziția poate varia.
La rândul său, ris.privedena cuprinde patru elemente - A, B, C și D. Element A este localizat la începutul cozii și elementul D - la sfârșitul anului. Elementele pot fi șterse numai de la începutul coadajului, adică primul element plasat în coadă este șters mai întâi. Din acest motiv, totul este adesea numit o listă, organizată în conformitate cu principiul „primul găzduit primul eliminat“, spre deosebire de principiul organizației stivă - „ultimul loc primul este îndepărtat“
Disciplina de serviciu, în care ordinea primită în coadă este selectată mai întâi pentru întreținere (și scoasă din coadă), numită FIFO (First In First Out). Coada de așteptare este deschisă pe ambele părți.
Astfel, eliminarea componentelor apare de la începutul coadajului și intrarea până la capăt. În acest caz, introduceți două indicatoare: una - la începutul coadajului, a doua - la sfârșit.
Locul real este creat în memoria calculatorului, sub forma unui tablou unidimensional cu un număr finit de elemente, în acest caz, trebuie să specificați tipul de elemente pe rând, și ai nevoie de o variabilă în coada de așteptare de lucru.
Din punct de vedere fizic, coada ocupă o zonă solidă de memorie, iar elementele se urmează unul pe altul, ca într-o listă secvențială.
Operațiile efectuate pe coadă:
Trei operații primitive sunt definite pentru coadă. Operația insert (q, x) plasează elementul x la sfârșitul coadă q. Operația de eliminare (q) elimină elementul de la începutul coadă q și își atribuie valoarea variabilei x. A treia operație, goală (q), returnează true sau false, în funcție de situația în care coada de date este goală sau nu. În plus. Dat fiind faptul că o coadă semi-statică este implementată într-o matrice unidimensională, este necesar să se monitorizeze posibilitatea de depășire a acesteia. În acest scop, este introdusă opțiunea completă (q).
Operația de inserare poate fi întotdeauna executată, deoarece nu există restricții asupra numărului de elemente pe care o coadă poate conține. Operația de eliminare, cu toate acestea, se aplică numai unei coadouri care nu este goală, deoarece nu puteți elimina un element dintr-o coadă care nu conține elemente. Rezultatul unei încercări de a șterge un articol dintr-o coadă goală este apariția unei excepții, pierderea semnificației. Operația goală, desigur, este întotdeauna posibilă.
Un exemplu de implementare a unei coadă sub formă de matrice unidimensională în Pascal:
Cache = Array [1..MaxQ] de E;
Eliminăm elementele A și B din coadă.
Din păcate, cu o astfel de reprezentare a cozii poate experimenta o situație absurdă în care coada este goală, dar noua celulă nu poate găzdui în ea (ia în considerare succesiunea operațiilor de mutare și inserție, rezultând într-o astfel de situație). Este clar că implementarea unei coadă cu o matrice este inacceptabilă.
O soluție la problema care apare este modificarea operației de eliminare astfel încât atunci când următorul element este șters, întreaga coadă este mutată la începutul matricei. Operația de îndepărtare (q) poate fi implementată în acest caz după cum urmează.
Variabila F nu mai este necesară, deoarece primul element al matricei este întotdeauna începutul coadajului. O coadă goală este reprezentată de o coadă pentru care valoarea lui R este zero.
Cu toate acestea, această metodă este foarte neproductivă. Fiecare ștergere necesită mutarea tuturor elementelor rămase în coadă. Dacă coada conține 500 sau 1000 de elemente, atunci este evident că acesta este un mod foarte ineficient. Mai mult, operația de înlăturare a unui element din coadă coincide logic cu manipularea unui singur element, adică cu cel care se află la începutul coadă. Punerea în aplicare a acestei operațiuni ar trebui să reflecte acest fapt, fără a face multe acțiuni suplimentare.
O altă modalitate este de a considera o matrice care conține o coadă sub forma unui inel închis, mai degrabă decât o secvență liniară având un început și un sfârșit. Aceasta înseamnă că primul element al coada de așteptare urmează imediat după ultima. Aceasta înseamnă că, chiar dacă ultimul element este ocupat, noua valoare poate fi plasată imediat după aceea în locul primului element dacă primul element este gol.
Organizarea unei linii de apel.
Să luăm în considerare un exemplu. Să presupunem că coada conține trei elemente - în pozițiile 3, 4 și 5 ale matricei cu cinci elemente. Acest caz, arătat în Fig. 2.17. Deși matricea nu este plină, ultimul element al coadă este ocupat.
Dacă se face o încercare de a plasa elementul G în coadă, acesta va fi scris în prima poziție a matricei, așa cum se arată în Fig. 2.17. Primul element al coadă este Q (3), urmat de elementele Q (4), Q (5) și Q (l).
Din nefericire, la o asemenea reprezentare este destul de dificil să se definească, când turnul este gol. Condiția R O modalitate de a rezolva această problemă este de a introduce un acord în care valoarea lui F este indicele elementului matricei care precedă imediat primul element al cozii. și nu indicele primului element. În acest caz, deoarece R conține indicele ultimului element al coadă, condiția F = R implică faptul că coada este goală. Rețineți că, înainte de o coadă de lucru, F și R în setul de ultima valoare index de matrice în loc de 0 și 1, deoarece în această reprezentare ultima coadă element de matrice imediată, dar precede primul element. Deoarece R = F, coada este inițial goală. Operații de bază cu o coadă de inel: 1. Introduceți elementul q în coada x. 2. Extrageți un element din coada x. 3. Verificați coada pentru gol. 19. Cum este organizată coada de așteptare? 20. Care este caracteristica punților? Până în prezent am considerat doar obiecte software statice. Cu toate acestea, utilizarea obiectelor statice numai în timpul programării poate provoca anumite dificultăți, în special în ceea ce privește obținerea unui program eficient al mașinii. Faptul este că uneori nu știm în avans nu numai dimensiunea valorii unui anumit obiect software, ci și dacă acesta va exista sau nu. Astfel de obiecte de program care apar deja în timpul executării unui program sau ale căror dimensiuni de valori sunt determinate în timpul execuției programului se numesc obiecte dinamice. Structurile de date dinamice au 2 caracteristici: 1) Numărul elementelor din structură nu este determinat în avans. 2) Elementele structurilor dinamice nu au o ordonare liniară rigidă. Ele pot fi împrăștiate din memorie. Pentru a lega elementele structurilor dinamice între ele, elementele elementelor în plus față de câmpurile de informație includ câmpuri de pointer (Figura 3.1) (legături cu alte elemente ale structurii). Cele mai comune structuri dinamice sunt listele legate. Din punct de vedere al reprezentării logice, se disting listele liniare și neliniar. Liniile liniare includ listele pur și simplu conectate și dublu. Pentru conectarea neliniară - înmulțită. Un element de listă este, în general, un câmp de înregistrare și unul sau mai mulți indicatori. Elementul unei liste pur și simplu conectate conține două câmpuri (Figura 3.2): câmpul de informații (INFO) și câmpul indicator (PTR). Accesul la elementul listei este numai de la început, adică nu există feedback în această listă. Lista inelară simplă conectată este obținută din lista obișnuită pur și simplu conectată prin atribuirea indicelui ultimului element al listei la valoarea indexului de la începutul listei (figura 3.3). Cele mai simple operații efectuate pe listele pur și simplu conectate 1) Introducerea unei liste pur și simplu conectate la început. Trebuie să introduceți un element cu câmpul de informații D în începutul unei liste simple conectate. Pentru a face acest lucru, trebuie să generați un element gol (P = GetNode). câmpul informațional al celulei pentru a atribui o valoare D (INFO (P) = D), o valoare pointer pentru acest element pentru a atribui un pointer la începutul listei (Ptr (P) = Lst), valoarea listei de start pointer pentru a atribui valoarea indicatorului P (Lst = P). Implementarea în Pascal: Introduceți la început 2) Scoateți un element de la începutul unei liste pur și simplu conectate. Este necesar să ștergeți primul element al listei, dar rețineți informațiile conținute în câmpul Info al acestui element. Pentru aceasta, introduceți indicatorul P, care va indica elementul șters (P = Lst). În variabila X, introduceți valoarea câmpului Info al elementului șters (X = Info (P)). Valoarea indicatorului la începutul listei este atribuită valorii indicatorului de lângă elementul care urmează să fie șters (Lst = Ptr (P)). Ștergeți elementul (FreeNode (P)). Implementarea în Pascal: Ștergerea de la început Utilizarea listelor unidirecționale în rezolvarea mai multor probleme poate provoca anumite dificultăți. Faptul este că, în conformitate cu lista unidirecțională, se poate deplasa într-o singură direcție, de la legătura de titlu cu ultimul link al listei. Între timp, este adesea necesar să se efectueze o anumită prelucrare a elementelor care preced elementul cu proprietatea dată. Cu toate acestea, după ce a constatat elementul cu această proprietate a unei liste legate, nu putem obține destul de un acces convenabil și rapid la elementul anterior - pentru a atinge acest obiectiv trebuie să complice algoritmul, care este incomod și nepractice. O listă dublu legată se caracterizează prin faptul că orice element are două indicatoare. Unul indică elementul anterior (invers), celălalt indică elementul următor (linia) (Figura 3.4). De fapt, o listă dublu conectată este o listă pur și simplu conectată cu aceleași elemente scrise în ordine inversă. Operațiuni pe liste duble conectate: - creați un element de listă; - căutați un element din listă; - introducerea unui element în locația specificată din listă; - eliminați articolul specificat din listă. Orice listă pur și simplu conectată poate fi văzută ca o stivă. Cu toate acestea, lista în comparație cu stiva sub formă de matrice unidimensională are avantajul, deoarece mărimea acesteia nu este setată în avans. Operațiuni stivuite care se aplică listelor 1). Pentru a adăuga un element în teanc, este necesar ca algoritmul să înlocuiască pointerul Lst cu indicatorul Stack (operația Push (S, X)). 2) Verificarea stivei de goluri (gol (S)) Dacă Stack = Nil, atunci Print "Stack este gol" 3) Selectarea unui element din stivă (POP (S)) Pentru a face o mai bună utilizare a memoriei computerului (pentru a evita risipa. Ie elemente neutilizate) cu listele sale pentru a crea o listă gratuit care are același format ca și cel al câmpului listei de funcții. Dacă listele de funcții au un format diferit, atunci trebuie să creați o listă gratuită a fiecărei liste funcționale. Numărul de articole din lista liberă ar trebui să fie determinat de sarcina pe care programul o rezolvă. De obicei, în memoria aparatului este creată o listă liberă ca o stivă. Crearea (GetNode) a noului element este echivalentă cu selectarea elementului liber stivă, iar funcția FreeNode adaugă elementul eliberat la stivă liberă. Să presupunem că trebuie să creăm o listă goală după tipul de stivă (Figura 3.6) cu indicatorul de start al listei - AVAIL. Vom dezvolta proceduri care ne permit să creăm un element de listă liber și să eliberăm un articol din listă. Vom dezvolta o procedură care va crea un element de listă goală cu pointerul P. Pentru a pune în aplicare operațiunile necesare GetNode generat elementul indicator atribuie o valoare de listă indicatorul liber și indicatorul de pornire pentru a trece la elementul următor. Înainte de a face acest lucru, trebuie să verificați dacă există elemente din listă. Lista goală gol (Avail = Nil) este echivalentă cu depășirea unei liste funcționale. Dacă Avail = Nil, atunci opțiunea Print "Overflow" Stop Când elementul Nod (P) este eliberat din lista de funcții prin operația FreeNode (P), acesta este introdus în lista liberă. Operațiile standard de returnare a unui element listă liber într-un grup de elemente libere nu dau întotdeauna efect dacă sunt utilizate liste neliniare multilaterale. Prima metodă de reciclare este metoda contoarelor. Un câmp de contor este introdus în fiecare element al listei conectate multiplu, care numără numărul de linkuri către acest element. Atunci când contorul elementului este în stare zero și câmpurile indicator ale elementului sunt în stare nulă, acest element poate fi returnat în grupul de elemente libere. A doua metodă este metoda de colectare a gunoiului (metoda de marcare). Dacă un element este legat, elementul de câmp de un bit (marcator) este setat la „1“, în caz contrar - „0“. Prin componentele de semnal de preaplin sunt căutate pentru care token-ul este setat la zero, adică. E. inclus programul de colectare a gunoiului, care scanează întreaga memorie și alocate pentru a reveni la lista liberă a elementelor de toate elementele care nu sunt marcate marcator. Este necesar să inserați un element X în matricea existentă între 5 și 6 elemente. Pentru a efectua această operație în matrice, trebuie să "omiteți" toate elementele, începând cu X6 - pentru a crește indicii lor cu unul. Ca urmare a introducerii, obținem următoarea matrice (Fig.3.7, 3.8): Această procedură poate dura foarte mult timp. În schimb, în lista legată, operația de inserare constă în modificarea valorii celor doi indicatori și generarea unui element liber. Timpul necesar pentru efectuarea acestei operațiuni este constant și nu depinde de numărul de articole din listă. Definiți elementul, după care trebuie să introduceți elementul în listă. Introducerea este efectuată utilizând procedura InsAfter (Q, X), iar ștergerea este DelAfter (Q, X). În acest caz, indicatorul de lucru P indică elementul, după care este necesar să inserați sau să ștergeți (figura 29). Să fie necesar să introduceți un element nou cu câmpul de informații X după elementul indicat de indicatorul de lucru P. 1) Trebuie să generați un element nou. 2) În câmpul de informații al acestui element trebuie să i se atribuie valoarea X. 3) Introduceți elementul primit. Aceasta este procedura InsAfter (Q, X). Să fie necesar să ștergeți elementul de listă care urmează după elementul indicat de indicatorul de lucru P. 1) Atribuiți valoarea Q a indicatorului elementului care trebuie șters. 2) În variabila X vom stoca valoarea câmpului de informații al elementului care trebuie șters. 3) Modificați valoarea indicatorului la elementul care trebuie șters de valoarea indicelui la elementul următor și efectuați ștergerea. Aceasta este procedura DelAfter (P, X). În limba Pascal, procedurile de mai sus vor arăta astfel: procedură InsAfter (var Q: PNode; X: Integer); procedura DelAfter (var Q: PNode; var X: Integer); Fie P pointerul de lucru, la începutul procedurii P = Lst. De asemenea, introducem Q pointer, în spatele căreia un element al P. Când indicatorul P va membru, acesta din urmă va fi îndepărtat relativ Q pointer ca un element ulterior. În timp ce P <> Nil nu Dacă Info (P) = 4 atunci Se afișează o ordine ordonată în ordine crescătoare. Trebuie să introduceți un element cu valoarea X din această listă, fără a încălca ordinea listei. Fie X = 16. Condiția inițială este Q = Nil, P = Lst. Introducerea elementului trebuie să aibă loc între elementele a treia și a patra (figura 3.10). În timp ce (P <> Nil) și (X> Info (P)) Pentru a crea o listă cu un antet, în partea de sus a listei se introduce un element suplimentar, care poate conține informații despre listă (Figura 3.11). O variabilă dinamică care conține numărul de elemente din listă (care nu numără antetul însuși) este adesea plasată în antetul listei. Dacă lista este goală, rămâne doar antetul listei (a se vedea Figura 3.12). Este, de asemenea, convenabil să introduceți valoarea indicatorului de sfârșit de listă în câmpul cu informații despre antet. Apoi, dacă lista este folosită ca o coadă, atunci Fr = Lst și Re = Info (Lst). Datorită volumului mare, acest material este plasat pe mai multe pagini:
3.1 Liste legate
3.1.1 Liste unidimensionale
3.1.2 Lista inelului unicat
3.1.3 Lista dublu conectată
3.1.4 Inel dublu legat
3.2 Stive de implementare cu liste cu un singur link
3.3 Organizarea operațiunilor Getnode, Freenode și reciclarea elementelor eliberate
3.3.1 Operația GetNode
3.3.2 Funcționarea FreeNode
3.3.3 Eliminarea elementelor libere în listele multiplicate
3.4 Lista unidimensională, ca o structură de date independentă
3.4.1 Introducerea și extragerea articolelor din listă
3.4.2 Exemple de operații tipice pe liste
3.4.3 Elemente ale titlurilor în liste
1 2 3 4 5 6 7 8
Articole similare
Trimiteți-le prietenilor: