Structuri de date si algoritmi
Nitu Madalin
  • Junior Member
  • 2 Posts

As dori sa postez pe acest forum diferite implementari ale algoritmilor si structurilor de date in C++. Sper sa va distrati in minunatea si sucita lume a informatici :))

Nitu Madalin
  • Junior Member
  • 2 Posts

Aici urmeaza si prima parte :) si desigur nu poate fi nimic alta decat metode de ordonare si cautare :) desigur uzuale , nu complexe precum un Heap cu arbori ori arbori de echivalenta :) (P.S: O sa urmeze si aceia :)) ) Deci ce mai incolo si incoace aici e codul, i-am facut generici pentru a putea fi folositi pentru orice tip de data :) (In cazul in care nu sunteti obisnuiti cu notatiile generice puteti accesa o functie de mai jos asa : Bubble_Sort<int>(myVector,nr_elemente) ori insa nu e recomandat in unele compilatoare  Bubble_Sort(myVector,nr_elemente) , aici tipul generic find inlocuit cu tipul de data al lui myVector).

 

#include<iostream>

using namespace std;

//----------Enunt 1. Ordonare crescator (Bubble_Sort)
template<typename T>    //tip generic pentru substituire tipul de data al vector
void Bubble_Sort(T *v,int n)
{
    for(int i = 0;i<n;i++)
        for(int j = i+1;j<n-1;j++)
            if(v[i]>v[j])    //adevarat interschimba
            {
                T aux = v[i];
                v[i] = v[j];
                v[j] = aux;
            }
}

//---------Enunt 2. Ordonare crescator (Insertion_sort)
template<typename T>     //tip generic pentru substituire tipul de data al vector
void Insertion_sort(T *v,int n)
{
    int i,j;
    T x;
    for(i = 1;i< n ;i++)
    {
        x  = v[i];    //valoare de verificat
        j = i-1;    //indicele valori
        while((j>=0)&&(x<v[j]))    //cat timp indicele nu e 0 si valoarea e mai mica decat 
        {                        //valorile din finalul vectorului
            v[j+1] = v[j];        //le mut pe pozitiile din fata
            j--;                //scad indicele valori de verificat
        }
        v[j+1] = x;                //indicele lui j+1 este o dublura din cauza mutari la dreapta din while
    }                            //asa ca punem maximul 'x' acolo
}

//--------Enunt 3. Ordonare crescator (Select_sort)
template<typename T>    //tip generic pentru substituire tipul de data al vector
void Select_sort(T *v,int n)
{
    int i,j,k;                //variabile index
    T min;                    //variabila max
    for(i = 0;i<=n-1;i++)    
    {
        k = i;                //indice min
        min = v[i];            //minimul trebuie sa fie pe pozitiile din stanga
        for(j = i+1;j<n;j++)//se cauta iterativ in continuarea vectorului
        {    
            if(v[j]<min)    //daca min este mai mare decat urmatoarele elemente
            {
                k = j;        //salvam indicele
                min = v[j];    //si min
            }
        }
        v[k] = v[i];    //valoarea lui v[k] este salvata in min asa ca 
        v[i] = min;        //le interschimbam min cu valoarea din vector urmatoare care e mai
    }                    //mica
}

//--------Enunt 4. Cautare secventionala (Search_iterativ)
template<typename T>    //tip generic pentru substituire tipul de data al vector
int Search_iterativ(T *v,int n,T val)
{
    for(int i = 0;i<n;i++)
        if(v[i]==val)
            return i;    //returneaza indicele unde se afla val in vector
    return -1;        //returneaza -1 daca nu e val in vector
}

template<typename T>    //tip generic pentru substituire tipul de data al vector
int Search_recursiv(T *v,int left,int right,T val)
{
    if((left == right - 1)&&v[left]!=val)    //se verifica daca sa terminat de cautat si daca ultima valoare
        return -1;                            //nu e cea cautata
    else if((left == right-1)&&v[left]==val)//se verifica daca ultima valoare e cea cautata
        return left;                    //returneaza indicele in caz favorabil
    if(left != right)                    //daca nu sa terminat de cautat
    {
        if(v[left]==val)                   //se verifica daca e valoarea de cautat
            return left;                //caz favorabil se returneaza indicele
        else
            return Search_recursiv(v,left+1,right,val);    //se returneaza recursiv urmatorul indice de cautat
    }
}

//---------Enunt 5. Cautare binara (Binary_search)
template<typename T>     //tip generic pentru substituire tipul de data al vector
int Binary_search(T *v,int left,int right,T val)
{
    if(val>v[right])    //daca valoarea de cautat e mai mare decat ultimul element 
        return -1;        //al vectorului atunci returneaza -1
    else if(val<v[left])//daca valoarea de cautat e mai mica decat primul
        return -1;        //element al vectorului returneaza -1
    else
    {
        if(left == right) // daca e ultimul element de cautat
        {
            if(v[left]==val)//si acesta este val
                return left;//returneaza indicele
            else
                return -1;//daca nu -1
        }
        else
        {
            int m = (left+right)/2; //daca nu sa ajuns la ultimul element 
            if(v[m]==val)        //se verifica mijlocul
                return m;        //daca acesta e val returneaza pozitia
            else if(v[m]<val)    //daca e mai mare val decat mijlocul
                return Binary_search(v,m+1,right,val);//returneaza recursiv cautarea in jumatatea din dreapta
            else
                return Binary_search(v,left,m-1,val); //returneaza recursiv cautarea in jumatatea in stanga
        }
    }
}

template<typename T>    //tip generic pentru substituire tipul de data al vector
int Binary_iterativ(T *v,int n,T val)
{
    if(val<v[0])    //daca val e mai mic decat primul element 
        return -1;    //returneaza -1
    if(val>v[n-1])    //daca val e mai mare decat ultimul element 
        return -1;    //returneaza -1

    int left,right,m;
    left= 0;    
    right = n;
    while(left<right) //cat timp mai sunt elemente de cautat
    {
        m = (left+right)/2; //mijlocul
        if(v[m] == val)    //valoarea din mijloc e val
            return m;    //returneaza indicele
        else if(v[m]<val)    //daca mijloc e mai mica decat val
            left = m;    //se cauta in partea dreapta
        else
            right = m; //se cauta in partea stanga
    }
    return -1; //daca nu sa returnat nimic in while inseamna ca nu e in
}                //vector asa ca returnam -1
 

Stefanescu Mihai
  • Keymaster
  • 54 Posts
Facebook account Twitter account Google plus account LinkedIn account

Multumim frumos Nitu Madalin, poate va mai intalni cineva o problema asemanatoare si se va ajuta folosind codul tau.

Edit

//-----

Acum am observat ca lipseste butonul de cod in editor, am sa-l pun diseara :)


Trebuie sa fii inregistrat sau autentificat pentru a posta!