数据结构课件第4章

第4章串内容4.1串的类型定义

4.2串的表示和实现

4.3串的模式匹配算法

4.4串操作应用举例●基本要求：

1）了解串的概念、逻辑结构、存储结构；

2）掌握串的表示与实现方法；

3）掌握串的模式匹配算法；

4）学会串的正确应用；●学习重点：

1）串的表示与实现方法；

2）串的模式匹配算法；4.1串的类型定义4.1.1

串的基本概念

术语：1）串名：S.2）串值：'a1a2···an'，ai(1≤i≤n).3）串的长度：串中所包含的字符个数，如串

‘abcde’的长度为5.4）空串：长度为0(n=0)的串，它不包含任何

字符，记作S=''(或S=φ).定义：串是由零个或多个任意字符组成的字符序列。一般记作：s='a1a2...an'(n>=0)

4.1串的类型定义4.1.1

串的基本概念

术语：5）空格串：由空格符(ASCII值32)组成的串，如S=‘’.注意S=‘’与S=‘’不

同，前者是长度为1的非空串，它含有

一个空格字符，而后者是长度为0的空

串。

6）子串：串中任意个连续的字符组成的子序

列。比如'abcde'中的'bcd'.4.1串的类型定义4.1.1

串的基本概念

用二元组的形式来定义串：串是一个二元组,

string=(D,R)其中，D={ai|ai∈字符集,i=1,2,···,n,n≥0}R={N}

有序偶的集合N={<ai-1,ai>|ai-1,ai∈D,i=2,3,···n}

故串的逻辑结构和线性表极为相似。区别仅在D的定义上。线性表的数据对象可以是任意数据类型，而串的数据对象是字符集。4.1串的类型定义4.1.2

串的ADT定义

ADTString{数据对象：D={ai|ai(-CharacterSet,i=1,2,...,n,n>=0}数据关系：R1={<ai-1,ai>|ai-1,ai(-D,i=2,...,n}基本操作：StrAssign(&T,chars)//chars是字符常量。生成一个其值//等于chars的串T。StrCopy(&T,S)//串S存在则由串S复制得串TStrEmpty(S)//串S存在则若S为空串,返回真否则返回假pare(S,T)//串S和T存在,若S>T,则返回值大于0,//若S=T,则返回值=0,若S<T,则返回值<04.1串的类型定义4.1.2

串的ADT定义

StrLength(S)//串S存在,返回S的元素个数称为串的长度.

ClearString(&S)//串S存在,将S清为空串

Concat(&T,S1,S2)//串S1和S2存在,用T返回由S1和S2联接

//而成的新串

SubString(&Sub,S,pos,len)//串S存在,求从位置pos开始//长度为len的子串

//1<=pos<=StrLength(S)且0<=len<=StrLength(S)-pos+1

Index(S,T,pos)//串S和T存在,T是非空。1<=pos<=StrLength(S)

//若主串S中存在和串T值相同的子串,则返回它在主串S中

//第一次出现的位置,否则函数值为0

Replace(&S,T,V)//串S,T和V存在,T是非空串,用V替换主串S中

//出现的所有与T相等的不重叠的子串

StrInsert(&S,pos,T)//串S和T存在,1<=pos<=StrLength(S)+1,//在串S的第pos个字符之前插入串T

StrDelete(&S,pos,len)//串S存在,1<=pos<=StrLength(S)-//len+1从串中删除第pos个字符起长度为len的子串

DestroyString(&S)//串S存在,则串S被销毁}ADTString4.1串的类型定义4.1.2

串的ADT定义

返回目录用一组地址连续的存储单元来存储串的字符序列。每个字符占用一个字节（Byte）。串中相邻的字符顺序地存放在相邻的字节中。4.2串的表示和实现4.2.1

串的定长顺序存储表示

DATASTRUCTURES11+11+21+15······图4.1串的顺序存储结构定长顺序存储结构串定义：#definemaxlen255//允许最大的长度typedefunsignedcharString[maxlen+1];//下标0的位置存放长度实现：串的联接函数、求子串的函数、求子串位置的定位函数1、串的联接函数Concat(L,s,t)4.2串的表示和实现4.2.1

串的定长顺序存储表示

其中，L,s,t是String；

[分析]相当于求L=s+t，若s与t连接后的串值长度超过maxlen，则超过部分将被截断。运算结果有三种可能情况。

1)length(s)+length(t)≤maxlen

Length(s)Length(t)s.cht.chL.chLength(L)maxlen图4.2串的联结操作示意图（1）1、串的联接函数Concat(L,s,t)4.2串的表示和实现4.2.1

串的定长顺序存储表示

2)length(s)+length(t)>maxlen，而length(s)<maxlen需将t的一部分截断，所得串L中包含s的全部与t的一个子串图4.3串的联结操作示意图（2）Length(s)Length(t)s.cht.chL.chmaxlent中被截去的字符序列Length(L)1、串的联接函数Concat(L,s,t)4.2串的表示和实现4.2.1

串的定长顺序存储表示

3)length(s)=maxlen得到的串L是s的串。图4.4串的联结操作示意图（3）Length(s)Length(t)s.cht.chL.chmaxlent串被全部截去Length(L)1、串的联接函数Concat(L,s,t)4.2串的表示和实现4.2.1

串的定长顺序存储表示

4)函数实现StatusConcat(string&L,strings,stringt){/*返回s和t联接的结果，s和t的值不变。*/switch{caselength(s)+length(t)≤maxlen://正常联接

L[1..length(s)]=s[1..length(s)];L[length(s)+1..length(s)+length(t)]=t[1..length(t)];L[0]=s[0]+t[0];overflow=false;1、串的联接函数Concat(L,s,t)4.2串的表示和实现4.2.1

串的定长顺序存储表示

4)函数实现caselength(s)<maxlen://串t截尾

overflow=true;L[1..length(s)]=s[1..length(s)];L[length(s)+1..maxlen]=t[1..maxlen–length(s)];L[0]=maxlen;default://串中只含soverflow=true;L[1..maxlen]=s[1..maxlen];L[0]=maxlen;}//switchreturnoverflow;}//Concat●

用堆结构存储串值4.2串的表示和实现4.2.2

串的堆分配存储表示

特点：每个串的串值各存储在一组地址连续的存储单元中，但它们的存储地址是在程序执行过程中动态分配而得。

typedefstruct{ char*ch; intlength; }HString;使用时必须分配(malloc)和回收(free)内存。4.2串的表示和实现4.2.2

串的堆分配存储表示

●

用堆结构存储串值定义HStrings1HStrings2s1s2lengthch2115

···ASTRINGOFLENGTH21F···DATASTRUCTURES

···HeapFreeFree是尚未分配的内存首地址图4.5串的动态分配存储结构示意图4.2串的表示和实现4.2.2

串的堆分配存储表示

●

联接运算ConcatStatusConcat(HString&t,HStrings1,HStrings2){

//连接s1,s2到t中

if(t.ch)free(t.ch);//释放原空间

if(!(t.ch=(char*)malloc(s1.length+s2.length)*sizeof(char))))

returnOVERFLOW;

//分配空间

t.ch[0..s1.length-1]=s1.ch[0..s1.length-1];

//处理s1

t.length=s1.length+s2.length;

//长度

t.ch[s1.length..t.length-1]=s2.ch[0..s2.length-1];

//s2}4.2串的表示和实现4.2.3

串的块链存储表示

●

用线性链表的方式存储串值结点大小问题？^H优点：便于实现插入、删除等操作缺点：浪费存储空间，存储利用率最多1/21）结点大小等于1，即一个结点存放1个字符DATAS^head······图4.6串值的链表存储方式（结点大小为1）4.2串的表示和实现4.2.3

串的块链存储表示

●

用线性链表的方式存储串值结点大小问题？^H优点：存储效率较高缺点：实现插入、删除等操作较复杂2）结点大小等于4，即一个结点存放4个字符DATASTRUCTURES^head图4.7串值的链表存储方式（结点大小为4）4.2串的表示和实现4.2.3

串的块链存储表示

●

用线性链表的方式存储串值

为便于进行串的操作，当以链表存储串值时，给出头、尾指针，加当前串的长度。称如此定义的串存储结构为块链结构。

设尾指针的目的是为了便于进行联接操作。clst15DATASTRUCTURES#^头尾长度图4.8块链结构示意图4.2串的表示和实现4.2.3

串的块链存储表示

●

用线性链表的方式存储串值//－－－－－－－串的块链存储表示－－－－－－－#defineCHUNKSIZE80//用户定义的结点大小typedefstructchunk{charch[CHUNKSIZE];//块大小

structchunk*next;//指针}chunk;typedefstruct{chunk*head，*tail;//串的头、尾指针

intlength;

//串的当前长度}LString;LStringclst;模式匹配算法，其中p为模式设有两个串

s='s1s2···sn'p='p1p2···pm'(0<m≤n)称主串S为目标（串），子串p为模式（串）。串的模式匹配：在目标S中寻找模式为p的子串的过程.串模式匹配的结果：（1）成功，Index(S,p)>0

（2）失败，Index(S,p)==0其中Index返回第一个模式为p的子串在主串s中的位置。4.3串的模式匹配算法4.3.1

求子串位置的定位函数

Index(s,p)

使用串的基本操作(如Equal，Length，Substr等)实现求子串位置的定位函数Index(s,p)的算法：intIndex(strings,stringp){n=Length(S);m=Length(p);i=1;while(i≤n–m+1)if(Equal(Substr(S,i,m),p))returni;elsei++;return0;}

//index4.3串的模式匹配算法4.3.1

求子串位置的定位函数

Index(s,p)

例：主串S:“acabaabaabcacaabc”模式串t:“abaabcac”简单的模式匹配算法（BF算法）s：acabaabaabcacaabct：abaabcaci=1j=1s：acabaabaabcacaabct：abaabcaci=2j=1if（s[i]==t[j]）{i++；j++；}if（s[i]！=t[j]）

{i回溯到本趟开始的下一个；

j回溯到1；}算法思想：s：acabaabaabcacaabct：abaabcaci=2j=1s：acabaabaabcacaabct：abaabcaci=3j=1i=4j=2i=5j=3i=6j=4i=7j=5i=8j=6s：acabaabaabcacaabct：abaabcaci=4j=1s：acabaabaabcacaabct：abaabcaci=5j=1i=6j=2s：acabaabaabcacaabct：abaabcaci=6j=1i=7j=2i=8j=3i=9j=4i=10j=5i=11j=6i=12j=7i=13j=8i=14j=9（2）