heapstring.cpp

数据结构中串的应用： (1)利用堆存储结构的实现串的插入操作； (2) 利用堆存储结构的实现串的置换操作。

 #include"c1.h"
 #include"c4-2.h" //类型定义
 #include"bo4-2.cpp"  //基本操作

 Status StrInsert(HString &S,int pos,HString T) // 算法4.4
 { // 1≤pos≤StrLength(S)+1。在串S的第pos个字符之前插入串T
   int i;
   if(pos<1||pos>S.length+1) // pos不合法
     return ERROR;
   if(T.length) // T非空,则重新分配空间,插入T
   {
     S.ch=(char*)realloc(S.ch,(S.length+T.length)*sizeof(char));
     if(!S.ch)
       exit(OVERFLOW);
     for(i=S.length-1;i>=pos-1;--i) // 为插入T而腾出位置
       S.ch[i+T.length]=S.ch[i];
     for(i=0;i<T.length;i++)
       S.ch[pos-1+i]=T.ch[i]; // 插入T
     S.length+=T.length;
   }
   return OK;
 }
 
 Status Replace(HString &S,HString T,HString V)
 { // 初始条件: 串S,T和V存在,T是非空串（此函数与串的存储结构无关）
   // 操作结果: 用V替换主串S中出现的所有与T相等的不重叠的子串
   int i=1; // 从串S的第一个字符起查找串T
   if(StrEmpty(T)) // T是空串
     return ERROR;
   do
   {
     i=Index(S,T,i); // 结果i为从上一个i之后找到的子串T的位置
     if(i) // 串S中存在串T
     {
       StrDelete(S,i,StrLength(T)); // 删除该串T
       StrInsert(S,i,V); // 在原串T的位置插入串V
       i+=StrLength(V); // 在插入的串V后面继续查找串T
     }
   }while(i);
   return OK;
 }
 
 main()
 {char *p="abcaabcaaabca",*q="bca",*r="x";
  HString s,t,v;
  InitString(s);
  InitString(t);
  InitString(v);
  StrAssign(s,p);
  StrAssign(t,q);
  StrAssign(v,r);
  cout<<"串s为: ";
  StrPrint(s);
  cout<<endl;
  cout<<"串t为: ";
  StrPrint(t);
  cout<<endl;
  cout<<"串v为: ";
  StrPrint(v);
  cout<<endl;
  Replace(s,t,v);
  cout<<"把串s中和串t相同的子串用串v代替后，串s为:"<<endl;
  StrPrint(s);
  cout<<endl;
 }