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

1、第四章 多维数组及广义表 v前几章引见的数据构造都是线性构造，数据元素都属于原子类型，其值不分解运用。v本章讨论的多维数组和广义表是线性构造的推行，从整体上看它们是多个元素组成的线性表，而从部分上看线性表中的数据元素不一定是原子类型，即数据元素又可以具有某种数据构造。主要内容：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按行优先原那么陈列，其线性序列为： a00，a01，a0,n

4、-1，a10，a11，a1,n-1，am-1,n-1 存储后的内存形状如下图: aij的地址为：LOCaij= LOCa00+in+j d 假设二维数组Amn按列优先原那么陈列，那么线性序列为：a00，a10，am-1,0，a01，a11，am-1,1，am-1,n-1 存储后的内存形状如下图: aij的地址为：LOCaij= LOCa00+jm+i d 二维数组的逻辑特征和存储方法可以很容易地推行到多维数组。例如三维数组可以看成是由二维数组组成的线性表，三维数组中的每个元素最多有三个直接前趋和三个直接后继。同样，行优先原那么和列优先原那么也可以推行到多维数组，按行优先原那么时先排最右的下标，

5、按列优先原那么时先排最左的下标。得到行优先或列优先序列后，可以把它们依次存放在延续的存储空间中，这就是多维数组的顺序存储，同样可实现随机存取。 42 矩阵的紧缩存储计算机在处置工程问题时，通常运用二维数组来存储矩阵，但是实践问题中的矩阵往往阶数较大，而有效数据非零元素很少且分布没有规律，假设用上面讨论的二维数组存储，其存储密度小存储了大量的零元素，浪费了存储空间。 矩阵的紧缩存储通常指在存储数据元素时，只存储非零元素，对零元素不分配空间；为多个一样的非零元素分配一个存储空间。下面分别讨论特殊矩阵和稀疏矩阵的紧缩存储。 一、特殊矩阵特殊矩阵是指非零元素或零元素分布有一定规律的矩阵。例如，对称矩阵

6、、三角矩阵上三角阵和下三角阵及对角矩阵，特殊矩阵可以根据元素的分布规律来进展紧缩存储。不同的特殊矩阵中元素的分布规律不同，紧缩存储的方法也不同。1 1对称矩阵对称矩阵满足aij=aji1i，jn的n阶方阵称为对称矩阵。 对称矩阵中的数据元素按主对角线对称，只需存储下三角或上三角中的元素即可。上三角或下三角中的元素可按行优先或列优先存储。由此可得四种存储方法： 行优先顺序存储下三角列优先顺序存储下三角行优先顺序存储上三角列优先顺序存储上三角。每种方法中元素的存储地址都可以经过公式计算出来，且具有随机存取的特点。1行优先顺序存储下三角行优先顺序存储下三角 以图以图a所示的所示的n阶方阵为例，行优先

7、顺序阶方阵为例，行优先顺序存储下三角时元素的陈列顺序如图存储下三角时元素的陈列顺序如图b所示所示，存储在一维数组中如图，存储在一维数组中如图c所示。所示。 a n阶对称矩阵 b 行优先顺序存储下三角c对应的一维数组设长度为nn+1/2的数组sa存储下三角中的元素。设矩阵下三角中的某一个元素aijij对应存储在一维数组的下标变量sak中，那么上三角中的某一个元素aiji0记为：LS =a1， a2， ，ai， an其中，LS是广义表的名字。a1为广义表的第一个元素，ai 为广义表的第i个元素。显然，广义表是一种递归的数据构造，由于广义表中的数据元素还可以是广义表。当广义表中的一切元素都是原子时，

8、此广义表就是线性表。 下面是一些广义表的例子：1A=A是一个空表，其长度为0。2B=a，bB是一个长度为2的广义表，它的两个元素都是原子，因此它就是一个线性表。3C=c，B=c，a，bC是长度为2的广义表，第一个元素是原子c，第二个元素是子表B。4D=B，C，d=a，b，c，a，b，dD是长度为3的广义表，第一个元素和第二个元素都为子表，第三个元素为原子d。5E=a，E=a，a，a， E是长度为2的广义表，第一个元素是原子，第二个元素是E本身，它是一个无限递归的广义表。 广义表还有其他的表示方法，如：1带名字的广义表表示：在每个表的前面冠以该表的名字A Ba，bCc，Ba，bD Ba，b，Cc

9、，a，b，dEa，Ea，Ea，E2广义表的图形表示 用非分支结点表示原子，用分支结点表示广义表空表除外，空表中不含元素，所以也用非分支结点表示。广义表分为：线性表、纯表、再入表和递归表四种。当广义表中的元素全部都是原子时，广义表就是线性表，因此也可以说线性表是广义表的一种特殊方式。上图中的广义表B就是一个线性表。假设广义表中既包含原子，又包含子表，但没有共享和递归，如广义表C，那么此时的广义表就是一棵树将在第五章讨论，称这种广义表为纯表。允许结点的共享但不允许递归的广义表为再入表，上图中的广义表D，子表B为共享结点，它既是表D的一个元素，又是子表C的一个元素。这样的广义表与数据构造的图形构造对

10、应将在第六章讨论。允许递归的表称为递归表，上图中的广义表E为递归表，表E是其本身的子表。递归表、再入表、纯表、线性表之间的关系满足：递归表 再入表 纯表 线性表 广义表可以兼容线性表、树和图等各种经典的数据构造，广义表的大部分运算都与经典数据构造的运算类似。四个特殊的运算：取表头HeadLS、取表尾TailLS、求表深、求表长。广义表的表头Head为广义表的第一个元素，广义表的表尾Tail为广义表中除第一个元素外，剩下一切的元素组成的广义表。对广义表LS =a1， a2， ， an来说，取表头、取表尾的运算定义为： HeadLS =a1，TailLS = a2， ， an 。例如：Heada，b= aTaila，b=bHeada= aTaila，b，c，a，b= c，a，b任何一个非空广义表LS =a1， a2， ， an均可分解为表头和表尾两个部分。反之，一对表头和表尾也可独一确定一个广义表。根据表头、表尾的定义可知：任何一个非空广义表的表头是表中第一个元素，