编写一个程序,实现单链表的各种基本运算,并在此基础上完成如下功能: 1.创建单链表 2.采用头插或尾插法依次插入节点元素的值 3.输出单链表 4.输出单链表的长度 5.判断单链表是否为空 6.输出单链表第i个位置上的元
时间: 2024-09-18 12:17:51 浏览: 55
数据结构(C语言)用单链表存储一元多项式并实现两个多项式的相加运算.doc
5星 · 资源好评率100%
在编写一个简单的单链表程序中,我们可以使用Python语言作为示例。这里我会给出一个基础的链表结构定义、操作函数以及对应的功能实现:
```python
class Node:
def __init__(self, data=None):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
# 创建空链表
def create_list(self):
self.head = None
# 插入节点(头插法)
def insert_at_head(self, value):
new_node = Node(value)
new_node.next = self.head
self.head = new_node
# 插入节点(尾插法)
def insert_at_tail(self, value):
if not self.head:
self.head = Node(value)
return
last_node = self.head
while last_node.next:
last_node = last_node.next
last_node.next = Node(value)
# 输出链表
def print_list(self):
current_node = self.head
while current_node:
print(current_node.data, end=" -> ")
current_node = current_node.next
print("None")
# 计算链表长度
def length(self):
count = 0
current_node = self.head
while current_node:
count += 1
current_node = current_node.next
return count
# 判断链表是否为空
def is_empty(self):
return self.head is None
# 获取并输出第i个节点(索引从0开始)
def get_nth_node(self, i):
if not self.is_empty() and i >= 0 and i < self.length():
current_node = self.head
for _ in range(i):
current_node = current_node.next
return current_node.data
else:
raise IndexError("Index out of range")
# 示例使用
linked_list = LinkedList()
linked_list.insert_at_head(1)
linked_list.insert_at_tail(3)
linked_list.insert_at_head(0)
linked_list.print_list() # 输出:0 -> 1 -> 3 -> None
print(linked_list.length()) # 输出:3
print(linked_list.get_nth_node(1)) # 输出:1
```
阅读全文