第 章 数 组 和 广 义 表 第五章 数组q数组的类型定义和表示方法数组的类型定义和表示方法q特殊矩阵和稀疏矩阵存储方法特殊矩阵和稀疏矩阵存储方法及运算的实现及运算的实现q广义表的结构特点广义表的结构特点第 章 数 组 和 广 义 表 5.1.1 二维数组的定义二维数组的定义n定义定义数组特点数组特点数组结构固定数组结构固定数据元素同构数据元素同构数组运算数组运算给定一组下标，存取相应的数据元素给定一组下标，存取相应的数据元素给定一组下标，修改数据元素的值给定一组下标，修改数据元素的值( )( )( )( )( )( )( )( )( )数组是一组有固定数组是一组有固定（一（一旦定义了数组的维数和旦定义了数组的维数和每一维的上下限个数）每一维的上下限个数）的元素的集合。的元素的集合。由于这由于这个性质，使得对数组的个性质，使得对数组的操作不像对线性表的操操作不像对线性表的操作那样可以在表中任意作那样可以在表中任意一个合法的位置插入或一个合法的位置插入或删除一个元素。对于数删除一个元素。对于数组的操作一般只有两类：组的操作一般只有两类：数组可以看成是一种特殊的线性表，即线性表数组可以看成是一种特殊的线性表，即线性表中数据元素本身也是一个线性表中数据元素本身也是一个线性表第 章 数 组 和 广 义 表 矩阵矩阵A Amnmn看成看成n n个列向量的线性表个列向量的线性表第 章 数 组 和 广 义 表 矩阵矩阵A Amnmn看成看成m m个行向量的线性表个行向量的线性表 第 章 数 组 和 广 义 表 5.1.2 数组的顺序存储结构次序约定次序约定n以行序为主序以行序为主序n以列序为主序以列序为主序a11a12.a1na21a22.a2nam1am2.amn.Loc(aij)=Loc(a11)+(i-1)n+(j-1)*l按行序为主序存放按行序为主序存放amn.am2am1a2n.a22a21a1na12a1101n-1m*n-1 n二维数组按列序为二维数组按列序为主序存放主序存放（下标从（下标从1开始）开始）01m-1m*n-1mamn.a2na1n.am2.a22a12am1.a21a11a11a12.a1na21a22.a2nam1am2.amn.Loc(aij)=Loc(a11)+(j-1)*m+(i-1)*LL为每一个数组元素所占的存储单元个数为每一个数组元素所占的存储单元个数第 章 数 组 和 广 义 表 二维数组二维数组二维数组二维数组 三维数组三维数组三维数组三维数组行向量行向量行向量行向量 下标下标下标下标 i i 页向量页向量页向量页向量 下标下标下标下标 i i列向量列向量列向量列向量 下标下标下标下标 j j 行向量行向量行向量行向量 下标下标下标下标 j j 列向量列向量列向量列向量 下标下标下标下标 k k共有共有120个元素个元素三维数组的逻辑结构图三维数组的逻辑结构图下标从下标从0开始开始页行列第 章 数 组 和 广 义 表 三维数组三维数组( (下标从下标从下标从下标从0 0开始开始开始开始) )FF 各维元素个数为各维元素个数为 m m1 1, m, m2 2, m, m3 3FF 下标为下标为 i i1 1,i,i2 2,i,i3 3的数组元素的存储地址：的数组元素的存储地址：（按页（按页/ /行行/ /列存放）列存放） LOC(i1, i2, i3)=a+(i1*m2*m3+ i2* m3+ i3 )* l 前前i1页总页总元素个数元素个数第第i1页的页的前前i2行行总总元素个数元素个数第 章 数 组 和 广 义 表 n n n 维数组维数组FF 各维元素个数为各维元素个数为 m m1 1, m, m2 2, m, m3 3, , , , m mn nFF 下标为下标为 i i1 1, i, i2 2, i, i3 3, , i, , in n 的数组元素的数组元素的存储地址：的存储地址： LOC(i1, i2, , in)=a+(i1*m2*m3*mn + i2*m3*m4*mn+ + + in-1*mn + in )* l 第 章 数 组 和 广 义 表 对称阵下三角矩阵5.2.1 特殊矩阵特殊矩阵为节约存储，只存对角线及对角线以上的元素，为节约存储，只存对角线及对角线以上的元素，为节约存储，只存对角线及对角线以上的元素，为节约存储，只存对角线及对角线以上的元素，或者只存对角线及对角线以下的元素。前者称为或者只存对角线及对角线以下的元素。前者称为或者只存对角线及对角线以下的元素。前者称为或者只存对角线及对角线以下的元素。前者称为上三角矩阵，后者称为下三角矩阵。上三角矩阵，后者称为下三角矩阵。上三角矩阵，后者称为下三角矩阵。上三角矩阵，后者称为下三角矩阵。第 章 数 组 和 广 义 表 对对称称阵阵的的上上三三角角矩矩阵阵n n把它们按行存放于一个一维数组把它们按行存放于一个一维数组把它们按行存放于一个一维数组把它们按行存放于一个一维数组 B B 中，称之为中，称之为中，称之为中，称之为对称矩阵对称矩阵对称矩阵对称矩阵 A A 的压缩存储方式。的压缩存储方式。的压缩存储方式。的压缩存储方式。n n数组数组数组数组 B B 共有共有共有共有 n + ( n n + ( n - - - - 1 ) + 1 ) + + 1 =+ 1 = n*(n+1)/2n*(n+1)/2 个元素。个元素。个元素。个元素。A=第 章 数 组 和 广 义 表 对称矩阵的存储对称矩阵的存储在矩阵中在矩阵中在矩阵中在矩阵中，aij =aji0 1 2 3 4 5 6 7 8 n(n+1)/2-1B a00a10a11a20a21a22a30a31a32 an-1n-1 存存下下三三角角第 章 数 组 和 广 义 表 若若若若 i ij j，数组元素数组元素数组元素数组元素 AAi i j j 在矩阵的在矩阵的在矩阵的在矩阵的上三角上三角上三角上三角部部部部分分分分, ,在数组在数组在数组在数组 BB中没有存放，可以找它的对称中没有存放，可以找它的对称中没有存放，可以找它的对称中没有存放，可以找它的对称元素元素元素元素AAj j i i=j *(j +1)/2+i若若若若 i i j j, ,数组元素数组元素数组元素数组元素AAi i j j 在数组在数组在数组在数组B B中的存放位置中的存放位置中的存放位置中的存放位置为为为为 1+2+1+2+i i +j j=( (i i +1)*1)*i i /2+/2+j j前i行元素总数 第i行第j个元素前元素个数若已知某矩阵元素位于数组若已知某矩阵元素位于数组若已知某矩阵元素位于数组若已知某矩阵元素位于数组 BB的第的第的第的第 k k个位置，可寻找满足个位置，可寻找满足个位置，可寻找满足个位置，可寻找满足i i( (i i+1)/2+1)/2 k k(i i+1)*(+1)*(i i+2)/2+2)/2的的的的 i i, , 此即为此即为此即为此即为该元素的行号。该元素的行号。该元素的行号。该元素的行号。j j=k k - - - - i i*(*(i i+1)/2+1)/2此即为该元素的列号。此即为该元素的列号。此即为该元素的列号。此即为该元素的列号。例，当例，当例，当例，当 k k=8=8,3*4/2=3*4/2=6 6 k k j，数组元素数组元素Aij在矩阵的下三角部分，在在矩阵的下三角部分，在数组数组B中没有存放。因此，找它的对称元素中没有存放。因此，找它的对称元素Aji。Aji在数组在数组B的第的第(2*n- -j- -1)*j/2+i的位置中找的位置中找到。到。对于上三角矩阵第 章 数 组 和 广 义 表 n三角矩阵三角矩阵a1100.0a21a220.0an1an2an3.ann.0Loc(aij)=Loc(a11)+(+(j-1)*Li(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开始开始第 章 数 组 和 广 义 表 三对角矩阵的压缩存储三对角矩阵的压缩存储三对角矩阵的压缩存储三对角矩阵的压缩存储B a00a01a10a11a12a21a22a23an-1n-2an-1n-10 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个非零元素。个非零元素。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 中位置为中位置为 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不第 章 数 组 和 广 义 表 n对角矩阵(这是三对角阵，如是K对角则要求K是奇数)a11a120.0a21a22a230000an-1,n-2an-1,n-1an-1,n00an,n-1ann.0a32a33a3400Loc(aij)=Loc(a11)+2(i-1)+(j-1)*La11 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,14), (4,3,24), (5,2,18), (6,1,15), (6,4,-7) 和矩阵维数（6,7,8）唯一确定例如：例如：第 章 数 组 和 广 义 表 稀疏矩阵的压缩存储方法稀疏矩阵的压缩存储方法n顺序存储结构顺序存储结构n三元组表三元组表#define M 20typedef struct node /*三元组表中元素类型*/ int i,j; /*非零元所在行号和列号*/ int v; /*非零元素值*/ TriTupleNode ;TriTupleNode maM; mai j v0 1 2 3 4 5 6 7 8第 章 数 组 和 广 义 表 mai 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 第 章 数 组 和 广 义 表 n求转置矩阵求转置矩阵Y问题描述：已知一个稀疏矩阵的三元组表，问题描述：已知一个稀疏矩阵的三元组表，求该矩阵转置矩阵的三元组表求该矩阵转置矩阵的三元组表Y问题分析问题分析一般矩阵转置算法：一般矩阵转置算法：for(col=0;coln;col+)for(row=0;row00时，时，时，时，表的第一个表元素称为广义表的表的第一个表元素称为广义表的表的第一个表元素称为广义表的表的第一个表元素称为广义表的表头表头表头表头( (headhead) )，除此之外，除此之外，除此之外，除此之外，其它表元素组成的表称为广义表的其它表元素组成的表称为广义表的其它表元素组成的表称为广义表的其它表元素组成的表称为广义表的表尾表尾表尾表尾( (tailtail) )。第 章 数 组 和 广 义 表 广广义义表表通通常常用用圆圆括括号号括括起起来来，用用逗逗号号分隔其中的元素。分隔其中的元素。n为为区区分分原原子子和和广广义义表表，用用大大写写字字母母表表示示广义表，用小写字母表示原子。广义表，用小写字母表示原子。n表表尾尾一一定定是是子子表表。但但表表头头可可以以是是原原子子，也可以是子表。也可以是子表。n广广义义表表是是递递归归定定义义的的，因因为为在在定定义义广广义义表时又用到了广义表的概念。表时又用到了广义表的概念。 需要注意的是：需要注意的是：第 章 数 组 和 广 义 表 广广义义表表是是一一个个多多层层次次的的线线性性结结构构。例例如如:有有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,三三个个元元素素都都是是列列表表,显然然,将子表的将子表的值代入后代入后,则有有D=(),(e),(a,(b,c,d)E=(a,E)这是是一一个个递归的的表表,它它的的长度度为2,E相当于一个无限的列表相当于一个无限的列表E=(a,(a,(a,.)第 章 数 组 和 广 义 表 1) 1) 广义表中的数据元素有相对广义表中的数据元素有相对次序次序; ;2) 2) 广广义义表表的的长长度度定定义义为为最最外外层层包包含含的的元元素素个个数数; ;3) 3) 广义表的广义表的深度深度定义为所含括弧的重数定义为所含括弧的重数; ; 注注意意: : “原原子子”的的深深度度为为“0 0”; ; “空空表表”的的深深度度为为1 14) 4) 表头可以是原子或列表表头可以是原子或列表; ;表尾必定是列表。表尾必定是列表。5) 5) 广义表可以是一个广义表可以是一个递归递归的表的表; ; 递归表的深度是无穷值，长度是有限值。递归表的深度是无穷值，长度是有限值。广义表的结构特点广义表的结构特点: :第 章 数 组 和 广 义 表 6)任何一个非空广义表任何一个非空广义表 LS = ( LS = ( 1 1, , 2 2, , , , n n) ) 均可分解为均可分解为 表头表头 Head(LS) = Head(LS) = 1 1 表尾表尾 Tail(LS) = ( Tail(LS) = ( 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 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 )LS = (A, D ) = ( ), ( E, F ) = ( ), (a, (b, c)LS = (A, D ) = ( ), ( E, F ) = ( ), (a, (b, c)，F )F )例如：例如：第 章 数 组 和 广 义 表 广广义义表表还还可可以以用用图图形形来来形形象象的的表表示示，下下图图给给出出了了几几个个广广义义表表的的图图形形表表示示，其其中中的的分分支支结结点点对对应应广广义义表表，非非分分支支结结点点（即即叶叶子子）对对应应原原子子或或者空表。者空表。递递归归表表线性表线性表再入表再入表第 章 数 组 和 广 义 表 与与树树对对应应的的广广义义表表称称为为纯纯表表（Pure Pure ListList），这这种种表表中中没没有有共共享享和和递递归归的的成成分分，即即没没有有任任何何成成分分出出现现多多次次，它它限限制制了了表表中中成成分分的的共共享享和和递递归归，例如图中的例如图中的( (a)a)，(b)(b)，(c)(c)都是纯表；都是纯表；与与有有向向无无环环图图对对应应的的表表称称为为再再入入表表，这这种种表表存存在在元元素素共共享享，在在图图中中表表现现为为存存在在结结点点共共享享，例例如如图图中中 ( (d)d)，子子表表A A是是共共享享结结点点，它它既既是是C C的的一一个元素，又是子表个元素，又是子表B B的元素；的元素；与与有有回回路路的的有有向向图图对对应应的的表表称称为为递递归归表表，这这种种表表的的某某个个成成员员内内含含有有广广义义表表自自己己，例例如如图图( (e)e)中中，表表D D是其自身的子表。是其自身的子表。第 章 数 组 和 广 义 表 n各种表之间的关系满足：递归表 再入表 纯表 线性表第 章 数 组 和 广 义 表 广义表的表示广义表的表示广义表的表示广义表的表示只包括整数和字符型数据的广义表的只包括整数和字符型数据的广义表的只包括整数和字符型数据的广义表的只包括整数和字符型数据的广义表的链表表示链表表示链表表示链表表示 表中套表情形下的广义表的表中套表情形下的广义表的表中套表情形下的广义表的表中套表情形下的广义表的链表表示链表表示链表表示链表表示5232436103914 list25list1 1247as（5,（3,2,（14,9,3）,（）（）,4）,2,（6,3,10）(5,12,s,47,a)第 章 数 组 和 广 义 表 广义表的基本运算，除包括线性表广义表的基本运算，除包括线性表的基本运算外，还有的基本运算外，还有求深度、取表头、求深度、取表头、取表尾、遍历取表尾、遍历等。这些运算中大部分与等。这些运算中大部分与对应的线性表、树或者图的运算类似，对应的线性表、树或者图的运算类似，只是只是取表头取表头和和取表尾取表尾是广义表特有的运是广义表特有的运算。算。