打印本文 打印本文  关闭窗口 关闭窗口  
C++技巧：循环链表实现约瑟夫环
作者：佚名  文章来源：不详  点击数  更新时间：2008/10/22 21:33:34  文章录入：杜斌  责任编辑：杜斌
　　若有不足望请指出
　　#include<iostream>
　　#include<malloc.h>
　　#include<stdlib.h>
　　using namespace std;
　　#define OK 1
　　#define ERROR 0
　　#define MAXSIZE 10
　　typedef int Status;
　　typedef int ElemType;　　
　　typedef struct CircularList
　　{
　　ElemType data;
　　struct CircularList *next;
　　}CircularList,*LinkList;
　　Status Init_List(LinkList &L,int n) //建立无头结点单循环链表
　　{
　　if(n<1) return ERROR;
　　L=(LinkList)malloc(sizeof(CircularList));
　　L->data=1;
　　if(n==1) {L->next=L; return OK;}
　　int i;
　　LinkList p,q;
　　for(i=2;i<=n;i++)
　　{
　　p=(LinkList)malloc(sizeof(CircularList)) ;
　　p->data=i;
　　if(i==2) {L->next=p; q=p;}
　　else {q->next=p;q=p;}
　　}
　　p->next=L;
　　return OK;
　　}
　　Status Delete_List(LinkList &L) //删除L的下一节点
　　{
　　LinkList p=L->next;
　　if(p==L) return ERROR;
　　L->next=p->next;
　　free(p);
　　return OK; }
　　void JOSEPHUS(int n,int k,int m)
　　{//n为总人数，k为第一个开始报数的人，m为出列者喊到的数
　　LinkList L;
　　Init_List(L,n);
　　for(int i=1;i<k;i++)
　　L=L->next;
　　int flag=1;
　　while(flag)
　　{
　　for(int i=1;i<m-1;i++)
　　L=L->next;
　　flag=Delete_List(L);
　　L=L->next;
　　}
　　cout<<"The end:"<<L->data<<endl;
　　}
　　int main()
　　{
　　int n,k,m;
　　while(cin>>n>>k>>m)
　　JOSEPHUS(n,k,m);
　　return 0;}
　　1 1 1
　　The end:1
　　5 2 3
　　The end:5
　　8 5 3
　　The end:3
　　8 1 3
　　The end:7 www.Ｅxamda.CoM
打印本文 打印本文  关闭窗口 关闭窗口