数据结构出栈、入栈实验报告.doc

序号：数据结构 题 目 数据结构出栈、入栈实验报告学 院 计算机学院 专 业 计算接科学与技术 年级班别 12级3 班 学 号 3112005895 学生姓名 朱靖宇 指导教师 曾孜 思路理论设计难度系数代码总成绩20 14 年 7 月 6 日1.实验目的1、 熟悉栈的定义和栈的基本操作。2、 掌握顺序存储栈和链接存储栈的基本运算。3、 加深对栈结构的理解，逐步培养解决实际能力问题的能力2.需求分析1、 栈的建立输入形式和输入值的范围：输入若干个正整数，用空格隔开，以0结束。2、 菜单操作根据提示进行操作。3.概要设计（1）为了实现上述程序功能，需要第一一个简化的链表抽象数据类型：ADT LinkList 数据对象：D=ai|aiIntegerSet,i=0,1,2,n,n0 数据关系：R1=|ai-1,ai1D,i=2,n 基本操作：进栈函数 int Push(SqStack *S, int e) 出栈函数 int Pop(SqStack *S,int *e) 输出栈元素 void OutputStack(SqStack *S)输出栈中的所有元素。4.详细设计采用链表实现概要设计中的定义的抽象数据类型，有关数据数据类型和伪码算法定义如下：（1）类型定义 typedef struct int *base;int *top; int stacksize; SqStack （2）基本操作的伪码算法/*构造一个空栈*/int InitStack(SqStack &S)S.base=(int *)malloc(STACK_INIT_SIZE*sizeof(int);if(!S.base) return 0;S.top=S.base;S.stacksize=STACK_INIT_SIZE ;return 1;int GetTop(SqStack S,int &e) if(S.top=S.base) return 0;e=*(S.top-1);return 1;/*入栈函数*/int Push(SqStack &S,int e) /插入元素e为新的栈顶元素if(S.top-S.base=S.stacksize) S.base=(int *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(int); if(!S.base) return 0; S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; *S.top+=e; return 1;/*出栈函数*/int Pop(SqStack &S,int &e) if(S.top=S.base) return 0;e=*-S.top;return 1;/*输出函数*/int OutputStack(SqStack &S) /输出栈中所有元素int *p;int i;p=S.top-1;printf(栈中的元素有：);for(i=0;iS.top-S.base;i+)printf( %d,*p);p-;return 1;5.使用说明程序名为实验1.exe，程序执行过程如下：运行程序显示如下菜单：printf(n);printf(ttt 顺序栈操作 n); printf(ttt*n); printf(ttt* 0.退出程序! *n); printf(ttt* 1.读取栈顶元素 *n); printf(ttt* 2.删除栈顶元素 *n); printf(ttt* 3.输出栈中所有元素 *n);printf(ttt*n); printf(请选择菜单号(0-3):);用户输入03的数字，选择执行相应的功能。每执行一次功能，就会显示执行的结果以及执行后顺寻栈的内容。6.测试结果7. 附录#include#include#include#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef structint *base;int *top;int stacksize;SqStack;/*构造一个空栈*/int InitStack(SqStack &S)S.base=(int *)malloc(STACK_INIT_SIZE*sizeof(int);if(!S.base) return 0;S.top=S.base;S.stacksize=STACK_INIT_SIZE ;return 1;int GetTop(SqStack S,int &e) if(S.top=S.base) return 0;e=*(S.top-1);return 1;/*入栈函数*/int Push(SqStack &S,int e) /插入元素e为新的栈顶元素if(S.top-S.base=S.stacksize) S.base=(int *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(int); if(!S.base) return 0; S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; *S.top+=e; return 1;/*出栈函数*/int Pop(SqStack &S,int &e) if(S.top=S.base) return 0;e=*-S.top;return 1;/*输出函数*/int OutputStack(SqStack &S) /输出栈中所有元素int *p;int i;p=S.top-1;printf(栈中的元素有：);for(i=0;iS.top-S.base;i+)printf( %d,*p);p-;return 1;void main()SqStack S;int a,b,e;char ch;InitStack(S); printf(请输入要进栈的元素个数是: );scanf(%d,&a); printf(请输入要进栈的元素: ); for(b=0;ba;b+)scanf(%d,&e);Push(S,e); OutputStack(S);printf(n);doprintf(n);printf(ttt 顺序栈操作 n); printf(ttt*n); printf(ttt* 0.退出程序! *n); printf(ttt* 1.读取栈顶元素 *n); printf(ttt* 2.删除栈顶元素 *n); printf(ttt* 3.输出栈中所有元素 *n);printf(ttt*n); printf(请选择菜单号(0-3):);getchar();scanf(%c,&ch); switch(ch) case 1: GetTop(S,e); printf(栈顶元素是: %dn,e); OutputStack(S); printf(n); break;case 2: Pop(S,e); printf(删除的栈顶元素是: