单链表的系列递归算法_递归建立单链表

分为递归创建单链表、递归从前向后输出单链表、递归求解单链表最大值、递归求解链表中所有整数的和 、递归求解链表结点个数、递归逆转链表几个部分

using namespace std;
#include<iostream>

typedef struct LNode{
		 int data;
 struct LNode *next;}LNode,*LinkList;


void CreatList(LinkList &p){
//递归创建链表	
	int n;
	cin>>n; //输入结点数值，输入0则退出
	if (n==0)  p=NULL;
    else{
		p=new LNode;
		p->data=n;
		CreatList(p->next);
	}
}

void Output(LinkList p){
//递归从前向后输出链表
	if (p==NULL) return;
    else{
		cout<<p->data<<' ';
		Output(p->next);
	}
}


int GetMax(LinkList p ){
//递归求解最大值	
    if(!p->next)	return p->data;
	else
	{
		int max=GetMax(p->next);
		return  p->data>=max ? p->data:max;
	}

}

int GetLength(LinkList p){
//递归求解链表的结点个数
  if(!p->next)                                	//p指向表尾，返回1
      return 1;
    else                                        //每递归一次，结点个数加1
    {
      return GetLength(p->next)+1;
    }
}

int GetSum(LinkList p )
{//递归求解链表中所有整数的和 
  if(!p->next)                                  	//p指向表尾，返回其数值
      return p->data;
    else
        return p->data+GetSum (p->next);         	
}

double GetAverage(LinkList p,int n)
{//递归求解链表中所有整数的平均值
  if(!p->next)                                  	//p指向表尾，返回其数值
      return p->data;
    else
    {
      double ave=GetAverage(p->next,n-1);
      // 递归求解除尾结点之外的其余n-1个结点的平均值
      return (ave*(n-1)+p->data)/n;         	//返回平均值
    }
}

LinkList Reverse(LinkList p){
//递归逆转链表 
//https://www.cnblogs.com/mld-code-life/p/12705213.html
    if(p->next == NULL)    return p; 
    LinkList q = p->next;
    LinkList head = Reverse(q);
    p->next = NULL;
    q->next = p;
    return head;
}


int main( ){	  
	  LinkList  L,H;
	  L=new LNode;
	  L->next=NULL;
	  CreatList(L->next);//递归创建链表	  
	  Output(L->next);//递归从前向后输出链表	  
	  int num=GetLength(L->next);//递归求解链表的结点个数
	  cout<<num;
	  cout<<GetMax(L->next);//递归求解最大值	
	  cout<<GetSum(L->next);//递归求解链表中所有整数的和
	  cout<<GetAverage(L->next,num);//递归求解链表中所有整数的平均值 
	  H=Reverse(L->next);//递归逆转链表 
	  Output(L->next);//递归从前向后输出链表
	  return 1;
	  
 }
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