数组和矩阵-Chapter5栈.ppt

数据结构与算法 Chapter4 数组和矩阵 本章教学内容 数组 矩阵 特殊矩阵 稀疏矩阵 4.3 特殊矩阵 方阵：具有相同行数和列数的矩阵 一些常用的特殊方阵 对角矩阵 三对角矩阵 下三角矩阵 上三角矩阵 对称矩阵 对角矩阵：所有非0元素都在对角线上，即当i≠j 时有M(i, j) = 0。 三对角矩阵： | i - j | 1 时有M(i, j ) = 0 下三角矩阵： i j 时有M (i, j ) = 0 上三角矩阵： i j 时有M (i, j ) = 0 对称矩阵： M (i, j ) =M (j, i ) 示例1：对称矩阵 任意两个城市之间的距离可以用一个 6 ×6的矩阵来表示。矩阵的第i行和第i列代表第i个城市，distance (i, j ) 代表城市i和城市j之间的距离。 示例2：上三角矩阵 堆栈折叠问题：选择n个折叠点 把堆栈分解成s个子堆栈；h是第i至第j纸盒所构成的堆栈的高度，h的可能取值是上三角矩阵。 1、对角矩阵的表示 使用二维数组：空间需要n2*sizeof(T) 压缩存储：只存储对角线上的元素 使用一维数组：空间需要n*sizeof(T) M(i,i) =A[i-1] 2、三对角矩阵的表示 只存储三个对角线上的元素（按行存储）； 一维数组空间需要： (3n-2) *sizeof(T) 另外两种存储方法 另外的存储映射方式 3、三角矩阵的表示 下三角矩阵的存储形式 只存储对角线以下的元素： 4、对称矩阵的表示 只存储上三角/下三角部分 存储映射方式参照上三角/下三角矩阵 例如，只存储下三角，按行主次序，则 小结：特殊矩阵压缩存储 课堂练习 课堂练习 4.4 稀疏矩阵 稀疏矩阵（Sparse Matrix）：大量矩阵元素的值为0，且分布没有一定的规律。 稠密矩阵：很少元素为0 结构化的稀疏矩阵 对角矩阵 三对角矩阵 下/上三角矩阵（算不算稀疏？） 非结构化的稀疏矩阵：需要特殊方法 稀疏矩阵的三元组表示 三元组定义 template class T class Term { private: int row, col; T value; }； 稀疏矩阵的存储结构 稀疏矩阵的类定义（程序4-20） 求稀疏矩阵的转置 矩阵转置常规算法 稀疏矩阵快速转置算法 【算法目标】将*this的转置结果存放在矩阵b中； 【算法思想】 若能在转置前求出矩阵*this的每一列col（即b中每一行）的第一个非零元转置后在b. a中的正确位置，则在对this-a的三元组依次作转置时，便可直接放到b.a中的恰当位置上去。 为了确定这些位置，在转置前，应先求得*this的每一列中非零元的个数进而就可求得A的每一列的第一个元素在b.a中应有的位置。 稀疏矩阵快速转置算法的具体做法（程序4-23） 引入两个辅助数组（1） ColSize[ ] ColSize[i]：*this矩阵第i列中的非0元素数（转置矩阵的第i行的非0元素个数）； 稀疏矩阵快速转置算法的具体做法（程序4-23） 引入两个辅助数组（2） RowNext[ ] RowNext[i]：转置矩阵b第i行的下一个非0元素在b中的位置。 稀疏矩阵快速转置算法（程序4-23） templateclass T void sparseMatrixT::transpose(sparseMatrixT b) { // 把*this的转置结果送入b if(termsb.MaxTerms) throw Nomem( ); // 设置转置特征 b.cols = rows; b.rows = cols; b.terms=terms; // 初始化 int* colSize = new int[cols + 1]; int* rowNext = new int[cols + 1]; 稀疏矩阵的链表描述：十字链表 行链表的串接 十字链表：一种描述形式 结点结构： 行链表数组 列链表数组 行列链表的最终组合 本书链表描述 看书提示 书上例子三个ADT之间是引用关系！ 列链表节点 行链表节点 稀疏矩阵的链表定义 稀疏矩阵的构造 课下自学 稀疏矩阵的输出： 注意操作符重载的嵌套使用 稀疏矩阵转置：两步 箱子分配：先行链表、后列链表 箱子收集：稀疏链表的构造 本章小结 二维数组的一维存储 行优先 列优先 一维数组类、二维数组类、Matrix类 特殊矩阵的压缩存储 压缩方法 映射公式 稀疏矩阵 存储方式（三元组顺序表、十字链表） 转置算法 Chapter5 栈（Sta