数据结构课程设计-数组和链表在矩阵多项式减运算中的应用.doc

数组和链表在矩阵多项式减运算中的应用学生姓名： 指导老师： 摘 要 本次课程设计主要根据课本中介绍的的实现思想及算法编写一个程序，主要实现矩阵多项式的减法运算。以数组、指针、线性链表等相关知识为基础，掌握并熟练运用数组及线性链表。在程序设计中，采用线性链表的形式实现多项式的存储，输入一个多项式中项的系数和指数，就产生一个新的节点，建立起它的右指针，并用头结点指向它，如此建立两个多项式的链表，实现减法运算。另用数组表示一个矩阵，用矩阵代替多项式中的未知量计算两个多项式的相减结果，并进行输出显示结果。这次课程设计的设计内容主要是通过实际的例子和程序来实现课本中所学习的算法的应用。程序设计设计语言采用c+,程序运行平台为windows xp。关键字 数组；线性链表；多项式 目 录1 引言31.1 目的与意义31.2课程设计内容32 开发工具简介53 设计与实现73.1函数及说明73.2数据结构设计73.3流程图设计94 测试114.1运行环境114.2多项式运算介绍114.3运行结果125 结束语13致谢14参考文献 15附录 源程序代码16 1引 言利用计算机进行数据处理是计算机应用的一重要领域。在进行数据处理时，实际需要处理的数据元素一般很多，而这些大量的数据元素都需要存放在计算机中，因此，大量的数据元素按什么结构存放在计算机中，以便提高数据处理的效率，并节省计算机的存储空间，这是进行数据处理的关键问题1。数据结构就是相互之间存在的一种或多种特定关系的数据元素的集合2。本课程设计主要实现矩阵多项式的减法，通过c+语言实现多项式的建立和输出，以及两个多项式相减后的结果输出，其中多项式中的未知量用一个给定矩阵表示。1.1目的与意义本课程设计是为了让同学们了解数据结构的作用和意义，学习算法的分析与应用。设计中主要涉及到线性表的链式存储结构，用线性链表进行数据存储时，每个数据元素用一个结点（node）来存储，一个结点有两个成分域：一个是存放数据元素的data，称为数据域；另一个是存储指向此链表下一个结点的指针next，称为指针域3。这里主要是运用线性链表实现多项式的存储。为插入一个新的数据元素，应生成一个新的结点，在需要插入的位置将指针域的指针指向新结点的数据域，将新结点的指针域指向下一结点的数据域。两个多项式做减法运算，结果按升幂或降幂排列，将要涉及到链表的插入算法。矩阵结构与程序语言中的二维数组结构很相似，我们可以用数组来表示矩阵，用数组进行运算4。数据结构是计算机科学与技术专业、计算机信息管理与应用专业和电子商务的专业的基础课，是十分重要的课程。所有的计算机系统软件和应用软件都要用到各种类型的数据结构。因此，想要更好地运用计算机来解决实际问题，必须学习和掌握好数据结构的有关知识，打好数据结构这门课的扎实基础。1.2课程设计内容编写一个程序，用线性链表实现多项式的存储，并完成两个多项式的减法运算，用矩阵表示多项式中的未知量，用具体的多项式调试实现。第一章引言部分主要介绍了本次课程设计的目的与意义，概述了本次课程设计的主要内容。第二章开发工具简介，主要是针对开发工具visual c+6.0的一些简单介绍，包括使用方法等。第三章主要是对课程设计中涉及的主要函数进行说明，进行数据结构的设计和算法的分析，画出程序流程图 。第四章测试部分简单介绍了测试运行环境和多项式运算介绍，给出具体实例，计算出理论结果，运行程序，得出实际结果并与理论结果相比较，验证程序的可靠性。2 开发工具简介visual c+6.0 是microsoft公司在1998年推出的基于windows 9x和windows nt的优秀集成开发环境。该环境为用户提供了良好的可视化编程环境，程序员可以里利用该开发环境轻松地访问c+源代码编辑器，资源编辑器和使用内部调试器，并且可以创建项目文件。visual c+6.0不仅包括编译器，而且它还包括许多有用组件，通过这些组件的协同工作，可以在visual c+6.0集成环境中轻松地完成创建源文件，编辑资源，以及对程序的编译，连接和调试等各项工作。vc+6.0是windows 95/98、xp或windows nt下的一个应用程序，本身对软硬件没有特殊要求。就是说它对环境的要求与windows 95/98、windows nt要求是一致的。硬件要求：一般在586以上的处理器、16mb以上内存、100mb以上的硬盘。软件要求：windows 95/98或windows nt3.51以上版本。vc+ 6.0系统可以在一张cd盘上，也可以在“visual studio( visual c+、visual foxpro)”等产品的第一张cd盘上。一般都有一个vc的自动安装程序，也可以执行vc6目录下的setup.exe，在安装包的提示下进行，对初学者可采用“典型安装”方式。在安装好vc+ 6.0系统后，有时根据需要添加或删除某些部件，可插入cd盘重新执行setup.exe安装程序，安装程序会检测当前系统安装vc+6.0的足件，用户单击“添加删除”按钮后，在“安装维护”对话框中选定要添加的部件或撤消选定要删除的部件。与一般的应用软件一样，有以下两种启动方式：(1)通过“开始”按钮，选择“程序”菜单，然后打开“microsoft visual studio 6.0中文版”子菜单中的“microsoft visual c+ 6.0 中文版”程序。(2)用户也可以使用命令行启动vc。单击“开始”按钮后选择“运行”命令，在“运行”对话框中输入c:program filesmicrosoft visual studiovc98vc6.exe（按默认盘符和路径安装）即可。如果要新建一个c+源程序，可采取以下的步骤： 在visualc+主窗口的主菜单栏中选择文件命令，然后选择新建命令，屏幕上出现一个新建对话框。单击此对话框的上方的文件，在其下拉菜单中选择“c+source file”项，表示要建立新的c+源程序文件，然后在对话框有半部分的目录文件框中输入准备编辑的源程序文件的存储路径。在上方的文件文本框中输入准备编辑的源程序文件的名字5。单击确定回到visual c+主窗口，程序编辑窗口已激活。 在编辑和保存了程序以后，单击主菜单栏中的组建，在其下拉菜单中选择“编译”命令，屏幕上出现一个对话框，提示是否同意建立一个默认的项目工作区，单击“是”按钮，开始编译。编译通过后，如源程序没有出现错误或警告，则可以进行组建连接，得到.exe可执行文件，单击“执行”命令，程序开始执行。3 设计与实现3.1函数及说明矩阵多项式的减法是类似于一元多项式的减法的运算，它将一元多项式中的未知量用一个具体的矩阵进行表示并参与运算。这里主要采用线性链表的形式实现多项式系数和指数的存储，并用数组表示一个具体的矩阵代替多项式中未知量的输出显示，最终显示出两个矩阵多项式的相减结果。通过键盘输入一个多项式的项数、系数和指数，调用create（）函数，创建一个多项式，再调用函数display（）函数，对所创建的函数进行输出显示。创建好亮哥多项式后，主函数将调用subtration（）函数进行两个多项式的减法运算，然后再分别调用create（）函数和mul（）函数对相减后的多项式重新建立一个线性链表存储并做输出最终的相减结果。程序涉及的主要函数有：create() 创建一个线性链表，用于存储多项式display() 输出显示所创建的多项式subtration() 将两个多项式做减法运算mul() 完成矩阵的幂运算3.2数据结构设计在许多实际应用中，经常会遇到多项式的处理与运算问题。下面通过运用单链表对多项式的表示以及运算进行讨论。设多项式为 pn（x）=anxn+an-1xn-1+a1x+a0在采用链表表示多项式时，对于多项式中每一个非零系数的项构成链表中的一个结点，而对于系数为零的项就不用表示。多项式中非零系数项所构成的结点如图3.1所示。其中数据域有两项：exp（i）表示该项的指数值，coef（i）表示该项的系数。指针域next（i）表示下一个非零系数项的结点序号。exp（i）coef（i）next（i）图3.1 多项式非零系数项的结点结构另外多项式的未知项用矩阵表示，即二维数组。在c+中，二维数组中元素排列的顺序是：按行存放，即在内存中先顺序存放第一行的元素，再存放第二行的元素6。在本程序中，给定一个具体数组，并进行初始化，完成矩阵的幂运算。其相关算法如下。 void mul() int a22=2,0,0,2; /给定2*2矩阵 int c22;int i,j,k; for(i=0;i2;i+) for(j=0;j2;j+) cij=aij; /初始化矩阵c的值，将矩阵a初值赋给cfor(int l=1;lexp;l+) /若指数大于1做矩阵的自乘运算 for(i=0;i2;i+) /矩阵的自乘运算 for(j=0;j2;j+) int temp=0; for(k=0;kexppoint2-exp) /被减式指数大于减式 p1=point1; point1=point1-next;else if(point1-expexp) /被减式的指数小于减式的指数 point2-coef=-point2-coef; p1-next=point2;p2-next=point2-next;point2-next=point1;p1=p1-next;point1=p1-next;point2=p2-next;elsepoint1-coef=point1-coef-point2-coef; /指数相同时的减法 3.3流程图设计矩阵多项式的计算主要包括矩阵的相关运算和多项式的运算。矩阵的运算主要涉及矩阵的幂运算和加减运算，这里主要应用mul（）函数进行矩阵的幂运算。根据上一小节的相关算法，画出矩阵运算的流程图如图3.1所示。开始结束创建矩阵多项式调用mul（）函数进行矩阵幂运算输出计算结果图3.1矩阵运算的流程图多项式的计算，申请结点空间，输入多项式的项数、系数和指数，调用创建函数，创建线性链表l3，l4用来存储两个多项式。用创建的两个多项式做减运算，判断是否有指数相同的两项，若有，则做系数相减，最后将两个多项式相减后的结果放入l3链表中，按升幂顺序排列输出多项式。程序流程图如图3.2所示。开始申请结点空间输入多项式各的系数和指数调用create函数创造多项式调用subtration函数做两个多项式相减判断指数是否相同系数相减输出相减后的多项式结束否是图3.2流程图4 测试4.1 运行环境c+语言实验环境配置要求硬件配置：586以上pc兼容机或品牌机，配有彩色显示器、鼠标、键盘，内存不小于20mb，硬盘自由空间不小于60mb。推荐配置为内存32mb或64mb（或以上），硬盘自由空间为500mb以上。软件配置：1、操作系统：windows 98，windows 2000，windows xp，linux，unix2、集成开发环境：(1)在windows 98，windows 2000，windows xp系统下，主要的开发编译环境有turboc/c+3.0、borland c+3.1、microsoft visual c+6.0、djgpp,其中djgpp是gcc在dos/windows操作系统下的移植。(2)在linux，unix系统下，采用gcc编译环境。本课程设计的测试环境如下： 测试系统: windows xp测试工具: visual c+ 6.0 （中文版）4.2 多项式运算介绍根据上一章介绍的多项式用链表存储的形式，假设两个多项式f（x）和g（x）已经用链表表示，头指针分别为p1和p2，差多项式用另一个链表表示，头指针为p3。多项式相减的运算规则很简单，只要从两个多项式链表的第一个元素结点开始检测，对每一次的检测结果做如下运算：（1）若两个多项式中对应结点的指数值相等，则将它们的系数值相减。如果不为零，则形成一个新节点后链入头指针为p3的链表末尾。然后再检测两个链表中的下一个结点。（2）若两个多项式中对应结点的指数值不相等，则复抄指数值大的那个结点中的指数值与系数值，形成一个新结点后链入头指针为p3的链表末尾。然后再检测指数值小的链表中的当前结点与指数值大的链表中的下一个结点。根据上述多项式的链表表示和相减规则，带入实例，分析结果。已知 f(x)= x(3)+ x , g(x)= 5x(7) + x(3) + 7x 和 ， 求f(a)-g(a), 即 （a(3) + a）-(5a(7) + a(3) + 7a)。根据设计要求，分析程序结果。f(a)-g(a)=-6-5(7) =-4.3运行结果执行sub.exe文件，运行程序，进入显示界面如图4.2所示。图4.2 显示界面根据分析理论结果是用到的具体个例，已知 f(x)= x(3)+ x , g(x)= 5x(7) + x(3) + 7x 和 ， 求f(a)-g(a), 即 （a(3) + a）-(5a(7) + a(3) + 7a)。 输入多项式的项数、系数和指数，输出显示多项式，并输出两个多项式的差多项式。运行结果如图4.3所示。此结果与理论分析结果一致。图4.3 运行结果图5 结束语本次课程设计实现了通过键盘输入多项式的系数和指数输出显示一个多项式，并完成了两个多项式相减运算。用矩阵表示多项式的未知项是通过在程序中给定一个具体矩阵实现，虽然完成矩阵方面的幂运算，但只能实现最终计算结果的输出显示。友好界面的设计也比较欠缺，还有待改进。通过本次数据结构的课程设计，我深刻的体会到专业基础知识的重要性，还有自己的不足。之前在学习c+语言时，由于不是十分认真，掌握、运用并不熟练，对数据结构和算法的理解也不到位。但是经过本次课程设计，我又重新翻阅了一些相关资料，并加以学习，对相关的知识有了进一步了解，由于个人能力有限，在编程的过程中，查阅了很多相关的算法，最终经个人修改完成。虽然程序并不完全是自己编写，功能也并不是很到位，但对我而言还是有很大收获。本次课程设计虽然结束了，但学习还不能停滞不前。在今后的学习中，应该更注重实践，自己多动手编写程序，只有在实际操作中才能发现问题，并想办法解决问题，才能提高编程能力。致 谢在本次课程设计完成的过程中，受到了很多人的帮助。报告的顺利完成，要感谢同学们给予的资料帮助，使我学习到很多知识。在这里还要感谢何锫老师，他以严谨的教学态度，做研究全力以赴的精神，对我课程设计报告的写作给予悉心指导，提出了许多批评建议，使个人的报告得以如期完成，在此致上最真挚的谢意。参考文献1徐士良,葛兵.实用数据结构：c+描述.北京：清华大学出版社, 2006 2严蔚敏，吴伟民.数据结构：c语言版. 北京：清华大学出版社, 19973唐宁九.数据结构与算法分析. 成都：四川大学出版社, 20064廖荣贵，许正宪.数据结构与算法. 北京：清华大学出版社, 20045谭浩强. c+程序设计题解与上机指导. 北京: 清华大学出版社, 20046谭浩强. c+程序设计. 北京: 清华大学出版社, 2004附录 源程序代码/ 程序名称： sub.cpp/ 程序功能：矩阵多项式的减运算/ 程序作者：王沥晨/ 最后修改日期：2010-11-20#includeusing namespace std;struct nodedouble coef;int exp;node *next;node *create(int *a,int n) /构造函数int t,l,i,j;int x40,y40;for(i=0;i2*n;i+)xi=a2*i; /将系数提出yi=a2*i+1; /将指数提出for(i=1;i=0;j-)if(yjt)yj+1=yj;xj+1=xj;elsebreak;yj+1=t;xj+1=l;for(i=0;inext=null;node *s=head;for(i=0;icoef=a2*i; /赋值系数r-exp=a2*i+1; /赋值指数s-next=r;s=r;s-next=null;return head;void display(node *head) /输出显示多项式int i,j;int x22=2,0,0,2; /给定一个2*2矩阵x int e22=1,0,0,1; /单位矩阵node *p=head-next;if(p=null) /判断链表是否为空cout0exp!=0)if(p-coef!=1)coutcoef; for(i=0;i=2;i+) for(j=0;j=2;j+) coutxij; /输出给定2*2矩阵x cout ; cout(exp); else for(i=0;i=2;i+) for(j=0;j=2;j+) coutxij; cout ; cout(exp);elsecoutcoef; for(i=0;i=2;i+) for(j=0;j=2;j+) couteij; /输出单位矩阵 coutnext;if(p!=null)if(p-coef0)cout+;elsecoutnext;node *point2=p2-next;while(point1!=null&point2!=null)if(point1-exppoint2-exp) /被减式指数大于减式p1=point1;point1=point1-next;else if(point1-expexp) /被减式的指数小于减式的指数 /减式的系数前加负号,并将减式插到被减式的前面point2-coef=-point2-coef; p1-next=point2;p2-next=point2-next;point2-next=point1;p1=p1-next;point1=p1-next;point2=p2-next;elsepoint1-coef=point1-coef-point2-coef; /指数相同时的减法！if(point1-coef=0)p1-next=point1-next;delete point1;point1=p1-next;elsep1=point1;point1=point1-next;p2-next=point2-next;delete point2;point2=p2-next;node *p3=point2; /记录跳出来时l2的所在！以便后来l1能把链子挂上！if(point2!=null) /将第二条链子说剩下的按负数输出！while(point2!=n