猴子选大王-课程设计文档Word文档下载推荐.doc
《猴子选大王-课程设计文档Word文档下载推荐.doc》由会员分享，可在线阅读，更多相关《猴子选大王-课程设计文档Word文档下载推荐.doc（14页珍藏版）》请在冰点文库上搜索。
5、运行结果（截图） 10
四、结论 11
五、致谢 12
六、参考文献 12
1、设计的目的与要求：
13
2、设计进度及完成情况 13
摘要
线性链表是一种重要而且使用广泛的数据结构，用链表所表示数据元素之间的逻辑关系是由节点中的指针指示的，而循环链表的特点是表种最后一个节点的指针指向头结点，整个链表形成一个环，用循环链表作为本课题的数据存储结构，充分考虑了循环链表的特点仅通过对两个循环链表的出、入列操作，大大降低空间复杂度就简单的实现了要求，动态地模拟出了猴子选大王问题中猴子循环报数的情况。
关键词：
数据结构线性链表存储结构空间复杂度（3~5个）
Abstract
Linearlistisanimportantandextensiveuseofthedatastructure,Listsaidthatthedatausedbythelogicofrelationsbetweentheelementsbythenodeinthedirectionofthepointer,Thecirculationlistofthecharacteristicsofthespecieslististhelastnodeoftheindicatorspointtothefirstnode,theentirelisttoformaring,Withthecycleofthelistasthesubjectofdatastoragestructures,takingintoaccountthefullcyclethroughthelistofthecharacteristicsofonlytwooutofcirculationlist,outintooperation,greatly
reducethecomplexityofspaceontherealizationofasimplerequest,Tosimulatethedynamicsofthemonkeykingelectionissueinanumberofmonkeyscirculation
Situation
Keywords:
DataStructure,LinearList,Storagestructure,
Spacecomplexity
《数据结构》课程设计
--猴子选大王问题设计
一、引言
数据结构是一门专业技术基础课，它对学习者的的要求很明确：
学会分析、研究计算机加工的数据结构的特性，以便为应用设计所需的数据选择适当的逻辑结构、存储结构及其相应的算法，并初步掌握算法的时间分析和空间分析的技术。
其次，该课程的学习过程也是复杂程序设计的训练过程，要求学习者编写的程序结构或设计的程序结构体清楚、正确、易读，符合软件工程的规范。
循环链表是一种重要的链式结构，其特殊性在于需附设两个指针分别指示表头元素及表尾元素的位置且表头和表尾相邻接，臆造的环状空间巧妙的解决了需循环依次删除元素的约瑟夫问题。
本设计采用目前最通用的程序设计语言之一——C语言作为数据结构和算法的描述语言，循环链表作为数据存储结构。
充分考虑了循环链表的特点仅通过对两个循环链表的出、入列操作，就简单的实现了要求，动态的模拟出了猴子选大王问题中猴子循环报数的情况。
该程序通俗易懂且实用性强，其他类似的算法均可借鉴和参考使用。
并且该程序清单详细具体、全面、具有很强的可读性。
二、设计目的与任务
1、课程设计的目的
1）初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；
训练学生灵活应用所学数据结构的基本知识，熟练的完成问题分析、算
2）法设计、编写程序，求解出指定的问题；
3）训练用系统的观点和软件开发一般规范进行软件开发，巩固、深化学生的理论知识，提高编程水平，并在此过程中培养严谨的科学态度和良好的工作作风；
4）提高综合运用所学的理论知识和方法独立分析和解决问题的能力。
2、课程设计的任务
问题描述：
一堆猴子都有编号，编号是1，2，3...m,这群猴子（m个）按照1到m的顺序围坐一圈，从第1开始数，每数到第n个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。
课题要求：
输入数据m,n其中m,n为整数，n输出形式为提示按照m个猴子，数n个数的方法，输出为大王的猴子是几号
三、设计方案与实施
1、总体设计
//写总体的设计思想
采用两个循环队列反复出队列与入队列来进行“舞伴配对”。
程序中主要用到以下抽象数据类型：
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）
特殊输出链表保留的最后一个元素，即猴子大王的序号。
程序包含两个模块
（1）主程序模块，其中主函数为
intmain{
输入信息；
根据输入要求进行删除和输出；
输出结果；
}
（2）循环链表模块——实现具体删除输出操作。
2）两模块之间的简单调用关系
主函数模块
循环队列模块
循环链表模块
图1模块调用图
2、详细设计
//对几个主要功能函数作出相应的说明
1）各个函数之间的调用关系
主函数
最后元素输出操作
链表循环删除输出操作
数据输入
输出
序号
图2函数调用关系图
2）函数设计
程序设计中主要包括下列函数
LinkListinitring（intn,linklistr）
{
构造一个含n个元素的循环链表;
LinkListdelete（intn,intk,linklistr）
循环删除报k号的元素；
循环输出所删除的元素；
记录链表最后所保留的元素的位置；
voidoutring（intn,linklistr）
输出链表最后保留的元素，即猴子大王的序号；
3、程序清单
//整个程序的运行清单
#include"
stdio.h"
#include"
stdlib.h"
typedefstructnode{
intdata;
structnode*next;
}listnode,*linklist;
linklistinitring（intn,linklistr）//创建一个循环单链表
{
linklistp,q;
inti;
r=q=（listnode*）malloc（sizeof（listnode））;
//两个指针指向首位置
for（i=1;
i<
n;
i++）{
p=（listnode*）malloc（sizeof（listnode））;
q->
data=i;
next=p;
q=p;
}
p->
data=n;
next=r;
//头尾相连
r=p;
//指向头节点位置
returnr;
linklistdeleted（intn,intk,linklistr）
inti,j;
p=r;
//p移至头节点位置
=n-1;
i++）//循环n-1次，即只需删除n-1个节点,最后剩下猴子大王
for（j=1;
j<
=k-1;
j++）
p=p->
next;
//p循环移至下一个位置
q=p->
next=q->
//报k号的猴子出列，即删除p->
next
printf（"
%4d"
q->
data）;
if（i%6==0）printf（"
\n"
）;
free（q）;
returnr;
//记录猴子大王位置并传递
voidoutring（intn,linklistr）
linklistp;
p=r;
//获得猴子大王位置
猴子大王：
"
%4d\n"
p->
voidmain（）//主函数
linklistr;
intn,k;
linklistinitring（intn,linklistr）;
linklistdeleted（intn,intk,linklistr）;
voidoutring（intn,linklistr）;
printf（"
请输入猴子总数monkeynumber="
scanf（"
%d"
&
n）;
请输入将出列猴子的报数号：
k）;
下列序号的猴子因报%d号而依次出列：
k）;
r=initring（n,r）;
r=deleted（n,k,r）;
outring（n,r）;
}
4、程序调试与体会
通过这次课程设计，我们受益颇多：
首先，上课时请的理论知识，似乎很容易接受，以及各种算法都能够比较轻松的理解，但是在真正的运用过程中，并不能把理论知道很好的和实践结合起来。
在平时做实验时，尤其是这次课程设计，总感到有些无从下手。
因此，在学知识的过程中，一定要多动手、动脑，将所学的知识熟练掌握，自如运用。
其次，通过这次课程设计，对我的逻辑思维能力是一个很大的锻炼，再有，它还加强了我们的系统思考问题的能力，在编程方面，我们开始从整体的角度来考虑问题了，而不再像以前一样的，胡乱动手。
也就是因为先前的这种编程习惯，使得我们在课程设计过程中浪费了不少的时间，尝到了教训。
另外，此次课程设计也对我的独自解决问题的能力有了极大的提高，以前做的都是小程序，就都是一个人做，做了后，甚至还洋洋得意，可这一次，一开始是对我们的一个打击，没有一个人能单独完成，最后还是大家一齐出力，共同商讨，才得出了最后的结果，并且在这个过程中，我们相互之间还掌握了其他人掌握了但自己还没有掌握的知识，是一次知识的大汇总，并且在这个讨论的过程中，还更正了不少我们各自自身对于某个知识点的误区。
这次程序设计也是一个毅力的考验过程。
有时候往往只是一个小小的错误，却要费很多
的时间来解决。
在这个过程不能过于急躁，并且要很有耐心才行程序需要反复调试，其过程很可能相当令人头疼，有时花很长时间设计出来还是需要重做，那时心中未免有点灰心，有时还特别想放弃，此时更加需要静下心，查找原因。
通过这次课程设计，我学习了很多平时很少关注的知识点，比如循环链；
也明白了很多道理，比如做不要事萎缩害怕，要尽力去思考，努力去解决，不要太依赖别人，要有团结精神，齐心协力一起解决。
5、运行结果（截图）
程序运行如下：
图
（1）、输入总元素个数
图
（2）、输入循环中所需删除元素的位置
图（3）、程序运行的输出结果
四、结论
运用循环链表的基本操作顺利的解决约瑟夫—猴子选大王问题，主要利用循环链表的环状结构，循环地执行删除操作并输出其值，记录最后保留元素的位置，而整个过程不需要不需要移动元素使程序在空间复杂度上降小很多，采用指针的移动大大加快了程序的执行效率。
系统整体上比较完美，可以从键盘获取输入元素，整体输出画面效果整洁、大方。
五、致谢
首先，我要感谢学校给我们提供了此次课程设计的机会，能让同学们在一起学习与研究，让我们有机会对所学的理论知识进行实践。
其次，在论文的写作过程中，也得到了许多同学的宝贵建议，同时还得到许多学长的支持和帮助，在此一并致以诚挚的谢意。
最后，我们还要特别感谢我们的辅导老师，在她的精心辅导和帮助下，我们的设计才得以顺利完成。
对她为我们的设计所提出的宝贵意见表示忠心的感谢！
六、参考文献
[1]谭浩强.C程序设计[M].北京:
清华大学出版社,2005
[2]罗宇等.数据结构[M].北京:
北京邮电大学出版社,2003
[3]严藯敏.数据结构[M].北京:
清华大学出版社,2001
[4]胡学钢.数据结构算法设计指导[M].北京:
清华大学出版社,1999
课程设计任务书及成绩评定
课题名称：
猴子选大王
完成者：
1）灵活应用所学数据结构知识，独立完成问题分析。
2）初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等方法。
3）训练用系统的观点和软件开发一般规范进行软件开发。
2、设计进度及完成情况
日期
内容
2008．12．22-2008．12．23
分析问题，找出所要解决问题的关键
2008．12．24-2008．12．25
总体设计，找出解决方案
2008．12．26-2008．12．28
详细设计，列出解决步骤
2008．12．29-2009．1．1
程序编码
2009．1．2-2009．1．3
程序调试，修改加以完善
2009．1．4-2009．1．5
书写文档
3、成绩评定：
设计成绩：
（教师填写）
指导老师：
（签字）
二00年月日
升级会员 