/****************************************************************************/ /* LAB81.C: Searching */ #include #define MAXLIST 24 typedef struct item_tag { int key, data; }item_type; /* structure for list information */ typedef struct node_tag { item_type info; /* info component is a structure */ struct node_tag *next; }node_type; /* structure for list node */ /********************* function build_l_list ***************************/ /* builds a linked list whose contents are the same as input array */ node_type *build_l_list(item_type a_list[MAXLIST]) { node_type *p, *q; int i; /* allocate and initialize first node */ p = (node_type *)malloc(sizeof(node_type)); p->info.key = a_list[0].key; p->info.data = a_list[0].data; q = p; /* build rest of list */ for (i = 1; i < MAXLIST; ++i) { q->next = (node_type *)malloc(sizeof(node_type)); q = q->next; q->info.key = a_list[i].key; q->info.data = a_list[i].data; } q->next = NULL; /* be sure to set last pointer component to NULL */ return p; } /********************* function print_l_list **************************/ /* Preconditions: none */ /* Postconditions: The list pointed to by p is printed; the list itself is */ /* not changed. */ void print_l_list(node_type *p) { node_type *temp; int i = 0; printf("Contents of linked list\n"); for (temp = p; temp != NULL; temp = temp->next) { printf("item(%d)=[%d, %d] ", i, temp->info.key, temp->info.data); if ( ((i+1) % 3) == 0) /* start new line after every four values */ printf("\n"); ++i; } printf("\n"); } /******************** function print_a_list ****************/ /* Prints a list stored contiguously in an array */ void print_a_list(item_type a_list[MAXLIST]) { int i; printf("Contents of array-based list\n"); for (i = 0; i < MAXLIST; ++i) { printf("item(%d)=[%d, %d] ", i, a_list[i].key, a_list[i].data); if ( ((i+1) % 3) == 0) /* start new line after every four values */ printf("\n"); } printf("\n"); } /********************** function seq_search *******************************/ /* Conducts a linear search on a contiguously stored sorted list */ /* If key is found, index returns location of key in array */ /* If key is not found, index = -1 */ /* comp = number of comparisons required to make decision */ void seq_search(item_type a_list[MAXLIST], /* array to be searched */ int key, /* key of desired item */ int *index, int *comp) { *comp = 0; *index = 0; while((*index < MAXLIST-1) && (a_list[*index].key < key)) { ++(*index); } if (a_list[*index].key != key) *index = -1; return; } /******************* function l_seq_search ***************************/ /* Conducts a linear search on a sorted linked list */ /* If key is found, index_ptr returns a pointer to the key node */ /* If key is not found, index_ptr = NULL */ /* comp = number of comparisons required to make decision */ void l_seq_search(node_type *list, /* pointer to the list */ int key, /* key of desired item */ node_type **index_ptr, int *comp) { *comp = 0; *index_ptr = list; while (((*index_ptr)->info.key < key) && ((*index_ptr)->next != NULL)) { *index_ptr = (*index_ptr)->next; } if ((*index_ptr)->info.key != key) *index_ptr = NULL; return; } /*************** function bin_search_2 *********************/ /* Conducts a binary search on a sorted array, stopping when key is found */ /* On exit, index returns the location of the key in the array */ /* If the key is not found, index = -1 */ /* Comp returns number of comparisons needed to make the decision */ void bin_search_2(item_type a_list[MAXLIST], /* array to be searched */ int key, /* key of desired item */ int *index, int *comp) { int top, bottom, middle; int found = 0; /* used to terminate search if key is found */ *comp = 0; top = MAXLIST - 1; bottom = 0; while ((top >= bottom) && (!found)) { /*check for end of search */ middle = (top + bottom)/2; if (a_list[middle].key == key) found = 1; /* key has been found; terminate search */ else if (a_list[middle].key < key) bottom = middle + 1; /* search upper half of list */ else top = middle - 1; /* search lower half of list */ } /* end search loop */ if (!found) *index = -1; else *index = middle; return; } /* Main function prototype */ int main(void) { /* Declarations */ /* Define and initialize array to hold list */ item_type A_list[24] = {{13, 634}, {17, 31}, {26, 28901}, {36, 901}, {40, 6561}, {58, 7178}, {73, 5957}, {89, 5146}, {101, 849}, {110, 4922}, {158, 61}, {189, 4007}, {223, 10}, {245, 855}, {270, 2439}, {288, 8401}, {350, 554}, {378, 91}, {400, 85541}, {429, 1345}, {480, 100}, {500, 3642}, {538, 77}, {600, 745}}; node_type *L_list, /* pointer to head of linked list */ *p, *temp; int index, /* used as array index */ key, /* key value to identify record in list search */ compares; /* returns number of comparisons */ char flag, dummy; /* used for interactive input */ /* Statements */ L_list = build_l_list(A_list); print_l_list(L_list); print_a_list(A_list); /* Begin loop to read in keys, search for corresponding records */ do { printf("Enter an integer value\n"); scanf("%d%c", &key, &dummy); /* read key and end of line character */ printf("key = %d\n", key); /* Conduct searches on three versions of list; collect statistics */ /*1*/ seq_search(A_list, key, &index, &compares); if (index < 0) printf("%d is not in the list.\n", key); else printf("The data for key %d is %d.\n", key, A_list[index].data); printf("Sequential array search required %d comparisons\n", compares); /*2*/ l_seq_search(L_list, key, &p, &compares); if (p == NULL) printf("%d is not in the list.\n", key); else printf("The data for key %d is %d.\n", key, p->info.data); printf("Linked list search required %d comparisons\n", compares); /*3*/ bin_search_2(A_list, key, &index, &compares); if (index < 0) printf("%d is not in the list.\n", key); else printf("The data for key %d is %d.\n", key, A_list[index].data); printf("binary array search required %d comparisons\n", compares); /* End searches */ printf("Do you want to look up another record? Enter 'y' or 'n'.\n"); scanf("%c", &flag); } while (flag == 'y'); return(0); }