栈的操作(实验报告)

实验三 栈和队列

3.1实验目的：

（1） 熟悉栈的特点（先进后出）及栈的基本操作，如入栈、出栈等，掌握栈的基本操作

在栈的顺序存储结构和链式存储结构上的实现；

（2） 熟悉队列的特点（先进先出）及队列的基本操作，如入队、出队等，掌握队列的基

本操作在队列的顺序存储结构和链式存储结构上的实现。

3.2 实验要求：

（1） 复习课本中有关栈和队列的知识；

（2） 用C语言完成算法和程序设计并上机调试通过；

（3） 撰写实验报告，给出算法思路或流程图和具体实现（源程序）、算法分析结果（包括

时间复杂度、空间复杂度以及算法优化设想）、输入数据及程序运行结果（必要时给出多种可能的输入数据和运行结果）。

3.3 基础实验

[实验1] 栈的顺序表示和实现

实验内容与要求:

编写一个程序实现顺序栈的各种基本运算，并在此基础上设计一个主程序，完成如下功能： （1）初始化顺序栈 （2）插入元素 （3）删除栈顶元素 （4）取栈顶元素 （5）遍历顺序栈 （6）置空顺序栈

分析:

栈的顺序存储结构简称为顺序栈,它是运算受限的顺序表。

对于顺序栈，入栈时，首先判断栈是否为满，栈满的条件为：p->top= =MAXNUM-1，栈满时，不能入栈; 否则出现空间溢出，引起错误，这种现象称为上溢。

出栈和读栈顶元素操作，先判栈是否为空，为空时不能操作，否则产生错误。通常栈空作为一种控制转移的条件。 注意：

（1）顺序栈中元素用向量存放

（2）栈底位置是固定不变的，可设置在向量两端的任意一个端点 （3）栈顶位置是随着进栈和退栈操作而变化的，用一个整型量top（通常称top为栈顶指针）来指示当前栈顶位置

参考程序:

#include #include #define MAXNUM 20

1

#define ElemType int

/*定义顺序栈的存储结构*/ typedef struct

{ ElemType stack[MAXNUM]; int top; }SqStack;

/*初始化顺序栈*/

void InitStack(SqStack *p) { if(!p) printf(\ p->top=-1; }

/*入栈*/

void Push(SqStack *p,ElemType x) { if(p->toptop=p->top+1; p->stack[p->top]=x; } else printf(\}

/*出栈*/

ElemType Pop(SqStack *p) { ElemType x; if(p->top!=0) { x=p->stack[p->top]; printf(\以前的栈顶数据元素%d已经被删除！\\n\ p->top=p->top-1; return(x); } else { printf(\ return(0); } }

/*获取栈顶元素*/

ElemType GetTop(SqStack *p) { ElemType x; if(p->top!=0) { x=p->stack[p->top]; return(x); } else { printf(\

2

return(0); } }

/*遍历顺序栈*/

void OutStack(SqStack *p) { int i; printf(\ if(p->top<0) printf(\这是一个空栈！\ printf(\ for(i=p->top;i>=0;i--) printf(\第%d个数据元素是：m\\n\}

/*置空顺序栈*/

void setEmpty(SqStack *p) {

p->top= -1; }

/*主函数*/ main()

{ SqStack *q; int y,cord;ElemType a; do{ printf(\ printf(\第一次使用必须初始化！\\n\ printf(\ printf(\ 主菜单 \\n\ printf(\ 1 初始化顺序栈 \\n\ printf(\ 2 插入一个元素 \\n\ printf(\ 3 删除栈顶元素 \\n\ printf(\ 4 取栈顶元素 \\n\ printf(\ 5 置空顺序栈 \\n\ printf(\ 6 结束程序运行 \\n\ printf(\ printf(\请输入您的选择( 1, 2, 3, 4, 5,6)\ scanf(\ printf(\ switch(cord) { case 1: { q=(SqStack*)malloc(sizeof(SqStack)); InitStack(q); OutStack(q); }break; case 2:

3

{ printf(\请输入要插入的数据元素：a=\ scanf(\ Push(q,a); OutStack(q); }break; case 3: { Pop(q); OutStack(q); }break; case 4: { y=GetTop(q); printf(\栈顶元素为：%d\\n\ OutStack(q); }break; case 5: { setEmpty(q); printf(\顺序栈被置空！\\n\ OutStack(q); }break; case 6: exit(0); } }while (cord<=6); }

[实验2] 栈的链式表示和实现

实验内容与要求:

编写一个程序实现链栈的各种基本运算，并在此基础上设计一个主程序，完成如下功能： （1）初始化链栈 （2）链栈置空 （3）入栈 （4）出栈

（5）取栈顶元素 （6）遍历链栈

分析:

链栈是没有附加头结点的运算受限的单链表。栈顶指针就是链表的头指针。 注意：

（1）LinkStack结构类型的定义可以方便地在函数体中修改top指针本身

（2）若要记录栈中元素个数，可将元素个数属性放在LinkStack类型中定义。 （3）链栈中的结点是动态分配的，所以可以不考虑上溢。

4