4.26.c

数据结构习题及答案

4.26③ 采用教科书4.2.2节中所定义的堆分配存储
表示。试写一算法，实现堆存储结构的串的插入操
作StrInsert(&S,pos,T)。

要求实现以下函数：
Status StrInsert(HString &S, int pos, HString T); // 算法4.4
/* 1<=pos<=StrLength(S)+1。在串S的第pos个字符之前插入串T */

堆串HString的类型定义：
typedef struct {
    char *ch;     // 若是非空串,则按串长分配存储区,否则ch为NULL
    int   length; // 串长度
} HString;
Status StrInsert(HString &S, int pos, HString T)  // 算法4.4
/* 1<=pos<=StrLength(S)+1。在串S的第pos个字符之前插入串T */
{  
  int i;
  if(pos<1||pos>S.length+1) return ERROR;
  if(T.length)
     {
       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];                          //插入点后面的元素后移
       for(i=0;i<T.length;i++) S.ch[pos+i-1]=T.ch[i];                                    //插入串T
       S.length+=T.length;
         }
  return OK;

}