文档介绍：数据结构实验报告(二)
实验二堆栈和队列
实验目的和要求:
掌握堆栈和队列的基本概念;
掌握堆栈和队列的基本操作。
实验原理:
堆栈的定义:堆栈是一种只允许在表的一端进行插入和删除运算的特殊的线性表。允许进行插入和删除运算的一端称为栈顶,另一端称为栈底,当链表中没有元素时,称为空栈。
堆栈的插入运算称为入栈或者进栈,删除运算称为出栈或者退栈,栈顶的当前位置是动态的,标识栈顶当前位置的指针称为栈顶指针。每次进栈的数据元素都放在原当前栈顶元素之前成为新的栈顶元素,每次退栈的数据元素都是原当前栈顶元素,最后进入堆栈的数据元素总是最先退出堆栈。
堆栈的存储结构:
顺序存储结构:栈的顺序存储结构称为顺序栈。顺序栈的本质是顺序表的简化。
链式存储结构:栈的链式存储结构称为链栈,通常用单链表示。链栈的插入和删除操作只需处理栈顶的情况。
队列的定义:队列是允许在表的一端进行插入,而在表的另一端进行删除的特殊线性表。允许进行插入的一端称为队尾,允许进行删除的一端称为队头。队列的插入运算称为进队或者入队,删除运算称为出队或者离队,因此队列又称为先进先出表。
队列的存储结构
队列的存储结构同线性表一样,可以分为顺序结构和链式结构。
顺序存储结构:用顺序存储结构存储队列称为顺序队列。顺序队列会出现假溢出问题,解决办法是用首尾相接的书顺序存储结构,称为循环队列。在队列中,只要涉及队头或者队尾指针的修改都要对其求模。
链式存储结构:用链式存储结构存储的队列称为链队列。链队列的基本操作的实现基本上也是单链表操作的简化。通常附设头结点,并设置队头指针指向头结点,队尾指针指向终端结点。插入数据时只考虑在链队列的尾部进行,删除数据时只考虑在链队列的头部进行。
实验内容:
试编写一个算法,建立一个学生成绩栈,要求从键盘上输入N个整数,按照下列要求分别进入不同的栈。
若输入的整数X小于60,则进入第一个栈;
若输入的整数x大于等于60并小于100,则进入第二个栈;
若输入的整数x大于100,则进入第三个栈;
分别输出每个栈的内容。
编写一个程序,使用两个链队q1和q2,用来分别存储由计算机产生的20个100以内的奇数和偶数,然后每行输出q1和q2的一个值,即奇数和偶数配对输出,直到任一队列为空为止。
假设一个算术表达式中可以包括三种括号:“(”和“)”,方括号“[”和“]”及花括号“{”和“}”,且这三种括号可以任意顺序的嵌套使用。编写算法判断给定表达式中所包含的括号是否配对出现。
:
,采用顺序存储结构。在类中定义*elements用来存放数据。然后定义测试主函数。在主函数中,定义三个堆栈对象,将三类数据根据要求分别压入这三个对象中,最后将它们输出。
首先定义链式队列结点类,结点类的data变量用于存放数值;然后定义链式队列类,类中的函数可实现对数据的存取;使用两个链队q1和q2,分别存放奇数和偶数,定义一个函数DeleteQueue(),使得每一行输出一个奇数和一个偶数,直到任一队列空为止。
,从左向右依次扫描各个字符
定义三个栈h(n),p(n),l(n).三个计数器x1,x2,x3.
for(int i=0;i<n;i++)进行循环,遇到’[’存入h(n),遇到‘{’存入p(n),遇到’(’存到l(n)
当遇到“]”“}”“)”时,分别判断相应的堆栈是否为空,若不为空,则取出栈顶元素,相应的计数器自加一,统计出成对的括号。
程序代码:
#include<>
#include<>
#include"iostream"
using namespace std;
class List;
typedef int ElemType;
class SeqStack
{//堆栈的数据成员
unsigned height;
int top;
int maxsize; //栈的最大元素个数
ElemType *elements; //元素存储空间
public:
SeqStack(int size); //构造函数,size用来设置栈的大小
~SeqStack(){ delete[]elements;} //析构函数
void PushStack(ElemType x); //进栈函数,将元素x压入栈中
ElemType PopStack(ElemType x); //出栈函数,将栈顶元素值放入x中
void ClearStack(){top=-1;} //清栈函数,用于释放所占的内存空间
bool IsFul