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

7.1查找的基本概念第7章查找查找又稱為檢索，其功能是從大量的數(shù)據(jù)元素中找出某個(gè)特定的滿足給定條件的記錄或數(shù)據(jù)元素。若找到滿足給定條件的記錄或數(shù)據(jù)元素，則稱查找是成功的，此時(shí)查找的結(jié)果為給出整個(gè)記錄的信息，或指示該記錄在查找表中位置的指針；相反，若未找到滿足給定條件的記錄或數(shù)據(jù)元素，則稱查找不成功，此時(shí)，查找的結(jié)果可給出一個(gè)“空”記錄或“空”指針。查找的目的一般有如下四種：（1）查找某指定的數(shù)據(jù)元素在查找表中是否存在；（2）檢索某個(gè)特定的數(shù)據(jù)元素的各種屬性；（3）在查找表的合理位置上插入一個(gè)數(shù)據(jù)元素；（4）從查找表中刪除某個(gè)數(shù)據(jù)元素。7.1查找的基本概念第7章查找關(guān)鍵字標(biāo)識(shí)數(shù)據(jù)元素（或記錄）中某個(gè)數(shù)據(jù)項(xiàng)的值，用它可以標(biāo)識(shí)一個(gè)數(shù)據(jù)元素（或記錄）。若此關(guān)鍵字可以唯一標(biāo)識(shí)一個(gè)記錄，則稱此關(guān)鍵字為主關(guān)鍵字（不同的記錄，其主關(guān)鍵字均不同）。反之，把用以識(shí)別若干個(gè)記錄的關(guān)鍵字稱為次關(guān)鍵字。當(dāng)數(shù)據(jù)元素只有一個(gè)數(shù)據(jù)項(xiàng)時(shí)，其關(guān)鍵字即為該數(shù)據(jù)元素的值。利用關(guān)鍵字的概念，查找運(yùn)算的功能可確切地表述如下：根據(jù)給定的某個(gè)關(guān)鍵字值key，在某種數(shù)據(jù)結(jié)構(gòu)中尋找一個(gè)其鍵值等于key的數(shù)據(jù)元素。若找到一個(gè)這樣的數(shù)據(jù)元素，則稱查找成功；否則，稱查找不成功。7.1查找的基本概念第7章查找靜態(tài)查找（staticsearch）若對(duì)查找表只做前兩種操作（即，肯定不會(huì)改變?cè)檎冶淼膬?nèi)容），則稱此查找為靜態(tài)查找。動(dòng)態(tài)查找（dynamicsearch）若在查找過程中同時(shí)插入查找表中不存在的數(shù)據(jù)元素，或者從查找表中刪除已存在的某個(gè)數(shù)據(jù)元素，則稱此查找為動(dòng)態(tài)查找。平均查找長度（averagesearchlength,ASL）為確定所查找的數(shù)據(jù)元素在查找表中的位置而需和給定關(guān)鍵字進(jìn)行比較的次數(shù)的平均值。ASL是衡量一個(gè)查找算法性能好壞的依據(jù),因?yàn)椴檎业倪^程實(shí)際上是“將查找表中各數(shù)據(jù)元素的關(guān)鍵字與給定的關(guān)鍵字進(jìn)行比較的過程”，所以比較次數(shù)越少，則查找所需的時(shí)間就越短，效率就越高。7.2靜態(tài)查找表第7章查找7.2.1順序查找順序查找是一種最簡單也是效率比較低下的查找算法。查找的基本思想是將每個(gè)結(jié)點(diǎn)的關(guān)鍵字與給定的待查的關(guān)鍵字值key依次進(jìn)行比較，若當(dāng)前掃描到的結(jié)點(diǎn)關(guān)鍵字值與key相等，則查找成功，返回該數(shù)據(jù)元素的存儲(chǔ)位置；反之，若掃描結(jié)束后，仍未找到關(guān)鍵字等于key的結(jié)點(diǎn)，則查找失敗，返回查找失敗標(biāo)志。順序查找法既可以采用順序存儲(chǔ)結(jié)構(gòu)，也可以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。//靜態(tài)查找表的順序存儲(chǔ)表示#definemaxsize100/*定義最大存儲(chǔ)容量*/typedefstruct{datatypedata[maxsize];intlength;}seqtable;/*靜態(tài)查找表的鏈?zhǔn)酱鎯?chǔ)表示*/typedefstructnode{datatypedata;structnode*next;}linktable;7.2靜態(tài)查找表第7章查找7.2.2折半查找折半查找也稱為“二分查找”,其查找效率較高，但要求待查找的數(shù)據(jù)元素采用順序存儲(chǔ)結(jié)構(gòu)，而且查找表按關(guān)鍵字有序(已經(jīng)按關(guān)鍵字排好序)。采用折半查找算法在有序表（假設(shè)為升序）中查找結(jié)點(diǎn)時(shí)，首先找到表的中間結(jié)點(diǎn)，將其關(guān)鍵字值與給定的要找的值key進(jìn)行比較，若相等，則查找成功；若當(dāng)前結(jié)點(diǎn)的關(guān)鍵字值大于要找的值key，則繼續(xù)在表的前半部分進(jìn)行折半查找，否則繼續(xù)在表的后半部分進(jìn)行折半查找。7.2靜態(tài)查找表第7章查找7.2.3分塊查找分塊查找是一種性能介于順序查找和二分查找之間的查找方法，但它要求先對(duì)查找表建立一個(gè)索引表，再進(jìn)行分塊查找。索引表建立方法是先對(duì)查找表進(jìn)行分塊，要求“分塊有序”，所謂“分塊有序”是指塊內(nèi)關(guān)鍵字不一定有序，但塊間有序，即后一塊子表中所有數(shù)據(jù)元素的關(guān)鍵字值均大于前一塊中最大的關(guān)鍵字值。然后，抽取各塊中的最大關(guān)鍵字及其起始位置構(gòu)成一個(gè)索引表，如圖7-3所示。分塊查找方法為分兩步進(jìn)行，先查找索引表，因其有序，故可采用二分查找，以確定待查記錄在哪一塊，然后，在已確定的塊中再進(jìn)行順序查找。7.3動(dòng)態(tài)查找表第7章查找7.3.1二叉排序樹1．二叉排序樹定義二叉排序樹（BinarySortTree）或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹：(1)若左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值；若右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值。(2)左右子樹也都是二叉排序樹。從二叉排序樹的定義可得出二叉排序樹的一個(gè)重要性質(zhì)：按中序遍歷該樹所得到的中序序列是一個(gè)遞增有序序列。7.3動(dòng)態(tài)查找表第7章查找2．二叉排序樹的查找過程在二叉排序樹中查找關(guān)鍵字值為key的數(shù)據(jù)元素的基本思想是用給定值key與根結(jié)點(diǎn)的關(guān)鍵字值比較，如果key小于根結(jié)點(diǎn)的值，則要找的結(jié)點(diǎn)只可能在左子樹中，所以繼續(xù)在左子樹中查找，否則將繼續(xù)在右子樹中查找，依此方法，查找下去，直至查找成功或查找失敗為止。二叉排序樹的查找過程描述如下：（1）若二叉排序樹為空樹，則查找失??；（2）若二叉排序樹非空，將給定值key與根結(jié)點(diǎn)關(guān)鍵字值比較，若相等，查找成功，結(jié)束查找過程；（3）否則，當(dāng)結(jié)定值key小于根結(jié)點(diǎn)關(guān)鍵字值時(shí)，則繼續(xù)在根結(jié)點(diǎn)的左子樹中查找；（4）否則，當(dāng)給定值key大于根結(jié)點(diǎn)關(guān)鍵字值時(shí)，則繼續(xù)在根結(jié)點(diǎn)的右子樹中查找。7.3動(dòng)態(tài)查找表第7章查找3．二叉排序樹的插入二叉排序樹是一種動(dòng)態(tài)樹表，樹的結(jié)構(gòu)通常不是一成不變的，在一棵二叉排序樹中插入一個(gè)結(jié)點(diǎn)時(shí)，首先要在二叉排序樹中進(jìn)行查找，若查找成功，則不用插入；查找不成功時(shí)，則插入，新插入結(jié)點(diǎn)一定是二叉排序樹的葉了結(jié)點(diǎn)。插入可以用一個(gè)遞歸過程實(shí)現(xiàn)，即：若二叉排序樹為空，則新結(jié)點(diǎn)作為二叉排序樹的根結(jié)點(diǎn)；否則，若給定結(jié)點(diǎn)的關(guān)鍵字值小于根結(jié)點(diǎn)關(guān)鍵字值，則插入在左子樹上；若給定結(jié)點(diǎn)的關(guān)鍵字值大于根結(jié)點(diǎn)的值，則插入在右子樹上。4.二叉排序樹的建立利用二叉排序樹的插入算法，可以很容易地實(shí)現(xiàn)創(chuàng)建二叉排序樹的操作，其基本思想是：由一棵空二叉樹開始，經(jīng)過一系列的查找插入操作生成一棵二叉排序樹。7.3動(dòng)態(tài)查找表第7章查找5．二叉排序樹刪除操作從二叉排序樹中刪除一個(gè)結(jié)之后，使得其仍能保持二叉排序樹的特性不變，即刪除一個(gè)結(jié)點(diǎn)后還是一棵二叉排序樹。下面分3種情況討論一下，如何確保從二叉排序樹中刪除一個(gè)結(jié)點(diǎn)后，不會(huì)影響二叉排序樹的性質(zhì)。設(shè)待刪結(jié)點(diǎn)為*p(p為指向待刪結(jié)點(diǎn)的指針)，其雙親結(jié)點(diǎn)為*f，且不失一般性，可設(shè)*p是*f的左孩子結(jié)點(diǎn)（右孩子結(jié)點(diǎn)的情況類似）。7.3動(dòng)態(tài)查找表第7章查找(1)若*p結(jié)點(diǎn)為葉結(jié)點(diǎn)，由于刪去葉子結(jié)點(diǎn)后不影響整棵樹的特性，所以，只需將被刪結(jié)點(diǎn)的雙親結(jié)點(diǎn)相應(yīng)指針域改為空指針。如圖7-6所示。7.3動(dòng)態(tài)查找表第7章查找(2)若*p結(jié)點(diǎn)只有右子樹PR或只有左子樹PL，此時(shí)，只要令PL或PR直接成為其雙親結(jié)點(diǎn)*f的左子樹即可，顯然，作此修改也不破壞二叉排序樹的特性。如圖7-7所示。7.3動(dòng)態(tài)查找表第7章查找(3)*p結(jié)點(diǎn)既有左子樹PL，又有右子樹PR，可按中序遍歷保持有序進(jìn)行調(diào)整。如圖7-8所示，刪除*p結(jié)點(diǎn)前，中序遍歷序列為：CL，C，…，QL，Q，SL,S,*P,PR,*f，…；則刪除結(jié)點(diǎn)*P后，為保持其它元素之間的相對(duì)位置不變，則中序序列為：CL，C，…，QL，Q，SL,S,PR,*f，…。以有兩種實(shí)現(xiàn)方法：其一是令*P的直接前驅(qū)（或直接后繼）替代*P，然后再從二叉排序樹中刪去它的直接前驅(qū)（或直接后繼），如圖7-8(a)所示。其二是令*P的左子樹為*f的左子樹，而*P的右子樹為S的右子樹，如圖7-8(b)所示。7.3動(dòng)態(tài)查找表第7章查找7.3動(dòng)態(tài)查找表第7章查找6．二叉排序樹查找性能分析在二叉排序樹上查找其關(guān)鍵字等于給定值的結(jié)點(diǎn)的過程，恰是走了一條從根結(jié)點(diǎn)到該結(jié)點(diǎn)的路徑的過程，和給定值比較的關(guān)鍵字個(gè)數(shù)等于路徑長度加1(或結(jié)點(diǎn)所在層次數(shù))，因此和折半查找類似，與給定值比較的關(guān)鍵字個(gè)數(shù)不超過樹的深度。但含有n個(gè)結(jié)點(diǎn)的判定樹是唯一的，而含有n個(gè)結(jié)點(diǎn)的二叉排序樹卻不唯一。例如，圖7-9（a）和圖7-9（b）所示的是結(jié)點(diǎn)數(shù)為6的兩棵二叉排序樹，圖7-9（a）中樹的深度為3，而圖7-9（b）中樹的深度為6。7.3動(dòng)態(tài)查找表第7章查找7.3.2平衡二叉樹1．平衡二叉樹定義平衡二叉樹又稱AVL樹，它或者是—棵空樹，或者是具有下列性質(zhì)的二叉排序樹：它的左子樹和右子樹都是平衡二叉樹，且左子樹和右子樹高度差的絕對(duì)值不超過1。圖7-10給出了兩棵二叉排序樹，每個(gè)結(jié)點(diǎn)旁邊所注數(shù)字是以該結(jié)點(diǎn)為根的二叉樹中左子樹與右子樹高度之差，稱這個(gè)數(shù)字為結(jié)點(diǎn)的平衡因子。由平衡二叉樹的定義可知，所有結(jié)點(diǎn)的平衡因子只能取-1，0，1三個(gè)值之一。若二叉排序樹中存在這樣的結(jié)點(diǎn)，其平衡因子的絕對(duì)值大于l，這棵樹就不是平衡二叉樹。如圖7-10（a）所示的二叉排序樹不是平衡二叉樹。7.3動(dòng)態(tài)查找表第7章查找1．平衡二叉樹定義7.3動(dòng)態(tài)查找表第7章查找2．二叉排序樹的平衡化在平衡二叉樹上插入或刪除結(jié)點(diǎn)后，可能使二叉樹失去平衡，因此，需要對(duì)失去平衡的二叉樹進(jìn)行平衡化調(diào)整。設(shè)A結(jié)點(diǎn)為失去平衡的最小子樹根結(jié)點(diǎn)，對(duì)該子樹進(jìn)行平衡化調(diào)整歸納起來有以下四種情況。（1）左單旋轉(zhuǎn)（RR型）這種失衡是因?yàn)樵谑Ш饨Y(jié)點(diǎn)的右孩子的右子樹上插入結(jié)點(diǎn)造成的。如圖7-11（a）為插入前的子樹。其中A的左子樹為AL，A的右孩子結(jié)點(diǎn)為B，BL、BR分別為結(jié)點(diǎn)B的左右子樹，AL、BL、BR三棵子樹的高度均為h。則圖7-10（a）所示的二叉樹是平衡二叉樹。7.3動(dòng)態(tài)查找表第7章查找（1）左單旋轉(zhuǎn)（RR型）7.3動(dòng)態(tài)查找表第7章查找（2）右單旋轉(zhuǎn)(LL型)這種失衡是因?yàn)樵谑Ш饨Y(jié)點(diǎn)的左孩子的左子樹上插入結(jié)點(diǎn)后，導(dǎo)致結(jié)點(diǎn)A的平衡因子由1變?yōu)?，如圖7-12（a）、（b）所示，此時(shí)應(yīng)進(jìn)行一次順時(shí)針旋轉(zhuǎn)操作，使結(jié)點(diǎn)A成為結(jié)點(diǎn)B的右孩子，如圖7-12（c）所示。7.3動(dòng)態(tài)查找表第7章查找（3）先左后右雙向旋轉(zhuǎn)（LR型）這種失衡是因?yàn)樵谑Ш饨Y(jié)點(diǎn)的左孩子的右子樹上插入結(jié)點(diǎn)造成的。如圖7-13所示，插入前，根結(jié)點(diǎn)A的平衡因子為1，將結(jié)點(diǎn)x插入到B的右子樹上。并使結(jié)點(diǎn)B的右子樹高度增1，從而使結(jié)點(diǎn)A的平衡因子變?yōu)?，導(dǎo)致以結(jié)點(diǎn)A為根的子樹平衡被破壞，如圖7-14（a）、圖7-15（a）所示。7.3動(dòng)態(tài)查找表第7章查找（4）先右后左雙向旋轉(zhuǎn)（RL型）這種失衡是因?yàn)樵谑Ш饨Y(jié)點(diǎn)的右孩子的左子樹上插入結(jié)點(diǎn)造成的。導(dǎo)致結(jié)點(diǎn)A的平衡因子由-1變?yōu)?2，則同樣需兩次旋轉(zhuǎn)，即先右后左雙向旋轉(zhuǎn)，調(diào)整過程與LR對(duì)稱，下面只給出雙向旋轉(zhuǎn)RL型I，如圖7-16所示。雙向旋轉(zhuǎn)RL型II，請(qǐng)讀者自行完成。7.3動(dòng)態(tài)查找表第7章查找（4）先右后左雙向旋轉(zhuǎn)（RL型）7.3動(dòng)態(tài)查找表第7章查找3.平衡二叉樹的插入在平衡二叉樹T上插入一個(gè)關(guān)鍵字為x的數(shù)據(jù)元素，遞歸算法的基本思想可描述如下：(1)若T為空樹，則插入的數(shù)據(jù)元素x為T的根結(jié)點(diǎn)，樹的深度增1；(2)若x和T的根結(jié)點(diǎn)關(guān)鍵字相等，則不進(jìn)行插入；(3)若x小于T的根結(jié)點(diǎn)關(guān)鍵字值，而且在T的左子樹中不存在與x有相同關(guān)鍵字值的結(jié)點(diǎn)，則將新元素插入在T的左子樹上，并且插入之后的左子樹深度增加1時(shí)，分別就下列情況進(jìn)行處理。7.3動(dòng)態(tài)查找表第7章查找4.平衡二叉樹查找性能分析在平衡二叉樹上進(jìn)行查找的過程和二叉排序樹類似，查找時(shí)和給定值進(jìn)行比較的關(guān)鍵字?jǐn)?shù)不超過樹的深度。下面我們討論含有n個(gè)關(guān)鍵字的平衡二叉樹的最大深度。假設(shè)以Nh表示深度為h的平衡二叉樹中含有的最少結(jié)點(diǎn)數(shù)。顯然，N0=0，N1=1，N2=2，并且Nh=Nh-1+Nh-2+1。含有n個(gè)結(jié)點(diǎn)的平衡二叉樹的最大深度為。利用歸納法可以證明：當(dāng)h≥0，時(shí)間復(fù)雜度為O(log2n)。7.4散列表第7章查找7.4.1散列表的概念1．散列表設(shè)所有可能出現(xiàn)的關(guān)鍵字集合記為U(簡稱全集)。實(shí)際發(fā)生(即實(shí)際存儲(chǔ))的關(guān)鍵字集合記為K(|K|比|U|小得多)。散列方法是使用函數(shù)h將U映射到表T[0..m-1]的下標(biāo)上(m=O(|U|))。這樣以U中關(guān)鍵字為自變量，以h為函數(shù)的運(yùn)算結(jié)果就是相應(yīng)結(jié)點(diǎn)的存儲(chǔ)地址。從而達(dá)到在O(1)時(shí)間內(nèi)就可完成查找。7.4散列表第7章查找2．散列表的沖突現(xiàn)象(1)沖突對(duì)于不同的關(guān)鍵字可能得到同一哈希地址，即key11key2，但h(key1)=h(key2)，該現(xiàn)象稱為沖突(Collision)或碰撞。發(fā)生沖突的兩個(gè)關(guān)鍵字稱為該散列函數(shù)的同義詞(Synonym)。7.4散列表第7章查找7.4.2散列函數(shù)的構(gòu)造方法1．散列函數(shù)的選擇標(biāo)準(zhǔn)散列函數(shù)的選擇有兩條標(biāo)準(zhǔn)：簡單和均勻。簡單是指散列函數(shù)的計(jì)算簡單快速；均勻是指對(duì)于關(guān)鍵字集合中的任一關(guān)鍵字，散列函數(shù)能以等概率將其映射到散列表空間的任何一個(gè)位置上。也就是說，散列函數(shù)能將子集K隨機(jī)均勻地分布在表的地址集{0，1，…，m-1}上，以使沖突最小化。7.4散列表第7章查找2．常用散列函數(shù)為簡單起見，假定關(guān)鍵字是定義在自然數(shù)集合上，目前比較常用的散列函數(shù)有以下幾種：

(1)平方取中法先通過求關(guān)鍵字的平方值擴(kuò)大相近數(shù)的差別，然后根據(jù)表長度取中間的幾位數(shù)作為散列函數(shù)值。又因?yàn)橐粋€(gè)乘積的中間幾位數(shù)和乘數(shù)的每一位都相關(guān)，所以由此產(chǎn)生的散列地址較為均勻。7.4散列表第7章查找(2)除留余數(shù)法該方法是最為簡單常用的一種方法。它是以表長m來除關(guān)鍵字，取其余數(shù)作為散列地址。其散列函數(shù)的形式為：h(key)=key%m。其中，key是關(guān)鍵字。m的選取十分重要，如果m選擇不當(dāng)，在某些情況下會(huì)造成嚴(yán)重沖突。例如，若m=2k，則h(key)的值僅依賴于最后k個(gè)比特。如果key是十進(jìn)制數(shù)，則m應(yīng)避免取10的冪次。多數(shù)情況下，選取一個(gè)不超過m的素?cái)?shù)p，令散列函數(shù)為h(key)=key%p，會(huì)收到較好的效果。7.4散列表第7章查找(3)相乘取整法該方法包括兩個(gè)步驟：首先用關(guān)鍵字key乘上某個(gè)常數(shù)A(0<A<1)，并抽取出key×A的小數(shù)部分，然后用m乘以該小數(shù)后取整。即：

該方法最大的優(yōu)點(diǎn)是選取m不再像除留余數(shù)法那樣關(guān)鍵。雖然該方法對(duì)任何A的值都適用，但對(duì)某些值效果會(huì)更好。Knuth建議：7.4散列表第7章查找7.4.3處理沖突的方法散列表中的沖突現(xiàn)象是難以避免的，因此，尋求較好的解決沖突的方法是一個(gè)重要的問題。通常有兩類處理沖突的方法：開放定址(OpenAddressing)法和拉鏈(Chaining)法。前者是將所有結(jié)點(diǎn)均存放在散列表T[0..m-1]中；后者是將互為同義詞的結(jié)點(diǎn)鏈成一個(gè)單鏈表，而將此鏈表的頭指針放在散列表T[0..m-1]中。7.4散列表第7章查找1.開放定址法(1)開放地址法解決沖突的方法用開放定址法解決沖突的方法是：當(dāng)沖突發(fā)生時(shí)，使用某種探查(亦稱探測)技術(shù)在散列表中形成一個(gè)探查(測)序列。沿此序列逐個(gè)單元地查找，直到找到給定的關(guān)鍵字，或者碰到一個(gè)開放的地址(即該地址單元為空)為止(若要插入，在探查到開放的地址時(shí)，則可將待插入的新結(jié)點(diǎn)存入到該地址單元)。查找時(shí)探查到開放的地址則表明表中無待查的關(guān)鍵字，即查找失敗。7.4散列表第7章查找(2)開放地址法的一般形式開放定址法的一般形式為：hi=(h(key)+di)%m1≤i≤m-1其中：①h(key)為散列函數(shù)，di為增量序列，m為表長；②h(key)是初始的探查位置，后續(xù)的探查位置依次是hl，h2，…，hm-1，即h(key)，hl，h2，…，hm-1形成了一個(gè)探查序列；③若令開放地址一般形式的i從0開始，并令d0=0，則h0=h(key)，hi=(h(key)+di)%m，1≤i≤m-1；探查序列可簡記為hi(0≤i≤m-1)。7.4散列表第7章查找(3)開放地址法對(duì)裝填因子的要求開放定址法要求散列表的裝填因子α≤1，實(shí)用中取α為0.5到0.9之間的某個(gè)值為宜。(4)形成探測序列的方法按照形成探查序列方法的不同，可將開放定址法分為線性探查法、二次探查法、雙重散列法等。①線性探查法(LinearProbing)該方法的基本思想是：將散列表T[0..m-1]看成是一個(gè)循環(huán)向量，若初始探查的地址為d(即h(key)=d)，則最長的探查序列為：d，d+l，d+2，…，m-1，0，1，…，d-1。即探查時(shí)從地址d開始，首先探查T[d]，然后依次探查T[d+1]，…，直到T[m-1]，此后又循環(huán)到T[0]，T[1]，…，直到探查到T[d-1]為止。7.4散列表第7章查找2．拉鏈法(1)拉鏈法解決沖突的方法拉鏈法解決沖突的方法是：將所有關(guān)鍵字為同義詞的結(jié)點(diǎn)鏈接在同一個(gè)單鏈表中。若選定的散列表長度為m，則可將散列表定義為一個(gè)由m個(gè)頭指針組成的指針數(shù)組T[0..m-1]。凡是散列地址為i的結(jié)點(diǎn)，均插入到以T[i]為頭指針的單鏈表中。T中各分量的初值均應(yīng)為空指針。在拉鏈法中，裝填因子α可以大于1，但一般均取α≤1。7.4散列表第7章查找(2)拉鏈法的特點(diǎn)與開放定址法相比，拉鏈法有如下幾個(gè)優(yōu)點(diǎn)：①拉鏈法處理沖突簡單，且無堆積現(xiàn)象，即非同義詞決不會(huì)發(fā)生沖突，因此平均查找長度較短；②由于拉鏈法中各鏈表上的結(jié)點(diǎn)空間是動(dòng)態(tài)申請(qǐng)的，故它更適合于造表前無法確定表長的情況；③開放定址法為減少?zèng)_突，要求裝填因子α較小，故當(dāng)結(jié)點(diǎn)規(guī)模較大時(shí)會(huì)浪費(fèi)很多空間。而拉鏈法中可取α≥1，且結(jié)點(diǎn)較大時(shí)，拉鏈法中增加的指針域可忽略不計(jì)，因此節(jié)省空間；④在用拉鏈法構(gòu)造的散列表中，刪除結(jié)點(diǎn)的操作易于實(shí)現(xiàn)。只要簡單地刪去鏈表上相應(yīng)的結(jié)點(diǎn)即可。7.4散列表第7章查找7.4.4散列表的查找及分析1．散列表數(shù)據(jù)類型描述#defineNIL-1/*空結(jié)點(diǎn)標(biāo)記依賴于關(guān)鍵字類型，本節(jié)假定關(guān)鍵字均為非負(fù)整數(shù)*/#defineM13/*表長度依賴于應(yīng)用，但一般應(yīng)確定M為一素?cái)?shù)*/typedefin