2010-02-19 3 views
1

Если у меня есть две функций:функция bsearch в с

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 найти подмножество моего списка. Например, если у меня есть два списка:

  • (список А) Боб, Джимми Ли, Джеймс, Энн
  • (список Б) Джен, Джон Ли, Джеймс, Стеф

Как искать в списке B, чтобы найти эти элементы в A?

Вы также можете выполнить поиск в списке B, чтобы найти эти элементы, не входящие в A?

Спасибо.

+3

Примечание: вы не можете использовать 'SizeOf (studentList)' значению, когда studentList является параметром функции - вы будете поиск в списке размеров 1. –

+0

Извините, вы можете объяснить это дальше? Я еще не совсем понимаю, почему все еще. – Crystal

+0

Поскольку тип «studentList» в функции «char **», поэтому размер такой же, как размер указателя (4 или 8 байт по существу всех машин), а sizeof (studentList [0]) - это размер «char *», который имеет одинаковый размер, поэтому количество элементов, переданных в сортировку qsort, равно 1, что не занимает много времени или вызывает какие-либо компараторы. –

ответ

4

Для выполнения поиска вам необходимо использовать список из одного элемента в качестве ключевого параметра в 'bsearch()'.

В контексте поиска для вступления в a_list[n] в b_list:

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

Таким образом, чтобы найти элементы в список B, которые находятся в списке А, вы будете делать: Список

  • Сортировка B (вам не нужно сортировать список A для этой части упражнения, если вы не хотите)
  • Для каждого элемента в списке A найдите элемент в списке (отсортированный) Список B.

И чтобы найти элементы в B, которые не находятся в A, вам нужно будет отсортировать список A в конце концов, а затем для каждого элемента в списке B, посмотрите, находится ли элемент в списке 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 
+0

в функции bsearch, которую вы указали, является & a_list [n], такой же как & a_list? – Crystal

+0

Нет.'& a_list [n]' - адрес N-го элемента в списке; & a_list - это адрес списка, который приблизительно эквивалентен адресу нулевого элемента в списке (технически, тип отличается, но адрес тот же). –

+0

Почему вы используете char ** found = bsearch, а не только char *? – Crystal