中國科大數(shù)據(jù)結構-資料下載頁
2025-02-27 14:41本頁面
【正文】 620， 110， 384， 355。桶的容量為 m＝ 3，桶數(shù) b＝ 7。用除留余數(shù)法作哈希函數(shù) H(key)＝ key MOD 7。由此得到的直接存取文件如下圖所示。 桶編號 基桶 溢出桶 0 063 184 1 589 505 008 330 2 3 269 164 4 109 620 5 278 215 810 110 355 6 930 083 384 直接存取文件示例 1229 中國科大《數(shù)據(jù)結構》 直接存取文件 (散列文件 ) ? 查找操作 查找過程 ：首先根據(jù)給定值求得哈希地址（即基桶號），將基桶的記錄讀入內(nèi)存進行順序查找，若找到關鍵字等于給定值的記錄，則檢索成功；否則，若基桶內(nèi)沒有填滿記錄或其指針域為空，則文件內(nèi)不含有待查記錄；否則根據(jù)指針域的值的指示將溢出桶的記錄讀入內(nèi)存繼續(xù)進行順序查找，直至檢索成功或不成功。因此，總的查找時間為： T = a (te + ti) 其中： a為存取桶數(shù)的期望值（相當于哈希表中的平均查找長度），對鏈地址處理溢出來說， a = 1 + α/2； te為存取一個桶所需的時間；ti為在內(nèi)存中順序查找一個記錄所需的時間。 α為裝載因子，在散列文件中： α= n/(bm) n為文件的記錄數(shù)， b為桶數(shù)， m為桶的容量。 1230 中國科大《數(shù)據(jù)結構》 直接存取文件 (散列文件 ) ? 刪除操作 在直接存取文件中刪除記錄時，僅需對被刪記錄作一標記即可。 ? 直接存取文件的特點 ? 優(yōu)點：文件隨機存放，記錄不需進行排序；插入、刪除方便，存取速度快，不需要索引區(qū)，節(jié)省存儲空間。 ? 缺點：不能進行順序存取，只能按關鍵字隨機存取，且詢問方式限于簡單詢問，并且在經(jīng)過多次的 插入、刪除之后，也可能造成文件結構不合理，即溢出桶滿而基桶內(nèi)多數(shù)為被刪除的記錄。此時亦需重組文件。 1231 中國科大《數(shù)據(jù)結構》 多關鍵字文件 在對文件進行檢索操作是，不僅對主關鍵字進行簡單詢問，還經(jīng)常需要對關鍵字進行其他類型的詢問檢索。 多重表文件 ? 特點：多重表文件（ Multilist File）的特點是： 1. 記錄按主關鍵字的順序構成一個串聯(lián)文件，并建立主關鍵字的索引（稱為主索引）； 2. 對每一個次關鍵字項建立次關鍵字索引（稱為次索引），所有具有同一次關鍵字的記 錄構成一個鏈表。 主索引為非稠密索引，次索引為稠密索引。每個索引項包括次關鍵字、頭指針和鏈表長度。 1232 中國科大《數(shù)據(jù)結構》 多關鍵字文件 ? 例子：例如，下圖 a所示為一個多重表文件。對工號非稠密索引分成三個子鏈表，其索引如圖 b所示，索引項中的主關鍵字為各組中關鍵字的最大值。職稱和專業(yè)是兩個次關鍵字項，其索引分別如圖 c和 d所示，具有相同次關鍵字值 的記錄鏈接在同一鏈表中。有 了這些次關鍵字索引，根據(jù)關 鍵字值找到鏈表頭指針，然后 從頭指針出發(fā)可列出鏈表中所 有記錄。 1233 中國科大《數(shù)據(jù)結構》 多關鍵字文件 倒排文件 倒排文件和多重表文件的區(qū)別在于次關鍵字索引的結構不同。通常稱倒排文件中的次關鍵字索引為倒排表，具有相同次關鍵字的記錄之間不設指針相鏈，而在倒排表中該次關鍵字的一項中存放這些記錄的物理記錄號。如圖所示為上例中的倒排表。 1234 中國科大《數(shù)據(jù)結構》 多關鍵字文件 在倒排文件中可以較快地檢索記錄，特別是在檢索多個次關鍵字的情況時。在處理各種次關鍵字的查詢時，只要在次關鍵字索引中檢索出有關的指針集合，再對這些指針集合進行交、并、差等邏輯運算，就可求出符合查詢條件的記錄指針，然后按指針到外存去存取記錄。 在插入和刪除記錄時，倒排表也要進行相應修改；需要移動索引項中記錄號以保持其有序排列。若數(shù)據(jù)文件是索引順序文件（如ISAM文件），倒排表中應存放記錄的主關鍵字而不是物理記錄號。 倒排文件的缺點是維護困難。同一倒排表中各項長度不同，不同倒排表的長度也不同，這些都給倒排文件的維護帶來一定的困難，而且倒排表需要額外存儲空間。 1235 中國科大《數(shù)據(jù)結構》 習題 ? 本章習題參見教師網(wǎng)頁： 1236 中國科大《數(shù)據(jù)結構》 演講完畢，謝謝觀看！
范文總結相關推薦
鄂ICP備17016276號-1