專升本之查找

1、數(shù)據(jù)結(jié)構(gòu)之查找1)了解查找表和平均查找長度的定義查找表：由一類同一類型的數(shù)據(jù)元素(或記錄)構(gòu)成的集合。由于“集合”中的數(shù)據(jù)元素之間存在著完全松散的關(guān)系，因此查詢表是一種非常靈便的數(shù)據(jù)結(jié)構(gòu)。平均查找長度：注明：n是查找表的元素個數(shù)，Pi是查找第i個元素的概率，通常假設(shè)每個查找元素概率相同即 nCi=1i1(Pi=1/n),Ci是查找第i個元素需要比較的次數(shù)(輪到與這個元素比較時已經(jīng)比較了幾次)如：等概率的順序查找的ASL第一個元素須比較1次，第二個元素須比較2次第n個元素須比較n次，所以Ci=1+2+3+.n=(1+n)*n)/2。(書上的Ci一般是n-i+1,從后往前查找：第0個元素需要比較n

2、+1次，第1個元素需要比較n次.第n-1個元素須比較2次，第n個元素須比較1次，則第i個元素時需比較n-i+1)=1/n*i(1+n)*n)/2=(n+1)/2。2)掌握順序查找、折半查找和分塊查找算法設(shè)計和算法分析順序查找：/*順序查找，a為數(shù)組，n為要查找的數(shù)組長度，key為要查找的關(guān)鍵字*/intSequential_Search(int*a,intn,intkey)inti;for(i=1;in;i+)if(ai=key)returni;return0;公式：ASL成功=nPiCiASL=nPiCi=1/n*nCi因為每次循環(huán)都需要對是否越界，即是否小于n做判斷。事實上，還可以有更好一

3、點的辦法，設(shè)置一個哨兵，可以解決不需要每次讓i與n作比較。intSequential_Search2(int*a,intn,intkey)inti;a0=key;設(shè)置a0為關(guān)鍵字值，稱為哨兵i=n;循環(huán)從數(shù)組尾部開始while(ai!=key)i-；)returni;/返回0,說明查找失敗算法分析：對于這種算法來說，查找成功最好的情況就是在第一個位置就找到了，算法時間復(fù)雜度為O(1),最壞情況是在最后一個位置才找到，需要進行n次比較，時間復(fù)雜度為O(n),當(dāng)查找不成功需要在n+1次比較，時間復(fù)雜度為O(n)。平均查找次數(shù)ASL=(n+1)/2,最終時間復(fù)雜度為O(n)。缺點：當(dāng)平均查找長度較大

4、時即n很大時，查找效率較低，優(yōu)點：算法簡單且適應(yīng)面廣，對表的結(jié)構(gòu)無任何要求，對線性鏈表也同樣適用折半查找：/*折半查找*/intBinary_Search(int*a,intn,intkey)intlow,hight,mid;low=1;/定義最低下標(biāo)為記錄首位high=n;/定義最高下標(biāo)為記錄末位while(low=hight)mid=(low+high)/2;/折半if(keyamid)/若查找值比中值大low=mid+1;最低下標(biāo)調(diào)整到中位下標(biāo)大一位elsereturnmid;若相等說明mid即為查找到的位置算法分析：時間復(fù)雜度：？log2n?+1。ASL=log2(n+11,折半查找的

5、查找效率比順序查找高,但折半查找只適用于有序表，且限于順序存儲結(jié)構(gòu)(對線性鏈表無法有效的進行折半查找)分塊查找(索引順序查找)：塊與塊之間有序，塊內(nèi)無序(但第第1個塊中的元素，依次類推)2個塊中的所有元素均大于場景：若以索引順序表表示靜態(tài)查找表，除表本身外，尚需建立一個索引表，索引表包括兩項：關(guān)鍵字項（其值為該字表（塊）內(nèi)最大關(guān)鍵字）和指針項（指示孩子表的第一個記錄在表中的位置）例：假定需在一個表中查找key,子表有三個步驟：1、現(xiàn)將key依次和索引表中各最大關(guān)鍵字比較（），確定在哪一個具體的塊中2、然后在這個確定的塊中的第一個關(guān)鍵字開始順序查找算法：要建一個索引表1.structindex/

6、定義塊的結(jié)構(gòu)2.(3.intkey;/塊的關(guān)鍵字4.intstart;/塊的起始值5.intend;/塊的結(jié)束值6.index_table4;/定義結(jié)構(gòu)體數(shù)組1.intblock_search(intkey,inta)/自定義實現(xiàn)分塊查找2.(3.inti,j;4.i=1;5.while(iindex_tablei.key)/確定在哪個塊中6.i+;7.if(i3)/大于分得的塊數(shù)，則返回08.return0;9.j=indextablei.start;/j等于塊范圍的起始值10.while(jindextablei.end)/如果大于塊范圍的結(jié)束值，則說明沒有要查找的數(shù)，j置013.j=0;

7、14.returnj;15.ASL=L(查找索引表確定所在塊的查找，可順序查找也可折半查找)為順序查找)第一種：用順序查找確定所在塊ASL=1/2(n/s+s)+1第二種：用折半查找確定所在快ASL=log2(n/s+1)+s/2+L(塊中的查找，只能算法分析：2)掌握二叉排序樹的算法設(shè)計，了解平衡二叉樹、B-和B+樹的定義和查找過程二叉排序樹(二叉查找樹)：(1)若他的左子樹不空，則左子樹上所有節(jié)點的值均小于它的根節(jié)點的值；(2)若他的右子樹不空，則右子樹上的所有節(jié)點均大于他的根節(jié)點的值(3)他的左右數(shù)也分別為二叉排序樹算法設(shè)計：/二叉樹二叉鏈表結(jié)點的結(jié)構(gòu)定義typedefstructBiT

8、Node(intdata;structBiTNode*lchild,*rchild;BiTnode,*BiTree;遞歸版本：Node*bstree_search(BSTreex,Typekey)(if(x=NULL|x-key=key)returnx;if(keykey)returnbstree_search(x-left,key);elsereturnbstree_search(x-right,key);非遞歸版本：Node*iterative_bstree_search(BSTreex,Typekey)(while(x!=NULL)&(x-key!=key)(if(keykey)

9、x=x-left;elsex=x-right;)returnx;)插入和刪除：插入：StatusInsertBiTree(BiTree*T,intkey)BiTreep,s;if(!SearchBiTree(叮,key,NULL,&p)/查找不成功s=(BiTree)malloc(sizeof(BiTNode);s-data=key;s-lchild=s-rchild=NULL;if(!p)*T=s;/插入s為新的根結(jié)點elseif(keydata)p-lchild=s;/插入s為左孩子elsep-rchild=s;/插入s為右孩子returnTRUE;)elsereturnFALSE

10、;)刪除：/若二叉排序樹T中存在關(guān)鍵字等于key的數(shù)據(jù)元素時，則刪除該元素結(jié)點/并返回TRUE否則返回FALSEStatusDeleteBST(BiTree*T,intkey)if(!*T)/不存在關(guān)鍵字等于key的數(shù)據(jù)元素returnFALSE;elseif(key=(*T)-data)/找到關(guān)鍵字等于key的數(shù)據(jù)元素returnDelete(T);elseif(keydata)returnDeleteBST(&(*T)-lchild,key);elsereturnDeleteBST(&(*T)-rchild,key);)平衡二叉樹（AVL樹）：或是一棵空樹或是具有以下性質(zhì)的

11、二叉樹：他的左子樹和右子樹都是平衡二叉樹，且左子樹和右子樹的深度之差的絕對值不超過1。查找過程：性能分析：時間復(fù)雜度：O（logn）B刷：B-樹是一棵多路查找樹（并不一定是二叉的），一棵m階的B-樹，或為空樹，或為滿足以下特性：1）樹中每個節(jié)點至多有m棵子樹；2）若根節(jié)點不是葉子節(jié)點，則至少有兩顆子樹（2,m）;3）除根之外的所有非終端節(jié)點至少有m/2棵子樹（m/2,m）;意圖：在于保證B-樹中節(jié)點空間的利用率不低于某個下限，改為2m/3則是不行的，應(yīng)為當(dāng)某節(jié)點應(yīng)插入關(guān)鍵字而使其中關(guān)鍵字?jǐn)?shù)目為m時，無法分裂成兩個子樹個數(shù)均大于2m/3的節(jié)點；改為m/3是可行的，但他的節(jié)點空間利用率較低，不過分

12、裂不如b-樹那樣頻繁。4）所有非終端節(jié)點中包含下列信息數(shù)據(jù)（n,A0,K1,A1,K2,A2,K3.Kn.An）淇中Ki為關(guān)鍵字，且Ki35,則若存在必在指針A1所指的子樹內(nèi)，順指針找到*c節(jié)點；2）該節(jié)點有兩個關(guān)鍵字，而4347rchild=NULL)右子樹為空，重接左子樹q=*p;*p=(*p)-lchild;free(q);else(*p)-lchild=NULL)/左子樹為空，重接右子樹q=*p;*p=(*p)-rchild;free(q);elseq=*p;s=(*p)-lchild;while(s-rchild)轉(zhuǎn)左，然后向右到盡頭，找到待刪結(jié)點前驅(qū)q=s;/q刪除結(jié)點的前驅(qū)s=s

13、-rchild;/刪除結(jié)點(*p)-data=s-data;/s指向被刪除結(jié)點的前驅(qū)if(q!=*p)q-rchild=s-lchild;/重接q右子樹elseq-lchild=s-rchild;/重接q左子樹free(s);)returnTRUE;)B+樹:一棵m階的B+樹和m階B-W的差異在于：(1)有n棵子樹的節(jié)點中含有n個關(guān)鍵字(一個節(jié)點中有幾顆子樹就有幾個關(guān)鍵字，B-樹是n-1個兀素)。(2)所有的葉子節(jié)點中包含了全部關(guān)鍵字的信息及指向含這些關(guān)鍵字記錄的指針這兩部分內(nèi)容，且葉子節(jié)點本身依關(guān)鍵字的大小自小而大順序鏈接。(3)所有的非終端節(jié)點可以看成是索引部分，節(jié)點中僅含有其子樹(根節(jié)點

14、)中的最大(或最小)關(guān)鍵字。通常在B+樹有兩個頭指針，一個指向根節(jié)點，另一個指向關(guān)鍵字最小的葉子結(jié)點。因此，可以對b+樹進行兩種查找運算：（1）從最小關(guān)鍵字其順序查找。（2）從根節(jié)點開始，進行隨機查找。優(yōu)點：1、IO次數(shù)更少；2、查詢范圍簡單；3、查詢性能穩(wěn)定3）掌握哈希表的基本概念、哈希函數(shù)構(gòu)造方法、哈希沖突解決方法和哈希查找過程哈希表的基本概念：哈希表也稱散列表，根據(jù)設(shè)定的哈希函數(shù)H（key）和處理沖突的方法將一組關(guān)鍵字映像到一個有限的連續(xù)的地址集上，并以關(guān)鍵字在地址集中的“像”作為記錄在表中的存儲位置，這種表稱為哈希表，這一映像過程稱為哈希造表或散列，所得存儲位置稱為哈希地址或散列地址。

15、（是一種根據(jù)關(guān)鍵字值（key-value）而進行訪問的數(shù)據(jù)結(jié)構(gòu)）。他是通過把關(guān)鍵字映射到數(shù)組的下標(biāo)來加快查找速度。哈希函數(shù)構(gòu)造方法：好的哈希函數(shù)：使關(guān)鍵字經(jīng)過哈希函數(shù)得到一個“隨機的地址”，以便使一組關(guān)鍵字的哈希地址均勻分布在整個地址區(qū)間中，從而減少沖突。常用的構(gòu)造哈希函數(shù)：1、直接定址法：取關(guān)鍵字或者關(guān)鍵字的某個線性函數(shù)值為哈希地址。H（key）=key或H（key）a*key+b2、數(shù)字分析法：假設(shè)關(guān)鍵字是以R為基的數(shù)，并且哈希表中可能出現(xiàn)的關(guān)鍵字都是事先知道的。則可取關(guān)鍵字的若干數(shù)位組成哈希地址。3、平方取中法：取關(guān)鍵字平方后的中間幾位為哈希地址。適用場景：通常在選定哈希函數(shù)時不一定能知

16、道關(guān)鍵字的全部情況，選其中幾位也不合適，而一個數(shù)的平方后的中間幾位數(shù)和數(shù)的每一位都相關(guān)，由此使隨機分布得到的哈希地址也是隨機的，取的位數(shù)有表長決定。例：A關(guān)鍵字：0100（關(guān)鍵字）A2:0010000哈希地址：010（取中間三位）4、折疊法：將關(guān)鍵字分割成位數(shù)相同的幾部分(最后一部分的位數(shù)可以不同)，然后取這幾部分的疊加作為哈希地址。適用場景：關(guān)鍵字位數(shù)很多，而且關(guān)鍵字中每一位上數(shù)字分布均勻時。5、除留余數(shù)法：取關(guān)鍵字被某個不大于哈希表表長m的數(shù)p除后所得余數(shù)為哈希地址。這是最簡單也是最常用的構(gòu)造函數(shù)的方法，不僅可以對關(guān)鍵字直接取模，也可在折疊、平方取中等運算之后取模。6、隨機數(shù)法：選擇一個隨

17、機函數(shù)，取關(guān)鍵字的隨機函數(shù)值為他的哈希地址，即H(key)=random(key)使用場景：當(dāng)關(guān)鍵字長度不等時叫恰當(dāng)。處理哈希沖突：沖突：對不同的關(guān)鍵字可能得到同一哈希地址。一般情況下，沖突只可能的減少，而不能完全避免。因為哈希函數(shù)是從關(guān)鍵字集合到地址集合的映像。同義詞：具有相同函數(shù)值的關(guān)鍵字對該哈希函數(shù)來說稱作同義詞解決處理沖突的方法1、開放定址法：Hi=(H(key)+di)MODmi=1,2,3,4,5.k(k=m-1)H(key)為哈希函數(shù)；m為哈希表長；di為增量序列。Di通常有三種取法：(1)di=1,2,3,4.m-1,稱為線性探測再散列；(2)Di=1A2,-1A2,2A2,-2A2.+-kA2(k=m/2)稱為二次探測再散列；(3)口1=偽隨機數(shù)序列，稱為隨機探測再散列。列如：2、再哈希法：Hi=RHi(key)i=1,2,3,4,5.kRHi均是不同的哈希函數(shù)，即在同義詞產(chǎn)生地址沖突時計算另一個哈希函數(shù)地址，直到?jīng)_突不再發(fā)生。這種方法不易產(chǎn)生“凝聚”，但增加了計算的時間。3、鏈地址法：將所有關(guān)鍵字為同義詞的記錄存儲在同一線性鏈表中。假設(shè)某哈希函數(shù)產(chǎn)生哈