数据结构多维数组及广义表

,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第四章 多维数组及广义表,前几章介绍的数据结构都是线性结构，数据元素都属于原子类型，其值不分解使用。,本章讨论的多维数组和广义表是线性结构的推广，从整体上看它们是多个元素组成的线性表，而从局部上看线性表中的数据元素不一定是原子类型，即数据元素又可以具有某种数据结构。,主要内容：,4,1,多维数组,多维数组的逻辑结构特征及存储方式,4,2,矩阵的压缩存储,特殊矩阵和稀疏矩阵的压缩存储,4,3,广义表,广义表的定义和运算,41 多维数组,一、多维数组的逻辑结构特征,数组中的元素具有相同类型，且下标一般具有固定的上界和下界。,数组可以是一维的，也可以是多维的。,本章主要以二维数组为例来分析多维数组的逻辑结构特征和存储结构。,二维数组可以看成是由多个一维数组组成的。例如，二维数组,A,mn,既可看成由,m,个行向量组成的线性表，也可看成是由,n,个列向量组成的线性表。,二维数组的逻辑结构具有如下特征：,a,00,为开始结点，它没有直接前趋；,a,m-1,n-1,为终端结点，它没有直接后继；,结点,a,0,n-1,和,a,m-1,0,都有一个直接前趋和一个直接后继；,除以上四个结点外，第一行和第一列的元素都有一个直接前趋和两个直接后继，最后一行和最后一列的元素都有两个直接前趋和一个直接后继；,其余的非边界元素,a,ij,同时处于第,i+1,行的行向量中和第,j+1,列的列向量中，都有两个直接前趋和两个直接后继。,二、多维数组的存储,二维数组一般采用顺序存储。,由于内存单元是一维的线性关系，而二维数组中元素之间的关系是非线性的，所以若要顺序存储二维数组，首先需要将二维数组中的元素按照某种原则排列成点的线性序列，然后再依次存放到连续的存储单元中。,通常二维数组有,行优先,和,列优先,两种排列原则。,（,1,）行优先原则，是指先排列二维数组的第一行中的数据元素，再排列第二行中的数据元素，,，以此类推。,（,2,）列优先原则，是指先排列二维数组的第一列中的数据元素，再排列第二列中的数据元素，,，以此类推。,数据元素的存储地址可根据数组的首地址、元素的存储空间大小及元素的序号三个信息计算出来，从而实现随机存取。,若二维数组,A,mn,按行优先原则排列，其线性序列为：,a,00,，,a,01,，,，,a,0,n-1,，,a,10,，,a,11,，,，,a,1,n-1,，,，,a,m-1,n-1,存储后的内存状态如图所示,:,a,ij,的地址为：,LOC,（,a,ij,）,=LOC,（,a,00,）,+,（,in+j,）,d,若二维数组,A,mn,按列优先原则排列，则线性序列为：,a,00,，,a,10,，,，,a,m-1,0,，,a,01,，,a,11,，,，,a,m-1,1,，,，,a,m-1,n-1,存储后的内存状态如图所示,:,a,ij,的地址为：,LOC,（,a,ij,）,=LOC,（,a,00,）,+,（,jm+i,）,d,二维数组的逻辑特征和存储方法可以很容易地推广到多维数组。,例如三维数组可以看成是由二维数组组成的线性表，三维数组中的每个元素最多有三个直接前趋和三个直接后继。,同样，行优先原则和列优先原则也可以推广到多维数组，按行优先原则时先排最右的下标，按列优先原则时先排最左的下标。,得到行优先或列优先序列后，可以把它们依次存放在连续的存储空间中，这就是多维数组的顺序存储，同样可实现随机存取。,42 矩阵的压缩存储,计算机在处理工程问题时，通常使用二维数组来存储矩阵，但是实际问题中的矩阵往往阶数较大，而有效数据（非零元素）很少且分布没有规律，若用上面讨论的二维数组存储，其存储密度小（存储了大量的零元素），浪费了存储空间。,矩阵的,压缩存储,通常指在存储数据元素时，只存储非零元素，对零元素不分配空间；为多个相同的非零元素分配一个存储空间。,下面分别讨论特殊矩阵和稀疏矩阵的压缩存储。,一、特殊矩阵,特殊矩阵是指非零元素或零元素分布有一定规律的矩阵。例如，对称矩阵、三角矩阵（上三角阵和下三角阵）及对角矩阵，特殊矩阵可以根据元素的分布规律来进行压缩存储。,不同的特殊矩阵中元素的分布规律不同，压缩存储的方法也不同。,1,对称矩阵,满足,aij=aji,（,1i,，,jn,）的,n,阶方阵称为对称矩阵。,对称矩阵中的数据元素按主对角线对称，只需存储下三角或上三角中的元素即可。上三角或下三角中的元素可按行优先或列优先存储。由此可得四种存储方法：,行优先顺序存储下三角,列优先顺序存储下三角,行优先顺序存储上三角,列优先顺序存储上三角。,每种方法中元素的存储地址都可以通过公式计算出来，且具有随机存取的特点。,（,1,）行优先顺序存储下三角,以图（,a,）所示的,n,阶方阵为例，行优先顺序存储下三角时元素的排列顺序如图（,b,）所示，存储在一维数组中如图（,c,）所示。,（,a,）,n,阶对称矩阵 （,b,）行优先顺序存储下三角,（,c,）对应的一维数组,设长度为,n,（,n+1,）,/2,的数组,sa,存储下三角中的元素。,设矩阵下三角中的某一个元素,a,ij,（,ij,）对应存储在一维数组的下标变量,sak,中，则上三角中的某一个元素,a,ij,（,i0,）记为：,LS=,（,a,1,，,a,2,，,，,a,i,，,，,a,n,）,其中，,LS,是广义表的名字。,a,1,为广义表的第一个元素，,a,i,为广义表的第,i,个元素。显然，广义表是一种递归的数据结构，因为广义表中的数据元素还可以是广义表。当广义表中的所有元素都是原子时，此广义表就是线性表。,下面是一些广义表的例子：,（,1,）,A=,（）,A,是一个空表，其长度为,0,。,（,2,）,B=,（,a,，,b,）,B,是一个长度为,2,的广义表，它的两个元素都是原子，因此它就是一个线性表。,（,3,）,C=,（,c,，,B,）,=,（,c,，（,a,，,b,）,C,是长度为,2,的广义表，第一个元素是原子,c,，第二个元素是子表,B,。,（,4,）,D=,（,B,，,C,，,d,）,=,（,a,，,b,），（,c,，（,a,，,b,），,d,）,D,是长度为,3,的广义表，第一个元素和第二个元素都为子表，第三个元素为原子,d,。,（,5,）,E=,（,a,，,E,）,=,（,a,，（,a,，（,a,，（,）,E,是长度为,2,的广义表，第一个元素是原子，第二个元素是,E,自身，它是一个无限递归的广义表。,广义表还有其他的表示方法，如：,（,1,）带名字的广义表表示：在每个表的前面冠以该表的名字,A,（）,B,（,a,，,b,）,C,（,c,，,B,（,a,，,b,）,D,（,B,（,a,，,b,），,C,（,c,，（,a,，,b,），,d,）,E,（,a,，,E,（,a,，,E,（,a,，,E,（,）,（,2,）广义表的图形表示,用非分支结点表示原子，用分支结点表示广义表（空表除外，空表中不含元素，所以也用非分支结点表示）。,广义表分为：线性表、纯表、再入表和递归表四种。,当广义表中的元素全部都是原子时，广义表就是线性表，因此也可以说线性表是广义表的一种特殊形式。上图中的广义表,B,就是一个线性表。,若广义表中既包含原子，又包含子表，但没有共享和递归，如广义表,C,，则此时的广义表就是一棵树（将在第五章讨论），称这种广义表为,纯表,。,允许结点的共享但不允许递归的广义表为,再入表,，上图中的广义表,D,，子表,B,为共享结点，它既是表,D,的一个元素，又是子表,C,的一个元素。这样的广义表与数据结构的图形结构对应（将在第六章讨论）。,允许递归的表称为,递归表,，上图中的广义表,E,为递归表，表,E,是其自身的子表。,递归表、再入表、纯表、线性表之间的关系满足：,递归表 再入表 纯表 线性表,广义表可以兼容线性表、树和图等各种经典的数据结构，广义表的大部分运算都与经典数据结构的运算类似。,四个特殊的运算：取表头,Head,（,LS,）、取表尾,Tail,（,LS,）、求表深、求表长。,广义表的,表头,（,Head,）为广义表的第一个元素，广义表的,表尾,（,Tail,）为广义表中除第一个元素外，剩下所有的元素组成的广义表。,对广义表,LS=,（,a,1,，,a,2,，,，,a,n,）来说，取表头、取表尾的运算定义为：,Head,（,LS,）,=a,1,，,Tail,（,LS,）,=,（,a,2,，,，,a,n,）。,例如：,Head,（,a,，,b,）,=a,Tail,（,a,，,b,）,=,（,b,）,Head,（,a,）,=a,Tail,（,a,，,b,），,c,，（,a,，,b,）,=,（,c,，（,a,，,b,）,任何一个非空广义表,LS=,（,a,1,，,a,2,，,，,a,n,）均可分解为表头和表尾两个部分。反之，一对表头和表尾也可唯一确定一个广义表。根据表头、表尾的定义可知：任何一个非空广义表的表头是表中第一个元素，它可以是原子，也可以是子表，但表尾必定是子表。,广义表（）和（）不同。前者是长度为,0,的空表，而后者是长度为,l,的非空表，其表头和表尾均是空表（）。,广义表是一个多层次的结构，广义表的元素可以是子表，子表的元素仍可以是子表。若将广义表的子表展开成全部由原子组成，则可将广义表的,深度,定义为表中所含括号的最大层数；而广义表的,长度,为表中包含的元素个数。,