串的知识点数据结构

数据结构-4 串数据结构 4 串在计算机科学中，数据结构是组织和存储数据的方式，以便能够有效地进行操作和访问。

今天，咱们来聊聊数据结构中的“串”。

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

这就好比我们日常说的一句话、一篇文章中的一段文字，都是串的具体表现形式。

串在计算机中的应用非常广泛。

比如说，在文本编辑中，我们输入的每一行文字都可以看作是一个串；在网络通信中，传输的各种信息也常常以串的形式存在；在数据库中，存储的字符数据也可以理解为串。

为了更好地处理串，计算机科学家们设计了各种各样的操作和算法。

首先是串的存储结构。

常见的有两种：顺序存储和链式存储。

顺序存储就像是把一串字符一个挨着一个地放在连续的内存空间里。

这样的好处是可以快速地随机访问串中的任意字符，但缺点是在插入或删除字符时可能需要大量的移动操作。

链式存储则是通过节点把字符连接起来，每个节点存储一个字符以及指向下一个节点的指针。

这种方式在插入和删除操作时比较方便，但随机访问的效率相对较低。

接下来，咱们聊聊串的比较操作。

比较两个串是否相等是很常见的需求。

这可不是简单地看看两个串长得一不一样，还得考虑字符的顺序和数量。

常见的比较方法有逐个字符比较，从串的开头一个一个比下去，直到发现不同或者其中一个串结束。

再说说串的模式匹配。

这是一个很重要的操作，比如说要在一篇长文章中找到某个特定的关键词或者短语，这就用到了模式匹配算法。

其中，著名的有朴素模式匹配算法和 KMP 算法。

朴素模式匹配算法的思路很直接，就是从主串的开头开始，逐个与模式串进行匹配，如果匹配不成功就将模式串往后移动一位继续匹配。

这个算法简单易懂，但效率不是很高，特别是在主串和模式串长度较长时。

KMP 算法则通过对模式串的预处理，计算出一个 next 数组，利用这个数组可以在匹配不成功时更有效地移动模式串，从而提高匹配的效率。

除了上面说的这些，串还有很多其他的操作，比如串的连接、子串提取、串的替换等等。

串的知识点总结1. 串的基本概念串是由零个或多个字符组成的有限序列，通常用来表示文本数据。

在编程语言中，串通常被定义为一个字符数组或字符串变量。

例如，在C语言中，字符串通常被定义为char类型的数组，而在Java语言中，字符串则是一个类对象。

2. 串的存储结构串的存储结构有两种常见形式：一是定长顺序存储结构，二是链式存储结构。

定长顺序存储结构是将串的字符按照顺序存储在一块连续的存储空间中，这种方式可以通过下标来访问任意位置的字符，但是需要预先分配足够的存储空间。

链式存储结构则是使用链表来存储串的字符，这种方式可以动态分配内存空间，但是访问任意位置的字符需要从链表头开始遍历，效率较低。

3. 串的基本操作串的基本操作包括串的创建、复制、连接、比较、插入和删除等。

创建串是指将一组字符转换成串的操作；复制是指将一个串的内容复制到另一个串中；连接是指将两个串连接在一起形成一个新的串；比较是指比较两个串的大小关系；插入是指在一个串中的指定位置插入一个子串；删除是指删除一个串中的指定子串。

这些操作都是串的基本操作，它们在实际应用中有着重要的作用。

4. 串的模式匹配串的模式匹配是指在一个主串中查找与给定模式串相匹配的子串的过程。

常见的模式匹配算法有暴力匹配算法、KMP算法和Boyer-Moore算法等。

暴力匹配算法是最简单的模式匹配算法，它的时间复杂度为O(m*n)，其中m为主串长度，n为模式串长度；KMP算法是一种高效的模式匹配算法，它的时间复杂度为O(m+n)，其中m为主串长度，n为模式串长度；Boyer-Moore算法是一种更加高效的模式匹配算法，它的时间复杂度为O(m*n)，其中m为主串长度，n为模式串长度。

5. 串的应用串在计算机科学中有着广泛的应用，它在各种应用中都有着重要的作用。

例如，在文本编辑器中，串被用来表示文本文件的内容；在数据库系统中，串被用来表示数据的各种属性；在网络通信中，串被用来表示网页的URL地址等。

第五章串§5.1串的定义串：又称字符串。

通常把串看作一种数据结构，它是数据元素仅由单个字符组成的特殊线性表。

一般说来，串是零个或有限个字符的线形序列。

记作：s='a1 a2… a n' n≥0其中：s:是串名，用单引号括起来的字符序列为串的值。

a i:为串的元素,它可以是字母、数字或其他字符(运算符、分割符、汉字等)。

n:为串的长度(即串中字符的个数)。

n=0时，称为空串。

注意：单引号本身不属于串，只是为了避免和其它变量混淆。

例如：a='BEIJING'其值为字符序列BEIJING两个特殊的串：①空格串：空格串是仅由空格组成的串，记作s=' '，串中空格字符的个数即为其长度(>0)，为了清楚起见，往往用符号φ来表示空格。

②空串：空串中无任何字符，记作s=''，其长度为0。

按字符在字符串中的次序可以规定字符的大小。

§5.2 串的存储结构串作为一种特殊的线性表，线性表的顺序存储结构和链式存储结构对串都是适用的。

一、顺序存储在此种存储方式中，串的字符相继按存入连续的存储单元中，有三种格式：1.紧缩格式（在按字编址的机器中）是在一个存储单元中存放多个字符，假定一个存储单元可存放k个字符（字长为4），而给出的串长度为n 全都利用上。

2.非紧缩格式：不管机器字的长短，在一个字中只存放一个字符。

如下图所示：3.以字节为单位存储（在按字节编址的机器中）通常因为一个字节恰好存储一个字符的ASCII 码，这就自然形成了一个字节存放一个字符的单字节存储格式，既节省空间，又处理方便。

可见顺序分配的共性,空间利用率高,访问方便,但插入删除不方便,链表的存储恰恰弥补了这一不足。

二、链式存储第一个字中存放串长值 例如：设k=4,存储如图：10 1312 11 ┅当结点大小大于1时，一个串所占的结点中最后一个结点不一定全被串值占满这时,一般都补上非串值的字符“#”。

《数据结构与算法》第四章串知识点及例题精选串（即字符串）是一种特殊的线性表，它的数据元素仅由一个字符组成。

4.1 串及其基本运算4.1.1 串的基本概念１．串的定义串是由零个或多个任意字符组成的字符序列。

一般记作：s=＂s1 s2 … s n＂＂其中s 是串名；在本书中，用双引号作为串的定界符，引号引起来的字符序列为串值，引号本身不属于串的内容；a i(1<=i<=n)是一个任意字符，它称为串的元素，是构成串的基本单位，i是它在整个串中的序号; n为串的长度，表示串中所包含的字符个数，当n=0时，称为空串，通常记为Ф。

２．几个术语子串与主串：串中任意连续的字符组成的子序列称为该串的子串。

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

子串的位置：子串的第一个字符在主串中的序号称为子串的位置。

串相等：称两个串是相等的，是指两个串的长度相等且对应字符都相等。

4.2 串的定长顺序存储及基本运算因为串是数据元素类型为字符型的线性表，所以线性表的存储方式仍适用于串，也因为字符的特殊性和字符串经常作为一个整体来处理的特点，串在存储时还有一些与一般线性表不同之处。

4.2.1 串的定长顺序存储类似于顺序表，用一组地址连续的存储单元存储串值中的字符序列，所谓定长是指按预定义的大小，为每一个串变量分配一个固定长度的存储区，如：#define MAXSIZE 256char s[MAXSIZE];则串的最大长度不能超过256。

如何标识实际长度？1. 类似顺序表，用一个指针来指向最后一个字符，这样表示的串描述如下：typedef struct{ char data[MAXSIZE];int curlen;} SeqString;定义一个串变量：SeqString s;这种存储方式可以直接得到串的长度：s.curlen+1。

如图4.1所示。

s.dataMAXSIZE-1图4.1 串的顺序存储方式12. 在串尾存储一个不会在串中出现的特殊字符作为串的终结符，以此表示串的结尾。

数据结构(串)数据结构(串)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.法律名词及注释- 数据结构：指计算机科学中研究数据存储方式及其相关操作的学科。

- 串：也称为字符串，是由零个或多个字符组成的有序序列。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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