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

I1数据结构课程设计资料袋计算机与通信学院（系、部）2009~2010学年第二学期课程名称数据结构指导教师职称博士学生姓名专业班级通信工程学号题目编制车厢调度的程序成绩起止日期2010年6月28日～2010年7月10日目录清单序号材料名称资料数量备注1课程设计任务书12课程设计说明书13课程设计图纸1张456II2课程设计任务书2009—2010学年第二学期计算机与通信学院（系、部）通信工程专业092班级课程名称：数据结构设计题目：编制一个车厢调度的程序完成期限：自2010年6月28日至2010年7月10日共一周内容及任务一、设计的主要技术参数使用栈机制模拟迷宫的寻路过程,图的DFS自动生成随机迷宫地图。二、设计任务使用C语言实现各个模块的功能。三、设计工作量王灿阳负责对栈的基本操作，我实现车厢的调度的进和出，以及状态的变化。进度安排起止日期工作内容2010-6-28设计本程序思路2010-6-30实现子程序模块函数2010-7-6将子程序和主程序构建成完整的C源程序，并且进行相关编译调试2010-7-7数据测试、形成文档指导教师（签字）：年月日系（教研室）主任（签字）：年月日IIIIII数据结构设计说明书数据结构课程设计编制一个车厢调度的程序起止日期：2010年6月28日至2010年7月10日学生姓名班级通信092班学号成绩指导教师(签字)IVIV计算机与通信学院（部）年月日湖南工业大学课程设计情况分析表课程设计名称数据结构设计周数17周学院（部）计算机与通信学院系（教研室）通信工程系指导教师文志诚学生专业、班级通信工程0901选题车厢调度成绩分布优良中及格不及格学生数百分比学生课程设计存在的主要问题改进措施及建议指导教师（签字）：年月日系（教研室）主任（签字）：年月日备注：本表在课程设计完成后由指导教师填写，与课程设计资料一起存档。VV目录1.题目……………………………………………VI2.概要设计………………………………………VII3.功能函数设计………………………………XI4.调试分析……………………………………XIX5.用户手册……………………………………XXI6.测试结果……………………………………XIVVIVI7.附录完整的程序清单……………………XV一、题目:编制一个车厢调度的程序.扩展:增加清屏函数；;增选择的功能;可显示所有的运行结果.需求分析(1)在教材书3.1.2节中提供的栈的顺序存储结构SqStack之上实现栈的基本操作，即实现栈类型。(2)程序对任何栈的任何存取（即更改、读取和状态判别等操作）必须借助于基本操作执行。(3)用户可以自己输入调度的大小,然后由程序自动生成结果.二、概要设计1.设定栈的抽象数据类型定义:ADTStack{数据对象:D={ai|ai∈ADTMazeType,i=0,1,2……n,n≥0}数据关系:R1={ai-1,ai|ai-1,ai∈D,i=2,……n}基本操作:InitStack(SqStack&s)操作结果:构造一个空栈GetTop(SqStacks,SElemType&e)初始条件:栈s以存在操作结果:获取栈顶元素Push(SqStack&s,SElemType&e)初始条件:栈s以存在操作结果:在栈顶插入新元素Pop(SqStack&s,SElemType&e)VIIVII初始条件:栈s以存在操作结果:删除栈顶元素,并删除e值StackEmpty(SqStacks)初始条件:栈s以存在操作结果:判断栈是否为空ClearStack(SqStack&s)初始条件:栈s以存在操作结果:将栈置为空栈}ADTSqStack;2.设定车厢调度的抽象数据类型ADTMazeType{数据对象: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|ai-1,j,ai,j∈D,i=1,……,m+1,j=0,……,n+1}N={ai-1,j,ai,j|ai-1,j,ai,j∈D,i=1,……,m+1,j=0,……,n+1}基本操作:voidprocess(intpos,intpath[],intcurp)//当前处理位置pos的元素{定一两个变量if(posn)//编号进栈递归{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==n&&Emptys())//输出一种可能的方案{for(i=0;icurp;i++)printf(%2d,path[i]);VIIIVIIIprintf(\n);}}3.本程序包含6个模块1)主程序模块:intmain(){主菜单函数,实现时间循环.return0;}//主函数2)栈模块----实现栈抽象数据类型3)递归模块----实现调度迷宫抽象数据类型4)选择生成模块----用户自定义菜单的生成5)调度模块----实现车站的模拟各模块之间的调用如下:4.求解调度通路的伪码算法:主程序模块选择模块调度模块递归模块栈模块IXIX设定当前位置的初值为入口位置;Do{若当前位置可通,按任意键进行，同时选择你需要的功能if(m==1){输入你的你的车厢长度}if(m==2){调用递归函数，输出所有可能的序列}if(m==3){欢迎你使用，系统}}while(栈不空);{栈空说明没有路径存在}三、功能函数设计本系统主要是考虑对栈的使用，循环队列和双向链表的运用。--------------------------头文件设计(部分)---------------------本部分是讲述栈的相关操作：#includestdlib.h#includestdafx.h#includewindows.h#includestdio.h#includeconio.h#defineMaxLen100structStack_node{intdata[MaxLen];inttop;}s;//定义一个栈指针intn;//定义输入序列总个数//----------------栈的基本操作----------------voidInitstack(){s.top=-1;}voidpush(intq)//元素n进栈{XXs.top++;s.data[s.top]=q;}intpop()//出栈{inttemp;temp=s.data[s.top];s.top--;returntemp;}intEmptys()//判断栈空{if(s.top==-1)return1;elsereturn0;}------------------------实现文件(部分)---------------------------本部分是主控函数，函数的调用以及菜单的选择：main.cpp主函数voidmain(){intpath[MaxLen];intm;charch;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);XIXIprintf(*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.做本次课设,刚开始写的代码中虽然用到了递归去求解函数，但是不能很好的输完整结果，但是栈的相关操作是正确的,后来发现是由于调度递归算法XIIXII中元素出栈后没有继续让其进栈。经改后恢复正常。2.在设计调度初始化函数的时候,参数的传递出现错误,主要是对指针和引用的理解出现混淆,通过查阅相关资料,弄清楚了两者之间的区别,指针是用于指向一个变量的地址,而引用只是对一个已存在变量的一个重命名.3.用printf函数输出标志信息跟踪函数调用,收到了显著的效果,大大提高了调试效率,有利于以后的代码调试.4.在实现调度功能时发现,每次调用system(cls)函数时都进行清屏操作,屏幕只出现当前的操作目标,一目了然。用户进入系统只需按要求进行，操作时简洁清晰.代码中的主要算法://输出一种可能的for(i=0;icurp;i++)的时间复杂度为O(n).5.经验体会:参考书本的代码进行改进，使用模块化操作易于代码的调试和修改,而且易于阅读.在设计实现过程中虽然遇到了很多问题,但是在解决这些问题的过程中,巩固和加深了我们对已学知识的理解,对团队合作有了一个比较基础的认识,为以后的工作实践打下了基础，同时也增加了我们对这门课的认识.五.用户手册1.本程序的运行环境为DOS操作系统,执行文件为Programming.exe.2.进入演示程序后,即显示文本方式的用户界面:XIIIXIII3.进入”建立自定义调度系统”命令后,根据提示输入你需要选择的序号,回车后即可得到”调度建立完成”的提示信息.4.数据不合要求则会提示:键入选择操作命令清单操作提示信息XIVXIV5.进入“试测模拟调度”命令后,用户只需根据要求一步步的输入,按Enter键后.完成后,输出可能的结果。6.输入“3”即可退出此演示程序.XVXV六.测试结果1.根据提示输入2.输入第二组测试数据：3七、附录完整的程序清单:#includestdlib.h#includestdafx.h#includestdio.h#includeconio.h#includewindows.h#defineMaxLen100structsnode{XVIXVIintdata[MaxLen];inttop;}s;//定义一个栈指针intn;//定义输入序列总个数voidInitstack(){s.top=-1;}voidpush(intq)//元素n进栈{s.top++;s.data[s.top]=q;}intpop()//出栈{inttemp;temp=s.data[s.top];s.top--;returntemp;}intEmptys()//判断栈空{if(s.top==-1)return1;elsereturn0;}/*每次调用求值阶段包含两重递