《数据结构与算法》第5章 多维数组与广义表

null数据结构与算法 （C++语言版）数据结构与算法 （C++语言版）第5章 多维数组与广义表数 组数 组数组的定义 与线性表一样，数组中所有的数据元素都必须属于同一数据类型，其特点是，每个数据元素可以又是一个线性表结构。若线性表中的数据元素为简单元素，则称为一维数组，即向量；若一维数组中的数据元素又是一维数组，则称为二维数组；依次类推，若二维数组中的元素又是一个一维数组结构，则称为三维数组。因此，线性表结构可看成是数组结构的一个特例，而数组结构则是线性表结构的扩展。 数 组数 组例如，在（a）所示的m行n列二维数组中，每个数据元素ai,j都受两个关系——行关系和列关系的约束。在行关系中，ai,j+1是ai,j的直接后继元素。在列关系中，ai+1,j是ai,j的直接后继元素，该数组元素的个数为m×n。该数组可被看成是一个线性表A=(a0, a1, …, ap)，p = m–1或n–1，其中每个元素aj可以是如（b）所示的列向量形式线性表aj=(a0,j, a1,j, …, am–1,j)，0≤j≤n–1，也可以是如（c）所示的行向量形式线性表ai=(ai,0, ai,1,…, ai,n–1)，0≤i≤m–1。 数 组数 组同理，n维数组中每个数据元素都受n个关系的约束，都对应于一组下标(j1, j2, …, jn)，元素 （1≤ji≤bi–1，i = 1, 2, …, n）有一个直接后继元素。因此，就单个关系而言，仍是线性关系。类似于线性表，数组的抽象数据类型定义参见以下ADT。 数 组数 组数 组数 组C++的数组 尽管在C++中数组是一个 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 的数据结构，但C++数组的索引（也称为下标）必须采用[i1][i2][i3]…[ik]的形式，其中，ik为非负整数。如果k为1，则数组为一维数组；如果k为2，则数组为二维数组。i1是索引的第一个坐标，i2是第二个坐标，ik是第k个坐标。在C++中，值为整数类型的k维数组score可用int score[u1][u2][u3]…[uk]语句来创建，其中，ui是正的常量或由常量表示的正的表达式。对于这样一个数组描述，索引ij的取值范围为：0≤ ij＜uj，1≤j≤k。因此，该数组最多可容纳n = u1u2u3…uk个值。由于数组score中的每个值都是整数，所以需要占用sizeof(int)个字节，因此，整个数组所需要的内存空间为sizeof(score) =n×sizeof(int)个字节。C++编译器将为数组预留这么多空间。如果预留空间的起始地址为start，则该空间将延伸至start+size(score)–1。 数 组数 组数组的存储结构与寻址问题 数组是一种特殊的数据结构，一般 要求 对教师党员的评价套管和固井爆破片与爆破装置仓库管理基本要求三甲医院都需要复审吗 元素的存储地址能根据它的下标（即逻辑关系）计算出来，因此数组一般只采用顺序存储结构。讨论数组元素地址时，一般将第1个元素的起始存储单元作为参考单元，参考单元的绝对地址称为该数组的首地址，数组其他元素的相对地址均相对于首元素的起始地址。设i1, i2,…, in为某n维数组中的一个元素的下标，则用Loc( )表示此元素的相对地址。 对一维数组，与线性表类似，可使用顺序存储方式；但对多维数组，由于其已不属于线性结构的范畴，因此不能直接使用顺序存储方式。但多维数组有其特殊性，具有线性结构的痕迹，它可唯一地转换为一维结构，并可根据元素的存储位置推算出元素的逻辑关系（下标），所以可将多维数组映射为一维结构，然后使用顺序存储方式。 数 组数 组1. 一维数组 一维数组的每个元素只含一个下标，其实质上是一个线性表，存储方法与普通线性表的顺序存储方法完全相同，即将数组元素按它们的逻辑次序存储在一片连续区域内。设一维数组为A =(a0, a1,…, an–1)，则它的元素ai的相对地址为Loc(ai) = i×c。这里，c表示每个元素占用的存储单元数目。 2. 二维数组 二维数组的每个元素含有两个下标，不是一般的线性表。如果将二维数组的第1个下标理解为行号，第2个下标理解为列号，然后按行列次序排列各元素，则二维数组呈阵列形状。对于这种非线性结构的存储，需将多维关系映射为一维（线性）关系，即要确定多维到一维的映射。 数 组数 组以之前所示的二维数组为例，它有两种存储方式：以列序为主序的存储方式（a）和以行序为主序的存储方式就（b）。 数 组数 组（1）按行存储 按行存储的基本思想是先行后列，即先存储行号较小的元素，对于行号相同者，先存储列号较小者。设二维数组的行下标与列下标变化范围分别为闭区间[l1, h1]与[l2, h2]，按行存储，则它的任一元素ai, j的相对地址计算公式为Loc(ai, j) = ((h2–l2+1)(i–l1)+(j–l2))×c，这里c为每个元素所占单元数目，i∈[l1, h1]，j∈[l2, h2]且i与j为整数。 例5-1例5-1设某二维数组的两个下标的范围分别为[–1, 2]与[0, 1]，则它的元素按行存储的次序为（用ai, j表示元素，每个元素占两个单元）： 它的元素a1, 1的相对地址计算如下： Loc(a1, 1)=((10+1)( 1+1)+(10))×2=2。 数 组数 组（2）按列存储 按列存储的基本思想是先列后行，即先存储列号较小者，对于列号相同者，先存储行号较小者。设二维数组的行下标与列下标变化范围分别为闭区间[l1, h1]与[l2, h2]，按列存储，每个元素占c个存储单元，则它的任一元素ai, j的相对地址计算公式为Loc(ai, j)=((j–l2)(h1l1+1)+(il1))×c。对二维数组，还可有其他的二维向一维的映射方法，如按正对角线、反对角线等，这里不作讨论。 数 组数 组3. 多维数组 下面将二维数组推广到多维数组，对n维数组也采用两种存储映射方式，即二维数组的按行存储与按列存储的推广。按行存储和按列存储都是一种“左”下标优先的存储方法，即第1个（最左）下标的下标值较小的元素较先存储，对于第1个下标值相同者，按第2个下标优先存储，对任意的k＞1，对第1～(k–1)维相同者，先存储第k维中下标值较小者。 例5-2例5-2设某三维数组a的三个下标范围分别为[2, 4]，[0, 1]，[1, 3]，则它按行存储的次序为： a2,0,1 a2,0,2 a2,0,3 a2,1,1 a2,1,2 a2,1,3 a3,0,1 a3,0,2 a3,0,3 a3,1,1 a3,1,2 a3,1,3 a4,0,1 a4,0,2 a4,0,3 a4,1,1 a4,1,2 a4,1,3 设n维数组第k维的下标范围是[lk, hk]，记dk=hk–lk+1，jk=ik–lk，k=1, 2,…, n。显然，dk为第k维的体积（元素个数）。设每个元素占c个单元，则下标为i1, i2,…, in的元素的相对地址的计算公式为Loc( )=c×(i1d2d3…dn+i2d3…dn+…+ in–1dn+in)。例如，三维数组的寻址公式为Loc( )=c×(i1d2d3+i2d3+i3)。n维数组寻址公式可应用数学归纳法证得。 数 组数 组4．寻址公式的计算 下面考虑如何根据一组给定下标求出对应数组元素地址的问题，这是数组最重要的基本操作，一般用在高级语言的实现当中。这里只考虑n维数组按行存储的寻址公式的计算。用秦九韶法变换按行存储公式中的主要部分： j1d2d3…dn + j2d3…dn +…+jn–1dn + jn =(j1d2+ j2)d3…dn + j3d4…dn +…+jn–1dn + jn =((j1d2+ j2)d3+ j3)d4…dn + j4d5…dn +…+jn–1dn + jn =… =(…(j1d2+ j2)d3+ j3)d4+j4)d5+…+jn–1)dn+ jn =(…((0×d1+j1)d2+ j2)d3+ j3) d4+j4)d5+…+jn–1)dn+ jn 数 组数 组此式的值乘以元素占用的单元数c即为元素（i1i2…in）的相对地址（jk=ik–lk）。此式可按下法计算： s=0;k=1; while(k<=n) {s=s*dk+jk; k=k+1;} 下面将该计算过程写成一个C函数，用3个一维数组l[ ]、h[ ]、i[ ]分别表示n个下标的下界、上界及待求地址的元素的n个下标值，见以下程序。 矩阵的压缩存储矩阵的压缩存储矩阵是很多科学与工程计算问题研究的数学对象。在高级语言程序设计中，常用二维数组来存储矩阵元素，有些程序语言还提供了各种方便用户使用的矩阵运算。然而，对于在数值分析中经常出现的一些阶数很高，且矩阵中有许多值相同的元素或者是零元素的特殊矩阵，不适合用二维数组来存放，因为这将造成大量存储空间的浪费。为了节省存储空间，可对这类矩阵进行压缩存储，即为多个值相同的元素只分配一个存储空间，对零元素不分配空间。 矩阵的压缩存储矩阵的压缩存储特殊矩阵 所谓特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵。常见的有对称矩阵、三角矩阵和对角矩阵等。 1. 对称矩阵 （1）定义 若n阶矩阵A中的元素满足下述性质ai, j=aj, i，1≤i，j≤n，则称A为n阶对称矩阵。下图所示为一个4阶对称矩阵。 矩阵的压缩存储矩阵的压缩存储（2）对称矩阵的压缩存储 对称矩阵中的元素关于主对角线对称，故只要存储矩阵上三角或下三角中的元素，让每两个对称的元素共享一个存储空间，这样就能节约近一半的存储空间。 ① 按“行优先顺序”存储主对角线（包括对角线）以下的元素（见下图）。 即按a0,0, a1,0, a1,1,…, an–1, 0, an–1, 1…, an–1, n–1次序存放在一个向量sa[0 .. n(n+1)/2–1]中（在下三角矩阵中，元素总数为n(n+1)/2），其中，sa[0]= a0,0, sa[1] = a1,0,…, sa[n(n+1)/2–1]= an–1, n–1。 矩阵的压缩存储矩阵的压缩存储② 元素ai, j的存放位置 ai, j元素前有i行（从第0行到第i–1行），一共有1+2+…+i = i×(i+1)/2个元素；在第i行上，ai, j之前有j个元素（即ai, 0, ai, l,…, ai, j–1），因此有sa[i×(i+1)/2+j] = ai, j。 ③ ai, j和sa[k]之间的对应关系 若i≥j，则k= i×(i+1)/2+j，0≤k＜n(n+1)/2；若i＜j，则k=j×(j+1)/2+i，0≤k＜n(n+1)/2；令I = max(i, j)，J = min(i, j)，则k和i，j的对应关系可统一为k = I ×(I+1)/2 + J， 0≤k＜n(n+1)/2。 矩阵的压缩存储矩阵的压缩存储（3）对称矩阵的地址计算公式 Loc(ai, j) = Loc(sa[k]) = Loc(sa[0])+k×d = Loc(sa[0])+ [I ×(I+1)/2 + J]×d 式中，d为每个元素所占的内存单元个数。通过下标变换公式，能立即找到矩阵元素ai, j在其压缩存储表示sa中的对应位置k，因此是随机存取结构。 矩阵的压缩存储矩阵的压缩存储2．三角矩阵 （1）三角矩阵的划分 以主对角线划分，三角矩阵有上三角矩阵和下三角矩阵两种。 ① 上三角矩阵：矩阵的下三角（不包括主角线）中的元素均为常数c。 ② 下三角矩阵：与上三角矩阵相反，矩阵的主对角线上方均为常数c。 注意：在多数情况下，三角矩阵的常数c为零。矩阵的压缩存储矩阵的压缩存储（2）三角矩阵的压缩存储 三角矩阵中的重复元素c可共享一个存储空间，其余的元素正好有n×(n+1)/2个，因此，三角矩阵可压缩存储到向量sa[0．．n(n+1)/2]中，其中，c存放在向量的最后一个分量中。 ① 上三角矩阵中ai, j和sa[k]之间的对应关系 在上三角矩阵中，主对角线之上的第p行（0≤p＜n）恰有n–p个元素，按行优先顺序存放上三角矩阵中的元素ai, j时，ai, j元素前有i行（从第0行到第i–1行），一共有(n–0)+(n–1)+(n–2)+ …+(n–i) = i×(2n–i+1)/2个元素；在第i行上，ai, j之前有j–i个元素（即ai, j, ai, j+l, …, ai, j–1），因此有sa[i×(2n–i+1)/2+j–i] = ai, j。所以：矩阵的压缩存储矩阵的压缩存储 ② 下三角矩阵中ai, j和sa[k]之间的对应关系 注意：三角矩阵的压缩存储结构是随机存取结构。 矩阵的压缩存储矩阵的压缩存储（3）对角矩阵 在这种矩阵中，所有的非零元素都集中在以主对角线为中心的带状区域中。即除了主对角线上和直接在对角线上、下方若干条对角线上的元素之外，其他的元素均为零，如下图所示。对这种矩阵也可按某种原则（或以行为主，或以对角线的顺序为主）将其压缩存储到一维数组上。 矩阵的压缩存储矩阵的压缩存储稀疏矩阵 1. 定义 对于稀疏矩阵，最常见的定义有以下两种： 定义1 假设矩阵Amn中有s个非零元素，若s远远小于矩阵元素的个数（s<< m×n），并且非零元素的分布没有规律，则称A为稀疏矩阵。 定义2 假设在m×n的矩阵中，有t个元素不为零。令 = t /(m×n)，称 为矩阵的稀疏因子。通常认为，≤0.05时为稀疏矩阵。 矩阵的压缩存储矩阵的压缩存储由于用数组存储稀疏矩阵中的元素时，仅有少部分空间存储了实际的数据元素，因此，为节省存储空间，通常采用一种压缩的存储方法来表示稀疏矩阵的内容。由于稀疏矩阵中非零元素分布没有一定规律，必须同时记下它所在行和列的位置(i, j)，因此可用一个三元组(i, j, ai, j)来唯一确定矩阵A的一个非零元素，即稀疏矩阵可由表示非零元素的三元组及其行、列数唯一确定。例如，下列三元组表((1, 2, 9)，(2, 1, 5)，(3, 4, 7)，(4, 1, 4))加上(4, 4)这一对行、列数便可作为下图所示矩阵A的另一种描述。 矩阵的压缩存储矩阵的压缩存储2. 三元组顺序表 假设非零元素的三元组以按行优先的原则顺序排列，一个稀疏矩阵可转换成一个对应的线性顺序来表示，其中每个元素由一个上述的三元组构成，这个线性表就称为三元组表，它是一种具体的线性表顺序存储结构，因此可看成是线性表顺序存储结构（LinearListSqu）的派生类，只是元素类型T要具体定义。 十 字 链 表十 字 链 表存储方式 三元组表采用顺序方法来存储稀疏矩阵中的非零元素，它不适合于非零元素个数和位置在操作过程中变化较大的矩阵。例如，在两个矩阵进行相加操作时，会改变非零元素的个数，这样将导致大量结点的移动。此时，采用链式存储结构来表示三元组的线性表更为合适。  十 字 链 表十 字 链 表一般采用十字链表的链接存储方式，即稀疏矩阵中的每个非零元素用一个包含5个域的结点表示，结点结构如上图所示，其中除了表示非零元素所在的行、列和值的三个域以外，还有两个分别指向同一行中下一个非零元素的right域和同一列中下一个非零元素的down域。因此，同一行的非零元素通过right域链接成一个线性链表，同一列的非零元素通过down域链接成一个线性链表。每个非零元素既是某个行链表中的一个结点，又是某个列链表中的一个结点，整个矩阵构成了一个十字交叉的链表，故称这样的存储结构为十字链表。这里以稀疏矩阵为背景介绍十字链表，不过十字链表的应用远不止稀疏矩阵，一切具有正交关系的结构，都可用十字链表存储。 例5-4例5-4设有一如下形式的矩阵： 它所对应的十字链表如如下图所示。 例5-4例5-4矩阵第1行有一个非0元素5，在十字链表中表示为结点(0, 2, 5)；总头结点中的4和5表示矩阵共有4行5列；行头结点用虚线画出，表示每行头结点与每列头结点为同一结点，如第1行/列头结点中的1和2表示：第1行有1个非0元素，第1列有2个非0元素。 广 义 表广 义 表广义表的定义 广义表（List，又称列表）是线性表的推广，它放松了对表元素的原子限制，允许表元素具有其自身结构。广义表是n (n≥0)个元素a1, a2, …, ai, …, an的有限序列，ai或者是一个原子，或者是一个广义表。广义表通常记作LS = (a1, a2,…, ai,…, an)，其中，LS是广义表的名字，n为它的长度，如果ai也是广义表，则称它为LS的子表。广义表通常用圆括号括起来，用逗号分隔其中的元素；为了区分原子和广义表，书写时用大写字母表示广义表，用小写字母表示原子；若广义表LS非空 (n≥1)，则a1是LS的表头，其余元素组成的表(a2,…, an)称为LS的表尾；广义表是递归定义的。 null 由表头、表尾的定义易知：任何一个非空列表 其表头可能是原子，也可能是列表，而其表尾必定 是列表。 例5-6例5-6① L1 = ( )表示：L1是一个空表，它的长度为0，深度为1。 ② L2 = ()表示：列表B只有一个原子，L2的长度为1，深度也为1。 ③ L3 = (, (, , ))表示：列表L3的长度为2，深度为2，两个元素分别为原子和子表(, , )。 ④ LS = (L1, L2, L3)表示：列表LS的长度为3，深度为1，3个元素都是列表。将子表的值带入后，则有LS =(( ), (), (, (, , )))。 ⑤ L4 = (, L4)表示：这是一个递归的表，它的长度为2，深度为∞。L4相当于一个无限的列表L4 = (, (, (,…)))。 广 义 表广 义 表广义表有如下重要结论：  ① 列表的元素可以是子表，而子表的元素还可以是子表，故列表是一个多层次的结构。如图所示的列表LS，图中圆圈表示列表，方块表示原子。 ② 列表可为其他列表所共享。 ③ 列表可以是一个递归的表，即列表也可以是其本身的一个子表。 广 义 表广 义 表 广义表的存储结构 1. 头尾链表存储表示 （1）结点结构 其中tag是标志域，tag=1表示表结点，tag=0表示原子结点；hp指示表头的指针域；tp指示表尾的指针域；data是值域。 广 义 表广 义 表（2）特点 ① 除空表的表头指针为空外，对任何非空表，其表头指针均指向一个表结点； ② 容易分清列表中原子和子表所在层次； ③ 最高层的表结点个数即为列表的长度。 （4）图形表示 举例如下。 例5-7例5-7LS =(L1, L2, L3)，其中L1 =( )，L2 =()，L3=(, (, , ))，如图所示。例5-8例5-8 L4 =(, L4)，如图所示。广 义 表广 义 表2. 扩展性链表存储表示 （1）结点结构 其中，tag是标志域，tag=1表示表结点，tag=0表示原子结点；hp指示表头的指针域；tp指示下一个元素结点；data是值域。 广 义 表广 义 表图形表示 前面两个例子中的广义表的存储结构可表示为如下列图所示的结构。 本 章 总 结本 章 总 结学习要点 本章主要介绍二维（多维）数组的逻辑结构形式化定义和顺序存储方式，特殊矩阵和稀疏矩阵的压缩存储方式，广义表的逻辑结构、存储结构以及运算和递归算法。主要学习要点如下：① 二维（多维）数组的定义和顺序存储结构的实现方法及元素存储位置计算公式，特殊矩阵及稀疏矩阵压缩存储的基本思想和压缩存储的实现方法；② 在压缩存储下标变换方法以及进行矩阵转置、相加、相乘运算所采用的处理方法（算法）；③ 广义表的表头、表尾分析方法及存储结构的实现。 本 章 总 结本 章 总 结基本要求 （1）深刻理解二维（多维）数组的逻辑结构定义和顺序存储及压缩存储的基本思想； （2）清楚二维（多维）数组的逻辑结构定义、读和写两种基本运算； （3）知道读、写两种运算的实现手段是下标变量和赋值； （4）掌握二维（多维）数组采用顺序存储结构表示时，元素位置的计算公式； （5）掌握特殊矩阵及稀疏矩阵压缩存储的实现方法以及转置、乘法运算的基本算法； （6）掌握特殊矩阵压缩存储的基本思想和对称矩阵及三角矩阵压缩存储的下标与元素存储位置的对应关系； 本 章 总 结本 章 总 结（7）清楚稀疏矩阵的定义、三元组表和十字链表的表示方法，以及在这两种表示方法下的转置、相加、相乘运算的基本思想和算法； （8）领悟广义表的定义、存储结构、递归程序设计的基本思想。 重点与难点 重点是：数组的逻辑定义、压缩存储方法、广义表的存储结构及串的连接。求子串、定位、置换基本运算（操作）的实现算法。难点是：特殊矩阵在压缩存储下元素位置的求址公式、稀疏矩阵的转置、乘法算法、广义表的链式存储结构。