《数据结构课程设计_一元多项式计算器》由会员分享，可在线阅读，更多相关《数据结构课程设计_一元多项式计算器（12页珍藏版）》请在金锄头文库上搜索。
1、实习1、一元稀疏多项式计算器一、需求分析1. 问题描述设计一个一元稀疏多项式简单计算器。2. 基本要求一元稀疏多项式简单计算器的基本功能是：(1) 输入并建立多项式。(2) 输出多项式，输出形式为整数序列：n, q, % c2, e2,，cn, en，其中n是多项式 的项数，cx,ex分别是第i项的系数和指数，序列按指数降序排列。(3) 多项式a和b想加，建立多项式a+b。(4) 多项式a和b想减，建立多项式a-b。3. 测试数据(1) (2x+5x8-3.1x11)+(7-5x8+11x9)=(-3.1x11+11x9+2x+7)(2) (6x-3-x+4.4x2T.2x9)-(-6x-3+
2、5.4x2-x2+7.8x15)=(-7.8x15T.2x9+12x-3-x)(3) (1+x+x2+x3+x4+x5 )+(-x3-x4)=(1+x+x2+x5)(4) (x+x3)+(-x-x3)=0(5) (x+x100)+(x100+x200)=(x+2x100+x200)(6) (x+x2+x3)+0=(x+x2+x3)(7) 互换测试数据的前后两个多项式。4. 实现提示用带表头结点的单链表存储多项式。二、概要设计为实现上述程序功能，应用带头结点的单链表存储多项式。为此需要一个抽象数据类 型：一元多项式。1.抽象数据类型一元多项式定义为：ATD Ploynomial数据对象：D=ai
3、|ai ETermset, i=1,2,3，m,mN0 Termset中的每个元素包含一个表示 系数的实数和表示指数的整数数据关系：R1 = ai-1,aiED,且ai-1中的指数ai中的指数的值，i=1,2,3*n基本操作：Insert(p,h)初始条件：h已存在。操作结果：插入p项。CreateLinklist(head, m)操作结果：建立一个头指针为head、项数为m的一元多项式。DestroyLinklist( p)初始条件：一元多项式p已存在。操作结果：销毁一元多项式p。PrintLinklist( P)初始条件：一元多项式p已存在。操作结果：输出一元多项式p。Compare(a,
4、b)初始条件：项a,b已存在。操作结果：比较a,b中x的指数的大小。AddLinklist(pa,pb)初始条件：一元多项式pa,pb已存在。操作结果：完成一元多项式pa,pb的相加运算。SubtractionLinklist(Sa,Sb)初始条件：一元多项式Sa,Sb已存在。操作结果：完成一元多项式Sa,Sb的相减运算。 ATD Ploynomial三、详细设计(源代码)(使用C语言)#include#include#define maxlen 10#define large 999typedef struct Linklistomialfloat coef;int expn;struct
5、Linklistomial *next;Linklistomial,*Linklist;/结点类型，指针类型void Insert(Linklist p,Linklist h)/ h已存在插入p项if(p-coef=0)free(p);/系数为0的话释放结点elseLinklist q1,q2;q1=h;q2=h-next;while(q2&p-expnexpn) /查找插入位置q1=q2;q2=q2-next;if(q2&p-expn=q2-expn) /将指数相同相合并 q2-coef+=p-coef;free(p);if(!q2-coef)/系数为0的话释放结点q1-next=q2-ne
6、xt;free(q2);else /指数为新时将结点插入p-next=q2;q1-next=p; Linklist CreateLinklist(Linklist head,int m)/建立一个头指针为head、项数为m的一元多项式int i;Linklist p;p=head=(Linklist)malloc(sizeof(struct Linklistomial);head-next=NULL;for(i=0;icoef,&p-expn);Insert(p,head);/调用Insert函数插入结点return head;void DestroyLinklist(Linklist p)/
7、销毁多项式pLinklist D1,D2;D1=p;while(D1)D2=D1-next;free(D1);D1=D2;void PrintLinklist(Linklist P)/输出一元多项式pLinklist q=P-next;int flag=1; /项数计数器if(!q) /若多项式为空，输出0putchar(O);printf(n);return;while(q)if(q-coef0&flag!=1) putchar(+); /系数大于 0 且不是第一项 if(q-coef!=1&q-coef!=-1) /系数非1或-1的普通情况 printf(%g”,q-coef);if(q-
8、expn=1) putchar(X);else if(q-expn) printf(X”%d”,q-expn);elseif(q-coef=1)if(!q-expn)putchar(1);else if(q-expn=1) putchar(X);elseprintf(X”%d”,q-expn);if(q-coef=-1)if(!q-expn)printf(-1);else if(q-expn=1) printf(-X);elseprintf(-X%dn,q-expn);q=q-next;flag+;printf(n);int Compare(Linklist a,Linklist b)/比较a
9、,b中x的指数的大小if(a&b)if(!b|a-expnb-expn)return 1;else if(!a|a-expnexpn)return -1;elsereturn 0;else if(!a&b)/a多项式已空，但b多项式非空 return -1;else/b多项式已空，但a多项式非空 return 1;Linklist AddLinklist(Linklist pa,Linklist pb)/求解并建立多项式a+b，返回其头指针Linklist qa=pa-next;Linklist qb=pb-next;Linklist headc,hc,qc;hc=(Linklist)mall
10、oc(sizeof(struct Linklistomial);/建 立头结点 hc-next=NULL;headc=hc;while(qa|qb)qc=(Linklist)malloc(sizeof(struct Linklistomial);switch(Compare(qa,qb)case 1:qc-coef=qa-coef;qc-expn=qa-expn;qa=qa-next;break;case 0:qc-coef=qa-coef+qb-coef;qc-expn=qa-expn;qa=qa-next;qb=qb-next;break;case -1:qc-coef=qb-coef;q
11、c-expn=qb-expn;qb=qb-next;break;if(qc-coef!=0)qc-next=hc-next;hc-next=qc;hc=qc;elsefree(qc);/当相加系数为0时，释放该结点return headc;Linklist SubtractionLinklist(Linklist Sa,Linklist Sb)/求解并建立多项式a-b，返回其头指针Linklist Cb=Sb-next;while(Cb)Cb-coef=(-1)*Cb-coef;Cb=Cb-next;return AddLinklist(Sa,Sb);int main()int m,n,a=1
12、;char flag;Linklist pa=0,pb=0,pc;printf(欢迎使用一元多项式加法器nn);/输出菜单printf(*n);printf( *一元多项式简单运算器*n);printf(*n);printf(*A:输入多项式aB:输入多项式b*n);printf( *n);printf(*C:输出多项式aD: 输出多项式 b*n);printf(*n);printf(*E:输出a+bF:输出a-b*n);printf(*n);printf(*G:使用完毕！*n);printf(寸寸寸寸寸寸寸寸寸寸寸寸寸寸寸寸寸寸寸寸寸寸寸寸寸寸寸寸寸寸寸寸寸寸寸寸寸寸寸寸寸寸寸寸寸寸寸寸寸寸寸寸寸寸寸.*n）；while(a)printf(n请选择操作：”)；scanf( %c,&flag);/空格符号一定要注意 switch(flag)caseA:casea:printf(下面进行多项式a的输入：n);printf(请输入a的项数:)； scanf(%d”,&m);pa=CreateLinklist(pa,m);/建立多项式 a break;caseB:caseb:printf(下面进行多项式b的输入：n);printf(请输入b的项数:)； scanf(%d”,&n);pb=CreateLinklist(pb,n);/建立
