已知head为单链表的表头指针,链表中存储的都是整型数据,实现下列运算的递归算法,给出完整能运行的c++代码:(1)求链表中的最大值。(2)求链表中的结点个数。(3)求所有整数的平均值。
时间: 2024-10-08 12:19:23 浏览: 28
已知head为单链表的表头指针,链表中存储的都是整形数据,实现下列运算的递归算法
4星 · 用户满意度95%
在C++中,我们可以使用递归的方式来处理链表操作。首先,我们需要一个Node类来表示链表节点,包含一个整数值和指向下一个节点的指针。以下是完整的代码实现:
```cpp
#include <iostream>
// 链表节点类
class ListNode {
public:
int val;
ListNode* next;
ListNode(int x) : val(x), next(nullptr) {}
};
// 辅助函数,用于递归遍历链表并返回累计值、节点数量
int sumAndCount(ListNode* head, int& count) {
if (head == nullptr) {
return 0; // 如果链表为空,结束递归
}
int currentSum = head->val + sumAndCount(head->next, count); // 递归获取前一个节点的和
count++; // 记录当前节点的数量
return currentSum;
}
// 主函数实现
void computeMaxAverage(ListNode* head) {
int maxVal = INT_MIN, count = 0;
maxVal = sumAndCount(head, count); // 求最大值同时计算节点数量
if (count > 0) {
double average = static_cast<double>(maxVal) / count; // 计算平均值
std::cout << "最大值: " << maxVal << ", 节数量: " << count << ", 平均值: " << average << std::endl;
} else {
std::cout << "链表为空" << std::endl;
}
}
// 测试代码
int main() {
// 创建一个示例链表
ListNode* list = new ListNode(5);
list->next = new ListNode(10);
list->next->next = new ListNode(15);
list->next->next->next = new ListNode(3);
computeMaxAverage(list);
delete list; // 别忘了释放内存
return 0;
}
```
这个程序中,`computeMaxAverage`函数包含了三个递归操作:求最大值、计数以及计算平均值。注意在主函数`main`中创建了一个简单的链表进行测试。
阅读全文