1、1 圖的定義、術(shù)語(yǔ)和存儲(chǔ)結(jié)構(gòu)圖的定義、術(shù)語(yǔ)和存儲(chǔ)結(jié)構(gòu)n頂點(diǎn)數(shù)頂點(diǎn)數(shù)n和邊和邊(弧弧)的數(shù)目的數(shù)目e：q無(wú)向圖：無(wú)向圖：q有向圖：有向圖：n完全圖：有完全圖：有n(n-1)/2條邊的無(wú)向圖條邊的無(wú)向圖;有向完全圖：有有向完全圖：有n(n-1)條弧的有向圖條弧的有向圖;稀疏圖、稠密圖稀疏圖、稠密圖n子圖：子圖：G=(V,E),G=(V,E)，若，若V V,且且E E,則稱則稱G為為G的子圖的子圖n鄰接點(diǎn)：無(wú)向圖中，鄰接點(diǎn)：無(wú)向圖中，(v,v)E，則，則v,v互為鄰接點(diǎn)；互為鄰接點(diǎn)；頂點(diǎn)頂點(diǎn)v的度：與的度：與v相關(guān)聯(lián)的邊的數(shù)目，相關(guān)聯(lián)的邊的數(shù)目，TD(v)n有向圖中有向圖中,若若AA，則頂點(diǎn)，則頂點(diǎn)

2、v v鄰接到頂點(diǎn)鄰接到頂點(diǎn)vv，而頂點(diǎn)，而頂點(diǎn)vv鄰鄰接自接自v vq出度：以出度：以v為尾的弧的數(shù)目，為尾的弧的數(shù)目，OD(v)q入度：以入度：以v為頭的弧的數(shù)目，為頭的弧的數(shù)目，ID(v) qTD(v)=OD(v)+ID(v) 1(210nne) 1(0nnen路徑：路徑：q回路（環(huán)）回路（環(huán)）q簡(jiǎn)單路徑：頂點(diǎn)序列中頂點(diǎn)不重復(fù)的路徑。簡(jiǎn)單路徑：頂點(diǎn)序列中頂點(diǎn)不重復(fù)的路徑。 圖的存儲(chǔ)結(jié)構(gòu)圖的存儲(chǔ)結(jié)構(gòu)G1.arcs=G2.arcs=表結(jié)點(diǎn)表結(jié)點(diǎn)頭結(jié)點(diǎn)頭結(jié)點(diǎn)V1V2V3V4V5012340121410323242. 圖的遍歷圖的遍歷圖的遍歷目標(biāo)是解決圖的連通性問(wèn)題、拓?fù)渑判驁D的遍歷目標(biāo)是解決圖的

3、連通性問(wèn)題、拓?fù)渑判騿?wèn)題、關(guān)鍵路徑問(wèn)題。問(wèn)題、關(guān)鍵路徑問(wèn)題。圖的遍歷方法：深度優(yōu)先算法、廣度優(yōu)先算法圖的遍歷方法：深度優(yōu)先算法、廣度優(yōu)先算法深度優(yōu)先遍歷深度優(yōu)先遍歷廣度優(yōu)先遍歷廣度優(yōu)先遍歷n廣度優(yōu)先搜索遍歷類似于樹(shù)的層次遍歷廣度優(yōu)先搜索遍歷類似于樹(shù)的層次遍歷n算法算法 3.圖的連通性問(wèn)題圖的連通性問(wèn)題掌握連通分量的求法掌握連通分量的求法651255664365125566435 拓?fù)渑判蛲負(fù)渑判? 最短路徑最短路徑10050602010301051005060201030105查找成功：查找成功： pi = 1/n ci= 1,2,3n ASL=1/n1+2+n = (n+1)/2查找不成功：

4、查找不成功：ASL = n+1 , (n, n-11, 0)成功和不成功同概率：成功和不成功同概率：1/2 ASL = *1/n1+2+n+1/2(n+1) = (n+1)22 12 13 8 9 20 33 42 44 38 24 48 60 58 74 49 86 5322 12 13 8 9 20 33 42 44 38 24 48 60 58 74 49 86 5322 12 13 8 9 20 33 42 44 38 24 48 60 58 74 49 86 5348 861 7 13n平衡二叉樹(shù)q平衡因子：左子深度減去右子深度為 1， 0， 1的二叉排序樹(shù)。q二叉平衡樹(shù)的構(gòu)造（單項(xiàng)

5、左旋/單項(xiàng)右旋）， （左右旋，右左旋）2222右旋右旋左旋左旋左右旋左右旋右左旋右左旋n確定的對(duì)應(yīng)關(guān)系f：記錄的存儲(chǔ)位置 關(guān)鍵字n對(duì)應(yīng)關(guān)系f就是哈希函數(shù)：f(K)n哈希函數(shù)是一個(gè)映象，構(gòu)造哈希函數(shù)的方法：q直接定址法；哈希地址：直接取關(guān)鍵字或者關(guān)鍵字的線性函數(shù)H(key)=key; or H(key)=a*key+bq數(shù)字分析法；分析關(guān)鍵字，取關(guān)鍵字的若干數(shù)位組成哈希地址。q平方取中法；取關(guān)鍵字平方后的中間幾位為哈希地址較為常用的方法q折疊法：分割關(guān)鍵字、疊加q除留余數(shù)法：H(key)=key MOD p p=哈希表長(zhǎng)mn沖突現(xiàn)象：當(dāng)K1K2時(shí)f(K1)=f(K2)n解決沖突的方法q開(kāi)放定址法

6、；Hi=(H(key)+di) MOD m i=1,2,k (k=m-1)m為哈希表長(zhǎng)度；di為增量,di的取法：(1)線性探測(cè)再散列；di=1,2,3,(2)二次探測(cè)再散列；di=k2(3)偽隨機(jī)探測(cè)再散列 ：di=偽隨機(jī)數(shù)序列q再哈希：Hi=RHi(key)q鏈地址：所有關(guān)鍵字為同義詞的記錄存儲(chǔ)在同一線性鏈表中q公共溢出區(qū)：發(fā)生沖突時(shí)填入溢出表。 49 38 65 97 76 13 27 49 49 38 65 97 76 13 27 49先將整個(gè)待排序記錄分割成若干個(gè)子序列分別進(jìn)行直接插入排序，待整個(gè)序列中的記錄基本有序時(shí)，再進(jìn)行一次全體記錄的插入排序。49 38 65 97 76 13

7、 27 49 55 0449 1338 2765 4976 0413 27 49 55 04 49 38 65 97 76 13 55 38 7627 04 6549 49 97第一次第一次分組分組這就是第一趟這就是第一趟排序結(jié)果排序結(jié)果第二趟的第二趟的“增量增量”就要縮小就要縮小了！了！n冒泡排序：冒泡排序：q具體做法：依次比較第i個(gè)關(guān)鍵字和第i+1個(gè)關(guān)鍵字，大者排后，一趟得到最大值。（i=1,2,3,4,-n-1)49 38 65 97 76 13 27 4938 49 65 97 76 13 27 4938 49 65 76 97 13 27 4938 49 65 76 13 97 27

8、 4938 49 65 76 13 27 97 4938 49 65 76 13 27 49 9749 38 65 97 76 13 27 49lowhigh27 38 65 97 76 13 49lowhigh27 38 13 97 76 65 49lowhigh27 38 97 76 13 65 49lowhigh27 38 13 76 97 65 49lowhighnknTavglnkik2ikik2i+1kik2ikik2i+149 38 65 97 76 13 27 499749386527137649494938652713769749 38 65 49 76 13 27 9749 38 13 49 76 65 27 9749 38 13 49 76 65 27 9749493813276576974913382765769749 38 65 97 76 13 27 n n個(gè)記錄看個(gè)記錄看成成n n個(gè)有序個(gè)有序的序列的序列 38 49 65 97 13 76 27 第