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

1、第 章 数 组 和 广 义 表 第五章 数组q数组的类型定义和表示方法数组的类型定义和表示方法q特殊矩阵和稀疏矩阵存储方法特殊矩阵和稀疏矩阵存储方法 及运算的实现及运算的实现q广义表的结构特点广义表的结构特点第 章 数 组 和 广 义 表 5.1.1 二维数组的定义二维数组的定义n定义定义mnmmnnnmaaaaaaaaaA.212222111211数组特点数组特点数组结构固定数组结构固定数据元素同构数据元素同构数组运算数组运算给定一组下标，存取相应的数据元素给定一组下标，存取相应的数据元素给定一组下标，修改数据元素的值给定一组下标，修改数据元素的值( )( )( )( )( )( )( )(

2、 )( )数组是一组有固定数组是一组有固定（一（一旦定义了数组的维数和旦定义了数组的维数和每一维的上下限个数）每一维的上下限个数）的元素的集合。的元素的集合。由于这由于这个性质，使得对数组的个性质，使得对数组的操作不像对线性表的操操作不像对线性表的操作那样可以在表中任意作那样可以在表中任意一个合法的位置插入或一个合法的位置插入或删除一个元素。对于数删除一个元素。对于数组的操作一般只有两类：组的操作一般只有两类： 数组可以看成是一种特殊的线性表，即线数组可以看成是一种特殊的线性表，即线性表中数据元素本身也是一个线性表性表中数据元素本身也是一个线性表第 章 数 组 和 广 义 表 矩阵矩阵A Am

3、 mn n看成看成n n个列向量的线性表个列向量的线性表 第 章 数 组 和 广 义 表 矩阵矩阵A Am mn n看成看成m m个行向量的线性表个行向量的线性表 第 章 数 组 和 广 义 表 5.1.2 数组的顺序存储结构次序约定次序约定n以行序为主序以行序为主序n以列序为主序以列序为主序 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 二维数组按列

4、序为二维数组按列序为主序存放主序存放（下标从（下标从1开始）开始）01m-1m*n-1m amn . a2n a1n . am2 . a22 a12 am1 . a21 a11 a11 a12 . a1n a21 a22 . a2n am1 am2 . amn .Loc(aij)=Loc(a11)+(j-1)*m+(i-1)*L L为每一个数组元素所占的存储单元个数为每一个数组元素所占的存储单元个数第 章 数 组 和 广 义 表 共有共有120个元素个元素三维数组的逻辑结构图三维数组的逻辑结构图 下标从下标从0开始开始页行列第 章 数 组 和 广 义 表 m m1 1, m, m2 2, m,

5、 m3 3LOC ( i1, i2, i3 ) = a + ( i1* m2 * m3 + i2* m3 + i3 ) * l 前前i1页总页总元素个数元素个数第第i1页的页的前前i2行行总总元素个数元素个数第 章 数 组 和 广 义 表 m m1 1, m, m2 2, m, m3 3, , , m, mn nlimianjnjknkj*111LOC ( i1, i2, , in ) = a + ( i1*m2*m3*mn + i2*m3*m4*mn+ + + in-1*mn + in ) * l 第 章 数 组 和 广 义 表 1112111012222120111211101002010

6、0nnnnnnnnaaaaaaaaaaaaaaaa对称阵下三角矩阵5.2.1 特殊矩阵特殊矩阵第 章 数 组 和 广 义 表 11121110122221201112111010020100nnnnnnnnaaaaaaaaaaaaaaaa对对称称阵阵的的上上三三角角矩矩阵阵A=第 章 数 组 和 广 义 表 对称矩阵的存储对称矩阵的存储11121110122221201112111010020100Annnnnnnnaaaaaaaaaaaaaaaa，aij = aji0 1 2 3 4 5 6 7 8 n(n+1)/2-1B a00 a10 a11 a20 a21 a22 a30 a31 a3

7、2 an-1n-1 存存下下三三角角第 章 数 组 和 广 义 表 = j *(j +1) / 2 + i 前i行元素总数 第i行第j个元素前元素个数第 章 数 组 和 广 义 表 33323130232221201312111003020100aaaaaaaaaaaaaaaa上三角矩阵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

8、个元素前元素个数n = 4第 章 数 组 和 广 义 表 若若 i j，数组元素，数组元素Aij在数组在数组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，数组元素，数组元素Aij在矩阵的下三角部分，在在矩阵的下三角部分，在数组数组 B 中没有存放。因此，找它的对称元素中没有存放。因此，找它的对称元素Aji。 Aji在数组在数组 B 的第的第 (2*n- -j- -1) * j / 2 +

9、 i 的位置中找的位置中找到。到。对于上三角矩阵第 章 数 组 和 广 义 表 n三角矩阵三角矩阵 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 3 4 n(n-1)/2 n(n+1)/2-1 按行序为主序：ji 时aij为0一个元素所占字节数一个元素所占字节数下标从下标从1开始开始第 章 数 组 和 广 义 表 1121122232232221121110010000000000000000000Ann

10、nnnnnnnnaaaaaaaaaaaaaB 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起起第 章 数 组 和 广 义 表 n三对角矩阵中除主对角线及在主对角线上下最临三对角矩阵中除主对角线及在主对角线上下最临近的两条对角线上的元素外，所有其它元素均为近的两条对角线上的元素外，所有其它元素均为0 0。总共有。总共有2+3(2+3(n n-2)+2= 3-2)+2= 3n n-2-2个非零元素。个非零

11、元素。n将三对角矩阵将三对角矩阵A A中三条对角线上的元素按行存放中三条对角线上的元素按行存放在一维数组在一维数组 B B 中，且中，且a a0000存放于存放于B0B0。n在三条对角线上的元素在三条对角线上的元素a aijij 满足满足 0 0 i i n n-1, -1, i i-1 -1 j j i i+1+1n在一维数组在一维数组 B B 中中 Aij Aij 在第在第 i i 行，它前面行，它前面有有 3 3* *i-1 i-1 个非零元素个非零元素, , 在本行中第在本行中第 j j 列前面有列前面有 j-i+1 j-i+1 个，所以元素个，所以元素 Aij Aij 在在 B B

12、中位置为中位置为 k k = 2 = 2* *i i + + j 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不第 章 数 组 和 广 义 表 5.2.2 稀疏矩阵稀疏矩阵定义：定义：非零元较零元少，且分非零元较零元少，且分布

13、没有一定规律的矩阵布没有一定规律的矩阵压缩存储原则：压缩存储原则：只存矩阵的行只存矩阵的行列维数和每个非零元的行列下列维数和每个非零元的行列下标及其值标及其值第 章 数 组 和 广 义 表 7600070015000001800000240001400003000000000009120MM由(1,2,12), (1,3,9), (3,1,-3), (3,6,14), (4,3,24), (5,2,18), (6,1,15), (6,4,-7) 和矩阵维数（6,7,8）唯一确定例如：例如：第 章 数 组 和 广 义 表 稀疏矩阵的压缩存储方法稀疏矩阵的压缩存储方法n三元组表三元组表#defin

14、e M 20typedef struct node /*三元组表中元素类型*/ int i,j; /*非零元所在行号和列号*/ int v; /*非零元素值*/ TriTupleNode ;TriTupleNode maM; mai j v0 1 2 3 4 5 6 7 8第 章 数 组 和 广 义 表 7600070015000001800000240001400003000000000009120Amai 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 1 15 6 4 -7 第 章 数 组 和 广

15、义 表 n求转置矩阵求转置矩阵Y问题描述：已知一个稀疏矩阵的三元组表，问题描述：已知一个稀疏矩阵的三元组表，求该矩阵转置矩阵的三元组表求该矩阵转置矩阵的三元组表Y问题分析问题分析一般矩阵转置算法：一般矩阵转置算法：for(col=0;coln;col+) for(row=0;rowm;row+) Bcolrow=Arowcol;时间复杂度：时间复杂度：T(n)=O(m n)第 章 数 组 和 广 义 表 7600070015000001800000240001400003000000000009120A6700000000014000000007000000024009018000121500

16、300B6 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 14 0 1 2 3 4 5 6 7 8mb按行序存放按行序存放第 章 数 组 和 广 义 表 解决思路：解决思路：将矩阵行、列维数互换将矩阵行、列维数互换将每个三元组中的将每个三元组中的i和和j相互调换相互调换重排三元组次序，使重排三元组次序，使mb中元素以中元素以B的行的行(A的列的列)为主

17、序为主序第 章 数 组 和 广 义 表 5.3 广义表 广义表广义表(Lists)(Lists)也称为也称为列表列表，它是线性表，它是线性表的推广。大家知道，线性表是的推广。大家知道，线性表是n n（n n0 0）个）个元素元素a a1 1，a a2 2，a ai i，a an n的有限序列。的有限序列。其中，线性表的元素仅限于原子项，所谓其中，线性表的元素仅限于原子项，所谓原原子子，指的是结构上不可再分割的一种成分，指的是结构上不可再分割的一种成分，它可以是一个数，或者是一个结构。如果放它可以是一个数，或者是一个结构。如果放松对线性表元素的这种限制，允许它们具有松对线性表元素的这种限制，允许

18、它们具有其自身独立的类型结构，那么就产生了广义其自身独立的类型结构，那么就产生了广义表的概念。表的概念。第 章 数 组 和 广 义 表 LS = (a0, a1, a2, , an-1) LS第 章 数 组 和 广 义 表 广义表通常用圆括号括起来，用逗号广义表通常用圆括号括起来，用逗号分隔其中的元素。分隔其中的元素。n为区分原子和广义表，用大写字母表示为区分原子和广义表，用大写字母表示广义表，用小写字母表示原子。广义表，用小写字母表示原子。n表尾一定是子表。但表头可以是原子，表尾一定是子表。但表头可以是原子，也可以是子表。也可以是子表。n广义表是递归定义的，因为在定义广义广义表是递归定义的，

19、因为在定义广义表时又用到了广义表的概念。表时又用到了广义表的概念。 需要注意的是：需要注意的是：第 章 数 组 和 广 义 表 广义表是一个广义表是一个多层次多层次的的线性结构线性结构。例如。例如:有有A、B、C、D、E五个广义表的描述如下：五个广义表的描述如下： 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,三个元素都

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

21、 “0”; “空表空表”的深度的深度为为1 14) 4) 表头可以是原子或列表表头可以是原子或列表; ;表尾必定是列表。表尾必定是列表。5) 5) 广义表可以是一个广义表可以是一个递归递归的表的表; ; 递归表的深度是无穷值，长度是有限值。递归表的深度是无穷值，长度是有限值。广义表的结构特点广义表的结构特点: :第 章 数 组 和 广 义 表 6) 任何一个非空广义表任何一个非空广义表 LS = ( LS = ( 1 1, , 2 2, , , , n n) ) 均可分解为均可分解为 表头表头 Head(LS) = Head(LS) = 1 1 表尾表尾 Tail(LS) = ( Tail(L

22、S) = ( 2 2, , , , n 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 ) ) = ( ) 求出的表头是原样，而求出的表尾要再加上一对圆括号才为所求第 章 数 组 和 广 义 表 Head(Head(LSLS) = A ) = A Tail(Tail(LSLS) = ( D ) = ( D )Head( Head( D

23、 D ) = E ) = E Tail( Tail( D D ) = ( F ) ) = ( F )Head(Head( E E ) = a Tail() = a Tail( E E ) = ( ( b, c) ) ) = ( ( b, c) )Head(Head( ( b, c) ( b, c) ) = ( b, c) Tail( ) = ( b, c) Tail( ( b, c)( b, c) ) = ( ) ) = ( )Head(Head( ( b, c) ( b, c) ) = b Tail( ) = b Tail( ( b, c)( b, c) ) = ( c ) ) = ( c

24、)LS = (A, D ) = ( ), ( E, F ) = ( ), (a, (b, c)LS = (A, D ) = ( ), ( E, F ) = ( ), (a, (b, c)，F )F )例如：例如：第 章 数 组 和 广 义 表 广义表还可以用图形来形象的表示，下图给出广义表还可以用图形来形象的表示，下图给出了几个广义表的图形表示，其中的分支结点对了几个广义表的图形表示，其中的分支结点对应应广义表广义表，非分支结点（即，非分支结点（即叶子叶子）对应原子或）对应原子或者空表。者空表。Lab(a)L=(a,b)AxL(b)A=(x,L)abAxLaByb(c)B=(A,y)AxLaCBb(d)C=(A,B)a