4 线性数据结构之数组

在前面的引言中，我们了解了数据结构的基本概念以及线性数据结构的主要特性。这一章，我们将专注于线性数据结构中的一种基本实现——数组。数组是一种最常用、最基本的数据结构，它为我们提供了一种高效管理数据的方法。

什么是数组

数组是一种按顺序排列的数据集合，所有元素都存储在连续的内存空间中。数组的每个元素都可以通过一个非负整数索引来访问。数组的大小在创建时就被定义，之后是不变的。

数组的特点

• 顺序存储：数组的元素在内存中是连续存放的，这使得随机访问非常高效。
• 固定大小：数组的容量在创建时就被确定，无法动态调整。
• 高效性：通过索引可以以 $O(1)$ 的时间复杂度访问任意元素，但插入和删除操作在最坏情况下可能需要 $O(n)$ 的时间复杂度。

数组的基本操作

在这一部分，我们将介绍一些基本的数组操作，包括创建数组、访问元素、更新元素和遍历数组。

创建数组

在Python中，我们可以使用普通的列表来创建一个数组。举个例子：

# 创建一个数组并初始化元素
array = [10, 20, 30, 40, 50]

访问元素

可以通过索引来访问数组中的元素。索引从0开始：

# 访问数组的第一个元素
first_element = array[0]  # 10

更新元素

数组中的元素也可以通过索引进行更新：

# 更新数组的第二个元素
array[1] = 25  # array 变为 [10, 25, 30, 40, 50]

遍历数组

我们可以使用循环遍历数组中的所有元素：

# 遍历数组并打印每个元素
for element in array:
    print(element)

数组的应用场景

数组在编程中有广泛的应用，以下是一些常见的场景：

1. 数据存储：由于其固定大小和顺序排列，数组非常适合用于存储静态数据。
2. 实现其他数据结构：许多其他数据结构（如栈、队列等）都可以使用数组来实现。
3. 快速查找：通过数组索引，我们可以快速查找数据。

数组的优缺点总结

优点：

• 快速访问：元素可以在常数时间内通过索引访问。
• 内存使用效率高：由于连续存储，数组可以有效利用内存。

缺点：

• 大小固定：在数组创建后，大小不可更改，这限制了灵活性。
• 插入和删除效率低：在数组中间插入或删除元素时，可能需要移动大量元素，从而导致 $O(n)$ 的时间复杂度。

小案例：数组的基本操作

我们来写一个简单的Python程序，示范数组的基本操作：

# 初始化一个数组
numbers = [1, 2, 3, 4, 5]

# 访问元素
print("访问第一元素:", numbers[0])  # 输出 1

# 更新元素
numbers[2] = 10
print("更新后的数组:", numbers)  # 输出 [1, 2, 10, 4, 5]

# 遍历数组
print("遍历数组:")
for number in numbers:
    print(number)

执行上述代码，我们能够直观地看到数组的创建、访问、更新和遍历。

小结

在本章中，我们详细讨论了数组的定义、特点及其基本操作。数组作为线性数据结构的一种基础实现，具有许多优点，但同时也有其局限性。了解数组的这些知识，将为后续数据结构的学习打下良好的基础。

下一篇将介绍线性数据结构中的另一重要实现——链表。在该章节中，我们将探索链表的构造和应用，以及它与数组的对比。希望大家能够保持兴趣，继续深入学习！