Structura de date este o colectie de date inzestrata cu informatii structurale care permit identificarea si selectia componentelor. r6r10rk
Componentele unei structuri de date pot fi identificate si selectate fie prin numele, fie prin intermediul relatiilor structurale. Cea mai simpla relatie structurala este pozitia fiecarei componente in cadrul structurii.
Asupra unei structuri de date se pot aplica mai multe tipuri de operatii :vizualizarea elementelor structurii sub diferite forme, actualizarea(adaugarea, modificarea sau stergerea unei componente), imbogatirea structurala(prin adaugarea unor informatii de legatura) sortare(aranjarea componentelor intr-o anumita ordine stabilita de un anumit criteriu de ordonare.
Din punct de vedere al continutului, structurile pot fi:
-omogene(toate componentele structurii sunt de acelasi tip)
-neomogene(componentele structurii sunt de tipuri diferite) in functie de modul in care sunt memorate structurile de date se impart in doua mari categorii:
-Structuri interne, sunt create in memoria interna RAM a sistemului, si au un caracter temporar, datorita faptului ca memoria interna este volatila.
-Structuri externe, sunt depozitate pe un suport de memorie externa (hard-disk.floppy-disk), avand astfel un caracter permanent.
TABLOURI
Un sir de elemente de acelasi tip, in care conteaza ordinea elementelor, se numeste vector sau tablou unidimensional.
Un tablou(array) este o structura formata dintr-un numar fixat de componente de acelasi tip, numit tip de baza. Numarul de componente este determinat de numarul de valori ale indicilor, care sunt obligatoriu tipuri ordinale. Pozitia unui element se mai numeste si indicele sau rangul elementului, iar elementele se mai numesc si componente ale vectorului. Sintaxa declararii tipului tablou este : type_nume=arrayatip_ordinal1,......tip_ordinalni 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=arraya1..100i 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 dupa numele tabloului, intre paranteze drepte.
Tipul tablou arrayatip_ordinali of tip poate ramane si anonim. Astfel, putem scrie ceva de genul type vector=array ...si var x:vector pe scurt prin var x:array...Adica, tipul tablou ramane anonim, nu trebuie neaparat sa primeasca un nume(aici cel de vector). tip_ordinal si tip pot fi atat tipuri anonime, cat si identifictori de tip.
Limbajul Turbo Pascal nu ne permite sa declaram o variabila de tip array cu un numar variabil de componente. De multe ori nu stim cate componente vor fi necesare pentru o anumita rulare a programului. Orice problema in care se lucreaza 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 numar maxim de componente, atat cat este necesar pentru rulare atunci cand n este maxim. la fiecare rulare a programului se cere numarul de componente. De cele mai multe ori o parte dintre cele rezervate raman neutilizate.
Prin declararea unui vector vom intelege numarul maxim de elementele acestuia. Numarul elementelor efective folosite, care difera de la o executie la alta se numeste numar real (efectiv de elemente).
"Vizualizarea" tuturor elementelor pe rand si prelucrare acestora se numeste parcurgere. Parcurgerea intr-un ciclu pozitiile elementelor din vector i=1,2,3,...,n si pentru fiecare valoare a lui i, "vizitam" si prelucram elementul vaii, adica elementul aflat pe pozitia i: secventa de program for i:=1 to n d0
<prelucrarea vaii urmarirea ciclului pas cu pas
Pasul 1:i:=1,prelucreza va1i
Pasul 2:i:=2,prelucreza va2i
------------------------------------ Pasul n:i:=n,prelucreza vani
OPERATII CU VECTORI
O variabila de tip tablou nu poate fi citita sau scrisa in intregime. In Turbo Pascal7.0 Se pot face atribuiri intre variabile de acelasi tablou. Dar, e preferabil sa se lucreze pe componente .Cu componentele unui tablou Se pot face toate operatiile ce Se pot face cu orice variabila de acel tip (afisare, citire, atribuire etc)
1.citirea unui vector
Aceasta inseamna citirea numarului n de componente, intr-un ciclu for, de pilda. De fapt avem de citit componenta numarului i, cu i de la 1 la n. Deci putem scrie: for i:= 1 to n do begin
write('dati xa',x,'i='); readln(xaii); end;
2.Srierea unui vector cand trebuie sa afisam vectorul, adica toate componentele sale efective numarul acestora este cunoscut. Afisarea se realizeaza ciclic si poate fi astfel:
-fiecare element pe un rand(folosita mai ales cand avem vectori si siruri de caractere) for i:1to n do
writeln(xaii);
-toate elementele pe acelasi rand, despartite de virgula si/sau spatii(in cazul valorilor numerice) for i:=1 to n do
write(xaii,',');
writeln;
3.inversarea unui vector in alt vector vom inversa vectorul x in vectorul y, de acelasi tip cu x, deci vom pune in componenta ya1i pe xani,in componenta ya2i pe xan-1i...,im componenta yani pe xa1i for i :=1 to n do yaii:=xan+1-ii
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 xaii cu xan+1-ii; for i:=1 to n do div 2 do begin aux:=xAii; xaii:=x an+1-ii; xan+1-ii:=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:=xa1i for i:=2 to n do if xaii<xa1i then minim:=xaii;
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 vaii,daca va1i mai mic decat vaii,atunci vaii 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:=xa1i;maxim:=xa1i; for i:= 2 to n do begin if xaii<minim then minim:=xaii if xaii>maxim then maxim:=xaii 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 xaii. suma:=0; for i:= 1 to n do suma:=suma+xaii;
9.Afisarea elementelor pare dintr-un vectorde numere intregi. sa consideram var x:=arrayA1..20i 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(xaii) then
writeln(xaii)
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 xaii.Asadar va trebui sa avem not odd )i)si oddxaii for i:=1 to ndo if (not oddaii) and odd(xaii)
writeln(xaii)
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 xaii<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 xaii:=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 xaii:=xai-1i; xapi:=m; n:=n=1;
Ordonare vectorilor
Metoda selectiei directe.
Consideram ca avem un vector de elemente comparabile intre ele, sa ordonam crescator elementele vectorului. Metoda este urmatoarea il punem pe cel mai mai in fata ,apoi procedam la fel cu restul elementelor .Aceasta metoda se implementeaza astfel: vom compara pe xa1i cu toate elementele de dupa el. Daca gasim un element xaji care e mai mic decat xa1i,atunci interschimbam pe xa1i cu xaji .Cand am ajuns la ultimul element inseamna ca pe prima pozitie va fi sigur cel mai mic element din vector(noul xa1i) in continuare, ne ocupam doar de elementele de pe pozitia doi incolo si vom parcurge vectorul pana la xani ca si in primul caz. Aceste traversari ale vectorului ,insotite de eventualile interschimbari au loc pana la penultima pozitie, cand mai are loc doar o singura comparare, intre xan-1i si xani
Metoda bubble-sort se compara fiecare element xaii cu elementul de pe pozitia succesoare, deci cu elementul xai+1i.Daca elementele nu sunt puse in ordine crescatoare, se vor schimba intre ele. Procesul se repeta pana cand la o traversare a lui x nu mai are loc nici o interschimbare
Sortare prin numarare
Pentru fiecare element din vector se numara cate elemente mai mici decat el exista in vector. program ordonare alfabetica; var x:arraya1..20i of string; i,j,n:integer;aux:string; begin
write ('cati elevi sunt?='); readln(n) ; for i:=1 to n do; begin
write('nume elev x ',i,':'); readln(xaii); end; for i:=1 to n-1 do for j:=i+1 to n do if xaii<xaji then begin aux:=xaii;xaii:=xaji;xaji:=aux; end;
writeln ('ordinea alfabetica este:'); for i:= 1 to n do writeln(i,'',xaii); readln; end.
Interclasarea a doi vectori
Presupunem ca dispunem de doi vectori( eventual de dimensiuni diferite) ordonati, sa obtinem vectorul reuniune ordonat. Fie a si b doi vectori, iar in vectorul c sa punem rezultatul. Vom proceda in felul urmator
1 vom compara primul element din vectorul a cu primul element din vectorul b si pe cel mai mic il vom pune in c, eliminandu-l din vectorul de unde provine;
2 procesul se repeta pana cand se epuizeaza unul din vectori;
3 Se copiaza la sfarsitul lui c toate elementele din vectorul ramas neterminat, care fireste vor fi deja ordonate, cat si mai mari ca ultimul element din vectorul care s-a epuizat primul.
Cautare binara
Cautarea binara se foloseste pentru a determina existenta unui element intr-un vector. Daca elementele vectorului sunt deja ordonate crescator sau descrescator, atunci procesul cautarii poate deveni mai rapid, daca se aplica cautarea binara .
Se compara elementul cauta cu elementul din mijloc si, daca ele nu coincid, se va trece la cautare doar in acea jumatate a vectorului in care in mod logic, elementul cautat s-ar putea gasi, in stanga sau in dreapta, dupa cum elementul din mijloc este mai mare sau mai mic decat elementul cautat s.a.m.d. pana cand domeniul in care trebuie sa mai caute sa terminat.