两一元高次多项式的乘法.doc

Xx学院数据结构与算法课程设计报 告 书课程设计题目 实现任意两个一元高次多项式的乘法运算院系名称计算机科学与技术系专 业 （班 级） 姓 名 （学 号） 指 导 教 师 完 成 时 间 【课题】设计程序以实现任意两个高次多项式的乘法运算。【要求】1所设计的数据结构应尽可能节省空间。2程序的运行时间尽可能少一、问题分析和任务定义： 1.问题描述： 根据对本次设计课题的理解：实现是任意两个高次多项式相乘，可以是一元也可以是多元，在本次设计中针对的是对两个一元高次多项式的相乘。首先高次多项式可以出现两次到多次及两项到多项的多种不同情况；其次存储空间和程序运行时间是矛盾的，必须从中找到最合理的算法使得程序存储空间及运行时间都相对较少。2.输入、输出的形式. 输入多项式时应注意该元之前的数字为系数，其后数字为指数，本程序按提示采用的人机对话的形式输入每一项的系数（实数型）和指数（整型）输出时是以数学表达式的形式输出，如输出相乘后的结（4.3*X5）+(-13*X-3) 3.算法（程序）所能达到的功能 多项式的建立 多项式的相乘 合并同类项 对合并后的多项式按降幂排序 输出最终多项式表达 释放内存4.测试用的数据（注：以下enter代表回车换行）输入两个多项式并相乘：(x+2.5x2+3x3)*(-4x4+5x5) 输出相乘后的结果：12.5X7-5X6-4X5+15X2-12X1在程序中的输入： 2 enter1 enter 1 enter 2.5 enter 2 enter 3 enter -3 enter-4 enter 4 enter 5 enter 5 enter1 enter 1 enter 1.6 enter -5 enter 86 enter 3 enter 在程序中的输出： (12.5*x7)+(-5*x6)+(-4*x5)+(15*x2) +(-12*x1)二、概要设计和数据结构的选择根据对本课题的理解，线性表是一个很好的选择。而线性表有两种可选的存储表示方式，顺序表和链表。考虑到课题要求：所设计的数据结构应尽可能节省空间。若采用顺序存储，需事先分配足够的空间，造成内存空间的浪费；而用链接存储，动态创建新结点以存储多项式的项，就简单的多。所以本设计采用的数据结构是链表。1 算法（程序）中用到的所有各种数据类型的定义本程序设计用到一中结构体和若干中变量的定义如下：1.1 用单链表存储多项式的结点： struct List float data; /系数 int index; /指数 struct List *next; ;/多项式项的数据类型定义1.2 其它主要变量的定义： int testNum; /测试数据的组数 int LA_Num,LB_Num; /多项式A，B中的项数 struct List *la,*lb; /定义两个链表，分别表示要相加的两个多项式中的项 struct List *pa,*pb=NULL;/pa指向存放相乘后的结果 ，pb为空指针指向合并同类项后的结果 struct List *result; /指向合并同类项后按降幂排序后的结果2.程序流程图 流程图说明： 先定义变量并初始相关变量 输入测试数据的组数 分配两多项式的存储空间 调用inputData()建立多项式 A不为空时执行相乘 如果A、B只有一项无须合并直接跳到 否则要进行合并同类项，排序合并后的结果 输出排序后的结果释放内存如果循环次数不大于测试数据组数，跳到进行下一组测试数据图1.流程图Introduce()freeM ()Print()Order()PaAndPb()LaAndLb()inputData() ()main()3程序主要（调用）关系：图2.函数调用图各函数的功能如下：inputData()功能： 完成多项式建立，如输入系数，指数的输入都在此函数中完成。LaAndLb()功能： 完成la中的某项分别与lb中的每一项相乘。PaAndPb()功能： 完成把相乘后的结果进行合并同类项。Order() 功能： 完成最终合并后的结果按降幂排序。Print()功能： 完成把最终排序后的结果以数学表达式的形式输出。freeM ()功能： 完成中间变量所占存储空间的释放。Introduce()功能：输出登陆界面的信息提示。 三、详细设计和编码变量说明： data-多项式系数 index-多项式指数 testNum-测试数据的组数 la-A多项式 lb-B多项式 LA_Num-A多项式的项数 LB_Num-B多项式的项数 pb-用来存放新多项式相加后的结果 pa-A中某项与B中每项相乘后得到的新的多项式 result-指向结果的头指针。 LaLb临时存放相乘结果 在此次设计中用到三个主要函数具体算法描述如下：LaAndLb()：算法描述: 先将A多项式分解，函数LaAndLb()，此函数中有四个参数，分别为A中某项系数：data; A中某项指数：index;B多项式：lb和B多项式的项数：ListB_Num;通过for循环控制使每次传来A的某项与B中的所有项相乘，形成一个新的多项式存放临时指针变量LaLb中。返回主函数。 PaAndPb()：算法描述: 将中产生新的多项式用pa表示，定义一个空链表pb。利用函数PaAndPb() 将多项式pa与pb进行相加。第一次循环是将pa复制到pb中，此后，pa中项与pb中的某项的指数相同，则将两系数相加，如果pb中没有与pa相等的项，则将pa插到pb的末端。Order()：算法描述:经过ListA_Num次循环，pb中存放的是没有排序的结果。函数order()的功能就是用来给结果排序。本函数是通过定义几个中间结构体指针变量,每次使pb中的进行冒泡排序，实现将排好序的链表的头指针赋给result。 四、上机调试下面为调程序遇到的问题和最后实验成功的心得体会：1程序调试遇到的问题：在程序调试中遇到六种问题如下1.1由于输出语句printf()在输出提示语时由于在书写时粗心导致下图3错误：图31.2由于在所有的scanf(%f,&p-data);语句少了&而导致出现下图4情况：图41.3 当输入的测试数据组数超出1时，运行时只能完成第一组测试数据，不能进入下一组测试数据的输入主要是在main()函数中对测试数据的组数在for循环没控制好所致。1.4开始输入的多项式要按降幂输入才能得出正确结果，否则运算结果出错，加了一个struct List *order(struct List *&pb)解决了此问题1.5由于要求界面更美观，现想要求在输出时：整数就输整数，小数输小数。出现以下问题，当在一行输入时，系数和指数之间用空格分隔而出现指数没被接受结果出错如下图5示。加逗号输入解决了，图51.6在输入地一个多项式的项数为1时出现下面图6的问题：图6现想把上图的输出中整数后的0去掉出现下面的问题把printf(%f*x%d)+,q-data,q-index);改为cout(data*xindex)+endl; 式子输出来了但是格式不对出现下图7情况 图7把上面的输出语句改为cout(data*xindex); if(n!=0)cout+;n-;其中n为定义一个全局变量控制n的初值为两个多项式的项数的乘积，每合并一次n-,由于加号总比多项式的项数少一，所以最后把n-1传给print()通过语句if(n!=0)cout+;n-; 控制“+”的输出。最终实现了正确的输出 心得体会1.1 算法的时空分析：（1）、算法的时间复杂度：本程序主要用到一个大循环，内有两个for循环和两个while循环，所以时间复杂度为O(m(2n+2log2n)。（2）、算法的空间复杂度：由于有两个多项式，没个多项式有n个元素，用了两个链表来存放，所以空间复杂度为O(2n).1.2体会：用到链表的程序，需要使用指针，指针虽然可以及节省空间，但是使用多了会给设计程序带来麻烦。如不小心指针指错了位置，可能导致结果的无法输出，或输出错误。就像本程序调试过程中排序如果没指好就会导致排序结果出错。学会计算时间复杂度和空间复杂度。编程时一定要细心，不然错误会很多。你的程序涉及到那些方面在开始编程时最好把有关这方面的知识仔细是的看看，这样对你的编程回有很的帮助。在编程时要养成一个好的编程习惯，这样对你以后从事这方面打下一个良好的基础。通过本次实验巩固了课本的基本知识、熟练运用课程知识。提高我组织数据及编写程序的能力，使我能够根据问题要求和数据对象的特性，学会数据组织的方法，把现实世界中的实际问题在计算机内部表示出来并用软件解决问题， 本次实验大大提高我了对编程的爱好，我发现只要你认认真真的去思考没有你办不到的事情，当我完成了本次实验，心里有一中莫名的自豪感。 五、使用说明输入时按提示输入：首先输入的是一共要测试数据的组数，按回车再输入第一个多项式的项数，按回车输入第二个多项式的项数，按回车输入第1个多项式的系数和指数（每输入一项按一次回车进行下一项的输入），同样的方法输入第2个多项式的系数和指数。按回车，此时输出第1组的测试结果，接下来继续输入下一组测试数据（方法同上），具体见下面运行结果。六、测试结果（见图8）图8七、参考书目自编，数据结构与算法实验和课程设计指导书，本系精品课程建设组。. 严蔚敏等，数据结构题集（c语言），北京清华大学出版社，1999年2月第1版。李春葆，数据结构习题与解析（c语言），北京清华大学出版社，2000年1月第1版。谭浩强 ，c语言程序设计（第三版）， 清华大学出版社 2005年出版。八、附录：带注释的源程序 #include #include #include struct List float data; /系数 int index; /指数 struct List *next; ;/多项式项的数据类型定义 int n=0; /记录合并后的多项式的相数struct List *inputData(int inputNum) /*建立多项式函数*/ struct List *head;/指向链表的头结点 struct List *p;/指向新建结点 int i; /循环控制变量 head=(struct List *)malloc(sizeof(struct List); /建立头结点 p=head;/p指向头结点 printf(系数:); scanf(%f,&p-data); printf(指数:); scanf(%d,&p-index); for(i=inputNum-1;i0;-i) /循环控制输入多项式的每一项 p-next=(struct List *)malloc(sizeof(struct List); /新增结点 p=p-next; printf(系数:); scanf(%f,&p-data); printf(指数:); scanf(%d,&p-index); p-next=NULL; return(head);/返回链表头指针 struct List *LaAndLb(float data,int index,struct List *lb,int LB_Num) /*la中的项分别与lb中的每一项相乘函数*/ struct List *head; /指乡链表的头结点 struct List *LaLb;/存放相乘后的结果 int i; /循环控制变量 LaLb=(struct List *)malloc(sizeof(struct List);/开辟新空间 LaLb-data = data * lb-data; /系数相乘 LaLb-index = index + lb-index; /指数相加 head=LaLb; for(i=1;inext=(struct List *)malloc(sizeof(struct List); lb=lb-next;/Lb指针后移 LaLb=LaLb-next;/新结点接到链表LaLb中 LaLb-data = data * lb-data; /系数相乘 LaLb-index = index + lb-index; /指数相加 LaLb-next=NULL; return(head); /返回相乘后的链表的头指针 struct List *PaAndPb(struct List *pa,struct List *pb,int &n) /*合并同类项函数*/struct List *head;/新建链表的头指针 struct List *p1,*p0,*p2,*p3; head=(struct List *)malloc(sizeof(struct List); /建头结点 if(pb=NULL) head=pa; return(head); / 第一次循环pb为空链表是将la中第一项的值和lb中每项值乘的结果到pb中 else /后来pa中某项与pb中的某项的指数相同，则将两系数相加， / 如果pb中没有与pa相等的项，则将pa插到pb的末端。 head=pb; p2=pa; while(p2) p1=pb; p3=NULL; /指向指数相同的项 while(p1) if(p2-index = p1-index) p3=p1; /指数相同时 p0=p1;/p0存放不能再合并的项 p1=p1-next; if(p3=NULL) /无指数相同时进行插入存到p0所指链表 p0-next=(struct List *)malloc(sizeof(struct List); p0=p0-next; p0-data=p2-data; p0-index=p2-index; p0-next=NULL; else p3-data=p3-data + p2-data; n-;/指数相同系数相加 p2=p2-next; return(head); struct List *order(struct List *pb) /*对最终运算的多项式按降幂排序*/ struct List *head; struct List *p1,*p2,*p,*p3,*p4; /p2指向第一个比较结点p4指向第二个比较点p3指向下一个待比较的结点 p1=(struct List *)malloc(sizeof(struct List); p1-next=(struct List *)malloc(sizeof(struct List); head=(struct List *)malloc(sizeof(struct List); p1-next=pb; /链表pb链接到p1后面 head-next=p1;/p1链接到head后 while(p1-next-next)/pb后存在下一结点执行 p2=p1-next; p3=p2; while(p3-next) p4=p3-next; if(p2-index index)/比较结点的指数大小，如果前者小于后者将其连接到p1的后面 p=p4-next; p1-next=p4; /p1指向指数大的结点 if(p2-next=p4) /两结点相临时指针的交换 p4-next=p2; p3=p4; else /两结点不相临时指针的交换 p4-next=p2-next; p3-next=p2; p2-next=p; /p指向下一个待比较的结点 p2=p1-next; /指向指数的的结点 p3=p3-next; / 如果前者不小于后者不移动将p3指针后移指向下一个要比较的结点 if(!p1-next|!p1-next-next) break; /当待排序的链表中只有1个或0个结点时无需排序 p1=p1-next; p1=head;/p1用来指向当前结点 while(p1-next) p2=p1-next; if(!p2-data) /系数为0时指向下一个结点并释放系数为0的结点的存储空间 p1-next=p2-next; free(p2); if(!p1-next) break; /链表为空结束 else p1=p1-next; /不为空指向下一结点 return(head-next-next); /返回排序好的链表的第2个结点，因为前两个结点是头结点无数据 void print(struct List *head,int n)/*输出链表的函数*/struct List *q;/指向要输出的结点q=head;if(q!=NULL)docout(data*xindex); if(n!=0)coutnext;while(q!=NULL);printf(b);printf( );printf(n); void freeMemory(struct List *&head) /*释放内存函数*/ struct List *p1; p1=head; while(head) p1=head-next; free(head); head=p1; void introduce( ) /*输出提示界面函数*/ printf(t +=设计简介=+n);printf(t 【设计课题】 两高次多项式的乘法 n);printf(t n);printf(t 【输入要求】 1.按提示输入测试数据的组数 n);printf(t 2.按提示输入多项式的项数 n);printf(t 3.按提示输入多项式的系数和指数(负