数据结构(c语言)用线性表实现约瑟夫问题,求求大佬帮我看看怎么实现

2025-03-06 05:32:19
推荐回答(1个)
回答1:

#include 
#include 
#include 
 
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
 
typedef int Status;
 
typedef int ElemType;
 
typedef struct LNode {
    ElemType data;
    struct LNode *next;
} LNode, *LinkList;
 
//解决约瑟夫问题
int yue (int m, int n) {
    //head指向不带头节点的循环单链表
    LinkList head = NULL, cur, p, q;
    int i, j;
     
    //生成第一个节点
    head = (LinkList) malloc (sizeof(LNode));
    head->data = 1;
    head->next = head;
     
    //使用尾插法按顺序生成节点
    p = head;
    for (i=1; i<=m; i++) {
        if (i==1) /* 首结点 */
            p->data = i; /* 向已存在的首结点写入编号 */
        else {
            q = (LinkList) malloc (sizeof(LNode)); /* 生成新结点 */
            if(!q) /* 内存分配失败 */
                exit (OVERFLOW);
            q->data = i; /* 为第i个人编号 */
            p->next = q; /* 将q链接到p之后,即表尾 */
            q->next = head; /* 将q链接到首结点之前 */
            p = p->next; /* p指向表尾 */
        }
    }
 
    //约瑟夫开始
    cur = head;
    printf ("出列顺序:");
    //循环m-1次
    for(i = 1; i < m; i++) {
        //每次循环开始计数
        for (j=1; j            cur = cur->next;
        q = cur->next; /* q指向p的后继结点,q即报到k之人 */
        cur->next = q->next; /* p的后继结点跨过q,指向q的后继结点 */
        printf("%d\t", q->data);
        if (q == head) /* q是首结点 */
            head = q->next; /* 移动首结点 */ 
        free (q); /* 删除q结点 */
         
        cur = cur->next; /* p指向下一个结点 */
        j--; /* 人数减一 */
    }
    putchar ('\n');
    //返回最后剩下的节点数据域,即为最后剩下的人
    return cur->data;
}
 
int main (void) {
    printf ("最后剩下的人:%d\n", yue (8, 3)); //8个人,报3者出列
    //运行结束后,需要销毁链表,此处略
    getch (); /* 屏幕暂留 */ 
    return 0 ;
}