第8章查找8.1查找的基本概念1.查找:也稱為檢索。如:查找某人的地址、電話號碼等，都屬于查找范疇。⑴查找是按關鍵字進行的:①關鍵字(key):是數據元素(或記錄)中某個數據項的值，用它可以標識(或識別)一個數據元素。例如:描述一個考生的信息，可以包含：考號、姓名、性別、年齡、家庭住址、電話號碼、成績等關鍵字。②有些關鍵字不能唯一標識一個數據元素，而有的關鍵字可以唯一標識一個數據元素。如:考生信息中，姓名不能唯一標識一個數據元素(因有同名同姓的人)，而考號可以唯一標識一個數據元素(每個考生考號是唯一的，不能相同)。③能唯一標識一個數據元素的關鍵字稱為主關鍵字，而其它關鍵字稱為輔助關鍵字或從關鍵字。⑵查找就是根據給定的值，在一個表中查找出其關鍵字等于給定值的數據元素:①若表中有這樣的元素，則稱查找是成功的:

查找的信息為給定整個數據元素的輸出或指出該元素在表中的位置；②若表中不存在這樣的記錄，則稱查找是不成功的，或稱查找失敗，并可給出相應的提示。2.采用何種查找方法，首先取決于使用哪種數據結構來表示

“表”:即表中結點是按何種方式組織的。3.為了提高查找速度，經常使用某些特殊的數據結構來組織表。4.研究各種查找算法時，首先必須弄清這些算法所要求的數據結構，特別是存儲結構。5.查找有內查找和外查找之分:⑴若整個查找過程全部在內存進行，則稱這樣的查找為內查找⑵若在查找過程中還需要訪問外存，則稱之為外查找。我們僅介紹內查找。6.將找到給定值與關鍵字的比較次數的平均值來作為衡量一個查找算法好壞的標準:

⑴對于一個含有n個元素的表，查找成功時的平均查找長度可表示為ASL=

①Ｐi為查找第i個元素的概率，且=1。

②一般情形下我們認為查找每個元素的概率相等，

③Ｃi為查找第i個元素所用到的比較次數。

8．2線性表的查找8.2.1順序查找1．順序查找的基本思想:⑴從表的一端開始，順序掃描線性表，依次將掃描到的結點關鍵字和待找的值Ｋ相比較:

①若相等，則查找成功，

②若整個表掃描完畢，仍末找到關鍵字等于Ｋ的元素，則查找失敗。⑵順序查找既適用于順序表，也適用于鏈表:

①順序表查找可從前往后掃描，也可從后往前掃描

②采用單鏈表，則只能從前往后掃描。

③另外，順序查找的表中元素可以是無序的。2．順序查找算法實現:constintn=maxn//n為表的最大長度structnode{…elemtypekey;//key為關鍵字};

intseqsearch(nodeR[n+1],elemtypek)//在表Ｒ中查找關鍵字值為Ｋ的元素{R[0].key=k;inti=n;//從表尾開始向前掃描

while(R[i].key!=k)i--;returni;}⑴函數中查找的范圍從Ｒ[n]到Ｒ[１]，⑵Ｒ[０]為監視哨，起兩個作用:

①為了省去判定while循環中下標越界的條件i≥1，從而節省比較時間

②保存要找值的副本，若查找時，遇到它，表示查找不成功。⑶若算法中不設立監視哨R[0]，程序花費的時間將會增加，這時的算法可寫為下面形式。intseqsearch(nodeR[n+1]，elemtypek){inti=n;while(R[i].key!=k)&&(i>=1)i--;returni;}3.順序查找性能分析:⑴假設在每個位置查找的概率相等，即有pi=1/n，由于查找是從后往前掃描，則有每個位置的查找比較次數

Cn=1，Cn-1=2，…，C1=n，于是，查找成功的平均查找ASL===⑵時間復雜度為O(n)。這就是說，查找成功的平均比較次數約為表長的一半。⑶若k值不在表中，則必須進行n+1次比較之后才能確定查找失敗。⑷另處:當n較大時，ASL值較大，查找的效率較低。⑸順序查找的特點:①算法簡單，對表結構無任何要求:

無論是用向量還是用鏈表來存放結點，也無論結點之間是否按關鍵字有序或無序，它都同樣適用。②順序查找的缺點:

查找效率低，當n較大時，不宜采用順序查找，而必須尋求更好的查找方法。8.2.2二分查找1.二分查找的基本思想:⑴二分查找，也稱折半查找，它是一種高效率的查找方法。

①

二分查找有條件限制：要求表必須用向量作存貯結構，且表中元素必須按關鍵字有序(升序或降序均可)。假設表中元素為升序排列。

②二分查找的基本思想是：首先將待查值K與有序表R[1]到R[n]的中點

mid上的關鍵字R[mid].key進行比較:a.若相等，則查找成功；

b.否則，若R[mid].key>k，則在R[1]到R[mid-1]中繼續查找，若有

R[mid].key<k，則在R[mid+1]到R[n]中繼續查找。⑵每通過一次關鍵字的比較，區間的長度就縮小一半，區間的個數就增加一倍，如此不斷進行下去，直到找到關鍵字為K的元素；若當前的查找區間為空(表示查找失敗)。從上述查找思想可知，每進行一次關鍵字比較，區間數目增加一倍，故稱為二分（區間一分為二），而區間長度縮小一半，故也稱為折半（查找的范圍縮小一半）。2．二分查找算法實現intbinsearch(nodeR[n+1],elemtypek){intlow=1,high=n;while(low<=high){intmid=(low+high)/2;//取區間中點

if(R[mid].key==k)returnmid;//查找成功

elseif(R[mid].key>k)

high=mid-1;//在左子區間中查找

elselow=mid+1;//在右子區間中查找

}return0;//查找失敗

}例如，假設給定有序表中關鍵字為8,17,25,44,68,77,98,100,115,125，將查找K=17和K=120的情況描述為圖8-1及圖8-2形式。3.二分查找的性能分析:

⑴用二叉樹來描述二分查找過程:

把當前查找區間的中點作為根結點，左子區間和右子區間分別作為根的左子樹和右子樹

⑵左子區間和右子區間再按類似的方法，由此得到的二叉樹稱為二分查找的判定樹。例如:圖8-1給定的關鍵字序列:8,17,25,44,68,77,98,100,115,125，的判定樹見圖8-3。從圖8-3可知:①查找根結點68，需一次查找②查找17和100，各需二次查找③查找8、25、77、115各需三次查找④查找44、98、125各需四次查找。⑤結論：二叉樹第K層結點的查找次數各為k次(根結點為第1層)，而第k層結點數最多為2k-1個。假設:該二叉樹的深度為h，則二分查找的成功的平均查找長度為（假設每個結點的查找概率相等）：ASL==1/n≤1/n(1+2﹡2+3﹡22+…+h﹡2h-1）①在最壞情形下，上面的不等號將會成立，并根據二叉樹的性質，最大的結點數n=2h-1，h=log2(n+1)

②可以得到平均查找長度:ASL=(n+1)/nlog2(n+1)-1③log2(n+1)-1可以作為二分查找成功時的平均查找長度它的時間復雜度為O(log2n)。4.二分查找的優缺點:

⑴

優點:

比較次數較順序查找少,查找速度快,

執行效率高。

⑵缺點：表的存儲結構只能是順序存儲，不能是鏈式存儲，且表中元素必須是有序的。8.2.3索引查找1.索引查找的思想⑴索引查找(分級查找):

它既是一種查找方法，又是一種存貯方法，稱為索引存貯。例如:在漢語字典中查找某個漢字時:

①若知道某個漢字讀音，則可以先在音節表中查找到對應正文中的頁碼，然后再在正文中所對應的頁中查出待查的漢字②若知道該漢字的字形，但不知道讀音，則可以先在部首表中根據字的部首查找到對應檢字表中的頁碼，再在檢字表中根據字的筆畫找到該漢字所在的頁碼。③整個字典就是索引查找的對象，字典的正文是字典的主要部分，被稱之為主表，而檢字表，部首表和音節表都是為了方便查找主表而建立的索引，所以被稱之為索引表。④在索引查找中:

主表只有一個:包含的是待查找的內容，索引表可以有多個:包含一級索引，二級索引……，所需的級數可根據具體問題而定。如:剛才的利用讀音查找漢字為一級索引，利用字形查找漢字為二級索引（部首表→檢字表→漢字）。我們僅討論一級索引。⑵索引查找是在線性表（主表）的索引存貯結構上進行的，而索引存貯的基本思想是：①首先將一個線性表（主表）按照一定的規則分成若干個邏輯上的子表，并為每個子表分別建立一個索引項，由所有這些索引項得到主表的一個索引表，②可采用順序或鏈接的方法來存儲索引表和各個子表。③索引表中的每個索引項通常包含三個域：一是索引值域:用來存儲標識對應子表的索引值，它相當于記錄的關鍵字，在索引表中由此索引值來唯一標識一個索引項（子表）；二是子表的開始位置:用來存儲對應子表的第一個元素的存儲位置；三是子表的長度:用來存儲對應子表的元素個數。例如，設有一個學校部分教師檔案表如表8-1所示，設編號為主關鍵字，則該表可以用一個線性表L=（a1,a2,a3,a4,a5,a6,a7,a8,a9,a10）來表示，其中ai(1≤i≤n)表示第i位教師的信息（包含有編號，姓名，部門，職稱），而它的索引表可以按部門進行，也可以按職稱進行，按部門的索引表中有4個子表，分別為：計算機系J=（a1,a2,a3,a4）電工系D=(a5,a6,a7)管理系G=(a8,a9)成教部C=(a10)該4個子表示成一個索引表如表8-2所示。

表8-1教師檔案表

編號

姓名

部門

職稱J001趙一計算機系教授J002錢二計算機系講師J003張三計算機系副教授J004李四計算機系助教D001王五電工系講師D002孫六電工系助教D003劉七電工系副教授G001朱八管理系教授G002楊九管理系講師C001羅十成教部副教授表8-2按部門的索引表J04D43G72C91indexstartlength若按職稱進行索引，則得到的索引表中也有4個子表，分別為：

Jiaosou=(a1,a8)FuJiaosou=(a3,a7,a10)Jiangshi=(a2,a5,a9)Zhujiao=(a4,a6)這時的主表用順序存貯不太方便，因相同職稱的教師沒有連在一起，故用鏈式存儲得到主表較方便。具體的存貯如圖8-4所示。在圖8-4中，箭頭上面的數字表示該元素在主表中的下標位置（指針），每個子表中最后個元素的指針為-1，表示為空指針。于是，可以得到如表8-3所示的職稱索引表。

表8-3按職稱的索引表

indexstartlength教授02副教授23

講師13

助教32索引查找的基本思想如下：第一步，在索引表中按index域查找所給值K1，這時可得到子表起始位置start和長度length，若找不到K1，結束查找，表示查找不成功。第二步，在主表的start位置開始，長度為length的范圍內查找所給值K2，若找到，查找成功，否則，查找不成功。例如，對于按部門的索引查找，主表可以用順序存貯，假設K1=“D”，“D”代電工系，K2=“孫六”，則先在表8-2的索引表中找到的index域為“D”的項，得到start=4，length=3，然后從主表的第4個位置開始（即a5）找姓名為“孫六”的人，則在主表的第5個位置可以找到，故查找成功。若假設K1=“D”，K2=“楊九”，則索引表的查找與上面相同，然后在主表的第4個位置開始查找，沒找到，進入第5個位置查找，還沒找到進入第6位置查找，仍然沒找到，但查找的length=3，既只允許3次查找，故查找不成功。若假設K1=“F”，K2=“張三”，則首先在索引表中就找不到“F”，故無需進入主表進行查找，查找不成功。3.索引查找的性能分析由于索引查找中涉及到兩方面查找，第一個是索引表的查找，第二個是主表的查找，假設兩種查找都按順序查找方式進行，則索引表的平均查找長度為(m+1)/2，主表中的平均查找長度為（s+1）/2，(m為索引表的長度，S為主表中相應子表的長度)，則索引查找的平均查找長度為：ASL=(m+1)/2+(s+1）/2。若假定每個子表具有相同的長度，而主表的長度為n，則有n=m.s，這時當s=時，索引查找具有最小的平均查找長度，即ASL=1+。從該公式可以看出，索引查找的性能優先順序查找，但比二分查找要差，時間復雜度介于O(log2n)~O(n)之間。8.2.4分塊查找

1.分塊查找的思想:⑴分塊查找實際上就是一種索引查找，但查找的性能更優先于索引查找。⑵分塊查找的索引表是一個有序表，故可以用二分查找來代替順序查找實現索引表的快速查找。⑶具體實現：將一個含有n個元素的主表分成m個子表，但要求子表之間元素是按關鍵字有序排列的，而子表中元素可以無序的，然后建立索引表⑷索引表中索引域的值用每個子表最大關鍵字代替，則可以按索引查找思想找到表中元素。例如，給定關鍵字序列如下：18,7,26,34,15,42,36,70,60,55,83,90,78,72,74，假設m=3，s=5，即將該序序分成3個子表，每個子表有5個元素，則得到的主表和索引表如圖8-5所示。8．3樹表查找8.3.1二叉排序樹查找1．什么是二叉排序樹二叉排序樹（BinarySortingTree），它或者是一棵空樹，或者是一棵具有如下特征的非空二叉樹：(1)若它的左子樹非空，則左子樹上所有結點的關鍵字均小于根結點的關鍵字；(2)若它的右子樹非空，則右子樹上所有結點的關鍵字均大于等于根結點的關鍵字；(3)左、右子樹本身又都是一棵二叉排序樹。2．二叉排序樹的數據類型描述和第六章類似，可以用一個二叉鏈表來描述一棵二叉排序樹，具體為：

structBtreenode{elemtypedata;//代表關鍵字

Btreenode*left,*right;//代表左、右孩子

};3．二叉排序樹的基本運算（1）二叉排序樹的插入若二叉排序樹為空，則作為根結點插入，否則，若待插入的值小于根結點值，則作為左子樹插入，否則作為右子樹插入，算法描述為：voidInsert

(Btreenode*BST,elemtypeX){if(BST==NULL){Btreenode*p=newBtreenode;

p->data=X;p->left=p->right=NULL;BST=p;}

elseif(BST->data>=X)

Insert(BST->left,X);//在左子樹中扦入

elseInsert(BST->right,X);//在右子樹中扦入}（2）二叉排序樹的建立只要反復調用二叉排序樹的扦入算法即可，算法描述為：Btreenode*Creat(intn)//建立含有n個結點的二叉排序樹{Btreenode*BST=NULL;for(inti=1;i<=n;i++){cin>>x;//輸入關鍵字序列

Insert(BST,x);}returnBST;}例如，結定關鍵字序列79，62，68，90，88，89，17，5，100，120，生成二叉排序樹過程如圖8-6所示。（注：二叉排序樹與關鍵字排列順序有關，排列順序不一樣，得到的二叉排序樹也不一樣）4．二叉排序樹上的查找（1）二叉排序樹的查找思想若二叉排樹為空，則查找失敗，否則，先拿根結點值與待查值進行比較，若相等，則查找成功，若根結點值大于待查值，則進入左子樹重復此步驟，否則，進入右子樹重復此步驟，若在查找過程中遇到二叉排序樹的葉子結點時，還沒有找到待找結點，則查找不成功。（2）二叉排序樹查找的算法實現Btreenode*find(Btreenode*BST,elentypex)

//在以BST為根指針的二叉排隊樹中查找值為x的結點{if(BST==NULL)returnNULL;//查找失敗

else{if(BST->data==x)//查找成功

returnBST;

elseif(BST->data>x)//進入左子樹查找

returnfind(BST->left,x);

else//進入右子樹查找

returnfind(BST->right,x);}}5．二叉排序樹查找的性能分析在二叉排序樹查找中，成功的查找次數不會超過二叉樹的深度，而具有n個結點的二叉排序樹的深度，最好為log2n，最壞為n。因此，二叉排序樹查找的最好時間復雜度為O(log2n)，最壞的時間復雜度為O(n)，一般情形下，其時間復雜度大致可看成O(log2n)，比順序查找效率要好，但比二分查找要差。8.3.2平衡二叉樹查找1．平衡二叉樹的概念平衡二叉樹(balancedbinarytree)是由阿德爾森一維爾斯和蘭迪斯(Adelson-VelskiiandLandis)于1962年首先提出的，所以又稱為AVL樹。若一棵二叉樹中每個結點的左、右子樹的深度之差的絕對值不超過1，則稱這樣的二叉樹為平衡二叉樹。將該結點的左子樹深度減去右子樹深度的值，稱為該結點的平衡因子(balancefactor)。也就是說，一棵二叉排序樹中，所有結點的平衡因子只能為0、1、-1時，則該二叉排序樹就是一棵平衡二叉樹，否則就不是一棵平衡二叉樹。如圖8-8所示二叉排序樹，是一棵平衡二叉樹，而如圖8-9所示二叉排序樹，就不是一棵平衡二叉樹。2.非平衡二叉樹的平衡處理若一棵二叉排序樹是平衡二叉樹，扦入某個結點后，可能會變成非平衡二叉樹，這時，就可以對該二叉樹進行平衡處理，使其變成一棵平衡二叉樹。處理的原則應該是處理與扦入點最近的、而平衡因子又比1大或比-1小的結點。下面將分四種情況討論平衡處理。（1）LL型的處理(左左型)如圖8-10所示，在C的左孩子B上扦入一個左孩子結點A，使C的平衡因子由1變成了2，成為不平衡的二叉樹。這時的平衡處理為：將C順時針旋轉，成為B的右子樹，而原來B的右子樹則變成A的左子樹，待扦入結點A作為B的左子樹。(注：圖中結點旁邊的數字表示該結點的平衡因子)（2）RR型的處理(右右型)如圖8-12所示，在A的右孩子B上扦入一個右孩子C，使A的平衡因子由-1變成-2，成為不平衡的二叉排序樹。這時的平衡處理為：將A逆時針旋轉，成為B的左子樹，而原來B的左子樹則變成A的右子樹，待扦入結點C成為B的右子樹。（3）RL型的處理(右左型)如圖8-13所示，在A的右孩子C上扦入一個左孩子B，使A的平衡因子由-1變成-2，成為不平衡的二叉排序樹。這時的平衡處理為：將B變到A與C之間，使之成為RR型，然后按第(3)種情形RR型處理。（4）LR型的處理(左右型)如圖8-11所示，在C的左孩子A上扦入一個右孩子B，使的C的平衡因子由1變成了2，成為不平衡的二叉排序樹。這是的平衡處理為：將B變到A與C之間，使之成為LL型，然后按第(1)種情形LL型處理。例8-2，給定一個關鍵字序列4,5,7,2,1,3,6，試生成一棵平衡二叉樹。分析：平衡二叉樹實際上也是一棵二叉排序樹，故可以按建立二叉排序樹的思想建立，在建立的過程中，若遇到不平衡，則進行相應平衡處理，最后就可以建成一棵平衡二叉樹。具體生成過程見圖8-14。3．平衡二叉樹的查找及性能分析平衡二叉樹本身就是一棵二叉排序樹，故它的查找與二叉排序樹完全相同。但它的查找性能優于二叉排序樹，不會出現最壞的時間復雜度O(n)，它的時間復雜度與二叉排