#include<stdio.h>
#include<stdlib.h>
/*-----串的堆分配存储表示-----*/
typedef struct{
 char *ch;
 int length;
}  HString;
#define TRUE   1
#define FALSE  0
#define OK     1
#define ERROR  0
#define INFEASIBLE  -1
#define OVERFLOW    -2
typedef  int  Status;

/*-----基本操作的函数原型说明-----*/
Status Assign(HString *,char *);
/*生成一个其值等于chars的串T。*/
Status StrCopy(HString *, HString *);
/*由串S复制得串T。*/
Status StrEmpty(HString *);
/*若串S为空串，则返回TRUE，否则返回FALSE。*/
int StrCompare(HString *, HString *) ;
/*若S>T,则返回值>0；若S<T，则返回值=0；若S<T,则返回值<0。*/
int StrLength(HString *) ;
/*返回S的元素的个数，称为串的长度。*/
Status ClearString(HString *);
/*将S清空为空串。*/
HString Concat(HString  *, HString *, HString *) ;
/*用T返回由S1和S2联接而成的新串。*/
HString SubString(HString  *, HString *,int ,int ) ;
/*用Sub返回串的第pos个字符起长度为len的子串。*/
int Index(HString * , HString *,int ) ;
/*若主串S中存在和串T相同的子串，则返回它在主串S中的第pos个字符之后第一次出现的位置，否则函数值为0。*/
Status Replace(HString  *, HString *, HString *) ;
/*用V替换主串S中出现的所有与T相等的不重叠的子串。*/
Status StrInsert(HString  *,int , HString *) ;
/*在串S中的第pos 个字符之前插入串T。*/
Status StrDelete(HString  *,int ,int );
/*从串S中删除第pos 个字符起长度为len的子串。*/
Status DestroyString(HString  *);
/*串S被销毁。*/
main()
{
    int k;char ch;HString *T,*S,*S1,*S2,*V,*Sub;  char  a[30],b[30],c[30];  
 do{
     printf("            String basic operation demo\n");
     printf("\n**********************************************************");
     printf("\n1. Generate a string:");
     printf("\n2. Copy a string to another:");
     printf("\n3. Determine whether a string is empty:");
  printf("\n4. Compare a string to another:");
     printf("\n5. Caculate the length of a string ");
     printf("\n6. Clear a string:");
     printf("\n7. Concat a String to another:");
     printf("\n8. Return the substring of the string S:");
     printf("\n9. Return the location of the substring's first appearing:");
     printf("\n10.Replace a string  with another:");
     printf("\n11.Insert a string before pos:");
     printf("\n12.Delete a substrig whose length is len:");
     printf("\n13.Destroy string :");
     printf("\n0. exit.");
     printf("\n**********************************************************\n");
     scanf("%d",&k);
 switch (k)
 {
     case 1:
         {    printf("Input string T:\n");
             gets(a);
             Assign(T,a);
             printf("The string you generate is :    T=%s",T->ch);
             getchar();
             break;}     
     case 2:
         {   
             
             printf("Input string T:");
             gets(a);
             Assign(T,a);
             printf("The string you generate is :    T=%s",T->ch);
             printf("Input string S:");
            gets(b);
             Assign(S,b);
             printf("The string you generate is :    S=%s",T->ch);
             StrCopy(T,S);
             getchar();
                      break;}         
     case 3:
         {    printf("Input string T:\n");
             gets(a);
              Assign(T,a);
             StrEmpty(T);
             getchar();
           break;}         
     case 4:
         {        printf("Input string S:");
             gets(a);
             Assign(T,a);
             printf("The string you generate is :    S=%s",T->ch);
             printf("Input string T:");
             gets(b);
             Assign(S,b);
             printf("The string you generate is :    T=%s",T->ch);
             StrCompare(S,T);
             getchar();        
             break;}         
     case 5:
        {       int i;
            printf("Input string T:\n");
             gets(a);
             Assign(T,a);
             printf("The string you generate is :    T=%s",T->ch);
             i=StrLength(T);
             printf("the length of the string T is:    %d",i);
             getchar();
                      break;    }
     case 6:
         {
             printf("Input string T:\n");
            gets(a);
             Assign(T,a);
             printf("The string you generate is :    T=%s",T->ch);
             ClearString(T);
             break;}
     /*case 7:
         {
             
             printf("Input string T:");
             gets(a);
             Assign(T,a);
             printf("The string you generate is :    T=%s",T->ch);
             printf("Input string S:");
             gets(b);
             Assign(S1,b);
             printf("The string you generate is :    S1=%s",T->ch);
             printf("Input string S:");
             gets(c);
             Assign(S1,c);
             printf("The string you generate is :    S2=%s",T->ch);
             Concat(T,S1,S2);
             printf("after the connection ,the string is T=%s",T->ch);
             break;}
     case 8:
         { int pos,len;
             printf("Input string T:\n");
             gets(a);
              Assign(S,a);
             printf("The string you generate is:    S=%s",S-ch);
                 printf("Input the value of pos:");
             scanf("%d",&pos);
                 printf("Input the value of len:");
             scanf("%d",&len);
             Substring(Sub,S,pos,len);
             printf("Sub=%s",Sub->ch);
             break;}
     case 9:
        {int i;  int pos;
             printf("Input string S:");
             gets(a);
             Assign(T,a);
             printf("The string you generate is :    S=%s",T->ch);
             printf("Input string T:");
             gets(b);
             Assign(S,b);
             printf("The string you generate is :    T=%s",T->ch);
             i=Index(S,T,pos);
             printf("The location of the substring's first appearing is:        %d",i);             
             break;}
     case 10:
         {        printf("Input string S:");
             gets(a);
             Assign(S,a);
             printf("The string you generate is :    S=%s",S->ch);
             printf("Input string T:");
             gets(b);
             Assign(T,b);
             printf("The string you generate is :    T=%s",T->ch);
             printf("Input string V:");
             gets(c);
             Assign(V,k);
             printf("The string you generate is :    V=%s",V->ch);
             Replace(S,T,V);
             printf("The string which has been replaced is:    S=%s",S->ch);
             break;}
     case 11:
         {
             int pos;
             printf("Input string S:");
             gets(a);
             Assign(T,a);
             printf("The string you generate is :    S=%s",T->ch);
             printf("Input string T:");
             gets(b);
             Assign(S,b);
             printf("The string you generate is :    T=%s",T->ch);
             printf("Input the value of pos:");
             scanf("%d",&pos);
             StrInsert(S,pos,T);
             printf("The new string is:    S=%s",S->ch);
             break;}
     case 12:
        {       int pos,len;
            printf("Input string S:\n");
             gets(a);
             Assign(S,a);
             printf("The string you generate is :    S=%s",S->ch);
             printf("Input the value of pos:");
             scanf("%d",&pos);
                 printf("Input the value of len:");
             scanf("%d",&len);
             StrDelete(S,pos,len);
             break;}
     case 13:
         {    printf("Input string S:\n");
             gets(a);
             Assign(S,a);
             printf("The string you generate is :    S=%s",S->ch);
            DestroyString(S);
             break;}
          case 0: exit(0);*/
     default:printf("unknown operator\n");
         break;
     }
 }while(k>=0&&k<=13);  
 printf("\nbye-bye");
 printf("\npress any key to continue...");
 ch=getchar();
}
    /*生成一个其值等于chars的串T。*/
Status StrAssgn(HString  *T,char *chars)
{
int i,j;char *c;
if(T->ch)  free(T->ch);  /*释放T原有空间*/
for(i=0,c=chars;c;i++,c++)
  if(!i)
  {
   T->ch=NULL;
   T->length=0;
  }
  else{
   if(!(T->ch=(char *)malloc (i*sizeof(char))))
     exit(OVERFLOW);
   for(j=0;j<i;j++)
     T->ch[j]=chars[j];
   T->length=i;
  }
  return OK;
}/*Assign*/
/*由串S复制得串T。*/
Status StrCopy(HString   *T, HString *S)
{
int i;
  if(T->ch)  free(T->ch);
      if(!(T->ch = (char *)malloc (S->length*sizeof(char))))
     exit(OVERFLOW);
    for(i=0;i<S->length;i++)
          T->ch[i]=S->ch[i];
          return OK;
}/*StrCopy*/
/*若串S为空串，则返回TRUE，否则返回FALSE。*/
Status StrEmpty(HString *S)
{
if(S->ch==NULL)
return TRUE;
}
/*若S>T,则返回值>0；若S<T，则返回值=0；若S<T,则返回值<0*/
int StrCompare(HString *S, HString *T)
{
 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;
}/*StrCompare*/
/*返回S的元素的个数，称为串的长度。*/
int     StrLength(HString *S)
{
return S->length;
}/*StrLength*/
/*将S清空为空串*/
Status ClearString(HString   *S)
{
 if(S->ch)
 {
  free(S->ch);
 }
 S->length=0;
 return OK;
}/*ClearString*/
/*用T返回由S1和S2联接而成的新串。*/
Status Concat0(HString  *T, HString *S1, HString *S2)
{  int i,j;
  if(T->ch)  free(T->ch);
  if(!(T->ch=(char *)malloc((S1->length+S2->length)*sizeof(char))))
    exit(OVERFLOW);
  for (i=0;i<S1->length;i++)
    T->ch[i]=S1->ch[i];
    T->length=S1->length+S2->length;
  for (j=0;j<S2->length;j++)
    T->ch[j+S1->length]=S2->ch[j];
  
  return OK;
}
/*用Sub返回串的第pos个字符起长度为len的子串。*/
Status SubString0(HString  *Sub, HString *S,int pos,int len)
{ 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));
   for (i=0;i<=len-1;i++)
   Sub->ch[i]=S->ch[i+pos-1];
   Sub->length = len;
  }
  return OK;
}/*SubString*/
/*若主串S中存在和串T相同的子串，则返回它在主串S中的第pos个字符之后第一次出现的位置，否则函数值为0。*/
int Index(HString *S, HString *T,int pos)
{
     int i=pos;int j=1;
    while (i<=S->length &&j<=T->length)
     {
          if( S->ch[i]==T->ch[j]) {++i;++j;}
              else {i=i-j+2;j=1;}
        }
        if(j>T->length)  return i-T->length;
            else  return 0;
}/*index*/
/*用V替换主串S中出现的所有与T相等的不重叠的子串。*/
Status Replace(HString  *S, HString *T, HString *V)
{
 int pos;
 pos = Index (S,T,1);
 StrDelete (S,pos,T->length);
 StrInsert(S,pos,V);
 Replace (S,T,V);
}
/*在串S中的第pos 个字符之前插入串T。*/
Status StrInsert(HString  *S,int pos, HString *T)
{
int i;
    if(pos < 1|| pos >S->length+1) return ERROR;
        if (T->length)
            {
                 if(!(S->ch = (char *)realloc (S->ch,(S->length+T->length)*sizeof (char))))
                    exit (OVERFLOW);
            for (i=S->length-1;i>=pos -1;--i)
               S->ch[i+T->length] = S->ch[i];
              for (i=pos ;i<=pos +T->length-1;i++)
               S->ch[i+pos - 1]=T->ch[i];    
                }
}
/*从串S中删除第pos 个字符起长度为len的子串。*/
Status StrDelete(HString  *S,int pos,int len)
{ int i;
 if(pos<1||pos>S->length-len+1||S->length<len)
       return ERROR;
     for (i=pos+len-1;i<S->length;i++)
        S->ch[i-len]=S->ch[i];
          for (i=(S->length-len);i<S->length;i++)
           free (S->ch);
}
/*串S被销毁。*/
Status DestroyString(HString  *S)
{
    if(S->ch) {free(S->ch);S->ch=NULL;}
        return OK;
}