數(shù)據(jù)結(jié)構(gòu)第十二章-文件-資料下載頁(yè)
2024-08-13 16:56本頁(yè)面
【正文】 存上的 映象地址 。 類(lèi)似于哈希表的構(gòu)造方法， 根 據(jù) 文件中關(guān)鍵字的特點(diǎn)設(shè)計(jì)一種 “哈 希函數(shù)”和“處理沖突的方法”將記錄 散列到外存儲(chǔ)設(shè)備上 ，又稱(chēng)“散列文件”。 ２．哈希文件的結(jié)構(gòu) 由于記錄在外存上是成組存放的， 因此允許多個(gè)記錄映象到同一個(gè)地址 上。在此，稱(chēng)外存儲(chǔ)器中存放多個(gè)記 錄的“數(shù)據(jù)塊”為“桶”。 因此 由哈希函 數(shù)得到的映象地址為“桶地址” 。 例如：有一組關(guān)鍵字如下所列 {589， 063， 269， 505， 764， 182， 166， 330} 假設(shè)哈希函數(shù)為 key MOD 7，每個(gè)桶可以容納 3個(gè)記錄（稱(chēng)桶的容量為 3），則哈希文件如下 : 基桶 063 182 589 505 764 269 166 330 溢出桶 在哈希文件中， “沖突”和“溢出” 是不同的概念 。一般情況下，假設(shè)桶 的大小為 m，則允許哈希地址產(chǎn)生 m1 次的沖突，當(dāng)發(fā)生第 m次沖突時(shí)，才 需要進(jìn)行“沖突處理”，對(duì)散列文件而 言，通常采用鏈地址法出路沖突。為 區(qū)別起見(jiàn)， 稱(chēng)直接“散列”的數(shù)據(jù)塊為 “基桶” ，而因“溢出”存放的數(shù)據(jù)塊為 “溢出桶” 。 ３．文件的操作 ? 檢索 ： 只能進(jìn)行按關(guān)鍵字的查找 ，不能進(jìn)行順序查找。檢索時(shí)，先在基桶內(nèi)進(jìn)行查找，若不存在，則再到溢出桶中進(jìn)行查找； ? 插入 ：當(dāng)查找不成功時(shí)，將記錄插入在相應(yīng)的基桶或溢出桶內(nèi) ； ? 刪除 ： 對(duì)被刪記錄作特殊標(biāo)記 。 ４． 優(yōu)點(diǎn)： 記錄隨機(jī)存放， 不需要 進(jìn)行 排 序；插入、刪除方便，存取速 度快；節(jié)省存儲(chǔ)空間 ，不需要 索引區(qū)。 缺點(diǎn)： 不能進(jìn)行順序存取 ；在經(jīng)過(guò)多 次插入和刪除操作之后，需進(jìn) 行“ 重組文件 ”的操作。 多 關(guān) 鍵 字 文 件 一、多關(guān)鍵字文件的特點(diǎn) 除需要對(duì)主關(guān)鍵字建立“主索引” 外， 尚需對(duì)各個(gè)次關(guān)鍵字建立 “次索引”。 次索引項(xiàng)： 次關(guān)鍵字 （指向記錄的）指針 二、次索引的組織方法 ? 1． 多重鏈表文件 特點(diǎn)：將所有 具有相同次關(guān)鍵字的記錄鏈接在同一鏈表中 ，該鏈表的頭指針即為次索引項(xiàng)中“指針域”的值； ? 2 ． 倒排文件 特點(diǎn)： 將所有 具有相同次關(guān)鍵字的記錄構(gòu)成一個(gè)次索引順序表 ，此時(shí)的次索引順序表中僅存放記錄的 “ 主關(guān)鍵字 ” 或記錄的 “ 物理記錄號(hào) ” 。 次索引項(xiàng)中的 “ 指針 ” 指向相應(yīng)的次索引順序表； ? 3． 次關(guān)鍵字索引表本身的結(jié)構(gòu) 可以是 順序表 ， 也可以是 樹(shù)表 或哈希表 ， 視具體的次關(guān)鍵字的特性而定 。 本章學(xué)習(xí)要求： 熟悉各類(lèi)文件的特點(diǎn)，構(gòu)造方法以及如何實(shí)現(xiàn)檢索，插入和刪除等操作。
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號(hào)-1