1、已知 first 為單鏈表的表頭指針，鏈表中存儲的都是整型數(shù)據，試寫出實現(xiàn)下列運算的遞歸算法：

（1）求鏈表中的最大整數(shù)：

（2）求鏈表的結點個數(shù)。

（3）求鏈表中所有元素的平均值。

#includeusing?namespace?std;
typedef?int?Elemtype;?
typedef?struct?node
{
	Elemtype?data;
	struct?node?*link;
}?Node,*LinkList;
//遞歸算法：求鏈表中的最大值
int?Max(LinkList?first)
{
	if(first->link?==?NULL)?return?first->data;	//鏈表僅一個結點，其值即所求
	int?temp?=?Max(first->link);
	if(first->data>temp)?return?first->data;
	else?return?temp;
}
//遞歸算法：求鏈表中結點個數(shù)
int?Num(LinkList?first)
{
	if(first?==?NULL)?return?0;	//空鏈表結點個數(shù)為0
	return?1+Num(first->link);
}
//遞歸算法：求鏈表中所有元素平均值
float?Avg(LinkList?first,int?&n)
{
	if(first->link?==?NULL)	//鏈表僅一個結點
	{
		n?=?1;
		return?(float)(first->data);
	}
	else
	{
		float?Sum?=?Avg(first->link,n)*n;	//先遞歸求后繼鏈表的平均值
		n++;
		return?(first->data?+?Sum)/n;
	}
}

2、用單鏈表存儲多項式的結構定義如下：

typedef?struct?Term?{	//多項式的項
	float?coef;		//系數(shù)
	int?exp;		//指數(shù)
	struct?Term?*link;	//鏈指針
}?Term,*Polynomial;

試編寫一個算法，輸入一組多項式的系數(shù)和指數(shù)，按指數(shù)降冪的方式建立多項式鏈表，要求該鏈表具有表頭結點。

如果輸入的指數(shù)與鏈表中已有的某一個項的指數(shù)相等，則新的項不加入，并報告作廢信息。整個輸入序列以輸入系數(shù)為0標志結束。

算法的首部為Polynominal createPoly();

Polynomial?createPoly()
{
	Polynomial?head,p,pre,s;
	float?c;int?i?=?0,e;
	cout<<"建立一個多項式的單鏈表。"<exp?=?-1;head->link?=?NULL;//表頭結點的exp標志為-1
	while(1)
	{
		cout<<"請輸入第"<<++i<<"個結點的信息："<>c>>e;
		if(c==0)?break;
		s?=?new?Term;
		s->coef?=?c;?s->exp?=?e;
		p?=?head;?pre?=?NULL;
		while(p!=NULL&&p->exp>e)
		{
			pre?=?p;
			p?=?p->link;
		}
		if(p!=NULL&&p->exp==e)?cout<<"輸入項的指數(shù)重復，此次輸入作廢！"<link?=?p;
			pre->link?=?s;
		}
	}
	return?head;
}

給出在多項式中插入新項的算法Insert。各個項的指數(shù)ei按遞減順序排列：em-1>em-2>...>e0>0 ?該算法的功能是：如果多項式中

沒有與新項的指數(shù)相等的項，則將此新項插入到多項式鏈表的適當位置；如果多項式中已有與新項指數(shù)相等的項，則將它們合并。

typedef?struct?Term
{
	float?coef;
	int?exp;
	struct?Term?*link;
}?Term,*Polynominal;
void?Insert(Polynominal?poly,Term?*t)
{
	Polynominal?p?=?poly,pre?=?NULL;
	while(p!=NULL&&p->exp>t->exp)
	{
		pre?=?p;
		p?=?p->link;
	}
	if(p->exp==t->exp)
	{
		if(p->coef?+?t->coef!=0)
		{
			p->coef=p->coef+t->coef;?//合并
		}
		else
		{
			pre->link?=?p->link;	//刪除p結點
			delete?p;
		}
	}
	else?if(pre==NULL)	//空表，鏈接在首部
	{
		t->link?=?poly;
		poly?=?t;
	}
	else	//p->expexp?插在p之前（包括p=NULL,鏈尾）
	{
		pre->link?=?t;
		t->link?=?p;
	}
}