[C语言、C++]数据结构作业：无头单链表—递归创建+递归求最大值_假设一个不带头结点的单链表h,设计递归算法求最大值

递归创建+递归求最大值

递归建立一个具有n个结点的无头单链表，并递归求这个单链表中数据的最大值

样例：n=6，结点数据分别为：20  100   5  214  88 99

main中：

1、递归创建。

2、遍历输出。

3、递归求最大值并打印

4、destory。

#include <iostream>
using namespace std;
typedef int ElemType;
typedef struct LinkNode {
	ElemType data;
	LinkNode* next;
}*LinkList;
void InitLinkList(LinkList& L) {
	L = NULL;
}
void Traverse(const LinkList& L) {
	LinkNode* p = L; //设p指向首元结点
	while (p) { //有结点则进行
		cout << p->data << endl;
		p = p->next; //结点指针后移
	}
}
 
void DestroyList(LinkList& L) {
	LinkNode* p = L;
	while (p)
	{
		L = L->next;
		delete(p);
		p = L;
	}
}
void RecCreatHead(LinkList& L, int n) {//递归法头插创建无头链表
	if (n != 0) {
		LinkNode* s = new LinkNode;
		cin >> s->data;
		s->next = L;
		L = s;
		RecCreatHead(L, n - 1);
	}
}
int RecMax(LinkList& L) {
	if (L->next) {
		return(L->data >= RecMax(L->next)) ? L->data : RecMax(L->next);
	}
	else {
		return L->data;
	}
}
int main() {//样例：n=6，结点数据分别为：20 100 5 214 88 99
	LinkList L; 
	InitLinkList(L); 
	RecCreatHead(L, 6);//1、递归创建。
	cout << "==========遍历==========="<<endl;
	Traverse(L);//2、遍历输出
	cout << "========================="<<endl;
	cout<<"经过递归求解，最大值为：" << RecMax(L);//3、递归求最大值并打印
	DestroyList(L);//4、destory
}

思路:

分问题：

若该节点指针指向的下一个节点存在，则比较该节点与下一个节点的大小，返回较大值

总问题：回退到整体

即比较 第一个节点的元素 和 后面所有元素中的最大值 的大小