嚴蔚敏《數據結構(c語言版)習題集》算法設計題第三章參考答案

　　第三章 棧與隊列

　　

　　typedef struct{

　　Elemtype *base[];

　　Elemtype *top[];

　　}BDStacktype; //雙向棧類型

　　Status Init_Stack(BDStacktype &twsint m)//初始化一個大小為m的雙向棧tws

　　{

　　twsbase[]=(Elemtype*)malloc(sizeof(Elemtype));

　　twsbase[]=twsbase[]+m;

　　twstop[]=twsbase[];

　　twstop[]=twsbase[];

　　return OK;

　　}//Init_Stack

　　Status push(BDStacktype &twsint iElemtype x)//x入棧i=表示低端棧i=表示高端棧

　　{

　　if(twstop[]>twstop[]) return OVERFLOW; //注意此時的棧滿條件

　　if(i==) *twstop[]++=x;

　　else if(i==) *twstop[]=x;

　　else return ERROR;

　　return OK;

　　}//push

　　Status pop(BDStacktype &twsint iElemtype &x)//x出棧i=表示低端棧i=表示高端棧

　　{

　　if(i==)

　　{

　　if(twstop[]==twsbase[]) return OVERFLOW;

　　x=*twstop[];

　　}

　　else if(i==)

　　{

　　if(twstop[]==twsbase[]) return OVERFLOW;

　　x=*++twstop[];

　　}

　　else return ERROR;

　　return OK;

　　}//pop

　　

　　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(sc);

　　*(q++)=c; //把H接在後部

　　}

　　}//Train_arrange

　　

　　int IsReverse()//判斷輸入的字符串中&前和&後部分是否為逆串是則返回否則返回

　　{

　　InitStack(s);

　　while((e=getchar())!=&)

　　push(se);

　　while((e=getchar())!=@)

　　{

　　if(StackEmpty(s)) return ;

　　pop(sc);

　　if(e!=c) return ;

　　}

　　if(!StackEmpty(s)) return ;

　　return ;

　　}//IsReverse

　　

　　Status Bracket_Test(char *str)//判別表達式中小括號是否匹配

　　{

　　count=;

　　for(p=str;*p;p++)

　　{

　　if(*p==() count++;

　　else if(*p==)) count;

　　if (count<) return ERROR;

　　}

　　if(count) return ERROR; //注意括號不匹配的兩種情況

　　return OK;

　　}//Bracket_Test

　　

　　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(sc);

　　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

　　

　　typedef struct {

　　 int x;

　　int y;

　　} coordinate;

　　void Repaint_Color(int g[m][n]int iint jint color)//把點(ij)相鄰區域的顏色置換為color

　　{

　　old=g[i][j];

　　InitQueue(Q);

　　EnQueue(Q{Ij});

　　while(!QueueEmpty(Q))

　　{

　　DeQueue(Qa);

　　x=ax;y=ay;

　　if(x>)

　　if(g[x][y]==old)

　　{

　　g[x][y]=color;

　　EnQueue(Q{xy}); //修改左鄰點的顏色

　　}

　　if(y>)

　　if(g[x][y]==old)

　　{

　　g[x][y]=color;

　　EnQueue(Q{xy}); //修改上鄰點的顏色

　　}

　　if(x

　　if(g[x+1][y]==old)

　　{

　　g[x+1][y]=color;

　　EnQueue(Q,{x+1,y}); //修改右鄰點的顏色

　　}

　　if(y

　　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); //運算符在棧內遵循越往棧頂優先級越高的原則

　　}//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(p^2-A)<=e) return p;

　　else return sqrt_recurve(A,(p+A/p)/2,e);

　　}//Sqrt_recurve

　　float Sqrt_nonrecursive(float A,f
From:http://tw.wingwit.com/Article/program/sjjg/201311/23571.html