5字符串

数据结构与算法For软件学院08级本科生2009-2010秋3字符串字符串2/40主要内容•字符串抽象数据类型•字符串的存储结构和类定义•字符串运算的算法实现•字符串的模式匹配主要掌握3.4.1字符串3/40字符串抽象数据类型•基本概念•字符串抽象数据类型•String抽象数据类型字符串4/40重要性•串（字符串），是计算机非数值处理的主要对象之一。–如，在汇编和编译程序中，源程序和目标程序都是串；–如，在事务处理程序中，顾客的姓名和地址，以及货物的名称、产地和规格等，通常也都作为串处理。•由于我们现今使用的计算机的硬件结构主要是面向数值计算的需要，基本上没有提供对串进行操作的指令，因此需要用软件来实现串数据类型。字符串5/40基本概念•字符串，由0个或多个字符的顺序排列所组成的复合数据结构，简称“串”。•串的长度：一个字符串所包含的字符个数。–空串：长度为零的串，它不包含任何字符内容。•字符(char)：组成字符串的基本单位。字符串6/40串中任意个连续的字符组成的子序列称为该串的子串。包含子串的串相应的称为主串。例，串eij是串beijing的子串，beijing称为主串。字符在序列中的序号称为该字符在串中的位置。子串在主串中的位置定义为子串的第一个字符在主串中的位置。例，字符‘n’在串beijing中的位置为6。例，子串eij在串beijing中的位置为。2字符串7/40•串–由零个或多个字符组成的有限序列。–记作S=a1a2…an（n0）•串名：S；•串值：用单引号括起来的字符序列。–长度：串中字符的数目。–空串：含零个字符的串，表示。–空格串：由一个或多个空格组成的串。–子串：串中任意个连续的字符组成的子序列。–字符在串的位置：字符在序列中的序号。–子串在串的位置：子串的第一个字符在串中的位置。–相等：当且仅当两个串的值相等。串值必须用一对单引号括起来空串与空格串的区别？字符串8/40两个串相等，当且仅当这两个串的值相等。例，串beijing与串beijing不相等。串值必须用一对单引号括起来，但单引号本身不属于串，只起界定作用。由一个或多个空格组成的串称为空格串。φ≠字符串9/40串与线性表区别•串的数据对象约束为字符集。•串的基本操作与线性表有很大差别–线性表的基本操作中，大多以“单个元素”作为操作对象，如查找某个元素、在某个位置上插入一个元素和删除一个元素。–串的基本操作中，通常以“串的整体”作为操作对象。如在串中查找某个子串、在串的某个位置上插入一个子串以及删除一个子串。字符串10/40例子a=BEIb=JINGc=BEIJINGd=BEIJING长度分别为3、4、7、8；a和b都是c和d的子串；a在c和d中的位置都是1；b在c和d中的位置是4和5；a、b、c、d彼此不相等。字符串11/40String抽象数据类型•字符串类（classString）：–不采用charS[M]的形式–而采用一种动态变长的存储结构。字符串12/40ClearString(&S)结果:将S清为空串。条件:串S已存在。数据对象:D={ai|ai∈CharacterSet，i=1,2,…,n}数据关系:R1={ai-1,ai}基本操作:ADTString{}ADTStringDestroyString(&S)结果:销毁串S。条件:串S已存在。StrAssign(&T，chars)结果:生成一个其值等于chars的串T。条件:chars是字符串常量。字符串13/40StrEmpty(S)StrCopy(&T，S)StrCompare(S，T)StrLength(S)Concat(&T，S1，S2)SubString(&Sub，S，pos，len)Index(S，T)Replace(&S，T，V)StrInsert(&S，pos，T)StrDelete(&S，pos，len)String串的常用操作（一）字符串14/40String串的常用操作（二）•赋值算子＝•拼接算子＋•比较算子==!=和==•重载下标算子[]char&operator[](intn);•按字符定位下标intFind(charc,intstart);•反向寻找，定位尾部出现的字符intFindLast(charc);字符串15/40串的表示和实现•定长顺序存储表示——用一组地址连续的存储单元存储串值的字符序列，属静态存储方式。•堆分配存储表示——用一组地址连续的存储单元存储串值的字符序列,但存储空间是在程序执行过程中动态分配而得。•串的块链存储表示——链式方式存储首先强调：串与线性表的运算有所不同，是以“串的整体”作为操作对象，例如查找某子串，在主串某位置上插入一个子串等。串有三种机内表示方法：顺序存储链式存储字符串16/40字符串的存储结构和类定义•字符串的顺序存储–用一个特殊的末尾标记'\0'。•字符串类classString的存储结构例如抽取子串函数：Strings1=value-;s2=s1.Substr(2,3);上述语句涉及的存储形式如下页所示。字符串17/40字符串类classString的存储结构字符串18/40•系统开辟一个串值存储空间（串值可利用空间），同时建立一个符号表；•建立一个新串时，在可利用空间分配，并在符号表中记录下串变量名、串值在可利用空间的位置、串长度等信息。堆分配存储表示长度位置串名符号表串值存储空间字符串19/4031a长度位置串名符号表IEB串值存储空间字符串20/4044b31a长度位置串名符号表GNIJIEB串值存储空间字符串21/4088c44b31a长度位置串名符号表IAHGNAHSGNIJIEB串值存储空间字符串22/40616d88c44b31a长度位置串名符号表NIBRAHIAHGNAHSGNIJIEB串值存储空间字符串23/40•用链表方式存储串值，每个结点大小相同。•结点分为两个域–data域–next域串的块链存储表示结点大小为1的链表ABCDEFhead结点大小为4的链表headDCBA##FE#占满存储密度=串值所占的存储位/实际分配的存储位。字符串24/40讨论：法1存储密度为；法2存储密度为；显然，若数据元素很多，用法2存储更优—称为块链结构链式存储特点：用链表存储串值，易插入和删除。法1：链表结点的数据分量长度取1（个字符）法2：链表结点（数据域）大小取n(例如n=4)1/29/15=3/5ABCINULLheadheadABCDEFGHI###NULL字符串25/40#defineCHUNKSIZE80//每块大小，可由用户定义typedefstructChunk{//首先定义结点类型charch[CHUNKSIZE];//每个结点中的数据域structChunk*next;//每个结点中的指针域}Chunk;typedefstruct{//其次定义用链式存储的串类型Chunk*head;//头指针Chunk*tail;//尾指针intcurLen;//结点个数}Lstring;//串类型只用一次，前面可以不加Lstring块链类型的定义字符串26/40字符串的模式匹配•在串T中查找是否有与串P相等的子串，则称串T为目标(Target)，把P称为模式(Pattern)。•称查找模式在目标中的匹配位置的运算为模式匹配(Patternmatching)。字符串27/40模式匹配算法•简单模式匹配算法–BF算法（又称古典的、经典的、朴素的、穷举的）–带回溯，速度慢•KMP(Knuth-Morris-Pratt)算法–避免回溯，匹配速度快•T=“longlonglongago”；•P=“longlongago”；字符串28/40简单匹配算法思想•算法设计思想：•将主串S的第pos个字符和模式T的第1个字符比较，–若相等，继续逐个比较后续字符；–若不等，从主串S的下一字符（pos+1）起，重新与T第一个字符比较。•直到主串S的一个连续子串字符序列与模式T相等。返回值为S中与T匹配的子序列第一个字符的序号，即匹配成功。•否则，匹配失败，返回值0.字符串29/40简单匹配算法代码intFind(char*target,char*pat){inti=0,j=0;intlengthP=strlen(pat),lengthT=strlen(target);while(i=lengthT-lengthP){j=0;while(target[i]==pat[j]&&jlengthP){i++;j++}if(j==lengthP)returni-j;//串pat扫描完，匹配成功elsei=i-j+1;//不匹配，做下一趟比较}return–1;}字符串30/40简单模式匹配算法过程longlonglont0t1t2t3t4t5t6t7t8t9t10gagt11t12t13o\0t14t15longlongp0p1p2p3p4p5p6p7ago\0p8p9p10p11jijijijijijijijijijijijijijijijijijijijijijiji第一趟比较：第二趟比较：第三趟比较：第四趟比较：第五趟比较：ji字符串31/40IntIndex(SStringS,SStringT,intpos){i=pos;j=1;while(i=S[0]&&j=T[0]){if(S[i]==T[j]){++i,++j}//继续比较后续字符else{i=i-j+2;j=1;}//指针回溯到下一首位，重新开始匹配}if(jT[0])returni-T[0];//子串结束，说明匹配成功elsereturn0;}//Index例2：S=ababcabcacbab，T=abcac，求Index(S,T,5)相当于子串向右滑动一个字符位置匹配成功后指针仍要回溯！因为要返回的是被匹配的首个字符位置。ijS=ababcabcacbabT=abcacpos=5字符串32/40简单模式匹配算法分析•设目标T的长度为n,模式P的长度为m,在最坏情况下，比较次数：•在多数情况下，m远小于n,因此算法的最坏的时间复杂性为O(n*m)。•复杂度高，效率低32(n-m+1)*m字符串33/40改进的算法•KMP算法–不做课程要求–注重思想字符串34/40Tt0…tsts+1ts+2ts+3…ts+j-k-1ts+j-k..ts+j-1ts+j…‖‖‖‖‖Pp0p1p2p3…pj-k-1pj-k….pj-1pjp0…………………...pj-2pj-1…p0…………….…..pj-3pj-2…p0……………..pj-4pj-3……..p0………pkpk+1…p0…pk-1pk…不需要回溯目标指针，模式右滑j-k位，下一趟比较从pk与ts+j开始字符串35/40KMP算法•思想：当在某个位置匹配不成功的时候可以根据之前的匹配结果从模式字符串的另一个位置开始,而不必从头开始匹配字符串.•K值如何确定？Tt0…tsts+1ts+2ts+3…ts+j-k-1ts+j-k..ts+j-1ts+j…‖‖‖‖‖Pp0p1p2p3…pj-k-1pj-k….pj-1pjp0…pk-1pk…字符串36/40基础知识题：思考•简述空串和空格串(或称空格符串)的区别。•设s=IAMASTUDENT,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),Concat(SubString(s,6,2),Concat(t,SubString(s,7,8)))字符串37/40•已知下列字符串a=THISf=ASAMPLEc=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(SubStrin