一串的定义

§ 字符串一般简称为串。串(String),或称字符串是由零个或多个字符组成的有限序列。一般记为：

   S = ‘a0a1…an-1 ‘ (n ≥ 0 )

§ 其中，S是串的名称，用单引号括起来的字符序列是串的值；ai (1≤i≤n)可以是字母、数字或其它字符串中字符的数目n称为串的长度。零个字符的串称为空串(null string)，它的长度为零。

§ 串中任意个连续的字符组成的子序列称为该串的子串。包含子串的的串相应地称为主串。通常称字符在序列中的序列号为该字符在串中的位置。子串在主串中的位置则以子串第1个字符在主串的位置来表示。

§ 串值必须用一对单引号括起来，但单引号不属于串，它的作用只是为了避免与变量或常量混淆。例如：

x = ‘123’;

其中，X是一个串变量名，赋给它的值是字符序列123,而不是整数123。之间可以进行比较。

aString=‘aString’;

左边的aString是一个串变量名，而右边的字符序列aString是赋给它的值

int Index (String S, String T, int pos) {

 // T为非空串。若主串S中第pos个字符之后存在与 T相等的子串，则返回第一个

    这样的子串在S中的位置，否则返回0

  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 ;

    } // while

  } // if

  return 0;          // S中不存在与T相等的子串

} // Index

4.2  串的表示和实现

一、串的定长顺序存储表示

#define  MAXSTRLEN  255

  // 用户可在255以内定义最大串长

  typedef unsigned char  Sstring

   [MAXSTRLEN + 1];

          // 0号单元存放串的长度

二、串的堆分配存储表示

typedef struct {

   char *ch;     

      // 若是非空串，则按串长分配存储区，

      //  否则ch为NULL

   int  length;   // 串长度

 } HString;

Status StrInsert(HString &S,int pos,HString T)

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];

S.ch[pos-1….pos+T.length-2]=T.ch[0…T.length-1];

S.length+=T.length;

}

Return OK;

}

Status StrAssign(HString &T,char *chars)

{

If(T.ch) free(T.ch);

For(i=0,c=chars;*c;++i,++c);

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;

}

Int StrCompare(HString S,HString T)

{

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;

}

Status ClearString(HString &S)

{

If(S.ch) {free(S.ch); S.ch=NULL;}

S.length=0;

Return OK;

}