《数据结构》课程实验报告学院：应用科技学院班级：09电子信息工程姓名：苏伟华学号：120352009006实验设备：计算机1台,Microsoft Visual C＋＋ 6.0 软件实验日期：2011年4月20日实验项目名称栈的基本操作实验目的1)熟悉栈的定义和栈的基本操作。

2)掌握顺序存储栈和链接存储栈的基本运算。

3)加深对栈结构的理解．逐步培养解决实际问题的能力。

实验要求：1.编写栈的基本操作函数（分别用顺序和链接两种方式实现）。

⑴--顺序栈的基本操作函数①进栈函数 int Push(SqStack &S, int e);②出栈函数 int Pop(SqStack &S,int &e);③输出栈元素 void OutputStack(SqStack &S);④取栈顶元素 int GetTop(SqStack S,int &e);--调用上述函数实现下列操作，操作步骤如下。

①调用进栈函数建立一个栈。

②读取栈顶元素。

③从栈中删除元素。

④输出栈中的所有元素。

⑵--链栈的基本操作函数①进栈函数 LinkStack PushStack(LinkStack top,int x);//进栈函数②出栈函数 LinkStack PopStack(LinkStack top);③输出栈元素 void Print();④取栈顶元素int GetStackTop(LinkStack top);--调用上述函数实现下列操作，操作步骤如下。

①调用进栈函数建立一个栈。

②读取栈顶元素。

③从栈中删除元素。

④输出栈中的所有元素。

实验内容(包括步骤)：1.⑴顺序栈的存储结构typedef struct{int *base;int *top;int stacksize;}SqStack;⑵程序中的主要函数及功能的说明int InitStack(SqStack &S);int GetTop(SqStack S,int &e);int Push(SqStack &S, int e);int Pop(SqStack &S,int &e);void OutputStack(SqStack &S);⑶主程序模块switch(m) {case '1':printf("\n");system("CLS");printf("请输入要进栈的元素个数是:");scanf("%d",&a);printf("\n请输入要进栈的%d个元素:",a); for(b=0;b<a;b++) {scanf("%d",&c);Push(s,c); }printf("\n输出的栈为:");OutputStack(s);break;case '2': printf("\n");system("CLS");GetTop(s,c);printf("\n栈顶元素为:%d",c);printf("\n输出的栈为:");OutputStack(s);break;case '3': printf("\n");system("CLS");Pop(s,c);printf("\n删除的栈顶元素:%d",c);printf("\n输出的栈为:");OutputStack(s);printf("\n");break;case '4':break;default: printf("\n");system("CLS");printf("输入的数字有错，请重新选择!\n");break;}getchar();}while(m!='4');2.(1) 链栈的存储结构typedef struct SNode{int data;struct SNode *next;}SNode,*LinkStack;LinkStack top;⑵程序中的主要函数及功能说明LinkStack PushStack(LinkStack top,int x);//进栈函数LinkStack PopStack(LinkStack top);//出栈函数bool IsEmpty();int GetStackTop(LinkStack top);//读取栈顶元素void Print();//输出栈元素（3）主程序模块switch(m){case '1':printf("\n");system("CLS");top=NULL;printf("\n栈已置空!");break;case '2': printf("\n");system("CLS");printf("\n请输入要进栈的元素个数是:"); scanf("%d",&a);printf("\n请输入要进栈的%d个元素:",a); for(b=0;b<a;b++) {scanf("%d",&x);top=PushStack(top,x); }printf("进栈已完成！\n");printf("\n输出栈为:");Print();break;case '3':printf("\n");system("CLS");printf("\n操作之前的输出栈为:");Print();top=PopStack(top);printf("\n操作过后的输出栈为:");Print();break;case '4':printf("\n");system("CLS");printf("\n输出栈为:");Print();if(top!=NULL)printf("\n栈顶元素是：%d\n",GetStackTop(top)); elseprintf("\n栈是空的，没有元素！");break;case '5':break;default:printf("\n");system("CLS");printf("\n输入的字符不对，请重新输入!");break; }调试与结果测试：⑴##############顺序栈的基本操作################## *********** 1.创建和输出栈的元素**************; *********** 2.取栈顶元素********************** *********** 3.删除栈顶元素******************** *********** 4.退出程序************************ ################################################ ①请选择一个字符:1请输入要进栈的元素个数是:5请输入要进栈的5个元素:2 9 13 26 39输出栈为：39<- 26<- 13<- 9<- 2②请选择一个字符:2栈顶元素为:39③请选择一个字符:3删除的栈顶元素:输出栈为：26<- 13<- 9<- 2④请选择一个字符:4press any key to continue⑵###############链栈的基本操作################## ××××××××1.置空栈××××××××××××××××××2.进栈××××××××××××××××××3.退栈×××××××××××××××××××4.取栈顶元素××××××××××××××××5.退出程序×××××××××##############################################①请选择一个字符：1栈已置空!②请选择一个字符：2请输入要进栈的元素个数是:5请输入要进栈的5个元素:1 9 15 21 32输出栈为:32<- 21<- 15<- 9<- 1③请选择一个字符：3操作之前的输出栈为:32<- 21<- 15<- 9<- 1操作过后的输出栈为:21<- 15<- 9<- 1④请选择一个字符：4输出栈为:21<- 15<- 9<- 1栈顶元素是：21⑤请选择一个字符：5press any key to continue代码注释://顺序栈的基本操作#include<stdio.h>#include<stdlib.h>#include<malloc.h>#define error 0#define ok 1#define OVERFLOW -2#define STACK_INIT_SIZE 100;//栈内存的初始分配量，以sizeof(ElemType)为单位#define STACKINCREMENT 10;//栈内存的分配增量，以sizeof(ElemType)为单位typedef int ElemType;typedef struct{int *base;////存储空间的基址，数据元素的数据类型约定为ElemTypeint *top;////表示栈顶，如果top==base，表示空栈int stacksize; //当前分配的存储容量，以sizeof(ElemType) 为单位}SqStack;//************************************************************************* ********************************************************//*******************************************函数的声明部分************************************************************************//************************************************************************* *******************************************************int InitStack(SqStack &S);//栈的初始化int GetTop(SqStack S,int &e);//初始条件：栈S已存在且非空。