第五章 数组和 广义表 数组 稀疏矩阵 广义表

数 组 一维数组 定义 相同类型的数据元素的集合。 一维数组的示例 0 1 2 3 4 5 6 7 8 9 数 组 一维数组 定义 相同类型的数据元素的集合。 一维数组的示例 0 1 2 3 4 5 6 7 8 9 35 27 49 18 60 54 77 83 41 02

数组的定义和初始化 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++; }

LOC(i) = LOC(i-1)+l = a+i*l LOC(i) = LOC(i-1)+l = a+i*l, i > 0 一维数组存储方式 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 ( i, j ) = a + ( i * m + j ) * l 行优先存放： 设数组开始存放位置 LOC( 0, 0 ) = a, 每个元素占用 l 个存储单元 LOC ( i, j ) = a + ( i * m + j ) * l

三维数组 各维元素个数为 m1, m2, m3 LOC ( i1, i2, i3 ) = a + （按页/行/列存放） LOC ( i1, i2, i3 ) = a + ( i1* m2 * m3 + i2* m3 + i3 ) * l 前i1页总 元素个数 第i1页的 前i2行总元素个数

( i1*m2*m3*…*mn + i2*m3*m4*…*mn+ + ……+ in-1*mn + in ) * l 各维元素个数为 m1, m2, m3, …, mn 下标为 i1, i2, i3, …, in 的数组元素的存储地址： LOC ( i1, i2, …, in ) = a + ( i1*m2*m3*…*mn + i2*m3*m4*…*mn+ + ……+ in-1*mn + in ) * l

行向量 下标 i 页向量 下标 i 列向量 下标 j 行向量 下标 j 列向量 下标 k 二维数组 三维数组 行向量 下标 i 页向量 下标 i 列向量 下标 j 行向量 下标 j 列向量 下标 k

特殊矩阵的压缩存储 特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵。 特殊矩阵的压缩存储主要是针对阶数很高的特殊矩阵。为节省存储空间，对可以不存储的元素，如零元素或对称元素，不再存储。 对称矩阵 三对角矩阵

对称矩阵的压缩存储 设有一个 nn 的对称矩阵 A。 在矩阵中，aij = aji

把它们按行存放于一个一维数组 B 中，称之为对称矩阵 A 的压缩存储方式。 为节约存储空间，只存对角线及对角线以上的元素，或者只存对角线及对角线以下的元素。前者称为上三角矩阵，后者称为下三角矩阵。 把它们按行存放于一个一维数组 B 中，称之为对称矩阵 A 的压缩存储方式。 数组 B 共有 n + ( n - 1 ) +  + 1 = n*(n+1)/2 个元素。

上三角矩阵 下三角矩阵

下三角矩阵 B a00 a10 a11 a20 a21 a22 a30 a31 a32 …… an-1n-1 若 i  j, 数组元素A[i][j]在数组B中的存放位置为 1 + 2 +  + i + j = (i + 1)* i / 2 + j 前i行元素总数 第i行第j个元素前元素个数

若 i < j，数组元素 A[i][j] 在矩阵的上三角部分, 在数组 B 中没有存放，可以找它的对称元素A[j][i]：= j 若 i < j，数组元素 A[i][j] 在矩阵的上三角部分, 在数组 B 中没有存放，可以找它的对称元素A[j][i]：= j *(j +1) / 2 + i

上三角矩阵 n = 4 0 1 2 3 4 5 6 7 8 9 B a00 a01 a02 a03 a11 a12 a13 a22 a23 a33 若i  j，数组元素A[i][j]在数组B中的存放位置为 n + (n-1) + (n-2) +  + (n-i+1) + j-i 前i行元素总数 第i行第j个元素前元素个数

若 i  j，数组元素A[i][j]在数组B中的存放位置为 n + (n-1) + (n-2) +  + (n-i+1) + j-i = = (2*n-i+1) * i / 2 + j-i = = (2*n-i-1) * i / 2 + j 若i > j，数组元素A[i][j]在矩阵的下三角部分，在数组 B 中没有存放。因此，找它的对称元素A[j][i]。 A[j][i]在数组 B 的第 (2*n-j-1) * j / 2 + i 的位置中找到。

三对角矩阵的压缩存储 B a00 a01 a10 a11 a12 a21 a22 a23 … an-1n-2 an-1n-1 0 1 2 3 4 5 6 7 8 9 10 B a00 a01 a10 a11 a12 a21 a22 a23 … an-1n-2 an-1n-1

三对角矩阵中除主对角线及在主对角线上 下最临近的两条对角线上的元素外，所有其它元素均为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) 非零元素个数远远少于矩阵元素个数

稀疏矩阵的抽象数据类型 template<class Type> class SparseMatrix; template<class Type> class Trituple { //三元组 friend class SparseMatrix <Type> private: int row, col; //非零元素行号/列号 Type value; //非零元素的值 } template <class Type> class SparseMatrix { //稀疏矩阵类定义

int Rows, Cols, Terms; //行/列/非零元素数 Trituple<Type> smArray[MaxTerms]; public: //三元组表 SparseMatrix (int MaxRow, int Maxcol); SparseMatrix<Type>& Transpose (SparseMatrix<Type>&); //转置 SparseMatrix<Type>& Add (SparseMatrix <Type> a, SparseMatrix<Type> b); //相加 SparseMatrix<Type>& Multiply(SparseMatrix <Type> a, SparseMatrix<Type> b); //相乘 }

稀疏矩阵

转置矩阵

假设以三元顺序存储结构来表示三元表，可得稀疏矩阵的一种压缩存储方式——三元组顺序表。 //------稀疏矩阵的三元组顺序表存储表示-----//

#define MAXSIZE 12500//假设非零元素////的个数的最大值为12500 Typedef struct { int i,j; //该非零元素的行下标和列下标 ElemType e; } Triple; Typedef struct{ Triple data[MAXSIZE+1];; int mu,nu,tu;//矩阵的行数、列数和非零元素个数 }TSMatrix;

两个矩阵实现转制: (1)将矩阵的行列值相互交换; (2)将每个三元组的i和j相互调换; (3)重排三元组之间的次序便可实现矩阵的转制.

按照b. data中三元组次序依次在a. data中找到相应的三元组进行转换. 换句话说,按照矩阵的M的列序来进行转制 按照b.data中三元组次序依次在a.data中找到相应的三元组进行转换.换句话说,按照矩阵的M的列序来进行转制.为了找到M的每一列所有的非零元素,需要对其三元组标的a.data从第一行起整个扫描一遍,由于a.data是以M的行序为主序来存放每个非零元的,由此得到的恰是b.data应有的顺序.

Status TransposeSmtrix(TSMatrix M,TSMatrix &T){ T.mu=M.nu; T.nu=M.nu; T.tu=M.tu; if(T.tu){ q=1; for(col=1;col<=M.nu;++col) for(p=1;p<=M.tu;++p) if(M.data[p].j==col){ T.data[q].i=M.data[p].j; T.data[q].j=M.data[p].i; T.data[q].e=M.data[p].e; ++q; }

广义表 (General Lists ) 限序列，记作 LS = (a0, a1, a2, …, an-1) LS是表名，ai是表元素，它可以是表 (称 为子表)，可以是数据元素(称为原子)。 n为表的长度。n = 0 的广义表为空表。 n > 0时，表的第一个表元素称为广义表 的表头(head)，除此之外，其它表元素组 成的表称为广义表的表尾(tail)。

例如 A=( ); //A是一个空表 B=(e); //表B有一个原子 C=(a,(b,c,d)); //两个元素为原子a和子表 (b,c,d) D=(A,B,C); //有三个元素均为列表 E=(a,E); //递归的列表

从上述定义和例子可推出列表的3个重要结论: (1)列表的元素可以是子表,而子表的元素还可以是子表 (2)列表可为其他列表所共享. (3)列表可以是一个递归的表,即列表也可以是其本身的一个子表.

GetHead(B)=e,GetTail(B)=() GetHead(D)=A;GetTail(D)=(B,C), 值得提醒的是列表()和(())不同.前者为空表,长度n=0;后者长度n=1,可分解得到其表头,可分解得到其表头,表尾均为空表().

广义表存储结构 表结点 Tag=1 hp tp 原子结点 Tag=0 atom typedef struct GLNode{ int tag; union{ char atom; struct {structGLNode hp,*yp;}ptr; }; }

方法一 A=NIL E  1 D B C 0 e 0 a 0 b 0 c 0 d

方法二 E  1 D B C 0 a 0 e 0 b 0 c 0 d A