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

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

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

3、ruct 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 *inputPoly();/输入多项式poly *psub(poly *p1,poly *p2);/减poly *pdiv(poly *p1,poly *p2);/除poly *inputPoly1();double caculate(double *,poly *p);/计算多项式void s

4、ortPoly(poly *p);/多项式排序void outputPoly(poly*p);/输出多项式void delPoly(poly*p);/清空多项式2物理设计：四、测试结果五、经历体会与缺乏不能连续输入多个多项式函数设计不够简洁算法过于直接简单加注释后修改代码方便六、附录：源代码带注释*include *include struct polynode int coef; int e*p; struct polynode * link;/建立新链表typedef struct polynode poly;poly* Attch(int c,int e,poly *d);/插入链表po

5、ly *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 *,poly *p);/计算void sortPoly(poly *p);/排序void outputPoly(poly*p);/输出多项式void delP

6、oly(poly*p);/除法void Insert(poly *p,poly *h) if(p-coef=0) free(p); else poly *q1,*q2; q1=h;q2=h-link; while(q2&p-e*pe*p) q1=q2; q2=q2-link; /*判断两个指数是否相等*/ if(q2&p-e*p=q2-e*p) q2-coef+=p-coef; free(p); if(!q2-coef) q1-link=q2-link; free(q2); /*相等就加系数*/ else p-link=q2; q1-link=p; /*不等就插在后面*/int main()

7、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); psub1-link=psub(p1,

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

9、c,int e,poly *d) poly *; *=newPoly(); *-coef=c; *-e*p=e; d-link=*; return *;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-e*pb-e*p)/如果a的系数大于b把a先输入 c=Attch(a-coef,a-e*p,c); a=a-link; else if(a-e*pe*p)/小于相反 c=Attch(b-coef,b

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

11、入相反值 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-e*pb-e*p) c=Attch(a-coef,a-e*p,c); a=a-link; else if(a-e*pe*p) c=Attch(b-coef*(-1),b-e*p,c); b=b-link; else if(a-coef-b-coef)0) c=Attch(a-coef-b-coef,a-e*p,c); a=a-link; b=b-link; else a=a-link; b=b-l

12、ink; while(a!=NULL) c=Attch(a-coef,a-e*p,c); a=a-link; while(b!=NULL) c=Attch(b-coef*(-1),b-e*p,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 ae*,aco

13、; a=p1-link; b=p2-link; sum=newPoly(); q=sum; while(a!=NULL) c=newPoly(); d=c; aco=a-coef; ae*=a-e*p; while(b!=NULL) c=Attch(aco*(b-coef),ae*+(b-e*p),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,

15、p1); while(q1-e*p=q2-e*p) temp2-link=newPoly(); temp2-link-coef=(q1-coef)/(q2-coef); temp2-link-e*p=(q1-e*p)-(q2-e*p); Insert(temp2-link,hf); p1=psub(p1,pmul(p2,temp2); q1=p1-link; temp2-link=NULL; pf=psub(temp1,pmul(hf,p2); p2=temp1; printf(商是); outputPoly(hf); printf(余数是); outputPoly(pf);/*输入：多项式的

16、系数和指数存在p1文件中，两个两个读，分别赋给多项式的系数和指数。*/poly *inputPoly() poly *q,*p; p=newPoly(); q=p; FILE *fp; if(fp=fopen(c:p1.t*t,rt)=NULL) printf(nCannot open file strike any key e*it!); getch(); e*it(1); int a,b; while(fscanf(fp,%d %d,&a,&b)!=-1) p-link=newPoly(); p=p-link; p-coef=a; p-e*p=b; p=q; sortPoly(q); q=

17、q-link; p-link=NULL; delPoly(p); fclose(fp); return q;poly *inputPoly1() poly *q,*p; p=newPoly(); q=p; FILE *fp; if(fp=fopen(c:p2.t*t,rt)=NULL) printf(nCannot open file strike any key e*it!); getch(); e*it(1); int a,b; while(fscanf(fp,%d %d,&a,&b)!=-1) p-link=newPoly(); p=p-link; p-coef=a; p-e*p=b;

18、p=q; sortPoly(q); q=q-link; p-link=NULL; delPoly(p); fclose(fp); return q;/*输出：读取系数和指数，按a*b的形式输出*/void outputPoly(poly*p) poly*q; q=p-link; if(q!=NULL) printf(%d*%d ,q-coef,q-e*p); q=q-link; else printf(0); while(q!=NULL) if(q-coefcoef,q-e*p); else printf(+%d*%d ,q-coef,q-e*p); q=q-link; printf(n);/*删除多项式*/void delPoly(poly*p) if(p-link=NULL) free(p); else delPoly(p-link);/*冒泡排序*/void sortPoly(poly *p) poly *a,*b; int i; a=p-link; while(a!