《链表线性结构(多项式地加减乘除).pdf》由会员分享，可在线阅读，更多相关《链表线性结构(多项式地加减乘除).pdf（18页珍藏版）》请在三一文库上搜索。
1、实用标准文案 精彩文档 哈尔滨工业大学计算机科学与技术学院 实验报告 课程名称：数据结构与算法 课程类型：必修 实验项目：线性结构及其应用 实验题目：多项式的加减乘除和特定值带入 实验日期： 2017/11/5 班级：1603001 学号：1160300121 姓名：安宏宇 设计成绩报告成绩指导老师 张岩 实用标准文案 精彩文档 一、实验目的 设计线性表的链式存储结构，并实现一元多项式的代数运算。 二、实验要求及实验环境 （1）实验要求： 以链表存储一元多项式， 在此基础上完成对多项式的代数操作。 1. 能够输入多项式（可以按各项的任意输入顺序， 建立按指数降幂排列的多项式） 和输出多项式（按
2、指数降幂排列）, 以文件形式输入和输出，并显示。 2. 能够计算多项式在某一点 x=x0 的值，其中 x0 是一个浮点型常量， 返回结果 为 浮点数。 3. 能够给出计算两个多项式加法、减法、乘法和除法运算的结果多项式，除法运 算的结果包括商多项式和余数多项式。 4. 要求尽量减少乘法和除法运算中间结果的空间占用和结点频繁的分配与回收 操作。 （提示：利用循环链表结构和可用空间表的思想，把循环链表表示的多项 式返还给可用空间表，从而解决上述问题）。 （2）实验环境： windows下的 CB; 三、设计思想（本程序中的用到的所有数据类型的定义，主程序的流程图及各程 序模块之间的调用关系） 1逻
3、辑设计 : struct polynode int coef; int exp; struct 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 *inputPoly();/输入多项式 poly *psub(poly *p1,poly *p2)
4、;/减 poly *pdiv(poly *p1,poly *p2);/除 poly *inputPoly1(); double caculate(double x,poly *p);/计算多项式 void sortPoly(poly *p);/多项式排序 void outputPoly(poly*p);/输出多项式 void delPoly(poly*p);/清空多项式 2物理设计： 四、测试结果 实用标准文案 精彩文档 五、经验体会与不足 不能连续输入多个多项式 函数设计不够简洁 算法过于直接简单 加注释后修改代码方便 六、附录：源代码（带注释） #include #include stru
5、ct polynode int coef; int exp; struct 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 *inputPoly();/输入多项式 poly *psub(poly *p1,poly *p2);/减法 poly *
6、pdiv(poly *p1,poly *p2);/除法 poly *inputPoly1();/输入 double caculate(double x,poly *p);/计算 void sortPoly(poly *p);/排序 void outputPoly(poly*p);/输出多项式 void delPoly(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 q2=q2-link; /*判断两个指数是否相等 */ if(q2
7、 free(p); if(!q2-coef) q1-link=q2-link; free(q2); /*相等就加系数 */ else p-link=q2; q1-link=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(p
8、2); padd1=newPoly(); pmul1=newPoly(); psub1=newPoly(); padd1-link=padd(p1,p2); printf(“paddn“); outputPoly(padd1); psub1-link=psub(p1,p2); printf(“psubn“); outputPoly(psub1); pmul1-link=pmul(p1,p2); printf(“pmuln“); outputPoly(pmul1); printf(“输入 x 的值！ “); int x; 实用标准文案 精彩文档 scanf(“%d“, x=caculate(x,
9、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(int 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();
10、 d=c; 实用标准文案 精彩文档 p=c; a=p1-link; b=p2-link; while(a!=NULL a=a-link; else if(a-expexp)/小于相反 c=Attch(b-coef,b-exp,c); 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-coe
11、f,b-exp,c); b=b-link; c-link=NULL; d=d-link; p-link=NULL; delPoly(p); return d; poly *psub(poly*p1,poly*p2)/加和减思路相同， b 的系数得输入相反值 poly *a, *b,*c,*d,*p; c=newPoly(); d=c; p=c; a=p1-link; b=p2-link; while(a!=NULL a=a-link; else if(a-expexp) c=Attch(b-coef*(-1),b-exp,c); b=b-link; 实用标准文案 精彩文档 else if(a-
12、coef-b-coef)0) c=Attch(a-coef-b-coef,a-exp,c); a=a-link; b=b-link; else a=a-link; b=b-link; while(a!=NULL) c=Attch(a-coef,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; 实用标准文案 精彩文档 /* 乘法，先用第一个链表的第一个数据乘以第二个链表里的所有值，储
13、存在新的 链表中，之后遍历一中所有的值，最后把这些多项式加在一起。 */ 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=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);
14、 a=a-link; delPoly(d); 实用标准文案 精彩文档 sum=sum-link; q-link=NULL; delPoly(q); sortPoly(sum); return sum; /* 除法：先用链表一第一个的系数除以第二个链表的第一个系数，得到的值乘以 被除多项式，再用第一个多项式减。最后得到一个最大系数比被除数小的多项 式。 */ poly *pdiv(poly*p1,poly*p2) poly *hf,*pf,*temp1,*temp2; poly *q1; q1=p1-link; poly *q2; q2=p2-link; hf=newPoly(); hf-lin
15、k=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-coef)/(q2-coef); 实用标准文案 精彩文档 temp2-link-exp=(q1-exp)-(q2-exp); Insert(temp2-link,hf); p1=psub(p1,pmul(p2,temp2)
16、; q1=p1-link; temp2-link=NULL; pf=psub(temp1,pmul(hf,p2); p2=temp1; printf(“); outputPoly(hf); printf(“); outputPoly(pf); /* 输入：多项式的系数和指数存在p1 文件中，两个两个读，分别赋给多项式的系 数和指数。 */ poly *inputPoly() poly *q,*p; p=newPoly(); q=p; FILE *fp; if(fp=fopen(“c:p1.txt“,“rt“)=NULL) printf(“nCannot open file strike any
17、 key exit!“); getch(); exit(1); 实用标准文案 精彩文档 int a,b; while(fscanf(fp,“%d %d“, 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=newPoly(); q=p; FILE *fp; if(fp=fopen(“c:p2.txt“,“rt“)=NULL) printf(“nCannot open fil
18、e strike any key exit!“); getch(); exit(1); int a,b; 实用标准文案 精彩文档 while(fscanf(fp,“%d %d“, 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*xb 的形式输出 */ void outputPoly(poly*p) poly*q; q=p-link; if(q!=NULL) printf(“%dx%d “,q-coef,
19、q-exp); q=q-link; else printf(“0“); 实用标准文案 精彩文档 while(q!=NULL) if(q-coefcoef,q-exp); else printf(“+%dx%d “,q-coef,q-exp); 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!=NUL
20、L) b=a-link; while(b!=NULL) 实用标准文案 精彩文档 if(a-exp)exp) i=a-coef; a-coef=b-coef; b-coef=i; i=a-exp; a-exp=b-exp; b-exp=i; b=b-link; a=a-link; /* 计算：调用函数 pow （x，b）之后乘以系数 */ double caculate(double x,poly *p) double m=0; if(p-link=NULL) return 0; else do m+=p-coef*pow(x,p-exp); p=p-link; while(p!=NULL); return m; 实用标准文案 精彩文档