数据结构约瑟夫环实验报告.doc

《数据结构约瑟夫环实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、.专业.专注.《数据结构》课程实验报告书姓名：_____徐鑫_________.word可编辑..专业.专注.学号：____2116110307____专业：____物联网工程____班级：_____1604________2017年10月15日.word可编辑..专业.专注.一、实验目的1．掌握线性表特性2．熟练掌握线性表的基本操作3.利用线性表设计算法并实现二、实验内容1.解决约瑟夫环问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出

2、列；依此规律重复下去，直到圆桌周围的人全部出列。2.基本要求：1）根据题目要求设计解决约瑟夫环应用问题的数据结构。2）要求采用C++编程语言实现设计的算法。三、设计思路1.数据逻辑关系的分析可将人的顺序简单编号，从1到n；构造一个循环链表，可以解决首位相连的问题；将人的编号插入到结构体的Data域中；遍历人的编号，输出参与的人的编号；开始报数，从头报数，报到k的人出局（删除此结点），并释放此结点。直到人数只有一个人时，退出循环，输出获胜的人。2.存储结构设计prep,count=2123nfirst……(建立约瑟夫环)prepk(循环结束条件)3.

3、算法的核心思想说明确定需要删除的位置；设置并删除该位置。.word可编辑..专业.专注.已知报数间隔m，我们可以把当前位置加上m获得需要删除的位置，如果获得的位置超过顺序表中实际元素的总长度，则可以通过减去数组的实际长度来修正修正（即模拟环状计数）。然后把顺序表中的当前指向位置设置为该位置，继而删掉该位置。反复进行上述确定位置和删除位置的操作，直到顺序表为空。四、数据结构设计1.类的声明和定义（要求给出完整的类声明和核心成员函数的定义）#ifndefJoseph_H#defineJoseph_H#includeusingname

4、spacestd;structNode//结点{intdata;//存储数据Node*next;//下一个节点的地址};classCircularLinkList//单向循环链表类{public:CircularLinkList()//构造函数{first=newNode;first->data=NULL;first->next=first;}~CircularLinkList(){deletefirst;}//析构函数voidCreateLinkList(inta[],intn);//创建单向循环链表voidPrintLinkList();//遍

5、历链表voidJoseph(intk,intn);//约瑟夫环实现private:Node*first;};#endif2.算法实现#include"Joseph.h"#include#includevoidCircularLinkList::CreateLinkList(inta[],intn){.word可编辑..专业.专注.Node*s,*r=first;//尾指针初始化for(inti=0;idata=a[i];r->next=s;r=s;}r->n

6、ext=first->next;//循环}voidCircularLinkList::PrintLinkList(){intcount=0;//计数器Node*r=first->next;do{cout<data;count++;r=r->next;if(count%10==0)cout<next);//当链表循环到第一节点时跳出循环cout<>请

7、输入约瑟夫密码：";cin>>m;//输入约瑟夫密码Node*pre,*p;pre=first;//工作指针初始化p=pre->next;for(inti=0;inext;p=pre->next;}intcount=1;//计数器初始化，约瑟夫问题至少有两个成员cout<<"***************************************************";while(pre!=p){if(count==m)//如果计数器等于密码{Sleep(1*1000);//执行挂起一段时间(1秒

8、).word可编辑..专业.专注.cout<data<<"号死亡！"<