整理SqList顺序存储线性表的程序
时间: 2024-09-29 22:08:22 浏览: 9
在使用顺序存储(数组或链表)来实现线性表结构时,如`SqList`(假设这是一个简单的单向链表),整理其顺序通常涉及到排序操作。这里以插入排序为例,它是一种简单直观的算法:
```python
class ListNode:
def __init__(self, value=0, next=None):
self.value = value
self.next = next
class SqList:
def __init__(self):
self.head = None
self.size = 0
# 插入排序函数
def insertion_sort(self):
if self.size <= 1:
return
current = self.head
while current.next:
key = current.next.value
prev_node = current
while prev_node and prev_node.value > key:
prev_node = prev_node.prev
current.next.prev = prev_node
prev_node.next = current.next
current.next = key
if not current.prev:
self.head = current.next
self.size += 1
current = current.next
# 添加节点(用于示例)
def add(self, value):
new_node = ListNode(value)
if self.head is None:
self.head = new_node
else:
last_node = self.head
while last_node.next:
last_node = last_node.next
last_node.next = new_node
self.size += 1
# 示例使用
sq_list = SqList()
sq_list.add(5) # 添加一些元素
sq_list.add(3)
sq_list.add(7)
# 调用插入排序
sq_list.insertion_sort()
# 打印排序后的列表
current = sq_list.head
while current:
print(current.value, end=" -> ")
current = current.next
```
在这个例子中,`insertion_sort`函数会遍历链表,将每个元素放到其适当的位置,使得整个列表有序。