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

数据结构课程实验报告书数据结构课程实验报告书 姓名：_XX_学号：_XX_专业：_物联网工程_ 班级：_1604_ 2017 年 10 月 15 日一、实验目的1 掌握线性表特性2 熟练掌握线性表的基本操作3. 利用线性表设计算法并实现二、实验内容1.解决约瑟夫环问题：已知n个人（以编号1，2，3.n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。2.基本要求：1）根据题目要求设计解决约瑟夫环应用问题的数据结构。 2）要求采用C+编程语言实现设计的算法。三、设计思路1.数据逻辑关系的分析可将人的顺序简单编号，从1到n；构造一个循环链表，可以解决首位相连的问题；将人的编号插入到结构体的Data域中；遍历人的编号，输出参与的人的编号；开始报数，从头报数，报到k的人出局（删除此结点），并释放此结点。直到人数只有一个人时，退出循环，输出获胜的人。2.存储结构设计 pre p,count=2123nfirst(建立约瑟夫环)pre pk (循环结束条件)3.算法的核心思想说明确定需要删除的位置； 设置并删除该位置。已知报数间隔m，我们可以把当前位置加上m获得需要删除的位置，如果获得的位置超过顺序表中实际元素的总长度，则可以通过减去数组的实际长度来修正修正（即模拟环状计数）。然后把顺序表中的当前指向位置设置为该位置，继而删掉该位置。 反复进行上述确定位置和删除位置的操作，直到顺序表为空。四、数据结构设计1.类的声明和定义（要求给出完整的类声明和核心成员函数的定义）#ifndef Joseph_H#define Joseph_H#include using namespace std; struct Node/结点int data;/存储数据Node *next;/下一个节点的地址; class CircularLinkList/单向循环链表类 public:CircularLinkList()/构造函数first = new Node;first-data = NULL;first-next = first;CircularLinkList() delete first; /析构函数void CreateLinkList(int a, int n); /创建单向循环链表 void PrintLinkList(); /遍历链表 void Joseph(int k,int n); /约瑟夫环实现private:Node *first;#endif2.算法实现#include Joseph.h#include #include void CircularLinkList:CreateLinkList(int 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 count = 0;/计数器Node *r = first-next;do cout setw(3)data;count+;r = r-next;if (count % 10 = 0)cout endlnext);/当链表循环到第一节点时跳出循环cout endl;void CircularLinkList:Joseph(int k,int n)int m; cout 请输入约瑟夫密码： ;cin m;/输入约瑟夫密码Node *pre, *p;pre = first;/工作指针初始化p = pre-next;for (int i = 0;i next;p = pre-next;int count = 1;/计数器初始化，约瑟夫问题至少有两个成员cout *n;while (pre != p)if (count = m)/如果计数器等于密码Sleep(1 * 1000);/执行挂起一段时间(1秒)cout setw(26)data 号死亡！ next = p-next;delete q;/删除死亡结点p = pre-next;count = 1;/计数器重新计数elsepre = pre-next;/工作指针后移p = p-next;count+;/计数器加一cout *n;cout setw(26)data 号存活！ endl;/显示最后存活的delete p;/删除结点psystem(pause);五、程序测试与实现1.程序在调试过程中出现的问题及解决办法2.程序运行过程及结果界面六、实验调试七、问题及解决方法问题：无法从第k个人开始报数。解决方法：用while循环，找寻开始报数的编号k，找到后把他报的数标记为1.问题：将LinkList.h文件的LinkList类中的行为函数放进LinkList.cpp文件中出现错误“重定义”。解决办法：将行为函数的定义与声明均放进LinkList.h文件中。八、心得体会通过对约瑟夫环问题算法的设计，我加深了对数据结构及存储结构的理解，进一步的理解了课本中所学的各种数据结构，尤其是对单链表上基本运算的体现，学会了如何使用循环链表，比如建立一个循环链表