C语言版数据结构课程设计

I 1 数据结构课程设计 资 料 袋 计算机与通信 学院 系 部 2009 2010 学年第 二 学期 课程名称 数据结构 指导教师 职称 博士 学生姓名 专业班级 通信工程 学号 题 目 编制车厢调度的程序 成 绩 起止日期 2010 年 6 月 28 日 2010 年 7 月 10 日 目 录 清 单 序号材 料 名 称资料数量备 注 1课程设计任务书1 2课程设计说明书1 3课程设计图纸1张 4 5 6 II 2 课程设计任务书 2009 2010 学年第学年第 二二 学期学期 计算机与通信 学院 系 部 通信工程 专业 092 班级 课程名称 数据结构 设计题目 编制一个车厢调度的程序 完成期限 自 2010 年 6 月 28 日至 2010 年 7 月 10 日共 一 周 内 容 及 任 务 一 设计的主要技术参数 使用栈机制模拟迷宫的寻路过程 图的 DFS 自动生成随机迷宫地图 二 设计任务 使用 C 语言实现各个模块的功能 三 设计工作量 王灿阳负责对栈的基本操作 我实现车厢的调度的进和出 以及状态的变化 起止日期工作内容 2010 6 28设计本程序思路 2010 6 30实现子程序模块函数 2010 7 6 将子程序和主程序构建成完整的 C 源程序 并且进行相关编译 调试 进 度 安 排 2010 7 7数据测试 形成文档 指导教师 签字 年 月 日 系 教研室 主任 签字 年 月 日 III III 数据结构数据结构 设计说明书 数据结构课程设计 编制一个车厢调度的程序编制一个车厢调度的程序 起止日期 2010 年 6 月 28 日 至 2010 年 7 月 10 日 学生 姓名 班级通信 092 班 学号 成绩 指导教师 签字 IV IV 计算机与通信学院 部 计算机与通信学院 部 年年 月月 日日 湖南工业大学课程设计情况分析表湖南工业大学课程设计情况分析表 课程设计名称数据结构设计周数17 周 学院 部 计算机与通信学院系 教研室 通信工程系 指导教师文志诚 学生专业 班级通信工程 0901 选题 车厢调度 优良中及格不及格 学生数成绩分布 百分比 学生课程设计存在 的主要问题 改进措施及建议 指导教师 签字 年 月 日 系 教研室 主任 签字 年 月 日 备注 本表在课程设计完成后由指导教师填写 与课程设计资料一起存档 V V 目录目录 1 1 题目题目 VIVI 2 2 概要设计概要设计 VII VII 3 3 功能函数设计功能函数设计 XI XI 4 4 调试分调试分析析 XIX XIX 5 5 用户手册用户手册 XXI XXI 6 6 测试测试结结果果 XI XIV V VI VI 7 7 附录附录 完整的程序清单完整的程序清单 XVXV 一 题目一 题目 编制一个车厢调度的程序 扩展扩展 增加清屏函数 增选择的功能 可显示所有的运行结果 需求分析需求分析 1 在教材书 3 1 2 节中提供的栈的顺序存储结构 SqStack 之上实现栈的基本操作 即实现栈类 型 2 程序对任何栈的任何存取 即更改 读取和状态判别等操作 必须借助于基本操作执行 3 用户可以自己输入调度的大小 然后由程序自动生成结果 二 概要设计二 概要设计 1 1 设定栈的抽象数据类型定义设定栈的抽象数据类型定义 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 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 当前处理位置 pos 的元素 定一两个变量 if pos n 编号进栈递归 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 VIII VIII printf 2d path i printf n 3 3 本程序包含本程序包含 6 6 个模块个模块 1 主程序模块 int main 主菜单函数 实现时间循环 return 0 主函数 2 栈模块 实现栈抽象数据类型 3 递归模块 实现调度迷宫抽象数据类型 4 选择生成模块 用户自定义菜单的生成 5 调度模块 实现车站的模拟 各模块之间的调用如下各模块之间的调用如下 4 4 求解调度通路的伪码算法求解调度通路的伪码算法 主程序模块主程序模块 选择模块选择模块 调度模块调度模块 递归模块递归模块栈模块栈模块 IX IX 设定当前位置的初值为入口位置 Do 若当前位置可通 按任意键进行 同时选择你需要的功能 if m 1 输入你的你的车厢长度 if m 2 调用递归函数 输出所有可能的序列 if m 3 欢迎你使用 系统 while 栈不空 栈空说明没有路径存在 三 功能函数设计三 功能函数设计 本系统主要是考虑对栈的使用 循环队列和双向链表的运用 头文件设计头文件设计 部分部分 本部分是讲述栈的相关操作 include stdlib h include stdafx h include include stdio h include define MaxLen 100 struct Stack node int data MaxLen int top s 定义一个栈指针 int n 定义输入序列总个数 栈的基本操作 void Initstack s top 1 void push int q 元素 n 进栈 X X 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 实现文件实现文件 部分部分 本部分是主控函数 函数的调用以及菜单的选择 main cppmain cpp 主函数主函数 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 getch do system cls 停顿 printf n n n n printf 1 请输入火车的长度 n XI XI 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 停止 getchar if m 3 printf 欢迎退出 n printf n if m 1 getchar 停止 getchar while m 3 四四 调试分析调试分析 1 做本次课设 刚开始写的代码中虽然用到了递归去求解函数 但是不能很 好的输完整结果 但是栈的相关操作是正确的 后来发现是由于调度递归算 XII XII 法中元素出栈后没有继续让其进栈 经改后恢复正常 2 在设计调度初始化函数的时候 参数的传递出现错误 主要是对指针和引用 的理解出现混淆 通过查阅相关资料 弄清楚了两者之间的区别 指针是用 于指向一个变量的地址 而引用只是对一个已存在变量的一个重命名 3 用 printf 函数输出标志信息跟踪函数调用 收到了显著的效果 大大提高了 调 试效率 有利于以后的代码调试 4 在实现调度功能时发现 每次调用 system cls 函数时都进行清屏操作 屏 幕只出现当前的操作目标 一目了然 用户进入系统只需按要求进行 操作 时简洁清晰 代码中的主要算法 输出一种可能的 for i 0 i curp i 的时间复杂度 为 O n 5 经验体会 参考书本的代码进行改进 使用模块化操作易于代码的调试和 修改 而且易于阅读 在设计实现过程中虽然遇到了很多问题 但是在解决这些问 题的过程中 巩固和加深了我们对已学知识的理解 对团队合作有了一个比较基础 的认识 为以后的工作实践打下了基础 同时也增加了我们对这门课的认识 五五 用户手册用户手册 1 本程序的运行环境为 DOS 操作系统 执行文件为 Programming exe 2 进入演示程序后 即显示文本方式的用户界面 XIII XIII 3 进入 建立自定义调度系统 命令后 根据提示输入你需要选择的序号 回车后即可得到 调度建立完成 的提示信息 4 数据不合要求则会提示 键入选择 操作命令清单 操作提示信息 XIV XIV 5 进入 试测模拟调度 命令后 用户只需根据要求一步步的输入 按 Enter 键后 完成后 输出可能的结果 6 输入 3 即可退出此演示程序 XV XV 六六 测试结果测试结果 1 1 根据提示输入根据提示输入 2 2 输入第二组测试数据输入第二组测试数据 3 3 七 附录七 附录 完整的程序清单完整的程序清单 include stdlib h include stdafx h include stdio h include include windows h define MaxLen 100 struct snode XVI XVI 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 temp int Emptys 判断栈空 if s top 1 return 1 else return 0 每次调用求值阶段包含两重递归 只有全部返回 才表示本 pos 处理完 可以对上一个元素求值 process 就是找出当前元素进栈后所有可能的操作 即在当前元素进栈后各种情况下 包括不出栈 立即出栈 出栈后继续出栈情况 出栈递归 下 继续处理下一个元素 入栈递归 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 递归处理出栈 XVII XVII m pop path curp m 数组存放出栈元素 curp process pos 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 getch do system cls 停顿 printf n n n n printf 1 请输入火车的长度 n printf n printf 2 输出所有可能序列 n printf n printf 3 退出本