1、數據結構之查找1)了解查找表和平均查找長度的定義查找表：由一類同一類型的數據元素(或記錄)構成的集合。由于“集合”中的數據元素之間存在著完全松散的關系，因此查詢表是一種非常靈便的數據結構。平均查找長度：注明：n是查找表的元素個數，Pi是查找第i個元素的概率，通常假設每個查找元素概率相同即 nCi=1i1(Pi=1/n),Ci是查找第i個元素需要比較的次數(輪到與這個元素比較時已經比較了幾次)如：等概率的順序查找的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)掌握順序查找、折半查找和分塊查找算法設計和算法分析順序查找：/*順序查找，a為數組，n為要查找的數組長度，key為要查找的關鍵字*/intSequential_Search(int*a,intn,intkey)inti;for(i=1;in;i+)if(ai=key)returni;return0;公式：ASL成功=nPiCiASL=nPiCi=1/n*nCi因為每次循環都需要對是否越界，即是否小于n做判斷。事實上，還可以有更好一

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

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

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

6、定義塊的結構2.(3.intkey;/塊的關鍵字4.intstart;/塊的起始值5.intend;/塊的結束值6.index_table4;/定義結構體數組1.intblock_search(intkey,inta)/自定義實現分塊查找2.(3.inti,j;4.i=1;5.while(iindex_tablei.key)/確定在哪個塊中6.i+;7.if(i3)/大于分得的塊數，則返回08.return0;9.j=indextablei.start;/j等于塊范圍的起始值10.while(jindextablei.end)/如果大于塊范圍的結束值，則說明沒有要查找的數，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)掌握二叉排序樹的算法設計，了解平衡二叉樹、B-和B+樹的定義和查找過程二叉排序樹(二叉查找樹)：(1)若他的左子樹不空，則左子樹上所有節點的值均小于它的根節點的值；(2)若他的右子樹不空，則右子樹上的所有節點均大于他的根節點的值(3)他的左右數也分別為二叉排序樹算法設計：/二叉樹二叉鏈表結點的結構定義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為新的根結點elseif(keydata)p-lchild=s;/插入s為左孩子elsep-rchild=s;/插入s為右孩子returnTRUE;)elsereturnFALSE

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

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

12、裂不如b-樹那樣頻繁。4）所有非終端節點中包含下列信息數據（n,A0,K1,A1,K2,A2,K3.Kn.An）淇中Ki為關鍵字，且Ki35,則若存在必在指針A1所指的子樹內，順指針找到*c節點；2）該節點有兩個關鍵字，而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)轉左，然后向右到盡頭，找到待刪結點前驅q=s;/q刪除結點的前驅s=s

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

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

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

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

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