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

《北邮数据结构实验-约瑟夫环》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、数据结构实验报告实验名称：实验1——约瑟夫环学生姓名：班级：班内序号：学号：口期：1.实验要求实验目的：通过利用循环链表实现约瑟夫问题的求解进行实现，掌握如下内容：1.熟悉C++语言的基本编程方法，掌握集成编译环境的调试方法2.学习指针、模板类、异常处理的使用3.掌握线性表的操作的实现方法4.学＞』使用线性表解决实际问题的能力实验内界：利用循环链表实现约瑟夫问题的求解。约瑟夫问题如下：已知n个人（n〉=l）围坐一圆桌周围，从1开始顺序编号。从序号为1的人开始报数，顺吋针数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规则重

2、复下去，直到所有人全部出列。请问最后一个出列的人的编号、2.程序分析2.1存储结构首先构建结点的结构体，包拈结点的编号rnnnber和指向后继元素的指针*!^^。然后构建循环链表储存每一个结点。2.2关键算法分析1、关键算法：插入：用尾插法构建循环链表，建立一个尾指针1•用来保存最后一个结点的地址，插入每一个节点后，r指向新插入的结点。用for循环来给每一个结点的number赋值。插入的步骤：1.建立新指针s;2.在for循环中给s赋值；3.将r指针指向s;4.修改尾招针r=s5.在全部结点插入后，将终端结点指肉第一个指针，r-〉next=fron

3、t-〉next。约瑟夫环算法实现：1.因为每次循环都有一个人出列，最后只剩一个人，因此要进行n-1次循环，用for循环实现。2.同时定义一个指针p=front-〉next，侮次循环front和p均后移m-1个，使p指向每次循环的第m个人，front指向第m-1个人。并输出出列的人的number,即p-〉number。3.让front-〉next=p-〉next,删除po4.继续进行循环2、代码详细分析：约瑟夫环算法步骤：①定义一个指针p=front->next,每次循环front和p均后移m-1个，使p指向每次循环的第m个人，front指昀第m-1

4、个人。②设q指向第m个元素：q=p；③摘链，即将q元素从链表中摘除：front->next=p-〉next;④P=p->next；⑤输出q元素的number:x=q->number；⑥释放q元素：deleteq；q3、时间复杂度：每次都删除第m个数字，都要用0(m)的时间，一共有n个数字，想要剩下一个，其余都要删除，那么就得用(n-l)*O(m)的吋间，故算法的吋间复杂度为O(mn).空间复杂度：O(n)2.3其他在约瑟夫环屮添加差错，使输入的都保证大于0.同时将约瑟夫环实现函数放在主函数try中，使得抛岀的错误能够被捕捉。源代码：#include

5、;classjoseph{private:intn;intm;nodc*front:public://建立约瑟夫环类//总人数//数到m的那个人山列//尖指针joseph(inta,intb);"joseph();intshove();};joseph::joseph(inta,intb)//以循环链表形式储存约瑟夫环{n=a;m二b;front=newnode;node*r=front;for(inti=l;i〈=n;i++){node氺s=ne'v

6、node;s->number=i;r->next=s;r=s;}r->next=front->ncxt;)//让最后一个人指向第一个人，形成循环链表joseph::〜joseph(){}//析构阑数//解决约瑟夫环intjoseph::shove0{if(n<=0)throw"n不能小于0〃;if(m<=0)throw〃m不能小于0";node*q;p=front_>next;//进行次循环，最后剩余1个人for(intj=l;j〈：n-1;j++)//找到第m个人的位置front二p;p=p->next:}//输山第m个人的编号//删除第m个人/

7、/删除第Hl个人的空间cout«p->number<<，z":front->ncxt=p->ncxt:Q=P；p=p->next;deleteq;}cout<〈〃剩下的〃<〈p->numbcr;)intmain(){intn,m;cout〈〈〃n=";cin»n;cout<〈’’m=";cin>>m;Josephtext(n,m);try//异常处理{text,shove();}catch(charconst*s)cout«s<

8、数能够输出正确的结果。如图所示.•2.总结问题:1.链表在循环时头指针不参与循环，将尾指针指向第一个结点，而久•指针只起到