数据结构 串结构

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

如果在某个位置上的字符不同，那么 ASCII 码值大的那个串就更大；如果前面的字符都相同，但是一个串先结束了，那么长度短的串就更小。

串的连接也是常见的操作。

想象一下把两段绳子接在一起，就形成了一个更长的绳子。

串的连接也是类似的道理，把两个串首尾相连，形成一个新的串。

但在实际操作中，要注意存储空间的分配，确保有足够的空间来容纳连接后的串。

还有串的子串操作。

比如说，从一篇文章中截取一段文字，这就是获取一个子串。

在程序中，我们需要明确指定子串的起始位置和长度，才能准确地获取到所需的部分。

串的模式匹配更是一个重要的应用。

这就像是在一篇长篇小说中寻找特定的关键词或者短语。

最常见的模式匹配算法有朴素模式匹配算法和 KMP 算法。

朴素模式匹配算法比较直接，就是从主串的开头逐个字符与模式串进行匹配。

而 KMP 算法则通过对模式串进行预处理，利用已经匹配的部分信息，减少不必要的比较，从而提高匹配的效率。

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

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

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

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

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

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

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

首先是串的存储结构。

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

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

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

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

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

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

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

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

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

再说说串的模式匹配。

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

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

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

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

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

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

第五章串§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时，一个串所占的结点中最后一个结点不一定全被串值占满这时,一般都补上非串值的字符“#”。

串-数据结构实验报告串数据结构实验报告一、实验目的本次实验的主要目的是深入理解和掌握串这种数据结构的基本概念、存储方式以及相关的操作算法。

通过实际编程实现串的基本操作，提高对数据结构的理解和编程能力，培养解决实际问题的思维和方法。

二、实验环境本次实验使用的编程语言为C+＋，开发工具为Visual Studio 2019。

三、实验原理（一）串的定义串是由零个或多个字符组成的有限序列。

在本次实验中，我们主要关注的是字符串。

（二）串的存储方式1、顺序存储定长顺序存储：使用固定长度的数组来存储字符串，长度不足时用特定字符填充。

堆分配存储：根据字符串的实际长度动态分配存储空间。

2、链式存储每个节点存储一个字符，并通过指针链接起来。

（三）串的基本操作1、串的创建和初始化2、串的赋值3、串的连接4、串的比较5、求子串6、串的插入和删除四、实验内容及步骤（一）顺序存储方式下串的实现1、定义一个结构体来表示顺序存储的字符串，包含字符数组和字符串的实际长度。

｀｀｀cppstruct SeqString ｛char str;int length;｝；｀｀｀2、实现串的创建和初始化函数｀｀｀cppSeqString createSeqString(const char initStr) ｛int len ＝ strlen(initStr)；SeqString s;sstr ＝ new charlen ＋ 1;strcpy(sstr, initStr)；slength ＝ len;return s;｝｀｀｀3、串的赋值函数｀｀｀cppvoid assignSeqString(SeqString& s, const char newStr) ｛delete sstr;int len ＝ strlen(newStr)；sstr ＝ new charlen ＋ 1;strcpy(sstr, newStr)；slength ＝ len;｝｀｀｀4、串的连接函数｀｀｀cppSeqString concatSeqString(const SeqString& s1, const SeqString& s2) ｛SeqString result;resultlength ＝ s1length ＋ s2length;resultstr ＝ new charresultlength ＋ 1;strcpy(resultstr, s1str)；strcat(resultstr, s2str)；return result;｝｀｀｀5、串的比较函数｀｀｀cppint compareSeqString(const SeqString& s1, const SeqString& s2) ｛return strcmp(s1str, s2str)；｝｀｀｀6、求子串函数｀｀｀cppSeqString subSeqString(const SeqString& s, int start, int len) ｛SeqString sub;sublength ＝ len;substr ＝ new charlen ＋ 1;strncpy(substr, sstr ＋ start, len)；substrlen ＝＇＼0'；return sub;｝｀｀｀7、串的插入函数｀｀｀cppvoid insertSeqString(SeqString& s, int pos, const SeqString& insertStr) ｛int newLength ＝ slength ＋ insertStrlength;char newStr ＝ new charnewLength ＋ 1;strncpy(newStr, sstr, pos)；strcpy(newStr ＋ pos, insertStrstr)；strcpy(newStr ＋ pos ＋ insertStrlength, sstr ＋ pos)；delete sstr;sstr ＝ newStr;slength ＝ newLength;｝｀｀｀8、串的删除函数｀｀｀cppvoid deleteSeqString(SeqString& s, int start, int len) ｛int newLength ＝ slength len;char newStr ＝ new charnewLength ＋ 1;strncpy(newStr, sstr, start)；strcpy(newStr ＋ start, sstr ＋ start ＋ len)；delete sstr;sstr ＝ newStr;slength ＝ newLength;｝｀｀｀（二）链式存储方式下串的实现1、定义一个节点结构体｀｀｀cppstruct LinkNode ｛char data;LinkNode next;LinkNode(char c) ： data(c)， next(NULL) ｛｝｝；｀｀｀2、定义一个链式存储的字符串类｀｀｀cppclass LinkString ｛private:LinkNode head;int length;public:LinkString(const char initStr)；～LinkString(）；void assign(const char newStr)；LinkString concat(const LinkString& other)；int compare(const LinkString& other)；LinkString subString(int start, int len)；void insert(int pos, const LinkString& insertStr)；void deleteSub(int start, int len)；｝；｀｀｀3、实现各个函数｀｀｀cppLinkString:：LinkString(const char initStr) ｛length ＝ strlen(initStr)；head ＝ NULL;LinkNode p ＝ NULL;for （int i ＝ 0; i ＜ length; i+＋）｛LinkNode newNode ＝ new LinkNode(initStri)；if （head ＝＝ NULL) ｛head ＝ newNode;p ＝ head;｝ else ｛p>next ＝ newNode;p ＝ p>next;｝｝｝LinkString:：～LinkString(）｛LinkNode p ＝ head;while （p) ｛LinkNode temp ＝ p;p ＝ p>next;delete temp;｝｝void LinkString:：assign(const char newStr) ｛／／先释放原有的链表LinkNode p ＝ head;while （p) ｛LinkNode temp ＝ p;p ＝ p>next;delete temp;｝length ＝ strlen(newStr)；head ＝ NULL;p ＝ NULL;for （int i ＝ 0; i ＜ length; i+＋）｛LinkNode newNode ＝ new LinkNode(newStri)；if （head ＝＝ NULL) ｛head ＝ newNode;p ＝ head;｝ else ｛p>next ＝ newNode;p ＝ p>next;｝｝｝LinkString LinkString:：concat(const LinkString& other) ｛LinkString result;LinkNode p1 ＝ head;LinkNode p2 ＝ otherhead;LinkNode p ＝ NULL;while （p1) ｛LinkNode newNode ＝ new LinkNode(p1-＞data)；if （resulthead ＝＝ NULL) ｛resulthead ＝ newNode;p ＝ resulthead;｝ else ｛p>next ＝ newNode;p ＝ p>next;｝p1 ＝ p1-＞next;｝while （p2) ｛LinkNode newNode ＝ new LinkNode(p2-＞data)；if （resulthead ＝＝ NULL) ｛resulthead ＝ newNode;p ＝ resulthead;｝ else ｛p>next ＝ newNode;p ＝ p>next;｝p2 ＝ p2-＞next;｝resultlength ＝ length ＋ otherlength;return result;｝int LinkString:：compare(const LinkString& other) ｛LinkNode p1 ＝ head;LinkNode p2 ＝ otherhead;while （p1 ＆＆ p2 ＆＆ p1-＞data ＝＝ p2-＞data) ｛p1 ＝ p1-＞next;p2 ＝ p2-＞next;｝if （p1 ＝＝ NULL ＆＆ p2 ＝＝ NULL) ｛return 0;｝ else if （p1 ＝＝ NULL) ｛return －1;｝ else if （p2 ＝＝ NULL) ｛return 1;｝ else ｛return p1-＞data p2-＞data;｝｝LinkString LinkString:：subString(int start, int len) ｛LinkString sub;LinkNode p ＝ head;for （int i ＝ 0; i ＜ start; i+＋）｛p ＝ p>next;｝for （int i ＝ 0; i ＜ len; i+＋）｛LinkNode newNode ＝ new LinkNode(p>data)；if （subhead ＝＝ NULL) ｛subhead ＝ newNode;｝ else ｛LinkNode temp ＝ subhead;while （temp>next) ｛temp ＝ temp>next;｝temp>next ＝ newNode;｝p ＝ p>next;｝sublength ＝ len;return sub;｝void LinkString:：insert(int pos, const LinkString& insertStr) ｛LinkNode p ＝ head;for （int i ＝ 0; i ＜ pos 1; i+＋）｛p ＝ p>next;｝LinkNode insertHead ＝ insertStrhead;while （insertHead) ｛LinkNode newNode ＝ new LinkNode(insertHead>data)；newNode>next ＝ p>next;p>next ＝ newNode;p ＝ p>next;insertHead ＝ insertHead>next;｝length ＋＝ insertStrlength;｝void LinkString:：deleteSub(int start, int len) ｛LinkNode p ＝ head;for （int i ＝ 0; i ＜ start 1; i+＋）｛p ＝ p>next;｝LinkNode temp ＝ p>next;for （int i ＝ 0; i ＜ len; i+＋）｛LinkNode delNode ＝ temp;temp ＝ temp>next;delete delNode;｝p>next ＝ temp;length ＝ len;｝｀｀｀（三）测试用例1、顺序存储方式的测试｀｀｀cppint main(）｛SeqString s1 ＝ createSeqString(＂Hello"）；SeqString s2 ＝ createSeqString(＂World"）；SeqString s3 ＝ concatSeqString(s1, s2)；std:：cout ＜＜＂连接后的字符串: ＂＜＜ s3str ＜＜ std:：endl; int cmpResult ＝ compareSeqString(s1, s2)；if （cmpResult ＜ 0) ｛std:：cout ＜＜＂s1 小于 s2" ＜＜ std:：endl;｝ else if （cmpResult ＝＝ 0) ｛std:：cout ＜＜＂s1 等于 s2" ＜＜ std:：endl;｝ else ｛std:：cout ＜＜＂s1 大于 s2" ＜＜ std:：endl;｝SeqString sub ＝ subSeqString(s1, 1, 3)；std:：cout ＜＜＂子串: ＂＜＜ substr ＜＜ std:：endl; insertSeqString(s1, 2, s2)；std:：cout ＜＜＂插入后的字符串: ＂＜＜ s1str ＜＜ std:：endl; deleteSeqString(s1, 3, 2)；std:：cout ＜＜＂删除后的字符串: ＂＜＜ s1str ＜＜ std:：endl; return 0;｝｀｀｀2、链式存储方式的测试｀｀｀cppint main(）｛LinkString ls1(＂Hello"）；LinkString ls2(＂World"）；LinkString ls3 ＝ ls1concat(ls2)；std:：cout ＜＜＂连接后的字符串: ＂；LinkNode p ＝ ls3head;while （p) ｛std:：cout ＜＜ p>data;p ＝ p>next;｝std:：cout ＜＜ std:：endl;int cmpResult ＝ ls1compare(ls2)；if （cmpResult ＜ 0) ｛std:：cout ＜＜＂ls1 小于 ls2" ＜＜ std:：endl;｝ else if （cmpResult ＝＝ 0) ｛std:：cout ＜＜＂ls1 等于 ls2" ＜＜ std:：endl;｝ else ｛std:：cout ＜＜＂ls1 大于 ls2" ＜＜ std:：endl;｝LinkString sub ＝ ls1subString(1, 3)；std:：cout ＜＜＂子串: ＂；p ＝ subhead;while （p) ｛std:：cout ＜＜ p>data;p ＝ p>next;｝std:：cout ＜＜ std:：endl;ls1insert(2, ls2)；std:：cout ＜＜＂插入后的字符串: ＂；p ＝ ls1head;while （p) ｛std:：cout ＜＜ p>data;p ＝ p>next;｝std:：cout ＜＜ std:：endl;ls1deleteSub(3, 2)；std:：cout ＜＜＂删除后的字符串: ＂；p ＝ ls1head;while （p) ｛std:：cout ＜＜ p>data;p ＝ p>next;｝std:：cout ＜＜ std:：endl;return 0;｝｀｀｀五、实验结果及分析（一）顺序存储方式1、连接操作成功实现，输出了正确连接后的字符串。

数据结构(串)数据结构(串)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 字符集。

再者，串中的字符是按照一定的顺序排列的，这个顺序是有意义且不可随意更改的。

为了在计算机中有效地存储和操作串，有多种不同的实现方式。

一种常见的方式是使用字符数组。

我们可以定义一个足够大的字符数组来存储串中的字符。

这种方式直观且简单，但在进行串的修改操作（如插入、删除）时，可能会比较麻烦，因为需要移动大量的字符来腾出空间或者填补空缺。

另一种方式是使用指针和动态分配内存。

通过动态分配内存，可以根据串的实际长度来灵活地分配所需的存储空间。

这样在处理长度变化较大的串时，效率会更高，但也需要注意内存的释放，以避免内存泄漏的问题。

在对串进行操作时，有许多常见的基本运算。

比如串的连接，就是将两个串拼接在一起形成一个新的串。

还有串的比较，判断两个串是否相等，或者哪个串在字典序上更大。

此外，还有子串的提取，从一个串中取出一部分连续的字符形成新的串。

串的应用场景十分广泛。

在文本编辑软件中，对输入的文本进行处理和存储就离不开串。

在数据库系统中，存储和检索字符串类型的数据也需要对串进行有效的管理。

在编程语言中，字符串的处理也是常见的操作，比如字符串的格式化输出、字符串的查找和替换等等。

举个例子，当我们在搜索引擎中输入关键词时，搜索引擎会将我们输入的关键词作为一个串，然后在其庞大的数据库中进行匹配和查找，找到与这个串相关的网页和信息。

1第4章串主要内容： 串的基本概念 串的定长顺序表示 串的堆分配存储表示 串的块链存储表示2串的概述串是一种常用于非数值处理的线性结构从数据结构角度看，串是一种线性表，其特殊之处在于其数据元素类型被限定为字符。

因此也可以称串是一种特殊的线性表。

从数据类型来看，串由字符构成，其操作特点和线性表大不相同，是完全不同的数据类型。

串通常以串的整体作为操作对象，因为串中的单个元素常常是无意义的。

而线性表的操作对象多以单个元素为操作对象串是元素类型被限制为字符的特殊线性表3§ 4.1 串的类型定义1. 串的基本概念串(String)：是零个或多个字符组成的有限序列。

一般记作S= ‘a 1a 2a 3…a n ’，S 是串名，单引号括起来的字符序列是串值； a i (1≤i ≤n )可以是字母、数字或其它字符；i 是字符在序列中的序号，也称为该字符在串中的位置。

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

引号不属于串。

两个串相等，当且仅当两个串值相等，即长度、位置相等。

4空串和空白串空串(Empty String)：长度为零的串，不包含任何字符。

空白串(Blank String)：空格也是串集合中的一个元素，通常将仅由一个或多个空格组成的串称为空白串。

注意：空串和空白串不同。

例如“”和“”分别表示长度为1的空白串和长度为0的空串。

为了清楚起见，用“φ”来表示空串5子串和主串子串：串中任意个连续字符组成的子序列称为该串的子串。

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

B 是A 的子串。

B 在A 中出现了两次，B 在A 中的序号(或位置)为3。

注意：空串是任意串的子串，任意串是其自身的子串子串的位置：通常将子串在主串中首次出现时，该子串首字符对应的主串中的序号，定义为子串在主串中的序号(或位置)。

例如：设A=“This is a string”，B=“is”。

问B 是A 的子串吗？如果是，B 在A 中出现了几次？其位置是几？62. 串的抽象数据定义ADT string {数据对象: D 数据关系: R 基本操作：StrAssign(&S,chars);StrCopy(&S,S1); StrEmpty(&S);StrCompare(S1,S2);StrLength(S); ClearString(&S);Concat(&S,S1,S2); SubString(&Sub,S,pos,len);Index(S,Sub,pos); Replace(&S,Sub,T); StrInsert(&S,pos,Sub); StrDelete(&S,pos,len);DestroyString(&S);}ADT String7§4.2 串的顺序表示和实现串的顺序存储：即用一组地址连续的存储单元存储串值中的字符序列非紧缩格式：一个存储单元中只存放一个字符，所需存储单元个数即是串的长度。

数据结构-4 串数据结构 4 串在计算机科学的广袤世界中，数据结构就像是一座精巧构建的大厦，为我们处理和管理数据提供了坚实的基础。

而在这众多的数据结构中，串（String）是一个十分常见且重要的存在。

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

它在我们的日常生活和计算机程序中无处不在。

比如我们日常输入的文本、网页上的各种字符串信息，甚至是程序代码中的标识符和字符串常量，都属于串的范畴。

从存储结构上来看，串可以有两种主要的存储方式：顺序存储和链式存储。

顺序存储方式就像是一个排列整齐的队列。

我们为串分配一块连续的存储空间，然后按照顺序依次存放串中的字符。

这种方式的优点是随机访问速度快，如果我们想要获取串中的某个特定位置的字符，能够迅速定位并获取。

但它也有缺点，那就是当串的长度发生变化时，尤其是需要增长时，可能会面临重新分配存储空间和数据搬移的操作，这会带来一定的性能开销。

与之相对的链式存储，则像是串起的一颗颗珍珠。

每个节点存储一个字符，并通过指针将各个节点连接起来。

这种方式在串的长度动态变化时，更加灵活，不需要进行大规模的数据搬移。

但它的随机访问速度相对较慢，因为要通过指针依次遍历才能找到特定位置的字符。

在实际应用中，我们常常会用到串的基本操作。

比如串的赋值，将一个串的值赋给另一个串；串的连接，把两个串拼接成一个新的串；串的比较，判断两个串是否相等或者哪个串更大；还有子串的提取，从一个串中取出一部分连续的字符组成新的串。

以串的比较为例，这可不是简单地看两个串的长度或者逐个字符比较那么简单。

在不同的应用场景中，可能会有不同的比较规则。

比如，在不区分大小写的情况下比较两个字符串，或者按照特定的编码规则进行比较。

再来说说串的模式匹配。

这是串处理中的一个重要问题。

想象一下，我们在一篇长篇文章中寻找特定的关键词或短语，这其实就是在进行串的模式匹配。

常见的模式匹配算法有朴素的模式匹配算法和 KMP 算法。