数据结构-C语言版：DS05-数组和广义表

1、第五章 数组数组的类型定义和表示方法特殊矩阵和稀疏矩阵存储方法 及运算的实现广义表的结构特点5.1.1 二维数组的定义定义数组特点数组结构固定数据元素同构数组运算给定一组下标，存取相应的数据元素给定一组下标，修改数据元素的值( )( )( )( )( )( )( )( )( )数组是一组有固定（一旦定义了数组的维数和每一维的上下限个数）的元素的集合。由于这个性质，使得对数组的操作不像对线性表的操作那样可以在表中任意一个合法的位置插入或删除一个元素。对于数组的操作一般只有两类：数组可以看成是一种特殊的线性表，即线性表中数据元素本身也是一个线性表矩阵Amn看成n个列向量的线性表 矩阵Amn看成m个

2、行向量的线性表 5.1.2 数组的顺序存储结构次序约定以行序为主序以列序为主序 a11 a12 . a1n a21 a22 . a2n am1 am2 . amn .Loc( aij)=Loc(a11)+(i-1)n+(j-1)*l 按行序为主序存放 amn . am2 am1 a2n . a22 a21 a1n a12 a1101n-1m*n-1 n二维数组按列序为主序存放（下标从1开始）01m-1m*n-1m amn . a2n a1n . am2 . a22 a12 am1 . a21 a11 a11 a12 . a1n a21 a22 . a2n am1 am2 . amn .Loc(

3、aij)=Loc(a11)+(j-1)*m+(i-1)*L L为每一个数组元素所占的存储单元个数 二维数组 三维数组行向量 下标 i 页向量 下标 i列向量 下标 j 行向量 下标 j 列向量 下标 k共有120个元素三维数组的逻辑结构图 下标从0开始页行列三维数组(下标从0开始) 各维元素个数为 m1, m2, m3 下标为 i1,i2,i3的数组元素的存储地址：（按页/行/列存放） LOC ( i1, i2, i3 ) = a + ( i1* m2 * m3 + i2* m3 + i3 ) * l 前i1页总元素个数第i1页的前i2行总元素个数 n 维数组 各维元素个数为 m1, m2,

4、m3, , mn 下标为 i1, i2, i3, , in 的数组元素的存储地址： LOC ( i1, i2, , in ) = a + ( i1*m2*m3*mn + i2*m3*m4*mn+ + + in-1*mn + in ) * l 对称阵下三角矩阵5.2.1 特殊矩阵为节约存储，只存对角线及对角线以上的元素，或者只存对角线及对角线以下的元素。前者称为上三角矩阵，后者称为下三角矩阵。对称阵的上三角矩阵把它们按行存放于一个一维数组 B 中，称之为对称矩阵 A 的压缩存储方式。数组 B 共有 n + ( n - 1 ) + + 1 = n*(n+1)/2 个元素。A=对称矩阵的存储在矩阵中

5、，aij = aji0 1 2 3 4 5 6 7 8 n(n+1)/2-1B a00 a10 a11 a20 a21 a22 a30 a31 a32 an-1n-1 存下三角 若 i j，数组元素 Aij 在矩阵的上三角部分, 在数组 B 中没有存放，可以找它的对称元素 Aji= j *(j +1) / 2 + i 若 i j, 数组元素Aij在数组B中的存放位置为 1 + 2 + + i + j = (i + 1)* i / 2 + j前i行元素总数 第i行第j个元素前元素个数若已知某矩阵元素位于数组 B 的第 k个位置，可寻找满足 i (i + 1) / 2 k (i + 1)*(i +

6、 2) / 2的 i, 此即为该元素的行号。 j = k - i * (i + 1) / 2此即为该元素的列号。 例，当 k = 8, 3*4 / 2 = 6 k j，数组元素Aij在矩阵的下三角部分，在数组 B 中没有存放。因此，找它的对称元素Aji。 Aji在数组 B 的第 (2*n-j-1) * j / 2 + i 的位置中找到。对于上三角矩阵三角矩阵 a11 0 0 . 0 a21 a22 0 . 0 an1 an2 an3. ann . 0Loc(aij)=Loc(a11)+( +(j-1)*L i(i-1)2a11 a21 a22 a31 a32 an1 ann .k=0 1 2

7、3 4 n(n-1)/2 n(n+1)/2-1 按行序为主序：ji 时aij为0一个元素所占字节数下标从1开始三对角矩阵的压缩存储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起存放对角阵元素的一维数组的下标从0起三对角矩阵中除主对角线及在主对角线上下最临近的两条对角线上的元素外，所有其它元素均为0。总共有2+3(n-2)+2= 3n-2个非零元素。将三对角矩阵A中三条对角线上的元素按行存放在一维数组 B 中，且a00存放于B0。在三条对角线上的元素aij 满足 0 i n-1,

8、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 = 10 时， i = (10+1)/3 = 3, j = 10-2*3 = 4不对角矩阵(这是三对角阵，如是K对角则要求K是奇数) a11 a12 0 . 0 a21 a22

9、 a23 0 0 0 0 an-1,n-2 an-1,n-1 an-1,n 0 0 an,n-1 ann. 0 a32 a33 a34 0 0 Loc(aij)=Loc(a11)+2(i-1)+(j-1)*L a11 a12 a21 a22 a23 ann-1 ann .k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1 按行序为主序：对角阵的下标从1起存放对角阵元素的一维数组的下标从0起5.2.2 稀疏矩阵定义：非零元较零元少，且分布没有一定规律的矩阵压缩存储原则：只存矩阵的行列维数和每个非零元的行列下标及其值M由(1,2,12), (1,3,9), (3,1,-3), (3,6

10、,14), (4,3,24), (5,2,18), (6,1,15), (6,4,-7) 和矩阵维数（6,7,8）唯一确定例如：稀疏矩阵的压缩存储方法顺序存储结构三元组表#define M 20typedef struct node /*三元组表中元素类型*/ int i,j; /*非零元所在行号和列号*/ int v; /*非零元素值*/ TriTupleNode ;TriTupleNode maM; mai j v0 1 2 3 4 5 6 7 8mai j v0 1 2 3 4 5 6 7 86 7 8 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6

11、 1 15 6 4 -7 求转置矩阵问题描述：已知一个稀疏矩阵的三元组表，求该矩阵转置矩阵的三元组表问题分析一般矩阵转置算法：for(col=0;coln;col+) for(row=0;row 0时，表的第一个表元素称为广义表的表头(head)，除此之外，其它表元素组成的表称为广义表的表尾(tail)。 广义表通常用圆括号括起来，用逗号分隔其中的元素。为区分原子和广义表，用大写字母表示广义表，用小写字母表示原子。表尾一定是子表。但表头可以是原子，也可以是子表。广义表是递归定义的，因为在定义广义表时又用到了广义表的概念。 需要注意的是：广义表是一个多层次的线性结构。例如:有A、B、C、D、E五

12、个广义表的描述如下：A = ( ) A是一个空表,它的长度为零B = (e) 列表B只有一个原子e,B的长度为1.C = (a,(b,c,d) 列表C的长度为2,两个元素分别为原子a和子表(b,c,d)D = (A,B,C) 列表D的长度为3,三个元素都是列表,显然,将子表的值代入后,则有D=(),(e),(a,(b,c,d)E = (a,E) 这是一个递归的表,它的长度为2,E相当于一个无限的列表E=(a,(a,(a,.)1) 广义表中的数据元素有相对次序;2) 广义表的长度定义为最外层包含的元素个数;3) 广义表的深度定义为所含括弧的重数; 注意: “原子”的深度为“0”; “空表”的深度

13、为14) 表头可以是原子或列表;表尾必定是列表。5) 广义表可以是一个递归的表; 递归表的深度是无穷值，长度是有限值。广义表的结构特点:6) 任何一个非空广义表 LS = ( 1, 2, , n) 均可分解为 表头 Head(LS) = 1 表尾 Tail(LS) = ( 2, , n) 两部分例如：Head( ( b, c) ) = ( b, c)Tail( ( b, c) ) = ( )Head( a,( b, c) ) = a Tail( a,( b, c) ) = ( b,c )Head( ( c ) ) =(c)Tail( ( c ) ) = ( ) 求出的表头是原样，而求出的表尾要

14、再加上一对园括号才为所求Head(LS) = A Tail(LS) = ( D )Head( D ) = E Tail( D ) = ( F )Head( E ) = a Tail( E ) = ( ( b, c) )Head( ( b, c) ) = ( b, c) Tail( ( b, c) ) = ( )Head( ( b, c) ) = b Tail( ( b, c) ) = ( c )LS = (A, D ) = ( ), ( E, F ) = ( ), (a, (b, c)，F )例如： 广义表还可以用图形来形象的表示，下图给出了几个广义表的图形表示，其中的分支结点对应广义表，非分支结点（即叶子）对应原子或者空表。递归表线性表再入表与树对应的广义表称为纯表（Pure List），这种表中没有共享和递归的成分，即没有任何成分出现多次，它限制了表中成分的共享和递归，例如图中的(a)，(b)，(c)都是纯表；与有向无环图对应的表称为再入表，这种表存在元素共享，在图中表现为存在结点共享，例如图中 (d)，子表A是共享结点，它既是C的一个元素，又是子表B的元素；与有回路的有向图对应的表称为递归表，这种表的某个成员内含有广义表自己，例如图(e)中，表D是其自身的