实现线性表的顺序存储定义,完成顺序表的创建、插入、删除、查找、排序等常用操作,完成两个有序线性表的合并,要求同样的数据元素只出现一次。
时间: 2023-06-19 12:10:55 浏览: 109
线性表的顺序存储的实现
4星 · 用户满意度95%
线性表的顺序存储定义:线性表的顺序存储结构是指用一组地址连续的存储单元依次存储线性表的数据元素。
具体实现:
```python
class SeqList:
def __init__(self, max_size):
self.data = [None] * max_size # 存储数据的列表
self.length = 0 # 线性表长度
self.max_size = max_size # 线性表最大长度
def is_empty(self):
"""
判断线性表是否为空
"""
return self.length == 0
def is_full(self):
"""
判断线性表是否已满
"""
return self.length == self.max_size
def clear(self):
"""
清空线性表
"""
self.data = [None] * self.max_size
self.length = 0
def insert(self, index, value):
"""
在指定位置插入元素
"""
if index < 0 or index > self.length:
raise Exception('Index out of range')
if self.is_full():
raise Exception('List is full')
for i in range(self.length - 1, index - 1, -1):
self.data[i + 1] = self.data[i]
self.data[index] = value
self.length += 1
def delete(self, index):
"""
删除指定位置的元素
"""
if index < 0 or index >= self.length:
raise Exception('Index out of range')
for i in range(index, self.length - 1):
self.data[i] = self.data[i + 1]
self.data[self.length - 1] = None
self.length -= 1
def find(self, value):
"""
查找元素并返回下标
"""
for i in range(self.length):
if self.data[i] == value:
return i
return -1
def sort(self):
"""
对线性表进行排序
"""
for i in range(self.length - 1):
for j in range(i + 1, self.length):
if self.data[i] > self.data[j]:
self.data[i], self.data[j] = self.data[j], self.data[i]
@staticmethod
def merge(list1, list2):
"""
合并两个有序线性表
"""
result = SeqList(list1.max_size + list2.max_size)
i, j = 0, 0
while i < list1.length and j < list2.length:
if list1.data[i] <= list2.data[j]:
if list1.data[i] != result.data[result.length - 1]:
result.insert(result.length, list1.data[i])
i += 1
else:
if list2.data[j] != result.data[result.length - 1]:
result.insert(result.length, list2.data[j])
j += 1
while i < list1.length:
if list1.data[i] != result.data[result.length - 1]:
result.insert(result.length, list1.data[i])
i += 1
while j < list2.length:
if list2.data[j] != result.data[result.length - 1]:
result.insert(result.length, list2.data[j])
j += 1
return result
```
其中,`SeqList` 为线性表的类,包含常用操作的实现,`merge` 为合并两个有序线性表的静态方法,使用示例:
```python
list1 = SeqList(10)
list1.insert(0, 1)
list1.insert(1, 3)
list1.insert(2, 5)
list2 = SeqList(10)
list2.insert(0, 2)
list2.insert(1, 4)
list2.insert(2, 6)
list3 = SeqList.merge(list1, list2)
print(list3.data) # [1, 2, 3, 4, 5, 6]
```
阅读全文