用顺序结构表示栈并实现栈的各种基本操作.doc

栈的顺序表示和实现2.2基础实验
2.2.1实验目的
（1）掌握栈的顺序表示和实现
（2）掌握栈的链式表示和实现
（3）掌握队列的顺序表示和实现
（4）掌握队列的链式表示和实现
2.2.2实验内容
实验一：栈的顺序表示和实现
【实验内容与要求】
编写一个程序实现顺序栈的各种基本运算，并在此基础上设计一个主程序，完成如下功能：
（1）初始化顺序栈
（2）插入元素
（3）删除栈顶元素
（4）取栈顶元素
（5）遍历顺序栈
（6）置空顺序栈
【知识要点】
栈的顺序存储结构简称为顺序栈,它是运算受限的顺序表。
对于顺序栈，入栈时，首先判断栈是否为满，栈满的条件为：p->top==MAXNUM-1，栈满时，不能入栈;否则出现空间溢出，引起错误，这种现象称为上溢。
出栈和读栈顶元素操作，先判栈是否为空，为空时不能操作，否则产生错误。通常栈空作为一种控制转移的条件。
注意：
（1）顺序栈中元素用向量存放
（2）栈底位置是固定不变的，可设置在向量两端的任意一个端点
（3）栈顶位置是随着进栈和退栈操作而变化的，用一个整型量top（通常称top为栈顶指针）来指示当前栈顶位置
【实现提示】
/*定义顺序栈的存储结构*/
typedefstruct{
ElemTypestack[MAXNUM];
inttop;
}SqStack;
/*初始化顺序栈函数*/
voidInitStack(SqStack*p)
{q=(SqStack*)malloc(sizeof(SqStack)/*申请空间*/)
/*入栈函数*/
voidPush(SqStack*p,ElemTypex)
{if(p->top<MAXNUM-1)
{p->top=p->top+1;/*栈顶+1*/
p->stack[p->top]=x;}/*数据入栈*/
}
/*出栈函数*/
ElemTypePop(SqStack*p)
{x=p->stack[p->top];/*将栈顶元素赋给x*/
p->top=p->top-1;}/*栈顶-1*/
/*获取栈顶元素函数*/
ElemTypeGetTop(SqStack*p)
{x=p->stack[p->top];}
/*遍历顺序栈函数*/
voidOutStack(SqStack*p)
{for(i=p->top;i>=0;i--)
printf("第%d个数据元素是：%6d\n",i,p->stack[i]);}
/*置空顺序栈函数*/
voidsetEmpty(SqStack*p)
{p->top=-1;}
【参考程序】
#include<stdio.h>
#include<stdlib.h>
#defineMAXNUM20
#defineElemTypeint
/*定义顺序栈的存储结构*/
typedefstruct
{ElemTypestack[MAXNUM];
inttop;
}SqStack;
/*初始化顺序栈*/
voidInitStack(SqStack*p)
{if(!p)
printf("Eorror");
p->top=-1;
}
/*入栈*/
voidPush(SqStack*p,ElemTypex)
{if(p->top<MAXNUM-1)
{p->top=p->top+1;
p->stack[p->top]=x;
}
else
printf("Overflow!\n");
}
/*出栈*/
ElemTypePop(SqStack*p)
{ElemTypex;
if(p->top!=0)
{x=p->stack[p->top];
printf("以前的栈顶数据元素%d已经被删除！\n",p->stack[p->top]);
p->top=p->top-1;
return(x);
}
else
{printf("Underflow!\n");
return(0);
}
}
/*获取栈顶元素*/
ElemTypeGetTop(SqStack*p)
{ElemTypex;
if(p->top!=0)
{x=p->stack[p->top];
return(x);
}
else
{printf("Underflow!\n");
return(0);
}
}
/*遍历顺序栈*/
voidOutStack(SqStack*p)
{inti;
printf("\n");
if(p->top<0)
printf("这是一个空栈！");
printf("\n");
for(i=p->top;i>=0;i--)
printf("第%d个数据元素是：%6d\n",i,p->stack[i]);
}
/*置空顺序栈*/
voidsetEmpty(SqStack*p)
{
p->top=-1;
}
/*主函数*/
main()
{SqStack*