c语言实现约瑟夫环问题

（一）基本问题1.问题描述设有编号为1,2,…,n的n（n＞0）个人围成一个圈，每个人持有一个密码m。从第一个人开始报数，报到m时停止报数，报m的人出圈，再从他的下一个人起重新报数，报到m时停止报数，报m的出圈，……，如此下去，直到所有人全部出圈为止。当任意给定n和m后，设计算法求n个人出圈的次序。建立模型，确定存储结构。对任意n个人，密码为m，实现约瑟夫环问题。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;}}q-next=L;if(L!=NULL){return(L);}4、输入报数的起始人号数k;5、Node*q=newNode;计数器初始化i=1;6、循环n次删除结点并报出位置（其中第一个人后移k个）当in时移动指针m-2次p=p-next;删除p结点的后一结点qq=p-next;p-next=q-next;*L=p-next;报出位置后Deleteq;计数器i++;运行流程图代码和相关解释#includeiostreamusingnamespacestd;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);//计算环上所有人数函数开始输入m和n创建链表kn-1移动指针p删除p后一结点q指针p后移，k++输出n结束YNvoidmain()//主函数//在主函数中，完成人数（n）和报数（m）的输入和工作指针的初始化{Node*L;L=NULL;//初始化尾指针intn,m;cout请输入人数N：;cinn;//环的长度if(n1){cout请输入正整数!;}//人数异常处理else{cout请输入所报数M：;cinm;if(m1){cout请输入正整数!;}//号数异常处理else{L=CreateList(L,n,m);//重新给尾指针赋值Joseph(L,n,m);}}system(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尾指针异常!endl;//尾指针异常处理}voidJoseph(Node*L,intn,intm)//输出每次出列的人{intk;cout请输入第一个报数人：;cink;if(k1||kn){cout请输入1-n之间的数endl;}else{cout\n出列顺序:\n;for(inti=1;in;i++){Node*q=newNode;if(i==1)q=DeleteList(&L,k+m-1,q);//第一个出列人的号数elseq=DeleteList(&L,m,q);cout号数：q-dataendl;deleteq;//释放出列人的存储空间}cout最后一个出列号数是：L-dataendl;;//输出最后出列人的号数}}Node*DeleteList(Node**L,inti,Node*q)//寻找每次出列的人{if(i==1)i+=LengthList(*L);//顺序依次出列情况的处理方式Node*p;p=*L;intj=0;while(ji-2){p=p-next;j++;}q=p-next;p-next=p-next-next;*L=p-next;return(q);}intLengthList(Node*L)//计算环上的人数{if(L){cout尾指针错误!endl;}//异常处理else{inti=1;Node*p=L-next;while(p!=L){i++;p=p-next;}return(i);}}复杂度分析：for(inti=1;i=n;i++){Node*p;p=newNode;p-number=i;p-next=NULL;if(i==1)L=q=p;else{q-next=p;q=q-next;}时间复杂度：O（n）if(i==1)i+=LengthList(*L);Node*p;p=*L;intj=0;while(ji-2){p=p-next;j++;}q=p-next;p-next=p-next-next;*L=p-next;return(q);时间复杂度：O（n2）算法的空间复杂度：O（n2）4.界面设计请输入报数人数n请输入所报数M请输入第一个报数人——以下列出依次报数的结果5.运行、测试与分析(二)采用顺序存储结构如何实现约瑟夫环问题代码和解释#includestdlib.h#includestdio.h#includemalloc.h#defineMaxSize50typedefcharElemType;typedefstructSeqlist{//线性表顺序存储结构定义ElemType*elem[MaxSize];//存放顺序表数据元素intlength;//当前长度}*JSeqlist;//线性表存储结构类型名JSeqlistInt_SeqList(void){//顺序表初始化JSeqlistL;L=(JSeqlist)malloc(sizeof(structSeqlist));if(L!=NULL)L-length=0;elseprintf(超出范围！！);returnL;}ElemType*Locate_SeqList(JSeqlistL,intp){//查找线性表中下标为P的元素if(p=0&&L-length)return(L-elem[p]);else{printf(顺序表中不存在相关元素);returnNULL;}}intInsert_SeqList(JSeqlistL,inti,ElemType*x){//在顺序表中指定元素前插入Xintj;if(L-length==MaxSize)//L.length是最后一个元素的位置{printf(线性表已满，无法进行插入操作！！！！\n);return0;}if(i0||iL-length){printf(插入位置不对，超出顺序表长度\n);return0;}if(i==0){L-elem[i]=x;L-length=L-length+1;return1;}for(j=L-length;j=i;j--){L-elem[j]=x;}L-length++;return1;}intDelete_JSeqlist(JSeqlistL,inti){//在顺序表中删除第i个元素intj;if(i0||iL-length-1){printf(删除位置不对，超出顺序表的长度啦\n);return0;}for(j=i;jL-length-1;j++)L-elem[j]=L-elem[j+1];L-length--;return1;}voidjosephus(JSeqlistL,intstart,intm){//josephus问题求解的非常牛逼的函数ints,i;ElemType*w;s=start-1;for(i=L-length;i0;i--){s=(s+m-1)%i;w=Locate_SeqList(L,s);printf(出列人员为：%s\n,w);Delete_JSeqlist(L,s);}}intmain(void){JSeqlistJosephus;intn,m,i,k,s;Josephus=Int_SeqList();//顺序表初始化printf(约瑟夫环问题顺序表求解_愚人节特别版\n\n);printf(请输入本问题中总人数m=);scanf(%d,&n);printf(请输入本问题开始人员的位置S=);scanf(%d,&s);printf(请输入本问题的计数值m=);scanf(%d,&m);printf(请输入本问题中这些人的名字\n);for(i=0;in;i++){printf(第%d位置的人员的名字为:,(i+1));Josephus-elem[i]=(ElemType*)calloc(10,sizeof(char));scanf(%s,Josephus-elem[i]);k=Insert_SeqList(Josephus,i,Josephus-elem[i]);if(k==0)exit(1);}josephus(Josephus,s,m);free(Josephus);getchar();return0;}运行结果(三)密码不同#includeiostream.hstructCList{intpassword;intnumber;structCList*next;};typedefstructCListCNode;typedefCNode*CLink;CLinkCreateList(intlength){CLinkhead;CLinkbefore;CLinknew_node;inti;head=newCNode;if(head==NULL)returnNULL;coutPleaseInputPassword1:endl;cinhead-password;head-number=1;head-next=NULL;before=head;for(i=1;ilength;i++){new_node=newCNode;if(new_node==NULL)returnNULL;new_node-number=i+1;coutPleaseInputPasswordnew_node-number:endl;cinnew_node-password;new_node-next=NULL;before-next=new_node;before=new_node;}new_node-next=head;returnhead;}intmain(){CLinkhead;CLinkptr,back,last;inti,j,m,n;coutPleaseInputtheNumberofPersons:endl;cinn;coutPleaseInputtheFirstPasswordM:endl;cinm;head=CreateList(n);ptr=head;for(i=0;in;i++){for(j=0;jm-1;j++){back=ptr;//定位最后一个数的接点赋值给backptr=back-next;}cout第i+1个出