数据结构之猴子要选大王

"数据结构之猴子要选大王" 一、课程设计目的： 本课程设计旨在让学生掌握数据结构的应用、算法的编写、类C语言的算法转换成C程序并用TC上机调试的基本方法。具体来说，学生将学习单循环链表的结构和设计方法，掌握数据结构的基本知识，算法的编写，程序的调试，类C语言算法的转换等。 二、设计方案论证： 2.1 问题描述： 猴子要选大王，选举方法如下：所有猴子按1，2，……，m编号并按照顺序围成一圈。从第一个开始数，每数到第n个，该猴子就跳出圈外，如此循环报数，直到圈内剩下一只猴子时，这只猴子就是大王。m和n由键盘输入，打印出成为猴王的猴子号。 （1）问题分析： 通过对“猴子选大王”问题的分析，由于本题目的数据元素的个数不可预知，因此使用链表。链表是动态的，可以在需要的时候增长和减小其长度，而数组是在编译时分配内存的，所以其大小是不可改变的，而且会出现内存浪费的情况。我认为单循环链表能较好的解决问题。在建立循环链表时，因为链表的大小由输入决定，因此与其匹配的结点数也是变化的，所以要进行动态内存分配。 （2）限制条件： m>0;n>0; （3）研究意义： 单循环链表及动态存储的实现。 测试用例： m＝4;n＝3;最后求出成为猴王的猴子号。 结果： 这群猴子的大王是1号猴子。 2.2 数据结构设计 猴子选大王问题可以归结为筛选和排序问题，由于猴子数目以及报数数字的不确定性。故而数组很难满足条件，同时对于报完一次之后对于下一次的报数，由于已经排除了一部分猴子，猴子的顺序被打乱。从而选择链表中的循环链表来解决这一问题循环链表结构特点就是链表中最后一个节点的指针不再是结束标记，而是指向整个链表的第一个节点，从而使单链表形成一个环。 三、设计思路及算法设计： 3.1 功能模块图 有问题描述知，功能模块图有建立链表、删除结点、主函数三部分组成。如图1所示。 3.2 功能模块图思路设计 有n个猴子选大王，首先建立一个循环链表，必须有一个空的单循环链表，然后运用尾插法建立一个单循环链表，一个环就创建出来了，接下来就是处理这个环。由于每一个结点有一个猴子和一个序号，所以我们将结点结构体定义为猴子-序号(i)-指针域(next)。每当结点计数到某一猴子时，将他的前驱接到他的后继，然后将他的序号值M赋给计数变量，再将此结点删除。如此下去，直到最后变为空的单循环链表为止。则最终选出来的为猴子大王。 malloc 向系统申请分配指定size个字节的内存空间。返回类型是void*类型。void*表示未确定类型的指针。C,C++规定，void*类型可以强制转换为任何其它类型的指针。 3.3 算法设计 #include<stdio.h> #define MAX 10000/*猴子最多不超过一千*/ int main(){ /*定义变量*/ int iMonkey[MAX] = {0}; /*这里定义一个数组存放猴子退出状态，1为已经退出，0为未退出，初始值都为0*/ int iCount = 0; /*iCount为数的数，初始值为1*/ int iMonk_Sum = 0, iMonk_Last = 0, iMonk_Count = 0;/*iMonkey_Sum为猴子的总数，初始值为0,iMonkey_Last为剩下猴子数,初始值为0,iMonkey_Count为循环计数量，初始值为0*/ scanf("%d",&iMonk_Sum); /*输入一共多少只猴子*/ iMonk_Last = iMonk_Sum;/*计算部分*/ while( iMonk_Last > 1 ){ /*剩下的猴子多余1个，就循环*/ if( iMonkey[iMonk_Count] == 0 ){ /*没有退出的猴子才数数*/ iCount++; /*猴子数数*/ } if( iCount == 3 ){ /*数到3*/ iMonkey[iMonk_Count] = 1; /*让数到3的猴子退出*/ iMonk_Last--; /*剩下的猴子减一*/ iCount = 0; /*， } iMonk_Count++; /*下一个猴子的序号*/ } printf("%d",iMonk_Count-1); /*输出最后的猴子大王*/ return 0; } 四、结论： 通过本课程设计，学生将掌握数据结构的应用、算法的编写、类C语言的算法转换成C程序并用TC上机调试的基本方法。单循环链表能较好的解决“猴子选大王”问题，并且动态存储的实现提供了一个灵活的解决方案。