数据结构课程设计5

《数据结构课程设计5》由会员分享，可在线阅读，更多相关《数据结构课程设计5（28页珍藏版）》请在金锄头文库上搜索。

1、 Word 文档 吉林工程技术师范学院 数据结构 课程设计报告 设计题目 车厢调度程序 专业 软件工程 班级 R1142 学生姓名 学号 02 指导教师 王锐 高岚 2 2012 年 12 月 信息工程学院 目录 第一章 问题描述 3 1 题目 3 2 需求分析 3 第二章 设计思路 4 1 菜单显示 4 2 调度过程 4 3 序列输出过程 4 第三章 数据结构定义 5 第四章 系统功能模块设计 9 第五章 运行与调试 11 总结 14 3 附录 15 参考文献 20 第一章 问题描述 1 题目 假设停在铁路调度站入口处的车厢序列的编号一次为 1 2 3 n 设计一个程序 求出所有可能由此输出

2、的长度 为 n 的车厢序列 本设计程序用于实现有限个车厢调度排序 用 户可根据自身情况自行输入车厢调度的长度 本程序会根据用户 所输入的长度自动进行排序 本程序增加选择的功能 可根据不 同需要进行步骤的选择 并显示出所有可能的排序方法 2 需求分析 1 提供的栈的顺序存储结构 SqStack 之上实现栈的基本 操作 即实现栈类型 2 程序对任何栈的任何存取 即更改 读取和状态判别 等操作 必须借助于基本操作执行 3 用户可以自己输入调度的大小 然后由程序自动生 成结果 4 第二章 设计思路 1 菜单显示 本系统主要的菜单显示有两个界面 一个是对本系统主要简介的 界面 其中包括数据结构课程设计

3、铁路调度站模拟 11 级软 件工程 另一个是主要的操作界面 主要包括 1 请输入火车长度 2 输出所有可能序列 3 退出本程序 5 2 调度过程 本系统主要是利用栈进行定义和设计 主要依赖于栈的基本操作 首先判断站是否为空 如果非空则进行进栈操作 否则返回 所 以每一个数根据以上出入栈的选择 将产生所有可能的车厢序列 本设计中还用到了递归的思想 数据入栈后 对数据有两种处理 方法 进栈或者下一个数的进栈 一个数的出栈后也有两种处理 方法 要么出栈 要么下一个数的进栈 3 序列输出过程 根据栈的特性输出长度为 N 的所有车厢序列 按 ENTER 将显示所 有的序列的显示 第三章 数据结构定义 1

4、 设定栈的抽象数据类型定义 ADT Stack 数据对象 D ai ai ADT MazeType i 0 1 2 n n 0 数据关系 R1 ai 1 ai D i 2 n 基本操作 InitStack SqStack 2 设定车厢调度的抽象数据类型 ADT MazeType 数据对象 D ai j ai j 0 i m 1 0 j n 1 m n 10 数据关系 R M N M ai 1 j ai j D i 1 m 1 j 0 n 1 N ai 1 j ai j D i 1 m 1 j 0 n 1 基本操作 void process int pos int path int curp 当

5、前处理位置 pos 的元素 定一两个变量 if pos n 编号进栈递归 7 push pos 1 当前元素进栈后下一个元素继 续进栈 process pos 1 path curp 处理下一个 元素 返回表明下一个元素进栈的情况处理完了 pop 下一个元素处理完后 pop 掉 准备处理直接出栈 if Emptys 递归处理出栈 m pop path curp m 数组存放出栈元素 curp process pos path curp 出栈后处 理下一个素继续进栈 push m if pos ni curp i printf 2d path i printf n 本系统主要是考虑对栈的使用 循

6、环队列和双向链表的运用 头文件设计 部分 本部分是讲述栈的相关操作 include stdlib h include include stdio h include define MaxLen 100 struct Stack node 8 int data MaxLen int top s 定义一个栈指针 int n 定义输入序列总个数 栈的基本操作 void Initstack s top 1 void push int q 元素 n 进栈 s top s data s top q int pop 出栈 int temp temp s data s top s top return tem

7、p int Emptys 判断栈空 if s top 1 return 1 else return 0 实现文件 部分 实现文件 部分 本部分是主控函数 函数的调用以及菜单的选择 main cppmain cpp 主函数主函数 void main int path MaxLen 9 int m char ch printf n n n n printf n printf 数据结构课程设计 n printf n printf 铁路调度站模拟 n printf n printf 11 级软件工程 n printf n printf n printf 按任意键继续 n if ch getch do

8、system cls 停顿 printf n n n n printf 1 请输入火车的长度 n printf n printf 2 输出所有可能序列 n printf n printf 3 退出本程序 n printf n printf 请你根据需要选择序号 n scanf d if m 1 printf 请输入车厢长度 n scanf d printf 车厢长度已输入 n getchar 停止 getchar if m 2 Initstack 10 push 1 printf 所有输出序列 n process 1 path 0 从 1 开始 递归处理所有元素 getchar 停止 getc

9、har if m 3 printf 欢迎退出 n printf n if m 1 getchar 停止 getchar while m 3 第四章 系统功能模块设计 1 主程序模块 int main 主菜单函数 实现时间循环 return 0 主函数 2 栈模块 实现栈抽象数据类型 3 递归模块 实现调度迷宫抽象数据类型 11 4 选择生成模块 用户自定义菜单的生成 5 调度模块 实现车站的模拟 各模块之间的调用如下各模块之间的调用如下 第五章 运行与调试 1 本程序的运行环境为 DOS 操作系统 执行文件为 Programming exe 2 进入演示程序后 即显示文本方式的用户界面 主程序

10、模块主程序模块 选择模块选择模块 调度模块调度模块 递归模块递归模块栈模块栈模块 12 进入 建立自定义调度系统 命令后 根据提示输入你 需要选择的序号 回车后即可得到 调度建立完成 的提 示信息 2 数据不合要求则会提示 1 进入 试测模拟调度 命令后 用户只需根据要求 一步步的输入 按 Enter 键后 完成后 输出可能的结 果 键入选择项 操作命令清单 操作提示信息 13 2 输入 3 即可退出此演示程序 根据提示输入根据提示输入 14 输入第二组测试数据输入第二组测试数据 3 3 总结 1 做本次课设 刚开始写的代码中虽然用到了递归去求解函数 但是不能很好的输完整结果 但是栈的相关操作

11、是正确的 后来 发现是由于调度递归算法中元素出栈后没有继续让其进栈 经改 后恢复正常 2 在设计调度初始化函数的时候 参数的传递出现错误 主要是对 指针和引用的理解出现混淆 通过查阅相关资料 弄清楚了两者 之间的区别 指针是用于指向一个变量的地址 而引用只是对一个 已存在变量的一个重命名 3 用 printf 函数输出标志信息跟踪函数调用 收到了显著的效果 大 大提高了调试效率 有利于以后的代码调试 4 在实现调度功能时发现 每次调用 system cls 函数时都进 行清屏操作 屏幕只出现当前的操作目标 一目了然 用户进入系 统只需按要求进行 操作时简洁清晰 代码中的主要算法 输出 一种可

12、for i 0 i curp i 的时间复杂度为 O n 5 经验体会 参考书本的代码进行改进 使用模块化操作易于代 码的调试和修改 而且易于阅读 在设计实现过程中虽然遇到了很 15 多问题 但是在解决这些问题的过程中 巩固和加深了我们对已学 知识的理解 对团队合作有了一个比较基础的认识 为以后的工作 实践打下了基础 同时也增加了我们对这门课的认识 附录 include stdlib h include stdio h include include windows h define MaxLen 100 struct snode int data MaxLen int top s 定义一个栈

13、指针 int n 定义输入序列总个数 void Initstack s top 1 void push int q 元素 n 进栈 16 s top s data s top q int pop 出栈 int temp temp s data s top s top return temp int Emptys 判断栈空 if s top 1 return 1 else return 0 每次调用求值阶段包含两重递归 只有全部返回 才表示本 pos 处理完 可以对上一个元素求值 process 就是找出当前元素进栈后所有可能的操作 即在当前元 素进栈后各种情况下 包括不出栈 立即出栈 出栈后继

14、续出栈情况 出栈递归 下 继 续处理下一个元素 入栈递归 17 void process int pos int path int curp 当前处理 位置 pos 的元素 int m i if pos n 编号进栈递归 push pos 1 当前元素进栈后下一个元素继续进栈 process pos 1 path curp 处理下一个元素 返回表明 下一个元素进栈的情况处理完了 这里用递归将 2 3 4 n 压入 栈 pop 下一个元素处理完后 pop 掉 准备处理直 接出栈 if Emptys 递归处理出栈 m pop path curp m 数组存放出栈元素 curp process po

15、s path curp 出栈后处理下一个素继续 进栈 用递归将 n 4 3 2 1 压入栈 push m 递归完后又按原顺序将 1 2 3 4 n 压入 栈 if pos ni curp i printf 2d path i printf n void main int path MaxLen int m char ch printf n n n n printf n printf 数据结构课程设计 n printf n printf 铁路调度站模拟 n printf n printf 11 级软件工程 n printf n printf n printf 按任意键继续 n if ch get

16、ch do system cls 停顿 19 printf n n n n printf 1 请输入火车的长度 n printf n printf 2 输出所有可能序列 n printf n printf 3 退出本程序 n printf n printf 请你根据需要选择序号 n scanf d if m 1 printf 请输入车厢长度 n scanf d printf 车厢长度已输入 n getchar 停止 getchar if m 2 Initstack push 1 printf 所有输出序列 n process 1 path 0 从 1 开始 递归处理所有元素 getchar 停止 20 getchar if m 3 printf 欢迎退出 n printf n if m 1 getchar 停止 getchar while m 3 参考文献 ISBN 9787302246039 数据结构 C 语言 版 清华大学出版社 秦锋 ISBN 9787030306609 数据结构 科学出版社 江家宝 ISBN 9787512305458 数据结构与算法 中国电力出版社 肖侬