第五次实验报告——顺序栈、链栈的插入和删除一需求分析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≥0}数据关系:R1={<ai-1,ai>|ai-1,ai ∈D, i=2,...,n }基本操作：InitStack(SqStack &S)操作结果：构造一个空栈Push(L,e)操作结果：插入元素e为新的栈顶元素Status Pop(SqStack &S)操作结果：删除栈顶元素}ADT List；2、链栈可能需要用到有序表的抽象数据类型定义：ADT List{数据对象:D={ai|ai∈ElemL, i=1,2,...,n, n≥0}数据关系:R1={<ai-1,ai>|ai-1,ai ∈D, i=2,...,n } 基本操作：LinkStack(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 STACK_INIT_SIZE 100//存储空间初始分配量#define STACKINCREMENT 10//存储空间分配增量typedef struct{int *base;//在构造栈之前和销毁之后，base的值为NULL int *top;//栈顶指针int stacksize;//当前已分配的存储空间，以元素为单位}SqStack#include"Base.h"主函数#include"construction.h"#include"stack_operation.c"int main(){SqStack S;int 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(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 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*)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;//插入元素return S;}出栈函数SqStack Pop(SqStack S)//删除函数{int e;if(S.top==S.base)printf("线性栈为空");e=*--S.top;return S;}输出函数void Print_Stack(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<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 OVERFLOW -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"construction.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(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=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); /* 输入元素值 */}return S;}入栈函数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",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() *//* 函数结果状态代码 */#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 1 2）请输入元素的个数：4，请输入4个数据 1 2 3 4，请输入执行语句，选择输入1执行入栈操作，选择输入2执行出栈操作choice=2,执行出栈操作后的线性栈为3 2 1链栈：1）请输入元素的个数：4，请输入4个数据 1 2 3 4，请输入执行语句，选择输入1执行入栈操作，选择输入2执行出栈操作choice=1，请输入插入元素的值e=6，执行入栈操作后的线性栈为6 4 3 2 1 2）请输入元素的个数：4，请输入4个数据 1 2 3 4，请输入执行语句，选择输入1执行入栈操作，选择输入2执行出栈操作choice=2,执行出栈操作后的线性栈为3 2 1。