串

串

定长顺序串

• 结构定义

  #define MAXLEN 256
  
  typedef char CHAR;
  
  typedef struct {
      CHAR ch[MAXLEN];
      int len;
  } String, *StringPtr;

• 插入

  bool StrInsert(StringPtr s, int pos, StringPtr t) {
      if (pos < 0 || pos > s->len || t->len == 0)
          return false;
  
      int mstart, mend, cend;
  
      if (s->len + t->len <= MAXLEN) {
          mstart = s->len + t->len - 1;
          mend = pos + t->len;
          cend = mend;
      } else if (pos + t->len <= MAXLEN) {
          mstart = MAXLEN - 1;
          mend = pos + t->len;
          cend = mend;
      } else {
          mstart = -1;
          mend = 0;
          cend = MAXLEN - 1;
      }
  
      int i;
      for (i = mstart; i >= mend; --i)
          s->ch[i] = s->ch[i - t->len];
      for (i = pos; i < cend; ++i)
          s->ch[i] = t->ch[i - pos];
  
      s->len += t->len;
  
      return true;
  }

• 删除

  int StrDelete(StringPtr *s, int pos, int len) {
      int i;
  	if( pos<0|lpos>(s->len-len))  return(0);	/*删除参数不合法*/
      for(i=pos+len;i<s->len;i++)	/*从pos+len开始至串尾依次向前移动,实现删除len个字符*/
          s->ch[i - len] = s->ch[i];
      s->len -= len;	/*s串长减len*/
  	return true;
  }

• Brute-Force算法（简单模式匹配算法）

  /*求从主串s的下标pos起，串t第一次出现的位置，成功返回位置序号，不成功返回-1*/
  int StrIndex(StringPtr s, int pos, StringPtr t) {
      int i, j, start;
  
      start = pos;
      i = start;
      j = 0;
      while (i < s->len && j < t->len) {
          if (s->ch[i] == t->ch[j]) {
              ++i;
              ++j;
          } else {
              ++start;
              i = start;
              j = 0;
          }
      }
  
      return j >= t->len ? start : -1;
  }

堆串

• 结构定义

  typedef char CHAR;
  
  typedef struct {
      CHAR *ch;
      int len;
  } String, *StringPtr;

• 插入

  //串插入函数(在第pos个位置之前插入T,)
  bool StrInsert(String *S, int pos, const String T) {
  	int i;
  	char *temp;
  	if (NULL == S || NULL == S->ch || NULL == T.ch || pos > S->len || pos < 1) {
  		return false;//插入位置不合法
  	}
  	else {
  		temp = (char *)malloc(sizeof(char)*(S->len + T.len + 1));
  		if (NULL == temp) {
  			return false;
  		}
  		else {
  			for (i = 1; i < pos; i++) {	//把S串pos（不含S->ch[pos]）之前的字符赋值给temp
  				temp[i] = S->ch[i];
  			}
  			for (i = pos; i < pos + T.len; i++) {	//把串T赋给temp[pos]到temp[pos+T.len]
  				temp[i] = T.ch[i - pos + 1];
  			}
  			for (i = pos + T.len; i <= S->len + T.len; i++) {	//把原来S串中pos之后的内容链接到temp尾部
  				temp[i] = S->ch[i - T.len];
  			}
  			free(S->ch);
  			S->ch = temp;
  			S->len = S->len + T.len;//更新S串的长度
  			return true;
  		}
  	}
  }

• 删除

  bool StrDelete(String *S, int pos, int len) {
  	int i;
  	char *temp;
  	if (NULL == S || NULL == S->ch || len < 0 || pos<1 || pos>S->len - len + 1) {
  		return false;
  	}
  	else {
  		temp = (char *)malloc(sizeof(char)*(S->len - len + 1));
  		if (NULL == temp) {
  			return false;
  		}
  		else {
  			for (i = 1; i < pos; i++) {//把S串pos（不含S->ch[pos]）之前的字符复制给temp
  				temp[i] = S->ch[i];
  			}
  			for (i = pos; i <= S->len - len; i++) {//把temp[pos]之后的部分改写为
  				temp[i] = S->ch[i + len];          //S[pos+len:S->len]的内容
  			}
  			free(S->ch);
  			S->ch = temp;
  			S->len = S->len - len;   //更新串S的长度
  			return true;
  		}
  	}
  }

• 与线性串的区别

  堆串的每一次操作都要重新生成一个新的定长串，并从原串中取值

  线性串则是在原串上操作

块链串

• 结构定义

  #define BLOCK_SIZE 4    // 可由用户定义的块大小
  #define BLS_BLANK '#'   // 用于空白处的补齐字符
  
  typedef struct _block {
      char ch[BLOCK_SIZE];    //块的数据域
      struct _block *next;    //块的指针域
  } Block;
  
  typedef struct {
      Block *head;        // 串的头指针
      Block *tail;        // 串的尾指针
      int len;            // 串的当前长度
  } BLString;