基本上关于带头结点的单链表能实现的都实现了，链表的转置写了递归和非递归，有些鸡肋的函数就没写。菜鸟一只，欢迎拍砖，高手无视。

 

1. //Code by Pnig0s1992 
2. //Date:2012,3,20 
3. #include <stdio.h> 
4. #include <Windows.h> 
5.  
6. typedef struct LinkNode 
7. { 
8.     int iElement; 
9.     struct LinkNode * pNext; 
10. }LinkNode; 
11. typedef int Element_type; 
12. typedef struct LinkNode * ptrNode; 
13. typedef ptrNode LinkList; 
14.  
15. void MakeEmpty(LinkList L);//清空单链表 
16. BOOL isEmpty(LinkList L);//判断链表是否为空 
17. BOOL isLast(ptrNode pPos,LinkList L);//判断指定结点是否为最后 
18. ptrNode FindNode(Element_type x,LinkList L);//返回指定元素值的结点 
19. ptrNode FindPrev(Element_type x,LinkList L);//返回指定元素值的前一个结点 
20. void Insert(Element_type x,ptrNode pPos);//在指定位置插入一个结点 
21. void Delete(Element_type x,LinkList L);//删除指定值的结点 
22. Element_type Retrieve(LinkList L);//返回指定结点位置的元素值 
23. void NonCurReverse(LinkList L);//单链表的逆置(非递归) 
24. void CurReverse(LinkList L);//单链表的逆置(递归) 
25. void printLinkLink(LinkList L);//打印单链表 
26. int main(int argc,char ** argv) 
27. { 
28.     LinkNode LinkHeader; 
29.     LinkHeader.pNext = NULL; 
30.     Insert(20,&LinkHeader); 
31.     Insert(40,&LinkHeader); 
32.     Insert(10,&LinkHeader); 
33.     Insert(70,&LinkHeader); 
34.     Insert(30,&LinkHeader); 
35.     Insert(50,&LinkHeader); 
36.     Insert(80,&LinkHeader); 
37.     Insert(90,&LinkHeader); 
38.     ptrNode InsertPos = FindNode(50,&LinkHeader); 
39.     Delete(20,&LinkHeader); 
40.     BOOL bResult; 
41.     bResult = isEmpty(&LinkHeader); 
42.     if(bResult) 
43.     { 
44.         printf("\nThe LinkList is empty."); 
45.     }else 
46.     { 
47.         printf("\nThe Linklink is not empty"); 
48.     } 
49.     printf("\nThe Linklist before reverse."); 
50.     printLinkLink(&LinkHeader); 
51.     NonCurReverse(&LinkHeader); 
52.     printf("\nThe Linklist after reverse."); 
53.     printLinkLink(&LinkHeader); 
54.     CurReverse(&LinkHeader); 
55.     printf("\nThe Linklist after second reverse."); 
56.     printLinkLink(&LinkHeader); 
57.     MakeEmpty(&LinkHeader); 
58.     bResult = isEmpty(&LinkHeader); 
59.     if(bResult) 
60.     { 
61.         printf("\nThe LinkList is empty."); 
62.     }else 
63.     { 
64.         printf("\nThe Linklink is not empty"); 
65.     } 
66.     system("pause"); 
67.     return 0; 
68. } 
69. //根据指定位置插入结点 
70. void Insert(Element_type x,ptrNode pPos) 
71. { 
72.     ptrNode NewNode = (ptrNode)HeapAlloc(GetProcessHeap(),0,sizeof(LinkNode)); 
73.     if(NewNode == NULL) 
74.     { 
75.         printf("\nAlloc memory on heap failed with error:%d",GetLastError()); 
76.         return; 
77.     } 
78.     NewNode->iElement = x; 
79.     NewNode->pNext = pPos->pNext; 
80.     pPos->pNext = NewNode; 
81.     printf("\nInsert node with element %d successfully.",x); 
82. } 
83. //返回指定数值所在的结点 
84. ptrNode FindNode(Element_type x,LinkList L) 
85. { 
86.     int iTarget = x; 
87.     while(L->pNext != NULL && L->iElement != iTarget) 
88.     { 
89.         L = L->pNext; 
90.     }//注意判断条件 
91.  
92.     return L; 
93. } 
94.  
95. //删除指定数值所在的结点 
96. void Delete(Element_type x,LinkList L) 
97. { 
98.     ptrNode BeforeTarget= FindPrev(x,L); 
99.     ptrNode TargetNode = BeforeTarget->pNext; 
100.     BeforeTarget->pNext = TargetNode->pNext; 
101.     HeapFree(GetProcessHeap(),0,TargetNode); 
102.     printf("\nDelete node with element %d successfully.",x); 
103. } 
104.  
105. //返回指定值结点的前一个结点 
106. ptrNode FindPrev(Element_type x,LinkList L) 
107. { 
108.     while(L->pNext != NULL) 
109.     { 
110.         if(L->pNext->iElement == x) 
111.         { 
112.             printf("\nFind node before node with element %d successfully.",x); 
113.             return L; 
114.         } 
115.         L = L->pNext; 
116.     } 
117.     return NULL; 
118. } 
119. //判断链表是否为空 
120. BOOL isEmpty(LinkList L) 
121. { 
122.     return L->pNext == NULL; 
123. } 
124.  
125. //判断结点是否在最后 
126. BOOL isLast(ptrNode pPos,LinkList L) 
127. { 
128.     if(!isEmpty(L)) 
129.     { 
130.         return pPos->pNext == NULL; 
131.     }else 
132.     { 
133.         return TRUE; 
134.     } 
135. } 
136.  
137. //返回指定结点的元素值 
138. Element_type Retrieve(LinkList L) 
139. { 
140.     return L->iElement; 
141. } 
142.  
143. //清空链表 
144. void MakeEmpty(LinkList L) 
145. { 
146.     ptrNode pTemp = L->pNext; 
147.     L->pNext = NULL; 
148.     ptrNode pT; 
149.     while(pTemp != NULL) 
150.     { 
151.         pT = pTemp->pNext; 
152.         HeapFree(GetProcessHeap(),0,pTemp); 
153.         pTemp = pT; 
154.     } 
155.     printf("\nThe LinkList has been emptyed successfully."); 
156. } 
157.  
158. //链表的转置(非递归) 
159. void NonCurReverse(LinkList L) 
160. { 
161.     ptrNode pFirst,pSecond; 
162.     pFirst = L->pNext; 
163.     pSecond = L->pNext; 
164.     pSecond = pSecond->pNext; 
165.     pFirst->pNext = NULL; 
166.     pFirst = pSecond; 
167.     while (pFirst != NULL) 
168.     { 
169.         pSecond = pSecond->pNext; 
170.         pFirst->pNext = L->pNext; 
171.         L->pNext = pFirst; 
172.         pFirst = pSecond; 
173.     } 
174. } 
175. //递归逆置单链表(带头结点) 
176. void CurReverse(LinkList L) 
177. { 
178.     if(NULL == L || NULL == L->pNext) 
179.         return; 
180.     ptrNode q = L->pNext,r = L; 
181.     while(NULL != q && NULL != q->pNext) 
182.     { 
183.         r = q; 
184.         q = q->pNext; 
185.     } 
186.     r->pNext = NULL; 
187.     q->pNext = L->pNext; 
188.     L->pNext = q; 
189.     CurReverse(q); 
190. } 
191.  
192. //打印单链表 
193. void printLinkLink(LinkList L) 
194. { 
195.     ptrNode pFirst = L->pNext; 
196.     while(pFirst != NULL) 
197.     { 
198.         printf("%d ",pFirst ->iElement); 
199.         pFirst = pFirst->pNext; 
200.     } 
201. } 

 

本文转hackfreer51CTO博客，原文链接：http://blog.51cto.com/pnig0s1992/811016，如需转载请自行联系原作者