数据结构05-2.ppt

第5章 数组和广义表（Arrays Lists） 5.3 矩阵的压缩存储 二、稀疏矩阵的操作 设计思路： 令：M矩阵中的列变量用col表示； num[ col ]：存放M中第col 列中非0元素个数 cpot[ col ]：存放M中第col列的第一个非0元素的位置 （即b.data中待计算的“恰当”位置所需参考点） 5.4 广义表的定义 2、特点： 有次序性 有长度 有深度 可递归 可共享 5.5 广义表的存储结构 本章小结 * * 5.1 数组的定义 5.2 数组的顺序表示和实现 5.3 矩阵的压缩存储 5.4 广义表的定义 5.5 广义表的存储结构 数组和广义表的特点： 表中元素也是一个线性表，即广义的线性表 重点介绍稀疏矩阵的压缩和相应的操作。 一、稀疏矩阵的压缩存储 二、稀疏矩阵的操作 有4种压缩方式：线性表、十字链表、三元组表、 带辅助向量的三元组表 做加减操作时很方便 做转置操作时很方便 0 12 9 0 0 0 0 0 0 0 0 0 -3 0 0 0 14 0 0 0 24 0 0 0 0 18 0 0 0 0 15 0 0 -7 0 0 0 0 –3 0 0 15 12 0 0 0 18 0 9 0 0 24 0 0 0 0 0 0 0 -7 0 0 14 0 0 0 0 0 0 0 0 0 (6, 4, -7) (6, 1, 15) (5, 2, 18) (4, 3, 24) (3, 5, 14) (3, 1, -3) (1, 3, 9 ) (1, 2, 12) (5, 3, 14) (4, 6, -7) (3, 4, 24) (3, 1, 9) (2, 5, 18) (2, 1, 12) (1, 6, 15) (1, 3, -3) 已知 三 元 组 表 a.data 求 三 元 组 表 b.data 转置后 M T （以转置运算为例） 目的： 转置后 有两种实现转置的方法 压缩转置 快速(压缩)转置 压缩转置的思路：反复扫描a表（记为a.data）中的列序，从j=1～n依次进行转置。 快速转置的思路：依次把a.data中的元素直接送入b.data的恰当位置上（即a.data三元组的p指针不回溯）。 关键：怎样寻找b.data的“恰当”位置？ 已知M 三 元 组 表 a.data 求T 三 元 组 表 b.data ③ (1, 3, -3) ① (2 ,1, 12) ⑥ (2, 5, 18) ② (3, 1, 9) ⑧ (4, 6, -7) ④ (5, 3, 14) ⑦ (1, 6, 15) ⑤ (3, 4, 24) (6, 4, -7) (6, 1, 15) (5, 2, 18) (4, 3, 24) (3, 5, 14) (3, 1, -3) (1, 3, 9 ) (1, 2, 12) 思路：依次把a.data中的元素直接送入b.data的恰当位置上（即M三元组的p指针不回溯）。 p 1 2 3 4 q 3 5 如果能预知M矩阵每一列(即T的每一行)的非零元素个数， 又能很快得知第一个非零元素在b.data中的位置, 则扫描a.data时便可以将每个元素准确定位(因已知若干参考点) 技巧：为实现转置运算，应当按列生成 M 矩阵三元组表的两个辅助向量，让它携带每列的非零元素个数 NUM(i) 以及每列的第一个非零元素在三元组表中的位置POS(i) 等信息。 2 1 1 2 0 2 NUM(i) 7 6 6 5 5 4 3 3 3 1 POS( i ) 2 1 i 计算式：POS(1)＝1 POS(i)＝POS(i-1)+NUM(i-1) 辅助向量的样式： 请注意a.data特征：每列首个非零元素必定先被扫描到。 讨论：求出按列优先的辅助向量后，如何实现快速转置？ 0 1 1 2 2 2 num[col] 6 5 4 3 1 cpot[col] 2 1 col 计算式： cpot(1)＝1 cpot[col] ＝ cpot[col-1] + num[col-1] 3 5 7 8 9 0 12 9 0 0 0