数据结构实验报告-栈和队列教程.doc
文本预览下载声明
《数据结构与算法》实验指导V2016
PAGE \* MERGEFORMAT 14
实验三 栈和队列
【实验目的】
1、掌握栈的结构特性及其入栈，出栈操作；
2、掌握队列的结构特性及其入队、出队的操作，掌握循环队列的特点及其操作。
3、理解掌握递归调用程序设计思想。
【实验学时】
4学时
【实验预习】
回答以下问题：
栈的顺序存储表示
单链队列的存储表示
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）补充栈的顺序存储分配表示，采用定长和可变长度存储均可*/
typedef struct
{
ElemType *base;
ElemType *top;
int stacksize;
}SqStack;
int InitStack(SqStack *S); /*构造空栈*/
int Push(SqStack *S,ElemType e); /*入栈*/
int Pop(SqStack *S,ElemType *e); /*出栈*/
int PopSq(SqStack *S);
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)
{
S-base=(ElemType *)malloc(STACK_INT_SIZE*sizeof(ElemType));
if(!S-base)
{
return ERROR;
}
S-top=S-base;
S-stacksize=STACK_INT_SIZE;
return OK;
}/*InitStack*/
/*（3）入栈函数*/
int Push(SqStack *S,ElemType e)
{
if(S-top-S-base=S-stacksize)
{
S-base=(ElemType *)realloc(S-base,(S-stacksize+STACKINCREMENT)*sizeof(ElemType));
if(!S-base)
{
return ERROR;
}
S-top=S-base+S-stacksize;
S-stacksize+=STACKINCREMENT;
}
*S-top++=e;
return OK;
}/*Push*/
/*（4）出栈函数*/
int Pop(SqStack *S,ElemType *e)
{
if(S-top==S-base)
{
return ERROR;
}
--S-top;
*e=*S-t
显示全部