7 数据结构概述之数组

在我们的 算法小白教程 系列中，上一篇文章介绍了 递归算法，在那篇文章中我们讨论了如何使用递归方法解决一些常见问题。今天，我们将深入探讨一种基本的数据结构：数组。在了解了数组的基本概念和特性后，我们将为后续的 链表 讲解打下坚实的基础。

数组的基本概念

数组 是一种线性数据结构，用于存储一组相同类型的元素。与其他数据结构相比，数组具有以下几个显著特征：

1. 固定大小：在数组创建时，需要定义其大小，数组的大小一旦确定便不能更改。
2. 元素连续存储：数组中的元素在内存中是连续存放的，因此能够通过索引快速访问任意元素。
3. 随机访问：由于数组是随机存储的，可以通过索引直接访问任意位置的元素，其访问时间复杂度为 $O(1)$。

数组的创建和访问

创建数组的基本语法取决于所用的编程语言。以 Python 为例，创建一个数组可以使用列表（list）来实现。

# 创建一个数组
arr = [1, 2, 3, 4, 5]

# 访问数组中的元素
print(arr[0])  # 输出：1
print(arr[2])  # 输出：3

在这个例子中，我们定义了一个包含五个整数的数组 arr，可以通过索引访问它们。

数组的优缺点

数组具有一些明显的优点和缺点：

优点

• 快速访问：由于数组元素在内存中是连续存放的，可以通过索引在 $O(1)$ 的时间内访问。
• 高效的内存使用：数组占用的内存空间是连续的，可以有效使用缓存，提高访问速度。

缺点

• 固定大小：一旦声明，数组的大小便无法改变，不能根据需求动态扩展。
• 插入和删除效率低：在数组中插入或删除元素需要移动后续元素，最坏情况下时间复杂度为 $O(n)$。

数组的应用案例

数组在日常编程中有广泛的应用。下面是一个简单的案例，演示如何使用数组统计一组数字的平均值：

# 计算一组数的平均值
def calculate_average(numbers):
    total = 0
    count = len(numbers)
    
    for num in numbers:
        total += num
        
    return total / count if count > 0 else 0

# 数组示例
data = [10, 20, 30, 40, 50]
average = calculate_average(data)
print(f"数组的平均值是：{average}")  # 输出：数组的平均值是：30.0

在这个示例中，我们定义了一个函数 calculate_average，它接受一个数组并计算其平均值。通过遍历数组，我们将所有元素的和除以元素的个数，从而得到平均值。

数组的排序

数组常常需要进行排序操作。以 冒泡排序 为例，下面是一个简单的排序算法实现：

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]  # 交换
    return arr

# 示例
unsorted_arr = [64, 34, 25, 12, 22, 11, 90]
sorted_arr = bubble_sort(unsorted_arr)
print(f"排序后的数组：{sorted_arr}")  # 输出：排序后的数组：[11, 12, 22, 25, 34, 64, 90]

在这个示例中，我们实现了一个简单的 冒泡排序 算法，将一个无序数组排序为有序数组。

总结

在本篇文章中，我们探讨了 数组 这一基础数据结构，了解了其基本特性、优缺点及一些实际应用场景。数组是很多复杂数据结构和算法的基础，在学习 链表 等更复杂的数据结构时，我们会发现数组的知识是至关重要的。

下一篇文章中，我们将继续探索 链表 数据结构，了解它与数组的区别和应用。如果你还想深入了解其他更复杂的算法，欢迎继续关注我们的系列教程！