搜索
敢死队问题2011年12月30日目录摘要..............................................................................................................................................21课题背景的介绍.......................................................................................................................21.1课题背景............................................................................................................................21.2目的....................................................................................................................................32需求分析...................................................................................................................................32.1数据需求分析....................................................................................................................32.2功能需求分析....................................................................................................................43系统总体设计...........................................................................................................................43.1系统模块划分....................................................................................................................43.2系统模块结构图................................................................................................................44系统详细设计...........................................................................................................................54.1系统操作界面....................................................................................................................54.2各模块功能实现................................................................................................................64.2.1顺序存储..........................................................................................................................64.2.2单循环链表......................................................................................................................74.2.3数组.................................................................................................................................84.2.4循环队列.........................................................................................................................94.2.5递归...............................................................................................................................114.2.6主函数...........................................................................................................................125总结.........................................................................................................................................156参考文献.................................................................................................................................157附录...........................................................................................................错误!未定义书签。7.1人员分工.............................................................................................错误!未定义书签。7.2代码..................................................................................................................................15敢死队问题摘要敢死队问题是根据著名的“约瑟夫环”演变而来的敢死队问题的处理与计算来设计的一个系统。整个系统从符合操作简便、界面友好、灵活、实用、安全的要求出发，完成敢死队问题的全过程，包括五种数据结构算法（顺序表、单循环链表、数组、循环队列、递归）、数据的处理与计算、数据的分析、结果的输出。本课程主要介绍了本课题的开发背景，所要完成的功能和开发的过程。重点说明了系统的设计思路、总体设计、各个功能模块的设计与实现方法。关键词：敢死队问题，C语言，数据结构，顺序存储结构，单链表存储结构，数组，队列，递归1课题背景的介绍1.1课题背景有M个敢死队员要炸掉敌人的一碉堡，谁都不想去，排长决定用轮回数数的办法来决定哪个战士去执行任务。如果前一个战士没完成任务，则要再派一个战士上去。现给每个战士编一个号，大家围坐成一圈，随便从某一个战士开始计数，当数到5时，对应的战士就去执行任务，且此战士不再参加下一轮计数。如果此战士没完成任务，再从下一个战士开始数数，被数到第5时，此战敢死队问题士接着去执行任务。以此类推，直到任务完成为止。排长是不愿意去的，假设排长为1号，请你设计一程序，求出从第几号战士开始计数才能让排长最后一个留下来而不去执行任务。要求：至少采用两种不同的数据结构的方法实现。1.2目的本课题运用C语言进行开发，C语言能够简单的进行编译一些程序，来实现对一些问题的解决。它虽然比较简单的处理一些问题，但却有更高的效率。它能够被大多数用户所接受，因为它能够呈现出清晰的界面，是人们能够很好的理解。能在一些方面给人们更好的服务，成为人们的好帮手。经过这一个学期对《数据结构》的学习，我们都学到了不少东西，可能有些学的还不够理想，但无论如何这些知识都为我们的下一步学习打下了坚实的基础。通过做这么个课程设计将理论联系实际，使我更好的理解课本上的知识，发现不足之处，然后更好的学习，使我的编程能力有进一步的提高。2需求分析本程序输入队伍人数n为任意的，最终输出记数的初始位置，首先输入一个报数上限m，当达到报数上限时，那名士兵出列执行任务，从下个人开始记数，再次循环，直到只剩一人，得到其在队伍中的位置，通过数学思想求得题目要求即队长为首的情况下需要记数初始位置。2.1数据需求分析由于约瑟夫环模拟的是人的报数操作，固本系统的主要处理的数据是正整数。正整数信息包括:队伍的人数，报数的数值，报数开始的位置。本程序任务是通过输入任意队伍人数n和报数上限m，输出使排长最后一个执行任务而开始记数的初始位置。首先输入队伍人数n，然后输入报数上限m(m=n),从1号开始报数，当达到报数上限时，那名士兵出列执行任务，从下个人开始记数，再次循环，直到只剩一人，得到其在队伍中的位置，记下该位置视敢死队问题为排长位置，则1号即可视为最先报数的人，通过数学计算即可获得所求(z=n-k+2)。2.2功能需求分析本系统主要实现对学生成绩信息进行管理，需要实现以下几个方面的管理功能：（1）创建存储结构：创建顺序表，创建单循环链表，创建数组，创建循环队列。（2）数据的输入：把队伍的人数，报数的数值输入。（3）数据的处理；对队伍的人数，报数的数值进行计算。（4）结果的输出：把报数开始的位置输出。3系统总体设计3.1系统模块划分本系统主要是对敢死队问题的处理，包括了创建存储结构、数据的输入、数据的处理、结果的输出等功能。整个系统分为以下几个模块。1、操作界面模块本模块提供操作界面的信息输出模式。2、顺序存储结构模块本模块用于通过运用顺序结构模块来计算结果。3、单链表存储结构模块本模块用于通过运用单链表结构模块来计算结果。4、数组模块本模块用于通过运用数组结构模块来计算结果。5、循环队列模块本模块用于通过运用循环队列模块来计算结果6、递归实现模块本模块通过递归思想来实现计算结果3.2系统模块结构图根据系统功能设计，对应的系统模块结构图如图所示敢死队问题功能模块顺序表存储循环队列递归单循环链表数组实现退出敢死队问题4系统详细设计4.1系统操作界面由于敢死队问题处理的是数字的调度问题，固不需要一些复杂的功能，因此根据实际需求设计了如下比较简洁的界面供用户使用。该界面简单明了，根据界面上的提示信息，用户能很快的使用该系统。敢死队问题4.2各模块功能实现4.2.1顺序存储(1)算法思想将有n个人的队列存入顺序表中，然后从顺序表的第一个元素开始按间隔人数m读取数据，当报数报到m的时候出队，同时将该位置上的值