Acum, să analizăm punerea în aplicare a unei coadă bazată pe o matrice. Ca și înainte, pentru simplitate, utilizați tabela TList. Cel puțin în acest caz, nu trebuie să ne facem griji cu privire la alocarea memoriei și la mărirea dimensiunii matricei.
Știind cum să pună în aplicare toate bazate pe lista legată, prima dorință poate fi pentru a simula operațiunile Puneți în coadă, adăugați elemente la instanța de capăt TList matrice folosind metoda Add, pentru a simula îndepărtarea de la linia - pentru a elimina primul element printr-o metodă Ștergeți metoda ( sau invers, inserați la începutul matricei și ștergeți-o din final). Cu toate acestea, să vedem ce se întâmplă cu matricea. Când metoda de adăugare este executată, nu se întâmplă nimic interesant, cu excepția cazurilor în care trebuie să măriți dimensiunea matricei. Aceasta este o operație a clasei O (l) - exact ceea ce este necesar. În ceea ce privește Ștergerea, totul nu este atât de neclar. Pentru punerea în aplicare a operațiunii pentru a elimina linia de matrice TList nevoie pentru a elimina primul element care va conduce la faptul că toate elementele de matrice va merge mai departe cu o poziție. O astfel de operație depinde de numărul de elemente din matrice, adică de aparține clasei 0 (n). Așa că au așteptat vestea proastă. Nu putem schimba operațiunile de coadă și coadă; Adăugăm doar în partea de sus a listei și ștergem de la sfârșit. Cu alte cuvinte, obținem încă o operație de clasa 0 (n) atunci când adăugăm la partea de sus a listei.
În unele surse, principiul descris este încă folosit pentru a implementa coada de așteptare. În plus, clasa TQueue din modulul Contnrs se poate baza pe acest principiu.
Figura 3.10. Folosind un matrice la coadă
Cum pot implementa o coadă bazată pe o matrice, astfel încât ambele operații de bază să aparțină clasei 0 (1)?
Soluția este de a utiliza o coadă de inel. Imaginați-vă o sală de așteptare la dentist. De obicei, aceasta este o cameră cu scaune de-a lungul pereților. Spre deosebire de coada de comandă din supermarket, unde ajungeți la partea de sus a coadă, împingând căruciorul, în sala de așteptare stați pe un scaun. Când sunați la următorul pacient, toți ceilalți nu se ridică și nu se mută la un scaun din apropiere. Doar începutul coada - un atribut greu de explicat (da, impresia că nu există cozi pentru dentist în America) - trece la o altă persoană. Când pacientul este chemat, acest atribut este transmis pacientului următor și devine "începutul" coadajului. Astfel, nimeni nu se ridică din scaune, doar într-un fel (posibil cu ajutorul unui asistent dentar) determină primul pacient din coadă. Acest tip de organizație se numește coadă circulară.
Pentru a implementa o coadă bazată pe array circulară, introducem o variabilă care va conține indexul primului element din coadă. În plus, introducem o altă variabilă care va indica sfârșitul coadajului. Începem cu o matrice cu un anumit număr de elemente (vom determina dimensiunea pe baza numărului maxim posibil de elemente din coadă) și vom seta indexul elementului inițial la indexul elementului finit. De fapt, această egalitate înseamnă că coada este goală.
Setarea unui element în coada de așteptare este echivalentă cu stabilirea valorii elementului indicat de indicele sfârșitului coadă, egal cu valoarea elementului scris în coadă. După aceasta, valoarea indicelui sfârșitului coadă ar trebui să fie mărită cu 1. Dacă după creșterea indexului depășește dimensiunea matricei, trebuie să fie setată la 0; indicele primului element.
Eliminarea unui element din coadă înseamnă returnarea valorii elementului indicat de indicele startului coadă. După aceasta, valoarea indexului de la începutul coadă crește cu 1. Dacă după creșterea indexului va depăși dimensiunea matricei, setați-o la 0. Evident, înainte de a elimina elementul din coadă, trebuie să vă asigurați că coada nu este goală. Pentru a face acest lucru, verificați dacă indicii începutului și sfârșitului coadă sunt egali (în cazul egalității indiciilor, coada este goală).
Și rămâne să luăm în considerare o altă problemă: atunci când plasați un element într-o coadă, trebuie să vă asigurați că noua valoare a indexului de sfârșit de coadă nu este egală cu valoarea indexului de la începutul coadă. Dacă egalitatea este respectată, atunci coada este complet umplută cu elemente. Din nefericire, această situație înseamnă, de asemenea (cel puțin pentru procedura de dequeu) că coada de așteptare este goală. Astfel, dacă se produce o astfel de situație destul de absurdă - o coadă goală este echivalentă cu cea completă - este necesar să se mărească dimensiunea matricei prin mutarea tuturor elementelor din matrice și modificarea valorilor indiciilor de start și de sfârșit ale coadă.
Interfața din clasa TtdArrayQueue arată exact ca interfața din clasa TtdQueue.
Listing 3.31. Clasa TtdArrayQueue
Constructorul și distrugătorul diferă foarte puțin de metodele corespunzătoare ale clasei TtdArrayStack.
Listing 3.32. Constructor și distrugător al clasei TtdArrayQueue
Cel mai interesant lucru se întâmplă în metodele lui Enqueue și Dequeue.
Listing 3.33. Metodele Enqueue și Dequeue din clasa TtdArrayQueue
După cum puteți vedea, un element din elementul de îndepărtare coadă include o revenire, care se află în poziție de index al cozii, și apoi creșterea indicelui de 1. Queuing include elementul de înregistrare la poziția de index sfârșitul cozii și creșterea indicelui de 1. În cazul în care coada ajunge la capătul de pornire sale , dimensiunea matricei este mărită folosind metoda aqGrow:
Listing 3.34. Extinderea dimensiunii de instanță a clasei TtdArrayQueue
Metoda de mai sus este cea mai complexă metodă din întreaga clasă. Atunci când este numit coada este plin, la sfârșitul indicelui coadă este egal cu indicele de început (nu uitați că acest lucru înseamnă, de asemenea, că coada este goală), necesitatea de a mări dimensiunea matrice TList. Primul lucru pe care îl facem este să mărim dimensiunea matricei cu 50%. După aceasta, trebuie să reparați coada de așteptare astfel încât să ia în considerare în mod corect spațiul liber. Dacă valoarea indicelui cozii este 0, linia inel nu a fost circulară, și tot ce trebuie să faceți - schimba valoarea de la sfârșitul indicelui coadă. Dacă valoarea indexului de început nu este egală cu 0, coada a fost "îndoită" în interiorul matricei. , Mutare în partea de sus a matrice și du-te la sfârșitul indicelui coadă (care este egală cu indicele coada) pentru a parcurge elementele în ordinea corectă, vom începe cu indicele de coadă, vom ajunge la sfârșitul șirului vechi. Acum avem elemente suplimentare care se află între capătul vechi și nou al matricei. Prin urmare, trebuie să plasăm elementele între începutul coadajului și vechiul capăt al matricei astfel încât să preia spațiul până la noul capăt al matricei. După aceasta, obținem ordinea corectă a elementelor din coada de așteptare.
Codul complet al clasei TtdArrayQueue poate fi găsit pe site-ul editorului, în secțiunea materiale. După descărcarea materialelor, găsiți fișierul TDStkQue.pas printre ele.
Algoritmi fundamentali și structuri de date în Delphi
Articole similare
Trimiteți-le prietenilor: