数据结构（C清华版）ppt课件.ppt

数据结构（C++版）二;第四章 广义线性表;第四章 广义线性表;第四章 广义线性表;数组的定义;广义线性表——多维数组; a11 a12 … a1n a21 a22 … a2n … … … … am1 am2 … amn;数组的基本操作;数组的基本操作;数组的存储结构与寻址——一维数组;常用的映射方法有两种： 按行优先：先行后列，先存储行号较小的元素，行号相同者先存储列号较小的元素。 按列优先：先列后行，先存储列号较小的元素，列号相同者先存储行号较小的元素。 ;广义线性表——多维数组;广义线性表——多维数组;Loc(aijk ) = Loc(a000) +( i×m2×m3 + j×m3 + k )×c ;矩阵的压缩存储;特殊矩阵的压缩存储——对称矩阵 ;(a) 下三角矩阵 (b) 存储说明 (c) 计算方法;对于下三角中的元素aij（i≥j），在数组SA中的下标k与i、j的关系为：k＝i×(i＋1)/2＋j 。 上三角中的元素aij（i＜j），因为aij＝aji，则访问和它对应的元素aji即可，即：k＝j×(j＋1)/2＋i 。;特殊矩阵的压缩存储——三角矩阵 ;矩阵中任一元素aij在数组中的下标k与i、j的对应关系：;矩阵中任一元素aij在数组中的下标k与i、j的对应关系： ;特殊矩阵的压缩存储——对角矩阵 ;;按行 存储;稀疏矩阵的压缩存储 ;template class T struct element { int row, col; //行号，列号 T item //非零元素值 };;三元组表：将稀疏矩阵的非零元素对应的三元组所构成的集合，按行优先的顺序排列成一个线性表。;稀疏矩阵的压缩存储——三元组顺序表;稀疏矩阵的压缩存储——三元组顺序表;存储结构定义： const int MaxTerm=100; template class T struct SparseMatrix { T data[MaxTerm]; //存储非零元素 int mu, nu, tu; //行数，列数，非零元个数 };;三元组顺序表操作——转置操作;矩阵的压缩存储;三元组顺序表转置算法——算法Ⅰ ;矩阵的压缩存储;矩阵的压缩存储;矩阵的压缩存储;矩阵的压缩存储;矩阵的压缩存储;矩阵的压缩存储;矩阵的压缩存储;矩阵的压缩存储;1. 设置转置后矩阵B的行数、列数和非零元个数； 2. 在B中设置初始存储位置pb； 3. for (col=最小列号; col=最大列号; col++) 3.1 ??A中查找列号为col的三元组； 3.2 交换其行号和列号，存入B中pb位置； 3.3 pb++；;分析：A中第0列的第一个非零元素一定存储在B中下标为0的位置上，该列中其它非零元素应存放在B中后面连续的位置上，那么第1列的第一个非零元素在B中的位置便等于第0列的第一个非零元素在B中的位置加上第0列的非零元素的个数，以此类推。 ;矩阵的压缩存储;引入两个数组作为辅助数据结构： num[nu]：存储矩阵A中某列的非零元素的个数； cpot[nu]：初值表示矩阵A中某列的第一个非零元素在B中的位置。 ; 0 0 15 0 3 22 0 5 -15 1 1 11 1 2 3 2 3 6 4 0 91 空 空 空 闲 闲 闲 ; 0 0 15 0 3 22 0 5 -15 1 1 11 1 2 3 2 3 6 4 0 91 空 空 空 闲 闲 闲 ; 0 0 15 0 3 22 0 5 -15 1 1 11 1 2 3