计算机科学与工程系
数据结构课程设计报告
课程设计题目 迷宫 航班信息查询系统 学 号 姓 名 班 级
专 业 网络工程 完 成 时 间 2013-1-4 指 导 教 师
数据结构课程设计
迷宫
题目一
1.设计内容 1.1问题描述
求迷宫从入口到出口的所有路径。 1.2设计要求
1．迷宫中不能使用递归算法查找路径。 2．试探方向限定为上、下、左、右四个方向。 3．迷宫采用随机生成和手工生成两种方式。 4．生成从迷宫入口到出口的最短和最长路径。 5．迷宫的入口和出口由键盘输入。
1.3开发环境
Visual C++6.0的集成化环境 1.4研究思路
对这样的矩形迷宫，可以用N*M的矩阵来描述，N和M分别代表迷宫的行数和列数。这样，迷宫中的每一个位置都可以用行号和列号来指定。从入口到出口的路径则是由一个位置构成的，每个位置上都没有障碍，且每个位置（第一个除外）都是前一个位置的东、南、西或北的邻居。为了描述迷宫中位置（i,j）处有无障碍，规定：当位置（i,j）处有一个障碍时，其值为1，否则为0。
经分析，一个简单的求解方法是：从入口出发，沿某一方向进行探索，若能走通，则继续向前走；否则沿原路返回，换一方向再进行搜索，直到所有可能的通路都探索到为止。即所谓的回溯法。
2.设计步骤
2.1 需求分析
（1）题目：迷宫的生成与路由。生成一个N*M（N行M列）的迷宫，0和
1- 1数据结构课程设计
迷宫
在该程序中，首先进入的是菜单选择，在菜单中有3种选择，选1是手动输入迷宫函数；选2是随机自动生成迷宫；选3是退出程序。在手动生成迷宫时，有两种输出方式，一是矩阵输出，二是图形输出。在矩阵输出时，直接将数组中的数进行输出，在图形输出时，则要判断该点的情况，然后输入迷宫的出入口，再调用mgpath（）函数进行判断是否存在路径，如果存在则将路径经过的点进行输出，并且将经过的点进入到辅助数组中（辅助数组是辅助图形界面的输出），并且将辅助数组初始为1，辅助数组中点为路径的重新赋值为0，然后根据情况输出图形界面。在自动生成迷宫时，用到了c语言随机函数，对于其它问题，和手动情况基本相同。
2.3 详细设计 （1）主菜单伪代码：
while(flag1){
}
{shuru();//输入行列数
printf(\"手动建立迷宫矩阵(0表示可通1表示障碍):\\n\"); for(i=1;i
for(j=1;j
- 3数据结构课程设计
迷宫
和“cla ‘maze’has an illegal zero-sized array”两行错误。双击错误信息，找到出错的程序段，经过查阅资料发现，在利用顺序栈时，没有定义顺序栈的向量空间大小，导致程序出错。但不要对向量空间定义过大，否则会浪费空间。
（2）算法的时空分析：
由于链栈实际上是运算受限制的单链表。所以取栈顶元素运算的算法、置空栈运算的算法执行时间与问题的规模无关，则该算法的时间复杂度为O(1)；而其入栈运算的算法与出栈运算的算法相当于在链表的表尾进行插入和删除操作，不需要移动元素，时间复杂度也为O（1）。建立迷宫矩阵的时间复杂度为O（x*y）。在查找路径的过程中，最坏的情况下可能要考察每一个非障碍的位置。因此，查找路径的时间复杂度应为O（unblocked）。
链栈的入栈算法、出栈算法、取栈顶元素算法、置空栈算法执行时所需要的空间都是用于存储算法本身所用的指令、常数、变量，各个算法的空间性能均较好。只是对于存放顺序栈的向量空间大小的定义很难把握好，如果定义过大，会造成不必要的空间浪费。所以在定义时要慎重考虑。
3.用户使用说明
运行该程序，运行的界面的会出现菜单界面，然后用户可根据界面的提示进行相应的操作，生成迷宫的方式有两种方式，手动生成和自动生成，手动生成时、，用户可根据自己的要求输入迷宫的格式，还需输入相应的入出口，确认程序就会生成相应的路径图形；自动生成只需输入所需的行数和列数，就会生成迷宫，接下来的操作和手动操作相同了。
- 5
图数据结构课程设计
迷宫
图1-2
图1-3 退出
5.总结与心得体会
本次课程设计过程中由于掌握的知识不牢固，在编程序的过程中得到了同学的帮助和指导，在此表示感谢。课程设计的过程中，遇到了一些问题，大部分是课本中的知识掌握的不牢固，还有就是在以前学习C++的过程中相关的知识掌握的不够全面。在以后的学习过程中，自己一定要把各种知识掌握牢固。
- 7
{ }
mg[i][j]=1; //初始化
矩阵,将最外围置为1
printf(\"\\n输入迷宫入口：\\n\"); scanf(\"%d%d\",&x1,&y1); printf(\"输入迷宫出口：\\n\"); scanf(\"%d%d\",&x2,&y2);
}mlink; mlink *stack;//定义一个栈 int m,n,x1,x2,y1,y2;//定义全局变量
}
void showplay(int mg[][M+2])//迷宫输出
{
\\n\");
for(i=1;i
printf(\"\\n\"); for(j=1;j
printf(\"%d \",mg[i][j]);
int i,j;
printf(\"迷宫矩阵如下(0可通)：printf(\"输入行数：\\n\"); scanf(\"%d\",&m); printf(\"输入列数：\\n\"); scanf(\"%d\",&n); 数据结构课程设计
迷宫
} } printf(\"\\n迷宫图形如下(白色for(i=1;i
}
printf(\"\\n\"); for(j=1;j
} if(mg[i][j]==0) printf(\"
if(mg[i][j]==1) printf(\"
if(mg[stack->row][stack->col+1]==
p->next=stack;
stack=p; {
p=(mlink 可通)：\\n\"); 0)//下面位置可通
*)malloc(sizeof(mlink));
p->row=stack->row; p->col=stack->col+1; □\");//为0的输出□ ■\");//为1的输出■
//入栈
mg[stack->row][stack->col]=1;//将
} else
访问过的标记为1 int Mazepath(int mg[][N+2]) {
mlink *p; if(mg[x1][y1]==0){ p=(mlink p->row=x1; p->col=y1; p->next=NULL; stack=p;
//将入口
mg[stack->row][stack->col]=1;/while((!(stack->row==NULL&
if(mg[stack->row][stack->col-1]==0)//上面可通
//入栈
stack=p;
p->next=stack;
{
p=(mlink *)malloc(sizeof(mlink));
*)malloc(sizeof(mlink));
p->row=stack->row; p->col=stack->col-1; 放入堆栈 /标志入口已访问
&stack->col==NULL))&&(!(stack->row==x2&&stack->col==y2)))//循环条件直到找到输入的出口
{
mg[stack->row][stack->col]=1;//将
访问过的标记为1
- 2数据结构课程设计
迷宫
void tonglu()//将坐标的顶点输出 {
始化
printf(\"(%d%3d)\\n\",q->row,q->col);
情况
else printf(\"□\");//0的 } q=stack; {
} for(i=0;i
for(j=0;jrow-1][q->col-1] q=q->next;
=
while (q!=NULL)//循环条件 q=q->next; for(j=0;j
情况
}
void create(int mg[][N+2])//创建和菜单
{
int i,j,x,choice,flag1=1; chushi(); while(flag1){ }
printf(\"\\n\"); printf(\"所有通道为（由下而q=stack; { 上）：\\n\"); while (q!=NULL)//循环条件
printf(\"
##
printf(\"#
\\n\");
*********选择菜单**********
#\\n\");
printf(\"
##
printf(\"输入选项：\"); scanf(\"%d\",&choice); switch(choice){ case 1://手动建立迷宫
{
shuru();
printf(\"手动建立for(i=1;i
\\n\");
printf(\"# 1-手动生成迷
宫
2-自动生成迷宫
3-退出
#\\n\"); 0;//将路径中的点赋给辅助数组a 形的界面输出
迷宫矩阵(0表示可通1表示障碍):\\n\");
for(j=1;j
- 4数据结构课程设计
航班信息查询与检索系统
题目二
1.设计内容 1.1问题描述
设计一个航班信息查询系统，提供信息的管理和使用功能，管理包括更新、添加、删除功能。
1.2设计要求
（1）原始信息存储在文件中，记录不少于50条。 （2）用户界面至少包括以下功能： 创建
修改（插入、添加、删除、更新） 查询 浏览 退出管理系统 （3）航班信息包括：
航班号：字符序列，具体字符表达的意思上网查询 起点站和终点站：字符串 班期：指一周中哪些天有航班
起飞时间：可将时间定义成一个时、分组成的序列 到达时间：可将时间定义成一个时、分组成的序列 机型：字符序列，具体字符表达的意思上网查询 票价：整型数，具体值可上网查询
（4）创建是指从文件中读取数据，并存入所定义的顺序表中。
（5）可按航班号、起点站、终点站、起飞时间、到达时间等进行查询。查询时要用到顺序查找、二分查找方法。输出查询结果时必须排序。
（6）可按航班号、起点站、起飞时间、票价进行删除和更新操作，删除的记录存入另外的文件中，作为日志文件保存。
（7）作插入操作前，先对信息按起点站进行排序。新记录插入为起点站相同的最后一条记录。
- 2数据结构课程设计
航班信息查询与检索系统
typedef struct node { Time rh; Time lv; }Pnode; （2）飞机结构体： struct Plane {
}; （3）静态链表： typedef struct Sqlist { int length; struct Plane *plane; char key[10],sted[20],sche[10]; Time rh,lv; int price; }Sqlist; 2.3 详细设计 （1）主函数：
do{printf(\"* * * * * * * * * * * * * 航班查询系统* * * * * * * * * * * * *\\n\");
printf(\"*
1.创建
2.修改
3.查询
4.浏览
5.表长
6.文件
0.退出
*\\n\");
printf(\"* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *\\n\");
scanf(\"%d\",&opt); switch(opt) {
case 1:Initlist(L);break;
case 2:handle(L);break;
case 3:search(L);break;
case 4:print(L);break; case 5:Get_Sq(L);break; case 6:File(L);break;
- 4数据结构课程设计
航班信息查询与检索系统
} }while(opt!=0); }
（4）文件操作： void File(Sqlist &L) {
int ch; do{ printf(\"* * * * * * * * * * * * * * * * * * * * * * * * *\\n\");
printf(\"*
*\\n\");
printf(\"* 1.保存信息到文件
2.从文件读取信息
0 退出 *\\n\");
printf(\"*
*\\n\");
printf(\"* * * * * * * * * * * * * * * * * * * * * * * * *\\n\");
printf(\"请输入选项\\n\");
scanf(\"%d\",&ch);
switch(ch)
{
case 1:SaveList(L);break;
} }while(ch!=0); case 2:ReadList(L);break;
case 0:printf(\"退出！\\n\");break; }
（5）浏览信息：就是循环使用输出函数，在此就不必多说了
2.4 调试分析
（1）在课设过程中，遇到问题时，通过与同学、老师交流，在图书馆查阅资料，使问题得以解决。
（2）算法中有许多不是很优化的地方。 3.用户使用说明
程序运行后用户根据提示输入要进行的操作选项（应先选择创建选项，这样可以直接读取保存好的文件），然后选择要进行的操作选项。由于主菜单中有修改、查询和浏览项目，每个项目又有各自的子菜单，所以在进行管理和使用时要注意输入的元素是否正确，需按照提示输入。输入操作元素时，元素之间以空格隔开。程序将按输入的操作元素找到相应的算法，然后进行处理，然后将结果打
- 6数据结构课程设计
航班信息查询与检索系统
图2-2 查询信息
图2-3插入
图2-4删除
- 8数据结构课程设计
航班信息查询与检索系统
时就需要重新写出一个子函数，哪怕这个子函数就是在原有的一个子函数的基础上改那么一丁点的地方，例如航班信息查询系统中的查询函数，其实每个子函数只是改了一下关键码而已。
6.附录
#include #include #include typedef struct time { int hour; int min;
{ }
void search_key(Sqlist L)//按航班号查找
{ 号：\");
Time rh; Time lv;
scanf(\"%s\",n); int i;
printf(\"此航班的航班号，起点char n[20];
printf(\"请输入要查找的航班
printf(\"%d\\n\",L.length);//表长
}Time; typedef struct node {
}Pnode; struct Plane {
}; typedef struct Sqlist { int length; struct Plane *plane; char key[10],sted[20],sche[10]; Time rh,lv; int price;
终点，班期，起飞时间，到达时间，票价：\\n\");
if(strcmp(L.plane[i].key,n)==0)
ted,
L.plane[i].sche,L.plane[i].lv.hour,L.
{
for(i=L.length-1;i>=0;i--) {
printf(\"%s %s %s %d:%d %
d:%d %d\\n\",L.plane[i].key,L.plane[i].s}Sqlist; int get_Sq(Sqlist &L) { } void Get_Sq(Sqlist &L) return L.length;
plane[i].lv.min,L.plane
[i].rh.hour,L.plane[i].rh.min,L.plane
[i].price);
- 10数据结构课程设计
航班信息查询与检索系统
printf(\"此航班的航班号，起点
ted,
{ 终点，班期，起飞时间，到达时间，票价：\\n\");
if(L.plane[i].lv.hour
ted,
L.plane[i].sche,L.plane[i].lv.hour,L.
{
for(i=L.length-1;i>=0;i--) {
printf(\"%s %s %s %d:%d %
d:%d %d\\n\",L.plane[i].key,L.plane[i].s
L.plane[i].sche,L.plane[i].lv.hour,L.
plane[i].lv.min,L.plane
[i].rh.hour,L.plane[i].rh.min,L.plane
}
void search(Sqlist L) {
int i; do {
printf(\"* * * * * * * * * * * }
} printf(\"%s %s %s %d:%d %d:%d %d\\n\",L.plane[i].key,L.plane[i].s[i].price); plane[i].lv.min,L.plane [i].rh.hour,L.plane[i].rh.min,L.plane
} void search_rh(Sqlist L) {
int hour; printf(\"请输入你所要求的最scanf(\"%d\",&hour); printf(\"此航班的航班号，起点 } } [i].price);
* * * * * * * * * * * * * ** * * * * * * * * * * * * * * *\\n\");
printf(\"* 1.航班号查询
2.起点终点查询
3.班期查询 4.起飞时间查询
5.到达时间查询
0.退出
*\\n\");
printf(\"* * * * * * * * * *
* * * * * * * * * * * * * * ** * * * * * * * * * * * * * * *\\n\");
scanf(\"%d\",&i);
switch(i)
{
case 晚时间：\"); 终点，班期，起飞时间，到达时间，票价：\\n\");
if(L.plane[i].rh.hour=0;i--) {
1:search_key(L);break;
- 12数据结构课程设计
航班信息查询与检索系统
\\n\");
} else { } printf(\"查找不成功。
i--; if(i==0)
{
char c[20];
printf(\"输入修改后的scanf(\"%s\",c);
内容：\");
strcpy(L.plane[i].sche,c);
printf(\"修改成功！\\n\"); }break; {
int a,b;
printf(\"输入修改后的int opt; printf(\"选择修改对象：\"); scanf(\"%d\",&opt); switch(opt) { case 1:
printf(\"修改成功！\\n\"); printf(\"修改成功！\\n\"); {
char a[10]; printf(\"输入修改后的scanf(\"%s\",a);
case 4:
内容：\");
char b[20]; printf(\"请输入修改后scanf(\"%s\",b);
scanf(\"%d:%d\",&a,&b);
L.plane[i].lv.hour=a; L.plane[i].lv.min=b; printf(\"修改成功！\\n\"); 航班号：\");
}break; {
int a,b;
printf(\"输入修改后的strcpy(L.plane[i].key,a); }break; {
case 5: case 2:
内容：\");
scanf(\"%d:%d\",&a,&b);
L.plane[i].rh.hour=a; L.plane[i].rh.min=b; printf(\"修改成功！\\n\"); 的内容：\"); strcpy(L.plane[i].sted,b); }break;
}break; {
int a;
case 6: case 3:
- 14数据结构课程设计
航班信息查询与检索系统
*\\n\");
printf(\"* * * * * * * * * * * * * * * * * * * * * * * * *\\n\");
printf(\"请输入选项\\n\");
scanf(\"%d\",&ch);
switch(ch)
{
case 1:SaveList(L);break; case 2:ReadList(L);break;
L.plane[i].sche,&L.plane[i].lv.hour,
&L.plane[i].lv.min,&L.plane
[i].rh.hour,&L.plane[i].rh.min,&L.pl
}
void delet_Sq1(Sqlist &L) {
char n[10]; int i,j;
printf(\"请输入您要删除的航scanf(\"%s\",n); if(L.length==0) {
printf(\"没有选项！\\n\"); for(i=0;i
L.length++;
ane[i].price);
case 0:printf(\"退出！\\n\");break;
}
void Initlist(Sqlist &L)//插入存储 {
\");
容：\"); 价\\n\");
scanf(\"%s%s%s%d:%d%d:%d%d\",
L.plane[i].key,L.plane[i].sted, for(i=0;i
班期
起飞时间
到达时间
票scanf(\"%d\",&n); L.length=0; L.plane=(Plane if(!L.plane) exit(0); printf(\"请输入顺序表中的内
int i,n; printf(\"输入表中航班的数量：
} }while(ch!=0);
班号：\");
if(strcmp(L.plane[i].key,n)==0)
{
printf(\"所删除的班机*)malloc((n+10000)*sizeof(Plane));
的信息：\\n\");
printf(\"\\n航班号
起点终点
printf(\"%s %s %s %d:%d %d:%
d %d\\n\",L.plane[i].key,L.plane[i].sted,
L.plane[i].sche,L.plane[i].lv.hour,L.
plane[i].lv.min,L.plane
[i].rh.hour,L.plane[i].rh.min,L.plane
[i].price);
- 16数据结构课程设计
航班信息查询与检索系统
\\n\"); } printf(\"无法打开文件！ }
}while(opt!=0);
void insert_Sq(Sqlist &L) { 数量
价\\n\");
for(i=0;i
printf(\"* * * * * * * * * * *
scanf(\"%s%s%s%d:%d%d:%d%d\",&L.plane[L.length].key,&L.plane[L.length].sted,
&L.plane[L.length].sche,&L.plane[
{
int a=get_Sq(L);
printf(\"请输入要添加班机的scanf(\"%d\",&n);
printf(\"请输入要添加的班机printf(\"\\n航班号
起点终点
int i,n;
//n表示添加的fprintf(fp,\"航班号：%s\\n起点站：%s
终点站：%s\\n班期：%d\\n起飞时间：%d:%d
到达时间：%d:%d\\n价格：%d\\n\\n\", p.key,p.sted,p.sche,p.lv.hour,p.lv.mi
\\n\"); } void delet_Sq(Sqlist &L) {
int opt; do { fclose(fp); printf(\"保存删除的信息成功。n,p.rh.hour,p.rh.min,p.price);
数量：\");
信息：\\n\");
班期
起飞时间
到达时间
票* * * * * * * * * *\\n\");
printf(\"* 1.航班号删除
printf(\"* * * * * * * * * * printf(\"输入你的选择：\"); 2.路线删除
0.退出
*\\n\"); * * * * * * * * * * *\\n\");
scanf(\"%d\",&opt);
switch(opt) {
case 1:delet_Sq1(L);break;
case 2:delet_Sq2(L);break;
case 0:printf(\"退出。 }
L.length].lv.hour,&L.plane[L.length].lv.min,
&L.plane[L.length].rh.hour,&L.plan
e[L.length].rh.min,&L.plane[L.length].price);
}
void handle(Sqlist &L) {
}
L.length++;
\\n\");break;
- 18
