栈的操作(实验报告)

栈的基本操作,附带源程序

实验三 栈和队列

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<stdio.h>

#include<stdlib.h>

#define MAXNUM 20

栈的基本操作,附带源程序

#define ElemType int

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

typedef struct

{ ElemType stack[MAXNUM];

int top;

}SqStack;

/*初始化顺序栈*/

void InitStack(SqStack *p)

{ if(!p)

printf("Eorror");

p->top=-1;

}

/*入栈*/

void Push(SqStack *p,ElemType x)

{ if(p->top<MAXNUM-1)

{ p->top=p->top+1;

p->stack[p->top]=x;

}

else

printf("Overflow!\n");

}

/*出栈*/

ElemType Pop(SqStack *p)

{ ElemType x;

if(p->top!=0)

{ x=p->stack[p->top];

printf("以前的栈顶数据元素%d已经被删除！\n",p->stack[p->top]);

p->top=p->top-1;

return(x);

}

else

{ printf("Underflow!\n");

return(0);

}

}

/*获取栈顶元素*/

ElemType GetTop(SqStack *p)

{ ElemType x;

if(p->top!=0)

{ x=p->stack[p->top];

return(x);

}

else

{ printf("Underflow!\n");

栈的基本操作,附带源程序

return(0);

}

}

/*遍历顺序栈*/

void OutStack(SqStack *p)

{ int i;

printf("\n");

if(p->top<0)

printf("这是一个空栈！");

printf("\n");

for(i=p->top;i>=0;i--)

printf("第%d个数据元素是：%6d\n",i,p->stack[i]);

}

/*置空顺序栈*/

void setEmpty(SqStack *p)

{

p->top= -1;

}

/*主函数*/

main()

{ SqStack *q;

int y,cord;ElemType a;

do{

printf("\n");

printf("第一次使用必须初始化！\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",&cord);

printf("\n");

switch(cord)

{ case 1:

{ q=(SqStack*)malloc(sizeof(SqStack));

InitStack(q);

OutStack(q);

}break;

case 2:

栈的基本操作,附带源程序

{ printf("请输入要插入的数据元素：a=");

scanf("%d",&a);

Push(q,a);

OutStack(q);

}break;

case 3:

{ Pop(q);

OutStack(q);

}break;

case 4:

{ y=GetTop(q);

printf("\n栈顶元素为：%d\n",y);

OutStack(q);

}break;

case 5:

{ setEmpty(q);

printf("\n顺序栈被置空！\n");

OutStack(q);

}break;

case 6:

exit(0);

}

}while (cord<=6);

}

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

实验内容与要求:

编写一个程序实现链栈的各种基本运算，并在此基础上设计一个主程序，完成如下功能：

（1）初始化链栈

（2）链栈置空

（3）入栈

（4）出栈

（5）取栈顶元素

（6）遍历链栈

分析:

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

注意：

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

（2）若要记录栈中元素个数，可将元素个数属性放在LinkStack类型中定义。

（3）链栈中的结点是动态分配的，所以可以不考虑上溢。

栈的基本操作,附带源程序

参考程序:

#include "stdio.h"

#include "malloc.h"

#include "stdlib.h"

typedef int Elemtype;

typedef struct stacknode {

Elemtype data;

stacknode * next;

}StackNode;

typedef struct {

stacknode * 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)

{ …… 此处隐藏：2499字，全部文档内容请下载后查看。喜欢就下载吧 ……