各位看官們,大家好,從今天開始,我們講大型章回體科技小說 :C栗子,也就是C語言實例。閑話休提, 言歸正轉(zhuǎn)。讓我們一起talk C栗子吧!
看官們,上一回中咱們說的是鏈表以及單鏈表順序儲存方式的例子,這一回咱們繼續(xù)說單鏈表的例子,不 過這一回咱們說的是:單鏈表鏈式存儲。
看官們單鏈表的鏈式存儲,咱們在上一回已經(jīng)說過,這里就不再多說了。這一回主要舉例子,通過例子來 說明什么是單鏈表的鏈式存儲。
通過對比單鏈表的順序儲存和鏈式存儲,可以看出來。順序存儲鏈表的優(yōu)點:遍歷鏈表方便,查找也方便。 其缺點:刪除,插入元素比較繁瑣。鏈式存儲鏈表的優(yōu)點:插入,刪除元素比較方便,遍歷和查找比較繁 瑣。總體來說鏈式存儲的鏈表在實際開發(fā)中使用較多,因為它比較靈活,而且鏈表的大小可以依據(jù)需要動 態(tài)地調(diào)整,空間利用率高。
看官們,詳細的代碼如下,請大家參考。關于代碼有以下幾點需要大家注意:
1 /* **************************
2 * Head file of List
3 * *************************/
4 #ifndef LIST_H
5 #define 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當作List類型,實際中可以使用其它的類型或者自己定義一個List類型,不過不能是使用struct復合類型
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 /*LIST_H*/
1 /* **************************
2 * Soure file of List
3 * *************************/
4
5 #include"Ex011_List.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) //分配成功后才能對它進行操作
18 return FAILE;
19
20 *list = l; //創(chuàng)建頭結(jié)點,并且初始化
21 l->data = 0;
22 l->next = NULL;
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 l->next = p;
34 l = p;
35 l->data = 0; //結(jié)點中的元素初始化為0,這里的data是Int類型
36 l->next = NULL;
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) //空鏈表時不進行刪除操作
53 {
54 printf("the list is empty \n");
55 return FAILE;
56 }
57
58 l = (*list)->next;
59 free(*list); //釋放頭結(jié)點
60 *list = NULL;
61
62 #ifdef DEBUG
63 size -= 1;
64 printf(" a delete a node in the list \n");
65 #endif
66 while(l != NULL) //從鏈表頭結(jié)點的下一個結(jié)點開始,一個結(jié)點接著一個結(jié)點地刪除
67 {
68 p = l->next;
69 free(l);
70 l = p;
71 #ifdef DEBUG
72 size -= 1;
73 printf("delete a node in the list \n");
74 #endif
75 }
76
77 return SUCCESS;
78 }
79
80 //向鏈表中插入結(jié)點,插入時從鏈表尾部插入,每次插入一個結(jié)點.
81 int ListInsert(List *list,ListNode *node)
82 {
83 ListNode *l = NULL;
84
85 if(NULL == *list)
86 {
87 printf("this is a empty list, can't be insered \n");
88 return FAILE;
89 }
90
91 l = (*list)->next;
92 // while(l != NULL) //遍歷鏈表到表尾
93 // l = l->next;
94
95 // l = node; //在表尾插入結(jié)點
96 // l->next = NULL;
97
98 (*list)->next = node; //在表頭,也就是頭結(jié)點后面插入結(jié)點,省去遍歷鏈表的時間,這是有頭結(jié)點的好處
99 node->next = l;
100
101 #ifdef DEBUG
102 size += 1;
103 #endif
104 return SUCCESS;
105 }
106
107 //刪除鏈表中包含data的結(jié)點
108 int ListDelete(List *list,ListElmt data)
109 {
110 int flag = 0;
111 int result = FAILE;
112 ListNode *current = NULL;
113 ListNode *next = NULL;
114
115 if(NULL == *list) //空鏈表沒有結(jié)點,不能刪除結(jié)點
116 {
117 printf("this is a empty list, can't be deleted \n");
118 return FAILE;
119 }
120
121 current = *list;
122 next = (*list)->next;
123
124 while(next != NULL) //依次遍歷鏈表,查找被刪除的元素,如果找到則刪除結(jié)點,并且停止遍歷鏈表
125 {
126 if(data == next->data)
127 {
128 current->next = next->next;
129 free(next);
130 next = NULL;
131 flag = 1;
132 #ifdef DEBUG
133 size -= 1;
134 #endif
135 break;
136 }
137 current = next;
138 next = next->next;
139 }
140
141 if( 1 == flag )
142 result = SUCCESS;
143 else
144 result = FAILE;
145
146 return result;
147 }
148
149 //遍歷鏈表,顯示鏈表中的每個結(jié)點的data
150 int ListTravel(List list)
151 {
152 ListNode *l = NULL;
153
154 if(NULL == list) //空鏈表直接返回
155 {
156 printf("It is a empyt list \n");
157 return FAILE;
158 }
159
160 l = list->next;
161
162 while(NULL != l) //遍歷鏈表,并且顯示鏈表中的data
163 {
164 printf("%d \n",l->data);
165 l = l->next;
166 }
167
168 #ifdef DEBUG
169 printf("list size: %d \n",size);
170 #endif
171 return SUCCESS;
172 }
173
174 //查找鏈表中是否包含值為data的結(jié)點
175 int ListFindElement(List list,ListElmt data)
176 {
177 ListNode *l = NULL;
178 int result = FAILE;
179
180 if(NULL == list) //空鏈表直接返回
181 {
182 printf("It is a empyt list \n");
183 return FAILE;
184 }
185
186 l = list->next;
187 while(NULL != l) //依次遍歷鏈表,查找值為data的結(jié)點
188 {
189 if(data == l->data) //找到后停止遍歷鏈表,否則繼續(xù)遍歷鏈表
190 {
191 result = SUCCESS;
192 break;
193 }
194 else
195 l = l->next;
196 }
197
198 return result;
199 }
200
201 int main()
202 {
203 int result = FAILE;
204 int len = 3;
205 ListNode *node = NULL; //node必須是指針,而且要用malloc分配空間,因為要使free釋放
206 List list = NULL; //創(chuàng)建一個指向鏈表的空指針
207
208 node = (ListNode *)malloc(sizeof(ListNode));
209 if(NULL != node)
210 {
211 node->data = 1;
212 node->next = NULL;
213 }
214
215 result = ListCreate(&list,len); //創(chuàng)建一個長度為Len的鏈表
216 if(result == SUCCESS)
217 ListTravel(list);
218
219 printf("Insert a node into list \n");
220 ListInsert(&list,node);
221 ListTravel(list);
222
223 result = ListFindElement(list,0);
224 if(result == SUCCESS )
225 printf("find it in the list \n");
226 else
227 printf("don't find it in the list \n");
228
229 printf("main delete a node in list \n");
230 result = ListDelete(&list,1);
231 if(result == SUCCESS )
232 ListTravel(list);
233
234 ListDestroy(&list);
235
236 #ifdef DEBUG
237 printf("list size: %d \n",size);
238 #endif
239 ListTravel(list);
240 return result;
241 }
各位看官,關于單鏈表鏈式存儲的例子咱們就說到這里。欲知后面還有什么例子,且聽下回分解。