数据结构中的串

数据结构第四章串在数据结构的世界里，串是一种非常基础且重要的结构。

它看似简单，却在很多实际的程序设计和应用中发挥着关键作用。

串，简单来说，就是由零个或多个字符组成的有限序列。

这就好比我们日常生活中的一句话、一段文字或者一个密码。

从存储方式上来看，串可以采用顺序存储和链式存储两种方式。

顺序存储就像是把一串珠子穿在一根线上，珠子依次排列，位置固定。

在计算机中，我们可以用一个连续的数组来存储串中的字符。

这种方式简单直观，访问速度快，但存在着一些局限性。

比如说，如果我们事先不知道串的长度，可能会造成存储空间的浪费或者不足。

相比之下，链式存储则更加灵活。

它就像把珠子用链条串起来，每个珠子（也就是字符）都有一个指针指向下一个珠子。

这样，即使在插入或删除字符时，也不需要像顺序存储那样进行大量的数据移动。

但是，链式存储的缺点是访问速度相对较慢，因为需要通过指针依次查找。

接下来，让我们看看串的一些基本操作。

串的比较是经常会用到的操作。

比较两个串的大小，不能像比较数字那样简单地直接比较，而是要从串的第一个字符开始，逐个字符进行比较。

如果在某个位置上的字符不同，那么 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 算法是一种利用哈希函数的
字符串匹配算法，通过计算目标串和模式串的哈希值，并逐个比较，减少比较次数。

数据结构(串)数据结构(串)数据结构中的串（String）是由字符构成的有限序列。

在计算机科学中，串是一种基本的数据结构，被广泛应用于字符串处理、文本搜索、模式匹配等领域。

1. 串的定义和基本操作串可以使用多种方式来定义和表示，常见的方式有：- 定长顺序存储表示：使用数组来存储串，数组的长度和最大串长相等，不足的部分用特定字符填充（通常用空格）。

- 堆分配存储表示：使用堆（动态内存分配区）来存储串，可以根据实际需要动态分配和释放串的存储空间。

- 串的块链存储表示：将串分成多个块，将每个块使用链表进行表示，将各块在一起组成完整的串。

串的基本操作包括：- 串的赋值：将一个串赋值给另一个串。

- 串的连接：将两个串按顺序连接成一个新的串。

- 串的比较：比较两个串的大小关系。

- 串的截取：从一个串中截取出一段子串。

- 串的插入：将一个串插入到另一个串的指定位置。

- 串的删除：删除一个串中指定位置的字符或一段子串。

- 串的替换：将一个串中指定位置的字符或一段子串替换成另一个串。

2. 串的匹配算法串的匹配是指在一个主串中查找一个模式串的过程。

常见的串匹配算法包括：- 朴素匹配算法：也称为暴力匹配算法，是最简单的匹配算法。

它从主串的第一个字符开始，与模式串逐个字符进行比较，若不匹配，则主串向后移动一位，直到找到匹配的子串或主串遍历完。

- KMP算法：即Knuth-Morris-Pratt算法，通过利用模式串自身的信息，减少字符的比较次数。

该算法具有线性时间复杂度，是一种高效的匹配算法。

- Boyer-Moore算法：基于模式串中的字符发生不匹配时的启发式策略，通过跳跃式地移动模式串，减少字符的比较次数，从而提高匹配效率。

3. 串的应用串作为一种基本的数据结构，在实际应用中具有广泛的用途，主要包括以下几个方面：- 字符串处理：串在文本编辑、编译器设计、语法分析、文件操作等方面都有广泛应用。

- 模式匹配：串的匹配算法常被用于字符串搜索、DNA序列分析、信息检索等领域。

数据结构之串类型 串的基本概念： 串(字符串)：是零个或多个字符组成的有限序列。

记作： S=“a1a2a3…”，其中S是串名，ai(1≦i≦n)是单个，可以是字母、数字或其它字符。

串值：双引号括起来的字符序列是串值。

串长：串中所包含的字符个数称为该串的长度。

空串(空的字符串)：长度为零的串称为空串，它不包含任何字符。

空格串(空⽩串)：构成串的所有字符都是空格的串称为空⽩串。

注意：空串和空⽩串的不同，例如“ ”和“”分别表⽰长度为1的空⽩串和长度为0的空串。

⼦串(substring)：串中任意个连续字符组成的⼦序列称为该串的⼦串，包含⼦串的串相应地称为主串。

⼦串的序号：将⼦串在主串中⾸次出现时的该⼦串的⾸字符对应在主串中的序号，称为⼦串在主串中的序号（或位置）。

特别地，空串是任意串的⼦串，任意串是其⾃⾝的⼦串。

串相等：如果两个串的串值相等(相同)，称这两个串相等。

换⾔之，只有当两个串的长度相等，且各个对应位置的字符都相同时才相等。

通常在程序中使⽤的串可分为两种：串变量和串常量。

串的抽象数据类型定义： ADT String{ 数据对象：D = { ai|ai∈CharacterSet, i=1,2,…,n, n ≥0 } 数据关系：R = {<ai-1, ai>| ai-1, ai∈D, i=2,3,…,n } 基本操作： StrAssign(t , chars) 初始条件： chars是⼀个字符串常量。

操作结果：⽣成⼀个值为chars的串t 。

StrConcat(s, t) 初始条件：串s, t 已存在。

操作结果：将串t联结到串s后形成新串存放到s中。

StrLength(t) 初始条件：字符串t已存在。

操作结果：返回串t中的元素个数，称为串长。

SubString (s, pos, len, sub) 初始条件：串s, 已存在, 1≦pos≦StrLength(s)且 0≦len≦StrLength(s) –pos+1。

数据结构-第四章串串也叫字符串，它是由零个或多个字符组成的字符序列。

基本内容1 串的有关概念串的基本操作2 串的定长顺序存储结构，堆分配存储结构；3 串的基本操作算法；4 串的模式匹配算法;5 串操作的应⽤。

学习要点1 了解串的基本操作，了解利⽤这些基本操作实现串的其它操作的⽅法；2 掌握在串的堆分配存储结构下，串的基本操作算法；3 掌握串的模式匹配算法；第四章串 4.1 串的基本概念4.2 串存储和实现4.3 串的匹配算法4.4 串操作应⽤举例第四章串 4.1 串的基本概念 4.2 串存储和实现 4.3 串的匹配算法 4.4 串操作应⽤举例第四章串4.1 串的基本概念 4.2 串存储和实现 4.3 串的匹配算法 4.4 串操作应⽤举例4. 1 串类型的定义⼀、串的定义1 什么是串串是⼀种特殊的线性表，它是由零个或多个字符组成的有,a2, a3, ... a n’限序列，⼀般记作s = ‘a1其中 s----串名， a1,a2, a3, ... a n----串值串的应⽤⾮常⼴泛，许多⾼级语⾔中都把串作为基本数据类型。

在事务处理程序中，顾客的姓名、地址；货物的名称、产地。

可作为字符串处理，⽂本⽂件中的每⼀⾏字符等也可作为字符串处理。

下⾯是⼀些串的例⼦：（1）a = ‘ LIMING’（2）b = ‘NANJING UNIVERSITY OF SCIENCE &TECHNOLOGY’（3）c = ‘ DATA STRUCTURE’（4）d = ‘’说明：1) 串中包含的字符个数，称为串的长度。

长度为0的串称为空串，它不包括任何字符，上⾯（4）中的串d 是空串,(5)中的e 是包含⼀个空格符的空格串；2）串中所包含的字符可以是字母、数字或其他字符，这依赖于具体计算机所允许的字符集。

2 串的有关术语1）⼦串串中任意连续的字符组成的⼦序列称为该串的⼦串例：c = ‘ DATA STRUCTURE’，f=‘DATA’ f是c的⼦串2）⼦串的位置⼦串T 在主串S中的位置是指主串S中第⼀个与T相同的⼦串的⾸字母在主串中的位置。

第四章串串又称字符串，是一种特殊的线性表，它的每个元素仅由一个字符组成。

计算机上非数值处理的对象基本上是字符串数据。

在较早的程序设计语言中，字符串仅作为输入和输出的常量出现。

随着计算机应用的发展，在越来越多的程序设计语言中，字符串也可作为一种变量类型出现，并产生了一系列字符串的操作。

在信息检索系统、文字编辑程序、自然语言翻译系统等等应用中，都是以字符串数据作为处理对象的。

本章将讨论串的存储结构和基本操作。

4.1 串的基本概念4.1.1 串的自然语言定义串(string)(或字符串)是由零个或多个字符组成的有限序列，一般记为：S="a1 a2 …… a n" (n≥0)其中，S是串名，用双引号括起来的字符串序列是串的值；a i(1≤i≤n)可以是字母、数字或其他字符；串中字符的个数n称为串的长度。

长度为0的串称为空串。

需要注意的是，串值必须用一对双引号括起来，但双引号本身不属于串，它的作用只是为了避免与变量名或数的常量混淆。

如"tempt"是个串,tempt则是变量名；"23"是串,而23则是一个常量.串中任意个连续的字符组成的子序列称为该串的子串，如：串S＝"This is a string"，其中"This"是一个子串，"string"也是一个子串。

求子串在串中的起始位置称为子串定位或模式匹配。

例如，设A，B，C为如下三个串：A＝"data"，B="structure"，C＝"data structure"，则它们的长度分别是4,9，14，A和B都是C的子串，A在C中的位置是1，而B在C中的位置是6。

下面注意区别空格串与空串的概念。

在各种应用中，空格常常是串的字符集合中的一个元素，因而可以出现在其他字符中间。

由一个或多个空格组成的串称为空格串，也就是说空格串中只有空格字符，空格串的长度不为零。