实验二十 栈与队列的操作.doc

实验二十 栈与队列的操作一、实验目的栈与队列是重要的数据结构，通过本实验要求掌握以下内容：1. 栈结构的特点及操作方法，能用面向对象的方法定义栈结构。2. 队列结构的特点及操作方法，能用面向对象的方法定义并检验队列。二、实验内容1. 定义存储字符的栈类，要求如下：1) 使用教材例7.8中定义的顺序栈模板，用字符作参数定义字符栈，完成压栈和出栈操作，顺序输入26个字母，输出为逆序。2) 修改顺序栈类，当栈满时，执行StackFull()操作：动态创建一个是原来的栈空间的两倍的空间，把原来栈中的内容放入新栈，再删除原栈空间。（这是C+标准模板库中的做法。） #include#includeusing namespace std;templateclass Stackint top; /栈顶指针（下标）T *elements; /动态建立数值的指针int maxSize; /栈最大允纳的元素个数public:Stack(int=20); /栈如不指定大小，设为20元素Stack()delete elements;void Push(const T &data); /压栈T Pop(); /出栈，top减1T GetElem(int i); /取数据，top不变void StackFull(); /堆栈加倍void MakeEmpty()top= -1; /清空栈bool IsEmpty() constreturn top= -1; /判栈是否空bool IsFull() constreturn top=maxSize-1; /判栈是否满void PrintStack(); /输出栈内所有数据;template Stack:Stack(int maxs)maxSize=maxs;top=-1;elements=new T maxSize; /建立栈空间assert(elements!=0); /分配不成功，结束程序template void Stack:PrintStack()for(int i=0;i=top;i+) coutelementsit;coutendl;template void Stack:Push(const T &data)if(IsFull()cout栈满endl;StackFull();/栈满则堆栈加倍 elements+top=data; /栈顶指针先加1，元素再进栈，top是指向栈顶元素template T Stack:Pop()assert(!IsEmpty(); /栈已空则不能退栈，退出程序return elementstop-; /返回栈顶元素，同时栈顶指针减1template T Stack:GetElem(int I)assert(i=0); /超出栈有效数据范围，退出程序return elementsi; /返回栈顶元素，top不变template void Stack:StackFull() /堆栈加倍T * el=elements;int i=maxSize,j;maxSize*=2;elements=new T maxSize; /建立栈空间assert(elements!=0); /分配不成功结束程序for(j=0;ji;j+) elementsj=elj;delete el;cout堆栈空间已加倍，空间为：maxSizeendl;int main()int i;char a25=a,b,c,d,e,f,g,h,i,j,k,l,m,n,o, p,q,r,s,t,u,v,w,x,y,b25;Stack istack(5);for(i=0;i25;i+) istack.Push(ai);istack.PrintStack();i=0;while(!istack.IsEmpty()bi=istack.Pop();i+;if(istack.IsEmpty() cout栈空endl;for(i=0;i25;i+) coutbit;/注意先进后出coutendl;return 0;3) 参考教材例7.9_h，用链式存储结构改写程序，并编程验证。2. 队列与双队列实验：1) 编程：使用教材【例7.10】中定义的顺序队列模板，用字符作参数定义字符队列，完成入队和出队操作，顺序输入26个字母，并按同样顺序输出。*2) 范例：用单链表类模板来表示一个双端队列，要求可在表的两端插入（链表头和尾，即可用向前和也可用向后生成），但只能在表的一端删除（链表头）。给出基于此结构队列的两个入队和一个出队算法的成员函数。#include#includeusing namespace std;templateclass DeQueue;templateclass NodeT info;Node *link;public:Node(T data=0,Node *l=NULL);friend class DeQueue;template Node:Node(T data,Node *l)info=data;link=l;templateclass DeQueueNode *front,*rear;public:DeQueue()rear=front=NULL; /构造一个空链队DeQueue()MakeEmpty();bool IsEmpty() return front=NULL; /队空否？void EnQueFront(const T &data); /进队void EnQueRear(const T &data); /进队T DeQue(); /出队T GetFront(); /查看队头数据void MakeEmpty(); /置空队列，与析构逻辑上不同，物理上一样;templatevoid DeQueue:MakeEmpty()Node *temp;while(front!=NULL)temp=front;front=front-link;delete temp;templatevoid DeQueue:EnQueFront(const T &data)if(front=NULL) front=rear=new Node(data,NULL);else front=new Node(data,front);templatevoid DeQueue:EnQueRear(const T &data)if(front=NULL) front=rear=new Node(data,NULL);else rear=rear-link=new Node(data,NULL);templateT DeQueue:DeQue()assert(!IsEmpty();Node *temp=front;T data=temp-info;front=front-link;delete temp;return data;templateT DeQueue:GetFront()assert(!IsEmpty();return front-info;int main()int i;DeQueue que; char str1=abcdefghijklmnopqrstuvwxyz;cout从队尾入队endl;for(i=0;i26;i+) que.EnQueRear(str1i);for(i=0;i26;i+) coutque.DeQue()t; /先进先出coutendl;if(que.IsEmpty() cout队空endl;cout从队首入队endl;for(i=0;i26;i+) que.EnQueFront(str1i);for(i=0;i26;i+) coutque.DeQue()t; /先进先出coutendl;if(que.IsEmpty() cout队空endl;return 0;3. 范例：四色地图问题。对于行政区划图，可以用不多于四种的颜色进行着色区分，使相邻行政区域不重色。可以用回溯法验证这一定理。n个行政区域之间的相邻关系可以用关系矩阵Rnn来表示。如果区域i与区域j相邻，则Rij=Rji=1；如果不相邻，则Rij=Rji=0；如果i=j，则对应元素为0。如图1.10的行政区划图，对应关系矩阵为图1.12。颜色用整型数1，2，3，4表示。使用栈来存储每个行政区着色结果，栈的下标与行政区号相同。要求读懂下面的程序，并为主程序添加注释。再设计一个行政区图，检验程序是否有错。01234567000101000100110000211011000301101100410110110500011010600001100700000000图1.12 关系矩阵图12345670 图1.11 华东行政区图#include#includeusing namespace std;templateclass Stackint top; /栈顶指针（下标）T *elements; /动态建立的数值int maxSize; /栈最大允纳的元素个数public:Stack(int=20); /栈的默认大小为20个元素Stack()delete elements;void Push(const T &data); /压栈T Pop(); /弹出，top减1T GetElem(int i); /取数据，top不变void StackFull(); /堆栈加倍void MakeEmpty()top= -1; /清空栈bool IsEmpty() constreturn top= -1; /判栈空bool IsFull() constreturn top=maxSize-1; /判栈满void PrintStack(); /输出栈内所有数据;template Stack:Stack(int maxs)maxSize=maxs;top=-1;elements=new T maxSize; /建立栈空间assert(elements!=0); /分配不成功结束程序template void Stack:PrintStack()for(int i=0;i=top;i+) coutelementsit;coutendl;template void Stack:Push(const T &data)if(IsFull()cout栈满endl;StackFull();/栈满则堆栈加倍 elements+top=data; /栈顶指针先加1，元素再进栈，top指向栈顶元素template T Stack:Pop()assert(!IsEmpty(); /栈已空则不能退栈，退出程序return elementstop-; /返回栈顶元素，同时栈顶指针减1template T Stack:GetElem(int i)assert(i=0); /超出栈有效数据则错，退出程序return elementsi; /返回栈顶元素，top不变template void Stack:StackFull() /堆栈加倍T * el=elements;int i=maxSize,j;maxSize*=2;elements=new T maxSize; /建立栈空间assert(elements!=0); /分配不成功，结束程序for(j=0;ji;j+) elementsj=elj;delete el;cout堆栈空间已加倍，空间为：maxSizeendl;const int n=8;int main()int rnn=0,0,1,0,1,0,0,0, 0,0,1,1,0,0,0,0, 1,1,0,1,1,0,0,0,0,1,1,0,1,1,0,0,1,0,1,1,0,