4.1 串的類型定義

4.1.1 串的基本概念

字符串（簡稱為串），是由n（n≥0）個字符組成的有限序列。從邏輯結構看，串是一種特殊的線性結構，即串可以看成是每個數據元素僅由一個字符組成的線性結構。串一般記為

s="c1c2…ci…cn"

其中：s是串名，也稱為串變量；i（1≤i≤n）稱為字符ci在串中的序號；雙引號內的字符序列稱為串值；一個串中包含的字符個數n稱為串的長度，簡稱串長。長度n為0的串稱為空串，即空串不包含任何字符。包含一個及以上空白字符的串稱為空白串。需要說明的是，空串和空白串是不同的。空串不包含任何字符，長度為0；空白串是由一個或多個空白字符所組成的字符串，其長度是空白字符的個數。

串中任意個連續的字符組成的子序列稱為該串的子串，包含子串的串相應地稱為主串。注意，空串是任意串的子串，任意串是其自身的子串。字符在串中的位置是指字符在串中的序號。子串在主串中的位置則以子串在主串中首次出現時的第一個字符在主串中的位置來表示。例如，設有s1，s2，s3，s4，s5五個串：

        s1="This is a string"
        s2="string"
        s3=" "
        s4=""
        s5="string"

封面

串相等是指兩個串的長度相等，并且各個對應位置的字符均相同。上面五個串中的s2和s5是相等的兩個串。

4.1.2 串的抽象數據類型描述

按照串的定義，串實際上是線性結構的一種。它與一般線性表的不同之處在于，其每個數據元素的類型一定為字符型，而不能為其他類型。根據串的特性及其在實際問題中的應用，可以抽象出串的一些基本操作，它們與串的定義一起構成了串的抽象數據類型。

串的抽象數據類型定義如下：

      ADT String{
          數據對象：D={ai|ai∈CharacterSet，i=1，2，…，n，n＞=0}
          數據關系：R={＜ai-1，ai＞|ai-1，ai∈D，i=2，…，n}
      基本操作：
          StrAssign（&S，chars）：串的賦值操作，將已知的串常量chars的值賦給串S。
          StrCopy（&T，S）：串拷貝操作，將已知串S復制給串T。
          StrEmpty（S）：串判空操作，若已知串S為空串，則返回真，否則返回假。
          StrCompare（S，T）：串比較操作，比較兩個已知的串S和串T。若S＞T，則返回大于 0的值；若S=
                T，則返回 0；若S＜T，則返回小于 0的值。
          StrLength（S）：求串長度操作，返回已知串S中所包括元素的個數。
          ClearString（&S）：串的置空操作，將已經存在的串S置為空串。
          Concat（&T，S1，S2）：串聯接操作，將已知串S2 聯接到串S1的后面形成一個新串T。

          SubString（&Sub，S，pos，len）：截取子串操作，用Sub返回串S的第pos個字符起長度為len的子
              串。其中：1≤pos≤StringLength（S）且 0≤len≤StingLength（S）-pos+1。
          Index（S，T，pos）：子串定位操作，在已知非空串S中從pos位置開始去搜索與已知串T相等的子
              串，若搜索成功，則返回串T在串S中的位置，否則返回 0。其中：1≤pos≤StringLength（S）。
          Replace（&S，T，V）：串替換操作，用已知串V替換掉已知非空串S中出現的所有與串T相等的不重
              疊的子串。
          StrInsert（&S，pos，T）：串的插入操作，在已知串S的第pos個字符之前插入一個已知串T。其中：
              1≤pos≤StringLength（S）+1。
          StrDelete（&S，pos，len）：串的刪除操作，從已知串S中刪除第pos個字符起長度為len的子串。
              其中：1≤pos≤StingLength（S）-len+1。
          DestroyString（&S）：串的銷毀操作，將已知存在的串S銷毀。
          StrPrint（S）：串的輸出操作，將已知串S中的內容輸出。
      }ADT String

上述抽象數據類型定義在實現時需要考慮串的具體的存儲結構。