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

数据结构实验报告评分满分10分学号：2015111898 姓名：许明华 专业：计算机科学与技术知识范畴：线性表、链表、文件 完成日期：2017年03月24日实验题目：基于链表的多项式乘法实验内容及要求：从字符文件输入两个多项式的非零系数及对应的指数，建立多项式的链式存储结构，计算这两个多项式的乘积，输出乘积多项式的全部非零系数及对应的指数到另一字符文件中。要求输入输出字符文件中的数据格式自拟；编程语言采用C/C+。实验目的：掌握单向链表的基本操作以及基于链表的多项式加法与乘法。数据结构设计简要描述：序言：这是本学期的第一个实验，实验的主要内容使我们第一章所学的线性表以及文件操作；数据结构设计：首先我们将本次实验分为两个大的模块：1，第一个模块，文件操作，采用fscanf函数从文件中将两个多项式的系数和指数读取出来，采用fprintf函数将两个多项式的乘积的系数和指数保存在文件中2，第二个模块，链表的多项式加法和乘法实现，采用带附加头结点的单向链表来保存多项式的系数和指数（系数和指数均为int型），每个节点包括两个整型的数据域和一个指针域； 算法设计简要描述：1， 链表的创建采用带附加头结点的单向动态链表实现，用于保存从文件中读取出来的多项式的系数和指数；1， 多项式的加法，考虑采用两个源多项式结点生成和式的结点，算法要求两个源多项式结点按指数e升序连接，算法结束时，两个源多项式称为空链表；2， 多项式的乘法，首先两个多项式的结点数必须相同，原理性算法如下： R(x) = 0 ; For(i = 0 ; i n ; i +) T(x) = P(x)CiXdi;/两个多项式的结点必须相同 R(x) = R(x) + T(x); /利用加法算法 输入/输出设计简要描述：2， 输入：输入存放第一个多项式的文件的文件名，打印第一个多项式后；输入第二个多项式的文件的文件名，打印为第二个多项式，并打印出多项式的乘积；再输入要保存乘积多项式的文件的文件名，以保存乘积多项式的系数和指数到文件中；3， 输出：输入第一个文件名后，打印第一个多项式；输入第二个文件名后，打印第二个多项式以及乘积多项式，；输入第三个文件名后，程序执行结束，将乘积多项式的系数和指数保存在文件中；4， 整个程序执行结束，退出doc页面。编程语言说明：5， 编程软件，Code Blocks 16.0；6， 代码均用c语言实现；7， 链表采用带附加头结点的单向动态链表实现，采用malloc函数给结构体变量分配内存空间；8， 输入输出采用C语言的scanf和printf函数；9， 文件读写采用FILE类型；10， 程序注释采用C/C+规范；主要函数说明： poly *creat_poly(char filename10);/创建链表保存多项式系数和指数poly *add_poly(poly *ha,poly *hb);/多项式的加法具体实现poly *mul_poly(poly *ha,poly *hb); /多项式的乘法具体实现void print_poly(poly *h);/多项式输出具体实现void ge_file(int i , poly *h ,char filename10);/从文件中读取多项式的系数和指数void wr_file(poly *h , poly *ha , poly *hb);/将多项式的乘积的系数和指数保存在文件中程序测试简要报告：（1），测试实例1 程序输入：第一个多项式文件名： poly_1.txt /文件中内容为（1 1 2 2 3 3 0 0 )第二个多项式文件名： poly_2.txt /文件中内容为（2 2 3 3 4 4 0 0 ）请输入你想要写入的文件名：mul_poly.txt /乘积的多项式的系数和指数保存的文件 程序输出：第一个多项式为： 1*x1+2*x2+3*x3第二个多项式为： 2*x2+3*x3+4*x4两个多项式的乘积： 2*x3+7*x4+16*x5+17*x6+12*x7结论： 程序输出结果和期望输出结果相符源程序代码：#include#include#include/定义结构体类型保存多项式的系数和指针typedef struct node int coef; int ex; struct node *next; /指针变量，指向结构体变量poly;#define CreatNode(p) p = (poly *)malloc(sizeof(poly)/单向链表建立结点#define DeleteNode(p) free(void *)(p) / 单向链表删除结点/声明函数（返回类型为指针，所以定义的时候要用*）poly *creat_poly(char filename10);/返回类型为指针所以必须加*号poly *add_poly(poly *ha,poly *hb);poly *mul_poly(poly *ha,poly *hb);void print_poly(poly *h);void ge_file(int i , poly *h ,char filename10);/文件读取void wr_file(poly *h , poly *ha , poly *hb);/文件写入/函数实现/创建链表(在创建链表的时候便将文件中的数据读写出来)poly *creat_poly(char filename10) FILE *fp; if(fp = fopen(filename,r) = NULL) printf(can not open the filen); exit(0); int coef; int ex; poly *head = NULL,*p1,*p2;/头结点head置空这样能保证程序不会错误，p1为指向头结点的指针，p2为保存输入的数据的指针 head = (poly *)malloc(sizeof(poly);/为head分配内存空间 head-coef = -1;/将head中的实际数据赋值为-1 head-ex = -1; head-next = NULL;/将head的下一个结点置空 p1 = head;/使p1指向head，便于后连接到p2上面去 while(1)/从文件中将系数和指数依次读出来，直到系数和指数为0 fscanf(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); return head;/多项式相加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-exex)/p1的指数小于p2的指数 p = p1; p1 = p1-next; else if(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); p = 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加入到尾结点中去 else if(p2) p3-next = p2;/p2的值保存在表尾的结点中去 else p3-next = NULL; ha-next = hb-next = NULL; return h;/多项式相乘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 ;i next; /p指向第一个多项式，并将hb=a-next的值保存在p中 while(p) /实现T(x)=P(x)*Ci*Xdi; CreatNode(pt-next); pt = pt-next; pt-coef = p-coef*q-coef;/用第二个多项式的第一项系数来乘第一个多项式的每一项系数 pt-ex = p-ex+q-ex; /将其指数相加 p = p-next; /第二个多项式进行循环 pt-next = NULL; q = q-next; p = add_poly(hr,ht); DeleteNode(hr); hr = p; DeleteNode(ht); return hr; /多项式输出void print_poly(poly *h) h = h-next; while(h!=NULL) if(h-next!=NULL)/多项式还没有到达末尾时，输出有+号 printf(%d*x%d+,h-coef,h-ex); h = h-next; else if(h-next = NULL)/当多项式到达表尾时，只输出最后一组数，不需要在输出+号了 printf(%d*x%d,h-coef,h-ex); h = h-next; printf(n);/文件读取void ge_file(int i , poly *h ,char filename10) FILE *fp; if(fp = fopen(filename,r) = NULL) printf(can not open the filen); exit(0); printf(第%d个多项式为:n,i); fclose(fp);/文件写入void wr_file(poly *h , poly *ha , poly *hb) FILE *fp; poly *hc; char filename10; /实现两个多项式的乘积操作 h = mul_poly(ha,hb); hc = h -next; print_poly(h);/将多项式的乘积输出到屏幕 printf(n请输入你想写入的文件名:n); gets(filename);/得到写入文件的文件名 if(fp = fopen(filename,w) = NULL) printf(can not open the filen); exit(0); while(hc!=NULL)/将多项式的系数和指数写入到文件中 fprintf(fp,%d%d,hc-coef,hc-ex); hc = hc-next; fclose(fp);/主函数输出int main() poly *h1,*h2,*s_poly,*m_poly,*M_poly; char filename10; printf(请输入第1个多项式文件名:n);/输出第1个多项式 gets(filename); ge_file(1,h1,filename);/从文件中读出第一个多项式系数