数据结构实验.docx
《数据结构实验.docx》由会员分享，可在线阅读，更多相关《数据结构实验.docx（19页珍藏版）》请在冰点文库上搜索。
数据结构实验
《数据结构》实验报告
实验序号：
4 实验项目名称：
栈的操作
学 号
姓 名
专业、班
实验地点
指导教师
实验时间
一、实验目的及要求
1.熟悉栈的基本概念；
2.掌握栈的顺序存储结构；
3．掌握栈的应用。
二、实验设备（环境）及要求
微型计算机；
windows操作系统；
MicrosoftVisualStudio6.0集成开发环境。
三、实验内容与步骤
1.栈的顺序表表示和实现的如下：
#include
#defineMaxSize100
usingnamespacestd;
typedefintElemType;
typedefstruct
{
ElemTypedata[MaxSize];
inttop;
}SqStack;
voidInitStack（SqStack*st）//初始化栈
{
st->top=-1;
}
intStackEmpty（SqStack*st）//判断栈为空
{
return（st->top==-1）;
}
voidPush（SqStack*st,ElemTypex）//元素进栈
{
if（st->top==MaxSize-1）
{
printf（"栈上溢出!
\n"）;
}
else
{
st->top++;//移动栈顶位置
st->data[st->top]=x;//元素进栈
}
}
voidPop（SqStack*st,ElemType&e）//出栈
{
if（st->top==-1）
{
printf（"栈下溢出\n"）;
}
else
{
e=st->data[st->top];//元素出栈
st->top--;//移动栈顶位置
}
}
intmain（）
{
SqStackL;
SqStack*st=&L;
ElemTypee;
inti;
InitStack（st）;
for（i=1;i<10;++i）
{
Push（st,i）;
printf（"入栈元素是：
%d\n",i）;
}
for（i=1;i<10;++i）
{
Pop（st,e）;
printf（"出栈元素是：
%d\n",e）;
}
return0;
}
改写以上程序，实现功能如下：
1）调用栈操作函数实现判别一个算术表达式中的圆括号配对是否正确。
2）改写Push和Pop函数，使得以上两个函数可以一次性将一个数组入栈和出栈。
（1）
（2）
2.C/C++的库函数中已经实现了栈，实例如下：
#include//引入栈
usingnamespacestd;
intmain（）
{
inta;
stacks;
scanf（"%d",&a）;
s.push（a）;//入栈
printf（"%d\n",s.top（））;//取得栈顶元素输出
s.pop（）;//出栈
return0;
}
请根据以上程序，设计算法如下：
判别一个算术表达式中的圆括号和方括号配对是否正确。
四、分析与讨论
五、教师评语
签名：
日期：
成绩
附源程序清单：
1.
（1）
#include
#defineMaxSize100
#defineSUCCESS0
#defineERROR-1
typedefstruct
{
intnData[MaxSize];
intnTop;
}SqStack;
voidInitStack（SqStack*PST_List）//初始化栈
{
PST_List->nTop=-1;
}
intStackEmpty（SqStack*PST_List）//判断栈为空
{
if（PST_List->nTop==-1）
returnERROR;
else
returnSUCCESS;
}
voidPush（SqStack*PST_List,intnData）//元素进栈
{
if（PST_List->nTop==MaxSize-1）
{
printf（"栈上溢出!
\n"）;
}
else
{
PST_List->nTop++;//移动栈顶位置
PST_List->nData[PST_List->nTop]=nData;//元素进栈
}
}
voidPop（SqStack*PST_List,int*pnData）//出栈
{
if（PST_List->nTop==-1）
{
printf（"栈下溢出\n"）;
}
else
{
pnData=&PST_List->nData[PST_List->nTop];//元素出栈
PST_List->nTop--;//移动栈顶位置
}
}
intGetTop（SqStack*PST_List）//获取栈顶
{
if（!
StackEmpty（PST_List））//先判断是否为空栈,不是空栈则返回栈顶
{
return（PST_List->nData[PST_List->nTop]）;
}
else
{
returnERROR;
}
}
intJudgeBrackets（SqStack*PST_List）//判断圆括号是否配对成功
{
charcData;//输入变量
intnSign=0;//判断标志
int*pnData=NULL;//传入pop中的参数
printf（"请输入一个表达式：
"）;
cData=getchar（）;
while（cData!
='\n'）//按下回车结束死循环
{
switch（cData）
{
case'（':
//对于左括号就入栈
{
Push（PST_List,（int）cData）;
break;
}
case'）':
{
if（GetTop（PST_List）=='（'）//栈顶有左括号就出栈
{
Pop（PST_List,pnData）;
}
else//否则就将判断标志置1
{
nSign=1;
}
break;
}
default:
//对于其他的输入不做操作
{
break;
}
}
cData=getchar（）;
}
if（GetTop（PST_List）=='（'）//结束输入后判断栈顶是否还有左括号
{
nSign=1;
}
if（nSign==1）
{
printf（"圆括号配对不成功！
\n"）;
}
else
{
printf（"圆括号配对成功！
\n"）;
}
returnSUCCESS;
}
intmain（）
{
SqStackST_List;
SqStack*PST_List=&ST_List;
//intnData;
//intnIndex;
InitStack（PST_List）;
JudgeBrackets（PST_List）;
/*for（nIndex=1;nIndex<10;++nIndex）
{
Push（PST_List,nIndex）;
printf（"入栈元素是：
%d\n",nIndex）;
}
for（nIndex=1;nIndex<10;++nIndex）
{
Pop（PST_List,nData）;
printf（"出栈元素是：
%d\n",nData）;
}*/
return0;
}
（2）
voidPush（SqStack*PST_List,int*pnData,intnLength）//元素进栈
{
intnIndex=0;
if（PST_List->nTop==MaxSize-1）
{
printf（"栈上溢出!
\n"）;
}
else
{
if（（MaxSize-PST_List->nTop-1）>=nLength）//判断栈剩余空间是否大于要入栈的元素个数
{
for（nIndex=0;nIndex{
PST_List->nTop++;//移动栈顶位置
PST_List->nData[PST_List->nTop]=pnData[nIndex];//元素进栈
printf（"入栈元素为:
%d\n",PST_List->nData[PST_List->nTop]）;
}
printf（"元素进栈成功!
\n"）;
}
else//栈空间小于要入栈元素的个数，只入栈剩余空间大小的元素个数
{
printf（"栈空间只剩%d个，而数组元素有%d个，所以只入栈%d个!
\n",（MaxSize-PST_List->nTop-1）,nLength,（MaxSize-PST_List->nTop-1））;
nLength=MaxSize-PST_List->nTop-1;//长度赋值为剩余空间大小
for（nIndex=0;nIndex{
PST_List->nTop++;//移动栈顶位置
PST_List->nData[PST_List->nTop]=pnData[nIndex];//元素进栈
printf（"入栈元素为:
%d\n",PST_List->nData[PST_List->nTop]）;
}
printf（"元素进栈成功!
\n"）;
}
}
}
voidPop（SqStack*PST_List,int*pnData,intnLength）//出栈
{
intnIndex=0;
if（PST_List->nTop==-1）
{
printf（"栈下溢出\n"）;
}
else
{
if（nLength<=PST_List->nTop+1）//要出栈元素个数小于当前栈顶
{
for（nIndex=0;nIndex{
pnData[nIndex]=PST_List->nData[PST_List->nTop];//元素出栈
printf（"出栈元素是：
%d\n",PST_List->nData[PST_List->nTop]）;
PST_List->nTop--;//移动栈顶位置
}
printf（"元素出栈成功!
\n"）;
}
else//要出栈元素个数大于当前栈顶，把栈内全部元素出栈
{
nLength=PST_List->nTop+1;
for（nIndex=0;nIndex{
pnData[nIndex]=PST_List->nData[PST_List->nTop];//元素出栈
printf（"出栈元素是：
%d\n",PST_List->nData[PST_List->nTop]）;
PST_List->nTop--;//移动栈顶位置
}
printf（"元素出栈成功!
\n"）;
}
}
}
2.
#include//引入栈
#include
usingnamespacestd;
intmain（）
{
charcBuff;
intnSign=0;//判断标志，初值为0
stackStList;
printf（"输入表达式，以#号结束输入!
\n"）;
do
{
scanf（"%c",&cBuff）;
switch（cBuff）
{
case'[':
StList.push（cBuff）;//入栈
//printf（"入栈：
%c\n",cBuff）;
break;
case'（':
StList.push（cBuff）;//入栈
//printf（"入栈：
%c\n",cBuff）;
break;
case'）':
if（StList.empty（））//对于一开始就输入"）"的情况作出判断，直接配对失败
{
nSign=-1;
}
else
{
if（StList.top（）=='（'）//取得栈顶元素输出
{
//出栈
//printf（"出栈：
%c\n",StList.top（））;
StList.pop（）;
}
else
{
nSign=-1;
}
}
break;
case']':
if（StList.empty（））////对于一开始就输入"]"的情况作出判断，直接配对失败
{
nSign=-1;
}
else
{
if（StList.top（）=='['）//取得栈顶元素输出
{
//出栈
//printf（"出栈：
%c\n",StList.top（））;
StList.pop（）;
}
else
{
nSign=-1;
}
}
break;
default:
break;
}
if（nSign==-1）
break;
}while（cBuff!
='#'）;
if（!
StList.empty（））//调用判空函数，看是否栈中还有（[
{
nSign=-1;
}
if（nSign==0）
{
printf（"配对成功!
\n"）;
}
else
{
printf（"配对失败!
\n"）;
}
return0;
}
升级会员 