線性表習(xí)題二

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

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

（2）求鏈表的結(jié)點(diǎn)個(gè)數(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;	//鏈表僅一個(gè)結(jié)點(diǎn)，其值即所求
	int?temp?=?Max(first->link);
	if(first->data>temp)?return?first->data;
	else?return?temp;
}
//遞歸算法：求鏈表中結(jié)點(diǎn)個(gè)數(shù)
int?Num(LinkList?first)
{
	if(first?==?NULL)?return?0;	//空鏈表結(jié)點(diǎn)個(gè)數(shù)為0
	return?1+Num(first->link);
}
//遞歸算法：求鏈表中所有元素平均值
float?Avg(LinkList?first,int?&n)
{
	if(first->link?==?NULL)	//鏈表僅一個(gè)結(jié)點(diǎn)
	{
		n?=?1;
		return?(float)(first->data);
	}
	else
	{
		float?Sum?=?Avg(first->link,n)*n;	//先遞歸求后繼鏈表的平均值
		n++;
		return?(first->data?+?Sum)/n;
	}
}

2、用單鏈表存儲(chǔ)多項(xiàng)式的結(jié)構(gòu)定義如下：

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

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

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

算法的首部為Polynominal createPoly();

Polynomial?createPoly()
{
	Polynomial?head,p,pre,s;
	float?c;int?i?=?0,e;
	cout<<"建立一個(gè)多項(xiàng)式的單鏈表。"<exp?=?-1;head->link?=?NULL;//表頭結(jié)點(diǎn)的exp標(biāo)志為-1
	while(1)
	{
		cout<<"請(qǐng)輸入第"<<++i<<"個(gè)結(jié)點(diǎn)的信息："<>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<<"輸入項(xiàng)的指數(shù)重復(fù)，此次輸入作廢！"<link?=?p;
			pre->link?=?s;
		}
	}
	return?head;
}

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

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

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結(jié)點(diǎn)
			delete?p;
		}
	}
	else?if(pre==NULL)	//空表，鏈接在首部
	{
		t->link?=?poly;
		poly?=?t;
	}
	else	//p->expexp?插在p之前（包括p=NULL,鏈尾）
	{
		pre->link?=?t;
		t->link?=?p;
	}
}