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