單鏈表，單鏈表的基本操作
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<malloc.h>
4
5 typedef int Elemtype;
6
7 typedef struct Node{
8 int data;
9 struct Node* next;
10 }Node;
11
12 typedef struct Node* LinkList;
13
14 void InitLinkList(LinkList *L);
15 void DestoryList(LinkList* L);
16 void ClearList(LinkList *L);
17 void HeadCreateList(LinkList*,int);
18 void TailCreateList(LinkList*,int);
19 void DisplayList(LinkList);
20
21 //void InitLinkList(Node** L){
22 // *L = (LinkList)malloc(sizeof(struct Node));
23 // (*L)->next = NULL;
24 // //alternation
25 //}
26 void InitList(LinkList *L){
27 *L = (LinkList)malloc(sizeof(struct Node));
28 (*L)->next = NULL;
29 }
30 void DestoryList(LinkList* L){
31 /*
32 LinkList p = *L,q;
33 printf("%d %d\n",p,*L); //p == *L == 7279912
34 while(p){
35 q = p->next;
36 free(p);
37 p = q; //last step p = NULL
38 }
39 printf("%d %d",p,*L); //p = 0;*L = 7279912
40 free(*L);
41 printf("%d ",*L); //*L = 7279912
42 analise the reason for error by the result of "printf"
43 free(p) is release the block of memory pointed by P,
44 dose not change pointer p itself. NULL == 0
45 */
46 LinkList q;
47 while(*L){
48 q = (*L)->next;
49 free(*L);
50 *L = q;
51 }
52 }
53 void ClearList(LinkList *L){
54 //ClearList(&L);
55 // LinkList p = *L;
56 // LinkList q;
57 //
58 // TailCreateList(&L,4);
59 // DisplayList(L);
60 // ClearList(&L);
61 // TailCreateList(&L,4);
62
63 LinkList p = (*L)->next;
64 LinkList q;
65 while(p){
66 q = p -> next;
67 free(p);
68 p = q;
69 }
70 (*L)->next = NULL;
71 printf("LinkList has been clear!\n");
72 }
73 void ListEmpty(LinkList L){
74 if(L->next == NULL)
75 printf("List empty!\n");
76 else
77 printf("Exit Element in List\n");
78 }
79 int ListLength(LinkList L){
80 LinkList p = L->next;
81 int count = 0;
82 while(p){
83 count+=1;
84 p = p->next;
85 }
86 return count;
87 }
88 int GetElem(LinkList L,int index,int *r){
89 int length = ListLength(L);
90 if(index < 1 || index > length){
91 return 0; //failed
92 }else{
93 int j = 0;
94 while(j<index){
95 L = L->next;
96 j++;
97 }
98 *r = L->data;
99 return 1;
100 }
101 }
102 void GetPriorElem(LinkList L,int current_elem,int *priorElement){
103 /*
104 LinkList p = L->next;
105 LinkList q;
106 if(p == NULL){
107 printf("List is Empty!\n");
108 exit(1);
109 }
110 if(p->data == current_elem){
111 printf("the current element is first!\n");
112 exit(1);
113 }
114 q = p->next;
115 while(q && q->data != current_elem){
116 p = q;q = q->next;
117 }
118 if(q == NULL){
119 printf("there is no current in List!\n");
120 exit(1);
121 }
122 else
123 *priorElement = p->data;
124 */
125 /*
126 the promise of the following code is that the
127 current_element is not the first element of the
128 list and does not consider the case of the list
129 for NULL
130 */
131 LinkList p = L->next; //p point first node
132 LinkList q;
133 while(p->next){
134 q = p->next;
135 if(q->data == current_elem){
136 *priorElement = p->data;
137 break;
138 }
139 p = q;
140 }
141 if(p->next == NULL)
142 printf("there is no current_element in List\n");
143 }
144 void GetNextElem(LinkList L,int current_elem,int* next_elem){
145 LinkList p = L->next;
146 LinkList q;
147 if(p == NULL){
148 printf("List is Empty!\n");
149 exit(1);
150 }
151 while(p->next){
152 q = p->next;
153 if(p->data == current_elem){
154 *next_elem = q->data;
155 return;
156 }
157 p = q;
158 }
159 printf("GetNextElement is Failed!\n");
160 }
161 void HeadCreateList(LinkList* L,int n){
162 LinkList s;
163 int i;
164 int e;
165 for(i = 1;i <= n; i++){
166 printf("enter %d integer: ",i);
167 scanf("%d",&e);
168 s = (LinkList)malloc(sizeof(struct Node));
169 s->data = e;
170 s->next = (*L)->next;
171 (*L)->next = s;
172 }
173 printf("\n");
174 }
175 void TailCreateList(LinkList* L,int n){
176 LinkList tail = *L;
177 LinkList s;
178 int i;
179 int e;
180 for(i = 1;i <= n; i++){
181 printf("enter %d integer: ",i);
182 scanf("%d",&e);
183 s = (LinkList)malloc(sizeof(struct Node));
184 s->data = e;
185 tail->next = s;
186 s->next = NULL;
187 tail = s;
188 }
189 printf("\n");
190 }
191 void ListInsert(LinkList* L,int index,int e){
192 /*
193 //insert element before index
194 LinkList q;
195 LinkList p = *L;
196 LinkList s;
197 int count = 0;
198 while(p->next){
199 q = p->next;
200 count += 1;
201 if(count == index){
202 s = (LinkList)malloc(sizeof(struct Node));
203 s -> data = e;
204 p->next = s;
205 s->next = q;
206 break;
207 }
208 p = q;
209 }
210 if(p->next == NULL){
211 printf("InsertList Index Error!\n");
212 }
213 */
214 //options
215 LinkList p = *L;
216 LinkList s;
217 int count = 0;
218 while(p && count<index-1){
219 p = p->next;
220 count += 1;
221 }
222 if(p){
223 s = (LinkList)malloc(sizeof(struct Node));
224 s->data = e;
225 s->next = p->next;
226 p->next = s;
227 }
228 if(p == NULL){
229 printf("InsertList Index Error!\n");
230 }
231 }
232 void ListDelete(LinkList *L,int index,int* e){
233 LinkList p = *L;
234 int count = 0;
235 while(p && count < index - 1){
236 p = p->next;
237 count += 1;
238 }
239 if(p){
240 if(p->next){
241 *e = p->next->data;
242 p->next = p->next->next;
243 }
244 else
245 printf("DeleteList Index Error\n");
246 }
247 if(p == NULL)
248 printf("DeleteList Index Error\n");
249 }
250 void DisplayList(LinkList L){
251 if(L == NULL){
252 printf("List has been destory!\n");
253 }else
254 {
255 LinkList p = L;
256 while(p -> next){
257 printf("%d ",p->next->data);
258 p = p->next;
259 }
260 printf("\n********displayList executed!\n");
261 }
262 }
263 void main(){
264 // Node L;
265 // LinkList L1 = &L;
266 // InitLinkList(&L1);
267
268 LinkList L;
269 InitList(&L);
270 TailCreateList(&L,4);
271 DisplayList(L);
272 ClearList(&L);
273 ListEmpty(L);
274 DisplayList(L);
275 DestoryList(&L);
276 DisplayList(L);
277
278 InitList(&L);
279 TailCreateList(&L,5);
280 printf("Length of List is: %d\n",ListLength(L));
281 DisplayList(L);
282
283 int r0;
284 if(GetElem(L,5,&r0)){
285 printf("getelement index=5 is : %d\n",r0);
286 }
287 else
288 printf("getelement index=5 is Failed\n");
289
290 if(GetElem(L,6,&r0)){
291 printf("getelement index=6 is : %d\n",r0);
292 }
293 else
294 printf("getelement index=6 is Failed\n");
295
296 int r1;
297 GetPriorElem(L,3,&r1);
298 printf("the result of GetPriorElement(3) is: %d\n",r1);
299
300 int r2;
301 GetNextElem(L,3,&r2);
302 printf("the result of GetNextElement(3) is: %d\n",r2);
303 ListInsert(&L,5,999);
304 DisplayList(L);
305
306 int r3;
307 ListDelete(&L,2,&r3);
308 DisplayList(L);
309 printf("execute ListDelete index=2 is %d\n",r3);
310 }
