数据结构C语言版栈的顺序存储表示和实现六
/*
数据结构C语言版栈的顺序存储表示和实现 46-47
栈顶指针始终指向当前栈顶素的下一个位置, 栈顶指针与栈底指针相同的为空栈。 编译环境：Dev-C++ 4.9.9.2 日期：2011年2月12日 */
#include <stdio.h> #include <malloc.h>
tyedef char SElemTye; // 栈的素类型
#define STACK_INIT_SIZE 10 // 存储空间初始分配量 #define STACKINCREMENT 2 // 存储空间分配增量 // 栈的顺序存储表示 46 tyedef struct SqStack {
SElemTye *base; // 在栈构造之前和销毁之后base的值为NULL SElemTye *to; // 栈顶指针 int stacksize; // 当前已分配的存储空间以素为单位 }SqStack; // 顺序栈
// 构造一个空栈S。 int InitStack(SqStack *S) {
// 为栈底分配一个指定大小的存储空间
(*S).base = (SElemTye *)malloc(STACK_INIT_SIZE*sizeof(SElemTye)); if( !(*S).base ) exit(0); // 存储分配失败
(*S).to = (*S).base; // 栈底与栈顶相同表示一个空栈 (*S).stacksize = STACK_INIT_SIZE; return 1; }
// 若栈S为空栈（栈顶与栈底相同的）则返回1否则返回0。 int StackEmty(SqStack S)
{
if(S.to == S.base) return 1; else return 0; }
// 插入素e为新的栈顶素。 int ush(SqStack *S, SElemTye e) {
if((*S).to - (*S).base >= (*S).stacksize) // 栈满追加存储空间 {
(*S).base = (SElemTye *)realloc((*S).base,
((*S).stacksize + STACKINCREMENT) * sizeof(SElemTye)); if( !(*S).base )
exit(0); // 存储分配失败
(*S).to = (*S).base+(*S).stacksize; (*S).stacksize += STACKINCREMENT; }
*((*S).to)++=e;
// 这个等式的++ * 优先级相同但是它们的运算方式是自右向左 return 1; }
// 若栈不空则删除S的栈顶素用e返回其值并返回1；否则返回0。 int o(SqStack *S,SElemTye *e) {
if((*S).to == (*S).base) return 0;
*e = *--(*S).to;
// 这个等式的++ * 优先级相同但是它们的运算方式是自右向左 return 1; }
// 销毁栈SS不再存在。 int DestroyStack(SqStack *S) {
free((*S).base); //释放栈底的空间并置空 (*S).base = NULL; (*S).to = NULL; (*S).stacksize = 0; return 1; }
// 把S置为空栈。 int ClearStack(SqStack *S) {
(*S).to = (*S).base; //栈底栈顶相同为空栈 return 1; }
// 返回S的素个数即栈的长度。 int StackLength(SqStack S) {
// 栈顶指针减去栈底指针刚好等于长度因为栈顶指针指向当前栈 // 顶素的下一个位置。 return S.to - S.base; }
// 若栈不空则用e返回S的栈顶素并返回1；否则返回0。 int GetTo(SqStack S,SElemTye *e) {
if(S.to > S.base) {
*e = *(S.to-1); // 栈顶指针的下一个位置为栈顶素 return 1; } else return 0; }
// 从栈底到栈顶依次对栈中每个素调用函数visit()。 int S
tackTraverse(SqStack S,int(*visit)(SElemTye)) {
while(S.to>S.base) visit(*S.base++);
rintf("\\n"); return 1; }
int visit(SElemTye c) {
rintf("%d ",c); return 1; }
int main() { int j;
SqStack s; SElemTye e;
// 创建一个顺序栈。 if(InitStack(&am;s) == 1)
rintf("顺序栈创建成功!\\n");
// 查看栈的长度。
rintf("栈的长度是%d\\n", StackLength(s));
// 查看栈是否为空。
rintf("栈空否：%d(1:空 0:否)\\n",StackEmty(s));
// 初始化栈。
for(j = 1; j <= 12; j++) ush(&am;s, j);
rintf("栈中素依次为："); StackTraverse(s,visit);
o(&am;s,&am;e);
rintf("弹出的栈顶素 e=%d\\n",e);
rintf("栈空否：%d(1:空 0:否)\\n",StackEmty(s));
GetTo(s,&am;e);
rintf("栈顶素 e=%d 栈的长度为%d\\n",e,StackLength(s));
ClearStack(&am;s);
rintf("清空栈后栈空否：%d(1:空 0:否)\\n",StackEmty(s));
DestroyStack(&am;s);
rintf("销毁栈后s.to=%u s.base=%u s.stacksize=%d\\n", s.to,s.base, s.stacksize);
system("ause");
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.to=0 s.base=0 s.stacksize=0 请按任意键继续. . . */
