用循环队列实现约瑟夫环.ppt

用循环队列实现约瑟夫环;设计思路;时间复杂度：;typedef int QElemType ; typedef int status; #define Error -1 #define OK 0 #define M 10 #define N 4 #define NULL 0; typedef struct Qnode { QElemType data; struct Qnode *next; }Qnode,*QueuePtr;; status InitQueue(LinkQueue *Q) { (*Q).front=(*Q).rear=(QueuePtr)malloc(sizeof(Qnode)); if(!(*Q).front) return Error; return OK; } status EnQueue(LinkQueue *Q,QElemType e) { QueuePtr p; p=(QueuePtr)malloc(sizeof(Qnode)); if(!p) return Error; p-data=e; p-next=NULL; (*Q).rear-next=p; (*Q).rear=p; return OK; }; status DeQueue(LinkQueue *Q,QElemType e) { QueuePtr p; if((*Q).front==(*Q).rear) return Error; p=(*Q).front-next; e=p-data; (*Q).front-next=p-next; if((*Q).rear==p) (*Q).rear=(*Q).front; free(p); return e; };void jesephu( LinkQueue *Q,int n,int i,int m,int A[]) { QElemType e; int j, k=0; InitQueue(Q); for(j=0;jn;j++) EnQueue(Q,j+1); for(j=1;ji;j++) { DeQueue(Q,e); EnQueue(Q,e); for(j=1;jm;j++) {DeQueue(Q,e); EnQueue(Q,e); } DeQueue(Q,e); A[k++]=e; } };void main() { int i,j=1,A[100]; QueuePtr p; int counter; LinkQueue Queue; InitQueue(Queue); for(i=0;iN;i++) EnQueue(Queue,i+1); jesephu(Queue,N,j,M,A); printf(please printf the queue:); for(i=0;i100;i++) printf(%4d,A[i]); }