《數(shù)據(jù)結(jié)構(gòu)（C語言描述）（第2版）》教學(xué)課件7-03分塊查找

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

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