编制一个能演示将两个有序表合并为一个有序表的程序。 已知递增有序线性表LA和LB,现将LA和LB合并到LC,LC也是递增有序的。
时间: 2024-09-27 11:06:10 浏览: 48
要编写一个程序将两个递增有序的线性表LA和LB合并成一个新的递增有序表LC,我们可以采用归并排序的思想,创建一个临时数组来辅助操作。以下是使用Python语言的一个简单实现:
```python
class Node:
def __init__(self, data=None):
self.data = data
self.next = None
def merge_sorted_lists(la, lb):
# 创建新的头节点作为合并后的链表
if not la:
return lb
elif not lb:
return la
elif la.data <= lb.data:
merged_head = la
la = la.next
else:
merged_head = lb
lb = lb.next
# 临时节点用于存储合并后的数据
temp = merged_head
while la is not None and lb is not None:
if la.data <= lb.data:
temp.next = la
la = la.next
else:
temp.next = lb
lb = lb.next
temp = temp.next
# 将剩余的链表添加到合并后的链表
if la is not None:
temp.next = la
elif lb is not None:
temp.next = lb
return merged_head
# 示例
la = Node(1)
la.next = Node(3)
la.next.next = Node(5)
lb = Node(2)
lb.next = Node(4)
lb.next.next = Node(6)
lc = merge_sorted_lists(la, lb)
while lc:
print(lc.data, end=" -> ")
lc = lc.next
print("None") # 结束
```
这个程序首先检查哪个链表的头部数据较小,然后依次比较两个链表的节点,将较小的数据添加到临时链表中。最后返回合并后的链表头节点。
阅读全文