4.10.c

数据结构习题及答案

4.10③  编写对串求逆的递推算法。

要求实现以下函数：
void Reverse(StringType &s);
/* Reverse s by iteration. */

StringType是串的一个抽象数据类型，它包含以下6种基本操作：
void InitStr(StringType &s);
  // 初始化s为空串。
void StrAssign(StringType &t, StringType s);
  // 将s的值赋给t。s的实际参数是串变量。
int StrCompare(StringType s, StringType t);
  // 比较s和t。若s>t，返回值>0；若s=t，返回值=0；若s<t，返回值<0。
int StrLength(StringType s);
  // 返回s中的元素个数，即该串的长度。
StringType Concat(StringType &s, StringType t); 
  // 返回由s和t联接而成的新串。
StringType SubString(StringType s, int start, int len);
  // 当1<=start<=StrLength(s)且0<=len<=StrLength(s)- start+1时，
  // 返回s中第start个字符起长度为len的子串，否则返回空串。

// 注意,不要使用 " s = " 的形式为 StringType 类型的变量赋值 ,
// 而要使用 StrAssign 函数!!!
void Reverse(StringType &s)
/* Reverse s by iteration. */
{ 
  StringType p,q,r;
  int i;
  StrAssign(q,"");                  //初始化
  for(i=StrLength(s);i!=0;i--)
  {
    StrAssign(p,SubString(s,i,1));   //从串尾每次取一个字符 
    StrAssign(r,Concat(q,p));
    StrAssign(q,r);
  }
    StrAssign(s,r);                  //把逆串赋给s
}