版权声明：本文为博主原创文章。未经博主同意不得转载。
https://blog.csdn.net/RowandJJ/article/details/24291281
示意图：
形态：
插入：
删除：
实现：
/***********************************************
串的堆分配存储表示
by Rowandjj
2014/4/21
***********************************************/
#include<IOSTREAM>
using namespace std;
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OVERFLOW 0
typedef int Status;
//---------串的堆式存储结构-------------------
typedef struct _HSTRING_
{
char *ch;//存储区
int length;//串长
}HString;
/*操作定义*/
Status StrAssign(HString *T,char *chars);//生成一个其值等于串常量chars的串T
Status StrCopy(HString *T,HString S);
Status StrEmpty(HString S);
int StrCompare(HString S,HString T);
int StrLength(HString S);
Status ClearString(HString *S);
Status Concat(HString *T,HString S1,HString S2);
Status SubString(HString *Sub, HString S,int pos,int len);//用Sub返回串S的第pos个字符起长度为len的子串。当中,1≤pos≤StrLength(S)且0≤len≤StrLength(S)-pos+1
void InitString(HString *T);
int Index(HString S,HString T,int pos);//若主串S中第pos个字符之后存在与T相等的子串,则返回第一个这种子串在S中的位置,否则返回0
Status StrInsert(HString *S,int pos,HString T);
Status StrDelete(HString *S,int pos,int len);
void StrPrint(HString T);
/*详细实现*/
Status StrAssign(HString *T,char *chars)
{
int i,j;
if(!(*T).ch)
{
free((*T).ch);
}
i = strlen(chars);
if(!i)//长度为0
{
(*T).ch = NULL;
(*T).length = 0;
}else
{
(*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)
{
int i;
if((*T).ch)
{
free((*T).ch);
}
(*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)
{
if(!S.length && S.ch==NULL)
{
return TRUE;
}
else
{
return FALSE;
}
}
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;
}
int StrLength(HString S)
{
return S.length;
}
Status ClearString(HString *S)
{
if((*S).ch)
{
free((*S).ch);
(*S).ch = NULL;
}
(*S).length = 0;
return OK;
}
Status Concat(HString *T,HString S1,HString S2)
{
int i;
if((*T).ch)
{
free((*T).ch);
}
(*T).length = S1.length+S2.length;
(*T).ch = (char *)malloc(sizeof(char)*(*T).length);
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[i+S1.length] = S2.ch[i];
}
return OK;
}
Status SubString(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(sizeof(char)*len);
if(!(*Sub).ch)
{
exit(-1);
}
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).ch = NULL;
(*T).length = 0;
}
int Index(HString S,HString T,int pos)
{
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)
{
int i;
if(pos<1 || pos>(*S).length+1)
{
return ERROR;
}
if(T.length)
{
(*S).ch = (char *)realloc((*S).ch,sizeof(char)*(T.length+(*S).length));
if(!(*S).ch)
{
exit(-1);
}
for(i = (*S).length-1;i>=pos-1;i--)
{
(*S).ch[i+T.length] = (*S).ch[i];
}
for(i = 0; i < T.length; i++)
{
(*S).ch[pos-1+i] = T.ch[i];
}
(*S).length += T.length;
}
return OK;
}
Status StrDelete(HString *S,int pos,int len)
{
int i;
if((*S).length < pos+len-1)
{
return 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,sizeof(char)*(*S).length);
return OK;
}
void StrPrint(HString T)
{
for(int i = 0; i < T.length; i++)
{
cout<<T.ch[i]<<" ";
}
cout<<endl;
}