假期连载之七
（串，串在C/C++中的应用—上）
前记：本篇的前半部分事实上在上周末即已完成，原本无意分为两个部分来写，不过身体突发小恙，卧床了两天，为不至于拖延太长时间故先把已完成的发布出来，下不为例。就这样了。
本节我们介绍字符串—一般简称为串，它在计算机数据类型中具有非常重要的地位。无论从汇编语言、C/C++还是到Java，串操作都是语言本身必不可少的一部分内容。尽管每种语言在串的存储形式上存在一些差异，但对其本身的定义和操作却完全一致。最后我们会以C++的String容器为例，综合介绍字符串操作的规则及原理。
字符串
字符串是指由零个或多个字符组成的有限序列。每个字符可以是字母、数字或其他字符，串中字符的个数称为字符串长度，当长度为0时称为空串。
学习过C语言的都知道，字符一般用单引号括起来，而字符串则使用双引号。事实上在一般数据结构描述中串默认代表了单个字符的情况，因此都使用单引号表示。
子串是指任意个连续的字符组成的子序列。
主串指包含子串的串，字串是主串的一部分。
字串在主串中的位置，是指字串的第一个字符在主串中的位置。
串相等的条件是两个串的长度相等，并且每个对应位置的字符也都相等。
现在，我们可以认识到，串也是一种特定的线性表，其特性主要体现在数据元素的类型为字符。
事实上，在C/C++中，所谓的字符串其实是以字符串数组char[]的形式来进行操作的，这一点与Java中lang.String的实现有所区别，一般而言Java的String类更符合字符串的存储形式。
串的抽象数据类型的C语言描述表示如下：
ADT String
{
数据对象:D={a1,a2,…,an},其中an为char类型
基本操作:
……
}
这里省略了字符串的基本运算函数，主要是因为在C/C++中既有从C语言继承而来的标准库函数，又有C++独立具备的STL中的String容器，Java中的String类也自成体系。对于众多运算必须明确地加以区别，否则会在实际编程中引起很多困难。
借助于Internet，我们收集了C/C++库函数中关于字符串操作的函数集：
void *memccpy (void *dest, const void *src, int c, size_t n);
从src所指向的对象复制n个字符到dest所指向的对象中。如果复制过程中遇到了字符c则停止复制，返回指针指向dest中字符c的下一个位置；否则返回NULL。
void *memcpy (void *dest, const void *src, size_t n);
从src所指向的对象复制n个字符到dest所指向的对象中。返回指针为dest的值
void *memchr (const void *s, int c, size_t n);
在s所指向的对象的前n个字符中搜索字符c。如果搜索到，返回指针指向字符c第一次出现的位置；否则返回NULL。
int memcmp (const void *s1, const void *s2, size_t n);
比较s1所指向的对象和s2所指向的对象的前n个字符。返回值是s1与s2第一个不同的字符差值。
int memicmp (const void *s1, const void *s2, size_t n);
比较s1所指向的对象和s2所指向的对象的前n个字符，忽略大小写。返回值是s1与s2第一个不同的字符差值。
void *memmove (void *dest, const void *src, size_t n);
从src所指向的对象复制n个字符到dest所指向的对象中。返回指针为dest的值。不会发生内存重叠。
char *stpcpy (char *dest, const char *src);
复制字符串src到dest中。返回指针为dest + len(src)的值。
char *strcpy (char *dest, const char *src);
复制字符串src到dest中。返回指针为dest的值。
char *strchr (const char *s, int c);
在字符串s中搜索字符c。如果搜索到，返回指针指向字符c第一次出现的位置；否则返回NULL。
int strcmp (const char *s1, const char *s2);
比较字符串s1和字符串s2。返回值是s1与s2第一个不同的字符差值。
int stricmp (const char *s1, const char *s2);
比较字符串s1和字符串s2，忽略大小写。返回值是s1与s2第一个不同的字符差值。
size_t strcspn (const char *s1, const char *s2);
返回值是字符串s1的完全由不包含在字符串s2中的字符组成的初始串长度。
size_t strspn (const char *s1, const char *s2);
返回值是字符串s1的完全由包含在字符串s2中的字符组成的初始串长度。
char *strdup (const char *s);
得到一个字符串s的复制。返回指针指向复制后的字符串的首地址。
char *strerror(int errnum);
返回指针指向由errnum所关联的出错消息字符串的首地址。errnum的宏定义见errno.h。
size_t strlen (const char *s);
返回值是字符串s的长度。不包括结束符’\0′。//计算长度len时不包括结束符’\0′，计算size时要包括结束符’\0′，亦即size=len+1。
char *strlwr (char *s);
将字符串s全部转换成小写。返回指针为s的值。
char *strupr (char *s);
将字符串s全部转换成大写。返回指针为s的值。
char *strncat (char *dest, const char *src, size_t maxlen);
将字符串src添加到dest尾部，最多添加maxlen个字符。返回指针为dest的值。
char *strcat (char *dest, const char *src);
将字符串src添加到dest尾部。返回指针为dest的值。
int strncmp (const char *s1, const char *s2, size_t maxlen);
比较字符串s1和字符串s2，最多比较maxlen个字符。返回值是s1与s2第一个不同的字符差值。
char *strncpy (char *dest, const char *src, size_t maxlen);
复制字符串src到dest中，最多复制maxlen个字符。返回指针为dest的值。
int strnicmp(const char *s1, const char *s2, size_t maxlen);
比较字符串s1和字符串s2，忽略大小写，最多比较maxlen个字符。返回值是s1与s2第一个不同的字符差值。
char *strnset (char *s, int ch, size_t n);
设置字符串s中的前n个字符全为字符c。返回指针为s的值。
void *memset (void *s, int c, size_t n);
设置s所指向的对象的前n个字符为字符c。返回指针为s的值。
char *strset (char *s, int ch);
设置字符串s中的字符全为字符c。返回指针为s的值。
char *strpbrk (const char *s1, const char *s2);
返回指针指向字符串s1中字符串s2的任意字符第一次出现的位置；如果未出现返回NULL。
char *strrchr (const char *s, int c);
在字符串s中搜索字符c。如果搜索到，返回指针指向字符c最后一次出现的位置；否则返回NULL。
char *strrev (char *s);
将字符串全部翻转，返回指针指向翻转后的字符串。
char *strstr (const char *s1, const char *s2);
在字符串s1中搜索字符串s2。如果搜索到，返回指针指向字符串s2第一次出现的位置；否则返回NULL。
char *strtok (char *s1, const char *s2);
用字符串s2中的字符做分隔符将字符串s1分割。返回指针指向分割后的字符串。第一次调用后需用NULLL替代s1作为第一个参数。
串的存储实现
由于串是一种特定的线性表，因而其存储结构与普通线性表之间并无很大差异。
最常用的即是前文已介绍的定长顺序串，其类型定义如下。
#define MAXLEN 40
typedef struct
{
char ch[MAXLEN];
int len; //存储字符串实际长度
}SString;
还有一种堆串，其串中的字符仍然存放在一组地址连续的存储单元中，但它们的存储空间是在程序执行过程中动态分配的。系统将一个地址连续、容量很大的存储空间作为字符串的可用空间，每当建立一个新串时，系统就会从这个空间中分配一个大小和字符串长度相同的空间存储新串的串值。其类型定义如下:
typedef struct
{
char *ch;
int len; //存储字符串实际长度
}HString;
由于堆串在实际应用中可以动态分配存储空间，其较定长顺序串而言方便了许多。但由于其本质未能发生变化，故操作上要不断生成新串、销毁旧串。
同时字符串还可以用链式存储结构表示。在这种结构中，结点值可以存放一个字符，也可以存放多个字符，故结点被称为块，链表相应被称为块链表。
鉴于块链表的特殊结构，在实际应用中要考虑几个重要因素。
结点大小：结点大小是指结点data域中存放的字符个数。由于存储密度=串值所占用的存储位/实际为串分配的存储位，得知当存储密度越小，块链表操作越容易，但需耗费更多的存储空间，这就需要根据实际情况来判断。
结点大小大于1，为节约空间而采用结点大小大于1的方法，尽管存储密度得到了提高，但结点内部串的操作就变得较为复杂，尤其是在进行删除、合并操作时需要充分考虑到data域自身的运算。
（未完待续）