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

Presentation on theme: "第五章 数组和 广义表 数组 稀疏矩阵 广义表."— Presentation transcript:

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

2 数 组 一维数组 定义 相同类型的数据元素的集合。 一维数组的示例 0 1 2 3 4 5 6 7 8 9
数 组 一维数组 定义 相同类型的数据元素的集合。 一维数组的示例

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

4 LOC(i) = LOC(i-1)+l = a+i*l LOC(i) = LOC(i-1)+l = a+i*l, i > 0
一维数组存储方式 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

5 二维数组 LOC ( i, j ) = a + ( i * m + j ) * l 行优先存放：
设数组开始存放位置 LOC( 0, 0 ) = a, 每个元素占用 l 个存储单元 LOC ( i, j ) = a + ( i * m + j ) * l

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

7 ( 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

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

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

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

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

12 上三角矩阵 下三角矩阵

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

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

15 上三角矩阵 n = 4 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个元素前元素个数

16 若 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 的位置中找到。

17 三对角矩阵的压缩存储 B a00 a01 a10 a11 a12 a21 a22 a23 … an-1n-2 an-1n-1
B a00 a01 a10 a11 a12 a21 a22 a23 … an-1n-2 an-1n-1

18 三对角矩阵中除主对角线及在主对角线上 下最临近的两条对角线上的元素外，所有其它元素均为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。

19 稀疏矩阵 (Sparse Matrix) 非零元素个数远远少于矩阵元素个数

20 稀疏矩阵的抽象数据类型 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 { //稀疏矩阵类定义

21 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); //相乘 }

22 稀疏矩阵

23 转置矩阵

24

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

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

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

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

29 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; }

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

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

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

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

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

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

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