curs algoritmi si structuri de date
TRANSCRIPT
Algritmi şi Structuri de Date
Note de curs
1
1. ALGORITMI ŞI MODURI DE REPREZENTARE
Prelucrarea datelor cu ajutorul calculatorului se realizează prin execuţia
unor operaţii simple (aritmetice, logice, pe iruri de caractere etc.). Înlănţuirea
acestora poate conduce la prelucrări deosebit de complexe. Această înlănţuire
nu este făcută la întîmplare, ci în conformitate cu reguli definite riguros, adică
în conformitate cu algoritmul de prelucrare sau de rezolvare a problemei.
Nu există o definiţie unanim acceptată a noţiunii de algoritm. În mod
intuitiv, un algoritm este o mulţime de operaţii cunoscute (aritmetice, logice
etc.), care executate într-o ordine bine stabilită, pornind de la o mulţime de
valori (numită intrarea algoritmului) care fac parte dintr-o mulţime de astfel de
mulţimi (numită domeniul de definiţie al algoritmului), produc în timp finit un o
altă mulţime de valori numită ieşirea algoritmului.
Pentru a analiza proprietăţile algoritmilor vom prezenta doi algoritmi
cunoscuţi:
determinarea celui mai mare divizor comun a două numere naturale nenule
(algoritmul lui Euclid);
rezolvarea aproximativă a ecuaţiilor algebrice şi transcendente prin metoda
înjumătăţirii intervalului.
Algoritmul lui Euclid
A determina cel mai mare divizor comun a două numere naturale nenule,
notate m şi n, înseamnă a găsi cel mai mare număr natural care divide numerele
date. Algoritmul lui Euclid de determinare a cmmdc constă în următoarea
secvenţă de operaţii:
(E1) Împarte m la n şi fie restul r
(E2) Dacă r=0 treci la (E6)
(E3) Notează cu m valoarea lui n (sau atribuie lui m valoarea n)
(E4) Notează cu n valoarea lui r (sau atribuie lui n valoarea r)
(E5) Treci la (E1)
(E6) Cel mai mare divizor comun este n (afişează cmmdc este n)
(E8) Stop
Rezolvarea ecuaţiilor algebrice şi transcendente prin metoda înjumătăţirii
intervalului
Fie Rb][a,:f o funcţie reală de o variabilă reală, continuă pe [a,b], cu
f(a)*f(b)<0 şi care are pe intervalul [a,b] exact o rădăcină. Ne propunem să
determinăm rădăcina ecuaţiei cu o precizie dată e. Rezolvarea ecuaţiei se
realizează conform următoarelor reguli
2
(I1) Fie c mijlocul intervalului [a,b], adică2
b) + (a:=c ;
(I2) Dacă f(c)=0 treci la (I10)
(I3) Dacă |a-b| e treci la (I9)
(I4) Dacă f(a)*f(c) < 0, treci la (I7)
(I5) Atribuie lui a valoarea lui c
(I6) Treci la (I1)
(I7) Atribuie lui b valoarea lui c
(I8) Treci la (I1)
(I9) Atribuie lui c valoarea lui b
(I10) Afişează ‘Radacina ecuatiei este’, c
(I11) Stop
Proprietăţile algoritmilor
Analizînd cei doi algoritmi constatăm că:
algoritmii rezolvă problemele unei clase de probleme: algoritmul lui
Euclid este aplicabil oricărei perechi de numere naturale nenule, iar
algoritmul de rezolvare a ecuaţiilor algebrice şi transcendente prin
înjumătăţirea intervalului este aplicabil oricărei funcţii f care satisface
condiţiile problemei şi orice eroare de aproximare e. Prin urmare, ei au
caracter general. Din acest motiv, algoritmii debutează cu precizarea
datelor iniţiale (sau citirea datelor iniţiale);
secvenţele de operaţii descrise mai sus se încheie după un număr finit de
operaţii. Prima se încheie pentru că şirul resturilor formează un şir de
numere naturale strict descrescător (restul fiind mai mic decît
împărţitorul). A doua secvenţă se termină după un număr finit de operaţii,
fiindcă lungimile intervalelor [a,b] formează un şir strict descrescător de
numere pozitive convergent la zero (la a n-a aplicare a operaţiei de
înjumătăţire, lungimea intervalului este 2
|a-b|n
), deci pentru un n
suficient de mare lungimea sa va fi mai mică decît e. Pentru acest n, orice
punct din intervalul [a,b] poate fi considerat rădăcină a ecuaţiei.
Prin urmare algoritmii au un caracter finit ;
operaţiile care alcătuiesc algoritmii se execută riguros şi fără ambiguităţi.
Prin urmare, pornind de la aceleaşi date de intrare se obţin aceleaşi date
de ieşire, deci algoritmii au un caracter de unicitate.
3
În practică se doresc algoritmi buni, dar noţiunea de algoritm bun este
definită vag. Uneori se doresc algoritmi care să conducă la programe de
dimensiuni reduse, alteori la programe simple şi elegante, alteori la
programe care furnizeze soluţia în timp cît mai scurt, alteori la algoritmi
care sînt adaptabili mai multor tipuri de calculatoare etc.
Numim pas al unui algoritm o succesiune de operaţii de acelaşi tip. Vom
conveni că, un pas nu poate conţine două sau mai multe operaţii de decizie sau
de trimitere. În cele două exemple, operaţiile identificate prin (E1)-(E7) şi (I1)-
(I11) sînt exemple de paşi. Operaţiile identificate prin (E3) şi (E4) pot fi reunite
într-un singur pas.
Pentru reprezentarea algoritmilor se pot utiliza mai multe procedee:
în cuvinte (ca mai sus);
cu ajutorul schemelor logice;
cu ajutorul limbajelor specializate (pseudocoduri);
direct într-un limbaj de programare.
LIMBAJUL PSEUDOCOD
Reprezentarea alogritmilor cu ajutorul limbajelor specializate se impune
cel puţin din următoarele motive:
descrierea algoritmilor în cuvinte este nepotrivită datorită ambiguităţii
limbajului natural (un cuvînt putînd avea mai multe sensuri);
dificultăţi legate de reprezentarea grafică prin scheme logice (algoritmi
relativ simpli se reprezintă prin scheme mari);
lipsesc comentariile explicative privind semnificaţia diferitelor variabile,
secvenţe de instrucţiuni etc.;
citirea unei scheme logice este greoaie;
majoritatea limbajelor de programare dispun de instrucţiuni puternice
care ţin locul mai multor operaţii elementare descrise în mai mulţi paşi ai
algoritmului (vezi instrucţiunea for, Do .. Until etc.).
Un identificator este o secvenţă de unul sau mai multe caractere, litere şi
cifre, primul caractere fiind obligatoriu literă. Literele mici sînt echivalente cu
literele mari.
Identificatorii se împart în două grupe mari:
cuvinte cheie (cuvinte rezervate care reprezintă nume de instrucţiuni sau
ale unor părţi din instrucţiuni; de exemplu If, then, else) ;
4
definiţi de utilizator (proiectant) pentru a desemna nume de variabilă,
procedură sau funcţie.
Vom prezenta în continuare un pseudocod care utilizează cuvinte cheie în
limba engleză, chiar dacă efortul necesar însuşirii lui este în faza iniţială mai
mare.
Adoptăm următoarele convenţii de scriere:
cuvintele cheie vor fi scrise cu litere italice (inclinate);
un element cuprins între [] este opţional (sintaxa nu impune prezenţa sa);
o mulţime de elemente dispuse unul sub altul şi incluse între {} indică o
alegere: din acea mulţime se va alege un singur element.
Instrucţiunile se împart în:
comentarii explicative;
instrucţiuni de descriere sau de declarare a variabilelor;
instrucţiuni executabile.
Comentariile sînt texte în care se explică rolul diferitelor secvenţe de
program, semnificaţia unor elemente, metoda utilizată, numele proiectantului
(programatorului), data şi autorul unor modificări aduse algoritmului etc. Se pot
întîlni oriunde în text, dar nu pot împărţi în două sau mai multe părţi un
identificator sau o constantă. Ele încep cu /* şi se încheie cu */.
Exemplu:
/* rezolvarea ecuatiilor algebrice si transcendente prin metoda
injumatatirii intervalului */
Succesiunea int/*20.03.1998*/eger m; este incorectă.
Orice instrucţiune de declarare sau executabilă se încheie cu ; (caracterul
punct şi virgulă). Sintaxa limbajului este liberă: o instrucţiune se poate întinde
pe mai multe rînduri, iar un rînd poate conţine mai multe instrucţiuni.
Variabila este o mărime (dată) care îşi poate modifica valoarea în timpul
execuţiei programului. Are asociat un nume prin intermediul căruia se fac
referiri la valoarea ei. După conţinutul pe care îl pot avea, variabilele sînt de tip
numeric (care la rîndul lor se împart în variabile de tip întreg şi de tip real), de
tip logic şi caracter.
Constantele sînt mărimi care nu îşi modifică şi nici nu-şi pot modifica
valoarea în timpul prelucrărilor. Ele se recunosc după forma lor: o constantă de
tip întreg se reprezintă printr-un număr cu sau fără semn (de exemplu -1, 2), o
constantă reală printr-un număr real cu sau fără semn (virgula zecimală este
caracterul punct), constantele logice sînt true şi false, iar un caracter sau un şir
5 ; ariabilelista_de_v
char
bool
real
integer
de caractere se reprezintă între apostrofuri sau între ghilimele. Dacă şirul este
delimitat prin apostrof şi conţine caracterul apostrof, acesta se va dubla, de
exemplu ‘intr ‘ ‘ o zi de sarbatoare ‘. Dacă şirul este delimitat prin ghilimele şi
conţine caracterul ghilimele acestea se vor dubla (de exemplu ;,. <> ).
Cu datele de tip numeric se pot efectua următoarele operaţii:
+ şi - operatori unari de precizare a semnului
+ adunare - scădere
* înmulţire / împărţire
^ ridicare la putere.
Dacă mărimile a şi b sînt de tip întreg, rezultatul împărţirii a/b este de tip
întreg (este cîtul împărţirii întregi).
Notăm cu [] funcţia parte întreagă, cu sqrt funcţia radical, cu sin, cos etc.
funcţiile trigonometrice cunoscute.
Datele de tip logic pot fi operanzi ai următoarelor operaţii logice:
negaţia (NOT);
conjucţia logică sau AND ( ŞI logic);
disjuncţia (OR, SAU LOGIC).
Datele de tip şir de caractere pot fi operanzi ai operaţiilor de concatenare
(notată +). Dacă a are valoarea ‘Astazi este ‘, iar b valoarea ‘Joi ‘, expresia
a+b are valoarea ‘Astazi este Joi ‘.
Expresiile de tip numeric şi cele de tip şir de caractere pot interveni în
expresii de relaţie. Se pot folosi următorii operatori de relaţie:
< (mai mic);
> (mai mare);
# (diferit);
= (egalitate);
<= (mai mic sau egal);
>= (mai mare sau egal).
Aceştia au semnificaţiile cunoscute. Două şiruri de caractere se compară
caracter cu caracter. Dacă c şi c ‘ sînt două caractere, c<c ‘ dacă în tabelul de
codificare ASCII c este în faţa lui c ‘ (cu alte cuvinte codul ASCII zecimal al lui
c este mai mic decît codul ASCII zecimal al lui c ‘).
Priorităţile şi regulile de asociere sînt cele cunoscute de la matematică.
Instrucţiunile de declarare precizează tipul şi modul de organizare a
variabilelor. Ele au sintaxa
6
expresie; = : _tablou element_de
variabila
Folosim cuvîntul cheie integer pentru a declara variabile care au valori
numere întregi, real pentru a declara variabile care au valori numere reale, bool
pentru a declara variabile de tip logic sau boolean (care au valoarea true -
adevărat sau false - fals), respectiv char pentru a declara variabile care au ca
valoare un caracter. Elementele listei de variabile se separă prin virgulă.
Exemple Instrucţiunile
integer m,n;
real x;
declară variabilele m şi n de tip întreg, iar variabila x de tip real.
Pentru a declara tablouri (matrici) cu una sau mai multe dimensiuni
folosim instrucţiunea array care are sintaxa
array listă_de_tablouri;
Elementele listei de tablouri se separă prin virgulă. Numele tabloului este urmat
de o listă de expresii de tip întreg care definesc valorile indicilor maximali pe
fiecare dimensiune. Lista de indici este cuprinsă între paranteze rotunde.
Prin array a(100); variabila a se declară vector de 100 de elemente.
Toate elementele unui vector au acelaşi tip (integer, real, bool sau char), iar
indicii încep să varieze de la 1. În locul a două instrucţiuni de declarare (de tip
şi organizare în tablou) putem folosi o singură instrucţiune. De exemplu, în
locul instrucţiunilor
integer a;
array a(100);
putem folosi instrucţiunea
integer a(100);
În expresii, un element de tablou este identificat prin numele tabloului şi
valorile indicilor săi. De exemplu, a(i) este elementul cu indicele i al vectorului
a, iar m(i,j) este elementul situat în linia i şi coloana j a matricii m.
Instrucţiuni executabile
instrucţiunea de atribuire are forma
7
Execuţia ei presupune evaluarea expresiei din mebrul drept, conversia
acesteia la tipul variabilei sau al elementului de tablou şi atribuirea
acestuia ca valoare nouă variabilei sau elementului de tablou.
De exemplu, instrucţiunea a:=1; atribuie variabilei a valoarea 1,
iar în instrucţiunea delta:=b^2_4*a*c; variabilei delta i se asociază
valoarea b*b-4*a*c.
instrucţiunea de citire (de introducere a datelor de la tastatură) are sintaxa
read lista_de_variabile_sau_elemente_de_tablou;
De exemplu, instrucţiunea
read m,n,a(i);
citeşte valorile variabilelor m şi n şi a elementului cu indicele i al
vectorului a.
instrucţiunea de scriere (afişare pe monitor) are sintaxa
Write lista_de_expresii;
De exemplu, instrucţiunea
write ‘Cel mai mare divizor comun este ‘,n;
afişează textul Cel mai mare divizor comun este şi valoarea pe care o are
variabila n.
Definiţie. Numim secvenţă de instrucţiuni o succesiune de instrucţiuni
executabile complete.
instrucţiunea de ramificare IF THEN ELSE are două forme:
if P then
Secvenţă_de_instrucţiuni_1
endif;
sau
if P then
Secvenţă_de_instrucţiuni_1
else
Secvenţă_de_instrucţiuni_2
endif;
În prima formă, se evaluează expresia logică P. Dacă este adevărată, se
execută secvenţa secvenţă_de_instrucţiuni_1. După execuţia acesteia sau
dacă P este falsă se trece la instrucţiunea următoare. În forma a doua, se
evaluează expresia logică P: dacă este adevărată se execută
secventă_de_instrucţiuni_1, altfel (dacă este falsă) se execută
secventă_de_instrucţiuni_2. Se trece la instrucţiune următoare.
Exemplu
8
if delta<0 then
Write ‘Ecuatia are radacini complexe’;
else
Write ‘Ecuatia are radacini reale ';
endif;
sau
if x>maxim then
Maxim:=x;
endif;
instrucţiunea repetitivă sau bucla While are sintaxa:
While p:
secventă_de_instructiuni
repeat;
Efectul său este:
1. Se evaluează expresia logică p;
2. Dacă este falsă se trece la instrucţiunea următoare (de după
repeat)
3. Se execută secvenţă_de_instrucţiuni;
4. Se reia de la 1.
Sau, altfel spus, atît timp cît p este adevărată se execută
secvenţă_de_instrucţiuni. Dacă p este iniţial falsă, secvenţa nu se execută
nici o dată.
Exemplu:
Să se calculeze suma elementelor unui vector x cu n elemente.
i:=1; s:=0;
s:=s+x(i);
i:=i+1;
repeat;
instrucţiunea repetitivă DO .. UNTIL are sintaxa
do
Secvenţă_de_instrucţiuni
until p;
Este echivalentă cu următoarea secvenţă:
secvenţă_de_instrucţiuni
while ךp
Secvenţă_de_instrucţiuni;
repeat;
9
în care ךp este negata expresiei logice p.
Exemplu. Afişaţi textul Nr de elemente şi citiţi valoarea variabilei n pînă
cînd aceasta devine strict pozitivă şi mai mică sau egală cu 100.
Do
write ‘Nr de elemente’;
read n;
<=100;
ciclul cu un contor sau instrucţiunea FOR are sintaxa
for v:=E1,E2 [ ,E3]:
secvenţă_de_instrucţiuni
repeat;
V este o variabilă numerică numită contor, iar E1, E2 şi E3 expresii
numerice numite valoare iniţială, valoare finală, respectiv pas. Dacă E3
lipseşte, se consideră egală cu 1.
Instrucţiunea for este echivalentă cu următoarele instrucţiuni:
v:=E1; v2:=E2; v3:=E3;
while(v - v2)*v3 0:
secvenţă_de_instrucţiuni
v:=v+v3;
repeat;
Exemplu.
Să se determine cel mai mic element al unui vector cu n elemente
de tip întreg.
Integer minim,n, i;
/* citeste numarul de elemente (un numar intreg si pozitiv) */
do
write ‘Dimensiunea vectorului =’;
read n;
until n 0;
/* declara vectorul si citeste elementele sale */
integer v(n);
for i:=1,n:
10
write ‘v(‘,i,’)=’;
read v(i);
repeat;
/* determina minimul */
minim:=v(1);
for i:=2,n:
if minim<v(i) then
Minim:=v(i);
endif;
repeat;
/* afiseaza rezultatul */
write ‘Cel mai mic element al vectorului este ‘, minim;
instrucţiunea exit are ca efect abandonarea celei mai interioare bucle
while, for, do ..until care o conţine (indiferent dacă este sau nu îndeplinită
condiţia de continuare a buclei). Are sintaxa
exit;
Exemplu.
Un şir de n numere întregi are elementele dispuse în ordine
crescătoare. Verificaţi dacă o valoare x face parte din şir.
/* presupunem că toate datele sînt citite */
for i:=1,n:
if x=v(i) then
Exit;
endif;
repeat;
write ‘Face parte din sir’;
else
write ‘Nu face parte din sir ‘;
endif;
instrucţiunea cycle provoacă trecerea la sfîrşitul celei mai interioare bucle
while, for, do ...until care o conţine. Bucla este reluată dacă sînt
îndeplinite condiţiile de reluare.
Sintaxa instrucţiunii este
cycle ;
Exemplu.
11
Determinaţi media aritmetică a elementelor nenule ale unui vector
cu n elemente de tip întreg.
/* presupunem ca datele sint citite */
suma:=0; /* suma elementelor nenule */
nr:=0; /* numarul elementelor nenule */
for i:=1,n:
if v(i)=0 then
Cycle;
endif;
suma:=suma+v(i);
nr:=nr+1;
repeat;
if nr=0 then
write ‘Vectorul nu contine elemente nenule ;
else
write ‘Media aritmetica a elementelor nenule este ‘, suma/nr;
instrucţiunea stop - marchează sfîrşitul execuţiei programului. Sintaxa ei
este
stop;
12
PROGRAME, PROCEDURI ŞI FUNCţII
Un program corespunde unui algoritm. Este alcătuit din una sau mai
multe proceduri (deci procedura ar corespunde unui subalgoritm). O procedură
începe cu o instrucţiune de declarare de procedură (excepţie face, eventual,
prima procedură) care are forma:
procedure nume_procedura[(Lista_de_parametri_formali)};
Se continuă cu instrucţiunile de declarare a parametrilor p1,p2 etc., cu
declararea variabilelor locale şi cu instrucţiunile executabile.
Se încheie cu instrucţiunea end care marchează sfîrşitul fizic al
procedurii.
Numele procedurii este un identificator (care nu poate fi un cuvînt cheie
sau numele unei variabile).
Execuţia unui program începe cu execuţia primei instrucţiuni executabile
a primei proceduri. O procedură poate apela o altă procedură. Dacă procedura p
are declaraţia
procedure proc(p1,p2,...pn);
apelul său se realizează printr-o instrucţiune de forma
call proc(a1,a2,...,an);
Parametrii p1,p2,...,pn se numesc parametri formali, iar a1,a2,... ,an se
numesc parametri actuali sau parametri efectivi sau parametri reali.
Corespondenţa dintre parametrii formali şi actuali se realizează prin poziţie
(valoarea lui a1 este atribuită ca valoare iniţială lui p1 etc.).
Revenirea în procedura apelantă are loc la întîlnirea (în procedura
apelată) a instrucţiunii return.
Exemplu
Elaboraţi un algoritm pentru determinarea celui mai mare divizor comun
a n numere naturale nenule.
procedure cmdc;
integer n,i;
do
write ‘Numar de elemente’;
read n;
until n 0;
integer a(n);
13
)];ri_formalide_parametie[(lista_nume_funct function
char
bool
real
integer
for i:=1,n:
do
Write ‘a(‘,i,’)=’;
Read a(i);
until a(i) 0;
repeat;
integer c,c1; /* cel mai mare divizor comun */
c:=a(1);
for i:=2,n:
call Euclid(c,a(i),c1);
c:=c1;
repeat;
write ‘Cmmdc este ‘,c;
stop;
end;
procedure Euclid(m,n,r); /*declararea procedurii */
integer m,n, /* cele două numere */
r; /* in final va contine cel mai mare divizor comun */
do
r:=m-n*[m/n];
m:=n;
n:=r;
until r=0;
r:=n;
return;
end; /*Euclid */
Ca şi procedurile, funcţiile sînt alcătuite dintr-o instrucţiune de declarare
a funcţiei, de forma:
din declaraţii ale parametrilor formali şi a variabilelor locale, din instrucţiuni
executabile, şi o instrucţiune de atribuire prin care numele funcţiei primeşte ca
14
valoare rezultatul întors de funcţie. Instrucţiunea end indică sfîrşitul fizic al
funcţiei (după end funcţia nu mai are instrucţiuni).
Apelul funcţiei constă în utilizarea în expresii a numelui funcţiei urmat
(cînd este cazul) de lista parametrilor actuali cuprinsă între paranteze rotunde.
Ca şi în cazul procedurilor, corespondenţa dintre parametrii formali şi cei
actuali se realizează prin poziţie.
Iată cum ar arăta algoritmul precedent, cu subalgoritmul Euclid implementat ca
funcţie:
procedure ccmdc;
integer n,i;
do write ‘Numar de elemente’; read n; until n 0;
integer a(n);
for i:=1,n:
do
Write ‘a(‘,i,’)=’;
Read a(i);
until a(i) 0;
repeat;
integer c; /* cel mai mare divizor comun */
c:=a(1);
for i:=2,n:
c:=Euclid(c,a(i));
repeat;
write ‘Cmmdc este ‘,c;
stop;
end;
integer function Euclid(m,n); /*declararea procedurii */
integer m,n; /* cele două numere */
integer r; /* restul impartirii */
do r:=m-n*[m/n]; m:=n; n:=r; until r=0;
Euclid:=n;
end; /*Euclid */
În cazul unor probleme de matematică (şi nu numai) anumite elemente
(mărimi) se calculează utilizînd o relaţie de recurenţă. De exemplu, funcţia
factorial se defineşte după cum urmează
15
1>n ,1)!-(n*n
1=n 1,
0=n 1,
= n!
Limbajul pseudocod permite scrierea de funcţii recursive.Condiţia
impusă este ca să fie îndeplinită o condiţie de consistenţă: o valoare a funcţiei
trebuie să fie o valoare dată sau o valoare calculabilă pe baza valorilor date. În
cazul nostru, valorile date pentru factorial sînt valorile pentru n=0 şi n=1.
Celelalte valori ale funcţiei se pot calcula ţinînd seama de aceste valori şi
formula de recurenţă.
Funcţia factorial se poate defini recursiv astfel:
integer function factorial (n);
integer n;
if n<2 then
factorial:=1;
else
factorial:=n*factorial(n-1);
endif;
end; /* factorial */
Funcţia Euclid se poate rescrie recursiv astfel
integer function Euclid(m,n);
integer m,n;
if n=0 then
Euclid:=m;
else
Euclid:=Euclid(n,m-n*[m/n]);
endif;
end; /* Euclid */
Pentru determinarea rădăcinii ecuaţiilor algebrice şi transcendente prin
metoda înjumătăţirii intervalului se poate folosi urmatorul algoritm
real function Biparti(f,a,b,e);
real a,b,e,c;
c:=(a+b)/2;
if |b-a|<e or f(c)=0 then
Biparti:=c;
16
else
if f(c)*f(a)<0 then
Biparti:=Biparti(f,a,c,e);
else
Biparti:=Biparti(f,c,b,e);
endif;
endif;
end ; /* Biparti */
17
LIMBAJE DE PROGRAMARE
Utilizatorul şi calculatorul comunică prin intermediul comenzilor
sistemului de operare pe care le introduce, în general, de la perifericul standard
de intrare (tastatura) şi prin intermediul unor secvenţe de instrucţiuni reunite sub
formă de programe. În ultimul caz, utilizatorul specialist (programatorul)
foloseşte un limbaj intermediar între limbajul natural şi limbajul calculatorului:
limbajul de programare.
Deşi evoluţia limbajelor de programare este strîns legată de evoluţia
sistemelor de calcul, se constată o tendinţă de apropiere a limbajului de
programare de limbajul natural.
Primele calculatoare au fost programate în limbajul calculatorului (cod
maşină). Sarcina utilizatorului în această etapă a fost deosebit de grea:
programele erau secvenţe de numere binare (programatorul acţiona
butoane sau comutatoare cu două stări);
programele aveau dimensiuni mici, prelucrările erau foarte simple şi
puternic dependente de tipul de calculator utilizat ;
programatorul trebuia să cunoască semnificaţia tuturor regiştrilor
calculatorului.
Odată cu evoluţia calculatoarelor şi creşterea nevoii de prelucrări
complexe, la începutul anilor ‘50, se trece la programarea simbolică.
Limbajele de programare simbolice îi uşurează munca programatorului sub
două aspecte:
instrucţiunile sînt scrise într-o formă intermediară între limbajul
calculatorului şi limbajul natural ;
programatorul nu este obligat să cunoască în amănunt semnificaţiile
diferiţilor regiştri ai calculatorului, el putîndu-se concentra asupra
algoritmului de prelucrare.
În anul 1950, un grup de cercetători ai firmei IBM conduşi de John W.
Backus proiectează limbajul de programare FORTRAN (FORmula
TRANslation) destinat calculelor numerice de natură tehnico-ştiinţifică.
Implementat pe diferite tipuri de calculatoare, el suferă mai multe transformări
concretizate în versiuni diferite ale limbajului: FORTRAN IV, FORTRAN 77,
FORTRAN 80 etc.
Zece ani mai tîrziu, un grup de cercetători coordonat de Peter Naur
definesc limbajul ALGOL - 60 (ALGOritmic Language). Acesta se remarcă
18
prin precizia definiţiilor şi prin completa formalizare a sintaxei (regulilor de
scriere). Deşi a avut o utilizare relativ restrînsă, limbajul devine un model
pentru proiectanţii de limbaje de programare.
În 1970, Nicolaus Wirth defineşte limbajul PASCAL. Continuator al
ALGOL-ului, el se remarcă prin simplitate şi claritate. De-a lungul vremii,
diferitele variante ale limbajului pornesc de la limbajul standard PASCAL
definit de Wirth în 1974. Datorită calităţilor sale, este foarte răspîndit în mediile
de învăţămînt.
COBOL - Common Business Oriented Language - fost definit în 1968,
apoi redefinit în 1974 de către ANSI (American National Standards Institute).
Este destinat prelucrărilor cu caracter economic care vehiculează volume mari
de date organizate în fişiere de organizare secvenţială, secvenţial indexată şi
selectivă. Deoarece este capabil să efectueze calcule exacte cu numere mari, se
pretează la proiectarea aplicaţiilor de gestiune economică. Implementarea unei
instrucţiuni de sortare cu posibilităţi de prelucrare iniţială (înainte de sortare) şi
finală (după sortare), prezenţa generatorului de rapoarte fac ca la nivelul anilor
1989, 60-70% din codul aplicaţiilor noi să se scrie în COBOL. Faptul că datele
sînt descrise într-o secţiune separată, la fel de importantă ca partea de
prelucrare, au o influenţă pozitivă asupra altor limbaje de programare.
Limbajul C este un limbaj de programare general care face economie în
scrierea expresiilor, se caracterizează printr-un control modern al fluxului de
prelucrare şi o mare varietate de operatori. Nu este un limbaj de programare de
nivel foarte înalt şi nu este specializat pe anumite tipuri de aplicaţii. El a fost
proiectat şi implementat de către Denis Ritchie pe un calculator DEC PDP 11
înzestrat cu un sistem de operare UNIX. Operaţiile de intrare/ieşire (puternic
dependente de echipament) nu sînt implementate sub formă de instrucţiuni, ci
sub formă de funcţii de bibliotecă, astfel că programele scrise în C au înalt grad
de portabilitate. La ora actuală aproape pe toate tipurile de calculator există
implementată o variantă de C. Cea mai mare parte a componentelor sistemelor
de operare sînt scrise în C, ceea ce îl face foarte apropiat de sistemul de operare,
dar şi faţă de sistemul de calcul.
LIMBAJUL PASCAL
VOCABULARUL
În scrierea programelor PASCAL se utilizează :
19
caractere alfabetice: literele mari şi mici ale alfabetului englez şi liniuţa de
subliniere;
caractere numerice: cifrele sistemului de numeraţie zecimal;
caractere punctuaţie şi speciale:
= - \ _ & spaţiu (blanc)
Numim identificator o succesiune de litere şi cifre care începe cu o literă
şi identifică o instrucţiune, o parte a sa, un tip de dată, o variabilă, un nume de
program, o constantă, o procedură sau funcţie. Lungimea acestuia depinde de
implementarea limbajului. O parte a acestora sînt predefiniţi (sînt identificatori
standard), iar o alta sînt definiţi de către programator. O parte a
identificatorilor standard pot fi redefiniţi (de exemplu readln). Cuvintele cheie
sînt identificatori care nu pot fi redefiniţi. Cuvintele cheie (BORLAND Pascal
versiunea 7) sînt:
And
Asm
Array
Begin
Case
Const
Constructor
Destructor
Div
Do
Downto
Else
End
Exports
File
For
Function
GoTo
If
Implementation
In
Inherited
Inline
Interface
Label
Library
Mod
Nil
Not
Object
Of
Or
Packed
Procedure
Program
Record
Repeat
Set
Shl
Shr
String
Then
To
Type
Unit
Until
Uses
Var
While
With
Xor.
PROGRAME PASCAL
Într-o primă aproximare, un program PASCAL este alcătuit dintr-un antet
(în care se precizează numele programului şi unităţilor - unit-urilor folosite) şi
un bloc alcătuit din instrucţiuni de declarare (a variabilelor, constantelor,
funcţiilor etc.) şi instrucţiuni executabile.
20
Comentariile explicative pot să apară oriunde în textul programului cu
condiţia să nu despartă un identificator sau o constantă. Ele încep cu (* şi se
încheie cu *), sau încep cu { şi se încheie cu }. Între caracterele delimitatoare se
poate insera orice text.
Exemplu de program Pascal
(* antetul *)
program afiseaza; { numele programului este afiseaza }
uses crt; { se foloseşte unitatea Crt }
(*declarari de variabile *)
const n=10; { n este constanta 10 }
var x: real; { variabila x este de tip Real }
i: integer; { variabila i este de tip Integer }
a: array [1..n] of real; { a este un vector cu n componente de tip
Real }
(*instructiuni executabile *)
begin
for i:=1 to n do { citeste elementele vectorului }
Begin
{ afiseaza numele elementului care se citeste }
Write( ‘a( ‘,i, ‘)= ‘);
Readln(a[i]) { citeste valoarea elementului }
End;
write( ‘Valoare cautata ‘); { citeste valoarea variabilei x }
readln(x);
for i:=1 to n do { compara valoarea lui x cu a elementelor
vectorului }
If a[i]=x then break; { daca este egala cu una, incheie
cautarea }
if i>n then {Daca i>n, valaarea x nu este luata de elem lui
a}
Writeln( ‘Nu este printre elementele date ‘);
else
Writeln( ‘Este printre elementele date ‘);
(* sfirsit program *)
end.
21
CONSTANTE ŞI VARIABILE
Reamintim că o constantă este o dată care nu-şi poate schimba valoarea în
timpul execuţiei programului. Ele se pot reprezenta explicit sau li se poate
asocia un nume (constante simbolice). Această asociere se face în partea
declarativă a programului folosind o construcţie de tipul:
const nume_constantă_1=valoare-1;
[nume_constantă_2=valoare_1;]...
Valoare_1, valoare_2 etc. pot fi constante în accepţiune uzuală sau pot fi
expresii constante (care pot fi evaluate în momentul compilării textului
programului).
Constantele pot fi de tip
întreg
zecimal - valoarea lor este un număr întreg cu sau fără semn
cuprins în intervalul -2147483648 .. 2147483647. De exemplu, -1
750 300 sînt constante de tip întreg;
hexazecimal - valoarea lor se exprimă printr-un şir cifre ale
sistemului de numeraţie hexazecimal precedat de caracterul $) şi
este cuprinsă între $00000000 şi $FFFFFFFF. De exemplu, $12
$400 sînt constante de tip întreg în reprezentare hexazecimală;
real se exprimă printr-un număr real cu sau fără semn) de forma
[semn][cifre].[cifre]
[semn][cifre].[cifre]E[semn]cifre
Prima formă este numită formă normală, iar a doua formă
exponenţială sau ştiinţifică. În aceste scrieri, semn este semnul
numărului real (+ sau -), cifre o succesiune de cifre zecimale,
caracterul . (punct) este virgula zecimală. Succesiunile de cifre din
faţa virgulei şi de după virgulă pot lipsi, dar nu simultan. Valoarea
constantelor exponenţiale se poate obţine înmulţind numărul real
situat în faţa lui E cu 10 ridicat la puterea dată de numărul întreg ce
este scris după E.
Exemple 10. .5 -10.7 6. E2 Valoarea ultimei constante este
600. (6. înmulţit cu 10 la puterea a doua).
22
boolean (logic) se reprezintă prin valorile true (pentru adevărat) şi false
(pentru fals).
şir de caractere care încep şi se încheie cu ‘. Dacă şirul conţine un
caractert apostrof, acesta se dublează. Pentru a reprezenta
constante de tip caracter corespunzătoare unor caractere speciale şi
de control se folosesc expresii de tipul #cod sau ^c , unde cod este
codul ASCII zecimal al caracterului ce trebuie reprezentat, iar c
caracterul ce se tastează simultan cu CTRL pentru a obţine
caracterul dorit. De exemplu #10 sau ^J pentru caracterul LF, #12
sau ^L pentru FF etc.
Exemple:
const n=10;
k=2*n;
j=1.5;
esc=$1b;
constat= ‘O linie ‘#13#10'Continuarea ei pe linia urmatoare ‘;
da=true;
Există şi constante predefinite MaxInt=32767 (care este cea mai mare
valoare întreagă cu semn), MaxLongInt= 2147483647 pentru cea mai mare
valoare reprezentabilă ca LongInt etc.
Variabilele sînt mărimi ale căror valoare se poate modifica în timpul
execuţiei programului. Ele au asociat un nume (care este un identificator) prin
intermediul căruia le putem referi. Valorile pe care le poate lua o variabilă şi
operaţiile permise asupra lor depind de tipul variabilei care nu poate fi modificat
şi care se declară prin construcţii de forma:
nume_de_variabila_11[,nume_de_variabila_12 ]... :
tip_de_data_1;
[nume_de_variabila_21[,nume_de_variabila_22] ... :
tip_de_data_2;]...
DATE DE TIP NUMERIC
23
Variabilele şi constantele cu tip numeric de bază sînt Integer şi Real şi
corespund reprezentărilor interne în virgulă fixă , respectiv virgulă flotantă (sau
mobilă). Alături de acestea se pot folosi şi următoarele tipuri: Byte, Shortint,
Word, Longint, Comp (care se reprezintă în virgulă fixă) şi Single, Double şi
Extended (care se reprezintă în virgulă flotantă).
Lungimile zonei de memorie necesare şi valorile maxime şi e pe care le
pot lua datele variază în funcţie de tipul lor şi depind de funcţie de tipul lor şi
depind de calculatorul folosit. În cazul calculatoarelor personale compatibile
IBM PC (Borland PASCAL 7) acestea sînt:
Tipul datei
Număr
de
octeţi Valoare ă
Valoare maximă
BYTE
1
0
255
SHORTINT
1
-128
127
WORD
2
0
65535
INTEGER
2
-32768
32767
LONGINT
4
-2147483648
2147483647
COMP
8
-9.2 E 18
9.2E18
Tipul de dată
Număr
octeţi
Număr de
cifre
semnificati
ve
Valoare
absolută ă
Valoare
absolută
maximă
SINGLE
4
7 .. 8
1.5 E -45
3.4 E 38
REAL
6
11 .. 12
2.9 E -39
1.7 E 38
DOUBLE
8
15 .. 16
5.0 E -324
1.7 E 308
EXTENDED
10
19 .. 20
3.4 E -4932
1.1 E 4932
24
Datele întregi reprezentate în Comp şi cele de tip Real, cu excepţia tipului
Real, necesită prezenţa coprocesorului matematic sau emularea acestuia cu
directivele {$E+,$N+}
Datele de acelaşi tip sau compatibil (de exemplu, integer cu comp,
integer cu real etc.) se pot compara folosind operatorii de relaţie = (egal) <
(mai mic) >(mai mare) <= (mai mic sau egal) >=(mai mare sau egal)
<> (diferit). În expresii logice (care pot conţine operatori aritmetici, operatori de
relaţie etc.), operatorii de relaţie au cea mai mică prioritate.
Indicăm, în ordinea crescîndă a priorităţii, operaţiile care pot fi efectuate
asupra datelor de tip întreg şi semnificaţia lor:
+ - (adunare, scădere);
* / (înmulţire întreagă şi împărţire cu rezultat real);
DIV (împărţire întreagă - cîtul împărţirii întregi);
MOD (restul împărţirii întregi).
Asupra datelor de tip întreg se pot executa următoarele operaţii logice:
op1 SHL op2 - deplasează valoarea lui op1 spre stînga cu op2 biţi;
biţii eliberaţi se pun pe zero;
op1 SHR op2 - deplasează valoarea lui op1 spre dreapta cu op2 biţi;
op1 OR op2 - sau logic bit cu bit asupra reprezentărilor lui op1 şi
op2;
op1 AND op2 - şi logic bit cu bit;
op1 XOR op2 - sau exclusiv bit cu bit asupra reprezentărilor
lui op1 şi op2;
NOT op1 - negaţie logică pe biţi.
Exemplu
Dacă op1 are valoarea 9 şi op2 valoarea 3 ele se reprezintă în memorie pe
2 octeţi astfel
op1 0000 0000 0000 10012
op2 0000 0000 0000 00112
Avem op1 SHR op2 = 0000 0000 0000 00012 =110,
op1 SHL op2 = 0000 0000 0001 10002 = 2410
op1 OR op2 = 0000 0000 0000 10112 = 1110
op1 AND op2 = 0000 0000 0000 00012 = 110
op1 XOR op2 = 0000 0000 0000 10102 = 1010
NOT op1 = 1111 1111 1111 01102 = -1010
25
Tabelele pentru operatorii OR AND XOR şi Not pentru operanzii binari
p1 şi p2 sînt
p1
p2
1
p1 OR p2
p1 AND p2
p1 XOR p2 0
0
1
0
0
0
0
1
1
1
0
1
1
0
0
1
0
1
1
1
0
1
1
0
Asupra mărimilor reprezentate în virgulă flotantă se pot executa următoarele
operaţii aritmetice:
+ - (adunare, scădere sau schimbare de semn);
* / (înmulţire şi împărţire).
Expresiile aritmetice sînt alcătuite din constante, variabile, valori de
funcţii sau constante, variabile şi valori de funcţii reunite cu ajutorul
operatorilor.
Pentru a se impune o anumită ordine de efectuare a operaţiilor se folosesc
parantezele rotunde. În lipsa parantezelor sau în interiorul lor, ordinea
descrescîndă a priorităţii operaţiilor este
- NOT (operatorii unari de schimbare a semnului şi negaţie pe bit);
* / DIV MOD SHR SHL AND ;
+ - OR XOR.
Dacă operatorii au aceeaşi prioritate, evaluarea rezultatului se face de la stînga
la dreapta.
DATE DE TIP CHAR
O dată de tip CHAR are ca valoare codul unui caracter (literă mare, mică,
cifră, caractere speciale) şi ocupă în memorie un octet. Pentru a reprezenta o
constantă de tip CHAR, caracterul respectiv se include între două caractere
apostrof.
26
DATE DE TIP BOOLEAN
O dată de tip BOOLEAN poate avea, la un moment dat, una din valorile
TRUE (pentru adevărat) şi FALSE (pentru fals). Identificatorul de tip cu care
se declară tipul lor este BOOLEAN. Modul de reprezentare internă ale valorilor
true şi false depinde de implementare. Datele de tip BOOLEAN pot fi
operanzi ai următoarelor operaţii logice:
- negaţia - operatorul NOT;
- conjucţia - operator AND
- disjuncţia - operator OR
- sau exclusiv - operator XOR (sau <>).
- echivalenţa - operator =
- implicaţia - operator <=
- implicaţia inversă - operator >=
OBSERVAţIE.
Pentru compatibilitate cu WINDOWS se pot folosi şi următoarele tipuri
logice:
WORDBOOL (se reprezintă pe 2 octeţi), LONGBOOL (pe 32 biţi) şi
BYTEBOOL (pe 1 octet).
TIPUL ENUMERARE
În numeroase situaţii intervin date care au un caracter nenumeric, cum ar
fi culoarea unui obiect, calitatea sau ocupaţia unei persoane etc.
Se pune probema de a asocia acestor variabile un tip de date care să fie
utilizat în prelucrări. O soluţia ar consta în codificarea acestora (de pildă
culoarea A să însemne alb, N negru, R roşu etc.). O alta, oferită de limbajul
PASCAL, constă în enumerarea constantelor care aparţin tipului respectiv. De
exemplu
culori=(alb,galben, oranj,bej,auriu,albastru,verde,rosu,negru);
sex=(femeiesc,barbatesc)
Datele de tip enumerare nu pot fi citite sau scrise sau utilizate pentru a
defini alte tipuri, dar ele pot fi utilizate în comparaţii, atribuiri etc. Ele se
utilizează în cadrul programelor pentru a mări gradul de lizibilitate.
TIPURI ORDINALE DE DATE
27
Tipurile ordinale se caracterizează prin faptul că mulţimea valorilor
posibile este finită şi ordonată. Astfel, dintre tipurile de date enumerate mai sus,
următoarele sînt tipuri ordinale:
întreg cu excepţia lui COMP;
CHAR;
BOOLEAN;
enumerare;
subdomeniu.
Orice dată de tip ordinal poate fi argument al unei dintre următoarele funcţii
ORD (ordinal sau valoarea datei sau rangul datei - primul element are
ordinalul 0 );
PREC (predecesor- este nedefinit pentru primul element);
SUCC (succesor - este nedefinit pentru ultimul).
Dacă ch este o dată de tipul CHAR, Ord(ch) este egal cu codul ASCII
zecimal al caracterului ch. De exemplu Ord( ‘A ‘)=45, Ord( ‘a ‘)=97, Prec( ‘B
‘)= ‘A ‘, Succ( ‘A ‘)= ‘B ‘.
Pentru constantele logice True şi False avem Ord(True)=1, Ord(False)=0,
Succ(False)=True şi Prec(True)=False.
Pentru data de tip enumerare culori=(rosu, galben, albastru), avem
Ord(rosu)=0, Ord(galben)=1, Ord(Albastru)=2, Succ(rosu)=galben,
Succ(galben)=albastru, Prec(albastru) = galben etc.
Pentru orice dată x de tip ordinal pentru care au sens Ord(x), Succ(x) şi
Prec(x) au loc relaţiile Ord(Prec(x))=Ord(x)-1 şi Ord(Succ(x))=Ord(x)+1.
OBSERVAţIE
Funcţia Chr, care are argument de tip întreg, furnizează caracterul care
are ordinalul egal cu argumentul. Prin urmare, Chr(65) este caracterul A,
Chr(48) caracterul 0, Chr(12)=FF (FormFeed), Chr(10)=LF (Line Feed) etc.
TIPUL SUBDOMENIU
Sînt numeroase situaţiile în care domeniile datelor care se vehiculează în
interiorul programelor sînt subdomenii ale unor date de tip ordinal. De
exemplu, notele care le obţin studenţii sînt numere întregi cuprinse între 1 şi 10,
o cifră a sistemului de numeraţie zecimal este cuprinsă între 0 şi 9 etc. Un tip
28
subdomeniu se defineşte prin intermediul a două constante de acelaşi tip ordinal.
Acestea satisfac condiţia că prima este mai mică sau egală cu a doua. Sintaxa de
definire este c1..c2. Dacă ord(c2)<ord(c1), atunci c1..c2 desemnează mulţimea
vidă.
Exemplu:
type nota=1..10;
culori=(alb,galben, oranj,bej,auriu,albastru,verde,rosu,negru);
culoare_deschisa=alb..auriu;
culoare_inchisa=albastru..negru;
INSTRUCţIUNI EXECUTABILE PASCAL
Un program PASCAL poate conţine instrucţiuni de declarare, instrucţini
executabile şi comentarii.
Comentariile se folosesc pentru a explica semnificaţia diferitelor
variabile, rolul unor secvenţe de program, autorul, data scrierii programului etc.
Sînt alcătuite din şiruri de caractere care încep cu { şi se încheie cu }, sau încep
cu (* şi se încheie cu *). Un comentariu se poate întinde pe mai multe linii de
program.
Sintaxa limbajului este liberă în sensul că o instrucţiune se poate întinde
pe mai multe linii de program şi o linie de program poate conţine mai multe
instrucţiuni. Instrucţiunile se separă unele de altele (cînd este cazul) prin
caracterul ; (punct şi virgulă).
Instrucţiunile executabile (cu excepţia instrucţiunii de atribuire) încep cu
un cuvînt cheie.
O instrucţiune executabilă este una dintre următoarele:
instrucţiunea de atribuire (:=);
instrucţiunea compusă sau blocul (Begin..End);
alternativa multiplă (Case..Of..Else..End);
ciclul cu contor (For..To/Downto..Do);
instrucţiunea de salt (GoTo);
alternativa simplă (If..Then..Else);
inserarea de instrucţiuni în limbaj de asamblare (inline(...));
apelul de procedură;
bucla cu test final (Repeat..Until..);
bucla cu test iniţial (While.. do);
intrucţiunea nulă;
29
instrucţiunea de calificare (With ... do ).
Mai multe instrucţiuni executabile se pot grupa într-un bloc pentru a fi
tratate din punct de vedere sintactic ca o instrucţiune. În acest scop se utilizează
cuvîntul cheie BEGIN în faţa primei intrucţiuni şi cuvîntul cheie END după
ultima instrucţiune.
Cînd, între instrucţiunile executabile, se întîlnesc două caractere punct
virgulă consecutive sau cînd caracterul punct şi virgulă este situat în faţa
cuvîntului cheie END (de încheiere a blocului), se consideră că între acestea se
află instrucţiune: instrucţiunea vidă. Efectul său din punctul de vedere al
execuţiei este nul. Totuşi ea este utilă în situaţia în care sintaxa cere prezenţa
unei instrucţiuni, dar efectul său trebuie să fie nul. Instrucţiunea vidă nu poate fi
utilizată în fată cuvîntului cheie ELSE asociat alternativei If.
Prezentăm în continuare instrucţiunile executabile ale limbajul
PASCAL. Cuvintele cheie care identifică instrucţiunea sau o parte a acesteia vor
fi scrise cu litere mari.
Instrucţiunea apel procedură se reduce la numele procedurii care poate fi urmat
de o listă de parametri actuali inclusă între (). În general, declararea procedurii
trebuie să preceadă utilizarea ei. Procedurile pot fi definite de către programator
sau pot face parte din bibliotecile PASCAL. Prezentăm în continuare două
funcţii de bibliotecă.
Procedura WRITE scrie în fişierul standard de ieşire (de regulă pe
monitor) valorile unor expresii. Apelul ei este de forma:
WRITE(Lista_de_expresii)
Elementele listei de expresii se separă prin virgulă. Nu pot fi date de tip
enumerare. Pentru a trece la rînd nou (la înregistrare nouă) vom tipări caracterul
#10 (LF), iar pentru a trece la început de rînd caracterul #13 (CR).
Prin urmare, instrucţiunea WRITE( ‘Viata e frumoasa ‘#13#10'Noi sa fim
sanatosi ‘) va scrie pe rîndul curent textul Viata e frumoasa, iar de la începutul
rîndului următor Noi sa fim sanatosi. Apelul WRITE( ‘A( ‘,i, ‘)= ‘) va afişa
textul A(, apoi valoarea variabilei i, apoi textul )=.
Vom folosi procedura WRITELN pentru a obţine efectul procedurii
WRITE urmat de o trecere la rîndul următor. Apelul acestei proceduri este
similar cu al procedurii WRITE.
Procedura READ se foloseşte pentru a citi date în memoria internă din
fişierul standard de intrare (de regulă, tastatura). Ea se apelează astfel
READ(Lista_de_elemente)
30
în care listă_de_elemente este alcătuită din variabile (cu tipul diferit de
enumerare) sau elemente de tablou separate prin virgulă. Valorile introduse
trebuie să facă parte din domeniul de valori al tipului variabilelor. În lista de
intrare, valorile se separă una de alta printr-un caracter alb (spaţiu, Tab etc.). Fie
apelul READ(a,b,c). Dacă A este de tip INTEGER, B şi C de tip REAL,
introducînd valorile 10 5. 20.4 după execuţia instrucţiunii apel de procedură, A
va avea valoarea 10, B valoarea 5. , iar C valoarea 20.4.
Dacă tipul elementului ce se citeşte şi tipul datei introduse nu sînt
compatibile (de exemplu, trebuie citită valoarea pentru o variabilă de tip întreg,
iar valoare introdusă este 14.34), execuţia instrucţiunii se încheie cu eroare.
Vom folosi procedura READLN pentru a obţine efectul procedurii READ
şi o trecere la linie nouă (sau o nouă înregistrare).
Instrucţiunea de atribuire are următoarea sintaxă
nume_variabilă :=expresie
Se execută următoarele prelucrări:
se evaluează mai întîi expresia din membrul drept;
rezultatul se converteşte la tipul variabilei;
valoarea rezultată este atribuită ca nouă valoare variabilei.
Tipul variabilei trebuie să coincidă sau să fie compatibil cu tipul
expresiei.Pentru tipurile de dată definite anterior sînt valabile regulile de
compatibilitate:
o expresie de tip întreg se poate atribui fără restricţii unei varibile de tip real
;
o expresie de tip întreg se poate atribui, în anumite limite, unei variabile de
tip întreg;
alte reguli se vor da ulterior.
OBSERVAŢII
Nu se poate atribui o expresie de tip real unei variabile de tip întreg. Pentru
aceasta se utilizează funcţii Round (de rotunjire la întreg) şi Trunc (de
trunchiere la întreg).
Atribuirile de forma
variabila:= variabila + expresie sau
variabila:=variabila-expresie
31
cînd expresie este de tipul LongInt, se pot înlocui cu instrucţiunile apel de
procedură
INC(variabila[,expresie]) respectiv
DEC(variabila[,expresie])
Valoarea implicită (prin lipsă) pentru expresie este 1.
Deci inc(n,3) este echivalentă cu n:=n+3, iar dec(n,4) cu n:=n-4
Pentru a realiza conversii de tip explicite se folosesc expresii de forma
nume_tip(expresie).
INSTRUCţIUNEA IF
Se foloseşte cînd trebuie efectuate prelucrări condiţionate de faptul că o
expresie logică este adevărată sau falsă. Este omoloaga instrucţiunii cu acelaşi
nume din limbajul pseudocod.
Are două forme
IF expresie_logica THEN
instrucţiune1
şi
IF expresie_logica THEN
instrucţiune1
ELSE
instructiune2
Prima formă a instrucţiunii este tratată astfel:
Se evaluează expresie_logica ;
Dacă este adevărată se execută instrucţiune1;
Se trece la instrucţiunea următoare.
A două formă a instrucţiunii este tratată astfel:
Se evaluează expresie_logică;
Dacă este adevărată se execută instrucţiune1, în caz contrar se execută
instrucţiune2;
32
Se trece la instrucţiunea următoare.
OBSERVAţII
instructiune1 şi instrucţiune2 pot fi instrucţiuni compuse ;
sînt permise instrucţiuni if imbricate (incluse una în alta). În acest caz
cuvîntul cheie else se asociază ultimului if început.
EXEMPLE
1.
if d=2 then
inc(d)
else
inc(d,2)
2.
If a=2 then
c:=b
else (* urmează o instrucţiune vida *)
;
INSTRUCţIUNEA CASE
Cînd execuţia programului continuă cu o instrucţiune sau alta dintr-o
mulţime de instrucţiuni posibile, în funcţie de valorile unei expresii numite
selector, programatorul poate folosi mai instrucţiuni if sau poate folosi
instrucţiunea case.
Sintaxa acesteia este
CASE expresie OF
lista_de_valori_1:
instructiune_1;
lista_de_valori_2:
instrucţiune_2;
.................................
lista-de_valori_n:
instrucţiune_n [;
ELSE
instructiune_m]
33
END;
lista_de_valori_1, lista_de valori_2 etc. sînt liste de elemente separate prin
virgulă. Elementele pot fi constante sau subdomenii. Listele de valori se numesc
etichete.
Execuţia instrucţiunii are loc după următorul algoritm:
Se evaluează expresie (selectorul) ;
Se compară cu etichetele în ordinea în care acestea sînt scrise ;
Daca valoarea expresiei este egală cu a unei constante din lista
corespunzătoare etichetei se execută instrucţiunea asociată etichetei. În caz
contrar, dacă else este prezent, se execută instrucţiune_m.
se trece la instrucţiunea care urmează după end.
OBSERVAţIE
Instructiunea care precede Else este urmată de caracterul ; dar
instrucţiunea ce precede end nu este urmată de caracterul ;
EXEMPLU. Găsiţi numărul trimestrului în funcţie de lună. Dacă luna este
incorectă, atribuiţi trimestrului valoarea 0.
case luna of
1..3: trimestrul:=1;
4..6: trimestrul:=2;
7..9: trimestrul:=3;
10..12: trimestrul:=4;
else
trimestrul:=0 (* luna incorecta *)
end;
INSTRUCţIUNEA FOR
Este corespondenta PASCAL a instrucţiunii For din limbajul pseudocod,
obţinută pentru valoarea pasului 1, respectiv -1.
Instrucţiunea FOR are două forme
FOR contor:=valoare_iniţială TO valoare_finală DO instrucţiune;
FOR contor:=valoare_iniţială DOWNTO valoare_finală DO
instructiune;
34
Contor este o variabilă de tip ordinal, iar valoare_iniţială şi valoare_finală
expresii care au au acelaşi tip ordinal (nu pot fi date de tip Real).
Execuţia acesteia presupune execuţia următorilor paşi:
1. se evaluează valoare_iniţială şi valoare_finală;
2. se atribuie variabile contor valoare_iniţială;
3. se compară contor cu valoare finală;
4. dacă este mai mică sau egală cu aceasta(în prima formă ) sau mai mare
sau egal cu aceasta în cea de-a doua, se execută instrucţiune. Altfel se
trece la instrucţiunea ce urmează după for
5. se măreşte cu 1 (în cazul primei variante) sau se micşorează cu 1 (în cazul
variantei a doua) valoarea variabilei contor. Se trece la punctul 3.
INSTRUCţIUNEA WHILE
Are sintaxa
WHILE expresie_logica DO instructiune;
Are următorul efect:
se evaluează expresie_logică;
dacă este adevărată se execută instrucţiune şi se reia de la reevalularea
condiţiei, iar
dacă este falsă se continuă cu tratarea instrucţiunii următoare.
INSTRUCţIUNEA REPEAT
Are forma
REPEAT
secventa_de_instrucţiuni
UNTIL expresie logică;
este echivalentă din punctul de vedere al tratării cu
35
secventa_de_instructiuni
WHILE expresie_logica DO secventă_de_instrucţiuni;
EXEMPLU
Verificaţi dacă numărul natural n, mai mare decît 1, introdus de la
tastatură este prim.
Uses crt; ‘
var n, (* numarul natural *)
d: INTEGER; (* un posibil divizor *)
Begin
repeat
write( ‘dati numarul natural ‘);
read(n)
until n>1;
d:=2;
while (d<n) and (n mod d <>0) do (* parantezele sint necesare! *)
Inc(d,1+ord(d<>2));
if d<n then
write( ‘Numarul este compus ‘)
Else
write( ‘Numarul este prim ‘)
end.
OBSERVAţIE
Sub influenţa limbajul C, au fost implementate procedurile:
break - care termină necondiţionat cea mai interioară instrucţiune de
ciclare (while, repeat
şi for).
continue - cea mai interioară instrucţiune de ciclare (while, repeat şi for)
se reia cu pasul următor.
PROCEDURI ŞI FUNCŢII PASCAL
36
Un subprogram este o alcătuit dintr-o mulţime de instrucţiuni care
execută o acţiune specifică, eventual, în funcţie de valorile unor parametri.
Gruparea instrucţiunilor în subprograme se face din două motive:
aceeaşi secvenţă de instrucţiuni trebuie executată în mai multe locuri ale
programului, eventual cu date diferite;
pentru a putea descompune o problemă complexă în subprobleme care să
poată fi stăpînite mai uşor.
Ele pot fi apelate din programul principal sau din alt subprogram. Cînd se
apelează un subprogram, execuţia programului se continuă cu prima
instrucţiune executabilă a acestuia, iar la revenirea în apelant se continuă cu
instrucţiunea următoare instrucţiunii de apel a subprogramului. Un subprogram
poate fi apelat de un alt subprogram, ba mai mult, un subprogram se poate apela
pe sine însuşi (deci subprogramul poate fi recursiv).
Subprogramele pot primi la intrare valori de care depinde rezultatul
execuţiei lor. Anumite valori de intrare (anumiţi parametri actuali) ai
procedurilor sau funcţiilor pot fi modificate în interiorul subprogramului.
Subprogramele Pascal sînt de două tipuri: proceduri şi funcţii. Funcţiile
sînt subprograme care întorc o valoare, adică la sfîrşitul execuţiei lor îi transmit
apelantului o valoare care este folosită în expresii. Spre deosebire de funcţii,
procedurile nu întorc nici o valoare. Folosind opţiunea de compilare {$X+},
valoarea furnizată de o funcţie poate fi ignorată: nu sîntem interesaţi de valoarea
întoarsă de funcţie, ci de acţiunea ei.
Subprogramele Pascal se definesc în întregime în partea introductivă a
unui program, înainte de corpul propriu-zis al programului.
O procedură este alcătuită din următoarele părti:
un antet în care se specifică numele procedurii şi, cînd este cazul, lista
parametrilor formali (care corespund valorilor de intrare):
procedure nume_de_procedură; sau
procedure nume_de_procedură ( lista_de_parametri ); În prima formă, procedura nu are parametri de intrare sau parametri
fomali.
Parametrii formali corespund valorilor care se transmit procedurii:
parametrilor reali, efectivi sau actuali. Corespondenţa dintre parametrii
formali şi parametrii actuali se face prin poziţie. Lista de parametri
formali este alcătuită din subliste de forma [var] p1[,p2]...; în care p1, p2
etc. sînt numele parametrilor formali. Dacă sublista nu începe cu var,
parametrii (numiţi parametri de tip valoare) pot fi modificaţi în
procedură, dar parametrii reali rămîn nemodificaţi după revenire din
37
procedură. În caz contrar,se numesc parametri de tip referinţă, iar valorile
primite în cadrul procedurii vor fi valorile parametrilor reali după
revenire în apelant;
declaraţii locale procedurii (variabile, constante etc.;
instrucţiuni care definesc corpul procedurii cuprinse între cuvintele Begin şi
End.
O funcţie este o parte de program în care se calculează şi care întoarce o
valoare. O funcţie este alcătuită din:
un antet de forma:
function nume_de_funcţie : tipul_functiei;
sau
function nume_de_functie (lista_de_parametri) : tipul funcţiei;
Antetul de funcţie specifică numele funcţiei, parametrii formali (dacă
există) şi tipul funcţiei. Lista de parametri are structura prezentată la
proceduri. Tipul funcţiei sau tipul valorii întoarse poate fi ordinal, real, şir
şi pointer. Valoarea furnizată de funcţie poate fi folosită în expresii
PASCAL;
declaraţii locale ;
corpul funcţiei. El trebuie să conţină cel puţin o instrucţiune de atribuire prin
care identificatorul funcţiei primeşte valoarea pe care funcţia o întoarce
apelantului;
o declaraţie de funcţie poate conţine directive forward, external, far sau
inline.
Exemple
1. Calculaţi şi afişati n!.
Vom prezenta trei versiuni ale aceluiaşi program. Vom considera că n=10
(modificaţi blocul de execuţie ca programul să fie independent de valoarea lui
n).
1a) { Calculati n! }
uses crt;
function fact(n:word):word;
var f:word;
begin
f:=1;
while (n>1) do begin
f:=f*n;
dec(n)
end;
38
fact:=f;
end;
begin
writeln('10!=',fact(10));
end.
1b) { Calculati n! }
uses crt;
procedure fact(n:word;var f:word);
begin
f:=1;
while (n>1) do begin
f:=f*n;
dec(n)
end;
end;
var factorial: Integer;
begin
fact(10,factorial);
writeln('10!=',factorial);
end.
1c) {Calculati lui n! prin recursivitate}
uses crt;
function fact(n:word):word;
begin
if (n=0) then
fact:=1
else
fact:=n*fact(n-1);
end;
begin
writeln('10!=',fact(10));
end.
39
Un alt caz de recursivitate este acela în care în definiţiile a două
subprograme acestea se apelează reciproc, deci avem de-a face cu o
recursivitate indirectă. Vom arăta cum se procedează în asemenea situaţii în
cazul următoarei probleme: Fie x0 şi y0 două numere reale pozitive. Definim
şirurile xn şi yn astfel: pentru n=0, avem x0= x0 şi y0=y0, iar pentru n>0a vem
xn=(xn-1+yn-1)/2 şi yn=(xn-1+yn-1)1/2
. Calculaţi , pentru un n dat, xn şi yn.
Vom scrie doar funcţiile prin care se calculează cele două valori.
Function y( x0,y0:Real;
n:Integer):Real; forward;{indicăm tipul funcţiei y şi că ea va fi
definită ulterior}
Function x( x0,y0:Real;n:
Integer):Real;
begin
if n=0 then
x:=x0
else
x:=(x(n-1)+y(n-1))/2;
end;
Function y;
begin
if n=0 then
y:=y0
else
y:=sqrt(x(n-1)+y(n-1));
end;
TIPURI DE DATE DEFINITE DE UTILIZATOR
Limbajul Pascal permite definirea unor tipuri de date noi pornind de la
cele de bază. Acestea pot reprezenta restricţii sau extensii ale tipurilor de date
predefinite. Aceste tipuri de date pot fi identificate printr-un nume sau pot fi
anonime. In primul caz, fiecare identificator se defineşte în partea declarativă a
blocului (de regulă, între declaraţiile de constante şi cele de variabile), în care se
utilizează.
Sintaxa lor este
type Identificator_de_tip= definiţie_de_tip;
40
identificator_de_tip=definitie_de_tip;
Complexitatea unei instrucţiuni de declarare a tipului variază în funcţie de
problema concretă care trebuie rezolvată.
Exemplu:
type logic=boolean;
În continuare tipul de dată definit poate fi utilizat pentru a declara
variabile, constante şi funcţii.
De exemplu
var da,nu:logic;
În cazul tipurilor anonime, declaraţiile se fac direct în cadrul
instrucţiunilor de definire/declarare a variabilelor.
Declararea tablourilor
Un tablou este un şir de elemente de acelaşi tip, fiecare element fiind
identificat printr-un indice, valorile acestuia formînd un subdomeniu al unui tip
ordinal. Pentru a declara tablouri, trebuie precizate: numele tabloului, tipul
elementelor sale şi subdomeniul indicilor.Prin urmare, un tablou se declară prin
construcţii de forma
identificator: ARRAY [domeniu_indice_1{,domeniu_indice_2}...] OF tip;
în care {} indică prezenţa unui element opţional, iar tip un tip de date
PASCAL.
Prin a: array [1..25] of integer , se declară a tablou (vector) cu elemente de tip
INTEGER, cu domeniul valorilor indicilor 1..25, deci a are 25 de elemente.
Prin declaraţia b: array [ ‘A ‘.. ‘Z ‘] of REAL; b se declară vector cu
elemente de tip real ale cărui elemente sînt indexate prin caractere cuprinse între
‘A ‘ şi ‘Z ‘ (prin urmare numărul elementelor sale este ord( ‘Z ‘)-ord( ‘A ‘)+1).
Un element al tabloului se poate referi prin numele tabloului urmat de o
listă de expresii de indici care dă rangul elementului pe fiecare dimensiune.
Singura operaţie predefinită asupra datelor de tip tablou este atribuirea,
care are ca efect copierea valorilor elementelor tabloului din membrul drept al
41
instrucţiunii în elementele tabloului din membrul stîng. Cele două tablouri
trebuie să aibă acelaşi tip.
Elementele unui tablou pot fi la rîndul lor elemente de tablou, deci sînt
posibile declaraţii de forma
a array [1..15] of array [1..10] of real.
În această situaţie a[i] este un vector de 10 elemente de tip real. Un element de
rang j al acestuia se referă prin a[i][j].
EXEMPLE
Fie (A, ) o mulţime finită total ordonată în raport cu relaţia adică:
relaţia este reflexivă: x A avem x x;
relaţia este tranzitivă: x,y,z A din x y şi y z rezultă x z;
relaţia este antisimetrică: din x y şi y x rezultă x=y;
Fie A={a1,a2,a3,..an}. A sorta mulţimea A înseamnă:
a dispune elementele sale în ordinea
a ... a a a iiii n321 , unde a,...,a,a=a ,...,a,a,a n21iiii n321
sau
a determina un vector O=(o1,o2,...,on), componenta oi indicînd poziţia
elementului ai în mulţimea sortată (ca la primul punct).
Exemplul 1. Se dă un şir (vector) de numere întregi. Să se scrie un program
Pascal de sortare crescătoare a acestuia.
Vom prezenta în continuare mai multe programe PASCAL
corespunzătoare unor algoritmi cunoscuţi. Pentru simplificarea expunerii vom
presupune că elementele mulţimii A sînt de tip întreg, că numărul elementelor
sale nu depăşeşte 100, iar relaţia de ordine este relaţia obişnuită.
1a) Sortare prin metoda bulelor sau prin interschimbare
Ideea acestui algoritm este următoarea:
parcurgem mulţimea (care poate fi echivalată cu un vector) de început la
sfîrşit comparînd doi vecini: ai cu ai+1. Dacă ai+1 i , schimbăm valorile lor
între ele ;
dacă am efectuat schimbări de poziţie (de valori) reluăm procedeul ;
Numele metodei derivă din faptul că, aşa cum o bulă de aer dintr-un lichid se
ridică la suprafaţă, tot aşa la fiecare pas, valorile elementelor mai mari îşi
ocupă poziţii pe care nu le mai părăsesc.
42
Programul Pascal este
uses crt;
var n, (* numarul de elemente *)
i, (* contor *)
aux: INTEGER; (* variabilă de lucru *)
a: Array [1..10] of INTEGER;
sortat:Boolean;
begin
(* citim numarul de elemente ce trebuie sortate *)
repeat
write ( ‘Numar de elemente de sortat ‘);
read(n)
until (n>0) and (n<=100);
(* citeste elementele *)
for i:=1 to n do begin
write( ‘a( ‘,i, ‘)= ‘);
read(a[i])
end;
(* sortarea elementelor *)
repeat
sortat:=true;
for i:=1 to n-1 do
if a[i+1]<= a[i] then begin
Aux:=A[i];
A[i]:=A[i+1];
A[i+1]:=Aux;
sortat:=false
end;
until sortat;
(* afiseaza rezultatul *)
clrscr; (*sterge ecranul*)
for i:=1 to n do
write(a[i], ‘ ‘);
readln; (*asteapta Enter *)
end.
43
1b) Sortare prin selecţie directă
Metoda se bazează pe observaţia că primul loc în vectorul sortat stă cel
mai mic element al mulţimii, locul al doilea este ocupat de elementul care
urmează imediat după acesta (ul multimii iniţiale mai puţin cel deja completat)
etc.
Programul Pascal este
uses crt;
var n, (* numarul de elemente *)
i,j, (* variabile contor *)
,indice_: INTEGER; (* variabile de lucru *)
a: Array [1..10] of INTEGER;
begin
(* citim numarul de elemente ce trebuie sortate *)
repeat
write ( ‘Numar de elemente de sortat ‘);
read(n)
until (n>0) and (n<=100);
(* citeste elementele *)
for i:=1 to n do begin
write( ‘a( ‘,i, ‘)= ‘);
read(a[i])
end;
(* sortarea elementelor *)
for i:=1 to n do (*completam toate pozitiile ale multimii sortate *)
Begin
(* pe pozitia i trebuie sa stea cel mai mic element dintre a[i],a[i+1],...,
a[n] *)
:=a[i];
indice_:=i;
for j:=i+1 to n do
if a[j]< then begin
44
:=a[j];
Indice_:=j
end;
a[indice_]:=a[i];
a[i]:=
End;
(* afiseaza rezultatul *)
clrscr; (*sterge ecranul*)
for i:=1 to n do
write(a[i], ‘ ‘);
readln; (*asteapta Enter *)
end.
1c) Sortare prin numărare
Cu această metodă mulţimea iniţială se sortează în conformitate cu
definiţia a doua a sortării (se găsesc poziţiile elementelor în mulţimea sortată).
Ideea este următoarea: se ia elementul de indice i şi se numără cîte
elemente sînt mai mici decît el. În vectorul sortat, el va ocupa următoarea
poziţie.
uses crt;
type vector=array [1..10] of integer; (* definim tipul de data vector *)
var n, (* numarul de elemente *)
i,j:Integer; (* variabile contor *)
a, (* vectorul de sortat *)
o: vector; (*pozitiile in vectorul sortat *)
begin
(* citim numarul de elemente ce trebuie sortate *)
repeat
write ( ‘Numar de elemente de sortat ‘);
read(n)
until (n>0) and (n<=100);
(* citeste elementele ce trebuie sortate si initializeaza vectorul cu ordinea
elementelor *)
for i:=1 to n do begin
o[i]:=1; (* cel mai mic element ocupă prima poziţie *)
45
write( ‘a( ‘,i, ‘)= ‘);
read(a[i])
end;
for i:=1 to n do (* elementele a[i] si a[j] se vor compara o singura
data ! *)
for j:=i+1 to n do
if a[i]<=a[j] then
Inc(o[j])
else
Inc(o[i]);
(* afiseaza rezultatul *)
clrscr; (*sterge ecranul*)
for i:=1 to n do
writeln (a[i], ‘ ocupa pozitia ‘,o[i]);
readln; (*asteapta Enter *)
end.
MODIFICAŢI programul de mai sus ca el să afişeze elementele în ordine
crescătoare.
1d) Sortare prin inserţie directă
Ideea acestei metode este următoarea: se porneşte de la o listă formată din
primul element al mulţimii. Se inserează al doilea element al mulţimii în listă
astfel încît noua listă să aibă elementele dispuse în ordine crescătoare.La pasul j
avem lista ordonată a1 a2 a3 ... aj-1. Trebuie inserat elementul aj în listă.
Pentru aceasta procedăm astfel: îl comparăm pe aj cu elementele listei începînd
cu aj-1, aj-2 s.a.m.d. Toate elementele mai mari decît el se deplasează cu o poziţie
mai la dreapta. Elementul aj va fi inserat în capul listei (cînd lista nu are
elemente mai mici decît el) sau după primul (însensul de parcurgere a
vectorului) element ai care satisface relaţia ai aj.
uses crt;
var n, (* numar de elemente *)
i,
j, (* contoare *)
aux, (* variabila de lucru *)
46
poz:integer; (*pozitia dupa care se va insera a[j] *)
a: array [1..100] of integer;
begin
(* citeste si valideaza numarul de elemente care alcatuiesc multimea (???!) *)
repeat
write('Numar de elemente = ');
readln(n)
until (n>0) and (n<=100);
(* citeste elementele *)
for i:=1 to n do begin
write('a(',i,')=');
read(a[i])
end;
(* completeaza pe rind elementele in lista partiala sortata *)
for j:=2 to n do begin
aux:=a[j]; (* pastreaza valoarea lui a[j] care se poate
modifica *)
i:=j-1;
while (i>0) and (aux<=a[i]) do begin
(* elementele mai mari ca a[j] se decaleaza spre dreapta cu o
pozitie *)
a[i+1]:=a[i];
dec(i)
end;
a[i+1]:=aux; (* pune a[j] pe locul sau *)
end;
(* afiseza rezultatul *)
clrscr;
for i:=1 to n do write (a[i],' ');
readkey; (* asteapta Enter *)
end.
2. Problema căutării
Fie A o mulţime finită de date şi x o dată de acelaşi tip cu elementele
mulţimii. Se cere să se verifice dacă x A.
47
Prezentăm în continuare mai multe soluţii ale acestei probleme,
presupunînd că mulţimea are n elemente care sînt citite în memoria internă şi
au tipul Integer.
2a) Căutare secvenţială
Se compara x cu elementele mulţimii pînă cînd am găsit unul cu care este
egal sau am efectuat toate comparaţiile posibile
(* s-a omis partea de declaraţii şi citiri de date *)
(* compara x cu elementele multimii. Daca s-a intilnit un element a[i] cu a[i]=x
ebandoneaza comparatiile *)
for i:=1 to n do
if x=a[i] then break;
if i<=n then
write( ‘Elementul ‘, x, ‘ este egal cu elementul de pe pozitia ‘,i)
else
write( ‘Elementul ‘,x, ‘ nu face parte din multime ‘);
Presupunem că mulţimea A este sortată crescător
Algoritmul de mai sus se poate îmbunătăţi în sensul că operaţiile de
comparare se pot încheia cînd s-a întîlnit primul element mai mare ca x sau cînd
s-a comparat cu toate. În acest caz avem
for i:=1 to n do
if x<=a[i] then break;
if (i<=n) and (x=a[i]) then
write( ‘Elementul ‘, x, ‘ este egal cu elementul de pe pozitia ‘,i)
else
write( ‘Elementul ‘,x, ‘ nu face parte din multime ‘);
2b). Căutare binară (sau prin metoda dihotomiei)
Ideea metodei este asemănătoare cu cea de rezolvare a ecuaţiilor
algebrice şi tran-scendente prin metoda înjumătăţirii intervalului.
program cautare;
var n, (* numar de elemente *)
x, (* valoarea ce se cauta *)
48
i,is,id,im:integer; (* indici *)
gasit:boolean;
a:array [1..10] of integer;
begin
for i:=1 to 10 do a[i]:=2*i+5;
write('introduceti valoarea de cautat ');
readln(x);
is:=1;id:=10; gasit:=false;
while((is<=id) and not gasit) do
begin
im:=(is+id) div 2;
if x<a[im] then
id:=im-1
else
if x>a[im] then
is:=im+1
else
gasit:=true;
end;
if gasit then writeln('Este pe pozitia ',im)
else writeln('Nu este');
end.
Se citesc de la tastatură valori întregi. Fie n un număr natural dat. Reţineţi
din valorile date cele mai mici n dispuse în ordine crescătoare.
Rezolvăm problema astfel:
fie k variabila în care memorăm numărul valorilor reţ
valoarea iniţială a variabile k este 0 (n-am reţinut nici un element);
citim o valoare x de la tastatură ;
încercăm să o inserăm în lista celor deja reţinute astfel:
parcurgem lista celor reţinute începînd cu ultimul element al acesteia punînd
fiecare element mai mare decît x pe poziţia următoare (cînd k=n, ultimul se
pierde);
dacă toate elementele sînt mai mari decît x, acesta se va insera pe prima
poziţie, altfel după elementul care este mai mic decît x (dacă nu există un
astfel de element şi k=n, valoarea x nu este inserată în listă)
Presupunem că numărul n este mai mic sau egal cu 100.
49
Un posibil program PASCAL este următorul
uses crt;
var x, (* valori citite *)
n, (*numar de elemente ce trebuie retinute *)
j, (* contor *)
k: Integer; (* numar de elemente retinute *)
a: Array [1..100] of Integer; (* va contine elementele retinute *)
Begin
(* citim numarul de elemente ce trebuie pastrate *)
Repeat
Write( ‘Cite elemente se retin (pastreaza) = ‘);
Readln(n);
until (n>0) and (n<=100);
K:=0; (* n-am retinut inca nici un element *)
writeln( ‘Incheiati cu CTRL - Z Enter ‘);
while true do begin
write( ‘x = ‘);
read(x);
if eof then (* functia de biblioteca Eof intoarce true daca s-a tastat
CTRL-Z *)
break;
j:=k;
while (j>0) and (x<a[j]) do begin
a[j+ord(j<n)]:=b[j];
dec(j);
end;
inc (k,ord(k<n));
if j<n then
a[j+1]:=x
end;
writeln( ‘Valorile retinute sint ‘);
for j:=1 to k do
write(a[j], ‘ ‘);
readln;
end
50
OBSERVAţII 1. Dacă numărul de elemente introduse coincide cu numărul de elemente ce
se păstrează, valorile introduse se sortează crescător ;
2. Ord(k<n) este 0 daca relaţia k<n este false şi 1 dacă este true;
3. Afişarea elementelor se opreşte la k şi nu la n, fiindcă s-ar putea ca
numărul de elemente introduse să fie mai mic decît n.
Tipul String
Tip de date String a fost introdus pentru a prelucra şiruri de caractere. Se
declară prin
String[N]
sau
String
unde N 255 este numărul maxim de caractere al şirului de caractere. Numărul
maxim implicit este 255.
Să considerăm următoarele declaraţii
Type Sir=string[120];
var S: string;
P: Sir;
V: array [0..120] of Char;
În memorie, un şir de caractere ocupă o zonă de N+1 octeţi, în exemplul
nostru variabila S ocupă 121 de octeţi, iar P 256 de octeţi. Caracterul i al şirului
S poate fi referit prin expresia S[i], deci la fel cum ne referim la elementele unui
vector ( în particular, de caractere). Spre deosebire de vectori, prima poziţie,
S[0], conţine lungimea actuală a şirului (de aici limitarea la 255 a lungimii
şirurilor de caractere), dar reprezentată sub formă de tip Char. Prin urmare,
lungimea şirului este Ord(S[0]).
Dacă vectorul V îl putem utiliza doar operaţii de atribuire, şirurile S şi P
pot fi folosite în operaţii de atribuire şi în următoarele operaţii cu şiruri:
concatenarea - notată + Dacă S are valoarea Astazi este , unde prin am
notat caracterul spaţiu, iar P miercuri atunci, S+P este şirul de caractere
Astazi este miercuri
De notat că rezultatul nu poate depăşi 255 de caractere.
comparări în sensul = < > <= >= şi <>. Compararea se face caracter cu
caracter ţinînd seama de poziţia fiecărui caracter în tabelul de codificare
ASCII (prin urmare ‘a ‘> ‘A ‘, ‘A ‘> ‘3' etc.). Această comparare este
numită comparare lexicografică.
51
Şirurile de caractere pot fi argumente actuale ale funcţiilor Read, Write
etc. Prin urmare, un şir nu trebuie citit caracter cu caracter ca în cazul vectorilor
şi nici nu trebuie scris caracter cu caracter.
Sînt disponibile următoarele proceduri şi funcţii pe şiruri:
Length - întoarce lungimea unui şir ;
Copy - întoarce un subşir al unui şir;
Concat - concatenează două sau mai multe şiruri;
Pos - întoarce poziţia unui subşir într-un şir;
Delete - elimină un subşir dintr-un şir;
Insert - inserează un subşir într-un şir;
Str - converteşte o expresie numerică în forma externă;
Val - converteşte un subşir într-o valoare numerică.
Toate vor fi tratate în capitolul relativ la unităţile de program Pascal.
Exemplu.
Să se transforme în litere mici literele mari ale unui şir de caractere.
function Litere_mari(S: string): string;
var
I: Integer;
begin
for I := 1 to Length(S) do
if (S[I] >= 'a') and (S[I] <= 'z') then
Dec(S[I], 32);
Litere_mari := S;
end;
Date de tip ZString
Un ZString este un tablou de caractere care are primul indice 0, iar
ultimul un întreg pozitiv nenul N. Ele se declară prin
array[0..N] of Char
Valoarea maximă a lui N este 65535. Lungimea acestuia poate fi mai
mică decît N+1. În acest caz, şirul se încheie cu caracterul NULL (de aceea ele
mai poartă numele de şiruri care se termină cu null).
Există funcţii de conversie din string în Zstring şi invers.
.
52
Tipul mulţime
Mulţimea este o colecţie de date de acelaşi tip care poate fi de un bază
nestructurat exceptînd tipul REAL.
Tipul mulţime se declară prin
Set of <tip>
Elementele pot fi numere naturale mai mici ca 256, elemente ale unui tip
enumerare sau caractere. Numărul de elemente care formează mulţimea se
limitează la 256. Prin urmare, tipul de bază al unei mulţimi de elemente de tip
întreg nu poate fi INTEGER, ci o parte a sa.
O mulţime poate fi construită din elementele sale folosind constructorul
de mulţimi [] care conţine în interior enumerări. De exemplu:
[] înseamnă mulţimea vidă;
[1] înseamnă mulţimea formată din elementul 1;
[1,2,3] este mulţiema formată din elementele 1,2 şi 3;
[ ‘A ‘.. ‘Z ‘] este mulţimea caracterelor alfabetice cuprinse între A şi Z;
[ ‘Z ‘.. ‘A ‘] este mulţimea vidă.
Exemple
type examen=(algebra, analiza,programare,bazamate);
examene=set of examen;
var promovate,
nepromovate,
aminate: examene;
O mulţime al cărui tip de bază are n elemente se reprezintă în memorie
printr-un şir de n biţi. Bitul I este 1 dacă elementul cu ordinalul I face parte din
mulţime.
Operaţii cu mulţimi:
reuniunea +
intersecţia *
diferenţa -
Două mulţimi se pot compara în sensul =, <> (diferit), <= şi >=
(incluziune).In fine, folsind operatorul IN se poate testa dacă un element
aparţine unei mulţimi.
În limbajul PASCAL există două proceduri de includere şi eliminare a
unui element dintr-o mulţime. Acestea sînt
Include(var S: set of T; element:T);
Exclude(var S: set of T; element:T);
53
Ele pot fi înlocuite cu instrucţiunile de atribuire S:=S+[T], respectiv S:=S-[T]
EXEMPLU
program Eratostene;
(*
Determinarea tuturor numerelor prime mai mici decit 255 folosind ciurul lui
Eratostene
*)
uses crt;
const n=255;
type multime= set of 2..n ;
var ciur,
prime : multime;
multiplu,
urmator :integer;
begin
ciur:=[2..n];
prime:=[];
urmator:=2;
clrscr;
repeat
while not (urmator in ciur) do (* cauta urmatorul numar prezent in
ciur *)
urmator:=succ(urmator);
exclude(ciur,urmator); (* exclude-l din ciur *)
include(prime,urmator); (* adauga-l la prime *)
multiplu:=urmator; (* elimina-i multiplii din ciur *)
while multiplu<=n do
begin
exclude(ciur,multiplu);
inc(multiplu,urmator);
end;
urmator:=succ(urmator); (*determina urmatorul element *)
until (ciur=[]) or (urmator>n);
for urmator:=2 to n do (* afiseaza numerele prime *)
54
if urmator in prime then
write(urmator:4);
write(^m^j'Tastati Enter');
readln;
end.
Tipul record (înregistrare)
Numeroase obiecte din lumea reală se caracterizează printr-o mulţime de
proprietăţi sau atribute. Atributele servesc la descrierea unei clase generale de
obiecte de acelaşi tip care formează tipul obiectului. Un obiect particular al
acestui tip se obţine asociind valori fiecărui atribut. De exemplu, un student al
Facultăţii de ştiinte se poate caracteriza prin: nume, nr_matricol, secţia, grupa,
adresa etc, un abonat al ROMTELECOM prin nume, adresa şi numar_telefon.
În informatică, definirea unui tip structurat constă în enumerarea numelui
fiecărui atribut care caracterizează tipul de date şi tipul de dată corespunzător
fiecărui atribut. Un astfel de tip de date se va numi tip record sau înregistrare.
.Declaraţia sa respectă următoarele reguli
TipDeInregistrare= record
cimp1[,cimp2].. : TipDeData;
[cimp1[,cimp2].. : TipDeData;]...
End;
Exemple
type
Point = record
X, Y: Real;
end;
Vector = array[0..1] of Point;
Month = (Jan, Feb, Mar, Apr, May, Jun, Jly, Aug, Sep, Oct, Nov, Dec);
Date = record
D: 1..31;
M: Month;
Y: 1900..1999;
end;
Exemplul 2.
type student=record
55
numele: string[30];
sex: boolean;
data_nasterii: record
zi: 1..31;
luna: 1..12;
an:1900..1982;
end;
nr_grupa:integer;
note: array[1..10] of 1..10;
end;
Se poate defini o variabilă de acest tip
var grupa:array [1..35] of student;
un_student: student;
Asupra datelor de tip record se pot efectua numai operaţii de atribuire, în
timp ce asupra unui cîmp se pot efectua toate operaţiile permise la acel tip de
date.
Pentru a face referiri la un cîmp al unei înregistrări se foloseşte selectorul
. (punct). Ne vom referi la cîmpul numele al variabilei un_student prin
un_student.numele, iar la cîmpul numele celui de-al 10-lea student al tabloului
grupa prin grupa[10].numele.
OBSERVAţIE
Structura de date înregistrare modelează produsul cartezian din
matematică. O înregistrare constă dintr-un număr fix de elemente componente,
fiecare avînd un anumit tip.
Pentru a simplifica scrierea programelor, cînd într-o secvenţa de
instrucţiuni ne referim în mod repetat la membrii aceleiaşi structuri, putem
folosi intructiunea WITH care are următoarea sintaxă
WITH înregistrare DO instrucţiune;
De exemplu secvenţa
with grupa[i] do begin
numele:= ‘ ‘;
sex:=false;
nr_grupa:=0;
end;
56
ţine locul următoarelor instrucţiuni:
grupa[i].numele:= ‘ ‘;
grupa[i].sex=false;
grupa[i].nr_grupa:=0;
Inregistrări cu variante
Sînt situaţii cînd structura unei înregistrări variază în funcţie de valoarea
pe care o ia un anumit cîmp al său numit discriminator. În mod obligatoriu,
partea variabilă se descrie la sfîrşitul structurii, astfel
CASE [discriminator:] tip_discriminator OF
valoare_discriminator:(definiţii_de_cîmpuri);
valoare_discriminator:(definiţii_de_cîmpuri);
Exemplul 1
uses crt;
type sex=(barbatesc,femeiesc);
alfa=string[30];
personal=record
nume:alfa;
adresa:alfa;
case sexul:sex of
Barbatesc: (greutate: integer; barba:char);
Femeiesc: (inaltime: 145..200;nume_fata: alfa);
end;
var persoana:personal;
C_sex:char;
begin
with persoana do begin
writeln('persoana'); readln(nume);
writeln('adresa'); readln(adresa);
writeln('sexul'); readln(C_sex);
case C_sex of
'm': begin
sexul:=barbatesc;
writeln('gr'); readln(greutate);
57
writeln('barba');readln(barba);
end;
'f': begin
Sexul:=femeiesc;
write('inaltime');readln(inaltime);
write('nume fata'); readln(nume_fata);
end;
end;
end;
end.
Exemplul 2.
Type denumire=array [1..30] of char;
forma=(fara, { fara studii}
Medie, { cu liceu }
Sup); { cu facultate }
persoana=record
Nume,prenume: array [1..20] of char;
Data_nasterii: record
zi: 1..31;
Luna: 1..12;
An: 1940..1975;
End;
Studii: forma;
case forma of
fara:(); { nu avem atribute}
medie:(liceu: record
Den:denumire;
Media_bac:real;
End);
sup:(s: record
Liceu:denumire;
Media_bac:real;
fac:denumire;
mediaf:real
end);
end; { persoana}
Date de tip referinţă cu tip
58
O variabilă de tip referinţă are ca valoare adresa unei zone de memorie.
Aceasta poate fi, de exemplu, adresa la care se memorează valoarea unei
variabile scalare (deci adresa variabilei). Se declară prin construcţii de forma:
nume_variabilă:^tip_de_dată
De exemplu
p:^integer; { variabila p este o referinţă de tip integer }
type ptr=^persoana; { ptr este tipul de date referinţă la date de tip
persoana}
persoana=record
nume:string[30];
vîrsta:integer;
end;
var student:ptr; { student este o referinţă la date de tip persoana }
În primul caz, data referită de p are tipul integer, iar în al doilea, data
referită de student este de tipul persoana.
Unei variabile referinţă cu tip i se poate atribui o valoare prin operaţii de
atribuire, folosind operatorul de adresă @ sau funcţiile New şi GetMem (prin
care poate rezerva zonă de memorie pentru date dinamice).
Valoarea predefinită de tip referinţă Nil corespunde referinţei către nici
un obiect/dată.
În expresii, valoarea datei spre care punctează o referinţă p este indicată
prin construcţia p^. Acţiunea prin care se identifică o dată prin intermediul unei
variabile de tip referinţă poartă numele de deferenţiere a variabilei.
O referinţă cu tip poate interveni în operaţii de adresare (cu @) sau de
comparare în sensul <> sau =).
Tipul pointer sau referinţă fără tip
Definirea şi utilizarea acestui tip de dată sînt asemănătoare cu cele de la
tipul referinţă cu tip. Deosebirile constau în:
data referită nu are precizat tipul (este nedefinit);
nu se poate utiliza funcţia New pentru a li se atribui valoare.
De exemplu
type adresa=Pointer;
var a:adresa;
59
CONSTANTE CU TIP
O categorie specială de constante este cea a constantelor cu tip.
Declararea lor se face în partea declarativă a blocului prin expresii de forma:
const nume_de_constanta_1 : tip_de_data_1=valoare_1;
[nume_de_constanta_2 : tip_de_data_2=valoare_2;]...
Constantele cu tip sînt similare variabilelor iniţializate (variabile ale căror
valori sînt definite cînd se intră in blocul în care se definesc).Expresiile prin
care se declară conţin atît tipul, cît şi valoarea constantei.
Constantele cu tip se utilizează ca variabilele de acelaşi tip şi pot să apară
în membrul stîng al unei instrucţiuni de atribuire.
Ele sînt iniţializate o singură dată: la începutul programului. Pentru orice
punct de intrare într-o procedură sau funcţie, constantele cu tip declarate local
nu sînt reiniţializate.
Exemple de constante simple cu tip:
const
Min : Integer = 0;
Max : Integer = 9999;
Send : Char = #3;
Constante cu tipul string
Declaraţia unei constante cu tipul string specifică lungimea maximă a
şirului şi valoarea sa iniţială.
Exemple
const LinieNoua: string[2] = #13#10;
Da: string[2] = 'Da';
Constante cu tipul Set Declararea unei constante cu tipul set specifică valoarea mulţimii folosind
expresii constante.
Exemple:
type Cifre = set of 0..9; Litere = set of 'A'..'Z';
const
CifrePare: Cifre = [0, 2, 4, 6, 8];
60
Vocale: Litere = ['A', 'E', 'I', 'O', 'U'];
CifreHexa: set of '0'..'z' = ['0'..'9', 'A'..'F', 'a'...f'];
Constante cu tipul Array Declaraţia unei constante cu tipul array specifică valorile componentelor
sale. Fiecare element al tabloului poate fi de orice tip diferit de file.
Exemple:
type Stare = (Activa, Pasiva, Asteptare); StareM = array[Stare] of
string[9];
const
StareStr: StareM = ('Activa', 'Pasiva', 'Asteptare');
{ Componentele acestei constante sînt: StareStr[Activa] = 'Activa',
StareStr[Pasiva] = 'Pasiva', StareStr[Asteptare] = 'Asteptare' }
Constante cu tipul array of Char
Tablourile de caractere pot fi specificate ca vectori ale căror elemente sînt
caractere sau ca şiruri. În acest sens, declaraţia
const Cifre: array[0..9] of Char = ('0', '1', '2', '3', '4', '5', '6', '7', '8', '9');
este echivalentă cu declaraţia
const Cifre: array[0..9] of Char = '0123456789';
Constante cu tipul ZString
Un ZString este un tablou de caractere care are primul indice 0, iar
ultimul un întreg pozitiv nenul. De exemplu, array[0..X] of Char. Cînd este
permisă sintaxa extinsă (directiva de compilare {$X+} ),un Zşir poate fi
iniţializat cu un şir care este mai scurt decît lungimea declarată a tabloului.
const Nume_De_Fişier = array[0..79] of Char = 'PERSONAL.DAT';
Dacă şirul de inţializare este mai scurt decît dimensiunea tabloului,
caracterele rămase (în dreapta) sînt puse pe NULL (00), deci tabloul va conţine
efectiv un şir care se încheie cu caracterul NULL.
61
Constante cu tipul tablou multidimensional
În cazul tablourilor multidimensionale, constantele pentru fiecare
dimensiune sînt incluse între paranteze. Constantele cele mai interioare
corespund dimensiunilor celor mai din dreapta. De exemplu, în cazul
declaraţiilor
type Cub = array[0..1, 0..1, 0..1] of Integer;
const Tab: Cub = (((0, 1), (2, 3)), ((4, 5), (6, 7)));
avem
Tab[0, 0, 0] = 0 Tab[0, 0, 1] = 1
Tab[0, 1, 0] = 2 Tab[0, 1, 1] = 3
Tab[1, 0, 0] = 4 Tab[1, 0, 1] = 5
Tab[1, 1, 0] = 6 Tab[1, 1, 1] = 7
Constante cu tipul înregistrare
Declaraţia unei constante de tip înregistrare specifică identificatorul şi
valoarea fiecărui cîmp (membru) al înregistrării.
Nu este aplicabilă înregistrărilor care conţin cîmpurile unor fişiere cu tip.
Dacă o înregistrare conţine o variantă se vor specifica numai cîmpurile variantei
selectate.
Exemplu
type Punct = record
X, Y: Real;
end;
Vector = array[0..1] of Punct;
Luna = (Ian, Feb, Mar, Apr, Mai, Iun, Jul, Aug, Sep, Oct, Nov, Dec);
Data = record
D: 1..31;
M: Luna;
Y: 1900..1999;
end;
const Origine: Punct = (X: 0.0; Y: 0.0);
Linie: Vector = ((X: -3.1; Y: 1.5), (X: 5.8; Y: 3.0));
Odata: Data = (D: 2; M: Dec; Y: 1960);
Constante cu tipul pointer Declaraţia unei constante cu tipul pointer utilizează expresii de adresă
constante pentru a specifica valoarea pointerului. Dacă este permisă utilizarea
62
sintaxei extinse (directiva {$X}), o constantă cu tipul PChar poate fi iniţializată
cu un şir de constante.
Exemple:
type Directie = (Stinga, Dreapta, Sus, Jos);
StringPtr = ^String;
NodPtr = ^Nod;
Nod = record
Urmator: NodePtr;
Simbol: StringPtr;
Valoare: Directie;
end;
const
S1: string[3] = 'JOS'; S2: string[3] = 'SUS';
S3: string[7] = 'DREAPTA'; S4: string[6] = 'STINGA';
N1: Nod = (Urmator: nil; Simbol: @S1; Valoare:Jos);
N2: Nod = (Urmator: @N1; Simbol: @S2; Valoare: Sus);
EXEMPLUL 1.
{
Calculeaza valoarea bitului de paritate al unui caracter ASCII si
seteaza-l
astfel incit:
- numarul total de biti 1 sa fie impar (ODD);
- numarul total de biti 1 sa fie par (EVEN);
- bitul sa fie 1 (MARK);
- bitul sa fie 0 (SPACE).
}
uses crt;
type paritate =(EVEN,ODD,MARK,SPACE);
{
Intoarce un sir de caractere alcatuit din valorile bitilor argumentului
}
function binary(n: byte):string;
var i:integer;
s:string;
63
begin
s:='';
for i:=7 downto 0 do
s:=s+chr ((n shr i) and 1 + $30);
binary:=s;
end;
{
intoarce cifra hexazecimala corespunzatoare valorii argumentului
}
function cifra(n:byte):char;
begin
if n<10 then
cifra:=chr(n+$30) { valorile sub 10 se transforma in caracterele '0' etc.}
else
cifra:=chr(n+$37); { valorile peste 9 in literele 'A'..'F'}
end;
{ intoarce valoarea hexazecimala a unui octet}
function hexa(c:byte):string;
begin
hexa:=cifra(c div 16) + cifra(c mod 16);
end;
{ In cazul paritatii EVEN numarul total de biti de 1 trebuie sa fie par,
deci valoarea bitului de paritate este rezultatul intersectiei exclusive a valorilor
bitilor b0-b6 ai caracterului.
In cazul paritatii ODD numarul total de biti de 1 trebuie sa fie impar,
deci valoarea bitului de paritate este complementara intersectiei exclusive a
valorilor
bitilor b0-b6 ai caracterului.
}
function pune( c: byte; fel:paritate) :INTEGER;
var c1: byte; { bitul de paritate setat}
i:integer;
begin
64
c:=c and $7f; { ELIMINA BITUL DE PARITATE }
if fel=MARK then
pune:=c or $80
else
if fel=SPACE then
pune:=c and $7f
else
begin
c1:=ord(fel);
for i:=0 to 6 do
c1:=c1 xor (( c shr i) and 1);
pune:=c or (c1 shl 7);
end;
end;
var c:byte;
begin
clrscr;
while true do begin
write('Tastati un caracter (Incheiati cu <CTRL-BREAK>) ');
c:=byte(readkey);
writeln(#10#13'Caracterul ',chr(c), '(cod ASCII hexazecimal ',hexa(c),
') are valoarea hexazecimala cu paritate: ',
#10#13,' ODD ',hexa(pune(c,ODD)),' ',binary(pune(c,ODD)),
#10#13,' EVEN ',hexa(pune(c,EVEN)),' ',binary(pune(c,EVEN)),
#10#13,' MARK ',hexa(pune(c,MARK)),' ',binary(pune(c,MARK)),
#10#13+' SPACE ',hexa(pune(c,SPACE)),'
',binary(pune(c,SPACE)));
end;
end.
EXEMPLUL 2.
(* Alcatuieste toate numerele binare de cel mult n cifre *)
65
program contor;
uses crt;
var n:integer; (* numar de cifre *)
a: array [1..10] of byte; (* cifrele numarului *)
(*in aceasta functie se alcatuieste un numar pornind de la precedentul *)
function alcatuieste:boolean;
var i:integer;
begin
alcatuieste:=true;
for i:=n downto 1 do
if a[i]=0 then
begin
a[i]:=1;
alcatuieste:=false;
exit;
end
else
a[i]:=0;
end;
var i:integer;
begin
repeat
write('n=');
readln(n);
until n in [1..10];
for i:=1 to n do a[i]:=0;
repeat
writeln;
i:=1;
while(i<n) and (a[i]=0) do
begin
inc(i);
write('..');
end;
for i:=i to n do write(a[i]:2);
until alcatuieste;
readln;end.
66
UNITĂŢI DE PROGRAM PASCAL
O unitate de program Pascal este o colecţie de elemente (constante, tipuri
şi variabile) , funcţii şi proceduri şi o secţiune de iniţializare organizate într-un
bloc compilabil separat.
O unitate de program are două părţi: interfaţa şi implementarea. Interfaţa
este alcătuită din elementele accesibile din exterior. Partea de implementare este
alcătuită din constante, variabile, funcţii şi proceduri, toate inaccesibile din
exterior şi funcţii şi proceduri descrise în interfaţă. Forma generală a unei unităţi
de program este
UNIT nume;
INTERFACE
{ declaraţii }
IMPLEMENTATION
{lista de declaraţii locale}
[BEGIN
{secvenţă de iniţializare}
] end.
Secvenţa de iniţializare poate lipsi şi conţine instrucţiuni ce trebuie
executate înaintea începerii execuţiei programului principal (pentru iniţializarea
unor elemente).
Un program sau unitate de program care doreşte să utilizeze unitatea U
trebuie să declare acest lucru explicit sub forma uses U;
Există unităţi de Program standard (oferite de mediul TURBO PASCAL)
cum sînt system (singura care nu trebuie declarată), crt, dos, etc.
Prezentăm în continuare o unitate de program PASCAL care defineşte
tipul virtual de dată număr raţional.
unit ura;
interface
type rational=record
numarator:integer;
67
numitor:integer;
end;
procedure aduna(a,b:rational;var suma:rational);
procedure scade(a,b:rational;var diferenta: rational);
procedure inmulteste(a,b:rational; var produs:rational);
procedure imparte(a,b:rational; var cit:rational);
procedure citeste(var r:rational);
procedure tipareste(r:rational);
function p_intreaga(r:rational):integer;
function mai_mare(a,b:rational):boolean;
function estezero(r:rational):boolean;
implementation
function cmmdc(m,n:integer):integer;
begin
if n=0 then
cmmdc:=m
else
cmmdc:=cmmdc(n, m mod n);
end;
function cmmmc(m,n:integer): integer;
begin
cmmmc:=m*n div cmmdc(m,n);
end;
procedure simplifica(var r:rational);
var c:integer;
begin
c:=cmmdc(r.numarator,r.numitor);
if c*r.numitor<0 then
c:=-c;
r.numarator:=r.numarator div c;
r.numitor:=r.Numitor div c;
end;
function estezero;
begin
estezero:=r.numarator=0;
end;
68
procedure aduna;
begin
suma.numarator:=a.numarator*b.numitor+b.numarator*a.numitor;
suma.numitor:=a.numitor*b.numitor;
simplifica(suma);
end;
procedure scade;
begin
diferenta.numarator:=a.numarator*b.numitor-b.numarator*a.numitor;
diferenta.numitor:=a.numitor*b.numitor;
simplifica(diferenta);
end;
procedure inmulteste;
begin
produs.numarator:=a.numarator*b.numarator;
produs.numitor:=a.numitor*b.numitor;
simplifica(produs);
end;
procedure imparte;
begin
cit.numarator:=a.numarator*b.numitor;
cit.numitor:=a.numitor*b.numarator;
simplifica(cit);
end;
procedure citeste;
begin
write('Numaratorul = '); read(r.numarator);
write('Numitorul = '); read(r.numitor);
end;
procedure tipareste;
begin
write(r.numarator); write('/'); write(r.numitor);
end;
function p_intreaga;
69
begin
p_intreaga:=r.numarator div r.numitor;
end;
function mai_mare;
begin
mai_mare:=(a.numarator*b.numitor-a.numitor*b.numarator)/(a.numitor*b.nu
mitor)>=0;
end;
end.
În exemplul de mai jos, unitatea de program Pascal Ura este folosită
pentru rezolvarea sistemelor de ecuaţii liniare cu coeficienţi raţionali.
program sistem;
uses ura,crt;
const n=3;
type vector=array [1..n] of rational;
matrice=array [1..n] of vector;
var a: matrice;
b: vector;
cod,i,k:integer;
{ citeste matricea extinsa asociata sistemului }
procedure citim(var a:matrice;var b:vector);
var i,j:integer;
begin
clrscr;
for i:=1 to n do { coeficientii se dau pe linie }
begin
for j:=1 to n do
begin
write('a(',i,',',j,') '); citeste(a[i,j]);
end;
write('b(',i,')'); citeste(b[i]); { citeste termenul liber }
end;
end;
70
procedure Gauss( n: integer;
var a:matrice;
var b:vector;
var cod:integer);
var i,j: integer;
var r:rational;
(* schimba intre ele liniile i si j *)
procedure schimba(i,j:integer);
var k: integer;
aux:rational;
begin { se putea porni cu indicele de la i,fiindca pina acolo toate elem sunt
zero}
for k:=1 to n do begin
aux:=a[i,k];
a[i,k]:=a[j,k];
a[j,k]:=aux;
end;
aux:=b[i]; b[i]:=b[j]; b[j]:=aux; { schimba si termenul liber }
end;
(* imparte ecuatia i cu r *)
procedure impart(i:integer;r:rational);
var k: integer;
begin
for k:=1 to n do
imparte(a[i,k],r,a[i,k]);
imparte(b[i],r,b[i]);
end;
procedure elimina(i,j:integer; r:rational); { elimina x[i] din ecuatia j }
var k:integer;
r1: rational;
begin
for k:=i to n do
begin
inmulteste(r,a[i,k],r1);
scade(a[j,k],r1,a[j,k]);
71
end;
inmulteste(r,b[i],r1);
scade(b[j],r1,b[j]);
end;
{ cauta un coeficient nenul pe linia i }
procedure cauta(var i,j:integer; var c:integer);
begin
if estezero(a[i,j]) then c:=0 else c:=1;
j:=i+1;
while (j<=n) and (c=0) do
if estezero(a[i,j]) then
j:=j+1
else
c:=1;
end;
(*inceputul metodei Gauss *)
begin
i:=1; cod:=1;
while(cod=1) and (i<n) do
begin
cauta(i,j,cod);
if cod=1 then begin
schimba(i,j);
r:=a[i,j];
impart(i,r);
for j:=i+1 to n do
begin
r:=a[i,j];
elimina(i,j,r);
end
end
else
cod:=0;
end;
end; {Gauss}
procedure rezolva( n:integer;
a:matrice;
72
var b:vector;
var ind: integer);
var r,r1:rational;
i,k: integer;
begin
r1:=b[n]; ind:=1;
if estezero(a[n,n]) then ind:=0 else imparte(r1,a[n,n],b[n]);
i:=n-1;
while(ind=1) and (i>=1) do
begin
r1:=b[i];
for k:=i+1 to n do
begin
r:=a[i,k];
inmulteste(r,b[k],r);
scade(r1,r,r1)
end;
if estezero(a[i,i]) then ind:=0 else imparte(r1,a[i,i],b[i]);
i:=i-1;
end;
end;
begin
citim(a,b);
gauss(n,a,b,cod);
rezolva(n,a,b,cod);
if cod=0 then writeln('Sistemul nu este Cramer')
else begin
writeln(#13#10'Solutia sistemului este ');
for i:=1 to n do begin
write('x(',i,')='); tipareste(b[i]); writeln;
end;
End;
end.
Tipul de dată file
A fost introdus pentru a face legătura cu perifericele unui calculator. El
respectă structura fişierelor de pe discul magnetic într-o formă proprie.
73
Un fişier este alcătuit dintr-o listă liniară de înregistrări (componente sau
articole), fiecare avînd sau nu un tip. Tipul componentelor trecuie să difere de
tipul file.
Dacă fişierul nu are tip, se consideră alcătuit din înregistrări de lungime
fixă. Lungimea înregistrărilor se declară la deschiderea sa. Accesul la articolele
fşierelor fără tip poate fi secvenţial şi direct (prin intermediul numărului de
articol - primul articol avînd numărul 0).
Fişierele predefinite de tip text conţin caractere care sînt organizate în
linii sau rînduri care sînt delimitate între ele prin caracterele CR LF. Sfîrşitul de
fişier este marcat prin caracterul CTRL Z (codul hexazecimal 1A). Accesul este
numai secvenţial.
Prezentăm mai jos cîteva instrucţiuni de declarare de fişiere:
type
Persoana = record
Nume: string[15];
Prenume : string[25];
Adresa : string[35];
end;
Var Fisier_persoane : file of Persoana;
Fiser_de_Numere : file of Integer;
FisierDeManevra : file;
Scrisoare : Text;
Prezentăm în continuare proceduri şi funcţii relative la tratarea fişierelor.
Acestea fac parte din unitatea de program Pascal System.
Assign
asociază numele unui fişier extern cu o variabilă PASCAL de tip fişier;
are declaraţia
procedure Assign(var f ;Sir:String);
unde f este o variabilă fişier de orice tip, iar Sir expresie de tip şir de
caractere (sau o expresie de tip Pchar în cazul sintaxei extinse). Toate
operaţiile asupra lui f vor acţiona asupra fişierului extern identificat prin
Sir. Sir este de forma [Drive:][Cale]Nume[.Ext] , unde Drive reprezintă
numele simbolic al unităţii de disc pe care se află fişierul, Cale calea de
căutare, Nume şi Ext numele şi extensia numelui fişierului. Elementele
cuprinse între [] sînt opţionale. Sînt valabile regulile din MS DOS privind
identificarea fişierelor. Lungimea şirului de caractere Sir trebuie să fie
cuprinsă intre 0 şi 79. În cazul în care şirul are lungimea 0, variabila fişier
f este asociată fişierului standard de intrare (dacă fişierul se deschide cu
74
Reset) sau fişierului standard de ieşire (dacă fişierul se deschide cu
procedura Rewrite);
asocierea dintre f şi fişierul Sir rămîne valabilă pînă cînd variabila fişier f
este utilizată într-un alt apel al funcţiei Assign;
nu poate fi utilizată pentru un fişier deschis.
Exemplu
var F1: Text;
F2: file of Integer;
Assign(F1, '');{ f1 este asociat fisierului standard de intrare sau iesire }
Assign(F2, ‘date ‘);
IOResult
întoarce modul de încheiere a ultimei operaţii de deschidere de fişier, citire
sau scriere şi pune pe 0 indicatorul intern de eroare;
are declaraţia
function IOResult: Integer;
întoarce 0 în cazul în care operaţiile s-au încheiat normal;
pentru a se putea verifica modul de terminare a operaţiilor de mai sus, textul
sursă trebuie să conţină directiva de compilare {$I-}. La întîlnirea unei erori,
toate operaţiile care urmează pînă la apelul funcţiei IOResult sînt ignorate.
Reset
deschide un fişier existent;
are declaraţia
procedure Reset(var F : File[; Lungime: Word ] );
unde F este un fişier de orice tip care a fost asociat cu un fişier extern,
Lungime specifică dimensiunea articolului în cazul fişierelor fără
tip.Valoarea sa implicită este 128;
dacă fişierul extern asociat variabilei F nu există, procedura Reset se încheie
anormal. Dacă la apelul procedurii F este deschis, el este închis, apoi
redeschis;
poziţia curentă în fişier (locul din care se va citi sau se va scrie) este
începutul fişierului. Funcţia Eof care are ca parametru fişierul F va avea
valoare True numai dacă fişierul este vid.
dacă F este de tipul text, asupra lui F se pot efectua numai operaţii de citire;
dacă directiva de compilare {$I-} este prezentă, funcţia IOResult întoarce
valoarea 0, iar în caz contrar codul de eroare.
Exemplu.
75
Funcţia de mai jos întoarce valoarea True, dacă fişierul identificat prin
parametrul FileName există
function Exista(FileName: String): Boolean;
var F: file;
begin
{$I-}
Assign(F, FileName);
{ deschide si inchide fisierul }
Reset(F); Close(F);
{$I+}
Exista := (IOResult = 0) and (FileName <> '');
end;
Rewrite
crează şi deschide un fişier nou;
are declaraţia
procedure Rewrite(var F: File [; Lungime: Word ] );
în care F este o variabilă file de orice tip asociată cu Assign unui fişier
extern. Parametrul Lungime poate fi specificat în cazul fişierelor fără tip.
Valoare implicită (prin lipsă) este 128;
dacă fişierul este deschis, el se închide. Dacă fişierul există, el este şters şi se
crează altul nou;
poziţia curentă în fişier este începutul fişierului;
în cazul fişierelor de tip text, singura operaţie permisă este scrierea;
după apelul funcţiei Rewrite, Eof(F) are valoarea True. În prezenţa directivei
de compilare {$I-}, funcţia IOResult întoarce valoarea 0 în cazul în care
deschiderea a reuşit, altfel aceasta întoarce un cod de eroare.
Exemplu
var F: Text;
{...}
Assign(F, 'scris');
Rewrite(F);
{...}
Append
deschide un fişier text pentru scriere în continuare (la sfîrşitul său);
are declaraţia
procedure Append(var f: Text);
unde f este o variabilă file de tip text care a făcut obiectul unei asocieri cu
un fişier extern (procedura Assign). Acesta din urmă trebuie să existe.
76
Poziţia curentă în fişier este sfîrşitul său sau, dacă în ultimii 128 de octeţi
ai fişierului este prezent caracterul CTRL Z, poziţia acestuia;
dacă fişierul este deschis, el este închis, apoi redeschis;
singura operaţie permisă este cea de scriere;
funcţia IOResult întoarce 0 sau codul de eroare, dacă este prezentă directiva de
compilare {$I-}.
Exemplu
var F: Text;
begin
Assign(F, 'TEST.TXT');
Rewrite(F); { Creaza un fisier }
Writeln(F, 'text initial');
Close(F); { inchide fisierul }
Append(F); {deschide fisierul pentru scriere in continuare }
Writeln(F, 'Text adaugat');
Close(F); { inchide fisierul }
end.
Close
închide un fişier deschis cu Reset, Rewrite sau Append;
are declaraţia
procedure Close(var F);
dacă fişierul F este deschis pentru scriere fişierul extern asociat lui F este
completat cu ultimele date care nu au fost scrise;
folosiţi IOResult pentru a verifica modul în care s-a terminat operaţia de
închidere.
Flush
transferă conţinutul zonei tampon pe disc sau goleşte zona tampon;
are declaraţia
flush(Var F: Text);
pentru a accelera transferul de date dintre memoria internă şi suportul
magnetic (discul), pentru citire şi scriere se utilizează o zonă de memorie
suplimentară (diferită de aceea în care citim componente ale fişierului)
numită zonă tampon sau buffer. Citirea şi scrierea efectivă au loc la prima
citire, în momentul în care zona tampon este goală (în cazul citirilor) sau
plină (în cazul scrierilor), cînd fişierul este închis, la terminarea normală a
77
programului sau cînd se cere în mod expres acest lucru.
Truncate
trunchiază un fişier începînd cu poziţia curentă;
are declaraţia
procedure Truncate(var F);
unde fişierul f este un fişier deschis şi de orice tip diferit de text. Toate
înregistrările fişierului începînd cu poziţia curentă sînt şterse, iar poziţia
curentă în fişier este sfîrşitul fişierului;
folosiţi IOResult pentru a verifica modul de încheiere a operaţiei de
trunchiere.
Uses crt, dos;
var
f: file of Integer;
i,j: Integer;
begin
Assign(f,'date');
Rewrite(f);
for i := 1 to 6 do Write(f,i);
Writeln('Continutul fisierului inainte de trunchiere:');
Reset(f);
while not Eof(f) do
begin
Read(f,i);
Writeln(i);
end;
Reset(f);
for i := 1 to 3 do
Read(f,j); { Citeste primele 3 articole}
Truncate(f); { Trunchiaza fisierul }
Writeln;
Writeln('Continutul fisierului dupa trunchiere:');
Reset(f);
while not Eof(f) do
begin
Read(f,i);
Writeln(i);
end;
78
Close(f);
Erase(f); { sterge fisierul }
end.
Seek
mută poziţia curentă a unui fişier la o componentă specificată;
are declaraţia
procedure Seek(var F; N: Longint);
unde F este o variabilă de tip file (diferit de text) deschis , iar N o
expresie de tipul LongInt;
după apelul procedurii, poziţia curentă devine cea a componentei a N-a,
prima componentă avînd numărul 0;
apelul seek(f,sizeof(f)) mută poziţia curentă la sfîrşitul fişierului;
folosiţi funcţia IOResult pentru a vedea dacă operaţia de poziţionare s-a
încheiat corect sau nu.
FilePos
întoarce poziţia curentă a unui fişier;
are declaraţia
function FilePos(var F): Longint;
în care F este o variabilă fişier diferită de tipul text, asociată unui fişier
deschis;
poziţia curentă corespunzătoare începutului de fişier este 0, iar poziţia
curentă corespunzătoare sfîrşitului de fişier este este FileSize(F).
Erase
şterge un fişier extern ;
are declaraţia
procedure Erase(var F);
în care F este o variabilă de tip file asociată unui fişier extern cu Assign;
fişierul nu trebuie să fie deschis !
folosiţi Ioresult pentru a verifica modul de încheiere a operaţiei de ştergere.
Rename
schimbă numele unui fişier extern ;
are declaraţia
procedure Rename(var F; Nume_nou);
în care F este o variabilă fişier de orice tip, iar Nume_nou este o expresie
de tip şir sau un pointer de tipul Char dacă este permisă sintaxa extinsă;
fişierul extern va primi numele Nume_nou;
79
IOResult întoarce 0 în cazul în care operaţia de schimbare a numelui a reuşit
şi #0 în caz contrar.
FileSize
întoarce dimensiunea curentă a fişierului în număr de componente;
are declaraţia
function FileSize(var F): Longint;
fişierul trebuie să fie deschis şi nu trebuie să aibă tipul text. Dacă fişierul este
fără tip, mărimea unei componente se precizează la deschidere (Reset sau
Rewrite);
Mărimea în octeţi a fişierului este FileSize(F)*sizeof(tip_componentă);
dacă fişierul este vid, dimensiunea sa este 0.
Read
pentru fişiere de tip text:
citeşte din fişierul text valorile unor variabile de tip numeric, caracter sau şir.
În cazul variabilelor numerice citirea începe cu primul caracter diferit de
spaţiu, Tab, LF/CR şi se încheie la întîlnirea unui caracter spaţiu, Tab,
CR/LF sau CTRL Z, valoarea şirului de caractere citit fiind convertită la
tipul variabilei. În cazul variabilelor Char se citeşte un caracter, iar pentru un
şir de caractere se citeşte pînă la sfîrşit de linie (CR/LF) sau pînă la CTRL Z
(în cazul în care lungimea şirului citit este mai mare decît a variabilei şir are
loc o trunchiere a valorii citite). În nici o situaţie nu se trece la linia
următoare;
are declaraţia
Procedure Read([Var F:Text;]var v1[,v2]...);
dacă F lipseşte, citirea are loc din fişierul standard de intrare, iar datele citite
sînt afişate în ecou pe monitor (sau fişierul standard de ieşire). Citirea este
efectivă după acţionarea tastei Enter;
după primul Read care conţine variabile şir, orice citire ulterioară va
întoarce un şir de lungime 0. Pentru a citi valori string succesive se va utiliza
procedura Readln;
pentru fişiere cu tip:
se citesc din fişier valorile unor variabile care au tipul identic cu tipul
fişierului;
are declaraţia
procedure Read(F , var V1 [, V2,...,Vn ] );
80
Readln
execută operaţiile de la Read şi trece la următoarea linie a fişierului;
are declaraţia
procedure Readln([ var F: Text; ] V1 [, V2, ...,Vn ]);
Write
în cazul fişierelor cu tip scrie o variabilă într-o componentă a fişierului, iar în
cazul fişierelor text scrie una sau mai multe valori în fişier;
are declaraţia
pentru fişiere cu tip
procedure Write(F, V1 [, V2,...,Vn ] );
pentru fişiere text
procedure Write( [ var F: Text; ] P1 [,P2,...,Pn ] );
parametrii P pot conţine specificaţii de lungime şi precizie (număr de
zecimale). Fiecare expresie P poate fi de tipul Char, Integer, Real, String sau
Boolean.
Writeln
execută procedura Write după care scrie CR/LF
are declaraţia
procedure Writeln([ var F: Text; ] P1 [, P2, ...,Pn ] );
este utilizabilă în cazul fişierelor de tip text .
SeekEof
întoarce valoarea true dacă fişierul cu tipul text nu conţine (începînd cu
poziţia curentă) decît caractere albe ;
are declaraţia
function SeekEof [ (var F: Text) ]: Boolean;
SeekEoln
întoarce valoarea true dacă, începînd cu poziţia curentă şi pînă la sfîrşitul
liniei curente din fişierul text, sînt numai caractere albe;
are declaraţia
function SeekEoln [ (var F: Text) ]: Boolean;
var
f : Text;
j : Integer;
81
begin
Assign(f,'TEST.TXT');
Rewrite(f);
{ Creaza un fisier cu 8 numere si spatiu la finele fiecarei linii }
Writeln(f,'1 2 3 4 ');
Writeln(f,'5 6 7 8 ');
Reset(f);
{
Citeste numerele. SeekEoln intoarce TRUE daca nu mai sint numere in
linia curenta, iar SeekEof intoarce TRUE daca nu mai exista caractere diferite
de caractere albe
}
while not SeekEof(f) do
begin
if SeekEoln(f) then
Readln; { Treci la o alta linie }
Read(f,j);
Writeln(j);
end;
end.
Eoln
întoarce valoarea true dacă pointerul de fişier asociat unui fişier text
punctează pe sfîrşit de linie (caracterele CR/LF) sau pe CTRL Z;
are declaraţia
function Eoln [(var F: Text) ]: Boolean;
Eof
întoarce valoarea true dacă poziţia curentă corespunde ultimului octet al unui
fişier fără tip, CTRL Z pentru fişiere text sau corespunde unei poziţii situate
după ultima înregistrare a unui fişier cu tip;
are declaraţia
function Eof(var F): Boolean;
Exemplu
Afişează conţinutul fişierului \autoexec.bat
var
F: Text;
Ch: Char;
begin
82
Assign(F, ‘\autoexec.bat ‘);
Reset(F);
while not Eof(F) do
begin
Read(F, Ch);
Write(Ch); { Afiseaza textul }
end;
end.
OPERAŢII CU FI ŞIERE FĂRĂ TIP
BlockRead
citeşte una sau mai multe înregistrări;
are declaraţia
procedure BlockRead(var F: File; var Buf; Nr: Word [; var Rezt:
Word]);
unde
F - este o variabilă de tip fişier fără tip care corespunde unui fişier
deschis;
Buf - variabilă de orice tip;
Nr - este o expresie de tip Word;
Rez este o variabilă de tip Word;
BlockRead citeşte cel mult Nr înregistrări din fişierul F în memorie, începînd
de la primul octet al lui Buf. Număr de înregistrări citite complet (mai mic
sau egal ca Nr) este întors în parametrul opţional Rez. Dacă acesta nu este
specificat şi numărul de înregistrări citite diferă de Nr, operaţia de citire se
încheie cu eroare de. Blocul transferat în memorie ocupă cel mult
Nr*lungime_înreg unde lungime_înreg a fost specificată la deschiderea
fişierului (valoarea sa implicită este 128). Mărimea blocului transferat nu
poate depăsi 65535 (64K)După citire, poziţia în fişier este deplasată cu Rez
articole (componente)spre sfîrşitul fişierului;
În prezenţa directivei {$I-}, funcţia IOResult întoarce o valoare nenulă în
cazul unei erori.
BlockWrite
scrie una sau mai multe înregistrări într-un fişier fără tip;
are declaraţia
procedure BlockWrite(var f: File; var Buf; Nr: Word [; var Rez:
Word]);
83
unde
F - este o variabilă de tip fişier fără tip corespunzătoare unui fişier
deschis;
Buf - variabilă de orice;
Nr - este o expresie de tip Word;
Rez este o variabilă de tip Word;
procedura scrie cel mult Nr înregistrări înfişierul F de la adresa Buf.
Numărul de înregistrări scrise efectiv este întors în parametrul opţional Rez.
Dacă acest parametru opţional nu este folosit şi Rez<Nr, apelul se încheie cu
eroare;
lungimea blocului transferat nu poate depăşi 64 K;
Poziţia în fişier este mutată cu Rez întregistrări spre sfîrşitul fişierului;
dacă este prezentă directiva {I-}, funcţia IOResult întoarce o valoare nenulă
în cazul unei erori.
Funcţia ParamStr, ca de altfel toate funcţiile şi procedurile prezentate la
acest tip de date, fac parte din unitatea de program PASCAL System. Iată care
este modelul de apel şi valoarea întoarsă.
ParamStr - întoarce un parametru al linie de comandă
delaraţia sa este
function ParamStr(Nr:word): String;
întoarce parametru cu numărul Nr de pe linia de comandă sau şirul vid dacă
Nr este mai mare decît ParamCount (numarul total).. ParamStr(0) întoarce
calea şi numele programului care se execută.
Exemplu
Copiaţi un fişier. Numele fişierului sursă şi numele fişierului destinaţie se
vor de pe linia de comandă corespunzătoare punerii în execuţie a programului
executabil.
var
De_unde, Unde: file;
NumCit, NumScris: Word;
Buf: array[1..2048] of Char;
begin
Assign(De_unde, ParamStr(1)); { Open input file }
Reset(De_unde, 1); { Record size = 1 }
84
Assign(Unde, ParamStr(2)); { Open output file }
Rewrite(Unde, 1); { Record size = 1 }
Writeln('Se copiaza ', FileSize(De unde), ' octeti...');
repeat
BlockRead(de_unde, Buf, SizeOf(Buf), NumCit);
BlockWrite(Unde, Buf, NumCit, NumScris);
until (NumCit = 0) or (NumScris <> NumCit);
Close(De_unde);
Close(Unde);
end.
85
Unitatea de program Pascal System
Vom prezenta procedurile şi funcţiile acestei unităţi de program Pascal
ţinînd seama de categoria lor.
Funcţii matematice
Abs
întoarce valoarea absolută a argumentului;
are declaraţia
function Abs(x): (acelaşi tip cu argumentul x);
ArcTan
întoarce arctangenta argumentului;
are declaraţia
function ArcTan(X:Real): Real;
deşi Pascal nu are funcţie tangentă, ea se poate calcula ţinînd seama de
relaţia:
tg(x)=sin(x)/cos(x);
Cos
întoarce cosinusul argumentului;
are declaraţia
function Cos(x:Real): real;
argumentul x se exprimă în radiani;
sin
întoarce sinusul argumentului care este un unghi exprimat în radiani;
declaraţia ca la funcţia cos;
Exp
intoarce ex ;
are declaraţia
function exp(x:real):Real;
Int
întoarce partea întreagă a argumentului;
are declaraţia
function Int(x:Real): Real;
86
Frac
întoarce partea fracţionară a argumentului;
are declaraţia
function Fract(X:Real):Real;
partea fracţionară a valorii x este x-Int(x);
Ln
întoarce logaritmul natural al argumentului;
are declaraţia
function Ln(X:Real): Real;
Pi
întoarce valoarea numărului iraţional π;
are declaraţia
function Pi: Real;
Sqr
întoarce pătratul argumentului;
are declaraţia
function Sqr(X): (acelaşi tip cu x);
Sqrt
întoarce radicalul argumentului;
are declaraţia
function Sqrt(X:Real): Real;
inc
incrementează (măreşte) valoarea unei variabile cu un număr ;
are declaraţia
procedure Inc(Var x[;N: Longint]);
variabila poate fi de tip scalar sau pointer de tip Pchar. În lipsă, valoarea lui
N este 1.
Dec
decrementează (micşorează) valoarea unei variabile cu un număr ;
are declaraţia
procedure Dec(Var x[;N: LongInt]);
sînt valabile observaţiile de la procedura Inc ;
87
Proceduri şi funcţii de gestionare dinamică a memoriei (de alocare dinamică de
memorie)
New
crează o variabilă dinamică şi setează o variabilă de tip referinţă pe adresa
zonei alocate;
are declaraţia
procedure New(Var P:pointer);
Dispose
eliberează o variabilă dinamică;
are declaraţia
procedure Dispose(Var P:Pointer);
FreeMem
eliberează o variabilă dinamică de mărime dată;
are declaraţia
procedure FreeMem(Var P: Pointer; mărime:Word);
GetMem
crează o variabilă dinamică de mărime specificată şi scrie adresa blocului în
variabila de tip Pointer;
are declaraţia
procedure Getmem(var P:pointer; mărime: Word);
mărimea zonei de memorie rezervată se exprimă în număr de octeţi
MaxAvail
întoarce mărimea în octeţi al celui mai mare bloc de memorie continuă şi
liberă din zona de manevră (Heap);
are declaraţia
function MaxAvail: LongInt;
MemAvail
întoarce dimensiunea în octeţi a memoriei Heap disponibile
declaraţie ca la MaxAvail;
Control de procese
Exit
abandonează blocul curent. Dacă acesta este blocul principal, încheie
execuţia programului;
88
are declaraţia
procedure Exit;
Halt
încheie execuţia programului şi predă controlului sistemului de operare;
are declaraţia
procedure Halt(Cod_retur:Word);
Proceduri şi funcţii de citire/scriere
se vor vedea şi funcţiile de la tipul de date File
Funcţii şi proceduri diverse
Assigned
testează dacă un pointer sau o variabilă au valoarea Nil;
are declaraţia
function Assigned(var P):Boolean;
întoarce valoarea True dacă P<>Nil;
ChDir
schimbă directorul curent;
are declaraţia
procedure ChDir(S: String);
S este un şir sau un pointer Pchar care conţine numele directorului;
dacă este prezentă directiva {$I+} IOResult furnizează codul de eroare sau 0
în caz de reuşită;
GetDir
întoarce directorul curent pentru un disc specificat;
are declaraţia
procedure GetDir(Disc:Byte; Var Director:String);
Disc =0 pentru discul de lucru, 1 pentru A, 2 pentru B, 3 pentru C etc.
Numele directorului curent va fi depus în variabila String S;
MkDir
crează un director;
are declaraţia
procedure MkDir(S:String);
S este un şir care conţine numele directorului , poate conţine şi numele
simbolic al discului;
RmDir
89
şterge un director vid;
are declaraţia
Procedure RmDir(S:string);
S conţine numele directorului (ca la MS DOS);
Exclude
elimină dintr-o mulţime un element;
are declaraţia
procedure Exclude(var S: Set Of T; Element : T);
elementele mulţimii sînt de tipul T;
Include
adaugă un element la o multime ;
are declaraţia
procedure înclude(var S: Set Of T; Element : T);
elementele mulţimii sînt de tipul T;
FillChar
iniţializează o zonă de memorie cu o valoare specificată (cuprinsă între
0..255) ;
are declaraţia
procedure FillChar(Var X; Lungime: Word; Valoare);
în urma execuţiei procedurii Lungime octeţi a zonei de memorie X vor fi
puşi pe Valoare;
Hi
întoarce octetul mai semnificativ a unei date de tipul Integer sau Word;
are declaraţia
function Hi(X): Byte;
Lo
întoarce octetul mai puţin semnificativ a unei date de tipul Integer sau Word;
are declaraţia
function Lo(X): Byte;
Swap
schimbă între ei octeţii semnificativ şi nesemnificativ al unui element de tip
Integer sau Word. Dacă valoarea iniţială a unui element X este
256*Hi(X0+Lo(x), după execuţia funcţiei va avea valoarea 256*Lo(X)+
90
Hi(X);
are declaraţia
function Swap(X): (Tipul lui X);
Move
copiază un număr de octeţi dintr-o zonă de memorie în alta;
are declaraţia
procedure Move(Var Suirsa, Destinaţie; Lungime: Word);
ParamCount
întoarce numărul de elemente ale liniei de comandă utilizată la punerea în
execuţie a programului;
are declaraţia
function ParamCount: Word ;
ParamStr
întoarce valoarea parametrului cu numărul de ordine precizat (parametrul cu
numărul 0 corespunde specificatorului complet asociat programului
executabil);
are declaraţia
function ParamStr(Număr : Word) :String;
Random
generează un număr aleator situat în intervalul [0, valoare) ;
are declaraţia
function Random(Valoare: Word): Real;
dacă Valoare lipseşte se consideră 1.
Randomize
iniţalizează variabila RandSeed declarată în unitatea Pascal System pe baza
ceasului sistem
are declaraţia
procedure Randomize;
SizeOf
întoarce mărimea zonei de memoriei necesară pentru memorarea unui
element (variabilă, tip de dată etc.);
are declaraţia
function SizeOf(X) : Word;
91
UpCase
converteşte o literă mică în literă mare;
are declaraţia
function UpCase(Char: caracter): Char;
întoarce valoarea convertită;
Length
determină lungimea unui şir de caractere;
are declaraţia
function Length(S: String): Integer;
lungimea şirului poate fi obţinută şi cu ajutorul expresiei Ord(S[0])
Concat
concatenează două sau mai multe şiruri de caractere ( a concatena şirul X cu
şirul Y înseamnă a adăuga la sfîrşitul şirului X caracterele din şirul Y);
are declaraţia
function Concat(S1,S2[,S3]...:String): String;
întoarce rezultatul operaţiei;
Copy
extrage un subşir dintr-un şir;
are declaraţia
function Copy(S: String; De_Unde, Lungime: Word): String;
este întors subşirul de caractere format din Lungime caractere din sirul S
începînd cu caracterul de pe poziţia De_Unde;
Delete
şterge dintr-un şir un subşir;
are declaraţia
procedure Delete(Var S: String; De_unde,Lungime: Word);
Insert
inserează un subşir într-un şir;
are declaraţia
procedure Insert(SubSir:string; Var Sir: string; De_unde:
Integer);
Pos
92
întoarce 0 sau locul din care începe prima apariţie a unui subşir într-un şir
are declaraţia
function Pos(SubSir,Sir:String):Byte;
Str
converteşte o expresie de tip numeric în şir de caractere;
are declaraţia
procedure Str(Expresie[:Numar_de_caractere{:Din_care_zecimale]];
Var S: String);
Val
converteşte un şir de caractere sau o parte a sa într-o valoare numerică pe
care o atribuie unei variabile;
are declaraţia
procedure Val(S: String; Var V; Var
Numar_de_caractere_convertite);
pentru ca programul să nu se încheie cu o eroare folosiţi directiva de
compilare {$R+}.
Unitatea de program PASCAL CRT
Imaginile afişate pe ecran sînt de două tipuri: text şi grafice. Adaptoarele
video au două moduri de lucru: un mod text şi un mod grafic. În modul text, se
pot afişa numai texte, pe cînd în modul grafic se pot afişa texte şi grafice. În
modul text cea mai mică unitate afişabilă este caracterul. Ecranul este împărţit
în linii (dispuse pe verticală), iar liniile în coloane. Poziţia unui caracter pe
ecran este dată de numărul liniei şi coloanei.
Procedurile şi funcţiile din unitatea Pascal Crt gestionează activitatea
ecranului în modul text şi a difuzorului extern.
În untitatea Crt sînt definite următoarele constante
moduri text:
BW40=0 - adaptor color B/W (alb/negru) 25 de linii a 40 de
coloane;
CO40= 1 - adaptor color 25 de linii a 40 de coloane;
BW80=2 - adaptor color B/W 25 de linii a 80 coloane;
CO80 = 3 - adaptor color 25 linii a 80 de coloane;
MONO = 7 Adaptor monocrom B/W 25 linii a 80 coloane;
culori pentru fond şi pentru text: Culoare
Nume constantă
valoare
93
Culoare
Nume constantă
valoare
Negru
Black
0
Albastru
Blue
1
Verde
gree
2
Cian
Cyan
3
Roşu
Red
4
Magenta
Magenta
5
Brun
Brown
6
Gri deschis
LightGray
7
Gri închis
DarkGray
8
Albastru deschis
LightBlue
9
verde deschis
LightGreen
10
Cian deschis
LightCyan
11
Roşu deschis
LightRed
1
Magenta decshis
LightMagenta
12
galben
Yellow
14
Alb
White
15
Pentru fond se pot folosi culorile 0 - 7, iar pentru text 0-15. Pentru a scrie
un text clipitor, adăugaţi la numărul culorii textului constanta Blink (128).
În unitatea de program Pascal Crt sînt definite următoarele variabile:
CheckBreak - variabilă booleană. Dacă are valoarea true, programul
executabil poate fi întrerupt cu Ctrl-Break sau CTRl-C. Valoarea implicită
este True ;
CheckEof - variabilă booleană. Dacă are valoarea True, combinaţia de taste
Ctrl-Z este interpretată ca sfîrşitul fişierului asociat lui Crt. Valoarea
implicită este False ;
DirectVideo - variabilă booleană. Dacă are valoare true, scrierile au loc
94
direct în memoria ecran, altfel se fac prin intermediul Bios-ului;
LastMode - variabilă de tip Word care conţine modul text anterior modului
grafic. Variabila este modificată la fiecare apel al procedurii TextMode;
TextAttr - variabilă de tip Byte care conţine:
- biţii 0-3 culoarea textului;
- biţii 4-6 culoarea fondului;
- bitul 7 - cod pentru Blink;
WindMin - variabilă de tip Word care conţine coordonatele punctului
(stînga, sus) al ferestrei (x- nr coloanei este în octetul superior, iar Y-
numărul liniei în octetul inferior);
Windmax - variabilă de tip Word ce conţine coordonatele punctului
(dreapta, jos) al ferestrei;
Funcţii şi proceduri din unitatea Crt
AssignCrt
perifericului Crt i se asociază un fişier text pentru o gestionare mai rapidă a
ecranului;
are declaraţia
procedure AssginCrt(Var F: Text);
window
defineşte o fereastră text pe ecran;
are declaraţia
Procedure Window(stîntga, sus, dreapta,jos: Byte);
colţul stînga sus al ecranului are coordonatele (1,1). Dimensiunea minimă a
ferestrei este 1 coloană dintr-o linie. Fereastra implicită corespunde
întregului ecran, deci apelului window(1,1, 80,25) în cazul modurilor text cu
25 de linii. Toate coordonatele (exceptîndu-le pe cele din apelul window)
sînt relative la fereastră. Punctul (stînga,sus) al ferestrei are coordonatele
(1,1).
ClrEol
şterge toate caracterele începînd de la poziţia curentă şi pînă la sfîrşitul liniei,
fără a modifica poziţia curentă;
DelLine
şterge linia curentă (în care se află cursorul) ;
are declaraţia
Procedure DelLine;
liniile următoare sînt mutate mai sus cu o linie, iar la baza ecranului este
adăugată o linie nouă;
95
InsLine
inserează o linie goală pe poziţia cursorului;
are declaraţia
Procedure InsLine;
Liniile care o urmează se deplasează în jos cu o poziţie, iar ultima linie se
pierde;
WhereX
întoarce coordonata x (numărul coloanei) punctului curent;
are declaraţia
Function WhereX : Byte;
Valoarea sa este dată de expresia Cursor.X+1;
WhereY
întoarce coordonata y (numărul liniei) punctului curent;
are declaraţia
Function WhereY : Byte;
Valoarea sa este dată de expresia Cursor.Y+1;
GoToXY
mută cursorul în punctul de coordonate specificat ;
are declaraţia
Procedure GoToXY(nr_coloana,nr_linie: Byte);
TextMode
stbileşte modul text;
are declaraţia
Procedure TextMode(Mod: Word);
fereastra curentă se extinde pe tot ecranul, modul video curent devine
LastMode, iar atributul textului pe Normal.
TextBackGround
stabileşte culoarea fondului;
are declaraţia
Procedure Textbackground(Culoare: Byte);
culoarea fondului este cuprinsă între 0 şi 7 (vezi tabelul de mai sus);
TextColor
stabileşte culoarea conturului caracterelor (peniţei)
are declaraţia
Procedure TextColor(culoare: Byte);
culoarea peniţei este cuprisă între 0 şi 15. Pentru a obţine efectul de clipire se
va aduna culoarea cu constanta Blink;
LowVideo
96
stabileşte modul de scriere la o intensitate mică (resetează bitul 3 al
variabilei TextAttr);
are declaraţia
Procedure LowVideo;
NormVideo
restabileşte modul de scriere la parametrii iniţiali (cu care a început
programul);
are declaraţia
Procedure NormVideo;
HighVideo
stabileşte modul de scriere la o intensitate mare (setează bitul 3 al variabilei
TextAttr);
are declaraţia
Procedure HighVideo;
Readkey
citeşte un caracter
are declaraţia
Function ReadKey: Char;
dacă în zona tampon asociată tastaturii există caractere, funcţia întoarce
primul caracter. În caz contrar, se aşteaptă pînă cînd se tastează un caracter.
Citirea este fără ecou (caracterul tastat nu este afişat în ecou pe monitor).
KeyPressed
întoarce valoarea True dacă în zona tampon asociată tastaturii există
caractere;
are declaraţia
Function KeyPressed : Boolean;
Sound
activează difuzorul intern;
are declaraţia
Procedure Sound(Frecventa: Word);
frecvenţa sunetului este dată prin argument (440 corespunde notei Do).
Sunetul se emite pînă la un alt apel Sound sau la un apel NoSound;
NoSound
opreşte difuzorul;
are declaraţia
Procedure NoSound;
Exemplu
Să se afişeze calendarul pe o lună a unui an.
97
program calendar;
{ Calendar pe o luna a unui an }
uses crt;
type vector_n=array [1..12] of integer;
vector_s=array [1..12] of string;
{ numar de zile scures de la inceputul unui an pina la inceputul lunii ianuarie,
februarie etc. }
const zile: vector_n=(0,31,59,90,120,151,181,212,243,273,304,334);
{ numar de zile din lunile unui an comun }
zile_luna: vector_n=(31,28,31,30,31,30,31,31,30,31,30,31);
{ nume de luni }
nume_luni:
vector_s=('Ianuarie','Februarie','Martie','Aprilie','Mai','Iunie',
'Iulie','August','Septembrie','Octombrie','Noiembrie','Decembrie');
procedure calend(luna,an:integer);
var z,
i: integer;
begin
if (luna>2) and ((an mod 400=0) Or ((an mod 4=0) and (an mod
100<>0))) then
z:=zile[luna]+1
else
z:=zile[luna];
dec(an);
z:=(z + an + 1 + an div 4 - an div 100 + an div 400) mod 7;
clrscr;
gotoxy(1,2);
write('Calendarul lunii ',nume_luni[luna],' ',an+1);
textcolor(WHITE);
write(#13#10' D L M M J V S'#13#10);
for i:=1 to z do
write(' ');
i:=z;
for z:=1 to zile_luna[luna] do
begin
inc(i);
98
write(z:3);
if i mod 7 =0 then
writeln
else
write(' ');
end;
end;
var luna,
anul:integer;
begin
clrscr;
window(1,1,lo(windmax),hi(windmax));
textbackground(LIGHTCYAN);
textcolor(RED);
repeat
gotoxy(5,2);
write('Calendar pe luna ');
read(luna);
until luna in [1..12];
repeat
gotoxy(25,2);
write(' anul ');
read(anul);
until anul >0;
calend(luna,anul);
readkey;
end.
Proceduri şi funcţii din unitatea de program Dos
În unitatea de program Pascal DOS se definesc următoarele tipuri de date:
DateTime = record Year, Month, Day, Hour, Min, Sec: Word end;
se utilizează în apelul de proceduri PackTime şi UnpackTime;
99
SearchRec= record
Fill: Array [1..21] of Byte;
Attr: Byte;
Time,Size: LongInt;
name: string[21];
end;
este utilizată de procedurile FindFirst şi Findnext;
ComStr = string[127];
se foloşeste pentru liniile de comandă ale programelor executabile (Exec);
PathStr = string [79];
DirStr= string[67];
NameStr = String[8];
ExtStr = String[4];
se folosesc pentru precizarea căii de căutare, numelor de fişiere, extensiilor
de nume;
Variabilă DosError declarată în unitatea DOS este de tip Integer. Dintre
valorile pe care le poate lua şi semnificaţia acestora amintim:
2 - fişier inexistent;
3 - cale inexistentă;
5 - acces interzis;
8 - memorie insuficientă;
18 - nu mai sînt fişiere.
Proceduri şi funcţii
GetDate
citeşte data calendaristică;
are declaraţia
procedure GetDate(var An, Luna, Zi, ZI_din_saptamina: Word);
anul furnizat este cuprins între 1980 şi 2099, luna între 1 şi 12, ziua între 1 şi
31, iar ziua din săptămînă între 0 şi 6 (0 corespunde zilei duminică);
GetFTime
întoarce data şi ora ultimei modificări relative la un fişier ;
are declaraţia
procedure GetFTime(var F; var Data: Longint);
F este o variabilă fişier cu sau fără tip sau un fişier de tip text care a fost
100
asignat şi deschis;
Data furnizată poate fi despachetată cu UnpackTime.
GetTime
citeşte ora curentă
are declaraţia
procedure GetTime(var Ore, Minute, Secunde, Sutimi: Word);
PackTime
converteşte data şi ora într-o forma utilizabilă de SetFTime.;
are declaraţia
procedure PackTime(var T: data_şi_ora; var Timp:
Longint);
SetDate
setează data în sistemul de operare ;
are declaraţia
procedure SetDate(An, Luna, Zi: Word);
SetFTime
setează data şi ora ultimei actuălizări a unui fişier;
are declaraţia
procedure SetFTime(var F; Data_ora: Longint);
fişierul F trebuie să fie deschis
SetTime
setează ora curentă;
are declaraţia
procedure SetTime(Ora, Minutul, Secunda, Sutimea_de_secunda:
Word);
UnpackTime
converteşte data şi ora împachetate într-o structura LongInt într-o structură
despachetată;
are declaraţia
procedure UnpackTime(Data_ora: Longint; var DaTa: TDateTime);
DiskFree
101
întoarce spaţiul disponibil pe o unitate de disc;
are declaraţia
function DiskFree(Drive: Byte): Longint;
Drive este numărul corespunzător unităţiide disc: 0- pentru discul de
lucru (implicit), 1 pentru A, 2 pentru B, 3 pentru C etc.
dacă numărul unităţii este invalid, întoarce valoarea -1.
DiskSize
întoarce capacitatea unui disc ;
are declaraţia
function DiskSize(Drive: Byte): Longint;
drive ia valorile indicate la funcţia DiskFree;
GetVerify
întoarce starea comutatorului MS DOS Verify;
are declaraţia
procedure GetVerify(var Verify: Boolean);
Dacă comutatorul Verify este off, variabila booleană Verify este false. În
acest caz operaţiile de scriere pe disc nu sînt verificate;
SetVerify
setează starea comutatorului Verify;
are declaraţia
procedure SetVerify(Verify: Boolean);
dacă parametrul verify este false, starea comutatorului Verify este setată
la On;
Fsearch
caută un fişier în directorul curent şi într-o listă de directoare;
are declaraţia
function FSearch(Path: PathStr; DirList: string): PathStr;
directoarele listei de directoare DirList se separă prin caracterul ; (punct
şi virgulă);
Fsplit
descompune un specificator de fişier în componentele sale (unitatea de
disc şi calea, numele şi extensia numelui);
are declaraţia
102
procedure FSplit(Specificator: PathStr; var Director: DirStr; var
Nume: NameStr; var Ext: ExtStr);
tipurile şir PathStr, DirStr, NameStr şi ExtStr sînt definite în unitatea de
program Pascal dos;
FindFirst
caută în directorul specificat în primul argument prima intrare în director
cu atributele specificate;
are declaraţia
procedure FindFirst(Path: PChar; Attr: Word; var F:
TSearchRec);
atributele posibile pentru un fişier sînt: ReadOnly = $01 Hidden=$02
SySfile=$03 Directory=$10 Archive=$20 AnyFile=$3F şi VolumeId=$08
parametrul Path este un specificator de fişier în accepţiunea Dos (poate
conţine unitatea logică de disc, calea, numele şi extensia numelui fişierului)
dacă există un astfel de fişier carcteristicile sale (atribute, data şi ora ultimei
modificări, numele şi extensia de nume exactă) sînt memorate în parametrul
F;
Exemplu
Prin apelul findfirst( ‘\*.bat ‘,AnyFile,fis); se caută în rădăcina
discului implicit fişiere cu extensia numelui bat
dacă nu există fişiere de tipul celor căutate, variabila DosError ia o valoare
nenulă ;
FindNext
continuă căutarea iniţiată cu FindFirst;
are declaraţia
procedure FindNext(var F: TSearchRec);
dacă nu mai există fişiere, variabila DosError ia valoarea 18;
Exec
lansează în lucru un program executabil;
are declaraţia
procedure Exec(Program, Parametri: string);
specificatorul de fişier corespunzător programului executabil se indică prin
parametrul Program, iar parametrii specifici programului prin Parametri;
orice eroare în execuţia procedurii Exec este evidenţiată în DosError;
GetCBreak
103
întoarce starea comutatorului Dos Break;
are declaraţia
procedure GetCBreak(var Break: Boolean);
dacă starea comutatorului Break este On (la fiecare apel al unor funcţii
sistem se va verifica dacă s-a tastat sau nu CTRL BREAK), variabila Break
(din apel) va primi valoarea True;
SetCBreak
setează starea comutatorului Break ;
are declaraţia
procedure SetCBreak(Break: Boolean);
dacă parametrul Break are valoarea True, comutatorul Break va fi setat pe
On . Dacă are valoarea false, comutatorul Break va fi pus pe Off (se verifică
dacă s-a tastat CTRL C numai la execuţia unor operaţii de citire/scriere pe
periferice standard -consolă, imprimantă şi porturile de comunicaţie).
Proceduri şi funcţii din unitatea Graph
În general, un monitor poate funcţiona în două moduri: text şi grafic.
În modul grafic, ecranul este privit ca o matrice de puncte (numite pixeli)
caracterizate prin culoare. Numărul de puncte pe orizontală şi verticală şi
numărul de culori pe care acestea le pot avea simultan definesc rezoluţia
imaginii. De exemplu, în cazul adaptorului grafic VGA, ecranul poate fi
împărţit în 640 x 200, 640 x 350 sau 640 x 480 pixeli. Colţul din stînga sus are
coordonatele (în ultimul caz) (0,0), cel din dreapta sus (639,0), cel din stînga jos
(0,479), iar cel din dreapta jos (639,479).
Dacă gestiunea imaginii este asigurată, din punctul de vedere al hardului,
de către adaptorul grafic, gestionarea acestuia din punct de vedere soft este
asigurată printr-un program (driver) de grafică. În Pascal, aceste drivere se află
pe suport sub formă de fişiere care au extensia numelor BGI (Borland Graphics
Interface). Unitatea Pascal în care sînt definite constantele, variabilele şi
procedurile grafice este Graph. Vom prezenta în continuare cîteva dintre
acestea.
InitGraph
iniţializează modul grafic;
are declaraţia
Inigraph(Var Driver_grafic,Mod_grafic:Integer;
Cale_fisiere_BGI);
driverele grafice posibile sînt: Detect = 0 (cu autodetecţie şi alegerea
104
modului grafic cel mai performant), CGA=1, MCGA=2, EGA=2,EGA64=3,
EGAMono=5, IBM8514=6, HecMono=7, ATT400=9, VGA=9, PC3270=10,
CurrentDriver=-128;
modurile grafice sînt constante definite în unitatea graph. Iată modurile
grafice posibile în cazul driverului de grafică VGA:
VGALo =0, 640x200 pixel;i,16 culori, fişier grafic EGAVGA.BGI;
VGAMed=1, 640x350 pixeli, 16 culori, fişier grafic
EGAVGA.BGI;
VGAHI=2, 640x480 pixeli, 16 culori, fişier grafic EGAVGA.BGI.
erorile de iniţializare sau cu care se încheie procedurile şi funcţiile grafice
sînt furnizate de funcţia GraphResult. Operaţia se încheie normal, cînd codul
de eroare este 0 (constanta GrOk);
CloseGraph
încheie lucrul în modul grafic, modul curent devenind modul text;
are declaraţia
procedure CloseGraph;
GraphResult
întoarce codul de eroare asociat ultimei operaţii grafice şi pune codul de
eroare pe 0;
are declaraţia
function GraphResult:Integer;
SetViewPort
precizează fereastra fizică (un domeniu dreptunghiular de pixeli) în care se
desenează;
are declaraţia
procedure SetViewPort(stînga,sus, dreapta,jos: Integer;
Decupare:Boolean);
fereastra este determinată de dreptunghiul care are vîrfurile opuse de
coordonate (stînga,sus) şi (dreapta, jos) şi are laturile orizontale şi verticale;
dacă variabila booleană Decupare are valoarea True, dintr-o figură care nu
încape în fereastră se decupează doar porţ
Cînd are valoare False, va fi afişată toată figura (chiar dacă nu încape în
fereastră);
după declararea ferestrei fizice, toate coordonatele vor fi relative la fereastră.
SetActivePage
stabileşte numărul paginii în care se desenează. Un ecran grafic poate avea
asociate una sau mai multe pagini grafice (de exemplu, VGALo 4, VGAMed
105
2, iar VGAHi 1). Pagina activă poate fi invizibilă. Numărul primei pagini
este 0;
are declaraţia
Procedure SetActivePage(Nr_Pagina:Word);
SetVisulalPage
afişează o pagină grafică;
are declaraţia
Procedure SetVisualPage(Nr_Pagină:Word);
GetX
întoarce abscisa corespunzătoare punctului grafic curent (a cursorului grafic)
;
are declaraţia
Function GetX: Integer;
GetY
întoarce ordonata corespunzătoare punctului grafic curent (a cursorului
grafic) ;
are declaraţia
Function GetY: Integer;
MoveTo
modifică poziţia punctului grafic curent (fără desenare) ;
are declaraţia
Procedure MoveTo(X,Y: Integer);
coordonatele X şi Y sînt relative la fereastră;
MoveRel
modifică poziţia punctului grafic curent (fără desenare) ;
are declaraţia
Procedure MoveRel(Depl_Pe_X,depl_Pe_Y: Integer);
Depl_Pe_X şi Depl_Pe_Y definesc coordonatele noului punct grafic curent
în coordonate relative faţă de poziţia actuală a cursorului grafic;
SetColor
stabileşte culoarea peniţei (culoarea cu care se desenează);
are declaraţia
Procedure SetColor(Culoare: Word);
valorile posibile pentru culoare sînt cuprinse în domeniul 0..15 şi sînt
prezentate la unitatea Pascal Crt;
106
GetColor
întoarce culoarea peniţei;
are declaraţia
Function GetColor: Word;
SetBkColor
stabileşte culoarea fondului;
are declaraţia
Procedure SetBkColor(Culoare: Word);
valorile posibile pentru culoare sînt cuprinse în domeniul 0..15 şi sînt
prezentate la unitatea Pascal Crt;
GetBkColor
întoarce culoare actuală a fondului;
are declaraţia
Function GetBkColor: Word;
PutPixel
“aprinde” un punct de o anumită culoare;
are declaraţia
Procedure PutPixel(X,Y: Integer; Culoare:Word);
pixelul are coordonatele relative X,Y, iar culoarea Culoare;
GetPixel
întoarce numărul culorii unui pixel;
are declaraţia
Function GetPixel(X,Y: Integer): Word;
ClearDevice
şterge imaginea afişată pe ecran;
are declaraţia
Procedure ClearDevice;
şterge ecranul (toţi pixelii vor avea culoarea fondului), iar punctul grafic
curent devine punctul (0,0) al ecranului;
ClearViewPort
şterge fereastra grafică curentă. Punctul grafic curent devine punctul (0,0) al
ferestrei;
are declaraţia
Procedure ClearViewPort;
GetMaxX
întoarce valoarea maximă abscisei vizibile pe ecran;
are declaraţia
Function GetMaxX: Integer;
107
GetMaxY
întoarce valoarea maximă ordonatei vizibile pe ecran;
are declaraţia
Function GetMaxY: Integer;
SetActivePage
stabileşte numărul paginii grafice active (în care se desenează). Adaptoarele
grafice Hercules, EGA şi VGA au mai multe pagini de memorie utilizate în
operaţii grafice. Prima pagină are numărul 0;
are declaraţia
Procedure SetActivePage(Nr_pagina: Word);
SetVisualPage
afişează pagina grafică indicată prin numărul său;
are declaraţia
Procedure SetVisualPage(Nr_pagină: Word);
Line
desenează un segment de dreaptă;
are declaraţia
Procedure Line(x_i,y_i,x_f,y_f: Integer);
segmentul de dreaptă este definit prin extremităţile sale (x_i,y_i) şi (x_f,y_f);
extremitatea finală a segmentului devine punct grafic curent;
LineTo
desenează un segment de dreaptă;
are declaraţia
Procedure LineTo(x_f,y_f: Integer);
segmentul de dreaptă este definit de punctul grafic curent şi (x_f,y_f);
extremitatea finală a segmentului devine punct grafic curent;
LineRel
desenează un segment de dreaptă;
are declaraţia
Procedure Linerel(Depl_x,Depl_y: Integer);
dacă (x_c,y_c) sînt coordonatele punctul grafic curent, atunci segmentul de
dreaptă este determinat de punctele (x_c,y_c) şi (x_c+Depl_x,y_c+Depl_y).
extremitatea finală a segmentului devine punct grafic curent ;
Circle
desenează un cerc;
are declaraţia
Procedure Circle(X_Centru,Y_Centru: Integer; Raza: Word);
Arc
desenează un arc de cerc;
108
are declaraţia
Procedure Arc(X_Centru,Y_Centru: Integer; Unghi_i,Unghi_f,
Raza: Word);
Unghi_i şi Unghi_f sînt unghiurile de poziţie ale primului şi ultimului punct
al arcului de cerc exprimate în grade;
Ellipse
desenează un arc eliptic;
are declaraţia
Procedure Ellipse(X_Centru,Y_Centru: Integer;
Unghi_i,Unghi_f: Word; Semiaxa_x,Semiaxa_y:
Word);
Unghi_i şi Unghi_f sînt unghiurile de poziţie ale primului şi ultimului punct
al arcului de eliptic exprimate în grade;
Rectangle
desenează un dreptunghi definit două vîrfuri diagonal opuse;
are declaraţia
Procedure Rectangle(X1,Y1,x2,y2: Integer);
DrawPoly
desenează o linie poligonală (dacă primul şi ultimul punct au aceleaşi
coordonate se desenează un poligon);
are declaraţia
procedure DrawPoly(Numar_de_virfuri: Word; Var Virfuri);
Vîrfuri este o alcătuit din perechi de forma (x,y), adică este un vector de
elemente de tipul
PointType= record { X,Y: Integer) end;
SetFillStyle
selectează modelul şi culoarea haşurii;
are declaraţia
Procedure SetFillStyle(Model_hasura,Culoare: Word);
dintre modelele de haşură amintim:
EmptyFill - haşurare cu culoarea de fond;
SollidFill - haşurare cu culoarea peniţei (figură plină );
LineFill - linii orizontale;
LtSlashFill - haşurare cu / (slash);
SlashFill - haşurare cu / (model mai gros);
HatchFill - pătrăţele;
XHatchFill -romburi
InterleaveFill - punctată (puncte dese);
WideDotFill - punctat (puncte rare);
109
Bar
desenează un dreptunghi haşurat;
are declaraţia
Procedure Bar(x1,y1,x2,y2);
FillEllipse
desenează o elipsă haşurată;
are declaraţia
o Procedure FillEllipse(X_centru,Y_centru: Integer; Semiaxa_x,
Semiaxa_y: Word);
FillPoly
desenează un poligon haşurat;
declaraţia este asemănătoare cu a procedurii Poly;
Sector
desenează un sector eliptic haşurat;
declaraţia este asemănătoare cu a procedurii Ellipse;
TextHeight
întoarce înălţimea textului în număr de pixeli;
are declaraţia
function Textheight: Word;
TextWidth
întoarce lăţimea textului în număr de pixeli;
are declaraţia
function TexWidth: Word;
SetTextStyle
defineşte tipul, direcţia şi dimensiunea caracterelor;
are declaraţia
Procedure SetTextStyle(Font,Directie:Word; Dimensiune: Word);
tipurile de fonturi (caractere) sînt: defaultFont, TriplexFont,
SmallFont,SanSerifFont, GothicFont;
direcţie text: HorDir - text orizontal şi VertDir - text vertical;
dimensiune font - UserCharSize dimensiune utilizator
SetTextJustify
stabileşte alinierea textului fată de cursorul grafic
are declaraţia
Procedure SetTextJustify(Oriz,vert: Word);
Oriz poate fi :
LeftText - la stînga; Centertext - poziţie centrală; RightText -
aliniere la dreapta
110
Vert poate fi :
BottomtText - jos; Centertext - poziţie centrală; TopText - sus;
OutText
scrie un text începînd cu punctul grafic curent;
are declaraţia
OutText(Text: String);
OutTextxy
scrie un text începînd cu punctul de coordonate indicate;
are declaraţia
OutTextxy(X,Y: Integer;Text: String);
ImageSize
întoarce numărul de octeţi necesari pentru a memora imaginea cuprinsă în
dreptunghiul definit prin vîrfurile diagonal opuse (stinga,sus) şi (dreapta,jos);
are declaraţia
Function ImageSize(Stînga,Sus,Dreapta,Jos): Word;
GetImage
copiază imaginea cuprinsă în dreptunghiul definit prin vîrfurile diagonal
opuse (stinga,sus) şi (dreapta,jos) în memorie ;
are declaraţia
Procedure getImage(stinga,sus,dreapta,jos:Integer; Var
Adresa_zona_memorie);
PutImage
afişează pe ecran imaginea salvată cu GetImage, în dreptunghiul care are
coordonatele vîrfului stînga-sus precizate;
are declaraţia
Procedure PutImage(Stinga,Sus: Integer; Var
Adresa_zona_memorie; Op:Word);
parametrul Op indică modul de afişare şi poate avea una din valorile
0 - CopyPut = afişare directă (fără modificare);
1 - XorPut = afişare cu XOR (cu imaginea curentă);
2 - OrPut = afişare cu Or;
3 - AndPut = afişare cu And;
4 - NotPut = afişare inversă.
Proceduri şi funcţii din unitatea de program String
111
Procedurile şi funcţiile din această unitate Pascal oferă posibilitatea
tratării elementelor cu tipul Zstring. Reamintim că pentru a putea lucra cu date
de tip Zstring, trebuie să fie permisă sintaxa extinsă (directiva {$X}).
StrLen
întoarce numărul de caractere al unui şir (lungimea şirului);
are declaraţia
Function Strlen(Sir: Pchar): Word;
în calculul lungimii şirului nu se ţine seama de caracterul NULL (acesta nu
este numărat).
StrEnd
întoarce un pointer la sfîrşitul unui ZString;
are declaraţia
Function StrEnd(Sir: Pchar): Pchar;
întoarce adresa caracterului Null (de încheiere a şirului);
StrNew
crează copia unui şir în zona de memorie de manevră (heap);
are declaraţia
Function StrNew(Sir: PChar): Pchar;
rezervă strlen(sir)+1 octeţi din zona Heap şi copiază în ea şirul Sir;
întoarce adresa memoriei alocate sau Nil (cînd nu există spaţiu).
StrDispose
eliberează zona de memorie rezervată în heap pentru un ZString;
are declaraţia
Procedure StrDispose(Sir: Pchar);
zona pentru şirul Sir a fost alocată prin intermediul funcţiei StrNew;
StrPas
converteşte Zstring într-un şir memorat în stil PASCAL (primul octet al
şirului conţine lungimea sa);
are declaraţia
Function StrPas(sir:PChar): String;
întoarce rezultatul conversiei;
StrComp
compară două şiruri;
are declaraţia
112
Function StrComp(Sir1,Sir2:Pchar): Integer;
întoarce valoarea 0 dacă şirurile sînt egale, o valoare negativă dacă primul şir
este mai mic decît al doilea şi o valoare pozitivă dacă primul şir este mai
mare decît al doilea.Compararea caracterelor din cele două şiruri se face pe
baza poziţiei lor în tabelul de codificare ASCII (ordine lexicografică).
StrIComp
compară două şiruri fără a ţine seama de felul literelor (literele mici sînt
echivalente cu cele mari);
are declaraţia
Function StrIComp(Sir1,Sir2:Pchar): Integer;
întoarce valoarea 0 dacă şirurile sînt egale, o valoare negativă dacă primul şir
este mai mic decît al doilea şi o valoare pozitivă dacă primul şir este mai
mare decît al doilea.Compararea caracterelor din cele două şiruri se face pe
baza poziţiei lor în tabelul de codificare ASCII (ordine lexicografică).
StrLComp
compară un număr de caractere din două şiruri ;
are declaraţia
Function StrLComp(Sir1,Sir2:Pchar;Nr_de_caractere:Word):
Integer;
întoarce aceeaşi valoare ca funcţia StrComp
StrECopy
copiază un şir în altul ;
are declaraţia
Function StrECopy(destinatie,Sursa:PChar):PChar;
nu se face nici un control în ceea ce priveşte lungimea destinaţiei (pentru ca
operaţia să fie încheiată corect trebuie ca zona destinaţie să aibă cel puţin
StrLen(Sursa) octeţi;
întoarce adresa sfîrşitului rezultatului;
StrLCopy
copiază un număr de octeţi dintr-un şir în altul ;
are declaraţia
Function
StrLCopy(destinatie,Sursa:PChar;Lungime:Word):PChar;
nu se face nici un control în ceea ce priveşte lungimea destinaţiei (pentru ca
operaţia să fie încheiată corect trebuie ca zona destinaţie să aibă cel puţin
StrLen(Sursa) octeţi;
întoarce adresa rezultatului;
StrPCopy
copiază un şir memorat în stil PASCAL (lungimea acestuia se memorează în
113
faţă) într-un ZString;
are declaraţia
Procedure StrPCopy(Destinatie: Pchar; Sursa: String): Pchar;
nu se efectuează nici un control de lungime (destinaţia trebuie să fie
sufiecient de mare)
întoarce adresa destinaţiei;
StrLower
converteşte literele mari ale unui ZString în litere mici;
are declaraţia
function StrLower(Sir: Pchar): Pchar;
întoarce adresa Sir;
StrUpper
converteşte literele mici ale unui ZString în litere mari;
are declaraţia
function StrLower(Sir: Pchar): Pchar;
întoarce adresa Sir;
StrCat
concatenează două Zstring-uri;
are declaraţia
function Strcat(Destinatie,Sursa: Pchar): Pchar;
întoarce adresa şirului rezultat ;
StrLCat
adaugă un număr de caractere ale unui şir la sfîrşitul unui Zstring;
are declaraţia
function StrLcat(Destinatie,Sursa: Pchar;
Nr_de_caractere:Word): Pchar;
întoarce adresa şirului rezultat ;
StrMove
copiază caractere dintr-un şir în altul;
are declaraţia
function StrMove(Destinatie,Sursa:PChar; Lungime:Word):
Pchar;
numărul de caractere copiate este dat de parametrul Lungime;
sursa şi destinaţia pot avea o porţiune comună ;
114
întoarce adresa destinaţiei.
StrPos
caută prima apariţie a unui şir în altul;
are declaraţia
function StrPos(Sir,Subsir: Pchar): Pchar;
întoarce adresa subşirului Subsir în sir sau pointerul Nil
StrScan
caută prima apariţie a unui caracter într-un ZString;
are declaraţia
function StrPos(Sir: Pchar; C: Char): Pchar;
întoarce adresa primului caracter c din Sir sau pointerul Nil
StrRScan
caută ultima apariţie a unui caracter într-un Zstring;
are declaraţia
function StrRScan(Sir: Pchar; C: Char): Pchar;
întoarce adresa ultimei apariţii în Sir a caracterului c sau pointerul Nil
Grafice de funcţii reale de o variabilă reală
Fie f o funcţie reală definită în intervalul [a,b] , mărginită. Prin
urmare, există un interval [c,d] cu proprietatea că f(x) [c,d] pentru orice x
din [a,b]. Să se reprezinte graficulu acestei funcţii.
Fie [u1,u2]x[v1,v2] zona dreptunghiulară de pe ecran care conţine
graficul funcţiei. Dacă P(x,y) este un un punct al dreptunghiului [a,b]x[c,d],
imaginea sa Q(u,v) trebuie să aparţină lui [u1,u2]x[v1,v2], prin urmare vom
avea
de unde, avînd în vedere că pe ecran coordonatele sînt numere întregi şi
pozitive, vom avea
v1-v2
v1-v =
d-c
d-y
u1-u2
u1-u =
a-b
a-x
115
Mărimile c şi d pot fi, în particular, maximul şi minimul funcţiei F pe [a,b].
Îin programul Pascal de mai jos, punctul (u1,v1) este notat (stînga,sus),
punctul de coordonate (u2,v2) este notat (dreapta,jos).
{$F+} { pentru a putea folosi functii si proceduri ca argumente de functii }
USES graph,crt;
TYPE functie= function(x:real):real;
tip=(puncte,linii,scara,bare);
procedure grafic(f:functie; { functia }
x1,x2,x3:real; { primul punct, al doilea, ultimul }
stinga,sus,dreapta,jos:integer; { dreptunghiul in care se va reprezenta }
culoare,fond:integer;{ culoare penita }
forma:tip); { forma graficului }
var x,y, { abscisa si ordonata reala }
pas, { pasul cu care se vor calcula ordonatele punctelor graficului }
, { valoarea a a functiei }
maxim, { valoarea maxima a functiei }
rx,ry: real; { variabile de lucru - contin valori de reducere la scara }
xc,yc,xp,yp:integer; { punctul grafic curent si punctul grafic precedent }
init:boolean; { are valoare true la primul punct }
BEGIN
pas:=(x2-x1); { determina pasul, ul si maximul functiei }
x:=x2; :=f(x1) ; maxim:=f(x1);
repeat
y:=F(x);
if y< then :=y
else if y>maxim then
maxim:=y;
x:=x+pas;
until x>x3;
rx:=(dreapta-stinga)/(x3-x1);
ry:=(sus-jos)/(maxim-);
v1) + d-c
v1)-(v2d)-(yRound( = v
u1) + a-b
u1)-(u2a)-(xRound( =u
116
init:=true;
yp:=detect;
{ initializare mod grafic }
initgraph(yp,xp,'\bp\bgi');
x:=x1;
{ traseaza graficul }
repeat
xc:=trunc(dreapta+rx*(x-x3)+0.5); { calculeaza coordonatele si le
rotunjeste }
yc:=trunc(sus+ry*(f(x)-maxim)+0.5);
if init then begin
{cleardevice; { sterge ecranul }
setcolor(GREEN); { deseneaza dreptunghiul cu culoarea verde }
rectangle(stinga,sus,dreapta,jos);
setcolor(culoare); { seteaza culoarea penitei }
setbkcolor(fond);
setfillstyle(InterleaveFill,BLUE);
if forma=puncte then
putpixel(xc,yc,culoare);
init:=false;
end
else
case forma of
puncte:
putpixel(xc,yc,culoare);
linii:
lineto(xc,yc);
scara:
linerel(xc-xp,0);
bare:
bar(xp,yp,xc-3,jos);
end;
moveto(xc,yc);
x:=x+pas;
xp:=xc; yp:=yc;
until x>x3;
end;
{ functii ce se reprezinta grafic }
117
function PATRAT(t:real):real;
begin
PATRAT:=t*t;
end;
function SINUS(x:real):real;
begin
sinus:=sin(x);
end;
Trasări de suprafeţe
Fie f o funcţie reală definită pe dreptunghiul [a,b]x[c,d]. Pentru a
reprezenta suprafaţa definită de f vom proiecta fiecare punct P(x,y,z) pe planul
XoYdupă următoarea regulă:
punctul P(0,0,1) va fi proiectat pe XoY în punctul Q care satisface relaţiile
OQ=r (o mărime fixată), iar = QoX_ ;
orice alt punct R(x,y,z) se va proiecta într-un punct S(x ‘,y ‘,0) cu
proprietatea că PQ RS. Din considerente geometrice x ‘ =x+r*z*cos(α),
iar y ‘=y+r*z*sin(α);
pentru orice x fixat, trasăm graficul proiecţiei punctelor P(x,y,f(x,y)) cu y
variabil în [c,d];
pentru orice y fixat, trasăm graficul proiecţiei punctelor P(x,y,f(x,y)) cu x
variabil în [a,b].
{$F+} { pentru a putea folosi functii si proceduri ca argumente de functii }
USES graph,crt;
TYPE fct2=function(x,y:real):real;
var x0,y0:real;
procedure suprafata(f:fct2; { functia }
a,b,c,d, { domeniul de definitie [a,b]x[c,d] }
alfa,r:real; { elemente ce definesc poiectia paralela }
118
stinga,sus,dreapta,jos:integer; { dreptunghiul in care se va reprezenta }
n:integer; { numar de subintervale }
culoare:integer);{ culoare penita }
var x,y,z, { abscisa, ordonata reala si cota }
pasx, { pasii pe ox si oy }
pasy,
xp,yp, { coordonatele proiectiei }
x, { extremele pentru xp si yp }
xmaxim,
y,
ymaxim,
rx,ry: real; { coeficienti de reducere la scara }
i,j, { contoare }
xc,yc:integer; { punctul grafic curent }
init:boolean; { are valoare true la primul punct }
BEGIN
pasx:=(b-a)/n; { determina pasii, ul si maximul coordonatelor }
pasy:=(d-c)/n;
x:=a+r*cos(alfa)*f(a,c) ; xmaxim:=x;
y:=c+r*sin(alfa)*f(a,c) ; ymaxim:=y;
for i:=0 to n do begin
x:=a+i*pasx;
for j:=0 to n do begin
y:=c+j*pasy;
z:=f(x,y);
xp:=x+r*cos(alfa)*z;
yp:=y+r*sin(alfa)*z;
if yp<y then y:=yp
else if yp>ymaxim then
ymaxim:=yp;
if xp<x then x:=xp
else if xp>xmaxim then
xmaxim:=xp;
end;
end;
{ calculeaza factorii de scara }
rx:=(dreapta-stinga)/(xmaxim-x);
ry:=(sus-jos)/(ymaxim-y);
119
{ traseaza graficele cu elemente x[i] fixate }
for i:=0 to n do begin
init:=true;
x:=a+i*pasx;
for j:=0 to n do begin
y:=c+j*pasy;
z:=f(x,y);
xp:=x+r*cos(alfa)*z;
yp:=y+r*sin(alfa)*z;
xc:=trunc(dreapta+rx*(xp-xmaxim)); { calculeaza coordonatele si le
rotunjeste }
yc:=trunc(sus+ry*(yp-ymaxim));
if init then
init:=false
else
lineto(xc,yc);
moveto(xc,yc);
end;
end;
readkey;
{ traseaza grafice cu y[j] fixat }
setcolor(culoare);
for j:=0 to n do begin
init:=true;
y:=a+j*pasy;
for i:=0 to n do begin
x:=c+i*pasx;
z:=f(x,y);
xp:=x+r*cos(alfa)*z;
yp:=y+r*sin(alfa)*z;
xc:=trunc(dreapta+rx*(xp-xmaxim));
yc:=trunc(sus+ry*(yp-ymaxim));
if init then begin
init:=false
end
else
lineto(xc,yc);
moveto(xc,yc);
120
end;
end;
end;
function f(x,y:real):real;
begin
f:=sin(x*x+y*y);
end;
function g(x,y:real):real;
begin
g:=sin(x*y);
end;
var gdriver,gmode:integer;
alfa,r:real;
BEGIN
gdriver:=detect;
initgraph(gdriver,gmode,'\bp\bgi');
alfa:=pi/4; r:=1;
suprafata(f,-pi,pi,-pi,pi,alfa,r,100,50,getmaxx-100,getmaxy-50,50,cyan);
readkey;
cleardevice;
suprafata(g,-pi,pi,-pi,pi,alfa,r,100,50,getmaxx-100,getmaxy-50,50,cyan);
readkey;
END.
{ procedura principala }
var t:real;
BEGIN
t:=arctan(1)*4;
grafic(sinus,0,0.1,2*t,0,0,300,300,CYAN,BLACK,puncte);
readkey;
grafic(sinus,0,0.1,2*t,0,0,300,300,CYAN,BLACK,scara);
readkey;
grafic(sinus,0,0.1,2*t,0,0,300,300,CYAN,BLACK,linii);
readkey;
121
grafic(patrat,0,5,100,0,0,300,300,CYAN,BLACK,puncte);
readkey;
grafic(patrat,0,5,100,0,0,300,300,CYAN,BLACK,scara);
readkey;
grafic(patrat,0,5,100,0,0,300,300,CYAN,BLACK,linii);
readkey;
grafic(patrat,0,5,100,0,0,300,300,CYAN,BLACK,bare);
readkey;
END.
Liste simplu înlănţuite
O listă este o mulţime (o colecţie) de elemente de acelaşi tip. O listă
poate fi vidă. De exemplu, lista candidaţilor înscrişi la concursul de admitere la
facultate, lista candidaţilor admişi, lista studenţilor bursieri, lista studenţilor
promovaţi etc. Asupra unei liste se pot efectua următoarele operaţii:
activarea sau crearea listei (lista nu conţine nici un element);
adăugarea unui element într-o listă. Adăugarea se poate face în orice poziţie
(la început, la sfîrşit etc.);
eliminarea (ştergerea) unui element din listă;
descompunerea unei liste în două sau mai multe liste (partiţionarea listei) în
funcţie de anumite criterii;
sortarea elementelor listei după diferite criterii;
căutarea unui element într-o listă.
Alocarea memoriei pentru elementele unei liste se poate realiza
static (la creare sau iniţializare se rezervă memorie pentru un număr maxim
de elemente);
dinamic (fiecărui element i se rezervă zonă cînd se adaugă în listă; memoria
va fi eliberată cînd elementul se va şterge).
În ultimul caz, pe lîngă valoarea fiecărui element, va trebui memorată o adresă
de înlănţuire (adresa zonei de memorie rezervată pentru următorul element al
122
listei). Prin urmare, o listă poate fi concepută ca o mulţime de noduri care
conţine o parte de date şi adresa următorului element.
Prezentăm în continuare un program Pascal în care se crează o listă
simplu înlănţuită cu studenţii unei grupe care conţine elemente de forma numele
(numele şi prenumele) şi media anuală (nota) şi lisează elementele listei în
ordinea descrescătoare a mediei.
{ Crearea unei liste simplu inlantuita}
program lista_inlantuita;
uses crt;
type Legatura=^lista;
gata=(da,nu);
lista= record
numele: string [30];
nota:integer;
adresa_u:legatura;
end;
var
adresa_e, { adresa elementului curent }
adresa_p, { adresa precedentului }
adresa_n, { adresa elementului urmator }
adresa_listei: Legatura;
incep: boolean;
{Scrie un text ca un nume propriu}
function StrProper(s:string):string;
var i,l:integer;
begin
i:=1; l:=length(s);
while i<=l do
begin
while (i<=l) and (s[i] in [' ',#9,'.',',',';']) {spatiu,TAB etc.}
do inc(i);
if s[i] in ['a'..'z'] then {este litera mica }
s[i]:=chr(ord(s[i])-32);
inc(i);
while (i<=l) and (s[i] in ['a'..'z','A'..'Z','0'..'9'])
123
do inc(i);
end;
strProper:=s;
end;
{Adauga unui element in lista}
procedure adauga_in_lista( n:string; { numele }
v:integer); { nota }
begin
new(adresa_e); { aloca spatiu in heap}
if incep then
begin
adresa_listei:=adresa_e; { la inceput memoreaza adresa listei }
incep:=false; { se vor memora alte elemente }
end
else
adresa_p^.adresa_u:=adresa_e; { memoreaza adresa in precedentul
element }
with adresa_e^ do
begin
adresa_u:=nil; { poate este ultimul }
numele:=n; { memoreaza numele }
nota:=v { ... si nota }
end;
adresa_p:=adresa_e; { retine adresa elementului curent }
end;
{ Listarea listei }
procedure listeaza_lista;
begin
adresa_e:=adresa_listei;
repeat
writeln('Numele ',adresa_e^.numele, ' nota ',adresa_e^.nota);
adresa_e:=adresa_e^.adresa_u
until adresa_e=nil;
write('Tastati Enter');
readln;
end;
{ sortarea listei in ordine descretoare a notei - mediei }
124
procedure sorteaza_lista;
var sortat:gata;
begin
repeat
sortat:=da;
adresa_p:=nil;
adresa_e:=adresa_listei;
adresa_n:=adresa_e^.adresa_u;
while adresa_n<>nil do
begin
if adresa_e^.nota < adresa_n^.nota then
begin
if adresa_p= nil then
adresa_listei:=adresa_n
else
adresa_p^.adresa_u:=adresa_n;
adresa_e^.adresa_u:=adresa_e;
adresa_n^.adresa_u:=adresa_n;
sortat:=nu;
end;
if adresa_p=nil then
adresa_p:=adresa_listei { nu are precedent }
else
adresa_p:=adresa_p^.adresa_u;
adresa_e:=adresa_e^.adresa_u; { treci la urmatoarea
pereche }
adresa_n:=adresa_n^.adresa_u;
if adresa_n<>nil then adresa_n:=adresa_n^.adresa_u;
end
until sortat=da
end;
{ procedura principala }
var valoare: integer;
nume: string[30];
begin
incep:=true; { initializari }
clrscr;
repeat
write('Numele (incheiati cu Enter) '); { citeste numele }
125
readln(nume);
if length(nume)=0 then break;
repeat
write('Nota='); { si nota }
readln(valoare);
until (valoare>=0) and (valoare<=10);
if valoare <>0 then { daca valoare admisa }
adauga_in_lista(strproper(nume),valoare); { memoreaza elementul}
until valoare=0; { pina cind nota = 0 }
if not incep then
begin
sorteaza_lista;
listeaza_lista;
end;
end.
Liste dublu înlănţuite Listele de tipul celei prezentate în exemplul precedent poate fi parcurse
într-un singur sens: de la început la sfîrşit (se începe cu primul, se continuă cu al
doilea, apoi al treilea etc.). Vom prezenta în continuare, o listă care poate fi
parcursă în ambele sensuri. Operaţiile pe listă vor face obiectul unităţii de
program PASCAL Listed. Toate funcţiile şi procedurile acestei unităţi sînt
polimorfice (independente de tipul elementelor listei).
unit listed;
interface
type PElement=^Element;
Element= record
adresa_date:pointer; {adresa partii ce contine datele }
adresa_u:Pelement; { adresa elementului urmator }
end;
{declarari de proceduri si functii }
procedure init_lista(var l:Pelement); { initializare lista }
procedure adauga(var s, { adauga un element }
precedent:Pelement;
date:pointer);
procedure citeste_date(s:Pelement;var date:pointer); { preia partea de date }
126
function treci_la_altul(var c:Pelement):boolean; { treci la urmatorul element
al listei }
function lista_vida(s:PElement): boolean; { test daca lista e vida }
procedure sterge_element(var s,prec:PElement); { sterge elementul curent }
{ partea de implementare a operatiilor }
implementation
{ initializare lista}
procedure init_lista(var l:Pelement);
begin
l:=nil;
end;
{ adaugare element }
procedure adauga(var s,
precedent:Pelement;
date:pointer);
var c:Pelement;
begin
new(c);
if s=nil then s:=c else precedent^.adresa_u:=c;
with c^ do begin
adresa_u:=nil;
adresa_date:=date;
end;
precedent:=c;
end;
{ citeste partea de date }
procedure citeste_date(s:Pelement;var date:pointer);
begin
date:=s^.adresa_date;
end;
{ treci la urmatorul element din lista }
function treci_la_altul(var c:Pelement):boolean;
begin
c:=c^.adresa_u;
treci_la_altul:=(c=nil);
127
end;
{ sterge elementul curent }
procedure sterge_element(var s,prec:PElement);
var p:PElement;
begin
if s=prec then begin
s:=s^.adresa_u;
dispose(prec);
end
else
begin
p:=prec^.adresa_u;
prec^.adresa_u:=p^.adresa_u;
end;
end;
{ test daca lista este vida }
function lista_vida(s:PElement): boolean;
begin
lista_vida:=(s=nil);
end;
end.
Programul de mai jos utilizează elementele unităţii Listed
program studenti;
uses listed,
crt;
type student=record (* date relative la un student *)
nume:string[30];
nota: integer;
end;
Tadr=^student; (* este un pointer la un articol de tip student *)
var stud, (* adresa listei de studenti *)
prec:Pelement; (* precedentul student *)
128
x:pointer; (* este un pointer al carui tip se va preciza *)
adresa_s:^student;
begin
init_lista(stud); (* initializarea listei de studenti *)
while true do begin (* introdu in lista pina cind numele este spatiu *)
new(adresa_s); (* rezerva spatiu pentru un student *)
with adresa_s^ do begin
write('Numele '); readln(nume); (* citeste numele *)
if length(nume)=0 then begin
dispose(adresa_s); (* elibereza zona alocata *)
break; (* incheie bucla *)
end;
write('nota= '); readln(nota); (* citeste nota *)
end;
adauga(stud,prec,adresa_s); (* adauga-l in lista *)
end;
(* listeaza studentii *)
prec:=stud; (* incepe cu primul *)
repeat
citeste_date(prec,x); (* citeste datele *)
writeln(Tadr(x)^.nume,' are nota ',Tadr(x)^.nota); (* afiseaza-le *)
until treci_la_altul(prec); (* treci la altul *)
readln; (* asteapta un caracter *)
prec:=stud;
(* listeaza studentii *)
sterge_element(stud,prec);
prec:=stud; (* incepe cu primul *)
repeat
citeste_date(prec,x); (* citeste datele *)
writeln(Tadr(x)^.nume,' are nota ',Tadr(x)^.nota); (* afiseaza-le *)
until treci_la_altul(prec); (* treci la altul *)
readln; (* asteapta un caracter *)
end.
129
2. Structuri de date
Date şi structuri de date
Tipuri de date
Sistemele de prelucrare automată a datelor prelucrează date, în concordanţă cu
cerinţele informaţionale, pentru a se obţine informaţii. Într-un program se
utilizează:
date de intrare, cunoscute în problema pe care programul o rezolvă;
date de ieşire, reprezentate de rezultatele ce se cer în problemă.
Datele de intrare sunt valori ce se atribuie variabilelor de intrare iar datele de ieşire
sunt valori pe care le iau variabilele de ieşire. Ele trebuie să aparţină domeniului
acestor variabile.
După complexitatea lor, datele pot fi:
date atomice (simple), a căror valoare nu se poate descompune;
date structurate (grupate), formate din n valori.
Structura defineşte modul de dispunere a elementelor unei date şi relaţiile ce se
pot stabili între aceste elemente. Elementele constitutive se numesc câmpuri şi ele
pot fi date simple sau, la rândul lor, grupate.
Un tip de date se identifică prin:
domeniu - o mulţime de valori posibile pentru acele date (realizări ale
tipului);
comportament - o mulţime de operaţii, funcţii şi relaţii ce operează cu
valorile tipului.
De foarte multe ori se pune problema prelucrării unui volum mare de date de
acelaşi tip. Prelucrările pot fi atât individuale cât şi globale. În prelucrările globale
datele sunt parcurse secvenţial, dar în prelucrările individuale se pune problema
accesului punctual la date, pe baza unui element de identificare.
Elementele unui tip de date se împart în:
130
partea de identificare (cheia), care trebuie să fie unică pentru o anumită
realizare a tipului;
partea de atribute (de informaţie).
Tipuri de legături
În funcţie de legăturile ce se pot stabili între elementele componente ale unui tip se
deosebesc patru tipuri fundamentale de structuri:
mulţime;
liniară;
arborescentă;
graf (reţea).
Tipul de legături specifice pentru fiecare tip de structură este dat în tab. 2.1, iar
reprezentarea grafică a acestora este dată în fig. 2.1.
Tip structură Tip legătură între elemente
mulţime nici una
liniară unu - la - unu
arbore unu - la - mai multe
graf mai multe - la - mai multe
Tab. 2.1 Tipul de legături specifice structurilor de date
131
mulţime liniară arbore graf
Fig. 2.1 Tipuri fundamentale de structuri de date
Structuri fizice de date
Memoria internă a sistemelor de calcul, în care datele se stochează în timpul
execuţiei programelor, are o organizare liniară. Indiferent de tipul structurilor
logice de date, se pune aşadar problema liniarizării lor. Liniarizarea se realizează în
mod diferit, astfel încât operaţiile elementare asupra structurilor de date să se
execute în timp optim. Din acest punct de vedere, structurile fizice de date pot fi:
statice - ocupă în memorie o zonă de dimensiune constantă, iar
elementele componente îşi păstrează locul în tot timpul execuţiei
programului;
semistatice - ocupă în memorie o zonă de dimensiune constantă, dar
elementele componente îşi modifică locul în timpul execuţiei
programului;
dinamice - memoria ocupată nu are o dimensiune constantă, ea alocându-
se pe măsura nevoii de prelucrare, în timpul execuţiei programului.
Unele structuri logice de date pot fi implementate sub oricare din cele trei forme,
altele nu.
Structuri statice
Pentru structurile statice de date alocarea memoriei este statică atât la nivelul
întregii structuri cât şi la nivelul elementelor componente. Locul structurilor şi a
fiecărei componente, în memoria internă, este fix, structurile statice fiind structuri
de date inerte. Ele există pe toată durata execuţiei programului sub aceeaşi formă,
fără să evolueze.
Articolul este format dintr-un număr fix de componente de tipuri diferite, care
formează în ansamblu o structură logică. Componentele articolului se numesc
132
câmpuri. Structura articolului este neomogenă, datorită câmpurilor de tip diferit.
Structura unui articol este reprezentată grafic în fig. 2.2.
câmp 1 câmp 2 … câmp i … câmp n
a1 l1 a2 l2 ai li an ln
Fig. 2.2 Structura unui articol
Câmpurile pot avea lungimi diferite, iar adresa câmpului i (ai) se poate obţine pe
baza adresei primului câmp (a1) şi a lungimii primelor i-1câmpuri (l1…li-1):
ai = a1+l1+ l2+…+ li-1 (2.1)
Tabloul este o aplicaţie prin care unui k-uplu de indici (i1, i2…ik) i se asociază un
element mi1, i2,…,ik. În general tabloul este o structură omogenă, toate elementele
tabloului fiind de acelaşi tip. Pentru k = 1 tabloul este unidimensional (vector), iar
pentru k = 2 tabloul este bidimensional (matrice). Elementele unui tablou ocupă, în
memoria internă, locaţii succesive.
Dacă tabloul este omogen, adresa relativă a unui element faţă de adresa de început
a tabloului este uşor de calculat. Pentru un vector, dacă toate elementele au
lungimea l şi adresa primului element al tabloului este a1, adresa elementului i (ai)
va fi:
ai = a1+l*(i-1) (2.2)
Mulţimea este o colecţie finită de elemente (m1, m2, …, mn) care poate fi asimilată
cu un vector. Structura de submulţime poate fi definită cu ajutorul unui vector
asociat, de aceeaşi dimensiune. Elementul i al vectorului asociat va avea valoarea 1
dacă elementul mi al mulţimii de bază aparţine submulţimii definită pe baza
vectorului asociat şi va avea valoarea 0 în caz contrar. Orice operaţii cu
submulţimile unei mulţimi pot fi implementate ca operaţii logice asupra vectorilor
asociaţi acelor submulţimi.
Structuri semistatice
Pentru structurile semistatice de date alocarea memoriei este statică la nivelul
întregii structuri şi dinamică la nivelul elementelor componente. Structurile
semistatice utilizează o zonă fixă de memorie, alocată în mod static, dar în cadrul
acesteia se alocă dinamic locaţii corespunzătoare elementelor structurii. Spaţiul
133
alocat structurilor statice este rezervat lor pe toată durata execuţiei programului, dar
structura se modifică prin adăugarea şi eliminarea de elemente.
Elementele structurii pot fi eliminate, atunci când nu mai sunt necesare, iar locaţiile
eliberate pot fi reutilizate pentru alte elemente. Procedura de adăugare a unui nou
element va trebui să verifice dacă structura semistatică nu este deja plină (spaţiul
alocat a fost utilizat în întregime), iar procedura de eliminare a unui element va
trebui să verifice dacă structura nu este deja vidă.
Stiva este o structură semistatică pentru care spaţiul de memorie alocat este
cuprins între baza B şi vârful V, unde B < V. Adăugarea unui element în stivă
se face prin ocuparea primei locaţii libere, de la bază spre vârf. Ştergerea unui
element din stivă se face prin eliberarea primei locaţii ocupate, de la vârf spre
bază. După modul în care elementele întră în şi ies din stivă, aceasta se mai
numeşte şi listă LIFO (Last In - First Out, ultimul intrat - primul ieşit).
Stiva are asociat un indicator inds. Dacă stiva este vidă, atunci inds = B, iar dacă
stiva este plină, atunci inds = V. Procedura de adăugare a unui nou element în stivă
trebuie să verifice dacă stiva nu este plină, iar în urma operaţiei de adăugare
indicatorul stivei va creşte cu o unitate. Procedura de eliminare a unui element din
stivă va trebui să verifice dacă stiva nu este vidă, iar în urma eliminării indicatorul
stivei va descreşte cu o unitate.
Coada este o structură semistatică asemănătoare cu stiva, dar al cărei mecanism de
actualizare este diferit. Adăugarea unui element în coadă se face prin ocuparea
primei locaţii libere de la vârf spre bază. Ştergerea unui element din coadă se face
prin eliberarea primei locaţii ocupate, de la bază spre vârf. După modul în care
elementele întră în şi ies din coadă, aceasta se mai numeşte şi listă FIFO (First In -
First Out, primul intrat - primul ieşit
O coadă are doi indicatori relativi, care arată locul în care se adaugă un element
nou (inda) şi respectiv locul din care se elimină un element (inde). Adresa la care
se adaugă noul element va fi B+inda, iar adresa de la care se extrage un element va
fi B+inde. Coada este vidă dacă inda = inde (iniţial inda = inde = 0) şi este plină
dacă inde = (inda+1)(mod n), unde n = V-B. Procedura de adăugare a unui nou
element în coadă trebuie să verifice dacă aceasta nu este plină, iar în urma operaţiei
de adăugare indicatorul inda va creşte cu o unitate (mod n). Procedura de eliminare
a unui element din coadă va trebui să verifice dacă aceasta nu este vidă, iar în urma
eliminării indicatorul inde va creşte cu o unitate (mod n).
Structuri dinamice
Pentru structurile dinamice de date alocarea memoriei este dinamică atât la nivelul
întregii structuri cât şi la nivelul elementelor componente. În cazul în care numărul
elementelor componente ale unei anumite structuri de date nu este cunoscut,
alocarea unui spaţiu fix de memorie pentru stocarea acelei structuri este ineficientă.
134
Spaţiul alocat poate fi fie insuficient, fie prea mare. Spaţiul de memorie trebuie să
fie alocat dinamic, pe măsura apariţiei elementelor structurii.
Alocarea dinamică a memoriei presupune înlănţuirea elementelor structurii.
Fiecare element va conţine:
informaţie de legătură (referinţă) - LEGi;
informaţie utilă - INFi.
Informaţia de legătură este o informaţie suplimentară pe baza căreia sunt legate
între ele elementele structurii.
Lista liniară este o structură dinamică în care elementele componente sunt situate
pe un singur nivel. Pentru reprezentarea internă a unei liste sunt necesare:
adresa primului element al listei, numit cap de listă (CAP);
modul de înlănţuire al elementelor listei;
indicarea ultimului element din listă (LEGn = nil).
CAP
INF1 LEG1 INF2 LEG2 … INFn LEGn=nil
Fig. 2.3. Structura unei liste
În lista liniară simplu înlănţuită informaţia de legătură conţine doar adresa
elementului următor din listă. În lista liniară dublu înlănţuită informaţia de
legătură conţine atât adresa elementului următor cât şi adresa elementului
precedent din listă. În lista circulară informaţia de legătură a ultimului element din
listă conţine adresa primului element al listei.
Structura arborescentă este o structură dinamică în care elementele componente
sunt grupate pe mai multe niveluri ierarhice. Elementele componente formează
nodurile (vârfurile) arborelui. Orice arbore are un nod special, numit rădăcină.
Nodul rădăcină formează nivelul 1 al unui arbore, fiind singurul nod nesubordonat
nici unui alt nod. Toate celelalte noduri ale arborelui sunt subordonate unele altora,
fiecare nod fiind subordonat direct unui singur nod. Nodurile subordonate rădăcinii
formează nivelul 2 al arborelui, nodurile subordonate acestora formează nivelul 3,
ş.a.m.d. Fiecare set disjunct de noduri, altele decât rădăcina, formează la rândul său
un arbore (subarbore).
Un nod terminal (frunză) este un nod care nu are nici un alt nod subordonat. Un
nod este părinte (tată) pentru nodurile subordonate direct lui, iar acestea sunt fii
135
ale nodului cărora le sunt subordonate. Nodurile subordonate direct aceluiaşi nod
sunt fraţi.
Arborii care nu au noduri ierarhizate pe mai multe niveluri sunt arbori neorientaţi.
Un arbore este binar dacă se compune din rădăcină şi din doi subarbori, numiţi
subarborele stâng şi subarborele drept. Un arbore ale cărui noduri au cel mult doi
descendenţi este binar dacă se ştie întotdeauna care sunt fiul stâng şi fiul drept al
fiecărui nod.
Elementele unui arbore sunt nodurile şi legăturile dintre ele. Ierarhizarea nodurilor
se exprimă, de regulă, prin referinţe descendente (părinte - fiu), dar se poate
exprima şi prin referinţe ascendente (fiu - părinte) sau orizontale (frate - frate).
Dacă numărul maxim de referinţe ale unui nod este n, elementul corespunzător
nodului poate fi reprezentat ca în fig. 2.7. Absenţa unei legături se semnalează
printr-o valoare specială nil.
LEG1 LEG2 … LEGn Informaţie utilă
Fig. 2.4. Reprezentarea unui nod cu n referinţe
Reţeaua (graful) este o structură dinamică în care elementele componente nu sunt
grupate pe niveluri ierarhice, putând exista legături între oricare dintre noduri.
Fiecare nod poate avea un număr oarecare de referinţe şi poate fi referit, la rândul
său, de un număr oarecare de alte noduri. Dacă numărul maxim de referinţe ale
unui nod este n, reprezentarea acestuia se poate face ca în fig. 2.7.
Implementarea tipurilor abstracte de date
Prima etapă în implementarea unui TAD este alegerea limbajului de programare.
Aceasta se va baza pe cunoaşterea tipurilor de date şi a facilităţilor de
implementare pe care le oferă limbajul respectiv. În continuare este dată o
clasificare generală a tipurilor de date pe care le posedă limbajele de programare de
nivel înalt. În fiecare caz sunt date exemple specifice limbajului Pascal.
După componenţa elementelor, tipurile de date se împart în:
simple (atomice) - integer, real, char, enumerare, subdomeniu, pointer;
structurate - omogene (tablou - array, mulţime set) sau heterogene
(articol - record).
După relaţiile între elementele domeniului, se disting:
tipuri de date ordinale (au operatori relaţionali - integer, real, char,
enumerare, subdomeniu);
136
tipuri liniare (au operatori de precedenţă - integer, char, enumerare,
subdomeniu);
tipuri amorfe (au doar operatori de atribuire şi egalitate - real, set, array,
record, pointer).
După specificarea în limbajul de programare, tipurile de date sunt:
predefinite - integer, real, char;
definite de utilizator (pe baza tipurilor existente, preluând de la acestea
reprezentarea, dar nu şi operaţiile existente) - enumerare, subdomeniu.
După gradul de abstractizare, tipurile de date sunt:
clasice;
abstracte (încapsulează date şi operaţii şi permit moştenirea acestora) -
object.
Limbajele noi de programare includ mecanisme proprii abstractizării datelor,
programării modulare şi obiectuale. Limbajele clasice apar în versiuni noi, care
extind limbajul standard. Versiunile limbajului Turbo Pascal includ mecanisme de
modularizare (unit-uri, începând cu versiunea 4.0) şi de programare obiectuală
(începând cu versiunea 5.5). Mecanismele de programarea obiectuală sunt
inexistente în limbajul C dar sunt prezente în limbajul C++.
Implementare unui TAD se va face pe baza tipurilor de date predefinite şi a
mecanismelor de tipizare şi abstractizare ale limbajului de programare ales.
Specificarea TAD-ului trebuie respectată întocmai la implementare. Pentru acelaşi
TAD pot fi imaginate implementări diferite. Alegerea algoritmilor utilizaţi la
implementare se va face după criterii de eficienţă specifice domeniului de utilizare.
Cele mai des utilizate criterii sunt cele privitoare la memoria necesară reprezentării
şi la timpul de execuţie a operaţiilor.
O problemă deosebit de importantă o reprezintă regăsirea unei instanţe a unui tip de
date, pe suportul de memorie. Regăsirea poate fi:
poziţională;
legată.
Regăsirea poziţională presupune determinarea adresei fizice a elementului căutat,
prin calcul. Ea se bazează pe o relaţie de ordine stabilită pe mulţimea elementelor,
relaţie definită de poziţia pe care elementul o ocupă în memorie. Se presupune că
se cunoaşte lungimea de reprezentare a unui element şi numărul de ordine al
elementului căutat. Regăsirea este rapidă, dar actualizarea elementelor (eliminare,
adăugare) este laborioasă, necesitând recopierea unor elemente.
Regăsirea legată impune ca fiecare element să conţină ca informaţie suplimentară
adresa următorului element. Actualizarea elementelor necesită doar modificarea
informaţiilor de legătură.
În continuare este dată o posibilă implementare, în limbajul Pascal, a tipului de date
Natural, conform specificaţiei informale prezentate anterior.
137
unit UNatural;
interface
{Tipul Natural se reprezinta ca subdomeniu al tipului predefinit LongInt}
type Natural = 0 .. MaxLongint;
function Zero: Natural;
function EZero(x: Natural): Boolean;
function Succesor(x: Natural): Natural;
function Predecesor(x: Natural): Natural;
function MaiMicSauEgal(x, y: Natural): Boolean;
function Egal(x, y: Natural): Boolean;
function Aduna(x, y: Natural): Natural;
function Scade(x, y: Natural): Natural;
function Inmulteste(x, y: Natural): Natural;
function Imparte(x, y: Natural): Natural;
implementation
procedure Eroare(Sir: String);
begin
WriteLn(‘EROARE!!! ‘, Sir);
ReadLn;
Halt;
end;
function Zero: Natural;
begin
Zero := 0
end;
function EZero(x: Natural): Boolean;
begin
EZero := (x = Zero)
end;
function Succesor(x: Natural): Natural;
begin
if x < MaxLongInt then Succesor := x + 1
else Eroare(‘Numar prea mare!)
end;
138
function Predecesor(x: Natural): Natural;
begin
if not EZero(x) then Predecesor:= x - 1
else Eroare(‘Nu are predecesor!’)
end;
function MaiMicSauEgal(x, y: Natural): Boolean;
begin
MaiMicSauEgal := (x <= y)
end;
function Egal(x, y: Natural): Boolean;
begin
Egal := (MaiMicSauEgal(x,y) and MaiMicSauEgal(y,x))
end;
function Aduna(x, y: Natural): Natural;
begin
if Int(x) + Int(y) <= Int(MaxLongInt) then Aduna := (x + y)
else Eroare(‘Rezultat prea mare!)
end;
function Scade(x, y: Natural): Natural;
begin
if y <= x then Scade := x-y
else Eroare(‘X<Y’!)
end;
function Inmulteste(x, y: Natural): Natural;
begin
if Int(x) * Int(y) <= Int(MaxLongInt) then Inmulteste := x * y
else Eroare(‘Rezultat prea mare’)
end;
function Imparte(x, y: Natural): Natural;
begin
if not EZero(y) then Imparte := x div y
else Eroare(‘Impartire la zero!’)
end;
end.
139
Un program pentru testarea unit-ului UNatural ar putea fi cel de mai jos.
Program Test_unit_UNatural;
uses UNatural, Crt;
var
Operatie: Integer;
x,y: Natural;
begin
clrscr;
Write('x, y: '); Readln(x,y);
Writeln('1 Aduna, 2 Scade, 3 Inmulteste, 4 Imparte');
Write('Operatie: '); Readln(Operatie);
case Operatie of
1: Writeln(Aduna(x,y));
2: Writeln(Scade(x,y));
3: Writeln(Inmulteste(x,y));
4: Writeln(Imparte(x,y));
end;
readln;
end.
Tipuri colecţie
Datele compuse de tip colecţie conţin un număr finit de elemente. Dacă pentru
tipul elementelor ce formează colecţia este definit un operator de ordonare (o
relaţie de ordine), colecţia este ordonată. În caz contrar colecţia este neordonată.
Colecţiile pot admite sau nu elemente multiple.
După tipul elementelor componente, colecţiile pot fi:
omogene (tablou de reali, string, stive de elemente întregi etc.);
heterogene (listă liniară de primitive grafice etc.).
Colecţiile pot fi:
de mărime fixă (tablou, string etc.);
de mărime variabilă (listă liniară sau arbore generate dinamic etc.).
Funcţiile primitive ale tipurilor colecţie pot fi:
de tip constructori;
de adăugare a unui element la colecţie;
140
de eliminare a unui element din colecţie;
de selecţie a unui element al colecţiei;
de testare a colecţiei vide.
Funcţiile derivate ale tipurilor colecţie reprezintă operaţii de:
căutare;
sortare;
interclasare;
traversare.
Liste liniare
Lista este una din structurile fundamentale de date, reprezentând un mod uzual de a
păstra o colecţie de elemente, în orice domeniu: lista studenţilor unei facultăţi, lista
medicamentelor existente într-o farmacie, lista abonaţilor unei centrale telefonice,
lista materialelor existente într-o magazie etc. Astfel de liste sunt actualizate
continuu, prin adăugarea de noi elemente, eliminarea unor elemente sau
modificarea unor elemente existente în listă. Listele sunt aşadar dinamice prin
natura lor. În memorie listele pot fi reprezentate prin structuri statice (tablouri) sau
prin structuri dinamice (liste înlănţuite).
Lista este o structură de date omogenă, formată din elemente ale listei. Elementele
pot fi de acelaşi tip atomic, caz în care lista este liniară simplă, sau pot fi la rândul
lor liste, caz în care lista este neliniară. Proprietăţile unei liste sunt independente
de proprietăţile tipului elementelor listei.
O listă este fie vidă fie este alcătuită dintr-un element de listă numit cap şi o listă
numită coadă (restul listei). Lista cu un singur element are lista coadă vidă. Lista
poate fi definită recursiv astfel:
listă tip_el_listă: listă_vidă / tip_el_listă cap listă tip_el_listă coadă
O caracteristică esenţială a unei liste este faptul că între elementele ei există
legături. Orice element al listei conţine, pe lângă informaţia utilă, şi o informaţie
de legătură. Prin legarea elementelor listei, există un unic element al listei numit
primul (capul listei) şi un unic element numit ultimul, a cărui informaţie de
legătură indică o valoare specială (nil), care nu reprezintă adresa nici unui element
din listă. Fiecare element al listei, cu excepţia primului, are un predecesor unic.
Fiecare element al listei, cu excepţia ultimului, are un succesor unic. Pentru ca
toate elementele listei să aibă predecesor şi succesor, în listă se pot introduce două
141
elemente false, numite santinele, plasate la începutul listei (înaintea primului
element al listei) şi la sfârşitul listei (după ultimul element din listă).
Toate operaţiile de prelucrare a listei operează cu poziţia curentă în listă, definită
ca poziţia elementului accesibil la momentul dat. Operaţiile se efectuează asupra
elementului curent. Elementul curent este singurul “vizibil” la un moment dat.
Toate elementele pot deveni, pe rând, “vizibile” prin modificarea poziţiei curente în
listă.
CAP
INF1 LEG1 INF2 LEG2 … INFn LEGn=nil
Fig. 2.5. Lista simplu înlănţuită
Dacă informaţia de legătură a fiecărui element al listei conţine doar adresa
succesorului său, lista este simplu înlănţuită (fig. 2.13). Listele liniare simplu
înlănţuite pot fi parcurse doar într-un singur sens, de la primul spre ultimul
element.
Operaţiile care presupun referirea la predecesorul elementului curent, cum sunt
inserarea unui element înaintea elementului curent sau ştergerea elementului
curent, sunt dificil de realizat pentru listele simplu înlănţuite. Dacă informaţia de
legătură a fiecărui element al listei conţine atât adresa succesorului cât şi a
predecesorului său, lista este dublu înlănţuită (fig. 2.14). Listele liniare dublu
înlănţuite pot fi parcurse în ambele sensuri, atât de la primul spre ultimul element,
cât şi de la ultimul spre primul element.
Pred1=nil INF1 Succ1 Pred2 INF2 Succ2 … Predn INFn Succn=nil
Fig. 2.6. Lista dublu înlănţuită
Dacă ultimul element este legat cu primul element, lista capătă o structură
circulară. În acest caz santinelele nu mai sunt necesare, primul element fiind
succesorul ultimului, iar ultimul element fiind predecesorul primului.
Structura unei liste poate fi modificată prin:
142
iniţializarea unei liste ca o listă vidă;
adăugare de noi elemente la sfârşitul listei;
inserare de noi elemente pe orice poziţie în listă;
ştergere de elemente de pe orice poziţie a listei;
modificarea unor elemente din listă.
Operaţii care nu modifică structura listei dar dau informaţii despre ea
(caracterizează lista) sunt:
determinarea lungimii listei (numărul de elemente din listă);
localizarea poziţiei elementului care satisface un criteriu dat.
Operaţii mai complexe asupra listelor sunt:
partiţionarea unei liste în două sau mai multe subliste;
combinarea a două sau mai multe liste într-una singură, prin
concatenare (simplă alipire) sau interclasare (ordinea elementelor în
noua listă e stabilită conform unui criteriu dat);
selecţia elementelor dintr-o listă, care îndeplinesc un criteriu dat;
ordonarea (ascendentă sau descendentă) a unei liste, după o cheie.
i. Implementarea dinamică a tipului abstract de date Lista
O implementare a TAD Lista, pe baza unei liste simplu înlănţuită este data mai
jos, prin unit-ul ULista. Alocarea memoriei se face dinamic. Elementele listei pot fi
de orice tip. Acest lucru este posibil prin utilizarea în nodurile listei a pointerilor
generici către elemente. Lista este formată din noduri, care păstrează referinţe la
elementele propriu-zise. Operaţiile asupra elementelor listei sunt, de fapt, operaţii
asupra nodurilor listei. Aşadar elementele listei sunt noduri, a căror informaţiei
utilă reprezintă referinţe către elementele propriu-zise.
Lista este o structură cu doi indicatori (fig. 2.15):
Cap - indică primul nod al listei;
Curent - indică poziţia curentă în listă.
Lista e declarată ca un articol cu două câmpuri, Cap şi Curent, iar nodul este un
articol ale cărui câmpuri sunt:
Element - pointer la elementul propriu-zis;
Urmatorul - pointer la nodul următor al listei.
143
Cap Curent
e1 e2 … ei-1 ei ei+1 … en nil
Fig. 2.7 Listă simplu înlănţuită cu doi indicatori (Cap, Curent)
{
Implementare TAD Lista prin lista simplu inlantuita.
Indicatori Cap (primul nod al listei) si Curent (nodul curent).
Alocare dinamica.
Informatia din noduri reprezinta pointeri la informatia utila.
Listele pot avea orice tip de elemente.
}
unit ULista;
Interface
type
{tip Nod lista}
PNod = ^Nod;
Nod = record
Element: pointer;
Urmatorul: PNod
end;
{tip lista}
Lista = record
Cap, Curent: PNod
end;
{initializare lista}
procedure Creaza(var L: Lista);
{test lista vida}
function EVida(L: Lista): Boolean;
{test pozitionare pe primul nod}
function EPrimul(L: Lista): Boolean;
{test pozitionare pe ultimul nod}
144
function EUltimul(L: Lista): Boolean;
{pozitionare pe primul nod}
function PePrimul(var L: Lista): Boolean;
{pozitionare pe ultimul nod}
function PeUltimul(var L: Lista): Boolean;
{pozitionare pe nodul urmator}
function PeSucc(var L: Lista): Boolean;
{pozitionare pe nodul precedent}
function PePrec(var L: Lista): Boolean;
{inserare dupa nodul curent}
procedure Insereaza(var L: Lista; e: pointer);
{adaugare la sfarsitul listei}
procedure Adauga(var L: Lista; e: pointer);
{stergere nodul curent}
procedure Sterge(var L: Lista);
{actualizare nod}
procedure Actualizeaza(var L: Lista; e: pointer);
{extragere nod}
procedure Extrage(var L: Lista; var e: pointer);
{lungime lista}
function Lungime(var L: Lista): Integer;
Implementation
procedure Creaza(var L: Lista);
begin
L.Cap := nil;
end;
function EVida(L: Lista): Boolean;
begin
EVida := (L.Cap = nil)
end;
function EPrimul(L: Lista): Boolean;
begin
if not EVida(L) then EPrimul := (L.Curent = L.Cap)
else EPrimul:=False;
end;
function EUltimul(L: Lista): Boolean;
begin
if not EVida(L) then EUltimul := (L.Curent^.Urmatorul = nil)
145
else EUltimul := False;
end;
function PePrimul(var L: Lista): Boolean;
begin
if not EVida(L) then
begin
L.Curent := L.Cap;
PePrimul := True;
end
else PePrimul := False;
end;
function PeUltimul(var L: Lista): Boolean;
begin
if not EVida(L) then
begin
repeat
until not PeSucc(L);
PeUltimul := True;
end
else PeUltimul := False;
end;
function PeSucc(var L: Lista): Boolean;
begin
if EVida(L) then PeSucc := False
else
begin
PeSucc := True;
if not Eultimul(L) then L.Curent := L.Curent^.Urmatorul
else PeSucc := False
end;
end;
function PePrec(var L: Lista): Boolean;
var p: PNod;
begin
if (not EVida(L)) and (L.Curent <> L.Cap) then
begin
p := L.Curent;
if PePrimul(L) then
repeat
146
until (p = L.Curent^.Urmatorul) or (not PeSucc(L))
else PePrec := False;
end
else PePrec := False;
end;
procedure Insereaza(var L: Lista; e: pointer);
var p: PNod;
begin
New(p);
p^.Element := e;
if EVida(L) then begin
p^.Urmatorul := L.Cap;
L.Cap := p;
L.Curent := p
end
else begin
p^.Urmatorul := L.Curent^.Urmatorul;
L.Curent^.Urmatorul := p;
L.Curent := p
end
end;
procedure Adauga(var L: Lista; e: pointer);
var p: PNod;
begin
if EVida(L) then Insereaza(L, e)
else
begin
repeat
until not PeSucc(L);
New(p);
p^.Element := e;
p^.Urmatorul := L.Curent^.Urmatorul;
L.Curent^.Urmatorul := p;
L.Curent := p
end;
end;
procedure Sterge(var L: Lista);
var p: PNod;
begin
if not EVida(L) then
147
begin
p := L.Curent;
if PePrec(L) then L.Curent^.Urmatorul := p^.Urmatorul;
else L.Cap := L.Cap^.Urmatorul;
if p^.Urmatorul <> nil then L.Curent := p^.Urmatorul;
{OPTIONAL - eliminarea elementului din memorie}
Dispose(p^.Element);
{eliminarea nodului din lista}
Dispose(p);
end;
end;
procedure Actualizeaza(var L: Lista; e: pointer);
begin
if not EVida(L) then
begin
{OPTIONAL - eliminarea vechiului element din memorie}
Dispose(L.Curent^.Element);
L.Curent^.Element := e
end;
end;
procedure Extrage(var L: Lista; var e: pointer);
begin
if not EVida(L) then e := L.Curent^.Element
end;
function Lungime(var L: Lista): Integer;
var i: Integer;
begin
i := 0;
if (not EVida(L)) and PePrimul(L) then
repeat
i := i+1;
until not PeSucc(L);
Lungime := i;
end;
end.
Procedura Sterge realizează atât eliminarea nodului curent din listă cât şi
eliminarea elementului propriu-zis din memorie. După efectuarea operaţiei nodul
148
succesor al nodului eliminat devine nod curent. Procedura Actualizeaza elimină şi
ea vechiul element din memorie. Implementarea celor două operaţii poate fi
modificată, astfel încât elementele să fie eliminate ca noduri din listă dar păstrate în
memorie. Această abordare este mai logică pentru că, aşa cum s-a mai precizat,
lista este formată din noduri asupra cărora acţionează operaţiile. Crearea şi
eliminarea din memorie a elementelor propriu-zise pot fi lăsate pe seama
aplicaţiei. Înainte de alocarea memoriei pentru noduri (respectiv elemente) noi
trebuie să se verifice dacă există memorie disponibilă. În Turbo Pascal acest lucru
se poate face cu ajutorul funcţiei MaxAvail.
Condiţia Cap = nil este suficientă pentru ca lista să fie vidă. Din acest motiv nu
este necesar ca procedura Creaza să iniţializeze şi indicatorul Curent = nil.
Operaţiile Adaugă, Şterge, PeUltimul, PePred şi Lungime sunt de complexitate
O(l), dacă l este lungimea listei. Toate celelalte operaţii sunt de complexitate O(1).
Complexitatea operaţiei Şterge se reduce la O(1) dacă implementarea se realizează
pe baza unei liste simplu înlănţuite cu trei indicatori: Cap, Curent şi Precedent (fig.
2.16).
Precedent
Cap Curent
e1 e2 … ei-1 ei ei+1 … en nil
Fig. 2.8 Listă simplu înlănţuită cu trei indicatori (Cap, Curent, Precedent)
Prin utilizarea unei liste circulare simplu înlănţuite cu doi indicatori, Coadă şi
Curent (fig. 2.17), complexitatea operaţiei Adaugă se reduce la O(1), dar
complexitatea operaţiei Şterge rămâne O(l). În acest caz indicatorul Cap devine
inutil, primul nod al listei fiind indicat de legătura ultimului nod. Complexitatea
operaţiei PeUltimul se reduce şi ea la O(1).
Curent Coadă
e1 e2 … ei-1 ei ei+1 … en
Fig. 2.9 Listă circulară simplu înlănţuită cu doi indicatori (Coadă, Curent)
149
Dacă se utilizează o listă circulară simplu înlănţuită cu trei indicatori, Coadă,
Curent şi Precedent (fig. 2.18), complexitatea operaţiilor Adaugă şi Şterge se
reduce la O(1), dar complexitatea operaţiei PeUltimul rămâne O(l).
Precedent
Curent Coadă
e1 e2 … ei-1 ei ei+1 … en
Fig. 2.10 Listă circulară simplu înlănţuită cu trei indicatori (Coadă, Curent,
Precedent)
În toate cele patru cazuri de liste simplu înlănţuite prezentate, structura unui nod
este aceeaşi (Element, Urmatorul). Structura listei diferă de la caz la caz, în funcţie
de indicatorii utilizaţi.
Listele dublu înlănţuite pot fi parcurse în ambele sensuri. În cazul listelor dublu
înlănţuite structura unui nod trebuie să fie:
Element - pointer la elementul propriu-zis;
Urmatorul - pointer la nodul următor al listei;
Precedentul - pointer la nodul precedent al listei.
Structura unei liste dublu înlănţuite este tot de tip articol cu două componente
(Cap, Curent), ca şi în cazul listei simplu înlănţuite. Indicatorul Precedent devine
inutil, fiecare nod al listei având o legătură la nodul precedent (fig 2.19). Prin
utilizarea unei astfel de liste complexitatea operaţiilor Şterge şi PePrec se reduce la
O(1).
Cap Curent
nil e1 e2 … ei-1 ei ei+1 … en nil
Fig. 2.11 Listă dublu înlănţuită cu doi indicatori (Cap, Curent)
În cazul unei liste circulare dublu înlănţuite (fig. 2.20) complexitatea tuturor
operaţiilor (mai puţin Lungime) devine O(1).
150
Curent Coadă
e1 e2 … ei-1 ei ei+1 … en
Fig. 2.12 Listă circulară dublu înlănţuită cu doi indicatori (Coadă, Curent)
Complexitatea operaţiilor Adaugă şi PeUltimul poate fi redusă la O(1) în toate
cazurile, prin introducerea în structura listei a indicatorului Coadă. Complexitatea
operaţiei Lungime poate fi redusă la O(1) în toate cazurile, prin introducerea în
structura listei a indicatorului Lungime. În mod evident, aceşti indicatori trebuie să
fie actualizaţi, când este cazul, de către operaţiile asupra listei.
Un program pentru testarea unit-ului ULista poate fi cel prezentat în continuare.
Elementele listei vor fi numere întregi. Programul poate fi uşor adaptat pentru
lucrul cu liste ale căror elemente au un alt tip. Pentru aceasta se vor schimba
declaraţia tipului PElement şi, corespunzător, procedurile de I/O.
{Testare unit ULista}
Program Operatii_cu_liste;
uses ULista, Crt;
type
{tipul elementelor listei}
PElement = ^Integer;
var
optiune: Integer;
L: Lista;
e: pointer;
element: PElement;
{cauta in lista elementul dat}
function Cauta (L:lista; e:pointer):Boolean;
var elem: pointer;
begin
Cauta := False;
if not EVida(L) then
151
begin
PePrimul(L);
repeat
Extrage(L, elem);
if PElement(e)^=PElement(elem)^ then Cauta := true;
until not PeSucc(L)
end;
end;
{afiseaza elementele listei}
procedure Afiseaza (L:lista);
var e: pointer;
begin
if not EVida(L) then
begin
PePrimul(L);
repeat
Extrage(L, e);
writeln(PElement(e)^);
until not PeSucc(L)
end;
end;
begin
clrscr;
Creaza(L);
repeat
Writeln('1 - Testeaza lista vida');
Writeln('2 - Test pozitionare pe primul element');
Writeln('3 - Test pozitionare pe ultimul element');
Writeln('4 - Adauga la sfarsitul listei');
Writeln('5 - Insereaza dupa elementul curent');
Writeln('6 - Cauta elementul in lista');
Writeln('7 - Pozitionare pe primul element');
Writeln('8 - Pozitionare pe elementul urmator');
Writeln('9 - Pozitionare pe elementul precedent');
Writeln('10 - Pozitionare pe ultimul element');
Writeln('11 - Extrage valoarea elementului curent');
Writeln('12 - Actualizeaza elementul curent');
Writeln('13 - Sterge elementul curent');
Writeln('14 - Afiseaza lista');
Writeln('15 - Da lungimea listei');
Writeln('16 - Termina executia programului');
152
Read(optiune);
if optiune in [4, 5, 6, 12] then
begin
new(element);
Readln(element^);
e := element;
end;
case optiune of
1: if EVida(L) then Writeln('Lista e vida!') else Writeln('Lista nu e
vida!');
2: if EPrimul(L) then Writeln('E primul!') else Writeln('Nu e primul!');
3: if EUltimul(L) then Writeln('E ultimul!') else Writeln('Nu e ultimul!');
4: Adauga(L, e);
5: Insereaza(L, e);
6: if Cauta(L, e) then Writeln('Elementul ', PElement(e)^, ' se afla in
lista')
else Writeln('Elementul ', PElement(e)^, ' nu se afla in lista');
7: if not PePrimul(L) then Writeln('Eroare!!! Lista e vida!');
8: if not PeSucc(L) then Writeln('Eroare!!! Nu are succesor!');
9: if not PePrec(L) then Writeln('Eroare!!! Nu are predecesor!');
10: if not PeUltimul(L) then Writeln('Eroare!!! Lista e vida!');
11: if EVida(L) then Writeln('Eroare!!! Lista e vida!')
else begin
Extrage(L, e);
Writeln(PElement(e)^)
end;
12: if EVida(L) then Writeln('Eroare!!! Lista e vida!') else
Actualizeaza(L, e);
13: if EVida(L) then Writeln('Eroare!!! Lista e vida!') else Sterge(L);
14: if EVida(L) then Writeln('Lista e vida!') else Afiseaza(L);
15: Writeln(Lungime(L));
end;
until optiune = 16;
end.
Implementarea statică a tipului abstract de date Lista
Între elementele unei liste liniare cu n elemente, x1, x2, ... , xn şi submulţimea
numerelor naturale {1, 2, …, n} se poate stabili o corespondenţă biunivocă.
153
Primului element al listei (x1) i se asociază numărul natural 1, celui de-al doilea
element (x2) i se asociază numărul natural 2, iar ultimului element (xn) i se asociază
numărul natural n. Numărul natural asociat unui element al listei defineşte poziţia
elementului în listă.
Ordinea elementelor listei este dată de poziţiile acestora în listă. Orice element al
listei, cu excepţia primului, are un predecesor. Orice element al listei, cu excepţia
ultimului, are un succesor. Legăturile între elemente nu mai trebuie să fie precizate
explicit, ele fiind implicite, prin poziţia elementelor în listă. Elementul xi va avea
ca predecesor pe xi-1 şi ca succesor pe xi+1. O astfel de listă este aşadar similară
listei dublu înlănţuite.
Consideraţiile de mai sus conduc la ideea de implementare a listelor prin tablouri.
Poziţia unui element în listă va fi determinată de poziţia sa în tablou. Primul
element al tabloului va reprezenta primul element al listei, iar elementul de pe
ultima poziţie ocupată a tabloului va reprezenta ultimul element al listei. Ca şi în
cazul implementării dinamice, elementele tabloului pot fi referinţe la elementele
propriu-zise ale listei (similare nodurilor de la implementarea dinamică). Acest
lucru va asigura faptul că pot fi gestionate liste cu elemente de orice tip. Alocarea
memoriei pentru elementelor propriu-zise se face dinamic.
Dezavantajul implementării unei liste printr-o structură statică (tablou) îl constituie
faptul că alocarea spaţiului de memorie pentru listă se face de la început şi nu mai
poate fi modificată pe parcurs. Numărul maxim de elemente din listă este egal cu
dimensiunea tabloului.
O listă implementată static va avea doi indicatori:
Curent - indică poziţia curentă în listă;
Ultim - indică ultima poziţie ocupată în listă.
Aceşti doi indicatori vor fi de tip întreg şi vor reprezenta indici în tabloul prin care
lista este implementată (fig. 2.21).
Curent Ultim
e1 e2 … ei-1 ei ei+1 … en …
Ultimul element al tabloului
Fig. 2.13 Implementare statică a TAD Lista
Toate operaţiile vor avea complexitate O(1), mai puţin Şterge şi Inserează, care vor
avea complexitate O(l). În ambele cazuri referinţele spre toate elementele ce succed
154
elementul curent vor trebui deplasate în tablou. În cazul operaţiei Şterge deplasarea
se va face spre stânga, pentru a se ocupa poziţia corespunzătoare elementului
eliminat din listă (fig. 2.22).
e1 e2 … ei-1 ei ei+1 … en
Fig. 2.14 Ştergere în listă implementată static
În cazul operaţiei Inserează deplasarea referinţelor spre elementele de după
elementul curent se va face spre dreapta, pentru a se elibera o poziţie
corespunzătoare noului element (fig. 2.23).
enou
e1 e2 … ei-1 ei ei+1 … en
Fig. 2.15 Inserare în listă implementată static
Liste ordonate
Un caz particular îl constituie listele ordonate, în care elementele ocupă în listă o
ordine stabilită după o cheie de ordonare. Toate operaţiile efectuate asupra listei
trebuie să păstreze lista ordonată.
Operaţiile afectate de obligativitatea ordonării listei sunt Adaugă, Inserează şi
Actualizează. Operaţia Adaugă nu are sens în cazul listelor ordonate, pentru că ea
poate afecta ordinea elementelor în listă.
Operaţia Inserează nu va mai introduce noul element după elementul curent, ci pe
o poziţie în concordanţă cu valoarea elementului nou introdus. Problema poate fi
rezolvată dacă operaţia este precedată de o repoziţionare în listă, astfel încât ultimul
element care respectă relaţia de ordine faţă de elementul ce va fi inserat în listă,
155
conform criteriului de ordonare, să devină noul element curent. Operaţia Inserează
poate fi apoi efectuată, pentru că ea va introduce în listă noul element pe o poziţie
care nu va afecta ordonarea. Dacă primul element al listei nu respectă relaţia de
ordine faţă de elementul nou, inserarea trebuie să se facă în capul listei.
Operaţia Actualizează nu se va mai limita la modificarea valorii elementului curent
din listă ci îl va repoziţiona în concordanţă cu noua sa valoare, conform criteriului
de ordonare. Operaţia Actualizează va implica, de fapt, o operaţie de ştergere a
elementului curent şi una de inserare a noului element. Operaţia Ştergere nu
afectează ordinea elementelor.
Stive şi cozi
Aşa cum am văzut până acum, în cazul listelor este importantă poziţia unui element
în listă şi nu momentul în care elementul a fost introdus în listă. Locul elementului
în listă este ales de utilizator sau este impus de informaţia utilă a elementului, în
cazul listelor ordonate. Un singur element este accesibil la un moment dat, dar toate
elementele pot fi făcute pe rând accesibile, prin modificarea poziţiei curente în
listă.
Există multe cazuri în care pentru o colecţie de elemente este esenţial momentul de
timp în care fiecare element a fost introdus în colecţie. Criteriul de alegere a
elementului curent, care va fi supus următoarei prelucrări, este dat de ordinea
introducerii elementelor în colecţie.
Să presupunem că în bucătăria unui restaurant farfuriile spălate se aşează pe un
raft, una peste alta. Se obţine o stivă de farfurii, iar în momentul servirii clienţilor
farfuria aşezată în vârful stivei va fi utilizată prima. Ea fiind ultima aşezată în stivă,
se poate spune că accesul la elementele stivei se face după principiul “ultimul
intrat, primul ieşit” (LIFO - Last In First Out). Un principiu identic se poate aplica
în cazul angajaţilor unei firme, dacă singurul criteriu de evaluare al acestora este
vechimea lor în firmă. Primul angajat ce va fi avut în vedere la o eventuală
concediere va fi angajatul cel mai nou, cu cea mai mică vechime în firmă.
Să analizăm acum cazul clienţilor unui magazin. În mod normal, aceştia vor fi
serviţi în ordinea intrării lor în magazin. Ei formează o coadă la care îşi aşteaptă
rândul pentru a fi serviţi. Spre deosebire de stivă, accesul la elementele cozii se
face după principiul “primul intrat, primul ieşit” (FIFO - First In First Out).
Acelaşi principiu este evident în cazul vagoanelor unui tren, la trecerea acestuia
printr-un tunel, se aplică maşinilor dintr-o intersecţie etc.
Atât stivele cât şi cozile sunt colecţii ordonate de elemente, dar relaţia de ordine
între elemente nu are legătură cu informaţia utilă conţinută în elemente, ci depinde
exclusiv de momentele integrării elementelor în colecţie. Proprietăţile colecţiilor de
tip stivă şi coadă sunt independente de tipul elementelor din colecţie. Atât în cazul
stivelor cât şi în cazul cozilor, un singur element este “vizibil” la un moment dat şi
va putea fi extras din colecţie în vederea prelucrării. În cazul stivei elementul
156
accesibil va fi cel plasat în vârful stivei, elementul cel mai nou din colecţie. În
cazul cozii elementul accesibil va fi cel plasat în capul cozii, elementul cel mai
vechi din colecţie. Se observă că structurile de date de tip stivă şi coadă trebuie să
aibă un mecanism care să memoreze ordinea în care elementele sunt introduse în
structură. Această ordine nu mai poate fi modificată.
Stivele şi cozile pot fi considerate cazuri particulare de liste. Ele sunt liste
specializate în privinţa accesului la elemente. Dacă în cazul listelor orice element
poate deveni accesibil, prin modificarea poziţiei curente, în cazul stivelor şi cozilor
se impun restricţii suplimentare. Poziţia curentă în listă nu poate fi modificată
arbitrar şi un singur element poate fi accesibil la un moment dat, conform
mecanismului de stivă, respectiv coadă.
Dacă o listă implementează o structură de tip stivă, introducerea şi extragerea
elementelor se va face la acelaşi capăt al listei (fig. 2.24), “în faţa” celorlalte
elemente din stivă.
Introducere/Extragere
e1 e2 … ei-1 ei ei+1 … en
nil
Fig. 2.16 Listă ce implementează o structură de tip stivă
În cazul în care lista implementează o structură de tip coadă, introducerea şi
extragerea elementelor din listă se va face la capete diferite (fig. 2.25). Fiecare nou
element este introdus “în spatele” celorlalte elemente din coadă, iar elementul care
se găseşte “în faţă” va fi primul extras.
Extragere Introducere
e1 e2 … ei-1 ei ei+1 … en
nil nil
Fig. 2.17 Listă ce implementează o structură de tip coadă
Operaţiile de bază în cazul stivelor şi cozilor sunt:
introducerea unui element în colecţie;
157
extragerea unui element din colecţie.
Dacă în cazul listelor extragerea şi eliminarea unui element din colecţie sunt
operaţii distincte, în cazul stivelor şi cozilor extragerea elementului accesibil la un
moment dat presupune, în mod normal, şi eliminarea sa din colecţie. Următorul
element va deveni element curent.
Alte operaţii ce se pot defini pentru colecţii de tip stivă sau coadă sunt:
iniţializarea colecţiei;
testarea colecţiei vide;
extragerea elementului curent fără eliminarea lui din colecţie.
Ca şi colecţiile de tip listă, colecţiile de tip stivă şi coadă pot fi implementate static
sau dinamic.
O generalizare a colecţiilor de tip stivă şi coadă o reprezintă colecţia de tip coadă
generalizată (sau stivă generalizată). O astfel de structură trebuie să permită
introducerea şi extragerea de elemente de la oricare din cele două capete.
Tipul de date Stiva
Stivele sunt colecţii din care elementele pot fi eliminate doar în ordinea inversă
introducerii lor. Stiva este o structură dinamică pentru că dimensiunea ei variază
prin introducerea şi eliminarea de elemente.
Stivele nu sunt adecvate prelucrărilor ce necesită traversarea colecţiilor. Ele sunt
mult utilizate ca suport pentru funcţiile recursive, apelul imbricat al funcţiilor şi
evaluarea expresiilor aritmetice în formă postfixată.
Operaţia de introducere a unui element în stivă se numeşte, de obicei, PUSH iar
operaţia de extragere a unui element din stivă se numeşte, de obicei, POP.
Mecanismul de apel recursiv fiind des utilizat, în limbajele de asamblare aceste
operaţii sunt implementate ca instrucţiuni cu acelaşi nume.
Unit-ul UStiva implementează TAD-ul Stiva static, printr-un tablou de pointeri.
Toate operaţiile au fost implementate ca funcţii ce returnează o valoare booleană:
True, dacă operaţia s-a efectuat corect, şi False, dacă operaţia nu a putut fi
executată.
Stiva este declarată ca o structură formată din (fig. 2.26):
Elemente - tablou de pointeri la elementele stivei;
Varf - poziţia pe care se va adăuga următorul element.
Numărul maxim de elemente din stivă este MAX, deşi numărul total de componente
al tabloului Elemente este MAX+1 (de la 0 la MAX). În implementarea realizată
prin unit-ul UStiva stiva este considerată plină atunci când Varf = MAX.
158
Varf
x x x x x x x …
0 1 2 MAX
Fig. 2.18 Implementarea statică a unei stive
{
Implementare statica (tablou de pointeri) a TAD-ului Stiva.
Indicator Varf (pozitia pe care se va adauga urmatorul element).
Stiva poate avea orice tip de elemente.
}
Unit UStiva;
Interface
const MAX = 5;
type
{tip indice tablou}
tip_indice = 0..MAX;
{tip stiva}
PStiva = ^Stiva;
Stiva = record
Varf: Integer;
Elemente: Array[tip_indice] of pointer;
end;
{initializare stiva}
function CreazaStiva(var S: Stiva): Boolean;
{test stiva vida}
function EStivaVida(S: Stiva): Boolean;
{adaugarea unui element}
function IntroduceInStiva(var S: Stiva; E: Pointer): Boolean;
{extragerea unui element}
function ExtrageDinStiva(var S: Stiva; var E: Pointer): Boolean;
{returneaza pointer spre elementul accesibil, fara eliminarea lui}
159
function ValoareVarfStiva(S: Stiva; var E: Pointer): Boolean;
Implementation
function CreazaStiva(var S: Stiva): Boolean;
begin
S.Varf := 0;
CreazaStiva := True;
end;
function EStivaVida(S: Stiva): Boolean;
begin
EStivaVida := (S.Varf = 0);
end;
function IntroduceInStiva(var S: Stiva; E: Pointer): Boolean;
begin
with S do
begin
If Varf=MAX then IntroduceInStiva := False
else
begin
Elemente[Varf] := E;
Varf := Varf+1;
IntroduceInStiva := True;
end;
end;
end;
function ExtrageDinStiva(var S: Stiva; var E: Pointer): Boolean;
begin
with S do
begin
If EStivaVida(S) then ExtrageDinStiva := False
else
begin
E := Elemente[Varf-1];
Varf := Varf-1;
ExtrageDinStiva := True;
end;
end;
end;
160
function ValoareVarfStiva(S: Stiva; var E: Pointer): Boolean;
begin
with S do
begin
If EStivaVida(S) then ValoareVarfStiva := False
else
begin
E := Elemente[Varf-1];
ValoareVarfStiva := True;
end;
end;
end;
end.
Programul Turbo Pascal Test_stiva este un program de testare a unit-ului UStiva.
{Testare unit UStiva}
program Test_stiva;
uses UStiva, Crt;
type
{tipul elementelor listei}
PElement = ^Integer;
var
optiune: Integer;
S: Stiva;
E: pointer;
element: PElement;
i: Integer;
begin
clrscr;
CreazaStiva(S);
repeat
Writeln('1 - Testeaza stiva vida');
Writeln('2 - Da lungimea stivei');
Writeln('3 - Adauga');
Writeln('4 - Extrage');
161
Writeln('5 - Afiseaza elementul curent');
Writeln('6 - Afiseaza stiva');
Writeln('7 - Afiseaza pozitia varfului');
Writeln('8 - Termina executia programului');
Read(optiune);
if optiune in [3] then
begin
new(element);
Readln(element^);
E := element;
end;
case optiune of
1: if EStivaVida(S) then Writeln('Stiva e vida!') else Writeln('Stiva nu e
vida!');
2: writeln('Stiva are ', S.Varf, ' elemente.');
3: If IntroduceInStiva(S, E) then writeln('OK!') else writeln('Imposibil!');
4: if not ExtrageDinStiva(S, E) then writeln('Imposibil!')
else writeln(PElement(E)^);
5: if not ValoareVarfStiva(S, E) then writeln('Imposibil!')
else writeln(PElement(E)^);
6: for i:=0 to S.Varf-1 do
begin
E := S.Elemente[i];
writeln(PElement(E)^);
end;
7: writeln('Varful este pe pozitia ', S.Varf);
end;
until optiune = 8;
end.
Tipul de date Coada
Cozile sunt colecţii din care elementele pot fi eliminate doar în ordinea introducerii
lor. Ca şi stiva, coada este o structură dinamică, pentru că dimensiunea ei variază
prin introducerea şi eliminarea de elemente. Tot ca şi stivele, cozile nu sunt
adecvate prelucrărilor ce necesită traversarea colecţiilor.
Unit-ul UCoada implementează TAD-ul Coada static, printr-un tablou de
pointeri. Toate operaţiile au fost implementate ca funcţii ce returnează o valoare
162
booleană: True, dacă operaţia s-a efectuat corect, şi False, dacă operaţia nu a putut
fi executată.
Coada este declarată ca o structură formată din (fig. 2.27):
Elemente - tablou de pointeri la elementele cozii;
Prim - poziţia elementului “vizibil”, care va fi primul extras din coadă;
Ultim - poziţia pe care se va adăuga următorul element;
Lungime - numărul elementelor din coadă.
Indicatorul Ultim nu indică poziţia ultimului element introdus în coadă, ci poziţia
pe care va fi introdus următorul element.
Prim Ultim
x x x x x …
0 1 2 MAX
Fig. 2.19 Implementarea statică a unei cozi
Numărul maxim de elemente din coadă este MAX. Datorită mecanismului cozii,
prin adăugarea elementelor la un capăt si extragerea lor de la un alt capăt, coada se
“deplasează” spre capătul la care se face adăugarea. Poziţiile rămase libere la
capătul de unde se extrag elemente nu mai pot fi utilizate. Pentru a preveni acest
lucru, ar fi necesar ca la fiecare extragere a unui element toate celelalte elemente
din coadă să se deplaseze cu câte o poziţie, astfel încât poziţia rămasă liberă să fie
ocupată (fig. 2.28).
x x x x x …
0 1 2 MAX
Fig. 2.20 Deplasarea elementelor unei cozi
O soluţie mai elegantă o reprezintă transformarea tabloului în care se păstrează
pointerii într-un tablou “circular”. După ocuparea tuturor poziţiilor din tablou la
163
capătul la care se face adăugare, următoarea poziţie disponibilă devine prima
poziţie de la capătul opus al tabloului (fig. 2.29). Acest lucru se poate realiza dacă
indicatorii Prim şi Ultim ai cozii sunt actualizaţi modulo numărul de elemente al
vectorului ce conţine elementele cozii.
La introducerea în coadă a unui nou element se va face actualizarea:
Ultim := (Ultim+1) mod MAX; (2.1)
La extragerea unui element din coadă se va face actualizarea:
Prim := (Prim+1) mod MAX; (2.2)
x … x x x x x
0 1 2 MAX
Fig. 2.21 Implementarea unei cozi prin tablou circular
Deşi numărul total de componente al tabloului Elemente este MAX+1, care ocupă
poziţiile 0 .. MAX, în implementarea realizată prin unit-ul UCoada numărul maxim
de elemente al cozii este MAX. Coada este considerată plină atunci când Lungime =
MAX.
{
Implementare statica (prin tablou de pointeri) a structurii Coada.
Indicatori Prim (pozitia elementului accesibil) si
Ultim (pozitia pe care se va adauga urmatorul element).
Coada poate avea orice tip de elemente.
}
Unit UCoada;
Interface
const MAX = 10;
type
{tip indice tablou}
164
tip_indice = 0..MAX;
{tip coada}
PCoada = ^Coada;
Coada = record
Prim, Ultim, Lungime: Integer;
Elemente: Array[tip_indice] of pointer;
end;
{initializare coada}
function CreazaCoada(var C: Coada): Boolean;
{test coada vida}
function ECoadaVida(C: Coada): Boolean;
{adaugarea unui element in coada}
function IntroduceInCoada(var C: Coada; E: Pointer): Boolean;
{extragerea unui element din coada}
function ExtrageDinCoada(var C: Coada; var E: Pointer): Boolean;
{returneaza pointer spre elementului accesibil, fara eliminarea lui din
coada}
function ValoareVarfCoada(C: Coada; var E: Pointer): Boolean;
Implementation
function CreazaCoada(var C: Coada): Boolean;
begin
with C do
begin
Prim := 0;
Ultim := 0;
Lungime := 0;
CreazaCoada := True;
end;
end;
function ECoadaVida(C: Coada): Boolean;
begin
ECoadaVida := (C.Lungime=0);
end;
function IntroduceInCoada(var C: Coada; E: Pointer): Boolean;
begin
with C do
begin
165
If Lungime=MAX then IntroduceInCoada := False
else
begin
Elemente[Ultim] := E;
Ultim := (Ultim+1) mod MAX;
Lungime := Lungime+1;
IntroduceInCoada := True;
end;
end;
end;
function ExtrageDinCoada(var C: Coada; var E: Pointer): Boolean;
begin
with C do
begin
If ECoadaVida(C) then ExtrageDinCoada := False
else
begin
E := Elemente[Prim];
Prim := (Prim+1) mod MAX;
Lungime := Lungime-1;
ExtrageDinCoada := True;
end;
end;
end;
function ValoareVarfCoada(C: Coada; var E: Pointer): Boolean;
begin
with C do
begin
If ECoadaVida(C) then ValoareVarfCoada := False
else
begin
E := Elemente[Prim];
ValoareVarfCoada := True;
end;
end;
end;
end.
166
Programul Turbo Pascal Test_coada este un program ce poate fi utilizat pentru
testarea unit-ului UCoada.
{Testare unit UCoada}
program Test_coada;
uses UCoada, Crt;
type
{tipul elementelor listei}
PElement = ^Integer;
var
optiune: Integer;
C: Coada;
E: pointer;
element: PElement;
i: Integer;
begin
clrscr;
CreazaCoada(C);
repeat
Writeln('1 - Testeaza coada vida');
Writeln('2 - Da lungimea cozii');
Writeln('3 - Adauga');
Writeln('4 - Extrage');
Writeln('5 - Afiseaza elementul curent');
Writeln('6 - Afiseaza coada');
Writeln('7 - Afiseaza pozitiile curente');
Writeln('8 - Termina executia programului');
Read(optiune);
if optiune in [3] then
begin
new(element);
Readln(element^);
E := element;
end;
case optiune of
1: if ECoadaVida(C) then Writeln('Coada e vida!') else Writeln('Coada
nu e vida!');
2: writeln('Coada are ', C.Lungime, ' elemente');
167
3: If IntroduceInCoada(C, E) then writeln('OK!') else
writeln('Imposibil!');
4: if not ExtrageDinCoada(C, E) then writeln('Imposibil!')
else writeln(PElement(E)^);
5: if not ValoareVarfCoada(C, E) then writeln('Imposibil!')
else writeln(PElement(E)^);
6: for i:=0 to MAX do
begin
E := C.Elemente[i];
writeln(PElement(E)^);
end;
7: writeln('Prim: ', C.Prim, ' Ultim: ', C.Ultim);
end;
until optiune = 8;
end.
Arbori
În multe cazuri colecţiile între elementele cărora se stabilesc legături liniare (unu-
la-unu) nu sunt adecvate pentru modelarea problemelor ce trebuie rezolvate cu
calculatorul. Obiectele poate fi descompuse în altele mai simple, procesul de
descompunere putându-se realiza pe un număr finit de niveluri ierarhice. Orice
obiect este definit printr-un set de atribute şi prin mulţimea obiectelor componente.
Acest mod de descriere este recursiv, pentru că obiectele componente pot fi, la
rândul lor, descompuse. Se obţine astfel o colecţie de elemente organizate ierarhic,
arborescent, elemente între care se stabilesc legături de tipul unu-la-mai-multe.
Organizarea ierarhică intervine în toate domeniile: organigrama unei societăţi
comerciale, structura directoarelor pe discul unui calculator, organizarea hardware-
ului unui calculator, nomenclatorul meseriilor recunoscute în România, organizarea
unei universităţi pe facultăţi, secţii, ani de studiu etc.
Elementele unei structuri de tip arbore se numesc noduri sau vârfuri. Orice nod,
cu excepţia rădăcinii, are un nod predecesor unic (părinte) căruia îi este
subordonat. Orice nod poate avea mai multe noduri succesoare (fii) care îi sunt
subordonate. Toate nodurile subordonate direct aceluiaşi nod sunt fraţi. Arborele
este format din mulţimea nodurilor şi legăturile dintre acestea. Un nod al arborelui
poate fi (fig. 2.30):
rădăcină - nodul de pe primul nivel al arborelui, care nu are părinte;
nod intern - are atât părinte cât şi fii;
168
nod terminal (frunză) - nu are noduri subordonate.
Rădăcină a
b c noduri
interne
d e f g
h i j k l m
frunze
Fig. 2.22 Structură arborescentă
Rădăcina unui arbore este situată pe nivelul 1. Dacă un nod este situat pe nivelul i
al arborelui, descendenţii săi direcţi sunt situaţi pe nivelul i+1. Accesul de la
rădăcina arborelui la un nod situat pe nivelul i necesită parcurgerea a i-1 arce şi a i-
2 noduri intermediare. Lungimea căii (drumului) unui nod este dată de numărul
de ramificări de la rădăcină până la acel nod. Lungimea căii unui nod situat pe
nivelul i va fi i. Lungimea căilor interne ale unui arbore este dată de suma
lungimii căilor tuturor nodurilor interne ale arborelui. Lungimea căilor externe ale
unui arbore este dată de suma lungimii căilor tuturor nodurilor terminale ale
arborelui. Înălţimea (adâncimea) unui arbore este dată de nivelul maxim al
nodurilor sale.
Ordinul sau gradul unui nod este dat de numărul descendenţilor direcţi ai acelui
nod. Gradul maxim al unui arbore este dat de maximul gradelor nodurilor sale.
Nodurile terminale au gradul 0. O listă reprezintă, de fapt, un arbore degenerat, în
care toate nodurile au ordinul 1, cu excepţia nodului terminal, care are gradul 0.
Un arbore este fie vid, fie format dintr-un nod rădăcină care are ataşaţi un număr
finit de arbori, numiţi subarbori ai arborelui iniţial. Orice nod intern este rădăcina
unui subarbore. Doi subarbori ai aceluiaşi arbore pot fi fie disjuncţi (nu au noduri
comune), fie unul este subarbore al celuilalt.
169
Gradul nodurilor unui arbore multicăi (arbore generalizat) nu este limitat. Un
arbore generalizat este compus dintr-un nod rădăcină şi un număr oarecare de
subarbori generalizaţi.
Numărul maxim posibil de noduri pe care le poate conţine un arbore de grad d şi
înălţime h este:
1
0
h-
i
idd,hN (2.3)
În tabelul 2.1 sunt specificate nivelele şi gradele nodurilor arborelui din fig. 2.30,
precum şi înălţimile fiecăruia din subarborii săi.
Dacă un arbore are gradul maxim 2 şi se pot întotdeauna identifica subarborele
stâng şi drept al fiecărui nod, arborele este binar. Aşadar un arbore binar este fie
vid, fie compus dintr-un nod rădăcină şi doi subarbori binari, stâng şi drept.
Pentru un arbore binar de înălţime h numărul de noduri poate fi cuprins între:
122 h-,hNh (2.4)
Numărul minim de noduri se obţine pentru arborii degeneraţi de tip listă, care au
câte un singur subarbore, stâng sau drept.
Înălţimea unui arbore binar cu N noduri poate varia între:
NhN 2log (2.5)
Nod Nivel Grad Înălţime subarbore
a 1 2 4
b 2 3 3
c 2 1 3
d 3 3 2
e 3 1 2
170
Nod Nivel Grad Înălţime subarbore
f 3 0 1
g 3 2 2
h 4 0 1
i 4 0 1
j 4 0 1
k 4 0 1
l 4 0 1
m 4 0 1
Tab. 2.2 Caracteristicile arborelui din fig. 2.22
Orice arbore multicăi poate fi transformat în arbore binar echivalent, dacă orice nod
este considerat direct legat la cel mult două noduri: primul fiu (la stânga) şi
următorul frate (la dreapta). Arborele din fig. 2.30 poate fi transformat în arborele
binar echivalent din fig. 2.31.
Un arbore este echilibrat dacă diferenţa dintre înălţimile subarborilor săi este cel
mult 1. Arborii binari echilibraţi se mai numesc şi arbori AVL (Adelson-Velsky şi
Landis). Arborii ordonaţi sunt arbori pentru care ramificările în fiecare nod sunt
ordonate, după valorile unei chei, reprezentată de un câmp din informaţia utilă a
nodurilor.
a
b
d c
h e g
i k f l
171
j m
Fig. 2.23 Arborele binar echivalent arborelui din fig. 2.22
Traversarea arborilor
Traversarea unui arbore presupune vizitarea (inspectarea) tuturor nodurilor sale, o
singură dată, într-o anumită ordine, cu scopul efectuării unor operaţii asupra
informaţiei utile din noduri. Ordinea vizitării, pentru un nod oarecare, stabileşte
succesiunea în care vor fi parcurse acel nod şi nodurile subarborilor pentru care
nodul este rădăcină. Ordinea de parcurgere a nodurilor este, de obicei, impusă de
specificul aplicaţiei (prelucrarea realizată asupra informaţiei utile din noduri).
În toate cazurile, ordinea relativă de prelucrare a nodurilor terminale este, prin
convenţie, de la stânga la dreapta. Există două moduri de parcurgere a nodurilor
unui arbore:
în lăţime (lărgime) - vizitarea nodurilor se face pe nivele ierarhice;
în adâncime - ordinea de vizitare a nodurilor reflectă relaţiile de
subordonare între acestea.
În cazul arborelui din fig. 2.30, traversarea în lăţime presupune vizitarea nodurilor
în ordinea a, b, c, d, e, f, g, h, i, j, k, l, m. Pentru implementarea traversării în lăţime
se poate utiliza o structură de tip coadă, iniţializată cu nodul rădăcină. Cât timp
coada nu devine vidă, se repetă următoarele operaţii:
se extrage şi se prelucrează nodul curent din coadă;
fii săi sunt adăugaţi în coadă.
Utilizând operaţiile tipului abstract de date Coada, algoritmul de traversare a unui
arbore în lăţime poate fi descris astfel:
ALGORITMUL TraversareÎnLăţime ESTE:
CreazăCoadă(C);
IntroduceÎnCoadă(C, Rădăcina);
CÎTTIMP not ECoadaVidă(C) EXECUTĂ
ExtrageDinCoadă(C, Nod);
Prelucrează(Nod);
CÂTTIMP (Nod are fii) EXECUTĂ
IntroduceÎnCoadă(C, Fiu);
SFCÂTTIMP
SFCÂTTIMP
SFALGORITM
172
În cazul traversării în adâncime sunt posibile două alternative, în funcţie de
ordinea de prelucrare a nodului rădăcină şi a subarborilor:
în preordine - nodul rădăcină este prelucrat înaintea subarborilor;
în postordine - nodul rădăcină este prelucrat după prelucrarea
subarborilor.
În cazul arborelui din fig. 2.30, la traversarea în preordine nodurile vor fi vizitate în
ordinea a, b, d, h, i, j, e, k, f, c, g, l, m. La traversarea în postordine ordinea de
vizitarea a nodurilor va fi h, i, j, d, k, e, f, b, l, m, g, c, a. Se poate observa că la
traversarea în preordine ierarhia este parcursă “descendent”, iar la traversarea în
postordine ierarhia este parcursă “ascendent”.
În cazul arborilor binari traversarea în adâncime se poate face în trei moduri:
în preordine - rădăcină, subarbore stâng, subarbore drept (RSD);
în inordine - subarbore stâng, rădăcină, subarbore drept (SRD);
în postordine - subarbore stâng, subarbore drept, rădăcină (SDR).
În cazul arborilor generalizaţi traversarea în inordine nu poate fi definită, pentru că
momentul prelucrării rădăcinii este incert.
Algoritmii de traversare în adâncime a unui arbore binar pot fi definiţi recursiv:
SUBALGORITMUL TraversareÎnPreordine (Arbore) ESTE:
* Prelucrare Rădăcină.
CHEAMĂ TraversareÎnPreordine(SubarboreStâng);
CHEAMĂ TraversareÎnPreordine(SubarboreDrept);
SFSUBALGORITM
SUBALGORITMUL TraversareÎnInordine (Arbore) ESTE:
CHEAMĂ TraversareÎnInordine(SubarboreStâng);
* Prelucrare Rădăcină.
CHEAMĂ TraversareÎnInordine(SubarboreDrept);
SFSUBALGORITM
SUBALGORITMUL TraversareÎnPostordine (Arbore) ESTE:
CHEAMĂ TraversareÎnPostordine(SubarboreStâng);
CHEAMĂ TraversareÎnPostordine(SubarboreDrept);
* Prelucrare Rădăcină.
SFSUBALGORITM
173
Tipul de date ArboreBinar
În continuare este prezentată o structură de tip arbore binar. Operaţiile
fundamentale specificate sunt operaţii ce modifică arborele, operaţii ce furnizează
informaţii despre arbore, şi operaţii de parcurgere a arborelui.
Operaţiile ce modifică arborele sunt:
IniţializeazăArbore - construieşte arborele vid;
CreazăArbore - construieşte un arbore pe baza elementelor caracteristice
date (informaţie utilă rădăcină, subarbore stâng, subarbore drept);
ModificăInfRădăcină, ModificăStâng, ModificăDrept - modifică
elementele caracteristice ale arborelui (respectiv informaţia utilă din
rădăcină, subarborele stâng, subarborele drept);
DistrugeRădăcină - elimină din memorie rădăcina arborelui.
S-au specificat următoarele operaţii ce furnizează informaţii despre arbore:
EArboreVid - testează dacă arborele este vid;
DăInfRădăcină, DăStâng, DăDrept - furnizează adresele elementelor
arborelui (informaţie utilă rădăcină, subarbore stâng, subarbore drept),
preluate din rădăcina arborelui;
Înălţime - dă înălţimea arborelui;
NumărNoduri - dă numărul de noduri ale arborelui.
S-au specificat cele trei operaţii posibile la parcurgerea arborelui în adâncime:
ÎnPreordine - traversare în preordine;
ÎnInordine - traversare în inordine;
ÎnPostordine - traversare în postordine.
Adăugarea sau eliminarea de noduri se poate realiza utilizându-se operaţiile
specificate.
Unit-ul UArbBin implementează structura ArboreBinar. Prelucrarea ce se aplică
informaţiei din noduri este generică, specificată prin variabila Prel, de tip
procedure. Ea este precizată la nivelul aplicaţiei.
{
Implementare a TAD-ului ArboreBinar.
Arborele poate avea orice tip de elemente.
174
}
Unit UArbBin;
Interface
type
{tip arbore}
arbore = ^nod;
nod = record
Element: pointer;
Stang, Drept: arbore;
end;
{tip prelucrare}
Prelucrare = procedure(p: pointer);
{Construieste arborele vid}
function InitializeazaArbore(var R: arbore): Boolean;
{Construieste un arbore}
function CreazaArbore(E: pointer; S, D: pointer; var R: arbore): Boolean;
{testeaza arborele vid}
function EArboreVid(R: arbore): Boolean;
{da adresa informatiei utile din radacina}
function DaInfRadacina(R: arbore; var E: pointer): Boolean;
{da adresa arborelui stang}
function DaStang(R: arbore; var S: arbore): Boolean;
{da adresa arborelui drept}
function DaDrept(R: arbore; var D: arbore): Boolean;
{modifica informatia utila din radacina}
function ModificaInfRadacina(R: arbore; E: pointer): Boolean;
{modifica arborele stang}
function ModificaStang(R: arbore; S: arbore): Boolean;
{modifica arborele drept}
function ModificaDrept(R: arbore; D: arbore): Boolean;
{elimina radacina}
function DistrugeRadacina(var R, S, D: arbore; var E: pointer): Boolean;
{da inaltimea arborelui}
function Inaltime(A: arbore): integer;
{da numarul nodurilor}
function NumarNoduri(A: arbore): integer;
{parcurge in preordine}
procedure InPreordine(A: arbore; Prel: Prelucrare);
{parcurge in inordine}
175
procedure InInordine(A: arbore; Prel: Prelucrare);
{parcurge in postordine}
procedure InPostordine(A: arbore; Prel: Prelucrare);
Implementation
function InitializeazaArbore(var R: arbore): Boolean;
begin
R := nil;
InitializeazaArbore := True;
end;
function CreazaArbore(E: pointer; S, D: pointer; var R: arbore): Boolean;
begin
if MaxAvail < SizeOf(nod) then
CreazaArbore := False
else
begin
new(R);
with R^ do
begin
Element := E;
Stang := S;
Drept := D;
end;
CreazaArbore := True;
end;
end;
function EArboreVid(R: arbore): Boolean;
begin
EArboreVid := (R=nil);
end;
function DaInfRadacina(R: arbore; var E: pointer): Boolean;
begin
if R<>nil then E := R^.Element
else E := nil;
DaInfRadacina := (E<>nil);
end;
function DaStang(R: arbore; var S: arbore): Boolean;
begin
176
if R<>nil then S := R^.Stang
else S := nil;
DaStang := (S<>nil);
end;
function DaDrept(R: arbore; var D: arbore): Boolean;
begin
if R<>nil then D := R^.Drept
else D := nil;
DaDrept := (D<>nil);
end;
function ModificaInfRadacina(R: arbore; E: pointer): Boolean;
begin
if R<>nil then R^.Element := E;
ModificaInfRadacina := (R<>nil);
end;
function ModificaStang(R: arbore; S: arbore): Boolean;
begin
if R<>nil then R^.Stang := S;
ModificaStang := (R<>nil);
end;
function ModificaDrept(R: arbore; D: arbore): Boolean;
begin
if R<>nil then R^.Drept := D;
ModificaDrept := (R<>nil);
end;
function DistrugeRadacina(var R, S, D: arbore; var E: pointer): Boolean;
begin
if R=nil then DistrugeRadacina := False
else
begin
with R^ do
begin
S := Stang;
D := Drept;
E := Element;
end;
dispose(R);
DistrugeRadacina := True;
177
end;
end;
function Inaltime(A: arbore): integer;
var
IStang, IDrept :Integer;
begin
if EArboreVid(A) then Inaltime := 0
else
begin
IStang := Inaltime(A^.Stang);
IDrept := Inaltime(A^.Drept);
if IStang>IDrept then
Inaltime := IStang+1
else
Inaltime := IDrept+1
end;
end;
function NumarNoduri(A: arbore): integer;
begin
if EArboreVid(A) then NumarNoduri := 0
else
NumarNoduri := 1+NumarNoduri(A^.Stang)+NumarNoduri(A^.Drept);
end;
procedure InPreordine(A: arbore; Prel: Prelucrare);
var
E: pointer;
arb: arbore;
begin
if DaInfRadacina(A,E) then Prel(E);
if DaStang(A, arb) then InPreordine(arb, Prel);
if DaDrept(A, arb) then InPreordine(arb, Prel);
end;
procedure InInordine(A: arbore; Prel: Prelucrare);
var
E: pointer;
arb: arbore;
begin
if DaStang(A, arb) then InInordine(arb, Prel);
if DaInfRadacina(A,E) then Prel(E);
178
if DaDrept(A, arb) then InInordine(arb, Prel);
end;
procedure InPostordine(A: arbore; Prel: Prelucrare);
var
E: pointer;
arb: arbore;
begin
if DaStang(A, arb) then InPostordine(arb, Prel);
if DaDrept(A, arb) then InPostordine(arb, Prel);
if DaInfRadacina(A,E) then Prel(E);
end;
end.
Un exemplu de utilizare a unit-ului UArbBin îl constituie programul ArbBin.
Programul construieşte un arbore binar total echilibrat de înălţime 3. Informaţia
utilă din noduri reprezintă pointeri la întregi. În fiecare nod se reţine numărul de
ordine al nodului. După construirea arborelui, se afişează înălţimea sa şi numărul
de noduri pe care le conţine. Arborele este apoi traversat în trei moduri (preordine,
inordine, postordine), prelucrarea ce se efectuează în fiecare caz fiind afişarea
informaţiei utile din nodurile parcurse (procedura Tiparire).
Utilizarea directivei de compilare {$F+} este obligatorie atunci când se utilizează
variabile de tip procedure sau function. Compilatorul este astfel forţat să utilizeze
modelul de apel FAR.
{Testare unit UArbBin}
program ArbBin;
{compilatorul foloseste modelul de apel FAR}
{$F+}
uses UArbBin, Crt;
type
PElement = ^Integer;
var
Element: PElement;
arb, nou, radacina: arbore;
179
procedure Tiparire(E: pointer);
begin
write(PElement(E)^:4);
end;
begin
clrscr;
InitializeazaArbore(Radacina);
{construire arbore}
New(Element);
Element^ := 1;
CreazaArbore(Element, nil, nil, Radacina);
New(Element);
Element^ := 2;
CreazaArbore(Element, nil, nil, nou);
ModificaStang(Radacina, nou);
New(Element);
Element^ := 3;
CreazaArbore(Element, nil, nil, nou);
ModificaDrept(Radacina, nou);
New(Element);
Element^ := 4;
CreazaArbore(Element, nil, nil, nou);
DaStang(Radacina, arb);
ModificaStang(arb, nou);
New(Element);
Element^ := 5;
CreazaArbore(Element, nil, nil, nou);
DaStang(Radacina, arb);
ModificaDrept(arb, nou);
New(Element);
Element^ := 6;
CreazaArbore(Element, nil, nil, nou);
DaDrept(Radacina, arb);
ModificaStang(arb, nou);
New(Element);
180
Element^ := 7;
CreazaArbore(Element, nil, nil, nou);
DaDrept(Radacina, arb);
ModificaDrept(arb, nou);
{informatii despre arbore}
Writeln('Inaltime: ', Inaltime(Radacina));
Writeln('NumarNoduri: ', NumarNoduri(Radacina));
{parcurgeri arbore}
Writeln('Preordine');
InPreordine(Radacina, Tiparire);
Writeln;
Writeln('Inordine');
InInordine(Radacina, Tiparire);
Writeln;
Writeln('Postordine');
InPostordine(Radacina, Tiparire);
readln;
end.
181