《數(shù)據(jù)結(jié)構(gòu)（C語言描述）（第2版）》教學(xué)課件7-03分塊查找_第1頁
《數(shù)據(jù)結(jié)構(gòu)（C語言描述）（第2版）》教學(xué)課件7-03分塊查找_第2頁
《數(shù)據(jù)結(jié)構(gòu)（C語言描述）（第2版）》教學(xué)課件7-03分塊查找_第3頁
《數(shù)據(jù)結(jié)構(gòu)（C語言描述）（第2版）》教學(xué)課件7-03分塊查找_第4頁
《數(shù)據(jù)結(jié)構(gòu)（C語言描述）（第2版）》教學(xué)課件7-03分塊查找_第5頁
已閱讀5頁，還剩1頁未讀， 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請進行舉報或認領(lǐng)

文檔簡介

1、2016數(shù)據(jù)結(jié)構(gòu)Data structure講授：賀寧 分塊查找常州信息職業(yè)技術(shù)學(xué)院0203線性表查找分塊查找1、分塊查找表存儲結(jié)構(gòu)：分塊查找表由“分塊有序”的線性表和索引表組成。（1）“分塊有序”的線性表 將表R1.n均分為b塊，前b-1塊中結(jié)點個數(shù)為s=n/b ，第b塊結(jié)點個數(shù)小于等于s；每一塊中的關(guān)鍵字不一定有序，但前一塊中的最大關(guān)鍵字必須小于后一塊中的最小關(guān)鍵字，即表是“分塊有序”的。（2） 索引表 抽取各塊中的最大關(guān)鍵字及該塊起始位置構(gòu)成一個索引表ID1.b，即： IDi(1ib)中存放第i塊的最大關(guān)鍵字及該塊在表R中的起始位置。由于表R是“分塊有序”的，所以索引表是一個遞增有序表。

2、分塊查找（block search）又稱索引順序查找。它是一種性能介于順序查找和二分查找之間的查找方法。043、實例分塊查找 下圖給出的就是滿足上述要求的存儲結(jié)構(gòu)，其中R只有15個結(jié)點，被分成3塊，每塊中有5個結(jié)點，第一塊中最大關(guān)鍵字22小于第二塊中最小關(guān)鍵字24，第二塊中最大關(guān)鍵字44小于第三塊中最小關(guān)鍵字47。 分塊查找123456789101112131415最大關(guān)鍵字值塊地址IDR224474161122121398334244382448605874472、基本思路 先在索引表中采用二分查找或順序查找，以確定待查的結(jié)點在哪一塊； 然后在已確定的塊中進行順序查找。05分塊查找4、算法分析優(yōu)缺點 分塊查找效率介于二分查找和順序查找之間，對經(jīng)常進行插入和刪除操作的表，可采用此方法，因為在表中插入或刪除記錄時，只要找到該記錄所屬的塊，就在該塊內(nèi)進行插入和刪除運算，因塊內(nèi)記錄的存放是任意的，所以插入或刪除無須移動大量記錄；分塊查找的主要代價是增加輔助存儲空間和將初始表分塊排序的運算。 平均查找長度 將含有n個元素的線性表平均分成b塊，每塊有s個元素。整個查找過程的平均查找長度是兩次查找的平均查找長度之和。以二分查找來確定塊，分塊查找成功時的平均查找長度ASLblk=ASLbn+ASLsq以順序

溫馨提示

  • 1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽，若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負責。
  • 6. 下載文件中如有侵權(quán)或不適當內(nèi)容，請與我們聯(lián)系，我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論