1 //////////////////////////////////////////////////////////////////////////////  2 // SqQueue.cpp  3 //  4 // author:Leetao  5 //////////////////////////////////////////////////////////////////////////////  6 // 简介：  7 //       约瑟夫环问题：设有编号为1，2，……，n的n(n>0)个人围成一个圈.  8 //从第1个人开始报数，报到sp时停止报数，报sp的人出圈，再从他的下一个人起重新报数，  9 //报到sp时停止报数，报sp的出圈，……，如此下去，直到所有人全部出圈为止.      10 ////////////////////////////////////////////////////////// /////////////////// 11 /** 12 *  13 * 14 * @author Leetao 15 * @version 1.0 16 * @date 2014.11.23  17 *//////////////////////////////////////////////////////////////////////////// 18 #include<stdio.h> 19 #include<malloc.h> 20  21 #define MAXQSIZE 100 //最大队列长度 22  23 typedef int QElem; 24 typedef int Status; 25  26 typedef struct  27 { 28     QElem *base;   //初始化的动态分配储存空间  29     int front;      //头指针  30     int rear;      //尾指针  31 } SqQueue; 32  33 //初始化队列 34 Status InitQueue(SqQueue &Q,int n) 35 { 36     Q.base=(QElem *)malloc((n+1)*sizeof(QElem));  37     if(Q.base==NULL)  //内存分配失败  38     { 39         printf("error!n"); 40     } 41     Q.front=Q.rear=0;  //空队列*很重要，之前一直报错，最后才发现 42      43     return 0; 44 }  45  46 //插入元素e为队尾元素  47 Status EnQueue(SqQueue &Q,int n,QElem e) 48 { 49     if((Q.rear+1)%(n+1)==Q.front)   50     { 51         printf("the queue is full already!\n");    52      53     } 54     Q.base[Q.rear]=e; 55 //    printf("%d ",Q.base[Q.rear]); 56     Q.rear=(Q.rear+1)%(n+1); 57      58     return 0;  59 }      60  61 //删除队列头元素,用e作返回值返回  62 Status DeQueue(SqQueue &Q,int n) 63 { 64     int e; 65     if(Q.front==Q.rear) 66     { 67         printf("error!\n"); 68     } 69     e=Q.base[Q.front]; 70     Q.front=(Q.front+1)%(n+1); 71      72     return e; 73 }  74  75 int main() 76 { 77     SqQueue Q; 78     int m,n,sp,k=0; 79      80     printf("enter the numbers of elements in the Joseph ring:\n"); 81     scanf("%d",&n); 82      83     printf("enter the starting position(1-%d):\n",n); 84     scanf("%d",&m); 85      86     printf("enter the number to stand up:\n"); 87     scanf("%d",&sp); 88      89     //初始化  90     InitQueue(Q,n); 91      92     for(int i=1;    i<=n;    i++)   //将n个人从1到n的编号放入队列中 93     { 94         EnQueue(Q,n,i); 95     } 96      97     for(int j=1;    j<m;    j++) 98     {     99         EnQueue(Q,n,DeQueue(Q,n));  //将起始位置变为头        100     }    101 102     printf("约瑟夫环得到序列为: \n");103         while(k<n)104         {105                 for(int j=1; j<sp; j++)106                 { 107                     EnQueue(Q, n, DeQueue(Q, n));  //数到sp，使数sp的人成为队列头108                 }109                 printf("%d ", DeQueue(Q,n)); //打印出队头及数到sp的人110                    111                k++;112         }113             printf("\n");114     return 0;115 }