3.2　強化習題詳解

【基礎知識題】

1若按教科書3.1.1節中圖3.1（b）所示的鐵道進行車廂調度（注意：兩側鐵道均為單向行駛道），則請回答：

（1）如果進棧的車廂序列為123，則可能得到的出站車廂序列是什么？

（2）如果進棧的車廂序列為123456，則能否得到435612和135426的出站序列，并請說明為什么不能得到或者如何得到（即寫出以‘S’表示進棧和以‘X’表示出棧的棧操作序列）。

答：（1）123，132，213，231，321。

（2）①可以得到135426的出棧序列，方法為：

1S，1X，輸出為1；

2S，3S，3X，輸出為1 3；

4S，5S，5X，輸出為1 3 5；

4X，輸出為1 3 5 4；

2X，輸出為1 3 5 4 2；

6S，6X，輸出為1 3 5 4 2 6。

②不能得到435612的出棧序列。因為4356出棧說明12已經在棧中，而1為棧底元素，2為棧頂元素，1不可能先于2出棧。

2簡述棧和線性表的差別。

答：含有n個相同數據類型的數據元素的有限序列稱為線性表，可以進行隨機插入和刪除操作；棧是限定僅在表尾進行插入或刪除操作的線性表，具有后進先出的特點。

棧是特殊的線性表，其操作是線性表基本操作的子集。

3寫出下列程序段的輸出結果（棧的元素類型SElemType為char）。

void main()
{
  Stack S;
  char x,y;
  InitStack(S);
  x= 'c';
  y= 'k';
  Push(S,x);
  Push(S, 'a');
  Push(S,y);
  Pop(S,x);
  Push(S, 't');
  Push(S,x);
  Pop(S,x);
  Push(S, 's');
  while(!StackEmpty(S))
  {
    Pop(S,y);
    printf(y);
  }
  printf(x);
}

答：根據進棧和出棧的順序依次寫出字符，答案為stack。

4簡述以下算法的功能（棧的元素類型SElemType為int）。

（1）

status algo1(Stack S)
{
  //初始時，S中已有255個元素
  int i,n,A[255];
  n=0;
  while(!StackEmpty(S))
  {
    n++;
    Pop(S,A[n]);
  }
  for(i=1;i<=n;i++)
    Push(S,A[i]);
}

（2）

status algo2(Stack S,int e)
{
  Stack T;
  int d;
  InitStack(T);
  while(!StackEmpty(S))
  {
    Pop(S,d);
    if(d!=e)Push(T,d);
  }
  while(!StackEmpty(T))
  {
    Pop(T,d);
    Push(S,d);
  }
}

答：（1）實現了棧中的數據元素逆置（棧具有后進先出的特點，元素依次出棧后再次入棧，會實現逆序）。

（2）利用棧T輔助查找棧中為e的元素，將其從棧中清除（先將元素全部出棧，如果元素不是e，則再次進棧，從而可以將棧中為e的元素清除）。

5假設以S和X分別表示入棧和出棧的操作，則初態和終態均為空棧的入棧和出棧的操作序列可以表示為僅由S和X組成的序列。稱可以操作的序列為合法序列（例如，SXSX為合法序列，SXXS為非法序列）。試給出區分給定序列為合法序列或非法序列的一般準則，并證明：兩個不同的合法（棧操作）序列（對同一輸入序列）不可能得到相同的輸出元素（注意：在此指的是元素實體，而不是值）序列。

答：一般準則：任意一個由S和X組成的前n個序列中，S的數目一定大于或者等于X的數目，且整個序列中S和X的數目相等。

下面證明兩個不同的合法序列不可能得到相同的輸出元素序列：

設兩個合法序列

T1＝S，…，X，…，S

T2＝S，…，X，…，X

分別是對存儲在棧A和棧B中的元素進行操作的序列，設前n個序列相同，從第n＋1個操作開始序列不相同，由于前n個操作序列相同，則棧中已存元素個數相同。現假設當前棧頂元素均為a，不妨礙設第n＋1個操作分別為：T1向棧A壓入b元素，T2從棧B退棧a元素，則T1操作得到的局部序列應為…，b，a，…，而T2操作得到的局部序列應為…，a，b，…，顯然證得兩個不同的合法（棧操作）序列（對同一輸入序列）不可能得到相同的輸出元素（注意：在此指的是元素實體，而不是值）序列。

6試證明：若借助棧由輸入序列12…n得到的輸出序列為P₁P₂P₃（它是輸入序列的一個排列），則在輸出序列中不可能出現這樣的情形：存在著i＜j＜k使P_j＜P_k＜P_i。

答：因為輸入序列是從小到大排列的，所以若Pj＜Pk＜Pi，則可以理解為通過輸入序列P_jP_kP_i可以得到輸出序列P_iP_jP_k，設P_j＝1，P_k＝2，P_i＝3，由棧的后進先出特點可知，通過輸入序列123是無法得到312的。所以不可能存在著i＜j＜k使Pj＜Pk＜Pi。

7按照四則運算加、減、乘、除和冪運算（↑）優先關系的慣例，并仿照教科書3.2節例3-2的格式，畫出對下列算術表達式求值時操作數棧和運算符棧的變化過程：A－B×C/D＋E↑F。

答：根據題意，其變化過程如表3-2所示。

表3-2　算術表達式求值變化過程表

8試推導求解n階Hanoi塔問題至少要執行的move操作的次數。

答：設至少要執行M（n）次move操作，由該問題的遞歸方程

可得

M（n）＝2M（n－1）＋1＝2（2M（n－2）＋1）＋1＝…＝2^n－1M（1）＋2^n－2＋…＋2¹＋2⁰

其中M（1）＝1；解得M（n）＝2ⁿ－1。

【算法設計題】

9試將下列遞推過程改寫為遞歸過程。

void ditui(int n)
{
  int i;
  i = n;
  while(i>1)
    printf(i--);
}

答：

void ditui(int j)
{
  if(j>1)
  {
    printf(j);
    ditui(j-1);
  }
  return;
}

10試將下列遞歸過程改寫為非遞歸過程。

void test(int &sum)
{
  int x;
  scanf("%d", &x);
  if(x==0)
    sum=0;
  else
  {
    test(sum);
    sum+=x;
  }
  printf("%d\n", sum);
}

答：當參數sum傳入20時，輸入和輸出結果如下：

輸入：1 2 3 4 5 6 0

輸出：0 26 25 24 23 22 21

由輸出結果可知，輸出＝輸入＋sum，且輸出結果與輸入相逆，需要使用棧，其非遞歸程序如下：

void test(int &sum)
{
  Stack s;
  InitStack(s);
  int x;
  do
  {
    scanf("%d",&x);
    Push(s,x);
  }while(x>0);
  while(!StackEmpty(s))
  {
    Pop(s,x);
    sum+=x;
    printf(sum);
  }
  DestoryStack(s);
}

11簡述隊列和棧這兩種數據類型的相同點和差異處。

答：相同點：棧和隊列都是操作受限的線性表。

不同點：

①棧是一種后進先出的線性表，且只允許在棧頂進行插入和刪除操作。

②隊列是一種先進先出的線性表，且只允許在隊頭進行刪除操作，在隊尾進行插入操作。

12寫出以下程序段的輸出結果（隊列中的元素類型QElemType為char）。

void main()
{
  Queue Q;
  InitQueue(Q);
  char x='e',y='c';
  EnQueue(Q,'h');
  EnQueue(Q,'r');
  EnQueue(Q,y);
  DeQueue(Q,x);
  EnQueue(Q,x);
  DeQueue(Q,x);
  EnQueue(Q,'a');
  While(!QueueEmpty(Q))
  {
    DeQueue(Q,y);
    printf(y);
  }
  printf(x);
}

答：char（根據隊列先進先出的操作特點，按照入隊和出隊順序依次寫出元素即可。）

13簡述以下算法的功能（棧和隊列的元素類型均為int）。

void algo3(Queue &Q)
{
  Stack S;
  int d;
  InitStack(S);
  while(!QueueEmpty(Q))
  {
    DeQueue(Q,d);
    Push(S,d);
  }
  while(!StackEmpty(S))
  {
    Pop(S,d);
    EnQueue(Q,d);
  }
}

答：該算法充分利用棧后進先出的特點和隊列先進先出的特點，功能是借助棧，將隊列中的數據元素進行逆置。

14若以1234作為雙端隊列的輸入序列，試分別求出滿足以下條件的輸出序列：

（1）能由輸入受限的雙端隊列得到，但不能由輸出受限的雙端隊列得到的輸出序列。

（2）能由輸出受限的雙端隊列得到，但不能由輸入受限的雙端隊列得到的輸出序列。

（3）既不能由輸入受限的雙端隊列得到，也不能由輸出受限的雙端隊列得到的輸出序列。

答：（1）4132

（2）4213

（3）4231

【注意】特殊棧和隊列在考研中時常出現，重點是會模擬其元素進出的過程。

15假設以順序存儲結構實現一個雙向棧，即在一維數組的存儲空間中存在著兩個棧，它們的棧底分別設在數組的兩個端點。試編寫實現這個雙向棧tws的三個操作：初始化inistack(tws)、入棧push(tws,i,x)和出棧pop(tws,i)的算法，其中i為0或1，用以分別指示設在數組兩端的兩個棧，并討論按過程（正/誤狀態變量可設為變參）或函數設計這些操作算法各有什么優缺點。

答：

typedef struct
{
  Elemtype *base[2]; //表示初始棧頂位置
  Elemtype *top[2]; //表示實際棧頂位置
}BDStacktype; //雙向棧類型
Status inistack(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;
} //inistack
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; //x入棧，進入低端棧
  else if(i==1)
    *tws.top[1]--=x; //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 Stack_Empty; //出棧時的棧空條件
    x=*--tws.top[0]; //x從低端棧出棧
  }
  else if(i==1)
  {
    if(tws.top[1]==tws.base[1])
      return Stack_Empty;
    x=*++tws.top[1]; //x從高端棧出棧
  }
  else
    return ERROR;
  return OK;
} //pop

16假設如題1所示火車調度站的入口處有n節硬席或軟席車廂（分別以H和S表示）等待調度，試編寫算法，輸出對這n節車廂進行調度的操作（即入棧或出棧操作）序列，以使所有的軟席車廂都被調整到硬席車廂之前。

答：

void Train_arrange(char *train) //這里用字符串train表示火車，H表示硬席，S表示軟席。
{
  q=train;
  p=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

17試寫一個算法，識別一次讀入的一個以@為結束符的字符序列是否為形如“序列1&序列2”模式的字符序列。其中序列1和序列2中都不含字符'&'，且序列2是序列1的逆序列。例如，“a+b&b+a”是屬該模式的字符序列，而“1+3&3-1”則不是。

答：

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; //最后添加判斷，若棧中還有元素，說明不是逆序列，考慮情況1234&432@
  return 1; //返回1，表明是符合模式的字符序列
} //IsReverse

18試寫一個判別表達式中開、閉括號是否配對出現的算法。

答：（1）使用棧：

bool BracketCorrespondency(char a[])
{
  int i=0;
  Stack s;
  InitStack(s);
  ElemType x;
  while(a[i])
  {
    switch(a[i])
    {
      case '(':
        Push(s,a[i]);
        break; //遇到左小括號，則入棧
      case '[':
        Push(s,a[i]);
        break; //遇到左中括號，則入棧
      case ')': //遇到 ) 或 ] 時，取出棧頂元素進行匹配，不匹配則說明有誤
        GetTop(s,x);
        if(x=='(')
          Pop(s,x);
        else
          return FALSE;
        break;
      case ']':
        GetTop(s,x);
        if(x=='[')
          Pop(s,x);
        else
          return FALSE;
        break;
    }
    i++;
  }
  return true;
}

（2）不使用棧：

Status Bracket_Test(char *str) //判別表達式中小括號是否匹配
{
  count=0;
  for(p=str;*p;p++)
  {
    if(*p= ='(')
      count++;
    else if(*p= =')')
      count--;
    if(count<0) //count<0，說明“）”的個數多于“（”的個數，不可能出現“）”數目超過“（”數目的情況
      return ERROR;
  }
  if(count)
    return ERROR; // count>0，說明“（”的個數多于“）”的個數，表達式中小括號不匹配
  return OK;
} //Bracket_Test

【注意】在（2）不使用棧的算法中，如果要判斷[]的匹配，方法和（）的匹配一樣。

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

【注意】在括號匹配中，都需要滿足兩個條件：一是括號必須成對出現；二是括號必須鄰接匹配（即在所給表達式中，不能出現鄰接的括號類似于“(”和“}”，這是不滿足要求的）。

20假設以二維數組g（1…m，1…n）表示一個圖像區域，g[i，j]表示該區域中點（i，j）所具顏色，其值為從0到k的整數。編寫算法置換點（i₀，j₀）所在區域的顏色。約定和（i₀，j₀）同色的上、下、左、右的鄰接點為同色區域的點。

答：

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,{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; //將左鄰點顏色置換為color
        EnQueue(Q,{x-1,y}); //修改左鄰點的顏色
      }
    if(y>1)
      if(g[x][y-1]==old)
      {
        g[x][y-1]=color; //將上鄰點顏色置換為color
        EnQueue(Q,{x,y-1}); //修改上鄰點的顏色
      }
    if(x<m)
      if(g[x+1][y]==old)
      {
        g[x+1][y]=color; //將右鄰點顏色置換為color
        EnQueue(Q,{x+1,y}); //修改右鄰點的顏色
      }
    if(y<n)
      if(g[x][y+1]==old)
      {
        g[x][y+1]=color; //將下鄰點顏色置換為color
        EnQueue(Q,{x,y+1}); //修改下鄰點的顏色
      }
  } //while
} //Repaint_Color

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

22如題21的假設條件，試寫一個算法，對以逆波蘭式表示的表達式求值。

答：

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

23如題21的假設條件，試寫一個算法，判斷給定的非空后綴表達式是否為正確的逆波蘭表達式（即后綴表達式），如果是，則將它轉化為波蘭式。

答：

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)。

24試編寫如下定義的遞歸函數的遞歸算法，并根據算法畫出求g（5，2）時棧的變化過程。

答：

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

假設主函數的返回地址是0，遞歸函數三條語句的返回地址是1、2、3，求g（5，2）時棧的變化過程如表3-3所示。

表3-3　棧變化過程表

25試寫出求遞歸函數F（n）的遞歸算法，并消除遞歸：

答：

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

26求解平方根的迭代函數定義如下：

其中，p是A的近似平方根，e是結果允許誤差。試寫出相應的遞歸算法，并消除遞歸。

答：

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,float p,float e) //求平方根的非遞歸算法
{
  while(abs(p^2-A)>=e)
    p=(p+A/p)/2;
  return p;
} //Sqrt_nonrecu rsive

27已知Ackerman函數的定義如下：

（1）寫出遞歸算法；

（2）寫出非遞歸算法；

（3）根據非遞歸算法，畫出求akm（2，1）時棧的變化過程。

答：（1）遞歸算法

unsigned int akm(unsigned int m,unsigned int n)
{
  unsigned int g;
  if(m==0)
    return n+1;
  else
    if(n==0)
      return akm(m-1,1);
    else
    {
      g=akm(m,n-1);
      return akm(m-1,g);
    }
}

（2）非遞歸算法：

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; //m=0時，akm(m,n)=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)
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;

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;
  Q->next=p; //直接把p加在Q的后面
  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;
}

29如果希望循環隊列中的元素都能得到利用，則需設置一個標志域tag，并以tag的值為0和1來區分尾指針和頭指針值相同時的隊列狀態是“空”還是“滿”。試編寫與此結構相應的入隊列和出隊列的算法，并從時間和空間角度討論設標志和不設標志這兩種方法的使用范圍（如當循環隊列容量較小而隊列中每個元素占的空間較多時，哪一種方法較好）。

答：

#define MaxQSize 4
typedef int ElemType;
typedef struct
{
  ElemType *base;
  int front;
  int rear;
  Status tag;
}Queue;
Status InitQueue(Queue &q)
{
  q.base=(ElemType*)malloc(MaxQSize*sizeof(ElemType));
  if(!q.base)
    return FALSE;
  q.front=0;
  q.rear=0;
  q.tag=0;
  return OK;
}
Status EnQueue(Queue &q,ElemType e)
{
  if(q.front= =q.rear&&q.tag)
    return FALSE; //隊列的頭指針和尾指針指向同一結點，并且隊列狀態為“滿”，則元素不能入隊
  else
  {
    q.base[q.rear]=e;
    q.rear=(q.rear+1)%MaxQSize; //循環隊列計算尾指針的位置
    if(q.rear= =q.front) //入隊操作后如果頭指針和尾指針指向同一個結點，說明隊列已滿
      q.tag=1;
  }
  return OK;
}
Status DeQueue(Queue &q,ElemType &e)
{
  if(q.front==q.rear&&!q.tag)
    return FALSE; //隊列的頭指針和尾指針指向同一結點，并且隊列狀態為“空”，沒有可出隊的元素
  else
  {
    e=q.base[q.front];
    q.front=(q.front+1)%MaxQSize; //循環隊列計算頭指針的位置
    q.tag=0; //出隊操作后，隊列可以繼續入隊
  }
  return OK;
} //設標志節省存儲空間，但運行時間較長，不設標志則正好相反。

當循環隊列容量較小而隊列中每個元素占的空間較多時設置tag位能夠充分利用存儲空間，更有價值。

30假設將循環隊列定義為：以域變量rear和length分別指示循環隊列中隊尾元素的位置和內含元素的個數。試給出此循環隊列的隊滿條件，并寫出相應的入隊列和出隊列的算法（在出隊列的算法中要返回隊頭元素）。

答：設head指示循環隊列中隊頭元素元素的位置，則有

head=((q.rear+MAXLEN)-q.length+1)%MAXLEN

其中MAXLEN為隊列可用的最大空間。

隊滿的條件為：length==MAXLEN。

#define MaxQSize 4
typedef int ElemType;
typedef struct
{
  ElemType *base;
  int rear;
  int length;
}Queue;
Status InitQueue(Queue &q)
{
  q.base=(ElemType*)malloc(MaxQSize*sizeof(ElemType));
  if(!q.base)
    return FALSE;
  q.rear=0;
  q.length=0;
  return OK;
}
Status EnQueue(Queue &q,ElemType e)
{
  //入隊操作，頭指針與尾指針指向同一結點，隊列滿
  if((q.rear+1)%MaxQSize==(q.rear+MaxQSize-q.length)%MaxQSize)
    return FALSE;
  else
  {
    q.base[q.rear]=e;
    q.rear=(q.rear+1)%MaxQSize; //循環隊列計算尾指針位置
    q.length++;
  }
  return OK;
}
Status DeQueue(Queue &q,ElemType &e)
{
  //出隊操作，頭指針與尾指針指向同一個結點，隊列空
  if((q.rear+MaxQSize-q.length)%MaxQSize==q.rear)
    return FALSE;
  else
  {
    e=q.base[(q.rear+MaxQSize-q.length)%MaxQSize]; //隊頭元素
    q.length--;
  }
  return OK;
}

31假設稱正讀和反讀都相同的字符序列為“回文”，例如，“abba”和“abcba”是回文，“abcde”和“ababab”則不是回文。試寫一個算法判別讀入的一個以'@'為結束符的字符序列是否是“回文”。

答：

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;
}

32試利用循環隊列編寫求k階菲波那契序列中前n＋1項的算法，要求滿足：f_n≤max而f_n＋1＞max，其中max為某個約定的常數。（注意：本題所用循環隊列的容量僅為k，則在算法執行結束時，留在循環隊列中的元素應是所求k階菲波那契序列中的最后k項）

答：

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(j=0;j<k;j++)
      sum=sum+Q.base[(m+j)%k];
    Q.base[m]=sum; //求第i項的值存入隊列中并取代已無用的第一項
    printf("%d",sum);
  }
}

33在順序存儲結構上實現輸出受限的雙端循環隊列的入列和出列（只允許隊頭出列）算法。設每個元素表示一個待處理的作業，元素值表示作業的預計時間。入隊列采取簡化的短作業優先原則，若一個新提交的作業的預計執行時間小于隊頭和隊尾作業的平均時間，則插入在隊頭，否則插入在隊尾。

答：

typedef struct
{
  ElemType *base;
  int front;
  int rear;
  Status tag;
  int MaxSize;
}DQueue; //定義隊列的抽象數據類型
Status InitDQueue(Dqueue &q,int size)
{
  q.MaxSize=size;
  q.base=(ElemType*)malloc(MaxSize*sizeof(ElemType));
  if(!q.base)
    return FALSE; //初始化操作失敗
  q.front=0;
  q.rear=0;
  q.tag=0;
  return OK;
}
Status EnDQueue(Dqueue &q,ElemType e)
{
  if(q.front==q.rear&&q.tag)
    return FALSE; //隊列已滿，無法進行入列操作
  if(q.front==q.rear&&!q.tag) //空隊列
  {
    q.base[q.rear]=e;
    q.rear=(q.rear+1)%q.MaxSize;
    if(q.rear==q.front)
      q.tag=1;
  }
  else //非空非滿，若一個新提交的作業的預計執行時間小于隊頭和隊尾作業的平均時間，則插入在隊頭，否則插入在隊尾。
  {
    if(e<(q.base[q.front]+q.base[(q.rear+q.MaxSize-1)%q.MaxSize])/2)
    {
    //從隊頭入隊
      q.front=(q.front+q.MaxSize-1)%q.MaxSize; //計算循環隊列的頭指針
      q.base[q.front]=e;
      if(q.rear==q.front)
        q.tag=1; //判斷隊列是否已滿
    }
    else //從隊尾入隊

    {
      q.base[q.rear]=e;
      q.rear=(q.rear+1)%q.MaxSize; //計算循環隊列的尾指針
      if(q.rear==q.front)
        q.tag=1; //判斷隊列是否已滿
    }
  }
  return OK;
}
Status DeDQueue(Dqueue &q,ElemType &e)
{
  if(q.front==q.rear&&!q.tag)
    return FALSE; //空隊列，無法進行出列操作
  else
  { //非空隊列
    e=q.base[q.front];
    q.front=(q.front+1)%q.MaxSize; //計算頭指針位置
    q.tag=0; //設置隊列不滿的標志
  }
  return OK;
}

34假設在如教科書3.4.1節中圖3.9所示的鐵道轉軌網的輸入端有n節車廂：硬座、硬臥和軟臥（分別以P，H和S表示）等待調度，要求這三種車廂在輸出端鐵道上的排列次序為：硬座在前，軟臥在中，硬臥在后。試利用輸出受限的雙端隊列對這n節車廂進行調度，編寫算法輸出調度的操作序列：分別以字符'E'和'D'表示對雙端隊列的頭端進行入隊列和出隊列的操作；以字符A表示對雙端隊列的尾端進行入隊列的操作。

答：

void Train_Rearrange(char *train)
//這里用字符串train表示火車，'P'表示硬座，'H'表示硬臥，'S'表示軟臥，最終按P，S，H的順序排列
{
  char *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);
  } //從頭端出隊列的車廂必然按P，S，H的順序排列
}