[电脑基础知识]数据结构5.pptVIP

第五章 数组和广义表 5.1 数组的定义 5.2 数组的顺序表示和实现 5.3 矩阵的压缩存储 5.3.1 特殊矩阵 5.3.2 稀疏矩阵 5.4 广义表的定义 5.5 广义表的存储结构 5.1 数组的定义 行（列）优先顺序 多维数组的优先顺序 转置运算算法基本思想 对 M.data从头至尾扫描： 第一次扫描时，将M.data中列号为1的三元组赋值到T.data中 第二次扫描时，将M.data中列号为2的三元组赋值到T.data中 …… 依此类推，直至将M.data所有三元组赋值到T.data中 转置运算算法分析 分析这个算法，主要的工作是在p和col的两个循环中完成的，故算法的时间复杂度为O(nu*tu)，即矩阵的列数和非零元的个数的乘积成正比。而一般传统矩阵的转置算法的时间复杂度为O(nu*mu)。当非零元素的个数t和mu*nu同数量级时，算法transmatrix的时间复杂度为O(mu*nu2)。 三元组顺序表虽然节省了存储空间，但时间复杂度比一般矩阵转置的算法还要复杂，同时还有可能增加算法的难度。因此，此算法仅适用于tm*n的情况。 快速转置算法的基本思想 下面给出另外一种称之为快速转置的算法，其算法思想为：对A扫描一次，按A第二列提供的列号一次确定位置装入B的一个三元组。 具体实施如下：一遍扫描先确定三元组的位置关系，二次扫描由位置关系装入三元组。可见，位置关系是此种算法的关键。 例子 快速转置算法主要步骤 求M中各列非零元个数num[ ] 求M中各列第一个非零元在T.data中的下标pos[ ]; 对M.data进行一次扫描， 遇到col列的第一个非零元三元组时，按pos[col]的位置，将其放至T.data中，当再次遇到col列的非零元三元组时，只须顺序放到col列元素的后面; 快速转置算法图示3 快速转置算法图示4 快速转置算法图示5 快速转置算法图示6 快速转置算法图示7 快速转置算法图示8 快速转置算法图示9 快速转置算法图示10 十字链表 稀疏矩阵的加法 A = A+B 典型题举例 1. 将一个A[1…100, 1…100]的三对角矩阵，按行优先顺序存入一维数组B[1…298]中，A中元素a66,65（即该元素下标i = 66, j = 65）在B数组中的位置K为_______。 A. 198 B. 195 C. 197 典型题举例 2. 下面________属于特殊矩阵。 A. 对角矩阵 B. 上三角矩阵 C. 下三角矩阵 D. 稀疏矩阵 E. 对称矩阵 本章小结 了解数组的两种存储表示方法，并掌握数组在以行为主的存储结构中的地址计算方法。 了解稀疏矩阵压缩存储方法的特点和适用范围，领会以三元组表示稀疏矩阵时进行矩阵运算采用的处理方法。 掌握广义表的结构特点及其存储表示方法，掌握两种结构的链表，学会对非空广义表进行分解的两种分析方法：即可将一个非空广义表分解为表头和表尾两部分或者分解为n个子表。 在经典算法中，不论M(I,k)和N(k,j)的值是否为零，都要进行一次乘法运算，而实际上，这两者有一个值为零时，其乘积也为零。因此，在对稀疏矩阵进行运算时，应免去这种无效操作。 即为求Q的值，只需在M.data和N.data中找到相应的各对元素（即M.data中的j值和N.data中的i值相等的各对元素）相乘即可。 3 0 0 7 0 0 -1 0 -1 -2 0 0 0 0 0 2 M= 0 0 -2 0 -1 0 0 -3 0 0 -1 0 0 0 0 0 0 0 3 0 N= 1 1 3 1 4 7 2 3 -1 3 1 -1 3 2 -2 4 4 2 1 3 -2 1 5 -1 2 3 -3 3 1 -1 4 4 3 方法： 1）形成积矩阵 0 0 -6 21 -3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2）形成矩阵N的num,pot 1 2 3 4 5 num 2 1 1 1 0 pot 1 3 4 5 6 3）计算 对M三元组1第一个开始向后扫描，与第二个三元 组N处理pot[k]到pot[k+1]的一段元素相乘（k为M的列号） (-1)*(-1) 3 0 0 7 0 0 -1 0 -1 -2 0 0 0 0 0 2 M= 0 0 -2