数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
Microsoft Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学Python动态数组的实现
动态数组
在Python中，列表、集合和字典是可变对象。而数字、字符串和元组是不可变对象。可变对象意味着我们可以向列表、集合或字典中添加/删除项，但对于不可变对象（如元组或字符串）则不行。
在Python中，列表就是一个动态数组。让我们尝试创建一个动态列表：
>>> #Create an empty list, named list1 >>> list1 = [] >>> type (list1) <class 'list'>
向我们的空列表list1中添加一些项：
>>> # Add items
>>> list1 =[2, 4, 6]
>>> list1
[2, 4, 6]
>>> # Another way to add items, using append.
>>> list1.append('Tutorialspoint')
>>> list1
[2, 4, 6, 'Tutorialspoint']从列表中删除一些项：
>>> # deleting item from a list >>> 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):
#Initialize it
def __init__(self):
#We'll have three attributes
self.n = 0 # by default
self.capacity = 1 # by default
self.A = self.make_array(self.capacity) # make_array will be defined later
#Length method
def __len__(self):
#It will return number of elements in the array
return self.n
def __getitem__(self, k):
#it will return the elements at the index k
if not 0 <=k <self.n:
return IndexError('k is out of bounds')
return self.A[k]
def append(self, element):
#checking the capacity
if self.n == self.capacity:
#double the capacity for the new array i.e
self.resize(2*self.capacity) # _resize is the method that is defined later
# set the n indexes of array A to elements
self.A[self.n] = element
self.n += 1
def _resize(self, new_cap): #new_cap is for new capacity
#declare array B
B = self.make_array(new_cap)
for k in range(self.n):
B[k] = self.A[k] # referencing the elements from array A to B
#ones refered then
self.A = B # A is now the array B
self.capacity = new_cap # resets the capacity
#making the make-array method using ctypes
def make_array(self,new_cap):
return (new_cap * ctypes.py_object)()
arr = DynamicArray()我们的动态类准备好使用后，让我们尝试一下：
>>> len(arr)
0
>>> arr.append(1)
>>> #First item entered
>>> len(arr)
1
>>> arr.append('Tutorialspoint')
>>> #second item entered
>>> len(arr)
2
>>> arr[1]
'Tutorialspoint'就是这样，我们创建了自己的动态数组，并且可以调整列表（在Python中是列表）的大小。
更新于：2019年7月30日
13K+ 浏览量
广告