《数据结构课程设计-猴子选大王课程设计.doc》由会员分享，可在线阅读，更多相关《数据结构课程设计-猴子选大王课程设计.doc（18页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、 猴子选大王 湖北民族学院 数据结构课程设计 课题名称：猴子选大王 专业：计算机科学与技术 班级：0311401 姓名： 学号：031140105 指导老师： 一、设计题目猴子选大王二、 主要内容一堆猴子都有编号，编号是1，2，3 .m ,这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。三、具体要求及应提交的材料要求：使用数组和循环链表等两种以上的存储方式来做输入数据：输入m,n m,n 为整数，nm输出形式：中文提示按照m个猴子，数n 个数的方法，输出为大王的猴子是几号 ，建立一个函数来实现此
2、功能用C/C+语言编程实现上述内容，对每个问题写出一个算法实现，并按数学与计算机学院对课程设计说明书规范化要求，写出课程设计说明书。可采用数组、链表数据结构实现。在此基础上用C/C+实现其操作。五、推荐参考资料1 严蔚敏，吴伟民.数据结构.清华大学出版社出版。 2 严蔚敏，吴伟民. 数据结构题集(C语言版) .清华大学出版社.2003年5月。3 唐策善，李龙澎.数据结构(作C语言描述) .高等教育出版社.2001年9月4 朱战立.数据结构(C+语言描述)（第二版本）.高等出版社出版.2004年4月5 胡学钢.数据结构(C语言版) .高等教育出版社.2004年8月6 徐孝凯 等著.数据结构（C语
3、言描述）.清华大学出版社.2004 目 录 摘 要3引 言41 需求分析41.1任务与分析41.2链表定义41.3主函数实现调用操作52详细设计93 调试分析144用户使用说明155测试结果15结 论16致 谢16参考文献16摘 要 随着计算机的普及，涉及计算机相关的科目也越来越普遍，其中数据结构是计算机专业重要的专业基础课程与核心课程之一，为适应我国计算机科学技术的发展和应用，学好数据结构非常必要，然而要掌握数据结构的知识非常难，所以对“数据结构”的课程设计比不可少。本课程设计主要通过使用循环链表、数组、以及单向链表，将猴子编号来数据化待选猴子坐成一个圈，并对圈内的猴子进行报数选取大王。最终
4、输出选出的猴子大王的编号。考虑到循环链表、数组、以及单向链表要使用不同的结构体、算法等，故将不同的三种方法设计为分开的三个类。只在主函数中调用其相应的函数。程序通过调试运行，结果与预计结果一致，初步实现了设计功能。关键词：现代版；队列（循环链表）；队列（数组）；单向链表 ；数据结构 引 言 A、 课程设计任务本课程设计主要实现在循环链表、数组、单向链表三种不同存储结构下对问题（即：“一堆猴子都有编号，编号是1，2，3 .m ,这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。”）实现要求。依据猴子
5、的编号数据化将猴子用以上方式存储。并进行报数入队，与出队操作。最终输出最后一位猴子编号，该猴子为此次当选的猴王。B、课程设计性质数据结构课程设计是重要地实践性教学环节。在进行了程序设计语言课和数据结构课程教学的基础上，设计实现相关的数据结构经典问题，有助于加深对数据结构课程的认识。本课程设计是数据结构中的一个关于数组、链表等算法的实现，包括在存储结构中添加、删除操作，最后把结果输出。此课程设计要求对数组存储结构和链表存储结构非常熟悉，并能熟练使用它们。C、课程设计目的其目的是让我们在学习完C+、数据结构等课程基础上，掌握数据的存储结构、掌握数据相应的存储，添加，更新等操作，并用输出结果。进一步
6、掌握设计、实现较大系统的完整过程，包括系统分析、编码设计、系统集成、以及调试分析，熟练掌握数据结构的选择、设计、实现以及操作方法，为进一步的应用开发打好基础。1 需求分析1.1任务与分析猴子选大王，众多猴子纷纷想成为大王，以一统群族。更便享有最高的地位与权利，因而导致猴子间惨重的事件发生。在现代发展的社会中不管人类还是猴子都不想看到如此不幸的画面。故利用计算机软件来解决血腥的冲突。即将编号为1，2，n的一群猴子按照1-n的顺序围坐成一个圈，所以可以用数组将其以循环的方式存储，输入猴子的总数m与要报的数n，且保证ndata = 1; p-next = p; /* 初始化循环链表 */ for (
7、i = 2; i data = i; s-next = p-next; p-next = s; p = p-next; /* 找到第 k 个节点 */ p = head; for (i = 1; i next; /* 保存节点总数 */ total = n; printf(nOut of sequence:); q = head; /* 只剩一个节点时停止循环 */ while (total != 1) /* 报数过程，p指向要删除的节点 */ for (i = 1; i next; /* 打印要删除的节点序号 */ printf(%d , p-data); /* q 指向 p 节点的前驱 *
8、/ while (q-next != p) q = q-next; /* 删除 p 节点 */ q-next = p-next; /* 保存被删除节点指针 */ s = p; /* p 指向被删除节点的后继 */ p = p-next; /* 释放被删除的节点 */ free(s); /* 节点个数减一 */ total-; /* 打印最后剩下的节点序号 */ printf(nn King of the Monkey is the No. %d nn, p-data); free(p); system(pause); return 0;2.详细设计程序代码：#include #include
9、/* 定义链表节点类型 */typedef struct node int data; struct node *next;linklist; int main() int i, n, k, m, total; linklist *head, *p, *s, *q; /* 读入问题条件 */ printf(Please enter the number of monkeys:); scanf(%d, &n); printf(Please enter from the monkeys began to count off the first of several:); scanf(%d, &k)
10、; printf(Please enter the number out:); scanf(%d, &m); /* 创建循环链表，头节点也存信息 */ head = (linklist*) malloc(sizeof(linklist); p = head; p-data = 1; p-next = p; /* 初始化循环链表 */ for (i = 2; i data = i; s-next = p-next; p-next = s; p = p-next; /* 找到第 k 个节点 */ p = head; for (i = 1; i next; /* 保存节点总数 */ total =
11、n; printf(nOut of sequence:); q = head; /* 只剩一个节点时停止循环 */ while (total != 1) /* 报数过程，p指向要删除的节点 */ for (i = 1; i next; /* 打印要删除的节点序号 */ printf(%d , p-data); /* q 指向 p 节点的前驱 */ while (q-next != p) q = q-next; /* 删除 p 节点 */ q-next = p-next; /* 保存被删除节点指针 */ s = p; /* p 指向被删除节点的后继 */ p = p-next; /* 释放被删除
12、的节点 */ free(s); /* 节点个数减一 */ total-; /* 打印最后剩下的节点序号 */ printf(nn King of the Monkey is the No. %d nn, p-data); free(p); system(pause); return 0;3 调试分析 由于此次的课程设计题目所需要的相关知识大多数可在数据结构书中找到，或借鉴。所以在完成代码后运行时，没出现严重错误和问题。只是有点小问题，即局部变量用错：没定义的也用了。调试并找出错误，进行修改。最后获得成功。4用户使用说明该系统具有简单、明了、使用等特点，能够方便、准确的计算出众多猴子编号选举大王
13、的结果。当使用该系统时，系统会给出相关的提示信息，用户只需根据提示信息，即可完成系统提供的所有功能。5测试结果结 论在课程设计中，首先要看清问题，将问题要求理解透彻，在构思要如何实现，要用到哪些函数，要用什么算法，在课程设计构思中选算法是一个很重要的概念。只有确定用什么算法后才能接下来的工作，将流程图画在纸上，再进行代码的编写。在程序设计中编写代码只是一个方面，调试才是关键，它是一个相当繁琐的过程。有许多新的问题需要被解决，但同时它也是个比较重要的过程，在调试中，你会学到很多新的东西，从而增加你编程能力和经验。通过本次实习，温固了数据结构的相关知识，加深了对课内所学的有关数据的逻辑结构和存储表
14、示、数据结构的选择合应用、算法的设计和时空效率分析等内容的理解，进一步熟悉了C+的应用与编程环境，巩固并提高了分析问题，解决问题的能力。 致 谢在本次课程设计过程中，首先感谢学校相关领导给了我一次提升实力的机会。其次要感谢监督我完成该实验的老师，是她在我需要必要帮助时，申出了援助之手。还要感谢教过我C+语言和数据结构的各位老师，是他们的授课，让我打下了完成该实验的基础。最后，感谢身边的同学们、朋友们以及网友们，是你们给了我完成该实验的思路、方法。 参考文献1杨宝刚.开展企业管理信息化工作的步骤J.企业管理.2002.（11）.12152Islamabad. Software tools for forgery detectionJ. Business line.2001. (5）. 2932 3王立柱.C/C+与数据结构.北京：清华大学出版社，20024顾元刚.数据结构简明教程.南京：东南大学出版社等，20035郭福顺，王晓芬，李莲治数据结构（修订本），大连理工大学出版社，199717