递归及队列(共10页)

1、精选优质文档-倾情为你奉上实验报告五 递归及队列一、 实验目的：（1） 掌握递归的基本思想。（2） 掌握链式队列及循环队列的基本操作算法。（3） 应用队列先进先出的特点，解决一些实际问题。二、 实验内容：1、 p(a-b，b)+1 当a>=bp(a,b)= 其中a,b为正整数。 0 当a<b利用递归设计此函数。#include<iostream.h>int p(int a,int b)if(a<b)return 0;elsereturn p(a-b,b)+1; void main() int x;x=p(6,2);cout<<"结果为: &q

2、uot;<<x<<endl;int y;y=p(3,4);cout<<"结果为: "<<y<<endl;粘贴测试数据及运行结果：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)？粘贴#include<iostream.h>int akm(int m,int n)if(m=0)return n+1; if(m && !n)retu

3、rn akm(m-1,1);else return akm(m-1,akm(m,n-1);void main() int s,t,l;s=akm(0,8);cout<<"结果为: "<<s<<endl;t=akm(1,2);cout<<"结果为: "<<t<<endl;l=akm(2,1);cout<<"结果为: "<<l<<endl;测试数据及运行结果：3、循环队列的实现（请采用模板类及模板函数实现）实现提示函数、类名称等可自

4、定义，部分变量请加上学号后3位。也可自行对类中所定义的操作进行扩展。所加载的库函数或常量定义及类的定义：#include<iostream>using namespace std;int maxsize=100;template <class T> /定义模板类DCirQueueclass DCirQueuepublic: DCirQueue( int size=10); /构造函数，置空队 DCirQueue( )delete queue; /析构函数 void EnQueue(T x); /将元素x入队 T DeQueue( ); /将队头元素出队 T GetQue

5、ue( ); /取队头元素（并不删除）int IsEmpty( ); /判断队列是否为空int length(); /求队列元素个数void display(); /遍历队列int destroy(); /清空队列private: T *queue; /存放队列元素的数组 int front, rear; /队头和队尾指针，分别指向队头元素的前一个位置和队尾元素的位置 int maxsize; /队列最大可容纳元素个数为maxsize-1;（1）构造一个空的循环队列 输入：队列元素存储区域的大小size;动作：初始化队列，队头及队尾指示器,申请存储队列的数组，设置队列存储区域的大小templa

6、te <class T>DCirQueue<T>:DCirQueue( int size):front(0),rear(0),maxsize(size) queue=new Tmaxsize;if(queue=NULL) cout<<"动态分配失败!" （2）入队操作算法实现：输入：要入队的元素x;前置条件：队列未满动作：把x插入队尾输出：无后置条件：队列中增加了一个元素template <class T> void DCirQueue<T>:EnQueue(T x) if (rear+1) % maxsize =

7、front) cout<<“队满" rear=(rear+1) % maxsize; /队尾指针在循环意义下加1 queuerear=x; /在队尾处插入元素（3）求队列的元素个数算法输入：无前置条件：无；动作：求队列的元素个数，含表空返回个数为零的情况。输出：返回队列的元素个数。template <class T> int DCirQueue<T>:length()int length;length=（maxsizerearfront）% maxsize;return length;（4）出队操作算法输入：无前置条件：队列非空动作：删除队头元素输

8、出：返回队头元素的值后置条件：队列中删除了一个元素template <class T> T DCirQueue<T>:DeQueue( ) if (rear=front) cout<< "下溢!" front=(front+1) % maxsize; /队头指针在循环意义下加1 return queuefront; /读取并返回出队前的队头元素，注意队头指针（5）遍历队列算法输入：无前置条件：队列非空动作：输出队列中的各元素输出：无后置条件：无template <class T> void DCirQueue<T>

9、:display()while(rear！=front) i=(front+1) % maxsize; front+; cout<<queuei-1<<” ”; （7）判队列为空算法输入：无前置条件：队列存在动作：判是否为空输出：空返回1，否则返回0后置条件：无template <class T>int DCirQueue<T>:IsEmpty( )if(front=rear)return 1;return 0;（8）获得队列头结点输入：无前置条件：队列存在动作：获得队头的元素输出：返回队头的元素值后置条件：无template <class

10、 T>T DCirQueue<T>:GetQueue( ) int i; if (rear=front) throw “队空!" i=(front+1) % maxsize; /注意不要给队头指针赋值 return queuei;测试主函数:void main()DCirQueue<int> myqueue(80);int a=3,6,8,78,35,67;int n=6;for(int i=0;i<n;i+)myqueue.EnQueue(ai);cout<<"队列长度为: "<<myqueue.len

11、gth()<<endl;cout<<"队头元素: "<<myqueue.GetQueue( )<<endl;cout<<"删除队头元素: "<<myqueue.DeQueue( )<<endl;cout<<"队列长度为: "<<myqueue.length()<<endl;myqueue.EnQueue(9);myqueue.EnQueue(75);cout<<"队列长度为: "<

12、;<myqueue.length()<<endl;cout<<"队列是否已满（1表示已满，0表示未满）: "<<myqueue.IsEmpty( )<<endl;cout<<"diyichibianli: "myqueue.display();cout<<endl;cout<<"队列是否已满（1表示已满，0表示未满）: "<<myqueue.IsEmpty( )<<endl;粘贴测试数据及运行结果：4、链式队列的基本操作算

13、法实现（请采用模板类及模板函数实现）实现提示 同时可参见教材p98-p99页的ADT描述及算法实现及ppt）函数、类名称等可自定义，部分变量请加上学号后3位。也可自行对类中所定义的操作进行扩展。所加载的库函数或常量定义及类的定义：（自选择带头结点或不带头结点）#include<iostream.h>template <class T>class LinkQueue;template <class T>class Node friend class LinkQueue<T>private:T data; Node<T> *next; /

14、此处<T>也可以省略;template <class T>class LinkQueuepublic: LinkQueue( ); /构造函数，初始化一个空的链队列 LinkQueue(T a,int n ); /有参构造函数 LinkQueue( ) /析构函数，释放链队中各结点的存储空间 void EnQueue(T x); /将元素x入队 T DeQueue( ); /将队头元素出队 T GetQueue( ); /取链队列的队头元素 int Empty( ); /判断链队列是否为空 int length(); /求队列长度 void display(); /遍历

15、private: Node<T> *front, *rear; /队头和队尾指针，分别指向头结点和终端结点;（1）初始化链式空队列关键动作：初始化队列，设置队头及队尾指示器。 template <class T>LinkQueue<T>:LinkQueue( )front=rear=NULL;（2）带参数的构造函数，实现创建链式队列输入：存储放初始数据元素的数组a，元素个数n前置条件：队列不存在动作：把a中的数据元素依次插入队尾输出：无后置template <class T> LinkQueue<T>:LinkQueue(T a,in

16、t n )front=rear=NULL; Node<T> *s; s=new Node<T> for(int i=0;i<n;i+) s->data=ai; /申请一个数据域为x的结点s s->next=NULL; rear=s; 条件：队列中有n个元素入队（3）入队操作算法输入：要入队的元素x;前置条件：队列未满动作：把x插入队尾输出：无后置条件：队列中增加了一个元素template <class T> void LinkQueue<T>:EnQueue(T x) Node<T> *s; s=new Node&l

17、t;T> s->data=x; /申请一个数据域为x的结点s s->next=NULL;if(front=NULL) /空队列，新结点既是队头，又是队尾 front=rear=s;else rear->next=s; /将结点s插入到队尾 rear=s;（4）出队操作算法输入：无前置条件：队列非空动作：删除队头元素输出：返回队头元素的值后置条件：队列中删除了一个元素template <class T>T LinkQueue<T>:DeQueue() Node <T> *p; int x; if (front=NULL) cout<

18、;<"队空" p=front; x=p->data; /暂存队头元素 front=front->next; /将队头元素所在结点摘链 if (front=NULL) rear=front; /判断出队前队列长度是否为1 delete p; return x;（5）清空队列算法输入：无前置条件：队列存在动作：释放队列的存储空间输出：无后置条件：队列不存在template <class T>Void LinkQueue<T>:destroy( )Node <T> *p,*q;P=front;While(p!=(rear-&g

19、t;next)q=p;P=p->next;Delete q;Front=rear=NULL;（6）判队列为空算法输入：无前置条件：队列存在动作：判是否为空输出：空返回1，否则返回0后置条件：无template <class T> int LinkQueue<T>:Empty( )if(rear=NULL)return 1;return 0;（7）获得队列头结点输入：无前置条件：队列存在动作：获得队头的元素输出：返回队头的元素值后置条件：无template <class T> T LinkQueue<T>:GetQueue() if (fro

20、nt!=NULL) return front->data;（8）遍历队列中的元素输入：无前置条件：队列非空动作：输出队列中的各元素输出：无后置条件：无template <class T>void LinkQueue<T>:display()while(front!=(rear->next)cout<<front->data<<" " front=front->next;（9）求队列数据元素个数输入：无前置条件：无；动作：求队列的元素个数，含表空返回个数为零的情况。输出：返回队列的元素个数。template <class T>int LinkQueue<T>:length()int