下载文档原格式
数据结构第四章串在数据结构的世界里，串是一种非常基础且重要的结构。
它看似简单，却在很多实际的程序设计和应用中发挥着关键作用。
串，简单来说，就是由零个或多个字符组成的有限序列。
这就好比我们日常生活中的一句话、一段文字或者一个密码。
从存储方式上来看，串可以采用顺序存储和链式存储两种方式。
顺序存储就像是把一串珠子穿在一根线上，珠子依次排列，位置固定。
在计算机中，我们可以用一个连续的数组来存储串中的字符。
这种方式简单直观，访问速度快，但存在着一些局限性。
比如说，如果我们事先不知道串的长度，可能会造成存储空间的浪费或者不足。
相比之下，链式存储则更加灵活。
它就像把珠子用链条串起来，每个珠子（也就是字符）都有一个指针指向下一个珠子。
这样，即使在插入或删除字符时，也不需要像顺序存储那样进行大量的数据移动。
但是，链式存储的缺点是访问速度相对较慢，因为需要通过指针依次查找。
接下来，让我们看看串的一些基本操作。
串的比较是经常会用到的操作。
比较两个串的大小，不能像比较数字那样简单地直接比较，而是要从串的第一个字符开始，逐个字符进行比较。
如果在某个位置上的字符不同，那么 ASCII 码值大的那个串就更大；如果前面的字符都相同，但是一个串先结束了，那么长度短的串就更小。
串的连接也是常见的操作。
想象一下把两段绳子接在一起，就形成了一个更长的绳子。
串的连接也是类似的道理，把两个串首尾相连，形成一个新的串。
但在实际操作中，要注意存储空间的分配，确保有足够的空间来容纳连接后的串。
还有串的子串操作。
比如说，从一篇文章中截取一段文字，这就是获取一个子串。
在程序中，我们需要明确指定子串的起始位置和长度，才能准确地获取到所需的部分。
串的模式匹配更是一个重要的应用。
这就像是在一篇长篇小说中寻找特定的关键词或者短语。
最常见的模式匹配算法有朴素模式匹配算法和 KMP 算法。
朴素模式匹配算法比较直接，就是从主串的开头逐个字符与模式串进行匹配。
而 KMP 算法则通过对模式串进行预处理，利用已经匹配的部分信息，减少不必要的比较，从而提高匹配的效率。
数据结构-4 串数据结构 4 串在计算机科学中，数据结构是组织和存储数据的方式，以便能够有效地进行操作和访问。
今天，咱们来聊聊数据结构中的“串”。
什么是串呢？简单来说，串就是由零个或多个字符组成的有限序列。
这就好比我们日常说的一句话、一篇文章中的一段文字，都是串的具体表现形式。
串在计算机中的应用非常广泛。
比如说，在文本编辑中，我们输入的每一行文字都可以看作是一个串；在网络通信中，传输的各种信息也常常以串的形式存在；在数据库中，存储的字符数据也可以理解为串。
为了更好地处理串，计算机科学家们设计了各种各样的操作和算法。
首先是串的存储结构。
常见的有两种：顺序存储和链式存储。
顺序存储就像是把一串字符一个挨着一个地放在连续的内存空间里。
这样的好处是可以快速地随机访问串中的任意字符，但缺点是在插入或删除字符时可能需要大量的移动操作。
链式存储则是通过节点把字符连接起来，每个节点存储一个字符以及指向下一个节点的指针。
这种方式在插入和删除操作时比较方便，但随机访问的效率相对较低。
接下来，咱们聊聊串的比较操作。
比较两个串是否相等是很常见的需求。
这可不是简单地看看两个串长得一不一样，还得考虑字符的顺序和数量。
常见的比较方法有逐个字符比较，从串的开头一个一个比下去，直到发现不同或者其中一个串结束。
再说说串的模式匹配。
这是一个很重要的操作，比如说要在一篇长文章中找到某个特定的关键词或者短语，这就用到了模式匹配算法。
其中，著名的有朴素模式匹配算法和 KMP 算法。
朴素模式匹配算法的思路很直接，就是从主串的开头开始，逐个与模式串进行匹配，如果匹配不成功就将模式串往后移动一位继续匹配。
这个算法简单易懂，但效率不是很高，特别是在主串和模式串长度较长时。
KMP 算法则通过对模式串的预处理，计算出一个 next 数组，利用这个数组可以在匹配不成功时更有效地移动模式串，从而提高匹配的效率。
除了上面说的这些，串还有很多其他的操作，比如串的连接、子串提取、串的替换等等。
数据结构(串)数据结构(串)1.介绍1.1 定义数据结构(串)是计算机科学中的一种基础数据结构，用于存储和操作一系列具有相同数据类型的元素的集合。
1.2 特性- 顺序存储：串中的元素按照在字符串中的顺序存储。
- 长度可变：可以动态改变串的长度。
- 计数方式：通常使用0开始计数。
1.3 应用字符串的数据结构广泛应用于文本处理、模式匹配、编译器设计等领域。
2.串的基本操作2.1 创建串：定义一个字符串变量并为其分配内存空间。
2.2 销毁串：释放字符串变量占用的内存空间。
2.3 清空串：将字符串中的元素清空，使字符串变为空串。
2.4 判断串是否为空：判断字符串是否为空串。
2.5 获取串的长度：获取字符串中元素的个数。
2.6 拷贝串：将一个串拷贝到另一个串中。
2.7 两个串：将两个串连接成一个新的串。
2.8 截取子串：从原串中截取一段子串。
2.9 查找子串：在串中查找指定子串的位置。
2.10 替换子串：在串中将指定子串替换成新的子串。
2.11 插入子串：在串中指定位置插入一个子串。
2.12 删除子串：从串中删除指定的子串。
3.串的存储结构3.1 顺序存储结构：使用一维数组存储字符串的字符元素。
3.2 链式存储结构：使用链表存储字符串的字符元素，每个节点存储一个字符。
4.串匹配算法4.1 暴力匹配算法：逐个比较字符串中的字符，若匹配失败则向后移动。
4.2 KMP算法：利用前缀函数预处理，避免重复比较已经匹配的字符。
4.3 Boyer-Moore算法：从匹配串的末尾开始比较，利用坏字符规则和好后缀规则跳过不必要的比较。
5.附件本文档不涉及附件。
6.法律名词及注释- 数据结构：指计算机科学中研究数据存储方式及其相关操作的学科。
- 串：也称为字符串，是由零个或多个字符组成的有序序列。
数据结构-4 串数据结构 4 串在计算机科学中，数据结构是组织和存储数据的方式，以便能够有效地进行操作和处理。
其中，串（String）是一种非常常见且重要的数据结构，它在众多的应用中都发挥着重要的作用。
串，简单来说，就是由零个或多个字符组成的有限序列。
我们日常生活中接触到的各种文本，比如一篇文章、一条短信、一个网页的标题等等，在计算机中都可以用串来表示。
串有其独特的特点。
首先，它具有有限长度。
这意味着串中包含的字符数量是有限的，不能无限增长。
其次，串中的字符通常来自某个特定的字符集，比如常见的ASCII 字符集或者Unicode 字符集。
再者，串中的字符是按照一定的顺序排列的，这个顺序是有意义且不可随意更改的。
为了在计算机中有效地存储和操作串，有多种不同的实现方式。
一种常见的方式是使用字符数组。
我们可以定义一个足够大的字符数组来存储串中的字符。
这种方式直观且简单，但在进行串的修改操作（如插入、删除）时，可能会比较麻烦，因为需要移动大量的字符来腾出空间或者填补空缺。
另一种方式是使用指针和动态分配内存。
通过动态分配内存，可以根据串的实际长度来灵活地分配所需的存储空间。
这样在处理长度变化较大的串时，效率会更高，但也需要注意内存的释放，以避免内存泄漏的问题。
在对串进行操作时，有许多常见的基本运算。
比如串的连接，就是将两个串拼接在一起形成一个新的串。
还有串的比较，判断两个串是否相等，或者哪个串在字典序上更大。
此外，还有子串的提取，从一个串中取出一部分连续的字符形成新的串。
串的应用场景十分广泛。
在文本编辑软件中，对输入的文本进行处理和存储就离不开串。
在数据库系统中，存储和检索字符串类型的数据也需要对串进行有效的管理。
在编程语言中，字符串的处理也是常见的操作，比如字符串的格式化输出、字符串的查找和替换等等。
举个例子，当我们在搜索引擎中输入关键词时，搜索引擎会将我们输入的关键词作为一个串，然后在其庞大的数据库中进行匹配和查找，找到与这个串相关的网页和信息。
数据结构的串操作数据结构的串操作
⒈概述
⑴串的定义
⑵串的基本操作
⒉串的存储结构
⑴顺序存储结构
⑵链式存储结构
⒊串的基本操作
⑴串的长度
⑵串的比较
⑶串的连接
⑷串的截取
⑸串的插入
⑹串的删除
⑺串的替换
⒋字符串匹配算法
⑴朴素模式匹配算法
⑵ KMP 算法
⑶ Boyer-Moore 算法
⑷ Rabin-Karp 算法
附件：
⒈示例代码
⒉数据集
法律名词及注释：
⒈串：在计算机科学中，串（String）是由零个或多个字符组成的有限序列。
⒉顺序存储结构：串的顺序存储结构是将串的字符按线性次序逐个存储在一组地址连续的存储单元里。
⒊链式存储结构：串的链式存储结构是通过定义一个节点类型来存储串的字符，每个节点包含一个字符和一个指向下一个节点的指针。
⒋朴素模式匹配算法：朴素模式匹配算法是最简单的字符串匹
配算法之一，通过对目标串的每个字符依次与模式串进行比较，直
到找到匹配的位置或遍历完所有字符。
⒌ KMP 算法：KMP 算法是一种高效的字符串匹配算法，通过利
用模式串的前缀和后缀信息，在匹配失败时将模式串移动比朴素算
法更远的位置，减少比较次数。
⒍ Boyer-Moore 算法：Boyer-Moore 算法是一种基于多种规则
的字符串匹配算法，通过从右到左比较模式串和目标串的字符，根
据不匹配字符在模式串中的位置和字符表进行移动，提高匹配效率。
⒎ Rabin-Karp 算法：Rabin-Karp 算法是一种利用哈希函数的
字符串匹配算法，通过计算目标串和模式串的哈希值，并逐个比较，减少比较次数。
