用指针和数组解决矩阵多项式加减法.doc

. 用指针和数组解决矩阵多项式加减法1 引言11数据结构简介数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关1。一般认为，一个数据结构是由数据元素依据某种逻辑联系组织起来的。对数据元素间逻辑关系的描述称为数据的逻辑结构；数据必须在计算机内存储，数据的存储结构是数据结构的实现形式，是其在计算机内的表示2,3；此外讨论一个数据结构必须同时讨论在该类数据上执行的运算才有意义。 在许多类型的程序的设计中，数据结构的选择是一个基本的设计考虑因素。许多大型系统的构造经验表明，系统实现的困难程度和系统构造的质量都严重的依赖于是否选择了最优的数据结构。许多时候，确定了数据结构后，算法就容易得到了。有些时候事情也会反过来，我们根据特定算法来选择数据结构与之适应。不论哪种情况，选择合适的数据结构都是非常重要的1,4。 选择了数据结构，算法也随之确定，是数据而不是算法是系统构造的关键因素。这种洞见导致了许多种软件设计方法和程序设计语言的出现，面向对象的程序设计语言就是其中之一。12课程设计目的本次课程设计目的是让同学更加熟悉一门计算机重要的课程数据结构。数据结构是计算机科学专业的一门考研科目，又直接涉及计算机的编程语言以及软件设计，因此数据结构这门课程的重要性可见一斑2，在大二下学期开设了这门课是为了让广大的同学更好的学习设计软件的思想甚至为更深层次的算法打好基础，运用不同的数据结构以及各种算法解决实际问题，并且在学习的途中还可以达到熟练编程语言以及计算机存储结构的目的，对以后的软件工程、编译原理、算法学习都是一个很好的铺垫4，所以本次课程设计的意义显得尤为重要。13课程设计内容此次课程设计的题目是运用指针数组解决矩阵多项式的加减法。矩阵多项式的运算一直以来是数据结构的一个经典问题，解决此问题需要充分的利用到指针、结构体、链表的知识，然后加入了矩阵多项式这个限制把难度提升了，解决矩阵的幂需要利用到数组的这一概念。而且在做多项式的加减法时又必须充分考虑到符号问题、系数问题、指数问题的特殊情况，在编写程序同时需要多方面考量设计是否合理，输出是否美观界面是否友好，解决此问题的同时又是对自己的程序语言以及数据结构的一次学习。本次课程设计共分为五章。第一章：引言部分，1.1主要是介绍数据结构总体的概念，重要性，1.2是简介此次课程设计的目的，1.3主要是提出此次课程设计的内容。第二章：开发工具简介，主要是针对我所使用的开发工具Visual Studio 2010，做一个简单的介绍，以及最基础的工程创建编译，让读者对此款工具有个大致的了解。第三章：系统分析与设计，3.1主要是针对该题目进行需求分析，提及所需要的理论知识，数据结构以及需要输出的结果3.2是概要设计，主要是简略的介绍了各功能函数的作用给出系统的总框架图。第四章：算法与数据结构，4.1主要介绍算法思想，以及如何利用该算法解决本次课程设计内容。4.2节介绍关键算法给出核心代码的解析和数据流程图。第五章：系统分析及测试，给出具体测试示例及理论结果,而后比对运行结果,由此说明系统的可靠、正确性。 2 开发工具简介本课程设计采用了微软最新的开发工具，功能极其强大的Visual Studio 2010，无论是从功能上还是界面上都完胜很多教材使用的VC6，或者是VS前几个版本。所以本人也把各个工程投入这个更新的平台上来，的确是提高了工作的效率。Visual Studio 是微软公司推出的开发环境。是目前最流行的 Windows 平台应用程序开发环境。目前已正式发布的是 9.0 版本，也就是 Visual Studio 2008，而在2008年12月份，一个振奋人心的信息传来：微软公布了下一代开发工具和平台“Visual Studio Team System 2010”以及.NET Framework 4.0的相关信息，并透露他们将在2009年底或者2010年正式发布。于是Visual Studio2010正式版在今年与我们见面了，我是一个喜欢新鲜事物的人，于是Visual Studio2010便出现在我的机器上。Visual Studio 2010 与 2008 版本的对比：自从微软于1998年发布Visual Studio 6以来，Visual Studio的IDE已经成为软件开发工具的标杆，很多其他的开发工具，甚至是其他用途的应用程序，都在模仿Visual Studio的IDE。但是，就像我们前面讲过的那样，从Visual Studio 6到Visual Studio 2008，虽然IDE的功能越来越多，但是并没有什么革命性的变化，反倒因为功能太多带来了使用上的不便，导致开发效率低下。程序员们都在期盼一个全新的IDE的出现。 现在，程序员们的梦想在Visual Studio 2010中成为了现实。在Visual Studio 2010中，微软用全新的WPF技术重新打造了它的编辑器，借助WPF的强大功能，新的编辑器可以实现很多以前Visual Studio 2008的IDE根本无法想象的功能，比如代码的无级缩放，多窗口即时更新，文档地图，代码的自动产生等等，这些新的IDE特性都会极大地提高程序员的开发效率。Visual Studio 2010界面友好，以下我来简单的介绍Visual Studio 2010对C+程序的开发过程，当然首先你必须安装好Visual Studio 2010，以及Framework4.0，这些都可以从微软的官方下载，并且微软近期发布了Visual Studio 2010的汉化版，更适合英语水平较弱的程序员使用。打开Visual Studio 2010你会看到以下界面，我的版本是微软发布的中文旗舰版，初始界面如图2.1所示。图2.1 Visual Studio 2010初始界面怎么样，是不是界面非常美观，接下来你需要创建一个工程。这里与VC6.0略有不同，VC6.0可以直接建立CPP文件并且编译，但是VS的后续版本都是基于工程的。所以我们双击-文件-新建-项目,出现创建项目窗口如图2.2所示。图2.2创建项目窗口选中Visual C+，并且选中一个空项目，输入项目名称。因为我们简单的数据结构并不需要MFC等内容的支持，单纯的控制台输出就足够了，然后出现了你建立的空项目，我们注意右边的解决方案资源管理器的内容如图2.3所示。图2.3 解决方案资源管理器我们双击源文件-右键添加-新建项如图2.4所示。图2.4 添加源文件新建项在新建项中选中C+文件并且输入名字，单击确定，如图2.5所示。图2.5 添加CPP文件这样你就可以在新建的工程中写入你的C+代码了，如图2.6所示。当然如果有需要你也可以在资源管理器的头文件中添加.h的文件写入头文件的内容，相比VC6.0更加符合逻辑，也相当美观。图2.6 建立CPP文件后添加代码界面当所有代码都添加完毕后你可以单击编译的按钮如图2.7所示，同时编译器会对你的代码进行编译并反馈结果如图2.8所示，然后出现控制台应用程序。图2.7 编译程序按钮图2.8 错误信息反馈当然通过Visual Studio2010你也可以编写C#,VB,VC+的代码，因为本课程设计没有涉及便不作介绍。我们看到了Visual Studio2010全面的功能和华丽的界面，自此我们的强大的开发工具Visual Studio2010介绍完毕。3 系统分析与设计31需求分析 例如矩阵多项式的题目如下：（已知 f(x)= x3 + x , g(x)= 5x7 + 3x3 + 7x +8 和A=， 求f(A)+g(A), 即 （A3 + A）+(5A7 + 3A3 + 7A +8E). 这里E=。 我需要解决的是矩阵多项式的加，（当然减法也可以同时得到解决），我们必须考虑的问题有两个，首先抛弃矩阵问题单纯的考虑多项式加减，多项式加减实现并不困难，只需要把指数相同的合并系数，指数不同的就按指数的降（升）幂依次排列。就如上文的f(x)= x3 + x , g(x)= 5x7 + 3x3 + 7x +8,相加的结果即为k(x)=5x7+4x3+8x+8。问题的难点在加入矩阵之后，需要充分利用到我们线性代数的内容，加入的矩阵必须有一个约束条件，那就是方阵，不然便无法完成乘幂的运算。譬如将矩阵A定义成：，取指数为2则乘幂后的结果为 ，然后用矩阵代替多项式中的x的n此幂，系数保持不变，减法可以使用同样的思想进行处理，我们所做的工作就是要完成这个目的。32概要设计为了达成此次课程设计的目的我们需要如下的函数：1)建立多项式函数：Polyn CreatePolyn(Polyn head,int m)主要是为了多项式创建一个链表，在结点中写入数据。2)插入功能函数：void Insert(Polyn p,Polyn h)主要是为了实现为结点在指定链表中寻找插入的位置。3）销毁多项式函数：void DestroyPolyn(Polyn p) 当前多项式链表使用之后，销毁链表，释放空间。4）多项式输出功能函数：void PrintPolyn(Polyn P) 按照一定的规则输出矩阵多项式。5）多项式指数比较以及非空判断函数：int compare(Polyn a,Polyn b)比较多项式的指数大小并返回相应数值。6）多项式相加功能函数：Polyn AddPolyn(Polyn pa,Polyn pb) 主要是实现多项式的相加并返回头指针。7）多项式相减功能函数：Polyn SubtractPolyn(Polyn pa,Polyn pb)主要是实现多项式的相加并返回头指针。8）矩阵求幂功能函数：void MatrixPlus(int power,int line)主要是实现矩阵的幂运算并输出结果。针对以上功能函数画出系统总框架图如图3.1所示。MainCreatePolyncompareInsertAddPolynDestroyPolynSubtractPolynPrintPolynMatrixPlus图3.1 系统总框架图4 算法与数据结构41算法思想多项式的运算多次在数据结构问题中出现，需要以链表的知识为基础，只要内存中还有空间，就期望能够存储任意数目的不同多项式。通常情况下我们需要存储的多项式为：A(x)=axn+bxm+cxoCoef Expn Link其中a、b、c等为系数，m、n、o为指数，所以我们需要系数域coef和指数域expn，以及指向下一项的指针link，Node结点可以表示为如图4.1所示。图4.1 Node结点结构示意图以多项式加法情况为例，为了将a,b两个多项式相加，得对多项式进行比较。如果这两项的指数相同，那么把它们的系数相加，并生成一个结果项，然后移动这两个指针，分别指向下一个结点3,6，如图4.2所示。coef：1 expn：0coef：2 expn：8coef：3 expn：14coef：10 expn：6coef：-3 expn：10coef：8 expn：14 Acoef：11 expn：14 B Null D图4.2 a.expn=b.expn示意图如果a的当前项指数小于b的当前项指数，那么生成b的副本项，加入到结果d中，并移动指针指向b的下一项。而a的情况采取同样的操作6，如图4.3所示。coef：1 expn：0coef：2 expn：8coef：3 expn：14coef：10 expn：6coef：-3 expn：10coef：8 expn：14 Acoef：-3 expn：10coef：11 expn：14 B Null D图4.3 a.expnb.expn示意图每次生成一个新结点，设置它的coef域和expn域，并将它加入到d的尾端。等a或b其中一个多项式读完之后，扫描另外一多项式情况。如果没读完则加入d的尾端，释放a和b。减法的过程与之相似。这个基本算法很直观，就是使用流的方法在多项式上移动，要么是复制项，要么就是将其加入到结果中。因此，根据下一对指数是=、的关系，while循环具有三个case语句，可以轻松实现比较的功能。关于矩阵的幂问题，需要用到3个数组，matrix、answer、tempmatrix，matrix用来录入矩阵，answer用来记录矩阵计算结果，tempmatrix协助上述两个矩阵完成矩阵幂运算并把值传入answer，矩阵幂所用到的算法需要参考线性代数关于矩阵的内容。42关键数据结构及数据流程图矩阵的幂问题是被大家认为的难点，需要利用到线性代数的知识，也被我认为是我本次课程设计最精华的部分，所以我在此也对我这段代码做出一个详细的讲解，其代码如下：void MatrixPlus(int power,int line)/定义matrixplus函数/answer初始化for(int i=0;iline;i+)for(int j=0;j1)/赋值的循环power-; /每执行一次幂数自减for(int z=0;zline;z+)/行循环 for(int y=0;yline;y+)/列循环tempmatrixzy=answerzy; /把answer的内容赋值给中间数组 /之后就可以用tempmatrix用作每次的乘幂运算for(int i=0;iline;i+)/自乘的循环for(int k=0;kline;k+)int temp=0;/定义中间变量并初始化for(int j=0;jline;j+) temp=temp+tempmatrixij*matrixjk;/运用线性代数的知识计算每行的元素answerik=temp;/将计算的结果赋值给answer用到的算法思想就是线性代数矩阵乘法的内容。我们给出两个矩阵，然后把第一个矩阵按行划分，第二个矩阵按列划分。然后用行的元素乘以对应列的元素并相加作为新矩阵的一个元素，temp=temp+tempmatrixij*matrixjk;这条语句就是为了实现这个作用，行元素与列元素相乘后存在temp变量中，然后经过循环把temp的结果加进新的行元素乘以列元素，几次累加后就是得出新矩阵的一个元素。然后经过多次循环得出最终的新矩阵，由answer数组记录，然后由循环的方式输出。本来在做这个功能的时候answer输出的数据一直只有第一次的计算是正确的，百思不得其解，为了解决这个问题我用了断点来检测temp，和answer100100,后来发现是每次从输出函数调用matrixplus函数的时候answer没有清空造成的,还保留着上次的数据,所以引入了answer清空的循环,和中间变量tempmatrix来保存中间变量,问题得到解决。此程序的重要数据流程在如下的3个图中列出：1）矩阵的幂（1）功能：矩阵按给定幂指数乘幂。（2）数据流入：输入矩阵以及调用乘幂函数。（3）数据流出：矩阵乘幂后的结果。（4）程序流程图：矩阵乘幂流程图如图4.4所示。（5）测试要点：乘幂结果是否计算正确。开始结束输出结果按给定的矩阵进行乘幂调用矩阵幂函数输入矩阵图4.4 矩阵幂运算流程图2）多项式的加法（1）功能：将两多项式相加。（2）数据流入：输入函数。（3）数据流出：多项式相加后的结果。（4）程序流程图：多项式的加法运算流程图如图4.5所示。（5）测试要点：两多项式是否为空，为空则提示重新输入，否则，运算。开始定义存储结果的空链 r存储多项式1的空链p是否为空是 否是存储多项式2的空链q是否为空直接把q中各项存入r直接把p中各项存入r中否同指数项系数相加后存入r中p,q链是否有不为空 是 否输出存储多项式的和的链r合并同类项结束图4.5 多项式加法运算流程图3）多项式的减法（1）功能：将两多项式相减。（2）数据流入：调用输入函数。（3）数据流出：多项式相减后的结果。（4）程序流程图：多项式的减法运算流程图如图4.6所示。（5）测试要点：两多项式是否为空，为空则提示重新输入，否则，进行运算。开始定义存储结果的空链 r存储多项式1的空链p是否为空是 否是存储多项式2的空链q是否为空否把p中各项系数改变符号后存入r中直接把q中各项存入r同指数项系数相加后存入r中p,q链是否有不为空是 否输出存储多项式的和的链r合并同类项结束图4.6 多项式减法运算流程图5 系统分析及测试为了方便我的验证我只去一个2*2的方阵，因为乘幂运算的运算量非常巨大，这种规格的方阵才在我们人的计算范围。实际上该系统可以运算100*100的方阵，计算能力可见一斑。我选取了矩阵A为，则A2=，A3=，A4=而多项式我们选取f(x)= x4+13x2 +3x , g(x)= 8x3 + 3x2,理论得到的k(x)=f(x)+g(x)=x4+8x3+16x2+3x。h(x)= f(x)-g(x)=x4-8x3+10x2+3x。然后用A的乘幂代替文中x的乘幂部分即可。我们运行程序来看看理论结果与实际结果是否相符，该程序界面友好使用简单，使用中只需要按提示完成操作即可，运行情况如下。1）进入程序，开始界面如图5.1所示。图5.1 开始界面2）按要求输入矩阵的行数，以及每行的元素如图5.2所示。图5.2 输入矩阵的行数及元素3）按系统提示输入多项式a，b的项数以及各项指数和系数，如图5.3所示。图5.3 输入多项式a，b项数以及各项指数系数4）按系统提示输入1，则输出两个矩阵多项式，如图5.4所示：图5.4 输出矩阵多项式a，b5）根据提示按2号操作键则输出多项式a+b，如图5.5所示。图5.5 多项式a+b输出结果6）输入3号操作，则出现多项式a-b的结果，如图5.6所示。图5.6 多项式a-b输出结果8）按4号键则程序退出。经过运行和调试，各部分功能正常，结果输出与理论预测结果一致，则证明了该程序的正确性，界面整洁美观。并能用此程序进行更庞大的方阵计算。6 结束语这次课程设计何老师给我定的题目是矩阵多项式的运算，何老师细致的给我们分析了每个课题用何种数据结构去完成，开始只让我完成加法运算，但是由于时间充裕并且减法在加法的基础上容易实现，所以我同时完成了矩阵多项式的加法以及减法运算。这次课程设计程序编写方面给我感觉最麻烦的在于求矩阵的幂运算上面，多项式的加法和减法编程并不难实现，关键在于如何编好矩阵的幂这个函数并且加到多项式里面并输出出来，为此我查阅了国外的经典教材，从矩阵的乘法加以改进简化就成了我自己的矩阵的幂功能函数，我是分别在VS2010下建立了两个工程，分别通过了多项式的运算以及矩阵的幂两种运算，然后再提取矩阵的幂的运算函数