《第五章_数组与广义表》由会员分享，可在线阅读，更多相关《第五章_数组与广义表（43页珍藏版）》请在金锄头文库上搜索。
1、第五章 数组和 广义表,数组 稀疏矩阵 广义表,数 组,定义 相同类型的数据元素的集合。 一维数组的示例,35 27 49 18 60 54 77 83 41 02,0 1 2 3 4 5 6 7 8 9,一维数组,数组的定义和初始化,main ( ) int a13 = 3, 5, 7 , *elem; for ( int i = 0; i 3; i+ ) printf ( “%d”, a1i, “n” ); /静态数组 elem = a1; for ( int i = 0; i 3; i+ ) printf ( “%d”, *elem, “n” ); /动态数组 elem+; ,一维数组存
2、储方式,类似于线性表，一个二维数组的逻辑结构可形式地表示为：2_Array=(D,R) 其中D=aij(i=0,1,m-1,j=0,1,n-1), aij是同类型数据元素的集合。 R=ROW,COL是数据元素上关系的集合。 ROW=|0|0=i=m-2,0=j=n-1每一列上的行关系。,二维数组,行优先存放： 设数组开始存放位置 LOC( 0, 0 ) = a, 每个元素占用 l 个存储单元 LOC ( i, j ) = a + ( i * m + j ) * l,三维数组,各维元素个数为 m1, m2, m3 下标为 i1, i2, i3的数组元素的存储地址： （按页/行/列存放）,LOC
3、( i1, i2, i3 ) = a + ( i1* m2 * m3 + i2* m3 + i3 ) * l,前i1页总 元素个数,第i1页的 前i2行总元素个数,n 维数组,各维元素个数为 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,特殊矩阵的压缩存储,特殊矩阵是指非零元素
4、或零元素的分布有一定规律的矩阵。 特殊矩阵的压缩存储主要是针对阶数很高的特殊矩阵。为节省存储空间，对可以不存储的元素，如零元素或对称元素，不再存储。 对称矩阵 三对角矩阵,对称矩阵的压缩存储,设有一个 nn 的对称矩阵 A。,在矩阵中，aij = aji,为节约存储空间，只存对角线及对角线以上的元素，或者只存对角线及对角线以下的元素。前者称为上三角矩阵，后者称为下三角矩阵。 把它们按行存放于一个一维数组 B 中，称之为对称矩阵 A 的压缩存储方式。 数组 B 共有 n + ( n - 1 ) + + 1 = n*(n+1)/2 个元素。,上三角矩阵,下三角矩阵,下三角矩阵,B a00 a10
5、a11 a20 a21 a22 a30 a31 a32 an-1n-1,0 1 2 3 4 5 6 7 8 n(n+1)/2-1,若 i j, 数组元素Aij在数组B中的存放位置为 1 + 2 + + i + j = (i + 1)* i / 2 + j,前i行元素总数 第i行第j个元素前元素个数,若 i j，数组元素 Aij 在矩阵的上三角部分, 在数组 B 中没有存放，可以找它的对称元素Aji：= j *(j +1) / 2 + i 若已知某矩阵元素位于数组B的第k个位置，可寻找满足 i (i + 1) / 2 k (i + 1)*(i + 2) / 2 的 i, 此即为该元素的行号。 j
6、 = k - i * (i + 1) / 2 此即为该元素的列号。 例，当 k = 8, 3*4 / 2 = 6 k 4*5 / 2 =10, 取 i = 3。则 j = 8 - 3*4 / 2 = 2。,上三角矩阵,B a00 a01 a02 a03 a11 a12 a13 a22 a23 a33,0 1 2 3 4 5 6 7 8 9,若i j，数组元素Aij在数组B中的存放位置为 n + (n-1) + (n-2) + + (n-i+1) + j-i,前i行元素总数 第i行第j个元素前元素个数,n = 4,若 i j，数组元素Aij在数组B中的存放位置为 n + (n-1) + (n-2
7、) + + (n-i+1) + j-i = = (2*n-i+1) * i / 2 + j-i = = (2*n-i-1) * i / 2 + j 若i j，数组元素Aij在矩阵的下三角部分，在数组 B 中没有存放。因此，找它的对称元素Aji。 Aji在数组 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,三对角矩阵中除主对角线及在主对角线上 下最临近的两条对角线上的元素外，所有其它元素均为0。总共有3n-
8、2个非零元素。 将三对角矩阵A中三条对角线上的元素按行存放在一维数组 B 中，且a00存放于B0。 在三条对角线上的元素aij 满足 0 i n-1, i-1 j i+1 在一维数组 B 中 Aij 在第 i 行，它前面有 3*i-1 个非零元素, 在本行中第 j 列前面有 j-i+1 个，所以元素 Aij 在 B 中位置为 k = 2*i + j。,若已知三对角矩阵中某元素 Aij 在数组 B 存放于第 k 个位置，则有 i = (k + 1) / 3 j = k - 2 * i 例如，当 k = 8 时， i = (8+1) / 3 = 3, j = 8 - 2*3 = 2 当 k = 1
9、0 时， i = (10+1) / 3 = 3, j = 10 - 2*3 = 4,稀疏矩阵 (Sparse Matrix),非零元素个数远远少于矩阵元素个数 在上图中,矩阵A是6*7的矩阵,它有42个元素,但只有8个非零元素,且分布无规律可循,所以可以称之为稀疏矩阵。,稀疏矩阵的抽象数据类型(三元组顺序表） #define MAXSIZE 12500 typedef struct int i,j; /非零元素行号/列号 ElemType e; /非零元素的值 Triple; /三元组 typedef union Triple dataMAXSIZE+1; int mu,nu,tu; /矩阵行
10、数、列数、非零元个数 TSMatrix;/稀疏矩阵类定义,稀疏矩阵,转置矩阵,用三元组表表示的稀疏矩阵及其转置,稀疏矩阵转置算法思想,显然，一个稀疏矩阵的转置仍然是一个稀疏矩阵，方法是：设将矩阵M转置为矩阵T （1）将矩阵的行列值交换 （2）将每一个三元组的i和j相互调换 （3）重排三元组之间的次序 可以有两种处理方法：,方法一：按照M(m*n)的列序来进行转置 设矩阵列数为nu，对矩阵三元组表扫描nu次。第k次检测列号为k的项。 第k次扫描找寻所有列号为k的项，将其行号变列号、列号变行号，顺次存于转置矩阵三元组表。,稀疏矩阵的转置 Status TransposeSMatrix(TSMatr
11、ix M, TSMatrix /TransposeSMatrix,该算法主要工作是在p*col的两重循环中做的，所以时间复杂度是O(nu*tu)。而一般矩阵的转置算法是在nu*mu的两重循环中做的，时间复杂度是O(nu*mu)。当稀疏矩阵的非零元个数tu=nu*mu时，其时间复杂度O(nu*tu)=O(nu*nu*mu)=O(nu2*mu)大大高于一般矩阵的时间复杂度，所以该算法仅适用于tunu*mu的稀疏矩阵。,方法二：快速转置运算,在对M矩阵转置时，M矩阵的三元组中元素按行序排列，T矩阵中的元素按M矩阵的列序排列，前面的转置算法的特点是以T矩阵的三元组为中心，在M矩阵的三元组中通盘查找合适
12、的结点置入T中。如果能预先确定M的每一列第一个非零元在T中应有的位置，则在转置时就可直接放到T中去，所以在转置前，应先求得M的每一列中非零元的个数和每一列的第一个非零元在T中的位置。 为此，需要两个辅助数组num和cpot,num表示M中第col列非零元素的个数。cpot表示M中第col列第一个非零元素在T中的位置。显然有：,cpot1=1,cpotcol=cpotcol-1+numcol-1,矩阵M的辅助数组的值,转置矩阵,Status FastTransposeSMatrix(TSMatrix M, TSMatrix /FastTransposeSMatrix,行逻辑链接的顺序表,为便于随
13、机存取任意一行的非零元，将快速转置矩阵的算法中的辅助数组cpot固定在稀疏矩阵的存储结构中。 typedef struct Triple dataMAXSIZE+1; int rposMAXRC+1; int mu,nu,tu; RLSMatrix; 该存储方法便于某些运算如稀疏矩阵的相乘。,十字链表,以链式存储结构表示三元组的线性表。,广义表 (General Lists ),广义表的概念 n ( 0 )个表元素组成的有 限序列，记作 LS = (a0, a1, a2, , an-1) LS是表名，ai是表元素，它可以是表 (称 为子表)，可以是数据元素(称为原子)。 n为表的长度。n =
14、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); /递归的列表,包含两个元素,一个是单元素a,另一个是子表,但该子表是其自身.所以,E相当于一个无限的广义表( a,(a,(a,).,例如,表结点,广义表存储结构,原子结点,typedef struct GLNode int tag; union char atom
15、; struct structGLNode *hp,*tp;ptr; ; *GList;,方法一,方法一,表结点,广义表存储结构,原子结点,typedef struct GLNode int tag; union char atom; struct GLNode *hp; ; struct GLNode *tp; *GList;,方法二,方法二,广义表的递归算法,1.广义表的深度（广义表中括号的重数） 设非空广义表为LS=(a1,a2,an) 其中ai(i=1,2,n)或为原子或为LS的子表。原子的深度为零，空表的深度为1，其它情况下表长为各子表深度最大值加1。,int GListDepth(GList L) if(!L) return 1; if(L-tag=ATOM) return 0; for(max=0,pp=L;pp;pp=pp-ptr.tp) dep=GListDepth(pp-ptr
