《程序設(shè)計(jì)教程：用C++語(yǔ)言編程》PPT-文件

第11章文件煙臺(tái)大學(xué)計(jì)算機(jī)學(xué)院孟佳娜基本概念文件(File)：性質(zhì)相同的記錄的集合。文件的數(shù)據(jù)量通常很大，它被放置在外存上。

記錄：文件中可存取的基本單位。它由若干數(shù)據(jù)項(xiàng)組成。

文件的邏輯結(jié)構(gòu)：文件的邏輯結(jié)構(gòu)是呈現(xiàn)在用戶或程序員面前的數(shù)據(jù)組織形式，是用戶對(duì)數(shù)據(jù)的表示和存取方式。

文件的物理結(jié)構(gòu)：文件在外存上的存儲(chǔ)方式或組織方式，是數(shù)據(jù)的物理表示和組織。

基本概念文件組織方式：順序文件、索引文件、散列文件、多關(guān)鍵字文件。

基本操作：檢索和維護(hù)。文件的檢索：順序訪問(wèn)：訪問(wèn)下一個(gè)邏輯記錄。直接訪問(wèn)：訪問(wèn)第k個(gè)記錄。

按關(guān)鍵字訪問(wèn)：給定一個(gè)值，查詢一個(gè)或一批關(guān)鍵字與給定值相關(guān)的記錄。

順序文件

順序文件(SequentialFile)：記錄按其在文件中的邏輯順序依次進(jìn)入存儲(chǔ)介質(zhì)而建立的，即順序文件中的物理記錄的順序和邏輯記錄的順序是一致的。特點(diǎn)存取第i個(gè)記錄，必須先存取前面的第i-1個(gè)記錄；插入的新記錄只能加在文件的末尾；若要更新文件中的某個(gè)記錄，必需將整個(gè)文件進(jìn)行復(fù)制。

索引文件

索引文件：具有索引結(jié)構(gòu)的文件。最簡(jiǎn)單的索引文件包括一個(gè)主文件和一個(gè)索引表。主文件是原有數(shù)據(jù)文件的順序存儲(chǔ)或順序鏈接存儲(chǔ)（被鏈接的每個(gè)結(jié)點(diǎn)為一個(gè)頁(yè)面）的文件。索引表是在主文件的基礎(chǔ)上建立的順序表。

索引文件的種類(lèi)在索引文件中，若主文件按關(guān)鍵字有序，則稱(chēng)為索引順序文件(IndexedSequentialFile)，否則稱(chēng)為索引非順序文件(IndexedNon-SequentialFile)。

散列文件

散列文件

在外存儲(chǔ)上利用散列方式組織的文件。散列文件又稱(chēng)直接存取文件，因?yàn)樯⒘形募敲總€(gè)記錄按照關(guān)鍵字直接轉(zhuǎn)換成外存的地址后存取的，沒(méi)有其它文件那樣需要一個(gè)關(guān)鍵字的比較過(guò)程。桶是指把若干數(shù)量的存儲(chǔ)單元作為一個(gè)組并以同樣的地址加以標(biāo)識(shí)的存儲(chǔ)區(qū)，每個(gè)桶中可以放若干條記錄。桶散列文件示例一個(gè)文件有15個(gè)記錄，其關(guān)鍵字值分為：05，231，502，412，78，24，20，56，23，129，40，154，80，424，219設(shè)桶的容量m=3,桶的數(shù)量b=5,并采用除留余數(shù)法構(gòu)造散列函數(shù)，散列函數(shù)為H(key)=kMOD5

桶編號(hào)基桶溢出桶

4

05204023156

502412

7823

24129154

0123480

424219

多關(guān)鍵字文件

多關(guān)鍵字文件

多關(guān)鍵字文件在對(duì)文件進(jìn)行檢索時(shí)，除了可以對(duì)主關(guān)鍵字進(jìn)行簡(jiǎn)單詢問(wèn)，還可以對(duì)次關(guān)鍵字進(jìn)行其它類(lèi)型的詢問(wèn)檢索。多重表文件：為了方便在次關(guān)鍵字域上進(jìn)行查詢，可把文件組織成多重表文件。一般來(lái)說(shuō)，多重表文件的主文件是一個(gè)順序文件。它是將索引方法和鏈接方法相結(jié)合的一種組織方式。倒排文件：為了方便在次關(guān)