n个人围成一圈，从第1个人开始顺序报号1、2、....k。凡报到k者推出圈子。找出最后留在圈子中的人原来的序号。本题要求用链表实现。n<50,k<50。

这是一个经典的约瑟夫问题。可以使用循环链表来实现，即将n个人的编号存入循环链表中，然后依次从头节点开始报数，每报到第k个人就将其从链表中删除，直到链表中仅剩一个节点，即为最后留在圈子中的人。

具体实现步骤如下：

1. 定义一个结构体Node，表示链表中的节点，包含成员变量编号和指向下一个节点的指针。

2. 构造循环链表，将n个人的编号存入链表中。

3. 定义一个指针p，指向链表的头节点，从头节点开始报数。

4. 使用循环遍历链表，每次将指针p向后移动k-1个节点，然后将下一个节点从链表中删除。

5. 循环执行步骤4，直到链表中仅剩一个节点。

6. 返回链表中剩余节点的编号，即为最后留在圈子中的人原来的序号。

以下是一个C++实现示例代码：

相关问题

C语言n个人围成一圈，从第1个人开始顺序报号1、2、....k。凡报到k者推出圈子。找出最后留在圈子中的人原来的序号。本题要求用链表实现

好的，这是一道经典的约瑟夫环问题，可以使用循环链表来实现。

首先，我们需要定义一个链表结构体，用来表示每个人：

typedef struct node {
    int num;
    struct node *next;
} Node;

其中，num表示该人的编号，next表示指向下一个人的指针。接下来，我们需要先构建一个循环链表，将所有人的编号依次添加到链表中：

int n, k; // n表示总人数，k表示报数为k的人出圈
Node *head, *tail;

void create_list() {
    head = tail = (Node*)malloc(sizeof(Node)); // 创建头结点
    head->num = 1;
    for (int i = 2; i <= n; i++) {
        Node *p = (Node*)malloc(sizeof(Node));
        p->num = i;
        tail->next = p;
        tail = p;
    }
    tail->next = head; // 将尾结点指向头结点，形成循环链表
}

接下来，我们需要对链表进行遍历，每次找到第k个人，将其从链表中删除。直到链表中只剩下一个人为止：

void josephus() {
    Node *p = head, *q = tail;
    while (p != q) { // 只剩下一个人时退出循环
        for (int i = 1; i < k; i++) { // 找到第k个人
            q = p;
            p = p->next;
        }
        q->next = p->next; // 将该人从链表中删除
        free(p);
        p = q->next;
    }
    printf("%d", p->num); // 输出最后留下的人的编号
}

最后，完整代码如下：

#include <stdio.h>
#include <stdlib.h>

typedef struct node {
    int num;
    struct node *next;
} Node;

int n, k;
Node *head, *tail;

void create_list() {
    head = tail = (Node*)malloc(sizeof(Node)); // 创建头结点
    head->num = 1;
    for (int i = 2; i <= n; i++) {
        Node *p = (Node*)malloc(sizeof(Node));
        p->num = i;
        tail->next = p;
        tail = p;
    }
    tail->next = head; // 将尾结点指向头结点，形成循环链表
}

void josephus() {
    Node *p = head, *q = tail;
    while (p != q) { // 只剩下一个人时退出循环
        for (int i = 1; i < k; i++) { // 找到第k个人
            q = p;
            p = p->next;
        }
        q->next = p->next; // 将该人从链表中删除
        free(p);
        p = q->next;
    }
    printf("%d", p->num); // 输出最后留下的人的编号
}

int main() {
    scanf("%d%d", &n, &k);
    create_list();
    josephus();
    return 0;
}

ptaC语言链表n个人围成一圈，从第1个人开始顺序报号1、2、....k。凡报到k者推出圈子。找出最后留在圈子中的人原来的序号。本题要求用链表实现。n<50,k<50。

以下是一个C语言实现示例代码：

#include <stdio.h>
#include <stdlib.h>

// 定义链表节点结构体
typedef struct Node {
    int num;  // 编号
    struct Node *next;  // 指向下一个节点的指针
} Node;

// 构造循环链表
Node *createList(int n) {
    Node *head = NULL;
    Node *tail = NULL;
    for (int i = 1; i <= n; i++) {
        Node *p = (Node*)malloc(sizeof(Node));
        p->num = i;
        if (head == NULL) {
            head = p;
        } else {
            tail->next = p;
        }
        tail = p;
    }
    tail->next = head;  // 将尾节点指向头节点，形成循环链表
    return head;
}

// 删除指定节点，并返回下一个节点的指针
Node *deleteNode(Node *p) {
    Node *next = p->next;
    p->num = next->num;  // 将下一个节点的编号复制到当前节点
    p->next = next->next;  // 将当前节点的指针指向下下个节点，跳过中间的节点
    free(next);  // 释放中间节点的内存
    return p->next;  // 返回下一个节点的指针
}

// 主函数
int main() {
    int n, k;
    printf("请输入n和k：");
    scanf("%d %d", &n, &k);

    // 构造循环链表
    Node *head = createList(n);

    // 报数并删除节点，直到链表中仅剩一个节点
    Node *p = head;
    while (p->next != p) {
        for (int i = 1; i < k; i++) {
            p = p->next;
        }
        p = deleteNode(p);
    }

    // 输出最后留在圈子中的人原来的序号
    printf("最后留在圈子中的人原来的序号是：%d\n", p->num);

    return 0;
}

该代码使用循环链表实现了约瑟夫问题的求解，时间复杂度为O(nk)，空间复杂度为O(n)。