2006年軟考程序員數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)筆記

3.4答：當(dāng)只設(shè)頭指針時，出隊的時間為1，而入隊的時間需要n，因為每次入隊均需從頭指針開始查找，找到最后一個元素時方可進行入隊操作。若只設(shè)尾指針，則出入隊時間均為1。因為是循環(huán)鏈表，尾指針?biāo)�指的下一個元素就是頭指針?biāo)�指元素，所以出隊時不需要遍歷整個隊列。
第四章：串(包括習(xí)題與答案及要點)

轉(zhuǎn)摘www.Ezikao.com

--------------------------------------------------------------------------------
本章介紹了串的邏輯結(jié)構(gòu)，存儲結(jié)構(gòu)及串上的基本運算，由于在高級語言中已經(jīng)提供了較全善的串處理功能，因此本章的重點是掌握在串上實現(xiàn)的模式匹配算法。同時這也是本章的難點。但是從全書來講，這屬于較簡單的一章內(nèi)容。 

--------------------------------------------------------------------------------
1.串及其運算(領(lǐng)會)(這些內(nèi)容比較容易理解，不用死記)
串就是字符串，是一種特殊的線性表，它的每個結(jié)點僅由一個字符組成。
空串：是指長度為零的串，也就是串中不包含任何字符(結(jié)點)。
空白串：指串中包含一個或多個空格字符的串。不同與空串，它的結(jié)點就是一個空格字符。
在一個串中任意個連續(xù)字符組成的子序列稱為該串的子串，包含子串的串就稱為主串。子串在主串中的序號就是指子串在主串中首次出現(xiàn)的位置。如A="I love you" B="love",則B在A中的序號為3，注意空格也是字符。
空串是任意串的子串，任意串是他自身的子串。
串分為兩種：串常量和串變量。串常量在程序中不能改變，串變量則可以。
關(guān)于串的基本運算，基本上在C語言中已經(jīng)學(xué)過，主要有
求串長strlen(char *s)、
串復(fù)制strcpy(char *to,char *from)、
串聯(lián)接strcat(char *to,char *from)、
串比較charcmp(char *s1,char *s2)
和字符定位strchr(char *s, char c)等
這些基本運算通過練習(xí)來掌握。

--------------------------------------------------------------------------------
2.串的存儲結(jié)構(gòu)(簡單應(yīng)用)
串是特殊的線性表(結(jié)點是字符)，所以串的存儲結(jié)構(gòu)與線性表的存儲結(jié)構(gòu)類似。
串的順序存儲結(jié)構(gòu)簡稱為順序串，順序串又可按存儲分配的不同分為靜態(tài)存儲分配的順序串和動態(tài)存儲分配的順序串。
靜態(tài)的意思可簡單地理解為一個確定的存儲空間，它的長度是不可變的。如直接使用定長的字符數(shù)組來定義一個串。它的優(yōu)點是涉及串長的操作速度快，因為它的最大長度是不變的。
動態(tài)存儲分配就是在定義串時不分配存儲空間，直到需要使用時按所需串的長度分配存儲單元給它，并且在運行中還可以根據(jù)需要變化串的長度，這就是動態(tài)分配。不過這樣的串仍是順序存儲的，也就是說指針指向串的首地址，后面的結(jié)點是連續(xù)存儲的。
串的鏈式存儲就是用單鏈表的方式存儲串值，串的這種鏈式存儲結(jié)構(gòu)簡稱為鏈串。鏈串與單鏈表的差異只是它的結(jié)點數(shù)據(jù)域為單個字符。這種存儲結(jié)構(gòu)方便于串的插入和刪除操作，但是空間利用率不高，因為存放每一個字符要"搭配"一個指向下一字符的地址,而地址所占空間是比較大的。為了解決這種"存儲密度"過低的狀況，可以讓一個結(jié)點存儲多個字符，事實上這是順序串和鏈串的綜合(折衷)。

--------------------------------------------------------------------------------
本章的重點和難點就是串運算的實現(xiàn)，特別是順序串上子串定位的運算。
子串定位運算又稱串的"模式匹配"或"串匹配"，就是在主串中查找出子串出現(xiàn)的位置，這在應(yīng)用中非常廣泛，比如文本編輯中的"查找和替換"用到的就是子串定位運算的算法。
在串匹配中，將主串稱為目標(biāo)(串)，子串稱為模式(串)，我們這樣想象，子串就如同一個模板(樣本)，用它在目標(biāo)上對比，從頭往后比較，凡是遇到一模一樣的那么一段，就算找到一個位置了(我們就說，從這個位置開始的匹配成功)。用很專業(yè)的很酷的話說就是"模式在目標(biāo)中出現(xiàn)"(我想起了警匪片里的對話),如果這個模板對應(yīng)的目標(biāo)串中有不一樣的字符出現(xiàn)，那么這個位置就匹配失敗。
當(dāng)我們用這個模子依次從目標(biāo)的頭部往后移,移動到的位置就叫位移，如果每次向右移動1格，那么每次的位移就加上1。
每次移動后要看看模板里的字符和目標(biāo)中相應(yīng)的字符是否相等，如果都相同，這次位移就叫有效位移(其實就是從這個位置開始的匹配成功)
另外有一個合法位移和不合法位移的概念，就是說，移動一個位置后，如果模板的最后一個字符還沒有超出目標(biāo)串中最后一個字符時，這個位移就是合法位移，如果超出了，那么就沒有比較的意義了，這時就是不合法位移。
這是比較容易理解的，串匹配問題就是找出給定模式串P在給定目標(biāo)串T中首次出現(xiàn)的有效位移或者是全部有效位移。
具體的串匹配算法也不是很難理解，就是用兩個循環(huán)，外循環(huán)用于進行模式的位移，內(nèi)循環(huán)進行模板內(nèi)每個字符的比較(判斷是否有效位移)。關(guān)于串匹配的時間復(fù)雜度，在最壞的情況下就是目標(biāo)串和模式串分別是"a^n-1b"和"a^m-1b"的形式，就是說，每一次合法位移后，在內(nèi)循環(huán)中都要比較m個字符才知道是不是有效位移(前面的字符都是一樣的)。所以最壞的情況下時間復(fù)雜度是O((n-m+1)m),假如m與n同階的話則它是O(n^2)。