数据结构课程设计__多项式运算

1、#include<stdio.h>#include<stdlib.h>#include"malloc.h"# defineOK1# defineERROR0# defineOVERFLOW-1# defineNULL0typedefintStatus;typedefstructElemTypefloatcoef;/多项式系数intexp;/多项式指数ElemType;/数据类型typedefstructPolynomialElemTypedata;structPolynomial*next;*Polyn,Polynomial;/多项式结构体voidI

2、nsert(Polynp,Polynhead)/*将新的结点插入链表，如果系数为零，则释放该结点；如果指数为新时将结点直接插入；否则查找插入位置，方法：比较该结点指数与首元结点及其他结点的指数，直到该结点指数大于等于链表内某结点的指数，相等则合并这两项；大于则插入到其前驱*/if(p->data.coef=0)free(p);p=NULL;/如果插入项的系数为零时，释放其结点将其删除else(Polynq1,q2;q1=head;q2=head->next;while(q2&&p->data.exp<q2->data.exp)/查找多项式某项的插入

3、位置，使多项式按指数降嘉排列q1=q2;q2=q2->next;if(q2&&p->data.exp=q2->data.exp)/将多项式指数相同相进行合并q2->data.coef+=p->data.coef;free(p);if(!q2->data.coef)/如果多项式的系数为零的话，将其删除即释放期结点q1->next=q2->next;free(q2);else/如果是新建的多项式，指数为新时将结点插入p->next=q2;q1->next=p;StatusCreatePolyn(Polyn&L,in

4、tm)/*建立一个头指针为L,项数为m的一元多项式；先建立一个头指针，再建立新结点来接收数据，然后再调用Insert函数插入结点*/inti；Polynp；L=(Polyn)malloc(sizeof(Polynomial)；if(!L)exit(OVERFLOW);L->next=NULL;for(i=1;i<=m;+i)p=(Polyn)malloc(sizeof(Polynomial);/建立新结点以接收数据if(exit(OVERFLOW);p->next=NULL;printf("请输入第d项的系数与指数中间用空格隔开>:",i);scan

5、f("%f%d",&p->data.coef,&p->data.exp);getchar();Insert(p,L);/调用Insert函数插入新建的结点returnOK;voidDestroyPolyn(Polynp)/销毁多项式pPolynq;while(q=p->next)p->next=q->next;free(q);q=NULL;free(p);p=NULL;)voidPrintPolyn(PolynP)/输出多项式(Polynq=P->next;intflag=1;/项数计数器，用来判别第一项if(!q)/如果

6、多项式为空链表，输出零putchar('0');printf("n");return;)while(q)if(q->data.coef>0&&flag!=1)putchar('+');/多项式系数大于0且不是第一项if(q->data.coef!=1&&q->data.coef!=-1)/多项式系数不是+1和-1的普通情况printf("%g",q->data.coef);if(q->data.exp=1)putchar('X');/多项式

7、系数不是1且指数为1时，输出Xelseif(q->data.exp)printf("XA%d",q->data.exp);/多项式系数不是1且指数不为1,输出X的指数次事)elseif(q->data.coef=1)/多项式系数为1时if(!q->data.exp)putchar('l');/多项式指数为零时，直接输出1elseif(q->data.exp=1)putchar('X');/多项式指数为1时，输出Xelseprintf("XA%d",q->data.exp);)if(q-&

8、gt;data.coef=-1)/多项式系数为-1时(if(!q->data.exp)printf("-1");/多项式指数为零时，直接输出-1elseif(q->data.exp=1)printf("-X");/多项式指数为1时，输出Xelseprintf("-XA%d",q->data.exp);)q=q->next;flag+;)printf("n");)StatusAddPolyn(Polyn&pc,Polynpa,Polynpb)/求解并建立多项式a+b,并用pc带回多项式

9、的和Polynqa=pa->next;Polynqb=pb->next;Polynhc,qc;intj;pc=(Polyn)malloc(sizeof(Polynomial);/建立头结点if(!pc)exit(OVERFLOW);pc->next=NULL;hc=pc;while(qa|qb)/(while(qa&&qb)退出循环可以用hc=qa?qa:qb;),使用时对后面的减法造成影响(if(qa&&qb)(if(qa->data.exp>qb->data.exp)j=1;/a多项式某项指数大于b多项式某项指数elsei

10、f(qa->data.exp<qb->data.exp)j=-1;/b多项式某项指数大于a多项式某项指数elsej=0;/a多项式某项指数等于b多项式某项指数elseif(!qa&&qb)j=-1;/a多项式已空，但b多项式非空elsej=1;/b多项式已空，但a多项式非空qc=(Polyn)malloc(sizeof(Polynomial);/建立新结点来存放两多项式相加和的某一项if(!qc)exit(OVERFLOW);qc->next=NULL;switch(j)case1:/a多项式某项指数大于b多项式指数，则把其存入qc内qc->dat

11、a.coef=qa->data.coef;qc->data.exp=qa->data.exp;qa=qa->next;break;case0:/两多项式两项指数相等，则把其和存入qc内qc->data.coef=qa->data.coef+qb->data.coef;qc->data.exp=qa->data.exp;qa=qa->next;qb=qb->next;break;)case-1:/b多项式某项指数大于a多项式指数，则把其存入qc内(qc->data.coef=qb->data.coef;qc->d

12、ata.exp=qb->data.exp;qb=qb->next;break;)if(qc->data.coef!=0)/产生的和项式插入链表pc内(hc->next=qc;hc=qc;)elsefree(qc);/当相加系数为零时，释放该结点)/hc->next=qa?qa:qb;/如果qa或qb空时，把另一个多项式剩余的项连接到hcreturnOK;)StatusSubtractPolyn(Polyn&pd,Polynpa,Polynpb)/求解并建立多项式a-b,用pd带回多项式的差Polynh=pb;Polynp=pb->next;while

13、(p)/将pb的系数取反，调用加法的函数实现减法p->data.coef*=-1;p=p->next;)AddPolyn(pd,pa,h);for(p=h->next;p;p=p->next)/为保证原多项式不变，恢复pb的系数p->data.coef*=-1;returnOK;)floatValuePolyn(Polynp,floatx)/输入x值，计算并返回多项式的值Polynq=p->next;/指针q用来遍历pinti;floatt;floatsum=0;while(q)t=1;i=q->data.exp;while(i)/来计算XAi的值if

14、(i<0)t/=x;i+;/如果多项式指数小于0时，对X取倒数进行除法elset*=x;i-;/如果指数大于0,则进行乘法sum+=q->data.coef*t;q=q->next;returnsum;StatusDerivativePolyn(Polyn&hd,Polynp)/求解多项式的导函数，并用hd带回求导后的结果Polynq=p->next,p1,p2;hd=p1=(Polyn)malloc(sizeof(Polynomial);/建立头结点if(!hd)exit(OVERFLOW);hd->next=NULL;while(q)if(q->

15、data.exp!=0)/如果多项式该项不是常数项时，常数的话就不用参与下面的计算p2=(Polyn)malloc(sizeof(Polynomial);/开辟新的结点用来存放求导后的该项if(!p2)exit(OVERFLOW);p2->next=NULL;p2->data.coef=q->data.coef*q->data.exp;/求导后该项的系数=原项系数*原项指数p2->data.exp=q->data.exp-1;/求导后该项的指数=原项指数-1p1->next=p2;/将求导后的该项插入新链表p1=p2;q=q->next;retu

16、rnOK;StatusMultiplyPolyn(Polyn&hf,Polynpa,Polynpb)/求解多项式a*b,并用hf带回乘积结果Polynpf;Polynqa=pa->next;/qa和qb用来遍历多项式pa和pbPolynqb=pb->next;hf=(Polyn)malloc(sizeof(Polynomial);/建立头结点if(!hf)exit(OVERFLOW);hf->next=NULL;while(qa)/利用两个循环让多项式pa和pb的任意两项相乘for(qb=pb->next;qb;qb=qb->next)pf=(Polyn)

17、malloc(sizeof(Polynomial);if(!pf)exit(OVERFLOW);pf->next=NULL;pf->data.coef=qa->data.coef*qb->data.coef;/系数相乘pf->data.exp=qa->data.exp+qb->data.exp;/指数相乘Insert(pf,hf);/调用Insert函数以合并指数相同的项，并按降嘉排序qa=qa->next;returnOK;StatusIndefinite_integralPolyn(Polyn&hd,Polynp)/求解多项式的不定积

18、分，并用hd带回求导后的结果Polynq=p->next,p1,p2;hd=p1=(Polyn)malloc(sizeof(Polynomial);/建立头结点if(!hd)exit(OVERFLOW);hd->next=NULL;while(q)(if(q->data.exp=-1)/如果含有-1次方的多项式，积分会涉及到ln(x),不好运算及存储，则直接默认积分结果为零(printf("n本程序不能对含有-1次方的多项式积分！n若还有-1次方，则积分结果默认为零！n");DestroyPolyn(hd);hd=(Polyn)malloc(sizeof(

19、Polynomial);/重新建立头结点，方便输出if(!hd)exit(OVERFLOW);hd->next=NULL;break;p2=(Polyn)malloc(sizeof(Polynomial);/建立新的结点来存放积分后某项的结果if(!p2)exit(OVERFLOW);p2->next=NULL;p2->data.coef=q->data.coef/(q->data.exp+1);/积分后该项的系数=原项的系数:(原项的指数+1)p2->data.exp=q->data.exp+1;/积分后该项的指数=原项指数+1p1->next

20、=p2;/积分后该项的结果插入链表p1=p2;q=q->next;returnOK;doubleDefinite_integralPolyn(Polynp,floata,floatb)/用e带回求定积分的结果求解多项式p的定积分，并doublee=0;Polynq;if(!p)exit(OVERFLOW);if(!p->next)return0;Indefinite_integralPolyn(q,p);/调用不定积分函数Indefinite_integralPolyn(),先计算多项式的不定积分e=ValuePolyn(q,b)-ValuePolyn(q,a);/调用求值函数Va

21、luePolyn,计算定积分的值returne;voidmain()intm,n,c=1;floatx,a,b;inttemp;doubleresult_a=0,result_b=0;Polynpa=0,pb=0,pc;printf(*printf("*n");printf("*数据结构课程设计*n");printf("*n");printf("*、-n.printf("*姓名：XX*n");printf("*班级：2010级2班*n");printf("*学号：XXXXXX

22、X*n");printf("*专业：电子信息科学与技术*n");printf(题目：一元多项式运算器*n");printf(*n");printf（"首先创建两个一元多项式，即多项式a和b:n"）;printf("请输入a的项数:");scanf("%d",&m);/getchar();CreatePolyn(pa,m);/建立多项式aprintf("n多项式a=");PrintPolyn(pa);printf("n");printf(&

23、quot;请输入b的项数:");scanf("%d",&n);/getchar();CreatePolyn(pb,n);/建立多项式bprintf("n多项式b=");PrintPolyn(pb);printf("n");输出菜单printf("*多项式操作菜单*n");printf("*n");printf("*1:显小两个一兀多项式*n");printf("*2:求两个多项式的和即（a+b)*n");printf("*3:求

24、两个多项式的差即（a-b)*n");printf("*4:求两个多项式的积即（a*b)*n");printf("*5:带入X求多项式的值*n");printf(*printf（"*6:对多项式求导计算*n"）;printf（"*7:对多项式不定定积分计算*n"）;printf（"*8:对多项式定积分计算*n"）;printf（"*9:销毁所创建的一元多项式*n"）;printf（"*10:重新创建两个一元多项式*n"）;printf（"

25、*11:退出程序（并且销毁了多项式）*n"）;printf(*while(c)printf（"n请选择操作："）;scanf("%d”,&temp);getchar();switch(temp)(case 1:(printf("n多项式a=");PrintPolyn(pa);printf("n多项式b=");PrintPolyn(pb);break;case 2:(AddPolyn(pc,pa,pb);printf("na+b=");PrintPolyn(pc);break;case 3

26、:(SubtractPolyn(pc,pa,pb);printf("na-b=");PrintPolyn(pc);break;)case 4:(MultiplyPolyn(pc,pa,pb);printf("na*b=");PrintPolyn(pc);break;)case 5:(printf("对于多项式a,输入x求多项式的值！n");printf("输入x的值：x=");scanf("%f",&x);printf("nx=%.3f时，a=%.3fn",x,Val

27、uePolyn(pa,x);printf("对于多项式b,输入x求多项式的值!n");printf("输入x的值：x=");scanf("%f",&x);printf("nx=%.3f时，b=%.3fn",x,ValuePolyn(pb,x);break;case 6:(DerivativePolyn(pc,pa);printf("n多项式a的导函数为：a'=");PrintPolyn(pc);DerivativePolyn(pc,pb);printf("n多项式b的导

28、函数为：b'=");PrintPolyn(pc);break;)case 7:(Indefinite_integralPolyn(pc,pa);printf("n多项式a的不定积分为：fa=");PrintPolyn(pc);Indefinite_integralPolyn(pc,pb);printf("n多项式b的不定积分为：bb=");PrintPolyn(pc);break;)case 8:(printf("请输入定积分的上下限：n");printf("请输入定积分的下限a=:");scanf("%f&quo