《《数据结构（C++版）（第二版）》-李根强-电子教案 第05章》由会员分享，可在线阅读，更多相关《《数据结构（C++版）（第二版）》-李根强-电子教案 第05章（62页珍藏版）》请在金锄头文库上搜索。
1、2019年5月24日,1,第5章 多维数组和广义表,本章学习内容,5.1 多维数组,5.2 多维数组的存储结构,5.3 特殊矩阵及其压缩存储,5.4 稀疏矩阵,5.5 广义表,2019年5月24日,2,5.1 多维数组,5.1.1 多维数组的概念,数组是大家都已经很熟悉的一种数据类型，几乎所有高级语言程序设计中都设定了数组类型。在此，我们仅简单地讨论数组的逻辑结构及其在计算机内的存储方式。,1一维数组,一维数组可以看成是一个线性表或一个向量（第2章中已经介绍），它在计算机内是存放在一块连续的存储单元中，适合于随机查找。这在第2章的线性表的顺序存储结构中已经介绍。,2二维数组,二维数组可以看成是
2、向量的推广。例如，设A是一个有m行n列的二维数组，则A可以表示为：,2019年5月24日,3,在此，可以将二维数组A看成是由m个行向量X0，X1，Xm-1T组成，其中，Xi=( ai0, ai1, ,ain-1)， 0im-1；也可以将二维数组A看成是由n个列向量y0, y1, ,yn-1组成，其中 yi=(ai0, a1i, ,am-1i)，0in-1。由此可知二维数组中的每一个元素最多可有两个直接前驱和两个直接后继（边界除外），故是一种典型的非线性结构。,3多维数组,同理，三维数组最多可有三个直接前驱和三个直接后继，三维以上的数组可以作类似分析。因此，可以把三维以上的数组称为多维数组，多维
3、数组可有多个直接前驱和多个直接后继，故多维数组是一种非线性结构。,5.1.2 多维数组在计算机内的存储,怎样将多维数组中的元素存入到计算机内存中呢？由于计算机内存结构是一维的（线性的），因此，用一维内存存放多维数组就必须按某种次序将数组元素排成一个线性序列，然后将这个线性序列顺序存放在存储器中，具体实现方法在下一节中介绍。,2019年5月24日,4,5.2 多维数组的存储结构,由于数组是先定义后使用，且为静态分配存储单元，也就是说，一旦建立了数组，则结构中的数组元素个数和元素之间的关系就不再发生变动，即它们的逻辑结构就固定下来了，不再发生变化。因此，采用顺序存储结构表示数组是顺理成章的事了。本
4、章中，仅重点讨论二维数组的存储，三维及三维以上的数组（多维），可以作类似分析。,多维数组的顺序存储有下面两种形式：行优先顺序存储和列优先顺序存储。,5.2.1 行优先顺序,1存放规则,行优先顺序也称为低下标优先存储，或左边下标优先于右边下标。具体实现时，按行号从小到大的顺序，先将第一行中元素按列号从小到大全部存放好，再存放第二行元素，第三行元素，依此类推,2019年5月24日,5,在BASIC语言、PASCAL语言、C/C+语言等高级语言程序设计中，都是按行优先顺序存放的。例如，对刚才的Amn二维数组，可用如下形式存放到内存中：a00，a01，a0n-1，a10，a11，.，a1 n-1，am
5、-1 0 ，am-1 1，am-1 n-1。即二维数组按行优先存放到内存后，变成了一个线性序列（线性表）。,因此，可以得出多维数组按行优先顺序存放到内存的规律：最左边下标变化最慢，最右边下标变化最快，右边下标变化一遍，与之相邻的左边下标才变化一次。因此，在算法中，若用循环语句的嵌套来实现按行优先顺序存放，最左边下标可以看成是最外层循环，最右边下标可以看成是最内层循环。,2019年5月24日,6,2地址计算,由于多维数组在内存中排列成一个线性序列，因此，若知道第一个元素的内存地址，如何求得其他元素的内存地址呢？我们可以将它们的地址排列看成是一个等差数列，假设每个元素占d个字节，元素aij 的存储
6、地址应为第一个元素的地址加上排在aij 前面的元素所占用的单元地址数，而aij 的前面有i行(0i-1)共in个元素，而本行前面又有j个元素，故aij的前面一共有in+j个元素，设a00的内存地址为LOC(a00)，则aij的内存地址按等差数列计算为LOC(aij)=LOC(a00)+(in+j)d。同理，三维数组Amnp按行优先顺序存放的地址计算公式为：LOC(aijk)=LOC(a000)+(inp+jp+k)d。,5.2.2 列优先顺序,1存放规则,列优先顺序也称为高下标优先存储，或右边下标优先于左边下标。具体实现时，按列号从小到大的顺序，先将第一列中的元素按行号从小到大的顺序全部存放好
7、，再存放第二列元素，第三列元素，依此类推,2019年5月24日,7,在FORTRAN语言程序设计中，数组是按列优先顺序存放的。例如，对前面提到的Amn二维数组，可以按如下的形式存放到内存中：a00，a10，am-10，a01，a11，am-1 1，a0 m-1，a1m-1，.，am-1 n-1 。 因此，二维数组按列优先顺序存放到内存后，也变成了一个线性序列（线性表）。,因此，可以得出多维数组按列优先顺序存放到内存的规律：最右边下标变化最慢，最左边下标变化最快，左边下标变化一遍，与之相邻的右边下标才变化一次。因此，在算法中，若用循环语句的嵌套来实现按列优先顺序存放，最右边下标可以看成是最外层循
8、环，最左边下标可以看成是最内层循环。,2地址计算,同样与行优先顺序存放类似，若知道第一个元素的内存地址，则同样可以求得按列优先顺序存放的某一元素aij的地址。 对二维数组Amn有：LOC(aij)=LOC(a00)+(jm+i)d 对三维数组Amnp有：LOC(aijk)=LOC(a000)+(kmn+jm+i)d,2019年5月24日,8,5.3 特殊矩阵及其压缩存储,矩阵是一个二维数组，它是很多科学与工程计算问题中研究的数学对象。矩阵可以用行优先顺序或列优先顺序的方法顺序存放到内存中，但是，当矩阵的阶数很大时，将会占用较多的存储单元。而当里面的元素分布呈现某种规律时，这时，从节约存储单元出
9、发，可考虑若干元素共用一个存储单元，即进行压缩存储。所谓压缩存储是指：为多个值相同的元素只分配一个存储空间，值为零的元素不分配空间。或者理解为：将二维数组（矩阵）压缩到一个占用存储单元数目较少的一维数组中。但是，在进行压缩存储时，虽然节约了存储单元，但怎样在压缩存储后直接找到某元素呢？因此还必须给出压缩前下标（二维数组的行、列）和压缩后（一维数组的下标）下标之间的变换公式，才能使压缩存储变得有意义。下面将分几种情况的特殊矩阵来讨论。,2019年5月24日,9,5.3.1 特殊矩阵,1对称矩阵,若一个n阶方阵A中元素满足下列条件： aij=aji 其中0i, jn-1，则称A为对称矩阵。 例如，
10、如图5-1所示是一个33的对称矩阵。,图5-1 一个对称矩阵,2三角矩阵,（1）上三角矩阵,即矩阵上三角部分元素是随机的，而下三角部分元素全部相同（为某常数C或全为0），具体形式见图5-2（a）。,（2）下三角矩阵,即矩阵的下三角部分元素是随机的，而上三角部分元素全部相同（为某常数C或全为0），具体形式见图5-2（b）。,（a）上三角矩阵 （b）下三角矩阵 图5-2 三角矩阵,2019年5月24日,10,3对角矩阵,若矩阵中所有非零元素都集中在以主对角线为中心的带状区域中，区域外的值全为0，则称为对角矩阵。 常见的对角矩阵有：三对角矩阵、五对角矩阵、七对角矩阵等。 例如，如图5-3所示为77的
11、三对角矩阵（即有三条对角线上元素非0）。,图5-3 一个77的三对角矩阵,2019年5月24日,11,5.3.2 压缩存储,在上面介绍的几种特殊矩阵（对称矩阵、上三角矩阵、下三角矩阵、三对角矩阵、多对角矩阵等）中，元素的分布有规律，从节省存储单元的角度来考虑，可以进行压缩存储，现讨论如下：,1对称矩阵,若矩阵Ann是对称的，对称的两个元素可以共用一个存储单元，这样，原来n 阶方阵需n2个存储单元，若采用压缩存储，仅需n(n+1)/2个存储单元，将近节约一半存储单元，这就是实现压缩的好处。但是，将n阶对称方阵压缩存放到一个向量空间s0到 中，我们怎样找到sk与aij的一一对应关系 呢？使我们在s
12、k中能直接找到aij。,2019年5月24日,12,我们仅以行优先顺序存放且分两种方式讨论：,（1）只存放下三角部分 由于对称矩阵关于主对角线对称，故我们只需存放主对角线及主对角线以下的元素。这时，a00存入s0，a10 存入s1，a11存入s2，an-1n-1存入 中，具体过程参见图5-4。,（a）一个下三角矩阵,（b）下三角矩阵的压缩存储形式 图5-4 对称矩阵及用下三角压缩存储,2019年5月24日,13,这时sk与aij的对应关系为： i(i+1)/2+j 当 ij k= j(j+1)/2+i 当 ij,上面的对应关系读者很容易推出： 当ij时，aij在下三角部分中，aij前面有i行，
13、共有1+2+3+i个元素，而aij是第i行的第j个元素，即有k=1+2+3+i+j=i(i+1)/2+j。 当ij时，aij在上三角部分中，但与aji对称，故只需在下三角部分中找aij即可，故只需将i与j交换即可，即k=j(j+1)/2+i。,（2）只存放上三角部分 对于对称矩阵，除了用下三角形式存放外，还可以用上三角形式存放，这时a00存入s0，a01存入s1，a02存入s2，a0n-1存入sn，a11存入sn+1，an-1n-1存入s 中，具体参见图5-5。,2019年5月24日,14,（a）一个上三角矩阵,（b）上三角矩阵的压缩存储形式 图5-5 对称矩阵及用上三角压缩存储,这时sk与a
14、ij的对应关系可以按下面的方法推出： 当ij时，aij在上三角部分中，前面的行号从0i-1，共有i行，第0行有n个元素，第1行有n-1个元素，第i-1行有n-(i-1)个元素，因此，前面i行共有n+n-1+n-(i-1)=i*n-个元素，而aij是本行第j-i个元素，故k=i*n-+j-i。,2019年5月24日,15,当ij时，由对称关系，交换i与j即可。 即有k=j*n-+i-j。,故sk与aij的对应关系为： i*n-+j-i ij K= j*n-+i-j ij,2三角矩阵,（1）下三角矩阵 下三角矩阵的压缩存放与对称矩阵用下三角形式存放类似，但必须多一个存储单元存放上三角部分元素，使用
15、的存储单元数目为n(n+1)/2+1。故可以将nn的下三角矩阵压缩存放到只有n(n+1)/2+1个存储单元的向量中。,假设仍按行优先存放，这时sk与aij的对应关系为： i(i+1)/2+j ij k= n(n+1)/2 ij,2019年5月24日,16,（2）上三角矩阵,和下三角矩阵的存储类似，共需n(n+1)/2+1个存储单元，假设仍按行优先顺序存放，这时sk与aij的对应关系为： i*n- i(i-1)/2+j-i ij k= n(n+1)/2 ij,3对角矩阵,我们仅讨论三对角矩阵的压缩存储。五对角矩阵、七对角矩阵等，读者可以作类似分析。 在一个nn的三对角矩阵中，只有n+n-1+n-1个非零元，故只需3n-2个存储单元即可，零元已不占用存储单元。,故可将nn三对角矩阵Ann压缩存放到只有3n-2个存储单元的s3n-2向量中，假设仍按行优先顺序存放，则sk与aij的对应关系为：,3i-1 i=j+1 k= 3i i=j或k=2i+j 3i+1 i=j-1,2019年5月24日,17,5.4 稀疏矩阵,在上节提到的特殊矩阵中，元素的分布呈现某种规律，故一定能找到一种合适的方法，将它们进行压缩存放。但是，在实际应用中，我们还经
