内容提要
? 5.1 串及其操作
? 串的定义
? 串的基本操作
? 5.2 串的表示和实现
? 顺序存储表示
? 串的块链存储表示
? 5.3 串的模式匹配算法
? 求子串位置的定位函数
? 模式匹配的一种改进算法
? 5.4串操作应用举例
? 文本编辑
? 建立词索引表
5.1 串及其操作
1、串的逻辑结构定义
串 (String)(或字符串 )：是由零个或多个字符组成的有
限序列。一般记为,s=‘a1a2…an’ (n ?0) 其中,s是串
的名，用单引号括起来的字符序列是串的值； ai(1? i?
n)可以是字母、数字或其他字符；串中字符的数目 n称
为串的长度。零个字符的串称为空串 (null string)，它
的长度为零。（空串与空格串的区别）
子串,串中任意个连续字符构成的子序列
串相等,当且仅当这两个串的值相等。也就是说，只
有当两个串的长度相等，并且各个对应位置的字符串
都相等时才相等。
串值必须用一对单引号括起来，但单引号本身不
属于串，它的作用只是为了避免与变量名或数的
常量混淆而已。
串及其操作 (cont’d)
2,串的基本操作
串的基本操作,
赋值 复制
比较 求长度
串连接 子串定位
取子串 串插入
串删除 串替换
普通线性表操作的最基本单位是结点，
而字符串操作的基本单位是串或子串
5.2 串的表示和实现
1、字符串的存储表示
(1)顺序存储
利用静态数组存放字符串
(2)堆分配存储
利用动态分配的内存存放字符串
(3)链式存储
块链结构, #define N 5 //N决定存储密度
typedef struct strnode
{char sdata[N];
struct strnode *next;
}STRNODE;
串的表示和实现 (cont’d)
(3)链式存储
块链结构, #define N 5 //N决定存储密度
typedef struct strnode
{char sdata[N];
struct strnode *next;
}STRNODE;
ABCDE FGH ^
在 D后面插入 "OOO"后：
ABCDO OOEFG H ^
串的表示和实现 (cont’d)
2、字符串基本操作的实现
(1)串的联接
利用截尾法进行处理
(2) 求两个串的最长公共子串
void maxcomstr(char s[],char t[])//串采用顺序存储结构
{int index=0,lens,lent,length=0,length1,i=0,j,k;
lens=strlen(s);lent=strlen(t);
while(i<lens)//当串 s没完,i是串 s的下标
{j=0;
while(j<lent)//当串 t没完,j是串 t的下标
{if(s[i]==t[j]) //遇到相等的字符,继续找相等字符构成子串
{length1=1;
for(k=1;s[i+k]==t[j+k];k++)length1++;
if(length1>length){index=i;length=length1;}
/*记下最长子串的位置和长度 */
j+=length1;/*从位置 j开始找下一个公共子串 */
}//if
else j++;
}//while (j
串的表示和实现 (cont’d)
(2)求两个串的最长公共子串
i++;
}//while(i
printf("最长子串,");
for(k=0;k<length;k++)printf("%c",s[index+k]);printf("\n");
}
int strindex(char *s,char *t,int beginpos)
{//s是主串,t是模式串，从 s的 beginpos处开始查找 t的位置
char *p,*q;
while(1)
{p=s+beginpos;q=t;
while(*p&&*q&&*p==*q){p++;q++;}
if(*q==0)return beginpos; //匹配，返回模式串的位置
else if(*p==0) return -1; //未找到模式串，匹配不成功
else beginpos++;//从 beginpos＋ 1处开始重新匹配
}//while(1
}
5.3 串的模式匹配算法
1、字符串模式匹配 普通算法
算法思想,
每当一趟匹配过程中出现字
符比较不等时，不需回溯 i
指针，而是利用已经得到的
“部分匹配”的结果将模式
向右“滑动”进可能远的一
段距离后，继续进行比较。
串的模式匹配算法 (cont’d)
? 2,字符串模式匹配的 KMP算法
第一趟匹配 a b a b c a b c a c b a b
a b c
i = 3
j = 3
i
第二趟匹配 a b a b c a b c a c b a b
a b c a c
i = 7
j = 1 j = 5
第三趟匹配 a b a b c a b c a c b a b
(a) b c a c
i i = 11
j = 2 j = 6
算法思想,
(1)对于象 "1234abcd"这样的模式串,KMP算法
与普通算法没有什么不同，但对于 "123a123b"
这样的模式串,KMP的算法就尽显优势。也就
是说，如果模式串本身包含有自身重复子串，
KMP算法会更快。
(2)与普通算法相比,KMP算法在比较失败时，
并没有一切推倒重来，而是巧妙利用的模式串
“包含重复子串”的特征，减少了比较的次数。
串的模式匹配算法 (cont’d)
(3)用大写字母表示子串，小写字母表示串中的
字符，假设当比较操作进行到主串 S的下标 j处
时，比较失败。这是模式串 T的当前字符的下
标时 k，并且 T[0..k]=P(T[m])P(T[k]),T[m]!=T[k],
也就是说，比较失败之前的模式串具有重复子
串。这时我们可以将 S看成是 S=XPaP(S[j])。
面要做的不是将 beginpos++，推倒重来，而是
直接将 T[m]与 S[j]进行比较。这种操作称为模
式串的滑动。每当比较失败就滑动一次，这样
可以有效减少比较次数。
(4)关键一点是滑动到哪里比较合适，也就是说，
如何确定 m的值。 m被称为 k的 next值。
(5)如果已知 k的 next值是 m,k+1的 next值如何
求？这是解决问题的突破口，因为我们已知 0
的 next值是－ 1,1的 next值是 0.
能者为之
? 2,字符串模式匹配的 KMP算法
串的模式匹配算法 (cont’d)
? 2,字符串模式匹配的 KMP算法
第一趟匹配 a b a b c a b c a c b a b
a b c
i = 3
j = 3
i
第二趟匹配 a b a b c a b c a c b a b
a b c a c
i = 7
j = 1 j = 5
第三趟匹配 a b a b c a b c a c b a b
(a) b c a c
i i = 11
j = 2 j = 6
0 当 j=1时
next[j]= Max{k|1<k<j且‘ p1…p k-1’=‘pjj-k+1…pj j-
1’}
当此集合不空时
1 其他情况
j 1 2 3 4 5 6 7 8
模式串 a b a a b c a c
next[j] 0 1 1 2 2 3 1 2
5.4 串操作应用举例
1、文本编辑
? 文本编辑程序是一个面向用户的系统服务程序，广泛用于源
程序的输入和修改，甚至用于报刊和书籍的编辑排版以及办
公室的公文书信的起草和润色。
? 文本编辑的实质是修改字符数据的形式或格式。
? 各种文本编辑程序的功能强弱不同，但是其基本操作是一致
的，一般都包括串的查找、插入和删除等基本操作。
文本编辑程序的设计：用户可以利用换页符和换行符把文本划分
为若干页，每页有若干行。可以把文本看承是一个字符串，
称为文本串，页则是文本串的子串，行又是页的子串。
2、建立词索引表
? 信息检索是计算机应用的重要领域之一。
? 主要操作是在大量的存放在磁盘上的信息中查询一个特定的
信息，为了提高效率，一个重要的问题是建立一个好的索引
系统。
? 5.1 串及其操作
? 串的定义
? 串的基本操作
? 5.2 串的表示和实现
? 顺序存储表示
? 串的块链存储表示
? 5.3 串的模式匹配算法
? 求子串位置的定位函数
? 模式匹配的一种改进算法
? 5.4串操作应用举例
? 文本编辑
? 建立词索引表
5.1 串及其操作
1、串的逻辑结构定义
串 (String)(或字符串 )：是由零个或多个字符组成的有
限序列。一般记为,s=‘a1a2…an’ (n ?0) 其中,s是串
的名，用单引号括起来的字符序列是串的值； ai(1? i?
n)可以是字母、数字或其他字符；串中字符的数目 n称
为串的长度。零个字符的串称为空串 (null string)，它
的长度为零。（空串与空格串的区别）
子串,串中任意个连续字符构成的子序列
串相等,当且仅当这两个串的值相等。也就是说，只
有当两个串的长度相等，并且各个对应位置的字符串
都相等时才相等。
串值必须用一对单引号括起来，但单引号本身不
属于串，它的作用只是为了避免与变量名或数的
常量混淆而已。
串及其操作 (cont’d)
2,串的基本操作
串的基本操作,
赋值 复制
比较 求长度
串连接 子串定位
取子串 串插入
串删除 串替换
普通线性表操作的最基本单位是结点，
而字符串操作的基本单位是串或子串
5.2 串的表示和实现
1、字符串的存储表示
(1)顺序存储
利用静态数组存放字符串
(2)堆分配存储
利用动态分配的内存存放字符串
(3)链式存储
块链结构, #define N 5 //N决定存储密度
typedef struct strnode
{char sdata[N];
struct strnode *next;
}STRNODE;
串的表示和实现 (cont’d)
(3)链式存储
块链结构, #define N 5 //N决定存储密度
typedef struct strnode
{char sdata[N];
struct strnode *next;
}STRNODE;
ABCDE FGH ^
在 D后面插入 "OOO"后：
ABCDO OOEFG H ^
串的表示和实现 (cont’d)
2、字符串基本操作的实现
(1)串的联接
利用截尾法进行处理
(2) 求两个串的最长公共子串
void maxcomstr(char s[],char t[])//串采用顺序存储结构
{int index=0,lens,lent,length=0,length1,i=0,j,k;
lens=strlen(s);lent=strlen(t);
while(i<lens)//当串 s没完,i是串 s的下标
{j=0;
while(j<lent)//当串 t没完,j是串 t的下标
{if(s[i]==t[j]) //遇到相等的字符,继续找相等字符构成子串
{length1=1;
for(k=1;s[i+k]==t[j+k];k++)length1++;
if(length1>length){index=i;length=length1;}
/*记下最长子串的位置和长度 */
j+=length1;/*从位置 j开始找下一个公共子串 */
}//if
else j++;
}//while (j
串的表示和实现 (cont’d)
(2)求两个串的最长公共子串
i++;
}//while(i
printf("最长子串,");
for(k=0;k<length;k++)printf("%c",s[index+k]);printf("\n");
}
int strindex(char *s,char *t,int beginpos)
{//s是主串,t是模式串，从 s的 beginpos处开始查找 t的位置
char *p,*q;
while(1)
{p=s+beginpos;q=t;
while(*p&&*q&&*p==*q){p++;q++;}
if(*q==0)return beginpos; //匹配，返回模式串的位置
else if(*p==0) return -1; //未找到模式串，匹配不成功
else beginpos++;//从 beginpos＋ 1处开始重新匹配
}//while(1
}
5.3 串的模式匹配算法
1、字符串模式匹配 普通算法
算法思想,
每当一趟匹配过程中出现字
符比较不等时，不需回溯 i
指针，而是利用已经得到的
“部分匹配”的结果将模式
向右“滑动”进可能远的一
段距离后，继续进行比较。
串的模式匹配算法 (cont’d)
? 2,字符串模式匹配的 KMP算法
第一趟匹配 a b a b c a b c a c b a b
a b c
i = 3
j = 3
i
第二趟匹配 a b a b c a b c a c b a b
a b c a c
i = 7
j = 1 j = 5
第三趟匹配 a b a b c a b c a c b a b
(a) b c a c
i i = 11
j = 2 j = 6
算法思想,
(1)对于象 "1234abcd"这样的模式串,KMP算法
与普通算法没有什么不同，但对于 "123a123b"
这样的模式串,KMP的算法就尽显优势。也就
是说，如果模式串本身包含有自身重复子串，
KMP算法会更快。
(2)与普通算法相比,KMP算法在比较失败时，
并没有一切推倒重来，而是巧妙利用的模式串
“包含重复子串”的特征，减少了比较的次数。
串的模式匹配算法 (cont’d)
(3)用大写字母表示子串，小写字母表示串中的
字符，假设当比较操作进行到主串 S的下标 j处
时，比较失败。这是模式串 T的当前字符的下
标时 k，并且 T[0..k]=P(T[m])P(T[k]),T[m]!=T[k],
也就是说，比较失败之前的模式串具有重复子
串。这时我们可以将 S看成是 S=XPaP(S[j])。
面要做的不是将 beginpos++，推倒重来，而是
直接将 T[m]与 S[j]进行比较。这种操作称为模
式串的滑动。每当比较失败就滑动一次，这样
可以有效减少比较次数。
(4)关键一点是滑动到哪里比较合适，也就是说，
如何确定 m的值。 m被称为 k的 next值。
(5)如果已知 k的 next值是 m,k+1的 next值如何
求？这是解决问题的突破口，因为我们已知 0
的 next值是－ 1,1的 next值是 0.
能者为之
? 2,字符串模式匹配的 KMP算法
串的模式匹配算法 (cont’d)
? 2,字符串模式匹配的 KMP算法
第一趟匹配 a b a b c a b c a c b a b
a b c
i = 3
j = 3
i
第二趟匹配 a b a b c a b c a c b a b
a b c a c
i = 7
j = 1 j = 5
第三趟匹配 a b a b c a b c a c b a b
(a) b c a c
i i = 11
j = 2 j = 6
0 当 j=1时
next[j]= Max{k|1<k<j且‘ p1…p k-1’=‘pjj-k+1…pj j-
1’}
当此集合不空时
1 其他情况
j 1 2 3 4 5 6 7 8
模式串 a b a a b c a c
next[j] 0 1 1 2 2 3 1 2
5.4 串操作应用举例
1、文本编辑
? 文本编辑程序是一个面向用户的系统服务程序，广泛用于源
程序的输入和修改，甚至用于报刊和书籍的编辑排版以及办
公室的公文书信的起草和润色。
? 文本编辑的实质是修改字符数据的形式或格式。
? 各种文本编辑程序的功能强弱不同，但是其基本操作是一致
的，一般都包括串的查找、插入和删除等基本操作。
文本编辑程序的设计：用户可以利用换页符和换行符把文本划分
为若干页，每页有若干行。可以把文本看承是一个字符串，
称为文本串，页则是文本串的子串，行又是页的子串。
2、建立词索引表
? 信息检索是计算机应用的重要领域之一。
? 主要操作是在大量的存放在磁盘上的信息中查询一个特定的
信息，为了提高效率，一个重要的问题是建立一个好的索引
系统。
