写在之前

大家好呀，我是帅蛋。

自从上次更新完栈和队列以后，已经好久没更新数据结构与算法的文章了，赶紧过来补救一下。

今天来学习字符串，这篇是我在牛客网连载系列 #帅蛋的数据结构与算法空间#的第 5 篇文章，欢迎大家关注。

希望我的这种写作方式，可以让你在学习数据结构与算法的时候不觉得无趣，我希望在这个过程中你能喜欢上它。

也希望大家能够喜欢上帅蛋，多多点赞收藏，记得关注我呀！

关于作者

因为误打误撞，在选专业的时候填上了计算机科学与技术，从此在大学开始与编程相爱相杀。

同样误打误撞，大一参加了 ACM，一晃就是两年多，是一个对编程从无感到热爱的距离。

你好，我是帅蛋。

不知名二本出身，ACM 亚洲区域赛银牌选手，以第四名的成绩拿下省赛金牌，后来去了一所软工排名前三的 985 院校读研。

讨厌复杂的环境，现在一家公司做数据分析，关系简单，是个负责人，管十几号人。

喜欢分享，写了很多文章，我秉持“分享是种积极的生活态度”。

以下是正文

说实话，字符串的内容本来不想写来着，在我的认知里感觉字符串都没什么内容。

后来证明是我年轻了，写着写着东西还真不少，赶紧学起来吧！

什么是字符串？

首先什么是字符串？

字符串是由零个或多个字符组成的有限序列，简称串儿。

这个定义里有两个关键词：“有限”和“序列”：

• “有限”：是指字符串的长度是一个有限的值。
• “序列”：是指字符串的相邻字符有前驱和后继的。

字符串一般记为 S = "a1a2a3...an"（n≥0），其中 S 是字符串的名称，ai 是字符串的元素，可以是数字、字母或者其它字符。

字符串里面有几个特殊的概念我需要在这里解释一下：“空串”、“空格串”、“子串”、“主串”。

字符串一般记为 S = "a1a2a3...an"（n≥0），其中 S 是字符串的名称，ai 是字符串的元素，可以是数字、字母或者其它字符。

字符串里面有几个特殊的概念我需要在这里解释一下：“空串”、“空格串”、“子串”、“主串”。

空串：就是由零个字符组成的字符串，串的长度为 0，记为 S = “”。

空格串：就是只包含空格的字符串，空格串是有长度的，可以是 1 个或者多个。

子串：字符串中任意个数的连续字符组成的子序列叫字符串的子串。

主串：包含子串的字符串就是主串。

比如 the 是 father 的子串，father 是主串。

还有一个就是，子串在主串中的位置，一般指的是子串的首字符在主串中的位置。

字符串的存储结构

字符串和线性表的存储结构一样，分为顺序存储和链式存储。

顺序存储

字符串的顺序存储是用一组地址连续的存储单元一次存放字符串中的字符序列。

这里的存储空间是确定的，长度不变的，因此也有叫定长顺序存储。

既然是定长，那就肯定存在一个预定义的最大字符串长度。

有的编程语言保存在数组的 0 下标位置，比如 Pascal 语言，这样方便使用。

有的不想这么搞，觉得麻烦，就在末尾加个结束标记字符，它不计入长度，比如在　C/C++ 中，用 ’\0‘ 表示字符串结束标记。

这种就很不直观，你想知道字符串的长度只能自己遍历一遍。

定长的顺序存储在预定的存储中可以自由的放来放去，超过这个长度的就会被“截断”，即舍弃。

那从这来看，定长的顺序存储很明显存在很大的问题，字符串的操作大多不是涉及单个字符的操作，而是子串和子串的操作，比如字符串和字符串的拼接，一不小心就可能超了定长。

而且定长的顺序存储也不切实际，在实际的工程中是很难估计字符串的最大长度的。

所以对于字符串的存储，只是个定长肯定是不行的，是串儿就得能软能硬，能长能短，随心所欲。

后来大佬们捣鼓了一下，做了改动，不再限定最大长度，开始动态分配字符串的存储空间，很多教材把这个叫做：堆分配存储，即采用动态数组存储字符串。

为什么叫堆分配存储呢？这里得从盘古，呃，从编程语言说起。

一般情况下，编程语言会把程序占有的内存空间分为很多的区域，程序里面包含的数据会被分类存储到对应的区域。

对于我们都很熟悉的 C 语言来说，它将内存分为堆区、栈区、数据区和代码区，那我们这个叫堆分配存储，显然就是分在堆区。

和其它区域不同的是，堆区的内存空间需要我们手动使用 malloc 申请，在不用的时候使用 free 释放。

链式存储

对于字符串的链式存储，就是用链表的形式存储字符串。

关于字符串的链式存储，臭宝们稍微了解就好，毕竟除了连接串等极少数情况稍微好用点以外，大多数情况下，链式存储比起顺序存储来简直就是弟弟。

在这里我用“无头结点的单链表”为例实现字符串的链式存储，当然你可以用“有/无头节点的单/双链表”都可以。

对于字符串的链式存储来说，因为字符串的特殊性，还是区别于线性表，链表的节点可以存储一个字符，也可以存储多个字符。

我以 S = “goudan” 为例，它可以有以下两种存法：

当然对于一个节点存储多少个字符合适，需要根据实际情况去决定，这会影响字符串的处理效率。

字符串的操作

我在上面讲过，由于字符串的特性，它的操作和线性表的操作不同。

字符串的操作不是涉及单个字符的操作，更多的是串和串之间的操作。比如字符串的大小比较，查找子串的位置，替换子串等。

在不同的编程语言里，对串的操作基本都差不多，更多的区别在对字符串操作函数的命名和某些小的细节上。臭宝们在学编程语言的时候，可以再去查一下相应的字符串操作的官方文档。

我在这就不过多赘述，主要就给大家讲一下字符串的大小比较。

字符串的相等是很好界定的，就是相比较的字符串完全一模一样就好了。

字符串既然不像数字那样，那它怎么去比较大小呢？两种情况。

第一种情况：

当字符串长度不相同时，长度相同的地方完全一样，那字符串长的那个字符串大。

比如 a = "goudan"，b = "gou"，那 a > b。

第二种情况：

字符串长度相同的地方就出现了不同的字符，那字符大的那个字符串大。

比如 a = "goudan"，b = “gov”，因为字母 u < v，所以字符串 a < b。

字符串到这就讲完辣，本来以为没啥内容可以讲，没想到也讲了这么多。

如果你觉得我写的对你一点点儿的帮助，记得也要动动小手帮我点个赞呀！

今天的内容就这些，我们下次见啦！

❤️ 欢迎关注我，有问题，找帅蛋，我最看不得别人迷茫！

❤️ 如果你觉得有帮助,希望爱学习的你不要吝啬三连击哟[点赞 + 收藏 + 评论]~

还有小小公众号 【编程文青李狗蛋】，聊聊迷茫吹吹牛皮~