利用c++实现,并在主函数测试实现1、已知head为单链表的表头指针,链表中存储的都是整型数据,实现下列运算的递归算法: (1)求链表中的最大值。 (2)求链表中的结点个数。 (3)求所有整数的平均值。
时间: 2024-10-06 13:04:10 浏览: 13
在C++中,你可以通过递归的方式来处理单链表的问题。下面是一个简单的例子,展示了如何分别实现这三个功能:
1. **求链表中的最大值**:
```cpp
#include <iostream>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
int findMax(ListNode* head) {
// 基本情况:如果链表为空,返回最小整数
if (head == nullptr) return INT_MIN;
// 如果只有一个节点,直接返回该节点的值
if (head->next == nullptr) return head->val;
// 递归情况:比较当前节点和下一个节点的最大值
return max(head->val, findMax(head->next));
}
```
2. **求链表中的结点个数**:
```cpp
int countNodes(ListNode* head) {
// 基本情况:如果链表为空,返回0
if (head == nullptr) return 0;
// 递归情况:当前节点加上下一个节点的数量
return 1 + countNodes(head->next);
}
```
3. **求所有整数的平均值**:
```cpp
double averageOfList(ListNode* head) {
if (head == nullptr) return 0.0; // 空链表平均值为0
double sum = findSum(head);
return sum / countNodes(head);
}
// 用于辅助计算总和
double findSum(ListNode* head) {
if (head == nullptr) return 0.0;
return head->val + findSum(head->next);
}
```
然后,在`main`函数中可以这样测试这些函数:
```cpp
int main() {
// 创建并初始化一个链表...
ListNode* head = ...;
cout << "Max value: " << findMax(head) << endl;
cout << "Node count: " << countNodes(head) << endl;
cout << "Average value: " << averageOfList(head) << endl;
return 0;
}
```