设计整数循环单链表的基本运算程序,并用相关数据进行测试
时间: 2024-05-12 11:20:02 浏览: 9
整数循环单链表的基本运算包括:
1. 初始化:创建一个空链表。
2. 插入:在链表中的某个位置插入一个元素。
3. 删除:删除链表中的某个元素。
4. 查找:查找链表中某个元素的位置。
5. 修改:修改链表中某个元素的值。
6. 遍历:遍历整个链表并输出所有元素。
以下是整数循环单链表的基本运算程序的实现:
```python
class Node:
def __init__(self, data):
self.data = data
self.next = None
class CircularLinkedList:
def __init__(self):
self.head = None
self.tail = None
def is_empty(self):
return self.head is None
def insert(self, data):
new_node = Node(data)
if self.is_empty():
self.head = new_node
self.tail = new_node
new_node.next = self.head
else:
new_node.next = self.head
self.tail.next = new_node
self.tail = new_node
def delete(self, data):
if self.is_empty():
return
if self.head.data == data:
if self.head == self.tail:
self.head = None
self.tail = None
else:
self.head = self.head.next
self.tail.next = self.head
else:
prev_node = self.head
curr_node = self.head.next
while curr_node != self.head:
if curr_node.data == data:
prev_node.next = curr_node.next
if curr_node == self.tail:
self.tail = prev_node
return
prev_node = curr_node
curr_node = curr_node.next
def search(self, data):
if self.is_empty():
return -1
curr_node = self.head
index = 0
while curr_node != self.tail:
if curr_node.data == data:
return index
curr_node = curr_node.next
index += 1
if curr_node.data == data:
return index
return -1
def modify(self, old_data, new_data):
if self.is_empty():
return
curr_node = self.head
while curr_node != self.tail:
if curr_node.data == old_data:
curr_node.data = new_data
return
curr_node = curr_node.next
if curr_node.data == old_data:
curr_node.data = new_data
def traverse(self):
if self.is_empty():
return
curr_node = self.head
while curr_node != self.tail:
print(curr_node.data, end=' ')
curr_node = curr_node.next
print(curr_node.data, end=' ')
```
下面是对整数循环单链表的基本运算程序进行测试的代码:
```python
# 创建一个空链表
clist = CircularLinkedList()
# 插入元素
clist.insert(1)
clist.insert(2)
clist.insert(3)
clist.insert(4)
clist.insert(5)
# 遍历链表
clist.traverse() # 1 2 3 4 5
# 删除元素
clist.delete(3)
# 遍历链表
clist.traverse() # 1 2 4 5
# 查找元素
print(clist.search(4)) # 2
# 修改元素
clist.modify(2, 6)
# 遍历链表
clist.traverse() # 1 6 4 5
```