C语言版数据结构课程设计报告书.doc

. . . 数据结构课程设计资 料 袋计算机与通信 学院（系、部）20092010学年第二学期 课程名称数据结构指导教师职称 博士学生专业班级通信工程学号题 目编制车厢调度的程序成 绩起止日期2010年6月28日2010年7月10日目 录 清 单序号材 料 名 称资料数量备 注1课程设计任务书12课程设计说明书13课程设计图纸1456课程设计任务书2009 2010 学年第 二 学期计算机与通信学院（系、部）通信工程专业092班级课程名称：数据结构 设计题目：编制一个车厢调度的程序完成期限：自2010年6月28日至2010年7 月10 日共 一周容与任务一、设计的主要技术参数使用栈机制模拟迷宫的寻路过程, 图的DFS 自动生成随机迷宫地图。二、设计任务使用C语言实现各个模块的功能。三、设计工作量王灿阳负责对栈的基本操作，我实现车厢的调度的进和出，以与状态的变化。进度安排起止日期工作容2010-6-28设计本程序思路2010-6-30实现子程序模块函数2010-7-6将子程序和主程序构建成完整的C源程序，并且进行相关编译调试2010-7-7数据测试、形成文档指导教师（签字）：年 月 日系（教研室）主任（签字）：年 月 日XVIII / 18数据结构设计说明书数据结构课程设计编制一个车厢调度的程序起止日期： 2010年6月28日 至 2010年7月10日学生班级通信092班学号成绩指导教师(签字)计算机与通信学院（部）年 月 日工业大学课程设计情况分析表课程设计名称数据结构设计周数17周学院（部）计算机与通信学院系（教研室）通信工程系指导教师文志诚学生专业、班级通信工程0901选题车厢调度成绩分布优良中与格不与格学生数百分比学生课程设计存在的主要问题改进措施与建议指导教师（签字）：年 月 日系（教研室）主任（签字）：年 月 日备注：本表在课程设计完成后由指导教师填写，与课程设计资料一起存档。目录1. 题目 VI2.概要设计 VII3. 功能函数设计 XI4. 调试分析XIX5. 用户手册 XXI6. 测试结果XIV7. 附录 完整的程序清单 XV一、题目:编制一个车厢调度的程序.扩展:增加清屏函数；;增选择的功能;可显示所有的运行结果.需求分析( 1 )在教材书3.1.2节中提供的栈的顺序存储结构SqStack之上实现栈的基本操作，即实现栈类型。( 2 )程序对任何栈的任何存取（即更改、读取和状态判别等操作）必须借助于基本操作执行。( 3 ) 用户可以自己输入调度的大小 , 然后由程序自动生成结果.二、概要设计1. 设定栈的抽象数据类型定义 :ADT Stack 数据对象 : D=ai|aiADT MazeType , 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)初始条件 : 栈 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的元素 定一两个变量 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,pathi); printf(n); 3.本程序包含6个模块1) 主程序模块:int main()主菜单函数, 实现时间循环.return 0;/主函数2) 栈模块-实现栈抽象数据类型3) 递归模块-实现调度迷宫抽象数据类型4) 选择生成模块-用户自定义菜单的生成5) 调度模块-实现车站的模拟各模块之间的调用如下:主程序模块选择模块栈模块递归模块调度模块4.求解调度通路的伪码算法:设定当前位置的初值为入口位置;Do若当前位置可通,按任意键进行，同时选择你需要的功能if(m=1)输入你的你的车厢长度if(m=2)调用递归函数，输出所有可能的序列if(m=3)欢迎你使用，系统while ( 栈不空 ); 栈空说明没有路径存在 三、功能函数设计本系统主要是考虑对栈的使用，循环队列和双向链表的运用。-头文件设计(部分)-本部分是讲述栈的相关操作：#includestdlib.h#includestdafx.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()/出栈 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); printf( | 09级通信工程|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(请输入车厢长度: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);四:调试分析1. 本次作业比较简单 , 只是刚开始写的代码中虽然用到了递归去求解函数，但是不能很好的输完整结果，但是栈的相关操作是正确的,后来发现是由于调度递归算法中元素出栈后没有继续让其进栈。经改后恢复正常。2. 在设计调度初始化函数的时候,参数的传递出现错误,主要是对指针和引用的理解出现混淆,通过查阅相关资料, 弄清楚了两者之间的区别,指针是用于指向一个变量的地址,而引用只是对一个已存在变量的一个重命名. 3.用printf函数输出标志信息跟踪函数调用,收到了显著的效果,大大提高了调 试效率, 有利于以后的代码调试.3 使用了小部分的win32 API,发现使用局部句柄时,调用的winAPI不能正常运行,改成全局后问题解决.4. 在实现调度功能时发现,每次调用system(cls)函数时都进行清屏操作,屏幕只出现当前的操作目标,一目了然。用户进入系统只需按要求进行，操作时简洁清晰.代码中的主要算法:/输出一种可能的for(i=0;icurp;i+)的时间复杂度为 O( n ). 5. 经验体会: 参考书本的代码进行改进，使用模块化操作易于代码的调试和修改,而且易于阅读.在设计实现过程中虽然遇到了很多问题,但是在解决这些问题的过程中,巩固和加深了我们对已学知识的理解,对团队合作有了一个比较基础的认识,为以后的工作实践打下了基础，同时也增加了我们对这门课的认识.五.用户手册1.本程序的运行环境为 DOS 操作系统, 执行文件为Programming.exe.2.进入演示程序后 , 即显示文本方式的用户界面:操作提示信息键入选择3. 进入”建立自定义调度系统” 命令后, 根据提示输入你需要选择的序号,回车后即可得到”调度建立完成”的提示信息.操作命令清单4. 数据不合要求则会提示:5. 进入 “试测模拟调度” 命令后, 用户只需根据要求一步步的输入,按Enter键后.完成后,输出可能的结果。此为出口6. 输入 “3” 即可退出此演示程序.六. 测试结果1. 根据提示输入2. 输入第二组测试数据 ：3七、附录 完整的程序清单:#includestdlib.h#includestdafx.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) 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); /处理下一个元素，返回表明下一个元素进栈的情况处理完了,这里用递归将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); void main() int pathMaxLen; int m; char ch; printf( nnn - n); printf( | n); printf( |数据结构课程设计|n); printf( | |n); printf( | 铁路调度站模拟 |n); printf( | |n); printf( | 09级通信工程|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(请输入车厢长度: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);参考书：，,