已知head为单链表的表头指针,使用递归求平均值算法fun2
时间: 2023-08-09 18:01:34 浏览: 127
已知head为单链表的表头指针,链表中存储的都是整形数据,实现下列运算的递归算法
4星 · 用户满意度95%
递归求平均值的算法fun2的实现如下:
首先计算单链表中所有节点的数值和和节点数量。
定义递归函数,传入一个节点指针和当前的节点数量。
在递归函数中,逐个遍历链表的节点,将节点的数值累加到一个总和变量中,并且每次递归调用时将节点数量加1。
当遍历到最后一个节点时,返回累加和除以节点数量的结果。
最后,调用递归函数,将单链表的表头指针和初始节点数量传入。
具体实现代码如下:
```python
class Node:
def __init__(self, value=None):
self.value = value
self.next = None
def fun2(head):
def recursive_func(node, count):
if node.next is None:
return node.value / count
return (node.value + recursive_func(node.next, count+1)) / count
if head is None:
return 0
return recursive_func(head, 1)
```
这样,通过递归实现的fun2算法可以求解出单链表中节点数值的平均值。
阅读全文