軟考軟件設(shè)計師專題講義九：數(shù)據(jù)結(jié)構(gòu)相關(guān)算法

　　u 散列表的查找

　　散列表又稱雜湊表，是一種非常實用的查找技術(shù)。它的原理是在結(jié)點的存儲位置和它的關(guān)鍵碼間建立一個確定的關(guān)系，從而讓查找碼直接利用這個關(guān)系確定結(jié)點的位置。其技術(shù)的關(guān)鍵在于解決兩個問題。

　　I. 找一個好的散列函數(shù)

　　II. 設(shè)計有效解決沖突的方法

　　常見的散列函數(shù)有：

　　I. 質(zhì)數(shù)除取余法

　　II. 基數(shù)轉(zhuǎn)換法

　　III. 平方取中法

　　IV. 折疊法

　　V. 移位法

　　常見的解決沖突的方法有：

　　I. 線性探查法

　　II. 雙散列函數(shù)法

　　III. 拉鏈法

　　假設(shè)HASH表的地址集為0-n-1，沖突是指由關(guān)鍵字得到的HASH地址的位置上已經(jīng)存在記錄，則處理沖突就是為該關(guān)鍵字的記錄找到另一個空的HASH地址用于存放。

　　處理沖突的方法：

　　開放地址法(線性探查法)：二次地址=(一次地址+增量序列) MOD 散列表長度M

　　再HASH法(雙散列函數(shù)法)：使用不同的散列函數(shù)計算，互相作為補償;

　　二次地址=RH(key) R和H都是散列函數(shù)

　　拉鏈法(鏈地址法)：設(shè)立一個指針數(shù)組，初始狀態(tài)是空指針，HASH地址為i的記錄都插入到指針數(shù)組中第i項所指向的鏈表中，保持關(guān)鍵字有序。

　　建立一個公共的溢出區(qū)：將所有沖突的關(guān)鍵字和記錄都添入到溢出區(qū)。

　　HASH查找分析： HASH的查找長度與查找表的長度無關(guān)，只與裝添因子有關(guān)

　　裝添因子=表中添入的記錄數(shù)/HASH的長度

　　4. 重點、難點解析

　　數(shù)據(jù)結(jié)構(gòu)的相關(guān)知識點在軟考中是經(jīng)常出現(xiàn)的，無論是上午的客觀題，還是下午的程序填空，都會涉及，而且考試的題型除了一般的概念和常識以外，還涉及各種算法，出題十分靈活。因此對這部分的復(fù)習(xí)一定要非常重視。這里我們總結(jié)了數(shù)據(jù)結(jié)構(gòu)部分的一些比較重要的要點。

　　n 鏈?zhǔn)酱鎯�結(jié)構(gòu)

　　不管是線性表、棧，還是隊列，都會使用鏈?zhǔn)酱鎯�結(jié)構(gòu)。對于鏈?zhǔn)酱鎯�結(jié)構(gòu)的操作與順序存儲結(jié)構(gòu)不一樣，因此我們需要熟悉它們的相關(guān)算法。如：

　　u 對于鏈?zhǔn)酱鎯Φ木�性表，它的插入、刪除和查找算法。

　　u 對于鏈接存儲棧，它的進(jìn)棧、出棧算法

　　u 對于鏈接存儲隊列，它的進(jìn)隊、出隊算法

　　另外，對于棧和隊列的一些實際應(yīng)用的算法也需要關(guān)心，特別在下午的程序填空的考試中，經(jīng)常會碰到類似的算法。

　　關(guān)于圖的概念和相關(guān)算法很多，這對高程軟考來說，也是一個重點。

　　除了我們前面羅列的一些關(guān)于的圖的基本概念以外，首先我們必須對圖的幾種存儲結(jié)構(gòu)要十分的清楚，因為這實際上是研究圖的相關(guān)問題和算法的基礎(chǔ)。包括：

　　u 鄰接矩陣

　　u 鄰接表

　　u 十字鏈表

　　u 鄰接多重表

　　對于圖的兩種遍歷算法(深度優(yōu)先和廣度優(yōu)先)實際可以參考樹的有關(guān)遍歷算法，這樣理解起來相對簡單。

　　而對于圖的有關(guān)算法，如求最小代價生成樹、求最短路徑、拓?fù)渑判蚝颓箨P(guān)鍵路徑等，這是數(shù)據(jù)結(jié)構(gòu)中的難點。不過一般來說，軟考中很難直接考到。因此，大家在復(fù)習(xí)的時候主要抓住涉及算法的相關(guān)概念、算法的基本原理以及算法的復(fù)雜度這幾個方面。當(dāng)然，有時間最好參看一下相關(guān)資料，對它的具體實現(xiàn)仔細(xì)看看，這對理解其算法的核心思想當(dāng)然會事半功倍。

　　　　　　　計算機軟考軟件設(shè)計師練習(xí)試題及答案解析匯總