当前位置：首页 > article >正文

【PTA函数题】6-2 约瑟夫环之循环链表

article 2025/1/19 11:25:58

n个人围成一圈（编号依次为：0,1,2...n-1）,从第一个人开始报数，1，2，……数到m者出列，再从下一个开始重新报数，数到m者再出列……。
下面的程序中，用不带附加表头的循环单链表来模拟约瑟夫环，且只设指向最后一个元素的尾指针。算法的思想是，第一步，先将每个人的编号追加到一个通过尾指针标识的循环单链表中。第二步，从首元素开始计数，数到m的取下这个元素，并追加到另一个用尾指针标识的循环单链表中……直到全部元素都取下。第三步，输出最后建立的循环单链表。请编写函数，完成第三步工作：输出通过尾指针标识的循环单链的全部元素。

函数接口说明：

void show(struct Node *r);//show data

其中r是指针，指向无附加表头的循环单链表的最后一个结点。

输入样例：

输入两个整数，以空格分隔，前者表示人总人数，后者表示计数的标准（数到几出列）。

9 4

输出样例：

按出列顺序依次打印每个人的编号于一对[]中，以逗号分隔。第一行是加入前：空的，第二行是加入后的出列顺序。

[]
[3,7,2,8,5,4,6,1,0]

裁判测试程序样例：

#include <stdio.h>
#include <stdlib.h>
struct Node{
    int data;
    struct Node *next;
};
void show(struct Node *r);//show data    需要完成的函数

int main(){
    int n,m;scanf("%d%d",&n,&m);
    struct Node *p=fun(n,m));//创建按出列顺序排列的循环单链表，返回指向尾元素的指针：测试程序提供
    show(p);//调用显示函数显示数据   该函数需要编程完成
    return 0;
}
/* 请在这里填写答案 */

代码呈现

//C语言
void show(struct Node* r) 
{
    // 显示循环单链表的全部元素
    
    if (r == NULL) 
    { // 如果链表为空
        printf("[]\n"); // 打印空列表
        return;
    }
    
    struct Node* p = r->next; // 创建指针p指向链表的第一个节点
    
    printf("["); // 打印左括号，表示列表的开始
    
    while (p != r) 
    { // 当指针p没有回到头节点时，进行循环遍历
        printf("%d,", p->data); // 打印当前节点的数据，并加上逗号
        p = p->next; // 将指针p指向下一个节点
    }
    
    printf("%d]\n", p->data); // 打印最后一个节点的数据，并加上右括号，表示列表的结束
}