数据构造课程设计 特殊矩阵运算.docx

数据构造课程设计特殊矩阵运算特殊矩阵运算1.1程序功能简介对特殊矩阵能够在界面上以人们熟悉的方式显示，能够对特殊矩阵进行加法运算和减法运算，矩阵转置。根据要求使用了多种数据构造来求解问题，详细为二维数组和类似图的数据构造。由于题目要求使用多种数据构造，因而分开写了两段程序，均实现了上述要求的功能，下面将分开讲明。先讲明的是用二维数组实现的程序，后讲明的是用图构造实现的程序。1.2关于输入、输出形式及数据范围1.2.1使用二维数组实现的程序输入、输出范围为：-73786976294838206000到73786976294838206000，足以解决绝大多数的矩阵运算问题。1.2.2输入的格式进入程序后首先展现的是功能选择界面，如下列图：此时可通过输入对应功能的数字来选择功能。在此程序中不同功能输入格式不同：选择功能1.矩阵转置时需要输入要进行转置操作的矩阵，首先输入矩阵的行数和列数，以逗号隔开，之后依次按矩阵形式输入矩阵即可，各数值之间以空格隔开。选择功能2.矩阵数乘时需要输入要进行数乘操作的矩阵，此输入格式同上，之后输入一个实数，即要进行数乘的数即可。功能3.矩阵加法与4.矩阵减法输入格式和5.矩阵乘法一样，按上述操作输入两个矩阵即可，需要注意的是矩阵减法默认顺序为先输入的矩阵减去后输入的矩阵。当根据格式输入时能够实现以上功能，但输入错误数据时，例如进行行列数不同的矩阵相加减时则会返回无法操作，请重新输入的提示。详细情况见下文测试部分。1.3.1使用图构造实现的稀疏矩阵运算器程序输入、输出范围同上。1.3.2输入的格式进入程序后首先展现的是功能选择界面，如下列图：选择功能部分输入同上。在进行矩阵输入时采取三元组的形式，这是由于稀疏矩阵的多零元性质。首先输入矩阵的行数、列数、非零元个数，以空格隔开，输入完毕后确认，开场输入各个非零元。输入非零元时按“所在行下标所在列下标值的形式输入，需要注意的是输入时只能从所在行小的开场按顺序输入，不能先输入行数大的数据再输入行数小的数据。2概要设计2.1用二维数组实现的程序的概要设计由于使用二维数组构造实现上述功能较为简单，故全部运算仅由主函数执行，不单写出各个简单的函数。通过switch实现对各个功能的选择。详细如下：Switch(1)：进入矩阵转置功能；Switch(2)：进入矩阵数乘功能；Switch(3)：进入矩阵加法功能；Switch(4)：进入矩阵减法功能；Switch(5)：进入矩阵乘法功能；Switch(6)：结束本程序；各功能中的矩阵都是以二维数组的形式进行存储与运算的，使用完好的存储方式使矩阵运算在设计上更为便捷，而且面对更多不同运算时也不存在因构造限制而导致的功能缺失。相应的，由于存储了完好矩阵，且运算时都是完好矩阵的每个元素都介入，所以运行相对较慢。2.2用图构造实现的程序的概要设计本模块要求设计函数建立稀疏矩阵并初始化，使用三元组构造。在创立稀疏矩阵时，需要设计三元组创立稀疏矩阵，在输入出现错误时，能够对错误进行判别处理，初始化稀疏矩阵都为空值。在对稀疏矩阵进行初始化时，只输入非零元素的值和它所在的所在行及所在列。在对稀疏矩阵输出时，以矩阵的完好形式输出。本程序存储矩阵的形式是非零元与矩阵形状结合，更适应稀疏矩阵的性质，在存储空间和运算速度上都有较大优势，但在设计各个功能时较为复杂，控制矩阵在运算时的行列变换需要进行复杂的判定和双层for循环来赋零值或进行非零值的运算。整体构造由主函数调用各个功能函数，条理明晰，详细如下：流程从运算器的图形界面输出开场，之后进行功能选择，此部分流程同上。中选择功能1.矩阵加法时先调用矩阵创立函数Creat输入矩阵A，调用输出矩阵函数Print_SMatrix()，再重复以上流程输入矩阵B，此时进行判定两矩阵能否相加，再调用矩阵加法函数AddSMatrix(A,B,C,n)进行矩阵加法运算输出结果矩阵C，结束后调用三次Destory_SMatrix()函数销毁矩阵A、B、C，最后返回流程开场处进行下一项任务。功能2矩阵减法流程同功能1矩阵加法。功能3矩阵转置只需输入矩阵A即可进行下一步调用矩阵转置函数TransposeSMatrix()，再输出转置后的矩阵B，销毁矩阵A、B后返回流程开场处进行下一项任务。功能4用来结束程序，在选择功能4后调用break函数跳出switch结束程序。3具体设计3.1二维数组构造的程序的具体设计算法1：矩阵的转置运算：首先是把将要运算的矩阵存放在数组中，矩阵的转置运算，就是把你将要进行运算的A矩阵的行ar和列ac，把A矩阵的行ar作为B矩阵的bc，A矩阵的列ac作为B矩阵的br，这样得到的新矩阵B的行br和列bc就是矩阵A的转置。算法如下：for(i=0;i下一页当前位置：文档视界数据构造课程设计特殊矩阵运算数据构造课程设计特殊矩阵运算算法4：矩阵的减法运算；首先是把将要运算的矩阵存放在数组中，矩阵的减法运算，就是要实现A矩阵与B矩阵进行减法运算。事实上就是A矩阵的每一行ar与B矩阵的每一行br进行减法运算，而得到的一个新的矩阵C的每一行cr就是A矩阵的ar行与B矩阵的br行的差；A矩阵的每一列ac与B矩阵的每一列bc进行减法运算，而得到的一个新的矩阵C的每一列cc就是A矩阵的ac列与B矩阵的bc列的差。这样就实现了A矩阵与B矩阵的减法运算。算法如下：ar=br;ac=bc;for(i=0;i下一页3.2.1主界面的设计：定义两个矩阵：矩阵A=123矩阵B=987456654789321定义两个数组A和B，用于存储矩阵a和矩阵b的值；定义一个数组C，用于存放数组A和数组B相加减后的结果。3.2.2矩阵存储的实现方式：稀疏矩阵的存储比拟浪费空间，所以我们能够定义两个数组A、B，采用压缩存储的方式来对上面的两个矩阵进行存储。详细的方法是，将非零元素的值和它所在的行号、列号作为一个结点存放在一起，这就唯一确定一个非零元素的三元组i、j、v,例如structTriple。将表示稀疏矩阵的非零元素的三元组按行优先的顺序排列，则得到一个其结点均为三元组的线性表rposx。即：以一维数组顺序存放非零元素的行号、列号和数值，行号-1作为结束标志。例如，上面的矩阵a，利用数组A存储后内容为：A0=0，A1=2,A2=3,A3=1,A4=6,A5=5,A6=3,A7=4,A8=7,A9=5,A10=1,A11=9,A12=-1。同理，用数组B存储矩阵b的值。3.2.3稀疏矩阵的加减法实现：主要算法构造分析：1)intCreateMatrix(intAmn,intB50)这是一个将稀疏矩阵转存的函数，类似于顺序存储三元组表。在这个方法中，只要用一个二重循环来判定每个矩阵元素能否为零，若不为零，则将其行、列下标及其值存入到一维数组B中对应的元素。在定义函数的经过中，我们需要定义一个for循环，以完成行和列的转换及存储。在函数的末尾我们定义一个BK=-1，用于结束非零元素的存储。2)intMatrixAdd(intAmax,intBmax,intCmax)这个函数用于实现数组A和数组B的相加，并将其相加的结果存入数组C。这个函数讨论了数组在相加的经过中的几种情况：a、A数组和B数组的行相等且列相等，两者直接相加后存入数组C中。3)intSubSMatrix(intAmax,intBmax,intCmax)这个函数用于实现数组A和数组B的相减，并将其相减的结果存入数组C。这个函数讨论了数组在相减的经过中的几种情况：a、A数组和B数组的行相等且列相等，两者直接相减后存入数组C中。4intTransposeSMatrix(TSMatrix*a,TSMatrix*b)此函数用于实现矩阵的转置，由于转置的本质是矩阵中每个元素的行、列下标互换，因而在做矩阵转置时矩阵B与矩阵A的行、列数和非零元个数都是相等的，只需把A矩阵中的元素在存入B矩阵的经过中将表示每个元素位置的行列数，即i、j互换存入即可得到转置矩阵B。3.2.3模块构造图当前位置：文档视界数据构造课程设计特殊矩阵运算数据构造课程设计特殊矩阵运算4.程序调试4.1二维数组程序的调试二维数组构造的矩阵运算程序比拟好做，因而除了题目要求的加减法和转置外我还做了数乘和乘法功能，最终实现了更为完善的矩阵运算程序在做这个程序的经过中在算法方面并没有碰到难以解决的的问题，所使用的算法都是基础的数组操作和三层下面的循环。花费功夫最多的是格式和界面的设计，这些设计也应用到了下一个以图构造为基础的矩阵运算器程序中。除了矩阵乘法功能的复杂度到达On3外，其他运算功能的复杂度都是On2。4.2图构造程序的调试使用图构造存储稀疏矩阵非常节省空间，但其算法也比二维数组数据构造的要复杂得多。在构建矩阵构造时，在参考了很多资料后觉得只存入非零元，用自动填零的方式输出矩阵很方便，而且非常符合稀疏矩阵的性质，因而决定使用双层构造体存入矩阵的性质及其中非零元的信息，在设计矩阵构造时一开场的构造体并不是最终使用的这种，缺少了非零元位置表，这使得矩阵在输出和运算时偶然会有不方便的地方。消耗最多时间的在于矩阵减法程序的修改。我做的矩阵减法的功能是根据已经做好的矩阵加法的程序进行修改得到的，但在修改时一开场并没注意到赋零值的条件在矩阵减法的算法中有所变化，导致的问题是在最后输出的结果中若存在0减一个非零数的情况就会出现结果为被减数的情况，并且之后进行的运算结果也会变成一个随机的很大的数。屡次修改减法部分的核心算法后结果并没有改变。最后发现是在给相减得到的矩阵C赋零值时循环的部分需要进行一定改动，使用原来的算法会使上述情况在运行时跳过相减运算的判定直接赋值并导致接下来的运算在循环时越界使结果出现奇怪的随机数。在此程序中只要输出和转置功能的复杂度到达了On2，其余函数复杂度都是On。5用户使用讲明5.1二维数组程序的用户使用讲明开场程序后进入选择功能界面，此时只需要输入对应功能的数字编号后输入回车就能够使用该功能，功能选择界面如下：当前位置：文档视界数据构造课程设计特殊矩阵运算数据构造课程设计特殊矩阵运算当前位置：文档视界数据构造课程设计特殊矩阵运算数据构造课程设计特殊矩阵运算