《国家级精品课程数据结构与算法知识讲解》由会员分享，可在线阅读，更多相关《国家级精品课程数据结构与算法知识讲解（66页珍藏版）》请在金锄头文库上搜索。
1、国家级精品课程数据结构与算法,张铭、赵海燕、王腾蛟、宋国杰、高军 北京大学信息科学与技术学院 “数据结构与算法”教学小组 本章主笔：赵海燕 版权所有，转载或翻印必究,第4章 字符串,主要内容,字符串基本概念 字符串的存储结构 字符串运算的算法实现 字符串的模式匹配,字符串基本概念,字符编码 字符编码顺序 字符串抽象数据类型,基本概念,字符串，由0个或多个字符/符号的顺序排列所组成的复合数据结构，简称“串”（string） 串的长度：一个字符串所包含的字符个数 空串：长度为零的串，它不包含任何字符内容 特殊的线性表，即元素为字符的线性表 n ( 0 ) 个字符的有限序列，一般记作 S : “c0
2、c1c2cn-1” 其中，S是串名字 “c0c1c2cn-1”是串值 ci是串中的字符 n是串的长度 （即字符个数），长度为0则为空串,字符编码,ASCII编码 单字节（8 bits） 对128个符号（字符集charset）进行编码 在C和C+中均采用 其他编码方式 ANSI编码（本地化，GB2312、BIG5、JIS等，不同ANSI编码间互不兼容） UNICODE（国际化，各种语言中的每一个字符具有唯一的数字编号，便于跨平台的文本转换）,字符的编码顺序,为了字符串间比较和运算的便利，字符编码表一般遵循约定俗成的“偏序编码规则” 字符偏序：根据字符的自然含义，某些字符间两两可以比较次序 字典序
3、 中文字符串有些特例，例如“笔划”序,字符串长度,理论上，一个字符串的长度是任意且有限的，但在实际的语言中总有一定的长度 定长：具有一个固定的最大长度，所用内存量始终如一 变长：根据实际需要伸缩。尽管命名为变长，但实际长度也有限（取决于可用的内存量）,子串,假设s1，s2 是两个串： s1 = a0a1a2an-1 s2 = b0b1b2bm-1 其中0 m n, 若存在整数i (0 i n-m)，使得 bj = ai+j, j = 0,1,m-1 同时成立，则称串s2是串s1的子串，或称s1包含串s2 真子串：非空且不为自身的子串。空串是任意串的子串 任意串S 都是S本身的子串 子串函数 提
4、取、插入、寻找、删除 ,字符串数据类型,因语言而不同 简单类型 复合类型 字符串常数和变量 字符串常数（string literal） 例如： “n”, “a”，“student” 字符串变量,C+的标准string,标准字符串：将C/C+的函数库作为字符串数据类型的方案 例如：char SM;定义了字符串变量 e.g., char s17 = “value”; 串的结束标记：0 0是ASCII码中8位BIT全0码，又称为NULL符， 专门用于结束标志 字符串的实际长度为 M-1 注意： s1 = s2,C+标准string,串长函数 int strlen(char *s); 串复制 char
5、 *strcpy(char *s1, char*s2); 串拼接 char *strcat(char *s1, char *s2); 串比较 (注意) int strcmp(char *s1, char *s2); 输入和输出函数 cin cout 定位函数 char *strchr(char *s, char c); 右定位函数 char *strrchr(char *s, char c);,String抽象数据类型,字符串类（class String）： 适应字符串长度动态变化的复杂性 不再以字符数组char SM的形式出现，而采用一种动态变长的存储结构,C+ String 部分操作列表,
6、字符串的存储结构和实现,字符串的顺序存储 字符串类class String的存储结构 C+标准串的运算实现 String类的运算实现,字符串的顺序存储,对于串长变化不大的字符串，可以有三种处理方案： （1）用S0作为记录串长的存储单元 ( Pascal) 缺点：限制了串的最大长度不能超过256 （2）为存储串的长度，另辟一个存储的地方 缺点：串的最大长度一般是静态给定的，不是动态申请数组空间 （3）用一个特殊的末尾标记0 ( C/C+) 例如：C+语言的string函数库（include ）采用这一存储结构,字符串类class String的存储结构,private: / 具体实现的字符串存储
7、结构 char *str;/ 字符串的数据表示 int size;/ 串的当前长度,例如， String s1 = Hello;,字符串运算的算法实现,1. 串长函数 int strlen(char *s); 2. 串复制 char *strcpy(char *d, char*s); 3串拼接 char *strcat(char *s1, char *s2); 4串比较 int strcmp(char *s1, char *s2); 5. 寻找字符 char * strchr(char *d, char ch) char * strrchr(char *d, char ch),C+标准串运算的
8、实现,/ 字符串的复制 char *strcpy(char *d, char *s) int i =0; while (si != 0) di = si; i+; di = 0; return d; / 问题？,C+标准串运算的实现,/ 字符串的比较 int strcmp(const char *s1, const char *s2) int i = 0; while (s2i != 0 ,C+标准串运算的实现,/ 求字符串的长度 int strlen(char d ) int i =0; while (di != 0) i+; return i; ,C+标准串运算的实现,/寻找字符 char
9、 * strchr(char *d , char ch) / 按照数组指针d依次寻找字符ch，如果找到ch，则将指针位置返回， / 如果没有找到ch，则为0值 i = 0; / 循环跳过那些不是ch的字符 while (di != 0 ,C+标准串运算的实现,/ 反向寻找字符 char * strrchr(char *d , char ch) / 按照数组指针d，从其尾部反着寻找字符ch，如果找到，则将指针位置返回， / 如果没有找到，则为0值。 i = 0; while (di != 0 ) / 找串尾 i+; / 循环跳过那些不是ch的字符 while (d-i != 0 ,C+标准str
10、ing,e.g, 字符串s ：,寻找字符o，strchr(s,o)结果返回4；,反方向寻找r， strrchr(s,o)结果返回7,String串运算的实现,/ 创建算子(constructor) String:String(char *s) / 先要确定新创字符串实际需要的存储空间，s的类型为(char *)， / 作为新创字符串的初值。确定s的长度，用标准字符串函数 /strlen(s)计算长度 size = strlen(s) ; / 然后，在动态存储区域开辟一块空间，用于存储初值s，把结束 / 字符也包括进来 str new char size1; / 开辟空间不成功时，运行异常，退出
11、 assert(str != 0); / 用标准字符串函数strcpy，将s完全复制到指针str所指的存储空间 strcpy(str, s); ,String串的创建运算,String s1 = Hello ;,String串运算的实现,/ 析构函数 String:String() / 必须释放动态存储空间 delete str; ,String串运算的实现,/ 赋值算子 String String:operator= (String ,String的赋值运算,String s2 = Hello world; 并通过赋值语句：s1 = s2;,String串运算的实现,/ 抽取子串函数 Str
12、ing String:Substr(int index , int count ) / 取出一个子串返回，自下标index开始，长度为count int i; / 本串自下标index开始向右数直到串尾，长度为left int left = size index ; String temp; char *p, *q; / 若下标index值太大，超过本串实际串长，则返回空串 if (index = size) return temp; / 若count超过自index以右的实际子串长度，则把count变小 if (count left ) count = left; / 释放原来的存储空间 d
13、elete temp.str;,String串运算的实现,/ 若开辟动态存储空间失败，则退出 temp.str = new char count+1; assert(temp.str != 0)； / p的内容是一个指针，指向目前暂无内容的字符数组的首字符处 p = temp.str; / q的内容是一个指针，指向本实例串的str数组的下标index字符 q = ,String抽取子串,s2 = s1.Substr(6, 5) ;,字符串模式匹配,模式匹配(pattern matching) 一个目标对象T（字符串） 一个模式（pattern）P（字符串） 在目标T中寻找一个给定的模式P的过程
14、 应用 文本编辑时的特定词、句的查找 DNA信息的提取 确认是否具有某种结构 ,模式匹配目标,在大文本（诸如，句子、段落，或书本）中定位（查找）特定的模式 对于大多数的算法而言，匹配的主要考虑在于其速度和效率 有相当数目的算法用于解决模式匹配问题，将介绍朴素(Brute Force)、 Knuth-Morris-Pratt (KMP) 算法,字符串模式匹配,精确匹配（Exact String Matching）：一种结果或成或败的匹配，即，若在目标T中至少一处存在模式P，则称为匹配成功，否则即使目标与模式只有一个字符不同也不能称为匹配成功，亦即匹配失败 单选的，”Set” ； 多选的，模式”
15、S?t” 正则表达式表示的模式 近似匹配（Approximate String Matching）： 如果模式P与目标T（或其子串）存在某种程度的相似，则认为匹配成功。 常用的衡量字符串相似度的方法是根据一个串转换成另一个串所需的基本操作数目来确定。基本操作由字符串的插入、删除和替换三种操作来组成,字符串模式匹配,模式单选精确匹配 用给定的模式P，在目标字符串T中搜索与模式P全同的一个子串，并求出T中第一个和P全同匹配的子串（简称为“配串”），返回其首字符位置 T T0 T1 TiTi+1 Ti+2 Ti+m-2 Ti+m-1 Tn-1 P p0 p1 p2 pm -2 pm-1 为使模式 P
16、 与目标 T 匹配，必须满足 p0 p1 p2 pm-1 = Ti Ti+1 Ti+2 Ti+m-1,单模式匹配算法,朴素模式匹配（穷举法）,设T= T0T1, T2, ,Tn，P = p1, p2, , pm j为指向T中字符的下标指针，i为指向P中字符的下标指针 匹配成功 (p1 = Tj , p2 = Tj+1 , , pm = Tj+m-1 ) 即，substr(T, j, m) 匹配失败 (pi Tj) 时， 将P右移再行比较 尝试所有的可能情况,朴素模式匹配：示例,把模式与目标逐一进行比较（首位置开始），直到碰到不匹配的字符为止（模式右移一位再次开始匹配） 算法可在第一个匹配或是目标的结束处停止,朴素匹配算法,#include “String
