数据结构约瑟夫环问题

img


要求有伪代码，图解，c语言程序(有清晰的注释)　
a）需求分析：在该部分中叙述每个模块的功能要求。　
b）概要设计：在此说明每个部分的算法设计说明（可以是描述算法的流程图），每个程序中使用的存储结构设计说明（如果指定存储结构请写出该存储结构的定义）。　
c）详细设计：各个算法实现的源程序，对每个题目要有相应的源程序（可以是一组源程序，每个功能模块采用不同的函数实现）。源程序要按照写程序的规则来编写。要结构清晰，重点函数的重点变量，重点功能部分要加上清晰的程序注释。　
d）调试分析：测试数据，测试输出的结果，时间复杂度分析，和每个模块设计和调试时存在问题的思考（问题是哪些？问题如何解决？），算法的改进设想。

仅供参考：

//假设有n个人团团围做，从第1个人开始数数，数到第m个人时候，第m个人出列，
//然后继续从1开始数数，数到第m个人退出
#include <stdio.h>
#include <conio.h>
int i,k,t;
int n,m;
static char f[1001];//0该座位未出圈,1该座位已出圈
void main() {
    while (1) {
        printf("Input n m(1000>=n>=m>=1):");
        fflush(stdout);
        rewind(stdin);
        if (2==scanf("%d%d",&n,&m)) {
            if (1000>=n && n>=m && m>=1) break;
        }
    }
    t=0;//已出圈总人数
    i=1;//座位编号
    k=1;//当前要数的数
    while (1) {
        if (0==f[i]) {
            if (m==k) {
                t++;
                f[i]=1;
                printf("%3d ",i);
                if (0==t%10) printf("\n");
                if (t>=n) break;
            }
            k++;if (k>m) k=1;
        }
        i++;if (i>n) i=1;
    }
    cprintf("Press any key ...");
    getch();
}

你好，这个用循环链表很简单就可以实现


 
#include <stdio.h>
#include <stdlib.h>
typedef struct Node
{
    int data;
    struct Node *next;
} node;
 
node *Creatlist(int n)
{
    node *l, *q, *p;
    l = (node *)malloc(sizeof(node));
    l->data = 1;
    l->next = l;
    q = l;
    for (int i = 2; i <= n; i++)
    {
        p = (node *)malloc(sizeof(node));
        q->next = p;
        p->data = i;
        p->next = q;
        q = p;
    }
    q->next = l;
 
    return l;
}
 
void yuesefu(node *l, int p)
{
    node *m, *n;
    m = n = l;
    int a = 1, data = l->data;
    while (m->next != m)
    {
        if (a == p)
        {
            printf("%d ", m->data);
            n->next = m->next;
            if (m->data == data) //重置头结点
            {
                l = m->next;
                data = l->data;
            }
            free(m);
            m = n->next;
            a = 1;
        }
        else
        {
            a++;
            n = m;
            m = m->next;
        }
    }
}
 
 
int main()
{
    int n, p;
    scanf("%d%d", &n, &p);
    node *l = Creatlist(n);
    // l = tou();
    // Creatlist(l, n);
    yuesefu(l, p);
 
    return 0;
}

带密码的约瑟夫环：

#include <stdio.h>
#include <stdlib.h>
typedef struct node{
    int number;
    int password;
    struct node * next;
}person;
person * initLink(int n){
    int password;
    person * head=(person*)malloc(sizeof(person));
    head->number=1;
    scanf("%d", &password);
    head->password=password;
    head->next=NULL;
    person * cyclic=head;
    for (int i=2; i<=n; i++) {
        person * body=(person*)malloc(sizeof(person));
        body->number=i;
        scanf("%d", &password);
        body->password=password;
        body->next=NULL;
        cyclic->next=body;
        cyclic=cyclic->next;
    }
    cyclic->next=head;//首尾相连
    return head;
}

void findAndKillK(person * head,int m){

    person * tail=head;
    //找到链表第一个结点的上一个结点，为删除操作做准备
    while (tail->next!=head) {
        tail=tail->next;
    }
    person * p=head;
    //从编号为k的人开始，只有符合p->next==p时，说明链表中除了p结点，所有编号都出列了，
    while (p->next!=p) {
        //找到从p报数1开始，报m的人，并且还要知道数m-1de人的位置tail，方便做删除操作。
        for (int i=1; i<m; i++) {
            tail=p;
            p=p->next;
        }
        tail->next=p->next;//从链表上将p结点摘下来
        printf("出列人的编号为:%d\n",p->number);
        m = p->password;
        free(p);
        p=tail->next;//继续使用p指针指向出列编号的下一个编号，游戏继续
    }
    printf("出列人的编号为:%d\n",p->number);
    free(p);
}

int main() {
    int n;
    int m;
    printf("输入圆桌上的人数n:");
    scanf("%d",&n);
    printf("输入初始m：");
    scanf("%d",&m);
    printf("输入各人密码：");
    person * head=initLink(n);
    findAndKillK(head, m);
    return 0;
}

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

img