湖北民族学院
数据结构课程设计课题名称：猴子选大王
专业：计算机科学与技术
班级：0311401
姓名：
学号：031140105
指导老师：
一、设计题目
猴子选大王
二、主要内容
一堆猴子都有编号，编号是1，2，3 ...m ，这猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。
三、具体要求及应提交的材料
要求：使用数组和循环链表等两种以上的存储方式来做
输入数据：输入m,n m,n 为整数，n<m
输出形式：中文提示按照m个猴子，数n 个数的方法，输出为大王的猴子是几号，建立一个函数来实现此功能
用C/C++语言编程实现上述内容，对每个问题写出一个算法实现，并按数学与计算机学院对课程设计说明书规范化要求，写出课程设计说明书。
可采用数组、链表数据结构实现。在此基础上用C/C++实现其操作。
五、推荐参考资料
[1] 严蔚敏，吴伟民.数据结构.清华大学出版社出版。
[2] 严蔚敏，吴伟民. 数据结构题集(C语言版) .清华大学出版社.2003年
5月。
[3] 唐策善，李龙澎.数据结构(作C语言描述) .高等教育出版社.2001年
9月
[4] 朱战立.数据结构(C++语言描述)（第二版本）.高等出版社出版.2004
年4月
[5] 胡学钢.数据结构(C语言版) .高等教育出版社.2004年8月
[6] 徐孝凯等著.数据结构（C语言描述）.清华大学出版社.2004
目录
摘要 (3)
引言 (4)
1 需求分析 (4)
1.1任务与分析 (4)
1.2链表定义 (4)
数组和链表1.3主函数实现调用操作 (5)
2 详细设计............................. 错误！未定义书签。
3  调试分析 (5)
4 用户使用说明 (14)
5 测试结果 (15)
结论 (16)
致谢 (16)
参考文献 (16)
摘要
随着计算机的普及，涉及计算机相关的科目也越来越普遍，其中数据
结构是计算机专业重要的专业基础课程与核心课程之一，为适应我国计算
机科学技术的发展和应用，学好数据结构非常必要，然而要掌握数据结构
的知识非常难，所以对“数据结构”的课程设计比不可少。
本课程设计主要通过使用循环链表、数组、以及单向链表，将猴子编
号来数据化待选猴子坐成一个圈，并对圈内的猴子进行报数选取大王。最
终输出选出的猴子大王的编号。
考虑到循环链表、数组、以及单向链表要使用不同的结构体、算法等，
故将不同的三种方法设计为分开的三个类。只在主函数中调用其相应的函
数。程序通过调试运行，结果与预计结果一致，初步实现了设计功能。
关键词：现代版；队列（循环链表）；队列（数组）；单向链表；数据结构引言
A、课程设计任务
本课程设计主要实现在循环链表、数组、单向链表三种不同存储结构下对问题（即：“一堆猴子都有编号，编号是1，2，3 ...m ，这猴子（m个）按照1-m 的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。”）实现要求。依据猴子的编号数据化将猴子用以上方式存储。并进行报数入队，与出队操作。最终输出最后一位猴子编号，该猴子为此次当选的猴王。
B、课程设计性质
数据结构课程设计是重要地实践性教学环节。在进行了程序设计语言课和《数据结构》课程教学的基础上，设计实现相关的数据结构经典问题，有助于加深对数据结构课程的认识。本课程设计是数据结构中的一个关于数组、链表等算法的实现，包括在存储结构中添加、删除操作，最后把结果输出。此课程设计要求对数组存储结构和链表存储结构非常熟悉，并能熟练使用它们。
C、课程设计目的
其目的是让我们在学习完C++、数据结构等课程基础上，掌握数据的存储结构、掌握数据相应的存储，添加，更新等操作，并用输出结果。进一步掌握设计、实现较大系统的完整过程，包括系统分析、编码设计、系统集成、以及调试分析，熟练掌握数据结构的选择、设计、实现以及操作方法，为进一步的应用开发打好基础。
1 需求分析
1.1任务与分析
猴子选大王，众多猴子纷纷想成为大王，以一统族。更便享有最高的地位与权利，因而导致猴子间惨重的事件发生。在现代发展的社会中不管人类还是猴子都不想看到如此不幸的画面。故利用计算机软件来解决血腥的冲突。
即将编号为1，2，……n的一猴子按照1-n的顺序围坐成一个圈，所以可以用数组将其以循环的方式存储，输入猴子的总数m与要报的数n，且保证n<m。还用rear表示数组尾front数组头，并进行报数，将未报到指定数的猴子加到rear；用链表时可以用指针结点将一个猴子作为一个结点存储，也用front表示链表头，rear表示链表尾。将未到报数的猴子加到链表尾；循环链表就将链表的头尾连接，不用将未报到n的猴子加到尾部，只需将报到n的猴子结点删除。最后输出最后一个猴子的信息，便得出该猴子为此次选举的猴子大王。具体步骤如下：第一步建立数组（链表），填入猴子编号及猴子出局时报的数；
第二步从第一个猴子报数；
第三步数组存储中将数m的猴子不作操作，将未数到的猴子循环存在数组中，可以将报过数的信息猴子覆盖。链表中将报到的猴子结点删除；
第四步继续报数，重复第三步。到只剩一个猴子编号；
第五步输出此猴子的信息。
1.2.链表定义
/* 定义链表节点类型*/
typedef struct node
{
int data;
struct node *next;

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。