数据结构C语言版第四章课件严蔚敏.pptx

《数据结构C语言版第四章课件严蔚敏.pptx》由会员分享，可在线阅读，更多相关《数据结构C语言版第四章课件严蔚敏.pptx（36页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、4.1 串类型的定义 1.基本概念基本概念l串串(字字符符串串)String：是是零零个个或或多多个个字字符符组组成成的的有有限限序序列列。一般记为：一般记为：S=a1a2.an(n0)栈、队列：操作受限的线性表。栈、队列：操作受限的线性表。串：取值范围受限的线性表，数据对象约束为字符集。串：取值范围受限的线性表，数据对象约束为字符集。其其中中S是是串串的的名名字字,用用单单引引号号括括起起来来的的字字符符序序列列是是串串的的值值，ai(1in)可以是字母、数字或其它字符。可以是字母、数字或其它字符。l串的长度：串中字符的个数串的长度：串中字符的个数n。l空空串串(Null String)：n

2、=0时时的的串串称称为为空空串串，用用符符号号“”表示表示 。第1页/共36页l子串：串中任意个连续的字符组成的子序列称为该串的子 串。“”为任意串的子串。l主串：包含子串的串相应地称为主串。第2页/共36页l位置：字符在串中的序号称为该字符在串中的位置。子串在主串中的位置则以子串的第一个字符在主串中的位置来表示。A=China Beijing,B=Beijing,C=China,则它们的长度分别为13、7和5。B和C是A的子串,B在A中的位置是7,C在A中的位置是1。l串相等：当且仅当两个串的值相等时,称这两个串是相等的，即只有当两个串的长度相等,并且每个对应位置的字符都相等时才相等。l空格

3、串：由一个或多个空格组成的串。与空串不同。第3页/共36页串的基本操作和线性表区别很大。线性表:大多以“单个元素”为操作对象串:通常以“串的整体”为操作对象例，查找某个元素；插入某个元素；删除某个元素例，查找某个子串；截取某个子串；在某个位置插入、删除某个子串串的逻辑结构和线性表相似，故看作一种线性表。s=a1a2 an (n0)第4页/共36页2.串的基本运算:l 串赋值StrAssign(&T,chars)初始条件:chars是字符串常量。操作结果:生成一个值等于chars的串T。l 串比较StrCompare(S,T)初始条件:串S和T存在。操作结果:若ST,则返回值0;如S=T,则返回

4、值=0;若ST,则返回值0。l 求串长StrLength(S)初始条件:串S存在。操作结果:返回串S的长度,即串S中的元素个数。第5页/共36页l 串联接Concat(&T,S1,S2)初始条件:串S1和S2存在。操作结果:将T返回由S1和S2联接而成的新串。l 求子串SubString(&Sub,S,pos,len)初始条件:串S存在,1posStrLength(S)且 1lenStrLength(S)-pos+1。操作结果:用Sub返回串S的第pos个字符起长度为len的 子串。第6页/共36页4.2 串的表示和实现 定长顺序存储表示顺序存储 堆分配存储表示顺序存储 块链存储表示链式存储第

5、7页/共36页1.定长顺序存储表示（定长顺序串）define MAXSTRLEN 255 typedef unsigned char SStringMAXSTRLEN+1;l定长顺序串的存储分配是在编译时完成的。与前面所讲的线性表的顺序存储结构类似,用一组地址连续的存储单元存储串的字符序列。l超出予定义长度的串值被舍去，称之为“截断”。012255第8页/共36页串长的表示：以下标为0的数组分量存放串的实际长度；串值后加入一个不计入串长的结束标记字符，C中“0”表串值的终结，其ASC码值为0。第9页/共36页算法4.2 串联接 strcat(&T，S1，S2)要求:顺序联接串 S1 和串 S2

6、 得到新串 T。思想:基于串S1和S2长度的不同情况，串T可能出现3种情况:S10+S20MAXSTRLEN，S10+S20MAXSTRLENS10MAXSTRLEN，S10MAXSTRLEN，直接联接，T0MAXSTRLEN；截断S2，联接，T0MAXSTRLEN；T S1；第10页/共36页1255S101255T0T0=S10+S201255S20S10+S20MAXSTRLEN第11页/共36页1255S10S10+S20MAXSTRLEN，S10MAXSTRLEN1255T0 255-S101255S20 255-S10T0MAXSTRLEN第12页/共36页2.堆分配存储表示（堆串

7、）在C语言中，已经有一个称为“堆”的自由存储空间，并可用malloc（）和free（）函数完成动态存储管理。typedef struct char *ch；int length；HString；应用程序用到的内存分配：栈分配和堆分配。堆：用户程序动态申请的地址空间。栈：保存函数参数和块内局部变量的内存区。void Fun1()void Fun2()int i;int*p=new int10;char p10;.;delete p;.;第13页/共36页3.串的块链存储表示（链串）define CHUNKSIZE typedef struct Chunk char chCHUNKSIZE;str

8、uct Chunk *next;Chunk;typedef struct Chunk *head;Chunk *tail;int curlen;LString;第14页/共36页l存储密度大，一些操作（如插入，删除）有所不便，引起大量字符移动，适合于在串基本保持静态使用方式时采用；l存储密度小，运算处理方便，但存储空间量大，若处理过程中，需大量内外存交换，会影响总效率；l串的字符集的大小，也会影响串值存储方式的选取。第15页/共36页l作业：4.14.18第16页/共36页1.朴素模式匹配算法(Brute-Force算法)求子串位置的定位函数Index(S,T,pos).l模式匹配：子串的定位

9、操作通常称作串的模式匹配。l目标串：主串S。l模式串：子串T。l匹配成功：若存在T的每个字符依次和S中的一个连续字符序列相等，则称匹配成功。返回T中第一个字符在S中的位置。l匹配不成功：返回0。4.3 串的模式匹配算法第17页/共36页lBrute-Force简称为BF算法,亦称简单匹配算法,其基本思路是:从目标串s=“s1s2sn”的第一个字符开始和模式串t=“t1t2tm”中的第一个字符比较,若相等,则继续逐个比较后续字符；否则从目标串s的第二个字符开始重新与模式串t的第一个字符进行比较。依次类推,若从目标串s的第i个字符开始,每个字符依次和模式串t中的对应字符相等,则匹配成功,该算法返回

10、i；否则,匹配失败,函数返回0。第18页/共36页 例如例如,设目标串设目标串s=“cddcdc”,模式串模式串t=“cdc”。s的长度为的长度为n(n=6),t的长度为的长度为m(m=3)。用指针。用指针i指示目标串指示目标串s的当前比较字符位置的当前比较字符位置,用指针用指针j指示模式串指示模式串t的当前的当前比较字符位置。比较字符位置。BF模式匹配过程如下所示。模式匹配过程如下所示。i=i j+2;j=1;第19页/共36页l子串定位int Index(SString S,SString T,int pos)i=pos;j=1;while(i=S0&jT0)return i-T0;els

11、e return 0;第20页/共36页l朴素模式匹配算法的时间复杂度 主串长n；子串长m。可能匹配成功的位置（1 n-m+1)。最好的情况下，第i个位置匹配成功，比较了（i-1+m）次，平均比较次数：最好情况下算法的平均时间复杂度O(n+m)。最坏的情况下，第i个位置匹配成功，比较了（i*m）次，平均比较次数：设nm，最坏情况下的平均时间复杂度为O(n*m)。第21页/共36页2.模式匹配的改进算法-KMP算法 KMP算法是、和共同提出的,简称KMP算法。该算法较BF算法有较大改进,主要是消除了主串指针的回溯,从而使算法效率有了某种程度的提高。因p p1 1pp2 2,s,s2 2=p=p2

12、 2,必有s s2 2pp1 1,又因p p1 1=p=p3 3,s,s3 3=p=p3 3,所以必有s s3 3=p=p1 1。因此,第二次匹配可直接从i=4,i=4,j=2j=2开始。第22页/共36页改进：每趟匹配过程中出现字符比较不等时，不回溯主指针i，利用已得到的“部分匹配”结果将模式向右滑动尽可能远的一段距离，继续进行比较。第23页/共36页s s1 1 s s2 2 s s3 3ssi-j+1i-j+1 s si-j+2i-j+2ssi-2i-2 s si-1i-1 s si i s si+1i+1 p p1 1 p p2 2 p pj-2j-2 p pj-1j-1 p pj j

13、 p pj+1j+1 p p1 1 p pk-1k-1 p pk k p pk+1k+1“p1p2pk-1”=“si-k+1si-k+2si-1”“pj-k+1pj-k+2pj-1”=“si-k+1si-k+2si-1”（部分匹配）“p1p2pk-1”=“pj-k+1pj-k+2pj-1”(真子串）第24页/共36页 max k|1kj,且“p1pk-1”=“pj-k+1pj-1”当此集合非空时 0 0 当j=1j=1时 1 1 其他情况nextj=为此,定义nextj函数，表明当模式中第j个字符与主串中相应字符“失配”时，在模式中需重新和主串中该字符进行比较的字符的位置。第25页/共36页i

14、nt Index_KMP(SString S,SString T,int pos)i=pos,j=1;while(i=S0&jT0)return i-T0;/*匹配成功匹配成功*/else return 0;/*返回不匹配标志返回不匹配标志*/第26页/共36页l如何求next函数值1.next1=0;表明主串从下一字符si+1起和模式串重新开始匹配。i=i+1;j=1;2.设nextj=k，则nextj+1=?若pk=pj，则有“p1pk-1pk”=“pj-k+1pj-1pj”，如果在 j+1发生不匹配，说明nextj+1=k+1=nextj+1。若pkpj，可把求next值问题看成是一个模

15、式匹配问 题，整个模式串既是主串，又是子串。第27页/共36页 p p1 1 p p2 2p pj-k+1j-k+1ppj-1j-1 p pj j p pj+1 j+1 nextj=knextj=k p p1 1 p pk-1k-1 p pk k p pk+1 k+1 nextk=knextk=k p p1 1 p pk k p pk k+1 +1 nextknextk=k=k”p p1 1 p pk k p pk k+1+1 nextknextk=k=k l若pk=pj，则有“p1pk”=“pj-k+1pj”，nextj+1=k+1=nextk+1=nextnextj+1.l若pk”=pj，

16、则有“p1pk”=“pj-k”+1pj”，nextj+1=k”+1=nextk+1=nextnextk+1.lnextj+1=1.第28页/共36页 j 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17模式串 a b c a a b b c a b c a a b d a b 0nextj1 1 1 2 2 3 1 1 2 3 4 5 6 7 1 2第29页/共36页lvoid get_next(SString T,int&next)i=1;next1=0;j=0;while(iT0)if(j=0|Ti=Tj)+i;+j;nexti=j;else j=next

17、j;第30页/共36页lKMPKMP算法的时间复杂度 设主串s s的长度为n,n,模式串t t长度为m,m,在KMPKMP算法中求nextnext数组的时间复杂度为O(m),O(m),在后面的匹配中因主串s s的下标不减即不回溯,比较次数可记为n,n,所以KMPKMP算法总的时间复杂度为O(n+m)O(n+m)。KMP算法最大的特点就是主串的指针不需要回溯，整个匹配过程只需从头到尾扫描一遍，这对于处理需要从外设输入的庞大数据很有效，可以一边读入一边匹配。第31页/共36页lnext函数的改进 j 1 2 3 4 5 模式 a a a a bnextj 0 1 2 3 4nextvalj 0 0

18、 0 0 4 a a a b a a a a b a a a a a a a a a a a a a a b i=5;j=1i=4j=4j=3j=1j=2nextj=k，而pj=pk，则 主串中si和pj不等时，不需再和pk进行比较，而直接和pnextk进行比较。第32页/共36页 j 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17模式串 a b c a a b b c a b c a a b d a b nextj 0 1 1 1 2 2 3 1 1 2 3 4 5 6 7 1 2 0nextvalj1 1 0 2 1 3 1 0 1 10 2 1 7 0

19、1第33页/共36页lvoid get_nextval(SString T,int&nextval)i=1;nextval1=0;j=0;while(iT0)if(j=0|Ti=Tj)+i;+j;if(Ti!=Tj)nextvali=j;else nextvali=nextvalj;else j=nextvalj;nexti=j;第34页/共36页本章小结本章基本学习要点如下:(1)(1)理解串和一般线性表之间的差异。(2)(2)重点掌握在顺序串上和链串上实现串的基本运算 算法。(3)(3)掌握串的模式匹配算法。(4)(4)灵活运用串这种数据结构解决一些综合应用问 题。第35页/共36页感谢您的观看！第36页/共36页