字串
字符串（英語：string），是由零個或多個字符組成的有限序列。一般記為（）。它是編程語言中表示文本的資料型別。
通常以串的整體作為操作對象，如：在串中查找某個子串、求取一個子串、在串的某個位置上插入一個子串以及刪除一個子串等。兩個字符串相等的充要條件是：長度相等，並且各個對應位置上的字符都相等。設p、q是兩個串，求q在p中首次出現的位置的運算叫做模式匹配。串的兩種最基本的存儲方式是順序存儲方式和鏈接存儲方式。
形式理論
[編輯]設Σ是叫做字母表的非空有限集合。Σ的元素叫做「符號」或「字符」。在Σ上的字符串（或字）是來自Σ的任何有限序列。[1]例如，如果Σ = {0, 1}，則0101是在Σ之上的字符串。
字符串的長度是在字符串中字符的數目（序列的長度），它可以是任何非負整數。「空串」是在Σ上的唯一的長度為0的字符串，並被指示為ε或λ。[1][2]
在Σ上的所有長度為n的字符串的集合指示為Σn。例如，如果Σ = {0, 1}則Σ2 = {00, 01, 10, 11}。注意Σ0 = {ε}對於任何字母表Σ。
在Σ上的所有任何長度的字符串的集合是Σ的Kleene閉包並被指示為Σ*。依據Σn,
- 。
例如，如果Σ = {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,…}）是在Σ上的形式語言。
串接和子串
[編輯]「串接」（英語：concatenation）是Σ*上的重要二元運算。對於Σ*中的兩個字符串s和t，它們的串接被定義為在s中的字符序列之後跟隨着t中的字符序列，並被指示為st。例如，Σ = {a, b,…, z}，並且s = bear且t = hug，則st = bearhug而ts = hugbear。
字符串串接是結合性的，但非交換性運算。空串充當單位元；對於任何字符串s，有εs = sε = s。所以，集合Σ*和串接運算形成了幺半群，就是從Σ生成的自由幺半群。此外，長度函數定義了一個從Σ*到非負整數的幺半群同態。
字符串s被稱為是字符串t的「子串」（英語：substring）或「因子」（英語：factor），如果存在（可能為空）字符串u和v使得t = usv。「是其子串」關係定義了在Σ*上的偏序，其最小元是空串。
詞典排序
[編輯]經常需要定義在字符串集合上的次序。如果字符表Σ有一個全序（cf. 字母序），則可以定義在Σ*上的叫做詞典序的全序。注意因為Σ是有限的，總是可以定義在Σ繼而在Σ*上的良好次序。例如，如果Σ = {0, 1}並且0 < 1，則Σ*的詞典次序是ε < 0 < 00 < 000 <…< 011 < 0110 <…< 01111 <…< 1 < 10 < 100 <…< 101 <…< 111…
字符串運算
[編輯]在形式理論中經常出現一些在字符串上的額外運算。它們在條目字符串運算中給出。
字符串數據類型
[編輯]字符串數據類型是建模在形式字符串的想法上的數據類型（Data type）。字符串是幾乎在所有編程語言中都可以實現的非常重要和有用的數據類型。在某些語言中它們可作為基本類型獲得，在另一些語言中做為複合類型獲得。多數高級語言的語法允許用某種方式引用起來的字符串來表示字符串數據類型的實例；這種元字符串叫做「常值」（英語：literal）或「字串常值」（英語：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編程語言中使用這種方法）。[3]或者在前面加入一個整數值來表示它的長度（在Pascal語言中使用這種方法）。
這是一個用NUL結束的字符串的例子，它用10個byte存儲，用ASCII表示法：
| F | R | A | N | K | NUL | k | e | f | w |
| 46 | 52 | 41 | 4E | 4B | 00 | 6B | 66 | 66 | 77 |
上面的字符串的長度為5個字符，但注意它占用6個字節。結束符後的字符沒有任何意義。
這是相同的Pascal字符串：
| length | F | R | A | N | K | k | e | f | w |
| 05 | 46 | 52 | 41 | 4E | 4B | 6B | 66 | 66 | 77 |
當然，可能還有其它的表示法。使用樹和列表可以使得一些字符串操作（如插入和刪除）更高效。
字符串實用程序
[編輯]一些編程語言設計為編寫字符串處理程序更容易編寫。這是一些例子：
很多UNIX實用程序進行簡單的字符串處理，並能用於簡單地編寫一些強大的字符串處理算法。文件和有限流可以像字符串一樣查看。
一些新的編程語言，包括Perl、Python和Ruby，藉助正則表達式來幫助文字處理。
算法
[編輯]這是一些字符串處理算法，在字符串上進行不同的處理：
參見
[編輯]參考資料
[編輯]- ^ 1.0 1.1 Barbara H. Partee; Alice ter Meulen; Robert E. Wall. Mathematical Methods in Linguistics. Kluwer. 1990.
- ^ John E. Hopcroft, Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley. 1979. ISBN 0-201-02988-X. Here: sect.1.1, p.1
- ^ Bryant, Randal E.; David, O'Hallaron, Computer Systems: A Programmer's Perspective 2003, Upper Saddle River, NJ: Pearson Education: 40, 2003 [2019-04-15], ISBN 0-13-034074-X, （原始內容存檔於2007-08-06）