数据结构第4章 串

第四章串和添锦第4章串

4.1基本概念

4.2串的存储结构

4.3串的基本运算

4.4简单模式匹配4.5KMP算法4.1基本概念

1、基本概念概念：由有限个合法字符组成一组数据表示方法：大写字母作为串的名称，串的内容使用“”、‘’括起来，中间使用等号（=），例如：S=“abc213%4&*a”其中，引号中的每一个字符是串S的一个元素。2、串的术语串长：一个串中每个元素占一个长度，所有元素的长度和就是串长空串：一个串中不包含任何元素空白串：串中的所有元素均是空格子串：一个串在另一个串中出现，这个串就是另一个串的字串主串：

包含字串的串相对于子串来说就是主串3.案例串长：S=“abcdefg”，这个串的长度为7空串：S=“”，这个串的长度为0，因此是一个空串空白串：S=“”这个串的元素都是空格，也就是一个空格串子串：S1=“abc”，S2=“acbdabc”，因此S1是S2的字串主串：由上一个例子可以得知，S2相对于S1就是它的主串。

4、串相等若串之间的长度相等，且其中的元素相同，对应位置的元素也相等，那么说这些串是相等的。S1=“Kunming”，S2=“KunMing”，S3=“Kunming”，S4=“KUNMING”首先，S1,S2,S3,S4的串长相等，满足相等的第一个条件；接下来，S1和S3均包含K,u,n,m,i,n,g，S2与之不同的是M和m,S4均为大写字母，S1和S3满足包含元素相等；且S1和S3对应位置的元素也相等，因此，S1和S3相等。第4章串

4.1基本概念

4.2串的存储结构

4.3串的基本运算

4.4简单模式匹配4.5KMP算法串的定义ClassSeqString(object):def__init__(self,ms):self.ch=[Noneforiinrange(ms)]self.length=0self.MAXSIZE=msProgramming……设ch[100],S=“Programming”,则S的逻辑结构为：012345678910……994.2

串的存储结构

串是一种线型数据结构，之前的课程中线性结构有两种存储形式，保证元素之间的逻辑为线型结构即可。顺序存储：不仅元素之间的关系为线型关系，存储结构也为连续的线性结构；链式存储：只要求元素之间的逻辑关系保持线性结构，存储结构不要求连续。4.2.1串的顺序存储单字节存储：在存储中，一个字符占一个字节的存储形式紧缩存储：串在进行存储时挨个将内存位数存满非紧缩存储：串在进行存储的时候每个内存位只存一个字符单字节存储

1单字节存储（1）存储结构要求存储空间是连续的，并且能够将整个串完整的存储下来（2）基本思想将串中的每一个元素，挨个的存在所分配的存储空间中，内一个元素的存储位置减去第一个元素的位置+1就是这个元素在串中的位置（3）存储实例

设存在串S=“Programming”，则这个串的存储方式为：单字节存储Programming012345678910

2紧缩存储

这种存储方式与单字节存储是一回事，存储形式有所区别。设串S=“Programming”，串的紧缩存储方式为：(32位系统，存储单元为4字节）紧缩存储Prohramming

3非紧缩存储（1）存储要求按照系统位数和存储位数分配存储空间，但是内一个存储位数只存储一个字符。（2）基本思想将存储空间的位数进行存储时，不再挨个存，而是挨位存。非紧缩存储（3）实例设S=“abcde”，则S进行非紧缩存储的示意图为：非紧缩存储abcde4.2.2

串的链式存储在线性表的学习中，我们知道，线性结构的数据还可以使用地址和数据两个域合作的形式完成非连接存储区域的线性存储，在串的存储中主要有以下两个链式存储方法：多字符域链式存储单字符域链式存储

定义4.2classLString(object):def__init__(self,ms):self.ch=[Noneforiinrange(ms)]self.length=0self.MAXSIZE=msself.next=None1、多字符域节点链表结构由定义4.2可以看出，如果按照这样的存储方式进行存储，串的每一个节点可以存储串长不高于MAXSIZE的一个串。这样的存储类似于定义了一个串组，每一个节点可以作为一个串，也可以作为一个字符。

例如：对于串S=“Programming”，多字符域链式存储结构示意图为：Programming^2、单字符域节点链表结构这种存储方式每一个节点只存一个字符，串S的单字符域节点存储示意图如下：

Progrg^ammin第4章串

4.1基本概念

4.2串的存储结构

4.3串的基本运算

4.4简单模式匹配4.5KMP算法4.4串的基本运算1、求串长length(S):统计串S中所包含的合法字符的个数。如：S=“abcde”,则length(S)=5

Slength(s)算法4.1求串长deflength(self）：

returnself.length2、串连接concat（S,T）：将一个串T连接在另一个串S的后面。如：S=“abcd”，T=“efgh”，则concat(S,T)=“abcdefg”STS.MaxSize算法4.2串连接defconcat(s,t):slen=s.lengthtlen=t.lengthifslen+tlen>s.MAXSIZE:returnFalse#空间不够

foriinrange(slen,slen+tlen):s.ch[i]=t.ch[i-slen]s.length=slen+tlenreturnTrue#连接成功3、串比较strcmp(S,T):比较S和T的大小，将其中的元素分别挨个进行对比，得出两个串的大小值。S>T=1，S=T=0，S<T=-1。S=“abcDE”,T=“abcde”,则strcmp(S,T)=-1。

ST是否相等算法4.3串比较defstrcmp(s,t):slen=s.lengthtlen=t.lengthifslen==tlen:i=0whilei<slenandi<tlen:ifs.ch[i]>t.ch[i]:return1ifs.ch[i]<t.ch[i]:return-1i=i+1return0elifslen>tlen:return1else:return-1T1T2T4T5T34、子串查询index（S,T）:查找子串T在主串S中第一次出现的位置。S=“abcdcbad”，T=“bad”，则index(S,T)=7。T能否找到T5、求子串substr(S,i,k):从串S的第i个位置开始，取k个字符作为S串的子串。S=“Programming”，则T=substr(S,3,3)=“ogr”

ST算法4.4求子串defsubstr(s,i,j):

n=s.lengthifi<1ori>nori+j>n+1:print("iorjisinvalid.")returnFalsesbs=String(j)sbs.length=jforkinrange(i,i+j):sbs.ch[k-i]=s.ch[k-1]returnsbs6、插入子串insert(S,T,i):在主串S的第i个位置插入子串TS=“aefg”，T=“bcd”，则insert（S,T,2）=“abcdefg”算法4.5插入子串definsert(s,t,i):#在的第i个位置插入tn=s.lengthm=t.lengthifi<1ori>n+1orm+n>s.MAXSIZE:returnFalse#出错结束插入操作

j=n-1whilej>=i-1:s.ch[m+j]=s.ch[j]j=j-1j=i-1whilej<i+m-1:s.ch[j]=t.ch[j-i+1]j=j+1s.length=m+n7、删除子串delete(S,i,k):在主串S中删除从第i位开始的连续k个字符。S=“Programming”，则delete（S,3,4）=“Prmming”

算法4.6删除子串defdelete(s,i,j):#删除s中第i个位置开始的j个字符

n=s.lengthifi<1ori>nori+j>s.MAXSIZE+1:returnFalse#出错结束删除操作

forkinrange(i-1+j,n):s.ch[k-j]=s.ch[k]s.length=s.length-j8、复制串strcpy（S,T）：将串S的所有元素复制给串T。S=“Kunming”，T=“”,运行strcpy(S,T)后，T=“Kunming”ST算法4.7复制串defstrcopy(s,t):#将字符串t的值，赋值给s1n=t.lengthforiinrange(0,n):s.ch[i]=t.ch[i]s.length=n第4章串

4.1基本概念

4.2串的存储结构

4.3串的基本运算

4.4简单模式匹配4.5KMP算法4.5串的简单模式匹配1、基本概念字符串匹配是串的基本运算的一种操作，主要是指在一个串中，查找另一个串，查找成功后返回首次出现的位置，查找失败直接返回错误。

2、基本思路将子串的元素挨个取出来，并与主串的元素进行比较。从主串的第一个位置开始对比，失败以后对比顺序往后移动一位，直到对比到主串长-子串长的位置。ST现在需要在主串S中寻找子串T，如果找到了就返回T[0]==S[i]时候的i的值，若直到最后都没有找到，则返回-1。（在数据结构中，顺序结构的下标是从0开始的，因此，即便在计算机中可以使用0表示逻辑否，但是这里不能返回0）？若这里的“？”是相等若这里的“？”是不相等继续判断”？”的逻辑k3、简单算法defindex(t,p):#在t中查找p是否存在

i=0whilei<t.length:j=0whilej<p.length:ift.ch[i+j]!=p.ch[j]:break;j=j+1ifj==p.length:returni#匹配成功，返回ii=i+1return-1#匹配不成功，返回-1第4章串

4.1基本概念

4.2串的存储结构

4.3串的基本运算

4.4简单模式匹配4.5KMP算法

4.6KMP算法1、基本思路

CDABADABCABADABABABADABABs=p=4.6KMP算法1、基本思路

CDABADABCABADABABABADABABs=p=根据对比我们可以看到。KMP算法在进行匹配时，出现失败了，并不会每一次都是移动一位进行二次匹配，而是移动到下一个有用的匹配的位置继续匹配2、算法描述在进行模式匹配时，如果执行s[i](1≤i≤m)与p[j](1≤j≤n)的试配，可能出现的情况如下：（1）如果s[i]=p[j]，则继续进行试配，进行s[i+1]与p[j+1]的试配；（2）如果s[i]≠p[j]，则①如果j=1，把模式p右移一位再从头开始进行试配。②如果2≤j≤n，选择一个适当的位置next[j],进行si与p[next(j)]的试配，把模式串的位置移动到j-next[j]。next[j]称为“失效函数”。算法4.9defindexKMP(t,p,next):#KMP算法,由于数组下标是从0开始,所以请注意文中描述的i,j值与下标之间的换算关系。

i=0j=0whilei<t.lengthandj<p.length:

ifj==-1ort.ch[i]==p.ch[j]: i=i+1 j=j+1 else: j=next[j]ifj==p.length:returni-jels