《数据结构》课件第5章 数组和广义表

1、第5章 数组和广义表学习要点: 了解数组的两种存储表示方法，掌握行序为主的存储结构中的地址计算方法掌握对特殊矩阵进行压缩存储时的下标变换公式了解稀疏矩阵的两种压缩存储方法的特点和适用范围，领会三元组表示的矩阵运算方法掌握广义表的结构特点及其存储表示方法5.1 数组的定义数组-线性表的扩展，其表中的数据元素本身也是一个数据结构。抽象数据类型定义：ADT Array 数据对象： Daj1,j2, .,ji,jn| aj1,j2, .,ji,jnElemSet, ji =0,.,bi -1, i=1,2,.,n 数据关系： RR1, R2, ., Rn Ri | 0 jkbk -1, 1kn 且k

2、i, 0 ji bi -2, aj1,. ji,. jn , aj1, .ji+1, .jnD, i=2,.,n ADT Array 基本操作:数组元素的第i维下标数组的维数第i维的长度n维数组中有 个数据元素：每个元素都受着n个关系的约束。每个关系中，元素aj1j2jn(0jibi-2)都有一个直接后继元素。每个元素对应一组下标(j1,j2,jn)，每个下标的取值范围是0jibi-1，bi为第i维的长度。InitArray(&A, n, bound1, ., boundn) 操作结果：若维数 n 和各维长度合法，则构造相应的数组A，并返回OK。DestroyArray(&A) 操作结果：销毁

3、数组A。ni=1Value(A, &e, index1, ., indexn) 初始条件：A是n维数组，e为元素变量，随后是n 个下标值。 操作结果：若各下标不超界，则e赋值为所指定的A 的元素值，并返回OK。Assign(&A, e, index1, ., indexn) 初始条件：A是n维数组，e为元素变量，随后是n 个下标值。 操作结果：若下标不超界，则将e的值赋给所指定的A的元素，并返回OK。二维数组的ADT定义： 数据对象: D = aij | 0ib1-1, 0 jb2-1, aijElemSet 数据关系: R = ROW, COL ROW = | 0ib1-2, 0jb2-1

4、COL = | 0ib1-1, 0 jb2-2数组的向量形式定义：二维数组Amn，以m行n列的矩阵形式表示： A=(0, 1, , p) (p=m-1或n-1)其中，每一个j是一个列向量形式的线性表： j=(a0j, a1j, , am-1,j) 0jn-1行向量形式的线性表： i=(ai0, ai1, , ai,n-1) 0im-1Amn=(a00a01a0,n-1), (a10a11a1,n-1), , (am-1,0am-1,1am-1,n-1)二维数组类型定义： typedef ElemType Array2mn; typedef ElemType Array1n; typedef A

5、rray1 Array2m;5.2 数组的顺序表示和实现数组类型的特点:只有引用型操作，没有加工型操作(插入和删除)；数组是多维的结构，而存储空间是一个一维的结构。有两种顺序映象的方式：以行序为主序(低下标优先)例如：以列序为主序(高下标优先)称为基地址或基址二维数组A中任一元素ai,j 的存储位置 LOC(i,j) = LOC(0,0) + (b2ij)a0,1a0,0a0,2a1,0a1,1a1,2a0,1a0,0a0,2a1,0a1,1a1,2L L (5-1)a0,0a1,0a0,1a1,1a0,2a1,2每一行元素的个数注意：如果基址的下标为(1,1)，公式的变化！n维数组行序为主序

6、存储位置的映象关系：称式(5-2)为 n 维数组的映象函数。数组元素的存储位置是其下标的线性函数。数组的顺序存储表示：#include /标准头文件，提供宏va_start、 /va_arg和va_end用于存取变长参数表#define MAX_ARRAY_DIM 8typedef struct ElemType *base; /数组元素基址，由InitArray分配 int dim; /数组维数 int *bounds; /数组维界基址，由InitArray分配 int *constants; /数组映像函数常量基址，由InitArray分配Array;其中 cn = L，ci-1 = bi

7、 ci , 1 i n。LOC(j1, j2, ., jn ) = LOC(0,0,.,0) + ci ji i=1n(5-2)例如：设按行序为主序存储整数数组A9358时，第一个元素的字节地址是100，每个整数占四个字节。则LOC(a1111)=？ LOC(a3125)=？解：由题可知，b1=9，b2=3，b3=5，b4=8。又L=4(字节)，则 c4=4，c3=b4c4=84=32， c2=b3c3=532=160，c1=b2c2=3160=480 LOC(a1111)= 100+(480*1+160*1+32*1+4*1)=776 LOC(a3125)= 100+(480*3+160*1

8、+32*2+4*5)=1784第i维的下标值每个数据元素占用的存储空间大小Status InitArray(Array A, int dim, ) /若维数dim和各维长度合法，则构造相应的数组A，并返回OK。 if (dimMAX_ARRAY_DIM) return ERROR; A.dim=dim; A.bounds=(int *)malloc(dim * sizeof(int); if (!A.bounds) exit(OVERFLOW); /若各维长度合法，则存入A.bounds，并求出A的元素总数elemtotal elemtotal=1; va_start(ap, dim); /初

9、始化变量ap(可变参数)，运行后ap指向第一个 /可变参数的堆栈地址 for (i=0; idim; +i) A.boundsi=va_arg(ap, int); /返回可变参数，类型为int if (A.boundsi0; -i) A.constantsi=A.boundsi+1 * A.constantsi+1; return OK;其它操作实现见教材P94P95。5.3 矩阵的压缩存储5.3.1 特殊矩阵定义：值相同的元素或者零元素在矩阵中的分布有一定规律的矩阵。若n阶矩阵A中的元素满足下述性质：aij=aji 1i, jn 则称为n阶对称矩阵。存储方式：以行序为主序存储矩阵的下三角(包

10、括对角线)中的元。存储空间：n(n+1)/2一维数组san(n+1)/2中元素sak和矩阵元aij的对应关系：例如：当ij当ijA44=sa10:12536847910(5-3)思考：如何推导式(5-3)的关系？第i行之前已经有i-1行元素被存储，且每一行只有i个元素。因此，前i-1行共有：1+2+(i-1)个元素。则aij的一维位置为，再加上第i行前j-1个元素： i(i-1)/2+j-1？三角矩阵：下(上)三角矩阵：矩阵的上(下)三角(不包括对角线)中的元均为常数c或零的矩阵。增加一个存储常数c的存储空间。例如：下三角矩阵对角矩阵：所有的非零元素都集中在以主对角线为中心的带状区域中。Ann

11、=思考：上三角矩阵中元素与一维数组元素的对应关系式？1jin课后作业P32：5.55.3.2 稀疏矩阵何谓稀疏矩阵？假设 m 行 n 列的矩阵含 t 个非零元素，则称为稀疏因子。通常认为 0.05 的矩阵为稀疏矩阵。产生的问题:零值元素占了很大空间;计算中进行了很多和零值的运算；遇除法，还需判别除数是否为零。解决问题的原则：尽可能少存或不存零值元素；尽可能减少没有实际意义的运算；操作方便。 即：能尽可能快地找到与下标值(i, j)对应的元素能尽可能快地找到同一行或同一列的非零值元压缩存储方法：只存储非零元！三元组顺序表：一个三元组(i, j, aij)唯一确定矩阵A的一个非零元。例如：(1,

12、2, 12), (1, 3, 9), (3, 1, -3), (3, 6, 14), (4, 3, 24), (5, 2, 18), (6, 1, 15), (6, 4, -7)存储表示：#define MAXSIZE 12500 typedef struct int i, j; /非零元的行下标和列下标 ElemType e; / 非零元的值 Triple; / 三元组类型typedef struct Triple dataMAXSIZE + 1; /行序为主序排列 int mu, nu, tu; /矩阵的行数、列数和非零元个数 TSMatrix; / 稀疏矩阵类型如何求转置矩阵？用常规的二

13、维数组表示时的算法：for (col=1; col=nu; +col) for (row=1; row=mu; +row) Tcolrow = Mrowcol; 其时间复杂度为: O(munu)M35T53用“三元组”表示时如何实现？按照T.data中三元组的次序，依次在M.data中找到相应的三元组进行转置，即按照矩阵M的列序来进行转置。1 2 141 5 -52 2 -73 1 363 4 282 1 145 1 -52 2 -71 3 364 3 28M35T53121415-522-7313634281336211422-7432851-5M35T53ijaijijaijStatus

14、TransposeSMatrix(TSMatrix M, TSMatrix &T) /采用三元组表存储表示，求稀疏矩阵M的转置T。 T.mu=M.nu; T.nu=M.mu; T.tu=M.tu; if (T.tu) q=1; /矩阵T的三元组顺序表的下标 for (col=1; col=M.nu; +col) /按照M的列序进行转置 for (p=1; p=M.tu; +p) /依次扫描M的三元组顺序 /表中的元素的列值 if (M.datap.j = col) T.dataq.i=M.datap.j; T.dataq.j=M.datap.i; T.dataq.e=M.datap.e; +q

15、; return OK;/TransposeSMatrix算法时间复杂度：O(nutu)适用于tumunu的情况！按照M.data中三元组的次序(M的行)进行转置，并将转置后的三元组置入T中恰当的位置。如何确定T中的位置？先求得M的每一列中非零元的个数；求得每一列的第一个非零元在T.data中应有的位置。2cola.nu(5-4)Status FastTransposeSMatrix(TSMatrix M, TSMatrix &T) T.mu = M.nu; T.nu = M.mu; T.tu = M.tu; if (T.tu) for (col=1; col=M.nu; +col) numc

16、ol = 0; for (t=1; t=M.tu; +t) +numM.datat.j; /M中每一列非零元的个数 cpot1 = 1; for (col=2; col=M.nu; +col) /第col列中第一个非零元在 /T.data中的序号 cpotcol = cpotcol-1 + numcol-1; for (p=1; p=M.tu; +p) / if return OK; / FastTransposeSMatrix 转置矩阵元素col = M.datap.j;q = cpotcol;T.dataq.i = M.datap.j;T.dataq.j = M.datap.i;T.dat

17、aq.e = M.datap.e;+cpotcol时间复杂度为: O(nu+tu)tu和munu等数量级时，时间复杂度为: O(munu)三元组顺序表(又称有序的双下标法)的特点：非零元在表中按行序有序存储，便于依行顺序处理的矩阵运算。行逻辑链接的顺序表：将指示“行”信息的数组cpot固定在稀疏矩阵的存储结构中，称这种“带行链接信息”的三元组表为行逻辑链接的顺序表。#define MAXMN 500 typedef struct Triple dataMAXSIZE + 1; int rposMAXMN + 1; /存储各行第一个非零元的位置 int mu, nu, tu; RLSMatrix

18、; / 行逻辑链接顺序表类型两个矩阵相乘：Q=Mm1n1Nm2n2 (n1=m2)经典算法：for (i=1; i=m1; +i) for (j=1; j=n2; +j) Qij = 0; for (k=1; k=n1; +k) Qij += Mik * Nkj; 当M和N是稀疏矩阵并用三元组表存储时，上述算法就不适用了！其时间复杂度为: O(m1n2n1)例如：则Q=MN为：它们的三元组M.data、N.data和Q.data分别为：ije11314522-1312ije12221131-2324ije12621-1324M.dataN.dataQ.data(5-5)分析：Q中元素：因此，对

19、M.data中的每个元素(i, k, M(i, k)(1im1, 1kn1)，找到N.data中所有相应的元素(k, j, N(k, j)(1km2, 1jn2)。利用行逻辑链接的顺序表中N.rpos数据项，可以获取N中所有相应的元素。1im11jn2(5-6)row1234rposrow1235M和N相乘的操作：对Q的每一个元素设一个累计和变量ctemp；扫描数组M中每个元素M.datap(p=1, 2, ., M.tu)，找到N中所有满足：M.datap.j=N.dataq.i 的元素N.dataq；求得M.datap和N.dataq乘积并累加到ctemp。ije11314522-1312

20、ije12221131-2324M.dataN.dataije12621-1324Q.data矩阵Q的存储：将求得的Q中的元素按照行序依次存到一个一维数组中；然后扫描该数组，对Q进行压缩存储。算法描述： Q初始化； if Q是非零矩阵 / 逐行求积 for (arow=1; arow=M.mu; +arow) / 处理M的每一行 ctemp = 0; / 累加器清零 计算Q中第arow行的积并存入ctemp 中； 将ctemp 中非零元压缩存储到Q.data； / for arow / if 稀疏矩阵相乘的算法精确描述：Status MultSMatrix (RLSMatrix M, RLSM

21、atrix N, RLSMatrix &Q) if (M.nu != N.mu) return ERROR; Q.mu = M.mu; Q.nu = N.nu; Q.tu = 0; if (M.tu*N.tu != 0) / Q是非零矩阵 for (arow=1; arow=M.mu; +arow) / 处理M的每一行，并压缩存储Q的非零元 / for arow / if return OK; / MultSMatrix ctemp = 0; / 当前行各元素累加器清零 Q.rposarow = Q.tu+1; for (p=M.rposarow; pM.rposarow+1;+p) /对当前

22、行中每一个非零元找到对应元在N中的行号 brow=M.datap.j; if (brow N.mu ) t = N.rposbrow+1; /t控制N中当前行非零元的提取 else t = N.tu+1 for (q=N.rposbrow; q t; +q) ccol = N.dataq.j; / 乘积元素在Q中列号 ctempccol += M.datap.e * N.dataq.e; / for q / 求得Q中第crow( =arow)行的非零元 for (ccol=1; ccol MAXSIZE) return ERROR; Q.dataQ.tu = arow, ccol, ctemp

23、ccol; / if处理 的每一行M(M.muN.nu)(M.tuN.tu/N.mu)(M.muN.nu)总的时间复杂度：(M.muN.nu+M.tuN.tu/N.mu)若M是m行n列的稀疏矩阵，N是n行p列的稀疏矩阵，则M中非零元的个数 M.tu = Mmn，N中非零元的个数 N.tu = Nnp，相乘算法的时间复杂度就是 O(mp(1+nMN) ，当M0.05 和N0.05及 n 1000时，相乘算法的时间复杂度就相当于O(mp)理想的结果！十字链表：当矩阵的非零元个数和位置在操作中变化较大时，不宜采用顺序存储结构来表示三元组的线性表。采用链表表示：typedef struct OLNod

24、e int i, j; ElemType e; struct OLNode *right, *down; /该非零元所在行表和 /列表的后继链域OLNode; *OLink;typedef struct OLink *rhead, *chead; /行和列链表头指针向量基址，由 /CreateSMatrix分配 int mu, nu, tu;CrossList;矩阵M的十字链表如图：11314522-13215.4 广义表的定义又称为列表(lists)，被广泛用于人工智能等领域的表处理语言LISP语言中。抽象数据类型定义：ADT Glist 数据对象：Dei | i=1,2,.,n; n0;

25、eiAtomSet 或 eiGList, AtomSet为某个数据对象 数据关系： LR| ei-1 ,eiD, 2in ADT Glist基本操作:基本操作：结构的创建和销毁： InitGList(&L); DestroyGList(&L); CreateGList(&L, S); CopyGList(&T, L);状态函数： GListLength(L); GListDepth(L); GListEmpty(L); GetHead(L); GetTail(L);插入和删除： InsertFirst_GL(&L, e); DeleteFirst_GL(&L, &e);遍历： Traverse

26、_GL(L, Visit();广义表是递归定义的线性结构： LS = (1, 2, ., n )i可以是单个元素(原子)，也可以是广义表(子表)。约定：用大写字母表示广义表的名称，用小写字母表示原子。例如: A = ( )长度为0；深度为1 F = (d, (e)长度为2；深度为2 D = (a,(b,c), F)长度为2；深度为3 C = (A, D, F)长度为3；深度为4 B = (a, B) = (a, (a, (a, . , ) ) )长度为2广义表的名称广义表的长度表头表尾注意：“表尾”是一个表！广义表的深度：指广义表包含的括号重数。广义表是一个多层次的线性结构：广义表的结构特点：

27、广义表中的数据元素有相对次序；广义表的长度定义为最外层包含的元素个数；广义表的深度定义为所含括弧的重数；广义表可以共享；广义表可以是一个递归的表。例如：D=(E, F)其中: E=(a, (b, c) F=(d, (e)DEFa( )d( )bce注意:1. “原子”的深度为 0 2. “空表”的深度为 1 3. 递归表的深度是无穷值，长度是有限值。任何一个非空广义表LS = (1, 2, , n)均可分解为：表头：Head(LS) = 1和表尾：Tail(LS) = (2, , n) 两部分。例如: D = ( E, F ) = (a, (b, c)，F )，则Head( D ) = E Tail( D ) = ( F )Head( E ) = a Tail( E ) = ( ( b, c) )Head( ( b, c) ) = ( b, c) Tail( ( b, c) ) = ( )Head( ( b, c)