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

(答案及點(diǎn)評(píng)) 3.4 設(shè)長(zhǎng)度為n的鏈隊(duì)用單循環(huán)鏈表表示，若設(shè)頭指針，則入隊(duì)出隊(duì)操作的時(shí)間為何? 若只設(shè)尾指針呢? 

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

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

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

--------------------------------------------------------------------------------
1.串及其運(yùn)算(領(lǐng)會(huì))(這些內(nèi)容比較容易理解，不用死記)
串就是字符串，是一種特殊的線性表，它的每個(gè)結(jié)點(diǎn)僅由一個(gè)字符組成。
空串：是指長(zhǎng)度為零的串，也就是串中不包含任何字符(結(jié)點(diǎn))。
空白串：指串中包含一個(gè)或多個(gè)空格字符的串。不同與空串，它的結(jié)點(diǎn)就是一個(gè)空格字符。
在一個(gè)串中任意個(gè)連續(xù)字符組成的子序列稱為該串的子串，包含子串的串就稱為主串。子串在主串中的序號(hào)就是指子串在主串中首次出現(xiàn)的位置。如A="I love you" B="love",則B在A中的序號(hào)為3，注意空格也是字符。
空串是任意串的子串，任意串是他自身的子串。
串分為兩種：串常量和串變量。串常量在程序中不能改變，串變量則可以。
關(guān)于串的基本運(yùn)算，基本上在C語(yǔ)言中已經(jīng)學(xué)過(guò)，主要有
求串長(zhǎng)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)等
這些基本運(yùn)算通過(guò)練習(xí)來(lái)掌握。

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

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