国家级精品课程—《数据结构与算法》 第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个汉字， 标点符号，… } ❑ ……
字符编码 ASc编码 单字节(8bits) 口对128个符号(字符集 charset)进行编码 在C和C++中均采用 其他编码方式 口ANS编码(本地化,GB2312、BG5、JS等, 不同ANS编码间互不兼容) 口 UNICODE(国际化,各种语言中的每一个字符 具有唯一的数字编号,便于跨平台的文本转换) “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 字符编码 ◼ ASCII编码 ❑ 单字节（8 bits） ❑ 对128个符号（字符集charset）进行编码 ❑ 在C和C++中均采用 ◼ 其他编码方式 ❑ ANSI编码（本地化，GB2312、BIG5、JIS等， 不同ANSI编码间互不兼容） ❑ UNICODE（国际化，各种语言中的每一个字符 具有唯一的数字编号，便于跨平台的文本转换）
字符的编码顺序 为了字符串间比较和运算的便利,字符编码表 般遵循约定俗成的“偏序编码规则” 字符偏序:根据字符的自然含义,某些字符间两 两可以比较次序 口字典序 口中文字符串有些特例,例如“笔划”序 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 字符的编码顺序 ◼ 为了字符串间比较和运算的便利，字符编码表一 般遵循约定俗成的“偏序编码规则” ◼ 字符偏序：根据字符的自然含义，某些字符间两 两可以比较次序 ❑ 字典序 ❑ 中文字符串有些特例，例如“笔划”序
字符串长度 理论上,一个字符串的长度是任意且有限的, 但在实际的语言中总有一定的长度 口定长:具有一个固定的最大长度,所用内存量始终如 口变长:根据实际需要伸缩。尽管命名为变长,但实际 长度也有限(取决于可用的内存量) “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 字符串长度 ◼ 理论上，一个字符串的长度是任意且有限的， 但在实际的语言中总有一定的长度 ❑ 定长：具有一个固定的最大长度，所用内存量始终如 一 ❑ 变长：根据实际需要伸缩。尽管命名为变长，但实际 长度也有限（取决于可用的内存量）
子串 假设s1,S2是两个串: 1=a0a1a2…an1 2 0u12-Wm-1 其中0≤m≤n,若存在整数i(0≤isnm),使得 j=0,1,…,m-1 同时成立,则称串s2是串s1的子串,或称s包含串s2 口真子串:非空且不为自身的子串。空串是任意串的子串 口任意串S都是S本身的子串 子串函数 口提取、插入、寻找、删除 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 子串 ◼ 假设s1，s2 是两个串： s1 = a0a1a2…an-1 s2 = b0b1b2…bm-1 其中0 ≤ m ≤ n, 若存在整数i (0 ≤ i ≤n-m)，使得 bj = ai+j, j = 0,1,…,m-1 同时成立，则称串s2是串s1的子串，或称s1包含串s2 ❑ 真子串：非空且不为自身的子串。空串是任意串的子串 ❑ 任意串S 都是S本身的子串 ◼ 子串函数 ❑ 提取、插入、寻找、删除 …
字符串数据类型 因语言而不同 口简单类型 口复合类型 字符串常数和变量 口字符串常数( string literal) 例如:“以 a student 口字符串变量 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 字符串数据类型 ◼ 因语言而不同 ❑ 简单类型 ❑ 复合类型 ◼ 字符串常数和变量 ❑ 字符串常数（string literal） ◼ 例如： “\n”, “a”，“student”… ❑ 字符串变量