数据结构--猴子选大王

课程设计说明书

课题名称：猴子选大王

学生学号：

专业班级：计算机科学与技术

学生姓名：

学生成绩：

指导教师：

课题工作时间：至

摘要

本次程序程序设计的主要目的是解决变相的“约瑟夫环”问题---猴子选大王。从而使复杂的选举工作变得明朗化。

全程序以数据结构（C语言）中的循环单链表为主要的设计支柱，利用了C语言简洁紧凑、灵活方便，语法限制不太严格，程序设计自由度大，生成目标代码质量高，程序执行效率高等方面的优点。循环单链表是单链表的另一种形式，其结构特点是链表中最后一个结点的指针域不再是结束标记，而是指向整个链表的第一个结点，从而使链表形成一个环，基于这样的特点，它适合处理具有环形结构的数据元素序列。

在程序代码的编写中，运用了结构体类型（struct Node），动态申请内存空间函数malloc（），释放动态申请内存空间函数free（）等类型，同时也具有多种循环、条件语句控制程序流向，如：嵌套if else语句，多重for循环语句，还有链表中结点指针（p->next），从而使程序完全结构化。

这样编写出的完整程序代码可以实现“猴子选大王”功能，输入猴子的数目m，循环数n，对m个猴子进行编号，通过嵌套if else语句，for语句，一遍一遍的循环，判断，删除，直到只剩下最后一个猴子，即大王。这样就可以实现所需的基本功能了。关键词：数据结构；循环；单链表

Abstract

The main purpose of the program design process to solve the form of "Joseph Ring" in the election --- monkey king. So complex it became clear the election.

All procedures for data structures (C language) in single-cycle design of the main pillars of the list, using the C language simple and compact, flexible and convenient, the syntax is not strictly limited, program design flexibility to produce high quality object code, program execution the advantages of higher efficiency. Single-loop single-linked list is another form of list, its structural features is the last node list pointer field is no longer the end of the tag, but point to the list the first node, so that form a ring list, based on Such features, it has a ring structure for the data processing sequence of elements.

The preparation of the program code, the use of a structure type (struct Node), dynamic application memory function malloc (), the release of dynamic memory functions for free () and other types, but also with a variety of loop, conditional statements control program flow such as: nested if else statements, multiple for loop, there is a linked list node pointer (p-> next), to make the program fully structured.

Write such a code can achieve a complete "Monkey King selected" feature, enter the number of monkeys m, cycles n, for number of monkeys on the m-by nested if else statements, for statements, loop over and over again, judge, removed until there are only a monkey, or king. This can achieve the required basic function.

Keywords: data structures; circulation; single linked list

第一章课程设计目的与要求

1.1 课程设计目的

1、训练学生灵活应用所学数据结构知识，独立完成问题分析，结合数据结构理论知识，编写程序求解指定问题。

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

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

4.训练用系统的观点和软件开发一般规范进行软件开发，巩固、深化学生的理论知识，提高编程水平，并在此过程中培养他们严谨的科学态度和良好的工作作风

1.2 课程设计的实验环境

课程设计使用C语言工具，C语言作为一种最基本简单的程序设计语言，C语言发展迅速，而且成为最受欢迎的语言之一，主要因为它具有强大的功能。许多著名的系统软件，如DBASE Ⅳ都是由C 语言编写的。用C 语言加上一些汇编语言子程序，就更能显示C 语言的优势了，像PC- DOS 、WORDSTAR等就是用这种方法编写的。

常用的C语言IDE（集成开发环境）有Microsoft Visual C++，Dev-C++，Code::Blocks，Borland C++，Watcom C++ ，Borland C++ Builder，GNU DJGPP C++ ，Lccwin32 C Compiler 3.1，High C，Turbo C，C-Free， win-tc 等等……

对于一个初学者，Microsoft Visual C++是一个比较好的软件。界面友好，功能强大，调试也很方便

1.3 课程设计的要求

1、在处理每个题目时，要求从分析题目的需求入手，按设计抽象数据类型、构思算法、通过设计实现抽象数据类型、编制上机程序和上机调试等若干步骤完成题目，最终写出完整的分析报告。前期准备工作完备与否直接影响到后序上机调试工作的效率。在程序设计阶段应尽量利用已有的标准函数，加大代码的重用率。

2、.设计的题目要求达到一定工作量（300行以上代码），并具有一定的深度和难度。

3、程序设计语言推荐使用C/C++，程序书写规范，源程序需加必要的注释;

4、每位同学需提交可独立运行的程序；

5 、每位同学需独立提交设计报告书（每人一份），要求编排格式统一、规范、内容充实，不少于10页（代码不算）；

6、课程设计实践作为培养学生动手能力的一种手段，单独考核。

第二章课程设计内容

2.1 问题描述

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

2、基本要求：输入数据：输入m,n 为整数

3、输出形式：中文提示按照m个猴子，数n 个数的方法，输出为大王的猴子是几号，建立一个函数来实现此功能。

2.2需求分析

一群猴子（m个）按照编号的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。

程序规定：

(1)在程序中输入猴子数m、要报的数n

(2)，对猴子进行编号

(3)利用循环链表，依次序删除猴子，找出最后一个猴子，即为大王，输出这只猴子的编号

2.3具体设计和实现

1.对每一个猴子进行编号

r=q=(listnode *)malloc(sizeof(listnode));

for(i=1;i

p=(listnode*)malloc(sizeof(listnode));

q->data=i;

q->next=p;

q=p;

}

p->data=n;

p->next=r;

r=p;

2.每数到n便删除该猴子，当循环单链表只剩一个时，输出该编号for(i=1;i<=n-1;i++)

{

for(j=1;j<=k-1;j++)

p=p->next;

q=p->next;

p->next=q->next;

if(i % 10==0)

free(q);

}

printf("\n");

r=p;return r;

}

void outring(int n,linklist r)

{

int i;

listnode *p;

p=r;

printf("猴子大王：");

printf("%4d\n",p->data);

3.主函数

int main()

{

linklist r;

int n,k;

linklist initring(int n,linklist r);

linklist deletedeath(int n,int k,linklist r); void outring(int n,linklist r);

printf("请输入猴子总数m：");

scanf("%d",&n);

printf("请输入n：");

scanf("%d",&k);

r=initring(n,r);

r=deletedeath(n,k,r);

outring(n,r);

}

2.4运行结果分析

输入猴子的数目以及n

最后得到结果

运行结果如下：

得到了预期结果

第三章课程设计总结

次课程设计在整整一周的时间内得以完成，全部内容主要包括：目录，课题设计背景，详细设计，设计结果及分析等方面的内容，主要通过上网收集资料，查找参考书目，了解图书管理的设计背景，明确设计方向和内容，在此基础上形成了该课程设计的的基础框架。再进行源代码的创作以及整合，并及时上级进行调试，保证代码的有效性。具体内容在程序设计各章节均有体现。

在本次课程设计中，我收获了许多。

首先，在课程设计中通过对相关资料的搜索，设计猴子选大王实际上是一个约瑟夫环问题，设计这个程序比较简单，更重要的是在看到现象的同时我看到了它的本质，程序设计确实是一门神奇的工具，它可以通过普普通通的程序代码实现很多法在的流程，在减少人力劳动的同时，展现着科学的魅力。这样是我更加清楚地认识到自身存在的差距，所学的那点知识是远远不够的，学无止境才是真道理。

其次，课程设计的主要内容和目的是解决实际问题，同时运用所学的知识。这是我认识到了将知识活学活用的重要性。以往的我们只是简简单单的将书本上的知识以模板的形式刻入脑袋中，而在面对实际问题时却往往不知所措，这是理论泛滥带来的直接后果。这次的实践，让我将上学期所学的C语言和本学期所学的数据结构在实际的操作运用中进一步巩固，对于那些没有学透的知识，如，函数调用，结构体等，在不停摸索，商讨的过程中最终将它们一一解决，同时也新增了许多没有学到过的内容。

最后，对于我来说，独立完成这项课程设计是十分困难的，在学习和复习知识的过程中，难免要请教同学老师，他们的热心，让我感受到了团队的力量和团队的温暖，使我能顺利的完成任务。

课程设计的结束并不代表着学习的结束。这次的设计，把我带入到了一个全新的不曾接触过的领域，让我在以往只是注重操作的基础上，更多的思考到了，这是如何实现的，运用我所学到的知识是不是可以同样做出这样的网站，实现不一样的操作，达到同样的效果？我似乎有所领悟了，学习的本质不是让你牢牢的掌握一个知识，而是让你掌握一种方法，一种思想。同时，我知识的局限是毋庸置疑的，在纵多高级语言中，如，C++，JA V A ，C#，C语言编程是我目前唯一能做到的，并且还做得很不完善，所以在

以后的学习中一定要抓紧现在的大好时光扩充自己的知识储备，掌握更多的方法，为将来实现更多领域功能所用！同时本次课程设计让我学习知识的同时，也锻炼了自己面对新问题时的抗压能力，直面困难，不抛弃不放弃，坚持到底！在以后的学习和生活中，我将发扬这些优点，劈荆斩浪，挑战自我，一步一步往前走。

由于时间有限，本人水平有限，报告中可能存在诸多不完善之处，还望见谅。

参考文献

1.谭浩强著，C程序设计（第三版），北京：清华大学出版社。

2. Gary J.Bronson著，刘勇译，C++程序开发与设计（第二版）北京：人民邮电出版

社

3.朱站立编著，数据结构——使用C语言（第4版）北京：电子工业出版社

4.谭浩强，张基温，唐永炎编著，C语言程序设计教程，北京：高等教育出版社1992

5.谭浩强编著，C程序设计题解与上机指导（第二版），北京：清华大学出版社，1992

6.谭浩强编著，QBASIC语言教程，北京：电子工业出版社，1997

7.谭浩强编著，田数清编著，PASCAL语言程序设计（第二版），北京：高等教育出版

社，1998

8.C程序编写组，常用C语言用法速查手册，北京：龙门书局，1995

9.H M Peitel，P J Deitei.C How to progrom,second Edition. 蒋才鹏等译，C程序设计教

程，北京：机械工业出版社，2000

10.Herbert Schild著，王曦若，李沛译，ANSIC标准详解，北京：学院出

附录：源程序代码

#include

#include

typedef struct node

{

int data;

struct node *next;

}listnode;

typedef listnode *linklist;

linklist initring(int n,linklist r)

{

listnode *p,*q;

int i;

r=q=(listnode *)malloc(sizeof(listnode));

for(i=1;i

p=(listnode*)malloc(sizeof(listnode));

q->data=i;

q->next=p;

q=p;

}

p->data=n;

p->next=r;

r=p;

return r;

}

linklist deletedeath(int n,int k,linklist r)

{

int i,j;

listnode *p,*q;

p=r;

for(i=1;i<=n-1;i++)

{

for(j=1;j<=k-1;j++)

p=p->next;

q=p->next;

p->next=q->next;

if(i % 10==0)

free(q);

}

printf("\n");

r=p;return r;

}

void outring(int n,linklist r) {

int i;

listnode *p;

p=r;

printf("猴子大王："); printf("%4d\n",p->data);

}

int main()

{

linklist r;

int n,k;

linklist initring(int n,linklist r);

linklist deletedeath(int n,int k,linklist r); void outring(int n,linklist r);

printf("请输入猴子总数m：");

scanf("%d",&n);

printf("请输入n：");

scanf("%d",&k);

r=initring(n,r);

r=deletedeath(n,k,r);

outring(n,r);

}

用C编写程序猴子选大王

湖南人文科技学院计算机系 课程设计说明书 课程名称: 数据结构 课程代码: 题目: 猴子选大王 年级/专业/班: 06级计算机科学与技术专业一班 学生姓名: 学号:06408109 06408102 06408107 06408122

06408103 指导教师: 刘刚常 开题时间: 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++下调试运行通过。整个程序使用中文界面,并有相应的提示信息,便于操作和程序运行。 关键词：循环队列；循环链表；存储结构 Abstract This 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

猴子选大王课程设计报告

课程设计报告 课程设计题目：猴子选大王 学生姓名:吴兆 专业:软件工程 班级:1321813 学号:201320181306 指导教师:吴建东 2015年1 月9 日 东华理工大学

目录一：需求分析 1.问题描述 2.基本要求 3.需求分析 二：概念设计 三：详细设计 四：调试分析和测试结果五：总结 六：源代码

一：需求分析 1.问题描述 一堆猴子都有编号，编号是1，2，3 ...m ,这群猴子（m个）按照1-m 的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。 2.基本要求 输入数据：输入m,n m,n 为整数，n

程序流程图如下： 否 是 三：详细设计 1.程序中使用的存储结构struct L { int num; struct L *next; }; int n; int i=0; 2.程序中使用的循环结构开始 进行1-m的报数 删除第n只猴子 剩下的猴子 数是否为1 输出猴子大王的序号 结束

猴子选大王

一、猴子选大王课题描述 一堆猴子都有编号，编号是1，2，3 ...m ,这群猴子（m个）按照1 到m的顺序围坐一圈，从第1开始数，每数到第n个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。 猴子选大王系统设计 1、猴子选大王总体设计结构图 2、系统数据的数据结构设计 猴子的存放采用链式存储结构，利用循环链表来实现建立的，其表示方法是递归定义的. (1)、变量说明 程序中使用的存储结构:ListNode结构体 Struct ListNode{ Int data; //数据域 Struct ListNode *nextPtr; //指向后继结点的指针域 }; Int monkeys,count //分别为猴子的个数和猴子的报数 HeadPtr,tailPtr，currentPtr //分别为链表的头结点，尾结点和结点 HeadPtr1,headPtr2 //分别为选大王的单循环链表和由淘汰的猴子所构成的链表 (2)、函数说明

DestroyList (LISTNODEPTR headPtr) //用destroylist函数来释放选大王链表的各个结点 CreateList (int n) //创建循环链表，容纳n个猴子 Printf(“input the amount of monkeys:”) //用printf函数来提示输入的内容 Scanf(“%d”,&monkeys) //用scanf函数来输入猴子的个数 Printf(“input the count number:”) //用printf函数来提示报数的数 Scanf(“%d”,&count) //用scanf函数来输入每次数到的猴子就出局(3)、while循环说明 while(currentPtr1!=currentPtr1->nextPtr){ /*往后数一个猴子*/ prePtr1=currentPtr1; currentPtr1=currentPtr1->nextPtr; count++; /*若数到n，则淘汰currentPtr指向的猴子*/ if(count%n==0){ /*从headPtr1指向链表中拆下currentPtr指向的结点*/ prePtr1->nextPtr=currentPtr1->nextPtr; currentPtr1->nextPtr=NULL; /*将currentPtr1指向的结点插入到headPtr2指向链表中*/ if(headPtr2==NULL){/*若headPtr2指向的为空链表*/ headPtr2=currentPtr1; tailPtr2=currentPtr1; } else{ /*将拆下来的结点组装到headPtr2指向的链表上*/ tailPtr2->nextPtr=currentPtr1; tailPtr2=tailPtr2->nextPtr; } currentPtr1=prePtr1; /*currentPtr1指向上一个结点，为下一次数数做准备*/

数据结构--猴子选大王

课程设计说明书 课题名称：猴子选大王 学生学号： 专业班级：计算机科学与技术 学生姓名： 学生成绩： 指导教师： 课题工作时间：至

摘要 本次程序程序设计的主要目的是解决变相的“约瑟夫环”问题---猴子选大王。从而使复杂的选举工作变得明朗化。 全程序以数据结构（C语言）中的循环单链表为主要的设计支柱，利用了C语言简洁紧凑、灵活方便，语法限制不太严格，程序设计自由度大，生成目标代码质量高，程序执行效率高等方面的优点。循环单链表是单链表的另一种形式，其结构特点是链表中最后一个结点的指针域不再是结束标记，而是指向整个链表的第一个结点，从而使链表形成一个环，基于这样的特点，它适合处理具有环形结构的数据元素序列。 在程序代码的编写中，运用了结构体类型（struct Node），动态申请内存空间函数malloc（），释放动态申请内存空间函数free（）等类型，同时也具有多种循环、条件语句控制程序流向，如：嵌套if else语句，多重for循环语句，还有链表中结点指针（p->next），从而使程序完全结构化。 这样编写出的完整程序代码可以实现“猴子选大王”功能，输入猴子的数目m，循环数n，对m个猴子进行编号，通过嵌套if else语句，for语句，一遍一遍的循环，判断，删除，直到只剩下最后一个猴子，即大王。这样就可以实现所需的基本功能了。关键词：数据结构；循环；单链表

Abstract The main purpose of the program design process to solve the form of "Joseph Ring" in the election --- monkey king. So complex it became clear the election. All procedures for data structures (C language) in single-cycle design of the main pillars of the list, using the C language simple and compact, flexible and convenient, the syntax is not strictly limited, program design flexibility to produce high quality object code, program execution the advantages of higher efficiency. Single-loop single-linked list is another form of list, its structural features is the last node list pointer field is no longer the end of the tag, but point to the list the first node, so that form a ring list, based on Such features, it has a ring structure for the data processing sequence of elements. The preparation of the program code, the use of a structure type (struct Node), dynamic application memory function malloc (), the release of dynamic memory functions for free () and other types, but also with a variety of loop, conditional statements control program flow such as: nested if else statements, multiple for loop, there is a linked list node pointer (p-> next), to make the program fully structured. Write such a code can achieve a complete "Monkey King selected" feature, enter the number of monkeys m, cycles n, for number of monkeys on the m-by nested if else statements, for statements, loop over and over again, judge, removed until there are only a monkey, or king. This can achieve the required basic function. Keywords: data structures; circulation; single linked list

猴子选大王课程设计说明书

数学与计算机学院 课程设计说明书课程名称: 数据结构课程设计 课程代码: 6014389 题目: 猴子选大王 年级/专业/班: 2010级软件工程2班 学生姓名: 蒋童 学号: 开始时间: 2011 年11 月9 日 完成时间: 2011 年12 月30 日 课程设计成绩： 指导教师签名：年月日数据结构课程设计任务书

学院名称：数学与计算机学院课程代码：__ 6014389______ 专业：软件工程年级：2班 一、设计题目 猴子选大王 二、主要内容 一堆猴子都有编号，编号是1，2，3 ...m ,这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。 三、具体要求及应提交的材料 要求：使用数组和循环链表等两种以上的存储方式来做 输入数据：输入m,n m,n 为整数，n

六、推荐参考资料 [1] 严蔚敏，吴伟民.数据结构.清华大学出版社出版。 [2] 严蔚敏，吴伟民. 数据结构题集(C语言版) .清华大学出版社.2003年 5月。 [3] 唐策善，李龙澎.数据结构(作C语言描述) .高等教育出版社.2001年 9月 [4] 朱战立.数据结构(C++语言描述)（第二版本）.高等出版社出版.2004 年4月 [5] 胡学钢.数据结构(C语言版) .高等教育出版社.2004年8月 [6] 徐孝凯等著.数据结构（C语言描述）.清华大学出版社.2004 指导教师签名日期年月日 系主任审核日期年月日 目录 摘要................................. 错误！未定义书签。引言.................................. 错误！未定义书签。 1 需求分析.............................. 错误！未定义书签。 1.1任务与分析..................................... 错误！未定义书签。 1.2测试数据....................................... 错误！未定义书签。 2 概要设计.............................. 错误！未定义书签。 2.1 ADT描述....................................... 错误！未定义书签。 2.2程序模块结构................................... 错误！未定义书签。 2.21 结构体定义................................... 错误！未定义书签。 2.3 各功能模块.................................... 错误！未定义书签。 3 详细设计............................. 错误！未定义书签。

猴子选大王数据结构课程设计报告(内附详细注释)

1.需求分析 问题定义：一堆猴子都有编号，编号是1，2，3…n,这群猴子（n个）按照1-n的顺序围坐一圈，从第1个开始数，每数到第m个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。m，n键盘输入，且m

If(Ptr2==ptr+n) Ptr2=ptr; 保证猴子围成圈 N i++ Y N Y N Y break 3.详细设计 #include #include //使用calloc()函数 void FindKing_pointer(int,int,int*);//移动指针法找大王 void Initialize(int,int*);//初始化数组 整形和指针型 int main() { int m,n,*ptr; printf("输入猴子数与出局时报的数\n"); scanf("%d %d",&n,&m); while(n

猴子选大王循环链表实现

C++ n只猴子围成一圈，顺时针方向从1到n编号。之后从1号开始没顺时针方向让猴子从1，2，...，m依次报数，凡是报到m的猴子，就让其出圈，取消候选资格。然后不停地按顺时针方向逐一让报到m者出圈，是的剩下的一个就是猴王。 #include using namespace std; struct monkey //结构声明 { int num; //整型数，用于记录猴子号 monkey *next; //monkey结构指针 }; monkey *head,*tail; //monkey结构指针，全局变量 void creat(int nn) //被调用函数 { //函数体开始 int i; //整型变量i，用于计数 monkey *p,*q; //声明monkey结构指针p,q p=new monkey; //为p分配内存空间 p->num=1; //初始化p结点num域为1 p->next=NULL; //初始化p结点next域为空 head=p; //链表头指针head赋值为p q=p; //q赋值为p for(i=2;i<=nn;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; //链表尾部指向链表头，形成循环链表 } //被调用函数select,mm表示结点删除间隔 void select(int mm) { //函数体开始 int x=0; //声明整型值x，并初始化为0 monkey *p,*q; //声明指针变量p,q q=tail; //q赋值给tail，指向循环链表尾部 do //直到型循环，用于循环删除指定间隔的结点 {

数据结构上机实验程序--猴子选大王

#include #include struct Monkeyking { int data; struct Monkeyking *next; }; void main() { struct Monkeyking *head, *s, *q, *t,*p,*h; int n, k, count=0, i,j; printf("输入猴子总数:"); scanf("%d",&k); printf("\n"); printf("输入报号起始猴子编号:"); scanf("%d",&j); printf("\n"); printf("输入报号间隔数:"); scanf("%d",&n); printf("\n"); for(i=0; idata=i+1; s->next=NULL; if(i==0) { head=s; q=head; } else { q->next=s; q=q->next; } }//建立一个单链表 q->next=head;//将单链表组成环状 printf("输出猴子原始的编号:"); q=head; while(q->next!=head) { printf("%d ",q->data); q=q->next; }//依次输出节点的值

printf("%d ",q->data); printf("\n"); printf("\n"); q=head; for (i=0;inext; } q=p; printf("输出被淘汰的猴子编号:"); if (n==1) { for (i=1;i<=k;i++) { t=q; q=q->next; t->next=h; h=t; } for (i=1;i<=k;i++) { printf("%d ",h->data);//倒序输出淘汰猴子的编号，第一个编号为大王h=h->next; } printf("\n"); } else { do { count++; if(count==n-1) { t=q->next; q->next=t->next; t->next=h; h=t; count=0; } q=q->next; } while(q->next!=q); q->next=h; h=q;

数据结构课程设计 猴子选大王

题目：n只猴子要选大王，选举办法如下：所有猴子按1,2,3……n编号围成一圈，从第一圈开始顺序1，2……m报数，凡报到m号的退出圈外，如此循环报数，直到圈内只剩一只猴子时，这只猴子就是大王。 利用单向循环链表存储结构模拟此过程，输出选出的大王编号。 程序：#include #include #define n 19 #define m 4 typedef struct monkey { int num; struct monkey *next; } Monkey,*LINK; void main() { LINK p,head,p2; int i; head=p=p2=(LINK)malloc(sizeof(Monkey)); for(i=1;inext=p; p2=p; } p2->next=head; p=head; printf("对猴子进行编号！\n"); for(i=1;i<=n;i++) { p->num=i; printf("%d号猴子：%d\n",p->num,p->num); p=p->next; } i=0; p=head; while(1) { i++; printf("%d号猴子报：%d\n",p->num,i);if(p->next==p) break; if(i==m) { i=0; printf("%d号猴被淘汰\n",p->num);

printf("\n"); p2->next=p->next; p=p2->next; continue; } else { if(i==m-1) p2=p; p=p->next; } } printf("胜出:%d",p->num); } #include #include #define n 19 #define m 4 typedef struct monkey { int num; struct monkey *next; } Monkey,*LINK; void main() { LINK p,head,p2; int i; head=p=p2=(LINK)malloc(sizeof(Monkey));//三个指针指向同一块内存 for(i=1;inext=p; p2=p; }

猴子选大王课程设计说明书

数学与计算机学院 课程设计说明书 课程名称: 数据结构课程设计 课程代码: 6014389 题目: 猴子选大王 年级/专业/班: 2010级软件工程2班 学生姓名: 蒋童 学号: 312010********* 开始时间: 2011 年 11 月 9 日 完成时间: 2011 年 12 月 30 日 课程设计成绩： 指导教师签名：年月日

数据结构课程设计任务书 学院名称：数学与计算机学院课程代码：__ 6014389______ 专业：软件工程年级：2班 一、设计题目 猴子选大王 二、主要内容 一堆猴子都有编号，编号是1，2，3 ...m ,这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。 三、具体要求及应提交的材料 要求：使用数组和循环链表等两种以上的存储方式来做 输入数据：输入m,n m,n 为整数，n

按教学计划规定，数据结构课程设计为2周，其进度及时间大致分配如下： 六、推荐参考资料 [1] 严蔚敏，吴伟民.数据结构.清华大学出版社出版。 [2] 严蔚敏，吴伟民. 数据结构题集(C语言版) .清华大学出版社.2003年 5月。 [3] 唐策善，李龙澎.数据结构(作C语言描述) .高等教育出版社.2001年 9月 [4] 朱战立.数据结构(C++语言描述)（第二版本）.高等出版社出版.2004 年4月 [5] 胡学钢.数据结构(C语言版) .高等教育出版社.2004年8月 [6] 徐孝凯等著.数据结构（C语言描述）.清华大学出版社.2004 指导教师签名日期年月日 系主任审核日期年月日

C语言-猴子选大王

1.#include #include #include void SelectKing(int MonkeyNum, int CallNum); void main() { int MonkeyNum; int CallNum; /* 输入猴子的个数*/ printf("Monkey Num = "); scanf("%d", &MonkeyNum); /* 输入M的值*/ printf("Call Num = "); scanf("%d", &CallNum); SelectKing(MonkeyNum, CallNum); } void SelectKing(int MonkeyNum, int CallNum) { int *Monkeys; // 申请一个数组，表示所有的猴子； int counter = 0; //计数，当计数为猴子个数时表示选到最后一个猴子了； int position = 0; // 位置，数组的下标，轮流遍历数组进行报数； int token = 0; // 令牌，将报数时数到M的猴子砍掉； // 申请猴子个数大小的数组，把桌子摆上。 Monkeys = (int *)malloc(sizeof(int)* MonkeyNum); if (NULL == Monkeys) { printf("So many monkeys, system error.\n"); return; } // 将数组的所有内容初始化为0，被砍掉的猴子设置为1 memset(Monkeys, 0, sizeof(int)*MonkeyNum); // 循环，直到选中大王 while(counter != MonkeyNum)

猴子选大王C语言课程设计

猴子选大王 一、设计目的 1、能根据实际问题的具体情况，结合数据结构课程中的基本理论和基本算法，分析并正确确定数据的逻辑结构，合理地选择相应的存储结构，并能设计出解决问题的有效算法。 2、提高程序设计和调试能力。学生通过上机实习，验证自己设计的算法的正确性。学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改。 3、初步掌握软件开发过程中问题分析、系统设计、程序编码、测试等基本方法和技能。 4、训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。 5、培养根据选题需要选择学习书籍，查阅文献资料的自学能力。 二、设计内容 1、系统名称：猴子选大王 按照规定的要求，选出最后的一只猴子，为大王。 2、要求： 一堆有编号的猴子，编号为1，2，3……m，这群猴子（m个）按照1-m的顺序围坐一圈，从第一开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中剩下最后一只猴子，则该猴子为大王。 三、程序设计步骤 1）采用主要的数据结构类型。 采用了链表的存储方式，属于链接存储结构。

for(i=1;inext=p; p2=p; } 以下是用于存储结点的结构体的定义: typedef struct monkey { int num; struct monkey *next; } Monkey,*LINK; 基本算法： 这个算法的主要流程为： 从控制台读取猴子的数量和报数的最大数——>对猴子进行编号，并用链表来存储——>让链表中的猴子进行报数，对于报数为m的猴子则从链表中删除——>当链表中只剩下一个报数后则停止这个过程，这最后一个猴子即选出来的大王。 以下为为猴子建立链表： for(i=1;inext=p; p2=p; } 以下为猴子进行编号： for(i=1;i<=n;i++) //对猴子进行编号 { p->num=i; //printf("%d号猴子：%d\n",p->num,p->num); p=p->next; } 以下为最主要的算法过程，是通过一个While循环来控制的，是让猴子报数的过程，并删除报数为m的猴子： while(1) { i++; //当链表只剩最后一个元素了则跳出循环，此时报数已完成 printf("%d号猴子报：%d\n",p->num,i);if(p->next==p) break; if(i==m) { i=0; printf("%d号猴被淘汰\n",p->num); printf("\n");

常用经典算法(整理中)

Ｃ语言经典算法及程序 算法（Algorithm）：计算机解题的基本思想方法和步骤。算法的描述：是对要解决一个问题或要完成一项任务所采取的方法和步骤的描述，包括需要什么数据（输入什么数据、输出什么结果）、采用什么结构、使用什么语句以及如何安排这些语句等。通常使用自然语言、结构化流程图、伪代码等来描述算法。 一、一些简单算法 1.求两个整数的最大公约数、最小公倍数 2.判断素数 3.验证哥德巴赫猜想 4.超级素数 5.猴子选大王 6.数的全排列 7.迭代法求平方根 二、排序算法 1.选择排序 2.冒泡排序 3.插入排序 4.快速排序 5.第K小元素 6.二分查找法

三、高精度数算法 1.已知Ｐ，且P×S=11...1，求Ｓ及１的个数 2.高精度数加法 3.高精度数减法 4.高精度数乘法 5.高精度数除法 6.高精度数阶乘 7. Fibonacci数列 四、数据结构相关问题 1.左右括号配对 2.多项式相加 3.N叉树 五、复杂算法 1．N女王问题 六、动态规划实例应用 1．求序列的最大连续序列和 2．求序列的最长下降子序列长度 3．数塔问题（解法一） 4．数塔问题（解法二）

一、一些简单算法 1.求两个整数的最大公约数、最小公倍数 最大公约数算法：(最小公倍数=两个整数之积/最大公约数) (1) 对于已知两数m，n，使得m>n； (2) m除以n得余数r； (3) 若r=0，则n为求得的最大公约数，算法结束；否则执行(4)； (4) m←n，n←r，再重复执行(2)。 程序： #include "stdio.h" int main( ) { int nm,r,n,m,t; printf("please input two numbers:\n"); scan f("%d,%d”,&m,&n); nm=n*m; if (mn*/ r=m%n; while (r!=0) { m=n; n=r; r=m%n; } printf("最大公约数:%d\n",n); printf("最小公倍数:%d\n",nm/n); return 0;}

猴子选大王——课程设计

邮电与信息工程学院 课程设计说明书 课题名称：猴子选大王 学生学号： 专业班级： 学生姓名： 学生成绩： 指导教师： 课题工作时间：2010-6-22至2010-6-25

目录 摘要............................................................................................, (6) Abstract ......................................................................................, (7) 第一章课题背景.................................................................................,.. (8) 1.1课程设计的目的 (8) 1.2 课程设计的要求.............................................................................., (8) 1.3 课程设计的实验环境......................................................................,. (8) 第二章课程设计详细内容...................................................................,, (9) 2.1 问题描述......................................................................................,, (9) 2.2 程序代码精解.................................................................................,, (9) 2.3 程序结果运行...............................................................................,. (13) 总结......................................................................................., (15) 致谢.........................................................................................,.. (16) 参考文献.....................................................................................,.. (17) 附录主要程序代码....................................................................., (18)

猴子选大王问题

猴子选大王问题 集团文件版本号：（M928-T898-M248-WU2669-I2896-DQ586-M1988）

这是17世纪的法国数学家加斯帕在《数目的游戏问题》中讲的一个故事：15个教徒和15个非教徒在深海上遇险，必须将一半的人投入海中，其余的人才能幸免于难，于是想了一个办法：30个人围成一圆圈，从第一个人开始依次报数，每数到第九个人就将他扔入大海，如此循环进行直到仅余15个人为止。问怎样排法，才能使每次投入大海的都是非教徒。 *问题分析与算法设计 约瑟夫问题并不难，但求解的方法很多；题目的变化形式也很多。这里给出一种实现方法。 题目中30个人围成一圈，因而启发我们用一个循环的链来表示。可以使用结构数组来构成一个循环链。结构中有两个成员，其一为指向下一个人的指针，以构成环形的链；其二为该人是否被扔下海的标记，为1表示还在船上。从第一个人开始对还未扔下海的人进行计数，每数到9时，将结构中的标记改为0，表示该人已被扔下海了。这样循环计数直到有15个人被扔下海为止。 [编辑本段] 约瑟夫问题的一般形式： 约瑟夫问题是个有名的问题：N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。例如N=6，M=5，被杀掉的人的序号为5，4，6，2，3。最后剩下1号。

假定在圈子里前K个为好人，后K个为坏人，你的任务是确定这样的最少M，使得所有的坏人在第一个好人之前被杀掉。 C++代码示例: #include usingnamespacestd; voidmain() { intn,m,a[101],k,i,j,num;//计数器是从1开始的,所以100个人用101 cout<<"请输入参加游戏的玩家人数(不超过100人):"; cin>>n; cout<<"----------------------------------------"<100) { cout<<"玩家太多,请重新登陆此程序!"<

基础算法(一)枚举法

基础算法（一）枚举（穷举）法 无论什么类型的试题，只要能归纳出数学模型，我们尽量用解析方法求解，因为一个好的数学模型建立了客观事物间准确的运算关系。 在一时找不出解决问题的更好途径时，可以根据问题中的约束条件，将所有可能的解全部列举出来，然后逐一验证是否符合整个问题的求解要求。 一、枚举法的基本思想: 从可能的解集合中一一穷举各元素，用题目给定的检验条件判定哪些是有用的，哪些是无用的，能使命题成立的，即为其解。 这种思维方法主要是基于计算机运算速度快的特点。 二、枚举法解题思路： 1、对命题建立正确的数学模型； 2、根据命题确定数学模型中各变量的变化范围（即可能解的范围）； 3、利用循环语句、条件判断语句逐步求解或证明。 三、枚举法的特点： 算法简单，但运算量大。 对于可能确定解的范围，又一时找不到更好的算法时，可以采用枚举法。 1、求满足表达式A+B=C的所有整数解，其中A、B、C为1～3之间的整数。 2、鸡兔同笼问题（在同一个笼子里有鸡和兔子若干只，从上面看，能看到 20个头，从下面看，能看到60只脚，问鸡兔各有多少只？） 3、百钱百鸡问题（一百块钱要买一百只鸡，这一百只鸡必须包含母鸡、公 鸡和小鸡，其中，公鸡5元一只，母鸡3元一只，小鸡1元三只，问有哪些购买方案？） 4、水仙花数问题（ABC=A3+B3+C3,列出所有的整数ABC） 5、一根29厘米长的尺子，只允许在上面刻7个刻度，要能用它量出1～29 厘米的各种长度，试问刻度应该怎样选择？ 6、猴子选大王：有M个猴子围成一圈，每个有一个编号，编号从1到M。 打算从中选出一个大王。经过协商，决定选大王的规则如下：从第一个开始，每隔N个，数到的猴子出圈，最后剩下来的就是大王。 要求：从键盘输入M，N，编程计算哪一个编号的猴子成为大王。 参考程序：

猴子选大王问题

这是17世纪的法国数学家加斯帕在《数目的游戏问题》中讲的一个故事：15个教徒和15 个非教徒在深海上遇险，必须将一半的人投入海中，其余的人才能幸免于难，于是想了一个办法：30个人围成一圆圈，从第一个人开始依次报数，每数到第九个人就将他扔入大海，如此循环进行直到仅余15个人为止。问怎样排法，才能使每次投入大海的都是非教徒。 *问题分析与算法设计约瑟夫问题并不难，但求解的方法很多；题目的变化形式也很多。这里给出一种实现方法。 题目中30个人围成一圈，因而启发我们用一个循环的链来表示。可以使用结构数组来构成一个循环链。结构中有两个成员，其一为指向下一个人的指针，以构成环形的链；其二为该人是否被扔下海的标记，为1表示还在船上。从第一个人开始对还未扔下海的人进行计数，每数到9时，将结构中的标记改为0，表示该人已被扔下海了。这样循环计数直到有15个人被扔下海为止。[编辑本段] 约瑟夫问题的一般形式：约瑟夫问题是个有名的问题：N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。例如N=6，M=5，被杀掉的人的序号为5，4，6，2，3。最后剩下1号。 假定在圈子里前K个为好人，后K个为坏人，你的任务是确定这样的最少M，使得所有的坏人在第一个好人之前被杀掉。 C++代码示例: #i n c l u d e u s i n g n a m e s p a c e s t d; v o i d m a i n()

i n t n,m,a[101],k,i,j,n um; //计数器是从1开始的,所以100个人用101 c o u t<<"请输入参加游戏的玩家人数(不超过100人):"; c i n>>n; c o u t<<"----------------------------------------"<100) { c o u t<<"玩家太多,请重新登陆此程序!"<>m; c o u t<<"----------------------------------------"<