,数据结构,
第四章
数据结构
tjm
第四章 串
4.1 串类型的定义
4.2 串的表示和实现
4.2.1 定长顺序存储表示
4.2.2 堆分配存储表示
4.2.3 串的块链存储表示
4.3 串的模式匹配算法
数据结构
tjm
4.1 串类型的定义
一、串和基本概念
串 (String)是零个或多个字符组成的有限序列 。一
般记作 S=?a1a2a3…an?，其中 S 是串名，双引号括
起来的字符序列是串值； ai(1≦ i≦ n)可以是字母、
数字或其它字符；串中所包含的字符个数称为该
串的长度。长度为零的串称为空串，它不包含任
何字符。
通常将仅由一个或多个空格组成的串称为空白串。
注意：空串和空白串不同，例如 ‘ ’ 和 ‘’ 分别
表示长度为 1的空白串和长度为 0的空串。
数据结构
tjm
子串,串中任意个连续字符组成的子序列
主串,包含子串的串
子串在主串中的序号（或位置）,子串在主串中首次
出现时的该子串的首字符对应的主串中的序号
例,设 A=“This is a string” B=“is”
则 B是 A的子串,A为主串,B在 A中的序号（或位置）
为 3
特别地,空串是任意串的子串，任意串是其自身
的子串 。
二、串的抽象数据定义
串的抽象数据类型定义见书 P71
数据结构
tjm
三、串的基本操作
几种在 C语言中常用的串运算：
（ 1）求串长 (length)：
int strlen(char *s);
（ 2）串复制 (copy)：
char *strcpy(char *to,char *from);
(3)联接 (concatenation)：
char strcat(char *to,char *from)
(4)串比较（ compare)
int strcmp(char *s1,char *s2);
（ 5）字符定位 (index)
char strchr(char *s,char c);
数据结构
tjm
例、串的定位 index(s,t,pos)
算法思想：在主串中取从第 i个字符起、长度和
串 t相等的子串和 t比较，若相等，则求得函数值
为 i，否则值增 1直至 S中不存在和串 t相等的子串
为止。
算法参见 P79
数据结构
tjm
4.2 串的表现和实现
4.2.1定长顺序存储表示
定长顺序存储表示,也称为静态存储分配的顺序表。
它是用一组连续的存储单元来存放串中的字符序列。
所谓定长顺序存储结构，是直接使用定长的字符数
组来定义，数组的上界预先给出：
#define MAXSTRLEN 255
typedef char Sstring[MAXSTRLEN＋ 1];
串长度的表示方法：
方法 1：用下标为 0的元素存储串长度。
方法 2,使用一个不会出现在串中的特殊字符在串
值的尾部来表示串的结束。例如,C语言中以字符
‵ \0′ 表示串值的终结。
数据结构
tjm
4.2.2堆分配存储表示
这种存储表示的 特点 是,仍以一组地址连续的存储
单元存放串值字符序列，但它们的存储空间是在程
序执行过程中动态分配而得 。所以也称为动态存储
分配的顺序表。在 C语言中利用函数 malloc()、
free()来根据实际需要动态分配和释放字符数组空
间。这样定义的顺序串类型也有两种形式。
1,typedef char * string; //c中的串相
当于此类型定义
2,typedef struct
{ char *ch;
int length;
}hstring;
数据结构
tjm
4.2.3 串的块链存储结构
链式存储结构类似线性链表，但需要考虑每个结
点是存放一个字符还是多个字符。一个字符的，
插入、删除、求长度非常方便，但存储效率低。
多个字符的，改善了效率，在处理大字符串时很
有效，可用特殊符号来填满未充分利用的结点，
但插入、删除不方便。
附设了头尾指针，并给出了当前串的长度的串的
链式存储结构称为块链存储结构。（参见 P78类
型定义）
数据结构
tjm
s t r i n g # # ^
head
s t r i n g ^
head
串值所占存储位
存储密度＝ —————————
实际分配的存储位
数据结构
tjm
4.3 串的模式匹配算法
子串定位运算又称为模式匹配或串匹配，此运
算的应用非常广泛。例如，文本编辑程序中，
经常要查找某一特定单词出现的位置。解此问
题的有效算法能极大地提高文本编辑程序的响
应性能。
串的模式匹配定义,在主串中寻找子串在串中的
位置。在模式匹配中，子串称为 模式串,主 串
称为 目标串 。
一、最简单的串匹配算法（算法参见 P79）
数据结构
tjm
s, a b a b c a b c a c b a b
s, a b c
i
j
s, a b a b c a b c a c b a b
t, a b c
s, a b a b c a b c a c b a b
t, a b c
i指针回溯
数据结构
tjm
二、首尾匹配算法
先比较模式串的第一个字符，然后再比较模式串
的最后一个字符，最后比较第 2个到第 n－ 1个字符。
三,KMP算法
基本思想,
a b ct d a b ??????
i
j
匹配失败
?????? a b c d a b a ???s ??? ???
a b ct d a b c a c b ???
1 2 3j 4 5 6 7 8 9 10
a b ct a b c a c a b
0 1 1next 1 2 3 4 5 1 2
数据结构
tjm
4.4 串操作应用举例
4.4.1 文本编辑
文本可被看作一个字符串，称为文本串。页则
是文本串的子串，行又是页的子串。
页号 起始行号
页表
…………
行号 起始地址 长度
行表
…………
第四章
数据结构
tjm
第四章 串
4.1 串类型的定义
4.2 串的表示和实现
4.2.1 定长顺序存储表示
4.2.2 堆分配存储表示
4.2.3 串的块链存储表示
4.3 串的模式匹配算法
数据结构
tjm
4.1 串类型的定义
一、串和基本概念
串 (String)是零个或多个字符组成的有限序列 。一
般记作 S=?a1a2a3…an?，其中 S 是串名，双引号括
起来的字符序列是串值； ai(1≦ i≦ n)可以是字母、
数字或其它字符；串中所包含的字符个数称为该
串的长度。长度为零的串称为空串，它不包含任
何字符。
通常将仅由一个或多个空格组成的串称为空白串。
注意：空串和空白串不同，例如 ‘ ’ 和 ‘’ 分别
表示长度为 1的空白串和长度为 0的空串。
数据结构
tjm
子串,串中任意个连续字符组成的子序列
主串,包含子串的串
子串在主串中的序号（或位置）,子串在主串中首次
出现时的该子串的首字符对应的主串中的序号
例,设 A=“This is a string” B=“is”
则 B是 A的子串,A为主串,B在 A中的序号（或位置）
为 3
特别地,空串是任意串的子串，任意串是其自身
的子串 。
二、串的抽象数据定义
串的抽象数据类型定义见书 P71
数据结构
tjm
三、串的基本操作
几种在 C语言中常用的串运算：
（ 1）求串长 (length)：
int strlen(char *s);
（ 2）串复制 (copy)：
char *strcpy(char *to,char *from);
(3)联接 (concatenation)：
char strcat(char *to,char *from)
(4)串比较（ compare)
int strcmp(char *s1,char *s2);
（ 5）字符定位 (index)
char strchr(char *s,char c);
数据结构
tjm
例、串的定位 index(s,t,pos)
算法思想：在主串中取从第 i个字符起、长度和
串 t相等的子串和 t比较，若相等，则求得函数值
为 i，否则值增 1直至 S中不存在和串 t相等的子串
为止。
算法参见 P79
数据结构
tjm
4.2 串的表现和实现
4.2.1定长顺序存储表示
定长顺序存储表示,也称为静态存储分配的顺序表。
它是用一组连续的存储单元来存放串中的字符序列。
所谓定长顺序存储结构，是直接使用定长的字符数
组来定义，数组的上界预先给出：
#define MAXSTRLEN 255
typedef char Sstring[MAXSTRLEN＋ 1];
串长度的表示方法：
方法 1：用下标为 0的元素存储串长度。
方法 2,使用一个不会出现在串中的特殊字符在串
值的尾部来表示串的结束。例如,C语言中以字符
‵ \0′ 表示串值的终结。
数据结构
tjm
4.2.2堆分配存储表示
这种存储表示的 特点 是,仍以一组地址连续的存储
单元存放串值字符序列，但它们的存储空间是在程
序执行过程中动态分配而得 。所以也称为动态存储
分配的顺序表。在 C语言中利用函数 malloc()、
free()来根据实际需要动态分配和释放字符数组空
间。这样定义的顺序串类型也有两种形式。
1,typedef char * string; //c中的串相
当于此类型定义
2,typedef struct
{ char *ch;
int length;
}hstring;
数据结构
tjm
4.2.3 串的块链存储结构
链式存储结构类似线性链表，但需要考虑每个结
点是存放一个字符还是多个字符。一个字符的，
插入、删除、求长度非常方便，但存储效率低。
多个字符的，改善了效率，在处理大字符串时很
有效，可用特殊符号来填满未充分利用的结点，
但插入、删除不方便。
附设了头尾指针，并给出了当前串的长度的串的
链式存储结构称为块链存储结构。（参见 P78类
型定义）
数据结构
tjm
s t r i n g # # ^
head
s t r i n g ^
head
串值所占存储位
存储密度＝ —————————
实际分配的存储位
数据结构
tjm
4.3 串的模式匹配算法
子串定位运算又称为模式匹配或串匹配，此运
算的应用非常广泛。例如，文本编辑程序中，
经常要查找某一特定单词出现的位置。解此问
题的有效算法能极大地提高文本编辑程序的响
应性能。
串的模式匹配定义,在主串中寻找子串在串中的
位置。在模式匹配中，子串称为 模式串,主 串
称为 目标串 。
一、最简单的串匹配算法（算法参见 P79）
数据结构
tjm
s, a b a b c a b c a c b a b
s, a b c
i
j
s, a b a b c a b c a c b a b
t, a b c
s, a b a b c a b c a c b a b
t, a b c
i指针回溯
数据结构
tjm
二、首尾匹配算法
先比较模式串的第一个字符，然后再比较模式串
的最后一个字符，最后比较第 2个到第 n－ 1个字符。
三,KMP算法
基本思想,
a b ct d a b ??????
i
j
匹配失败
?????? a b c d a b a ???s ??? ???
a b ct d a b c a c b ???
1 2 3j 4 5 6 7 8 9 10
a b ct a b c a c a b
0 1 1next 1 2 3 4 5 1 2
数据结构
tjm
4.4 串操作应用举例
4.4.1 文本编辑
文本可被看作一个字符串，称为文本串。页则
是文本串的子串，行又是页的子串。
页号 起始行号
页表
…………
行号 起始地址 长度
行表
…………
