循环链表，数组标志位，静态链表。

    1. #include <stdio.h>
    2. #include <stdlib.h>
    3. /*循环链表实现约瑟夫环问题*/
    4. /*
    5. typedef struct node {
    6.     int data;
    7.     struct node* next;
    8. }Node,*Link;  //定义结构体链表
    9. void  displayMonkey(); //定义显示猴子编号函数
    10. int n, m, i;  //n表示猴子数量 m表示从1开始报到的数并退出
    11. int count; //报数记录
    12. count = 1;
    13. int main(void)
    14. {
    15.     Link head;
    16.     Link flag;
    17.     Link p, q;
    18.     head = (Link)malloc(sizeof(struct node));
    19.     flag = head;
    20.     printf("请输入（猴子个数，报到的数）\n");
    21.     scanf_s("%d,%d", &n, &m);
    22.     fflush(stdin);
    23.     for (i = 1; i <= n; i++)   //尾插法 插入猴子 使链表 猴子编号 从小到大输出
    24.     {
    25.         flag->next = (Link)malloc(sizeof(struct node));
    26.         flag->next->data = i;
    27.         flag = flag->next;
    28.     }
    29.     flag->next = head->next; //构建循环链表，使尾指针的下一个节点指向头指针的下一个节点
    30.     q = flag; //初始化后指针
    31.     p = head->next; //初始化前指针
    32.     displayMonkey(head);
    33.     free(head);  //释放头指针内存
    34.     while (n > 1)
    35.     {
    36.         //p指针为报到的数的位置，如果没到m则前后指针向后挪一位
    37.         if (count != m) {
    38.             q = p;
    39.             p = p->next;
    40.             ++count;
    41.         }
    42.         //p=m， 讲q指向p的后移位。并释放p。
    43.         else {
    44.             q->next = p->next;    //这条需注意不是 q=p->next
    45.             free(p);
    46.             p = q->next;         //这条需注意
    47.             n--;
    48.             count = 1;
    49.         }
    50.     }
    51.     printf("剩下的猴子编号为：%d",p->data);
    52.     free(q);free(p);
    53.     return 0;
    54. }
    55. void displayMonkey(Link head) {
    56.     for (i = 1; i <= n; i++)
    57.     {
    58.         head = head->next;
    59.         printf("猴子编号:%d", head->data);
    60.         printf("\n");
    61.     }
    62.     return 0;
    63. }*/
    64. /*数组标志位实现方式*/
    65. /*
    66. int main(void) {
    67.     int pos, count, n, m,i,number;
    68.     int mon[301] = { 0 };
    69.     printf("请输入  猴子个数,报到的数  --  输入 0,0  结束程序\n");
    70.     while (~scanf_s("%d,%d", &n, &m))
    71.     {
    72.         if (n == 0 || m == 0)
    73.         {
    74.             return 0;
    75.         }
    76.         for (i = 0; i < n; i++)
    77.         {
    78.             mon[i] = i + 1;
    79.             printf("猴子编号:%d\n", mon[i]);
    80.         }
    81.         number = n;
    82.         pos = 0;
    83.         count = 1;
    84.         while (number > 1)
    85.         {
    86.             if (mon[pos] > 0)
    87.             {
    88.                 if (count == m)
    89.                 {
    90.                     mon[pos] = 0;
    91.                     number--;
    92.                     count = 1;
    93.                     pos = (pos + 1) % n;
    94.                 }
    95.                 else
    96.                 {
    97.                     count++;
    98.                     pos = (pos + 1) % n;
    99.                 }
    100.             }
    101.             else
    102.             {
    103.                 pos = (pos + 1) % n;
    104.             }
    106.         }
    107.         for (i = 0; i < n; i++)
    108.         {
    109.             if (mon[i] > 0) {
    110.                 printf("最后的猴子编号:%d\n", mon[i]);
    111.             }
    112.         }
    113.     }
    114.     return 0;
    115. }
    116. */
    117. /*静态链表实现方法*/
    118. #define MAXSIZE 301
    119. #define status int
    120. #define OK 1
    122. typedef struct MonList{
    123.     int MonkN;
    124.     int cur;
    125. }StaticLinkList[MAXSIZE];
    126. status InitList(StaticLinkList space);
    127. status MonkeyList(StaticLinkList space,int i);
    128. status ListDelete(StaticLinkList space,int pos);
    129. status DisplayList(StaticLinkList space);
    130. void Free_SSL(StaticLinkList space, int k);
    131. int Malloc_SLL(StaticLinkList space);
    132. int ListLenghth(StaticLinkList space);
    133. int n, m;
    134. int main(void) {
    135.     int i;
    136.     int number,count;
    137.     count = 1;
    138.     StaticLinkList MokeyList;
    139.     printf("请输入  猴子个数,报到的数  --  输入 0,0  结束程序\n");
    140.     while (~scanf_s("%d,%d", &n, &m))
    141.     {
    142.         fflush(stdin);
    143.         number = n;
    144.         if (n == 0 || m == 0)
    145.         {
    146.             return 0;
    147.         }
    148.         InitList(MokeyList);
    149.         MonkeyList(MokeyList,n);
    150.         DisplayList(MokeyList);
    151.         int pos; 
    152.         pos = 1;
    153.         while (number > 1)
    154.         {
    155.             if (MokeyList[pos].MonkN > 0)
    156.             {
    157.                 if (count == m)
    158.                 {
    159.                     ListDelete(MokeyList,pos);
    160.                     number --;
    161.                     count = 1;
    162.                     pos = MokeyList[pos].cur;
    163.                 }
    164.                 else
    165.                 {
    166.                     pos = MokeyList[pos].cur;
    167.                     count++;
    168.                 }
    169.             }
    170.             else {
    171.                 pos = MokeyList[pos].cur;
    172.             }
    173.         }
    174.         int i;
    175.         for (i = 1; i <= n; i++)
    176.         {
    177.             if (MokeyList[i].MonkN != 0)
    178.             {
    179.                 printf("最后的猴子编号:%d\n", MokeyList[i].MonkN);
    180.             }
    181.         }
    182.         for (i = n; i >= 1; i--) {
    183.             Free_SSL(MokeyList, i);
    184.         }
    186.     }
    187.     return 0;
    188. }
    189. status InitList(StaticLinkList space) {
    190.     int i;
    191.     for (i = 0; i < MAXSIZE - 1; i++) space[i].cur = i + 1;
    192.     space[MAXSIZE].cur = 0;
    193.     return OK;
    194. }
    195. status MonkeyList(StaticLinkList space, int n) {
    196.     int j;
    197.     for (j = Malloc_SLL(space); j < n; j++)
    198.     {
    199.         space[j].MonkN = j;
    200.     }
    201.     space[j].MonkN = j;
    202.     if (j == n)
    203.     {
    204.         space[j].cur = 1;
    205.     }
    206.     return 1;
    207. }
    208. status ListDelete(StaticLinkList space, int pos) {
    209.     space[pos].MonkN = 0;
    210. }
    211. status DisplayList(StaticLinkList space) {
    212.     int i = 1;
    213.     for (i = i; i <= n; i++)
    214.         printf("猴子编号：%d\n",space[i].MonkN);
    215. }
    216. int Malloc_SLL(StaticLinkList space) {
    217.     int i = space[0].cur;
    218.     if (space[0].cur)
    219.         space[0].cur = space[i].cur;
    220.     return i;
    221. }
    222. void Free_SSL(StaticLinkList space, int k){
    223.     space[k].cur = space[0].cur;
    224.     space[0].cur = k;
    225. }