编程题: 设计实现一个表示动态数组的类。实现数组中数据的增加,删除,输出功能。 要求: 当向数组中增加元素时,容量不够时,自动扩充原数组容量2倍的大小,用于存放新元素。
时间: 2024-03-07 17:48:47 浏览: 88
好的,根据您的要求,我可以给您提供一个基本的实现思路:
```python
class DynamicArray:
def __init__(self):
self.capacity = 4
self.size = 0
self.arr = [None] * self.capacity
def __len__(self):
return self.size
def __getitem__(self, index):
if not 0 <= index < self.size:
return IndexError('Index out of range')
return self.arr[index]
def append(self, element):
if self.size == self.capacity:
self._resize(2 * self.capacity)
self.arr[self.size] = element
self.size += 1
def _resize(self, new_capacity):
new_arr = [None] * new_capacity
for i in range(self.size):
new_arr[i] = self.arr[i]
self.arr = new_arr
self.capacity = new_capacity
def pop(self):
if self.size == 0:
raise IndexError('Pop from empty array')
self.size -= 1
element = self.arr[self.size]
self.arr[self.size] = None
if self.size <= self.capacity // 4:
self._resize(self.capacity // 2)
return element
def __str__(self):
return "[" + ", ".join(str(self.arr[i]) for i in range(self.size)) + "]"
```
在上述代码中,我们首先定义了一个 `DynamicArray` 类,它包含了以下几个属性:
- `capacity`:表示当前数组的容量大小
- `size`:表示当前数组中数据元素的数量
- `arr`:表示当前数组中存储的元素列表
接着,我们实现了以下几个方法:
- `__init__`:初始化 `DynamicArray` 类,设置初始容量大小为 4,并将数组中的所有元素设置为 `None`
- `__len__`:返回当前数组中数据元素的数量
- `__getitem__`:返回数组中指定索引位置的元素,如果索引超出了数组的范围,则抛出 `IndexError`
- `append`:向数组中增加一个元素,如果当前数组容量不足,则自动扩充数组容量为原来的 2 倍
- `_resize`:调整数组的容量大小,将数组中的元素复制到新的数组中
- `pop`:从数组中移除最后一个元素,并返回该元素的值。如果数组为空,则抛出 `IndexError`
- `__str__`:将数组中的所有元素以字符串的形式返回
这样,我们就实现了一个简单的动态数组类,可以实现数据的增加、删除和输出功能,并且能够自动扩充数组容量。
阅读全文