实验一约瑟夫问题实验报告

数据结构实验报告实验名称： 实验一 约瑟夫问题学生姓名： *班 级： 20132111*班内序号： *学 号： 201321*日 期： 2014年1月4日1 实验要求实验题目：利用循环链表实现约瑟夫问题的求解。约瑟夫问题如下：已知n个人（n=1）围坐一圆桌周围，从1开始顺序编号。从序号为1的人开始报数，顺时针数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规则重复下去，直到所有人全部出列。请问最后一个出列的人的编号。实验目的：熟悉C+语言的基本编程方法，掌握集成编译环境的调试方法学习指针、模板类、异常处理的使用掌握线性表的操作的实现方法学习使用线性表解决实际问题的能力2. 程序分析2.1 存储结构 采用单循环链表实现约瑟夫问题的求解单循环链表示意图2.2关键算法分析1、关键算法首先通过尾插法建立单循环链表，若只有一个人，即只删除该人即可，若多于一人，则每查到m个人时删除该节点，并将循环链表连接好，共循环n-1次，每次删除均返回被删数值。2、代码详细分析：1).指针结构、类的声明struct Node /创立节点 int number; Node *next; ; class Joseph /建立Joseph类 private: int n; int m; Node *front ; /front头指针public: Joseph(int nn, int mm); /构造函数 Joseph(); /析构函数 void Delete(); /删除函数; 2）.单循环链表的建立 Joseph:Joseph(int nn, int mm) /构造函数，建立循环链表 n=nn; m=mm; Node *p,*rear; /建立两个指针.尾插法，p2始终指向为节点 for(int i=1; inumber=i; if(i=1) /建立空链表 front=p; rear=p; else rear-next=p; rear=p; rear-next=front; /尾指向头，循环完成 算法： 设两个指针p,rear, rear为尾节点，p为新增加的节点 若是空链表，则front=p; rear=p; 否则用尾插法,即p 在rear的后面，将p给rear;rear-next=p; rear=p; 头结点赋给rear的指针域，完成循环循环次数为n, 时间复杂度为O（n）3）. 输入值异常的情况coutn;if (n1) /考虑n输入错误的情况coutn值输入错误endl;coutm;if (m1) /考虑m输入异常的情况coutm值输入错误endl;4）.寻找一定间隔的人，并将其删除void Joseph:Delete() /删除人员的函数 Node *p1,*p2,*p; int count; /用来计数 p1=front; /头结点给p1if(m=1)cout最后一个人的编号为nendl;elsecout每次被删除的人为endl; for(int i=1; i=n-1; i+) /共删除n-1个人，循环n-1次 count=1; while(countnext; /p1向后移 count+; coutnumbernext=p1-next; p1=p1-next; /p1后移，防止删除后指针悬挂 delete p; coutendl; cout最后一个人的编号为 numbernext; p2始终指向第一个节点 摘链，将p指向待删除的p1，即将p1元素从链表中摘除： 输出p1的数值 释放p元素：delete p;循环次数为m(n-1), 时间复杂度为O（n）5）析构函数Joseph:Joseph() /析构函数 delete front; front=NULL; 6）主函数void main() int n,m; coutn; coutm; Joseph joseph(n,m); joseph.Delete(); 3. 程序运行结果测试主函数流程： 开始等待用户输入输入值是否有效 是查找删除节点循环次数是否大于n-1次 是输出最后一个数值结束流程图示意图1、 测试条件：n数量级无限制 2、 测试结论4. 总结由于是第一次做数据结构的实验，而上学期的C+也因长时间没有碰过而稍显手生，在码程序的过程中遇到了很多问题，但通过翻看教材已基本解决。约瑟夫虽然构思起来比较简单