数据结构课程设计一元稀疏多项式计算器报告代码

1、数据结构课程设计设计题目：一元稀疏多项式计算器专业班级学号姓名指导教师2010年12月20H目录一'课程题目1二、需求分析1三、测试数据2四'概要设计2五'调用关系图3六、程序代码3七、测试结果11八、心得体会及总结12数据结构课程设计课程题目一元稀诡多项式计算器二、需求分析1、一元稀疏多项式简单计算器的功能是：1.1 输入并建立多项式；1.2 输出多项式,输出形式为整数序列:n,cl,el,c2,e2,cn,en,其中ii是多项式的项数,ci和ei分别是第i项的系数和指数，序列按指数降序排列；1.3 求多项式a、b的导函数；1.4 计算多项式在x处的值；1.5 多项式

2、和b和加，建立多项认a+b；1.6 多项式a和b相减,建立多项式a-bo2、设计思路：2.1 定义线性表的动态分配顺序存储结构；2.2 建立多项式存储结构，定义指针*优田2.3 利用链表实现队列的构造.每次输入一项的系数和指数，町以输出构造的一元多项式2.4 演示程用以用户和计舜机的对话方式执行，即在计舜机终站上显示“提示信息”Z后，由川户化键盘，输入演示程序小规运的运行命令；报后根据相应的输入数据（滤去输入中的4法字符）建立的多项式以及多项式相加的运行结果在屏幕上显示。多项式显示的格式为:clx*el+c2x*e2+4-cnxnen3、设计思路分析要解决多项式相加，必须要有多项式，所以必须首

3、先建立两个多项式，在这电采用链表的方式存储琏表，所以我将结点结构体定义为序数coef指数expn指针域next运川尾插法建立两条单链表，以巾链表polynp和polynh分别表不两个一元多项式a和b,a+b的求和运算等同于单链表的插入问题（将单链表polynP中的结点插入到单链表polynh中），因此“和多项式”中的结点无须另生成。为了实现处理'设P、q分别指向单链衣polya和polyb的彳前项，比较hq结点的指数项，山此得到下列运算规则：若p->expnvq->expn,则结点p所指的结点应是和多项式”中的“项，令指针P后移。若p->expn=q->expn

4、,则将两个结点中的系数相加，半和不为。时修改结点P的系数。若p->expn>q->expm则结点q所指的结点应是“和多项式中的-项，将结点q插入在结点PZ前，且令指针q在原来的链农上后移。三、测试数据：1、(2x+5x8-31x41)+(7-5x8+llx'9)=(-3.lxll+Ux'9+2x+7);2、(6x-3x+4.4x21.2x9+1.2x9)-(-6x-3十5.4x2-x2十7.8x15)=(-7.8x”15l.2x“9+12x-3-x);3、(l+x+x*2+x*3+x°4+x5)+(_x*3-x4)=(l+x+x*2+x*5);4、(

5、x+x'3)+(-x-x*3)=0;5、(x+x”100)+(x*100+xA200)二(x+2x*100+x*200);6、(x+x”2+x"3)+0=x+x”2+x”3.四、概要设计1、元素类型、结点类型和指针类型：typedefstructPolynomial(floatcoef;系数intexpn;指数structPolynomial*next;*Polyn,Polynomial;2、建立一个头指针为head.项数为m的一兀多项式，建立新结点以接收数据，调用Insert函数插入结点：PolynCreatePolyn(Polynhead,intm)inti;Polynp

6、;p=liead=(Polyn)malloc(sizeof(structPolynomial);head->next=NULL;for(i=0;ivm;i+)(p=(Polyn)malloc(sizeof(structPolynomial);printfC请输入第d项的系数与指数："，i十1);scanf(u%f%d：&p->coef,&p->expn);Insert(p,head);)returnhead:)3、主函数和其他函数：voidmainO(intm,n,a,x;charflag;Polynpa=0,pb=0,pc;)floatValueP

7、olyn(Polynhead,intx)输入x值，计算并返回多项式的值五、调用关系图(图1)六、程序代码：#include<stdio.h>#include<stdlib.h>typedefstructPolynomialfloatcoef;intexpn;定义多项式的项structPolynomial*next;*Polyn,Polynomial;系数voidInsert(Polvnp,Polvn指数h)if(p->coef=0)free(p);elsePolvnql,q2;qi=h；系豹为o的话奢放结占q2=h->next;while(q2&&a

8、mp;p->expn<q2-expn)查找插入位置ql=q2;q2=q2->next;)if(q2&&p->expr)=q2->expn)将指数相同相合并q2->coef+二p->coef;free(p);if(!q2->coef)系数为0的话禅放结点ql->next=q2->next;free(q2);else指数为新时将结点插入p->next=q2;ql->next=p;PolynCreatePoIvn(Polynhead,intm)为heud>项数为m的一元多项式inti;Polynp;pAhe

9、ud31(Pulvn)malloc(sizeof(structPolynomial);head->next=XULL;for(i=0;i<m;i+)建立一个头指针p=(Polyn)malloc(sizeof(structPolynomial);收数据printf(请输入第d项的系数-与指数:,i+1);scanf("%f&p->coef,&p->expn);Insert(p,head);数插入结点建立新结点以接调HJInsert函returnhead;)voidDestroyPolyn(Polynp)Polynql,q2;ql=p>nex

10、t;Q2=ql->nexi;while(ql->next)销毁多项式Pfree(ql);ql=q2；q2=q2->nexl;)voidPrinlPolyn(PolynP)Polynq=P")next;intflag=l;if(!q)项数计数器若多项式为空,putcharO);printf(',nu);return;while(q)输出0if(q->coef>0&&flag!=l)putcharf+，)；系数大于0且不是第一项if(q->coef!=l&&q->coef!=-1)1系数非1或T的普通情况p

11、rintfC*%g*,q->coef);if(q->expn=l)putchar('X')；elseif(q->expn)prititf("X%cT,q->expn);)else(if(q->coef=l)，,if(!q->expn)putchar1');elseif(q->expn=l)pulchar(?X');elseprintfq->expn);)ir(q->coef=-l)(if(!q->expn)printf(uTn);elseif(q->expn=l)prinlf(u-XH)

12、;elseprintfC-X%dH,q->expn):)q=q-)next;flag+;)printf(nnn);)inicompare(PolynatPolynb)iifGiMb)(if(!bl1a->expn>b->expn)return1;elseif(!cdIa->expn<b->expn)returnT;elsereturn0;)elseif(!a&&b)return-1;a多项式已空，但b多项式非空elsereturn1;/b多项式己空，但a多项式非空PolynAddPolyn(Polynpa,Polynpb)缸+b,返回其

13、头指针求解并建立多项式Polynqa=pa->next;Polynqb=pb->next;Polynheadc,he,qc;hc=(Polyn)malloc(sizeof(structPolynomial);建立头结点hc->next=XLLL;headc=hc;while(qaqb)qc=(Polyn)malloc(sizeof(structPolynomial);switch(compare(qa,qb)case1:qc->coef=qa->coef;qc->expn=qa->expn;qa=qa->next;break;case0:qc-&

14、gt;coef=qci->coefAclb->coef;qc->expn=qa->expn;qd二qti->nexl;qb=qb->next;break:case-1:qc->coef=qb->coof;qc->expn=qb->expn;qb二qb->nexl;break;if(qc->coef!=0)qc->next=hc->next;hc->next=qc;he二qc;elsefree(qc)/当相力II系数为0时释放该结点returnheadc:)Polvn SubtractPolyn(Polyn

15、 pa, Polvn pb) 返 回其头指针Polyn h=pb;Polyn p=pb->nexl:Polyn pd;whi le(p)(p->coef*=-l;p=p->next:)pdAzWdPulynCpa, h);for (p=h->next;p;p=p->nexl) p->coef*=-l; return pd;)float ValuePolyn(PoIyn head, int x)返回多项式的值Polyn p;int i, t;float sum 二 0;for (p=head->next;p;p=p->next)t=l；for (i

16、=p->expn;i!=0;)(if(i<0) (t./=x;i+;) elsei* 二 x；i；)sum+=p->coef*t;求解并建立多项式a-b,将pb的系数取反恢复pb的系数输入x值,计算并指数小于0,进行除法指数大于0,进行乘法returnsum;PolynDerivative(Polynhead)求解并建立导函数多项式,并返回其头指针Polynq=head->next>pl,p2,hd;hd=p1=(Po1yn)ma11oc(sizeof(structPolynomial)；建立头结点hdnext=NULL;while(q)(if(q->exp

17、n!=0)该项不是常数项时p2=(Polyn)malloc(sizeof(structPolynoffliul);p2->coel-q->coef*q->expn;p2->expn=q->expn-l;p2->next二pl-next;p»next=p2;pl=p2;连接结点q=q->next;)returnhd;)PolynMultiplyPolyn(Polynpa,Polvnpb)求解并建立多项式a*b,返回其头指针Polynhf,pf:Polynqa=pa->next;Polynqb=pb->next;hf=(Polyn)m

18、alloc(sizeof(struetPolynomial);建立头结点hf->next=NULL;for(;qa;qa=qa->nexl)for(qb=pb->next;qb;qb=qb>next)pf=(Polyn)malloc(sizeof(structPolynomial);pf->coef=qa->coef*qb->coef;pf->expn二qai->expn+qb-)expn;Insert(pf,hf);调用Insert函数以合并指数和同的项)returnhf;)voidmain()intm,n,a,x;charflag;Po

19、lynpa=0,pb=0,pc;printfCnn)；printf*班*nn);printfC*rT);printfC欢迎使川多项式操作程序rT);prinlf(八请输入e的项数:“)；scanf(n%dn,&m);pa=CreatePolyn(pa,m);建立多项式apriritf®输入b的项数：”);scanf(n%dn,&n);pb=(,reatePolvn(pbtn);建立多项式b输出菜单printfCprintf(u*printf(/z*printf(*printf('，*n”)；printff*printfC*n”)；printf(“*printf

20、("*n)printf('z*printf(n*r)；printfC*n)；多项式操作程序*2;*rv);A:输ill多项式aB:输出多项式b*n)*C:输出a的导数D:输出b的导数*n”)；*E:代入x的值计算aF:代入x的傅计算b*lv);*G:输出a+bH:输出u-b*n”)；*I:输出a*bJ：退出程序printfC*n)；prinlfC*门”)；while(a)printfCni#选择操作：)；scanfC%c：&flag);switch(flag)caseA:case'ci:printf(z，n多项式沪);PrintPolyn(pa);break;

21、)case。B':case*:(printf(nn多项式b=H);PrintPolyn(pb);break;case,C：case*c':(pc=Derivative(pa);printfCXn多项式a的导函数为：PrintPolyn(pc);break;)case"D:cased':(pc=Derivative(pb);printfCn多项式b的导函数为：PrintPolyn(pc);break;)case1E':case，:(printf(*输入x的值:x=");scanf&x);printf('zna=%<3fnn,x,ValuePolyn(pa,x);break;)case*F