数据结构——线性表的经典应用

杨伟彬
杨伟彬   发布于 2018-10-08 14:28
阅读量: 177

1. 一元多项式的表示和相加

        在数学上,一个一元多项式\(P_{n}(x)\)可升序写成:

\(P_{n}(x) = p_{0}+p_{1}x^1+p_{2}x^2+...++p_{n}x^n\)

它由n+1个系数唯一确定。因此,在计算机中,可用一个线性表P来表示:

\(P=(p_{0},p_{1},p_{2},...,p_{n})\)

每一项的指数i隐含在其系数\(p_{i}\)的序号里。

       假设\(Q_{m}(x)\)是一元m次多项式,同样可用线性表Q来表示:

\(Q=(q_{0},q_{1},q_{2},...,q_{n})\)

 

        不失一般性,设m < n,则两个多项式相加的结果可用线性表R表示:

\(R=(p_{0}+q_{0},p_{1}+q_{1},p_{2}+q_{2},...,p_{n}+q_{n})\)但是,只存储系数的方案对存在大量零系数的多项式并不适用

\(S(x)=1+3x^{10000}+2x^{20000}\)

       要用一个长度为20001的线性表来表示,表中仅有3个非零系数,会浪费大量存储空间。

若只存储非零系数项,则必须同时存储相应的指数。

一般情况下,一元n次多项式可写成:

\(P_{n}=p_1x^{e_1}+p_2x^{e_2}+...+p_mx^{e_m}\)

其中,\(p_i\)是指数为\(e_i\)的项的非零系数,且满足

\(0 \le e_1 < e_2<...<e_m=n\)

       若用一个长度为m且每个元素有两个数据项(系数项和指数项)的线性表

\(((p_1,e_1),(p_2,e_2),...,(p_m,e_m))\)

       便可唯一确定多项式\(P_n(x)\)。在最坏情况下,n+1(=m)个系数都不为零,则比只存储每项系数的方案要多存储一倍的数据,但是对于\(S(x)\)类多项式,这种存储表示将大大节省空间。

        一元多项式可采用两种存储表示方法。在实际工程中使用哪一种?视多项式进行哪种运算而定。若只对多项式进行求值不改变多项式的系数和指数的运算,则采用顺序存储结构;否则,采用链式存储结构。本节讨论使用链式存储形式。

例如:

\(A_{17}(x)=7+3x+9x^8+5x^{17}\)   

\(B_8(x)=8x+22x^{7}-8x^8\)

     采用单链表存储效果如下:

       将两个多项式相加为:

\(C_{17}(x)=7+11x+22x^7+5x^{17}\)

 

       采用单链表存储效果如下:

2. 一元多项式的实现

       (1)一元多项式抽象数据类型的动态链式表示

typedef struct	//项的表示,多项式的项作为LinkList的数据元素
{
	float coef;	//系数
	int expn;		//指数
}term, ElemType;
//两个类型名:term用于本ADT,ElemType为LinkList的数据对象名

typedef struct Node
{
	ElemType data;
	struct Node * next;	
}LNode, *LinkList, *Position;

typedef LinkList polynomial;

       (2)一元多项式的创建

void CreatPolyn(polynomial &P, int m)
	//输入m项的系数和指数,建立表示一元多项式的有序链表P
{
	polynomial h;	ElemType e;		
int i;
	InitList(P);
	h = P;
	e.coef = 0.0;
	e.expn = -1;
	SetCurElem(h, e);	//设置头结点的数据元素
	for(i = 1; i <= m; ++i)
	{
		Position q;	LinkList s;
		scanf("%f %d",&e.coef,&e.expn);
		if(!LocateElem(P, e, q, cmp))	//当前链表不存在该指数项
		{
			if(MakeNode(s, e))
				InsFirst(q,s);			//生成结点并插入链表
		}
	}
}//CreatPolyn

在函数CreatPolyn里面用到函数的说明:
int cmp(term a, term b)
//依a的指数值<、=或>b的指数值,分别返回-1、0或+1
	
Status LocateElem(polynomial L, term e, Position &q, int  (*compare)(term,term))
//若升序链表L中存在与e满足判定函数compare()取值为0的元素,则q指示L中 
//第一个值为e的结点的位置,并返回TRUE;否则q指示第一个与e满足判定函数
//compare()取值>0的元素的前驱的位置。并返回FALSE。(用于一元多项式)

Status MakeNode(LinkList &p, ElemType e)
//分配由p指向的值为e的结点,并返回OK;若分配失败。则返回ERROR.

Status InsFirst(LinkList q, LinkList s)
//将s指向的结点,插入到q指向的结点后面

         (3)一元多项式的相加

 

void AddPolyn(polynomial &Pa, polynomial &Pb)
	//多项式的加法:Pa = Pa + Pb,利用两个多项式的结点构成“和多项式”。 
{
	LinkList ha = Pa;		//ha和hb分别指向Pa和Pb的头指针
	LinkList hb = Pb;
	LinkList qa = Pa->next;
	LinkList qb = Pb->next;	//ha和hb分别指向pa和pb的前驱
	while (qa && qb)		//如果qa和qb均非空
	{
		float sum = 0.0;
		term a = qa->data;
		term b = qb->data;
		switch (cmp(a,b))
		{
		case -1:	//多项式PA中当前结点的指数值小
			ha = qa;
			qa = qa->next;
			break;
		case 0:		//两者指数值相等
			sum = a.coef + b.coef;
			if(sum != 0.0)
			{	//修改多项式PA中当前结点的系数值
				qa->data.coef = sum;
				ha = qa;
			}else
			{	//删除多项式PA中当前结点
				DelFirst(ha, qa);
				free(qa);
			}
			DelFirst(hb, qb);
			free(qb);
			qb = hb->next;
			qa = ha->next;
			break;
		case 1:
			DelFirst(hb, qb);
			InsFirst(ha, qb);
			qb = hb->next;
			ha = ha->next;
			break;
		}//switch
	}//while
	if(!ListEmpty(Pb))
		Append(Pa,qb);
	DestroyList(hb);

}//AddPolyn

       在AddPolyn函数里面用到的函数说明:

Status DelFirst(LinkList h, LinkList q) 
//h指向q的前驱,让h指向q的下一个结点
Status Append(LinkList &L, LinkList s)
//将指针s(s->data为第一个数据元素)所指(彼此以指针相链,以NULL结尾)的
//一串结点链接在线性链表L的最后一个结点之后
  

 

收藏 转发 评论