Stucturi de date
8.1 Noţiuni generale
Orice algoritm lucrează cu date (numere întregi, reale, şiruri de caractere etc.). Referitor la acestea, în informatică, s-au cristalizat anumite concepte fundamentale, pe care le vom prezenta în continuare.
Printr-un tip de dată înţelegem o mulţime cu elemente numite valori.
Exemplu:{-32768, 32767, …….0,1,……..32767} este omulţime de numere întregi. Atunci cînd nu există posibilatea de confuzie, putem nota mulţimea de mai sus astfel: [-32768,32767]. Un element al acestei mulţimi este 7 (valoarea 7). În Turbo Pascal un astfel de tip se numeşte integer. Şi este predefinit (este cunoscut de limbaj, nu trebuie definit de programator).
Pe mulţimea valorilor unui tip se definesc operaţiile asociate tipului.
Exemplu: Pentru tipul integer se definesc operaţiile de adunare, scădere, înmulţire etc.
Pentru fiecare tip se defineşte modul în care se valorile sale.
Exemplu: Pentru tipul integer valorile se memorizează utilizînd codul complementar şi se folosesc 2 octeţi consecutivi.
Pentru a lucra cu date de un anumit tip se folosesc variabile.
O variabilă se caracterizează prin: tip (natura datelor şi modul de memorare), nume (prin care aceasta se adresează) şi adresă (număr de ordine al primului octet în care se reţin datele, memoria internă fiind privită ca o succesiune de octeţi numerotaţi).
Tipuri de date pot fi simple (mulţimile care alcătuiesc nu sunt rezultate ca produs cartezian a altor mulţimi) şi stucturate în caz contrar. Exemplu:tipul integer este simplu, iar tipul record este structurat.
Limbajele de programare evoluate utilizează din plin tipurile de date. Mai mult, unele din ele permit programului, folosind tipurile existente, să definească noi tipuri de date. Limbajul Turbo Pascal este un exemplu în acest sens.
Noţiunea de tip de date este strânsă legată de un anumit limbaj de programare. În situaţia în care se renunţă la această legătură, se ajunge la o altă noţiune mult utilizată şi anume cea de structură de date.
Exemplu: Mulţimea este o structură de date (după cum vom arăta). În limbajul Turbo Pascal există tipul mulţime (set). Alte limbaje (de exemplu C) nu cunosc acest tip. Aceasta nu înseamnă că în C nu vom putea lucra cu mulţimi. Sarcina noastră este să înţelegem structura de date numită mulţime şi să o implementăm în orice limbaj de programare dorim.
Un curs de algoritmi trebuie să fie independenţi de orice limbaj. Fapt că în aceasta lucrare algoritmii se implementează în Turbo Pascal nu înseamnă că ei pot fi folosiţi numai în acest limbaj. Din acest motiv, orice curs de algoritmi va utiliza noţiunea de structură de date.
Structurile de date se clasifică în două mari categorii:statice şi dinamice.
Criteriul de clasificare este dat de modul de alocare a memoriei interne.
Astfel, pentru structurile statice memoria se alocă la începutul execuţiei programului şi rămăne alocată pînă cînd se încheie execuţia acestuia. Pentru structurile dinamice se alocă memorie în timpul execuţiei programului, iar cînd nu mai este necesară, memoria se eliberează.Modalitatea prin care se poate realiza aceasta în Turbo Pascal va fi arătată chiar în acest capitol.
8.1.1 Structuri statice
Aceste structuri ne sunt deja binecunoscute. În acest capitol le vom prezenta în mod sistematic şi, pe cît posibil, formalizat.
1) Tabloul
Fie Ani={1,2,….ni} mulţimea primelor ni numere naturale.
Fie M=An1 x An2 x…..x Ank produsul cartezian a k astfel de mulţimi.
Se numeşte tablou o funcţie f:M→T, unde T este o mulţime oarecare.
Numărul k este dimensiunea tabloului. Dacă k=1 tabloul se mai numeşte şi vector. Vectorul are n1 componente. Dacă k=2 tabloul se mai numeşte şi matrice. Matricea are n1xn2 elemente.
Atenţie! Frecvent se confundă numărul componentelor cu dimensiunea tabloului.
De exemplu, despre un vector cu n componente se spune că este de dimensiune n (cînd, de fapt, toţi vectorii au dimensiunea 1).
Majoritatea limbajelor de programare evoluate au implementat tipul tablou (array în Turbo Pascal). Pentru a identifica elementele unui tablou se folosesc indici (aceştia sunt elemente ale produsului cartezian pe care este definită funcţia).
2) Articolul
Fie A1, A2,….An n mulţimi finite. În general, natura elementelor acestor mulţimi poate fi diferită. De exemplu, A1 poate fi alcătuită din numere întregi, A2 poate fi alcătuită din caractere etc. Fie A=A1xA2x…xAn produsul cartezian a celor n mulţimi. Un articol reţine un element al mulţimii A. Un cîmp reţine un element al mulţimii Ai. Majoritatea limbajelor de programare evaluate cunosc tipul structurat articol (record în Turbo Pascal). Oricare cîmp poate fi, la rîndul său, articol (record în record).
3) Mulţimea
Fie A o mulţime finită. Ea poate fi privită ca o structură de date. Puţine dintre limbaje (Turbo Pascal) admit chiar un tip de date numit mulţime (set). Însă şi aici numărul elementelor unei mulţimi nu poate fi mai mare decît 255 (avantajul este că sunt predefinite operaţiile cu mulţimi ). În ipoteza că programatorul doreşte să implementeze algoritmi care lucrează cu mulţimi, indiferent de limbaj, se poate folosi vectorul caracteristic. Astfel , pentru o mulţime cu n elemente, orice submulţime a sa (v) va fi definită cu ajutorul unui vector cu n componente, în care fiecare componentă poate lua doar două valori 0 şi 1.
¥ i Є{1..n} avem v(i)=
În acest caz, este sarcina programatorului să stimuleze diversele operaţii cu mulţimi.
4) Stiva alocată static
Structura de date numită stivă a fost prezentată şi este binecunoscută cititorului. Nu ne rămîne decît să precizăm faprul că, pînă acum, a fost impementată ca structură statică, cu ajutorul vectorilor . modul în care s-a realizat implementarea ne este clar, cu ajutorul unui vector (ST l-am numit) şi a unei variabile k (indică vîrful ei). Principalul dezavantaj al unei astfel de implementări este dat de faptul că, deşi ca structură de date nu are limitat numărul nivelelor (putem folosi oricîte), practice, numărul acestora nu poate fi mai mare decît numărul componentelor vectorului. Acest dezavantaj se reduce simţitor în cazul cînd în care stivă este implementată dinamic, însă, din cauza limitării memoriei interne, se menţine totuşi.
5) Coada alocată static
Coada este acea structură de date în care toate înserările sunt făcute la unul din capetele cozii, iar toate ştergerile (în general, prelucrările) sunt făcute la celălalt capăt.
Este cu totul nerecomandabilă utilizarea vectorilor pentru stimularea cozii (alocarea statică). Facem această precizare deoarece, în această situaţie are loc un fenomen de migraţie a datelor de la dreapta la stînga în cadrul vectorului.
Să presupunem că stimulăm o coadă cu ajutorul unui vector cu zece componente, care reţin numere întregi. Presupunem de asemenea că niciodată în coadă nu vom mai avea mai mult bde 4 elemente. Introducem în coadă numerele 1,2,3,4. pentru a avea unde să introducem şi alte completăm vectorul de la dreapta la stînga.
| 4 | 3 | 2 | 1 |
Dacă scoatem din coadă pe 1 şi introducem în coadă pe 5, coada va arăta astfel:
| 5 | 4 | 3 | 2 |
Scoatem din coadă pe 2 şi obţinem pe 6:
| 6 | 5 | 4 | 3 |
Se observă acest fenomen de migraţie a datelor, de la dreapta spre stînga.
O altă soluţie ar fi ca, după fiecare stocare de date din coadă, să deplasăm întregul şir de date cărte dreapta, însă în acest caz se consumă mult timp.
O soluţie mai bună de implementare a cozii este să folosim un vector pe care îl privim ca fiind “circular” (facem convenţia ca după ultima componentă să urmeze prima). Adresa componentei de început a cozii va fi reţinută de altă variabilă, iar adresa componentei de sfîrşit va fi reţinută de o altă variabilă. Un astfel de procedeu poate fi folosit, dar nu este recomandabil atît timp cît există alocarea dinamică a memoriei (aşa se lucra prin anii 70, când limbajele “la modă” Fortan şi Cobol nu putea aloca memoria dinamic).
Din cele prezentate nu rezultă în nici un fel la ce foloseşte această structură de date. Deşi are numeroase utilizări (rol fundamental în informatică) pentru moment nu putem da exemple (ne lipsesc condiţiile necesare). Vezi parcurgerea în lăţime a arborilor oarecare.
8.1.2. Alocarea dinamică a memoriei în Turbo Pascal
Din punct de vedere al unui programator, memoria calculatorului se prezintă ca o succesiune de octeţi, fiecare octet avînd o adresă binară bine stabilită. Aceşti octeţi sunt identificaţi prin numere cuprinse între 0 şi n-1. convenim să numim adresă numărul de ordine al unui octet. Un octet este format din 8 biţi. Fiecare bit poate memora fie cifra binară 1, fie cifra binară 0, diversele tipuri de date cunoscute pînă acum (INTEGER, REAL) ocupă 2 sau mai mulţi octeţi consecutive. Pentru fiecare tip de dată cunoscut există o anumită logică potrivit căreia se face memorarea efectivă a conţinutului. De exemplu, pentru tipul INTEGER memorarea se face în COD COMPLEMENTAR. Nu ne propunem să prezentăm modul de reprezintare a datelor. Ne mărginim numai să atragem atenţia că o variabilă folosită de noi în program are un nume (simbolic), o valoare şi o adresă la care o găsim memorată (adresa primului octet din cei p octeţi consecutive ocupaţi de variabilă). În general, în limbajele evaluate nu este necesar ca programatorul să cunoască adresa la care se găsesc variabilele cu care lucrează.
Se cunosc două forme de alocare a memoriei de către programator în cadrul limbajului PASCAL: statică şi dinamică.
- Utilizînd forma de alocare statică, variabilele se declară utilizînd cuvîntul cheie VAR la începutul programului.
- Utilizînd forma de alocare dinamică, în timpul rulării programului, în funcţie de necesităţi, se alocă memorie suplimentară sau se renunţă la ea.
Pentru alocarea dinamică utilizăm tipul de date referinţă. Se consideră secvenţa de program:
type ref=^inr;
inr=record
nr:integer;
adrurm:ref
end;
var c:ref;
Aici variabila c este o variabilă de tip referinţă. Ea reţine adrese de înregistrări. La rîndul ei, o înregistrare are două cîmpuri: nr, care conţine un număr întreg (informaţia utilă) şi adrurm (adresa următoare), care conţine adresa unei alte înregistrări.
Procedura NEW (c) rezervă spaţiu (un număr de octeţi cosecutivi) pentru o înregistrare, adresa primului octet fiind depusă în variabila c. Presupunem că variabila c conţine adresa unei înregistrări.
Procedura DISPOSE (c) eliberează spaţiul de memorie afectat acelei înregistrări care avea adresa în c. Cuvîntul cheie NIL are semnificaţia ” nici o adresă”.
Observaţii:
1) c se referă la adresa care se găseşte în variabila c;
2) c^.nr se referă la cîmpul numeric al înregistrării care are adresa memorată în variabil c;
3) c^.adrurm semnifică adresa de înregistrare care se găseşte memorată în cadrul înregistrării care are adresa c;
4) c^.adrurm.nr semnifică variabila nr care se găseşte în înregistrarea care care adresa plasată în cîmpul adrurm al înregistrării cu adresa c.
Observaţie foarte importantă: spaţiul necesar variabilelor alocate dinamic se rezervă într-o zonă de memorie, special destinată numită HEAP (pentru PC compatibile i.B.M.).
8.2 Structuri dinamice.
8.2.1 Listă liniară simplu înlănţuită
O listă liniară simplu înlănţuită este o structură de forma:
adr1 adr2 adrn
Semnificaţia notaţiilor folosite este următoarea:
- adr1, adr2,…,adrn reprezintă adresele din memorie ale celor n înregistrări;
- in1, in2,…, inn reprezintă informaţiile utile din cele n înregistrări (altele decît cele de adresă pentru înregistrarea următoare ).
Denumirea “simplu înlănţuită” provine din faptul că fiecare element al listei conţine o singură adresă, şi anume adresa elementului următor din listă. Aici avem o excepţie pentru ultimul element, care are în cîmpul de adresă cuvîntul cheie NIL (semnificînd “nici o adresă”). Operaţiile pe care le putem face în legătură cu această structură de date sunt următoarele:
1) creare;
2) listare;
3) adăugare;
4) ştergere;
În programul care urmează aceste operaţii sunt realizate de procedurile cu acelaşi nume (facem precizarea că, în program, informaţiile utile sunt date de numere 1,2,…,n). Am recurs la această cale din dorinţa de a simplifica pe cît posibil prezentarea.
1) Creare
Se cere numărul n de înregistrări. Se creează o primă înregistrare avînd ca informaţie utilă numărul 1. Variabila b de tip referinţă reţine adresa primei înregistrări din listă. Pentru fiecare i cuprins între 2 şi n se adaugă cite o nouă înregistrare listei. Variabila d reţine adresa ultimei înregistrări deja create pentru a-i completa cîmpul de adresă. Se procedează astfel pentru că în momentul în care am creat o înregistrare nu se cunoaşte adresa înregistrării care urmează.
2) Listare
Am precizat faptul că b reţine adresa primei înregistrări. Pentru a nu deteriora această valoare, o vom memora în variabila c . Atît timp cît nu am ajuns la sfîrşitul listei, tipărim informaţia utilă şi încărcăm în c adresa înregistrării următoare.
3) Adăugare
Operaţia de adăugare a unui nou element la listă comportă cunoaşterea a două informaţii:
- Informaţia utilă a elementului (înregistrării) din listă după care urmează să se facă adăugarea;
- Informaţia utilă a elmentului care urmează să fie adăugat.
Adăugarea propriu-zisă constă în următoarele:
- Poziţionarea pe înregistrarea după care urmează să adăugăm noua înregistrare;
- Alocarea spaţiului pentru noua înregistrare;
- Completarea informaţiei utile pentru aceasta;
- Completarea adresei următoare a noii înregistrări, care va fi adresa următoare a înregistrării pe care suntem poziţionaţi;
- Cîmpul de adresă al înregistrării pe care suntem poziţionaţi va lua ca valoare adresa noii înregistrări.
Observaţie:
- Aşa cum este concepută procedura, nu se poate adăuga o primă înregistrare listei. Propunem ca exerciţiu modificarea ei în acest sens.
4) Ştergerea
Pentru a şterge o înregistrare este necesar să cunoaştem informaţia utilă
a acesteia. Vom proceda în mod diferit pentru situaţiile în care se şterge prima înregistrare sau una diferită de prima.
În cazul în care ştergem prima înregistrare, efectuăm operaţiile:
- Se salvează în variabila c adresa primei înregistrări (cea care urmează a fi ştearsă);
- Variabila b (care reţine adresa primei înregistrări) va lua ca valoare adresa următoare primei înregistrări;
- Se eliberează spaţiul rezervat înregistrării şterse;
În situaţia în care ştergem o altă înregistrare decît prima, procedăm în felul următor:
- Se face poziţionarea pe înregistrarea care urmează a fi ştearsă;
- Cîmpul de adresă al înregistrării precedente capătă valoarea cîmpului de adresă al înregistrării curente;
- Eliberăm spaţiul rezervat înregistrării curente.
program 11n;
type ref=^inr;
inr=record
nr:integer;
adrurm:ref
end;
var b,c,d:ref;
n,i: integer;
procedure creare;
begin
write (‘n=’); readln(n);
new ( c); c^.nr:=1;
b:=c; d:=c;
for i:=2 to n do
begin
new ( c);
c^.nr:=i;
d^.adrurm:=c;
d:=c
end;
procedure listare;
begin
c:=b;
while c< >nil do
begin
writeln( c^.nr);
c:=c^.adrurm
end
end;
procedure ştergere;
begin
write (‘i=’); readln(i);
if i=1 then
begin
c:=b;
b:=b^.adrurm;
dispose (c)
end
else
begin
c:=b;
while c^.nr< >i do
begin
d:=c;
c:=c^.adrurm
end;
d^.adrurm:=c^.adrurm;
dispose ( c)
end
end;
procedure adăugare;
begin
write(‘i=’); readln(i);
write(‘n=’); readln(n);
c:=b;
while c^.nr< >i do c:=c^.adrurm;
new (d );
d^.nr:=n;
d^.adrurm:=c^.adrurm;
c^.adrurm:=d
end;
begin
creare;
listare;
adăugare;
listare;
ştergere;
listare
end.
În continuare ne propunem să construim şi să tipărim o listă liniară simplu înlănţuită, utilizînd tehnici recursive.
Funcţia lista are sarcina de a construi lista liniară înlănţuită. La început se cere informaţia utilă. În situaţia în care aceasta este diferită de 0 (valoare care semnifică faptul că nu mai avem de adăugat nici un element), se rezervă un spaţiu pentru noua înregistrare, se completează informaţia utilă, iar cîmpul adrurm va lua valoarea funcţiei de tip lista care se autoapelează. În încheiere lista va lua valoarea c a cîmpului care reţine adresa noului element.
Este interesant să observăm că iniţial se creează lista simplu înlănţuită fără a completa cîmpul adresa, această completare urmînd să se facă la revenirea în procedură.
Să ne imaginăm că rulînd acest program dorim să creăm o listă cu două înregistrări care au informaţiile utile 1 şi 2.
Rularea decurge astfel:
- Apelăm procedura;
- Citim valoarea lui n şi anume 1;
- Se alocă spaţiu pentru prima înregistrare;
- Completăm informaţia utilă;
- Pentru a completa adresa următoare înregistrării curente, se apelează din nou funcţia;
- Citim valoarea lui n şi anume 2;
- Alocăm spaţiu pentru a doua înregistrare;
- Completăm informaţia utilă cu 2;
- Se apelează din nou funcţia;
- Se citeşte 0;
- Funcţia ia valoarea NIL;
- Se revine din apel şi se continuă de acolo de unde am rămas;
- Cîmpul de adresă al celei de a doua înregistrări va lua valoarea NIL;
- Funcţia capătă valoarea adresei înregistrării 2,
- Se revine din apel;
- Cîmpul de adresă al primei înregistrări ia valoarea celei de-a doua înregistrări;
- Funcţia ia valoarea adresei primei înregistrări;
- Se revine în programul principal.
Observăm că valoarea variabilei c a programului principal va fi după rulare adresa primei înregistrări.
Propunem ca exerciţiu construirea listei utilizînd o procedură recursivă. Putem defini recursiv lista astfel:
- O mulţime vidă de înregistrări este o listă;
- Dacă la o listă se adaugă o înregistrare, se obţine o listă.
Recursiv putem tipări informaţia utilă din listă în două moduri:
- În ordinea în care a fost creată;
- În ordinea inversă celei în care a fost creată.
Lăsăm pe seama cititorului analiza acestor două proceduri.
program 11r;
type ref=^inr;
inr=record
nr:integer;
adrurm:ref
end;
var n:integer;
c:ref;
function lista:ref;
var c:ref;
begin
write(‘n=’); readln(n);
if n< >0
then
begin
new(c);
c^.nr:=n;
c^.adrurm:=lista;
lista:=c;
end
else lista:nil
end;
procedure tipard(c:ref);
begin
if c< >nil
then
begin
writeln(c^.nr);
tipard (c^.adrurm)
end
end;
procedure tipari(c:ref);
begin
if c< > nil tfen
begin
tipari (c^.adrurm);
writeln(c^.nr)
end
end;
begin
c:=lista;
tipard©;
writeln(‘————’);
tipari©
end.
Aplicaţie (Sortare topologică)
Presupunem că dorim sortarea numerelor. 1, 2, ….., n, numere care se găsesc într-o ordine oarecare, alta decît naturală. Pentru a afla relaţia în care se găsesc numerele, introducem un număr finit de perechi (i,j). O astfel de pereche ne spune că, în relaţia de ordine considerată, i se află înaintea lui j.
Exemplu 1: n=3 şi citim perechile (3,1) şi (3,2). Numărul 3 se află înaintea lui1 şi 3 se află înaintea lui 2. Apar două soluţii posibile: 3,1,2 şi 3,2,1, întucît nu avem nici o informaţie asupra relaţiilor dintre 1şi 2. Tragem de aici concluzia că o astfel de problemă poate avea mai multe soluţii.
Exemplu 2: n=3 şi citim (1,2), (2,3), (3,1). În acest caz nu avem soluţie.di primele două relaţii rezultă că ordinea ar fi 1,2,3 iar a-3-a contrazice această ordine.
În concluzie, problema ar avea sau nu soluţie, iar dacă are poate fi sau nu unică.
Algoritmul pe care îl prezentăm în continuare furnizează o singură soluţie atunci cînd problema admite soluţii. În caz contrar specifică faptul că problema nu admite soluţie.
Vom exemplifica funcţionarea algoritmului pe exemplu următor: n=4 şi se citesc perechile (3,4), (4,2), (1,2), (3,1).
Pentru fiecare număr între 1 şi n trebuie să avem următoarele informaţii:
- Numărul predecesorilor săi;
- Succesorii săi;
Pentru aceasta folosi doi vectori:
- contor, vector care reţine numărul predecesorilor fiecărui k, cu k Є {1..n}.
- a, care reţine adresele de început ale listelor de succesori ai fiecărui element.
Pentru fiecare element există o listă simplu înlănţuită a succesorulor săi. Fiecare înregistrare din aceste liste conţine două elemente:
- succesorul;
- adresa următorului element din listă.
Iniţial, în dreptul fiecărui element în vectorul „contor” se trece 0, iar în vectorul „a” se trece NIL.
Citirea unei perechi (i,j) înseamnă efectuarea următoarelor operaţii:
- mărirea cu 1 a cîmpului contor (j) (j are un predecesor, şi anume pe i);
- adăugarea lui j la lista succesorului lui i.
Pentru exemplu nostru, lucrurile decurg astfel:
CONTOR
A
În continuare se procedează astfel:
- toate elementele au 0 în cîmpul lui contor se reţine într-un vector c;
- pentru fiecare element al vectorului c se procedează astfel:
- se tipăreşte;
- se marchează cu -1 cîmpul său de contor;
- pentru toţi succesorii săi (aflaţi în lista succesorilor) se scade cu 1 din cîmpul contor (este normal, întrucît aceştia au un predecesor mai puţin).
- Se reia algoritmul dacă nu este îndeplinită una din condiţiile următoare:
v Au fost tipărite toate elementele, caz în care algoritmul se încheie cu succes;
v Nu avem nici un element cu 0 în cîmpul contor, caz în care relaţiile au fost incoerente.
.
| 1 | 2 | -1 | 0 |
| al1 | nil | al3 | al4 |
| 2 | 4 | 2 |
tipăresc 3, scad 1 din predecesorii lui 4 şi 1, cu -1 contorul lui 3;
| 0 | 1 | -1 | -1 |
Observaţie:
Algoritmul are mai multe aplicaţii, ca de exemplu:
- Ordonarea unor activităţi, atunci cînd ele sunt condiţionate una după alta;
- Ordonarea unor termeni care se cer explicaţi pentru a-i putea explica prin alţi deja prezentaţi.
Program stoop;
type ref=^inr;
inr=record
succ:integer;
urm:ref
end;
vector=array [1..100] of integer;
vectad=array [1..100]of ref;
var n, m, i, j, k:integer;
contor, c:vector;
a:vectad;
gasit:boolean;
procedure adaug (i,j:integer);
var c,d:ref;
begin
contor [j]:=contor [j]+1;
c:=a[i];
new (d);
d^.urm:=nil;
d^.succ:=j;
if c=nil
then a[i]:=d
else
begin
while c^.urm< >nil do c:=c^.urm;
c^.urm:=d
end
end;
procedure actual (i:integer);
var c:ref;
begin
c:=a[i];
while c < >nil do
begin
contor [c^.succ]:=contor[c^.succ]-1;
c:=c^.urm
end
end;
begin
write (’n=’); readln(n);
for i:=1 to n do
begin
contor [i]:=0;
a[i]:=nil
end;
while i< >0 do
begin
write (’tastati i,j=’);
readln (i,j);
if i< >0 then adaug (i,j)
end;
m:=n;
repeat
k:=1;
gasit:false;
for i:=1 to n do if contor [i]=0
then
begin
gasit:=true;
m:=m-1;
c[k]:=1;
k:=k+1;
contor [i]:=-1
end;
for i:=1 to k-1 do
begin
actual (c[i]);
writeln (c[i]);
end;
until (not gasit) or (m=0);
if m=0
then writeln (’totul e ok’)
else writeln (’relatii contradictorii’)
end.
8.2.2 Lista liniară dublu înlănţuită
O listă dublu înlănţuită este o structură de date de forma:
adr1 adr2 adrn
Operaţiile pe care le putem face cu o listă dublu înlănţuită sunt următoarele:
1) Creare;
2) Adăugare la dreapta;
3) Adăugare la stînga;
4) Adăugare în interiorul listei;
5) Ştergere din interiorul listei;
6) Ştergere la sînga listei;
7) Ştergere la dreapta listei;
8) Listare de la sînga la dreapta;
9) Listare de la dreapta la sînga;
1) Creare
O listă dublu înlănţuită se creează cu o singură înregistrare. Pentru a ajunge la numărul de înregistrări dorit, utilizăm proceduri de adăugare la stînga sau la dreapta. În programul de faţă acest lucru este realizat de procedura creare. Această procedură realizează operaţiile următoare:
- Citirea informaţiei utile;
- Completarea înregistrării cu informaţia utilă;
- Completarea adreselor de legătură la stînga şi la dreapta cu NIL;
- Variabilele tip referinţă b şi s vor căpăta valoarea adresei acestei prime înregistrări (b semnfică adresa înregistrării cea de mai din stînga, s adresa ultimei înregistrări din dreapta).
2) Adăugarea la dreapta
Această operaţie este realizată de procedura addr. Pentru adăugarea unei înregistrări se realizează următoarele operaţii:
- Citirea informaţiei utile;
- Alocarea spaţiului pentru înregistrare;
- Completarea adresei la dreapta cu NIL;
- Completarea adresei din stînga şcu adresa celei mai din dreapta înregistrări (reţinute în variabila s);
- Modificare cîmpului de adresă la dreapta a înregistrării din s cu adresa noii înregistrări;
- s va lua valorile noi înregistrări, deoarece va fi cea mai din dreapta.
3) Adăugarea la stînga
Această operaţie o propunem ca exerciţiu.
4) Adăugare în interiorul listei
Această operaţie este realizată de procedura includ, care realizează următoarele operaţii:
ü Parcurge lista de la stînga la dreapta căutînd înregistarea cu informaţia utilă m, în dreapta căreia urmează să introducem noua înregisrare;
ü Citeşte informaţia utilă;
ü Alocă spaţiu pentru noua înregistrare;
ü Completează informaţia utilă;
ü Adresa stîngă a noii înregistrări ia valoarea adresei înregistrării de informaţie utilă m;
ü Adresa dreaptă a noii înregistrări ia valoarea adresei dreapta a înregistrării de informaţia utilă m;
ü Adresa dreaptă a înregistrării cu informaţia utilă m ia valoarea noii înregistrări;
Observaţie:
Propunem ca exerciţiu realizarea unei proceduri de adăugare în interiorul listei a unei înregistrări la dreapta înregistrării cu informaţia utilă m.
5) Ştergere din interiorul listei
Această operaţie este realizată de procedura sterg. Operaţiile efectuate de această procedură următoarele:
ü Se parcurge lista de la stînga la dreapta pentru a ne poziţiona pe înregistrarea care urmează a fi ştearsă;
ü Cîmpul de adresă dreapta al înregistrării care o precede pe această şi va lua valoarea cîmpului de adresă dreapta al înregistrării care va fi ştearsă;
ü Cîmpul de adresă stînga al înregistrării care urmează înregistrării care va fi ştearsă va lua valoarea cîmpului de adresă stînga al înregistrării pe care o ştergem;
ü Se eliberează spaţiul de memorie rezervat înregistrării care se şterge.
6)-7) Ştergere la sînga şi la dreapta listei
Aceste două operaţii sunt propuse cititorului ca exerciţiu.
8) Listare de la sînga la dreapta
Această operaţie este realizată de procedura listare, procedură care realizează următoarele operaţii:
v Porneşte din stînga listei;
v Atît timp cît nun s-a ajuns la capătul din dreapta al listei, se tipăreşte informaţia utilă şi se trece la înregistrarea următoare.
9) Listare de la dreapta la sînga
O propunem ca exerciţiu.
Program 1di;
type ref=^inr;
inr=record
as:ref;
nr:integer;
ad:ref
end;
var b,s,c:ref;
n,m,i:integer;
procedure creare (var b,s:ref);
begin
write (‘n=’); readln (n);
new (b); b^.nr:=n;
b^.as:=nil; b^.ad:=nil;
s:=b
end;
procedure addr (var s:ref);
var d:ref;
begin
write (‘n=’); readln (n);
new (d); d^.nr:=n;
d^.as:=s; d^.ad:=nil;
s^.ad:=d; s:=d
end;
procedure listare (b:ref);
var d:ref;
begin
d:=b;
while d< >nil do
begin
writeln (d^.nr);
d:=d^.ad
end
end;
procedure include (m:integer; b:ref);
var d,e:ref;
begin
d:=b;
while d^.nr< >m do d:d^.ad;
write (‘n=’); readln (n);
new (e);
e^.nr:=n;
e^.as:=d;
d^.ad^.as:=e;
e^.ad:=d^.ad;
d^.ad:=e
end;
procedure sterg (m:integer; b:ref);
var d:ref;
begin
d:=b;
while d^.nr< >m do d:=d^.ad;
d^.as^.ad:=d^.ad;
d^.ad^.as:=d^.as;
dispose (d)
end;
begin
writeln (‘creare lista cu o singura inregistrare’);
creare (b, s);
write (‘cite inregistrari se adauga?’);
readln (m);
for i:=1 to m do addr (s);
writeln (‘acum listez de la stinga la dreapta’);
listare (b);
writeln (‘includem la dreapta o inregistrare’);
write (‘dupa care inregistrare se facec includerea?’);
readln (m);
include (m,b);
writeln (‘acum listez de la stinga la dreapta’);
listare (b);
writeln (‘Acum stergem o inregistrare din interior’);
write (‘Ce inregistrare stergem?’);
readln (m);
sterg (m,b);
writeln (‘Acum listez de la stinga la dreapta’);
listare (b)
end.
8.2.3 Lista circulară
Se consideră o listă liniară. Dacă, ultima înregistrare, adresa următoare va fi înregistrării, am definit o listă circulară. În cazul în care lista iniţială este simplu înlănţuită, listă circulară va fi simplu înlănţuită, iar dacă listă iniţială este dublu înlănţuită şi lista ciculară va fi dublu înlănţuită.
Întucît operaţiile care se efectuează cu aceasta sunt asemănătoare cu cele prezente anterior, ne oprim cu explicaţiile în acest punct.
8.2.4 Stiva
O stivă poate fi definită şi ca o listă liniară simplu înlănţuită în care toate intrările şi ieşirile se fac la un singur capăt al ei.
În acest caz, elementul de pe nivelul k al stivei va reţine adresa elementului de pe nivelul k-1.
În versiunile anterioare ale acestei cărţi am prezentat stiva ca fiind o listă liniară dublu înlănţuită, fapt pentru care am fost criticat. Motivul? Prezentînd stiva ca o listă dublu înlănţuită, am avantajul că o pot folosi în mai multe aplicaţii (de exemplu, pentru backtracking, unde pentru a valida un element era necesară comparaţia sa cu cele aflate în stivă pe nivelele inferioare). Desigur, chiar folosind pentru stiva actuala definiţie (prezentă în toate lucrările de specialitate) putem realiza toate aplicaţiile făcute pînă în acest moment, însă mai greu (recursiv, cu pierdere de timp). Chiar modul de lucru standart cu stiva calculatorului (în limbaj de asamblare) permite accesul la elemente ale stivei care nu se află pe ultimul nivel.
Datorită celor prezentate, vom implementa stiva tot ca listă liniară dublu înlănţuită. Cititorul, dacă nu este de acord cu aceasta, îşi poate scrie propriile rutine.
Fiecare înregistrare corespunzătoare stivei conţine trei informaţii: adresa înainte (a elementului următor), adresa înapoi şi informaţia utilă care se diferă de la caz la caz.
Pentru a lucra cu o astfel de stivă sunt suficiente două proceduri: adaug şi scot, cu rolul de a adăuga şi, respectiv, de a scoate o informaţie din stivă. Modul de alcătuire al acestora îl putem analiza din programul următor:
Program stivă;
type ref=^inr;
inr=record
adrurm, adrinap:ref
end;
var v:ref;
n:integer;
procedure adaug (var v:ref);
var c:ref;
n:integer;
begin
write (‘n=’); readln (n);
new (c);
c^.nr:=n;
c^.adrurm:=nil;
c^.adrinap:=v;
if v< >nil then v^.adrurm:=c;
v:=c
end;
procedure scot (var v:ref);
var c:ref;
begin
if v=nil
then
writeln (’Stiva este vida’)
else
begin
writeln (v^.nr);
c:=v;
v:=v^.adrinap;
dispose (c)
end
end;
begin
adaug (v); adaug (v);
scot (v); scot (v); scot (v)
end.
Spre deosebire de stimularea stivei prin intermediul vectorilor, aici avem avantajul că stiva nu este limitată la cele n componente alocate vectorului. Principalul dezavantaj al acestui mod de stimulaqre a stivei este faptul că pe lîngă informaţia utilă se reţin informaţii de adresă, fapt care duce la consum de memorie.
8.2.5 Coada
Structura de coadă a fost deja prezentată (nu şi exemplificată). Reamintim faptul că toate intrările se fac la un capăt şi toate ieşirile se fac la celălalt capăt. Coada nu se poate implementa dinamic cu mare uşurinţă. Astfel va fi implementată ca o listă simplu înlănţuită (sau, pentru a uşura anumite operaţii, chiar dublu înlănţuită). O variabilă de tip referinţă va reţine o adresă de început a cozii, iar alta de acelaşi tip va reţine adresa de sfîrşit. Exerciţiu: scrieţi un program care creează o coadă cu două, trei elemente, apoi le scoate. La sfîrşit se va da mesajul coadă vidă (asemănător cu programul care exemplifică stiva).
8.2.6 Structuri arborescente
8.2.6.1 Arbori binari
Vom defini arborii binari ca un set finit T de unul sau mai multe noduri, astfel încît:
- există un nod cu destinaţie specială numită tulpina (rădăcina) arborelui;
- Celelalte noduri sunt repartizate în două seturi disjuncte şi fiecare din aceste seturi este la rîndul lui un arbore.
Observaţii:
- Cei doi arbori subordonaţi tulpinei poartă denumirea de subarbore stîng şi subarbore drept,
- Definiţia este recursivă, acest lucru fiind de mare folos în continuare,
- În cele ce urmează, pentru tulpină vom folosi şi termenul de vîrf,
- Dacă un nod nu subordonează arbori, îl vom numi nod terminal, în caz contrar îl vom numi nod neterminal.
Ne propunem să construim un program care generează în memorie un arbore binar. Pentru aceasta, fiecare nod va fi o înregistrare care conţine trei cîmpuri: informaţia utilă, adresa subarborelui stîng şi adresa subarborelui drept. Modul recursiv de definire a arborilor binari ne conduce la ideea de a folosi o funcţie recursivă şi chiar de a utiliza metoda DIVIDE ET IMPERA conform acestei metode se procedează astfel:
Se citeşte informaţia utilă pentru un nod;
Se alocă spaţiu în memorie pentru aceasta;
Se completează informaţia utilă;
Se costruieşte subarborele stâng;
Se costruieşte subarborele drept;
Exact în acest mod se procedează funcţia arb de tip referinţă. Aici, este de remarcat modalitate de trecere la construcţia subarborilor stâg şi drept. Atunci cînd trebuie completate cîmpurile de adresă, acestea primesc ca valoare funcţiei, ceea ce duce autoapelarea ei. Semnalizarea faptului că nu avem subarbore stîng sau drept se face completînd 0 pentru informaţia utilă.
În principal se folosesc trei metode de parcurgere a arborilor.
- Stînga, vîrf, dreapta sau inordine, în care se parcurg mai întîi subarborele stîng, rădăcina şi apoi subarborele drept;
- Vîrf, stînga, dreapta saunpreordine, în care se parcurg mai întîi rădăcina, subarborele stîng şi apoi subarborele drept;
- Stînga, dreapta, vîrf sau postordine, în care se parcurg mai întîi subarborele stîng, subarborele drept şi apoi rădăcina.
Fie arborele de mai jos:
Datele se introduc astfel:
1240050800360079001000.
Parcurgerea în inordine înseamnă:
4 2 5 8 1 6 3 9 7 10.
Parcurgerea în preordine înseamnă:
1 2 4 5 8 3 6 7 9 10.
Parcurgerea în postordine înseamnă:
8 5 2 6 9 10 7 3 1.
Parcurgerile arborului binar sunt realizate de procedurile: svd ( Stînga, vîrf, dreapta), vsd (Vîrf, stînga, dreapta), sdv (Stînga, dreapta, vîrf).în comentariul pe care îl facem acestor proceduri ne mărginim să precizăm că sunt realizate utilizînd tehnica DIVIDE ET IMPERA.
Program arbori;
type ref=^inr;
inr=record
st,dr:ref;
nr:integer
end;
var c:ref;
function arb:ref;
var n:integer;
c:ref;
begin
write (‘n=); readln (n);
if n< >0
then
begin
new (c);
arb:=c;
arb^.nr:=n;
arb^.st:=arb;
arb^.dr:=arb
end
else arb:=nil
end;
procedure svd (c:ref);
begin
if c< >nil
then
begin
svd (c^.st);
writeln (c^.nr);
svd (c^.dr)
end
end;
procedure vsd (c:ref);
begin
if c< >nil
then
begin
writeln (c^.nr);
vsd (c^.st);
vsd (c^.dr)
end
end;
procedure sdv (c:ref);
begin
if c< >nil
then
begin
svd (c^.st);
svd (c^.dr);
writeln (c^.nr)
end
end;
begin
c:=arb;
writeln (‘Parcurg stinga virf dreapta’);
svd(c);
writeln (‘Parcurg virf stinga dreapta’);
vsd (c);
writeln (‘Parcurg stinga dreapta virf’);
sdv (c)
end.
Aplicaţie. Forma poloneză
Se dă o expresie aritmetică. Să se construiască forma poloneză asociată acesteia.
Acest exerciţiu l-am rezolvat utilizînd diagramele de sintaxă. În acest capitol îl vom rezolva cu ajutorul arborilor binari. Tehnica de programare folosită va fi DEVIDE ET IMPERA.
Expresiile aritmetice pot fi reprezentate utilizînd arbori binari, respectînd următoarele reguli:
- Fiecare operaţie corespunde unui nod neterminal, avînd ca informaţie utilă operaţia respectivă;
- Fiecare nod terminal este etichetat cu o variabilă sau cu o constantă;
- Pentru fiecare nod neterminal subarborele din stînga şi cel din dreapta reprezintă, în această ordine, cei doi operanzi;
- Rădăcina corespunde ultimei operaţii executate la evaluarea expresiei.
Exemplu: Expresiei (a+b)*c-d/e i se asociază arborele binar din figura de mai jos. Parcurgerea acestui arbore în postordine va da chir forma poloneză: ab+c*de/-. Utilizînd cele spuse, pentru rezolvarea problemei, vom proceda în felul următor:
- Construim arborele binar asociat, expresiei aritmetice;
- Îl parcurgem în postordine pentru a obţine forma poloneză.
Parcurgerea arborelui a fost deja prezentată, problema principală rămînînd construirea acestuia.
Pentru aceasta vom acorda priorităţi operatorilor şi operanzilor (mai puţin parantezelor), după cum urmează:
- Prioritatea iniţială a operatorilor ‘+’, ‘-’ este 1;
- Prioritatea iniţială a operatorilor ‘*’, ‘/’ este 10;
- La prioritatea unui operator se adună 10 pentru fiecare pereche de paranteze între care se găseşte;
- Prioritatea unui operand este 1000.
În program acest lucru se realizează astfel:
- Se citeşte expresia aritmetică în variabila e;
- Se utilizează o variabilă j care indică ce număr se adaugă la prioritatea iniţială a unui operator (la întîlnirea unei paranteze deschise j creşte cu 10, iar la întîlnirea unei paranteze închise j scade cu 10);
- Se parcurge expresia caracter cu caracter şi se pun în vectorul p priorităţile acestor operatori şi operanzi (mai puţin ale parantezelor);
- În efp se construieşte expresia fără paranteze (la expresia aritmetică iniţială lipsesc parantezele), iar în pfp se obţine vectorul priorităţilor, din care, spre deosebire de p, lipsesc componentele corespunzătoare parantezelor (acestea nu aveau nici o valoare).
Utilizînd efp şi pfp ,cu ajutorul funcţiei arb, se construieşte arborele ataşat expresiei aritmetice. Un nod al acestui arbore are ca informaţie utilă un operator sau un operand.
Conform tehnicii DIVIDE ET IMPERA, funcţia arb procedează în felul următor:
- de la limita superioară către limita inferioară (limite corespunzătoare subşirurilor de caractere tratate din efp) caută operatorul sau operandul cu prioritate minimă, reţinînd poziţia acestuia;
- acesta constituie informaţia utilă din nod, care va fi completată;
- în situaţia în care limita inferioară este diferită de limita superioară, pentru completarea adresei subarborelui din stînga şi a arborelui din dreapta se reapelează funcţia, iar în caz contrar aceste cîmpuri capătă valoarea NIL.
Pentru listarea în postordine se utilizează procedura parc .
program fp;
type ref=^inr;
sir=array [1..30] of char;
vector=array [1..30] of integer; inr=record
as, ad:ref;
op:char
end;
var e, efp:sir;
pfp, p:vector;
i, j, n:integer;
c:ref;
a:char;
function arb (1i,1s:integer; var efp:sir; var pfp:vector):ref;
var c:ref;
i, j, min: integer;
begin
min:=pfp [1s];
i:=1s;
for j:= 1s downto 1i do
if pfp [j]<min
then
begin
min:=pfp [j];
i:=j
end;
new ( c);
arb:=c;
arb^.op:=efp [i];
if 1i=1s
then
begin
arb^.as:=nil;
arb^.ad:=nil
end
else
begin
arb^.as:=arb(1i, i-1, efp, pfp);
arb^.ad:=arb(i+1, 1s, efp, pfp)
end
end;
procedure parc (c:ref);
begin
if c< >nil
then
begin
parc ( c^.as);
parc (c^.ad);
write (c^.op)
end
end;
begin
j:=0;
read (a);
n:=1;
while a< >’.’ do
begin
e [n]:=a;
n;=n+1;
read (a )
end;
n:=n-1;
for I;=1 to n do
case e[i] of
‘)’:j:=j-10;
‘(‘:j:=j+10;
‘+’,’-‘:p[i]:=j+1;
‘*’,’/’:p[i]:=j+10
else p[i]:=1000
end;
j:=1;
for i:=1 to n do
if (e[i] < >’)’) and ( e[i]< >’(‘)
then
begin
efp[j]:=e[i];
pfp[j]:=p[i];
j:=j+1
end;
c:=arb (1,j-1, efp,pfp);
parc ( c);
writeln
end.
Aplicaţie. Arbori de căutare
Se numeşte arbore de căutare un arbore binar ale cărui noduri au o cheie de identificare ( mulţimea cheilor asociate nodurilor este o mulţime bine ordonată – între oricare două elemente distincte ale acestei mulţimi a şi b avem sau a>b sau a<b=, iar pentru fiecare nod avem proprietăţile următoare:
- Orice cheie asociată unui nod al subarborelui stîng este mai mică decît cheia asociată nodului;
- Orice cheie asociată unui nod al subarborelui drept este mai mare decît cheia asociată nodului.
Orice nod al arborelui are asociate trei informaţii
- Cheia de identificare (NR);
- Adresa subarborelui stîng (AS);
- Adresa subarborelui drept (AD).
Arborii de căutare au fost creaţi pentru regăsirea rapidă a informaţiei.
Aplicaţiile care creează şi actualizează un arbore de căutare, care reţine numerele naturale citite (acestea var fi şi chei asociate noduri).
Vor fi prezentate următoarele funcţii:
- Inserarea şi căutarea;
- Listarea;
- Ştergerea;
Inserarea şi căutarea
Crearea arborilor de căutare se face aplicînd de un număr de ori operaţia de inserare. Regula de inserare este următoarea:
- se compară cheia asociată a unui nod cu numărul de inserat;avem trei posibilităţi:
- cheia coincide cu numărul – se renunţă la inserarea acelui număr;
- cheia este mai mare decît numărul – se încearcă inserarea în subarborele stîng;
- cheia este mai mic decît numărul – se încearcă inserarea în subarborele drept.
Inserarea propriu-zisă se realizează atunci cînd subarborele stîng, respectiv drept, este vid, altfel se reia.
Mecanismul descris este tipic tehnicii DIVIDE ET IMPERA.
Pornim de la un arbore de căutare vid. Inserăm numărul 10.
| 10 |
Inserăm 5. Acest număr se inserează în subarborele sting.
Inserăm 7. Acesta este mai mic decît 10. Se trece la subarborele stîng. Se compară cu 5, faţă de care este mai mare. Se inserează în subarborele drept.
Se inserează 15; cum acesta este mai mare decît 10 vom avea:
Iată cum arată arborele după inserarea numerelor 3, 9, 12, 30.
Operaţia de căutare este asemănătoare cu cea de inserare. Cheia căutată se compară cu cheia asociată vîrfului. În caz de egalitate imformaţia a fost găsită. Dacă este mai mică decît cheia asociată nodului, se caută în subarborele stîng iar dacă este mai mare se caută în subarborele drept. Dacă în procesul de căutare s-a ajuns să se caute cheia într-un subarbore vid, înseamnă că nodul cu cheia respectivă lipseşte.
Programul care urmează conţine o procedură de inserare (C_I). Când cheia pentru care se încearcă inserarea lipseşte se execută inserarea, altfel se dă un mesaj corespunzător.
Transmiterea parametrului c se face prin referinţă. Adresa de alocare (obţinută prin NEW) va fi trecută automat părintelui, ca adresă de subarbore stîng sau drept (după caz).
Odată creat, un arbore de căutare permite regăsirea mai rapidă a informaţiei decât în cazul în care ar fi memorate secvenţial. Odată analizată informaţia ataşată prin nod, în caz de inegalitate se trece la subarborele stâng (sau drept) caz în care informaţiile cu cheile din subarborele drept (sau stâng) nu se mai ia în calcul. Numărul de comparaţii este mai mic sau egal cu numărul de niveluri ale arborelui de căutare. De exemplu, pentru regăsirea unei imformaţii, în cadrul arborelui din figură se fac cel mult 4 comparaţii. Dacă pentru memorizare se utilizează o listă simplu înlănţuită, în cazul cel mai defavorabil trebuie de efectuate 8 comparaţii.
Există totuţi o problemă care poate duce la scăderea eficienţei de căutare. În cazul în care cheile sunt introduse în ordine strict crescătoare sau în ordine descrescătoare, arborele degenerează într-o listă liniară (fiecare nod are un singur subarbore nevid). Putem aprecia că introducerea numerelor în această ordine este improbabilă.
Listarea informaţiei
Informaţia se poate lista utilizând oricare din metodele cunoscute pentru parcurgerea arborilor. Dacă dorim listarea imformaţiilor în ordinea strict crescătoare a cheilor, se utilizează metoda stânga-vârf-dreapta (inordine), întucât pentru orice nod avem următoarele:
- cheile nodurilor din subarborele stâng sunt mai mici decât cheia asociată nodului;
- cheile nodurilor din subarborele drept sunt mai mari decât cheia asociată nodului.
Vom lista arborele stâng,informaţia din nod şi informaţiile din subarborele drept (SVD).
Ştergerea
După ştergerea unui nod care are o anumită cheie, arborele rămas trebuie să fie de căutare. Nodul care urmează a fi şters se caută după metoda de acum binecunoscută. Se disting 4 situaşii posibil:
a) nodul care urmează a fi şters este nod terminal – în acest caz se face ştergerea având grijă ca la părintele lui să înlocuim adresa către el cu NIL;
b) nodul care urmează a fi şters subordonează un singur subarbore – cel drept – caz în care părintelui i se va înlocui adresa către el cu adresa subarborelui drept, iar nodul respectiv se va şterge;
c) nodul care urmează a fi şters subordonează un singur subarbore – cel stâng – caz în care părintelui i se va înlocui adresa către el cu adresa subarborelui stâng, iar nodul respectiv se va şterge;
d) nodul care urmează a fi şters (după cum vom vedea, acesta se va şterge numai logic) subordonează doi subarbori, caz în care se fac operaţiile:
- se identifică cel mai din dreapta nod al subarborelui stâng corespunzător nodului care urmează a fi şters (acesta va fi şters ăn mod efectiv, ni înainte de a muta informaţiile sale la nodul care se şterge logic);
- cheia acestuia şi alte informaţii utile conţinute de el (altele decât cele de adresă) se mută lanodul care urmează a fi şters;
- subarborele stâng care se va şterge fizic se leagă:
- în stânga nodului care se va şterge logic (dacă nodul identificat ca cel mai din dreapta din subarborele stâng este descendentdirect al nodului care se va şterge logic)
- în dreapta tatălui nodului care se va şterge fizic (în caz contrar);
se şterge fizic nodul care a fost identificat şi ale cărui informaţii au fost mutate (cu cheia cea mai mare din suarborele stâng).
Exemlu: pentru cazul d):
Fie arborele din figura de mai jos la care se şterge nodul 6:
- se identifică nodul cel mai din dreapta pentru subarborele stâng (5);
- el nu este descendent direct al nodului care se şterge (6);
- informaţia sa se trece nodului şi se obţine:
- subarborele stâng al nodului care se şterge fizic este dat de nodul 4;
- acesta se leagă în dreapta tatălui nodului care se şterge fizic (3);
- se execută ştergerea fizică şi se obţine:
Ştergerea unui nod este realizată de procedura ŞTERG. Pentru situaţia în care un nod care urmează a fi şters subordonează doi arbori, se apelează procedura CMMD.
Mecanismul de transmitere al parametrilor prin referinţă face ca această procedură să fie exterm de scurtă. Astfel, căutarea nodului cel mai din dreapta pentru subarborele stâng (adresa F) se face recursiv, ce procedura a fost apelată pentru primul nod al subarborelui stâng. În situaţia în care acesta este subordonat direct nodului care se şterge, procedura nu se autoapelează, iar după transferul informaţiilor adresa subarborelui stâng (F^.AS) trece ca adresă în stînga nodului care se şterge logic. În caz contrar, datorită faptului că procedura s-a autoapelat, F^.AS trece ca adresa în dreapta pentru părintele nodului care se şterge fizic.
Întrebarea la care trebuie să răspundem în continuare este următoarea: de ce, dacă se şterge în acest mod un nod, arborele rămîne în căutare? Ştergerea unui nod se face în mod distinct pentru fiecare din cele 4 cazuri arătate. Datorită simplităţii prelucrării, primele 3 cazuri nu necesită comentarii. În cazul 4 se identifică nodul cel mai din dreapta din arborele stâng (care este cu cheia cea mai mare din aceste subarbore). Cheia acestuia trece în locul cheii nodului care se şterge. Aceasta este mai mică decât cheia iniţială (pentru că se găseşte în subarborele stâng), este în acelaşi timp cea mai mare cheie din subarborele stâng care este cea mai mică decât cheia care se şterge. Iată motivul pentru care aceasta trece în locul cheii şterge logic.
program c;
type ref=^inr;
inr=record
nr:integer;
as, ad:ref
end;
var v, man:ref;
k:integer;
opt:char;
procedure c_i (var c:ref; k:integer;);
begin
if c< >nil
then
if c^.nr=k
then
writeln (‘nr deja inserat’)
else
if c^.nr<k
then
c_i(c^.ad,k)
else
c_i(c^.as,k)
else
begin
new (c);
c^.as:=nil;
c^.ad:=nil;
c^.nr:=k
end;
end.
procedure svd (c:ref);
begin
if c< >nil then
begin
svd (c^.as);
writeln (c^.nr);
svd( c^.ad)
end;
end;
procedure cmmd (var c,f:ref);
begin
if f^.ad< >nil
then
cmmd (c,f^.ad)
else
begin
c^.nr:=f^.nr;
man:=f;
f:=f^.as;
dispose (man);
end;
end;
procedure sterg;
var f:ref;
begin
if c< >nil
then
if c^.nr=k
then
begin
if (c^.as=nil) and (c^.ad=nil)
then
begin
dispose (c);
c:=nil
end
else
if c^.as=nil
then
begin
f:=c^.ad;
dispose (c);
c:=f;
end
else
if c^.ad=nil
then
begin
f:=c^.as;
dispose (c);
c:=f;
end
else
cmmd (c, c^.as)
end
else
if c^.nr<k
then
sterg (c^.ad, k)
else
sterg (c^.as, k)
else
writeln (‘numar absent – tentativa esuata ‘)
end;
begin
v:=nil;
repeat
write (‘optiunea’);
readln (opt);
case opt of
’i’: begin
write (‘k=’); readln (k);
c_i (v, k)
’l’: svd (v);
’s’: begin
write (‘se va sterge numarul ‘); readln (k);
sterg (v, k)
end;
end {case}
until opt=’t’
end.
Teoria regăsirii informaţiei este deosebit de importantă pentru viaţa practică. Reţinem faptul că se pot crea arbori de căutare (echilibraţi) în care toate nodurile terminale se găsesc numai pe două niveluri consecutive. Aceasta conduce la o căutare rapidă (puţine operaţii).
8.2.7 Arbori oarecare
Vom defini arbori oarecare după D.E. KNUTH. Se numeşte arbore oarecare un set finit T de unul sau mai multe noduri astfel încât:
- există un nod cu destinaţie specială numit tulpina arborelui;
- celelalte noduri sunt repartizate în m≥0 seturi disjunctive T1,T2, …, Tm unde fiecare din aceste seturi la rândul său este un arbore.
Am folosit această definiţie recursivă întrucît ne este de mare folos în scrierea programului care creează un arbore oarecare.
În programul care urmează construim un arbore oarecare în care fiecărui nod i se subordonează cel mult trei subarbori.
Pentru un nod se completează informaţia utilă (un număr întreg) precum şi un vector de adrese ale subarborilor subordonaţi nodului respectiv. Am utilizat tehnica DIVIDE ET IMPERA atât la creare cât şi la parcurgere.
Fie arborele oarecare din figura de mai jos:
Pentru a crea acest arbore vom introduce informaţiile în ordinea următoare:
1 2 3 0 0 0 4 0 0 0 5 0 0 0 6 0 0 0.
Vom prezenta două dintre cele mai uzuale metode de parcurgere a arborilor oarecare:
1) Parcurgerea în adâncime (realizată de procedura padinc), în care se utilizează întâi tulpina, apoi subarborii de la stânga la dreapta (pentru arboreledin figura de mai sus avem: 1 2 3 4 5 6);
program arbg;
type ref=^inr;
vectad=array [1..3] of ref;
inr=record
nr:integer;
a:vectad
end;
var c:ref;
function arb:ref;
var c:ref;
n, i:integer;
begin
write (‘n=’); readln (n);
if n< >0
then
begin
new (c);
arb:=c;
arb^.nr:=n;
for i:=1 to 3 do arb ^.a[i]:=arb
end
else arb:=nil
end;
procedure padinc (c:ref);
var i:integer;
begin
if c< >nil then
begin
writeln (c^.nr);
for i:=1 to 3 do padinc (c^.a[i])
end
end;
begin
c:=arb;
padinc (c)
end.
2) Parcurgerea în lăţime.
În acest caz, fiecare element al listei liniare care constituie coada va fi o înregistrare care cuprinde în general două câmpuri: adresa înapoi şi informaţia utilă. Dacă variabilele de tip referinţă b şi v vor reţine adresa utimului element introdus în coadă şi adresa elementului care poate fi scos din coadă.
Lucrul cu coada se poate face utilizînd trei proceduri:
1) crearea cozii;
2) adăugarea la coadă;
3) scoaterea (prelucrarea) din coadă.
1) Crearea cozii
Această operaţie este realizată de procedura ccoada. Crearea cozii constă în:
- alocarea spaţiului pentru o înregistrare;
- completarea informaţiei utile;
- completarea informaţiei îapoi prin NIL.
2) Adăugarea la coadă
Operaţia de adăugare la coadă este realizată de procedura adcoada. Parametrii ei sunt: t (informaţia utilă) şi b (adresa ultimului element introdus în coadă). Pentru aceasta se realizează următoarele operaţii:
- alocarea spaţiului pentru noua înregistrare;
- completarea informaţiei utile;
- completarea câmpului de adresă înapoi a înregistrării de la b cu adresa noii înregistrări;
- b va lua valoarea adresei noii înregistrări.
3) Scoaterea din coadă
Această operaţie este realizată de procedura scoada. În acest sens se realizează operaţiile:
- se reţine adresa elementului care urmează a fi scos din coadă;
- se şterge înregistrarea acestui element;
- v va lua valoarea adresei înregistrării plasate înaintea celei şterse.
O aplicaţie foarte importantă a structurii de coadă este parcurgerea în lăţime a arborilor oarecare.
Pentru arborele din figura de mai sus, ordinea de parcurgere a vârfurilor este următoarea:
1 2 5 6 3 4.
În exemplul care urmează, această parcurgere este realizată de procedura tipari. Ideea de lucru este următoarea:
- se porneşte cu o coadă care conţine numai rădăcinile arborelui;
- pentru fiecare element din vârful cozii procedăm astfel:
- îl listăm;
- îi încărcăm toţi succesorii în coadă;
- algoritmul se încheie când coada este vidă.
Recomandăm cititorului analizarea cu atenţie a acestei proceduri.
program arbg;
type ref=^inr;
vectad=array [1..3]of ref;
inr=record
nr:integer;
a:vectad
end;
refl=^inr1;
inr1=record
inreg:inr;
inapoi:ref1
end;
var c:ref;
b, v:ref1;
function arb:ref;
var c:ref;
n,i:integer;
begin
write (‘n=’);
readln (n);
if n< >0
then
begin
new (c);
arb:=c;
arb^.nr:=n;
for i:=1 to 3 do arb^.a[i]:=arb
end
else arb:=nil
end;
procedure ccoada;
var d:ref1;
i:integer;
begin
new (d);
d^.inreg:=c^;
d^.inapoi:=nil;
b:=d;
v:=d
end;
procedure adcoada (t:inr; var b:ref1);
var d:ref1;
begin
new (d);
d^.inapoi:=nil;
d^.inreg:=t;
b^.inapoi:=d;
b:=d
end;
procedure scoada (var v:ref1);
var d:ref1;
begin
d:=v;
dispose (v);
v:=d^.inapoi
end;
procedure tipari (var b, v:ref1);
var d:ref;
t:inr;
i:integer;
begin
while v< >nil do
begin
writeln (v^.inreg.nr);
for i:=1 to 3 do begin
d:=v^.inreg.a[i];
if d< >nil
then
begin
t:=d^;
adcoada (t,b)
end
end;
scoada (v)
end
end;
begin
c:=arb;
ccoada;
tipari (b, v)
end.
Aplicaţie. Partiţia determinată de o relaţie de echivalenţă.
Un arbore oarecare poate fi memorat utilizînd o legătură de tip tată. Pentru aceasta este necesar un singur vector v, în care, pentru fiecare nod i, v(i) are semnificaţia de tatăl lui i. Avem v(i)=0 dacănodul lui i este vârf.
Observaţii:
- această formă de memorare este extrem de economică din punct de vedere al memoriei folosite (un nod poate avea mai multe noduri subordonate, dar numai un nod tată, deci avem o singură informaţie de adresă).
-parcurgerea arborilor reprezintanţi astfel de greoaie, fiind consumat mult timp.
Din matematică este cunoscută relaţia de echivalenţă. Aici o vom reaminti. O relaţie de echivalenţă ‘≈’ este o relaţie între elementele unei mulţimi, care satisface următoarele trei proprietăţi:
1) x≈x (reflexivitate);
2) dacă x≈y avem şi y≈x (simetrie);
3) dacă x≈y şi y≈z, atunci x≈z (tranzitivitate).
Pentru că formează o submulţime aparte a mulţimii considerate, toate elementele sunt echivalente între ele. Cum fiecare element este cel puţin echivalent cu el însuşi, înseamnă că o relaţie de echivalenţă determină pe mulţimea considerată o partiţie.
Se consideră mulţimea primilor n numere naturale {1, 2, …, n}. Se dau un număr neprecizat de perechi echivalente de forma x≈y şi se cere partiţia determinată de această relaţie de echivalenţă.
Exemplu:
Fie n=4 şi perechile 1≈3, 1≈4, 3≈4.
În acest caz relaţia 3≈4 ar putea fi dedusă dinprimele două relaţii:anume din 1≈4 rezultă 4≈1 (simetrie), iar din 4≈1 şi 1≈3 rezultă 4≈3 (tranzitivitate), deci 3≈4 (simetrie). Partiţia determinată de această relaţie de echivalenţă este {1,3,4}, {2}.
Pentru rezolvare, considerăm o pădure cu arbori oarecare, cu nodurile elemente ale mulţimii considerate, reprezintaţi într-un vector cu n, componente, utilizând legătura de tip ‘tată’.
Iniţial, fiecare element constituie un arbore aparte, deci componentele vectorului v au valoarea 0.
Aplicăm soluţia următoare: toate elementele echivalente între ele (care vor alcătui o submulţime aparte a partiţiei) formează un arbore oarecare. Deci la citirea unei perechi j≈k se pune v(j) =k (adică tatăl lui j este k). Există posibilitatea ca j să fie subordonat unui alt părinte (v(j)≠0). În această situaţie j va lua valoarea lui v(j); raţionamentul continuă pînă când v(j) va fi 0 (se ajunge la tulpina arborelui construit pentru această submulţime). În acest moment v(j) va lua valoarea lui k, ceea ce înseamnă că întreg arborele se subordonează lui k. preluăm un exemplu al lui D.E. KNUTH.
Fie n=9 şi perechile citite: 1≈5, 6≈8, 7≈2, 9≈8, 3≈7, 4≈2, 9≈3.
Iniţial vectorul v va arăta astfel:
indici 1 2 3 4 5 6 7 8 9
v 0 0 0 0 0 0 0 0 0
arbori 1 2 3 4 5 6 7 8 9
indici 1 2 3 4 5 6 7 8 9
v 5 0 0 0 0 0 0 0 0 am citit 1=5
|
arbori 2 3 4 5 6 7 8 9
indici 1 2 3 4 5 6 7 8 9
v 5 0 0 0 0 8 0 0 0 am citit 6=8
arbori 2 3 4 5 7 8 9
1 6
|
indici 1 2 3 4 5 6 7 8 9
v 5 0 0 0 0 8 2 0 0 am citit 9=8
arbori 2 3 4 5 7 8
indici 1 2 3 4 5 6 7 8 9
v 5 0 7 2 0 8 2 0 8 am citit 3=7
arbori 2 4 5 8
|
|
|
indici 1 2 3 4 5 6 7 8 9
v 5 0 7 2 0 8 2 0 8 am citit 4=2
arbori 2 5 8
|
|
|
||||||||
indici 1 2 3 4 5 6 7 8 9
|
|
v 5 0 7 2 0 8 2 3 8 am citit 8=3arbori
Se obţine partiţia {2,7,4,3,8,6,9} şi {5,1}.
Observaţie:
- Algoritmul nu înregistrează relaţii de forma j≈j sau, dacă a înregistrat j≈k, nu înregistrează k≈j. Pentru listare utilizăm procedura tipar. Precizăm faptul că, în acest algoritm nu sunt permise ca intrări informaţii redundante.
Exemplu:(1,2), (2,3), (3,1). Modificarea algoritmuui în acest sens este propusă ca exerciţiu.
program rechiv;
type vector=array [1..100] of integer;
var v:vector;
n, j, k:integer;
procedure adaug (var j, k:integer; var v:vector);
begin
while v[j]< >0 do j:=v[j];
if (j< >k) and (v[k]< >j) then v[j]:=k
end;
procedure tipar (j:integer);
var i:integer;
begin
for i:=1 to n do if v[i]=j
then
begin
if j=0 then writeln (‘——-clasa——-‘);
writeln (i);
tipar (i);
end
end;
begin
write (‘n=’); readln (n);
for j:=1 to n do v[j]:=0;
while j< >0 do
begin
write (‘j k’);
readln (j, k);
if j< >0 then adaug (j, k, v)
end;
tipar (0)
end.
Probleme propuse
1) Se citesc n numere naturale, distincte. Să se sorteze crescător, utilizînd lista liniară simplu înlănţuită, după următorul algoritm
- iniţial lista va conţine numai primul număr;
- dacă al doilea este mai mare decît primul, se va pune în coada listei, altfel va fi primul element din listă;
- orice număr se aşează în listă înaintea celui mai mic număr care este mai mare decît el (dacă există un astfel de număr), sau la sfîrşitul listei, în caz contrar.
În final, se listează conţinutul listei liniare simplu înlănţuită. (sortare prin inserţie).
2) Să se rezolve una din problemele propuse la capitolul 1 utilizînd stiva implementată dinamic.
3) Să se creeze un obiect numit LLSI – lista liniară simplu înlănţuită – care conţine numere naturale. Acesta va cuprinde metode pentru adăugarea la sfîrşitul listei, ştergerea unui element ş.a.m.d. (în general toate operaţiile care se fac cu liste liniar simplu înlănţuite).
4) Utilizînd obiectul creat la problema anterioară să se construiască un descendent al acestuia, numit NUMĂR_MARE, în care fiecare element al listei reţine o cifră între 0 şi 9 (în ansamblu o astfel de listă va reţine un număr cu mai multe cifre). Obiectul va fi înzestrat cu metode pentru citarea şi tipărirea numărului.
5) Să se scrie o procedură care poate aduna două ’’numere mari’’.
6) Să se scrie o procedură care înmulţeşte două ’’numere mari’.
7) Pentru realizarea unui curs în care se explică conţinutul a n noţiuni, se citesc p perechi de cuvinte de forma (ni, nj). Fiecare cpereche citită are semnificaţia următoare: noţiunea i foloseşte în definirea noţiunii j. Se cere să se precizeze ordinea de prezentare a noţiunilor în curs.
8) În jurul arbitrului sunt aşezaţi în cerc N jucători, numerotaţi în sens orar. Arbitrul, începînd de la jucătorul K, numără pînă la M. persoana la care sa oprit numărătoarea este eliminată din cerc. Arbitrul se poziţionează pe următoarea persoană şi repetă procedeul pînă cînd în cerc rămîne un singur jucător (L).
Să se scrie un program care:
- Citind M, N şi K, să-l determuine pe L;
- Citind M, N şi L, să-l determuine pe K.
9) Să se sorteze n numere naturale cu ajutorul arborilor de căutare.
10) Evidenţa produselor aflate în stocul unui magazin se ţine pe baza unui arbore de căutare. Pentru fiecare produs se reţine:
- denumirea;
- preţul;
- cantitatea existentă (buc.).
În fiecare seară arborele estev actualizat prin comenzi de forma:
i – se introduc produsele primite de la depozit (Atenţie! Un astfel de produs poate să mai existe în stoc);
s – se şterg produsele vândute în ziua respectivă;
De asemenea, programul acceptă şi comenzile:
v – se tipăreşte valoarea tuturor produselor aflate în stoc;
l – se tipăreşte o listă completă a produselor aflate în stoc, în ordine alfabetică. Pentru fiecare produs se va tipări şi numărul de bucăţi.
11) Problema jocurilor între doi parteneri, în care unul din jucători este calculatorul. Pentru a putea juca, calculatorul îşi construieşte un arbore corespunzător situaţiilor care pot apărea.
Pentru a exemplifica vom considera un joc simplu, numit ’GRUNDY’. Se consideră o stivă de n monede. Unul din cei doi parteneri o împarte în două părţi inegale. Celălalt partener împarte una din cele două stive de monede rămase în două părţi inegale ş.a.m.d.. Pierde acel jucător care nu mai poate face o astfel de împărţire.
Vom considera cazul n=5. În această situaţie calculatorul îşi construieşte arborele din figura de mai jos:
O primă problemă care se pune este dacă într-o anumită situaţie, presupunînd că trebuie să mute calculatorul, acesta dispune sau nu de strategie sigură de cîştig. Această problemă se poate rezolva utilizînd algoritmul MINI-MAX. Aplicarea acestui algoritm presupune următoarele:
- analiza nodurilor terminale ale arborelui, unde pot apărea două situaţii:
- trebuie să mute calculatorul, caz în care nodul se etichetează cu 0;
- trebuie să mute partenerul uman, caz în care nodul se etichetează cu 1;
- analiza nodurilor neterminale ale arborelui, unde apar din nou două situaţii:
- mută calculatorul, situaţie în care nodul se etichetează cu maximul dintre etichetele nodurilor subordonate acestuia;
- mută partenerul uman, situaţie în care nodul se etichetează cu minimul dintre etichetele nodurilor subordonate acestuia.
Acest mod de etichetare îşi găseşte explicaţia în faptul că, la mutarea efectuată de calculator, acesta va alege o mutare convenabilă (se va duce într-un nod etichetat cu 1), iar la mutarea efectuată de partenerul uman se presupune că acesta va alege o mutare convenabilă lui (va face o mutare care îl va duce într-un nod etichetat 0).
Scrieţi un program cu ajutorul căruia calculatorul va juca Grundy cu dumneavoastră.
