用c语言写的循环链表约瑟夫环
时间: 2023-05-13 10:06:56 浏览: 69
循环链表约瑟夫环问题是一个经典的问题,可以用C语言来实现。以下是一个简单的C语言代码示例:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
int data;
struct node *next;
} Node;
Node *createList(int n) {
Node *head = NULL, *tail = NULL;
for (int i = 1; i <= n; i++) {
Node *newNode = (Node *)malloc(sizeof(Node));
newNode->data = i;
newNode->next = NULL;
if (head == NULL) {
head = tail = newNode;
} else {
tail
相关问题
使用C语言循环链表完成约瑟夫环问题
好的,约瑟夫环问题可以使用循环链表来解决。具体实现步骤如下:
1. 定义一个循环链表结构体,包括数据域和指向下一个节点的指针。
2. 根据参与游戏的人数n,创建一个含有n个节点的循环链表,并将它们连接成一个环形。
3. 定义一个指针p指向链表的头节点,并让它依次指向链表中每一个节点,直到p指向最后一个节点。
4. 定义一个计数器count,每次p指向下一个节点时,count加1。
5. 当count的值等于m时,将p指向的节点从链表中删除,并将count重置为0。
6. 重复执行步骤4和5,直到链表中只剩下一个节点为止,该节点即为游戏的胜者。
下面是C语言的实现代码:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
int data;
struct node* next;
} Node;
// 创建循环链表
Node* createCircularLinkedList(int n) {
Node* head = NULL, *p = NULL, *tail = NULL;
for (int i = 1; i <= n; i++) {
p = (Node*)malloc(sizeof(Node));
p->data = i;
if (i == 1) {
head = p;
} else {
tail->next = p;
}
tail = p;
}
tail->next = head;
return head;
}
// 在循环链表中删除节点
Node* deleteNode(Node* head, Node* p) {
if (head == NULL) {
return NULL;
}
if (p == head) {
head = head->next;
} else {
Node* q = head;
while (q->next != p) {
q = q->next;
}
q->next = p->next;
}
free(p);
return head;
}
// 约瑟夫环问题
void josephus(int n, int m) {
Node* head = createCircularLinkedList(n);
Node* p = head;
int count = 0;
while (p->next != p) {
count++;
if (count == m) {
printf("%d ", p->data);
head = deleteNode(head, p);
p = head;
count = 0;
} else {
p = p->next;
}
}
printf("%d\n", p->data);
free(p);
}
int main() {
int n = 5, m = 3;
josephus(n, m);
return 0;
}
```
以上代码实现了约瑟夫环问题的求解,其中createCircularLinkedList函数用于创建循环链表,deleteNode函数用于在循环链表中删除节点,josephus函数用于解决约瑟夫环问题。
c语言使用循环链表解决约瑟夫环问题
约瑟夫环问题是一个经典的数学问题,具体描述如下:有n个人(编号为1~n),围成一个圆圈,从第一个人开始报数,报到m的人出圈,然后从他的下一个人开始重新报数,重复这个过程,直到剩下最后一个人。
下面是使用循环链表解决约瑟夫环问题的C语言实现:
```
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
int num;
struct node *next;
} Node;
void create_circle(Node **head, int n) {
Node *tail = NULL, *p = NULL;
for (int i = 1; i <= n; i++) {
p = (Node *)malloc(sizeof(Node));
p->num = i;
if (*head == NULL) {
*head = p;
tail = p;
} else {
tail->next = p;
tail = p;
}
}
tail->next = *head; // 将尾节点指向头节点,形成循环链表
}
void josephus_circle(Node **head, int m) {
Node *p = *head, *q = NULL;
int count = 0;
while (p->next != p) {
count++;
if (count == m) {
q->next = p->next;
printf("%d出圈\n", p->num);
free(p);
p = q->next;
count = 0;
} else {
q = p;
p = p->next;
}
}
printf("剩下%d号\n", p->num);
*head = p;
}
int main() {
int n, m;
Node *head = NULL;
printf("请输入总人数n和报数m:");
scanf("%d%d", &n, &m);
create_circle(&head, n);
josephus_circle(&head, m);
return 0;
}
```
首先,使用 `create_circle` 函数创建一个有 n 个节点的循环链表,其中头节点指针保存在 `head` 变量中。
然后,使用 `josephus_circle` 函数来模拟约瑟夫环问题。使用两个指针 `p` 和 `q` 遍历循环链表, `count` 记录报数的次数。当 `count` 等于 `m` 时,删除节点 `p`,并输出其编号。否则,指针 `p` 和 `q` 向后移动。当循环链表中只剩下一个节点时,输出其编号并退出循环。
最后,将头节点指针 `head` 指向最后剩下的节点,返回其编号。