一元多项式运算课程设计报告

课程设计（论文）学 号： 201040410113 课 程 设 计题 目一元多项式的运算教 学 院 计算机学院专 业计算机科学与技术班 级一班姓 名王建国指导教师邓丹君2011年12月 30日课程设计任务书 2011 2012 学年第 1 学期学生姓名： 王建国 专业班级： 10级计科1班 指导教师： 邓丹君 工作部门： 计算机学院 一、课程设计题目一元多项式的运算二、课程设计内容1一元多项式的存储2一元多项式的加法与减法3一元多项式的乘法三、进度安排1、2011年12月19日，设计动员，布置任务2、2011年12月20日到21日，查阅资料，分析、讨论与设计3、2011年12月22日到27日，编写程序，进行调试4、2011年12月28日到29日完成模块联调，进行测试5、2011年12月30日，成果验收，完成设计报告四、基本要求1用C语言实现一元多项式的运算.2利用链表实现一元多项式运算的存储.3该程序具有加法、减法、乘法基本运算功能.4. 程序的各个功能模块要求用函数的形式实现.5. 完成设计任务并书写课程设计报告。目 录一 概述3二 总体方案设计4三 详细设计6四 程序的调试与运行结果说明12五 课程设计总结16参考文献17附录：程序源代码18 一 概述1. 课程设计的目的1理解和掌握该课程中的有关基本概念，程序设计思想和方法。2培养综合运用所学知识独立完成课题的能力。3培养勇于探索、严谨推理、实事求是、有错必改，用实践来检验理论，全方位考虑问题等科学技术人员应具有的素质。4掌握从资料文献、科学实验中获得知识的能力，提高学生从别人经验中找到解决问题的新途径的悟性，初步培养工程意识和创新能力。2. 课程设计的要求1用C语言实现一元多项式的运算.2利用链表实现一元多项式运算的存储.3该程序具有加法、减法、乘法基本运算功能.4. 程序的各个功能模块要求用函数的形式实现.5. 完成设计任务并书写课程设计报告。二 总体方案设计1程序设计对多项式存储的解释与说明：多项式，顾名思义是含有多个单项式的，所以很容易让程序员联想到的是链式单链表，因为链式的单链表比顺序的操作灵活，链式的便于插入和删除。我对多项式的存储思考了很多常见的输入错误，必须要对输入的每个单项式进行校验，符合条件的就存入，反之就删除并提示重新输入，所以我的程序中也是选择链式单链表来存储多项式的，这样就给我程序后期的算法设计带来了很多的好处。头结点coef（0）expn（-1）next如上头结点，是采用的结构体形式，其中大的方面分为两个域，分别为data域和next域，其中data域又是一个嵌套的结构体，里面又分为coef 和expn两个域，而next域是指向下一个结点的指针域。初始化头结点时，我将coef 和expn赋初值为 0 和 -1，因为头结点在整个算法中都没有参与计算，只是起到一个连接的作用，而其指数域expn为 -1 是起标志性的作用。整体设计思路：模仿DOS界面，用命令行来操控整个程序的运行；算法的整体思路：先写命令行函数，然后将一元多项式运算的函数插入到命令行函数中，以达到函数调用的目的；主要特点：可以实现一元多项式的DOS界面命令操控；具体功能：用命令调用函数，以实现一元多项式的存储、相加、相减、相乘的功能，还有显示、销毁、清屏、帮助、退出等命令。2.主要问题解决我所承担的设计工作是实现一元多项式的存储、相加、相减、相乘的功能，而我就想到了模仿DOS界面命令形式，采用命令操作来实现本次课程设计的要求，其中还加入了一些另外的功能，比如DOS界面的帮助、清屏、退出等命令。3.程序的主要模块如上1、2所提到的，我采用的是模仿DOS命令界面来实现多项式的存储以及其相加、相减、相乘等功能。所以我设计的程序模块主要有两大模块，其分别为命令行调用模块和一元多项式的存储、运算模块。3.1命令行调用模块在此模块中，我也使用了结构体来存储相关命令，但这里采用的是顺序的链表，因为在使用命令行函数的时候会有指针偏移寻找相关命令的函数指针，所以用顺序有利益控制循环使用。命令行的节点形式，pCmdName为命令名，pCmdInfo为命令的功能说明，pFun是自定义的一个函数指针内型，也就是存储相关命令的函数指针。*pCmdName*pCmdInfo;pFun命令行顺序表g_CmdInfo然后就写了一个命令行输入函数CmdProc，在此函数里面用while循环来输入相关的命令，用库函数strcmp来核对输入的命令，以达到调用相关命令函数的效果。而相关命令函数里面就调用下面模块中的相关函数。3.2一元多项式的存储、运算模块在此模块中，我使用的链式单链表来存储多项式的，相关的介绍看上面的 1.程序设计 中的详细说明。 此模块主要的几大功能函数为createLink创建链表，printList输出链表，addPolyn相加函数，substractPolyn相减函数，mulPolyn相乘函数。还有相关的辅助函数copyLink复制多项式函数，locateLink核对单项式函数，destroyLink销毁结点函数。copyLinklocateLinkdestroyLinkcreateLinkprintListaddPolynsubstractPolynmulPolyn相关的主要函数和辅助函数之间的联系如上所示。三 详细设计1.一元多项式运算函数设计1.1创建多项式的过程编写此过程中，我采用了链式单链表的形式，固然最后一个区域是指针next域，其中多项式结点中data域里又嵌套了一个结构体，即将data域划分为系数coef和指数expn两个区域。 头结点coef（0）expn（-1）next15 2next 23 5next 17 8NULL这是创建多项式的过程，此多项式为15*x2+23x23+17x8 ，当然了在创建多项式的过程中还有更为细密的校验，如：（在输入的过程中）1.指数为负校验：2.系数为 0 的校验：3.输入指数相同的校验：黑体函数locateLink是一个判断指数是否与多项式中已存在的某项相同。补充： 在校验3之前必须将每次输入的单项式按从小到大的顺序排列，这也为locateLink和下面的相加、相减函数做了简单的铺垫。我采用的遍历发找到每次输入的单项式应在的位置，然后插入。 1.2 多项式输出实现过程在输出之前必须对传入参数指针进行校验：本来一开始我想的是从多项式的第一个结点一次输出，这样很简单啊，可是我发现这样的通用性很差，所以我就想到了先将第一个结点分开输出，然后再依次用循环输出其它结点，这样就大大地提高了此函数的通用效果。同时在输出各结点时，我还对系数、指数进行了讨论，（系数不可能为0）以多项式的第一项系数大于0的情况输出为例，如下：如果指数为0时，只输出系数如果系数和指数都为1时就不用输出1，只输出x如果系数或指数其中一个为1的时候，也不用输出1，其它的照原样输出： 1.3多项式相加过程在两个多项式相加对其进行了保护，将两个多项式分别复制给了另外两个多项式中。同样也对两个多项式进行了校验： 如果校验正确，则进行相加，如下：1. 两个多项式没有指数相同时，算法中结点的变化如下：（“蛇形连接”的尾是“和”的next域，而头就从在“加数”和“被加数”中寻找指数小的项，然后通过指针偏移连接。）2. 两个多项式中如果有指数相同的的项，则先相加存到其中一个多项式， 然后再用上面1的“蛇形连接”的方法连接，不过唯一要注意的就是要将指数相同的项中未被累加存储的那项给跳过，不用连接。3. 但是在指数相同的项相加时还要注意一点，那就核对相加的结果，即对存到其中一个多项式中的项的系数，必须进行非0 的校验。因为两种情况的结点连接方式不同：当然了如果校验不正确，则有：1.4多项式相减过程相减函数就很简单了，就是想将第二个多项式的所有项的系数化为负号，然后再与第一个多项式相加，同样在函数之前使用了“复制copyLink”多项式结点的操作： 补充：黑体函数destroyLink是销毁单链表的函数，是为了释放内存空间的：具体的函数代码如下： 同时destroyLink函数也是命令行DesPolyn调用的主要函数。1.5多项式相乘过程 由于相乘过程中只需用其中一个多项式的每一项依次去乘另一个多项式的每一项，依次形成多项式，并累加到同一个多项式中，这样最后得到了所要的结果了，并及时销毁临时的多项式：2.模仿DOS命令行设计命令行函数中定义的是顺序单链表，第一个域为字符串指针（命令名），第二个域也是字符串指针域（命令功能），第三个域为函数指针域（命令函数）。CreatePolyn创建多项式CreatePolynShowPolyn显示多项式ShowPolynAddPolyn多项式相加AddPolynSubPolyn多项式相减SubPolynMulPolyn多项式相乘MulPolynDesPolyn销毁多项式DesPolynClear清屏操作ClearHelp帮助信息HelpExit退出Exit然后分别写了以上9个函数，并用函数指针执行了对应的函数，随后写了个调用命令的函数CmdProc，在这里面进行循环输入命令字符串，然后用strcmp比较输入的字符串与命令名，如果相同则调用相应函数指针所指向的函数。四 程序的调试与运行结果说明1.程序的源代码：（见附录）2. 程序的调试与运行结果说明：运行结果图片一：说明：第一次输入的命令有误，所以紧接着就是提示语句。在使用Help之后就 显示了该模拟DOS界面内的命令与其功能，而后如果之前没有创建多项式，则你输入的其它要用到多项式的命令都会无效，而且还会给予相应的提示，要我们先创建多项式。随后我创建了两个相同的多项式（1+x），然后把两个多项式显示出来。运行结果图片二：说明：由于界面内容太多，所以我就输入了Clear命令。按下回车后结果如上图。运行结果图片三：说明：虽然上面的采用了Clear清屏操作，但是其不影响原有多项式的内容，所以我有一次显示了原来输入的两个多项式，随后操作了相加、相减、相乘的命令，最后销毁了多项式。如果在销毁多项式之后还想进行操作，就应该再次创建多项式，不然系统会再次提醒你未创建多项式。运行结果图片四：说明：这是未创建多项式之前的错误命令操作，以及退出命令Exit。运行结果图片五：说明：第二次操作，创建了不同的两个多项式，已经其相关命令操作。3.算法的改进设想：最开始想到的创建多项式方法很简单，并没有对多项式进行指数由小到大的排列，最后到多项式相加的时候才发现有点麻烦了，每次都要用两个指针分别从两个多项式的链表的头遍历到尾，找其有没有指数相同的两项，然后对其系数相加。这样就很消耗时间，而且还改变了原有的两个多项式。所以我又写了个“复制函数”，就是将一个多项式复制到另一个里面，已达到保护原有的多项式的作用。而且一早将多项式进行了排序，在相加时将两个原多项式进行“保护”，随后只需要判断两个复制过来的多项式最前面的指数是不是相等，采用“蛇形连接”的方式将两个复制多项式中的结点连接到另一个多项式中。对于相减函数就简单多了，只需将第二个多项式的系数全部变为负数，然后再将其与第一个多项式进行相加。对于相乘的函数，就是采用一般的算法，用其中一个多项式中每一项依次去乘另一个多项式，然后将其都相加起来。对于命令行的函数，由于这个这需要定义一个属于命令行的结构体，里面含有三个内容：1.命令名称；2.命令功能；3.命令名对应的函数指针。再写一个输入命令的函数进行调用相关的命令函数。4.时间复杂度分析：在createPolyn创建多项式的函数中，用了个while对多项式进行指数由小到大的排序，是为后面的相加函数做铺垫。时间复杂度为O(n) 。由于addPolyn函数中采用的是“蛇形连接”，所以其时间复杂度为O(m+n)。由于mulPolyn函数中采用的是用其中一个多项式中每一项依次去乘另一个多项式，所以时间复杂度为O(n*m)。其它的辅助函数，如：输出多项式函数printList、复制多项式函数copyLink、校验输入单项式有没有指数相同的函数locateLink 的时间复杂度都为O(n)。五 课程设计总结1.程序总结：通过这个的课程设计，我进一步的巩固了链式单链表的使用，以及写命令行的大致步骤。而且我已掌握一元多项式所要求的基本算法。我的程序代码完全符合这次的课程要求，我通过模仿DOS命令行的形式来实现一元多项式的具体功能，其中的命令基本上很完善，初步的展现了我对命令行的理解与使用。在一元多项式的算法实现中，也几乎是尽善尽美的，由于整个过程是采用的链式单链表，所以全部输入和输出的过程都有指针或者是数据的校验内容，这样就更加增强了代码的可行性。2.程序进一步设想：我的程序代码满足了这次课程设计的要求，但我想我还没有做到最完美的，因为在一元多项式的运算中应该是有除法的，所以这样就有问题了，那我的程序里面还应该加上指数为负数的操作，也就是除法的间接性实现的步骤。对于一元多项式的除法以及指数为负的运算提出假设：我想应该可以写个一元多项式相除的函数，是乘法函数的逆过程，只不过要在相除之前先确定两者之间的关系是能够除得尽的，不然这样就很麻烦了。3. 对数据结构课程的思考：通过这次课程，我更深入的了解到数据结构这门课程对于程序员来说很重要，因为程序的两大组成成员之一就是数据结构。程序的核心是算法，同时程序的实现也要靠数据结构，所以数据结构也是程序的主要成员，所以说学好数据结构是必须的。参考文献1 谭浩强，C程序设计题解与上机指导（第二版），北京，清华大学出版社，2000年9月。2 严蔚敏 吴伟民 ，数据结构（C语言版），北京，清华大学出版社，2007年3 美 James P.Cohoon ，Jack W.Davidson 著，刘瑞挺 韩毅刚 盛素英 刘海嘉 等译 ， C+ 程序设计（第三版），北京，电子工业出版社，2002年1月4 缪淮扣 顾训穰 沈俊 ，数据结构(C+实现) ，北京，科学出版社，2001年附录：程序源代码#include using namespace std;#include #include #include stdio.htypedef struct float coef;/结点类型 int expn;polynomial;typedef struct LNode polynomial data;/链表类型 struct LNode *next;LNode,*Link;typedef int (*PFUN)();struct CMDINFOconst char *pCmdName;const char *pCmdInfo;PFUN pFun;/*调用的函数*/void createLink(Link &L,int n);void printList(Link L);void addPolyn(Link &pc,Link pa,Link pb);void substractPolyn(Link &pc,Link pa,Link pb);void mulPolyn(Link &pc,Link pa,Link pb);void copyLink(Link &pc,Link pa);int locateLink(Link pa,Link e);void destroyLink(Link &L);/*命令行函数*/void CmdProc(const char *pTitle);int CreatePolyn();int ShowPolyn();int AddPolyn();int SubPolyn();int MulPolyn();int DesPolyn();int Clear();int Help();int Exit();CMDINFO g_CmdInfo = CreatePolyn, 创建多项式, CreatePolyn, ShowPolyn, 显示多项式, ShowPolyn,AddPolyn, 多项式相加, AddPolyn,SubPolyn, 多项式相减, SubPolyn,MulPolyn, 多项式相乘, MulPolyn,DesPolyn, 销毁多项式, DesPolyn,Clear, 清屏操作, Clear,Help, 帮助信息, Help,Exit, 退出, Exit;int g_nCmdSize = sizeof(g_CmdInfo)/sizeof(CMDINFO);Link La = NULL,Lb = NULL;void main() CmdProc(多项式);void CmdProc(const char *pTitle) /Dos界面命令行函数char szCmdBuf50 = ;int i = 0; if(NULL = pTitle)coutxxx空系统 v 2.0endl;elsecoutpTitle系统 v 2.0endl;while(true)cout;cinszCmdBuf;for(i = 0; i g_nCmdSize; i+)if(!strcmp(szCmdBuf, g_CmdInfoi.pCmdName)g_CmdInfoi.pFun();break;if(i = g_nCmdSize)cout您输入的命令有误，请用Help命令查询!endl;int CreatePolyn() /创建多项式if(La != NULL & Lb != NULL) /多项式校验 cout您已经创建了多项式，请使用其它命令!endl;return 0;int n;coutn;createLink(La,n);coutn;createLink(Lb,n);return 0;int ShowPolyn() /显示多项式if(La = NULL | Lb = NULL) /多项式校验 cout您还未创建多项式，请先创建!endl;return 0;cout第一个一元多项式为：endl;printList(La);cout第二个一元多项式为：endl;printList(Lb);return 0;int AddPolyn() /多项式相加Link L;if(La = NULL | Lb = NULL) /多项式校验cout您还未创建多项式，请先创建!endl;return 0;addPolyn(L,La,Lb);cout两个多项式相加后的结果为：endl;printList(L);destroyLink(L);return 0;int SubPolyn() /多项式相减Link L;if(La = NULL | Lb = NULL) /多项式校验cout您还未创建多项式，请先创建!endl;return 0;substractPolyn(L,La,Lb);cout两个多项式相减后的结果为：endl;printList(L);destroyLink(L);return 0;int MulPolyn() /多项式相乘Link L;if(La = NULL | Lb = NULL) /多项式校验 cout您还未创建多项式，请先创建!endl; return 0;mulPolyn(L,La,Lb);cout两个多项式相乘后的结果为：endl;printList(L);destroyLink(L);return 0;int DesPolyn() /销毁多项式if(La = NULL | Lb = NULL) /多项式校验 cout您还未创建多项式，请先创建!endl; return 0;if(La & Lb) destroyLink(La); destroyLink(Lb); cout销毁成功！endl;else cout您还未创建多项式，请先创建!endl;return 0;int Clear() /清屏函数 char a; a = getchar(); system(cls); /system是DOS界面命令行操作函数 cls是清屏命令 ，format d: /q 是格式化D盘命令 cout多项式系统 v 2.0endl; return 0;int Help() /帮助函数int i = 0;int j = 0;int nSize = 0;cout相关命令信息: endl;for(i = 0; i g_nCmdSize; i+) cout g_CmdInfoi.pCmdName;nSize = strlen(g_CmdInfoi.pCmdName);for(j = 0; j 20 - nSize; j+)cout ;coutg_CmdInfoi.pCmdInfonext; while(p) L-next = p-next; delete p; p = L-next; delete L; L = NULL;/*判断指数是否与多项式中已存在的某项相同*/int locateLink(Link L,Link e) Link p; p = L-next; while(p != NULL & (e-data.expn != p-data.expn) p = p-next; if(p = NULL) return 0; else return 1; void createLink(Link &L,int n) /创建链表 Link p,newp; L = new LNode; L-next = NULL; (L-data).expn = -1;/创建头结点 p = L; for(int i = 1; i = n; i+) newp = new LNode;cout请输入第i项的系数和指数:endl;cout(newp-data).coef; cout(newp-data).expn;if(newp-data.expn 0) /指数校验cout您输入有误，指数不允许为负值!next = NULL;p = L;if(newp-data.coef = 0) /系数校验cout系数为零，重新输入!next != NULL) & (p-next-data).expn data).expn) /指数排序p = p-next;if(!locateLink( L, newp) newp-next = p-next; p-next = newp;else cout输入的该项指数与多项式中已存在的某项相同,请重新创建一个正确的多项式next = NULL) /校验 coutnext; /跳过头结点 if(p-data).coef 0 ) if(p-data).expn = 0)coutdata).coef;else if(p-data).coef = 1 & (p-data).expn = 1)coutdata).coef = 1 & (p-data).expn != 1)coutxdata).expn;elseif(p-data).expn = 1 & (p-data).coef != 1)coutdata).coefx;else coutdata).coefxdata).expn; if(p-data).coef data).expn = 0) coutdata).coef; else if(p-data.coef = -1 & p-data.expn = 1) coutdata.coef = -1 & p-data.expn != 1) cout-xdata.expn; else if(p-data.expn = 1) coutdata.coefx; else coutdata).coefxdata).expn; p = p-next; while(p != NULL) if(p-data).coef 0)if(p-data).expn = 0) cout+data).coef;else if(p-data).expn = 1 & (p-data).coef != 1) cout+data).coefdata).expn = 1 & (p-data).coef = 1)coutdata).coef = 1 & (p-data).expn != 1)cout+xdata).expn;else cout+data).coefxdata).expn;if(p-data).coef data).expn = 0) coutdata).coef; else if(p-data.coef = -1 & p-data.expn = 1) coutdata.coef = -1 & p-data.expn != 1) cout-xdata.expn; else if(p-data.expn = 1) coutdata.coefx; else coutdata).coefxdata).expn; p=p-next; coutnext = NULL; r = pc; p = pa; while(p-next != NULL) q = new LNode; q-data.coef = p-next-data.coef; /跳过头结点 q-data.expn = p-next-data.expn; r-next = q; q-next = NULL; r = q; p = p-next; /*将两个一元多项式相加*/void addPolyn(Link &pc,Link pa,Link pb) Link p1,p2,p,pd; /*以下为保护原多项式操作 分别复制到 p1、p2里*/ copyLink(p1,pa); copyLink(p2,pb); pc = new LNode; pc-next = NULL; p = pc; p1 = p1-next; /跳过头结点 p2 = p2-next; while(p1 != NULL & p2 != NULL) /蛇形连接 if(p1-data.expn data.expn) p-next = p1; p = p-next; p1 = p1-next; else if(p1-data.expn p2-data.expn) p-next = p2; p = p-next; p2 = p2-next; else /两结点指数相等 p1-data.coef = p1-data.coef