顺序栈、链栈的插入和删除实验报告

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

2、象：D=ai|ai ElemL, i=1,2，,n, n 0 数据关系：R1=|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 D, i=2,.,n 基本操作：LinkStack(SqStack &S)操作结果：构造一个空栈St

3、atus 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

4、/ 存储空间分配增量typedef structint *base;/ 在构造栈之前和销毁之后， base 的值为 NULLint *top;/ 栈顶指针int stacksize;/ 当前已分配的存储空间，以元素为单位SqStack#includeBase.h 主函数#includeconstruction.h#includestack_operation.cint main()SqStack S;int choice,e;S=InitStack();S=Input_Sq(S);printf( 请选择执行的操作，输入 1 执行入栈操作，输入 2 执行出栈操作 choice=);scanf(%

5、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 * size

6、of(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=S.stacksize)/ 判断栈是否为满， 追加存储 空间S.base=(int*)realloc(S.base,(S.stacksize+STACKINCREMEN T)*size

7、of(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;iS.top-S.base;

8、i+)S.top-;printf(%5d,*S.top);printf(n);库函数* Base.h ( 程序名 ) */#include#include#include /* malloc() 等 */#include /* INT_MAX 等 */#include /* EOF(Z或 F6),NULL */#include /* atoi() */#include /* eof() */#include /* floor(),ceil(),abs() */#include /* exit() */* 函数结果状态代码 */#define TRUE 1#define FALSE 0#defi

9、ne 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,*LinkS

10、tack; 主函数 #includeBase.h #includeconstruction.h #includeLinkStack_operation.c int main()LinkStack S;int choice,e;S=Creatlist_Stack();printf( 请选择执行的操作，输入 执行出栈操作 choice=);scanf(%d,&choice);switch(choice)case 1:1 执行入栈操作，输入 2e=);printf( 请输入插入元素的值 scanf(%d,&e);S=Push(S,e);printf( 执行操作入栈后的线性栈为 ); Print_St

11、ack(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

12、,&S-data);for(i=1;inext=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(

13、LinkStack S)while(S)printf(%5d,S-data);S=S-next;printf(n); 库函数* Base.h ( 程序名 ) */#include#include#include /* malloc() 等 */#include /* INT_MAX 等 */#include /* EOF(Z或 F6),NULL */#include /* atoi() */#include /* eof() */#include /* floor(),ceil(),abs() */#include /* exit() */* 函数结果状态代码 */#define TRUE 1

14、#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 2 3 4 ，请输 入执行语句，选择输入 1 执行入栈操作，选择输入 2 执行出 栈操作 choice=2, 执行出栈操