实验三栈和队列讲解.doc

《数据结构与算法》实验指导V2015 常熟理工学院计算机科学与工程学院  PAGE \* MERGEFORMAT 15 《数据结构与算法》实验指导与报告书 ______学年 第____ 学期 专 业： ___________________________________________ 学 号： ___________________________________________ 姓 名： ___________________________________________ 实验地点：___________________________________________ 指导教师：___________________________________________ 计算机科学与工程学院 2015 实验三 栈和队列 【实验目的】 1、掌握栈的结构特性及其入栈，出栈操作； 2、掌握队列的结构特性及其入队、出队的操作，掌握循环队列的特点及其操作。 3、理解掌握递归调用程序设计思想。 【实验学时】 4学时 【实验预习】 回答以下问题： 1、栈的顺序存储表示 2、单链队列的存储表示 3、循环队列的顺序存储表示 【实验内容和要求】 1、按照要求完成程序exp3_1.c，实现顺序栈的相关操作。以下具有返回值的函数，若操作完成，返回OK，操作失败返回ERROR。函数需返回的其他数据，使用函数参数返回。 调试及测试数据并给出结果： 初始化栈； 连续进栈3 ，5，7，9，13； 获取当前栈顶元素； 返回当前栈长度； 判断当前栈是否为空； 栈内元素依次出栈； 判断当前栈是否为空； 清空栈； 利用栈实现数制转换，测试整数8和255； 判断表达式括号是否匹配，测试以下三个表达式： 表达式1：1*(2+3)/4； 表达式2：((3+4)*7-(8-9)； 表达式3：（（1+2）*（3+4）-（5+6）*3） exp3_1.c部分代码如下： #includestdio.h #includemalloc.h #includestring.h #define ERROR 0 #define OK 1 #define STACK_INT_SIZE 10 /*存储空间初始分配量*/ #define STACKINCREMENT 5 /*存储空间分配增量*/ typedef int ElemType; /*定义元素的类型*/ /*（1）补充栈的顺序存储分配表示，采用定长和可变长度存储均可*/ int InitStack(SqStack *S); /*构造空栈*/ int Push(SqStack *S,ElemType e); /*入栈*/ int Pop(SqStack *S,ElemType *e); /*出栈*/ int GetTop(SqStack *S,ElemType *e); /*获取栈顶元素*/ int ClearStack(SqStack *S); /*清空栈*/ int StackEmpty(SqStack *S); /*判断栈是否为空*/ int StackLength(SqStack *S); /*求栈的长度*/ void conversion(); /*十进制转换为二进制*/ void Correct(); /*判断表达式括号是否匹配*/ /*（2）初始化栈函数*/ int InitStack(SqStack *S) { }/*InitStack*/ /*（3）入栈函数*/ int Push(SqStack *S,ElemType e) { }/*Push*/ /*（4）出栈函数*/ int Pop(SqStack *S,ElemType *e) { }/*Pop*/ /*（5）返回栈顶元素函数*/ int GetTop(SqStack *S,ElemType *e) { }/*GetTop*/ /*（6）清空栈函数*/ int ClearStack(SqStack *S) { }/*ClearStack*/ /*（8）判断栈是否为空函数*/ int StackEmpty(SqStack *S) { }/*StackEmpty*/ /*（9）返回栈的长度函数*/ int StackLength(SqStack *S) { }/*StackLength*/ /*（10）十进制整数转换为二进制并输出函数*/ void Conversion() { }/*Conversion*/ /*（11）判断表达式括弧是否匹配