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

第7章

查找7.1知識(shí)簡(jiǎn)介

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

順序查找表類(lèi)型定義好之后，可以初始化查找表ST。先新申請(qǐng)能存儲(chǔ)MAXSIZE+1個(gè)ElemType型數(shù)據(jù)的空間（下標(biāo)為0的單元用來(lái)存放哨兵），然后將查找表ST的初始長(zhǎng)度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實(shí)驗(yàn)范例2、算法描述7.3.1范例1

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

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

設(shè)計(jì)查找函數(shù)，在查找表ST中查找學(xué)號(hào)等于stdNo的元素，找到則返回該元素的序號(hào)，否則返回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實(shí)驗(yàn)范例2、算法描述7.3.1范例1

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

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

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

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

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

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

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

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

如果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實(shí)驗(yàn)范例1、問(wèn)題分析7.3.2范例2

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

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

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

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

7.3實(shí)驗(yàn)范例3、算法分析7.3.2范例2

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

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

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

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

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

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

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

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

二分查找的遞歸算法和非遞歸算法邏輯上基本是一致的，都是通過(guò)不斷縮小搜索范圍來(lái)查找目標(biāo)值。二分查找的遞歸算法是通過(guò)函數(shù)自身調(diào)用來(lái)逐步縮小搜索范圍，而非遞歸算法是通過(guò)循環(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）二叉排序樹(shù)查找操作任務(wù)2提示

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

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

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

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

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

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

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

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

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

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

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

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

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