实验二 栈和队列一,实验目的
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
算符优先法就是根据这个运算优先关系的规则来实现对表达式的编译或解释执行的。
[基本要求] 要求能根据算符优先法则对所输入的四则运算表达进行求值。
[实现提示] 任何表达式都由操作数、运算符、定界符组成，我们把运算符和定界符统称为算符。它们构成的集合命名为OP，根据运算法则在每一步中，任意两个算符优先级关系可以由下表来描述:
其中， Q1<Q2 Q1的优先级低于Q2
Q1=Q2 Q1的优先级等于Q2
Q1>Q2 Q1的优先级高于Q2
“#”号表示表达式的开始与结束。
该表可以采用二维表表示，由先后两算符的序号做下标定位两者的优先级，如“*”的序号为2，“+”的序号为1，则“*”与“+”相遇OP[2，1]得到“>”所以“*”的优先级高。
[程序实现]
算法思想为了实现算符优先算法，可以使用两个工作栈，一个是操作数栈OPDS，另一个是运算符栈OPS，分别存放操作数与算符。首先将标志“#”进运算符栈OPS的底，按照栈后进先出的原则进行：
遇到操作数，进操作数栈，计算机继续扫描下一符号；
遇到运算符时，需要将此算符的优先级与OPS栈顶算符优先级比较。
若优先级比站顶元素高，则进OPS栈，继续扫描下一符号；
若优先级比站顶元素低，则运算符优先级比站顶元素OPS栈顶元素退栈形成一个操作码Q；同时，操作数栈OPDS两次退栈，形成两个操作数a,b.计算机对操作数与操作码完成一次运算操作，即aQb.其运算结果存放在操作数OPDS栈，作为一次运算的中间结果进OPDS栈。
若与栈OPS栈顶元素优先级相等，则栈顶元素退栈。当遇到栈顶元素是“#”时，表示整个运算结果，否则，继续扫描下一个符号。
程序实现
/* 初始化*/
#define FALSE 0
#define TRUE 1
#define MAX 10
#include <stdio.h>
#include <stdlib.h>
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*/
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!='/')&&(symb!='(')&&(symb!=')')&&(symb!='#')&&(symb!=' '))
{ /*不是算符，则是操作数进OPDS栈
push_opds(symb);
symb=getchar();
}
else
{ /*是算符，先比较优先级，在分情况处理
ch=relation((char)(ops[top]),symb);
switch(ch)
{
case '<':
push_ops(symb);
symb=getchar();
break;
case '=':
sy=pop_ops();
symb=getchar();
break;
case '>':
sy=pop_ops();
b=pop_opds();
a=pop_opds();
topd=topd+1; /*push_opds stack*/
opds[topd]=operate(a,sy,b);
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);
}
}
/*操作符弹栈
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;
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个方向（东，东南，南，西南，西，西北，北和东北）。一个构造的迷宫如下页图：
[程序实现]
设计思想当迷宫采用二维数组表示时，老鼠在迷宫中任一时刻的位置可由数组的行列序号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步，继续探测，如果以退出到迷宫的入口（栈中无元素），则表示此迷宫无路径可通行。
（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”);
}
printf(“\n”);
for(i=0,j=0;i<=<M+1;i++)//设置迷宫的边界
maze[i][j]=1;
for(i=0,j=N+1;i<=M;i++)
maze[i][j]=1;
for(i=0,j=0;j<=N+1;j++)
maze[i][j]=1;
for(i=M+1,j=0;j<=N+1;)
maze[i][j]=1;
}
/*初始化方向位移数组*/
void inmove(struct moved move[])
/*依次为E,SE,S,SW,W,NW,N,NE*/
{ move[0].dx=0;move[0].dy=1;
move[1].dx=1;move[1].dy=1;
move[2].dx=1;move[2].dy=0;
move[3].dx=1;move[3].dy=-1;
move[4].dx=0;move[4].dy=-1;
move[5].dx=-1;move[5].dy=-1;
move[6].dx=-1;move[6].dy=0;
move[7].dx=-1;move[7].dy=1;
} /*inimove*/
/*初始化栈*/
void inistack(sqstktp *s)
{ s->top=-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) /*如果栈空，返回空值*/
{ 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 <7) /*如果当前方向不可行，就转到下一个方向*/
dir + +;
else
{ elem=pop(s); /*8个方向都不可行，就退回一步*/
if (elem.x!=Null)
{ i=elem.x;
j=elem.y;
dir=elem.dir+1; }
}
}while (!((s->top= =-1)&&(dir>=7)||(x= =M)&&(y= =N)&&(maze[x][y]==-1)));
/*如果是入口处，则迷宫无通路*/
if (s->top= =-1)
printf(“此迷宫无通路\n”);
else
{ elem.x=x;elem.y=y;elem.dir=dir; /*最后出口的坐标入栈*/
f=push(s,elem);
printf(“迷宫通路是：\n”);
i=0;
/*显示迷宫通道*/
while (i<=s->top)
{ printf(“%d,%d”,s->stack[i].x,s->stack[i].y;
if(i!=s->top)
printf(“-->”);
if((i+1)%4= =0)
printf(“\n”);
i++;
}
printf(“\n”);
}
} /*path*/
/*在迷宫中绘制出通路*/
void draw(int maze[][N2],sqstktp *s)
{ int i,j;
elemtype elem;
for(i=1;i<=M;i++) /*将迷宫中全部的-1值恢复为0值*/
for(j=1;j<=N;j++)
if (maze[i][j]= =-1)
maze [i][j]=0;
/*根据栈中元素的坐标，将通路的各个点的值改为8*/
while (s->top>-1)
{ elem=pop(s);
i=elem.x;j=elem.y;
maze[i][j]=8;
}
for(i=1;it=M;i++)
{ for(j=1;j<=N;j++)
printf(“%3d”,maze[i][j]); /*显示已标记通路的迷宫*/
printf(“\n”);
}
printf(“\n”);
} /*draw*/
/*寻找迷宫通路程序*/
void main( )
{ sqstktp *s;
int maze[M2][N2];
struct moved move[8];
inimaze(maze); /*初始化迷宫数组*/
s=(sqstktp )malloc(sizeof(sqstktp));
inistack(s); /*初始化栈*/
inimove(move); /*初始化方向位移数组*/
path(maze,move,s); /*绘制作出通路标记的迷宫*/
}/*main*/
3、迷宫最短路径问题
[问题描述]在第2题给出的条件基础上，要求设计一个算法，寻找一条从迷宫入口到出口的最短路径。输出信息的要求同第2题。
[设计思想] 一般走迷宫的方法是只要找出一条通路即可，至于这条通路是怎样形成的，并没有关系。由于走迷宫的方法是采用试探法，因此第一步试探的方法非常重要，它决定了通路的可能走向。例如第一步向东走与向东南走，最终形成的通路一般是不一样的。本题是在一般走迷宫的方法上，更进一步要求找出一条最短的路径，而不论起始试探的方位为何。
算法的基本思想是：从迷宫的入口[1][1]出发，向四周搜索，记下所有一步能到达的坐标点p11,p12,……，p1k1(0≤k1≤3);然后依次从p11,……,p1k1出发向四周搜索，几下所有从入口点出发，经过两部可以到达的坐标点p21,……，p2k2(0≤K2≤5);依次进行下去，一直到达迷宫的出口处[m][n]。然后从出口出演搜索路径回溯直至入口点，这样就找到了从入口到出口的一条最短路径。
在本算法中，搜索[i][j]点周围8个方向的坐标点，以决定那些坐标点是可以到达的，方法同上机实习题2。这里只是需要解决搜索路径的保存问题。
在搜索过程中必须记下每一个可到达的坐标点，以便从这些点出发继续向四周搜索。由于先到达的点将作为新的起点先进新搜索，故须采用一个先进先出的队列来保存已到达的坐标点。对于每一个记录下来的坐标点，还需同时保存是从哪一个坐标点出发到达的（该坐标点肯定已在队列中了）。另外搜索结束后，还需从出口向入口回溯，以寻找一条通路，因此尽管采用队列形式，但每一个出发点并不真正离开队列（或者说并不真正从队列中将其删除），只是取其值作为搜索的出发点。这样我们采用一个结构数组queue[]来做该队列的存储空间。因为迷宫中的每一个点至多被访问一次，因此queue[]的容量最大为m*n。queue的每一个元素有三个域：x,y,pre。其中x和y分别记下每一个到达点的行、列坐标，pre则是一个静态链域，他保存到达该点的出发点在queue中的下标。该队列的头尾指针front和rear分别指向实际的队头和队尾元素。例如开始时，队列中只有一个元素，即入口点[1][1]，它的pre域值为0，因为不是从其它出发点到达[1][1]的。front和rear同时指向该元素。此后搜索时，均以front所指的元素作为搜索的出发点，当找到一个可到达点时，将该点的坐标及出发点的下标一起入队。而rear始终指向当前入队列的可到达点元素。假如front所指的点出发搜索完毕，则使front指向下一个新的出发点，继续搜索。一直到找到出口点，或者当前队列为空结束。前者表示成功找到通路，而后者则表示迷宫无通路。
在输出通路时，由于是从队列的队尾（出口）向队头（入口）回溯，得到的结果序列就是从出口到入口。为了保证输出通路是从入口到出口，需将队列中回溯得到的结果先入栈，然后再从栈中输出。
[算法实现]
#define M2 12 /*M2×N2为实际使用的迷宫数组的大小*/
#define N2 11
#define MAXLEN M2*N2/2 /*队列和栈的长度*/
#define Ture 1
#define False 0
#include,stido.h”
int M=M2-2,N=N2-2; /* M×N为迷宫大小*/
typedef struct /*定义栈元素的类型*/
{int x,y;
}elemtype;
typedef struct /*定义顺序栈*/
{elemtype stack[MAXLEN];
int top;
}sqstktp;
typedef struct /*定义队列元素的类型*/
{int x,y,pre;
}queeletp;
typedef struct /*定义顺序队列*/
{queeletp queue[MAXLEN];
int front,rear;
}queuetp;
struct moved /*定义方向位移数组元素的类型*/
{int dx;dy;
};
/*初始化迷宫*/
void inimaze(int maze[ ][N2])
{ int i,j,num;
for(i=1;i<=M;i++) /*根据M和N的值产生迷宫*/
{ for(j=1;j<=N;j++)
{ num=(800*(i+j)+1500) &327;
if (num<150 &&(i!=M ||j!=N))
maze[i][j]=1;
else
maze[i][j]=0;
printf(“%3d”,maze[i][j]); /*显示迷宫*/
}
printf(“\n”);
}
printf(“\n”);
for(i=0,j=0;i<=M+1;i++) /*设置迷宫的边界值*/
maze[i][j]=1;
for(i=0,j=N+1;i<=M+1;i++)
maze[i][j]=1;
for (i=0,j=0;j<=N+1;j++)
maze[i][j]=1;
for(i=M+1,j=0;j<=N+1;j++)
maze[i][j]=1;
} /*inimaze*/
/*初始化方向位移数组*/
void inimove(struct moved move[])
{ move[0].dx=0;move[0].dy=1; /*依次为 E,SE,S,SW,W,NW,N,NE*/
move[1].dx=1;move[1].dy=1;
move[2].dx=1;move[2].dy=0;
move[3].dx=1;move[3].dy=-1;
move[4].dx=0;move[4].dy=-1;
move[5].dx=-1;move[5].dy=-1;
move[6].dx=-1;move[6].dy=0;
move[7].dx=-1;move[7].dy=1;
}/*inimove*/
/*初始化栈*/
void inistack(sqstktp *s)
{s->top=-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) /*如果栈空，返回空值*/
{ elem.x=Null;
elem.y=Null;
elem.dir=Null;
return(elem);
}
else
{ s->top- -;
return(s->stack[s->top+1]); /*栈不空，返回栈顶元素*/
}
}/*pop*/
/*初始化队列*/
void iniqueue(queuetp *s)
{ s->fornt=1; /*为直观，设置队头在数组下标为1处*/
s->rear=1;
} /*iniqueue*/
/*寻找迷宫中最短路径
int shortpath(int maze[][N2],struct moved move[],queuetp *p)
{ int i,j,dir,x,y;
p->queue[1].x=1;//入口点坐标入队列
p->queue[1].y=1;
p->queue[1].pre=0;
maze[1][1]=-1;//设置入口点以到达
while(p->front<=p->rear)//当队列不空时循环
{ i=p->queue[p->front].x;//j,i为出发点
j->p->queue[p->fornt].y;
for(dir=0;dir<8;dir++)
{ x=I+move[dir].dx;
y=j+move[dir].dy;
if(maze[x][y]==0)//如有可到达点，将此点坐标入对列
{ p->rear++:
p->queue[p->rear].x=x;
p->queue[p->rear].y=y;
p->queue[p->rear].pre=p->front;
maze[x][y]=-1;//设置已达到标志
}
if(((x==M)&&(y==N))//如到达出口，返回true
return（true）;
}
p->front++;//对头指针指向下一个队列元素
}
return (false);//迷宫无通路
}
/*显示迷宫通路
void printpath(queuetp*p,sqstktp *s)
{ int i,f;
elemtype elem;
i=p->rear;
Do /*从队列中取出最短路径放入栈中
{ elem.x=p->queue[I].x;
elem.x=p->queue[I].y;
f=push(s,elem);
if(f==false)//如果f为假，则栈长度太短
printf(“栈长太短“)；
i=p->queue[i].pre;
}while(i>0);
i=s->top;
While(i>-1)
{ printf(s->stack[i].x,s->stack[i].y);/*显示迷宫最短的通路
if(i>0)
printf(“(”);
if((s->top-i+1)%4==0)
printf(“\n”);
i—;
}
printf(“\n”);
}
/*在迷宫中绘出最短路径
void draw(int maze[][n2],sqstktp*s)
{ int i,j;
elemtype elem;
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
if(maze[i][j]==-1)
maze[i][j]=0;
while(s->top=-1)//根据栈中元素的坐标，将最短路径各点的值该为8
{ elem=pop(s);
i=elem.x;j=elem.y;
Maze[i][j]=8;
}
for(i=1;i<=m;i++)//显示已标记最短通路的迷宫
{ for(j=1;j<=n;j++)
printf(maze[i][j]);
printf(“\n”);
}
printf(“\n”);
}
/*寻找迷宫最短通路路径程序
Void main()
{ sqstktp *s;
queuetp *p;
int maze[m2][n2],f;
struct moved move[8];
inimaze(maze);/*初始化迷宫
s=(sqstktp*)malloc(sizeof(sqstktp));
inistack(s);/*初始化栈
p=(queuetp*)malloc(sizeof(queuetp));
iniqueue(p);/*初始化队列
inimove(move);/*初始化方向为一数组
f=shortpath(maze,move,p)/* 寻找迷宫最短通路路径程序
if(f==true)
{ printpath(p,s);/*如果找到，显示通路和绘制出通路标记的迷宫
draw(maze,s);
}
else
printf(“此迷宫无通路\n”);/*如果没找到显示无通路
}
4、停车场管理
[问题描述] 有一个可以停放n辆汽车的狭长停车场，它只有一个大门可以供车辆进出。车辆按到达停车场时间的早晚依次从停车场最里面向大门口处停放（最先到达的第一辆车放在停车场的最里面）。如果停车场已停放满n辆车，则后来的车辆只能在停车场大门外的便道上等候，一旦停车场内有车开走，则排在便道上的第一辆车就进入停车场。停车场内如果有某辆车要开走，在它之后进入停车场的车都必须先退出停车场为它让路，待其开出停车场后，这些车再按原来的次序进场。每辆车在离开停车场是，都应根据它在停车场内停留的时间长短交费。如果停留在便道上的车未进入停车场就要离去，允许其离去，不收停车费，并仍然保持在便道上等待的车辆的次序。编制一个程序模拟该停车场的管理。
[实现要求] 要求程序输出每辆车到达后的位置（停车场或便道上），以及某辆车离开停车场是应交纳的费用和它在停车场内停留的时间。
[实现提示] 汽车的模拟输入信息格式可以是：（到达/离去，汽车牌照号码，到达/离去的时刻）。例如，（‘A’，1，5）表示1号牌照车在5这个时刻到达，而（‘D’，5，20）表示5号牌照车在20这个时刻离去。整个过程可以在输入信息为（‘E’，0，0）时结束。本题可以用栈和队列来实现。
[程序实现]
设计思想根据题目要求，停车场只有一个门，因此可用一个栈来模拟；而当栈满后，继续来到的车辆只能停在便道上，根据便道停车的特点，可知这可以用一个队列来模拟，先排队的车辆先离开便道，进入停车场。由于停在停车场中间的车辆可以提出离开停车场，并且要求在离开到停车场到停车场大门之间的车辆都必须先离开停车场，让此车离去，然后再让这些车辆按原来的次序进入停车场，因此在一个栈和队列的基础上，还需要有一个地方（车辆规避所）保存为了让路而离开停车场的车辆，很显然这也应该用一个栈来模拟。因此本题中用到两个栈和一个队列对于停车场和车辆贵比索，有车辆经过和离去两个动作，这就是栈的进栈和出栈操作，只是还允许排在中间的车辆先离开停车场，因此在栈中需要进行查找。而对于便道，也有如队列和入队列的操作，同样允许排在中间的车辆先离开队列。这样基本动作只需利用栈和队列的基本操作即可实现。
整个操作过程是：当输入数据表示有车辆到达，则判断栈是否慢，若未满就将新数据进栈（表示新到达的车辆进入停车场的里面），数据应包括车牌号和到达时间；若以满，就将数据放在队尾，表示车辆在便道上等待进入停车场。
当输入数据表示有车辆要离去，就在栈中寻找是否有该车牌号的车辆，如有就让此车辆离开停车场，并根据停车时间记费；如没有找到，就到队列中（便道上）去寻找此车牌号的车辆，如有就允许此车辆离开队列，但不收费；如没有就显示出错信息。
当离开停车场的车辆位于栈的中间时，必须先将此位置到站顶之间的所有数据倒到另一个栈中去（车辆规避所），然后安排车辆出栈，最后将另一个栈中的数据倒回到停车场栈中来。
在模拟停车场管理时，还应注意，如果停车场栈中已没有车辆停放时，输入数据仍然要求车辆退出，则显示出错信息；程序中停车场的停车数量为n，但对便道没有规定，因此认为便道上可以听任意多的车辆。
程序实现根据题目分析的结果，停车场和车辆规避所的栈可以采用顺序栈，而便道可用链队列来模拟。
#define N 2 /*定义停车场栈长度*/
#define M 5 /*M为单元时间的收费值*/
#define True 1
#define False 0
#include,stdio.h”
/*存储结构*/
typedef struct /*定义栈元素的类型*/
{int num;
int arrtime;
}elemtype;
typedef struct /*定义栈*/
{elemtype stack[N];
int top;
}sqstktp;
typedef struct node /*定义队列节点的类型*/
{int num;
struct node *next;
}queueptr;
typedef struct /*定义队列*/
{queueptr *front,*rear;
}linkedquetp;
/*初始化栈*/
void inistack(sqstktp s)
{ s->top= -1;
}
/*压栈，将数据元素x压入指针s所指的栈*/
int push(sqstktp s,elemtype x)
{ if (s->top= =N-1)
return (False); /*如果栈满，返回False*/
else
{ s->stack[++s->top]=x; /*栈不满，x入栈。*/
return (True);
}
}/*push*/
/*弹栈，将栈顶元素出栈*/
elemtype pop (sqstktp *s)
{ elemtype x ;
if (s->top<0)
{ x.num=Null;
x.arrtime=Null;
return (x); /*如果栈空，返回空值*/
}
else
{ s->top - -;
return (s->stack[s->top+1]); /*返回栈顶元素*/
}
}/*pop*/
/*初始化队列*/
void inilinkedque (linkedquetp s)
{ s->fornt= (queueptr )malloc (sizeof (queueptr)); /产生一个新节点，作头节点*/
s->rear= s->fornt;
s->front->next =Null;
s->front->num =0; /*头节点的num保存队列元素的个数*/
}/* nilinkedque */
/*数据入队列*/
void enlinkedque (linkedquetp s,int numl)
{ queueptr *p;
p= (queueptr)malloc (sizeof (queueptr));/*产生一个新节点*/
p->num =numl;
p->next =Null;
s->rear->next=p; /*新节点入队列*/
s->rear=p;
s->front->num++; /*队列元素个数加1*/
}/*enlinkedque*/
/*数据出队列*/
int dllinkedque(linkedquetp s)
{ queueptr *p;
int n;
if (s->front ==s->rear)
return (Null); /*如果队列空，返回空值*/
else
{ p=s->front->next=p->next; /*返回队头元素值*/
if (p->next==Null)
s->rear=s->front;
n=p->num;
free(p);
s->front->num - -; /*队列元素的个数减1*/
return (n);
}
}/*dllinkedque*/
/*处理车辆到达的情况*/
void arrive(sqstktp *sl,linkedquetp *p,elemtype x)
{ int f;
f=push (s1,x); /*新到达的车辆入停车场栈*/
if (f==False)
{ enlinkedque(p,x.num); /*如停车场满，入便道队列*/
printf(“第%d号车停在便道第%d号车位上 \n”,x.num,p->front->num);
}
else /*新到车辆进入停车场*/
printf(“第%d号车停在停车场第%d号车位上\n”,x.num,sl->top+1);
}/*arrive*/
/*处理车辆离去的情况*/
void delive(sqstktp *sl,sqstktp *s2,linkedquetp *p,elemtype x)
{ int n,f=False;
elemtype y;
queueptr *q;
/*在停车场中寻找要离开的车辆*/
while ((sl->top>-1)&&(f!=Ture))
{ y=pop(sl);
if (y.num!=x.num) /*如果栈顶元素不是要离开的车辆，就将其放入车辆规避所*/
n=push(s2,y);
else
f=Ture;
}/*end of while
if (y.num= =x.num) /*在停车场中找到要离开的车辆*/
{ printf(“第%d号车应收费%d元\n”,y.num,(x.arrtime-y.arrtime)*M);
/*车辆规避所不空，将其全部放回停车场*/
while (s2->top>-1)
{ y=pop(s2);
f=push(s1,y); }
n=dllinkedque(p);
/*如便道上有车辆，将第一辆车放入停车场*/
if (n!=Null)
{ y.num=n;
y.arrtime=x.arrtime; /*计费时间为刚离开车辆的离去时间*/
f=push(s1,y);
printf(“第%d号车停在停车场第%d号车位上\n”,y.num,s1->top+1);
}
}/*end the pat one of if
else /*在停车场中没有找到要离开的车辆*/
{ while (s2->top>-1) /*将车辆规避所中的所有车辆放入停车场*/
{ y=pop(s2);
f=push(s1,y);
}
q=p->front;
f=False;
/*在便道上寻找要离开的车辆*/
while (f= =False &&q->next!=Null)
if (q->next->num!=x.num)
q=q->next;
else
/*在便道上找到该车辆*/
{ q->next=q->next->next;
p->fornt->num - -;
if (q->next= =Null)
p->rear=p->front;
printf(“第%d号车离开便道\n”,x.num); /*该车离开便道，但不收费*/
f=Ture;
}
/*在便道上也没找到要离开的车辆，输入数据错误*/
if (f= =False)
printf(“输入数据错误,停车场和便道上均无第%d号车\n”,x.num);
}
}/*delive*/
/*停车场模拟管理程序*/
void main( )
{ char ch1,ch2;
sqstktp *s1,*s2;
linkedquetp *p;
elemtype x;
int flag;
s1=(sqstktp *)malloc(sizeof(sqstktp));
s2=(sqstktp *)malloc(sizeof(sqstktp));
p=(linkedquetp *)malloc(sizeof(linkedquetp));
inistack(s1); /*初始化停车场栈*/
inistack(s2); /*初始化便道队列*/
flag= true;
for(;;)
{printf(“输入数据：‘A’/ ‘D’,车牌号，到达/离开时间\n”);
scanf(“%c %d %d”,&ch1,&x.num,x.arrtime);
ch2=getchar( );
switch (ch1)
{ case ‘A’, arrive(s1,p,x); /*车辆到达*/
break;
case ‘D’, delive(s1,s2,p,x); /*车辆离去*/
break;
case ‘E’,flag=False; /*结束程序运行*/
printf(“程序正常结束\n”);
break;
default,printf(“输入数据错误，重新输入\n”);
}
if (flag = =False) break;
}
}/*main*/
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
算符优先法就是根据这个运算优先关系的规则来实现对表达式的编译或解释执行的。
[基本要求] 要求能根据算符优先法则对所输入的四则运算表达进行求值。
[实现提示] 任何表达式都由操作数、运算符、定界符组成，我们把运算符和定界符统称为算符。它们构成的集合命名为OP，根据运算法则在每一步中，任意两个算符优先级关系可以由下表来描述:
其中， Q1<Q2 Q1的优先级低于Q2
Q1=Q2 Q1的优先级等于Q2
Q1>Q2 Q1的优先级高于Q2
“#”号表示表达式的开始与结束。
该表可以采用二维表表示，由先后两算符的序号做下标定位两者的优先级，如“*”的序号为2，“+”的序号为1，则“*”与“+”相遇OP[2，1]得到“>”所以“*”的优先级高。
[程序实现]
算法思想为了实现算符优先算法，可以使用两个工作栈，一个是操作数栈OPDS，另一个是运算符栈OPS，分别存放操作数与算符。首先将标志“#”进运算符栈OPS的底，按照栈后进先出的原则进行：
遇到操作数，进操作数栈，计算机继续扫描下一符号；
遇到运算符时，需要将此算符的优先级与OPS栈顶算符优先级比较。
若优先级比站顶元素高，则进OPS栈，继续扫描下一符号；
若优先级比站顶元素低，则运算符优先级比站顶元素OPS栈顶元素退栈形成一个操作码Q；同时，操作数栈OPDS两次退栈，形成两个操作数a,b.计算机对操作数与操作码完成一次运算操作，即aQb.其运算结果存放在操作数OPDS栈，作为一次运算的中间结果进OPDS栈。
若与栈OPS栈顶元素优先级相等，则栈顶元素退栈。当遇到栈顶元素是“#”时，表示整个运算结果，否则，继续扫描下一个符号。
程序实现
/* 初始化*/
#define FALSE 0
#define TRUE 1
#define MAX 10
#include <stdio.h>
#include <stdlib.h>
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*/
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!='/')&&(symb!='(')&&(symb!=')')&&(symb!='#')&&(symb!=' '))
{ /*不是算符，则是操作数进OPDS栈
push_opds(symb);
symb=getchar();
}
else
{ /*是算符，先比较优先级，在分情况处理
ch=relation((char)(ops[top]),symb);
switch(ch)
{
case '<':
push_ops(symb);
symb=getchar();
break;
case '=':
sy=pop_ops();
symb=getchar();
break;
case '>':
sy=pop_ops();
b=pop_opds();
a=pop_opds();
topd=topd+1; /*push_opds stack*/
opds[topd]=operate(a,sy,b);
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);
}
}
/*操作符弹栈
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;
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个方向（东，东南，南，西南，西，西北，北和东北）。一个构造的迷宫如下页图：
[程序实现]
设计思想当迷宫采用二维数组表示时，老鼠在迷宫中任一时刻的位置可由数组的行列序号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步，继续探测，如果以退出到迷宫的入口（栈中无元素），则表示此迷宫无路径可通行。
（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”);
}
printf(“\n”);
for(i=0,j=0;i<=<M+1;i++)//设置迷宫的边界
maze[i][j]=1;
for(i=0,j=N+1;i<=M;i++)
maze[i][j]=1;
for(i=0,j=0;j<=N+1;j++)
maze[i][j]=1;
for(i=M+1,j=0;j<=N+1;)
maze[i][j]=1;
}
/*初始化方向位移数组*/
void inmove(struct moved move[])
/*依次为E,SE,S,SW,W,NW,N,NE*/
{ move[0].dx=0;move[0].dy=1;
move[1].dx=1;move[1].dy=1;
move[2].dx=1;move[2].dy=0;
move[3].dx=1;move[3].dy=-1;
move[4].dx=0;move[4].dy=-1;
move[5].dx=-1;move[5].dy=-1;
move[6].dx=-1;move[6].dy=0;
move[7].dx=-1;move[7].dy=1;
} /*inimove*/
/*初始化栈*/
void inistack(sqstktp *s)
{ s->top=-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) /*如果栈空，返回空值*/
{ 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 <7) /*如果当前方向不可行，就转到下一个方向*/
dir + +;
else
{ elem=pop(s); /*8个方向都不可行，就退回一步*/
if (elem.x!=Null)
{ i=elem.x;
j=elem.y;
dir=elem.dir+1; }
}
}while (!((s->top= =-1)&&(dir>=7)||(x= =M)&&(y= =N)&&(maze[x][y]==-1)));
/*如果是入口处，则迷宫无通路*/
if (s->top= =-1)
printf(“此迷宫无通路\n”);
else
{ elem.x=x;elem.y=y;elem.dir=dir; /*最后出口的坐标入栈*/
f=push(s,elem);
printf(“迷宫通路是：\n”);
i=0;
/*显示迷宫通道*/
while (i<=s->top)
{ printf(“%d,%d”,s->stack[i].x,s->stack[i].y;
if(i!=s->top)
printf(“-->”);
if((i+1)%4= =0)
printf(“\n”);
i++;
}
printf(“\n”);
}
} /*path*/
/*在迷宫中绘制出通路*/
void draw(int maze[][N2],sqstktp *s)
{ int i,j;
elemtype elem;
for(i=1;i<=M;i++) /*将迷宫中全部的-1值恢复为0值*/
for(j=1;j<=N;j++)
if (maze[i][j]= =-1)
maze [i][j]=0;
/*根据栈中元素的坐标，将通路的各个点的值改为8*/
while (s->top>-1)
{ elem=pop(s);
i=elem.x;j=elem.y;
maze[i][j]=8;
}
for(i=1;it=M;i++)
{ for(j=1;j<=N;j++)
printf(“%3d”,maze[i][j]); /*显示已标记通路的迷宫*/
printf(“\n”);
}
printf(“\n”);
} /*draw*/
/*寻找迷宫通路程序*/
void main( )
{ sqstktp *s;
int maze[M2][N2];
struct moved move[8];
inimaze(maze); /*初始化迷宫数组*/
s=(sqstktp )malloc(sizeof(sqstktp));
inistack(s); /*初始化栈*/
inimove(move); /*初始化方向位移数组*/
path(maze,move,s); /*绘制作出通路标记的迷宫*/
}/*main*/
3、迷宫最短路径问题
[问题描述]在第2题给出的条件基础上，要求设计一个算法，寻找一条从迷宫入口到出口的最短路径。输出信息的要求同第2题。
[设计思想] 一般走迷宫的方法是只要找出一条通路即可，至于这条通路是怎样形成的，并没有关系。由于走迷宫的方法是采用试探法，因此第一步试探的方法非常重要，它决定了通路的可能走向。例如第一步向东走与向东南走，最终形成的通路一般是不一样的。本题是在一般走迷宫的方法上，更进一步要求找出一条最短的路径，而不论起始试探的方位为何。
算法的基本思想是：从迷宫的入口[1][1]出发，向四周搜索，记下所有一步能到达的坐标点p11,p12,……，p1k1(0≤k1≤3);然后依次从p11,……,p1k1出发向四周搜索，几下所有从入口点出发，经过两部可以到达的坐标点p21,……，p2k2(0≤K2≤5);依次进行下去，一直到达迷宫的出口处[m][n]。然后从出口出演搜索路径回溯直至入口点，这样就找到了从入口到出口的一条最短路径。
在本算法中，搜索[i][j]点周围8个方向的坐标点，以决定那些坐标点是可以到达的，方法同上机实习题2。这里只是需要解决搜索路径的保存问题。
在搜索过程中必须记下每一个可到达的坐标点，以便从这些点出发继续向四周搜索。由于先到达的点将作为新的起点先进新搜索，故须采用一个先进先出的队列来保存已到达的坐标点。对于每一个记录下来的坐标点，还需同时保存是从哪一个坐标点出发到达的（该坐标点肯定已在队列中了）。另外搜索结束后，还需从出口向入口回溯，以寻找一条通路，因此尽管采用队列形式，但每一个出发点并不真正离开队列（或者说并不真正从队列中将其删除），只是取其值作为搜索的出发点。这样我们采用一个结构数组queue[]来做该队列的存储空间。因为迷宫中的每一个点至多被访问一次，因此queue[]的容量最大为m*n。queue的每一个元素有三个域：x,y,pre。其中x和y分别记下每一个到达点的行、列坐标，pre则是一个静态链域，他保存到达该点的出发点在queue中的下标。该队列的头尾指针front和rear分别指向实际的队头和队尾元素。例如开始时，队列中只有一个元素，即入口点[1][1]，它的pre域值为0，因为不是从其它出发点到达[1][1]的。front和rear同时指向该元素。此后搜索时，均以front所指的元素作为搜索的出发点，当找到一个可到达点时，将该点的坐标及出发点的下标一起入队。而rear始终指向当前入队列的可到达点元素。假如front所指的点出发搜索完毕，则使front指向下一个新的出发点，继续搜索。一直到找到出口点，或者当前队列为空结束。前者表示成功找到通路，而后者则表示迷宫无通路。
在输出通路时，由于是从队列的队尾（出口）向队头（入口）回溯，得到的结果序列就是从出口到入口。为了保证输出通路是从入口到出口，需将队列中回溯得到的结果先入栈，然后再从栈中输出。
[算法实现]
#define M2 12 /*M2×N2为实际使用的迷宫数组的大小*/
#define N2 11
#define MAXLEN M2*N2/2 /*队列和栈的长度*/
#define Ture 1
#define False 0
#include,stido.h”
int M=M2-2,N=N2-2; /* M×N为迷宫大小*/
typedef struct /*定义栈元素的类型*/
{int x,y;
}elemtype;
typedef struct /*定义顺序栈*/
{elemtype stack[MAXLEN];
int top;
}sqstktp;
typedef struct /*定义队列元素的类型*/
{int x,y,pre;
}queeletp;
typedef struct /*定义顺序队列*/
{queeletp queue[MAXLEN];
int front,rear;
}queuetp;
struct moved /*定义方向位移数组元素的类型*/
{int dx;dy;
};
/*初始化迷宫*/
void inimaze(int maze[ ][N2])
{ int i,j,num;
for(i=1;i<=M;i++) /*根据M和N的值产生迷宫*/
{ for(j=1;j<=N;j++)
{ num=(800*(i+j)+1500) &327;
if (num<150 &&(i!=M ||j!=N))
maze[i][j]=1;
else
maze[i][j]=0;
printf(“%3d”,maze[i][j]); /*显示迷宫*/
}
printf(“\n”);
}
printf(“\n”);
for(i=0,j=0;i<=M+1;i++) /*设置迷宫的边界值*/
maze[i][j]=1;
for(i=0,j=N+1;i<=M+1;i++)
maze[i][j]=1;
for (i=0,j=0;j<=N+1;j++)
maze[i][j]=1;
for(i=M+1,j=0;j<=N+1;j++)
maze[i][j]=1;
} /*inimaze*/
/*初始化方向位移数组*/
void inimove(struct moved move[])
{ move[0].dx=0;move[0].dy=1; /*依次为 E,SE,S,SW,W,NW,N,NE*/
move[1].dx=1;move[1].dy=1;
move[2].dx=1;move[2].dy=0;
move[3].dx=1;move[3].dy=-1;
move[4].dx=0;move[4].dy=-1;
move[5].dx=-1;move[5].dy=-1;
move[6].dx=-1;move[6].dy=0;
move[7].dx=-1;move[7].dy=1;
}/*inimove*/
/*初始化栈*/
void inistack(sqstktp *s)
{s->top=-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) /*如果栈空，返回空值*/
{ elem.x=Null;
elem.y=Null;
elem.dir=Null;
return(elem);
}
else
{ s->top- -;
return(s->stack[s->top+1]); /*栈不空，返回栈顶元素*/
}
}/*pop*/
/*初始化队列*/
void iniqueue(queuetp *s)
{ s->fornt=1; /*为直观，设置队头在数组下标为1处*/
s->rear=1;
} /*iniqueue*/
/*寻找迷宫中最短路径
int shortpath(int maze[][N2],struct moved move[],queuetp *p)
{ int i,j,dir,x,y;
p->queue[1].x=1;//入口点坐标入队列
p->queue[1].y=1;
p->queue[1].pre=0;
maze[1][1]=-1;//设置入口点以到达
while(p->front<=p->rear)//当队列不空时循环
{ i=p->queue[p->front].x;//j,i为出发点
j->p->queue[p->fornt].y;
for(dir=0;dir<8;dir++)
{ x=I+move[dir].dx;
y=j+move[dir].dy;
if(maze[x][y]==0)//如有可到达点，将此点坐标入对列
{ p->rear++:
p->queue[p->rear].x=x;
p->queue[p->rear].y=y;
p->queue[p->rear].pre=p->front;
maze[x][y]=-1;//设置已达到标志
}
if(((x==M)&&(y==N))//如到达出口，返回true
return（true）;
}
p->front++;//对头指针指向下一个队列元素
}
return (false);//迷宫无通路
}
/*显示迷宫通路
void printpath(queuetp*p,sqstktp *s)
{ int i,f;
elemtype elem;
i=p->rear;
Do /*从队列中取出最短路径放入栈中
{ elem.x=p->queue[I].x;
elem.x=p->queue[I].y;
f=push(s,elem);
if(f==false)//如果f为假，则栈长度太短
printf(“栈长太短“)；
i=p->queue[i].pre;
}while(i>0);
i=s->top;
While(i>-1)
{ printf(s->stack[i].x,s->stack[i].y);/*显示迷宫最短的通路
if(i>0)
printf(“(”);
if((s->top-i+1)%4==0)
printf(“\n”);
i—;
}
printf(“\n”);
}
/*在迷宫中绘出最短路径
void draw(int maze[][n2],sqstktp*s)
{ int i,j;
elemtype elem;
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
if(maze[i][j]==-1)
maze[i][j]=0;
while(s->top=-1)//根据栈中元素的坐标，将最短路径各点的值该为8
{ elem=pop(s);
i=elem.x;j=elem.y;
Maze[i][j]=8;
}
for(i=1;i<=m;i++)//显示已标记最短通路的迷宫
{ for(j=1;j<=n;j++)
printf(maze[i][j]);
printf(“\n”);
}
printf(“\n”);
}
/*寻找迷宫最短通路路径程序
Void main()
{ sqstktp *s;
queuetp *p;
int maze[m2][n2],f;
struct moved move[8];
inimaze(maze);/*初始化迷宫
s=(sqstktp*)malloc(sizeof(sqstktp));
inistack(s);/*初始化栈
p=(queuetp*)malloc(sizeof(queuetp));
iniqueue(p);/*初始化队列
inimove(move);/*初始化方向为一数组
f=shortpath(maze,move,p)/* 寻找迷宫最短通路路径程序
if(f==true)
{ printpath(p,s);/*如果找到，显示通路和绘制出通路标记的迷宫
draw(maze,s);
}
else
printf(“此迷宫无通路\n”);/*如果没找到显示无通路
}
4、停车场管理
[问题描述] 有一个可以停放n辆汽车的狭长停车场，它只有一个大门可以供车辆进出。车辆按到达停车场时间的早晚依次从停车场最里面向大门口处停放（最先到达的第一辆车放在停车场的最里面）。如果停车场已停放满n辆车，则后来的车辆只能在停车场大门外的便道上等候，一旦停车场内有车开走，则排在便道上的第一辆车就进入停车场。停车场内如果有某辆车要开走，在它之后进入停车场的车都必须先退出停车场为它让路，待其开出停车场后，这些车再按原来的次序进场。每辆车在离开停车场是，都应根据它在停车场内停留的时间长短交费。如果停留在便道上的车未进入停车场就要离去，允许其离去，不收停车费，并仍然保持在便道上等待的车辆的次序。编制一个程序模拟该停车场的管理。
[实现要求] 要求程序输出每辆车到达后的位置（停车场或便道上），以及某辆车离开停车场是应交纳的费用和它在停车场内停留的时间。
[实现提示] 汽车的模拟输入信息格式可以是：（到达/离去，汽车牌照号码，到达/离去的时刻）。例如，（‘A’，1，5）表示1号牌照车在5这个时刻到达，而（‘D’，5，20）表示5号牌照车在20这个时刻离去。整个过程可以在输入信息为（‘E’，0，0）时结束。本题可以用栈和队列来实现。
[程序实现]
设计思想根据题目要求，停车场只有一个门，因此可用一个栈来模拟；而当栈满后，继续来到的车辆只能停在便道上，根据便道停车的特点，可知这可以用一个队列来模拟，先排队的车辆先离开便道，进入停车场。由于停在停车场中间的车辆可以提出离开停车场，并且要求在离开到停车场到停车场大门之间的车辆都必须先离开停车场，让此车离去，然后再让这些车辆按原来的次序进入停车场，因此在一个栈和队列的基础上，还需要有一个地方（车辆规避所）保存为了让路而离开停车场的车辆，很显然这也应该用一个栈来模拟。因此本题中用到两个栈和一个队列对于停车场和车辆贵比索，有车辆经过和离去两个动作，这就是栈的进栈和出栈操作，只是还允许排在中间的车辆先离开停车场，因此在栈中需要进行查找。而对于便道，也有如队列和入队列的操作，同样允许排在中间的车辆先离开队列。这样基本动作只需利用栈和队列的基本操作即可实现。
整个操作过程是：当输入数据表示有车辆到达，则判断栈是否慢，若未满就将新数据进栈（表示新到达的车辆进入停车场的里面），数据应包括车牌号和到达时间；若以满，就将数据放在队尾，表示车辆在便道上等待进入停车场。
当输入数据表示有车辆要离去，就在栈中寻找是否有该车牌号的车辆，如有就让此车辆离开停车场，并根据停车时间记费；如没有找到，就到队列中（便道上）去寻找此车牌号的车辆，如有就允许此车辆离开队列，但不收费；如没有就显示出错信息。
当离开停车场的车辆位于栈的中间时，必须先将此位置到站顶之间的所有数据倒到另一个栈中去（车辆规避所），然后安排车辆出栈，最后将另一个栈中的数据倒回到停车场栈中来。
在模拟停车场管理时，还应注意，如果停车场栈中已没有车辆停放时，输入数据仍然要求车辆退出，则显示出错信息；程序中停车场的停车数量为n，但对便道没有规定，因此认为便道上可以听任意多的车辆。
程序实现根据题目分析的结果，停车场和车辆规避所的栈可以采用顺序栈，而便道可用链队列来模拟。
#define N 2 /*定义停车场栈长度*/
#define M 5 /*M为单元时间的收费值*/
#define True 1
#define False 0
#include,stdio.h”
/*存储结构*/
typedef struct /*定义栈元素的类型*/
{int num;
int arrtime;
}elemtype;
typedef struct /*定义栈*/
{elemtype stack[N];
int top;
}sqstktp;
typedef struct node /*定义队列节点的类型*/
{int num;
struct node *next;
}queueptr;
typedef struct /*定义队列*/
{queueptr *front,*rear;
}linkedquetp;
/*初始化栈*/
void inistack(sqstktp s)
{ s->top= -1;
}
/*压栈，将数据元素x压入指针s所指的栈*/
int push(sqstktp s,elemtype x)
{ if (s->top= =N-1)
return (False); /*如果栈满，返回False*/
else
{ s->stack[++s->top]=x; /*栈不满，x入栈。*/
return (True);
}
}/*push*/
/*弹栈，将栈顶元素出栈*/
elemtype pop (sqstktp *s)
{ elemtype x ;
if (s->top<0)
{ x.num=Null;
x.arrtime=Null;
return (x); /*如果栈空，返回空值*/
}
else
{ s->top - -;
return (s->stack[s->top+1]); /*返回栈顶元素*/
}
}/*pop*/
/*初始化队列*/
void inilinkedque (linkedquetp s)
{ s->fornt= (queueptr )malloc (sizeof (queueptr)); /产生一个新节点，作头节点*/
s->rear= s->fornt;
s->front->next =Null;
s->front->num =0; /*头节点的num保存队列元素的个数*/
}/* nilinkedque */
/*数据入队列*/
void enlinkedque (linkedquetp s,int numl)
{ queueptr *p;
p= (queueptr)malloc (sizeof (queueptr));/*产生一个新节点*/
p->num =numl;
p->next =Null;
s->rear->next=p; /*新节点入队列*/
s->rear=p;
s->front->num++; /*队列元素个数加1*/
}/*enlinkedque*/
/*数据出队列*/
int dllinkedque(linkedquetp s)
{ queueptr *p;
int n;
if (s->front ==s->rear)
return (Null); /*如果队列空，返回空值*/
else
{ p=s->front->next=p->next; /*返回队头元素值*/
if (p->next==Null)
s->rear=s->front;
n=p->num;
free(p);
s->front->num - -; /*队列元素的个数减1*/
return (n);
}
}/*dllinkedque*/
/*处理车辆到达的情况*/
void arrive(sqstktp *sl,linkedquetp *p,elemtype x)
{ int f;
f=push (s1,x); /*新到达的车辆入停车场栈*/
if (f==False)
{ enlinkedque(p,x.num); /*如停车场满，入便道队列*/
printf(“第%d号车停在便道第%d号车位上 \n”,x.num,p->front->num);
}
else /*新到车辆进入停车场*/
printf(“第%d号车停在停车场第%d号车位上\n”,x.num,sl->top+1);
}/*arrive*/
/*处理车辆离去的情况*/
void delive(sqstktp *sl,sqstktp *s2,linkedquetp *p,elemtype x)
{ int n,f=False;
elemtype y;
queueptr *q;
/*在停车场中寻找要离开的车辆*/
while ((sl->top>-1)&&(f!=Ture))
{ y=pop(sl);
if (y.num!=x.num) /*如果栈顶元素不是要离开的车辆，就将其放入车辆规避所*/
n=push(s2,y);
else
f=Ture;
}/*end of while
if (y.num= =x.num) /*在停车场中找到要离开的车辆*/
{ printf(“第%d号车应收费%d元\n”,y.num,(x.arrtime-y.arrtime)*M);
/*车辆规避所不空，将其全部放回停车场*/
while (s2->top>-1)
{ y=pop(s2);
f=push(s1,y); }
n=dllinkedque(p);
/*如便道上有车辆，将第一辆车放入停车场*/
if (n!=Null)
{ y.num=n;
y.arrtime=x.arrtime; /*计费时间为刚离开车辆的离去时间*/
f=push(s1,y);
printf(“第%d号车停在停车场第%d号车位上\n”,y.num,s1->top+1);
}
}/*end the pat one of if
else /*在停车场中没有找到要离开的车辆*/
{ while (s2->top>-1) /*将车辆规避所中的所有车辆放入停车场*/
{ y=pop(s2);
f=push(s1,y);
}
q=p->front;
f=False;
/*在便道上寻找要离开的车辆*/
while (f= =False &&q->next!=Null)
if (q->next->num!=x.num)
q=q->next;
else
/*在便道上找到该车辆*/
{ q->next=q->next->next;
p->fornt->num - -;
if (q->next= =Null)
p->rear=p->front;
printf(“第%d号车离开便道\n”,x.num); /*该车离开便道，但不收费*/
f=Ture;
}
/*在便道上也没找到要离开的车辆，输入数据错误*/
if (f= =False)
printf(“输入数据错误,停车场和便道上均无第%d号车\n”,x.num);
}
}/*delive*/
/*停车场模拟管理程序*/
void main( )
{ char ch1,ch2;
sqstktp *s1,*s2;
linkedquetp *p;
elemtype x;
int flag;
s1=(sqstktp *)malloc(sizeof(sqstktp));
s2=(sqstktp *)malloc(sizeof(sqstktp));
p=(linkedquetp *)malloc(sizeof(linkedquetp));
inistack(s1); /*初始化停车场栈*/
inistack(s2); /*初始化便道队列*/
flag= true;
for(;;)
{printf(“输入数据：‘A’/ ‘D’,车牌号，到达/离开时间\n”);
scanf(“%c %d %d”,&ch1,&x.num,x.arrtime);
ch2=getchar( );
switch (ch1)
{ case ‘A’, arrive(s1,p,x); /*车辆到达*/
break;
case ‘D’, delive(s1,s2,p,x); /*车辆离去*/
break;
case ‘E’,flag=False; /*结束程序运行*/
printf(“程序正常结束\n”);
break;
default,printf(“输入数据错误，重新输入\n”);
}
if (flag = =False) break;
}
}/*main*/
