资源描述：
《数据结构第四章串课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、数据结构 第四章串重庆一中葛静串的基本概念串：字符串，是一种特殊的线性表，它的数据仅由一个字符组成，计算机非数值处理的对象经常是字符串数据。例如：’Iloveprograms!’字符串的定义串的定义：vars:string;字符串长度255Vars:string[100];字符串长度100串的数组实现：Typestring=recordch:array[1..maxlen]ofchar;curlen:integer;end;串的指针实现：Typetlink=recordch:char;next:^tlink;end;string
2、=^tlink;串的相关概念串的长度：串中的字符个数n称为串的长度。空串：一个串只有0个字符，长度为0。子串：串中连续的任意个字符的子序列为子串，空串是任意串的子串。两串相等：对于串s1,s2,如果s1是s2的子串，且s2是s1的子串，则两串s1,s2相等。串的运算1、串的连接，即串的加法运算2、求子串S=copy(s1,i,j),求串s1中第i位开始的，连续j个字符组成的子串。3、删除子串的操作：删除s中第i位开始的连续j个字符。S=delete(s,i,j)4、插入子串的操作：将s1插入s的第i位之后。Insert(s1,s
3、,i);5、求子串的位置：求串s1第一次出现在s的哪个位置。Result=pos(s1,s)6、求字符串s的长度：len=length(s)7、将数值转换为字符串str(value,s)例如：value=12345,str(value:6,s),s=‘12345’Value=3.14e4,str(value:10:0,s),s=‘31400’Value=3.14e4,str(value:10:2,s),s=‘31400.00’串的运算8、将字符串转换为数值Val(s,value,code)把字符串表达式s转换成对应的整型值或实型
4、值。Code为错误代码，成功为0，不成功则返回第一个出错字符的位置。例如：s=‘1234’,转换后value=1234,code=0S=‘123a’,转换后value无意义，code=4S=‘3.14e4’,转换后value=31400,code=0串的模式匹配问题简单说：主串Ｔ[1..n]，模式串P[1..m]，问T串是否包含P串?包含，则返回模式串在主串中的起始位置。如：T=‘Ilovepascal!’,P=‘pascal’,T包含P，P在T的第6位首次出现。抽象地说：主串Ｔ[1..n]，模式串P[1..m]，找到所有的S∈
5、[1..n-m+1],满足对于X∈[1..m],都有T[s+x-1]=P[x]。串的模式匹配问题朴素算法从主串的第一个字符起合模式串的第一个字符进行比较，若相等则进一步比较二者的后续字符，否则从主串的第二个字符起再重新和模式串的第一个字符比较，依此类推，直至模式串和主串中的一个子串相等，则匹配成功，否则称匹配失败。串的模式匹配问题朴素算法vart,p:string;n,m,i,j,k:integer;beginreadln(t);readln(p);n:=length(t);m:=length(p);i:=1;j:=1;Whil
6、e(i<=n-m+1)and(j<=m)doift[i]=p[j]thenbegininc(i);inc(j)endelsebegini:=i-j+2;j:=1;end;Ifj>mthenwriteln(i-m)Elsewriteln(‘no!’);End;时间复杂度Ｏ（nm）KMP算法由Kunth、Morris和Pratt提出的一个模式匹配算法，简称为KMP算法。其基本思想是：不象朴素算法中每次重新比较，充分利用已经得到的部分匹配结果，将模式向右滑动尽可能远的一段距离，接着继续进行比较。KMP算法例1：Ｔ=‘tomatogoo
7、dtomatobad’P=‘tomatoisbad’解：Pt0matoisbadpr00001200000TtomatogoodtomatobadPtomatoisbadPtomatoisbadPtomatoisbadPtomatoisbKMP算法O(m+n)例2：T=‘abababaababacb’,P=‘ababacb’解：PababacbPr0012300TabababaababacbPababacbPababacbPababacbPababacbPababacbKMP算法j:=0; fori:=1tondo begin
8、 while(j>0)and(P[j+1]<>T[i])doj:=Pr[j]; ifP[j+1]=T[i]thenj:=j+1; ifj=mthen begin writeln(‘Patternoccurswithshift’,i-m)
