Tipuri de Date C++

Tipurile de date standard in C++ sunt:
1. char - este un tip de date pentru numere intregi sau caractere care se reprezinta pe 1 octet. Are semn iar valorile lui sunt in intervalul [-128, 127].
2. unsigned char - este un tip de date pentru numere intregi sau caractere care se reprezinta pe 1 octet. Nu are semn, valorile lui sunt doar pozitive si sunt in intervalul [0, 255].
3. short - este un tip de date pentru numere intregi care se reprezinta pe 2 octeti. Are semn iar valorile lui sunt in intervalul [-32768, 32767].
4. unsigned short - este un tip de date pentru numere intregi care se reprezinta pe 2 octeti. Nu are semn, valorile lui sunt doar pozitive si sunt in intervalul [0, 65535].
5. int - este un tip de date pentru numere intregi care se reprezinta pe 4 octeti. Are semn iar valorile lui sunt in intervalul [-2³¹, 2³¹-1].
6. unsigned int - este un tip de date pentru numere intregi care se reprezinta pe 4 octeti. Nu are semn, valorile lui sunt doar pozitive si sunt in intervalul [0, 2³²-1].
7. long - este un tip de date identic cu int.
8. long long - este un tip de date pentru numere intregi foarte mari care se reprezinta pe 8 octeti. Are semn iar valorile lui sunt in intervalul [-2⁶³, 2⁶³-1].
9. unsigned long long - este un tip de date pentru numere intregi foarte mari care se reprezinta pe 8 octeti. Nu are semn, valorile lui sunt doar pozitive si sunt in intervalul [0, 2⁶⁴-1].
10. float - este un tip de date pentru numere in virgula mobila si se reprezinta pe 4 octeti.
11. double - este un tip de date pentru numere in virgula mobila si se reprezinta pe 8 octeti.
12. long double - este un tip de date pentru numere in virgula mobila si se reprezinta pe 12 octeti.

Algoritmi de cautare

O sa consideram cazul in care cautam un numar intreg intr-o colectie(vector) de numere intregi.

1. Cautare secventiala. Este cea mai simpla metoda, se parcurge vectorul de la primul la ultimul element si se compara pe rand elementul cautat cu fiecare element al vectorului.

int v[100], n, a, pos=-1;
//se citeste n si apoi se citesc n numere intregi in vectorul v.
//a este valoarea pe care o cautam si pos este pozitia in vector
// la care am gasit valoarea a
for (int i = 0; i < n; i++)
{
    if (v[i] == a)  
    {
        pos = i;
        break;
    }
}
if (pos >= 0)
{
    cout<<"valoarea cautata a fost gasita pe pozitia "<<pos;
}
else
{
    cout<<"valoarea cautata nu a fost gasita";
}

2. Cautare secventiala intr-un vector sortat crescator. Este acelasi algoritm de mai sus cu deosebirea ca vectorul in care cautam este ordonat crescator. Aici se poate face o mica modificare pentru ca algoritmul sa devina mai eficient. Daca ajungem la o valoare in vector mai mare decat valoarea cautata abandonam cautarea deoarece toate valorile din vector care vor urma sunt mai mari decat elementul curent.

int v[100], n, a, pos=-1;
//se citeste n si apoi se citesc n numere intregi ordonate crescator
//in vectorul v. a este valoarea pe care o cautam si pos este 
//pozitia in vector la care am gasit valoarea a
for (int i = 0; i < n; i++)
{
    if (v[i] == a)  
    {
        pos = i;
        break;
    }
    else if (v[i] > a)
    {
        break;
    }
}
if (pos >= 0)
{
    cout<<"valoarea cautata a fost gasita pe pozitia "<<pos;
}
else
{
    cout<<"valoarea cautata nu a fost gasita";
}

3. Cautare binara. Vectorul in care cautam este ordonat crescator. Folosim metoda de programare "Divide et impera" si o functie recursiva. Comparam valoarea cautata cu elementul din mijlocul vectorului si daca este egalitate terminam cautarea. Daca valoarea cautata este mai mica decat elementul din mijlocul vectorului atunci continuam cautarea in jumatatea stanga a vectorului (de la primul element pana la elementul din stanga elementului din mijloc) si daca este mai mare continuam cautarea in jumatatea dreapta. Conditia de oprire a recursivitatii este daca secventa in care cautam este vida sau daca contine un singur element caz in care comparam acest element cu valoarea cautata.

//intoarce -1 daca nu a fost gasita valoarea si indexul din vector 
//daca valoarea a fost gasita
int cauta_binar(int v[], int start, int sfarsit, int a)
{
    if (start > sfarsit)
    {
        return -1;
    }
    if (start == sfarsit)
    {
        return (a==v[start])?start:-1;
    }
    int mijloc = (start+sfarsit)/2;
    if (a == v[mijloc])
    {
        return mijloc;
    }
    else if (a < v[mijloc])
    {
        return cauta_binar(v, start, mijloc-1, a);
    }
    else
    {
        return cauta_binar(v, mijloc+1, sfarsit, a);
    }
}

Daca avem un vector de numere intregi ordonate crescator si vrem sa cautam o valoare intreaga "a" putem face asa:

int v[100], n, a;
//citim n, cele n valori si valoarea de cautat a
int idx = cauta_binar(v, 0, n-1, a);
if (idx >= 0)
{
    cout<<"am gasit valoarea cautata pe pozitia "<<idx;
}
else
{
    cout<<"nu s-a gasit valoarea cautata";
}

Algoritmul de Interclasare

Algoritmul presupune interclasarea a doua colectii de obiecte ordonate crescator si scrierea rezultatului intr-o a treia colectie astfel incat colectia rezultata sa fie ordonata crescator si sa contina toate elementele din cele doua colectii initiale. Daca un element apare in ambele colectii atunci va aparea de doua ori in colectia rezultata.

In exemplul de mai jos este o functie C++ care ia ca argumente doi vectori de numere intregi ordonate crescator si interclaseaza cei doi vectori intr-un al treilea care este dat ca ultim argument functiei. Functia intoarce lungimea vectorului rezultat care este intotdeauna suma lungimilor celor doi vectori initiali. Ultimul argument al functiei este folosit ca parametru de iesire.

int Interclasare(int v1[], int n1, int v2[], int n2,
            int v[])
{
    int i = 0; // index pentru v1
    int j = 0; // index pentru v2
    int k = 0; // index pentru vectorul rezultat v

    // scriu in v cel mai mic numar dintr v1[i] si v2[j] si avansez cu indexul corespunzator
    while (i < n1 && j < n2)
    {
        if (v1[i] <= v2[j])
        {
            v[k] = v1[i];
            i++;
        }
        else
        {
            v[k] = v2[j];
            j++;
        }
        k++;
    }

    if (i < n1)
    {
        // scriu in v ce a mai ramas din v1
        for (; i < n1; i++)
        {
            v[k] = v1[i];
            k++;
        }
    }
    else if (j < n2)
    {
        // scriu in v ce a mai ramas din v2
        for (; j < n2; j++)
        {
            v[k] = v2[j];
            k++;
        }
    }

    return k;
}

Algoritmul de sortare "Selection Sort"

Algoritmul de "Sortare prin selectie" este un algoritm pentru sortarea in ordine crescatoare sau descrescatoare a unei colectii de obiecte. In exemplul de mai jos am folosit un vector de numere intregi.

Algoritmul consta in parcurgerea repetata a vectorului pe secvente din ce in ce mai mici si aducerea pe prima pozitie a secventei parcurse a minimului din aceasta secventa. La prima parcurgere se aduce pe prima pozitie a vectorului minimul dintre toate numerele, la a doua parcurgere (de la al doilea element pana la ultimul) se aduce pe a doua pozitie minimul dintre numerele de la pozitia a doua pana la ultimul. A treia parcurgere se face de la al treilea element pana la ultimul si minimul se aduce pe pozitia a treia s.a.m.d. Ultima parcurgere va compara doar ultimele doua elemente ale vectorului.

void SelectSort(int v[], int n)
{
    for (int i = 0; i < n-1; i++)
    {
        int minim = v[i];
        int indmin = i;

        for (int j = i+1; j < n; j++)
        {
            if (v[j] < minim)
            {
                indmin = j;
                minim = v[j];
            }
        }

        if (indmin != i)
        {
            int temp = v[i];
            v[i] = v[indmin];
            v[indmin] = temp;
        }
    }
}

Algoritmul de sortare "Bubble Sort"

Sortare inseamna ordonarea in ordine crescatoare sau descrescatoare a elementelor unei colectii. In exemplul de mai jos am folosit un vector de numere intregi.
Exista doua variante ale algoritmului, prima este cea clasica si a doua cea imbunatatita. Ideea algoritmului este de a parcurge colectia (vectorul) de numere de la stanga la dreapta si de a compara numarul curent cu cel de dupa el (v[i] cu v[i+1]). Daca primul numar este mai mic sau egal cu al doilea atunci algoritmul continua altfel se interschimba cele doua valori. Se parcurge colectia de numere atat timp cat exista cel putin o pereche de numere care urmeaza a fi interschimbate. Colectia se parcurge de la primul element pana la penultimul si se compara fiecare element cu cel de dupa el.

void bubblesort(int v[], int n)
{
    bool sortat = false;
 
    while (!sortat)
    {
        sortat = true;
        for (int i = 0; i <= (n-2); i++)
        {
            if (v[i] > v[i+1])
            {
                int temp = v[i];
                v[i] = v[i+1];
                v[i+1] = temp;
                sortat = false;
            }
        }
    }
}

A doua varianta se bazeaza pe faptul ca dupa fiecare parcurgere a colectiei se acumuleaza maximele incepand de la dreapta la stanga. Dupa prima parcurgere pe ultima pozitie a vectorului va fi maximul dintre toate numerele, dupa a doua parcurgere pe penultima pozitie va fi maximul dintre toate numerele mai putin maximul care se afla pe ultima pozitie, la a treia parcurgere pe antepenultima pozitie va fi maximul dintre numerele de la prima pozitie pana la antepenultima pozitie, s.a.m.d. Se observa ca nu mai este nevoie de o parcurgere completa a colectiei de fiecare data si este sufient ca la fiecare parcurgere sa inspectam un numar de numere mai mic cu unu. La prima parcurgere se inspecteaza n numere, apoi n-1 numere apoi n-2 numere s.a.m.d.

void bubblesort2(int v[], int n)
{
    bool sortat = true;
  
    for (int i = n-2; i >= 0; i--)
    {
        sortat = true;
        for (int j = 0; j <= i; j++)
        {
            if (v[j] > v[j+1])
            {
                int temp = v[j];
                v[j] = v[j+1];
                v[j+1] = temp;
                sortat = false;
            }
        }
      
        if (sortat)
        {
            break; // vectorul este sortat
        }
    }
}