猴子选大王课程设计报告.pdf

北京化工大学北方学院

课程设计报告

课程名称数据结构课程设计

设计题目猴子选大王

专业、班级软件工程0902班

学号090203

姓名

指导教师周建敏

设计时间2012年9月17日—2012年10月14日

2012年10月10日

1

一、引言（简要说明设计题目的目的、意义、内容、主要任务等）

1、目的

(1)训练学生灵活应用所学数据结构知识，独立完成问题分析，结合数据结构理

论知识，编写程序求解指定问题。

(2)初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法

和技能；

(3)提高综合运用所学的理论知识和方法独立分析和解决问题的能力；

(4)训练用系统的观点和软件开发一般规范进行软件开发，巩固、深化学生的理

论知识，提高编程水平，并在此过程中培养他们严谨的科学态度和良好的工作作风

(5)本次程序程序设计的主要目的是解决变相的“约瑟夫环”问题猴子大王。

从而使复杂的甄选工作变得明朗简单化。同样，这种解决问题的思想还可以运用到其

他具有类似问题的领域，达到一点窥面的效果。

2、意义

熟练掌握数据结构这门课程，掌握经性表、栈、队列、串、数组、广义表、树和

二叉树以及图等基本类型的数据结构及其应用。

进一步熟悉抽象数据类型的定义和实现、如何利用数组的动态分酚实现顺序结

构、继承的实现方式。

学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的

逻辑结构、想念结构及基相应的算法并初步掌握算法的时间分析和空间分析的技术。

基本掌握程序设计的基本思路和方法。

利用所学的基本知识和技能，解决简单的程序设计问题各算法描述

培养我们的数据抽象能力。利用单向循环链表模拟此过程，输出选出的大王编号。

通过本课程设计，可加深我们对链表的了解，对今后的学习有很大帮助。

3、内容

全程序以数据结构（C语言）中的循环单链表为主要的设计支柱，利用了C语言

简洁紧凑、灵活方便，语法限制不太严格，程序设计自由度大，生成目标代码质量高，

程序执行效率高等方面的优点。C语言是一种计算机程序设计语言，它既具有高级语

言的特点，又具有汇编语言的特点。它由美国贝尔研究所的D.M.Ritchie于1972年

推出，1978年后，C语言已先后被移植到大、中、小及微型机上，它可以作为工作系

2

统设计语言，编写系统应用程序，也可以作为应用程序设计语言，编写不依赖计算机

硬件的应用程序。它的应用范围广泛，具备很强的数据处理能力，不仅仅是在软件开

发上，而且各类科研都需要用到C语言，适于编写系统软件，三维，二维图形和动画，

具体应用比如单片机以及嵌入式系统开发。

循环单链表是单链表的另一种形式，其结构特点是链表中最后一个结点的指针域

不再是结束标记，而是指向整个链表的第一个结点，从而使链表形成一个环，基于这

样的特点，它适合处理具有环形结构的数据元素序列。

4、主要任务

现在需要用数据结构（C语言）解决“猴子选大王”的问题，具体问题如下：

一堆猴子都有编号，编号是1，2，3...m,这群猴子（m个）按照1-m的顺序围

坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到

圈中只剩下最后一只猴子，则该猴子为大王。

要求解决问题的程序必须满足以下条件：

1、输入数据：输入m,n为整数

2、输出形式：中文提示按照m个猴子，数n个数的方法，输出为大王的猴子是

几号，建立一个函数来实现此功能。