《数据结构 第四章ppt课件.ppt》由会员分享，可在线阅读，更多相关《数据结构 第四章ppt课件.ppt（34页珍藏版）》请在三一办公上搜索。
1、数据结构课程的内容,第4章 串（String）,4.2 串的表示和实现4.3 串的模式匹配算法,1.定义2.逻辑结构3.存储结构4.运算规则5.实现方式,4.1 串类型的定义,串即字符串，是由零个或多个字符组成的有限序列，是数据元素为单个字符的特殊线性表。,4.1 串类型的定义,说明：串是一种在数据元素的组成上具有一定约束条件的线性表，即要求组成线性表的所有数据元素都是字符（字母、数字或其他字符），所以，人们经常这样定义串：串是一个有穷字符序列。,4,若干术语：串长：空白串：子串：子串位置：字符位置：串相等：,串中字符个数（n0）.n=0 时称为空串。由一个或多个空格符组成的串。串s中任意个连
2、续的字符序列叫s的子串;S叫主串。子串的第一个字符的序号。字符在串中的序号。串长度相等，且对应位置上字符相等。,注：空串是任意串的子串。任意串是其自身的子串。,5,串常量和串变量通常在程序中使用的串可分为：串常量和串变量。串变量：串变量和其它类型的变量一样，其值是可以改变的。串常量：串常量和整常数、实常数一样，在程序中只能被引用但不能改变其值。即只能读不能写。串常量由直接量来表示的：【例】Error（“overflow”）中“overflow”是直接量。串常量命名 有的语言允许对串常量命名，以使程序易读、易写。【例】C+中，可定义串常量pathconst char path=dir/bin/a
3、ppl;,练1：串是由 字符组成的序列，一般记为。,练2：现有以下4个字符串：a=BEI b=JING c=BEIJING d=BEI JING,问：他们各自的长度？a是哪个串的子串？在主串中的位置是多少？,a=3，b=4，c=7，d=8,a是c和d的子串，在c和d中的位置都是1,练3：空串和空白串有无区别？答：有区别。空串(Null String)是指长度为零的串；而空白串(Blank String),是指包含一个或多个空白字符(空格键)的字符串.,0个或多个,S=a1a2an,ADT StingObjects:D=ai|aiCharacterSet,i=1,2,，n,n0Relations
4、:R1=|ai-1,ai D,i=2,，nfunctions:/有13种之多StrAssign(&T,chars)/串赋值，生成值为chars的串TStrCompare(S,T)/串比较，若ST，返回值大于0 StrLength(S)/求串长，即返回S的元素个数 Concat(&T,S1,S2)/串连接，用T返回S1S2的新串SubString(&Sub,S,pos,len)/求S中pos起长度为len的子串Index(S,T,pos)/返回子串T在pos之后的位置 Replace(&S,T,V)/用子串V替换子串TADT Sting,串的抽象数据类型定义（参见教材P71）,最小操作子集,设
5、s=I AM A STUDENT,t=GOOD,q=WORKER。求：,练习：,StrLength(s)StrLength(t)SubString(s,8,7)=SubString(t,2,1)=Index(s,A)=Index(s,t)=Replace(s,STUDENT,q)=,144STUDENTO30（s中没有t！）I AM A WORKER,再问：Concat(SubString(s,6,2),Concat(t,SubString(s,7,8)？,4.2串的表示和实现,定长顺序存储表示用一组地址连续的存储单元存储串值的字符序列堆分配存储表示用一组地址连续的存储单元存储串值的字符序列,
6、但存储空间是在程序执行过程中动态分配而得。串的块链存储表示链式方式存储,首先强调：串与线性表的运算有所不同，是以“串的整体”作为操作对象，例如查找某子串，在主串某位置上插入一个子串等。串有三种机内表示方法：,顺序存储,链式存储,定长顺序存储特点：用一组连续的存储单元来存放串，直接使用定长的字符数组来定义，数组的上界预先给出，故称为静态存储分配。,例如：#define Maxstrlen 255/用户可用的最大串长 typedef unsigned char SString Maxstrlen1;SString s;/s是一个可容纳255个字符的顺序串。,注：一般用SString0来存放串长信息
7、；C语言约定在串尾加结束符 0，以利操作加速，但不计入串长；若字符串超过Maxstrlen 则自动截断（因为静态数组存不 进去）。,讨论：想存放超长字符串怎么办？静态数组有缺陷！,实现方式：参见教材P73编程两例，两串连接和求子串,改用动态分配的一维数组,“堆”！,例：用顺序存储方式实现求子串函数SubString(&Sub,S,pos,len),Status SubString(SString,将串S中从第pos个字符开始长度为len的字符序列复制到串Sub中（注：串Sub的预留长度与S一样）,s=a1,a2,.,an,n串长,pos,len,思路：利用malloc函数合理预设串长空间。特点
8、：若在操作中串值改变，还可以利用realloc函数按新串长度增加(堆砌)空间。,Typedef struct char*ch;/若非空串,按串长分配空间;否则 ch=NULLint length;/串长度HString,堆分配存储特点：仍用一组连续的存储单元来存放串，但存储空间是在程序执行过程中动态分配而得。,约定：所有按堆存储的串，其关键信息放置在：,Status StrInsert(HString/StrInsert,例：用“堆”实现串插入操作(教材P75),Status StrAssign(HString/StrAssign,指针变量C也可以自增！意即每次后移一个数据单元。,附：堆分配存
9、储表示,直到终值为“假”停止，串尾特征是0NULL=0,显然，若数据元素很多，用法2存储更优称为块链结构,链式存储特点：用链表存储串值，易插入和删除。,法1：链表结点（数据域）大小取1,法2：链表结点（数据域）大小取n(例如n=4),16,虽然提高结点的大小使得存储密度增大，但是做插入、删除运算时，可能会引起大量字符的移动，给运算带来不便。,#define CHUNKSIZE 80/可由用户定义的块大小typedef struct Chunk/首先定义结点类型 char ch CHUNKSIZE;/结点中的数据域 struct Chunk*next;/结点中的指针域Chunk;,块链类型定义：
10、,例略,typedef struct/其次定义用链式存储的串类型 Chunk*head;/头指针 Chunk*tail;/尾指针 int curLen;/结点个数 Lstring;,再次强调：串与线性表的运算有所不同，是以“串的整体”作为操作对象，例如查找某子串，在主串某位置上插入一个子串等。,这类操作中均涉及到定位问题，称为串的模式匹配。它是串处理系统中最重要的操作之一。,19,4.3 串的模式匹配算法,模式匹配(Pattern Matching)即子串定位运算（Index函数）。,算法目的：确定主串中所含子串第一次出现的位置（定位）即如何实现 Index(S,T,pos)函数（见教材P72
11、）,初始条件：串S和T存在，T是非空串，1posStrLength(s)操作结果：若主串S中存在和串T值相同的子串，则返回它在主串S中第pos个字符之后第一次出现的位置；否则函数值为0。,注：S称为被匹配的串，T称为模式串。若S包含串T，则称“匹配成功”。否则称“匹配不成功”。,BF算法设计思想：将主串的第pos个字符和模式的第1个字符比较，若相等，继续逐个比较后续字符；若不等，从主串的下一字符（pos+1）起，重新与第一个字符比较。,BF算法（又称古典或经典的、朴素的、穷举的）KMP算法（特点：速度快）,算法种类：,直到主串的一个连续子串字符序列与模式相等。返回值为S中与T匹配的子序列第一个
12、字符的序号，即匹配成功。否则，匹配失败，返回值 0.,Int Index(SString S,SString T,int pos)i=pos;j=1;while(iT0)return i-T0;/子串结束，说明匹配成功 else return 0;/Index,BF算法的实现即Index（）操作的实现（见教材P79）,相当于子串向右滑动一个字符位置,匹配成功后指针仍要回溯！因为要返回的是被匹配的首个字符位置。,例：S=ababcabcacbab，T=abcac，pos=1，求：串T在串S中第pos个字符之后的位置。,解：,此题的BF算法：int IndexBF(Sstring S,Sstrin
13、g T)i=1;j=1;while(iT0)return i-T0;else return 0;,讨论：若n为主串长度，m为子串长度，则串的BF匹配算法最坏的情况下需要比较字符的总次数为,(n-m+1)*mO(n*m),最恶劣情况是：主串前面n-m个位置都部分匹配到子串的最后一位，即这n-m位比较了m次，别忘了最后m位也各比较了一次，还要加上m！,BF匹配算法的最坏时间复杂度,但一般情况下BF算法的时间复杂度为O(n+m),KMP算法（特点：速度快）,KMP算法设计思想 KMP算法的推导过程 KMP算法的实现（关键技术:计算nextj）KMP算法的时间复杂度,能否利用已经部分匹配的结果而加快模
14、式串的滑动速度？能！而且主串S的指针i不必回溯！可提速到O(n+m)！例：,KMP算法设计思想：(参见教材P80-84）,S=a b a b c a b c a c b a b,T=a b c a c,S=a b a b c a b c a c b a b,T=a b c a c,S=a b a b c a b c a c b a b,T=a b c a c,Index_kmp的返回值应为i=6,需要讨论两个问题：如何“记忆”部分匹配结果？如何由“记忆”结果计算出主串S第i个字符应该与模式T中哪个字符再比较？即确定模式T中的新比较起点k.,a b a,a b c,KMP算法的推导过程：（见教材
15、P81）,抓住部分匹配结果的两个特征：,两式联立可得：T1Tk-1=Tj-(k-1)Tj-1注意：j 为当前已知的失配位置，我们的目标是计算新起点 k，仅剩一个未知数k，理论上已可解，且k仅与模式串T有关！,则S前i-1i-(k-1)位T的j-1j-(k-1)位 即(4-3）式含义,则T的k-11位S前i-1i-(k-1)位 即(4-2）式含义,刚才肯定是在S的i处和T的第j字符 处失配,设目前应与T的第k字符开始比较,KMP算法的推导过程(续）：,根据模式串T的规律：T1Tk-1=Tj-(k-1)Tj-1和已知的当前失配位置j，可以归纳出计算新起点 k的表达式。令k=next j，则,nex
16、t j,0 当j1时max k|1kj 且T1Tk-1=Tj-(k-1)Tj-1 1 其他情况,讨论：next j 有何意义？一旦失配，应从模式串T中第next j 个字符开始与S的失配点i 重新匹配!next j 怎么求？后面会举例（参见教材P81）,第一步，先把模式T所有可能的失配点j所对应的nextj计算出来；第二步：执行定位函数index_kmp（与BF算法模块非常相似）,KMP算法的实现即Index()操作的实现（见教材P82）,Int Index_KMP(SString S,SString T,int pos)i=pos;j=1;while(iT0)return i-T0;/子串结
17、束，说明匹配成功 else return0;/Index_KMP,怎样计算模式T所有可能的失配点 j 所对应的 nextj？,例：模 式 串 T：a b a a b c a c 可能失配位 j：1 2 3 4 5 6 7 8新匹配位 nextj:,0,1,1,2,2,3,1,2,讨论：,j=1时,next j=0；因为属于“j=1”;j=2时,next j=1；因为属于“其他情况”；,刚才已归纳：,j=3时,k=2，只需查看T1=T2；,j=4时,k=2，3，要查看T1=T3 和T1T2=T2 T3,j=5时,k=2，3，4，要查看T1=T4、T1T2=T3T4 和 T1T2T3=T2T3T4
18、,以此类推，可得后续nextj值。,讨论两个有关next j 的问题：,怎样简捷计算nextj？可用递推法编程实现！（参见P83简捷算法）计算nextj的时间为O(m),void get_next(SString T,int/get_next,void get_nextval(SString T,int/get_nextval,next j 是否完美无缺？答：未必，例如当S=a b a a a a b,T=a a a a b时仍有多余动作（参见P84改进算法,称为nextval j）,附：求解nextj 算法流程图:,例如：求abaabcac模式串的next函数,next1=0next2=1
19、pnext1!=p1next3=1 pnext2!=p2next4=2 pnext3=p3next5=2 pnext4!=p4 pnextnext4=p4next6=3 pnext5=p5next7=1 pnext6!=p6 pnext3!=p6 pnext3!=p6next8=2 pnext7=p7,next函数的改进算法,前面定义的next函数在某些情况下还是有缺陷例如：模式aaaab与主串aaabaaaab匹配情况：,S:a a a b a a a a b,T:a a a a b,i:1 2 3 4 5 6 7 8 9,a a a a b,a a a a b,a a a a b,a a
20、a a b,当Pj=Pnextj时，则,如果Si!=Pj，=Si!=Pnextj,因此，Si 没有必要继续与 Pnextj进行比较，而应该直接和Pnextj的下一个字符Pnextnextj进行比较。,因此，在计算next函数时，如果出现Pj=Pnextj=Pk则nextj=nextk=nextnextj,修改算法见教材P84 算法4.8,此时效率不高的原因为：,KMP算法的时间复杂度,注意：由于BF算法在一般情况下的时间复杂度也近似于O(n+m)，所以至今仍被采用。,而此时KMP的情况是：由于指针i无须回溯，比较次数仅为n,即使加上计算nextj时所用的比较次数m，比较总次数也仅为n+m=O(nm)，大大快于BF算法。,回顾BF的最恶劣情况：S与T之间存在大量的部分匹配，比较总次数为：(n-m+1)*mO(n*m),因为主串指针i不必回溯，所以从外存输入文件时可以做到边读入边查找，“流式”作业！,KMP算法的用途：,本章结束,
