数据结构语言版习题集答案-第三章栈与队列

typedef

Elemtype*base[2];Elemtype*top[2];}BDStacktype;StatusInit_Stack(BDStacktype&tws,intm)//初始化一个大小为m的双向栈{returnOK;Statuspush(BDStacktype&tws,inti,Elemtypex)//x入栈,i=0表示栈,i=1表示高{if(tws.top[0]>tws.top[1returnOVERFLOW注意此时的栈满条件if(i==0)*tws.top[0]++=x;elseif(i==1)*tws.top[1]--=x;elsereturnERROR;returnStatuspop(BDStacktype&tws,inti,Elemtype&x)//x出栈,i=0表示栈,i=1表示{{if(tws.top[0]==tws.base[0])returnOVERFLOW;}else{if(tws.top[1]==tws.base[1])returnOVERFLOW;}elsereturnERROR;returnOK;{{voidTrain_arrange(char*train)//这里用字符串train表示火车,'H'表示硬席,'S'表示{{if(*p=='H')push(s,*p把'H'存入栈中else*(q++)=*p;//把'S'调到前部}{*(q++)=c;//把'H'接在后}intIsReverse()//判断输入的字符串中'&'前和'&'后部分是否为逆串,1,{{if(StackEmpty(s))return0;if(e!=c)return}if(!StackEmpty(s))returnreturnStatusBracket_Test(char*str)//判别表达式中小括号是否匹{if(*p=='(')elseif(*p==')')count--if(count<0)return}if(count)returnERROR注意括号不匹配的两种情况returnOK;StatusAllBrackets_Test(char*str)//判别表达式中三种括号是否匹{{if(*p=='('||*p=='['||*p=='{')else{if(StackEmpty(s))returnERROR;if(*p=='}'&&creturnERROR}if(!StackEmpty(s))returnERROR;returnOK;typedefstruct intint}voidRepaint_Color(intg[m][n],inti,intj,intcolor)//把点(i,j)相邻区域的颜色置换为{if(g[x-{g[x-EnQueue(Q,{x-1,y}}if(g[x][y-{g[x][y-EnQueue(Q,{x,y-1}}{EnQueue(Q,{x+1,y}}{EnQueue(Q,{x,y+1}}voidNiBoLan(char*str,char*new)//把中缀表达式str转换成逆波兰式{p=str;q=new;//为方便起见,设str的两端都加上了优先级最低的特殊符InitStack(s/s{if(*p是字母*q++=*p;直接输出{if(*p优先级比c高push(s,*p);{while(gettop(s)优先级不比*p低{push(s,*p}//NiBoLan参见编译原理{p=str;InitStack(s/s{if(*p是数push(s,*p);{pute(b,*p,a);假 pute为执行双目运算的过pop(s,r);returnr;StatusNiBoLan_to_BoLan(char*str,stringtype&new)//把逆波兰表达式str转换波兰式{p=str;Initstack(ss的元素为stringtype类{if(*p为字母push(s,*p);{if(StackEmpty(s))returnERROR;if(StackEmpty(s))returnif(!StackEmpty(s))returnERROR;returnOK;种抽象数据类型stringtype,对其可以进行连接操作:c=link(a,b).Statusg(intm,intn,int&s)//求递归函数g的值{if(m==0&&n>=0)elseif(m>0&&n>=0)s=n+g(m-1,2*n);elsereturnERROR;returnStatusF_recursive(intn,int&s)//递归算{if(n<0)returnERROR;if(n==0)s=n+1;{}returnStatusF_nonrecursive(intn,ints)//非递归算{if(n<0)returnERROR;if(n==0)s=n+1;{InitStack(s/s的元素类型为struct{inta;intb;}{{}return{if(abs(p^2-A)<=e)returnelsereturnfloatSqrt_nonrecursive(floatA,floatp,floate)//求平方根的非递归算{return这一题的所有算法以及栈的变化过程请参见《数据结构(pascal版)》,作者不再详voidInitCiQueue(CiQueue&Q)//初始化循环链表表示的队列{voidEnCiQueue(CiQueue&Q,intx)//把元素x插入循环链表表示的队列Q,Q指向队尾元素,Q->next指向头结点,Q->next->next指向队头元素{p->next=Q->next;直接把p加在QQ-Q=p;//}StatusDeCiQueue(CiQueue&Q,intx)//从循环链表表示的队列Q头部删除元素{if(Q==Q->next)returnINFEASIBLE队列已空returnStatusEnCyQueue(CyQueue&Q,intx)//带tag域的循环队列入队算{if(Q.front==Q.rear&&Q.tag==1)//tag域的值为0表示"空",1表示"满"returnOVERFLOW;if(Q.front==Q.rearQ.tag=1;队列满StatusDeCyQueue(CyQueue&Q,int&x)//带tag域的循环队列出队算{if(Q.front==Q.rear&&Q.tag==0)returnINFEASIBLE;if(Q.front==Q.rearQ.tag=1;队列空returnOK;节约较多的空间,较有价值.StatusEnCyQueue(CyQueue&Q,intx)//带length域的循环队列入队算{returnOK;StatusDeCyQueue(CyQueue&Q,int&x)//带length域的循环队列出队算{if(Q.length==0)returnhead=(Q.rear-Q.length+1)%MAXSIZE详见书后注释Q.length--intPalindrome_Test()//判别输入的字符串是否回文序列,是则返回1,否则返回{{);//}{if(a!=b)returnERROR;}returnvoidGetFib_CyQueue(intk,intn)//求k阶斐波那契序列的前n+1{InitCyQueue(Q)其MAXSIZE设置为kfor(i=0;i<k-1;i++)Q.base[i]=0;Q.base[k-1]=1;//给前k初值for(i=0;i<k;i+printf("%d",Q.base[i]);{for(j=0;j<k;j++)Q.base[m]=sum;求第i}StatusEnDQueue(DQueue&Q,intx)//{if((Q.rear+1)%MAXSIZE==Q.front)returnOVERFLOW队列满if(x>=avr)//根据x的值决定插入在队头还是队{{returnStatusDeDQueue(DQueue&Q,int&x)//{if(Q.front==Q.rearreturnINFEASIBLE队列空returnvoidTrain_Rea