数据结构DS05-数组和广义表

1、第5章要点数组的类型定义和表示方法特殊矩阵和稀疏矩阵存储方法 及运算的实现广义表的结构特点1第5章 数组数组可以看成是一种特殊的线性表，即线性表中数据元素本身也是一个线性表。5.1.1 多维数组组的定义定义数组特点数组结构固定数据元素同构数组运算给定一组下标，存取相应的数据元素给定一组下标，修改数据元素的值( )( )( )( )( )( )( )( )( )25.1.2 数组的顺序存储结构次序约定以行序为主序以列序为主序 a00 a01 . a0,n-1 a10 a11 . a1,n-1 am-1,0 am-1,1 . am-1,n-1 .Loc( aij)=Loc(a00)+(in+j)L

2、 按行序为主序存放 am-1,n-1 . am-1,1 am-1,0 . a1,n-1 . a11 a10 a0,n-1 . a01 a0001n-1m*n-1n3按列序为主序存放01m-1m*n-1m am-1,n-1 . a1, n-1 a0, n-1 . am-1,1 . a11 a01 am-1,0 . a10 a00 a00 a01 . a0, n-1 a10 a11 . a1, n-1 am-1,0 am-1,1 . am-1,n-1 .Loc(aij)=Loc(a00)+(jm+i)L45.2.1 特殊矩阵对称矩阵 a00 a01 . . a0,n-1 a10 a11 . . a

3、1,n-1 an-1,0 an-1,1 . an-1,n-1 . a00 a10 a11 a20 a21 an-1,0 an-1,n-1 .k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1 按行序为主序：5三角矩阵（下三角矩阵） a00 C C . C a10 a11 C . C an-1,0 an-1,1 an-1,2 . an-1,n-1 . Ca00 a10 a11 a20 a21 an-1,0 an-1,n-1 .k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1 按行序为主序：6对角矩阵 a00 a01 0 . 0 a10 a11 a12 0 0 0 0 a

4、n-2,n-3 an-2,n-2 an-2,n-1 0 0 an-1,n-2 an-1,n-1 0 a21 a22 a23 0 0 设每个元素占L个存储单元，则元素aij的存储地址为： Loc(aij)=Loc(a00)+(2i+j) La00 a01 a10 a11 a12 an-1,n-2 an-1,n-1.k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1 按行序为主序：7M由(1,2,12), (1,3,9), (3,1,-3), (3,6,14), (4,3,24), (5,2,18), (6,1,15), (6,4,-7) （共8个非零元素）和矩阵维数（6,7）唯一确定

5、。5.2.2 稀疏矩阵定义：非零元比零元少，且分布没有一定规律的矩阵称为稀疏矩阵。压缩存储原则：只存储每个非零元素的行、列下标及其值和矩阵的行、列、维数。8稀疏矩阵的压缩存储方法顺序存储结构三元组表#define M 20typedef struct node int i,j; int v; TriTupleNode ;TriTupleNode maM;三元组表所需存储单元个数为3(t+1)其中t为非零元个数6 7 8 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 mai j v0 1 2 3 4 5 6 7 8ma0.i,ma0

6、.j,ma0.v分别存放矩阵行列维数和非零元个数行列下标非零元值9求转置矩阵问题描述：已知一个稀疏矩阵的三元组表，求该矩阵转置矩阵的三元组表问题分析一般矩阵转置算法：for(col=0;coln;col+) for(row=0;rowm;row+) ncolrow=mrowcol;T(n)=O(mn)106 7 8 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 i j v0 1 2 3 4 5 6 7 8mai j v7 6 8 1 3 -3 1 6 15 2 1 12 2 5 18 3 1 9 3 4 24 4 6 -7 6 3

7、 14 0 1 2 3 4 5 6 7 8mb?11解决思路：只要做到 将矩阵行、列维数互换 将每个三元组中的i和j相互调换 重排三元组次序，使mb中元素以N的行(M的列)为主序方法一：按M的列序转置即按mb中三元组次序依次在ma中找到相应的三元组进行转置。为找到M中每一列所有非零元素，需对其三元组表ma从第一行起扫描一遍。由于ma中以M行序为主序,所以由此得到的恰是mb中应有的顺序算法描述：算法分析：T(n)=O(M的列数n非零元个数t) 若 t 与mn同数量级，则126 7 8 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 i

8、 j v0 1 2 3 4 5 6 7 8ma7 6 8 1 3 -3 1 6 15 2 1 12 2 5 18 3 1 9 3 4 24 4 6 -7 6 3 14 i j v0 1 2 3 4 5 6 7 8mbkppppppppkkkkppppppppcol=1col=213方法二：按行序转置（快速转置）即按ma中三元组次序转置，转置结果放入b中恰当位置此法关键是要预先确定M中每一列第一个非零元在mb中位置，为确定这些位置，转置前应先求得M的每一列中非零元个数实现：设两个数组numcol：表示矩阵M中第col列中非零元个数cpotcol：指示M中第col列第一个非零元在mb中位置显然有：

9、cpot1=1;cpotcol=cpotcol-1+numcol-1; (2col ma0.j)1357889colnumcolcpotcol1222324150617014算法分析：T(n)=O(M的列数n+非零元个数t) 若 t 与mn同数量级，则T(n)=O(mn)算法描述：156 7 8 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 i j v0 1 2 3 4 5 6 7 8mai j v0 1 2 3 4 5 6 7 8mbcolnumcolcpotcol1122323524715806817907 6 8 1 3 -

10、3 1 6 15 2 1 12 2 5 18 3 1 9 3 4 24 4 6 -7 6 3 14 pppppppp4629753165.3 广义表 广义表(Lists)也称为列表，它是线性表的推广。大家知道，线性表是n（n0）个元素a1，a2，ai，an的有限序列。其中，线性表的元素仅限于原子项，所谓原子，指的是结构上不可再分割的一种成分，它可以是一个数，或者是一个结构。如果放松对线性表元素的这种限制，允许它们具有其自身独立的类型结构，那么就产生了广义表的概念。 广义表是n（n0）个元素a1，a2，ai，an的有限序列，其中ai或者是原子，或者是一个广义表。通常，广义表可记作LS=(a1,a

11、2,ai,an)。LS是广义表的名字，n为广义表LS的长度。若ai本身也是广义表，则称它为LS的子表。不包含任何元素（即n=0）的广义表称为空表。17需要注意的是：广义表通常用圆括号括起来，用逗号分隔其中的元素。为区分原子和广义表，用大写字母表示广义表，用小写字母表示原子。若广义表LS非空(n1)，则a1称为LS的表头，其余元素组成的表(a2,ai,an)称为LS的表尾。显然，表尾一定是子表，但表头可以是原子，也可以是子表。广义表是递归定义的，因为在定义广义表时又用到了广义表的概念。 18广义表是一个多层次的线性结构。例如:有A、B、C、D、E五个广义表的描述如下：A=( ) A是一个空表,它

12、的长度为零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,.)19广义表的结构特点:1) 广义表中的数据元素有相对次序;2) 广义表的长度定义为最外层包含的元素个数;3) 广义表的深度定义为所含括弧的重数; 注意: “原子”的深度为“0”; “空表”的深度为14) 表头可以是原子或列表;表尾必定是列表

13、。5) 广义表可以是一个递归的表; 递归表的深度是无穷值，长度是有限值。206) 任何一个非空广义表 LS = ( 1, 2, , n) 均可分解为： 表头 Head(LS) = 1 和 表尾 Tail(LS) = ( 2, , n) 两部分。21例如：Head( ( b, c) ) = ( b, c)Tail( ( b, c) ) = ( )Head( a,( b, c) ) = a Tail( a,( b, c) ) = ( b,c )Head( ( c ) ) =(c)Tail( ( c ) ) = ( ) 22广义表还可以用图形来形象的表示，下图给出了几个广义表的图形表示，其中的分支结点对应广义表，非分支结点（即叶子）对应原子或者空表。23与树对应的广义表称为纯表（Pure List），这种表中没有共享和递归的成分，即没有任何成分出现多次，它限制了表中成分的共享和递归，例如图中的(a)，(b)，(c)都是纯表；与有向无环图对应的表称为再入表，这种表存在元素共享，在图中表现为存在结