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

1、第五次实验报告顺序栈、链栈的插入和删除1、在演示程序中，出现的元素以数字出现定义为 int型，2、演示程序在计算机终端上，用户在键盘上输入演示程序中规定的运算命令, 相应的输入数据和运算结果显示在终端上3、顺序栈的程序执行的命令包括如下：(1)(2)(3)(4)(5)定义结构体顺序栈的初始化及创建元素的插入元素的删除顺序栈的打印结果3、链栈的程序执行的命令包括如下：(1)(2)(3)(4)(5)定义结构体链栈的初始化及创建元素的插入元素的删除链栈的打印结果二概要设计1、顺序栈可能需要用到有序表的抽象数据类型定义:ADT List数据对象：D=ai|ai ElemL, i=1,2，,n, n数据

2、关系：R仁<ai-1,ai>|ai-1,ai D, i=2,.,n 基本操作:In itStack(SqStack &S)操作结果：构造一个空栈Push(L,e)操作结果：插入元素e为新的栈顶元素Status Pop (SqStack &S)操作结果：删除栈顶元素ADT List ;2、链栈可能需要用到有序表的抽象数据类型定义:ADT List数据对象：D=ai|ai ElemL, i=1,2，,n, n D, i=2,.,n 数据关系：R仁<ai-1,ai>|ai-1,ai基本操作:Lin kStack(SqStack &S)操作结果：构造一个

3、空栈Status P ush(L,e)操作结果：插入元素e为新的栈顶元素Status Pop (SqStack &S)操作结果：删除栈顶元素ADT List ;3、顺序栈程序包含的主要模块:(1) 已给定的函数库:(2)顺序栈结构体:(3)顺序栈初始化及创建：(4)元素插入(5)元素删除(6)主程序:4、链栈程序包含的主要模块:(1)已给定的函数库:(2) 链栈结构体:(3) 链栈初始化及创建：兀素插入(5)元素删除(6)主程序：三详细设计线性栈:结构体(邱建美)#defineSTACK INIT SIZE 100/存储空间初始分配量 #defi ne STACKINCREMENT 1

4、0/存储空间分配增量 typ edef structint *base;/ 在构造栈之前和销毁之后，base的值为NULLint *top;/栈顶指针int stacksize;/当前已分配的存储空间，以元素为单位SqStack#i nclude"Base.h"主函数(张涛)#in clude"c on structi on .h" #in clude"stack_ op eratio n.c" int mai n()SqStack S;int choiceeS=I nitStackO;S=I np ut_Sq(S);printf（&

5、quot;请选择执行的操作，输入1执行入栈操作，输入2执行出栈操作choice="）;sca nf("%d", &choice);switch(choice) case 1:printf（”请输入插入元素的值e="）;sca nf("%d", &e);S=P ush(S,e);printf（”执行入栈操作后的线性栈为"）;Prin t_Stack(S);break;case 2:S=Pop(S);printf（”执行出栈操作后的线性栈为"）;Prin t_Stack(S);break;default

6、 : printf(”您输入的值不合法"）;线性栈的创建（郑峰）SqStack In itStack()/线性栈的创建SqStack S;S.base=(i nt*)malloc(STACK_INIT_SIZE* sizeof(i nt);/分配存储空间if(!S.base)exit(OVERFLOW);/存储分配失败S.t op 二S.base;S.stacksize二STACK_INIT_SIZE;retur n S;输入函数（胡高飞）SqStack Inpu t_Sq(SqStack S)/ 输入函数int n,i;printf（"请输入元素个数n二”）;sea nf

7、("%d",&n);prin tf（"请输入d个元素",n）;for(i=0;i vn ;i+)sea nf("%d",S.to p);S.t op+;retur n S;进栈函数（郑峰）SqStack P ush(SqStack S,i nt e)/ 进栈函数if(S.t op-S.base>=S.stacksize)/判断栈是否为满，追加存储空S.base=(i nt*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(i nt);if(!S.base)exit(O

8、VERFLOW);/存储分配失败S.to p=S.base+S.stacksize;S.stacksize+二STACKINCREMENT;*S.to P+二e;/ 插入元素retur n S;出栈函数（邱建美）SqStack Pop (SqStack S)/ 删除函数int e;if(S.t op二二S.base)printf（”线性栈为空"）;e=*-S.t op;retur n S;输出函数（方傲侠）void Prin t_Stack(SqStack S)/打印函数int i;while(S.base!二S.t op)for(i=0;ivS.t op-S.base;i+)S.t

9、op-;p ri ntf("%5d",*S.to p);prin tf("n");库函数* Base.h (程序名)*/#in cludevstri ng.h>#in cludevct yp e.h>#in cludevmalloc.h> /* malloc()等*/#includevlimits.h> /* INT MAX等*/#i ncludevstdio.h> /* EOF(=Z或 F6),NULL */#i ncludevstdlib.h> /* atoi() */#i ncludevio.h> /* e

10、of() */#i ncludevmath.h> /* floor(),ceil(),abs() */#in clude vp rocess.h> /* exit() */*函数结果状态代码*/#defi ne TRUE 1#defi ne FALSE 0#defi ne OK 1 #defi ne ERROR 0 #defi ne INFEASIBLE -1 /* #define OVERFLOW -2 因为在 math.h 中已定义 OVERFLOW值为是函数的类型，其值是函数结果状3,故去掉此行*/ typ edef int Status; /* Status态代码，如OK等

11、*/typ edef int Boolea n; /* Boolea n是布尔类型，其值是TRUE或FALSEl链栈程序:结构体（邱建美）typ edef struct SNode/建立链表结构体int data;struct SNode *n ext;SNode,*Li nkStack;主函数（方傲侠）#i nclude"Base.h" #in clude"c on structio n.h" #i nclude"Li nkStack_ op eratio n.c" int mai n()default : printf(”您输入的

12、值不合法n"）;Lin kStack S;int choiceeS=Creatlist_Stack();printf（"请选择执行的操作，输入1执行入栈操作，输入2执行出栈操作choice="）;sca nf("%d", &choice);switch(choice)case 1:printf（”请输入插入元素的值e="）;sca nf("%d", &e);S=Pu sh(S,e);printf（”执行操作入栈后的线性栈为"）;Prin t_Stack(S);break;case 2:S=

13、Pop(S);printf（”执行出栈操作后的线性栈为"）;Prin t_Stack(S);break;创建一个链栈创建链栈函数（张涛）Li nkStack Creatlist_Stack()/Lin kStack S;Lin kStack P;int i,n;S=(Li nkStack)malloc(sizeof(SNode);S->next二NULL;/*先建立一个链栈*/printf（"请输入元素个数n二”）;sca nf("%d",&n);prin tf（"请输入d个数据n", n）;i=0;sca nf(&qu

14、ot;%d", &S->data);生成新结点*/for(i=1;i vn;+i)P=(Li nkStack)malloc(sizeof(SNode); /*P-> next二S;S二P;scanf("%d",&S->data); /*输入元素值 */retur n S;入栈函数（方傲侠）Li nkStack Push(Li nkStack S,i nt e)Lin kStack P;if(S=NULL)return ERROR;P=(Li nkStack)malloc(sizeof(SNode);P->data二e;P-&

15、gt; next二S;S二P;retur n S;出栈函数（胡高飞）Li nkStack Pop(Lin kStack S)Lin kStack P,Q;P=S;S=S->n ext;free( P);retur n S;输出函数（郑峰）void Prin t_Stack(Li nkStack S)while(S)prin tf("%5d",S->data);S=S->n ext;prin tf("n");库函数* Base.h (程序名)*/#in cludevstri ng.h>#in cludevct yp e.h>#

16、in cludevmalloc.h> /* malloc()等*/#includevlimits.h> /* INT MAX等*/#i ncludevstdio.h> /* EOF(=Z或 F6),NULL */#i ncludevstdlib.h> /* atoi() */#i ncludevio.h> /* eof() */#i nclude<math.h> /* floor(),ceil(),abs() */ #in elude <p rocess.h> /* exit() */*函数结果状态代码*/ #defi ne TRUE 1

17、#defi ne FALSE 0#defi ne OK 1 #defi ne ERROR 0 #defi ne INFEASIBLE -1 /* #define OVERFLOW -2 因为在 math.h 中已定义 OVERFLOW值为是函数的类型，其值是函数结果状3,故去掉此行*/ typ edef int Status; /* Status态代码，如OK等*/typ edef int Boolea n; /* Boolea n是布尔类型，其值是TRUE或FALSEl四调试分析: 输出函数用了语句 S->next!二NULL改正：语句S! =NULL五用户手册:看提示内容六测试结果线性栈:1）请输入元素的个数：4，请输入4个数据1 2 3 4，请输入执行语句，选择输入1执行入栈操作，选择输入2执行出栈操作choice=1 , 请输入插入元素的值e=6,执行入栈操作后的线性栈为6 4 3 2 1 2）请输入