数据结构实验一完成多项式的相加运算

福建农林大学金山学院本科实验报告规范（暂行）程序设计类一、每个实验项目一份实验报告。二、实验报告内容一般包括以下几个内容：1、实验项目名称：2、实验目的和要求：3、实验内容和原理：4、实验环境：本次上机实验所使用的软硬件平台。5、算法描述及实验步骤：用算法、流程图或者源代码的形式表达算法设计思想与算法实现步骤。6、调试过程：详细记录程序在调试过程中出现的问题及解决方法。7、实验结果：记录测试数据及程序执行的结果。8、总结：对上机实验结果进行分析、上机的心得体会及改进意见。9、附录（调试正确的源程序清单）说明：1、2、3、4、5属于实验预习报告的内容，每次实验需经指导教师检查签字后才能进行实验。三、实验报告格式见附件二（可打印）。四、每学期将拟存档的学生实验报告按课程、学生装订成册，即每个学生每门课程所有实验报告装订成一本。装订线在左侧，第一页加订实验报告封皮。五、福建农林大学计算机与信息学院实验报告封皮范本见附件一。六、福建农林大学计算机与信息学院实验报告范本见附件二。附件一：福建农林大学金山学院（程序设计类课程）实验报告课程名称：线性表及其应用姓名：曾钦选系：专业：计算机科学与技术年级：08级学号：082231032指导教师：林敏职称：讲师2010年4月18日实验项目列表序号实验项目名称成绩指导教师1线性表及其应用2哈夫曼树及哈夫曼编码译码的实现3Prim最小生成树4实现Fibonacci检索算法5快速、堆、基数排序算法的设计6789101112福建农林大学金山学院实验报告系（教研室）：专业：计算机科学与技术年级：08实验课程：姓名：曾钦选学号：082231032实验室号：______计算机号：实验时间：指导教师签字：成绩：实验一：完成多项式的相加运算（验证性、4学时）一、实验目的和要求完成多项式的相加、相乘运算。（1）掌握线性表的插入、删除、查找等基本操作设计与实现（2）学习利用线性表提供的接口去求解实际问题（3）熟悉线性表的的存储方法二、实验内容和原理1.实验内容设计一个一元多项式的简单计算程序，其基本功能有：（1）输入并建立多项式；（2）输出多项式；（3）多项式的相加运算。利用单链表实现。2.实验原理使用单链表实现一元多项式的存储，并实现两个一元多项式的加法运算。三、实验环境硬件：（1）学生用微机（2）多媒体教室或远程教学（3）局域网环境软件：（1）WindowsXP中文操作系统（2）VC6.0四、算法描述及实验步骤1、描述：加法：输入建立一元多项式,进行简单加法运算,输出结果；通过建立单链表A和B分别存放多项式的a和b的各项系数及指数；并且利用A使得不产生新的节点而在A中存放数据运算结果；该过程通过定义指针变量p和q使它们分别指向两个多项式的第一个节点，之后依次比较它们所指向的项的指数，即一种情况指数相等时系数相加且和不为零，修改当前p所指项的系数（和），同时删除q所指项，若和为零则同时删除p和q各自所指；情况二，p当前项指数大于q当前项，将q所指插入p所指之前作为结果项之一；情况三，p当前项指数小于q当前项，p所指作为多项式和的一项，移动p指向下一项，进行比较，在移动p，q至其中以个链空，把另一个链余下节点插在p所指之后；乘法：定义指针p,q指向所操作节点，通过A链表的每一项与B链表各项相乘，指数相加，系数相乘，将值赋给新节点各自域，构成一新的链表，最后返回头结点。可这样有一个问题，即新生成的链表，即最终结果混乱，没有对数据进行过滤，相同指数项应在执行加法运算，所以可以这样实现，通过A链表的每一项与B链表各项相乘的新生成节点单独构成一链表，并将第一个链表加入另一新链表，循环此操作将后生成的链表加之先前的链表，即可实现排序问题。1）加法算法如下：polynomial*polyadd(polynomial*A,polynomial*B){polynomial*p,*q,*s,*r;floatx;p=A-next;q=B-next;s=p;while((p!=NULL)&&(q!=NULL))if((p-exp)(q-exp)){r=q-next;q-next=p;s-next=q;s=q;q=r;}elseif((p-exp)(q-exp)){s=p;p=p-next;}else{x=(p-coef)+(q-coef);/*if(x!=0){p-coef=x;s=p;}else{s-next=p-next;free(p);}*/p=s-next;r=q;q=q-next;free(r);}if(q!=NULL)s-next=q;free(B);returnA;}2）乘法算法polynomial*polyand(polynomial*A,polynomial*B)/*核心算法实现两链表的乘法运算*/{polynomial*p,*q,*n,*head,*r,*temp,*m;//定义当前指针p，q风别指向两链表和头指针，尾指针，及新生成节点nintexp;//定义整型指数floatcoef;//定义浮点型系数head=(polynomial*)malloc(sizeof(polynomial));//创头节点为新生链表准备head-next=NULL;//置空链表r=head;//临时变量，为后移指针做准备p=A-next;//当前指针跳过A链表头指向实际运算数while(p!=NULL)//控制操作，循环A链表与内部while所控制B链表进行项之间的运算{temp=(polynomial*)malloc(sizeof(polynomial));//在内部创头节点为新生链表准备即A中每一项与B中各项相乘构成一新链表temp-next=NULL;//置空链表m=temp;//临时变量，为后移指针做准备q=B-next;//当前指针跳过B链表头指向实际运算数while(q!=NULL){n=(polynomial*)malloc(sizeof(polynomial));//建立新节点exp=p-exp+q-exp;//进行系数相加操作coef=p-coef*q-coef;////进行指数相乘操作n-coef=coef;//赋值新节点的系数域n-exp=exp;//赋值新节点的指数域m-next=n;//链接节点至头结点，构成链表m=m-next;//后移指针，为下一节点做准备q=q-next;//控制B链表下一项//printf(%f%d,coef,exp);//调试用}p=p-next;//控制A链表下一项m-next=NULL;//链表尾置空//head=head-next;polyadd(head,temp);//}returnhead;}2、1）加法算法流程图2）乘法算法流程图polynomial*p,*q,*s,*r;floatx;p=A-next;q=B-next;s=p;Y(p-exp)(q-exp)Nr=q-next;s-next=q;free(B);returnA;p=s-next;r=q;q=q-next;free(r);x=(p-coef)+(q-coef);q-next=p;s-next=q;Yx！=0Ns=q;(p-exp)(q-exp)NY(p!=NULL)&&(q!=NULL)q=r;p-coef=x;s=p;s-next=p-next;free(p);s=p;p=p-next;q!=NULLY3、代码(注释)#includestdio.h#includemalloc.hpolynomial*p,*q,*n,*head,*r,*temp,*m;intexp；floatcoef；head=(polynomial*)malloc(sizeof(polynomial));head-next=NULL;p=A-next;temp=(polynomial*)malloc(sizeof(polynomial));temp-next=NULL;m=temp;q=B-next;n=(polynomial*)malloc(sizeof(polynomial));exp=p-exp+q-exp;coef=p-coef*q-coef;n-coef=coef;n-exp=exp;m-next=n;m=m-next;q=q-next;p!=NULL;q!=NULL;p=p-next;m-next=NULL;polyadd(head,temp);returnhead;typedefstructlinknode/*定义节点*/{floatcoef;intexp;structlinknode*next;}polynomial;polynomial*creatlist()/*创建单链表*/{floatx;/*节点中存放项系数和指数*/intz;polynomial*head,*r,*n;/*下指针,分别是头指针、尾指针和新建立节点的指针*/head=(polynomial*)malloc(sizeof(polynomial));/*malloc分配内存单元给头指针申请空间*/head-next=NULL;/*头指针next指向空位空链表状态*/r=head;printf(建立一元多项式:(以系数0结束)\n);/*打印文字提醒用户输入*/while(x!=0)/*建立单链表*/{n=(polynomial*)malloc(sizeof(polynomial));/*建立新节点,将用户输入的数据分别作为项(各节点)的系数和指数*/n-coef=x;n-exp=z;r-next=n;/*为指针指向下一新建节点*/r=r-next;/*后移尾指针*///r=n;printf(请按升幂输入系数和指数:);scanf(%f%d,&x,&z);}r-next=NULL;head=head-next;/*链接节点使之勾成链表*/return(head);/*还回head指针(链表头标志或是说地址)给函数调用者*/}voidprint(polynomial*head)/*打印输出函数*/{polynomial*p;/*为传入的链表设立当前指针*/p=head-next;/*将指针后移指向包含实际数据的节点*/while(p!=NULL)/*判断需要打印的链表是否为空*/{printf(%.2fX(%d),p-coef,p-exp);/*打印当前指针所指项的数据*/p=p-next;/*后移指针指向下一节点*/}printf(\n);}polynomial*polyadd(polynomial*A,polynomial*B)/*核心算法实现两链表的加法运算并将结果保存在A中*/{polynomial*p,*q,*s,*r;/*为链表设立指针分别指向链表A和链表B(多项式A和B)，s为临时存放为后续移动指针做地址保留*/floatx;p=A-next;q=B-next;s=A;/**//*s作为p的前驱*/while((p!=NULL)&&(q!=NULL))/*判断所比较链表是否为空不同时为空时反复执行下列函数*/if((p-exp)(q-exp))/*将q插入p之前*/{r=q-next;/*保存当前q的下一结点地址为r后移作准备*/q-next=p;/*将p接到到q之后*/s-next=q;/*将q彻底的插入到A链表中p之前作为结果项之一*/s=q;/*修改当前指针为下一节点作比较准备*/q=r;}elseif((p-exp)(q-exp))/*将p作为结果项之一，后移p进行下一结点比较*/{s=p;/*后移s*/p=p-next;/*后移当前指针p指向下一节点*/}else/*当前链表中节点的指数相等进行系数加法运算*/{x=(p-coef)+(q-coef);/*实现系数相加赋给x，节点中的系数单元*/if(x!=0)/*判断系数和是