数据结构约瑟夫环实验报告记录

1、数据结构约瑟夫环实验报告记 录作者:日期:tji朋岬越数据结构课程实验报告书姓名：徐鑫学号： 2116110307专业：物联网工程班级：16042017 年 10 月 15 日一、实验目的1 掌握线性表特性2 熟练掌握线性表的基本操作3.利用线性表设计算法并实现二、实验内容1. 解决约瑟夫环问题：已知n个人（以编号1, 2, 3.n分别表示）围坐在一张 圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从 1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全 部出列。2. 基本要求：1）根据题目要求设计解决约瑟夫环应用问题的数据结构。2）要求采用C+编程语言

2、实现设计的算法。三、设计思路1. 数据逻辑关系的分析可将人的顺序简单编号，从1到n； 构造一个循环链表，可以解决首位相连的问题； 将人的编号插入到结构体的 Data域中； 遍历人的编号，输出参与的人的编号；开始报数，从头报数，报到k的人出局（删除此结点），并释放此结点 直到人数只有一个人时，退出循环，输出获胜的人。fi(循环结束条件）2. 存储结构设计preP，cou nt=21L-A（建立约瑟夫环）3. 算法的核心思想说明 已知报数间隔m，我们可以把当前位置加上 m获得需要删除的位置，如 果获得的位置超过顺序表中实际元素的总长度， 则可以通过减去数组的实 际长度来修正修正(即模拟环状计数)。

3、然后把顺序表中的当前指向位置 设置为该位置，继而删掉该位置。确定需要删除的位置;设置并删除该位置。反复进行上述确定位置和删除位置的操作，直到顺序表为空。四、数据结构设计1. 类的声明和定义(要求给出完整的类声明和核心成员函数的定义)#ifndef Joseph_H#define Joseph_H#inelude using namespacestd;struct Node/结点int data;/存储数据Node *n ext; /下一个节点的地址;class CircularLinkList 单向循环链表类public:CircularLinkList() 构造函数first = new N

4、ode; first-data = NULL ; first- n ext = first;CircularLinkList() delete first; /析构函数void CreateLinkList( int a, int n); /创建单向循环链表void PrintLin kList(); / 遍历链表void JosephQnt k,int n); 约瑟夫环实现 private:Node *first;#en dif2. 算法实现#include Joseph.h#include #include void CircularLinkList :CreateLinkList( in

5、t a, int n)Node *s, *r = first; /尾指针初始化for (int i = 0;i data = ai;r-next = s;r = s;r-next = first-next; /循环void CircularLinkList :PrintLinkList() int cou nt = 0; 计数器Node *r = first- n ext;do cout setw(3) data; coun t+;r = r-n ext;if (cou nt % 10 = 0)cout en dlnext); /当链表循环到第一节点时跳出循环cout en dl;void C

6、ircularLinkList :Joseph(int k,int n)int m;cout 请输入约瑟夫密码：”；cin m;输入约瑟夫密码Node *pre, *p;pre = first; II工作指针初始化p = pre_n ext;for (int i = 0;i n ext;p = pre_n ext;int count = 1; II计数器初始化，约瑟夫问题至少有两个成员cout vv *nwhile (pre != p)if (cou nt = m) II如果计数器等于密码Sleep(1 * 1000); II执行挂起一段时间(1秒)cout data 号死亡！ n ext =

7、 p_n ext;delete q;删除死亡结点p = pre_n ext;count = 1;/计数器重新计数elsepre = pre-n ext; /工作指针后移 p = p_n ext;cou nt+; /计数器加一cout *ncout setw(26)data 号存活！ endl;显示最后存活的delete p;删除结点p system(pause);五、程序测试与实现1. 程序在调试过程中出现的问题及解决办法2. 程序运行过程及结果界面陲 C:Wi n d owssy-EtsmS 2cm d. ewe-X约瑟夫环游戏A请输入参与人数：6QB CiWi n d owssyst e

8、m3 2cm d. ex&-X约瑟夫环游戏 A请输入参与人数：6对所有人进行编号！ ！编号如下半123 4 5 6一请输入从第几人开始；2V六、实验调试ISEI C:Wi ndowssyitein32cmdrexfr X3约瑟夫环游戏 请输入参与人数：6对所有人进行编号！骗号如下二12 34 56一请输入从第几人开始：2 请输入约苦夫密码：4*豈事*审*字窝*来*卓常*卓*字案*字*黑豈*零* *5号死亡！3号死匸！戈号死亡！4号死亡！1号死亡！1*1 jjW 5*|l 5j*l 击*8 K 51 58 FW -S 宙 jjii|w 5j*i *1 51 1|*16号存活！请按任意键继续.搜狗拼音输入法全：七、问题及解决方法问题：无法从第k个人开始报数。解决方法：用while循环，找寻开始报数的编号k，找到后把他报的数标记为1. 问题：将LinkList.h文件的LinkList类中的行为函数放进LinkList.cpp文件中出现 错误“重定义”。解决办法：将行为函数的定义与声明均放进LinkList.h文件中。八、心得体会通过对约瑟夫环问题算法的设计，我加深了对数据结构及存储结构的理解，进一步的理解了课本中所学的各种数据结构，尤其是对单链表上基本运算的体现，