北京大学：《数据结构与算法》课程教学资源（实验班PPT课件）第三章 字符串

数据结构与算法 第三章字符串 张铭 http://db.pkuedu.cn/mzhang/ds/ 北京大学信息科学与技术学院 数据结构与算法”教学小组 版权所有,转载或翻印必究

数据结构与算法 第三章 字符串 张铭 http://db.pku.edu.cn/mzhang/DS/ 北京大学信息科学与技术学院 “数据结构与算法 ”教学小组 ©版权所有，转载或翻印必究

主要内容 ■3,1字符串抽象数据类型 32字符串的存储结构和类定义 33字符串运算的算法实现 ■3,4字符串的模式匹配 back 北京大学信息学院 张铭编写@版权所有,转载或翻印必究 Page 2

北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 2 back next 主要内容 „ 3.1 字符串抽象数据类型 „ 3.2 字符串的存储结构和类定义 „ 3.3 字符串运算的算法实现 „ 3.4 字符串的模式匹配

31字符串抽象数据类型 31.1基本概念 n312 String抽象数据类型 back 北京大学信息学院 张铭编写@版权所有,转载或翻印必究 Page 3

北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 3 back next 3.1字符串抽象数据类型 „ 3.1.1 基本概念 „ 3.1.2 String抽象数据类型

311基本概念 ■字符串,由0个或多个字符的顺 序排列所组成的复合数据结构, 简称“串”。 串的长度:一个字符串所包含的 字符个数。 空串:长度为零的串,它不包含 任何字符内容。 back 北京大学信息学院 张铭编写@版权所有,转载或翻印必究 Page 4

北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 4 back next 3.1.1 基本概念 „ 字符串，由0个或多个字符的顺 序排列所组成的复合数据结构， 简称“串”。 „ 串的长度：一个字符串所包含的 字符个数。 „ 空串：长度为零的串，它不包含 任何字符内容

31.1.1字符串常数和变量 字符串常数 例如:"lm 字符串变量 back 北京大学信息学院 张铭编写@版权所有,转载或翻印必究 Page 5

北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 5 back next 3.1.1.1字符串常数和变量 „ 字符串常数 „ 例如： "\n" „ 字符串变量

3112字符 ■字符(char):组成字符串的基 本单位。 在C和C++中 单字节(8bits) 采用 ASCII码对128个符号(字符 集 charset)进行编码 back 北京大学信息学院 张铭编写@版权所有,转载或翻印必究 Page 6

北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 6 back next 3.1.1.2 字符 „ 字符(char) ：组成字符串的基 本单位 。 „ 在C和C＋＋中 „ 单字节（8 bits） „ 采用ASCII码对128个符号（字符 集charset）进行编码

3114C++标准 string 标准字符串:将C++的 函数库作为字符串 数据类型的方案 例如: char s[M] 串的结束标记:"Y0 "0是ASCI码中8位BTT全0码, 又称为NULL符。 back 北京大学信息学院 张铭编写@版权所有,转载或翻印必究 Page 7

北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 7 back next 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.串复制 char strcpy char *s1, charks2); 3.串拼接 char *strcat(char *s1, char *s2) 4.串比较 int strcmp(char *s1, char *s2) back 北京大学信息学院 张铭编写@版权所有,转载或翻印必究 Page 8

北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 8 back next 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 *strchr(char *s, char c)i 7.右定位函数 char * strrchr(char * s, char c) back 北京大学信息学院 张铭编写@版权所有,转载或翻印必究 Page 9

北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 9 back next 3.1.1.4 C++标准string(续) „ 5．输入和输出函数 „ 6．定位函数 char *strchr(char *s, char c); „ 7．右定位函数 char *strrchr(char *s, char c);

312 String抽象数据类型 字符串类( class String): 不采用 char s[M]的形式 而采用一种动态变长的存储结 构 back 北京大学信息学院 张铭编写⊙版权所有,转载或翻印必究 Page 10

北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 10 back next 3.1.2 String抽象数据类型 „ 字符串类（class String）： „ 不采用char S[M]的形式 „ 而采用一种动态变长的存储结 构