栈队列实验.docx
- 文档编号:262132
- 上传时间:2023-04-28
- 格式:DOCX
- 页数:23
- 大小:119.64KB
栈队列实验.docx
《栈队列实验.docx》由会员分享,可在线阅读,更多相关《栈队列实验.docx(23页珍藏版)》请在冰点文库上搜索。
栈队列实验
福州大学数计学院
《数据结构》上机实验报告
专业:
信息与计算科学
学号
031201206
姓名
詹小青
班级
02班
实验名称
栈、队列结构及其应用
实验内容
栈、队列结构及其应用---基本操作
实
验
目
的
和
要
求
【背景知识】
入栈、出栈,入队、出队。
【目的要求】
1.掌握栈、队列的结构特点及结构实现方法。
2.掌握栈、队列的常见算法的程序实现并能运用。
【实验主要内容】
运用栈和队列的结构,完成基本操作算法的实现,并自选以下题目来实现:
1、迷宫问题
2、算术表达式求值演示
问
题
描
述
和
主
要
步
骤
一、栈与队列基本算法的实现
【实验目的】
1.掌握栈、队列的思想及其存储实现。
2.掌握栈、队列的常见算法的程序实现。
【实验内容】
1.采用链式存储实现栈的初始化、入栈、出栈操作。
2.采用顺序存储实现栈的初始化、入栈、出栈操作。
3.采用链式存储实现队列的初始化、入队、出队操作。
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
#include
#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;
returnOK;
}
StatusPop(SqStack&s,SelemType&e)//出栈
{
if(s.top==s.base)
returnERROR;
e=*--s.top;
returnOK;
}
//链式栈的基本操作
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;
returnOK;
}
StatusPushLStack(LinkLStackls,SelemType&e)//入栈
{
LinkLStackl;
l=(LinkLStack)malloc(sizeof(Lstack));
if(!
l)
exit(OVERFLOW);
printf("请输入入栈元素e=");
scanf("%d",&e);
l->data=e;
l->next=ltop->next;
ltop->next=l;
ls=ltop;
returnOK;
}
StatusPopLStack(LinkLStackls,SelemType&e)//出栈
{
LinkLStackp;
p=ltop->next;
if(p!
=NULL)
{
e=p->data;
ltop->next=p->next;
free(p);
returnOK;
}
else
returnERROR;
}
//顺序队列的基本操作
typedefstructQueue{
QElemType*base;
intfront;
intrear;
}SqQueue;
StatusInitQueue(SqQueue&Q)
{
Q.base=(QElemType*)malloc(MAXQSIZE*sizeof(QElemType));
if(!
Q.base)
exit(OVERFLOW);
Q.front=Q.rear=0;
returnOK;
}
StatusEnQueue(SqQueue&Q,QElemTypee)
{
if((Q.rear+1)%MAXQSIZE==Q.front)
returnERROR;
Q.base[Q.rear]=e;
Q.rear=(Q.rear+1)%MAXQSIZE;
returnOK;
}
StatusDeQueue(SqQueue&Q,QElemType&e)
{
if(Q.front==Q.rear)
returnERROR;
e=Q.base[Q.front];
Q.front=(Q.front+1)%MAXQSIZE;
returnOK;
}
//以下是链式队列的操作
typedefstructQNode
{
QElemTypedata;
structQNode*next;
}QNode,*QueuePtr;
typedefstruct
{
QueuePtrfront;
QueuePtrrear;
}LinkQueue;
StatusInitQueue(LinkQueue&Q)//初始化
{
Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));
if(!
Q.front)
exit(OVERFLOW);
Q.front->next=NULL;
returnOK;
}
StatusEnQueue(LinkQueue&Q,QElemTypee)//入队列
{
QueuePtrp;
p=(QueuePtr)malloc(sizeof(QNode));
if(!
p)
exit(OVERFLOW);
p->data=e;
p->next=NULL;
Q.rear->next=p;
Q.rear=p;
returnOK;
}
StatusDeQueue(LinkQueue&Q,QElemType&e)//出队列
{
QueuePtrp;
if(Q.front==Q.rear)
returnERROR;
p=Q.front->next;
e=p->data;
Q.front->next=p->next;
if(Q.rear==p)
Q.rear=Q.front;
free(p);
returnOK;
}//以下控制打印菜单
voidprint()
{
printf("操作菜单如下:
\n");
printf("1.采用链式存储实现栈的初始化、入栈、出栈操作\n");
printf("2.采用顺序存储实现栈的初始化、入栈、出栈操作\n");
printf("3.采用链式存储实现循环队列的初始化、入队、出队操作\n");
printf("4.采用顺序存储实现循环队列的初始化、入队、出队操作\n");
printf("0.退出操作。
\n");
printf("请输入要操作的数字:
");
}
voidprint1()
{
printf("采用链式存储实现栈操作菜单如下:
\n");
printf("1.初始化\n");
printf("2.入栈\n");
printf("3.出栈\n");
printf("0.退出。
\n");
printf("请输入要操作的数字:
");
}
voidprint2()
{
printf("采用顺序存储实现栈操作菜单如下:
\n");
printf("1.初始化\n");
printf("2.入栈\n");
printf("3.出栈\n");
printf("0.退出。
\n");
printf("请输入要操作的数字:
");
}
voidprint3()
{
printf("采用链式存储实现循环队列操作菜单如下:
\n");
printf("1.初始化\n");
printf("2.入栈\n");
printf("3.出栈\n");
printf("0.退出。
\n");
printf("请输入要操作的数字:
");
}
voidprint4()
{
printf("采用顺序存储实现循环队列操作菜单如下:
\n");
printf("1.初始化\n");
printf("2.入栈\n");
printf("3.出栈\n");
printf("0.退出。
\n");
printf("请输入要操作的数字:
");
}
intmain()
{
print();
intncase,n1,n2,n3,n4;
boolflag=true;
boolf1,f2,f3,f4;
SqStacks;
LinkLStackls;
SqQueueQ;
LinkQueueLQ;
inte;
while(scanf("%d",&ncase)!
=EOF)
{
f1=true;
f2=true;
f3=true;
f4=true;
switch(ncase)
{
case1:
print1();
IniLStack(ls);
while(scanf("%d",&n1)!
=EOF)
{
switch(n1)
{
case1:
if(IniLStack(ls))
printf("链式栈建立成功!
\n");
else
printf("链式栈建立失败!
\n");
break;
case2:
if(PushLStack(ls,e))
printf("入栈成功!
\n");
else
printf("入栈失败!
\n");
break;
case3:
if(PopLStack(ls,e))
printf("e=%d出栈成功!
\n",e);
else
printf("栈为空!
\n");
break;
case0:
f1=false;
break;
default:
printf("输入有误,请重新输入!
\n");
break;
}
if(!
f1)
break;
print1();
}
break;
case2:
print2();
while(scanf("%d",&n2)!
=EOF)
{
switch(n2)
{
case1:
if(Initack(s))
printf("顺序栈建立成功!
\n");
else
printf("顺序栈建立失败!
\n");
break;
case2:
if(Push(s,e))
printf("入栈成功!
\n");
else
printf("入栈失败!
\n");
break;
case3:
if(!
Pop(s,e))
printf("顺序栈为空!
\n");
else
printf("e=%d出栈成功!
\n",e);
break;
case0:
f2=false;
break;
default:
printf("输入有误,请重新输入!
\n");
break;
}
if(!
f2)
break;
print2();
}
break;
case3:
print3();
while(scanf("%d",&n3)!
=EOF)
{
switch(n3)
{
case1:
if(InitQueue(LQ))
printf("链式队列构造成功!
\n");
else
printf("链式队列构造失败!
\n");
break;
case2:
printf("请输入队列元素e=");
scanf("%d",&e);
if(EnQueue(LQ,e))
printf("链式队列入列成功!
\n");
else
printf("链式队列入列失败!
\n");
break;
case3:
if(DeQueue(LQ,e))
printf("e=%d出队列成功!
\n",e);
else
printf("队列为空!
\n");
break;
case0:
f4=false;
break;
default:
printf("输入有误,请重新输入!
\n");
break;
}
if(!
f4)
break;
print4();
}
break;
case4:
print4();
while(scanf("%d",&n4)!
=EOF)
{
switch(n4)
{
case1:
if(InitQueue(Q))
printf("顺序队列初始化成功!
\n");
else
printf("顺序队列初始化失败!
\n");
break;
case2:
printf("请输入队列元素e=");
scanf("%d",&e);
if(EnQueue(Q,e))
printf("插入队列成功!
\n");
else
printf("插入失败!
\n");
break;
case3:
if(DeQueue(Q,e))
printf("e=%d出队列成功!
\n",e);
else
printf("队列为空!
\n");
break;
case0:
f3=false;
break;
default:
printf("输入有误,请重新输入!
\n");
break;
}
if(!
f3)
break;
print3();
}
break;
case0:
flag=false;
break;
default:
printf("输入错误,请重新输入,谢谢!
\n");
break;
}
if(!
flag)
break;
print();
}
return0;
}
实验结果截图:
2、利用栈实现迷宫求解
实验程序:
#include
#include
usingnamespacestd;
#defineM20
#defineN20
structmove{intdx,dy;};
movemazemove[8];
charma[M][N];
intFalse=0;
voidmaze()
{inti,j,num;
for(i=1;i {for(j=1;j {num=(800*(i+j)+1500)%327; if((num<156)&&(i! =M||j! =N)) ma[i][j]='1'; else ma[i][j]='0'; } } ma[1][1]='0'; ma[M-2][N-2]='0'; for(i=0;i {for(j=0;j cout< cout< } } 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]=='0'){k=0;break;} } if(k! =8) {if(ma[i][j]=='8')ma[i][j]='2'; if(ma[i][j]=='0')ma[i][j]='>'; i=x;j=y; } else {for(k=0;k<8;k++) {x=i+mazemove[k].dx; y=j+mazemove[k].dy; if(ma[x][y]=='8')break; } ma[i][j]='2'; i=x;j=y; } if((i==1)&&(j==1)) {False=0; break; } elseFalse=1; } } intmain() {inti,j; maze(); inimove(); outpath(); cout< if(False==0) cout<<"无法走出该迷宫! "< else {cout<<"走出迷宫的路径(用‘>’符号表示)为: "< ma[M-2][N-2]='>'; for(i=0;i {for(j=0;j {{if(ma[i][j]=='2')ma[i][j]='>'; if(ma[i][j]=='0')ma[i][j]=''; if(ma[i][j]=='1')ma[i][j]='*'; } cout< } cout< } } return0; } 实验结果截图: 研 究 与 探 讨 1、主要问题出在如何看到已经插入的结点的数据域,所以构造了逐个”读取头结点”的操作; 2、做连续插入操作时,要改变的是尾指针的指向,而不是头指针;虽然初始状态下头指针和尾指针都指向头结点,所以做第一个插入时关系不大,但第二次开始就一定要改变尾指针; 3、出队操作时,要考虑除了头结点外,只有一个结点的情况。 删去一个结点后就剩下一个头结点了。 说明: 实验名称为教学大纲中各章的实验项目名称,实验内容
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 队列 实验