約瑟夫環_循環單連結清單

//
// Created by Admin on 2017/3/30.
//

#include <cstdio>
#include <malloc.h>

//定義結點
typedef struct node{
    int num;
    int pas;
    struct node *next;
}JosephNode;
typedef JosephNode *CircularList;

//初始化循環連結清單為空表
void InitList(CircularList &first){
    first=(JosephNode *)malloc(sizeof(JosephNode));
    first->next=first;
}


//存儲每個人的編号和密碼
void InputData(CircularList &first,int n){
    int temp;
    printf("請輸入每個人的密碼（以空格分隔）：");
    CircularList newnode,p=first;
    for (int i = 1; i <= n; ++i) {
        scanf("%d",&temp);
        newnode=(JosephNode *)malloc(sizeof(JosephNode));  //建立結點
        if(!newnode)exit(0);
        newnode->num=i; //存儲編号
        newnode->pas=temp;  //存儲出局密碼
        //插入到鍊尾
        p->next=newnode;
        p=newnode;
    }
    p->next=first;  //将鍊尾連接配接頭結點
}

//周遊連結清單
void TravelList(CircularList first){
    CircularList p=first->next;
    while(p!=first){
        printf("\tnum: %d\t\tpas: %d\n",p->num,p->pas);
        p=p->next;
    }
}//testing

//solve
void Solve(CircularList &first,int n,int m){
    CircularList p=first;
    int count=1; //count用于控制輸出格式
    while (n--){
        int i=1;  //i為計數器
        while(i<m){  //找到第m-1個結點
            if(p->next==first)p=p->next; //如果下一個結點為頭結點，則跳過頭結點，計數器不自增
            else{  //否則計數+1，并且指向下一個結點
                p=p->next;
                i++;
            }
        }//循環結束後，p為第m-1個結點

        if(p->next==first)p=p->next; //判斷下一個是否為頭結點，是則跳過頭結點
        printf("num= %d\t",p->next->num);  //輸出第m個結點的标号
        if(n==0)printf("\n\n\tThe Winner is : %d",p->next->num);
        else{
            if(count%5==0)printf("\n");
            count++;
        }
        m=p->next->pas;  //更新m值
        //删除第m個結點
        CircularList q=p->next;
        p->next=q->next;
        free(q);
    }
    printf("\n\n");
}

int main(){
    char op;
    int n,m;
    CircularList first;
    printf("輸入Y/y進入操作！\n");
    while (~scanf("%c",&op)){
        if(op=='n'||op=='N')break;
        else{
            system("cls");
            InitList(first);
            printf("請輸入參與人數：");
            scanf("%d",&n);
            printf("請輸入初始出局密碼：");
            scanf("%d",&m);
            InputData(first,n);
            printf("\n/****************testing*****************/\n");
            printf("/****************資料存儲****************/\n");
            TravelList(first);
            printf("\n/****************出列順序****************/\n");
            Solve(first,n,m);
        }
        printf("輸入Y/N,繼續操作：\n");
        getchar();
    }
    return 0;
}
           

特殊資料已測試