c++已知f为单链表的表头指针,链表中存储的都是整型数据,试写出实现下列运算的递归算法和非递归算法:(1)求链表中的最大整数。(2)求所有整数的平均值。
时间: 2024-10-13 15:07:29 浏览: 8
在C++中,我们可以使用递归和迭代的方式分别实现链表的最大整数和平均值计算。
**递归算法**:
1. **求最大整数(递归)**:
- 如果链表为空,返回INT_MIN作为初始情况;
- 否则,比较当前节点的值和下一个节点的最大值,取较大者为结果,并继续递归到链表尾部。
```cpp
int maxRecursive(Node* f, int maxSoFar = INT_MIN) {
if (f == nullptr)
return maxSoFar;
else
return max(maxSoFar, f->val > maxSoFar ? f->val : maxRecursive(f->next));
}
```
2. **求平均值(递归)**:
- 首先需要计算链表的总和,然后除以节点总数(包括头节点)。可以辅助一个变量记录总和和节点计数;
- 初始情况,如果链表为空,总和为0,节点数为0;
- 否则,累加当前节点值并增加计数,然后递归处理下一个节点。
```cpp
double averageRecursive(Node* f, int sum = 0, int count = 1) {
if (f == nullptr)
return 0.0;
else {
sum += f->val;
count++;
return averageRecursive(f->next, sum, count);
}
}
double getAverageRecursive(Node* f) {
int totalSum = sumRecursive(f);
int totalNodes = countRecursive(f);
return static_cast<double>(totalSum) / totalNodes;
}
```
**非递归算法**:
1. **求最大整数(非递归)**:
- 使用栈保存遍历过程中的最大值,从头节点开始,逐个比较更新最大值。
```cpp
Node* findMaxIterative(Node* f) {
if (f == nullptr)
return nullptr;
Node* maxNode = f;
while (f->next != nullptr) {
if (f->val > maxNode->val)
maxNode = f;
f = f->next;
}
return maxNode;
}
```
2. **求平均值(非递归)**:
- 初始化总和、计数,遍历整个链表。
```cpp
double averageNonRecursive(Node* f) {
int sum = 0;
int count = 0;
for (; f != nullptr; f = f->next) {
sum += f->val;
count++;
}
return static_cast<double>(sum) / count;
}
```