n元多项式乘法-课程论文.docVIP

西北农林科技大学信息工程学院数据结构与c语言综合训练实习报告题 目： n元多项式的乘法 学 号20101012834姓 名 张 勇专业班级 计算机科学与技术指导教师 蔡 骋实践日期2011年7月8日2011年7月18日目录一、综合训练目的与要求1二、 综合训练任务描述1三、算法设计1四、 详细设计及说明5(1)n元多项式的存储结构5(2)n元多项式的建立6(3)n元多项式的乘法7(4)n元多项式的输出9五、调试与测试10六、实习日志11七、实习总结11八、附录：核心代码清单11一、综合训练目的与要求 本综合训练是计算机科学与技术专业重要的实践性环节之一，是在学生学习完c语言和数据结构课程后进行的综合练习。本课综合训练的目的和任务：1. 巩固和加深学生对数c语言和数据结构程基本知识的理解和掌握；2. 培养利用算法知识解决实际问题的能力；3. 掌握利用程序设计语言进行算法程序的开发、调试、测试的能力；4. 掌握书写算法设计说明文档的能力；5. 提高综合运用算法、程序设计语言、数据结构知识的能力。2、 综合训练任务描述n元多项式的乘法：(1) 界面友好，函数功能要划分好(2) 总体设计应画一流程图 (3) 程序要加必要的注释(4) 要提供程序测试方案(5) 程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。三、算法设计(1) 文字描述 本题为完成n元多项式的乘法，n元多项式所以每一项中有n个未知数，而且未知数的指数未定，我采用的是链表之中嵌套链表的方法存储多项式，大链表存储多项式的系数和指向小链表的指针，小链表存储未知数和其指数。然后再分步相乘，先是项项相乘，然后相加即可得到多项式的乘积，最后将多项式输出即可。输入多项式a，b 开始多项式c=a*b输出多项式c 结束(2) 框图程序主流程图如下： 函数中项项相乘函数multvarible(vartype a, vartype b)实现的流程图如下： vartype c，vlink pa, pb ， elemtype data， pa = a.head-next;否 是是是否是否 开 始1 pa=null pa为多项式a指向头结点的下一个节点的指针data为数据域，pb指向子链表的数据域， pb为多项式b指向头结点的下一个节点的指针inslastvar(c, data);pa=pa-next;pb-data.varible = data.variblepb=nullpb=null data.expn+=pb-data.expn; pb=pb-next 无操作 32是否是否pa-data.varible = pb-data.varible1 3 2否pb=b.head-next;pa=c.head-next;flag=0是pa=null否returne c pb=pb-next data = pb-data; inslastvar(c, data);无操作flag=0pa=pa-next break跳出当前循环 fiag=1无操作 结束多项式相乘算法流程图：eplink pa ,pb;varitype va ,vb, vc ;int cofe;expersstype c;是否是否开始定义指针eplink pa，pb，vartype va,vb,vc int coef, expressiontype c;pa = a.head-nextpa=nullva = pa-exprepb = b.head-nextpb=nullvb = pb-exprevc = multvarible(va, vb)coef = (pa-coef)*(pb-coef)inslastexp(c, vc, coef) pb = pb-nextpa=pa-next结束return c (3) 伪代码定义链表的抽象数据类型：数据对象：d=ai|aielemdata,i=1,2,3,，n=0/-基本操作-/void initexpression(expressiontype &a)操作结果：初始化多项式inslastvar(vartype &a, elemtype data)操作结果：将多项式中的一项尾插进子链表（存储一项之中未知数和其指数的链表）void inslastexp(expressiontype &a, vartype expre, int coef)操作结果：将多项式中的一项尾插进多项式链表之中vartype multvarible(vartype a, vartype b)操作结果：多项式中的项项相乘，返回一个子链表的首地址expressiontype multexpression(expressiontype a, expressiontype b)操作结果：多项式相乘,返回一个多项式链表的首地址printpolyn(expressiontype c)操作结果：输出多项式4、 详细设计及说明(1)n元多项式的存储结构 链表在c语言中是一种常见的数据结构形式，由于本题为n元多项式，故不能使用普通的单链表类型，所以必须加以改进。此题的链表存储结构型为：coef*vartype*nextvaribleexpn*nextcoef中存储的为多项式每个项前面的常数项系数，vartype为指向一项中的除常数项之外的未知数及它的指数，varible为未知数，expn为varible的指数。例如：5x2b4+c6k10的存储形式为5*vartype*next b 4nextx5*next null明确链表的数据类型接下来就是建立这个链表首先我们来定义一个结构体同于存储未知数和它的指数，结构体如下：typedef structchar varible; /变量名int expn; /变量的指数 elemtype;然后就是在定义一个结构题用于存储子链表（即存储未知数的链表），结构体如下：typedef struct vnode elemtype data; /数据类型 struct vnode*next; /指向下一个节点的指针*vlink;为了方便以后的操作，将子链表中的头结点和尾节点存入一个结构体之中，如下：typedef struct vlink head; /指向子链表的头结点 vlink rear; /指向子链表的尾节点 vartype;接下来我们来定义大链表结构体（即存储多项式的链表），结构体如下：typedef struct epnode int coef; /定义每一项前面的系数 vartype expre; /指向子链表的指针 struct epnode *next; /大节的下一个*eplink;同理为了便于操作，我们同样将大链表的头指针和尾指针存入结构体之中,如下：typedef struct char symbol; /存储多项式名称 eplink head; /多项式链表的头结点 eplink rear; /多项式链表的尾节点 expressiontype;以上即为n元多项式的存储结构。(2)n元多项式的建立 有了以上n元多项式的存储结构，接下类就是要建立这个多项式，由上边的存储结构知n元多项式为链表嵌套链表式结构，所以我们可以先建立以未知数和其指数为结构体的小链表，可直接使用一个尾插的函数来建立这个小链表，函数如下：void inslastvar(vartype &a, elemtype data) vlink p = new vnode; /建立新节点 p-data = data; /赋值 p-next = null; a.rear-next = p; a.rear = p;有了这个尾插函数接下来我们再来建立多项式函数，即大链表，同理我们依然可以根据尾插原理来建立这个多项式函数，函数如下：void inslastexp(expressiontype &a, vartype expre, float coef) eplink p = new epnode; /建立新节点 p-expre = expre; /将子链表的首地址赋给大链表中的指针 p-coef = coef; /为系数赋值 p-next = null; a.rear-next = p; a.rear = p;(3)n元多项式的乘法在处理多项式相乘的问题时，对多项式的相乘做了分步骤进行，首先我们定义了一个函数来完成连个子链表的相乘，函数代码如下：vartype multvarible(vartype a, vartype b) vartype c; initvar(c); vlink pa, pb; elemtype data; pa = a.head-next; while(pa) data = pa-data; /将指针pa指向的数据赋予data pb = b.head-next; while(pb) if(pb-data.varible = data.varible) /如果pa和pb指向的未知数相同，则两 /两指数相加将值赋予pa data.expn+=pb-data.expn; pb = pb-next; inslastvar(c, data); /将pa的值存入链表c中 pa = pa-next; pb = b.head-next; int flag = 0; /定义一个标志数 while(pb) /循环直到pb为空 pa = c.head-next; while(pa) if(pa-data.varible = pb-data.varible) /如果两个数的未知数相同 /则flag为一，并跳出循环 flag = 1; break; pa = pa-next; if(!flag) /如果标志数不为为0，将pb中的数据连接到 /链表c之中 data = pb-data; inslastvar(c, data); pb = pb-next; return c;代码的大致思想是先将一个子链表1中的数据存入一个临时节点，将这个临时节点与子链表2的每一个节点比较，如果有未知数相同的，把他们的指数相加，然后把相加之后的值赋值给临时节点，然后在将临时节点的值用尾插到方式插入到链表3之中。做好了子链表的相乘则接下来的多项式相乘就好办了，代码如下：expressiontype multexpression(expressiontype a, expressiontype b) expressiontype c; initexpression(c); eplink pa, pb; vartype va, vb, vc; float coef; pa = a.head-next; while(pa) va = pa-expre; pb = b.head-next; while(pb) vb = pb-expre; vc = multvarible(va, vb); printvarible(vc); coef = (pa-coef)*(pb-coef); inslastexp(c, vc, coef); pb = pb-next; pa = pa-next; return c;此代码使用了连个while循环结构，第一个循环为控制大链表1的循环，首先指针pa指向大链表的第二个节点（第一个节点的数据为空），在第一个while循环中嵌套了第二个while循环。两个节点的系数相乘，节点所指向的子链表相乘，直到第二个指针循环为空。这样第多项式一中的每一项就与多项式二中的每一项都进行了相乘。即完成了多项式的乘法。(4)n元多项式的输出在多项式的输出方面我才用了循环输出的方法，首先定义一个while循环来控制大链表的循环，定义一个指针指向头结点下一个的数据域，先输出系数，然后在定义一个while循环用以控制小链表的循环输出多项式的一项，就这样这个多项式就能够按照次序完全输出出来，具体程序代码如下：void printpolyn(expressiontype c) /输出多项式 eplink p; vlink q;p = c.head-next; int count = 0; /定义标志 while(p) /知道指向多项式结构体的指针指向为空 if(count = 0) printf(%d, p-coef); /如果是第一个的话则不需要加号 else if(p-coef 0) /如果指数大于零，则加上 printf(+%d, p-coef); else printf(%d, p-coef); count+; q = p-expre.head-next; while(q) printf(%c%d, q-data.varible, q-data.expn); q = q-next; p = p-next; coutendl;五、调试与测试程序的调试是程序顺利完成中非常关键的一步。通过程序的调试分析可以解决程序的运行错误也可以对程序的性能进行分析。这个n元多项式运算问题研究的程序最重要的就是看输出的链表是否正确，是否带有空结点，合并是否完全。决定程序成功与否的第一步是定义的multvarible函数操作是否正确。如果这一步中出现错误，那么接下来的操作可以说是错上加错。控制此操作的调用printvarible函数是决定成功与否的关键。可以先在本上写出两个正确的简单的多项式，使其具有相加后出现空结点的特点，然后变换循环变量的范围，当输出吻合时则说明操作正确。各个关键部分都已检查完毕，剩下的就是对程序的进一步细心的完善直到满足要求。此外为了美观，将字体的颜色改变，更加有利于阅读。下面我们进行多项式函数的测试：多项式a：5a2b+6a2c多项式b：6a2b2 +7e6b4+8c7多项式d：5x3e5+9x10y9+20e8x多项式e：5e8x6+10d7f9测试结果如图：由结果得程序运行正确。六、实习日志7月8日：上午选定题目，下午确定题目，完成实习实施计划书7月9日：思考n元多项式的存储方法，完成初步的存储代码7月10日：继续修改n元多项式的存储代码，并且完成7月11日：接下来要做的是n元多项式的乘法，有初步的思想，大致完成乘法的基本代码7月12日：修改完善乘法部分的代码，并且测试通过7月13日：休息一天7月14日：完成多项式的输出，至此实习的代码部分已经结束7月15日：开始写课程论文7月16日：完成课程论文7月17日：准备答辩材料7月18日：上台答辩七、实习总结通过这次c语言数据结构的综合实训让我获益匪浅。让我的书写代码的能力有了显著的提高，拿到这个课题首先遇到的问题就是如何存储这个多项式，然后在本班同学李阳的提醒下我采用了链表之中嵌套链表的方法来表示多项式，大链表的节点之中存储多项式每一项的系数和指向小链表的头指针，小链表用来存储一项之中的未知数和其指数。终于在实习第二天的时候成功将n元多项式的存储结构表示出来。接下里遇到的最大问题就是就是如何来完成多项式的乘法，根据我的存储结构，我先将两个小链表中的未知数相乘，然后循环相乘。将两个多项式的乘积存入另外一个多项式之中，然后将多项式输出。遗憾的是这次的n元多项式没有从屏幕进行输入，而是直接在程序之中进行数值的输入，尽管程序可以运行成功，但是实际操作起来很不方便八、附录：核心代码清单#include #include #include #include #include #include using namespace std;typedef struct char varible;/变量名 float expn;/变量的指数 elemtype;typedef struct vnode elemtype data; struct vnode*next;*vlink;typedef struct vlink head; vlink rear; vartype;typedef struct epnode int coef; vartype expre; struct epnode *next;*eplink;typedef struct char symbol; eplink head; eplink rear; expressiontype;/=初始化子链表=void initvar(vartype &a) a.head = new vnode; a.rear = a.head; a.head-next = null;/=初始化多项式链表=void initexpression(expressiontype &a) a.head = new epnode; a.rear = a.head; a.head-next = null;/=将多项式的一项中的一个未知数插入子链表之中=void inslastvar(vartype &a, elemtype data) vlink p = new vnode; p-data = data; p-next = null; a.rear-next = p; a.rear = p;/=将子链表尾插入多项式链表之中=void inslastexp(expressiontype &a, vartype expre, float coef) eplink p = new epnode; p-expre = expre; p-coef = coef; p-next = null; a.rear-next = p; a.rear = p;/=多项式中的项与项之间的乘法函数=vartype multvarible(vartype a, vartype b) vartype c; initvar(c); vlink pa, pb; elemtype data; pa = a.head-next; while(pa) data = pa-data; pb = b.head-next; while(pb) if(pb-data.varible = data.varible) data.expn+=pb-data.expn; pb = pb-next; inslastvar(c, data); pa = pa-next; pb = b.head-next; int flag; while(pb) pa = c.head-next; flag = 0; while(pa) if(pa-data.varible = pb-data.varible) flag = 1; break; pa = pa-next; if(!flag) data = pb-data; inslastvar(c, data); pb = pb-next; return c;/=多项式相乘函数=expressiontype multexpression(expressiontype a, expressiontype b) expressiontype c; initexpression(c); eplink pa, pb; vartype va, vb, vc; float coef; pa = a.head-next; while(pa) va = pa-expre; pb = b.head-next; while(pb) vb = pb-expre; vc = multvarible(va, vb); coef = (pa-coef)*(pb-coef); inslastexp(c, vc, coef); pb = pb-next; pa = pa-next; return c;/=输出多项式=void printpolyn(expressiontype c) eplink p; vlink q; p = c.head-next; int count = 0; while(p) if(count = 0) printf(%.2f, p-coef); else if(p-coef 0) printf(+%.2f, p-coef); else printf(%.2f, p-coef); count+; q = p-expre.head-next; while(q) printf(%c%.2f, q-data.varible, q-data.expn); q = q-next; p = p-next; coutendl;/= inputpolyn =int main() expressiontype a, b, c,a1,b1,c1,d; /定义三个多项式 initexpression(a); /初始化a，b两个多项式 initexpression(b); initexpression(a1); initexpression(b1); a.symbol = a; /多项式的名字 b.symbol = b; a1.symbol= d; b1.symbol= e; vartype v1, v2, v3,v4,v5,v6; /定义三个子链表 initvar(v1); /初始化三个子链表 initvar(v2); initvar(v3); initvar(v4); initvar(v5); initvar(v6); vartype v7,v8,v9,v10,v11,v12; initvar(v7); /初始化三个子链表 initvar(v8); initvar(v9); initvar(v10); initvar(v11); initvar(v12);/=输入数据 测试方案一 = elemtype data22; printf(n); data0.varible = a; data0.expn = 2; data1.varible = b; data1.expn = 1; data2.varible = b; data2.expn = 2; data3.varible = b; data3.expn = 4; data4.varible = c; data4.expn = 4; data5.varible= e; data5.expn = 1; data6.varible= e; data6.expn = 6; data7.varible= e; data7.expn= 5; data8.varible= e; data8.expn = 7; data9.varible= f; data9.expn = 9; data10.varible = x; data10.expn = 3; data11.varible = y; data11.expn=8; data12.varible=y; data12.expn = 9; data13.varible=e; data13.expn=8; data14.varible=q; data14.expn=8; data15.varible = x; data15.expn = 6; data16.varible = d; data16.expn = 7; data17.varible = q; data17.expn = 10; data18.varible = d; data18.expn = 10; data19.varible = x; data19.expn = 10; data20.varible = x; data20.expn = 1; inslastvar(v1, data0); inslastvar(v1, data1); inslastvar(v2, data0); inslastvar(v2, data4); inslastexp(a, v1, 5); inslastexp(a, v2, 6); inslastvar(v4, data0); inslastvar(v4, data2); inslastvar(v5, data6); inslastvar(v5, data3); inslastvar(v6, data8); inslastexp(b, v4, 6); inslastexp(b, v5, 7); inslastexp(b, v6, 8); inslastvar(v7, data10); inslastvar(v7, data7); inslastvar(v8, data19); inslastvar(v8, data12); inslastvar(v9, data13); inslastvar(v9, data20); inslastvar(v10, data13); inslastvar(v10, data15); inslastvar(v11, data16); inslastvar(v11, data9); inslastexp(a1, v7, 5); inslastexp(a1, v8, 9); inslastexp(a1, v9, 20); inslastexp(b1, v10, 5); inslastexp(b1, v11, 10); setconsoletextattribute(getstdhandle(std_output_handle),foreground_intensity |foreground_blue); printf(=测试n元多项式乘法函数=n); printf(n); setconsoletextattribute(getstdhandle(std_output_handle),foreground_intensity | foreground_red); printf(多项式a为：n); setconsoletextattribute(getstdhandle(std_output_handle),foreground_intensity | foreground_red | foreground_blue); printpolyn(a); printf(n); setconsoletextattribute(getstdhandle(std_output_handle),foreground_intensity | foreground_red); printf(多项式b为：n); setconsoletextattribute(getstdhandle(std_output_handle),foreground_intensity | foreground_red | foreground_blue); printpolyn(b); printf(n); setconsoletextattribute(getstdhandle(std_output_handle),foreground_intensity | foreground_red); printf(多项式d为：n); setconsoletextattribute(getstdhandle(std_output_handle),foreground_intensity | foreground_red | foreground_blue); printpolyn(a1); printf(n); setconsoletextattribute(getstdhandle(std_output_handle),foreground_intensity | foreground_red); printf(多项式e为：n); setconsoletextattribute(getstdhandle(std_output_handle),foreground_intensity | foreground_red | foreground_blue); printpolyn(b1); printf(n); c = multexpression(a, b); setconsoletextattribute(getstdhandle(std_output_han