数据结构和算法 ＜字符串＞（一、介绍字符串）
个人比较喜欢系统学习一个知识，竟然是一个系统学习过程，前面的介绍部分自然不能少，总不能一上来就高潮吧，先来点过渡，也好好整理一个概念。
1.1 串的定义
我们现在常用的搜索引擎，当我们在文本框中输入“数据”时，它已经把我们想要的“数据结构”列在下面了，这个显然就是一个字符串查找匹配的工作。
所以我们就要好好分析字符串这样的数据结构，来看看《大话数据结构》是怎么定义的： 串是由零个或多个字符组成的有限序列，又名叫字符串
一般记为s="a1a2......an" (n≥0)
a就是一个一个的字符，然后把n个字符拼接起来就是字符串，n是字符串的长度，是有限长度的，n也可能为0，为0是就是空串，可以用“”这个表示。
特别注意的是，有一种字符串叫空格串，空格串是有内容的，里面包含着空格，可能不止一个空格。
1.2 串的比较
两个数字，很容易比较大小。2比1大，这完全正确，可是两个字符串如何比较？比如“silly”、“stupid”这样的同样表达“愚蠢的”的单词字符串，它们在计算机中的大小其实取决于它们挨个字母的前后顺序。它们的第一个字母都是“s”，我们认为不存在大小差异，而第二个字母，i<t,我们排序都是按字典序，所以说“silly” < "stupid"。（明确的说应该是按ASCII码表编码的顺序，不过ASCII码表在编码的时候本来就是按字典序的）
1.3 串的存储结构
字符串一般都是用一组地址连续的存储单元来存储的，按照字符串的长度，为字符串变量分配一个固定的存储区。一般我们都是用定长的数组来定义。 既然是定长数组，就存在一个最大串的长度，但是实际字符串的长度不会是最大长度的，所以我们需要把实际的串长度值保存在数组的0下标位置，有的保存在最后一个下标位置（感觉没看到这么用的）。但是c语言就不这么干，c语言在字符串的最后添加一个"\0"表示字符串的结束，我们要想知道字符串的长度，就遍历一次字符串，就知道了长度，确实有点麻烦。
像c语言我们比较喜欢用结构体来封装一个字符串，一个是字符数组，存储字符串，一个是长度，为什么这样呢？是因为如果字符串后面忘记了“\0”，就会出现指针越界，是一个非常危险的事情，所以一般都是封装成一个结构体。
又比如高级语言c++、Java，语言级别就支持了string类型，这个就不用我们操心了，不过底层的封装其实跟c语言是差不多的。
1.4 字母表
一些应用程序可能会对字符串的字母表做出限制，在Java中，会封装一个Alphabet类描述字母表
字母表的API
| public class Alphabet | |
|---|---|
| More ActionsAlphabet(String s) | 根据S中的字符创建一个字母表 |
| char toChar(int index) | 获取字母表中索引位置的字符 |
| int toIndex(char c) | 获取c字符的索引，在0到R-1之间 |
| boolean contains(char c) | c在字母表之中么 |
| int R() | 基数（在字母表中的字符数量） |
| int lgR() | 表示一个索引所需的比特数 |
| int[] toIndices(String s) | 将s转换为R进制的整数 |
| String toChars(int[] indices) | 将R进制的整数转换为基于该字母表的字符串 |
是不是有点懵逼，我为什么写这个，下面我们来看看一个经典的例子就明白了：
public class Count { public static void main(String[] args) { Alphabet alpha = new Alphabet(argc[0]); //生成一个字母表 int R = alpha.R(); //获取字母表的字符数量 int[] count = new int[R]; //申请一个统计字符频率的数组 String S = StdIn.readAll(); //读取字符串 int N = S.length(); //计算字符串 for (int i=0; i<N; i++) { if (alpha.contains(s.charAt(i))) //判断字符是否在字母表中 count[alpha.toIndex(s,charAt(i))]++; //如果在的话，获取下标，然后进行统计 } for (int c=0; c<R; c++) { StdOut.println(alpha.toChar(c) + " " + count[c]); //输出 } } }
作者：善良的小油条
链接：https://juejin.cn/post/7028855944251441166