熱點推薦:
您现在的位置: 電腦知識網 >> 編程 >> 數據結構 >> 正文

數據結構之分塊查找

2013-11-15 15:33:15  來源: 數據結構 

  分塊查找(Blocking Search)又稱為索引順序查找其性能介順序查找和二分查找之間

  分塊查找的基本思想分塊查找要求把順序表分成若干塊每一塊中的鍵值存儲順序是任意的但要求分塊有序即前一塊中的最大鍵值小於後一塊中最小鍵值即塊間結點有序塊內結點任意另外還需要建立一個索引表索引表中的每一項對應順序表的一塊索引項由關鍵字域和鏈域組成關鍵字域存放對應塊內結點的最大鍵值鏈域存放對應塊首結點的位置索引表中的索引項是按鍵值遞增順序存放

  若以二分查找來確定塊則分塊查找成功時的平均查找長度為lg(n/s+)+s/若以順序查找確定塊則分塊查找成功時的平均查找長度為(s+s+n)/(s)
  分塊查找算法的效率介於順序查找和二分查找之間
  線性表查找方法的比較


From:http://tw.wingwit.com/Article/program/sjjg/201311/23596.html
    推薦文章
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.