recursion [Algoritmi si Tehnici de Programare - C] Cautare Liniara (In format Recursiv)

[NOT a MERCEDES]

** OBIECTIV ** 

VOM PROIECTA , IMPLEMENTA SI TESTA ALGORITMUL DE CAUTARE LINIARA , IN STIL RECURSIV SI GENERIC . 

** IMPLEMENTARE ALGORITM in C **

Antentul functiei de cautare LINIARA , va arat de forma : 

int linear_search_recursive(void* a, size_t bufferArr,size_t elementSize,void* searchedElement,int i , int (*genericCMP)(const void*,const void*)) 
{
}

• Colectia Generica "a" poate fi substituit de orice tip de date si reprezinta colectia pe care o primim de la tastatura ; 
• "bufferArr" reprezinta numarul total de elemente a colectiei ;
•  "elementSize" reprezinta dimensiunea , in biti , a unui element din colectie  . Asta ne asigura accesul la elementul generic ;
• "searchedElement" reprezinta elementul cautat , poarta tipul de date cu cel al elementelor colectiei ;
• "i" reprezinta indexul care se mareste o data cu apelul recursiv al functiei ;
• "genericCMP" reprezinta interfata de comparare a elementelor . Ea este substituita in functie de tipul de date a  elementelor pe care le comparam  ;
• RETURNAM INDEXUL LA CARE SE SITUEAZA ELEMENTUL CAUTAT , ASTA DACA EXISTA . DACA NU , RETURNAM -1 .

1. NE ASIGURAM CA MAI AVEM ELEMENTE IN COLECTIE .

  // 1. NE ASIGURAM CA MAI AVEM ELEMENTE IN COLECTIE 
        if(i >= bufferArr)
          return -1; // IN CAZUL ACESTA , NU AM GASIT ELEMENTUL CAUTAT IN COLECTIE 

2. EFECTUAM COMPARATIA INTRE ELEMENTUL CURENT AL COLECTIEI SI ELEMENTUL CAUTAT 

//2. TRIMITEM ADRESELE SPRE A COMPARA VALORILE ASOCIATE INTRE ELE !!
if(genericCMP((char*)a + i*elementSize,searchedElement))

 NOTA* : "(char*)a+i*elementSize" si "searchedElement" ==> SUNT ADRESE DE MEMORIE ASOCIATE ELEMENTELOR CARE URMEAZA SA FIE COMPARATE . (SE COMPARA VALORILE INTRE ELE , NICIDECUM ADRESELE DE MEMORIE !!!) .  

DACA ELEMENTELE SUNT EGALE (RETURNEAZA 1) , ATUNCI AM GASIT ELEMENTELUL CAUTAT  =>

{
return i; // Returnam indexul curent
}

DACA NU SUNT SIMILARE  , RETURNAM FUNCTIA RECURSIV MARIND INDEXUL CU VALOARE 1 

// 3. PARCURGEM COLECTIA RECURSIV 
return linear_search_recursive(a,bufferArr,elementSize,searchedElement,i+1,genericCMP);

IN FINAL , FUNCTIA VA ARATA IN FELUL URMATOR : 

int linear_search_recursive(void* a, size_t bufferArr,size_t elementSize,void* searchedElement,int i , int (*genericCMP)(const void*,const void*)) //RETURNAM INDEXUL ELEMENTULUI CAUTAT
        // 1. NE ASIGURAM CA MAI AVEM ELEMENTE IN COLECTIE 
{
        if(i >= bufferArr)
          return -1; // IN CAZUL ACESTA , NU AM GASIT ELEMENTUL CAUTAT IN COLECTIE 

        // Altfel , daca avem in elemente in colectie , CONTINUAM 

        // Verificam daca elementul de pe indexul curent este cel cautat

        if(genericCMP((char*)a + i*elementSize,searchedElement))  // DACA ESTE 1 ATUNCI AM GASIT ELEMENTUL CAUTAT 
           return i; // Return 

         // DACA NU L AM GASIT LA INDEXUL CURENT , MERGEM LA URMATORUL 

          return linear_search_recursive(a,bufferArr,elementSize,searchedElement,i+1,genericCMP);  

     }

 

 

ACUM , PUTEM EFECTUA OPERATIUNEA DE CAUTARE LINIARA PENTRU FIECARE TIP DE DATE , TOTUSI , VA TREBUIE SA PROIECTAM O INTERFATA DE CAUTARE PENTRU FIECARE TIP DE DATE  . 

De exemplu , interfata pentru numere intregi si reale va arata asa : 

// PENTRU FIECARE TIP DE DATE TREBUIE SA II FACEM CATE O INTERFATA SEPARATA 

int compareInt(const void* a,const void* b)  // FUNCTIE PENTRU COMPARAREA INTREGILOR 
{
    if(*(int*)a == *(int*)b)  // COMPARAM VALORILE ASOCIATE ADRESELOR DE MEMORIE
      return 1; // DACA E EGAL , RETURNAM 1 

       else 
       return 0;  // DACA NU E EGAL , RETURNAM 0 ; 

}

int compareFloat(const void* a , const void* b)  // FUNCTIE PENTRU COMPARAREA NUMERELOR REALE 
{
    if(*(float*)a == *(float*)b)
      return 1;

        else 
        return 0; 
}

 NOTA * : Pentru acest tutorial , vom folosi intregi dar pentru urmatoarele , voi folosi alte tipuri de date pentru o intelegere mai buna a functiilor generice !!! 

** TESTARE ** 

ACUM , O SA TESTAM ALGORITMUL FOLOSIND O COLECTIE DE NUMERE INTREGI PRELUATA DE LA TASTATURA : 

#include "stdio.h"
#include "stdlib.h"
  
// INTRODUCERE COLECTIE DE LA TASTATURA 
  
 int insertArray(int **arr)  // Returnam lungimea colectiei 
{
   // AM ALOCAT IN AFARA FUNCTIEI +1 element ca tot acest va deveni repetitiv 

	char yesOrNo;

   static int index = 1; // STATIC sa retinem indexu intre apelurile recursive a functiei 
	
	printf("Dati-mi un numar : ");
	scanf_s("%d",&(*arr)[index-1]); // Inseram un nou element in colectie de la tastatura


	printf("Continuam[y/n] ?");
	scanf_s(" %c", &yesOrNo,1); // Primim confirmarea de la utilizare de a continua sau nu inserarea 

	if (yesOrNo == 'n') // Daca nu continuam inserarea 
		 return 1; // Oprim algoritmul (1 si nu 0 deoarece luam in calcul si primul element al listei )


	else {
		index++;  // Indexu se mareste cu un element 
		*arr = realloc(*arr, index * sizeof(int)); // Realocam inca o zona de memorie 
		return 1 + insertArray(arr);  // Apelam din nou functia de inserare pentru noul element (++ adaugam un nou elemnt )
	}
}

  

int main()
    {
        int* a = (int*)malloc(sizeof(int)); // Declaram o colectie cu un element 
        int bufferArr = insertArray(&a);// Trimitem pointerul a prin adresa (VOM MODIFICA STRUCTRURA ACESTUIA IN FUNCTIE ) si 
	// ++ Vom returna lungimea finala in bufferArr
       
        int searchedNumber, searchedIndex;

        printf("\nINTRODUCETI NUMARUL CAUTAT : ");
        scanf("%d",&searchedNumber);

        // APELAM FUNCTIA DE CAUTARE LINIARA 
  
 
       // compareInt --> ESTE INTERFATA DE COMPARARE A NUMERELOR INTREGI (DEOARECE LUCRAM CU NUMERE INTREGI)
    
        if((searchedIndex = linear_search_recursive(a,bufferArr,sizeof(int),&searchedNumber,0,compareInt)) != -1)
            printf("AM GASIT ELEMENTUL CAUTAT LA INDEXUL %d !!",searchedIndex);
          else 
            printf("NU AM GASIT ELEMENTUL IN COLECTIE !! \n"); 

    free(a); // Eliberam Colectia in Sine 
    a = NULL; // Setam NULL Pointer 

    }

IN URMA TESTARII , VOM AVEA CA REZULTAT   :