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

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

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

3、nkStack(SqStack &S)操作结果：构造一个空栈Status Push(L,e)操作结果：插入元素e 为新的栈顶元素Status Pop(SqStack &S)操作结果：删除栈顶元素ADT List ；3、顺序栈程序包含的主要模块：(1) 已给定的函数库：（ 2）顺序栈结构体：（ 3）顺序栈初始化及创建 :(4) 元素插入(5) 元素删除;.'.（6）主程序：4 、链栈程序包含的主要模块：(1) 已给定的函数库：（ 2）链栈结构体：（ 3）链栈初始化及创建 :(4) 元素插入(5) 元素删除(6) 主程序：三 详细设计线性栈：结构体（邱建美）#define

4、STACK_INIT_SIZE 100/存储空间初始分配量#define STACKINCREMENT 10/存储空间分配增量typedef structint *base;/在构造栈之前和销毁之后，base 的值为 NULLint *top;/栈顶指针int stacksize;/当前已分配的存储空间，以元素为单位SqStack#include"Base.h"主函数（张涛）;.'.#include"construction.h"#include"stack_operation.c"int main()SqStack S;in

5、t choice,e;S=InitStack();S=Input_Sq(S);printf("请选择执行的操作，输入1 执行入栈操作，输入2 执行出栈操作 choice=");scanf("%d",&choice);switch(choice)case 1:printf("请输入插入元素的值e=");scanf("%d",&e);S=Push(S,e);printf("执行入栈操作后的线性栈为");Print_Stack(S);break;case 2:;.'.S=Pop

6、(S);printf("执行出栈操作后的线性栈为");Print_Stack(S);break;default : printf("您输入的值不合法 ");线性栈的创建（郑峰）SqStack InitStack()/线性栈的创建SqStack S;S.base=(int*)malloc(STACK_INIT_SIZE* sizeof(int);/分配存储空间if(!S.base)exit(OVERFLOW);/ 存储分配失败S.top=S.base;S.stacksize=STACK_INIT_SIZE;return S;输入函数（胡高飞）SqStack

7、 Input_Sq(SqStack S)/输入函数;.'.int n,i;printf("请输入元素个数n=");scanf("%d",&n);printf("请输入 %d个元素 ",n);for(i=0;i<n;i+)scanf("%d",S.top);S.top+;return S;进栈函数（郑峰）SqStack Push(SqStack S,int e)/进栈函数if(S.top-S.base>=S.stacksize)/判断栈是否为满，追加存储空间S.base=(int*)rea

8、lloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(int);if(!S.base);.'.exit(OVERFLOW);/ 存储分配失败S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+=e;/插入元素return S;出栈函数（邱建美）SqStack Pop(SqStack S)/删除函数int e;if(S.top=S.base)printf("线性栈为空 ");e=*-S.top;return S;输出函数 ( 方傲侠 )void Print_S

9、tack(SqStack S)/打印函数int i;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&l

10、t;stdio.h> /* EOF(=Z或 F6),NULL */#include<stdlib.h> /* atoi() */#include<io.h> /* eof() */#include<math.h> /* floor(),ceil(),abs() */#include<process.h> /* exit() */*函数结果状态代码*/#define TRUE 1#define FALSE 0;.'.#define OK 1#define ERROR 0#define INFEASIBLE -1/* #define O

11、VERFLOW -2因为在 math.h 中已定义 OVERFLOW的值为3, 故去掉此行 */typedef int Status; /* Status是函数的类型 , 其值是函数结果状态代码，如 OK等 */typedef int Boolean; /* Boolean是布尔类型 , 其值是TRUE或FALSEl链栈程序：结构体 ( 邱建美）typedef struct SNode/建立链表结构体int data;struct SNode *next;SNode,*LinkStack;主函数（方傲侠）#include"Base.h"#include"const

12、ruction.h"#include"LinkStack_operation.c"int main();.'.LinkStack S;int choice,e;S=Creatlist_Stack();printf("请选择执行的操作，输入1 执行入栈操作，输入2 执行出栈操作 choice=");scanf("%d",&choice);switch(choice)case 1:printf("请输入插入元素的值e=");scanf("%d",&e);S=Push

13、(S,e);printf("执行操作入栈后的线性栈为");Print_Stack(S);break;case 2:S=Pop(S);printf("执行出栈操作后的线性栈为");Print_Stack(S);break;.'.default : printf("您输入的值不合法 n");创建链栈函数（张涛）LinkStack Creatlist_Stack()/创建一个链栈LinkStack S;LinkStack P;int i,n;S=(LinkStack)malloc(sizeof(SNode);S->next=N

14、ULL;/*先建立一个链栈*/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); /*输入元素值 */;.'.return S;入栈函数

15、（方傲侠）LinkStack Push(LinkStack S,int e)LinkStack P;if(S=NULL)return ERROR;P=(LinkStack)malloc(sizeof(SNode);P->data=e;P->next=S;S=P;return S;出栈函数（胡高飞）LinkStack Pop(LinkStack S)LinkStack P,Q;P=S;S=S->next;free(P);.'.return S;输出函数（郑峰）void Print_Stack(LinkStack S)while(S)printf("%5d&qu

16、ot;,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>

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