Python 中动态数组的实现
pythonserver side programmingprogramming更新于 2024/2/22 15:04:00
动态数组
在 Python 中，列表、集合和字典是可变对象。而数字、字符串和元组是不可变对象。可变对象意味着我们可以从列表、集合或字典中添加/删除项目，但是，对于元组或字符串等不可变对象，情况并非如此。
在 Python 中，列表是动态数组。让我们尝试创建一个动态列表 −
>>> #创建一个名为 list1 的空列表 >>> list1 = [] >>> type (list1) <class 'list'>
在我们的空列表 list1 上添加一些项目 −
>>> # 添加项目
>>> list1 =[2, 4, 6]
>>> list1
[2, 4, 6]
>>> # 添加项目的另一种方法，使用附加。
>>> list1.append('Tutorialspoint')
>>> list1
[2, 4, 6, 'Tutorialspoint']
从列表中删除一些项目 −
>>> # 从列表中删除项目 >>> list1.pop() 'Tutorialspoint' >>> list1 [2, 4, 6]
从上面我们可以看到，列表实际上是数组的扩展，我们可以在其中修改(增加或减少)列表的大小。我们从大小为"零"的列表开始，然后向其中添加"四个"项目。
动态数组实现的基础
考虑一个列表(即 list1)的示例，当数组的大小已满时，我们需要执行以下步骤来克服其大小限制的缺点。这是动态数组实现 − 背后的基础
- 分配一个具有更大容量的新数组 list2
- 设置 list2[i] = list1[i]，其中 i = 0,1...n-1，其中 n 是项目的当前编号。
- 设置 list1=list2，因为现在 list2 正在引用我们的新列表。
- 然后，只需将新项目插入(附加)到我们的列表(list1)中。
让我们创建一个简单的代码，说明如何在 python 编程中实现动态数组概念。我们将使用 python 中名为 ctypes 的内置库类创建我们自己的动态数组类，该类将用作 ctypes 模块中的原始数组。
dynamicArray.py
import ctypes
class DynamicArray(object):
#初始化它
def __init__(self):
#我们将有三个属性
self.n = 0 # 默认
self.capacity = 1 # 默认
self.A = self.make_array(self.capacity) # make_array 将在稍后定义
#Length 方法
def __len__(self):
#它将返回数组中的元素数量
return self.n
def __getitem__(self, k):
#它将返回索引 k 处的元素
if not 0 <=k <self.n:
return IndexError('k is out of bounds')
return self.A[k]
def append(self, element):
#检查容量
if self.n == self.capacity:
#将新数组的容量加倍，即
self.resize(2*self.capacity) # _resize 是稍后定义的方法
# 将数组 A 的 n 个索引设置为元素
self.A[self.n] = element
self.n += 1
def _resize(self, new_cap): #new_cap 用于新容量
# 声明数组 B
B = self.make_array(new_cap)
for k in range(self.n):
B[k] = self.A[k] # 引用从数组 A 到 B 的元素
# 然后引用一个
self.A = B # A 现在是数组 B
self.capacity = new_cap # 重置容量
#使用 ctypes 制作 make-array 方法
def make_array(self,new_cap):
return (new_cap * ctypes.py_object)()
arr = DynamicArray()
由于我们的动态类已准备好使用，让我们尝试使用它 −
>>> len(arr)
0
>>> arr.append(1)
>>> #输入第一项
>>> len(arr)
1
>>> arr.append('Tutorialspoint')
>>> #输入的第二项
>>> len(arr)
2
>>> arr[1]
'Tutorialspoint'
就是这样，我们创建了自己的动态数组，我们可以调整数组的大小，它是 python 中的列表。
