用c语言创建和排序单链列表

今天，我将简要总结我以前学过的链表的知识. 顺便写一些代码；创建链表有头插值和尾插值两种. 在以下代码中c语言单链表排序，我们为节点分配的内存实际上是在堆上分配的c语言单链表排序，因此我们需要使用free（）函数进行释放，以手动释放它

以下代码粘贴特定代码:

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 
 4 struct person {
 5     int age;
 6     struct person *next;
 7 };
 8 
 9 struct person *insert_head(struct person *head, int age);
10 struct person *insert_tail(struct person *head, int age);
11 void destroy_list(struct person *head);
12 void show(struct person *head);
13 
14 int main()
15 {
16     struct person *head = NULL;
17     head = insert_tail(head, 20);    
18     head = insert_tail(head, 30);    
19     head = insert_tail(head, 60);    
20     head = insert_tail(head, 50);    
21     head = insert_tail(head, 40);    
22     show(head);
23 
24　　　return 0；
25 }
26 
27 /*头插法*/
28 struct person *insert_head(struct person *head, int age)
29 {
30     struct person *tmp = NULL;
31 
32     tmp = (struct person *)malloc(sizeof(struct person));
33     tmp->age = age;
34     tmp->next = NULL;
35 
36     if(NULL == head) {
37         return tmp;
38     }
39     tmp->next = head;
40     head = tmp;
41 
42     return head;        
43 }
44 
45 /*尾插法*/
46 struct person *insert_tail(struct person *head, int age)
47 {
48     struct person *tmp = NULL;
49     struct person *find = NULL;
50 
51     tmp = (struct person *)malloc(sizeof(struct person));    
52     tmp->age = age;
53     tmp->next = NULL;
54     
55     if(NULL == head) {
56         return tmp;
57     }
58     find = head;
59     while(find->next) {
60         find = find->next;
61     }
62     find->next = tmp;
63 
64     return head;    
65 }
66 
67 /*销毁整个链表*/
68 void destroy_list(struct person *head)
69 {
70     struct person *tmp = NULL;
71     
72     tmp = head->next;
73     while(tmp) {
74         head->next = tmp->next;
75         free(tmp);
76         tmp = head->next;
77     }
78 }
79 
80 /*遍历链表*/
81 void show(struct person *head)
82 {
83     struct person *tmp = head;
84     while(tmp) {
85         printf("aeg is %d\n", tmp->age);
86         tmp = tmp->next;        
87     }    
88 }
89 
90     

上面是创建一个简单的链表. 下面我们只对链接列表进行排序:

对于以下排序列表: 我们可以将其分为三个步骤:

（1）在原始链表中找到最小的一个

（2）从原始链表中选取最小的一个

（3）一次插入新的链接列表

循环直到原始链表为空

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 
  4 struct person {
  5     int age;
  6     struct person *next;
  7 };
  8 
  9 struct person *insert_head(struct person *head, int age);
 10 struct person *insert_tail(struct person *head, int age);
 11 struct person *insert_sort(struct person *head);
 12 void destroy_list(struct person *head);
 13 void show(struct person *head);
 14 
 15 int main()
 16 {
 17     struct person *head = NULL;
 18     head = insert_tail(head, 20);    
 19     head = insert_tail(head, 30);    
 20     head = insert_tail(head, 60);    
 21     head = insert_tail(head, 50);    
 22     head = insert_tail(head, 40);    
 23     show(head);
 24     printf("------------------------------\n");
 25     head = insert_sort(head);
 26     show(head);
 27 }
 28 
 29 /*头插法*/
 30 struct person *insert_head(struct person *head, int age)
 31 {
 32     struct person *tmp = NULL;
 33 
 34     tmp = (struct person *)malloc(sizeof(struct person));
 35     tmp->age = age;
 36     tmp->next = NULL;
 37 
 38     if(NULL == head) {
 39         return tmp;
 40     }
 41     tmp->next = head;
 42     head = tmp;
 43 
 44     return head;        
 45 }
 46 
 47 /*尾插法*/
 48 struct person *insert_tail(struct person *head, int age)
 49 {
 50     struct person *tmp = NULL;
 51     struct person *find = NULL;
 52 
 53     tmp = (struct person *)malloc(sizeof(struct person));    
 54     tmp->age = age;
 55     tmp->next = NULL;
 56     
 57     if(NULL == head) {
 58         return tmp;
 59     }
 60     find = head;
 61     while(find->next) {
 62         find = find->next;
 63     }
 64     find->next = tmp;
 65 
 66     return head;    
 67 }
 68 
 69 /*销毁整个链表*/
 70 void destroy_list(struct person *head)
 71 {
 72     struct person *tmp = NULL;
 73     
 74     tmp = head->next;
 75     while(tmp) {
 76         head->next = tmp->next;
 77         free(tmp);
 78         tmp = head->next;
 79     }
 80 }
 81 
 82 #if 0
 83 /*从大到小*/
 84 struct person *insert_sort(struct person *head)
 85 {
 86     struct person *tmp = NULL;
 87     struct person *newhead = NULL;
 88     struct person *min = NULL;
 89     struct person *min_pre = NULL;
 90     
 91     if(NULL == head || NULL == head->next)
 92         return head;
 93 
 94     while(head) {
 95         tmp = head;
 96         min = head;
 97         min_pre = NULL;
 98         
 99         /*step 1:find min*/
100         while(tmp->next) {
101             if(min->age > tmp->next->age) {
102                 min_pre = tmp;
103                 min = tmp->next;
104             }
105             tmp = tmp->next;
106         }
107 
108         /*step 2: cut min*/
109         if(min == head) {
110             head = head->next;
111             min->next = NULL;
112         }
113         else {
114             min_pre->next = min->next;
115             min->next = NULL;
116         }
117 
118         /*step 3: insert new list*/
119         if(NULL == newhead) {
120             newhead = min;
121             continue;
122         }
123         min->next = newhead;
124         newhead = min;
125     }
126 
127     return newhead;    
128 }
129 
130 #else
131 /*从小到大*/
132 struct person *insert_sort(struct person *head)
133 {
134     struct person *tmp = NULL;
135     struct person *newhead = NULL;
136     struct person *newtail = NULL;
137     struct person *min = NULL;
138     struct person *min_pre = NULL;
139     
140     if(NULL == head || NULL == head->next)
141         return head;
142 
143     while(head) {
144         tmp = head;
145         min = head;
146         min_pre = NULL;
147         
148         /*step 1: find min*/
149         while(tmp->next) {
150             if(min->age > tmp->next->age) {
151                 min_pre = tmp;
152                 min = tmp->next;
153             }
154             tmp = tmp->next;
155         }
156 
157         /*step 2: cut min*/
158         if(min == head) {
159             head = head->next;
160             min->next = NULL;
161         }
162         else {
163             min_pre->next = min->next;
164             min->next = NULL;
165         }
166 
167         /*step 3: insert new list*/
168         if(NULL == newhead) {
169             newhead = min;
170             newtail = min;
171             continue;
172         }
173         newtail->next = min;
174         newtail = newtail->next;
175     }
176 
177     return newhead;    
178 }
179 #endif
180 
181 /*遍历链表*/
182 void show(struct person *head)
183 {
184     struct person *tmp = head;
185     while(tmp) {
186         printf("aeg is %d\n", tmp->age);
187         tmp = tmp->next;        
188     }    
189 }

发布于2015-09-05 17: 18z572089387阅读（...）评论（...）编辑

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-176502-1.html