两个串相等，当且仅当两个串长度相同，并且各个对应位
置的字符都相同。
s1=“abcd”,s2=“aBcd”
s1和s2不相等。
北京邮电大学世纪学院
算法与数据结构 第四章
4.1.2 串的基本操作
（1）字符串的长度计算 （2）字符串的复制 （3）字符串的连接 （4）字符串的替换 （5）字符串的插入 （6）字符串的删除 （7）字符串的比较
算法与数据结构 第四章
（3）空格串
由一个或多个空格组成的串，不等于空串，长度是串中包 含空格个数。
串的实例
“This is a string” “string” “ “” ”
串长度
16 6 1 0 空格也算一个字符
注
空格串: 仅由一个或多个空格组成的串 空串: 长度为0的串称为空串，它不包括任何 字符 串中所包含的字符可以是字母、数字或其他 字符，这依赖于具体计算机所允许的字符集
北京邮电大学世纪学院
第四章 串
目 录
4.1 串的概念及基本运算 4.2 串的存储结构 4.3 串的查找——模式匹配
内容特殊的线性表——（字符）串
非数值数据
源码翻译为机器码
利用计算机把一种自然源语言转变为
另一种自然目标语言的过程，一般指 自然语言之间句子和全文的翻译。
机器 翻译
字符 编译
搜索 引擎
typedef struct { } char str[MAXSIZE]; int lenrth; String; //串的长度
北京邮电大学世纪学院
算法与数据结构 第四章
4.1.3 链式串
1. 单字符结点链 可用单链表方式来存储串值。链串与单链表的差异只
是它的结点数据域为字符。
typedef struct Node { char data; struct Node *next; } SCharNode;
子串 t 在主串 s 中的位置为3。 ab abc abcac
s = “The C Program is not c program” , t = “program” 子串 t 在主串 s 中的位置为 24 。
北京邮电大学世纪学院
算法与数据结构 第四章
（7）串的比较
“a0 a1…… an”
“b0b 1…… bm”
北京邮电大学世纪学院
算法与数据结构 第四章
2. 块链
typedef struct Node
{ char data[Number]; //块链
struct Node *next; } NCharNode;
算法与数据结构 第四章
4.3 串的查找—模式匹配
字符串的查找——模式匹配
搜索引擎——做字符串査找匹配的工作。 模式匹配算法是搜索引擎的关键， 它直接影响系统的实时性能。
（8）抽取字符串
（9）字符串的分割 （10）字符串的查找
北京邮电大学世纪学院
算法与数据结构 第四章
C语言中字符串操作函数
北京邮电大学世纪学院
算法与数据结构 第四章
北京邮电大学世纪学院
算法与数据结构 第四章
例4.1 C语言中的串函数
北京邮电大学世纪学院
算法与数据结构 第四章
北京邮电大学世纪学院
串的比较，按照字符的ASII码进行比较：
先比较第一个字符的大小 “abc”>”ABC” “abs”<“ads” “abcd”>”abc”
若 a0 b0 ，则a<b；
若 a0 b0 ，则a>b；
若 a b ，比较第二个字符； 0 0
依次类推
北京邮电是指根据一定的策略、 运用特定的计算机程序从互联 网上搜集信息，在对信息进行 组织和处理后，为用户提供检 索服务，将用户检索相关的信 息展示给用户的系统。
字符串 处理
文献 查询
计算机将检索者输入检索系 统的检索提问 ( 即检索标识 ) 按检索者预先制定的检索策 略与系统文档（机读数据库） 中的存贮标识进行类比、匹 配运算 ,通过“人机对话”而 检索出所需要的文献
算法与数据结构 第四章
4.1 串的概念及基本运算
北京邮电大学世纪学院
算法与数据结构 第三章
4.1.1 串的基本概念
1. 串的定义
串是一种特殊的线性表，它是由n (≥ 0)个字符组成的 有限序列。 记作 s = “a1,a2, a3, ... an” s—串名， a1,a2, a3, ... an—串值
“你好”
4
北京邮电大学世纪学院
算法与数据结构 第四章
（4）子串、主串
串中任意一个连续的字符组成的子序列称为该串的子串，
空串是任何串的子串。包含子串的字符串称为主串。 c = “ DATA STRUCTURE” f=“DATA” f是c的子串； 空串 是c的子串； c是f， 的主串。
北京邮电大学世纪学院
ai是串中字符，n是串的长度
a1 a2 ... ai ... an
ai是字符
北京邮电大学世纪学院
算法与数据结构 第四章
s1=“Student”
串名
串值
注意：串中字符区分大小写！
2. 基本术语
（1）串长度
串中所包含的字符个数。
（2）空串 零个字符的串，称为空串，它的长度为零，记为 。
北京邮电大学世纪学院
北京邮电大学世纪学院
算法与数据结构 第四章
串的模式匹配又称为字串定位运算：扫描主串S，寻
找子串T在主串S中首次出现的位置。
主串S称为目标串； 字串T称为模式串。
北京邮电大学世纪学院
算法与数据结构 第四章
匹配结果
成功
返回子串T在S中的起始位置
失败
返回约定标记
模式匹配的常用算法：BF算法和KMP算法
算法与数据结构 第四章
（5）字符在串中的位置
一个字符在序列中的序号称为该字符在串中的位置。
c = “ DATA STRUCTURE”
‘D’的位置是1；
‘S’的位置是6.
北京邮电大学世纪学院
算法与数据结构 第四章
（6）子串的位置
子串t 在主串S中的位置是指：主串s 中第一个与t相同的子
串的首字母在主串中的位置。 s = “ababcabcac” , t = “abc”
算法与数据结构 第四章
算法与数据结构 第四章
4.2 串的存储结构
北京邮电大学世纪学院
算法与数据结构 第四章
由于串是一种特殊的线性表，它的每个结点仅由 一个字符组成，因此存储串的方法也同样可以采用 顺序存储或链式存储。
北京邮电大学世纪学院
算法与数据结构 第四章
4.1.2 顺序串
串中的字符顺序地存储在内存一片相邻的空间。