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

　　u 散列表的查找

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

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

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

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

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

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

　　III. 平方取中法

　　IV. 折疊法

　　V. 移位法

　　常見(jiàn)的解決沖突的方法有：

　　I. 線(xiàn)性探查法

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

　　III. 拉鏈法

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

　　處理沖突的方法：

　　開(kāi)放地址法(線(xiàn)性探查法)：二次地址=(一次地址+增量序列) MOD 散列表長(zhǎng)度M

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

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

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

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

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

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

　　4. 重點(diǎn)、難點(diǎn)解析

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

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

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

　　u 對(duì)于鏈?zhǔn)酱鎯?chǔ)的線(xiàn)性表，它的插入、刪除和查找算法。

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

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

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

　　關(guān)于圖的概念和相關(guān)算法很多，這對(duì)高程軟考來(lái)說(shuō)，也是一個(gè)重點(diǎn)。

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

　　u 鄰接矩陣

　　u 鄰接表

　　u 十字鏈表

　　u 鄰接多重表

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

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

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