第4章串4.1串的基本概念当且仅当两个串的长度相等并且各个对应位置上的字符都相同时这两个串才是相等的。一个串中任意个连续字符组成的子序列含空串，但不含串本身）称为该串的子串。例如，“a”、“ab”、“abc”和“abcd”等都是“abcde”的子串（有的教科上将本身作为子串）。串的基本运算如下：(1)StrAssign(&s,chars):将一个字符串常量赋给串s,即生成一个其值等于chars的串s。(2)StrCopy(&s,t):串复制：将串t赋给串s。(3)StrEqual(s,t)：判串相等：若两个串s与t相等则返回真：否则返回假。(4)StrLength(s)：求串长：返回串s中字符个数。(5)Concat(s,t)：串连接：返回由两个串s和t连接在一起形成的新串。(6)SubStr(s,ij)：求子串：返回串s中从第i(1≤i≤StrLength(s))个字符开始的、由连续j个字符组成的子串。(7)InsStr(s1,i,s2):将串s2插入到串s1的第i(1≤i≤StrLength(s)+1)个字符中,即将s2的第一个字符作为s1的第i个字符，并返回产生的新串。(8)DelStr(s,i,)：从串s中删去从第i(1≤i≤StrLength(s))个字符开始的长度为j的子串，并返回产生的新串。(9)RepStr(s,ij,t)：替换：在串s中,将第i(1≤i≤StrLength(s))个字符开始的个字符构成的子串用串t替换，并返回产生的新串。(10)DispStr(s)：串输出：输出串s的所有元素值。4.2.1串的顺序存储及其基本操作实现串是一种特殊的线性表,在非紧缩格式中,它的每个结点仅由一个字符组成,因此存储串的方法也就是存储线性表的一般方法。存储串最常用的方式是采用顺序存储，即把串的字符顺序地存储在内存一片相邻的空间,这称为顺序串。4.2串的存储结构顺序存储采用一般顺序表的存储结构，其类型定义如下：#defineMaxSize100typedef structchar data[MaxSize]int len,SqString;其中.data域用来存储字符串,len域用来存储字符串的当前长度.MaxSize常量表示允许所存储字符串的最大长度。在C语言中每个字符串以10标志结束。顺序串中实现串的基本运算如下：(1) StrAssign(str,cstr)将一个字符串常量赋给串str,即生成一个其值等于cstr的串s。(2) StrCopy(s,t)将串t复制给串 s。(3) StrEqual(s,t)判断两个串是否相等：若两个串s与t相等返回真(1)；否则返回假(O)。(4) StrLength(s)求串长：返回串s中字符个数。(5) Concat(s,t)32
32 第 4 章 串 4.1 串的基本概念 当且仅当两个串的长度相等并且各个对应位置上的字符都相同时,这两个串才是相等的。 一个串中任意个连续字符组成的子序列(含空串,但不含串本身)称为该串的子串。例 如,“a”、“ab”、“abc”和“abcd”等都是“abcde”的子串（有的教科上将本身作为子串）。 串的基本运算如下: (1) StrAssign(&s,chars):将一个字符串常量赋给串 s,即生成一个其值等于 chars 的串 s。 (2) StrCopy(&s,t):串复制:将串 t 赋给串 s。 (3) StrEqual(s,t):判串相等:若两个串 s 与 t 相等则返回真；否则返回假。 (4) StrLength(s):求串长:返回串 s 中字符个数。 (5) Concat(s,t):串连接:返回由两个串 s 和 t 连接在一起形成的新串。 (6)SubStr(s,i,j):求子串:返回串 s 中从第 i(1≤i≤StrLength(s))个字符开始的、由连续 j 个字符组成的子串。 (7)InsStr(s1,i,s2):将串 s2 插入到串 s1 的第 i(1≤i≤StrLength(s)+1)个字符中,即将 s2 的 第一个字符作为 s1 的第 i 个字符,并返回产生的新串。 (8)DelStr(s,i,j):从串 s 中删去从第 i(1≤i≤StrLength(s))个字符开始的长度为 j 的子串,并返回 产生的新串。 (9)RepStr(s,i,j,t):替换:在串 s 中,将第 i(1≤i≤StrLength(s))个字符开始的 j 个字符构成 的子串用串 t 替换,并返回产生的新串。 (10) DispStr(s):串输出:输出串 s 的所有元素值。 4.2.1 串的顺序存储及其基本操作实现 串是一种特殊的线性表,在非紧缩格式中,它的每个结点仅由一个字符组成,因此存储 串的方法也就是存储线性表的一般方法。存储串最常用的方式是采用顺序存储,即把串的字 符顺序地存储在内存一片相邻的空间,这称为顺序串。 4.2 串的存储结构 顺序存储采用一般顺序表的存储结构,其类型定义如下: #define MaxSize 100 typedef struct { char data[MaxSize]; int len; } SqString; 其中,data 域用来存储字符串,len 域用来存储字符串的当前长度,MaxSize 常量表示允许 所存储字符串的最大长度。在 C 语言中每个字符串以'\0'标志结束。 顺序串中实现串的基本运算如下: (1) StrAssign(str,cstr) 将一个字符串常量赋给串 str,即生成一个其值等于 cstr 的串 s。 (2) StrCopy(s,t) 将串 t 复制给串 s。 (3) StrEqual(s,t) 判断两个串是否相等:若两个串 s 与 t 相等返回真(1)；否则返回假(0)。 (4) StrLength(s) 求串长:返回串 s 中字符个数。 (5) Concat(s,t)
返回由两个串s和t连接在一起形成的新串。(6) SubStr(s,i,i)返回串s中从第i(1≤i≤StrLength(s))个字符开始的、由连续个字符组成的子串。(7) InsStr(sl,i,s2)将串s2插入到串s1的第i个字符中,即将s2的第一个字符作为s1的第i个字符,并返回产生的新串。(8) DelStr(s,i,j)从串s中删去第i(1≤i≤StrLength(s))个字符开始的长度为j的子串,并返回产生的新串。(9) RepStr(s,i,j,t)在串s中,将第i(1≤i≤StrLength(s)个字符开始的j个字符构成的子串用串t替换,并返回产生的新串。(10) DispStr(s)输出串s的所有元素值。4.2.2串的链式存储及其基本操作实现也可以采用链式方式存储串，即用单链表形式存储串。这称为链式串或链串。链串中的结点类型定义typedef struct snodechar data,struct snode *next; LiString;其中data域用来存储组成字符串的字符,next域用来指向下一个结点。每个字符对应一个结点，一个这样的链表存储一个字符串。下图所示是一个结点大小为1的链串。链串示意图下面讨论在链串上实现串基本运算的算法。(1) StrAssign(s,t)将一个字符串常量t赋给串s,即生成一个其值等于t的串s。以下采用尾插法建立链串。(2) StrCopy(s,t)将串t复制给串s。以下采用尾插法建立复制后的链串s(3) StrEqual(s,t)判断两个串是否相等：若两个串s与t相等则返回真(1)：否则返回假(0)。(4) StrLength(s)求串长：返回串s中字符个数。(5) Concat(s,t)返回由两个串s和t连接在一起形成的新串。(6) SubStr(s,i,j)返回串 s中从第i(1≤i≤StrLength(s))个字符开始的、由连续j个字符组成的子串。(7) InsStr(s1,i,s2)将串s2插入到串s1的第(1≤i≤StrLength(s)+1)个字符中,即将s2的第一个字符作为s1的第i个字符,并返回产生的新串。(8) DelStr(s,i.j)从串s中删去从第(1≤i≤StrLength(s)个字符开始的长度为j的子串,并返回产生的新串。33
33 返回由两个串 s 和 t 连接在一起形成的新串。 (6) SubStr(s,i,j) 返回串 s 中从第 i(1≤i≤StrLength(s))个字符开始的、由连续 j 个字符组成的子串。 (7) InsStr(s1,i,s2) 将串 s2 插入到串 s1 的第 i 个字符中,即将 s2 的第一个字符作为 s1 的第 i 个字符,并 返回产生的新串。 (8) DelStr(s,i,j) 从串 s 中删去第 i(1≤i≤StrLength(s))个字符开始的长度为 j 的子串,并返回产生的新 串。 (9) RepStr(s,i,j,t) 在串 s 中,将第 i(1≤i≤StrLength(s))个字符开始的j 个字符构成的子串用串t 替换,并返 回产生的新串。 (10) DispStr(s) 输出串 s 的所有元素值。 4.2.2 串的链式存储及其基本操作实现 也可以采用链式方式存储串,即用单链表形式存储串。这称为链式串或链串。 链串中的结点类型定义: typedef struct snode { char data; struct snode *next; } LiString; 其中 data 域用来存储组成字符串的字符,next 域用来指向下一个结点。每个字符对应一个结 点,一个这样的链表存储一个字符串。下图所示是一个结点大小为 1 的链串。 链串示意图 下面讨论在链串上实现串基本运算的算法。 (1) StrAssign(s,t) 将一个字符串常量 t 赋给串 s,即生成一个其值等于 t 的串 s。以下采用尾插法建立链 串。 (2) StrCopy(s,t) 将串 t 复制给串 s。以下采用尾插法建立复制后的链串 s。 (3) StrEqual(s,t) 判断两个串是否相等:若两个串 s 与 t 相等则返回真(1)；否则返回假(0)。 (4) StrLength(s) 求串长:返回串 s 中字符个数。 (5) Concat(s,t) 返回由两个串 s 和 t 连接在一起形成的新串。 (6) SubStr(s,i,j) 返回串 s 中从第 i(1≤i≤StrLength(s))个字符开始的、由连续 j 个字符组成的子串。 (7) InsStr(s1,i,s2) 将串 s2 插入到串 s1 的第 i(1≤i≤StrLength(s)+1)个字符中,即将 s2 的第一个字符作为 s1 的第 i 个字符,并返回产生的新串。 (8) DelStr(s,i,j) 从串 s 中删去从第 i(1≤i≤StrLength(s))个字符开始的长度为 j 的子串,并返回产生的 新串
(9) RepStr(s,i,j,t)在串s中,将第i(1≤i≤StrLength(s)个字符开始的j个字符构成的子串用串t替换,并返回产生的新串。(10) DispStr(s)输出串s的所有元素值。4.3串的模式匹配设有主串s和子串t子串t的定位就是要在主串s中找到一个与子串t相等的子串。通常把主串s称为自标串.把子串t称为模式串，因此定位也称作模式匹配。模式匹配成功是指在目标串s中找到一个模式串t；不成功则指目标串s中不存在模式串t。4.4.1Brute-Force算法Brute-Force简称为BF算法,亦称简单匹配算法,其基本思路是从目标串s="sOs1sn-1"的第一个字符开始和模式串="tOtltm-1"中的第一个字符比较若相等则继续逐个比较后续字符：否则从且标串S的第二个字符开始重新与模式串t的第一个字符进行比较。依次类推，若从模式串s的第i个字符开始，每个字符依次和目标串t中的对应字符相等则匹配成功,该算法返回i；否则，匹配失败，函数返回-1。int indexpos(SqString str,SqString substr)int i,j,k,idx=-1,for (i=0;i<str.len;i++)for (j=i,k=0;str.data[i]==substr.data[k];j++,k++)if(k=—substr.len)//注意j每次从i开始，有回溯return(i),3return(-1);1算法1int index(SqString s,SqString t):int i=0,j=0,k;while (i<s.len && j<t.len)if (s.data[i]--t.data[i])/*继续匹配下一个字符*/1/*主串和子串依次匹配下一个字符*i++; j++;else/*主串、子串指针回溯重新开始下一次匹配*/1i=i-j+1;/*主串从下一个位置开始匹配*/j=0,/*子串从头开始匹配*/31/*返回匹配的第一个字符的下标*if (i>=t.len)k=i-t.len,else k=-l;/*模式匹配不成功*/return k,3算法2这个算法简单，易于理解，但效率不高，主要原因是：主串指针i在若干个字符序列比较相等后，若有一个字符比较不相等,仍需回溯(即i=i-j+1)。该算法在最好情况下的时间复杂度为O(m),即主串的前m个字符正好等于模式串的m个字符。在最坏情况下的时间复杂度为O(n*m)。例如,设目标串s=“cddcdc”,模式串t=“cdc”。s的长度为n(n=6),t的长度为m(m=3)。用指34
34 (9) RepStr(s,i,j,t) 在串 s 中,将第 i(1≤i≤StrLength(s))个字符开始的j 个字符构成的子串用串t 替换,并返 回产生的新串。 (10) DispStr(s) 输出串 s 的所有元素值。 4.3 串的模式匹配 设有主串 s 和子串 t,子串 t 的定位就是要在主串 s 中找到一个与子串 t 相等的子串。 通常把主串 s 称为目标串,把子串 t 称为模式串,因此定位也称作模式匹配。模式匹配成功是 指在目标串 s 中找到一个模式串 t；不成功则指目标串 s 中不存在模式串 t。 4.4.1 Brute-Force 算法 Brute-Force 简称为 BF 算法,亦称简单匹配算法,其基本思路是: 从目标串 s="s0s1.sn-1"的第一个字符开始和模式串 t="t0t1.tm-1"中的第一个字符 比较,若相等,则继续逐个比较后续字符；否则从目标串 s 的第二个字符开始重新与模式串 t 的第一个字符进行比较。依次类推,若从模式串 s 的第 i 个字符开始,每个字符依次和目标串 t 中的对应字符相等,则匹配成功,该算法返回 i；否则,匹配失败,函数返回-1。 int indexpos(SqString str,SqString substr) { int i,j,k,idx=-1; for (i=0;i<str.len;i++) { for (j=i,k=0;str.data[j]==substr.data[k];j++,k++); if (k==substr.len) //注意 j 每次从 i 开始,有回溯 return(i); } return(-1); } 算法 1 int index(SqString s,SqString t) { int i=0,j=0,k; while (i<s.len && j<t.len) { if (s.data[i]==t.data[j]) /*继续匹配下一个字符*/ { i++; j++; } /*主串和子串依次匹配下一个字符*/ else /*主串、子串指针回溯重新开始下一次匹配*/ { i=i-j+1; /*主串从下一个位置开始匹配*/ j=0; /*子串从头开始匹配*/ } } if (j>=t.len) k=i-t.len; /*返回匹配的第一个字符的下标*/ else k=-1; /*模式匹配不成功*/ return k; } 算法 2 这个算法简单,易于理解,但效率不高,主要原因是:主串指针 i 在若干个字符序列比较相等后, 若有一个字符比较不相等,仍需回溯(即 i=i-j+1)。该算法在最好情况下的时间复杂度为 O(m), 即主串的前 m 个字符正好等于模式串的 m 个字符。在最坏情况下的时间复杂度为 O(n*m)。 例如,设目标串 s=“cddcdc”,模式串 t=“cdc”。s 的长度为 n(n=6),t 的长度为 m(m=3)。用指
针i指示目标串s的当前比较字符位置，用指针i指示模式串t的当前比较字符位置。BF模式匹配过程如下所示。4.3.2KMP算法KMP算法是D.E.Knuth、J.H.Morris和V.R.Pratt共同提出的.简称KMP算法。该算法较BF算法有较大改进.主要是消除了主串指针的回溯，从而使算法效率有了某种程度的提高。所谓真子串是指模式串t存在某个k(0<k<i)，使得"tOt1*tk"="tj-ktj-k+1tj"成立。t=“abab”对应的next数组如下：void GetNext(SqString t,int next[l)intj,k;1j=0;k=-1;next[0]=-1;while (j<t.len-1)( if(k---1 Il t.data[i]--t.data[k])/*k为-1或比较的字符相等时*/( j++;k++;next[i]=k,1else k=next[k];11由模式串t求出next值的算法int KMPIndex(SqString s, SqString t)int next[MaxSize],i=0,j=0,vGetNext(t,next);while (i<s.len && j<t.len)if (i==-1 I s.data[i]-=t.data[i])i+j++; }/*ij各增1*//*i不变后退*/else j=next[i];1/*返回匹配模式串的首字符下标*if (i>=t.len))v=i-t.len,/else v=-1;/*返回不匹配标志*/returnv,KMP算法设主串s的长度为n，子串t长度为m。在KMP算法中求next数组的时间复杂度为O(m)在后面的匹配中因主串s的下标不减即不回溯,比较次数可记为n,所以KMP算法总的时间复杂度为O(n+m)。例如，设目标串s-“aaabaaaab”，模式串t=“aaaab”。s的长度为n(n=9),t的长度为m(m=5)。用指针i指示目标串s的当前比较字符位置用指针i指示模式串t的当前比较字符位置。KMP上述定义的next在某些情况下尚有缺陷。例如,模式“aaaab”在和主串“aaabaaaab”匹配时,当i=3j=3时,s.data[3]≠t.data[3],由next[i]的指示还需进行i=3、j=2,i=3、j=1,i=3、j-0等三次比较。实际上,因为模式中的第1、2、3个字符和第4个字符都相等,因此,不需要再和主串中第4个字符相比较,而可以将模式一次向右滑动4个字符的位置直接进行=4.=0时的字符比较。这就是说,若按上述定义得到nexti]=k,而模式中pj=pk,则为主串中字符si和pi比较不等时，35
35 针 i 指示目标串 s 的当前比较字符位置,用指针 j 指示模式串 t 的当前比较字符位置。BF 模式 匹配过程如下所示。 4.3.2 KMP 算法 KMP 算法是 D.E.Knuth、J.H.Morris 和 V.R.Pratt 共同提出的,简称 KMP 算法。该算法 较BF算法有较大改进,主要是消除了主串指针的回溯,从而使算法效率有了某种程度的提高。 所谓真子串是指模式串 t 存在某个 k(0＜k＜j)，使得"t0t1.tk " = " tj-ktj-k+1.tj "成立。 t=“abab”对应的 next 数组如下: void GetNext(SqString t,int next[]) { int j,k; j=0;k=-1;next[0]=-1; while (j<t.len-1) { if (k==-1 || t.data[j]==t.data[k]) /*k 为-1 或比较的字符相等时*/ { j++;k++; next[j]=k; } else k=next[k]; } } 由模式串 t 求出 next 值的算法 int KMPIndex(SqString s,SqString t) { int next[MaxSize],i=0,j=0,v; GetNext(t,next); while (i<s.len && j<t.len) { if (j==-1 || s.data[i]==t.data[j]) { i++;j++; } /*i,j 各增 1*/ else j=next[j]; /*i 不变,j 后退*/ } if (j>=t.len) v=i-t.len; /*返回匹配模式串的首字符下标*/ else v=-1; /*返回不匹配标志*/ return v; } KMP 算法 设主串 s 的长度为 n,子串 t 长度为 m。 在 KMP 算法中求 next 数组的时间复杂度为 O(m),在后面的匹配中因主串 s 的下标 不减即不回溯,比较次数可记为 n,所以 KMP 算法总的时间复杂度为 O(n+m)。 例如,设目标串 s=“aaabaaaab”,模式串 t=“aaaab”。s 的长度为 n(n=9),t 的长度为 m(m=5)。 用指针i指示目标串 s的当前比较字符位置,用指针 j指示模式串 t的当前比较字符位置。KMP 上述定义的 next[]在某些情况下尚有缺陷。 例如,模式“aaaab”在和主串“aaabaaaab”匹配时,当 i=3,j=3 时,s.data[3]≠t.data[3], 由 next[j]的指示还需进行 i=3、j=2,i=3、j=1,i=3、j=0 等三次比较。实际上,因为模式中的第 1、 2、3 个字符和第 4 个字符都相等,因此,不需要再和主串中第 4 个字符相比较,而可以将模式一 次向右滑动 4 个字符的位置直接进行 i=4,j=0 时的字符比较。 这就是说,若按上述定义得到 next[j]=k,而模式中 pj=pk,则为主串中字符 si 和 pj 比较不等时
不需要再和pk进行比较,而直接和pnext[k]进行比较,换句话说,此时的next[]应和next[k]相同。为此将next[]修正为nextval[i]：比较t.data[i]和t.data[k]，若不等，则nextval[i]-next[i];若相等nextval[i]=nextval[k]void GetNextval(SqString t,int nextval)int j=0,k=-1;nextval[0]--1;while (j<t.len)if (k=--1 II t.data[i]--t.data[k]j++;k++;if (t.data[i]!=t.data[k]) nextval[i]-k;elsenextval[i]=nextval[k];1else k=nextval[k];3由模式串t求出nextval值intKMPIndexl(SqStrings,SqStringt) int nextval[MaxSize],i=0,j-0,v,GetNextval(t,nextval);while (i<s.len && j<t.len)if (j-=-1 Il s.data[i]-=t. data[i])(i++j++;}/*ij各增1*//*i不变，i后退*/elsej=nextval[i];if(i>=t.len)/*返回匹配模式串的首字符下标*) v=i-t.len, else v=-;/*返回不匹配标志*/return v,m本章小结本章基本学习要点如下(1)理解串和一般线性表之间的差异。(2)重点掌握在顺序串上和链串上实现串的基本运算算法。(3）掌握串的模式匹配算法。（4）灵活运用串这种数据结构解决一些综合应用问题。练习题教材中p98的习题1、2和3。36
36 不需要再和 pk 进行比较,而直接和 pnext[k]进行比较,换句话说,此时的 next[j]应和 next[k]相 同。 为此将 next[j]修正为 nextval[j]： 比较 t.data[j]和 t.data[k]，若不等，则 nextval[j]=next[j];若相等 nextval[j]=nextval[k]; void GetNextval(SqString t,int nextval[]) { int j=0,k=-1; nextval[0]=-1; while (j<t.len) { if (k==-1 || t.data[j]==t.data[k]) { j++;k++; if (t.data[j]!=t.data[k]) nextval[j]=k; else nextval[j]=nextval[k]; } else k=nextval[k]; } } 由模式串 t 求出 nextval 值 int KMPIndex1(SqString s,SqString t) { int nextval[MaxSize],i=0,j=0,v; GetNextval(t,nextval); while (i<s.len && j<t.len) { if (j==-1 || s.data[i]==t.data[j]) { i++;j++; } /*i,j 各增 1*/ else j=nextval[j]; /*i 不变,j 后退*/ } if (j>=t.len) v=i-t.len; /*返回匹配模式串的首字符下标*/ else v=-1; /*返回不匹配标志*/ return v; } 本章小结 本章基本学习要点如下: (1) 理解串和一般线性表之间的差异。 (2)重点掌握在顺序串上和链串上实现串的基本运算算法。 (3) 掌握串的模式匹配算法。 (4) 灵活运用串这种数据结构解决一些综合应用问题。 练习题 教材中 p98 的习题 1、2 和 3