//数据结构 第三章栈和队列
#include<stdio.h>
#include<stdlib.h>
#define OVERFLOW -2
#define FALSE 0
#define TRUE 1
#define OK 1
#define ERROR 0
typedef int Status;
//栈的顺序存储表示
#define STACK_INIT_SIZE 100 //存储空间的初始分配量
#define STACKINCREAMENT 10 //存储空间分配增量
typedef char SElemType;
typedef struct
{
SElemType *base; //构造之前和销毁之后base的值为NULL
SElemType *top; //栈顶指针
int stacksize; //当前已分配的存储空间
}SqStack;
//基本操作的函数原型声明
//构造一个空栈
Status InitStack(SqStack *S);
//销毁栈S
Status DestroyStack(SqStack *S);
//把S置为空栈
Status ClearStack(SqStack *S);
//若栈为空栈返回TRUE
Status StackEmpty(SqStack S);
//返回栈的长度
int StackLength(SqStack S);
//返回栈顶元素
Status GetTop(SqStack S,SElemType *e);
//入栈
Status Push(SqStack *S,SElemType e);
//出栈
Status Pop(SqStack *S,SElemType *e);
//遍历栈
Status StackTraverse(SqStack S,Status( *visit)());
Status InitStack(SqStack *S)
{
S->base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if(!S->base) exit(OVERFLOW);//存储分配失败
S->top=S->base;
S->stacksize=STACK_INIT_SIZE;
return OK;
}
Status GetTop(SqStack S,SElemType *e)
{
if(S.top==S.base) return ERROR;
*e=*(S.top-1);
return OK;
}
Status Push(SqStack *S,SElemType e)
{
if(S->top-S->base>=S->stacksize)//栈满,追加存储空间
{
S->base=(SElemType *)realloc(S->base,(S->stacksize+STACKINCREAMENT)*sizeof(SElemType));
if(!S->base) exit(OVERFLOW);
S->top=S->base+S->stacksize;
S->stacksize+=STACKINCREAMENT;
}
//入栈操作,完成操作后,top指针加1
*S->top++=e;
return OK;
}
Status Pop(SqStack *S,SElemType *e)
{
if(S->base==S->top) return ERROR;
*e=*--S->top;
return OK;
}
Status StackEmpty(SqStack S)
{
if(S.base==S.top)
{
return TRUE;
}
else
{
return FALSE;
}
}
Status ClearStack(SqStack *S)
{
S->top=S->base;
return OK;
}
Status DestroyStack(SqStack *S)
{
S->base=NULL;
return OK;
}
//栈的应用举例,数制转转
void conversion(SqStack *S)
{
//对于输入的任意一个非负十进制整数,打印输出其八进制数
SElemType quotient;
int N;
InitStack(S);
scanf("%d",&N);
while(N)
{
Push(S,N%8);
N=N/8;
}
while(!StackEmpty(*S))
{
Pop(S,"ient);
printf("%d",quotient);
}
}
//行编辑程序
//如果从终端接收的一个字符既不是退格符也不是退行符,则将该字符入栈
//如果是一个退格符,则从栈顶删除一个字符,如果是一个退行符则将字符栈清空
void LineEdit(SqStack *S)
{
char ch,c;
ch=getchar();
InitStack(S);
while(ch!=EOF)
{
while(ch!=EOF && ch!='\n')
{
switch(ch)
{
case '#':Pop(S,&c); break;
case '@':ClearStack(S); break;
default:Push(S,ch); break;
}
ch=getchar();//从终端接收下一个字符
}
//将从栈底到栈顶的字符传送至调用过程的数据区
ClearStack(S);//重置栈为空
if(ch!=EOF) ch=getchar();
}
DestroyStack(S);
}
以下还有迷宫求解问题,表达式求值问题(计算器的核心原理)
栈与递归的实现,汉诺塔问题,马踏棋盘问题,八皇后问题等。
以后再单独列出来将,队列下一步再说。