数据结构基础之单链表

安哥网络

数据结构基础之单链表

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

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

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

1. #include
   
2. #include
   
3. #include
   
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 << "        ";
    
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]<<"";
     
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<< "";
     
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<<"";
     
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..." << endl;
     
202.     NODE *p = Create();
     
203.     cout << "print link..." << endl;
     
204.     Print(p);
     
205. 
     
206.     int delnode;
     
207.     cout << "input delete node: ";
     
208.     cin >> delnode;
     
209.     cout << "delete node " << delnode << endl;
     
210.     Del(p, delnode);
     
211.     cout << "print link..." << endl;
     
212.     Print(p);
     
213. 
     
214.     cout << "insert link...";
     
215.     Insert(p, 20);
     
216.     Print(p);
     
217. 
     
218.     cout <<"sort from low to high...";
     
219.     Sort(p);
     
220.     Print(p);
     
221. 
     
222.     cout << "reverse...";
     
223.     NODE *revlink = Reverse(p);
     
224.     Print(revlink);
     
225. 
     
226.     cout << "find mid node data...";
     
227.     SearchMid(p);
     
228. 
     
229.     return 0;
     
230. }

复制代码

运行结果：

数据结构基础之单链表

摘自：http://blog.csdn.net/feitianxuxue/article/details/9989591