数据结构与算法 第三章字符串 主讲人张铭 http://db.pku.edu.cn/mzhang/ds zhang@db.pku.edu.cn 北京大学信息科学与技术学院 网络与信息系统研究所 版权所有,转载或翻印必究
数据结构与算法 第三章 字符串 主讲人 张铭 http://db.pku.edu.cn/mzhang/ds mzhang@db.pku.edu.cn 北京大学信息科学与技术学院 网络与信息系统研究所 ©版权所有，转载或翻印必究
主要内容 31字符串抽象数据类型 32字符串的存储结构和类定义 33字符串运算的算法实现 34字符串的模式匹配 北京大学信息学院 版权所有,转载或翻印必究 Page 2
北京大学信息学院 ©版权所有，转载或翻印必究 Page 2 主要内容 ◼ 3.1 字符串抽象数据类型 ◼ 3.2 字符串的存储结构和类定义 ◼ 3.3 字符串运算的算法实现 ◼ 3.4 字符串的模式匹配
3.1字符串抽象数据类型 311基本概念 a312 String抽象数据类型 北京大学信息学院 版权所有,转载或翻印必究 Page 3
北京大学信息学院 ©版权所有，转载或翻印必究 Page 3 3.1字符串抽象数据类型 ◼ 3.1.1 基本概念 ◼ 3.1.2 String抽象数据类型
311基本概念 ■字符串,由0个或多个字符的顺 序排列所组成的复合数据结构, 简称“串”。 m串的长度:一个字符串所包含的 字符个数。 空串:长度为零的串,它不包含 任何字符内容。 北京大学信息学院 版权所有,转载或翻印必究 Page 4
北京大学信息学院 ©版权所有，转载或翻印必究 Page 4 3.1.1 基本概念 ◼ 字符串，由0个或多个字符的顺 序排列所组成的复合数据结构， 简称“串” 。 ◼ 串的长度：一个字符串所包含的 字符个数。 ◼ 空串：长度为零的串，它不包含 任何字符内容
31.11字符串常数和变量 字符串常数 例如:"ln" 字符串变量 北京大学信息学院 版权所有,转载或翻印必究 Page 5
北京大学信息学院 ©版权所有，转载或翻印必究 Page 5 3.1.1.1字符串常数和变量 ◼ 字符串常数 ◼ 例如： "\n" ◼ 字符串变量
31.1.2字符 字符(char):组成字符串的基 本单位 在C和C++中 单字节(8bits) .用ACI码对128个符号(字符 集 charset)进行编码 北京大学信息学院 版权所有,转载或翻印必究 Page 6
北京大学信息学院 ©版权所有，转载或翻印必究 Page 6 3.1.1.2 字符 ◼ 字符(char) ：组成字符串的基 本单位 。 ◼ 在C和C＋＋中 ◼ 单字节（8 bits） ◼ 采用ASCII码对128个符号（字符 集charset）进行编码
31.13字符的编码顺序 为了字符串间比较和运算的便利, 字符编码表一般遵循约定俗成的 “偏序编码规则”。 ■字符偏序:根据字符的自然含义 某些字符间两两可以比较次序 n其实大多数情况下就是字典序 中文字符串有些特例,例如“笔划” 序 北京大学信息学院 版权所有,转载或翻印必究 Page 7
北京大学信息学院 ©版权所有，转载或翻印必究 Page 7 3.1.1.3 字符的编码顺序 ◼ 为了字符串间比较和运算的便利， 字符编码表一般遵循约定俗成的 “偏序编码规则” 。 ◼ 字符偏序：根据字符的自然含义， 某些字符间两两可以比较次序。 ◼ 其实大多数情况下就是字典序 ◼ 中文字符串有些特例，例如“笔划” 序
3114C++标准srng 标准字符串:将C++的 函数库作为字符串 数据类型的方案。 例如: char s[M]P 串的结束标记:"V0 "0是ASCT码中8位B工T全0码, 又称为NUL符。 北京大学信息学院 版权所有,转载或翻印必究 Page 8
北京大学信息学院 ©版权所有，转载或翻印必究 Page 8 3.1.1.4 C++标准string ◼ 标准字符串：将C++的 函数库作为字符串 数据类型的方案。 ◼ 例如：char S[M]; ◼ 串的结束标记：'\0' ◼ '\0'是ASCII码中8位BIT全0码， 又称为NULL符
3114C++标准 string(续) 1.串长函数 int strlen (char *s)i 2,串复制 ar strcpy char *s1, char*s2) ■3.串拼接 char *strcat(char *s1, char *s2) 4.串比较 int strcmp(char *s1, char *s2)i 北京大学信息学院 版权所有,转载或翻印必究 Page 9
北京大学信息学院 ©版权所有，转载或翻印必究 Page 9 3.1.1.4 C++标准string(续) ◼ 1. 串长函数 int strlen(char *s); ◼ 2. 串复制 char *strcpy(char *s1, char*s2); ◼ 3．串拼接 char *strcat(char *s1, char *s2); ◼ 4．串比较 int strcmp(char *s1, char *s2);
3114C++标准 string(续) 5.输入和输出函数 6.定位函数 char xstrchr(char *s, char ci 7.右定位函数 char *strrchr (char *s, char c)i 北京大学信息学院 版权所有,转载或翻印必究 Page 10
北京大学信息学院 ©版权所有，转载或翻印必究 Page 10 3.1.1.4 C++标准string(续) ◼ 5．输入和输出函数 ◼ 6．定位函数 char *strchr(char *s, char c); ◼ 7．右定位函数 char *strrchr(char *s, char c);