数据结构4串4完整版

第四章串数据结构一.串的抽象数据类型的定义二.串的表示和实现三.串的模式匹配算法串是字符串的简称。它是一种特殊的线性表，线性表的每个元素仅由一个字符组成。串是由零个或多个字符组成的有限序列。一般记为：s=“

a1a2…an”

串名串值串的长度：串中字符的数目。空串：长度为零的串。用“”来表示空串。4.1串的基本概念子串：串中任意个连续的字符组成的子序列称为该串的子串。主串：包含子串的串相应地称为主串。例：s1=“12ab3AB45ABC”-------主串

s2=“AB”-------子串字符在串中的位置：字符在字符串序列中的序号子串在主串中的位置：子串在主串中的第一次出现时，子串中的第一个字符在主串中的位置。串相等：两个串的长度相等，并且各个对应位置的字符都相等。4.2串的基本操作(1)判等函数：EQUAL(s，t)(2)求长函数：LENGTH(s)(3)连接函数：CONCAT(s，t)(4)求子串函数：SUBSTR(s，start，len)

若1≤start≤length(s)

且

0<len

≤length(s)-start+1，则返回从串s中第start个字符起，长度为len的字符序列，否则返回一个特殊的串常量。(5)INDEX(s，t)定位函数。t<>

若在主串s

中存在和

t

相等的子串，则函数值为s

中第一个这样的子串在主串s

中的位置，否则函数值为零。(6)REPLACE(

s，t，v)

置换操作：以串v替换串s中所有和t相等的不重叠的子串。例如：设s=“BBABBABBA”，

t

=“AB”，v=“A”

则REPLACE(s，t，v)的操作结果为:“BBABABA”(7)INSERT(s，pos，t)插入操作:

当1≤pos≤length(s)+1时，在串s的第pos个字符之前插入串t。(8)DELETE(s，pos，len)删除操作当1≤pos≤length(s)

且

0<len

≤length(s)-pos+1时，从串s中删去从第pos个字符起长度为len的子串。(9)CREAT(s，ss)：

设定一个串s，其值为字符序列ss。(10)ASSIGN(s

，t)：将t的值赋给s。一.定长顺序存储方式

4.3串的存储结构#defineMAXLEN255//预定义长度typedef

charSString[MAXLEN+1]

//0号单元存放串长按这种串的表示方法实现的串的运算时，其基本操作为

“字符序列的复制”串的实际长度可在这个预定义长度的范围内随意设定，超过予定义长度的串值则被舍去，称之为“截断”特点:定长顺序存储方式下串操作的实现n

t1t2…tnt

ms1s2…smsMAXLEN

s1s2…sm

t1t2…tnlm+n例1：串联接concat(s，t)；SString

concat(SStrings1，SStrings2，int

&overflow)

//设局部变量t用于函数的返回值，overflow=0为正常联接{if(

s1[0]+s2[0]≤MAXLEN

){t[1..s1[0]]=s1[1..s1[0]]；t[s1[0]+1..s1[0]+s2[0]]=s2[1..s2[0]]；t[0]=s1[0]+s2[0]；overflow=0；}；

elseif

(s1[0]<MAXLEN)

//截断s2串

{t[1..s1[0]]=s1[1..s1[0]]；t[s1[0]+1..MAXLEN]=s2[1..MAXLEN–s1[0]]；t[0]=MAXLEN；overflow=1；}；

else{

//s1[0]==MAXLENt[0..MAXLEN]=s1[0..MAXLEN];overflow=1；}

return(t);}//concat

(2)求子串SUBSTR(s，start，n)SString

substr(SString

s，int

start，

int

n){

//返回在s串中从start位置起长度为n的子串if(start<1||start>s[0]||n<1||n>s[0]-start+1)return空串；

else{

sub[1..n]=s[start..start+n-1]；sub[0]=n；

return(sub)；

}}以一组地址连续的存储单元存放串值字符序列，但它们的存储空间是在程序执行中从堆中(Heap)动态分配而得。所以也称为动态存储分配的顺序表。在C语言中，利用动态存储管理函数，来根据实际需要动态分配和释放字符数组空间typedef

struct{

char*ch；

//若是非空串，则按串长分配存储空间，否则ch为NULL

intlength；

//串的长度}HString；HString

S；二.堆分配顺序存储方式(1)串联接函数CANCAT(S1，S2，&T)statusconcat(HString

S1,HString

S2,HString

&T){

//用参数T返回连接S1和S2后的新串if(T.ch)

free(T.ch)；

//释放旧的空间

T.ch=(char*)malloc((S1.length+S2.length)*sizeof(char)

)

T.length=S1.length+S2.length；T.ch[0..S1.length-1]=S1[0..S1.length-1]；T.ch[S1.length..T.length-1]=S2[0..S2.length-1]；

returnOK；}//concat

(2)求子串SUBSTR(s，start，n)HSstring

substr(HString

s，int

start，

int

n){//用sub返回在s串中从start位置起长度为n的子串if(start<1||start>s.length||n<1||n>s.length-start+1)

return空串；else{

sub.ch=(char

*)malloc(n*sizeof(char))；sub.ch[0..n-1]=s[start-1..start+n-2]；

sub.length=n；

return(sub)；}}为了便于进行串的操作，除头指针外还可附设一个尾指针指示链表中的最后一个结点，并给出当前串的长度。称这种结构为块链结构。三.串的块链存储方式例如:

在编辑系统中，整个文本编辑区可以看成是一个串，每一行是一个子串，构成一个结点。即:同一行的串用定长结构(80个字符),行和行之间用指针相联接。abcdefghi###/\Headabc…i/\Head#define

CHUNKSIZE

80

//

可由用户定义的块大小typedef

struct

BNode

{chardata[CHUNKSIZE]；//块内连续字符结点成员

struct

BNode*next；}typedef

struct{

struct

BNode*head，*tail；//串的头和尾指针

int

curlen；

//串的当前长度

}LString；

//串的类型是一个结构

LString

s；abcdefghi###/\headtail9例：主串s=“ababcabcacbab”,

模式串t=“abcac”的匹配过程。

第一趟：ababcabcacbab

abc

ac

i=1

j=1i=2j=2i=3j=3

第二趟：ababcabcacbab

abc

aci=2j=14.4子串的模式匹配

第三趟：ababcabcacbab

abc

a

c

i=3j=1i=4j=2i=6j=4i=5j=3i=7j=5

第四趟：ababcabcacbab

abc

aci=4j=1

第五趟：ababcabcacbab

abc

aci=5j=1

第六趟：ababcabcacbab

abc

aci=6j=1i=7j=2i=8j=3i=9j=4i=10j=5i=11j=6定长顺序存储方式

下INDEX(S，T)算法如下：int

index(SStringS，SString

T){//返回子串T在主串S中首次出现的位置i=1；j=1；//S[0],T[0]为串长while(i≤S[0]&&j≤

T[0])

if(S[i]==T[j])

{i++；j++};else{i=i-j+2；j=1}；if(j>T[0])

return(i-T[0]);elsereturn(0)；}//index模式匹配的一种改进算法(KMP算法)

第三趟：ababcabcacbab

abc

a

ci=3j=1i=4j=2i=6j=4i=5j=3i=7j=5

在index(s，t)的回溯法中，第三趟如下：第四趟：让i回溯到4。回溯方法的问题：改进：

每一趟匹配过程中出现字符比较不等时，不需回溯i指针，而是利用已经得到的“部分匹配”的结果，将模式串向右“滑动”尽可能远的一段距离后，继续进行比较。0000000000000000000000000000000000000000000000001000000010000000100000001

第一趟：ababcabcacbab

abc

ac

i=1

j=1i=2j=2i=3j=3

第二趟：ababcabcacbab

abc

aci=3j=1i=4j=2i=5j=3i=6j=4i=7j=5

第三趟：ababcabcacbab

(a)bc

aci=7j=2i=8j=3i=9j=4i=10j=5i=11j=6S1S2……Si-j+1……Si-j+k-1……Si-k+1……Si-1

Si…

≠

P1P2……Pk-1

Pk

……Pj-k+1……Pj-1

Pj

?

k=next[j]

P1……Pk-1

Pk假设主串为“s1s2…sn”，模式串为“p1p2…pm”，如在匹配过程中产生“失配”(si

≠pj)，模式串应向右滑动多远，即si

应与模式串中哪个字符再比较？假设应与第k(k<j)个字符pk继续比较，“p1p2…pk-1”=“Si-k+1Si-k+2…Si-1”

(1)“pj-k+1

pj-k+2…pj-1

”=“Si-k+1Si-k+2…Si-1”

(2)由(1)、(2)得到：

“p1p2…pk-1”=“pj-k+1pj-k+2…pj-1”

若令next[j]=k，则模式串的next函数如下定义：0，j=1next[j]=max

{k|1<k<j且

“p1…pk-1”=“pj-k+1…pj-1”}1，其它

j12345678模式串

abaabcacnext[j]j=1:

next[1]=0j=2:

满足1<k<j的k不存在，next[2]=1j=3

:满足1<k<j的k=2:“p1”=“a”不等于“p2”=“b”,next[3]=1j=4

:满足1<k<的k=2，3；

k=2

:“p1”=“a”等于“p3”=“a”k=3

:“p1p2”=“ab”不等于“p2p3”=“ba”,

next[4]=2

0

1

1

2j=5

满足1<k<j的有k=2，3，4；

k=2:“p1”=“a”等于“p4”=“a”

k=3:“p1p2”=“ab”不等于“p3p4”=“aa”,

k=4:

“p1p2p3”=“aba”不等于“p2p3p4”=“baa”,next[5]=2

j12345678模式串

abaabcacnext[j]0112

2

3j=6

满足1<k<j的有k=2，3,4，5；

k=2:“p1”=“a”不等于“p5”=“b”

k=3:

“p1p2”=“ab”等于“p4p5”=“ab”,

k=4：“p1p2p3”=“aba”不等于“p3p4p5”=“aab”,

k=5:

“p1p2p3p4”=“abaa”不等于“p2p3p4p5”=“baab”,

next[6]=3j=7

时满足1<k<j的有k=2，3,4，5，6；

k=2:“p1”=“a”不等于“p6”=“c”

k=3:“p1p2”=“ab”不等于“p5p6”=“bc”,

k=4：“p1p2p3”=“aba”不等于“p4p5p6”=“abc”,

k=5:“p1p2p3p4”=“abaa”不等于“p3p4p5p6”=“aabc”,

k=6:“p1p2p3p4p5”=“abaab”不等于“p2p3p4p5p6”=“baabc”,

next[7]=1

j12345678模式串

abaabcacnext[j]011223

1j=8

时满足1<k<j的有k=2，3,4，5，6，7；

k=2:"p1"="a"等于

"p7"="a"

k=3:"p1p2"="ab"不等于"p6p7"="ca",

k=4："p1p2p3"="aba"不等于"p5p6p7"="bca",

k=5:"p1p2p3p4"="abaa"不等于"p4p5p6p7"="abca",k=6:“p1p2p3p4p5”=“abaab”不等于"p3p4p5p6p7"="aabca",k=7:"p1p2p3p4p5p6"="abaabc"不等于"p2p3p4p5p6p7"="baabca",

next[8]=2

j12345678模式串

abaabcacnext[j]01122312[问题1]已知next[j]后，INDEX(s,p)算法的实现(1)：当Si

=Pj

或j=0时，则i++；j++；(2)：当Si≠Pj

时，i不变，让j=next[j]，转到(1)；a

c

abaabca

a

baabcac例：主串S=“acabaabcaabaabcac”

，

模式串T=“abaabcac”a

b

(∵j=2,∴让j=next[2]=1)i=2a

(∵j=1,∴让j=next[1]=0，下次让i++，j++(=1)；)abaabcac

(∵j=8，∴让j=next[8]=2)i=3

i=10

(a)

b

(∵j=2，∴让j=next[2]=1)abaabcac改进算法(KMP算法)：int

index_kmp(SSring

S，SStringT)//利用模式串t的next函数值求T在主串S中首次出的位置{i=1；j=1；while(i≤S[0]&&j≤T[0])

if(j==0

||

S[i]==T[j]){i++；j++};elsej=next[j]；if(j>T[0])

return(i-T[0])；elsereturn(0)}//index_kmp

(1)由定义得知next[1]=0(2)

已知

next[j]=k，如何求next[j+1]?

由于next[j]=k，则有下面的等式成立：

“p1…pk-1”=“pj-k+1…pj-1”

①若

pk=pj

则有：“p1…pk”=“pj-k+1…pj”

next[j+1]=next[j]+1=k+1p1p2……pk-1

……

pj-k+1……pj-1

pj

pj+1……pn[问题2]

如何求next[j]函数：(b)

若

pk≠pj

，

则将求函数next的问题看成是一个模式匹配的过程。由于已有“p1…pk-1”=“pj-k+1…pj-1”则当pj

≠pk时，将模式串向右滑动，使第next[k]个字符和主串中的第j个字符相比较。若next[k]=k´，且pj=pk´

则：next[j+1]=k´+1=next[k]+1若pj

≠pk´，则使第next[k´]个字符和pj对齐，…依此类推。S1S2……Si-j+1……Si-j+k-1……Si-k+1……Si-1

Si…

≠

P1P2……Pk-1

……

Pj-k+1……Pj-1

Pj

≠

k=next[j]

P1……Pk-1

Pk

当Pj≠Pk时，Pj应与那一个P比较？设与Pk’比较：则P1P2……Pk-1

……

Pj-kj+1……Pj-1

Pj

P1………Pk’-1

Pk’

即：k’=next[k]voidget_next(Sstring

T，int&next[])//求模式串T的next值并存入数组next[1..T[0]]中{

j=1；k=0；next[j]=k；//初始化while(j<T[0])

if(T[j]==T[k]||k==0)

{

k++；j++；

next[j]=k；//next[j+1]=k+1

}elsek=next[k];}//get_next

j12345678模式串

abaabcacnext[j]①初始化：k=0，j=1，

next[1]=0；②∵k=0,∴k++后k=1，j++后

j=2，next[2]=1③

∵t[2]≠t[1],∴k=next[k]=0，∴k++后k=1，j++(3),

next[3]=1④∵t[3]=t[1],∴k++后k=2，j++后

j=4,next[4]

=2⑤∵t[4]≠t[2],∴k=next[k]=1,∵t[4]=t[1],∴k=2，j=5,next[5]=2⑥∵t[5]=t[2],∴k++后k=3，j++后j=6,next[6]=3⑦∵t[6]≠t[3],∴k=next[k]=1,即：k=1，∵t[6]≠t[1]

,

∴k=next[k]=next[1]=0

，∵

k=0,

∴k=1，j=7,next[7]=1⑧∵t[7]=t[1],∴k++后k=2，j++后

j=8，

next[8]

=201122312前面定义的next函数尚有缺陷。例如：

j12345模式串：

aaaab

next[j]01