数据结构C语言版第四章严蔚敏学习教案.pptx

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

1、会计学1数据结构数据结构(sh j ji u)C语言版第四章课语言版第四章课件严蔚敏件严蔚敏第一页，共36页。4.1 串类型串类型(lixng)的定义的定义 1.基本概念基本概念串串(字字符符串串)String：是是零零个个或或多多个个字字符符组组成成的的有有限限序序列列。一一般般(ybn)记为：记为：S=a1a2.an(n0)栈、队列：操作受限的线性表。栈、队列：操作受限的线性表。串：取值范围受限的线性表，数据对象约束为字符集。串：取值范围受限的线性表，数据对象约束为字符集。其其中中S是是串串的的名名字字,用用单单引引号号括括起起来来的的字字符符序序列列是是串串的的值值，ai(1in)可以是

2、字母、数字或其它字符。可以是字母、数字或其它字符。串的长度：串中字符的个数串的长度：串中字符的个数n。空串空串(Null String)：n=0时的串称为空串，用符号时的串称为空串，用符号“”表示表示 。第1页/共36页第二页，共36页。l子子串串：串串中中任任意意个个连连续续的的字字符符组组成成的的子子序序列列称称为为该该串串的的子子 串。串。“”为任意串的子串。为任意串的子串。l主串：包含主串：包含(bohn)子串的串相应地称为主串。子串的串相应地称为主串。第2页/共36页第三页，共36页。l l位置：字符在串中的序号称为该字符在串中的位位置：字符在串中的序号称为该字符在串中的位位置：字符

3、在串中的序号称为该字符在串中的位位置：字符在串中的序号称为该字符在串中的位置。子串在主串中的位置则以子串的第一个字符置。子串在主串中的位置则以子串的第一个字符置。子串在主串中的位置则以子串的第一个字符置。子串在主串中的位置则以子串的第一个字符在主串中的位置来表示。在主串中的位置来表示。在主串中的位置来表示。在主串中的位置来表示。l l A=China Beijing,B=Beijing,C=China,A=China Beijing,B=Beijing,C=China,则则则则它们的长度分别它们的长度分别它们的长度分别它们的长度分别(fnbi)(fnbi)为为为为1313、7 7和和和和5 5

4、。B B和和和和C C是是是是A A的的的的子串子串子串子串,B,B在在在在A A中的位置是中的位置是中的位置是中的位置是7,C7,C在在在在A A中的位置是中的位置是中的位置是中的位置是1 1。l l串相等：当且仅当两个串的值相等时串相等：当且仅当两个串的值相等时串相等：当且仅当两个串的值相等时串相等：当且仅当两个串的值相等时,称这两个串称这两个串称这两个串称这两个串是相等的，即只有当两个串的长度相等是相等的，即只有当两个串的长度相等是相等的，即只有当两个串的长度相等是相等的，即只有当两个串的长度相等,并且每个并且每个并且每个并且每个对应位置的字符都相等时才相等。对应位置的字符都相等时才相等

5、。对应位置的字符都相等时才相等。对应位置的字符都相等时才相等。l l空格串：由一个或多个空格组成的串。与空串不空格串：由一个或多个空格组成的串。与空串不空格串：由一个或多个空格组成的串。与空串不空格串：由一个或多个空格组成的串。与空串不同。同。同。同。第3页/共36页第四页，共36页。串的基本操作和线性表区别串的基本操作和线性表区别(qbi)很大。很大。线性表线性表:大多以大多以“单个元素单个元素(yun s)”为操作对象为操作对象串串:通常通常(tngchng)以以“串的整体串的整体”为操作对象为操作对象例，例，查找某个元素；插入某个元素；删除某个元素查找某个元素；插入某个元素；删除某个元素

6、例，例，查找某个子串；截取某个子串；查找某个子串；截取某个子串；在某个位置插入、删除某个子串在某个位置插入、删除某个子串串的逻辑结构和线性表相似，故看作一种线性表。串的逻辑结构和线性表相似，故看作一种线性表。s=a1a2 an (n0)第4页/共36页第五页，共36页。2.串的基本运算串的基本运算:串赋值串赋值StrAssign(&T,chars)初始条件初始条件:chars是字符串常量。是字符串常量。操作结果操作结果:生成一个值等于生成一个值等于chars的串的串T。串比较串比较(bjio)StrCompare(S,T)初始条件初始条件:串串S和和T存在。存在。操作结果操作结果:若若ST,则

7、返回值则返回值0;如如S=T,则返回值则返回值=0;若若ST,则返回值则返回值0。求串长求串长StrLength(S)初始条件初始条件:串串S存在。存在。操作结果操作结果:返回串返回串S的长度的长度,即串即串S中的元素个数。中的元素个数。第5页/共36页第六页，共36页。l 串联串联(chunlin)接接Concat(&T,S1,S2)l 初始条件初始条件:串串S1和和S2存在。存在。l 操作结果操作结果:将将T返回由返回由S1和和S2联接而成的新串。联接而成的新串。l 求子串求子串SubString(&Sub,S,pos,len)l 初始条件初始条件:串串S存在存在,1posStrLengt

8、h(S)且且l 1lenStrLength(S)-pos+1。l 操操作作结结果果:用用Sub返返回回串串S的的第第pos个个字字符符起起长长度度为为len的的l 子串。子串。第6页/共36页第七页，共36页。4.2 串的表示串的表示(biosh)和实和实现现 定长顺序存储表示定长顺序存储表示(biosh)顺序存储顺序存储 堆分配堆分配(fnpi)存储表示存储表示顺序存储顺序存储 块链存储表示块链存储表示链式存储链式存储第7页/共36页第八页，共36页。1.定长顺序存储表示定长顺序存储表示(biosh)（定长顺序串）（定长顺序串）define MAXSTRLEN 255 typedef uns

9、igned char SStringMAXSTRLEN+1;l定长顺序串的存储分配是在编译定长顺序串的存储分配是在编译(biny)时完成的。与前面所讲的线性表的顺序存储结构类似时完成的。与前面所讲的线性表的顺序存储结构类似,用一组地址连续的存储单元存储串的字符序列。用一组地址连续的存储单元存储串的字符序列。l超出予定义长度的串值被舍去，称之为超出予定义长度的串值被舍去，称之为“截断截断”。012255第8页/共36页第九页，共36页。n n串长的表示：串长的表示：n n以下标为以下标为0的数组分量存放串的实际长度；的数组分量存放串的实际长度；n n串值后加入一个不计入串值后加入一个不计入(j

10、r)串长的结串长的结束标记字符，束标记字符，C中中“0”表串值的终结，其表串值的终结，其ASC码值为码值为0。第9页/共36页第十页，共36页。算法算法(sun f)4.2 串联接串联接 strcat(&T，S1，S2)要求要求:顺序联接顺序联接(lin ji)串串 S1 和串和串 S2 得到新串得到新串 T。思想思想(sxing):基于串基于串S1和和S2长度的不同情况，串长度的不同情况，串T可能出现可能出现3种情况种情况:S10+S20MAXSTRLEN，S10+S20MAXSTRLENS10MAXSTRLEN，S10MAXSTRLEN，直接联接，直接联接，T0MAXSTRLEN；截断截断

11、S2，联接，联接，T0MAXSTRLEN；T S1；第10页/共36页第十一页，共36页。1255S101255T0T0=S10+S201255S20S10+S20MAXSTRLEN第11页/共36页第十二页，共36页。1255S10S10+S20MAXSTRLEN，S10MAXSTRLEN1255T0 255-S101255S20 255-S10T0MAXSTRLEN第12页/共36页第十三页，共36页。2.堆分配存储堆分配存储(cn ch)表示（堆串）表示（堆串）在在C语言中，已经有一个称为语言中，已经有一个称为“堆堆”的自由的自由(zyu)存储空间，并可用存储空间，并可用malloc（）

12、和（）和free（）函数完成动态存储管理。（）函数完成动态存储管理。typedef struct char *ch；int length；HString；应用程序用到的内存分配应用程序用到的内存分配(fnpi)：栈分配：栈分配(fnpi)和堆分配和堆分配(fnpi)。堆：用户程序动态申请的地址空间。堆：用户程序动态申请的地址空间。栈：保存函数参数和块内局部变量的内存区。栈：保存函数参数和块内局部变量的内存区。void Fun1()void Fun2()int i;int*p=new int10;char p10;.;delete p;.;第13页/共36页第十四页，共36页。3.串的块链存储串

13、的块链存储(cn ch)表示（链串）表示（链串）define CHUNKSIZE typedef struct Chunk char chCHUNKSIZE;struct Chunk *next;Chunk;typedef struct Chunk *head;Chunk *tail;int curlen;LString;第14页/共36页第十五页，共36页。l存储密度大，一些操作（如插入存储密度大，一些操作（如插入(ch r)，删除）有所不便，删除）有所不便，引起大量字符移动，适合于在串基本保持静态使用方式时采引起大量字符移动，适合于在串基本保持静态使用方式时采用；用；l存储密度小，运算处理

14、方便，但存储空间量大，若处理过程存储密度小，运算处理方便，但存储空间量大，若处理过程中，需大量内外存交换，会影响总效率；中，需大量内外存交换，会影响总效率；l串的字符集的大小，也会影响串值存储方式的选取。串的字符集的大小，也会影响串值存储方式的选取。第15页/共36页第十六页，共36页。l l作业作业(zuy)：l l 4.1l l4.18第16页/共36页第十七页，共36页。1.朴素模式匹配算法朴素模式匹配算法(Brute-Force算法算法)求子串位置的定位函数求子串位置的定位函数Index(S,T,pos).模式匹配：子串的定位操作通常称作串的模式匹配。模式匹配：子串的定位操作通常称作串

15、的模式匹配。目标串：主串目标串：主串S。模式串：子串模式串：子串T。匹配成功：若存在匹配成功：若存在T的每个字符依次和的每个字符依次和S中的一个连续字符序中的一个连续字符序列列(xli)相等，则称匹配成功。返回相等，则称匹配成功。返回T中第一个字符在中第一个字符在S中的中的位置。位置。匹配不成功：返回匹配不成功：返回0。4.3 串的模式匹配算法串的模式匹配算法(sun f)第17页/共36页第十八页，共36页。l lBrute-Force简称为简称为BF算法算法,亦称简亦称简单匹配算法单匹配算法,其基本思路是其基本思路是:l l 从目标串从目标串s=“s1s2sn”的第的第一个字符开始和模式串

16、一个字符开始和模式串t=“t1t2tm”中的第一个字符比较中的第一个字符比较(bjio),若相等若相等,则继续逐个比较则继续逐个比较(bjio)后续字符；否则从目标串后续字符；否则从目标串s的第二个字符开始重新与模式串的第二个字符开始重新与模式串t的第一个字符进行比较的第一个字符进行比较(bjio)。依次类推依次类推,若从目标串若从目标串s的第的第i个字个字符开始符开始,每个字符依次和模式串每个字符依次和模式串t中中的对应字符相等的对应字符相等,则匹配成功则匹配成功,该算该算法返回法返回i；否则；否则,匹配失败匹配失败,函数返函数返回回0。第18页/共36页第十九页，共36页。例如,设目标串s

17、=“cddcdc”,模式串t=“cdc”。s的长度(chngd)为n(n=6),t的长度(chngd)为m(m=3)。用指针i指示目标串s的当前比较字符位置,用指针j指示模式串t的当前比较字符位置。BF模式匹配过程如下所示。i=i j+2;j=1;第19页/共36页第二十页，共36页。l l子串定位子串定位子串定位子串定位(dngwi)int Index(SString S,SString T,(dngwi)int Index(SString S,SString T,int pos)int pos)l l l l i=pos;j=1;i=pos;j=1;l l while(i=S0&j=T0)

18、while(i=S0&jT0)return i-T0;if(jT0)return i-T0;l l else return 0;else return 0;l l 第20页/共36页第二十一页，共36页。l l朴素模式匹配算法的时间复杂度朴素模式匹配算法的时间复杂度朴素模式匹配算法的时间复杂度朴素模式匹配算法的时间复杂度l l 主串长主串长主串长主串长n n；子串长子串长子串长子串长mm。可能。可能。可能。可能(knng)(knng)匹配成功的位置（匹配成功的位置（匹配成功的位置（匹配成功的位置（1 n-m+1)1 n-m+1)。l l最好的情况下，最好的情况下，最好的情况下，最好的情况下，l

19、 l 第第第第i i个位置匹配成功，比较了（个位置匹配成功，比较了（个位置匹配成功，比较了（个位置匹配成功，比较了（i-1+mi-1+m）次，平均比较次数：）次，平均比较次数：）次，平均比较次数：）次，平均比较次数：l l 最好情况下算法的平均时间复杂度最好情况下算法的平均时间复杂度最好情况下算法的平均时间复杂度最好情况下算法的平均时间复杂度O(n+m)O(n+m)。l l最坏的情况下，最坏的情况下，最坏的情况下，最坏的情况下，l l 第第第第i i个位置匹配成功，比较了（个位置匹配成功，比较了（个位置匹配成功，比较了（个位置匹配成功，比较了（i*mi*m）次，平均比较次数：）次，平均比较次数

20、：）次，平均比较次数：）次，平均比较次数：l l 设设设设nmnm，最坏情况下的平均时间复杂度为，最坏情况下的平均时间复杂度为，最坏情况下的平均时间复杂度为，最坏情况下的平均时间复杂度为O(n*m)O(n*m)。第21页/共36页第二十二页，共36页。2.2.模式匹配的改进模式匹配的改进模式匹配的改进模式匹配的改进(g(g ijn)ijn)算法算法算法算法-KMP-KMP算法算法算法算法 KMP KMP算法是、和共同提出的算法是、和共同提出的算法是、和共同提出的算法是、和共同提出的,简称简称简称简称KMPKMP算法。该算法较算法。该算法较算法。该算法较算法。该算法较BFBF算法有较大改进算法有

21、较大改进算法有较大改进算法有较大改进(g(g ijn),ijn),主要是消除了主串指针的回主要是消除了主串指针的回主要是消除了主串指针的回主要是消除了主串指针的回溯溯溯溯,从而使算法效率有了某种程度的提高。从而使算法效率有了某种程度的提高。从而使算法效率有了某种程度的提高。从而使算法效率有了某种程度的提高。因因p1p2,s2=p2,p1p2,s2=p2,必有必有s2p1,s2p1,又因又因p1=p3,s3=p3,p1=p3,s3=p3,所以必有所以必有s3=p1s3=p1。因此。因此,第二次匹第二次匹配可直接配可直接(zhji)(zhji)从从i=4,j=2i=4,j=2开始。开始。第22页/

22、共36页第二十三页，共36页。改进：每趟匹配过程中出现字符比较不等时，不回溯主指针改进：每趟匹配过程中出现字符比较不等时，不回溯主指针i，利用已得到的，利用已得到的“部分匹配部分匹配”结果将模式向右滑动尽可能远结果将模式向右滑动尽可能远的一段距离，继续的一段距离，继续(jx)进行比较。进行比较。第23页/共36页第二十四页，共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 p pj+1j+1

23、 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”（部（部分分(b fen)匹配）匹配）“p1p2pk-1”=“pj-k+1pj-k+2pj-1”(真子串）真子串）第24页/共36页第二十五页，共36页。max max k|1kj,k|1kj,且且“p1pk-1”=“pj-“p1pk-1”=“pj-k+1pj-1”k+1pj-1”当此集合当此集合(jh)(jh)非空时非空时 0 0 当当j=1j=1时时 1 1 其他情况其他情况nextj=为此为

24、此,定义定义nextj函数，表明当模式中第函数，表明当模式中第j个字符与主串中个字符与主串中相应字符相应字符“失配失配”时，在模式中需重新和主串中该字符进时，在模式中需重新和主串中该字符进行行(jnxng)比较的字符的位置。比较的字符的位置。第25页/共36页第二十六页，共36页。int Index_KMP(SString S,SString T,int pos)i=pos,j=1;while(i=S0&jT0)return i-T0;/*匹配成功匹配成功*/else return 0;/*返返回回(fnhu)不不匹匹配配标标志志*/第26页/共36页第二十七页，共36页。l l如何求如何求如

25、何求如何求nextnext函数值函数值函数值函数值l l1.next1=0;1.next1=0;表明主串从下一字符表明主串从下一字符表明主串从下一字符表明主串从下一字符si+1si+1起和模式串重新起和模式串重新起和模式串重新起和模式串重新开始匹配。开始匹配。开始匹配。开始匹配。i=i+1;j=1;i=i+1;j=1;l l2.2.设设设设nextj=knextj=k，则，则，则，则nextj+1=?nextj+1=?l l若若若若pk=pjpk=pj，则有，则有，则有，则有“p1pk-1pk”=“pj-k+1pj-1pj”“p1pk-1pk”=“pj-k+1pj-1pj”，如果在如果在如果在

26、如果在l l j+1 j+1发生不匹配，说明发生不匹配，说明发生不匹配，说明发生不匹配，说明nextj+1=k+1=nextj+1nextj+1=k+1=nextj+1。l l若若若若pkpjpkpj，可把求，可把求，可把求，可把求nextnext值问题看成是一个值问题看成是一个值问题看成是一个值问题看成是一个(y(y )模式模式模式模式匹配问匹配问匹配问匹配问l l 题，整个模式串既是主串，又是子串。题，整个模式串既是主串，又是子串。题，整个模式串既是主串，又是子串。题，整个模式串既是主串，又是子串。第27页/共36页第二十八页，共36页。p p p p1 1 1 1 p p p p2 2

27、2 2p p p pj-k+1j-k+1j-k+1j-k+1ppppj-1j-1j-1j-1 p p p pj j j j p p p pj+1 j+1 j+1 j+1 nextj=knextj=knextj=knextj=k p p p p1 1 1 1 p p p pk-1k-1k-1k-1 p p p pk k k k p p p pk+1 k+1 k+1 k+1 nextk=knextk=knextk=knextk=k p p p p1 1 1 1 p p p pk k k k p p p pk k k k+1 +1 +1 +1 nextknextknextknextk=k=k=k=k

28、”p p p p1 1 1 1 p p p pk k k k p p p pk k k k+1+1+1+1 nextknextknextknextk=k=k=k=k l若若pk=pj，则有，则有“p1pk”=“pj-k+1pj”，nextj+1=k+1=nextk+1=nextnextj+1.l若若pk”=pj，则有，则有“p1pk”=“pj-k”+1pj”，nextj+1=k”+1=nextk+1=nextnextk+1.lnextj+1=1.第28页/共36页第二十九页，共36页。j 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 j 1 2 3 4 5

29、 6 7 8 9 10 11 12 13 14 15 16 17模式模式模式模式(msh)(msh)串串串串 a b c a a b b c a b c a a b a b c a a b b c a b c a a b d a b d a b 0nextj11122311 2345 6712第29页/共36页第三十页，共36页。l lvoid get_next(SString T,int&next)void get_next(SString T,int&next)i=1;next1=0;j=0;i=1;next1=0;j=0;while(iT0)while(iT0)if(j=0|Ti=Tj)

30、if(j=0|Ti=Tj)+i;+j;+i;+j;nexti=j;nexti=j;else else j=nextj;j=nextj;第30页/共36页第三十一页，共36页。lKMPKMP算法的时间复杂度算法的时间复杂度 l 设设主主串串s s的的长长度度为为n,n,模模式式串串t t长长度度为为m,m,在在KMPKMP算算法法中中求求nextnext数数组组的的时时间间复复杂杂度度为为O(m),O(m),在在后后面面的的匹匹配配中中因因主主串串s s的的下下标标(xi(xi bio)bio)不不减减即即不不回回溯溯,比比较较次次数数可可记记为为n,n,所所以以KMPKMP算法总的时间复杂度为

31、算法总的时间复杂度为O(n+m)O(n+m)。lKMPKMP算算法法最最大大的的特特点点就就是是主主串串的的指指针针不不需需要要回回溯溯，整整个个匹匹配配过过程程只只需需从从头头到到尾尾扫扫描描一一遍遍，这这对对于于处处理理需需要要从从外外设输入的庞大数据很有效，可以一边读入一边匹配。设输入的庞大数据很有效，可以一边读入一边匹配。第31页/共36页第三十二页，共36页。l lnext函数函数(hnsh)的改进的改进 j 1 2 3 4 5 模式模式(msh)a a a a bnextj 0 1 2 3 4nextvalj 0 0 0 0 4 a a a b a a a a b a a a a

32、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进行进行(jnxng)比较，而直接比较，而直接和和pnextk进行进行(jnxng)比较。比较。第32页/共36页第三十三页，共36页。j 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 j 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17模式模式模式模式(msh)(msh)串串串串 a b c a a b b c a b c a a b

33、d a b 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 nextj 0 1 1 1 2 2 3 1 1 2 3 4 5 6 7 1 2 0nextvalj110 2131 011021701第33页/共36页第三十四页，共36页。l lvoid get_nextval(SString T,int&nextval)void get_nextval(SString T,int&nextval)i=1;nextval1=0;j=0;i=1;nextval1=0;j=0;while(iT0)whil

34、e(iT0)if(j=0|Ti=Tj)if(j=0|Ti=Tj)+i;+j;+i;+j;if(Ti!=Tj)nextvali=j;if(Ti!=Tj)nextvali=j;else nextvali=nextvalj;else nextvali=nextvalj;else j=nextvalj;else j=nextvalj;nexti=j;第34页/共36页第三十五页，共36页。本章小结本章小结本章基本学习要点本章基本学习要点(yodin)(yodin)如下如下:(1)(1)理解串和一般线性表之间的差异。理解串和一般线性表之间的差异。(2)(2)重点掌握在顺序串上和链串上实现串的基本运算重点掌握在顺序串上和链串上实现串的基本运算 算法。算法。(3)(3)掌握串的模式匹配算法。掌握串的模式匹配算法。(4)(4)灵活运用串这种数据结构解决一些综合应用问灵活运用串这种数据结构解决一些综合应用问 题。题。第35页/共36页第三十六页，共36页。