数据结构与算法 第三章字符串 主讲人张铭 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" ◼ 字符串变量