西南科技大学：《数据结构》课程教学资源（教案讲义）实验二 栈和队列

实验二栈和队列 实验目的 1、掌握栈和队列的顺序存储结构和链式存储结构,以便在实际背景下 灵活运用 握栈和队列的特点,即先进后出与先进先出的原则 3、栈和队列的基本运算,如入栈和出栈、入队与出队等运算在顺序存 储结构和链式存储结构上的实现。 二、实验内容 1、表达式求值 [问题描述]表达式求值是程序设计语言编译中的一个基本算法。他的 实现是栈应用的一个典型例子。这里采用较为流行的“算符优先法”来实现 对表达式的求值。要把一个表达式翻译成正确求值的一个机器指令序列,或 者是直接对表达式求值,首先要能够正确解释表达式。那么就要了解算术四 则运算的基本规则 1)先乘除,后加减 2)从左算到右 4)先括号内,后括号外。 例如表达式:4+2*3-10/5的计算顺序为: 4+2*3-10/5=4+6-10/5=10-10/5=10-2=8 算符优先法就是根据这个运算优先关系的规则来实现对表达式的编译或解 释执行的。 [基本要求]要求能根据算符优先法则对所输入的四则运算表达进行求 值 [实现提示]任何表达式都由操作数、运算符、定界符组成,我们把运 算符和定界符统称为算符。它们构成的集合命名为ΦP,根据运算法则在每 步中,任意两个算符优先级关系可以由下表来描述 Q2 幸() >>>>><> >>>> <> <<<<< <<<< 其中,Q1<Q2Q1的优先级低于Q2 Q1=Q2Q1的优先级等于Q2

实验二 栈和队列 一、 实验目的 1、掌握栈和队列的顺序存储结构和链式存储结构，以便在实际背景下 灵活运用。 2、 握栈和队列的特点，即先进后出与先进先出的原则。 3、栈和队列的基本运算，如入栈和出栈、入队与出队等运算在顺序存 储结构和链式存储结构上的实现。 二、实验内容 1、表达式求值 [问题描述] 表达式求值是程序设计语言编译中的一个基本算法。他的 实现是栈应用的一个典型例子。这里采用较为流行的“算符优先法”来实现 对表达式的求值。要把一个表达式翻译成正确求值的一个机器指令序列，或 者是直接对表达式求值，首先要能够正确解释表达式。那么就要了解算术四 则运算的基本规则： 1）先乘除，后加减； 2）从左算到右； 4）先括号内，后括号外。 例如表达式：4+2*3-10/5 的计算顺序为： 4+2*3–10/5=4+6–10/5=10–10/5=10–2=8 算符优先法就是根据这个运算优先关系的规则来实现对表达式的编译或解 释执行的。 [基本要求] 要求能根据算符优先法则对所输入的四则运算表达进行求 值。 [实现提示] 任何表达式都由操作数、运算符、定界符组成，我们把运 算符和定界符统称为算符。它们构成的集合命名为 OP，根据运算法则在每 一步中，任意两个算符优先级关系可以由下表来描述: 其中， Q1<Q2 Q1 的优先级低于 Q2 Q1=Q2 Q1 的优先级等于 Q2

Q1>Q2Q1的优先级高于Q2 “#”号表示表达式的开始与结東 该表可以采用二维表表示,由先后两算符的序号做下标定位两者的优先 级,如“*”的序号为2,“+”的序号为1,则“*”与“+”相遇OP[2,1] 得到“>”所以“*”的优先级高 [程序实现] (1)算法思想 为了实现算符优先算法,可以使用两个工作栈,一个是操作数栈OPDS, 另一个是运算符栈oPS,分别存放操作数与算符。首先将标志“#”进运算 符栈OPS的底,按照栈后进先出的原则进行: 遇到操作数,进操作数栈,计算机继续扫描下一符号 遇到运算符时,需要将此算符的优先级与OPS栈顶算符优先级比 若优先级比站顶元素高,则进OPS栈,继续扫描下一符号 若优先级比站顶元素低,则运算符优先级比站顶元素OPS栈顶 元素退栈形成一个操作码Q:同时,操作数栈OPS两次退栈 形成两个操作数a,b.计算机对操作数与操作码完成一次运算 操作,即aQb.其运算结果存放在操作数OPDS栈,作为一次运 算的中间结果进OPDS栈。 ≯若与栈OPS栈顶元素优先级相等,则栈顶元素退栈。当遇到栈 顶元素是“#”时,表示整个运算结果,否则,继续扫描下一 个符号 (2)程序实现 /*初始化* ALsE O #define true 1 #define max 10 #include #include void push opds (: / *push opds stack. * float pop opds(: /=pop opds stack. * void push ops o: /=push ops stack. * float pop ops o: /pop ops stack. * char relation(:/*>,<,=*/ float operate: /*+ - *, /* float opds [MAX int ops [MAX /* operator’ s stack*/ int topd=O

Q1>Q2 Q1 的优先级高于 Q2 “#”号表示表达式的开始与结束。 该表可以采用二维表表示，由先后两算符的序号做下标定位两者的优先 级，如“*”的序号为 2，“+”的序号为 1，则“*”与“+”相遇 OP[2，1] 得到“>”所以“*”的优先级高。 [程序实现] （1） 算法思想 为了实现算符优先算法，可以使用两个工作栈，一个是操作数栈 OPDS， 另一个是运算符栈 OPS，分别存放操作数与算符。首先将标志“#”进运算 符栈 OPS 的底，按照栈后进先出的原则进行： ◆ 遇到操作数，进操作数栈，计算机继续扫描下一符号； ◆ 遇到运算符时，需要将此算符的优先级与 OPS 栈顶算符优先级比 较。 ➢ 若优先级比站顶元素高，则进 OPS 栈，继续扫描下一符号； ➢ 若优先级比站顶元素低，则运算符优先级比站顶元素 OPS 栈顶 元素退栈形成一个操作码 Q；同时，操作数栈 OPDS 两次退栈， 形成两个操作数 a,b.计算机对操作数与操作码完成一次运算 操作，即 aQb.其运算结果存放在操作数 OPDS 栈，作为一次运 算的中间结果进 OPDS 栈。 ➢ 若与栈 OPS 栈顶元素优先级相等，则栈顶元素退栈。当遇到栈 顶元素是“#”时，表示整个运算结果，否则，继续扫描下一 个符号。 （2） 程序实现 /* 初始化*/ #define FALSE 0 #define TRUE 1 #define MAX 10 #include #include void push_opds(); /*push opds stack.*/ float pop_opds(); /*pop opds stack.*/ void push_ops(); /*push ops stack.*/ float pop_ops(); /*pop ops stack.*/ char relation(); /*>,<,=*/ float operate(); /*+,-,*,/*/ float opds[MAX]; /*operand's stack */ int ops[MAX]; /*operator's stack */ int topd=0; /*opds's top*/

/*主函数,表达式求值 void maino char sy flo rinf ("\n Please input expression(# end): \n") sh ops(#') ymb=getchar o while((symb!=#)I((char)(ops[top)!=#)) if((symb!=+)&&(symb!=-)&&(symb!=’*)&&(symb!=/)&&(s ymb!=()&(symb!=)’)&&(symb!=#)&&(symb!=)) /*不是算符,则是操作数进OPDS栈 push opds(symb se /*是算符,先比较优先级,在分情况处理 ch=relation((char)(ops [top]), symb) switch(ch) case case s topd=topd+1: / *push opds stack*/

int top=0; /*opd's top*/ char symb; /*主函数，表达式求值 void main() { char sy; char ch; float a,b; printf("\n Please input expression(# end):\n"); push_ops('#'); symb=getchar(); while ((symb!='#')||((char)(ops[top])!='#')) { if((symb!='+')&&(symb!='-')&&(symb!='*')&&(symb!='/')&&(s ymb!='(')&&(symb!=')')&&(symb!='#')&&(symb!=' ')) { /*不是算符，则是操作数进 OPDS 栈 push_opds(symb); symb=getchar(); } else { /*是算符，先比较优先级，在分情况处理 ch=relation((char)(ops[top]),symb); switch(ch) { case '': sy=pop_ops(); b=pop_opds(); a=pop_opds(); topd=topd+1; /*push_opds stack*/ opds[topd]=operate(a,sy,b);

printf(error\n") printf("\nThe result=%1. 2f\n", opds [topd]); retch /*操作数压栈 void push opds(ch) char c int ch if (topd==MAX-1) printf( the opds stack is overflow. \n") else chi=ch-’0’;/*将字符转化为“值”:“3”转为3 opds [topd]=ch i /*操作数弹栈 float pop opds o return (opds [topd+1]) /*操作符压栈 void push ops (ch) cnal printf( the ops stack is overflow. \ n") else top++:

break; case ' ': printf("error\n"); break; } } } printf("\nThe result=%1.2f\n",opds[topd]); getch(); } /*操作数压栈 void push_opds(ch) char ch; { int ch_i; if (topd==MAX-1) printf("the opds stack is overflow.\n"); else { ch_i=ch-'0'; /*将字符转化为“值”：“3”转为 3 topd++; opds[topd]=ch_i; } } /*操作数弹栈 float pop_opds() { topd=topd-1; return(opds[topd+1]); } /*操作符压栈 void push_ops(ch) char ch; { if (top==MAX-1) printf("the ops stack is overflow.\n"); else { top++;

ops[top]=(int)(ch) /*操作符弹栈 t return((char)(ops [top+1])) /*比较两个算符sym1,sym2的优先关系 char relation(syml, sym2) char chl[2] int ind [2] char re[7][7={{>,>,’’,”〉}, ”>,’〉’,〉’,’〉,’,”〉’,”〉’,〉’,’<’,”〉,”〉}, ”,,, <’,’<,”<,<,<, chl[oj=syml for(i=0;i<=1;i++) switch(chl[il) case '+: ind[i]=0; break ind[i]=l: break case '*t: ind[i]=2; break; case/: ind[i]=3: break case(: ind[i]=4; break case#: ind[i]6: break default: printf ("error\n"): return(0')

ops[top]=(int)(ch); } } /*操作符弹栈 float pop_ops() { top=top-1; return((char)(ops[top+1])); } /*比较两个算符 sym1,sym2 的优先关系 char relation(sym1,sym2) char sym1,sym2; { int i; char chl[2]; int ind[2]; char re[7][7]={ {'>','>','','>'}, {'>','>','','>'}, {'>','>','>','>','','>'}, {'>','>','>','>','','>'}, {'','>','>','>',' ','>','>'}, {'<','<','<','<','<',' ','='}}; chl[0]=sym1; chl[1]=sym2; for (i=0;i<=1;i++) { switch(chl[i]) { case '+': ind[i]=0;break; case '-': ind[i]=1;break; case '*': ind[i]=2;break; case '/': ind[i]=3;break; case '(': ind[i]=4;break; case ')': ind[i]=5;break; case '#': ind[i]=6;break; default:printf("error\n");return('0'); }

return(re[ind[0]][ind[1]]):/*取优先符>、=、< /*执行操作运算 float operate(a, sym, b) float a, b: char sym { float re switch(sym) case + re=a+b: break case/: re=a/b break default: printf(error \n"): return(O) return (re) 2、迷宫路径问题 [问题描述]迷宫实验是取自心理学的一个古典实验。在该实验中,把 只老鼠从一个无顶大盒子的门放入,在盒中设置了许多墙,对行进方向形 成了多处阻挡。盒子仅有一个出口,在出口处放一块奶酪,吸引老鼠在迷宫 中寻找道路以到达出口。对同一只老鼠重复进行上述实验,一直到老鼠从入 口到出口,而不走错一步。老鼠经多次实验终于得到他学习走通迷宫的路线 设计一个计算机程序对任意设定的迷宫,求出一条入口到出口的通路,或得 出没有通路的结论。 [基本要求]要求程序输出: (1)、一条通路的二元组(i,j)数据序列,(i,j)表示同路上某一点 的坐标。 (2)、用一种标志(如数字8)在二维数组中标出该条通路,并在屏幕 上输出二维数组。 [实现提示]可以利用一个二维数组maze[i]j表示迷宫,其中1≤i≤ l≤j≤n。数组元素值为1表示该位置是墙壁,不能通行:元素值为0表 示该位置是通路。假定从maze[1][1]出发,出口位于maze[m][n],移动方向 可以是8个方向(东,东南,南,西南,西,西北,北和东北)。一个构造 的迷宫如下页图

} return(re[ind[0]][ind[1]]); /*取优先符>、=、< } /*执行操作运算 float operate(a,sym,b) float a,b; char sym; { float re; switch(sym) { case '+':re=a+b;break; case '-':re=a-b;break; case '*':re=a*b;break; case '/':re=a/b;break; default:printf("error\n");return(0); } return(re); } 2、迷宫路径问题 [问题描述] 迷宫实验是取自心理学的一个古典实验。在该实验中，把 一只老鼠从一个无顶大盒子的门放入，在盒中设置了许多墙，对行进方向形 成了多处阻挡。盒子仅有一个出口，在出口处放一块奶酪，吸引老鼠在迷宫 中寻找道路以到达出口。对同一只老鼠重复进行上述实验，一直到老鼠从入 口到出口，而不走错一步。老鼠经多次实验终于得到他学习走通迷宫的路线。 设计一个计算机程序对任意设定的迷宫，求出一条入口到出口的通路，或得 出没有通路的结论。 [基本要求] 要求程序输出： （1）、一条通路的二元组（i,j）数据序列，（i,j）表示同路上某一点 的坐标。 （2）、用一种标志（如数字 8）在二维数组中标出该条通路，并在屏幕 上输出二维数组。 [实现提示] 可以利用一个二维数组 maze[i][j]表示迷宫，其中 1≤i≤ m,1≤j≤n。数组元素值为 1 表示该位置是墙壁，不能通行；元素值为 0 表 示该位置是通路。假定从 maze[1][1]出发，出口位于 maze[m][n],移动方向 可以是 8 个方向（东，东南，南，西南，西，西北，北和东北）。一个构造 的迷宫如下页图：

[程序实现] 010001100011111 (1)设计思想 100011011100111 当迷宫采用二维数组表示时,老鼠011000011110011 在迷宫中任一时刻的位置可由数组的110111011011 行列序号i,来表示。而从[[j位110100101111 置出发,可能的行进方向见下图1 001101110100101 如果[i][j周围位置均为0值,则老00110110100101 鼠可以选择这8个维之中的任一个作 011110011111111 为它的下一个位置。将这八个方向分00110110111101 别记作:E(东)、SE(东南、S(南)、110001101100000 SW(西南)、W(西)、N(西北)N00111110001110 (北)和NE(东北)。但是并非每-01001111101110 个位置都有8个相邻位置。如果[i][j 位于边界上,即i=1,或im,或jn,则相邻位置可能是5个或3个。为了避 免检查边界条件,将数组四周围用值为1的边框包围起来,这样二维数组 maze应该声明为maze[m+2][n+2]。 在迷宫中行进时,可能有多个行进方向可供选择,我们可以规定方向搜 索的次序是从东(E)沿顺时针方向进行。为了简化问题,规定[i][j的下 步位置坐标是[x][y],并将这8个方向上的x和y坐标的增量预先放在 个结构数组move[8]中(见图2)。该数组的每个分量有两个域dx和dy。例 如要向东走,只要在j值上加dy,就可以得到下一步位置的[x][y]的值为 [i][j+dy]。于是搜索方向的变化只是要令方向值dir从0增加到7,便可 以从move数组中得到从[i[j点出发搜索到的每一个相邻点[x][y] x=i+move [dir]. dx y=j+move [dir] dy 为了防止重走原路,我们规定对已经走到过的位置,将原值0改为-1 这既可以区别该位置是否已经走到过,又可以与边界值1相区别。当整个搜 索过程结束后,可以将所有的-1该回到0,从而恢复迷宫的原样。 这个计算机走迷宫的算法是:采取一步一步试探的方法。每一步都从东 (E)开始,按顺时针方向对8个方向进行探测,如某个方向上的 maze[x][y]=0,表示可以通行,则走一步;如 maze [x][y]=1,表示此方向上 不可通行,须换方向再试,直至8个方向都试过,maze[x][y]均为1,说明 此步已无路可走,须退回一步,再上一步的下一个方向上重新探测。为此须 设置一个栈,用来记录所走过的位置和方向(i,j,dir)。当退回一步时,就 从栈中退回一个元素,以便在上一个位置的下一个方向上探测,如果有找到 个进行方向,这把但前位置核心的方向重新进栈,并走到新的位置。如果 有探测到x=m,y=n,则已达到迷宫得出口,可以停止检测,输出存在栈中的 路径:若在某一个位置的8个方向上都堵塞,则退回1步,继续探测,如果

[程序实现] （1） 设计思想 当迷宫采用二维数组表示时，老鼠 在迷宫中任一时刻的位置可由数组的 行列序号 i,j 来表示。而从[i][j]位 置出发，可能的行进方向见下图 1。 如果[i][j]周围位置均为 0 值，则老 鼠可以选择这 8 个维之中的任一个作 为它的下一个位置。将这八个方向分 别记作：E（东）、SE（东南）、S（南）、 SW（西南）、W（西）、NW（西北）、N （北）和 NE（东北）。但是并非每一 个位置都有 8 个相邻位置。如果[i][j] 位于边界上，即 i=1,或 i=m,或 j=n,则相邻位置可能是 5 个或 3 个。为了避 免检查边界条件，将数组四周围用值为 1 的边框包围起来，这样二维数组 maze 应该声明为 maze[m+2][n+2]。 在迷宫中行进时，可能有多个行进方向可供选择，我们可以规定方向搜 索的次序是从东（E）沿顺时针方向进行。为了简化问题，规定[i][j]的下 一步位置坐标是[x][y]，并将这 8 个方向上的 x 和 y 坐标的增量预先放在一 个结构数组 move[8]中（见图 2）。该数组的每个分量有两个域 dx 和 dy。例 如要向东走，只要在 j 值上加 dy,就可以得到下一步位置的[x][y]的值为 [i][j+dy]。于是搜索方向的变化只是要令方向值 dir 从 0 增加到 7，便可 以从 move 数组中得到从[i][j]点出发搜索到的每一个相邻点[x][y]。 x=i+move[dir].dx y=j+move[dir].dy 为了防止重走原路，我们规定对已经走到过的位置，将原值 0 改为-1， 这既可以区别该位置是否已经走到过，又可以与边界值 1 相区别。当整个搜 索过程结束后，可以将所有的-1 该回到 0，从而恢复迷宫的原样。 这个计算机走迷宫的算法是：采取一步一步试探的方法。每一步都从东 （E）开始，按顺时针方向对 8 个方向进行探测，如某个方向上的 maze[x][y]=0,表示可以通行，则走一步；如 maze[x][y]=1,表示此方向上 不可通行，须换方向再试，直至 8 个方向都试过，maze[x][y]均为 1，说明 此步已无路可走，须退回一步，再上一步的下一个方向上重新探测。为此须 设置一个栈，用来记录所走过的位置和方向（i,j,dir）。当退回一步时，就 从栈中退回一个元素，以便在上一个位置的下一个方向上探测，如果有找到 一个进行方向，这把但前位置核心的方向重新进栈，并走到新的位置。如果 有探测到 x=m,y=n,则已达到迷宫得出口，可以停止检测，输出存在栈中的 路径；若在某一个位置的 8 个方向上都堵塞，则退回 1 步，继续探测，如果 0 1 0 0 0 1 1 0 0 0 1 1 1 1 1 1 0 0 0 1 1 0 1 1 1 0 0 1 1 1 0 1 1 0 0 0 0 1 1 1 1 0 0 1 1 1 1 0 1 1 1 1 0 1 1 0 1 1 0 0 1 1 0 1 0 0 1 0 1 1 1 1 1 1 1 0 0 1 1 0 1 1 1 0 1 0 0 1 0 1 0 0 1 1 0 1 1 1 0 1 0 0 1 0 1 0 1 1 1 1 0 0 1 1 1 1 1 1 1 1 0 0 1 1 0 1 1 0 1 1 1 1 1 0 1 1 1 0 0 0 1 1 0 1 1 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 1 1 1 1 0 0 1 0 0 1 1 1 1 1 0 1 1 1 1 0

以退出到迷宫的入口(栈中无元素),则表示此迷宫无路径可通行 (2)程序实现 这里用到一个栈,栈的元素是一个结构。为了方便采用顺序栈。由于数 组maze的每一个位置最多被访问一次,所以至多有m*n个元素放入栈中 因此m*n作为栈的容量大小是个安全的值,但也是一个保守的值。一般取 mn/2即可 define 12/*MD米N2为实际使用迷宫数组的大小*/ define # define maXlen m2/*栈的长度* define True 1 define False o intM=M2-w,N=N2-2;/*M*N为迷宫的大小 typedef struct /*定义栈元素的类型 lint x, y, dir teletype typedef struct /*定义顺序栈* lelemtype stack [MAXLEN] int top I sastkt /*定义方向位移数组对于存储坐标增量的方向位移数组move*/ struct moved lint dx, dy /*初始化迷宫*/ void inimaze (int maze [[N2]) for(i;i=M; i++) J- (num=(800*(j+i)+1500)%327;//根据M和N值产生迷宫 f(mum<150)&&(i!=Mj!N) maze [i][j]= maze[][j]=0 printf(maze[i][j);//显示迷宫 printf(“hn”)

以退出到迷宫的入口（栈中无元素），则表示此迷宫无路径可通行。 （2）程序实现 这里用到一个栈，栈的元素是一个结构。为了方便采用顺序栈。由于数 组 maze 的每一个位置最多被访问一次，所以至多有 m*n 个元素放入栈中， 因此 m*n 作为栈的容量大小是个安全的值，但也是一个保守的值。一般取 m*n/2 即可。 # define M2 12 /*M2*N2 为实际使用迷宫数组的大小*/ # define N2 11 # define MAXLEN M2 /*栈的长度*/ # define True 1 # define False 0 # define “stdio.h” int M=M2-w,N=N2-2; /*M*N 为迷宫的大小*/ typedef struct /*定义栈元素的类型*/ {int x,y, dir; }elemtype; typedef struct /*定义顺序栈*/ {elemtype stack[MAXLEN]; int top; }sqstktp; /*定义方向位移数组对于存储坐标增量的方向位移数组 move */ struct moved {int dx,dy; }; /*初始化迷宫*/ void inimaze(int maze[][N2]) {int i,j,num; for(i;i<=M;i++) { for(j=1;i<=n;j++) { num=(800*(j+i)+1500)%327;//根据 M 和 N 值产生迷宫 if((num<150)&&(i!=M||j!=N)) maze[i][j]=1; else maze[i][j]=0; printf(maze[i][j]);//显示迷宫 } printf(“\n”); }

for(i=0,j=0;itop== MAXLEN-1)/*栈满,返回 False*/ s-> stack[艹+s-top]=x;/*栈不满,执行入栈操作*/ return(Ture): 1 /*栈顶元素出栈*/ elemtype pop (sgstktp *s elemtype ele if(s->top<0)/*如果栈空,返回空值*/

printf(“\n”); for(i=0,j=0;itop=-1; }/*inistack*/ /*数据元素 x 入指针 s 所指的栈*/ int push(sqstktp *s,elemtype x) { if (s->top= =MAXLEN-1) /*栈满，返回 False */ return(False); else { s->stack[++s->top]=x; /*栈不满，执行入栈操作*/ return(Ture); } } /*push*/ /*栈顶元素出栈*/ elemtype pop(sqstktp *s) { elemtype elem; if (s->top<0) /*如果栈空，返回空值*/

i elem. x =Null e. y elem. dir =Null return(elem) return(s-> stack[s->top+1]);/*返回栈顶元素*/ }/*pop*/ /*寻找迷宫中的一条通路* void path(int maze[ ][N2], struct moved move[, sqstktp s*) int 1, j, dir, x, y, f elemtype elem maze[l][1]=-1;/*设[1][1]为入口处*/ /*循环,直到入口处或出口处为止*/ x= trove[dir].dx;/*求下一步可行的到达点的坐标*/ =j+move [dir]. dy if(maze [][y]==o) telem. dir f=push(s,elem);/*如果可行,将此点数据入栈*/ f(f== False)/*如果入栈操作返回假,说明栈容量不够*/ printf(“栈长度太短\n”) i=x:j=y: dir=0; maze [x][y]=-1: if(dirtop==-1)&&(dir>=7)‖|(x==M)&&(y= =N)&&(maze[x][y]==-1)) /*如果是入口处,则迷宫无通路*/

{ elem.x =Null; elem.y =Null; elem.dir =Null; return(elem); } else { s->top- -; return(s->stack[s->top+1]); /*返回栈顶元素*/ } }/*pop*/ /*寻找迷宫中的一条通路*/ void path(int maze[ ][N2],struct moved move[],sqstktp s*) { int i,j,dir,x,y,f; elemtype elem; i=1;j=1;dir=0; maze[1][1]=-1; /*设[1][1]为入口处*/ /*循环，直到入口处或出口处为止*/ do { x=i+move[dir].dx; /*求下一步可行的到达点的坐标*/ y=j+move[dir].dy; if (maze[x][y]= =0) { elem.x=i;elem.y=j;elem.dir=dir; f=push(s,elem); /*如果可行，将此点数据入栈*/ if (f= =False) /*如果入栈操作返回假，说明栈容量不够*/ printf(“栈长度太短\n”); i=x;j=y;dir=0;maze[x][y]=-1; } else if (dir top= =-1)&&(dir>=7)||(x= =M)&&(y= =N)&&(maze[x][y]==-1))); /*如果是入口处，则迷宫无通路*/