用C++编写程序 猴子选大王
湖南人文科技学院计算机系
课程设计说明书
课程名称: 数据结构
课程代码:
题目: 猴子选大王
年级/专业/班: 06级计算机科学与技术专业一班
学生姓名:
学号:06408109 06408102 06408107 06408122 06408103 指导教师: 刘刚常
开题时间: 2008 年 6 月 16 日完成时间: 2008 年 6 月 29 日
目录
摘要 (2)
一、引言 (3)
二、设计目的与任务 (3)
三、设计方案 (4)
1、总体设计 (4)
2、详细设计 (6)
3、程序清单 (10)
4、程序调试与体会 (14)
5、运行结果 (15)
四、结论 (16)
五、致谢 (16)
六、参考文献 (16)
摘要
本文首先介绍顺序表和链表并作以比较，我们分别使用循环队列和循环链表来解决猴子选大王的问题,程序使用了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
《数据结构》课程设计
——猴子选大王
一、引言
数据结构是一门非常重要的基础学科，但是实验内容大都不能很好的和实际应用结合
起来。从而让很多学生认为学习数据结构并没有很大的作用。但本实验运用数据结构的知识，很好的解决了一个对于人脑来说比较烦琐的实际问题。
链表是一种以链式结构存储的线性表，特点是数据元素可以用任意的存储单元存储，线性表中逻辑上相邻的两元素存储空间可以是不连续的。同时为了表示逻辑关系，每个数据元素除了存放自身的数据信息外还要存储一个指示其直接后继的信息。队列是一种先进先出的线性表。它只允许在的表的一端进行插入，而在另一端删除元素。循环队列是队列的顺序表示和实现。从时间上考虑顺序表中插入和删除元素的时间复杂度为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的顺序依次进入该队列，再按题目要求把被淘汰的猴子踢出队列，使用两个循环把被淘汰猴子的编号和猴王的编号分别输出。 本设计使用循环队列求解猴子选大王的问题，程序中定义的数据结构如下： 定义一个循环队列typedef struct SqQueue 进队列int EnQueue(SqQueue &Q,QElemType e) 出队列int DeQueue(SqQueue &Q,QElemType &e) 主程序包含模块： typedef struct SqQueue { //定义一个循环队列 }SqQueue; int InitQueue(SqQueue &Q) { //初始化} int EnQueue(SqQueue &Q,QElemType e) { //进队列 } //EnQueue() end { //出队列} //DeQueue() end int QueueLength(SqQueue Q) { //返回Q的元素个数，即队列的长度} // QueueLength() end void exit() { } void Change(SqQueue &Q) { //选大王} void main() { SqQueue Q; InitQueue(Q); Change(Q); } 2）使用链表存储结构实现 我们选择用一个循环链表来完成该设计，设计一个猴子的结构体, 并开辟空间用来存储猴子结构，生成了一个猴子结构的循环链表，对链表中的猴子进行编号，报号到n的猴子被淘汰，最后剩下的猴子为猴王，把依次被淘汰的猴子和猴王输出。 本设计使用循环链表求解猴子选大王的问题，程序中定义的数据结构如下： 设计一个猴子的结构体typedef struct monkey 开辟空间用来存储猴子结构head=p=p2=(LINK)malloc(sizeof(Monkey)) 开辟新空间用来存各个猴子结构p=(LINK)malloc(sizeof(Monkey)) 把链表变成循环链表p2->next=head 报号为n的猴子被淘汰，最后剩下的是猴王，输出被淘汰的猴子和猴王 while(1) { if(i==m){ printf("%d号猴被淘汰\n",p->num)} else{ //没有报到m的继续报数} printf("猴王的编号为:%d",p->num);} 3）菜单选择函数程序 int menu_select() // { printf(" \t\t 猴子选大王系统\n"); printf(" \t\t 1 使用顺序表\n"); printf(" \t\t 2 使用链表\n"); printf(" \t\t 请选择：") ; 2、详细设计 1）使用顺序存储结构实现 (1) 输入m，n.m是猴子的总个数，n是小于m的正整数数。 (2) 把m只猴子编上好“1，2，3……m”然后按照1--m的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。 (3) 输出最后剩下的那只猴子的编号，这猴子就是大王。 (4) 对结果进行分析 本程序设计中所包括的函数如下: typedef int QElemType; typedef struct SqQueue //定义一个循环队列{ 、、、、、、、、、、、、、、、、、、、、、、、、、、、、、 }SqQueue; int InitQueue(SqQueue &Q) //初始化{ 、、、、、、、、、、、、、、、、、、、、、、、、、、、、、 } int EnQueue(SqQueue &Q,QElemType e) //进队列{ 、、、、、、、、、、、、、、、、、、、、、、、、、、、、、 } //EnQueue() end int DeQueue(SqQueue &Q,QElemType &e) //出队列{ 、、、、、、、、、、、、、、、、、、、、、、、、、、、、、 } //DeQueue() end int QueueLength(SqQueue Q) //返回Q的元素个数，即队列的长度{、、、、、、、、、、、、、、、、、、、、、、、、、、、、、 } // QueueLength() end void exit() { } void Change(SqQueue &Q)//选大王 { int n,m; int e; cout<<"输入猴子总数:"; cin>>m; for(int j=1;j<=m;j++) EnQueue(Q,j); cout<<"从第1个开始数，每数到第n个，该猴子将离开此圈"< cout<<"请输入n:"< cin>>n; cout<<"被淘汰猴子的顺序为:"; if(n { while(QueueLength(Q)!=1) //当只剩下一个元素时循环结束，依次输出被淘汰猴子编号{ for(int i=0;i { e=DeQueue(Q,e); EnQueue(Q,e); } e=DeQueue(Q,e); cout< } while(Q.front!=Q.rear) //循环到最后找出猴王 { for(int i=0;i { e=DeQueue(Q,e); EnQueue(Q,e); } e=DeQueue(Q,e); } cout<<"猴王是编号为"< Change(Q); } } void main() { SqQueue Q; InitQueue(Q); Change(Q); } 2）使用链表存储结构实现 (1) 设计一个猴子的结构体,typedef struct monkey (2) 输入m，n.m是猴子的总个数，n是小于m的正整数数。 (3)开辟空间用来存储猴子结构，生成了个猴子结构的链表，并使其循环。head=p=p2=(LINK)malloc(sizeof(Monkey)); for(i=1;i { p=(LINK)malloc(sizeof(Monkey)); p2->next=p; p2=p; } p2->next=head; } (4) 找出所有被淘汰的猴子编号和猴王的编号，并将其输出。 while(1) i++; if(p->next==p) break; if(i==n) { i=0; p2->next=p->next; printf("%d",p->num); p=p2->next; } else { if(i==n-1) p2=p; p=p->next; } } printf("猴王的编号为:%d\n",p->num); } 3）主菜单选择程序和主函数 int menu_select() //菜单选择函数程序 { int x; printf(" \t\t 猴子选大王系统\n"); printf(" \t\t 1 使用顺序表\n"); printf(" \t\t 2 使用链表\n"); printf(" \t\t 请选择：") ; for(;;) { scanf("%d",&x); if(x<=0 || x>2) printf("\n\t输入错误，重选1-2："); else break; return x; } } void main() { switch(menu_select()) { case 1: SqQueue Q; Change(Q); break; return; case 2: monkey(); break; return; } } 3、程序清单 #include #include #include #include # define STACK_INIT_SIZE 100 # define STACKINCREMENT 10 # define MAXQSIZE 100 # define OK 1 # define ERROR 0 typedef int QElemType; typedef struct SqQueue //定义一个循环队列 { QElemType *base; int front; int rear; }SqQueue; int InitQueue(SqQueue &Q) //构造一个空队列Q { Q.base=(QElemType *)malloc(MAXQSIZE*sizeof(QElemType)); if(!Q.base) return ERROR; //存储分配失败 Q.front=Q.rear=0; return OK; } int EnQueue(SqQueue &Q,QElemType e) //进队列 { if((Q.rear+1)%MAXQSIZE==Q.front) return ERROR; //队列满 Q.base[Q.rear]=e; Q.rear=(Q.rear+1)%MAXQSIZE; return OK; } //EnQueue() end int DeQueue(SqQueue &Q,QElemType &e) //出队列 return ERROR; e=Q.base[Q.front]; Q.front=(Q.front+1)%MAXQSIZE; return e; } //DeQueue() end int QueueLength(SqQueue Q) //返回Q的元素个数，即队列的长度 { return(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;} //QueueLength() end void exit() { } void Change(SqQueue &Q)//选大王 { int n,m; int e; cout<<"输入猴子总数:"; cin>>m; for(int j=1;j<=m;j++) EnQueue(Q,j); cout<<"请输入n:"< cin>>n; cout<<"被淘汰猴子的顺序为:"; if(n { while(QueueLength(Q)!=1) //当只剩下一个元素时循环结束，依次输出被淘汰的猴子编号 { for(int i=0;i { e=DeQueue(Q,e); EnQueue(Q,e); } e=DeQueue(Q,e); cout< } while(Q.front!=Q.rear) //循环到最后找出猴王 { for(int i=0;i e=DeQueue(Q,e); EnQueue(Q,e); } e=DeQueue(Q,e); } cout<<"猴王是编号为"< Change(Q); } } typedef struct monkey //设计一个猴子的结构体,该结构体用monkey表示 //link表示该结构体的指针 { int num; //它的号码 struct monkey *next; //下个猴子的地址指针 } Monkey,*LINK; void monkey() { int n,m; printf("请输入猴子总数m的值:\n"); scanf("%d",&m); printf("请输入n的值:\n"); scanf("%d",&n); printf("被淘汰猴子的顺序为:"); LINK p,head,p2; //定义了三个猴子结构的指针 int i; head=p=p2=(LINK)malloc(sizeof(Monkey));//开辟空间用来存储猴子结构 for(i=1;i { p=(LINK)malloc(sizeof(Monkey)); //开辟新空间用来存各个猴子结构 p2->next=p; p2=p; } p2->next=head;//这步很重要,这样链表变成循环链表了,也就是说链表到了结//尾它的下个地址就是链表头了如此不停循环下去,就是个圆 p=head; for(i=1;i<=m;i++) { p->num=i; //对猴子编号 p=p->next; //指针指向下个猴子 } //所有猴子编号结束 i=0; p=head; //又将p指向了链表的头 while(1) i++; if(p->next==p)//这是结束条件,你想自己的下一个就是自己本身了,是不是说//明只剩下自己了,也就是大王了 break; if(i==n) //如果这一个报到了数n { i=0; //再次从1开始报数,因为以后要执行i++语句 p2->next=p->next;//将该猴子从链表中拿下 printf("%d",p->num); //这个号码的猴子要被淘汰 p=p2->next;//指针指向下一个猴子 } else //没有报到m的继续报数 { if(i==n-1) p2=p; p=p->next; } } printf("猴王的编号为:%d\n",p->num); } int menu_select() //菜单选择函数程序 { int x; printf(" \t\t 猴子选大王系统\n"); printf(" \t\t 1 使用顺序表\n"); printf(" \t\t 2 使用链表\n"); printf(" \t\t 请选择：") ; for(;;) { scanf("%d",&x); if(x<=0 || x>2) printf("\n\t输入错误，重选1-2："); else break; return x; } } void main() { switch(menu_select()) case 1: SqQueue Q; InitQueue(Q); Change(Q); break; return; case 2: monkey(); break; return; } } 4、程序调试与体会 程序调试的步骤： 1)调试各个模块函数,并测试模块间参数的传递与调用。 2)调试主函数和对其他模块函数的调用，并检验最后的输出结果。 本程序还算比较简单，用链表存储结构不是很复杂，在使用循环链表的程序中最主要的是定义一个结构体，然后构造一个循环链表并为其在结构体中开辟存储空间。但是真正的程序中还要考虑各种限制条件，这就给调试过程带来一些问题，例如在出队列的过程中，可能队列已经为空队列，就要给出该队列为空队列此信息的提示，还有在使用循环队列的程序中我们刚开始只能输出猴王的编号，却不能输出各个被淘汰猴子的编号，后来才发现是循环控制的不对，在使用循环链表的程序中我们刚开始调试根本不出结果，后来发现是在编号和循环函数之前没返回链表的表头。通过本次课程设计，我们学到了很多东西：首先，平时在学理论知识时觉得很简单容易的知识，实践起来并不是那么容易。比如最基础的构造结构体，要完全不出错的用自己的语言输到屏幕上，却要求对相关知识的掌握熟练到一定程度。又如，循环的次数不能多也不能少，否则就会导致输出结果不是所需的。 其次，只有理论知识没实践经验是不可能成为一名出色的软件设计师的。理论是实践的基础，实践是对所学知识的巩固与提高，只有理论与实践相结合才能真正掌握知识。 再次，我们还懂得了团结精神的重要性。设计思路是最重要的，只有大家讨论出来的设计思路才是清晰的，这是程序设计成功的关键。在本次程序设计过程中，大家共同努力，分工合作，一起到图书馆找资料，找范文，并在网上搜索了大量的资料，共同学习，使得我们共同进步。一个人的力量是有限的，但团结的力量是无穷的。在竞争如此激烈的当今社会，这些东西都是终生实用的，为我们以后的工作和学习奠定了基础。 最后，这次程序设计提炼了我们的心理素质。设计过程是一个考验人耐心的过程，不能有丝毫的急躁，马虎。在不影响试验的前提下可以加快进度。必须要有耐心，要有坚持的毅力。程序需要反复调试，其过程很可能相当烦琐，而且在程序调试出来后写报告书也是一个很繁琐的过程，有时花很长时间写出来的报告书还是需要重写，那时心中未免有点灰心，有时还特别想放弃，此时更加需要静下心，查找原因。 5、运行结果 主菜单函数运行结果如图1所示，主菜单函数是一个选择函数 图 1 有两种选择，输入你要选择的一项 使用顺序表程序运行结果如图2所示，输入选择1，输入猴子总数和n的值 图2 猴子总数为6，n为2，依次被淘汰的猴子是24631号，猴王为5号 使用链表程序运行结果如图3所示，输入选择2，输入猴子总数和n的值 图3 猴子总数为9，n为4，依次被淘汰的猴子是48396572号，猴王为1号 四、结论 经过将近两周的数据结构课程设计，我们分别使用循环链表和循环队列的一些基本操作终于完成实现猴子选大王的设计，猴子选大王的过程如果用人脑来计算完成的话会十分浪费脑力和精力，但是我们选用了计算机编程这个工具使问题就简单而且容易操作了。过程中遇到了很多困难，设计结果也不够简洁完美，但大体上符合设计要求，解决了猴子选大王这个对于人脑来说比较复杂繁琐的问题。 五、致谢 首先，我们要感谢学校给我们提供了这么好的学习环境和空间，让我们有机会在一起学习与研究，让我们有机会进行理论知识的实践。 其次，我们还要特别感谢我们的辅导老师袁辉勇老师，如果没有他的帮助和指导，我想我不可能学到这么多知识，可能还得摸索更长一段时间。在我们遇到不能解决的设计问题时，只要去问袁老师，他都会很高兴并且耐心的指导我们，使设计最后得以完成，同时，在袁老师的身上我们学到了很多实用的知识，袁老师是个专业知识功底非常深厚扎实且对学生和学术要求都十分严格的好老师。对袁老师我们再次表示忠心的感谢！ 祝学校越办越好，前途更加光明与灿烂；祝袁老师工作顺利，生活愉快。 六、参考文献 [1]严蔚敏等，数据结构（C语言版）.北京清华大学出版社, 2005年 [2]严蔚敏等，数据结构题集（C语言版）. 北京清华大学出版社， 2005年 [3]苏仕华等，数据结构课程设计. 机械工业出版社， 2005年 课程设计任务书及成绩评定 课题名称：_ 猴子选大王 完成者：李伟民李一可袁川华张志明周伟波 1、设计的目的与要求： 1)训练学生灵活应用所学基本知识，熟练的完成问题分析、算法设计、编写程序； 2)初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能 并培养学生进行规范化软件设计的能力。； 3)提高综合运用所学的理论知识和方法独立分析和解决问题的能力； 4)训练用系统的观点和软件开发一般规范进行软件开发，巩固、深化学生的理论知识， 提高编程水平，并在此过程中培养他们严谨的科学态度和良好的工作作风。 5）使学生掌握使用各种计算机资料和有关参考资料，提高学生程序设计的基本能力。 2、设计进度及完成情况 3、成绩评定： 设计成绩：（教师填写） 指导老师：（签字） 湖南人文科技学院计算机系 课程设计说明书 课程名称: 数据结构 课程代码: 题目: 猴子选大王 年级/专业/班: 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 C++ n只猴子围成一圈，顺时针方向从1到n编号。之后从1号开始没顺时针方向让猴子从1，2，...，m依次报数，凡是报到m的猴子，就让其出圈，取消候选资格。然后不停地按顺时针方向逐一让报到m者出圈，是的剩下的一个就是猴王。 #include 题目：n只猴子要选大王，选举办法如下：所有猴子按1,2,3……n编号围成一圈，从第一圈开始顺序1，2……m报数，凡报到m号的退出圈外，如此循环报数，直到圈内只剩一只猴子时，这只猴子就是大王。 利用单向循环链表存储结构模拟此过程，输出选出的大王编号。 程序：#include 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 printf("%d ",q->data); printf("\n"); printf("\n"); q=head; for (i=0;i 数学与计算机学院 课程设计说明书 课程名称: 数据结构课程设计 课程代码: 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 指导教师签名日期年月日 系主任审核日期年月日 猴子选大王 一、设计目的 1、能根据实际问题的具体情况，结合数据结构课程中的基本理论和基本算法，分析并正确确定数据的逻辑结构，合理地选择相应的存储结构，并能设计出解决问题的有效算法。 2、提高程序设计和调试能力。学生通过上机实习，验证自己设计的算法的正确性。学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改。 3、初步掌握软件开发过程中问题分析、系统设计、程序编码、测试等基本方法和技能。 4、训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。 5、培养根据选题需要选择学习书籍，查阅文献资料的自学能力。 二、设计内容 1、系统名称：猴子选大王 按照规定的要求，选出最后的一只猴子，为大王。 2、要求： 一堆有编号的猴子，编号为1，2，3……m，这群猴子（m个）按照1-m的顺序围坐一圈，从第一开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中剩下最后一只猴子，则该猴子为大王。 三、程序设计步骤 1）采用主要的数据结构类型。 采用了链表的存储方式，属于链接存储结构。 for(i=1;i 1.#include 数据结构课程设计报告 目录 第一章设计目的 (3) 第二章设计任务及要求 (3) 一、基本要求 (3) 二、内容 (3) 第三章题目分析与解答 (4) 一、仓库管理系统 (4) 1.题目要求 (4) 2.应用程序功能 (4) 3.输入数据类型、格式和内容限制 (6) 4.主要模块的算法描述 (6) 5.源程序代码 (7) 二、通讯录管理系统 (13) 1.题目要求 (13) 2.应用程序功能 (13) 3.输入数据类型、格式和内容限制 (15) 4.主要算法模块描述 (16) 5.源程序代码 (16) 三、猴子选大王 (22) 1.题目要求： (22) 2.应用程序功能 (22) 3.输入数据类型、格式和内容限制 (23) 4.主要算法模块描述 (23) 5.源程序代码 (23) 四、二叉树运算2 (26) 1.题目要求 (26) 2.应用程序功能 (26) 3.输入数据类型、格式和内容限制 (26) 4.主要算法模块描述 (26) 5.源程序代码 (28) 第一章设计目的 一、培养学生运用算法与数据结构的基本知识解决实际编程中的数据结构设计和算法设计问题。 二、培养学生独立设计程序与解决问题的能力，培养学生团队协作集成程序模块及调试能力。 三、培养学生初步的软件设计及软件测试的能力。 第二章设计任务及要求 一、基本要求 学生必须仔细阅读《数据结构》课程设计指导书，认真主动完成课设的要求。有问题及时主动通过各种方式与教师联系沟通。 学生要发挥自主学习的能力，充分利用时间，安排好课设的时间计划，并在课设过程中不断检测自己的计划完成情况，及时的向教师汇报。 课程设计按照教学要求需要一周时间完成，一周中每天（按每周5天）至少要上3-4小时的机来调试C语言设计的程序，总共至少要上机调试程序15小时。 根据设计报告要求编写设计报告，主要内容包括目的、意义、原理和实现方法简介、过程分析及说明、实验结果情况说明、结论。 每个人必须有可运行的程序，学生能对自己的程序面对教师提问并能熟练地解释清楚，学生回答的问题和程序运行的结果作为评分的主要衡量标准。 二、内容 本次课程设计完成如下模块：仓库管理系统、通讯录管理系统、猴子选大王及二叉树运算2。 Ｃ语言经典算法及程序 算法（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 (m 上海应用技术学院课程设计报告 课程名称《数据结构课程设计》 设计题目猴子选大王；建立二叉树；各种排序；有序表的合并；成绩管理系统；院系计算机科学与信息工程专业计算机科学与技术班级 姓名学号指导教师日期 一.目的与要求 1. 巩固和加深对常见数据结构的理解和掌握 2. 掌握基于数据结构进行算法设计的基本方法 3. 掌握用高级语言实现算法的基本技能 4. 掌握书写程序设计说明文档的能力 5. 提高运用数据结构知识及高级语言解决非数值实际问题的能力 二.课程设计内容说明 1. 项目一 (1) 对设计任务内容的概述 学生成绩管理** 任务：要求实现对学生资料的录入、浏览、插入和删除等功能。 输入：设学生成绩以记录形式存储，每个学生记录包含的信息有：学号和各门课程的成绩，设学生成绩至少3门以上。存储结构：采用线性链式结构。 (2) 详细设计 LinkList *create()：输入学生成绩记录函数； void print(LinkList *head)：显示全部记录函数 LinkList *Delete(LinkList *head)：删除记录函数 LinkList *Insert(LinkList *head)：插入记录函数 void menu_select()：菜单选择 void ScoreManage()：函数界面 (3) 程序流程图 (4) 程序模块及其接口描述 该程序可以分为以下几个模块： 1、菜单选择：void menu_select(); 提供五种可以选择的操作，在main函数中通过switch语句调用菜单menu_select()函数，进入不同的功能函数中完成相关操作。 2、输入功能：LinkList *create(); 通过一个for循环语句的控制，可以一次完成无数条记录的输入。并将其存入链 邮电与信息工程学院 课程设计说明书 课题名称：猴子选大王 学生学号： 专业班级： 学生姓名： 学生成绩： 指导教师： 课题工作时间：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用C编写程序猴子选大王
猴子选大王课程设计报告
猴子选大王
数据结构--猴子选大王
猴子选大王课程设计说明书
猴子选大王数据结构课程设计报告(内附详细注释)
猴子选大王循环链表实现
数据结构课程设计 猴子选大王
数据结构上机实验程序--猴子选大王
猴子选大王课程设计说明书
猴子选大王C语言课程设计
C语言-猴子选大王
推荐-数据结构课程设计报告仓库管理系统、通讯录管理系统、猴子选大王、 精品
常用经典算法(整理中)
数据结构课程设计(附代码)
猴子选大王——课程设计
猴子选大王问题