一元多项式的相加(数据结构).docx

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

1、实验报告课程名称：数据结构实验名称：一元多项式的相加班级：1333学生姓名：蔡景旺学号：37一、需求分析1.用户可以根据自己的需求分别输入两个一元多项式（输入必须按指数递增顺序），并且能够实现输入的一元多项式的显示。2.能够完成两个一元多项式的相加功能并显示结果。3.程序执行的命令包括：（1）构造链表A（2）构造链表B（3）两个链表的相加（4）求链表的长度（5）打印（显示）已有的链表二、概要设计⒈为实现上述算法，需要线性表的抽象数据类型：ADTPolynomial{数据对象：D={ai:

2、ai∈Term

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

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

5、始条件：一元多项式P已存在。操作结果：返回一元多项式中P的项数。AddPolyn(&Pa,&Pb)初始条件：一元多项式Pa和Pb已存在。操作结果：完成一元多项式相加运算，即：Pa=Pa+Pb,销毁一元多项式Pb.}ADTPolynomailtypedefstruct{//项的表示，多项式为linklist的数据元素floatcoef;//系数intevpn;//指数}term,ElemType;//两个类型名：term用于本ADT,ElemType为Linklist的数据对象名TypedefLinkli

6、stpolynomial;//用带表头结点的有序链表表示多项式；Intcmp(terma,termb)；voidCreatPolyn(polynomial&P,intm){//输入m项的系数和指数，建立表示一元多项式的有序链表PInitList(P);h=GetHead(P);e.coef=0.0;e.expn=-1;SetCurElem(h,e);//设置头结点的数据元素for（i=1;i<=m;++i）{//依次输入m项非零项scanf(e.coef,e.expn);if(!LocateElem(P

7、,e,q,(*cmp)){//当链表不存在指数项if(MakeNode(s,e))InsFirst(q,s);//生成结点并插入链表}}}//CreatPolynvoidAddPolyn(polynomial&Pa,polynomial&Pb){//多项式加法：Pa=Pa+Pb，利用两个多项式的结点构成“和多项式”ha=Gethead(Pa);hb=Gethead(Pb);//ha和hb分别指向Pa和Pb的头结点qa=NextPos(Pa,ha);qb=NextPos(Pb,hb);///ha和hb分别

8、指向Pa和Pb的当前结点while(qa&&qb){//qa和qb均非空a=GetCurElem(qa);b=GetCurElem(qb);switch(*cmp(a,b)){case-1://多项式PA中当前结点的指数值小ha=qa;qa=NextPos(Pa,ha);break;case0://l两者的指数相等sum=a.cofe+b.cofe;if(sum!=0.0){//修改多项式PA中当前结点的系数值SetCurELem(qa,sum);ha=qa;}else{//删除当前结点Delfirst

9、(ha,qa);FreeNode(qa);}Delfirst(ha,qa);FreeNode(qa);qb=NextPos(Pb,hb);qa=NextPos(Pa,ha);break;Case1://多项式PB中当前结点的指数值小DelFirst(hb,qb);InsFirst(ha,qb);qb=NextPos(Pb,hb);qa=NextPos(Pa,ha);break;}//swtich}//whileIf(!ListEmpty(Pb))Append(Pa,qb);FreeNode(hb)://

10、释放Pb头结点}//AddPolyn2.数据结构分析：逻辑结构为线性表，采用链式存储结构。因为我们要让一元多项式相加，需要使得数据变更，采用顺序存储结构的话，工作量就运用起来不便捷。因此链式存储结构显得更加简单方便。3.本程序有三个模块：⑴主程序模块main(){初始化；{构造线性表1；构造线性表2；相加；显示结果；｝｝⑵函数调用关系Main↓------------------------------------------------↓