约瑟夫环

// 约瑟夫环的循环链表实现  

#include

#include

#define LENGTH sizeof(MEN)

struct men  

{

     int   number;   //人数

int   code;     //密码

struct men *next;

};

typedef struct men MEN;                                           

int main(int argc, char *argv[])

{

MEN  *pOne = NULL, *pTwo = NULL, *pHead = NULL;

int  client;

int  NUMBER = 13;  //设置默认的人数 

int  NEXT = 3;     //选出的人数间隔的初始间隔数

     //  输入人数

printf("请输入游戏的人数:");

scanf("%d", &NUMBER);

     

/****创建环形链表****/

     pHead = pOne = pTwo = (MEN *)malloc(LENGTH);

     if (pHead == NULL)

{

printf("头结点空间分配出错!\n");

return EXIT_FAILURE;

}

// 初始这个链表，对头结点进行赋值

     pHead->number = 1;

printf("请输入第1位的密码:");

scanf("%d", &pHead->code);

for (client = 2; client <= NUMBER; client++)

{

pOne = (MEN *)malloc(LENGTH);

if(pOne == NULL)

{

printf("空间分配出错!\n");

return EXIT_FAILURE;

}

pOne->number = client;

printf("请输入第%d位的密码:", client);

scanf("%d", &pOne->code);

pTwo->next = pOne;

pTwo = pOne;

}

pOne->next = pHead;

printf("\n被选出的次序:");

     // 进行操作

pTwo = pHead;

pOne = pTwo->next;

while(pOne->next != pTwo)

{

for(client = 0; client < NEXT - 2; client++)

{

pTwo = pOne;

pOne = pOne->next;

}

    pTwo->next = pOne->next;

         // 释放不用的结点

printf("%d ", pOne->number);

    NEXT = pOne->code;

pOne = NULL;

free(pOne);

  

pOne = pTwo->next;

pOne = pOne->next;

pTwo = pTwo->next;//保持初始状态

}

printf("%d", pTwo->number);

printf("\n最后留下的是:%d\n", pOne->number);

return EXIT_SUCCESS;

}