《数据结构-05》由会员分享，可在线阅读，更多相关《数据结构-05（59页珍藏版）》请在金锄头文库上搜索。
1、1,前述各章所讨论的各种数据结构(如线性表，栈和队列等)均是线性结构，结构中的每个元素是无结构的单个字符或其它数据元素。这里所要讨论的是两种新数据结构，结构中的元素本身也可以是具有某种结构的数据。,2,基本概念 数组：按一定格式排列起来的一列同一属性的项目,是相同类型的数据元素的集合。 有一维数组A5、二维数组A55、三维数组A555、多维数组等。 数组的逻辑结构：表中的数据元素本身是数据结构的线性表。 数组的存储结构：由于数组一般不作插入或删除操作， 数组一旦建立则结构中的数据元素个数和元素之间的关系就不再发生变动，故采用顺序存储结构。是一种随机存储结构。,5.1 数组的定义,3,1、数组的
2、逻辑结构定义,ARRAY=(D, R),其中D是数据元素的集合，R是描述下标的关系的集合，由此，对于一维数组有：,Dai| c1id1, ai ElemSet,RR1,c1 ，d1为一维数组下标的下界和上界。,R1 |c1id1-1, ai ai+1D ,4,二维数组：,D=aij| c1i d1, c2 j d2 , aijElemSet ,Row=| c1 i d1 ， c2 j d21 aij, ai, j +1 D ,R=Row, Col,Col=| c1 i d1 1 ，c2 j d2 aij, ai+1 ,j D ,5,n维数组：,D=aj1j2jn | ci jidi 1 i n
3、 (n0) aj1j2 jnElemSet ,R=R1, R2 , Rn,(0, bi-1 )为第i维下标的下界和上界。,6,从其逻辑结构来看，数组实际上是线性表的推广，如一个二维数组可看成如下的线性表：,线性表(x1x2, xn)是把二维数组A看成由n个元素组成的线性表，每个元素是二维数组中的一个列向量。,(x1x2xn),或,(x1x2xm),xi=a1i , a2i , a3i , , ami,7,(x1x 2 xm)是由m个元素组成的线性表，每个元素是一个行向量。,由此可见，一个二维数组可看成是一维数组作为元素而组成的线性表。,8,同样，一个三维数组可看成是其元素为二维数组构成的线性表
4、。,依此类推，对于K维数组，可用其数据元素为k1维数组的线性表定义。,n维数组中数据元素个数为：,在n维数组中，每个元素都受n个关系的约束。由此可见，n维数组是一种较复杂的数据结构，但它可以由简单的数据结构线性表辗转合成而得。,9,n维数组的逻辑特性可归纳为：,（1）每个元素aj1j2 jn都对应于一组下标(j1 j2 jn),（2）每个元素aj1j2 ji jn都有一直接后继aj1j2 ji1 jn (最后一个元素除外),（3）n维数组是一个同构的数据结构，即它的每一个数据元素均属同一数据类型或同一数据结构。,10,2、数组的抽象数据类型的形式定义,ADT Array 数据对象：ji=0,b
5、i-1,i=1,2,n, D=aj1j2jn|n(0)称为数组的维数，bi是数 组第i维的长度，ji是数组元素的第i维 下标，aj1j2jn ElemSet 数据关系：R=R1,R2,Rn Ri=| 0 jk bk-1，1 k n 且ki 0 ji bi2 aj1ji jn , aj1ji+1 jn D，i=2,3,，n,11,基本操作： InitArray(&A,n,bound1,boundn) 操作结果：若维数n和各维长度合法，则构造相应的数组A，并返回OK。 DestroyArray(&A) 操作结果：销毁数组A。 Value(A,&e,index1,indexn) 初始条件：A 是n维
6、数组，e为元素变量，随后是n个下标值。 操作结果：若各下标不越界，则e赋值为所指定的A的元素值，并返回OK。 Assign(&A,e,index1,indexn) 初始条件：A是n维数组，e为元素变量，随后是n个下标值。 操作结果：若下标不越界，则将e的值赋值给所指定的A的元素，并返回OK。 /ADT Array,12,5.2 数组的顺序表示和实现,由于数组的运算一般不包括插入和删除，因此不必考虑数据元素的移动。因而，采用顺序存储方式是较为适宜的。,数组作为一种多维结构，若要将其元素存于一维结构的存储器中，则必须给出一个约定，这个约定就是我们存取数组元素的规则。以二维数组为例，通常可有两种约定
7、：,13,（1）行主次序存取，即把二维数组看成行向量组成的一维结构。,（2）列主次序存取，即把二维数组看成列向量 组成的一维结构。,此方式下的存储映象为：,行主次序:,列主次序:,此方式下的存储映象为：,14,数组的顺序存储是一种随机存取的结构。只要给出数组的一组下标即可确定数据元素在存储中的位置(地址)。以行主次序为例：设二维数组的第一个元素为a00 ,Loci,j表示aij 在存储中的地址，则aij的存储地址为：,l为每个元素占用的存储单元。,15,例：设有数组A(019, 09),=Loc0,0+(10i+j) l 0i 19, 0j 9,当i=3, j=4时：LOC3, 4=Loc0,
8、0+103+4 l,若A0=1, l=1则LOC 3, 4=35,= Loc0,0+34l,由二维数组的访问公式可推导出求n维数组中 的数据元素的存储地址：,16,17,可缩写为：,上式称为n维数组的映像函数。从该式可看出 数组是其下标的线性函数，一旦确定了数组的 各维的长度， Ci就是常数。,18,5.3 矩阵的压缩存储,1、压缩存储：为多个值相同的元素只分配一个 存储空间；对零元不分配空间。,2、特殊矩阵：是指值相同的元素或零元素在矩 阵中的分布有一定的规律。,19,3、稀疏矩阵：零元素的个数远远大于非零元素 的个数。,20,4、 矩阵的压缩存储： 主要是指对一些特殊矩阵的压缩存储，如对称
9、矩阵、三角矩阵、稀疏矩阵等，在这些矩阵中，通常有很多值相同的元素或有很多零元素，对于这类矩阵，可根据其元素在矩阵中的分布规律，只存储其中的部分元素，从而可节省大量的存储空间，如三角矩阵，只存储上三角阵中的元素或只存下三角阵中的元素，对于稀疏矩阵(零元素个数非零元素个数)可只存放其非零元素。,21,5.3.1 特殊矩阵,对称矩阵的存储： 给每一个对称元分配一个存储空间，则n*n个 元所需的空间为：n*(n+1)/2;,对称矩阵： 在n阶矩阵A中，有如下性质： aij=aji; 1=i，j=n,22,下面以行序为主序存储其下三角（包括对角线） 中的元素）：若san(n+1)/2为矩阵A的存储结构，
10、 则sak和矩阵aij存在如下关系：,1、对称矩阵,k=i(i-1)/2+j-1,ij k= j(j-1)/2+i-1,ij,24,以上的存储方法也适用于三角矩阵和对角矩阵。 下（上）三角矩阵：是指矩阵的上（下）三角（不包括对角线）中的元均为常数c 或零的n阶矩阵。其存储：只存储下（上）三角中的元之外，还加一个存储常数c 的存储空间即可。 对角矩阵：所有的非零元都集中在以对角线为中心的带状区域中。即除了主对角线上和直接在对角线上、下方若干对角线上的元之外，所有其他的元皆为零。,2、三角矩阵,Loc(aij)=Loc(a11)+ ( i*(i-1)/2+(j-1) *L,3、对角矩阵,27,28
11、,假设在m*n的矩阵中，有t个元素不为零，若矩 阵稀疏因子（r=t/(m*n)），r=0.05时，称为稀疏矩 阵。,例如：,5.3.2 稀疏矩阵,29,三元组表示法(三列二维数组),设矩阵：,稀疏矩阵的压缩存储方法：,30,M中共有42个元素，而非零元素只有8个，大部分元素都是零元素。如果42个元素都存储，则需占用42个单元，若只存放其非零元素，则只需8个存储单元。为了正确地描述这一矩阵，可用下列三元组的结构存放其非零元：,(i, j, Mij) Mij为非零元素值， i, j为非零元Mij在矩阵M中的行号和列号。则M中非零元可由下列线性表描述。,(1, 2, 12), (1, 3, 9),
12、(3, 1, -3), (3, 6, 14), (4, 3, 24), (5, 2, 18), (6, 1, 15), (6, 4, -7) ),31,该线性表中的元素又是一个由无结构的元素构成的线性表(即一维向量)，因此可以将上表用二维数组表示为：,32,33,1、三元组顺序表 假设以顺序存储结构来表示三元组表，则可得稀疏矩阵的一种压缩存储方式：三元组顺序表。,#define MAXSIZE 12500 typedef struct int i, j; /该非零元的行、列下标 ElemType e; Triple; typedef union Triple dataMAXSIZE+1; in
13、t mu, nu, tu; TSMatrix;,34,a.data,b.data,下面我们讨论如何对三列二维数组表示的稀疏矩阵进行运算（求转置矩阵）：,35,(1) 求转置矩阵,注意：上述三列二维数组存放的非零元是以行主次序存放，则转置后的矩阵，必须仍以行主次序存放。,算法1： 先存放原矩阵中第一列的非零元，然后再存放原矩阵中第二列的非零元，如此类推，直到最后一列。,36,算法2：,算法思想：原矩阵以三列二维数组a存储，转置后的矩阵以三列二维数组b存储。按三元组a的行主次序进行转换，转换后的元素直接存放到b中应有的位置。,附设两个向量:,num 和 cpot ,37,2、行逻辑链接的顺序表 为
14、便于随机存取任意一行的非零元，可将指示行信息的辅助数组cpot固定在稀疏矩阵的存储结构中。称这种“带行链接信息”的三元组表为行逻辑链接的顺序表。,typedef struct Triple dataMAXSIZE+1; /非零元三元组表 int rposMAXRC+1; /各行第一个非零元的位置表 int mu,nu,tu; RLSMatrix;,38,3、十字链表,在矩阵运算时，常常遇到其非零元素个数的变化，以及非零元素在矩阵中的位置变化，(如作加减运算、乘法运算时)。尽管运算的结果可能是稀疏矩阵，若用三元组作为存储结构，因事先不能预计结果矩阵中非零元的个数，不便为三元组分配空间，既使分配足
15、够大的空间，当非零元元素个数变化时，还将作大量的移动。,39,因此，三元组就不适宜在进行这类运算时作为存储结构，而需要采用一种动态的链表结构。为了正确地描述非零元之间的关系，可以将矩阵中的非零元用链指针链接成一个纵横交叉的链表，即称之为十字链表。,40,结点结构：,i：表示非零元在矩阵中的行号,j：表示非零元在矩阵中的列号,e：非零元的值。,right：指向同一行中下一个非零元的指针。,down：指向同一列中下一个非零元的指针。,41,例：,42,1,4,2,2,3,1,2,1,5,M.chead,M.rhead,对应的十字链表,43,5.4 广义表(lists),1、概念：广义表(或称列表lists)可定义为：,Lists=(D, R),其中：Dei| eiAtomSet 或 ei Glist 1i n, n0,R=| ei-1, ei D 2 i n,44,根据定义，广义表的元素ei即可是单个元素，又可以是广义表。为区别起见，我们称eiAtomSet 的元素为“原子”，称eiGlist的元素为“子表”。并以小写字母表示单元素，以大写字母
