利用数组建立顺序表实现任意节点的插入和删除输出顺序表中的所有元素
时间: 2024-10-15 13:11:30 浏览: 1
利用数组实现顺序表时,我们可以创建一个动态大小的数组来存储数据。为了实现在任意位置插入和删除元素以及遍历整个列表,我们需要维护一些关键信息:
1. **头指针**:指向数组的第一个元素,表示当前有序序列的开始。
2. **长度**:记录数组的实际元素数量。
### 插入操作:
- **在开头插入**:只需将新元素放在头指针的位置,然后更新头指针和长度。
- **在指定位置插入**:找到插入点(目标索引),将插入点后的元素向右移动一位,再将新元素放入该位置。
### 删除操作:
- **删除某个元素**:查找并移除目标元素的值,如果删除的是头元素,更新头指针;如果删除的是中间元素,则需要将后续元素向前移动一位。
### 遍历输出所有元素:
- 创建一个循环,从头指针开始,每次迭代增加索引直到达到数组长度。打印当前位置的元素。
以下是伪代码形式的实现:
```python
class ArraySequentialList:
def __init__(self):
self.data = []
self.head = 0
self.length = 0
# 插入元素
def insert(self, index, value):
if index < 0 or index > self.length:
print("Invalid index")
return
elif index == self.length:
self.data.append(value)
self.length += 1
else:
temp = self.data[index:]
self.data = self.data[:index] + [value] + temp
self.length += 1
# 删除元素
def remove(self, index):
if index < 0 or index >= self.length:
print("Invalid index")
return
if index == self.head:
self.head += 1
else:
for i in range(index, self.length - 1):
self.data[i] = self.data[i + 1]
self.length -= 1
# 遍历并输出
def traverse(self):
for i in range(self.head, self.length):
print(self.data[i])
# 使用示例
list = ArraySequentialList()
list.insert(0, 1) # 插入到头部
list.insert(2, 3) # 在第二个位置插入
list.traverse() # 输出:1, 3
list.remove(1) # 删除第二个元素
list.traverse() # 输出:1
```