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

《用单循环链表解决约瑟夫问题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、用单循环链表解决约瑟夫问题1需求分析：有约瑟夫单链循环，当一个人被叫出去时候，他的下一位极其以后的指针就要随之改变，与单链表相似分析。首先，设计实现约瑟夫环问题的存储结构。由于约瑟夫环本身具有循环性质，考虑采用循环链表，为了统一对表中任意节点的操作，循环链表不带头结点。循环链表的结点定义为如下结构类型：structNode { intnumber; Node*next;};然后，建立一个不带头结点的循环链表并由头指针first指示。最后，设计约瑟夫环问题的算法。2源代码#includestructjose{

2、 intdata; intno; structjose*next;};intmain(){ structjose*head,*p_curent,*p_find; intn,m; cout<<"Pleaseenterthetotalofnumbers(n):"; cin>>n; cout<<"Pleaseenterthecounternumber(m):"; cin>>m;  //初始化链表 head=p_curent=newjose;//标记首表元地址，即头指针 head->no=1; cout<<"Pleaseenterthef

3、irstnumber:"; cin>>head->data; //形成其余的n-1表元 cout<<"Pleaseenterlastnumbers:"<next=newjose;  p_curent=p_curent->next;  cin>>p_curent->data;  p_curent->no=i; }//endfor p_curent->next=head;//尾指针指向头指针，形成环，到这完成初始化链表 //开始查询，第M个人出列，并输出

4、 cout<<"Now:The numbersofwhowillquitthecycleinturnare:"<next;//end for  //找到第M个人  p_find=p_curent->next;  //从表中删除第m个人，并输出第m个人  p_curent->next=p_find->next;  cout<data<

5、/释放第m个表元占用的空间  deletep_find;  n--; } //endwhile  return0;}3调试分析：时间复杂度：O（n2）206120