数据结构与算法4-串

4.2串及其运算4.3串的存储结构及实现第4章串4.4串的模式匹配4.1应用实例4.5实例分析与实现4.6算法总结数据结构与算法4-串全文共25页，当前为第1页。4.1应用实例应用实例：文本编辑软件文本编辑程序是利用计算机进行文字加工的基本软件工具，实现对文本文件的插入、删除等修改操作，甚至用于报刊和书籍的编辑排版。常用的简单文本编辑程序Edit，和文字处理软件WPS、Word等，究其实质，都是修改字符数据的形式或格式。可用于文本编辑的程序很多，功能不同且强弱差别很大，但基本操作是一样的，一般都包含串的查找、插入和删除等基本操作。数据结构与算法4-串全文共25页，当前为第2页。4.2串及其运算是由零个或多个字符组成的有限序列。

S=a0a1a2…an-1

(n≥0)子串：第4章串串中任意个连续的字符组成的子序列。主串：包含子串的串相应地称为主串。位置：字符在序列中的序号。子串在主串中的位置则以子串的第一个字符在主串中的位置来表示。相等：两个串的长度相等，并且对应位置的字符都相等。空串与空白串数据结构与算法4-串全文共25页，当前为第3页。串的抽象数据类型的定义第4章串ADTString{

数据元素：D={ai|ai∈CharacterSet,记为V,i=1,2,…，n;n≥0}

数据关系：R＝｛<ai,ai+1>|ai,ai+1∈V，i=1,2,…,n-1;n-1≥0

｝

基本操作：

（1）StrAssign(S,chars)

（2）StrInsert(S,pos,T)

（3）StrDelete(S,pos,len)

………p106}ADT

String4.2串及其运算数据结构与算法4-串全文共25页，当前为第4页。基本操作：第4章串StrInsert(S,pos,T)初始条件：串S和T存在，1≤pos≤StrLength(S)+1。

操作结果：在串S的下标为pos的字符之前插入串T。StrInsert(S,pos,T)例如：S=chater，T=rac，则执行StrInsert(S,3,T)之后S=

character4.2串及其运算数据结构与算法4-串全文共25页，当前为第5页。基本操作：第4章串StrDelete(S,pos,len)初始条件：串S存在1≤pos≤StrLength(S)+1。

操作结果：从串S中删除下标为pos的字符起长度为len的子串。

StrDelete(S,pos,len)例如：S=character，则执行StrDelete(S,3,3)之后S=chater4.2串及其运算数据结构与算法4-串全文共25页，当前为第6页。基本操作：第4章串StrCat(S,T)初始条件：串S和T存在。

操作结果：返回由S和T联接而成的新串。StrCat(S,T)例如：StrCat(man,kind)=mankind4.2串及其运算数据结构与算法4-串全文共25页，当前为第7页。基本操作：第4章串SubString(Sub,S,pos,len)初始条件：串S存在，1≤pos≤Length(S)

且0≤len≤Length(S)-pos+1。操作结果：用Sub返回串S的第pos个字符起长度为len的子串。SubString(Sub,S,pos,len)例如：SubString(sub1,commander,4,3)sub1=manSubString(sub2,

commander,4,7)sub2=?SubString(sub3,beijing,7,2)=?sub3=?起始位置和子串长度之间存在约束关系!4.2串及其运算数据结构与算法4-串全文共25页，当前为第8页。基本操作：第4章串StrIndex(S,pos,T)

初始条件：主串S和T存在，T是非空串操作结果：若主串S中存在和串T值相同的子串,则返回它在主串S中从第pos个字符开始第一次出现的位置；否则函数值为0。StrIndex(S,pos,T)例如：S=abcaabcaaabc,T=bcaStrIndex(S,1,T)=2StrIndex(S,4,T)=64.2串及其运算数据结构与算法4-串全文共25页，当前为第9页。基本操作：第4章串StrReplace(S,T,V)

初始条件：串S,T和V均已存在，且T是非空串。操作结果：用V替换主串S中出现的所有与（模式串）T相等的不重叠的子串。StrReplace(S,T,V)例如：S=abcaabcaaabca,T=bca,V=xS=axaxaax给出一个由小写字母组成的串s和一个不超过s的长度的正整数l，求s所有长度不小于l的子串在s中不重叠地重复出现次数最多的子串。4.2串及其运算数据结构与算法4-串全文共25页，当前为第10页。对于串的基本操作集可以有不同的定义方法，在使用高级程序设计语言中的串类型时，应以该语言的参考手册为准。基本操作第4章串4.2串及其运算数据结构与算法4-串全文共25页，当前为第11页。①定长顺序串4.3串的存储及实现常用的实现方法：第4章串②堆串③块链串数据结构与算法4-串全文共25页，当前为第12页。①定长顺序串常用的实现方法：第4章串存储表示：静态数组结构#defineMAXLEN40typedefstruct{charstr[MAXLEN];intlength;}SString;4.3串的存储及实现数据结构与算法4-串全文共25页，当前为第13页。①定长顺序串常用的实现方法：第4章串基本操作：

插入、删除、复制、判空、比较、求串长、清空、连接、求子串。参见P78~80页4.3串的存储及实现数据结构与算法4-串全文共25页，当前为第14页。②堆串常用的实现方法：第4章串存储表示：

动态地分配一组地址连续的存储单元。typedefstruct{char*ch;intlen;}HString;4.3串的存储及实现数据结构与算法4-串全文共25页，当前为第15页。poolelpmasNAMEINFORMATION•,6•,4pool4elpmas6NAMEINFORMATION••数据结构与算法4-串全文共25页，当前为第16页。②堆串常用的实现方法：基本操作：

赋值、插入、删除。参见P81~82页4.3串的存储及实现数据结构与算法4-串全文共25页，当前为第17页。③块链串常用的实现方法：第4章串存储表示：可用链表来存储串值，由于串的数据元素是一个字符，它只有8位二进制数，因此用链表存储时，通常一个结点中存放的不是一个字符，而是一个字符串。#defineBLOCK_SIZE4

typedefstructBlock

{charch[BLOCK_SIZE];

structBlock

*next;

}Block;

typedefstruct{

Block*head,*tail;

intcurlen;

}BLString;4.3串的存储及实现数据结构与算法4-串全文共25页，当前为第18页。4.4简单的行编辑器

整个文本编辑区可以看成是一个字符串，称为文本串。每一页是文本串的一个子串，每一行是每一页的一个子串，即:同一行的串用定长结构(80个字符),行和行之间用行指针相链接，页和页之间用页指针相链接。数据结构与算法4-串全文共25页，当前为第19页。4.5串的模式匹配算法首先，回忆一下串匹配(查找)的定义:StrInex(S,pos,T)初始条件：主串S和T存在，T是非空串并且1≤pos≤Length(S)。

操作结果：若主串S中存在和串T值相同的子串,则返回它在主串S中从第

pos个字符开始第一次出现的位置；

否则函数值为0。数据结构与算法4-串全文共25页，当前为第20页。“子串在主串中的位置”意指子串中的第一个字符在主串中的位序。例如：S=abcaabcaaabc,T=bcaStrInex(S,1,T)=StrInex(S,4,T)=624.5串的模式匹配算法数据结构与算法4-串全文共25页，当前为第21页。下面讨论以定长顺序结构表示串时的几种算法。①简单匹配算法（Brute-Force）②首尾匹配算法③KMP(D.E.Knuth,J.H.Morris,V.R.Pratt)算法4.5串的模式匹配算法数据结构与算法4-串全文共25页，当前为第22页。*4.4串的模式匹配算法①简单匹配算法（Brute-Force）intStrIndex(SStrings,intpos,SStringt){ inti,j,start; if(t.len==0) return(0);

start=pos;

i=start;

j=0; while(i<s.len&&j<t.len)

if(s.ch[i]==t.ch[j]) {

i++;

j++;

} else {

start++;

i=start;

j=0;

} if(j>=t.len) return(start);

else

return(-1);}数据结构与算法4-串全文共25页，当前为第23页。②首尾匹配算法先比较模式串中的第一个字符再比较模式串中的最后一个字符最后比较模式串中从第二个到第n-1个字符4.5串的模式匹配算法数据结构与算法4-串全文共25页，当前为第