循环链表

Word count: 832Reading time: 4 min

 2022/05/01 

双链表

约瑟夫环

问题描述

设有 n 个人围坐在圆桌周围，现从某个位置 k上的人开始报数，报数到 m 的人就站出来。下一个人，即原来的第 m+1 个位置上的人，又从 1 开始报数，再报数到 m 的人站出来。依次重复下去，直到全部的人都站出来为止。试设计一个程序求出这 n 个人的出列顺序。

要求一：采用循环链表解决。

要求二：可以使用模拟法，模拟循环链表。

要求三：可以不使用循环链表类的定义使用方式。

输入描述

输入只有一行且为用空格隔开的三个正整数 n,k,m其含义如上所述。

输出描述

共 n行，表示这 n 个人的出列顺序。

C++写法

struct Node{
    int data;
    Node *pnext;
};

int main(){
    int n,k,m;//有n个人，从k位上开始报数,报到m的人站出来
    int i;
    Node *p,*q,*head;
    cin>>n>>k>>m;

    Node *first=new Node;
    first->data=1;
    p=first;
    for(i=2;i<=n;i++){
        q=new Node;
        q->data=i;

        p->pnext=q;//p节点指向q节点
        p=p->pnext;//p=q;
    }
    p->pnext=first;//末尾指向开头 
    //相当于 q->pnext=first

    p=first;
    for(i=1;i<=k-1;i++){//寻找开始报数的地方//i<=k-1，循环k-1
        p=p->pnext;
    }

    while(p!=p->pnext){//只有一个元素的时候跳出循环
        for(i=1;i<m-1;i++){//寻找出列的前一个元素，循环m-2次
            p=p->pnext;
        }
        q=p->pnext;//要出列的数
        cout<<q->data<<endl;
        p->pnext=q->pnext;//从链表中删除
        delete q;//从内存中删除
        
        p=p->pnext;//又从第一个开始报数
    }
    cout<<p->data<<endl;
    return 0;
}

java写法

import java.util.Scanner;

public class Main
{
    static class Node
    {
        int val;
        Node next;
        Node(int v)
        {
            val = v;
        }
    } //成员类，代表节点，类似于C++语言中的结构体

    public static void main(String[] args)
    {

        int N, M, K; //n个人从k位置开始报数，数到m出列

        Scanner input = new Scanner(System.in);

        N = input.nextInt();

        K = input.nextInt();
        M = input.nextInt();
        
     
        Node t = new Node(1); //头节点单列出来，方便形成循环链表
        Node x = t;

        for (int i = 2; i <= N; i++)
            x = (x.next = new Node(i)); //建立单向链表
        x.next = t;                     //最后一个节点的next指向第一个节点，形成循环链表

        for (int i = 1; i <= K - 1; i++) //寻找报数的起点
            x = x.next;

        while (x != x.next)
        { //只剩下一个结点的时候停止
            for (int i = 1; i < M; i++) {
                x = x.next;
                // System.out.print(x.val+" ");
            }
            //此时x是将出列的节点的前一个节点
            System.out.println(x.next.val + " ");
            x.next = x.next.next;
        }
        System.out.println(x.val);
       
    }
}

Python写法

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


def createLink(n):
    if n <= 0:
        return False
    if n == 1:
        return Node(1)
    else:
        root = Node(1)
        tmp = root
        for i in range(2, n + 1):
            tmp.next = Node(i)
            tmp = tmp.next
        tmp.next = root
        return root


if __name__ == '__main__':
    n, k, m = map(int, input().split())
     
    root = createLink(n)
    tmp = root

    for i in range(0, k - 1):
        tmp = tmp.next

    while tmp.next != tmp:
        for i in range(m - 2):
            tmp = tmp.next
        print(tmp.next.value, " ")
        tmp.next = tmp.next.next
        tmp = tmp.next

    print(tmp.value)

Author：yuyu

Link：http://example.com/2022/05/01/%E5%BE%AA%E7%8E%AF%E9%93%BE%E8%A1%A8/

Publish date：May 1st 2022, 1:02:46 am

Update date：May 1st 2022, 1:15:27 am

License：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可