数据结构(C语言版)严蔚敏 吴伟民主编课件第五章(精品·公开课件).pptVIP

第五章 数组 数组可以看成是一种特殊的线性表，即线性表中数据元素本身也是一个线性表 5.1 数组的定义和特点 定义 5.2 数组的顺序存储结构 次序约定 以行序为主序 以列序为主序 5.3 矩阵的压缩存储 对称矩阵 三角矩阵 稀疏矩阵的压缩存储方法 顺序存储结构 三元组表 带辅助行向量的二元组表 求转置矩阵 问题描述：已知一个稀疏矩阵的三元组表，求该矩阵转置矩阵的三元组表 问题分析 一般矩阵转置算法： 十字链表 设行指针数组和列指针数组，分别指向每行、列第一个非零元 结点定义 * 数组特点 数组结构固定 数据元素同构 数组运算 给定一组下标，存取相应的数据元素 给定一组下标，修改数据元素的值 〔 〕 〔 〕 〔 〕 〔 〕 〔 〕 〔 〕 〔 〕 〔 〕 〔 〕 ┇ am-1,n-1 a0,n-1 a1,n-1 a00 a10 ┇ am-1,0 a01 a11 ┇ am-1,1 a02 a12 ┇ am-1,2 ┅ ┅ ┇ ┅ Am×n＝ a00 a01 …….. a0,n-1 a10 a11 …….. a1,n-1 am-1,0 am-1,1 …….. am-1,n-1 …………………. Loc( aij)=Loc(a00)＋[i×n＋j]×L ??按行序为主序存放 am-1,n-1 …….. am-1,1 am-1,0 ………. a1,n-1 …….. a11 a10 a0,n-1 ……. a01 a00 0 1 n-1 m*n-1 n ??按列序为主序存放 0 1 m-1 m*n-1 m am-1,n-1 …….. a1,n-1 a0,n-1 ………. am-1，1 …….. a11 a01 am-1，0 ……. a10 a00 a00 a01 …….. a0,n-1 a10 a11 …….. a1,n-1 am-1,0 am-1,1 …….. am-1,n-1 Loc( aij)=Loc(a00)＋[j×m＋i]×L a11 a12 …. … ….. a1n a21 a22 …….. ……. a2n an1 an2 …….. ann …………………. a11 a21 a22 a31 a32 an,1 an,n …... …... k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1 按行序为主序： a11 0 0 …….. 0 a21 a22 0 …….. 0 an1 an2 an3…….. ann …………………. 0 Loc(aij)=Loc(a11)+[( +(j-1)]*L i(i-1) 2 a11 a21 a22 a31 a32 an1 ann …... …... k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1 按行序为主序： 对角矩阵 a11 a12 0 …………… . 0 a21 a22 a