2015秋数据结构课程-第4章

第4章

串2015/9/20工业大学测绘学院slide2第4章串学习目标理解串的基本操作的定义，并能利用这些基本操作来实现串的其它

的方法。的方法。熟练掌握在串的顺序

结构上实现串的了解串操作的应用方法和特点。串的模式匹配。2015/9/20工业大学测绘学院slide3第4章串本章主要内容4.1

串的逻辑结构4.2

串的表示4.3

串的模式匹配算法2015/9/20工业大学测绘学院slide4第4章串4.1串的逻辑结构串：零个或多个字符组成的有限序列。串的长度：串中所包含的字符个数。空串：长度为0的串，记为：“”。非空串：通常记为：s=‘a1a2a3……an’其中s是串

引号或双引号是定界符，引号 是串值，a1是一个任意字符。字符集：ASCII码，扩展ASCII码，Unicode，UTF-8等。子串：串中任意个连续的字符组成的子序列。子串的位置：子串的第一个字符在主串中的序号。2015/9/20工业大学测绘学院slide5第4章串4.1串的逻辑结构（

Cont.）串相等：两个串相等，当且仅当这两个串的值相等。即，只有当两个串的长度相等，并且各个对应位置的字符都相等时才相等。串的比较：给定2个串：s=‘a1a2……an’,t=‘b1b2……bm’,当满足以下条件之一时，s<t。1.存在某个k≤min(n,m),使得ai=bi(i=1,2,……,k-1)，且ak<bk例如s=‘happen’,t=‘happy’2.n<m,且ai=bi(i=1,2,……,n)例如s=‘hap’,t=‘happy’2015/9/20工业大学测绘学院slide6第4章串4.1串的逻辑结构（

Cont.）串的特点：串的逻辑结构和线性表极为相似，区别仅在于串的数据对象约束为字符集。串的基本操作和线性表有很大差别。性表的基本操作中，大多以“单个元素”作为操作对象。而在串的基本操作中，通常以“串的整体”作为操作对象，如：在串中找某个子串，求取一个子串，在串的某个位置上

一个子串以及删除一个子串等。2015/9/20工业大学测绘学院slide7第4章串4.1串的逻辑结构（

Cont.）串的抽象数据类型：ADT

String

{数据对象：D

＝

{

ai

|

ain≥0

}数据关系：R1＝{<ai-1,

ai基本操作：……}∈CharacterSet,

i=1,2,...,n,>|

ai-1,

ai∈D,

i=2,...,n}2015/9/20工业大学测绘学院slide8第4章串4.1串的逻辑结构（

Cont.）串的基本操作：StrAssign

(&T,

chars)DestroyString(&S)StrCopy

(&T,

S)StrLength(S)pare

(S,

T)Concat

(&T,

S1,

S2)SubString(&Sub,S,pos,len)StrEmpty

(S)ClearString

(&S)Index

(S,

T,

pos)Replace

(&S,

T,

V)StrInsertT)StrDeletelen)(&S,

pos,(&S,pos,2015/9/20工业大学测绘学院slide9第4章串4.2

串的表示串的块链

表示串的堆分配串的定长顺序 表示顺序表示链式2015/9/20工业大学测绘学院slide10第4章串4.2

串的定长顺序存储#define

MAXSTRLEN

255//用户可在255以内定义最大串长typedef

unsigned

char

sString

[MAXSTRLEN

+

1];用一组地址连续的

单元

串值的字符序列。按照预定义的大小，为每个定义的串变量分配一个固定长度的 区，可用定长数组描述。用sString[0]来存放串长信息。串值后面加一个不计入串长度的标识符‘\0’。串的实际长度可在予定义长度的范围内随意,超过预定义长度的串值则被舍去，称为“截断”。2015/9/20工业大学测绘学院slide11第4章串4

.

2

串的定长顺序

（

Cont.）例

：

用

顺

序

方

式

实

现

求

子

串

函

数SubString(&Sub,s,pos,len)将串S中从第pos个字符开始长度为len的字符序列到Sub中（注：串Sub的预留长度与S一样）Status

SubString(SString

&Sub,SString

s,int

pos,int

len)=

S[pos…pos+len-1]S

=

‘a1a2……an-1

an’pos

lenSub[1…len]Sub[0]=len;Retrun

OK:{}If(pos<1||pos>S[0]||len<0||len>S[0]-pos+1)Return

error;想存放超长字符串怎么办？改用动态分配的一维数组2015/9/20工业大学测绘学院slide12第4章串4.2

串的堆分配串的堆分配符序列，但：仍以一组地址连续的 单元存放串值字空间是在程序执行过程中动态分配而得。typedef

struct

{char

*ch;//若是非空串，则按串实用长度分配//

区，否则

ch

为NULLint

length;

//串长度}HString;2015/9/20工业大学测绘学院slide13第4章串4.2

串的堆分配例：用堆分配 方式实现串（

Cont.）操作2015/9/20工业大学测绘学院slide14第4章串4.2

串的块链结构来

串串—用非压缩形式：abg∧sefg#∧压缩形式：sabcd密度=串值所占

位实际分配的

位2015/9/20工业大学测绘学院slide15第4章串4.2

串的块链（

Cont.）结构定义：串的#definetypedefchar//可由用户定义的块大小//结点结构CHUNKSIZE

80struct

Chunk

{ch[CHUNKSIZE];struct

Chunk}Chunk;typedef

struct

{*next;//串的链表结构Chunk

*head,*tail;//串的头和尾指针int

curlen;

//串的当前长度}LString;2015/9/20工业大学测绘学院slide16第4章串4.2

串的模式匹配模式匹配：给定主串s=“s1s2…sn”和模式t=“t1t2…tm”，在s中寻找t的过程称为模式匹配。如果匹配成功，返回t在s中的位置，如果匹配失败，返回0。是串的一种重要操作，很多

，若有“编辑”菜单项的话，则其中必有“查找”子菜单项。2015/9/20工业大学测绘学院slide17第4章串4.2

串的模式匹配（

Cont.）朴素模式匹配算法(Brute-Force算法)：基本思想：从主串s的第一个字符开始和模式t的第一个字符进行比较，若相等，则继续比较两者的后续字符；否则，从主串s的第二个字符开始和模式t的第一个字符进行比较；重复上述过程，直到t中的字符全部比较完毕，则说明本趟匹配成功；或s中字符全部比较完，则说明匹配失败。2015/9/20工业大学测绘学院slide18第4章串4.2

串的模式匹配（

Cont.）a

b

ca

c第4趟匹配：a

b

a

b

c

a

b

c

a

cb

aba第5趟匹配：a

b

a

b

c

a

b

c

a

cb

aba第6趟匹配：a

b

ab

c

a

bc

ac

b

aba

bc

a

c设主串S=‘ababcabcacbab’，模式串T=‘abcac’第1趟匹配：a

b

a

b

c

a

b

c

a

cb

aba

bc第2趟匹配：a

b

a

b

c

a

b

c

a

cb

aba第3趟匹配：a

b

a

b

c

a

b

c

a

c

b

a

特点：主串指针需回溯，模式串指针需复位。2015/9/20工业大学测绘学院slide19第4章串4.2

串的模式匹配（

Cont.）Brute-Force算法实现的详细步骤：在串s和串t中设比较的起始下标i和j；循环直到t或t的所有字符均比较完；如果s[i]=t[j]，继续比较s和t的下一个字符；否则，将i和j回溯，准备下一趟比较；如果t中所有字符均比较完，则匹配成功，返回匹配的起始比较下标；否则，匹配失败，返回0；2015/9/20工业大学测绘学院slide20第4章串4.2

串的模式匹配（

Cont.）Brute-Force算法的时间复杂度：假设主串s

长n,模式串t

长m

。可能匹配成功的位置（1~n-m+1）。最好情况下，模式串的第1个字符失配设匹配成功在s的第i个字符，则i-1趟匹配比较了i-1次，第i趟成功匹配共比较了m次，总共比较了（i-1+m）次。所有匹配成功的可能共有n-m+1种，所以在等概率情况下的平均比较次数：最好情况下算法的平均时间复杂度O(n+m)。2015/9/20工业大学测绘学院slide21第4章串4.2

串的模式匹配（

Cont.）Brute-Force算法的时间复杂度：的情况下，模式串的最后1个字符失配设匹配成功在s的第i个字符，则

i-1趟匹配 比较了(i-1)*m次，第i趟成功匹配共比较了m次，总共比较了(i*m)次。共需要