循环链表应用——约瑟夫置换
2021/9/18 23:35:04
本文主要是介绍循环链表应用——约瑟夫置换,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
约瑟夫问题
介绍
约瑟夫问题,又称约瑟夫置换、丢手绢问题。
一般形式
(本部分内容来自百度百科)
约瑟夫问题是个有名的问题:N个人围成一圈,从第一个开始报数,第M个将被杀掉,最后剩下一个,其余人都将被杀掉。例如N=6,M=5,被杀掉的顺序是:5,4,6,2,3。
代码
问题描述
本文以以下问题为例
编号为1-10的10 个人围成一圈,从第一个开始报数,第9个被淘汰出圈,剩下的组成新的圈。依次这样下去,求最后一个人的编号
解决
注意:该段代码与上篇文章——《 循环链表定义及操作 》相接
//解答约瑟夫问题 bool Joseph(LinkList* &L, int interval) { LinkList *p = L, *q; int i = 0, j = 0; int times = 0; //当前轮数 int num = 0; if(!L || p->next == L) { cout << "链表为空\n"; return false; } if(interval < 1) { cout << "报数淘汰口令不能小于1\n"; return false; } do{ i += interval; //找查第i个结点,p指向该结点的上一个结点 while(p->next){ if(p->next != L) { //如果不是头结点的话 j++; } if(j >= i) break; p = p->next; } times++; q = p->next; //临时保存被删结点以备释放空间 num = q->data; cout << "当前结点:" << q->data << " 上一个结点:" << p->data <<" 下一个结点:" << q->next->data << endl; p->next = q->next; delete q; //释放被删除结点内存 LinkListPrint(L); }while(L->next != L); //链表不为空,继续报数 cout << "最后一个出圈者的编号" << num << endl; return true; }
完整代码
代码
#include <iostream> #include <string> using namespace std; typedef struct _LinkNode { int data; struct _LinkNode *next; }LinkList; bool InitList(LinkList* &L) { L = new LinkList; if(!L) return false; L->next = L; L->data = 0; return true; } bool ListInsert_back(LinkList* &L, LinkList *node) { LinkList *last = NULL; if(!L || !node) return false; if(L == L->next) { //头结点指针指向了自己(链表只有头结点) node->next = L; L->next = node; }else{ //非空的循环链表 last = L->next; //寻找尾结点(指向头结点的结点) while(last->next != L) { last = last->next; } node->next = L; last->next = node; } return true; } void LinkListPrint(LinkList *L) { LinkList *p; if(!L || L == L->next) { cout << "链表为空\n"; return; } p = L->next; while(p != L) { cout << p->data << "\t"; p = p->next; } cout << endl; } //解答约瑟夫问题 bool Joseph(LinkList* &L, int interval) { LinkList *p = L, *q; int i = 0, j = 0; int times = 0; //当前轮数 int num = 0; if(!L || p->next == L) { cout << "链表为空\n"; return false; } if(interval < 1) { cout << "报数淘汰口令不能小于1\n"; return false; } do{ i += interval; //找查第i个结点,p指向该结点的上一个结点 while(p->next){ if(p->next != L) { //如果不是头结点的话 j++; } if(j >= i) break; p = p->next; } times++; q = p->next; //临时保存被删结点以备释放空间 num = q->data; cout << "当前结点:" << q->data << " 上一个结点:" << p->data <<" 下一个结点:" << q->next->data << endl; p->next = q->next; delete q; //释放被删除结点内存 LinkListPrint(L); }while(L->next != L); //链表不为空,继续报数 cout << "最后一个出圈者的编号" << num << endl; return true; } int main() { LinkList *L, *s; int i = 0; if(InitList(L)) { cout << "创建一个空的循环链表\n"; }else{ exit(-1); } cout << "尾插10个元素...\n"; while((++i)<=10) { s = new LinkList; s->data = i; s->next = NULL; if(ListInsert_back(L, s)) { cout << "success\n"; }else{cout << "default\n";} } LinkListPrint(L); Joseph(L,9); return 0; }
输出结果
注:0为头结点的数据,该结点并不计入约瑟夫环中(但最后也将其删除销毁链表释放内存)
创建一个空的循环链表 尾插10个元素... success success success success success success success success success success 1 2 3 4 5 6 7 8 9 10 当前结点:9 上一个结点:8 下一个结点:10 1 2 3 4 5 6 7 8 10 当前结点:8 上一个结点:7 下一个结点:10 1 2 3 4 5 6 7 10 当前结点:10 上一个结点:7 下一个结点:0 1 2 3 4 5 6 7 当前结点:2 上一个结点:1 下一个结点:3 1 3 4 5 6 7 当前结点:5 上一个结点:4 下一个结点:6 1 3 4 6 7 当前结点:3 上一个结点:1 下一个结点:4 1 4 6 7 当前结点:4 上一个结点:1 下一个结点:6 1 6 7 当前结点:1 上一个结点:0 下一个结点:6 6 7 当前结点:6 上一个结点:0 下一个结点:7 7 当前结点:7 上一个结点:0 下一个结点:0 链表为空 最后一个出圈者的编号7
这篇关于循环链表应用——约瑟夫置换的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-01后台管理开发学习:新手入门指南
- 2024-11-01后台管理系统开发学习:新手入门教程
- 2024-11-01后台开发学习:从入门到实践的简单教程
- 2024-11-01后台综合解决方案学习:从入门到初级实战教程
- 2024-11-01接口模块封装学习入门教程
- 2024-11-01请求动作封装学习:新手入门教程
- 2024-11-01登录鉴权入门:新手必读指南
- 2024-11-01动态面包屑入门:轻松掌握导航设计技巧
- 2024-11-01动态权限入门:新手必读指南
- 2024-11-01动态主题处理入门:新手必读指南