链表线性结构多项式的加减乘除

1、哈尔滨工业大学计算机科学与技术学院实验报告课程名称：数据结构与算法课程类型：必修实验项目：线性结构及其应用实验题目：多项式的加减乘除和特定值带入实验日期：2017/11/5班级：1603001学号：1160300121姓名：安宏宇设计成绩报告成绩指导老师张岩一、实验目的 设计线性表的链式存储结构，并实现一元多项式的代数运算。二、实验要求及实验环境（1）实验要求： 以链表存储一元多项式， 在此基础上完成对多项式的代数操作。1. 能够输入多项式（可以按各项的任意输入顺序， 建立按指数降幂排列的多项式） 和输出多项式（按指数降幂排列） , 以文件形式输入和输出，并显示。2. 能够计算多项式在某一点

2、x=x0 的值，其中 x0 是一个浮点型常量，返回结果 为浮点数。3. 能够给出计算两个多项式加法、 减法、 乘法和除法运算的结果多项式， 除法运 算的结果包括商多项式和余数多项式。4. 要求尽量减少乘法和除法运算中间结果的空间占用和结点频繁的分配与回收 操作。（提示：利用循环链表结构和可用空间表的思想，把循环链表表示的多项 式返还给可用空间表，从而解决上述问题） 。（ 2）实验环境： windows 下的 CB;三、设计思想 （本程序中的用到的所有数据类型的定义， 主程序的流程图及各程 序模块之间的调用关系）1逻辑设计 :struct polynodeint coef;int exp;str

3、uct polynode * link;/ 建立链表typedef struct polynode poly;poly* Attch（int c,int e,poly *d）;/多项式插入poly * newPoly();新链表poly *padd(poly *p1,poly *p2);多项式加法poly *pmul(poly *p1,poly *p2);乘法poly * in putPoly();输入多项式poly *psub(poly *p1,poly *p2);减poly *pdiv(poly *p1,poly *p2);除poly *in putPoly1();double cacul

4、ate(double x,poly *p);计算多项式void sortPoly(poly *p);多项式排序void outputPoly(poly*p);输出多项式void delPoly(poly*p);清空多项式2物理设计四、测试结果不能连续输入多个多项式函数设计不够简洁算法过于直接简单加注释后修改代码方便六、附录：源代码(带注释)#i nclude #i nclude struct polynodeint coef;int exp;struct polynode * link;/建立新链表typedef struct polynode poly;poly* Attch( in t c

5、,i nt e,poly *d);/插入链表poly * newPoly(); 建立新链表poly *padd(poly *p1,poly *p2);/加法poly *pmul(poly *p1,poly *p2);/乘法poly *inputPoly();/ 输入多项式poly *psub(poly *p1,poly *p2);/减法poly *pdiv(poly *p1,poly *p2);/除法poly *inputPoly1();/ 输入 double caculate(double x,poly *p);/ 计算 void sortPoly(poly *p);/排序void outp

6、utPoly(poly*p);/输出多项式void delPoly(poly*p);/ 除法 void Insert(poly *p,poly *h) if(p-coef=0)free(p);elsepoly *q1,*q2; q1=h;q2=h-link; while(q2&p-expexp) q1=q2;q2=q2-link;/* 判断两个指数是否相等 */ if(q2&p-exp=q2-exp) q2-coef+=p-coef;free(p); if(!q2-coef) q1-link=q2-link;free(q2);/* 相等就加系数 */elsep-link=q2;q1-link=

7、p;/* 不等就插在后面 */int main()poly *p1,*p2,*padd1,*psub1,*pmul1; p1=newPoly();printf( 第一个多项式 n);p1-link=inputPoly();outputPoly(p1);p2=newPoly();printf( 第二个多项式 n);p2-link=inputPoly1();outputPoly(p2);padd1=newPoly();pmul1=newPoly();psub1=newPoly();padd1-link=padd(p1,p2);printf(paddn);outputPoly(padd1);psub

8、1-link=psub(p1,p2);printf(psubn);outputPoly(psub1); pmul1-link=pmul(p1,p2); printf(pmuln);outputPoly(pmul1);printf(输入 x 的值！ );int x;scanf(%d,&x);x=caculate(x,p1);printf(%dn,x);pdiv(p1,p2);return 0;poly *newPoly()poly *x;x=(poly*)malloc(sizeof(poly);x-link=NULL;x-coef=0;x-exp=0;return x;poly* Attch(i

9、nt c,int e,poly *d)poly *x;x=newPoly();x-coef=c;x-exp=e;d-link=x;return x;poly *padd(poly *p1,poly *p2)poly *a, *b,*c,*d,*p;c=newPoly();d=c;p=c;a=p1-link;b=p2-link;while(a!=NULL&b!=NULL)if(a-expb-exp)/ 如果 a 的系数大于 b 把 a 先输入c=Attch(a-coef,a-exp,c);a=a-link;else if(a-expexp)/ 小于相反c=Attch(b-coef,b-exp,c

10、);b=b-link;else/ 相等c=Attch(b-coef+a-coef,a-exp,c);a=a-link;b=b-link;/*a b 比较完成开始遍历剩下的未插入的 */while(a!=NULL)c=Attch(a-coef,a-exp,c);a=a-link;while(b!=NULL)c=Attch(b-coef,b-exp,c);b=b-link;c-link=NULL; d=d-link;p-link=NULL;delPoly(p);return d;b 的系数得输入相反值poly *psub(poly*p1,poly*p2)/ 加和减思路相同， poly *a, *b

11、,*c,*d,*p;c=newPoly();d=c;p=c;a=p1-link;b=p2-link;while(a!=NULL&b!=NULL)if(a-expb-exp) c=Attch(a-coef,a-exp,c); a=a-link;else if(a-expexp) c=Attch(b-coef*(-1),b-exp,c); b=b-link; elseif(a-coef-b-coef)0) c=Attch(a-coef-b-coef,a-exp,c); a=a-link;b=b-link;elsea=a-link;b=b-link;while(a!=NULL)c=Attch(a-c

12、oef,a-exp,c); a=a-link;while(b!=NULL)c=Attch(b-coef*(-1),b-exp,c); b=b-link;c-link=NULL;d=d-link;p-link=NULL;delPoly(p);return d;/* 乘法，先用第一个链表的第一个数据乘以第二个链表里的所有值，储存在新的 链表中，之后遍历一中所有的值，最后把这些多项式加在一起。*/poly *pmul(poly*p1,poly*p2)/ 乘法poly*a,*b,*c,*d,*q,*sum;int aex,aco;a=p1-link;b=p2-link; sum=newPoly();q

13、=sum;while(a!=NULL)c=newPoly();d=c;aco=a-coef; aex=a-exp;while(b!=NULL) c=Attch(aco*(b-coef),aex+(b-exp),c); b=b-link;b=p2-link;sum-link=padd(d,sum);a=a-link;delPoly(d);sum=sum-link;q-link=NULL;delPoly(q);sortPoly(sum);return sum;/*除法：先用链表一第一个的系数除以第二个链表的第一个系数，得到的值乘以 被除多项式，再用第一个多项式减。最后得到一个最大系数比被除数小的多

14、项 式。*/poly *pdiv(poly*p1,poly*p2)poly *hf,*pf,*temp1,*temp2;poly *q1;q1=p1-link;poly *q2;q2=p2-link;hf=newPoly();hf-link=NULL;pf=newPoly();pf-link=NULL;temp1=newPoly();temp1-link=NULL;temp2=newPoly();temp2-link=NULL;temp1=padd(temp1,p1);while(q1-exp=q2-exp)temp2-link=newPoly();temp2-link-coef=(q1-co

15、ef)/(q2-coef);temp2-li nk-exp=(q1-exp)-(q2-exp);In sert(temp2-li nk,hf);p1=psub(p1,pmul(p2,temp2);q1=p1-li nk;temp2-li nk=NULL;pf=psub(temp1,pmul(hf,p2);p2=temp1;prin tf(商是);outputPoly(hf);prin tf(余数是);outputPoly(pf);/*输入：多项式的系数和指数存在p1文件中，两个两个读，分别赋给多项式的系数和指数。*/poly *in putPoly()poly *q,*p;p=n ewPoly

16、();q=p;FILE *fp;if(fp=fope n(c:p1.txt,rt)=NULL)prin tf(nCannot ope n file strike any key exit!);getch();exit(1);int a,b;while(fscanf(fp,%d %d,&a,&b)!=-1) p-link=newPoly(); p=p-link;p-coef=a;p-exp=b;p=q;sortPoly(q);q=q-link; p-link=NULL;delPoly(p);fclose(fp);return q;poly *inputPoly1()poly *q,*p; p=n

17、ewPoly();q=p;FILE *fp;if(fp=fopen(c:p2.txt,rt)=NULL)printf(nCannot open file strike any key exit!); getch();exit(1); int a,b;while(fscanf(fp,%d %d,&a,&b)!=-1) p-link=newPoly(); p=p-link;p-coef=a; p-exp=b;p=q;sortPoly(q);q=q-link; p-link=NULL;delPoly(p);fclose(fp);return q;/*输出：读取系数和指数，按 a*xAb的形式输出*/

18、void outputPoly(poly*p)poly*q;q=p-link;if(q!=NULL)printf(%dxA%d ,q-coef,q-exp); q=q-link;elseprintf(0);while(q!=NULL)if(q-coefcoef,q-exp); elseprin tf(+%dxA%d ,q-coef,q-exp); q=q-link;printf(n);/* 删除多项式 */void delPoly(poly*p)if(p-link=NULL) free(p);elsedelPoly(p-link);/* 冒泡排序 */void sortPoly(poly *p)poly *a,*b;int i;a=p-link