数据结构课程设计.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={|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）
初始条件:
栈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∈D,i=1,……,m+1,j=0,……,n+1}
N={|ai-1,j,ai,j∈D,i=1,……,m+1,j=0,……,n+1}
基本操作:
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;iprintf（"%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;i5.经验体会:
参考书本的代码进行改进，使用模块化操作易于代码的调试和修改,而且易于阅读.在设计实现过程中虽然遇到了很多问题,但是在解决这些问题的过程中,巩固和加深了我们对已学知识的理解,对团队合作有了一个比较基础的认识,为以后的工作实践打下了基础，同时也增加了我们对这门课的认识.
附录
#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;iprintf（"%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《数据结构与算法》中国电力出版社肖侬
升级会员 