TABLOURI UNIDIMENSIONALE

 

Structura de date este o colecţie de date înzestrată cu informaţii structurale care permit identificarea şi selecţia componentelor.

Componentele unei structuri de date pot fi identificate si selectate fie prin numele, fie prin intermediul relaţiilor structurale. Cea mai simpla relaţie structurala este poziţia fiecărei componente in cadrul structurii.

Asupra unei structuri de date se pot aplica mai multe tipuri de operaţii :vizualizarea elementelor structurii sub diferite forme, actualizarea(adăugarea, modificarea sau ştergerea unei componente), îmbogăţirea structurală(prin adăugarea unor informaţii de legătura) sortare(aranjarea componentelor intr-o anumita ordine stabilita de un anumit criteriu de ordonare.

Din punct de vedere  al conţinutului, structurile pot fi:

-omogene(toate componentele structurii sunt de acelaşi tip)

-neomogene(componentele structurii sunt de tipuri diferite)

in funcţie de modul in care sunt memorate structurile de date se împart in doua mari categorii:

-Structuri interne, sunt create in memoria interna RAM a sistemului, şi au un caracter temporar, datorită faptului ca memoria interna este volatila.

-Structuri externe, sunt depozitate pe un suport de memorie externa (hard-disk.floppy-disk), având astfel un caracter permanent.

TABLOURI

Un sir de elemente de acelaşi tip, în care contează ordinea elementelor, se numeşte vector sau tablou unidimensional.

Un tablou(array) este o structura formata dintr-un număr fixat de componente de acelaşi tip, numit tip de baza. Numărul de componente este determinat de numărul de valori ale indicilor, care sunt obligatoriu tipuri ordinale. Poziţia unui element se mai numeşte si indicele sau rangul elementului, iar elementele se mai numesc si componente ale vectorului. Sintaxa declarării  tipului tablou este :

type_nume=array[tip_ordinal1,......tip_ordinaln] of tip_oarecare

unde:

n-reprezinta dimensiunea tabloului

tip_ordinal1,...tip_ordinaln reprezinta tipul indicilor tabloului

tip_oarecare reprezinta tipul componentelor tabloului

!Obervatii.In cazul in care tip_ordinal este unul din tipurile intregi,este obligatoriu sa folosim subdomeniile lui

Exemplu: type vector=array[1..100] of integer;

var v:vector;

variabila v este un tablou de dimensiune 1 cu 100 componente intregi  identificate prin indici din subdomeniul 1..100.

Aici tipul ordinal este subdomeniu al tipului integer, iar tipul oarecare este ineger. Componentele unui tablou sunt memorate pe zone de memorii consecutive. Adresarea unei componente a tabloului se face prin indice (o valoare a tipului ordinal) care se specifica după numele tabloului, între paranteze drepte.

Tipul tablou array[tip_ordinal] of tip poate rămâne si anonim. Astfel, putem scrie ceva de genul type vector=array ...si var x:vector pe scurt prin var x:array...Adică, tipul tablou rămâne anonim, nu trebuie neapărat să primească un nume(aici cel de vector).

tip_ordinal si tip pot fi atât tipuri anonime, cât si identifictori de tip.

Limbajul Turbo Pascal nu ne permite sa declaram o variabila de tip array cu un număr variabil de componente. De multe ori nu ştim cate componente vor fi necesare pentru o anumita rulare a programului. Orice problema în care se lucrează cu variabila de tip array si in care se cere prelucrare a n componente constituie un exemplu in acest sens .In acest caz ideea este sa rezervam un număr maxim de componente, atât cat este necesar pentru rulare atunci când n este maxim. la fiecare rulare a programului se cere numărul de componente. De cele mai multe ori o parte dintre cele rezervate rămân neutilizate.

Prin declararea unui vector vom înţelege numărul maxim de elementele acestuia. Numărul elementelor efective folosite, care diferă de la o execuţie la alta se numeşte număr real (efectiv de elemente).

"Vizualizarea" tuturor elementelor pe rând si prelucrare acestora se numeşte parcurgere. Parcurgerea intr-un ciclu poziţiile elementelor din vector i=1,2,3,...,n si pentru fiecare valoare a lui i, "vizităm" si prelucram elementul v[i], adică elementul aflat pe poziţia i: secvenţa de program

for i:=1 to n d0

<prelucrarea v[i]

urmarirea ciclului pas cu pas

Pasul 1:i:=1,prelucreza v[1]

Pasul 2:i:=2,prelucreza v[2]

-------------------------------------

Pasul n:i:=n,prelucreza v[n]

OPERAŢII CU VECTORI

O variabila de tip tablou nu poate fi citita sau scrisa in întregime. In Turbo Pascal7.0 Se pot face atribuiri intre variabile de acelaşi tablou. Dar, e preferabil sa se lucreze pe componente .Cu componentele unui tablou Se pot face toate operaţiile ce Se pot face cu orice variabilă de acel tip (afişare, citire, atribuire etc)

1.citirea unui vector

Aceasta înseamnă citirea numărului n de componente, intr-un ciclu for, de pilda. De fapt avem de citit componenta numărului i, cu i de la 1 la n. Deci putem scrie:

for i:= 1 to n do

begin

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

readln(x[i]);

end;

2.Srierea unui vector

când  trebuie sa afişăm vectorul, adică toate componentele sale efective numărul acestora  este cunoscut. Afişarea se realizează ciclic si poate fi astfel:

-fiecare element pe un rând(folosita mai ales când avem vectori si şiruri de caractere)

for i:1to n do

writeln(x[i]);

-toate elementele pe acelaşi rând, despărţite de virgula si/sau spatii(in cazul valorilor numerice)

for i:=1 to n do

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

writeln;

3.inversarea unui vector in alt vector

vom inversa vectorul x in vectorul y, de acelaşi tip cu x, deci vom pune in componenta y[1] pe x[n],in componenta y[2] pe x[n-1]...,im componenta y[n] pe x[1]

for i :=1 to n do

y[i]:=x[n+1-i]

4.inversarea unui vector in el insasi

Va trebui sa  schimbam prima componenta cu ultima,pe a doua cu penultima s.a.m.d.,pana la mijloc vom intelege n div 2 indiferent daca n este par sau impar.Asadar,va trebui sa parcurgem vectorul pana la n div 2 intershimband pe x[i] cu x[n+1-i];

for i:=1 to n do div 2 do

begin

aux:=x{i];

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

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

end;

5.determinarea elementului minim dintr-un vector

Aceasta problema se rezolva astfel:consideram minim primul element,apoi parcurgem restul vectorului si,ori de cate ori gasim un element mai mic actualizam minimul la valoarea acelui element

minim:=x[1]

for i:=2 to n do

if x[i]<x[1] then minim:=x[i];

In acest moment,la sfarsitul ciclului,variabila minim(de acelasi tip ca si componentele x) contine cel mai mic element din vector

6.determinarea elementului maxim dintr-un vector

Se actualizeaza  maximul intr-o variabila max.Algoritmul este asemanator cu cel de minim.Initializam maximul cu primul element.Parcurgem intr-un ciclu pozitiile celorlalte elemente i pentru fiecare element v[i],daca v[1] mai mic decat v[i],atunci v[i] devine noul maxim.

7.determinarea simultana a minimului si maximului dintr-un vector

Pentru a realiza aceste lucruri simultan se procedeaza dupa cum urmeaza:

minim:=x[1];maxim:=x[1];

for i:= 2 to n do

begin

if  x[i]<minim then minim:=x[i]

if  x[i]>maxim then maxim:=x[i]

end;

Evident daca vectorul contine doar un singur element acela va fi si maxim si minim

8.insumarea componentelor unui vector de numere

Suma componentelor unui vector se calculeaza ca orice suma,se pleaca cu suma nula,apoi la fiecare pas i (i de la 1 la n),suma creste cu elementul curent,care este x[i].

suma:=0;

for i:= 1 to n do

suma:=suma+x[i];

9.Afisarea elementelor pare dintr-un vectorde numere intregi.

sa consideram var x:=array{1..20] of integer,si var n,i:integer.Vom parcurge vectorul si vom afisa doar numerele pare:

for i:=1 to n do

if not odd(x[i]) then

writeln(x[i])

10.afisarea elementelor impare de pe pozitii pareale unui vector de intregi

Vectorul are componentele intregi.Consideram aceleasi variabile ca si la problema anterioara.Daca spunem pozitie trebuie sa ne gandimla indice,iar dac spunem element trebuie sa ne gandim la elementul de pe pozitia i,deci la x[i].Asadar va trebui sa avem not odd )i)si oddx[i]

for i:=1 to ndo

if (not  odd[i]) and odd(x[i])

writeln(x[i])

11.numararea elementelor negative si a celor pozitive dintr-un vector de numere.

Fie NN Si NP cele doua numere.Acestea se comporta ca doua contoare,initial nule,De fiecare data cand gasim in sirul de numere un element negativ se incrementeazaNN,NN:=NN+1,altfel NP.

NN=0;NP=0;

for i:=1to n do

if x[i]<0 then inc(NN)

else inc(NP);

writeln('Exista',NN,'elemente negative');

writeln('Exista,'NP',elemente pozitive');

12cautare secventiala a unui element intr-un vector

Aceasta problema necesita pentru  a putea fi reolvata si o parcurgere a vectorului de la prima pozitie pana la sfarsit sau pana s-a gasit elementul cautat.Gasirea elementului cautat este marcat de o variabila logica gasit,pozitionata initial pe fals.Fie x vectorul,iar a elementul cautat

gasit:=false;

i:=1

while(i:=n) and (not gasit) do

if x[i]:=a then

gasit:=true

else

inc(i)

12.inserarea unui element dintr-un vector.

sa inseram,pe poozitia p intr-un vector,un element nou m.Pentru aceasta vom deplasa elementele de pe pozitiile de la p la n,unde n ete numarul de elemente ale vectorului,cu o pozitie mai incolo spre dreapta.Deplasare se vaface de la pozitia ultima inspre pozitia p.In final vom pune elementul m pe pozitia p.Fireste numarul de elemnte ale vectorului vor creste cu o unitate:n:=n+1

for i:=n+1 downto p+1 do

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

x[p]:=m;

n:=n=1;

Ordonare vectorilor

Metoda selecţiei directe.

Consideram ca avem un vector de elemente comparabile intre ele, să ordonam crescător elementele vectorului. Metoda este următoarea il punem pe cel mai mai in fata ,apoi procedam la fel cu restul elementelor .Aceasta metoda se implementează astfel: vom compara pe x[1] cu toate elementele de după el. Dacă găsim un element x[j] care e mai mic decât x[1],atunci interschimbam pe x[1] cu x[j] .Când am ajuns la ultimul element înseamnă ca pe prima poziţie va fi sigur cel mai mic element din vector(noul x[1]) in continuare, ne ocupam doar de elementele de pe poziţia doi încolo si vom parcurge vectorul pana la x[n] ca si in primul caz. Aceste traversări ale vectorului ,însoţite de eventualile interschimbari au loc  pana la penultima poziţie, când mai are loc doar o singura comparare, intre x[n-1] si x[n]

Metoda bubble-sort

se compara fiecare element x[i] cu elementul de pe poziţia succesoare, deci cu elementul x[i+1].Daca elementele nu sunt puse in ordine crescătoare, se vor schimba  intre ele. Procesul se repeta pana când la o traversare a lui x nu mai are loc nici o interschimbare

Sortare prin numărare

Pentru fiecare element din vector se număra cate elemente mai mici decât el exista in vector.

program ordonare alfabetica;

var x:array[1..20] of string;

i,j,n:integer;aux:string;

begin

write ('cati elevi sunt?=');

readln ;

for i:=1 to n do;

begin

write('nume elev x ',i,':');

readln(x[i]);

end;

for i:=1 to n-1 do

for j:=i+1 to n do

if x[i]<x[j] then

begin

aux:=x[i];x[i]:=x[j];x[j]:=aux;

end;

writeln ('ordinea alfabetica este:');

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

readln;

end.

Interclasarea a doi vectori

Presupunem ca dispunem de doi vectori( eventual de dimensiuni diferite) ordonaţi, să obţinem vectorul reuniune ordonat. Fie a si b doi vectori, iar in vectorul c sa punem rezultatul. Vom proceda in felul următor

1 vom compara primul element din vectorul a cu primul element din vectorul b si pe cel mai mic îl vom pune in c, eliminându-l din vectorul de unde provine;

2 procesul se repeta pana când se epuizează unul din vectori;

3 Se copiază la sfârşitul lui c toate elementele din vectorul rămas  neterminat, care fireşte vor fi deja ordonate, cât şi mai mari ca ultimul element din vectorul care s-a epuizat primul.

Căutare binara

Căutarea binara se foloseşte  pentru a determina existenta unui element intr-un vector. Dacă elementele vectorului sunt deja ordonate crescător sau descrescător, atunci procesul căutării poate deveni mai rapid, daca se aplica căutarea binara  .

Se compara elementul căuta cu elementul din mijloc si, daca ele nu coincid, se va trece la căutare doar in acea jumătate  a vectorului  in care in mod logic, elementul căutat s-ar putea găsi, in stânga sau in dreapta, după cum elementul din mijloc este mai mare sau mai mic decât elementul căutat s.a.m.d. pana când domeniul in care trebuie sa mai caute sa terminat.