完善上述代码,要求利用单向循环链表存储结构模拟此过程,按照出列的顺序输出各个人的编号。m 的初值为 20,n=7,7 个人的密码依次为 3,1,7,2,4,7,4,首先 m=6。输入数据:建立输入函数处理输入的数据,输入m的初值n,输入每个人的密码,建立单向循环链表。输出形式:建立一个输出函数,将正确的出列顺序输出。
时间: 2024-03-12 17:49:59 浏览: 114
利用单向循环链表存储结构模拟约瑟夫问题,按照出列的顺序印出每个人的编号。
好的,根据您的需求,我修改了程序,使用单向循环链表存储结构,并增加了输入函数和输出函数,以便更好地模拟出队过程并输出正确的出队顺序。以下是修改后的程序:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
int id; // 编号
int password; // 密码
struct node* next; // 指向下一个节点的指针
} Node;
// 创建单向循环链表
Node* createCircleList(int n) {
Node* head = NULL; // 头节点指针
Node* tail = NULL; // 尾节点指针
int i;
for (i = 1; i <= n; i++) {
Node* p = (Node*) malloc(sizeof(Node)); // 创建新节点
p->id = i;
scanf("%d", &(p->password)); // 输入密码
p->next = NULL;
if (head == NULL) { // 第一个节点
head = tail = p;
} else { // 后续节点
tail->next = p;
tail = p;
}
}
tail->next = head; // 将尾节点指向头节点,形成单向循环链表
return head;
}
// 打印链表
void printList(Node* head) {
Node* p = head;
do {
printf("(%d, %d) ", p->id, p->password);
p = p->next;
} while (p != head);
printf("\n");
}
// 根据报数计算出下一个节点的指针
Node* getNextNode(Node* p, int m) {
int i;
for (i = 1; i < m; i++) {
p = p->next;
}
return p;
}
// 从单向循环链表中删除一个节点
void deleteNode(Node** head, Node* p) {
Node* pre = *head;
while (pre->next != p) {
pre = pre->next;
}
pre->next = p->next;
if (p == *head) { // 如果删除的是头节点,则需要更新头节点指针
*head = p->next;
}
free(p);
}
// 输出出列顺序
void printOrder(Node* head, int n, int m) {
int i;
Node* p = head;
for (i = 1; i <= n; i++) {
p = getNextNode(p, m); // 计算下一个节点
printf("%d ", p->id); // 输出要删除的节点的编号
deleteNode(&head, p); // 删除节点
}
}
// 主程序
int main() {
int n, m;
printf("请输入人数 n 和报数 m:");
scanf("%d%d", &n, &m);
Node* head = createCircleList(n); // 创建单向循环链表
printf("初始链表:");
printList(head); // 打印初始链表
printf("出列顺序:");
printOrder(head, n, m); // 输出出列顺序
printf("\n");
return 0;
}
```
程序的详细注释请参考代码。希望能对您有所帮助!
阅读全文