考研笔记-计算机之数据结构:线性结构-表(数组|广义表)

——如阅读体验不佳，可转为横屏阅读；如微信无法横屏，可尝试文末方法。

数组和广义表

数组和广义表可以看成是线性表在下述含义上的扩展：表中的数据元素本身也是一个数据结构。

数组

• 数组的定义

数组：n维数组中含有个数据类型相同的数据元素；每个元素受n个关系的约束（即在每一维上都受该维上的一个关系的约束），在每个关系中，元素（）都有一个直接后继元素（因此，就单个关系而言，这n个关系中的每一个都是线性关系）；每个数据元素都对应于一组下标，每个下标的取值范围是，称为数组第i维的长度（）。显然，当n=1时，n维数组就退化为定长的线性表；反之，n维数组可以看成线性表的推广。由此，可以从另一角度定义n维数组，即将n维数组看成其数据元素为n-1维数组的一维数组，即“typedef ElemType Arrayn[][]…[]”等价于“typedef ElemType Array1[]；typedef Array1 Array2[]；……；typedef Arrayn-1 Arrayn[]；”）。

抽象数据类型数组：

1）数据对象D：D为具有相同特性的数据元素的集合，D={|n(>0)称为数组的维数；称为数组第i维的长度，；是数组元素的第i维下标，；}。

2）数据关系R：，R_i={|，，且；；；}，R_i表示第i维上相邻两元素之间的关系。

3）基本操作P：创建、销毁、查询和修改（数组一旦被定义，它的维数和维界就不再改变。因此，除了初始化和销毁外，数组只有查询和修改元素的操作）。

• 数组的表示

n维数组采用顺序存储作为其存储结构。

• 数组的实现

n维数组的顺序存储可以有两种方式：以第1维为主序（即第1维作为最外层顺序，第n维作为最内层顺序，如C，C++，C#，Java），或以第n维为主序（即第n维作为最外层顺序，第1维作为最内层顺序，如FORTRAN，Matlab）。

• n维数组中数据元素存储位置的计算公式

假设n维数组的顺序存储以第1维为主序，每个数组元素占L个存储单元，则下标为的数据元素的存储单元的地址为：（其中，，，），该式称为n维数组的映像函数。可以看出，数组元素的存储位置是其下标的线性函数，一旦确定了数组的各维的长度，就是常数（实际是第i维对应的一维数组的数据元素的类型大小（即类型所占的存储单元的个数），可以看作是数组索引中第i维的“权重”）。由于计算各个元素存储位置的时间相等，所以存取数组中任一元素的时间也相等，称具有这一特点的存储结构为随机存储结构。

• 矩阵的压缩存储

矩阵的压缩存储：①对值相同的元只分配一个存储空间；②对零元不分配空间。

矩阵的压缩存储分为两类：①特殊矩阵的压缩存储；和②稀疏矩阵的压缩存储。

• 特殊矩阵的压缩存储

特殊矩阵：若值相同的元素或零元素在矩阵中的分布有一定规律，则称此类矩阵为特殊矩阵。（特殊矩阵一般为方阵）特殊矩阵包括对称矩阵、三角矩阵和对角矩阵。

• 对称矩阵的压缩存储

对称矩阵：矩阵中的元满足（）的n阶方阵称为对称矩阵。（值相同的元在矩阵中的分布有一定规律）

压缩存储方法：为每一对对称元分配一个存储空间，则可将个元压缩存储到，即个元的空间中。不失一般性，以行序为主序存储其下三角（包括对角线）中的元素。以一维数组A[n(n+1)/2]作为n阶对称矩阵的存储结构，则数组元素A[k]和矩阵元之间存在一一对应的关系：

（其中(i,j)为矩阵中元的下标，；k为一位数组中元素的下标，）（公式说明：当时，表达式中，子表达式为矩阵的下三角（包括对角线）的前i-1行所含的矩阵元的个数，即等差数列1,2,…,i-1的和；子表达式j为矩阵的下三角（包括对角线）的第i行中其位置不超过的矩阵元的个数；子表达式-1表示将矩阵元的个数转为以0开始的一维数组的下标。当i<j时，因，所以此时矩阵元对应的一维数组的索引即为矩阵元对应的一维数组的索引，即）

• 三角矩阵的压缩存储

上（下）三角矩阵：矩阵的下（上）三角（不包括对角线）中的元均为非零常数c或零的n阶方阵称为上（下）三角矩阵（与线性代数中的定义不同）。（值相同的元或零元在矩阵中的分布有一定规律）

压缩存储方法：对于上（下）三角矩阵，使用对称矩阵的压缩存储方法存储其上（下）三角中的元，同时加一存储空间存放非零常数c（矩阵中的零元在压缩存储时不需分配空间）。

• 对角矩阵的压缩存储

对角矩阵：所有的非零元都集中在以主对角线为中心的带状区域（带状区域中可含零元）中的n阶方阵（即除了主对角线和直接在对角线上、下方若干条对角线上的元之外，所有其他的元皆为零元）称为对角矩阵。（零元在矩阵中的分布有一定规律）

压缩存储方法：可按某个原则（或以行为主，或以对角线的顺序）将其压缩到一维数组上。

• 稀疏矩阵的压缩存储

• 稀疏矩阵的定义

稀疏矩阵：非零元较零元少，且分布没有规律的矩阵称为稀疏矩阵。

稀疏因子：若在m×n的矩阵中，由t个元素不为零，则称为矩阵的稀疏因子。通常称的矩阵为稀疏矩阵（该条件只是稀疏矩阵的必要条件，若矩阵中元的分布有一定规律，则即使满足，也不是稀疏矩阵，而是特殊矩阵）。

抽象数据类型稀疏矩阵：

1）数据对象D：D为具有相同特性的数据元素的集合，D={|，；；m和n分别称为矩阵的行数和列数}。

2）数据关系R：，Row={|，}，Col={|，}。

3）基本操作P：创建、销毁及矩阵相关的运算。

• 稀疏矩阵的表示

稀疏矩阵可由表示非零元的三元组(r,c,e)的线性表及矩阵的行列数(row,col)唯一确定，其中，r表示非零元的行号，c表示非零元的列号，e表示非零元的值，row表示稀疏矩阵的行数，col表示稀疏矩阵的列数。三元组表的不同表示方法可引出稀疏矩阵不同的压缩方法。

• 稀疏矩阵的实现

三元顺序表

实现方法：以顺序存储结构表示三元组表，以实现稀疏矩阵的压缩存储。

适用条件：非零元的个数和位置变化不大的稀疏矩阵。

行逻辑链接的顺序表

实现方法：为便于随机存取任意一行的非零元，需知道每一行的第一个非零元在三元组表中的位置，为此可在三元顺序表中添加指示“行”信息的辅助数组，称这种“带行链接信息”的三元组表为行逻辑链接的顺序表。

适用条件：非零元的个数和位置变化不大的稀疏矩阵。

十字链表

实现方法：以链式存储结构表示三元组表，以实现稀疏矩阵的压缩存储。

链表中的结点如下，

其中，r表示非零元的行号，c表示非零元的列号，e表示非零元的值，向右域right用以链接同一行中的下一非零元，向下域down用以链接同一列中的下一非零元。

同一行的非零元通过right域链接成一个线性链表，同一列的非零元通过down域链接成一个线性链表，每个非零元既是某个行链表中的一个结点，又是某个列链表中的一个结点，整个矩阵构成了一个十字交叉的链表，故称这样的存储结构为十字链表，可用两个分别存储行链表的头指针和列链表的头指针的一维数组表示之。

适用条件：非零元的个数和位置变化较大的稀疏矩阵。

广义表

• 广义表的定义

广义表：广义表一般记作，其中，LS是广义表的名称，n是它的长度。可以是单个元素，也可以是广义表（递归定义），分别称为广义表LS的原子和子表。习惯上，用大写字母表示广义表，小写字母表示原子。当广义表LS非空时，称第一个元素为LS的表头，称其余元素组成的表为LS的表尾。

抽象数据类型广义表：

1）数据对象D：D为数据元素的集合，D={|；；或，AtomSet为某个数据对象}。

2）数据关系R：R={|，}。

3）基本操作P：关键操作遍历广义表。

• 广义表的性质

(1)非空列表的表头可以是原子或列表，但表尾只能是列表，且表头不能同时是表尾，当广义表中只有一个元素时，表头为该元素，表尾为空表；（例如，若表LS=，则表头为，表尾为，但两个空表的来源不同，表头即为表LS中的元素，而表尾则是表LS中除去元素后其余元素形成的空表）

(2)列表的元素可以是子表，而子表的元素还可以是子表……由此，列表是一个多层次结构，可以用图形象地表示；

(3)列表可以为其他列表所共享，即在列表的表示中可以不必列出子表的值，而是通过子表的名称来引用；（例如，，）

(4)列表可以是一个递归的表，即列表也可以是其本身的一个子表；（例如，）

• 广义表的表示

由于广义表中的数据元素可以具有不同的结构（或是原子，或是列表），因此难以用顺序存储结构表示，通常采用链式存储结构，每个数据元素可以用一个结点表示。

• 广义表的实现

由于广义表中的数据元素可能为原子或列表，因此需要两种结构的结点：①表结点，用以表示列表；和②原子结点，用以表示原子。若列表非空，则可以分解为表头和表尾；反之，一对确定的表头和表尾可唯一确定列表。由此，一个表结点由三个域组成：标志域、指示表头的表头指针域和指示表尾的表尾指针域；一个原子结点只需两个域：标志域和值域。可用联合体来实现表结点和原子结点

原子结点：

表结点：

广义表的上述链式存储结构的说明：

①空表的表头指针为空，对任何非空列表，其表头指针均指向一个表结点，且该表结点的表头指针指示列表表头（或为原子结点，或为表结点），表结点的表尾指针指示列表表尾（若表尾为空，则Tail为空；否则，必为表结点）；

②容易分清表中原子和子表所在层次，由表尾指针链接而成的链表上的各结点（原子结点或表结点）的层次相同，由表头指针链接而成的链表上的各结点（原子结点或表结点）的层次依次递减（广义表元素为嵌套结构）；

③最高层的表结点的个数即为列表的长度。