大家好呀，我是你们的帅蛋。
国庆后上班第一天，咋样？
是不是身体在上班，灵魂还在床上？
醒醒！该起来学习了！
今天来讲字符串，本来字符串想直接肝题来着。
不要问我为什么，肯定不是因为懒（shen）惰（kui），只能是我觉得没啥好写的。
后来本蛋的兄弟海狗做了一批丸，我现在又可以了，那句话说的真对，治懒惰不含糖。
我现在不可抑制的洪荒之力，疯狂码字，快来跟我起飞。
什么是字符串？
首先什么是字符串？
字符串是由零个或多个字符组成的有限序列，简称串儿。
这个定义里有两个关键词：“有限”和“序列”：
- “有限”：是指字符串的长度是一个有限的值。
- “序列”：是指字符串的相邻字符有前驱和后继的。
字符串一般记为 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。
字符串到这就讲完辣，本来以为没啥内容可以讲，没想到也讲了这么多。
接下来就是字符串的实战操作了，臭宝们给我点赞在看走起，我要疯狂输出辣。
我是帅蛋，我们下次见辣。
