一元多项式的表示及相加.ppt

《一元多项式的表示及相加.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、2.1线性表的类型定义2.3线性表的链式表示和实现2.4一元多项式的表示及相加2.2线性表的顺序表示和实现第二章线性表￡2.4一元多项式的表示及相加若对P,Q,R采用顺序存储结构，则问题很简单：在数学上，一个多项式可表示为：。用线性表可表示为。假设是一元m次多项式：（m

2、很难确定。例如：。就要用一长度为20001的线性表来表示，而表中仅有3个非零元素，这种对内存空间的浪费是应该避免的。为此我们可以用单链表来实现。在单链表中每个结点有两个数据项（系数项和指数项）。例如：和相加。A-1703198517^B-181227-98^C-170111517^227图2.14多项式相加链式存储结构示例一元多项式的实现：typedefstruct{//项的表示floatcoef;//系数intexpn;//指数}term,ElemType;typedefOrderedLinkListpolynomial;//用带表头结点的有序链表表示多项式

3、结点的数据元素类型定义为:voidAddPolyn(Polynomial&Pa,Polynomial&Pb){//多项式加法：Pa=Pa+Pb，利用两个多项式的结点构成“和多项式”。ha=GetHead(Pa);//ha和hb分别指向Pa和Pb的头结点hb=GetHead(Pb);qa=NextPos(Pa,ha);//qa和qb分别指向Pa和Pb中当前结点qb=NextPos(Pb,hb);while(qa&&qb){//qa和qb均非空a=GetCurElem(qa);//a和b为两表中当前比较元素b=GetCurElem(qb);switch(*cmp(

4、a,b)){case-1://多项式PA中当前结点的指数值小ha=qa;qa=NextPos(Pa,qa);break;case0://两者的指数值相等sum=a.coef+b.coef;if(sum!=0.0){//修改多项式PA中//当前结点的系数值SetCurElem(qa,sum);ha=qa;}算法2.15如下：多项式相加else{//删除多项式PA中当前结点DelFirst(ha,qa);FreeNode(qa);}DelFirst(hb,qb);FreeNode(qb);qb=NextPos(Pb,hb);qa=NextPos(Pa,ha);br

5、eak;case1://多项式PB中当前结点的指数值小DelFirst(hb,qb);InsFirst(ha,qb);qb=NextPos(Pb,hb);ha=NextPos(Pa,ha);break;}//switch}//whileif(!ListEmpty(pb))Append(Pa,qb);//链接Pb中剩余结点FreeNode(hb);//释放Pb的头结点}//AddPolyn两个一元多项式相乘的算法，可以利用两个一元多项式相加的算法来实现，因为乘法运算可以分解为一系列的加法运算。假设A(x)和B(x)为多项式：则：M(x)=A(x)×B(x)=A(

6、x)×=其中每一项都是一个一元多项式。本章小结1.了解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构。用前者表示的线性表简称为顺序表，用后者表示的线性表简称为链表。2.熟练掌握这两类存储结构的描述方法，以及线性表的各种基本操作的实现。3.能够从时间复杂度中比较线性表两种存储结构的不同特点及其适用场合。