數(shù)據(jù)結(jié)構(gòu)第九章ppt課件-展示頁
2025-05-09 18:12本頁面
【正文】 記該索引塊的最大關(guān)鍵碼及該索引塊的存儲地址 ..如果二級索引在內(nèi)存中也放不下,需要分為許多，,訪問外存次數(shù)等于讀入索引次數(shù)再加上1次讀取對象..必要的話,還可以有4級索引,5極索引,….多級索引結(jié)構(gòu)形成一種 m 叉樹 .31.樹中每一個 分支結(jié)點 表示一個索引塊 ,它最多存放 m 個索引項 ,每個索引項分別給出各子樹結(jié)點 (低一級索引塊 ) 的最大關(guān)鍵碼和結(jié)點地址 ..樹的 葉結(jié)點 中各索引項給出在數(shù)據(jù)表中存放的對象的關(guān)鍵碼和存放地址 .這種 m叉樹用來作為多級索引 ,就是 m路搜索樹 .. m路搜索樹 可能是 靜態(tài)索引結(jié)構(gòu) ,即結(jié)構(gòu)在初始創(chuàng)建 ,數(shù)據(jù)裝入時就已經(jīng)定型 ,在整個運行期間 ,樹的結(jié)構(gòu)不發(fā)生變化 .. m路搜索樹 還可能是 動態(tài)索引結(jié)構(gòu) ,即在整個系統(tǒng)運行期間 ,樹的結(jié)構(gòu)隨數(shù)據(jù)的增刪及時調(diào)整 ,以保持 最佳的搜索效率 . 32多級索引結(jié)構(gòu)形成 m 路搜索樹 33.動態(tài)的 m 路搜索樹.一般定義為 :.一棵 m 路搜索樹 , 它或者是一棵空樹 , 或者是滿足如下性質(zhì)的樹： 根最多有 m 棵子樹 , 并具有如下的結(jié)構(gòu)： n, P0, ( K1, P1 ), ( K2, P2 ), ……, ( Kn, Pn ) 其中， Pi 是指向子樹的指針 ,0 ? i ? n m。第 2層結(jié)點有 2個 ,搜索第 2層結(jié)點要比較 2次 。 /*在后半?yún)^(qū)間繼續(xù)查找 */ } return (0)。 /*查找成功 */ else if( key ST[mid].key) high=mid1。 while(low=high) { mid=(low+high)/2。 low=1。 return(i)。 /*從表尾開始向前查找 */ r[0].key=k。哈希查找 ..幾個基本概念.查找表 :由同一類型的數(shù)據(jù)元素構(gòu)成的集合 ..靜態(tài)查找表 :若 只 在查找表中 搜索 某一特定的數(shù)據(jù)元素是否存在 ,這類搜索過程稱之為靜態(tài)查找 . .動態(tài)查找表 :若在查找表中搜索時 插入 了不存在的數(shù)據(jù)元素或 刪除 了已存在的數(shù)據(jù)元素 ,這類搜索過程稱之為動態(tài)查找表 . 2.關(guān)鍵字 :是數(shù)據(jù)元素中某個數(shù)據(jù)項的值 ,它可以標(biāo)識一個數(shù)據(jù)元素 ..查找 :根據(jù)給定的某個值 ,在查找表中確定一個其關(guān)鍵字等于給定值的記錄或數(shù)據(jù)元素 .. 查找成功 :若表中存在這樣的記錄 ,稱查找是成功的 . . 查找不成功 :若表中不存在關(guān)鍵字等于給定值的記錄 ,稱查找不成功 . 3167。數(shù)據(jù)結(jié)構(gòu)第九章 查找1主要討論的問題：靜態(tài)查找 。動態(tài)查找 。.順序表的查找的定義又 稱線性查找 ,主要用于在線性結(jié)構(gòu)中進行搜索 .. 順序查找的思想從表的一端開始 ,用給定值 k與表中各個結(jié)點的鍵值逐個比較 .1)查找成功 找出相等 k值；2)查找失敗 已到達表的另一端 (可在此設(shè)置一個 監(jiān)視哨 ，作為下標(biāo)越界的條件 ),即表中所有結(jié)點的鍵值都不等于 k.4.監(jiān)視哨的作用 :作為越界 (即已查完 )的檢測條件,省去在循環(huán)中每次均要判定是否越界 ,從而節(jié)省比較的時間 ..順序查找算法：int sxcz(JD r[],int n,int k){ int i=n。 /*設(shè)置監(jiān)視哨 */ while(r[i].key!=k) i。}5.平均查找長度 (在等概率的前提下 )（ n+1） /2.平均查找長度 ASL..如何衡量順序查找的性能？.順序查找的特點 ：1)算法簡單 ,對線性表的邏輯次序無要求 (即不必按關(guān)鍵字值不增或不減的次序排列 )；2)存儲結(jié)構(gòu)可采用順序或鏈?zhǔn)酱鎯Y(jié)構(gòu)均可 ,但其平均查找長度較大 ((n+1)/2).6.思想 :先確定待查找記錄所在的范圍 ,然后逐步縮小范圍 ,直到找到或確認(rèn)找不到該記錄為止 ..二分查找.適用條件 :必須在 具有順序存儲結(jié)構(gòu)的有序表中進行 ..算法實現(xiàn)7.思想 :先確定待查找記錄所在的范圍 ,然后逐步縮小范圍 ,直到找到或確認(rèn)找不到
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1