約瑟夫環問題--循環連結清單

問題描述：設有編号為1，2，……，n的n(n>0)個人圍成一個圈，每人手中持有一個密碼（正整數）。一開始給定一個m 值，從第1個人開始報數，報到m時停止報數，報m的人出圈，将他手中的密碼作為新的m 值。再從他的下一個人起重新報數，報到m時停止報數，報m的出圈，……，如此下去，直到所有人全部出圈為止。當任意給定n和m後，設計算法求n個人出圈的次序。

問題分析：因為問題還是比較簡單的，是以給出以下連結：約瑟夫環問題

實作代碼：

#include<stdio.h>
#include<stdlib.h>
typedef struct Link{
    int data;
    int passwd ;
    struct Link *next;
}LinkList ;

LinkList* creat(int n)   //  特殊情況；n == 1 
{
    LinkList  *head,*rear, *new ;
    int i ;
    head=rear=(LinkList *)malloc(sizeof(LinkList));
    head->next =NULL;
    for(i=  ;i< n;i++)
    {
        new=(LinkList *)malloc(sizeof(LinkList));
        new->data = i+;
        printf("請輸入第%d 個人的密碼：",new->data);
        scanf("%d",&new->passwd);
        new->next = NULL ;
        rear->next = new ;
        rear = new ;
    }
    rear->next = head->next ;
    return rear ;
}
LinkList *fun(LinkList *rear ,int n)
{
    LinkList  *temp, *new_head , *new_rear  ;
    int i ;
    int t= n ;
    new_head =  new_rear = (LinkList *)malloc(sizeof(LinkList));
    new_head->next = NULL ;
    while(rear != rear->next)   //核心要點
    {
        for(i=  ;i< t -  ;i++)
            rear= rear->next ;
        temp = rear->next ;   //要删除的就是rear 的下一個節點
        rear->next = temp->next ;
        temp->next = NULL ;
        t = temp->passwd;  //當passwd == 0 時，直接會删除rear 的下一個節點，符合邏輯，保留
        new_rear->next = temp ;
        new_rear = temp ;
        new_rear->next= NULL ;
    }
    new_rear->next = rear ;    //把最後剩的一個連到另一個連結清單的尾部
    new_rear = rear ;
    new_rear->next= NULL ;
    return new_head;
}

int print(LinkList *head2)
{
    LinkList *temp= head2->next ;
    while(temp)
    {
        printf("出對順序為：");
        printf("%d\n",temp->data);
        temp= temp->next ;
    }
    return ;

}
int main(void){  
    LinkList *rear ,*head2 ;
    int n ;
    printf("請輸入一共有多少個人：");
    scanf("%d",&n);
    rear = creat(n);
    head2 = fun(rear,) ;
    print(head2);
    return ;
}  
           

運作截圖：

在這個程式中，我們将m 初始化為3。可以通過畫圖得，出隊順序是正确的。