首页 > > 程序设计 > C/C++ >

C语言基础——链表的相关操作

2018-12-04 07:13:04来源：博客园阅读 ()


  1 #include <stdio.h>
  2 #include <malloc.h>
  3 #include <string.h>
  4 #include <math.h>
  5 #include <stdlib.h>
  6  
  7 typedef int elemtype;
  8  
  9 #define TRUE 0
 10 #define FALSE 1
 11 #define OK 1
 12 #define ERROR 0
 13 #define INFEASIBLE -1
 14  
 15  
 16 #if(1)
 17  
 18 typedef struct LNode
 19 {
 20     struct LNode *next;
 21     int date;
 22 }*LinkList;
 23  
 24 //typedef LNode *LinkList;
 25  
 26 #endif
 27  
 28 #if(0)
 29  
 30 typedef struct LNode
 31 {
 32     struct LNode *next;
 33  
 34     elemtype data;
 35 };
 36  
 37 #endif
 38  
 39 void InitList(LinkList L)
 40 {
 41     L = (LinkList)malloc(sizeof(struct LNode));
 42     if(!L)
 43     {
 44         exit(-1);
 45     }
 46     L->next = NULL;
 47 }
 48  
 49 void DestroyList(LinkList L)
 50 {
 51     LinkList q;
 52     while(L)
 53     {
 54         q = L->next;
 55         free(L);
 56         L = q;
 57     }
 58 }
 59  
 60 void ClearList(LinkList L)
 61 {
 62     LinkList p, q;
 63     p = L->next;          //p = L的话就销毁了链表相当于DestroyList
 64     while(p)
 65     {
 66         q = p->next;
 67         free(p);
 68         p = q;
 69     }
 70  
 71     L->next = NULL;
 72 }
 73  
 74 int ListEmpty(LinkList L)
 75 {
 76     if(L->next)
 77     {
 78         return FALSE;
 79     }
 80  
 81     return TRUE;
 82 }
 83  
 84 int ListLength(LinkList L)
 85 {
 86     int i = 0;
 87     LinkList p = L->next;        //应该设立一个新的指针代替L，
 88  
 89     while(p)
 90     {
 91         i++;
 92         p = p->next;
 93     }
 94  
 95     return i;
 96 }
 97  
 98 int GetElem(LinkList L, int i, elemtype *e)
 99 {
100     int j;
101     LinkList p;
102     p = L;
103  
104     for(j = 0; j < i; j++)
105     {
106         p = p->next;
107     }
108  
109     if(!p)
110     {
111         return ERROR;
112     }
113  
114     *e = p->date;
115  
116     return OK;
117  
118 }
119  
120 int LocateElem(LinkList L, elemtype *e)
121 {
122     int i = 0;
123     LinkList p;
124     p = L->next;
125  
126     while(p)
127     {
128         i++;
129  
130         if(p->date == *e)
131         {
132             return i;
133         }
134  
135         p = p->next;
136     }
137  
138     return 0;
139 }
140  
141 int PriorElem(LinkList L, elemtype cur_e, elemtype *pre_e)
142 {
143     LinkList p, q;
144  
145     p = L->next;
146  
147     while(p->next)
148     {
149         q = p->next;
150  
151         if(q->date == cur_e)
152         {
153             *pre_e = p->date;
154  
155             return OK;
156  
157         }
158  
159         p = q;
160     }
161  
162     return INFEASIBLE;
163 }
164  
165 int NextElem(LinkList L, elemtype cur_e, elemtype *next_e)
166 {
167     LinkList p;               //remember it
168  
169     p = L->next;
170  
171     while(p->next)
172     {
173  
174         if(p->date == cur_e)
175         {
176             *next_e = p->next->date;
177             return OK;
178         }
179  
180         p = p->next;
181  
182     }
183  
184     return INFEASIBLE;
185  
186 }
187  
188 int ListInsert(LinkList L, int i, elemtype e)
189 {
190     int j = 1;
191     LinkList p = L, s;
192  
193     if(i < 1)
194     {
195         return ERROR;
196     }
197     s = (LinkList)malloc(sizeof(struct LNode));
198     s->date = e;
199     if(i == 1)
200     {
201         s->next = L;
202  
203         L = s;
204     }
205     else
206     {
207         while(p && j < i - 1)
208         {
209             p = p->next;
210             j++;
211         }
212         if(!p)
213         {
214             return ERROR;
215  
216         }
217         s->next = p->next;
218         p->next = s;
219     }
220     return OK;
221  
222 }
223  
224 int ListDelete(LinkList L, int i, elemtype *e)
225 {
226     int j = 1;
227     LinkList p = L->next;
228     LinkList q = L;
229  
230     while(j < i)
231     {
232         p = p->next;
233         q = q->next;
234         j++;
235     }
236  
237     if(!p || j >= i)
238     {
239         return ERROR;
240     }
241  
242     q->next = p->next;
243     *e = p->date;
244     free(p);
245  
246     return OK;
247 }
248  
249 void ListTraverse(LinkList L)
250 {
251     LinkList q = L;
252     while(q)
253     {
254         printf("%d ", q->date);
255         q = q->next;
256     }
257  
258     //printf("\n\n");
259 }
260  
261  
262 #if(0)
263  
264 void main()
265 { // 除了几个输出语句外，主程序和main2-1.cpp很像
266     LinkList L = NULL; // 与main2-1.cpp不同
267     elemtype e, e0;
268     int i;
269     int j, k;
270  
271     InitList(L);
272  
273     for(j=1; j<=5; j++)
274     {
275         i = ListInsert(L, 1, &j);
276     }
277  
278     printf("在L的表头依次插入1～5后：L=");
279  
280     ListTraverse(L); // 依次对元素调用print()，输出元素的值
281  
282     i = ListEmpty(L);
283  
284     printf("L是否空：i=%d(1:是0:否)\n",i);
285  
286     ClearList(L);
287  
288     printf("清空L后：L=");
289  
290     ListTraverse(L);
291     i = ListEmpty(L);
292  
293     printf("L是否空：i=%d(1:是0:否)\n",i);
294  
295     for(j=1; j<=10; j++)
296     {
297         ListInsert(L, j, &j);
298     }
299  
300     printf("在L的表尾依次插入1～10后：L=");
301  
302     ListTraverse(L);
303     GetElem(L, 5, &e);
304  
305     printf("第5个元素的值为%d\n",e);
306     for(j=0; j<=1; j++)
307     {
308         k = LocateElem(L, &j);
309         if(k)
310         {
311             printf("第%d个元素的值为%d\n",k,j);
312         }
313         else
314         {
315             printf("没有值为%d的元素\n",j);
316         }
317     }
318     for(j=1;j<=2;j++) // 测试头两个数据
319     {
320         GetElem(L, j, &e0); // 把第j个数据赋给e0
321         i = PriorElem(L, e0, &e); // 求e0的前驱
322         if(i == INFEASIBLE)
323  
324             printf("元素%d无前驱\n", e0);
325         else
326             printf("元素%d的前驱为%d\n", e0, e);
327     }
328     for(j=ListLength(L)-1; j<=ListLength(L); j++) // 最后两个数据
329     {
330         GetElem(L, j, &e0); // 把第j个数据赋给e0
331         i=NextElem(L, e0, &e); // 求e0的后继
332         if(i == INFEASIBLE)
333         {
334             printf("元素%d无后继\n",e0);
335         }
336         else
337         {
338             printf("元素%d的后继为%d\n", e0, e);
339         }
340     }
341     k = ListLength(L); // k为表长
342  
343     for(j=k+1; j>=k; j--)
344     {
345         i = ListDelete(L, j, &e); // 删除第j个数据
346         if(i == ERROR)
347         {
348             printf("删除第%d个元素失败\n",j);
349         }
350         else
351         {
352             printf("删除第%d个元素成功，其值为%d\n", j, e);
353         }
354     }
355     printf("依次输出L的元素：");
356  
357     ListTraverse(L);
358     DestroyList(L);
359  
360     printf("销毁L后：L=%u\n",L);
361 }
362  
363 #endif
364  
365 void main()
366 {
367     LinkList L = NULL;
368     int i, j;
369     InitList(L);
370  
371     for(j=1; j<=5; j++)
372     {
373         i = ListInsert(L, 1, j);
374     }
375  
376     printf("在L的表头依次插入1～5后：L=");
377  
378     ListTraverse(L); // 依次对元素调用print()，输出元素的值
379 }