DAY 05 : 字串

5.1 什麼是字串?

字串是由零個或者是由多個字元所組成的有限序列

有稍微碰過程式語言的人應該會知道在撰寫時字串是用雙引號括起來的(也有一些是用單引號)，字串內容可以是字母和數字，也可以是其他字元，零個字元的時候叫做｢空字串(Null String)也可以直接用｢" "表示。
在這邊有兩個觀念要另外說明:
1.空格字串:空格字串並非｢空字串，他是有內容，有長度的，而且也可以有不只一個空格。
2.主字串和子字串:主字串包含子字串，主字串和子字串皆有任一個連續字元，子字串在主字串的位置就是子字串的第一個字元在主字串的序號。
作者有舉了一個我覺得還蠻有趣的例子:
即使是lover裡也有over，即使是friend也有個end，即使是believe裡也有個lie。這句話真的很有說服力XD

5.2 字串的比較

字串的比較是透過組成字串的字元，使用字元之間的編碼來進行比較，通常會使用ASCII和Unicode等常見的編碼。

ASCII:

• 八位元的二進位數字
• 256個字元
  Unicode:
• 十六位元的二進位數字
• 約有65000個字元
• Unicode的前256個字元和ASCII的編碼是一樣的

如果想要在C語言中比較兩個字串是否相同的話:
1.字串長度是否相同
2.對應位置的字元都相等

5.3 字串的儲存結構

字串的邏輯結構和線性串列有點相似，但是字串中的元素都是字元，不過他們兩者的基本操作有很大的差別，字串主要是搜尋子字串位置、得到指定位置子字串，和替換子字串等操作。

5.3.1 字串順序儲存結構

字串順序儲存結構是用一組位置連續的儲存單元來儲存字元序列，按照預定的大小安排一個固定長度的儲存空間(固定長度的陣列)。
字串順序儲存結構有一個缺點:當字串序列的長度超過陣列的最大長度，字串會被截斷，不過有些程式語言可以透過動態分配取得更多的儲存空間。

5.3.2 字串鏈結儲存結構

字串鏈結儲存結構和線性串列的相似，但是由於一個節點只放一個字元實在是太浪費了，所以字串鏈結儲存結構中，一個節點可以放一個也可以放多個字元，若一個節點未被占滿時，可以放入其他非字串值得字元補齊，不過字串鏈結儲存結構的效率並沒有比字串順序儲存結構好。

5.4 KMP字串比對演算法

KMP字串比對比較法是被發明用來避免重複走訪的情形發生。

接下來要來講它的原理:
假設有一個主字串S(abcdefgab....)
一個子字串T(abcdex)
我們可以看到S字串的前五位和T字串的前五位是一樣的，而T字串的第一位為｢a，且在與後面的四位bcde比較後發現並沒有相等，因此a也不可能與S字串中的二到五位相等，因此這段比較的步驟就可以省略。
但是當比對到第六位時會發現兩者是不相等的，所以這個比較的步驟就會被保留下來。

在這邊先提到兩個值，分別是i值和j值:
i值是主字串當前位置的編號
j值是子字串中目前字元(沒重複到的)之前的字串

(不知道為什麼今天在撰寫文章的時候，只要在前方加字，後方的字就會被吞掉，所以有些MarkDown還有"」"無法添加上去，只好等到之後再修改了，還請多多見諒。)