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

文档介绍：实验三栈和队列及其应用一. 实验目的及要求(1) 掌握栈和队列这两种特殊的线性表, 熟悉它们的特性, 在实际问题背景下灵活运用它们; (2) 本实验训练的要点是“栈”的观点及其典型用法; (3) 掌握问题求解的状态表示及其递归算法, 以及由递归程序到非递归程序的转化方法。二. 实验内容(1) 编程实现栈在两种存储结构中的基本操作(栈的初始化、判栈空、入栈、出栈等); (2) 应用栈的基本操作,实现数制转换(任意进制); (3) 编程实现队列在两种存储结构中的基本操作(队列的初始化、判队列空、入队列、出队列); (4) 利用栈实现任一个表达式中的语法检查(括号的匹配)。(5) 利用栈实现表达式的求值。三. 实验主要流程、基本操作或核心代码、算法片段(该部分如不够填写,请另加附页) (1) 编程实现栈在两种存储结构中的基本操作(栈的初始化、判栈空、入栈、出栈等); 程序代码部分: 顺序存储头文件: #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"" int main() { printf(" 是否创建空栈? \n"); printf("1 、创建\n2 、退出\n"); int a;// 选择 scanf("%d",&a