数据结构串课件

1、数据结构串课件 第 4 章 串 陈守孔陈守孔 孟佳娜孟佳娜 陈卓陈卓 数据结构串课件 本章目录 w4.1串类型的定义 w4.2串的表示和实现 n4.2.1 串的顺序存储结构 n4.2.2 串的链式存储结构 w4.3 串的模式匹配 n4.3.1 朴素的模式匹配算法 n4.3.2 KMP算法 w4.4 串的应用举例 w4.5 算法设计举例 数据结构串课件 知识点和难点重点 w 知识点知识点 n基本概念基本概念 n串操作串操作 n模式匹配模式匹配 w 难点重点难点重点 n根据给定操作，编写其它操作的算法根据给定操作，编写其它操作的算法 (如，根据前如，根据前5个基本操作，编写个基本操作，编写inde

2、x,replace操作操作 n KMP算法算法 l模式串的模式串的next和和nextval函数值函数值 l手工模拟手工模拟KMP算法的执行过程算法的执行过程 n串的其它算法。串的其它算法。 数据结构串课件 定义和概念 w 串（串（StringString）: :由零个或多个字符组成的有限序列。由零个或多个字符组成的有限序列。 记为：记为：s=a1a2an（n0） w 概念：概念： ns为串名为串名 na1a2an为串值为串值 nn为串的长度为串的长度 nai，字符，字符 nn=0，空串（，空串（Null String），记为：），记为： n若若ai 都是都是 ，则称为空格串，则称为空格串(b

3、lank string) n子串：串中子串：串中任意连续任意连续个字符组成的子序列被称为该个字符组成的子序列被称为该 串的子串串的子串 ，包含子串的串又被称为该子串的，包含子串的串又被称为该子串的主串主串 n子串在主串中的位置：子串在主串中的位置： n串的相等：两个串的串值相等（两个串的长度相等，串的相等：两个串的串值相等（两个串的长度相等， 并且各个对应的字符也都相同并且各个对应的字符也都相同 ） 数据结构串课件 串的操作 n串赋值：串赋值：StringAssign(S,T)StringAssign(S,T) n求串长：求串长：StringLenth(S)StringLenth(S) n串判

4、等：串判等：StringEqual(S,T)StringEqual(S,T) n串联接：串联接：StringConcat(S,T)StringConcat(S,T) n求子串：求子串：SubString(S,start,length)SubString(S,start,length) n子串定位：子串定位：Index(S,T)Index(S,T) n置换：置换：Replace(S,T,V)Replace(S,T,V) n插入子串：插入子串：StringInsert(S,start,T)StringInsert(S,start,T) n删除子串：删除子串：StringDeleteStringDe

5、lete( (S,start,lengthS,start,length) ) （其中，前（其中，前5 5个操作为基本操作。）个操作为基本操作。） 数据结构串课件 串运算举例 串运算的例子： 长度分别为长度分别为1818、7 7、3 3、3 3；且；且b b、c c、d d都是都是a a的子串；的子串；b b在在a a中的中的 位置是位置是1 1，c c在在a a中的位置是中的位置是1212；c c和和d d两串相等两串相等 例：例： a= Welcome to Beijing b= Welcome a= Welcome to Beijing b= Welcome c= Bei d= Bei c

6、= Bei d= Bei 数据结构串课件 子串定位（index）的实现 int Index(String S, String T) 若主串若主串S第第i个字符之后存在与个字符之后存在与T相等的子串，则返回相等的子串，则返回T串在串在S中中 的位置，否则返回的位置，否则返回0 n=StringLength(S); m=StringLength(T); i=1; while(istr) free(S-str); 若若s已经存在，将它占据的空间释放掉已经存在，将它占据的空间释放掉 len= T-length; T串的长度串的长度 S-length=len; 赋予字符串长度赋予字符串长度 if(!le

7、n) 空串空串 S-str=(char*)malloc(sizeof(char); S-str0=0; else 非空串非空串 S-str=(char*)malloc(len+1)*sizeof(char);分配空间分配空间 if(!S-str) return ERROR; for(i=0;istri=T-stri; if return OK; StringAssign 数据结构串课件 基本操作:串联接 int StringConcat(STRING *S,*T) 将串将串T联接到串联接到串S后后 STRING temp; StringAssign(temp,S); 将将S原来的内容保留在原来

8、的内容保留在temp中中 S-length=S-length+T-length; 计算计算S和和T的长度之和为的长度之和为S的新长度的新长度 free(S-str); 释放释放S原来占据的空间原来占据的空间 S-str=(char*)malloc(S-length+1)*sizeof(char); 重新为重新为S分配空间分配空间 if(!S-str) return ERROR; else 连接两个串的内容连接两个串的内容 for(i=0;istri=temp.stri; for(j=0;jlength;j+,i+) 将将T的值赋在的值赋在S现有值之后现有值之后 S-stri=T-strj; f

9、ree(temp.str); 释放为临时串释放为临时串temp分配的空间分配的空间 return OK; if StringConcat 数据结构串课件 int Index(STRING *S,*T) 返回子串返回子串T在主串在主串S中的位置，若中的位置，若T非非S的子串则返回的子串则返回0 i=0; j=0; 设置两个扫描指针设置两个扫描指针 while(ilength j+; else 对应字符不相等时，重新比较对应字符不相等时，重新比较 i=i-j+1; j=0; if(j=T-length) return i-T-length+1;返回子串在主串中的位置返回子串在主串中的位置 else

10、 return 0; 子串不在主串中子串不在主串中 Index 基本操作的算法:子串定位 数据结构串课件 定长顺序表示中的C表示方法 w 在C中，字符串的概念是：以0为结尾 的字符数组。 w 初始化： nString s; nS0 = 0; 数据结构串课件 串的链式存储结构 w 串串作为一种特殊的线性表（数据元素为字 符），使用顺序表示时，做插入和删除运 算，运算量很大，不方便。 w 链式存储结构：链式存储结构： s p r i n g S S s p r i n g # # # # 数据结构串课件 串的块链存储结构 w 直接使用线性链表来存储字符串：效率太低直接使用线性链表来存储字符串：效率

11、太低 实际分配的存储单元 串值所占的存储单元 存储密度 = = w 块链式结构的定义块链式结构的定义 #define CHUNKSIZE 80 可由用户定义的块大小可由用户定义的块大小 typedef struct Chunk 结点结构结点结构 char chCHUNKSIZE; struct Chunk *next; Chunk; typedef struct 串的链表结构串的链表结构 Chunk *head, *tail; 串的头和尾指针串的头和尾指针 int curlen; 串的当前长度串的当前长度 LString; 数据结构串课件 块链运算：插入 H esi s de nuta# #.

12、t? He is a student. He is a bright student. 数据结构串课件 块链运算：插入 H esi b g d e ira .#tn? httus 数据结构串课件 串的模式匹配 w 子串定位算法子串定位算法Index n基本思想：基本思想：先以主串先以主串S S中第一个字符为中第一个字符为S S子串子串 的头一个字符，模式串的头一个字符，模式串T T的长度作为的长度作为S S子串的子串的 长度，得到一个子串去与模式串长度，得到一个子串去与模式串T T中的字符逐中的字符逐 个比较，若子串与模式串相同，即返回个比较，若子串与模式串相同，即返回S S中子中子 串的第一

13、个字符位置作为模式串在主串串的第一个字符位置作为模式串在主串S S中的中的 位置；否则，取位置；否则，取S S中第二个字符为子串头，将中第二个字符为子串头，将 其往后的字符再依次和模式串其往后的字符再依次和模式串T T比较判断是否比较判断是否 相等，以此类推直到找到子串位置或没有一相等，以此类推直到找到子串位置或没有一 个子串与模式串相同为止个子串与模式串相同为止 ，前者模式匹配成，前者模式匹配成 功，后者模式匹配失败。功，后者模式匹配失败。 数据结构串课件 朴素的模式匹配 w 主串主串S=S=ababcabcacbabababcabcacbab，模式串，模式串T= abcacT= abcac

14、 i=2 第一趟匹配：第一趟匹配： a b a b c a b c a c b a b a b c j=2 i=1 第二趟匹配：第二趟匹配： a b a b c a b c a c b a b a j=0 i=6 第三趟匹配：第三趟匹配： a b a b c a b c a c b a b a b c a c j=4 i=3 第四趟匹配：第四趟匹配： a b a b c a b c a c b a b a j=0 i=4 第五趟匹配：第五趟匹配： a b a b c a b c a c b a b a j=0 i=10 第六趟匹配：第六趟匹配： a b a b c a b c a c b a

15、b a b c a c（成功）（成功） j=5 数据结构串课件 上面的模式匹配只需三趟 w 主串主串S=ababcabcacbab，模式串，模式串T= abcac i=3 第一趟匹配：第一趟匹配： a b a b c a b c a c b a b a b c j=3 (next3=1) i=3 第二趟匹配：第二趟匹配： a b a b c a b c a c b a b a b c a c j=5 (next5=2 i=7 第三趟匹配：第三趟匹配： a b a b c a b c a c b a b (a) b c a c j=5 i=7 怎么得来的呢？这就是怎么得来的呢？这就是KMP算法。

16、算法。 数据结构串课件 KMP算法 wKMPKMPKnuth, Morris, PrattKnuth, Morris, Pratt三人发明三人发明 w特点特点 n无需回溯 n在O（nm）的时间量级上完成串的模 式匹配操作 数据结构串课件 KMP算法 假设主串假设主串S为为s1s2s3sn，模式串，模式串T为为p1p2tm，若，若si与与tj发生失配，则有：发生失配，则有： si-j+1si-1=p1pj-1 (1) 由（由（1），若），若kj,则有：则有： si-k+1si-1= pj-k+1pj-1 (3) 若主串不回溯，设此时将模式串中第若主串不回溯，设此时将模式串中第k（kj）个字符继续

17、比较，则有：）个字符继续比较，则有： si-k+1si-1= p1pk-1 (2) 由（由（2）和（）和（3），则下式成立：），则下式成立： p1pk-1 =pj-k+1pj-1 （4） 该等式只与模式串有关，与主串无关。该等式只与模式串有关，与主串无关。 数据结构串课件 若模式串若模式串P为为 abaabc，由定义可得，由定义可得next函数值函数值 j1 2 3 4 5 6 模式串模式串a b a a b c nextj0 1 1 2 2 3 KMP算法 = = = 其它情况 当此集合不空时且 时当 1 . jk1 |kmax 10 1111jkjk pppp j jnext next函数

18、的定义函数的定义 数据结构串课件 i=2 第一趟匹配：第一趟匹配： 主串主串 a c a b a a b a a b c a c a a b c 模式串模式串 a b j=2 next2=1 i=2 第二趟匹配：第二趟匹配： 主串主串 a c a b a a b a a b c a c a a b c 模式串模式串 a j=1 next1=0 i=3 i=8 第三趟匹配：第三趟匹配： 主串主串 a c a b a a b a a b c a c a a b c 模式串模式串 a b a a b c j=1 j=6 next6=3 i=8 i=12 第四趟匹配：第四趟匹配： 主串主串 a c a

19、 b a a b a a b c a c a a b c 模式串模式串 (a b) a a b c j=3 j=7 KMP算法手工模拟 主串主串 S=a c a b a a b a a b c a c a a b c 模式串模式串 P=a b a a b c 数据结构串课件 0 1 2 3 1 1 2 3 1 0 1 1 1 2 3 4 5 1 j123456 789 模式串aaabca aba j1 2 3 4 5 6 7 8 9 模式串 a b c a b c a c b 求模式串的next函数值举例 数据结构串课件 如何求next函数 已知next1 = 0，假设nextj = k且 t

20、j = tk，则有 nextj+1 = k+1= nextj+1； 若nextj = k且 tj tk，则需往前回溯，检查 tj = t?。 这实际上也是一个匹配的过程，不同在于主串和模 式串是同一个串。 若k=nextk且tj = tk，则nextj=nextk+1，若tj tk 则继续往前回溯，直到存在k使tj = tk或k=0 0 1 1 2 2 3 4 3 j1234 5 678 模式串babb abab 数据结构串课件 利用KMP算法的子串定位函数 int IndexKMP(STRING *S,*T) 利用模式串利用模式串T的的next函数求函数求T在主串在主串S中的位置的中的位置的

21、KMP算法。其中算法。其中T非空非空 i=0; j=1; while(ilength +j； 继续比较后继字符继续比较后继字符 else j=nextj; 模式串向右移动模式串向右移动 while if(jT-length) return i-T-length+1; 匹配成功匹配成功 else return 0; IndexKMP 数据结构串课件 对对S=aabcbabcaabcaabaS=aabcbabcaabcaaba，T=bcaT=bca，画出以，画出以T T为模为模 式串，式串，S S为目标串的匹配过程。为目标串的匹配过程。 a a b c b a b c a a b c a a b

22、a b b b c a b c b b c a bca的next值数为: 011 利用KMP算法举例 数据结构串课件 如何求next函数 已知已知next1=0，假设，假设nextj=k且且 pj=pk，则有，则有 nextj+1=k+1=nextj+1；若；若nextj=k且且 pj pk，则需往，则需往 前回溯，检查前回溯，检查 pj=p?。这实际上也是一个匹配的过程，不同在于主。这实际上也是一个匹配的过程，不同在于主 串和模式串是同一个串。若串和模式串是同一个串。若k=nextk且且pj=pk，则，则 nextj=nextk+1，若，若pj pk 则继续往前回溯，直到存在则继续往前回溯，

23、直到存在k 使使pj=pk或或k=0。next函数算法描述如下：函数算法描述如下： void GetNext(STRING *P,int next) 求模式串求模式串P的的next函数值并存入数组函数值并存入数组next。 i=1; next1=0; j=0; while(ilength) if(j=0|P-stri-1=P-strj-1) +i; +j; nexti=j; else j=nextj; while GetNext 数据结构串课件 next函数的改进 问题的提出问题的提出 模式串模式串P=aaaab，其，其next函数值为函数值为01234，若主串，若主串 为为aaabaaaba

24、aaab，当，当i4，j4时时sipj，由，由nextj的指示还需的指示还需 进行进行i4、j3，i4、j2，i4、j1等三次比较。实际上，由等三次比较。实际上，由 于模式中第于模式中第1、2、3个字符和第个字符和第4个字符都相等，因此这种比较是不个字符都相等，因此这种比较是不 必要的，可以将模式串一次向右滑动必要的，可以将模式串一次向右滑动4个字符直接进行个字符直接进行i5、j1的的 比较。也就是说，若比较。也就是说，若nextj=k，当，当si与与pj失配且失配且pjpk，则下一步不，则下一步不 需将主串中的需将主串中的si与与pk比较，而是直接与比较，而是直接与nextk进行比较。由以上

25、思进行比较。由以上思 想对想对next函数进行改进，得到函数进行改进，得到nextval函数如下函数如下 j1 2 3 4 5 模式串模式串a a a a b nextj0 1 2 3 4 nextvalj0 0 0 0 4 数据结构串课件 nextval函数 void GetNextVal(STRING *P,int nextval) 求模式串求模式串P的的next函数修正值存入数组函数修正值存入数组nextval。 i=1; nextval1=0; j=0; while(ilength) if(j=0|P-stri-1=P-strj-1) +i; +j; if(P-stri-1!=P-st

26、rj-1) nextvali=j; else nextvali=nextvalj; else j=nextvalj; while GetNextVal 数据结构串课件 利用nextval求模式匹配举例 （1）p的的nextval函数值为函数值为0110132。 （2）利用利用KMP(改进的改进的nextval)算法，每趟匹配过程如下：算法，每趟匹配过程如下： 第一趟匹配：第一趟匹配： abcaabbabcabaacbacba abcab(i=5,j=5) 第二趟匹配：第二趟匹配： abcaabbabcabaacbacba abc(i=7,j=3) 第三趟匹配：第三趟匹配： abcaabbabcabaacbacba a(i=7,j=1) 第四趟匹