约瑟夫环-joseph环-数据结构与算法课程设计报告

合肥学院

计算机科学与技术系

课程设计报告

2009～2010学年第二学期

课学学专指

业导

班教生

姓

程 数据结构与算法

joseph环

课程设计名称

名 号 级 师

朱玉庭 0804012029 08计本(2) 王昆仑、张贯虹

2010 年06月08号

一、问题分析和任务定义：

约瑟夫环是一个数学游戏，根据游戏内容的描述，能够很容易的看出，游戏中

的玩家顺时针围坐一圈，能够很容易的发现，这跟本课上的单循环链表非常相似，所以可以通过单循环链表存储结构模拟此过程，当游戏中的玩家出列时，可以通过删除单循环链表中的结点来实现。

二、数据结构的选择和概要设计：

选择带为指针的单循环链表来解决这个问题，先建立一个空链表，然后根据人数生成具有相应结点的单循环链表，知道密码后，通过循环来找到对应的结点，然后将该结点的编号输出，改变密码，最后删除结点，以此类推，知道编码全部输完，即可得到结果序列。

三、详细设计和编码：

本题目是通过单循环链表存储结构来模拟此过程的，首先要先明确该单循环链表中结点的结构类型，定义如下：

typedef struct Node {

int key; //每个人持有的密码 int num; //这个人的编号 struct Node *next; //指向下一个结点 }Link;

当生成单循环链表时，就需要用到课本上创建单循环链表的有关内容了，可以先通过子函数Link *InitList()建立一个空链表，返回指针L，然后将返回的指针代入子函数Link *Creater(Link *L,int n)的形参中，对循环链表进行初始化，并且也返回一个指针，然后再将这个返回的指针代入到输出函数void Output(Link *L,int n,int m)的形参中，要想根据题目要求完成序列的输出，需要通过两个for循环来实现，第一个循环for(i=1;i<=n;i++) ，因为一个用n个人，所以结果要输出n个编号，这个循环每循环一次 输出一个编号即printf(\"%d \，并将该编号下的密码赋值给m 即m=q->key，当循环完毕时正好将编号全部输出，第二个循环for(j=1;jnext; q=p->next; 用以找到相应的结点，并用指针q指向它，当完成了编号的输出和密码的赋值后，删除q指向的结点，将两个循环适当结合，即可输出正确的结果序列，其中的人数n和初始密码在主函数中确定。 四、上机调试：

（1） 有2个玩家，初始密码为21；

（2）有3个玩家，初始密码为5：

（3）有5个玩家，初始密码为8：

（4）有7个玩家，初始密码为10：

五、测试结果及分析：

（1）程序运行后，只能执行一部分，错误情况如下：

错误原因如下：

调用子函数时，传递给形参的并不是L的地址，而是传递的内容，以至在对链表进行初始化时，语句L->next=p不能执行，for循环不了，故程序只能运行一部分，将程序略作修改，建空链表时，不用形参即可，修改如下：

（2）程序运行时，结果输不出来，错误情况如下：

错误原因如下：

两个形参中的L不能联系在一起，因为在进入约瑟夫环的函数Creater（L，n）后，L的地址虽然变化了，但是不会对主函数中L的地址造成影响，故在调用输出函数Output（L，n，m）时，其中的L的地址不是Creater（L，n）中改变后的地址，所以不能联系到一起， 将程序略作修改，在生成约瑟夫环的函数中返回一个指针，将此返回的指针代入到输出函数Output中即可，修改如下：

六、用户使用说明：

进入程序运行界面后，根据提示输入相应的信息，第一步输入的是总人数n，第二步输入初始密码m，紧接着依次输入n个学生的密码，输入完成后，即可显示出最终结果。 示例：

请先输入总人数：3

请确定开始时的报数上限值： 5 第1个人的密码：4 第2个人的密码：6 第3个人的密码：2 结果序列为：2 1 3

七、参考文献：

[1] 王昆仑，李红. 数据结构与算法. 北京：中国铁道出版社，2006年5月。 [2] 何钦铭，颜 晖. C语言程序设计. 北京：高等教育出版社，2008年1月。

[3] 郑 莉，董 渊. C++语言程序设计（第三版）. 北京：清华大学出版社，2004年1月。 [4] 谭浩强. C语言设计（第三版）. 北京：清华大学出版社，2006年3月。 [5] 百度。

八、附录：

#include\"stdio.h\" #include\"stdlib.h\" typedef struct Node {

int key; //每个人持有的密码 int num; //这个人的编号 struct Node *next; //指向下一个节点 }Link;

void Menu() {

printf(\"\\********************************************\\n\"); printf(\"\\\**Joseph环---课程设计**\\n\");

printf(\"\\********************************************\\n\"); }

Link *InitList() //创建一个空的链表 {

Link *L;

L=(Link *)malloc(sizeof(Link)); L->key=0; L->num=0; L->next=L; return L; }

Link *Creater(Link *L,int n) //初始化链表

{

Link *p,*q; int i; q=L;

for(i=1;i<=n;i++) {

p=(Node *)malloc(sizeof(Node)); printf(\"第%d个人的密码:\ scanf(\"%d\ p->num=i; L->next=p; L=p; }

L->next=q->next; free(q); return L; }

void Output(Link *L,int n,int m) {

Link *p,*q; int i,j; p=L;

printf(\"\\\**********Order**********\\n\"); printf(\"\\\结果序列为：\"); for(i=1;i<=n;i++) {

for(j=1;jnext; //p指到目的结点前一个结点 q=p->next; //q指向目的结点 m=q->key;

printf(\"%d \

p->next=q->next; //此两步是为了释放目的结点，即删除 free(q); }

printf(\"\\n\\\***********End***********\\n\"); }

void main() {

Link *L,*S; int n,m;

system(\"color A\");

L=InitList(); //构造出一个只有头结点的空链表 Menu();

printf(\"请先输入总人数:\");

scanf(\"%d\总共的人数n

printf(\"请确定开始时的报数上限值:\"); scanf(\"%d\初始密码为m

S=Creater(L,n); //建立好一个约瑟夫环 Output(S,n,m); }