实验5递归及队列.docx
- 文档编号:2618207
- 上传时间:2023-05-04
- 格式:DOCX
- 页数:17
- 大小:47.16KB
实验5递归及队列.docx
《实验5递归及队列.docx》由会员分享,可在线阅读,更多相关《实验5递归及队列.docx(17页珍藏版)》请在冰点文库上搜索。
实验5递归及队列
实验报告五递归及队列
一、实验目的:
(1)掌握递归的基本思想。
(2)掌握链式队列及循环队列的基本操作算法。
(3)应用队列先进先出的特点,解决一些实际问题。
二、实验内容:
1、p(a-b,b)+1当a>=b
p(a,b)=其中a,b为正整数。
0当a
利用递归设计此函数。
#include
intp(inta,intb)
{
if(a
return0;
else
returnp(a-b,b)+1;
}
voidmain()
{intx;
x=p(6,2);
cout<<"结果为:
"< inty; y=p(3,4); cout<<"结果为: "< } 粘贴测试数据及运行结果: 2、Ackerman函数如下: n+1当m=0 akm(m,n)=akm(m-1,1)当m≠0,n=0 akm(m-1,akm(m,n-1))其它情形 利用递归设计此函数。 试求akm(1,2),akm(2,1)? 粘贴#include intakm(intm,intn) { if(m==0) returnn+1; if(m&&! n) returnakm(m-1,1); else { returnakm(m-1,akm(m,n-1)); } } voidmain() {ints,t,l; s=akm(0,8); cout<<"结果为: "< t=akm(1,2); cout<<"结果为: "< l=akm(2,1); cout<<"结果为: "< }测试数据及运行结果: 3、循环队列的实现(请采用模板类及模板函数实现) [实现提示]函数、类名称等可自定义,部分变量请加上学号后3位。 也可自行对类中所定义的操作进行扩展。 所加载的库函数或常量定义及类的定义: #include usingnamespacestd; intmaxsize=100; template classDCirQueue {public: DCirQueue(intsize=10);//构造函数,置空队 ~DCirQueue(){delete[]queue;};//析构函数 voidEnQueue(Tx);//将元素x入队 TDeQueue();//将队头元素出队 TGetQueue();//取队头元素(并不删除) intIsEmpty();//判断队列是否为空 intlength();//求队列元素个数 voiddisplay();//遍历队列 intdestroy();//清空队列 private: T*queue;//存放队列元素的数组 intfront,rear;//队头和队尾指针,分别指向队头元素的前一个位置和队尾元素的位置 intmaxsize;//队列最大可容纳元素个数为maxsize-1 }; (1)构造一个空的循环队列 输入: 队列元素存储区域的大小size; 动作: 初始化队列,队头及队尾指示器,申请存储队列的数组,设置队列存储区域的大小 template DCirQueue : DCirQueue(intsize) : front(0),rear(0),maxsize(size) { queue=newT[maxsize]; if(queue==NULL) cout<<"动态分配失败! "; } (2)入队操作算法实现: 输入: 要入队的元素x; 前置条件: 队列未满 动作: 把x插入队尾 输出: 无 后置条件: 队列中增加了一个元素 template voidDCirQueue : EnQueue(Tx) { if((rear+1)%maxsize==front)cout<<“队满"; rear=(rear+1)%maxsize;//队尾指针在循环意义下加1 queue[rear]=x;//在队尾处插入元素 } (3)求队列的元素个数算法 输入: 无 前置条件: 无; 动作: 求队列的元素个数,含表空返回个数为零的情况。 输出: 返回队列的元素个数。 template intDCirQueue : length() {intlength; length=(maxsize+rear-front)%maxsize; returnlength; } (4)出队操作算法 输入: 无 前置条件: 队列非空 动作: 删除队头元素 输出: 返回队头元素的值 后置条件: 队列中删除了一个元素 template TDCirQueue : DeQueue() { if(rear==front)cout<<"下溢! "; front=(front+1)%maxsize;//队头指针在循环意义下加1 returnqueue[front];//读取并返回出队前的队头元素,注意队头指针 } (5)遍历队列算法 输入: 无 前置条件: 队列非空 动作: 输出队列中的各元素 输出: 无 后置条件: 无 template voidDCirQueue : display() {while(rear! =front) {i=(front+1)%maxsize; front++; cout< } (7)判队列为空算法 输入: 无 前置条件: 队列存在 动作: 判是否为空 输出: 空返回1,否则返回0 后置条件: 无 template intDCirQueue : IsEmpty() {if(front==rear) return1; return0; } (8)获得队列头结点 输入: 无 前置条件: 队列存在 动作: 获得队头的元素 输出: 返回队头的元素值 后置条件: 无 template TDCirQueue : GetQueue() { inti; if(rear==front)throw“队空! "; i=(front+1)%maxsize;//注意不要给队头指针赋值 returnqueue[i]; } 测试主函数: voidmain() { DCirQueue inta[]={3,6,8,78,35,67}; intn=6; for(inti=0;i myqueue.EnQueue(a[i]); cout<<"队列长度为: "< cout<<"队头元素: "< cout<<"删除队头元素: "< cout<<"队列长度为: "< myqueue.EnQueue(9); myqueue.EnQueue(75); cout<<"队列长度为: "< cout<<"队列是否已满(1表示已满,0表示未满): "< cout<<"diyichibianli: "; myqueue.display(); cout< cout<<"队列是否已满(1表示已满,0表示未满): "< } 粘贴测试数据及运行结果: 4、链式队列的基本操作算法实现(请采用模板类及模板函数实现) [实现提示]同时可参见教材p98-p99页的ADT描述及算法实现及ppt)函数、类名称等可自定义,部分变量请加上学号后3位。 也可自行对类中所定义的操作进行扩展。 所加载的库函数或常量定义及类的定义: (自选择带头结点或不带头结点) #include template template classNode {friendclassLinkQueue private: Tdata; Node }; template classLinkQueue { public: LinkQueue();//构造函数,初始化一个空的链队列 LinkQueue(Ta[],intn);//有参构造函数 ~LinkQueue(){}//析构函数,释放链队中各结点的存储空间 voidEnQueue(Tx);//将元素x入队 TDeQueue();//将队头元素出队 TGetQueue();//取链队列的队头元素 intEmpty();//判断链队列是否为空 intlength();//求队列长度 voiddisplay();//遍历 private: Node }; (1)初始化链式空队列 关键动作: 初始化队列,设置队头及队尾指示器。 template LinkQueue : LinkQueue() { front=rear=NULL; } (2)带参数的构造函数,实现创建链式队列 输入: 存储放初始数据元素的数组a[],元素个数n 前置条件: 队列不存在 动作: 把a中的数据元素依次插入队尾 输出: 无 后置template LinkQueue : LinkQueue(Ta[],intn) { front=rear=NULL; Node s=newNode for(inti=0;i { s->data=a[i];//申请一个数据域为x的结点s s->next=NULL; rear=s; } }条件: 队列中有n个元素入队 (3)入队操作算法 输入: 要入队的元素x; 前置条件: 队列未满 动作: 把x插入队尾 输出: 无 后置条件: 队列中增加了一个元素 template voidLinkQueue : EnQueue(Tx) { Node s=newNode s->data=x;//申请一个数据域为x的结点s s->next=NULL; if(front==NULL)//空队列,新结点既是队头,又是队尾 {front=rear=s;} else {rear->next=s;//将结点s插入到队尾 rear=s;} } (4)出队操作算法 输入: 无 前置条件: 队列非空 动作: 删除队头元素 输出: 返回队头元素的值 后置条件: 队列中删除了一个元素 template TLinkQueue : DeQueue() { Node if(front==NULL) cout<<"队空"; p=front; x=p->data;//暂存队头元素 front=front->next;//将队头元素所在结点摘链 if(front==NULL)rear=front;//判断出队前队列长度是否为1 deletep; returnx; } (5)清空队列算法 输入: 无 前置条件: 队列存在 动作: 释放队列的存储空间 输出: 无 后置条件: 队列不存在 template VoidLinkQueue : destroy() {Node P=front; While(p! =(rear->next)) {q=p; P=p->next; Deleteq; } Front=rear=NULL; } (6)判队列为空算法 输入: 无 前置条件: 队列存在 动作: 判是否为空 输出: 空返回1,否则返回0 后置条件: 无 template intLinkQueue : Empty() { if(rear==NULL) return1; return0; } (7)获得队列头结点 输入: 无 前置条件: 队列存在 动作: 获得队头的元素 输出: 返回队头的元素值 后置条件: 无 template TLinkQueue : GetQueue() { if(front! =NULL) returnfront->data; } (8)遍历队列中的元素 输入: 无 前置条件: 队列非空 动作: 输出队列中的各元素 输出: 无 后置条件: 无 template voidLinkQueue : display() {while(front! =(rear->next)) { cout< front=front->next; } } (9)求队列数据元素个数 输入: 无 前置条件: 无; 动作: 求队列的元素个数,含表空返回个数为零的情况。 输出: 返回队列的元素个数。 template intLinkQueue : length() {intn=0; while(front! =(rear->next)) { front=front->next; n++; } voidmain() { inta[]={1,34,67,89,34,78}; intn=6; LinkQueue for(inti=0;i myqueue.EnQueue(a[i]); cout<<"队头元素为: "; cout< myqueue.EnQueue(94); myqueue.EnQueue (2); cout<<"获得队列头元素并删除: "; cout< cout<<"队列是否为空(1表示为空,0表示非空): "< myqueue.DeQueue(); cout< cout<<"遍历队列: "; myqueue.display(); cout< } 粘贴测试数据及运行结果: 三、心得体会: 经过前面几个实验,如今编程已经觉得简单多了,有时出现的错误,因为看多了也就很容易的改成正确的。 觉得递归算法真的很简洁,短小精悍,不起眼几句语句就实现了复杂的运算,打算以后编程序尽量往递归算法上靠拢。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 实验 递归 队列