猴子选大王——课程设计.doc

武汉工程大学邮电与信息工程学院 综合设计报告邮电与信息工程学院课程设计说明书课题名称： 猴子选大王 学生学号： 专业班级： 学生姓名： 学生成绩： 指导教师： 课题工作时间： 2010-6-22 至 2010-6-25 一、课程设计的任务的基本要求：1、设计前提部分 现在需要用数据结构（C语言）解决“猴子选大王”的问题，具体问题如下：一堆猴子都有编号，编号是1，2，3 .m ,这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。 要求解决问题的程序必须满足以下条件：1、输入数据：输入m,n 为整数2、输出形式：中文提示按照m个猴子，数n 个数的方法，输出为大王的猴子是几号，建立一个函数来实现此功能。3、使用循环单链表实现。2、课程设计部分 设计系统的主页面显示模式形如： Input the number of monkeys:4 Input the cycle number: 3 对猴子进行编号： 第1位猴子的编号为： 1 第2位猴子的编号为： 2 第3位猴子的编号为： 3 第4位猴子的编号为： 4 要删除的猴子号为： 2要删除的猴子号为： 4要删除的猴子号为： 3The king monkeys number is 1指导教师签字： 年 月 日 二、进度安排：1、程序设计十七周：周二周五 上午8：30-11：30 下午2：30-5：002、撰写课程设计报告十八周：周一周二 自行安排时间3、程序演示和课程设计报告提交十八周：周三周五 三、收集的资料及主要参考文献1.谭浩强著，C程序设计（第三版），北京：清华大学出版社。2. Gary J.Bronson著，刘勇译，C+程序开发与设计（第二版）北京：人民邮电出版社3.朱站立编著，数据结构使用C语言（第4版）北京：电子工业出版社4.谭浩强，张基温，唐永炎编著，C语言程序设计教程，北京：高等教育出版社19925.谭浩强编著，C程序设计题解与上机指导（第二版），北京：清华大学出版社，19926.谭浩强编著，QBASIC语言教程，北京：电子工业出版社，19977.谭浩强编著，田数清编著，PASCAL语言程序设计（第二版），北京：高等教育出版社，19988.C程序编写组，常用C语言用法速查手册，北京：龙门书局，19959.H M Peitel，P J Deitei.C How to progrom,second Edition. 蒋才鹏等译，C程序设计教程，北京：机械工业出版社，200010.Herbert Schild著，王曦若，李沛译，ANSIC标准详解，北京：学院出版社，1994四、成绩评定：指导教师评语： 指导教师签字： 2010 年 月 日项 目评价项 目评价调查论证工作量、工作态度实践能力分析、解决问题能力质 量创 新得 分目 录摘 要 ., 6Abstract .,. 7第一章 课题背景.,.8 1.1课程设计的目的.81.2 课程设计的要求., 81.3 课程设计的实验环境.,. 8第二章课程设计详细内容 .,. 92.1 问题描述.,.92.2 程序代码精解.,.92.3 程序结果运行.,.13总 结 .,. 15致 谢 .,.16参考文献 .,.17附录 主要程序代码 .,.18 摘 要本次程序程序设计的主要目的是解决变相的“约瑟夫环”问题-猴子选大王。从而使复杂 的选举工作变得明朗化。全程序以数据结构（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 complete program code can have a monkey king selected feature, enter the number of monkeys m, cycles n, m were monkeys on the number, by nested if else statements, for statement, the cycle 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课程设计要求针对本次猴子数为，循环数为的猴子选大王问题，要求如下：1、基本要求：输入数据m,n 为整数。2、输出形式：中文提示按照m个猴子，数n 个数的方法，输出为大王的猴子几号，建立一个函数来实现此功能。3、实现方案：使用循环单链表。1.3课程设计实验环境本次课程设计使用的是以C语言为基础的数据结构，C语言作为一种最基本简单的程序设计语言，C语言发展迅速，而且成为最受欢迎的语言之一，主要因为它具有强大的功能。同时数据结构中的循环单链表适用于解决具有环形结构的数据元素序列。许多著名的系统软件，如DBASE 都是由C 语言编写的。用C 语言加上一些汇编语言子程序，就更能显示C 语言的优势了，像PC- DOS 、WORDSTAR等就是用这种方法编写的。1.3.1 C语言和循环单链表所具有的特点归纳起来C 语言具有下列特点1.C是结构式语言。结构式语言的显著特点是代码及数据的分隔化。这种结构化方式可使程序层次清晰，便于使用、维护以及调试。2.C语言功能齐全。具有各种各样的数据类型，并引入了指针概念，可使程序效率更高。另外C语言也具有强大的图形功能，支持多种显示器和驱动器。3.C语言适用范围大。适合于多种操作系统，如Windows、DOS、UNIX等等；也适用于多种机型。4.C语言文件由数据序列组成，可以构成二进制文件或文本文件常用的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 等等循环单链表具有的特点：1.操作灵活。单链表中的每个结点，是在需要时才向系统申请，即动态内存申请，节省了大量内存空间。2.循环单链表是单链表的另一种形式，其结构特点是链表中最后一个结点的指针域不再是结束标记，而是指向整个链表的第一个结点，从而使链表形成一个环，基于这样的特点，它适合处理具有环形结构的数据元素序列。第二章 课程设计详细内容在本章节，主要介绍符合要求的程序代码的具体分析。其各个部分的的具体功能,以及显示出的具体结果。2.1问题描述一堆猴子都有编号，编号是1，2，3 .m ,这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。【要求】 输入整型数据m，n，输出的形式按照中文提示，m个猴子，数n个数的方法，输出为大王的猴子是几号，由此建立一个函数来实现此功能，最好使用循环单链表。2.2程序代码精解完整的程序代码参见后文附表，现进行小部分解说。2.2.1头文件说明1# include此程序主要以C语言为编写语言，因此在程序中要用到系统提供的标准库函数中的输入，输出函数，例如：scanf()函数,printf()函数。所以必须在程序开头一行写上#include。例如，程序中用到的相关函数就有printf(tttinput the number of monkey:)；scanf(%d,&m)；等。2#include在这个程序中，用到的主要是数据结构中的循环单链表方面的相关知识。我们把由一个数据元素域及一个或若干个指针域组成的结构体称为一个结点。而在单链表中的每个结点，实在需要时才向系统申请的，也就是所谓的动态内存空间申请。动态申请的内存空间，当不再需要时，必须由申请者自己释放。C语言提供了动态申请内存空间的函数malloc（）和动态释放内存空间的函数free（）。这些函数都包含在头文件malloc.h中。所以也必须在程序开头写上#include。例如，head=q=p=(monkey *)malloc(sizeof(monkey)；这一句就是申请占用字节个数为sizeof(monkey)的monkey类型的一个结点，并且让head，q，p三个指针同时指向这个结点。 3. typedef int DataType; 我们都知道，没有实际含义的数据元素称作抽象数据元素。在设计时遇到抽象数据元素，我们将用DataType表示该抽象数据元素的数据类型；而当软件设计问题具体确定时，抽象数据元素的数据类型将被具体的数据类型所取代。在本程序中，要求线性表的数据类型为int类型，可以通过重新定义抽象数据元素为int类型，来确定该抽象数据元素的数据类型。即相应的C语句为typedef int DataType;。2.2.2 结构体说明 typedef struct Node DataType data; struct Node *next;monkey; 我们把由一个数据元素域及一个或若干个指针域组成的结构体称为一个结点，其中数据域用来存放数据，指针域用来构造数据元素之间的关联关系。 所以函数中定义了单链表的结构体struct Node，其中data域用来存放数据素，next域用来存放下一个结点的指针。monkey是struct Node类型的变量。且链表的结点结构如图2-1datanext 2-1 单链表的结点2.2.3 main（）函数说明 void main() monkey *head,*p,*q,*s; int m,n,i; printf(tttinput the number of monkey:); scanf(%d,&m); printf(n); printf(tttinput the cycle number: ); scanf(%d,&n); printf(n); printf(ttt对猴子进行编号:nn); head=q=p=(monkey *)malloc(sizeof(monkey); for(i=1;idata=i; p-next=q; p=q; printf(ttt第%d位猴子的编号是t%dn,q-data,q-data); q-next=head; head-data=m; p=head; q=p-next; printf(ttt第%d位猴子的编号是t%dn,p-data,m); printf(n); if(m=1) printf(ntttthe king monkeys number is 1n); else if(m!=1) if(n=1)for(i=1;i=m;i+)printf(ttt要删除的猴子号为t%dn,i); printf(ntttthe king monkeys number is %dn,m);elsefor(i=1;inext; q=q-next;if(i=n-1)printf(ttt要删除的猴子号为t%dn,q-data);s=q;q=q-next;p-next=q;free(s);i=0;m-;if(m=1) break;printf(ntttthe king monkeys number is t%dn,q-data);1.在相关有效的提示信息后输入m，n：printf(tttinput the number of monkey:); scanf(%d,&m); printf(n); printf(tttinput the cycle number: ); scanf(%d,&n);2. 通过for语句，为m只猴子申请m-1个节点,并将从1m的猴子依次放入前m-1个节点中,将第m个猴子放入head结点中。且对猴子编号编好后的单链表如图2-2所示。printf(ttt对猴子进行编号:nn); head=q=p=(monkey *)malloc(sizeof(monkey); for(i=1;idata=i; p-next=q; p=q; printf(ttt第%d位猴子的编号是t%dn,q-data,q-data); q-next=head; head-data=m; p=head; q=p-next; printf(ttt第%d位猴子的编号是t%dn,p-data,m);printf(n);m123m-1 head p q 2-2 构建好的具有m个结点单链表3.对具体的m个猴子，分不同的情况找出大王：当m=1时，不论n为何值，大王就是这个编号为1的猴子；如：if(m=1) printf(ntttthe king monkeys number is 1n);当m!=1，但n=1时，前m-1个猴子均要删除，最后留下的第m个猴子就是大王；如：else if(m!=1) if(n=1) for(i=1;i=m;i+) printf(ttt要删除的猴子号为t%dn,i); printf(ntttthe king monkeys number is %dn,m); 当m!=1，但n!=1时,根具具体的代码（如下）求出大王.如：else for(i=1;inext; q=q-next; if(i=n-1) printf(ttt要删除的猴子号为t%dn,q-data); s=q; q=q-next; p-next=q; free(s); i=0; m-; if(m=1) break; printf(ntttthe king monkeys number is t%dn,q-data);2.3程序结果运行 如图2-3,根据提示信息输入相对应的m，n值： 2-3 输入数据m，n 由上图知，假设输入的m=4，n=3，则对猴子进行编号，并且通过循环单链表对猴子进行删除如图2-4：2-4 对4个猴子进行编号 最后显示最后留下来的猴子的号码，即为猴子大王，如图2-5： 2-5 显示猴子大王号码 总 结本次课程设计在整整三天的时间内得以完成，全部内容主要包括：目录，课题设计背景，详细设计，设计结果及分析等方面的内容，主要通过上网收集资料，查找参考书目，了解图书管理的设计背景，明确设计方向和内容，在此基础上形成了该课程设计的的基础框架。再进行源代码的创作以及整合，并及时上级进行调试，保证代码的有效性。具体内容在程序设计各章节均有体现。在本次课程设计中，我收获了许多。首先，在课程设计中通过对相关资料的搜索，是我对图书管理方面的流程有了一定的认识，更重要的是在看到现象的同时我看到了它的本质，程序设计确实是一门神奇的工具，它可以通过普普通通的程序代码实现很多法在的流程，在减少人力劳动的同时，展现着科学的魅力。这样是我更加清楚地认识到自身存在的差距，所学的那点知识是远远不够的，学无止境才是真道理。其次，课程设计的主要内容和目的是解决实际问题，同时运用所学的知识。这是我认识到了将知识活学活用的重要性。以往的我们只是简简单单的将书本上的知识以模板的形式刻入脑袋中，而在面对实际问题时却往往不知所措，这是理论泛滥带来的直接后果。这次的实践，让我将上学期所学的C与语言在实际的操作运用中进一步巩固，对于那些没有学透的知识，如，函数调用，结构体等，在不停摸索，商讨的过程中最终将它们一一解决，同时也新增了许多没有学到过的内容。最后，对于我来说，独立完成这项课程设计是十分困难的，在学习和复习知识的过程中，难免要请教同学老师，他们的热心，让我感受到了团队的力量和团队的温暖，使我能顺利的完成任务。课程设计的结束并不代表着学习的结束。这次的设计，把我带入到了一个全新的不曾接触过的领域，让我在以往只是注重操作的基础上，更多的思考到了，这是如何实现的，运用我所学到的知识是不是可以同样做出这样的网站，实现不一样的操作，达到同样的效果？我似乎有所领悟了，学习的本质不是让你牢牢的掌握一个知识，而是让你掌握一种方法，一种思想。同时，我知识的局限是毋庸置疑的，在纵多高级语言中，如，C+，JAVA ，C#，C语言编程是我目前唯一能做到的，并且还做得很不完善，所以在以后的学习中一定要抓紧现在的大好时光扩充自己的知识储备，掌握更多的方法，为将来实现更多领域功能所用！同时本次课程设计让我学习知识的同时，也锻炼了自己面对新问题时的抗压能力，直面困难，不抛弃不放弃，坚持到底！在以后的学习和生活中，我将发扬这些优点，劈荆斩浪，挑战自我，一步一步往前走。由于时间有限，本人水平有限，报告中可能存在诸多不完善之处，还望见谅。致 谢 本次课程设计在选题上，指导老师刘老师给了我细心地指导。同学们也给了我极大地帮助。在程序的编写过程中由于个人知识的局限，导致有许多的问题一时不能发现，耗费了大量的时间却也得不到及时有效地解决，思路也不够开阔，而时间有十分紧张。问题接踵而来时，我一度的不知所措，幸好有老师和同学们，在我遇到困难的时候，在我想放弃的时候不断的支持我，鼓励我，帮助我分析思路，打开视角。老师严谨求实的求学态度，踏实坚忍的工作精神，将使我受益终身。同学们热情无私的帮助与关怀将使我有更大的动力面对更多的困难。再多华丽的语言也显苍白。在此，谨向给予我帮助的刘老师和同学们致以诚挚的感谢和崇高的敬意。感谢寝室的室友们对我的帮助。由于时间的紧迫，我每天必须起早贪黑的上网查资料，写东西。不管我再怎么注意，再怎么消息，敲打键盘时发出的声音，显示屏的光亮，必定会打扰到她们。感谢她们给与我的理解和包容。感谢在这次程序设计中所有帮助过我和理解我的人。参考文献1.谭浩强著，C程序设计（第三版），北京：清华大学出版社。2. Gary J.Bronson著，刘勇译，C+程序开发与设计（第二版）北京：人民邮电出版社3.朱站立编著，数据结构使用C语言（第4版）北京：电子工业出版社4.谭浩强，张基温，唐永炎编著，C语言程序设计教程，北京：高等教育出版社19925.谭浩强编著，C程序设计题解与上机指导（第二版），北京：清华大学出版社，19926.谭浩强编著，QBASIC语言教程，北京：电子工业出版社，19977