数据结构Ch5数组和广义表.ppt
《数据结构Ch5数组和广义表.ppt》由会员分享,可在线阅读,更多相关《数据结构Ch5数组和广义表.ppt(40页珍藏版)》请在三一文库上搜索。
1、数 据 结 构 Ch.5数组和广义表,计 算 机 学 院 肖明军 Email: http:/ 多维数组,多维数组 是最易处理的非线性结构。因为各元素类型一致,各维上下界固定,所以它最容易线性化,故可看做是线性表的拓广。例如:二维数组可以看做是由列向量组成的线性表。,3,5.1 多维数组,结构特性 例:二维数组 ,它属于两个向量;i th行和j th列。 除边界外,每个aij恰有两个直接前驱和两个直 接后继。,4,5.1 多维数组,非线性特征 i th行:前驱aij-1,后继aij+1 j th列:前驱ai-1j,后继ai-1j 仅有一个开始结点:a11 仅有一个终端节点:amn 其他边界上的
2、结点只有一个直接前驱或一个直接后继,类似的m维数组 的每一个元素都属于m个向量。,5,5.1 多维数组,存储 一般均采用顺序方式存储,原因是结构中的结点不变动,内存是一维的,必须将多维数组线性化。 行优先(行主序)方式: 将(i+1)th行向量紧接在i th行向量之后: 特点:列下标变化快。Pascal、C等均是此方法。先排最右下标(多维)。,6,5.1 多维数组,列优先(列主序)方法 特点行下标变化最快,先排最左下标(可推广至多维)。Fortan是用此方法。 地址计算 一维存储地址(内部实现)。 基地址开始结点存储地址Loc(a11). 维数每维的上下界(若下界固定,则只须知道维长度) 每个
3、元素占用的单元数(元素大小):L,7,5.1 多维数组,例:行主序 。 A1m,1n 原理:aij的地址=基址+排在aij之前的元素个数每 个元素的大小 Loc(aij)=Loc(a11)+(i-1)n+(j-1) L 前i-1行结点总数 第i行上aij之前的结点数 在C语言中, 是A0m-1 , 0n-1,故有: Loc(aij)=Loc(a00)+in+j L,8,5.1 多维数组,多维推广:以C为例,行主序。 思考:Ac1d1 , c2d2 Loc(aij)=Loc(ac1c2)+(i-c1) (d2-c2+1)+(j-c2) L i th行前行数 第2维长度 i th行aij之前结点数
4、 特点:随机存取。,9,5.2 矩阵的压缩存储,用二维数组表示的特点:随机存取,存储密度为1。但对特殊和稀疏矩阵的存储则浪费空间,尤其是大规模科学与工程计算。 5.2.1 特殊矩阵 有规律:压缩后可找到地址变换公式,保持随机存取功能。,10,5.2 矩阵的压缩存储,对称阵 n阶方阵A,若 则称A为对称阵。 因为矩阵元素关于主对角线对称,故只存上三角或 下三角元素即可,节约近一半空间。 不失一般性,存储下三角(包括主对角线),以行 主序存储: 元素个数,11,5.2 矩阵的压缩存储,压缩存储: 将其存于向量sa0n(n+1)/21中。 如何访问aij?必须将其与sak的对应关系找出来。 地址计算
5、: 下三角中有j i. aij之前有i行(0 i-1) 第i行上aij之前元素个数为j(0 j-1).,12,5.2 矩阵的压缩存储,上三角中有i j ,只需交换上式的j和i即可得: 令I=max (i , j),J=min (i , j),则k和i,j之关系可统一表示为: 三角矩阵 压缩方式同上,在sa中多增加一个单元: sa0n(n+1)/2 将C存于最后一个分量中。,13,5.2 矩阵的压缩存储,对角矩阵 总结:这类矩阵压缩存储后能找到地址计算公式,使其保持随机存取的功能。,14,5.2 矩阵的压缩存储, 5.2.2 稀疏矩阵 定义:设Amn中有t个非零元素,若 ,称A为稀疏矩阵。 稀疏
6、因子: 一般非零元素分布无规律性 压缩存储: 只存储非零元,故须存储辅助信息,才能确定其位置。 三元组(i,j,aij):(行号,列号,非零元的值)唯一确定一个非零元。 当用三元组表示非零元时,有两种压缩方式:顺序和链式。,15,5.2 矩阵的压缩存储,三元组顺序表(三元组表) 以行主序(或列主序)的顺序存储非零元,跳过零元。得到一个其节点均是三元组的线性表,称此顺序存储结构为三元组表。 #define MaxSize 10000 typedef int DataType typedef struct/三元组 int i, j; DataType v; TripleNode;,16,5.2 矩
7、阵的压缩存储,typedef struct/三元组表 TripleNode dataMaxSize; int m, n, t; /行数,列数,非零元总数 TripleTable; 设a,b是TripleTable型变量。 转置运算,17,5.2 矩阵的压缩存储,18,5.2 矩阵的压缩存储,方法一:按B的次序或按A的列序转置。 A的列是B的行,故按A的列序转置,所得B是按行主序存放的。 基本思想:对A中每列,从头至尾扫描a.data,找出所有列号为col的三元组(0coln-1),将它们的行、列号互换后依次放入b.data,即可得行主序表示的B的三元组。 正确性:按A的列号递增序转置,保证B按
8、行号增序排列,B中同一行号的三元组,扫描A时所得三元组 必有ij,转置后保证按B的列号增序排列。 例,上图。,19,5.2 矩阵的压缩存储,void TransMatrix(TripleTable ,20,5.2 矩阵的压缩存储,方法二:按A的行序转置。 若简单的变换a.data的行和列,则b.data为列主序存储,要重排。但若预先确定A中每一列(即B中每一行)的第一个非零元在b.data中应有的位置,则可正确转置。 位置向量:,21,5.2 矩阵的压缩存储,思想 先求出A中每一列的非零元个数,可将第col列的非零元个数记入potcol+1中。 step1:初始化将所有pot中元素清0. /O
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 Ch5 数组 广义
链接地址:https://www.31doc.com/p-3185577.html