本次课程内容

第四章 数组、广义表和串

第一节 数组及广义表

数组的基本操作

数组是高级程序设计语言中的重要语法成分，很多语言都定义了数组类型。例如，在C语言中，定义了一维数组。数组元素还可以是数组，由此得到数组的数组，

即多维数组。

一般将n(n>2)维数组看作n-1维数组的数组。

从数据结构的角度来理解，一维数组可以作为线性表的存储结构，数组中保存的各元素可以组成一个线性表。多维数组在系统内部都对应一个隐含的一维数组，所

以多维数组也是一种线性表。例如，二维数组就是以一维数组为元素的线性表。

数组的每个元素都是形如(index，value)的二元对，index是数组下标，也称为索引，value是对应于该下标的数值。任何两个元素的index值都不相同。

从数组的操作可知，它没有一般线性表常用的插入和删除操作，更多的是根据下标index访问元素。

数组的顺序存储方式-借用矩阵行列式概念

一维数组天然地采用顺序存储方式，

多维数组的顺序存储又是什么样的呢?

数组的顺序存储有两种形式。以二维数组为例，它的元素可以按行排列，也可以按列排列。

这里的“行”和“列”借用数学上矩阵或行列式中的概念。

所谓按行排列，就是先排数组的第一行，紧随其后排第二行，依此类推。

所谓按列排列，就是先排数组的第一列，紧随其后排第二列，依此类推。

最终都是将数组中的全部元素排列成一个序列。

在C语言中，可以定义多维数组，它的下标采取如下的形式表示:

二维数组C语言对应的函数-通常行主序方式

通常int类型占4字节，数组D2Array中含有18个元素，共占用18x4=72字节。如果保存的起始地址是1000，则数组将占用从1000到1071的内存空间。注意，这里

提到的字节编号并不是内存中真实的编号。将图4-1所示的下标表格按行自上而下、同一行中自左至右的次序进行连续编号，从0开始，

即可得到图4-2a所示的编号结果，

这种按行优先把二维数组中的下标映射到0~n-1之间的某个整数的方式称为按行优先方式，也称为行主序方式。

包括C语言在内的大多数程序设计语言均采用行主序的实现模式。

也有一些程序设计语言采用另一种实现模式，称为按列优先方式，也称为列主序方式。

在列主序方式中，按列优先，对于下标表格，从第一列开始，从上到下进行连续编号，直到最后一列。这个结果如图4-2b所示。

矩阵的压缩存储

数学中的矩阵可以使用二维数组保存。对于n行m列的矩阵，数组元素至少需要分配n x m个。

有些矩阵因其特殊性，可以不必保存其中的所有元素，因而可以减少为数组分配的空间。

对称矩阵和三角矩阵

如果不考虑矩阵的特殊性，按照一般二维数组的顺序存储方式来存储特殊矩阵，也是完全可行的。

但是，从节省存储空间的角度考虑，对称矩阵和上(下)三角矩阵都可以只保存矩阵中约一半的元素，从而可以节省差不多一半的存储空间。

这样的存储形式称为压缩存储。

• 具体来说，对干对称矩阵，因为对角线以上及以下的元素对称相等，所以只需要保存其中的一半及对角线上的元素。

• 对于上三角矩阵或下三角矩阵，仅保存上三角部分或下三角部分的元素，另外一半的0元素不再保存。

若矩阵有n行n列，则这三种形式下需要保存的元素个数为nx(n+1)/2。

在采用压缩存储以后，需要寻找与普通二维数组不同的映射函数。

压缩存储后，采用不同的映射函数

稀疏矩阵-可以构成三元组线性表

在实际的应用中，矩阵中可能会出现大量的0元素，而非0元素数量很少，这就是所谓的稀疏矩阵。至于非0元素少到什么程度才能称为稀疏矩阵，并没有很严格的定义。通常认为，矩阵中非0元素的个数与矩阵的阶数相当，即可将其看作稀疏矩阵。

• 如何理解？

为了节省空间，一般只存储稀疏矩阵中的非0元素。但在稀疏矩阵中，非0元素的出现是没有规律的，

所以在存储非0元素时必须将它所在的行号和列号一起存储起来。这些信息组成一个三元组(i，j，v)的形式

其中v表示非0元素的值，i表示v所在的行号，i表示v所在的列号。

一个稀疏矩阵的所有元素用一个三元组表来表示，也就是可以构成一个三元组的线性表。

为了方便后续其他操作的实现，三元组表应该是一个有序序列，通常按行主序的次序排列，即先按行的大小排列，同一行的三元组再按列的大小排列。

三元组表的初始值从键盘输入，输入时，各三元组可以按行主序排列，也可以按任意的次序排列，但最终都应该按行主序的次序插入到一维数组的合适位置。

当然，在有特殊需求的应用中，也可以按列主序方式保存。

三元组在C语言中的实现

三元组表的转置

转置是矩阵中常用的一种操作。下面实现采用三元组表表示的稀疏矩阵的转置算法。矩阵转置即行、列互换，i行的元素放置到i列，这也意味着，j列的元素放置在j行。如果矩阵是nxm则转置后得到的矩阵是mxn的。
很容易想到，将三元组表中的每个三元组项的i与i互换，即可得到转置后矩阵的三元组表。但是，这样转换后得到的三元组表不再按行主序排列，不便于后续操作的实现。所以，要实现矩阵转置程序，必须先得到一个按行主序排列的三元组表。

可以像readSparseMatrix函数那样处理，读入原矩阵的一个三元组，插入到目标矩阵的三元组表中。在插入过程中，需要调整部分三元组在三元组表中的次序，也就是需要进行元素的移动。从顺序表实现的时间复杂度分析中知道，这样的移动会导致转置操作的效率很低。
可以使用一个临时计数数组，记录原矩阵的每个三元组在目标矩阵的三元组表中的插入位置，以辅助完成转置操作，由此避免了三元组的移动，可高效率地实现转置操作。
不失一般性，设原矩阵A的行数是rows，列数是cols，则转置后矩阵B的行数是cols，列数是rows。元组的个数没有改变。

三元组转置的算法实现

数组的应用-解决迷宫问题

多维数组，特别是二维数组，在计算机科学中有广泛的应用。

下面以一个有趣的“迷宫”问题为例,介绍数组的应用。

“老鼠走迷宫”是实验心理学中的一个经典问题，也是一种智力游戏。

在计算机模拟实现中，可以用-个较大的二维数组表示迷宫，其中元素0表示走得通，元素1表示走不通(受阻)，行走路径只考虑水平和垂直方向上的4个方向(上、下、左、右)。图4-9是一个迷宫示意图。

• 适合解决复杂迷宫问题，简单的用算法不至于

广义表

广义表是线性表的推广，也称为列表。

它是由n(n≥0)个表元素组成的有限序列，记为:

广义表示例

广义表操作示例