数据结构:用递归函数求链表各节点和的平均值

设计一个函数double getaverage(List f, int *nodenum) 
已知f为一个不带头结点单向链表的头指针，链表结点数据结构如下所示，使用递归函数，求出所有结点中数值的平均数。 nodenum为结点数的输出参数，返回平均数，如果为空链表，则返回0。
List的结构如下：
typedef struct T_Node{
    int d;
    struct T_Node *next;
} Node, *List;
createlink函数如下：
void createlink(List *pf)
{
    int i;
    Node *p;

    *pf = (Node *)malloc(sizeof(Node));
    p = *pf;
    for(i = 1; i <= 99; i++)
    {
        p->d = i;
        p->next = (Node *)malloc(sizeof(Node));
        p = p->next;
    }
    p->d = 100;
    p->next  = NULL;
}

main函数如下：
int main()
{
    int n;
    List f;
    double a;
    createlink(&f);
    a = getaverage(f, &n);
    printf("%d  %lf\n",n, a);
    return 0;
 }
函数getaverage如下：

double getaverage(List f, int *nodenum)
{
	
	double temp;              /*设置temp用来存储并返回，到当前节点的前一个结点为止所求得的均值*/
	if(f==NULL)               /*当链表为空时，按照题目要求，该返回的值*/
	{
		(*nodenum)=0;
		return 0;
	}
	else
	{
		temp=getaverage(f->next,nodenum);    /*到上一个结点为止所求的均值*/
		return (temp*(*nodenum)+f->d)/(++(*nodenum));	 
	}
}
    /*到上一个为止所求的均值，乘上到上一个节点为止的结点数，等于当前结点之前所有结点的和，再加上当前结点的值，等于到当前节点所有结点值的和，最后除以当前的结点数，得到到当前结点为止的均值*/

整体代码如下：

#include
#include

typedef struct T_Node{
	int d;
	struct T_Node *next;
} Node, *List;

void createlink(List *pf)
{
	int i;
	Node *p;

	*pf = (Node *)malloc(sizeof(Node));
	p = *pf;
	for(i = 1; i <= 99; i++)
	{
		p->d = i;
		p->next = (Node *)malloc(sizeof(Node));
		p = p->next;
	}
	p->d = 100;
	p->next  = NULL;
}

double getaverage(List f, int *nodenum)
{
	
	double temp;
	if(f==NULL)
	{
		(*nodenum)=0;
		return 0;
	}
	else
	{
		temp=getaverage(f->next,nodenum);
		return (temp*(*nodenum)+f->d)/(++(*nodenum));	 
	}
}

int main()
{
	int n;
	List f;
	double a;
	createlink(&f);
	a = getaverage(f, &n);
	printf("%d  %lf\n",n, a);
	return 0;
 }

 运行结果：

小结：

就我个人来说的话，我是不太喜欢用递归算法的。当然在有些情况下递归算法会很简洁，但能用递归解决的问题，用循环基本上都可以解决。而递归算法可能出现许多不可预知的错误，不容易检查出来。

就这道题目而言，最核心的问题，莫过于解决当f不是空链表时的返回值。如果可以熟练掌握栈的话，应该知道，递归算法实际上就是栈。当当前结点不为空的话，会一直向下一个结点运算，直至为空，然后从最后一个结点逐级返回。