设计一个单链表的基本操作的演示程序。初始化单链表,生成单链表,遍历线性表,在第i个元素前插入元素e,删除第i个元素,将单链表逆置
时间: 2024-11-09 22:20:00 浏览: 5
数据结构第二章 线性表.doc
设计一个简单的单链表操作演示程序可以使用Python语言编写,这里我们先定义链表节点和链表结构,然后实现基本操作:
```python
class Node:
def __init__(self, data=None):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
# 初始化空链表
def initialize(self):
self.head = None
# 添加节点到链表尾部
def append(self, data):
if not self.head:
self.head = Node(data)
else:
current = self.head
while current.next:
current = current.next
current.next = Node(data)
# 遍历链表并打印数据
def traverse(self):
current = self.head
while current:
print(current.data, end=" -> ")
current = current.next
print("None")
# 在第i个位置插入元素e
def insert_at_index(self, i, e):
if i <= 0 or i > self.size():
raise IndexError("Index out of range")
new_node = Node(e)
if i == 1:
new_node.next = self.head
self.head = new_node
else:
current = self.head
for _ in range(i - 2):
if current is None:
raise IndexError("Invalid index")
current = current.next
new_node.next = current.next
current.next = new_node
# 删除第i个元素
def delete_at_index(self, i):
if i < 1 or i > self.size():
raise IndexError("Index out of range")
if i == 1:
self.head = self.head.next
else:
current = self.head
for _ in range(i - 1):
current = current.next
if current is None or current.next is None:
raise IndexError("Invalid index")
current.next = current.next.next
# 计算链表大小
def size(self):
count = 0
current = self.head
while current:
count += 1
current = current.next
return count
# 将链表逆置
def reverse(self):
prev = None
current = self.head
while current:
next_node = current.next
current.next = prev
prev = current
current = next_node
self.head = prev
# 演示操作
ll = LinkedList()
ll.initialize()
# 插入操作
ll.append(1)
ll.append(2)
ll.insert_at_index(1, 3)
# 遍历、删除和逆置操作
ll.traverse() # 输出: 1 -> 3 -> 2 -> None
ll.delete_at_index(1) # 删除3
ll.traverse() # 输出: 1 -> 2 -> None
# 逆置链表
ll.reverse()
ll.traverse() # 输出: 2 -> 1 -> None
```
在这个程序中,我们首先创建了Node类表示链表节点,然后创建LinkedList类实现了链表的各种操作。通过这个例子,你可以看到如何初始化链表、添加元素、遍历、插入、删除和逆置链表。
阅读全文