数据结构多维数组及广义表.ppt
《数据结构多维数组及广义表.ppt》由会员分享,可在线阅读,更多相关《数据结构多维数组及广义表.ppt(34页珍藏版)》请在三一文库上搜索。
1、第四章 多维数组及广义表,前几章介绍的数据结构都是线性结构,数据元素都属于原子类型,其值不分解使用。 本章讨论的多维数组和广义表是线性结构的推广,从整体上看它们是多个元素组成的线性表,而从局部上看线性表中的数据元素不一定是原子类型,即数据元素又可以具有某种数据结构。,主要内容:,41 多维数组 多维数组的逻辑结构特征及存储方式 42 矩阵的压缩存储 特殊矩阵和稀疏矩阵的压缩存储 43 广义表 广义表的定义和运算,41 多维数组,一、多维数组的逻辑结构特征 数组中的元素具有相同类型,且下标一般具有固定的上界和下界。 数组可以是一维的,也可以是多维的。 本章主要以二维数组为例来分析多维数组的逻辑结
2、构特征和存储结构。,二维数组可以看成是由多个一维数组组成的。例如,二维数组Amn既可看成由m个行向量组成的线性表,也可看成是由n个列向量组成的线性表。,二维数组的逻辑结构具有如下特征: a00为开始结点,它没有直接前趋; am-1,n-1为终端结点,它没有直接后继; 结点a0,n-1和am-1,0都有一个直接前趋和一个直接后继; 除以上四个结点外,第一行和第一列的元素都有一个直接前趋和两个直接后继,最后一行和最后一列的元素都有两个直接前趋和一个直接后继; 其余的非边界元素aij同时处于第i+1行的行向量中和第j+1列的列向量中,都有两个直接前趋和两个直接后继。,二、多维数组的存储 二维数组一般
3、采用顺序存储。 由于内存单元是一维的线性关系,而二维数组中元素之间的关系是非线性的,所以若要顺序存储二维数组,首先需要将二维数组中的元素按照某种原则排列成点的线性序列,然后再依次存放到连续的存储单元中。 通常二维数组有行优先和列优先两种排列原则。 (1)行优先原则,是指先排列二维数组的第一行中的数据元素,再排列第二行中的数据元素,以此类推。 (2)列优先原则,是指先排列二维数组的第一列中的数据元素,再排列第二列中的数据元素,以此类推。,数据元素的存储地址可根据数组的首地址、元素的存储空间大小及元素的序号三个信息计算出来,从而实现随机存取。 若二维数组Amn按行优先原则排列,其线性序列为: a0
4、0,a01,a0,n-1,a10,a11,a1,n-1,am-1,n-1 存储后的内存状态如图所示: aij的地址为:LOC(aij)= LOC(a00)+(in+j) d,若二维数组Amn按列优先原则排列,则线性序列为: a00,a10,am-1,0,a01,a11,am-1,1,am-1,n-1 存储后的内存状态如图所示: aij的地址为:LOC(aij)= LOC(a00)+(jm+i) d,二维数组的逻辑特征和存储方法可以很容易地推广到多维数组。 例如三维数组可以看成是由二维数组组成的线性表,三维数组中的每个元素最多有三个直接前趋和三个直接后继。 同样,行优先原则和列优先原则也可以推广
5、到多维数组,按行优先原则时先排最右的下标,按列优先原则时先排最左的下标。 得到行优先或列优先序列后,可以把它们依次存放在连续的存储空间中,这就是多维数组的顺序存储,同样可实现随机存取。,42 矩阵的压缩存储,计算机在处理工程问题时,通常使用二维数组来存储矩阵,但是实际问题中的矩阵往往阶数较大,而有效数据(非零元素)很少且分布没有规律,若用上面讨论的二维数组存储,其存储密度小(存储了大量的零元素),浪费了存储空间。 矩阵的压缩存储通常指在存储数据元素时,只存储非零元素,对零元素不分配空间;为多个相同的非零元素分配一个存储空间。 下面分别讨论特殊矩阵和稀疏矩阵的压缩存储。,一、特殊矩阵,特殊矩阵是
6、指非零元素或零元素分布有一定规律的矩阵。例如,对称矩阵、三角矩阵(上三角阵和下三角阵)及对角矩阵,特殊矩阵可以根据元素的分布规律来进行压缩存储。 不同的特殊矩阵中元素的分布规律不同,压缩存储的方法也不同。,1对称矩阵,满足aij=aji(1i,jn)的n阶方阵称为对称矩阵。 对称矩阵中的数据元素按主对角线对称,只需存储下三角或上三角中的元素即可。上三角或下三角中的元素可按行优先或列优先存储。由此可得四种存储方法: 行优先顺序存储下三角 列优先顺序存储下三角 行优先顺序存储上三角 列优先顺序存储上三角。 每种方法中元素的存储地址都可以通过公式计算出来,且具有随机存取的特点。,(1)行优先顺序存储
7、下三角 以图(a)所示的n阶方阵为例,行优先顺序存储下三角时元素的排列顺序如图(b)所示,存储在一维数组中如图(c)所示。,(a) n阶对称矩阵 (b) 行优先顺序存储下三角,(c)对应的一维数组,设长度为n(n+1)/2的数组sa存储下三角中的元素。 设矩阵下三角中的某一个元素aij(ij)对应存储在一维数组的下标变量sak中,则上三角中的某一个元素aij(ij)存储在与aji对应的存储单元中。 下三角中任一数据元素aij (ij),位于第i+1行的第j+1列,则排在它前面的i行元素共有1+2+3+i-1+i=i(i+1)/2个,在第i+1行中排在它前面的元素还有j个,因此排在它前面的元素总
8、共有i(i+1)/2+j个元素。由于一维数组的下标从0开始,因此元素aij在一维数组中的下标为i(i+1)/2+j。综上可得下标k的计算公式为:,同理可得其他三种方法存储时,元素aij在一维数组中 的下标计算公式: (2)列优先顺序存储下三角 (3)行优先顺序存储上三角 (4)列优先顺序存储上三角,2三角矩阵,包括上三角阵和下三角阵两种。 上三角阵的主对角线以下(不包括对角线)元素均为常数C,通常为0。而下三角阵主对角线以上(不包括对角线)元素均为常数C,通常为0。 利用压缩存储的原理,只为矩阵中下三角的相同元素C分配一个存储单元,且当常数C为零时,不分配存储空间。则为图中的上三角阵定义一个长
9、度n(n+1)/2+1的数组,最后一个单元存储常数C。,若上三角阵以行优先顺序存储,则地址公式与对称矩阵的行优先顺序存储上三角的地址公式相似,元素的下标k为: 若上三角阵以列优先顺序存储,则地址公式与对称矩阵的列优先顺序存储上三角的地址公式相似,元素的下标k为: 下三角阵的存储同理。,3对角矩阵,所有非零元素都集中在主对角线及主对角线两侧对称的带状区域,其余部分全部为零的n阶方阵为对角矩阵。 常见的对角矩阵有三对角阵,对角阵可以按照行优先顺序、列优先顺序或对角线顺序来进行存储,每一种存储顺序下都存在非零元素的下标与一维数组中下标之间的对应关系。 以行优先顺序为例,n阶三对角阵以行优先顺序存储的
10、一维数组如下: 排在aij前面的i行中共2+(i-1)3=3i-1个元素;在第i+1行中,排在它前面的还有j-(i-1)=j-i+1个元素;则排在元素aij之前的共2i+j个元素,即下标k=2i+j。,二、 稀疏矩阵,在一个矩阵中,若非零元素的个数远远小于矩阵元素的总个数,则该矩阵称为稀疏矩阵。若mn的矩阵中有t个非零元素,则定义矩阵的稀疏因子为=t/(mn),通常取0.05的矩阵为稀疏矩阵。,稀疏矩阵的压缩存储,通常采用只存储非零元素的方法。 由于非零元素的分布没有规律,所以在存储非零元素值的同时,还需要存储非零元素的位置,即行号和列号。因此,矩阵中的每一个非零元素都由一个包括非零元素所在的
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 多维 数组 广义
链接地址:https://www.31doc.com/p-3185663.html