设计一个有序顺序表,实现以下操作: 1.将元素x插入表中并保持有序; 2.查找值为x的元素,若找到则将其删除; 3.输出表中所有元素。 。要求:对上述每个操作各设计为一个子函数,并设计一个主函数调用各子函数,以验证所设计的有序顺序表的正确性。
时间: 2024-09-24 17:19:43 浏览: 28
为了设计一个有序顺序表,我们可以选择使用常见的线性结构,比如单链表。这里我们将创建一个Node类表示节点,包含一个数据元素和指向下一个节点的指针,然后定义一个OrderedList类,实现插入、查找和遍历功能。
首先,我们定义`Node`类:
```python
class Node:
def __init__(self, data=None):
self.data = data
self.next = None
```
接下来,我们实现`OrderedList`类:
```python
class OrderedList:
def __init__(self):
self.head = None
# 插入元素并保持有序
def insert_sorted(self, x):
if not self.head or x < self.head.data:
new_node = Node(x)
new_node.next = self.head
self.head = new_node
else:
current = self.head
while current.next and x > current.next.data:
current = current.next
new_node = Node(x)
new_node.next = current.next
current.next = new_node
# 查找并删除值为x的元素
def delete_element(self, x):
if not self.head:
return False
elif self.head.data == x:
self.head = self.head.next
return True
current = self.head
while current.next and current.next.data != x:
current = current.next
if current.next is not None:
current.next = current.next.next
return True
return False
# 遍历并输出所有元素
def print_list(self):
elements = []
current = self.head
while current:
elements.append(current.data)
current = current.next
print("Sorted List:", elements)
# 主函数用于测试
def main():
ordered_list = OrderedList()
# 测试插入元素
ordered_list.insert_sorted(5)
ordered_list.insert_sorted(2)
ordered_list.insert_sorted(8)
print("\nAfter insertion:")
ordered_list.print_list()
# 测试查找和删除
element_to_delete = 2
if ordered_list.delete_element(element_to_delete):
print(f"Element {element_to_delete} deleted successfully.")
else:
print(f"{element_to_delete} not found in the list.")
ordered_list.print_list()
# 测试更多插入和打印
ordered_list.insert_sorted(3)
ordered_list.insert_sorted(7)
ordered_list.print_list()
if __name__ == "__main__":
main()
```
阅读全文