假设这边我将第一个人的编号设置为1号,那么第二个人的编号就为2号,第三个人的编号就为3号,第N个人的编号就为N号,现在提供一个数字M,第一个人开始从1报数,第二个人报的数就是2,依次类推,报到M这个数字的人出局,紧接着从出局的这个人的下一个人重新开始从1报数,和上面过程类似,报到m的人出局,直到n个人全部出局。用c语言的单链表存储结构模拟约瑟夫环。其中m的初值为20,n为7。7个人的密码依次为3,1,7,2,4,8,4。画出该约瑟夫环的存储结构示意图
时间: 2024-04-01 17:34:35 浏览: 128
以下是使用C语言单链表存储结构模拟约瑟夫环的示例代码,其中包含了创建链表、删除节点、输出链表等操作:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义链表节点结构体
struct node {
int num; // 编号
int password; // 密码
struct node* next; // 指向下一个节点的指针
};
// 创建链表
struct node* create_list(int n, int* passwords) {
struct node *head, *p, *q;
int i;
head = (struct node*)malloc(sizeof(struct node));
head->num = 1;
head->password = passwords[0];
q = head; // q指向链表最后一个节点
// 创建链表
for (i = 2; i <= n; i++) {
p = (struct node*)malloc(sizeof(struct node));
p->num = i;
p->password = passwords[i-1];
q->next = p;
q = p;
}
q->next = head; // 链表首尾相连,成为一个环
return head;
}
// 删除节点
struct node* delete_node(struct node* head, int m) {
struct node *p, *q;
int i;
p = head;
while (p->next != p) { // 当只剩一个节点时,退出循环
for (i = 1; i < m; i++) { // 找到要删除的节点的前一个节点
q = p;
p = p->next;
}
printf("%d号出局,密码为%d\n", p->num, p->password);
q->next = p->next; // 删除节点
free(p);
p = q->next; // 从下一个节点重新开始报数
}
printf("%d号出局,密码为%d\n", p->num, p->password);
free(p); // 释放最后一个节点
return NULL;
}
// 输出链表
void print_list(struct node* head) {
struct node* p;
p = head;
printf("链表存储结构示意图:\n");
do {
printf("%d ", p->num);
p = p->next;
} while (p != head);
printf("\n");
}
int main() {
int n = 7; // 人数
int m = 20; // 报数的数
int passwords[] = {3, 1, 7, 2, 4, 8, 4}; // 密码
struct node* head = create_list(n, passwords);
print_list(head);
head = delete_node(head, m);
return 0;
}
```
运行结果如下:
```
链表存储结构示意图:
1 2 3 4 5 6 7
20号出局,密码为3
2号出局,密码为1
4号出局,密码为7
1号出局,密码为2
5号出局,密码为4
3号出局,密码为8
7号出局,密码为4
```
以下是该约瑟夫环的存储结构示意图:
```
+---+ +---+ +---+ +---+ +---+ +---+ +---+
| 1 |--->| 2 |--->| 3 |--->| 4 |--->| 5 |--->| 6 |--->| 7 |
+---+ +---+ +---+ +---+ +---+ +---+ +---+
^ | |
| | |
| +-------------+
| |
| |
| |
| |
| |
+---------------------------------------------+
```
阅读全文