home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / snip9707.zip / LL_MSORT.C < prev    next >
C/C++ Source or Header  |  1997-07-05  |  2KB  |  85 lines
  1. /* +++Date last modified: 05-Jul-1997 */
  2.  
  3. /*
  4. ** Here's an example of how to sort a singly-linked list.  I think it
  5. ** can be modified to sort a doubly-linked list, but it would get a bit
  6. ** more complicated.  Note that this is a recursive method, but the
  7. ** recursion depth is limited to be proportional to the base 2 log of
  8. ** the length of the list, so it won't "run away" and blow the stack.
  9. **
  10. **  10/21/93 rdg  Fixed bug -- function was okay, but called incorrectly.
  11. */
  12.  
  13. #include "snipsort.h"
  14.  
  15. /* linked list sort -- public domain by Ray Gardner  5/90 */
  16.  
  17. #include <stdio.h>              /* for NULL definition */
  18. #include <string.h>
  19.  
  20.  
  21. /* returns < 0 if *p sorts lower than *q */
  22. int keycmp (list *p, list *q)
  23. {
  24.       return strcmp(p->key, q->key);
  25. }
  26.  
  27. /* merge 2 lists under dummy head item */
  28. list *lmerge (list *p, list *q)
  29. {
  30.       list *r, head;
  31.  
  32.       for ( r = &head; p && q; )
  33.       {
  34.             if ( keycmp(p, q) < 0 )
  35.             {
  36.                   r = r->next = p;
  37.                   p = p->next;
  38.             }
  39.             else
  40.             {
  41.                   r = r->next = q;
  42.                   q = q->next;
  43.             }
  44.       }
  45.       r->next = (p ? p : q);
  46.       return head.next;
  47. }
  48.  
  49. /* split list into 2 parts, sort each recursively, merge */
  50. list *lsort (list *p)
  51. {
  52.       list *q, *r;
  53.  
  54.       if ( p )
  55.       {
  56.             q = p;
  57.             for ( r = q->next; r && (r = r->next) != NULL; r = r->next )
  58.                   q = q->next;
  59.             r = q->next;
  60.             q->next = NULL;
  61.             if ( r )
  62.                   p = lmerge(lsort(r), lsort(p));
  63.       }
  64.       return p;
  65. }
  66.  
  67. #if 0        /* Not really main(), but a fill-in-the-blanks framework    */
  68.  
  69. #ifdef __WATCOMC__
  70.  #pragma off (unreferenced)
  71. #endif
  72.  
  73. main (void)
  74. {
  75.       list *listp;                 /* pointer to start of list */
  76.  
  77.       /* first build unsorted list, then */
  78.  
  79.       listp = lsort(listp);                                 /* rdg 10/93 */
  80.  
  81.       return 0;
  82. }
  83.  
  84. #endif
  85.