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语言中的静态数组,串值的存储空间必须进行预分配,致使它的应用受到一定限制。 |