约瑟夫环实验.pdf

《约瑟夫环实验.pdf》由会员分享，可在线阅读，更多相关《约瑟夫环实验.pdf（9页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、 约瑟夫问题 一、流程图。1.建立约瑟夫环；2.输出每次出列号数；3.寻找每次出列人；4.计算环上所有人数 Y 开始 输入 m n 创建链表 kn-1 移动指针 p 删除 p 后一节点 q P 后移，k+输出 n 结束 二、源代码。#include#include using namespace std;struct Node/循环节点的定义 int number;/编号 Node*next;Node*CreateList(Node*L,int&n,int&m);/建立约瑟夫环函数 void Joseph(Node*L,int n,int m);/输出每次出列号数函数 Node*DeleteL

2、ist(Node*L,int i,Node*q);/寻找每次出列人的号数 int LengthList(Node*L);/计算环上所有人数函数 void main()/主函数 system(color 1d);Node*L;L=NULL;/初始化尾指针 int n,m;coutn;/环的长度 if(n1)cout请输入正整数!;/人数异常处理 else coutm;if(m1)cout请输入正整数!;/号数异常处理 else L=CreateList(L,n,m);/重新给尾指针赋值 Joseph(L,n,m);system(pause);Node*CreateList(Node*L,int&

3、n,int&m)/建立一个约瑟夫环（尾插法）Node*q;for(int i=1;inumber=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);/返回尾指针 else cout尾指针异常!endl;/尾指针异常处理 void Joseph(Node*L,int n,int m)/输出每次出列的人 int k;coutk;if(kn)cout请输入 1-n之间的数endl;else coutn 出列顺序:n;for(int i=1;in;i+)Node*q=new

4、 Node;if(i=1)q=DeleteList(&L,k+m-1,q);/第一个出列人的号数 else q=DeleteList(&L,m,q);cout号数：numberendl;delete q;/释放出列人的存储空间 cout最后一个出列号数是：numberendl;/输出最后出列人的号数 Node*DeleteList(Node*L,int i,Node*q)/寻找每次出列的人 if(i=1)i+=LengthList(*L);/顺序依次出列情况的处理方式 Node*p;p=*L;int j=0;while(jnext;j+;q=p-next;p-next=p-next-next;*L=p-next;return(q);int LengthList(Node*L)/计算环上的人数 if(L)cout尾指针错误!next;while(p!=L)i+;p=p-next;return(i);三、运行结果。