数据结构与算法 第三章字符串 张铭 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]的形式 而采用一种动态变长的存储结 构
