【数据结构】线性数据结构——数组

1. 定义

数组是一种线性数据结构，由一组相同类型的元素组成，这些元素使用连续的内存空间存储。数组通过索引（下标）访问，每个元素的索引是固定的，从零开始递增。

2. 特点

• 顺序存储：
  • 元素在内存中按地址连续存储。
  • 索引可以直接计算存储位置，因此支持快速访问。
• 高效的随机访问： 通过索引可以在 O(1) 时间内访问任意元素。
• 固定大小： 数组的大小在创建时确定，无法动态扩展（静态数组）。
• 相同数据类型： 数组中的所有元素必须具有相同的数据类型。
• 插入和删除效率低： 若在中间插入或删除元素，需移动大量元素，时间复杂度为 O(n)。

3. 主要操作

• 访问元素： 通过索引直接访问，如 array[i]。时间复杂度：O(1)。
• 插入元素： 若在末尾插入，效率高，时间复杂度为 O(1)。若在中间插入，需要移动后续元素，时间复杂度为 O(n)。
• 删除元素： 删除中间元素需移动后续元素，时间复杂度为 O(n)。删除末尾元素效率高，时间复杂度为 O(1)。
• 搜索元素：
  • 线性搜索：逐个比较元素，时间复杂度为 O(n)。
  • 二分搜索（仅适用于有序数组）：时间复杂度为 O(logn)。

4. 优缺点

• 优点： 支持快速随机访问。/ 内存连续，易于管理。/适合存储固定大小、类型一致的数据。
• 缺点： 大小固定，缺乏灵活性。/ 插入和删除效率低，需移动大量元素。/ 可能导致内存浪费（未充分利用数组大小）。

5. 应用场景

• 需要高效随机访问的场景： 数组索引提供快速的定位能力。
• 存储固定大小的数据集： 如存储一周的温度数据、学生的成绩。
• 基础结构： 许多高级数据结构（如栈、队列、堆）都基于数组实现。