栈和队列的应用的实验
报告
软件系统测试报告下载sgs报告如何下载关于路面塌陷情况报告535n,sgs报告怎么下载竣工报告下载
栈和队列的应用的实验报告 一、实验目的
1. 掌握队列和栈的顺序存储结构和链式存储结构，并初步学会在实际背景下灵
活运用;
2. 掌握栈和队列的基本运算在两种存储结构上的实现方法; 3. 掌握栈和队列的特点，即FILO 及FIFO的原则。
二、实验内容
1. 停车场管理的模拟;
2. 迷宫问题的模拟。
三、实验要求
1. “停车场管理的模拟”部分
[问题说明] 设有一个可以停放n辆汽车的狭长停车场，它只有一个大门可以供车辆进出。车辆按到达停车场时间的早晚依次从停车场最里面向大门口处停放(最先到达的第一辆车放在停车场的最里面)。如果停车场已放满n辆车，则后到达的车辆只能在停车场大门外的便道上等待，一旦停车场内有车开走，则排在便道上的第一辆车就进入停车场。停车场内如果有某辆车要开走，在它之后进入停车场的车辆都必须先退出停车场(进入规避所)为它让道，待其开出停车场后，这些车辆再依原来的次序进场。每辆车在离开停车场时，都应根据它在停车场内停留的时间长短交纳停车费。如果停留在便道上的车辆没有进入停车场就要离去，则允许其离去，不收停车费，并且仍然保持在便道上等待车辆的次序。编制一程序模拟停车场的管理。
[基本要求] 程序能输出每辆车到达后的停车位置(停车场/便道)，每辆车离开停车场时应交纳的费用。
1.编译并运行:
输入数据:'A'/'D',车牌号，到达时间/离开时间
E---退出。
输入数据:'A'/'D',车牌号，到达时间/离开时间
E---退出。
A,2120,6 <回车>
第2120号车停在停车场的第1号车位上
Press any key to continue...<回车>
输入数据:'A'/'D',车牌号，到达时间/离开时间
E---退出。
A,8761,11<回车>
Stack Overflow!
第8761号车停在便道的第1号车位上
Press any key to continue...
输入数据:'A'/'D',车牌号，到达时间/离开时间
E---退出。
A,2110,7<回车>
第2110号车停在停车场的第2号车位上
Press any key to continue...
<回车>
输入数据:'A'/'D',车牌号，到达时间/离开时间
E---退出。
A,4153,8<回车>
第4153号车停在停车场的第3号车位上
Press any key to continue...
<回车>
输入数据:'A'/'D',车牌号，到达时间/离开时间
E---退出。
A,5154<回车>
第5354号车停在停车场的第4号车位上
Press any key to continue...
<回车>
2.分析程序(注:该程序的Delive函数有错误，已将更改后的程序覆盖到原程序上)
#define N 4 /* 声明停车场n为4*/ #define M 5 /* 收费单价*/ #define True 1
#define False 0
#define Null 0
#include
#include
#include
typedef struct element {
int num;
int arrtime; /*定义到达时间*/ } ElemType; /* ElemType代
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
一个新类型名，代表上面指定的一个结构体类型。这是就可以用ElemType定义变量*/
typedef struct stacktag {
ElemType stack[N];
int top;
} STACK; /* STACK代表一个新类型名，代表上面指定的一个结构体类型。这是就可以用STACK定义变量*/
typedef struct nodetag {
int num;
struct nodetag *next;
} QUEUE; /* QUEUE代表一个新类型名，代表上面指定的一个结构体类型。这是就可以用QUEUE定义变量*/
typedef struct queuetag {
QUEUE *front,*rear; /“定义队头指针*front, 队尾指针*rear ”/
}LinkedQueTp; /* LinkedQueTp代表一个新类型名，代表上面指定的一个结构体类型。这是就可以用LinkedQueTp定义变量*/
void IniStack(STACK *s); /*定义STACK *s 表示s为指向STACK结构体类型数据的指针，初始化栈*/
int Push(STACK *s,ElemType x); ElemType Pop(STACK *s);
/*初始化队列*/ void IniLinkedQue(LinkedQueTp *s);
void EnLinkedQue(LinkedQueTp *s,int num1);
int DeLinkedQue(LinkedQueTp *s); /*删除队列*/ void Arrive(STACK *s1,LinkedQueTp *p,ElemType x); /*到达*/
/*离开*/ void Delive(STACK *s1,STACK *s2,LinkedQueTp *p,ElemType x);
void IniStack(STACK *s) /*初始化栈*/ {
s->top=-1; /*定义为空栈*/
return;
}
int Push(STACK *s,ElemType x) 问:/*压栈函数(完成进栈操作,,)*/
{
if(s->top==N-1) /*判断队是否为满*/
{
printf("\nStack Overflow!\n");
return (False); } /*返回“错误”，即返回“0”
值*/
else {
s->top++; /*指针s后移*/
s->stack[s->top]=x; /*把s->top中的值赋给stack[],并把数据域
的值定为x */
return (True); }
}/* Initialize Stack */
ElemType Pop(STACK *s) /*弹栈函数*/
{
ElemType x;
int i;
if(s->top<0) { 问题:/*判断栈是否为空,*/
x.num=Null;
x.arrtime=Null; /*不计入车辆入栈时间*/
return (x); }
else {
s->top--; /*指针从栈顶下移(后进先出)*/
i=s->top+1; /*用i记录移动前指针s的位置*/
x=s->stack[i]; /*将该位置的数据给x(完成出栈，即所谓的删除车辆工作)*/
return x;}
} /* Pop */
void IniLinkedQue(LinkedQueTp *s) {
QUEUE *p1;
>front=(QUEUE *)malloc(sizeof(QUEUE)); /*为s指针开辟一个新结点*/ s-
s->rear=s->front;
p1=s->front; /*p1指向栈顶*/
>next=Null; /* 头结点指针域初始化(定义为空栈)*/ p1-
p1->num=0; /*头结点数据域初始化 */ }/* IniLinkedQue */
void EnLinkedQue(LinkedQueTp *s,int num1)/*数据入队列(链接式循环队列)*/
{ QUEUE *p,*p1;
p=(QUEUE *)malloc(sizeof(QUEUE)); /* 产生一个新节点 */
p->num=num1; /* 加入数据 */
p->next=Null; /*下一个为零 */
p1=s->rear; /* 加入队尾 */(在这里我觉得p1可以删除。等同于s->rear->next=p,即结构体指针s中rear成员的指针域等于p,为尾插法，)
p1->next=p; /* 加入*/
s->rear=p; /将p指针移动到s->rear,完成尾插/
p1=s->front;
p1->num++; /* 修改保存在头结点数据域中的车辆数*/ }
/* EnLinkedQue */
int DeLinkedQue(LinkedQueTp *s) {/* 数据节点出队列 */
QUEUE *p;
int n;
if(s->front==s->rear) return (Null); /*若队列为空，则返回空*/
else {
p=s->front->next; /* p是第1个节点*/
s->front->next=p->next; /* 将p指针指向的节点中的数据取出 */
if(p->next==Null) /* 若仅有一个节点，则直接删除*/
s->rear=s->front;
n=p->num; /* 存储取出的数据，即头指针和尾指针画在一个节点里，表示此时链队列为空*/
free(p); /* 释放单元*/
s->front->num--; /* 队列个数减一*/
return (n); } /* 返回取出的数据，即车牌号*/ } /* DeLinkedQue */
void Arrive(STACK *s1,LinkedQueTp *p,ElemType x) /*车辆到达处理*/ {
int f;
f=Push(s1,x); /*新到车辆进入停车场栈。在栈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,s1->top+1);
}
} /* Arrive */
void Delive(STACK *s1,STACK *s2,LinkedQueTp *p,ElemType x)
{
int n,f=False;
ElemType y,z; /* 增加z */
QUEUE *q;
while((s1->top>-1) && (f!=True))/*循环条件:栈中有数据并且没找到那辆要出来的车*/
{/* 在停车场中寻找要离开的车辆 */
y=Pop(s1);/*弹出数据*/
if(y.num!=x.num) /* 如果栈顶元素不是要离开的车辆,就将其放如车辆规闭所*/
n=Push(s2,y);/*压不离开的车辆入规避所*/
else f=True;/*找到要离开的车辆，此时y.num==x.num*/
}
/******/
/*规避所的车辆回原位*/
while(s2->top>-1)
{ /* 将y改为z ，不能改变Y因为里面存着要离开的车辆*/
z=Pop(s2);/*规避所的车辆出栈*/
f=Push(s1,z);/*再次进入停车场*/
}
if(y.num==x.num) /*在停车场中找到要离开的车辆*/
{
printf("第%d号车应收费%d元",y.num,(x.arrtime-y.arrtime)*M);
/*规避所的车辆回原位*/
while(s2->top>-1)
{ /* 将y改为z ，不能改变Y因为里面存着要离开的车辆*/
z=Pop(s2);/*规避所的车辆出栈*/
f=Push(s1,z);/*再次进入停车场*/
}/*规避所的车辆全部回原位后*/
n=DeLinkedQue(p);/*车出便道队列 */
if(n!=Null)
*/ { /* 有车在便道队列中等待
y.num=n;/*存入车牌号*/
y.arrtime=x.arrtime; /*存入到达时间*/
f=Push(s1,y); /*进入停车场*/
printf("第%d号车停在停车场第%d号车位上\n",y.num,s1->top+1);
/*打印一下有车进入*/
}
}
else
{ /*在停车场中没有找到要离开的车辆，说明在便道 */
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->front->num--;
if(q->next==Null) p->rear=q; /* =p->front是错误的 */
printf("第%d号车离开便道\n",x.num);/*该车离开便道,但不收费*/
f=True;
}
}
}
if(f==False) printf("输入数据错误,停车场和便道上均无第%d号车\n",x.num);
}
void main() { /* 停车场模拟管理程序 */
char ch1,ch2; STACK *s1,*s2; /* 定义两个栈，一个停车场，一个规避所 */
LinkedQueTp *p; /* 定义一个便道队列*/
ElemType x;
int flag,t1,t2;
s1=(STACK *)malloc(sizeof(STACK)); /*新建停车场*/
s2=(STACK *)malloc(sizeof(STACK)); /*新建规避所*/
p=(LinkedQueTp *)malloc(sizeof(LinkedQueTp)); /*新建便道队列*/
IniStack(s1); /*初始化停车场栈*/
IniStack(s2); /*初始化车辆规避所栈*/
IniLinkedQue(p); /*初始化便道队列*/
flag=True; /*初始化退出旗帜*/
for(;;) {
clrscr();
printf("\n输入数据:'A'/'D',车牌号，到达时间/离开时间\n");
\n"); printf("E---退出。
scanf("%c,%d,%d",&ch1,&t1,&t2);
x.num=t1;
x.arrtime=t2; /* 只记录小时值，没有考虑分钟 */
ch2=getchar(); /* 清空输入缓冲区 */
switch(ch1) {
case 'a': /*加入车辆*/
case 'A': Arrive(s1,p,x); /*调用加入函数*/
printf("\nPress any key to continue...\n");
getch();
break;
case 'd': /*删除车辆*/
case 'D': Delive(s1,s2,p,x); /*调用删除车辆函数*/
printf("\nPress any key to continue...\n");
getch();
break;
case 'e': /*退出程序*/
case 'E': flag=False;
printf("\n程序正常结束\n");
break;
default: printf("\n输入数据错误，重新输入\n");
printf("\nPress any key to continue...\n");
getch();
break;
}
if(flag==False) break; /* 退出循环 */
}
return;
}
思考:该停车场管理系统程序与现实生活中的停车场有一些区别。其使用价值有些令人质疑。比如对时间的计算(如果单纯的计入小时数，如果一辆车9:00pm. 进的而第二天8:00am.出的停车场，其缴纳的费用就会有错误。)
思考题如何改进“停车场管理模拟程序”的设计，使每辆车到达及离开的时间可以人们习惯的方式输入,如果用数据库系统来做这一模拟工作，如何设计, 先自定义一个函数，读入到达离开的小时、分钟。
分钟换算成小时的小数，小时、分钟相加， 用单价*分钟=费用。
2. “迷宫问题的模拟”部分
[问题说明] 模拟心理学实验中老鼠对仅有一入口和一个出口的迷宫找出路的过程。
基本要求] 设计一程序对任意设定的迷宫，求出一条从入口到出口的路线，[
或得出没有可行通路的结论。
#define M2 12 /*以下均为声明*/
#define N2 11
#define MAXLEN M2
#define True 1
#define False 0
#define Null 0
#include
#include
#include
#include
int M=M2-2,N=N2-2;
typedef struct elem {
int x,y,dir;
} ElemType; /*定义一个结构体类型*/
typedef struct stktag {
ElemType stack[MAXLEN];
int top;
} STACK;
typedef struct moved {
int dx,dy;
}MOVE;
void IniMaze(int maze[][N2]); /*初始化迷宫*/
void IniMove(MOVE move[]); void IniStack(STACK *s);
int Push(STACK *s,ElemType x);
ElemType Pop(STACK *s);
void path(int maze[][N2],MOVE move[],STACK *s);
void draw(int maze[][N2],STACK *s);
void main() { /*主函数*//* 寻找迷宫通路程序*/
STACK *s;
int maze[M2][N2];
MOVE move[8];
IniMaze(maze); /* 初始化迷宫数组 */
getch();
s=(STACK *)malloc(sizeof(STACK)); /*创建一个栈，开辟新结点*/
IniStack(s); /*初始化栈*/
IniMove(move); /*初始化移动函数*/
path(maze,move,s); /*调用路径函数，寻找路径，并存储在栈s里*/
draw(maze,s); /*用“*”显示迷宫通路*/ getch();} „„„为原样本程序的一个错误。由于没有该句，导致运行时屏幕显示的不全。
void IniMaze(int maze[][N2]) { /*初始化迷宫*/
int i,j,num;
for(i=0,j=0;i<=M+1;i++) maze[i][j]=1;/*构建迷宫第一列，用数字1代表墙壁*/
for(i=0,j=N+1;i<=M+1;i++) maze[i][j]=1/*构建迷宫第11列，用数字1代表墙壁*/
;
for(i=0,j=0;j<=N+1;j++) maze[i][j]=1; /*构建迷宫第1行，用数字1代表墙壁*/
for(i=M+1,j=0;j<=N+1;j++) maze[i][j]=1; /*构建迷宫第12行，用数字1代表墙壁*/
for(i=1;i<=M;i++) {
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; /*在迷宫内部填满“0”或“1”来将迷宫构建完善*/
}
}
printf("\n");
for(i=0;i<=M+1;i++) {
printf("\n");
for(j=0;j<=N+1;j++) {
if((i==0)&&(j==0)||(i==M+1)&&(j==N+1)) printf("%3d",0);/*显示迷宫的出口和入口*/
/*将迷宫的图示整个完整的输出 else printf("%3d",maze[i][j]); }*/
}
}/* IniMaze */
void IniMove(MOVE move[]) /*设置移动函数表示8个方向*/ {
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(STACK *s) /*初始化栈*/ {
s->top=-1;
}/* IniStack */
int Push(STACK *s,ElemType x) /*压栈函数*/ {
if(s->top==MAXLEN-1) return (False);
else {
s->stack[++s->top]=x;
return (True); } }
/* Push */
ElemType Pop(STACK *s) /*弹栈*/
{
ElemType elem;
if(s->top<0) {
elem.x=Null; /*栈空时，返回NULL，栈非空，返回一个值*/
elem.y=Null;
elem.dir=Null;
return (elem);
}
else {
s->top--; /*STACK形指针s指向该结构体内成员top,再移动s*/
>top+1]); }/*将s指向的成员中的值*/ return (s->stack[s-
}/* pop */
void path(int maze[][N2],MOVE move[],STACK *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 { /* 8个方向都不可行,就退回一步 */
elem=Pop(s);
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迷宫的通路是:\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],STACK *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;
while(s->top>-1) {
elem=Pop(s);
i=elem.x; j=elem.y;
maze[i][j]=8;/*将通路用8表示*/ }
for(i=0;i<=M+1;i++) {
for(j=0;j<=N+1;j++) {
if((i==0)&&(j==0)||(i==M+1)&&(j==N+1)) printf("%3d",0);
else if(maze[i][j]==8) printf(" %c",'*');/*用“*”代替8，来表示迷宫通路*/
else printf("%3d",maze[i][j]); /* 显示已标记通路的迷宫 */
}
printf("\n");
}
printf("\n");
}/* draw */
思考题“迷宫模拟”中程序是如何记住可行线路的, 用栈记住，栈有先进后出的性质,利用这个特点记住线路。
思考:以上为迷宫程序，使用了栈思想，而下面的程序用了“队列”
的思想，运用了“先进先出”的思想。可以表达同样的效果。由于两程序有许多
相似之处，所以注释处有省略。
“迷宫问题的最短线路”部分
1) 编译并运行样本程序;显示屏上出现:
0 1 1 1 1 1 1 1 1 1 1
1 0 0 1 0 1 0 1 0 1 1
1 0 1 0 1 0 1 0 1 0 1
1 1 0 1 0 1 0 1 0 0 1
1 0 1 0 1 0 1 0 0 1 1
1 1 0 1 0 1 0 0 1 0 1
1 0 1 0 1 0 0 1 0 1 1
1 1 0 1 0 0 1 0 1 0 1
1 0 1 0 0 1 0 1 0 1 1
1 1 0 0 1 0 1 0 1 0 1
1 0 0 1 0 1 0 1 0 0 1
1 1 1 1 1 1 1 1 1 1 0
迷宫中的最短通路是:
(1,1)-->(1,2)-->(2,3)-->(3,4)-->4,5)-->(5,6)-->(6,6
)-->(7,7)-->(8,8)-->(9,9)-->(10,9)
* 1 1 1 1 1 1 1 1 1 1 1 * * 1 0 1 0 1 0 1 1 1 0 1 * 1 0 1 0 1 0 1 1 1 0 1 * 1 0 1 0 0 1 1 0 1 0 1 * 1 0 0 1 1 1 1 0 1 0 1 * 0 1 0 1 1 0 1 0 1 0 * 1 0 1 1 1 1 0 1 0 0 1 * 1 0 1 1 0 1 0 0 1 0 1 * 1 1 1 1 0 0 1 0 1 0 1 * 1 1 0 0 1 0 1 0 1 0 * 1
1 1 1 1 1 1 1 1 1 1 *
2.分析程序
#define M2 12
#define N2 11
#define MAXLEN M2*N2
#define True 1
#define False 0
#define Null 0
#include
#include #include #include
int M=M2-2,N=N2-2;
定义栈元素的数据类型 */ typedef struct elem { /*
int x,y;
int dir;
} ElemType;
typedef struct stktag { /* 定义顺序栈结构 */
ElemType stack[MAXLEN];
int top;
} STACK;
typedef struct QueEle { /* 定义队列元素的数据类型 */
int x,y;
int pre;
} QueElem;
typedef struct QueTag {
QueElem queue[MAXLEN];
int front,rear;
} QUEUE;
typedef struct moved { /* 定义方向位移数组元素的类型 */
int dx,dy;
} MOVE;
void IniMaze(int maze[][N2]); /*初始化迷宫*/ void IniMove(MOVE move[]); void IniStack(STACK *s); int Push(STACK *s,ElemType x);
ElemType Pop(STACK *s);
int shortpath(int maze[][N2],MOVE move[],QUEUE *p);
void draw(int maze[][N2],STACK *s); void IniQueue(QUEUE *s); /* 初始化队列 */
void printpath(QUEUE *p,STACK *s); /* 显示迷宫通路 */
void main() { /* 寻找迷宫通路程序*/
STACK *s;
QUEUE *p;
int maze[M2][N2],f;
MOVE move[8];
IniMaze(maze); /* 初始化迷宫数组 */
getch();
s=(STACK *)malloc(sizeof(STACK));
IniStack(s);
p=(QUEUE *)malloc(sizeof(QUEUE));
初始化队列 */ IniQueue(p); /*
IniMove(move); /* 初始化位移方向数组*/
f=shortpath(maze,move,p); /* 寻找迷宫中的一条最短路径 */
if(f==True) {
printpath(p,s); /**/
draw(maze,s); }
else printf("\n此迷宫无通路\n"); /* 如果没找到，显示"无通路" */
getch();
}/* main */
void IniMaze(int maze[][N2]) { /*初始化迷宫*/
int i,j,num;
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;
for(i=1;i<=M;i++) {
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; }
}
for(i=0;i<=M+1;i++) {
printf("\n");
for(j=0;j<=N+1;j++) {
if((i==0)&&(j==0)||(i==M+1)&&(j==N+1)) printf("%3d",0);
else printf("%3d",maze[i][j]); }
}
printf("\n");
} /* IniMaze */
void IniMove(MOVE move[]) { 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; }
void IniStack(STACK *s) {
s->top=-1;
} /* IniStack */
int Push(STACK *s,ElemType x) { /*数据元素x进入s指针所指的栈 */
栈满处理 */ if(s->top==MAXLEN-1) /*
return (False);
else { /* 进栈 */
s->stack[++s->top]=x;
return (True); }
} /* End of Push */
ElemType Pop(STACK *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(QUEUE *s) { /* 初始化队列 */
s->front=1; /*设置队头在数组下标为1处 */
s->rear=1;
return;
}
int shortpath(int maze[][N2],MOVE move[],QUEUE *p) {
int i,j,dir,x,y,f;
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; /* i,j 为出发点 */
j=p->queue[p->front].y;
for(dir=0;dir<8;dir++) { /* 寻找从[i][j]出发, 8个方向中有哪些点可到达 */
x=i+move[dir].dx;
y=j+move[dir].dy;
if(maze[x][y]==0) { /* 如有可到达点，将此点坐标入对列 */
p->rear++;
>queue[p->rear].x=x; p-
>queue[p->rear].y=y; p-
p->queue[p->rear].pre=p->front;
maze[x][y]=-1; /* 设置此点已到达标志 */
}
if((x==M)&&(y==N)) /* 如到达出口，返回True */
return (True);
}
p->front++; /*队头指针指向下一个队列元素 */
}
return (False);
}/* shortpath */
void printpath(QUEUE *p,STACK *s) { /* 显示迷宫通路 */
int i,f;
ElemType elem;
i=p->rear;
do { /* 从队列中取出最短的迷宫通路放入栈中 */
elem.x=p->queue[i].x;
elem.y=p->queue[i].y;
f=Push(s,elem);
if(f==False) /* 如果f为假,说明栈太短，不能再次加入元素(满) */
printf("\n栈长度太短\n");
i=p->queue[i].pre;
} while(i>0);
printf("\n 迷宫中的最短通路是:\n");
i=s->top;
while(i>-1) {
printf("(%d,%d)",s->stack[i].x,s->stack[i].y);
if(i>0) printf("-->");
if((s->top-i+1)%4==0) /* 每四个点占一行 */
printf("\n");
i--; }
printf("\n");
}/* printpath */
void draw(int maze[][N2],STACK *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; }
while(s->top>-1) { /* 根据栈中元素的坐标,将通路的各个点的值改为8 */
elem=Pop(s);
i=elem.x; j=elem.y;
maze[i][j]=8; }
for(i=0;i<=M+1;i++) {
for(j=0;j<=N+1;j++) {
if((i==0)&&(j==0)||(i==M+1)&&(j==N+1)) printf(" %c",'*');
else if(maze[i][j]==8) printf(" %c",'*');
else printf("%3d",maze[i][j]); /* 显示已标记通路的迷宫 */
}
printf("\n");
}
printf("\n");
}/* draw */
浙公网安备 33021202002483