Vectori - Algoritmi Elementari - Stive și Cozi

1. SCOPUL LUCRARII

In aceasta lucrare se studiaza tablourile unidimensionale (vectorii). Acestea reprezinta structurile de date eel mai frecvent utilizate. Ele sunt incluse in majoritatea limbajelor de programare. De aceea, tablourile sunt un bun punct de start pentru prezentarea domeniului structurilor de date. Se studiaza de asemenea alte doua structuri de date, mai abstracte, stiva si coada, implementate cu vectori.

2. BREVIAR TEORETIC

Un tablou reprezinta o colectie de date de acelasi tip. Un tablou poate sa alba una sau mai multe dimerisiuni. Tablourile unidimensionale sunt denumite vectori.

La declararea unui tablou se specifics numarul de elemente ale fiecarei dimensiuni, incluzand fiecare dintre aceste numere intre paranteze drepte. Indexul inferior al fiecarei dimensiuni este 0.

Sintaxa pentru declararea unui vector este urmatoarea:

tipul_datelor nume_vector[numarul_total_de elemente]; Exemplu: tab -vector ce contine 100 de numere reale:

double tab[100];

Elementele tabloului se acceseaza indexand corespunzator numele tabloului. Exemplu:

tab[10]=tab[10]+l;

Un vector poate fi initializat inca din faza de declarare, ca in exemplul urmator:

intx[4]={-l, 2, 0, 56};

Un tablou, in general, poate contine si componente al caror tip este nestandard, declarat de programator cu cuvantul cheie typedef, ca in exemplul urmator:

typedef unsigned char byte;

bytexflOOJ;

Tabloul, la fel ca §i alte structuri de date ce vor fi studiate ulterior (liste inlantuite, arbori) sunt adecvate pentru memorarea informatiilor caracteristice unei baze de date (inregistrari numerice dintr-un experiment, inregistrari de personal al unei firme, etc.). Tablourile permit accesul rapid la un element memorat.

Sunt alte structuri de date ce sunt in primul rand utilizate pentru a simplifica anumite activitati de programare. Dintre aceste vom studia stivele si cozile. Astfel, stiva este o structura de date utila pentru stocarea parametrilor actuali transmisi unei functii (subprogram). Coada este o structura de date folosita pentru a efectua cautari intr-un graf. Stivele si cozile pot fi insa utilizate si pentru modelarea unor activitati reale ( astfel, cu ajutorul unei cozi putem modela o coada de asteptare la un spectacol, sau pachetele de date ce urmeaza a fi transmise pe Internet). Stivele §i cozile reprezinta structuri de date mai abstracte decat tablourile. Ele pot fi implementate cu tablouri (ca in aceasta lucrare de laborator) sau cu liste inlantuite. De regula, mecanismul de implementare este ascuns utilizatorului, acesta avand acces la structura de date respectiva (stiva sau coada) printr-un set de functii.

O stiva este o lista liniara ce are proprietatea ca operatiile de inserare / extragere a datelor se fac pe la un singur cap. Ultimul element inserat va fi primul extras. De aceea stivele se mai numesc si liste LIFO (last in, first out). Deci, intr-o stiva, spre deosebire de vectori, avem acces la un moment dat, la un singur element: eel care a fost inserat ultimul. Operatiile esentiale asupra unei stive sunt introducerea unui element in varful stivei push() si extragerea elementului din varful stivei: pop().

O coada este o lista liniara ce are proprietatea ca operatiile de inserare a nodurilor se fac pe la un cap, iar extragerile pe la celalalt cap. Primul nod inserat va fi primul nod extras. De aceea cozile se mai numesc si liste FIFO (first in, first out). Structura de coada modeleaza un rand de asteptare pentru bilete la un spectacol. Prima persoana din rand, este prima care ajunge sa cumpere bilete.

Operatiile importante asupra cozilor sunt inserarea unui element in spatele cozii si §tergerea elementului din fata cozii. Un caz particular de cozi sunt cozile circulare ce se implementeaza folosind un vector C de dimensiune n, pe care II tratam ca si cum ar fi circular : dupa locatia C[n-1] urmeaza locatia 0.

3. DESFA§URAREA LUCRARII

Se vor edita si apoi executa programele descrise in continuare.

3.1. Programul nr. 1 Calculul maximului si a pozitiei lui intr-un vector.

Algoritm:

- intializare maxim cu prima valoare din vector

- initializare pozitie maxim cu pozitia 0

- pentru resrul valorilor din vector se repeta

se compara maximul cu elemental curent daca elemental curent > maxim atunci:

- se memoreaza noul maxim

- se memoreaza noua pozitie Greseli frecvente:

- neinitializarea pozitiei maximului

- initializarea maximului cu 0 Sursa programului: Mnclude <stdio.h> Mnclude <conio.h>

Mefine N 51/nr. componente vector void mainQ

{

int a[N];

int i, max, pozMax; clrscrQ; for(i=0;i<N;i++){

printf("a[%d]=",i);

scanf("%d",&a[i]);

}

max=a[0]; pozMax=0; for(i=l;i<N;i++) if(a[i]>max){ max=a[i]; pozMax=i;} printf("max=%d,pozitia:=%d",max,pozMax); getchl); }

3.2. Programul nr. 2 Cautarea liniara a unui numar intr-un vector.

Algoritm:

-initializare semafor (flag) estePrezent cu 0 (fals - presupunem ca nu este prezent.) -se parcurge vectorul de la prima la ultima valoare daca numar este egal cu element curent atunci:

-estePrezent=l ("se ridica" variabila flag, caci s-a gasit) -iesire fortata din bucla -daca semaforul estePrezent este 0 atunci nu este prezent numaral in vector altfel este prezent Greseli frecvente:

- neinitializarea variabilei semafor, sau initializarea ei inversa, cu 1 in loc de 0.

- se da un nume nesugestiv pentru variabila semafor. De exemplu: x. Desi nu afecteaza corectitudinea rezultatelor, programul este dificil de urmarit.

- se uita iesirea fortata din bucla. Desi, nu implica aceasta asupra corectitudinii rezultatului, se pierde inutil timp .

- greseala de sintaxa frecventa: if(a[i]=numar) in loc de if(a[i]= =numar). ( Operatorul de comparatie in limbajul C este =

= ■)

Sursa programului:

Mnclude <stdio.h>

Mnclude <conio.h>

#define N 5 //nr. componente vector

void mainQ

{

int a[N];

int i, estePrezent, numar; clrscrQ; for(i=0;i<N;i++){

printf("a[%d]=",i);

scanf("%d",&a[i]);

}

printfC 'numar•= ");

scanf("%d", &numar);

2

estePrezent=0; for(i=0;i<N;i++) if(a[i]~-numar) { estePrezent=1; break;} if(estePrezent==0)printf("NU."); elseprintf("DA"); getchO; }