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

實現下列3個函數：
Status InitStack(TwoWayStack &tws, int size);
Status Push(TwoWayStack &tws, int i, SElemType x);
Status Pop(TwoWayStack &tws, int i, SElemType &x);

雙向棧類型定義如下：
typedef struct {
    SElemType *elem;
    int        top[2];
    int        size;    // 分配給elem的總容量
}TwoWayStack;           // 雙端棧

Status InitStack(TwoWayStack &tws, int size)
{
 tws.elem=(SElemType*)malloc(size*sizeof(SElemType));
 if(!tws.elem) exit(OVERFLOW);
 tws.top[0]=0;
 tws.size=size;
 tws.top[1]=tws.size-1;
 return OK;  
}

Status Push(TwoWayStack &tws, int i, SElemType x)
{
 if(tws.top[1]<tws.top[0]) return ERROR;
 else
   {
    if(!i)
    tws.elem[tws.top[0]++]=x;
    else
      tws.elem[tws.top[1]--]=x; 
 return OK;
 }
}

Status Pop(TwoWayStack &tws, int i, SElemType &x)
{
 if(!i)
   {
    if(!tws.top[0]) return ERROR;
    else x=tws.elem[--tws.top[0]];
   }
 else
   {
    if(tws.top[1]==tws.size-1) return ERROR;
    else x=tws.elem[++tws.top[1]];
   }
 return OK;
}


3.16②  假設如題3.1所述火車調度站的入口處有n節
硬席或軟席車廂（分別以H和S表示）等待調度，試編
寫算法， 輸出對這n節車廂進行調度的操作（即入棧
或出棧操作）序列，以使所有的軟席車廂都被調整到
硬席車廂之前。
    
實現下列函數：
void SwitchYard(SqList train, char *s);    
/* 順序表train表示列車，其元素取值H或S，   */
/* 分別表示硬席或軟席車廂；                */
/* 以U和O分別表示入棧和出棧操作；          */
/* 函數用參數s以UO串的形式，返回對該列車   */
/* 進行軟席在前，硬席在后的編組的操作序列。*/

順序表類型定義如下：
typedef struct {
    ElemType *elem;
    int       length;
    int       listsize;
} SqList;  // 順序表

void SwitchYard(SqList train, char *s)
/* 順序表train表示列車，其元素取值H或S，   */
/* 分別表示硬席或軟席車廂；                */
/* 以U和O分別表示入棧和出棧操作；          */
/* 函數用參數s以UO串的形式，返回對該列車   */
/* 進行軟席在前，硬席在后的編組的操作序列。*/
{
 int i,j=0;
 for(i=0;i<train.length;i++)
   {   
    if(train.elem[i]=='S')   //如果是S,則先返回U,再返回O
      {
       *(s++)='U';
       *(s++)='O';
      }    
    if(train.elem[i]=='H')
      {
       *(s++)='U';        //如果是H,則先返回U,再把U的個數用j記錄下來
       j++;
      }
   }   
 for(i=0;i<j;i++)         // 根據j返回O的個數 
   *(s++)='O'; 
}



◆3.19④ 假設一個算術表達式中可以包含三種括號：圓括號"(" 和
")"，方括號"["和"]"和花括號"{"和"}"，且這三種括號可按任意的
次序嵌套使用（如：…[…{…}…[…]…]…[…]…(…)…）。編寫判別給定表達
式中所含括號是否正確配對出現的算法(已知表達式已存入數據元素
為字符的順序表中)。  

實現下列函數：
Status MatchCheck(SqList exp);                  
/* 順序表exp表示表達式；                        */
/* 若exp中的括號配對，則返回TRUE，否則返回FALSE */

順序表類型定義如下：
typedef struct {
    ElemType *elem;
    int       length;
    int       listsize;
} SqList;  // 順序表

Stack是一個已實現的棧。
可使用的相關類型和函數：
typedef char SElemType; // 棧Stack的元素類型
Status InitStack(Stack &s);
Status Push(Stack &s, SElemType e);
Status Pop(Stack &s, SElemType &e);
Status StackEmpty(Stack s);
Status GetTop(Stack s, SElemType &e);

Status MatchCheck(SqList exp)
/* 順序表exp表示表達式；                        */
/* 若exp中的括號配對，則返回TRUE，否則返回FALSE */
{
 SqStack S;
 int i;
 char s;
 InitStack(S);
 for(i=0;i<exp.length;i++)
   {
    if(exp.elem[i]=='(' || exp.elem[i]=='[' || exp.elem[i]=='{')
      Push(S,exp.elem[i]);     //如果是左括號則把它們壓入棧中
    else
      if(exp.elem[i]==')' || exp.elem[i]==']' || exp.elem[i]=='}')
        {
         if(StackEmpty(S)) return ERROR;   //如果是右括號,而S是空棧,則不匹配
         Pop(S,s);
         if(s!='(' && exp.elem[i]==')') return ERROR;
         if(s!='[' && exp.elem[i]==']') return ERROR;  
         if(s!='{' && exp.elem[i]=='}') return ERROR;
        }
   }
 if(!StackEmpty(S)) return ERROR;   //最后如果S不為空,不匹配
 return OK;

}



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

實現下列函數：
void ChangeColor(GTYPE g, int m, int n, 
                 char c, int i0, int j0);
/* 在g[1..m][1..n]中，將元素g[i0][j0] */
/* 所在的同色區域的顏色置換為顏色c    */

表示圖像區域的類型定義如下：
typedef char GTYPE[m+1][n+1];

Stack是一個已實現的棧。
可使用的相關類型和函數：
typedef int SElemType; // 棧Stack的元素類型
Status StackInit(Stack &s, int initsize);
Status Push(Stack &s, SElemType e);
Status Pop(Stack &s, SElemType &e);
Status StackEmpty(Stack s);
Status GetTop(Stack s, SElemType &e);

void ChangeColor(GTYPE g,int m,int n,char c,int i0,int j0)
{
 int i,j;
 char old;
 SqStack S1,S2;
 old=g[i0][j0];
 StackInit(S1,m);
 StackInit(S2,n);
 Push(S1,i0);
 Push(S2,j0);
 while(!StackEmpty(S1) && !StackEmpty(S2))
   {
    Pop(S1,i);
    Pop(S2,j); 
    if(i>1)
      if(g[i-1][j]==old)
      {
       g[i-1][j]=c;
       Push(S1,i-1); 
       Push(S2,j);    //修改左鄰點的顏色
      }
    if(j>1)
      if(g[i][j-1]==old)
      {
        g[i][j-1]=c;
        Push(S1,i);  
        Push(S2,j-1);   //修改上鄰點的顏色
      }
    if(i<m)
      if(g[i+1][j]==old)
      {
        g[i+1][j]=c;
        Push(S1,i+1);
        Push(S2,j);     //修改右鄰點的顏色
      }
    if(j<n)
      if(g[i][j+1]==old)
      {
        g[i][j+1]=c;
        Push(S1,i);
        Push(S2,j+1);   //修改下鄰點的顏色
      }
  }
}



◆3.21③  假設表達式由單字母變量和雙目四則運
算算符構成。試寫一個算法，將一個通常書寫形式
且書寫正確的表達式轉換為逆波蘭式。

實現下列函數：
char *RPExpression(char *e);
/* 返回表達式e的逆波蘭式 */

Stack是一個已實現的棧。
可使用的相關類型和函數：
typedef char SElemType; // 棧Stack的元素類型
Status InitStack(Stack &s);
Status Push(Stack &s, SElemType e);
Status Pop(Stack &s, SElemType &e);
Status StackEmpty(Stack s);
SElemType Top(Stack s);

char *RPExpression(char *e)
/* 返回表達式e的逆波蘭式 */
{
 unsigned char Prior[7][7]={
      '>','>','<','<','<','>','>',
      '>','>','<','<','<','>','>',
      '>','>','>','>','<','>','>',      //用一個二維數組存放七個運算符
      '>','>','>','>','<','>','>',      //同時表示他們的優先關系
      '<','<','<','<','<','=',' ',
      '>','>','>','>',' ','>','>',
      '<','<','<','<','<',' ','='  };        
 char opset[7]={'+' , '-' , '*' , '/' ,'(' , ')' , '#'};   
 SqStack OPTR;      //定義一個棧用來暫時存放運算符
 char *new,*q,c;
 int i,j,k;
 new=(SElemType*)malloc(30*sizeof(SElemType));    //開辟一個新的數組空間存放
 if(!new)exit(OVERFLOW);                          //e的逆波蘭表達式
 q=new;                        //用p指向數組new的首地址
 InitStack(OPTR);
 Push(OPTR,'#');
 while(*e)
   {
    if('a'<=*e && *e<='z')        //如果e是字母，直接放到數組new里
      {
       *q++=*e;
       e++;
      }
    else
      {
       for(i=0;i<7;i++)
         {
          if(Top(OPTR)==opset[i])    //確定棧頂運算符在二維數組中所在的行
           {
            k=i;
            break;
           }
          }
       for(i=0;i<7;i++)
         {
          if(*e==opset[i])        //確定*e運算符在二維數組中所在的列
           {
            j=i;
            break;
           }
          }
       switch(Prior[k][j])
         {
          case '<':Push(OPTR,*e); e++; break;    //棧頂運算符關系比*e 小，則把*e運算符進棧
          case '=':Pop(OPTR,c); e++; break;      //相等則退棧，把它刪掉
          case '>':Pop(OPTR,c); *q++=c; break;   //大于也則棧，把退出來的運算符送到數組new
         }
      }
   if(!*e)
     {
      while(Top(OPTR)!='#' && !StackEmpty(OPTR)) //最后如果棧里不止有‘#’這個運算符
        {                                        //則把‘#’除外的所有運算符送到new
         Pop(OPTR,c);
         *q++=c;
        }      
     }
   }
 return new;
}



3.24③ 試編寫如下定義的遞歸函數的遞歸算法:
      g(m,n) = 0             當m=0,n>=0
      g(m,n) = g(m-1,2n)+n   當m>0,n>=0
并根據算法畫出求g(5,2)時棧的變化過程。

實現下列函數：
int g(int m, int n); 
/* if m<0 or n<0 then return -1. */

int G(int m, int n)
/* if m<0 or n<0 then return -1. */
{
 int f;
 if(n<0 || m<0)return -1;
 if(m==0) f==0;
 else f=G(m-1,2*n)+n;
 return f;
}



3.25④ 試寫出求遞歸函數F(n)的遞歸算法，
并消除遞歸：
    F(n) = n+1      當n=0
    F(n) = nF(n/2)  當n>0

實現下列函數：
int F(int n);
/* if n<0 then return -1. */

int F(int n)
/* if n<0 then return -1. */
{
 int f=1;
 if(n<0) return -1;
 while(n>1)
   {
    f*=n;
    n/=2;
   }
 return f;   
}



◆3.28② 假設以帶頭結點的循環鏈表表示隊列，并且
只設一個指針指向隊尾元素結點(注意不設頭指針)，
試編寫相應的隊列初始化、入隊列和出隊列的算法。

實現下列函數：
Status InitCLQueue(CLQueue &rear);
Status EnCLQueue(CLQueue &rear, ElemType x);
Status DeCLQueue(CLQueue &rear, ElemType &x);

帶頭結點循環鏈隊列CLQueue的類型為以下LinkList類型：
typedef struct LNode{
    ElemType data;
    struct LNode *next;
} LNode, *LinkList;
typedef LinkList CLQueue;

Status InitCLQueue(CLQueue &rear)
{
 rear=(CLQueue)malloc(sizeof(LNode));
 if(!rear) exit(OVERFLOW);
 rear->next=rear;
 return OK; 
}

Status EnCLQueue(CLQueue &rear, ElemType x)
{ 
 CLQueue p;
 p=(CLQueue)malloc(sizeof(LNode));
 if(!p) exit(OVERFLOW);
 p->data=x;
 p->next=rear->next;
 rear->next=p;
 rear=p;
 return OK;
}

Status DeCLQueue(CLQueue &rear, ElemType &x)
{ 
 CLQueue p;
 if(rear==rear->next) return ERROR;
 p=rear->next->next;
 x=p->data;
 rear->next->next=p->next;
 free(p);
 return OK;
}



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

實現下列函數：
Status EnCQueue(CTagQueue &Q, QElemType x);
Status DeCQueue(CTagQueue &Q, QElemType &x);

本題的循環隊列CTagQueue的類型定義如下：
typedef char QElemType;
typedef struct {
    QElemType elem[MAXQSIZE];
    int tag;
    int front;
    int rear;
} CTagQueue;

Status EnCQueue(CTagQueue &Q, QElemType x)
{
 if(Q.front==Q.rear && Q.tag==1)
   return ERROR;
 Q.elem[Q.rear]=x;
 Q.rear=(Q.rear+1)%MAXQSIZE;
 if(Q.rear==Q.front) Q.tag=1;
 return OK;
}

Status DeCQueue(CTagQueue &Q, QElemType &x)
{
 if(Q.front==Q.rear && Q.tag==0)
   return ERROR;
 x=Q.elem[Q.front];
 Q.front=(Q.front+1)%MAXQSIZE;
 if(Q.front==Q.rear) Q.tag=0;
 return OK;
}



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

實現下列函數：
Status EnCQueue(CLenQueue &Q, QElemType x);
Status DeCQueue(CLenQueue &Q, QElemType &x);

本題的循環隊列CLenQueue的類型定義如下：
typedef char QElemType;
typedef struct {
    QElemType elem[MAXQSIZE];
    int length;
    int rear;
} CLenQueue;

Status EnCQueue(CLenQueue &Q, QElemType x)
{
 if(Q.length==MAXQSIZE) return ERROR;   //隊列滿
 Q.rear=(Q.rear+1)%MAXQSIZE;
 Q.elem[Q.rear]=x;
 Q.length++;
 return OK;
}

Status DeCQueue(CLenQueue &Q, QElemType &x)
{
 int head;
 if(Q.length==0) return ERROR;     //隊列空
 head=(Q.rear+1+MAXQSIZE-Q.length)%MAXQSIZE;  //head指示循環隊列中隊頭元素的位置
 x=Q.elem[head];         //把隊頭元素返回
 Q.length--;
 return OK;
}



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

實現下列函數：
Status Palindrome(char *word);
/* 利用棧和隊列判定字符序列word是否是回文 */

可使用棧Stack和隊列Queue及其下列操作：
Status InitStack(Stack &S);           
Status Push(Stack &S, ElemType x);    
Status Pop(Stack &S, ElemType &x);    
Status StackEmpty(Stack S);           

Status InitQueue(Queue &Q);
Status EnQueue(Queue &Q, ElemType x);
Status DeQueue(Queue &Q, ElemType &x);
Status QueueEmpty(Queue Q);

Status Palindrome(char *word)
/* 利用棧和隊列判定字符序列word是否是回文 */
{
 SqStack S;
 CQueue Q;
 char q,s;
 InitStack(S);
 InitQueue(Q);
 while(*word!='@')
   {
    Push(S,*word);
    EnQueue(Q,*word);   //把字符序列一個一個字符都放到棧和隊列里面
    word++;
   }
 while(!StackEmpty(S) && !QueueEmpty(Q))
   {
    DeQueue(Q,q);    //根本棧的“后進先出”和隊列的”先進先出“比較原字符序列
    Pop(S,s);        //第一個和最后一個是否相同，以此類推
    if(q!=s) return ERROR;
   } 
 return OK;
}