数据结构(5) 串 [一] (定义 & 朴素的模式匹配算法)

╰+哭是因爲堅強的太久メ 2022-02-03 06:53 165阅读 0赞

### 串的定义：**是由零个或多个字符组成的有限序列，又叫字符串。** ###

![img][]

一般记为 s=“a1a2a3…an"(n>=0)，其中，s是字符串的名称，用双引号括起来的字符序列是串的值，**注意引号不属于串的内容**。ai可以是字母、数字或者其他字符，i是该字符在串中的位置。**串中的字符数目n称为串的长度**，定义中谈到的有限是指长度n是一个有限的数值。零个字符的串称为空串，它的长度为0，可以直接用两个双引号表示，所谓序列，说明串的相邻字符之间具有前驱和后继的关系。

还有一些概念需要注意：

*  空格串，是只包含空格的串，注意它与空串的区别，空格串是有内容有长度的，而且枯眼不止一个空格。
 *  子串与主串，串中任意个数的连续字符组成的子序列称为该串的子串，相应地，包含子串的串称为主串。
 *  子串在主串中的位置就是该子串的第一个字符在主串中的位置。

### 串的比较 ###

两个数字进行比较，2比1大，这完全正确，可是两个字符串如何比较呢？

事实上，串的比较是通过组成串的字符之间的编码来进行的，而字符的编码指的是字符在对应字符集中的序号。

计算机中的常用字符是用标准的ASCII编码，更准确一点，由8位二进制数表示一个字符，一共可以表示256字符，这些只够以英文为主的语言和特殊符号，但全世界文字千千万万，显然这是不够用的，于是提出了Unicode编码，采用16位的二进制数表示一个字符，一共可以表示6.5万多个，而前256个字符与ASCII完全一致。

如果我们在C语言中比较两个串是否相等，必须是他们串的长度以及他们各个对应位置的字符都相等，才算是相等。

那么当两个字符串不想等时，如何比较他们的大小呢？

给定两个串：s=“a1a2a3…an”，t=“b1b2b3…bm”，当满足以下条件之一时s < t：

1.  n < m，且ai < bi(1<=i<=n);
2.  存在某个k <= min(m,n)，使得ai=bi，(i从1到k-1)，ak < bk ;

换句话说，当两个字符串相等，对应位置的字符也都相等，则两个串是相等的。

### 串的存储结构 ###

1、顺序存储结构

**串的顺序存储结构是用一组地址连续的存储单元来存储串中的字符序列的。按照预定义的大小，为每个定义的串变量分配一个固定长度的存储区。一般是用定常数组来定义。**

既然是定长数组，就存在一个预定义的最大串长度，一般可以将实际的串长度值保存在数组的0下标位置，有的语言加在数组最后：

![img][img 1]

上面说的串的顺序存储其实是有问题的，因为字符串的操作，比如两个串的连接，新串的插入等，都有可能造成串长度超过数组长度。

于是对于顺序存储，有一些优化，串值的存储空间可在程序执行过程中动态分配而得。

2、链式存储结构

对于串的链式存储结构，与线性表是相似的，但由于传结构的特殊性，结构中的每个元素数据是一个字符，如果也简单的应用链表存储串值，一个结点对应一个字符，就存在很大的内存浪费。因此一个结点可以存放一个字符，也可以考虑存放多个字符，最后一个结点若是未被占满，可以用井号或其他值将其填满。

![img][img 2]

总的来说，不如顺序存储灵活，性能也不如顺序存储结构好。

### 朴素的模式匹配算法 ###

**子串的定位操作，通常称作串的模式匹配**

通常的模式匹配，是对主串的每一个字符作为子串的开头，与要匹配的字符串进行匹配，不匹配则整体后移一位，直到完全匹配。

其时间复杂度为O(n+m)，n是主串的长度，m是子串的长度。

示例：

主串： “goodgoogle”找到 “google” 这个子串的位置

![img][img 3]

![img][img 4]

### 后续会有 KMP算法的实现，因为比较复杂，单独拿出一个章节进行讲解。。。。 ###

[img]: /images/20220203/9f6cb2b749234b66bc91a5fbdff9f58c.png
[img 1]: /images/20220203/ffd7bd2bc25d4deab8eb937bb17e073c.png
[img 2]: /images/20220203/45d3e76470e74a66832c242d66260fba.png
[img 3]: /images/20220203/ef9bf18253584ad39785af3899b91e12.png
[img 4]: /images/20220203/2e29df27f3684d1c9a94cf26c3ce9a46.png