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

2023年2月3日

數(shù)據(jù)結(jié)構(gòu)

2023年2月3日

2023年2月3日

第7章查找7.1查找的基本概念7.2

線性表的查找7.3

樹表的查找7.4哈希表的查找教學(xué)內(nèi)容

2023年2月3日

1.熟練掌握順序表和有序表（折半查找）的查找算法及其性能分析方法；2.熟練掌握二叉排序樹的構(gòu)造和查找算法及其性能分析方法；3.掌握二叉排序樹的插入算法，了解二叉排序樹的刪除算法；4.熟練掌握哈希函數(shù)（除留余數(shù)法）的構(gòu)造5.熟練掌握哈希函數(shù)解決沖突的方法及其特點(diǎn)

教學(xué)目標(biāo)

2023年2月3日

7.1查找的基本概念查找表:

由同一類型的數(shù)據(jù)元素（或記錄）構(gòu)成的集合靜態(tài)查找表： 對(duì)查找表沒有修改操作動(dòng)態(tài)查找表： 對(duì)查找表具有修改操作關(guān)鍵字 記錄中某個(gè)數(shù)據(jù)項(xiàng)的值，可用來識(shí)別一個(gè)記錄主關(guān)鍵字： 唯一標(biāo)識(shí)數(shù)據(jù)元素次關(guān)鍵字： 可以標(biāo)識(shí)若干個(gè)數(shù)據(jù)元素是一種數(shù)據(jù)結(jié)構(gòu)

2023年2月3日

關(guān)鍵字的平均比較次數(shù)，也稱平均搜索長(zhǎng)度ASL(AverageSearchLength)n：記錄的個(gè)數(shù)pi：查找第i個(gè)記錄的概率(通常認(rèn)為pi=1/n)ci：找到第i個(gè)記錄所需的比較次數(shù)查找算法的評(píng)價(jià)指標(biāo)

2023年2月3日

7.2線性表的查找一、順序查找（線性查找）二、折半查找（二分或?qū)Ψ植檎遥?/p>

2023年2月3日

順序查找應(yīng)用范圍：順序表或線性鏈表表示的靜態(tài)查找表表內(nèi)元素之間無序typedefstruct{ElemType*R;//表基址

intlength;//表長(zhǎng)}SSTable;順序表的表示

2023年2月3日

intLocateELem(SqListL,ElemTypee){for(i=0;i<L.length;i++)if(L.elem[i]==e)returni+1;return0;}改進(jìn)：把待查關(guān)鍵字key存入表頭（“哨兵”），從后向前逐個(gè)比較，可免去查找過程中每一步都要檢測(cè)是否查找完畢，加快速度。第2章在順序表L中查找值為e的數(shù)據(jù)元素

2023年2月3日

intSearch_Seq(SSTableST,KeyTypekey){

//若成功返回其位置信息，否則返回0

ST.R[0].key=key;

for(i=ST.length;ST.R[i].key!=key;--i);

//不用for(i=n;i>0;--i)或for(i=1;i<=n;i++)

returni;

}

2023年2月3日

空間復(fù)雜度：一個(gè)輔助空間。時(shí)間復(fù)雜度：1)查找成功時(shí)的平均查找長(zhǎng)度設(shè)表中各記錄查找概率相等

ASLs(n)=(1+2+...+n)/n=(n+1)/22)查找不成功時(shí)的平均查找長(zhǎng)度ASLf

=n+1順序查找的性能分析

2023年2月3日

算法簡(jiǎn)單，對(duì)表結(jié)構(gòu)無任何要求（順序和鏈?zhǔn)剑﹏很大時(shí)查找效率較低改進(jìn)措施：非等概率查找時(shí)，可按照查找概率進(jìn)行排序。順序查找算法有特點(diǎn)

2023年2月3日

n個(gè)數(shù)存在一維數(shù)組A[1..n]中，在進(jìn)行順序查找時(shí)，這n個(gè)數(shù)的排列有序或無序其平均查找長(zhǎng)度ASL不同。練習(xí):判斷對(duì)錯(cuò)查找概率相等時(shí)，ASL相同；查找概率不等時(shí)，如果從前向后查找，則按查找概率由大到小排列的有序表其ASL要比無序表ASL小。

2023年2月3日

lowhighmid

1234567891011513192137566475808892找211234567891011513192137566475808892lowhighmid1234567891011513192137566475808892lowhighmid折半查找若k==R[mid].key，查找成功若k<R[mid].key，則high=mid-1若k>R[mid].key，則low=mid+1

2023年2月3日

1234567891011513192137566475808892lowhighmid找701234567891011513192137566475808892lowhighmid1234567891011513192137566475808892lowhighmid若k==R[mid].key，查找成功若k<R[mid].key，則high=mid-1若k>R[mid].key，則low=mid+1

2023年2月3日

1234567891011513192137566475808892lowhigh1234567891011513192137566475808892lowhighmid直至low>high時(shí)，查找失敗

2023年2月3日

折半查找（非遞歸算法）設(shè)表長(zhǎng)為n，low、high和mid分別指向待查元素所在區(qū)間的上界、下界和中點(diǎn),k為給定值初始時(shí)，令low=1,high=n,mid=(low+high)/2讓k與mid指向的記錄比較若k==R[mid].key，查找成功若k<R[mid].key，則high=mid-1若k>R[mid].key，則low=mid+1重復(fù)上述操作，直至low>high時(shí)，查找失敗

2023年2月3日

折半查找（遞歸算法）intSearch_Bin(SSTableST,keyTypekey,intlow,inthigh){if(low>high)return0;//查找不到時(shí)返回0mid=(low+high)/2;if(key與ST.elem[mid].key)returnmid;elseif(key小于ST.elem[mid].key)

……..//遞歸

else…….//遞歸}

2023年2月3日

-13-46-79-101-22-34-55-67-88-910-1111-639147102581112h外結(jié)點(diǎn)內(nèi)結(jié)點(diǎn)><=折半查找的性能分析－判定樹1234567891011513192137566475808892若所有結(jié)點(diǎn)的空指針域設(shè)置為一個(gè)指向一個(gè)方形結(jié)點(diǎn)的指針，稱方形結(jié)點(diǎn)為判定樹的外部結(jié)點(diǎn)；對(duì)應(yīng)的，圓形結(jié)點(diǎn)為內(nèi)部結(jié)點(diǎn)。

2023年2月3日

-13-46-79-101-22-34-55-67-88-910-1111-639147102581112h外結(jié)點(diǎn)內(nèi)結(jié)點(diǎn)><=ASL＝1/11*(1*1＋2×2＋4×3+4*4)＝33/11=3練習(xí):假定每個(gè)元素的查找概率相等，求查找成功時(shí)的平均查找長(zhǎng)度。

2023年2月3日

查找成功時(shí)比較次數(shù)：為該結(jié)點(diǎn)在判定樹上的層次數(shù)，不超過樹的深度d=log2n+1查找不成功的過程就是走了一條從根結(jié)點(diǎn)到外部結(jié)點(diǎn)的路徑d或d-1。-13-46-79-101-22-34-55-67-88-910-1111-639147102581112h外結(jié)點(diǎn)內(nèi)結(jié)點(diǎn)><=

2023年2月3日

查找過程：每次將待查記錄所在區(qū)間縮小一半，比順序查找效率高,時(shí)間復(fù)雜度O(log2n)適用條件：采用順序存儲(chǔ)結(jié)構(gòu)的有序表，不宜用于鏈?zhǔn)浇Y(jié)構(gòu)折半查找的性能分析

2023年2月3日

7.3樹表的查找表結(jié)構(gòu)在查找過程中動(dòng)態(tài)生成對(duì)于給定值key若表中存在，則成功返回；否則插入關(guān)鍵字等于key的記錄二叉排序樹平衡二叉樹B-樹B+樹鍵樹

2023年2月3日

二叉排序樹或是空樹，或是滿足如下性質(zhì)的二叉樹：

(1)若其左子樹非空，則左子樹上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值；

(2)若其右子樹非空，則右子樹上所有結(jié)點(diǎn)的值均大于等于根結(jié)點(diǎn)的值；

(3)其左右子樹本身又各是一棵二叉排序樹二叉排序樹

2023年2月3日

練習(xí)下列圖形中，哪個(gè)不是二叉排序樹？

2023年2月3日

451253337241006190783，12，24，37，45，53，61，78，90，100遞增得到一個(gè)關(guān)鍵字的遞增有序序列練習(xí)中序遍歷二叉排序樹后的結(jié)果有什么規(guī)律？

2023年2月3日

若查找的關(guān)鍵字等于根結(jié)點(diǎn)，成功否則若小于根結(jié)點(diǎn)，查其左子樹若大于根結(jié)點(diǎn)，查其右子樹在左右子樹上的操作類似12225030011020099105230216二叉排序樹的操作－查找

2023年2月3日

（1）若二叉排序樹為空，則查找失敗，返回空指針。（2）若二叉排序樹非空，將給定值key與根結(jié)點(diǎn)的關(guān)鍵字T->data.key進(jìn)行比較：①若key等于T->data.key，則查找成功，返回根結(jié)點(diǎn)地址；②若key小于T->data.key，則進(jìn)一步查找左子樹；③若key大于T->data.key，則進(jìn)一步查找右子樹?！舅惴ㄋ枷搿?/p>

2023年2月3日

BSTreeSearchBST(BSTreeT,KeyTypekey){if((!T)||key==T->data.key)returnT; elseif(key<T->data.key)returnSearchBST(T->lchild,key); //在左子樹中繼續(xù)查找

elsereturnSearchBST(T->rchild,key); //在右子樹中繼續(xù)查找}//SearchBST【算法描述】

2023年2月3日

二叉排序樹的操作－插入插入的元素一定在葉結(jié)點(diǎn)上若二叉排序樹為空，則插入結(jié)點(diǎn)應(yīng)為根結(jié)點(diǎn)否則，繼續(xù)在其左、右子樹上查找樹中已有，不再插入樹中沒有，查找直至某個(gè)葉子結(jié)點(diǎn)的左子樹或右子樹為空為止，則插入結(jié)點(diǎn)應(yīng)為該葉子結(jié)點(diǎn)的左孩子或右孩子

2023年2月3日

4512533372410061907820插入結(jié)點(diǎn)20二叉排序樹的操作－插入

2023年2月3日

{10，18，3，8，12，2，7}10101810183101838101838121018381221018381227從空樹出發(fā)，經(jīng)過一系列的查找、插入操作之后，可生成一棵二叉排序樹二叉排序樹的操作－生成

2023年2月3日

不同插入次序的序列生成不同形態(tài)的二叉排序樹4024551237122437405540，24，12，37，5512，24，37，40，55二叉排序樹的操作－生成

2023年2月3日

二叉排序樹的操作－刪除將因刪除結(jié)點(diǎn)而斷開的二叉鏈表重新鏈接起來防止重新鏈接后樹的高度增加

2023年2月3日

2023年2月3日

刪除葉結(jié)點(diǎn)，只需將其雙親結(jié)點(diǎn)指向它的指針清零，再釋放它即可。被刪結(jié)點(diǎn)缺右子樹，可以拿它的左子女結(jié)點(diǎn)頂替它的位置，再釋放它。被刪結(jié)點(diǎn)缺左子樹，可以拿它的右子女結(jié)點(diǎn)頂替它的位置，再釋放它。被刪結(jié)點(diǎn)左、右子樹都存在，可以在它的右子樹中尋找中序下的第一個(gè)結(jié)點(diǎn)(關(guān)鍵碼最小),用它的值填補(bǔ)到被刪結(jié)點(diǎn)中，再來處理這個(gè)結(jié)點(diǎn)的刪除問題。

2023年2月3日

第i層結(jié)點(diǎn)需比較i次。在等概率的前提下，上述兩圖的平均查找長(zhǎng)度為：40245512371224374055查找的性能分析

2023年2月3日

平均查找長(zhǎng)度和二叉樹的形態(tài)有關(guān)，即，最好：log2n（形態(tài)勻稱，與二分查找的判定樹相似）最壞:（n+1)/2（單支樹）查找的性能分析40245512371224374055

2023年2月3日

問題：如何提高二叉排序樹的查找效率？

盡量讓二叉樹的形狀均衡左、右子樹是平衡二叉樹；所有結(jié)點(diǎn)的左、右子樹深度之差的絕對(duì)值≤1平衡二叉樹平衡因子:該結(jié)點(diǎn)左子樹與右子樹的高度差

2023年2月3日

任一結(jié)點(diǎn)的平衡因子只能?。?1、0或1；如果樹中任意一個(gè)結(jié)點(diǎn)的平衡因子的絕對(duì)值大于1，則這棵二叉樹就失去平衡，不再是AVL樹；對(duì)于一棵有n個(gè)結(jié)點(diǎn)的AVL樹，其高度保持在O(log2n)數(shù)量級(jí)，ASL也保持在O(log2n)量級(jí)。

2023年2月3日

(a)平衡樹(b)不平衡樹練習(xí)：判斷下列二叉樹是否AVL樹？00011-1-120001-1

2023年2月3日

如果在一棵AVL樹中插入一個(gè)新結(jié)點(diǎn)，就有可能造成失衡，此時(shí)必須重新調(diào)整樹的結(jié)構(gòu)，使之恢復(fù)平衡。我們稱調(diào)整平衡過程為平衡旋轉(zhuǎn)。LL平衡旋轉(zhuǎn)RR平衡旋轉(zhuǎn)LR平衡旋轉(zhuǎn)RL平衡旋轉(zhuǎn)保證二叉排序樹的次序不變

2023年2月3日

若在A的左子樹的左子樹上插入結(jié)點(diǎn)，使A的平衡因子從1增加至2，需要進(jìn)行一次順時(shí)針旋轉(zhuǎn)。(以B為旋轉(zhuǎn)軸）ABCABC若在A的右子樹的右子樹上插入結(jié)點(diǎn)，使A的平衡因子從-1增加至-2，需要進(jìn)行一次逆時(shí)針旋轉(zhuǎn)。(以B為旋轉(zhuǎn)軸）2）RR平衡旋轉(zhuǎn)：ABCABC1）LL平衡旋轉(zhuǎn)：

2023年2月3日

若在A的右子樹的左子樹上插入結(jié)點(diǎn)，使A的平衡因子從-1增加至-2，需要先進(jìn)行順時(shí)針旋轉(zhuǎn)，再逆時(shí)針旋轉(zhuǎn)。(以插入的結(jié)點(diǎn)C為旋轉(zhuǎn)軸）4）RL平衡旋轉(zhuǎn)：ABCABCABC若在A的左子樹的右子樹上插入結(jié)點(diǎn)，使A的平衡因子從1增加至2，需要先進(jìn)行逆時(shí)針旋轉(zhuǎn)，再順時(shí)針旋轉(zhuǎn)。(以插入的結(jié)點(diǎn)C為旋轉(zhuǎn)軸）ABCABCABC3）LR平衡旋轉(zhuǎn)：

2023年2月3日

013037024練習(xí)：請(qǐng)將下面序列構(gòu)成一棵平衡二叉排序樹

（13，24，37，90，53）013037-113024-124-213需要RR平衡旋轉(zhuǎn)(繞B逆轉(zhuǎn),B為根）090-124-137053190-237需要RL平衡旋轉(zhuǎn)(繞C先順后逆）037090053037090053

2023年2月3日

變種的AVL樹－－紅黑樹

2023年2月3日

IseeabrandnewnodeIwanttopaintitblack.Weneedabalancedtree,we'vegottopaintitblack.

I

wanttofindmykeyinlogntime--thatsall,Rotatingsub-trees'roundsurecanbeaball.IseeabrandnewnodeIwanttopaintitblack.Can'thavealotofrednodes,Wemustpaintthemblack.Unfortunately,codingthemcanbeabitch.紅黑樹之歌

TheRed-BlackTreeSongIfwehadhalfabraintosplaytreeswewouldswitch.IseeabrandnewnodeIwanttopaintitblack.NotimeforAVLtreeswemustpaintitBLACK.Andifthey'restillconfusing,youshouldhavenofear.Becauseoutsidethisclass,ofthemyou'llneverhear.Iwannapaint'emBLACK.Paintnodesblack.Againandagain.

2023年2月3日

7.3哈希表的查找基本思想：記錄的存儲(chǔ)位置與關(guān)鍵字之間存在對(duì)應(yīng)關(guān)系，Loc(i)=H(keyi)

優(yōu)點(diǎn)：查找速度極快O(1),查找效率與元素個(gè)數(shù)n無關(guān)哈希函數(shù)關(guān)鍵字集合存儲(chǔ)地址集合hash

2023年2月3日

若將學(xué)生信息按如下方式存入計(jì)算機(jī)，如：將2001011810201的所有信息存入V[01]單元；將2001011810202的所有信息存入V[02]單元；……將2001011810231的所有信息存入V[31]單元。查找2001011810216的信息，可直接訪問V[16]！例1

2023年2月3日

數(shù)據(jù)元素序列(14，23，39，9，25，11)，若規(guī)定每個(gè)元素k的存儲(chǔ)地址H（k）＝k，請(qǐng)畫出存儲(chǔ)結(jié)構(gòu)圖?！?4…11…9…內(nèi)容地址…39…25242314119232539例2

2023年2月3日

根據(jù)哈希函數(shù)H（k）＝k

查找key=9,則訪問H(9)=9號(hào)地址，若內(nèi)容為9則成功；若查不到，則返回一個(gè)特殊值，如空指針或空記錄。如何查找…14…11…9…內(nèi)容地址…39…25242314119232539

2023年2月3日

哈希方法(雜湊法)選取某個(gè)函數(shù)，依該函數(shù)按關(guān)鍵字計(jì)算元素的存儲(chǔ)位置，并按此存放；查找時(shí)，由同一個(gè)函數(shù)對(duì)給定值k計(jì)算地址，將k與地址單元中元素關(guān)鍵碼進(jìn)行比，確定查找是否成功。哈希函數(shù)(雜湊函數(shù))：哈希方法中使用的轉(zhuǎn)換函數(shù)有關(guān)術(shù)語

2023年2月3日

沖突：不同的關(guān)鍵碼映射到同一個(gè)哈希地址哈希表(雜湊表)：按上述思想構(gòu)造的表有關(guān)術(shù)語…14…11…9…內(nèi)容地址…39…25242314119232539同義詞：具有相同函數(shù)值的兩個(gè)關(guān)鍵字key1key2，但H(key1)=H(key2)

2023年2月3日

（14，23，39，9，25，11）哈希函數(shù)：H(k)=kmod72539239146個(gè)元素用7個(gè)地址應(yīng)該足夠!H(14)=14%7=011H(25)=25%7=4H(11)=11%7=4同義詞有沖突0123456沖突現(xiàn)象舉例

2023年2月3日

哈希函數(shù)在信息安全領(lǐng)域中的應(yīng)用

2023年2月3日

wmic全稱WindowsManagementInstrumentationCommand-line（Windows管理規(guī)范命令行），它提供了從命令行接口和批命令腳本執(zhí)行系統(tǒng)管理的支持。通過它我們可以執(zhí)行一些復(fù)雜的命令，從而更為有效地管理系統(tǒng)。點(diǎn)擊“開始”菜單→“運(yùn)行”，輸入“cmd”運(yùn)行“命令提示符”，在其中輸入如下命令“wmicprocessget”。第一次使用wmic時(shí)，它會(huì)提示你安裝，安裝過程只需幾秒鐘。MD5破解QQ密碼

2023年2月3日

點(diǎn)擊QQ主界面下方的“QQ游戲”，游戲自動(dòng)登錄。在“命令提示符”中輸入“wmicprocessget>c:\123.txt”并回車。這條命令的作用是執(zhí)行“wmicprocessget”命令并將結(jié)果保存在c盤的123.txt文件中。打開此文件，按下“Ctrl”+“F”，以“QQgame”為關(guān)鍵字進(jìn)行搜索，在進(jìn)程的末尾處會(huì)看見類似的語句：STARTQQUIN:12345678PWDHASH:sjTC1t9/B5zJKZWg9u236g==INCOG:1。將“PWDHASH”和“INCOG”之間的內(nèi)容復(fù)制下來。這個(gè)就是QQ密碼在經(jīng)過MD5加密后再進(jìn)行BASE64編碼所得的結(jié)果。

2023年2月3日

打開MD5在線破解網(wǎng)站：，在其中的文本框中輸入剛才得到的密文，點(diǎn)擊“MD5”碰撞就可以對(duì)密文進(jìn)行解密了。

2023年2月3日

沖突是不可能避免的如何減少?zèng)_突構(gòu)造好的哈希函數(shù)制定一個(gè)好的解決沖突方案

2023年2月3日

哈希函數(shù)的構(gòu)造方法根據(jù)元素集合的特性構(gòu)造地址空間盡量小均勻直接定址法數(shù)字分析法平方取中法折疊法除留余數(shù)法隨機(jī)數(shù)法

2023年2月3日

Hash(key)=a·key+b(a、b為常數(shù))優(yōu)點(diǎn)：以關(guān)鍵碼key的某個(gè)線性函數(shù)值為哈希地址，不會(huì)產(chǎn)生沖突。缺點(diǎn)：要占用連續(xù)地址空間，空間效率低。直接定址法

2023年2月3日

例：

{100，300，500，700，800，900}，哈希函數(shù)Hash(key)=key/1000123456789900800700500300100直接定址法

2023年2月3日

Hash(key)=keymodp(p是一個(gè)整數(shù))關(guān)鍵：如何選取合適的p？技巧：設(shè)表長(zhǎng)為m，取p≤m且為質(zhì)數(shù)

除留余數(shù)法

（最常用重點(diǎn)掌握）

2023年2月3日

①執(zhí)行速度（即計(jì)算哈希函數(shù)所需時(shí)間）；②關(guān)鍵字的長(zhǎng)度；③哈希表的大?。虎荜P(guān)鍵字的分布情況；⑤查找頻率。構(gòu)造哈希函數(shù)考慮的因素

2023年2月3日

1.開放定址法處理沖突的方法2.鏈地址法

2023年2月3日

基本思想：有沖突時(shí)就去尋找下一個(gè)空的哈希地址，只要哈希表足夠大，空的哈希地址總能找到，并將數(shù)據(jù)元素存入。1.開放定址法（開地址法）線性探測(cè)法二次探測(cè)法偽隨機(jī)探測(cè)法

2023年2月3日

Hi=(Hash(key)+di)modm(1≤i<m)

其中：m為哈希表長(zhǎng)度

di

為增量序列1，2，…m-1，且di=i一旦沖突，就找下一個(gè)空地址存入線性探測(cè)法

2023年2月3日

關(guān)鍵碼集為{47，7，29，11，16，92，22，8，3}，設(shè)：哈希表表長(zhǎng)為m=11；哈希函數(shù)為Hash(key)=keymod11

012345678910477△▲△△291116922283①

47、7、11、16、92沒有沖突②Hash(29)=7，有沖突，由H1=(Hash(29)+1)mod11=8，哈希地址8為空，因此將29存入③

3

連續(xù)移動(dòng)了兩次線性探測(cè)法

2023年2月3日

線性探測(cè)法的特點(diǎn)優(yōu)點(diǎn)：只要哈希表未被填滿，保證能找到一個(gè)空地址單元存放有沖突的元素。缺點(diǎn)：可能使第i個(gè)哈希地址的同義詞存入第i+1個(gè)地址，這樣本應(yīng)存入第i+1個(gè)哈希地址的元素變成了第i+2個(gè)哈希地址的同義詞，……，產(chǎn)生“聚集”現(xiàn)象，降低查找效率。解決方案：二次探測(cè)法

2023年2月3日

二次探測(cè)法關(guān)鍵碼集為{47，7，29，11，16，92，22，8，3}，設(shè)：哈希函數(shù)為Hash(key)=keymod11

Hi=(Hash(key)±di)modm其中：m為哈希表長(zhǎng)度，m要求是某個(gè)4k+3的質(zhì)數(shù)；

di為增量序列

12，-12，22，-22，…，q2

012345678910829716924732211△▲△△Hash(3)=3，哈希地址沖突，由H1=(Hash(3)+12)mod11=4，仍然沖突；H2=(Hash(3)-12)mod11=2，找到空的哈希地址，存入。

2023年2月3日

偽隨機(jī)探測(cè)法Hi=(Hash(key)+di)modm(1≤i<m)

其中：m為哈希表長(zhǎng)度

di

為隨機(jī)數(shù)

2023年2月3日

2.鏈地址法(拉鏈法）基本思想：相同哈希地址的記錄鏈成一單鏈表，m個(gè)哈希地址就設(shè)m個(gè)單鏈表，然后用用一個(gè)數(shù)組將m個(gè)單鏈表的表頭指針存儲(chǔ)起來，形成一個(gè)動(dòng)態(tài)的結(jié)構(gòu)012345678910111214^127796855198420231011^^^^^^^^^^^^

2023年2月3日

鏈地址法的優(yōu)點(diǎn)：非同義詞不會(huì)沖突，無“聚集”現(xiàn)象鏈表上結(jié)點(diǎn)空間動(dòng)態(tài)申請(qǐng)，更適合于表長(zhǎng)不確定的情況

2023年2月3日

哈希表的查找給定k值計(jì)算H(k)此地址為空關(guān)鍵字==k查找失敗查找成功按處理沖突方法計(jì)算HiYNYN給定值與關(guān)鍵字比較

2023年2月3日

已知一組關(guān)鍵字(19,14,23,1,68,20,84,27