数据结构实验报告（二）
实验二堆栈和队列
一、 实验目的和要求：
1、 掌握堆栈和队列的基本概念；
2、 掌握堆栈和队列的基本操作。
二、 实验原理：
1、 堆栈的定义：堆栈是一种只允许在表的一端进行插入和删除运算的特殊的线性表。允许进行插入和删除运算的一端称为栈顶，另一端称为栈底，当链表中没有元素时，称为空栈。
2、 堆栈的插入运算称为入栈或者进栈，删除运算称为出栈或者退栈，栈顶的当前位置是动态的，标识栈顶当前位置的指针称为栈顶指针。每次进栈的数据元素都放在原当前栈顶元素之前成为新的栈顶元素，每次退栈的数据元素都是原当前栈顶元素，最后进入堆栈的数据元素总是最先退出堆栈。
3、 堆栈的存储结构：
（1） 顺序存储结构：栈的顺序存储结构称为顺序栈。顺序栈的本质是顺序表的简化。
（2） 链式存储结构：栈的链式存储结构称为链栈，通常用单链表示。链栈的插入和删除操作只需处理栈顶的情况。
4、 队列的定义：队列是允许在表的一端进行插入，而在表的另一端进行删除的特殊线性表。允许进行插入的一端称为队尾，允许进行删除的一端称为队头。队列的插入运算称为进队或者入队，删除运算称为出队或者离队，因此队列又称为先进先出表。
5、 队列的存储结构
队列的存储结构同线性表一样，可以分为顺序结构和链式结构。
（1） 顺序存储结构：用顺序存储结构存储队列称为顺序队列。顺序队列会出现假溢出问题，解决办法是用首尾相接的书顺序存储结构，称为循环队列。在队列中，只要涉及队头或者队尾指针的修改都要对其求模。
（2） 链式存储结构：用链式存储结构存储的队列称为链队列。链队列的基本操作的实现基本上也是单链表操作的简化。通常附设头结点，并设置队头指针指向头结点，队尾指针指向终端结点。插入数据时只考虑在链队列的尾部进行，删除数据时只考虑在链队列的头部进行。
三、 实验内容：
1、 试编写一个算法，建立一个学生成绩栈，要求从键盘上输入N个整数，按照下列要求分别进入不同的栈。
（1） 若输入的整数X小于60，则进入第一个栈；
（2） 若输入的整数x大于等于60并小于100，则进入第二个栈；
（3） 若输入的整数x大于100，则进入第三个栈；
（4） 分别输出每个栈的内容。
2、 编写一个程序，使用两个链队q1和q2，用来分别存储由计算机产生的20个100以内的奇数和偶数，然后每行输出q1和q2的一个值，即奇数和偶数配对输出，直到任一队列为空为止。
3、 假设一个算术表达式中可以包括三种括号：“（”和“）”，方括号“[”和“]”及花括号“{”和“}”，且这三种括号可以任意顺序的嵌套使用。编写算法判断给定表达式中所包含的括号是否配对出现。
四.编程思想：
P165.2首先定义一个堆栈类，采用顺序存储结构。在类中定义*elements用来存放数据。然后定义测试主函数。在主函数中，定义三个堆栈对象，将三类数据根据要求分别压入这三个对象中，最后将它们输出。
P166.7首先定义链式队列结点类，结点类的data变量用于存放数值；然后定义链式队列类，类中的函数可实现对数据的存取；使用两个链队q1和q2，分别存放奇数和偶数，定义一个函数DeleteQueue()，使得每一行输出一个奇数和一个偶数，直到任一队列空为止。
P166.8采用顺序栈.用一个字符串表示一个表达式,从左向右依次扫描各个字符
1. 定义三个栈h(n),p(n),l(n).三个计数器x1,x2,x3.
2. for(inti=0;i＜n;i++)进行循环，遇到’[’存入h（n）,遇到‘{’存入p(n),遇到’(’存到l(n)
3. 当遇到“]”“}”“)”时，分别判断相应的堆栈是否为空，若不为空，则取出栈顶元素，相应的计数器自加一，统计出成对的括号。
程序代码:
P165.2
#include＜stdlib.h＞
#include＜time.h＞
#include"iostream"
using namespace std;
class List;
typedefintElemType;
class SeqStack
{//堆栈的数据成员
unsigned height;
int top;
intmaxsize; //栈的最大元素个数
ElemType *elements; //元素存储空间
public:
SeqStack(int size); //构造函数，size用来设置栈的大小
~SeqStack(){ delete[]elements;} //析构函数
void PushStack(ElemType x); //进栈函数，将元素x压入栈中
ElemTypePopStack(ElemType x); //出栈函数，将栈顶元素值放入x中
void ClearStack(){top=-1;} //清栈函数，用于释放所占的内存空间
boolIsFullStack() {return top==maxsize-1;} //判断栈是否为满
boolIsEmptyStack(); //判断栈是否为空
void PrintStack(); //将栈中元素输入到屏幕上
};
SeqStack::SeqStack(int size)
{
height=0;
top=-1;
maxsize=size; //设置最大栈高
elements=new ElemType[size];
}
void SeqStack::PushStack(ElemType x)
{ if(IsFullStack())
cout＜＜"栈已满~";
else
{
elements [++top]=x;
height++;
}
}
ElemTypeSeqStack::PopStack(ElemType x)
{
x=elements[top];
top--;
height--;
return x;
}
boolSeqStack::IsEmptyStack() //判断栈是否为空
{
return (height==0)? true:false;
}
void SeqStack::PrintStack()
{
while(IsEmptyStack()==false)
{cout＜＜elements[top]＜＜" ";
top--;
height--;
}
cout＜＜endl;
}
int main()
{
int n;
ElemType m;
cout＜＜"请输入学生人数：";
cin＞＞n;
SeqStack h(n),p(n),l(n);
cout＜＜"学生的成绩为：";
for(inti=0;i＜n;i++)
{
cin＞＞m;
cout＜＜ m＜＜" ";
if(m＞100)
h.PushStack(m);
else if( m＞=60&&m＜=100)
p.PushStack(m);
else l.PushStack(m);
}
cout＜＜endl;
cout＜＜"小于60的成绩：";
l.PrintStack();
cout＜＜"小于等于100且大于等于60的成绩：";
p.PrintStack();
cout＜＜"大于100的成绩：";
h.PrintStack();
system("PAUSE");
}
实验结果
P166.7
#include＜stdlib.h＞
#include＜iostream＞
using namespace std;
class LinkQueue;
class ListNode //定义链式队列的结点类
{
friend class LinkQueue;
int data;
ListNode* link;
};
class LinkQueue
{ public:
ListNode* head;
ListNode* tail;
intqsize; //定义队长
int *elements;
LinkQueue() {head=tail=NULL;} //构造函数,建立空队列
~LinkQueue() {Clear();} //析构函数
void PushTail(int&x); //将新元素插入在队尾
boolPopFront(int&x); //从队头取一个元素
void Clear() ; //清空队列
intIsEmpty() {return head==NULL;} //判断队列是否为空
intDeleteQueue();
};
void LinkQueue::PushTail(int&x)//插入，将元素插入到队尾
{
ListNode *p=new ListNode;
p-＞data=x;
if(tail!=NULL)
{p-＞link=NULL;
tail-＞link=p;
tail=p;
}
else
{p-＞link=NULL;
tail=p;
head=p;}}
boolLinkQueue::PopFront(int&x)
{ListNode *p;
if(head) //若队列为非空
{
x=head-＞data;
p=head;
head=head-＞link;
if(head==NULL)
tail=NULL;
delete p;
qsize--;
return 1;
} return -1;
}
void LinkQueue::Clear()
{ int p;
while(PopFront(p))
head=tail=NULL;
}
intLinkQueue::DeleteQueue()
{
ListNode *q=head;//指向队列头元素
head=q-＞link;
int y=q-＞data;//用y返回队头元素
delete q;
return y;
}
int main()
{
LinkQueue q1,q2;
for(inti=0; i＜20; i++)
{
int x=rand()%100;
cout＜＜x＜＜" ";
if(x%2==1)
q1.PushTail(x); //用q1链队存放奇数
else
q2.PushTail(x); //用q2链队存放偶数
}
cout＜＜endl;
while(!q1.IsEmpty()&&!q2.IsEmpty()) //每一行输出一个奇数和一个偶数，直到任一队列空为止
{
cout＜＜"奇数"＜＜q1.DeleteQueue()＜＜" "＜＜"偶数"＜＜q2.DeleteQueue()＜＜endl;
}
cout＜＜endl;
system("PAUSE");
}
P166.8
#include＜stdlib.h＞
#include＜time.h＞
#include"iostream"
using namespace std;
class List;
typedef char ElemType;
class SeqStack
{//堆栈的数据成员
unsigned height;
int top;
intmaxsize;
//栈的最大元素个数
ElemType *elements; //元素存储空间
public:
SeqStack(int size); //构造函数，size用来设置栈的大小
~SeqStack(){ delete[]elements;} //析构函数
void PushStack(ElemType x); //进栈函数，将元素x压入栈中
ElemTypePopStack(ElemType x); //出栈函数，将栈顶元素值放入x中
ElemTypetopStack(ElemType&e);
void ClearStack(){top=-1;} //清栈函数，用于释放所占的内存空间
boolIsFullStack() {return top==maxsize-1;} //判断栈是否为满
boolIsEmptyStack(); //判断栈是否为空
void PrintStack(); //将栈中元素输入到屏幕上
};
SeqStack::SeqStack(int size)
{
height=0;
top=-1;
maxsize=size; //设置最大栈高
elements=new ElemType[size];
}
void SeqStack::PushStack(ElemType x)
{ if(IsFullStack())
cout＜＜"栈已满~";
else
{
elements [++top]=x;
height++;
}
}
ElemTypeSeqStack::PopStack(ElemType x)
{
x=elements[top];
top--;
height--;
return x;
}
ElemTypeSeqStack::topStack(ElemType&e)
{
if (height==0) return false;
else{
e=elements[top-1];
return e
;
} }
boolSeqStack::IsEmptyStack() //判断栈是否为空
{
return (height==0)? true:false;
}
void SeqStack::PrintStack()
{
while(IsEmptyStack()==false)
{cout＜＜elements[top]＜＜" ";
top--;
height--;
}
cout＜＜endl;
}
int main()
{int n,x1,x2,x3;
x1=0;
x2=0;
x3=0;
char tm;
ElemType m[n];
cout＜＜"请输入字符串的长度：";
cin＞＞n;
SeqStack h(n),p(n),l(n);
cout＜＜"请输入字符串：";
for(inti=0;i＜n;i++)
{
cin＞＞ m[i];
cout＜＜m[i]＜＜" ";
if(m[i]=='[')
{h.PushStack(m[i]);}
else if(m[i]==']')
{if(h.IsEmptyStack())
return false;
else
{
h.PopStack(tm);
x1++;}
}
if( m[i]=='{')
p.PushStack(m[i]);
else if(m[i]=='}')
{if(p.IsEmptyStack())
return false;
else
{
p.PopStack(tm);
x2++;}
}
if( m[i]=='(')
l.PushStack(m[i]);
else if(m[i]==')')
{ if (l.IsEmptyStack())
return false;
else
{
l.PopStack(tm);
x3++;
}
}
} cout＜＜endl;
cout＜＜" [ "＜＜"成对了"＜＜x1＜＜"对"＜＜endl;
cout＜＜" { "＜＜"成对了"＜＜x2＜＜"对"＜＜endl;
cout＜＜" ( "＜＜"成对了"＜＜x3＜＜"对"＜＜endl;
system("PAUSE");
}
程序结果
五.编程心得：
通过P165.2熟悉了堆栈的定义,以及其构造函数与析构函数.求栈长以及入栈与出栈的函数定义.
P166.7中感到较为困难的奇偶数的交替输出
P166.8较为困难的是第一次在堆栈中输入字符串，并实现循环与查找操作。
通过这次程序的编译让我更加认识到了堆栈与队列的应用范围之广。充分利用堆栈与队列的元素进出的特点可以省去很多麻烦。
通过上机编译，认识到很多细节上的问题，细致了解了顺序栈与链式栈，顺序队列与链式队列的从定义到使用上的区别。