數(shù)據(jù)結構8第8章：文件

1、第第8 8章章 文文 件件 Slide. 8 - 12015秋秋數(shù)據(jù)結構與算法數(shù)據(jù)結構與算法8.1 文件及文件操作文件及文件操作8.2 文件組織文件組織第第8章章 文文 件件第第8 8章章 文文 件件 Slide. 8 - 22015秋秋數(shù)據(jù)結構與算法數(shù)據(jù)結構與算法8.1 文件及文件操作文件及文件操作1、相關概念、相關概念文件是用于表示駐留在外存儲器中的數(shù)據(jù)，是同性質文件是用于表示駐留在外存儲器中的數(shù)據(jù)，是同性質記錄的有序集合。記錄的有序集合。記錄記錄學號姓名性別年齡數(shù)學語文物理其它A003孫 喆B008陳 益C009史碩剛D010許藝洪E011張 爽F(xiàn)012沈 鍵關鍵字：關鍵字： 主關鍵字主

2、關鍵字 次關鍵字次關鍵字第第8 8章章 文文 件件 Slide. 8 - 32015秋秋數(shù)據(jù)結構與算法數(shù)據(jù)結構與算法文件的邏輯結構和物理結構文件的邏輯結構和物理結構邏輯結構：呈現(xiàn)給用戶，描述記錄間的邏輯關系邏輯結構：呈現(xiàn)給用戶，描述記錄間的邏輯關系物理結構：存儲結構，記錄在存儲器中的組織，連續(xù)，鏈式等物理結構：存儲結構，記錄在存儲器中的組織，連續(xù)，鏈式等2、文件操作、文件操作操作操作 ： INSERT， 在文件中插入記錄在文件中插入記錄 DELETE， 從文件中刪除記錄從文件中刪除記錄 MODIFY， 修改滿足條件的記錄修改滿足條件的記錄 RETRIEVE，檢索滿足條件的記錄，檢索滿足條件的記

3、錄檢索方式：實時檢索方式：實時 or 成批成批更新方式：實時更新方式：實時 or 成批成批文件更新文件檢索第第8 8章章 文文 件件 Slide. 8 - 42015秋秋數(shù)據(jù)結構與算法數(shù)據(jù)結構與算法查詢方式：查詢方式： Q1簡單查詢：查詢單個關鍵字值等于給定值的記錄簡單查詢：查詢單個關鍵字值等于給定值的記錄 如：性別如：性別=男男 Q2范圍查詢：查詢單個關鍵字值滿足指定范圍的記錄范圍查詢：查詢單個關鍵字值滿足指定范圍的記錄 如：數(shù)學如：數(shù)學80 Q3函數(shù)查詢：對于某個關鍵字的函數(shù)，查詢滿足指定函數(shù)值的函數(shù)查詢：對于某個關鍵字的函數(shù)，查詢滿足指定函數(shù)值的 記錄記錄 如：物理如：物理平均分平均分

4、Q4布爾查詢：對布爾查詢：對Q1Q2Q3進行組合的查詢，查詢滿足布爾表達進行組合的查詢，查詢滿足布爾表達 式的記錄式的記錄 如：如：(性別性別=男男)and(年齡年齡=18) 布爾運算：布爾運算：and or not第第8 8章章 文文 件件 Slide. 8 - 52015秋秋數(shù)據(jù)結構與算法數(shù)據(jù)結構與算法Main() FILE *fp;Source file .c輸入數(shù)據(jù)原始數(shù)據(jù)磁盤磁盤/帶文件帶文件處理結果輸出數(shù)據(jù)第第8 8章章 文文 件件 Slide. 8 - 62015秋秋數(shù)據(jù)結構與算法數(shù)據(jù)結構與算法文件指針文件指針文件結構體文件結構體FILEFILEtypedef struct in

5、t _fd; /文件號文件號 int _cleft; /緩沖區(qū)中剩下的字符數(shù)緩沖區(qū)中剩下的字符數(shù) int _mode; /文件操作方式文件操作方式 char *_next; /文件當前讀寫位置文件當前讀寫位置 char *_buff; /文件緩沖區(qū)位置文件緩沖區(qū)位置FILE;文件信息用系統(tǒng)定義的名為文件信息用系統(tǒng)定義的名為FILEFILE的結構體描述的結構體描述Stdio.hFILE *變量名；變量名；第第8 8章章 文文 件件 Slide. 8 - 72015秋秋數(shù)據(jù)結構與算法數(shù)據(jù)結構與算法Int fclose(FILE *fp)FILE FILE * *fopenfopen(char (c

6、har * *name,char name,char * *mode)mode) fread(buffer,size,count,fp); fwrite(buffer,size,count,fp);標準輸入標準輸入-鍵盤鍵盤 stdinstdin標準輸出標準輸出-顯示器顯示器 stdoutstdout標準出錯輸出標準出錯輸出-顯示器顯示器 stderrstderr第第8 8章章 文文 件件 Slide. 8 - 82015秋秋數(shù)據(jù)結構與算法數(shù)據(jù)結構與算法#include stdio.h main( int argc,char *argv ) FILE *in,*out; if(argc!=3)

7、 printf(You forgot to enter a filenamen); exit(0); if(in = fopen(argv1,r) = = NULL) printf(Cannot open infile!n); exit(0); if(out = fopen(argv2,w) = = NULL) printf(Cannot open outfile!n); exit(0); while(!feof(in) fputc(fgetc(in),out); fclose(in); fclose(out);？第第8 8章章 文文 件件 Slide. 8 - 92015秋秋數(shù)據(jù)結構與算法數(shù)

8、據(jù)結構與算法按用途 系統(tǒng)文件、庫文件、用戶文件 按保護級別 可執(zhí)行文件、只讀文件、讀寫文件 按信息流向 輸入文件、輸出文件、輸入輸出文件 按存放時限 臨時文件、永久文件、檔案文件 按設備類型 磁盤文件、磁帶文件、卡片文件、打印文件 按文件組織結構 邏輯文件(流式文件、記錄式文件)、物理文件（順序文件、鏈接文件、索引文件） 文件分類 FAT：File Allocation Table NTFS：NewTechnology Files SyatemWinFS：Windows Future Storage第第8 8章章 文文 件件 Slide. 8 - 102015秋秋數(shù)據(jù)結構與算法數(shù)據(jù)結構與算法操

9、作系統(tǒng)操作系統(tǒng)FAT12Fat16Fat32NTFSNTFS5.0WinFSDOS3.0以下是支持末來的操作系統(tǒng)Dos3.0是DOS4.0是Windows 3.X是Windows 95是Windows 95 OSR2是是Windows 98是是Windows 98 SE是Windows Me是是Windows NT是是Windows 2000是是是是Windows XP是是是是Windows 2003是是是是Unix 是 Linux 是是(軟盤引導) 文件大小限制文件大小限制最大支持8M最大支持2G不能大于4G單文件最大64GB單文件最大2TB第第8 8章章 文文 件件 Slide. 8 -

10、112015秋秋數(shù)據(jù)結構與算法數(shù)據(jù)結構與算法8.2 文件組織文件組織常用的文件組織方式 順序方式 索引方式 散列方式 鏈接方式另外還有 ISAM VSAM UNIX問題：文件駐留外存，數(shù)據(jù)量大 每次讀入一個物理快文件操作復雜為使操作方便，要研究設計 有效的存儲機制第第8 8章章 文文 件件 Slide. 8 - 122015秋秋數(shù)據(jù)結構與算法數(shù)據(jù)結構與算法8.2.1 順序方式順序方式文件的各個記錄文件的各個記錄按邏輯順序按邏輯順序存放在外存的連續(xù)區(qū)內存放在外存的連續(xù)區(qū)內記錄的順序往往是記錄的順序往往是按主關鍵字的大小排列按主關鍵字的大小排列的的適合于適合于Q1型查詢型查詢，且檢索與更新是成批進

11、行的，且檢索與更新是成批進行的適合磁帶或磁盤適合磁帶或磁盤第第8 8章章 文文 件件 Slide. 8 - 132015秋秋數(shù)據(jù)結構與算法數(shù)據(jù)結構與算法串聯(lián)文件串聯(lián)文件：物理記錄之間的次序由指針相鏈接表示的順序文件。：物理記錄之間的次序由指針相鏈接表示的順序文件。（1）定義）定義 順序文件順序文件（Sequential FileSequential File）：）： 是記錄按其在文件中的邏輯順是記錄按其在文件中的邏輯順序依次進入存儲介質而建立的，即順序文件中物理記錄的順序和邏輯序依次進入存儲介質而建立的，即順序文件中物理記錄的順序和邏輯記錄的順序是一致的。記錄的順序是一致的。 連續(xù)文件連續(xù)文件

12、：次序相繼的兩個物理記錄在存儲介質上的存儲位置是相：次序相繼的兩個物理記錄在存儲介質上的存儲位置是相鄰的順序文件。鄰的順序文件。（2 2）特點）特點 順序文件是根據(jù)記錄的序號或記錄的相對位置來進行存取的文件組順序文件是根據(jù)記錄的序號或記錄的相對位置來進行存取的文件組織方式。它的特點是：織方式。它的特點是： 存取第存取第i i個記錄，必須先搜索在它之前的個記錄，必須先搜索在它之前的i-1個記錄。個記錄。 插入記錄時要批量移動記錄，或加在文件的末尾，插入記錄時要批量移動記錄，或加在文件的末尾，“溢出區(qū)溢出區(qū)”。 刪除記錄時要批量移動記錄，或標記記錄刪除記錄時要批量移動記錄，或標記記錄 若要更新文件

13、中的某個記錄，則必須將整個文件進行復制。若要更新文件中的某個記錄，則必須將整個文件進行復制。（3）磁帶上順序文件的批處理）磁帶上順序文件的批處理 主文件主文件：待修改的原始文件。：待修改的原始文件。 事務文件事務文件：所有的修改請求集中構成的一個文件。：所有的修改請求集中構成的一個文件。第第8 8章章 文文 件件 Slide. 8 - 142015秋秋數(shù)據(jù)結構與算法數(shù)據(jù)結構與算法磁帶文件的批處理過程：磁帶文件的批處理過程： 首先對事務文件進行排序，然后將主文件和事務文件歸并成一個首先對事務文件進行排序，然后將主文件和事務文件歸并成一個新的主文件。新的主文件。 其中，主文件、事務文件和新的主文件

14、分別存放在一臺磁帶上。主其中，主文件、事務文件和新的主文件分別存放在一臺磁帶上。主文件按關鍵字自小至大（或自大至?。╉樞蛴行?，事務文件必須和主文件文件按關鍵字自小至大（或自大至小）順序有序，事務文件必須和主文件有相同的有序關系。有相同的有序關系。事務文件舉例：新調來35人調走28人漲工資343人事務總數(shù)406件文件修改程序事務文件職工老文件職工新文件第第8 8章章 文文 件件 Slide. 8 - 152015秋秋數(shù)據(jù)結構與算法數(shù)據(jù)結構與算法 終端終端事務事務文件文件排序排序有序的事務文件有序的事務文件主文件主文件新主文件新主文件第第8 8章章 文文 件件 Slide. 8 - 162015秋

15、秋數(shù)據(jù)結構與算法數(shù)據(jù)結構與算法 在歸并的過程中，順序讀出主文件與事務文件中的記錄，比較它們的在歸并的過程中，順序讀出主文件與事務文件中的記錄，比較它們的關鍵字并分別進行處理。對于關鍵字不匹配的主文件中的記錄，則直接將關鍵字并分別進行處理。對于關鍵字不匹配的主文件中的記錄，則直接將其寫入新主文件中。其寫入新主文件中?！案母摹焙秃汀皠h除刪除”記錄時，要求其關鍵字相匹配。記錄時，要求其關鍵字相匹配。“刪去刪去”不用寫入，而不用寫入，而“更改更改”則要將更改后的新記錄寫入新主文。則要將更改后的新記錄寫入新主文?！安宀迦肴搿睍r不要求關鍵字相匹配，可直接將事務文件上要插入的記錄寫到新主時不要求關鍵字相

16、匹配，可直接將事務文件上要插入的記錄寫到新主文件的適當位置。文件的適當位置。 算法實現(xiàn)：算法實現(xiàn)： 算法中：算法中： f f 主文件；主文件；g g 事務文件；事務文件；h h 新主文件。新主文件。 它們都按關鍵字遞增排序。它們都按關鍵字遞增排序。 事務文件的每個記錄中，增設一個代碼以示修改要求，事務文件的每個記錄中，增設一個代碼以示修改要求， 其中：其中：“I I”表示插入；表示插入；“D D”表示刪去；表示刪去；“U U”表示更改。表示更改。 void MergeFile (FILE *f, FILE *g, FILE *h) /由按關鍵字遞增有序的非空順序文件由按關鍵字遞增有序的非空順序

17、文件f和和g歸并得到新文件歸并得到新文件h，三個文件均已打開，三個文件均已打開，/其中，其中，f和和g為只讀文件，文件中各附加一個最大關鍵字記錄，且為只讀文件，文件中各附加一個最大關鍵字記錄，且g文件中對該記文件中對該記/錄的操作為插入。錄的操作為插入。 h為只寫文件。為只寫文件。fread (*fr, sizeof(RcdType), 1, f);fread (*gr, sizeof(RcdType), 1, g);第第8 8章章 文文 件件 Slide. 8 - 172015秋秋數(shù)據(jù)結構與算法數(shù)據(jù)結構與算法while (!feof (f) | | !feof (g) switch case

18、 fr.key gr.key: /插入,函數(shù)P把gr加工為h的結構 fwrite ( P(gr), sizeof(RcdType), 1, h ); if (!feof (g)fread ( *gr, sizeof(RcdType), 1, g ); break;第第8 8章章 文文 件件 Slide. 8 - 182015秋秋數(shù)據(jù)結構與算法數(shù)據(jù)結構與算法 case gr.code = = U & fr.key = = gr.key: /更改”舊”主文件中記錄fwrite ( Q(fr, gr), sizeof(RcdType), 1, h );/函數(shù)Q將fr和gr歸并成一個h結構的記

19、錄if (!feof (f) fread ( *fr, sizeof(RcdType), 1, f );if (!feof (g) fread ( *gr, sizeof(RcdType), 1, g );break; default ERROR();/其他均為出錯情況 / switch / while / MergeFile分析批處理算法的時間：分析批處理算法的時間： 假設主文件包含假設主文件包含n個記錄，事務文件包含個記錄，事務文件包含m個記錄。一般情況下，事個記錄。一般情況下，事務文件較小，可以進行內部排序，則時間復雜度為務文件較小，可以進行內部排序，則時間復雜度為O(m*logm)。內

20、部歸并。內部歸并的時間復雜度為的時間復雜度為O(n+m)，則總的內部處理時間為，則總的內部處理時間為O(m*logm+n)。 第第8 8章章 文文 件件 Slide. 8 - 192015秋秋數(shù)據(jù)結構與算法數(shù)據(jù)結構與算法(4)磁盤上順序文件的批處理磁盤上順序文件的批處理 磁盤上順序文件的批處理和磁帶文件類似，只是當修改項中沒有插磁盤上順序文件的批處理和磁帶文件類似，只是當修改項中沒有插入，且更新時不增加記錄的長度時，可以不建立新的主文件，而直接修入，且更新時不增加記錄的長度時，可以不建立新的主文件，而直接修改原來的主文件即可。顯然，磁盤文件的批處理可以在一個磁盤上進行。改原來的主文件即可。顯然

21、，磁盤文件的批處理可以在一個磁盤上進行。 假設所有的輸入假設所有的輸入/輸出都是通過緩沖區(qū)進行的，并假設緩沖區(qū)大小為輸出都是通過緩沖區(qū)進行的，并假設緩沖區(qū)大小為 s（個記錄），則整個批處理過程中讀（個記錄），則整個批處理過程中讀/寫外存的次數(shù)為寫外存的次數(shù)為 ：snmsm*2*2n：主文件包含的記錄數(shù)，m：事務文件包含記錄數(shù)第第8 8章章 文文 件件 Slide. 8 - 202015秋秋數(shù)據(jù)結構與算法數(shù)據(jù)結構與算法8.2.2 索引方式索引方式“索引索引” 指的是記錄的關鍵字值與記錄駐留在外存的地址組成數(shù)對的指的是記錄的關鍵字值與記錄駐留在外存的地址組成數(shù)對的集合。每個數(shù)對稱為一個索引項。集合

22、。每個數(shù)對稱為一個索引項。索引文件在存儲器上分兩區(qū)：索引文件在存儲器上分兩區(qū)： 索引區(qū)索引區(qū) 和和 數(shù)據(jù)區(qū)數(shù)據(jù)區(qū)查找記錄：分兩步進行查找記錄：分兩步進行刪除記錄：只刪除索引刪除記錄：只刪除索引插入記錄：先存數(shù)據(jù)，然后登記索引并重新排序插入記錄：先存數(shù)據(jù)，然后登記索引并重新排序建立文件：按數(shù)據(jù)存入的先后順序建立索引，最后索引排序建立文件：按數(shù)據(jù)存入的先后順序建立索引，最后索引排序示例：序號姓名記錄內容記錄位置柱面號盤面號1An Cai11人事檔案示意文件人事檔案示意文件柱面的最大關鍵字柱面號Cai Long1柱面索引柱面索引盤面的最大關鍵字盤面號Pi Hong1盤面索引盤面索引第第8 8章章 文

23、文 件件 Slide. 8 - 212015秋秋數(shù)據(jù)結構與算法數(shù)據(jù)結構與算法 非稠密索引非稠密索引：數(shù)據(jù)文件中的記錄按關鍵字順序有序，則可對一組：數(shù)據(jù)文件中的記錄按關鍵字順序有序，則可對一組記錄建立一個索引項，這種索引表稱為非稠密索引。記錄建立一個索引項，這種索引表稱為非稠密索引。（1 1）基本術語）基本術語 索引表索引表：除了文件本身（稱做數(shù)據(jù)區(qū)）之外，另建立的一張指示邏：除了文件本身（稱做數(shù)據(jù)區(qū)）之外，另建立的一張指示邏輯記錄和物理記錄之間一一對應關系的表。輯記錄和物理記錄之間一一對應關系的表。 索引項索引項：索引表中的每一項。總是按關鍵字（或邏輯記錄號）順：索引表中的每一項?？偸前搓P鍵字

24、（或邏輯記錄號）順序排列。序排列。索引文件索引文件：包括文件數(shù)據(jù)區(qū)和索引表兩大部分的文件。：包括文件數(shù)據(jù)區(qū)和索引表兩大部分的文件。索引順序文件索引順序文件：數(shù)據(jù)區(qū)中的記錄也按關鍵字順序排列的文件。：數(shù)據(jù)區(qū)中的記錄也按關鍵字順序排列的文件。 通常為索引順序文件建立通常為索引順序文件建立“溢出區(qū)溢出區(qū)”索引非順序文件索引非順序文件：數(shù)據(jù)區(qū)中的記錄不按關鍵字順序排列的文件。：數(shù)據(jù)區(qū)中的記錄不按關鍵字順序排列的文件。 稠密索引稠密索引：由于數(shù)據(jù)文件中記錄不按關鍵字順序排列，則必須對每個：由于數(shù)據(jù)文件中記錄不按關鍵字順序排列，則必須對每個記錄都建立一個索引項，如此建立的索引表稱為稠密索引。記錄都建立一個

25、索引項，如此建立的索引表稱為稠密索引。第第8 8章章 文文 件件 Slide. 8 - 222015秋秋數(shù)據(jù)結構與算法數(shù)據(jù)結構與算法 在記錄輸入建立數(shù)據(jù)區(qū)的同時建立一個索引表，表中的索引項按記在記錄輸入建立數(shù)據(jù)區(qū)的同時建立一個索引表，表中的索引項按記錄輸入的先后次序排列，待全部記錄輸入完畢后再對索引表進行排序。錄輸入的先后次序排列，待全部記錄輸入完畢后再對索引表進行排序。（2 2）索引表的生成）索引表的生成索引表是由系統(tǒng)程序自動生成的。索引表是由系統(tǒng)程序自動生成的。（3 3）索引文件的檢索）索引文件的檢索檢索方式：直接存取或按關鍵字（進行簡單詢問）存取。檢索方式：直接存取或按關鍵字（進行簡單詢

26、問）存取。 檢索過程：首先，查找索引表，若索引表上存在該記錄，則根據(jù)索引項檢索過程：首先，查找索引表，若索引表上存在該記錄，則根據(jù)索引項的指示讀取外存上該記錄的指示讀取外存上該記錄; ;否則說明外存上不存在該記錄，也就不需要訪否則說明外存上不存在該記錄，也就不需要訪問外存。問外存。 由于索引項的長度比記錄小得多，則通?？蓪⑺饕硪淮巫x入內存，由于索引項的長度比記錄小得多，則通?？蓪⑺饕硪淮巫x入內存，由此在索引文件中進行檢索只訪問外存兩次，即一次讀索引，一次讀記錄。由此在索引文件中進行檢索只訪問外存兩次，即一次讀索引，一次讀記錄。并且由于索引表是有序的，則查找索引表時可用折半查找法。并且由于索

27、引表是有序的，則查找索引表時可用折半查找法。第第8 8章章 文文 件件 Slide. 8 - 232015秋秋數(shù)據(jù)結構與算法數(shù)據(jù)結構與算法（4 4）索引文件的修改）索引文件的修改刪除操作：刪除一個記錄時，僅需刪去相應的索引項；刪除操作：刪除一個記錄時，僅需刪去相應的索引項； 插入操作：插入一個記錄時，應將記錄置于數(shù)據(jù)區(qū)的末尾，同時再插入操作：插入一個記錄時，應將記錄置于數(shù)據(jù)區(qū)的末尾，同時再 索引表中插入索引項；索引表中插入索引項；更新操作：更新記錄時，應將更新后的記錄置于數(shù)據(jù)區(qū)末尾，同時更新操作：更新記錄時，應將更新后的記錄置于數(shù)據(jù)區(qū)末尾，同時 修改索引表中相應的索引項。修改索引表中相應的索引

28、項。（5 5）多級索引）多級索引 查找表：對索引表建立的索引。查找表：對索引表建立的索引。通常最高可有四級索引：通常最高可有四級索引： 第三查找表第二查找表查找表索引表數(shù)據(jù)文件 上述的多級索引是一種靜態(tài)索引，各級索引均為順序表結構。其結構上述的多級索引是一種靜態(tài)索引，各級索引均為順序表結構。其結構簡單，但修改很不方便，每次修改都要重組索引。簡單，但修改很不方便，每次修改都要重組索引。 因此，當數(shù)據(jù)文件在使用過程中記錄變動較多時，應采用動態(tài)索引。因此，當數(shù)據(jù)文件在使用過程中記錄變動較多時，應采用動態(tài)索引。如如,二叉排序樹（或二叉平衡樹）、二叉排序樹（或二叉平衡樹）、B-樹以及鍵樹。樹以及鍵樹。第

29、第8 8章章 文文 件件 Slide. 8 - 242015秋秋數(shù)據(jù)結構與算法數(shù)據(jù)結構與算法多級索引結構形成 m 路搜索樹數(shù)據(jù)區(qū)數(shù)據(jù)區(qū)一級索引一級索引二級索引二級索引三級索引三級索引四級索引四級索引n多級索引結構形成多級索引結構形成 m m 叉樹。叉樹。每個分支結點表示一個索引塊，每個分支結點表示一個索引塊，最多存放最多存放 m m 個索引項個索引項每個索引項給出各子樹結點每個索引項給出各子樹結點 ( (較低一級索引塊較低一級索引塊) ) 的最大關鍵碼的最大關鍵碼和結點地址。和結點地址。葉結點中各索引項給出在數(shù)據(jù)表中存放的記錄的關鍵碼和存放葉結點中各索引項給出在數(shù)據(jù)表中存放的記錄的關鍵碼和存放

30、地址。地址。n這種這種m m叉樹用來作為多級索引，就是叉樹用來作為多級索引，就是 m m 路搜索樹路搜索樹第第8 8章章 文文 件件 Slide. 8 - 252015秋秋數(shù)據(jù)結構與算法數(shù)據(jù)結構與算法8.2.3 散列方式散列方式用散列（用散列（HASH）法組織的文件。特點是用一個散列函數(shù)）法組織的文件。特點是用一個散列函數(shù)H(key)，將關鍵字將關鍵字key映射為記錄的地址，即映射為記錄的地址，即: 記錄地址記錄地址 = HASH(key) 基本步驟基本步驟:確定記錄數(shù)確定記錄數(shù)存儲單位（桶）記錄數(shù)存儲單位（桶）記錄數(shù)確定桶數(shù)確定桶數(shù)設計設計HASH(key)函數(shù)函數(shù)（1）定義）定義 直接存取

31、文件直接存取文件指的是利用哈希（指的是利用哈希（Hash）法進行組織的文件。它類似）法進行組織的文件。它類似于哈希表，既根據(jù)文件中關鍵字的特點設計一種哈希函數(shù)和處理沖突的于哈希表，既根據(jù)文件中關鍵字的特點設計一種哈希函數(shù)和處理沖突的方法將記錄散列到存儲設備上，故又稱方法將記錄散列到存儲設備上，故又稱散列文件散列文件。 與哈希表不同，磁盤上的文件記錄通常是成組存放的。與哈希表不同，磁盤上的文件記錄通常是成組存放的。又稱 直接存取文件第第8 8章章 文文 件件 Slide. 8 - 262015秋秋數(shù)據(jù)結構與算法數(shù)據(jù)結構與算法（2）溢出處理）溢出處理 若干個記錄組成一個存儲單位，在散列文件中，這個

32、存儲單位叫做若干個記錄組成一個存儲單位，在散列文件中，這個存儲單位叫做桶（桶（Bucket）。 假若一個桶能存放假若一個桶能存放m個記錄，個記錄，m個同義詞的記錄可以存放在同一地址個同義詞的記錄可以存放在同一地址的桶中，而當?shù)诘耐爸?，而當?shù)趍1個同義詞出現(xiàn)時才發(fā)生個同義詞出現(xiàn)時才發(fā)生“溢出溢出”。解決溢出：鏈地址法解決溢出：鏈地址法 當發(fā)生當發(fā)生“溢出溢出”時，需要將第時，需要將第m1個同義詞存放到另一個桶中，通個同義詞存放到另一個桶中，通常稱此桶為常稱此桶為“溢出桶溢出桶”；相對地，稱前；相對地，稱前m個同義詞存放的桶為個同義詞存放的桶為“基桶基桶”。 溢出桶和基桶大小相同，相互之間用指針相

33、鏈接。當在基桶中沒有溢出桶和基桶大小相同，相互之間用指針相鏈接。當在基桶中沒有待查記錄時，就順指針所指到溢出桶中進行查找。因此，希望同一散列待查記錄時，就順指針所指到溢出桶中進行查找。因此，希望同一散列地址的溢出桶和基桶在磁盤上的物理位置不要相距太遠，最好在同一柱地址的溢出桶和基桶在磁盤上的物理位置不要相距太遠，最好在同一柱面上。面上。第第8 8章章 文文 件件 Slide. 8 - 272015秋秋數(shù)據(jù)結構與算法數(shù)據(jù)結構與算法（3）圖形表示）圖形表示 例如，某一文件有例如，某一文件有18個記錄，其關鍵字分別為個記錄，其關鍵字分別為278，109，063，930，589，184，505，269

34、，008，083，164，215，330，810，620，110，384，355。桶的容量為。桶的容量為m3，桶數(shù)，桶數(shù)b7。用除留余數(shù)法作哈希函數(shù)。用除留余數(shù)法作哈希函數(shù)H(key)key MOD 7。由此得到的直接存取文件如圖所示。由此得到的直接存取文件如圖所示。桶編號桶編號 基桶基桶 溢出桶溢出桶0 063 1841 589 505 008 33023 269 1644 109 6205 278 215 810 110 3556 930 083 384直接存取文件示例直接存取文件示例第第8 8章章 文文 件件 Slide. 8 - 282015秋秋數(shù)據(jù)結構與算法數(shù)據(jù)結構與算法其中：其中：

35、a為存取桶數(shù)的期望值（相當于哈希表中的平均查找長度），對為存取桶數(shù)的期望值（相當于哈希表中的平均查找長度），對鏈地址處理溢出來說，鏈地址處理溢出來說，a = 1 + /2；te為存取一個桶所需的時間；為存取一個桶所需的時間；ti為在為在內存中順序查找一個記錄所需的時間。內存中順序查找一個記錄所需的時間。（4）查找操作）查找操作 查找過程：首先根據(jù)給定值求得哈希地址（即基桶號），將基桶的記查找過程：首先根據(jù)給定值求得哈希地址（即基桶號），將基桶的記錄讀入內存進行順序查找，若找到關鍵字等于給定值的記錄，則檢索成功；錄讀入內存進行順序查找，若找到關鍵字等于給定值的記錄，則檢索成功；否則，若基桶內沒有

36、填滿記錄或其指針域為空，則文件內不含有待查記錄；否則，若基桶內沒有填滿記錄或其指針域為空，則文件內不含有待查記錄；否則根據(jù)指針域的值的指示將溢出桶的記錄讀入內存繼續(xù)進行順序查找，否則根據(jù)指針域的值的指示將溢出桶的記錄讀入內存繼續(xù)進行順序查找，直至檢索成功或不成功。因此，總的查找時間為：直至檢索成功或不成功。因此，總的查找時間為：T = a (te + ti)為裝載因子，在散列文件中：為裝載因子，在散列文件中： bmn其中：其中：n為文件的記錄數(shù)，為文件的記錄數(shù)，b為桶數(shù)，為桶數(shù)，m為桶的容量。為桶的容量。 （5）刪除操作）刪除操作 在直接存取文件中刪除記錄時，僅需對被刪記錄作一標記即可。在直接

37、存取文件中刪除記錄時，僅需對被刪記錄作一標記即可。第第8 8章章 文文 件件 Slide. 8 - 292015秋秋數(shù)據(jù)結構與算法數(shù)據(jù)結構與算法（6）直接存取文件的特點）直接存取文件的特點 優(yōu)點：優(yōu)點：文件隨機存放，記錄不需進行排序；插入、刪除方便，存取速文件隨機存放，記錄不需進行排序；插入、刪除方便，存取速度快，不需要索引區(qū)，節(jié)省存儲空間。度快，不需要索引區(qū)，節(jié)省存儲空間。 缺點：缺點：不能進行順序存取，只能按關鍵字隨機存取，且詢問方式限于不能進行順序存取，只能按關鍵字隨機存取，且詢問方式限于簡單詢問，并且在經過多次的插入、刪除之后，也可能造成文件結構不合簡單詢問，并且在經過多次的插入、刪除

38、之后，也可能造成文件結構不合理，即溢出桶滿而基桶內多數(shù)為被刪除的記錄。此時亦需重組文件。理，即溢出桶滿而基桶內多數(shù)為被刪除的記錄。此時亦需重組文件。最大學號最大學號204060記錄記錄B記錄記錄C記錄記錄A記錄記錄D記錄記錄F記錄記錄E改進方法：改進方法：索引鏈接文件，將鏈表分拆成多個較多的小鏈表8.2.4 鏈接方式文件和多重鏈表文字鏈接方式文件和多重鏈表文字 把文件中的關鍵字按照主關鍵字的某種次序用鏈接字連接起來，整個文件對應一個鏈表。在記錄中保存鏈接。特點：特點：順序查找，速度較慢。第第8 8章章 文文 件件 Slide. 8 - 302015秋秋數(shù)據(jù)結構與算法數(shù)據(jù)結構與算法多關鍵字文件多

39、關鍵字文件 特點：在對文件進行檢索操作時，不僅對主關鍵字進行簡單詢問，還特點：在對文件進行檢索操作時，不僅對主關鍵字進行簡單詢問，還經常需要對關鍵字進行其他類型的詢問檢索。經常需要對關鍵字進行其他類型的詢問檢索。 1、多重表文件、多重表文件 多重表文件（多重表文件（Multilist File）的特點是：）的特點是：記錄按主關鍵字的順序構成一個串聯(lián)文件，建立主關鍵字的索引記錄按主關鍵字的順序構成一個串聯(lián)文件，建立主關鍵字的索引 （主索引）；（主索引）；對每一個次關鍵字項建立次關鍵字索引（次索引），所有具有同一次對每一個次關鍵字項建立次關鍵字索引（次索引），所有具有同一次 關鍵字的記關鍵字的記

40、錄構成一個鏈表。錄構成一個鏈表。 主索引為非稠密索引，次索引為稠密索引。每個索引項包括次關鍵字、主索引為非稠密索引，次索引為稠密索引。每個索引項包括次關鍵字、頭指針和鏈表長度。頭指針和鏈表長度。第第8 8章章 文文 件件 Slide. 8 - 312015秋秋數(shù)據(jù)結構與算法數(shù)據(jù)結構與算法數(shù)據(jù)文件：一個多重表數(shù)據(jù)文件：一個多重表其中，其中，學號學號為主關鍵字，為主關鍵字， 記錄按學號順記錄按學號順序鏈接，為了查找方便，分成序鏈接，為了查找方便，分成3個子鏈表，個子鏈表，其索引如圖其索引如圖 (b)所示，索引項中的主關鍵所示，索引項中的主關鍵字為各子表中的字為各子表中的最大值最大值。(b)主關鍵字

41、索引主關鍵字索引紀錄號紀錄號姓名姓名學號學號專業(yè)專業(yè)已修學分已修學分選修課程選修課程01王雯王雯135002軟件軟件0241203丙丙02丁丁0302馬小雁馬小雁135103軟件軟件0739807甲甲04丙丙0303阮森阮森135204計算機計算機05436乙乙05丙丙04丁丁0504蘇明明蘇明明1353應用應用0640208甲甲06丙丙0805田永田永135406計算機計算機38402乙乙07丁丁0906楊青楊青135507應用應用0935610甲甲0707薛平平薛平平135608軟件軟件08398甲甲08乙乙08崔子健崔子健1357軟件軟件40801甲甲09丙丙09王洪王洪135810應用

42、應用1037005甲甲10丁丁10劉倩劉倩1359應用應用36409甲甲主關鍵字主關鍵字頭指針頭指針135301135705135909第第8 8章章 文文 件件 Slide. 8 - 322015秋秋數(shù)據(jù)結構與算法數(shù)據(jù)結構與算法(d) “已修學分已修學分”索引索引(e) “選修課目選修課目”索引索引圖圖 多重表文件示例多重表文件示例(c) “專業(yè)專業(yè)”索引索引 專業(yè)、已修學分和選修課專業(yè)、已修學分和選修課目為目為 3 3個次關鍵字項，具有相個次關鍵字項，具有相同次關鍵字的記錄鏈接在同一同次關鍵字的記錄鏈接在同一鏈表中。鏈表中。 它們的索引如圖它們的索引如圖(c)(c)(e)(e)所示。所示。

43、次關鍵字次關鍵字頭指針頭指針長度長度軟件軟件014計算機計算機032應用應用044次關鍵字次關鍵字頭指針頭指針長度長度甲甲027乙乙033丙丙015丁丁014次關鍵字次關鍵字頭指針頭指針長度長度350-399066400-449044第第8 8章章 文文 件件 Slide. 8 - 332015秋秋數(shù)據(jù)結構與算法數(shù)據(jù)結構與算法記錄記錄職工號職工號姓名姓名職務職務指針指針性別性別指針指針婚否婚否指針指針工資工資A29丁一丁一程序員程序員男男E婚婚E898B05王二王二維修員維修員E男男G婚婚A456C02趙忠趙忠程序員程序員G女女D婚婚B1200D38張三張三工程師工程師H女女F否否H2400E

44、31王五王五維修員維修員F男男婚婚F456F43劉玉劉玉維修員維修員女女H婚婚456G17李芳李芳程序員程序員A男男A否否D1200H46張洪張洪工程師工程師女女否否3000次關鍵字次關鍵字長度長度指針指針程序員程序員3C維修員維修員3B工程師工程師2D次關鍵字次關鍵字長度長度指針指針男男4B女女4C次關鍵字次關鍵字長度長度指針指針婚婚5C否否3G職務索引職務索引性別索引性別索引婚否索引婚否索引例：多重鏈表文件結構例：多重鏈表文件結構第第8 8章章 文文 件件 Slide. 8 - 342015秋秋數(shù)據(jù)結構與算法數(shù)據(jù)結構與算法2 2、倒排文件、倒排文件在索引中保存鏈接在索引中保存鏈接倒排文件和

45、多重表文件的區(qū)別在于次關鍵字索引的結構不同。倒排文件和多重表文件的區(qū)別在于次關鍵字索引的結構不同。通常稱倒排文件中的次關鍵字索引為倒排表，具有相同次關鍵字的記錄通常稱倒排文件中的次關鍵字索引為倒排表，具有相同次關鍵字的記錄之間不設指針鏈接，而在倒排表中該次關鍵字的一項中存放這些記錄的之間不設指針鏈接，而在倒排表中該次關鍵字的一項中存放這些記錄的物理記錄號。物理記錄號。 倒排表作索引的好處在于檢索記錄較快。倒排表作索引的好處在于檢索記錄較快。特別是對某些詢問，不用讀取特別是對某些詢問，不用讀取記錄，就可得到解答，如詢問記錄，就可得到解答，如詢問“軟件軟件”專業(yè)的學生中有否選課程專業(yè)的學生中有否選

46、課程“乙乙”的，的，則只要將則只要將“軟件軟件”索引中的記錄號和索引中的記錄號和“乙乙”索引中的記錄號作求索引中的記錄號作求“交集交集”的的運算即可。運算即可。 在插入和刪除記錄時，倒排表也要作相應的修改，值得注意的是倒排表在插入和刪除記錄時，倒排表也要作相應的修改，值得注意的是倒排表中具有同一次關鍵字的記錄號是有序排列的，則修改時要作相應移動。中具有同一次關鍵字的記錄號是有序排列的，則修改時要作相應移動。 第第8 8章章 文文 件件 Slide. 8 - 352015秋秋數(shù)據(jù)結構與算法數(shù)據(jù)結構與算法(a) 專業(yè)倒排表專業(yè)倒排表(b) 已修學分倒排表已修學分倒排表(c)(c)倒排文件索引示例倒

47、排文件索引示例選修課目倒排表選修課目倒排表例如，上例文件的倒排表例如，上例文件的倒排表紀錄號紀錄號姓名姓名學號學號專業(yè)專業(yè)已修學分已修學分選修課程選修課程01王雯王雯135002軟件軟件0241203丙丙02丁丁0302馬小雁馬小雁135103軟件軟件0739807甲甲04丙丙0303阮森阮森135204計算機計算機05436乙乙05丙丙04丁丁0504蘇明明蘇明明1353應用應用0640208甲甲06丙丙0805田永田永135406計算機計算機38402乙乙07丁丁0906楊青楊青135507應用應用0935610甲甲0707薛平平薛平平135608軟件軟件08398甲甲08乙乙08崔子健崔

48、子健1357軟件軟件40801甲甲09丙丙09王洪王洪135810應用應用1037005甲甲10丁丁10劉倩劉倩1359應用應用36409甲甲軟件軟件01,02,07,08計算機計算機03,05應用應用04,06,09,10350-39902,05,06,07,09,10400-449 01,03,04,08甲甲 02,04,06,07,08,09,10乙乙 03,05,07丙丙 01,02,03,04,08丁丁01,03,05,09第第8 8章章 文文 件件 Slide. 8 - 362015秋秋數(shù)據(jù)結構與算法數(shù)據(jù)結構與算法 若數(shù)據(jù)文件非串鏈文件，而是索引順序文件（如若數(shù)據(jù)文件非串鏈文件，而

49、是索引順序文件（如ISAMISAM文件），則倒文件），則倒排表中應存放記錄的主關鍵字而不是物理記錄號。排表中應存放記錄的主關鍵字而不是物理記錄號。 倒排文件的缺點：倒排文件的缺點：維護困難維護困難 在同一索引表中，不同的關鍵字其記錄數(shù)不同，在同一索引表中，不同的關鍵字其記錄數(shù)不同，各倒排表的長度不等，同一倒排表中各項長度也不等。各倒排表的長度不等，同一倒排表中各項長度也不等。記錄記錄職工號職工號姓名姓名職務職務性別性別婚否婚否工資工資A29丁一丁一程序員程序員男男婚婚898B05王二王二維修員維修員男男婚婚456C02趙忠趙忠程序員程序員女女婚婚1200D38張三張三工程師工程師女女否否240

50、0E31王五王五維修員維修員男男婚婚456F43劉玉劉玉維修員維修員女女婚婚456G17李芳李芳程序員程序員男男否否1200H46張洪張洪工程師工程師女女否否3000次關鍵字次關鍵字指針指針程序員程序員C G A維修員維修員B E F工程師工程師D H次關鍵字次關鍵字指針指針男男B G A E女女C D F H次關鍵字次關鍵字指針指針婚婚C B A E F否否G D H 職務索引職務索引性別索引性別索引婚否索引婚否索引例：倒排文件結構例：倒排文件結構第第8 8章章 文文 件件 Slide. 8 - 372015秋秋數(shù)據(jù)結構與算法數(shù)據(jù)結構與算法ISAM和和VSAM文件文件8.2.5 ISAM文件

51、文件（1）定義）定義 索引順序存取方法索引順序存取方法ISAM(Indexed Sequential Access Method)： 是一種專為是一種專為磁盤磁盤存取設計的文件組織方式，采用靜態(tài)索引結構存取設計的文件組織方式，采用靜態(tài)索引結構 。 由于磁盤是以盤組、柱面和磁道三級地址存取的設備，則可對磁盤上由于磁盤是以盤組、柱面和磁道三級地址存取的設備，則可對磁盤上的數(shù)據(jù)文件建立盤組、柱面和磁道三級索引。的數(shù)據(jù)文件建立盤組、柱面和磁道三級索引。磁道索引項磁道索引項 基本索引項基本索引項 關鍵字：表示該磁道中最末一個記錄的關鍵字（在此為最大關鍵字）關鍵字：表示該磁道中最末一個記錄的關鍵字（在此為

52、最大關鍵字） 指針：指示該磁道中第一個記錄的位置。指針：指示該磁道中第一個記錄的位置。 溢出索引項溢出索引項 關鍵字：表示該磁道溢出的記錄的最大關鍵字。關鍵字：表示該磁道溢出的記錄的最大關鍵字。 指針：指示在溢出區(qū)中的第一個記錄。指針：指示在溢出區(qū)中的第一個記錄。 柱面索引項柱面索引項 關鍵字：表示該柱面中最末一個記錄的關鍵字（最大關鍵字）。關鍵字：表示該柱面中最末一個記錄的關鍵字（最大關鍵字）。 指針：指示該柱面上的磁道索引位置。指針：指示該柱面上的磁道索引位置。第第8 8章章 文文 件件 Slide. 8 - 382015秋秋數(shù)據(jù)結構與算法數(shù)據(jù)結構與算法主索引主索引柱面索引柱面索引磁道索引

53、磁道索引基本數(shù)據(jù)區(qū)基本數(shù)據(jù)區(qū)ISAM文件結構示意圖文件結構示意圖第第8 8章章 文文 件件 Slide. 8 - 392015秋秋數(shù)據(jù)結構與算法數(shù)據(jù)結構與算法圖為存放一個磁盤組上的圖為存放一個磁盤組上的ISAMISAM文件。每個柱面建立一個磁道索引，每個磁道索文件。每個柱面建立一個磁道索引，每個磁道索引項由基本索引項和溢出索引項兩部分組成。引項由基本索引項和溢出索引項兩部分組成。ISAM文件結文件結構示例構示例 柱面索引存放在某個柱面上，若柱面索引較大，占多個磁道時，柱面索引存放在某個柱面上，若柱面索引較大，占多個磁道時，則可建立柱面索引的索引則可建立柱面索引的索引主索引主索引。第第8 8章章

54、 文文 件件 Slide. 8 - 402015秋秋數(shù)據(jù)結構與算法數(shù)據(jù)結構與算法（2）ISAM文件的檢索文件的檢索 在在ISAMISAM文件上檢索記錄的過程：文件上檢索記錄的過程： 先從主索引出發(fā)找到相應的柱面索引，再從柱面索引找到記錄所在先從主索引出發(fā)找到相應的柱面索引，再從柱面索引找到記錄所在柱面的磁道索引，最后從磁道索引找到記錄所在磁道的第一個記錄的位置，柱面的磁道索引，最后從磁道索引找到記錄所在磁道的第一個記錄的位置，由此出發(fā)在該磁道上進行順序查找直至找到為止；反之，若找遍該磁道而由此出發(fā)在該磁道上進行順序查找直至找到為止；反之，若找遍該磁道而不存在此記錄，則表明該文件中無此記錄。不存

55、在此記錄，則表明該文件中無此記錄。（3 3）溢出區(qū)和插入操作）溢出區(qū)和插入操作 溢出區(qū)是為插入記錄所設置的。每個柱面的基本區(qū)是順序存儲結構，溢出區(qū)是為插入記錄所設置的。每個柱面的基本區(qū)是順序存儲結構，而溢出區(qū)是鏈表結構。同一磁道溢出的記錄由指針相鏈。而溢出區(qū)是鏈表結構。同一磁道溢出的記錄由指針相鏈。 溢出區(qū)的設置方法：溢出區(qū)的設置方法：集中存放：整個文件設一個大的單一的溢出區(qū)。集中存放：整個文件設一個大的單一的溢出區(qū)。分散存放：每個柱面設一個溢出區(qū)。分散存放：每個柱面設一個溢出區(qū)。集中與分散相結合：溢出時記錄先移至每個柱面各自的溢出區(qū)，待滿集中與分散相結合：溢出時記錄先移至每個柱面各自的溢出區(qū)

56、，待滿之后再使用公共溢出區(qū)。之后再使用公共溢出區(qū)。第第8 8章章 文文 件件 Slide. 8 - 412015秋秋數(shù)據(jù)結構與算法數(shù)據(jù)結構與算法 當插人新記錄時，首先找到它應插入的磁道當插人新記錄時，首先找到它應插入的磁道,若該磁道不滿，則將新記若該磁道不滿，則將新記錄插入該磁道的適當位置上即可；若該磁道已滿，則新記錄或者插在該磁錄插入該磁道的適當位置上即可；若該磁道已滿，則新記錄或者插在該磁道上，或者直接插入到該磁道的溢出鏈表上。插入后，可能要修改磁道索道上，或者直接插入到該磁道的溢出鏈表上。插入后，可能要修改磁道索引中的基本索引項和溢出索引項。引中的基本索引項和溢出索引項。 (3)插入R8

57、3，因為808390，則83直接插入溢出區(qū)T112中，其指針指向T110，并修改磁道1的溢出鏈表，使得表頭指向T112。(2)插入R95，使得T2中的R145溢出至溢出區(qū)T111，修改相應磁道索引。 (1)插入R65，首先將1柱面1磁道中大于65的記錄順次后移，導致R90溢出至溢出區(qū)T110(11磁道0塊中)，造成磁道T1中最大關鍵字成為R80，修改磁道索引，將基本項中最大關鍵字90修改為80，將溢出項中最大關鍵字改為90，指針指向T110（溢出鏈表頭在11磁道0塊中），然后在相應位置插入R65。T11,0第第8 8章章 文文 件件 Slide. 8 - 422015秋秋數(shù)據(jù)結構與算法數(shù)據(jù)結構

58、與算法（5 5）柱面索引的位置）柱面索引的位置 假設文件占有假設文件占有n n個柱面，柱面索引在第個柱面，柱面索引在第x x柱面上，則磁頭移動距離的平柱面上，則磁頭移動距離的平均值為：均值為： )()(111nxixixiixns2) 1() 1(12nnxnxn令令0dxsd，得到，得到21nx。這就是說，柱面索引應放在數(shù)據(jù)文件的。這就是說，柱面索引應放在數(shù)據(jù)文件的中間位置的柱面上。中間位置的柱面上。（4）刪除操作）刪除操作 ISAM文件中刪除記錄，只需找到待刪除的記錄，在其存儲位置上做文件中刪除記錄，只需找到待刪除的記錄，在其存儲位置上做刪除標記即可，而不需要移動記錄或改變指針。但在經過多

59、次的增刪后，刪除標記即可，而不需要移動記錄或改變指針。但在經過多次的增刪后，文件的結構可能變得很不合理。此時，大量的記錄進入溢出區(qū)，而基本區(qū)文件的結構可能變得很不合理。此時，大量的記錄進入溢出區(qū)，而基本區(qū)中又浪費很大空間。由此，通常需要周期地整理中又浪費很大空間。由此，通常需要周期地整理ISAM文件。把記錄讀入文件。把記錄讀入內存，重新排列，復制成一個新的內存，重新排列，復制成一個新的ISAM文件，填滿基本區(qū)而空出溢出區(qū)。文件，填滿基本區(qū)而空出溢出區(qū)。第第8 8章章 文文 件件 Slide. 8 - 432015秋秋數(shù)據(jù)結構與算法數(shù)據(jù)結構與算法8.2.6 VSAM文件文件控制區(qū)域控制區(qū)域（Co

60、ntrol Range）：順序）：順序集中一個結點連同對應所有控制區(qū)間集中一個結點連同對應所有控制區(qū)間形成的一個整體。形成的一個整體。（1）定義）定義 虛擬存儲存取方法虛擬存儲存取方法VSAM（Virtual Storage Access Methed）. 它也是一種索引順序文件的組方式，采用它也是一種索引順序文件的組方式，采用B+樹作為動態(tài)索引結構。樹作為動態(tài)索引結構。 該方法利用了操作系統(tǒng)的虛擬存儲器的功能，給用戶提供方便。對該方法利用了操作系統(tǒng)的虛擬存儲器的功能，給用戶提供方便。對用戶來說，文件只有控制區(qū)間和控制區(qū)域等邏輯存儲單位，與外存儲器用戶來說，文件只有控制區(qū)間和控制區(qū)域等邏輯存儲單位，與