繼續接去年的常見資料結構和算法總結 系列随筆記錄
一、計算機裡進行非數值處理的對象基本上是字元串資料，比處理浮點和整數都要複雜
string串定義：由 0 個或多個 字元 組成的 有限的 序列，通常記為：s =“a1 a2 a3 … ai …an” ( n≥0 ，且n是有限的)。其中的引号不屬于串，隻是一個标記作用！
n就是串的長度，且字元串裡的字元 ai 的值由 字母、數字或其他字元 組成的。
二、字元串為什麼要用雙引号标記
作用：避免字元串與變量名或數的常量混淆。
三、幾個概念
空串：不含任何字元的串，長度 = 0，用符号 f 表示。也就是說空串也是字元串！
空格串：僅由一個或多個空格組成的串。 區分空串和空格串！
子串：由串中任意個連續的字元組成的子序列。空串是任意串的子串，任意串是其自身的子串。
主串：包含子串的串。
字元的位置：字元在序列中的序号。
子串在主串中的位置：子串的首字元在主串中的位置。
串相等：當兩個串的長度相等且各個對應位置的字元都相等時才相等。
四、串的邏輯存儲結構
還是那句話，線性表是資料結構和算法的基礎！很多地方都以線性表為基礎去擴充！同樣，串的邏輯結構和線性表很相似！
串和線性表的差別：串的資料對象，我們約定是字元集，也就是說，字元串是資料受限的！而線性表的資料對象，不一定是字元集！可以存儲整數，浮點數等，都沒問題。
五、串的基本操作
和線性表差别較大。 因為，線性表的基本操作大多以“單個元素”作為操作對象，比如删除一個元素，初始化一個結點，插入一個結點等，而串的基本操作通常以“串這個整體”作為操作對象。比如在串中查找某個子串、在串的某個位置上插入一個子串、删除一個子串，子串的模式比對……
六、字元串的三種存儲結構
串也是一類特殊的線性表，故其存儲結構與線性表的存儲結構類似，隻不過組成串的結點是單個字元而已。
定長順序存儲
也稱為靜态存儲配置設定的順序串。即用一組位址連續的存儲單元依次存放串中的字元序列。“定長”、“靜态”的意思可簡單地了解為一個确定的存儲空間，它的長度是不變的。
串長的表示方法：
1）在串的存貯區首位址顯式地記錄串的長度。 友善使用，一目了然，比如pascal語言。
2）在串之後加結束标志，隐式記錄串的長度，不直覺，如c/c++ 使用 “\0”。這裡使用的是1）中的顯式方式記錄串長度。
字元串this is a dog. 的存儲形式對比，要知道，串的靜态存儲結構（簡單一維數組表示），大小不可變。
注意：
1）串的實際長度可在這個預定義長度的範圍内随意設定，超過預定義長度的串值則被舍去，稱之為“截斷”。
2）字元類型存儲的是對應字元在 ascii 裡的值，10進制表示！
定長順序存儲表示時串操作的缺點 ：
需事先預定義串的最大長度，這在實際的程式運作前是很難估計的。
由于定義了串的最大長度，使得串的某些操作受限（截尾），如串的聯接、插入、置換等運算。
克服辦法：不限定最大長度——動态配置設定串值的存儲空間。
ps：c沒有字元串類型，c的字元串類型實際上是字元數組。而常說的c風格字元串，實際是末尾元素為零的字元數組。其他字元串風格取決于該語言設計思想，如pascall語言為了強化類型管理與簡化實作，字元串類型不要求字元串尾部有特殊字元表示字元串結束，而采用一種資料結構來管理字元串，在字元串頭部分别有兩個字段表示了該字元串的長度和引用計數。這樣，簡單的指針指派直接複制位址并增加引用計數即可。而且字元串長度也不用每次都要重新計算。後來的c++、java等語言都借鑒了這樣的設計思想。
堆配置設定存儲（很重要，經常用）
堆存儲結構的特點：
仍以一組空間足夠大的、位址連續的存儲單元依次存放串值字元序列，但它們的存儲空間是在程式執行過程中動态配置設定的，c 語言中提供的串類型就是以這種存儲方式實作的。
由動态配置設定函數 malloc() 配置設定一塊實際串長所需要的存儲空間（“堆”），如果配置設定成功，則傳回此空間的起始位址，作為串的基址，由 free( ) 釋放串不再需要的空間。
這樣配置設定的字元串，對配置設定的，可以動态改變長度，進行串的複制，插入，連接配接，置換算法等
堆存儲結構的優點：
堆存儲結構既有順序存儲結構的特點，處理（随機取子串）友善，操作中對串長又沒有任何限制，更顯靈活，是以在串處理的應用程式中常被采用。
塊鍊存儲
剛剛的堆配置設定，其實還是順序表的動态配置設定的演化。那麼自然有連結清單的演化，串值也可用單連結清單存儲，簡稱為鍊串。 鍊串與單連結清單的差異隻是它的結點資料域為單個字元。
優點：便于插入和删除 缺點：空間使用率低 ，這裡知道一個公式：
為了提高空間使用率，可使每個結點存放多個字元（這是順序串和鍊串的綜合 (折衷) ），稱為塊鍊結構。 實際應用時，可以根據問題所需來設定結點的大小。例如：在編輯系統中，整個文本編輯區可以看成是一個串，每一行是一個子串，構成一個結點。即：同一行的串用定長結構（80個字元），行和行之間用指針相聯接。
為了便于進行串的操作（連接配接等），當以塊鍊存儲串值時，除頭指針外還可附設一個尾指針訓示連結清單中的最後一個結點，并給出目前串的長度。
先表示塊鍊的結點的結構（這也是這類問題的慣常做法，鍊式的，可以考慮定義單個的結點，然後定義整體的組織，從小到大，由内而外！）
串的連結清單結構
辛苦的勞動，轉載請注明出處，謝謝……
http://www.cnblogs.com/kubixuesheng/p/4116378.html