bsearch( ) with an Ordered Linked List : Can it be Done ?

AussieBill · May 12, 2000

Hello folks, Can anyone help ? I want to READ in an Ordered Text file of Words into Memory - i.e Ordered Linked List. I'm OK here.. Then use bsearch() to locate a KeyWord and see if it exists in the Ordered Linked List. Can it be done ? I only know how to use bsearch() with an Array. Aussie Bill

ssingh · May 14, 2000

Below is the code: Yes it can be done thru linked list also. The concept is : In case of array you pass the index or subscript of the array. While in case of linked list you need to pass the pointer to the node. If you need source code , I can try. Does this answer your question ? Thanx Siddhartha Singh <A HREF="mailto:ssingh@aztecsoft.com">ssingh@aztecsoft.com</A> I am giving you the source code of linked list merge sort. Hope it will help in understanding you the logic for binary search. /* ** Here's an example of how to sort a singly-linked list.  I think it ** can be modified to sort a doubly-linked list, but it would get a bit ** more complicated.  Note that this is a recursive method, but the ** recursion depth is limited to be proportional to the base 2 log of ** the length of the list, so it won't "run away" and blow the stack. */ #include "snipsort.h" /* linked list sort -- public domain by Ray Gardner  5/90 */ #include <stdio.h>              /* for NULL definition */ #include <string.h> /* returns < 0 if *p sorts lower than *q */ int keycmp (list *p, list *q) {       return strcmp(p->key, q->key); } /* merge 2 lists under dummy head item */ list *lmerge (list *p, list *q) {       list *r, head;       for ( r = &head; p && q; )       {             if ( keycmp(p, q) < 0 )             {                   r = r->next = p;                   p = p->next;             }             else             {                   r = r->next = q;                   q = q->next;             }       }       r->next = (p ? p : q);       return head.next; } /* split list into 2 parts, sort each recursively, merge */ list *lsort (list *p) {       list *q, *r;       if ( p )       {             q = p;             for ( r = q->next; r && (r = r->next) != NULL; r = r->next )                   q = q->next;             r = q->next;             q->next = NULL;             if ( r )                   p = lmerge(lsort(r), lsort(p));       }       return p; } #if 0 /* Not really main(), but a fill-in-the-blanks framework */ #ifdef __WATCOMC__  #pragma off (unreferenced) #endif main (void) {       list *listp;                 /* pointer to start of list */       /* first build unsorted list, then */       listp = lsort(listp);                                 /* rdg 10/93 */       return 0; } #endif Siddhartha Singh <a href=mailto:siddhu_singh@hotmail.com>siddhu_singh@hotmail.com</a> <a href=siddhu.freehosting.net> </a>

AussieBill · May 14, 2000

Thanks for your reply on TEk Tips forum (C), I appreciate this. .....I have attached a file "diction.c" (which is a linked list of letters(a,b,c,...,p) which is sorted. Say I am looking for letter 'c'  if it exists in the linked list. How do I use bsearch() to find the if match in the linked list ?   My Overall Problem: I will READ in a already Sorted List of Words (Dictionary) into Memory - i.e usingOrdered Linked List. I wanted to store the Words in an Array but don't know how many words exist, so cannot declare proper size of array. So I guess I will have to use a linked list Then use bsearch() to locate a KeyWord and see if it exists in the Ordered Linked List. If it can be done. ------------------------------------------------------------ See my attached file "diction.c" (at bottom page) ------------------------------------------------------------ BSEARCH: (function I need to use) *bsearch( const void *key, const void * base, size_t nnemb, size_t size, int (*compar)(const void *, const void*) );   e.g Search for word 'hello'  in array :array[10] stores 10 words   bsearch("hello", array, 10, sizeof(array[0]),comp) where compare function is :- int comp (const void *s1, const void *s2) {     return (strcmp(*(char **)s1, *(char **)s2)); } ----------------------------------------------------------- ----------------------------------------------------------- #include <stdio.h> #include <string.h> #include <ctype.h> #include <stdlib.h> int comp(const void *s1, const void *s2); typedef struct D_ENTRY_STRUCT LIST; typedef LIST *LISTPTR; struct D_ENTRY_STRUCT { char  letter; struct D_ENTRY_STRUCT *next_rec; }; LISTPTR add_to_list ( char, LISTPTR ); void show_list( void ); void free_memory_list( void ); LISTPTR first = NULL; main () { LISTPTR rec_addr; int i=0; char letter,ptr; rec_addr = add_to_list('a', (LISTPTR)NULL ); first = rec_addr; printf("Before Insertion\n&quot

; while (i++<15) rec_addr = add_to_list('a'+i,rec_addr); show_list(); printf("\nCount : %d",i); printf("\nSearch key : &quot

; letter = getchar(); // ptr = (char)bsearch(letter,first,16,sizeof(first),comp); // if (ptr != NULL) // printf("found&quot

; // else // printf("not found&quot

; */ // free_memory_list(); return 0; } LISTPTR add_to_list (char ch, LISTPTR prev_rec) { LISTPTR new_rec=NULL; new_rec = (LISTPTR)malloc(sizeof(LIST)); if (!new_rec) { printf("\nUnable to allocate memory!\n&quot

; exit(1); } new_rec->letter = ch; new_rec->next_rec = NULL; if (prev_rec) prev_rec->next_rec = new_rec; return(new_rec); } void show_list ( ) { LISTPTR cur_ptr; int counter=1; printf("Rec addr   Position   Data   Next Rec addr\n&quot

; printf("========   ========   ====   =============\n&quot

; cur_ptr = first; while (cur_ptr) { printf("  %X   ", cur_ptr); printf("     %2i       %c",counter++,cur_ptr->letter); printf("      %X   \n",cur_ptr->next_rec); cur_ptr = cur_ptr->next_rec; } } void free_memory_list ( ) { LISTPTR cur_ptr, next_rec; cur_ptr = first; while (cur_ptr) { next_rec = cur_ptr->next_rec; free(cur_ptr); cur_ptr = next_rec; } } int comp(const void *s1, const void *s2) { return (strcmp(*(char **)s1, *(char **)s2)); } ------------------------------------------------------------

ssingh · May 14, 2000

I will look into your code after sometime. Beucase right now I am very much busy. let me tell you the logic. You can then try yourself. Else whenever I will get time , will let you know.   Note:       In an array case you know the lower limit (usually 0) and upper bound also. In case of linked list , your problem is how to know the uppor bound. Header is the lower bound. Since binary search involves previous knowledge of these bounds.   Solution:     During fetching data into linked list just maintain a counter also . Which will keep count of the no. of nodes in the linked list. Or you can know the number of nodes by this logic also count = 1; while(heade->next != NULL)        count++; When you come out of the loop , count will be having the upper bound of the linked list. Now when you use your binary search in the program. Just use the numbers as in the case of array. But when you compute  , use it like this way:   Suppose in case of array , when you pass mid , last as a subscript. You use like array[mid] or array[last]. And then you pass these to comp function to check the values. Instead of this , in case of linked list. When you pass mid, then you have to implement the logic like:     int k = 1; node = header; While(k <= mid){     node = node->next;     k++; }     This way when you come out of the loop , node will be having the value of mid  position.    Does this answer your question ?   Siddhartha Singh <a href=mailto:siddhu_singh@hotmail.com>siddhu_singh@hotmail.com</a> <a href=siddhu.freehosting.net> </a>

Tek-Tips is the largest IT community on the Internet today!

Members share and learn making Tek-Tips Forums the best source of peer-reviewed technical information on the Internet!

<b>bsearch( ) with an Ordered Linked List : Can it be Done ? </b>

AussieBill

Technical User

ssingh

Programmer

AussieBill

Technical User

ssingh

Programmer

Similar threads

Part and Inventory Search

Sponsor

Tek-Tips is the largest IT community on the Internet today!

Members share and learn making Tek-Tips Forums the best source of peer-reviewed technical information on the Internet!

&lt;b&gt;bsearch( ) with an Ordered Linked List : Can it be Done ? &lt;/b&gt;

AussieBill

Technical User

ssingh

Programmer

AussieBill

Technical User

ssingh

Programmer

Similar threads

Log in

Part and Inventory Search

Sponsor

<b>bsearch( ) with an Ordered Linked List : Can it be Done ? </b>