Posted on 2010-08-20 14:24
David Fang 閱讀(457)
評論(0) 編輯 收藏 引用 所屬分類:
算法點滴
1 #include <stdio.h>
2 #include <stdlib.h>
3
4 typedef struct LinkNode{
5 int val;
6 struct LinkNode* next;
7 }LinkNode;
8
9 LinkNode* CreateList(int A[], int count)
10 {
11 LinkNode* head = (LinkNode*)malloc(sizeof(LinkNode));
12 head->val = A[0];
13 head->next = NULL;
14
15 LinkNode* p = head;
16
17 for (int i = 1; i < count; ++i)
18 {
19 p->next = (LinkNode*)malloc(sizeof(LinkNode));
20 p->next->val = A[i];
21 p->next->next = NULL;
22 p = p->next;
23 }
24
25 return head;
26 }
27
28 //asscending sort link list
29 //
30 LinkNode* SortLinkListBubble(LinkNode* head)
31 {
32 if (NULL == head)
33 {
34 return head;
35 }
36
37 //points to the last, also the bigest value node
38 LinkNode* lastN = NULL;
39
40 while(true)
41 {
42 LinkNode* n = head->next;
43
44 if (n == lastN)
45 {
46 break;
47 }
48
49 if (n->val < head->val)
50 {
51 head->next = n->next;
52 n->next = head;
53 head = n;
54 }
55
56 LinkNode* pre = head;
57 LinkNode* cur = head->next;
58 LinkNode* tmp;
59 n = cur->next;
60
61 while(lastN != n)
62 {
63 if (n->val < cur->val)
64 {
65 tmp = n->next;
66 cur->next = n->next;
67 n->next = cur;
68 pre->next = n;
69 n = tmp;
70 }
71 else
72 {
73 n = n->next;
74 }
75 pre = pre->next;
76 cur = cur->next;
77 }
78
79 lastN = cur;
80 }
81
82 return head;
83 }
84
85 LinkNode* SortLinkListInsertion(LinkNode* head)
86 {
87 if (NULL == head || NULL == head->next)
88 {
89 return head;
90 }
91
92 LinkNode* r = head->next;
93 LinkNode* tmp;
94 head->next = NULL;
95
96 while(NULL != r)
97 {
98 if (r->val < head->val)
99 {
100 tmp = r->next;
101 r->next = head;
102 head = r;
103 r = tmp;
104 }
105 else
106 {
107 LinkNode* p = head;
108 while(NULL != p->next)
109 {
110 if (r->val >= p->val && r->val <= p->next->val)
111 {
112 tmp = r->next;
113 r->next = p->next;
114 p->next = r;
115 r = tmp;
116 break;
117 }
118 else
119 {
120 p = p->next;
121 }
122 }
123
124 if (NULL == p->next)
125 {
126 tmp = r->next;
127 r->next = NULL;
128 p->next = r;
129 r = tmp;
130 }
131 }
132 }
133
134 return head;
135 }
136
137 LinkNode* SortLinkListSelection(LinkNode* head)
138 {
139 if (NULL == head || NULL == head->next)
140 {
141 return head;
142 }
143
144 LinkNode* p = NULL;
145 LinkNode* pre = NULL;
146 LinkNode* pmin = NULL;
147 LinkNode* pminpre = NULL;
148 LinkNode* L = NULL;
149 LinkNode* Ltail = NULL;
150
151 while (NULL != head && NULL != head->next)
152 {
153 pminpre = pmin = head;
154
155 if (head->val > head->next->val)
156 {
157 pmin = head->next;
158 }
159
160 pre = head;
161 p = head->next;
162
163 while(NULL != p)
164 {
165 if (pmin->val > p->val)
166 {
167 pminpre = pre;
168 pmin = p;
169 }
170 pre = pre->next;
171 p = p->next;
172 }
173
174 //delete pmin from original list
175 if (pmin == head)
176 {
177 head = head->next;
178 }
179 else
180 {
181 pminpre->next = pmin->next;
182 }
183
184 //add it to the new list
185 if (NULL == L)
186 {
187 L = Ltail = pmin;
188 pmin->next = NULL;
189 }
190 else{
191 Ltail->next = pmin;
192 Ltail = pmin;
193 pmin->next = NULL;
194 }
195 }
196
197 //do not forget the last node
198
199 Ltail->next = head;
200 return L;
201 }
202
203 void ShowList(LinkNode* L)
204 {
205 LinkNode* p = L;
206 printf("%d", p->val);
207
208 while(p->next)
209 {
210 p = p->next;
211 printf("-->%d", p->val);
212 }
213
214 printf("\n");
215 }
216
217 int main(int argc, char *argv[])
218 {
219 //int A[] = {3, 6, 9, 8, 5, 2, 1, 4, 7, 0};
220 int A[] = {3, 6, 9, 8, 3, 2, 1, 2, 7, 6};
221
222 LinkNode* L = CreateList(A, 10);
223
224 ShowList(L);
225
226 //L = SortLinkListInsertion(L);
227
228 //L = SortLinkListBubble(L);
229
230 L = SortLinkListSelection(L);
231
232 ShowList(L);
233
234 return 0;
235 }
寫得有點混亂，有點像C又有點像C++，權當參考吧