输出形式:
中文提示按照m个猴子,数n个数的方法,输出为大王的猴子是几号,建立一个函数来实现此功能
1.引言
随着计算机科学的迅速发展,计算机已深入到揉合社会的各个领域,它
的应用已不再局限于科学计算,以解决一些数学问题,而且可以解决一些抽象化
的具体问题,更多地用于控制,管理及数据处理等非数值计算的处理工作,这便为我们的日常生活提供了很多的方便,譬如说火车、飞机售票系统,学生成绩管理,商品管理系统,医院选址等实际问题。
如今程序设计的语言很多,有发展比较完善高级语言,也有最基本的低级语言,然而再好的程序设计也要有一个比较清晰的思路——算法。
为了编写好一个好程序,必须分析待处理对象的特性以及各处理对象之间的关系,于是数据结构便成为我们绝佳的选择。
数据结构是计算机程序设计的重要理论技术基础,它不仅是计算机科学的核心课程,而且已成为其他理工专业的热门选修课。
数据结构是计算机程序设计的重要理论基础,它不仅是计算机学科一门专业技术基础课,它对学习者的的要求很明确:
学会分析、研究计算机加工的数据结构的特性,以便为应用设计所需的数据选择适当的逻辑结构、存储结构及其相应的算法,并初步掌握算法的时间分析和空间分析的技术。
其次,该课程的学习过程也是复杂程序设计的训练过程,要求学习者编写的程序结构或设计的程序结构体清楚、正确、易读,符合软件工程的规范。
循环链表是一种重要的链式结构,其特殊性在于需附设两个指针分别指示表头元素及表尾元素的位置且表头和表尾相邻接,臆造的环状空间巧妙的解决了需循环依次删除元素的约瑟夫问题。
本设计采用目前最通用的程序设计语言之一——C语言作为数据结构和算法的描述语言,单循环链表作为数据存储结构。
充分考虑了循环链表的特点仅通过对两个循环链表的出、入列操作,就简单的实现了要求,动态的模拟出了猴子选大王问题中猴子循环报数的情况。
该程序通俗易懂且实用性强,其他类似的算法均可借鉴和参考使用。
并且该程序清单详细具体、全面、具有很强的可读性。
2.需求分析
2.1问题分析
根据问题描述得知,该问题中m个猴子围坐在一起形成首尾相接的环,因此可用循环链表解决。
从第n个猴子开始出列相当于从链表中删除一个结点。
该程序主要有三个模块组成,建立循环链表,报数利用循环链表实现猴子的出列,最终剩下的猴子即猴王。
具体步骤如下:
第一步 首先创建循环链表。
第二步向链表中填入猴子的编号
第二步 找第一个开始报数的猴子。
第三步 数到n让这个猴子出列
第四步 接着开始报数,重复第三步,直到剩下最后一个猴子,它就为大王
2.2总体设计
采用两个循环队列反复出队列与入队列来进行“舞伴配对”。
程序中主要用到以下抽象数据类型:
1)设定链表抽象数据类型的定义
ADTstruct
{对象数据=(整数)
操作对象:
structmonkey*create()
建立循环链表
structmonkey*findout(start,n)
找出被淘汰的猴子的上一个
Structmonkey*letout(last)
删掉被淘汰的猴子,返回的指针值指向下一个猴子}。
基本操作
(1)initring(intn,linklistr)
操作结果:
构造一个具有n个元素的循环链表r。
(2)iinklistdelete(intn,intk,linklistr)
初始条件:
链表r已存在。
操作结果:
循环依次删除问题对应所需位置的元素并当即输出其值,用指针r记录其最后元素的位置。
}ATDlinklist
(3)outring(intn,linklistr)
特殊输出链表保留的最后一个元素,即猴子大王的序号。
程序包含两个模块
a.主程序模块,其中主函数为
voidmain{
输入猴子的信息;
根据输入要求进行删除和输出;
剩下一个猴子后,输出结果;
}
b.循环链表模块——实现具体删除输出操作。
2)两模块之间的简单调用关系
图1模块调用图
3.概要设计
3.1模块分析
3.1.1链表循环输入删除输出
程序包含两个模块
(1)主程序模块,其中主函数为
voidmain{
输入猴子的信息;
根据输入要求进行删除和输出;
剩下一个猴子后,输出结果;
}
(2)循环链表模块——实现具体删除输出操作。
a.输入功能:
当用户执行的猴子信息时,系统会提示用户输入猴子总数m和猴子的报号数n,输入完后,执行收索查找功能
b.收索查找功能:
在输入的猴子总数和猴子报号数后,猴子开始进行按1至n循环报数(第1个猴子开始报数1,第2个猴子报数2,……,第n个猴子报数n,找出该猴子,第n+1个猴子报数1,第n+2个猴子报数2,……,在循环链表循环报数至释放剩最后一个猴子)释放节点,找出猴子王结点。
c.释放功能:
当用户执行的检索完猴子信息后,系统会提示用户已释放出费猴子大王节点和猴子大王结点的编号信息,该算法具体的实现:
设计一个循环,找到要删除的结点p以及它的前驱结点front,然后执行front->next=p->next;e=p->shifang;释放结点p并且返回被删除猴子的编号。
删除函数为:
voidDelete--()
删除算法的图形表示为:
当猴子报号数n时:
图2循环链表释放结点
循环链表模块图层分析(具体如下图2所示)
图3链表循环删除输出模块
3.1.2各个函数之间的调用关系
整个函数调用关系:
主函数由数据输入、链表循环删除输出操作
、数据输出等组成(如下图3所示)
图4函数调用关系图
3.2函数的流程分析
(如下图5流程图所示)
设定链表抽象数据类型的定义
ADTstruct
{对象数据=(猴子总数,m为整数)
操作对象:
structmonkey*create()
建立循环链表
structmonkey*findout(start,n)
找出被淘汰的猴子的上一个
Structmonkey*letout(last)
删掉被淘汰的猴子,返回的指针值指向下一个猴子}。
图5流程图
4.详细设计
4.1函数设计
程序设计中主要包括下列函数
LinkListinitring(intn,linklistr)
{
构造一个含n个元素的循环链表;
}
LinkListdelete(intn,intk,linklistr)
{
循环删除报k号的元素;
循环输出所删除的元素;
记录链表最后所保留的元素的位置;
}
voidmain()
voidoutring(intn,linklistr)
{
输出链表最后保留的元素,即猴子大王的序号;
}
4.2程序源代码
#include"stdio.h"
#include"stdlib.h"
typedefstructnode
{
intdata;
structnode*next;
}listnode,*linklist;
//**************************************************************************
//**函数名称:
创建一个循环链表
//**功能描述:
输入猴子总数数据m和猴子报数数据n,每报到n的猴子就删除此猴子结点,
//下一个猴子开始报数,每报到n的均删除,如此循环,循环m-1次,即只需删除m-1个
//节点,最后剩下猴子大王
//**参数:
循环链表的头指针front,尾指针rear
//***************************************************************************
linklistinitring(intn,linklistr)//创建一个循环单链表
{
linklistfront,rear;
inti;
r=rear=(listnode*)malloc(sizeof(listnode));//两个指针指向首位置
for(i=1;ifront=(listnode*)malloc(sizeof(listnode));
rear->data=i;
rear->next=front;
rear=front;
}
front->data=n;
front->next=r;//头尾相连
r=front;//指向头节点位置
returnr;
}
linklistdeleted(intn,intk,linklistr)
{
inti,j;
linklistfront,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->data);
if(i%6==0)printf("\n");
free(rear);
}
printf("\n");
r=front;returnr;//记录猴子大王位置并传递
}
voidoutring(intn,linklistr)
{
inti;
linklistfront;
front=r;//获得猴子大王位置
printf("猴子大王:
");
printf("%4d\n",front->data);
}
//***************************************************************************
//**函数名称:
主函数
//**功能描述:
输入猴子总数m,猴子报数数据n
//**参数:
m,n,j
//***************************************************************************
voidmain()
{
//***************************************************************************
//**功能描述:
猴子选大王游戏C语言工作界面,动态显示日期和时间
//***************************************************************************
printf("\n");
printf("\n");
system("date/t");
system("time/t");
system("color16");
printf("\n");
printf("\n");
printf("〓〓〓〓〓〓〓〓〓〓〓〓\n");
printf("〓〓〓〓〓〓〓〓〓〓〓〓\n");
printf("〓★★★★★★〓\n");
printf("〓...★★★欢迎进入★★★...〓\n");
printf("〓〓\n");
printf("〓...★★★猴子选大王游戏C语言工作界面★★★...〓\n");
printf("〓〓\n");
printf("〓〓\n");
printf("〓★★★★★★〓\n");
printf("〓〓〓〓〓〓〓〓〓〓〓〓\n");
printf("〓〓〓〓〓〓〓〓〓〓〓〓\n");
intxuliehao;
printf("\n");
printf("\n");
printf("\n");
printf("请输入密码:
");
scanf("%d",&xuliehao);
printf("\n");
while(xuliehao!
=39)
{printf("不好意思,您的序列号输入错误,请重新输入序列号:
");
scanf("%d",&xuliehao);
}
system("cls");
linklistr;
intm,n;
linklistinitring(intm,linklistr);
linklistdeleted(intm,intk,linklistr);
voidoutring(intm,linklistr);
intj;
while(j)
{
printf("〓〓〓〓〓〓〓〓〓〓〓〓〓\n");
printf("〓★★★★★★★★★★★★★★★★★★★★★★★〓\n");
printf("〓★★作者:
庞康永*************★★〓\n");
printf("〓★★工具:
C-Free4.1★★〓\n");
printf("〓★★题目:
猴子选大王.★★〓\n");
printf("〓★★M个猴子围成一圈坐在一起,从第一个(1,2,3....)开始★★〓\n");
printf("〓★★报数,报到n(nprintf("〓★★新开始报数,如此类推.剩下最后一个为王.★★〓\n");
printf("〓★★创建时间:
2010年01月20日.★★〓\n");
printf("〓★★★★★★★★★★★★★★★★★★★★★★★〓\n");
printf("〓〓〓〓〓〓〓〓〓〓〓〓〓\n");
printf("请输入猴子总数monkeynumberM=");
scanf("%d",&m);
printf("请输入将出列猴子的报数号n=");
scanf("%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.设计体会
经过了两周的数据结构课程设计,我是受益颇多,从选题到定稿,从理论到实践,在这短短的两个星期的日子里,可以说得是苦多于甜,但是可以学到很多很多的的东西,同时不仅可以巩固了以前所学过的知识,而且学到了很多在书本上所没有学到过的知识,使我懂得了理论与实际相结合是很重要的,只有理论知识是远远不够的,只有把所学的理论知识与实践相结合起来,从理论中得出结论,从而提高自己的实际动手能力和独立思考的能力。
在设计的过程中遇到问题,可以说得是困难重重,这毕竟第一次做的,不可避免会遇到过各种各样的问题,同时在设计的过程中发现了自己的不足之处,上课时老师讲的理论知识,似乎很容易接受,以及各种算法都能够较为理解,但是在真正的运用过程中,并不能把理论知道很好的和实践结合起来。
在平时做实验时,尤其是这次课程设计,总感到有些无从下手。
因此,在学知识的过程中,一定要多动手、动脑,将所学的知识熟练掌握,自如运用。
通过这次课程设计,对我的逻辑思维能力是一个很大的锻炼,再有,它还加强了我们的系统思考问题的能力,在编程方面,我们开始从整体的角度来考虑问题了,而不再像以前一样的,胡乱动手。
也就是因为先前的这种编程习惯,使得我们在课程设计过程中浪费了不少的时间,尝到了教训。
此次课程设计也对我的独自解决问题的能力有了极大的提高。
说实在的,刚看到课程设计题目是《猴子选大王》,一开始我是蒙了,听都没听过的游戏而且还要用算法实现,这对我是一个打击,第一次要我一个人单独完成一个课程设计,难度可想而知,后来慢慢的静下来冷静思考理解题目,经过较长时间的调试代码和修改代码,才得出了最后的结果,并且在这个过程中,我掌握了不少专业知识,是一次知识的大汇总,并且在这个问题的思考的过程中,还更正了不少我们各自自身对于某个知识点的误区。
这次程序设计也是一个毅力的考验过程。
有时候往往只是一个小小的错误,却要费很多的时间来解决。
在这个过程不能过于急躁,并且要很有耐心才行程序需要反复调试,其过程很可能相当令人头疼,有时花很长时间设计出来还是需要重做,那时心中未免有点灰心,此时更加需要静下心,查找原因。
7.结束语
感谢学校给我提供一次这样的动手机会,运用循环链表的基本操作顺利的解决猴子选大王问题,主要利用循环链表的环状结构,循环地执行删除操作并输出其值,记录最后保留元素的位置,而整个过程不需要不需要移动元素使程序在空间复杂度上降小很多,采用指针的移动大大加快了程序的执行效率。
系统整体上比较完美,可以从键盘获取输入元素,整体输出画面效果整洁、大方。
课程设计是培养学生综合运用所学知识,发现,提出,分析和解决实际问题,锻炼实践能力的重要环节,是对学生实际工作能力的具体训练和考察过程
我想这不只是一次简简单单的课程设计,更体现了数据结构算法和生活的紧密联系。
让人不得不深思,这一个学期的学习,这两年来的大学学习生涯,自己究竟学会了什么,掌握了多少,是否能胜任以后作编译人员的职位。
我想大家都心里都有很多的感触。
对于自己,我想我已经认识到了自己的不足,在今后的学习过程中,一定会以严谨的态度来对待编程,以最好的面貌来迎接大三的计算机专业课程,并且要经常上机调试,坚持理论与实践相结合。
参考文献
【1】严蔚敏,吴伟民数据结构(C语言版)清华大学出版社
【2】谭浩强C程序设计(第三版)清华大学出版社
【3】胡学钢.数据结构算法设计指导[M].北京:
清华大学出版社,1999
【4】罗宇等.数据结构[M].北京:
北京邮电大学出版社,2003
【5】
【6】