Rekursive lineare Suche in C debug

Question

Problem: 1 In diesem Code, wenn ich eine Nummer suchen, die nicht in Array ist, sollte es Value not found anzeigen, aber ich weiß nicht, es zeigt nicht diese Nachricht stattdessen jedes Mal zeigt es Found value in element -5 ich nicht habe eine Ahnung, warum es passiert.

#include<stdio.h> 
#define SIZE 100 

size_t linearSearch(const int array[], int key, size_t size); 

int main(void) 
{ 

    int a[SIZE]; 
    size_t x; 
    int searchKey; 
    size_t element; 


    for(x=0; x<SIZE; ++x){ 
     a[x] = 2*x; 
    } 

    for(x=0; x<SIZE; ++x){ 
     if(x%10 == 0){ 
      puts(""); 
     } 
     printf("%5d", a[x]); 
    } 

    puts("\n\nEnter integer search key:"); 
    scanf("%d", &searchKey); 

    // attempt to locate searchKey in array a 
    element = linearSearch(a, searchKey, SIZE); 

    // display results 
    if(element != -1){ 
     printf("Found value in element %d", element); 
    } 
    else{ 
     puts("Value not found"); 
    } 
} 

size_t linearSearch(const int array[], int key, size_t size) 
{ 
    if(size<0){ 
     return -1; 
    } 
    if(key == array[size-1]){ 
     return size-1; 
    } 
    return linearSearch(array, key, size-1); 

} 

Problem: 2

kann ich nicht verstanden, wie

size_t linearSearch (const int array [], int key, size_t size)

Funktion speziell Arbeits diese Linie

if(key == array[size-1]){ 
     return size-1; 
return linearSearch(array, key, size-1); 

Answer 1

Wie jeder gesagt, dass Sie einen kleinen Fehler haben, der ist, sollten Sie schreiben if(size==0) nicht if(size<0).

lassen Sie mich erklären, was rekursiv in linearSearch() Funktion los ist

size_t linearSearch(const int array[], int key, size_t size) 
{ 
    if(size == 0){ 
     return -1; 
    } 
    else 
     if(key == array[size-1]){ 
      return size-1; 
    } 
    else{ 
     return linearSearch(array, key, size-1); 
    } 
} 

Angenommen, Sie einen Eingang gab 198 als Suchschlüssel. Wenn Sie Aufruf linearSearch() Funktion durch die Aussage

element = linearSearch(a, searchKey, SIZE); 

Sie Verweis auf array[], searchKey 198, and Size 100 als Argument übergeben werden.

In linearSearch Funktion if-Anweisung if(size==0) prüft zunächst, ob die Größe auf Null, wenn nicht dann else if-Anweisung ausgeführt gleich ist.

in else if-Anweisung If(198 == array[100-1]) Zustand überprüft wird. und wir sehen 198 in array[99] vorhanden ist, so dass die sonst, wenn die Bedingung so wahr ist linearSearch Funktion, um die 99 als Ergebnis zurück.

können nun sehen, was passiert, wenn Sie Eingabe 55, die nicht in der Array-Liste ist. if (size == 0) ist nicht wahr, so dass das Programm es überspringt und zur nächsten Anweisung geht. if(55 == array[100-1] wird als nicht wahr ist, dann überprüft werden linearSearch(array, 55, 100-1) aufgerufen wird. wieder if(55==array[99-1]) wird überprüft werden. irgendwann Größe wird 0 und die erste if(size==0) Anweisung wird ausgeführt.

Answer 2

1) Das Hauptproblem ist . Bedingter Ausdruck ist immer falsch. weil size_t eine vorzeichenlose Ganzzahl ist. So gibt es eine zufällige Position mit den gefundenen Werten (Es ist undefiniertes Verhalten) zufällig eine große Zahlen (z. B. -5 ist 4294967291 als unsigned) ohne Ende (nicht gefunden).

if(size<0){ sollte if(size==0){

2) seine Position Wenn die Taste Spiel das letzte Element, zurückgibt. Wenn nicht, mit einer kürzeren Größe wiederholen. Schlüssel nicht gefunden, wenn die Größe Null ist.

Answer 3

Ändern Sie einfach die if-Anweisung von if(size<0) zu if(size==0) Ihr Code wird funktionieren.