【正文】 第八章 查找 基本概念 靜態(tài)查找表 動態(tài)查找表 哈希表 ? 查找 —— 也叫檢索，是根據(jù)給定的某個值，在表中確定一個關(guān)鍵字等于給定值的記錄或數(shù)據(jù)元素? 關(guān)鍵字 —— 是數(shù)據(jù)元素中某個數(shù)據(jù)項的值，它可以標(biāo)識一個數(shù)據(jù)元素? 查找方法評價– 查找速度– 占用存儲空間多少– 算法本身復(fù)雜程度– 平均查找長度 ASL(Average Search Length)： 為確定記錄在表中的位置，需和給定值進(jìn)行比較的關(guān)鍵字的個數(shù)的期望值叫查找算法的 ~ 順序表的查找 查找過程：從表的一端開始逐個進(jìn)行記錄的關(guān)鍵字和給定值的比較i例 0 1 2 3 4 5 6 7 8 9 10 11 5 13 18 21 37 56 64 75 80 88 92找 6464監(jiān)視哨i i i i比較次數(shù) =5比較次數(shù)：查找第 n個元素： 1查找第 n1個元素： 2……….查找第 1個元素： n查找第 i個元素： n+1i查找失敗 ： n+1define MAXSIZE 100define KEYTYPE inttypedef struct{KEYTYPE key。 otherdata ……。 // 記錄的其余數(shù)據(jù)部分}SSELEMENT。typedef struct{ SSELEMENT r［ MAXSIZE］ 。 int len。}SSTABLE。int seq_search (KEYTYPE k, SSTABLE st){ int 　 j。 j = 。 ［ 0］ .key = k。 while(［ j］ .key != k) j。 return j。}順序查找算法：?順序查找方法的 ASL? 查找過程 ： 每次將待查記錄所在區(qū)間縮小一半? 適用條件 ：采用順序存儲結(jié)構(gòu)的 有序 表? 算法實現(xiàn) :– 設(shè)表長為 n， low、 high和 mid分別指向待查元素所在區(qū)間的上界、下界和中點(diǎn) ,k為給定值– 初始時，令 low=1,high=n,mid=?(low+high)/2?– 讓 k與 mid指向的記錄比較? 若 k==r[mid].key， 查找成功? 若 kr[mid].key， 則 high=mid1? 若 kr[mid].key， 則 low=mid+1– 重復(fù)上述操作，直至 lowhigh時，查找失敗 有序表查找（折半查找）? 算法描述：low highmid例 1 2 3 4 5 6 7 8 9 10 115 13 18 21 37 56 64 75 80 88 92找 211 2 3 4 5 6 7 8 9 10 115 13 18 21 37 56 64 75 80 88 92low highmid1 2 3 4 5 6 7 8 9 10 115 13 18 21 37 56 64 75 80 88 92low highmid例 1 2 3 4 5 6 7 8 9 10 115 13 18 21 37 56 64 75 80 88 92low highmid找 701 2 3 4 5 6 7 8 9 10 115 13 18 21 37 56 64 75 80 88 92low highmid1 2 3 4 5 6 7 8 9 10 115 13 18 21 37 56 64 75 80 88 92lowhighmid1 2 3 4 5 6 7 8 9 10 115 13 18 21 37 56 64 75 80 88 92low highmid1 2 3 4 5 6 7 8 9 10 115 13 18 21 37 56 64 75 80 88 92lowhigh1185210741936判定樹：1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92算法評價 :判定樹：描述查找過程的二叉樹叫 ~有 n個結(jié)點(diǎn)的判定樹的深度為 ?log2n?+1折半查找法在查找過程中進(jìn)行的比較次數(shù)最多不超過其判定樹的深度折半查找的 ASL： 索引順序表查找（分塊查找）– 查找過程：將表分成幾塊，塊內(nèi)無序，塊間有序；先確定待查記錄所在塊，再在塊內(nèi)查找– 適用條件：分塊有序表– 算法實現(xiàn)?用數(shù)組存放待查記錄 ,每個數(shù)據(jù)元素至少含有關(guān)鍵字域?建立索引表，每個索引表結(jié)點(diǎn)含有最大關(guān)鍵字域和指向本塊第一個結(jié)點(diǎn)的指針1 2 3 4 5 6 7 8 8 10 11 12 13 14 15 16 17 1822 12 13 8 8 20 33 42 44 38 24 48 60 58 74 57 86 5322 48 861 7 13索引表查 38–算法描述 :typedef struct{ int 　 key。 int 　 link。}SD。typedef struct{ int 　 key。 float 　 info。}JD。int blocksrch(JD r[ ],SD nd[ ],int b,int k,int n){ int i=1,j。while((knd[i].key)amp。amp。(i=b) i++。 if(ib) { printf(\nNot found)。 return(0)。 } j=nd[i].link。 while((jn)amp。amp。(k!=r[j].key)amp。amp。(r[j].key=nd[i].key)) j++。 if(k!=r[j].key) { j=0。 printf(\nNot found)。 } return(j)。}ASL 最大 最小 兩者之間表結(jié)構(gòu) 有序表、無序表 有序表 分塊有序表存儲結(jié)構(gòu) 順序存儲結(jié)構(gòu)線性鏈表順序存儲結(jié)構(gòu) 順序存儲結(jié)構(gòu)線性鏈表查找方法比較順序查找 折半查找 分塊查找　動態(tài)查找表　　　 動態(tài)查找表的特點(diǎn)：表結(jié)構(gòu)本身是在查找過程中動態(tài)生成的，即對給定值 key，若表中存在則查找成功，否則插入關(guān)鍵字等于 key的記錄 ．定義：二叉排序樹或是一棵空樹，或 是具有下列性質(zhì)的二叉樹 ：–若它的左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值–若它的右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于或等于它的根結(jié)點(diǎn)的值–它的左、右子樹也分別為二叉排序樹 二叉排序樹生成和插入二叉排序樹的插入：–插入原則： 若二叉排序樹為空，則插入結(jié)點(diǎn)應(yīng)為新的根結(jié)點(diǎn)；否則，繼續(xù)在其左、右子樹上查找，直至某個葉子結(jié)點(diǎn)的左子樹或右子樹為空為止，則插入結(jié)點(diǎn)應(yīng)為該葉子結(jié)點(diǎn)的左孩子或右孩子–二叉排序樹生成 ：從空樹出發(fā)，經(jīng)過一系列的查找、插入操作之后，可生成一棵二叉排序樹? 插入算法例 {10， 18， 3， 8， 12， 2， 7， 3}10 101810183101838101838 12101838 122101838 1227101838 12273中序遍歷二叉排序樹可得到一個關(guān)鍵字的有序序列數(shù)據(jù)結(jié)點(diǎn)類型：define KEYTYPE int。typedef struct node{KEYTYPE key。 otherdata ……。 // 結(jié)點(diǎn)的其余數(shù)據(jù)部分struct node *lchild, *rchild。} BSTNODE插入算法：void insert_btree_onenode(KEYTYPE k, BSTNODE *p){ if(p == NULL) // 如果二叉排序樹空 {p = malloc(sizeof(BSTNODE))。 plchild = NULL。 prchild = NULL。 pkey = k。} else if(k pkey) insert_btree_onenode(k,prchild else insert_btree_onenode(k,plchild }}typedef struct node{ int data。 struct node *lchild,*rchild。}JD。JD *insertbst(JD *r,int x){ JD *p,*q,*s。 s=(JD *)malloc(sizeof(JD))。 sdata=x。 slchild=srchild=NULL。 q=NULL。 if(r==NULL) { r=s。 return(r)。} p=r。 while(p!=NULL) { q=p。 if(xpdata) p=plchild。 else p=prchild。 } if(xqdata) qlchild=s。 else qrchild=s。 r