数据结构串和数组(一)

一、串的基本概念

串是由零个或多个字符组成的有限序列。记作str="a0a1…an-1"（n≥0）。

串中所包含的字符个数n称为串长度，当n=0时，称为空串。

一个串中任意连续的字符组成的子序列称为该串的子串。

包含子串的串相应地称为主串。

若两个串的长度相等且对应字符都相等，则称两个串相等。

设s是一个长度为n的串，其中的字符各不相同，则s中的所有子串个数是多少？

二、串的抽象数据类型

三、串的存储结构

串的顺序存储结构—顺序

和顺序表一样，用一个data数组和一个整型变量size来表示一个顺序串，size表示data数组中实际字符的个数。

为了简单，data数组采用固定容量为MaxSize（可以模仿顺序表改为动态容量方式）。

顺序串类SqString

顺序串上的基本运算算法设计与顺序表类似，仅以求子串为例说明。

求子串：对于一个顺序串求序号i开始长度为j的子串。

实现：先创建一个空串s，当参数正确时，s子串的字符序列为data[i..i+j-1]，共j个字符，当i和i+j-1不在有效序序号0～size-1范围内时，则参数错误，此时返回空串。

设计一个算法Strcmp(s，t)，以字典顺序比较两个英文字母串s和t的大小，假设两个串均以顺序串存储。

串的链式存储结构—链串

用带头结点的单链表表示链串

例如，s= "ABCDEFGHIJKLMN"，共14个字符。

链串的结点类型LinkNode（结点大小为1）

一个链串用一个头结点head来唯一标识，链串类LinkString

链串上的基本运算算法设计与单链表类似，仅以串插入算法为例说明。

串插入：链串在序号i位置插入串t

实现：先创建一个空串s，当参数正确时，采用尾插法建立结果串s：

（1）将当前链串的前i个结点复制到s中。

（2）将t中所有结点复制到s中。

（3）再将当前串的余下结点复制到s中。

串的模式匹配

设有两个串s和t，串t定位操作就是在串s中查找与子串t相等的子串。

通常把串s称为目标串，把串t称为模式串，因此定位也称作模式匹配。

模式匹配成功是指在目标串s中找到一个模式串t。

不成功则指目标串s中不存在模式串t。

BF算法

思路：目标串s="s0s1…sn-1"，模式串t="t0t1…tm-1"

第1趟：从s0/t0开始比较，若相等，则继续逐个比较后续字符。如果对应的字符全部相同且t的字符比较完，说明t是s的子串，返回t在s中的起始位置，表示匹配成功；如果对应的字符不相同，说明第一趟匹配失败。

第2趟：从s1/t0开始比较，若相等，则继续逐个比较后续字符。如果对应的字符全部相同且t的字符比较完，说明t是s的子串，返回t在s中的起始位置，表示匹配成功；如果对应的字符不相同，说明第一趟匹配失败。

依次类推。只要有一趟匹配成功，则说明t是s的子串，返回t在s中的起始位置。如果i超界都没有匹配成功，说明t不是s的子串，返回-1。

BF算法性能

该算法在最好情况下的时间复杂度为O(m)，即主串的前m个字符正好等于模式串的m个字符。

最坏情况下的时间复杂度为O(n×m)。

平均情况下的时间复杂度为O(n×m)。

KMP算法

主要是消除了目标串指针的回溯，从而使算法效率有了某种程度的提高。

KMP算法性能

设目标串s的长度为n，模式串t长度为m。

在KMP算法中求next数组的时间复杂度为O(m)。

在后面的匹配中因主串s的下标i不减即不回溯，比较次数可记为n。

KMP算法总的时间复杂度为O(n+m)。

例子：设目标串s="ababcabcacbab"，模式串t="abcac"。给出KMP进行模式匹配的过程。

KMP算法的性能提高了吗？

KMP算法跳过了中间一些趟，正确吗？

例子：设s="aaabaaaab"，t="aaaab"。计算模式串t的nextval函数值。并画出利用改进KMP算法进行模式匹配时每一趟的匹配过程。

例子：设目标串为s="abcaabbabcabaacbacba"，模式串t="abcabaa"。计算模式串t的nextval函数值。并画出利用KMP算法进行模式匹配时每一趟的匹配过程。