数据结构(C语言版CHAP5(精品·公开课件).ppt

第五章? ? 数组和广义表 第五章 ??? 数组和广义表 5．1 数 组 5．1 数 组 5．1 数 组 5．1 数 组 5．1 数 组 5．1 数 组 5．1 数 组 5．1 数 组 5．1 数 组 5．1 数 组 5．2 矩阵的压缩存储 5．2 矩阵的压缩存储 5．2 矩阵的压缩存储 5．2 矩阵的压缩存储 5．2 矩阵的压缩存储 5．2 矩阵的压缩存储 5．2 矩阵的压缩存储 5．2 矩阵的压缩存储 5．2 矩阵的压缩存储 5．2 矩阵的压缩存储 5．2 矩阵的压缩存储 5．2 矩阵的压缩存储 5．2 矩阵的压缩存储 5．2 矩阵的压缩存储 5．2 矩阵的压缩存储 5．2 矩阵的压缩存储 5．2 矩阵的压缩存储 5．2 矩阵的压缩存储 5．2 矩阵的压缩存储 5．2 矩阵的压缩存储 5．2 矩阵的压缩存储 5．2 矩阵的压缩存储 5．2 矩阵的压缩存储 5．2 矩阵的压缩存储 5．2 矩阵的压缩存储 5．2 矩阵的压缩存储 第五章 习 题 5．3 广义表 5．3 广义表 5．3 广义表 5．3 广义表 5．3 广义表 5．3 广义表 5．3 广义表 5．3 广义表 第五章 习 题 i j v 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 i j v 3 1 -3 2 5 18 1 3 -3 6 1 15 1 6 15 1 2 12 2 1 12 5 2 18 1 3 9 3 1 9 4 3 24 3 4 24 6 4 -7 4 6 -7 3 6 14 6 3 14 M.data T.data 对M六次扫描完成转置运算 第一次扫描查找第1列元素 第一次扫描结束 第二次扫描结束 第二次扫描查找第2列元素 5．2 矩阵的压缩存储 第三次扫描查找第3列元素 第四次扫描查找第4列元素 第五次扫描查找第5列元素 第六次扫描查找第6列元素 转置运算算法图示 时间复杂度分析 算法的基本操作为将M.data中的三元组赋值到T.data，是在两个循环中完成的，故算法的时间复杂度为O(nu?tu) 我们知道，若用二维数组存储矩阵，转置算法的时间复杂度为O（ mu?nu） 。当非零元的个数tu和矩阵元素个数mu?nu 同数量级时，转置运算算法1的时间复杂度为O（ mu?nu ? nu）。由此可见：在这种情况下，用三元组顺序表存储矩阵，虽然可能节省了存储空间，但时间复杂度提高了，因此算法仅适于tu mu?nu的情况。 该算法效率不高的原因是：对为实现M到T的转置，该算法对M.data进行了多次扫描。能否在对M.data一次扫描的过程中，完成M到T 的转置？ 快速转置算法 下面介绍转置运算算法称为快速转置算法 分析 在M.data中， M的各列非零元对应的三元组是以行为主序存储的，故M的各列非零元对应的三元组存储位置不是“连续”的。然而，M的各列非零元三元组的存储顺序却与各列非零元在M中的顺序一致。 如：M的第一列非零元素是 -3、15，它们对应的三元组在M.data 中的存储顺序也是（3，1，-3）在前（6，1，15）后。 如果能先求得M各列第一个非零元三元组在T.data中的位置，就能在对M.data一次扫描的过程中，完成M到T 的转置： 对M.data一次扫描时， 首先遇到各列的第一个非零元三元组，可按先前求出的位置，将其放至T.data中，当再次遇到各列的非零元三元组时，只须顺序放到对应列元素的后面。 M = 0 12 9 0 0 0 0 0 0 0 0 0 0 0 -3 0 0 0 0 14 0 0 0 24 0 0 0 0 0 18 0 0 0 0 0 15 0 0 -7 0 0 0 i j v 0 1 2 3 4 5 6 7 8 3 1 -3 6 1 15 1 2 12 5 2 18 1 3 9 4 3 24 6 4 -7 3 6 14 M.data 6 7 8 M.mu M.nu M.tu M的各列非零元三元组 的存储顺序与各列 非零元在M中的顺序一致 i j v 0 1