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”); }