数据结构实验报告约瑟夫环2013053003.doc
文本预览下载声明
工程实践1
项目报告
实验课程： 数据结构 实验项目： 约瑟夫环问题 指导教师： 徐虹 学生姓名: 杨坤玉 学生学号： 2013053003 班 级： 数媒131班
2014年月成都信息工程学院院n个人围坐在圆桌周围，现从某个位置 i 上的人开始报数，数到 m 的人就站出来。下一个人，即原来的第m+1个位置上的人，又从1开始报数，再是数到m的人站出来。依次重复下去，直到全部的人都站出来，按出列的先后又可得到一个新的序列。要求编制程序，上机验证。
解决方法
解决约瑟夫环问题的四种方法：
1．循环链表
2．循环队列
3．顺序表
4．置标志
四种方法的算法
循环链表算法
循环队列算法
3．顺序表
4．置标志
实验中遇到的问题及心得
在解决顺序表的代码过程中，发现数组是从下标为0的地方开始的。所以起始位置输入的时候，要从0开始数。
而其余的代码却都是从第一个数字从1开始数的。
完整源程序（带注解）
1、循环链表代码：
#include iostream
using namespace std;
typedef struct student
{
int data;
struct student* next;
}node, *LinkList;
//约瑟夫环
void printfList(LinkList head){
LinkList p = head;
if (head != NULL)
{
do{
//cout p-data ;
p = p-next;
} while (p != head);//这里出现过问题，用do-while
}
}
void Josephus(int n, int k, int m){
int i = 2;
LinkList head = (LinkList)malloc(sizeof(node));
head-next = head;
head-data = 1;
LinkList pre = head;
while (i = n){
LinkList p = (LinkList)malloc(sizeof(node));
p-data = i;
p-next = pre-next;
pre-next = p;
pre = p;
i++;
}
printfList(head);
LinkList mend = pre;
int kk = 0;
while (kk != k){
mend = mend-next;
++kk;
}//找到k个开始
while (n--){//要全部输出
int mm = 1;
pre = mend;//每次都要给pre从新复值否则程序错误
while (mm != m){//不是要求的数，指针每次往前推一步，mend指向报数的人，pre指向前一个
pre = mend;
mend = mend-next;
mm++;
}
pre-next = mend-next;//前一个链到下一个准备报数的
cout mend-data endl;
mend = pre-next;//mend指向报数的人；
}
cout 最终剩下的人为: mend-data endl;
}
int main(){
int m, n, i;
cout 请输入人数n: ;
cin n;
cout 请输入开始位置i: ;
cin i;
cout 请输入报数m: ;
cin m;
cout 出队顺序如下: endl;
Josephus(n, i, m);
system(pause);
return 1;
}
2、循环队列代码：
#includeiostream
using namespace std;
typedef struct Node
{
int data;
struct Node* next;
}LNode, *LinkList;
LinkList list = NULL;
int n; //人数
int m; //报数号
//n为总人数，k为第一个开始报数的人，m为出列者喊到的数
void JosephRing(int n, int k, int m)
{
LinkList p, r; /* p为当前结点,r为辅助结点，指向p的前驱结点*/
for (int i = 1; i = n; i++) /*建立循环队列*/
{
p = (LinkList)malloc(sizeof(LNode));
p-data = i;
if (list == NULL)
显示全部