计算机上的非数值处理的对象基本上都是字符串数据.ppt

1、2020/8/6,第四章 串,2020/8/6,计算机上的非数值处理的对象基本上都是字符串数据。,例：学生管理系统中，学生学号、姓名、性别、院系等；,图书管理系统中，图书编号、书名、作者、简介等；,2020/8/6,字符串常量,字符串变量,+ 一系列字符串操作,= 一种新的数据类型串类型,由于硬件结构的特点，决定了处理字符串数据时要比数值数据复杂的多。,(1) 字符串是由一个个字符组成的，需要对每个字符分别处理,(2) 字符串需要先转化为数值后再进行处理,ASC(A),ASC(a),= 65,= 97,2020/8/6,4.1 串类型的定义,1. 基本概念,串: 由零个或多个字符组成的有限序列

2、。,s串名,|s|串的长度，即串中字符的数目。,零个字符的串称为空串，计作 = 。,|,= 0,ai为字符,2020/8/6,串中任意个连续的字符组成的子序列称为该串的子串。,包含子串的串相应的称为主串。,例，串 eij 是串 beijing 的子串， beijing 称为主串。,字符在序列中的序号称为该字符在串中的位置。,子串在主串中的位置定义为子串的第一个字符在主串中的位置。,例，字符 n 在串 beijing 中的位置为 6 。,例，子串 eij 在串 beijing 中的位置为 。,2,2020/8/6,两个串相等，当且仅当这两个串的值相等。,例，串 bei jing 与串 beiji

3、ng 不相等 。,串值必须用一对单引号括起来，但单引号本身不属于串，只起界定作用。,2020/8/6,串的基本操作和线性表区别很大。,线性表: 大多以“单个元素”为操作对象,串: 通常以“串的整体”为操作对象,例:查找某个元素；插入某个元素；删除某个元素,例: 查找某个子串；截取某个子串； 在某个位置插入、删除某个子串,2020/8/6,2. 串的抽象数据类型的定义,数据对象: D = ai | ai CharacterSet，i = 1, 2, , n ,数据关系: R1 = ,基本操作:,ADT String ,2020/8/6,StrEmpty ( S ),StrCopy ( ,# de

4、fine MaxWordNum 100,2020/8/6,方便插入,采用链式结构,HString keyword ；,LinkIdxList bnolist ；,Struct Node * next ；,# define MaxKeyNum 2500,LinkNode * head ；,Int length ；,2020/8/6,串的模式匹配,模式匹配是指子串的的定位运算，又称串匹配，是串中常用且应用广泛的一种操作，一般将主串称为目标串S，子串称为模式串t，如果在目标串S中找到模式串t，则模式匹配成功。常用的算法如下： 一、简单模式匹配： 算法的基本思想：从目标串S=“S0S1S2SN-1的第

5、一个字符开始和模式串t=“t0t1t2.tm-1”中的第一个字符比较，若相等，则继续逐个比较后续字符，否则从目标串的第二个字符开始重新与模式串t的第一个字符进行比较，依次类推，若匹配成功，则返回模式串t中第一个字符在目标串s 中的位置，否则匹配失败。,2020/8/6,最坏情况下，每次比较都在最后出现不等，最多比较n-m+1趟，总比较次数为m(n-m+1),最坏情况下的时间复杂度为: O（n m) 例如：s=“aaaaaaaaaaaab” t=“aab”,简单模式匹配算法如下： int index (Sstring s, Sstring t,int pos) i=pos;j=1; while

6、(i= t0)return i- t0; else return 0; ,2020/8/6,二、模式匹配的一种改进算法（KMP) 简单模式匹配算法的比较次数较大，原因在于目标串的检测指针需要回溯。 KMP算法的改进在于：每一趟匹配过程中出现字符比较时，不需回溯I指针而是利用已经得到的部分匹配的结果将模式向右“滑动”尽可能远的一段距离，继续进行比较。,2020/8/6,例： i =3 第一趟：a b a b c a b c a c b a b a b c j=3,第二趟：a b a b c a b c a c b a b,i,i =7,a b c a c,j=5,第三趟：a b a b c a

7、b c a c b a b,i,i =11,(a) b c a c,j=2,j=6,2020/8/6,一般情况下若令nextj=k，则nextj表明当模式中第j个字符与主串中相应字符失配时，在模式中需重新和主串中该字符进行比较的字符的位置。 nextj定义如下：,nextj=,0 当j=1时 Maxk|1kj 且p1.pk=pj-k+1.pj-1 1 其它情况,例如： j 1 2 3 4 5 6 7 8,模式串 a b a a b c a c Nextj 0 1 1 2 2 3 1 2,在求得模式的 next函数后，匹配方法如下: i ,j 分别为主串、子串的指针，初值为pos 和1； 若在匹

8、配过程中si=pj ，则i, j各自增1；,说明：j=nextj=0时，表示j不移动，i=i+1,2020/8/6,否则，i不变，j=nextj的位置再比较，若相等，则指针各自增 1，否则，j再退到下一个next的位置，依次类推。,算法:int index_kmp(sstring S , sstring T,int pos) I=pos ;j=1; While (IT0) return I-T0; Else return 0 ,2020/8/6,例： 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,第三趟 a c a b a

9、 a b a a b c a c a a b c,i =2,a,j=1,i =3,i =8,a b a a b c,j=1,j=6,next1=0,第二趟 a c a b a a b a a b c a c a a b c,next6=3,2020/8/6,三、Next函数求值,Next函数只与模式串有关，与主串无关。用递推法求得。,Next1=0 设nextj=k,若tk=tj,则nextj+1=nextj+1=k+1; 否则把计算nextj+1的值看作模式匹配问题，将模式串向右滑动至k=nextk(0kk)若tj=pk,则nextj+1=k+1=nextk+1, 若tj pk，则继续右滑到

10、k”=nextk,依次类推，直到某次匹配成功或最后失败，则失败时next0+1=-1+1=0 例： j 1 2 3 4 5 6 7 8 模式 a b a a b c a c nextj 0 1 1 2 2 3 1 2 (a b a),2020/8/6,j 1 2 3 4 5 6 7 8 模式 a b a a b c a c nextj 0 1 1 2 2 3 1 2 (a b a),Next1=0; Next2=next1+1=1; Next3=next2+1=1 /next2=1(k) , p1 p2 ,k=nextk=next1=0 Next4=next3+1=2 / next3=1 ,p

11、1=p3 ,next3+1=k+1=1+1=2; Next5=next4+1 /next4=2(k);p2p4 ,k=nextk=next2=1,p1=p4 Next5 =next4+1=k+1=1+1=2;,2020/8/6,Next6=next5+1 =3/ next5=2 ,p2=p5 =2+1=3 next1=0 Next7=next6+1=1 / next6=3,p3 p6 ,k=nextk=next3=1,next1=0,next7=0+1=1,2020/8/6,求next 函数值的算法： Get _next (Sstring T ,int ,2020/8/6,Nextvalj=,Nextk nextj=k 且tj=tk Nextj 其它,例：已知s1=aaab,s2=abcabaa, 分别求出它们的Ne