本文共 1220 字，大约阅读时间需要 4 分钟。

数组（数据结构）

数组的导学

课程结构

本章将从数组的基础知识入手，深入探讨数组的存储结构及其应用。

知识点线索

数组是一种特殊的线性表结构，其每个数据元素本身又是线性表。数组可以采用顺序存储或链式存储方式。

主要内容

数组的存储

不同语境中的数组

数组的抽象数据类型（ADT）

数据对象

数组中的每个数据元素属于同一种数据类型，具有相同类型的元素集合是数组。

数据关系

数组中的数据元素是一对一的线性关系。

基本操作

数组ADT中定义了一系列基本操作，但本文不做详细阐述。

维度不同的数组

数组的存储地址

数组的存储结构

要求数组所有元素存储在一块地址连续的内存单元中。

一维数组的存储地址

• 一维数组a[0]~a[9]存储在连续内存空间中，每个元素占L个字节。
• 元素地址计算：a + i * L，其中i为下标。

二维数组的存储地址

• 二维数组可以看成特殊的一维数组。
• 行优先存储：存储顺序为a1,a2,...,ap。
• 列优先存储：存储顺序为a1,a2,...,an。

特殊矩阵的压缩存储

什么是特殊矩阵

非零元素或零元素分布有规律的矩阵。

矩阵的存储方案

对称矩阵

定义

n阶方阵A[n][n]，满足a[i][j] = a[j][i]（0≤i，j≤n-1）。

存储

只存储下三角或上三角，包括主对角线。

对角矩阵

定义

非零元素集中在主对角线附近的带状区域。

特征

• 半带宽b：主对角线上下方各有b条次对角线。
• (2b+1)：矩阵的带宽。

三对角矩阵（b=1）的压缩存储

• 只存储带状区内的元素。
• 共有3n-2个非零元素。

稀疏矩阵

定义

阶数较大的矩阵中非零元素个数远小于总元素个数。

特点

• 大多数元素为零。
• 稀疏因子e = s/(m*n)，通常e≤0.05时称为稀疏矩阵。

存储方式

• 顺序存储：三元组表。
• 链式存储：十字链表。

以上内容结合了对数组数据结构的基础知识和实际应用，全面阐述了数组的存储方式及特殊矩阵的压缩存储方法。