3.16.c

数据结构习题及答案

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,Hcount=0;
    for(i=0;i<train.length;i++)
      {
       if(train.elem[i]=='H')
         {
          s[j]='U';
          j++;                 //硬座入栈
          Hcount++;
         }
     else
         {
          s[j]='U';
          s[++j]='O';          //软座入栈同时出栈
          j++;
         }
      }
   for(i=1;i<=Hcount;i++)
     {
      s[j]='O';
      j++;
     }

}