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

1、数据结构课程设计报告题目：猴子选大王采用循环链表及动态存储的实现班 级：计算机082班姓 名：指导教师：成 绩： 信息工程学院 2010年01 月 20 日 目录课程设计摘要(题目) 03 032.需求分析 04 问题分析 04 总体设计 05 07模块分析 07链表循环输入删除输出07各个函数之间的调用关系 09 10 12函数设计 12 135.测试结果 16 18 19参考文献 20摘要(题目):猴子选大王任务：一堆猴子都有编号，编号是1，2，3 .m ,这群猴子m个按照1-m的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，那么该

2、猴子为大王。要求：输入数据：输入m,n ；m,n 为整数n<m输出形式：中文提示按照m个猴子，数n 个数的方法，输出为大王的猴子是几号 ，建立一个函数来实现此功能随着计算机科学的迅速开展，计算机已深入到揉合社会的各个领域，它的应用已不再局限于科学计算，以解决一些数学问题，而且可以解决一些抽象化的具体问题，更多地用于控制，管理及数据处理等非数值计算的处理工作，这便为我们的日常生活提供了很多的方便，譬如说火车、飞机售票系统，学生成绩管理，商品管理系统，医院选址等实际问题。如今程序设计的语言很多，有开展比拟完善高级语言，也有最根本的低级语言，然而再好的程序设计也要有一个比拟清晰的思路算法。为了

3、编写好一个好程序，必须分析待处理对象的特性以及各处理对象之间的关系，于是数据结构便成为我们绝佳的选择。数据结构是计算机程序设计的重要理论技术根底，它不仅是计算机科学的核心课程，而且已成为其他理工专业的热门选修课。数据结构是计算机程序设计的重要理论根底，它不仅是计算机学科一门专业技术根底课，它对学习者的的要求很明确：学会分析、研究计算机加工的数据结构的特性，以便为应用设计所需的数据选择适当的逻辑结构、存储结构及其相应的算法，并初步掌握算法的时间分析和空间分析的技术。其次，该课程的学习过程也是复杂程序设计的训练过程，要求学习者编写的程序结构或设计的程序结构体清楚、正确、易读，符合软件工程的标准。循

4、环链表是一种重要的链式结构，其特殊性在于需附设两个指针分别指示表头元素及表尾元素的位置且表头和表尾相邻接，臆造的环状空间巧妙的解决了需循环依次删除元素的约瑟夫问题。本设计采用目前最通用的程序设计语言之一C语言作为数据结构和算法的描述语言，单循环链表作为数据存储结构。 充分考虑了循环链表的特点仅通过对两个循环链表的出、入列操作，就简单的实现了要求，动态的模拟出了猴子选大王问题中猴子循环报数的情况。该程序通俗易懂且实用性强，其他类似的算法均可借鉴和参考使用。并且该程序清单详细具体、全面、具有很强的可读性。2.需求分析 根据问题描述得知，该问题中m个猴子围坐在一起形成首尾相接的环，因此可用循环链表解

5、决。从第n个猴子开始出列相当于从链表中删除一个结点。该程序主要有三个模块组成，建立循环链表，报数利用循环链表实现猴子的出列，最终剩下的猴子即猴王。具体步骤如下：    第一步  首先创立循环链表。第二步 向链表中填入猴子的编号    第二步  找第一个开始报数的猴子。    第三步  数到n让这个猴子出列第四步  接着开始报数，重复第三步，直到剩下最后一个猴子，它就为大王！ 2.2总体设计 采用两个循环队列反复出队列与入队列来进行“舞伴配对。程序中主要用到

6、以下抽象数据类型：1) 设定链表抽象数据类型的定义ADT struct 对象数据整数 操作对象:struct monkey *create() 建立循环链表 struct monkey *findout(start,n) 找出被淘汰的猴子的上一个 Struct monkey *letout(last) 删掉被淘汰的猴子，返回的指针值指向下一个猴子。根本操作(1) initring(int n,linklist r) 操作结果：构造一个具有n个元素的循环链表r。(2) iinklist delete(int n,int k,linklist r)初始条件：链表r已存在。操作结果：循环依次删除问题

7、对应所需位置的元素并当即输出其值，用指针r记录其最后元素的位置。ATD linklist(3) outring(int n,linklist r)特殊输出链表保存的最后一个元素，即猴子大王的序号。程序包含两个模块a. 主程序模块，其中主函数为void main输入猴子的信息；根据输入要求进行删除和输出；剩下一个猴子后，输出结果；b. 循环链表模块实现具体删除输出操作。2) 两模块之间的简单调用关系主函数模块循环队列模块循环链表模块图1 模块调用图3.概要设计链表循环输入删除输出程序包含两个模块(1) 主程序模块，其中主函数为void main输入猴子的信息；根据输入要求进行删除和输出；剩下一个

8、猴子后，输出结果；(2) 循环链表模块实现具体删除输出操作。 a.输入功能：当用户执行的猴子信息时，系统会提示用户输入猴子总数m和猴子的报号数n，输入完后，执行收索查找功能 b.收索查找功能：在输入的猴子总数和猴子报号数后，猴子开始进行按1至n循环报数第1个猴子开始报数1，第2个猴子报数2，第n个猴子报数n，找出该猴子，第n+1个猴子报数1，第n+2个猴子报数2，在循环链表循环报数至释放剩最后一个猴子释放节点，找出猴子王结点。c.释放功能：当用户执行的检索完猴子信息后，系统会提示用户已释放出费猴子大王节点和猴子大王结点的编号信息，该算法具体的实现：设计一个循环，找到要删除的结点p以及它的前驱结

9、点front，然后执行front->next=p->next; e=p->shifang;释放结点p并且返回被删除猴子的编号。删除函数为：void Delete - ()删除算法的图形表示为：当猴子报号数n时： 图2 循环链表释放结点循环链表模块图层分析具体如以下图2所示循环链表模块输入功能删除释放功能报数查找功能释放出非猴子大王结点释放出猴子大王图3 链表循环删除输出模块各个函数之间的调用关系整个函数调用关系：主函数由数据输入、链表循环删除输出操作、数据输出等组成如以下图3所示主函数最后元素输出操作链表循环删除输出操作数据输入输出猴子大王序号图4 函数调用关系图如以下图5

10、流程图所示设定链表抽象数据类型的定义ADT struct 对象数据猴子总数，m为整数 操作对象:struct monkey *create() 建立循环链表 struct monkey *findout(start,n) 找出被淘汰的猴子的上一个 Struct monkey *letout(last) 删掉被淘汰的猴子，返回的指针值指向下一个猴子。在循环链表填入数据：猴子总数m、报号数nfrontàdata= =n?= = n-1？建立循环单链表定义结构体及变量front、rear、m、n结束开始释放第n个猴子，指针front指向第n+1个结点rear=rear->next猴王

11、就是第rear-data 个猴子front= =rear?= = n-1？front +YNNY输出已删除的猴子节点和猴子大王结点 图5 流程图4.详细设计4.1函数设计程序设计中主要包括以下函数LinkList initring(int n,linklist r) 构造一个含n个元素的循环链表;LinkList delete(int n,int k,linklist r) 循环删除报k号的元素； 循环输出所删除的元素；记录链表最后所保存的元素的位置；void main ( )void outring(int n,linklist r) 输出链表最后保存的元素，即猴子大王的序号；4.2程序源代

12、码#include "stdio.h" #include "stdlib.h" typedef struct node int data; struct node *next; listnode,*linklist; /* /* 函数名称:创立一个循环链表 /* 功能描述:输入猴子总数数据m和猴子报数数据n，每报到n的猴子就删除此猴子结点， /下一个猴子开始报数，每报到n的均删除，如此循环，循环m-1次，即只需删除m-1个 / 节点,最后剩下猴子大王 /* 参数:循环链表的头指针front，尾指针rear /* linklist initring(int

13、 n,linklist r) /创立一个循环单链表 linklist front,rear; int i; r=rear=(listnode *)malloc(sizeof(listnode); /两个指针指向首位置 for(i=1;i<n;i+) front=(listnode*)malloc(sizeof(listnode); rear->data=i; rear->next=front; rear=front; front->data=n; front->next=r; /头尾相连 r=front; /指向头节点位置 return r; linklist d

14、eleted(int n,int k,linklist r) int i,j; linklist front,rear; front=r; /p移至头节点位置 for(i=1;i<=n-1;i+) /循环m-1次，即只需删除m-1个节点,最后剩下猴子大王 for(j=1;j<=k-1;j+) front=front->next; /front循环移至下一个位置 rear=front->next; front->next=rear->next; /报n号的猴子出列，即删除front->next printf("%4d",rear-&g

15、t;data); if(i % 6=0) printf("n"); free(rear); printf("n"); r=front;return r; /记录猴子大王位置并传递 void outring(int n,linklist r) int i; linklist front; front=r; /获得猴子大王位置 printf("猴子大王："); printf("%4dn",front->data); /* /* 函数名称:主函数/* 功能描述:输入猴子总数m，猴子报数数据n /* 参 数:m，n，

16、j /* void main() /* /* 功能描述:猴子选大王游戏C语言工作界面，动态显示日期和时间 /* printf("n"); printf("n"); system("date /t"); system("time /t"); system("color 16"); printf("n"); printf("n"); printf(" n"); printf(" n"); printf(" n&

17、quot;); printf(" .欢 迎 进 入. n"); printf(" n"); printf(" .猴子选大王游戏C语言工作界面. n"); printf(" n"); printf(" n"); printf(" n"); printf(" n"); printf(" n"); int xuliehao; printf("n"); printf("n"); printf("

18、n"); printf(" 请输入密码:"); scanf(" %d",&xuliehao);printf("n"); while(xuliehao!=39) printf("不好意思，您的序列号输入错误，请重新输入序列号:"); scanf("%d",&xuliehao);system("cls"); linklist r; int m,n; linklist initring(int m,linklist r); linklist deleted

19、(int m,int k,linklist r); void outring(int m,linklist r); int j; while(j) printf" n"); printf(" n"); printf(" 作者: 庞康永 050120210239 n"); printf(" 工具: C-Free 4.1 n"); printf(" 题目: 猴子选大王. n"); printf(" M个猴子围成一圈坐在一起,从第一个(1,2,3.)开始 n"); printf(&

20、quot; 报数,报到n(n<M)的那个退出,然后从退出的下一个重 n"); printf(" 新开始报数,如此类推.剩下最后一个为王. n"); printf(" 创立时间: 2010年01月20日. n"); printf(" n"); printf(" n"); printf("请输入猴子总数 monkey number M= "); scanf("%d",&m); printf("请输入将出列猴子的报数号n= "); sca

21、nf("%d",&n); printf("以下序号的猴子因报%d号而依次出列：n",n); r=initring(m,r); r=deleted(m,n,r); outring(m,r); 5.程序运行结果1登陆主界面2. 输入序列号进入功能界面3. 输入猴子总数m=54结果显示界面4.输入猴子报号n=6后运行结果界面6.设计体会经过了两周的数据结构课程设计，我是受益颇多，从选题到定稿，从理论到实践，在这短短的两个星期的日子里，可以说得是苦多于甜，但是可以学到很多很多的的东西，同时不仅可以稳固了以前所学过的知识，而且学到了很多在书本上所没有学到过

22、的知识，使我懂得了理论与实际相结合是很重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，从理论中得出结论，从而提高自己的实际动手能力和独立思考的能力。在设计的过程中遇到问题，可以说得是困难重重，这毕竟第一次做的，不可防止会遇到过各种各样的问题，同时在设计的过程中发现了自己的缺乏之处，上课时老师讲的理论知识，似乎很容易接受，以及各种算法都能够较为理解，但是在真正的运用过程中，并不能把理论知道很好的和实践结合起来。在平时做实验时，尤其是这次课程设计，总感到有些无从下手。因此，在学知识的过程中，一定要多动手、动脑，将所学的知识熟练掌握，自如运用。通过这次课程设计，对我的逻辑思维能力是一个很大的锻炼，再有，它还加强了我们的系统思考问题的能力，在编程方面，我们开始从整体的角度来考虑问题了，而不再像以前一样的，胡乱动手。也就是因为先前的这种编程习惯，使得我们在课程设计过程中浪费了不少的时间，尝到了教训。此次课程设计也对我的单独解决问题的能力有了极大的提高。说实在的，刚看到课程设计题目是?猴子选大王?，一开始我是蒙了，听都没听过的游戏而且还要用算法实现，这对我是一个打击，第一次要我一个人单独完成一个课程设计，难度可想而知，后来慢慢的静下来冷静思考理解题目，经过较长时间的调试代码和修改代码，才得出了最后的结果，并且在这个过程中，我掌握了不少专业知识，是一