TABLOURI  UNIDIMENSIONALE (SIRURI, VECTORI)

 

În cazul în care o aplicaţie trebuie să prelucreze un  şir de 20 de numere, să le ordoneze crescător de exemplu, numerele sunt date de intrare pentru algoritm şi în primul pas vor fi introduse în memoria calculatorului.

La pasul urmator numerele vor fi prelucrate  şi aranjate conform criteriului de ordonare precizat, după care, la al treilea pas, vor fi furnizate utilizatorului sub formă de date de ieşire. În memoria internă ele vor fi reprezentate într-o structura de date de tip tablou de memorie.

Tabloul este o structură de date internă formată dint-o mulţime ordonată de elemente, ordonarea făcându-se cu un ansamblu de indici. Tabloul de memorie se va identifica după un nume, iar fiecare element al său, după numele tabloului  şi numărul său de ordine. Fiecare element al structurii se identifică după numele tabloului şi poziţia din tablou. De la început trebuie să se precizeze câte elemente are tabloul pentru ca sistemul să-i aloce zona de memorie corespunzătoare. În timpul prelucrării tabloului nu i se pot adăuga mai multe elemente decât au fost alocate, pentru că se iese din spaţiul de memorie alocat. Tabloul de memorie este o structură de date statică.

Tabloul cu o singură dimensiune este numit  vector.

Declararea unui tablou de memorie de tip vector se face prin instructiunea: 

Tip_data nume [ nr_elemente ];

Aici,  tip_data precizează tipul elementelor vectorului,  nume este identificatorul vectorului, iar  nr_elemente este o constantă întreagă care specifică numărul de elemente ale vectorului. De exemplu, prin:

int a[20];  se declară un vector cu 20 de elemente de tip întreg.

La declararea unui vector se pot atribui valori iniţiale elementelor sale astfel:

Tip_data nume[ nr_elemente ] = { lista_valori };

Exemplu:

int a[5]={10, 20, 2, 4, 9 };

În cazul declarării unui vector iniţializat se poate omite numărul elementelor sale, dacă se iniţializează toate elementele.

Referirea la un element al vectorului se face prin construcţia:

nume[indice];

unde  nume este numele tabloului, iar  indice este numărul de ordine al elementului în vector. În C++ numerotarea indicilor se face pornind de la 0!

 

CĂUTARE SECVENŢIALĂ

Căutarea secvenţială este unul dintre cei mai simpli algoritmi studiaţi. El urmăreşte să verifice apartenenţa unui element la un  şir de elemente de aceeaşi natură, în speţă a unui număr la un şir de numere. Pentru aceasta se parcurge şirul de la un capăt la celălalt şi se compară numărul de căutat cu fiecare număr din  şir. În cazul în care s-a găsit corespondenţă (egalitate), un indicator flag este poziţionat. La sfârşitul parcurgerii şirului, indicatorul ne va arăta dacă numărul căutat aparţine sau nu şirului.

#include<iostream>

using namespace std;

int main() 

int n,x,i,gasit,a[50]; 

 cout<<“Dati numarul de elemente ale sirului : “; cin>>n; 

 cout<<“Dati numarul de cautat : “; cin>>x;

 cout<<“Dati elementele sirului”<<endl;

 gasit=0;

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

{

  cout<<“a[“<<i<<“]= “;

  cin>>a[i];

            if (a[i]==x) gasit=1;

 } 

if (gasit==0)

                         cout<<“Numarul nu apartine sirului !”<<endl;

else

 cout<<“Numarul apartine sirului !”<<endl;

}

 

CĂUTARE BINARĂ

Algoritmul de căutare binară oferă performanţe mai bune decât  algoritmul de căutare secvenţială. El funcţionează astfel: se compară numărul de căutat cu elementul aflat la mijlocul şirului (element care se mai numeşte şi pivot). În cazul în care cele două elemente coincid căutarea s-a încheiat cu succes. Dacă numărul de căutat este mai mare decât pivotul, se continuă căutarea în aceeaşi manieră în subşirul delimitat de pivot şi capătul şirului iniţial. Dacă numărul de căutat este mai mic decât pivotul se continuă căutarea în aceeaşi manieră în subşirul delimitat de pivot  şi începutul  şirului iniţial.

Algoritmul prezentat se încadrează în clasa algoritmilor elaboraţi conform tehnicii de programare Divide et Impera.

Unul din dezavantajele acestui algoritm este că şirul în care se face căutarea trebuie să fie iniţial sortat.

#include<iostream>

using namespace std;

int main() 

int i, n, x, st, dr, mijl, gasit, a[50];

 cout<<“Introduceti numarul elementelor vectorului : “;

 cin>>n;

 cout<<“Introduceti elementul de cautat : “;

 cin>>x;

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

  cout<<“a[“<<i<<“]= “;

  cin>>a[i];

 }

 st=0; dr=n-1; gasit=0;

while (st<=dr && gasit!=1) { 3

  mijl=(st+dr)/2;

    if (a[mijl]==x)

   gasit=1; 

            else

      if (x<a[mijl])

    dr=mijl-1;

      else 

    st=mijl+1;

 }

if (st>dr)

  cout<<“Nu s-a gasit elementul cautat !”<<endl;

else

  cout<<“Elementul cautat apartine sirului !”<<endl; 

}

 

 

 

 

 

Problemă.

Să se elaboreze un algoritm pentru  ştergerea dintr-un vector a elementului cu indicele k  şi deplasarea elementelor vectorului, începând cu indicele k+1, cu o poziţie spre stânga, lungimea logică a vectorului micşorându-se cu 1.

#include<iostream>

using namespace std;

int main()

{

int i,n,k,a[10];

 cout<<“Introduceti dimensiunea vectorului : “; cin>>n;

 cout<<“Introduceti indicele elementului ce se elimina : “; cin>>k;

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

{

  cout<<“a[“<<i<<“]=”;

  cin>>a[i];

 }

 

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

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

 

cout<<“Vectorul rezultat este : “;

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

  cout<<a[i]<<” “<<endl;

}

Problemă.

Algoritmul pentru inserarea unui element într-un vector în poziţia indicelui k înseamnă deplasarea elementelor vectorului, începând cu indicele k+1, cu o poziţie spre dreapta şi apoi atribuirea noii valori lementului cu indicele k. Lungimea logică a vectorului se va mări cu o unitate  şi va fi n+1, cu condiţia ca n+1 să fie mai mic sau cel puţin egal cu lungimea fizică a vectorului, altfel ultimul element al vectorului se pierde.

#include<iostream>

using namespace std;

int main()

{

const int dim=10;

int i,n,k,x,a[dim];

 cout<<“Introduceti dimensiunea vectorului (<=10): “; cin>>n;

 cout<<“Introduceti pozitia de inserare : “; cin>>k;

 cout<<“Introduceti elementul ce se insereaza : “; cin>>x;

 

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

{                                                           //sunt citite componentele vectorului

  cout<<“a[“<<i<<“]=”;

  cin>>a[i];

 }

 

 cout<<“Vectorul obtinut prin inserare este : “;

if(n!=dim)

{

  for(i=n;i>k-1;i–)                   //daca dimensiunea era strict mai mica decat dim, putem obtine

      a[i]=a[i-1];                       //un vector de dimensiune mai mare, fara pierderea de elemente

  

  a[k-1]=x;

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

   cout<<a[i]<<” “;

 }

else { 

    if (k<n-1)                            //prin inserarea elementului x se pierde ultima componenta a

    {  for(i=n-1;i>k-1;i–)        //vectorului citit de la tastatura

              a[i]=a[i-1];                //prima ramura din if-ul urmator este pentru situatia in care

              a[k-1]=x;                  //pozitia de inserare nu este ultima pozitie a vectorului initial

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

            cout<<a[i]<<” “;

    }

    else {                                   //cazul in care trebuie inserat un element pe ultima pozitie

             a[n-1]=x;                   //a vectorului initial

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

             cout<<a[i]<<” “;

            }

 }

 cout<<endl; }

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s