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

.第五次实验报告顺序栈、链栈的插入和删除一 需求分析1、 在演示程序中，出现的元素以数字出现定义为int型，2、 演示程序在计算机终端上，用户在键盘上输入演示程序中规定的运算命令，相应的输入数据和运算结果显示在终端上3、顺序栈的程序执行的命令包括如下： （1） 定义结构体 （2） 顺序栈的初始化及创建 （3） 元素的插入 （4） 元素的删除 （5） 顺序栈的打印结果3、 链栈的程序执行的命令包括如下： （1） 定义结构体 （2） 链栈的初始化及创建 （3） 元素的插入 （4） 元素的删除 （5）链栈的打印结果二 概要设计1、顺序栈可能需要用到有序表的抽象数据类型定义：ADT List数据对象:D=ai|aiElemL, i=1,2,.,n, n0数据关系: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|aiElemL, i=1,2,.,n, n0数据关系:R1=|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 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(%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=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;iS.top-S.base;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 #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;主函数（方傲侠）#includeBase.h#includeconstruction.h#includeLinkStack_operation.cint 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;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(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 #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执行入栈操作，选择输