数据结构基础之单链表

古城微笑少年丶 2022-08-09 17:39 196阅读 0赞

**数据结构基础之单链表**

对单链表的建立，插入，删除，逆序，打印元素做一个小小的总结，不过我不觉得这些东西在具体的工作后到底能发挥什么作用，因为强大的STL已经把这些都做好了，我们只需要明白在什么场合使用哪一个STL就可以了。链表有一个数据域，有一个指针域，它的操作其实就是对指针域的操作，无非是指来指去而已。也许这些能反映出一个人的思维敏捷度，以及扎实的编程基础吧。

但是我想说的是这些玩意在你头脑比较清楚的时候写这个很简单，但是当你烦躁的时候，不好写吧，除非你经常写这个。单链表看着简单，但是不见得能写的正确。

该代码经过验证，测试正确，但是代码中不免有错误之处，或者哪些部分写的不好，希望高手能指出来，不胜感激。因为代码必须经过验证，那些没有经过验证的代码是不负责任的代码。在代码中我加了详细的注释。

**\[cpp\]**  [view plain][] [copy][view plain]

1.  \#include <stdio.h>  
2.  \#include <string>  
3.  \#include <iostream>  
4.    
5.  **using** **namespace** std;  
6.    
7.  **typedef** **struct** NODE\_STRU  
8.  \{  
9.      **int** data;//数据域  
10.     **struct** NODE\_STRU \*next;//指针域  
11. \}NODE;  
12.   
13. //创建单链表  
14. NODE \*Create()  
15. \{  
16.     NODE \*head, \*p, \*s;//head表示头结点，p表示当前节点，s表示添加的新节点  
17.     **int** input\_data;  
18.     **int** cycle\_flag = 1;  
19.     head = (NODE\*)malloc(**sizeof**(NODE));//首先为头结点分配空间  
20.     p = head;//当前节点指向头结点  
21.   
22.     **while**(cycle\_flag)  
23.     \{  
24.         cout << "please input data(if input 0, cycle over!):"<< endl;  
25.         cin >> input\_data;  
26.         **if**(0 != input\_data)  
27.         \{  
28.             s = (NODE\*)malloc(**sizeof**(NODE));//为新添加的数据分配节点空间  
29.             s->data = input\_data;  
30.             p->next = s;//当前节点的下一个节点指向新节点  
31.             p = s;//将当前节点指向新节点  
32.         \}  
33.         **else**  
34.         \{  
35.             cycle\_flag = 0;  
36.         \}  
37.     \}  
38.   
39.     head = head->next;//由于头结点没有数据，使头结点指向下一个节点，即指向第一个真正的节点  
40.     p->next = NULL;//数据插入完成后，当前节点也跑到了最后，使它的下一个节点置为NULL，表示节点完成  
41.   
42.     **return** head;  
43. \}  
44.   
45. //单链表测长,这个很简单，只需判断当前节点（初始化当前节点为头结点）是不是为空，如果不为空指向下一个节点，并计数就可以了  
46. **int** Length(NODE \*head)  
47. \{  
48.     **int** length = 0;  
49.     NODE \*p = head;  
50.     **while**(p != NULL)  
51.     \{  
52.         p = p->next;  
53.         length++;  
54.     \}  
55.     **return** length;  
56. \}  
57.   
58. //打印单链表，这个也很简单，在当前节点（初始化当前节点为头结点）不为空时候，打印出来，并使得当前节点指向下一个节点即可  
59. **void** Print(NODE \*head)  
60. \{  
61.     NODE \*p = head;  
62.     **int** length = Length(head);  
63.     cout << "link length is: " << length << endl;  
64.     **while**(p != NULL)  
65.     \{  
66.         cout << "data: " << p->data << "\\t";  
67.         p = p->next;  
68.     \}  
69.   
70. \}  
71.   
72. //删除节点,这里的删除节点是根据节点数据进行删除的，不是从第一个节点进行删除，也不是从最后一个节点进行删除  
73. //p->next = p->next->next  
74. NODE \*Del(NODE \*head, **int** num)  
75. \{  
76.     NODE \*p1, \*p2;//p1表示当前节点，初始化时指向头结点  
77.     p1 = head;  
78.   
79.     **while**(num != p1->data && p1->next != NULL)//如果当前节点的数据域与要删除的数据不相等，使当前节点指向下一个节点  
80.     \{  
81.         p2 = p1;//在未找到节点时指针指向下一个节点前，先保存该节点  
82.         p1 = p1->next;  
83.     \}  
84.   
85.     **if**(num == p1->data)//如果当前节点数据域与要删除的数据相等  
86.     \{  
87.         **if**(p1 == head)//如果当前节点为头结点，将头结点指向当前节点的下一个节点，并释放当前节点  
88.         \{  
89.             head = p1->next;  
90.             free(p1);  
91.         \}  
92.         **else**//如果当前节点为中间节点，使当前节点指向下一个节点，注意：这里不能使用p1->next=p1->next->next,使用之前保存的节点  
93.             p2->next = p1->next;  
94.     \}  
95.     **else**  
96.         cout << num << "can not find in link!" << endl;  
97.   
98.     **return** head;  
99. \}  
100.   
101. //插入节点，在这里只在链表的结尾进行插入  
102. NODE \*Insert(NODE \*head, **int** num)  
103. \{  
104.     NODE \*p0, \*p1, \*p2;//p0表示新插入的节点，p1表示当前节点，初始化的时候指向头结点，p2用于保存当前节点  
105.     p1 = head;  
106.     p0 = (NODE \*)malloc(**sizeof**(NODE));  
107.     p0->data = num;  
108.   
109.     **while**(p1->next != NULL)//如果当前节点的下一个节点不为空，当前节点指向下一个节点，这样当前节点最后为最后一个节点  
110.     \{  
111.         p2 = p1;  
112.         p1 = p1->next;  
113.     \}  
114.     p1->next = p0;  
115.     p0->next = NULL;  
116.   
117.     **return** head;  
118. \}  
119.   
120. //进行排序，其实就是简单的冒泡排序，时间复杂度为O(n2),空间复杂度为O(1),稳定  
121. NODE \*Sort(NODE \*head)  
122. \{  
123.     NODE \*p;  
124.     **if**(head == NULL || head->next == NULL)  
125.         **return** head;  
126.   
127.     **int** length = Length(head);//得到链表的长度，用于遍历  
128.     **for**(**int** i=1; i<length; i++)  
129.     \{  
130.         p = head;  
131.         **for**(**int** j=0; j<length-i; j++)  
132.         \{  
133.             **if**(p->data > p->next->data)  
134.             \{  
135.                 **int** temp = p->data;  
136.                 p->data = p->next->data;  
137.                 p->next->data = temp;  
138.             \}  
139.             p = p->next;  
140.         \}  
141.     \}  
142.   
143.     **return** head;  
144. \}  
145.   
146. //链表逆序  
147. NODE \*Reverse(NODE \*head)  
148. \{  
149.     **if**(head == NULL || head->next == NULL)  
150.         **return** head;  
151.     //这样来实现，在链表中一次从链表尾删除节点，然后在新建立的链表中插入节点（尾插法）  
152.     **int** length = Length(head);  
153.     **int** a\[length\];  
154.     **int** i = 0;  
155.     NODE \*p = head;  
156.     **while**(p != NULL)  
157.     \{  
158.         a\[i\] = p->data;  
159.         i++;  
160.         p = p->next;  
161.     \}  
162.   
163.     **for**(**int** j=0; j<length; j++)//暂时用于测试  
164.         cout << j << ":" << a\[j\]<<"\\n";  
165.   
166.     NODE \*newhead, \*link, \*s;  
167.     newhead = (NODE \*)malloc(**sizeof**(NODE));  
168.     link = newhead;  
169.     **for**(**int** k=length-1; k>=0; k--)  
170.     \{  
171.          s = (NODE \*)malloc(**sizeof**(NODE));  
172.          s->data = a\[k\];  
173.          link->next = s;  
174.          link = s;  
175.     \}  
176.     newhead = newhead->next;  
177.     link->next = NULL;  
178.   
179.     **return** newhead;  
180. \}  
181.   
182. //求单链表的中间节点  
183. **void** SearchMid(NODE\* head)  
184. \{  
185.     cout << "head data: " << head->data<< "\\n";  
186.     NODE \*tmp1 = head;  
187.     NODE \*tmp2 = head;  
188.     NODE \*mid;  
189.     **while**(tmp1->next != NULL && tmp1->next->next != NULL)  
190.     \{  
191.         tmp1 = tmp1->next->next;  
192.         tmp2 = tmp2->next;  
193.         cout << "tmp1:" << tmp1->data<< ",tmp2:" << tmp2->data<<"\\n";  
194.     \}  
195.     mid = tmp2;  
196.     cout << "SearchMid mid data: " << mid->data;  
197. \}  
198.   
199. **int** main(**int** argc, **char** \*argv\[\])  
200. \{  
201.     cout << "create link...\\n" << endl;  
202.     NODE \*p = Create();  
203.     cout << "print link...\\n" << endl;  
204.     Print(p);  
205.   
206.     **int** delnode;  
207.     cout << "\\ninput delete node: ";  
208.     cin >> delnode;  
209.     cout << "\\ndelete node " << delnode << endl;  
210.     Del(p, delnode);  
211.     cout << "print link..." << endl;  
212.     Print(p);  
213.   
214.     cout << "\\ninsert link...\\n";  
215.     Insert(p, 20);  
216.     Print(p);  
217.   
218.     cout <<"\\nsort from low to high...";  
219.     Sort(p);  
220.     Print(p);  
221.   
222.     cout << "\\nreverse...\\n";  
223.     NODE \*revlink = Reverse(p);  
224.     Print(revlink);  
225.   
226.     cout << "\\nfind mid node data...\\n";  
227.     SearchMid(p);  
228.   
229.     **return** 0;  
230. \}

运行结果：

![SouthEast][]

![SouthEast 1][]

如是转载，请指明原出处：[http://blog.csdn.net/feitianxuxue][http_blog.csdn.net_feitianxuxue]，谢谢合作！

[view plain]: http://blog.csdn.net/feitianxuxue/article/details/9989591#
[SouthEast]: /images/20220731/ea5d3d94e8894aac8fd112e10d7876f3.png
[SouthEast 1]: /images/20220731/98b80681378447f19616c7102b251966.png
[http_blog.csdn.net_feitianxuxue]: http://blog.csdn.net/feitianxuxue