(10)已知f为单链表的表头指针，链表中存储的都是整型数据，试写出实现下列运算的递归算法 ①求链表中的最大整数;②求链表的结点个数;③求所有整数的平均值。

①递归求链表中的最大整数:

int getMax(Node* head){
if(head == NULL){
return INT_MIN;
}
int max_num = head->data;
int next_max = getMax(head->next);
return max(max_num, next_max);
}

调用方法: getMax(f)

②递归求链表的结点个数:

int getCount(Node* head){
if(head == NULL){
return 0;
}
return 1 + getCount(head->next);
}

调用方法: getCount(f)

③递归求所有整数的平均值:

double getAverage(Node* head){
if(head == NULL){
return 0.0;
}
int sum = head->data;
int count = 1;
double next_average = getAverage(head->next);
count += next_count;
sum += next_sum;
return (double)sum / count;
}

调用方法: getAverage(f)

相关问题

已知f为单链表的表头指针，链表中存储的都是整型数据，试写出实现下列运算的递归算法

要实现单链表的递归操作，比如求和、查找特定值等，首先我们需要定义递归的基本情况和递归调用步骤。这里假设我们有一个简单的单链表结构：

// 单链表节点结构
typedef struct ListNode {
    int val;         // 节点值
    ListNode* next;   // 指向下一个节点的指针
} ListNode;

对于递归函数，我们可以考虑以下几个常见的递归操作：

1. **递归求和 (Sum)**:
- 基本情况：如果链表为空，则返回0。
- 递归情况：对非空链表的头部节点计算其值加上其后继节点值的和。

int sum(ListNode* head) {
    if (head == nullptr) {     // 链表为空，返回0
        return 0;
    } else {
        return head->val + sum(head->next);   // 递归调用
    }
}

2. **查找特定值 (Find)**:
- 基本情况：如果找到目标值，返回当前节点；若遍历到末尾未找到，返回nullptr。
- 递归情况：检查当前节点是否等于目标值，如果不是则继续向下遍历。

ListNode* find(ListNode* head, int target) {
    if (head == nullptr || head->val == target) {   // 找到或结束条件
        return head;
    } else {
        return find(head->next, target);   // 递归调用
    }
}

3. **删除所有等于目标值的节点 (Delete)**
- 基本情况：如果链表为空或节点值不等于目标，直接返回。
- 递归情况：处理当前节点，然后递归处理后继节点。

void deleteNodes(ListNode** head, int target) {
    if (*head != nullptr && (*head)->val == target) {
        ListNode* temp = *head;
        *head = (*head)->next;
        delete temp;
    } else if (*head != nullptr) {
        deleteNodes(&(*head)->next, target);
    }
}

已知f为单链表的表头指针，链表中存储的都是整型数据，试写出实现下列运算的递归算法 求链表中的最大整数 求链表的结点个数

对于单链表，递归算法可以按照以下步骤来实现：

1. **求链表中的最大整数** (Max Value in Linked List)

def max_value(head):
    # 基本情况：空链表或只有一个节点
    if head is None or head.next is None:
        return head.value if head else float('-inf')  # 如果是None则返回负无穷大
    # 递归情况：找到当前节点的最大值和剩余部分的最大值
    else:
        current_max = max(head.value, max_value(head.next))
        return current_max

这个函数首先检查是否到达链表末尾，然后比较当前节点的值与剩余部分的最大值。

2. **求链表的结点个数** (Count Nodes in a Linked List)

def count_nodes(head):
    # 基本情况：空链表
    if head is None:
        return 0
    # 递归情况：当前节点加上剩余部分的节点数
    else:
        return 1 + count_nodes(head.next)

这个函数同样从头开始，如果遇到`head`为空，则表示链表结束，返回0；否则，返回1（当前节点）加上递归计算剩余部分的节点数。