數(shù)據(jù)結(jié)構(gòu)第7章查找

1、 2021年10月15日 2021年10月15日 2021年10月15日 第第7 7章查找章查找7.17.1查找的基本概念查找的基本概念7.27.2線性表的查找線性表的查找7.37.3樹表的查找樹表的查找7.47.4哈希表的查找哈希表的查找教學(xué)內(nèi)容教學(xué)內(nèi)容 2021年10月15日 1.熟練掌握順序表和有序表（熟練掌握順序表和有序表（折半查找折半查找）的查找算）的查找算法及其性能分析方法；法及其性能分析方法；2.熟練掌握熟練掌握二叉排序樹的構(gòu)造和查找二叉排序樹的構(gòu)造和查找算法及其性能算法及其性能分析方法；分析方法；3.掌握二叉排序樹的掌握二叉排序樹的插入插入算法，了解二叉排序樹的算法，了解二叉排

2、序樹的刪除算法；刪除算法；4.熟練掌握哈希函數(shù)熟練掌握哈希函數(shù)（除留余數(shù)法）（除留余數(shù)法）的構(gòu)造的構(gòu)造5.熟練掌握哈希函數(shù)熟練掌握哈希函數(shù)解決沖突的方法解決沖突的方法及其特點(diǎn)及其特點(diǎn) 教學(xué)目標(biāo)教學(xué)目標(biāo) 2021年10月15日 7.1 7.1 查找的基本概念查找的基本概念 查找表查找表: :由同一類型的數(shù)據(jù)元素（或記錄）構(gòu)成的集合由同一類型的數(shù)據(jù)元素（或記錄）構(gòu)成的集合 靜態(tài)查找表：靜態(tài)查找表：對(duì)查找表沒有修改操作對(duì)查找表沒有修改操作 動(dòng)態(tài)查找表：動(dòng)態(tài)查找表：對(duì)查找表具有修改操作對(duì)查找表具有修改操作 關(guān)鍵字關(guān)鍵字記錄中某個(gè)數(shù)據(jù)項(xiàng)的值，可用來識(shí)別一個(gè)記錄記錄中某個(gè)數(shù)據(jù)項(xiàng)的值，可用來識(shí)別一個(gè)記錄 主

3、關(guān)鍵字：主關(guān)鍵字：唯一標(biāo)識(shí)數(shù)據(jù)元素唯一標(biāo)識(shí)數(shù)據(jù)元素 次關(guān)鍵字：次關(guān)鍵字：可以標(biāo)識(shí)若干個(gè)數(shù)據(jù)元素可以標(biāo)識(shí)若干個(gè)數(shù)據(jù)元素是一種數(shù)據(jù)結(jié)構(gòu)是一種數(shù)據(jù)結(jié)構(gòu) 2021年10月15日 關(guān)鍵字的平均比較次數(shù)關(guān)鍵字的平均比較次數(shù)，也稱，也稱平均搜索長(zhǎng)度平均搜索長(zhǎng)度ASLASL( (Average Search LengthAverage Search Length) )n n：記錄的個(gè)數(shù)：記錄的個(gè)數(shù)pipi：查找第：查找第i i個(gè)記錄的概率個(gè)記錄的概率 ( ( 通常認(rèn)為通常認(rèn)為pi =1/n )pi =1/n )cici：找到第：找到第i i個(gè)記錄所需的比較次數(shù)個(gè)記錄所需的比較次數(shù)niiicpASL1查找算法的

4、評(píng)價(jià)指標(biāo)查找算法的評(píng)價(jià)指標(biāo) 2021年10月15日 7.2 7.2 線性表的查找線性表的查找一、順序查找（線性查找）一、順序查找（線性查找）二、折半查找（二分或?qū)Ψ植檎遥┒?、折半查找（二分或?qū)Ψ植檎遥?2021年10月15日 順序查找順序查找應(yīng)用范圍：應(yīng)用范圍：順序表或線性鏈表表示的靜態(tài)查找表順序表或線性鏈表表示的靜態(tài)查找表表內(nèi)元素之間無序表內(nèi)元素之間無序typedef struct ElemType *R; /表基址表基址 int length; /表長(zhǎng)表長(zhǎng)SSTable;順序表的表示順序表的表示 2021年10月15日 int LocateELem(SqList L,ElemType e)

5、 for (i=0;i0; - -i) for(i=n; i0; - -i) 或或 for(i=1; i=n; i+)for(i=1; i=n; i+) return i; 2021年10月15日 空間復(fù)雜度：一個(gè)輔助空間?？臻g復(fù)雜度：一個(gè)輔助空間。 時(shí)間復(fù)雜度：時(shí)間復(fù)雜度：1) 1) 查找成功時(shí)的平均查找長(zhǎng)度查找成功時(shí)的平均查找長(zhǎng)度 設(shè)表中各記錄查找概率相等設(shè)表中各記錄查找概率相等 ASLASLs s(n)=(1+2+ . +n)/n =(n+1)/2(n)=(1+2+ . +n)/n =(n+1)/22)2)查找不成功時(shí)的平均查找長(zhǎng)度查找不成功時(shí)的平均查找長(zhǎng)度 ASLASLf f =n+1

6、=n+1順序查找的性能分析順序查找的性能分析 2021年10月15日 算法簡(jiǎn)單，對(duì)表結(jié)構(gòu)無任何要求（順序和鏈?zhǔn)剑┧惴ê?jiǎn)單，對(duì)表結(jié)構(gòu)無任何要求（順序和鏈?zhǔn)剑?n n很大時(shí)查找效率較低很大時(shí)查找效率較低 改進(jìn)措施：改進(jìn)措施：非等概率非等概率查找時(shí)，可按照查找概率進(jìn)查找時(shí)，可按照查找概率進(jìn)行排序。行排序。順序查找算法有特點(diǎn)順序查找算法有特點(diǎn) 2021年10月15日 n n個(gè)數(shù)存在一維數(shù)組個(gè)數(shù)存在一維數(shù)組A1.nA1.n中，在進(jìn)行順序查找時(shí)，中，在進(jìn)行順序查找時(shí)，這這n n個(gè)數(shù)的排列個(gè)數(shù)的排列有序或無序有序或無序其平均查找長(zhǎng)度其平均查找長(zhǎng)度ASLASL不同不同。 練習(xí)練習(xí): :判斷對(duì)錯(cuò)判斷對(duì)錯(cuò)查找概率

7、相等時(shí)，查找概率相等時(shí)，ASL相同；相同；查找概率不等時(shí)，如果從前向后查找，則按查找概率查找概率不等時(shí)，如果從前向后查找，則按查找概率由大到小排列的有序表其由大到小排列的有序表其ASL要比無序表要比無序表ASL小。小。 2021年10月15日 lowhighmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92找找211 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75

8、80 88 92lowhighmid折半查找折半查找若若k=Rmid.key，查找成功，查找成功若若kRmid.key，則，則low=mid+1 2021年10月15日 1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid找找701 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid若若k=Rmid.key，查找成功，查

9、找成功若若kRmid.key，則，則low=mid+1 2021年10月15日 1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhigh1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92low highmid直至直至lowhigh時(shí)，查找失敗時(shí)，查找失敗 2021年10月15日 折半查找（非遞歸算法）折半查找（非遞歸算法） 設(shè)表長(zhǎng)為設(shè)表長(zhǎng)為n n，lowlow、highhigh和和midmid分別指向待查元素所分別指向待查元素所在區(qū)間的上界、下界和中點(diǎn)在區(qū)間的上界、下界和

10、中點(diǎn), ,k k為給定值為給定值 初始時(shí)，令初始時(shí)，令low=1,high=low=1,high=n,midn,mid= = (low+high)/2(low+high)/2 讓讓k k與與midmid指向的記錄比較指向的記錄比較若若k=k=Rmid.keyRmid.key，查找成功查找成功若若kkkRmid.keyRmid.key，則則low=mid+1low=mid+1 重復(fù)上述操作，直至重復(fù)上述操作，直至lowhighlowhigh時(shí)，查找失敗時(shí)，查找失敗 2021年10月15日 折半查找（遞歸算法）折半查找（遞歸算法）int Search_Bin (SSTable ST, keyTyp

11、e key, int low, int high) if(lowhigh) return 0; /查找不到時(shí)返回查找不到時(shí)返回0 mid=(low+high)/2; if(key與與ST.elemmid.key) return mid; else if(key小于小于ST.elemmid.key) ./遞歸遞歸 else. /遞歸遞歸 2021年10月15日 -13-46-79-101-22-34-55-67-88-910-1111-639147102581112h外結(jié)點(diǎn)外結(jié)點(diǎn)內(nèi)結(jié)點(diǎn)內(nèi)結(jié)點(diǎn)data.key進(jìn)行比較：進(jìn)行比較： 若若key等于等于T-data.key，則查找成功，返回根結(jié)點(diǎn)地，則

12、查找成功，返回根結(jié)點(diǎn)地址；址； 若若key小于小于T-data.key，則進(jìn)一步查找左子樹；，則進(jìn)一步查找左子樹； 若若key大于大于T-data.key，則進(jìn)一步查找右子樹。，則進(jìn)一步查找右子樹?！舅惴ㄋ枷胨惴ㄋ枷搿?2021年10月15日 BSTree SearchBST(BSTree T,KeyType key) if(!T) | key=T-data.key) return T; else if (keydata.key) return SearchBST(T-lchild,key);/在左子樹中繼續(xù)查找在左子樹中繼續(xù)查找 else return SearchBST(T-rchild,

13、key); /在右子樹中繼續(xù)查找在右子樹中繼續(xù)查找 / SearchBST【算法描述算法描述】 2021年10月15日 二叉排序樹的操作插入二叉排序樹的操作插入插入的元素插入的元素一定在一定在葉結(jié)點(diǎn)上葉結(jié)點(diǎn)上若二叉排序樹為空，則插入結(jié)點(diǎn)應(yīng)為若二叉排序樹為空，則插入結(jié)點(diǎn)應(yīng)為根結(jié)點(diǎn)根結(jié)點(diǎn)否則，繼續(xù)在其左、右子樹上查找否則，繼續(xù)在其左、右子樹上查找樹中已有，不再插入樹中已有，不再插入樹中沒有，樹中沒有，查找查找直至某個(gè)葉子結(jié)點(diǎn)的左子樹直至某個(gè)葉子結(jié)點(diǎn)的左子樹或右子樹為空為止，則插入結(jié)點(diǎn)應(yīng)為該或右子樹為空為止，則插入結(jié)點(diǎn)應(yīng)為該葉子結(jié)葉子結(jié)點(diǎn)點(diǎn)的左孩子或右孩子的左孩子或右孩子 2021年10月15日 4

14、512533372410061907820插入結(jié)點(diǎn)插入結(jié)點(diǎn)2020二叉排序樹的操作插入二叉排序樹的操作插入 2021年10月15日 10， 18， 3， 8， 12， 2， 710101810183101838101838 12101838 122101838 1227從空樹出發(fā)，經(jīng)過一系列的查找、插入操作之后，從空樹出發(fā)，經(jīng)過一系列的查找、插入操作之后，可生成一棵二叉排序樹可生成一棵二叉排序樹二叉排序樹的操作生成二叉排序樹的操作生成 2021年10月15日 不同插入次序的序列生成不同形態(tài)的二叉排序樹不同插入次序的序列生成不同形態(tài)的二叉排序樹4024551237122437405540，24，

15、12，37，5512，24，37，40，55二叉排序樹的操作生成二叉排序樹的操作生成 2021年10月15日 二叉排序樹的操作刪除二叉排序樹的操作刪除 2021年10月15日 2021年10月15日 2021年10月15日 第第i i層結(jié)點(diǎn)需比較層結(jié)點(diǎn)需比較i i次。在等概率的前提下，上述次。在等概率的前提下，上述兩圖的兩圖的平均查找長(zhǎng)度平均查找長(zhǎng)度為：為：)(35/ )54321 ()(2 . 25/ )23221 (11右圖左圖niiiniiicpcp40245512371224374055查找的性能分析查找的性能分析 2021年10月15日 平均查找長(zhǎng)度和二叉樹的形態(tài)有關(guān)，即，平均查找長(zhǎng)

16、度和二叉樹的形態(tài)有關(guān)，即，最好：最好：loglog2 2n n（形態(tài)勻稱，與二分查找的判定樹相似）（形態(tài)勻稱，與二分查找的判定樹相似）最壞最壞: : （n n+1)/2+1)/2（單支樹）（單支樹）查找的性能分析查找的性能分析40245512371224374055)( 35/ ) 54321 ()( 2 . 25/ ) 23221 (11右圖左圖niiiniiicpcp 2021年10月15日 問題：如何提高二叉排序樹的查找效率？問題：如何提高二叉排序樹的查找效率？盡量讓二叉樹的形狀均衡盡量讓二叉樹的形狀均衡左、右子樹是平衡二叉樹；左、右子樹是平衡二叉樹；所有結(jié)點(diǎn)的左、右子樹深度之差的絕對(duì)值

17、所有結(jié)點(diǎn)的左、右子樹深度之差的絕對(duì)值 1 1平衡因子平衡因子: :該結(jié)點(diǎn)左子樹與右子樹的高度差該結(jié)點(diǎn)左子樹與右子樹的高度差 2021年10月15日 v任一結(jié)點(diǎn)的平衡因子只能?。喝我唤Y(jié)點(diǎn)的平衡因子只能?。?1-1、0 0 或或 1 1；如果；如果樹中任意一個(gè)結(jié)點(diǎn)的平衡因子的絕對(duì)值大于樹中任意一個(gè)結(jié)點(diǎn)的平衡因子的絕對(duì)值大于1 1，則這棵二叉樹就失去平衡，不再是則這棵二叉樹就失去平衡，不再是AVLAVL樹；樹；v對(duì)于一棵有對(duì)于一棵有n n個(gè)結(jié)點(diǎn)的個(gè)結(jié)點(diǎn)的AVLAVL樹，其樹，其高度保持在高度保持在O(logO(log2 2n n) )數(shù)量級(jí)，數(shù)量級(jí)，ASLASL也保持在也保持在O(logO(log2

18、 2n n) )量級(jí)。量級(jí)。 2021年10月15日 (a) (a) 平衡樹平衡樹 (b) (b) 不平衡樹不平衡樹練習(xí)：判斷下列二叉樹是否練習(xí)：判斷下列二叉樹是否AVLAVL樹？樹？0 00 00 01 11 1-1-1-1-10 00 00 01 1-1-1 2021年10月15日 如果在一棵如果在一棵AVLAVL樹中插入一個(gè)新結(jié)點(diǎn)，就有可能造樹中插入一個(gè)新結(jié)點(diǎn)，就有可能造成失衡，此時(shí)必須成失衡，此時(shí)必須重新調(diào)整樹的結(jié)構(gòu)重新調(diào)整樹的結(jié)構(gòu)，使之恢復(fù)，使之恢復(fù)平衡。我們稱調(diào)整平衡過程為平衡。我們稱調(diào)整平衡過程為平衡旋轉(zhuǎn)平衡旋轉(zhuǎn)。LLLL平衡旋轉(zhuǎn)平衡旋轉(zhuǎn)RRRR平衡旋轉(zhuǎn)平衡旋轉(zhuǎn)LRLR平衡旋轉(zhuǎn)平

19、衡旋轉(zhuǎn)RLRL平衡旋轉(zhuǎn)平衡旋轉(zhuǎn)保證二叉排序樹保證二叉排序樹的次序不變的次序不變 2021年10月15日 若在若在A A的的左子樹的左子樹上插入左子樹的左子樹上插入結(jié)點(diǎn)，使結(jié)點(diǎn)，使A A的平衡因子從的平衡因子從1 1增加至增加至2 2，需要進(jìn)行一次，需要進(jìn)行一次順時(shí)針旋轉(zhuǎn)順時(shí)針旋轉(zhuǎn)。( (以以B B為旋轉(zhuǎn)軸）為旋轉(zhuǎn)軸）若在若在A A的的右子樹的右子樹上插入右子樹的右子樹上插入結(jié)點(diǎn)，使結(jié)點(diǎn)，使A A的平衡因子從的平衡因子從-1-1增加增加至至-2-2，需要進(jìn)行一次，需要進(jìn)行一次逆時(shí)針旋轉(zhuǎn)逆時(shí)針旋轉(zhuǎn)。( (以以B B為旋轉(zhuǎn)軸）為旋轉(zhuǎn)軸） 2021年10月15日 若在若在A的的右右子樹的子樹的左左子樹

20、上插入子樹上插入結(jié)結(jié)點(diǎn)，使點(diǎn)，使A的平衡因子從的平衡因子從-1增加至增加至-2，需要需要先進(jìn)行先進(jìn)行順順時(shí)針旋轉(zhuǎn)，再時(shí)針旋轉(zhuǎn)，再逆逆時(shí)時(shí)針旋轉(zhuǎn)針旋轉(zhuǎn)。(以插入的結(jié)點(diǎn)以插入的結(jié)點(diǎn)C為旋轉(zhuǎn)軸）為旋轉(zhuǎn)軸）若在若在A的的左左子樹的子樹的右右子樹上插入子樹上插入結(jié)點(diǎn)，使結(jié)點(diǎn)，使A的平衡因子從的平衡因子從1增加至增加至2，需要，需要先進(jìn)行先進(jìn)行逆逆時(shí)針旋轉(zhuǎn)，再時(shí)針旋轉(zhuǎn)，再順順時(shí)針旋轉(zhuǎn)。時(shí)針旋轉(zhuǎn)。(以插入的結(jié)點(diǎn)以插入的結(jié)點(diǎn)C為旋轉(zhuǎn)軸）為旋轉(zhuǎn)軸） 2021年10月15日 0 013130 037370 024240 013130 03737-1-113130 02424-1-124241313需要需要RR平衡

21、旋轉(zhuǎn)平衡旋轉(zhuǎn)(繞繞B逆轉(zhuǎn)逆轉(zhuǎn),B為根）為根）0 09090-1-12424-1-137370 053531 190903737需要需要RL平衡旋轉(zhuǎn)平衡旋轉(zhuǎn)(繞繞C先順后逆）先順后逆）0 037370 090900 053530 037370 090900 05353 2021年10月15日 變種的變種的AVLAVL樹樹紅紅黑樹黑樹 2021年10月15日 I see a brand new nodeI want to paint it black. We need a balanced tree,weve got to paint it black. I want to find my key

22、 in log n time - thats all,Rotating sub-trees round sure can be a ball. I see a brand new nodeI want to paint it black. Cant have a lot of red nodes,We must paint them black. Unfortunately, coding them can be a bitch.紅紅黑樹之歌黑樹之歌The Red-Black Tree SongIf we had half a brain to splay trees we would swi

23、tch. I see a brand new nodeI want to paint it black. No time for AVL treeswe must paint it BLACK. And if theyre still confusing, you should have no fear.Because outside this class, of them youll never hear. I wanna paint em BLACK. Paint nodes black. Again and again. 2021年10月15日 7.3 7.3 哈希表的查找哈希表的查找

24、基本思想：基本思想：記錄的存儲(chǔ)位置與關(guān)鍵字之間存在記錄的存儲(chǔ)位置與關(guān)鍵字之間存在對(duì)應(yīng)關(guān)系，對(duì)應(yīng)關(guān)系，Loc(i)=H(keyi)Loc(i)=H(keyi) 優(yōu)點(diǎn)：優(yōu)點(diǎn)：查找速度極快查找速度極快O(1),查找效率與元素個(gè)數(shù)查找效率與元素個(gè)數(shù)n無關(guān)無關(guān)哈希函數(shù)哈希函數(shù)關(guān)鍵字關(guān)鍵字集合集合存儲(chǔ)地址存儲(chǔ)地址集合集合hash 2021年10月15日 若將學(xué)生信息按如下方式存入計(jì)算機(jī)，如：若將學(xué)生信息按如下方式存入計(jì)算機(jī)，如：將將20010118102200101181020101的所有信息存入的所有信息存入VV0101 單元；單元；將將20010118102200101181020202的所有信息存入

25、的所有信息存入VV0202 單元；單元；將將20010118102200101181023131的所有信息存入的所有信息存入V31V31單元。單元。查找查找20010118102200101181021616的信息，可直接訪問的信息，可直接訪問V16V16！例例1 1 2021年10月15日 數(shù)據(jù)元素序列數(shù)據(jù)元素序列(14(14，2323，3939，9 9，2525，11)11)，若規(guī)定每個(gè)，若規(guī)定每個(gè)元素元素k k的存儲(chǔ)地址的存儲(chǔ)地址H H（k k）k k，請(qǐng)畫出存儲(chǔ)結(jié)構(gòu)圖。，請(qǐng)畫出存儲(chǔ)結(jié)構(gòu)圖。141411119 9內(nèi)容內(nèi)容地址地址3939252524242323141411119 9232

26、325253939例例2 2 2021年10月15日 根據(jù)哈希函數(shù)根據(jù)哈希函數(shù)H（k）k 查找查找key=9,key=9,則訪問則訪問H(9)=9H(9)=9號(hào)地址，若內(nèi)容為號(hào)地址，若內(nèi)容為9 9則成功；則成功；若查不到，則返回一個(gè)特殊值，如空指針或空記錄。若查不到，則返回一個(gè)特殊值，如空指針或空記錄。 如何查找如何查找141411119 9內(nèi)容內(nèi)容地址地址3939252524242323141411119 9232325253939 2021年10月15日 哈希方法哈希方法( (雜湊法雜湊法) )選取某個(gè)選取某個(gè)函數(shù)函數(shù)，依該函數(shù)按關(guān)鍵字計(jì)算元素的存儲(chǔ)位置，依該函數(shù)按關(guān)鍵字計(jì)算元素的存儲(chǔ)位置

27、，并按此存放；并按此存放；查找時(shí)，由同一個(gè)函數(shù)對(duì)給定值查找時(shí)，由同一個(gè)函數(shù)對(duì)給定值k k計(jì)算地址，計(jì)算地址，將將k k與地址與地址單元中元素關(guān)鍵碼進(jìn)行比單元中元素關(guān)鍵碼進(jìn)行比，確定查找是否成功。，確定查找是否成功。哈希函數(shù)哈希函數(shù)( (雜湊函數(shù)雜湊函數(shù)) )：哈希方法中使用的哈希方法中使用的轉(zhuǎn)換函數(shù)轉(zhuǎn)換函數(shù)有關(guān)術(shù)語有關(guān)術(shù)語 2021年10月15日 沖沖 突：突：不同的關(guān)鍵碼映射到同一個(gè)哈希地址不同的關(guān)鍵碼映射到同一個(gè)哈希地址哈希表哈希表( (雜湊表雜湊表) )：按上述思想構(gòu)造的表按上述思想構(gòu)造的表有關(guān)術(shù)語有關(guān)術(shù)語141411119 9內(nèi)容內(nèi)容地址地址3939252524242323141411

28、119 9232325253939同義詞：同義詞：具有具有相同函數(shù)值相同函數(shù)值的兩個(gè)關(guān)鍵字的兩個(gè)關(guān)鍵字key1 key2，但但H(key1)=H(key2) 2021年10月15日 （14，23，39，9，25，11）哈希函數(shù)：哈希函數(shù)：H(k)=k mod 72539239146個(gè)元素用個(gè)元素用7個(gè)個(gè)地址應(yīng)該足夠地址應(yīng)該足夠!H(14)=14%7=011H(25)=25%7=4H(11)=11%7=4同義詞同義詞 0 1 2 3 4 5 6沖突現(xiàn)象舉例沖突現(xiàn)象舉例 2021年10月15日 哈希函數(shù)在信息安全領(lǐng)域中的應(yīng)用哈希函數(shù)在信息安全領(lǐng)域中的應(yīng)用 2021年10月15日 wmic全稱全稱W

29、indows Management Instrumentation Command-line（Windows管理規(guī)范命令行），它提管理規(guī)范命令行），它提供了從命令行接口和批命令腳本執(zhí)行系統(tǒng)管理的支供了從命令行接口和批命令腳本執(zhí)行系統(tǒng)管理的支持。通過它我們可以執(zhí)行一些復(fù)雜的命令，從而更持。通過它我們可以執(zhí)行一些復(fù)雜的命令，從而更為有效地管理系統(tǒng)。為有效地管理系統(tǒng)。 點(diǎn)擊點(diǎn)擊“開始開始”菜單菜單“運(yùn)行運(yùn)行”，輸入，輸入“cmd”運(yùn)行運(yùn)行“命令提示符命令提示符”，在其中輸入如下命令，在其中輸入如下命令“wmic process get”。第一次使用。第一次使用wmic時(shí)，它會(huì)提示你安裝，時(shí)，它會(huì)提示

30、你安裝，安裝過程只需幾秒鐘。安裝過程只需幾秒鐘。MD5破解破解QQ密碼密碼 2021年10月15日 點(diǎn)擊點(diǎn)擊QQ主界面下方的主界面下方的“QQ游戲游戲”，游戲自動(dòng)登錄。，游戲自動(dòng)登錄。在在 “ 命 令 提 示 符命 令 提 示 符 ” 中 輸 入中 輸 入 “ w m i c p ro c e s s getc:123.txt”并回車。這條命令的作用是執(zhí)行并回車。這條命令的作用是執(zhí)行“wmic process get”命令并將結(jié)果保存在命令并將結(jié)果保存在c盤的盤的123.txt文件中。文件中。打開此文件，按下打開此文件，按下“Ctrl”+“F” ，以，以“QQgame”為為關(guān)鍵字進(jìn)行搜索，在進(jìn)

31、程的末尾處會(huì)看見類似的語句：關(guān)鍵字進(jìn)行搜索，在進(jìn)程的末尾處會(huì)看見類似的語句：START QQUIN:12345678 PWDHASH: sjTC1t9/B5zJKZWg9u236g= INCOG:1。將將“PWDHASH”和和“INCOG”之間的內(nèi)容復(fù)制下之間的內(nèi)容復(fù)制下來。這個(gè)就是來。這個(gè)就是QQ密碼在經(jīng)過密碼在經(jīng)過MD5加密后再進(jìn)行加密后再進(jìn)行BASE64編碼所得的結(jié)果。編碼所得的結(jié)果。 2021年10月15日 打開打開MD5在線破解網(wǎng)站：在線破解網(wǎng)站：，在其，在其中的文本框中輸入剛才得到的密文，點(diǎn)擊中的文本框中輸入剛才得到的密文，點(diǎn)擊“MD5”碰撞就可以對(duì)密文進(jìn)行解密了。碰撞就可以對(duì)密文

32、進(jìn)行解密了。 2021年10月15日 沖突是不可能避免的沖突是不可能避免的如何減少?zèng)_突如何減少?zèng)_突構(gòu)造好的哈希函數(shù)構(gòu)造好的哈希函數(shù)制定一個(gè)好的解決沖突方案制定一個(gè)好的解決沖突方案 2021年10月15日 哈希函數(shù)的構(gòu)造方法哈希函數(shù)的構(gòu)造方法根據(jù)元素集合的特性構(gòu)造根據(jù)元素集合的特性構(gòu)造地址空間盡量小地址空間盡量小均勻均勻直接定址法直接定址法 數(shù)字分析法數(shù)字分析法平方取中法平方取中法折疊法折疊法除留余數(shù)法除留余數(shù)法隨機(jī)數(shù)法隨機(jī)數(shù)法 2021年10月15日 Hash(key) = akey + b ( (a、b為常數(shù)為常數(shù)) )優(yōu)點(diǎn)：優(yōu)點(diǎn)：以關(guān)鍵碼以關(guān)鍵碼keykey的某個(gè)線性函數(shù)值為哈希的某個(gè)線性

33、函數(shù)值為哈希地址，不會(huì)產(chǎn)生沖突。地址，不會(huì)產(chǎn)生沖突。缺點(diǎn)：缺點(diǎn)：要占用連續(xù)地址空間，空間效率低。要占用連續(xù)地址空間，空間效率低。 直接定址法直接定址法 2021年10月15日 例：例： 100，300，500，700，800，900， 哈希函數(shù)哈希函數(shù)Hash(key)=key/1000 1 2 3 4 5 6 7 8 9900800700500300100直接定址法直接定址法 2021年10月15日 Hash(key)=key mod p (p是一個(gè)整數(shù)是一個(gè)整數(shù))關(guān)鍵：關(guān)鍵：如何選取合適的如何選取合適的p？技巧：技巧：設(shè)表長(zhǎng)為設(shè)表長(zhǎng)為m，取，取pm且為且為質(zhì)數(shù)質(zhì)數(shù) 除留余數(shù)法除留余數(shù)法 （

34、最常用重點(diǎn)掌握）（最常用重點(diǎn)掌握） 2021年10月15日 執(zhí)行速度（即計(jì)算哈希函數(shù)所需時(shí)間）；執(zhí)行速度（即計(jì)算哈希函數(shù)所需時(shí)間）； 關(guān)鍵字的長(zhǎng)度；關(guān)鍵字的長(zhǎng)度； 哈希表的大??；哈希表的大??； 關(guān)鍵字的分布情況；關(guān)鍵字的分布情況； 查找頻率。查找頻率。構(gòu)造哈希函數(shù)考慮的因素構(gòu)造哈希函數(shù)考慮的因素 2021年10月15日 1.開放開放定址法定址法處理沖突的方法處理沖突的方法2.鏈地址法鏈地址法 2021年10月15日 基本思想：基本思想：有沖突時(shí)就去有沖突時(shí)就去尋找下一個(gè)空尋找下一個(gè)空的哈希地的哈希地址，只要哈希表足夠大，空的哈希地址總址，只要哈希表足夠大，空的哈希地址總能找到，并將數(shù)據(jù)元素存入

35、。能找到，并將數(shù)據(jù)元素存入。 1.1.開放定址法（開地址法）開放定址法（開地址法）線性探測(cè)法線性探測(cè)法二次探測(cè)法二次探測(cè)法偽隨機(jī)探測(cè)法偽隨機(jī)探測(cè)法 2021年10月15日 Hi=(Hash(key)+di) mod m ( 1i m ) 其中：其中：m為哈希表長(zhǎng)度為哈希表長(zhǎng)度 di 為增量序列為增量序列 1，2，m-1，且，且di=i一旦沖突，就找下一個(gè)空地址存入一旦沖突，就找下一個(gè)空地址存入線性探測(cè)法線性探測(cè)法 2021年10月15日 關(guān)鍵碼集為關(guān)鍵碼集為 47，7，29，11，16，92，22，8，3，設(shè)：設(shè)：哈希表表長(zhǎng)為哈希表表長(zhǎng)為m=m=11； 哈希函數(shù)為哈希函數(shù)為Hash(key)=

36、key mod 11 0 1 2 3 4 5 6 7 8 9 10477 291116922283 47、7、11、16、92沒有沖突沒有沖突 Hash(29)=7，有沖突，由，有沖突，由H1=(Hash(29)+1) mod 11=8，哈希地址哈希地址8為空，因此將為空，因此將29存入存入 線性探測(cè)法線性探測(cè)法 2021年10月15日 線性探測(cè)法的特點(diǎn)線性探測(cè)法的特點(diǎn)優(yōu)點(diǎn)：優(yōu)點(diǎn)：只要哈希表未被填滿，只要哈希表未被填滿，保證能找到保證能找到一個(gè)空一個(gè)空地址單元存放有沖突的元素。地址單元存放有沖突的元素。缺點(diǎn)：缺點(diǎn)：可能使第可能使第i個(gè)哈希地址的同義詞存入第個(gè)哈希地址的同義詞存入第i+1個(gè)個(gè)地址

37、，這樣本應(yīng)存入第地址，這樣本應(yīng)存入第i+1個(gè)哈希地址的元素個(gè)哈希地址的元素變成了第變成了第i+2個(gè)哈希地址的同義詞，個(gè)哈希地址的同義詞，產(chǎn)，產(chǎn)生生“聚集聚集”現(xiàn)象，降低查找效率?，F(xiàn)象，降低查找效率。解決方案：解決方案：二次探測(cè)法二次探測(cè)法 2021年10月15日 二次探測(cè)法二次探測(cè)法關(guān)鍵碼集為關(guān)鍵碼集為 47，7，29，11，16，92，22，8，3，設(shè)：設(shè)： 哈希函數(shù)為哈希函數(shù)為Hash(key)=key mod 11 Hi=(Hash(key)di) mod m其中：其中：m為哈希表長(zhǎng)度，為哈希表長(zhǎng)度，m要求是某個(gè)要求是某個(gè)4k+3的質(zhì)數(shù)的質(zhì)數(shù)； di為增量序列為增量序列 12，-12，2

38、2，-22，q2 0 1 2 3 4 5 6 7 8 9 10829716924732211 Hash(3)=3，哈希地址沖突，由，哈希地址沖突，由H1=(Hash(3)+12) mod 11=4，仍然沖突；，仍然沖突；H2=(Hash(3)-12) mod 11=2，找到空的哈希地址，存入。找到空的哈希地址，存入。 2021年10月15日 偽隨機(jī)探測(cè)法偽隨機(jī)探測(cè)法Hi=(Hash(key)+di) mod m ( 1i m ) 其中：其中：m為哈希表長(zhǎng)度為哈希表長(zhǎng)度 di 為隨機(jī)數(shù)為隨機(jī)數(shù) 2021年10月15日 2.2.鏈地址法鏈地址法( (拉鏈法）拉鏈法）基本思想：基本思想：相同哈希地址

39、的記錄鏈成一單鏈表，相同哈希地址的記錄鏈成一單鏈表，m個(gè)哈個(gè)哈希地址就設(shè)希地址就設(shè)m個(gè)單鏈表個(gè)單鏈表，然后用用一個(gè)數(shù)組將，然后用用一個(gè)數(shù)組將m個(gè)單個(gè)單鏈表的表頭指針存儲(chǔ)起來，形成一個(gè)動(dòng)態(tài)的結(jié)構(gòu)鏈表的表頭指針存儲(chǔ)起來，形成一個(gè)動(dòng)態(tài)的結(jié)構(gòu)0 1 2 3 4 5 6 7 8 9 10 11 12 14127796855198420231011 2021年10月15日 鏈地址法的優(yōu)點(diǎn)：鏈地址法的優(yōu)點(diǎn)： 非同義詞不會(huì)沖突，無非同義詞不會(huì)沖突，無“聚集聚集”現(xiàn)象現(xiàn)象 鏈表上結(jié)點(diǎn)空間動(dòng)態(tài)申請(qǐng)，更適合于表長(zhǎng)不確鏈表上結(jié)點(diǎn)空間動(dòng)態(tài)申請(qǐng)，更適合于表長(zhǎng)不確定的情況定的情況 2021年10月15日 哈希表的查找哈希表

40、的查找給定給定k k值值計(jì)算計(jì)算H(k)H(k)此地址為空此地址為空關(guān)鍵字關(guān)鍵字=k=k查找失敗查找失敗查找成功查找成功按處理沖突按處理沖突方法計(jì)算方法計(jì)算HiHiY YN NY YN N給定值與關(guān)鍵字比較給定值與關(guān)鍵字比較 2021年10月15日 已知一組關(guān)鍵字已知一組關(guān)鍵字(19,14,23,1,68,20,84,27,55,11,10,79)(19,14,23,1,68,20,84,27,55,11,10,79) 哈希函數(shù)為：哈希函數(shù)為：H(key)=key MOD 13, H(key)=key MOD 13, 哈希表長(zhǎng)為哈希表長(zhǎng)為m=16m=16， 設(shè)每個(gè)記錄的查找概率相等設(shè)每個(gè)記錄的

41、查找概率相等(1) (1) 用線性探測(cè)再散列處理沖突，即用線性探測(cè)再散列處理沖突，即Hi=(H(key)+di) MOD mHi=(H(key)+di) MOD m0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1514 1 68 27 55 19 20 84 79 23 11 101 2 1 4 3 1 1 3 9 1 1 3 H(19)=6H(14)=1H(23)=10H(1)=1 沖突，沖突，H1=(1+1) MOD16=2H(68)=3H(20)=7H(27)=1 沖突，沖突，H1=(1+1)MOD16=2 沖突，沖突，H2=(1+2)MOD16=3 沖突，沖突，H3=(1+3)MOD16=4ASL=(1*6+2+3*3+4+9)/12=2.5哈希表的查找哈希表的查找 2021年10月15日 (2) (2) 用鏈地址法處理沖突用鏈地址法處理沖突0 1 2 3 4 5 6 7 8 9 10 11 12 1412779685519842023