数据结构课程设计.docx
- 文档编号:9371675
- 上传时间:2023-05-18
- 格式:DOCX
- 页数:18
- 大小:79.84KB
数据结构课程设计.docx
《数据结构课程设计.docx》由会员分享,可在线阅读,更多相关《数据结构课程设计.docx(18页珍藏版)》请在冰点文库上搜索。
数据结构课程设计
吉林工程技术师范学院
《数据结构》课程设计报告
设计题目:
车厢调度程序
专业:
软件工程班级:
R1142
学生姓名:
学号:
02
指导教师:
王锐高岚
2012年12月
信息工程学院
目录
第一章问题描述3
1.题目3
2.需求分析3
第二章设计思路4
1.菜单显示4
2.调度过程4
3.序列输出过程4
第三章数据结构定义5
第四章系统功能模块设计9
第五章运行与调试11
总结14
附录15
参考文献20
第一章问题描述
1.题目
假设停在铁路调度站入口处的车厢序列的编号一次为1,2,3,……,n。
设计一个程序,求出所有可能由此输出的长度为n的车厢序列。
本设计程序用于实现有限个车厢调度排序,用户可根据自身情况自行输入车厢调度的长度,本程序会根据用户所输入的长度自动进行排序。
本程序增加选择的功能,可根据不同需要进行步骤的选择,并显示出所有可能的排序方法。
2.需求分析
(1)提供的栈的顺序存储结构SqStack之上实现栈的基本操作,即实现栈类型。
(2)程序对任何栈的任何存取(即更改、读取和状态判别等操作)必须借助于基本操作执行。
(3)用户可以自己输入调度的大小,然后由程序自动生成结果.
第二章设计思路
1.菜单显示
本系统主要的菜单显示有两个界面,一个是对本系统主要简介的界面,其中包括数据结构课程设计、铁路调度站模拟、11级软件工程。
另一个是主要的操作界面,主要包括1请输入火车长度、2输出所有可能序列、3退出本程序。
2.调度过程
本系统主要是利用栈进行定义和设计,主要依赖于栈的基本操作,首先判断站是否为空,如果非空则进行进栈操作,否则返回。
所以每一个数根据以上出入栈的选择,将产生所有可能的车厢序列。
本设计中还用到了递归的思想:
数据入栈后,对数据有两种处理方法,进栈或者下一个数的进栈,一个数的出栈后也有两种处理方法,要么出栈,要么下一个数的进栈。
3.序列输出过程
根据栈的特性输出长度为N的所有车厢序列,按ENTER将显示所有的序列的显示。
第三章数据结构定义
1.设定栈的抽象数据类型定义:
ADTStack{
数据对象:
D={ai|ai∈ADTMazeType,i=0,1,2……n,n≥0}
数据关系:
R1={
基本操作:
InitStack(SqStack&s)
操作结果:
构造一个空栈
GetTop(SqStacks,SElemType&e)
初始条件:
栈s以存在
操作结果:
获取栈顶元素
Push(SqStack&s,SElemType&e)
初始条件:
栈s以存在
操作结果:
在栈顶插入新元素
Pop(SqStack&s,SElemType&e)
初始条件:
栈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={
N={
基本操作:
voidprocess(intpos,intpath[],intcurp)//当前处理位置pos的元素
{
定一两个变量
if(pos { 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;i printf("%2d",path[i]); printf("\n"); }} 本系统主要是考虑对栈的使用,循环队列和双向链表的运用。 ---------头文件设计(部分)----- 本部分是讲述栈的相关操作: #include"stdlib.h" #include #include"stdio.h" #include #defineMaxLen100 structStack_node { intdata[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; else return0; } ------实现文件(部分)———— 本部分是主控函数,函数的调用以及菜单的选择: 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"); 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)主程序模块: intmain() { 主菜单函数,实现时间循环. return0; }//主函数 2)栈模块----实现栈抽象数据类型 3)递归模块----实现调度迷宫抽象数据类型 4)选择生成模块----用户自定义菜单的生成 5)调度模块----实现车站的模拟 各模块之间的调用如下: 第五章运行与调试 1.本程序的运行环境为DOS操作系统,执行文件为Programming.exe. 2.进入演示程序后,即显示文本方式的用户界面: 进入”建立自定义调度系统”命令后,根据提示输入你需要选择的序号,回车后即可得到”调度建立完成”的提示信息。 2数据不合要求则会提示: 1.进入“试测模拟调度”命令后,用户只需根据要求一步步的输入,按Enter键后.完成后,输出可能的结果。 2.输入“3”即可退出此演示程序. 根据提示输入 输入第二组测试数据: 3 总结 1.做本次课设,刚开始写的代码中虽然用到了递归去求解函数,但是不能很好的输完整结果,但是栈的相关操作是正确的,后来发现是由于调度递归算法中元素出栈后没有继续让其进栈。 经改后恢复正常。 2.在设计调度初始化函数的时候,参数的传递出现错误,主要是对指针和引用的理解出现混淆,通过查阅相关资料,弄清楚了两者之间的区别,指针是用于指向一个变量的地址,而引用只是对一个已存在变量的一个重命名. 3.用printf函数输出标志信息跟踪函数调用,收到了显著的效果,大大提高了调试效率,有利于以后的代码调试. 4.在实现调度功能时发现,每次调用system("cls")函数时都进行清屏操作,屏幕只出现当前的操作目标,一目了然。 用户进入系统只需按要求进行,操作时简洁清晰.代码中的主要算法: //输出一种可for(i=0;i 5.经验体会: 参考书本的代码进行改进,使用模块化操作易于代码的调试和修改,而且易于阅读.在设计实现过程中虽然遇到了很多问题,但是在解决这些问题的过程中,巩固和加深了我们对已学知识的理解,对团队合作有了一个比较基础的认识,为以后的工作实践打下了基础,同时也增加了我们对这门课的认识. 附录 #include"stdlib.h" #include"stdio.h" #include #include"windows.h" #defineMaxLen100 structsnode { intdata[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; else return0; } /* 每次调用求值阶段包含两重递归,只有全部返回,才表示本pos处理完,可以对上一个元素求值, process就是找出当前元素进栈后所有可能的操作,即在当前元素进栈后各种情况下, 包括不出栈,立即出栈,出栈后继续出栈情况(出栈递归)下,继续处理下一个元素(入栈递归) */ voidprocess(intpos,intpath[],intcurp)//当前处理位置pos的元素 { intm,i; if(pos { push(pos+1);//当前元素进栈后下一个元素继续进栈 process(pos+1,path,curp);//处理下一个元素,返回表明下一个元素进栈的情况处理完了,这里用递归将2,3,4....n压入栈 pop();//下一个元素处理完后,pop掉,准备处理直接出栈 } if(! Emptys())//递归处理出栈 { m=pop(); path[curp]=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;i printf("%2d",path[i]); printf("\n"); } } 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"); 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《数据结构与算法》中国电力出版社肖侬
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 课程设计