[Algoritmi și Tehnici de Programare - C] Căutare Liniară (În format Recursiv)

[Soulrayne]

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   : 

 

Edited yesterday at 04:13 PM by Soulrayne