实验三栈操作
一、实验目的
1．熟悉栈的的顺序存储结构和链式存储结构定义；
2．掌握栈的基本操作，如：压栈、弹栈、判栈空、判栈满等运算。
3．掌握栈的特点(先进后出FILO)，并能在实际问题背景下灵活应用。二、实验内容
示例程序1：圆括号匹配的检验（LinkStack.h＋LS_ParenMatch.cpp）本示例程序在头文件LinkStack.h中定义了栈的链式存储结构，并实现了链栈的基本操作（判栈空、构造、压栈、弹栈、销毁栈等）。在文件LS_ParenMatch.cpp 中实现了栈基本操作的一个实际应用：圆括号()匹配的检验。要求学生利用头文件LinkStack.h中已经定义的栈的基本操作实现栈的其他应用，或在头文件中添加其他关于栈的基本操作。
1.LinkStack.h中代码如下：
//链栈基本操作的实现
#include
#include
#define NULL 0
//定义栈中元素的类型,可根据实际数据类型进行定义
//typedef char StackElementType;//栈中元素的类型
//#define PF "%c" //元素输出格式
//定义栈的链式存储结构
typedef struct node
{
StackElementType data;
struct node *next;
}LinkStack;
//链栈基本操作的说明
int IsEmpty(LinkStack *top);//判栈空
LinkStack *Push(LinkStack *top,StackElementType x);// 压栈
LinkStack *Pop(LinkStack *top,StackElementType &elem);//弹栈StackElementType GetTop(LinkStack *top);//取栈顶元素
void ShowStack(LinkStack *top);//输出栈中数据（顶-->底）void DestroyStack(LinkStack *top);//销毁栈
//链栈基本操作的实现
int IsEmpty(LinkStack *top)
{//判栈空
return top? 0:1;
}
LinkStack *Push(LinkStack *top,StackElementType x)
{// 压栈
LinkStack *p;
p=(LinkStack *)malloc(sizeof(LinkStack));
if(p)
{
p->data=x;
p->next=top;
top=p;
}
else
{
printf("内存空间不足,程序运行终止!\n");
exit(0);
}
return top;
}
LinkStack *Pop(LinkStack *top,StackElementType &elem)
{//弹栈
LinkStack *temp;
if(IsEmpty(top))
{
printf("空栈，出栈操作失败！\n");
return NULL;
}
else
{
temp=top;
elem=top->data;
top=top->next;
free(temp);
return top;
}
}
StackElementType GetTop(LinkStack *top)
{//取栈顶元素
if(IsEmpty(top))
{
printf("空栈，取栈顶元素失败！\n");
return 0;
}
else
return top->data;
}
void ShowStack(LinkStack *top)
{//输出栈中数据（顶-->底）
LinkStack *p;
p=top;
printf(" Stack:");
while(p)
{
printf(PF,p->data);
p=p->next;
}
printf("\n");
}
void DestroyStack(LinkStack *top)
{//销毁栈
LinkStack *p;
if(top)
{
p=top;
top=top->next;
free(p);
}
printf("栈已经销毁！\n");
}
2.LS_ParenMatch.cpp中代码如下：
//栈的一个应用实例：圆括号()匹配的检验
//假设表达式中充许括号嵌套,
//则检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。
//例：（（）（）（（）））
//先出现的左括号后匹配，后出现的左括号先匹配。
//符合栈的操作特性：先进后出（后进先出）。
//故可通过栈的基本操作实现括号是否匹配的检验。
//链栈基本操作的实现
//定义栈中元素的类型,可根据实际数据类型进行定义typedef char StackElementType;//元素类型
#define PF "%c" //元素输出格式
#include "linkstack.h"
//链栈头文件，实现了链栈的基本操作
//（判栈空、构造、压栈、弹栈、销毁栈、输出栈数据）
bool PMatch()
{//检查表达式中圆括号()配对是否正确
LinkStack *s=NULL;
char c,e;
printf("请输入表达式(以';'结束):\n");
c=getchar();
while(c!=';')
{
printf("读入字符为：%c",c);
ShowStack(s);
if(c=='(')
s=Push(s,c);
if(c==')')
{
if(s) s=Pop(s,e);
else {
printf("missing '('\n");
return false;
}
}
c=getchar();
}
if(!IsEmpty(s))
{
printf("missing ')'\n");
return false;
}
else { printf("Match Success!\n");
return true;
