迷宫(C语言版)--数据结构课程设计

1、一 迷宫问题求解1. 问题描述迷宫问题是实验心理学的一个经典问题，心理学家把一只老鼠从一个无顶盖的大盒子的入口出赶迷宫。迷宫中设置了很多隔壁，对前进方向形成了多出障碍，心理学家在迷宫的唯一出口处放置了一块奶酪，吸引老鼠在迷宫中寻找路径以到达出口。然而，用计机模拟迷宫问题，即划好迷宫的隔壁的设置，让计算机从入口处进入迷宫探究出一条通路。2. 设计思路回溯法是一种不断试探且及时纠正错误的探索方法。下面的求解过程既是使用回溯法。从入口出发，按某一个方向向前探索，若能走通并且未走过，即某处可以到达，则到达新点，否则试探下一个方向；若所有的方向均没有通路，则沿原路返回前一个点，换下一个方向继续探索，直到

2、找到一条通路，或无路可走又返回到入口点。在求解过程中，为了保证在到达某一点后不能向前继续行走（无路）时，能正确返回前一个点以便继续从下一个方向向前试探，则需要用一个栈保存所有到达点的下标。另外，求解该问题的一个重要问题是如何防止回溯时走重复节点，以避免发生死循环。这里，我们采用对走过的结点，修改其结点信息。如在设计之初，我们设置保存迷宫结构的二维数组中0值代表该节点可走，1值代表其不可走，那么我们可以把走过的结点值改为非0，已使其不能被再次探索。3数据结构设计由上面的设计思路知，若想正确的使用回溯法求解迷宫问题，必须要借助一个栈以保存走过的结点信息。而这里我活用了栈，只把其数据结构抽象为了一个

3、结构体数组，具体设计如下：typedef struct int x,y;/*记录迷宫结点的位置信息*/pos;pos Pos100; /*结构体数组以保存走过的结点信息*/4功能函数介绍（1）判断是否找到出口函数Isover（）；该函数的参数是当前结点的x、y坐标与出口结点的x、y坐标，通过比较其值来判断是否找到出口结点，从而控制程序结束。（2）对程序相关信息的简单介绍函数introduce()；该函数主要是在进行绘制迷宫的图形化界面之前开发者搞的一点小插曲，以介绍跟该程序的相关的部分信息。（3）用回溯法探究迷宫出口函数mazepath（）；该函数即是利用回溯法探究迷宫问题。函数从接受的起点出

4、发，逐个向其可走方向进行探究，并同时把其所走过的结点的结点信息值改为迷宫现有探索结点中为有效的个数，以避免走重复结点。同时该函数在探索一条有入口到出口的路径的同时，加入了一些图像处理函数，把迷宫的探索的过程动态的显示出来，个人对迷宫探索的思路已较为直观的感觉。(4) 主函数main()该函数中处理了图形设备的初始化及迷宫结构的初始化工作，同时在调用上述功能函数完成迷宫探索路径问题的同时，加入了探索完成后的一些图形界面的显示内容。5.编码实现#include#include#include#include#include#include#define MaxSize 8#define Start

5、Px 170#define StartPy 150typedef struct int x,y;pos;pos Pos100;int Isover(int s_x,int s_y,int e_x,int e_y) /*判断是否找到出口*/ if(s_x=e_x&s_y=e_y) return 1; else return 0;void mazepath(int m_mazeArrayMaxSize,int s_x,int s_y,int e_x,int e_y) int count=0,sum=0; int str80; m_mazeArrays_ys_x=-1; Poscount.x=s_x

6、; Poscount.y=s_y; while(!Isover(s_x,s_y,e_x,e_y) if(m_mazeArrays_ys_x+1=0) sum+; m_mazeArrays_y+s_x=+count; setcolor(GREEN); circle(s_x*30+StartPx+15,s_y*30+StartPy+15,10); setfillstyle(1,YELLOW); floodfill(s_x*30+StartPx+15,s_y*30+StartPy+15,GREEN); sleep(1); Poscount.x=s_x; Poscount.y=s_y; else if

7、(m_mazeArrays_y-1s_x=0) sum+; m_mazeArray-s_ys_x=+count; setcolor(GREEN); circle(s_x*30+StartPx+15,s_y*30+StartPy+15,10); setfillstyle(1,YELLOW); floodfill(s_x*30+StartPx+15,s_y*30+StartPy+15,GREEN); sleep(1); Poscount.x=s_x; Poscount.y=s_y; else if(m_mazeArrays_ys_x-1=0) sum+; m_mazeArrays_y-s_x=+c

8、ount; setcolor(GREEN); circle(s_x*30+StartPx+15,s_y*30+StartPy+15,10); setfillstyle(1,YELLOW); floodfill(s_x*30+StartPx+15,s_y*30+StartPy+15,GREEN); sleep(1); Poscount.x=s_x; Poscount.y=s_y; else if(m_mazeArrays_y+1s_x=0) sum+; m_mazeArray+s_ys_x=+count; setcolor(GREEN); circle(s_x*30+StartPx+15,s_y

9、*30+StartPy+15,10); setfillstyle(1,YELLOW); floodfill(s_x*30+StartPx+15,s_y*30+StartPy+15,GREEN); sleep(1); Poscount.x=s_x; Poscount.y=s_y; else m_mazeArrays_ys_x=-1; sum+; count-; setcolor(BLUE); rectangle(s_x*30+StartPx,s_y*30+StartPy,s_x*30+StartPx+30,s_y*30+StartPy+30); setfillstyle(1,GREEN); fl

10、oodfill(s_x*30+StartPx+10,s_y*30+StartPy+10,BLUE); sleep(1); if(count=-1) sum-; break; s_x=Poscount.x; s_y=Poscount.y; if(count!=-1) settextstyle(1,0,1); outtextxy(170,400,you win!n); sprintf(str,It walk %d steps totally!n,count); outtextxy(180,430,str); else settextstyle(1,0,1); outtextxy(170,400,T

11、here is no way for it to reach the end!nn); int main() int gdriver, gmode; int x,y; int m_mazeMaxSizeMaxSize; int triangle8; char str2; detectgraph(&gdriver, &gmode); /*自动测试硬件*/ initgraph(&gdriver, &gmode, c:Win-Tcprojects); setbkcolor(BLACK); setcolor(RED); settextstyle(0,0,3); outtextxy(160,50,Pro

12、blem:Maze); srand( time( NULL ) ); setcolor(WHITE); for( x = 0; x MaxSize; x+ ) m_maze0x = 1; m_mazeMaxSize-1x = 1; for( x = 0; x MaxSize; x+ ) m_mazex0 = 1; m_mazexMaxSize-1 = 1; for ( y = 1; y MaxSize-1; y+ ) for ( x = 1; x 1 ? 1 : 0 ); /*为数组随机附值*/ m_maze11=0; m_mazeMaxSize-2MaxSize-2=0; /*指定迷宫出口*

13、/ for ( y = 0; y MaxSize; y+ ) for ( x = 0; x MaxSize; x+ ) if(m_mazeyx=1) rectangle(x*30+StartPx,y*30+StartPy,x*30+StartPx+30,y*30+StartPy+30); line(x*30+StartPx,y*30+StartPy,x*30+StartPx+30,y*30+StartPy+30); line(x*30+StartPx+30,y*30+StartPy,x*30+StartPx,y*30+StartPy+30); sleep(1); x=y=1; setcolor

14、(GREEN); circle(x*30+StartPx+15,y*30+StartPy+15,10); setfillstyle(1,YELLOW); floodfill(x*30+StartPx+15,y*30+StartPy+15,GREEN); sleep(1); line(x*30+StartPx+15,y*30+StartPy,x*30+StartPx+15,y*30+StartPy-50); line(x*30+StartPx+15,y*30+StartPy-50,x*30+StartPx+5,y*30+StartPy-40); line(x*30+StartPx+15,y*30

15、+StartPy-50,x*30+StartPx+25,y*30+StartPy-40); settextstyle(1,0,0); outtextxy(x*30+StartPx,y*30+StartPy-50,StartPoint); x=y=MaxSize-2; setcolor(RED); triangle0=x*30+StartPx+10; triangle1=y*30+StartPy; triangle2=x*30+StartPx+20; triangle3=y*30+StartPy+10; triangle4=x*30+StartPx+10; triangle5=y*30+Star

16、tPy+20; triangle6=x*30+StartPx+10; triangle7=y*30+StartPy; drawpoly(4,triangle); setfillstyle(1,RED); floodfill(x*30+StartPx+15,y*30+StartPy+6,RED); /*line(x*30+StartPx+10,y*30+StartPy,x*30+StartPx+20,y*30+StartPy+10); line(x*30+StartPx+20,y*30+StartPy+10,x*30+StartPx+10,y*30+StartPy+20);*/ line(x*3

17、0+StartPx+10,y*30+StartPy+20,x*30+StartPx+10,y*30+StartPy+30); sleep(1); line(x*30+StartPx+30,y*30+StartPy+15,x*30+StartPx+30+50,y*30+StartPy+15); line(x*30+StartPx+30+50,y*30+StartPy+15,x*30+StartPx+30+50-10,y*30+StartPy+15-10); line(x*30+StartPx+30+50,y*30+StartPy+15,x*30+StartPx+30+50-10,y*30+StartPy+15+10); settextstyle(1,1,0); outtextxy(x*30+StartPx+30+50,y*30+StartPy,EndPoint); mazepath(m_maze,1,1,MaxSize-2,MaxSize-2); getch(); closegraph(); return 0;6.测试与运行截图程序中对迷宫的结构以及其起点、终点都已经指定，故程序运行开始后，不需要用户进行相关操作，只需要观看迷宫的探索过程即可。探索过程会有图像显示，给人关于探索问题的直观反映。程序运行的部分截图如下：7.问题分析与总