Ⅰ C++語言中提供有關串的類
第四章：串(包括習題與答案及要點)
本章介紹了串的邏輯結構，存儲結構及串上的基本運算，由於在高級語言中已經提供了較全善的串處理功能，因此本章的重點是掌握在串上實現的模式匹配演算法。同時這也是本章的難點。但是從全書來講，這屬於較簡單的一章內容。
--------------------------------------------------------------------------------
1.串及其運算(領會)(這些內容比較容易理解，不用死記)
串就是字元串，是一種特殊的線性表，它的每個結點僅由一個字元組成。
空串：是指長度為零的串，也就是串中不包含任何字元(結點)。
空白串：指串中包含一個或多個空格字元的串。不同與空串，它的結點就是一個空格字元。
在一個串中任意個連續字元組成的子序列稱為該串的子串，包含子串的串就稱為主串。子串在主串中的序號就是指子串在主串中首次出現的位置。如A="I love you" B="love",則B在A中的序號為3，注意空格也是字元。
空串是任意串的子串，任意串是他自身的子串?
串分為兩種：串常量和串變數。串常量在程序中不能改變，串變數則可以。
關於串的基本運算，基本上在C語言中已經學過，主要有
求串長strlen(char *s)、
串復制strcpy(char *to,char *from)、
串聯接strcat(char *to,char *from)、
串比較charcmp(char *s1,char *s2)
和字元定位strchr(char *s, char c)等
這些基本運算通過練習來掌握。
--------------------------------------------------------------------------------
2.串的存儲結構(簡單應用)
串是特殊的線性表(結點是字元)，所以串的存儲結構與線性表的存儲結構類似。
串的順序存儲結構簡稱為順序串，順序串又可按存儲分配的不同分為靜態存儲分配的順序串和動態存儲分配的順序串。
靜態的意思可簡單地理解為一個確定的存儲空間，它的長度是不可變的。如直接使用定長的字元數組來定義一個串。它的優點是涉及串長的操作速度快，因為它的最大長度是不變的。
動態存儲分配就是在定義串時不分配存儲空間，直到需要使用時按所需串的長度分配存儲單元給它，並且在運行中還可以根據需要變化串的長度，這就是動態分配。不過這樣的串仍是順序存儲的，也就是說指針指向串的首地址，後面的結點是連續存儲的。
串的鏈式存儲就是用單鏈表的方式存儲串值，串的這種鏈式存儲結構簡稱為鏈串。鏈串與單鏈表的差異只是它的結點數據域為單個字元。這種存儲結構方便於串的插入和刪除操作，但是空間利用率不高，因為存放每一個字元要"搭配"一個指向下一字元的地址,而地址所佔空間是比較大的。為了解決這種"存儲密度"過低的狀況，可以讓一個結點存儲多個字元，事實上這是順序串和鏈串的綜合(折衷)。
--------------------------------------------------------------------------------
本章的重點和難點就是串運算的實現，特別是順序串上子串定位的運算。
子串定位運算又稱串的"模式匹配"或"串匹配"，就是在主串中查找出子串出現的位置，這在應用中非常廣泛，比如文本編輯中的"查找和替換"用到的就是子串定位運算的演算法。
在串匹配中，將主串稱為目標(串)，子串稱為模式(串)，我們這樣想像，子串就如同一個模板(樣本)，用它在目標上對比，從頭往後比較，凡是遇到一模一樣的那麼一段，就算找到一個位置了(我們就說，從這個位置開始的匹配成功)。用很專業的很酷的話說就是"模式在目標中出現"(我想起了警匪片里的對話),如果這個模板對應的目標串中有不一樣的字元出現，那麼這個位置就匹配失敗。
當我們用這個模子依次從目標的頭部往後移,移動到的位置就叫位移，如果每次向右移動1格，那麼每次的位移就加上1。
每次移動後要看看模板里的字元和目標中相應的字元是否相等，如果都相同，這次位移就叫有效位移(其實就是從這個位置開始的匹配成功)
另外有一個合法位移和不合法位移的概念，就是說，移動一個位置後，如果模板的最後一個字元還沒有超出目標串中最後一個字元時，這個位移就是合法位移，如果超出了，那麼就沒有比較的意義了，這時就是不合法位移。
這是比較容易理解的，串匹配問題就是找出給定模式串P在給定目標串T中首次出現的有效位移或者是全部有效位移。
具體的串匹配演算法也不是很難理解，就是用兩個循環，外循環用於進行模式的位移，內循環進行模板內每個字元的比較(判斷是否有效位移)。關於串匹配的時間復雜度，在最壞的情況下就是目標串和模式串分別是"a^n-1b"和"a^m-1b"的形式，就是說，每一次合法位移後，在內循環中都要比較m個字元才知道是不是有效位移(前面的字元都是一樣的)。所以最壞的情況下時間復雜度是O((n-m+1)m),假如m與n同階的話則它是O(n^2)。
鏈串上的子串定位運算的不同之處就是位移是結點地址而不是整數。理解一下演算法即可。
真正的應用主要還是要掌握串的基本演算法並用它們構造出可以解決具體問題的簡單演算法。
第四章 串 復習要點
本章復習要點是：
串是一種特殊的線性表，它的結點僅由一個字元組成。
空串與空白串的區別：空串是長度為零的串，空白串是指由一個或多個空格組成的串。
串運算的實現中子串定位運算又稱串的模式匹配或串匹配。
串匹配中，一般將主串稱為目標(串),子串稱為模式(串)。
本章可能出的題型多半為選擇、填空等。
Ⅱ 字元串通常採用的兩種存儲方式是什麼
字元串的兩種最基本的存儲方式是順序存儲方式和鏈接存儲方式，選第三個啦
Ⅲ 順序存儲方式串的基本操作是什麼
1.串聯結concat串聯結concat函數是用T返回由S1和S2聯結而成的新串。由於串長固定，因此超過串長的串值必須捨去，稱為「截斷」。假設S1、S2和T都是SString型的串變數，且串T是由串S1聯結得到的，即串T的值的前一段和串S1的值相等，串T的值的後一段和串S2的值相等，則只要進行相應的「串值復制」操作即可，只是需要約定，對超長部分實施「截斷」操作。基於串S1和S2長度的不同情況，串T值的產生可能有2種情況：①S1［0］＋S2［0］≤MAXSTRLEN時，得到串T的正確結果；②S1［0］＜MAXSTRLEN，而S1［0］＋S2［0］＞MAXSTRLEN時，則將串S2的一部分截斷，得到的串T只包含S2的一個子串；③S1［0］＝MAXSTRLEN時，則得到的串T並非聯結結果，而和串S1相等。在這里僅考慮能正確聯結的情況，即S1［0］＋S2［0］＜MAXSTRLEN，
Ⅳ 請問一下，數據結構中串的順序存儲和鏈接存儲要怎麼實現啊
順序存儲的實現方法：使用數組
鏈接存儲的實現方法：使用指針
Ⅳ 下面關於串的的敘述中，哪一個是不正確的
下面關於串的的敘述中哪一個是不正確的
A串是字元的有限序列
B空串是由空格構成的串
C模式匹配是串的一種重要運算
D串既可以採用順序存儲也可以採用鏈式存儲
答案B