4.2.2 堆分配存储表示
这种存储表示的特点是，仍以一组地址连续的存储单元存放串值字符序列，但它们的存储空间是在程序执行过程中动态分配而得。在C语言中，存在一个称之为“堆”的自由存储区，并由C语言的动态分配函数malloc()和free()来管理。利用函数malloc()为每个新产生的串分配一块实际串长所需的存储空间，若分配成功，则返回一个指向起始地址的指针，作为串的基址，同时，为了以后处理方便，约定串长也作为存储结构的一部分。
//—————串的堆分配存储表示—————
Typedef struet {
char *ch； //若是非空串，则按串长分配存储区，否则ch为NULL
int length； //串长度
} HString；
这种存储结构表示时的串操作仍是基于“字符序列的复制”进行的。[例如]，串复制操作 StrCopy(&T，S)的实现算法是，若串T已存在，则先释放串T所占空间，当串S不空时，首先为串T分配大小和串S长度相等的
存储空间，然后将串S的值复制到串T中；[又如]串插入操作StrInsert(&S，pos，T)的实现算法是，为串S重新分配大小等于串S和串T长度之和的存储空间，然后进行串值复制。
Status StrInsert (Hstring &S，int pos， Hstring T){
// 1≤pos≤StrLength(S)+1。在串S的第pos个字符之前插入串T。
if(pos<1 || pos>S.length+1) return ERROR； // pos不合法
if(T.length){ //T非空，则重新分配空间，插入T
if(!(S.ch=(char*)realloc(S.ch，(S.length+T.length) *sizeof(char))) exit(OVERFLOW)；
for( i=S.length-1；i>=pos-1；--i )
S.ch[i+T.length]=S.ch[i]；//为插入T而腾出位置
S.ch[pos-1.. pos+T.length-2] =T.ch[0.. T.length-1]；//插入T
S.length + = T.length；
}
return OK
} // StrInsert算法
以上两种存储表示通常为高级程序设计语言所采用。由于堆分配存储结构的串既有顺序存储结构的特点，处理方便，操作中对串长又没有任何限制，更显灵活，因此在串处理的应用程序中也常被选用。
以下所示为只含最小操作子集的HString串类型的模块说明（ADT String的表示与实现)
//———串的堆分配存储表示———
typedef struct {
char * ch； //若是非空串，则按串长分配存储区，否则ch为NULL
int length； //串长度
}HString；
//—————基本操作的函数原型说明————
Status StrAssign (Hstring &T， char *chars)；
int StrLength (Hstring S)；
int StrCompare (Hstring S，Hstring T)；
Status ClearString(Hstring &S)；
Status Concat (Hstring &T，Hstring S1，Hstring S2)；
HString SubString ( Hstring S，int pos，int len)；
//—————基本操作的
算法描述—————
Status StrAssign( Hstring &T，char *chars){ //生成一个其值等于串常量chars的串T
if(T.ch) free(T.ch)； //释放T原有空间
for(i=0，c=chars；c；++i，++c)； //求chars的长度i
if(!i ){T.ch= NULL； T.length = 0；}
else {
if (!(T.ch = (char *)malloc(i*sizeof(char)))) exit(OVERFLOW);
T.ch[0..i-1]= chars[0..i-1]; T.length = i;
}
return OK;
}//StrAssign
int StrLength (HString S){ //返回s的元素个数 ，称为串的长度。
return S.length；
} //StrLength
int StrCompare(HString S，HString T){ //若S>T，则返回值>0；若S=T，则返回值=0；若S<T，则返回值<0。
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；
}// StrCompare
Status ClearString (HString &S){ //将s清为空串。
if( S.ch ) {
free(S.ch)； S.ch=NULL；
}
S.length = 0；
return OK；
}//ClearString
Status Concat (Hstring &T，Hstring Sl，HStringS2){ //用T返回s1和s2联接成的新串。
if(T.ch) free(T.ch)； //释放旧空间
if(!(T.ch=(char*)malloc((S1.length+S2.length) *sizeof(char)))) exit(OVERFLOW)；
T.ch[0.. S1.length -1]=S1.ch[0..S1.length - 1]；
T.length = S1.length+S2.length；
T.ch[S1.length..T.length -1]=S2.ch[0..S2.length -1]；
return OK；
} // Concat
Status SubString (Hstring &Sub，Hstring S， int pos，int len){
//用Sub返回串s的第pos个字符起长度为len的子串。
//其中，1≤pos≤StrLength(S)且0≤len≤StrLength(S)-pos-1
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(len* sizeof(char));
Sub.ch[0..len-1]=S[pos-1..pos+len-2];
Sub.length=len；
}
return OK 字符串常量在内存中的存放位置由系统自动安排吗
}//SubString

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。