一元稀疏多项式计算器实验(报告+程序)

1一元稀疏多项式计数器预习报告姓名：刘茂学号222012315220062一、实验要求(1)输入并建立多项式；(2)输出多项式，输出形式为整数序列：n，c1，e1，c2，e2……cn，en，其中n是多项式的项数，ci，ei分别为第i项的系数和指数。序列按指数降序排列；(3)多项式a和b相加，建立多项式a+b；(4)多项式a和b相减，建立多项式a-b。（5）多项式求值；（6）多项式求导；（7）求多项式的乘积。二、测试数据：1、(2x+5x^8-3.1x^11)+(7-5x^8+11x^9)=(-3.1x^11+11x^9+2x+7);2、(6x^-3-x+4.4x^2-1.2x^9+1.2x^9)-(-6x^-3+5.4x^2-x^2+7.8x^15)=(-7.8x^15-1.2x^9+12x^-3-x);3、(1+x+x^2+x^3+x^4+x^5)+(-x^3-x^4)=(1+x+x^2+x^5);4、(x+x^3)+(-x-x^3)=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、互换上述测试数据中的前后两个多项式。三、思路分析用带表头结点的单链表存储多项式。本程序要求输入并建立多项式，能够降幂显示出多项式，实现多项式相加相减的计算问题，输出结果。采用链表的方式存储链表，定义结点结构体。运用尾差法建立两条单链表，以单链表polynp和polynh分别表示两个一元多项式a和b。为实现处理，设p、q分别指向单链表polya和polyb的当前项，比较p、q结点的指数项。①若p-expnq-expn，则结点p所指的结点应是“和多项式”中的一项，2令指针p后移。②若p-expn=q-expn，则将两个结点中的系数相加，当和不为0时修改结点p的系数。③若p-expnq-expn，则结点q所指的结点应是“和多项式”中的一项，将结点q插入在结点p之前，且令指针q在原来的链表上后移。四、实验程序//头文件#includestdio.h#includemalloc.h#includestdlib.h//定义多项式的项typedefstructPolynomial{floatcoef;intexpn;structPolynomial*next;}*Polyn,Polynomial;voidInsert(Polynp,Polynh){if(p-coef==0)free(p);//系数为0的话释放结点else{Polynq1,q2;q1=h;q2=h-next;while(q2&&p-expnq2-expn){//查找插入位置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);}}3else{//指数为新时将结点插入p-next=q2;q1-next=p;}}}PolynCreatePolyn(Polynhead,intm){//建立一个头指针为head、项数为m的一元多项式inti;Polynp;p=head=(Polyn)malloc(sizeof(structPolynomial));head-next=NULL;for(i=0;im;i++){p=(Polyn)malloc(sizeof(structPolynomial));//建立新结点以接收数据printf(请输入第%d项的系数与指数:,i+1);scanf(%f%d,&p-coef,&p-expn);Insert(p,head);//调用Insert函数插入结点}returnhead;}voidDestroyPolyn(Polynp){//销毁多项式pPolynq1,q2;q1=p-next;q2=q1-next;while(q1-next){free(q1);q1=q2;q2=q2-next;}}voidPrintPolyn(PolynP){Polynq=P-next;intflag=1;//项数计数器if(!q){//若多项式为空，输出0putchar('0');printf(\n);4return;}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');elseif(q-expn)printf(X^%d,q-expn);}else{if(q-coef==1){if(!q-expn)putchar('1');elseif(q-expn==1)putchar('X');elseprintf(X^%d,q-expn);}if(q-coef==-1){if(!q-expn)printf(-1);elseif(q-expn==1)printf(-X);elseprintf(-X^%d,q-expn);}}q=q-next;flag++;}printf(\n);}intcompare(Polyna,Polynb){if(a&&b){if(!b||a-expnb-expn)return1;elseif(!a||a-expnb-expn)return-1;elsereturn0;}elseif(!a&&b)return-1;//a多项式已空，但b多项式非空elsereturn1;//b多项式已空，但a多项式非空}PolynAddPolyn(Polynpa,Polynpb){//求解并建立多项式a+b，返回其头指针5Polynqa=pa-next;Polynqb=pb-next;Polynheadc,hc,qc;hc=(Polyn)malloc(sizeof(structPolynomial));//建立头结点hc-next=NULL;headc=hc;while(qa||qb){qc=(Polyn)malloc(sizeof(structPolynomial));switch(compare(qa,qb)){case1:{qc-coef=qa-coef;qc-expn=qa-expn;qa=qa-next;break;}case0:{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时，释放该结点}returnheadc;}6PolynSubtractPolyn(Polynpa,Polynpb){//求解并建立多项式a-b，返回其头指针Polynh=pb;Polynp=pb-next;Polynpd;while(p){//将pb的系数取反p-coef*=-1;p=p-next;}pd=AddPolyn(pa,h);for(p=h-next;p;p=p-next)//恢复pb的系数p-coef*=-1;returnpd;}intValuePolyn(Polynhead,intx){//输入x值，计算并返回多项式的值Polynp;inti;intsum=0,t;for(p=head-next;p;p=p-next){t=1;for(i=p-expn;i!=0;){if(i0){t/=x;i++;}//指数小于0，进行除法else{t*=x;i--;}//指数大于0，进行乘法}sum+=p-coef*t;}returnsum;}PolynDerivative(Polynhead){//求解并建立导函数多项式，并返回其头指针Polynq=head-next,p1,p2,hd;hd=p1=(Polyn)malloc(sizeof(structPolynomial));//建立头结点hd-next=NULL;while(q){if(q-expn!=0){//该项不是常数项时p2=(Polyn)malloc(sizeof(structPolynomial));p2-coef=q-coef*q-expn;7p2-expn=q-expn-1;p2-next=p1-next;//连接结点p1-next=p2;p1=p2;}q=q-next;}returnhd;}PolynMultiplyPolyn(Polynpa,Polynpb){//求解并建立多项式a*b，返回其头指针Polynhf,pf;Polynqa=pa-next;Polynqb=pb-next;hf=(Polyn)malloc(sizeof(structPolynomial));//建立头结点hf-next=NULL;for(;qa;qa=qa-next){for(qb=pb-next;qb;qb=qb-next){pf=(Polyn)malloc(sizeof(structPolynomial));pf-coef=qa-coef*qb-coef;pf-expn=qa-expn+qb-expn;Insert(pf,hf);//调用Insert函数以合并指数相同的项}}returnhf;}voidmain(){intm,n,a,x;charflag;Polynpa=0,pb=0,pc;printf(欢迎使用多项式操作程序\n\n);printf(请输入a的项数:);scanf(%d,&m);pa=CreatePolyn(pa,m);//建立多项式aprintf(请输入b的项数:);scanf(%d,&n);pb=CreatePolyn(pb,n);//建立多项式b8//输出菜单printf(*******************************************************\n);printf(*多项式操作程序*\n);printf(**\n);printf(*A:输出多项式B:输出多项式b*\n);printf(**\n);printf(*C:输出a的导数D:输出b的导数*\n);printf(**\n);printf(*E:代入x的值计算aF:代入x的值计算b*\n);printf(**\n);printf(*G:输出a+bH:输出a-b*\n);printf(**\n);printf(*I:输出a*bJ:退出程序*\n);printf(**\n);printf(*******************************************************\n);while(a){printf(\n请选择操作：);scanf(%c,&flag);//空格符号一定要注意switch(flag){case'A':case'a':{printf(\n多项式a=);PrintPolyn(pa);break;}case'B':case'b':{printf(\n多项式b=);PrintPolyn(pb);break;}case'C':case'c':{pc=Derivative(pa);printf(\n多项式a的导函数为：a'=);PrintPolyn(pc);break;9}case'D':case'd':{pc=Derivative(pb);printf(\n多项式b的导函数为：b'=);PrintPoly