n个人围成一圈(编号依次为:0,1,2...n-1),从第一个人开始报数,1,2,……数到m者出列,再从下一个开始重新报数,数到m者再出列……。 下面的程序中,用不带附加表头的循环单链表来模拟约瑟夫环,且只设指向最后一个元素的尾指针。算法的思想是,第一步,先将每个人的编号追加到一个通过尾指针标识的循环单链表中。第二步,从首元素开始计数,数到m的取下这个元素,并追加到另一个用尾指针标识的循环单链表中……直到全部元素都取下。第三步,输出最后建立的循环单链表。请编写函数,完成第三步工作:输出通过尾指针标识的循环单链的全部元素。c语言
时间: 2024-03-17 09:46:15 浏览: 60
yuesefuhuan.zip_K.
好的,我可以为您提供 C 语言的代码实现。假设我们已经完成了前两步工作,即将每个人的编号追加到循环单链表中,并不断取下元素,将其追加到另一个循环单链表中。现在,我们需要编写一个函数来输出最后建立的循环单链表。
首先,我们需要一个 Node 结构体来表示链表中的节点:
```
typedef struct node {
int data;
struct node *next;
} Node;
```
其中,data 表示节点存储的数据(即人的编号),next 表示指向下一个节点的指针。接下来,我们可以定义一个函数,通过尾指针遍历循环单链表,并输出每个节点的值:
```
void output_list(Node *last) {
Node *p = last->next;
while (p != last) {
printf("%d ", p->data);
p = p->next;
}
printf("%d\n", p->data);
}
```
在这个函数中,我们首先将指针 p 指向循环单链表的第一个节点。然后,使用一个 while 循环来遍历链表,当 p 指向尾节点时跳出循环。在循环中,我们输出当前节点的值,然后将指针 p 指向下一个节点。最后,我们再输出一次尾节点的值,即可完成输出循环单链表的工作。
完整代码如下:
```
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
int data;
struct node *next;
} Node;
void output_list(Node *last) {
Node *p = last->next;
while (p != last) {
printf("%d ", p->data);
p = p->next;
}
printf("%d\n", p->data);
}
int main() {
int n, m, i;
Node *last1, *last2, *p, *q;
printf("请输入总人数 n 和报数 m:\n");
scanf("%d%d", &n, &m);
// 创建循环单链表
last1 = (Node *)malloc(sizeof(Node));
last2 = (Node *)malloc(sizeof(Node));
last1->data = 0;
last2->data = -1;
last1->next = last2;
last2->next = last1;
p = last1;
for (i = 1; i < n; i++) {
q = (Node *)malloc(sizeof(Node));
q->data = i;
p->next = q;
p = q;
}
p->next = last1;
// 取下元素,建立新链表
p = last1;
while (p->next != p) {
for (i = 1; i < m; i++) {
q = p;
p = p->next;
}
q->next = p->next;
p->next = last2->next;
last2->next = p;
p = q->next;
}
// 输出最后建立的循环单链表
output_list(last2);
return 0;
}
```
希望能够解答您的问题。
阅读全文