循环链表解决约瑟夫环问题python 并实现一个完整的主程序

好的，以下是循环链表解决约瑟夫环问题的 Python 实现代码：

class Node:
    def __init__(self, data=None, next=None):
        self.data = data
        self.next = next

class CircularLinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        if not self.head:
            self.head = Node(data)
            self.head.next = self.head
        else:
            new_node = Node(data)
            cur = self.head
            while cur.next != self.head:
                cur = cur.next
            cur.next = new_node
            new_node.next = self.head

    def remove(self, key):
        if self.head.data == key:
            cur = self.head
            while cur.next != self.head:
                cur = cur.next
            cur.next = self.head.next
            self.head = self.head.next
        else:
            cur = self.head
            prev = None
            while cur.next != self.head:
                prev = cur
                cur = cur.next
                if cur.data == key:
                    prev.next = cur.next
                    cur = cur.next

    def __len__(self):
        cur = self.head
        count = 0
        while cur:
            count += 1
            cur = cur.next
            if cur == self.head:
                break
        return count

    def display(self):
        elems = []
        cur = self.head
        while cur:
            elems.append(cur.data)
            cur = cur.next
            if cur == self.head:
                break
        print(elems)

    def get_josephus_position(self, step):
        cur = self.head
        while len(self) > 1:
            count = 1
            while count != step:
                cur = cur.next
                count += 1
            print(f"Removed: {cur.data}")
            self.remove(cur.data)
            cur = cur.next
        return self.head.data

if __name__ == '__main__':
    cll = CircularLinkedList()
    n = int(input("Enter the number of people: "))
    k = int(input("Enter the steps to be skipped: "))
    for i in range(1, n+1):
        cll.append(i)
    cll.display()
    print(f"Josephus Position: {cll.get_josephus_position(k)}")

代码中定义了一个 `Node` 类和一个 `CircularLinkedList` 类。`Node` 类用于创建一个节点，而 `CircularLinkedList` 类用于创建循环链表并实现相关操作。具体来说，`CircularLinkedList` 类实现了以下方法：

- `append(data)`：在链表的末尾添加一个新的节点。
- `remove(key)`：删除链表中的节点。
- `__len__()`：返回链表的长度。
- `display()`：显示链表中的元素。
- `get_josephus_position(step)`：使用约瑟夫环算法获取最后一个幸存者的位置。

在 `main` 函数中，我们首先获取用户输入的总人数和步数。然后，我们使用 `for` 循环将数字从 1 到 n 添加到循环链表中。最后，我们调用 `get_josephus_position(step)` 方法来获取最后一个幸存者的位置，并将其打印出来。

希望能对你有所帮助！