动态链表之实现多项式加法和乘法

1/8数据结构实验报告学号：2015111898姓名：许明华专业：计算机科学与技术知识范畴：线性表、链表、文件完成日期：2017年03月24日实验题目：基于链表的多项式乘法实验内容及要求：从字符文件输入两个多项式的非零系数及对应的指数，建立多项式的链式存储结构，计算这两个多项式的乘积，输出乘积多项式的全部非零系数及对应的指数到另一字符文件中。要求输入输出字符文件中的数据格式自拟；编程语言采用C/C++。实验目的：掌握单向链表的基本操作以及基于链表的多项式加法与乘法。数据结构设计简要描述：序言：这是本学期的第一个实验，实验的主要内容使我们第一章所学的线性表以及文件操作；数据结构设计：首先我们将本次实验分为两个大的模块：1，第一个模块，文件操作，采用fscanf函数从文件中将两个多项式的系数和指数读取出来，采用fprintf函数将两个多项式的乘积的系数和指数保存在文件中2，第二个模块，链表的多项式加法和乘法实现，采用带附加头结点的单向链表来保存多项式的系数和指数（系数和指数均为int型），每个节点包括两个整型的数据域和一个指针域；算法设计简要描述：1，链表的创建采用带附加头结点的单向动态链表实现，用于保存从文件中读取出来的多项式的系数和指数；1，多项式的加法，考虑采用两个源多项式结点生成和式的结点，算法要求两个源多项式结点按指数e升序连接，算法结束时，两个源多项式称为空链表；2，多项式的乘法，首先两个多项式的结点数必须相同，原理性算法如下：R(x)=0;For(i=0;in;i++){T(x)=P(x)CiX^di;//两个多项式的结点必须相同R(x)=R(x)+T(x);//利用加法算法}输入/输出设计简要描述：2，输入：输入存放第一个多项式的文件的文件名，打印第一个多项式后；输入第二个多项式的文件的文件名，打印为第二个多项式，并打印出多项式的乘积；再输入要保存乘积多项式的文件的文件名，以保存乘积多项式的系数和指数到文件中；3，输出：输入第一个文件名后，打印第一个多项式；输入第二个文件名后，打印第二个评分满分——10分2/8多项式以及乘积多项式，；输入第三个文件名后，程序执行结束，将乘积多项式的系数和指数保存在文件中；4，整个程序执行结束，退出doc页面。编程语言说明：5，编程软件，CodeBlocks16.0；6，代码均用c语言实现；7，链表采用带附加头结点的单向动态链表实现，采用malloc函数给结构体变量分配内存空间；8，输入输出采用C语言的scanf和printf函数；9，文件读写采用FILE类型；10，程序注释采用C/C++规范；主要函数说明：poly*creat_poly(charfilename[10]);//创建链表保存多项式系数和指数poly*add_poly(poly*ha,poly*hb);//多项式的加法具体实现poly*mul_poly(poly*ha,poly*hb);//多项式的乘法具体实现voidprint_poly(poly*h);//多项式输出具体实现voidge_file(inti,poly*h,charfilename[10]);//从文件中读取多项式的系数和指数voidwr_file(poly*h,poly*ha,poly*hb);//将多项式的乘积的系数和指数保存在文件中程序测试简要报告：（1），测试实例1程序输入：第一个多项式文件名：poly_1.txt//文件中内容为（11223300)第二个多项式文件名：poly_2.txt//文件中内容为（22334400）请输入你想要写入的文件名：mul_poly.txt//乘积的多项式的系数和指数保存的文件程序输出：第一个多项式为：1*x^1+2*x^2+3*x^3第二个多项式为：2*x^2+3*x^3+4*x^4两个多项式的乘积：2*x^3+7*x^4+16*x^5+17*x^6+12*x^7结论：程序输出结果和期望输出结果相符源程序代码：#includestdio.h#includemalloc.h#includestdlib.h3/8//定义结构体类型保存多项式的系数和指针typedefstructnode{intcoef;intex;structnode*next;//指针变量，指向结构体变量}poly;#defineCreatNode(p)p=(poly*)malloc(sizeof(poly))//单向链表建立结点#defineDeleteNode(p)free((void*)(p))//单向链表删除结点//声明函数（返回类型为指针，所以定义的时候要用*）poly*creat_poly(charfilename[10]);//返回类型为指针所以必须加*号poly*add_poly(poly*ha,poly*hb);poly*mul_poly(poly*ha,poly*hb);voidprint_poly(poly*h);voidge_file(inti,poly*h,charfilename[10]);//文件读取voidwr_file(poly*h,poly*ha,poly*hb);//文件写入//函数实现//创建链表(在创建链表的时候便将文件中的数据读写出来)poly*creat_poly(charfilename[10]){FILE*fp;if((fp=fopen(filename,r))==NULL){printf(cannotopenthefile\n);exit(0);}intcoef;intex;poly*head=NULL,*p1,*p2;//头结点head置空这样能保证程序不会错误，p1为指向头结点的指针，p2为保存输入的数据的指针head=(poly*)malloc(sizeof(poly));//为head分配内存空间head-coef=-1;//将head中的实际数据赋值为-1head-ex=-1;head-next=NULL;//将head的下一个结点置空p1=head;//使p1指向head，便于后连接到p2上面去while(1)//从文件中将系数和指数依次读出来，直到系数和指数为0{4/8fscanf(fp,%d%d,&coef,&ex);//从文件中将系数和指数依读出来if(coef==0&&ex==0){break;}p2=(poly*)malloc(sizeof(poly));//给p2分配内存空间，来保存输入的数据p2-coef=coef;p2-ex=ex;p2-next=NULL;p1-next=p2;//将p2所指结点连接到p1所指结点的后面p1=p2;}fclose(fp);returnhead;}//多项式相加poly*add_poly(poly*ha,poly*hb){poly*p1,*p2,*p3,*h,*p;p1=ha-next;p2=hb-next;//将ha-next的值保存在p1中，将hb-next的值保存在p2中CreatNode(h);p3=h;//建立头结点并将p3指向头结点while(p1&&p2){if(p1-exp2-ex)//p1的指数小于p2的指数{p=p1;p1=p1-next;}elseif(p1-nextp2-next)//p1的指数大于p2的指数{p=p2;p2=p2-next;}else//当两者的指数相等时{p1-coef=p1-coef+p2-coef;if(p1-coef==0){//如果系数为，两者在和的多项式中应该被去掉，所以将两个结点都要删除p=p1;p1=p1-next;DeleteNode(p);5/8p=p2;p2=p2-next;DeleteNode(p);continue;}p=p2;p2=p2-next;DeleteNode(p);//删除p2，将p1所指结点作为和式多项式的值p=p1;p1=p1-next;}p3-next=p;p3=p;//将p的值保存在p3的下一个结点中，并将p3作为p的表尾}if(p1)p3-next=p1;//p1未完，将p1加入到尾结点中去elseif(p2)p3-next=p2;//p2的值保存在表尾的结点中去elsep3-next=NULL;ha-next=hb-next=NULL;returnh;}//多项式相乘poly*mul_poly(poly*ha,poly*hb){poly*hr,*ht,*q,*pt,*p;//创建五个poly指针变量，hr，ht用于初始化两个多项式，//q指向第二个多项式/p只想第一个多项式///pt指向第二个多项式并作为扫描指针CreatNode(hr);hr-next=NULL;//R(x)=0;CreatNode(ht);ht-next=NULL;//T(x)=0;q=hb-next;//q指向第二个多项式，并将hb-next的值保存在q中while(q){//q为真时，执行for(i=0;in;i++)pt=ht;//让pt指向ht，即指向第二个多项式p=ha-next;//p指向第一个多项式，并将hb=a-next的值保存在p中while(p){//实现T(x)=P(x)*Ci*X^di;CreatNode(pt-next);pt=pt-next;pt-coef=p-coef*q-coef;//用第二个多项式的第一项系数来乘第一个多项式的每一项系数pt-ex=p-ex+q-ex;//将其指数相加p=p-next;//第二个多项式进行循环}6/8pt-next=NULL;q=q-next;p=add_poly(hr,ht);DeleteNode(hr);hr=p;}DeleteNode(ht);returnhr;}//多项式输出voidprint_poly(poly*h){h=h-next;while(h!=NULL){if(h-next!=NULL){//多项式还没有到达末尾时，输出有+号printf(%d*x^%d+,h-coef,h-ex);h=h-next;}elseif(h-next==NULL){//当多项式到达表尾时，只输出最后一组数，不需要在输出+号了printf(%d*x^%d,h-coef,h-ex);h=h-next;}}printf(\n);}//文件读取voidge_file(inti,poly*h,charfilename[10]){FILE*fp;if((fp=fopen(filename,r))==NULL){printf(cannotopenthefile\n);exit(0);}7/8printf(第%d个多项式为:\n,i);fclose(fp);}//文件写入voidwr_file(poly*h,poly*ha,poly*hb){FILE*fp;poly*hc;charfilename[10];//实现两个多项式的乘积操作h=mul_poly(ha,hb);hc=h-next;print_poly(h);//将多项式的乘积输出到屏幕printf(\n请输入你想写入的文件名:\n);gets(filename);//得到写入文件的文件名if((fp=fopen(filename,w))==NULL){printf(cannotopenthefile\n);exit(0);}while(hc!=NULL)//将多项式的系数和指数写入到文件中{fprintf(fp,%d%d,hc-coef,hc-ex);hc=hc-next;}fclose(fp);}//主函数输出intmain(){poly*h1,*h2,*s_poly,*m_poly,*M_poly;charfilename[10];printf(请输入第1个多项式文件名:\n);//输出第1个多项式gets(filename);8/8ge_file(1,h1,filename);//从文件中读出第一个多项式