数组：线性表的特殊形式与存储结构

"数据结构——数组" 在计算机科学中，数组是一种基础且重要的数据结构，它被视为一种特殊的线性表，因为在这个线性表中，每个数据元素本身也是一个线性表。数组通常由一个固定的大小的元素集合组成，这些元素具有相同的数据类型，并通过索引来访问。 ### 定义与特点 1. **定义**: 数组是由相同类型的数据元素构成的集合，这些元素在内存中是连续存储的，并通过一个唯一的整数索引（下标）来标识和访问。数组的大小（元素个数）是固定的，在声明时就需要确定，通常用m x n表示一个m行n列的二维数组。 2. **特点**: - **数组结构固定**: 一旦创建，数组的大小就不可变，这意味着不能动态添加或删除元素。 - **数据元素同构**: 所有元素都属于同一个数据类型，例如都是整数、字符或者浮点数等。 ### 数组运算 数组的基本操作包括： - **存取**: 给定一个索引，可以直接访问或修改对应位置的数据元素，时间复杂度为O(1)。 - **遍历**: 可以按顺序或反序遍历数组的所有元素，实现各种算法和操作。 ### 顺序存储结构 数组在内存中的存储通常采用顺序存储方式，有两种常见的主序约定： 1. **行序为主序**: 按照从左到右、从上到下的顺序存储，例如2D数组的第一维先变化，然后是第二维。 2. **列序为主序**: 与行序相反，先按列变化，再按行变化。 数组元素的位置可以通过公式计算得到： - 对于行序为主序的二维数组，`Loc(aij) = Loc(a11) + [(i-1)*n + (j-1)]*l`，其中`Loc()`表示元素的内存位置，`l`是每个元素的字节长度。 - 对于列序为主序，公式变为`Loc(aij) = Loc(a11) + [(j-1)*m + (i-1)]*l`。 ### 压缩存储 在处理特定类型的矩阵时，为了节省空间，可以使用压缩存储： 1. **对称矩阵**: 只存储对角线以下或以上的非零元素，因为对称矩阵的下三角等于上三角。 2. **三角矩阵**: 包括下三角矩阵（只存储下三角的元素）和上三角矩阵（只存储上三角的元素）。 3. **对角矩阵**: 只存储对角线上的元素，其他位置的元素默认为0。 对于压缩存储的矩阵，元素的位置也需要根据不同的存储方式调整计算公式。 数组作为基本的数据结构，广泛应用于编程和算法设计中，如排序算法、搜索算法、图论、线性代数等多个领域。理解并掌握数组的特点、存储方式和操作方法是学习高级数据结构和算法的基础。