实验5-递归及队列

实验报告五 递归及队列一、 实验目的：（1） 掌握递归的基本思想。（2） 掌握链式队列及循环队列的基本操作算法。（3） 应用队列先进先出的特点，解决一些实际问题。二、 实验内容：1、 p(a-b，b)+1 当a=bp(a,b)= 其中a,b为正整数。 0 当ab利用递归设计此函数。#includeint p(int a,int b)if(ab)return 0;elsereturn p(a-b,b)+1; void main() int x;x=p(6,2);cout结果为: xendl;int y;y=p(3,4);cout结果为: yendl;粘贴测试数据及运行结果：2、Ackerman函数如下： n+1 当m=0akm(m,n)= akm(m-1,1) 当m0,n=0 akm(m-1,akm(m,n-1) 其它情形利用递归设计此函数。试求akm(1，2),akm(2，1)？粘贴#includeint akm(int m,int n)if(m=0)return n+1; if(m & !n)return akm(m-1,1);else return akm(m-1,akm(m,n-1);void main() int s,t,l;s=akm(0,8);cout结果为: sendl;t=akm(1,2);cout结果为: tendl;l=akm(2,1);cout结果为: lendl;测试数据及运行结果：3、循环队列的实现（请采用模板类及模板函数实现）实现提示函数、类名称等可自定义，部分变量请加上学号后3位。也可自行对类中所定义的操作进行扩展。所加载的库函数或常量定义及类的定义：#includeusing namespace std;int maxsize=100;template /定义模板类DCirQueueclass DCirQueuepublic: DCirQueue( int size=10); /构造函数，置空队 DCirQueue( )delete queue; /析构函数 void EnQueue(T x); /将元素x入队 T DeQueue( ); /将队头元素出队 T GetQueue( ); /取队头元素（并不删除）int IsEmpty( ); /判断队列是否为空int length(); /求队列元素个数void display(); /遍历队列int destroy(); /清空队列private: T *queue; /存放队列元素的数组 int front, rear; /队头和队尾指针，分别指向队头元素的前一个位置和队尾元素的位置 int maxsize; /队列最大可容纳元素个数为maxsize-1;（1）构造一个空的循环队列 输入：队列元素存储区域的大小size;动作：初始化队列，队头及队尾指示器,申请存储队列的数组，设置队列存储区域的大小template DCirQueue:DCirQueue( int size):front(0),rear(0),maxsize(size) queue=new Tmaxsize;if(queue=NULL) cout动态分配失败!; （2）入队操作算法实现：输入：要入队的元素x;前置条件：队列未满动作：把x插入队尾输出：无后置条件：队列中增加了一个元素template void DCirQueue:EnQueue(T x) if (rear+1) % maxsize =front) cout“队满; rear=(rear+1) % maxsize; /队尾指针在循环意义下加1 queuerear=x; /在队尾处插入元素（3）求队列的元素个数算法输入：无前置条件：无；动作：求队列的元素个数，含表空返回个数为零的情况。输出：返回队列的元素个数。template int DCirQueue:length()int length;length=（maxsizerearfront）% maxsize;return length;（4）出队操作算法输入：无前置条件：队列非空动作：删除队头元素输出：返回队头元素的值后置条件：队列中删除了一个元素template T DCirQueue:DeQueue( ) if (rear=front) cout 下溢!; front=(front+1) % maxsize; /队头指针在循环意义下加1 return queuefront; /读取并返回出队前的队头元素，注意队头指针（5）遍历队列算法输入：无前置条件：队列非空动作：输出队列中的各元素输出：无后置条件：无template void DCirQueue:display()while(rear！=front) i=(front+1) % maxsize; front+; coutqueuei-1” ”; （7）判队列为空算法输入：无前置条件：队列存在动作：判是否为空输出：空返回1，否则返回0后置条件：无template int DCirQueue:IsEmpty( )if(front=rear)return 1;return 0;（8）获得队列头结点输入：无前置条件：队列存在动作：获得队头的元素输出：返回队头的元素值后置条件：无template T DCirQueue:GetQueue( ) int i; if (rear=front) throw “队空!; i=(front+1) % maxsize; /注意不要给队头指针赋值 return queuei;测试主函数:void main()DCirQueue myqueue(80);int a=3,6,8,78,35,67;int n=6;for(int i=0;in;i+)myqueue.EnQueue(ai);cout队列长度为: myqueue.length()endl;cout队头元素: myqueue.GetQueue( )endl;cout删除队头元素: myqueue.DeQueue( )endl;cout队列长度为: myqueue.length()endl;myqueue.EnQueue(9);myqueue.EnQueue(75);cout队列长度为: myqueue.length()endl;cout队列是否已满（1表示已满，0表示未满）: myqueue.IsEmpty( )endl;coutdiyichibianli: ;myqueue.display();coutendl;cout队列是否已满（1表示已满，0表示未满）: myqueue.IsEmpty( )endl;粘贴测试数据及运行结果：4、链式队列的基本操作算法实现（请采用模板类及模板函数实现）实现提示 同时可参见教材p98-p99页的ADT描述及算法实现及ppt）函数、类名称等可自定义，部分变量请加上学号后3位。也可自行对类中所定义的操作进行扩展。所加载的库函数或常量定义及类的定义：（自选择带头结点或不带头结点）#includetemplate class LinkQueue;template class Node friend class LinkQueue;private:T data; Node *next; /此处也可以省略;template class LinkQueuepublic: LinkQueue( ); /构造函数，初始化一个空的链队列 LinkQueue(T a,int n ); /有参构造函数 LinkQueue( ) /析构函数，释放链队中各结点的存储空间 void EnQueue(T x); /将元素x入队 T DeQueue( ); /将队头元素出队 T GetQueue( ); /取链队列的队头元素 int Empty( ); /判断链队列是否为空 int length(); /求队列长度 void display(); /遍历private: Node *front, *rear; /队头和队尾指针，分别指向头结点和终端结点;（1）初始化链式空队列关键动作：初始化队列，设置队头及队尾指示器。 template LinkQueue:LinkQueue( )front=rear=NULL;（2）带参数的构造函数，实现创建链式队列输入：存储放初始数据元素的数组a，元素个数n前置条件：队列不存在动作：把a中的数据元素依次插入队尾输出：无后置template LinkQueue:LinkQueue(T a,int n )front=rear=NULL; Node *s; s=new Node; for(int i=0;idata=ai; /申请一个数据域为x的结点s s-next=NULL; rear=s; 条件：队列中有n个元素入队（3）入队操作算法输入：要入队的元素x;前置条件：队列未满动作：把x插入队尾输出：无后置条件：队列中增加了一个元素template void LinkQueue:EnQueue(T x) Node *s; s=new Node; s-data=x; /申请一个数据域为x的结点s s-next=NULL;if(front=NULL) /空队列，新结点既是队头，又是队尾 front=rear=s;else rear-next=s; /将结点s插入到队尾 rear=s;（4）出队操作算法输入：无前置条件：队列非空动作：删除队头元素输出：返回队头元素的值后置条件：队列中删除了一个元素template T LinkQueue:DeQueue() Node *p; int x; if (front=NULL) coutdata; /暂存队头元素 front=front-next; /将队头元素所在结点摘链 if (front=NULL) rear=front; /判断出队前队列长度是否为1 delete p; return x;（5）清空队列算法输入：无前置条件：队列存在动作：释放队列的存储空间输出：无后置条件：队列不存在template Void LinkQueue:destroy( )Node *p,*q;P=front;While(p!=(rear-next)q=p;P=p-next;Delete q;Front=rear=NULL;（6）判队列为空算法输入：无前置条件：队列存在动作：判是否为空输出：空返回1，否则返回0后置条件：无template int LinkQueue:Empty( )if(rear=NULL)return 1;return 0;（7）获得队列头结点输入：无前置条件：队列存在动作：获得队头的元素输出：返回队头的元素值后置条件：无template T LinkQueue:GetQueue() if (front!=NULL) return front-data;（8）遍历队列中的元素输入：无前置条件：队列非空动作：输出队列中的各元素输出：无后置条件：无template void LinkQueue:display()while(front!=(rear-next)coutdatanext;（9）求队列数据元素个数输入：无前置条件：无；动作：求队列的元素个数，含表空返回个数为零的情况。输出：返回队列的元素个数。template int LinkQueue:length()int n=0;while(front!=(rear-next) front=front-next; n+; void main()int a=1,34,67,89,34,78;int n=6;LinkQueuemyqueue;for(int i=0;in;i+)myqueue.EnQueue(ai);cout队头元素为: ;coutmyqueue.GetQueue()endl;myqueue.EnQueue(94);myqueue.EnQueue(2);cout获得队列头元素并删除