4.2.1 串的定长顺序存储表示

  类似于线性表的顺序存储结构,可用一组地址连续的存储单元存储串值的字符序列。例如C和C++语言中串不是预定义的数据类型,而是以字符数组来表示串。如声明
   char str[10];

  表明 str 是一个串变量。C语言中还规定了一个"串的结束标志 '\0'"(字符 '\0'称为空终结符),即数组中在该结束标志之前的字符是串变量的有效字符,但结束标志本身要占一个字符的空间,因此串变量 str 的值(字符序列)的实际长度可在这个定义范围内随意,但最大不能超过9。

  在这种表示方法下,实现串操作的基本操作是"字符序列的复制"。如下列算法4.1和4.2分别为串的联接和求子串。
 
 

  如果在程序设计语言中,串只是作为输入/输出的常量出现,则只需要存储这个串常量值,即字符序列即可。但在多数非数值处理的程序中,串也以变量的形式出现。则需要根据串操作的特点,合理地选择和设计串值的存储结构及其维护方式。

  这里介绍三种串的表示方法。
 
  算法 算法 4.3
  void Concat( char S1[ ], char S2[ ], char T[ ])
 {
  // 以T返回由S1和S2联接而成的新串
  j=0; k=0;
  while ( S1[j] != '\0') T[k++] = S1[j++];   // 复制串 S1
  j = 0;
  while ( S2[j] != '\0') T[k++] = S2[j++];   // 紧接着复制串 S2
  T[k] = '\0';                // 置结果串T的结束标志
 } // Concat_Sq
 
 
  这种表示方法中,存储串值的数组空间都是静态分配的,此算法中串T的存储空间必须在调用此函数的程序中予以分配,即在该程序中必须为T分配足够的空间。否则将会出现"数组越界"的非法操作错误。
 
  算法 算法 4.4
  bool SubString ( char Sub[ ], char S, int pos, int len )
 {
  // 若参数合法(即1≤pos≤StrLength(S) 且
  // 0≤len≤StrLength(S)-pos+1),则以Sub带回串S中第pos个
  // 字符起长度为len的子串,并返回TRUE,否则返回FALSE

  slen=StrLength(S);               // 求串S的长度
  if (pos < 1 || pos > slen || len < 0 || len > slen-pos+1)
   return FALSE;
  for ( j = 0; j < len; j++ ) Sub[ j ] = S[ pos + j - 1 ];
                          // 向子串Sub复制字符
  Sub[len] = '\0';                // 置串Sub的结束标志
  return TRUE;
 } // SubString
 
  同理,函数中Sub的存储空间由调用函数中的实参确定。

  从这两个例子可见,用字符数组表示字符串时,串的操作容易进行,而且允许用数组名进行串的输入和输出,但由于在此用的是C语言中的静态数组,串值的存储空间必须进行预分配,致使它的应用受到一定限制。