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

实验报告课程名称： 数据结构 实验名称： 一元多项式的相加 班 级： 1333 学生姓名： 蔡景旺 学号： 37 一、 需求分析1. 用户可以根据自己的需求分别输入两个一元多项式（输入必须按指数递增顺序），并且能够实现输入的一元多项式的显示。2. 能够完成两个一元多项式的相加功能并显示结果。3. 程序执行的命令包括：（1）构造链表A （2）构造链表B （3）两个链表的相加 （4）求链表的长度 （5）打印（显示）已有的链表 二、概要设计 为实现上述算法，需要线性表的抽象数据类型：ADT Polynomial 数据对象：D=ai:|aiTermSet,i=1n,n0TermSet 中的每个元素包含一个表示系数的实数和表示指数的整数数据关系：R1=|ai-1,aiD,且ai-1中的指数值 ai 中的指数值i=2,n0基本操作: CreatPolyn(&p,m)操作结果：输入m项的系数和指数，建立一个一元多项式P。 DestroyPolyn(&p)初始条件：一元多项式P已存在。操作结果：销毁一元多项式P。 PrintPolyn(P)初始条件：一元多项式P已存在。操作结果：打印输出一元多项式P。 PolynLength(P)初始条件：一元多项式P已存在。操作结果：返回一元多项式中P的项数。 AddPolyn(&Pa,&Pb)初始条件：一元多项式Pa和Pb已存在。操作结果：完成一元多项式相加运算，即：Pa=Pa+Pb,销毁一元多项式Pb.ADT Polynomailtypedef struct / 项的表示，多项式为linklist的数据元素 float coef; /系数 int evpn; /指数term,ElemType; /两个类型名：term用于本ADT,ElemType为Linklist的数据对象名Typedef Linklist polynomial; /用带表头结点的有序链表表示多项式；Int cmp(term a,term b)；void CreatPolyn (polynomial &P,int m)/输入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,e,q,(*cmp) /当链表不存在指数项if(MakeNode (s,e) InsFirst(q,s);/生成结点并插入链表/CreatPolynvoid AddPolyn(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分别指向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;case 0:/l两者的指数相等 sum=a.cofe+b.cofe; if(sum!=0.0)/修改多项式PA中当前结点的系数值 SetCurELem(qa,sum);ha=qa;else /删除当前结点Delfirst(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):/释放Pb头结点/AddPolyn2. 数据结构分析：逻辑结构为线性表，采用链式存储结构。因为我们要让一元多项式相加，需要使得数据变更，采用顺序存储结构的话，工作量就运用起来不便捷。因此链式存储结构显得更加简单方便。3.本程序有三个模块： 主程序模块 main()初始化；构造线性表1；构造线性表2；相加；显示结果； 函数调用关系 Main - CreatPolyn(&p,m) AddPolyn(&Pa,&Pb) PrintPolyn(P)4Addpolyn流程开始 CreatPolyn(&p,m)AddPolyn(&Pa,&Pb) PrintPolyn(P)PrintPolyn(P)结束 三、详细设计#include#include#define Len sizeof (struct link)struct linkint coef,expn;struct link * next;void main()int n,m,i,j;struct link *head1,*rear1,*p,*head2,*rear2,*head3,*rear3;head1=rear1=(struct link *)malloc(Len);printf(请输入第一个一元多项式的项数n);scanf(%d,&m);printf(请输入第一个一元多项式的系数和指数n);for(i=0;icoef,&p-expn);rear1-next=p;p-next=NULL;rear1=p;rear1=head1-next;head2=rear2=(struct link *)malloc(Len);printf(请输入第二个一元多项式的项数n);scanf(%d,&n);printf(请输入第二个一元多项式的系数和指数n);for(i=0;icoef,&p-expn);rear2-next=p;p-next=NULL;rear2=p;rear2=head2-next;head3=rear3=(struct link *)malloc(Len);while(rear1!=NULL&rear2!=NULL)p=(struct link *)malloc(Len);if(rear1-expn=rear2-expn)p-coef=rear1-coef+rear2-coef;p-expn=rear2-expn;rear1=rear1-next;rear2=rear2-next;i+;j+;rear3-next=p;rear3=p;else if(rear1-expnrear2-expn)p-coef=rear2-coef;p-expn=rear2-expn;rear3-next=p;rear3=p;j+;rear2=rear2-next;else if(rear1-expnexpn)p-coef=rear1-coef;p-expn=rear1-expn;rear3-next=p;rear3=p;i+;rear1=rear1-next;while(rear1!=NULL)p=(struct link *)malloc(Len);p-coef=rear1-coef;p-expn=rear1-expn;rear3-next=p;rear3=p;rear1=rear1-next;while(rear2!=NULL)p=(struct link *)malloc(Len);p-coef=rear2-coef;p-expn=rear2-expn;rear3-next=p;rear3=p;rear2=rear2