c语言实现约瑟夫环问题

《c语言实现约瑟夫环问题》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、实用文案（一）基本问题1.问题描述设有编号为1,2,…,n的n（n＞0）个人围成一个圈，每个人持有一个密码m。从第一个人开始报数，报到m时停止报数，报m的人出圈，再从他的下一个人起重新报数，报到m时停止报数，报m的出圈，……，如此下去，直到所有人全部出圈为止。当任意给定n和m后，设计算法求n个人出圈的次序。建立模型，确定存储结构。对任意n个人，密码为m，实现约瑟夫环问题。2.数据结构设计首先，设计实现约瑟夫环问题的存储结构。由于约瑟夫环问题本身具有循环性质，考虑采用循环链表，为了统一对表中任意结点的操作，循环链

2、表不带头结点。将循环链表的结点定义为如下结构类型：structNode{intdata;Node*next;};其次，建立一个不带头结点的循环链表并由头指针first指示3.算法设计1、工作指针first，r，s，p，q初始化2、输入人数（n）和报数（m）3、循环n次，用尾插法创建链表Node*q;for(inti=1;i<=n;i++){Node*p;p=newNode;p->data=i;标准文档实用文案p->next=NULL;if(i==1)L=q=p;else{q->next=p;q=q->next;

3、}}q->next=L;if(L!=NULL){return(L);}4、输入报数的起始人号数k;5、Node*q=newNode;计数器初始化i=1;6、循环n次删除结点并报出位置（其中第一个人后移k个）当inext;删除p结点的后一结点qq=p->next;p->next=q->next;*L=p->next;报出位置后Deleteq;计数器i++;运行流程图标准文档实用文案开始输入m和n创建链表k>n-1移动指针p删除p后一结点q指针p后移，k++输出n结束YN代码和相关解

4、释#includeusingnamespacestd;structNode//循环节点的定义{intdata;//编号Node*next;};Node*CreateList(Node*L,int&n,int&m);//建立约瑟夫环函数voidJoseph(Node*L,intn,intm);//输出每次出列号数函数Node*DeleteList(Node**L,inti,Node*q);//寻找每次出列人的号数intLengthList(Node*L);//计算环上所有人数函数标准文档实用文

5、案voidmain()//主函数//在主函数中，完成人数（n）和报数（m）的输入和工作指针的初始化{Node*L;L=NULL;//初始化尾指针intn,m;cout<<"请输入人数N：";cin>>n;//环的长度if(n<1){cout<<"请输入正整数!";}//人数异常处理else{cout<<"请输入所报数M：";cin>>m;if(m<1){cout<<"请输入正整数!";}//号数异常处理else{L=CreateList(L,n,m);//重新给尾指针赋值Joseph(L,n,m);}}syst

6、em("pause");}Node*CreateList(Node*L,int&n,int&m)//建立一个约瑟夫环（尾插法）{Node*q;for(inti=1;i<=n;i++){Node*p;p=newNode;p->data=i;标准文档实用文案p->next=NULL;if(i==1)L=q=p;//工作指针的初始化else{q->next=p;q=q->next;}}q->next=L;if(L!=NULL){return(L);}//返回尾指针elsecout<<"尾指针异常!"<

7、尾指针异常处理}voidJoseph(Node*L,intn,intm)//输出每次出列的人{intk;cout<<"请输入第一个报数人：";cin>>k;if(k<1

8、

9、k>n){cout<<"请输入1-"<

10、数："<data<data<