建立一个有序的单链表。单链表中各结点的值和结点个数等自定。要求将建立好的有序单链表遍历输出。
时间: 2024-10-11 12:11:28 浏览: 18
创建一个有序的单链表通常涉及以下几个步骤:
1. 定义节点结构:首先,你需要定义一个`Node`类,包含数据域`data`和指向下一个节点的指针`next`。
```python
class Node:
def __init__(self, data=None):
self.data = data
self.next = None
```
2. 创建头节点:初始化一个特殊的节点,称为头节点(head),它本身没有数据,仅用于链接列表中的其他节点。
```python
def create_empty_list():
head = Node()
head.next = None
return head
```
3. 插入元素保持有序:添加新元素时,需要将其插入到已排序的部分。可以设计一个辅助函数来比较新值并找到正确的插入位置。
```python
def insert_sorted(head, new_data):
if not head or new_data < head.data:
new_node = Node(new_data)
new_node.next = head
head = new_node
else:
current = head
while current.next and new_data > current.next.data:
current = current.next
new_node = Node(new_data)
new_node.next = current.next
current.next = new_node
return head
```
4. 遍历并打印链表:最后,你可以定义一个函数来遍历整个链表,并按顺序打印节点的数据。
```python
def print_list(head):
current = head
while current:
print(current.data)
current = current.next
```
现在,你可以通过不断调用`insert_sorted`函数来添加元素,然后调用`print_list`来查看结果。记住,为了保持有序,每次插入元素时都需要确保它在正确的位置。
阅读全文