字符串
| 字符串 | |
|---|---|
| 术语名称 | 字符串 |
| 英语名称 | string |
| 别名 | 串 |
字符串(string)是计算机科学领域及编程语言中处理文字信息的数据类型，可以字面理解为“一串字符”或“字符的串”。字符串是由零到多个字符构成的有限序列，可以将字符串看作元素为字符的线性表。
字符串这一数据类型在不同编程语言中有不同处理。由于连续范围表示中存在头尾和头加长度两种，根据不同编程语言，字符串的具体实现也存在指定长度的数组（即字符的静态数组）和以空字符结尾字符串（即字符的有哨兵线性表）两种。在一些语言中，字符串是基本类型，而在另一些语言中，字符串不被视为基本类型，而是元素为字符的数组。在一些语言中，字符串被视为普通的字符线性表，允许自身可变的操作，而在另一些语言中，字符串被视为一个整体进行同一操作，对内存的读写操作通过写时复制机制进行。
定义
对集合 [math]\displaystyle{ \Sigma }[/math] ，其中含有有限个不同的符号，称为字母表(alphabet)，集合上的序列称为集合 [math]\displaystyle{ \Sigma }[/math] 上的字符串(string over [math]\displaystyle{ \Sigma }[/math] )，其中的每个序列元素称为字符串的字符(character)。
由集合 [math]\displaystyle{ \Sigma }[/math] 中 [math]\displaystyle{ n }[/math] 个符号构成的全体字符串集合，与 [math]\displaystyle{ \Sigma }[/math] 的 [math]\displaystyle{ n }[/math] 次笛卡尔幂结构相同，但其中每个元组的元素被依次序连接为一个字符串，也使用相同符号记作 [math]\displaystyle{ \Sigma^n }[/math] 。对全体自然数 [math]\displaystyle{ n }[/math] 的字符串构成的集合称为 [math]\displaystyle{ \Sigma }[/math] 上的字符串集(string set over [math]\displaystyle{ \Sigma }[/math] )，记作 [math]\displaystyle{ \Sigma^* }[/math] ，其中星号这一运算符被称为 Kleene 闭包运算符。
| 集合符号 | 作为笛卡尔幂表示 | 作为字符串集表示 |
|---|---|---|
| [math]\displaystyle{ \Sigma }[/math] | - | [math]\displaystyle{ \{0,1\} }[/math] |
| [math]\displaystyle{ \Sigma^0 }[/math] | [math]\displaystyle{ \{()\} }[/math] | [math]\displaystyle{ \{\varepsilon\} }[/math] |
| [math]\displaystyle{ \Sigma^1 }[/math] | [math]\displaystyle{ \{0,1\} }[/math] | [math]\displaystyle{ \{0,1\} }[/math] |
| [math]\displaystyle{ \Sigma^2 }[/math] | [math]\displaystyle{ \{(0,0),(0,1),(1,0),(1,1)\} }[/math] | [math]\displaystyle{ \{00,01,10,11\} }[/math] |
| …… | ||
| [math]\displaystyle{ \Sigma^* }[/math] | - | [math]\displaystyle{ \{\varepsilon,0,1,00,01,10,11,\cdots\} }[/math] |
数据类型
逻辑结构
与数组相同，其他术语见数组（数据结构）#逻辑结构。
可变字符串与不可变字符串
一般来说不同的编程语言中，字符串有可变(mutable)与不可变(immutable)两种实现方式。
可变字符串是指编程语言中的一种字符串，创建后仍然可以继续修改，也就是说字符串可以像一般的数组一样修改其中指定位置的字符。
不可变字符串是指编程语言中的一种字符串，创建后的值就是固定的，只会通过复制新字符串进行修改。基本字符串不可变的语言，很多会同时提供一个可变版本的字符串。
尽管不可变字符串会在有大量写操作时会引入大量复制操作，但是在并发读的时候总是能保证线程安全，在字符串本身的实现更加简单，进行并发编程也更容易。
字符编码区别
主条目：字符编码
字符串的每个字符都要通过某种字符编码映射到二进制数据，以作为这一数据类型中被存储的数据。 传统上，以及一些较早期的编程语言中，字符串中每个字符都是用单个字节编码的，且更早期时只需要容许保存机器支持的字符，长度与机器设计字节有关，典型情况下包括 ASCII 或 EBCDIC 等。
对于不只包括英语字母和数字的情况下，也会使用 ISO 8859 系列在内的编码。
由于现代跨语言以及 CJK 区域对更多码位的要求，现代也会使用 Unicode 的某种编码作为默认字符编码，比如 UTF-8 。在这些编码中，字符串每个字符的长度存在差异，也就是说在这类变长字符的字符串中，地址下标和字符下标是有差异的，直接索引字符串中的下标不代表可以获得指定位置上的字符，有可能会取得错误位置上的字符，也可能会取得一个不完整的字符信息。
字符串长度区别
一类实现中，字符串通过其开始地址与长度标记字符串范围，根据长度是否可变，可能是定长字符串(fixed-length string)（类似静态数组）或变长字符串(variable-length string)（类似动态数组）。通常都与对应的线性表结构实现类似。
实际表示
空字符结尾字符串
一类实现中，字符串通过其开始地址与某个结尾哨兵元素标记字符串范围，哨兵元素是某个不允许正常出现在字符串内容中的字符，比如空字符，这种字符串称为空字符结尾字符串(null-terminated string)。由于这也是 C 语言中字符欻你的表达方式，也被称为 C 语言风格字符串(C string)。空字符结尾字符串也常常出现在定长或变长字符串所给定的内存空间（称为缓冲区(buffer)）中，通过结尾的空字符指定字符串的真实长度。
由于必须以一个额外字符结尾，空字符结尾字符串必须多保存额外的字符来标记，因为对于缓冲区长度要求至少比所需要容纳的内容多一个字符。当结尾字符丢失或者长度超出缓冲区时，就可能造成读写缓冲区外的内容，一般称为缓冲区溢出。
其他结尾字符串
一类实现中，由于不同语言或硬件上的历史硬件软件习惯，可能采取不出现在正常字符串中的数据内容作为字符串的固定结尾，比如特殊的字符或特殊的位标记。其他与上述空字符结尾字符串相同。
长度标记字符串
一类实现中，字符串被描述为一个开始地址和一个长度。这类方法有些类似于动态数组中用开始和长度标记数组有数据范围的方法。通常会对用户隐藏实现。
长度前缀字符串
一类实现中，字符串被描述为一个开始地址。类似长度标记字符串，但是长度不是在字符串的描述中，而是放在字符串开始地址中，后面紧接着对应长度的字符串内容。也可以理解为字符串的地址指向一段所占有的内存，这段分为两部分，有一个信息头结构，其中只含有一个长度信息，后续是字符串内容。由于这种风格在 Pascal 方言中使用，这种字符串也称为 Pascal 风格字符串（Pascal string, P string）。
其他表示方式
池化
一些实现使用缓存池化技术，短字符串被放在缓存池里的同一实例中，每个字符串的内部存放在缓存池中的编号。
短字符串优化
对于需要地址和长度两个字段的字符串表示，对于字符串足够短时，一些实现指定某个标识位，存在的时候字符串内部直接放置字符串内容，而不直接使用指针指向内容。称为短字符串优化。
特殊实现
其他编码包括游程编码等压缩字符编码或纠错码等。
字符串是线性表，所以理论上也存在单向链表等数据结构的实现。此外，还有专门用于编辑器等场景的字符串表示方式。