Domanda
Se ho due funzioni:
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));
}
Questo genere e confrontare utilizzando la funzione di qsort, come faccio io uso bsearch di trovare sottoinsiemi di mia lista. Per esempio, se ho due liste:
- (elenco A) Bob, Jimmy, Lee, James, Anne
- (elenco B) Jen, Jon, Lee, James, Steph
Come faccio a cercare nell'elenco B per trovare quegli elementi in A?
Si può anche fare una ricerca nell'elenco B per trovare quegli elementi non in un?
Grazie.
Soluzione
Per fare una ricerca, è necessario utilizzare un elenco di un elemento come il parametro chiave per 'bsearch ()'.
Nel contesto, la ricerca per l'entrata in a_list[n]
in b_list
:
void *found = bsearch(&a_list[n], b_list, b_list, b_size, Compare);
Quindi, per trovare gli elementi di Lista B che si trovano nella Lista A, si farà:
- Ordina Lista B (non è necessario per ordinare elenco A per questa parte dell'esercizio a meno che non si desidera)
- Per ogni elemento nell'elenco A, cercare la voce in (l'ordinato) Lista B.
E per trovare gli elementi di B che non sono in A, è necessario ordinare elenco A, dopo tutto e poi per ogni elemento nell'elenco B, vedere se l'elemento è nell'elenco A utilizzando la ricerca inversa.
#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);
}
E l'output era:
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