C++语言之链表初解(三)约瑟夫环之循环链表实现
小标 2018-06-25 来源 : 阅读 1020 评论 0

摘要:本文主要向大家介绍了C++语言之链表初解的约瑟夫环之循环链表实现,通过具体的代码向大家展示,希望对大家学习C++语言有所帮助。

本文主要向大家介绍了C++语言之链表初解的约瑟夫环之循环链表实现,通过具体的代码向大家展示,希望对大家学习C++语言有所帮助。

约瑟夫环是一个数学的应用问题:已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开

始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列。现编写循环链表程序来实现约瑟夫环问题并输出每次出列的结果~

用循环链表模拟此过程即可:1、建表;2、模拟出列规则。

下面还是老套路,直接贴上源码+注释~

Code:

[cpp] view plain copy
1. #include<iostream>  
2. using namespace std;  
3.   
4. typedef struct List  
5. {  
6.     int data;  
7.     struct List *next;  
8. }List, *Lnode;  
9.   
10. void Josephus(int n, int k, int m)//n:有n个人,编号1-n;k:从编号为k的人开始报数;m:数到m的人出列。  
11. {  
12.     Lnode first, now, pre, temp;//first:头节点;now:始终代表当前指针位置;pre:now的前驱节点;temp:新创建的节点。  
13.     //创建一个节点的循环链表  
14.     first = (Lnode)malloc(sizeof(List));  
15.     first->data = 1;  
16.     first->next = first;  
17.     now = first;  
18.     //创建循环链表,编号为1-n   
19.     for(int iFirst = 2; iFirst <= n; iFirst++)  
20.     {  
21.         temp = (Lnode)malloc(sizeof(List));  
22.         temp->data = iFirst; //给每个节点编号为1-n。  
23.         //将当前指针的后继赋给新创建的节点的后继(即新节点的后继为默认的“头节点”first)。  
24.         temp->next = now->next;         
25.         now->next = temp;    //将断开的连接修复好。  
26.         now = temp;         //移动当前指针,继续建表过程。  
27.     }  
28.     //将当前指针位置初始化,指向编号为1处。  
29.     now = now->next;  
30.     //当前指针指向编号为k处。  
31.     while(--k)   
32.     {  
33.         pre = now;  
34.         now = now->next;  
35.     }  
36.     //模拟出列过程。  
37.     printf("The Line is : ");  
38.     while(n--)  
39.     {  
40.         for(int j = 1; j < m; j++)  
41.         {//当前指针指向第m个报数的人。  
42.             pre = now;  
43.             now = now->next;  
44.         }  
45.         //删除并输出出列的编号。  
46.         pre->next = now->next;  
47.         if(now->next == now) printf("%d\n\n", now->data);//当剩余一个节点时,换行。  
48.         else printf("%d->", now->data);  
49.         first = now->next;   //出列后,第一个报数的人。  
50.         free(now);  //释放删除的节点。  
51.         now = first;    //当前指针转移到第一个报数的人,继续出列的过程。  
52.     }  
53. }  
54.   
55. int main()  
56. {  
57.     Josephus(9, 1, 5);  
58.     return 0;  
59. }

C++语言之链表初解(三)约瑟夫环之循环链表实现

Ps:仅供参考哈~~

本文由职坐标整理并发布,了解更多内容,请关注职坐标编程语言C/C+频道!

本文由 @小标 发布于职坐标。未经许可,禁止转载。
喜欢 | 0 不喜欢 | 0
看完这篇文章有何感觉?已经有0人表态,0%的人喜欢 快给朋友分享吧~
评论(0)
后参与评论

您输入的评论内容中包含违禁敏感词

我知道了

助您圆梦职场 匹配合适岗位
验证码手机号,获得海同独家IT培训资料
选择就业方向:
人工智能物联网
大数据开发/分析
人工智能Python
Java全栈开发
WEB前端+H5

请输入正确的手机号码

请输入正确的验证码

获取验证码

您今天的短信下发次数太多了,明天再试试吧!

提交

我们会在第一时间安排职业规划师联系您!

您也可以联系我们的职业规划师咨询:

小职老师的微信号:z_zhizuobiao
小职老师的微信号:z_zhizuobiao

版权所有 职坐标-一站式IT培训就业服务领导者 沪ICP备13042190号-4
上海海同信息科技有限公司 Copyright ©2015 www.zhizuobiao.com,All Rights Reserved.
 沪公网安备 31011502005948号    

©2015 www.zhizuobiao.com All Rights Reserved

208小时内训课程