北方民族大学数据结构与算法课件第五章 数组与广义表.ppt

数组和广义表 数组 稀疏矩阵 广义表 数 组 定义 相同类型的数据元素的集合。 一维数组的示例 数组的定义和初始化 main ( ) { int a1[3] = { 3, 5, 7 }, *elem; for ( int i = 0; i 3; i++ ) printf ( “%d”, a1[i], “\n” ); //静态数组 elem = a1; for ( int i = 0; i 3; i++ ) { printf ( “%d”, *elem, “\n” ); //动态数组 elem++; } } 一维数组存储方式  三维数组 各维元素个数为 m1, m2, m3 下标为 i1, i2, i3的数组元素的存储地址： （按页/行/列存放） n 维数组 各维元素个数为 m1, m2, m3, …, mn 下标为 i1, i2, i3, …, in 的数组元素的存储地址： 行向量 下标 i 页向量 下标 i 列向量 下标 j 行向量 下标 j 列向量 下标 k 特殊矩阵的压缩存储 特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵。 特殊矩阵的压缩存储主要是针对阶数很高的特殊矩阵。为节省存储空间，对可以不存储的元素，如零元素或对称元素，不再存储。 对称矩阵 三对角矩阵 对称矩阵的压缩存储 设有一个 n?n 的对称矩阵 A。 为节约存储空间，只存对角线及对角线以上的元素，或者只存对角线及对角线以下的元素。前者称为上三角矩阵，后者称为下三角矩阵。 把它们按行存放于一个一维数组 B 中，称之为对称矩阵 A 的压缩存储方式。 数组 B 共有 n + ( n - 1 ) + ??? + 1 = n*(n+1)/2 个元素。 三对角矩阵的压缩存储 三对角矩阵中除主对角线及在主对角线上 下最临近的两条对角线上的元素外，所有其它元素均为0。总共有3n-2个非零元素。 将三对角矩阵A中三条对角线上的元素按行存放在一维数组 B 中，且a00存放于B[0]。 在三条对角线上的元素aij 满足 0 ? i ? n-1, i-1 ? j ? i+1 在一维数组 B 中 A[i][j] 在第 i 行，它前面有 3*i-1 个非零元素, 在本行中第 j 列前面有 j-i+1 个，所以元素 A[i][j] 在 B 中位置为 k = 2*i + j。 稀疏矩阵 (Sparse Matrix) 用三元组表表示的稀疏矩阵及其转置 稀疏矩阵转置算法思想 设矩阵列数为 j，对矩阵三元组表扫描j 次。第 k 次检测列号为 k 的项。 第 k 次扫描找寻所有列号为 k 的项，将其行号变列号、列号变行号，顺次存于转置矩阵三元组表。 广义表 (General Lists ) A=( ); //A是一个空表 B=(e); //表B有一个原子 C=(a,(b,c,d)); //两个元素为原子a和子表 (b,c,d) D=(A,B,C); //有三个元素均为列表 E=(a,E); //递归的列表 表结点 * 35 27 49 18 60 54 77 83 41 02 0 1 2 3 4 5 6 7 8 9 一维数组 35 27 49 18 60 54 77 83 41 02 0 1 2 3 4 5 6 7 8 9 l l l l l l l l l l LOC(i) = LOC(i-1)+l = a+i*l LOC(i) = LOC(i-1)+l = a+i*l, i 0 a, i = 0 a+i*l a 二维数组 行优先存放： 设数组开始存放位置 LOC( 0, 0 ) = a, 每个元素占用 l 个存储单元 LOC ( i, j ) = a + ( i * m + j ) * l LOC ( i1, i2, i3 ) = a + ( i1* m2 * m3 + i2* m3 + i3 ) * l 前i1页总 元素个数 第i1页的 前i