1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
|
/*
** 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.
**
** 10/21/93 rdg Fixed bug -- function was okay, but called incorrectly.
*/
/* linked list sort -- public domain by Ray Gardner 5/90 */
#include <stdio.h> /* for NULL definition */
#include <string.h>
typedef struct list_struct {
struct list_struct *next;
char *key;
/* other stuff */
} list;
/* 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;
}
main (void)
{
list *listp; /* pointer to start of list */
/* first build unsorted list, then */
listp = lsort(listp); /* rdg 10/93 */
return 0;
}
|
