【串】基本操作和实现

#include<stdio.h>
#include<stdlib.h>
#define MAXLEN 255
typedef struct{
  char ch[MAXLEN];
  int length; 
}SString;
bool StrAssign(SString &T,char* chars);
bool StrCopy(SString &T,SString S);
bool StrEmpty(SString S);
int Strcompare(SString S, SString T);
int Index(SString S,SString T);
int Index_KMP(SString S, SString T);
int StrLength(char * ch);
bool SubString(SString &Sub, SString S, int pos, int len);
bool Concat(SString &T,SString S1,SString S2);
void StrPrint(SString T);
void get_next(SString T, int next[]);
void get_nextval(SString T, int nextval[],int next[]);
int main(){
  SString T,S1,S2,S,Sub;
  int pos;
  char chars[255];
  scanf("%s",chars);
  if(StrAssign(T,chars))
    StrPrint(T);
  else
    printf("字符串长度过长！\n");
  printf("连接字符串，请输入S1，S2：\n\n"); 
  scanf("%s",chars);
  StrAssign(S1,chars); 
  scanf("%s",chars);
  StrAssign(S2,chars);
  if(Concat(S,S1,S2))
    printf("连接成功！未截断S2\n");
  else
    printf("连接成功！S2截断!\n");
  if(S.ch)
    StrPrint(S);
  printf("\n");
  printf("求子串\n\n");  
  SubString(Sub,T,3,4);
  StrPrint(Sub);
  printf("\n");
  printf("模式串匹配\n\n");
  pos = Index_KMP(T,S2);
  if(pos > 0)
    printf("已找到！\npos=%d\n\n",pos);
  else printf("未找到！\n\n");
  return 0;
}
bool StrAssign(SString &T,char* chars){
  int i;
  if(StrLength(chars) > MAXLEN){
    printf("字符串长度过长！\n");
    return false;
  } 
  T.length = StrLength(chars);
  for(i=1;i<=T.length;i++){
    T.ch[i] = *(chars+i-1);
  } 
  return true;
}
bool StrCopy(SString &T,SString S){
  for(int i = 1;i<S.length;i++){
    T.ch[i] = S.ch[i];
  }
  return true;
}
bool StrEmpty(SString S){
  if(S.length == 0) return true;
  else return false;
}
int Strcompare(SString S, SString T){ 
  for(int i = 1;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(char * ch){
  int len = 0;
  while(ch[len]) len++;
  return len;
}
void ClearString(SString &T){
  T.length = 0;
}
bool Concat(SString &T,SString S1,SString S2){
  // 若未截断，返回true，否则返回false 
  int i,j;
  if(S1.length+S2.length <= MAXLEN){
    // 未截断
    for(i = 1;i <= S1.length;i++)
      T.ch[i] = S1.ch[i];
    for(j = 1;j <= S2.length;j++,i++)
      T.ch[i] = S2.ch[j];     
    T.length = S1.length+S2.length+1;
    return true;
  }else{
    // 截断S2
    for(i = 1;i <= S1.length;i++)
      T.ch[i] = S1.ch[i];
    for(j = 1;i <= MAXLEN;i++,j++) 
      T.ch[i] = S2.ch[j];
    T.length = MAXLEN+1;
    return false;
  }
}
bool SubString(SString &Sub, SString S, int pos, int len){
  // 边界判断
  if(pos<1 || pos>S.length || len<0 || len>S.length-pos+1){
    printf("下标越界！\n");
    return false;
  } 
  for(int i = 1;i <= len;i++){
    Sub.ch[i] = S.ch[pos+i-1];
  }
  Sub.length = len;
  return true;
}
int Index(SString S,SString T){
  // 返回子串T在主串S中第pos个字符之后的位置。若不存在,则函数返回值为0。
  int i = 1;  // 主串下标 
  int j = 1;    // 模式串下标 
  while(i <= S.length && j <= T.length){
    if(S.ch[i] == T.ch[j]){
      i++; j++;   // 如果相等则继续 
    }else{
      i = i-j+2;  // i退回上次匹配的下一位 
      j = 1;      // j退回子串的首位 
    }   
  } 
  if(j>T.length) return i-T.length; // 如果找到 ，返回下标 
  else return 0;
}
int Index_KMP(SString S, SString T){
  int i = 1, j = 1;
  int next[T.length+1];
  int nextval[T.length+1];
  get_next(T,next);
  get_nextval(T, nextval,next);
  while(i <= S.length && j <= T.length){
    if(j == 0 || S.ch[i] == T.ch[j]){
      i++; j++;
    }else{
      j = nextval[j];
    }
  } 
  if(j > T.length) return i-T.length;
  else return 0;
}
void StrPrint(SString T){
  for(int i = 1;i <= T.length;i++){
    printf("%c",T.ch[i]);
  }
  printf("\n");
}
void get_next(SString T, int next[]){
  int i = 1, j = 0;
  next[1] = 0;
  while(i < T.length){
    if(j == 0 || T.ch[i] == T.ch[j]){
      i++; j++;
      next[i] = j;
    }else{
      j = next[j];
    }
  }
}
void get_nextval(SString T, int nextval[],int next[]){
  nextval[1] = 0;
  for(int j = 2;j<=T.length;j++){
    if(T.ch[next[j]] == T.ch[j]){
      nextval[j] = nextval[next[j]];
    } else{
      nextval[j] = next[j];
    }
  }
}