1、栈的顺序表示和实现2.2基础实验2.2.1实验目的（1）掌握栈的顺序表示和实现（2）掌握栈的链式表示和实现（3）掌握队列的顺序表示和实现（4）掌握队列的链式表示和实现2.2.2实验内容实验一：栈的顺序表示和实现【实验内容与要求】编写一个程序实现顺序栈的各种基本运算，并在此基础上设计一个主程序，完成如下功能：（1）初始化顺序栈（2）插入元素（3）删除栈顶元素（4）取栈顶元素（5）遍历顺序栈（6）置空顺序栈【知识要点】栈的顺序存储结构简称为顺序栈,它是运算受限的顺序表。对于顺序栈，入栈时，首先判断栈是否为满，栈满的条件为：p-top= =MAXNUM-1，栈满时，不能入栈;否则出现空间溢出，引起错
2、误，这种现象称为上溢。出栈和读栈顶元素操作，先判栈是否为空，为空时不能操作，否则产生错误。通常栈空作为一种控制转移的条件。注意：（1）顺序栈中元素用向量存放（2）栈底位置是固定不变的，可设置在向量两端的任意一个端点（3）栈顶位置是随着进栈和退栈操作而变化的，用一个整型量 top（通常称 top 为栈顶指针）来指示当前栈顶位置【实现提示】/*定义顺序栈的存储结构*/typedef struct ElemType stackMAXNUM;int top;SqStack;/*初始化顺序栈函数*/void InitStack(SqStack *p)q=(SqStack*)malloc(sizeof(S
3、qStack) /*申请空间*/)/*入栈函数*/void Push(SqStack *p,ElemType x)if(p-toptop=p-top+1; /*栈顶+1*/p-stackp-top=x; /*数据入栈*/*出栈函数*/ElemType Pop(SqStack *p)x=p-stackp-top; /*将栈顶元素赋给 x*/p-top=p-top-1; /*栈顶-1*/*获取栈顶元素函数*/ElemType GetTop(SqStack *p) x=p-stackp-top;/*遍历顺序栈函数*/void OutStack(SqStack *p) for(i=p-top;i=0;
4、i-)printf(“第%d 个数据元素是： %6dn“,i,p-stacki);/*置空顺序栈函数*/void setEmpty(SqStack *p) p-top= -1;【参考程序】#include#include#define MAXNUM 20#define ElemType int/*定义顺序栈的存储结构*/typedef struct ElemType stackMAXNUM;int top;SqStack;/*初始化顺序栈*/void InitStack(SqStack *p) if(!p)printf(“Eorror“);p-top=-1;/*入栈*/void Push(Sq
5、Stack *p,ElemType x) if(p-toptop=p-top+1;p-stackp-top=x;elseprintf(“Overflow!n“);/*出栈*/ElemType Pop(SqStack *p) ElemType x;if(p-top!=0) x=p-stackp-top;printf(“以前的栈顶数据元素%d 已经被删除！n“,p-stackp-top);p-top=p-top-1;return(x);else printf(“Underflow!n“);return(0);/*获取栈顶元素*/ElemType GetTop(SqStack *p) ElemTyp
6、e x;if(p-top!=0) x=p-stackp-top;return(x);else printf(“Underflow!n“);return(0);/*遍历顺序栈*/void OutStack(SqStack *p) int i;printf(“n“);if(p-toptop;i=0;i-)printf(“第%d 个数据元素是：%6dn“,i,p-stacki);/*置空顺序栈*/void setEmpty(SqStack *p)p-top= -1;/*主函数*/main() SqStack *q;int y,cord;ElemType a;doprintf(“n“);printf(
7、“第一次使用必须初始化！n“);printf(“n“);printf(“n 主菜单 n“);printf(“n 1 初始化顺序栈 n“);printf(“n 2 插入一个元素 n“);printf(“n 3 删除栈顶元素 n“);printf(“n 4 取栈顶元素 n“);printf(“n 5 置空顺序栈 n“);printf(“n 6 结束程序运行 n“);printf(“n-n“);printf(“请输入您的选择( 1, 2, 3, 4, 5,6)“);scanf(“%d“,printf(“n“);switch(cord) case 1: q=(SqStack*)malloc(sizeo
8、f(SqStack);InitStack(q);OutStack(q);break;case 2: printf(“请输入要插入的数据元素：a=“);scanf(“%d“,Push(q,a);OutStack(q);break;case 3: Pop(q);OutStack(q);break;case 4: y=GetTop(q);printf(“n 栈顶元素为：%dn“,y);OutStack(q);break;case 5: setEmpty(q);printf(“n 顺序栈被置空！n“);OutStack(q);break;case 6:exit(0);while (cordtop=NU
9、LL;/*链栈置空函数*/void setEmpty(LinkStack * s) s-top=NULL;/*入栈函数*/void pushLstack(LinkStack * s, Elemtype x) p=(StackNode *)malloc(sizeof(StackNode); /建立一个节点。p-data=x;p-next=s-top; /指向栈顶。s-top=p; /插入/*出栈函数*/Elemtype popLstack(LinkStack * s)x=p-data;s-top=p-next; /当前的栈顶指向原栈的 nextfree(p); /释放/*取栈顶元素函数*/Ele
10、mtype StackTop(LinkStack *s) return s-top-data;/*遍历链栈函数*/void Disp(LinkStack * s)while (p!=NULL) printf(“%dn“,p-data);p=p-next;【参考程序】#include “stdio.h“#include “malloc.h“#include “stdlib.h“typedef int Elemtype;typedef struct stacknode Elemtype data;stacknode * next;StackNode;typedef struct stacknode
11、 * top; /栈顶指针LinkStack;/*初始化链栈*/void InitStack(LinkStack * s) s-top=NULL;printf(“n 已经初始化链栈！n“);/*链栈置空*/void setEmpty(LinkStack * s) s-top=NULL;printf(“n 链栈被置空！n“);/*入栈*/void pushLstack(LinkStack * s, Elemtype x) StackNode * p;p=(StackNode *)malloc(sizeof(StackNode); /建立一个节点。p-data=x;p-next=s-top; /由
12、于是在栈顶 pushLstack，所以要指向栈顶。s-top=p; /插入/*出栈*/Elemtype popLstack(LinkStack * s) Elemtype x;StackNode * p;p=s-top; /指向栈顶if (s-top =0) printf(“n 栈空，不能出栈！n“);exit(-1);x=p-data;s-top=p-next; /当前的栈顶指向原栈的 nextfree(p); /释放return x;/*取栈顶元素*/Elemtype StackTop(LinkStack *s) if (s-top =0) printf(“n 链栈空n“);exit(-1
13、);return s-top-data;/*遍历链栈*/void Disp(LinkStack * s) printf(“n 链栈中的数据为：n“);printf(“=n“);StackNode * p;p=s-top;while (p!=NULL) printf(“%dn“,p-data);p=p-next;printf(“=n“);void main() printf(“=链栈操作 =nn“);int i,m,n,a;LinkStack * s;s=(LinkStack *)malloc(sizeof(LinkStack); int cord; do printf(“n“);printf(
14、“第一次使用必须初始化！n“);printf(“n“);printf(“n 主菜单 n“);printf(“n 1 初始化链栈 n“);printf(“n 2 入栈 n“);printf(“n 3 出栈 n“);printf(“n 4 取栈顶元素 n“);printf(“n 5 置空链栈 n“);printf(“n 6 结束程序运行 n“);printf(“n-n“);printf(“请输入您的选择( 1, 2, 3, 4, 5,6)“);scanf(“%d“,printf(“n“);switch(cord) case 1: InitStack(s);Disp(s);break;case 2:printf(“输入将要压入链栈的数据的个数：n=“);scanf(“%d“,printf(“依次将%d 个数据压入链栈：n“,n);for(i=1;ifront=-1;q-rear=-1;/*入队函数*/int append(sqqueue *q, Elemtype x) q-rear+;q-queueq-rear=x;/*出队函数*/Elemtype Delete(sqqueue *q) x=q-queue+q-front;/*判断队列是否为空函数*/int Empty(sqqueue *q)
