题目

已知L为不带表头结点的单链表的表头指针（L非空），链表中存储的都是整型数据，写出实现下列运算的递归算法。

（1）求链表中的最大整数

（2）求链表中的结点个数

（3）求所有整数的平均值

分析

使用递归的方法。

代码

核心代码：

/* 求链表中的最大整数 */
int getMax(LNode *L) {
	if(L->next==NULL) { // 链表中仅一个结点
		return L->data; // 其值即为所求
	}
	int temp=getMax(L->next);// 递归求后继结点的最大值
	if(L->data>temp) { // 再与首元结点相比较，取大值
		return L->data;
	} else {
		return temp;
	}
}

/* 求链表中的结点个数 */
int getNum(LNode *L) {
	if(L->next==NULL) { // 链表仅有一个结点
		return 1;
	}
	return 1+getNum(L->next);// 否则求后继链表结点数再加1
}

/* 求所有整数的平均值 */
float getAvg(LNode *L,int n) {
	if(L->next==NULL) { // 链表仅有一个结点
		return (float)(L->data);// 其值即为所求
	} else {
		float sum=getAvg(L->next,n-1)*(n-1);// 求后面n-1各结点值的和
		return (float)(L->data+sum)/n;// 然后加上首结点的值求平均值
	}
}

完整代码：

#include <stdio.h>
#include <stdlib.h>

// 声明单链表结构体
typedef struct LNode {
    int data;
    struct LNode *next;
} LNode;

/* 通过用户输入数据创建一个单链表，由用户输入整型测试数据 */
/* 返回一个单链表 */
LNode *createList() {
    LNode *head;
    LNode *p1, *p2;
    p1 = p2 = (LNode *) malloc(sizeof(LNode));
    head = (LNode *) malloc(sizeof(LNode));
    scanf("%ld", &p1->data);
    int i = 0;
    while (p1->data != 0) { // 当用户在控制台输入0时结束循环
        i += 1;
        if (i == 1) {
            head = p1;
        } else {
            p2->next = p1;
        }
        p2 = p1;
        p1 = (LNode *) malloc(sizeof(LNode));
        scanf("%ld", &p1->data);
    }
    p2->next = NULL;
    return head;
}

/* 打印单链表 */
/* *list指的是要被打印输出的单链表 */
void printList(LNode *list) {
    printf("\n");
    while (list != NULL) { // 循环单链表
        printf("%ld\t", list->data); // 打印单链表中的data数据
        list = list->next; // 遍历至下一个结点
    }
    printf("\n"); // 换行
}

/* 求链表中的最大整数 */
int getMax(LNode *L) {
    if (L->next == NULL) { // 链表中仅一个结点
        return L->data; // 其值即为所求
    }
    int temp = getMax(L->next);// 递归求后继结点的最大值
    if (L->data > temp) { // 再与首元结点相比较，取大值
        return L->data;
    } else {
        return temp;
    }
}

/* 求链表中的结点个数 */
int getNum(LNode *L) {
    if (L->next == NULL) { // 链表仅有一个结点
        return 1;
    }
    return 1 + getNum(L->next);// 否则求后继链表结点数再加1
}

/* 求所有整数的平均值 */
float getAvg(LNode *L, int n) {
    if (L->next == NULL) { // 链表仅有一个结点
        return (float) (L->data);// 其值即为所求
    } else {
        float sum = getAvg(L->next, n - 1) * (n - 1);// 求后面n-1各结点值的和
        return (float) (L->data + sum) / n;// 然后加上首结点的值求平均值
    }
}

int main() {
    /* [0.]创建初始测试单链表 */
    LNode *list;
    list = createList();// 创建测试链表
    printList(list);// 打印单链表

    printf("最大值：%d\n", getMax(list));
    printf("结点个数：%d\n", getNum(list));
    printf("平均值：%2.f\n", getAvg(list, getNum(list)));

    return 0;
}

运行结果：

 

关于求所有整数的平均值图解如下：至于为什么要乘以 (n-1)，是因为我们求平均值的常用方法是先求和再除以元素个数最后得到平均值，而 getAvg() 方法会计算得到平均值，而 getAvg()*(n-1) 会恢复为它的和值。如已知平均值是 4.5，又元素个数是 2，那么就可以求得两个元素的总和为 4.5*2=9，而最终实际上还是计算得到所有的和然后除以元素个数得到平均值。