1. 数组

1.1 一维数组

1.2 二维数组

二维数组的存储结构

二维数组可以采用以下两种方式存储：

  • 以行为主序（行优先）
  • 以列为主序（列优先）

以行为主序优先存储的地址计算公式：

LOC(a[i][j]) = LOC(a[0][0]) + (i × n + j) × L

以列为主序优先存储的地址计算公式：

LOC(a[i][j]) = LOC(a[0][0]) + (j × m + i) × L

其中：

  • m 为数组行数
  • n 为数组列数
  • L 为每个元素占用的存储单元数

2. 矩阵

2.1 对称矩阵

对于 n 阶对称矩阵 A，满足 a[i][j] = a[j][i]，可以只存储下三角（或上三角）部分的元素，从而节省存储空间。

存储元素个数为：n(n+1)/2

2.2 三对角矩阵

三对角矩阵是指非零元素只出现在主对角线及其上下两条对角线上的矩阵。

对于 n 阶三对角矩阵，非零元素个数为：3n - 2

2.3 稀疏矩阵

稀疏矩阵是指矩阵中绝大多数元素为零，只有少数非零元素的矩阵。

稀疏矩阵的存储通常采用三元组表或十字链表的方式，只存储非零元素的信息。

三元组表：每个非零元素用一个三元组 (i, j, a[i][j]) 表示，其中 i 为行号，j 为列号，a[i][j] 为元素值。

3. 广义表

3.1 广义表的定义

广义表是线性表的推广，是由零个或多个单元素或子表所组成的有限序列。

3.2 广义表的基本概念

广义表通常记作：

LS = (a₁, a₂, …, aₙ)

其中：

  • LS 是广义表的名称
  • n 是广义表的长度
  • aᵢ 可以是单个元素（原子），也可以是广义表（子表）

3.3 广义表的性质

  • 广义表可以是多层次的结构
  • 广义表可以被其他广义表共享
  • 广义表可以是递归的表

3.4 广义表的基本操作

  • 取表头（Head）：取广义表的第一个元素
  • 取表尾（Tail）：取广义表除第一个元素外其余元素组成的子表