栈
顺序实现:
存储结构:
#define STACK_INIT_SIZE 10 // 存储空间初始分配量
#define STACK_INCREMENT 2 // 存储空间分配增量
struct SqStack
{
SElemType *base; // 在栈构造之前和销毁之后,base的值为NULL
SElemType *top; // 栈顶指针
int stacksize; // 当前已分配的存储空间,以元素为单位
}; // 顺序栈
基本操作:
void InitStack(SqStack &S)
{ // 构造一个空栈S
if(!(S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType))))
exit(OVERFLOW); // 存储分配失败
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
}
void DestroyStack(SqStack &S)
{ // 销毁栈S,S不再存在
free(S.base);
S.base=NULL;
S.top=NULL;
S.stacksize=0;
}
void ClearStack(SqStack &S)
{ // 把S置为空栈
S.top=S.base;
}
Status StackEmpty(SqStack S)
{ // 若栈S为空栈,则返回TRUE,否则返回FALSE
if(S.top==S.base)
return TRUE;
else
return FALSE;
}
int StackLength(SqStack S)
{ // 返回S的元素个数,即栈的长度
return S.top-S.base;
}
Status GetTop(SqStack S,SElemType &e)
{ // 若栈不空,则用e返回S的栈顶元素,并返回OK;否则返回ERROR
if(S.top>S.base)
{
e=*(S.top-1);
return OK;
}
else
return ERROR;
}
void Push(SqStack &S,SElemType e)
{ // 插入元素e为新的栈顶元素
if(S.top-S.base>=S.stacksize) // 栈满,追加存储空间
{
S.base=(SElemType *)realloc(S.base,(S.stacksize+STACK_INCREMENT)*sizeof(SElemType));
if(!S.base)
exit(OVERFLOW); // 存储分配失败
S.top=S.base+S.stacksize;
S.stacksize+=STACK_INCREMENT;
}
*(S.top)++=e;
}
Status Pop(SqStack &S,SElemType &e)
{ // 若栈不空,则删除S的栈顶元素,用e返回其值,并返回OK;否则返回ERROR
if(S.top==S.base)
return ERROR;
e=*--S.top;
return OK;
}
void StackTraverse(SqStack S,void(*visit)(SElemType))
{ // 从栈底到栈顶依次对栈中每个元素调用函数visit()
while(S.top>S.base)
visit(*S.base++);
printf("\n");
}
循环队列
存储结构
#define MAX_QSIZE 5 // 最大队列长度+1
struct SqQueue
{
QElemType *base; // 初始化的动态分配存储空间
int front; // 头指针,若队列不空,指向队列头元素
int rear; // 尾指针,若队列不空,指向队列尾元素的下一个位置
};
void InitQueue(SqQueue &Q)
{ // 构造一个空队列Q
Q.base=(QElemType *)malloc(MAX_QSIZE*sizeof(QElemType));
if(!Q.base) // 存储分配失败
exit(OVERFLOW);
Q.front=Q.rear=0;
}
void DestroyQueue(SqQueue &Q)
{ // 销毁队列Q,Q不再存在
if(Q.base)
free(Q.base);
Q.base=NULL;
Q.front=Q.rear=0;
}
void ClearQueue(SqQueue &Q)
{ // 将Q清为空队列
Q.front=Q.rear=0;
}
Status QueueEmpty(SqQueue Q)
{ // 若队列Q为空队列,则返回TRUE;否则返回FALSE
if(Q.front==Q.rear) // 队列空的标志
return TRUE;
else
return FALSE;
}
int QueueLength(SqQueue Q)
{ // 返回Q的元素个数,即队列的长度
return(Q.rear-Q.front+MAX_QSIZE)%MAX_QSIZE;
}
Status GetHead(SqQueue Q,QElemType &e)
{ // 若队列不空,则用e返回Q的队头元素,并返回OK;否则返回ERROR
if(Q.front==Q.rear) // 队列空
return ERROR;
e=Q.base[Q.front];
return OK;
}
Status EnQueue(SqQueue &Q,QElemType e)
{ // 插入元素e为Q的新的队尾元素
if((Q.rear+1)%MAX_QSIZE==Q.front) // 队列满
return ERROR;
Q.base[Q.rear]=e;
Q.rear=(Q.rear+1)%MAX_QSIZE;
return OK;
}
Status DeQueue(SqQueue &Q,QElemType &e)
{ // 若队列不空,则删除Q的队头元素,用e返回其值,并返回OK;否则返回ERROR
if(Q.front==Q.rear) // 队列空
return ERROR;
e=Q.base[Q.front];
Q.front=(Q.front+1)%MAX_QSIZE;
return OK;
}
void QueueTraverse(SqQueue Q,void(*vi)(QElemType))
{ // 从队头到队尾依次对队列Q中每个元素调用函数vi()
int i;
i=Q.front;
while(i!=Q.rear)
{
vi(Q.base[i]);
i=(i+1)%MAX_QSIZE;
}
printf("\n");
}