抽象数据结构一元多项式的实现.doc

数据结构实验报告 题目：一元多项式的实现 学 院 计算机学院 专 业 软件工程 年级班别 2010级 4 班 学 号 3110006385 学生姓名 黄 斌 指导教师 李小妹 成 绩 _2012年6月 5 日报告：内容：详细完整不完整设计方案：非常合理合理较差实现：全部实现部分实现未实现文档格式：规范基本规范不规范答辩：理解题目透彻，问题回答流利理解题目较透彻，回答问题基本正确部分理解题目，部分问题回答正确未能完全理解题目，答辩情况较差总评成绩：优良中及格不及格/编译环境：VC6.0 windows 7 （64位）1. 题目一元多项式的抽象数据类型的实现： ADT Polynomial 数据对象：D ai | aiTermSet, i=1,2,.,m, m0 TermSet中的每个元素包含一个表示系数的实数和表示指数的整数 数据关系：R1 |ai-1, aiD, i=2,.,n 基本操作： 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。SubtractPolyn(&Pa,&Pb)初始条件：一元多项式Pa和Pb已存在；操作结果:完成多项式相减运算，即Pa=Pa-Pb，并销毁一元多项式Pb。MultiplyPolyn(&Pa,&Pb)初始条件：一元多项式Pa和Pb已存在；操作结果:完成多项式相乘运算，即Pa=Pa-Pb，并销毁一元多项式Pb。 ADT Polynomial题目分析：由一元多项式的运算规则可知，一元多项式的加法和减法类似两个有序表的归并，而一元多项式乘法可分解为一系列的一元多项式加法运算。为了使线性列表有序，需要增加按有序关系进行插入的操作int OrderInsert(Link p,Link e)，该操作还可返回链表结点数目的变化，有利于对一元多项式项数的统计。2存储结构定义公用头文件#include #include #include /带头结点单链表存储结构typedef struct / 项的表示,多项式的项作为LinkList的数据元素 float coef;/ 系数 int expn;/ 指数 term, ElemType;/ 两个类型名:term用于本ADT,ElemType为LinkList的数据对象名 typedef struct LNode / 结点类型 ElemType data;struct LNode *next;LNode,*Link,*Position;typedef struct _LinkList / 链表类型 Link head;/ 指向线性链表中的头结点 int len;/ 指示当前线性链表中数据元素的个数 LinkList,*PLinkList;3. 算法设计/带头结点单链表int OrderInsert(Link p,Link e)/按系数从小到大插入多项式的项，返回值表示项数的变化，-1,0,1分别表示 减少一项，项数不变，增加一项for(;p-next;p=p-next)if(p-next-data.expn=e-data.expn) break;if(p-next)if(p-next-data.expn=e-data.expn) p-next-data.coef=p-next-data.coef+e-data.coef;free(e);if(p-next-data.coef=0)e=p-next;p-next=p-next-next;free(e);return -1;return 0;elsee-next=p-next;p-next=e;return 1;elsee-next=p-next;p-next=e;return 1;void DestroyPolyn(PLinkList L)/销毁一元多项式Link p,q;p=L-head-next;for(;p;)q=p-next;free(p);p=q;free(L-head);L-len=0;void CreatPolyn(PLinkList L,int m)/创建一元多项式Link p,e;int i;int tag=0;int count=0;p=(Link)malloc(sizeof(LNode);p-data.coef=0.0;p-data.expn=-1;p-next=NULL;L-head=p;for(i=0;idata.coef,&e-data.expn);tag=OrderInsert(p,e);if(taglen=count;int PolynLength(PLinkList L)/返回多项式的项数return L-len;void PrintPolyn(PLinkList L)/打印一元多项式Link p;p=L-head-next;printf(该一元多项式共有%d 项，多项式如下:n,PolynLength(L);if(L-len) printf(P(x)=%.3fx%d,p-data.coef,p-data.expn);p=p-next;elseprintf(P(x)=0n);return ;for(;p;p=p-next)if(p-data.coef0)printf(+%.3fx%d,p-data.coef,p-data.expn);else printf(%.3f x%d ,p-data.coef,p-data.expn);printf(n);void AddPolyn(PLinkList La,PLinkList Lb)/多项式相加Link p1,p2,e;int count=0;p1=La-head;p2=Lb-head-next;for(;p2;p2=p2-next)e=(Link)malloc(sizeof(LNode);e-data.coef=p2-data.coef;e-data.expn=p2-data.expn;count=count+OrderInsert(p1,e);DestroyPolyn(Lb);La-len=La-len+count;void SubtractPolyn(PLinkList La,PLinkList Lb)/多项式相减Link p1,p2,e;int count=0;p1=La-head;p2=Lb-head-next;for(;p2;p2=p2-next)e=(Link)malloc(sizeof(LNode);e-data.coef=-p2-data.coef;e-data.expn=p2-data.expn;count=count+OrderInsert(p1,e);DestroyPolyn(Lb);La-len=La-len+count;void MultiplyPolyn(PLinkList La,PLinkList Lb)/多项式相乘LinkList Ld;Link e,pa,pb,q;pa=La-head-next;La-head-next=NULL;La-len=0;pb=(Link)malloc(sizeof(LNode);pb-next=NULL;for(;pa;)q=pa-next;e=(Link)malloc(sizeof(LNode);e-data.coef=pa-data.coef;e-data.expn=pa-data.expn;e-next=pb-next;pb-next=e;free(pa);pa=q;pb=pb-next;for(;pb;)q=pb-next;CreatPolyn(&Ld,0);pa=Lb-head-next;for(;pa;pa=pa-next)e=(Link)malloc(sizeof(LNode);e-data.coef=pa-data.coef*pb-data.coef;e-data.expn=pa-data.expn+pb-data.expn;OrderInsert(Ld.head,e);AddPolyn(La,&Ld);free(pb);pb=q;DestroyPolyn(Lb);4测试/带头结点单链表void main()LinkList L,La,Lb;int m;dosystem(cls);printf(-n);printf(按键操作指引:n);printf(创建一个新的一元多项式： 1n);printf(打印一元多项式： 2n);printf(销毁一元多项式： 3n);printf(创建两个一元多项式并相加： 4n);printf(创建两个一元多项式并相减： 5n);printf(创建两个一元多项式并相乘： 6n);printf(-n);switch(getch()case 1:printf(请输入多项式的项数：);scanf(%d,&m);CreatPolyn(&L,m);break;case 2:PrintPolyn(&L);break;case3:DestroyPolyn(&L);break;case 4:printf(n一元多项式相加nn请输入第一个多项式的项数：);scanf(%d,&m);CreatPolyn(&La,m);PrintPolyn(&La);printf(请输入第二个多项式的项数：);scanf(%d,&m);CreatPolyn(&Lb,m);PrintPolyn(&Lb);AddPolyn(&La,&Lb);printf(相加得到的一元多项式为：n);PrintPolyn(&La);break;case 5:printf(n一元多项式相减nn请输入第一个多项式的项数：);scanf(%d,&m);CreatPolyn(&La,m);PrintPolyn(&La);printf(请输入第二个多项式的项数：);scanf(%d,&m);CreatPolyn(&Lb,m);PrintPolyn(&Lb);SubtractPolyn(&La,&Lb);printf(相减得到的一元多项式为：n);PrintPolyn(&La);break;case 6:printf(n一元多项式相乘nn请输入第一个多项式的项数：);scanf(%d,&m);CreatPolyn(&La,m);PrintPolyn(&La);printf(请输入第二个多项式的项数：);scanf(%d,&m);CreatPolyn(&Lb,m);PrintPolyn(&Lb);MultiplyPolyn(&La,&Lb);printf(相乘得到的一元多项式为：n);PrintPolyn(&La);break;default:printf(指令错误!n);printf(nn按任何键继续，想退出请按 0 n);while(getch()!=0);测试结果以及分析初始界面：程序功能指引一元多项式的加法，减法以及乘法的实现与输出分析：该程序能完成一元多项式的各种操作，但还存在未完成异常处理：在多项式不存在的情况下，对多项式的输出和销毁会造成程序中断退出。5顺序映像和带头结点单链表两种种存储结构的比较存储结构顺序映象带（无）头结点单链表基本操作时间复杂度CreatPolyn( &L, m)由于顺序映像的插入删除操作过于繁琐，只适合一元多项式的求值，所以没有实现O(n)PrintPolyn(L)O(n)PolynLength(L)O(1)DestroyPolyn(&L)O(n)AddPolyn(&La,&Lb)O(n)SubtractPolyn(&La,&Lb)O(n)MultiplyPolyn(&La,&Lb)O(m*(n+1)优缺点分析优 点结构简单，可对多项式随机读取，方便多项式求值对各项的插入及删除不用移