5字符串06064.ppt

《5字符串06064.ppt》由会员分享，可在线阅读，更多相关《5字符串06064.ppt（45页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、数据结构与算法数据结构与算法For For 软件学院软件学院0808级本科生级本科生 2009-20102009-2010秋秋3 3 字符串字符串主要内容字符串抽象数据类型字符串抽象数据类型字符串的存储结构和类定义字符串的存储结构和类定义字符串运算的算法实现字符串运算的算法实现字符串的模式匹配主要掌握字符串的模式匹配主要掌握3.4.12字符串字符串抽象数据类型 基本概念基本概念字符串抽象数据类型字符串抽象数据类型String抽象数据类型抽象数据类型3字符串重要性串（字符串），是计算机非数值处理的主要对象之一。串（字符串），是计算机非数值处理的主要对象之一。如，在汇编和编译程序中，源程序和目标程

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

3、数据结构，简称“串串”。串的串的长度长度：一个字符串所包含的字符个数。：一个字符串所包含的字符个数。空串空串：长度为零的串，它不包含任何字符内容。：长度为零的串，它不包含任何字符内容。字符字符(char)：组成字符串的基本单位：组成字符串的基本单位。5字符串串中任意个连续的字符组成的子序列称为该串的串中任意个连续的字符组成的子序列称为该串的子串子串。包含子串的串相应的称为包含子串的串相应的称为主串主串。例，串例，串 eij 是串是串 beijing 的子串，的子串，beijing 称为称为主串。主串。字符在序列中的序号称为该字符在串中的字符在序列中的序号称为该字符在串中的位置位置。子串在主串中

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

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

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

7、8 8；a a和和b 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彼此不相等。彼此不相等。10字符串String抽象数据类型字符串类（字符串类（class String）：）：不采用不采用char SM的形式的形式而采用一种动态变长的存储结构。而采用一种动态变长的存储结构。11字符串ClearString(&S)结果结果:将将 S 清为空串。清为空串。条件条件:串串 S 已存在已存在。数据对象数据对象:D=ai|ai CharacterSet，i

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

9、pos，T)StrDelete(&S，pos，len)String串的常用操作（一）ReplaceReplace（&S&S，T T，V V）13字符串String串的常用操作（二）串的常用操作（二）赋值算子赋值算子拼接算子拼接算子比较算子比较算子 =!=!=和和 =重载下标算子重载下标算子 char&operator (char&operator (intint n);n);按字符定位下标按字符定位下标 intint Find(char Find(char c,intc,int start);start);反向寻找，定位尾部出现的字符反向寻找，定位尾部出现的字符 intint FindLast

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

11、和类定义字符串的顺序存储字符串的顺序存储用一个特殊的末尾标记用一个特殊的末尾标记0。字符串类字符串类class String的存储结构的存储结构 例如抽取子串函数：例如抽取子串函数：String s1=value-;s2=s1.Substr(2,3);上述语句涉及的存储形式如下页所示。上述语句涉及的存储形式如下页所示。16字符串字符串类class String的存储结构17字符串系系统统开开辟辟一一个个串串值值存存储储空空间间（串串值值可可利利用用空空间间），同时建立一个符号表；，同时建立一个符号表；建建立立一一个个新新串串时时，在在可可利利用用空空间间分分配配，并并在在符符号号表表中中记记录

12、录下下串串变变量量名名、串串值值在在可可利利用用空空间间的的位位置置、串长度等信息。串长度等信息。堆分配存储表示堆分配存储表示长度位置串名符号表串值存储空间18字符串31a长度位置串名符号表IEB串值存储空间19字符串44b31a长度位置串名符号表GNIJIEB串值存储空间20字符串88c44b31a长度位置串名符号表IAHGNAHSGNIJIEB串值存储空间21字符串616d88c44b31a长度位置串名符号表NIBRAHIAHGNAHSGNIJIEB串值存储空间22字符串用链表方式存储串值，每个结点大小相同。结点分为两个域data域next域串的块链存储表示串的块链存储表示结点大小为结点大

13、小为1 1的链表的链表ABCDEFhead结点大小为结点大小为4 4的链表的链表headDCBA#FE#占满占满存储密度存储密度=串值所占的存储位串值所占的存储位/实际分配的存储位。实际分配的存储位。23字符串讨论：讨论：法法1 1存储密度为存储密度为 ；法法2 2存储密度为存储密度为 ；显然，若数据元素很多，用法显然，若数据元素很多，用法2 2存储更优存储更优称为称为块链结构块链结构链式存储特点链式存储特点 ：用链表存储串值，易插入和删除。用链表存储串值，易插入和删除。法法1 1：链表结点的数据分量长度取链表结点的数据分量长度取1 1 1 1（个字符）（个字符）（个字符）（个字符）法法2 2

14、：链表结点（数据域）大小取链表结点（数据域）大小取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#NULL24字符串#define CHUNKSIZE 80 /每块大小，可每块大小，可由由用户定用户定义义typedef struct Chunk /首先定义结点类型首先定义结点类型 char ch CHUNKSIZE;/每个结点中的数据域每个结点中的数据域 struct Chunk*next;/每个结点中的指针域每个结点中的指针域Chunk;typedef struct /其次定义用链式存

15、储的串类型其次定义用链式存储的串类型 Chunk *head;/头指针头指针 Chunk *tail;/尾指针尾指针 int curLen;/结点个数结点个数 Lstring;/串类型只用一次，前面可以不加串类型只用一次，前面可以不加LstringLstring块链类型的定义25字符串字符串的模式匹配在串T中查找是否有与串P相等的子串，则称串T为目标(Target)，把P称为模式(Pattern)。称查找模式在目标中的匹配位置的运算为模式匹配(Pattern matching)。26字符串模式匹配算法简单模式匹配算法简单模式匹配算法BF算法算法 （又称古典的、经典的、朴素的、穷举的）又称古典的

16、、经典的、朴素的、穷举的）带回溯，速度慢带回溯，速度慢KMP(Knuth-Morris-Pratt)算法算法避免回溯，匹配速度快避免回溯，匹配速度快T=“longlonglongago”；P=“longlongago”；27字符串简单匹配算法思想算法设计思想：算法设计思想：将主串将主串S的第的第pos个字符和模式个字符和模式T的第的第1个字符比个字符比较，较，若相等，继续逐个比较后续字符；若相等，继续逐个比较后续字符；若不等，从主串若不等，从主串S的下一字符（的下一字符（pos+1）起，重新与）起，重新与T第一个字符比较。第一个字符比较。直到主串直到主串S的一个连续子串字符序列与模式的一个连续

17、子串字符序列与模式T相相等。返回值为等。返回值为S中与中与T匹配的子序列第一个字符匹配的子序列第一个字符的序号，即匹配成功。的序号，即匹配成功。否则，匹配失败，返回值否则，匹配失败，返回值 0.28字符串简单模式匹配算法过程lo n glo n glo nt0t1t2t3t4t5t6t7t8t9t10g a gt11t12t13o 0t14t15lo n glo n gp0p1p2p3p4p5p6p7a g o 0p8p9p10p11jijijijijijijijijijijijijijijijijijijijijijiji第一趟比较：第一趟比较：第二趟比较：第二趟比较：第三趟比较：第三趟比较

18、：第四趟比较：第四趟比较：第五趟比较：第五趟比较：ji29字符串简单匹配算法代码int Find(char*target,char*pat)int i=0,j=0;int lengthP=strlen(pat),lengthT=strlen(target);while(i=lengthT-lengthP)j=0;while(targeti=patj&jlengthP)i+;j+if(j=lengthP)return i-j;/串pat扫描完，匹配成功 else i=i-j+1;/不匹配，做下一趟比较 return 1;30字符串简单模式匹配算法分析设目标T的长度为n,模式P 的长度为m,在最坏

19、情况下，比较次数：在多数情况下，m远小于n,因此算法的最坏的时间复杂性为O(n*m)。复杂度高，效率低31(n-m+1)*m31字符串改进的算法KMP算法算法不做课程要求不做课程要求注重思想注重思想32字符串 T t0 ts ts+1 ts+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 .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位，位，下一趟比较从下

20、一趟比较从p pk k 与与t ts+js+j开始开始 33字符串KMP算法思想：当在某个位置匹配不成功的时候可以根据之前的匹配结果从模式字符串的另一个位置开始,而不必从头开始匹配字符串.K值如何确定？T t0 ts ts+1 ts+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 34字符串前缀子串：模式串前缀子串：模式串P开头的任意开头的任意k个字个字符符,p0,p1,pk-1。j位置的左子串：在位置的左子串：在P第第j位置的左边，位置的左边，取出取出k个字符，即个字符，即pj-k

21、+1,pj。第第j位的最长前缀串：与位的最长前缀串：与j位置左子串位置左子串相等的最长前缀子串。相等的最长前缀子串。coco colap0p1p2p3p4p5p6p7预备知识35字符串模式串的特征数和特征向量第第j位位的的最最长长前前缀缀串串的的长长度度k k就就是是模模式式串串P P在位置在位置j j上的上的特征数nj特特征征数数组组成成的的向向量量称称为为该该模模式式串串的的特征向量。其意义在于：其意义在于：表表示示一一旦旦匹匹配配过过程程中中p pj j与与t ti i比比较较不不等等，可可用用p p中中以以n n j-1j-1为为下下标标的的字字符符与与t ti i进进行行比较。比较。

22、36字符串MAX k,0 k=j 且且 P0 Pk-1=Pj-k+1 Pj-1 Pj 0 其它情况其它情况 nj=特征数定义示例示例 ：确定：确定特征数特征数 nj，P=cococola001234 0 c 1 o 2 c 3 o 4 c 5 o j P P nj 6 l0 7 a0 37字符串 运用运用KMP算法的匹配过程算法的匹配过程第第1趟趟 目标目标 a c a b a a b a a b c a c a a b c 模式模式 a b a a b c a c j=1 j=n(j-1)=0第第2趟趟 目标目标 a c a b a a b a a b c a c a a b c 模式模式

23、a b a a b c a c j=0 目标指针加目标指针加 1 第第3趟趟 目标目标 a c a b a a b a a b c a c a a b c 模式模式 a b a a b c a c j=5 j=n(j-1)=2 第第4趟趟 目标目标 a c a b a a b a a b c a c a a b c 模式模式 (a b)a a b c a c iiiiijjjjj38字符串ico c oco colat0t1t2t3t4t5t6t7t8t9t10coco colap0p1p2p3p4p5p6p7ico c oco colacoco colap0p1p2p3p4p5p6p7coc

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

25、1)Index(s,A)Index(s,t),Replace(s,STUDENT,q),Concat(SubString(s,6,2),Concat(t,SubString(s,7,8)41字符串已知下列字符串a=THISf=A SAMPLEc=GOODd=NEb=s=Concat(a,Concat(SubString(f,2,7),Concat(b,SubString(a,3,2)t=Replac(f,SubString(f,3,6),c)u=Concat(SubString(c,3,1),d)g=ISv=Concat(s,Concat(b,Concat(t,Concat(b,u),试问:s

26、,t,v,StrLength(s),Index(v,g),Index(u,g)各是什么?42字符串试问执行以下函数会产生怎样的输出结果?void demonstrate()StrAssign(s,THIS IS A BOOK);Replace(s,SubString(s,3,7),ESE ARE);StrAssign(t,Concat(s,S);StrAssign(u,XYXYXYXYXYXY);StrAssign(v,SubString(u,6,3);StrAssign(w,W);printf(t=,t,v=,v,u=,Replace(u,v,w);/demonstrate43字符串已知：s=(XYZ)+*，t=(X+Z)*Y。试利用联接、求子串和置换等基本运算，将 s 转化为 t。编写算法，从串 s 中删除所有和串 t 相同的子串。编写算法，实现串的基本操作 Replace(&S,T,V)。假设以块链结构作串的存储结构。试编写判别给定串是否具有对称性的算法，并要求算法的时间复杂度为 O(StrLength(S)。44字符串后续内容第第7章章 排序排序为了同为了同SSD5安排同步安排同步45字符串