清华大学数据结构串的基本操作

#include "head.h" Status StringInit(HString &s){ if(s.str){free(s.str);s.str=NULL; } s.length=0; return(0); } void StringCreate(HString &T){ int i,j; char chars[100]; char * c; scanf("%s",chars); for(i=0,c=chars;*c;++i,++c); if(!i) { T.str =NULL; T.length =0; } else { if(!(T.str =(char *)malloc((i+1)*sizeof(char)))) exit(OVERFLOW); for(j=0;j<i+1;j++) T.str[j]=chars[j]; T.length =i; } } Status StringAssign(HString &S,HString T)//串的赋值 { S.length=T.length; S.str=new char[S.length+1]; for(int i=0;i<=S.length;i++) S.str[i]=T.str[i]; return (0); } Status StringEqual(HString S,HString T)//判串相等 {int i; for (i=0;i<S.length&&i<T.length;++i) if(S.str[i]!=T.str[i]) return S.str[i]-T.str[i]; return S.length-T.length; } Status StringConcat(HString S1,HString S2,HString &T)//串连接 {//if(T.str) free(T.str); T.length=S1.length+S2.length; T.str=(char*)malloc((S1.length+S2.length)*sizeof(char)); for(int i=0;i<S1.length;i++) T.str[i]=S1.str[i]; for(int j=0;j<=S2.length;i++,j++) T.str[i]=S2.str[j]; return (0); } Status StringLength(HString S)//求串长 {return S.length;} Status SubString(HString T1,int pos,int len,HString &T2) { int i; if(pos<1||pos>T1.length ||len<0||len>T1.length -pos+1) return (1); if(!len) { T2.str =NULL; T2.length =0; } else { T2.str=(char *)malloc((len+1)*sizeof(char)); for(i=0;i<len;i++) { T2.str[i]=T1.str[pos-1+i]; T2.length =len; } T2.str[len]='\0'; } return (0); } Status Index(HString S,HString T)//子串定位 {int i,j; i=0; j=0; while(i<S.length&&j<T.length) {if(S.str[i]==T.str[j]) {i++;j++;} else {i=i-j+1;j=0;} } if(j==(T.length)) return (i-T.length+1); else return 0; } /*Status StringDelete(HString &s,HString t){ int n,i; for(n=0,i=1;i<=StringLength(s)-StringLength(t)+1;i++) if(!StringEqual(SubString(s,i,StringLength(t)),t)){ HString head,tail,s3; StringAssign(head,SubString(s,1,i-1)); StringAssign(tail,SubString(s,i+StringLength(t),StringLength(s)-i-StringLength(t)+1)); StringConcat(s3,head,tail); StringAssign(s,s3); //把head,tail连接为新串 } return (0); }*/ Status StrReplace(HString T1,HString T2,HString T3,HString &T4) { /*子串替换*/ int i=1,j,k=0; do { i=Index(T1,T2); /*利用KMP算法查找子串*/ if(k==0) /*初始化T4*/ { if(i!=1) { T4.str=(char *)malloc((i-1)*sizeof(char)); T4.length =i-1; for(j=0;j<i-1 ;j++) T4.str[j]=T1.str [j]; } else { T4.str =NULL; T4.length =0; } } else if(i!=0) { T4.str =(char *)realloc(T4.str ,(T4.length+i-1)*sizeof(char)); /*利用堆存储扩大T4的存储分配空间*/ for(j=0;j<i-1 ;j++) T4.str[j+T4.length ]=T1.str [j]; T4.length +=i-1; } if(i!=0) { StringConcat(T4,T3,T4); T1.str +=i+T2.length-1; } /*T1表示的字符串指针后移*/ k+=i; }while(i!=0); T1.length -=k; StringConcat(T4,T1,T4); return (0); }