4.1.2　串的抽象数据类型

1.数据集合

串的数据集合可以表示为字符序列s0，s1，…，sn_1，每个数据元素的数据类型为字符类型。

2.操作集合

为方便说明问题，我们先定义如下几个串：

（1）赋值Assign（S，T）：把串T的值赋给串S。

（2）求长度Length（S）：求串S的长度。

例如，Length（S1）＝14，Length（S2）＝7。

（3）比较Compare（S4，S1）＝1。这是由于当比较到第7个字符时，字符't'的ASCII码值大于字符's'的ASCII码值，所以函数返回1。

（4）插入Insert（S，pos，T）：若参数满足约束条件0≤pos≤Length（S），则在串S的第pos个字符前插入串T，串S的新长度为Length（S）＋Length（T），函数返回1；若参数不满足约束条件，则函数返回0。

例如，Insert（S1，4，＂not＂）操作后，串S1＝＂I am not a student＂。

（5）删除Delete（S，pos，len）：若参数满足约束条件0≤pos≤Length（S）－1，1≤len和pos＋len≤Length（S）－1，则删除串S中从第pos个字符开始，长度为len的连续字符，且函数返回1；若参数不满足约束条件，则函数返回0。

例如，Delete（S1，6，7）操作后，串S1＝＂I am a＂。

（6）截取子串SubString（S，pos，len，T）：若参数满足约束条件0≤pos＜Length（S）－1，1≤len和pos＋len≤Length（S）－1，则截取串S中从第pos个字符开始，长度为len的连续字符并赋给串T，且函数返回1；若参数不满足约束条件，则函数返回0。

例如，SubString（S1，6，7，T）操作后，串T＝＂student＂。

（7）查找Search（S，start，T）：在主串S中，从位置start开始查找是否存在子串T，若主串S中存在子串T，则函数返回子串T在主串S中的第一个字符位置；若主串S中不存在子串T，则函数返回－1。

例如，Search（S1，0，S2）＝7，Search（S1，0，S3）＝－1。

（8）替换Replace（S，start，T，V）：在主串S中，从位置start开始查找是否存在子串T，若主串S中存在子串T，则用子串V替换子串T，且函数返回1；若主串S中不存在子串T，则函数返回0。

例如，Replace（S1，0，S2，S3）的返回值为1，且该函数调用后，S1＝＂I am a teacher＂。

4.1.3 C语言的串函数

C语言用字符数组存储串，其长度不定，解决该问题的方法是在串的末尾自动添加一个字符'＼0'作为串结束标志。下面的语句定义了一个字符数组并赋值为＂I am a teacher＂。

该串在内存中的存储形式如下：

其中，数组名str指示了串＂I am a teacher＂在内存中的首地址，标志'＼0'指示了串的结束。

C语言的库文件string.h中也提供了许多实现串操作的函数。这些函数的功能和4.1.2节讨论的串操作的功能不完全相同。下面给出几个常用的C语言串函数及其使用方法。

我们先定义如下语句：

（1）串长度int strlen（char＊str）

（2）拷贝char＊strcpy（char＊str1，char＊str2）

（3）比较int strcmp（char＊str1，char＊str2）

（4）字符定位char＊strchr（char＊str，char ch）

（5）子串查找char＊strstr（char＊s1，char＊s2）

（6）连接char＊strcat（char＊str1，char＊str2）

C语言提供的实现串操作的函数还有很多而且功能较强，因为篇幅不能一一叙述。下面给出一个使用C语言串函数编程的例子。

例4.1 中文姓名与英文姓名最大的不同是，中文姓在前名在后，而英文名在前姓在后。试编写程序把以汉语拼音表示的中文名转换为英文名。

设计思路：利用C库函数strchr（）、strcpy（）和strcat（）实现。

程序如下：