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