數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)匯編

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

韓萍muziq@sina數(shù)據(jù)結(jié)構(gòu)(DataStructure)：是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)（物理結(jié)構(gòu)）數(shù)據(jù)的邏輯結(jié)構(gòu)：數(shù)據(jù)元素之間的邏輯關(guān)系，分：集合——數(shù)據(jù)元素間除“同屬于一個(gè)集合”外，無其它關(guān)系線性結(jié)構(gòu)——一個(gè)對一個(gè)，如線性表、棧、隊(duì)列樹形結(jié)構(gòu)——一個(gè)對多個(gè)，如樹圖狀結(jié)構(gòu)——多個(gè)對多個(gè)，如圖或網(wǎng)概念及術(shù)語數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)設(shè)備中的映射，分：依次存儲(chǔ)結(jié)構(gòu)、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。依次存儲(chǔ)：以相對的存儲(chǔ)位置表示邏輯關(guān)系

鏈?zhǔn)酱鎯?chǔ)以以附加指針表示后繼關(guān)系a1a2a3a2

a1概念及術(shù)語§１．2算法和算法分析算法概念

對特定問題求解步驟的一種描述，是指令的有限序列，每條指令表示一個(gè)或多個(gè)操作。算法應(yīng)具備的特性：（2）

確定性：指令具有精確的含義，相同的輸入有相同的輸出。（1）有窮性：對合法的輸入值在執(zhí)行有窮步之后結(jié)束。（3）可行性：全部操作可經(jīng)已實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來實(shí)現(xiàn)（4）

輸入：0個(gè)或多個(gè)（5）

輸出：一個(gè)或多個(gè)（2）可讀性：便于閱讀和溝通

（3）健壯性：能夠?qū)斎氲姆欠〝?shù)據(jù)作出反應(yīng)和處理

（4）效率與低存儲(chǔ)量需求：效率指算法的執(zhí)行時(shí)間；存儲(chǔ)量需求指算法執(zhí)行過程中所須要的最大存儲(chǔ)空間。算法設(shè)計(jì)的要求（1）正確性：算法應(yīng)滿足具體問題的需求。

a.程序不含語法錯(cuò)誤

b.對于幾組輸入可得滿足要求的結(jié)果c.對于細(xì)心選擇的幾組典型、苛刻、帶有刁難性的輸入數(shù)據(jù)可得滿足要求的結(jié)果d.對一切合法的輸入數(shù)據(jù)都能得出產(chǎn)生要求的結(jié)果

算法效率的度量算法的時(shí)間效率主要由兩個(gè)因素確定：l所需處理問題的數(shù)據(jù)量大小，數(shù)據(jù)量大，所花費(fèi)的時(shí)間就多；l在解決問題的過程中，基本操作的執(zhí)行次數(shù)時(shí)間困難度：算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個(gè)函數(shù)，T(n)=O(f(n))好的算法應(yīng)當(dāng)能夠在數(shù)據(jù)量n增長的同時(shí)，函數(shù)T(n)的增長速度比較緩慢。

常見函數(shù)的增長率一個(gè)算法時(shí)間為O(1)的算法，它的基本運(yùn)算執(zhí)行的次數(shù)是固定的。總時(shí)間由一個(gè)常數(shù)(即零次多項(xiàng)式)來限界。一個(gè)時(shí)間為O(n2)的算法由一個(gè)二次多項(xiàng)式來限界。以下六種計(jì)算算法時(shí)間的多項(xiàng)式是最常用的。關(guān)系為:O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)指數(shù)時(shí)間的關(guān)系為：O(2n)<O(n!)<O(nn)其次章線性表：是n≥0特性質(zhì)相同的數(shù)據(jù)元素的有限序列。線性表可記作（a1,a2,…,an）n≥0基本操作： 建立、存取、插入、刪除、檢索、分解、排序等。

(a1,…,ai-1,ai,…,an)變更為(a1,…,ai-1,e,ai,…,an)a1a2

…ai-1ai

…ana1a2

…ai-1

…aiean表的長度加1基本運(yùn)算在線性表第i（1≤i≤n+1）個(gè)位置上插入元素e留意：C語言中的數(shù)組下標(biāo)從“0”起先，因此，若L是Sqlist類型的依次表，則表中第i個(gè)元素是l.elem[i-1]。statusinsert_sq(Sqlist&L，elemtypee，inti){if(i<1||i>L.length+1)//檢查i值是否合理returnERROR; if(L.length>=ListSize)//推斷是否溢出exit(overflow);for(j=L.length-1;j>=i-1;j--)L.elem[j+1]=L.elem[j];//騰出第i個(gè)位置L.elem[i-1]=e; //插入L.length++; //當(dāng)前表長加1returnOK;}這里的問題規(guī)模是表的長度，設(shè)它的值為n。該算法的時(shí)間主要花費(fèi)在循環(huán)的元素后移語句上，所需移動(dòng)元素的次數(shù)不僅依靠于表的長度，而且還與插入位置有關(guān)。 i位置 移動(dòng)次數(shù) 1 n 2 n-1 ︰ ︰ i n-i+1 n+1 0平均移動(dòng)次數(shù)：時(shí)間困難度：O（n）(a1,…,ai-1,ai,ai+1,…,an)變更為(a1,…,ai-1,ai+1,…,an)ai+1…an表的長度減1a1a2

…ai-1ai

ai+1

…ana1a2

…ai-1

在線性表中刪除第i（1≤i≤n）個(gè)元素，使statusdelete_sq(Sqlist&L,inti,elemtype&e){if(i<1||i>L.length)//檢查i值是否合理 returnERROR; e=L.elem[i-1];//C下標(biāo)從0起先for(j=i;j<=L.length-1;j++) L.elem[j-1]=L.elem[j];//刪除L.length--; returnOK;}該算法的時(shí)間分析與插入算法相像，結(jié)點(diǎn)的移動(dòng)次數(shù)也是由表長n和位置i確定。 i位置 移動(dòng)次數(shù) 1 n-1 2 n-2 ︰ ︰ i n-i n 0平均移動(dòng)次數(shù)：時(shí)間困難度：O（n）第三章棧和隊(duì)列棧和隊(duì)列也可以被稱作為操作受限的線性表。思索：假設(shè)有A,B,C三個(gè)元素進(jìn)S棧的依次是A,B,C，寫出全部可能的出棧序列。CBAACBABCCABBACBCA棧屬于加了限制條件的線性結(jié)構(gòu)；棧是后進(jìn)先出的線性表；進(jìn)棧和出棧只能從棧頂進(jìn)行；棧中的元素個(gè)數(shù)可以是0（空棧）；棧的元素的個(gè)數(shù)不能是無窮多個(gè)；每個(gè)棧中的元素的類型相同.棧的特性隊(duì)列（queue）是一種只允許在一端進(jìn)行插入，而在另一端進(jìn)行刪除的線性表，它是一種操作受限的線性表。3.2隊(duì)列(

Queue)

3.2.1隊(duì)列的定義及其運(yùn)算定義允許刪除的一端叫做隊(duì)頭(front)，允許插入的一端叫做隊(duì)尾(rear)。特性先進(jìn)先出(FIFO,FirstInFirstOut)a0

a1

a2

an-1frontrear依次123456刪除兩個(gè)元素之后的頭元素是？第四章串

零個(gè)或多個(gè)字符組成的有限序列。一般記S=‘a(chǎn)1a2....an’其中，S是串名，單引號括起的字符序列是串值；

2、串長

串中所包含的字符個(gè)數(shù)

3、空串長度為零的串，它不包含任何字符。

1、串4、空格串由一個(gè)或多個(gè)空格組成的串，其長度為串中空格字符的個(gè)數(shù)。

第五章§5.3廣義表的定義一、廣義表（GeneralList）廣義表中的元素即可以是單個(gè)元素（稱為原子）也可以是廣義表（稱為子表）。一般表示：LS=(a1,a2,…,an

)習(xí)慣上廣義表名用大寫字母，原子用小寫字母當(dāng)LS非空時(shí)，a1稱為LS

的表頭（head），其余元素組成的表（a2,…,an

）稱為表尾（tail）。例：A=() B=(e)C=(a,(b,c,d))D=(A,B,C)E=(a,E)F=(a,b,(c,(d)))廣義表特點(diǎn)：允許遞歸，可共享子表元素不僅有先后次序，而且有層次關(guān)系元素的層次：是包括該元素的括號對數(shù)表深：廣義表中元素的最大層次廣義表的存儲(chǔ)結(jié)構(gòu)（通常用鏈?zhǔn)剑V義表的擴(kuò)展線性鏈表存儲(chǔ)typedefstructglnode{ inttag;//0原子結(jié)點(diǎn)；1子表結(jié)點(diǎn)

union{ atomtypeatom;//原子結(jié)點(diǎn)的值域

structglnode*hp;//子表表頭指針

} structglnode*next;//下一元素指針}*glist;例：A=();B=(e);C=(a,(b,c,d));D=(A,B,C);E=(a,E)

都設(shè)一附加表頭結(jié)點(diǎn)1^^A1^B0e^1^C0a1^0b0c0d^1^1^11^D1^0a1^E作業(yè)練習(xí)求下列廣義表操作的結(jié)果：GetHead【(p,h,w)】；GetTail【(b,k,p,h)】；GetHead【((a,b),(c,d))】；GetTail【((a,b),(c,d))】；GetHead【GetTail【((a,b),(c,d))】】GetTail【GetHead【((a,b),(c,d))】】GetHead【GetTail【GetHead【((a,b),(c,d))】】】GetTail【GetHead【GetTail【((a,b),(c,d))】】】第六章ABCDEFGHK例如：先序序列：中序序列：后序序列：A

BCD

EFGHKBDC

A

EHGKFDCBHKGFE

A二叉樹的遍歷層次序列：ABECFDG

HK5.3.2依據(jù)二叉樹的遍歷構(gòu)造二叉樹3結(jié)點(diǎn)的5棵二叉樹的3種遍歷序列如表所示。存在狀況:ABCABCABCABCCAB因此，對3種遍序序列有結(jié)論：（1）由先序遍歷序列和中序遍歷序列能夠唯一確定一棵二叉樹。（2）由后序遍歷序列和中序遍歷序列能夠唯一確定一棵二叉樹。（3）由先序遍歷序列和后序遍歷序列不能唯一確定一棵二叉樹。例如：已知二叉樹BT的后序遍歷序列為：CBEHGIFDA，中序遍歷序列為：BCAEDGHFI，請構(gòu)造這棵二叉樹T。ABCDEFGHIADEFGHIBCFGHIABCDEGHABCDEFIABCDEFHGI由中序遍歷序列和后序遍歷序列構(gòu)造二叉樹的過程示意平衡二叉樹或者是一棵空樹，或者是具有下列性質(zhì)的二叉排序樹：(1)左、右子樹都是平衡二叉樹；(2)左、右子樹高度差的確定值<=1。若把左子樹與右子樹高度之差稱為結(jié)點(diǎn)x的平衡因子(balancefactor)，用bf(x)表示。則由平衡二叉樹定義知:Bf(x)=x左子樹深度-x右子樹深度1.平衡二叉樹的定義91000065504741853060727842-330-202141853060727842-1110010a.非平衡二叉樹b.平衡二叉樹全部結(jié)點(diǎn)的平衡因子只能取-1，0，1三個(gè)值之一。6.2堆排序堆是一棵依次存儲(chǔ)的完全二叉樹，若每個(gè)結(jié)點(diǎn)的關(guān)鍵字都不?。ù螅┯谄浜⒆咏Y(jié)點(diǎn)的關(guān)鍵字，則稱為大（小）根堆。968338112791236854724305391堆排序的基本思想是：首先，按堆的定義將R[1..n]調(diào)整為堆（這個(gè)過程稱為初始建堆），交換R[1]和R[n]；然后，將R[1..n-1]調(diào)整為堆，交換R[1]和R[n-1]；如此反復(fù)進(jìn)行，直到交換了R[1]和R[2]為止。6.3.1哈夫曼樹的定義設(shè)二叉樹具有n個(gè)帶權(quán)值的葉子結(jié)點(diǎn)，那么從根結(jié)點(diǎn)到各個(gè)葉子結(jié)點(diǎn)的路徑長度li與相應(yīng)結(jié)點(diǎn)權(quán)值wi的乘積的和，稱為二叉樹的帶權(quán)路徑長度，記作：

WPL=1×3+3×3+2×2+4×1=20。6.3.2哈夫曼樹的構(gòu)造（1）由給定的n個(gè)權(quán)值{W1,W2,…,Wn}構(gòu)造n棵只有一個(gè)葉子結(jié)點(diǎn)的二叉樹，從而得到一個(gè)二叉樹的集合F={T1,T2,…,Tn}。（2）在F中選取根結(jié)點(diǎn)的權(quán)值最小和次小的兩棵二叉樹作為左、右子樹構(gòu)造一棵新的二叉樹，新二叉樹根結(jié)點(diǎn)的權(quán)值為其左、右子樹根結(jié)點(diǎn)權(quán)值之和。（3）在集合F中刪除作為左、右子樹的兩棵二叉樹，并將新建立的二叉樹加入到集合F中。（4）重復(fù)（2）、（3）兩步，當(dāng)F中只剩下一棵二叉樹時(shí)，這棵二叉樹便是所要建立的哈夫曼樹。注：如此建立的二叉樹，沒有度為1的結(jié)點(diǎn)。如有n個(gè)葉子，必有m=2n-1個(gè)結(jié)點(diǎn)。9例如:已知權(quán)值W={5,6,2,9,7}56275276976713952767139527952716671329WPL=(6+7+9)*2+(5+2)*3=22*2+7*3=44+21=65留意：1.只算葉子2.分層計(jì)算3.路徑長為層數(shù)減1快速遠(yuǎn)距傳輸電文時(shí)，為使電文盡量短，接受不等長編碼，且運(yùn)用頻高的字符用較短的碼。并且使任何一個(gè)字符的編碼都不是同一字符集中另一個(gè)字符的編碼的前綴。

利用赫夫曼樹可以構(gòu)造出一種最優(yōu)前綴編碼使所傳電文的總長度最短,這種編碼就是赫夫曼編碼。6.3.3赫夫曼編碼

例：已知某通信息流只用8種字符，出現(xiàn)頻率為0.05，0.29，0.07，0.08，0.14，0.23，0.03，0.11，試設(shè)計(jì)赫夫曼編碼。設(shè)W=(5,29,7,8,14,23,3,11),n=8,則m=15.351123714291111111000000080010010110011301117111081111哈夫曼樹和編碼的代碼實(shí)現(xiàn)序號權(quán)重父號左子右子172193246532637218109101112131415W={7,19,2,6,32,3,21,10}N=8m=2*8-1=159953610101194111117181212281011131340271414601251515100131410010210300000400015016000017118001112345678第7章圖

7.1圖的基本概念

7.1.1圖的定義圖是一種非線性結(jié)構(gòu),它比樹形結(jié)構(gòu)更困難.圖中的數(shù)據(jù)元素之間是多對多關(guān)系,每一個(gè)元素都可能與其他元素有關(guān).圖是由一個(gè)非空的頂點(diǎn)集合和一個(gè)描述頂點(diǎn)之間關(guān)系即邊（或者?。┑募辖M成.7.2圖的存儲(chǔ)結(jié)構(gòu)

7.2.1鄰接矩陣鄰接矩陣是表示頂點(diǎn)之間相鄰關(guān)系的矩陣。設(shè)G=(V,E)是具有n個(gè)頂點(diǎn)的圖，則G的鄰接矩陣是n階方陣定義A：若G是網(wǎng)，則鄰接矩陣可定義為：Aij={0(i,j)VR1(i,j)VRBACDFE例如:矩陣的元素為ABCDEFABCDEF無向圖----對稱矩陣，半存即可，節(jié)約空間。每行(列)數(shù)字和即是頂點(diǎn)的度有向圖的鄰接矩陣為非對稱矩陣ABECDABCDEABCDE行和為出度列和為入度有向網(wǎng)的鄰接矩陣為非對稱矩陣ABECDABCDEABCDE12173157.3.2深度優(yōu)先搜尋深度優(yōu)先搜尋的基本思想是：從圖G中某個(gè)頂點(diǎn)vi動(dòng)身，訪問vi，然后選擇一個(gè)與vi相鄰且沒被訪問過的頂點(diǎn)v訪問，再從v動(dòng)身選擇一個(gè)與v相鄰且未被訪問的頂點(diǎn)vj訪問，依次接著。假如當(dāng)前已訪問過的頂點(diǎn)的全部鄰接頂點(diǎn)都已被訪問，則回退到已被訪問的頂點(diǎn)序列中最終一個(gè)擁有未被訪問的相鄰頂點(diǎn)w，從w動(dòng)身按同樣方法向前遍歷。直到圖中全部頂點(diǎn)都被訪問。從圖中某個(gè)頂點(diǎn)V0動(dòng)身，訪問此頂點(diǎn)，然后依次從V0的各個(gè)未被訪問的鄰接點(diǎn)動(dòng)身深度優(yōu)先搜尋遍歷圖，直至圖中全部都被訪問到。為確定每一個(gè)結(jié)點(diǎn)是否被訪問，必需設(shè)置訪問標(biāo)記。一、連通圖的深度優(yōu)先搜尋遍歷achdekf8234570FFFFFFFFF012345678TTTTTTTachdkfeachkfed訪問標(biāo)記:訪問次序:例如:achdkfe7.4最小生成樹在一個(gè)無向連通圖G中，假如取它的全部頂點(diǎn)和一部分邊構(gòu)成一個(gè)子圖G'，即：V(G')=V(G)和E(G')E(G)若邊集E(G‘)中的邊，既將圖G中的全部頂點(diǎn)連通，又不形成回路，則稱子圖G'是原圖G的一棵生成樹。產(chǎn)生最小生成樹主要有兩個(gè)算法，即普里姆算法和克魯斯卡爾算法。7.4.2

普里姆算法普里姆(Prim)算法的思路是：假設(shè)G=(V,E)是一個(gè)具有n個(gè)頂點(diǎn)的連通網(wǎng)，T=(U,TE)是G的最小生成樹，其中U是T的頂點(diǎn)集，TE是T的邊集，U和TE的初值均為空。算法起先時(shí)，首先從V中任取一個(gè)頂點(diǎn)（假定取v0），將它并入U(xiǎn)中，此時(shí)U={v0}，然后只要U是V的真子集（即UV），就從那些其一個(gè)端點(diǎn)已在T中，另一個(gè)端點(diǎn)仍在T外的全部邊中，找一條最短（即權(quán)值最?。┻?，假定為(vi,vj)，其中vi∈U，vj∈V-U，并把該邊(vi,vj)和頂點(diǎn)vj分別并入T的邊集TE和頂點(diǎn)集U。V0V3V5V2V1V46453821756V01V2closedge

i12345AdjvexLowcostV0V1V2V3V4V5V0V1V2V3V4V5v06v01v070v25v26v2440V5v55v5220V350V1v1330V41+4+2+5+3=15例如：UV-U7.7AOE網(wǎng)與關(guān)鍵路徑若在帶權(quán)的有向圖中，以頂點(diǎn)表示事務(wù)，有向邊表示活動(dòng)，邊上的權(quán)值表示完成該活動(dòng)的開銷（如該活動(dòng)所需的時(shí)間），則稱此帶權(quán)的有向圖為用邊表示活動(dòng)的網(wǎng)絡(luò)，簡稱AOE網(wǎng)（ActivityOnEdgenetwork）。在一個(gè)表示工程的AOE網(wǎng)中，應(yīng)當(dāng)不存在回路，網(wǎng)中僅存在一個(gè)入度為0的頂點(diǎn)（事務(wù)），稱為起先頂點(diǎn)（源點(diǎn)），它表示了整個(gè)工程的起先；網(wǎng)中也僅存在一個(gè)出度為0的頂點(diǎn)（事務(wù)），稱為結(jié)束頂點(diǎn)（匯點(diǎn)），它表示整個(gè)工程的結(jié)束。在找尋關(guān)鍵活動(dòng)時(shí)所用到的幾個(gè)參量的定義：（1）事務(wù)vk的最早發(fā)生時(shí)間（2）事務(wù)vk的最遲發(fā)生時(shí)間（3）活動(dòng)ai的最早起先時(shí)間（4）活動(dòng)ai的最遲起先時(shí)間因AOV網(wǎng)中的活動(dòng)可以并行，故工程完成的最短時(shí)間為從源點(diǎn)到匯點(diǎn)的最長路徑(關(guān)鍵路徑)。abcdefghk64521187244例如:“關(guān)鍵活動(dòng)”是：關(guān)鍵路徑上的活動(dòng)，權(quán)值增加

將使有向圖上的最長路徑的長度增加。源點(diǎn)匯點(diǎn)6174關(guān)鍵路徑a-b-e-h-k把從源點(diǎn)到頂點(diǎn)j的最長路徑長度叫做事務(wù)(頂點(diǎn))的最早發(fā)生時(shí)間ve(j);它是可能發(fā)生的最早時(shí)間。把從頂點(diǎn)k到匯點(diǎn)的最短路徑長度叫做事務(wù)(頂點(diǎn))的最遲發(fā)生時(shí)間vl(k).它是在不推遲工期的前提下最遲必需起先的時(shí)間。事務(wù)發(fā)生時(shí)間的計(jì)算公式:ve(源點(diǎn))=0;ve(k)=Max{ve(j)+dut(<j,k>)}例如：ve(k)=18,ve(h)=14,ve(f)=7;vl(匯點(diǎn))=ve(匯點(diǎn));vl(j)=Min{vl(k)–dut(<j,k>)}例如:vl(k)=18,vl(h)=14,vl(f)=10。設(shè)第i條弧為<j,k>則對第i項(xiàng)活動(dòng)言,“活動(dòng)(弧)”的最早起先時(shí)間e(i)e(i)=ve(j);e(<h,k>)=14;e(<f,h>)=7;“活動(dòng)(弧)”的最遲起先時(shí)間l(i)l(i)=vl(k)–dut(<j,k>);l(<h,k>)=14;e(<f,h>)=10。jkdut

什么是“關(guān)鍵活動(dòng)”？該活動(dòng)的最早起先時(shí)間=該活動(dòng)的最遲起先時(shí)間<h,k>在關(guān)鍵路徑上,e(h,k)=l(h,k),<f,h>不在關(guān)鍵路徑上e(f,h)=7,l(f,h)=10，推遲起先或延遲3天均不影響工期。abcdefghk6452118724400000000064571157151418181818181818181818161486610807拓?fù)溆行蛐蛄?a-d-f-c-b-e-h-g-k0645771514181814161078660000645777151414160236688710

算法的實(shí)現(xiàn)要點(diǎn):明顯，求ve的依次應(yīng)當(dāng)是按拓?fù)溆行虻拇涡?而求vl的依次應(yīng)當(dāng)是按拓?fù)淠嫘虻拇涡?因?yàn)橥負(fù)淠嫘蛐蛄屑礊橥負(fù)溆行蛐蛄械哪嫘蛄?，因此?yīng)當(dāng)在拓?fù)渑判虻倪^程中，另設(shè)一個(gè)“?！钡怯浲?fù)溆行蛐蛄小?.2二分查找所謂有序表,即表中的各元素按關(guān)鍵字的值升序(或降序)存放。折半查找又稱二分查找,是查找有序表的簡潔、有效的常用方法?；舅枷耄涸O(shè)低高端指針為L、H,則選取中間記錄M=(L+H)/2,將其關(guān)鍵字與給定關(guān)鍵字k進(jìn)行比較,若相等,則查找成功；否則,若k值比表中關(guān)鍵字值大,則令L=M+1,H不變,在表的后半部分接著對右子表進(jìn)行折半查找；若k值比表中關(guān)鍵字值小,則令H=M-1,L不變,接著對左子表進(jìn)行折半查找。每進(jìn)行一次比較,要么找到要查找的元素,要么將查找的范圍縮小一半。如此遞推,直到查找成功或把要查找的范圍縮小為空（查找失?。?。LHMK=210123456789102.指針：L=0H=4M=[(L+H)/2]=2HM3.指針：L=3H=4M=[(L+H)/2]=3LM查找過程構(gòu)成描述折半查找的判定樹，當(dāng)前的M作根，左子表的M作為左子樹的根，右子表的M作為右子樹的根，…

，若n=11，則判定樹如下?？煽闯鲋行虮闅v判定樹與表序相同，其查找次數(shù)恰好等于層數(shù)。528036914710L=0,H=10M=5L=6,H=10M=8L=0,H=4M=2L=0,H=1M=0L=9,H=10M=9L=3,H=4M=3L=6,H=7M=6L=1,H=1M=1L=4,H=4M=4L=7,H=7M=7L=10,H=10M=10例:5,13,19,21,37,56,64,75,80,88,92）例:5,13,19,21,37,56,64,75,80,88,92）1.指針：L=0H=10M=[(L+H)/2]=5LHMK=850123456789102.指針：L=6H=10M=[(L+H)/2]=8M3.指針：L=9H=10M=[(L+H)/2]=9L4.指針：L=9H=8H<L失敗LM不難看出：假如把建立的描述折半查找的判定樹中全部結(jié)點(diǎn)的空指針域上加一個(gè)指向稱為外部結(jié)點(diǎn)的方形結(jié)點(diǎn)的指針。則失敗時(shí)必指向外部指針，所以比較次數(shù)也不會(huì)超過層數(shù)。528036914710<02-35-68-90-13-46-79-101-24-57-8>10

折半查找算法intBinSearch(LineListR[],intn,KeyTypek){intlow=0,hight=n-1,mid;while(low<=hight){mid=(low+hight)/2;if(k==R[mid].key)returnmid;elseif(k<R[mid].key)hight=mid-1;elselow=mid+1;}return-1;}//Search_Bin算法分析：在二分查找過程中，關(guān)鍵字與k每比較一次查找范圍就縮小一半。因?yàn)楸容^次數(shù)等于元素所在層數(shù)h，而h層最多有2h-1個(gè)元素，設(shè)有序表中元素個(gè)數(shù)為n，則有則二分查找的最大查找長度為：二分查找的平均查找長度為O(log2n)，比依次查找速度快。因故課本錯(cuò)誤，請照此修改p168中7.5哈希表查找

7.5.1哈希表查找的基本概念哈希表查找的思想，它通過對元素的關(guān)鍵字值進(jìn)行某種運(yùn)算，干脆求出元素的地址，即運(yùn)用關(guān)鍵字到地址的干脆轉(zhuǎn)換方法，而不須要反復(fù)比較。因此，哈希表查找法又叫雜湊法或散列法。用一個(gè)函數(shù)H把數(shù)據(jù)集中的n個(gè)結(jié)點(diǎn)的關(guān)鍵字唯一地轉(zhuǎn)換成0..m-1范圍內(nèi)的數(shù)值，即對隨意結(jié)點(diǎn)的關(guān)鍵字ki，有：0≤H(ki)≤m-1（0≤i≤n-1）H(ki)是表與元素關(guān)鍵字之間映射關(guān)系的函數(shù)，稱為哈希函數(shù)。構(gòu)造哈希函數(shù)和建立解決沖突的方法是兩個(gè)主要任務(wù)。假定某教室有35個(gè)座位，哈希法則要限定學(xué)生所坐的位置應(yīng)與其學(xué)號的末兩位相同，則學(xué)號為0601605的學(xué)生應(yīng)坐編號為5的座位。這樣我們要找某個(gè)學(xué)生時(shí)只需依據(jù)其學(xué)號的末兩位到相應(yīng)座位上去找即可，不必一一比較了。在這個(gè)例子里，學(xué)生好比記錄，學(xué)號則為關(guān)鍵字，對關(guān)鍵字進(jìn)行的操作----哈希函數(shù)則是取其末兩位，用以確定記錄的位置。不同的關(guān)鍵字可能得到同一哈希地址，這種現(xiàn)象稱沖突。具有同一地址的關(guān)鍵字稱作同義詞。應(yīng)當(dāng)盡可能地避開沖突的發(fā)生?？傊?，哈希表就是依據(jù)設(shè)定的哈希函數(shù)和處理沖突的方法將一組關(guān)鍵字映像到一個(gè)有限的連續(xù)地址上，并以此地址作為存儲(chǔ)地址的表。這一映像過程稱為哈希造表或散列，所得存儲(chǔ)位置稱哈希地址或散列地址。7.5.2哈希函數(shù)的構(gòu)造方法一個(gè)好的哈希函數(shù)能將給定的數(shù)據(jù)集勻整地映射到給定的地址區(qū)間中。構(gòu)造哈希函數(shù)的常用方法：1.干脆定值法H(ki)=a*ki+b,例如按序號的若干倍加上一個(gè)常數(shù)存儲(chǔ)。2.數(shù)字分析法取關(guān)鍵字中某些取值較分散的數(shù)字位作為散列地址。再如取下列各元素的第6位和第7位：{100011211，100011322，100011413，100011556，100011613，100011756，100011823}的散列地址分別是：12，13，14，15，16，17，18。3.除留余數(shù)法H（k）=kmodm,如學(xué)號后兩位。4.平方取中法取關(guān)鍵字平方的中間幾位。5.折疊法把關(guān)鍵字分割成