数据结构实验
《数据结构》实验报告
实验序号：4 实验项目名称：栈的操作
}
改写以上程序，实现功能如下：
1）调用栈操作函数实现判别一个算术表达式中的圆括号配对是否正确。
2）改写Push和Pop函数，使得以上两个函数可以一次性将一个数组入栈和出栈。（1）
（2）
2.C/C++的库函数中已经实现了栈，实例如下：
#include
using namespace std;
int main()
{
int a;
stack
scanf("%d",&a);
s.push(a); //入栈
printf("%d\n",s.top()); //取得栈顶元素输出
s.pop(); //出栈
return 0;
}
请根据以上程序，设计算法如下：
判别一个算术表达式中的圆括号和方括号配对是否正确。
四、分析与讨论
五、教师评语
成绩
签名：
日期：
附源程序清单：
1.
（1）
#include
#define MaxSize100
#define SUCCESS0
#define ERROR-1
typedef struct
{
int nData[MaxSize];
int nTop;
}SqStack;
void InitStack(SqStack*PST_List)//初始化栈
{
PST_List->nTop=-1;
}
int StackEmpty(SqStack*PST_List)//判断栈为空
{
if(PST_List->nTop==-1)
return ERROR;
else
return SUCCESS;
}
void Push(SqStack*PST_List,int nData)//元素进栈
{
if(PST_List->nTop==MaxSize-1)
{
printf("栈上溢出!\n");
}
else
{
PST_List->nTop++;//移动栈顶位置
PST_List->nData[PST_List->nTop]=nData;//元素进栈}
}
void Pop(SqStack*PST_List,int*pnData)//出栈
{
if(PST_List->nTop==-1)
{
printf("栈下溢出\n");
}
else
{
pnData=&PST_List->nData[PST_List->nTop];//元素出栈
PST_List->nTop--;//移动栈顶位置
}
}
int GetTop(SqStack*PST_List)//获取栈顶
{
if(!StackEmpty(PST_List))//先判断是否为空栈,不是空栈则返回栈顶{
return(PST_List->nData[PST_List->nTop]);
}
else
{
return ERROR;
}
}
int JudgeBrackets(SqStack*PST_List)//判断圆括号是否配对成功
{
char cData;//输入变量
int nSign=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");
}
return SUCCESS;
}
int main()
{
SqStack ST_List;
SqStack*PST_List=&ST_List;
//int nData;
//int nIndex;
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）
void Push(SqStack*PST_List,int*pnData,int nLength)//元素进栈
{
int nIndex=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"); } } } void Pop(SqStack*PST_List,int*pnData,int nLength)//出栈 { int nIndex=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]);