软件课设实验报告

《软件课设实验报告》由会员分享，可在线阅读，更多相关《软件课设实验报告（25页珍藏版）》请在装配图网上搜索。

1、北京信息科技大学计算机软件基础课程设计题 目： 链表多项式运算 学 院： 信息和通信工程学院 专 业： 通信工程专业 学生姓名： 班级/学号 指导老师： 起止时间： 2015年10月至 2015年11月 5日 24 / 2524 / 25任务书题目4链表多项式运算主要内容1、 掌握多项式链式存储结构及运算方法，例如插入、删除、创建等，完成一元多项式加法和乘法运算。2、 根据多项式求和、求积原理，实现多项式的建立、求和、求积、显示、释放，插入排序等功能。例如：输入：5x3+1.2x+4.5x2; -1.2x+1加法结果：14.5x2+5x3;乘法结果：1.2x+3.06x2-0.4x3-6x43

2、、 学会编写DLL函数。4、 掌握C+编程环境的基本调试方法，熟练使用可视化C+编程工具。设计要求1、 上交课程设计的书面材料，要求打印。包括课程设计任务书、主要内容，源程序，对程序的功能进行客观评价，明确指出自己编写了哪些具体函数。2、 上交电子版源程序，包括多项式求和、求积、插入、删除、链表创建、排序等程序。3、自己编写一个求素数函数，把它书写成一个动态链接库形式，并在主函数中调用它。尝试把自己编写的程序写成动态链接库和静态链接库形式（无需上交），并比较以下三种EXE文件的大小。A：调用静态链接库生成的EXE执行文件。B：调用动态链接库生成的EXE执行文件。C：直接调用函数生成的EXE执行

3、文件。主要仪器设备计算机一台，安装Windows XP 操作系统、Microsoft Visual C+ 6.0、MSDN Library。主要参考文献1 侯俊杰. 深入浅出MFC(第二版)M. 武汉：华中科技大学出版社, 2001.2 谭浩强. C程序设计（第二版）M. 北京：清华大学出版社, 1999.3 孟彩霞. 计算机软件基础M. 陕西：西安电子科技大学出版社, 2003.4 严蔚敏, 吴伟民. 数据结构M. 北京：清华大学出版社, 2005.课程设计进度计划（起止时间、工作内容）4 学时 了解课题背景，选题，学习DLL，学习链表的基本概念。4 学时 编写求和程序。4 学时 编写求积程

4、序。4 学时 完善功能，编写排序程序。4 学时 调试程序，答辩。课程设计开始日期第2周周一课程设计完成日期第2周周五课程设计实验室名称计算中心机房地 点健翔桥校区摘要： 用C语言实现一元多项式的运算.利用链表实现一元多项式运算的存储，该程序具有加法、乘法基本运算功能。程序的各个功能模块全部用函数的形式实现。 关键字：多项式 运算 函数 链表内容：1、 根据多项式求和、求积原理以及程序框架，分别编写函数createpoly,polyadd,polymulti,Clearlist,InserNode,实现多项式的建立、求和、求积、显示、释放、插入排序等功能。2、 比较多项式相加运算和归并两个有序表

5、的异同3、 InserNode函数的功能是什么？ 目录 一 概述4二 总体方案设计4三 详细设计6四 程序的调试和运行结果说明12五 课程设计总结13参考文献14附录：程序源代码14一 概述1. 课程设计的目的掌握多项式链式存储结构及运算方法，例如插入、删除、创建等，完成一元多项式加法和乘法运算。2. 课程设计的要求1用C语言实现一元多项式的运算.2利用链表实现一元多项式运算的存储.3该程序具有加法、减法、乘法基本运算功能.4. 程序的各个功能模块要求用函数的形式实现.5. 完成设计任务并书写课程设计报告。二 总体方案设计1程序设计对多项式存储的解释和说明：多项式，顾名思义是含有多个单项式的，

6、所以很容易让程序员联想到的是链式单链表，因为链式的单链表比顺序的操作灵活，链式的便于插入和删除。我对多项式的存储思考了很多常见的输入错误，必须要对输入的每个单项式进行校验，符合条件的就存入，反之就删除并提示重新输入，所以我的程序中也是选择链式单链表来存储多项式的，这样就给我程序后期的算法设计带来了很多的好处。头结点coef（0）expn（-1）next如上头结点，是采用的结构体形式，其中大的方面分为两个域，分别为data域和next域，其中data域又是一个嵌套的结构体，里面又分为coef 和expn两个域，而next域是指向下一个结点的指针域。初始化头结点时，我将coef 和expn赋初值为

7、 0 和 -1，因为头结点在整个算法中都没有参和计算，只是起到一个连接的作用，而其指数域expn为 -1 是起标志性的作用。整体设计思路：模仿DOS界面，用命令行来操控整个程序的运行；算法的整体思路：先写命令行函数，然后将一元多项式运算的函数插入到命令行函数中，以达到函数调用的目的；主要特点：可以实现一元多项式的DOS界面命令操控；具体功能：用命令调用函数，以实现一元多项式的存储、相加、相乘的功能，还有显示、销毁等命令。2.主要问题解决我的设计是实现一元多项式的存储、相加、相乘的功能，而我就想到了模仿DOS界面命令形式，采用命令操作来实现本次课程设计的要求。3.程序的主要模块如上1、2所提到的

8、，我采用的是模仿DOS命令界面来实现多项式的存储以及其相加、相乘等功能。所以我设计的程序模块主要有两大模块，其分别为命令行调用模块和一元多项式的存储、运算模块。3.1命令行调用模块在此模块中，我也使用了结构体来存储相关命令，但这里采用的是顺序的链表，因为在使用命令行函数的时候会有指针偏移寻找相关命令的函数指针，所以用顺序有利益控制循环使用。命令行的节点形式，pCmdName为命令名，pCmdInfo为命令的功能说明，pFun是自定义的一个函数指针内型，也就是存储相关命令的函数指针。*pCmdName*pCmdInfo;pFun命令行顺序表g_CmdInfo然后就写了一个命令行输入函数CmdPr

9、oc，在此函数里面用while循环来输入相关的命令，用库函数strcmp来核对输入的命令，以达到调用相关命令函数的效果。而相关命令函数里面就调用下面模块中的相关函数。3.2一元多项式的存储、运算模块在此模块中，我使用的链式单链表来存储多项式的，相关的介绍看上面的 1.程序设计 中的详细说明。 此模块主要的几大功能函数为createLink创建链表，printList输出链表，addPolyn相加函数，substractPolyn相减函数，mulPolyn相乘函数。还有相关的辅助函数copyLink复制多项式函数，locateLink核对单项式函数，destroyLink销毁结点函数。copyL

10、inklocateLinkdestroyLinkcreateLinkprintListaddPolynsubstractPolynmulPolyn相关的主要函数和辅助函数之间的联系如上所示。 三 详细设计1.一元多项式运算函数设计1.1创建多项式的过程编写此过程中，我采用了链式单链表的形式，固然最后一个区域是指针next域，其中多项式结点中data域里又嵌套了一个结构体，即将data域划分为系数coef和指数expn两个区域。 头结点coef（0）expn（-1）next15 2next 23 5next 17 8NULL这是创建多项式的过程，此多项式为15*x2+23x23+17x8 ，当然

11、了在创建多项式的过程中还有更为细密的校验，如：（在输入的过程中）1.指数为负校验：2.系数为 0 的校验：3.输入指数相同的校验：黑体函数locateLink是一个判断指数是否和多项式中已存在的某项相同。补充： 在校验3之前必须将每次输入的单项式按从小到大的顺序排列，这也为locateLink和下面的相加、相减函数做了简单的铺垫。我采用的遍历发找到每次输入的单项式应在的位置，然后插入。 1.2 多项式输出实现过程在输出之前必须对传入参数指针进行校验：本来一开始我想的是从多项式的第一个结点一次输出，这样很简单啊，可是我发现这样的通用性很差，所以我就想到了先将第一个结点分开输出，然后再依次用循环输

12、出其它结点，这样就大大地提高了此函数的通用效果。同时在输出各结点时，我还对系数、指数进行了讨论，（系数不可能为0）以多项式的第一项系数大于0的情况输出为例，如下：如果指数为0时，只输出系数如果系数和指数都为1时就不用输出1，只输出x如果系数或指数其中一个为1的时候，也不用输出1，其它的照原样输出： 1.3多项式相加过程在两个多项式相加对其进行了保护，将两个多项式分别复制给了另外两个多项式中。同样也对两个多项式进行了校验： 如果校验正确，则进行相加，如下：1. 两个多项式没有指数相同时，算法中结点的变化如下：（“蛇形连接”的尾是“和”的next域，而头就从在“加数”和“被加数”中寻找指数小的项，

13、然后通过指针偏移连接。）2. 两个多项式中如果有指数相同的的项，则先相加存到其中一个多项式， 然后再用上面1的“蛇形连接”的方法连接，不过唯一要注意的就是要将指数相同的项中未被累加存储的那项给跳过，不用连接。3. 但是在指数相同的项相加时还要注意一点，那就核对相加的结果，即对存到其中一个多项式中的项的系数，必须进行非0 的校验。因为两种情况的结点连接方式不同：当然了如果校验不正确，则有： 补充：黑体函数destroyLink是销毁单链表的函数，是为了释放内存空间的：具体的函数代码如下： 同时destroyLink函数也是命令行DesPolyn调用的主要函数。1.5多项式相乘过程 由于相乘过程中

14、只需用其中一个多项式的每一项依次去乘另一个多项式的每一项，依次形成多项式，并累加到同一个多项式中，这样最后得到了所要的结果了，并及时销毁临时的多项式：2.模仿DOS命令行设计命令行函数中定义的是顺序单链表，第一个域为字符串指针（命令名），第二个域也是字符串指针域（命令功能），第三个域为函数指针域（命令函数）。create创建多项式createdisplay显示多项式displayadd多项式相加addcheng多项式相乘cheng/*命令行函数*/void CmdProc(const char *pTitle);int create();int display();int add();int

15、cheng();CMDINFO shuzu = create, 创建多项式, create,display, 显示多项式, display,add, 多项式相加, add,cheng, 多项式相乘, cheng,;int g_nCmdSize = sizeof(shuzu) / sizeof(CMDINFO);Link La = NULL, Lb = NULL;int main()CmdProc(多项式);void CmdProc(const char *pTitle) /Dos界面命令行函数char szCmdBuf50 = ;int i = 0;while (true)cout ;cin

16、szCmdBuf;for (i = 0; i g_nCmdSize; i+)if (!strcmp(szCmdBuf, shuzui.pCmdName)shuzui.pFun();break;用函数指针执行了对应的函数，随后写了个调用命令的函数CmdProc，在这里面进行循环输入命令字符串，然后用strcmp比较输入的字符串和命令名，如果相同则调用相应函数指针所指向的函数。 四 程序的调试和运行结果说明1.程序的源代码：（见附录）2. 程序的调试和运行结果说明：运行结果:3时间复杂度分析：在createPolyn创建多项式的函数中，用了个while对多项式进行指数由小到大的排序，是为后面的相加

17、函数做铺垫。时间复杂度为O(n) 。由于addPolyn函数中采用的是“蛇形连接”，所以其时间复杂度为O(m+n)。由于mulPolyn函数中采用的是用其中一个多项式中每一项依次去乘另一个多项式，所以时间复杂度为O(n*m)。其它的辅助函数，如：输出多项式函数printList、复制多项式函数copyLink、校验输入单项式有没有指数相同的函数locateLink 的时间复杂度都为O(n)。五 课程设计总结1.程序总结：通过这个的课程设计，我进一步的巩固了链式单链表的使用，以及写命令行的大致步骤。而且我已掌握一元多项式所要求的基本算法。我的程序代码完全符合这次的课程要求，我通过模仿DOS命令行

18、的形式来实现一元多项式的具体功能，其中的命令基本上很完善，初步的展现了我对命令行的理解和使用。在一元多项式的算法实现中，也几乎是尽善尽美的，由于整个过程是采用的链式单链表，所以全部输入和输出的过程都有指针或者是数据的校验内容，这样就更加增强了代码的可行性。2.程序进一步设想：我的程序代码满足了这次课程设计的要求，但我想我还没有做到最完美的，因为在一元多项式的运算中应该是有减法和除法的，所以这样就有问题了，那我的程序里面还应该加上指数为负数的操作，也就是除法的间接性实现的步骤。对于一元多项式的除法以及指数为负的运算提出假设：我想应该可以写个一元多项式相除的函数，是乘法函数的逆过程，只不过要在相除

19、之前先确定两者之间的关系是能够除得尽的，不然这样就很麻烦了。3. 对数据结构课程的思考：通过这次课程，我更深入的了解到数据结构这门课程对于程序员来说很重要，因为程序的两大组成成员之一就是数据结构。程序的核心是算法，同时程序的实现也要靠数据结构，所以数据结构也是程序的主要成员，所以说学好数据结构是必须的。参考文献1 谭浩强，C程序设计题解和上机指导（第二版），北京，清华大学出版社，2000年9月。2 严蔚敏 吴伟民 ，数据结构（C语言版），北京，清华大学出版社，2007年3 美 James P.Cohoon ，Jack W.Davidson 著，刘瑞挺 韩毅刚 盛素英 刘海嘉 等译 ， C+ 程

20、序设计（第三版），北京，电子工业出版社，2002年1月4 缪淮扣 顾训穰 沈俊 ，数据结构(C+实现) ，北京，科学出版社，2001年附录：程序源代码#include using namespace std;#include #include #include stdio.htypedef structfloat coef;/结点类型int expn;polynomial;typedef struct LNodepolynomial data;/链表类型struct LNode *next;LNode, *Link;typedef int(*PFUN)();struct CMDINFOcons

21、t 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 mulPolyn(Link &pc, Link pa, Link pb);void copyLink(Link &pc, Link pa);int locateLink(Link pa, Link e);void destroyLink(Link &L);/*命令行函数*/void

22、 CmdProc(const char *pTitle);int create();int display();int add();int cheng();CMDINFO shuzu = create, 创建多项式, create,display, 显示多项式, display,add, 多项式相加, add,cheng, 多项式相乘, cheng,;int g_nCmdSize = sizeof(shuzu) / sizeof(CMDINFO);Link La = NULL, Lb = NULL;int main()CmdProc(多项式);void CmdProc(const char *

23、pTitle) /Dos界面命令行函数char szCmdBuf50 = ;int i = 0;while (true)cout ;cin szCmdBuf;for (i = 0; i g_nCmdSize; i+)if (!strcmp(szCmdBuf, shuzui.pCmdName)shuzui.pFun();break;int create() /创建多项式int n;cout n;createLink(La, n);cout n;createLink(Lb, n);return 0;int display() /显示多项式if (La = NULL | Lb = NULL) /多项

24、式校验cout 您还未创建多项式，请先创建! endl;return 0;cout 第一个一元多项式为： endl;printList(La);cout 第二个一元多项式为： endl;printList(Lb);return 0;int add() /多项式相加Link L;if (La = NULL | Lb = NULL) /多项式校验cout 您还未创建多项式，请先创建! endl;return 0;addPolyn(L, La, Lb);cout 两个多项式相加后的结果为： endl;printList(L);destroyLink(L);return 0;int cheng() /

25、多项式相乘Link L;if (La = NULL | Lb = NULL) /多项式校验cout 您还未创建多项式，请先创建! endl;return 0;mulPolyn(L, La, Lb);cout 两个多项式相乘后的结果为： next;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.e

26、xpn)p = p-next;if (p = NULL)return 0;elsereturn 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 项的系数和指数: (newp-data).coef (newp-data).expn;if (newp-data.expn 0) /指数校验cout 您输入有误，指数不允许

27、为负值! next = NULL;p = L;if (newp-data.coef = 0) /系数校验cout 系数为零，重新输入! next = NULL;p = L;while (p-next != NULL) & (p-next-data).expn data).expn) /指数排序p = p-next;if (!locateLink(L, newp)newp-next = p-next;p-next = newp;elsecout 输入的该项指数和多项式中已存在的某项相同,请重新创建一个正确的多项式 next = NULL) /校验cout next; /跳过头结点if (p-da

28、ta).coef 0)if (p-data).expn = 0)cout data).coef;elseif (p-data).coef = 1 & (p-data).expn = 1)cout data).coef = 1 & (p-data).expn != 1)cout x data).expn;elseif (p-data).expn = 1 & (p-data).coef != 1)cout data).coef x;elsecout data).coef x data).expn;if (p-data).coef data).expn = 0)cout data).coef;els

29、eif (p-data.coef = -1 & p-data.expn = 1)cout data.coef = -1 & p-data.expn != 1)cout -x data.expn;elseif (p-data.expn = 1)cout data.coef x;elsecout data).coef x data).expn;p = p-next;while (p != NULL)if (p-data).coef 0)if (p-data).expn = 0)cout + data).coef;elseif (p-data).expn = 1 & (p-data).coef !=

30、 1)cout + data).coef data).expn = 1 & (p-data).coef = 1)cout data).coef = 1 & (p-data).expn != 1)cout +x data).expn;elsecout + data).coef x data).expn;if (p-data).coef data).expn = 0)cout data).coef;elseif (p-data.coef = -1 & p-data.expn = 1)cout data.coef = -1 & p-data.expn != 1)cout -x data.expn;e

31、lseif (p-data.expn = 1)cout data.coef x;elsecout data).coef x data).expn;p = p-next;cout next = 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,

32、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;elseif (p1-data.expn p2-data.exp

33、n)p-next = p2;p = p-next;p2 = p2-next;else /两结点指数相等p1-data.coef = p1-data.coef + p2-data.coef;if (p1-data.coef != 0) /这个是必须有的,对两个相同多项式相减时有用p-next = p1;p = p-next;p1 = p1-next;p2 = p2-next;elsepd = p1;p1 = p1-next;p2 = p2-next;delete pd;if (p1 != NULL)p-next = p1;if (p2 != NULL)p-next = p2;/*将两个一元多项式

34、相乘*/void mulPolyn(Link &pc, Link pa, Link pb)Link p1, p2, p, pd, newp, t;pc = new LNode;pc-next = NULL;p1 = pa-next; /跳过头结点p2 = pb-next;while (p1 != NULL)pd = new LNode;pd-next = NULL;p = new LNode;p-next = NULL;t = p;while (p2)newp = new LNode;newp-next = NULL;newp-data.coef = p1-data.coef * p2-data.coef;newp-data.expn = p1-data.expn + p2-data.expn;t-next = newp;t = t-next;p2 = p2-next;addPolyn(pd, pc, p);copyLink(pc, pd);p1 = p1-next;p2 = pb-next;destroyLink(p);destroyLink(pd);