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

[AussieBill]

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

 

[ssingh]

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

 

[ami123]

Hi buddies,<br>&nbsp;&nbsp;&nbsp;I think i will have to differ with siddhartha...<br>I dont think a bsearch() on a linked list is a practical solution..for the basic reasoning that there is no way to index into the middle of a linked list other than to traverse through the list(linked list are dynamically allocated) ...and if we are doing that then the whole concept of bsearch() is lost.<br><br>thanks<br>adios<br>amit

 

[clive]

Sorry Siddhartha but I tend to agree with amit here. You cannot do a binary search on a linked list. I think Aussie Bill would have to create a binary tree instead.

However because you're reading from an ordered text file the binary tree would come out rather unbalanced. If you're unkeen on making a binary tree and implementing a balancing function then I suggest traversing the linked list or find some way to stick the words in an array.

Let me know if you need help with the binary tree stuff.

-Clive [sig][/sig]

 

[mbaranski]

You could use the STL to make a vector, and this will give you the random access of an array, like element, and the variable size of a linked list. There is already a binary search written and optimized for the STL (Standard Template Library), so all you'll have to do is read the stuff in from a file and push it into the vector, and call the functions.

Hope That Helps

Mike