数据结构课程设计之敢死队问题.doc

##大学 数据结构课程设计报告 题目： 敢死队问题 院（系）： 计算机工程学院 学生姓名: 班级： 学号: 起迄日期: 2011.06.20——2011.06.29 指导教师: 指导教师评语： 指导教师评语： 成绩： 签名： 年 月 日 2010—2011年度 第 2 学期 一、需求分析 1.问题描述： 使用不同的数据结构来实现敢死队问题，即利用已学的知识，使用不同的数据结构，找出在一队士兵中从第几个士兵开始数，每隔5个则派出去执行任务，依次循环，直至最后可以使排长留下来而不必去执行任务，或者说最后只剩下排长（1号元素）的问题。 2.基本功能 通过程序求出符合要求的士兵的编号，即运用不同的数据结构来完成本题中给定的题目要求以及得出正确的结果。 3.输入输出 程序中的输入为该排中的人员的个数，然后其它的数组中的元素的个数，包括每个程序中的结构的定义都由函数自动完成。其中包括第一个程序中的数组的定义，第二个程序中的队列的定义和第三个程序中的链表的建立都是由函数自动完成的。 程序运行过程中三个均采用了顺序查找的方法进行了查找，应该本身这个程序也不可能使用其他的查找方法，既要计数，又必须判断计数是否达到了上限，所以必须使用顺序查找的方法。 程序的输出为输出第几个开始时可以使排长留下来而不去执行任务。当然也可以输出每一次执行时的顺序，但是那样的话时间复杂度会增加，而且在cmd命令窗口中如果每个都输出的话，由于其本身的缺陷，会将本程序的一部分输出结果给截取掉，查询资料知道，cmd本身有容量限制。为了防止这种情况发生，本程序不采用那样的输出形式。 测试数据，根据测试题目的测试原则，我采用了从文件读入的方法进行测试，选取了35组数据，假如这35组数据的输出结果是相同的，可以在一定的程度上证明该程序是正确的，以及输出的结果的正确性。 二、 概要设计 1.设计思路： 本程序可以采用不同的结构，不同的算法，但是循环查找是必须的，因为本身的问题就是依次查找，假如不是依次的循环查找的话是不会找到正确的结果的。但是结构不同，故查找也是不相同的。 根据题意所给的内容，我初步分析可以分别使用数组（顺序存储结构），队列（顺序存储结构，先进先出）和链表（链式存储结构）中循环查找找出符合题意的数据成员，来达到程序所要得到的结果。进一步分析该题目所说的敢死队问题，其实质则为约瑟夫环问题。 第一个程序是利用数组实现该问题，在数组中循环查找，当查找到数组最后一个元素时再从第一个元素开始查找，直至最后数组为空或者最后留下来的是排长（1号元素）即可。 第二个程序是利用队列的数据结构，先进先出，先使用出队函数EnLine()，如果计数元素count！=5时，调用入队函数DeLine（）使之入队，否则的话，该元素不入队，并将count置为0，继续执行，判断下一个元素是否符合条件，直至所有的元素都出队，判断最后出队的是否为排长即可。 第三个程序是利用链表的数据结构，更准确的说是循环链表，依旧是计数，count为5时删除该结点（调用deletenode（）），并使count为0，否则的话继续计数，直至链表只剩下最后一个元素。 2.数据结构设计： 在三个程序中定义的逻辑结构均为线性结构，但是存储结构却分为顺序存储和链式存储，第一二个为顺序存储，第三个为链式结构。由于顺序结构中可以使用顺序循环查找，数组和队列都可以在头部删除，并且在尾部添加，符合本题目的要求，所以选择；而链式存储结构则是链式的查找，依次查找，并且查找删除较为方便，所以选定了这三种结构来解决本问题。 定义程序中用到的抽象数据类型； 抽象数据类型线性表的定义如下： 数组实现的数据类型很明确，故不必定义。 队列实现： ADT List{ 数据对象：D={a[i]| a[i] ∈ElemSet,i=1,2,3……，n,n≥0} 数据关系：R1={ai-1,ai| ai-1,ai ∈D,i=1,2,3,……，n} 基本操作： EnLine(L,i) 初始条件：线性表L已存在。 操作结果：在L的最后插入新的数据元素i。即入队操作。 DeLine(L,i) 初始条件：线性表L已存在且非空。 操作结果：删除L的第一个数据元素,并用i返回其值。 } 链表实现： ADT List{ 数据对象： struct sql //定义结构体 ，为链表中的结点 { int data; //只包含了一个元素 s