熱點推薦:
您现在的位置: 電腦知識網 >> 編程 >> 數據結構 >> 正文

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

2013-11-15 15:32:17  來源: 數據結構 

  第三章 棧與隊列

  

  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

    推薦文章
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.