home *** CD-ROM | disk | FTP | other *** search
/ The World of Computer Software / World_Of_Computer_Software-02-385-Vol-1of3.iso / s / snip1292.zip / LL_MSORT.C < prev    next >
C/C++ Source or Header  |  1991-11-22  |  2KB  |  71 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.  
  9. /* linked list sort -- public domain by Ray Gardner  5/90 */
  10.  
  11. #include <stdio.h>              /* for NULL definition */
  12.  
  13. typedef struct list_struct {
  14.    struct list_struct *next;
  15.    char *key;
  16.    /* other stuff */
  17.    } list;
  18.  
  19. /* returns < 0 if *p sorts lower than *q */
  20. int keycmp (p, q)
  21. list *p, *q;
  22. {
  23.    return strcmp(p->key, q->key);
  24. }
  25.  
  26. /* merge 2 lists under dummy head item */
  27. list *lmerge (p, q)
  28. list *p, *q;
  29. {
  30.    list *r, head;
  31.  
  32.    for ( r = &head; p && q; ) {
  33.       if ( keycmp(p, q) < 0 ) {
  34.          r = r->next = p;
  35.          p = p->next;
  36.       } else {
  37.          r = r->next = q;
  38.          q = q->next;
  39.       }
  40.    }
  41.    r->next = (p ? p : q);
  42.    return head.next;
  43. }
  44.  
  45. /* split list into 2 parts, sort each recursively, merge */
  46. list *lsort (p)
  47. list *p;
  48. {
  49.    list *q, *r;
  50.  
  51.    if ( p ) {
  52.       q = p;
  53.       for ( r = q->next; r && (r = r->next) != NULL; r = r->next )
  54.          q = q->next;
  55.       r = q->next;
  56.       q->next = NULL;
  57.       if ( r )
  58.          p = lmerge(lsort(r), lsort(p));
  59.    }
  60.    return p;
  61. }
  62.  
  63. main ()
  64. {
  65.    list *listp;                 /* pointer to start of list */
  66.  
  67.    /* first build unsorted list, then */
  68.  
  69.    lsort(listp);
  70. }
  71.