Python实现的顺序表手动构建
在 Python 中,顺序表通常可以用列表(list)来实现,因为 Python 的列表在内部实现上就是动态数组。不过,如果你想手动构建一个类似于顺序表的数据结构,可以从底层使用数组的思想来实现。这里是一个简单的例子,展示了如何手动构建一个顺序表类:
class MyArrayList:
def __init__(self, capacity=10):
# 初始化数组容量和内部存储
self.capacity = capacity # 初始容量
self.size = 0 # 当前元素个数
self.array = [None] * self.capacity # 内部存储
def is_empty(self):
return self.size == 0
def get_size(self):
return self.size
def get(self, index):
if 0 <= index < self.size:
return self.array[index]
else:
raise IndexError("Index out of bounds")
def add(self, element):
# 如果数组已满,扩充容量
if self.size == self.capacity:
self._resize(2 * self.capacity)
self.array[self.size] = element
self.size += 1
def insert(self, index, element):
if index < 0 or index > self.size:
raise IndexError("Index out of bounds")
if self.size == self.capacity:
self._resize(2 * self.capacity)
for i in range(self.size, index, -1):
self.array[i] = self.array[i - 1]
self.array[index] = element
self.size += 1
def remove(self, index):
if index < 0 or index >= self.size:
raise IndexError("Index out of bounds")
removed_element = self.array[index]
for i in range(index, self.size - 1):
self.array[i] = self.array[i + 1]
self.array[self.size - 1] = None
self.size -= 1
return removed_element
def _resize(self, new_capacity):
new_array = [None] * new_capacity
for i in range(self.size):
new_array[i] = self.array[i]
self.array = new_array
self.capacity = new_capacity
# 使用示例
my_list = MyArrayList()
my_list.add(10)
my_list.add(20)
my_list.insert(1, 15)
print(my_list.get(1)) # 输出 15
my_list.remove(1)
print(my_list.get(1)) # 输出 20
关键点说明:
容量管理:当数组达到其容量上限时,通过
_resize
方法增加容量。通常将容量加倍,以减少频繁扩容所带来的开销。数据移动:在插入和删除操作中,需要移动数组中的元素以保持顺序。
基本操作:提供了一些基本操作如
add
(尾部添加)、insert
(插入)和remove
(删除)等。
这个实现基本上涵盖了顺序表的一些常见操作,你可以根据需要进行扩展或优化。