北京大学：《数据结构与算法》课程教学资源（实验班讲义）第三章 字符串

主要内容 数据结构与算法 第三章字符串 31字符串抽象数据类型 32字符串的存储结构和类定义 张铭 33字符串运算的算法实现 http:/db.pku.edu.cn/mzhang/ds/ 北京大学信息科学与技术学院 34字符串的模式匹配 数据结构与算法教学小组 ⊙版权所有,转數或翻印必究 next 31字符串抽象数据类型 311基本概念 311基本概念 字符串,由0个或多个字符的顺 312 String抽象数据类型 序排列所组成的复合数据结构, 简称“串” m串的长度:一个字符串所包含的 字符个数。 空串:长度为零的串,它不包含 任何字符内容。 北京歌魏孔节了有,印究 大恤盒 张帖写 权质有,即鱼究 31.11字符串常数和变量 3112字符 字符串常数 字符(char):组成字符串的基 例如:" 本单位 ■字符串变量 在C和C++中 ■单字节(8bits) 采用AScI码对128个符号(字符 集 charset)进行编码 真大学健张帖写c所有,即必究 北太拳息单张帖权所者,即亮

1 数据结构与算法 第三章 字符串 张铭 http://db.pku.edu.cn/mzhang/DS/ 北京大学信息科学与技术学院 “数据结构与算法”教学小组 ©版权所有，转载或翻印必究 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 2 back next 主要内容 „ 3.1 字符串抽象数据类型 „ 3.2 字符串的存储结构和类定义 „ 3.3 字符串运算的算法实现 „ 3.4 字符串的模式匹配 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 3 back next 3.1字符串抽象数据类型 „ 3.1.1 基本概念 „ 3.1.2 String抽象数据类型 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 4 back next 3.1.1 基本概念 „ 字符串，由0个或多个字符的顺 序排列所组成的复合数据结构， 简称“串”。 „ 串的长度：一个字符串所包含的 字符个数。 „ 空串：长度为零的串，它不包含 任何字符内容。 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 5 back next 3.1.1.1字符串常数和变量 „ 字符串常数 „ 例如： "\n" „ 字符串变量 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 6 back next 3.1.1.2 字符 „ 字符(char) ：组成字符串的基 本单位 。 „ 在C和C＋＋中 „ 单字节（8 bits） „ 采用ASCII码对128个符号（字符 集charset）进行编码

4314c+标准tng1314c+标准ng续 标准字符串:将C++的 1.串长函数 < string. h>函数库作为字符串 int strlen(char *s)i 数据类型的方案。 char *strcpy(char *s1, char*s2); 例如: char s[M] ■3.串拼接 ■串的结束标记:"Y0 char *strcat(char *s1, char *s2); "\o是AsCI码中8位BTT全0码, 4.串比较 又称为NULL符 int strcmp(char *s1, char *s2); next 北京大单啦检写解有,究 3114C++标准 string(续) 312 String抽象数据类型 5.输入和输出函数 字符串类( class String) ■6.定位函数 ■不采用 char s[M]的形式 char strchr(char *s, char c); 而采用一种动态变长的存储结 ■7.右定位函数 构 char *strrchr(char *s, char c); 北京歌魏孔节了有,印究 张所有,赖 ass String /它的存储结构和实现方法使用了C++标准st 为了区别,类 String所派生创建的实例对象 char.tr://私有的指针变量,用于指向存储向量atr[aixe+1] 在程序首,要# include< string.h)和 includ /本串的当前实际长度 ∥/及# nclude< stdlib.b>,以及# include String(hr咖="):/创建一个空的字符 ∥创建新字符串,并将标准字符率s持贝为初位 /1.字符串的数据表示 String0∥销數本串,从计算机存储空间删去本串 /字符串S通常用顺序存放,用数组S[]存储,元素的类型为char ∥下面是函数的定文,包捐赋值函数=拼换函数十和比较函敷〈等 /字符串为变长,使用变量size记录串的当前长度 String operators( char = s);/属值操作标准率持贝到本串 String operator=( String 5);/值操作,率复制到本率 ∥2.使用变量访问字符串 );/∥拼接函量十,本率拼接标准率 /字符串变量能参与运算,例如S1+S2表示两个字符串首尾拼接在一起 String operator+( String s);∥拼接函录十,本率拼按串 7/用数组strD存储字符串,在内部可以用str[访问串的第i个字符, end String operator+ ring s)1 友函教作为拼接函数+其返回值是一个实例串,等于标准串t拼接串 ∥/3.字符串类的运算集:请参看下面的成员函数 2

2 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 7 back next 3.1.1.4 C++标准string „ 标准字符串：将C++的 <string.h>函数库作为字符串 数据类型的方案。 „ 例如：char S[M]; „ 串的结束标记：'\0' „ '\0'是ASCII码中8位BIT全0码， 又称为NULL符。 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 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); 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 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); 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 10 back next 3.1.2 String抽象数据类型 „ 字符串类（class String）： „ 不采用char S[M]的形式 „ 而采用一种动态变长的存储结 构。 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 11 back next 3.1.2 String抽象数据类型(续) class String //字符串 类 //它的存储结构和实现方法使用了C++标准string(简称标准串), //为了区别,类String所派生创建的实例对象,简称‘本串’,或‘实例串’ //在程序首,要#include <string.h>和#include <iostream.h>及 // 及 #include <stdlib.h>，以及#include <assert.h> { //1.字符串的数据表示： //字符串 S 通常用顺序存放，用数组S[]存储，元素的类型为char //字符串为变长，使用变量size记录串的当前长度 // 2.使用变量访问字符串： //字符串变量能参与运算,例如S1 + S2表示两个字符串首尾拼接在一起 //用数组str[]存储字符串，在内部可以用str[i]访问串的第i个字符, // 3.字符串类的运算集：请参看下面的成员函数 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 12 back next private: char *str; //私有的指针变量，用于指向存储向量str[size+1] int size； //本串的当前实际长度 public: String(char *s = ''); //创建一个空的字符串 String(char *s); // 创建新字符串，并将标准字符串s拷贝为初值 ~String() // 销毁本串，从计算机存储空间删去本串 //下面是函数的定义，包括赋值函数 ＝ 拼接函数 ＋ 和比较函数 < 等 String& operator= (char *s）；//赋值操作=，标准串s拷贝到本串 String& operator= (String& s）;//赋值操作=，串s复制到本串 String operator＋ (char *s）;//拼接函数＋，本串拼接标准串s String operator＋ (String& s）；//拼接函数＋，本串拼接串s friend String operator+ (char *s1, String& s）； //友函数作为拼接函数+ 其返回值是一个实例串,等于标准串str拼接串s

int operator<(char*s);//比较大小,本串小于标准串s则返回非0 3.1.23赋值操作符、拼接操 Int operator<( String s)://比较大小,本串小于串 friend int operator<(char*sl, String s);∥友函数用于比较 作符和比较操作符 /输入输出'函数》》和<<以及读子串等,例如友函数 friend istream operator>>(istream istr, String s) 赋值操作符= riend Ostream& operator<< (ostereamk istr, String s) ·子串函数'ε插入子串、寻找子串、提取子串、删除子串等,例如 ■拼接操作符+ String Substr( int index, int count);//它们的功能参见下文 //串与字符'函数:按字符定位等 比较操作符<<=> int Find( char c, Int start)://在本串中寻找字符c,从下标 start开始找, ∥/寻找到c后,返回字符c在本串的下标位置 ==和== //其他函数:求串长、判空串、清 nt IsEmpty o;//判本串为空串 void clear0:/清本串为空串 北京大单啦检写@有,翰 31.24输入输出操作符 3125处理子串( Substring) <和>> 的函数 ■输入操作符>> ■简称“子串函数” 输出操作符<< 提取子串 插入子串 ■寻找子串 删除子串 nexy 大带_息 张写 积新有,神 张所有,赖 32字符串的存储结构圈 31.26字符串中的字符 和类定义 ■重载下标操作符[] ■321字符串的顺序存储 char& operator[](int n); ■322字符串类 class string的 ■按字符定位下标 存储结构 int Find(char c, int start; ■反向寻找,定位尾部出现的字符 int Find Last(char c; 北底大 张储帖写 真大带健意张写c所有,邮必究

3 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 13 back next //‘关系’函数，用于比较相等、大、小，例如 int operator< (char *s）;//比较大小,本串小于标准串s则返回非0 int operator< (String& s）;//比较大小，本串小于串s则返回非0 friend int operator< (char *s1, String& s）； //友函数用于比较, // ,标准串s1小于串s,则返回非0 //‘输入输出’函数 >>和<< 以及 读子串等，例如友函数 friend istream& operator>> (isteream& istr,String& s）； friend ostream& operator<< (osteream& istr,String& s）； // ‘子串函数’：插入子串、寻找子串、提取子串、删除子串等，例如 String Substr(int index，int count）; //它们的功能参见下文 //‘串与字符’函数：按字符定位等，例如 int Find(char c,int start);//在本串中寻找字符c,从下标start开始找, // 寻找到c后,返回字符c在本串的下标位置 //其他函数：求串长、判空串、清为空串、 int strlen(); //返回本串的当前串长 int IsEmpty(); //判本串为空串? void clear(); //清本串为空串 }; 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 14 back next 3.1.2.3 赋值操作符、拼接操 作符和比较操作符 „ 赋值操作符 ＝ „ 拼接操作符＋ „ 比较操作符 < <= > >= != 和 == 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 15 back next 3.1.2.4 输入输出操作符 << 和 >> „ 输入操作符>> „ 输出操作符<< 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 16 back next 3.1.2.5 处理子串(Substring) 的函数 „ 简称“子串函数” „ 提取子串 „ 插入子串 „ 寻找子串 „ 删除子串 „ … 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 17 back next 3.1.2.6 字符串中的字符 „ 重载下标操作符[] char& operator[] (int n); „ 按字符定位下标 int Find(char c,int start); „ 反向寻找，定位尾部出现的字符 int FindLast(char c); 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 18 back next 3.2 字符串的存储结构 和类定义 „ 3.2.1字符串的顺序存储 „ 3.2.2字符串类class String的 存储结构

322字符串类 class string 321字符串的顺序存储 的存储结构(续) 用S[]作为记录串长的存储单元 微vc++的 CString类介绍 缺点:串的最大长度不能超过256 管理,串的最大长度不超过2GB ■另辟一个存储的地方存储串的长度 缺点:串的最大长度静态给定 使用特点: 变量申明 用一个特殊的末尾标记0 例如:C++语言的stri ring city=" Philadelphia";//串常敷作为初值 clude <string. h>) 2="hi there" 变量比较i(s1==s2) 方法调用 s1. MakeUpper(; 大卿血端张_·权,成 3字符串运算的算法实现 ■1.串长函数 int strcmp_1(char *d, char *s)t int strlen(char *s) for(int i=O; d[i]==s[i];++i)t ■2.串复制 f(d[i]==o&&s[i]==Y0) char *strcpy (char *s1, char*s2) return0;//两个字符串相等 3.串拼接 char *strcat(char *s1, char *s2) //不等比较第一个不同的字符 4.串比较 return(d[i-s[iD/abs(d[il-s[i]) nt strcmp(char *s1, char *s2); 大带_息 张写 积新有,神 张所有,赖 3.3字符串运算的算法实现 34字符串的模式匹配 ■331C++标准串运算的实现 ■模式匹配( pattern matching) ■332 String串运算的实现 个目标对象S(字符串) 一个模板( pattern)P(字符 任务:求出s中第一个与P全同 匹配的子串(简称为“配串”) 返回其首字符位置 北底大 张储帖写 真大带健意张写c所有,邮必究 e

4 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 19 back next 3.2.1字符串的顺序存储 „ 用S[0]作为记录串长的存储单元 „ 缺点：串的最大长度不能超过256 „ 另辟一个存储的地方存储串的长度 „ 缺点：串的最大长度静态给定 „ 用一个特殊的末尾标记'\0' „ 例如：C++语言的string函数库（＃ include <string.h>）采用这一存储 结构 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 20 back next 3.2.2 字符串类class String 的存储结构(续) „ 微软VC＋＋的CString类介绍 „ 自动的动态存储管理，串的最大长度不超过2GB „ 容器型 „ 不必使用new和delete „ 使用特点： „ 变量申明 „ CString s6( 'x', 6 ); // s6 = "xxxxxx" „ CString city = "Philadelphia"; // 串常数作为初值 „ 赋值语句 „ s1 = s2 = "hi there"; „ 变量比较 if( s1 == s2 ) „ 方法调用 s1.MakeUpper(); „ 内部字符比较 if( s2[0] == 'h' ) 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 21 back next 3.3 字符串运算的算法实现 „ 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); 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 22 back next int strcmp_1(char *d, char *s) { for (int i=0;d[i]==s[i];++i ) { if(d[i]=='\0' && s[i]=='\0') return 0;//两个字符串相等 } //不等,比较第一个不同的字符 return (d[i]-s[i])/abs(d[i]-s[i]); } 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 23 back next 3.3 字符串运算的算法实现 „ 3.3.1 C++标准串运算的实现 „ 3.3.2 String串运算的实现 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 24 back next 3.4 字符串的模式匹配 „ 模式匹配(pattern matching) „ 一个目标对象S（字符串） „ 一个模板（pattern）P（字符 串） „ 任务：求出S中第一个与P全同 匹配的子串（简称为“配串”）， 返回其首字符位置

34字符串的模式匹配 S551…s52…,sm25m1…Sn1 341朴素模式匹配 PPP…Pm-2Pm1 34.2字符串的特征向量N ■343KMP模式匹配算法 为使模式P与目标S匹配,必须满足 几nP… next 大卿血端张_·权,成 北京大单啦检写@有,赖职 朴素模式匹配 朴素模式匹配代码(简洁) b ababb int Find Pat_2(String S, String P, int startindex)t /g为S的游标,用模板P和S第g位置子串比较 /若失败则继续循环 翼 bb a bb for (int g= startindex; g<= Sstrlen(-Pstrlen O; or(int j=o;((<Pstrlen()&&(S[g+j]==PD) if G== P strlen) return g: return(-1);∥/for结東,或 startindex值过大则匹配失败 b I 大带_息 张写 张所有,赖 MMP算法思想 朴素模式匹配算法代价 5155+15+2 例如, aaaaaaaaaab n1…p2 ■目标S的长度为n,模板P长度为m,m≤n 则有ss152…5=阳P…P(1) 在類藝雞(每m不成功,则 朴素下一越 阳n…P21 如果%1…P2≠几1P2…1 时阁,相潭要知:个字符比校 则立刻可以断定 Po pi 整个算法的最坏时间开销估计为o(m·n) 朴素匹配的)下一趙一定不匹配,可以跳过去 Po p1 p2 next 北底大 张储帖写 真大带健意张写c所有,邮必究 5

5 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 25 back next S s0 s1 … si si+1 si+2 … si+m-2 si+m-1 … sn-1 ‖‖ ‖ ‖ ‖ P p0 p1 p2 … pm -2 pm-1 为使模式 P 与目标 S 匹配，必须满足 p0 p1 p2 …pm-1 = si si+1 si+2 … si+m-1 si si+1 si+2 … si+m-2 si+m-1 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 26 back next 3.4 字符串的模式匹配 „ 3.4.1 朴素模式匹配 „ 3.4.2 字符串的特征向量N „ 3.4.3 KMP模式匹配算法 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 27 back next 朴素模式匹配 S= P= a b a b a b a b a b a b b a b a b a b b a b a b a b b a b a b a b b Xa b a b a b b X X X a b a b a b bX Xa b a b a b b a b a b a b b 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 28 back next 朴素模式匹配代码（简洁） int FindPat_2(String S, String P, int startindex) { //g为S的游标，用模板P和S第g位置子串比较， //若失败则继续循环 for (int g= startindex; g <= S.strlen() - P.strlen(); g++) { for (int j=0; ((j<P.strlen()) && (S[g+j]==P[j])) ; j++) ; if (j == P.strlen()) return g; } return(-1); // for结束，或startindex值过大,则匹配失败 } 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 29 back next 朴素模式匹配算法代价 例如，aaaaaaaaaab aaaaaab „ 目标S的长度为n，模板P长度为m， m≤n „ 在最坏的情况下，每一次循环都不成功，则 一共要进行比较（n-m+1）次 „ 每一次“相同匹配”需要P和S逐个字符比较 的时间，最坏情况下，共m次 „ 整个算法的最坏时间开销估计为O(m • n) 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 30 back next KMP算法思想 S s0 s1 … si-j-1 si-j si-j+1 si-j+2 … si-2 si-1 si … sn-1 ‖ ‖ ‖ ‖‖ P p0 p1 p2 … pj-2 pj -1 pj 则有 si-j si-j+1 si-j+2 … si-1 = p0 p1 p2 …pj-1 (1) p0 p1 p2 … pj-2 pj -1 如果 p0 p1 …pj-2 ≠ p1 p2 …pj-1 (2) 则立刻可以断定 p0 p1 …pj-2 ≠ si-j+1 si-j+2 … si-1 (朴素匹配的)下一趟一定不匹配，可以跳过去 p0 p1 p2 … pj-2 pj -1 朴素下一趟 × si pj