数据结构课件：第5章 数组与广义表

1、第5章 数组与广义表第 2 页5.1 数组的概念数量固定，数据类型相同的（变量）元素组合在一起。使用一个名称代表它。这个名称就是数组名。如果要访问其中某个元素(变量)，可以使用元素的索引值(下标)来访问它。在C语言中，数组元素的索引值从0开始。 int A3010; int Ac1.d1, c2.d2 一般情况：子界类型第 3 页5.1 数组的概念数组的逻辑结构1. 线性结构扩展AMN=a0 0 a0 1 a0 N-1a1 0 a1 1 a1 N-1aM-1 0 aM-1 1 aM-1 N-1 A=(A0，A1，AN-1) 其中： Ai=(a0i, a1i, , Am-1i) (0iN-1)二

2、维数组是数据元素为线性表的线性表第 4 页5.1 数组的概念数组的逻辑结构2. 二维数组中的每个元素都受两个线性关系的约束行关系、列关系AMN=a0 0 a0 1 a0 N-1a1 0 a1 1 a1 N-1aM-1 0 aM-1 1 aM-1 N-1在行关系中 aij 直接前趋是 aij-1 aij 直接后继是 aij+1在列关系中 aij 直接前趋是 ai-1j aij 直接后继是 ai+1jN维数组中的每个元素都受N个线性关系的约束第 5 页5.1 数组的概念数组的基本操作初始化操作 InitArray(&A,n,bound1,boundn)销毁操作 DestroyArray(&A)读元

3、素操作 Value(A,&e,index1,indexn)写元素操作 Assign(&A,e,index1,indexn) 在高级语言中的典型体现： int AMN; Aij = x; 写 y = Aij; 读AMN=a0 0 a0 1 a0 N-1a1 0 a1 1 a1 N-1aM-1 0 aM-1 1 aM-1 N-1第 6 页5.1 数组的概念数组的基本操作1. 读：给定一组下标，读出对应的数组元素；2. 写：给定一组下标，存储或修改与其相对应的数组元素。读/写操作本质上只对应一种操作寻址。确定指定元素在内存中的物理地址。数组的存储两种形式：既可以是顺序存储，也可以采用链式结构。第 7

4、 页5.2 数组的存储和实现数组的存储结构与寻址一维数组设具有M个元素的一维数组的下标范围为闭区间 0, M-1，每个数组元素占用 L 个存储单元。L a0 ai-1 ai aM-1 a1 Loc(a0)Loc(ai)ai 的存储地址：Loc( ai )Loc(a0)iL 第 8 页5.2 数组的存储和实现数组的存储结构与寻址二维数组常用的映射方法有两种：按行优先：先行后列，先存储行号较小的元素，行号相同者先存储列号较小的元素。按列优先：先列后行，先存储列号较小的元素，列号相同者先存储行号较小的元素。 二维数组内 存二维结构一维结构第 9 页5.2 数组的存储和实现二维数组按行优先（MN）0N

5、-1 0M-1aij前面的元素个数 = 阴影部分的面积= 整行数每行元素个数 + 本行中aij前面的元素个数= i Nj本行中 aij 前面的元素个数每行元素个数整行数aijLoc(aij) = Loc(a00)( Nij )L第 10 页5.2 数组的存储和实现二维数组按行优先的更一般情况l2h2 l1h1aij前面的元素个数 = 阴影部分的面积= 整行数每行元素个数 + 本行中aij前面的元素个数= (i -l1)(h2 -l21)(j -l2)aijLoc(aij)Loc(al1 l2) + (i-l1)(h2-l2+1) + (j-l2)L本行中 aij 前面的元素个数每行元素个数整行

6、数第 11 页5.2 数组的存储和实现三维数组三维数组：Am1, m2, m3：Loc(aijk ) = Loc(a000) +( im2m3 + jm3 + k )L 第 12 页5.2 数组的存储和实现N维数组一般的N维数组：Ab1, b2, , bn： Loc( j1, j2, , jn ) = Loc(0, 0, , 0) + ci ji其中：cn=L，ci-1 =bici，1in。ni=1数组基址Ci为常数第 13 页5.2 数组的存储和实现二维数组静态数组表示法typedef ElemType Arraym*n; Array A; Amn=a0 0 a0 1 a0 n-1a1 0

7、a1 1 a1 n-1 am-1 0 am-1 1 am-1 n-1a00.a0n-1a10.a1n-1.am-1 0.am-1 n-1第 14 页5.2 数组的存储和实现数组的动态表示法typedef struct ElemType *base; / 动态空间基址 int dim; / 数组维数 int *bound； / 维界基址 int *constants; / 数组映像函数常量基址 Array;A.baseA.dimA.boundsA.constantsb1 b2 b3c1 c2 c3a000 a0013Ab1b2b3第 15 页5.3 矩阵的压缩存储 为了节省存储空间，时常会对某些

8、矩阵进行压缩存储。所谓压缩存储：1）对多个值相同的元只分配一个存储空间；2）对零元不分配存储空间。5.3.1 特殊矩阵的压缩存储5.3.2 稀疏矩阵的压缩存储第 16 页5.3.1 特殊矩阵 值相同元素或者非零元素的分布有一定规律的矩阵，称为特殊矩阵。 对称矩阵、 上（下）三角矩阵。a11 a12 a1na21 a22 a2n am1 am2 amna11 a12 a1n0 a22 a2n 0 0 amn第 17 页5.3.1 特殊矩阵对称矩阵/上（下）三角矩阵用一维数组，按行优先存储下三角元素。a11 a12 a13 a14 a1na21 a22 a23 a24 a2na31 a32 a33

9、 a34 a3nan1 an2 an3 an4 anna11 a21 a22 a31 a32 a33 an1 an2 ann 0 1 2 3 4 5 n(n+1)/2-1k =i(i-1)/2+j-1 当 i jj(j-1)/2+i-1 当 i j性质：aij = aji 1i, jn对于下标i, j，线性地址第 18 页5.3.2 稀疏矩阵 含有较多值相同元素或较多零元素，且值相同元素或者零元素分布没有一定规律的矩阵称为稀疏矩阵。 讨论含有较多零元素的稀疏矩阵的压缩存储。M = 0 12 9 0 0 0 0 0 0 0 0 0 0 0-3 0 0 0 0 14 0 0 0 24 0 0 0

10、0 0 18 0 0 0 0 015 0 0 -7 0 0 0M有42（67）个元素，有8个非零元素如何进行稀疏矩阵的压缩存储？第 19 页5.3.2 稀疏矩阵三元组顺序表M = 0 12 9 0 0 0 0 0 0 0 0 0 0 0-3 0 0 0 0 14 0 0 0 24 0 0 0 0 0 18 0 0 0 0 015 0 0 -7 0 0 0采用三元组存储：(行, 列, 值)( (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 第 20 页5.3.2 稀

11、疏矩阵三元组顺序表 #define MAXSIZE 12500 typedef struct int i,j; / 非零元的行下标和列下标 ElemType e; / 非零元值 Triple; typedef struct Triple data MAXSIZE+1 ; / 用于存储三元组表, data0未用 int mu,nu,tu; / 行数、列数和非零元个数 TSMatrix;第 21 页5.3.2 稀疏矩阵三元组表的顺序存储M = 0 12 9 0 0 0 0 0 0 0 0 0 0 0-3 0 0 0 0 14 0 0 0 24 0 0 0 0 0 18 0 0 0 0 015 0

12、0 -7 0 0 0i j e12345678M.dataM.muM.nuM.tu3 1 -36 1 151 2 125 2 181 3 94 3 246 4 -73 6 14678 按行（行内按列）顺序存储非零元素。第 22 页5.3.2 稀疏矩阵三元组表的顺序存储转置算法M = 0 12 9 0 0 0 0 0 0 0 0 0 0 0-3 0 0 0 0 14 0 0 0 24 0 0 0 0 0 18 0 0 0 0 015 0 0 -7 0 0 0 T = 0 0 -3 0 0 1512 0 0 0 18 0 9 0 0 24 0 0 0 0 0 0 0 -7 0 0 0 0 0 0

13、0 0 14 0 0 0 0 0 0 0 0 0 基本算法：交换对应行、列位置上的元素。第 23 页5.3.2 稀疏矩阵一般矩阵的转置算法 int amn,bmn; for ( i =0; im; +i ) for (j = 0; jn; +j ) b j i = a i j ; 算法的时间复杂度为：O(m*n)第 24 页5.3.2 稀疏矩阵i j e12345678M.dataM.muM.nuM.tu3 1 -36 1 151 2 125 2 181 3 94 3 246 4 -73 6 146782 1 124 6 -71 3 -33 4 241 6 153 1 96 3 142 5 1

14、8i j e12345678T.dataT.muT.nuT.tu768第 25 页5.3.2 稀疏矩阵转置运算算法TransposeSMatrix(TSMatrix M, TSMatrix &T) 基本思想 对 M.data 从头至尾扫描： 第一次扫描时，将 M.data 中列号为 1 的三元组赋值到 T.data 中； 第二次扫描时，将 M.data 中列号为 2 的三元组赋值到T.data中； 依此类推，直至将 M.data 所有三元组赋值到T.data 中。第 26 页1 2 121 3 93 1 -33 6 144 3 245 2 186 1 156 4 -7i j vi j v3 1

15、 -32 5 181 3 -36 1 151 6 151 2 122 1 125 2 181 3 93 1 94 3 243 4 246 4 -74 6 -73 6 146 3 14M.dataT.data第一次扫描查找第1列元素第一次扫描结束第二次扫描结束第二次扫描查找第2列元素第三次扫描查找第3列元素第四次扫描查找第4列元素第五次扫描查找第5列元素第六次扫描查找第6列元素5.3.2 稀疏矩阵第七次扫描查找第7列元素三元组表的顺序存储转置算法第 27 页5.3.2 稀疏矩阵Status TranMatrix( TSMatrix M, TSMatrix &T ) T.mu=M.nu; T.nu

16、=M.mu; T.tu=M.tu; if ( T.tu ) / 非零元素个数!=0 q=1; / q为当前三元组在T.data 存储位置(下标) for ( col=1; col=M.nu; +col ) for (p=1;p=M.tu;+p) /p为扫描M.data指示器 if ( M.datap.j= =col ) T.dataq.i = M.datap.j; T.dataq.j = M.datap.i; T.dataq.e = M.datap.e; +q; / if return OK; / TranMtrix算法的时间复杂度：O(nu*tu)第 28 页5.3.2 稀疏矩阵时间复杂度分

17、析转置算法 TranMatrix 的时间复杂度为O(nutu) 当非零元的个数tu和矩阵元素个数 munu 同数量级时，转置运算算法的时间复杂度为 O(nu munu)算法一般用于 tu munu 的情况第 29 页5.3.2 稀疏矩阵提高算法效率numcol：存储M第 col 列非零元个数cpotcol：存储M第 col 列第一个非零元在T.data 中的位置1 2 121 3 93 1 -33 6 144 3 245 2 186 1 156 4 -7i j vM.datacpotcol的计算方法： cpot1 = 1 cpotcol = cpotcol-1 + numcol-1 2 col

18、 ncolnumcolcpotcol1 2 3 4 5 6 7 22811012785309第 30 页5.3.2 稀疏矩阵第3列第二个非零元在b中的位置1 2 121 3 93 1 -33 6 144 3 245 2 186 1 156 4 -7colnumcolcpotcol1 2 3 4 5 6 7 228110135278M.dataT.data1 2 122 1 12第2列第一个非零元在b中的位置1 3 9第3列第一个非零元在b中的位置3 1 93 1 -31 3 -33 6 146 3 144 3 243 4 245 2 182 5 186 1 151 6 156 4 -74 6

19、-74第2列第二个非零元在b中的位置65第4列第二个非零元在b中的位置第1列第一个非零元在b中的位置2793第6列第一个非零元在b中的位置扫描M.data实现M到T 的转置809第 31 页5.3.2 稀疏矩阵Status FastTransMatrix(TSMatrix M, TSMatrix &T) /采用三元组顺序表存储稀疏矩阵，求M的转置矩阵T T.mu=M.nu; T.nu=M.mu; T.tu=M.tu; if ( T.tu ) for ( col=1; col=M.nu; +col ) numcol=0; / 求M中每一列非零元个数 for ( t=1; t=M.tu; +t )

20、 + num M.datat.j ; /求第 col列中第一个非零元在T.data中的序号 cpot1 = 1; for ( col=2; col=M.nu; +col ) cpotcol = cpotcol-1 + numcol-1;第 32 页5.3.2 稀疏矩阵 for ( p=1; pM.tu; +p ) col = M.data p .j; q = cpotcol; T.dataq.i = M.datap.j; T.dataq.j = M.datap.i; T.dataq.e = M.datap.e; + cpot col ; / for / if return OK; / Fast

21、TranMatrix时间复杂度分析算法中有四个并列的单循环，循环次数分别为 nu、tu、nu 和 tu，时间复杂度为：O(nu+tu)第 33 页5.3.2 稀疏矩阵 行逻辑链接顺序表 #define MAXMN 500 typedef struct Triple data MAXSIZE+1 ; int rposMAXMN+1; / 每行第一个元素的位置表 int mu, nu, tu; RLSMatrix; 1 2 121 3 93 1 -33 6 144 3 245 2 186 1 156 4 -7123456M.rpos M.muM.nuM.tu678103567第 34 页5.3.2

22、 稀疏矩阵例：给定一组下标，求矩阵指定元素的值ElemType value(RLSMatrix M, int r, int c) p = M.rposr; while ( M.datap.i=r & M.datap.j c ) p+; if (M.datap.i=r & M.datap.j=c) return M.datap.e; else return 0; /value第 35 页5.3.2 稀疏矩阵 稀疏矩阵的链式存储十字链表 采用链式存储结构存储三元组表，每个非零元素对应的三元组存储为一个链表结点：rowcolitemdownrightrow： 存储非零元素的行号col： 存储非零元素

23、的列号item： 存储非零元素的值right： 指针域，指向同一行中的下一个三元组down：指针域，指向同一列中的下一个三元组第 36 页5.3.2 稀疏矩阵 稀疏矩阵的链式存储十字链表3 0 0 50 -1 0 02 0 0 0M=1 1 33 1 22 2 -11 4 5M.cheadM.rhead第 37 页5.3.2 稀疏矩阵 十字链表的类型定义typedef struct OLNode int row, col; / 非零元的行下标和列下标 ElemType e; / 非零元值 struct OLNode * right, * down OLNode,OLink;typedef st

24、ruct OLink *rhead,*chead; / 行/列表头指针数组 int mu, nu, tu; / 行数、列数和非零元个数 CrossList;第 38 页广义表(generalized lists)的概念广义表是一种不同构的线性结构，5.4.1 广义表的定义 LS = ( 1, 2, , n )其中：i 或为原子(atom) 或为广义表。广义表的基本性质 1. 广义表的定义是一个递归定义，因为在描述广义表时又用到了广义表； 2. 在线性表中数据元素是单个元素，而在广义表中， 元素可以是单个元素称为原子(atom)，也可以是广义表，称为广义表的子表(sublist)； 3. 当每个

25、元素均为原子且类型相同时，就是线性表。第 39 页广义表的术语5.4.1 广义表的定义LS = ( 1, 2, , n )表头head表名表尾tailn是表长表头：LS的第一个元素称为表头表尾：其余元素组成的表称为LS的表尾表长：为最外层包含元素个数 深度：所含括弧的重数。原子的深度为 0，“空表”的深度为 1。第 40 页5.4.1 广义表的定义例： A = ( ) 空表 B = ( b, c, d ) C = ( a, B ) = ( a, (b,c,d) ) D = ( A, B, C ) = ( ( ), (b,c,d), (a,(b,c,d) )特点有次序有长度有深度可递归可共享一个

26、直接前驱和一个直接后继表中元素个数表中括号的重数自己可以作为自己的子表可以为其他广义表所共享第 41 页5.4.1 广义表的定义例： A = ( ) 空表 B = ( b, c, d ) C = ( a, B ) = ( a, (b,c,d) ) D = ( A, B, C ) = ( ( ), (b,c,d), (a,(b,c,d) )表长：0；深度：1表长：3，深度：1表长：2，深度：2表长：3，深度：3递归表共享表E = (a,E) = (a, (a,E) ) = ( a, (a, (a, .) ) )第 42 页5.4.1 广义表的定义 广义表的图形化表示ABDCeabcdA = (

27、a , (b, A) )D = ( A, B, C ) = ( ( ), (e), ( a, (b,c,d) ) )Aab表长：3深度：3表长：2深度：深度括号的重数 结点的层数用表示子表用表示原子第 43 页 任何一个非空广义表 LS = ( 1, 2, , n) 均可分解为 表头 Head(LS) = 1 和 表尾 Tail(LS) = ( 2, , n ) 两部分。5.4.1 广义表的定义例如：D = ( E, F ) = ( ( a, ( b, c ) )，F )Head( D ) = Tail( D ) = Head( E ) = Tail( E ) = Head( (b, c) )

28、 = Tail( (b, c) ) = Head( (b, c) ) = Tail( (b, c) ) = Head( ( c ) ) = Tail( ( c ) ) =E( F )a( (b, c) )(b, c)( )b( c )c( )第 44 页 广义表的基本操作 教材P107 1） 创建空的广义表L； 2） 销毁广义表L； 3） 已有广义表L，由L复制得到广义表T； 4） 求广义表L的长度； 5） 求广义表L的深度； 6） 判广义表L是否为空； 7） 取广义表L的表头； 8） 取广义表L的表尾； 9） 在L中插入元素作为L的第一个元素； 10）删除广义表L的第一个元素，并e用返回其值

29、； 11）遍历广义表L，用函数visit( )处理每个元素；5.4.1 广义表的定义第 45 页 广义表中的数据元素可能为原子或列表，由此需要两种结点： 表结点：用以表示广义表； 原子结点：用以表示原子。5.4.2 广义表的存储结构 链表存储： 两种链式存储形式：根据广义表分解方法的不同，其具体实现也有差异。第 46 页广义表(1, 2 n)的两种分解方法：5.4.2 广义表的存储结构 广义表：表头+表尾 广义表 L= (1, 2 n) 表头: 1 表尾: (2 , ,n) 广义表 L= (1, 2 n) 子表: 1 2 3 n 广义表：子表1 +子表2 + + 子表n 第 47 页 结点的类

30、型定义（头尾链表）Typedef enum ATOM, LIST ElemTag; / ATOM=0:原子，LIST=1: 列表Typedef struct GLNode ElemTag tag; / 标志域 union AtomType atom; / 原子结点的值域 struct struct GLNode *hp,*tp; ptr; / 表结点的指针域：ptr.hp指表头，ptr.tp指表尾 ; * Glist;5.4.2 广义表的存储结构tag ptr表结点1 hp tp data0 tag atom原子结点第 48 页 广义表头尾存储方式的实现：5.4.2 广义表的存储结构若表头为原

31、子，则为空表 ls=NULL非空表 lstag=1 指向表头的指针指向表尾的指针tag=0 data否则，依次类推。tag=1 第 49 页 头尾表构造法5.4.2 广义表的存储结构L = (a , ( b, c ) , ( ( d ) ) )1 L0 a 1 1 1 1 1 1 a( ( b, c ) , ( ( d ) ) ) ( b, c )b( c )c( ( ( d ) ) )( ( d ) ) ( d ) d0 b 0 c 0 d 第 50 页 广义表存储方式练习（头尾法）：5.4.2 广义表的存储结构A = ( ) B = (e) C = (a, (b,c,d) ) D = (A

32、, B, C)A=NULL1B0eD1111Aa(b,c,d)(b,c,d)b(c,d)c(d)d( )C11110a0b0c0d1？第 51 页 结点的类型定义（子表链表）Typedef enum ATOM, LIST ElemTag; / ATOM=0:原子，LIST=1: 列表Typedef struct GLNode ElemTag tag; / 标志域 union AtomType atom; / 原子结点的值域 struct GLNode *hp; /表节点的表头指针 ; struct GLNode *tp; /指向下一个元素结点 * Glist;5.4.2 广义表的存储结构tag

33、 表结点1 hp tp data0 tag atom原子结点tp第 52 页 b c 子表构造法5.4.2 广义表的存储结构L = (a , ( b, c ) , ( ( d ) ) ) a ( b, c ) ( ( d ) ) 1 L1 ( d ) 1 1 d 0 a 0 b 0 c 0 d 第 53 页 广义表是递归结构，所以广义表的许多操作可以用递归算法实现。5.4.3 广义表操作的实现 递归函数 一个含直接或间接调用本函数语句的函数被称之为递归函数，它必须满足以下两个条件： 1. 在每一次调用自己时，必须是（在某种意义上）更接近于解; 2. 必须有一个终止条件。第 54 页5.4.3

34、广义表操作的实现 递归算法的基本思路分治法 对于一个输入规模为 n 的函数或问题，用某种方法把输入分解成 k(1tag=ATOM ) return 0; / 原子深度0 for ( max=0, pp=L; pp; pp=pp-ptr.tp ) dep = GListDepth( pp-ptr.hp ); if ( depmax ) max = dep; return max+1;第 59 页5.4.3 广义表操作的实现 复制广义表 CopyGList(T,L)1 L1 1 1 1 1 0 d 1 0 c 0 b 0 a L = ( a , ( b ,c ) , ( ( d ) ) )表头表尾

35、第 60 页5.4.3 广义表操作的实现void GListCopy( GList &T, GList L ) /*由广义表L复制得到广义表T */ if ( !L ) T=NULL; / 复制空表 else T=(GList) malloc( sizeof(GLNode) ); / 建表结点 if ( !T ) exit(OVERFLOW); T-tag = L-tag; if ( L-tag=ATOM ) T-data = L-data; / 原子 else GListCopy( T-ptr.hp, L-ptr.hp ); / 复制hp GListCopy( T-ptr.tp, L-ptr

36、.tp ); / 复制tp 第 61 页5.4.3 广义表操作的实现 建立广义表输入：字符串 (1, 2, , n )结果: 建立广义表的链表分解：将广义表分解成 n个子表1,2,n，分别建立 1, 2, , n 对应的子表。直接求解： 空表: NULL 原子: 建立原子结点 组合：将 n 个子表组合成一个广义表第 62 页5.4.3 广义表操作的实现 建立广义表子表和广义表的关系相邻两个子表之间的关系( ( d ) )( b ,c )a子表1 L1 1 1 1 1 0 d 1 0 c 0 b 0 a 第 63 页5.4.3 广义表操作的实现void CreateGList( GList &L

37、, char str ) if ( strcmp( str,()“ )=0) L=NULL; /空表 else /非空表 L=(GList)malloc(sizeof(GLNode); L-tag=LIST； p=L; /p始终指向新建节点 SubString(sub,str,2,strlen(str)-2); /脱外层括号 do 由sub中所含n个子串重复建立n个子表; while(!StrEmpty(sub); p-ptr.tp=NULL; /表尾为空，结束 / else / CreateGList第 64 页5.4.3 广义表操作的实现do /由sub中所含n个子串建立n个子表 seve

38、r( sub, hsub ); /分离出子表串hsub=i if(StrLength(hsub)=1) /建原子结点 p-ptr.hp= (GList)malloc(sizeof(GLNode); p-ptr.hp-tag=ATOM; p-prt.hp-atom=hsub; else /递归建子表 CreateGList( p-ptr.hp, hsub ); if ( !strempty(sub) ) /建下一个子表的表结点 p-ptr.tp = (GList)malloc(sizeof(GLNode); p-ptr.tp-tag = LIST; p = p-ptr.tp; while(!st

39、rempty(sub);第 65 页5.4.3 广义表操作的实现 删除广义表中所有元素为 x 的原子结点分析： 比较广义表和线性表的结构特点。相似处：都是链表结构。不同处： 1)广义表的数据元素可能还是个广义表； 2)删除时，不仅要删除原子结点，还需要删除相应的表结点。第 66 页5.4.3 广义表操作的实现void Delete_GL( Glist&L, AtomType x ) /删除广义表L中所有值为x的原子结点 if ( L ) head = L-ptr.hp; / 考察第一个子表 if ( ( head-tag = Atom ) & ( head-atom = x ) ) / 删除原子项 x的情况 else / 第一项没有被删除的情况 / Delete_GL第 67 页5.4.3 广义表操作的实现void Delete_GL( Glist&L, AtomType x )p=L; L = L-ptr.tp;