栈队列实验Word格式.docx
《栈队列实验Word格式.docx》由会员分享，可在线阅读，更多相关《栈队列实验Word格式.docx（23页珍藏版）》请在冰点文库上搜索。
4．采用顺序存储实现循环队列的初始化、入队、出队操作。
二、利用栈实现迷宫求解
应用栈结构来解决应用问题，加深对栈结构特点的认识和应用。
【问题描述】
以一个mn的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。
设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论
【基本要求】
首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。
求得的通路以三元组（i,j,d）的形式输出，其中：
（i,j）指示迷宫中的一个坐标，d表示走到下一坐标的方向。
如:
对于下列数据的迷宫，输出的一条通路为;
（1,1,1）,（1,2,2）,（2,2,2）,（3,2,3）,（3,1,2）,....
结
果
（
截
图
表
示
）
1、栈与队列基本算法的实现
程序代码：
#include<
stdio.h>
stdlib.h>
#defineOK1
#defineERROR0
#defineOVERFLOW-2
#defineSTACK_INIT_SIZE100
#defineSTACKINSREMENT10
#defineMAXQSIZE100
typedefintSelemType,Status,QElemType;
//以下是顺序存储栈的操作
typedefstructStack//定义结构体
{
SelemType*base;
SelemType*top;
intstacksize;
}SqStack;
StatusInitack（SqStack&
s）//初始化链式栈
s.base=（SelemType*）malloc（STACK_INIT_SIZE*sizeof（SelemType））;
if（!
s.base）
exit（OVERFLOW）;
s.top=s.base;
s.stacksize=STACK_INIT_SIZE;
returnOK;
}
StatusPush（SqStack&
s,SelemTypee）//入栈
if（s.top-s.base>
=s.stacksize）
{
s.base=（SelemType*）realloc（s.base,（s.stacksize+STACKINSREMENT）*sizeof（SelemType））;
if（!
s.base）
exit（OVERFLOW）;
s.top=s.base+STACKINSREMENT;
s.stacksize+=STACKINSREMENT;
}
printf（"
请输入入栈元素e="
）;
scanf（"
%d"
&
e）;
*s.top++=e;
StatusPop（SqStack&
s,SelemType&
e）//出栈
if（s.top==s.base）
returnERROR;
e=*--s.top;
//链式栈的基本操作
typedefstructLStack
SelemTypedata;
structLStack*next;
}Lstack,*LinkLStack;
LinkLStackltop,lbase;
StatusIniLStack（LinkLStackls）//初始化
ls=（LinkLStack）malloc（sizeof（Lstack））;
ls->
next=NULL;
//ls->
data=0;
ltop=ls;
lbase=ls;
StatusPushLStack（LinkLStackls,SelemType&
e）//入栈
LinkLStackl;
l=（LinkLStack）malloc（sizeof（Lstack））;
l）
l->
data=e;
next=ltop->
next;
ltop->
next=l;
ls=ltop;
StatusPopLStack（LinkLStackls,SelemType&
LinkLStackp;
p=ltop->
if（p!
=NULL）
e=p->
data;
ltop->
next=p->
free（p）;
returnOK;
else
//顺序队列的基本操作
typedefstructQueue{
QElemType*base;
intfront;
intrear;
}SqQueue;
StatusInitQueue（SqQueue&
Q）
Q.base=（QElemType*）malloc（MAXQSIZE*sizeof（QElemType））;
Q.base）
Q.front=Q.rear=0;
StatusEnQueue（SqQueue&
Q,QElemTypee）
if（（Q.rear+1）%MAXQSIZE==Q.front）
Q.base[Q.rear]=e;
Q.rear=（Q.rear+1）%MAXQSIZE;
StatusDeQueue（SqQueue&
Q,QElemType&
e）
if（Q.front==Q.rear）
e=Q.base[Q.front];
Q.front=（Q.front+1）%MAXQSIZE;
//以下是链式队列的操作
typedefstructQNode
QElemTypedata;
structQNode*next;
}QNode,*QueuePtr;
typedefstruct
QueuePtrfront;
QueuePtrrear;
}LinkQueue;
StatusInitQueue（LinkQueue&
Q）//初始化
Q.front=Q.rear=（QueuePtr）malloc（sizeof（QNode））;
Q.front）
Q.front->
StatusEnQueue（LinkQueue&
Q,QElemTypee）//入队列
QueuePtrp;
p=（QueuePtr）malloc（sizeof（QNode））;
p）
p->
Q.rear->
next=p;
Q.rear=p;
StatusDeQueue（LinkQueue&
e）//出队列
p=Q.front->
e=p->
if（Q.rear==p）
Q.rear=Q.front;
free（p）;
}//以下控制打印菜单
voidprint（）
操作菜单如下：
\n"
1.采用链式存储实现栈的初始化、入栈、出栈操作\n"
2.采用顺序存储实现栈的初始化、入栈、出栈操作\n"
3.采用链式存储实现循环队列的初始化、入队、出队操作\n"
4.采用顺序存储实现循环队列的初始化、入队、出队操作\n"
0.退出操作。
请输入要操作的数字：
"
voidprint1（）
采用链式存储实现栈操作菜单如下：
1.初始化\n"
2.入栈\n"
3.出栈\n"
0.退出。
voidprint2（）
采用顺序存储实现栈操作菜单如下：
voidprint3（）
采用链式存储实现循环队列操作菜单如下：
voidprint4（）
采用顺序存储实现循环队列操作菜单如下：
intmain（）
print（）;
intncase,n1,n2,n3,n4;
boolflag=true;
boolf1,f2,f3,f4;
SqStacks;
LinkLStackls;
SqQueueQ;
LinkQueueLQ;
inte;
while（scanf（"
ncase）!
=EOF）
f1=true;
f2=true;
f3=true;
f4=true;
switch（ncase）
{
case1:
print1（）;
IniLStack（ls）;
while（scanf（"
n1）!
{
switch（n1）
{
case1:
if（IniLStack（ls））
printf（"
链式栈建立成功!
else
链式栈建立失败!
break;
case2:
if（PushLStack（ls,e））
入栈成功!
入栈失败!
case3:
if（PopLStack（ls,e））
e=%d出栈成功!
e）;
栈为空!
case0:
f1=false;
default:
printf（"
输入有误，请重新输入!
}
if（!
f1）
print1（）;
}
break;
case2:
print2（）;
n2）!
switch（n2）
if（Initack（s））
顺序栈建立成功!
顺序栈建立失败!
if（Push（s,e））
if（!
Pop（s,e））
顺序栈为空!
f2=false;
f2）
print2（）;
case3:
print3（）;
n3）!
switch（n3）
if（InitQueue（LQ））
链式队列构造成功!
链式队列构造失败!
请输入队列元素e="
scanf（"
if（EnQueue（LQ,e））
链式队列入列成功!
链式队列入列失败!
if（DeQueue（LQ,e））
e=%d出队列成功!
队列为空!
f4=false;
f4）
print4（）;
case4:
print4（）;
n4）!
switch（n4）
case1:
if（InitQueue（Q））
顺序队列初始化成功!
顺序队列初始化失败!
if（EnQueue（Q,e））
插入队列成功!
插入失败!
if（DeQueue（Q,e））
f3=false;
f3）
print3（）;
case0:
flag=false;
default:
printf（"
输入错误，请重新输入，谢谢!
}
flag）
print（）;
return0;
实验结果截图：
2、利用栈实现迷宫求解
实验程序：
#include<
iostream>
iomanip>
usingnamespacestd;
#defineM20
#defineN20
structmove{intdx,dy;
};
movemazemove[8];
charma[M][N];
intFalse=0;
voidmaze（）
{inti,j,num;
for（i=1;
i<
M-1;
i++）
{for（j=1;
j<
N-1;
j++）
{num=（800*（i+j）+1500）%327;
if（（num<
156）&
&
（i!
=M||j!
=N））
ma[i][j]='
1'
;
else
0'
}
ma[1][1]='
ma[M-2][N-2]='
for（i=0;
M;
{for（j=0;
N;
cout<
<
setw（3）<
ma[i][j];
endl;
}
voidinimove（）
{mazemove[0].dx=0;
mazemove[0].dy=1;
mazemove[1].dx=1;
mazemove[1].dy=1;
mazemove[2].dx=1;
mazemove[2].dy=0;
mazemove[3].dx=1;
mazemove[3].dy=-1;
mazemove[4].dx=0;
mazemove[4].dy=-1;
mazemove[5].dx=-1;
mazemove[5].dy=-1;
mazemove[6].dx=-1;
mazemove[6].dy=0;
mazemove[7].dx=-1;
mazemove[7].dy=1;
voidoutpath（）
{inti,j,x,y,k;
i=1;
j=1;
k=0;
while（（i!
=（M-2））||（j!
=（N-2）））
{for（k=0;
k<
8;
k++）
{x=i+mazemove[k].dx;
y=j+mazemove[k].dy;
if（ma[x][y]=='
）{k=0;
break;
if（k!
=8）
{if（ma[i][j]=='
8'
）ma[i][j]='
2'
if（ma[i][j]=='
>
'
i=x;
j=y;
）break;
if（（i==1）&
（j==1））
{False=0;
break;
elseFalse=1;
intmain（）
{inti,j;
maze（）;
inimove（）;
outpath（）;
if（False==0）
无法走出该迷宫!
{cout<
走出迷宫的路径（用‘>
’符号表示）为:
{{if（ma[i][j]=='
'
*'
return0;
研
究
与
探
讨
1、主要问题出在如何看到已经插入的结点的数据域，所以构造了逐个”读取头结点”的操作；
2、做连续插入操作时，要改变的是尾指针的指向，而不是头指针；
虽然初始状态下头指针和尾指针都指向头结点，所以做第一个插入时关系不大，但第二次开始就一定要改变尾指针；
3、出队操作时，要考虑除了头结点外，只有一个结点的情况。
删去一个结点后就剩下一个头结点了。
说明：
实验名称为教学大纲中各章的实验项目名称，实验内容
升级会员 