数据结构课程设计-一元多项式计算器

.实习 1、一元稀疏多项式计算器一、需求分析1. 问题描述设计一个一元稀疏多项式简单计算器。2. 基本要求一元稀疏多项式简单计算器的基本功能是：(1)输入并建立多项式。(2)输出多项式，输出形式为整数序列：n, c1, e1, c 2, e2, ,cn, en ，其中 n 是多项式的项数， ci,ei 分别是第i 项的系数和指数，序列按指数降序排列。(3)多项式 a 和 b 想加，建立多项式a+b 。(4)多项式 a 和 b 想减，建立多项式a-b 。3. 测试数据(1) (2x+5x 8 -3.1x11)+(7 -5x8+11x9)=( -3.1x11+11x9+2x+7)(2) (6x -3-x+4.4x 2-1.2x 9)-(-6x-3+5.4x 2-x2+7.8x15)=(-7.8x 15-1.2x 9+12x -3-x)(3) (1+x+x 2 +x3+x 4+x5 )+(-x3-x4)=(1+x+x 2+x 5)(4) (x+x 3)+(-x-x3)=0(5) (x+x 100)+(x 100+x 200)=(x+2x 100+x 200)(6) (x+x 2+x 3)+0=(x+x 2+x 3)(7) 互换测试数据的前后两个多项式。4. 实现提示用带表头结点的单链表存储多项式。二、概要设计为实现上述程序功能，应用带头结点的单链表存储多项式。为此需要一个抽象数据类型：一元多项式。1.抽象数据类型一元多项式定义为：ATD Ploynomial数据对象： D=ai|ai Termset, i=1,2,3 ，m,m 0 Termset 中的每个元素包含一个表示系数的实数和表示指数的整数数据关系： R1=ai -1,ai D,且 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,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 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 -next;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)/ 销毁多项式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(0);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 -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%d,q -expn);q=q-next;flag+;printf(n);int Compare(Linklist a,Linklist b)./ 比较 a,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)malloc(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;qc-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;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);/ 建立多项式abreak;caseB:caseb:printf( 下面进行多项式b 的输入： n);printf( 请输入 b 的项数 :);scanf(%d,&n);pb=CreateLinklist(pb,n);/ 建立多项式bbreak;caseC:casec:printf(n多项式 a=);PrintLinklist(pa);break;caseD:cased:printf(n多项式 b=);PrintLinklist(pb);break;caseE:.casee:pc=AddLinklist(pa,pb);printf(na+b=);PrintLinklist(pc);break;caseF:casef:pc=SubtractionLinklist(pa,pb);printf(na-b=);PrintLinklist(pc);break;caseG:caseg:DestroyLinklist(pa);DestroyLinklist(pb);a=0;printf(n欢迎下次使用！n);break;default:printf(n您的选择错误，请重新选择!n);return 0;四、调试分析编译环境为CodeBlocks。.