如何在c中正确使用bsearch？

Question

我想在日期数组中搜索日期（这是一个结构体）以查看它是否在其中。这是我第一次使用

bsearch

，它总是返回相同的结果

，而它应该返回

null

或指向找到的日期的指针。我使用与对数组进行排序相同的比较函数，并且排序工作正常。我猜测如果该函数返回“0”，则意味着它已在数组中找到了日期。我做错了什么？如果错误不明显，我可以发布完整的代码。

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

Answer 1

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

我忽略了区分大小写。

然后将此枚举存储在日期结构中，并且月份比较至少有意义。

Answer 2

这是我根据你的代码组装的代码，似乎有效。我没有对其进行压力测试。

#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

不在列表中，但将

更改为

，日期就会在列表中。在这两种情况下，代码都会正确报告这一点。

输出示例：

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

的地址之前，等等，以便您可以比较指针并得出正确的答案。但是，我还没有实现这一点。事实上，我认为在结构中存储月份名称是一个坏主意；我会存储一个月的号码。我还认为只存储年份的两位数字是一个糟糕的决定。也许您没有意识到千年虫修复工作是必要的，因为人们试图走捷径，多年来只存储两位数字而不是四位数字，但它很混乱。仅存储年份数字要简单得多。您甚至没有节省任何空间，因为您使用 4 个字节（现在

int

通常是 4 个字节）来存储 2 位数年份。如果年份是 4 位数字，月份和日期是 2 位数字，那么

yyyy * 10000 + mm * 100 + dd

会为您提供一个可以简单排序的 8 位整数。如果您需要计算两个日期之间的天数，则细分格式不如计算自参考日期（例如 1900-01-01 是第一天）以来的天数方便。您可以利用两个此类日期值之间的差异来获取它们之间的天数。

如何在c中正确使用bsearch？

问题描述投票：0回答：2

2个回答

最新问题

如何在c中正确使用bsearch？

问题描述 投票：0回答：2

2个回答

最新问题

问题描述投票：0回答：2