学习循环链表，约瑟夫问题
循环链表——约瑟夫问题#include <iostream>
using namespace std;
typedef int ElemType;
typedef struct Node {
ElemType data;
struct Node *next;
} LinkNode, *LinkList;
// 初始化循环链表
bool InitList(LinkList &L) {
L = new LinkNode;
if (!L) {
return false;
}
L->next = L;
L->data = -1;
return true;
}
// 尾插法
bool insert_tail(LinkList &L, ElemType e) {
if (!L) {
return false;
}
LinkNode *p = L;
while (p->next != L) {
p = p->next;
}
LinkNode *s = new LinkNode;
if (!s) {
return false;
}
s->data = e;
s->next = p->next;
p->next = s;
return true;
}
void printList(const LinkList &L) {
if (!L) {
return;
}
LinkNode *p = L->next;
while (p != L) {
cout << p->data << " ";
p = p->next;
}
cout << endl;
}
bool Joseph(LinkList &L, int interval) {
if (!L || L->next == L) {
cout << "循环链表为空" << endl;
return false;
}
if (interval <= 0) {
cout << "间隔数必须大于0" << endl;
return false;
}
LinkNode *p = L->next, *pre=L; // p指向要删除的结点，pre指向要删除结点的前一个结点
int times = 0;
while (L->next != L) {
// 找到要删除的结点的前一个结点和要删除的结点
// 从1 开始计数，删除计数到interval 的结点，不包括头结点
for (int i = 1; i < interval; i++) {
pre = p;
p = p->next;
if (p == L) { // 跳过头结点计数
pre = p;
p = L->next;
}
}
pre->next = p->next;
LinkNode *temp = p;// 用temp 保存要删除的结点，删除
p = p->next;
times++;
cout << "第" << times << "次删除的元素为" << temp->data << endl;
delete temp;
if (p == L){//防止计数错误，当p指向头结点时，重新指向头结点的下一个结点
pre = p;
p = L->next;
}
printList(L);
}
return true;
}
int main() {
LinkList L;
// 1.初始化一个空的循环链表
if (!InitList(L)) {
exit(-1);
} else {
cout << "初始化成功" << endl;
}
// // 2.尾插法插入元素
// cout << "请输入要插入的元素,ctrl d结束" << endl;
// ElemType e;
// while (cin >> e) {
// insert_tail(L, e);
// }
// cin.clear();
for (int i = 1; i <= 10; i++) {
insert_tail(L, i);
}
cout << endl;
// // 3.打印循环链表
// printList(L);
// 约瑟夫环
Joseph(L, 9);
return 0;
}
循环链表是一种特殊的链表，其中最后一个节点的指针指向头节点，从而形成一个环状结构。约瑟夫问题是一个经典的数学应用问题：有 n 个人围成一圈，从第 k 个人开始报数，数到 m 的人出列，然后从下一个人继续报数，直到所有人出列。循环链表非常适合模拟这个过程。
在您提供的代码中，定义了一个循环链表结构，并实现了初始化、尾插法和打印功能。但约瑟夫问题的函数不完整。下面我将解释关键部分，并提供一个完整的约瑟夫问题实现。
首先，循环链表的基本操作：
- InitList：初始化链表，创建一个头节点并使其指向自身。
- insert_tail：使用尾插法在链表末尾添加新节点。
- printList：遍历并打印链表中的数据（跳过头节点）。
约瑟夫问题函数需要模拟报数出列的过程。以下是完整的实现：
#include <iostream>
using namespace std;
typedef int ElemType;
typedef struct Node {
ElemType data;
struct Node *next;
} LinkNode, *LinkList;
// 初始化循环链表
bool InitList(LinkList &L) {
L = new LinkNode;
if (!L) {
return false;
}
L->next = L;
L->data = -1;
return true;
}
// 尾插法
bool insert_tail(LinkList &L, ElemType e) {
if (!L) {
return false;
}
LinkNode *p = L;
while (p->next != L) {
p = p->next;
}
LinkNode *s = new LinkNode;
if (!s) {
return false;
}
s->data = e;
s->next = p->next;
p->next = s;
return true;
}
void printList(const LinkList &L) {
if (!L) {
return;
}
LinkNode *p = L->next;
while (p != L) {
cout << p->data << " ";
p = p->next;
}
cout << endl;
}
// 约瑟夫问题函数
void josephus(LinkList &L, int m) {
if (!L || L->next == L) {
cout << "链表为空或只有头节点！" << endl;
return;
}
LinkNode *p = L->next; // 从第一个数据节点开始
LinkNode *prev = L; // 记录p的前驱节点
while (L->next != L) { // 当还有数据节点时循环
for (int i = 1; i < m; i++) { // 数m-1次
prev = p;
p = p->next;
if (p == L) { // 如果遇到头节点，跳过
prev = p;
p = p->next;
}
}
// 删除当前节点p
prev->next = p->next;
cout << p->data << " ";
delete p;
p = prev->next;
if (p == L) { // 如果删除后指向头节点，调整到下一个数据节点
p = p->next;
prev = L;
}
}
cout << endl;
}
int main() {
LinkList L;
InitList(L);
int n, m;
cout << "请输入人数n：";
cin >> n;
cout << "请输入报数m：";
cin >> m;
for (int i = 1; i <= n; i++) {
insert_tail(L, i);
}
cout << "初始链表：";
printList(L);
cout << "出列顺序：";
josephus(L, m);
return 0;
}
使用说明：
1. 代码首先初始化循环链表，然后使用尾插法插入数据（例如人的编号）。
2. josephus 函数模拟报数过程，每次数到 m 时删除节点并输出数据。
3. 在循环中，如果指针遇到头节点，会自动跳过以确保只处理数据节点。
这个实现确保了约瑟夫问题的正确模拟，代码简洁易读。如果您有更多问题，欢迎继续提问！
以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。 和我一样，刚学数据结构{:10_256:}
页:
[1]