1、数据结构课程设计吉林工程技术师范学院数据结构课程设计报告设计题目： 车厢调度程序 专业：软件工程 班级：R1142 学生姓名： 学号：02 指导教师： 王锐 高岚 2012年12月信息工程学院目录第一章 问题描述 31.题目 32.需求分析 3第二章 设计思路 41.菜单显示 42.调度过程 43.序列输出过程 4第三章 数据结构定义 5第四章 系统功能模块设计 9第五章 运行与调试 11总结 14附录 15参考文献 20第一章 问题描述1.题目假设停在铁路调度站入口处的车厢序列的编号一次为 1,2,3，n。设计一个程序，求出所有可能由此输出的长度为n的车厢序列。本设计程序用于实现有限个车厢调
2、度排序，用户可根据自身情况自行输入车厢调度的长度，本程序会根据用户所输入的长度自动进行排序。本程序增加选择的功能，可根据不同需要进行步骤的选择，并显示出所有可能的排序方法。2.需求分析( 1 )提供的栈的顺序存储结构SqStack之上实现栈的基本操作，即实现栈类型。( 2 )程序对任何栈的任何存取（即更改、读取和状态判别等操作）必须借助于基本操作执行。( 3 ) 用户可以自己输入调度的大小 , 然后由程序自动生成结果.第二章 设计思路1.菜单显示本系统主要的菜单显示有两个界面，一个是对本系统主要简介的界面，其中包括数据结构课程设计、铁路调度站模拟、11级软件工程。另一个是主要的操作界面，主要包
3、括1请输入火车长度、2输出所有可能序列、3退出本程序。2.调度过程本系统主要是利用栈进行定义和设计，主要依赖于栈的基本操作，首先判断站是否为空，如果非空则进行进栈操作，否则返回。所以每一个数根据以上出入栈的选择，将产生所有可能的车厢序列。本设计中还用到了递归的思想：数据入栈后，对数据有两种处理方法，进栈或者下一个数的进栈，一个数的出栈后也有两种处理方法，要么出栈，要么下一个数的进栈。3.序列输出过程根据栈的特性输出长度为N的所有车厢序列，按ENTER将显示所有的序列的显示。 第三章 数据结构定义1. 设定栈的抽象数据类型定义 :ADT Stack 数据对象 : D=ai|aiADT MazeT
4、ype , i = 0,1,2n , n0数据关系 : R1= | ai-1,ai D,i=2,n 基本操作 :InitStack(SqStack &s) 操作结果 : 构造一个空栈GetTop(SqStack s,SElemType &e) 初始条件 : 栈 s 以存在操作结果 : 获取栈顶元素 Push(SqStack &s,SElemType &e) 初始条件 : 栈 s 以存在操作结果 : 在栈顶插入新元素Pop(SqStack &s,SElemType &e) 初始条件 : 栈 s 以存在操作结果 : 删除栈顶元素,并删除e值StackEmpty(SqStack s) 初始条件 :
5、栈 s 以存在操作结果 : 判断栈是否为空ClearStack(SqStack &s) 初始条件 : 栈 s 以存在操作结果 : 将栈置为空栈 ADT SqStack;2. 设定车厢调度的抽象数据类型ADT MazeType 数据对象 : D=ai,j|ai,j ,#、*，0=i=m+1, 0=j=n+1,m,n=10 数据关系 : R=M,NM=|ai-1,j,ai,jD,i=1,m+1,j=0,n+1N=|ai-1,j,ai,jD,i=1,m+1,j=0,n+1 基本操作 : void process(int pos,int path,int curp)/当前处理位置pos的元素 定一两个
6、变量 if(posn)/编号进栈递归 push(pos+1);/当前元素进栈后下一个元素继续进栈 process(pos+1,path,curp); /处理下一个元素，返回表明下一个元素进栈的情况处理完了 pop(); /下一个元素处理完后，pop 掉，准备处理直接出栈 if(!Emptys()/递归处理出栈 m=pop(); pathcurp=m; /数组存放出栈元素 curp+; process(pos,path,curp);/出栈后处理下一个素继续进栈 push(m); if(pos=n&Emptys()/输出一种可能的方案 for(i=0;icurp;i+) printf(%2d,pa
7、thi); printf(n); 本系统主要是考虑对栈的使用，循环队列和双向链表的运用。-头文件设计（部分）- 本部分是讲述栈的相关操作：#includestdlib.h#include #includestdio.h#include #define MaxLen 100 struct Stack_node int dataMaxLen; int top; s; /定义一个栈指针 int n;/定义输入序列总个数 /-栈的基本操作-void Initstack() s.top=-1; void push(int q)/元素n进栈 s.top+; s.datas.top=q; int pop()
8、/出栈 int temp; temp=s.datas.top; s.top-; return temp; int Emptys()/判断栈空 if(s.top=-1) return 1; else return 0; -实现文件（部分）本部分是主控函数，函数的调用以及菜单的选择：main.cpp 主函数void main() int pathMaxLen; int m; char ch; printf( nnn - n); printf( | n); printf( |数据结构课程设计|n); printf( | |n); printf( | 铁路调度站模拟 |n); printf( | |n
9、); printf( | 11级软件工程|n); printf( | n); printf( -n); printf( 按任意键继续 n); if(ch=getch(); do / system(cls); /停顿 printf(nnn * n); printf( * 1:请输入火车的长度: *n); printf( * *n); printf( * 2:输出所有可能序列: *n); printf( * *n); printf( * 3:退出本程序: *n); printf( * n); printf( 请你根据需要选择序号n); scanf(%d,&m); if(m=1) printf(请输
10、入车厢长度:n); scanf(%d,&n); 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&m!=2&m!=3) printf(n输入有误!请重新输入!); getchar();/停止 getchar(); while(m!=3);第四章 系统功能模块设
11、计1) 主程序模块:int main() 主菜单函数, 实现时间循环. return 0;/主函数2) 栈模块-实现栈抽象数据类型3) 递归模块-实现调度迷宫抽象数据类型4) 选择生成模块-用户自定义菜单的生成5) 调度模块-实现车站的模拟各模块之间的调用如下: 第五章 运行与调试 1.本程序的运行环境为 DOS 操作系统, 执行文件为Programming.exe.2.进入演示程序后 , 即显示文本方式的用户界面:进入”建立自定义调度系统” 命令后, 根据提示输入你需要选择的序号,回车后即可得到”调度建立完成”的提示信息。2数据不合要求则会提示:1. 进入 “试测模拟调度” 命令后, 用户只
12、需根据要求一步步的输入,按Enter键后.完成后,输出可能的结果。2. 输入 “3” 即可退出此演示程序.根据提示输入输入第二组测试数据 ：3 总结 1.做本次课设, 刚开始写的代码中虽然用到了递归去求解函数，但是不能很好的输完整结果，但是栈的相关操作是正确的,后来发现是由于调度递归算法中元素出栈后没有继续让其进栈。经改后恢复正常。2.在设计调度初始化函数的时候,参数的传递出现错误,主要是对指针和引用的理解出现混淆,通过查阅相关资料, 弄清楚了两者之间的区别,指针是用于指向一个变量的地址,而引用只是对一个已存在变量的一个重命名.3.用printf函数输出标志信息跟踪函数调用,收到了显著的效果,
13、大大提高了调试效率, 有利于以后的代码调试. 4在实现调度功能时发现,每次调用system(cls)函数时都进行清屏操作,屏幕只出现当前的操作目标,一目了然。用户进入系统只需按要求进行，操作时简洁清晰.代码中的主要算法:/输出一种可for(i=0;icurp;i+)的时间复杂度为 O( n ).5.经验体会: 参考书本的代码进行改进，使用模块化操作易于代码的调试和修改,而且易于阅读.在设计实现过程中虽然遇到了很多问题,但是在解决这些问题的过程中,巩固和加深了我们对已学知识的理解,对团队合作有了一个比较基础的认识,为以后的工作实践打下了基础，同时也增加了我们对这门课的认识.附录 #include
14、stdlib.h#includestdio.h#include #includewindows.h #define MaxLen 100 struct snode int dataMaxLen; int top; s; /定义一个栈指针 int n;/定义输入序列总个数 void Initstack() s.top=-1; void push(int q)/元素n进栈 s.top+; s.datas.top=q; int pop()/出栈 int temp; temp=s.datas.top; s.top-; return temp; int Emptys()/判断栈空 if(s.top=-1
15、) return 1; else return 0; /* 每次调用求值阶段包含两重递归，只有全部返回，才表示本pos 处理完，可以对上一个元素求值，process 就是找出当前元素进栈后所有可能的操作，即在当前元素进栈后各种情况下， 包括不出栈，立即出栈，出栈后继续出栈情况(出栈递归)下，继续处理下一个元素(入栈递归) */ void process(int pos,int path,int curp)/当前处理位置pos的元素 int m,i; if(posn)/编号进栈递归 push(pos+1);/当前元素进栈后下一个元素继续进栈 process(pos+1,path,curp); /
16、处理下一个元素，返回表明下一个元素进栈的情况处理完了,这里用递归将2,3,4.n压入栈 pop(); /下一个元素处理完后，pop 掉，准备处理直接出栈 if(!Emptys()/递归处理出栈 m=pop(); pathcurp=m; /数组存放出栈元素 curp+; process(pos,path,curp);/出栈后处理下一个素继续进栈, 用递归将n,.4,3,2,1压入栈 push(m);/ 递归完后又按原顺序将1,2,3,4.n压入栈 if(pos=n&Emptys()/输出一种可能的方案 for(i=0;icurp;i+) printf(%2d,pathi); printf(n);
17、 void main() int pathMaxLen; int m; char ch; printf( nnn - 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(nnn * n); printf( * 1:请输入火车的长度: *n); p
18、rintf( * *n); printf( * 2:输出所有可能序列: *n); printf( * *n); printf( * 3:退出本程序: *n); printf( * n); printf( 请你根据需要选择序号n); scanf(%d,&m); if(m=1) printf(请输入车厢长度:n); scanf(%d,&n); 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&m!=2&m!=3) printf(n输入有误!请重新输入!); getchar();/停止 getchar(); while(m!=3);参考文献 ISBN：9787302246039 数据结构（C语言）版 清华大学出版社 秦锋ISBN：9787030306609 数据结构 科学出版社 江家宝ISBN：9787512305458 数据结构与算法中国电力出版社 肖侬
