第10章查找-全文預(yù)覽
【正文】 后該結(jié)點(diǎn)將不滿足 B_樹的定義，此時(shí)若該結(jié)點(diǎn)的左（或右）兄弟結(jié)點(diǎn)中關(guān)鍵字個(gè)數(shù) n大于 m/2+1， 則把該結(jié)點(diǎn)的左（或右）兄弟結(jié)點(diǎn)中最大（或最?。┑年P(guān)鍵字上移到雙親結(jié)點(diǎn)中，同時(shí)把雙親結(jié)點(diǎn)中大于（或小于）上移關(guān)鍵字的關(guān)鍵字下移到要?jiǎng)h除關(guān)鍵字的結(jié)點(diǎn)中，這樣刪去關(guān)鍵字后該結(jié)點(diǎn)以及它的左（或右）兄弟結(jié)點(diǎn)都仍舊滿足 B_樹的定義。 c 39。 b 110 116 132 189 200 (d)插入結(jié)點(diǎn) 195后結(jié)點(diǎn)分裂的過(guò)程 39。 （ 2） 判斷該結(jié)點(diǎn)是否還有空位置 ， 即判斷該結(jié)點(diǎn)是否滿足 nm1， 若該結(jié)點(diǎn)滿足 nm1， 說(shuō)明該結(jié)點(diǎn)還有空位置 ， 直接把關(guān)鍵字；若該結(jié)點(diǎn)有 n=m1， 說(shuō)明該結(jié)點(diǎn)已沒(méi)有空位置 ， 要插入就要分裂該結(jié)點(diǎn) 。 （ 2） 若 keyK1則沿著指針 P0所指的子樹繼續(xù)查找 。 B_樹中所有結(jié)點(diǎn)的孩子結(jié)點(diǎn)的最大值稱為 B_樹的階 ， 一棵 m階的 B_樹或者是一棵空樹，或者是滿足下列要求的 m叉樹： (1)樹中每個(gè)結(jié)點(diǎn)至多有 m個(gè)孩子結(jié)點(diǎn)。 在一般情況下，二叉排序樹的平均查找長(zhǎng)度為 O(log2n)。 else printf(\n數(shù)據(jù)元素不存在 ！ )。root, test[i])。 BiTreeNode *root = NULL。 printf(%d , root)。 struct node *rightChild。 typedef struct { KeyType key。 (3)要?jiǎng)h除結(jié)點(diǎn) 只有右孩子結(jié)點(diǎn) ， 刪除該結(jié)點(diǎn)且使被刪除結(jié)點(diǎn)的雙親結(jié)點(diǎn)指向被刪除結(jié)點(diǎn)的右孩子結(jié)點(diǎn) 。 return 1。 prightChild = NULL。 else current = currentleftChild。 current = *root。 else p = pleftChild。 381 12 410 9 40 394 540 35 190 146 476 760 445 600 800 下圖所示就是一棵二叉排序樹 二、二叉排序樹的查找算法 int Search(BiTreeNode *root, DataType item) { BiTreeNode *p。 二叉排序樹中結(jié)點(diǎn)的結(jié)構(gòu)體定義如下： typedef struct node { DataType data。 相關(guān)術(shù)語(yǔ) 假設(shè)索引表的長(zhǎng)度為 m， 主表中每個(gè)子表的長(zhǎng)度為 s， 并假設(shè)在索引表上和在主表上均采用順序查找算法 ， 則索引順序表上查找算法的 平均查找長(zhǎng)度 為： 122 12 1 ??????? smsmA S L算法分析 動(dòng)態(tài)查找表 動(dòng)態(tài)查找表主要有 二叉樹結(jié)構(gòu) 和 樹結(jié)構(gòu) 兩種類型。 完全索引表 :和主表項(xiàng)完全相同，但只包含索引關(guān)鍵字和該數(shù)據(jù)元素在主表中位置信息的索引表 二級(jí)索引表 :當(dāng)主表中的數(shù)據(jù)元素個(gè)數(shù)非常龐大時(shí)，按照建立索引表的同樣方法對(duì)索引表再建立的索引表。 //查找失敗 } 算法分析 查找成功時(shí)的平均查找長(zhǎng)度 ASL成功 為： 查找失敗時(shí)的平均查找長(zhǎng)度 ASL失敗 為 nnnninCPA S Lnikiiii 221 11 lo g1)1(lo g112 ??????? ? ?? ??成功)1(lo g)1(lo g1 221 1????? ? ?? ?nnnCPA S Lniniii失敗 當(dāng)順序表中的數(shù)據(jù)元素個(gè)數(shù)非常大時(shí)，采用 在順序表上建立索引表 的辦法提高查找速度。 //確定查找區(qū)間中心下標(biāo) if(a[mid].key == key) return mid。反之，如果 key大，則縮小至后半部?jī)?nèi)查找。 if(a[i].key == key) return i。 查找函數(shù)設(shè)計(jì)如下： int SeqSearch(DataType a[], int n, KeyType key) //在 a[0]a[n1]中順序查找關(guān)鍵碼為 key的數(shù)據(jù)元素 //查找成功時(shí)返回該元素的下標(biāo)序號(hào)；失敗時(shí)返回 1 { int i = 0。 主關(guān)鍵字 :能夠惟一區(qū)分各個(gè)不同數(shù)據(jù)元素的關(guān)鍵字 次關(guān)鍵字 :通常不能惟一區(qū)分各個(gè)不同數(shù)據(jù)元素的關(guān)鍵字 查找成功 :在數(shù)據(jù)元素集合中找到了要查找的數(shù)據(jù)元素 查找不成功 :在數(shù)據(jù)元素集合中沒(méi)有找到要查找的數(shù)據(jù)元素 靜態(tài)查找 :只查找，不改變數(shù)據(jù)元素集合內(nèi)的數(shù)據(jù)元素 動(dòng)態(tài)查找 :既查找，又改變（增減）集合內(nèi)的數(shù)據(jù)元素 靜態(tài)查找表 :靜態(tài)查找時(shí)構(gòu)造的存儲(chǔ)結(jié)構(gòu) 動(dòng)態(tài)查找表 :動(dòng)態(tài)查找時(shí)構(gòu)造的存儲(chǔ)結(jié)構(gòu) 平均查找長(zhǎng)度 :查找過(guò)程所需進(jìn)行的關(guān)鍵字比較次數(shù)的平均值 ,是衡量查找算法效率的最主要標(biāo)準(zhǔn) ,其數(shù)學(xué)定義為： ?? ??niii CPA S L1其中， Pi是要查找數(shù)據(jù)元素出現(xiàn)的概率， Ci是查找相應(yīng)數(shù)據(jù)元素的比較次數(shù)。也稱作 檢索 。 靜態(tài)查找表 靜態(tài)查找表主要有三種結(jié)構(gòu)： 順序表 有序順序表 索引順序表 在順序表上查找的 基本思想是： 從順序表的一端開(kāi)始，用給定數(shù)據(jù)元素的關(guān)鍵字逐個(gè)和順序表中各數(shù)據(jù)元素的關(guān)鍵字比較，若在順序表中查找到要查找的數(shù)據(jù)元素，則查找成功，函數(shù)返回該數(shù)據(jù)元素在順序表中的位置；否則查找失敗，函數(shù)返回 1。 a[i].key != key) i++。 一 、 順序查找 有序順序表上的順序查找算法和順序表上的查找算法方法類同 二、二分查找（ 又稱 折半查找） 算法的基本思想： 先給數(shù)據(jù)排序 （例如按升序排好），形成 有序表， 然后再將 key與 正中 元素相比，若 key小，則縮小至前半部?jī)?nèi)查找；再取其 中值 比較，每次縮小 1/2的范圍，直到查找成功或失敗為止。 while(low = high) { mid = (low + high)/2。 } return 1。 8 14 6 9 10 22 34 18 19 31 40 38 54 66 46 71 78 68 80 85 14 0 0 34 5 1 66 10 2 85 15 3 key link 下標(biāo) 索引表 0 1 2 3 4
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1