【出圈】 （C++代码）（典型的约瑟夫环——链表解决）

解题思路:

典型的约瑟夫环题




注意事项:

用C提交时就行了#include <cstdlib>

但是用C++提交需要#include <malloc.h>

说好的C++完全兼容C呢，，还是说这个OJ编译器的版本问题

参考代码:

#include <stdio.h>
#include <cstdlib>
#include <malloc.h>

struct Joseph {//约瑟夫环
    int number;
    struct Joseph *next;
};

struct Joseph *Create(int);//建立环链
void Out(struct Joseph *, int);//输出
struct Joseph *Delete(struct Joseph *, struct Joseph *);//删除节点

int main() {
    int m, n;
    struct Joseph *head = NULL;
    while (scanf("%d %d", &m, &n) != EOF) {
        head = Create(m);//建立环链
        Out(head, n);//输出
    }
    return 0;
}

struct Joseph *Create(int m) {//建立环链
    struct Joseph *head = NULL, *p = NULL, *q = NULL;
    p = (struct Joseph *) malloc(sizeof(struct Joseph));
    if (p == NULL) {
        printf("内存分配出错\n");
        exit(0);
    } else
        head = q = p;
    p->number = 1;
    for (int i = 2; i <= m; i++) {
        p = (struct Joseph *) malloc(sizeof(struct Joseph));
        if (p == NULL) {
            printf("内存分配出错\n");
            exit(0);
        }
        q->next = p;
        p->number = i;
        q = p;
    }
    q->next = head;
    return head;
}

void Out(struct Joseph *p, int n) {
    struct Joseph *q = NULL;
    while (p != p->next) {
        for (int i = 1; i < n; i++) {
            q = p;
            p = p->next;
        }
        p = Delete(p, q);//删除节点
    }
    printf("%d\n", p->number);
    free(p);
}

struct Joseph *Delete(struct Joseph *p, struct Joseph *q) {
    q->next = p->next;
    free(p);
    return q->next;
}