在C和C++語言中 ，提供一個稱之為“堆”的共享空間，可以在程序運行過程中，系統利用函數malloc( )和free( )動態地申請或釋放一塊連續空間。
由於在C和C++語言中可以用指針對數組進行訪問和操作，在串的存儲和操作上也可以充分利用上述特性。
串的堆式存儲結構類似於線性表的順序存儲結構，以一組地址連續的存儲單元存放串值字符序列，其存儲空間是在程序執行過程中動態分配的，而不是靜態分配的。
串的堆式存儲結構定義
Typedef struct { char *ch; //指針域，指向存放串值的存儲空間基址 int length; // 整型域：存放串長 }HString;
說明：在這種存儲結構下，由於串仍然是以數組存儲的字符序列表示，因此此類串的操作是先為新生成的串分配一個存儲空間，然後進行“字符序列的復制”。例如，如串插入操作StrInsert(S,pos ,T)（將串T插入到串S的第pos字符之前）的算法是，為串S重新分配大小等於串S和串T長度之和的存儲空間，然後進行將S和T串值復制到新分配存儲空間中。
串的一系列實現 www.2cto.com
/*
串的堆式存儲表示
*/
#include<stdio.h>
#include<stdlib.h>
#define OVERFLOW -2//堆溢出
#define OK 1//函數執行成功
#define ERROR -1//函數執行失敗
typedef int datatype;
typedef struct{
char* ch;//指針域，指向存放串值的存儲空間基址
int len;// 整型域：存放串長
}HString;
//初始化一個空串
datatype InitHString(HString* s)
{
s->ch=(char*)malloc(sizeof(char));
if(NULL==s->ch) return OVERFLOW;
s->ch=NULL;
s->len=0;
return OK;
}
//為串賦值
datatype assigment_string(HString* s, const char* str)
{
if(s->ch) free(s->ch);
int length=0,i;
while(str[length]!='\0')
length++;
s->ch=(char*)malloc(length*sizeof(char));
if(!s->ch) return OVERFLOW;
for(i=0;i<length;i++)
*(s->ch+i)=*(str+i);
s->len=length;
*(s->ch+s->len)='\0';
return OK;
}
//打印
void PrintString(const HString* s)
{
int i=0;
while(*(s->ch+i)!='\0')
{
printf("%c",*(s->ch+i));
i++;
}
printf("\n");
}
//求串的長度
datatype GetLength(const HString* s)
{
int len=0;
while(*(s->ch+len)!='\0')
len++;
return len;
}
//查找某個字符的位置，返回位序
datatype HSLocal(const HString* s,char c)
{
int i;
for(i=0;i<s->len;i++)
{
if(c==*(s->ch+i))
return i+1;
}
return -1;
}
//串的連接
datatype HSCat(HString* s,const HString* t)
{
int i=0;
char* temp=(char*)malloc((s->len+t->len)*sizeof(char));
if(!temp) return OVERFLOW;
for(i=0;i<s->len;i++)
*(temp+i)=*(s->ch+i);
free(s->ch);//釋放防止內存洩漏
for(i=0;i<t->len;i++)
*(temp+i+s->len)=*(t->ch+i);
s->len+=t->len;
s->ch=temp;//使s->ch重新指向temp
*(s->ch+s->len)='\0';
return OK;
}
datatype HSCopy(HString* to, const HString* from)
{
//如果目標串不為空則清空
[cpp] view plaincopy
if(to->ch)
{
free(to->ch);
to->ch=NULL;
to->len=0;
}
int i=0;
to->len=from->len;
to->ch=(char*)malloc(from->len*sizeof(char));
if(!to->ch) return OVERFLOW;
for(i=0;i<from->len;i++)
*(to->ch+i)=*(from->ch+i);
*( to->ch+to->len)='\0';
return OK;
}
//在串s的pos位置處插入串t
datatype HSInsert(HString* s,const HString *t,int pos)
{
if(pos<0 || pos>s->len)
return ERROR;
else{
s->ch=(char*)realloc(s->ch,(s->len+t->len)*sizeof(char));
int i,j=1;
//後移
for(i=s->len+t->len-1;i>=pos+t->len;i--)
{
*(s->ch+i)=*(s->ch+(s->len-j));
j++;
}
//insert
for(i=0;i<t->len;i++)
*(s->ch+i+pos)=*(t->ch+i);
}
s->len+=t->len;
*(s->ch+s->len)='\0';
return OK;
}
//在串s的index位置刪除長度為x個字符
datatype HSdel(HString* s,int index,int x)
{
// index value invalid
if(index<0 || index>s->len) return ERROR;
// if x+index> s->len
if((index+x)>=s->len)
s->len=index;
else
{
int i;
for(i=index;i<s->len;i++)
{
*(s->ch+i)=*(s->ch+i+x);
}
s->len-=x;
}
*(s->ch+s->len)='\0';
return OK;
}
//串比較
datatype HScomp(const HString* s1,const HString* s2)
{
int i=0;
for(i=0;i<s1->len && i<s2->len;i++)
{
if(*(s1->ch+i)!=*(s2->ch+i))
return *(s1->ch+i)-*(s2->ch+i);
}
return 0;//equal
}
/*串的提取
* 在串s中的index開始長度為length的子串提取到temp串中
* */
datatype HSsub(HString* temp,const HString* s,int index,int length)
{
if(index<0 || index>s->len) return ERROR;
if(length > s->len) length=s->len-index;
temp->len=length;
temp->ch=(char*)malloc(length*sizeof(char));
if(!temp->ch) return OVERFLOW;
int i;
for(i=0;i<length;i++)
{
*(temp->ch+i)=*(s->ch+index+i);
}
*(temp->ch+temp->len)='\0';
return OK;
}
//串的替換，把串s的從index開始長度為length的子串，用串t替換掉
datatype HSReplace(HString* s,int index,int length,const HString*t)
{
if(index<0 || index>s->len )
return ERROR;
//如果length大於串s的長度就替換掉從index後的所有字符
if(length>s->len)
length=s->len;
int i;
for(i=0;i<length;i++)
{
*(s->ch+i+index)=*(t->ch+i);
}
*(s->ch+s->len)='\0';
return OK;
}
int main(int argc ,char** argv)
{
// bulid string
HString S;
InitHString(&S);
assigment_string(&S,"hello world!");
PrintString(&S);
printf("length=%d\n",GetLength(&S));
#if 0
//localion
int local=HSLocal(&S,'w');
printf("local=%d\n",local);
free(S.ch);
#endif
#if 0
// insert
HString S1;
InitHString(&S1);
assigment_string(&S1,"****");
HSInsert(&S,&S1,2);
PrintString(&S);
printf("length=%d\n",GetLength(&S));
free(S1.ch);
#endif
#if 0
// copy
HString S2;
InitHString(&S2);
assigment_string(&S2,"beijing");
HSCopy(&S,&S2);
PrintString(&S);
printf("length=%d\n",GetLength(&S));
free(S.ch);
free(S2.ch);
#endif
#if 0
//cat
HString S3;
InitHString(&S3);
assigment_string(&S3,"////");
HSCat(&S,&S3);
PrintString(&S);
printf("length=%d\n",GetLength(&S));
free(S3.ch);
free(S.ch);
#endif
#if 0
// delete
HSdel(&S,2,5);
PrintString(&S);
printf("length=%d\n",GetLength(&S));
free(S.ch);
#endif
#if 0
// complar
HString S4;
InitHString(&S4);
assigment_string(&S4,"hello world!");
datatype ret=HScomp(&S,&S4);
if(ret>0)
printf("S>S4\n");
else if(ret<0)
printf("S<S4\n");
else
printf("S=S4\n");
free(S4.ch);
free(S.ch);
#endif
#if 0
// sub
HString S5;
HSsub(&S5,&S,2,5);
PrintString(&S5);
printf("length=%d\n",GetLength(&S5));
free(S.ch);
free(S5.ch);
#endif
#if 1
// replace
HString S6;
InitHString(&S6);
assigment_string(&S6,"************************************");
HSReplace(&S,2,50,&S6);
PrintString(&S);
printf("length=%d\n",GetLength(&S));
free(S6.ch);
free(S.ch);
#endif
// free(S.ch);
return 0;
}
