数组和广义表线性表的扩展表中的数据元素本身.ppt

Data Structure,第5章 数组和广义表 线性表的扩展：表中的数据元素本身也是一个数据结构,5.1 数组的定义 5.2 数组的顺序表示和实现 5.3 矩阵的压缩存储 5.3.1 特殊矩阵 5.3.2 稀疏矩阵,Data Structure,一、教学目的与要求 理解数组的定义、顺序表示和实现；矩阵的压缩存储；广义表的定义和存储结构 二、主要教学内容 数组的定义；数组的顺序表示和实现；矩阵的压缩存储、特殊矩阵、稀疏矩阵；广义表的定义、广义表的存储结构 三、教学重点、难点 多维数组、特殊矩阵、稀疏矩阵、广义表的存储结构 四、授课方法及手段 采用多媒体大屏幕投影授课 五、讲课具体内容（讲稿）,Data Structure,ADT Array 数据对象： ji=0,bi-1,I=1,2,n; D = aj1j2.jn | n(0)称为数组的维数,bi是数组第i维的长度, ji是数组元素的第i维下标, aj1j2. . .jnElemset 数据关系： R=R1 , R2 . Rn Ri = aj1.ji.jn, aj1.ji+1.jn | 对每一维是线性的 0jkbk-1, 1kn 且ki 0jibi-2, aj1.ji.jn, aj1.ji+1.jnD,I=2,n 基本操作： InitArray( ADT Array,5.1 数组的定义,Data Structure,二维数组的类型定义: typedef ElemType Array2mn; Array2 A; 等价于： typedef ElemType Array1n; typedef Array1 Array2m; Array2 A;,维数和维界,Data Structure,a00 a01 a02 . A0,n-1 a10 a11 a12 . A1,n-1 Amxn= am-1,0 am-1,1 am-1,2 . Am-1,n-1 Amn=( (a00,a01,.a0,n-1), (a10,a11,.a1,n-1), ., (am-1,0,am-1,1,.am-1,n-1) ),二维的数组 = 定长的线性表,Data Structure,5.2 数组的顺序表示和实现,除了初始化和销毁之外, 数组一般只有存取操作和修改元素值的操作， 也没有插入和删除操作。 存储时一般以行序为主序:(如C语言, PASCAL, BASIC等) Amxn=(a00,a01,.a0,n-1,a10,a11,.a1,n-1,.,am-1,0, am-1,1,.am-1,n-1),Data Structure,二维数组的存储,LOC0,0为基地址,二维数组Ab1b2中元素aij的存储位置为: LOCi,j=LOC0,0+(b2i+j)L 0=i=b1-1 0=j=b2-1 L每个数据元素所占的存储空间大小,Data Structure,例5.1: 若 L=2, LOC0,0 = 1000，求LOC2,3,LOC2,3 = LOC0,0 + (5*2+3)*L = 1000 + 13 * 2 = 1026,Data Structure,三维数组的存储,若LOC0,0,0 为基地址: LOCi,j,k = LOC0,0,0+ (n*h*i+h*j+k)*L 0 = i m 0 = j n 0 = k h 每个数据元素占L个存储单元,Data Structure,N维数组存储,b1,b2,.,bn是n维数组A每一维的维界,数组元素A(j1,j2,.,jn)的存储位置为： LOCj1,j2,.jn=LOC0,0,.,0 + (b2b3bnj1 + b3bnj2 + . + bnjn-1 + jn )L,Data Structure,Data Structure,例: 在C语言中,设数组A5678的首地址为2000,每个元素占2个字节；求元素A3454的地址。 LOC3,4,5,4 = 2000+(6*7*8*3+7*8*4+8*5+4)*2 = 2000+(1008+224+40+4)*2 = 4552,Data Structure,数组顺序存储的表示和实现,#incluse #define MAX_ARRAY_DIM 8 typedef struct ElemType *base; int dim; int *bounds; int *constants; Array;,Data Structure,Data Structure,10 11 12 13 20 21 22 23 30 31 32 33,A =,3,.,4,8,2,10,11,31,32,33,= 2,Data Structure,5.3 矩阵的压缩存储,矩 阵: 二维数组 特殊矩阵: 大量重复元素或大量0元素 稀疏矩阵: 大量0元素 压缩存储: 重复元素只分配一个存储空间, 0元素不分配存储空间,Data Structure,5.3.1 特殊矩阵,对 称 矩阵: aij = aji (11时, aij = 0, (1=i,j=n),Data Structure,对称矩阵: aij = aji (1=i , j=n),存储元素数 : 1+2+.+n = n(n+1)/2,Data Structure,用一维数组SA0n(n+1)/2-1存储矩阵A下三角元素: SAk=a11,a21,a22,a31,a33,an1,ann （k = 1,2,n(n+1)/2） SAk和Ai,j的一一对应关系: i(i-1)/2+j-1 当i=j（下三角含对角线） k= j(j-1)/2+i-1 当ij （上三角）,Data Structure,例5.3 对称矩阵,n = 5, 1+2+3+4+5 = 5*(5+1)/2 = 15 一维数组SA014作为数组A的存储结构: SA=(4 5 2 3 1 3 2 5 2 8 1 6 7 9 5) 如: a5,3 = a3,5 = 7 k = 5(5-1)/2 + 3 -1= 12 故: sa12 = 7,Data Structure,下三角矩阵:当ij时,aij=0,(1=i,j=n),同样用一维数组SA0n(n+1)/2-1作为数组A非零元素的存储结构: sak和ai,j的一一对应关系: sak,k=i(i-1)/2+j-1 (当i=j) ai,j= 0 (当ij),Data Structure,例5.4 下三角矩阵,4 0 0 0 0 5 2 0 0 0 A = 3 1 3 0 0 2 5 2 8 0 1 6 7 9 5 如: a5,3 = 7 k = 5(5-1)/2 + 3 - 1 = 12 故: sa12 = 7 （但：a3,5 = 0）,Data Structure,三对角矩阵: 当|i-j| 1时, aij = 0, (1=i,j=n),a11 a12 0 0 . 0 a21 a22 a23 0 . 0 Ann = 0 a32 a33 a34 . 0 an-1n 0 0 0 . ann-1 ann,Data Structure,一维数组SA03*n-3作为数组A三角元素的存储结构: SAk=a11,a12,a21,a22,a23,a32,.,ann-1,ann （k=0,2,3,4,5,6,3n-3,3n-3） sak和ai,j的一一对应关系: sak,k=3*(i-1)+j-i， 当|i-j|1,Data Structure,例5.5 三对角矩阵,4 3 0 0 0 5 2 2 0 0 A = 0 1 0 4 0 0 0 2 8 7 0 0 0 9 5 一维数组SA03*5-3作为数组A的存储结构: SA=(4 3 5 2 2 1 0 4 2 8 7 9 5) 如: a5,4 = 9 k = 3*(5-1) + 4 - 5 = 11 故: sa11 = 9,Data Structure,5.3.2 稀疏矩阵,稀疏因子：假设在mn的矩阵中，有t个元素不为零。令=t/(mn)，称为矩阵的稀疏因子，通常稀疏因子0.05时称为稀疏矩阵。 0 12 9 0 0 0 0 0 0 0 0 0 0 0 M(67) = -3 0 0 0 0 14 0 0 0 24 0 0 0 0 0 18 0 0 0 0 0 15 0 0 -7 0 0 0,Data Structure,转置矩阵,0 0 -3 0 0 15 12 0 0 0 18 0 9 0 0 24 0 0 T(76) = 0 0 0 0 0 -7 0 0 0 0 0 0 0 0 14 0 0 0 0 0 0 0 0 0,Data Structure,稀疏矩阵的存储结构 一. 三元组顺序表,M: i j e T: i j e 1 2 12 1 3 -3 1 3 9 1 6 15 3 1 -3 2 1 12 3 6 14 2 5 18 4 3 24 3 1 9 5 2 18 3 4 24 6 1 15 4 6 -7 6 4 -7 6 3 14,Data Structure,三元组顺序表结构定义,#define MAXSIZE 12500 typedef struct int i, j; Elemtype e; Triple;,typedef struct Triple dataMAXSIZE+1; int mu,nu,tu; TSMatrix; TSMatrix M, T;,Data Structure,Data Structure,求稀疏矩阵M的转置矩阵T,方法：1. 将矩阵的行列值相互交换； 2. 将每个三元组中的i、j相互调换； 3. 重排三元组之间的次序。,Data Structure,算法5.1：求稀疏矩阵M的转置矩阵T,Status TransposeSMatrix(TSMatrix M,TSMatrix /TransposeSMatrix,算法复杂度： O(nu*tu),Data Structure,算法5.2：求转置矩阵的快速方法,为了减少算法复杂度,增加两个向量num和cpot: numcol: M中第 col 列中非零元素的个数; cpotcol: M中第col列中的第一个非零元素在T.data中的位置; 有: cpot1 = 1; cpotcol=cpotcol-1+numcol-1; （2=col=m.nu）,Data Structure,例5.6 0 12 9 0 0 0 0 0 0 0 0 0 0 0 M= -3 0 0 0 0 14 0 0 0 24 0 0 0 0 0 18 0 0 0 0 0 15 0 0 -7 0 0 0 上例中的向量num和cpot: col 1 2 3 4 5 6 7 num 2 2 2 1 0 1 0 cpot 1 3 5 7 8 8 9,Data Structure,i j v,i j v,3 4 24,1 6 15,3 1 9,6 3 14,2 5 18,T ,1 3 -3,2 1 12,4 6 -7,col 1 2 3 4 5 6 7 cpot 1 3 5 7 8 8 9,4,6,2,9,7,5,3,8,M ,Data Structure,Status FastTransposeSMatrix(TSMatrix M,TSMatrix / FastTransposeSMatrix,算法复杂度： O(nu+tu),Data Structure,三元组顺序表（有序的双下标法）小结 特点/优点： 非零元在表中按行序有序存储，便于进行依行序顺序处理的矩阵运算。 缺点： 若需按行号存取某一行的非零元，则需从头开始进行查找。,Data Structure,#define MAXRC 100 typedef struct int i, j; Elemtype e; Triple;,二、行逻辑链接的顺序表 （指出每一行的第一个非零元素在三元组中的位置）,typedef struct Triple dataMAXSIZE+1; int rposMAXRC+ 1; int mu,nu,tu; RLSMatrix;,Data Structure,M.datap .i .j .e,0 1 2 ,maxsize,M.rposrow,Data Structure,三、十字链表 （行和列都是线性链表非线性结构）,当矩阵的非零元个数和位置在操作过程中变化较大时，不宜采用顺序存储结构，采用链式存储结构表示更恰当。 十字链表的表示法是稀疏矩阵的链式存储方法之一，其基本思想为：将稀疏矩阵同一行的所有非零元素串成一个带表头的环形链表，同一列的所有非零元素也串成一个带表头的环形链表。因此，在十字链表的表示中有两类结点，非零元素结点和表头结点。,Data Structure,非零元素结点：,表头结点：,十字链表：,Data Structure,1 什么是广义表 广义表也称为列表，是线性表的一种扩展，也是数据元素的有限序列。 记作：LS= (d1, d2, . . . . . .dn)。其中di既可以是单个元素，也可以是广义表。 说明 1）广义表的定义是一个递归定义，因为在描述广义表时又用到了广义表； 2）在线性表中数据元素是单个元素，而在广义表中， 元素可以是单个元素, 称为单元素(原子)，也可以是广义表，称为广义表的子表； 3）n 是广义表长度；,5.4 广义表,Data Structure,4）下面是一些广义表的例子： A = ( ) 空表，表长为0 B = (a,(b,c,d) B的表长为2，两个元素分别为 a 和子表（b,c,d) C = (e) C中只有一个元素e，表长为1 D = (A,B,C,f ) D 的表长为4，它的前三个元素 A，B，C是 广义表，第四个是单元素 E=( a ,E )