Notiuni introductive privind organizarea datelor. Limbajul algoritmic

Notiuni introductive privind organizarea datelor. Limbajul algoritmic

1. Structuri elementare de date

Organizarea datelor, in vederea prelucrarii acestora, este un proces complex, dar de o deosebita importanta. De modul in care sunt structurate datele, depinde eficienta algoritmilor de prelucrare. Unele date sunt de tip simplu: data apare ca o entitate indivizibila atat din punct de vedere a informatiei pe care o reprezinta cat si in raport cu unitatea centrala de prelucrare. Alte date sunt descrise prin componente, cu acelasi tip sau cu tipuri diferite. O colectie de date pe care s-a evidentiat un anumit mod de structurare si s-au stabilit procedeele de inregistrare/identificare a componentelor se va numi structura de date. Componentele unei structuri de date pot fi de tip elementar sau pot fi, la randul lor, structuri. Identificarea unei componente se poate face prin pozitia pe care o ocupa in structura sau prin nume.

Pentru o data elementara trebuie specificate: un identificator, atribute (domeniul de valori, modul de reprezentare in sistemul de calcul, precizia reprezentarii) si valorile datei (pot fi enumerate sau indicate printr-o proprietate comuna). Din punct de vedere al domeniului de valori asociat unei date se disting urmatoarele clase:

date de tip integer (numere intregi),

date de tip real sau float (cu elemente din multimea numerelor rationale);

date de tip boolean (se refera la valorile de adevar true (adevarat), false (fals));

date de tip char (cu elemente ale multimilor ASCII sau Unicode);

date de tip string (obtinute prin concatenarea datelor de tip caracter);

date de tip array (structura cu componente de acelasi tip ce ocupa locatii succesive din memoria sistemului de calcul, identificate prin pozitie);

date de tip record (structura cu componente diverse, identificate prin nume).

Un mod special de organizare a datelor este intalnit cand avem de prelucrat liste. O lista liniara este o structura de date omogena, secventiala, formata din elemente apartinand unei multimi date. O lista poate fi vida (nu are nici un element) sau plina (nu mai exista spatiu pentru stocarea unor componente suplimentare). Este foarte important sa putem accesa un element al listei, sa inseram sau sa stergem un element etc.

Listele pot fi stocate in memoria unui sistem de calcul in doua moduri: secvential si inlantuit. Modul secvential presupune stocarea elementelor listei in locatii succesive de memorie conform ordinii elementelor din lista si retinerea adresei primului element al listei (adresa de baza). Modul inlantuit presupune ca fiecare element al listei este inlocuit cu o celula formata dintr-o parte de informatie (corespunzatoare elementului listei) si o parte de legatura ce contine adresa celulei urmatorului element din lista. Se va retine adresa de baza a listei, iar ultima celula va indica, in partea de legatura, o valoare speciala (ce nu poate desemna o legatura).

Structura de date elementara adecvata reprezentarii secventiale a listelor este tabloul unidimensional.

Orice lista liniara are un inceput si un sfarsit pe care le numim baza, respectiv varf. O lista liniara la care inserarea si extragerea elementelor se face prin varful listei se numeste stiva (stack). O lista liniara in care inserarile se efectueaza la baza listei, iar extragerile prin varful listei se numeste coada queue

Listele liniare pot fi transformate in liste circulare considerand ca legatura ultimului element indica adresa bazei listei.

Exemple:

Numerele 1234 si -423 sunt valori de tip intreg. Numerele 12.354 si 0.123E+2 sunt numere reale (primul este specificat in notatia clasica, iar al doilea in notatia stiintifica si reprezinta numarul 12.3). 'Bazele Informaticii' este un sir de caractere.

Multimea sirurilor x cu 10 numere intregi poate fi descrisa prin array x(10), iar multimea tabelelor (matricelor) y cu 7 linii si 5 coloane este descrisa prin array y(7,5).

O modalitate de reprezentare a grafurilor (resp. digrafurilor) presupune cunoscute: n - numarul de varfuri (numerotate 1, 2, , n) si o matrice patratica E de ordin (dimensiune) n, numita matricea de adiacenta a grafului (resp. digrafului), construita conform regulei: "Daca [i,jI (respectiv, (i,j)) este o muchie a grafului (resp. un arc al digrafului) atunci E(i,j)=E(j,i)=1 (resp. E(i,j)=1), altfel E(i,j) = E(j,i) = 0 (resp. E(i,j)=0)". Fie tabloul de adiacenta:

Reprezentati grafic obiectul desemnat.

O alta modalitate de reprezentare a grafurilor (digrafurilor), in locul matricei de adiacenta, utilizeaza liste. Pentru fiecare varf i (de la 1 la n) , Li specifica (intr-o anumita ordine) vecinii varfului i:

L1: 2, 3, 5; L2: 1, 3, 4, 5;

L3: 1, 2, 4; L4: 2, 3;

L5: 1, 2.

Datele privind evidenta personalului unei firme sunt stocate in inregistrari. O inregistrare poate contine diverse campuri precum: Cod, Nume Prenume, Adresa, Colectiv, etc.

2. Limbaj algoritmic

Am vazut ca algoritmii pot fi reprezentati in 'limbaj natural' sau cu ajutorul schemelor logice. O alta modalitate de reprezentare a algoritmilor o constituie utilizarea limbajului algoritmic. Limbajul algoritmic foloseste o scriere similara limbajelor de programare moderne. El permite atat descrierea instructiunilor algoritmului cat si descrierea exacta a tipului datelor cu care lucreaza algoritmul. Un algoritm descris folosind limbajul algoritmic este o succesiune finita de declarari si instructiuni. Declararile precizeaza tipul si organizarea datelor. Ele apar inaintea instructiunilor ce descriu pasii algoritmului. Din punct de vedere al scrierii instructiunilor, o instructiune poate ocupa mai multe randuri sau pe un rand pot fi scrise mai multe instructiuni. Instructiunile vor fi separate, intre ele, folosind caracterul

Cuvintele care identifica un tip de date sau o instructiune, numite in continuare cuvinte cheie, apar evidentiate pentru a fi deosebite de numele variabilelor.

O declarare utilizeaza unul dintre cuvintele cheie integer, real, boolean, char, string, array, record, stack, queue, urmat de o lista de nume de variabile. Declararile sunt separate intre ele folosind caracterul . Variabilele prezente intr-o lista au tipul si organizarea precizata prin cuvantul cheie respectiv. De exemplu, declararile:

integer array a(10);

record (integer cod; string nume; real media) x, y;

stack S; queue Q; char ch; boolean ind;

indica faptul ca a este un tablou cu maxim 10 elemente intregi; x si y sunt inregistrari (cu trei componente: cod - o valoare intreaga, nume - un sir de caractere, media - un numar real), S este o stiva, Q este o coada, ch este un caracter, iar ind este o variabila logica.

O importanta deosebita o au declararile de subprograme. In rezolvarea multor probleme apare necesitatea executarii repetate a acelorasi calcule pentru date diferite. Subprogramele permit descrierea acestor calcule o singura data. Subprogramul poate fi apelat ori de cate ori este necesara efectuarea acestor operatii. Un subprogram este identificat printr-un nume si o lista de parametri. Subprogramele se impart in proceduri si functii. Delararea unei proceduri consta in specificarea cuvantului procedure, a unui identificator al procedurii si a unei liste de declarari (intre paranteze rotunde) ce indica informatiile ce fac obiectul transferului intre apelant si apelat. Pentru declararea unei functii se foloseste cuvantul cheie function Spre deosebire de proceduri, functiile intorc obligatoriu un rezultat. De aceea, in declaratii, declararea unei functii incepe cu specificarea multimii de valori ce corespunde rezultatului, a cuvantului function, a identificatorului functiei si a listei parametrilor (similar ca la o procedura).

Un algoritm este complet cunoscut daca este descrisa si definitia subprogramelor folosite. Definitia unui subprogram presupune descrierea (prin instructiuni) modului in care se efectueaza calculele si se transmit rezultatele. Mai multe detalii prezentam in finalul acestei sectiuni.

Instructiunile limbajului algoritmic sunt urmatoarele:

a) Instructiunea de atribuire. Aceasta instructiune are forma: v := E (atribuire simpla) sau (v1 v2 vn E1 E2 En) ce realizeaza simultan atribuirile vi :=Ei, pentru oricare i = 1, 2, , n. Operatia de atribuire este permisa cand variabila v (variabilele v1 v2 vn) din membru stang si expresia E (expresiile E1 E2 En) sunt compatibile (se refera la aceeasi clasa de obiecte). O expresie contine paranteze (optional), operanzi (inclusiv apeluri de functii) si operatori adecvati.

b) Instructiuni de intrare/iesire. Vom presupune ca citirea datelor (de intrare) se face de la un mediu de intrare (de exemplu: tastatura sistemului de calcul), iar scrierea rezultatelor (de iesire) se face la un mediu de iesire (de exemplu: ecranul, imprimanta, plotterul etc.). Forma instructiunilor de intrare/iesire este:

read v1, v2, , vn

write v1, v2, , vn

unde v1 v2 vn sunt variabile de tip elementar.

c) Instructiunea repetitiva While. Aceasta instructiune are forma: while p do S, unde p este un predicat, iar S este o secventa de instructiuni. Deoarece instructiunile sunt separate intre ele, folosind ';' va trebui sa delimitam secventa S. Pentru aceasta se utilizeaza constructia SEQ..END prezentata mai sus. Semnificatia acestei instructiuni este aceeasi ca pentru sub-schema logica While(p,S).

d) Instructiunea If_then else. Aceasta instructiune are forma: if p then S1 else S2 unde p este un predicat, iar S1 si S2 sunt secvente de instructiuni. Daca neindeplinirea predicatului p nu indica vreo actiune, portiunea else S2 poate lipsi, fapt reprezentat prin includerea intre paranteze drepte, exprimarea fiind echivalenta cu IF0(p, S1). Atunci cand, atat S1 cat si S2 sunt actiuni prevazute, instructiunea este echivalenta cu sub-schema logica IF(p, S1, S2).

d) Instructiunile insert si extract. Aceste instructiuni sunt necesare pentru lucrul cu liste. Acestea sunt o prelungire a instructiunii de atribuire. Daca se specifica o lista L atunci insert i, L (sau L:=i) exprima introducerea elementului specificat prin i in lista  L, iar instructiunea extract i, L (sau i:=L) specifica extragerea elementului curent din lista L si depunerea acestuia in i.

e) Instructiunea apel de procedura. Apelarea unei proceduri se face prin instructiunea apel de procedura care are una din formele:

identificator procedura

sau

identificator procedura(lista de argumente)

unde identificator procedura specifica o procedura declarata, iar argumentele sunt expresii separate prin virgula.

Atunci cand se ajunge la un apel de procedura se stabileste corespondenta intre argumente si parametri, si se executa toate instructiunile specificate in definitia procedurii. Dupa ultima instructiune a procedurii se continua cu instructiunea urmatoare apelului de procedura. Un apel de procedura este corect atunci cand intre argumente si parametri exista o concordanta ca numar, tip si mod de organizare. Prin conventie, atunci cand referim o variabila (intr-o procedura) de fapt, facem o referire la locatia de memorie corespunzatoare argumentului respectiv. Spunem ca se realizeaza un transfer prin referinta. Sunt posibile si alte moduri de transfer, dar acestea nu sunt considerate momentan.

f) Instructiunea return. Aceasta instructiune provoaca parasirea corpului unui subprogram. In cazul in care cuvantul return este urmat de o expresie, valoarea expresiei este folosita ca valoare de retur a subprogramului. Instructiunea return fara valoare de retur este folosita pentru a parasi executia unei proceduri si a reveni in unitatea de program din care a avut loc apelul; si anume la instructiunea ce urmeaza imediat acestui apel.

g) Pentru a usura descrierea algoritmilor admitem prezenta, ca instructiuni ale limbajului algoritmic, a instructiunilor Repeat si For Instructiunea Repeat este modelata de structura repetitiva REPEAT (a, S). Ea are forma:

Repeat S until a

unde S este o secventa (eventual vida) de instructiuni, iar a modeleaza o expresie logica.

Instructiunea For este modelata de structura iterativa FOR(a; a,b,c) si are forma simplificata

For v := e1, e2, e3 do S

unde: S este o secventa de instructiuni, iar expresiile e1, e2 si e3 au acelasi domeniu de valori ca variabila v. In forma prezentata, instructiunea determina executarea secventei S pentru v luand succesiv valorile e1, e1+e3, e1+2e3, , fara a trece dincolo de e2. Formei de mai sus ii corespunde structura iterativa:

FOR((v-v2)*v3 £ 0; SEQ v:= e1; v1 :=e2; v3:=e3 END, S, v := v +v3).

Exemplul 3.4.1. Fie N un numar natural, N<10000. Sa se determine toate numerele prime x, x £ N.

Metoda de rezolvare utilizata este atribuita lui Eratostene (275-195 i.e.n). Algoritmul utilizeaza, ca structura de date, un tablou cu elemente de tip boolean. In final se obtine a[iI = true daca i este numar prim, respectiv a[iI = false daca i nu este numar prim. Prin int(x) notam partea intreaga a numarului x

boolean array a(10000);

integer i,j,n;

SEQ

read N;

a[1I := false;

for i := 2, N, 1 do a[iI := true;

for i := 2, int(n/2), 1 do

for j := 2, int(n/i), 1 do a[i*jI := false;

for i:= 1, n, 1 do if a[iI then write i;

END

Exemplul 3.4.2. (Operatii de manipulare a stivelor). Fie N numarul maxim de elemente ale stivei S (cand lista este plina) si ps indicele (adresa) ultimului element din stiva (varful stivei). S[psI desemneaza varful stivei, iar S[1I este primul element al stivei. Convenim asupra existentei a doua variabile logice identificate prin plin (indica posibilitatea introducerii in stiva) si gol (care indica daca stiva este vida sau nu). Introducerea, respectiv extragerea unui element t in (respectiv din) stiva S se poate realiza conform urmatoarelor proceduri:

procedure insert(S,N,ps,t)

integer N, ps;

Tip element array S(N);

Tip element t;

SEQ

if ps < N then SEQ

ps:=ps+1;

S[psI := t;

return

END

else SEQ

write "Stiva plina";

plin := true;

return

END

END

procedure extract(S, N,ps,t)

integer N, ps;

Tip element array S(N);

Tip element t;

SEQ

if ps > 0 then SEQ

t := S[psI;

ps := ps-1;

return

END

else SEQ

write "Stiva goala";

gol := true;

return

END

END

Exemplul 3.4.3. (Operatii de manipulare a cozilor). Fie N-1 capacitatea de stocare a cozii C. Presupunem ca elementele cozii sunt memorate intr-un tablou unidimensional cu celulele: C[1I, C[2I, , C[NI si ca dupa celula C[NI urmeaza elementul C[1I. Notam cu p+1 indicele primului element din coada (urmatorul de prelucrat) si cu u indicele ultimului element prezent in coada. Coada este vida (goala) daca p = u. Introducerea unui element in coada revine la marirea indicelui u cu o unitate, iar eliminarea unui element din coada se reduce la marirea lui p cu o unitate. Vom considera coada plina atunci cand u+1 = p mod (N). Convenim ca initializarea cozii vide se va face prin instructiunile: p:=n; u:=n; gol:=true; plin:=false; Introducerea unui element in coada (insert) este descrise prin urmatoarea procedura:

procedure insert (C, N, p, u, t)

queue C;

integer N, p, u;

Tip element t;

SEQ

if u < N then u:=u+1

else u:=1;

if u = p then

SEQ

write "Coada plina";

plin:=true;

return

END;

C[uI:=t;

return

END

Eliminarea (extract) din coada este realizata folosind urmatoarea procedura:

procedure extract(C, N, p, u, t)

queue C;

integer N, p, u;

Tip element t;

SEQ

if p = u then

SEQ

write "Coada goala";

gol:=true;

return

END;

if p=n then p:=1 else p:=p+1;

t:=C[pI

END

Algoritmii de manipulare a listelor de tip stack si queue implementate inlantuit vor fi prezentati in cadrul unei lec?ii viitoare).

Exemplul 3.4.4. (Parcurgerea "breath first" a grafurilor). O metoda de vizitare a varfurilor unui graf cu n varfuri, pornind de la un varf dat x, consta in parcurgerea "in latime" - breath first - a grafului: se viziteaza varful x, apoi vecinii acestuia, apoi vecinii inca nevizitati ai acestora etc. Mai precis, metoda utilizeaza matricea de adiacenta E, o lista Q de tip queue (coada) si un tablou V cu n componente logice, astfel: Initial in coada se depune varful x. Apoi, cat timp coada este nevida, se extrage un varf din coada, se viziteaza acest varf si se introduc in coada vecinii sai care n-au fost introdusi anterior in coada. Pentru varfurile i introduse in coada avem V[iI=true.

Boolean array v(10);

integer array E(10,10);

integer i, j, n, x;

queue Q;

SEQ

read n;

for i := 1, n, 1 do v[iI := false;

read x;

read E;

insert x, Q;

v[xI := true;

while not empty(Q) do

SEQ

extract i, Q;

viziteaza i;

for j := 1, n, 1 do

if E[i,jI= then

if not v[jI then

SEQ

insert j, Q;

v[jI := true;

END

END

END

In descrierea de mai sus, empty(Q) furnizeaza valoarea logica TRUE cand lista Q este vida si FALSE, in caz contrar. Constructia "viziteaza i;" se poate reduce la afisarea varfului i

Exemplul 3.4.5. (Parcurgerea "depth first" a grafurilor). O alta metoda de vizitare a varfurilor unui graf cu n varfuri, pornind din varful x, numita parcurgere "in adancime" - depth first - foloseste:

un tablou V cu n componente booleene (V[iI = false pentru varfurile i nevizitate, V[iI = true pentru varfurile vizitate);

o lista de tip stack (ce va contine varfurile ce apar pe drum ce leaga varful x de varful curent);

un subprogram function numit NEXT care pentru un varf i indica primul din vecinii lui i la care nu s-a ajuns intr-o analiza anterioara a lui i, respectiv intoarce valoarea 0 daca nu mai exista un astfel de vecin.

Algoritmul de parcurgere este descris prin urmatoarea procedura:

procedure vizitare DF(x,n)

integer x,n; boolean array v(n);  stack S;

integer i; boolean fin;

SEQ

for i := 1, n, 1 do v[iI := false;

insert x, S; viziteaza x; i:=x; fin:=false;

repeat

j:=NEXT(i);

if j = 0   then if empty(S) then fin:=true

else extract i,S

else if not v(j) then

SEQ

viziteaza j;

v[jI:=true;

insert j, S;

i := j;

END

until fin;

return

END

Pentru cazuri particulare ale grafurilor (arbori) vom intalni specializari ale parcurgeri in adancime in lectiile urmatoare.