//基于单循环链表的约瑟夫环问题。n个人围成一圈,从第一个人开始报数1、2、3, 凡报到3者退出圈子,
// 找出最后留在圈子中的人的序号。请实现下列解决约瑟夫环问题的单循环链表类Joseph,使程序正确运行。
// 当单向链表中的尾结点指向头结点即构成单循环链表。
//如果输入为0,输出 No one!
#include<iostream>
using namespace std;
struct node
{
int data;
node* next;
node(int d, node* n = NULL) :data(d), next(n) {}
};
class Joseph
{
private:
node* head;
public:
Joseph(int n);
~Joseph();
void simulate();
};
int main()
{
int n;
cin>> n; //若输入5,表5人
Joseph jos(n);//生成有5个结点的链表,5个结点的data为1、2、3、4、5,表各人的序号
jos.simulate();
//输出两行。第一行输出被淘汰人的序号(序号间一个空格隔开):3 1 5 2
//第二行输出剩下人的序号:4
return 0;
}

基于单循环链表的约瑟夫环问题
- 写回答
- 好问题 0 提建议
- 追加酬金
- 关注问题
- 邀请回答
-
2条回答 默认 最新
- apples_kk 2023-03-29 15:12关注
#include <iostream> using namespace std; struct Node { int data; Node *pNext; }; class Joseph { private: Node *head; public: Joseph() { head = NULL; } // 创建单链表 void creatList(int n) { if(n == 0) { cout << "No one!" << endl; } else { // 创建头结点 head = new Node; head->pNext = head; head->data = 1; Node *p = head; // 创建节点 for(int i = 2; i <= n ; i++) { Node *s = new Node; s->data = i; p->pNext = s; p = s; } // 重新回到头结点 p->pNext = head; } } // 出圈 void JosephRing() { if(head != NULL) { int count = 0; Node *pPre = head; Node *pCur = head->pNext; while(pPre->pNext != pPre) { count++; if(count == 3) { // 删除pCur pPre->pNext = pCur->pNext; cout << pCur->data << "出圈"<< endl; // 将当前指针移动至下一位 pCur = pPre->pNext; // counter 归零 count = 0; } else { // 将pPre 指针移动至下一位 pPre = pCur; // 将当前指针移动至下一位 pCur = pPre->pNext; } } cout << "最后留在圈中的是:" << pPre->data << endl; } } ~Joseph(){} }; int main() { int n = 0; cin >> n; Joseph joseph; joseph.creatList(n); joseph.JosephRing(); return 0; }
本回答被题主选为最佳回答 , 对您是否有帮助呢?解决 无用评论 打赏 举报
悬赏问题
- ¥40 找同学帮敲Python代码
- ¥15 MYSQL 订单的商品明细重复计算问题
- ¥15 微信实时共享位置修改
- ¥100 TG的session协议号转成直登号号后客户端登录几分钟后自动退出设备
- ¥50 共模反馈回路的小信号增益
- ¥15 arduino ssd1306函数与tone函数放歌代码不兼容问题
- ¥70 0.96版本hbase的row_key里含有双引号,无法deleteall
- ¥15 诊断性META分析合并效能的检验
- ¥15 请问abb根据色块判断奇偶数并根据批次号放入仓储
- ¥66 开发PC客户端一定也要开发上位机吗?