数据结构与算法 课件 第5章 数组和广义表

5.1数组

5.2特殊矩阵的压缩存储

5.3稀疏矩阵的压缩存储

5.4广义表5.1数组5.1.1数组的基本概念数组中各元素具有相同的类型，数组元素具有值和确定元素位置的下标。通常可以把一维数组称为向量，多维数组是向量的扩充。由于数组中各元素具有统一的类型，并且数组元素的下标一般具有固定的上界和下界。因此，数组的处理比其他复杂的结构更为简单。一维数组可表示为An = [a1，a2，…，an]，每个数据元素对应一个数组下标，它具有线性表的结构，即除了第一个元素和最后一个元素，每个元素存在一个直接前驱元素和一个直接后继元素。二维数组可表示为3在二维数组中，每个数据元素对应一对数组下标，在行方向上和列方向上都存在一个线性关系，即存在两个前驱(前件)和两个后继(后件)；也可看作是以线性表为数据元素的线性表。也就是说，一个m行n列的二维数组，可以看成由m个长度为n的一维数组(行)所组成的线性表，也可以看成n个长度为m的一维数组(列)所组成的线性表，即在n维数组中，每个数据元素对应n个下标，受n个关系的制约，其中任一个关系都是线性关系。它可看作是数据元素为n-1维数组的一维数组。多维数组是对线性表的扩展，线性表中的数据元素本身又是一个多层次的线性表。5.1.2数组的存储结构在计算机中一般采用顺序存储结构来存放数组。而内存结构是一维的，因此存放二维数组或多维数组，就必须按照某种顺序将数组中的元素形成一个线性序列，然后将这个线性序列存放在内存中。下面讨论二维数组的存储方式。1)行优先顺序存储将数组元素按行向量的顺序存储，即第i+1行的元素存放在第i行的元素之后。元素存储的线性序列为2)列优先顺序存储将数组元素按列向量的顺序存储，即第j+1列的元素存放在第j列的元素之后。元素存储的线性序列为在多数计算机语言中，二维数组都是按行优先的顺序存储的，少数语言采用按列优先的顺序存储。按照上述两种存储二维数组的线性序列，若已知数组存储的起始地址，下标的上、下界，以及每个数组元素所占用的存储单元个数，就可以计算出元素aij的存储地址，从而对数组元素随机存取。例如，二维数组A[c1..d1,c2..d2] 按行优先的顺序存储在内存中，假设每个元素占d个存储单元，计算元素aij的地址公式为其中Loc(ac1c2)是数组的起始地址；元素aij前面的i-c1行中共有(i-c1) × (d2-c2+1)个元素，第i行上元素aij前面又有j-c2个元素。类似地，我们可以得出当二维数组A[c1…d1，c2…d2]按列优先的顺序存储在内存中时，元素aij的地址计算公式为5.2特殊矩阵的压缩存储5.2.1三角矩阵在n阶方阵中，以主对角线进行划分，如果矩阵的下三角(不包括主对角线)中的元素均为值相同的常数，则称为上三角矩阵；反之称为下三角矩阵。在多数情况下，三角矩阵的常数为零。这两种三角矩阵如图5.1所示。为简便起见，可以用向量A[0…n(n+1)/2]压缩存储三角矩阵，其中A[0]～A[n(n+1)/2-1]存储矩阵下(上)三角中的元素，向量的最后一个分量A[n(n+1)/2]存储三角矩阵中的常数。下三角矩阵按行优先的顺序存储，A[k]与aij的对应关系为上三角矩阵按列优先的顺序存储，A[k]与aij的对应关系为5.2.2对称矩阵若n阶方阵A中的元素关于主对角线对称，即满足下述性质：则称A为对称矩阵。如果采用一维数组存储矩阵中的上三角或下三角元素，使对称的两个元素共享同一个存储空间，可以节省近一半的存储空间。存储n阶对称方阵时，一维数组的长度为n(n+1)/2。同样，可以用向量A[0…n(n+1)/2-1]压缩存储对称矩阵。下三角矩阵按行优先的顺序存储，A[k]与aij的对应关系为对于上三角矩阵中的元素aij(i<j)，因为aij = aji，相当于按列优先的顺序存储，所以A[k]与aij的对应关系为对于任意给定一组下标(i，j)，均可在A[n(n+1)/2]中找到矩阵元素aij；反之，对所有的k = 0，1，2…，

，都能确定元素A[k]在矩阵中的位置(i，j)。由此，称A[n(n+1)/2]为n阶对称矩阵A的压缩存储，见图5.2。图5.3给出了一个4阶对称方阵，按行优先的顺序存储下三角矩阵，按列优先的顺序存储上三角矩阵。图5.4是其存储形式。5.2.3对角矩阵所谓对角矩阵，是指方阵中的所有非零元素集中在以主对角线为中心的带状区域内，带状区域之外的元素值均为零。带宽为3的对角矩阵又称为三对角矩阵，如图5.5所示。显然，当 |i-j| > 1时，元素aij为0。一般地，对于k对角矩阵(k为奇数)，当 |i-j| > (k-1)/2时，元素aij为0。n阶三对角矩阵有3n-2个非零元素，采用向量A[0…3n-3]按行优先的顺序压缩存储三对角矩阵。每个非零元素与向量下标的对应关系为上述各种特殊矩阵的非零元素的分布都具有一定的规律，采用向量压缩存储，通过元素与向量的对应关系，仍然可以对矩阵中的元素进行随机存取。5.3稀疏矩阵的压缩存储5.3.1稀疏矩阵的三元组表存储将稀疏矩阵中的非零元素的行号、列号和元素值作为一个三元组(i,j,aij)，所有非零元素的三元组按行优先(或列优先)的顺序排列，便得到一个结点均是三元组的线性表。我们将该线性表的顺序存储结构称为三元组表。在下面的讨论中，三元组均以按行优先的顺序排列。在三元组表中，除了要表示非零元素之外，还需要表示矩阵的行、列数及非零元素的总个数。三元组表的结构类型定义描述为设a为spmattrix型指针变量，图5.6(a)所示的稀疏矩阵A的三元组表如图5.6(b)所示。下面以矩阵的转置为例，说明采用三元组表的形式存储稀疏矩阵，如何实现矩阵的转置运算。一个m × n的矩阵A，它的转置矩阵B是一个n × m的矩阵，且A[i][j] = B[j][i]，1≤i≤m，1≤j≤n，即A的行是B的列，A的列是B的行。例如图5.6(a)中的A和图5.7(a)中的B互为转置矩阵。为了叙述方便，下面将三元组表 *a中的成员a->data简称为三元组表，因为相对于其他成员而言，它是主要的。将A转置为B，就是将A的三元组表a->data置换为B的三元组表b->data，如果只是互换a->data中i和j的内容，那么所得到的b->data是按列存放的矩阵B的三元组表，还必须重新排列b->data中各结点的顺序。由于A的列是B的行，如果按a->data的列序转置，所得到的转置矩阵B的三元组表b->data必定是按行优先的顺序存放。算法的基本思想是：对a->data按列扫描n趟，在第col趟扫描中，找出所有列号等于col的那些三元组，将它们的行号、列号和元素值分别放入b->data的列号、行号和元素值中，即可得到B的按行优先的压缩存储表示。以图5.6和图5.7为例，设col = 1，则扫描a->data找到列号为1的三元组依次是(1,1,3)和(3,1,2)，存入b->data后为(1,1,3)和(1,3,2)，恰好为B中第1行的两个非零元素。只要依次取col=1,2,3,4，即可得到a->data的转置矩阵b->data。下面给出具体的算法。算法5.1矩阵的转置(用三元组表存储矩阵)。该算法的时间主要耗费在col和ano的二重循环上，算法的时间复杂度为O(n × t)，t <<m × n。而通常用二维数组表示矩阵时，其转置算法的时间复杂度是O(m × n)。如果非零元素个数大于矩阵的行数，从转置算法的时间复杂度来说，采用三元组表存储就不合适了，可考虑十字链表存储。5.3.2稀疏矩阵的十字链表存储当矩阵的非零元素个数和位置在操作过程中变化较大时，不宜采用顺序存储结构来表示三元组的线性表。例如，对于“将矩阵B加到矩阵A上”的操作，由于非零元素的插入或删除将会引起A.data中元素的移动。对于这种情况，采用十字链表存储稀疏矩阵更为恰当。十字链表存储稀疏矩阵的基本思想是将每个非零元素对应的三元组作为链表的结点，结点由5个域组成，其结构如图5.8所示。结点的结构体类型定义如下：图5.9给出了一个3行4列有4个非零元素的稀疏矩阵存储在十字链表的示意图。我们可以看到同一行的非零元素结点通过right域链接成一个循环链表，同一列的非零元素结点通过down域链接成一个循环链表，每个非零元素既是某个行链表中的一个结点，又是某个列链表中的一个结点，整个矩阵构成类一个十字交叉的链表，故称这样的存储结构为十字链表。可用两个分别存储行链表和列链表头指针的一维数组表示，h[i]是其数组元素。5.4广义表5.4.1广义表的概念及基本运算1．广义表概述广义表一般记作其中，LS是广义表的名称；n(≥0)是它的长度。在线性表的定义中，ai(1≤i≤n)只限于单元素。而在广义表的定义中，ai可以是单元素，也可以是广义表，分别称为广义表LS的原子和子表。习惯上，用大写字母表示广义表的名称，用小写字母表示原子。当广义表LS非空时，称第一个元素a1为LS的表头(Head)，称其余元素组成的表(a2,a3,…,an)是LS的表尾(Tail)。因此，任何一个非空广义表的表头可能是单元素，也可能是广义表，但其表尾一定是广义表。显然，广义表的定义是一个递归的定义，因为在描述广义表时又用到了广义表自身的概念。2．广义表的特点从上述定义和例子可推出广义表具有如下特点：(1)广义表是一种线性结构，其长度为最外层包含的元素个数。(2)广义表的元素可以是子表，而子表的元素还可以是子表，因此广义表是一种多层次的结构，可以用图形象地表示。(3)一个广义表可为其他广义表所共享。(4)广义表可以是一个递归的表，即广义表也可以是其本身的一个子表。广义表的这些特点对于它的应用起到了很大的作用。广义表可以看作是线性表的推广，因此线性表只是广义表的一个特例。由于广义表的结构相当灵活，在某种前提下它可以兼容线性表、数组、树和有向图等各种常用的数据结构。例如可以将二维数组看作是广义表，二维数组每行(或每列)作为子表来处理。由于广义表具有线性表、数组、树和图这些常用数据结构的特点，而且可以有效地利用存储空间，因此广义表在许多领域都得到了广泛的应用。3．广义表的基本操作广义表作为一种数据结构，也具有一组基本操作，常用的基本操作如下：(1) InitGList(&L)；初始条件：广义表L不存在。操作结果：创建空的广义表L。(2) GreatGList(&L,S)；初始条件：S是广义表的书写形式串。操作结果：由S建立广义表L。(3) DestroyGList(&L)；初始条件：广义表L存在。操作结果：销毁广义表L。(4) CopyGList(&T,L)；初始条件：广义表L存在。操作结果：由广义表L复制得到广义表T。(5) GListLength(L)；初始条件：广义表L存在。操作结果：求广义表L的长度，即元素个数。(6) GListDepth(L)；初始条件：广义表L存在。操作结果：求广义表L的深度，所谓广义表的深度是指广义表中所包含的括号层数。(7) GListEmpty(L)；初始条件：广义表L存在。操作结果：判定广义表L是否为空。(8) GetHead(L)；初始条件：广义表L存在。操作结果：取广义表L的头。(9) GetTail(L)；初始条件：广义表L存在。操作结果：取广义表L的尾。(10) InsertFirst_GL(&L,e)；初始条件：广义表L存在。操作结果：插入元素e作为广义表L的第一元素。(11) DeleteFirst_GL(&L,e)；初始条件：广义表L存在。操作结果：删除广义表L的第一元素，并用e返回其值。(12) Traverse_GL(L,Visit())；初始条件：广义表L存在。操作结果：遍历广义表L，用函数Visit处理每个元素。5.4.2广义表的存储结构由于广义表(a1,a2,…,an)中的数据元素可以是原子，也可以是子表，因此它是一种带有层次的非线性结构，难以用顺序存储结构表示，通常采用链式存储结构来存储广义表。链式存储结构较为灵活，易于解决广义表的共享与递归问题。在链式存储结构中，每个数据元素都可以用一个结点来表示。根据结点形式的不同，广义表的链式存储结构又可以分为头尾表示法和孩子兄弟表示法两种不同的存储形式。1.头尾表示法如何设定结点的结构？由于广义表中的元素可以是子表，也可以是原子，由此需要两种结构的结点：一种是表结点，用以表示子表；另一种是原子结点，用以表示原子。从5.4.1节可知：若子表不为空，则可分解为表头和表尾；反之，一对确定的表头和表尾可唯一确定子表。由此，一个表结点可由3个域组成，分别是标志域、指向表头的指针域和指向表尾的指针域，如图5.11(a)所示。而原子结点只需标志域和值域两个域，如图5.11(b)所示。标志域tag=1，表示结点为表结点；tag=0，表示结点为原子结点。广义表头尾表示法的结点类型定义如下：头尾表示法存储广义表有如下三个特点：(1)若广义表为空表，则表头指针为空。对于任何非空广义表，其表头指针均指向一个表结点，且该结点中的hp域指向广义表的表头(原子结点或者表结点)，tp域