约瑟夫问题（各功能用菜单方式实现）数据结构

Question

问题遇到的现象和发生背景

编号为 1，2，… ，n 的n个人按顺时针方向围坐一圈，每人均持有一个密码(正整数)。游戏开始由系统随机产生一个正整数m（1~10之间），同时随机产生一个起始位置s（正整数），从第s人开始按顺时针方向开始顺序报数，报到m时停止报数。报m的人出列，获取出列人的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。要求做到：
1）出列结束时可以一次性完整输出所有出列人的信息。
2）出列结束时可以一次性逆序输出出列人的信息。
3）在出列过程中随时可以查询某人是否已经出列。
4）在出列过程中随时可以查询已经出列的人数。

Answer 1

参考代码如下：

#define ERROR 0
#define OK 1
#include <stdio.h>
#include <stdlib.h>
struct CirNode /*定义每个结点的类型 */
{
    int data; /*每个人所拥有的密码*/
    int num;  /*每个人在圈中的位序*/
    struct CirNode *next;
};
int a[30];                        /*人数要求≤30 */
struct CirNode *CreateList(int n) /*生成n个结点的单向循环链表 */
{
    struct CirNode *L, *p, *q;
    int i;
    int j = 1;
    L = q = (struct CirNode *)malloc(sizeof(struct CirNode)); /*建立一个不带头结点的单向循环链表 */
    if (!q)
        return ERROR;
    printf("shu ru mei ge ren de mi ma:\n");
    q->num = j;
    printf("%d.data=", j);
    scanf("%d", &q->data);
    j++;
    q->next = L;
    for (i = 1; i < n; i++)
    {
        p = (struct CirNode *)malloc(sizeof(struct CirNode));
        printf("shu ru mei ge ren de mi ma:\n");
        p->num = j;
        printf("%d.data=", j);
        scanf("%d", &p->data);
        j++;
        q->next = p;
        p->next = L;
        q = q->next;
    } /*for*/
    return (L);
} /*Create*/
struct CirNode *DeleteList(struct CirNode *L, int m, int n) /*报m的人出列*/
{
    int i, j = 0;
    int k = n;
    struct CirNode *p, *q, *pre;
    pre = p = L;
    do
    {
        i = 1;
        while (i < m - 1)
        {
            p = p->next;
            i++;
        }
        if (m == 1)
        {
            while (pre->next != p)
                pre = pre->next;
            m = p->data;   /*得到新的密码 */
            a[j] = p->num; /*得到出列人的序号 */
            q = p;
            pre->next = p->next;
            p = p->next;
            free(q);
            L = pre = p; /*让新的报1的人作为头结点 */
            k--;
            j++;
        } /*if */
        else
        {
            q = p->next;
            m = q->data;
            a[j] = q->num;
            p->next = q->next;
            p = q->next;
            free(q);
            L = pre = p;
            k--;
            j++;
        } /*else*/
    } while (k > 1);
    a[j] = p->num; /*最后一个出列人的序号 */
    printf("xian zai suo you ren chu lie.\n");
    return (L);
} /*DeleteList*/
int main()
{
    struct CirNode *L;
    int i, n, m;
    printf("======This is a Joseph problem======\n");
    printf("qing shu ru ren shu,n=");
    scanf("%d", &n);
    if (n > 30 || n < 1)
    {
        printf("ERROR! Please input again,n=");
        scanf("%d", &n);
    } /*if*/
    L = CreateList(n);
    printf("Please input the first code,m=");
    scanf("%d", &m);
    if (m < 1)
    {
        printf("ERROR! Please input again,m=");
        scanf("%d", &m);
    } /*if */
    DeleteList(L, m, n);
    printf("chu dui ren de shun xu31:\n");
    for (i = 0; i < n; i++)
        printf("%d ", a[i]);
    printf("\n");
    return 0;
}

如有帮助，请点击我的回答下方的【采纳该答案】按钮帮忙采纳下，谢谢!