数据结构实验——栈(附程序).doc

实验二 栈一、实验目的 1.了解栈的特性。 2.掌握栈的顺序表示和实现。 3.掌握栈的链式表示和实现。二、实验内容 实验2.1栈的顺序表示和实现 编写一个程序实现顺序栈的各种基本运算，并在此基础上设计一个主程序，完成如下功能： (1)初始化顺序栈。 (2)插入元素。 (3)删除栈顶元素。 (4)取栈顶元素。 (5)遍历顺序栈。 (6)置空顺序栈。 实验2. 2栈的链式表示和实现 编写一个程序实现链栈的各种基本运算，并在此基础上设计一个主程序，完成如下功能： (1)初始化链栈。 (2)链栈置空。 (3)入栈。 (4)出栈。 (5)取栈顶元素。 (6)遍历链栈。 顺序栈#include#include#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef structint *base;int *top;int stacksize;SqStack;int InitStack(SqStack &S)S.base=(int*)malloc(STACK_INIT_SIZE*sizeof(int);if(!S.base)exit(0);S.top=S.base;S.stacksize=STACK_INIT_SIZE;return 0;/初始化顺序栈int 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(0);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+=e;return 0;/插入元素eint Pop(SqStack &S,int e)if(S.top=S.base)return 0;e=*-S.top;printf(删除的栈顶元素%5d,e);printf(n);return 0;/删除栈顶元素eint Gettop(SqStack &S,int e)if(S.top=S.base)return 0;e=*(S.top-1);printf(返回的栈顶元素%5d,e);printf(n);return 0;/返回栈顶元素evoid PrintStack(SqStack &S) int *k; printf(顺序栈中的元素：n); for(k=S.base;k!=S.top;k+)printf(%5d,*k); printf(n);/遍历顺序栈void ClearStack(SqStack &S)S.top=S.base;/置空顺序栈void main()int e,i,n; SqStack S;InitStack(S);printf(1插入顶元素；2删除顶元素；3返回顶元素；4置空顺序栈；0结束运行n); printf(n);printf(n);printf(n); printf(n);printf(n); printf(选择: ); scanf(%d,&n);printf(n);printf(n); while(n!=0) switch(n) case 1:printf(插入栈顶元素);scanf(%d,&e);Push(S,e);PrintStack(S);printf(n);printf(n);break;case 2:Pop(S,e);PrintStack(S);printf(n);printf(n);break;case 3:Gettop(S,e);printf(n);printf(n);break;case 4:printf(已置空顺序栈);ClearStack(S);printf(n);printf(n);break; printf(选择: );scanf(%d,&n);printf(n);printf(n); printf(结束运行。再见！n);链式栈#include#includetypedef struct SNode int data; struct SNode *next;SNode,*Stack;typedef structStack top;int length;SqStack;/定义链式栈的结构体int InitStack(SqStack &S)S.top=NULL;S.length=0;return 0;/初始化链式栈int Push(SqStack &S,int e)Stack p;p=(Stack)malloc(sizeof(SNode);if(!p)exit(0);p-data=e;p-next=S.top;S.top=p;S.length+;return 0;/插入元素eint Pop(SqStack &S)if(!S.top)return 0;elseStack q;q=S.top;S.top=S.top-next;-S.length;free(q); return 0;/删除栈顶元素eint GetTop(SqStack &S)if(!S.top)return 0;elseprintf(返回栈顶元素%5dn,S.top-data);return 0;/返回栈顶元素int PrintStack(SqStack &S)Stack p;printf(链式队列中的元素);p=S.top;if(S.top!=NULL)while(p!=NULL)printf(%5d,p-data);p=p-next;elseprintf(队列为空n);printf(n);return 0;/遍历链式栈int ClearStack(SqStack &S)S.top=NULL;printf(已置空链式栈);printf(n);return 0;/置空链式栈void main()SqStack S;int e,m;printf(n);printf(n);printf(n);printf(n);printf(1插入元素；2删除元素；3返回栈顶元素4置空链式栈0结束运行n);printf(n);printf(n);printf(n);InitStack(S); printf(n);printf(n);printf(选择: ); scanf(%d,&m);printf(n);printf(n); while(m!=0) switch(m) case 1:printf(插入元素：);scanf(%d,&e);Push(S,e);PrintStack(S);printf(n);printf(n);break;case 2:Pop(S);PrintStack(S);printf(n);printf(n);break;case 3: