栈的基本操作.doc

物光学院计算机类实验报告数据结构课程实验报告学院： 应用科技学院 班级：09电子信息工程 姓名： 苏伟华 学号：120352009006 实验设备：计算机1台,Microsoft Visual C 6.0 软件 实验日期：2011年4月20日实验项目名称栈的基本操作实验目的1)熟悉栈的定义和栈的基本操作。2)掌握顺序存储栈和链接存储栈的基本运算。3)加深对栈结构的理解逐步培养解决实际问题的能力。实验要求： 1.编写栈的基本操作函数（分别用顺序和链接两种方式实现）。-顺序栈的基本操作函数进栈函数 int Push(SqStack &S, int e); 出栈函数 int Pop(SqStack &S,int &e); 输出栈元素 void OutputStack(SqStack &S);取栈顶元素 int GetTop(SqStack S,int &e);-调用上述函数实现下列操作，操作步骤如下。调用进栈函数建立一个栈。读取栈顶元素。从栈中删除元素。输出栈中的所有元素。-链栈的基本操作函数进栈函数 LinkStack PushStack(LinkStack top,int x);/进栈函数 出栈函数 LinkStack PopStack(LinkStack top); 输出栈元素 void Print();取栈顶元素int GetStackTop(LinkStack top); -调用上述函数实现下列操作，操作步骤如下。调用进栈函数建立一个栈。读取栈顶元素。从栈中删除元素。输出栈中的所有元素。实验内容(包括步骤)：1.顺序栈的存储结构typedef structint *base; int *top; int stacksize;SqStack;程序中的主要函数及功能的说明int InitStack(SqStack &S);int GetTop(SqStack S,int &e);int Push(SqStack &S, int e);int Pop(SqStack &S,int &e);void OutputStack(SqStack &S);主程序模块switch(m) case 1: printf(n);system(CLS); printf(请输入要进栈的元素个数是:); scanf(%d,&a); printf(n请输入要进栈的%d个元素:,a); for(b=0;ba;b+) scanf(%d,&c); Push(s,c); printf(n输出的栈为:); OutputStack(s); break; case 2: printf(n);system(CLS); GetTop(s,c); printf(n栈顶元素为:%d,c); printf(n输出的栈为:); OutputStack(s); break; case 3: printf(n);system(CLS); Pop(s,c); printf(n删除的栈顶元素:%d,c); printf(n输出的栈为:); OutputStack(s); printf(n); break; case 4:break;default: printf(n); system(CLS); printf(输入的数字有错，请重新选择!n); break; getchar();while(m!=4);2.(1) 链栈的存储结构typedef struct SNodeint data;struct SNode *next;SNode,*LinkStack;LinkStack top;程序中的主要函数及功能说明LinkStack PushStack(LinkStack top,int x);/进栈函数LinkStack PopStack(LinkStack top);/出栈函数bool IsEmpty();int GetStackTop(LinkStack top);/读取栈顶元素void Print();/输出栈元素（3）主程序模块switch(m) case 1:printf(n); system(CLS); top=NULL;printf(n栈已置空!); break; case 2: printf(n); system(CLS); printf(n请输入要进栈的元素个数是:); scanf(%d,&a); printf(n请输入要进栈的%d个元素:,a); for(b=0;ba;b+) scanf(%d,&x); top=PushStack(top,x); printf(进栈已完成！n); printf(n输出栈为:); Print(); break; case 3:printf(n); system(CLS); printf(n操作之前的输出栈为:);Print(); top=PopStack(top); printf(n操作过后的输出栈为:); Print(); break; case 4:printf(n); system(CLS); printf(n输出栈为:); Print(); if(top!=NULL) printf(n栈顶元素是：%dn,GetStackTop(top); else printf(n栈是空的，没有元素！); break; case 5:break; default:printf(n); system(CLS); printf(n输入的字符不对，请重新输入!); break; 调试与结果测试：#顺序栈的基本操作#* 1.创建和输出栈的元素*;* 2.取栈顶元素* 3.删除栈顶元素* 4.退出程序*# 请选择一个字符:1请输入要进栈的元素个数是:5请输入要进栈的5个元素:2 9 13 26 39输出栈为：39- 26- 13- 9- 2请选择一个字符:2栈顶元素为:39请选择一个字符:3删除的栈顶元素:输出栈为：26- 13- 9- 2请选择一个字符:4press any key to continue#链栈的基本操作# 1.置空栈 2.进栈 3.退栈 4.取栈顶元素 5.退出程序# 请选择一个字符：1 栈已置空!请选择一个字符：2请输入要进栈的元素个数是:5请输入要进栈的5个元素:1 9 15 21 32输出栈为:32- 21- 15- 9- 1请选择一个字符：3操作之前的输出栈为:32- 21- 15- 9- 1操作过后的输出栈为:21- 15- 9- 1请选择一个字符：4输出栈为:21- 15- 9- 1栈顶元素是：21请选择一个字符：5press any key to continue代码注释: /顺序栈的基本操作#include#include#include#define error 0#define ok 1#define OVERFLOW -2#define STACK_INIT_SIZE 100;/栈内存的初始分配量，以sizeof(ElemType)为单位#define STACKINCREMENT 10;/栈内存的分配增量，以sizeof(ElemType)为单位typedef int ElemType;typedef struct int *base;/存储空间的基址，数据元素的数据类型约定为ElemType int *top;/表示栈顶，如果top=base，表示空栈 int stacksize;/当前分配的存储容量，以sizeof(ElemType) 为单位SqStack;/* /*函数的声明部分* /*int InitStack(SqStack &S);/栈的初始化int GetTop(SqStack S,int &e);/初始条件：栈S已存在且非空。操作结果：用e返回S的栈顶元素。int Push(SqStack &S, int e);/初始条件：栈S已存在。操作结果：插入元素e为新的栈顶元素。int Pop(SqStack &S,int &e);/初始条件：栈S已存在且非空。操作结果：删除S的栈顶元素，并用e返回其值。void OutputStack(SqStack &S); /*/*函数的实现部分* /*int InitStack(SqStack &S) /为栈S分配存储空间，并置S为空栈 int size = STACK_INIT_SIZE; S.base=(ElemType*)malloc(size*sizeof(ElemType); if(!S.base) exit(OVERFLOW); S.top=S.base; /置栈S为空栈 S.stacksize=STACK_INIT_SIZE; return ok;int GetTop(SqStack S,int &e)/若栈不空，则用e返回S的栈顶元素并返回OK，否则返回ERROR if(S.top=S.base) return error; e=*(S.top-1); return ok;int Push(SqStack &S, int e) /将e插入栈S中并使之成为栈顶元素 if(S.top-S.base=S.stacksize) /栈满，追加存储空间 int stackinvrement = STACKINCREMENT; S.base=(ElemType *) realloc(S.base,(S.stacksize+stackinvrement)*sizeof(ElemType); if(!S.base) exit(OVERFLOW);/存储分配失败 S.stacksize+=STACKINCREMENT; *S.top+=e; return ok;int Pop(SqStack &S,int &e)/若栈S不空，则删除S的栈顶元素，用e返回其值并返回OK，否则返回ERROR if(S.top=S.base) return error; e=*-S.top; return ok; void OutputStack(SqStack &S)/输出栈的所有元素int *q ; q=S.top-1; for(int i=0;iS.top-S.base;i+) printf(-%3d ,*q);q-;/*/*主函数部分*/* void main() system(color 2D); int a,b,c ; char m; SqStack s; InitStack(s); do printf(n); printf(#顺序栈的基本操作#n); printf(* 1.创建和输出栈的元素*n); printf(* 2.取栈顶元素*n); printf(* 3.删除栈顶元素*n); printf(* 4.退出程序*n); printf(#n); printf(n请选择一个字符:); scanf(%c,&m);switch(m) case 1: printf(n);system(CLS); printf(请输入要进栈的元素个数是:); scanf(%d,&a); printf(n请输入要进栈的%d个元素:,a); for(b=0;ba;b+) scanf(%d,&c); Push(s,c); printf(n输出的栈为:); OutputStack(s); break; case 2: printf(n);system(CLS); GetTop(s,c); printf(n栈顶元素为:%d,c); printf(n输出的栈为:); OutputStack(s); break; case 3: printf(n);system(CLS); Pop(s,c); printf(n删除的栈顶元素:%d,c); printf(n输出的栈为:); OutputStack(s); printf(n); break; case 4:break;default: printf(n); system(CLS); printf(输入的数字有错，请重新选择!n); break; getchar();while(m!=4); system(pause);/链栈的基本操作 #include#includetypedef struct SNode/单链表结点结构int data;struct SNode *next;SNode,*LinkStack;/链栈类型定义LinkStack top;/指向栈顶结点/* /*函数的声明部分* /*LinkStack PushStack(LinkStack top,int x);/在栈中压入一元素xLinkStack PopStack(LinkStack top);/在栈中删除栈顶元素bool IsEmpty();/判单链形式栈是否为空栈int GetStackTop(LinkStack top);/对非空栈求栈顶元素void Print();/输出栈元素/*/*函数的实现部分* /*LinkStack PushStack(LinkStack top,int x) /在栈中压入一元素x LinkStack s; s=(LinkStack)malloc(sizeof(SNode);/s = (struct Node *)malloc( sizeof( struct Node ) );if ( s = NULL ) printf(Out of space!n);else s-data=x; s-next=top; top=s; return top;LinkStack PopStack(LinkStack top) /在栈中删除栈顶元素 LinkStack p; if(top!=NULL) p=top; top=top-next; free(p); printf(退栈已完成n); return top; else printf(栈是空的，无法退栈！n); return 0;int GetStackTop(LinkStack top) /对非空栈求栈顶元素 return top-data;bool IsEmpty()/bool取值false和true，是0和1的区别,bool只有一个字节,BOOL为int型,bool为布尔型 return top=NULL ? true:false;void Print()/输出栈的所有元素 SNode *p; p=top; if(IsEmpty() printf(The stack is empty!n); return; while(p) printf(data); p=p-next; printf(n);/*/*主函数部分*/* void main() system(color 2D); int x,a,b; char m;do printf(n); printf(#链栈的基本操作#n); printf(1.置空栈n); printf(2.进栈n); printf(3.退栈n); printf(4.取栈顶元素n); printf(5.退出程序n); printf(#n); printf(n请选