C中的通用二进制搜索
Generic binary search in C
我为通用二进制搜索编写的这段代码遇到了问题。
当尝试对字符串数组执行搜索时，我注意到传递给 binSearch 函数的字符串数组不包含字符串。
有人可以提供提示吗？
非常感谢
#define SIZE 100
typedef unsigned char BYTE
请考虑这个主要的：
void main()
{
char ** stringArr, stringToFind[SIZE];
int stringSize;
int res;
stringArr = getStringArr(&stringSize);
// string to find
gets(stringToFind);
res = stringBinSearch(stringArr, stringSize, stringToFind);
if (res == 1)
printf("The string %s was found\n", stringToFind);
else
printf("The string %s was not found\n", stringToFind);
}
char** getStringArr(int* stringSize)
{
int i, size, len;
char** arr;
char temp[SIZE];
scanf("%d", &size);
getchar();
arr = (char**)malloc(size * sizeof(char*));
checkAllocation(arr);
for (i = 0; i < size; i++)
{
gets(temp);
len = strlen(temp);
temp[len] = '[=11=]';
arr[i] = (char*)malloc((len+1) * sizeof(char));
checkAllocation(arr[i]);
strcpy(arr[i], temp);
}
*stringSize = size;
return arr;
}
int stringBinSearch(char** stringArr, int stringSize, char* stringToFind)
{
return binSearch(stringArr, stringSize, sizeof(char*), stringToFind,compare2Strings);
}
int binSearch(void* Arr, int size, int ElemSize, void* Item, int(*compare)(void*, void*))
{
int left = 0, right = size - 1, place;
BOOL found = FALSE;
while (found == FALSE && left <= right)
{
place = (left + right) / 2;
if (compare(Item, (BYTE*)Arr + place*ElemSize) == 0)
found = TRUE;
else if (compare(Item, (BYTE*)Arr + place*ElemSize) < 0)
right = place - 1;
else
left = place + 1;
}
return found;
}
int compare2Strings(void* str1, void* str2)
{
char* elemA, *elemB;
elemA = (char*)str1;
elemB = (char*)str2;
return strcmp(elemA, elemB);
}
您编写通用二进制搜索的方法是正确的。但是，尽早尝试 return 会减慢二进制搜索的速度。这也意味着您不能使用 "less than" 是定义的比较运算符的 C++ 约定。等到左右相等，return即
您好，您的问题是您将字符串数组发送到二进制搜索函数的方式。因为您需要将一个字符串数组传递给它，所以您的 Arr 参数必须是 void** 而不是 void*
int binSearch(void** Arr, int size, int ElemSize, void* Item, int(*compare)(void*, void*))
在你的函数中，每当你想从你的数组中访问一个字符串时，像这样访问它就足够了：(char*) *(Arr+place*ElemSize)
当您对 int 的数组进行排序时，传递的值是指向 int 的指针，拼写为 int *。当您对字符串数组（拼写为 char *）进行排序时，传递的值是指向字符串的指针，拼写为 char **。您的比较器无法用于比较字符串。由于无与伦比的 BLUEPIXY 具有令人难以置信的简洁风格 — 您需要修改代码以将传递的 void * 参数视为 char ** 而不是 char *.
使用一般排序，问题通常就到此为止了。使用二进制搜索，还有另一个问题是您 运行 犯规的。那就是要搜索的项的类型需要与数组中的一项相同，所以你需要传递一个指向项的指针，而不仅仅是项。
因此，添加 material 以允许代码以最小的更改进行编译，从 gets() 更改为 fgets() 的封面（因为 gets() is too dangerous to be used — ever! 和使用的程序它在 macOS Sierra 10.12.5 上使用时会产生警告 — warning: this program uses gets(), which is unsafe.)，并打印出输入数据，以便您查看是什么，我最终得到：
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define BOOL int
#define TRUE 1
#define FALSE 0
static inline char *sgets(size_t buflen, char *buffer)
{
char *result = fgets(buffer, buflen, stdin);
if (result)
buffer[strcspn(buffer, "\n")] = '[=10=]';
return result;
}
#define checkAllocation(x) assert((x) != 0)
#define SIZE 100
typedef unsigned char BYTE;
char **getStringArr(int *stringSize);
int stringBinSearch(char **stringArr, int stringSize, char *stringToFind);
int binSearch(void *Arr, int size, int ElemSize, void *Item, int (*compare)(void *, void *));
int compare2Strings(void *str1, void *str2);
int main(void)
{
char **stringArr, stringToFind[SIZE];
int stringSize;
int res;
stringArr = getStringArr(&stringSize);
sgets(sizeof(stringToFind), stringToFind);
printf("Strings: %d\n", stringSize);
for (int i = 0; i < stringSize; i++)
printf("[%d] = [%s]\n", i, stringArr[i]);
printf("Search: [%s]\n", stringToFind);
res = stringBinSearch(stringArr, stringSize, stringToFind);
if (res == 1)
printf("The string %s was found\n", stringToFind);
else
printf("The string %s was not found\n", stringToFind);
return 0;
}
char **getStringArr(int *stringSize)
{
int i, size, len;
char **arr;
char temp[SIZE];
scanf("%d", &size);
getchar();
arr = (char **)malloc(size * sizeof(char *));
checkAllocation(arr);
for (i = 0; i < size; i++)
{
sgets(sizeof(temp), temp);
len = strlen(temp);
temp[len] = '[=10=]';
arr[i] = (char *)malloc((len + 1) * sizeof(char));
checkAllocation(arr[i]);
strcpy(arr[i], temp);
}
*stringSize = size;
return arr;
}
int stringBinSearch(char **stringArr, int stringSize, char *stringToFind)
{
return binSearch(stringArr, stringSize, sizeof(char *), &stringToFind, compare2Strings);
}
int binSearch(void *Arr, int size, int ElemSize, void *Item, int (*compare)(void *, void *))
{
int left = 0, right = size - 1, place;
BOOL found = FALSE;
while (found == FALSE && left <= right)
{
place = (left + right) / 2;
if (compare(Item, (BYTE *)Arr + place * ElemSize) == 0)
found = TRUE;
else if (compare(Item, (BYTE *)Arr + place * ElemSize) < 0)
right = place - 1;
else
left = place + 1;
}
return found;
}
int compare2Strings(void *str1, void *str2)
{
char *elemA = *(char **)str1;
char *elemB = *(char **)str2;
return strcmp(elemA, elemB);
}
主要变化是：
compare2Strings() — 比较 char ** 值中的数据。stringBinSearch() — 传递 stringToFind.
AFAICR，任何其他更改都是装饰性的或 'infrastructure'。
请注意 the return type of main() should be int — 您只能在允许的 Windows 上使用 void。
示例运行 1:
数据：
5
Antikythera
albatross
armadillo
pusillanimous
pygmalion
pygmalion
输出：
Strings: 5
[0] = [Antikythera]
[1] = [albatross]
[2] = [armadillo]
[3] = [pusillanimous]
[4] = [pygmalion]
Search: [pygmalion]
The string pygmalion was found
示例运行 2:
数据文件：
5
armadillo
pygmalion
Antikythera
pusillanimous
albatross
pygmalion
输出：
Strings: 5
[0] = [armadillo]
[1] = [pygmalion]
[2] = [Antikythera]
[3] = [pusillanimous]
[4] = [albatross]
Search: [pygmalion]
The string pygmalion was not found
两组数据的不同之处在于，在第一种情况下，字符串的排序顺序正确——这是成功（可靠）二分查找的先决条件——而在第二种情况下，数据不正确排序顺序。 （也就是说，我有一个未排序的订单仍然找到 'pygmalion' — 我对显示的结果使用了不同的洗牌。但是 'reliable' 注释适用。）
我为通用二进制搜索编写的这段代码遇到了问题。 当尝试对字符串数组执行搜索时，我注意到传递给 binSearch 函数的字符串数组不包含字符串。
有人可以提供提示吗？
非常感谢
#define SIZE 100
typedef unsigned char BYTE
请考虑这个主要的：
void main()
{
char ** stringArr, stringToFind[SIZE];
int stringSize;
int res;
stringArr = getStringArr(&stringSize);
// string to find
gets(stringToFind);
res = stringBinSearch(stringArr, stringSize, stringToFind);
if (res == 1)
printf("The string %s was found\n", stringToFind);
else
printf("The string %s was not found\n", stringToFind);
}
char** getStringArr(int* stringSize)
{
int i, size, len;
char** arr;
char temp[SIZE];
scanf("%d", &size);
getchar();
arr = (char**)malloc(size * sizeof(char*));
checkAllocation(arr);
for (i = 0; i < size; i++)
{
gets(temp);
len = strlen(temp);
temp[len] = '[=11=]';
arr[i] = (char*)malloc((len+1) * sizeof(char));
checkAllocation(arr[i]);
strcpy(arr[i], temp);
}
*stringSize = size;
return arr;
}
int stringBinSearch(char** stringArr, int stringSize, char* stringToFind)
{
return binSearch(stringArr, stringSize, sizeof(char*), stringToFind,compare2Strings);
}
int binSearch(void* Arr, int size, int ElemSize, void* Item, int(*compare)(void*, void*))
{
int left = 0, right = size - 1, place;
BOOL found = FALSE;
while (found == FALSE && left <= right)
{
place = (left + right) / 2;
if (compare(Item, (BYTE*)Arr + place*ElemSize) == 0)
found = TRUE;
else if (compare(Item, (BYTE*)Arr + place*ElemSize) < 0)
right = place - 1;
else
left = place + 1;
}
return found;
}
int compare2Strings(void* str1, void* str2)
{
char* elemA, *elemB;
elemA = (char*)str1;
elemB = (char*)str2;
return strcmp(elemA, elemB);
}
您编写通用二进制搜索的方法是正确的。但是，尽早尝试 return 会减慢二进制搜索的速度。这也意味着您不能使用 "less than" 是定义的比较运算符的 C++ 约定。等到左右相等，return即
您好，您的问题是您将字符串数组发送到二进制搜索函数的方式。因为您需要将一个字符串数组传递给它，所以您的 Arr 参数必须是 void** 而不是 void*
int binSearch(void** Arr, int size, int ElemSize, void* Item, int(*compare)(void*, void*))
在你的函数中，每当你想从你的数组中访问一个字符串时，像这样访问它就足够了：(char*) *(Arr+place*ElemSize)
当您对 int 的数组进行排序时，传递的值是指向 int 的指针，拼写为 int *。当您对字符串数组（拼写为 char *）进行排序时，传递的值是指向字符串的指针，拼写为 char **。您的比较器无法用于比较字符串。由于无与伦比的 BLUEPIXY void * 参数视为 char ** 而不是 char *.
使用一般排序，问题通常就到此为止了。使用二进制搜索，还有另一个问题是您 运行 犯规的。那就是要搜索的项的类型需要与数组中的一项相同，所以你需要传递一个指向项的指针，而不仅仅是项。
因此，添加 material 以允许代码以最小的更改进行编译，从 gets() 更改为 fgets() 的封面（因为 gets() is too dangerous to be used — ever! 和使用的程序它在 macOS Sierra 10.12.5 上使用时会产生警告 — warning: this program uses gets(), which is unsafe.)，并打印出输入数据，以便您查看是什么，我最终得到：
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define BOOL int
#define TRUE 1
#define FALSE 0
static inline char *sgets(size_t buflen, char *buffer)
{
char *result = fgets(buffer, buflen, stdin);
if (result)
buffer[strcspn(buffer, "\n")] = '[=10=]';
return result;
}
#define checkAllocation(x) assert((x) != 0)
#define SIZE 100
typedef unsigned char BYTE;
char **getStringArr(int *stringSize);
int stringBinSearch(char **stringArr, int stringSize, char *stringToFind);
int binSearch(void *Arr, int size, int ElemSize, void *Item, int (*compare)(void *, void *));
int compare2Strings(void *str1, void *str2);
int main(void)
{
char **stringArr, stringToFind[SIZE];
int stringSize;
int res;
stringArr = getStringArr(&stringSize);
sgets(sizeof(stringToFind), stringToFind);
printf("Strings: %d\n", stringSize);
for (int i = 0; i < stringSize; i++)
printf("[%d] = [%s]\n", i, stringArr[i]);
printf("Search: [%s]\n", stringToFind);
res = stringBinSearch(stringArr, stringSize, stringToFind);
if (res == 1)
printf("The string %s was found\n", stringToFind);
else
printf("The string %s was not found\n", stringToFind);
return 0;
}
char **getStringArr(int *stringSize)
{
int i, size, len;
char **arr;
char temp[SIZE];
scanf("%d", &size);
getchar();
arr = (char **)malloc(size * sizeof(char *));
checkAllocation(arr);
for (i = 0; i < size; i++)
{
sgets(sizeof(temp), temp);
len = strlen(temp);
temp[len] = '[=10=]';
arr[i] = (char *)malloc((len + 1) * sizeof(char));
checkAllocation(arr[i]);
strcpy(arr[i], temp);
}
*stringSize = size;
return arr;
}
int stringBinSearch(char **stringArr, int stringSize, char *stringToFind)
{
return binSearch(stringArr, stringSize, sizeof(char *), &stringToFind, compare2Strings);
}
int binSearch(void *Arr, int size, int ElemSize, void *Item, int (*compare)(void *, void *))
{
int left = 0, right = size - 1, place;
BOOL found = FALSE;
while (found == FALSE && left <= right)
{
place = (left + right) / 2;
if (compare(Item, (BYTE *)Arr + place * ElemSize) == 0)
found = TRUE;
else if (compare(Item, (BYTE *)Arr + place * ElemSize) < 0)
right = place - 1;
else
left = place + 1;
}
return found;
}
int compare2Strings(void *str1, void *str2)
{
char *elemA = *(char **)str1;
char *elemB = *(char **)str2;
return strcmp(elemA, elemB);
}
主要变化是：
compare2Strings()— 比较char **值中的数据。stringBinSearch()— 传递stringToFind. 的地址
AFAICR，任何其他更改都是装饰性的或 'infrastructure'。
请注意 the return type of main() should be int — 您只能在允许的 Windows 上使用 void。
示例运行 1:
数据：
5
Antikythera
albatross
armadillo
pusillanimous
pygmalion
pygmalion
输出：
Strings: 5
[0] = [Antikythera]
[1] = [albatross]
[2] = [armadillo]
[3] = [pusillanimous]
[4] = [pygmalion]
Search: [pygmalion]
The string pygmalion was found
示例运行 2:
数据文件：
5
armadillo
pygmalion
Antikythera
pusillanimous
albatross
pygmalion
输出：
Strings: 5
[0] = [armadillo]
[1] = [pygmalion]
[2] = [Antikythera]
[3] = [pusillanimous]
[4] = [albatross]
Search: [pygmalion]
The string pygmalion was not found
两组数据的不同之处在于，在第一种情况下，字符串的排序顺序正确——这是成功（可靠）二分查找的先决条件——而在第二种情况下，数据不正确排序顺序。 （也就是说，我有一个未排序的订单仍然找到 'pygmalion' — 我对显示的结果使用了不同的洗牌。但是 'reliable' 注释适用。）