《数组与广义表》PPT课件.ppt

1、第五章 数组与广义表,数组的定义 数组的存储 矩阵的压缩存储 广义表的概念 广义表的存储,多维数组的定义,二维数组(矩阵)Amn是m个定长行向量构成的向量 Amn = (1, 2, 3, ., m,Amn,a11 a12 a13 . a1n,a21 a22 a23 . a2n,am1 am2 am3 . amn,. . .,i = (ai1, ai2, ai3, , ain) i = 1, 2, , m,其中所有aij均具有相同的类型,二维数组（续,二维数组也可以看成是由n个列向量构成的。 遍历二维数组的方法有两种：行优先顺序和列优先顺序. 行优先顺序: 将数组元素按行向量排列: a11 a1

2、2 a1n, a21 a22 a2n, , am1 am2 . amn. 同理,列优先顺序是将元素按照列向量排列: a11 a21 an1, a12 a22 an2, , a1m a2m . anm,多维数组,三维数组Almn 是l个mn二维向量的向量. 三维向量的遍历可按照“第I个下标优先”, 如, 先排第一个下标, 再排第二个下标, 最后排第三个下标的方式进行. 推而广之, m位数组An1 n2 nm 的元素ai1 i2 im 属于m个向量,数组上操作,初始化一个数组 销毁一个数组 给定一组下标, 取得具有该下标的元素 给定一组下标和一个值e, 将该下标的元素替换为e 遍历数组的元素,数组

3、的存储,数组的操作没有插入和删除，只有“随机存取”， 故使用顺序结构。 使用顺序结构需要将数组线性化，并且能够由元素的下标直接定位到它的存储地址。 线性化的方法可选择“行优先”（多数语言）或者“列优先”（如Fortran,二维数组的存储,数组Amn =（aij）使用“行优先”的存储， 假定下标为 0im-1 0jn-1 假定每个单元分配的大小为L (=sizeof 元素类型,Loc(aij) = Loc(a00) + (n*i+j)*L,a00 a01 . a0n-1,a10 a11 . a1n-1,am-10 am-11 . am-1n-1,aij. .,线性化后相对于a00的位序：n*i

4、+ j +1,aij 的存储地址， 可随机存取,数组的首地址,不需要行数m， 故二维数组作为参数时， 行数可以不指定,三维数组的存储,a111 a112 a113 a11n a121 a122 a123 a12n a1m1 a1m2 a1m3 a1mn a211 a212 a213 a21n a221 a222 a223 a22n a2m1 a2m2 a2m3 a2mn ahij ak11 ak12 ak13 ak1n ak21 ak22 ak23 ak2n akm1 akm2 akm3 akmn,h,i,j)元素相对于(1,1,1)的位序： (h-1)*m*n + (i-1)*n + j,h

5、,i,j)元素的存储地址： Loc(h,i,j) = Loc(1,1,1) + (h-1)*m*n + (i-1)*n + (j-1)L,数组的顺序存储表示,typedef struct ElemType *base; /数组元素基址 int dim; / 数组维数 int *bounds; /数组维界基址，存储各维长度 int *constants; /数组映像函数常量基址 Array,矩阵的压缩存储,特殊矩阵(Regular Matrix)的存储,稀疏矩阵(Sparse Matrix)的存储,具有一定规律的矩阵，如对称矩阵，三角矩阵等,很多元素是0（或者同一个值）, 只有少量元素具有特定值

6、,压缩存储(compressed storage)：使用少于二维数组的空间存储矩阵,对称矩阵的存储,n阶对称矩阵：aij = aji 0i,j n-1 不需存储所有n2 个元素，只需存储n(n+1)/2个元素 方法是将下三角元素线性化后用一维数组存储,a00 a01 . a0n-1,a10 a11 . a1n-1,an-1,0 an-1,1 . an-1,n-1,aij . . .,aij (ij) (=aji)的存储单元 j(j+1)/2+i,aij (ij) 的位序 1+2+i+j+1 = i(i+1)/2+j+1,aij (ij) 的存储单元 i(i+1)/2+j(丛0单元算起,三角矩阵

7、的存储,下)三角矩阵：所有的上三角元素aij (ij)均等于一个常数, 如0. 上述方法同样适用于三角矩阵的存储: 用一维数组存储下三角元素aij (ij), 其中一个单元存储上三角元素，如0单元存放上三角元素， i(i+1)/2+j+1存放aij (i j,稀疏矩阵,6行, 7列, 非零元素8个,稀疏因子,稀疏因子 0.2,稀疏矩阵: 非零元素数m*n,应用: 数值计算, 图算法等,稀疏矩阵ADT,稀疏矩阵作为一类重要的数据结构可以定义为一个ADT,ADT SparseMatrix 数据对象：D=aij | aij ElemType i=1,2,m; j=1,2,n 数据关系：R = Row

8、, Col Row = (ai,j , ai,j+1) 1im, 1jn-1 Col = (ai,j , ai+1,j) 1im-1, 1jn 基本操作： ADT SparseMatrix,基本操作包括：创建、输出、转置和加、减、乘等运算,稀疏矩阵的存储,稀疏矩阵可以用所有的非零元素和它们的下标来唯一表示； 每个非零元素可用一个三元组 （行下标， 列下标， 值）表示； 任务：如何存储这些三元组， 并实现稀疏矩阵上的运算； 顺序结构三元组顺序表：按照行优先或者列优先的方法把非零元素视为一个线性表； 链式存储十字链：给每个非零元素附上它所在行和列的下一个非零元素的地址,稀疏矩阵的顺序存储,使用顺序

9、结构存储行优先的三元组表称为三元组顺序表 其结构定义如下,typedef struct int row, col; /非零元素的行、列下标 ElemType value; Triplet; typedef struct Triplet dataMAXSIZE+1; /存放非零元素三元组 int rows, cols, vals; /矩阵的行数、列数和非零元素数 TSMatrix,矩阵的转置,A67 的转置,矩阵的转置,A67 的存储结构(行优先序列,B76 的存储结构(A67 的列优先序列,转置的实现： 扫描数组M， 顺序找出列号为0的元素，转置，将其存放到数组T中； 对下一列号重复进行， 直

10、至最大列号,M,T,转置的实现,Status TransposeSMatrix(TSMatrix M, TSMatrix /TranspsoeSMatrix,时间复杂度,上述算法的时间复杂度为O(cols vals) 通常的转置算法时间复杂度为O(cols rows,for (j=0; jcols; +j) for(k = 0; k= rows; +k) Tik = Mkj,如果vals cols rows, 则时间复杂度为O(cols2 rows ). 可见， 只有非零元素个数vals cols rows时， 上述算法才是有效的,快速转置,扫描一次， 转置每个三元组,直接定位,快速转置,顺序

11、转置三元组表中的每个元素，将其存储到转置矩阵的三元组表中的最终位置； 用rowSizej表示矩阵M中第j列非零元素个数，则第j列的第一个非零元素存放位置为 rowStartj = rowSize0 + + rowSizej-1 用rowStartj表示M的当前读到的第j列元素在转置三元表中的位置 rowSizej可以通过扫描M一次求得 算法的时间复杂度为O(vals + cols)， 代价是空间 算法实现见课本,三元组表示的特点,节省了空间； 当非零元素个数远远小于矩阵规模时，操作效率较高； 当非零元素个数与矩阵规模为同一数量阶时，操作效率大大降低； 稀疏矩阵的其他运算会使得结果的非零元素增加

12、或者减少， 相应的三元组表需要增加或者删除元素，在线性结构中需要移动元素， 增加了时间的支出,稀疏矩阵的十字链表,0 3 0 0 5 6 2 0 0,每个结点存储非零元的行列号，值，以及指向下一行和下一列非零元结点的指针,十字链表的表示,typedef struct OLNode int row,col; /非零元的行列号 ElemType elem; struct OLNode *right, *down; /行列的后继链域 OLNode; *OLink; typedef struct OLink *rhead, *chead; /行头结点和列头结点向量 int rows, cols, va

13、ls; /稀疏矩阵的行数，列数和非零元素数 CrossList,广义表,一个广义表是零个或者多个原子或者子表构成的有限序列。 一个不空的广义表记作 L = (d1,d2, , dn)， 其中di可以是单元素（原子），也可以是广义表， 称为广义表的子表。n 称为广义表的长度。d1称为表头，(d2, ,dn)成为表尾。 广义表简称表或者列表。 在线性表中，所有元素具有相同的类型。而在广义表中，每个元素可以是单个元素，也可以是一个广义表,广义表的例子,A = ( ) 是一个空表； B = (6, 2) 是长度为2的广义表。 C = (a, (5, 3, x) 是长度为2的表。 D = (B, C,

14、A)是长度为3 的表。 E = （B, D) 是长度为2 的表。 F = (4, F)是一个递归表。 一个广义表的元素间不仅有次序关系， 而且存在层次关系，即表的钳套深度。 如B的深度为1， D的深度为3. F的深度为无穷大,广义）表的图示,表结点用圈表示， 原子结点用方框表示,构成一棵树,广义表的运算,创建空的广义表: initGList,广义表作为ADT,ADT Glist 数据对象: D=ei |i=1,2, n; n0, ei AtomSet 或ei Glist 数据关系: R=(ei-1 , ei ) | ei D 基本操作: initGList,广义表的存储,顺序结构不适用, 因为

15、表中元素类型不同; 采用类似于线性表的链式结构,L1 =(5,12,s,47,a,L2 = (5, (3,2,(14,9,3), (), 4),2, (6,3,10,广义表的存储结构,tag atom/hp tp,tag=0: 原子结点 tag=1: 表结点,结点格式,原子结点：原子信息 表结点： 指向表头结点的指针,指向同层下一个结点的指针,0 a,1,0 5,0 3,0 x,head,广义表的链表表示,typedef enum ATOM, LIST ElemTag; typedef struct GLNode ElemTag tag;/标志原子或表结点 union AtomType ato

16、m; /原子结点的值 struct GLNode *hp; / 表结点的表头指针 ； struct GLNode *tp; /指向下一个元素结点 *GList; /广义表类型是扩展的线性表,求广义表的深度,例如，对于广义表 E ( B (a, b), D ( B (a, b), C (u, (x, y, z), A ( ) ) ) 按递归算法分析： Depth (E) = 1+Max Depth (B), Depth (D) Depth (B) = 1+Max Depth (a), Depth (b) = 1 Depth (D) = 1+Max Depth (B), Depth (C), De

17、pth (A,LS = (a1, a2, , an,Depth (C) = 1+Max Depth (u), Depth (x, y, z) Depth (A) = 1 Depth (u) = 0 Depth (x, y, z) = 1+Max Depth (x), Depth (y), Depth (z) = 1 Depth (C) = 1+Max Depth (u), Depth (x, y, z) = 1+Max 0, 1 = 2 Depth (D) = 1+Max Depth (B), Depth (C), Depth (A) = 1+Max 1, 2, 1 = 3 Depth (E) = 1+Max Depth (B), Depth (D) = 1+Max 1, 3 = 4,E ( B (a, b), D ( B (a, b), C (u, (x, y, z), A ( ) ),Int depth ( GList *ls ) /广义表ls 用扩展的线性链表存储，函数返回ls的深度 if ( ls = NULL ) return 1; /空表 GList *temp = ls; int m = 0; /m 表示当前层元素的最大深度