1.数组
约 1082 字大约 4 分钟
2025-06-21
由于数组有很多语言都有，而广义表实现有太复杂，因此本章我只会解说一些结构性质和做题技巧，以后有机会再做补充。
1.数组
普通的一维数组肯定是没有什么值得讨论的意义的，但是这里的数组如果还可以存储别的线性表，那么这个数组就有讨论的空间了。
1.1.数组的概念
首先我们要明确，这里说的数组不是任何一门语言的具体数组，是更加抽象的抽象数组，其他语言的数组都是这个抽象数组的特殊化。
数组是由相同的数据元素构成的有序集合，每个元素被称为数组元素，数组可以看作是线性表的推广，线性表存储的是较为单一的数据元素，但是数组可以存储具有某种结构的数据集合。
1.2.数组的存储
1.2.1.顺序存储
假设有一个 m 行 n 列的抽象数组 Array[0...m−1,0...n−1] ，其中每一个数组元素需要的存储空间为 L，并且假设抽象数组的每一个元素是按照行来存储的。
若我们规定 LOC(0,0) 是抽象数组首元素的存储位置，那么抽象数组元素 (i,j) 的存储位置为 LOC(i,j)=LOC(0,0)+(n⋅i+j)L。
补充
1：假设有一个 m 行 n 列的抽象数组 Array[0...m−1,0...n−1] ，其中每一个数组元素需要的存储空间为 L，并且假设抽象数组的每一个元素是按照行来存储的。若我们规定 LOC(0,0) 是抽象数组首元素的存储位置，那么抽象数组元素 (i,j) 的存储位置为 LOC(i,j)=LOC(0,0)+(m⋅j+i)L。补充
2：C语言的数组是怎么具体实现抽象数组的要求呢？我们知道，在
C语言中，数组名可以当作指针来使用，取得数组int arr[m][n]（m和n为常量）第一个元素的地址就是(*(arr+0))+0、第二个元素的地址就是(*(arr+0))+1...、第(m*n)个元素就是(*(arr+m))+n。因此实际上就是上述式子 LOC(i,j)=LOC(0,0)+(n⋅i+j)L 变化为 LOC(i,j)=(LOC(0,0)+n⋅i⋅L)+j⋅L，
C本身会帮助我们处理元素大小的问题，用户只需要根据起始位置和 i,j 值即可。
1.2.2.压缩存储
1.2.2.1.对称矩阵
关于主对角线对称的对称矩阵，一般只存储下三角数据（包括主对角线）即可，一行一行存储到一维数组中，原矩阵数组和一维数组的一一对应关系如下：
k = \left \{ \begin{array}{**lr**} \frac{i(i - 1)}{2} + j - 1,(i \geq j)\\ \frac{j(j - 1)}{2} + i - 1,(i < j)\\ \end{array} \right.(i 和 j 从 1 开始)
1.2.2.2.三角矩阵
上/下三角矩阵的存储思想与对称矩阵类似，不同之在于：存储完上/下三角区（不会包含主对角线）和主对角线元素之后，紧接着存储对角线先/上方的常量一次（该常量可以非 0，也可以是 0）。
1.2.2.3.对角矩阵
对角矩阵的所有非零元都集中在以主对角线为中心的带状区域中，而除了带状区域，其他地方的元皆为零元。
2.广义表
广义表是线性表的推广，也被称为“列表”，一般记作 LS=(a1,a2,...,an)，其中每一个 ai 可以是单个元素（原子），也可以是一个表（子表）。可以注意到，这里使用了递归定义，在描述广义表的时候也使用广义表的概念。
由于广义表的结构比较复杂，因此最重要的两个操作时是 GetHead() 和 GetTail()。
GetHead()：取表头，即非空广义表的第一个元素，可以是一个原子，也可以是子表GetTail()：取除表头以外的所有元素构成的新表，即对于广义表来说，表尾一定是个广义表