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

第三章栈和队列借助栈实现单链表上的逆置运算。/Stdafx.h#include<iostream>#include<tchar.h>ttincludezztime.h"usingnamespacestd;结点类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);构造函数List(void);析构函数voidinput(intn);输入voidOUtPUt(VOid);输出voidmakcEmpty(void);清空voidinverse(void);逆转函数protected:1.inkNode*first;链表头指针；#Pragmaonceinclude.list.h"classstack(public:stack(void);“stack(VOid);protected:1.inkNode*top;friendclassList;public:voidPush(constint&x);boolPop();boolIsEmpty(void)return(top=NULL)?true:false;)；Itinclude"StdAfx.h"include”.list.h"fusing<mscorlib.dll>1.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;i<n;i+)(intx=rand()%100;newNode=newLinkNode(x);newNode->1ink=first->link;first->link=newNode;)voidList:output(void)(1.inkNode*current=first->link;while(current!=NULL)(cout<<current->data<<zz；current=current->link;)cout<<endl;)voidList:makeEmpty(void)1.inkNode*p;whiIe(first->link!=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;)include"StdAfx.hinclude”.stack.hfusing<mscorlib.dll>stack: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;)include"stdafx.h"include.list.h"#usingll>usingnamespaceSystem;int_tmain()(srand(time(NULL);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<iostream>#include<tchar.h>usingnamespacestd;structLinkNodeintdata;1.inkNode*link;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;);Winclude"StdAfx.hincludestack.hfusing<mscorlib.dll>stack: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;)#include"stdafx.hinclude”.stack.hfusing<mscorlib.dll>usingnamespaceSystem;int_tmain()(intn,m,temp,yu;COUt<<输入十进制数:；cin>>n;COUt<<输入基数：”；cin>>m;stack1;while(n!=O&&m!=0)temp=n%m;n=nm;1.Push(temp);)while(!1.IsEmptyO)1.Pop(yu);cout<<yu;cout<<endl;return0;)试编写一个算法，求解最大公因数问题：在求两个正整数m和n的最大公因数常常使用辗转相除法，反复计算直到余数为零为止。其递归定义为：/stdafx.h#include<iostream>include<tchar.h>#include<math.h>usingnamespacestd;intf(intnl,intn2);includezzstdafx.h"fusing<mscorlib.dll>usingnamespaceSystem;int_tmain()intnl,n2;COUt<<"Enterthefirstpositivenumber:"z<<end1;cin>>nl;cout<<zzEnterthesecondpositivenumber:"z<<endl;cin>>n2;if(nl>O&&n2>0)(cout<<nl<<"和<<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)相等时，队列状态为“空”还是“满、试编写与此结构相应的插入(EnQueue)和删除(DeQlIelIe)算法。#include<iostream>Itinclude<tchar.h>ttinclude<time.h>usingnamespacestd;#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)?true:false;boolIsFulKvoid)return(front=rear&&tag=l)?true:false;friendOStreaoperator<<(ostream&os,SeqQueueftQ);；include"StdAfx.h#include”.SeqQeue.httusing<mscorlib.dll>SeqQueue: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