用c++编写程序猴子选大王.docx
《用c++编写程序猴子选大王.docx》由会员分享，可在线阅读，更多相关《用c++编写程序猴子选大王.docx（7页珍藏版）》请在冰点文库上搜索。
用c++编写程序猴子选大王
用C++编写程序猴子选大王（总9页）
湖南人文科技学院计算机系
课程设计说明书
课程名称:
数据结构
课程代码:
题目:
猴子选大王
年级/专业/班:
06级计算机科学与技术专业一班
学生姓名:
学号:
0640810906408102064081070640812206408103
指导教师:
刘刚常
开题时间:
2008年6月16日
完成时间:
2008年6月29日
摘要
本文首先介绍顺序表和链表并作以比较，我们分别使用循环队列和循环链表来解决猴子选大王的问题,程序使用了C语言编写,有很少一部分函数是用C++编写的，有比较详细的中文注释并在VC++下调试运行通过。
整个程序使用中文界面,并有相应的提示信息,便于操作和程序运行。
关键词：
循环队列；循环链表；存储结构
Abstract
Thispaperdetailsthedifferenceofsequencelistandrespectivelyusequeueandcircularqueueandcircularlinkedlisttosolvetheseekelectedkingofthemonkeyproblem.TheprocedurewritewithClanguage，averysmallpartfunctionisusedbytheC++,andhaschineseexplanatory’smore,itwasdebuggedinVC++debuggerandrunverywholeprocedure,withChineseinterfaceandthecorrespondinghints,isconvenienttorunandeasytobeoperated.
Keywords:
circularqueue；circularlinkedlist；storagestructure
《数据结构》课程设计
——猴子选大王
一、引言
数据结构是一门非常重要的基础学科，但是实验内容大都不能很好的和实际应用结合起来。
从而让很多学生认为学习数据结构并没有很大的作用。
但本实验运用数据结构的知识，很好的解决了一个对于人脑来说比较烦琐的实际问题。
链表是一种以链式结构存储的线性表，特点是数据元素可以用任意的存储单元存储，线性表中逻辑上相邻的两元素存储空间可以是不连续的。
同时为了表示逻辑关系，每个数据元素除了存放自身的数据信息外还要存储一个指示其直接后继的信息。
队列是一种先进先出的线性表。
它只允许在的表的一端进行插入，而在另一端删除元素。
循环队列是队列的顺序表示和实现。
从时间上考虑顺序表中插入和删除元素的时间复杂度为O（N）,查找元素的时间复杂度为O
（1）;而链表中插入和删除元素的时间复杂度为O
（1）,查找元素的时间复杂度为O（N）。
而链表中除了存放自身的数据信息外,还要存放后继结点的地址信息,存储密度不高。
本设计分别通过一个顺序存储结构和一个链表存储结构，再加适当函数与改变，就简明的解决了猴子选大王这个实际问题，其中顺序存储结构我们使用的是循环队列。
依次按要求淘汰猴子一直到找到猴王，并依次显示被淘汰猴子的编号，输出猴王的编号。
该程序具有一定的通俗性与实用性，其他类似的算法均可借鉴和参考使用。
该程序清单详细具体、全面，为了使组员之间能够很好的理解各自完成的程序，促进组员之间的沟通，我们在程序中添加了较多的注释和说明，具有很强的可读性。
二、设计目的与任务
1、本课程设计的目的
1）初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能并培养学生进行规范化软件设计的能力。
2）训练学生灵活应用所学数据结构的基本知识，熟练的完成问题分析、算法设计、编写程序，求解出指定的问题；
3）提高综合运用所学的理论知识和方法独立分析和解决问题的能力；
4）训练用系统的观点和软件开发一般规范进行软件开发，巩固、深化学生的理论知识，提高编程水平，并在此过程中培养他们严谨的科学态度和良好的工作作风。
5）使学生会使用各种计算机资料和有关参考资料，提高学生进行程序设计基本能力。
2、本课程设计的任务
问题描述：
1）分别使用顺序和链表二种存储结构
2）功能实现：
一群猴子都有编号，编号是1，2，3...m,这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第n个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。
输入数据：
输入m,n。
其中m,n为整数，n输出形式：
依次显示离开圈的猴子编号，并且输出为大王的猴子编号。
三、设计方案
1、总体设计
1）使用顺序存储结构实现
我们选择的是使用一个循环队列来完成这个设计。
定义并构造一个空循环队列，把猴子按照1到m的顺序依次进入该队列，再按题目要求把被淘汰的猴子踢出队列，使用两个循环把被淘汰猴子的编号和猴王的编号分别输出。
本设计使用循环队列求解猴子选大王的问题，程序中定义的数据结构如下：
定义一个循环队列typedefstructSqQueue
进队列intEnQueue（SqQueue&Q,QElemTypee）
出队列intDeQueue（SqQueue&Q,QElemType&e）
主程序包含模块：
typedefstructSqQueue
{
京清华大学出版社,2005年
[2]严蔚敏等，数据结构题集（C语言版）.北京清华大学出版社，2005年
[3]苏仕华等，数据结构课程设计.机械工业出版社，2005年
课程设计任务书及成绩评定
课题名称：
_猴子选大王
完成者：
李伟民李一可袁川华张志明周伟波
1、设计的目的与要求：
1）训练学生灵活应用所学基本知识，熟练的完成问题分析、算法设计、编写程序；
2）初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能并培养学生进行规范化软件设计的能力。
；
3）提高综合运用所学的理论知识和方法独立分析和解决问题的能力；
4）训练用系统的观点和软件开发一般规范进行软件开发，巩固、深化学生的理论知识，提高编程水平，并在此过程中培养他们严谨的科学态度和良好的工作作风。
5）使学生掌握使用各种计算机资料和有关参考资料，提高学生程序设计的基本能力。
2、设计进度及完成情况
日期
内容
分析问题，找出所要解决问题的关键
—
总体设计，找出解决方案
详细设计，列出解决步骤
—
程序编码
—
程序调试，修改加以完善
书写文档
3、成绩评定：
设计成绩：
（教师填写）
指导老师：
（签字）
二00年月日
升级会员 