第3章 数组与动态数组
3.1 数组的基本概念
数组是计算机科学中最基础的线性数据结构，其核心特征是连续存储与随机访问。从逻辑结构看，数组中元素按线性顺序排列，每个元素对应唯一的索引；从物理结构看，元素在内存中占用连续的存储单元，相邻元素的地址间隔固定（取决于元素类型大小）。
3.1.1 数组的定义与特点
定义：数组是由相同数据类型的元素组成的有限集合，元素在内存中按顺序连续存储，通过索引（index）可直接访问任意元素。
核心特点：
随机访问：通过索引计算元素地址，访问时间复杂度为 O(1)O(1)O(1)。设数组首地址为 basebasebase，元素大小为 sizesizesize，则索引 iii 处元素的地址为 base+i×sizebase + i \times sizebase+i×size（Python中因动态类型特性，实际地址计算更复杂，但逻辑一致）。
固定容量：静态数组在创建时需指定容量，一旦分配内存，容量不可修改（若需扩容需手动申请新空间并复制元素）。
存储密度高：无需额外空间存储元素间关系（如链表的指针），内存利用率高。
局限性：
插入/删除效率低：若在数组中间或头部插入/删除元素，需移动后续元素（时间复杂度 O(n)O(n)O(n)）；仅尾部操作可高效完成（O(1)O(1)O(1)）。
容量固定问题：静态数组容量不足时需手动扩容，过程涉及内存申请与数据复制，耗时且繁琐。
3.1.2 静态数组与动态数组
按容量是否可动态调整，数组分为静态数组与动态数组：
静态数组：创建时指定容量，运行时不可修改。例如C语言的 int arr[10]，容量固定为10，若元素数量超过容量会导致溢出。
动态数组：容量可随元素数量增长自动调整（扩容），解决静态数组的容量限制问题。Python的列表（list）、Java的 ArrayList 均为动态数组的实现。
3.2 Python列表的底层实现：动态数组
Python中没有内置的静态数组类型，但其核心数据结构列表（list） 本质是动态数组。理解列表的底层实现，是掌握动态数组原理的关键。
3.2.1 列表的动态扩容机制
列表的底层通过动态数组实现：初始化时分配一定容量的内存空间，当元素数量达到容量上限时，自动申请更大的内存空间（通常为原容量的2倍），并将原元素复制到新空间，释放旧空间。这一过程称为“扩容”（resizing）。
扩容策略（以CPython为例）：
初始容量：创建空列表时，初始容量为0；添加第一个元素时，容量扩容为4。
倍增扩容：当元素数量（len(list)）等于当前容量时，新容量 = 原容量 * 2（若原容量为0，则新容量为1；若原容量接近阈值（如大于50000），扩容倍数可能降为1.125，避免内存浪费）。
扩容过程：
1.申请大小为新容量的内存块；
2.将原数组元素复制到新内存块；
3.释放原内存空间，更新列表的底层指针。
示例：
python

	lst = [] # 初始容量0，元素数0 
	lst.append(1) # 容量不足，扩容至4，元素数1 
	lst.append(2) # 容量4 > 元素数2，无需扩容 
	lst.append(3) 
	lst.append(4) # 元素数4 = 容量4，触发扩容，新容量8 
	lst.append(5) # 容量8 > 元素数5，无需扩容

3.2.2 列表常用操作的时间复杂度
列表的操作效率直接取决于底层动态数组的特性，核心操作的时间复杂度分析如下：

关键解释：append 的均摊复杂度为 O(1)O(1)O(1)
设数组初始容量为 nnn，扩容倍数为2，扩容前可执行 nnn 次 append（每次 O(1)O(1)O(1)），扩容时复制 nnn 个元素（O(n)O(n)O(n)）。总操作次数为 n+n=2nn + n = 2nn+n=2n，平均每次 append 为 2n/n=O(1)2n/n = O(1)2n/n=O(1)。
3.2.3 列表的空间效率
动态数组通过“预分配内存”提升时间效率，但可能导致空间浪费。例如，一个包含5个元素的列表，底层容量可能为8（如3.2.1示例），空闲空间占比 (8−5)/8=37.5% (8-5)/8 = 37.5% (8−5)/8=37.5%。
Python列表不主动缩容（即使删除元素，容量保持不变），若需释放冗余空间，可通过 lst = lst[:] 或 lst.clear() 触发内存重分配（但实际开发中极少需要手动优化）。
3.3 自定义动态数组实现
为深入理解动态数组的原理，本节基于Python实现一个简化的动态数组类 DynamicArray，模拟列表的核心功能（随机访问、尾部添加、插入、删除等）。
3.3.1 类设计与初始化
DynamicArray 需维护三个核心属性：
_data：底层存储容器（用Python列表模拟连续内存，实际开发中可用 ctypes 分配原始内存，但此处为简化用列表）；
_size：当前元素数量（即数组的“长度”）；
_capacity：当前容量（即底层容器的最大存储能力）。
初始化逻辑：
支持指定初始容量（默认1）；
初始 _size = 0，_data 初始化为长度为 _capacity 的列表（用 None 填充空位置）。
python

	class DynamicArray:
	def __init__(self, capacity=1):
	self._capacity = capacity # 初始容量
	self._size = 0 # 当前元素数量
	self._data = [None] * self._capacity # 底层存储容器

3.3.2 核心方法实现

1. 扩容与缩容（_resize）
   当元素数量达到容量上限时，触发扩容（默认2倍）；可选缩容（当元素数量远小于容量时，释放冗余空间）。
   python

	def _resize(self, new_capacity):
	"""调整数组容量至new_capacity，复制原元素到新空间"""
	new_data = [None] * new_capacity
	for i in range(self._size):
	new_data[i] = self._data[i] # 复制原元素
	self._data = new_data
	self._capacity = new_capacity

2. 尾部添加元素（append）
   检查是否需要扩容（若 _size == _capacity），然后在 _size 位置添加元素，更新 _size。
   python

	def append(self, value):
	"""在尾部添加元素"""
	if self._size == self._capacity:
	# 容量不足，扩容为原容量的2倍（至少1）
	self._resize(2 * self._capacity if self._capacity != 0 else 1)
	self._data[self._size] = value
	self._size += 1

3. 插入元素（insert）
   在指定索引 index 处插入元素，需移动后续元素（从 _size-1 到 index，依次后移一位），并检查扩容。
   python

	def insert(self, index, value):
	"""在索引index处插入元素（0 <= index <= _size）"""
	if index < 0 or index > self._size:
	raise IndexError("insert index out of range")
	if self._size == self._capacity:
	self._resize(2 * self._capacity if self._capacity != 0 else 1)
	# 移动后续元素（从后往前移，避免覆盖）
	for i in range(self._size, index, -1):
	self._data[i] = self._data[i-1]
	self._data[index] = value
	self._size += 1

4. 删除元素（pop）
   删除指定索引 index 处的元素，需移动后续元素（从 index+1 到 _size-1，依次前移一位）。可选缩容（例如当 _size < _capacity // 4 时，缩容为原容量的一半，避免空间浪费）。
   python

	def pop(self, index=None):
	"""删除并返回索引index处的元素（默认删除尾部元素）"""
	if self._size == 0:
	raise IndexError("pop from empty array")
	if index is None:
	index = self._size - 1 # 默认删除尾部
	if index < 0 or index >= self._size:
	raise IndexError("pop index out of range")
	value = self._data[index]
	# 移动后续元素（从前往后移，覆盖被删除元素）
	for i in range(index, self._size - 1):
	self._data[i] = self._data[i+1]
	self._data[self._size - 1] = None # 清空最后一个位置（可选）
	self._size -= 1
	
	# 缩容：当元素数量小于容量的1/4时，缩容为原容量的一半（避免频繁缩容）
	if self._capacity > 1 and self._size < self._capacity // 4:
	self._resize(self._capacity // 2)
	return value

5. 随机访问（getitem 与 setitem）
   通过索引访问或修改元素，需检查索引合法性（0≤index<size0 \leq index < _size0≤index<s​ize）。
   python

	def __getitem__(self, index):
	"""支持通过索引访问元素：arr[index]"""
	if index < 0 or index >= self._size:
	raise IndexError("index out of range")
	return self._data[index]
	
	def __setitem__(self, index, value):
	"""支持通过索引修改元素：arr[index] = value"""
	if index < 0 or index >= self._size:
	raise IndexError("index out of range")
	self._data[index] = value

6. 辅助方法（len、str）
   python

	def __len__(self):
	"""返回元素数量：len(arr)"""
	return self._size
	
	def __str__(self):
	"""返回字符串表示：[e0, e1, ..., en-1]"""
	return "[" + ", ".join(str(self._data[i]) for i in range(self._size)) + "]"

3.3.3 功能测试
通过实例验证 DynamicArray 的核心功能：
python

	# 初始化容量为2的动态数组
	arr = DynamicArray(capacity=2)
	arr.append(1)
	arr.append(2)
	print(arr) # 输出：[1, 2]（此时_size=2，_capacity=2）
	
	arr.append(3) # 容量不足，扩容至4
	print(arr._capacity) # 输出：4（扩容后容量）
	print(arr) # 输出：[1, 2, 3]
	
	arr.insert(1, 10) # 在索引1处插入10
	print(arr) # 输出：[1, 10, 2, 3]
	
	arr.pop(2) # 删除索引2处的元素（值为2）
	print(arr) # 输出：[1, 10, 3]
	
	arr.pop() # 删除尾部元素（值为3）
	print(arr) # 输出：[1, 10]（此时_size=2，_capacity=4，满足缩容条件）
	print(arr._capacity) # 输出：2（缩容至原容量的一半）

3.4 数组的应用：前缀和与差分
数组的连续存储特性使其在数值计算中应用广泛，前缀和与差分是两种基于数组的高效预处理技术，可显著优化区间查询与更新操作。
3.4.1 前缀和数组
定义：对于数组 numsnumsnums，其前缀和数组 prefixprefixprefix 满足 prefix[i]=nums[0]+nums[1]+⋯+nums[i−1]prefix[i] = nums[0] + nums[1] + \dots + nums[i-1]prefix[i]=nums[0]+nums[1]+⋯+nums[i−1]（即 prefix[0]=0prefix[0] = 0prefix[0]=0，prefix[1]=nums[0]prefix[1] = nums[0]prefix[1]=nums[0]，prefix[2]=nums[0]+nums[1]prefix[2] = nums[0]+nums[1]prefix[2]=nums[0]+nums[1]，以此类推）。
核心作用：通过前缀和数组，可将“区间和查询”从 O(n)O(n)O(n) 优化为 O(1)O(1)O(1)。设查询区间 [l,r][l, r][l,r]（0-based，闭区间），则区间和 sum(nums[l..r])=prefix[r+1]−prefix[l]sum(nums[l..r]) = prefix[r+1] - prefix[l]sum(nums[l..r])=prefix[r+1]−prefix[l]。
实现步骤：
1.初始化前缀和数组 prefixprefixprefix，长度为 n+1n+1n+1（nnn 为原数组长度），prefix[0]=0prefix[0] = 0prefix[0]=0；
2.遍历原数组，计算 prefix[i]=prefix[i−1]+nums[i−1]prefix[i] = prefix[i-1] + nums[i-1]prefix[i]=prefix[i−1]+nums[i−1]（iii 从1到 nnn）。
示例：
python

	def compute_prefix(nums):
	n = len(nums)
	prefix = [0] * (n + 1)
	for i in range(1, n + 1):
	prefix[i] = prefix[i-1] + nums[i-1]
	return prefix
	
	nums = [1, 2, 3, 4, 5]
	prefix = compute_prefix(nums)
	print(prefix) # 输出：[0, 1, 3, 6, 10, 15]
	
	# 查询区间[1, 3]（即nums[1]到nums[3]：2+3+4=9）
	l, r = 1, 3
	print(prefix[r+1] - prefix[l]) # 输出：10 - 1 = 9

3.4.2 差分数组
定义：对于数组 numsnumsnums，其差分数组 diffdiffdiff 满足 diff[0]=nums[0]diff[0] = nums[0]diff[0]=nums[0]，diff[i]=nums[i]−nums[i−1]diff[i] = nums[i] - nums[i-1]diff[i]=nums[i]−nums[i−1]（i≥1i \geq 1i≥1）。差分数组的前缀和即为原数组（nums[i]=diff[0]+diff[1]+⋯+diff[i]nums[i] = diff[0] + diff[1] + \dots + diff[i]nums[i]=diff[0]+diff[1]+⋯+diff[i]）。
核心作用：将“区间更新”（对 [l,r][l, r][l,r] 内所有元素加 valvalval）从 O(n)O(n)O(n) 优化为 O(1)O(1)O(1)。通过差分数组，区间更新可转化为两点更新：diff[l]+=valdiff[l] += valdiff[l]+=val，diff[r+1]−=valdiff[r+1] -= valdiff[r+1]−=val（若 r+1<nr+1 < nr+1<n），最后对差分数组求前缀和即可还原更新后的原数组。
实现步骤：
1.初始化差分数组 diffdiffdiff，长度为 nnn（nnn 为原数组长度）；
2.区间更新 [l,r][l, r][l,r] 加 valvalval：diff[l]+=valdiff[l] += valdiff[l]+=val，若 r+1<nr+1 < nr+1<n 则 diff[r+1]−=valdiff[r+1] -= valdiff[r+1]−=val；
3.对 diffdiffdiff 求前缀和，得到更新后的原数组。
示例：
python

	def compute_diff(nums):
	n = len(nums)
	diff = [0] * n
	diff[0] = nums[0]
	for i in range(1, n):
	diff[i] = nums[i] - nums[i-1]
	return diff
	
	def range_add(diff, l, r, val):
	"""对原数组区间[l, r]（闭区间）所有元素加val，通过差分实现O(1)更新"""
	diff[l] += val
	if r + 1 < len(diff):
	diff[r + 1] -= val
	
	def diff_to_nums(diff):
	"""将差分数组还原为原数组（求前缀和）"""
	nums = [0] * len(diff)
	nums[0] = diff[0]
	for i in range(1, len(diff)):
	nums[i] = nums[i-1] + diff[i]
	return nums
	
	# 原数组：[1, 2, 3, 4, 5]
	nums = [1, 2, 3, 4, 5]
	diff = compute_diff(nums)
	print(diff) # 输出：[1, 1, 1, 1, 1]（差分数组）
	
	# 对区间[1, 3]（原数组索引1到3）所有元素加2
	range_add(diff, l=1, r=3, val=2)
	print(diff) # 输出：[1, 3, 1, 1, -1]（差分数组更新后）
	
	# 还原原数组
	new_nums = diff_to_nums(diff)
	print(new_nums) # 输出：[1, 4, 5, 6, 5]（原数组更新后：[1, 2+2, 3+2, 4+2, 5]）

小结
本章系统介绍了数组的核心概念、动态数组的实现原理及Python列表的底层机制，并通过自定义 DynamicArray 类深入理解了动态扩容、元素操作等细节。数组的连续存储特性使其支持高效随机访问，但插入删除效率受限；动态数组通过自动扩容解决了静态数组的容量问题，是Python列表的底层实现。最后，通过前缀和与差分技术，展示了数组在优化区间查询与更新中的关键作用，为后续复杂数据结构的学习奠定基础。
本站原创，转载请注明出处：https://www.xin3721.com/python3/python53022.html