迷宫课程设计报告

迷宫课程设计报告本文简介：西安郵電大學数据结构课程设计报告题目：迷宫问题院系名称：计算机学院专业名称：软件工程班级：1101学生姓名：武妍娜学号（8位）：04113027指导教师：李培设计起止时间：2012年12月3日~2012年12月14日一.设计目的1.熟悉C语言程序的编辑、编译链接和运行的过程，能够熟练地编辑、编译及调

迷宫课程设计报告本文内容：

西安郵電大學

数据结构课程设计报告

题

目：

迷宫问题

院系名称：

计算机学院

专业名称：

软件工程

班

级：

1101

学生姓名：

武妍娜

学号（8位）：

04113027

指导教师：

李培

设计起止时间：2012年12月3日~2012年12月14日

一.

设计目的

1.熟悉C语言程序的编辑、编译链接和运行的过程，能够熟练地编辑、编译及调试程序。

2.掌握文件和文件指针的概念以及文件的定义方法，学会熟练使用文件打开、关闭、读、写

等基本操作。

3.熟练掌握结构体、链表、指针的使用，及函数间的调用。

4.能够熟练运用所学栈的相关知识及操作，顺利完成题目的要求。

二.

设计内容

迷宫是实验心理学中一个古典问题。用计算机解迷宫路径的程序，就是仿照人走迷宫。计算机解迷宫时，通常用的是“穷举求解“的方法，即从入口出发，顺某一方向向前探索，若能走通，则继续往前走；否则沿原路退回，换一个方向再继续探索，直至所有可能的通路都探索到为止。

1.功能与数据需求

迷宫求解问题描述：

以一个M×N的矩阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。

1.1

题目要求的功能

（1）基本要求：

首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以二元组（i,j）的形式输出，其中：（i,j）指迷宫中对应的坐标。

（2）测试数据：

?左上角（1,1）为入口，右下角（9,8）为出口。

?左上角（1,1）为入口，右上角（1,8）为出口。

（3）

如下图所示：

1.2

扩展功能

（1）编写非递归形式的算法，求得迷宫中所有可能的通路；

（2）以方阵形式输出迷宫及其通路

2.界面需求

（1）在菜单中选择要执行的操作

（2）输出方阵迷宫

（3）用户自己输入迷宫起始位置

（4）输出所走的迷宫路径

（5）输出方阵路径，并保存到文件中

3.开发环境与运行需求

Microsoft

Visual

C++6.0

Ubuntu

三．概要设计

主模块

1．功能模块图；

本程序包含三个模块

（1）主程序模块：

void

main（）

｛

文件模块

栈模块

迷宫模块

初始化；

do｛

接受命令；

处理命令；

｝while（命令！=“退出”）；

｝

（2）栈模块——实现栈抽象数据类型

（3）

迷宫模块——实现迷宫抽象数据类型

2．

各个模块详细的功能描述。

（1）菜单：从菜单中选择要执行的操作

（2）文件模块：实现文件的各项基本操作

a）打开文件b）关闭文件

c）从文件读信息d）向文件中写入内容

（3）栈模块：实现栈的各项基本操作

a）初始化栈b）入栈

c）出栈d）取栈顶元素

(4）迷宫模块：求解迷宫问题

a）显示迷宫b)获取迷宫路径

c）判断当前路径是否走过d）获得下一个可走的位置

e）获得东面，南面，西面，北面相邻的位置

4．

详细设计

1．功能函数的调用关系图

打开源文件

输出迷宫路径

判断当前路径是否走过

显示迷宫

主函数

入栈

出栈

获得迷宫路径

初始化栈

菜

单

获得下一个可走的位置

显示迷宫路线

保存迷宫路线

取栈顶元素

开始

2.各功能函数的数据流程图

MStackElem

start,cur;

p2=head;

（1）

获得迷宫路径函数

cur=

start;

do

while

(cur.x

!=

chukou[0]

||

cur.y

!=

chukou[1])

当前位置是否走过

Push(

cur

=

GetNext(cur);

cur=GetNext(cur);

是

否

else

if

cur.val==-1

Push(

return

1;

if

cur.x==chukou[0]

cur=GetTop(

next.x=next.y=next.val

=

-1;

if

else

if

GetNorth(cur).val==

next=

North(cur);

next=

GetEast(cur);

next=

GetEast(cur);

3.重点设计及编码

获得迷宫路径的函数：

int

GetMazePath()

{

MStackElem

start,cur;

start.x

=

rukou[0];

start.y

=

rukou[1];

start.val

=

Maze[rukou[0]][rukou[1]];

cur

=

start;

do

{

if

(UnPass(path,cur))

{

Push(

Push(

cur

=

GetNext(cur);

if

(cur.x

==

chukou[0]

Push(

return

1;

}

else

if(cur.val

==

-1)

{

Pop(

cur

=

GetTop(

}

}

else

{

cur

=

GetNext(cur);

if

(cur.val

==

-1)

{

Pop(

cur

=

GetTop(

}

}

}

while

(cur.x

!=

chukou[0]

||

cur.y

!=

chukou[1]);

return

0;

}

五．测试数据及运行结果

1．正常测试数据和运行结果

2.异常测试数据及运行结果

六．调试情况，设计技巧及体会

1．改进方案

在迷宫问题中，由于走的方向顺序不同，存在着多条路径的结果。因此就出现了一个最大的问题，哪条路径最短，即求最短路径。

由于时间有限和难度问题，我没能及时解决这个问题，这也是在这次的迷宫课程设计中，我唯一的不足之处。不过我并没有放弃，课程设计结束后，我还会继续努力，解决掉这个问题。在以后的生活中，我也会不断督促自己，提高编程能力。

2．体会

刚开始，头脑里没有任何思路，不知道如何下手，经过仔细研读课本和上网查资料后，终于有了思绪。先将整个程序划分为三个大模块：主模块，栈模块和迷宫模块。然后再依次实现每个大模块中的小操作。最后将所有的程序拼接起来，进行调试。

我觉得所有模块中最难编的就是查找迷宫路径函数，经过苦思冥想，再加上老师和同学的帮助，总算做出来了，但是非常复杂。在编译的过程中总会出现五花八门的错误，比如：从文件里读不出信息，又或者是存不进去文件，或者是乱码等。后来才发现原来是源文件中存的信息类型和程序中定义的类型不匹配，经过改正之后果然正确了。改正完后，当把所有的小块连接在一起时，虽然没有错误，但是总有许多警告语句，运行的结果也不尽人意。通过上网查资料后，发现这都是一些格式问题。看来编程格式很重要啊！经过两个星期的上机实践学习，我才发现我的C语言上机实践能力还有待加强，有待进步。以后不但要重视课本与习题，更要重视上机实践。

七．参考文献

1.

耿国华主编，《数据结构——C语言描述》，高等教育出版社，2005年

2.

陈锐，《数据结构（C语言版）》，清华大学出版社

2012年

八．附录

#include

#include

#include

#define

M

11//迷宫行数

#define

N

10//迷宫列数

#define

STACK_INIT_SIZE

100

#define

STACKINCREMENT

10

char

Maze[M][N]={0};//迷宫

char

s[M][N]={0};//迷宫路线图

int

rukou[2],chukou[2];

//定义栈元素类型

typedef

struct

{

int

x;//x坐标

int

y;//y坐标

char

val;//Maze[x][y]的值

}MStackElem;

//定义栈

typedef

struct

{

MStackElem

base;

MStackElem

top;

int

StackSize;

}MStack;

//初始化栈

InitStack(MStackS)

{

S->base

=

(MStackElem)malloc(STACK_INIT_SIZE

sizeof(MStackElem));

if

(!S->base)

{

printf(“初始化栈失败!\n“);

exit(-1);//存储分配失败

}

S->top

=

S->base;

S->StackSize

=

STACK_INIT_SIZE;

}

//入栈

Push(MStackS,MStackElem

e)

{

//向栈中添加元素前先判断栈是否还有空间容纳新元素

if

(S->top

-

S->base

>=

S->StackSize)//栈满,追加元素

{

S->base

=

(MStackElem)realloc(S->base,(STACK_INIT_SIZE+STACKINCREMENT)

sizeof(MStackElem));

if

(!S->base)

{

printf(“空间不足，入栈失败!\n“);

exit(-1);//存储分配失败

}

S->top

=

S->base

+

S->StackSize;

//因为是重新分配了空间,所以base的值其实已经改变,所以top的值也就相应的改变,才能指向新的迷宫栈

S->StackSize

+=

STACKINCREMENT;

}(S->top++)

=

e;//将新元素加到栈顶

}

//获得栈顶元素

MStackElem

GetTop(MStackS)

{

if

(S->top

==

S->base)

{

printf(“\n对不起，没有出路!\n\n“);

exit(0);

}

else

return(S->top

-

1);

}

//出栈

Pop(MStackS)

{

//若栈不为空,则删除s的栈顶元素

if

(S->top

==

S->base)

{

printf(“栈为空，出栈失败!\n“);

exit(0);

}

else

--(S->top);

}

MStack

realPath,path;//构造两个栈,一个用来保存探索中的全部路径,一个用来保存有效路径

//判断当前位置是否走过

int

UnPass(MStack

path,MStackElem

cur)//这里不能传path的地址,否则在遍历过程中它的top值就被改了

{

int

flag

=

1;//未走过

while(path.top

!=

path.base)

{

MStackElem

e

=(path.top

-

1);

if

(e.x

==

cur.x//曾走过

(path.top)--;//每循环一次令头指针下移一个位置

}

return

flag;

}

//获得东面(即右边)相邻的位置

MStackElem

GetEast(MStackElem

cur)

{

if(cur.y

!=

N-2)//当y==N-2时已到了迷宫右边界,不能再向东(右)行了

{

cur.y

+=

1;

cur.val

=

Maze[cur.x][cur.y];

}

return

cur;//当y==N-2时返回的是它本身

}

//获得南面(即下边)相邻的位置

MStackElem

GetSouth(MStackElem

cur)

{

if(cur.x

!=

M-2)//当x==M-2时已到了迷宫下边界,不能再向南(下)行了

{

cur.x

+=

1;

cur.val

=

Maze[cur.x][cur.y];

}

return

cur;//当x==M-2时返回的是它本身

}

//获得西面(即左边)相邻的位置

MStackElem

GetWest(MStackElem

cur)

{

if(cur.y

!=

1)//当y==1时已到了迷宫左边界,不能再向西(左)行了

{

cur.y

-=

1;

cur.val

=

Maze[cur.x][cur.y];

}

return

cur;//当y==1时返回的是它本身

}

//获得北面(即上边)相邻的位置

MStackElem

GetNorth(MStackElem

cur)

{

if(cur.x

!=

1)//当cur.x==1时表示在迷宫的上边界,不能再向北(上)行了

{

cur.x

-=

1;

cur.val

=

Maze[cur.x][cur.y];

}

return

cur;//当cur.x==1时返回的还是它本身

}

//获得下一个可通行的位置,按东南西北(即顺时针)的方向试探

MStackElem

GetNext(MStackElem

cur)

{

MStackElem

next;

next.x

=

next.y=next.val

=

-1;

if(GetEast(cur).val

==

else

if(GetSouth(cur).val

==

else

if(GetWest(cur).val

==

else

if(GetNorth(cur).val

==

return

next;//如果当前位置的四面或为墙或已走过,则返回的next的val值为-1

}

//获得迷宫路径的函数

int

GetMazePath()

{

MStackElem

start,cur;

start.x

=

rukou[0];

start.y

=

rukou[1];

start.val

=

Maze[rukou[0]][rukou[1]];//入口坐标的值

cur

=

start;

//设定当前位置为“入口位置“do

{

if

(UnPass(path,cur))//如果当前位置未曾走到过

{

Push(

Push(

cur

=

GetNext(cur);

if

(cur.x

==

chukou[0]

//把出口结点放入路径中

Push(

return

1;

}

else

if(cur.val

==

-1)//当前位置的四面都为墙

{

Pop(//删除真实路径的栈顶元素

cur

=

GetTop(//令cur指向栈顶元素

}

}

else//如果当前位置已经走过,说明原来测试的方向不对,现在尝试其它方向

{

cur

=

GetNext(cur);

if

(cur.val

==

-1)

{

Pop(//仍不通,删除真实路径的栈顶元素

cur

=

GetTop(//令cur指向栈顶元素

}

}

}

while

(cur.x

!=

chukou[0]

||

cur.y

!=

chukou[1]);

return

0;

}

//输出迷宫路径

PrintMazePath(MStackS)//为了安全,这里不传MStack的地址,以防在遍历的过程中把它们的top或base的值也修改了

{

MStackElem

e;

int

i,j;

for(i=0;ibase

top-1))

{

e

=(S->base);//先指向栈底元素,以后依次向上增1

s[e.x][e.y]=

.

;

printf(“(%d,%d)

----->

“,e.x,e.y);

(S->base)++;

}

//最后一个结点没有后继,所以不再输出“------>“e

=(S->base);

s[e.x][e.y]=

.

;

printf(“(%d,%d)“,e.x,e.y);

}

//打开文件，获取迷宫

OpenFile()

{

FILEfp;

int

i,j,c;

system(“cls“);

if((fp=fopen(“in.txt“,“rt“))==NULL)//打开迷宫文件in.txt

{

printf(“打开文件失败！\n“);

exit(1);

}

for(i=0;i

代表入口，

;//入口标志

s[chukou[0]][chukou[1]]=

=M-2||rukou[1]>N-2||chukou[0]>M-2||chukou[1]>N-2||rukou[0]<0||rukou[1]<0||chukou[0]<0||chukou[1]<0)

printf(“输入的入口或出口坐标错误!\n“);//判断输入坐标是否正确

else

{

InitStack(

InitStack(

GetMazePath();

printf(“\n迷宫路径为:\n\n“);

PrintMazePath(

getchar();

}

printf(“\n\n“);

system(“pause“);

system(“cls“);

break;

case

3:

system(“cls“);

Print2();//显示迷宫路线图

printf(“\n“);

SaveFile();//保存迷宫路线图

break;

case

0://退出

system(“cls“);

printf(“\n谢谢您的使用,再见!\n\n“);

Flower();

break;

default:

system(“cls“);

printf(“\n抱歉，您输入错误!\n请重新输入哦!\n\n“);

system(“pause“);

}

}while(choice);

}