C/C++知识点之链表的相关操作-职坐标

C/C++知识点之链表的相关操作

小标 2018-08-10 来源：阅读 1459 评论 0

摘要：本文主要向大家介绍了C/C++知识点之链表的相关操作，通过具体的内容向大家展示，希望对大家学习C/C++知识点有所帮助。

本文主要向大家介绍了C/C++知识点之链表的相关操作，通过具体的内容向大家展示，希望对大家学习C/C++知识点有所帮助。

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 }