软件设计师之数据结构深化：数组、矩阵与广义表的全面解析_对角矩阵软件设计师

技术文档

软件设计师之数据结构深化：数组、矩阵与广义表的全面解析

在软件设计的知识体系中，数据结构是极为关键的基础部分。数组、矩阵和广义表作为重要的数据结构，在各类程序设计中有着广泛的应用。我写这篇博客，旨在与大家共同学习进步，深入剖析这些数据结构的概念、特点、存储方式以及相关操作，以通俗易懂的语言结合图表和Java代码示例进行讲解，帮助大家更好地掌握。

数组

数组的定义与特点

数组是定长线性表在维数上的扩展，其元素类型相同且结构一致。以二维数组为例，它可以看作是行向量或列向量形式的线性表。例如二维数组 int[][] array = new int[3][4]; ，有3行4列，每个元素都是 int 类型。数组具有数据元素数目固定、元素类型相同、下标关系有上下界约束且有序的特点。

数组的基本运算

存取元素：通过给定的下标可以访问数组中的元素，如 int value = array[1][2]; 可获取 array 数组中第2行第3列的元素。
修改元素：同样通过下标来修改元素的值，如 array[1][2] = 10; 可将该位置的元素值改为10 。

数组的顺序存储

数组通常采用顺序存储结构，对于二维数组，有以行为主序和以列为主序两种存储方式。以行为主序优先存储时，地址计算公式为 Loc(a_ij) = Loc(a₁₁) + ((i - 1) × n + (j - 1)) × L ；以列为主序优先存储时，地址计算公式为 Loc(a_ij) = Loc(a₁₁) + ((j - 1) × m + (i - 1)) × L ，其中 L 为每个数据元素占用的单元数，m 、n 为数组的行数和列数。

存储方式地址计算公式特点示例（二维数组）以行为主序 Loc(a_ij) = Loc(a₁₁) + ((i - 1) × n + (j - 1)) × L 先存储完一行，再存储下一行对于 int[][] array = new int[3][4]; ，先存储 array[0][0] 到 array[0][3] ，再存储 array[1][0] 等以列为主序 Loc(a_ij) = Loc(a₁₁) + ((j - 1) × m + (i - 1)) × L 先存储完一列，再存储下一列先存储 array[0][0] 到 array[2][0] ，再存储 array[0][1] 等

矩阵

特殊矩阵

对称矩阵：若矩阵 (A_{n×n}) 满足 (a_{ij} = a_{ji}(1 ≤ i, j ≤ n)) ，则为对称矩阵。为节省空间，可将其下三角（包括对角线）元素压缩存储到一维数组中。例如，将 (n) 阶对称矩阵 (A) 的元素存储到一维数组 (B[n(n + 1) / 2]) 中，元素 (B[k]) 与矩阵元素 (a_{ij}) 的对应关系为：
[k= \\begin{cases}\\frac{i(i - 1)}{2} + j & 当 i \\geq j \\ \\frac{j(j - 1)}{2} + i & 当 i < j\\end{cases}]
对角矩阵：非0元素集中在主对角线及附近的带状区域，如三对角矩阵。以行为主序将 (n) 阶三对角矩阵 (A_{n×n}) 的非0元素 (a_{ij}) 存储在一维数组 (B[k](1 ≤ k ≤ 3×n - 2)) 中，对应关系为 k = 2i + j - 2 。

稀疏矩阵

若矩阵中非0元素个数远少于0元素个数且分布无规律，则为稀疏矩阵。通常用三元组 ((i, j, a_{ij})) 来确定矩阵中的元素，一个稀疏矩阵可由表示非0元素的三元组及其行、列数唯一确定。稀疏矩阵的存储结构有三元组顺序表（顺序存储）和十字链表（链式存储）。

矩阵类型特点存储方式元素与存储位置对应关系示例对称矩阵元素满足 (a_{ij} = a_{ji}) 压缩存储到一维数组 k = \\begin{cases}\\frac{i(i - 1)}{2} + j & 当 i \\geq j \\\\ \\frac{j(j - 1)}{2} + i & 当 i < j\\end{cases} （以一维数组 (B[n(n + 1) / 2]) 存储 (n) 阶对称矩阵）对角矩阵（如三对角矩阵）非0元素集中在主对角线及附近带状区域压缩存储到一维数组 k = 2i + j - 2 （以一维数组 (B[k](1 ≤ k ≤ 3×n - 2)) 存储 (n) 阶三对角矩阵）稀疏矩阵非0元素少且分布无规律三元组顺序表、十字链表用三元组 ((i, j, a_{ij})) 确定元素位置

广义表

广义表的定义与基本操作

广义表是线性表的推广，其元素既可以是单元素（原子），也可以是子表。记为 LS = (α₁, α₂, …, α_n) 。广义表的基本操作包括取表头 head(LS) 和取表尾 tail(LS) 。例如对于广义表 LS = (a, (b, c, d)) ，head(LS) 为 a ，tail(LS) 为 ((b, c, d)) 。

广义表的特点

多层次结构：元素可以是子表，子表的元素还可以是子表，形成多层次结构。
元素共享：广义表中的元素可以被其他广义表共享。
递归特性：元素可以是本广义表的名字，形成递归结构。

广义表的存储结构

由于广义表结构复杂，通常采用链式存储结构。针对原子和子表设计不同的结点结构，如对于广义表 LS = (a, (b, c, d)) ，其链式存储结构通过不同类型的结点来表示原子和子表。

代码示例：数组、矩阵与广义表操作实现

import java.util.ArrayList;import java.util.List;// 二维数组操作示例class ArrayOperations {  public static void main(String[] args) {  int[][] array = new int[3][4]; // 初始化数组 for (int i = 0; i < array.length; i++) {  for (int j = 0; j < array[i

软件设计师之数据结构深化：数组、矩阵与广义表的全面解析_对角矩阵软件设计师