STRUCTURI DE DATE in programare

6. STRUCTURI DE DATE
Structurile de date, spre deosebire de cele simple, sunt combinaţii de alte tipuri, definite prin descrierea tipurilor componentelor şi prin indicarea unor metode de structurare. Componentele tipurilor structurate pot fi elementare sau structurate.

6.1. Tablouri unidimensionale
În multe probleme apare necesitatea de a lucra cu grupuri de variabile de acelaşi tip. De exempu, pentru a memora notele studentului de la sesiunea de iarnă avem nevoie de un grup de numere naturale, iar pentru a memora temperaturile zilnice ale lunii noiemrie avem nevoie de un grup de numere întregi. Un grup de elemente de acelaşi tip se mai numeşte şi tablou unidimensional sau vector. Vectorul reprezintă un tip de date structurat.
Să alcătuim algoritmul rezolvării următoarei probleme: să se calculeze suma a 5 numere întregi.
Rezolvare: Vom declara 5 variabile de tip integer pentru a memora valorile celor 5 numer întregi.
Algoritm suma
Var
N1: integer
N2: integer
N3: integer
N4: integer
N5: integer
S : integer
Begin
Readint(n1)
Readint(n2)
Readint(n3)
Readint(n4)
Readint(n5)
S:=n1+n2+n3+n4+n5
Writeint(s)
End.
Să calculăm suma a 30 numere întregi. Dacă rezolvăm problema în mod analog, atunci avem nevoie de 30 variabile pentru păstrarea celor 30 numere şi algoritmul ar fi mult mai lung. Ar fi mai bine ca cele 30 de variabile să nu le declarăm separate, dar să declarăm un grup format din 30 elemente.
Tipul tablou unidimensional (vector) se declară în felul următor:
Type
< Nume_tip> = array of ,
unde
tip indece poate fi de orice tip scalar,
iar tip element – de orice tip de date.
Exemple:
Type
vector = array[1..20] of integer ar însemna un grup de elemente numere înteregi, numerotate de la 1 la 20.
Dacă am declara o variabilă de acest tip:
Var
X: vector
Pentru a accesa elementul cu numărul 7 vom specifica X[7], deci componenta de ordin I se va specifica prin X[I].
Pentru a referi un element al vectorului se foloseşte următoarea specificare
< Nume_variabila> [ ]
Se pot defini şi vectori cu elementele numerotate, de pildă, de la –5 la 5:
Type
vector1=array[-5 ..5] of integer
Var
X1:vector
În acest caz vectorul va avea 10 elemente, numerotate astfel:
[-5][-4][-3][-2][-1][0][ 1][ 2][ 3][ 4][ 5]
Primul element al acestui vector poate fi accesat astfel X1[-5], al 6-lea –X1[0]
Fie date următoarele declaraţii:
Type
Lucratori=(Ivanov,Petrov,Sidorov)
Vector2 = array[lucratori] of real
Var
Salar : vector2
Vectorul Salar are 3 elemente. Specificarea Salar[Ivanov] ar referi primul element, Salar[Petrov] – al 2-lea, iar Salar[Sidorov] – al 3-lea.

Type
Vector=array[‘a’ ..’z’] of real ar însemna un şir de numere reale, “numerotate” de la ‘a’ la ‘z’
Pentru vectorul
Var
X: vector
Componenta a 3-ia ar fi referită astfel X[‘c’]
Am putea defini chiar:
Type
Vector=array[char] of integer ceea ce ar însemna un grup de elemente numere întregi, numerotate de la caracterul cu codul ASCII 0 pănă la caracterul cu codul ASCII 255, care este ultimul.
Putem folosi şi tipul Boolean pentru a defini vectori, de exemplu:
Type
Vector=array[Boolean] of integer
Var
Y:vector
Vectorul Y are 2 elemente. Primul poate fi referit Y[false], iar ultimul –Y[true].
O variabilă de tip vector nu poate fi nici citită nici scrisă în întregime. De obicei se lucrează cu componentele vectorului. Cu componentele vectorului se pot face toate operaţiile ce se pot face cu orice variabilă de acel tip ( afişare, citire, atribuire etc.)

6.1.1. Prelucrarea secvenţială a elementelor vectorului
Deoarece o structură de tip vector cuprinde un număr fixat de elemente de acelaşi tip, pentru a prelucra toate elementele lui se va folosi un ciclu care se va repeta de n ori, unde n- numărul de componente ale vectorului.
For I := to step 1
< Prelucrarea elementului I>
Endfor
Acest algoritm parcurge elementele vectorului de la primul pănă la ultimul.
Pentru a parcurge elementele vectorului în ordine inversă se va folosi următorul algoritm:
For I := valoare finala indice to valoare initiala indice step -1
Prelucrarea elementului I
Endfor
6.1.2.Metode de lucru cu elementele vectorilor
Fie următoarea declaraţie:
Type
Vector=array[1 .. 10] of integer
Var
A: Vector
6.1.2.1.Formarea vectorului
Citirea vectorului de la tastatură
Trebuie să fie formate toate cele 10 componente ale vectorului. Deci folosim algoritmul de prelucrare consecutivă a elementelor, unde în fiecare iteraţie se va citi valoarea care se va memoriza în elementul corespunzător.
Pentru organizarea ciclului cu contor avem nevoie de variabila ciclului, fie I
Var
I:cardinal
Begin
For I:=1 to 10 step 1
ReadInt(A[I])
Endfor
End
Formarea vectorului
1. Sa se formeze un vector elementele căruia sunt primele n numere naturale
Var
I:natural
Begin
For I:=1 to 10 step 1
A[I] := I
End
End
2. Sa se formeze un vector elementele căruia sunt primele n numere Fibonacci
Primul număr Fibonacci este 1.deaceia vom atribui primului element al vectorului A[1] valoara 1. Şi cel de-al doilea număr Fibonacci este 1 şi vom atribui celui de-al doilea element al vectorului valoarea 1. Celelalte numere Fibonacci, începând cu al 3-lea sunt egale cu suma celor doi vecini din stânga, care vor fi referiţi A[I-1] şo A[I-2] respective.
Var
I: natural
Begin
A[1]:=1
A[2]:=1
For I:=3 to 10 step 1
A[I] := A[I-2}+A[I-1]
End
End
6.1.2.2. Afişarea unui vector
Afişarea poate fi făcută în două feluri:
- fiecare element pe un rând;
- toate elementele pe un rând.

Afişarea vectorului - fiecare element pe un rând
Var
I: natural
Begin
For I:=1 to 10 step 1
WriteInt(A[I] )
Writeln
End
End
Afişarea vectorului - toate elementele pe un rând
Var
I: natural
Begin
For I:=1 to 10 step 1
WriteInt(A[I] )
End
End
Afişarea vectorului - toate elementele pe un rând în ordine inversă
Vom folosi algoritmul care parcurge elementele vectorului în ordine inversă
Var
I: natural
Begin
For I:=10 to 1 step -1
WriteInt(A[I] )
End
End
Afişarea elementelor pare ale vectorului
Elementul current al vectorului A[I] va fi afişat numai dacă conţine un număr par (A[I] mod 2 =0)
Var
I: natural
Begin
For I:=1 to 10 step 1
If A[I] mod 2 =0
WriteInt(A[I] )
Endif
End
End
Afişarea elementelor impare de pe poziţii pare
Poziţia înseamnă indicele I, iar elementul de pe poziţia I va fi referit ca A[I]. Pentru a parcurge numai elementele de pe poziţii pare vom începe cu primul element de pe poziţie pară –al 2-lea, apoi cu pasul 2 var fi parcurse celelalte elemente.
Var
I: natural
Begin
For I:=2 to 10 step 2
If A[I] mod 2 #0 then
WriteInt(A[I] )
End
End
End

6.1.2.3. Modificarea valorilor elementelor vectorului
1. De exemplu: să se mărească cu 5 ultimul element al tabloului
Rezolvare:
În acest caz vom accesa direct elementul 5 al vetorului folosind referirea A[10]
A[10]:=A[10]+5

2. Toate elementele negative ale vectorului să fie micşorate de 3 ori
Rezolvare:
Vom parcurge toate elementele vectorului, dar vor fi modificate numai cele negative(A[I]<0)
Var
I: natural
Begin
For I:=1 to 10 step 1
If A[I]<0 then
A[I]:= A[I] div 3
End
End
End
6.1.2.4. Însumarea componentelor unui vector
Însumarea tuturor componentelor unui vector
Suma componentelor se calculează ca orice sumă, se pleacă de la suma nulă. Apoi la fiecare iteraţie i ( i de la 1 la n), suma creşte cu elementul curent, care este A[I]
Var
I: natural
S:integer
Begin
S:=0
For I:=1 to 10 step 1
S:=S+A[I]
End
End
Însumarea componentelor unui vector care posedă o proprietate
Dacă elementul curent posedă proprietatea atunci el este adăugat la sumă.
Exemplu:
Să se calculeze suma elementelor divizibile prin 3
Var
I: natural
S:integer
Begin
S:=0
For I:=1 to 10 step 1
If A[I] mod 3=0 then
S:=S+A[I]
End
End
End
6.1.2.5. Numărarea elementelor vectorului cu o proprietate dată
Proprietatea poate fi:
- Elementul conţine o valoare negativă (A[I]<0);
- Elementul conţine o valoare pozitivă (A[I]<0);
- Elementul conţine o valoare pară (A[I] mod 2 =0);
- Elementul conţine o valoare impară (A[I] mod 2 #0);
- Elementul conţine o valoare egală cu X;
- Elementul e număr prim;
- Elementul e număr perfect etc.
Vom folosi un contor pentru a număra elementele. Iniţial el trebuie să fie nul. De fiecare dată când găsim un element cu proprietatea dată contorul se incrementează cu 1.
Exemplu:
Să se determine câte elemente divizibile prin 5 sau 7 conţine vectorul.
Rezolvare:
Proprietatea se va scrie A[I] mod 5=0 sau A[I] mod 7=0
Var
I: natural
N_el: natural
Begin
N_el:=0
For I:=1 to 10 step 1
If (A[I] A[I]mod5=0) or ( A[I] mod 7=0) then
N_el:=N_el+1
End
End
End

Dacă proprietatatea reprezintă un algoritm mai complicat, se poate elaboara o funcţie logică care verifică dacă un element o posedă sau nu. Apoi în condiţia construcţiei If se va apela această funcţie pentru fiecare element al vectorului.
Să se calculeze căte elemente ale vectorului sunt numere perfecte.
Rezolvare:
Vom elabora funcţia logică Este_perfect
Function Este_perfect(n:natural):Boolean
Var
I: natural
S_div: natural
Begin
S_div:=0
For I:=1 to n-1 step 1
If n mod I=0 then
S_div:=s_div+I
End
End
If s_div=n then
Return True
Else
Return False
End
End
Se va parcurge vectorul şi se va verifica proprietatea apelând funcţia Este_perfect
Var
I: natural
N_el: natural
Begin
N_el:=0
For I:=1 to 10 step 1
If Este_perfect(A[I]) then
N_el:=N_el+1
End
End
End
61.2.6.. Determinarea minimului unui vector
Considerăm minim primul element; apoi parcurgem restul vectorului şi, ori de câte ori găsim un element mai mic, actualizăm minimul la valoarea acelui element.
Min:=A[1]
For I:=2 to n step 1
If A[I] < min then
Min:=A[I]
End
End
La sfârşitul ciclului, variabila min (de acelaşi tip ca şi componentele vectorului) conţine cel mai mic element al vectorului.
Pentru a găsi şi poziţia elementului minim în vector vom modifica algoritmul astfel:
Min:=A[1]
p_min:=1 ; considerăm că elementul minim este pe primul loc în vector
For I:=2 to n step 1
If A[I] < min then
Min:=A[I]
p_min:= I ; dacă s-a găsit alt minim, atunci memorizăm şi poziţia lui
End
End
6.1.27. Determinarea maximului unui vector
Considerăm minim primul element; apoi parcurgem restul vectorului şi, ori de câte ori găsim un element mai mare, actualizăm maximul la valoarea acelui element.
Max:=A[1]
For I:=2 to n step 1
If A[I] > max then
Max:=A[I]
End
End
La sfârşitul ciclului, variabila max (de acelaşi tip ca şi componentele vectorului) conţine cel mai mic element al vectorului.
Pentru a găsi şi poziţia elementului maxim în vector vom modifica algoritmul astfel:
Max:=A[1]
p_max:=1 ; considerăm că elementul maxim este pe primul loc în vector
For I:=2 to n step 1
If A[I] >max then
Max:=A[I]
p_max:= I ; dacă s-a găsit alt maxim, atunci memorizăm şi poziţia lui
End
End
6.1.2.8. Determinarea existenţei în vector a elementelor cu oproprietate dată
Se poate aplica algoritmul de numărare a elementelor cu o proprietate dată. Dacă N_el>0 rezultă că există aşa elemnte, altfel – nu există.
Var
I: natural
N_el: natural
Begin
N_el:=0
For I:=1 to 10 step 1
If Este_perfect(A[I]) then
N_el:=N_el+1
End
End
End
If N_el>0 then
WriteString(‘Există’)
Else
WriteString(‘Nu există’)
End
Acest algoritm ar putea fi optimizat. Parcurgerea vectorului se va face de la prima poziţie, până la sfârşit sau până s-a găsit primul element căutat. Această metodă, de comparare succesivă a valorii căutate cu cele din vector, considerate în ordinea apariţiei lor, este denumită căutare secvenţială.
Fie A vectorul cu n elemente în care este căutată valoarea X şi Gasit o variabilă de tip Boolean, a cărei valoare precizează dacă valoarea căutată a fost găsită sau nu. Înainte de a începe căutarea, variabila Găsit trebuie iniţializată cu valoarea false, deoarece nu s-a găsit valoarea căutată (X). Atunci când aceasta este găsită, variabilei Gasit i se atribuie valoarea True şi căutarea se termină. Dacă însă vectorul nu conţine valoarea X, valoarea variabilei Gasit rămâne neschimbată(False), căutarea terminându-se după analiza ultimului element din vector.
Algoritmul care realizează căutarea,conform celor expuse anterior, este următoarea:

Gasit:=false
I:=1
While (I<=n) and (not Gasit) do
If A[I]=X then
Gasit:=true
Endif
I:=I+1
End
If Gasit then
WriteString(‘Există’)
Else
WriteString(‘Nu există’)
End
Dacă am transfera verificarea condiţiei din corpul ciclului în condiţia ciclului, algoritmul ar fi următorul:
I:=1
While (I<=n) and (A[I] # X) do
I:=I+1
End
Ieşirea din ciclu se va face sau când elementul căutat s-a găsit ( A[I]#X = False) sau când în vector nu mai sunt elemente (I>n)
Deci,
If I<=n then
WriteString(‘Există’)
Else
WriteString(‘Nu există’)
End
Dacă se cere ca rezultatul căutării să fie reprezentat de indicele primului element din vector egal cu X, atunci ultimele două variante ale căutării se modifică după cum urmează:
1) Gasit:=false
I:=1
While (I<=n) and (not Gasit) do
If A[I]=X then
Gasit:=true
End
I:=I+1
End
If Gasit then
prim:=i-1
Else
WriteString(‘Nu există’)
End
2) I:=1
While (I<=n) and (A[I] # X) do
I:=I+1
End
If I<=n then
prim:=i
Else
WriteString(‘Nu există’)
End
Dacă se cere ca să fie căutat ultimul element al vectorului egal cu X, atunci se pot folosi aceiaşi algoritmi, numai că parcurgerea vectorului se va face în direcţie opusă, începând cu ultimul element.
I:=n
While (I>=1) and (A[I] # X) do
I:=I-1
End
If I<=1 then
ultim:=i
Else
WriteString(‘Nu există’)
End