1 #include<iostream>
2 #include<iomanip>
3 using namespace std;
4
5 #define OK 1
6 #define ERROR 0
7 typedef int Status;
8
9 typedef struct LNode
10 {
11 int data; //结点的数据域
12 struct LNode *next; //结点的指针域
13 }LNode, *LinkList; //LinkList为指向结构体LNode的指针类型
14
15 void create_List(LinkList &L, int n){ //法1：递归初始化创建n个节点
16 if (n == 0)return;//创建n个节点
17 else{ //此时传进来的是第一个节点的指针
18 L = new LNode; //指针指向新生成的节点
19 cin >> L->data; //输入数据，将其压栈
20 L->next = NULL; //尾插法，先将下一个指针域赋为NULL
21 create_List(L->next, n - 1); //递归创建n个节点
22 }
23 }
24
25 Status Creat_LinkList(LinkList &L){ //法2：创建链表，当输入数字为-1时，令当前指针为空
26 int num;
27 cout << "请每行输入一个数据元素并按回车(直到-1退出)：";
28 cin >> num;//输入数据
29 if (num == -1){ L = NULL; return OK; } //结束
30 else{
31 L = new LNode; //申请新的节点，指针指向结构体
32 L->data = num; //先将数据放到数据域
33 return Creat_LinkList(L->next); //递归创建节点
34 }
35 }
36
37 int count_LNode(LinkList L){ //统计节点个数，传入链表首地址
38 if (L == NULL)return 0; //递归结束条件，递归到尾节点的下一个节点，直接返回
39 else return count_LNode(L->next) + 1; //否则继续指向下一个节点，表长加1
40 }
41
42 void lprint_LNode(LinkList L){ //正序打印链表
43 if (L == NULL)return; //递归的结束条件
44 else{
45 cout << L->data << ' '; //先打印当前节点的数据
46 lprint_LNode(L->next); //再递归循环链表
47 }
48 }
49
50 void bprint_LNode(LinkList L){ //反序打印链表
51 if (L == NULL)return; //递归的结束条件
52 else{
53 bprint_LNode(L->next); //先递归循环链表，将数据域压入栈中
54 cout << L->data << ' '; //讲数据出栈并打印
55 }
56 }
57
58 int maxVal_List(LinkList L) //求表中元素的最大值
59 {
60 int maxVal;
61 if (L->next == NULL) //如果到尾节点，就把当前节点的值赋值为maxVal
62 return L->data; //递归结束条件，出栈比较
63 else{
64 maxVal = maxVal_List(L->next);//先把一个个数据压栈
65 if (L->data > maxVal)
66 maxVal = L->data;
67 return maxVal;
68 }
69
70 }
71
72 int minVal_List(LinkList L) //求表中元素的最小值
73 {
74 int minVal;
75 if (L->next == NULL) //如果到尾节点，就把当前节点的值赋值为minVal
76 return L->data; //返回末尾的值赋给尾节点
77 else{
78 minVal = minVal_List(L->next);//先把一个个数据压栈
79 if (L->data < minVal)
80 minVal = L->data;
81 return minVal; //返回上一层
82 }
83 }
84
85 int getSum_List(LinkList L){ //递归求该表中所有元素的和
86 if (L == NULL)return 0; //递归结束条件：当p指向空时，返回0
87 else //否则将当前指针指向的数据域压入栈中，递归到链表尾
88 return getSum_List(L->next) + L->data;
89 }
90
91 bool found = false;
92 void Print_List(LinkList L, int val){ //12.打印单链表中从某节点元素开始后的所有节点
93 if (!L)return; //递归结束条件
94 else{
95 if (L->data == val)found = true;
96 if (found)cout << L->data << ' '; //只要从满足那一节点之后，打印该点之后的所有节点
97 Print_List(L->next, val); //递归
98 }
99 }
100
101 bool flag = false;//用来标记是否查找成功
102 void PriorElem_List(LinkList L, int val, int &preVal){ //9.求某元素的前驱元素，引用前驱元素
103 if (!L || L->data == val){ //当输入val刚好是第一个节点的时候，直接返回
104 preVal = val;
105 return;
106 }
107 else {
108 if (L->next && L->next->data == val){//找到值为val的前驱节点
109 preVal = L->data;
110 flag = true;
111 }
112 else
113 PriorElem_List(L->next, val, preVal);//递归查找
114 }
115 }
116
117 LinkList pre = NULL;
118 Status IsOrder_List(LinkList L){ //10.判断单链表是否递增有序
119 if (!L)return OK; //当遍历到尾节点的下一个位置，返回正确，表示递增有序
120 if (pre && (pre->data > L->data))return ERROR;
121 pre = L; //将当前节点作为前驱pre节点
122 return IsOrder_List(L->next); //递归遍历每个节点
123 }
124
125 int j = 1; //记录节点的序号
126 bool flag_insert = false;//标记是否插入成功
127 void insert_List(LinkList &L, int i, int e){ //11.在单链表的第i个位置插入元素e
128 LinkList q;
129 if (i == 1){
130 q = new LNode;
131 q->data = e;//赋值
132 q->next = L;
133 L = q;//L时刻指向尾节点
134 flag_insert = true;
135 }
136 if (!L || flag_insert)return; //递归终止条件
137 else {
138 if (j == i - 1){
139 q = new LNode; //申请一个新的节点
140 q->data = e; //接下来的操作按常规来
141 q->next = L->next;
142 L->next = q;
143 flag_insert = true;//表示插入成功
144 }
145 else{
146 j++; //表长先加1，再递归循环链表
147 insert_List(L->next, i, e);
148 }
149 }
150 }
151
152 bool findVal_list = false;
153 void check_List(LinkList L, int val){ //检查val元素是否在表中
154 if (L == NULL || findVal_list)return; //递归出口，若找到的话就不用递归了
155 else{
156 if (L->data == val)findVal_list = true; //此时已经找到
157 else check_List(L->next, val); //继续递归查找
158 }
159 }
160
161 int k = 1;
162 bool delNodeflag = false;
163 void delNode_List(LinkList &L, int i, int &e){ //13.删除单链表的第i个元素
164 if (!L || delNodeflag)return;
165 else{
166 LinkList q;
167 if (i == 1){
168 q = L;
169 e = q->data;
170 L = L->next;
171 delete q;
172 delNodeflag = true;
173 }
174 else if (k == i - 1){ //找到要删除节点的前驱
175 q = L->next; //基本操作
176 e = q->data;
177 L->next = q->next;
178 delete q;
179 delNodeflag = true; //标记删除成功
180 }
181 else {
182 k++; //循环链表
183 delNode_List(L->next, i, e); //递归链表
184 }
185 }
186 }
187
188
189 int i = 0; double sum = 0.0; //尾递归计算平均值
190 //double getAverage_List(LinkList L){
191 // if (L == NULL)return sum / i;
192 // else{
193 // sum += L->data;
194 // i++;
195 // return getAverage_List(L->next);
196 // }
197 //}
198 double getAverage_List(LinkList L,int n){//递归计算平均值
199 if (!L->next)return L->data;
200 else{
201 double ave = getAverage_List(L->next, n - 1);
202 return (ave*(n - 1) + L->data) / n;
203 }
204 }
205 int main()
206 {
207 int e;
208 int choose;
209
210 LinkList L;
211 choose = -1;
212 while (choose != 0)
213 {
214 cout << "******************************************************************************
";
215 cout << " 1. 建立空链表(不带头节点); 2. 输入指定个数的数据元素创建链表
";
216 cout << " 3. 正序打印表中元素 ; 4. 逆序打印表中元素
";
217 cout << " 5. 求表中元素的最大值; 6. 求表中元素的最小值
";
218 cout << " 7. 返回单链表的长度; 8. 递归求该表中所有节点元素的和
";
219 cout << " 9. 查找某元素的前驱元素; 10.判断单链表是否递增有序
";
220 cout << " 11.在单链表的第i个位置插入元素e 12.打印单链表中从某节点元素开始后的所有节点
";
221 cout << " 13.删除单链表的第i个元素 14.求表所有元素的平均值
";
222 cout << " 0. 退出
";
223 cout << "*******************************************************************************
";
224
225 cout << "请选择:";
226 cin >> choose;
227 switch (choose)
228 {
229 case 1: //建立空链表
230 L = NULL;//这里不带头结点，建立空链表
231 cout << "成功建立空链表" << endl << endl;
232 break;
233 case 2: //输入指定个数的数据元素创建链表 ,这里也可以调用当输入不为-1的函数
234 /*cout << "请输入一个数，代表元素的个数：";
235 cin >> i;
236 if (i == 0)
237 cout << "此时创建的是空链表" << endl<<endl;
238 else{
239 cout << "请输入" << i << "个数据元素，之间用空格隔开：";
240 create_List(L, i);
241 cout << "成功建立单链表" << endl << endl;
242 } */
243 if (Creat_LinkList(L)) //也可以用第2中创建节点的方法创建单链表，此时实参传入第一个节点的指针
244 cout << "成功创建单链表" << endl;
245 else
246 cout << "创建单链表失败" << endl;
247 break;
248 case 3: //正序打印表中元素
249 if (count_LNode(L)){
250 cout << "当前表中一共有" << count_LNode(L) << "个元素，正序输出依次为";
251 lprint_LNode(L);
252 cout << endl << endl;
253 }
254 else
255 cout << "当前为空链表" << endl << endl;
256 break;
257 case 4: //逆序打印表中元素
258 if (count_LNode(L)){
259 cout << "当前表中一共有" << count_LNode(L) << "个元素，逆序输出依次为";
260 bprint_LNode(L);
261 cout << endl << endl;
262 }
263 else
264 cout << "当前为空链表" << endl << endl;
265 break;
266 case 5: //求表中元素的最大值
267 if (count_LNode(L)){
268 cout << "表中最大的元素为：" << maxVal_List(L) << "。
" << endl;
269 }
270 else
271 cout << "当前为空链表" << endl << endl;
272 break;
273 case 6: //求表中元素的最小值
274 if (count_LNode(L)){
275 cout << "表中最小的元素为：" << minVal_List(L) << "。
" << endl;
276 }
277 else
278 cout << "当前为空链表" << endl << endl;
279 break;
280 case 7: //返回单链表的长度
281 if (count_LNode(L))
282 cout << "当前单链表表长为" << count_LNode(L) << "。
" << endl;
283 else
284 cout << "当前为空表" << endl << endl;
285 break;
286 case 8: //递归求该表中所有元素的和
287 if (count_LNode(L))
288 cout << "当前表中所有元素的和为" << getSum_List(L) << "。
" << endl;
289 else
290 cout << "当前为空表" << endl << endl;
291 break;
292 case 9: //查找某元素的前驱元素
293 if (!L)
294 cout << "当前为空表" << endl << endl;
295 else {
296 int val, preVal;
297 cout << "请输入一个待查找前驱元素的元素：";
298 cin >> val;
299 flag = false;
300 PriorElem_List(L, val, preVal);
301 if (flag)
302 cout << "待查找元素" << val << "的前驱元素为" << preVal << "。
" << endl;
303 else
304 cout << "找不到" << val << "的前驱元素" << endl << endl;
305 }
306 break;
307 case 10: //判断单链表是否递增有序
308 if (IsOrder_List(L))
309 cout << "该链表递增有序" << endl << endl;
310 else
311 cout << "该链表非递增" << endl << endl;
312 break;
313 case 11: //在单链表的第i个位置后面插入元素e，在这里链表长度至少为1，否则插入失败
314 cout << "请输入要插入元素的位置及插入的元素分别为(用空格隔开):";
315 cin >> i >> e;
316 if (i<1 || (i>count_LNode(L) + 1))
317 cout << "输入" << i << "不在节点位置范围内。" << endl << endl;
318 else{
319 flag_insert = false, j = 1;
320 insert_List(L, i, e);
321 if (flag_insert)
322 cout << "成功在第" << i << "个位置插入元素" << e << "。
" << endl;
323 else
324 cout << "插入失败" << endl << endl;
325 }
326 break;
327 case 12: //打印单链表中从某节点元素开始后的所有节点
328 if (!L)
329 cout << "当前为空表" << endl << endl;
330 else{
331 int val;
332 findVal_list = found = false;
333 cout << "请输入打印的起始元素:";
334 cin >> val;
335 check_List(L, val);
336 if (findVal_list){
337 cout << "链表元素依次为：";
338 Print_List(L, val);
339 cout << endl << endl;
340 }
341 else
342 cout << "该表中没有" << val << "这个元素。" << endl << endl;
343 }
344 break;
345 case 13: //删除单链表的第i个元素
346 if (!L)
347 cout << "当前链表为空。" << endl << endl;
348 else{
349 cout << "请输入要删除节点的位置：";
350 cin >> i;
351 if (i<1 || i>count_LNode(L))
352 cout << "输入" << i << "不在节点位置范围内。" << endl << endl;
353 else{
354 delNodeflag = false, k = 1;
355 delNode_List(L, i, e);
356 if (delNodeflag)
357 cout << "成功删除第" << i << "个位置的元素" << e << "。
" << endl;
358 else
359 cout << "删除失败。" << endl << endl;
360 }
361 }
362 break;
363 case 14:
364 if (L->next == NULL)
365 cout << "当前链表为空" << endl << endl;
366 else{
367 //sum = 0.0, i = 0; //尾递归初始化条件
368 int n = count_LNode(L);
369 cout << "此时表中元素总和的平均值是";
370 cout << setiosflags(ios::fixed) << setprecision(2) << getAverage_List(L,n) << endl << endl;
371 }
372 break;
373 }
374 }
375 return 0;
376 }
