数据结构与算法课件：数组广义表和串.ppt

压缩存储对于对称矩阵，因为对角线以上及以下的元素对称相等，所以只需要保存其中的一半及对角线上的元素即可对于上三角矩阵或下三角矩阵，仅保存上三角部分或下三角部分的元素，另外一半的零元素不再保存若矩阵有n行n列，则这三种形式下需要保存的元素个数为n?(n+1)/2三角部分?例4-4设有一个10行10列的下三角矩阵A，采用行优先压缩存储方式，保存A中第一个元素a00的地址是100，保存a11的地址是108，则保存元素a44的地址是（）A．115B．156C．160D．212答案为B稀疏矩阵稀疏矩阵该矩阵只有10个非零元素，每个非零元素用一个三元组表示?三元组表三元组表应是一个有序序列，通常按行主序次序排列，即先按行的大小排列，同一行的三元组再按列的大小排列对应前例的三元组表i0012234455j1200521405v891-3121624615-7稀疏矩阵的存储结构typedefstruct{ inti,j; //存储非零元素的下标 ELEMTypev; //存储非零元素的值}triTerm;typedefstruct{ introws,cols; //矩阵的行数、列数 intterms; //非零元素个数 triTermtri[maxSize]; //三元组表}SparseMatrix;输入三元组生成三元组表的程序矩阵转置矩阵转置即是行、列互换，i行的元素放置到i列，这也意味着，j列的元素放置在j行。如果矩阵是n?m的，则转置后得到的矩阵是m?n的很容易想到，将三元组表中的每个三元组项的i与j互换，即可得到转置后矩阵的三元组表但是这样转换后得到的三元组表不再按行主序排列，不便于后续操作的实现所以要实现的矩阵转置程序，必须得到一个按行主序排列的三元组表思路可以像readSparseMatrix函数那样处理，读入原矩阵的一个三元组，插入到目标矩阵的三元组表中可以使用一个临时计数数组，记录原矩阵的每个三元组在目标矩阵的三元组表中的插入位置，以辅助完成转置操作，由此避免了三元组的移动，高效率地实现转置操作不失一般性，设原矩阵A的行数是rows，列数是cols。则转置后矩阵B的行数是cols，列数是rows。三元组的个数没有改变A中处于0列的元素，将是B中处于0行的元素。所以B的三元组表中的最前面的元素，是A中列值为0的元素。接下来是A中列值为1的元素，依此类推，最后是A中列值为cols-1的元素。使用临时数组ColSize来保存统计结果前例中的矩阵，临时数组ColSize内容在B的三元组表中，为各行元素预留位置01234532201201234567890行元素1行元素2行元素4行元素5行元素对于A的三元组(0,1,8)和(4,1,24)，转置后分别为(1,0,8)和(1,4,24)，它们应该保存在上述第二部分，即位置3和位置4中故由ColSize数组中的元素值，从前向后依次相加，得到RowNext的值012345603577810转置算法数组的应用走迷宫是实验心理学中的一个经典问题不失一般性，使用一个m行n列的矩阵maze表示迷宫，让机器人R寻找从maze[0][0]（左上角，入口）到maze[m-1][n-1]（右下角，迷宫的唯一出口）间的可行路径任一时刻，R在迷宫中的位置用行、列号[i][j]来表示，这时它有4个方向可以进行试探，即从图上看是上、下、左、右设下一位置是[g][h]，显然[g][h]的值与走的方向有关若从[i][j]向右走一步，则g=i;h=j+1若向上走一步，则g=i-1;h=j当R走到迷宫边缘时，可以试探的方向不足4个，需要进行边界的判断为了避免过多的边界条件判断，可以把原来表示迷宫的矩阵maze扩大一圈，变成m+2行n+2列，并且令表示边缘的这些矩阵元素全为1编写计算机程序求解迷宫问题，一般采用一步一探查并加回溯的方法。称R所在的位置为当前位置，当R走到一个位置时，除了进入当前位置的方向外，可以在其他3个方向进行探查，选择可行并尚未走过的方向走一步，所处的新位置变为当前位置，并再次探查下一个可行位置；当3个方向都走不通时，只能沿来路退到前一个位置再选择其他方向，这一步骤称为回溯。回溯后的位置又变为当前位置在探查的过程中，因为有回溯，所以可能会走到原来已走过的位置，为避免重复并找出确定的可行路径，需要一个栈记录已走过的每一步的位置及方向，另外还需要设置一个与原来迷宫矩阵同样大小的标志矩阵mark，以