c - 如何修复 C 中字符串数组的二分搜索

Question

我有一个 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 个名称列表，并对新的列表进行排序 列表，然后通过搜索姓氏找到学生 ＃包括 #包括

#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;
 }

Answer 1

您的程序存在许多问题，但我注意到的第一件事是，当从具有 13 个名称的列表 a 进行复制时，您的 for 循环仅复制 12 个:

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

将“i<12”更改为“i <= 12”或“i < 13”。

理想情况下，您根本不会使用硬编码数字，相反，如果您将每个较小列表中的最后一个元素设置为 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");
}