Tehnologie Afaceri Scoala Didactica Legislatie Familie

Acasa » scoala » informatica
TIPURI DE DATE STRUCTURATE

TIPURI DE DATE STRUCTURATE

TIPURI DE DATE STRUCTURATE

DEF:

Tipurile de date structurate, spre deosebire de cele simple, sunt combinatii de alte tipuri definite prin descrierea tipurilor componentelor si prin indicarea unor metode de structurare.

A. TIPUL TABLOU (ARRAY)

A1.Tablouri unidimensionale (vectori)

DEF:

Un sir de elemente de acelasi tip se numeste vector sau tablou unidimensional.

SINTAXA:

1. Type vector=array[1..20] of integer

reprezinta un sir de elemente numere intregi numerotate de la 1 la 20.

2. Prin VAR x:vector;

x[3] -componenta de ordin 3

x[i] -componenta de ordin i

OPERATII cu vectori

a). citirea

- prima data se face citirea nr de componente, iar apoi citirea componenta cu componenta:

write('dati nr de componente:');readln(n);

for i := 1 to n do begin

write('x[', i ,']=');

readln(x[ i ] );

end;

b)scrierea

- se poate face scriind:

- fiecare element pe un rand

for i := 1 to n do writeln(x[i]);

- toate elementele pe acelsi rand despartite prin virgule sau spatii:

for i := 1 to n do write(x[i],' ');

writeln;

exemplu:

- citirea unui vector si afisarea acestuia in ordine inversa.

Program scriere_vector ;

Var x:array[1..25] of real;

i,n:integer;

Begin

Write('n=');readln(n);

For i:=1 to n do begin

Write('x[',i,']=');

Readln (x[i]);

end;

For i :=n downto 1do

write(x[i]:3:2,' ');

End.

c) inversarea unui vector in alt vector:

- vom inversa vectorul x si y , y de acelasi tip cu x, avand in y₁ pe X_m, in y₂ pe X_m-1 in Y_m pe x₁.

OBS:

Intotdeauna suma celor doi indici de pozitie (din x si y ) este acceasi si este egala cu m+1, deci pentru centralizare in componenta y, vom pune valorea lui x[m+1-i].

d) inversarea unui vector in el insusi:

- se face pana la mijlocul sau indiferent daca m este impar sau par:

for i:=1 to (n div 2) do begin

aux:=x[i];

x[i]:=x[m+1-i];

x[m+1-i]:=aux;

end;

unde ''aux '' este variabila de acelasi tip cu x[i].

e) determinarea minimului unui vector:

min:=x[1];

for i:=2 to n do

if x[i]<min then min:=x[i];

unde ''min'' este de acelasi tipcu x[i];

f) determinarea simultana a minimului si maximului dintr-un vector:

min:=x[1];

max:= x[1];

for i:=2 to n do begin

if x[i]<min then min:=x[i];

if x[i]>max then max:=x[i];

end;

g) insumarea componentelor unui vector:

- se calculeaza ca orice suma;

- se pleaca de la suma nula;

- apoi la fiecare pas i suma creste cu elementul curent(x[i]):

s:=0;

for i:=1 to n do s:=s+x[i];

exemplu:

Sa se calculeze suma patratelor componentelor unui vector:

program suma;

var x:array[1..25] of integer;

s:longint;

n,i:integer;

begin

write('n=');readln(n);

for i:=1 to n do begin

write('x[',i,']=');readln(x[i]);

end;

s:=0;

for i:=1 to n do

s:=s+x[i]*x[i];

writeln('suma=',s);

end.

h) afisarea elementelor pare dintr-un vector de numere intregi:

for i:=1 to n do

if not(odd(x[i])) then writeln(x[i]);

i) afisarea elementelor impare de pe pozitii pare:

for i:=1 to n do

if (not odd i) and odd(x[i]) then writeln(x[i]);

j) numararea elementelor negative si a celor pozitive dintr-un vector;

- de fiecare data cand gasim un element negativ incrementeaza nn (nn:=nn+1);altfel se incrementeaza np (np:=np+1);

nn:=0;

np:=0;

for i:=1 to n do if x[i] <0 then nn:=nn+1

else np:=np+1;

k) cautarea secventiala a unui element intr-un vector:

- aceasta problema necesita pentru rezolvarea ei o parcurgere a vectorului de la prima pozitie pana la sfarsit sau pana s-a gasit elementul cautat. Gasirea elementului cautat e marcata de o variabila logica pozitionata initial pe valoarea ''false'':

write('el cautat=');readln(a);

gasit:=false;

i:=1;

while (I<=m) and not gasit do

if x[i]=a then gasit:=true

else i:=i+1:

l) inserarea unui element intr-un vector:

- inseram pe pozitia p intr-un vector un element m;

- pentru aceasta deplasam elementul de pe pozitia p pe n, unde n reprezinta nr de elemente ale vectorului, cu o pozitie mai incolo, deplasarea se va face de la ultima pozitie inspre pozitia p. In final punem elementul pe pozitia m, nr de elemente ale vectorului va creste cu o unitate (n devine n+1);

for i:=n+1 downto p+1 do x[i]:=x[i-1];

x[p]:=m;

n:=n+1;

q1) METODE DE SORTARE ale vectorului:

- se citesc n nr intregi si se cere ca acestea sa fie scrise in ordine descrescatoare. De exemplu pt n=4 se citesc nr 3,1,6,2. Ordonate vor fi 1,2,3,6.

Operatia prin care se aranjeaza cele n nr in ordine crescatoare se numeste sortare.

Sortare prin calculul minimului:

Se calculeaza minimul dintre valorile retinute incepand cu prima pozitie. Minimul este trecut in prima pozitie prin interschimbarea continuturilor dintre componente si componenta care-l memoreaza. Se calculeaza minimul dintre valorile retinute incepand cu a doua pozitie. .

min=1 min=2

 

 

 

min=3

ordonat

program sortare_minim;

var

a:array[1..100] of integer;

n,i,k,j,man,min :integer;

begin

write('n=');readln(n);

for i:=1 to n do begin

write('a[',i,']=');

readln(a[i]);

end;

for i:=1 to n-1 do begin

min:=a[i];

k:=i;

for j :=i+1 to n do

if a[j]<min then begin

min:=a[j];

k:=j;

end;

man:=a[k];

a[k]:=a[i];

a[i]:=man;

end;

for i:= 1 to n do

write(a[i], ');

end.

Sortare prin interschimbare:

- se parcurge vectorul inversand continuturile componentelor alaturate care sunt in ordine crescatoare;

- procedeul se repeta pana cand are loc o parcurgere in care se nu fac inversari;

program interschimbare;

var

a:array[1..10] of integer;

n,i,man:integer;

gasit:boolean;

begin

write('n=');readln(n);

for i:=1 to n do begin

write('a[',i,']=');readln(a[i]);

end;

repeat

gasit:=false;

for i:=1 to n-1 do

if a[i]>a[i+1] then begin

gasit:=true:

man:=a[i];

a[i]:=a[i+1];

a[i+1]:=man;

end;

until not gasit;

for i:= 1 to n do

write(a[i]);

end.

Sortare prin insertie

- cu ajutorul variabilei citite ''a'' de tip array se aranjeaza valoarea intr-o alta variabila ''b'' de tip array ordonata crescator:

b[1]:=a[1];

for i:=2 to n do begin

j:=i-1:

while (j>0) and (a[i]<b[j]) do begin

j:=j-1;

for k:=(i-1) downto (j+1) do begin

b[k+1]:=b[k];

b[j+1]:=a[i];

end;

end;

end;

for i:=1 to n do

writeln(b[i]);

end.

Sortare prin metoda bulelor

- fie tabloul a₁,a₂,..,a_n; a_i - intreg; i = 1,n. Sirul este ordonat crescator daca intre elementele sale exista relatia: a₁ <= a₂ <= . <= a_n.

Algoritmul de cautare binara

-se da un sir de nr intregi si presupus ordonat. Sa se caute daca o valoare oarecare se gaseste in acest sir, folosind algoritmul de cautare binara;

A2. TABLOU BIDIMENSIONAL (MATRICI)

Def:

MATRICE = tablou bidimensional in care regasirea unui element se face pe baza de 2 indici.

i - indice de linie

j - indice de coloana.

a[i,j] - matricea a cu i linii si j coloane.

Nr de elementelor unei matrice = i*j;

Matricea in care numarul liniilor este egal cu numarul coloanelor se numeste matrice patratica; (i=j).

Relatii intre indicii unei matrice patratice:

- deasupra diagonalei principale i < j

- pe diagonala principala i = j

- sub diagonala principala i > j

- deasupra diagonalei secundare i+j < n+1

- pe diagonala secundara i+j = n+1

- sub diagonala secundara i+j > n+1

Declarea unei matrici:

Type matrice=array[1..10,1..10] of tip element

Var a:matrice

OPERATII CU MATRICI

a)citirea

- se face prin intermediul a doua structuri de tip for

for i := 1 to m do

for j := 1 to n do

begin

write('a[',I,',',j,']=');

readln(a[I,j]);

end;

b) tiparirea

for i := 1 to m do begin

for j:=1 to n do write(a[I,j],' ');

writeln;

end;

B) TIPUL STRING

Def:

- tip special de vector cu elemente de tip caracter (char), care memoreaza in afara caracterelor din sir si lungimea respectivului sir de caractere, adica nr de caractere existente in sir.

-- variabilele de tip string ocupa in memorie un spatiu egal cu n+1 octeti, unde n reprezinta nr de caractere din sir.

-- o varibila de tip string este o succesiune de caractere cuprinsa intre 2 caractere apostrof

-- tipul string este predefinit, adica nu e nevoie sa fie declarat cu ''type'' el fiind cunoscut.

Declararea

-- pt constante:

const

nume_constanta='sir de caractere'

-- pt variabile:

const

nume_variabila:string[constanta de tip byte];

--lungimea sirului de caractere se precizeaza optional si trebuie sa fie de tip byte[0-255].

Obs:

Cand declaram un tablou de string-uri este bine sa specificam, pt string, dimensiunea.

Operatii cu siruri:

a) citirea

v    variabilele de tip string pot sa apara ca argument in apelul procedurii ''read'', in acest fel citindu-se intreg sirul de caractere:

var x,y:string[5];

begin

read(x,y);

b)scrierea

v    forme admise v salv si v:w.

v    in cazul utilizarii primei forme se afiseaza toate caracterele reprezentand valorile expresiei v incepand de la pozitia cursorului.

v    pentru a doua forma, daca sirul de caractere are mai putin de w elemente, elementul se va afisa alineat la dreapta in zona cuprinzand w pozitii.

c) functia concat

v    concateneaza intr-un singur sir toate sirurile de caractere ce apar in lista de parametrii efectivi. Sirul rezultat prin concatenare nu trebuie sa depaseasca 255 de caractere, caracterele care sunt in plus se pierd.

v    apelul are forma concat(s1,s2,s3.sn); unde ''s_i'' reprezinta un sir de caractere.

v    functia concat(s1, s2) este echivalenta cu s1+ s2

d) functia copy:

v    returneaza subsirul unui sir care apare ca parametru efectiv al functiei, obtinut prin preluarea a n caractere din sir incepand cu o pozitie i, precizata in apel.

v    apelul are forma: copy(sir,i,n) unde:

sir = expresie string

n, i = var de tip intreg sau byte.

Obs:

v    Daca incepand din pozitia i sirul are mai putin de n caractere se vor prelua doar cele existente;

v    functia copy returneaza sir vid daca i este mai mare decat lungimea sirului.

e) functia pos:

v    returneaza pozitia unui subsir intr-un sir, rezultatul fiind de tip byte.

v    daca subsirul nu este continut in sir functia returneaza valoarea zero.

Apelul are forma:

Pos(subsir,sir); unde subsir, sir: tip string.

f) procedura delete:

v    sterge n caractere dintr-un sir, incepand cu o pozitie i.

v    daca i depaseste lungimea sirului, procedura este inafectiva, iar daca n depaseste numarul de caractere existente in sir incepand cu pozitia i se vor sterge doar acestea.

Apelul are forma:

Delete(sir,I,n) unde sir-tip string

I,n---tip intreg.

C) TIPUL ARTICOL(inregistrare-record)

Def:

Tipul inregistrare reprezinta cea mai flexibila structura de date. Spre deosebire de tipul tablou,acest tip cuprinde un nr fix sau variabil de componentenumite ''campuri'' al caror tip nu este neaparat acelasi definind astfel o structura neomogena.Componentele nu pot fi indexate

Printr-o expresie ,ca in cazul tablourilor, ci se selecteaza prin intermediul identificatorilor de camp care se definesc la declararea tipului inregistrare. Datorita acestui fapt, identificatorul de camp se mai numeste si '''selector'.

Declarare

Type

Cd_tip_inregistrare=record

Lista_de_campuri_1:id_tip1;

Lista_de_campuri_2:id_tip2;

......

Lista_de_campuri_n:id_tip_n;

End:

Var var_inregistrare:id_tip_inregistrare;

Operatii care actioneaza la nivelul unei variabile de tip record:

1)atribuirea

--are ca efect o atribuire multipla si se poate face doar intre 2 variabile ce fac parte din acelasi tip de inregistrare;

--fiecare camp al variabile din membrul stang primeste valoare campului corespunzator din variabila membrului drept:

--limbajul Turbo Pascal incepand cu versiunea 7.0 pune la dispozitie instructiunea WITH care parmite accesarea campurilor unei date de tip record fara specificarea identificatorului datei respective.

--aceasta instructiune des utilizata si in situatiile cand o data de tip inregistrare cuprinde un camp care este tut un tip inregistrare.

2)accesarea campurilor:

se face prin identificatorul datei si a campului respectiv separate prin caracterul ''.'';

Obs:

*instructiunea

with var1,var2,var3,.,varn do

instructiuni..

este echivalenta cu :

with var1 do

with var2 do

......

with var n do

instructiuni.

.com	Copyright © 2024 - Toate drepturile rezervate. Toate documentele au caracter informativ cu scop educational.