实验一约瑟夫问题

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

1、北京邮电大学信息与通信工程学院数据结构实验报告实验名称：实验一2.4——约瑟夫问题学生姓名：班级：班内序号：学号：日期：2012年10月31日1．实验要求实验目的：1、熟悉C++语言的基本编程方法，掌握集成编译环境的调试方法2、学习指针、模板类、异常处理的使用Ø3、掌握线性表的操作的实现方法Ø4、学习使用线性表解决实际问题的能力实验内容：已知n个人（n>=1）围坐一圆桌周围，从1开始顺序编号。从序号为1的人开始报数，顺时针数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规则重复下去，直到所有

2、人全部出列。输出最后一个出列的人的编号。2.程序分析2.1存储结构采用单循环链表实现约瑟夫问题的求解。front1n……2.2关键算法分析基本思想：第7页北京邮电大学信息与通信工程学院确定构造链表时所用的插入方法尾插法。当数到m的那个人就出列也即删除这个节点，同时建立这个节点的前节点与后节点的联系，并依次输出出列号码。采用循环链表进行循环操作，就是关于出列节点的逻辑判断，依次找到待删结点的直接前驱便于删除结点后修改它的直接后继，如此循环直到最后一个人出列。还要考虑输入值异常的情况。关键算法：1、在循环中实现逐个出列并

3、找出最后一个出列人的序号。while(w){inti=1;//控制次数while(i<=m){p=q;q=q->next;//p和q向前进,p在q后面if(q==front){i=i;}//如果q指向了头结点，则不计入次数，并且不可以删除该点else{i++;}//其他情况i++Node*r;p->next=q->next;r=q;//p指向q后面一个，r指向q,删除r结点,q再指向p，o=r->data;q=p;deleter;//使得与开始时处于同一情况使i<=m条件成立,cout<

4、确删除r所指的q结点。if(front->next->next==front){w=0;}//链表里只剩一个数（人）时的判断条件}时间复杂度为O(m*(n-1))2、删除出列结点并返回第7页北京邮电大学信息与通信工程学院Node*r;p->next=q->next;r=q;//p指向q后面一个，r指向q,删除r结点,q再指向p，o=r->data;q=p;deleter;//使得与开始时处于同一情况使i<=m条件成立,在i=m时正确删除r所指的q结点时间复杂度O（1）①从第一个结点开始，查找第m-1个元素，设为p指向

5、该结点；②设q指向第m个元素：q=p->next;③摘链，让r=q,后将q元素从链表中摘除：p->next=q->next;④保存r元素的数据：o=r->data;⑤释放r元素：deleter;front1n……2、尾插法建立单循环链表front=newNode;front->data=0;//便于最后人数判别时、作为一个标识取出非零人的编号Node*r=front;第7页北京邮电大学信息与通信工程学院for(inti=0;idata=a[i];r->next=s;

6、r=s;}r->next=front;时间复杂度O（n）3、输入的人数n、序号m异常的情况报错：if(n==1){cout<<"最后一个出列人的编号是"<<1<

7、

8、m<1){cout<<"输入错误"<

9、老师提出修改意见：按序输出出列结点修改代码：cout<<"依次出列的人是："<data;cout<

10、通过将q再次指向p使得计数正确。3、判断是否只剩一个元素（即输出该号码）时，调试时发现与实际情况不相符，后分析发现条件不正确，后改为front->next->next==front运行成功。心得体会：1、数据结构学习中有很多有用、有效而且高度优化的算法，熟知他们并且能够熟练的应用才是我们学习的真正目的，理论是为了应用准备的。2、数据结构与STL