《数据结构与算法》课设说明书模板

1、数学与计算机学院 课程设计说明书 课 程 名 称: 数据结构与算法-课程设计 课 程 代 码: 题 目: 敢死队问题 年级/专业/班: 2010 级软件工程 02 班 学 生 姓 名: 学 号: 1221 开 始 时 间: 20112011 年 1212 月 1414 日 完 成 时 间: 20112011 年 1212 月 2626 日 课程设计成绩： 学习态度及平 时成绩（30） 技术水平与实际 能力（20） 创新 （5） 说明书撰写质量（45） 总 分 （100） 指导教师签名： 年 月 日 摘摘 要要 分析了敢死队问题，利用循环链表和队列编程实现了敢死队系统，该系统 具有找出从某号战士

2、开始计数，每当数到 5 时该名战士去执行任务，出去的战士 不在进行计数最后输出的是 1 等功能。 关键词：关键词：数据结构; ;C+语言; ;敢死队;循环链表;循环队列 目目 录录 1 1 需求分析需求分析.1 1.1.1.1.课程任务课程任务.1 1.2.1.2. 程序执行的命令包括：程序执行的命令包括： .1 2 2 开发及运行平台开发及运行平台.1 3 3 概要设计概要设计.2 3.13.1 循环链表：循环链表： .2 3.23.2 循环队列：循环队列：.2 3.33.3 系统模块设计：系统模块设计：.2 4 4 详细设计详细设计.3 4.14.1 程序流程图程序流程图.3 4.24.2

3、 核心代码核心代码.4 4.34.3 函数调用图如图函数调用图如图 4-24-2：.6 5 调试分析调试分析.7 6 6 测试结果测试结果.8 6.1 测试数据分析测试数据分析.8 6.2 数据测试如下图数据测试如下图.8 7 7 结论结论.11 7.17.1 算法分析算法分析: :.11 7.27.2 总结：总结：.11 参考文献参考文献.12 1 1 需求分析需求分析 1.1.1.1.课程任务课程任务 本程序输入队伍人数 M 为大于等于 1 的任意的整数，最终输出记数的初始位置， 首先有一个报数上限 5，当达到报数上限时，那名士兵出列执行任务，从下个人开 始记数，再次循环，直到只剩一人，得

4、到其在队伍中的位置，通过数学思想求得题 目要求即队长为首的情况下 需要记数初始位置。 1.2.1.2. 程序执行的命令包括：程序执行的命令包括： 1.1.2.12.1 循环链表循环链表 （1）构造链表；（2）数据输入；（3）执行删除；（4）输出要求数值 （5）输出出队序列；（6）结束。 1.2.21.2.2 循环队列循环队列 （1）构造队列；（2）数据输入；（3）执行删除；（4）输出要求数 值（5）输出出队序列；（6）结束。 2 2 开发及运行平台开发及运行平台 硬件: 微型计算机 P4 软件: Windows XP+Microsoft Visual C+6.0 3 3 概要设计概要设计 3.

5、13.1 循环链表：循环链表： 以单循环链表为存储结构，包含 5 个模块： 1.主程序模块 2.构造链表并初始化 3.创建链表并形成约瑟夫环 4.查找报数起点 5输出 3.23.2 循环队列：循环队列： 以循环队列为存储结构，包含 5 个模块 1.主程序模块 2.构造队列并初始化 3.创建循环队列 4.查找报数起点 5输出 3.33.3 系统模块设计：系统模块设计： 此系统是为了找出开始执行任务士兵的序号，使排长最后一个去执行任务。 敢死队问题系统 采用链表解决采用队列解决退出 创 建 链 表 查 找 起 点 输 出 序 列 创 建 队 列 查 找 起 点 输 出 序 列 图 3-1 软件整体

6、设计模块图 4 4 详细设计详细设计 4.14.1 程序流程图程序流程图 程序流程图如图 4-1： 开始 选择服务类型 定义变量并初始化 初始化单链或者队列表循环 模块 或者 输入敢死队员总数 敢死队员人数内存 空间 队员报数 报数值=偏移值? 队员出列 剩下的队员数 1? 输出 增加存储分配 图 4-1 程序流程图 4.24.2 核心代码核心代码 4.2.14.2.1 链表的结点类型链表的结点类型 typedef struct node int num; node *next; linknode; /定义结点 4.2.24.2.2 队列的结点类型：队列的结点类型： typedef struc

7、t int dataMaxsize; int front;/头指针 int rear;/尾指针 int count; /计数器，记录队中元素总数 Queue; /定义结点 4.2.34.2.3 主程序模块：主程序模块： void main() zhujiemian(); 4.2.34.2.3 界面模块界面模块 void zhujiemian() char ch=y; cout *endl; cout *敢死队问题*endl; cout *endl; cout * 1.链表实现 *endl; cout * 2.队列实现 *endl; cout * 3.退出 *endl; cout *endl;

8、int n; coutn; while(n3) coutn; switch(n) case 1: diaoyonglist(); break; case 2: diaoyongduilie(); break; case 3: exit(0); cout是否继续!(y / n)ch; if(ch=y)/判断是否继续，继续则返回主界面 zhujiemian(); 4.2.34.2.3 链表创建模块链表创建模块 void creatlink(linknode *head,int M) linknode *p=new linknode; head-next=head; p=head; /头结点 p-n

9、um=1; p-next=p; for(int i=2;inum=i; p-next=q; p=q; linknode *t=new linknode; t-num=M; p-next=t; p=t; p-next=head; 4.2.44.2.4 链表查找起点模块链表查找起点模块 int serchstart(linknode *head,int M,int start)/查找起点 linknode *p=new linknode; linknode *t=new linknode; p=head; for(int i=1;inext; /开始计数出队 while(p-next!=p) fo

10、r(int i=1;inext; t-next=p-next; delete p; p=t-next; int x=p-num; return x; 4.2.54.2.5 进队列模块进队列模块 void EnQueue(Queue *Q,int x) if (IsFull(Q) cout队列上溢dataQ-rear=x; /新元素插入队尾 Q-rear=(Q-rear+1)%Maxsize; /循环意义下将尾指针加 1 4.2.64.2.6 出队列模块出队列模块 int DeQueue(Queue *Q) int temp; if(IsEmpty(Q) cout队列为空front; Q-cou

11、nt-; /队列元素个数减 1 Q-front=(Q-front+1)%Maxsize; /循环意义下的头指针加 1 return temp; 4.34.3 函数调用图如图函数调用图如图 4-24-2： main() diaoyonglist()diaoyongduilie() creatlink(linknod e *head,int M) Serchstart(linknod e *head,int M,int start) print(linknode *head,int M,int start) DeQueue( Queue *Q) EnQueue(Queue *Q,int x) In

12、itial(Queue *Q) zhujiemian() 图 4-3 函数调用图 5 调试分析 起初我在循环链表外加了循环遍历，由于遍历一次链表就被删除了。故无法重新 遍历。后来经过反复思考，我了解到应该每遍历一次后又重复建立一次链表。当我把 代码修改后却提示我 deleted and rebuid,并且代码无法运行。后来我将链表改成用 函数实现，可输出时任然有问题。最后发现还是因为创建链表时未初始建成环，更改 后就成功了。由于在链表的基础上再做的队列，所以在做队列时有前面链表和课本做 铺垫，没有遇到过多的麻烦。 6 6 测试结果测试结果 6.1 测试数据分析测试数据分析 测试敢死队人数为：2

13、0 预期测试结果：15 预期输出序列： 19 4 9 14 20 6 12 18 7 15 3 13 5 17 11 10 16 2 8 1 测试敢死队人数为：9 预期测试结果：3 预期输出序列： 7 3 9 6 5 8 2 4 1 测试敢死队人数为：5 预期测试结果：5 预期输出序列： 4 5 2 3 1 6.2 数据测试如下图数据测试如下图 6.2.16.2.1测试敢死队人数为：测试敢死队人数为：2020 链表实现如图链表实现如图 6-16-1 图 6-1 链表实现测试结果图 6.2.26.2.2测试敢死队人数为：测试敢死队人数为：2020 时队列实现如图时队列实现如图 6-26-2 图

14、6-2 队列现测试结果图 6.2.36.2.3测试敢死队人数为：测试敢死队人数为：9 9 时时 链表实现如图链表实现如图 6-36-3 图 6-3 链表实现测试结果图 6.2.46.2.4测试敢死队人数为：测试敢死队人数为：9 9 时队列实现如图时队列实现如图 6-46-4 图 6-4 队列现测试结果图 6.2.56.2.5测试敢死队人数为：测试敢死队人数为：5 5 时链表实现如图时链表实现如图 6-56-5 图 6-5 链表实现测试结果图 6.2.66.2.6测试敢死队人数为：测试敢死队人数为：6 6 时链表实现如图时链表实现如图 6-66-6 图 6-6 队列现测试结果图 7 7 结论结论

15、 7.17.1 算法分析算法分析: : 在程序设计前，如果按原题所设，则需设队长为第一位，再分别测试从第几个开 始才能符合条件。现在改变思想，通过数学思想：单循环链表本身是一个循环体，可 先求出当从第一个出发的话，求出每隔 5 个出去一个，剩下最后一个再令他与 1 号 （排长）对比，如果是 1 则符题目要求，输出结果。所以 f(x)=n*n,时间复杂度为 O（n*n）采用循环队列的数据结构方法实现，但其先进先出的算法结构加大了本程序 的时间及空间复杂度。所以 f(x)=n*n 程序时间复杂度为 O（n*n） 所以本程序空间复杂度为 f(x)=n*n 程序时间复杂度为 O（n*n） 7.27.2 总结：总结： 通过这次课程设计我又学到了很多东西,如程序的模块化设计思想，同时也加深了 对数据结构这门课程的理解和学会了如何在实际中应用数据结构. 第一个方法是用单循环链表来做的，实现的方法是这样的：首先从第一号开始报 数，循环到指定的偏移位置删除结点，直至剩下一个结点。然后设计输出，令这个位 置为队长位置，队首为开始报数的位置，并按此输出即为所求。 第二个方法是用队列