关注公众号凡花花的小窝，收获更多的考研计算机专业编程相关的资料 3.20 假设以二维数组g(1…m, 1…n)表示一个图像区域，g[i,j]表示该区域中点(i,j)所具颜色，其值为从0到k的整数。编写算法置换点(i0,j0)所在区域的颜色。约定和(i0,j0)同色的上、下、左、右的邻接点为同色区域的点。 解： #include <iostream.h> #include <stdlib.h>
typedef struct{ int x; int y; }PosType; typedef struct{ int Color; int Visited; PosType seat; }ElemType;
#include “d:\VC99\Stack.h”
#define M 8 #define N 8
ElemType g[M][N];
void CreateGDS(ElemType g[M][N]); void ShowGraphArray(ElemType g[M][N]); void RegionFilling(ElemType g[M][N],PosType CurPos,int NewColor);
int main() { CreateGDS(g); ShowGraphArray(g);
PosType StartPos; StartPos.x=5; StartPos.y=5; int FillColor=6; RegionFilling(g,StartPos,FillColor); cout<<endl; ShowGraphArray(g); return 0;}
void RegionFilling(ElemType g[M][N],PosType CurPos,int FillColor) { Stack s; InitStack(s); ElemType e; int OldColor=g[CurPos.x][CurPos.y].Color;
Push(s,g[CurPos.x][CurPos.y]); while(!StackEmpty(s)){ Pop(s,e); CurPos=e.seat; g[CurPos.x][CurPos.y].Color=FillColor; g[CurPos.x][CurPos.y].Visited=1; if(CurPos.x<M && !g[CurPos.x+1][CurPos.y].Visited && g[CurPos.x+1][CurPos.y].Color==OldColor ) Push(s,g[CurPos.x+1][CurPos.y]); if(CurPos.x>0 && !g[CurPos.x-1][CurPos.y].Visited && g[CurPos.x-1][CurPos.y].Color==OldColor ) Push(s,g[CurPos.x-1][CurPos.y]); if(CurPos.y<N && !g[CurPos.x][CurPos.y+1].Visited && g[CurPos.x][CurPos.y+1].Color==OldColor ) Push(s,g[CurPos.x][CurPos.y+1]); if(CurPos.y>0 && !g[CurPos.x][CurPos.y-1].Visited && g[CurPos.x][CurPos.y-1].Color==OldColor ) Push(s,g[CurPos.x][CurPos.y-1]); }}
void CreateGDS(ElemType g[M][N]) { int i,j; for(i=0;i<M;i++) for(j=0;j<N;j++){ g[i][j].seat.x=i; g[i][j].seat.y=j; g[i][j].Visited=0; g[i][j].Color=0; } for(i=2;i<5;i++) for(j=2;j<4;j++) g[i][j].Color=3; for(i=5;i<M-1;i++) for(j=3;j<6;j++) g[i][j].Color=3; }
void ShowGraphArray(ElemType g[M][N]) { int i,j; for(i=0;i<M;i++){ for(j=0;j<N;j++) cout<<g[i][j].Color; cout<<endl; } } 3.21 假设表达式有单字母变量和双目四则运算符构成。试写一个算法，将一个通常书写形式且书写正确的表达式转换为逆波兰表达式。 解： // 输入的表达式串必须为#…#格式 void InversePolandExpression(char Buffer[]) { Stack s; InitStack(s); int i=0,j=0; ElemType e;
Push(s,Buffer[i]); i++; while(Buffer[i]!='#'){ if(!IsOperator(Buffer[i])){ // 是操作数 Buffer[j]=Buffer[i]; i++; j++; } else{ // 是操作符 GetTop(s,e); if(Prior(e,Buffer[i])){// 当栈顶优先权高于当前序列时，退栈 Pop(s,e); Buffer[j]=e; j++; } else{ Push(s,Buffer[i]); i++; } } } while(!StackEmpty(s)){ Pop(s,e); Buffer[j]=e; j++; }}
Status IsOpertor(char c) { char p="#±/"; while(*p){ if(*p==c) return TRUE; p++; } return FALSE; }
Status Prior(char c1,char c2) { char ch[]="#±*/"; int i=0,j=0; while(ch[i] && ch[i]!=c1) i++; if(i2) i–; // 加和减可认为是同级别的运算符 if(i4) i–; // 乘和除可认为是同级别的运算符 while(ch[j] && ch[j]!=c2) j++; if(j2) j–; if(j4) j–; if(i>=j) return TRUE; else return FALSE; } 3.22 如题3.21的假设条件，试写一个算法，对以逆波兰式表示的表达式求值。 解： char CalVal_InverPoland(char Buffer[]) { Stack Opnd; InitStack(Opnd); int i=0; char c; ElemType e1,e2;
while(Buffer[i]!='#'){ if(!IsOperator(Buffer[i])){ Push(Opnd,Buffer[i]); } else{ Pop(Opnd,e2); Pop(Opnd,e1); c=Cal(e1,Buffer[i],e2); Push(Opnd,c); } i++; } return c;}
char Cal(char c1,char op,char c2) { int x,x1,x2; char ch[10]; ch[0]=c1; ch[1]=’\0’; x1=atoi(ch);
ch[0]=c2; ch[1]='\0'; x2=atoi(ch); switch(op){ case '+': x=x1+x2; break; case '-': x=x1-x2; break; case '*': x=x1*x2; break; case '/': x=x1/x2; break; default: break; } itoa(x,ch,10); return ch[0];} 3.23 如题3.21的假设条件，试写一个算法，判断给定的非空后缀表达式是否为正确的逆波兰表达式，如果是，则将它转化为波兰式。 解： #include <iostream.h> #include <stdlib.h> #include <string.h> #include “d:\VC99\DSConstant.h”
typedef char ARRAY[30]; typedef ARRAY ElemType; typedef struct NodeType{ ElemType data; NodeType *next; }NodeType,*LinkType; typedef struct{ LinkType top; int size; }Stack;
void InitStack(Stack &s); Status Push(Stack &s,ElemType e); Status Pop(Stack &s,ElemType e); Status IsOperator(char c); Status StackEmpty(Stack s);
Status InvToFroPoland(char a[]);
int main() { char a[30]; cout<<“请输入逆波兰算术表达式字符序列：”; cin>>a; if(InvToFroPoland(a)) cout<<a<<endl; else cout<<“输入逆波兰算术表达式字符序列错误!”; return 0; }
Status InvToFroPoland(char a[]) { Stack s; InitStack(s); int i=0; ElemType ch; ElemType c1; ElemType c2;
while(a[i]!='#'){ if(!IsOperator(a[i])){ if(a[i]>='0' && a[i]<='9'){ ch[0]=a[i]; ch[1]='\0'; Push(s,ch); } else return FALSE; } else{ ch[0]=a[i]; ch[1]='\0'; if(!StackEmpty(s)){ Pop(s,c2); if(!StackEmpty(s)){ Pop(s,c1); strcat(ch,c1); strcat(ch,c2); Push(s,ch); } else return FALSE; } else return FALSE; } i++; } if(!StackEmpty(s)){ Pop(s,c1); strcpy(a,c1); } else return FALSE; if(!StackEmpty(s)) return FALSE; return OK;} void InitStack(Stack &s) { s.top=NULL; s.size=0; }
Status Push(Stack &s,ElemType e) { LinkType p; p=new NodeType; if(!p) exit(OVERFLOW); p->next=s.top; s.top=p; strcpy(p->data,e); s.size++; return OK; }
Status Pop(Stack &s,ElemType e) { LinkType p; if(s.top){ strcpy(e,s.top->data); p=s.top; s.top=p->next; delete p; s.size–; } return OK; }
Status StackEmpty(Stack s) { if(s.size==0) return TRUE; else return FALSE; }
Status IsOperator(char c) { char p="#±/"; while(*p){ if(*p==c) return TRUE; p++; } return FALSE; } 3.24 试编写如下定义的递归函数的递归算法，并根据算法画出求g(5,2)时栈的变化过程。
解： int g(int m,int n); int main() { int m,n; cout<<“请输入m和n的值：”; cin>>m>>n; if(n>=0) cout<<g(m,n)<<endl; else cout<<“No Solution!”; return 0; } int g(int m,int n) { if(m>0) return(g(m-1,2*n)+n); else return 0; } 假设主函数的返回地址为0，递归函数3条语句的地址分别为1、2、3。 3 0 64 3 1 32 3 2 16 3 3 8 3 4 4 0 5 2 3.25 试写出求递归函数F(n)的递归算法，并消除递归：
解： #include <iostream.h> #define N 20 int main() { int i; int a[N]; int n; cout<<“请输入n:”; cin>>n; for(i=0;i<n+1;i++){ if(i<1) a[i]=1; else a[i]=i*a[i/2]; } cout<<a[n]<<endl; return 0; } 3.26 求解平方根的迭代函数定义如下：
其中，p是A的近似平方根，e是结果允许误差。试写出相应的递归算法，并消除递归。 解： #include <iostream.h> double Sqrt(double A,double p,double e); int main() { double A,p,e; cout<<“请输入A p e:”; cin>>A>>p>>e; cout<<Sqrt(A,p,e)<<endl; return 0; } double Sqrt(double A,double p,double e) { if((pp-A)>-e && (pp-A)<e) return p; else return Sqrt(A,(p+A/p)/2,e); } 3.27 已知Ackerman函数的定义如下：
(1) 写出递归算法； (2) 写出非递归算法； (3) 根据非递归算法，画出求akm(2,1)时栈的变化过程。解： unsigned int akm(unsigned int m,unsigned int n) { unsigned int g; if(m0) return n+1; else if(n0) return akm(m-1,1); else{ g=akm(m,n-1); return akm(m-1,g); } } 非递归算法： int akm1(int m,int n) { Stack s; InitStack(s); ElemType e,e1,d; e.mval=m; e.nval=n; Push(s,e); do{ while(e.mval){ while(e.nval){ e.nval–; Push(s,e); } e.mval–; e.nval=1; } if(StackLength(s)>1){ e1.nval=e.nval; Pop(s,e); e.mval–; e.nval=e1.nval+1; } }while(StackLength(s)!=1||e.mval!=0); return e.nval+1; }
0,akm(2,1) 0 2 1 g=akm(2,0) 1,akm(2,0) 6 2 0 akm=akm(m-1,1)=akm(1,1) 2,akm(1,1) 4 1 1 g=akm(m,n-1)=akm(1,0) 3,akm(1,0) 6 1 0 akm=akm(m-1,1)=akm(0,1) 4,akm(0,1) 4 0 1 akm=n+1=2 退栈
0,akm(2,1) 0 2 1 g=akm(2,0) 1,akm(2,0) 6 2 0 akm=akm(m-1,1)=akm(1,1) 2,akm(1,1) 4 1 1 g=akm(m,n-1)=akm(1,0) 3,akm(1,0) 6 1 0 akm=akm(m-1,1)=akm(0,1)=2 退栈
0,akm(2,1) 0 2 1 g=akm(2,0) 1,akm(2,0) 6 2 0 akm=akm(m-1,1)=akm(1,1) 2,akm(1,1) 4 1 1 g=akm(m,n-1)=akm(1,0)=2; akm=akm(m-1,g)=akm(0,2); 3,akm(0,2) 7 0 2 akm=n+1=3 退栈
0,akm(2,1) 0 2 1 g=akm(2,0) 1,akm(2,0) 6 2 0 akm=akm(m-1,1)=akm(1,1) 2,akm(1,1) 4 1 1 g=akm(m,n-1)=akm(1,0)=2; akm=akm(m-1,g)=akm(0,2)=3; 退栈
0,akm(2,1) 0 2 1 g=akm(2,0) 1,akm(2,0) 6 2 0 akm=akm(m-1,1)=akm(1,1)=3 退栈
0,akm(2,1) 0 2 1 g=akm(2,0)=3; akm=akm(1,3) 1,akm(1,3) 6 1 3 g=akm(1,2); akm(m-1,g) 2,akm(1,2) 6 1 2 g=akm(1,1); akm(m-1,g) 3,akm(1,1) 6 1 1 g=akm(1,0); akm(m-1,g) 4,akm(1,0) 6 1 0 akm=akm(0,1) 5,akm(0,1) 4 0 1 akm(0,1)=2退栈
0,akm(2,1) 0 2 1 g=akm(2,0)=3; akm=akm(1,3) 1,akm(1,3) 6 1 3 g=akm(1,2); akm(m-1,g) 2,akm(1,2) 6 1 2 g=akm(1,1); akm(m-1,g) 3,akm(1,1) 6 1 1 g=akm(1,0); akm(m-1,g) 4,akm(1,0) 6 1 0 akm=akm(0,1)=2退栈
0,akm(2,1) 0 2 1 g=akm(2,0)=3; akm=akm(1,3) 1,akm(1,3) 6 1 3 g=akm(1,2); akm(m-1,g) 2,akm(1,2) 6 1 2 g=akm(1,1); akm(m-1,g) 3,akm(1,1) 6 1 1 g=akm(1,0)=2; akm(m-1,g)=akm(0,2) 4,akm(0,2) 7 0 2 akm=n+1=3 退栈
0,akm(2,1) 0 2 1 g=akm(2,0)=3; akm=akm(1,3) 1,akm(1,3) 6 1 3 g=akm(1,2); akm(m-1,g) 2,akm(1,2) 6 1 2 g=akm(1,1); akm(m-1,g) 3,akm(1,1) 6 1 1 g=akm(1,0)=2; akm(m-1,g)=akm(0,2)=3退栈
0,akm(2,1) 0 2 1 g=akm(2,0)=3; akm=akm(1,3) 1,akm(1,3) 6 1 3 g=akm(1,2); akm(m-1,g) 2,akm(1,2) 6 1 2 g=akm(1,1)=3; akm(m-1,g)=akm(0,3) 3,akm(0,3) 7 0 3 akm=n+1=4 退栈
0,akm(2,1) 0 2 1 g=akm(2,0)=3; akm=akm(1,3) 1,akm(1,3) 6 1 3 g=akm(1,2); akm(m-1,g) 2,akm(1,2) 6 1 2 g=akm(1,1)=3; akm(m-1,g)=akm(0,3)=4 退栈
0,akm(2,1) 0 2 1 g=akm(2,0)=3; akm=akm(1,3) 1,akm(1,3) 6 1 3 g=akm(1,2)=4; akm(m-1,g)=akm(0,4) 2,akm(0,4) 7 0 4 akm=n+1=5 退栈
0,akm(2,1) 0 2 1 g=akm(2,0)=3; akm=akm(1,3) 1,akm(1,3) 6 1 3 g=akm(1,2)=4; akm(m-1,g)=akm(0,4)=5退栈
0,akm(2,1) 0 2 1 g=akm(2,0)=3; akm=akm(1,3)=5退栈
akm(2,1)=5; 3.28 假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），试编写相应的队列初始化、入队列何处队列的算法。 解： typedef int ElemType; typedef struct NodeType{ ElemType data; NodeType *next; }QNode,*QPtr; typedef struct{ QPtr rear; int size; }Queue; Status InitQueue(Queue& q) { q.rear=NULL; q.size=0; return OK; } Status EnQueue(Queue& q,ElemType e) { QPtr p; p=new QNode; if(!p) return FALSE; p->data=e; if(!q.rear){ q.rear=p; p->next=q.rear; } else{ p->next=q.rear->next; q.rear->next=p; q.rear=p; } q.size++; return OK; } Status DeQueue(Queue& q,ElemType& e) { QPtr p; if(q.size0)return FALSE; if(q.size1){ p=q.rear; e=p->data; q.rear=NULL; delete p; } else{ p=q.rear->next; e=p->data; q.rear->next=p->next; delete p; } q.size–; return OK; }
