栈的操作实验报告.docx
《栈的操作实验报告.docx》由会员分享，可在线阅读，更多相关《栈的操作实验报告.docx（29页珍藏版）》请在冰点文库上搜索。
栈的操作实验报告
（此文档为word格式，下载后您可任意编辑修改！
）
实验三栈和队列
3.1实验目的：
（1）熟悉栈的特点（先进后出）及栈的基本操作，如入栈、出栈等，掌握栈的基本操作在栈的顺序存储结构和链式存储结构上的实现；
（2）熟悉队列的特点（先进先出）及队列的基本操作，如入队、出队等，掌握队列的基本操作在队列的顺序存储结构和链式存储结构上的实现。
3.2实验要求：
（1）复习课本中有关栈和队列的知识；
（2）用C语言完成算法和程序设计并上机调试通过；
（3）撰写实验报告，给出算法思路或流程图和具体实现（源程序）、算法分析结果（包括时间复杂度、空间复杂度以及算法优化设想）、输入数据及程序运行结果（必要时给出多种可能的输入数据和运行结果）。
3.3基础实验
[实验1]栈的顺序表示和实现
实验内容与要求:
编写一个程序实现顺序栈的各种基本运算，并在此基础上设计一个主程序，完成如下功能：
（1）初始化顺序栈
（2）插入元素
（3）删除栈顶元素
（4）取栈顶元素
（5）遍历顺序栈
（6）置空顺序栈
分析:
栈的顺序存储结构简称为顺序栈,它是运算受限的顺序表。
对于顺序栈，入栈时，首先判断栈是否为满，栈满的条件为：
p->top==MAXNUM-1，栈满时，不能入栈;否则出现空间溢出，引起错误，这种现象称为上溢。
出栈和读栈顶元素操作，先判栈是否为空，为空时不能操作，否则产生错误。
通常栈空作为一种控制转移的条件。
注意：
（1）顺序栈中元素用向量存放
（2）栈底位置是固定不变的，可设置在向量两端的任意一个端点
（3）栈顶位置是随着进栈和退栈操作而变化的，用一个整型量top（通常称top为栈顶指针）来指示当前栈顶位置
参考程序:
#include}
*出栈*
ElemTypePop（SqStack*p）
{ElemTypex;
if（p->top!
=0）
{x=p->stack[p->top];
printf（"以前的栈顶数据元素%d已经被删除！
\n",p->stack[p->top]）;
p->top=p->top-1;
return（x）;
}
else
{printf（"Underflow!
\n"）;
return（0）;
}
}
*获取栈顶元素*
ElemTypeGetTop（SqStack*p）
{ElemTypex;
if（p->top!
=0）
{x=p->stack[p->top];
return（x）;
}
else
{printf（"Underflow!
\n"）;
return（0）;
}
}
*遍历顺序栈*
voidOutStack（SqStack*p）
{inti;
printf（"\n"）;
if（p->top<0）
printf（"这是一个空栈！
"）;
printf（"\n"）;
for（i=p->top;i>=0;i--）
printf（"第%d个数据元素是：
%6d\n",i,p->stack[i]）;
}
*置空顺序栈*
voidsetEmpty（SqStack*p）
{
p->top=-1;
}
*主函数*
main（）
{SqStack*q;
inty,cord;ElemTypea;
do{
printf（"\n"）;
printf（"第一次使用必须初始化！
\n"）;
printf（"\n"）;
printf（"\n主菜单\n"）;
printf（"\n1初始化顺序栈\n"）;
printf（"\n2插入一个元素\n"）;
printf（"\n3删除栈顶元素\n"）;
printf（"\n4取栈顶元素\n"）;
printf（"\n5置空顺序栈\n"）;
printf（"\n6结束程序运行\n"）;
printf（"\n\n"）;
printf（"请输入您的选择（1,2,3,4,5,6）"）;
scanf（"%d",&cord）;
printf（"\n"）;
switch（cord）
{case1:
{q=（SqStack*）malloc（sizeof（SqStack））;
InitStack（q）;
OutStack（q）;
}break;
case2:
{printf（"请输入要插入的数据元素：
a="）;
scanf（"%d",&a）;
Push（q,a）;
OutStack（q）;
}break;
case3:
{Pop（q）;
OutStack（q）;
}break;
case4:
{y=GetTop（q）;
printf（"\n栈顶元素为：
%d\n",y）;
OutStack（q）;
}break;
case5:
{setEmpty（q）;
printf（"\n顺序栈被置空！
\n"）;
OutStack（q）;
}break;
case6:
exit（0）;
}
}while（cord<=6）;
}
[实验2]栈的链式表示和实现
实验内容与要求:
编写一个程序实现链栈的各种基本运算，并在此基础上设计一个主程序，完成如下功能：
（1）初始化链栈
（2）链栈置空
（3）入栈
（4）出栈
（5）取栈顶元素
（6）遍历链栈
分析:
链栈是没有附加头结点的运算受限的单链表。
栈顶指针就是链表的头指针。
注意：
（1）LinkStack结构类型的定义可以方便地在函数体中修改top指针本身
（2）若要记录栈中元素个数，可将元素个数属性放在LinkStack类型中定义。
（3）链栈中的结点是动态分配的，所以可以不考虑上溢。
参考程序:
#include"stdio."）;
}
*链栈置空*
voidsetEmpty（LinkStack*s）
{s->top=NULL;
printf（"\n链栈被置空！
\n"）;
}
*入栈*
voidpushLstack（LinkStack*s,Elemtypex）
{StackNode*p;
p=（StackNode*）malloc（sizeof（StackNode））;建立一个节点。
p->data=x;
p->next=s->top;由于是在栈顶pushLstack，所以要指向栈顶。
s->top=p;插入
}
*出栈*
ElemtypepopLstack（LinkStack*s）
{Elemtypex;
StackNode*p;
p=s->top;指向栈顶
if（s->top==0）
{printf（"\n栈空，不能出栈！
\n"）;
exit（-1）;
}
x=p->data;
s->top=p->next;当前的栈顶指向原栈的next
free（p）;释放
returnx;
}
*取栈顶元素*
ElemtypeStackTop（LinkStack*s）
{if（s->top==0）
{printf（"\n链栈空\n"）;
exit（-1）;
}
returns->top->data;
}
*遍历链栈*
voidDisp（LinkStack*s）
{printf（"\n链栈中的数据为：
\n"）;
printf（"=======================================\n"）;
StackNode*p;
p=s->top;
while（p!
=NULL）
{printf（"%d\n",p->data）;
p=p->next;
}
printf（"=======================================\n"）;
}
voidmain（）
{printf（"=================链栈操作=================\n\n"）;
inti,m,n,a;
LinkStack*s;
s=（LinkStack*）malloc（sizeof（LinkStack））;
intcord;
do{printf（"\n"）;
printf（"第一次使用必须初始化！
\n"）;
printf（"\n"）;
printf（"\n主菜单\n"）;
printf（"\n1初始化链栈\n"）;
printf（"\n2入栈\n"）;
printf（"\n3出栈\n"）;
printf（"\n4取栈顶元素\n"）;
printf（"\n5置空链栈\n"）;
printf（"\n6结束程序运行\n"）;
printf（"\n\n"）;
printf（"请输入您的选择（1,2,3,4,5,6）"）;
scanf（"%d",&cord）;
printf（"\n"）;
switch（cord）
{case1:
{InitStack（s）;
Disp（s）;
}break;
case2:
{printf（"输入将要压入链栈的数据的个数：
n="）;
scanf（"%d",&n）;
printf（"依次将%d个数据压入链栈：
\n",n）;
for（i=1;i<=n;i++）
{scanf（"%d",&a）;
pushLstack（s,a）;
}
Disp（s）;
}break;
case3:
{printf（"\n出栈操作开始!
\n"）;
printf（"输入将要出栈的数据个数：
m="）;
scanf（"%d",&m）;
for（i=1;i<=m;i++）
{printf（"\n第%d次出栈的数据是：
%d",i,popLstack（s））;}
Disp（s）;
}break;
case4:
{printf（"\n\n链栈的栈顶元素为：
%d\n",StackTop（s））;
printf（"\n"）;
}break;
case5:
{setEmpty（s）;
Disp（s）;
}break;
case6:
exit（0）;
}
}while（cord<=6）;
}
[实验3]队列的顺序表示和实现
实验内容与要求
编写一个程序实现顺序队列的各种基本运算，并在此基础上设计一个主程序，完成如下功能：
（1）初始化队列
（2）建立顺序队列
（3）入队
（4）出队
（5）判断队列是否为空
（6）取队头元素
（7）遍历队列
分析:
队列的顺序存储结构称为顺序队列，顺序队列实际上是运算受限的顺序表。
入队时，将新元素插入rear所指的位置，然后将rear加1。
出队时，删去front所指的元素，然后将front加1并返回被删元素。
顺序队列中的溢出现象：
（1）"下溢"现象。
当队列为空时，做出队运算产生的溢出现象。
“下溢”是正常现象，常用作程序控制转移的条件。
（2）"真上溢"现象。
当队列满时，做进栈运算产生空间溢出的现象。
“真上溢”是一种出错状态，应设法避免。
（3）"假上溢"现象。
由于入队和出队操作中，头尾指针只增加不减小，致使被删元素的空间永远无法重新利用。
当队列中实际的元素个数远远小于向量空间的规模时，也可能由于尾指针已超越向量空间的上界而不能做入队操作。
该现象称为"假上溢"现象。
注意：
（1）当头尾指针相等时，队列为空。
（2）在非空队列里，队头指针始终指向队头元素，尾指针始终指向队尾元素的下一位置。
参考程序:
#includeq->front=-1;
q->rear=-1;
returnTRUE;
}
*入队*
intappend（sqqueue*q,Elemtypex）
{if（q->rear>=MAXNUM-1）returnFALSE;
q->rear++;
q->queue[q->rear]=x;
returnTRUE;
}
*出队*
ElemtypeDelete（sqqueue*q）
{Elemtypex;
if（q->front==q->rear）return0;
x=q->queue[++q->front];
returnx;
}
*判断队列是否为空*
intEmpty（sqqueue*q）
{if（q->front==q->rear）returnTRUE;
returnFALSE;
}
*取队头元素*
intgethead（sqqueue*q）
{if（q->front==q->rear）return0;
return（q->queue[q->front+1]）;
}
*遍历队列*
voiddisplay（sqqueue*q）
{ints;
s=q->front;
if（q->front==q->rear）
printf（"队列空!
\n"）;
else
{printf（"\n顺序队列依次为：
"）;
while（srear）
{s=s+1;
printf（"%d<-",q->queue[s]）;
}
printf（"\n"）;
printf（"顺序队列的队尾元素所在位置:
rear=%d\n",q->rear）;
printf（"顺序队列的队头元素所在位置:
front=%d\n",q->front）;
}
}
*建立顺序队列*
voidSetsqqueue（sqqueue*q）
{intn,i,m;
printf（"\n请输入将要入顺序队列的长度:
"）;
scanf（"%d",&n）;
printf（"\n请依次输入入顺序队列的元素值:
\n"）;
for（i=0;i{scanf（"%d",&m）;
append（q,m）;}
}
main（）
{sqqueue*"）;
printf（"\n请选择操作（1--7）:
\n"）;
printf（"===================================\n"）;
printf（"1初始化\n"）;
printf（"2建立顺序队列\n"）;
printf（"3入队\n"）;
printf（"4出队\n"）;
printf（"5判断队列是否为空\n"）;
printf（"6取队头元素\n"）;
printf（"7遍历队列\n"）;
printf（"===================================\n"）;
scanf（"%d",&select）;
switch（select）
{case1:
{initQueue（"）;
break;
}
case2:
{Setsqqueue（"）;
display（"）;
scanf（"%d",&x）;
append（",z）;
display（"）;
else
printf（"队列非空\n"）;
break;
}
case6:
{y=gethead（",y）;
break;
}
case7:
{display（,x;
printf（"输入将建立链队列元素的个数：
n="）;
scanf（"%d",&n）;
;i++）
{printf（"链队列第%d个元素的值为：
",i）;
scanf（"%d",&x）;
Lappend（q,x）;
}
}
*出链队列*
ElemTypeLdelete（Lqueue*q）
{Qnodetype*p;
ElemTypex;
if（q->front==q->rear）
{printf（"队列为空!
\n"）;
x=0;
}
else
{p=q->front->next;
q->front->next=p->next;
if（p->next==NULL）
q->rear=q->front;
x=p->data;
free（p）;
}
return（x）;
}
*遍历链队列*
voiddisplay（Lqueue*q）
{Qnodetype*p;
p=q->front->next;*指向第一个数据元素节点*
printf（"\n链队列元素依次为：
"）;
while（p!
=NULL）
{printf（"%d-->",p->data）;
p=p->next;
}
printf（"\n\n遍历链队列结束！
\n"）;
}
main（）
{Lqueue*p;
intx,cord;
printf（"\n*****第一次操作请选择初始化并建立链队列！
*****\n"）;
do
{printf（"\n链队列的基本操作\n"）;
printf（"=========================================\n"）;
printf（"主菜单\n"）;
printf（"=========================================\n"）;
printf（"1初始化并建立链队列\n"）;
printf（"2入链队列\n"）;
printf（"3出链队列\n"）;
printf（"4遍历链队列\n"）;
printf（"5结束程序运行\n"）;
printf（"==========================================\n"）;
scanf（"%d",&cord）;
switch（cord）
{case1:
{p=（Lqueue*）malloc（sizeof（Lqueue））;
creat（p）;
display（p）;
}break;
case2:
{printf（"请输入队列元素的值：
x="）;
scanf（"%d",&x）;
Lappend（p,x）;
display（p）;
}break;
case3:
{printf（"出链队列元素：
x=%d\n",Ldelete（p））;
display（p）;
}break;
case4:
{display（p）;}break;
case5:
{exit（0）;}
}
}while（cord<=5）;
}
3.4提高实验
[实验1]迷宫的求解
实验内容与要求:
迷宫只有两个门，一个叫做入口，另一个叫做出口。
把一只老鼠从一个无顶盖的大盒子的入口处赶进迷宫。
迷宫中设置很多隔壁，对前进方向形成了多处障碍，在迷宫的唯一出口处放置了一块奶酪，吸引老鼠在迷宫中寻找通路以到达出口。
求解迷宫问题，即找出从入口到出口的路径。
分析:
迷宫问题是栈应用的一个典型例子。
求解过程可采用回溯法。
回溯法是一种不断试探且及时纠正错误的搜索方法。
从入口出发，按某一方向向前探索，若能走通（未走过的），即某处可以到达，则到达新点，否则试探下一方向;若所有的方向均没有通路，则沿原路返回前一点，换下一个方向再继续试探，直到所有可能的通路都探索到，或找到一条通路，或无路可走又返回到入口点。
在求解过程中，为了保证在到达某一点后不能向前继续行走（无路）时，能正确返回前一点以便继续从下一个方向向前试探，则需要用一个栈保存所能够到达的每一点的下标及从该点前进的方向，栈中保存的就是一条迷宫的通路。
为了确保程序能够终止，调整时，必须保证曾被放弃过的填数序列不被再次试验，即要求按某种有序模型生成填数序列。
给解的候选者设定一个被检验的顺序，按这个顺序逐一生成候选者并检验。
参考程序:
:
#include{初始化top[],置所有方向数为左
for（i=0;i{top[i].c=1;}
printf（"themazeis:
\n"）;
打印原始迷宫矩阵
for（i=0;i{for（j=0;j printf（maze[i][j]?
"*":
" "）;
printf（"\n"）;}
i=0;top[i].x=1;top[i].y=0;
maze[1][0]=2;
*回溯算法*
do{
if（top[i].c<5） 还可以向前试探
{if（top[i].x==5&&top[i].y==9）已找到一个组合
{ 打印路径
printf（"Theway%dis:
\n",m++）;
for（j=0;j<=i;j++）
{printf（"（%d,%d）-->",top[j].x,top[j].y）;}
printf（"\n"）;
打印选出路径的迷宫
for（j=0;j {for（k=0;k {if（maze[j][k]==0） printf（" "）;
elseif（maze[j][k]==2） printf（"O"）;
elseprintf（"*"）;}
printf（"\n"）;}
maze[top[i].x][top[i].y]=0;
top[i].c=1;
i--;
top[i].c+=1;
continue;}
switch（top[i].c） 向前试探
{
case1:
{ if（maze[top[i].x][top[i].y+1]==0）
{i++;
top[i].x=top[i-1].x;
top[i].y=top[
升级会员 