栈和队列及其应用(实验三).doc

文档介绍：实验三栈和队列及其应用
实验目的及要求
掌握栈和队列这两种特殊的线性表,熟悉它们的特性,在实际问题背景下灵活运用它们;
本实验训练的要点是“栈”的观点及其典型用法;
掌握问题求解的状态表示及其递归算法,以及由递归程序到非递归程序的转化方法。
实验内容
编程实现栈在两种存储结构中的基本操作(栈的初始化、判栈空、入栈、出栈等);
应用栈的基本操作,实现数制转换(任意进制);
编程实现队列在两种存储结构中的基本操作(队列的初始化、判队列空、入队列、出队列);
利用栈实现任一个表达式中的语法检查(括号的匹配)。
利用栈实现表达式的求值。
实验主要流程、基本操作或核心代码、算法片段(该部分如不够填写,请另加附页)
编程实现栈在两种存储结构中的基本操作(栈的初始化、判栈空、入栈、出栈等);
程序代码部分:
顺序存储
头文件:
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define INFEASTALE -1
#define OVERFLOW -2
功能函数:
typedef int Status;
typedef int SElemType;
typedef struct{
SElemType *base;
SElemType *top;
int stacklength;
}Sqstack;
Status Init(Sqstack &S);
Status Destroy(Sqstack &S);
Status Clear(Sqstack &S);
Status Empty(Sqstack S);
int Length(Sqstack S);
Status GetTop(Sqstack S,SElemType &e);
Status Push(Sqstack &S,SElemType e);
Status Pop(Sqstack &S,SElemType &e);
#include""
#include""
#include""
Status Init(Sqstack &S)
{
=(SElemType *)malloc (STACK_INIT_SIZE*sizeof(SElemType));
if(!) exit(OVERFLOW);
=;
=STACK_INIT_SIZE;
return OK;
}
Status Destroy(Sqstack &S)
{
=NULL;
return OK;
}
Status Clear(Sqstack &S)
{
=;
return OK;
}
Status Empty(Sqstack S)
{
if(==)
{
return TRUE;
}
else return FALSE;
}
int Length(Sqstack S)
{
return -;
}
Status GetTop(Sqstack S,SElemType &e)
{
if(==) return ERROR;
e=*(-1);
return OK;
}
Status Push(Sqstack &S,SElemType e)
{
if(->=STACK_INIT_SIZE)
{
=(SElemType *) realloc(,(+STACKINCREMENT)*sizeof(SElemType));
if(!) exit(OVERFLOW);
=+;
+=STACKINCREMENT;
}
*++=e;
return OK;
}
Status Pop(Sqstack &S,SElemType &e)
{
if(==) exit(ERROR);
e=*--;
return OK;
}
主函数:
#include""
#include""
#include"