配套资源下载
第4章串
4.1应用实例
文本编辑器
4.2串及其运算
4.2.1串的基本概念
1.串的概念
串（string）是由零个或多个字符组成的有限序列，一般记作：S=‘a1a2a3…an’
其中
（1） S 为串的名字
（2）单引号括起来的字符串序列为串的值；将串值括起来的单引号本身不属于串，它的作用是避免串与常数与标识符混淆
（3）an（1≤i≤n）可以是字母、数字或其他字符
（4）n为串中字符的字数，称为串的长度。
2.常用术语
①空串
②空格串
③子串
④主串
⑤前缀子串
⑥后缀子串
⑦位置
⑧串相等
⑨模式匹配
4.2.2 串的基本运算
1.串的抽象数据类型定义
串的抽象数据类型定义如下。
ADT String{
数据对象:D={ai,lai∈CharacterSet,i=1,2,…,n,n>0}
数据关系:R={<ai-1|a,>lai-1,ai∈D,i=2,3,n}
基本操作:
(1) StrAssign(S,chars)
初始条件:chars是字符串常量。
操作结果:生成一个串S,并使其串值等于chars。
(2)StrCopy(S.T)
初始条件:串T存在
操作结果:将串T的值献给串S
(3) StrLength(S)
初始条件:串S存在
操作结果:返回串S的长度,即串S中字符的个数
(4) Strlnsert(S,pos,T)
初始条件:串S和T存在,I≤pos≤StrLength(S)+1
操作结果:在串S的第pos个字符之前插入串T
(5) StrDelete(S.pos,len)
初始条件:串S存在,1≤pos≤Strlength(S),且0≤len≤Sulengh(S)-pos+l
操作结果:在串S中删除从第pas个字符开始连续len个字符后形成的子串,
(6) StrCompare(S,T)
初始条件:串S和T存在。
操作结果:若串S和串了相等,则返回值等于0;否则返回串S和串下第一个不相等字符的ANSI码值之差
(7) StrCat(S,T)
初始条件:串S和T存在。S足够长
操作结果:将串T的值连接在串S的后面。
(8) SubString(T,S.pos.len）
初始条件:串S存在,1≤lpos≤StrLength(S),且0≤lensStrLength(S)-pos+1
操作结果:截取串S中从第pos个字符开始连续len个字符形成的子串,并赋值给串T,
(9) StrIndex(S,pos, T)
初始条件:串S和T存在,1≤pos≤StrLength(S):
操作结果:若串S中从第pos个字符后存在与串T相等的子串,则返回串T在申S中第pos个字符后首次出现的位置;否则返回0。
(10) StrReplace(S,T,V)
初始条件;串S、串T和串V存在,且串T是非空申。
操作结果:用串V替换串S中出现的所有与串T相等的不重叠的子串。
(11) StrEmpty(S)
初始条件:串S存在。
操作结果:若串S为空串,则返回TRUE;否则返回FALSE
(12) StrClear(S)
初始条件;串S存在
操作结果:将S清为空串，
(13) StrDestroy(S)
初始条件;串S存在
操作结果:销毁串S
}ADT Siring
2. 串的基本运算示例
4.3串的存储结构及实现
4.3.1 定长顺序串
1.定长顺序串存储结构
定长顺序串存储结构如下:
#define MAXLEN 50//字符串的最大长度 typedef struct{ char ch[ MAXLEN+1];//存储字符串的一维数组,每个分量存储一个字符,第0号单元不使用 int len;//字符串的长度 }SString;
串的实际长度可在预定义长度MAXLEN的范围内随意变动,超过MAXLEN,串值被舍去,称为“截断”
4.3.2 堆串
1.堆串存储结构
typedef struct{ char * ch;//若是非空串,则指向串的起始地址;否则ch为NULL int len;//字符串的长度 }HString;
为了便于理解和讨论,这里在给串分配存储空间时,在实际串长的基础上多分配一个存储间，且连续空间的第0号单元不使用。
4.3.3 块链串
4.3.3块链串
由于串是一种符殊的线性表,所以存储字符串的串值除了可以采用顺序存储结构，也可以用链式存储结构。
在串的链式存储结构中，链表的每个结点既可以存放一个字符,也可以存放多个字符，每个结点称为“块”,整个链表称为“块链结构”。
块链串存储结构如下:
#define BLOCK_SIZE 4//每个结点存放字符个数为4 typedef struct block{ char ch[ BLOCK_SIZE]; struet block * next; } Block; typedef struct{ Block * head;//块链串的头指针 Block * lail;//块链串的尾指针 int len;//字符串长度 }LString;
4.4串的模式匹配
4.4.1 BF模式匹配算法
蛮力匹配
4.4.2 KMP模式匹配算法
[KMP算法思想]Knuth-Mrris-Pratt算法(简称KMP),是由D.E.Knuth.JHMorris和VR.Pratt共同提出的一个改进算法。KMP算法是模式匹配中的经典算法，和BF算法相比，KMP算法的不同点是消除BF算法中主串S指针回溯的情况，从而完成串的模式匹配，这样的结果使得算法的时间复杂度为O(n+m)。
[KMP算法描述]KMP算法每当一趟匹配过程中出现字符比较不等时，主串S中的i指针不需回溯，而是利用已经得到的“部分匹配”结果将模式向右“滑动”尽可能远的一段距离后，继续进行比较。
回顾图4.5的匹配过程示例，在第三趟的匹配中，当i=7、j=5字符比较不等时，又从i4、j=1重新开始比较。然后，经过仔细观察可发现，在i=4和j=1，i=5和j=1以及i=6和j=1这三次比较都是不必进行的。因为从第三趟部分匹配的结果就可得出，主串中第4、5、6个字符必然和模式串中的第2、3、4个字符相等，即都是"b’、'c、‘a’。因为模式串中的第一个字符是’a，因此它无需再和这三个字符进行比较，而仅需将模式串向右滑动三个字符的位置继续进行i=7、j=2时的字符比较即可。同理，在第一趟的匹配中出现字符不等时，仅需将模式向右移动两个字符的位置进行i=3、j=1时的字符比较。因此，在整个匹配的过程中，i指针没有回溯，如图4.7所示。
一般情况下，假设主串为’S1S2…Sn’,模式串为’T1T2…Tn’，从上例的分析可知，为了实现KMP算法，需要解决以下问题，当匹配过程中产生“失配”(即Si≠Ti)时，模式串“向右滑动”可滑动的距离有名远，也就是说，当主串中字符Si,与模式串中字符Tj"失配”时，主串中字符Si( i 指针不回溯)应与模式串中哪个字符再进行比较?
假设此时主串中字符Si应与模式中字符Tk(k<j)继续进行比较，则主串S和模式串T满 如下关系。
S=S1S2…Si-j+1Si-j+2…Si-k+1…Si-1Si …Sn
T= T1 T2 …Tj-k+1…Tj-k+2…
T= T1 …Tk-1…
可以看出，若模式串中存在’T1T2…Tk-1’=‘Tj-k+1Tj-k+2…Tj-1’,且满足1<k<j，则当匹配过程中Si≠Tj 时，仅需将模式串向右滑动至第k个字符和主串中第i个字符对齐，匹配仅需从Si、Tk的比较起继续进行，无需i指针的回溯。在匹配过程中为了尽可能“滑动”远一段的距离，因而应选择满足条件较大的k值。
若令next[j]=k，则next[]表明当模式中第j个字符与主串中相应字符“失配”时，在模式中需重新和主串中该字符进行比较的字符的位置。由此可引出模式串的next函数的定义:
由此可见next函数的计算仅和模式串本身有关，而和主串无关。其中’T1T2…Tk-1’是’T1T2…Tj-1‘’ 的真前缀子串,'Tj-k+1Tj-k+2…Tj-1’是’T1T2…Tj-1’的真后缀子串。当next函数定义中的集合不为空时 next[j]的值等于串’T1T2…Tj-1’的真前缀子串和真后缀子串相等时的最大子串长度+1。
通过以上分析，推导出模式串’abaabcac’的next值的计算过程如表4.1所示。
(1)当j=1时，由定义得知，next[1]=0;
(2)当j=2时，满足1<k<j的k值不存在，由定义得知next[2]=1
4.5实例分析与实现
4.5.1串的实例分析
略
4.5.2简单文本编辑软件的实现
略
4.6算法总结
(1)字符串是一种特殊的线性表，器特殊性在于组成线性表的数据元素仅是一个单字符
(2)字符串常用的存储方式有定长顺序串、堆串和块链串三种。
(3)顺序串是以一维数组作为存储结构，其运算实现方法类似于线性表的顺序存储结构
(4)堆串是以动态一维数组作为存储结构,其运算实现方法和顺序串在存储管理上有所不同。
(5)块链串以链表作为存储结构，其运算实现方法类似于链表。
(6)串的模式匹配算法是本章的难点，BF模式匹配算法处理思路简单,但由于需要进行失配后主串回溯的处理，故而时间复杂度较高。改进的KMP模式匹配算法计算失配后模式串向右滑动的最大位置，由于失配后无回溯，故而匹配速度较高。
习题
略
