数据结构第三章到第九章练习题答案.docx

《数据结构第三章到第九章练习题答案.docx》由会员分享，可在线阅读，更多相关《数据结构第三章到第九章练习题答案.docx（30页珍藏版）》请在优知文库上搜索。

1、第三章栈和队列借助栈实现单链表上的逆置运算。/Stdafx.h#include#includettincludezztime.husingnamespacestd;结点类structLinkNodeintdata;1.inkNode*link;1.inkNode(constint&item,LinkNode*ptr=NULL)data=item;link=ptr;1.inkNode(LinkNode*ptr=NULL)link=ptr;；#Pragmaonce带附加头结点的单链表classList(public:1.ist(void);构造函数1.ist(constint&x);构造函数Lis

2、t(void);析构函数voidinput(intn);输入voidOUtPUt(VOid);输出voidmakcEmpty(void);清空voidinverse(void);逆转函数protected:1.inkNode*first;链表头指针；#Pragmaonceinclude.list.hclassstack(public:stack(void);“stack(VOid);protected:1.inkNode*top;friendclassList;public:voidPush(constint&x);boolPop();boolIsEmpty(void)return(top=N

3、ULL)?true:false;)；ItincludeStdAfx.hinclude”.list.hfusing1.ist:List(constint&x)(first=newLinkNode(x);)1.ist:List(void)(first=newLinkNode;)1.ist:List(void)(makeEmpty();)voidList:input(intn)(1.inkNode*newNode;first=newLinkNode;for(inti=0;i1ink=first-link;first-link=newNode;)voidList:output(void)(1.inkN

4、ode*current=first-link;while(current!=NULL)(coutdatalink;)coutlink!=NULL)p=first-link;first-link=p-link;deletep;)逆转函数voidList:inverse(void)(stacks;1.inkNode*p=first-link,*q;while(p!=NULL)(s.Push(p-data);p=p-link;)p=first-link;while(!s.IsEmptyO)(q=s.top;p-data=q-data;p=p-link;s.PopO;)includeStdAfx.hi

5、nclude”.stack.hfusingstack:stack(void):top(NULL)()stack:飞tack(void)()入栈voidstack:Push(constint&x)(top=newLinkNode(x,top);)出栈boolstack:Pop()(if(IsEmptyO-true)returnfalse;1.inkNode*p=top;top=top-link;deletep;returntrue;)includestdafx.hinclude.list.h#usingllusingnamespaceSystem;int_tmain()(srand(time(N

6、ULL);1.ist1;调用输入函数1.input(10);调用输出函数1.output();COUt调用逆转函数endl;1.inverse();调用输出函数1.output();return0;QB数据结构作业3新建文件夹逆转Debug实套exeHglX7662241调用逆转函数217205Pressanykey367907221?9364122676tocontinue编写一个算法，将一个非负的十进制整数N转换为另一个基为B的B进制数。/stdafx.h#include#includeusingnamespacestd;structLinkNodeintdata;1.inkNode*li

7、nk;1.inkNode(constint&item,LinkNode*ptr=NULL)(data=item;link=ptr;1.inkNode(LinkNode*ptr=NULL)link=ptr;)；#Pragmaonceclassstackpublic:stack(void);stack(void);voidPush(constint&x);boolPop(int&x);boolIsEmpty(void)return(top=NULL)?true:false;protected:1.inkNode*top;);WincludeStdAfx.hincludestack.hfusings

8、tack:stack(void):top(NULL)()stack:StaCk(VOid)()voidstack:Push(constint&x)(top=newLinkNode(x,top);)boolstack:Pop(int&x)(if(IsEmpty()=true)returnfalse;1.inkNode*p=top;top=top-link;x=p-data;deletep;returntrue;)#includestdafx.hinclude”.stack.hfusingusingnamespaceSystem;int_tmain()(intn,m,temp,yu;COUtn;C

9、OUtm;stack1;while(n!=O&m!=0)temp=n%m;n=nm;1.Push(temp);)while(!1.IsEmptyO)1.Pop(yu);coutyu;coutendl;return0;)试编写一个算法，求解最大公因数问题：在求两个正整数m和n的最大公因数常常使用辗转相除法，反复计算直到余数为零为止。其递归定义为：/stdafx.h#includeinclude#includeusingnamespacestd;intf(intnl,intn2);includezzstdafx.hfusingusingnamespaceSystem;int_tmain()intn

10、l,n2;COUtEnterthefirstpositivenumber:znl;coutzzEnterthesecondpositivenumber:zn2;if(nlO&n20)(coutnl和n2的最大公约数是：f(nl,n2)endl;)elseCoUt非法数据endl;returnO;)intf(intnl,intn2)(intt;while(n2!=0)(t=nl%112inl=n2;n2=t;)returnnl;)3.23假设以数组Qm存放循环队列中的元素，同时设置一个标志tag,以tag=O和tag=l来区别在对头指针(fr。IIt)和对尾指针(rear)相等时，队列状态为“空

11、”还是“满、试编写与此结构相应的插入(EnQueue)和删除(DeQlIelIe)算法。#includeItincludettincludeusingnamespacestd;#pragmaonceclassSeqQueuepublic:SeqQueue(intsize=10);SeqQucue(void);protected:intrear,front,tag;int*element;intmaxSize;public:boolEnQueue(constint&x);boolDeQueue(void);boolIsEmpty(void)return(front=rear&tag=0)?tru

12、e:false;boolIsFulKvoid)return(front=rear&tag=l)?true:false;friendOStreaoperator(ostream&os,SeqQueueftQ);；includeStdAfx.h#include”.SeqQeue.httusingSeqQueue:SeqQueue(intsize):rear(O),front(O),tag(O),maxSize(size)(element=newintmaxSize;SeqQucue:SeqQucue(void)deleteelement;)boolSeqQueue:EnQueue(constint&x)if(IsFullO=true)returnfalse;elementrear=x;rear=(rear+l)%maxSize;tag=l;returntrue;)boolSeqQueue:DeQueue(void)if(IsEmpty()=true)returnfalse;front=(front+1)%maxSize;tag=0;returntrue;)Ostreamftoperator(ostream&os,SeqQueuefeQ)(in