《数据结构》课程实验报告书
《数据结构》课程实验报告书
姓名：_____徐鑫_________ 学号：____2116110307____ 专业：____物联网工程____ 班级：_____1604________
2017 年 10 月 15 日
1
《数据结构》课程实验报告书
一、实验目的
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=2 first
1 2 3 …… n (建立约瑟夫环) pre p k (循环结束条件) 3.算法的核心思想说明
确定需要删除的位置； 设置并删除该位置。
2
《数据结构》课程实验报告书
已知报数间隔m，我们可以把当前位置加上m获得需要删除的位置，如果获得的位置超过顺序表中实际元素的总长度，则可以通过减去数组的实际长度来修正修正（即模拟环状计数）。然后把顺序表中的当前指向位置设置为该位置，继而删掉该位置。
反复进行上述确定位置和删除位置的操作，直到顺序表为空。
四、数据结构设计
1.类的声明和定义（要求给出完整的类声明和核心成员函数的定义）
#ifndef Joseph_H
#define Joseph_H #include
};
class CircularLinkList//单向循环链表类 { public:
}; #endif
CircularLinkList()//构造函数 { }
~CircularLinkList() { delete first; }//析构函数
void CreateLinkList(int a[], int n); //创建单向循环链表 void PrintLinkList(); //遍历链表 void Joseph(int k,int n); //约瑟夫环实现 Node *first;
first = new Node; first->data = NULL; first->next = first; int data;//存储数据
Node *next;//下一个节点的地址
private:
2.算法实现
#include \
#include
void CircularLinkList::CreateLinkList(int a[], int n) {
Node *s, *r = first;//尾指针初始化 for (int i = 0;i < n;i++)//尾插法
3
数据结构约瑟夫环实验报告
