对上述代码进行完善,要求利用单向循环链表存储结构模拟此过程,按照出列的顺序输出各个人的编号。输入数据:建立输入函数处理输入的数据,输入m的初值n,输入每个人的密码,建立单向循环链表。输出形式:建立一个输出函数,将正确的出列顺序输出。
时间: 2024-03-12 17:50:28 浏览: 61
利用单向循环链表存储结构模拟约瑟夫问题,按照出列的顺序印出每个人的编号。
以下是使用单向循环链表模拟出列过程的代码:
```python
class Node:
def __init__(self, data):
self.data = data
self.next = None
class CircleLinkedList:
def __init__(self):
self.head = None
self.tail = None
self.size = 0
# 在链表尾部添加节点
def add(self, data):
new_node = Node(data)
if self.head is None:
self.head = new_node
self.tail = new_node
else:
self.tail.next = new_node
self.tail = new_node
self.tail.next = self.head # tail节点指向head节点,形成循环链表
self.size += 1
# 在链表中删除指定节点
def remove(self, node):
if self.size == 0:
return
if self.head == node:
if self.size == 1:
self.head = None
self.tail = None
else:
self.head = self.head.next
self.tail.next = self.head
else:
cur_node = self.head
while cur_node.next != self.head:
if cur_node.next == node:
cur_node.next = node.next
if self.tail == node:
self.tail = cur_node
break
cur_node = cur_node.next
self.size -= 1
def input_data():
m = int(input("请输入m的初值n:"))
n = int(input("请输入每个人的密码,以空格分隔:"))
nums = list(range(1, n+1))
linked_list = CircleLinkedList()
for num in nums:
linked_list.add(num)
return m, linked_list
def output_data(m, linked_list):
cur_node = linked_list.head
while linked_list.size > 0:
for i in range(m-1):
cur_node = cur_node.next
print(cur_node.data, end=" ")
next_node = cur_node.next
linked_list.remove(cur_node)
cur_node = next_node
m, linked_list = input_data()
output_data(m, linked_list)
```
在这个代码中,我们定义了一个Node类,表示链表中的节点。然后定义了一个CircleLinkedList类,表示单向循环链表。在这个类中,我们实现了在链表尾部添加节点和在链表中删除指定节点的功能,同时维护了链表的大小。
然后我们定义了一个input_data函数,用于处理输入的数据。在这个函数中,我们首先输入m和n的值,然后生成一个包含1到n的整数的列表,将这个列表添加到单向循环链表中。最后返回m和链表。
最后我们定义了一个output_data函数,用于输出正确的出列顺序。在这个函数中,我们首先获取链表的头结点,并在循环中按照m的值找到需要出列的节点。然后删除这个节点,并将当前节点指向下一个节点,循环直到链表为空。每次删除节点时,我们都会将当前节点指向下一个节点,以便在下一轮循环中继续查找。在删除节点之前,我们还会打印出要出列的节点的编号。最后输出的结果即为正确的出列顺序。
阅读全文