《实验一约瑟夫问题.doc》由会员分享，可在线阅读，更多相关《实验一约瑟夫问题.doc（7页珍藏版）》请在金锄头文库上搜索。
1、北京邮电大学信息与通信工程学院数据结构实验报告实验名称： 实验一2.4约瑟夫问题学生姓名：班 级： 班内序号： 学 号： 日 期： 2012年10月31日1实验要求实验目的：1、熟悉C+语言的基本编程方法，掌握集成编译环境的调试方法2、学习指针、模板类、异常处理的使用3、掌握线性表的操作的实现方法4、学习使用线性表解决实际问题的能力实验内容：已知n个人（n=1）围坐一圆桌周围，从1开始顺序编号。从序号为1的人开始报数，顺时针数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规则重复下去，直到所有人全部出列。输出最后一个出列的人的编号。2. 程序分析2.1 存储结构采用单
2、循环链表实现约瑟夫问题的求解。front1n2.2 关键算法分析基本思想：确定构造链表时所用的插入方法尾插法。当数到m的那个人就出列也即删除这个节点，同时建立这个节点的前节点与后节点的联系，并依次输出出列号码。采用循环链表进行循环操作，就是关于出列节点的逻辑判断，依次找到待删结点的直接前驱便于删除结点后修改它的直接后继，如此循环直到最后一个人出列。还要考虑输入值异常的情况。关键算法：1、在循环中实现逐个出列并找出最后一个出列人的序号。while(w) int i=1; /控制次数 while(inext; /p和q向前进,p在q后面 if(q=front)i=i; /如果q指向了头结点，则不计
3、入次数，并且不可以删除该点 elsei+; /其他情况i+ Node *r;p-next=q-next;r=q; /p指向q后面一个，r指向q,删除r结点,q再指向p， o=r-data;q=p;delete r; /使得与开始时处于同一情况使i=m条件成立, coutonext-next=front)w=0; /链表里只剩一个数（人）时的判断条件 时间复杂度为O(m*(n-1)2、删除出列结点并返回Node *r;p-next=q-next;r=q; /p指向q后面一个，r指向q,删除r结点,q再指向p， o=r-data;q=p;delete r; /使得与开始时处于同一情况使inext;
4、摘链，让r = q ,后将q元素从链表中摘除：p-next = q-next;保存r元素的数据：o = r-data;释放r元素：delete r;front1n2、尾插法建立单循环链表 front=new Node;front-data=0; /便于最后人数判别时、作为一个标识取出非零人的编号Node * r=front;for(int i=0;idata=ai;r-next=s;r=s;r-next=front;时间复杂度O（n）3、输入的人数n、序号m异常的情况报错：if(n=1)coutn最后一个出列人的编号是1endl;else if(n1|m1)cout输入错误endl;3. 程序
5、运行结果1、测试主函数流程：流程图如图所示输入n,m， m输入正确请按任意键继续否初始化循环链表是开始移动工作指针p,q，找到目标结点否输出数据，删除结点剩下1个元素？是输出最后一个出列的编号结束2、程序运行结果如下图（其他事项老师提出修改意见：按序输出出列结点修改代码：cout依次出列的人是：data;coutonext-next=front运行成功。心得体会： 1、数据结构学习中有很多有用、有效而且高度优化的算法，熟知他们并且能够熟练的应用才是我们学习的真正目的，理论是为了应用准备的。2、数据结构与STL和C+、C等语言息息相关，要拓宽我们的知识面，这样才能够得心应手。3、很多实际问题都能够找到相关的算法解决，通过自己编程可以发现不管过程中出现多少错误，有过多少失望，但最终解决方法是一定存在的，所以只要是自己编写的程序，不管代码多长多乱，一定能找到一个解决的方法，一定要有信心并且给予自己坚持的力量。下一步改进：相关模版类运用不够熟练，相关知识也不是很了解，希望可以通过自己的学习将相关知识应用到程序中，优化并精简程序结构和算法。大多数算法都是在前人的基础上总结并逐步优化提高的，希望自己能够多看课外书，增加相关知识的了解。第1页
