湖南工程学院猴子选大王数据结构课程设计报告

课 程 设 计 报 告

课程名称 数据结构

课题名称 猴子选大王

专 业 通信工程 班 级 1281 学 号 201213120121 姓 名 周永鑫 指导教师 张鏖辉

2014年 06 月 22 日

目 录

一、需求分析．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．1

1.1、问题描述．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．1 1.2、基本要求．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．1 1.3、需求分析．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．1

二、概要设计 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 2-3 三、详细设计．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．4

3.1、函数设计．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．4

3.2、代码．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．4-6 3.3、具体函数分析及变量分析．．．．．．．．．．．．．．．．．．．．．．．．．．6-7

四、调试分析及测试结果．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．7-9 五、用户使用说明．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．9-10

5.1、猴子选大王总体设计结构图．．．．．．．．．．．．．．．．．．．．．．．．．．10 5.2、猴子选大王系统模块结构图．．．．．．．．．．．．．．．．．．．．．．．．．．11

六、总结．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．12 七、附录．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．13-14

一、 需求分析

1.1、问题描述

一堆猴子都有编号，编号是1，2，3 ...m ,这群猴子（m个）按照编号的顺序围坐一圈，从第1开始数，每数到第n个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。

输入数据：输入整数m,n，且有n?m；

输出形式：（1）“按照m个猴子，数n 个数的方法，选出的大王是：几号” （2）输出选举过程中猴子离开的顺序。

存储结构：学生自己根据系统功能要求自己设计，请在最后的上交资料中指明你用到的存储结构；

测试数据：要求使用1、全部合法数据；2、整体非法数据；3、局部非法数据。进行程序测试，以保证程序的稳定。测试数据及测试结果请在上交的资料中写明；

1.2、基本要求

针对本次猴子数为m，循环数为n的猴子选大王问题，要求如下： 1：基本要求：输数据m，n为整数。2：输出形式：中文提示按照m个猴子，数n个数的方法，输出为大猴子几号，建一个函数来实现此功能。3：实现方案：使用循环单链表。

1.3、需求分析

1：输入数据m,n

2：计算出最终猴子大王的序号。 3：模拟出整个过程

4：找到合适的数据结构处理这个问题。 5：找到正确的方法解决这个问题。

二、 概要设计

n只猴子（编号0~(n-1)）,从0开始报数，报到（m-1）的退出，剩下的猴子继续从0开始报数。最后剩下的就是大王的编号。

我们知道第一只猴子(编号一定是m mod n-1)出列之后，剩下的n-1只猴子组成一个新的约瑟夫环（以编号为k=m mod n 的人开始）： K k+1 k+2...n-2,n-1,0,1,2,....k-2 并且从k开始报0。

现在我们把他们的编号做一次转换： k->0 k+1->1 k+2->2 ... ... k-2->n-2 k-1->n-1

变换后就完完全全成为了（n-1）只猴子选大王的问题。 递推公式 F[1]=0;

F=(f+m) mod i; (i>1)

有了这个公式，我们要做的就是从 1-n 顺序算出f的数值，最后的结果是f[n]。因为实际生活中编号总是从1开始，我们输出f[n]+1。 故此设计会用到4个未知数，我们定义为n,m,i,s: 其中n代表共有n只猴子选大王。 其中m代表间隔数。

其中i代表递归算法中的只i猴子选大王。 其中s代表最后剩下的猴子，即大王。 基本操作： 创建数组，链表

输入编号猴子信息，进入存储于数组，链表中 报数开始，报到出局数的猴子出局

输入选出的猴子大王信息 单向链表定义：

如下是单向链式的结构体包含一个数域和一个指下的指针域，数值域。 并也对其用类进行封装，使其更佳。

Struct Node //单向链表中每个结点包含一个数域和一个指下的指针域 {

int data; //数值域 Node *next;

}; //指针域，指向链表的下一个结点 Class danx //建类进行封装 {

Private:

Node *top; //创建头指针 Pubilc; };

循环链表定义：

如下是单向链式的结构体包含一个数域和一个指下的指针域，数值域。 并也对其用类进行封装，使其更佳。其中含有一个头指针，用于对其中初始结点的指向。

Struct NodeType //链表结点的结构体 {

Int num; //数值域，存储猴子编号 NodeType *next;

}; //指针域，指向下一个猴子结点 Class xunh {

private:

NodeType *Head; // 将头指针设为私有 Public; };

三、 详细设计

3.1、函数设计

程序设计中主要包括下列函数

LinkList initring(int n,linklist r) {

构造一个含n个元素的循环链表; }

LinkList delete(int n,int k,linklist r) {

循环删除报k号的元素； 循环输出所删除的元素；

记录链表最后所保留的元素的保置；

3.2、代码

void main() {

monkey *head,*p,*q,*s; int m,n,i;

printf(\请输入猴子的总数:\ scanf(\printf(\

printf(\请输入周期数:\ scanf(\

printf(\对猴子进行编号:\\n\\n\ head=q=p=(monkey *)malloc(sizeof(monkey)); for(i=1;i

q=(monkey *)malloc(sizeof(monkey));

q->data=i;

p->next=q;//使链表循环起来 p=q;

printf(\第%d位猴子的编号是:%d\\n\ }

q->next=head; head->data=m; p=head; q=p->next;

printf(\第%d位猴子的编号是:%d\\n\ printf(\if(m==1)

printf(\猴子大王的编号是:1\\n\else if(m!=1) {

if(n==1) {

for(i=1;i<=m;i++)

printf(\要删除的猴子号为:%d\\n\ printf(\猴子大王的编号是:%d\\n\ } else {

for(i=1;i

p=p->next; q=q->next;

if(i==n-1) {

printf(\要删除的猴子号为:%d\\n\s=q;

q=q->next;//q即为被点到的猴子 p->next=q;//删除q结点 free(s);//释放内存 i=0;//

计数器清零，重新开始计数m--;

}

if(m==1) break; }

printf(\猴子大王的编号是:%d\\n\此时的结点就是大王

} } }

3.3、具体函数分析及变量分析

在相关有效的提示信息后输入 m，n：

printf(\请输入猴子的总数:\scanf(\

printf(\请输入的周期数:\scanf(\

通过for语句，为m只猴子申请m-1个节点, 并将从1—m的猴子依次放入前m-1个节点中, 将第m个猴子放入head结点中。 printf(\对猴子进行编号:\\n\\n\

head=q=p=(monkey *)malloc(sizeof(monkey)); for(i=1;i

q=(monkey *)malloc(sizeof(monkey));

q->data=i; p->next=q; p=q;

printf(\第%d位猴子的编号是%d\\n\}

q->next=head; head->data=m; p=head; q=p->next;

printf(\第%d位猴子的编号是%d\\n\printf(\

构建好的具有m个结点单链表 m 1 2 3 m-1

head p q 4、对具体的m个猴子，分不同的情况找出大王： ①当m==1时，不论n为何值，大王就是这个编号为1的猴子； 如： if(m==1)

printf(\猴子大王的编号是:1\\n\

② 当m!=1，但n=1时，前m-1个猴子均要删除，最后留下的第m个猴子就是大王； 如：

else if(m!=1) { if(n==1) {

for(i=1;i<=m;i++)

printf(\要删除的猴子号为:%d\\n\ printf(\猴子大王的编号是:%d\\n\ }

③ 当m!=1，但n!=1时,根具具体的代码（如下）求出大王。 如： else {

for(i=1;i

p=p->next; q=q->next; if(i==n-1) {

printf(\要删除的猴子号为:%d\\n\s=q;

q=q->next;//q即为被点到的猴子 p->next=q;//删除q结点 free(s);//释放内存

i=0;//计数器清零，重新开始计数m--; }

if(m==1) break; }

printf(\猴子大王的编号是:%d\\n\

} } }

由于此次的课程设计题目所需要的相关知识大多数可在《《数据结构》》书中

找到，或借鉴。所以在完成代码后运行时，没出现严重错误和问题，只是有点小问题，即局部变量用错；没定义的也没用了，调试并找出错误，进行修改。最后获得成功。

四、 调试分析及测试结果

图1.根据提示信息输入相对应的m,n值

图2、对猴子进行编号，并且通过循环单链表对猴子进行删除

图3、最后显示最后留下来的猴子的号码，即为猴子大王 定义 n=8, m=3, 测试结果如下： 对猴子进行编号！

1号猴子：1 1号猴子报：1 2号猴子：2 2号猴子报：2

3号猴子：3 3号猴子报：3 号猴被淘汰 4号猴子：4 4号猴子报：1 5号猴子：5 5号猴子报：2

6号猴子：6 6号猴子报：3 6号猴被淘汰 7号猴子：7 7号猴子报：1 8号猴子：8 8号猴子报：2 1号猴子报：3 1号猴被淘汰 2号猴子报：1

4号猴子报：2

5号猴子报：3 5号猴被淘汰 7号猴子报：1 8号猴子报：2

2号猴子报：3 2号猴被淘汰 4号猴子报：1 7号猴子报：2

8号猴子报：3 8号猴被淘汰 4号猴子报：1 7号猴子报：2

4号猴子报：3 4号猴被淘汰 7号猴子报：1

胜出：7号猴子 press any key to continue

五、 用户使用说明

该系统具有简单、明了、使用等特点，能够方便、准确的计算出众多猴子编号选举大王的结果。当使用该系统时，系统会给出相关的提示信息，用户只需根据提示信息，即可完成系统提供的所有功能。

5.1、猴子选大王总体设计结构图

图4、猴子选大王流程图

5.2、猴子选大王系统模块结构图

图5、猴子选大王系统模块结构图

六、 总结

我们通信工程的学生在这周，在E座6楼进行了为期3天的课程设计。通过完成老师分布的课程任务，来更加的深入了解数据结构这门课程。再进一步的通过老师的亲自讲解，为我们解决了许多我们平时在课堂中没有理解或者消化的知识和难题。 猴子选大王是一个数据结构很古老很经典的问题，融知识性和娱乐性为一体人产生较大兴趣，因此编写程序实现之是一件很有意义的事。为编写这个程的代码及写课程设计报告，我们花了两周的时间，下面说说我们在这期间的感悟。

在课程设计中，首先要看清问题，将问题要求理解透彻，在构思要如何实现，要用到哪些函数，要用什么算法，在课程构思中选算法是一个很重要的概念，只有确定用这么算法后才能接下来的工作，将流程图画在纸上，再依次编写代码，在程序设计中，编写代码只是一个方面，调试才是关键。它是一个相当繁琐的过程，有许多新的问题需要被解决，但同时它也是一个比较重要的过程，因为在程序调试过程中，你会学到很多新的东西，从而增加你编程的经验。

通过本次实习，温固了数据结构的相关知识，加深对课内所学的有关数据的逻辑结构和存储表示、数据结构的选择和应用、算法的设计和时空效率分析等课程基本内容的理解，进一步熟悉了VC++编程环境，巩固并提高了分析问题、解决实际问题的能力。 做任何一件事情都需要一个过程，在这个过程中，面对许多问题，我们尽最大的努力寻找解决方法，现学现用新的知识，不断积累经验，为未来的发展打下基础。相互学习但是我们真正要学的是学习的能力，我们享受这个过程，因为它引领我们进步！

再次特别感谢老师的指导，为我们解决了许多的难题和困惑，通过这次课程设计，让我们更深一步的了解到数据结构的精髓和它的魅力所在。我们也在这次课程设计中感觉到我们的深深的不足，有许多的问题和缺漏。一些基本的理解和书本知识并不是太理解，所以在实际操作过程中不能得心应手，总是磕磕碰碰，动不动就要翻开书籍来查阅不解的问题，大大的降低了我们设计程序进程，所以我们要更加的一步步来，慢慢的理解，这样才能进步，慢慢的成长。

七、 附录

源程序：

#include #include typedef int DataType; typedef struct Node {

DataType data; struct Node *next; }monkey;// 定义结点 void main() {

monkey *head,*p,*q,*s; int m,n,i;

printf(\请输入猴子的总数:\ scanf(\ printf(\

printf(\请输入的周期数:\scanf(\

printf(\ printf(\对猴子进行编号:\\n\\n\head=q=p=(monkey *)malloc(sizeof(monkey)); for(i=1;i

q=(monkey *)malloc(sizeof(monkey)); q->data=i;

p->next=q;//使链表循环起来

p=q; printf(\第%d位猴子的编号是:%d\\n\ }

q->next=head;

head->data=m; p=head; q=p->next;

printf(\第%d位猴子的编号是:%d\\n\ printf(\if(m==1)

printf(\猴子大王的编号是:1\\n\ else if(m!=1) { if(n==1) {

for(i=1;i<=m;i++)

printf(\要删除的猴子号为:%d\\n\ printf(\猴子大王的编号是:%d\\n\} else {

for(i=1;i

{ p=p->next; q=q->next; if(i==n-1)

{

printf(\要删除的猴子号为:%d\\n\ s=q; q=q->next;//q 即为被点到的猴子 p->next=q;//删除q结点 free(s);//释放内存

i=0;//计数器清零，重新开始计数 m--;

} if(m==1) break;

}

printf(\猴子大王的编号是:%d\\n\此时的结点就是大王

} } }

课程设计评分表

课程名称： 数据结构 项 目 设计方案的合理性与创造性 设计与调试结果 设计说明书的质量 答辩陈述与回答问题情况 课程设计周表现情况 综合成绩

评 价

指导教师： 日 期：

本文来源：https://www.bwwdw.com/article/6ryv.html