Как исправить бинарный поиск для массива строк в C - PullRequest
Новая
       16

Как исправить бинарный поиск для массива строк в C

0 голосов
/ 26 апреля 2019

У меня есть программа на C, которая должна объединить 4 строковых массива, отсортировать этот новый список и затем найти фамилию, введенную пользователем. Это работает до нахождения фамилии; в нем говорится, что любая введенная фамилия отсутствует в списке, даже если она есть. 

printf("Please enter the surname you wish to find\n");
gets(sntbf);

while (lf <= rg) {
    p = lf + (rg - 1)/2;
    int q = strcmp(list[p], sntbf);

    if (q == 0) {
        printf("This surname is located at elemnent %d \n", p);
        z++;
    } else if (q < 0) {
        rg = p - 1;
    } else if(q>0) {
        lf = p + 1;
    }
}

if (z==0) {
    printf("This surname is not in the list \n");
}

Переменные и постоянные значения, размещен только один из исходных строковых массивов, остальные имеют идентичный формат 

#define SIZE 20
#define TOTAL 42

...... 

char list[TOTAL][SIZE];
char temp[SIZE];
char sntbf[SIZE];

//define miscellaneous integers to be used at various points of this program
int i = 0;
int j = 13;
int k = 27;
int l = 36;
int m = 0;
int n = 0;
int o = 0;
int lf = 0;
int rg = TOTAL-1;
int p;
int z = 0;

//define each class list as an array
char* a[13] = { "Harmon",
    "Farrell",
    "Ellison",
    "Mcknight",
    "Palmer",
    "Caldwell",
    "Mann",
    "Townsend",
    "Stuart",
    "Hull",
    "Pham",
    "Singleton",
    "Holden"
    };

.......

Вся программа: // Это программа, которая объединит 4 списка имен, сортировка этого нового список, а затем найти студента, выполнив поиск по фамилии #включают #include 

#define SIZE 20
#define TOTAL 42

int main() {

//define a 2d list array to hold the list of names and a temp array to be used when sorting, as well as a char array to hold the surname to be found
char list[TOTAL][SIZE];
char temp[SIZE];
char sntbf[SIZE];

//define miscellaneous integers to be used at various points of this program
int i = 0;
int j = 13;
int k = 27;
int l = 36;
int m = 0;
int n = 0;
int o = 0;
int lf = 0;
int rg = TOTAL-1;
int p;
int z = 0;

//define each class list as an array
char* a[13] = { "Harmon",
    "Farrell",
    "Ellison",
    "Mcknight",
    "Palmer",
    "Caldwell",
    "Mann",
    "Townsend",
    "Stuart",
    "Hull",
    "Pham",
    "Singleton",
    "Holden"
    };
char* b[14] = { "Hudson",
    "Harolds",
    "Christian",
    "Ware",
    "Benjamin",
    "Atkinson",
    "Mcpherson",
    "Michael",
    "Perez",
    "Austin",
    "Graves",
    "Hammond",
    "Barry",
    "Christensen"
    };
char* c[9] = { "Adkins",
    "Prince",
    "Collins",
    "Garrison",
    "Skinner",
    "Bean",
    "Gentry",
    "Chambers",
    "Armstrong"
    };
char* d[6] = { "Berg",
    "Douglas",
    "Novak",
    "Turner",
    "Love",
    "Fowler",
    };

//now merge all the lists into the list array
for(i=0; i<13; i++) {
    strcpy(list[i], a[i]);
}
i=0; //reset i to use it again as a counter 
for(i=0; i<14; i++) {
    strcpy(list[j], b[i]); 
    j++;
}
i=0;
for(i=0; i<9; i++) {
    strcpy(list[k], c[i]);
    k++;
}
i=0;
for(i=0; i<6; i++) {
    strcpy(list[l], d[i]);
    l++;
}

for(m=0; m<TOTAL-1; m++) {
    for(n=0; n<TOTAL; n++){
        if(strcmp(list[m], list[n])<0) {
            strcpy(temp, list[m]);
            strcpy(list[m], list[n]);
            strcpy(list[n], temp);
        }
    }
}

for(o=0; o<TOTAL; o++){
    puts(list[o]);
}

printf("Please enter the surname you wish to find\n");
gets(sntbf);

while (lf <= rg) {
    p = lf + (rg - 1)/2;
    int q = strcmp(list[p], sntbf);

    if(q = 0) {
        printf("This surname is located at elemnent %d \n", p);
        z ++;
    }
    else if(q < 0) {
        rg = p - 1;
    }
    else if(q > 0) {
        lf = p + 1;
    }
}
if(z == 0) {
    printf("This surname is not in the list \n");
}

return 0;
 }

1 Ответ

0 голосов
/ 26 апреля 2019

Есть ряд проблем с вашей программой, но первое, что я заметил, это то, что при копировании из списка a, который имеет 13 имен, ваш цикл for копирует только 12: 

for(i=0; i<12; i++) {
    strcpy(list[i], a[i]);
}

либо изменитеот «i <12» до «i <= 12» или «i <13». </p>

В идеале вы не должны использовать жестко закодированные числа вообще, вместо этого, если вы сделаете последний элемент в каждом из меньших списков NULL(0) вы можете использовать циклы while и использовать одну переменную int для представления как следующей точки вставки в объединенном списке, так и общего количества элементов в списке.Например: 

const char* a[] = 
{"Harmon","Farrell","Ellison","Mcknight","Palmer","Caldwell",
"Mann","Townsend","Stuart","Hull","Pham","Singleton","Holden",0 };
const char* b[] = {
"Hudson","Harolds","Christian","Ware","Benjamin","Atkinson",
"Mcpherson","Michael","Perez","Austin","Graves","Hammond",
"Barry","Christensen",0 };

int sourceIndex = 0;
int destIndex = 0;

while ( a[sourceIndex] != 0 )
{
    strcpy( list[destIndex], a[sourceIndex] );
    sourceIndex++;
    destIndex++;
}
sourceIndex = 0;
while ( b[sourceIndex] != 0 )
{
    strcpy( list[destIndex], b[sourceIndex] );
    sourceIndex++;
    destIndex++;
}

и т. Д.

Кроме того, ваш поиск обрабатывает границы (lf & rg) в обратном направлении и должен выглядеть следующим образом: 

lf = 0;
rg = destIndex - 1;

while (lf<=rg) {
    p = (rg + lf)/2;
    int q = strcmp(list[p], sntbf);

    if(q==0) {
        printf("This surname is located at elemnent %d \n", p);
        z++;
        break;
    }
    else if(q<0) {
        lf = p + 1;
    }
    else if(q>0) {
        rg = p - 1;
    }
}
if(z==0) {
    printf("This surname is not in the list \n");
}
...