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

哈尔滨工业大学计算机科学与技术学院实验报告课程名称：数据结构与算法课程类型：必修实验项目：线性结构及其应用实验题目：多项式的加减乘除和特定值带入实验日期：2017/11/5班级：1603001学号：1160300121姓名：安宏宇设计成绩报告成绩指导老师张岩一、实验目的设计线性表的链式存储结构，并实现一元多项式的代数运算。二、实验要求及实验环境（1）实验要求：以链表存储一元多项式，在此基础上完成对多项式的代数操作。1.能够输入多项式（可以按各项的任意输入顺序，建立按指数降幂排列的多项式）和输出多项式（按指数降幂排列）,以文件形式输入和输出，并显示。2.能够计算多项式在某一点x=x0的值，其中x0是一个浮点型常量，返回结果为浮点数。3.能够给出计算两个多项式加法、减法、乘法和除法运算的结果多项式，除法运算的结果包括商多项式和余数多项式。4.要求尽量减少乘法和除法运算中间结果的空间占用和结点频繁的分配与回收操作。（提示：利用循环链表结构和可用空间表的思想，把循环链表表示的多项式返还给可用空间表，从而解决上述问题）。（2）实验环境：windows下的CB;三、设计思想（本程序中的用到的所有数据类型的定义，主程序的流程图及各程序模块之间的调用关系）1．逻辑设计:structpolynode{intcoef;intexp;structpolynode*link;};//建立链表typedefstructpolynodepoly;poly*Attch(intc,inte,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();doublecaculate(doublex,poly*p);//计算多项式voidsortPoly(poly*p);//多项式排序voidoutputPoly(poly*p);//输出多项式voiddelPoly(poly*p);//清空多项式2．物理设计：四、测试结果五、经验体会与不足不能连续输入多个多项式函数设计不够简洁算法过于直接简单加注释后修改代码方便六、附录：源代码（带注释）#includestdio.h#includestdlib.hstructpolynode{intcoef;intexp;structpolynode*link;};//建立新链表typedefstructpolynodepoly;poly*Attch(intc,inte,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();//输入doublecaculate(doublex,poly*p);//计算voidsortPoly(poly*p);//排序voidoutputPoly(poly*p);//输出多项式voiddelPoly(poly*p);//除法voidInsert(poly*p,poly*h){if(p-coef==0)free(p);else{poly*q1,*q2;q1=h;q2=h-link;while(q2&&p-expq2-exp){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);}}/*相等就加系数*/else{p-link=q2;q1-link=p;}}/*不等就插在后面*/}intmain(){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(padd\n);outputPoly(padd1);psub1-link=psub(p1,p2);printf(psub\n);outputPoly(psub1);pmul1-link=pmul(p1,p2);printf(pmul\n);outputPoly(pmul1);printf(输入x的值！);intx;scanf(%d,&x);x=caculate(x,p1);printf(%d\n,x);pdiv(p1,p2);return0;}poly*newPoly(){poly*x;x=(poly*)malloc(sizeof(poly));x-link=NULL;x-coef=0;x-exp=0;returnx;}poly*Attch(intc,inte,poly*d){poly*x;x=newPoly();x-coef=c;x-exp=e;d-link=x;returnx;}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;}elseif(a-expb-exp)//小于相反{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;}}/*ab比较完成开始遍历剩下的未插入的*/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);returnd;}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&&b!=NULL){if(a-expb-exp){c=Attch(a-coef,a-exp,c);a=a-link;}elseif(a-expb-exp){c=Attch(b-coef*(-1),b-exp,c);b=b-link;}else{if((a-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);returnd;}/*乘法，先用第一个链表的第一个数据乘以第二个链表里的所有值，储存在新的链表中，之后遍历一中所有的值，最后把这些多项式加在一起。*/poly*pmul(poly*p1,poly*p2)//乘法{poly*a,*b,*c,*d,*q,*sum;intaex,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);a=a-link;delPoly(d);}sum=sum-link;q-link=NULL;delPoly(q);sortPoly(sum);returnsum;}/*除法：先用链表一第一个的系数除以第二个链表的第一个系数，得到的值乘以被除多项式，再用第一个多项式减。最后得到一个最大系数比被除数小的多项式。*/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-coef)/(q2-coef);temp2-link-exp=(q1-exp)-(q2-exp);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);}/*输入：多项式的系数和指数存在p1文件中，两个两个读，分别赋给多项式的系数和指数。*/poly*inputPoly(){poly*q,*p;p=newPoly();q=p;FILE*fp;if((fp=fopen(c:\\p1.txt,rt))==NULL){printf(\nCannotopenfilestrikeanykeyexit!);getch();exit(1);}inta,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);returnq;}poly*inputPoly1(){poly*q,*p;p=newPoly();q=p;FILE*fp;if((fp=fopen(c:\\p2.txt,rt))==NULL){printf(\nCannotopenfilestrikeanykeyexit!);getch();exit(1);}inta,b;while(fscanf(fp,%d%d,&a,&b)