实验二、堆栈详解.docx

实验二堆栈的应用一、实验目的（1）了解栈的定义。（2）理解栈的顺序存储结构。（3）实现进栈和出栈程序。二、实验内容栈是只能在表的一端—表尾进行插入和删除运算的线性表，表尾也称作栈顶（Top），表头也称为栈底(Bottom)。当表中没有元素时称为空栈。栈的顺序存储结构栈的顺序存储可用一维数组，用一个指针指示栈顶的位置。设栈的最大容量为maxsize，则用C语言来描述顺序存储结构的栈： #define maxsize 10int data[maxsize+1];int *top,k,d,num,x;其中，maxsize是栈可能达到的最大容量；data[0]为栈顶指针，栈空时data[0]为0；data[1]表示第一个进栈的元素；data[i]表第i个进栈的元素；data[data[0]]表栈顶元素。 当data[0]=maxsize时，表示栈满，如果再有元素进入时，则栈要溢出，称“上溢”；当data[0]=0时再作退栈运算，就要发生“下溢”。栈的基本运算把一个给定的元素x压入栈内。该过程称为进栈，它是在栈顶位置加一个新数据项，程序如下：voidpush_stack(x,s)int x;int s[maxsize+1]; {printf(压栈前：top=%d x=%d\n,s[0],x);if(s[0]==maxsize) printf(OVERFLOW\n);else {s[0]=s[0]+1;s[s[0]]=x;printf(压栈后：);printf(top=%d s[top]=%d\n,s[0],s[s[0]]);printf(\n); } }2）弹出栈顶元素。该过程称为出栈（Pop），它是从栈顶取出一个数据项紧接着这个数据项下面的数据项变为栈顶，程序如下：voidpop_stack(s)int s[maxsize+1]; {if(s[0]==0) printf(栈空！\n);else {s[0]=s[0]-1;printf(出栈的元素是：%d;当前栈顶是：%d,s[s[0]+1],s[0]); } }3）读栈顶元素。4）判断栈是否空。三、程序流程图（略）四、运行程序1）实验主程序#includestdio.h#define maxsize 10int data[maxsize+1]; /*data[0]-栈顶指针*/intk,d,num,x;voidpush_stack(x,s);voidpop_stack(s);main() {data[0]=0;pop_stack(data);printf(请输入数据个数:);scanf(%d,num);printf(num=%d\n,num);for(k=1;k=num;k++) {scanf(%d,x);push_stack(x,data); }printf(\n);printf(栈中元素为：);for(k=1;k=maxsize;k++)printf(%d-,data[k]);printf(\n); d=8;push_stack(d,data);printf(栈中元素为：);for(k=1;k=maxsize;k++)printf(%d|,data[k]);printf(\n);pop_stack(data);}voidpush_stack(x,s)int x;int s[maxsize+1]; {printf(压栈前：top=%d x=%d\n,s[0],x);if(s[0]==maxsize) printf(OVERFLOW\n);else {s[0]=s[0]+1;s[s[0]]=x;printf(压栈后：);printf(top=%d s[top]=%d\n,s[0],s[s[0]]);printf(\n); } }voidpop_stack(s)int s[maxsize+1]; {if(s[0]==0) printf(栈空！\n);else {s[0]=s[0]-1;printf(出栈的元素是：%d;当前栈顶是：%d,s[s[0]+1],s[0]); } }2）程序在Visual C ++下运行。1、先建项目。2、保存项目。3、编译并运行。五、运行窗口显示运行窗口输入数据：4输入实验数据：3 5 2 67运行结果六、小结1）实现对堆栈的应用。2）了解堆栈的定义。3)应用堆栈结构程序