一元多项式相加.docx

《一元多项式相加.docx》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、题目：设计并实现以下算法：给出用单链表存储多项式的结构，利用后接法生成多项式的单链表结构，实现两个多项式相加的运算，并就地逆置相加后的多项式链式。一、需求分析1.用户可以根据自己的需求分别输入两个一元多项式，并且能够实现输入的一元多项式的显示。2.能够完成两个一元多项式的相加功能，而且还能显示相加后的逆置的一元多项式。3.程序执行的命令包括：（1）构造链表A（2）构造链表B（3）两个链表的相加（4）求链表的长度（5）打印（显示）已有的链表（6）将已相加的链表进行逆序排列二、概要设计⒈为实现上述算法，需要线性表的抽象数据类型：ADTPolynomial{数据对象：D={ai:

2、ai∈

3、TermSet,i=1…n,n≥0TermSet中的每个元素包含一个表示系数的实数和表示指数的整数}数据关系：R1={

4、ai-1,ai∈D,且ai-1中的指数值

5、项式A和B已存在。操作结果：完成多项式相加运算，即：C=A+B，并且带回C。subtracypolyn(&La,&Lb,)初始条件：一元多项式La和Lb已存在。操作结果：完成多项式的相减运算La=La+Lb，并且销毁多项式Lb。Multiplypolyn(&La,&Lb)初始条件：多项式La，Lb已经存在。操作结果：完成多项式的相乘运算，即La=La*Lb，并销毁多项式Lb。Changlink（L）初始条件：一元多项式L已经存在。操作结果：完成多项式的逆置功能，即将链表逆置。}ADTPolynomial2.本程序有三个模块：⑴主程序模块main(){初始化；{接受命令；显示结果；｝

6、｝⑵链表单元模块：实现链表抽象数据类型操作，即函数的定义模块；三、详细设计⒈元素类型，结点类型typedefstructlnode{floatnum;intexpn;structlnode*next;}*linklist,lnode;linklistinitlink(){linklistp;p=(lnode*)malloc(sizeof(lnode));p->next=null;returnp;}2.对抽象数据类型中的部分基本操作的伪码算法如下：/*创建一个非空链表*/linklistcreatlink(linklistp,floata[],intb[],intn){linklis

7、tr,s;inti;r=p;for(i=0;inum=a[i];s->expn=b[i];r->next=s;r=s;}r->next=null;returnp;}/*求链表的长度*/intlength(linklistp){intn=0;linklistq=p->next;while(q!=null){n++;q=q->next;}returnn;}/*显示链表*/voiddisplay(linklistp){intn=length(p),i;linklistq=p->next;if(n==0)

8、printf("ThePolymialisnull");elseif(n==1)printf("%3.1f%3d",q->num,q->expn);else{for(i=1;i",q->num,q->expn);q=q->next;}printf("%3.1f%3d",q->num,q->expn);}printf("");}/*比较指数*/intcmpexpn(intexpn1,intexpn2){if(expn1>expn2)return-1;elseif(expn1==expn2)return0;elsereturn

9、1;}/*两个一元多项式相加*/linklistaddPolyn(linklistha,linklisthb,linklisthc){linklistla,lb,lc,r;floatsum;la=ha->next;lb=hb->next;lc=hc;while(la&&lb){switch(cmpexpn(la->expn,lb->expn)){case-1:r=(lnode*)malloc(sizeof(lnode));r->num=lb->num;r->expn=