C语言一个单链表的实现

   

[cpp] view plaincopy

1. #include<stdio.h>  
2. #include<malloc.h>  
3.   
4. typedef int Item;//定义数据项类型  
5. typedef struct node * PNode;//定义节点指针  
6. //节点的定义  
7. typedef struct node  
8. {  
9.     Item item;//数据域  
10.     PNode next;//链域  
11.       
12. }Node,* SList;  
13.   
14. /* 
15. int SL_Creat(SList *p_list,int size) 
16. 参数 
17. p_list：指向一个链表指针，此处传入表头地址 
18. size：要创建的链表分配的数据元素空间个数，不包含头节点 
19. 返回值 
20. 若成功返回1，否则返回0。 
21. 功能 
22. 该函数的功能是创建一个大小为size的链表并把链表的头指针赋给p_lsit所指的链表指针。 
23.  
24. */  
25. int SL_Creat(SList *p_list,int size)  
26. {  
27.     PNode p=NULL;  
28.     int i;  
29.   
30.     *p_list = (SList)malloc(sizeof(Node));  
31.     if(*p_list==NULL)  
32.         return -1;  
33.     (*p_list)->next = NULL;  
34.     for(i=size;i>0;i--)  
35.     {  
36.         p = (PNode)malloc(sizeof(Node));  
37.         if(p==NULL)  
38.             return -1;  
39.         p->item = 0;  
40.         p->next = (*p_list)->next;  
41.         (*p_list)->next = p;  
42.     }  
43.     return 1;  
44. }  
45. /* 
46. int SL_Insert(SList list,int pos,Item item) 
47. 参数 
48. list：要插入数据的单链表 
49. int：指定要插入元素的位置，从1开始计数 
50. item:要插入的数据项 
51. 返回值 
52. 若成功返回1，否则返回-1。 
53. 功能 
54. 该函数的功能是在链表list的pos位置插入新元素，其值为item。 
55.  
56. */  
57. int SL_Insert(SList list,int pos,Item item)  
58. {  
59.     PNode p,q;  
60.     int i;  
61.   
62.     p = list;  
63.     i = 0;  
64.     while(p!=NULL && i<pos-1)//将指针p移动到要插入元素位置之前  
65.     {  
66.         p = p->next;  
67.         i++;//i记录p指向的是第几个位置  
68.     }  
69.     if(p==NULL || i > pos-1)  
70.         return -1;  
71.     q = (Node *)malloc(sizeof(Node));//未插入节点分配内存  
72.     if(q!=NULL)//若内存分配成功，将节点插入指定位置  
73.     {  
74.         q->item = item;  
75.         q->next = p->next;  
76.         p->next = q;  
77.         return 1;  
78.     }  
79.     else  
80.     {  
81.         return -1;  
82.     }  
83. }  
84. /* 
85. int SL_GetItem(SList list,int pos,Item *p_item) 
86. 参数 
87. list：要获取数据项所在的单链表 
88. int：指定要获取元素在单链表中的位置 
89. p_item:指向要接收数据项的变量 
90. 返回值 
91. 若成功返回1，否则返回-1。 
92. 功能 
93. 该函数的功能是获取在链表list的pos位置的元素的数据项，其值赋给p_item所指的变量。 
94.  
95. */  
96. int SL_GetItem(SList list,int pos,Item *p_item)  
97. {  
98.     PNode p;  
99.     int i;    
100.   
101.     p = list;  
102.     i = 0;  
103.     while(p!=NULL && i<pos)//将指针p移动到要返回的元素位置  
104.     {  
105.         p = p->next;  
106.         i++;//i记录p指向的是第几个位置  
107.     }  
108.     if((p==NULL)||(i>pos))  
109.     {  
110.         return -1;  
111.     }  
112.     *p_item = p->item;  
113.     return 1;  
114. }  
115. /* 
116. int SL_Delete(SList list,int pos,Item * p_item) 
117. 参数 
118. list：要删除元素所在的单链表 
119. int：指定要删除元素在单链表中的位置 
120. p_item:指向接收删除元素的数据项的变量 
121. 返回值 
122. 若成功返回1，否则返回-1。 
123. 功能 
124. 该函数的功能是删除在链表list的pos位置的元素，其值赋给p_item所指的变量。 
125.  
126. */  
127. int SL_Delete(SList list,int pos,Item * p_item)  
128. {  
129.     PNode p,q;  
130.     int i;  
131.     p = list;  
132.     i = 0;  
133.     while(p!=NULL && i<pos-1)//将指针p移动到要插入元素位置之前  
134.     {  
135.         p = p->next;  
136.         i++;//i记录p指向的是第几个位置  
137.     }  
138.     if(p->next==NULL || i > pos-1)  
139.         return -1;  
140.     q = p->next;  
141.     p->next = q->next;  
142.     if(p_item != NULL)  
143.         *p_item = q->item;  
144.     free(q);  
145.     return 1;  
146. }  
147. /* 
148. int SL_SetItem(SList list,int pos,Item item) 
149. 参数 
150. list：要设置元素所在的单链表 
151. int：指定要设置元素在单链表中的位置 
152. p_item:要设置元素的数据项的值 
153. 返回值 
154. 若成功返回1，否则返回-1。 
155. 功能 
156. 该函数的功能是将链表list的pos位置的元素的数据项设置为item。 
157.  
158. */  
159. int SL_SetItem(SList list,int pos,Item item)  
160. {  
161.     PNode p=NULL;  
162.     int i;  
163.     p = list;  
164.     i = 0;  
165.     while(p!=NULL && i<pos)//将指针p移动到要插入元素位置之前  
166.     {  
167.         p = p->next;  
168.         i++;//i记录p指向的是第几个位置  
169.     }  
170.     if(p==NULL || i > pos)  
171.         return -1;  
172.     p->item = item;  
173.     return 1;  
174.   
175. }  
176. /* 
177. int SL_Find(SList list,int *pos,Item item) 
178. 参数 
179. list：要查找元素所在的单链表 
180. int：指向要存储的查得的元素的位置的变量 
181. p_item:要查找元素的数据项的值 
182. 返回值 
183. 若成功返回1，否则返回-1。 
184. 功能 
185. 该函数的功能是在链表list中查找数据项为item的元素，将其位置值赋给pos所指的变量。 
186.  
187. */  
188. int SL_Find(SList list,int *pos,Item item)  
189. {  
190.     PNode p;  
191.     int i;  
192.     p = list;  
193.     i = 0;  
194.     while(p!=NULL && p->item!=item)//将指针p移动到要插入元素位置之前  
195.     {  
196.         p = p->next;  
197.         i++;//i记录p指向的是第几个位置  
198.         if(p->item == item)  
199.         {  
200.             *pos = i; //返回查询到的位置  
201.             return 1;  
202.         }  
203.     }  
204.     return -1;    
205. }  
206. /* 
207. int SL_Empty(SList list) 
208. 参数 
209. list：要判断的单链表 
210. 返回值 
211. 若为空则返回1，否则返回 0。 
212. 功能 
213. 该函数的功能是判断链表list是否为空表。 
214.  
215. */  
216. int SL_Empty(SList list)  
217. {  
218.     PNode p;  
219.     p = list;  
220.     if(p->next == NULL)  
221.         return 1;  
222.     return 0;  
223. }  
224. /* 
225. int SL_Size(SList list) 
226. 参数 
227. list：要查找的单链表 
228. 返回值 
229. 返回包含节点的个数。 
230. 功能 
231. 该函数的功能是返回链表list中节点的个数，包含头节点。 
232.  
233. */  
234. int SL_Size(SList list)  
235. {  
236.     PNode p;  
237.     int i;  
238.   
239.     p = list;  
240.     i = 0;  
241.     while(p!=NULL)  
242.     {  
243.         p = p->next;  
244.         i++;  
245.           
246.     }  
247.     return i;  
248. }  
249. /* 
250. int SL_Clear(SList *p_list) 
251. 参数 
252. p_list：指向要清除的单链表 
253. 返回值 
254. 成功返回值为1。 
255. 功能 
256. 该函数的功能是清除链表的所有节点，包含头节点。 
257.  
258. */  
259. int SL_Clear(SList *p_list)  
260. {  
261.     PNode p,q;  
262.     int i;  
263.   
264.     p = *p_list;  
265.     i = 0;  
266.     while(p!=NULL)  
267.     {  
268.         q = p->next;//借助于q存储p的链域，否则释放p后无法引用  
269.         free(p);  
270.         p = q;  
271.     }  
272.     *p_list = NULL;//将所指的链表指针设为NULL  
273.       
274.     return 1;  
275. }