// bo4-2.cpp 串采用堆分配存儲結構(由c4-2.h定義)的基本操作(15個)
 // 包括算法4.1、4.4
 Status StrAssign(HString &T,char *chars)
 { // 生成一個其值等于串常量chars的串T
   int i,j;
   if(T.ch)
     free(T.ch); // 釋放T原有空間
   i=strlen(chars); // 求chars的長度i
   if(!i)
   { // chars的長度為0
     T.ch=NULL;
     T.length=0;
   }
   else
   { // chars的長度不為0
     T.ch=(char*)malloc(i*sizeof(char)); // 分配串空間
     if(!T.ch) // 分配串空間失敗
       exit(OVERFLOW);
     for(j=0;j<i;j++) // 拷貝串
       T.ch[j]=chars[j];
     T.length=i;
   }
   return OK;
 }

 Status StrCopy(HString &T,HString S)
 { // 初始條件: 串S存在。操作結果: 由串S復制得串T
   int i;
   if(T.ch)
     free(T.ch); // 釋放T原有空間
   T.ch=(char*)malloc(S.length*sizeof(char)); // 分配串空間
   if(!T.ch) // 分配串空間失敗
     exit(OVERFLOW);
   for(i=0;i<S.length;i++) // 拷貝串
     T.ch[i]=S.ch[i];
   T.length=S.length;
   return OK;
 }

 Status StrEmpty(HString S)
 { // 初始條件: 串S存在。操作結果: 若S為空串,則返回TRUE,否則返回FALSE
   if(S.length==0&&S.ch==NULL)
     return TRUE;
   else
     return FALSE;
 }

 int StrCompare(HString S,HString T)
 { // 若S>T,則返回值>0;若S=T,則返回值=0;若S<T,則返回值<0
   int i;
   for(i=0;i<S.length&&i<T.length;++i)
     if(S.ch[i]!=T.ch[i])
       return S.ch[i]-T.ch[i];
   return S.length-T.length;
 }

 int StrLength(HString S)
 { // 返回S的元素個數,稱為串的長度
   return S.length;
 }

 Status ClearString(HString &S)
 { // 將S清為空串
   if(S.ch)
   {
     free(S.ch);
     S.ch=NULL;
   }
   S.length=0;
   return OK;
 }

 Status Concat(HString &T,HString S1,HString S2)
 { // 用T返回由S1和S2聯接而成的新串
   int i;
   if(T.ch)
     free(T.ch); // 釋放舊空間
   T.length=S1.length+S2.length;
   T.ch=(char *)malloc(T.length*sizeof(char));
   if(!T.ch)
     exit(OVERFLOW);
   for(i=0;i<S1.length;i++)
     T.ch[i]=S1.ch[i];
   for(i=0;i<S2.length;i++)
     T.ch[S1.length+i]=S2.ch[i];
   return OK;
 }

 Status SubString(HString &Sub, HString S,int pos,int len)
 { // 用Sub返回串S的第pos個字符起長度為len的子串。
   // 其中,1≤pos≤StrLength(S)且0≤len≤StrLength(S)-pos+1
   int i;
   if(pos<1||pos>S.length||len<0||len>S.length-pos+1)
     return ERROR;
   if(Sub.ch)
     free(Sub.ch); // 釋放舊空間
   if(!len) // 空子串
   {
     Sub.ch=NULL;
     Sub.length=0;
   }
   else
   { // 完整子串
     Sub.ch=(char*)malloc(len*sizeof(char));
     if(!Sub.ch)
       exit(OVERFLOW);
     for(i=0;i<=len-1;i++)
       Sub.ch[i]=S.ch[pos-1+i];
     Sub.length=len;
   }
   return OK;
 }

 void InitString(HString &T)
 { // 初始化(產生空串)字符串T。另加
   T.length=0;
   T.ch=NULL;
 }

 int Index(HString S,HString T,int pos) // 算法4.1
 { // T為非空串。若主串S中第pos個字符之后存在與T相等的子串,
   // 則返回第一個這樣的子串在S中的位置,否則返回0
   int n,m,i;
   HString sub;
   InitString(sub);
   if(pos>0)
   {
     n=StrLength(S);
     m=StrLength(T);
     i=pos;
     while(i<=n-m+1)
     {
       SubString(sub,S,i,m);
       if(StrCompare(sub,T)!=0)
	 ++i;
       else
         return i;
     }
   }
   return 0;
  }

 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 StrDelete(HString &S,int pos,int len)
 { // 從串S中刪除第pos個字符起長度為len的子串
   int i;
   if(S.length<pos+len-1)
     exit(ERROR);
   for(i=pos-1;i<=S.length-len;i++)
     S.ch[i]=S.ch[i+len];
   S.length-=len;
   S.ch=(char*)realloc(S.ch,S.length*sizeof(char));
   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;
 }

 void DestroyString()
 { // 堆分配類型的字符串無法銷毀
 }

 void StrPrint(HString T)
 { // 輸出T字符串。另加
   int i;
   for(i=0;i<T.length;i++)
     printf("%c",T.ch[i]);
   printf("\n");
 }