数据结构栈的基本操作,进栈,出栈

第五次实验报告——顺序栈、链栈的插入和删除一 需求分析1、在演示程序中，出现的元素以数字出现定义为 int 型，2、演示程序在计算机终端上，用户在键盘上输入演示程序中规定的运算命令，相应的输入数据和运算结果显示在终端上3、顺序栈的程序执行的命令包括如下：1）定义结构体2）顺序栈的初始化及创建3）元素的插入4）元素的删除5）顺序栈的打印结果3、链栈的程序执行的命令包括如下：1）定义结构体2）链栈的初始化及创建3）元素的插入4）元素的删除5）链栈的打印结果概要设计1、顺序栈可能需要用到有序表的抽象数据类型定义：ADTList{数据对象 :D={ai|ai ∈ElemL,i=1,2,...,n,n ≥0}数据关系 :R1={<ai-1,ai>|ai-1,ai ∈D,i=2,...,n}基本操作：InitStack(SqStack&S)操作结果：构造一个空栈Push(L,e)操作结果：插入元素 e为新的栈顶元素StatusPop(SqStack&S)操作结果：删除栈顶元素}ADTList ；2、链栈可能需要用到有序表的抽象数据类型定义：ADTList{数据对象 :D={ai|ai ∈ElemL,i=1,2,...,n,n ≥0}数据关系 :R1={<ai-1,ai>|ai-1,ai ∈D,i=2,...,n}基本操作：LinkStack(SqStack&S)操作结果：构造一个空栈StatusPush(L,e)操作结果：插入元素 e为新的栈顶元素StatusPop(SqStack&S)操作结果：删除栈顶元素}ADTList ；3、顺序栈程序包含的主要模块：(1) 已给定的函数库：2）顺序栈结构体：3）顺序栈初始化及创建:(4) 元素插入(5) 元素删除（6）主程序：、链栈程序包含的主要模块：(1) 已给定的函数库：2）链栈结构体：3）链栈初始化及创建:(4) 元素插入(5) 元素删除(6) 主程序：三 详细设计线性栈：结构体（邱建美）#defineSTACK_INIT_SIZE100// 存储空间初始分配量#defineSTACKINCREMENT10// 存储空间分配增量typedefstruct{int*base;// 在构造栈之前和销毁之后， base的值为 NULLint*top;// 栈顶指针intstacksize;// 当前已分配的存储空间，以元素为单位}SqStack#include"Base.h"主函数（张涛）#include"construction.h"#include"stack_operation.c"intmain(){SqStackS;intchoice,e;S=InitStack();S=Input_Sq(S);printf(" 请选择执行的操作，输入 1执行入栈操作，输入 2执行出栈操作 choice=");scanf("%d",&choice);switch(choice){case1:{printf(" 请输入插入元素的值 e=");scanf("%d",&e);S=Push(S,e);printf(" 执行入栈操作后的线性栈为 ");Print_Stack(S);};break;case2:{S=Pop(S);printf(" 执行出栈操作后的线性栈为 ");Print_Stack(S);};break;default:printf(" 您输入的值不合法 ");}}线性栈的创建（郑峰）SqStackInitStack()// 线性栈的创建{SqStackS;S.base=(int*)malloc(STACK_INIT_SIZE *sizeof(int));// 分配存储空间if(!S.base)exit(OVERFLOW);// 存储分配失败S.top=S.base;S.stacksize=STACK_INIT_SIZE;returnS;}输入函数（胡高飞）SqStackInput_Sq(SqStackS)// 输入函数{intn,i;printf(" 请输入元素个数 n=");scanf("%d",&n);printf(" 请输入%d个元素",n);for(i=0;i<n;i++){scanf("%d",S.top);S.top++;}returnS;}进栈函数（郑峰）SqStackPush(SqStackS,inte)//{

进栈函数if(S.top-S.base>=S.stacksize)//

判断栈是否为满， 追加存储空间{S.base=(int*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(int));if(!S.base)exit(OVERFLOW);// 存储分配失败S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}*S.top++=e;// 插入元素returnS;}出栈函数（邱建美）SqStackPop(SqStackS)// 删除函数{inte;if(S.top==S.base)printf(" 线性栈为空 ");e=*--S.top;returnS;}输出函数(方傲侠)voidPrint_Stack(SqStackS)// 打印函数{inti;while(S.base!=S.top){for(i=0;i<S.top-S.base;i++){S.top--;printf("%5d",*S.top);}printf("\n");}库函数*Base.h( 程序名)*/#include<string.h>#include<ctype.h>#include<malloc.h>/*malloc() 等*/#include<limits.h>/*INT_MAX 等*/#include<stdio.h>/*EOF(=^Z 或F6),NULL*/#include<stdlib.h>/*atoi()*/#include<io.h>/*eof()*/#include<math.h>/*floor(),ceil(),abs()*/#include<process.h>/*exit()*//* 函数结果状态代码 */#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1/*#defineOVERFLOW-2 因为在 math.h中已定义 OVERFLOW的值为3,故去掉此行 */typedefintStatus;/*Status 是函数的类型 ,其值是函数结果状态代码，如 OK等*/typedefintBoolean;/*Boolean 是布尔类型 ,其值是 TRUE或FALSEl链栈程序：结构体(邱建美）typedefstructSNode// 建立链表结构体{intdata;structSNode*next;}SNode,*LinkStack;主函数（方傲侠）#include"Base.h"#include"construction.h"#include"LinkStack_operation.c"intmain(){LinkStackS;intchoice,e;S=Creatlist_Stack();printf(" 请选择执行的操作，输入 1执行入栈操作，输入 2执行出栈操作 choice=");scanf("%d",&choice);switch(choice){case1:{printf(" 请输入插入元素的值 e=");scanf("%d",&e);S=Push(S,e);printf(" 执行操作入栈后的线性栈为 ");Print_Stack(S);};break;case2:{S=Pop(S);printf(" 执行出栈操作后的线性栈为 ");Print_Stack(S);};break;default:printf(" 您输入的值不合法 \n");}}创建链栈函数（张涛）LinkStackCreatlist_Stack()// 创建一个链栈{LinkStackS;LinkStackP;inti,n;S=(LinkStack)malloc(sizeof(SNode));S->next=NULL;/* 先建立一个链栈 */printf(" 请输入元素个数 n=");scanf("%d",&n);printf(" 请输入%d个数据\n",n);i=0;scanf("%d",&S->data);for(i=1;i<n;++i){P=(LinkStack)malloc(sizeof(SNode));/*

生成新结点

*/P->next=S;S=P;scanf("%d",&S->data);/*

输入元素值

*/}returnS;}入栈函数（方傲侠）LinkStackPush(LinkStackS,inte){LinkStackP;if(S==NULL)returnERROR;P=(LinkStack)malloc(sizeof(SNode));P->data=e;P->next=S;S=P;returnS;}出栈函数（胡高飞）LinkStackPop(LinkStackS){LinkStackP,Q;P=S;S=S->next;free(P);returnS;}输出函数（郑峰）voidPrint_Stack(LinkStackS){while(S){printf("%5d",S->data);S=S->next;}printf("\n");}库函数*Base.h(程序名#include<string.h>#include<ctype.h>

)*/#include<malloc.h>/*malloc()

等

*/#include<limits.h>/*INT_MAX

等

*/#include<stdio.h>/*EOF(=^Z

或

F6),NULL*/#include<stdlib.h>/*atoi()*/#include<io.h>/*eof()*/#include<math.h>/*floor(),ceil(),abs()*/#include<process.h>/*exit()*//* 函数结果状态代码 */#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1/*#defineOVERFLOW-2 因为在 math.h中已定义 OVERFLOW的值为3,故去掉此行 */typedefintStatus;/*Status 是函数的类型 ,其值是函数结果状态代码，如 OK等*/typedefintBoolean;/*Boolean 是布尔类型 ,其值是 TRUE或FALSEl四调试分析:输出函数用了语句 S->next!=NULL改正：语句 S！=NULL五用户手册:看提示内容六 测试结果线性栈：1）请输入元素的个数： 4，请输入 4个数据 1234 ，请输入执行语句，选择输入 1执行入栈操作，选择输入 2执行出栈操作 choice=1，请输入插入元素的值 e=6，执行入栈操作后的线性栈为 643212）请输入元素的个数： 4，请输入 4个数据 1234 ，请输入执行语句，选择输入 1执行入栈操