数据结构之字符串

1、字符串2/45主要内容 字符串抽象数据类型字符串抽象数据类型 字符串的存储结构和类定义字符串的存储结构和类定义 字符串运算的算法实现字符串运算的算法实现 字符串的模式匹配主要掌握字符串的模式匹配主要掌握3.4.1字符串3/45字符串抽象数据类型 基本概念基本概念 字符串抽象数据类型字符串抽象数据类型 String抽象数据类型抽象数据类型字符串4/45重要性 串（字符串），是计算机非数值处理的主要对象之一。串（字符串），是计算机非数值处理的主要对象之一。如，在汇编和编译程序中，源程序和目标程序都是串；如，在汇编和编译程序中，源程序和目标程序都是串；如，在事务处理程序中，顾客的姓名和地址，以及货物

2、的名如，在事务处理程序中，顾客的姓名和地址，以及货物的名称、产地和规格等，通常也都作为串处理。称、产地和规格等，通常也都作为串处理。 由于我们现今使用的计算机的硬件结构主要是面向数由于我们现今使用的计算机的硬件结构主要是面向数值计算的需要，基本上没有提供对串进行操作的指令，值计算的需要，基本上没有提供对串进行操作的指令，因此需要用软件来实现串数据类型。因此需要用软件来实现串数据类型。字符串5/45基本概念 字符串字符串，由，由0个或多个字符的顺序排列所组个或多个字符的顺序排列所组成的复合数据结构，简称成的复合数据结构，简称“串串”。 串的串的长度长度：一个字符串所包含的字符个数。：一个字符串所

3、包含的字符个数。 空串空串：长度为零的串，它不包含任何字符内容。：长度为零的串，它不包含任何字符内容。 字符字符(char) ：组成字符串的基本单位：组成字符串的基本单位 。字符串6/45串中任意个连续的字符组成的子序列称为该串的串中任意个连续的字符组成的子序列称为该串的子串子串。包含子串的串相应的称为包含子串的串相应的称为主串主串。例，串例，串 eij 是串是串 beijing 的子串，的子串， beijing 称为主称为主串。串。字符在序列中的序号称为该字符在串中的字符在序列中的序号称为该字符在串中的位置位置。子串在主串中的位置子串在主串中的位置定义为子串的第一个字符在主串定义为子串的第一

4、个字符在主串中的位置。中的位置。例，字符例，字符 n 在串在串 beijing 中的位置为中的位置为 6 。例，子串例，子串 eij 在串在串 beijing 中的位置为中的位置为 。2字符串7/45 串由零个或多个字符组成的有限序列。记作 S=a1a2an 串名：S； 串值：用双引号括起来的字符序列。长度：串中字符的数目。空串：含零个字符的串，表示。空格串：由一个或多个空格组成的串。子串：串中任意个连续的字符组成的子序列。字符在串的位置：字符在序列中的序号。子串在串的位置：子串的第一个字符在串中的位置。相等：当且仅当两个串的值相等。串值必须用一对串值必须用一对双引号括起来双引号括起来空串与空

5、格空串与空格串的区别？串的区别？字符串8/45两个串两个串相等相等，当且仅当这两个串的，当且仅当这两个串的值相等值相等。例，串例，串 bei jing 与串与串 beijing 不相等不相等 。串值必须用一对双引号括起来，但双引号本身不属串值必须用一对双引号括起来，但双引号本身不属于串，只起界定作用。于串，只起界定作用。由由一个一个或或多个多个空格组成的串称为空格组成的串称为空格串空格串。 字符串9/45串与线性表区别串与线性表区别 串的数据对象约束为串的数据对象约束为字符集字符集。 串的串的基本操作基本操作与线性表有很大差别与线性表有很大差别 线性表的基本操作中，大多以线性表的基本操作中，大

6、多以“单个元素单个元素”作为作为操作对象，如查找某个元素、在某个位置上插入操作对象，如查找某个元素、在某个位置上插入一个元素和删除一个元素。一个元素和删除一个元素。 串的基本操作中，通常以串的基本操作中，通常以“串的整体串的整体”作为操作作为操作对象。如在串中查找某个子串、在串的某个位置对象。如在串中查找某个子串、在串的某个位置上插入一个子串以及删除一个子串。上插入一个子串以及删除一个子串。字符串10/45例子a=BEIa=BEIb=JINGb=JINGc=BEIJINGc=BEIJINGd=BEI JINGd=BEI JING长度长度分别为分别为3 3、4 4、7 7、8 8；a a和和b

7、b都是都是c c和和d d的子串；的子串；a a在在c c和和d d中的位置中的位置都是都是1 1；b b在在c c和和d d中的位置中的位置是是4 4和和5 5； a a、b b、c c、d d彼此不相等。彼此不相等。字符串11/45String抽象数据类型 字符串类（字符串类（class String）：）： 不采用不采用char SM的形式的形式 而采用一种动态变长的存储结构。而采用一种动态变长的存储结构。字符串12/45ClearString( &S )结果结果: 将将 S 清为空串。清为空串。条件条件: 串串 S 已存在已存在。数据对象数据对象: D = ai | ai Charac

8、terSet，i = 1 1, 2, , n 数据关系数据关系: R1 1 = 基本操作基本操作: ADT String ADT StringDestroyString( &S )结果结果: 销毁串销毁串 S。条件条件: 串串 S 已存在已存在。StrAssign( &T ，chars )结果结果: 生成一个其值等于生成一个其值等于 chars 的串的串 T。条件条件: chars 是字符串常量。是字符串常量。字符串13/45StrEmpty ( S )StrCopy ( &T ，S )StrCompare ( S ，T )StrLength ( S )Concat ( &T，S1，S2 )S

9、ubString ( &Sub，S，pos，len )Index ( S，T )StrInsert ( &S，pos，T )StrDelete( &S，pos，len )String串的常用操作（一）字符串14/45String串的常用操作（二）串的常用操作（二） 赋值算子赋值算子 拼接算子拼接算子 比较算子比较算子 = != = != 和和 = 重载下标算子重载下标算子 char& operator (int char& operator (int n); n); 按字符定位下标按字符定位下标 int Find(char c,intint Find(char c,int start); st

10、art); 反向寻找，定位尾部出现的字符反向寻找，定位尾部出现的字符 int FindLast(charint FindLast(char c); c);字符串15/45串的表示和实现 定长顺序存储表示用一组地址连续的存储单元存储串值的字符序列，属静态存储方式。 堆分配存储表示用一组地址连续的存储单元存储串值的字符序列,但存储空间是在程序执行过程中动态分配而得。 串的块链存储表示链式方式存储首先强调：串与线性表的运算有所不同，是以首先强调：串与线性表的运算有所不同，是以“串的整体串的整体”作为操作对象，例如查找某子串，在主串某位置上插入一个作为操作对象，例如查找某子串，在主串某位置上插入一个子

11、串等。子串等。串有三种机内表示方法：串有三种机内表示方法：顺序顺序存储存储链式链式存储存储字符串16/45字符串的存储结构和类定义 字符串的顺序存储字符串的顺序存储 用一个特殊的末尾标记用一个特殊的末尾标记0。 字符串类字符串类class String的存储结构的存储结构 例如抽取子串函数：例如抽取子串函数： String s1 = value-; s2 = s1.Substr(2,3); 上述语句涉及的存储形式如下页所示。上述语句涉及的存储形式如下页所示。字符串17/45字符串类class String的存储结构字符串18/45 系统系统开辟一个串值存储空间开辟一个串值存储空间（串值可利用空

12、间）（串值可利用空间） ，同时建立一个符号表；同时建立一个符号表； 建立一个新串时，在可利用空间分配，并在符号建立一个新串时，在可利用空间分配，并在符号表中记录下串变量名、串值在可利用空间的位置、表中记录下串变量名、串值在可利用空间的位置、串长度等信息。串长度等信息。堆分配存储表示堆分配存储表示长度位置串名符号表串值存储空间字符串19/4531a长度位置串名符号表IEB串值存储空间字符串20/4544b31a长度位置串名符号表GNIJIEB串值存储空间字符串21/4588c44b31a长度位置串名符号表IAHGNAHSGNIJIEB串值存储空间字符串22/45616d88c44b31a长度位置

13、串名符号表NIBRAHIAHGNAHSGNIJIEB串值存储空间字符串23/45 用链表方式存储串值，每个结点大小相同。 结点分为两个域data域next域串的块链存储表示串的块链存储表示结点大小为结点大小为1 1的链表的链表ABCDEFhead结点大小为结点大小为4 4的链表的链表headDCBA#FE# #占满占满存储密度存储密度= =串值所占的存储位串值所占的存储位/ /实际分配的存储位。实际分配的存储位。字符串24/45讨论：讨论：法法1 1存储密度为存储密度为 ；法；法2 2存储密度为存储密度为 ；显然，若数据元素很多，用法显然，若数据元素很多，用法2 2存储更优存储更优称为称为块链

14、结构块链结构链式存储特点链式存储特点 ：用链表存储串值，易插入和删除。用链表存储串值，易插入和删除。法法1 1：链表结点的数据分量长度取链表结点的数据分量长度取法法2 2：链表结点（数据域）大小取链表结点（数据域）大小取n n( (例如例如n=4)n=4)1/21/29 9/15=3/5/15=3/5 A B C I NULLheadheadA B C D E F G H I # # # NULL字符串25/45#define CHUNKSIZE 80 /每块大小，可由用户定义每块大小，可由用户定义typedef struct Chunk /首先定义结点类型首先定义结点类型 char ch C

15、HUNKSIZE ; /每个结点中的数据域每个结点中的数据域 struct Chunk * next ; /每个结点中的指针域每个结点中的指针域Chunk; typedef struct /其次定义用链式存储的串类型其次定义用链式存储的串类型 Chunk *head; /头指针头指针 Chunk *tail; /尾指针尾指针 int curLen; /结点个数结点个数 Lstring; /串类型只用一次，前面可以不加串类型只用一次，前面可以不加LstringLstring块链类型的定义字符串26/45字符串的模式匹配 在串T中查找是否有与串P相等的子串，则称串T为目标(Target)，把P称为

16、模式(Pattern)。 称查找模式在目标中的匹配位置的运算为模式匹配(Pattern matching)。字符串27/45模式匹配算法 简单模式匹配算法简单模式匹配算法 BF算法算法 （又称古典的、经典的、朴素的、穷举的）（又称古典的、经典的、朴素的、穷举的） 带回溯，速度慢带回溯，速度慢 KMP(Knuth-Morris-Pratt)算法算法 避免回溯，匹配速度快避免回溯，匹配速度快 T=“longlonglongago”； P=“longlongago”；字符串28/45简单匹配算法思想 算法设计思想：算法设计思想： 将主串将主串S的第的第pos个字符和模式个字符和模式T的第的第1个字符

17、个字符比较，比较， 若相等，继续逐个比较后续字符；若相等，继续逐个比较后续字符； 若不等，从主串若不等，从主串S的下一字符（的下一字符（pos+1）起，重新与）起，重新与T第一个字符比较。第一个字符比较。 直到主串直到主串S的一个连续子串字符序列与模式的一个连续子串字符序列与模式T相相等。返回值为等。返回值为S中与中与T匹配的子序列第一个字符匹配的子序列第一个字符的序号，即匹配成功。的序号，即匹配成功。 否则，匹配失败，返回值否则，匹配失败，返回值 0 .字符串29/45简单模式匹配算法过程lo n glo n glo nt0t1t2t3t4t5t6t7t8t9t10g a gt11t12t1

18、3o 0t14t15lo n glo n gp0p1p2p3p4p5p6p7a g o 0p8p9p10p11jijijijijijijijijijijijijijijijijijijijijijiji第一趟比较：第一趟比较：第二趟比较：第二趟比较：第三趟比较：第三趟比较：第四趟比较：第四趟比较：第五趟比较：第五趟比较：ji字符串30/45简单匹配算法代码int Find(char* target, char* pat) int i=0,j=0;int lengthP =strlen(pat), lengthT =strlen(target);while(i=lengthT-lengthP)

19、j=0;while(targeti=patj&jlengthP) i+;j+ if(j=lengthP) return i-j; /串pat扫描完，匹配成功 else i=i-j+1;/不匹配，做下一趟比较 return 1; 字符串31/45简单模式匹配算法分析 设目标T的长度为n,模式P 的长度为m,在最坏情况下，比较次数： 在多数情况下，m远小于n, 因此算法的最坏的时间复杂性为O(n*m)。 复杂度高，效率低31(n-m+1)*m字符串32/45改进的算法 KMP算法算法 不做课程要求不做课程要求 注重思想注重思想字符串33/45 T t0 ts ts+1 ts+2 ts+3 ts+j

20、-k-1 ts+j-k.ts+j-1 ts+j P p0 p1 p2 p3 pj-k-1 pj-k . pj-1 pj p0 . . pj-2 pj-1 p0 . pj-3 pj-2 p0 . . pj-4 pj-3 . p0 pk pk+1 p0 pk-1 pk 不需要回溯目标指针，模式右滑不需要回溯目标指针，模式右滑j-kj-k位，位， 下一趟比较从下一趟比较从p pk k 与与t ts+js+j开始开始 字符串34/45KMP算法 思想：当在某个位置匹配不成功的时候可以根据之前的匹配结果从模式字符串的另一个位置开始,而不必从头开始匹配字符串. K值如何确定？ T t0 ts ts+1 t

21、s+2 ts+3 ts+j-k-1 ts+j-k.ts+j-1 ts+j P p0 p1 p2 p3 pj-k-1 pj-k . pj-1 pj p0 pk-1 pk 字符串35/45 前缀子串：模式串前缀子串：模式串P开头的任意开头的任意k个字个字符符, p0, p1 ,pk-1 。 j位置的左子串：在位置的左子串：在P第第j位置的左边，位置的左边，取出取出k个字符，即个字符，即pj-k+1,pj。 第第j位的最长前缀串：与位的最长前缀串：与j位置左子串位置左子串相等的最长前缀子串。相等的最长前缀子串。c oc o colap0p1p2p3p4p5p6p7字符串36/45模式串的特征数和特征

22、向量 第第j位的最长前缀串的长度位的最长前缀串的长度k k就是模就是模式串式串P P在位置在位置j j上的上的特征数nj 特征数组成的向量称为该模式串的特征数组成的向量称为该模式串的特征向量。 其意义在于：其意义在于：表示一旦匹配过程中表示一旦匹配过程中p pj j与与t ti i比较不等，比较不等，可用可用p p中以中以n j-1n j-1为下标的字符与为下标的字符与t ti i进行进行比较。比较。字符串37/45MAX k, 0 k = j 且且 P0 Pk-1 = Pj-k+1 Pj-1 Pj 0 其它情况其它情况 nj = 特征数定义001234 0 c 1 o 2 c 3 o 4 c

23、 5 o j P P nj 6 l0 7 a0 字符串38/45 a a b a a b a a b c a c a a b c a a a b c a c a a b a a b a a b c a c a a b c b a a b c a c a c a b a a b a b c a c a a b c a b a a b a c a c a b a a b a b c a c a a b c (a b) a b c a c iiiiijjjjj字符串39/45ico c oco c olat0t1t2t3t4t5t6t7t8t9t10c oc o colap0p1p2p3p4p5p6

24、p7ico c oco c olac oc o colap0p1p2p3p4p5p6p7c oc o colap0p1p2p3p4p5p6p7ico c oco c ola 目标指针加目标指针加1 模式指针=n6-1第一趟：第一趟：第二趟：第二趟：第三趟：第三趟：字符串40/45 KMP匹配算法的时间复杂度匹配算法的时间复杂度O(m+n)。计算特征数的时间复杂度为计算特征数的时间复杂度为O(m) 40字符串41/45基础知识题：思考基础知识题：思考简述空串和空格串(或称空格符串)的区别。 设s = I AM A STUDENT, t = GOOD, q = WORKER。求：StrLength(s)StrLength(t) SubString(s,8,7) SubString(t,2,1)Index(s,A) Index(s,t),Replace(s, STUDENT,q