C语言递归求解链表元素的最大值、最小值、平均值等

题目

解答

	#include<stdio.h>
	#include<stdlib.h>
	
	typedef struct LNode{
		int data;
		struct LNode *next;
	}LNode,*LinkList; //指向单链表结点的指针 
	
	/*头插法建立带头结点的单链表*/
	int CreateList(LinkList *L, int n){
		int i;
		LinkList p;
		int tmp;
			
		*L = (LinkList)malloc(sizeof(LNode));
		if(!(*L))
			exit(0);
		(*L)->next = NULL;	 //建立头结点 
		
		printf("请为链表输入%d个整形数据【以空格分割】\n",n);
		for(i=1; i<=n; ++i){
			if(scanf("%d", &tmp)){
				p = (LinkList)malloc(sizeof(LNode));
				if(!p)
					exit(0);
				p->data = tmp;		   //给新结点录入数据 
				p->next = (*L)->next;  //将新结点的next指向头结点后面的那一堆
				(*L)->next = p;		   //将新结点接在头结点后面
			}
			else
				return 0;
		}
		
		return 1;
	}  
	
	/*（1）递归法正序打印单链表【初始传入的L为首元结点】*/
	void ListTraverse1(LinkList L){
		if(L==NULL)  //递归的结束条件
			return;
		else{
			printf("%d ",L->data);  //先打印当前节点的数据
			ListTraverse1(L->next); //递归单链表
		}
	}
	
	/*（2）递归法逆序打印单链表【初始传入的L为首元结点】*/
	void ListTraverse2(LinkList L){
		if(L==NULL)  //递归的结束条件
			return;
		else{
			ListTraverse2(L->next); //先递归单链表，将数据域压入栈中
			printf("%d ",L->data);  //再将数据出栈并打印
		}
	}
	
	/*（3）递归法判断单链表是否递增有序【初始传入的L为首元结点】*/
	LinkList pre = NULL; //设置一个前驱结点，初始为空
	int isOrder(LinkList L){
		if(!L) //当遍历到尾节点的下一个位置，返回正确【说明最后一个结点也判断完了，表明递增有序】
			return 1;  
		if(pre && (pre->data > L->data)) //如果有前驱结点并且比当前结点大，返回错误
			return 0;
		pre = L;  //将当前节点作为前驱pre节点
		return isOrder(L->next);  //递归遍历每个节点
	}
	
	/*（4）递归法求单链表存储元素个数【初始传入的L为首元结点】*/
	int elemCount(LinkList L){
		if(L==NULL)
			return 0;  //递归结束条件，递归到尾节点的下一个节点，直接返回
		else 
			return elemCount(L->next) + 1;   //否则继续指向下一个节点，表长加1
	}
	
	/*（5）递归法求单链表最大值【初始传入的L为首元结点】*/
	int getMax(LinkList L){
		int maxVal;
	
		if(L->next==NULL) //如果到尾节点
			return L->data;  //递归结束条件，出栈比较
		else{
			maxVal = getMax(L->next); //先把一个个数据压栈
			if(L->data>maxVal)  //若该结点的值比maxVal大
				maxVal=L->data; //更新maxVal
		}
		return maxVal;
	}
	
	/*（6）递归法求单链表最小值【初始传入的L为首元结点】*/
	int getMin(LinkList L){
		int minVal;
	
		if(L->next==NULL) //如果到尾节点
			return L->data;  //递归结束条件，出栈比较
		else{
			minVal = getMin(L->next); //先把一个个数据压栈
			if(L->data<minVal)  //若该结点的值比minVal小
				minVal=L->data; //更新minVal
		}
		return minVal;
	}
	
	/*（7）递归法求单链表所有元素的和【初始传入的L为首元结点】*/
	int getSum(LinkList L){
		if(L==NULL) //递归结束条件
			return 0;  
		else
		    return getSum(L->next) + L->data;
	}
	
	/*（8）递归法求单链表所有元素的平均值【初始传入的L为首元结点】*/
	/*
	s[5]={2,3,1,5,4}
	第n-1步的平均值：
	getAve(s,n-1)=(2+3+1+5)/(n-1)
	第n步的平均值：  
	getAve(s,n) =[4+(2+3+1+5)]/n
	            ={4+(n-1)*[(2+3+1+5)/(n-1)]}/n
				=[4+(n-1)*getAve(s,n-1)]/n
	*/
	double getAve(LinkList L,int n){
		double ave; //注意平均值用double型
		if(!L->next)
			return L->data;
		else{
			ave=getAve(L->next, n-1);
			return (L->data + (n-1)*ave) / n ;
		}
	}
	
	int main(){
		int n=10;
		LinkList L;
		CreateList(&L, n); //参数为二级指针
		printf("正序打印单链表【注意：头插法输入的数据在单链表中是逆序存放的】\n");
		ListTraverse1(L->next);
		printf("\n");
		printf("逆序打印单链表【注意：头插法输入的数据在单链表中是逆序存放的】\n");
		ListTraverse2(L->next);
		printf("\n");
		if(isOrder(L->next))
			printf("你输入的单链表递增有序\n");
		else
			printf("你输入的单链表非递增有序\n");
		printf("单链表元素个数为：%d\n",elemCount(L->next));
		printf("单链表元素的最大值为：%d\n",getMax(L->next));
		printf("单链表元素的最小值为：%d\n",getMin(L->next));
		printf("单链表所有元素之和为：%d\n",getSum(L->next));
		printf("单链表所有元素的平均值为：%.2f\n",getAve(L->next,n));
		return 0;
	}
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