计算机与信息学院
课程名称：姓 名：系：专 业：年 级：学 号：指导教师：职 称：（程序设计类课程）
实验报告
算法与数据结构
计算机科学与技术
计算机科学与技术 2009级 091150022 宁正元 2011 年 6 月 5 日
实验项目列表
序号 1 2 3 4 5 6 7 8 9 10 11 12 实验项目名称 编程实现Josephus问题 编程实现哈夫曼算法 成绩 指导教师 宁正元 宁正元
福建农林大学计算机与信息学院实验报告
数据结构的程序实现
一、 实验目的和要求
1.进一步了解数据结构的实验策略。 2.掌握动态结构的静态实现方法。 3.了解大批量数据的组织策略。 4.掌握数据结构在问题建模中的应用。
二、 实验内容
编程实现Josephus问题 问题描述：
有n个人围坐一圈并由1～n编号，从某个人（例如编号为k的人）开始报数，数到m的人出列；接着从出列的下一个人开始重新1~m报数，数到m的人又出列；如此反复地报数，直到最后一个人出列为止。试设计确定这n个人出列序列的程序。分析：首先对每一个人赋以一个序号值作为人出列时，将他的序号改为0作为出列的标志。 游戏情况如下：（假设n=6,k=1,m=2）
6个人围坐一圈的序号：1，2，3，4，5，6 人出列的序号：2，4，6，3，1 最后一个人出列的序号：5
三、 实验环境
Microsoft Visual C++
四、算法描述及实验步骤
解题思路：
这里假设k=1，定义一个循环链表，用其每个节点来记录1到n的数。从1数到m（每数一个就把指针移下一位），当数到m时就把对应的结点删除。直到循环链表里只剩下一个结点时就可以得到结果了。 要求用户输入的内容有：
（1）人的个数，也就是n的值；
（2）是出列的人的间隔，也就是m的值；
（3）所有人的序号要求存在链表中，需要定义一个指针，这里我们用数组来存放人的序号。 要求输出的内容是： （1）离开人的序号； （2）最后留下人的序号；
所以，根据上面分析输入输出参数，我们考虑出列的序号可以直接输出，这样可以使函数的复杂性。下面用Ｃ＋＋编写程序： //输入参数：
//People为指向一个整形指针，指向保存人数组的首地址； //n为人的个数； //m为数人的个数；
int Josephus(int *People,int n,int m) {
int i=-1,j=0,k=1;
//开始数人，只到留下一个人 while(1) {
//数m个人 for(j=0;j i=(i+1)%n; //取下标加1的模，当i的值在0到n-1之间循环 if(People[i]!=-1) //人在环中则数数有效； j++; } if(k==n) //如果k==n则表示，此时数组中只留下一个人， break; //序号为People[i]中的值，跳出循环; cout< People[i]=-1; //离开的人用-1作标记 k=k+1; } cout< return(People[i]); //返回最获胜人的序号 } 五、调试过程 在Microsoft Visual C++中调试通过，完整的程序：