XDOJ-278约瑟夫环

约瑟夫环

时间限制
2 S
内存限制
10000 Kb

问题描述

习题集P79。编号为1,2,…,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。现在给定一个随机数m>0，从编号为1的人开始，按顺时针方向1开始顺序报数，报到m时停止。报m的人出圈，同时留下他的密码作为新的m值，从他在顺时针方向上的下一个人开始，重新从1开始报数，如此下去，直至所有的人全部出圈为止。
问题输入
输入数据第一行为两个正整数n和m，分别表示人的个数及初始随机数，每组数据的第二行为n个整数，表示每个人持有的密码。
问题输出
用一行输出n个整数表示依次出圈人的编号，整数之间用空格分隔
输入样例
7 20
3 1 7 2 4 8 4

输出样例
6 1 4 7 2 3 5
提示
使用不带头节点的循环链表

思路

1. 创建一个单向循环链表Node，根据题目中的数据结构，在节点中创建密码data、序号num、下一节点的地址的变量next；
2. 对链表进行赋值。使用CreateList()和InitNode()函数，根据输入的数据进行存储密码。并且对每个节点进行标序号（从1开始，1，2，3，4……）；
3. 根据题意，创建DeleteNode()和Remove()函数。其中DeleteNode(Node *p)函数用来传入需要删除的节点的地址，遍历整个链表，达到删除该节点的目的。而Remove()则是根据题意，根据m之确定循环次数，循环链表结束后删除对应的节点。删除的同时打印该节点的序号。

测试数据：

第一组：

输入：

7 20

3 1 7 2 4 8 4

输出：

6 1 4 7 2 3 5

代码

#include <stdio.h>
#include <stdlib.h>
typedef struct Node
{
    int data;
    int num;
    struct Node *next;
} Node;
Node *InitNode(Node *p)
{
    p = (Node *)malloc(sizeof(Node));
    p->data = -1;
    p->num = -1;
    p->next = NULL;
    return p;
}
Node *CreateList(int n)
{
    Node *p;
    p = InitNode(p);
    Node *q = p;
    Node *head = p;
    for (int i = 0; i < n; i++)
    {
        if (p->next != NULL)
        {
            p = p->next;
        }
        scanf("%d", &p->data);
        p->num = i + 1;
        q = InitNode(q);
        p->next = q;
    }
    p->next = head;
    return head;
}
void DeleteNode(Node *p)
{
    Node *q = p;
    while (q->next != p)
    {
        q = q->next;
    }
    q->next = q->next->next;
}
void Remove(Node *head, int n, int m)
{
    Node *p = head;
    Node *q;
    int i, index = m;
    for (int j = 0; j < n; j++)
    {

        for (i = 0; i < index - 1; i++)
        {
            p = p->next;
        }
        printf("%d ", p->num);
        index = p->data;
        q = p;
        p = p->next;
        DeleteNode(q);
        free(q);
    }
}
int main()
{
    int m, n;
    scanf("%d%d", &n, &m);
    Node *head = CreateList(n);
    // for (int i = 0; i < n; i++)
    // {
    //     printf("%d %d %d\n", head->data, head->next, head->num);
    //     head = head->next;
    // }
    Remove(head, n, m);
    return 0;
}