约瑟夫环（循环单链表）

  1 #include <cstdio>
  2 #include <cstdlib>
  3 #include <iostream>
  4 using namespace std;
  5 
  6 const int maxn = 1000;
  7 int Num_of_Player;
  8 int m_val;
  9 int cnt;
 10 //循环链表
 11 typedef struct LNode
 12 {
 13     int num, password;
 14     struct LNode *next;
 15 }*linklist, lnode;
 16 
 17 void InitLinkList(linklist *L)
 18 {
 19     (*L) = (linklist)malloc(sizeof(lnode));
 20     (*L)->num = -1;
 21     (*L)->password = -1;
 22     (*L)->next = *L;
 23 }
 24 
 25 void ClearLinkList(linklist *L)
 26 {
 27     lnode *pos, *node;
 28 
 29     pos = (*L)->next;
 30     while(pos != (*L))
 31     {
 32         node = pos;
 33         pos = pos->next;
 34         free(node);
 35     }
 36     (*L)->next = (*L);
 37 }
 38 
 39 void CreatLinkList(linklist L)
 40 {
 41     lnode *u, *v;
 42     //清空链表
 43     ClearLinkList(&L);
 44     //初始化尾指针
 45     v = L;
 46     int j = 1, psw;
 47 
 48     printf("please input the number of the players: ");
 49     scanf("%d", &Num_of_Player);
 50     printf("
please input the passwords of the players: ");
 51     while(j <= Num_of_Player)
 52     {
 53         scanf("%d", &psw);
 54 /*----------------------插入新结点-------------------------------------*/
 55         u = (linklist)malloc(sizeof(lnode));     //分配一个节点head
 56         u->num = j;                              //为结点赋值
 57         u->password = psw;
 58         v->next = u;
 59         v = u;                                //更新尾结点
 60 /*---------------------------------------------------------------------*/
 61         j++;
 62     }
 63     v->next = L;
 64 }
 65 
 66 void DestoryLinkList(linklist L)
 67 {
 68     ClearLinkList(&L);//清空链表
 69     free(L);//销毁虚拟头结点
 70 }
 71 
 72 void solve(linklist L)
 73 {
 74     printf("please input the value of m: ");
 75     scanf("%d", &m_val);
 76 
 77     lnode *u, *v;
 78     v = L;
 79     int k = 0;
 80     while(v->next != v)
 81     {
 82         u = v;
 83         v = v->next;
 84 
 85         //注意：如果到了头部的虚拟结点，则再向后移一步
 86         if(v == L)
 87         {
 88             u = v;
 89             v = v->next;
 90         }
 91         k++;
 92 
 93         if(k == m_val)
 94         {
 95 //            cout << m_val << endl;
 96             //输出并释放掉第m个结点
 97             if(cnt) printf(" ");
 98             printf("%d", v->num);
 99             m_val = v->password;
100 /*----------------销毁第m个数-----------------*/
101             u->next = v->next;
102             lnode *tmp = v;
103             free(tmp);
104             v = u;
105 /*----------------销毁第m个数-----------------*/
106             k = 0;
107             cnt++;
108         }
109     }
110 }
111 
112 
113 int main()
114 {
115     linklist players;//开始“游戏”
116     InitLinkList(&players);//初始化“游戏人员”
117     CreatLinkList(players);//创建“游戏人员”
118     solve(players);//进行“游戏”
119     DestoryLinkList(players);//销毁“游戏人员”
120     return 0;
121 }