实验2 堆栈与队列.doc

实验2 堆栈与队列
实验目的
  会定义顺序栈和链栈的结点类型。
  掌握栈的插入和删除结点在操作上的特点。
  熟悉对栈的一些基本操作和具体的函数定义。
会定义顺序队列和链队列的结点类型。
实验内容
程序1
该程序的功能是实现顺序栈的定义和操作。该程序包括定义的栈结构类型以及对每一种栈操作的具体的函数定义和主函数。
/* 定义DataType为int类型*/
typedef int DataType;
 
/* 栈的结点类型*/
#define MAXSIZE 1024
typedef struct
{DataType data[MAXSIZE];
int top;
}SeqStack;
 
/* 初始化顺序栈*/
SeqStack SeqStackInit()
 
/* 检查顺序栈是否为空*/
int SeqStackEmpty(SeqStack S)
 
/* 把S置为空栈*/
void ClearStack(SeqStack *S)
 
/* 把元素x压入栈,使其成为新的栈顶元素*/
void SeqStackPush(SeqStack *S,DataType x)
 
/* 把栈顶元素弹出*/
DataType SeqStackPop(SeqStack *S)
 
/* 取栈顶元素*/
DataType SeqStackGetTop(SeqStack S)
 
/*输出顺序栈中的元素*/
void SeqStackPrint(SeqStack S)
程序2:试利用堆栈将队列中的元素逆置。
程序3:编写括号匹配算法。
队列的抽象数据类型定义:
ADT Queue{
数据对象:D={|∈ElemSet, i=1,2,...,n, n>=0}
数据关系:R1={<,>|,∈D, i=2,...,n}
基本操作:
InitQueue(&Q) 构造一个空队列Q
QueueEmpty(Q) 判断队列是否为空
QueueLenght(Q) 返回队列Q的元素个数,即队列的长度
GetHead(Q,&e) 取队列Q的队头元素,并用e返回
EnQueue(&Q,e) 将元素e入队列
DeQueue(&Q,&e) 删除非空队列Q的队头元素,并用e返回其值
}ADT Q