文档库 最新最全的文档下载
当前位置:文档库 › 数据结构C语言版_栈的顺序存储表示和实现

数据结构C语言版_栈的顺序存储表示和实现

/*
数据结构C语言版 栈的顺序存储表示和实现
P46-P47
栈顶指针始终指向当前栈顶元素的下一个位置,
栈顶指针与栈底指针相同的为空栈。
编译环境:Dev-C++ 4.9.9.2
日期:2011年2月12日
*/
#include
#include

typedef char SElemType; // 栈的元素类型

#define STACK_INIT_SIZE 10 // 存储空间初始分配量
#define STACKINCREMENT 2 // 存储空间分配增量
// 栈的顺序存储表示 P46
typedef struct SqStack
{
SElemType *base; // 在栈构造之前和销毁之后,base的值为NULL
SElemType *top; // 栈顶指针
int stacksize; // 当前已分配的存储空间,以元素为单位
}SqStack; // 顺序栈



// 构造一个空栈S。
int InitStack(SqStack *S)
{
// 为栈底分配一个指定大小的存储空间
(*S).base = (SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if( !(*S).base )
exit(0); // 存储分配失败
(*S).top = (*S).base; // 栈底与栈顶相同表示一个空栈
(*S).stacksize = STACK_INIT_SIZE;
return 1;
}

// 若栈S为空栈(栈顶与栈底相同的),则返回1,否则返回0。
int StackEmpty(SqStack S)
{
if(S.top == S.base)
return 1;
else
return 0;
}

// 插入元素e为新的栈顶元素。
int Push(SqStack *S, SElemType e)
{
if((*S).top - (*S).base >= (*S).stacksize) // 栈满,追加存储空间
{
(*S).base = (SElemType *)realloc((*S).base,
((*S).stacksize + STACKINCREMENT) * sizeof(SElemType));
if( !(*S).base )
exit(0); // 存储分配失败
(*S).top = (*S).base+(*S).stacksize;
(*S).stacksize += STACKINCREMENT;
}
*((*S).top)++=e;
// 这个等式的++ * 优先级相同,但是它们的运算方式,是自右向左
return 1;
}

// 若栈不空,则删除S的栈顶元素,用e返回其值,并返回1;否则返回0。
int Pop(SqStack *S,SElemType *e)
{
if((*S).top == (*S).base)
return 0;
*e = *--(*S).top;
// 这个等式的++ * 优先级相同,但是它们的运算方式,是自右向左
return 1;
}

// 销毁栈S,S不再存在。
int DestroyStack(SqStack *S)
{
free((*S).base); //释放栈底的空间,并置空
(*S).base = NULL;
(*S).top = NULL;
(*S).stacksize = 0;
return 1;
}

// 把S置为空栈。
int ClearStack(SqStack *S)
{
(*S).top = (*S).base; //栈底栈顶相同为空栈
return 1;
}


// 返回S的元素个数,即栈的长度。
int StackLength(SqStack S)
{
// 栈顶指针减去栈底指针刚好等于长度,因为栈顶指针指向当前栈
// 顶元素的下一个位置。
return S.top - S.base;
}

// 若栈不空,则用e返回S的栈顶元素,并返回1;否则返回0。
int GetTop(SqStack S,SElemType *e)
{
if(S.top > S.base)
{
*e = *(S.top-1); // 栈顶指针的下一个位置为栈顶元素
return 1;
}
else
return 0;
}



// 从栈底到栈顶依次对栈中每个元素调用函数visit()。
int S

tackTraverse(SqStack S,int(*visit)(SElemType))
{
while(S.top>S.base)
visit(*S.base++);
printf("\n");
return 1;
}


int visit(SElemType c)
{
printf("%d ",c);
return 1;
}

int main()
{
int j;
SqStack s;
SElemType e;

// 创建一个顺序栈。
if(InitStack(&s) == 1)
printf("顺序栈创建成功!\n");

// 查看栈的长度。
printf("栈的长度是%d\n", StackLength(s));

// 查看栈是否为空。
printf("栈空否:%d(1:空 0:否)\n",StackEmpty(s));

// 初始化栈。
for(j = 1; j <= 12; j++)
Push(&s, j);
printf("栈中元素依次为:");
StackTraverse(s,visit);

Pop(&s,&e);
printf("弹出的栈顶元素 e=%d\n",e);

printf("栈空否:%d(1:空 0:否)\n",StackEmpty(s));

GetTop(s,&e);
printf("栈顶元素 e=%d 栈的长度为%d\n",e,StackLength(s));

ClearStack(&s);
printf("清空栈后,栈空否:%d(1:空 0:否)\n",StackEmpty(s));

DestroyStack(&s);
printf("销毁栈后,s.top=%u s.base=%u s.stacksize=%d\n",
s.top,s.base, s.stacksize);

system("pause");
return 0;
}

/*
输出效果:

顺序栈创建成功!
栈的长度是0
栈空否:1(1:空 0:否)
栈中元素依次为:1 2 3 4 5 6 7 8 9 10 11 12
弹出的栈顶元素 e=12
栈空否:0(1:空 0:否)
栈顶元素 e=11 栈的长度为11
清空栈后,栈空否:1(1:空 0:否)
销毁栈后,s.top=0 s.base=0 s.stacksize=0
请按任意键继续. . .

*/

相关文档
相关文档 最新文档