堆分配前天的普通串比有如下优点：
（1）节省空间，用多少，分配多少！
（2）struct结构体体积小，减少了位对齐的机会，提高了效率
缺点：
（1）用了new所以记得delete
（2）结构上字符串从0开始，这个下标是很折磨人的
HString.h
#include <iostream>
enum {OK=0,WRONG=-1};
typedef int Status;
struct HString
{
char *chars;
int len;
};
void StrInit(HString &S)
{
S.chars=NULL;
S.len=0;
}
Status StrAssign(HString &S,char *T)
{
int i;
int len=strlen(T);
if(S.chars!=NULL)
delete S.chars;
S.chars=new char[len];
if(S.chars==NULL)
return WRONG;
for(i=0;i<len;i++)
S.chars[i]=T[i];
S.len=len;
return OK;
}
Status StrCopy(HString &S,HString T)
{
int i;
if(S.chars!=NULL)
delete S.chars;
S.chars=new char[T.len];
if(S.chars==NULL)
return WRONG;
S.len=T.len;
for(i=0;i<T.len;i++)
S.chars[i]=T.chars[i];
return OK;
}
bool StrEmpty(HString S)
{
return S.chars==NULL&&S.len==0;
}
int StrCompare(HString H,HString T)
{
int i=0;
while(i<H.len&&i<T.len)
if(H.chars[i]!=T.chars[i])
return H.chars[i]-T.chars[i];
else
i++;
return H.len-T.len;
}
int StrLen(HString S)
{
return S.len;
}
void StrClear(HString &S)
{
delete S.chars;
S.chars=NULL;
S.len=0;
}
Status StrConCat(HString &T,HString S1,HString S2)
{
int i;
if(T.chars!=NULL)
delete T.chars;
T.chars=new char[S1.len+S2.len];
if(T.chars==NULL)
return WRONG;
T.len=S1.len+S2.len;
for(i=0;i<S1.len;i++)
T.chars[i]=S1.chars[i];
for(i=0;i<S2.len;i++)
T.chars[i+S1.len]=S2.chars[i];
return OK;
}
Status StrSub(HString &Sub,HString S,int pos,int len)
{
if(pos<1||pos>S.len||len<0||pos+len>S.len+1)
return WRONG;
int i;
if(Sub.chars!=NULL)
delete Sub.chars;
if(len==0)
{
Sub.chars=NULL;
Sub.len=0;
}
else
{
Sub.chars=new char[len];
if(Sub.chars==NULL)
return WRONG;
for(i=0;i<len;i++)
Sub.chars[i]=S.chars[pos-1+i];
Sub.len=len;
}
return OK;
}
void GetNext(HString T,int *next)
{
int i=0,j=-1;
next[0]=-1;
while(i<T.len-1)
if(j==-1||T.chars[i]==T.chars[j])
{
i++;
j++;
next[i]=j;
}
else
j=next[j];
}
int Index(HString S,HString T,int pos)
{
int *next,i=pos-1,j=0;
next=new int[T.len];
GetNext(T,next);
while(i<S.len&&j<T.len)
if(j==-1||S.chars[i]==T.chars[j])
{
i++;
j++;
}
else
j=next[j];
if(j>=T.len)
return i-T.len+1;
else
return 0;
}
Status StrInsert(HString &S,HString T,int pos)
{
int i;
char *newchars;
if(pos<1||pos>S.len+1)
return WRONG;
newchars=new char[S.len+T.len];
if(newchars==NULL)
return WRONG;
memcpy(newchars,S.chars,sizeof(char)*S.len);
delete S.chars;
//一定注意这个循环，想想为什么从后往前拷贝呢？因为从前会错的！
for(i=S.len-1;i>=pos-1;i--)
{
newchars[i+T.len]=newchars[i];
}
for(i=0;i<T.len;i++)
{
newchars[i+pos-1]=T.chars[i];
}
S.chars=newchars;
S.len+=T.len;
return OK;
}
Status StrDelete(HString &S,int pos,int len)
{
int i;
char *newchars;
if(pos+len>S.len+1)
return WRONG;
newchars=new char[S.len-len];
memcpy(newchars,S.chars,S.len*sizeof(char));
for(i=pos-1;i<=S.len-1;i++)
newchars[i]=S.chars[i+len];
delete S.chars;
S.chars=newchars;
S.len-=len;
return OK;
}
Status Replace(HString &S,HString T,HString V)
{
int i=1;
if(S.chars==NULL)
return WRONG;
while(i)
{
i=Index(S,T,i);
if(i!=0)
{
StrDelete(S,i,T.len);
StrInsert(S,V,i);
i+=V.len;
}
}
return OK;
}
void StrPrint(HString S)
{
int i;
for(i=0;i<S.len;i++)
std::cout<<S.chars[i];
std::cout<<std::endl;
}
main.cpp
#include "HString.h"
using namespace std;
int main()
{
HString S1,S2,S;
StrInit(S1);
StrInit(S2);
StrInit(S);
StrAssign(S1,"ab");
cout<<"输出S1:";
StrPrint(S1);
StrAssign(S2,"x");
cout<<"输出S2:";
StrPrint(S2);
StrAssign(S,"ababaabbbaaabbaa");
cout<<"输出S:";
StrPrint(S);
Replace(S,S1,S2);
cout<<"把S中的S1用S2替换掉：";
StrPrint(S);
StrInsert(S1,S2,2);
cout<<"把S2插入在S1的2位置：";
StrPrint(S1);
StrDelete(S1,2,1);
cout<<"删除刚才的插入：";
StrPrint(S1);
cout<<"S2在S1的位置"<<Index(S1,S2,1)<<endl;
cout<<"串2的大小:"<<StrLen(S2)<<endl;
cout<<"对S1与S2做比较:";
if(StrCompare(S1,S2)>0)
cout<<"串1大"<<endl;
else
cout<<"串2大"<<endl;
//StrCopy(T,S);
StrConCat(S,S1,S2);
cout<<"把S1,S2连接起来到S，输出S：";
StrPrint(S);
if(StrSub(S,S1,2,5)==OK)
{
cout<<"截取S1的字符串，复制到S，输出：";
StrPrint(S);
}
return 0;
}