国家级精品课程—《数据结构与算法》 第4章字符串 张铭、赵海燕、王腾蛟、宋国杰、高军 http:/www.ipk.pku.edu.cn/pkuipk/courselsig 北京大学信息科学与技术学院 “数据结构与算法”教学小组 本章主笔:赵海燕 版权所有,转载或翻印必究
国家级精品课程—《数据结构与算法》 张铭、赵海燕、王腾蛟、宋国杰、高军 http://www.jpk.pku.edu.cn/pkujpk/course/sjjg/ 北京大学信息科学与技术学院 “数据结构与算法”教学小组 本章主笔：赵海燕 ©版权所有，转载或翻印必究 第4章 字符串
主要内容 字符串基本概念 字符串的存储结构 字符串运算的算法实现 字符串的模式匹配 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 主要内容 ◼ 字符串基本概念 ◼ 字符串的存储结构 ◼ 字符串运算的算法实现 ◼ 字符串的模式匹配
字符串基本概念 ■字符编码 字符编码顺序 字符串抽象数据类型 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 字符串基本概念 ◼ 字符编码 ◼ 字符编码顺序 ◼ 字符串抽象数据类型
基本概念 字符串,由0个或多个字符号的顺序排列所组成的复 合数据结构,简称“串”( string) 口串的长度:一个字符串所包含的字符个数 口空串:长度为零的串,它不包含任何字符内容 ■特殊的线性表,即元素为字符的线性表 口n(≥0)个字符的有限序列,一般记作 s:“coC1C2.Cn- 其中,S是串名字 CnC, C2 cnr”是串值 c是串中的字符 n是串的长度(即字符个数),长度为0则为空串 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 基本概念 ◼ 字符串，由0个或多个字符/符号的顺序排列所组成的复 合数据结构，简称“串”（string） ❑ 串的长度：一个字符串所包含的字符个数 ❑ 空串：长度为零的串，它不包含任何字符内容 ◼ 特殊的线性表，即元素为字符的线性表 ❑ n ( ≥ 0 ) 个字符的有限序列，一般记作 S : “c0c1c2…cn-1 ” ◼ 其中，S是串名字 ◼ “c0c1c2…cn-1 ”是串值 ◼ ci是串中的字符 ◼ n是串的长度 （即字符个数），长度为0则为空串
字符/符号 字符(char):组成字符串的基本单位 取值依赖于字符集Σ(结点的有限集合) 口二进制字符集:Σ={0,1} 口生物信息中DNA字符集:Σ={AcG,T 口英语语言:Σ={26个字符,标点符号,} 口简体中文标准字符集GB2312:Σ={6763个汉字 标点符号,… “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 字符/符号 ◼ 字符(char) ：组成字符串的基本单位 ◼ 取值依赖于字符集Σ（结点的有限集合） ❑ 二进制字符集：Σ= {0,1} ❑ 生物信息中DNA字符集：Σ = {A,C,G,T} ❑ 英语语言： Σ = {26个字符，标点符号，…} ❑ 简体中文标准字符集 GB2312 ：Σ = {6763个汉字， 标点符号，… } ❑ ……