c语言实现约瑟夫环问题.docx

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

1、（一）基本问题1.问题描述有号人开始数，到停止数，1,2,⋯,n的n（n＞0）个人成一个圈，每个人持有一个密m。从第一个m停止数，m的人出圈，再从他的下一个人起重新数，到mm的出圈，⋯⋯，如此下去，直到所有人全部出圈止。当任意定n和m后，算法求n个人出圈的次序。建立模型，确定存构。任意n个人，密m，瑟夫。2.数据结构设计首先，瑟夫的存构。由于瑟夫本身具有循性，考采用循表，了一表中任意点的操作，循表不点。将循表的点定如下构型：structNode{intdata;Node*next;};其次，建立一个不点的循表并由指first指示3.算法设计1、工作指first，r，s，p，q初始化2、入人数

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;}}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-

3、>next;报出位置后Deleteq;计数器i++;运行流程图开始输入m和n创建链表Yk>n-1N移动指针p删除p后一结点q指针p后移，k++输出n结束代码和相关解释#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);//寻找每次出列人的号数i

4、ntLengthList(Node*L);//计算环上所有人数函数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);}}system("pause"

5、);}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<<"尾指针异常!"<

6、输入第一个报数人：";cin>>k;if(k<1

7、

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

9、st(Node**L,inti,Node*q)//寻找每次出列的人{if(i==1)i+=LengthList(*L);//顺序依次出列情况的处理方式Node*p;p=*L;intj=0;while(jnext;j++;}q=p->next;p->next=p->next->next;*L=p->next;return(q);}intLengthList(Node*L)//计