文档介绍：河南城建学院
数据结构
课程设计说明书
题目: 敢死队问题
院系: 计算机科学与工程系
专业班级: 计算机科学与技术
学号:
学生姓名:
同组人:
指导教师:
2010年 12 月 25 日
目录
1 需求分析 1
1
1
1
2 概要设计 1
功能设计 1
抽象数据类型定义 1
算法流程图 2
3 详细设计 2
界面设计 2
详细代码分析 2
调试分析 2
2
3
4 总结 3
参考文献 3
线性表数据结构
1 需求分析
,最终输出记数的初始位置,首先输入一个报数上限m,当达到报数上限时,那名士兵出列执行任务,从下个人开始记数,再次循环,直到只剩一人,得到其在队伍中的位置,通过数学思想求得题目要求即队长为首的情况下需要记数初始位置。
:
(1)构造数据结构;(2)数据输入;(3)执行队员出列;(4)输出要求数值
(5)结束。
:
当 n=10 输出结果为:要求的位置是:9
2 概要设计
功能设计
本程序其实质是约瑟夫环问题,本次实验用了线性表数据结构,并运用模块化的程序设计思想,算法的实现是这样的:
定义类类型
定义变量并初始化
线性表初始化
当队员数小于等于1时,输出错误
算法流程图
开始
声明数据类型
定义变量并初始化
初始化线性表
输入敢死队员总数
敢死队员人数>线性表长度
队员报数
报数值=偏移值?
[i]清零
剩下的队员数>1?
输出
增加存储分配
图 1 算法流程图
3 详细设计
头文件设置
#include <iostream>
using namespace std;
template<class T>
class SeqList //顺序表类,T指定元素类型
{
private:
T *element;//动态数组存储顺序表的数据元素
int size; //顺序表的数组容量
int len; //顺序表长度
public:
SeqList(int size=100); //构造指定(默认)容量的空表
T get(int i); //返回第i(i>=0)个元素
int set(int i,T x); //设置第i个元素为x
int remove(int i); //删除第i个元素
void insert(T x); //在顺序表最后插入x
void insert(int i,T x);
};
//------------------------------------------------------------------------------------------
template<class T>
SeqList<T>::SeqList(int size) //构造指定容量的空表
{
this->size=size<100? 100:size;
this->element=new T[this->size];
this->len=0;
};
//------------------------------------------------------------------------------------------
template <class T>
T SeqList<T>::get(int i) //返回第i(i>=0)个元素
{ //若i指定元素序号无效,则抛出异常
if (i>=0 && i<len)
return element[i];
throw "参数i指定元素序号无效";
};
//------------------------------------------------------------------------------------------
template<class T>
int SeqList<T>::set(int i,T x) //设置第i个元素为x
{ //操作成功返回true,若i指定序号无效返回false
if(i>=0 && i<len)
{
element[i]=x;
return element[i] ;
}
return 0 ;
};
//---------------------------------------