《《大數(shù)據(jù)結(jié)構(gòu)》基本概念》由會(huì)員分享，可在線閱讀，更多相關(guān)《《大數(shù)據(jù)結(jié)構(gòu)》基本概念（30頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、基本概念 ? 數(shù)據(jù) 數(shù)據(jù)是信息的載體，在計(jì)算機(jī)科學(xué)中是指所有能 輸入到計(jì)算機(jī)中并能被計(jì)算機(jī)程序識(shí)別和 處理的符號(hào) 集合。 ? 數(shù)據(jù)元素 數(shù)據(jù)元素也稱為結(jié)點(diǎn)，是表示數(shù)據(jù)的基本單位，在計(jì)算機(jī)程序中通常作為一個(gè)整體進(jìn)行考慮和處理。 ? 數(shù)據(jù)項(xiàng) 數(shù)據(jù)項(xiàng)是構(gòu)成數(shù)據(jù)元素的不可分割的最小單位。 ? 數(shù)據(jù)對(duì)象 數(shù)據(jù)對(duì)象是具有相同性質(zhì)的數(shù)據(jù)元素的集合，是數(shù)據(jù)的子集。 注意：在不產(chǎn)生混淆的情況下，將數(shù)據(jù)對(duì)象簡(jiǎn)稱為數(shù)據(jù)。 ? 數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一定關(guān)系的數(shù)據(jù)元素的集合，即數(shù)據(jù)結(jié)構(gòu)是一個(gè)二元組 DataStructure = (D, R)，其中D是數(shù)據(jù)元素的集合，R是D上關(guān)系

2、的集合。按照視點(diǎn)的不同，數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)和存 儲(chǔ)結(jié)構(gòu)。 ? 數(shù)據(jù)的邏輯結(jié)構(gòu) 數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)元素之間邏輯關(guān)系的整體。根據(jù)數(shù)據(jù)元素之間邏輯關(guān)系的不同，數(shù)據(jù)結(jié)構(gòu)分 為四類： ⑴ 集合：數(shù)據(jù)元素之間就是“屬于同一個(gè)集合”，除此之外，沒(méi)有任何關(guān)系； ⑵ 線性結(jié)構(gòu)：數(shù)據(jù)元素之間存在著一對(duì)一的線性關(guān)系； ⑶ 樹(shù)結(jié)構(gòu)：數(shù)據(jù)元素之間存在著一對(duì)多的層次關(guān)系； ⑷ 圖結(jié)構(gòu)：數(shù)據(jù)元素之間存在著多對(duì)多的任意關(guān)系。 注意：數(shù)據(jù)結(jié)構(gòu)分為兩類：線性結(jié)構(gòu)和非線性結(jié)構(gòu)。 ? 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)又稱為物理結(jié)構(gòu)，是數(shù)據(jù)及其邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示。通常有兩種存儲(chǔ)結(jié)構(gòu)：順 序存儲(chǔ)結(jié)構(gòu)和鏈接存

3、儲(chǔ)結(jié)構(gòu)。 順序存儲(chǔ)結(jié)構(gòu)的基本思想是：用一組 連續(xù)的存儲(chǔ)單元 依次存儲(chǔ)數(shù)據(jù)元素，數(shù)據(jù)元素之間的邏輯關(guān)系是 由元素的存儲(chǔ)位置來(lái)表示的。 鏈接存儲(chǔ)結(jié)構(gòu)的基本思想是：用一組 任意的存儲(chǔ)單元存儲(chǔ)數(shù)據(jù)元素，數(shù)據(jù)元素之間的邏輯關(guān)系是用指 針來(lái)表示的。 注意：存儲(chǔ)結(jié)構(gòu)除了存儲(chǔ)數(shù)據(jù)元素之外，必須存儲(chǔ)數(shù)據(jù)元素之間的邏輯關(guān)系。 ? 抽象數(shù)據(jù)類型 抽象數(shù)據(jù)類型是一個(gè)數(shù)據(jù)結(jié)構(gòu)以及定義在該結(jié)構(gòu)上的一組操作的總稱。抽象數(shù)據(jù)類型提供了使用和實(shí) 現(xiàn)兩個(gè)不同的視圖，實(shí)現(xiàn)了封裝和信息隱藏。 ? 算法的定義 通俗地講，算法是解決問(wèn)題的方法，嚴(yán)格地說(shuō)，算法是對(duì)特定問(wèn)題求解步驟的一種描述，是指令的有 限序列。 ?

4、 算法的特性 ⑴ 輸入：一個(gè)算法有零個(gè)或多個(gè)輸入（即算法可以沒(méi)有輸入），這些輸入通常取自于某個(gè)特定的對(duì)象 集合。 ⑵輸出：一個(gè)算法有一個(gè)或多個(gè)輸出（即算法必須要有輸出），通常輸出與輸入之間有著某種特定的 關(guān)系。 ⑶有窮性：一個(gè)算法必須總是（對(duì)任何合法的輸入）在執(zhí)行有窮步之后結(jié)束，且每一步都在有窮時(shí)間 內(nèi)完成。 ⑷ 確定性：算法中的每一條指令必須有確切的含義，不存在二義性。并且，在任何條件下，對(duì)于相同 的輸入只能得到相同的輸出。 ⑸ 可行性：算法描述的操作可以通過(guò)已經(jīng)實(shí)現(xiàn)的基本操作執(zhí)行有限次來(lái)實(shí)現(xiàn)。 ? 線性表的定義 線性表簡(jiǎn)稱表，是零個(gè)或多個(gè)具有相同類型的數(shù)據(jù)元素的有限序列。數(shù)據(jù)

5、元素的個(gè)數(shù)稱為線性表的 長(zhǎng) 度，長(zhǎng)度等于零時(shí)稱為空表。 ? 線性表的邏輯關(guān)系 在一個(gè)非空表L= (ai, a2, , an)中，任意一對(duì)相鄰的數(shù)據(jù)元素 a-i和ai之間(1 < i

6、lemType 表示不確定的數(shù)據(jù)類型 int len gth; 〃len gth 表示線性表的長(zhǎng)度 } SeqList; ? 順序表是隨機(jī)存取結(jié)構(gòu) 設(shè)順序表的每個(gè)元素占用 c個(gè)存儲(chǔ)單元，則第i個(gè)元素的存儲(chǔ)地址為： LOC(ai)= LOC(ai) + (i— 1) xc ? 順序表的優(yōu)缺點(diǎn) 順序表利用了數(shù)組元素在物理位置上的鄰接關(guān)系來(lái)表示線性表中數(shù)據(jù)元素之間的邏輯關(guān)系，這使得順 序表具有下列優(yōu)點(diǎn)： ⑴無(wú)需為表示表中元素之間的邏輯關(guān)系而增加額外的存儲(chǔ)空間； ⑵ 可以快速地存取表中任一位置的元素（即隨機(jī)存?。?。 同時(shí)，順序表也具有下列缺點(diǎn)： ⑴ 插入和刪除操作需移動(dòng)大量元素。

7、在順序表上做插入和刪除操作，等概率情況下，平均要移動(dòng)表中 一半的元素。 ⑵ 表的容量難以確定。由于數(shù)組的長(zhǎng)度必須事先確定，因此，當(dāng)線性表的長(zhǎng)度變化較大時(shí)，難以確定 合適的存儲(chǔ)規(guī)模。 ⑶ 造成存儲(chǔ)空間的“碎片”。數(shù)組要求占用連續(xù)的存儲(chǔ)空間，即使存儲(chǔ)單元數(shù)超過(guò)所需的數(shù)目，如果 不連續(xù)也不能使用，造成存儲(chǔ)空間的“碎片”現(xiàn)象。 ? 單鏈表的存儲(chǔ)結(jié)構(gòu)定義 單鏈表的存儲(chǔ)結(jié)構(gòu)定義如下： Struct Node { ElemType data; // ElemType 表示不確定的數(shù)據(jù)類型 struct Node *n ext; } *first; //first 為單鏈表的頭指針 ? 雙鏈

8、表的存儲(chǔ)結(jié)構(gòu)定義 雙鏈表存儲(chǔ)結(jié)構(gòu)定義如下： struct DulNode { ElemType data; // ElemType 表示不確定的數(shù)據(jù)類型 struct DulNode *prior, * next; // prior 為前驅(qū)指針域， next 為后繼指針域 } *first; //first表示雙鏈表的頭指針 ? 棧的定義 棧是限定僅在表尾進(jìn)行插入和刪除操作的線性表。允許插入和刪除的一端稱為棧頂，另一端稱為棧底， 不含任何數(shù)據(jù)元素的棧稱為空棧。 ? 棧的操作特性 棧的操作具有后進(jìn)先出的特性。 ? 隊(duì)列的定義 隊(duì)列是只允許在一端進(jìn)行插入操作，而另一端進(jìn)行刪

9、除操作的線性表。允許插入的一端稱為隊(duì)尾，允 許刪除的一端稱為隊(duì)頭。 ? 隊(duì)列的操作特性 隊(duì)列的操作具有 先進(jìn)先出的特性。 ? 循環(huán)隊(duì)列中解決隊(duì)空隊(duì)滿的判斷條件 方法一：附設(shè)一個(gè)存儲(chǔ)隊(duì)列中元素個(gè)數(shù)的變量 num，當(dāng)num=0時(shí)隊(duì)空，當(dāng)num=QueueSize 時(shí)為隊(duì) 滿； 方法二：修改隊(duì)滿條件，浪費(fèi)一個(gè)元素空間，隊(duì)滿時(shí)數(shù)組中只有一個(gè)空閑單元；即隊(duì)空的條件是 front =rear，隊(duì)滿的條件 是(rear+1) % QueueSize=front ，隊(duì)列長(zhǎng)度為 (rear-front+QueueSize) % QueueSize。 方法三：設(shè)置標(biāo)志 flag，當(dāng)front=r

10、ear 且flag=0 時(shí)為隊(duì)空，當(dāng)front=rear 且flag=1 時(shí)為隊(duì)滿。 ? 串的定義 串是零個(gè)或多個(gè)字符組成的有限序列。 ? 空格串和空串的定義 只包含空格的串稱為 空格串。串中所包含的字符個(gè)數(shù)稱為串的長(zhǎng)度，長(zhǎng)度為 0的串稱空串，記作” ”。 ? 串的比較 串的比較是通過(guò)組成串的字符之間的比較來(lái)進(jìn)行的。 給定兩個(gè)串： X=" X1X2???Xn" Y=" y1y2???ym" 則當(dāng) n=m 且 X1 = y1，…，Xn=ym時(shí)，稱 X=Y； 當(dāng)下列條件之一成立時(shí)，稱 Xv Y： ⑴ n v m，且 Xi=yi (i=1 , 2，…，n)； ⑵ 存在某個(gè) k

11、

12、 ⑵ 修改：給定一組下標(biāo)，存儲(chǔ)或修改相應(yīng)的數(shù)組元素。 ? 二維數(shù)組的尋址 按行優(yōu)先，設(shè)二維數(shù)組的行下標(biāo)與列下標(biāo)的范圍分別為］ 11, hl］與［12, h2］,則任一元素 a的存儲(chǔ) 地址可由下式確定： LOC( aij) = LOC( aii 12) + ((i — 11) x(h2 — I2 + 1) + (j — I2)) xc 特殊矩陣的定義 特殊矩陣是指矩陣中有很多值相同的元素并且它們的分布有一定的規(guī)律。 矩陣壓縮存儲(chǔ)的基本思想 壓縮存儲(chǔ)的基本思想是：⑴ 為多個(gè)值相同的元素只分配一個(gè)存儲(chǔ)空間；⑵ 對(duì)零元素不分配存儲(chǔ)空間。 ? 對(duì)稱矩陣的壓縮存儲(chǔ)中： 下三角兀素ai

13、j (i>j)在一個(gè)數(shù)組 SA中的下標(biāo)為：k = ix(i-1)/2 + j-1。上三 角中的元素aij (ivj),則訪問(wèn)和它對(duì)應(yīng)的下三角中的元素 aji即可，即：k = jx(j-1)/2 + i-1。 精彩文檔 三角矩陣的壓縮存儲(chǔ)中： 下三角矩陣中任一兀素 aij在一個(gè)數(shù)組SA中的下標(biāo)k與i、j的對(duì)應(yīng)關(guān)系為: r i x (i-1)/2 + j-1 當(dāng) i > j "[nx (n + 1)/2 當(dāng) i

14、 ? 三元組的定義 struct eleme nt { int row, col; ElemType item }; ? 廣義表的定義 廣義表是n (n》0)個(gè)數(shù)據(jù)元素的有限序列。 ? 表頭 當(dāng)廣義表LS非空時(shí)，稱第一個(gè)元素為 LS的表頭； ? 表尾 稱廣義表LS中除去表頭后其余元素組成的廣義表為 LS的。 ? 長(zhǎng)度 廣義表LS中的直接元素的個(gè)數(shù)稱為 LS的長(zhǎng)度； ? 深度 廣義表LS中括號(hào)的最大嵌套層數(shù)稱為 LS的深度。 樹(shù)的定義 樹(shù)是n (n》0)個(gè)結(jié)點(diǎn)的有限集合。當(dāng) n = 0時(shí)，稱為空樹(shù)；任意一棵非空樹(shù)滿足以下條件： ⑴ 有且僅有一個(gè)特定的稱為 根的結(jié)

15、點(diǎn)； ⑵ 當(dāng)n> 1時(shí)，除根結(jié)點(diǎn)之外的其余結(jié)點(diǎn)被分成 m (m>0 )個(gè)互不相交的有限集合Ti, T2,…，Tm, 其中每個(gè)集合又是一棵樹(shù)，并稱為這個(gè)根結(jié)點(diǎn)的子樹(shù)。 ? 結(jié)點(diǎn)的度、樹(shù)的度 某結(jié)點(diǎn)所擁有的子樹(shù)的個(gè)數(shù)稱為該結(jié)點(diǎn)的度；樹(shù)中各結(jié)點(diǎn)度的最大值稱為該樹(shù)的度。 ? 葉子結(jié)點(diǎn)、分支結(jié)點(diǎn) 度為0的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)，也稱為終端結(jié)點(diǎn)；度不為 0的結(jié)點(diǎn)稱為分支結(jié)點(diǎn)，也稱為非終端結(jié)點(diǎn)。 ? 孩子結(jié)點(diǎn)、雙親結(jié)點(diǎn)、兄弟結(jié)點(diǎn) 某結(jié)點(diǎn)的子樹(shù)的根結(jié)點(diǎn)稱為該結(jié)點(diǎn)的孩子結(jié)點(diǎn)；反之，該結(jié)點(diǎn)稱為其孩子結(jié)點(diǎn)的雙親 ? 路徑、路徑長(zhǎng)度 如果樹(shù)的結(jié)點(diǎn)序列 ni, n2,…,nk滿足如下關(guān)系：結(jié)點(diǎn)m是結(jié)點(diǎn)m+

16、i的雙親(1 wiv k)，則把ni, n2,… nk稱為一條由ni至nk的路徑；路徑上經(jīng)過(guò)的邊的個(gè)數(shù)稱為路徑長(zhǎng)度。 ? 祖先、子孫 如果從結(jié)點(diǎn)x到結(jié)點(diǎn)y有一條路徑，那么 x就稱為y的祖先，而y稱為x的子孫。 注意：某結(jié)點(diǎn)子樹(shù)中的任一結(jié)點(diǎn)都是該結(jié)點(diǎn)的子孫。 ? 結(jié)點(diǎn)的層數(shù)、樹(shù)的深度(高度) 規(guī)定根結(jié)點(diǎn)的層數(shù)為i，對(duì)其余任何結(jié)點(diǎn)，若某結(jié)點(diǎn)在第 k層，則其孩子結(jié)點(diǎn)在第 k+i層；樹(shù)中所有 結(jié)點(diǎn)的最大層數(shù)稱為樹(shù)的深度，也稱為樹(shù)的高度。 ? 二叉樹(shù)的定義 二叉樹(shù)是n (n >0)個(gè)結(jié)點(diǎn)的有限集合，該集合或者為空集(稱為空二叉樹(shù))，或者由一個(gè)根結(jié)點(diǎn)和兩 棵互不相交的、分別稱為根結(jié)點(diǎn)的

17、左子樹(shù)和右子樹(shù)的二叉樹(shù)組成。 2的結(jié)點(diǎn)；(2)子樹(shù)的次 ? 二叉樹(shù)的特點(diǎn) 二叉樹(shù)的特點(diǎn)是：⑴ 每個(gè)結(jié)點(diǎn)最多有兩棵子樹(shù)，所以二叉樹(shù)中不存在度大于 序不能任意顛倒，某結(jié)點(diǎn)即使只有一棵子樹(shù)也要區(qū)分是左子樹(shù)還是右子樹(shù)。 注意：二叉樹(shù)和樹(shù)是兩種樹(shù)結(jié)構(gòu)。 二叉樹(shù)的基本形態(tài) 二叉樹(shù)具有五種基本形態(tài)：⑴ 空二叉樹(shù)；⑵ 只有一個(gè)根結(jié)點(diǎn)；⑶ 根結(jié)點(diǎn)只有左子樹(shù)；⑷ 根結(jié)點(diǎn)只 有右子樹(shù)；⑸ 根結(jié)點(diǎn)既有左子樹(shù)又有右子樹(shù)。 斜樹(shù) 所有結(jié)點(diǎn)都只有左子樹(shù)的二叉樹(shù)稱為左斜樹(shù)；所有結(jié)點(diǎn)都只有右子樹(shù)的二叉樹(shù)稱為右斜樹(shù)；左斜樹(shù)和 右斜樹(shù)統(tǒng)稱為斜樹(shù)。 斜樹(shù)的特點(diǎn)：①每一層只有一個(gè)結(jié)點(diǎn)，即只有度為 1和度為0的結(jié)點(diǎn)

18、并且只有一個(gè)葉子結(jié)點(diǎn)；② 斜樹(shù) 的結(jié)點(diǎn)個(gè)數(shù)與其深度相同。 滿二叉樹(shù) 在一棵二叉樹(shù)中，如果所有分支結(jié)點(diǎn)都存在左子樹(shù)和右子樹(shù)，并且所有葉子都在同一層上，這樣的二 叉樹(shù)稱為滿二叉樹(shù)。 滿二叉樹(shù)的特點(diǎn)：① 葉子結(jié)點(diǎn)都在最下一層；② 只有度為0和度為2的結(jié)點(diǎn)。 完全二叉樹(shù) 對(duì)一棵具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)按層序編號(hào)，如果編號(hào)為 i (1 wi

19、左孩子。 二叉樹(shù)的基本性質(zhì) 性質(zhì)1 二叉樹(shù)的第i層上最多有2卜1個(gè)結(jié)點(diǎn)（i >1 ）。 性質(zhì)2 在一棵深度為k的二叉樹(shù)中，最多有 2k-1個(gè)結(jié)點(diǎn)，最少有k個(gè)結(jié)點(diǎn)。 性質(zhì)3 在一棵二叉樹(shù)中，如果葉子結(jié)點(diǎn)的個(gè)數(shù)為 no，度為2的結(jié)點(diǎn)個(gè)數(shù)為n2，則 no= n2+ 1。 性質(zhì)4 具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為 log2 n 1。 性質(zhì)5 對(duì)一棵具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)中的結(jié)點(diǎn)從 1開(kāi)始按層序編號(hào)，則對(duì)于任意的編號(hào)為 i （1 wiwn）的結(jié)點(diǎn)（簡(jiǎn)稱為結(jié)點(diǎn)i）,有： ⑴如果i> 1，則結(jié)點(diǎn)i的雙親的編號(hào)為i/2 ；否則結(jié)點(diǎn)i是根結(jié)點(diǎn)，無(wú)雙親； ⑵ 如果2iwn,則結(jié)點(diǎn)i的左孩子的

20、編號(hào)為 2i；否則結(jié)點(diǎn)i無(wú)左孩子； ⑶ 如果2i + 1 wn，則結(jié)點(diǎn)i的右孩子的編號(hào)為2i+ 1 ；否則結(jié)點(diǎn)i無(wú)右孩子。 ? 二叉樹(shù)的存儲(chǔ) 包括：二叉樹(shù)的順序存儲(chǔ)和二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)。 二叉鏈表的存儲(chǔ)結(jié)構(gòu)定義如下： struct BiNode { ElemType data; BiNode *lchild, *rchild; } *root; //root 表示二叉鏈表的頭指針 struct TriNode { ElemType data; TriNode *lchild, *rchild, *pare nt; // pare nt 指向該結(jié)點(diǎn)的雙親 } *root

21、; //三叉鏈表的頭指針 遍歷的含義 所謂遍歷就是無(wú)重復(fù)無(wú)遺漏地訪問(wèn)。二叉樹(shù)的遍歷是指從根結(jié)點(diǎn)出發(fā)，按照某種次序訪問(wèn)二叉樹(shù)中的 所有結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)被訪問(wèn)一次且僅被訪問(wèn)一次。 ? 二叉樹(shù)的遍歷次序定義 前序遍歷（或稱前根遍歷、先序遍歷） 若二叉樹(shù)為空，則空操作返回；否則 ⑴訪問(wèn)根結(jié)點(diǎn)； ⑵ 前序遍歷根結(jié)點(diǎn)的左子樹(shù)； ⑶前序遍歷根結(jié)點(diǎn)的右子樹(shù)。 中序遍歷（或稱中根遍歷） 若二叉樹(shù)為空，則空操作返回；否則 ⑴中序遍歷根結(jié)點(diǎn)的左子樹(shù)； ⑵訪問(wèn)根結(jié)點(diǎn)； ⑶中序遍歷根結(jié)點(diǎn)的右子樹(shù)。 后序遍歷（或稱后根遍歷） 若二叉樹(shù)為空，則空操作返回；否則 ⑴ 后序遍歷根結(jié)點(diǎn)的左子樹(shù)；

22、 ⑵ 后序遍歷根結(jié)點(diǎn)的右子樹(shù)； ⑶訪問(wèn)根結(jié)點(diǎn)。 層序遍歷 二叉樹(shù)的層序遍歷是從二叉樹(shù)的第一層（根結(jié)點(diǎn)）開(kāi)始，從上至下逐層遍歷，在同一層中，則按從左 到右的順序?qū)Y(jié)點(diǎn)逐個(gè)訪問(wèn)。 線索二叉樹(shù)的定義 在一個(gè)具有n個(gè)結(jié)點(diǎn)的二叉鏈表中， 利用n+1個(gè)空指針域存放指向該結(jié)點(diǎn)在某種遍歷序列中的前驅(qū)和 后繼結(jié)點(diǎn)的指針，這些指向前驅(qū)和后繼結(jié)點(diǎn)的指針?lè)Q為 線索，加上線索的二叉樹(shù)稱為 線索二叉樹(shù)，相應(yīng)地, 加上線索的二叉鏈表稱為線索鏈表。 ? 線索二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)定義 線索鏈表中的結(jié)點(diǎn)定義如下： enum flag {Child, Thread}; // 枚舉類型，枚舉常量 Child=0

23、，Thread=1 struct ThrNode { ElemType data; // ElemType 表示不確定的數(shù)據(jù)類型 ThrNode *lchild, *rchild; flag ltag, rtag; }*root; //root 表示線索鏈表的頭指針 ? 樹(shù)的存儲(chǔ)結(jié)構(gòu) 包括：雙親表示法、孩子表示法、孩子兄弟表示法。 雙親表示法的存儲(chǔ)結(jié)構(gòu)定義如下: //樹(shù)中最大結(jié)點(diǎn)個(gè)數(shù) //數(shù)組元素的類型 //樹(shù)中結(jié)點(diǎn)的數(shù)據(jù)信息， //該結(jié)點(diǎn)的雙親在數(shù)組中的下標(biāo) #defi ne MaxSize 100; struct PNode { ElemType data;

24、 int pare nt; }; PNode Tree[MaxSize]; 孩子表示法的存儲(chǔ)結(jié)構(gòu)定義如下: struct CTNode // 孩子結(jié)點(diǎn) { int child; CTNode *n ext; }; struct CBNode // 表頭結(jié)點(diǎn) { ElemType data; CTNode *firstchild; //指向孩子鏈表的頭指針 }; 孩子兄弟表示法又稱為二叉鏈表表示法，存儲(chǔ)結(jié)構(gòu)定義如下: struct TNode ElemType data; TNode *firstchild; TNode *rightsib; }； //

25、ElemType 表示不確定的數(shù)據(jù)類型 //firstchild 指向該結(jié)點(diǎn)的第一個(gè)孩子 //rightsib 指向該結(jié)點(diǎn)的右兄弟 樹(shù)轉(zhuǎn)換為二叉樹(shù) 樹(shù)轉(zhuǎn)換為二叉樹(shù)的方法是: ⑴加線——樹(shù)中所有相鄰兄弟結(jié)點(diǎn)之間加一條連線； ⑵ 去線——對(duì)樹(shù)中的每個(gè)結(jié)點(diǎn)，只保留它與第一個(gè)孩子結(jié)點(diǎn)之間的連線， 刪去它與其它孩子結(jié)點(diǎn)之間 的連線； ⑶層次調(diào)整一一以根結(jié)點(diǎn)為軸心，將樹(shù)順時(shí)針轉(zhuǎn)動(dòng)一定的角度，使之層次分明。 森林轉(zhuǎn)換為二叉樹(shù) 森林轉(zhuǎn)換為二叉樹(shù)的方法如下： ⑴ 將森林中的每棵樹(shù)轉(zhuǎn)換成二叉樹(shù)； ⑵ 從第二棵二叉樹(shù)開(kāi)始，依次把后一棵二叉樹(shù)的根結(jié)點(diǎn)作為前一棵二叉樹(shù)根結(jié)點(diǎn)的右孩子，當(dāng)所有二 叉樹(shù)連

26、起來(lái)后，所得到的二叉樹(shù)就是由森林轉(zhuǎn)換的二叉樹(shù)。 ? 二叉樹(shù)轉(zhuǎn)換為樹(shù)或森林 樹(shù)和森林轉(zhuǎn)換為二叉樹(shù)的過(guò)程是可逆的，將一棵二叉樹(shù)還原為樹(shù)或森林的方法如下： ⑴加線一一若某結(jié)點(diǎn) x是其雙親y的左孩子，則把結(jié)點(diǎn) x的右孩子、右孩子的右孩子、……，都與結(jié) 點(diǎn)y用線連起來(lái)； ⑵去線一一刪去原二叉樹(shù)中所有的雙親結(jié)點(diǎn)與右孩子結(jié)點(diǎn)的連線； ⑶ 層次調(diào)整一一整理由⑴、⑵兩步所得到的樹(shù)或森林，使之層次分明。 樹(shù)的遍歷序列與二叉樹(shù)的遍歷序列之間的對(duì)應(yīng)關(guān)系 根據(jù)樹(shù)與二叉樹(shù)的轉(zhuǎn)換關(guān)系以及樹(shù)和二叉樹(shù)遍歷的操作定義可知，樹(shù)的遍歷序列與由樹(shù)轉(zhuǎn)化成的二叉 樹(shù)的遍歷序列之間具有如下對(duì)應(yīng)關(guān)系：樹(shù)的前序遍歷序列等于二叉樹(shù)的

27、前序遍歷序列，樹(shù)的后序遍歷序列 等于二叉樹(shù)的中序遍歷序列。 ? 哈夫曼樹(shù)中葉子結(jié)點(diǎn)的權(quán)值 葉子結(jié)點(diǎn)的權(quán)值是指對(duì)葉子結(jié)點(diǎn)賦予的一個(gè)有意義的數(shù)值量。 ? 二叉樹(shù)的帶權(quán)路徑長(zhǎng)度 設(shè)二叉樹(shù)具有 n個(gè)帶權(quán)值的葉子結(jié)點(diǎn)，從根結(jié)點(diǎn)到各個(gè)葉子結(jié)點(diǎn)的路徑長(zhǎng)度與相應(yīng)葉子結(jié)點(diǎn)權(quán)值的乘 積之和稱做二叉樹(shù)的帶權(quán)路徑長(zhǎng)度，記為： n WPL= wGk k 1 其中，wk為第k個(gè)葉子結(jié)點(diǎn)的權(quán)值；lk為從根結(jié)點(diǎn)到第k個(gè)葉子結(jié)點(diǎn)的路徑長(zhǎng)度。 ? 哈夫曼樹(shù)定義 給定一組具有確定權(quán)值的葉子結(jié)點(diǎn)，可以構(gòu)造出不同的二叉樹(shù)，將其中帶權(quán)路徑長(zhǎng)度最小的二叉樹(shù)稱 為哈夫曼樹(shù)，也稱為最優(yōu)二叉樹(shù)。 ? 哈夫曼算法的基本思想

28、 哈夫曼算法的基本思想是： ⑴初始化：由給定的n個(gè)權(quán)值{wi, W2,…，Wn}構(gòu)造n棵只有一個(gè)根結(jié)點(diǎn)的二叉樹(shù)，從而得到一個(gè)二 叉樹(shù)集合F= {Ti, T2，…,Tn}; ⑵ 選取與合并：在F中選取根結(jié)點(diǎn)的權(quán)值最小的兩棵二叉樹(shù)分別作為左、 右子樹(shù)構(gòu)造一棵新的二叉樹(shù), 這棵新二叉樹(shù)的根結(jié)點(diǎn)的權(quán)值為其左、右子樹(shù)根結(jié)點(diǎn)的權(quán)值之和； ⑶ 刪除與加入：在 F中刪除作為左、右子樹(shù)的兩棵二叉樹(shù)，并將新建立的二叉樹(shù)加入到 F中； ⑷重復(fù)⑵、⑶兩步，當(dāng)集合 F中只剩下一棵二叉樹(shù)時(shí)，這棵二叉樹(shù)便是哈夫曼樹(shù)。 ? 圖的定義 圖是由頂點(diǎn)的有窮非空集合和頂點(diǎn)之間邊的集合組成，通常表示為： G=(V,巳

29、 其中，G表示一個(gè)圖，V是圖G中頂點(diǎn)的集合，E是圖G中頂點(diǎn)之間邊的集合。 ? 無(wú)向圖與有向圖 若頂點(diǎn)Vi和Vj之間的邊沒(méi)有方向，則稱這條邊為無(wú)向邊，用無(wú)序偶對(duì) （Vi, Vj）來(lái)表示；若從頂點(diǎn) Vi到Vj 的邊有方向，則稱這條邊為有向邊（也稱為弧），用有序偶對(duì) ＜Vi, Vj＞來(lái)表示，Vi稱為弧尾，Vj稱為弧頭。 如果圖的任意兩個(gè)頂點(diǎn)之間的邊都是無(wú)向邊，則稱該圖為 無(wú)向圖，否則稱該圖為 有向圖。 ? 簡(jiǎn)單圖 若不存在頂點(diǎn)到其自身的邊，且同一條邊不重復(fù)出現(xiàn)，則稱這樣的圖為簡(jiǎn)單圖。 ? 鄰接、依附 在無(wú)向圖中，對(duì)于任意兩個(gè)頂點(diǎn) Vi和Vj，若存在邊（Vi，Vj），則稱頂點(diǎn)Vi和Vj

30、互為鄰接點(diǎn)，同時(shí)稱邊（Vi， Vj）依附于頂點(diǎn)Vi和Vj。 在有向圖中，對(duì)于任意兩個(gè)頂點(diǎn) Vi和Vj，若存在弧＜Vi，Vj＞，則稱頂點(diǎn)Vj是Vi的鄰接點(diǎn)，同時(shí)稱弧＜Vi， Vj＞依附于頂點(diǎn)Vi和Vj。 ? 無(wú)向完全圖、有向完全圖 在無(wú)向圖中，如果任意兩個(gè)頂點(diǎn)之間都存在邊，則稱該圖為無(wú)向完全圖。含有 n個(gè)頂點(diǎn)的無(wú)向完全圖 有 n X（n-1）/2 條邊。 在有向圖中，如果任意兩頂點(diǎn)之間都存在方向互為相反的兩條弧，則稱該圖為有向完全圖。含有 n個(gè) 頂點(diǎn)的有向完全圖有 n x（n-1）條邊。 ? 稠密圖、稀疏圖 稱邊數(shù)很少的圖為稀疏圖，反之，稱為稠密圖。 ? 頂點(diǎn)的度、入度、出

31、度 在無(wú)向圖中，頂點(diǎn) V的度是指依附于該頂點(diǎn)的邊的個(gè)數(shù)，記為 TD（v）。在具有n個(gè)頂點(diǎn)e條邊的無(wú)向 圖中，有下式成立： TD (Vi) 2e i 1 在有向圖中，頂點(diǎn) v的入度是指以該頂點(diǎn)為弧頭的弧的個(gè)數(shù)，記為 ID(v)；頂點(diǎn)v的出度是指以該頂點(diǎn) n 為弧尾的弧的個(gè)數(shù)，記為 OD(v)。在具有n個(gè)頂點(diǎn)e條邊的有向圖中，有下式成立: n n ID (vj OD(vJ e i 1 i 1 ? 連通圖、連通分量 在無(wú)向圖中，若任意頂點(diǎn) Vi和vj(i^j)之間有路徑，則稱該圖是連通圖。非連通圖的極大連通子圖稱為 連通分量。 強(qiáng)連通圖、強(qiáng)連通分量 在有向圖

32、中，對(duì)任意頂點(diǎn) Vi和Vj(izj)，若從頂點(diǎn)Vi到Vj和從頂點(diǎn)Vj到Vi均有路徑，則稱該有向圖是強(qiáng) 連通圖。非強(qiáng)連通圖的極大強(qiáng)連通子圖稱為強(qiáng)連通分量。 鄰接矩陣的存儲(chǔ)結(jié)構(gòu)定義 假設(shè)圖G = (V, E)有n個(gè)頂點(diǎn)，則鄰接矩陣是一個(gè) n xn的方陣，定義為: 1 若(Vi, Vj) € E 或€ E 啊山「0否則 鄰接矩陣的存儲(chǔ)結(jié)構(gòu)定義如下： #defi ne MaxSize 10 typedef struct { ElemType vertex[MaxSize]; int arc[MaxSize][MaxSize]; int vertexNum, arcN

33、um; } MGraph; 鄰接表的存儲(chǔ)結(jié)構(gòu)定義 //存放圖中頂點(diǎn)的信息，ElemType表示不確定的數(shù)據(jù)類型 //存放圖中邊的信息 //圖的頂點(diǎn)數(shù)和邊數(shù) 鄰接表是一種順序存儲(chǔ)與鏈接存儲(chǔ)相結(jié)合的存儲(chǔ)方法，具體方法為：將頂點(diǎn) Vi的所有鄰接點(diǎn)鏈成一個(gè) 單鏈表，稱為頂點(diǎn) Vi的邊表(對(duì)于有向圖則稱為出邊表)，邊表的頭指針和頂點(diǎn)的數(shù)據(jù)信息采用順序存儲(chǔ)

34、 （稱為頂點(diǎn)表）。所以，在鄰接表中存在兩種結(jié)點(diǎn)：頂點(diǎn)表結(jié)點(diǎn)和邊表結(jié)點(diǎn)。 vertex firstedge 頂點(diǎn)表結(jié)點(diǎn) 鄰接表表示的結(jié)點(diǎn)結(jié)構(gòu) adjvex n ext 邊表結(jié)點(diǎn) 其中，vertex :數(shù)據(jù)域，存放頂點(diǎn)信息; firstedge :指針域，邊表的頭指針; adjvex :鄰接點(diǎn)域，存放邊該頂點(diǎn)的鄰接點(diǎn)在頂點(diǎn)表中的下標(biāo); next :指針域，指向邊表中的下一個(gè)結(jié)點(diǎn)。 鄰接表的存儲(chǔ)結(jié)構(gòu)定義如下: struct ArcNode //定義邊表結(jié)點(diǎn) { int adjvex; II鄰接點(diǎn)域 ArcNode *n e

35、xt; }； struct VertexNode II定義頂點(diǎn)表結(jié)點(diǎn) { ElemType vertex; II ElemType 表示不確定的數(shù)據(jù)類型 ArcNode *firstedge; }； #define MaxSize 10 typedef struct { VertexNode adjlist[MaxSize]; II 頂點(diǎn)表 int vertexNum, arcNum; II圖的頂點(diǎn)數(shù)和邊數(shù) } ALGraph; 圖的遍歷次序定義 深度優(yōu)先遍歷 從圖中某頂點(diǎn)v出發(fā)進(jìn)行深度優(yōu)先遍歷的基本思想是： ① 訪問(wèn)頂點(diǎn)V； ② 從v的未被訪問(wèn)的鄰接點(diǎn)中選取

36、一個(gè)頂點(diǎn) w，從w出發(fā)進(jìn)行深度優(yōu)先遍歷; ③ 重復(fù)上述兩步，直至圖中所有和 v有路徑相通的頂點(diǎn)都被訪問(wèn)到。 廣度優(yōu)先遍歷 精彩文檔 從圖中某頂點(diǎn)v出發(fā)進(jìn)行廣度優(yōu)先遍歷的基本思想是： ① 訪問(wèn)頂點(diǎn)V ； ② 依次訪問(wèn)V的各個(gè)未被訪問(wèn)的鄰接點(diǎn) V1 , V2 , , Vk； ③ 分別從Vi , V2,…，Vk出發(fā)依次訪問(wèn)它們未被訪問(wèn)的鄰接點(diǎn)，直至圖中所有與頂點(diǎn) V有路徑相通的 頂點(diǎn)都被訪問(wèn)到。 ? 最小生成樹(shù)的定義 設(shè)G=(V, E)是一個(gè)無(wú)向連通網(wǎng)，生成樹(shù)上各邊的權(quán)值之和稱為該生成樹(shù)的代價(jià)， 在G的所有生成樹(shù)中， 代價(jià)最小的生成樹(shù)稱為最小生成樹(shù)。 ? 普里姆(Prim

37、)算法的基本思想 設(shè)G=(V，曰是一個(gè)無(wú)向連通網(wǎng)， 令T=(U,TE)是G的最小生成樹(shù)。T的初始狀態(tài)為 U={vo}(vo € V), TE={ }，然后重復(fù)執(zhí)行下述操作：在所有 u € U , V € V-U的邊中找一條代價(jià)最小的邊 (u , v)并入邊集TE, 同時(shí)v并入頂點(diǎn)集U，直至U= V為止。 ? 克魯斯卡爾(Kruskal )算法的基本思想 設(shè)無(wú)向連通網(wǎng)為 G = (V, E),令G的最小生成樹(shù)為 T=(U , TE)，其初態(tài)為U= V, TE={}，然后按照邊 的權(quán)值由小到大的順序，依次考察邊集 E中的各條邊。若被考察邊的兩個(gè)頂點(diǎn)屬于 T的兩個(gè)不同的連通分 量，則將此

38、邊加入到 TE中，同時(shí)把兩個(gè)連通分量連接為一個(gè)連通分量；若被考察邊的兩個(gè)頂點(diǎn)屬于同一個(gè) 連通分量，則舍去此邊，以免造成回路。如此下去，當(dāng) T中的連通分量個(gè)數(shù)為 1時(shí)，此連通分量便為 G的 一棵最小生成樹(shù)。 ? 迪杰斯特拉(Dijkstra )算法的基本思想 設(shè)置集合S存放已經(jīng)找到最短路徑的頂點(diǎn)， S的初始狀態(tài)只包含源點(diǎn) v ,對(duì)Vi€ V-S,假設(shè)從源點(diǎn)v到 Vi的有向邊為最短路徑。以后每求得一條最短路徑 V,…，Vk，就將Vk加入集合S中，并將路徑V,…，Vk , Vi 與原來(lái)的假設(shè)相比較，取路徑長(zhǎng)度較小者為當(dāng)前最短路徑。重復(fù)上述過(guò)程，直到集合 V中全部頂點(diǎn)加入到 集合S中。 ?

39、 Floyd算法的基本思想 假設(shè)從Vi到Vj的弧(若從Vi到Vj的弧不存在，則將其弧的權(quán)值看成8)是最短路徑，然后進(jìn)行 n次試 探。若Vi,…,Vk和Vk,…，Vj分別是從Vi到Vk和從Vk到Vj中間頂點(diǎn)的序號(hào)不大于 k-1的最短路徑，則將Vi,…, Vk,…，出和已經(jīng)得到的從 Vi到出中間頂點(diǎn)的序號(hào)不大于 k-1的最短路徑相比較，取長(zhǎng)度較短者為從 Vi到Vj 中間頂點(diǎn)的序號(hào)不大于 k的最短路徑。 ? AOV網(wǎng)的定義 在一個(gè)表示工程的有向圖中，用頂點(diǎn)表示活動(dòng)，用弧表示活動(dòng)之間的優(yōu)先關(guān)系，稱這樣的有向圖為頂 點(diǎn)表示活動(dòng)的網(wǎng)，簡(jiǎn)稱 AOV網(wǎng)。 ? 拓?fù)湫蛄械亩x 設(shè)G=(V, E)是一

40、個(gè)具有n個(gè)頂點(diǎn)的有向圖， V中的頂點(diǎn)序列vi, V2, -, Vn稱為一個(gè)拓?fù)湫蛄?，?dāng)且僅 當(dāng)滿足下列條件：若從頂點(diǎn) Vi到Vj有一條路徑，則在頂點(diǎn)序列中頂點(diǎn) Vi必在頂點(diǎn)Vj之前。 ? 拓?fù)渑判虻幕舅枷? 對(duì)AOV網(wǎng)進(jìn)行拓?fù)渑判虻幕舅枷胧牵? ⑴ 從AOV網(wǎng)中選擇一個(gè)沒(méi)有前驅(qū)的頂點(diǎn)并且輸出它； ⑵ 從AOV網(wǎng)中刪去該頂點(diǎn)，并且刪去所有以該頂點(diǎn)為尾的?。? ⑶ 重復(fù)上述兩步，直到全部頂點(diǎn)都被輸出，或 AOV網(wǎng)中不存在沒(méi)有前驅(qū)的頂點(diǎn)。 ? 查找算法的時(shí)間性能 查找算法用關(guān)鍵碼的比較次數(shù)來(lái)度量查找算法的時(shí)間性能。對(duì)于查找成功的情況，將關(guān)鍵碼比較次數(shù) 的數(shù)學(xué)期望值定義為平均查找長(zhǎng)度，即：

41、 n ASL pi 5 i 1 其中，n表示問(wèn)題規(guī)模，即查找集合中的記錄個(gè)數(shù)； pi表示查找第i個(gè)記錄的概率；Ci表示查找第i個(gè)記錄 所需的關(guān)鍵碼的比較次數(shù)。 ? 順序查找算法的時(shí)間復(fù)雜度 對(duì)于具有n個(gè)記錄的順序表，查找第 i個(gè)記錄時(shí)，需進(jìn)行 n-i+1次關(guān)鍵碼的比較。設(shè)每個(gè)記錄的查找 概率相等，查找成功時(shí)，順序查找的平均查找長(zhǎng)度為： O （n）；查找不成功時(shí)，關(guān)鍵碼的比較次數(shù)是 n+1次, 則查找失敗的平均查找長(zhǎng)度為 O（ n）。 ? 順序查找的適用情況 順序查找對(duì)表中記錄的存儲(chǔ)沒(méi)有任何要求，順序存儲(chǔ)和鏈接存儲(chǔ)均可應(yīng)用；對(duì)表中記錄的有序性也沒(méi) 有要求，無(wú)論記錄是否按關(guān)

42、鍵碼有序均可應(yīng)用。 ? 折半查找的適用情況 折半查找（也稱對(duì)半查找、對(duì)分查找、二分查找）要求線性表中的記錄必須按關(guān)鍵碼有序，并且必須 采用順序存儲(chǔ)。 ? 折半查找的基本思想 取有序表的中間記錄作為比較對(duì)象，則 （1 ）若給定值與中間記錄的關(guān)鍵碼相等，則查找成功； （2 ）若給定值小于中間記錄的關(guān)鍵碼，則在中間記錄的左半?yún)^(qū)繼續(xù)查找； （3 ）若給定值大于中間記錄的關(guān)鍵碼，則在中間記錄的右半?yún)^(qū)繼續(xù)查找。 不斷重復(fù)上述過(guò)程，直到查找成功，或所查找的區(qū)域無(wú)記錄，查找失敗。 ? 折半查找的時(shí)間復(fù)雜度 具有n個(gè)結(jié)點(diǎn)的折半查找判定樹(shù)的深度為 log2 n 1。 最好情況：比較1次，即

43、查找的關(guān)鍵碼是判定樹(shù)的根結(jié)點(diǎn)； 最壞情況：比較次數(shù)為 log2 n 1，即查找的關(guān)鍵碼是判定樹(shù)的最下一層結(jié)點(diǎn)； 平均情況：折半查找的平均時(shí)間復(fù)雜度為 O（log 2n）。 查找不成功的比較次數(shù)最多不超過(guò)樹(shù)的深度，最多為 log2 n 1次。 ? 二叉排序樹(shù)的定義 二叉排序樹(shù)或者是一棵空的二叉樹(shù)，或者是具有下列性質(zhì)的二叉樹(shù)： ⑴ 若它的左子樹(shù)不空，則左子樹(shù)上 所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值； ⑵ 若它的右子樹(shù)不空，則右子樹(shù)上 所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值； ⑶ 它的左右子樹(shù)也都是二叉排序樹(shù)。 ? 二叉排序樹(shù)的查找性能 如果二叉排序樹(shù)是平衡的，則其查找效率為 O(log 2n)。

44、如果二叉排序樹(shù)為一棵斜樹(shù)，則其查找效率為 0(n)。因此，二叉排序樹(shù)的查找性能在 O(log2n)和O(n)之間。 ? 平衡二叉樹(shù)的定義 平衡二叉樹(shù)或者是一棵空的二叉排序樹(shù)，或者是具有下列性質(zhì)的二叉排序樹(shù)： ⑴根結(jié)點(diǎn)的左子樹(shù)和右子樹(shù)的深度最多相差 1。 ⑵根結(jié)點(diǎn)的左子樹(shù)和右子樹(shù)也都是平衡二叉樹(shù)。 ? 構(gòu)造平衡二叉樹(shù)的基本思想 在構(gòu)造二叉排序樹(shù)的過(guò)程中，每當(dāng)插入一個(gè)結(jié)點(diǎn)時(shí)，首先檢查是否因插入而破壞了樹(shù)的平衡性，若是， 則找出最小不平衡子樹(shù)，在保持二叉排序樹(shù)特性的前提下，調(diào)整最小不平衡子樹(shù)中各結(jié)點(diǎn)之間的鏈接關(guān)系， 進(jìn)行相應(yīng)的旋轉(zhuǎn)，使之成為新的平衡子樹(shù)。 ? 平衡調(diào)整的四種類型

45、 設(shè)結(jié)點(diǎn)A為最小不平衡子樹(shù)的根結(jié)點(diǎn)，對(duì)該子樹(shù)進(jìn)行平衡化調(diào)整有以下四種情況： ⑴LL型：結(jié)點(diǎn)x插在根結(jié)點(diǎn)A的左孩子的左子樹(shù)上。 ⑵RR型：結(jié)點(diǎn)x插在根結(jié)點(diǎn)A的右孩子的右子樹(shù)上。 ⑶LR型：結(jié)點(diǎn)x插在根結(jié)點(diǎn)A的左孩子的右子樹(shù)上。 ⑷RL型：結(jié)點(diǎn)x插在根結(jié)點(diǎn)A的右孩子的左子樹(shù)上。 ? 散列查找的基本思想 散列查找也稱為哈希查找、 Hash查找，其基本思想是：在記錄的存儲(chǔ)位置和它的關(guān)鍵碼之間建立一個(gè) 確定的對(duì)應(yīng)關(guān)系 H，使得每個(gè)關(guān)鍵碼 key和唯一的一個(gè)存儲(chǔ)位置 H(key)相對(duì)應(yīng)。在查找時(shí)，根據(jù)這個(gè)確定 的對(duì)應(yīng)關(guān)系找到給定值 k的映射H(k)，若查找集合中存在這個(gè)記錄，則必定在 H(

46、k)的位置上。 ? 散列查找的基本概念 采用散列技術(shù)將記錄存儲(chǔ)在一塊連續(xù)的存儲(chǔ)空間中，這塊連續(xù)的存儲(chǔ)空間稱為 散列表，將關(guān)鍵碼映射 為散列表中適當(dāng)存儲(chǔ)位置的函數(shù)稱為 散列函數(shù)，所得的存儲(chǔ)位置址稱為散列地址。 對(duì)于兩個(gè)不同的關(guān)鍵碼 ki^k2,有H(ki)= H(k2),即兩個(gè)不同的記錄需要存放在同一個(gè)存儲(chǔ)位置， 這種 現(xiàn)象稱為 沖突，ki和k2相對(duì)于H稱做同義詞。 ? 散列查找的關(guān)鍵問(wèn)題 采用散列技術(shù)需要考慮的兩個(gè)關(guān)鍵問(wèn)題是： ⑴散列函數(shù)的設(shè)計(jì)。如何設(shè)計(jì)一個(gè)簡(jiǎn)單、均勻、存儲(chǔ)利用率高的散列函數(shù)。 ⑵沖突的處理。如何采取合適的處理沖突方法來(lái)解決沖突。 ? 處理沖突的方法 開(kāi)放

47、定址法 用開(kāi)放定址法處理沖突得到的散列表叫做 閉散列表。 所謂開(kāi)放定址法，就是由關(guān)鍵碼得到的散列地址一旦產(chǎn)生了沖突，就去尋找下一個(gè)空的散列地址，只 要散列表足夠大，空的散列地址總能找到，并將記錄存入。 ① 線性探測(cè)法 當(dāng)發(fā)生沖突時(shí)，線性探測(cè)法從沖突位置的下一個(gè)位置起， 依次尋找空的散列地址， 即對(duì)于鍵值key ,設(shè) H (key )= d，閉散列表的長(zhǎng)度為 m，則發(fā)生沖突時(shí)，尋找下一個(gè)散列地址的公式為： 精彩文檔 Hi=(H(key) + di) % m (di=1 , 2，…，m-1 )。 線性探測(cè)法會(huì)出現(xiàn)非同義詞之間對(duì)同一個(gè)散列地址爭(zhēng)奪的現(xiàn)象，稱為 堆積或聚集。 ② 二

48、次探測(cè)法 當(dāng)發(fā)生沖突時(shí)，二次探測(cè)法尋找下一個(gè)散列地址的公式為： Hi=(H(key) + di)% m (di=1 2, - 1 2, 22,— 22，…，q2,— q2 且 q wm/2 ) ③ 隨機(jī)探測(cè)法 當(dāng)發(fā)生沖突時(shí)，隨機(jī)探測(cè)法探測(cè)下一個(gè)散列地址的位移量是一個(gè)隨機(jī)數(shù)列，即尋找下一個(gè)散列地址的 公式為： Hi=( H(key)+ di)% m (di是一個(gè)隨機(jī)數(shù)列，i=1 , 2, , m-1 ) 拉鏈法(鏈地址法) 用拉鏈法處理沖突構(gòu)造的散列表叫做 開(kāi)散列表。 拉鏈法的基本思想是：將所有散列地址相同的記錄，即所有關(guān)鍵碼為同義詞的記錄存儲(chǔ)在一個(gè)單鏈表 中 稱為同義詞子

49、表，在散列表中存儲(chǔ)的是所有同義詞子表的頭指針。 ? 直接插入排序的基本思想 直接插入排序的基本思想是：依次將待排序序列中的每一個(gè)記錄插入到一個(gè)已排好序的序列中，直到 全部記錄都排好序。 ? 直接插入排序算法的性能 ?時(shí)間性能 最好情況：待排序序列為正序，時(shí)間復(fù)雜度為 O( n); 最壞情況：待排序序列為逆序，時(shí)間復(fù)雜度為 0( n2)。 平均情況：待排序序列中各種可能排列的概率相同，時(shí)間復(fù)雜度為 0( n2)。 -空間性能 直接插入排序只需要一個(gè)記錄的輔助空間。 ?穩(wěn)定性 直接插入排序是一種穩(wěn)定的排序方法。 ? 希爾排序的基本思想 希爾排序的基本思想是：先將整個(gè)待排

50、序記錄序列分割成若干個(gè)子序列，在子序列內(nèi)分別進(jìn)行直接插 入排序，待整個(gè)序列基本有序時(shí)，再對(duì)全體記錄進(jìn)行一次直接插入排序。 ? 希爾排序算法的性能 ?時(shí)間性能 希爾排序算法的時(shí)間性能是所取增量的函數(shù)， 其時(shí)間性能在 O(n2)和O(nlog 2n)之間，當(dāng)n在某個(gè)特定 范圍時(shí)，希爾排序的時(shí)間性能約為 O(n1.3)。 ?空間性能 希爾排序只需要一個(gè)記錄的輔助空間，用于暫存當(dāng)前待插入的記錄。 ?穩(wěn)定性 希爾排序是一種不穩(wěn)定的排序方法。 ? 起泡排序的基本思想 起泡排序的基本思想是：兩兩比較相鄰記錄的關(guān)鍵碼，如果反序則交換，直到?jīng)]有反序的記錄為止。 ? 起泡排序算法的性能 ?

51、時(shí)間性能 最好情況：待排序記錄序列為正序，時(shí)間復(fù)雜度為 O(n)； 最壞情況：待排序記錄序列為反序，時(shí)間復(fù)雜度為 0( n2); 平均情況：時(shí)間復(fù)雜度為 0( n2)。 -空間性能 起泡排序只需要一個(gè)記錄的輔助空間，用來(lái)作為記錄交換的暫存單元。 ?穩(wěn)定性 起泡排序是一種穩(wěn)定的排序方法。 ? 快速排序的基本思想 快速排序又稱為分區(qū)交換排序，其基本思想是：首先選一個(gè)軸值(即比較的基準(zhǔn)) ，將待排序記錄分割 成獨(dú)立的兩部分，左側(cè)記錄的關(guān)鍵碼均小于或等于軸值，右側(cè)記錄的關(guān)鍵碼均大于或等于軸值，然后分別 對(duì)這兩部分重復(fù)上述過(guò)程，直到整個(gè)序列有序。 ? 快速排序的性能 ?時(shí)間性能

52、 最好情況：時(shí)間復(fù)雜度為 O( niog2 n)。 最壞情況：待排序記錄序列為正序或逆序，時(shí)間復(fù)雜度為 0( n2)。 平均情況：時(shí)間復(fù)雜度為 0( nlog2 n)。 ?空間性能 最好情況下為 O(log 2n)；最壞情況下，棧的深度為 0(n)；平均情況下，棧的深度為 O(log 2n)。 ?穩(wěn)定性 快速排序是一種不穩(wěn)定的排序方法。 ? 簡(jiǎn)單選擇排序的基本思想 簡(jiǎn)單選擇排序的基本思想是：第 i趟(1 wiwn-1 )排序通過(guò)n-i次關(guān)鍵碼的比較，在 n-i+1個(gè)記錄中選 取關(guān)鍵碼最小的記錄，并和第 i個(gè)記錄交換作為有序序列的第 i個(gè)記錄。 ? 簡(jiǎn)單選擇排序算法的性能

53、?時(shí)間性能 簡(jiǎn)單選擇排序最好、最壞和平均的時(shí)間復(fù)雜度均為 O（ n2）。 ?空間性能 在簡(jiǎn)單選擇排序過(guò)程中，只需要一個(gè)用來(lái)作為記錄交換的暫存單元。 ?穩(wěn)定性 簡(jiǎn)單選擇排序是一種不穩(wěn)定的排序方法。 ? 堆的定義 小根堆）； 堆是具有下列性質(zhì)的完全二叉樹(shù)：每個(gè)結(jié)點(diǎn)的值都小于或等于其左右孩子結(jié)點(diǎn)的值（稱為 或者每個(gè)結(jié)點(diǎn)的值都大于或等于其左右孩子結(jié)點(diǎn)的值（稱為 大根堆）。 ? 堆排序的基本思想 首先將待排序的記錄序列構(gòu)造成一個(gè)堆（假設(shè)利用大根堆），此時(shí)，選出了堆中所有記錄的最大者即 堆頂記錄，然后將它從堆中移走（通常將堆頂記錄和堆中最后一個(gè)記錄交換），并將剩余的記錄再調(diào)整成 堆，

54、這樣又找出了次大的記錄，以此類推，直到堆中只有一個(gè)記錄為止。 ? 堆排序算法的性能 ?時(shí)間性能 堆排序最好、最壞和平均的時(shí)間復(fù)雜度為 0（nlog 2n）。 ?空間性能 在堆排序算法中，只需要一個(gè)用來(lái)交換的暫存單元。 ?穩(wěn)定性 堆排序是一種不穩(wěn)定的排序方法。 ? 二路歸并排序的基本思想 將若干個(gè)有序序列進(jìn)行兩兩歸并，直至所有待排序記錄都在一個(gè)有序序列為止。 ? 二路歸并排序算法的性能 -時(shí)間性能 歸并排序算法最好、最壞、平均的時(shí)間性能的時(shí)間代價(jià)是 O(n| og2 n)。 ?空間性能 二路歸并排序在歸并過(guò)程中需要與原始記錄序列同樣數(shù)量的存儲(chǔ)空間，以便暫存歸并的中間結(jié)果，因 此其空間復(fù)雜度為 O( n)。 ?穩(wěn)定性 二路歸并排序是一種穩(wěn)定的排序方法。