已知f为单链表的表头指针, 链表中存储的都是整型数据,试写出实现下列运算的递归算法: ① 求链表中的最大整数; ② 求链表的结点个数; ③ 求所有整数的平均值。
时间: 2024-05-19 07:12:24 浏览: 15
好的,我会注意回答问题。关于你的问题,递归算法可以实现以下三个操作:
① 求链表中的最大整数:
递归从链表头节点开始,每递归到一个节点就和当前最大值比较,更新最大值并继续递归下一个节点直到链表尾节点。
代码如下:
int getMax(Node* head) {
if (head == NULL) {
return -1; // 链表为空返回-1
}
if (head->next == NULL) {
return head->data; // 已经到达链表末尾,返回当前节点值
}
int maxVal = getMax(head->next); // 继续向下递归
return max(head->data, maxVal); // 返回较大的值
}
② 求链表的结点个数:
递归从链表头节点开始,每递归到一个节点就将计数器加1,继续递归下一个节点直到链表尾节点。
代码如下:
int countNodes(Node* head) {
if (head == NULL) {
return 0; // 链表为空,节点数为0
}
return 1 + countNodes(head->next); // 继续向下递归并累加计数器
}
③ 求所有整数的平均值:
递归从链表头节点开始,每递归到一个节点就将节点值加到累加器中,并统计节点数,继续递归下一个节点直到链表尾节点。当到达链表尾节点时,计算累加器除以节点数的平均值。
代码如下:
double getAvg(Node* head, double sum, int count) {
if (head == NULL) {
return 0; // 链表为空,平均数为0
}
sum += head->data; // 累加节点值
count++; // 计算节点数
if (head->next == NULL) {
return sum / count; // 已经到达链表尾节点,计算平均数
}
return getAvg(head->next, sum, count); // 继续向下递归
}