Structuri de date și algoritmi în Pascal
Cozi, stive, liste legate și copaci
Programele constau în algoritmi și structuri de date. programe bune să profite de ambele dintre ele. Selecția și dezvoltarea structurii de date este la fel de importantă ca și dezvoltarea unor proceduri care le manipuleaza. organizarea de informații și metode de acces este de obicei determinată de natura problemei cu care se confruntă programator. Prin urmare, fiecare programator trebuie să aibă în „bagaj“ dumneavoastră metode adecvate de prezentare și de recuperare a datelor, care pot fi aplicate în orice situație dată.
De fapt, structura de date în computer se bazează pe tipurile de date de bază, cum ar fi „char“, „întreg“, „real“. La nivelul următor sunt matrice, care sunt seturi de tipuri de date de bază. Apoi, există înregistrări, care sunt grupuri de tipuri de date, care sunt accesate de către unul dintre date, iar la ultimul nivel, atunci când aceasta nu abordează aspectele fizice de prezentare a datelor, se atrage atenția asupra ordinea în care datele sunt stocate și le face căutate. În esență, datele fizice asociate cu „datele mașinii“, care controlează modul de acces la informații în programul. Există patru astfel de „mașini“:
- loc;
- stiva;
- Lista legată;
- arbore binar.
Fiecare metodă utilizată pentru a rezolva o anumită clasă de probleme. Fiecare metodă este, în esență, un fel de „dispozitiv“, care oferă informații predeterminate la o metodă specifică de stocare și, la cerere, efectuează anumite operațiuni de recuperare a datelor. Fiecare dintre aceste metode utilizează două operații: adăugați un element și pentru a găsi elementul / element este înțeleasă ca o anumită unitate de informație /.
Coada este o listă liniară a datelor care pot fi accesate de principiul „primul venit, primul“ / prescurtat, uneori, așa cum se numește metoda / acces FIFO. Un element care a fost pus în aplicare, va fi primul obținut în căutare. Element din coada de așteptare în al doilea rând, o căutare va fi obținut ca al doilea, etc. Această metodă este singura în formularea elementelor din coadă și atunci când caută elemente în coadă. coadă de aplicare nu permite accesul direct la orice element particular.
În viața de zi cu zi, există adesea cozi. De exemplu, coada de la banca sau la toate cantinele cu un serviciu rapid este o coadă, în sensul de mai sus / cu excepția cazurilor în care o persoană încearcă să obțină serviciu din rândul său! /. Pentru a înțelege mai bine coada de locuri de muncă, ia în considerare două proceduri: și eșalonare de recuperare din coadă. Când procesul de setare pentru elementul de coadă este plasat în coada. Atunci când procedura de eșantionare dintr-o coadă a primului element de îndepărtat, care este rezultatul acestei proceduri. Coada de lucru este ilustrat în figura 1. Trebuie amintit că eșantionul din coada de ea elimină într-adevăr un element. În cazul în care acest element este nicăieri pentru a fi salvat, aceasta nu poate fi efectuată mai târziu pentru a accesa.
Fig.1. coadă de locuri de muncă: 1 - eșalonare; 2 - un eșantion de elemente de coadă A, B, C.
Cozile în programare sunt utilizate în multe cazuri, de exemplu atunci când modelarea (discutat mai jos în capitolul corespunzător), activitatea de planificare (metoda PERT sau grafica Gatta) cu tampon de intrare-ieșire.
Ca un exemplu, ia în considerare un simplu program de regulamente de planificare, care permite accesul la o serie de reglementări. De fiecare dată când accesați o rețetă eliminată din listă și afișează următoarea rețetă. Pentru simplificare, programul utilizează o serie de șiruri de caractere pentru a controla evenimente. Descriere prescripție este limitat la 80 de caractere și numărul de prescriptii nu trebuie să depășească 100. În primul rând, ar trebui prevăzută acest program de planificare pentru procedura de stabilire în coada de așteptare și procedura de eșantionare coadă. Aceste proceduri sunt prezentate mai jos și sunt date variabile globale și tipuri de date necesare.
Funcționarea acestor funcții utilizează trei variabile globale: „SPOS“, care conține indicele următorul element liber; „Rpos“, care conține indexul următorului element de selectabilă și „evenimentul“, care este o matrice de șiruri de caractere care descriu cerințe. Variabile „SPOS“ și „rpos“ ar trebui să fie setat la zero, înainte de primul apel la procedurile de selecție și eșalonare coadă.
În acest program procedura de setare la rândul său, pune noul eveniment în sfârșitul listei și face controale popula lista. din funcția de eșantionare coadă selectează evenimentele din coadă după cum este necesar pentru a le manipula. Atunci când un nou eveniment este planificat, „SPOS“ variabila este incrementat cu unu, iar când se termină evenimentului, incrementat „rpos“ variabila. De fapt, variabila „rpos“ urmărește „SPOS“ variabilă pe rând trece. Acest proces este ilustrat în figura 2. În cazul în care valoarea indicatorului spațiu liber coincide cu valoarea indicelui a elementului selectat, înseamnă că nici un eveniment în coadă. Trebuie amintit faptul că, deși elementul funcție de eșantionare a cozii nu încalcă de fapt informația în coada de așteptare, un al doilea acces la aceasta nu este posibil, și, de fapt, dispare.
Mai jos este întregul program este la fel de simplu ca și reglementările de planificare. Puteți îmbunătăți acest program pe cont propriu.
loc ciclic
2 - indicatorul de comunicare;
1, primul element nou
1 Ștergerea primul element
6 Ștergerea unui element Mijlociu
7 Ștergerea ultimul element
Liste ale dublei legături
1 Inserling un nou element Primul
1 Ștergerea primul element
6 Ștergerea unui element Mijlociu
7 Ștergerea ultimul element
Figura 9. Ștergerea unui element din listă, cu o dublă legătură: 1 - îndepărtarea primului element; 2 - câmpurile de informații; 3 - lista din stânga este convertit la dreapta; 4 - element de la distanță; 5 - indicare Tel cu o valoare zero; 6 - îndepărtarea elementului de mijloc; 7 - eliminarea ultimul element.
Mai jos este o funcție care șterge o „adresă“ tip de element din lista dublei legături:
Această funcție este trecut un pointer la una mai mică decât pentru funcția corespunzătoare utilizând lista de link-ul de unul. / Element de la distanță are deja un pointer la elementul anterior, și un pointer la elementul următor /. Ca primul element din listă se poate modifica, funcția returnează un pointer la partea de sus a listei.
Mai jos este un simplu program de la o listă de corespondență de e-mail, care a fost construit în lista cu o legătură dublă. Aici, întreaga listă este conținută în memoria RAM. Cu toate acestea, programul poate fi modificat pentru a stoca lista discului.
arbore binar
Această secțiune examinează a patra structură de date care se numește un arbore binar. Există mai multe tipuri de copaci. Cu toate acestea, arbori binari ocupă o poziție specială. Dacă astfel de arbori regulariza, operația de căutare, introducerea și retragerea se va efectua foarte repede. Fiecare element are un binar câmpuri de date copac, comunicarea cu membrul din stânga și un element de legătură dreapta. Figura 10 prezintă un arbore mic.
Descriind copaci speciale terminologia folosită. Primul element din arborele se numește rădăcina ei. Fiecare element este numit nod / sau frunze / copac, iar copacul se numește subramificație. Top care are subarbori este numit un nod terminal de. Înălțimea arborelui este egal cu numărul de vârfuri de niveluri în copac. Mai mult, în acest copac poate fi considerat că acestea sunt aranjate în memorie cât și pe suport de hârtie. Cu toate acestea, amintiți-vă că copacii sunt o modalitate de prezentare a datelor în memorie, iar memoria are de fapt o formă liniară.