串的概念：串（字符串）：是由 0 個或多個字符組成的有限序列。 通常記為：s =‘ a1 a2 a3 … ai …an ?’ ( n≥0 )。

串的邏輯結構和線性表極為相似。

?

一些串的類型：

?

空串：不含任何字符的串，長度 = 0。

空格串：僅由一個或多個空格組成的串。

子串：由串中任意個連續的字符組成的子序列。

主串：包含子串的串。

位置：字符在序列中的序號。

子串在主串中的位置：子串的首字符在主串中的位置。

?

空串是任意串的子串，任意串是其自身的子串。

串相等的條件：當兩個串的長度相等且各個對應位置的字符都相等時才相等。

?

實現：

?

因為串是特殊的線性表，故其存儲結構與線性表的 存儲結構類似，只不過組成串的結點是單個字符。

?

定長順序存儲表示

也稱為靜態存儲分配的順序串。 即用一組地址連續的存儲單元依次存放串中的字符序列。

?

串長：可能首字符記錄（顯式）或\0結尾（隱式）

?

定長順序存儲表示時串操作的缺點 ：串的某些操作受限（截尾），如串的聯接、插入、置換

?

堆分配存儲表示 ?

?

存儲空間在程序執行過程中動態分配，malloc() 分配一塊實際串長所需要的存儲空間（“堆”）

堆存儲結構的優點：堆存儲結構既有順序存儲 結構的特點，處理（隨機取子串）方便，操作中對 串長又沒有任何限制，更顯靈活，因此在串處理的 應用程序中常被采用。

?

串的塊鏈存儲表示

為了提高空間利用率，可使每個結點存放多個字符 （這是順序串和鏈串的綜合 (折衷) ），稱為塊鏈結構。

?優點：便于插入和刪除 ? ?缺點：空間利用率低?

?

?

?

?