◆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(sizeof(SElemType)*size); 
 tws.size=size; 
 tws.top[0]=0; //hao 
 tws.top[1]=size-1; 
 return OK; 

}

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

 

}

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

}

 

 

◆3.16②  假设如题3.1所述火车调度站的入口处有n节
硬席或软席车厢（分别以H和S表示）等待调度，试编
写算法，输出对这n节车厢进行调度的操作（即入栈
或出栈操作）序列，以使所有的软席车厢都被调整到
硬席车厢之前。
   
实现下列函数：
void SwitchYard(SqList train, char *s);   


顺序表类型定义如下：
typedef struct {
    ElemType *elem;
    int       length;
    int       listsize;
} SqList;  // 顺序表

 

void SwitchYard(SqList train, char *s)
{ int i,j=0,L; 
 char *p; 
 L=train.length;p=s;
 for(i=0;i<=L-1;i++) 
 { 
 if(train.elem[i]=='H') 
 {*(p++)='U';j++;} 
 else 
 { 
 *p='U'; p++; 
 *p='O'; p++; 
 } 
 } 
 for(;j>0;j--)
 { *p='O';p++; } 

}

 

◆3.19④ 假设一个算术表达式中可以包含三种括号：圆括号"(" 和
")"，方括号"["和"]"和花括号"{"和"}"，且这三种括号可按任意的
次序嵌套使用（如：…[…{…}…[…]…]…[…]…(…)…）。编写判别给定表达
式中所含括号是否正确配对出现的算法(已知表达式已存入数据元素
为字符的顺序表中)。 

实现下列函数：
Status MatchCheck(SqList exp);                 

顺序表类型定义如下：
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)
{ Stack s;
  char *p;
  SElemType c;
 InitStack(s);
  for(p=exp.elem;*p;p++)
  {
    if(*p=='('||*p=='['||*p=='{') Push(s,*p);
    else if(*p==')'||*p==']'||*p=='}')
    {
      if(StackEmpty(s)) return FALSE;
      Pop(s,c);
      if(*p==')'&&c!='(') return FALSE;
      if(*p==']'&&c!='[') return FALSE;
      if(*p=='}'&&c!='{') return FALSE;
    }
  }
  if(!StackEmpty(s)) return FALSE;
  return TRUE;

 }

 

◆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);

表示图像区域的类型定义如下：
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 x,y,old;
   Stack s; 
  old=g[i0][j0];
  StackInit(s,m*n*2);
  Push(s,i0);
  Push(s,j0);

  while(!StackEmpty(s))
  {
   Pop(s,y);
   Pop(s,x);
    if(x>1)
      if(g[x-1][y]==old)
      {
        g[x-1][y]=c;
        Push(s,x-1);
        Push(s,y);
      }
    if(y>1)
      if(g[x][y-1]==old)
      {
        g[x][y-1]=c;
        Push(s,x);
        Push(s,y-1);
      }
    if(x
      if(g[x+1][y]==old)
      {
        g[x+1][y]=c;
        Push(s,x+1);
        Push(s,y);

      }
    if(y
      if(g[x][y+1]==old)
      {
        g[x][y+1]=c;
        Push(s,x);
        Push(s,y+1);
      }
  }

}

 

 

◆3.21③  假设表达式由单字母变量和双目四则运
算算符构成。试写一个算法，将一个通常书写形式
且书写正确的表达式转换为逆波兰式。

实现下列函数：
char *RPexpression_r(char *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_r(char *e)
{ static char b[20]; 
 char *a=b; 
 char w3='k'; 
 char w; 
 char w1,w2; 
 Stack S; 
 InitStack(S); 
 while(*e!='\0') 
 { 
 switch(*e) 
 { 
 case '+': 
 if(!StackEmpty(S)) 
 { 
 Pop(S,w2); 
 Push(S,w2); 
 if(w2=='*'||w2=='/'||w2=='+'||w2=='-') 
 { 
 Pop(S,w); 
 *a=w; 
 a++; 
 } 
 w2=Top(S); 
 if(w2=='+'||w2=='-') 
 { 
 Pop(S,w); 
 *a=w; 
 a++; 
 } 
 Push(S,*e); 
 } //if(!StackEmpty(S)) 
 else Push(S,*e); 
 e++; 
 break; 
 case '-': 
 if(!StackEmpty(S)) 
 { 
 Pop(S,w2); 
 Push(S,w2); 
 if(w2=='*'||w2=='/'||w2=='+'||w2=='-') 
 { 
 Pop(S,w); 
 *a=w; 
 a++; 
 } 
 w2=Top(S); 
 if(w2=='+'||w2=='-') 
 { 
 Pop(S,w); 
 *a=w; 
 a++; 
 } 
 Push(S,*e); 
 } //if(!StackEmpty(S)) 
 else Push(S,*e); 
 e++; 
 break; 
 case '*': 
 if(!StackEmpty(S)) 
 { 
 Pop(S,w2); 
 Push(S,w2); 
 if(w2=='*'||w2=='/') 
 { 
 Pop(S,w); 
 *a=w; 
 a++; 
 } 
 Push(S,*e); 
 } //if(!StackEmpty(S)) 
 else Push(S,*e); 
 e++; 
 break; 
 case '/': 
 if(!StackEmpty(S)) 
 { 
 Pop(S,w2); 
 Push(S,w2); 
 if(w2=='*'||w2=='/') 
 { 
 Pop(S,w); 
 *a=w; 
 a++; 
 } 
 Push(S,*e); 
 } //if(!StackEmpty(S)) 
 else Push(S,*e); 
 e++; 
 break; 
 case '(': 
 Push(S,*e); 
 e++; 
 break; 
 case ')': 
 while(w3!='('&&!StackEmpty(S)) 
 { 
 Pop(S,w3); 
 if(w3!='(') 
 { 
 *a=w3; 
 a++; 
 } 
 } //while 
 w3='k'; 
 e++; 
 break; 
 default: 
 *a=*e; 
 a++; 
 e++; 
 break; 
 } //switch(*e) 
 } //while(*e!='\0') 
 while(!StackEmpty(S)) 
 { 
 Pop(S,w); 
 *a=w; 
 a++; 
 } 
 *a='\0'; 
 return b; 

 }

 

◆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);

 

int G(int m, int n)
{int s;
if(m<0||n<0)return -1;
if(m==0&&n>=0) s=0;
else if(m>0&&n>=0) s=n+G(m-1,2*n);
return s;
}
   

 

◆3.25④ 试写出求递归函数F(n)的递归算法，
并消除递归：
    F(n) = n+1      当n=0
    F(n) = nF(n/2)  当n>0

实现下列函数：
int F(int n);

 

int F(int n)
{int s;
  if(n<0) return -1;
  if(n==0) s=n+1;
  else
  {
   
   s=n*F(n/2);
  }
  return s;
}

 

◆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)); 
 rear->next=rear; 
  return (OK); 

}

Status EnCLQueue(CLQueue &rear, ElemType x)
{LinkList p; 
 p=(CLQueue)malloc(sizeof(LNode)); 
 p->data=x; 
 p->next=rear->next; 
 rear->next=p; 
 rear=p; 
 return OK; 

}

Status DeCLQueue(CLQueue &rear, ElemType &x)
{LinkList q; 
 if(rear==rear->next) return ERROR ; 
 q=rear->next->next; 
 x=q->data; 
 rear->next->next=q->next; 
 free(q); 
 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.rear==Q.front&&Q.tag==1) return ERROR; 
 else 
 { 
 Q.elem[Q.rear]=x; 
 Q.rear++; 
 if(Q.rear==Q.front) Q.tag=1; 
 return OK; 
 } 

}

Status DeCQueue(CTagQueue &Q, QElemType &x)
{  if(Q.rear==Q.front&&Q.tag==0) return ERROR; 
 else 
 { 
 x=Q.elem[Q.front]; 
 Q.front++; 
 if(Q.rear==Q.front) 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; 
 else 
 { 
 Q.rear=Q.rear+1; 
 Q.elem[Q.rear]=x; 
 Q.length++; 
 return OK; 
 } 

}

Status DeCQueue(CLenQueue &Q, QElemType &x)
{ if(Q.length==0) return ERROR; 
 else 
 { 
 int front; 
 front=front+1; 
 Q.length--; 
 return OK; 
 } 

}

 

 

◆3.31③  假设称正读和反读都相同的字符序列为
"回文"，例如，'abba'和'abcba'是回文，'abcde'
和'ababab'则不是回文。试写一个算法判别读入的
一个以'@'为结束符的字符序列是否是"回文"。

实现下列函数：
Status Palindrome(char *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)
{ char a,b; 
 Stack S; 
 Queue Q; 
 InitStack(S); 
 InitQueue(Q); 
 while(*word!='@') 
 { 
 Push(S,*word); 
 EnQueue(Q,*word); 
 word++; 
 } 
 while(!StackEmpty(S))
 { 
 Pop(S,a); 
 DeQueue(Q,b); 
 if(a!=b) return ERROR; 
 } 
 return OK; 

}