數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)概念

1、第一章 緒論程序設(shè)計的一般過程是“問題想法算法程序” ，其實質(zhì)是數(shù)據(jù)表示和數(shù)據(jù)處理。數(shù)據(jù)結(jié)構(gòu)是研究非數(shù)值問題中計算機的操作對象以及它們之間關(guān)系和操作的學(xué)科。數(shù)據(jù)元素是數(shù)據(jù)的基本單位，在計算機程序中通常作為一個整體進(jìn)行考慮和處理。數(shù)據(jù)項是數(shù)據(jù)的最小單位，數(shù)據(jù)元素是討論數(shù)據(jù)結(jié)構(gòu)時涉及的最小數(shù)據(jù)單位。從邏輯關(guān)系上講， 數(shù)據(jù)結(jié)構(gòu)主要分為集合， 線性結(jié)構(gòu)，樹結(jié)構(gòu)，圖結(jié)構(gòu)。數(shù)據(jù)的內(nèi)存結(jié)構(gòu)主要有順序存儲結(jié)構(gòu)，鏈接存儲結(jié)構(gòu)兩種基本方法，不論哪種存儲結(jié)構(gòu)，都要存儲兩方面的內(nèi)容 :數(shù)據(jù)元素和數(shù)據(jù)元素之間的關(guān)系。算法具有五個特性分別是有零個或多個輸入，有一個或多個輸出，有窮性，確定性，可行性。算法的描述方法通常有自

2、然語言，程序設(shè)計語言，流 程圖和偽代碼，其中偽代碼被稱為算法語言。在一般情況下，一個算法的時間復(fù)雜度是問題規(guī)模的 函數(shù)。順序存儲結(jié)構(gòu)中數(shù)據(jù)元素之間的邏輯關(guān)系是由存儲位 置表示的，鏈接存儲結(jié)構(gòu)中的數(shù)據(jù)元素之間的邏輯關(guān) 系是由指針表示的?？梢杂贸橄髷?shù)據(jù)類型定義一個完整的數(shù)據(jù)元素。算法指的是對特定問題求解步驟的一種描述，是指令 的有限序列。算法分析的目的是分析算法的效率以求改進(jìn)，算法分 析的兩個主要方面是數(shù)據(jù)復(fù)雜性和程序復(fù)雜性。時間復(fù)雜度要通過算法中基本語句執(zhí)行次數(shù)的數(shù)量級 來確定。邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的內(nèi)容和形式無關(guān)。順序存儲結(jié)構(gòu)的特點是用元素在存儲器中的相對位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系，鏈

3、接存儲結(jié)構(gòu)的特點是用指示元素存儲地址的指針表示數(shù)據(jù)元素之間的邏輯關(guān)系。算法在發(fā)生非法操作時可以做出處理的特性稱為健壯性。常見的算法時間復(fù)雜度用大O 記號表示為：常數(shù)階0(1),對數(shù)階O(log2n),線性階O(n),平方階O(nA2), 指數(shù)階0(2An)第二章 線性表對順序表和單鏈表的比較要考慮時間性能和空間性能兩個方面。作為一般規(guī)律，若線性表需頻繁查找卻很少進(jìn)行插入和是刪除操作，或其操作和“數(shù)據(jù)元素在線性表中的位置”密切相關(guān)時，宜采用順序表作為存儲結(jié)構(gòu)；若線性表需頻繁進(jìn)行插入和刪除操作，則宜采用單鏈表作為存儲結(jié)構(gòu)；當(dāng)線性表元素個數(shù)變化較大或者未知時，最好使用單鏈表實現(xiàn)；若用戶事先知道線性表

4、的大致長度， 使用順序表的空間效率會更高。對于順序表，在等概率情況下，插入和刪除一個元素平均需移表長的一半個元素，具體移動元素的個數(shù)與表長和該元素在表中的位置有關(guān)。單鏈表中設(shè)頭結(jié)點的作用是為了方便運算。一個具有 n 個結(jié)點的單鏈表，在指針 p 所指結(jié)點后插入一個新結(jié)點的時間復(fù)雜度為 O（ 1） ；在給定值為 x的結(jié)點后插入一個新結(jié)點的時間復(fù)雜度為 O （ n） 。可有一個尾指針唯一確定的鏈表有循環(huán)單鏈表，循環(huán)雙鏈表，雙鏈表。線性表的順序存儲是一種隨機存取的存儲結(jié)構(gòu)，線性表的鏈接存儲結(jié)構(gòu)是一種順序存取的存儲結(jié)構(gòu)。線性表采用鏈接存儲時，其地址連續(xù)與否都可以。單循環(huán)鏈表的主要優(yōu)點是從表中任一結(jié)點出發(fā)

5、都能掃描到整個鏈表。鏈表不具有的特點是可隨機訪問任一元素。若某線性表中最常用的操作是去取第 i 個元素和找第 i個元素的前趨，則采用順序表存儲節(jié)省時間。若鏈表中最常用的操作在最后一個結(jié)點之后插入一個結(jié)點和刪除一個結(jié)點，則采用帶尾指針的單循環(huán)鏈表存儲方法最節(jié)省時間。若鏈表最常用的操作是在最后一個結(jié)點之后插入一個結(jié)點和刪除最后一個結(jié)點，則采用循環(huán)雙鏈表存儲方法最節(jié)省時間。對于 n 個元素組成的線性表，建立一個有序單鏈表的時間復(fù)雜度是O (nA2).使用雙鏈表存儲線性表，其優(yōu)點是可以更方便數(shù)據(jù)的插入和刪除。順序表的邏輯順序和存儲順序一致，鏈表的邏輯順序和存儲順序不一定一致。第三章 棧和隊列棧是限定僅

6、在表尾進(jìn)行插入和刪除操作的線性表。棧中元素除了具有線性關(guān)系外， 還具有后進(jìn)先出的特性。棧的順序存儲結(jié)構(gòu)稱為順序棧，順序棧本質(zhì)上是順序表的簡化。通常把數(shù)組中下標(biāo)為 0 的一端作為棧底，同時附設(shè)指針 top 指示棧頂元素在數(shù)組中的位置。實現(xiàn)順序棧基本操作的算法的時間復(fù)雜度均為 O(1)棧的鏈接存儲結(jié)構(gòu)稱為鏈棧，通常用單鏈表表示，并且不用附加頭結(jié)點。鏈棧的插入和刪除操作只需處理棧頂即開始結(jié)點的情況，其時間復(fù)雜度均為 O ( 1) 。隊列時只允許在一端進(jìn)行插入操作，而另一端進(jìn)行刪除操作的線性表。 隊列中的元素除了具有線性關(guān)系外，還具有先進(jìn)先出特性。順序隊列會出現(xiàn)假溢出問題，解決的辦法是用首尾相接的順序

7、存儲結(jié)構(gòu)，稱為循環(huán)隊列。在循環(huán)隊列中， 凡是涉及隊頭及隊尾指針的修改都需要將其求模。在循環(huán)隊列中， 隊空的判斷條件是： 隊頭指針 = 隊尾指針；再浪費一個存儲單元的情況下，隊滿的判定條件是（隊尾指針 +1） %數(shù)組長度=隊頭指針隊列的鏈接存儲結(jié)構(gòu)稱為鏈隊列。鏈隊列通常附設(shè)頭結(jié)點，并設(shè)置隊頭指針指向頭結(jié)點，隊尾指針指向終端結(jié)點。鏈隊列基本操作的實現(xiàn)本質(zhì)上也是單鏈表操作的簡化，插入只考慮在練隊列的尾部進(jìn)行，刪除只考慮在鏈隊列的頭部進(jìn)行，其時間復(fù)雜度均為 O（1） 。棧結(jié)構(gòu)通常采用的兩種存儲結(jié)構(gòu)是順序存儲結(jié)構(gòu)和鏈接存儲 （順序棧和鏈棧） ， 其判定棧空的條件分別是棧頂指針 top=-1 和 top=

8、null ，其判定棧滿的條件分別是棧頂指針 top 等于數(shù)組的長度和內(nèi)存無可用空間。?？勺鳛閷崿F(xiàn)遞歸函數(shù)調(diào)用的一種數(shù)據(jù)結(jié)構(gòu)。棧和隊列是兩種特殊的線性表，棧的操作特性是后進(jìn)先出，隊列的操作特性是先進(jìn)先出，棧和隊列的主要區(qū)別在于對插入和刪除操作限定的位置不同。循環(huán)隊列是為了克服假溢出。數(shù)組 Q【 n 】用來表示一個循環(huán)隊列， front 為隊頭元素的前一個位置， rear 為隊尾元素的位置，計算隊列中元素個數(shù)的計算公式為( rear-front+n) %n用循環(huán)鏈表表示的隊列中，出隊即是刪除開始結(jié)點，這只需修改相應(yīng)指針；入隊即是在終端結(jié)點的后面插入一個結(jié)點，這需要從頭指針開始查找終端結(jié)點的地址。設(shè)

9、計一個判別表達(dá)式中左右括號是否配對的算法，采用棧數(shù)據(jù)結(jié)構(gòu)最佳。在解決計算機主機與打印機之間速度不匹配問題時通 常設(shè)置一個打印緩沖區(qū)，該緩沖區(qū)應(yīng)該是一個隊列結(jié) 構(gòu)。棧和隊列的主要區(qū)別在于插入刪除運算的限定不一樣。在棧滿的情況下不能做進(jìn)棧操作， 否則將產(chǎn)生 “上溢” 。對于棧和隊列，無論它們采用順序存儲結(jié)構(gòu)還是鏈接存儲結(jié)構(gòu)，進(jìn)行插入和刪除操作的時間復(fù)雜度都是O(1)。第四章 字符串和多維數(shù)組字符串是由 0 個或多個字符組成的有限序列。 只包含空格串的稱為空格串，長度為 0 的稱為空串。字符串的比較是通過組成串的字符之間的比較來進(jìn)行的， 而字符見的大小關(guān)系是字符編碼之間的大小關(guān)系。字符串有順序存儲結(jié)

10、構(gòu)和鏈接存儲結(jié)構(gòu)， 在大多數(shù)語言中， 串的存儲和基本操作的實現(xiàn)都是采用順序存儲給定主串 S 和模式 T ， 在主串 S 中尋找模式 T 的過程稱為模式匹配。 BF 算法是一種帶回溯的匹配算法， KMP 算法是一種不帶回溯的算法數(shù)組是有類型相同的數(shù)據(jù)元素構(gòu)成的有序集合， 其特點是結(jié)構(gòu)中的元素本身可以具有某種結(jié)構(gòu)，但屬于同一數(shù)據(jù)類型。比如：一維數(shù)組可以看作一個線性表， 二維數(shù)組可以看作是線性表的線性表，以此類推，所以數(shù)組是線性表的推廣。在數(shù)組中通常只有兩種操： 存取和修改， 他們本質(zhì)上只對應(yīng)一種操作尋址由于數(shù)組一般不做插入和刪除操作， 因此， 數(shù)組通常采用順序存儲結(jié)構(gòu)。采用順序存儲結(jié)構(gòu)存儲二維數(shù)組

11、需要將二維數(shù)組映射到一維結(jié)構(gòu)，常用的映射方法有兩種：按行優(yōu)先和按列優(yōu)先。矩陣壓縮存儲的基本思想是： 為多個值相同的元素只分配一個存儲空間；對0 元素不分配存儲空間。對稱矩陣壓縮存儲的基本方法是將下三角的元素按行優(yōu)先存儲到一維數(shù)組SA 中，下三角的元素aij (i>j) 在數(shù)組 SA 中的下標(biāo) k與 i、 j 的關(guān)系是 k=i* ( i+1 ) /2+j-1.下三角矩陣的壓縮存儲方法是將下三角中的元素按行存儲非零元素表示為三元組（行號、列號、非零元素） 。將稀疏矩陣的非零元素對應(yīng)的三元組所構(gòu)成的集合， 按行優(yōu)先的順序排列成一個線性表，稱為三元組表。三元組表有兩種存儲結(jié)構(gòu)：順序存儲結(jié)構(gòu)（三元

12、組順序表）和鏈接存儲結(jié)構(gòu)（稱為十字鏈表）字符串是一種特殊的線性表， 其特殊性體現(xiàn)在數(shù)據(jù)元素的類型是一個字符。數(shù)組通常只有兩種運算： 存取和修改， 這決定了數(shù)組通常采用順序存儲結(jié)構(gòu)來實現(xiàn)存儲。設(shè)有兩個串p和q,求q在p中首次出現(xiàn)的位置的運算稱作模式匹配。將數(shù)組稱為隨機存取結(jié)構(gòu)是因為對數(shù)組任一元素的存取時間是相等的數(shù)組是一種線型結(jié)構(gòu)數(shù)組是一種定長的線型結(jié)構(gòu)數(shù)組的基本操作有存取、修改、檢索和排序等，沒有插入和刪除操作。對特殊矩陣采用壓縮存儲的目的主要是為了減少不必要的存儲 空間。使用三元組存儲稀疏矩陣的元素，有時并不能節(jié)省存儲空間。稀疏矩陣壓縮存儲后，必會失去隨機存取功能。樹是 n（ n>=0

13、 ）個結(jié)點的有限集合。任意一顆非空數(shù)滿足：1 .有且僅有一個特定的稱為根的結(jié)點；2 .當(dāng) n>1 時，除根節(jié)點之外的其余結(jié)點被分成 m （ m>0 ）個互不相交的有限集合T1,T2,Tm,其中每個集合又是一顆樹，并稱為這個根結(jié)點的字?jǐn)?shù)。樹的存儲結(jié)構(gòu)有雙親表示法、孩子表示法、孩子雙親表示法、孩子兄弟表示法。二叉樹的遍歷方式： 前序遍歷、 中序遍歷、 后序遍歷和層序遍歷、二叉樹有 5 中形態(tài)。樹是 n（ n>=0 ）結(jié)點的有限集合，在一棵非空樹中，有且僅有一個根結(jié)點，其余的借點分成 m（ m>0 ）個互不相交的集合，每個集合都是根結(jié)點的子樹。樹中某結(jié)點的個數(shù)稱為該結(jié)點的度，

14、子樹的根結(jié)點稱為該結(jié)點的孩子，該結(jié)點稱為其子樹根結(jié)點的雙親。一顆二叉樹的第i （i>=1）層最多有2人（i-1）個結(jié)點；一 棵樹有n （n>0）個結(jié)點的滿二叉樹共有（n+1） /2個 葉子結(jié)點和（ n-1） /2 個非終端結(jié)點。設(shè)二叉樹有 n 個結(jié)點，則其深度最多是n ，最少是【 log2n】 +1如果T 是由有序樹T 轉(zhuǎn)化而來的二叉樹，那么 T 中結(jié)點的前序序列就是T 中結(jié)點的前序序列， T 中結(jié)點的后序序列就是T 中結(jié)點的中序序列。在二叉樹的前序遍歷序列中，任意一個結(jié)點均處在其子女的前面。由樹轉(zhuǎn)換成二叉樹，其根結(jié)點的右子樹總是空的。對于一棵具有n 個結(jié)點的樹，其所有結(jié)點的度之和

15、為n-1.前序遍歷和中序遍歷結(jié)果相同的二叉樹是根結(jié)點無左孩子的二叉樹。第六章 圖在無向圖中，對于任意頂點 Vi 和 Vj ，若存在（ Vi ，Vj ） ， 則稱頂點 Vi 和 Vj 互為鄰接點。 在有向圖中， 對 于任意頂點 Vi 和 Vj ，若存在弧 Vi ， Vj ，則稱頂點Vj 是 Vi 的鄰接點。含有 n 個頂點的無向完全圖共有n* （n-1） /2 條邊；含有n個頂點的有向完全圖共有n* （n-1）條邊。在無向圖中，頂點 v 的度是指依附于該頂點的邊的個數(shù)；在有向圖中，頂點 v 的入度是指以該頂點為弧頭的弧的個數(shù)，頂點 v 的出度是指以該頂點為弧尾的弧的個數(shù)。在圖中，權(quán)通常是指對邊賦

16、予的有意義的數(shù)量值，邊上帶權(quán)的圖稱為網(wǎng)或網(wǎng)圖。在無向圖G=(V,E)中，頂點Vp到Vq之間的路徑是一 個頂點序列 Vp=Vi0 , Vi, Vim=Vq，其九(Vij-1 ,Vij) WE (l<=j<=m)；如果 G 是有向圖，則 <Vij-1,Vij> C E(1<=j<=m).路徑上邊的數(shù)目稱為路徑長度。第一個 頂點和最后一個頂點相同的路徑稱為回路。在無向圖中，若任意頂點 Vi和Vj (i wj )之間有路 徑，則稱該圖是連通圖，非連通圖的極大連通子圖稱為連通分量；在有向圖中，對任意頂點Vi和Vj (i wj ) ，若從頂點 Vi 到 Vj 和頂點 V

17、j 到 Vi 均有路徑，則 稱該有向圖為強連通圖，非強連通圖的極大強連通子圖稱為強連通分量。連通圖G的生成樹是包含G中全部頂點的一個極小連 通子圖。圖的生成樹可以在遍歷過程中得到。圖的遍歷通常有深度優(yōu)先遍歷和廣度優(yōu)先遍歷兩種方式。圖的深度優(yōu)先遍歷是以遞歸方式進(jìn)行的，需用棧記載遍歷路線；圖的廣度優(yōu)先遍歷是以層次方式進(jìn)行的，需用隊列保存已訪問的頂點。為了在圖的遍歷過程中區(qū)分頂點是否已被訪問，設(shè)置一個訪問標(biāo)志數(shù)組visitedn, 其初值為未被訪問標(biāo)志“ 0” ，如果某個頂點已被訪問，則將該頂點的訪問標(biāo)志置為“ 1”圖的存儲結(jié)構(gòu)有鄰接矩陣，鄰接表，十字鏈表，鄰接多重表等。圖的鄰接矩陣存儲用一個一維數(shù)組存儲圖中頂點的信息，用一個二維數(shù)組存儲圖中邊的信息(鄰接矩陣) ；圖的鄰接表存儲由邊表和頂點表組成，圖中每個頂點的所有鄰接點構(gòu)成一個邊表，所有邊表的頭指針和存儲頂點信息的一維數(shù)組構(gòu)成頂點表。最小生成樹是無向連通網(wǎng)中代價最小的生成樹。最小生成樹具有MST14質(zhì)，Prim算法和Kruskal算法是兩 個利用MST4質(zhì)構(gòu)造最小生成樹的經(jīng)典算法。Prim算法的時間復(fù)雜度為 O (nA2),適用于求稠密網(wǎng)的最小生成樹； Kruskal 算法的時間復(fù)雜度為 O(elog2e