数据结构 猴子选大王

*****数据结构课程设计题目: 赫夫曼树的建立运动会分数统计订票系统猴子选大王图的建立与输出姓名：***学号 ****专业：计算机科学与技术指导教师：****2006年9月20日目录一：绪言 (3)1.1课题设计背景 (3)1.2课题研究的目的和意义…………………………….3.1.3课题研究的内容 (4)二：主菜单设计 (4)2.1主菜单 (4)2.2主菜单源代码 (4)2.3主菜单流程图 (5)三：具体程序设计 (6)3.1赫夫曼树的建立 (6)3.2运动会设计 (8)3.3订票系统 (12)3.4猴子选大王 (15)3.5图的建立及输出 (16)四：总结与展望 (19)五：参考文献 (19).1.绪言1．1 课题背景《数据结构》作为一门独立的课程最早是美国的一些大学开设的，1968年美国唐·欧·克努特教授开创了数据结构的最初体系，他所著的《计算机程序设计技巧》第一卷《基本算法》是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。

从60年代末到70年代初，出现了大型程序，软件也相对独立，结构程序设计成为程序设计方法学的主要内容，人们就越来越重视数据结构，认为程序设计的实质是对确定的问题选择一种好的结构，加上设计一种好的算法。

从70年代中期到80年代初，各种版本的数据结构著作就相继出现。

目前在我国，《数据结构》也已经不仅仅是计算机专业的教学计划中的核心课程之一，而且是其它非计算机专业的主要选修课程之一。

《数据结构》在计算机科学中是一门综合性的专业基础课。

数据结构的研究不仅涉及到计算机硬件（特别是编码理论、存储装置和存取方法等）的研究范围，而且和计算机软件的研究有着更密切的关系，无论是编译程序还是操作系统，都涉及到数据元素在存储器中的分配问题。

在研究信息检索时也必须考虑如何组织数据，以便查找和存取数据元素更为方便。

因此，可以认为数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程，在计算机科学中，数据结构不仅是一般程序设计（特别是非数值计算的程序设计）的基础，而且是设计和实现编译程序、操作系统、数据系统及其它系统程序和大型应用程序的重要基础。

5.4.8 实验项目5-14：猴子选大王1、实验名称：猴子选大王2、实验目的：（1）熟练使用循环控制。

（2）熟练理解和掌握二维数组存储结构的使用技巧。

3、实验任务（1）实验内容：一群猴子要选新猴王。

新猴王的选择方法是：让n只候选猴子围成一圈，从某位置起顺序编号为1~n号。

从第1号开始报数（从1到3），凡报到3的猴子即退出圈子，接着又从紧邻的下一只猴子开始同样的报数。

如此不断循环，最后剩下的一只猴子就选为猴王。

请问是原来第几号猴子当选猴王？（2）实验要求：输入一个正整数n（n<=100），写一个程序来模拟这个过程，输出猴王的序号。

测试用例：4、实验要点分析（1）问题分析：用循环的方法模拟选猴王的过程。

一种简单的方法是对n只猴子用1~n 编号，编号存放在大小为n的一维整数数组中，若某编号的猴子要退出圈子，则把其编号改为-1。

若数组中只剩一个非-1的编号时，该编号的猴子就是大王。

开始时数组中的元素是从1到n的整数，表示都在“圈子”中，凡报到3的猴子退出圈子，即置为-1。

再依次查找下一只在“圈子”中的猴子，并重新开始报数。

这个过程进行n-1次，就只剩下一只编号不是-1的猴子了。

这种方法在寻找“下一个在圈子中的猴子”时可能会遇到很多“-1”而浪费时间。

另一种改进的方法是把n只猴子用0~n-1编号，数组的下标表示猴子的编号，数组元素的值表示相邻下一只在圈子中的猴子编号。

比如，n=5时，初始的数组M的内容如下表: 下标：0 1 2 3 4当2号猴子（报数轮到3）退出圈子时，1号猴子的下一只相邻猴子就是3号猴子了，实现时只需一个赋值M[1]=M[2]（即原来2号猴子的下一只相邻猴子成了1号猴子的下一只相邻猴子）。

数组M的内容变成了下表:下标：0 1 2 3 4这样做的好处有两个，一是第i号猴子的下一只相邻猴子就是M[i]，不需要用一个循环去找了；二是不用当心数组M下标的访问会越界。

（2）实现要点：1）循环控制结构。

上海应用技术学院课程设计报告课程名称《数据结构课程设计》设计题目猴子选大王；建立二叉树；各种排序；有序表的合并；成绩管理系统；院系计算机科学与信息工程专业计算机科学与技术班级姓名学号指导教师日期一.目的与要求1. 巩固和加深对常见数据结构的理解和掌握2. 掌握基于数据结构进行算法设计的基本方法3. 掌握用高级语言实现算法的基本技能4. 掌握书写程序设计说明文档的能力5. 提高运用数据结构知识及高级语言解决非数值实际问题的能力表。

3、输出功能：void print(LinkList *head);通过一个while的循环控制语句，在指针p!=NULL时，完成全部学生记录的显示。

知道不满足循环语句，程序再次回到菜单选择功能界面。

4、删除功能：LinkList *Delete(LinkList *head);按想要删除的学生的学号首先进行查找，通过指针所指向结点的下移来完成，如果找到该记录，则完成前后结点的连接，同时对以查找到的结点进行空间的释放，最后完成对某个学生记录进行删除，并重新存储。

5、插入功能：LinkList *Insert(LinkList *head)；输入你想插入的位置，通过指针所指向结点的下移，找到该位置，将该新的学生记录插入到该结点，并对该结点后面的指针下移。

链表长度加一，重新存储。

(5) 程序的输入与输出描述输入：调用LinkList *create()函数，输入学生的姓名、学号、三门功课的成绩；输出：调用void print(LinkList *head)函数，输出学生的记录。

(6) 程序测试主菜单：成绩管理系统的主界面：学生成绩记录的输入：输出学生成绩记录：学生成绩记录的删除（删除学号是1101的学生记录）插入新的学生成绩记录（插入学号为1103的学生记录）(7) 尚未解决的问题或改进方向尚未解决的问题：该成绩管理系统还存在不少缺陷，而且它提供的功能也是有限的，只能实现学生成绩的输入、输出、删除、插入。

第5章数组和广义表本章所讨论的多维数组和广义表是对线性表的推广，其特点是数据元素仍可被视为一个表。

要求熟悉多维数组的逻辑结构、存储结构，广义表的逻辑结构、表示形式，以及矩阵的压缩存储的有关内容。

重点提示：●多维数组的存储方式和存取特点●特殊矩阵的存储●稀疏矩阵的存储●广义表的表示形式5-1 重点难点指导5-1-1 相关术语1．特殊矩阵要点：矩阵中非零元素或零元素的分布有一定规律的矩阵。

2．对称矩阵要点：一种特殊矩阵；n阶方阵的元素满足性质：a ij=a ji（0≤i，j≤n-1）。

3．三角矩阵要点：以主对角线划分，有上三角矩阵和下三角矩阵两种；主对角线以下，不包括主对角线中的元素，均为常数c，称为上三角矩阵；主对角线以上，不包括主对角线中的元素，均为常数c，称为下三角矩阵。

4．对角矩阵要点：非零元素集中在以主对角线为中心的带状区域中，也称带状矩阵。

5．稀疏矩阵要点：矩阵中非零元素的个数远小于矩阵元素总数的矩阵。

6．三元组表要点：是稀疏矩阵的一种存储结构；将稀疏矩阵的非零元素的三元组（行、列和值）按行优先的顺序排列；得到结点均是三元组的线性表。

7．广义表要点：是线性表的推广；是n个元素a1,a2,…,a n的有限序列；其中a i或者是原子或者是广义表；通常记为LS=(a1,a2,…,a n)，LS为广义表的名字。

5-1-2 多维数组1．对n维数组逻辑结构的理解n维数组可视为由n-1维数组为元素的线性结构。

举例：一个m行n列的二维数组可视为由m个一维数组为元素组成的线性结构，其中每个一维数组又由n 个单元素组成。

]a ,,a ,[a A A A A a a a a a a a a a Amn in i2i1i m 21mnv m2m12n 22211n 1211 =⎪⎪⎪⎪⎪⎭⎫⎝⎛=⎪⎪⎪⎪⎪⎭⎫⎝⎛=其中2．数组的顺序存储方式（1）行优先顺序——将数组元素按行向量排列，即第i ＋1行紧接在第i 行后面。

一、猴子选大王：（1）M只猴子要选大王，选举办法如下：所有猴子按1-M编号围坐一圈，从1号开始按顺序1，2，，，K报数，凡报到K的猴子退出到圈外，如此循环报数，直到圈内只剩下一只猴子时，这只猴子就是大王。

M和K由输入文件提供，要求在输出文件中打印出最后剩下的猴子的编号。

数据规模（M<=1000,K<=10）【输入文件】输入文件monkey.in 的第1 行，为两个正整数，用一个空格隔开:M K【输出文件】输出文件monkey.out 只有一个正整数,输出最后一个猴子的编号【输入样例】7 3【输出样例】4这就是顶顶有名的约瑟夫问题。

这是一个据说是由古罗马著名史学家Josephus提出的问题演变而来的。

称之为约瑟夫问题。

很多资料上对这一问题解释得过于繁杂，实现起来不好理解。

在这里介绍一下本人的一些想法以供大家参考。

这个题目其实就是一种编程的经验问题。

我们可以假设猴子就位的状态用1表示，把猴子离开的状态用0表示。

那么我们就可以用一个a[M]的数组来存放M个猴子是否就位的状态。

我们可以一边报数一边遍历该数组，每遇到第K个1时，就把当前位置的1变为0，表示当前位置的猴子已经出局了。

一直循环遍历到我们的状态数组只有一个1的时候，这个存放1的数组下标再加上1（因为数组下标是由0开始的，所以要加1）即为选出的大王的编号。

想法很简单，现在关键的问题是如何解决当报数到第M个猴子的时候如何使得下一个报数重新回到第1个猴子处，也就是如何使用一维数组来解决环型问题的求解技巧。

大家想一下当我们的猴子围成圈坐的时候，问题其实由简单的一维数组变成了首尾相接的环型数组，也就是我们数据结构中的环型队列。

假设p为当前数组某一元素的下标，对于一维数组来说，我们只要p++就可以移动到下一个元素的位置上。

那么当p=M时，如果我们直接使用p++的话，p的值就超出了a[M]数组的最大长度，我们想要的是p++之后等于0。

那么如何实现呢？解决环型数组循环遍历元素的方法：对于环型数组移动下标时，我们如果每次在p++之后再加上p=p%M的话就能解决先前遇到的越界的问题。

《数据结构》课程设计题目(程序实现采用C语言)题目1：猴子选王(学时:3）一堆猴子都有编号，编号是1，2,3 .。

.m，这群猴子（m个)按照1-m的顺序围坐一圈，从第1开始数，每数到第n个,该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王.要求:m及n要求从键盘输入,存储方式采用向量及链表两种方式实现该问题求解.//链表#include 〈stdio.h〉＃include 〈stdlib.h>// 链表节点typedef struct _RingNode｛int pos；struct _RingNode ＊next;}RingNode， *RingNodePtr；// 创建约瑟夫环，pHead:链表头指针,count：链表元素个数void CreateRing(RingNodePtr pHead, int count)｛RingNodePtr pCurr = NULL， pPrev = NULL；int i = 1;pPrev = pHead；while（——count 〉 0）｛pCurr = (RingNodePtr）malloc（sizeof（RingNode））;i++;pCurr—〉pos = i；pPrev-〉next = pCurr；pPrev = pCurr;}pCurr-〉next = pHead; // 构成环状链表｝void KickFromRing(RingNodePtr pHead， int n){RingNodePtr pCurr, pPrev；int i = 1； // 计数pCurr = pPrev = pHead；while(pCurr != NULL){if （i == n）｛// 踢出环printf（"\n％d"， pCurr->pos); // 显示出圈循序pPrev—>next = pCurr->next；free（pCurr)；pCurr = pPrev—>next；i = 1;}pPrev = pCurr；pCurr = pCurr—〉next;if （pPrev == pCurr)｛// 最后一个printf("\nKing is %d", pCurr—〉pos）; // 显示出圈循序 free（pCurr)；break；}i++;｝}int main（）｛int n = 0, m = 0；RingNodePtr pHead = NULL;printf("M（person count）= ”）;scanf(”％d”, &m);printf("N（out number) = "）;scanf(”％d”， &n）;if(m 〈= 0 |｜ n <= 0）｛printf("Input Error\n”)；return 0;}// 建立链表pHead = (RingNodePtr)malloc（sizeof（RingNode））； pHead->pos = 1;pHead->next = NULL;CreateRing(pHead， m);// 开始出圈printf("\nKick Order： ")；KickFromRing(pHead， n）；printf(”\n"）;system(”pause”）；return 0；}//数组做：#include<stdio。

一维、二维数组及应用程序设计习题1、 【字符统计问题】题目描述：试统计用户键盘输入的一串英文字符中每种英文字符个数。

题目要求：⑴相同英文字符的大小写形式视为同一种统计对象；⑵遇到任意非英文字符时统计终止；⑶输出数据时每行仅输出10个数据。

输入数据：abcdeABCDElKlhmn2输出数据：A(2) B(2) C(2) D(2) E(2) F(0) G(0) H(1) I(0) J(0)K(1) L(0) M(1) N(1) O(0) P(0) Q(0) R(0) S(0) T(0) U(0) V(0) W(0) X(0) Y(0) Z(0)2、 【约瑟夫(猴子选大王)问题】题目描述：有M(1000以内)个猴子围成一圈，每个有一个编号，编号从1到M 。

打算从中选出一个大王。

经过协商，决定选大王的规则如下：从第一个开始，每隔N(任意正整数)个，数到的猴子出圈，最后剩下来的就是大王。

题目要求：从键盘输入M 、N(均为正整数)，试编程计算哪一个编号的猴子将成为大王。

输入数据：15 3 输出数据：5 200 55 93 3、 【行列互换问题】题目描述：试编程将一个二维数组行和列元素互换，存到另一个二维数组中。

例如：A =B = 4、 【矩阵初始化问题】题目描述：矩阵是线性代数中的重要概念及研究工具，在计算机算法设计中，我们常常选用二维数组之类的数据结构来描述矩阵。

下图是两个4×4的下三角方阵(即行列相等)初始化后的状态，请编程输出任意方阵(用户从键盘输入方阵的行列值)的这类初始化状态。

A 4×4 =B 4×4 =5、 【杨辉三角问题】题目描述：杨辉三角(出自其1261年所著的《详解九章算法》，也叫贾宪三角或帕斯卡三角)，它可以简单解释为由两个未知数和的幂次方运算后按某个未知数的降幂排列(或另一未知数的升幂排列)后的系数表(二项式定理)。

比如(x+y)0=1，系数为(1)；(x+y)1=x+y ，系数为(1、1)；(x+y)2=x 2+2xy+y 2，系数为(1、2、1)；(x+y)3=x 3+3x 2y+3xy 2+y 3，系数为(1、3、3、1)以及四次、五次、……等运算后所得的系数表，如下图(仅举5行)：题目要求：⑴利用一维数组试求用户给定行数的杨辉三角形；⑵利用二维数组试求用户给定行数的杨辉三角形(请尽力严格按照上图要求的输出格式)。

数据结构课程设计----个人设计报告专业：班级：姓名：学号：指导教师：日期： 2016年X月XX日至XX日目录1 课程设计目的 (3)2 课程设计内容和要求 (3)3 任务完成情况 (3)4 设计报告 (4)4.1顺序表应用 (4)4.1.1 设计目的 (4)4.1.2 设计内容及要求 (4)4.1.3 需求分析 (5)4.1.4 概要设计 (7)4.1.5 详细代码 (8)4.1.6 使用说明 (8)4.1.7 测试结果与分析 (8)4.1.8 参考文献 (10)4.2链表应用 (10)4.2.1 设计目的 (10)4.2.2 设计内容及要求 (11)4.2.3 需求分析 (12)4.2.4 概要设计 (14)4.2.5 详细代码 (16)4.2.6 使用说明 (16)4.2.7 测试结果与分析 (16)4.2.8 参考文献 (18)4.3树和二叉树 (19)4.3.1 设计目的 (19)4.3.2 设计内容及要求 (19)4.3.3 需求分析 (19)4.3.4 概要设计 (20)4.3.5 详细代码 (21)4.3.6 使用说明 (21)4.3.7 测试结果与分析 (22)4.3.8 参考文献 (22)5 体会与感想 (23)附录： (24)设计一（顺序表应用）的代码 (24)设计二（链表的应用）的代码 (35)设计三（二叉树应用）的代码 (47)1 课程设计目的1、学习获取知识的方法；2、提高发现问题、分析问题和解决实际问题的能力；3、加强创新意识和创新精神；4、加强团队的分工与合作；5、掌握面向实际背景思考问题的方法。

2 课程设计内容和要求内容：（仅供参考，请根据实际完成情况填写）第一章前言第二章顺序表与链表的应用第三章树结构的应用第四章图结构的应用第五章赫夫曼编码的应用要求：完成第2章、第3章中每章的比作必做任务。

在完成个人任务的基础上，完成第4章第5章的小组任务。

每人必须在完成个人任务的基础上提交个人任务的设计报告，内容包括：任务名称、目的、具体内容、需求分析、概要设计、主要代码分析、测试结果、收获与体会。

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

要求：m及n要求从键盘输入，存储方式采用向量及链表两种方式实现该问题求解。

#include <stdio.h>struct monkey{int num;monkey *next;};monkey *head,*tail;void creat(int n){int i;monkey *p,*q;p=new monkey; //为p分配内存空间p->num=1; //初始化p结点num域为1p->next=NULL; //初始化p结点next域为空head=p; //链表头指针head赋值为pq=p;for(i=2;i<=n;i=i+1) //循环存入猴子{p=new monkey; //为p配内存空间p->num=i; //初始化p结点num域为i，表示猴子号q->next=p; //将p点加到链表尾部q=p; //让指向链表尾部结点p->next=NULL; //链表尾部指向空}tail=q; //链表尾tail->next=head; //链表尾部指向链表头，形成循环链表}void select(int n){int x=0;monkey *p,*q;q=tail; //q赋值给tail，指向循环链表尾部do //直到型循环，用于循环删除指定间隔的结点{p=q->next; //p赋值给相邻的下一个结点x=x+1; //x加1if(x%n==0) //x是否整除m{printf("%d号猴子淘汰\n",p->num);q->next=p->next; //删除此结点delete p; //释放空间p=NULL;}else q=p; //q指向相邻的下一个结点p }while(q!=q->next); //剩余结点数不为1，则继续循环head=q; //head指向结点q,q为链表中剩余的一个结点}void main(){int n,m;head=NULL; //初始化head为空printf("请输入猴子的个数\n");scanf("%d",&m);printf("请输入n\n");scanf("%d",&n);creat(m); //调用函数creat建立循环链表select(n); //调用函数select，找出剩下的猴子printf("猴王是%d号\n",head->num); //输出猴王delete head; //删除循环中最后一个结点}#include<stdio.h>int main(){int a[1000];//定义一个较大的数组存储数据int m,n,x,count,i;//定义猴子数m、输入n、所需变量x、cout、iprintf("请输入猴子个数:\n");//提示输入mscanf("%d",&m);printf("请输入n:\n");//提示输入nscanf("%d",&n);for(i=1;i<=m;i++) //令数组与猴子编号对应a[i]=i;count=m;//令cout等于猴子个数x=0;//令x初始值为零for(i=0;count>1;i++)// 执行循环，淘汰的猴子值为-1，直到只剩一只猴子，即为猴王{if(a[i%m+1]!=-1) {x++;}if(x==n&&a[i%m+1]!=-1){a[i%m+1]=-1;count--;x=0;printf("%d号猴子淘汰\n",i%m+1);} }for(i=1;i<=m;i++) //输出值不为-1的猴子，即猴王if(a[i]!=-1) printf("猴王是%d号\n",i);}。

浙江师范大学数理与信息学院数据结构与算法分析报告班级：计算机051班曹玮（05190101）葛生生（05190107）董毅（04190107）指导老师：瞿有甜数理与信息工程学院《数据结构与算法设计》课程设计组号:无设计主题: 数据结构相关实现程序指导老师: 瞿有甜组长(学号): 曹玮（05190101）组员(学号):葛生生（05190107）、董毅（04190107）完成时间: 2007年1月26日需求分析：该程序实现菜单化、可视化、界面良好的输入和输出效果，各部分之间用模块连接。

第一部分模块实现输入功能，用户可根据提示按要求输入；在选择数字后，就进入了各个分模块中。

第一模块是约瑟夫环（Joseph）问题，这是一个模拟报数的问题，用户根据提示输入总的人数和要循环报的数，通过运行程序输出最后剩下的人的编号。

第二部分是有关二叉树的层序和先序遍历问题，输入结点数，建立二叉树，然后层序和先序输出结果。

第三部分是有关哈夫曼树的建立，输入要建立的哈夫曼树各结点的权值，按照最优生成树的建立方法建立哈夫曼树，最后输出最小全值。

第四部分是纸牌游戏，用户按要求输入和输出，这是一道典型的模拟题。

第五部分是有关图的广度优先遍历和深度优先遍历问题，输入各边的两端点和长度，建立存储结构，按两种方法输出。

第六部分是有关运动会分数统计的问题。

概要设计：第一部分：有关运动会分数统计的问题，涉及排序、搜索算法，用到结构体，链表的运用以及数组等数据结构，按要求实现即可。

第二部分：飞机定票系统，通过结构体，和两个单链表的运用完成飞机定票系统的各项功能设计，再在主函数里实现这些功能。

第三部分：约瑟夫环（Joseph）问题实际上是一个模拟问题，我们可以利用链表这一数据结构来求解，利用链表的删除结点来模拟人的退出，直到最后只剩下一个结点。

第四部分：猴子选大王的思想和约瑟夫环一样，不做分析。

第五部分：二叉树的层序和先序遍历问题，我们可以通过建立二叉树来实现这一要求，遍历可以用递归或非递归算法实现。

《数据结构》课程设计题目(程序实现采用C语言)题目1：猴子选王（学时：3）一堆猴子都有编号，编号是1，2，3 ...m，这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第n个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。

要求：m及n要求从键盘输入，存储方式采用向量及链表两种方式实现该问题求解。

n");return;}n", position+1);}}}ame,&stuff[i].department,&stuff[i].basepay,&stuff[i].allowance);if((fp=fopen("","wb"))==NULL){printf("Can't open file\n");return 0;}for(i=0;i<SIZE;i++)if(fwrite(&stuff[i],LENTH,1,fp)!=1)printf("文件写入出错\n");fclose(fp);if((fp=fopen("","rb"))==NULL){printf("Can't open file\n");}printf("修改过后的结果：\n");for(i=0;i<SIZE;i++){fread(&stuff[i],LENTH,1,fp);stuff[i].total=stuff[i].basepay+100+stuff[i].allowance;printf("%-10s%-10s %f %f %f\n",stuff[i].name,stuff[i].department,stuff[i].basepay+100,stuff[i].allowance,stuff[i ].total);}fclose(fp);return 0;}题目4：满足条件的有序表生成（学时：3）已知三个有序表A、B、C，它们皆由同一类元素构成，现要求对于表A作以下运算而获得有序表D：排出A中所有的既在B中又在C中出现的元素。

湖南人文科技学院计算机系课程设计说明书课程名称: 数据结构课程代码:题目: 猴子选大王年级/专业/班: 06级计算机科学与技术专业一班学生姓名:学号:06408109 06408102 06408107 0640812206408103指导教师: 刘刚常开题时间: 2008 年 6 月16 日完成时间: 2008 年 6 月29 日目录摘要 (3)一、引言 (4)二、设计目的与任务 (4)三、设计方案 (5)1、总体设计 (5)2、详细设计 (8)3、程序清单 (14)4、程序调试与体会 (22)5、运行结果 (23)四、结论 (24)五、致谢 (24)六、参考文献 (25)摘要本文首先介绍顺序表和链表并作以比较，我们分别使用循环队列和循环链表来解决猴子选大王的问题,程序使用了C语言编写,有很少一部分函数是用C++编写的，有比较详细的中文注释并在VC++下调试运行通过。

整个程序使用中文界面,并有相应的提示信息,便于操作和程序运行。

关键词：循环队列；循环链表；存储结构AbstractThis paper details the difference of sequence list and linklist.We respectively use queue and circular queue and circular linked list to solve the seek elected king of the monkey problem . The procedure write with C language ，a very small part function is used by the C + +,and has chinese explanatory note.What’s more,it was debugged in VC++ debugger and run very well.The whole procedure,with Chinese interface and thecorresponding hints,is convenient to run and easy to be operated.Keywords : circular queue；circular linked list ；storage structure《数据结构》课程设计——猴子选大王一、引言数据结构是一门非常重要的基础学科，但是实验内容大都不能很好的和实际应用结合起来。

讲题比赛讲稿一、问题的提出我今天要讲的是第12题。

题目为：有2015个同学站成一个圆圈，按顺时针方向编号：1—2015。

现在从1号开始，按“0、1、0、1、0、1……”的方式报数，报到1的同学立即离开，不再参与报数。

到最后只剩一个同学时报数停止。

请问最后留下的这个同学的编号是多少？二、问题分析这道题其实源于一道很有意思约瑟夫问题。

约瑟夫问题，有时也称为约瑟夫斯置换，是一个出现在计算机科学和数学中的问题。

据说著名犹太历史学家Josephus有过以下的故事：在罗马人占领乔塔帕特后，39个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数3该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。

然而Josephus 和他的朋友并不想遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。

回到我今天要讲的题目。

题目中将约瑟夫问题中的报数方式置换成“0、1、0、1……”循环报数，而且将结果也变成了“最后留下的同学的编号是多少？”虽然题目条件有了变化，但是仍然属于“约瑟夫问题”，可以用该类方法进行分析和解决。

三、问题的研究拿到题目以后，我们对此题的研究经历了三个阶段。

第一阶段：自我摸索阶段拿到题后，我简直有点懵。

说实话，我从来没有遇到过这样的题。

不过我想，通过网络搜索应该会有些眉目。

可是当我将原题输入百度以后，却找不到答案。

我只能对着题目，自己动手研究了。

首先我想到数的奇偶问题。

当总人数为奇数时，第一轮留下的是所有奇数编号；而到第二轮……情况比较复杂了。

而当总人数为偶数时，那么第一轮排除的是偶数编号；第二轮排除的就是4n的编号；第三轮时，剩下的编号可能是奇数个，怎么办呢？再次受挫的我只能像个小学生一样从最原始的方法开始模拟游戏过程。

我从3人开始研究3人留下的是3号；4人留下的是1号……当研究到8人留下是1号时，我恍如黑暗中窥见无限光明。