Python如何实现动态数组
Python序列类型
在本博客中，我们将学习探讨Python的各种“序列”类，内置的三⼤常⽤数据结构——列表类（list）、元组类（tuple）和字符串类（str）。
不知道你发现没有，这些类都有⼀个很明显的共性，都可以⽤来保存多个数据元素，最主要的功能是：每个类都⽀持下标（索引）访问该序列的元素，⽐如使⽤语法 Seq[i]。其实上⾯每个类都是使⽤数组这种简单的数据结构表⽰。
但是熟悉Python的读者可能知道这3种数据结构⼜有⼀些不同：⽐如元组和字符串是不能修改的，列表可以修改。
计算机内存中的数组结构
计算机体系结构中，我们知道计算机主存由位信息组成，这些位通常被归类成更⼤的单元，这些单元则取决于精准的系统架构。⼀个典型的单元就是⼀个字节，相当于8位。
计算机系统拥有庞⼤数量的存储字节，那么如何才能到我们的信息存在哪个字节呢？答案就是⼤家平时
熟知的存储地址。基于存储地址，主存中的任何字节都能被有效的访问。实际上，每个存储字节都和⼀个作为其地址的唯⼀⼆进制数字相关联。如下图中，每个字节均被指定了存储地址：
⼀般来说，编程语⾔记录标识符和其关联值所存储的地址之间的关系。⽐如，当我们声明标识符 xx 就有可能和存储器中的某⼀值相关联，⽽标识符 yy就可能和其他的值相关联。⼀组相关的变量能够⼀个接⼀个地存储在计算机存储器的⼀块连续区域内。我们将这种⽅式称为数组。
我们来看Python中的例⼦，⼀个⽂本字符串 HELLO 是以⼀列有序字符的形式存储的，假定该字符串的每个Unicode字符需要两个字节的存储空间。最下⾯的数字就是该字符串的索引值。
我们可以看到，数组可以存储多个值⽽⽆需构造具有特定索引的多个变量来指定其中的每个项⽬，并且⼏乎在所有编程语⾔（例如C、Java、C#、C++）中使⽤，但是Python更具有优势。Python在构建列表时，熟悉的读者可能知道，不需要预先定义数组或列表的⼤⼩，相反，在Python中，列表具有动态性质，我们可以不断的往列表中添加我们想要的数据元素。接下来，让我们看看Python列表的知识（已经熟悉的读者可以快速浏览或者跳过）。
Python列表
Python列表的操作
创建列表的语法格式：
[ele1, ele2, ele3, ele4, ...]
创建元组的语法格式：
(ele1, ele2, ele3, ele4, ...)
元组⽐列表的内存空间利⽤率更⾼，因为元组是固定不变的，所以没有必要创建拥有剩余空间的动态数组。
我们先在Python的IDE中创建⼀个列表，然后⼤致了解⼀下列表部分内置操作，我们先创建了⼀个名为test_list的列表，然后修改（插⼊或删除）元素，反转或清空列表，具体如下：
>>> test_list = [] # 创建名为test_list的空列表
>>> test_list.append("Hello")
>>> test_list.append("World")
>>> test_list
['Hello', 'World']
>>> test_list = ["Hello", "Array", 2019, "easy learning", "DataStructure"] # 重新给test_list赋值
>>> len(test_list) # 求列表的长度
5
>>> test_list[2] = 1024 # 修改列表元素
>>> test_list
['Hello', 'Array', 1024, 'easy learning', 'DataStructure']
>>>
>>> test_list.insert(1, "I love")  # 向列表中指定位置中插⼊⼀个元素
>>> test_list
['Hello', 'I love', 'Array', 1024, 'easy learning', 'DataStructure']
>>> test_list.append(2020) # 向列表末尾增加⼀个元素
>>> test_list
['Hello', 'I love', 'Array', 1024, 'easy learning', 'DataStructure', 2020]
>>>
>>> test_list.pop(1)  # 删除指定位置的元素
'I love'
>>> ve(2020) # 删除指定元素
>>>
>>> test_list.index('Hello')  # 查某个元素的索引值
>>> test_list.index('hello')  # 如果查某个元素不在列表中，返回ValueError错误
Traceback (most recent call last):
File "<pyshell#11>", line 1, in <module>
test_list.index('hello')
ValueError: 'hello' is not in list
>>>
>>> verse() # 反转整个列表
>>> test_list
['DataStructure', 'easy learning', 2019, 'Array', 'Hello']
>>> test_list.clear()  # 清空列表
>>> test_list
[]
我们看上⾯的代码，可以看到list的相关操作——增删改查，已经很强⼤了，还有⼀些内置⽅法这⾥并没有做展⽰，留给读者⾃⼰去发现并体验。
那么Python内置的list类是如何被实现的呢？
好吧，答案是动态数组。说到这⾥，不知道⼤家学Python列表的时候是不是这样想的——列表很简单嘛，就是list()类、⽤中括号[]括起来，然后指导书籍或⽂档上的各类⽅法append、insert、在IDE或者Pycharm⼀顿操作过后，是的我学会了。
但其实真的很不简单，⽐如我举个例⼦：A[-1]这个操作怎么实现？列表切⽚功能怎么实现？如何⾃⼰写pop()默认删除列表最右边的元素(popleft删除最左边简单)？...这些功能⽤起来爽，但真的⾃⼰实现太难了（我也还在学习中，⼤佬们请轻喷！）如果我们能学习并理解，肯定可以加强我们对数组这⼀结构的理解。
动态数组
什么是动态数组
动态数组是内存的连续区域，其⼤⼩随着插⼊新数据⽽动态增长。在静态数组中，我们需要在分配时指定⼤⼩。在定义数组的时候，其实计算机已经帮我们分配好了内存来存储，实际上我们不能扩展数组，因为它的⼤⼩是固定的。⽐如：我们分配⼀个⼤⼩为10的数组，则不能插⼊超过10个项⽬。
但是动态数组会在需要的时候⾃动调整其⼤⼩。这⼀点有点像我们使⽤的Python列表，可以存储任意数
量的项⽬，⽽⽆需在分配时指定⼤⼩。
所以实现⼀个动态数组的实现的关键是——如何扩展数组？当列表list1的⼤⼩已满时，⽽此时有新的元素要添加进列表，我们会执⾏⼀下步骤来克服其⼤⼩限制的缺点：
分配具有更⼤容量的新数组 list2
设置 list2[i] = list1[i] (i=0,1,2,...，n-1)，其中n是该项⽬的当前编号
设置list1 = list2，也就是说，list2正在作为新的数组来引⽤我们的新列表。
然后，只要将新的元素插⼊（添加）到我们的列表list1即可。
接下来要思考的问题是，新数组应该多⼤？通常我们得做法是：新数组的⼤⼩是已满的旧数组的2倍。我们将在Python中编程实现动态数组的概念，并创建⼀个简单的代码，很多功能不及Python强⼤。
实现动态数组Python代码
在Python中，我们利⽤ctypes的内置库来创建⾃⼰的动态数组类，因为ctypes模块提供对原始数组的⽀持，为了更快的对数组进⾏学习，所以对ctypes的知识可以查看官⽅⽂档进⾏学习。关于Python的公有⽅法与私有⽅法，我们在⽅法名称前使⽤双下划线**__**使其保持隐藏状态，代码如下：
# -*- coding: utf-8 -*-
# @Time  : 2019-11-01 17:10
# @Author  : yuzhou_1su
# @ContactMe : blog.csdn/yuzhou_1shu
# @File  : DynamicArray.py
# @Software : PyCharm
import ctypes
class DynamicArray:
"""A dynamic array class akin to a simplified Python list."""  def __init__(self):
"""Create an empty array."""
self.n = 0      # count actual elements
self.capacity = 1  # default array capacity
self.A = self._make_array(self.capacity)  # low-level array  def is_empty(self):
""" Return True if array is empty"""
return self.n == 0
def __len__(self):
"""Return numbers of elements stored in the array."""
return self.n
def __getitem__(self, i):
"""Return element at index i."""
if not 0 <= i < self.n:
# Check it i index is in bounds of array
raise ValueError('invalid index')
return self.A[i]
def append(self, obj):
"""Add object to end of the array."""
if self.n == self.capacity:
# Double capacity if not enough room
self._resize(2 * self.capacity)
self.A[self.n] = obj  # Set self.n index to obj
self.n += 1
def _resize(self, c):
"""Resize internal array to capacity c."""
B = self._make_array(c)  # New bigger array
for k in range(self.n):  # Reference all existing values
B[k] = self.A[k]
self.A = B    # Call A the new bigger array
self.capacity = c  # Reset the capacity
@staticmethod
def _make_array(c):
"""Return new array with capacity c."""
return (c * ctypes.py_object)()
def insert(self, k, value):
"""Insert value at position k."""
if self.n == self.capacity:
字符串转数组 csdn
self._resize(2 * self.capacity)
for j in range(self.n, k, -1):
self.A[j] = self.A[j-1]
self.A[k] = value
self.n += 1
def pop(self, index=0):
"""Remove item at index (default first)."""
if index >= self.n or index < 0:
raise ValueError('invalid index')
for i in range(index, self.n-1):
self.A[i] = self.A[i+1]
self.A[self.n - 1] = None
self.n -= 1
def remove(self, value):
"""Remove the first occurrence of a value in the array."""    for k in range(self.n):
if self.A[k] == value:
for j in range(k, self.n - 1):
self.A[j] = self.A[j+1]
self.A[self.n - 1] = None
self.n -= 1
return
raise ValueError('value not found')
def _print(self):
"""Print the array."""
for i in range(self.n):
print(self.A[i], end=' ')
print()
测试动态数组Python代码
上⾯我们已经实现了⼀个动态数组的类，相信都很激动，接下来让我们来测试⼀下，看能不能成功呢？在同⼀个⽂件下，写的测试代码如下：
def main():
# Instantiate
mylist = DynamicArray()
# Append new element
mylist.append(10)
mylist.append(9)
mylist.append(8)
# Insert new element in given position
mylist.insert(1, 1024)
mylist.insert(2, 2019)
# Check length
print('The array length is: ', mylist.__len__())
# Print the array
print('Print the array：')
mylist._print()
# Index
print('The element at index 1 is :', mylist[1])
# Remove element
print('Remove 2019 in array:')
mylist._print()
# Pop element in given position
print('Pop pos 2 in array:')
# mylist.pop()
mylist.pop(2)
mylist._print()
if __name__ == '__main__':
main()
测试结果
激动⼈⼼的时刻揭晓，测试结果如下。请结合测试代码和数组的结构进⾏理解，如果由疏漏，欢迎⼤家指出。
The array length is: 5
Print the array：
10 1024 2019 9 8
The element at index 1 is : 1024
Remove 2019 in array:
10 1024 9 8
Pop pos 2 in array:
10 1024 8
总结
通过以上的介绍，我们知道了数组存在静态和动态类型。⽽在本博客中，我们着重介绍了什么是动态数组，并通过Python代码进⾏实现。希望你能从此以复杂的⽅式学会数组。
总结发⾔，其实越是简单的操作，背后实现原理可能很复杂。
以上就是本⽂的全部内容，希望对⼤家的学习有所帮助，也希望⼤家多多⽀持。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。