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

1、实习1、一元稀疏多项式计算器1. 需求分析1问题描述设计一个一元稀疏多项式简单计算器。2. 基本要求一元稀疏多项式简单计算器的基本功能是：(1) 输入并建立多项式。(2) 输出多项式,输出形式为整数序列：n, cx/ eiz c2t e2/ ,cn,en,其中n是多项式的项数，ce分别是第i项的系数和指数，序列按指数降序排列。多项式a和b想加，建立多项式a+b。(4) 多项式a和b想减，建立多项式a-b 03 测试数据(1) (2x+5x8-3.1xn)+(7-5 x8+11x9)=(-3.1x11+11 x9+2x+7)(2) (6x'3-x+4.4x2-1.2x9)-(-6x

2、9;3+5.4x2-x2 +7.8x15)=(-7.8x15-1.2x9+12x'3-x)(1 +x+x2+x3+x 4+x5)+(-x3 -x4)=(l+x+x2+x5)(4 ) (x+x3)+(-x-x3)=o(5) (x+x100)+(x100+x 200)=(x+2x 叫x2°°)(6) (x+x2 +x3)+o=(x+x2+x3)(7 )互换测试数据的前后两个多项式。4 实现提示用带表头结点的单链表存储多项式。二、概要设计为实现上述程序功能，应用带头结点的单链表存储多项式。为此需要一个抽象数据类 型：一元多项式。2.抽象数据类型一元多项式定义为：atd p

3、loy nomial数据对象：d=ai |atermset,i=l,2,3 , m,mmo te rmset中的每个元素包含一个表示系数的实数和表示指数的整数数据关系：rl=i-l,aied,且ail中的指数i中的指数的值，曰23 n基本操作：lnsert(p,h)初始条件：h已存在。 操作结果：插入p项。creatednklist(head, m)操作结果：建立一个头指针为head、项数为m的一元多项式。destroylinklist( p)初始条件：一元多项式p已存在。 操作结果：销毁一元多项式p。printlinklist( p)初始条件：一元多项式p已存在。操作结果：输出一元多项式p。

4、compare(a,b)初始条件：项a,b己存在。操作结果：比较a,b中x的指数的大小。addlinklist(pa,pb)初始条件：一元多项式pa 7pb已存在。操作结果：完成一元多项式pa,pb的相加运算。subtractio nlinklist(sa,sb)初始条件：一元多项式sa,sb b存在。操作结果：完成一元多项式sa ,sb的相减运算。 atd ployn omial三、详细设计(源代码)(使用c语言)#in clude<stdio.h>#include<malloc.h>#define maxlen 10#define large 999typedef

5、struct linklistomialfloat coef;int expn;struct linklistomial ext;linklisto mial/link list;/结点类型,指针类型void lnsert(linklist p,linklist h)/ h已存在插入p项if(p->coef=0)fre e(p);/系数为0的话释放结点elselinklist ql,q2;ql=h;q2=h->n ext;while(q2&&p->exp nvq2 >exp n)查找插入位置ql=q2;q2=q2 >n ext;if(q2&

6、&p->exp n=q2->exp n)将指数相同相合并q2->coef+=p->coef;free(p);if(!q2->coef)/系数为0的话释放结点ql->next=q2->n ext;free(q2);else /指数为新吋将结点插入p->n ext=q2;ql->next=p; linklist createlinklist(linklist head,int m)/建立一个头指针为head、项数为m的一元多项式int i;linklist p;p=head=(linklist)malloc(sizeof(struct

7、linklistomial);head->next=null;for(i=0;i<m;i+)p=(linklist)m alloc(size of(struct linklistom ial);/建立新结点以接收数据 prin tf(”请输入第d项的系数与指数:uj+1);scanf("%f %d",&p->coef,&p->expn);insert (p,head);调用 inse rt xl数插入结点return head;void destroylinklist(linklist p)/销毁多项式plinklist d1,d2;

8、dl=p；while(dl)d2=dl->next;free(dl);d1=d2;void printlinklist(linklist p)/输出一元多项式plinklist q=p->next;int fla g=l; /项数计数器if(!q)若多项式为空，输出0putcharco1);printf("n");return;while(q)if (q->coef>0 putchar('+'); 系数大于 0 且不是第一项 if(q->coef!=l&&q->coef!=-l)/系数非1或j的普通情况pr

9、intf (吆g 笃 q>coef);讦(q->expputchar('x');else if(q->expn) printf("xa%d",q->expn);else讦(q->coef=l)if(!q->exp n)putchar('l');else if(q->expn=l)putcharfx*);elseprintf("xa%d,q->expn);讦(q->coef=-l)讦(!q->expn)printfc'-l");else if(q>ex

10、pn=l)printfc'-x");elseprintf("-xa%d"/q->expn);q 二q>ne xt;flag+;printfcxn"); int compare(linklist a丄inklist b)/比较+ x的指数的大小if(a&&b)if(!b| |a->expn>b->expn)return 1;else if(!a| |a->expnvboexpn)return -1;elsereturn 0;else if(哆项式已空,但b多项式非空return -1;else/b

11、多项式已空，但a多项式非空return 1;linklist addlinklist(linklist pa丄inklist pb)求解并建立多项式a+b,返回其头指针linklist qa=pa->next;linklist qb=pb->next;linklist headc,hc,qc;hc=(l inklist)ma lloc(sizeo f(struct l inklistomi al);建立头结点 hc->next=null;headc=hc;while(qa| |qb)qc=(linklist)malloc(sizeof(struct linklistomial

12、);switch(compare(qa,qb)case 1:qc->coef=qa->coef;qc->expn=qa > exp n;qa=qa->n ext;break;case 0:qc->coef=qa->coef+qb->coef;qc->exp n 二 qa->exp n;qa=qa->n ext;qb=qb->n ext;break;case -1:qc->coef=qb->coef; qc->exp n 二 qb->expn; qb=qb->n ext;break;if(qc-

13、>coef!=0)qc>n ext=hc->n ext;hcn ext=qc;hc=qc;elsefree (qc);当相加系数为0时,释放该结点 return headc;linklist subtractionlinklist(linklist sa丄inklist sb) 求解并建立多项式ib,返冋其头指针linklist cb=sb->next;while(cb)cb->coef=(-l)*cb->coef;cb=cb->n ext;return addlinklist(sa,sb); int main()int m,n,a=l;char fl

14、ag;linklist pa=o,pb=o,pc;printtf"欢迎使用一元多项式加法器nn");/输出菜单printf(h* * * * * * *n n) printf（n* 一元多项式简单运算器*n“）;printf(h*nn);pr intf（”*a:输入多项式a b:输入多项式b*n "）;printf(h prin tf(h*nn）;c :输出多项式a d:输出多项式b *n"）；printf(n*nh);printf ("*e:输出 a+b f:输出 a-b *n");printf(n*nm);printf("

15、;g:使用完毕! *nh);printf(h* *nwhile(a)printf("n请选择操作：”)；scan lag);/空格符号一定要注意 switch(flag)case'a': case'a':printff'下面进行多项式a的输入：nh); prin tf(“请输入a的项数:”)；scanf("%ct,&m);pa=createl inklistfpa ,m);建立多项式 a break;case'b':case'b':printff"下面进行多项式b的输入:nu); pr

16、in tf(“请输入b的项数:”)；scanf(“d”,&n);pb=createl inklist(pb ,n);建立多项式 b break;case'c':case'c':printf("n 多项式a=“)；printlinklist(pa);break;case'd': case'd': printf("n 多项式 b=");printlinklist(pb); break;case'e':case©:pc=addli nklist(pa，pb); printf("n a+b="); printlinklist(pc);break;case'f':case'f'