4.1 数组的逻辑结构和基本运算

数组可看成是一种特殊的线性表，其特殊在于，表中的数组元素本身也是一种线性表。

在早期的高级语言中，数组是唯一可供使用的数据类型。由于数组中各元素具有统一的类型，并且数组元素的下标一般具有固定的上界和下界，因此，数组的处理比其他复杂的结构更为简单。

多维数组是线性表的推广；例如二维数组：

二维数组Amn可以看成是由m个行向量组成的向量（行优先），也可以看成是n个列向量组成的向量（列优先）。 数组一旦被定义，它的维数和维界就不再改变。因此，除了结构的初始化和销毁之外，数组通常只有俩种基本运算：

①读–给定一组下标，读取相应的数据元素； ②写–给定一组下标，修改相应的数据元素；

4.2 数组的存储结构

4.2.1 基本概念

顺序存储结构

由于计算机的内存结构是一维的。因此用一维内存来表示多维数组，就必须按某种次序将数组元素排成一列序列，然后将这个线性序列存放在存储器中。

又由于对数组一般不做插入和删除操作，也就是说，数组一旦建立，结构中的元素个数和元素间的关系就不再发生变化。因此，一般都是采用顺序存储的方法来表示数组。

寻址公式（行优先）

例如，二维数组Amn按『行优先顺序』存储在内存中，假设每个元素占用k个存储单元。 元素aij的存储地址应是数组的基地址加上排在aij前面的元素所占用的单元数。因为Aij位于第i+1行、第j+1列，前面i行一共有i * n个元素，第i+1行上Aij前面又有j个元素，故它前面一共有i * n + j个元素，因此，aij的地址计算函数为：LOC(Aij) = LOC(A00) + (i * n + j) * k

4.2.2 矩阵的压缩存储

为了 节省存储空间 ，我们可以对这类矩阵进行压缩存储：即为多个相同的非零元素只分配一个存储空间；对零元素不分配空间。

矩阵：二维的数据结构，它由行和列组成，可以有不同的行数和列数。当矩阵的行数等于列数时，它被称为正方形矩阵。正方形矩阵（也叫方阵）是一种特殊情况，其中每行和每列的元素数量相同。

并非所有的矩阵都可以压缩；一些特殊的矩阵具有特别的规律才可以进行压缩。

4.2.3 特殊矩阵

为了 节省存储空间 ，我们可以对这类矩阵进行压缩存储：即为多个相同的非零元素只分配一个存储空间；对零元素不分配空间。

特殊矩阵： 即指非零元素或零元素的分布有一定规律的矩阵。下面我们讨论几种特殊矩阵的压缩存储。

对称矩阵（方阵）

定义：在一个n阶方阵A中，若元素满足下述性质：Aij == Aji

下图就是一个5阶方阵：

下图就是一个5阶对称方阵：

对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三角或下三角中的元素（包括对角线），让每俩个对称的元素共享一个存储空间，这样，能节约近一半的存储空间。不失一般性，我们按『行优先顺序』存储主对角线（包括对角线）以下的元素，以上图的对称矩阵为例，其存储形式如图所示：

且可以明显看出，在第n行有n个元素需要存储；因此对称的n阶方阵的存储元素个数为：

要想将对称方阵有序存储到一维数组中就必须找到二维数组下标ij和以为数组下标k的对应关系。

下标变换公式（压缩）

一定要多画图练习！！！

下三角（行优先）

下三角（上优先）

三角矩阵

以主对角线划分，三角矩阵有上三角和下三角。

三角矩阵中的重复元素c可共享一个存储空间，其余的元素正好有 n(n + 1) / 2 = k 个，因此，三角矩阵可压缩存储到数组S[0,1,2,…,k-1,k]中，其中重复元素c存放在向量的最后一个元素k中。

稀疏矩阵（压缩存储）

稀疏矩阵：矩阵存储的一种特殊情况，其元素为0个数远大于非0元素个数。 稀疏矩阵的压缩存储： 即只存储稀疏矩阵中的非零元素。 目的：节省存储空间。

由于非零元的分布一般是没有规律的，因此在存储非零元素的同时，还必须同时记下它所在的行和列的位置(i, j)。反之，一个三元组（i, j, A[i][j]）唯一确定了矩阵A的一个非零元素。因此，稀疏矩阵可由表示非零元的三元组及其行列数唯一确定。

三元组顺序表稀疏矩阵的三元组顺序表表示法： 将矩阵中的非零元素化成三元组形式并按行的不减次序（同行按列的递增次序）存放在存储中。

三元组表结构： 假设以顺序存储结构来表示三元组表，则可得到稀疏矩阵的一种压缩存储方法–三元组顺序表。

const int maxnum = 100;
typedef struct node {
    int i, j; // 非零元素的行下标和列下标
    DataType v; // 非零元素的值
} NODE; // 三元组

typedef struct spmatrix {
    NODE data[maxnum]; // 非零元素三元组表
    int mu, nu, tu; // 矩阵的行数，列数和非零元素个数
} SpMtx; // 稀疏矩阵三元组表存储类型

4.4 广义表概念

广义表的元素可以是子表，子表又可以含有子表，广义表是一个多层次结构的表。

• 广义表：n个表元素组成的有限序列，GL = (d0, d1, …, dn-1) GL是表名，d为表元素
• 表头（head）:表中第一个元素，GetHead()取表头
• 表尾（tail）:表中最后一个元素，GetTail()取表尾
• 长度：最外层包含元素的个数
• 深度：最大所含括弧的重数

4.5 广义表的存储结构

• 特点：由于广义表是递归定义的一种带有层次的非线性结构，数据元素具有不同的结构，常常采用链式存储
• 表结点：包含表结点或者原子结点；标志域、表头指针域、表尾指针域组成
• 原子结点：不包含表结点或原子结点；标志域、值域组成

广义表链表存储结构：

扩展线性链表存储结构：

4.6 广义表的运算

• GetHead :取广义表的第一个元素，去除最外一层括号
• GetTail : 取广义表的最后一个元素，不去除最外一层括号
• 深度：最大的括号重数，上图D E F A深度分别为1 2 2 1
• 长度：表中元素个数，上图E和F和GL元素个数为2
• () 为空表，长度为0；(()) 长度为1，表尾为空表。

GetHead(GL) = A

GetTail(GL) = D

GetHead( D ) = E

GetTail( D ) = F

GetHead(E) = a

GetTail(E) = (b,c)

GetHead(F) = d

GetTail(F) = (e)

本人能力有限，文中内容难免有纰漏，真诚欢迎大家斧正~

喜欢本文的朋友请三连哦！！！

另外本文也参考了网络上其他优秀博主的观点和实例，这里虽不能一一列举但内心属实感谢无私分享知识的每一位原创作者。