字串

字串

字元串String),是由零個或多個字元組成的有限串列。 s=“a1a2···an”(n>=0)。它是程式語言中表示文本數據類型

通常以串的整體作為操作對象,如:在串中查找某個子串、求取一個子串、在串的某個位置上插入一個子串以及刪除一個子串等。兩個字元串相等的充要條件是:長度相等,並且各個對應位置上的字元都相等。設p、q是兩個串,求q在p中首次出現的位置的運算叫做模式匹配。串的兩種最基本的存儲方式是順序存儲方式和連結存儲方式。

基本介紹

  • 中文名:字元串
  • 外文名:String
基本信息,形式理論,串接和子串,詞典排序,字串運算,

基本信息

字元串String),是由零個或多個字元組成的有限串列。s=“a1a2···an”(n>=0)。它是程式語言中表示文本數據類型
通常以串的整體作為操作對象,如:在串中查找某個子串、求取一個子串、在串的某個位置上插入一個子串以及刪除一個子串等。兩個字元串相等的充要條件是:長度相等,並且各個對應位置上的字元都相等。設p、q是兩個串,求q在p中首次出現的位置的運算叫做模式匹配。串的兩種最基本的存儲方式是順序存儲方式和連結存儲方式。

形式理論

設Σ是叫做字母表非空有限集合。Σ的元素叫做“符號”或“字元”。在Σ上的字元串(或)是來自Σ的任何有限串列。例如,如果Σ = {0, 1},則0101是在Σ之上的字元串。
字元串的長度是在字元串中字元的數目(串列的長度),它可以是任何非負整數。“空串”是在Σ上的唯一的長度為0的字元串,並被指示為ελ
在Σ上的所有長度為n的字元串的集合指示為Σ。例如,如果Σ = {0, 1}則Σ= {00, 01, 10, 11}。注意Σ= {ε}對於任何字母表Σ。
在Σ上的所有任何長度的字元串的集合是Σ的Kleene閉包並被指示為Σ*。依據
,。例如,如果Σ = {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,…})是在Σ上的形式語言。

串接和子串

“串接”是Σ*上的重要二元運算。對於Σ*中的兩個字元串st,它們的串接被定義為在s中的字元串列之後跟隨著t中的字元串列,並被指示為st。例如,Σ = {a, b,…, z},並且s=bear且t=hug,則st=bearhug而ts=hugbear。
字元串串接是結合性的,但非交換性運算。空串充當單比特;對於任何字元串s,有εs=sε =s。所以,集合Σ*和串接運算形成了么半群,就是從Σ生成的自由么半群。此外,長度函式定義從Σ*到非負整數的么半群同態。
字元串s被稱為是字元串t的“子串”或“因子”,如果存在(可能為空)字元串uv使得t=usv。“是其子串”關係定義了在Σ*上的偏序,其最小元是空串。

詞典排序

經常需要定義在字串集合上的次序。如果字元表Σ有一個全序(cf.字母序),則可以定義在Σ*上的叫做詞典序的全序。注意因為Σ是有限的,總是可以定義在Σ繼而在Σ*上的良好次序。例如,如果Σ = {0, 1}並且0 < 1,則Σ*的詞典次序是ε < 0 < 00 < 000 <…< 011 < 0110 <…< 01111 <…< 1 < 10 < 100 <…< 101 <…< 111…

字串運算

在形式理論中經常出現一些在字串上的額外運算。它們在條目字元串運算中給出。

相關詞條

熱門詞條

聯絡我們