1、第 章 数 组 和 广 义 表 第五章 数组q数组的类型定义和表示方法数组的类型定义和表示方法q特殊矩阵和稀疏矩阵存储方法特殊矩阵和稀疏矩阵存储方法 及运算的实现及运算的实现q广义表的结构特点广义表的结构特点第 章 数 组 和 广 义 表 5.1.1 二维数组的定义二维数组的定义n定义定义mnmmnnnmaaaaaaaaaA.212222111211数组特点数组特点数组结构固定数组结构固定数据元素同构数据元素同构数组运算数组运算给定一组下标，存取相应的数据元素给定一组下标，存取相应的数据元素给定一组下标，修改数据元素的值给定一组下标，修改数据元素的值()()()()()()()()()数组是一
2、组有固定数组是一组有固定（一（一旦定义了数组的维数和旦定义了数组的维数和每一维的上下限个数）每一维的上下限个数）的元素的集合。的元素的集合。由于这由于这个性质，使得对数组的个性质，使得对数组的操作不像对线性表的操操作不像对线性表的操作那样可以在表中任意作那样可以在表中任意一个合法的位置插入或一个合法的位置插入或删除一个元素。对于数删除一个元素。对于数组的操作一般只有两类：组的操作一般只有两类：数组可以看成是一种特殊的线性表，即线性表数组可以看成是一种特殊的线性表，即线性表中数据元素本身也是一个线性表中数据元素本身也是一个线性表第 章 数 组 和 广 义 表 矩阵矩阵A Am mn n看成看成n
3、 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,m3 3LOC(i1,i2,i3)=a+(i1*m2
5、*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 第 章 数 组 和 广 义 表 11121110122221201112111010020100nnnnnnnnaaaaaaaaaaaaaaaa对称阵下三角矩阵5.2.1 特殊矩阵特殊矩阵第 章 数 组 和 广 义 表 1112111012222120111
6、2111010020100nnnnnnnnaaaaaaaaaaaaaaaa对对称称阵阵的的上上三三角角矩矩阵阵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 a32 an-1n-1 存存下下三三角角第 章 数 组 和 广 义 表=j*(j+1)/2+i 前i行元素总数 第i行第j个元素前元素个数第 章 数 组 和 广 义 表 3
7、3323130232221201312111003020100aaaaaaaaaaaaaaaa上三角矩阵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)+(n-i+1)+j-i=(2*n-i+1)*i/2+j-
8、i=(2*n-i-1)*i/2+j 若若i j，数组元素，数组元素Aij在矩阵的下三角部分，在在矩阵的下三角部分，在数组数组 B 中没有存放。因此，找它的对称元素中没有存放。因此，找它的对称元素Aji。Aji在数组在数组 B 的第的第(2*n-j-1)*j/2+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
9、)/2 n(n+1)/2-1 按行序为主序：ji 时aij为0一个元素所占字节数一个元素所占字节数下标从下标从1开始开始第 章 数 组 和 广 义 表 1121122232232221121110010000000000000000000AnnnnnnnnnnaaaaaaaaaaaaaB 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三对角矩阵中除主对角线及在主对角
10、线上下最临三对角矩阵中除主对角线及在主对角线上下最临近的两条对角线上的元素外，所有其它元素均为近的两条对角线上的元素外，所有其它元素均为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 A
11、ij 在第在第 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=1
12、0-2*3=4不第 章 数 组 和 广 义 表 n对角矩阵(这是三对角阵，如是K对角则要求K是奇数)a11 a12 0 .0 a21 a22 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起起第 章 数
13、 组 和 广 义 表 5.2.2 稀疏矩阵稀疏矩阵定义：定义：非零元较零元少，且分非零元较零元少，且分布没有一定规律的矩阵布没有一定规律的矩阵压缩存储原则：压缩存储原则：只存矩阵的行只存矩阵的行列维数和每个非零元的行列下列维数和每个非零元的行列下标及其值标及其值第 章 数 组 和 广 义 表 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）唯一确定例如：例如：第 章 数 组 和
14、 广 义 表 稀疏矩阵的压缩存储方法稀疏矩阵的压缩存储方法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第 章 数 组 和 广 义 表 7600070015000001800000240001400003000000000009120Amai j v0 1 2 3 4 5 6 7 86 7 8 1 2 12 1 3 9 3 1
15、-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;rowm;row+)Bcolrow=Arowcol;时间复杂度：时间复杂度：T(n)=O(m n)第 章 数 组 和 广 义 表 760007001500000180000024000140000300000000000912
16、0A6700000000014000000007000000024009018000121500300B6 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?按行序存放按行序存放第 章 数 组 和 广 义 表 解决思路：解决思路：只要做到只要做到 将矩阵行、列维数互换将矩阵行、列维数互换 将每个三元组中的将每个
17、三元组中的i和和j相互调换相互调换 重排三元组次序，使重排三元组次序，使mb中元素以中元素以B的行的行(A的列的列)为主序为主序算法描述：算法分析：T(n)=O(A的列数n非零元个数t)若 t 与mn同数量级，则)()(2nmOnT方法一：按原矩阵方法一：按原矩阵A的列序转置的列序转置,来得到来得到A的转置矩阵的转置矩阵B 因为在因为在ma是阵是阵A的按行优先存放的三元组表，要想从的按行优先存放的三元组表，要想从ma得到得到mb。即按。即按mb中三元组次序依次在中三元组次序依次在ma中找到相应的三元组进行转中找到相应的三元组进行转置。为找到置。为找到A中每一列所有非零元素，需对其三元组表中每一
18、列所有非零元素，需对其三元组表ma从第一从第一个元素起扫描一遍。由于个元素起扫描一遍。由于ma中以中以A行序为主序行序为主序,所以由此得到的恰所以由此得到的恰是是mb中应有的顺序中应有的顺序第 章 数 组 和 广 义 表 由于我们已按行优先将阵由于我们已按行优先将阵A中的非零元存储到三中的非零元存储到三元组表元组表ma中了，现在的问题就是如何由中了，现在的问题就是如何由ma得到得到mb！思路是：思路是：按按ma中三元组次序转置，转置结果放入中三元组次序转置，转置结果放入mb中恰当位置。此法关键是要预先确定原矩阵中恰当位置。此法关键是要预先确定原矩阵A中每中每一列第一个非零元在一列第一个非零元在
19、mb中位置，为确定这些位置，中位置，为确定这些位置，转置前应先求得转置前应先求得A的每一列中非零元个数。的每一列中非零元个数。方法二：按行序转置（快速转置）方法二：按行序转置（快速转置）即如何得到阵即如何得到阵A的按列优先排列的非零元三元组表的按列优先排列的非零元三元组表mb?第 章 数 组 和 广 义 表 设两个数组设两个数组numcol：表示矩阵：表示矩阵A中第中第col列中非零元个数列中非零元个数cpotcol：指示：指示A中第中第col列第一个非零元在列第一个非零元在mb中的位置中的位置显然有：显然有：cpot1=1;cpotcol=cpotcol-1+numcol-1;(2col m
20、a0.j)1357889colnumcolcpotcol122232415061707600070015000001800000240001400003000000000009120A矩阵矩阵A的列数的列数第 章 数 组 和 广 义 表 算法描述：算法描述：算法分析：算法分析：T(n)=O(A的列数的列数n+非零元个数非零元个数t)若若 t 与与m n同数量级，则同数量级，则T(n)=O(m n)第 章 数 组 和 广 义 表 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 i j v0 1 2 3 4 5 6 7 8m
21、ai j v0 1 2 3 4 5 6 7 8mbcolnumcolcpotcol1122323524715806817907 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 pppppppp4629753第 章 数 组 和 广 义 表 7 0 0 0 15 0 0 -4 0 0 0 0 -2 0 0 0 0 21 0 0 0 -1 0 0A=22-41515 41-2 4621 11734-1 i j edown right希疏矩阵的链式存储结构希疏矩阵的链式存储结构第 章 数 组 和 广 义 表 5.3 广义表 广义表广
22、义表(Lists)(Lists)也称为也称为列表列表，它是线性表，它是线性表的推广。大家知道，线性表是的推广。大家知道，线性表是n n（n n0 0）个）个元素元素a a1 1，a a2 2，a ai i，a an n的有限序列。的有限序列。其中，线性表的元素仅限于原子项，所谓其中，线性表的元素仅限于原子项，所谓原原子子，指的是结构上不可再分割的一种成分，指的是结构上不可再分割的一种成分，它可以是一个数，或者是一个结构。如果放它可以是一个数，或者是一个结构。如果放松对线性表元素的这种限制，允许它们具有松对线性表元素的这种限制，允许它们具有其自身独立的类型结构，那么就产生了广义其自身独立的类型结
23、构，那么就产生了广义表的概念。表的概念。第 章 数 组 和 广 义 表 LS=(a0,a1,a2,an-1)LS第 章 数 组 和 广 义 表 广义表通常用圆括号括起来，用逗号广义表通常用圆括号括起来，用逗号分隔其中的元素。分隔其中的元素。n为区分原子和广义表，用大写字母表示为区分原子和广义表，用大写字母表示广义表，用小写字母表示原子。广义表，用小写字母表示原子。n表尾一定是子表。但表头可以是原子，表尾一定是子表。但表头可以是原子，也可以是子表。也可以是子表。n广义表是递归定义的，因为在定义广义广义表是递归定义的，因为在定义广义表时又用到了广义表的概念。表时又用到了广义表的概念。需要注意的是：
24、需要注意的是：第 章 数 组 和 广 义 表 广义表是一个广义表是一个多层次多层次的的线性结构线性结构。例如。例如:有有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)
25、E=(a,E)这是一个递归的表这是一个递归的表,它的长度为它的长度为2,E相当于一个无限的列表相当于一个无限的列表E=(a,(a,(a,.)第 章 数 组 和 广 义 表 1)1)广义表中的数据元素有相对广义表中的数据元素有相对次序次序;2)2)广义表的广义表的长度长度定义为最外层包含的元素个数定义为最外层包含的元素个数;3)3)广义表的广义表的深度深度定义为所含括弧的重数定义为所含括弧的重数;注意注意:“:“原子原子”的深度为的深度为“0”;“0”;“空表空表”的深度的深度为为1 14)4)表头可以是原子或列表表头可以是原子或列表;表尾必定是列表。表尾必定是列表。5)5)广义表可以是一个广义
26、表可以是一个递归递归的表的表;递归表的深度是无穷值，长度是有限值。递归表的深度是无穷值，长度是有限值。广义表的结构特点广义表的结构特点:第 章 数 组 和 广 义 表 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(
27、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)
28、=(),(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)aD(e)D=(a,D)y递递归归表表线性表线性表再入表再入表第
29、章 数 组 和 广 义 表 与与树树对应的广义表称为对应的广义表称为纯表（纯表（Pure ListPure List），这种表中没有共享和递归的成分，即没有任何这种表中没有共享和递归的成分，即没有任何成分出现多次，它限制了表中成分的共享和递成分出现多次，它限制了表中成分的共享和递归，例如图中的归，例如图中的(a)(a)，(b)(b)，(c)(c)都是纯表；都是纯表；与与有向无环图有向无环图对应的表称为对应的表称为再入表再入表，这种表存，这种表存在元素共享，在图中表现为存在结点共享，例在元素共享，在图中表现为存在结点共享，例如图中如图中 (d)(d)，子表，子表A A是共享结点，它既是是共享结点
30、，它既是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)第 章 数 组 和 广 义 表 广义表的基本运算，除包括线性表广义表的基本运算，除包括线性表的基本运算外，还有的基本运算外，还有求深度、取表头、求深度、取表头、取表尾、遍历取表尾、遍历等。这些运算中大部分与等。这些运算中大部分与对应的线性表、树或者图的运算类似，对应的线性表、树或者图的运算类似，只是只是取表头取表头和和取表尾取表尾是广义表特有的运是广义表特有的运算。算。
