第三章算法设计题10

#pragma once
#include 

using namespace std;


//单链表的存储结构
typedef struct Lnode
{
	int data;
	struct Lnode* next;
}Lnode,*linkList;


//单链表的初始化
void InitList(linkList& L)
{
	L = new Lnode;
	L->next = NULL;
}
//创建单链表
void createList(linkList& L, int a[],int n)
{

	//生成新节点
	Lnode* s;
	Lnode* pre;
	//pre指向头结点
	pre = L;



	for (int i = 0; i < n; i++)
	{
		s = new Lnode;
		s->data = a[i];
		pre->next = s;
		pre = s;
	}
	pre->next = NULL;
}


//打印
void show(linkList L)
{
	while (L->next)
	{
		cout << L->next->data << " ";
		L = L->next;
	}
	cout << endl;

}



//递归获取最大值
int getMaxL(linkList L)
{
	int ans = 0;
	//指向首元结点
	Lnode* p = L->next;
	if (p->next == NULL)
	{
		return p->data;
	}

	else
	{
		ans = getMaxL(p->next);
		return p->data > ans ? p->data : ans;

	}

}

//求结点个数（求长度）
int getLength(linkList L)
{
	
	if (L->next==NULL)
	{
		return 0;
	}
	else
	{
		return getLength(L->next) + 1;
	}


}


//求平均值
float getAverage(Lnode *p, int n)
{
	
	if (p->next == NULL) 
	{ // 链表仅有一个结点
		return p->data;
	}
	else 
	{
		// 求后面n-1各结点值的和
		float sum = getAverage(p->next, n - 1) * (n - 1);
		// 然后加上首结点的值求平均值
		return (p->data + sum) / n;
	}
}




int main()
{

	//创建并初始化链表
	linkList L;
	InitList(L);

	int nums[] = {2,3,5,4,6};
	int len = sizeof(nums) / sizeof(int);

	createList(L, nums,len);
	show(L);


	//获取最大值
	int res = getMaxL(L);
	cout << "最大值为：" << res << endl;

	int length = getLength(L);
	cout << "元素个数为：" << length << endl;


	//创建新结点指向首元结点
	Lnode* p = L->next;
	float avg = getAverage(p, length);
	cout << "平均值为：" << avg << endl;

	system("pause");
	return 0;
}