《抽象数据结构一元多项式的实现.doc》由会员分享，可在线阅读，更多相关《抽象数据结构一元多项式的实现.doc（13页珍藏版）》请在金锄头文库上搜索。
1、数据结构实验报告 题目：一元多项式的实现 学 院 计算机学院 专 业 软件工程 年级班别 2010级 4 班 学 号 3110006385 学生姓名 黄 斌 指导教师 李小妹 成 绩 _2012年6月 5 日报告：内容：详细完整不完整设计方案：非常合理合理较差实现：全部实现部分实现未实现文档格式：规范基本规范不规范答辩：理解题目透彻，问题回答流利理解题目较透彻，回答问题基本正确部分理解题目，部分问题回答正确未能完全理解题目，答辩情况较差总评成绩：优良中及格不及格/编译环境：VC6.0 windows 7 （64位）1. 题目一元多项式的抽象数据类型的实现： ADT Polynomial 数据对
2、象：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)初始条件：一
3、元多项式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题目分析：由一元多项式的运算规则可知，一元多项式的加法和减法类似两个有序表的归并，而一元多项式乘法可分解为一系列的一元多项式加法运算。为了使线性列表有序，需要增加按
4、有序关系进行插入的操作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;st
5、ruct 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;i
6、f(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
7、-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 PolynLengt
8、h(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)
9、;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)
10、;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 Multi
11、plyPolyn(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
