查看“︁字符串”︁的源代码

{{noteTA
|T=zh-hans:字符串; zh-hant:字串;
|G1=IT
|1=zh:常值; zh-hans:字面值; zh-hant:常值;
|2=zh:字串常值; zh-hans:字符串字面值; zh-hant:字串常值;
}}
'''字符串'''（{{lang-en|string}}），是由零个或多个[[字符]]组成的有限序列。一般记为<math>s=a_1 a_2\dots a_n</math>（<math>0\leq n \lneq\infty</math>）。它是[[编程语言]]中表示[[文本]]的[[資料型別|-{zh-hans:数据类型; zh-hant:資料型別;}-]]。

通常以串的整体作为操作对象，如：在串中查找某个子串、求取一个子串、在串的某个位置上插入一个子串以及删除一个子串等。两个字符串相等的充要条件是：长度相等，并且各个对应位置上的字符都相等。设p、q是两个串，求q在p中首次出现的位置的运算叫做模式匹配。串的两种最基本的存储方式是顺序存储方式和链接存储方式。

== 形式理论 ==
设Σ是叫做[[字母表 (计算机科学)|字母表]]的[[空集|非空]][[有限集合|有限]][[集合 (數學)|集合]]。Σ的元素叫做“符号”或“字符”。在Σ上的'''字符串'''（或'''字'''）是来自Σ的任何有限[[序列]]。<ref name="partee">{{cite book |author1=Barbara H. Partee |author2=Alice ter Meulen |author3=Robert E. Wall |title=Mathematical Methods in Linguistics |publisher=Kluwer |year=1990}}</ref>例如，如果Σ = {0, 1}，则''0101''是在Σ之上的字符串。

字符串的长度是在字符串中字符的数目（序列的长度），它可以是任何[[非负整数]]。“[[空串]]”是在Σ上的唯一的长度为0的字符串，并被指示为''ε''或''λ''。<ref name="partee"/><ref>{{cite book| author=John E. Hopcroft, Jeffrey D. Ullman| title=Introduction to Automata Theory, Languages, and Computation| url=https://archive.org/details/trent_0116301269779| year=1979| publisher=Addison-Wesley| isbn=0-201-02988-X}} Here: sect.1.1, p.1</ref>

在Σ上的所有长度为''n''的字符串的集合指示为Σ<sup>''n''</sup>。例如，如果Σ = {0, 1}则Σ<sup>2</sup> = {00, 01, 10, 11}。注意Σ<sup>0</sup> = {ε}对于任何字母表Σ。

在Σ上的所有任何长度的字符串的集合是Σ的[[Kleene星号|Kleene闭包]]并被指示为Σ*。依据Σ<sup>''n''</sup>, 
:<math>\Sigma^{*} = \bigcup_{n=0}^{\infty}\Sigma^{n}</math>。
例如，如果Σ = {0, 1}，则Σ* = {ε, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011,…}。尽管Σ*自身是[[可数集合|可数无限]]的，Σ*的所有元素都有有限长度。

在Σ上一个字符串的集合（就是Σ*的任何[[子集]]）被称为在Σ上的[[形式语言]]。例如，如果Σ = {0, 1}，则带有偶数个零的字符串的集合（{ε, 1, 00, 11, 001, 010, 100, 111, 0000, 0011, 0101, 0110, 1001, 1010, 1100, 1111,…}）是在Σ上的形式语言。

=== 串接和子串 ===
“[[串接]]”（{{lang-en|''concatenation''}}）是Σ*上的重要[[二元运算]]。对于Σ*中的两个字符串''s''和''t''，它们的串接被定义为在''s''中的字符序列之后跟随着''t''中的字符序列，并被指示为''st''。例如，Σ = {a, b,…, z}，并且''s'' = <tt>bear</tt>且''t'' = <tt>hug</tt>，则''st'' = <tt>bearhug</tt>而''ts'' = <tt>hugbear</tt>。

字符串串接是[[结合律|结合性]]的，但非[[交换律|交换性]]运算。空串充当[[单位元]]；对于任何字符串''s''，有ε''s'' = ''s''ε = ''s''。所以，集合Σ*和串接运算形成了[[幺半群]]，就是从Σ生成的[[自由幺半群]]。此外，长度函数定义了一个从Σ*到非负整数的[[幺半群同态]]。

字符串''s''被称为是字符串''t''的“[[子串]]”（{{lang-en|''substring''}}）或“因子”（{{lang-en|''factor''}}），如果存在（可能为空）字符串''u''和''v''使得''t'' = ''usv''。“是其子串”[[二元关系|关系]]定义了在Σ*上的[[偏序]]，其[[最小元]]是空串。

=== 词典排序 ===
经常需要定义在字符串集合上的次序。如果字符表Σ有一个[[全序]]（cf. [[字母序]]），则可以定义在Σ*上的叫做[[词典序]]的[[全序]]。注意因为Σ是有限的，总是可以定义在Σ继而在Σ*上的良好次序。例如，如果Σ = {0, 1}并且0 < 1，则Σ*的词典次序是ε < 0 < 00 < 000 <…< 011 < 0110 <…< 01111 <…< 1 < 10 < 100 <…< 101 <…< 111…

=== 字符串运算 ===
在形式理论中经常出现一些在字符串上的额外运算。它们在条目[[字符串运算]]中给出。

== 字符串数据类型 ==

'''字符串数据类型'''是建模在形式字符串的想法上的[[数据类型]]（{{lang|en|Data type}}）。字符串是几乎在所有[[编程语言]]中都可以实现的非常重要和有用的数据类型。在某些语言中它们可作为[[基本类型]]获得，在另一些语言中做为[[复合类型]]获得。多数高级语言的[[语法]]允许用某种方式引用起来的字符串来表示字符串数据类型的实例；这种元字符串叫做“常值”（{{lang-en|''literal''}}）或“[[字串常值]]”（{{lang-en|''string literal''}}）。

=== 字符串长度 ===

尽管形式字符串可以有任意（但有限）的长度，实际语言的字符串的长度经常被限制到一个人工极大值。一般的说，有两种类型的字符串数据类型：“定长字符串”，它有固定的极大长度并且不管是否达到了这个极大值都使用同样数量的内存；和“变长字符串”，它的长度不是专断固定的并且依赖于实际的大小使用可变数量的内存。在现代[[编程语言]]中的多数字符串是变长字符串。尽管叫这个名字，所有变长字符串还是在长度上有个极限，一般的说这个极限只依赖于可获得的内存的数量。

=== 字符编码 ===

历史上，字符串数据类型为每个字符分配一个[[字节]]，尽管精确的字符集随着区域而改变，[[字符编码]]足够类似得程序员可以忽略它—同一个系统在不同的区域中使用的字符集组要么让一个字符在同样位置，要么根本就没有它。这些字符集典型的基于[[ASCII]]码或[[EBCDIC]]码。

[[意音文字]]的语言比如[[汉语]]、[[日语]]和[[朝鲜语]]（合称为[[CJK]]）的合理表示需要多于256个字符（每字符一个字节编码的极限）。常规的解决涉及：保持对[[ASCII]]码的单字节表示，并使用双字节来表示CJK[[字形]]。现存代码在用到它们会导致一些字符串匹配和切断上的问题，严重程度依赖于字符编码是如何设计的。
# 某些编码比如[[EUC]]家族保证在ASCII码范围内的字节值只表示ASCII字符，使得使用这些字符作为字段分隔符的系统得到编码安全。其他编码如[[ISO-2022]]和[[Shift-JIS]]不做这种担保，使得基于字节的代码做的匹配不安全。
# 另一个问题是如果一个字符串的开头被删除了，对解码器的重要指示或关于在多字节序列中的位置的信息可能就丢失了。
# 另一个问题是如果字符串被连接到一起（特别是在被不知道这个编码的代码截断了它们的结尾之后），第一个字符串可能不能导致编码器进入适合处理第二个字符串的状态中。

[[Unicode]]也有些复杂的问题。多数语言有Unicode字符串数据类型（通常是[[UTF-16]]，因为它在Unicode补充位面介入之前就被增加了）。在Unicode和本地编码之间转换要求理解本地编码，这对于现存系统要一起传输各种编码的字符串而又没有实际标记出它们用了什么编码就是个问题。

=== 实现 ===

某些语言如[[C++]]把字符串实现为可以用于任何[[基本类型]]的[[泛型|模版]]，但这是个例外而不是规则。

在一个面向对象语言把字符串表示为对象的情况下，如果值可以在运行期变更，则叫做“可变的”（mutable），如果值在建立后就不可变更了，则叫做“不变的”（immutable）。例如，[[Ruby]]有可变字符串，而[[Python]]的字符串是不可变的。

其他语言，最著名的有[[Prolog]]和[[Erlang]]，避免实现字符串数据类型，转而采用把字符串表示为字符代码的列表的约定。

=== 表示法 ===
一种常用的表示法是使用一个[[字符代码]]的[[数组]]，每个字符占用一个字节（如在[[ASCII]]代码中）或两个字节（如在[[unicode]]中）。它的长度可以使用一个结束符（一般是[[NUL]]，ASCII代码是0，在[[C编程语言]]中使用这种方法）。<ref>{{Citation
 |last        = Bryant
 |first       = Randal E.
 |author-link = Randal Bryant
 |last2       = David
 |first2      = O'Hallaron
 |title       = Computer Systems: A Programmer's Perspective
 |place       = Upper Saddle River, NJ
 |publisher   = Pearson Education
 |year        = 2003
 |edition     = 2003
 |url         = http://csapp.cs.cmu.edu/
 |isbn        = 0-13-034074-X
 |page        = 40
 |deadurl     = yes
 |archiveurl  = https://web.archive.org/web/20070806075942/http://csapp.cs.cmu.edu/
 |archivedate = 2007-08-06
 |df          = 
 |accessdate  = 2019-04-15
}}</ref>或者在前面加入一个[[整数]]值来表示它的长度（在[[Pascal語言|Pascal]]语言中使用这种方法）。

这是一个用NUL结束的字符串的例子，它用10个[[整数数据类型|byte]]存储，用ASCII表示法：

{| class="wikitable" style="margin-left: auto; margin-right:auto;"
|-
| F  || R  || A  || N  || K
| <small>NUL</small>
| style="background: #DDD" | k
| style="background: #DDD" | e
| style="background: #DDD" | f
| style="background: #DDD" | w
|-
| 46 || 52 || 41 || 4E || 4B
| 00
| style="background: #DDD" | 6B
| style="background: #DDD" | 66
| style="background: #DDD" | 66
| style="background: #DDD" | 77
|}

上面的字符串的长度为5个字符，但注意它占用6个字节。结束符后的字符没有任何意义。

这是相同的Pascal字符串：

{| class="wikitable" style="margin-left: auto; margin-right:auto"
|-
| <small>length</small>
| F  || R  || A  || N  || K
| style="background: #DDD" | k
| style="background: #DDD" | e
| style="background: #DDD" | f
| style="background: #DDD" | w
|-
| 05
| 46 || 52 || 41 || 4E || 4B
| style="background: #DDD" | 6B
| style="background: #DDD" | 66
| style="background: #DDD" | 66
| style="background: #DDD" | 77
|}

当然，可能还有其它的表示法。使用[[树 (图论)|树]]和[[列表]]可以使得一些字符串操作（如插入和删除）更高效。

== 字符串实用程序 ==
一些编程语言设计为编写字符串处理程序更容易编写。这是一些例子：
* [[awk]]
* [[Icon编程语言|Icon]]
* [[perl]]
* [[MUMPS]]
* [[sed]]
* [[SNOBOL]]

很多[[UNIX]]实用程序进行简单的字符串处理，并能用于简单地编写一些强大的字符串处理算法。文件和有限流可以像字符串一样查看。

一些新的[[编程语言]]，包括[[Perl]]、[[Python]]和[[Ruby]]，借助[[正则表达式]]来帮助文字处理。

== 算法 ==
这是一些字符串处理[[算法]]，在字符串上进行不同的处理：
* [[字符串查找算法]]
* [[排序算法]]
* [[正则表达式|正则表达式算法]]
* [[模式匹配]]

== 参见 ==
* [[string (C++标准库)|string]] —— C++字符串处理
* [[string.h]] —— C语言字符串处理
* [[空字符串]]
* [[正则表达式]]

==参考资料==
{{Reflist|2}}

{{字符串}}
{{数据类型}}
{{Data structures}}

{{DEFAULTSORT:Z}}
[[Category:字符串| ]]
[[Category:字符编码]]
[[Category:数据类型]]
[[Category:形式语言]]
[[Category:词语组合]]
[[Category:語法實體]]
[[Category:字符串算法]]