用单循环链表解决约瑟夫问题

用单循环链表解决约瑟夫问题1需求分析：有约瑟夫单链循环，当一个人被叫出去时候，他的下一位极其以后的指针就要随之改变，与单链表相似分析。首先，设计实现约瑟夫环问题的存储结构。由于约瑟夫环本身具有循环性质，考虑采用循环链表，为了统一对表中任意节点的操作，循环链表不带头结点。循环链表的结点定义为如下结构类型：structNode{intnumber;Node*next;};然后，建立一个不带头结点的循环链表并由头指针first指示。最后，设计约瑟夫环问题的算法。2源代码#includeiostream.hstructjose{intdata;intno;structjose*next;};intmain(){structjose*head,*p_curent,*p_find;intn,m;coutPleaseenterthetotalofnumbers(n):;cinn;coutPleaseenterthecounternumber(m):;cinm;//初始化链表head=p_curent=newjose;//标记首表元地址，即头指针head-no=1;coutPleaseenterthefirstnumber:;cinhead-data;//形成其余的n-1表元coutPleaseenterlastnumbers:endl;for(inti=2;i=n;i++){p_curent-next=newjose;p_curent=p_curent-next;cinp_curent-data;p_curent-no=i;}//endforp_curent-next=head;//尾指针指向头指针，形成环，到这完成初始化链表//开始查询，第M个人出列，并输出coutNow:Thenumbersofwhowillquitthecycleinturnare:endl;while(n)//全部出列后结束循环{//掠过m－1个表元for(intj=1;jm;j++)p_curent=p_curent-next;//endfor//找到第M个人p_find=p_curent-next;//从表中删除第m个人，并输出第m个人p_curent-next=p_find-next;coutp_find-dataendl;//释放第m个表元占用的空间deletep_find;n--;}//endwhilereturn0;}3调试分析：时间复杂度：O（n2）206120