栈的应用——迷宫求解

1、一、 栈的来源与定义：线性表：有序的有限集合，集合元素依据具体问题而定。例子：A=13,45,12 B=小明 87,小王 90等，这只是数学层次上的描述，如何在计算机层次上描述？有两种：以上述为例数组：链表：当然，在实际运用中，一般很难估计到具体问题的规模，即不清楚集合中的元素个数上限是多少，所以都是用动态存储分配进行实现的。相应的有些基本操作：插入元素，删除元素，合并线性表，拆分线性表，查找元素，修改元素等，根据元素的性质还可以得到一下额外操作。如：数值型元素可以有排序这个操作。在进行插入和删除时，对任意位置元素都能进行。人们实践中发现许多问题在进行上述两项操作时都限制在末尾。由此提出栈的概

2、念，特定是“后进先出”；若将删除限制在开头，则称为队列，特定是“先进先出”。根据栈的特点，在数学层次上描述时，换一种更能符合其特点的表示，如下：134512headtail将其用“叠罗汉”的形式表示出来，每次进行插入或删除时，都在最上面进行，最上面称为栈顶，最下面称为栈底，head指向第一个元素，tail指向栈顶的下一个元素。进行插入时，改变*tail的值，tail+；进行删除时，tail-；可以看出当tail与head相等时，便是空集，或称为空栈。当然也可以用一个变量来记录栈的元素个数，简称栈长。二、 栈的应用方形迷宫求解起点终点如上图，如何运用计算机对其进行求解呢？1. 算法思路：计算机求

3、解迷宫时，通常用的都是“穷举法”，即每种走法都尝试一遍，若走到终点，则输出，否则，输出迷宫无解。步骤如下：记录begin所在的方块坐标，当前方块设为begin所在的方块（一）寻找方向第一步：搜索当前方块东南西北哪些方向可以走，为了方便描述，用数组direction4表示四个方向，分别代表东南西北，值为1，表示可以走，值为0，表示不能走。 第二步：在搜寻路径时，不能走已经记录过的方块坐标，免得在原地转圈。因此，在能走的方向中，判断是否有已经记录过的方块坐标，有则置相应的方向为0（二）选择方向 让当前方块从东边开始顺时针搜寻可以走的方向（可以从别的方向开始，还可以不用顺时针，只要数组directi

4、on各个下标对应的方向不重复即可），即找到direction数组中，第一个为1的下标，0,1,2,3分别代表可以往东南西北走；若为其他值，表示当前方块四处都无路可走。 if 有路可走 记录此方向的方块坐标，当前方块设为刚刚记录的方块，若为end，则跳出循环，否则转到（一）继续循环else删除最后一次记录的方块坐标if 记录空了迷宫无解，跳出循环else当前方块设为倒数第二次记录的方块，并将此方块通往刚刚删除的方块的方向上设为0，转到（二）2. 数据描述：i. 描述迷宫：可将迷宫看成矩阵，用二维数组进行描述即可，为0，表示墙壁；为1，表示通路，则上图可用以下矩阵表示ii. 描述记录：从算法的思路

5、中可以看出，记录可用栈来描述，包含着求解结果，若记录为空，则迷宫无解；否则，迷宫有解，输出路径。3. 举例说明：beginend用上述迷宫，描述依次算法下，栈的变化：第一次循环：00东南西北1100有路可走，往东走。第二次循环：01东南西北000000东南西北1100不为终点，无路可走，退回去，封锁东边，往南走。第三次循环：10东南西北010000东南西北0100不为终点，有路可走，往南走。第四次循环：20东南西北110010东南西北010000东南西北0100不为终点，有路可走，往东走。第五次循环：21东南西北100020东南西北110010东南西北010000东南西北0100不为终点，有路

6、可走，往东走。第六次循环：22东南西北010121东南西北100020东南西北110010东南西北010000东南西北0100不为终点，有路可走，往南走。第七次循环：32东南西北100022东南西北010121东南西北100020东南西北110010东南西北010000东南西北0100不为终点，有路可走，往东走。第八次循环：33东南西北000032东南西北100022东南西北010121东南西北100020东南西北110010东南西北010000东南西北0100不为终点，无路可走，退回去，封锁东边。第九次循环：32东南西北000022东南西北010121东南西北100020东南西北110010

7、东南西北010000东南西北0100不为终点，无路可走，退回去，封锁南边，往北走。第十次循环：12东南西北100022东南西北000121东南西北100020东南西北110010东南西北010000东南西北0100不为终点，有路可走，往东走。第十一次循环：13东南西北000112东南西北100022东南西北000121东南西北100020东南西北110010东南西北010000东南西北0100不为终点，有路可走，往北走。第十二次循环：03东南西北000013东南西北000112东南西北100022东南西北000121东南西北100020东南西北110010东南西北010000东南西北0100走

8、到终点，算法结束，输出路径。4. 结构化设计：迷宫求解软件选择界面欢迎界面手动录入迷宫随机生成迷宫迷宫求解方向搜寻禁止重复判断结束返回禁止打印结果5. 补充：（1）虽然此程序探讨的是方形迷宫，但是对于形如下面非方形的迷宫，可以用一个方形进行覆盖，原迷宫不变，其余地方都作为墙壁。（2）需要用到计算机求解的迷宫一般规模都比较大，如下图，手动输入时过于繁琐，还不能保证没错，可以采取以下方法减少工作量。运用MATLAB将该图片读入，判断出一个方块所含的像素点，将其像素值全部相加求平均值作为该方块的像素值，黑像素点的像素值和白像素点的像素值相差十分大，因此可以很明显的判断哪些方块是墙壁或通路，生成矩阵。

9、三、 代码示例：#include<stdio.h>#include<stdlib.h>#define Max_size 10000 /迷宫求解路径的长度上限，越大越好 main() void welcome(); /欢迎界面 void choose(); /选择界面 welcome();choose();void welcome()printf("*nn");printf("欢迎来到迷宫求解软件!nn");printf("*nn");void choose()void rand_maze();/选择随机生成迷宫

10、 void hand_maze();/选择手动生成迷宫 int number; printf("选择以下选项：n");printf("输入1：随机生成迷宫n");printf("输入2：手动输入迷宫n");scanf("%d",&number);/考虑数据选项输入违法 while(number!=1&&number!=2)printf("输入错误，重新输入：");scanf("%d",&number);switch(number)case 1:

11、rand_maze();break;case 2:hand_maze();break;void rand_maze()void solve(int *p,int n);int n,*p,i;/迷宫用动态生成的一维数组保存，用指针p指向其首地址 printf("输入迷宫规模(大于等于3)：");scanf("%d",&n);while(n<=2)printf("输入错误，重新输入：");scanf("%d",&n);p=(int *)malloc(sizeof(int)*n*n);for(i=0

12、;i<n*n;i+)if(rand()<=17000)/rand（）所生成的范围在-9032767，将其划分成两半，依此随机生成通路和墙壁 *(p+i)=0;else*(p+i)=1;printf("代表通路，代表墙壁n"); /输出迷宫形状 printf("随机生成的迷宫如下:n");for(i=0;i<n*n;i+)switch(*(p+i)case 1:printf("");break;case 0:printf("");break;if(i+1)%n=0)printf("n&qu

13、ot;);solve(p,n);/进行求解，传送保存迷宫的一维数组的首地址和规模 void hand_maze()/和rand_maze大体相同，不过录入迷宫时用二维数组表示 void solve(int *p,int n);int n,*p,i;printf("输入迷宫规模：");scanf("%d",&n);while(n<=0)printf("输入错误，重新输入：");scanf("%d",&n);p=(int *)malloc(sizeof(int)*n*n);printf("

14、;下面开始录入迷宫，用1表示（通路），用0表示（墙壁）:n");printf("例如:n1 1 0 n0 1 0 n0 1 1 等于 nnn");for(i=0;i<n*n;i+)scanf("%d",p+i);printf("手动生成的迷宫如下:n");for(i=0;i<n*n;i+)switch(*(p+i)case 1:printf("");break;case 0:printf("");break;if(i+1)%n=0)printf("n")

15、;solve(p,n);void solve(int *p,int n)int set(int begin_road2,int end_road2,int n,int *p);void exhaustion(int begin_road2,int end_road2,int n,int *p);int begin_road2,end_road2,judge;/设置起点和终点，在此函数中判断起点终点是否重叠，重叠则返回0，求解完毕；否则返回1，调用函数 exhaustion运用穷举法求解 judge=set(begin_road,end_road,n,p);if(judge=1)exhausti

16、on(begin_road,end_road,n,p);int set(int begin_road2,int end_road2,int n,int *p)int judge,i;/说明规则，按照C语言二维数组的下标进行描述，方便下面编程printf("设置起点和终点，规则如下:n");printf("将迷宫方块所在的位置看成一个矩阵，左上角的下标设为00n");printf("右移一格，第二个下标加1；下移一格，第一个下标加1n");/输入起点和终点首先要判断是否越界，再判断是否为墙壁 /设置起点 do printf("

17、输入起点的横坐标："); scanf("%d",&begin_road0);while(begin_road0<0|begin_road0>=n)printf("越过范围，重新输入:");scanf("%d",&begin_road0);printf("输入起点的纵坐标：");scanf("%d",&begin_road1);while(begin_road1<0|begin_road1>=n)printf("越过范围，重新输入

18、:");scanf("%d",&begin_road1);if(*(p+begin_road0*n+begin_road1)=0)printf("%d%d处是墙壁，设置错误，重新设置!n",begin_road0,begin_road1);judge=1;elsejudge=0;while(judge=1);/设置终点 doprintf("输入终点的横坐标："); scanf("%d",&end_road0);while(end_road0<0|end_road0>=n)pri

19、ntf("越过范围，重新输入:");scanf("%d",&end_road0);printf("输入终点的纵坐标：");scanf("%d",&end_road1);while(end_road1<0|end_road1>=n)printf("越过范围，重新输入:");scanf("%d",&end_road1);if(*(p+end_road0*n+end_road1)=0)printf("%d%d处是墙壁，设置错误，重新设置

20、!n",end_road0,end_road1);judge=1;elsejudge=0;while(judge=1);/设置起点和终点，在此函数中判断起点终点是否重叠，重叠则返回0，求解完毕；否则返回1，调用函数 exhaustion运用穷举法求解 if(begin_road0=end_road0&&begin_road1=end_road1)printf("迷宫的终点和起点重叠，迷宫求解完毕");return 0;elseprintf("在你的设置下，迷宫初始化如下图：代表起点，代表终点:n"); for(i=0;i<

21、n*n;i+)if(i=(begin_road0*n+begin_road1)printf("");if(i+1)%n=0)printf("n");continue;if(i=(end_road0*n+end_road1)printf("");if(i+1)%n=0)printf("n");continue;switch(*(p+i)case 1:printf("");break;case 0:printf("");break;if(i+1)%n=0)printf("

22、;n");return 1;/设置求解时所需的变量结构，栈用结构体数组roadMax_size进行存储，answer指向栈，有栈顶，栈尾和栈长三个量 struct road_step int coordinate2; /存储路径的坐标 int direction4; /存储相应坐标的四个方向的可通行，0不可通，1可通 roadMax_size;struct searchstruct road_step *head;/栈尾 struct road_step *tail; /栈顶 int step_number;answer;/运用穷举法进行求解的函数exhaustion，需要起点，终点

23、，规模，迷宫四个变量 void exhaustion(int begin_road2,int end_road2,int n,int *p)/返回栈顶四个方向中第一个可通的方向，0,1,2,3分别代表东，南，西，北，返回4时表示无路可走 int search_direction(struct road_step *a);/用来判断栈顶四个方向的可通性 void set_direction(struct road_step *a,int n,int *p);/用来判断栈顶是否与终点重合，判断是否求解完毕，重合返回1，否则返回0，用judge接受 int arrive_aim(struct roa

24、d_step *a,int end_road2);/判断完栈顶四个方向的可通性后，为了避免在一个地方转圈圈，若某方向的可通方块已经在栈内，则该方向设为不通 void ban_repeat(struct road_step *aim_end,struct road_step *aim_begin);/因为某方向探索完后发现不通，在退回来时要将该探索方向设置为0 void update_direction(struct road_step *a); /打印行走路线 void printf_road(struct search answer,int n,int *p);int choose_dire

25、ction,i,judge; /judge用来判断是否到达终点 printf("迷宫的求解情况如下：n");/tail指向将要要存储信息的单元，初始化后，head指向road0，tail指向road1，栈长为1，则tail-1表示栈顶 road0.coordinate0=begin_road0;road0.coordinate1=begin_road1;answer.head=&road0;answer.tail=&road1;answer.step_number=1;/设置起点四个方向的可通行 set_direction(answer.tail-1,n,p

26、);/选择栈顶可通的方向进行探索，当探索后此方向不通时，将其置为0，若四个方向都不通则删除栈顶do/按照东，南，西，北的顺序选择第一个可通的方向进行探索 choose_direction=search_direction(answer.tail-1);if(choose_direction!=4)/如果值不为4，表示还能探索，将第一个可通方向的方块放入，并设置该方块的可通行，而且不走重复路 switch(choose_direction) case 0: /东边 answer.tail->coordinate1=(answer.tail-1)->coordinate1+1;answ

27、er.tail->coordinate0=(answer.tail-1)->coordinate0;answer.tail=answer.tail+1;answer.step_number+; /判断是否为终点judge=arrive_aim(answer.tail-1,end_road);/设置栈顶方向，分两步，初始化和不走重复路 set_direction(answer.tail-1,n,p); ban_repeat(answer.tail-1,answer.head);break;case 1: /南边 answer.tail->coordinate1=(answer.

28、tail-1)->coordinate1;answer.tail->coordinate0=(answer.tail-1)->coordinate0+1;answer.tail=answer.tail+1;answer.step_number+; /判断是否为终点judge=arrive_aim(answer.tail-1,end_road);/设置栈顶方向，分两步，初始化和不走重复路 set_direction(answer.tail-1,n,p);ban_repeat(answer.tail-1,answer.head);break;case 2: /西边answer.t

29、ail->coordinate1=(answer.tail-1)->coordinate1-1;answer.tail->coordinate0=(answer.tail-1)->coordinate0;answer.tail=answer.tail+1;answer.step_number+; /判断是否为终点judge=arrive_aim(answer.tail-1,end_road);/设置栈顶方向，分两步，初始化和不走重复路 set_direction(answer.tail-1,n,p); /初步可探索方向 ban_repeat(answer.tail-1,

30、answer.head); /禁止走重复的路 break;case 3: /北边answer.tail->coordinate1=(answer.tail-1)->coordinate1;answer.tail->coordinate0=(answer.tail-1)->coordinate0-1;answer.tail=answer.tail+1;answer.step_number+; /判断是否为终点judge=arrive_aim(answer.tail-1,end_road);/设置栈顶方向，分两步，初始化和不走重复路 set_direction(answer

31、.tail-1,n,p); ban_repeat(answer.tail-1,answer.head);break;if(judge=1) /栈顶是出口了，退出循环，开始输出 break; else /表示栈顶没有方向探索了，删除栈顶，并且新栈顶在通往旧栈顶的方向上设置为不通 answer.tail-;if(answer.step_number!=1)update_direction(answer.tail); answer.step_number-; while(answer.step_number!=0);/若全都探索完毕还没有找到出口，最后会连用来初始化的起点也删除 ，导致answer.

32、step_number=0，此时迷宫无解if(answer.step_number=0)printf("此迷宫无解!");elseprintf_road(answer,n,p);void set_direction(struct road_step *a,int n,int *p) /初始化方向 /先判断是否在边缘/再判断是否在四个角if(a->coordinate0=0&&a->coordinate1=0) /左上角 /西边和北边不通 a->direction2=0,a->direction3=0;/判断东边是否通 if(*(p+a

33、->coordinate0*n+a->coordinate1+1)=1)a->direction0=1;elsea->direction0=1;/判断南边是否通 if(*(p+(a->coordinate0+1)*n+a->coordinate1)=1)a->direction1=1;elsea->direction1=0;return; if(a->coordinate0=0&&a->coordinate1=n-1) /右上角 /东边和北边不通 a->direction0=0,a->direction3=

34、0;/判断西边是否通 if(*(p+a->coordinate0*n+a->coordinate1-1)=1)a->direction2=1;else a->direction2=0;/判断南边是否通 if(*(p+(a->coordinate0+1)*n+a->coordinate1)=1)a->direction1=1;elsea->direction1=0;return; if(a->coordinate0=n-1&&a->coordinate1=0) /左下角 /西边和南边不通 a->direction1

35、=0,a->direction2=0;/判断东边是否通 if(*(p+a->coordinate0*n+a->coordinate1+1)=1)a->direction0=1;elsea->direction0=0; /判断北边是否通 if(*(p+(a->coordinate0-1)*n+a->coordinate1)=1)a->direction3=1;elsea->direction3=0;return; if(a->coordinate0=n-1&&a->coordinate1=n-1) /右下角 /东边

36、和南边不通 a->direction0=0,a->direction1=0;/判断西边是否通 if(*(p+a->coordinate0*n+a->coordinate1-1)=1)a->direction2=1;elsea->direction2=0; /判断北边是否通 if(*(p+(a->coordinate0-1)*n+a->coordinate1)=1)a->direction3=1;elsea->direction3=0;return; /判断是否在上边，第一个坐标是否为0，则北面不通 if(a->coordinat

37、e0=0)a->direction3=0;/判断西边是否通 if(*(p+a->coordinate0*n+a->coordinate1-1)=1)a->direction2=1;elsea->direction2=0; /判断东边是否通 if(*(p+a->coordinate0*n+a->coordinate1+1)=1)a->direction0=1;elsea->direction0=0; /判断南边是否通 if(*(p+(a->coordinate0+1)*n+a->coordinate1)=1)a->direc

38、tion1=1;elsea->direction1=0;return; /判断是否在左边，第二个坐标是否为0，则西边不通 if(a->coordinate1=0)a->direction2=0;/判断东边是否通 if(*(p+a->coordinate0*n+a->coordinate1+1)=1)a->direction0=1;elsea->direction0=0; /判断南边是否通 if(*(p+(a->coordinate0+1)*n+a->coordinate1)=1)a->direction1=1;elsea->di

39、rection1=0;/判断北边是否通 if(*(p+(a->coordinate0-1)*n+a->coordinate1)=1)a->direction3=1;elsea->direction3=0;return; /判断是否在下边，南边不通 if(a->coordinate0=n-1)a->direction1=0;/判断北边是否通 if(*(p+(a->coordinate0-1)*n+a->coordinate1)=1)a->direction3=1;elsea->direction3=0;/判断东边是否通 if(*(p+a

40、->coordinate0*n+a->coordinate1+1)=1)a->direction0=1;elsea->direction0=0;/判断西边是否通 if(*(p+a->coordinate0*n+a->coordinate1-1)=1)a->direction1=1;elsea->direction1=0; return; /判断是否在右边,东边不通 if(a->coordinate1=n-1)a->direction0=0; /判断南边是否通 if(*(p+(a->coordinate0+1)*n+a->c

41、oordinate1)=1)a->direction1=1;elsea->direction1=0; /判断北边是否通 if(*(p+(a->coordinate0-1)*n+a->coordinate1)=1)a->direction3=1;elsea->direction3=0;/判断西边是否通 if(*(p+a->coordinate0*n+a->coordinate1-1)=1)a->direction2=1;elsea->direction2=0; return; /不在边缘/判断南边是否通 if(*(p+(a->co

42、ordinate0+1)*n+a->coordinate1)=1)a->direction1=1;elsea->direction1=0; /判断北边是否通 if(*(p+(a->coordinate0-1)*n+a->coordinate1)=1)a->direction3=1;elsea->direction3=0;/判断西边是否通 if(*(p+a->coordinate0*n+a->coordinate1-1)=1)a->direction2=1;elsea->direction2=0; /判断东边是否通 if(*(p+

43、a->coordinate0*n+a->coordinate1+1)=1)a->direction0=1;elsea->direction0=0;return;int search_direction(struct road_step *a)int i;for(i=0;i<4;i+)if(a->directioni=1)break;return i; /放回的i值代表第一个可通的方向，0,1,2,3分别代表东，南，西，北；为4时代表无路可走 int arrive_aim(struct road_step *a,int end_road2)if(a->c

44、oordinate0=end_road0&&a->coordinate1=end_road1)/是终点return 1;elsereturn 0; void ban_repeat(struct road_step *aim_end,struct road_step *aim_begin) /栈顶的可通方向中不能有已纳入栈的方块 while(aim_begin!=aim_end)/栈的方块在栈顶方块的上边,北边不通 if(aim_begin->coordinate0+1)=aim_end->coordinate0&&aim_begin->c

45、oordinate1=aim_end->coordinate1) aim_end->direction3=0;/栈的方块在栈顶方块的左边,西边不通 if(aim_begin->coordinate0=aim_end->coordinate0&&(aim_begin->coordinate1+1)=aim_end->coordinate1) aim_end->direction2=0;/栈的方块在栈顶方块的下边，南边不通 if(aim_begin->coordinate0-1)=aim_end->coordinate0&

46、;&aim_begin->coordinate1=aim_end->coordinate1) aim_end->direction1=0;/栈的方块在栈顶方块的右边，东边不通if(aim_begin->coordinate0=aim_end->coordinate0&&(aim_begin->coordinate1-1)=aim_end->coordinate1) aim_end->direction0=0;aim_begin+;void update_direction(struct road_step *a)/根据新旧栈顶