數(shù)據(jù)結(jié)構(gòu)與算法實踐指導(dǎo) 課件 7-查找

第7章

查找7.1知識簡介

在數(shù)據(jù)結(jié)構(gòu)中，查找是計算機科學(xué)中的一個重要概念和操作，它是指在一組預(yù)先組織好的數(shù)據(jù)集合（稱為查找表或查找結(jié)構(gòu)）中確定一個特定的數(shù)據(jù)元素（記錄或鍵值對）的過程。查找的目的通常是為了找到與給定關(guān)鍵字相匹配的數(shù)據(jù)元素。7.1.1查找1、查找表

查找表是由同一類型的數(shù)據(jù)元素（或記錄）構(gòu)成的集合。由于“集合”中的數(shù)據(jù)元素之間存在著完全松散的關(guān)系，因此查找表是一種非常靈便的數(shù)據(jù)結(jié)構(gòu)，可以利用其他的數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)，如線性表、樹表和散列表等。7.1知識簡介2、關(guān)鍵字

關(guān)鍵字是數(shù)據(jù)元素中的某個特定字段，用以區(qū)分不同的數(shù)據(jù)元素。主關(guān)鍵字通常是用來進行查找的主要依據(jù)，而次關(guān)鍵字則可以用于輔助排序或進一步細化搜索條件。7.1.1查找3、查找方法

按數(shù)據(jù)結(jié)構(gòu)組織方式可以分為：線性表的查找、樹表的查找和哈希表的查找。

線性表的查找：采用線性表作為查找表的組織形式，在線性表中查找指定元素主要方法有：順序查找、折半查找（也稱為二分查找，僅限于有序線性表）、分塊查找。7.1知識簡介7.1.1查找

樹表的查找：采用樹作為查找表的組織形式，查找操作主要依賴于樹的類型和特性，查找方法有：二叉排序樹（二叉查找樹）、B樹、AVL樹、紅黑樹等，根據(jù)結(jié)點的關(guān)鍵字值進行遞歸搜索。

哈希表的查找：哈希表（HashTable）是一種高效的數(shù)據(jù)結(jié)構(gòu)，它通過使用哈希函數(shù)將關(guān)鍵字映射到一個固定大小的數(shù)組中，從而實現(xiàn)快速查找、插入和刪除操作。4、查找性能指標(biāo)

查找長度：查找過程中實際需要對比的關(guān)鍵字次數(shù)。

平均查找長度(ASL)：為了確定數(shù)據(jù)元素在查找表中的位置，需和給定值進行比較的關(guān)鍵字個數(shù)的期望值，稱為查找算法在查找成功時的平均查找長度。它是衡量查找算法效率的重要標(biāo)準(zhǔn)。7.1知識簡介

在線性表的查找中，順序查找既適用于線性表的順序存儲結(jié)構(gòu)，用適用于線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)，折半查找要求線性表必須是順序存儲結(jié)構(gòu)，分塊查找的表可以是順序存儲結(jié)構(gòu)也可以是鏈?zhǔn)酱鎯Y(jié)構(gòu)，但索引表必須是順序存儲結(jié)構(gòu)。7.1.2線性表的查找

查找表采用順序存儲結(jié)構(gòu)的數(shù)據(jù)描述為：//數(shù)據(jù)元素類型typedefstruct{KeyTypekey;//關(guān)鍵字域InfoTypeotherinfo;}ElemType;typedefstruct{ElemType*R;//存儲空間基地址intlength;//當(dāng)前長度}SSTable;7.1知識簡介7.1.3樹表的查找

樹表的查找主要掌握二叉排序樹。二叉排序樹或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹：若左子樹不空，則左子樹上所有結(jié)點的值均小于根結(jié)點的值；若右子結(jié)不空，則右子樹上所有結(jié)點的值均大于根結(jié)點的值；左右子樹又分別是二叉排序樹。

采用二叉鏈表存儲結(jié)構(gòu)存儲二叉排序樹，二叉鏈表存儲表示如下：//數(shù)據(jù)元素類型typedefstruct{KeyTypekey;//關(guān)鍵字項InfoTypeotherinfo;//其他數(shù)據(jù)項}ElemType;typedefstructBSTNode{ElemTypedata;structBSTNode*lchild;//左孩子指針

structBSTNode*rchild;//右孩子指針}BSTNode,*BSTree;7.2實驗?zāi)康?/p>

通過本章的實驗，深刻理解基于不同查找結(jié)構(gòu)的查找技術(shù)，在實際應(yīng)用中能夠靈活選擇或設(shè)計合適的查找方法，同時鍛煉學(xué)生實際編程和算法設(shè)計的能力。7.3實驗范例學(xué)號姓名性別大學(xué)英語高等數(shù)學(xué)2023001AlanF93882023002DanieM75692023003PeterM56772023004BillF87902023005HelenM79862023006AmyF6875一個班有50個學(xué)生，每個學(xué)生的信息有學(xué)號、姓名、性別、大學(xué)英語成績和高等數(shù)學(xué)成績，學(xué)生信息如下表所示。要求根據(jù)輸入的學(xué)號查找學(xué)生的信息。7.3實驗范例

順序查找（設(shè)置監(jiān)視哨）：根據(jù)輸入的n個學(xué)生的信息，建立順序表，并在順序表中用順序查找方法（帶監(jiān)視哨）查找與輸入的學(xué)號相同的學(xué)生信息，輸出該學(xué)生的所有信息。7.3.1范例17.3實驗范例1、問題分析7.3.1范例1

先需要定義順序表，順序表中每個元素用來存儲一個學(xué)生的信息，需要定義結(jié)構(gòu)體類型，數(shù)據(jù)元素的類型就是結(jié)構(gòu)體類型。

然后初始化順序表，分配能放MAXSIZE+1學(xué)生信息的空間（下標(biāo)為0的單元用來存放哨兵），將順序表的長度初始化為0。

接著建立長度為n的順序表，輸入n個學(xué)生信息，將學(xué)生信息存入順序表中。這個過程和實驗一的過程相同。輸入需要查找學(xué)生的學(xué)號，利用順序查找在順序表中查找和給定學(xué)號相同的學(xué)生。7.3實驗范例1、問題分析7.3.1范例1

順序查找（帶監(jiān)視哨）操作的基本步驟：

先將帶查找的關(guān)鍵字的值存入監(jiān)視哨中，監(jiān)視哨可設(shè)置在表頭，也可設(shè)置在表尾，這里我們將其設(shè)置在表頭。

接著從表中最后一個元素開始，逆序掃描查找表，依次將掃描到的元素的學(xué)號與所給學(xué)號進行比較，相等，返回該元素的下標(biāo)。由于將待查找的學(xué)號放在下標(biāo)為0的位置，如果元素不存在，當(dāng)比較到監(jiān)視哨時兩個學(xué)號相等，返回0，表示查找失敗。

由于順序表中的數(shù)據(jù)元素包含多個數(shù)據(jù)，輸入一個學(xué)生信息和輸出一個學(xué)生信息分別定義兩個函數(shù)來實現(xiàn)。7.3實驗范例2、算法描述7.3.1范例1先定義順序查找表SSTable，定義如下：//數(shù)據(jù)元素類型typedefstructStudent{charNo[8];//學(xué)號charname[16];//姓名charsex;//性別intenglish;//大學(xué)英語成績intmath;//高等數(shù)學(xué)成績}ElemType;//順序查找表typedefstruct{ElemType*R;//存儲空間基地址intlength;//當(dāng)前長度}SSTable;7.3實驗范例2、算法描述7.3.1范例1

順序查找表類型定義好之后，可以初始化查找表ST。先新申請能存儲MAXSIZE+1個ElemType型數(shù)據(jù)的空間（下標(biāo)為0的單元用來存放哨兵），然后將查找表ST的初始長度length設(shè)置為0。初始化查找表的函數(shù)可以定義如下：voidInitList(SSTable&ST){

//分配內(nèi)存單元，下標(biāo)為0的位置放哨兵

ST.R=(ElemType*)malloc((MAXSIZE+1)*sizeof(ElemType));

if(!ST.R)

exit(0);

ST.length=0;}7.3實驗范例2、算法描述7.3.1范例1

接著設(shè)計函數(shù)用來建立長度為n的查找表ST，輸入n個學(xué)生信息存入查找表ST中，將查找表當(dāng)前長度length設(shè)置為n。在定義該函數(shù)之前定義函數(shù)用來輸入一個學(xué)生信息。輸入一個學(xué)生信息的函數(shù)定義如下：voidInputOneStu(ElemType&stu){fflush(stdin);//清空輸入緩沖區(qū)printf("學(xué)號:");gets(stu.No);fflush(stdin);printf("姓名:");fflush(stdin);gets();printf("性別：");scanf("%c",&stu.sex);printf("大學(xué)英語成績：");scanf("%d",&stu.english);printf("高等數(shù)學(xué)成績：");scanf("%d",&stu.math);}7.3實驗范例2、算法描述7.3.1范例1

在建立長度為n的查找表函數(shù)中循環(huán)n次調(diào)用函數(shù)InputOneStu()用來輸入n個學(xué)生信息，函數(shù)可以定義如下：voidCreateSSTable(SSTable&ST,intn){inti;printf("輸入%d個學(xué)生信息：\n",n);for(i=1;i<=n;i++){InputOneStu(ST.R[i]);}ST.length=n;}7.3實驗范例2、算法描述7.3.1范例1

設(shè)計查找函數(shù)，在查找表ST中查找學(xué)號等于stdNo的元素，找到則返回該元素的序號，否則返回0。函數(shù)可以定義如下：intSearch_Seq(SSTable&ST,char*stdNo){inti;strcpy(ST.R[0].No,stdNo);//設(shè)置哨兵for(i=ST.length;strcmp(ST.R[i].No,stdNo)!=0;i--);returni;}7.3實驗范例2、算法描述7.3.1范例1

定義函數(shù)PrintStuInfo(Studentstu)實現(xiàn)輸出一個學(xué)生的信息。函數(shù)可以定義如下：voidPrintStuInfo(Studentstu){printf("學(xué)號：%s\n",stu.No);printf("姓名：%s\n",);printf("性別：%c\n",stu.sex);printf("大學(xué)英語成績：%d\n",stu.english);printf("高等數(shù)學(xué)成績：%d\n",stu.math);}7.3實驗范例2、算法描述7.3.1范例1

在main()函數(shù)中定義查找表L，然后調(diào)用InitList()函數(shù)對查找表L進行初始化，接著調(diào)用CreateSSTable()函數(shù)將n個學(xué)生信息存入查找表中，輸入待查找的學(xué)號存入stdNo字符數(shù)組中，調(diào)用Search_Seq()函數(shù)在L中查找學(xué)號等于stdNo的學(xué)生，并返回其下標(biāo)。如果返回值不等于0，表示該學(xué)號的學(xué)生存在，輸出該學(xué)生的所有信息。如果等于0，表示該學(xué)號的學(xué)生不存在。7.3實驗范例2、算法描述7.3.1范例1#include<stdio.h>#include<stdlib.h>#include<string.h>#defineMAXSIZE100//在main()之前加入類型定義和函數(shù)定義intmain(){intm,stdPos;charstdNo[8];SSTableL;InitList(L);printf("---------順序查找---------\n");printf("請輸入順序表的長度:");scanf("%d",&m);CreateSSTable(L,m);7.3實驗范例2、算法描述7.3.1范例1printf("請輸入需要查找的學(xué)生學(xué)號：");fflush(stdin);scanf("%s",stdNo);stdPos=Search_Seq(L,stdNo);if(stdPos!=0){printf("存在學(xué)號為%s的學(xué)生，該學(xué)生信息如下\n",stdNo);PrintStuInfo(L.R[stdPos]);}else{printf("不存在學(xué)號為%s的學(xué)生！\n",stdNo);}return0;}7.3實驗范例3、算法分析7.3.1范例1

按值查找操作時間主要耗費在比較元素上，而比較的次數(shù)取決于被查元素在表中的位置，平均比較次數(shù)為(n+1)/2，時間復(fù)雜度為O(n)。通過設(shè)置監(jiān)視哨，當(dāng)順序表長度大于1000時，進行一次查找所需的平均時間比普通算法的時間幾乎減少一半。7.3實驗范例

二分查找（遞歸算法）：假設(shè)范例1中的順序表已按照學(xué)號遞增有序，用二分查找方法在該順序表中查找與給定學(xué)號相等的學(xué)生信息，并輸出該學(xué)生的所有信息。7.3.2范例27.3實驗范例1、問題分析7.3.2范例2

能使用二分查找的前提是待查找表是有序的，而且是順序存儲方式。在任務(wù)1所建的查找表基礎(chǔ)上用二分查找查找，在建立查找表時按學(xué)號從小到大的順序輸入學(xué)生信息。二分查找是從表的中間元素開始查找，如果給定值和中間元素的關(guān)鍵字值相等，則查找成功；如果給定值大于或小于中間元素的關(guān)鍵字值，則在表中大于或小于中間元素的那一半中查找，重復(fù)操作，直到找到或者在某步中查找區(qū)間為空，則查找失敗。7.3實驗范例1、問題分析7.3.2范例2

假設(shè)待查找表ST中元素的起止元素下標(biāo)為low和high，查找關(guān)鍵字值為key的元素的步驟為：

（1）判斷l(xiāng)ow是否大于high，是則返回-1，查找結(jié)束；

（2）否則，計算中間元素的下標(biāo)mid，mid=(low+high)/2，將下標(biāo)為mid的元素的關(guān)鍵字值和key進行比較：

如果key和下標(biāo)為mid的元素關(guān)鍵字的值相等，返回mid；

如果key小于下標(biāo)為mid的元素關(guān)鍵字的值，則在下標(biāo)為low和mid-1之間的元素中繼續(xù)查找；

如果key大于下標(biāo)為mid的元素關(guān)鍵字的值，則在下標(biāo)為mid+1和high之間的元素中繼續(xù)查找。7.3實驗范例1、問題分析7.3.2范例2

本范例中需要查找和給定學(xué)號相同的學(xué)生信息，所以key為學(xué)號，學(xué)號為字符數(shù)組，在比較時需要用調(diào)用庫函數(shù)strcmp實現(xiàn)。7.3實驗范例2、算法描述7.3.2范例2

先需建立一個遞增有序的查找表ST，可以利用函數(shù)CreateSSTable(SSTable&ST,intn)建立長度為n的查找表ST，在輸入學(xué)生信息時按照學(xué)號從小到大的順序輸入。接著設(shè)計遞歸函數(shù)Search_Bin(SSTableST,char*stdNo,intlow,inthigh)，在查找表ST中下標(biāo)為low到high之間元素中查找學(xué)號等于stdNo的元素。找到返回該元素序號，否則返回0。7.3實驗范例2、算法描述7.3.2范例2

遞歸函數(shù)Search_Bin()可以如下定義：intSearch_Bin_Recur(SSTableST,char*stdNo,intlow,inthigh){intmid;if(low>high)return0;//查找表找完mid=(low+high)/2;//計算中間元素的位置intcmpResult=strcmp(stdNo,ST.R[mid].No);if(cmpResult==0)returnmid;//找到，返回該元素的位置elseif(cmpResult<0)returnSearch_Bin_Recur(ST,stdNo,low,mid-1);//在[low,mid-1]的元素中繼續(xù)查找elsereturnSearch_Bin_Recur(ST,stdNo,mid+1,high);//在[mid+1,high]的元素中繼續(xù)查找}7.3實驗范例2、算法描述7.3.2范例2

在main()函數(shù)中定義查找表L，調(diào)用InitList()函數(shù)對查找表L進行初始化，接著調(diào)用CreateSSTable()函數(shù)將n個學(xué)生信息輸入到查找表中，輸入待查找學(xué)號stdNo，調(diào)用Search_Bin_Recur()函數(shù)在L中查找學(xué)號為stdNo的元素的位置，如果該學(xué)生存在，則調(diào)用PrintStuInfo()輸出該學(xué)生信息。這個過程和范例1的過程一樣，只需將查找函數(shù)改成二分查找函數(shù)Search_Bin_Recur()即可。7.3實驗范例2、算法描述7.3.2范例2#include<stdio.h>#include<stdlib.h>#include<string.h>#defineMAXSIZE100//在main()之前加入類型定義和函數(shù)定義intmain(){intm,stdPos;charstdNo[8];SSTableL;InitList(L);printf("---------順序查找---------\n");printf("請輸入順序表的長度:");scanf("%d",&m);CreateSSTable(L,m);7.3實驗范例2、算法描述7.3.2范例2printf("請輸入需要查找的學(xué)生學(xué)號：");fflush(stdin);scanf("%s",stdNo);stdPos=Search_Bin_Recur(L,stdNo,1,L.length);if(stdPos!=0){printf("存在學(xué)號為%s的學(xué)生，該學(xué)生信息如下\n",stdNo);PrintStuInfo(L.R[stdPos]);}

else{printf("不存在學(xué)號為%s的學(xué)生！\n",stdNo);}return0;}

7.3實驗范例3、算法分析7.3.2范例2

二分查找算法利用了查找表的有序特性，每次都將查找區(qū)間縮小一半。在最理想的情況下，每進行一次比較，問題規(guī)模減半。因此，對于包含n個元素的查找表，最多需要log2n次比較就能找到目標(biāo)值或者確定目標(biāo)值不存在，所有二分查找的時間復(fù)雜度為O(logn)。

在二分查找的遞歸算法中，遞歸深度等于最大的比較次數(shù)，即log2n+1（加1是因為當(dāng)元素數(shù)量為1時仍然需要一次遞歸調(diào)用）。因此，二分查找遞歸算法的空間復(fù)雜度為O(logn)，因為遞歸調(diào)用過程中會占用遞歸棧，每個遞歸層級通常需要常量級別的額外空間來保存局部變量和返回地址。7.4實驗任務(wù)完成下列任務(wù)，并分析各算法的時間復(fù)雜度。任務(wù)1：二分查找（非遞歸算法），實現(xiàn)范例2中二分查找的非遞歸算法。任務(wù)2：二叉排序樹，編程實現(xiàn)如下功能：

（1）按照輸入的n個關(guān)鍵字序列順序建立二叉排序樹，二叉排序樹采用二叉鏈表的存儲結(jié)構(gòu)。

（2）先輸入待查找記錄的關(guān)鍵字值key，然后在二叉排序樹上查找該記錄，如果在二叉排序樹中存在該記錄，則顯示“找到”的信息，否則顯示“找不到”的信息。

（3）輸入待插入記錄的關(guān)鍵字值key，然后在二叉排序樹上查找該記錄，如果查找失敗，則在二叉排序樹中插入該記錄對應(yīng)的結(jié)點，并輸出插入操作后的二叉排序樹（以某種遍歷序列表示）。7.4實驗任務(wù)完成下列任務(wù)，并分析各算法的時間復(fù)雜度。任務(wù)1：二分查找（非遞歸算法），實現(xiàn)范例2中二分查找的非遞歸算法。任務(wù)2：二叉排序樹，編程實現(xiàn)如下功能：

（4）輸入待刪除記錄的關(guān)鍵字值key，然后在二叉排序樹上查找該記錄，如果查找成功，則在二叉排序樹中刪除該記錄對應(yīng)的結(jié)點，并輸出刪除操作后的二叉排序樹（以某種遍歷序列表示）。

假設(shè)二叉排序樹中元素的關(guān)鍵字值類型為int。7.4實驗任務(wù)完成下列任務(wù)，并分析各算法的時間復(fù)雜度。任務(wù)3（選做）：編程實現(xiàn)分塊查找，有如下功能：（1）建立索引查找表；（2）利用索引查找確定給定記錄在索引查找表中的塊號和在塊中的位置。

索引查找表有索引表和塊表兩部分所構(gòu)成，其中索引表存儲的是各塊記錄中的最大關(guān)鍵字值和各塊的起始存儲地址，用順序存儲結(jié)構(gòu)，各塊的起始存儲地址的初始值置為空指針；而塊表中存儲的是查找表中的所有記錄并且按塊有序，用鏈?zhǔn)酱鎯蝽樞虼鎯Y(jié)構(gòu)，在此用鏈?zhǔn)酱鎯Y(jié)構(gòu)。7.5任務(wù)提示

二分查找的遞歸算法和非遞歸算法邏輯上基本是一致的，都是通過不斷縮小搜索范圍來查找目標(biāo)值。二分查找的遞歸算法是通過函數(shù)自身調(diào)用來逐步縮小搜索范圍，而非遞歸算法是通過循環(huán)結(jié)構(gòu)迭代地更新搜索范圍。任務(wù)1提示7.5任務(wù)提示任務(wù)1提示intSearch_Bin(SSTableL,char*stdNo){//若找到，則函數(shù)值為該元素在表中的位置，否則為0low=1;high=L.length;while(low<=high){mid=(low+high)/2;cmpResult=strcmp(stdNo,L.R[mid].No);if(cmpResult==0)returnmid;elseif(cmpResult<0)high=mid-1;//在前面的子表中查找elselow=mid+1; //在后面的子表中查找}return0; //查找失敗}

7.5任務(wù)提示（1）二叉排序樹查找操作任務(wù)2提示

對于給定的待查找記錄的關(guān)鍵字值key，在二叉排序樹非空的情況下，先將給定的值key與二叉排序樹的根結(jié)點的關(guān)鍵字值進行比較，如果相等，則查找成功，函數(shù)返回指向根結(jié)點的指針，否則，如果給定的值key小于根結(jié)點的關(guān)鍵字值，則在二叉排序樹的左子樹上繼續(xù)查找；如果給定的值key大于根結(jié)點的關(guān)鍵字值，則在二叉排序樹的右子樹上繼續(xù)查找，直到查找成功，函數(shù)返回結(jié)點的地址。如果子樹為空即查找失敗，函數(shù)返回空指針。7.5任務(wù)提示（1）二叉排序樹查找操作任務(wù)2提示BSTreeSearchBST(BSTreeT,KeyTypekey){if((!T)||key==T->data.key)returnT; elseif(key<T->data.key)returnSearchBST(T->lchild,key); //在左子樹中繼續(xù)查找elsereturnSearchBST(T->rchild,key); //在右子樹中繼續(xù)查找}7.5任務(wù)提示（2）二叉排序樹的插入操作任務(wù)2提示

如果已知二叉排序樹是空樹，則插入的結(jié)點成為二叉排序樹的根結(jié)點；如果待插入結(jié)點的關(guān)鍵字值小于根結(jié)點的關(guān)鍵字值，則插入到左子樹中；如果待插入結(jié)點的關(guān)鍵字值大于根結(jié)點的關(guān)鍵字值，則插入到右子樹中。7.5任務(wù)提示（2）二叉排序樹的插入操作任務(wù)2提示

voidInsertBST(BSTree&T,KeyTypee){if(!T){//找到插入位置，遞歸結(jié)束

S=(BSTNode*)malloc(sizeof(BSTNode));//生成新結(jié)點SS->data=e;S->lchild=S->rchild=NULL;T=S;//把新結(jié)點S鏈接到插入位置} elseif(key<T->data.key)InsertBST(T->lchild,key); //將key插入到左子樹中elseif(key>T->data.key)InsertBST(T->rchild,key);//將key插入到右子樹中}7.5任務(wù)提示（3）二叉排序樹的建立任務(wù)2提示

從空的二叉排序樹開始，每輸入一個結(jié)點，經(jīng)過查找操作，將新結(jié)點插入到當(dāng)前二叉排序樹的合適位置。voidCreateBST(BSTree&T){//依次讀入一個關(guān)鍵字為e的結(jié)點，將此結(jié)點插入二叉排序樹T中T=NULL;//將二叉排序樹T初始化為空樹cin>>e; //輸入待插入結(jié)點關(guān)鍵字的值while(e!=ENDFLAG){//ENDFLAG為自定義常量InsertBST(T,e);//將此結(jié)點插入二叉排序樹T中cin>>e;}}7.5任務(wù)提示（4）二叉排序樹的刪除操作任務(wù)2提示

在二叉排序樹中刪除結(jié)點，需分三種情況分別處理：若待刪除的結(jié)點是葉子結(jié)點，則只要將其雙親結(jié)點中相應(yīng)指針域的值改為“空”；若待刪除的結(jié)點只有左子樹或者只有右子樹，則只要將其雙親結(jié)點的相應(yīng)指針域的值改為“指向待刪除結(jié)點的左子樹或右子樹”；若待刪除的結(jié)點既有左子樹又有右子樹，則以其中序遍歷序列下的前驅(qū)結(jié)點替代掉待刪結(jié)點p，然后再刪除該前驅(qū)結(jié)點。7.5任務(wù)提示（4）二叉排序樹的刪除操作任務(wù)2提示voidBSTdelete(BSTree&T,KeyTypekey){p=T;f=NULL;while(p){ if(p->data.key==key)break;//找到等于key的結(jié)點p f=p;//f為p的雙親 if(p->data.key>key)p=p->lchild;//在p的左子樹中繼續(xù)查找 elsep=p->rchild;//在p的右子樹中繼續(xù)查找}if(!p)return;//元素不存在q=p;7.5任務(wù)提示（4）二叉排序樹的刪除操作任務(wù)2提示

if((p->lchild)&&(p->rchild))//待刪結(jié)點左右子樹都不為空{(diào)s=p->lchild;//找到被刪結(jié)點p在中序遍歷序列中的前驅(qū)結(jié)點while(s->rchild){

q=s;//記下s的雙親結(jié)點 s=s->rchild;//一直向右}p->data=s->data;//s為被刪結(jié)點的前驅(qū)if(q!=p)q->rchild=s->lchild;elseq->lchild=s->lchild;deletes;return;

}7.5任務(wù)提示（4）二叉排序樹的刪除操作任務(wù)2提示elseif(p->rchild==NULL)//待刪結(jié)點無右子樹{p=p->lchild;}else//待刪結(jié)點無左子樹{p=p->rchild;}if(!f)T=p;elseif(q==f->lchild)f->lchild=p;elsef->rchild=p;deleteq;}7.5任務(wù)提示

分塊查找（BlockingSearch）又稱為索引順序查找，是折半查找和順序查找的一種改進方法，性能介于兩者之間。分塊查找的前提是線性表可分解成若干塊，每塊中的元素之間是無序的，但塊與塊之間必須有序。假設(shè)是按關(guān)鍵碼值非遞減的，塊與塊之間有序是指對于任意的塊i，第i塊中的所有元素的關(guān)鍵碼值都必須小于第i+1塊中的所有節(jié)點的關(guān)鍵碼值。還需建立一個索引表，把每塊中的最大關(guān)鍵碼值作為索引表的關(guān)鍵碼值，按塊的順序存放到一個輔助數(shù)組中，這個輔助數(shù)組是按關(guān)鍵碼值非遞減排序的。任務(wù)3提示7.5任務(wù)提示

查找時，首先在索引表中進行查找，確定要找的節(jié)點所在的塊。由于索引表是排序的，因此，對索引表的查找可以采用順序查找或折半查找；然后，在相應(yīng)的塊中采用順序查找，即可找到對應(yīng)的節(jié)點。如下圖所示，表中有15個記錄，分成3塊，給每個塊建立一個索引項，每個索引項包括兩個部分：關(guān)鍵字（塊內(nèi)最大關(guān)鍵字）和指針項（塊內(nèi)第一個元素的位置）。任務(wù)3提示7.5任務(wù)提示分塊查找的過程分為兩步：

第一步：在索引表中確定待查找記錄所在的塊。由于塊間有序，即索引表中的元素是有序的，故可以采用折半查找或順序查找索引表；

第二步：在塊內(nèi)順序查找該待查記錄。由于塊內(nèi)無序，故只能采用順序查找。任務(wù)3提示7.5任務(wù)提示存儲結(jié)構(gòu)的定義：任務(wù)3提示//數(shù)據(jù)元素的類型typedefstruct{KeyTypekey;//關(guān)鍵字InforTypeotherInfo;//其他信息}ElemType;//索引表中元素的定義typedefstruct{KeyTypemaxKey;//