本文主要向大家介绍了用C++语言编写单链表的创建、删除、插入、测长、排序、逆置，通过具体的代码向大家展示，希望对大家学习C++语言有所帮助。

Code：

[cpp] view plain copy
1. #include<iostream>  
2. using namespace std;  
3.   
4. typedef struct student  
5. {  
6.     int data;  
7.     struct student *next;  
8. }node;  
9.   
10. //创建单链表  
11. node *create()  
12. {  
13.     node *head, *p, *s;  
14.     int x;  
15.     head = (node *)malloc(sizeof(node));    //先创建一个头节点，便于头指针的操作。  
16.     p = head;  
17.     printf("\nInput the data (end with '0') : ");  
18.     while(1)  
19.     {  
20.         if(scanf("%d", &x) != EOF && x != 0)  
21.         {//如果输入数据合法，则再创建一个节点；否则跳出循环。  
22.             s = (node *)malloc(sizeof(node));  
23.             s->data = x;  
24.             p->next = s;  
25.             p = s;  
26.         }  
27.         else break;  
28.     }  
29.     head = head->next;  
30.     p->next = NULL;  
31.     return head;  
32. }  
33.   
34. //计算单链表长度  
35. int length(node *head)  
36. {  
37.     int n = 0;  
38.     while(head != NULL)  
39.     {  
40.         head = head->next;  
41.         n++;  
42.     }  
43.     return n;  
44. }  
45.   
46. //打印单链表  
47. void print(node *head)  
48. {  
49.     int n = length(head);  
50.     printf("Output the list (%d records~) : ", n);  
51.     while(head != NULL)  
52.     {  
53.         printf(head->next == NULL ? "%d\n" : "%d->", head->data);  
54.         head = head->next;  
55.     }  
56. }  
57.   
58. //删除单链表节点  
59. node *del(node *head, int num)  
60. {  
61.     node *p1, *p2;  
62.     if(head == NULL) return NULL;  
63.     p1 = head;  
64.     while(num != p1->data && p1->next != NULL)  
65.     {//若当前指针所存储的值与要删除的值不符，则向后遍历，直至相等或至最后一个节点。  
66.         p2 = p1;  
67.         p1 = p1->next;  
68.     }  
69.     if(num == p1->data)  
70.     {//如果链表中存在要删除的节点，则分两种情况：在头节点处或链表中。  
71.         if(head == p1) head = p1->next;  
72.         else p2->next = p1->next;  
73.         free(p1);   //别忘了释放删除的节点哦~节约点~  
74.     }  
75.     else printf("There is no '%d' \n", num);    //找不到要删除的值。  
76.     return head;  
77. }  
78.   
79. //插入单链表节点  
80. node *insert(node *head, int num)  
81. {  
82.     node *p1, *p2, *p3;  
83.     p2 = head;  
84.     p1 = (node *)malloc(sizeof(node));  //先将要插入的节点申请下~  
85.     p1->data = num;  
86.     //思路同删除节点操作  
87.     while(num > p2->data && p2->next != NULL)   
88.     {  
89.         p3 = p2;  
90.         p2 = p2->next;  
91.     }  
92.     if(num <= p2->data)  
93.     {  
94.         if(head == p2)  
95.         {  
96.             p1->next = p2;  
97.             head = p1;  
98.         }  
99.         else  
100.         {  
101.             p3->next = p1;  
102.             p1->next = p2;  
103.         }  
104.     }  
105.     else   
106.     {//此处要细心，别忘了可以在尾部插入节点。  
107.         p2->next = p1;  
108.         p1->next = NULL;  
109.     }  
110.     return head;  
111. }  
112.   
113. //单链表排序  
114. node *sort(node *head)  
115. {  
116.     node *p;  
117.     p = head;  
118.     int n, temp;  
119.     n = length(head);  
120.     //运用冒泡排序似乎对链表排序来说是最方便的~（递增）  
121.     for(int j = 1; j < n; j++)  
122.     {  
123.         p = head;  
124.         for(int i = 0; i < n - j; i++)  
125.         {  
126.             if(p->data > p->next->data)  
127.             {  
128.                 temp = p->data;  
129.                 p->data = p->next->data;  
130.                 p->next->data = temp;  
131.             }  
132.             p = p->next;  
133.         }  
134.     }  
135.     printf("\nAfter sorting ~\n");  
136.     return head;  
137. }  
138.   
139. //单链表逆置  
140. node *reverse(node *head)  
141. {  
142.     node *p1, *p2, *p3;  
143.     p1 = head;  
144.     p2 = p1->next;  
145.     if(head == NULL || head->next == NULL) return head;  
146.     //逆置的思想：选出三个节点（第三个可能是NULL），操作前两个节点，使其逆置，而后按同样做法操作第二、三个节点和第四个节点~  
147.     while(p2 != NULL)  
148.     {  
149.         p3 = p2->next;  
150.         p2->next = p1;  
151.         p1 = p2;  
152.         p2 = p3;  
153.     }  
154.     head->next = NULL;  
155.     head = p1;  
156.     printf("\nAfter reversing ~\n");  
157.     return head;  
158. }  
159.   
160. int main()  
161. {  
162.     node *head;  
163.     //创建单链表  
164.     head = create();  
165.     print(head);  
166.     //排序  
167.     head = sort(head);  
168.     print(head);  
169.     //删除单链表  
170.     int numD;  
171.     printf("\nInput the value you want to delete : ");  
172.     scanf("%d", &numD);  
173.     head = del(head, numD);  
174.     print(head);  
175.     //插入单链表  
176.     int numS;  
177.     printf("\nInput the value you want to insert : ");  
178.     scanf("%d", &numS);  
179.     head = insert(head, numS);  
180.     print(head);  
181.     //逆置  
182.     head = reverse(head);  
183.     print(head);  
184.   
185.     return 0;  
186. }

运行示例：

本文由职坐标整理并发布，了解更多内容，请关注职坐标编程语言C/C+频道！