北邮数据结构实验-约瑟夫环.docVIP

数据结构实验报告 实验名称： 实验1——约瑟夫环 学生姓名： 班 级： 班内序号： 学 号： 日 期： 1．实验要求 实验目的： 通过利用循环链表实现约瑟夫问题的求解进行实现，掌握如下内容： 熟悉C++语言的基本编程方法，掌握集成编译环境的调试方法 学习指针、模板类、异常处理的使用 掌握线性表的操作的实现方法 学习使用线性表解决实际问题的能力 实验内容： 利用循环链表实现约瑟夫问题的求解。 约瑟夫问题如下：已知n个人（n=1）围坐一圆桌周围，从1开始顺序编号。从序号为1的人开始报数，顺时针数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规则重复下去，直到所有人全部出列。请问最后一个出列的人的编号。 首先构建结点的结构体，包括结点的编号number和指向后继元素的指针*next。然后构建 2.2 关键算法分析 关键算法： 插入： 用尾插法构建循环链表，建立一个尾指针r用来保存最后一个结点的地址，插入每一个节点后，r指向新插入的结点。用for循环来给每一个结点的number赋值。 插入的步骤： 2.在for循环中给s赋值；3.将r指针指向s；4.修改尾指针r=s 5.在全部结点插入后，将终端结点指向第一个指针，r-next=front-next。 1.因为每次循环都有一个人出列，最后只剩一个人，因此要进行n-1次循环，用for循环实现。 2.同时定义一个指针p=front-，即p-number。 3.让f 4.继续进行循环 约瑟夫环算法步骤： 定义一个指针p=front- 向每次循环的第m个人，front指向第m-1个人。 设q指向第m个元素：q = p； 摘链，即将q元素从链表中摘除：front-next = p-next； P=p-next； ：x=q-number 时间复杂度: 每次都删除第m个数字，都要用O(m)的时间，一共有n个数字，想要剩下一个，其余都要删除，那么就得用(n-1)*O(m)的时间，故算法的时间复杂度为O(mn). 空间复杂度： 2.3 其他 在约瑟夫环中添加差错，使输入的,m都保证大于0.同时将约瑟夫环实现函数放在主函数try中，使得抛出的错误能够被捕捉。源代码： #includeiostream using namespace std; struct node // { int number; node *next; }; class joseph //建立约瑟夫环类 { private: int n; //总人数 int m; //数到m的那个人出列 node*front; //头指针 public: joseph(int a,int b); ~joseph(); int shove(); }; joseph::joseph(int a,int b) //以循环链表形式储存约瑟夫环 { n=a; m=b; front=new node; node*r=front; for(int i=1;i=n;i++) { node*s=new node; s-number=i; r-next=s; r=s; } r-next=front-next; //让最后一个人指向第一个人，形成循环链表 } joseph::~joseph(){} //析构函数 int joseph::shove() //解决约瑟夫环 { if(n=0) throw n不能小于0; if(m=0) throw m不能小于0; node *p,*q; p=front-next; for(int j=1;j=n-1;j++) //进行n-1次循环，最后剩余1个人 { for(int i=1;im;i++) //找到第m个人的位置 { front=p; p=p-next; } coutp-number ; //输出第m个人的编号 front-next=p-next; //删除第m个人 q=p; p=p-next; delete q; //删除第m个人的空间 } cout剩下的p-number; } int main() { int n,m; coutn=; cinn;