《严蔚敏数据结构》PPT课件.ppt

第第4章章 串（串（String）4.1 4.1 串类型的定义串类型的定义4.2 4.2 串的表示和实现串的表示和实现4.3 4.3 串的模式匹配算法串的模式匹配算法1记为：记为：s=a1 a2.an (n0)串名串名串值（用串值（用 括起来）括起来）串串即字符串，是由零个或多个字符组成的即字符串，是由零个或多个字符组成的有限有限序列，序列，是是数据数据 元素为单个字符元素为单个字符的特殊线性表。的特殊线性表。4.1 4.1 串类型的定义串类型的定义隐含结束符隐含结束符0 0，即，即ASCIIASCII码码NULLNULL为何要单独讨论为何要单独讨论“串串”类型？类型？1 1）字符串操作比其他数据类型更复杂（如拷贝、连接操作）字符串操作比其他数据类型更复杂（如拷贝、连接操作）2 2）程序设计中，处理对象很多都是串类型。程序设计中，处理对象很多都是串类型。2若干术语：若干术语：串长：串长：串中字符的个数（串中字符的个数（n0n0）.n=0.n=0 时称为空串时称为空串 。空白串：空白串：由一个或多个由一个或多个空格符空格符组成的串。组成的串。问：空串和空白串有无区别？问：空串和空白串有无区别？答：答：有区别。有区别。空串空串(Null String)(Null String)是指长度为零的串；是指长度为零的串；而空白串而空白串(Blank String),(Blank String),是指包含一个或多是指包含一个或多个空白字符个空白字符 (空格键空格键)的字符串的字符串.3 子串：子串：子串位置：子串位置：字符位置：字符位置：串相等：串相等：例例1：现有以下现有以下4个字符串：个字符串：a=BEI b=JING c=BEIJING d=BEI JING问：问：他们各自的长度？他们各自的长度？a是是c和和d的子串，在的子串，在c和和d中的位置都是中的位置都是1串串S S中中任意个连续的字符任意个连续的字符序列叫序列叫S S的子串的子串;S;S叫叫主串主串。子串的第一个字符在主串中的序号。子串的第一个字符在主串中的序号。字符在串中的序号。字符在串中的序号。串长度相等，且对应位置上字符相等。串长度相等，且对应位置上字符相等。a是哪个串的子串？在主串中的位置是多少？是哪个串的子串？在主串中的位置是多少？a=3，b=4，c=7，d=8“空串是任意串的子串；任意串空串是任意串的子串；任意串S S都是都是S S本身的子串，除本身的子串，除S S本身本身外，外，S S的其他子串称为的其他子串称为S S的的真子串真子串。”数据结构与算法中山大学出版社数据结构与算法中山大学出版社 空串是哪个串的子串？空串是哪个串的子串？a是不是自己的子串？是不是自己的子串？4C语言中已有类似串运算函数！语言中已有类似串运算函数！ADT StringObjects:D=ai|aiCharacterSet,i=1,2,，n,n0Relations:R1=|ai-1,ai D,i=2,，nfunctions:/至少有至少有1313种基本操作种基本操作StrAssign(&T,chars)/串赋值串赋值，生成值为，生成值为charschars的串的串T TStrCompare(S,T)/串比较串比较，若，若STST，返回值大于，返回值大于00 StrLength(S)/求串长求串长，即返回串，即返回串S S中的元素个数中的元素个数 Concat(&T,S1,S2)/串连接串连接，用，用T T返回返回S1S1S2S2的新串的新串 SubString(&Sub,S,pos,len)/求求S S中中pospos起长度为起长度为lenlen的的子串子串 Index(S,T,pos)/子串定位函数（模式匹配），子串定位函数（模式匹配），返回位置返回位置 Replace(&S,T,V)/用子串用子串V V替换替换子串子串T TADT String串的抽象数据类型定义串的抽象数据类型定义（参见教材（参见教材P71P71）最最小小操操作作子子集集5注：注：ConcatConcat操作操作concatenationconcatenation，把，把多个短字符串合并为长字符串多个短字符串合并为长字符串复习：复习：C语言中常用的串运算语言中常用的串运算 C C串比较串比较：int strcmp(char*s1,char*s2);求串长：求串长：int strlen(char*s);串连接：串连接：char strcat(char*to,char*from)子串子串T T定位：定位：char strchr(char*s,char*c);注：用注：用C处理字符串时，要调用标准库函数处理字符串时，要调用标准库函数#include 类类CStrCompare(S,T)StrLength(S)Concat(&T,S1,S2)Index(S,T,pos)6Replace(&S,T,V)/用子串用子串V V替换子串替换子串T T 设设 s=I AM A STUDENT,t=GOOD,q=WORKER。求：。求：例例1：StrLength(s)StrLength(t)SubString(&sub,s,8,7)=SubString(&sub,t,2,1)=Index(s,A)=Index(s,t)=Replace(&s,STUDENT,q)=14 /参见参见P714STUDENTO30 （s中没有中没有t=GOOD！）！）Index(S,T,pos)/返回子串返回子串T T在在pospos之后的位置之后的位置I AM A WORKER7提问：提问：当当s=I AM A STUDENTs=I AM A STUDENT时时,INDEXINDEX（s,As,A，pospos）=3=3，若想搜索后面那个，若想搜索后面那个AA怎么办？怎么办？答答:根据根据教材教材P71P71倒倒1 1行行的函数说明，的函数说明，INDEXINDEX（s,As,A）返回的只是返回的只是“第一次第一次”出现的位置。出现的位置。如果还要搜索后面的如果还要搜索后面的A A，则，则pospos变量要跟着变才变量要跟着变才行。行。也就是说，要把得到的也就是说，要把得到的“第一次第一次”位置再代入位置再代入INDEXINDEX（s,As,A，pospos）函数中循环操作才行。）函数中循环操作才行。8解：因为解：因为SubString(s,6,2)A；SubString(s,7,8)STUDENTConcat(,t,SubString(s,7,8)GOOD STUDENT所以：所以：Concat(,SubString(s,6,2),Concat(t,SubString(s,7,8)A GOOD STUDENT例例2：设设 s=I AM A STUDENT,t=GOOD,求：求：Concat(SubString(s,6,2),Concat(t,SubString(s,7,8)？94.2 串的表示和实现串的表示和实现定长顺序存储表示定长顺序存储表示用一组地址连续的存储单元存储串值的字用一组地址连续的存储单元存储串值的字符序列，属符序列，属静态存储静态存储方式。方式。堆分配存储表示堆分配存储表示用一组地址连续的存储单元存储串值的字用一组地址连续的存储单元存储串值的字符序列符序列,但存储空间是在程序执行过程中但存储空间是在程序执行过程中动态动态分配分配而得。而得。串的块链存储表示串的块链存储表示链式方式存储链式方式存储首先强调：首先强调：串与线性表的运算有所不同，是以串与线性表的运算有所不同，是以“串的整体串的整体”作作为操作对象，例如查找某子串，在主串某位置上插入一个子串为操作对象，例如查找某子串，在主串某位置上插入一个子串等。等。串有三种机内表示方法：串有三种机内表示方法：顺序顺序存储存储链式链式存储存储10定长顺序存储特点：定长顺序存储特点：用一组连续的存储单元来存放串，用一组连续的存储单元来存放串，直接使用定长的字符数组来定义，数组的直接使用定长的字符数组来定义，数组的上界预先给出上界预先给出，故称为故称为静态存储静态存储分配。分配。例如：例如：#define Maxstrlen 255 /用户可用的最大串长用户可用的最大串长 typedef unsigned char SString Maxstrlen1 SString;/P73 SString s;/s 是一个可容纳是一个可容纳255个字符的顺序串。个字符的顺序串。注：注：一般用一般用SString0来存放来存放串长串长信息（如信息（如pascal语言）；语言）；C语言约定在串尾加结束符语言约定在串尾加结束符 0，以利操作加速，但不，以利操作加速，但不计入串长计入串长（用首址和串长、或首址和尾标记来描述串数组）（用首址和串长、或首址和尾标记来描述串数组）若字符串超过若字符串超过Maxstrlen 则自动截断则自动截断（因为静态数组存不（因为静态数组存不 进去）。进去）。11例：例：用用顺序存储方式顺序存储方式编写编写求子串函数求子串函数SubString(SubString(&Sub,S,pos,len)Sub,S,pos,len)Status SubString(SString&sub,SString S,int pos,int len)if(posS0|lenS0-pos+1)return ERROR;/若若pospos和和lenlen参数越界，则告警参数越界，则告警 Sub1len=Spospos+len-1;Sub0=len;return OK;将串将串S S中从第中从第pospos个字符开始、长度为个字符开始、长度为lenlen的字符序列复制到串的字符序列复制到串SubSub中。中。（注：考虑到函数的通用性，应当让串（注：考虑到函数的通用性，应当让串SubSub的预留长度与的预留长度与S S一样）一样）子串长度子串长度s=a1 a2.anposlenSub 讨论：想存放讨论：想存放超长超长字符串怎么办？字符串怎么办？改用改用动态分配动态分配的一维数组的一维数组堆堆12思路：思路：利用利用mallocmalloc函数合理预设串长空间。函数合理预设串长空间。特点：特点：若在操作中串值改变，还可以利用若在操作中串值改变，还可以利用reallocrealloc函数函数按新串长度按新串长度增加空间增加空间（即动态数组概念）（即动态数组概念）。Typedef struct char*ch;/若非空串若非空串,按串长分配空间按串长分配空间;否则否则ch=NULLch=NULL int length;/串长度串长度HString堆分配存储特点：堆分配存储特点：仍用一组连续的存储单元来存放串，但仍用一组连续的存储单元来存放串，但 存储空间是在程序执行过程中存储空间是在程序执行过程中动态分配动态分配而得。而得。堆堆T T的存储结构描述：的存储结构描述：T.ch13C C是指针变量，可以自增！是指针变量，可以自增！意即每次后移一个数据单意即每次后移一个数据单元。元。直到终值为直到终值为“假假”停止，串尾特征是停止，串尾特征是c c00NULLNULL0 0Status StrAssign(HString&T,char*chars)/生成一个串生成一个串T,TT,T值值串常量串常量charschars if(T.ch)free(T.ch);/释放释放T T原有空间原有空间 for(i=0,c=chars;c c;+i,+c);/求求charschars的串长度的串长度i i例例1：编写编写建堆函数建堆函数 (参见教材参见教材P76）此处此处T.ch0T.ch0没有用没有用来装串长，因为另来装串长，因为另有有T.length T.length 分量分量if(!i)T.ch=NULL;T.length=0;else if(!(T.ch=(char*)malloc(i*sizeof(char)exit(OVERFLOW);T.ch0.i-1=chars0.i-1;T.length=i;Return OK;/StrAssign14Status StrInsert(HString&S,int pos,HString T)/在串在串S S的第的第pospos个字符个字符之前之前（包括尾部）插入串（包括尾部）插入串T Tif(posS.length+1)return ERROR;/pos/pos不合法则告警不合法则告警 if(T.length)/只要串只要串T T不空，就需要重新分配不空，就需要重新分配S S空间，以便插入空间，以便插入T T if(!（S.ch=(char*)realloc(S.ch,(S.length+T.length)*sizeof(char)exit(OVERFLOW);/若开不了新空间，则退出若开不了新空间，则退出 for(i=S.length-1;i=pos-1;-i)S.chi+T.length=S.chi;/为插入为插入T T而腾出而腾出pospos之后的位置，即从之后的位置，即从S S的的pospos位置起全部字符均后移位置起全部字符均后移 S.chpos-1pos+T.length-2=T.ch0-1;/插入插入T T，略，略/0/0 S.length+=T.length;/刷新刷新S S串长度串长度 return OK;/StrInsert例例2：用用“堆堆”方式编写方式编写串插入函数串插入函数(参见教材参见教材P75)P75)15讨论：讨论：法法1 1存储密度为存储密度为 ；法；法2 2存储密度为存储密度为 ；显然，若显然，若数据元素很多，用法数据元素很多，用法2 2存储更优存储更优称为称为块链结构块链结构链式存储特点链式存储特点 ：用链表存储串值，易插入和删除。用链表存储串值，易插入和删除。法法1 1：链表结点的数据分量长度取链表结点的数据分量长度取1 1 1 1（个字符）（个字符）（个字符）（个字符）法法2 2：链表结点（数据域）大小取链表结点（数据域）大小取n n(例如例如n=4)n=4)1/21/29/15=3/59/15=3/5 A B C I NULLheadheadA B C D E F G H I#NULL16对块链表的整体描述对块链表的整体描述#define CHUNKSIZE 80 /每块大小，可由用户定义每块大小，可由用户定义typedef struct Chunk /首先定义结点类型首先定义结点类型 char ch CHUNKSIZE;/每个结点中的数据域每个结点中的数据域 struct Chunk*next;/每个结点中的指针域每个结点中的指针域Chunk;块链类型定义：块链类型定义：块链函数的编写略块链函数的编写略typedef struct /其次定义用链式存储的串类型其次定义用链式存储的串类型 Chunk *head;/头指针头指针 Chunk *tail;/尾指针尾指针 int curLen;/结点个数结点个数 Lstring;/串类型只用一次，前面可以不加串类型只用一次，前面可以不加LstringLstring对每个结点的描述对每个结点的描述17算法目的：算法目的：确定主串中所含子串第一次出现的位置确定主串中所含子串第一次出现的位置（定位定位）4.3 串的模式匹配算法串的模式匹配算法（属于选讲部分）（属于选讲部分）BF算法算法 （又称古典的、经典的、朴素的、穷举的）（又称古典的、经典的、朴素的、穷举的）KMP算法算法算法种类：算法种类：带回溯，速度慢带回溯，速度慢避免回溯，匹配速度快，避免回溯，匹配速度快，是全课程的亮点之一是全课程的亮点之一定位问题称为串的模式匹配定位问题称为串的模式匹配(Pattern Matching)(Pattern Matching)，即子串定位运，即子串定位运算，算，它是串处理系统中最重要的操作之一。它是串处理系统中最重要的操作之一。典型函数为典型函数为Index(S,T,pos)Index(S,T,pos)Index(S,T,pos)Index(S,T,pos)，见教材见教材P71P7118BFBF算法的实现算法的实现即编写即编写Index(S,T,pos)函数函数例例1 1：S S=ababcabcacbab，T T=abcac，pospos=1=1，求：串求：串T T在串在串S S中第中第pospos个字符之后的位置。个字符之后的位置。利用利用演示系统演示系统看看BFBF算法执行过程。算法执行过程。BFBF算法设计思想：算法设计思想：将主串将主串S S的第的第pospos个字符和模式个字符和模式T T的第的第1 1个字符比较，个字符比较，若若相等相等，继续逐个比较后续字符；，继续逐个比较后续字符；若若不等不等，从主串，从主串S S的下一字符（的下一字符（pos+1pos+1）起，重新与起，重新与T T第一第一个字符比较。个字符比较。直到主串直到主串S S的一个连续子串字符序列与模式的一个连续子串字符序列与模式T T相等。返回值相等。返回值为为S S中与中与T T匹配的子序列匹配的子序列第一个字符的序号第一个字符的序号，即匹配成功。，即匹配成功。否则，匹配失败，返回值否则，匹配失败，返回值 0.0.19Int IndexIndex(SString S,SString T,int pos)i=pos;j=1;while(i=S0&jT0)return i-T0;/子串结束，说明匹配成功子串结束，说明匹配成功 else return0;/Index例例2 2：S S=ababcabcacbab，T T=abcac，求求Index(S,T,5)Index(S,T,5)（参见教材（参见教材（参见教材（参见教材P79P79）相当于子串向右滑动一个字符位置相当于子串向右滑动一个字符位置匹配成功后指针仍要回溯！因为要返回的匹配成功后指针仍要回溯！因为要返回的是被匹配的首个字符位置。是被匹配的首个字符位置。i ij jS=a b a b c a b c a c b a bT=T=a b c a cpos=520讨论：讨论：若若n n为主串长度，为主串长度，m m为子串长度，则串的为子串长度，则串的BFBF匹配算法最坏的情匹配算法最坏的情况下需要比较字符的总次数为况下需要比较字符的总次数为(n-m+1)*mO(n*m)一般的情况是：一般的情况是：O(n+m)推导方法：推导方法：要从最好到最坏情况统计总的比较次数，然后要从最好到最坏情况统计总的比较次数，然后要从最好到最坏情况统计总的比较次数，然后要从最好到最坏情况统计总的比较次数，然后取平均。取平均。取平均。取平均。BF算法的时间复杂度算法的时间复杂度最好的情况是：最好的情况是：一配就中！一配就中！只比较了只比较了m m次。次。能否利用已能否利用已部分匹配过部分匹配过的信息而加快模式串的滑动速度？的信息而加快模式串的滑动速度？能！能！而且主串而且主串S S的指针的指针i i不必回溯不必回溯！最坏情况也能达到！最坏情况也能达到O(n+m)O(n+m)请看请看KMP算法！算法！最恶劣情况是：最恶劣情况是：主串前面主串前面n-mn-m个位置都个位置都部分匹配部分匹配到子串的最后一到子串的最后一位，即这位，即这n-mn-m位比较了位比较了m m次，别忘了最后次，别忘了最后m m位也各比较了一次，还位也各比较了一次，还要加上要加上m m！所以总次数为：！所以总次数为：(n-m)*m+m(n-m+1)*m21KMP算法算法（特点：速度快）（特点：速度快）KMPKMP算法设计思想算法设计思想 KMPKMP算法的推导过程算法的推导过程 KMPKMP算法的实现算法的实现 （关键技术（关键技术:计算计算nextjnextj）KMPKMP算法的时间复杂度算法的时间复杂度全书一大亮点！全书一大亮点！22