数据结构单链表

一、总体要求

1.利用单向链表数据结构完成对链表的如下操作
2.创建一条含整数结点的无序链表
3.链表结点的输出
4.链表结点的升序排序
5.分别计算链表中奇数和偶数结点之和并输出
6.释放链表
7.退出

二、开发环境

1.操作系统：Windows 10
2.运行环境：mingw64
3.开发工具：CLion 2020.1 x64

三、系统运行效果截图

1.创建一条含整数结点的无序链表

2.链表结点的输出

3.链表结点的升序排序

4.分别计算链表中奇数和偶数结点之和并输出

5.释放链表

6.退出

四、源程序

1.#include <stdio.h>  
2.#include <stdlib.h>  
3.#include <iostream>  
4.  
5.using namespace std;  
6./** 
7. * 定义单链表结构体 
8. */  
9.typedef struct node {  
10.    int data;//代表数据域  
11.    struct node *next;//代表指针域，指向直接后记元素  
12.} link;  
13.  
14./** 
15. * 展示链表数据 
16. * @param p 
17. */  
18.void display(link *p) {  
19.  
20.    if (p->next == NULL) {  
21.        printf("请先初始化链表");  
22.        return;  
23.    }  
24.    printf("链表的数据为:");  
25.    link *temp = p;//将temp指针重新指向头结点  
26.    //只要temp指针指向的结点的next不是Null，就执行输出语句。  
27.    while (temp->next) {  
28.        temp = temp->next;  
29.        printf("%d\t", temp->data);  
30.    }  
31.    printf("\n");  
32.}  
33.  
34./** 
35. * 链表中奇数偶数分别求和 
36. * @param p 
37. */  
38.void sumOddEven(link *p) {  
39.    if (p->next == NULL) {  
40.        printf("请先初始化链表");  
41.        return;  
42.    }  
43.    int odd = 0;//奇数  
44.    int even = 0;//偶数  
45.    link *temp = p;//将temp指针重新指向头结点  
46.    //只要temp指针指向的结点的next不是Null，就执行输出语句。  
47.    while (temp->next) {  
48.        temp = temp->next;  
49.        if (temp->data % 2 == 0) {  
50.            even += temp->data;  
51.        } else {  
52.            odd = odd + temp->data;  
53.        }  
54.    }  
55.  
56.    display(p);//现将链表数据展示出来  
57.    printf("链表中奇数之和:%d", odd);  
58.    printf("\n");  
59.    printf("链表中偶数之和:%d", even);  
60.    printf("\n");  
61.}  
62.  
63.  
64./** 
65. * 每个节点删除并释放链表 
66. * @param p 
67. */  
68.void freeList(link *p) {  
69.  
70.    if (p->next == NULL) {  
71.        printf("链表数据已为空");  
72.        return;  
73.    }  
74.    node *curNode = p->next;  
75.    while (curNode != NULL) {  
76.        node *delNode = curNode;  
77.        curNode = curNode->next;  
78.        free(delNode);  
79.    }  
80.    p->next = NULL;//头结点指向NULL  
81.    printf("释放链表已成功,链表数据已为空");  
82.    return;  
83.  
84.}  
85.  
86.  
87./** 
88. * 使用冒泡排序 升序 
89. * @param head 
90. * @return 
91. */  
92.node *sorted(node *head) {  
93.    node *p, *q;  
94.    int num = 0, j = 0;  
95.    q = head;  
96.    //获取链表的长度  
97.    while (q != NULL) {  
98.        q = q->next;  
99.        num++;  
100.    }  
101.    //使用冒泡排序，两两比较交换  
102.    for (int i = 0; i < num - 1; i++) {  
103.        p = q = head;  
104.        j = num - i - 1; //减少每一趟循环中两两比较的次数  
105.        while (p->next != NULL && j != 0) {  
106.            j--;  
107.            if (p->data > p->next->data) {  
108.                //节点的交换  
109.                if (p == head) head = p->next;  
110.                else q->next = p->next;  
111.                q->next = p->next;  
112.                q = q->next;  
113.                p->next = q->next;  
114.                q->next = p;  
115.                //执行完上面的过程后，为了能够让p顺利地执行移动到交换后的下一位 .  
116.                p = q;  
117.            }  
118.            q = p; //为了能让q保持在p的前面  
119.            p = p->next; //p指针后移，即p变成了在q的前面  
120.        }  
121.    }  
122.  
123.    printf("排序后的链表数据为:");  
124.    display(head);//展示数据  
125.    return head;  
126.}  
127.  
128./** 
129. * 操作菜单 
130. */  
131.void showMenu() {  
132.    cout << "\n*********单链表数据操作菜单**********" << endl;  
133.    cout << "********* 1.创建一条含整数结点的无序链表  **********" << endl;  
134.    cout << "********* 2.链表结点的输出 **********" << endl;  
135.    cout << "********* 3.链表结点的升序排序 **********" << endl;  
136.    cout << "********* 4.分别计算链表中奇数和偶数结点之和并输出 **********" << endl;  
137.    cout << "********* 5.释放链表 **********" << endl;  
138.    cout << "********* 0.退出 **********" << endl;  
139.    cout << "请输入你的选择:" << endl;  
140.}  
141.  
142./** 
143. * 退出系统函数 
144. * @return 
145. */  
146.int exit() {  
147.    exit(0);  
148.}  
149.  
150./** 
151. * 初始化链表 
152. * @param con 
153. * @return 
154. */  
155.link *initLink(link *con) {  
156.    cout << "请输入整数添加到链表【-1即退出添加】\n";  
157.    int tem;  
158.    int arr[100]; // n 是一个包含 10 个整数的数组  
159.    int index = 0;  
160.    while (tem != -1) {  
161.        cout << "正在插入链表第" << index + 1 << "个元素:";  
162.        cin >> tem;  
163.        if (tem != -1) {  
164.            arr[index] = tem;  
165.            index++;  
166.        }  
167.  
168.    }  
169.  
170.    link *temp = con;//声明一个指针指向头节点  
171.  
172.    //链表中插入数据  
173.    for (int i = 0; i < index; i++) {  
174.        link *a = (link *) malloc(sizeof(link));  
175.        a->data = arr[i];  
176.        a->next = NULL;  
177.        temp->next = a;  
178.        temp = temp->next;  
179.    }  
180.    cout << "链表初始化完成";  
181.    temp->next = NULL;//尾指针指向NULL  
182.    return con;  
183.}  
184.  
185./** 
186. * 主函数运行单链表操作 
187. * @return 
188. */  
189.int main() {  
190.    setbuf(stdout, NULL); //强制不缓存  
191.  
192.    link *p;  
193.    //声明头结点  
194.    p = (link *) malloc(sizeof(link));  
195.    p->next = NULL;  
196.    p->data = NULL;  
197.  
198.  
199.    while (true) {  
200.        showMenu();  
201.        int i;  
202.        cin >> i;  
203.        switch (i) {  
204.            case 1:  
205.                initLink(p); //初始化单链表  
206.                break;  
207.            case 2:  
208.                display(p);//显示链表数据  
209.                break;  
210.            case 3:  
211.                sorted(p);//自然排序链表  
212.                break;  
213.            case 4:  
214.                sumOddEven(p);//分别计算链表奇数和与偶数和  
215.                break;  
216.            case 5:  
217.                freeList(p);//释放链表  
218.                break;  
219.            case 0:  
220.                exit(); //退出  
221.                break;  
222.        }  
223.    }  
224.}  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224

有啥不懂得小伙伴们加群交流啦：852665736
无偿免费分享源码以及技术和面试文档，更多优秀精致的源码技术栈分享请关注微信公众号：gh_817962068649