《第5章数组和稀疏矩阵1.ppt》由会员分享，可在线阅读，更多相关《第5章数组和稀疏矩阵1.ppt（27页珍藏版）》请在三一文库上搜索。
1、本章的基本内容是： 数组的基本概念 数组的逻辑结构 特殊矩阵的压缩存储 广义表,第五章 数组和广义表,限制插入、删除位置,限制元素类型为字符,串零个或多个字符组成的有限序列 。,广义线性表多维数组,5.1.1数组的基本概念,数组的定义 数组是由一组类型相同的数据元素构成的有序集合，每个数据元素称为一个数组元素（简称为元素），每个元素受n(n1)个线性关系的约束，每个元素在n个线性关系中的序号i1、i2、in称为该元素的下标，并称该数组为 n 维数组。,数组具有以下性质： (1) 数组中的数据元素数目固定。一旦定义了一个数组,维数与维界及其数据元素数目不再有增减变化。 (2) 数组中的数据元素具
2、有相同的数据类型。 (3) 数组中的每个数据元素都和一组惟一的下标值对应。 (4) 数组是一种随机存储结构。可随机存取数组中的任意数据元素。,5.1.1数组的基本概念,a11 a12 a1n a21 a22 a2n am1 am2 amn,A=,数组线性表的推广,二维数组是数据元素为线性表的线性表。,数组的基本概念,数组的基本操作,在数组中插入（或）一个元素有意义吗？,将元素 x 插入 到数组中第1行第2列。,删除数组中 第1行第2列元素。,数组的基本概念,数组的基本操作, 存取：给定一组下标，读出对应的数组元素； 修改：给定一组下标，存储或修改与其相对应的数组元素。 存取和修改操作本质上只对
3、应一种操作寻址,数组应该采用何种方式存储？,数组没有插入和删除操作，所以，不用预留空间，适合采用顺序存储。,数组的基本概念,数组的存储结构一维数组,已知：a0 地址为2000H,数组每个元素所占字节数 L为2 计算： a5 的地址,LOC(a5)=LOC(a0)+L*(5-0) =2000+2*5 =2010 总结： 若是一维数组 已知起始地址为LOC(a1)，每个元素所占K个存储单元，则 LOC(ai)= LOC(a1) +K*(i-1),设一维数组的下标的范围为闭区间l，h，每个数组元素占用 c 个存储单元，则其任一元素 ai 的存储地址可由下式确定： Loc(ai)Loc(al)(il)
4、c,数组的存储结构一维数组,常用的映射方法有两种： 按行优先：先行后列，先存储行号较小的元素，行号相同者先存储列号较小的元素。 按列优先：先列后行，先存储列号较小的元素，列号相同者先存储行号较小的元素。,数组的存储结构二维数组,l2,h2,l1,h1,(a) 二维数组,aij前面的元素个数 =阴影部分的面积 =整行数每行元素个数+本行中aij前面的元素个数 =(i -l1)(h2 -l21)(j -l2),按行优先存储的寻址,数组的存储结构二维数组,数组的存储结构二维数组,已知：int a34;,已知：a0 0 地址为2000H 数组每个元素所占字节数 L为2 计算： a23 的地址,LOC(
5、a23)=LOC(a00)+(2-0)*4+(3-0)*L =2000+(8+3)*2 =2022 总结： LOC(aij)=LOC(a00)+ (i-0)*4+(j-0)*L,第l1行,第l1+1行,(i -l1)(h2 -l21)(j -l2)个元素,Loc(aij)Loc(al1l2)(il1)(h2l21)(jl2)c,按列优先存储的寻址方法与此类似。,数组的存储结构二维数组,按行优先存储的寻址,5.1.3特殊矩阵的压缩存储,特殊矩阵：包括对称矩阵、三角矩阵、对角矩阵和稀疏矩阵等。 稀疏矩阵：矩阵中有很多零元素。,3 6 4 7 8 6 2 8 4 2 4 8 1 6 9 7 4 6
6、0 5 8 2 9 5 7,A,对称矩阵特点：aij=aji,如何压缩存储？,只存储下三角部分的元素。,特殊矩阵的压缩存储对称阵,3 c c c c 6 2 c c c 4 8 1 c c 7 4 6 0 c 8 2 9 5 7,(a) 下三角矩阵,3 4 8 1 0 c 2 9 4 6 c c 5 7 c c c 0 8 c c c c 7,(b) 上三角矩阵,如何压缩存储？,只存储上三角（或下三角）部分的元素。,特殊矩阵的压缩存储三角阵,如何只存储非零元素？,注意：稀疏矩阵中的非零元素的分布没有规律。,特殊矩阵的压缩存储稀疏矩阵,稀疏矩阵是指矩阵中存在大量的零元，非零元数目较少且分布没有规
7、律。 一个阶数较大的矩阵中的非零元素个数s相对于矩阵元素的总个数t十分小时,即st时,称该矩阵为稀疏矩阵。例如一个100100的矩阵,若其中只有100个非零元素,就可称其为稀疏矩阵。,5.2 稀疏矩阵,这就是稀疏矩阵，为什么要研究稀疏矩阵？,三元组表：将稀疏矩阵的非零元素对应的三元组所构成的集合，按行优先的顺序排列成一个线性表。,三元组表( (0,0,15), (1,1,11), (2,3,6), (4,0,9) ),如何存储三元组表？,5.2.1稀疏矩阵的压缩存储三元组,思考如下问题： (1)是不是所有的稀疏矩阵都可以对其非零元描述成三元组线性表？ (2)是不是所有的三元组线性表都可以唯一的
8、表示一个稀疏矩阵？,还需要记录总行数和总列数,采用顺序存储结构存储三元组表,0 0 15 0 3 22 0 5 -15 1 1 11 1 2 3 2 3 6 4 0 91 空 空 空 闲 闲 闲,row col item,0 1 2 3 4 5 6,MaxTerm-1,7（非零元个数）,是否对应惟一的稀疏矩阵？,5.2.1稀疏矩阵的压缩存储三元组,三元组顺序表的数据结构（一）,三元组顺序表的数据结构,5.2.1稀疏矩阵的压缩存储三元组,三元组数据结构： typedef struct int r; int c; ElemType d; TupNode;,三元组顺序表数据结构： typedef s
9、truct int rows; int cols; int nums; TupNode dataMaxSize; TSMatrix;,(1)从一个二维矩阵创建其三元组表示 void CreatMat(TSMatrix &t,ElemType AMN) (2) 输出三元组 void DispMat(TSMatrix t) (3) 矩阵转置 void TranTat(TSMatrix t,TSMatrix &tb),5.2. 2三元组顺序表的基本运算,(1) 从一个二维矩阵创建其三元组表示 以行序方式扫描二维矩阵A,将其非零的元素插入到三元组t的后面。算法如下： void CreatMat(TSMatrix ,(2) 输出三元组 从头到尾扫描三元组t,依次输出元素值。算法如下： void DispMat(TSMatrix t) int i; printf(“t%dt%dt%dn“,t-rows,t-cols,t-nums); printf(“ -n“); for (i=0;inums;i+) printf(“t%dt%dt%dn“,t-datai.r, t-datai.c, t-datai.d); ,