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

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

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

3、作和线性表区别(qbi)很大。很大。线性表线性表: 大多以大多以“单个元素单个元素(yun s)”为操作对象为操作对象串串: 通常通常(tngchng)以以“串的整体串的整体”为操作对象为操作对象例，例，查找某个元素；插入某个元素；删除某个元素查找某个元素；插入某个元素；删除某个元素例，例，查找某个子串；截取某个子串；查找某个子串；截取某个子串； 在某个位置插入、删除某个子串在某个位置插入、删除某个子串串的逻辑结构和线性表相似，故看作一种线性表。串的逻辑结构和线性表相似，故看作一种线性表。s = a1a2 an ( n0)第4页/共36页第五页，共36页。2. 串的基本运算串的基本运算: 串赋

4、值串赋值StrAssign(&T, chars) 初始条件初始条件: chars是字符串常量。是字符串常量。 操作结果操作结果: 生成一个值等于生成一个值等于chars的串的串T。 串比较串比较(bjio)StrCompare(S, T) 初始条件初始条件: 串串S和和T存在。存在。 操作结果操作结果: 若若ST, 则返回值则返回值0;如如S=T, 则返回值则返回值=0; 若若ST, 则返回值则返回值0。 求串长求串长StrLength(S) 初始条件初始条件: 串串S存在。存在。 操作结果操作结果: 返回串返回串S的长度的长度, 即串即串S中的元素个数。中的元素个数。第5页/共36页第六页，

5、共36页。l 串联串联(chunlin)接接Concat(&T, S1, S2)l 初始条件初始条件: 串串S1和和S2存在。存在。l 操作结果操作结果: 将将T返回由返回由S1和和S2联接而成的新串。联接而成的新串。l 求子串求子串SubString(&Sub, S, pos, len)l 初始条件初始条件: 串串S存在存在, 1posStrLength(S)且且l 1lenStrLength(S)-pos+1。l 操作结果操作结果: 用用Sub返回串返回串S的第的第pos个字符起长度为个字符起长度为len的的l 子串。子串。 第6页/共36页第七页，共36页。4.2 串的表示串的表示(bi

6、osh)和实和实现现 定长顺序存储表示定长顺序存储表示(biosh)顺序存储顺序存储 堆分配堆分配(fnpi)存储表示存储表示顺序存储顺序存储 块链存储表示块链存储表示链式存储链式存储第7页/共36页第八页，共36页。1. 定长顺序存储表示定长顺序存储表示(biosh)（定长顺序串）（定长顺序串）define MAXSTRLEN 255 typedef unsigned char SStringMAXSTRLEN+1; l定长顺序串的存储分配是在编译定长顺序串的存储分配是在编译(biny)时完成的。与前面所讲的线性表的顺序存储结构类似时完成的。与前面所讲的线性表的顺序存储结构类似, 用一组地址

7、连续的存储单元存储串的字符序列。用一组地址连续的存储单元存储串的字符序列。l超出予定义长度的串值被舍去，称之为超出予定义长度的串值被舍去，称之为“截断截断”。012255第8页/共36页第九页，共36页。第9页/共36页第十页，共36页。算法算法(sun f)4.2 串联接串联接 strcat( &T，S1，S2 )要求要求: 顺序联接顺序联接(lin ji)串串 S1 和串和串 S2 得到新串得到新串 T 。思想思想(sxing): 基于串基于串S1和和S2长度的不同情况，串长度的不同情况，串T可能出现可能出现3种情况种情况:S10+S20MAXSTRLEN，S10+S20MAXSTRLEN

8、S10MAXSTRLEN，S10MAXSTRLEN，直接联接，直接联接，T0MAXSTRLEN ；截断截断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)表示（堆串）表示（堆串） 在

9、在C语言中，已经有一个称为语言中，已经有一个称为“堆堆”的自由的自由(zyu)存储空间，并可用存储空间，并可用malloc（）和（）和free（）函数完成动态存储管理。（）函数完成动态存储管理。typedef struct char * ch； int length； HString； 应用程序用到的内存分配应用程序用到的内存分配(fnpi)：栈分配：栈分配(fnpi)和堆分配和堆分配(fnpi)。堆：用户程序动态申请的地址空间。堆：用户程序动态申请的地址空间。栈：保存函数参数和块内局部变量的内存区。栈：保存函数参数和块内局部变量的内存区。void Fun1() void Fun2() int

10、 i; int *p=new int10; char p10;.; delete p;.; 第13页/共36页第十四页，共36页。3. 串的块链存储串的块链存储(cn ch)表示（链串）表示（链串） A B C D E F G H I # # # A B B C I . define CHUNKSIZE typedef struct Chunk char chCHUNKSIZE; struct Chunk *next;Chunk;typedef struct Chunk *head; Chunk *tail; int curlen;LString; 第14页/共36页第十五页，共36页。l存储

11、密度大，一些操作（如插入存储密度大，一些操作（如插入(ch r)，删除）有所不便，删除）有所不便，引起大量字符移动，适合于在串基本保持静态使用方式时，引起大量字符移动，适合于在串基本保持静态使用方式时采用；采用；l存储密度小，运算处理方便，但存储空间量大，若处理过存储密度小，运算处理方便，但存储空间量大，若处理过程中，需大量内外存交换，会影响总效率；程中，需大量内外存交换，会影响总效率；l串的字符集的大小，也会影响串值存储方式的选取。串的字符集的大小，也会影响串值存储方式的选取。串值所占的存储位存储密度实际分配的存储位第15页/共36页第十六页，共36页。第16页/共36页第十七页，共36页。

12、1. 朴素模式匹配算法朴素模式匹配算法(Brute-Force算法算法) 求子串位置的定位函数求子串位置的定位函数Index( S, T, pos).模式匹配：子串的定位操作通常称作串的模式匹配。模式匹配：子串的定位操作通常称作串的模式匹配。目标串：主串目标串：主串S。模式串：子串模式串：子串T。匹配成功：若存在匹配成功：若存在T的每个字符依次和的每个字符依次和S中的一个连续字符中的一个连续字符序列序列(xli)相等，则称匹配成功。返回相等，则称匹配成功。返回T中第一个字符在中第一个字符在S中的位置。中的位置。匹配不成功：返回匹配不成功：返回0。4.3 串的模式匹配算法串的模式匹配算法(sun

13、 f)第17页/共36页第十八页，共36页。的对应字符相等的对应字符相等,则匹配成功则匹配成功,该算该算法返回法返回i；否则；否则,匹配失败匹配失败,函数返函数返回回0。第18页/共36页第十九页，共36页。 第第 1 次次匹匹配配 s=cddcdc i=3 t=cdc j=3 失失败败 第第 2 次次匹匹配配 s=cddcdc i=2 t=cdc j=1 失失败败 第第 3 次次匹匹配配 s=cddcdc i=3 t=cdc j=1 失失败败 第第 4 次次匹匹配配 s=cddcdc i=6 t=cdc j=3 成成功功 例如,设目标串s=“cddcdc”,模式串t=“cdc”。s的长度(c

14、hngd)为n(n=6),t的长度(chngd)为m(m=3)。用指针i指示目标串s的当前比较字符位置,用指针j指示模式串t的当前比较字符位置。BF模式匹配过程如下所示。i = i j +2;j = 1;第19页/共36页第二十页，共36页。第20页/共36页第二十一页，共36页。第21页/共36页第二十二页，共36页。 第第 1 次匹配次匹配 s s=abacaba=abacabab b i=4 p p=abab=abab j=4 失败失败 p p=abab=abab j=2 因因p1p2,s2=p2,p1p2,s2=p2,必有必有s2p1,s2p1,又因又因p1=p3,s3=p3,p1=p

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

16、1pj-k+2pj-1” = “si-k+1si-k+2si-1”（部（部分分(b fen)匹配）匹配） “p1p2pk-1” = “pj-k+1pj-k+2pj-1” (真子串）真子串）第24页/共36页第二十五页，共36页。 max k|1kj, max k|1kj,且且“p1pk-1”=“pj-“p1pk-1”=“pj-k+1pj-1” k+1pj-1” 当此集合当此集合(jh)(jh)非空时非空时 0 0 当当j=1j=1时时 1 1 其他情况其他情况nextj=为此为此,定义定义nextj函数，表明当模式中第函数，表明当模式中第j个字符与主串中个字符与主串中相应字符相应字符“失配失配

17、”时，在模式中需重新和主串中该字符时，在模式中需重新和主串中该字符进行进行(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页。第27页/共36页第二十八页，共36页。l若若pk=pj，则有，则有“p1pk”=“pj-k+1pj”， ne

18、xtj+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页。0nextj11122311 2345 6712第29页/共36页第三十页，共36页。第30页/共36页第三十一页，共36页。lKMPKMP算法的时间复杂度算法的时间复杂度 l 设主串设主串s s的长度为的长度为n,n,模式串模式串t t长度为长度为m,m,在在KMPKMP算法中算法中求求nextnext数组的时间复杂度为数组的时间复杂度为O(m),O(m),在后面的匹配中因主在后面的匹配中因主串串s s的下标的下标(xi bio)(xi bio)不减即不回溯不减即不回溯, ,比较次数可记为比较次数可记为n,n,所以所以KMPKMP算法总的时间复杂度为算法总的时间复杂度为O(n+m)O(n+m)。lKMPKMP算法最大的特点就是主串的指针不需要回溯，整个算法最大的特点就是主串的指针不需要回溯，整个匹配过程只需从头到尾扫描一遍，这对于处理需要从外匹配过程只需从头到尾扫描一遍，这对于处理需要从外设输入的庞大数据很有效，可