1

如果我有两个功能：

void SortStudents(char *studentList[], size_t studentCount) 
{
    qsort(studentList, sizeof(studentList)/sizeof(studentList[0]), sizeof(studentList[0]), Compare);
}

int Compare(const void *a, const void *b) 
{
    return (strcmp(*(char **)a, *(char **)b));
}

使用 qsort 函数进行排序和比较，如何使用 bsearch 查找列表的子集。例如，如果我有两个列表：

  • （列表 A）鲍勃、吉米、李、詹姆斯、安妮
  • （名单 B）Jen、Jon、Lee、James、Steph

如何在列表 B 中搜索以找到 A 中的那些元素？

您还可以在列表 B 中进行搜索以找到不在 A 中的元素吗？

谢谢。

4

1 回答 1

5

要进行搜索，您必须使用单项列表作为“bsearch()”的关键参数。

在上下文中，搜索 in 处的a_list[n]条目b_list：

 void *found = bsearch(&a_list[n], b_list, b_list, b_size, Compare);

因此，要查找列表 A 中的列表 B 中的元素，您将执行以下操作：

  • 对列表 B 排序（除非您愿意，否则您不需要对这部分练习的列表 A 进行排序）
  • 对于列表 A 中的每个元素，搜索（已排序的）列表 B 中的项目。

为了找到 B 中不在 A 中的元素，您需要对 List A 进行排序，然后对于 List B 中的每个元素，使用反向搜索查看该元素是否在 List A 中。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

static char *a_list[] = { "Bob", "Jimmy", "Lee", "James", "Anne"  };
static char *b_list[] = { "Jen", "Jon",   "Lee", "James", "Steph" };
static size_t a_number = sizeof(a_list)/sizeof(a_list[0]);
static size_t b_number = sizeof(b_list)/sizeof(b_list[0]);

static int Compare(const void *a, const void *b) 
{
    return (strcmp(*(char **)a, *(char **)b));
}

void SortStudents(char *studentList[], size_t studentCount) 
{
    qsort(studentList, studentCount, sizeof(studentList[0]), Compare);
}

static void dump_list(const char *tag, char **list, size_t number)
{
    size_t i;
    printf("%s:\n", tag);
    for (i = 0; i < number; i++)
        printf(" %s%s", list[i], (i == number - 1) ? "" : ",");
    putchar('\n');
}

static char *search_list(char *name, char **list, size_t number)
{
    char **found = bsearch(&name, list, number, sizeof(*list), Compare);
    return((found == 0) ? 0 : *found);
}

static void names_in_list(char **find_list, size_t find_number, char **name_list, size_t name_number)
{
    size_t i;
    for (i = 0; i < find_number; i++)
    {
        char *name = search_list(find_list[i], name_list, name_number);
        if (name != 0)
            printf("Found %s in list at %s\n", find_list[i], name);
    }
}

static void names_not_in_list(char **find_list, size_t find_number, char **name_list, size_t name_number)
{
    size_t i;
    for (i = 0; i < find_number; i++)
    {
        char *name = search_list(find_list[i], name_list, name_number);
        if (name == 0)
            printf("Did not find %s in list\n", find_list[i]);
    }
}

int main(void)
{
    dump_list("Unsorted A list", a_list, a_number);
    dump_list("Unsorted B list", b_list, b_number);
    SortStudents(a_list, a_number);
    SortStudents(b_list, b_number);
    dump_list("Sorted A list", a_list, a_number);
    dump_list("Sorted B list", b_list, b_number);
    dump_list("Searching in B list for people in A list", b_list, b_number);
    names_in_list(a_list, a_number, b_list, b_number);
    dump_list("Searching in A list for people not in B list", a_list, a_number);
    names_not_in_list(b_list, b_number, a_list, a_number);
    return(0);
}

输出是：

Unsorted A list:
 Bob, Jimmy, Lee, James, Anne
Unsorted B list:
 Jen, Jon, Lee, James, Steph
Sorted A list:
 Anne, Bob, James, Jimmy, Lee
Sorted B list:
 James, Jen, Jon, Lee, Steph
Searching in B list for people in A list:
 James, Jen, Jon, Lee, Steph
Found James in list at James
Found Lee in list at Lee
Searching in A list for people not in B list:
 Anne, Bob, James, Jimmy, Lee
Did not find Jen in list
Did not find Jon in list
Did not find Steph in list
于 2010-02-19T16:50:52.287 回答