数据结构第四章ppt课件

1、第第4章章 串串String） 4.1 串类型的定义串类型的定义 4.2 串的表示和实现串的表示和实现 4.2.1 定长顺序存储表示定长顺序存储表示 4.2.2 堆分配存储表示堆分配存储表示 4.2.3 串的块链存储表示串的块链存储表示 4.3 串基本操作的实现串基本操作的实现记为：记为： s = a1 , a2 , . , an (n0 ) 串名串名串值用串值用 括起来）括起来）定义：定义：串即字符串，是由零个或多个字符组成的有串即字符串，是由零个或多个字符组成的有限序列，是数据元素为单个字符的特殊线性表。限序列，是数据元素为单个字符的特殊线性表。4.1 4.1 串类型的定义串类型的定义隐含

2、结束符隐含结束符/0 ，即即ASCII码码NUL 若干术语：若干术语： 串长：串长： 空白串：空白串： 子串：子串： 串相等：串相等：串中字符个数串中字符个数n0n0）. n=0 . n=0 时称为空串时称为空串 。由一个或多个空格符组成的串。由一个或多个空格符组成的串。串串s s中任意个连续的字符序列叫中任意个连续的字符序列叫s s的子串的子串; S; S叫主串。叫主串。串长度相等，且对应位置上字符相等。串长度相等，且对应位置上字符相等。 附：附：1.空串空串(Null String)是指长度为零的串；而空白串是指长度为零的串；而空白串(Blank String)是指包含一个或多个空白字符是

3、指包含一个或多个空白字符 (空格键空格键)的字符串的字符串.2. 空串是任意串的子串，任意串是其自身的子串。空串是任意串的子串，任意串是其自身的子串。3.通常将子串在主串中首次出现时该子串的首字符对应的主串通常将子串在主串中首次出现时该子串的首字符对应的主串中的序号，定义为子串在主串中的序号或位置）。中的序号，定义为子串在主串中的序号或位置）。练练1：现有以下：现有以下4个字符串：个字符串：a =BEI b =JING c = BEIJINGBEI d = BEI JING问：问： 他们各自的长度？他们各自的长度？ a是哪个串的子串？在主串中的位置是多少？是哪个串的子串？在主串中的位置是多少？

4、a =3，b =4，c = 7，d=8a是是c和和d的子串，在的子串，在c和和d中的位置都是中的位置都是1串的抽象数据类型定义参见教材串的抽象数据类型定义参见教材P71） 设设 s =I AM A STUDENT, t =GOOD, q=WORKER。求：。求：例例2： StrLength(s) StrLength(t) SubString(s, 8, 7)= SubString(t, 2, 1)= Index(s, A,4)= Index( s, t)=Replace(s, STUDENT,q)=144STUDENTO60 （ s中没有中没有t！）！）I AM A WORKER考虑：考虑：C

5、oncat(SubString(s,6,2), Concat(t,SubString(s,7,8) ？ 4.2 串的表示和实现串的表示和实现 注：注： 因为串是特殊的线性表，故其存储因为串是特殊的线性表，故其存储结构与线性表的存储结构类似。但是，串结构与线性表的存储结构类似。但是，串与线性表的运算又有所不同，是以与线性表的运算又有所不同，是以“串的串的整体作为操作对象，例如查找某子串，整体作为操作对象，例如查找某子串，在主串某位置上插入一个子串等。在主串某位置上插入一个子串等。 定长顺序存储表示定长顺序存储表示 用一组地址连续的存储单元存储串值的用一组地址连续的存储单元存储串值的字符序列字符序

6、列 堆分配存储表示堆分配存储表示 用一组地址连续的存储单元存储串值的用一组地址连续的存储单元存储串值的字符序列字符序列,但存储空间是在程序执行过程中但存储空间是在程序执行过程中动态分配而得。动态分配而得。 串的块链存储表示串的块链存储表示 链式方式存储链式方式存储串有三种机内表示方法：串有三种机内表示方法：顺序顺序存储存储链式链式存储存储 特点：特点： 用一组连续的存储单元来存放串，直接用一组连续的存储单元来存放串，直接使用定长的字符数组来定义，数组的上界预先给使用定长的字符数组来定义，数组的上界预先给出，故称为静态存储分配。出，故称为静态存储分配。例如：例如：#define Maxstrle

7、n 255 /用户可用的最大串长用户可用的最大串长typedef unsigned char SString Maxstrlen1 ;SString s; /s是一个可容纳是一个可容纳255个字符的顺序个字符的顺序串。串。4.2.1 定长顺序存储表示定长顺序存储表示注：注： 一般用一般用SString0来存放串长信息；来存放串长信息； C语言约定在串尾加结束符语言约定在串尾加结束符 0，以利操作加速，但不计，以利操作加速，但不计入串长；入串长； 若字符串超过若字符串超过Maxstrlen 则自动截断因为静态数组存不则自动截断因为静态数组存不 进去）。进去）。 若不设结束符，可用一个整数来表示串

8、的长度，那么该长若不设结束符，可用一个整数来表示串的长度，那么该长度减度减1的位置就是串值的最后一个字符的位置。那么：位置。的位置就是串值的最后一个字符的位置。那么：位置。此时顺序串的类型定义和顺序表类似：此时顺序串的类型定义和顺序表类似： typedef struct char chmaxstrlen; int length; sstring; /其优点是涉及到串长操作时速度快。其优点是涉及到串长操作时速度快。实现方式：实现方式：参见教材参见教材P73编程两例，两串连接和求子串编程两例，两串连接和求子串例：顺序方式实现求子串函数例：顺序方式实现求子串函数SubString(&Sub, S,

9、pos, len) /将串将串S中从第中从第pos个字符开始长度为个字符开始长度为len的字符的字符序列复制到串序列复制到串Sub中中 （注：串（注：串Sub的预留长度与的预留长度与S一样）一样）Status SubString(SString &sub, SString S, int pos, int len ) if(posS0 | lenS0-pos+1) return ERROR; /pos不合法则警告 Sub1len=Spospos+len-1; Sub0=len; return OK;s = a1 , a2 , . , an串长串长poslen考虑：考虑：超长字符串如何存储超长字符

10、串如何存储静态数组有缺陷！静态数组有缺陷！引入动态分配的一维数组引入动态分配的一维数组 “堆堆”！思路：思路： 利用利用mallocmalloc函数合理预设串长空间。若在操作中串值改函数合理预设串长空间。若在操作中串值改变，还可以利用变，还可以利用reallocrealloc函数按新串长度增加函数按新串长度增加( (堆砌堆砌) )空空间。堆存储的串，其关键信息放置在：间。堆存储的串，其关键信息放置在：Typedef struct char *ch; / 若非空串若非空串,按串长分配空间按串长分配空间; 否则否则 ch = NULL int length; /串长度串长度HString 特点：特

11、点： 仍用一组连续的存储单元来存放串，但存储空间仍用一组连续的存储单元来存放串，但存储空间是在程序执行过程中动态分配而得。是在程序执行过程中动态分配而得。4.2.2 堆分配存储表示堆分配存储表示Status StrInsert ( HString &S, int pos, HString T ) /在串S的第pos个字符之前包括尾部插入串Tif (posS.length+1) return ERROR; /pos不合法则警告If (T.length) /只要串T不空，就需要重新分配S的空间，以便插入T if (!（S.ch=(char*)realloc(S.ch, (S.length+T.le

12、ngth)*sizeof(char) ) exit(OVERFLOW); for ( i=S.length-1; i=pos-1; -i ) /为插入T而腾出pos之后的位置 S.chi+T.length = S.chi; /从S的pos位置起全部字符均后移 S.chpos-1pos+T.length-2 = T.ch0T.length-1; /插入T，忽略/0 S.length + = T.length; /刷新串S的长度 return OK;/StrInsert例：用例：用“堆实现串插入操作堆实现串插入操作(教材教材P75) Status StrAssign(HString &T, cha

13、r *chars) /生成其值等于串常量chars的串Tif (T.ch) free(T.ch); /释放T原有空间for (i=0, c=chars; c; +i, +c); /求串chars的长度iif (!i) T.ch = NULL; T.length = 0; /判断chars是否是空串else if (!(T.ch = (char*)malloc(i*sizeof(char) exit(OVERFLOW); /创建大小为i的字符型空间给T.ch T.ch0.i-1 = chars0.i-1;T.length =i;Return OK;/StrAssign指针变量指针变量C也可以自增

14、！也可以自增！意即每次后移一个数据意即每次后移一个数据单元。单元。例：堆分配存储表示例：堆分配存储表示(教材教材P76) 直到终值为直到终值为“假假停顿，串尾特征是停顿，串尾特征是/0NUL=04.2.3 串的块链存储表示串的块链存储表示特点特点 ： 用链表存储串值，易插入和删除。顺序串上用链表存储串值，易插入和删除。顺序串上的插入和删除操作不方便，需要移动大量的字符；因的插入和删除操作不方便，需要移动大量的字符；因而，我们可用单链表方式来存储串值，串的这种链式而，我们可用单链表方式来存储串值，串的这种链式存储结构简称为链串。存储结构简称为链串。说明：说明： 这种结构便于进行插入和删除运算，但

15、存储这种结构便于进行插入和删除运算，但存储空间利用率太低。空间利用率太低。为了提高存储密度，可使每个结点存放多个字符。通为了提高存储密度，可使每个结点存放多个字符。通常将结点数据域存放的字符个数定义为结点的大小，常将结点数据域存放的字符个数定义为结点的大小，显然，当结点大小大于显然，当结点大小大于1时，串的长度不一定正好是时，串的长度不一定正好是结点的整数倍，因此要用特殊字符来填充最后一个结结点的整数倍，因此要用特殊字符来填充最后一个结点，以表示串的终结。点，以表示串的终结。那么：法那么：法1 1存储密度为存储密度为 ；法；法2 2存储密度为存储密度为 ；显然，若数据元素很多，用法显然，若数据

16、元素很多，用法2 2存储更优存储更优称为块链结构称为块链结构法法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 # # # NULL#define CHUNKSIZE 80 /可由用户定义的块大可由用户定义的块大小小typedef struct Chunk /首先定义结点类型首先定义结点类型 char ch CHUNKSIZE ; /结点中的数据域结点中的数据域 struct Ch

17、unk * next ; /结点中的指针域结点中的指针域Chunk; 块链类型定义：块链类型定义：例略例略typedef struct /其次定义用链式存储的串其次定义用链式存储的串类型类型 Chunk *head; /串的头指针串的头指针 Chunk *tail; /串的尾指针串的尾指针 int curLen; /串的当前结点个数长度）串的当前结点个数长度） Lstring; /串类型只用一次，前面可以不加串类型只用一次，前面可以不加Lstring 例：用顺序存储方式实现求子串函数例：用顺序存储方式实现求子串函数SubString (教材教材P75) 例：用例：用“堆实现串插入操作堆实现串插

18、入操作(教材教材P75) 例：堆分配存储表示例：堆分配存储表示(教材教材P76)4.3 串基本操作的实现串基本操作的实现算法目的：确定主串中所含子串第一次出现的位置定位）算法目的：确定主串中所含子串第一次出现的位置定位） 即如何实现即如何实现 Index(S,T,pos)Index(S,T,pos)函数见教材函数见教材P71P71）4.4 串的模式匹配算法串的模式匹配算法模式匹配模式匹配(Pattern Matching) (Pattern Matching) 即子串定位运即子串定位运算。算。初始条件：串初始条件：串S S和和T T存在，存在，T T是非空串，是非空串，1posStrLengt

19、h(s)1posStrLength(s)操作结果：若主串操作结果：若主串S S中存在和串中存在和串T T值相同的子串，则返回它在主值相同的子串，则返回它在主串串S S中第中第pospos个字符之后第一次出现的位置；否则函数值为个字符之后第一次出现的位置；否则函数值为0 0。注：注：S S称为被匹配的串，称为被匹配的串，T T称为模式串。若称为模式串。若S S包含串包含串T T，则称，则称“匹配成功匹配成功”。否则称。否则称 “ “匹配不成功匹配不成功” ” 。 BF BF算法设计思想：算法设计思想：将主串的第将主串的第pospos个字符和模式的第个字符和模式的第1 1个字符比较，个字符比较，

20、若相等，继续逐个比较后续字符；若相等，继续逐个比较后续字符； 若不等，从主串的下一字符若不等，从主串的下一字符pos+1pos+1起，重新起，重新与第一个字符比较。与第一个字符比较。 BF算法算法 （又称古典或经典的、朴素的、穷（又称古典或经典的、朴素的、穷举的）举的） KMP算法特点：速度快）算法特点：速度快）算法：算法： 直到主串的一个连续子串字符序列与模式相等直到主串的一个连续子串字符序列与模式相等 。返回值。返回值为为S S中与中与T T匹配的子序列第一个字符的序号，即匹配成功。匹配的子序列第一个字符的序号，即匹配成功。 否则，匹配失败，返回值否则，匹配失败，返回值 0 .0 .S=a

21、 b a b c a b c a c b a bT=a b c a cT=a b c a cpos=5Int Index(SString S, SString T, int pos) i=pos; j=1; while ( i=S0 & jT0) return i-T0; /子串结束，说明匹配成功 else return0;/Index BF BF算法的实现算法的实现即即IndexIndex（）操作的实现（）操作的实现 （见教材（见教材P79P79） S=a b a b c a b c a c b a bT=a b c a cT=a b c a cpos=5相当于子串向右滑动一个字符位置相当于

22、子串向右滑动一个字符位置匹配成功后指针仍要回溯！因为要返回的是被匹匹配成功后指针仍要回溯！因为要返回的是被匹配的首个字符位置。配的首个字符位置。i ij jKMP算法特点：速度快）算法特点：速度快） KMP KMP算法设计思想算法设计思想 KMP KMP算法的推导过程算法的推导过程 KMP KMP算法的实现算法的实现 （关键技术（关键技术: :计算计算nextjnextj） KMP KMP算法的时间复杂度算法的时间复杂度能否利用已经部分匹配的结果而加快模式串的滑动速度？能否利用已经部分匹配的结果而加快模式串的滑动速度？能！而且主串能！而且主串S S的指针的指针i i不必回溯！可提速到不必回溯！

23、可提速到O(n+m)O(n+m)！例：例： KMP KMP算法设计思想：算法设计思想： ( (参见教材参见教材P80-84P80-84）S=a b a b c a b c a c b a bT=a b c a cT=a b c a cS=a b a b c a b c a c b a bT=a b c a cT=a b c a cS=a b a b c a b c a c b a bT=a b c a cT=a b c a cIndex_kmpIndex_kmp的返回值应为的返回值应为i=6i=6需要讨论两个问题：需要讨论两个问题： 如何如何“记忆部分匹配结果？记忆部分匹配结果？ 如何由如何由

24、“记忆结果计算出主串记忆结果计算出主串S S第第i i个字符应该与模式个字符应该与模式T T中中哪个字符再比较？即确定模式哪个字符再比较？即确定模式T T中的新比较起点中的新比较起点k.k.i ii ii ik kk k a b aa b ci ik kj jS=a b a b c a b c a c b a bT=a b c a cT=a b c a c KMP算法的推导过程：（见教材算法的推导过程：（见教材P81）抓住部分匹配结果的两个特征：抓住部分匹配结果的两个特征：两式联立可得：两式联立可得：T1Tk-1=Tj-(k-1) Tj-1注意：注意：j 为当前已知的失配位置，我们的目标是计算

25、新起点为当前已知的失配位置，我们的目标是计算新起点 k，仅剩一个未知数仅剩一个未知数k，理论上已可解，且，理论上已可解，且k仅与模式串仅与模式串T有关！有关！ 则则S S前前i-1i-1i-(k-1)i-(k-1)位位T T的的j-1j-1j-(k-1)j-(k-1)位位 即即(4-3(4-3式含义式含义S=a b a b c a b c a c b a bT=a b c a cT=a b c a ci ik k则则T T的的k-1k-11 1位位S S前前i-1i-1i-(k-1)i-(k-1)位位 即即(4-2(4-2式含义式含义刚才肯定是在刚才肯定是在S的的i处和处和T的第的第j字符字符

26、 处失配处失配设目前应与设目前应与T的第的第k字符开始比较字符开始比较 KMP算法的推导过程算法的推导过程(续）：续）：根据模式串根据模式串T的规律：的规律： T1Tk-1=Tj-(k-1) Tj-1和已知的当前失配位置和已知的当前失配位置j ，可以归纳出计算新起点，可以归纳出计算新起点 k的表达式。的表达式。令令k = next j ，那么，那么next j 0 当当j1时时max k |1kj 且且T1Tk-1=Tj-(k-1) Tj-1 1 其他情况其他情况讨论：讨论： next j 有何意义？有何意义？ 一旦失配，应从模式串一旦失配，应从模式串T中第中第next j 个字符开始与个字符

27、开始与S的失配的失配点点i 重新匹配重新匹配! next j 怎么求？怎么求？ 后面会举例参见教材后面会举例参见教材P81）第一步，先把模式第一步，先把模式T所有可能的失配点所有可能的失配点j所对应的所对应的nextj计算出来；计算出来；第二步：执行定位函数第二步：执行定位函数index_kmp （与（与BF算法模块非常相似）算法模块非常相似） KMP KMP算法的实现算法的实现即即Index( )Index( )操作的实现操作的实现 （见教材（见教材P82P82） Int Index_KMP(SString S, SString T, int pos) i=pos; j=1; while ( i=S0 & jT0) return i-T0; /子串结束，说明匹配成功子串结束，说明匹配成功 else return0;/Index_KMP例：例： 模模 式式 串串 T： a b a a b c a c 可能失配位可能失配位 j： 1 2 3 4 5 6 7 8新匹配位新匹配位 nextj :next j 0 当当j1时时max k |1kj 且且T1Tk-1=Tj-(k-1) Tj-1 1 其他情况其他情况0 1 1 2 2 3 1 2讨论：讨论：j=1时时, next j 0；因为属于；因为属于“j=1”;j=2时时, next j 1；因为属于；因为属于“其他情况其他情况