数据结构 多维数组及广义表课件.ppt

《数据结构 多维数组及广义表课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四章多维数组及广义表前几章介绍的数据结构都是线性结构，数据元素都属于原子类型，其值不分解使用。本章讨论的多维数组和广义表是线性结构的推广，从整体上看它们是多个元素组成的线性表，而从局部上看线性表中的数据元素不一定是原子类型，即数据元素又可以具有某种数据结构。主要内容：4．1多维数组多维数组的逻辑结构特征及存储方式4．2矩阵的压缩存储特殊矩阵和稀疏矩阵的压缩存储4．3广义表广义表的定义和运算4．1多维数组一、多维数组的逻辑结构特征数组中的元素具有相同类型，且下标一般具有固定的上界和下界。数组可以是一维的，也可以是多维的。

2、本章主要以二维数组为例来分析多维数组的逻辑结构特征和存储结构。二维数组可以看成是由多个一维数组组成的。例如，二维数组Amn既可看成由m个行向量组成的线性表，也可看成是由n个列向量组成的线性表。二维数组的逻辑结构具有如下特征：a00为开始结点，它没有直接前趋；am-1,n-1为终端结点，它没有直接后继；结点a0,n-1和am-1,0都有一个直接前趋和一个直接后继；除以上四个结点外，第一行和第一列的元素都有一个直接前趋和两个直接后继，最后一行和最后一列的元素都有两个直接前趋和一个直接后继；其余的非边界元素aij同时处于第i+

3、1行的行向量中和第j+1列的列向量中，都有两个直接前趋和两个直接后继。二、多维数组的存储二维数组一般采用顺序存储。由于内存单元是一维的线性关系，而二维数组中元素之间的关系是非线性的，所以若要顺序存储二维数组，首先需要将二维数组中的元素按照某种原则排列成点的线性序列，然后再依次存放到连续的存储单元中。通常二维数组有行优先和列优先两种排列原则。（1）行优先原则，是指先排列二维数组的第一行中的数据元素，再排列第二行中的数据元素，……，以此类推。（2）列优先原则，是指先排列二维数组的第一列中的数据元素，再排列第二列中的数据元素，

4、……，以此类推。数据元素的存储地址可根据数组的首地址、元素的存储空间大小及元素的序号三个信息计算出来，从而实现随机存取。若二维数组Amn按行优先原则排列，其线性序列为：a00，a01，…，a0,n-1，a10，a11，…，a1,n-1，……，am-1,n-1存储后的内存状态如图所示:aij的地址为：LOC（aij）=LOC（a00）+（i×n+j）×d若二维数组Amn按列优先原则排列，则线性序列为：a00，a10，…，am-1,0，a01，a11，…，am-1,1，……，am-1,n-1存储后的内存状态如图所示:aij的

5、地址为：LOC（aij）=LOC（a00）+（j×m+i）×d二维数组的逻辑特征和存储方法可以很容易地推广到多维数组。例如三维数组可以看成是由二维数组组成的线性表，三维数组中的每个元素最多有三个直接前趋和三个直接后继。同样，行优先原则和列优先原则也可以推广到多维数组，按行优先原则时先排最右的下标，按列优先原则时先排最左的下标。得到行优先或列优先序列后，可以把它们依次存放在连续的存储空间中，这就是多维数组的顺序存储，同样可实现随机存取。4．2矩阵的压缩存储计算机在处理工程问题时，通常使用二维数组来存储矩阵，但是实际问题中的

6、矩阵往往阶数较大，而有效数据（非零元素）很少且分布没有规律，若用上面讨论的二维数组存储，其存储密度小（存储了大量的零元素），浪费了存储空间。矩阵的压缩存储通常指在存储数据元素时，只存储非零元素，对零元素不分配空间；为多个相同的非零元素分配一个存储空间。下面分别讨论特殊矩阵和稀疏矩阵的压缩存储。一、特殊矩阵特殊矩阵是指非零元素或零元素分布有一定规律的矩阵。例如，对称矩阵、三角矩阵（上三角阵和下三角阵）及对角矩阵，特殊矩阵可以根据元素的分布规律来进行压缩存储。不同的特殊矩阵中元素的分布规律不同，压缩存储的方法也不同。1．对称

7、矩阵满足aij=aji（1≤i，j≤n）的n阶方阵称为对称矩阵。对称矩阵中的数据元素按主对角线对称，只需存储下三角或上三角中的元素即可。上三角或下三角中的元素可按行优先或列优先存储。由此可得四种存储方法：行优先顺序存储下三角列优先顺序存储下三角行优先顺序存储上三角列优先顺序存储上三角。每种方法中元素的存储地址都可以通过公式计算出来，且具有随机存取的特点。（1）行优先顺序存储下三角以图（a）所示的n阶方阵为例，行优先顺序存储下三角时元素的排列顺序如图（b）所示，存储在一维数组中如图（c）所示。（a）n阶对称矩阵（b）行优先

8、顺序存储下三角（c）对应的一维数组设长度为n（n+1）/2的数组sa存储下三角中的元素。设矩阵下三角中的某一个元素aij（i≥j）对应存储在一维数组的下标变量sa[k]中，则上三角中的某一个元素aij（i