数据结构（C语言版）严蔚敏 吴伟民 编著 第4章 串
数据结构（C语言版）严蔚敏 吴伟民 编著 第4章 串
前言
计算机上的非数值处理的对象基本上是字符串数据。在较早的程序设计语言中，字符串是作为输入和输出的常量出现的。随着语言加工程序的发展，产生了字符串处理。这样，字符串也就作为一种变量类型出现在越来越多的程序设计语言中，同时也产生了一系列字符串的操作。字符串一般简称为串。在汇编和语言的编译程序中，源程序及目标程序都是字符串数据。在事务处理程序中，顾客的姓名和地址以及货物的名称、产地和规格等一般也是作为字符串处理的。又如信息检索系统、文字编辑系统、问答系统、自然语言翻译系统以及音乐分析程序等，都是以字符串数据作为处理对象的。然而，现今我们使用的计算机的硬件结构主要是反映数值计算的需要的，因此，在处理字符串数据时比处理整数和浮点数要复杂得多。而且，在不用类型的应用中，所处理的字符串具有不同的特点，要有效地实现字符串的处理，就必须根据具体情况使用合适的存储结构。
4.1 串类型的定义
串（或字符串）是由零个或多个字符组成的有限序列，一般记为：
s=‘a1a2…an’
其中s是串的名，用单引号括起来的字符序列是字符串的值，ai可以是字母、数字或其他字符，串中字符的数目n称为串的长度。零个字符的串称为空串，它的长度为零。串中任意个连续的字符组成的子序列称为该串的子串。包含子串的串相应地称为主串。通常称字符在序列中的序号为该字符在串中的位置。子串在主串中的位置则以子串的第一个字符在主串中的位置来表示。称两个串相等的，当且仅当这两个串的值相等。也就是说，只有当两个串的长度相等，并且各个对应位置的字符都相等时才相等。串值必须用一对单引号括起来，但单引号本身不属于串，它的作用只是为了避免与变量名或数的常量混淆而已。
在各种应用中，空格常常是串的字符集合中的一个元素，因而可以出现在其他字符串中间。有一个或多个空格组成的串’ '称为空格串，它的长度为串中空格字符的个数。
利用判等、求串长和求子串等操作实现定位函数Index(S, T, pos)。算法的基本思想是在主串S中取从第i（i的初始值为pos）个字符起、长度和串T相等的子串和串T比较，若相等，则求得函数值为i，否则i值增1直至串S中不存在和串T相等的子串为止：
int Index(Sring 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; // 返回子串在主串中的位置
}
}
return 0; // S中不存在与T相等的子串
}// Index
4.2 串的表示和实现
如果在程序设计语言中，串只是作为输入或输出的常量存在，则只需存储此串的串值，即字符序列即可。但在多数非数值处理的程序中，串也以变量的形式出现。串有3中机内表示方法，分别介绍如下：
4.2.1 定长顺序存储表示
类似于线性表的顺序存储结构，用一组地址连续的存储单元存储串值得字符序列。在串的定长顺序存储结构中，按照预定义的大小，为每个定义的串变量分配一个固定长度的存储区，则可用定长数组如下描述之：
// 串的定长顺序存储表示
#define MAXSTRLEN 255 // 用户可在255以内定义最大串长
typedef unsigned char SString[MAXSTRLEN + 1]; // 0号单元存放串的长度
串的实际长度可在这预定义长度的范围内随意，超过预定义长度的串值则被舍去，称之为截断。对串长有两种表示方法：一是如上述定义描述的那样，以下标为0的数组分量存放串的实际长度，如PASCAL语言中的串类型采用这种表示方法；二是在串值后面加一个不计入串长的结束标记字符，如在有的C语言中以’\0’表示串值的终结。此时的串长为隐藏值，显然不便于进行某些串操作。
在这种存储结构表示时如何实现串的操作，下面以串联接和求子串为例讨论之。
- 串连接（Concat&T,S1,S2）
Status Concat(SSting &T,SString S1,SString S2){
// 用T返回由S1和S2联结而成的新串，若为截断，则返回TRUE，否则FALSE
if(S[0]+S[1]<= MAXSRELEN){ // 未截断
T[1..S1[0]] = S1[1..S1[0]];
T[S1[0]+1..S1[0]+S2[0]] =S2[1..S2[0]];
T[0] = S1[0] + S2[0]; uncat = TRUE;
}
else if(S1[0 < MAXSTRLEN]){ // 截断
T[1..S1[0]] = S1[1..S1[0]];
T[S1[0]+1..MAXSTRLEN] = S2[1..MAXSTELEN - S1[0]];
T[0] = MAXSTRLEN; uncat = FALSE;
}
else{ // 截断
T[0..MAXSTRLEN] = S1[0..MAXSTRLEN];
T[0] ==S1[0] == MAXSTRLEN;
uncat = FALSE;
}
return uncut;
}// Concat
- 求子串SubString(&Sub,S,pos,len)
求子串的过程即为复制字符序列的过程，将串S中从第pos个字符开始长度为len的字符序列复制到串Sub中。显然，本操作不会有需截断的情况，但有可能产生用户给出的参数不符合操作的初始条件，当参数非法时，返回ERROR，其算法为：
Status SubString(SString &Sub,SString S, int pos, int len){
// 用Sub返回串的第pos个字符起长度为len的子串，其中1≤pos≤StrLength(S) 且0≤len≤StrLength(S)-pos+1
if(pos<1|| pos>S[0]||len<0 || len>S[0] - pos+1)
return ERROR;
Sub[1..len] = S[pos..pos+len-1];
Sub[0] = len; return OK;
}// SubString
综上两个操作可见，在顺序存储结构中，实现串操作的原操作为字符序列的复制，操作的时间复杂度基于复制的字符序列的长度。另一操作特点是，如果在操作中出现串值序列的长度超过上界MAXSTRLEN时，约定用截尾法处理，这种情况下不仅在求联接串时可能发生，在串的其他操作中，如插入、置换等也可能发生。克服这个弊病唯有不限定串长的最大长度，即动态分配串值的存储空间。
4.2.2 堆分配存储表示
这种存储表示的特点是，仍以一组地址连续的存储单元存放串值字符序列，但它们的存储空间是在程序执行过程中动态分配而得。在C语言中，存在一个称之为堆的*存储区，并由C语言的动态分配函数malloc()和free()来管理。利用函数malloc()为每个新产生的串分配一块实际串长所需的存储空间，若分配成功，则返回一个指向起始地址的指针，作为串的基址，同时为了以后处理方便，约定串长也作为存储结构的一部分。
// 串的堆分配存储表示
typedef struct{
char *ch; // 若是非空串，则按串长分配存储区，否则ch为NULL
int length; // 串长度
}HString：
这种存储结构表示时的串操作仍是基于字符序列的复制进行的。
如串插入操作StrInsert(&S,pos,T)的实现方法是，为串S重新分配大小等于串S和串T长度之和的存储空间，然后进行串值复制：
Status StrInsert(HString &S, int pos, HString T){
// 1≤pos≤StrLength(S)+1 在串S的第pos个字符之前插入串T
if(pos<1 || pos > S.length +1) return ERROR; // pos值不合法
if(T.length){ // T非空，则重新分配空间，插入T
if(!(S.ch = (char *)realloc(S.ch,(S.length + T.length)*sizeof(char))))
exit(OVERFLOW);
for(i = S.length -1; i>=pos-1; --i) // 为插入T而腾出位置
S.ch[i+T.length] = S.ch[i];
S.ch[pos-1..pos + T.length -2] = T.ch[0..T.length-1]; // 插入T
S.length += T.length;
}
return OK;
}// StrInsert
以上两种存储表示通常为高级程序设计语言所采用的。由于堆分配存储结构的串既有顺序存储结构的特点，处理方便，操作中对串长又没有任何限制，更显灵活。因此在串处理的应用程序中也常被选用。
int StrLength(HString S){
// 返回S的元素个数，称为串的长度
return S.length;
}// StrLength
int Compare(HString S, HString T){
// 若S>T，则返回>0；若S=T，则返回 = 0；若S<T，则返回<0
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;
}// StrCompare
Status ClearString(HString &S){
// 将S清为空串
if(S.ch) {free(S.ch); S.ch = NULL;}
S.length = 0;
return OK;
}ClearString
Status Concat(HString &T, HString S1, HString S2){
// 用T返回由S1和S2联接而成的新串
if(T.ch) free(T.ch); // 释放旧空间
if(!(T.ch = (char *)malloc((S1.length+S2.length)*sizeof(char))))
exit(OVERFLOW);
T.ch[0..S1.length-1] = S1.ch[0..S1.length - 1];
T.length = S1.length + S2.length;
T.ch[S1.length..T.length - 1] = S2.ch[0..S2.length - 1];
return OK;
}// Concat
Status SubString(HString &Sub,Hstring S,int pos, int len){
// 用Sub返回串S的第pos个字符起长度为len的子串，其中1≤pos≤StrLength(S)且0≤len小于等于StrLength(S) - pos +1
if(pos < 1|| pos >S.length|| len <0 || len >S.length - pos +1)
return ERROR;
if(Sub.cn) free(Sub.ch); // 释放旧空间
if(!len) {Sub.ch = NULL; Sub.length = 0;} // 空子串
else{
Sub.cn = (char *)malloc(len * sizeof(char));
Sub.cn[0..len - 1] = S.ch[pos - 1.. pos + len -2];
Sub.length = len;
}
return OK;
}// SubString
4.2.3 串的块链存储表示
为了便于进行串的操作，当以链表存储串值时，除头指针外还可附设一个尾指针指示链表中的最后一个结点，并给出当前串的长度。称如此定义的串存储结构为块链结构，说明如下：
#define CHUNKSIZE 80 // 可由用户定义的块大小
typedef struct Chunk{
char ch[CHUNKSIZE];
struct Chunk *next;
}Chunk;
typedef struct{
Chunk *head,*tail; // 串的头和尾指针
int curlen; // 串的当前长度
}LString;
串值得链式存储结构对某些串操作，如联接操作等具有一定方便之处，但总的来说不如另外两种存储结构灵活，它占用存储量大且操作复杂。
4.3 串的模式匹配算法
4.3.1 求子串位置的定位函数Index(S,T,pos)
子串的定位操作通常称为串的模式匹配，其中T为模式串，是各种串操作系统中最重要的操作之一。
int Index(SString S,SString T,int pos){
// 返回子串T在主串S中第pos个字符之后的位置，若不存在，则函数值为0，其中T非空，1≤pos≤StrLength(S)
i = pos; j = 1;
while(i <= S[0] && j<= T[0]){
if(S[i] == T[j]) {++i; ++j;} // 继续比较后继字符
else(i = i-j+2;j = 1;) // 指针后退开始匹配
}
if(j>T[0]) return i - T[0];
else return 0;
}// Index
4.3.2 模式匹配的一种改进算法
D.E.Knuth与V.R.Pratt和J.H.Morris同时发现了改进算法，简称为KMP算法，此算法可以在O(n+m)的时间数量级上完成串的模式匹配操作。其改进在于：每当一遍匹配过程中出现字符比较不等时，不需回溯i指针，而是利用已经得到的部分匹配的结果将模式向右滑动尽可能远的一段距离后，继续进行比较。