如何在c中正确使用bsearch？
How to use bsearch correctly in c?
我想在日期数组中搜索一个日期（它是一个结构），看看它是否在其中。这是我第一次使用 bsearch，它总是 return 相同的结果 0，而它应该 return null 或指向找到日期的指针。我正在使用我用来对数组进行排序的相同比较函数，并且排序工作正常。我猜函数 returns 0 是否意味着它已经在数组中找到了日期。我做错了什么？如果错误不明显，我可以 post 完整代码。
#define MIN_SIZE 0
#define MAX_SIZE 10000
#define MAX_MONTH_STR 9
#define SWAP 1
#define NO_SWAP -1
#define EQUAL 0
//Define a struct data type
typedef struct
{
//Declaration of struct members
char* month;
int day;
int year;
}date;
//Method to allocate memory for a list of date structures
date* allocateStruct(int size)
{
//Declaration of variables
date *array;
int i;
//Allocate memory for array to store 'size' many 'date' struct data types
array = malloc(size*sizeof(date));
//For-loop to allocate memory for each struct's members and initialize them to zero
for (i=0; i<size; i++)
{
array[i].month = calloc(MAX_MONTH_STR,sizeof(char));
array[i].day = (int) calloc(1,sizeof(int));
array[i].year = (int) calloc(1,sizeof(int));
}
return array;
}
//Method to free memory allocated
void freeStruct(date* array, int size)
{
//Declaration of variable
int i;
//For-loop to free up struct members
for (i=0; i<size; i++)
{
free(array[i].month);
free(&array[i].day);
free(&array[i].year);
}
//Free up structs
free(array);
}
//Method to compare two dates
int cmpDates (const void *a, const void *b)
{
//Declaration and dereference of variables
date first = *(date*)a;
date second = *(date*)b;
int y_result, m_result, d_result;
//Calculate results
y_result = second.year-first.year;
m_result = second.month-first.month;
d_result = second.day-first.day;
//If-statements to determine whether to swap dates based on year
//If-statement to determine whether both years are in 90s group
if (first.year>=90 && first.year<=99 && second.year>=90 && second.year<=99)
{
//If-statement to determine whether years are equal
if (y_result!=0)
{
return (y_result);
}
}
//Else-if-statement to determine whether both years are in 00-12 group
else if (first.year>=0 && first.year<=12 && second.year>=0 && second.year<=12)
{
//If-statement to determine whether years are equal
if (y_result!=0)
{
return (y_result);
}
}
//Otherwise the two years belong to different year groups
else
{
//If-statement to determine whether first year belongs to 00-12 group
if (first.year>=0 && first.year<=12)
{
return NO_SWAP;
}
else
{
return SWAP;
}
}
//If-statement to determine whether to swap dates based on months
if (m_result!=0)
{
return m_result;
}
//If-statement to determine whether to swap dates based on days
if (d_result!=0)
{
return d_result;
}
//If dates are exactly the same
return EQUAL;
}
enum months {
January=1,
February,
March,
April,
May,
June,
July,
August,
September,
October,
November,
December
};
int main()
{
//Declaration of variables
int n; //number of dates in array
date* date_list; //array of dates
date *key_date; //date to search for
date *q_result; //result of search
//Read input
do
{
//printf("Enter number of dates you want to enter (between 1 and 10000):\n");
scanf("%d", &n);
}while(n<MIN_SIZE || n>MAX_SIZE);
//Allocate memory for an array of n dates
date_list = allocateStruct(n);
//For-loop to store values in 'date_list'
for (i=0; i<n; i++)
{
//printf("Enter the date (month day year) in the following format <text number number>:");
scanf("%s", date_list[i].month);
scanf("%d", &date_list[i].day);
scanf("%d", &date_list[i].year);
}
//Allocate memory for one date
key_date = allocateStruct(1);
//Read date for query
//printf("Enter date you want to query:");
scanf("%s", key_date->month);
scanf("%d", &key_date->day);
scanf("%d", &key_date->year);
//Sort the array with built-in function qsort
qsort(date_list, n, sizeof(date), cmpDates);
//Print list of sorted dates
for (i=0; i<n; i++)
{
//printf("Enter the date (month day year) in the following format: text number number");
printf("%s ", date_list[i].month);
printf("%d ", date_list[i].day);
printf("%02d\n", date_list[i].year); //need & ?
}
//Query with bsearch --> I TRIED BOTH OF THESE LINES BUT THE RESULT WAS THE SAME
q_result = (date*) bsearch(&key_date, date_list, n, sizeof(date), cmpDates);
// q_result = bsearch(&key_date, date_list, n, sizeof(date), cmpDates);
//Printing answer to query
if(q_result!=NULL)
{
printf("Yes in list");
}
else
{
printf("No not in list");
}
}
key_date 是一个指针，但是你将它的地址传递给 bsearch 所以当 cmpDates 被调用时，它会尝试转换（重新解释）一个 void* 这是一个 date** 到 date*，然后将其取消引用到 date。显然，从 date 结构中检索到的值都是错误的。我很惊讶你没有遇到月份字符串的崩溃。
q_result = (date*) bsearch(&key_date, date_list, n, sizeof(date), cmpDates);
应该是
q_result = (date*) bsearch(key_date, date_list, n, sizeof(date), cmpDates);
显然，您仍然需要解决（无双关语）calloc 问题
for (i=0; i<size; i++)
{
array[i].month = calloc(MAX_MONTH_STR,sizeof(char));
array[i].day = (int) calloc(1,sizeof(int));
array[i].year = (int) calloc(1,sizeof(int));
}
应该是（如果你真的需要把月份作为一个字符串）
for (i=0; i<size; i++)
{
array[i].month = calloc(MAX_MONTH_STR,sizeof(char));
array[i].day = 0;
array[i].year = 0;
}
然后
for (i=0; i<size; i++)
{
free(array[i].month);
free(&array[i].day);
free(&array[i].year);
}
应该是
for (i=0; i<size; i++)
{
free(array[i].month);
}
关于你的月份比较，你需要这样的函数：
months GetMonth(char* m)
{
if (strcmp(m, "January") == 0)
return months.January;
else if (strcmp(m, "February") == 0)
return months.February;
....
}
我忽略了区分大小写。
然后将此枚举存储在日期结构中，月份比较至少有意义。
这是我根据您的代码组装的代码，似乎可以正常工作。我没有对其进行压力测试。
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#define MIN_SIZE 1
#define MAX_SIZE 10000
#define MAX_MONTH_STR 10
#define EQUAL 0
#define LESS_THAN -1
#define MORE_THAN +1
typedef struct
{
char *month;
int day;
int year;
} date;
static
date *allocateStruct(int size)
{
date *array = malloc(size * sizeof(date));
if (array == 0)
exit(1);
for (int i = 0; i < size; i++)
{
array[i].month = calloc(MAX_MONTH_STR, sizeof(char));
if (array[i].month == 0)
exit(1);
}
return array;
}
static
void freeStruct(date *array, int size)
{
for (int i = 0; i < size; i++)
{
free(array[i].month);
}
free(array);
}
static inline int normalize_year(int year)
{
return (year < 50) ? year + 2000 : year + 1900;
}
static inline int month_number(const char *name)
{
static const char *months[] =
{
"",
"January", "February", "March", "April", "May", "June",
"July", "August", "September", "October", "November", "December",
};
for (int i = 1; i <= 12; i++)
if (strcmp(name, months[i]) == 0)
return i;
fprintf(stderr, "Invalid (unrecognized) month name <<%s>>\n", name);
exit(1);
/*NOTREACHED*/
}
static
int cmpDates(const void *a, const void *b)
{
date first = *(date *)a;
date second = *(date *)b;
int y1 = normalize_year(first.year);
int y2 = normalize_year(second.year);
if (y1 < y2)
return LESS_THAN;
else if (y1 > y2)
return MORE_THAN;
int m1 = month_number(first.month);
int m2 = month_number(second.month);
if (m1 < m2)
return LESS_THAN;
else if (m1 > m2)
return MORE_THAN;
if (first.day < second.day)
return LESS_THAN;
else if (first.day > second.day)
return MORE_THAN;
else
return EQUAL;
}
int main(void)
{
int n;
date *date_list;
date *key_date;
date *q_result;
do
{
if (scanf("%d", &n) != 1)
exit(1);
} while (n < MIN_SIZE || n > MAX_SIZE);
date_list = allocateStruct(n);
printf("Input data:\n");
for (int i = 0; i < n; i++)
{
scanf("%s", date_list[i].month);
scanf("%d", &date_list[i].day);
scanf("%d", &date_list[i].year);
printf("%.2d: %.2d %s %.2d\n", i, date_list[i].day, date_list[i].month, date_list[i].year);
}
qsort(date_list, n, sizeof(date), cmpDates);
printf("Sorted:\n");
for (int i = 0; i < n; i++)
printf("%.2d: %.2d %s %.2d\n", i, date_list[i].day, date_list[i].month, date_list[i].year);
key_date = allocateStruct(1);
scanf("%s", key_date->month);
scanf("%d", &key_date->day);
scanf("%d", &key_date->year);
printf("Search: %.2d %s %.2d\n", key_date->day, key_date->month, key_date->year);
q_result = (date *) bsearch(key_date, date_list, n, sizeof(date), cmpDates);
if (q_result != NULL)
{
printf("Yes (%.2d %s %.2d) in list (%.2d %s %.2d)\n",
key_date->day, key_date->month, key_date->year,
q_result->day, q_result->month, q_result->year);
}
else
{
printf("No (%.2d %s %.2d) in list\n",
key_date->day, key_date->month, key_date->year);
}
freeStruct(date_list, n);
freeStruct(key_date, 1);
return 0;
}
示例数据：
16
November 26 00
February 18 12
January 19 08
March 22 11
October 08 05
December 22 10
November 08 01
May 21 10
July 10 92
October 06 91
November 30 93
April 25 90
March 21 90
September 18 97
June 23 97
July 19 98
November 29 93
文件的最后一行是要搜索的日期。 November 29 93 不在列表中，但将 29 更改为 30 并且日期在列表中。在这两种情况下，代码都正确报告了这一点。
示例输出：
Input data:
00: 26 November 00
01: 18 February 12
02: 19 January 08
03: 22 March 11
04: 08 October 05
05: 22 December 10
06: 08 November 01
07: 21 May 10
08: 10 July 92
09: 06 October 91
10: 30 November 93
11: 25 April 90
12: 21 March 90
13: 18 September 97
14: 23 June 97
15: 19 July 98
Sorted:
00: 21 March 90
01: 25 April 90
02: 06 October 91
03: 10 July 92
04: 30 November 93
05: 23 June 97
06: 18 September 97
07: 19 July 98
08: 26 November 00
09: 08 November 01
10: 08 October 05
11: 19 January 08
12: 21 May 10
13: 22 December 10
14: 22 March 11
15: 18 February 12
Search: 29 November 93
No (29 November 93) in list
我认为将月份名称存储在日期结构中是个糟糕的主意。如果您要存储一个指针，您可以存储一个指向表示月份名称的固定字符串数组之一的指针。您将输入名称读入数组，然后从月份名称列表中找到规范指针。您将存储名称，以便 January 的地址位于 February 的地址之前，等等，以便您可以比较指针并得出正确答案。但是，我还没有实现。事实上，我认为在结构中存储月份名称是个坏主意；我会存储一个月的数字。我还认为只存储两位数的年份是一个糟糕的决定。也许您没有意识到必要的 Y2K 错误修复工作，因为人们试图偷工减料，多年来只存储两位数字而不是四位数字，但这很混乱。仅存储年份数字要简单得多。您甚至没有保存任何 space，因为您使用 4 个字节（现在 int 通常是 4 个字节）来存储两位数的年份。如果您将年作为 4 位数字，将月和日作为 2 位数字，那么 yyyy * 10000 + mm * 100 + dd 将为您提供一个可以简单排序的 8 位整数。如果您需要计算两个日期之间的天数，那么细分格式不如计算自参考日期（例如 1900-01-01 是第 1 天）以来的天数方便。您可以取两个这样的日期值之间的差值以获得它们之间的天数。
我想在日期数组中搜索一个日期（它是一个结构），看看它是否在其中。这是我第一次使用 bsearch，它总是 return 相同的结果 0，而它应该 return null 或指向找到日期的指针。我正在使用我用来对数组进行排序的相同比较函数，并且排序工作正常。我猜函数 returns 0 是否意味着它已经在数组中找到了日期。我做错了什么？如果错误不明显，我可以 post 完整代码。
#define MIN_SIZE 0
#define MAX_SIZE 10000
#define MAX_MONTH_STR 9
#define SWAP 1
#define NO_SWAP -1
#define EQUAL 0
//Define a struct data type
typedef struct
{
//Declaration of struct members
char* month;
int day;
int year;
}date;
//Method to allocate memory for a list of date structures
date* allocateStruct(int size)
{
//Declaration of variables
date *array;
int i;
//Allocate memory for array to store 'size' many 'date' struct data types
array = malloc(size*sizeof(date));
//For-loop to allocate memory for each struct's members and initialize them to zero
for (i=0; i<size; i++)
{
array[i].month = calloc(MAX_MONTH_STR,sizeof(char));
array[i].day = (int) calloc(1,sizeof(int));
array[i].year = (int) calloc(1,sizeof(int));
}
return array;
}
//Method to free memory allocated
void freeStruct(date* array, int size)
{
//Declaration of variable
int i;
//For-loop to free up struct members
for (i=0; i<size; i++)
{
free(array[i].month);
free(&array[i].day);
free(&array[i].year);
}
//Free up structs
free(array);
}
//Method to compare two dates
int cmpDates (const void *a, const void *b)
{
//Declaration and dereference of variables
date first = *(date*)a;
date second = *(date*)b;
int y_result, m_result, d_result;
//Calculate results
y_result = second.year-first.year;
m_result = second.month-first.month;
d_result = second.day-first.day;
//If-statements to determine whether to swap dates based on year
//If-statement to determine whether both years are in 90s group
if (first.year>=90 && first.year<=99 && second.year>=90 && second.year<=99)
{
//If-statement to determine whether years are equal
if (y_result!=0)
{
return (y_result);
}
}
//Else-if-statement to determine whether both years are in 00-12 group
else if (first.year>=0 && first.year<=12 && second.year>=0 && second.year<=12)
{
//If-statement to determine whether years are equal
if (y_result!=0)
{
return (y_result);
}
}
//Otherwise the two years belong to different year groups
else
{
//If-statement to determine whether first year belongs to 00-12 group
if (first.year>=0 && first.year<=12)
{
return NO_SWAP;
}
else
{
return SWAP;
}
}
//If-statement to determine whether to swap dates based on months
if (m_result!=0)
{
return m_result;
}
//If-statement to determine whether to swap dates based on days
if (d_result!=0)
{
return d_result;
}
//If dates are exactly the same
return EQUAL;
}
enum months {
January=1,
February,
March,
April,
May,
June,
July,
August,
September,
October,
November,
December
};
int main()
{
//Declaration of variables
int n; //number of dates in array
date* date_list; //array of dates
date *key_date; //date to search for
date *q_result; //result of search
//Read input
do
{
//printf("Enter number of dates you want to enter (between 1 and 10000):\n");
scanf("%d", &n);
}while(n<MIN_SIZE || n>MAX_SIZE);
//Allocate memory for an array of n dates
date_list = allocateStruct(n);
//For-loop to store values in 'date_list'
for (i=0; i<n; i++)
{
//printf("Enter the date (month day year) in the following format <text number number>:");
scanf("%s", date_list[i].month);
scanf("%d", &date_list[i].day);
scanf("%d", &date_list[i].year);
}
//Allocate memory for one date
key_date = allocateStruct(1);
//Read date for query
//printf("Enter date you want to query:");
scanf("%s", key_date->month);
scanf("%d", &key_date->day);
scanf("%d", &key_date->year);
//Sort the array with built-in function qsort
qsort(date_list, n, sizeof(date), cmpDates);
//Print list of sorted dates
for (i=0; i<n; i++)
{
//printf("Enter the date (month day year) in the following format: text number number");
printf("%s ", date_list[i].month);
printf("%d ", date_list[i].day);
printf("%02d\n", date_list[i].year); //need & ?
}
//Query with bsearch --> I TRIED BOTH OF THESE LINES BUT THE RESULT WAS THE SAME
q_result = (date*) bsearch(&key_date, date_list, n, sizeof(date), cmpDates);
// q_result = bsearch(&key_date, date_list, n, sizeof(date), cmpDates);
//Printing answer to query
if(q_result!=NULL)
{
printf("Yes in list");
}
else
{
printf("No not in list");
}
}
key_date 是一个指针，但是你将它的地址传递给 bsearch 所以当 cmpDates 被调用时，它会尝试转换（重新解释）一个 void* 这是一个 date** 到 date*，然后将其取消引用到 date。显然，从 date 结构中检索到的值都是错误的。我很惊讶你没有遇到月份字符串的崩溃。
q_result = (date*) bsearch(&key_date, date_list, n, sizeof(date), cmpDates);
应该是
q_result = (date*) bsearch(key_date, date_list, n, sizeof(date), cmpDates);
显然，您仍然需要解决（无双关语）calloc 问题
for (i=0; i<size; i++)
{
array[i].month = calloc(MAX_MONTH_STR,sizeof(char));
array[i].day = (int) calloc(1,sizeof(int));
array[i].year = (int) calloc(1,sizeof(int));
}
应该是（如果你真的需要把月份作为一个字符串）
for (i=0; i<size; i++)
{
array[i].month = calloc(MAX_MONTH_STR,sizeof(char));
array[i].day = 0;
array[i].year = 0;
}
然后
for (i=0; i<size; i++)
{
free(array[i].month);
free(&array[i].day);
free(&array[i].year);
}
应该是
for (i=0; i<size; i++)
{
free(array[i].month);
}
关于你的月份比较，你需要这样的函数：
months GetMonth(char* m)
{
if (strcmp(m, "January") == 0)
return months.January;
else if (strcmp(m, "February") == 0)
return months.February;
....
}
我忽略了区分大小写。
然后将此枚举存储在日期结构中，月份比较至少有意义。
这是我根据您的代码组装的代码，似乎可以正常工作。我没有对其进行压力测试。
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#define MIN_SIZE 1
#define MAX_SIZE 10000
#define MAX_MONTH_STR 10
#define EQUAL 0
#define LESS_THAN -1
#define MORE_THAN +1
typedef struct
{
char *month;
int day;
int year;
} date;
static
date *allocateStruct(int size)
{
date *array = malloc(size * sizeof(date));
if (array == 0)
exit(1);
for (int i = 0; i < size; i++)
{
array[i].month = calloc(MAX_MONTH_STR, sizeof(char));
if (array[i].month == 0)
exit(1);
}
return array;
}
static
void freeStruct(date *array, int size)
{
for (int i = 0; i < size; i++)
{
free(array[i].month);
}
free(array);
}
static inline int normalize_year(int year)
{
return (year < 50) ? year + 2000 : year + 1900;
}
static inline int month_number(const char *name)
{
static const char *months[] =
{
"",
"January", "February", "March", "April", "May", "June",
"July", "August", "September", "October", "November", "December",
};
for (int i = 1; i <= 12; i++)
if (strcmp(name, months[i]) == 0)
return i;
fprintf(stderr, "Invalid (unrecognized) month name <<%s>>\n", name);
exit(1);
/*NOTREACHED*/
}
static
int cmpDates(const void *a, const void *b)
{
date first = *(date *)a;
date second = *(date *)b;
int y1 = normalize_year(first.year);
int y2 = normalize_year(second.year);
if (y1 < y2)
return LESS_THAN;
else if (y1 > y2)
return MORE_THAN;
int m1 = month_number(first.month);
int m2 = month_number(second.month);
if (m1 < m2)
return LESS_THAN;
else if (m1 > m2)
return MORE_THAN;
if (first.day < second.day)
return LESS_THAN;
else if (first.day > second.day)
return MORE_THAN;
else
return EQUAL;
}
int main(void)
{
int n;
date *date_list;
date *key_date;
date *q_result;
do
{
if (scanf("%d", &n) != 1)
exit(1);
} while (n < MIN_SIZE || n > MAX_SIZE);
date_list = allocateStruct(n);
printf("Input data:\n");
for (int i = 0; i < n; i++)
{
scanf("%s", date_list[i].month);
scanf("%d", &date_list[i].day);
scanf("%d", &date_list[i].year);
printf("%.2d: %.2d %s %.2d\n", i, date_list[i].day, date_list[i].month, date_list[i].year);
}
qsort(date_list, n, sizeof(date), cmpDates);
printf("Sorted:\n");
for (int i = 0; i < n; i++)
printf("%.2d: %.2d %s %.2d\n", i, date_list[i].day, date_list[i].month, date_list[i].year);
key_date = allocateStruct(1);
scanf("%s", key_date->month);
scanf("%d", &key_date->day);
scanf("%d", &key_date->year);
printf("Search: %.2d %s %.2d\n", key_date->day, key_date->month, key_date->year);
q_result = (date *) bsearch(key_date, date_list, n, sizeof(date), cmpDates);
if (q_result != NULL)
{
printf("Yes (%.2d %s %.2d) in list (%.2d %s %.2d)\n",
key_date->day, key_date->month, key_date->year,
q_result->day, q_result->month, q_result->year);
}
else
{
printf("No (%.2d %s %.2d) in list\n",
key_date->day, key_date->month, key_date->year);
}
freeStruct(date_list, n);
freeStruct(key_date, 1);
return 0;
}
示例数据：
16
November 26 00
February 18 12
January 19 08
March 22 11
October 08 05
December 22 10
November 08 01
May 21 10
July 10 92
October 06 91
November 30 93
April 25 90
March 21 90
September 18 97
June 23 97
July 19 98
November 29 93
文件的最后一行是要搜索的日期。 November 29 93 不在列表中，但将 29 更改为 30 并且日期在列表中。在这两种情况下，代码都正确报告了这一点。
示例输出：
Input data:
00: 26 November 00
01: 18 February 12
02: 19 January 08
03: 22 March 11
04: 08 October 05
05: 22 December 10
06: 08 November 01
07: 21 May 10
08: 10 July 92
09: 06 October 91
10: 30 November 93
11: 25 April 90
12: 21 March 90
13: 18 September 97
14: 23 June 97
15: 19 July 98
Sorted:
00: 21 March 90
01: 25 April 90
02: 06 October 91
03: 10 July 92
04: 30 November 93
05: 23 June 97
06: 18 September 97
07: 19 July 98
08: 26 November 00
09: 08 November 01
10: 08 October 05
11: 19 January 08
12: 21 May 10
13: 22 December 10
14: 22 March 11
15: 18 February 12
Search: 29 November 93
No (29 November 93) in list
我认为将月份名称存储在日期结构中是个糟糕的主意。如果您要存储一个指针，您可以存储一个指向表示月份名称的固定字符串数组之一的指针。您将输入名称读入数组，然后从月份名称列表中找到规范指针。您将存储名称，以便 January 的地址位于 February 的地址之前，等等，以便您可以比较指针并得出正确答案。但是，我还没有实现。事实上，我认为在结构中存储月份名称是个坏主意；我会存储一个月的数字。我还认为只存储两位数的年份是一个糟糕的决定。也许您没有意识到必要的 Y2K 错误修复工作，因为人们试图偷工减料，多年来只存储两位数字而不是四位数字，但这很混乱。仅存储年份数字要简单得多。您甚至没有保存任何 space，因为您使用 4 个字节（现在 int 通常是 4 个字节）来存储两位数的年份。如果您将年作为 4 位数字，将月和日作为 2 位数字，那么 yyyy * 10000 + mm * 100 + dd 将为您提供一个可以简单排序的 8 位整数。如果您需要计算两个日期之间的天数，那么细分格式不如计算自参考日期（例如 1900-01-01 是第 1 天）以来的天数方便。您可以取两个这样的日期值之间的差值以获得它们之间的天数。