Tablouri unidimensionale: vectori

COLEGIUL NATIONAL

“MIHAIL KOGALNICEANU”

TABLOURI

UNIDIMENSIONALE:

VECTORI.

TABLOURI UNIDIMENSIONALE.

TIPURI STRUCTURATE

Spre deosebire de tipurile simple, tipurile structurate sunt combinatii de alte tipuri,definite prin descrierea tipurilor componente si prin indicarea modului de strcturare.

Tipurile structurate sunt : tablou,inregistrare si multime.

Ca un caz particular al tipului tablou,putem mentiona tipul sir de caractere.

TIPUL TABLOU

Tipul tablou contine un numar fix de componente de acelasi tip.

Tipul comun al elemetelor se numeste TIP DE BAZA al tabloului.

Pentru a avea acces la continutul componentelor unui tablou,vom folosi pozitia elementului din tablou,numita si indice.Aceasta mai trebuie sa fie un tip ordinal.Tipul tablou poate fi oricare din tipurile de baza si structurate.

Tabloul poate fi privit ca o functie definita pe multimea indicelui tabloului cu valori in multimea tipului de baza al tabloului.

In cazul in care componentele unui tablou sunt accesate dupa un singur indice, tabloul se numeste VECTOR(sau TABLOU UNIDIMENSIONAL).

Daca elementele sunt accesate dupa mai multi indici, atunci tabloul este tablou multidimensional.

Compilatorul face verificari pentru depasirea limitelor tabloului. In acest fel este asigurata o protectie a datelor impotriva distrugerii accidentale.

Elementelor tabloului le sunt permise orice operatii valabile tipului de baza.Ele sunt stocate in zone de memorie continue.

TABLOURI IN C ++

In C++ tipul tablou se declara astfel :

TIP NUME [nr. natural 1 nr. natural 2][nr.natural n].

* Exemplul 1: int v[100];

v[0] v[1] v[2] v[98] v[99]

- am declarat un vector cu 100 de componente de tip intreg. Adresarea unei componente se face prin indice, care se trece intre paranteze drepte.

ATENTIE ! Componentele au indicii intre 0 si 99. Aceasta regula este valabila in general.

De exemplu, daca dorim sa adresam componenta a doua, scriem v[1].

*Exemplul 2 : float a[50], b[50] ;

- am declarat doi vectori, a si b, care au componente de tip float.

a[0] a[1] a[2] ______________ a[48] a[49]

b[0] b[1] b[2] ______________ b[48] b[49]

Limbajul C ++ nu ne permite sa declaram o variabila tablou cu un numar variabil de componente (exista si limbaje care permit aceasta, de exemplu Basic).

De multe ori nu stim cate componente vor fi necesare pentru o anumita rulare a programului. Orice problema in care se lucreaza cu variabile de tip tablou si in care se cere prelucrarea unui numar(care nu se cunoaste de la inceput) de componente, constitue un exemplu in acest sens. Atunci ce facem ?

Ideea este sa rezervam un numar maxim de componente, atat cat este necesar pentru rulare atinci cand n este maxim. La fiecare rulare a programului se cere numarul de componente. De cele mai multe ori o parte dintre ele raman neutilizate.

1). Analizam programul urmator. Acesta citeste si tipareste variabila din exemplul 1.

Initial, se citeste n (numarul componentelor). Dupa aceasta se citesc, pe rand, toate componentele. Sa presupunem ca s-a citit n = 3.

Se citesc apoi trei numere intregi, cate unul pentru fiecare componenta si anume : 6 . Citirea s-a facut cu ajutorul instructiunii FOR, unde variaila de ciclare reprezinta chiar indicele componentei care se citeste(i ia valori intre 0 si 2).

In final, se tipareste continutul componentelor citite. Restul componentelor vor retine valoarea initiala(reziduala, pentru ca aceasta nu este cunoscuta).

#include<iostream.h>

void main()

for(i=0;i<n;i++)

cout<<v[i]<<endl;

}

Inainte de a citi o componenta afisam numele variabilei, urmat de indicele componentei(intre paranteze) si semnul ’=’ .De exemplu se va afisa :

*v[1]=_se asteapta introducerea valorii pentru prima componenta.

*v[2]=_se asteapta introducerea valorii pentru a doua componenta.

*v[3]=_se astapta introducerea valorii pentru a treia componenta.

OBSERVATIE :Nu sunt permise atribuiri de forma b=a(unde a si b sunt tablouri).In acest caz atribuirea se face pe componente.

Programul de mai jos utilizeaza 2 vectori ,cu componente de tip float.Se citeste vectorul a.Apoi se face atribuirea de mai sus,pe componente.

La sfarsit se tipareste vectorul b.

#include<iostream.h>

void main()

for(i=0;i<n;i++)

b[i]=a[i];

for(i=0;i<n;i++)

cout<<b[i]<<endl;

}

MAXIM,MINIM

Se citeste un vector cu n componente numere intregi.Se cere sa se afiseze cel mai mare numar gasit.

Exemplu :n=4 si se citesc valorile :2,-4,3,5.Se va afisa 5.

O variabila (max) va prelua continutul primei componente .Pe rand, continutul acesteia va fi comparat cu numerele intregi retinute de componentele 2,3,..,n.

In cazul in care se gasaste un numar mai mare decat cel retinut de variabila max,aceasta va retine acel numar.Iata situatia initiala.

-4<2(continutul variabilei max).Se terce mai departe.

v

max

In final ,valoare maxima gasita este 5.

#include<iostream.h>

int v[9],n,i,max ;

void main()

max=v[0];

for(i=1;i<n;i++)

if(v[i]>max)

max=v[i];

cout<<”valoarea maxima citita este:”<<max;

MULTIMI

In acest paragraf prezentam programe care realizeaza principalele operatii cu multimi(reuniune, intersectie etc.).

A citi o multime, inseamna a introduce elementele care o alcatuiesc.

Acestea sunt memorate intr-o variabila de tip vector. Presupunem ca elementele introduse sunt distincte.

a). * TESTUL DE APARTENENTA.

Se citeste multimea A de numere intregi. Se citeste un numar intreg e, sa se decida daca e € A.

Pentru rezolvare, procedam intr-un mod clasic. O variabila gasit va retine, initial, o valoare 0. Apoi se testeaza fiecare element al multimii A daca este sau nu egal cu numarul retinut de e. In caz de egalitate variabila gasit va retine 1. La sfarsit, se va da raspunsul in functie de continutul variabilei gasit.

#include<iostream.h>

int mult[9],n,e,i,gasit ;

void main()

cout<<elementul considerat:”;cin>>e;

gasit=0;

for(i=0;i<n && !gasit;i++)

if(mult[i]==e) gasit=1;

if(gasit) cout<<”elem. apartine multimii”;

else cout<<”elem. nu apartine multimii”;

}

b). *DIFERENTA A DOUA MULTIMI.

Se citesc 2 multimi A si B.Se cere sa se afiseze multimea C=A-B.

O variabila k (cu valoare initiala 0) retine indicele componentei din C, care va memora urmatorul element ce se adauga multimii diferenta.In final,se tipareste C.Afisarea se face numai pentru componentele de indice intre 0 si k-2.

#include<iostream.h>

int multa[9],multb[9],multc[9],n,m,i,j,k,gasit ;

void main()

cout<<”nr de elemente al multimii B“;

cin>>m;

for(i=0;i<m;i++)

k=0;

for(i=0;i<n;i++)

cout<<”A-B”<<endl;

for(i=0;i<k;i++)

cout<<multc[i]<<endl;

}

c). *REUNIUNEA A 2 MULTIMI

Se citesc doua multimi de numere intregi A si B.Se cere sa se afiseze multimea C=AUB.

Pentru rezolvare ,se rezerva 3 variabile de tip tablou cu componente care retin numere intregi(A,B,C).Dupa citirea celor doua multimi A si B se multimea B,apoi A-B.

Aplicam formula : C=AUB=BU(A-B)

#include<iostream.h>

int multa[9],multb[9],multc[9],n,m,i,j,k,gasit;

void main()

cout<<”nr de elemente al multimii B”;cin>>m;

for(i=0 ;i<m ;i++)

k=0;

for(i=0;i<n;i++)

cout<<”A reunit cu B”<<endl;

for(i=0;i<m;i++) cout<<multb[i]<<endl;

for(i=0;i<k;i++) cout<<multc[i]<<endl;

}

d). *INTERSECTIA A DOUA MULTIMI

Se citesc 2 multimi de numere intregi A si B.Se cere sa se afiseze multimea C=A∩B.

Pornind de la definitie,se deduce imediat algoritmul : pentru fiecare element al multimii A se face testul de apartenenta la multimea B,iar in caz afirmativ, este adaugat la o multime C,initial vida.

#include<iostream.h>

int multa[9],multb[9],multc[9],n,m,i,j,k,gasit ;

void main()

cout<<”nr de elemente al multimii B”;cin>>m;

for(i=0 ;i<m ;i++)

k=0;

for(i=0;i<n;i++)

cout<<”A intersectat cu B”<<endl;

for(i=0 ;i<k ;i++)

cout<<multc[i]<<endl ;

}

e). *PRODUSUL CARTEZIAN (a doua multimi)

Fie multimile A

B

m si n se citesc.Se cere sa se afiseze multimea :C=A*B.

#include<iostream.h>

char multa[9],multb[9] ;

int n,m,i,j ;

void main()

cout<<”nr de elem al multimii B”;cin>>m;

for(i=0;i<m;i++)

for(i=0;i<n;i++)

for(j=0;j<m;j++)

cout<<multa[i]<<” “<<multb[j]<<endl;

}

METODE DE SORTARE

SORTAREA

Se citesc n numere intregi. Se cere ca acestea sa fie scrise in ordine crescatoare (descrescatoare).

Operatia prin care se aranjeaza cele n numere in ordine crescatoare (descrescatoare) se numeste sortare.

Pentru a sorta cele n valori, acestea se citesc intr-o variabila de tip tablou. Sortarea propriu-zisa se face in cadrul acestei variabile. Se cunosc o multime de algoritmi de sortare, acestia au fost elaborati in timp.

Orice valoare care apartine unui tip asupra caruia pot actiona operatorii relationari (<,>,<=,>=) se poate sorta.

Prin urmare:

* Vaorile care apartin unuia dintre tipurile intregi pot fi sortate

* Valorile apartinand unuia din tipurile reale pot fi sortate

a). *SORTAREA PRIN SELECTAREA MINIMULUI(MAXIMULUI)

Algoritmul este :

- se determina minimul dintre valorile retinute, incepand cu prima pozitie.

- minimul este trecut in prima pozitie prin interschimbarea continuturilor dintre componenta de indice 1 si componenta care il memoreaza.

- se determina minimul dintre valorile retinute, incepand cu a doua pozitie.

- minimul este trecut in pozitia 2, prin interschimbarea continuturilor dintre componenta de indice 2 si componenta care il memoreaza.

- se detrmina minimul dintre valorile retinute, incepand cu a treia pozitie.

..

- se detrmina minimul dintre valorile retinute, incepand cu penultima pozitie.

- minimul este trecut in penultima pozitie, prin interschimbarea continuturilor dintre componenta de indice n-1 si componenta care il memoreaza.

#include<iostream.h>

int a[9],n,i,j,k,man,min ;

void main()

for(i=0;i<n-1;i++)

man=a[k];

a[k]=a[i];

a[i]=man;

}

for(i=0;i<n;i++)

cout<<a[i]<<endl;

}

b).*SORTAREA PRIN INTERSCHIMBARE

Algoritmul este urmatorul:

-se parcurge variabila continuturilor componentelor alaturate care nu sunt in ordine crescatoare(descrescatoare).

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

Fie situatia initiala:

A

A[1] A[2] A[3] A[4]

*Se efectueaza prima parcurgere.Se inverseaza valorile retinute de componente 1 si 2.Se obtine :

A

A[1] A[2] A[3] A[4]

*Valorile retinute de componentele 2 si 3 nu se inverseaza.In schimb,se inverseaza valorile retinute de componentele 3 si 4.

A

A[1] A[2] A[3] A[4]

*Intrucat au loc inversari se parcurge vectorul.Se inverseaza valorile retinute de componentele 2 si 3.

A

A[1] A[2] A[3] A[4]

*Alte inversari nu se fac.Intrucat in actuala parcurgere au fost facute inversari,se reparcurge vectorul, de data aceasta inutil si algoritmul se incheie.

SORTAREA PRIN INTERSCHIMBARE

#include<iostream.h>

int a[9],n,i,k,man,gasit ;

void main()

do

}

while (gasit);

for(i=0;i<n;i++)

cout<<a[i]<<endl;

}

c). * SORTAREA PRIN INSERTIE.

Cu ajutorul variabilei citite A (vector) se aranjeaza valorile intr-o alta B (vector) in ordine crescatoare. Pentru aceasta se procedeaza astfel :

B[1]= A[1] ;

- fiecare din valorile retinute de componentele de la 2 la n (in ordinea indicilor) se insereaza intre valorile ordonate deja ale vectorului B.

- vom alege cazul de sortare crescatoare.

Fie i cu proprietatea ca a[1] < a[2]<a[3]<<a[i-1]

Ideea de sortare consta in inserarea lui a[i] in subsirul ordonat anterior. Pentru aceasta comparam pe rand a[i] cu elementele a[1], a[2], a[i-1] pana cand vom gasi pozitia j, cuprinsa intre 1 si i, astfel incat a[j]> a[i].

Atunci elementul va fi inserat pe pozitia j-1 si celelalte elemente de la pozitia j la i-1 vor fi deplasate cu o pozitie la dreapta.

In cazul in care j este egal cu i nu va mai avea loc nici o deplasare. Repetam acest procedeu de insertie a elementului a[i] pentru i de la 2 la n.

In final se va obtine tabloul a ordonat crescator.

#include<stdio.h>

void main()

puts(“sirul ordonat este”);

for(i=0;i<n;i++)

printf(“%d”,x[i]);

}

d). *SORTAREA SHELL SORT

Algoritmul de sortare SHELL, cunoscut si sub numele de “sortarea prin micsorarea incrementului”, consta in urmatorii pasi:

- se vor grupa mai intai toate elementele in n/2 perechi si se va ordona fiecare pereche. Elementele din orice pereche vor fi situate la distanta de n/2 elemente unul de celalalt.

- la a doua trecere se vor grupa in n/4 grupe a cate patru elemente si se va ordona fiecare grupa. La acest pas elementele vor fi situate la distanta n/4 unul de celalalt.

In general continuam la fiecare astfel :

-daca la pasul anterior avem n/k grupe a cate k elemente, la pasul urmator k se va injumatati, luand astfel un grup de 2*k elemente situate la distante k/2 unul de celalalt, care se vor ordona.

Procesul de injumatatire a pasului pentru grupele elementelor sortate se va continua pana va ajunge la distanta 1 si va exista un singur grup in care sunt incluse toate elementele.

Aceasts repetare a ordonarii, asemanatoare cu metoda BUBLE SORT (unde pasul k este tot timpul 1) este ma avantajoasa din punct de vedere al timpului de executie.

#include<stdio.h>

void main()

} while(b==0);

} while(k!=1);

printf(“sirul ordonat este:”);

for(i=1;i<=n;i++)

printf(“%d”,v[i]);

}

CAUTAREA BINARA

Pentru cautarea binara se vor efectua urmatorii pasi:

1.- se stabilesc reperele pentru intervalul de cautare intre care se poate afla numarul :

st=1 ; dr=n ;

se alege pozitia din mijloc : p= (st+dr)/2;

Comparand valoarea elementului din tablou de pe pozitia p cu cheia de cautare c avem cazurile :

a). Daca valoarea numarului de pe pozitia din mijloc este egala cu valoarea cheii de cautare se termina cu succes si se tipareste pozitia gasita.

b). Daca valoarea numarului de pe pozitia din mijloc este mai mica dacat valoarea cheii de cautare, atunci cheia se poate afla doar in a doua jumatate a intervalului de cautare. In acest caz se actualizeaza limita din stanga : st=p+1

c). Daca valoarea numarului de pe pozitia dim mijloc este mai mare ca valoarea cheii de cautare atunci intervalul de cautare se restrange la prima jumatate. Astfel se va actualiza reperul din dreapta : dr= p-1

Cautarea continua in cat timp nu s-a gasit cheia cautata si cat timp lungimea intervalului de cautare este pozitiva. Aceasta inseamna ca dr >= st.

#include<stdio.h>

void main()

if(x[p]<c)

st=p+1;

else dr=p-1;

}

printf(« nu se afla in tablou « );

}

INTERCLASAREA

Interclasarea a doua tablouri de numere reale ordonate crescator.

Dupa cum se stie interclasarea este procedeul de obtinere, plecand de la doua tablouri ordonate, a unui nou tablou ordonat care contine toate elementele celor doua tablouri componente.

Vom avea doua variante de interclasare a doua tablouri a si b. Fie a[i], i=1.m si b[i], i=1..n cele doua tablouri ordonate crescator.

Sirul interclasat va fi stocat in tabloul c[i], i=1..m +n.

Vom asigura printr-o singura parcurgere obtinerea sirului c, comparand succesiv cate un element din sirul a de pe pozitia i cu un element din sirul b de pe pozitia j.

La acest moment toate elementele a[1], a[2], .,a[i-1] respectiv b[1], b[2],b[j-1] au fost deja stocate in tabloul c.

PRIMA VARIANTA :

In urma comparatiei se va prelua valoarea cea mai mica. Se va repeta aceasta operatie pana cand se vor stoca toate elementele din unul din cele doua tablouri.

Dupa aceasta se vor copia direct in tabloul c, elementele ramase de stocat ale celuilalt tablou.

#include<stdio.h>

void main()

VARIANTA A DOUA:

2. Interclasarea prin santinele

Pentru aceasta vom adauga cate un element fictiv in cele doua tablouri, numit SANTINELA, ales astfel:

- primul tablou de dimensiune m, santinela va fi elementul de pe pozitia m+1 din tabloul care va avea o valoare mai mare decat orice element din celalalt tablou b.

Spre exemplu :

a[m+1]=b[n]+1

- in al doilea tablou de dimensiune n santinela va fi elementul de pe pozitia n+1 din tablou care va avea o valoare mai mare dacat orice element din celalalt tablou a.

Spre exemplu :

a[n+1]=b[m]+1

Interclasarea se va face comparand printr-un ciclu de lungime m+n elementul curent din cele doua tablouri a si b. La fel ca la varianta anterioara de interclasare, valoarea preluata in tabloul c va fi cea mai mica valoare.

Datorita folosirii santinelelor, elementele stocate dupa un ciclu de lungime m+n vor fi toate elementele di tablourile initiale fara cele doua valori ale santinelelor care vor asigura o limita peste care nu se va trece in preluarea elementelor din cele doua tablouri.

#include<stdio.h>

void main()

CULEGERE DE C/C ++: autor- STOIELESCU DORIAN

editura - RADIAL.

INFORMATICA C ++ : autor - TUDOR SORIN

editura - L&S INFOMAT

3. MANUAL DE INFORMATICA C ++:

autori - CORNELIA IVASC

- MONA CARMEN PRUNA

- LUMINITA CONDURACHE

- DOINA HRINCIUC- LOGOFATU

editura - PETRION