严蔚敏数据结构c语言版习题集答案第三章栈与队列.docx

第三章 栈与队列 3.15 typedef struct Elemtype *base2; Elemtype *top2; BDStacktype; /双向栈类型 Status Init_Stack(BDStacktype &tws,int m)/初始化一个大小为m的双向栈tws tws.base0=(Elemtype*)malloc(sizeof(Elemtype); tws.base1=tws.base0+m; tws0=tws.base0; tws1=tws.base1; return OK;/Init_Stack Status push(BDStacktype &tws,int i,Elemtype x)/x入栈,i=0表示低端栈,i=1表示高端栈 if(tws0>tws1) return OVERFLOW; /留意此时的栈满条件 if(i=0) *tws0+=x; else if(i=1) *tws1-=x; else return ERROR; return OK;/push Status pop(BDStacktype &tws,int i,Elemtype &x)/x出栈,i=0表示低端栈,i=1表示高端栈 if(i=0) if(tws0=tws.base0) return OVERFLOW; x=*-tws0; else if(i=1) if(tws1=tws.base1) return OVERFLOW; x=*+tws1; else return ERROR; return OK;/pop 3.16 void Train_arrange(char *train)/这里用字符串train表示火车,'H'表示硬席,'S'表示软席 p=train;q=train; InitStack(s); while(*p) if(*p='H') push(s,*p); /把'H'存入栈中 else *(q+)=*p; /把'S'调到前部 p+; while(!StackEmpty(s) pop(s,c); *(q+)=c; /把'H'接在后部/Train_arrange 3.17 int IsReverse()/推断输入的字符串中'&'前和'&'后局部是否为逆串,是则返回1,否则返回0 InitStack(s); while(e=getchar()!='&') push(s,e); while(e=getchar()!='') if(StackEmpty(s) return 0; pop(s,c); if(e!=c) return 0; if(!StackEmpty(s) return 0; return 1;/IsReverse 3.18 Status Bracket_Test(char *str)/判别表达式中小括号是否匹配 count=0; for(p=str;*p;p+) if(*p='(') count+; else if(*p=')') count-; if (count<0) return ERROR; if(count) return ERROR; /留意括号不匹配的两种状况 return OK;/Bracket_Test 3.19 Status AllBrackets_Test(char *str)/判别表达式中三种括号是否匹配 InitStack(s); for(p=str;*p;p+) if(*p='('|*p=''|*p='') push(s,*p); else if(*p=')'|*p=''|*p='') if(StackEmpty(s) return ERROR; pop(s,c); if(*p=')'&&c!='(') return ERROR; if(*p=''&&c!='') return ERROR; if(*p=''&&c!='') return ERROR; /必需与当前栈顶括号匹配 /for if(!StackEmpty(s) return ERROR; return OK;/AllBrackets_Test 3.20 typedef struct . int x; int y; coordinate;void Repaint_Color(int gmn,int i,int j,int color)/把点(i,j)相邻区域的颜色置换为color old=gij; InitQueue(Q); EnQueue(Q,I,j); while(!QueueEmpty(Q) DeQueue(Q,a); x=a.x;y=a.y; if(x>1) if(gx-1y=old) gx-1y=color; EnQueue(Q,x-1,y); /修改左邻点的颜色 if(y>1) if(gxy-1=old) gxy-1=color; EnQueue(Q,x,y-1); /修改上邻点的颜色 if(x<m) if(gx+1y=old) gx+1y=color; EnQueue(Q,x+1,y); /修改右邻点的颜色 if(y<n) if(gxy+1=old) gxy+1=color; EnQueue(Q,x,y+1); /修改下邻点的颜色 /while/Repaint_Color分析:本算法承受了类似于图的广度优先遍历的思想,用两个队列保存相邻同色点的横坐标和纵坐标.递归形式的算法该怎么写呢 3.21 void NiBoLan(char *str,char *new)/把中缀表达式str转换成逆波兰式new p=str;q=new; /为便利起见,设str的两端都加上了优先级最低的特别符号 InitStack(s); /s为运算符栈 while(*p) if(*p是字母) *q+=*p; /干脆输出 else c=gettop(s); if(*p优先级比c高) push(s,*p); else while(gettop(s)优先级不比*p低) pop(s,c);*(q+)=c; /while push(s,*p); /运算符在栈内遵循越往栈顶优先级越高的原则 /else /else p+; /while/NiBoLan /参见编译原理教材 3.22 int GetValue_NiBoLan(char *str)/对逆波兰式求值 p=str;InitStack(s); /s为操作数栈 while(*p) if(*p是数) push(s,*p); else pop(s,a);pop(s,b); r=compute(b,*p,a); /假设compute为执行双目运算的过程 push(s,r); /else p+; /while pop(s,r);return r;/GetValue_NiBoLan 3.23 Status NiBoLan_to_BoLan(char *str,stringtype &new)/把逆波兰表达式str转换为波兰式new p=str;Initstack(s); /s的元素为stringtype类型 while(*p) if(*p为字母) push(s,*p); else if(StackEmpty(s) return ERROR; pop(s,a); if(StackEmpty(s) return ERROR; pop(s,b); c=link(link(*p,b),a); push(s,c); /else p+; /while pop(s,new); if(!StackEmpty(s) return ERROR; return OK;/NiBoLan_to_BoLan分析:根本思想见书后注释.本题中暂不考虑串的具体操作的实现,而将其看作一种抽象数据类型stringtype,对其可以进展连接操作:c=link(a,b). 3.24 Status g(int m,int n,int &s)/求递归函数g的值s if(m=0&&n>=0) s=0; else if(m>0&&n>=0) s=n+g(m-1,2*n); else return ERROR; return OK;/g 3.25 Status F_recursive(int n,int &s)/递归算法 if(n<0) return ERROR; if(n=0) s=n+1; else F_recurve(n/2,r); s=n*r; return OK;/F_recursive Status F_nonrecursive(int n,int s)/非递归算法 if(n<0) return ERROR; if(n=0) s=n+1; else InitStack(s); /s的元素类型为struct int a;int b; while(n!=0) a=n;b=n/2; push(s,a,b); n=b; /while s=1; while(!StackEmpty(s) pop(s,t); s*=t.a; /while return OK;/F_nonrecursive 3.26 float Sqrt_recursive(float A,float p,float e)/求平方根的递归算法 if(abs(p2-A)<=e) return p; else return sqrt_recurve(A,(p+A/p)/2,e);/Sqrt_recurve float Sqrt_nonrecursive(float A,float p,float e)/求平方根的非递归算法 while(abs(p2-A)>=e) p=(p+A/p)/2; return p;/Sqrt_nonrecursive 3.27 这一题的全部算法以及栈的变更过程请参见数据构造(pascal版),作者不再具体写出. 3.28 void InitCiQueue(CiQueue &Q)/初始化循环链表表示的队列Q Q=(CiLNode*)malloc(sizeof(CiLNode); Q->next=Q;/InitCiQueue void EnCiQueue(CiQueue &Q,int x)/把元素x插入循环链表表示的队列Q,Q指向队尾元素,Q->next指向头结点,Q->next->next指向队头元素 p=(CiLNode*)malloc(sizeof(CiLNode); p->data=x; p->next=Q->next; /干脆把p加在Q的后面 Q->next=p; Q=p; /修改尾指针Status DeCiQueue(CiQueue &Q,int x)/从循环链表表示的队列Q头部删除元素x if(Q=Q->next) return INFEASIBLE; /队列已空 p=Q->next->next; x=p->data; Q->next->next=p->next; free(p); return OK;/DeCiQueue 3.29 Status EnCyQueue(CyQueue &Q,int x)/带tag域的循环队列入队算法 if(Q.front=Q.rear&&Q.tag=1) /tag域的值为0表示"空",1表示"满" return OVERFLOW; Q.baseQ.rear=x; Q.rear=(Q.rear+1)%MAXSIZE; if(Q.front=Q.rear) Q.tag=1; /队列满/EnCyQueue Status DeCyQueue(CyQueue &Q,int &x)/带tag域的循环队列出队算法 if(Q.front=Q.rear&&Q.tag=0) return INFEASIBLE; Q.front=(Q.front+1)%MAXSIZE; x=Q.baseQ.front; if(Q.front=Q.rear) Q.tag=1; /队列空 return OK;/DeCyQueue分析:当循环队列容量较小而队列中每个元素占的空间较多时,此种表示方法可以节约较多的存储空间,较有价值. 3.30 Status EnCyQueue(CyQueue &Q,int x)/带length域的循环队列入队算法 if(Q.length=MAXSIZE) return OVERFLOW; Q.rear=(Q.rear+1)%MAXSIZE; Q.baseQ.rear=x; Q.length+; return OK;/EnCyQueue Status DeCyQueue(CyQueue &Q,int &x)/带length域的循环队列出队算法 if(Q.length=0) return INFEASIBLE; head=(Q.rear-Q.length+1)%MAXSIZE; /详见书后注释 x=Q.basehead; Q.length-;/DeCyQueue 3.31 int Palindrome_Test()/判别输入的字符串是否回文序列,是则返回1,否则返回0 InitStack(S);InitQueue(Q); while(c=getchar()!='') Push(S,c);EnQueue(Q,c); /同时运用栈和队列两种构造 while(!StackEmpty(S) Pop(S,a);DeQueue(Q,b); if(a!=b) return ERROR; return OK;/Palindrome_Test 3.32 void GetFib_CyQueue(int k,int n)/求k阶斐波那契序列的前n+1项 InitCyQueue(Q); /其MAXSIZE设置为k for(i=0;i<k-1;i+) Q.basei=0; Q.basek-1=1; /给前k项赋初值 for(i=0;i<k;i+) printf("%d",Q.basei); for(i=k;i<=n;i+) m=i%k;sum=0; for(j=0;j<k;j+) sum+=Q.base(m+j)%k; Q.basem=sum; /求第i项的值存入队列中并取代已无用的第一项 printf("%d",sum);/GetFib_CyQueue 3.33 Status EnDQueue(DQueue &Q,int x)/输出受限的双端队列的入队操作 if(Q.rear+1)%MAXSIZE=Q.front) return OVERFLOW; /队列满 avr=(Q.baseQ.rear-1+Q.baseQ.front)/2; if(x>=avr) /依据x的值确定插入在队头还是队尾 Q.baseQ.rear=x; Q.rear=(Q.rear+1)%MAXSIZE; /插入在队尾 else Q.front=(Q.front-1)%MAXSIZE; Q.baseQ.front=x; /插入在队头 return OK;/EnDQueue Status DeDQueue(DQueue &Q,int &x)/输出受限的双端队列的出队操作 if(Q.front=Q.rear) return INFEASIBLE; /队列空 x=Q.baseQ.front; Q.front=(Q.front+1)%MAXSIZE; return OK;/DeDQueue 3.34 void Train_Rearrange(char *train)/这里用字符串train表示火车,'P'表示硬座,'H'表示硬卧,'S'表示软卧,最终按PSH的依次排列 r=train; InitDQueue(Q); while(*r) if(*r='P') printf("E"); printf("D"); /事实上等于不入队列,干脆输出P车厢 else if(*r='S') printf("E"); EnDQueue(Q,*r,0); /0表示把S车厢从头端入队列 else printf("A"); EnDQueue(Q,*r,1); /1表示把H车厢从尾端入队列 /while while(!DQueueEmpty(Q) printf("D"); DeDQueue(Q); /while /从头端出队列的车厢必定是先S后H的依次 /Train_Rearrange第 17 页