各位看官們,大家好,從今天開始,我們講大型章回體科技小說 :C栗子,也就是C語言實例。閑話休提, 言歸正轉(zhuǎn)。讓我們一起talk C栗子吧!
看官們,上一回中咱們說的是單鏈表鏈?zhǔn)酱鎯Φ睦?,這一回咱們說的例子是:循環(huán)鏈表。
看官們,循環(huán)鏈表也是鏈表的一種,只不過該鏈表的頭部和尾部相連接,所以構(gòu)成了一個循環(huán)鏈,因此叫 作循環(huán)鏈表。讓我們一起對比一下單鏈接與循環(huán)鏈表的不同之處:單鏈表的尾結(jié)點哪里也沒有指,因為它 的next指針值為空。循環(huán)鏈表的尾結(jié)點指向了它的頭結(jié)點。
看官們,詳細(xì)的代碼放如下,大家可以參考。該例子的代碼與上一回中例子中的代碼類似,不同之處在于, 上一回的例子中判斷鏈表結(jié)束時需要使用指針和NULL進(jìn)行對比。這一回的例子中判斷鏈表結(jié)束時需要使用 尾結(jié)點的指針和頭結(jié)點的指針進(jìn)行對比。如果這兩個指針相同,那么就表示鏈表結(jié)束。
1 /* **************************
2 * Head file of CircleList
3 * *************************/
4 #ifndef CIRCLE_LIST_H
5 #define CIRCLE_LIST_H
6
7 #include<stdio.h>
8 #include<stdlib.h>
9
10 //#define DEBUG 0
11 #ifdef DEBUG
12 int size = 0;
13 #endif
14
15 #define SUCCESS 0
16 #define FAILE 1
17
18 typedef int ListElmt; //把int當(dāng)作List類型,實際中可以使用其它的類型或者自己定義一個List類型,不過不能是使用struct復(fù)合類型
19 typedef struct _ListNode //List node 類型
20 {
21 ListElmt data;
22 struct _ListNode *next;
23 }ListNode;
24
25 //typedef struct _ListNode ListNode;
26 typedef struct _ListNode *List; //定義鏈表的類型為ListNode類型的指針
27
28 //聲明函數(shù)原型,這里有插入,刪除,查找鏈表元素的函數(shù),以及遍歷鏈表的函數(shù)
29 int ListCreate(List *list,int len);
30 int ListDestroy(List *list);
31 int ListInsert(List *list,ListNode *node);
32 int ListDelete(List *list,ListElmt data);
33 int ListTravel(List list);
34 int ListFindElement(List list,ListElmt data);
35
36 #endif /*CIRCLE_LIST_H*/
1 /* **************************
2 * Soure file of Cirecle List
3 * *************************/
4
5 #include"CircleList.h"
6
7 //實現(xiàn)List的函數(shù),為了方便,放到了主函數(shù)所在的文件中,最好是單獨建立實現(xiàn)函數(shù)的源文件
8
9 //創(chuàng)建List Node,創(chuàng)建一個長度為len的鏈表,其中有一個鏈表頭,鏈表中結(jié)點個數(shù)為len
10 int ListCreate(List *list,int len)
11 {
12 ListNode *l = NULL;
13 ListNode *p = NULL;
14
15 l = (ListNode*)malloc(sizeof(ListNode)); //先創(chuàng)建頭結(jié)點
16
17 if(NULL == l) //分配成功后才能對它進(jìn)行操作
18 return FAILE;
19
20 *list = l; //創(chuàng)建頭結(jié)點,并且初始化
21 l->data = 0;
22 l->next = l; //循環(huán)鏈表,首尾相連
23 #ifdef DEBUG
24 size += 1;
25 #endif
26
27 while(len-- > 0 )
28 {
29 p = (ListNode*)malloc(sizeof(ListNode)); //新創(chuàng)建結(jié)點
30
31 if(NULL != p)
32 {
33 p->next = l->next;
34 l->next = p;
35 l = p;
36 l->data = 0; //結(jié)點中的元素初始化為0,這里的data是Int類型
37 }
38 #ifdef DEBUG
39 size += 1;
40 #endif
41 }
42
43 return SUCCESS;
44 }
45
46 //刪除List,從鏈表頭開始刪除,每次刪除一個結(jié)點,直到所有結(jié)點都刪除為止,此時為空鏈表,只剩下頭結(jié)點
47 int ListDestroy(List *list)
48 {
49 ListNode *l = NULL;
50 ListNode *p = NULL;
51
52 if(NULL == *list) //空鏈表時不進(jìn)行刪除操作
53 {
54 printf("the list is empty \n");
55 return FAILE;
56 }
57
58 l = (*list)->next;
59 #ifdef DEBUG
60 size -= 1;
61 printf(" a delete a node in the list \n");
62 #endif
63 while(l != *list) //從鏈表頭結(jié)點的下一個結(jié)點開始,一個結(jié)點接著一個結(jié)點地刪除
64 {
65 p = l->next;
66 free(l);
67 l = p;
68 #ifdef DEBUG
69 size -= 1;
70 printf("delete a node in the list \n");
71 #endif
72 }
73 free(*list); //釋放頭結(jié)點
74 *list = NULL;
75
76 return SUCCESS;
77 }
78
79 //向鏈表中插入結(jié)點,插入時從鏈表尾部插入,每次插入一個結(jié)點.
80 int ListInsert(List *list,ListNode *node)
81 {
82 ListNode *l = NULL;
83
84 if(NULL == *list)
85 {
86 printf("this is a empty list, can't be insered \n");
87 return FAILE;
88 }
89
90 l = (*list)->next;
91 // while(l != *list) //遍歷鏈表到表尾
92 // l = l->next;
93
94 // l = node; //在表尾插入結(jié)點
95 // l->next =*list;
96
97 (*list)->next = node; //在表頭,也就是頭結(jié)點后面插入結(jié)點,省去遍歷鏈表的時間,這是有頭結(jié)點的好處
98 node->next = l;
99
100 #ifdef DEBUG
101 size += 1;
102 #endif
103 return SUCCESS;
104 }
105
106 //刪除鏈表中包含data的結(jié)點
107 int ListDelete(List *list,ListElmt data)
108 {
109 int flag = 0;
110 int result = FAILE;
111 ListNode *current = NULL;
112 ListNode *next = NULL;
113
114 if(NULL == *list) //空鏈表沒有結(jié)點,不能刪除結(jié)點
115 {
116 printf("this is a empty list, can't be deleted \n");
117 return FAILE;
118 }
119
120 current = *list;
121 next = (*list)->next;
122
123 while(next != current) //依次遍歷鏈表,查找被刪除的元素,如果找到則刪除結(jié)點,并且停止遍歷鏈表
124 {
125 if(data == next->data)
126 {
127 current->next = next->next;
128 free(next);
129 next = NULL;
130 flag = 1;
131 #ifdef DEBUG
132 size -= 1;
133 #endif
134 break;
135 }
136 current = next;
137 next = next->next;
138 }
139
140 if( 1 == flag )
141 result = SUCCESS;
142 else
143 result = FAILE;
144
145 return result;
146 }
147
148 //遍歷鏈表,顯示鏈表中的每個結(jié)點的data
149 int ListTravel(List list)
150 {
151 ListNode *l = NULL;
152
153 if(NULL == list) //空鏈表直接返回
154 {
155 printf("It is a empyt list \n");
156 return FAILE;
157 }
158
159 l = list->next;
160
161 while(list != l) //遍歷鏈表,并且顯示鏈表中的data
162 {
163 printf("%d \n",l->data);
164 l = l->next;
165 }
166
167 #ifdef DEBUG
168 printf("list size: %d \n",size);
169 #endif
170 return SUCCESS;
171 }
172
173 //查找鏈表中是否包含值為data的結(jié)點
174 int ListFindElement(List list,ListElmt data)
175 {
176 ListNode *l = NULL;
177 int result = FAILE;
178
179 if(NULL == list) //空鏈表直接返回
180 {
181 printf("It is a empyt list \n");
182 return FAILE;
183 }
184
185 l = list->next;
186 while(list != l) //依次遍歷鏈表,查找值為data的結(jié)點
187 {
188 if(data == l->data) //找到后停止遍歷鏈表,否則繼續(xù)遍歷鏈表
189 {
190 result = SUCCESS;
191 break;
192 }
193 else
194 l = l->next;
195 }
196
197 return result;
198 }
199
200 int main()
201 {
202 int result = FAILE;
203 int len = 3;
204 ListNode *node = NULL; //node必須是指針,而且要用malloc分配空間,因為要使free釋放
205 List list = NULL; //創(chuàng)建一個指向鏈表的空指針
206
207 node = (ListNode *)malloc(sizeof(ListNode));
208 if(NULL != node)
209 {
210 node->data = 1;
211 node->next = NULL;
212 }
213
214 result = ListCreate(&list,len); //創(chuàng)建一個長度為Len的鏈表
215 if(result == SUCCESS)
216 ListTravel(list);
217
218 printf("Insert a node into list \n");
219 ListInsert(&list,node);
220 ListTravel(list);
221
222 result = ListFindElement(list,0);
223 if(result == SUCCESS )
224 printf("find it in the list \n");
225 else
226 printf("don't find it in the list \n");
227
228 printf("main delete a node in list \n");
229 result = ListDelete(&list,0);
230 if(result == SUCCESS )
231 ListTravel(list);
232
233 ListDestroy(&list);
234
235 #ifdef DEBUG
236 printf("list size: %d \n",size);
237 #endif
238 ListTravel(list);
239 return result;
240 }
各位看官,關(guān)于循環(huán)列表的例子咱們就說到這里。欲知后面還有什么例子,且聽下回分解。