当元素大小超过数组大小的1/2时调整数组大小

基础概念

在编程中，数组是一种线性数据结构，用于存储相同类型的元素集合。当数组中的元素数量超过其初始大小的一定比例（例如1/2）时，可能需要调整数组的大小以容纳更多的元素。这种操作通常称为动态数组扩容。

类型

固定大小数组：在编译时确定大小，无法在运行时调整。
动态数组：在运行时可以根据需要调整大小。

应用场景

动态数组常用于需要存储不确定数量元素的数据结构，例如：

列表
栈
队列

问题与解决方案

问题

当元素大小超过数组大小的1/2时，可能会导致数组越界错误或性能下降。

原因

数组越界：当尝试访问超出数组当前大小的索引时，会导致数组越界错误。
性能下降：频繁的插入和删除操作可能导致数组频繁调整大小，从而影响性能。

解决方案

动态扩容：当数组元素数量超过当前大小的1/2时，创建一个新的更大的数组，并将现有元素复制到新数组中。
预分配空间：根据经验或统计信息预先分配足够的空间，减少动态扩容的频率。

示例代码

以下是一个简单的Python示例，展示如何实现动态数组扩容：

class DynamicArray:
    def __init__(self):
        self.array = [None] * 1  # 初始大小为1
        self.length = 0  # 当前元素数量
        self.capacity = 1  # 数组容量

    def append(self, item):
        if self.length == self.capacity:
            self._resize(2 * self.capacity)  # 扩容为当前容量的两倍
        self.array[self.length] = item
        self.length += 1

    def _resize(self, new_capacity):
        new_array = [None] * new_capacity
        for i in range(self.length):
            new_array[i] = self.array[i]
        self.array = new_array
        self.capacity = new_capacity

# 使用示例
dynamic_array = DynamicArray()
dynamic_array.append(1)
dynamic_array.append(2)
dynamic_array.append(3)
print(dynamic_array.array)  # 输出: [1, 2, 3, None]