《数据结构》课程教学资源：答案_第三章 栈与队列

第三章栈与队列 3.15 typedef struct( Ele 2] Elemtype *top[2]: BDStacktype;/双向栈类型 Status Init Stack (BDStacktype&tws,intm)∥/初始化一个大小为m的双向栈tws tws base[0](Elemtype*)malloc(sizeof(Elemtype) tws base[l=tws base[0]+m tws top[O]tws base[o] tws. top[lF=tws base[1] return OK i //nit Stack Status push( BDStacktype& wS, int i, Elemtype x入栈=0表示低端栈=1表示高 端栈 if(tws. top[ oPts. top[ D return OVERFLOW,∥/注意此时的栈满条件 if(i-0)*tws. top[0J++= Ise if(F=1)*tws. top[1]-- else return erROR: turn oK i//push Status pop( BDStacktype& tws, int 1, Elemtype&x/x出栈=0表示低端栈r=1表示 高端栈 if(i==0) if(tws top[O==tws base[od return OVERFLOw =*--tws top[O]: else if(F==1) f(tws top[1ltws base[ld return OVERFLOw x=*++tws. top[1]; else return erROR. eturn oK g//pop

第三章 栈与队列 3.15 typedef struct{ Elemtype *base[2]; Elemtype *top[2]; }BDStacktype; //双向栈类型 Status Init_Stack(BDStacktype &tws,int m)//初始化一个大小为 m 的双向栈 tws { tws.base[0]=(Elemtype*)malloc(sizeof(Elemtype)); tws.base[1]=tws.base[0]+m; tws.top[0]=tws.base[0]; tws.top[1]=tws.base[1]; return OK; }//Init_Stack Status push(BDStacktype &tws,int i,Elemtype x)//x 入栈,i=0 表示低端栈,i=1 表示高 端栈 { if(tws.top[0]>tws.top[1]) return OVERFLOW; //注意此时的栈满条件 if(i==0) *tws.top[0]++=x; else if(i==1) *tws.top[1]--=x; else return ERROR; return OK; }//push Status pop(BDStacktype &tws,int i,Elemtype &x)//x 出栈,i=0 表示低端栈,i=1 表示 高端栈 { if(i==0) { if(tws.top[0]==tws.base[0]) return OVERFLOW; x=*--tws.top[0]; } else if(i==1) { if(tws.top[1]==tws.base[1]) return OVERFLOW; x=*++tws.top[1]; } else return ERROR; return OK; }//pop

3.16 void Train arrange(char* Train这里用字符串tain表示火车,H表示硬席S表示 软席 p= train, q≡tran Init Stack(s) if(*p=H)push(s,*p),把H存入栈中 else*(q++)=*p;/把S'调到前部 p+ while(!Stack Empty(s)) pop(s, c) *(q+)=c;∥把H接在后部 i//Train arrange 3.17 int IsReverseo∥判断输入的字符串中&前和&后部分是否为逆串,是则返回1,否 则返回0 Init Stack(s) while((e=getchar)I=&') ife=@) retur0∥不允许在&之前出现@ push(s, e); while( (e=getchar)l=@) if(Stack Empty(s)return 0 pop(s, c if(el=c)return 0 if(STack Empty(s))return 0; un 3//rEverse 3.18 Status Bracket Test(char*str判别表达式中小括号是否匹配

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())!='&') { if(e==’@’) return 0;//不允许在’&’之前出现’@’ 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)//判别表达式中小括号是否匹配 {

counto for(p=str; *p p++) f(p=0 count++ else if(p=))count if(count <0)return ERROR if(count) return error;∥注意括号不匹配的两种情况 return OK i//Bracket Test 3.19 Status allBrackets Test(char*strm判别表达式中三种括号是否匹配 Init Stack(s) for(p=str, *p: p++) if(p=cp=tl"p==t push(s, *p) else if((*p=)‖*p=‖*p=}") if(Stack Empty(s) return ERROR pop(s, c ); if(p==)&&cl='C)return ERROR if( p==l&&cl=D return ERRO if(p&&c!=() return Error;∥必须与当前栈顶括号匹配 if(I Empty(s)) return ERROR return OK i//AllBrackets Test 3.20 typedef struct i Int coord inate void Repaint Color(int g[mJn] int i, int j, int color )/把点(ij)相邻区域的颜色置换为 color old=gp[l InitQueue(Q)

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 g[m][n],int i,int j,int color)//把点(i,j)相邻区域的颜色置换为 color { old=g[i][j]; InitQueue(Q);

EnQueue(Q, ( j)); while(!Queue Empty(Q)) De Queue(Q, a); x-a. x,y-a. y if(glx-1]y==old) glx-1Ly=color EnQueue(Q,{x-1,y}),∥修改左邻点的颜色 if(glx]y-1==old) glxly-1=color EnQueue(Q{xy-1},/修改上邻点的颜色 if(gx+1]y]==old) glx+lllylcolor; EnQueue(Q,{x+1,y}),∥修改右邻点的颜色 if(glx]y+1=old) g[x]y+1=color; EnQueue(Q,{xy+1},∥修改下邻点的颜色 i//while i//Repaint Color 分析:本算法采用了类似于图的广度优先遍历的思想用两个队列保存相邻同色点 的横坐标和纵坐标递归形式的算法该怎么写呢? 3.21 void nibolan(char* str char*newy/把中缀表达式str转换成逆波兰式new p=strq=new,∥为方便起见设str的两端都加上了优先级最低的特殊符号 InitStack(s,/为运算符栈 while if(*p是字母)*q+=*p,∥直接输出

EnQueue(Q,{I,j}); while(!QueueEmpty(Q)) { DeQueue(Q,a); x=a.x;y=a.y; if(x>1) if(g[x-1][y]==old) { g[x-1][y]=color; EnQueue(Q,{x-1,y}); //修改左邻点的颜色 } if(y>1) if(g[x][y-1]==old) { g[x][y-1]=color; EnQueue(Q,{x,y-1}); //修改上邻点的颜色 } if(x<m) if(g[x+1][y]==old) { g[x+1][y]=color; EnQueue(Q,{x+1,y}); //修改右邻点的颜色 } if(y<n) if(g[x][y+1]==old) { g[x][y+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)∥运算符在栈内遵循越往栈顶优先级越高的原则 allele p++; i//while NiBoLan/参见编译原理教材 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); p+ i//while pop(s, r), return r; i//Get Value NiBoLan 3.23 Status nibolan to bolan(char* str, stringtype&newy/把逆波兰表达式str转换为 波兰式new p= str Initstack(s),/s的元素为 stringtype类型 while(°p) if(*p为字母)push(s,*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(Stack Empty(s))return ERROR pop(s, a) if(Stack Empty())return ERROR pop(s, b) c=link(link(*p, b ), a) bush(s, c); i/else p+ i//while pop(s, new) if(!Stack Empty(s))return ERROR; eturn OK //NiBoLan to Bolan 分析:基本思想见书后注释本题中暂不考虑串的具体操作的实现而将其看作 种抽象数据类型 stringtype,对其可以进行连接操作c=link(ab) 3.24 Status g(intm,ntn,int&sy求递归函数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 eturn OK }/g 3.25 Status f recursive(intn,int&s∥/递归算法 if(n<0)return ERROR if(n==0)s=n+1; F recurve(n/2, r) s-n"r return OK i//F recursive Status F nonrecursive(int n,ints非递归算法 if(n<0)retun ERROR if(n==0)s=n+1;

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

Init Stack(s),/s的元素类型为 struct{inta;intb;} hile(n=0) an bush(s, (a,b)); i/while while(stack Empty(s)) pop(s, t) s*气ta; i//while return OK 3//F nonrecursive 3.26 float Sqrt recursive(float A, float p, float e求平方根的递归算法 if(abs(p 2-A)=e)return else return sqrt recurve(A, (p+ A/p)2, e) i//Sqrt recurve float Sqrt nonrecursive(float A, float p, float ey/求平方根的非递归算法 while(abs(p 2-Ap=e) (p+A/p)2 i/ Sqrt nonrecursive 这一题的所有算法以及栈的变化过程请参见《数据结构 (pascal版)》,作者不再详 细写出 void Init CiQueue( CiQueue&Q初始化循环链表表示的队列Q Q=(CiLNode *)malloc(sizeof(CILNode)) Q i//nitCiQueue

{ 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(p^2-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插入循环链表表示的队列QQ指向 队尾元素,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 De CiQueue( CiQueue&Q, int x)从循环链表表示的队列Q头部删除元素x if(=Q>next) return INFEASIBLE/队列已空 P=Q->next->next xp->data Q->next->next=p->next free(p); eturn OK i//DeCiQueue 3.29 Status EnCyQueue( qUeue&Q,intx∥/带tag域的循环队列入队算法 if(Q. front= Qrear&&Qtag=1)/tag域的值为0表示"空",l表示"满 return OVERFLOW Q rear(Q rear+ 1)%MAXSIZE if(Q. front= EQ rear))Qtag=1l;/队列满 i//En Cy Queue Status DeCy Queue( CyQueue&Qnt&x)带tag域的循环队列出队算法 if(Q front==Q rear&&Q tag=0)return INFEASIBLE; Q front=(Q front+1)%MAXSIZE xQ. base[Q front]; if(Q. front= EQ rear))Qtag=1;/队列空 return OK //DeCy Queue 分析:当循环队列容量较小而队列中每个元素占的空间较多时,此种表示方法可以 节约较多的存储空间,较有价值. 3.30

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.base[Q.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.base[Q.front]; if(Q.front==Q.rear) Q.tag=1; //队列空 return OK; }//DeCyQueue 分析:当循环队列容量较小而队列中每个元素占的空间较多时,此种表示方法可以 节约较多的存储空间,较有价值. 3.30

Status EnCy Queue( qUeue&Q,intx∥/带 length域的循环队列入队算法 if(Q length==MAXSIZE)return OVERFLOW Q rear(Q rear+ 1)%MAXSIZE; Q base[Q rear]= O length return OK 3//EnCyQueue Status De CyQueue( CyQueue&Q,nt&xy带 length域的循环队列出队算法 if(Q length==0) return INFEASIBLE head=( Q. rear-Q length+1)% MAXSIZE,∥详见书后注释 xQ. base head] Qlength- ecyQueue 3.31 int Palindrome TestO判别输入的字符串是否回文序列是则返回1,否则返回0 InitStack(s), InitQueue(Q) while((c=getchar)=(@) Push(S) EnQueue(Q,c),∥同时使用栈和队列两种结构 while(stack Empty (s)) Pop(S, a), DeQueue(Q, b); if(al=b) return ERROR. eturn OK. i//Palindrome Test void Get Fib CyQueue( int k, int n))/求k阶斐波那契序列的前n+1项 Init CyQueue(Q,∥其 MAXSIZE设置为k for(F0; i<k-1; i++)Qbase]=0 Q base[k-l=1;给前k项赋初值 for(F0; i<k; i++)printf("%d",Q base; for(ik; K<=n; i++) m=i%k sum=0

Status EnCyQueue(CyQueue &Q,int x)//带 length 域的循环队列入队算法 { if(Q.length==MAXSIZE) return OVERFLOW; Q.rear=(Q.rear+1)%MAXSIZE; Q.base[Q.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.base[head]; 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.base[i]=0; Q.base[k-1]=1; //给前 k 项赋初值 for(i=0;i<k;i++) printf("%d",Q.base[i]); for(i=k;i<=n;i++) { m=i%k;sum=0;

for(=0; j=avr)∥根据x的值决定插入在队头还是队尾 Q base[Q rear]=x Q rear(Q rear+1 )%MAXSIZE }/插入在队尾 Q front=(Q front-1)%MAXSIZE, Q base[Q front }/插入在队头 return OK i//EnQUeue Status DeQUeue QUeue&Q,nt&xy∥/输出受限的双端队列的出队操作 if(Q front= Q rear) return INFEASIble∥队列空 xQ. base[Q front]; Q front=(Q front+1)%MAXSIZE eturn OK 3//DeQUeue 3.34 void Train Rearrange(char+rain)/这里用字符串 train表示火车P表示硬座,H表 示硬卧S表示软卧,最终按PSH的顺序排列 rtrain Init QUeue(Q) hile(r) printf(e");

for(j=0;j=avr) //根据 x 的值决定插入在队头还是队尾 { Q.base[Q.rear]=x; Q.rear=(Q.rear+1)%MAXSIZE; } //插入在队尾 else { Q.front=(Q.front-1)%MAXSIZE; Q.base[Q.front]=x; } //插入在队头 return OK; }//EnDQueue Status DeDQueue(DQueue &Q,int &x)//输出受限的双端队列的出队操作 { if(Q.front==Q.rear) return INFEASIBLE; //队列空 x=Q.base[Q.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");