北京理工大学数据结构实验报告二 堆栈和队列.docx

数据结构实验报告（二）实验二 堆栈和队列一、 实验目的和要求：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(int i=0;in;i+)进行循环，遇到存入h（n）,遇到存入p(n),遇到(存到l(n)3. 当遇到“”“”“)”时，分别判断相应的堆栈是否为空，若不为空，则取出栈顶元素，相应的计数器自加一，统计出成对的括号。程序代码:P165.2#include#include#includeiostreamusing namespace std;class List;typedef int ElemType;class SeqStack/堆栈的数据成员 unsigned height; int top; int maxsize; /栈 的最大元素个数 ElemType *elements; /元素存储空间 public: SeqStack(int size); /构造函数，size用来设置栈的大小 SeqStack() deleteelements; /析构函数 void PushStack(ElemType x); /进栈函数，将元素x压入栈中 ElemType PopStack(ElemType x); /出栈函数，将栈顶元素值放入x中 void ClearStack()top=-1; /清栈函数，用于释放所占的内存空间 bool IsFullStack() return top=maxsize-1; /判断栈是否为满 bool IsEmptyStack(); /判断栈是否为空 void PrintStack(); /将栈中元素输入到屏幕上 ;SeqStack:SeqStack(int size) height=0; top=-1; maxsize=size; /设置最大栈高 elements=new ElemTypesize; void SeqStack:PushStack(ElemType x) if(IsFullStack() cout栈已满; else elements +top=x; height+; ElemType SeqStack:PopStack(ElemType x) x=elementstop; top-; height-; return x; bool SeqStack:IsEmptyStack() /判断栈是否为空 return (height=0)? true:false; void SeqStack:PrintStack() while(IsEmptyStack()=false) coutelementstop ; top-; height-; coutendl; int main() int n; ElemType m; coutn; SeqStack h(n),p(n),l(n); cout学生的成绩为：; for(int i=0;im; cout m100) h.PushStack(m); else if( m=60&m=100) p.PushStack(m); else l.PushStack(m); coutendl; cout小于60的成绩：; l.PrintStack(); cout小于等于100且大于等于60的成绩：; p.PrintStack(); cout大于100的成绩：; h.PrintStack(); system(PAUSE); 实验结果P166.7#include#includeusing namespace std;class LinkQueue; class ListNode /定义链式队列的结点类 friend class LinkQueue; int data; ListNode* link; ;class LinkQueue public: ListNode* head; ListNode* tail; int qsize; /定义队长 int *elements; LinkQueue() head=tail=NULL; /构造函数,建立空队列 LinkQueue() Clear(); /析构函数 void PushTail(int &x); /将新元素插入在队尾 bool PopFront(int &x); /从队头取一个元素 void Clear() ; /清空队列 int IsEmpty() return head=NULL; /判断队列是否为空 int DeleteQueue(); ; 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; bool LinkQueue: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;int LinkQueue:DeleteQueue() ListNode *q=head;/指向队列头元素 head=q-link; int y=q-data;/用y返回队头元素 delete q; return y; int main() LinkQueue q1,q2; for(int i=0; i20; i+) int x=rand()%100; coutx ; if(x%2=1) q1.PushTail(x); /用q1链队存放奇数 else q2.PushTail(x); /用q2链队存放偶数 coutendl; while(!q1.IsEmpty()&!q2.IsEmpty() /每一行输出一个奇数和一个偶数，直到任一队列空为止 cout奇数q1.DeleteQueue() 偶数q2.DeleteQueue()endl; coutendl; system(PAUSE); P166.8#include#include#includeiostreamusing namespace std;class List;typedef char ElemType;class SeqStack/堆栈的数据成员 unsigned height; int top; int maxsize; /栈 的最大元素个数 ElemType *elements; /元素存储空间 public: SeqStack(int size); /构造函数，size用来设置栈的大小 SeqStack() deleteelements; /析构函数 void PushStack(ElemType x); /进栈函数，将元素x压入栈中 ElemType PopStack(ElemType x); /出栈函数，将栈顶元素值放入x中 ElemType topStack(ElemType &e); void ClearStack()top=-1; /清栈函数，用于释放所占的内存空间 bool IsFullStack() return top=maxsize-1; /判断栈是否为满 bool IsEmptyStack(); /判断栈是否为空 void PrintStack(); /将栈中元素输入到屏幕上 ;SeqStack:SeqStack(int size) height=0; top=-1; maxsize=size; /设置最大栈高 elements=new ElemTypesize; void SeqStack:PushStack(ElemType x) if(IsFullStack() cout栈已满; else elements +top=x; height+; ElemType SeqStack:PopStack(ElemType x) x=elementstop; top-; height-; return x; ElemType SeqStack:topStack(ElemType &e) if (height=0) return false; else e=elementstop-1; return e ; bool SeqStack:IsEmptyStack() /判断栈是否为空 return (height=0)? true:false; void SeqStack:PrintStack() while(IsEmptyStack()=false) coutelementstop ; top-; height-; coutendl; int main() int n,x1,x2,x3; x1=0; x2=0; x3=0; char tm;ElemType mn; coutn; SeqStack h(n),p(n),l(n); cout请输入字符串：; for(int i=0;i mi; cout mi ; if(mi=) h.PushStack(mi); else if(mi=) if(h.IsEmptyStack() return false; else h.PopStack(tm); x1+; if( mi=) p.PushStack(mi); else if(mi=) if(p.IsEmptyStack() return false; else p.PopStack(tm); x2+; if( mi=() l.PushStack(mi); else if(mi=) if (l.IsEmptyStack() return false; else l.PopStack(tm); x3+; coutendl; c