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