第三章.txt

这是自己编写的,严蔚敏版的数据结构第三章的部分答案

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