數(shù)據(jù)結(jié)構(gòu)與算法：第8章 文件

8.1文件及文件操作8.2文件組織第8章文件8.1文件及文件操作1、相關(guān)概念文件是用于表示駐留在外存儲器中的數(shù)據(jù)，是同性質(zhì)記錄的有序集合。記錄學號姓名性別年齡數(shù)學語文物理其它A003孫喆B008陳益C009史碩剛D010許藝洪E011張爽F(xiàn)012沈鍵關(guān)鍵字：主關(guān)鍵字次關(guān)鍵字文件的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)邏輯結(jié)構(gòu)：呈現(xiàn)給用戶，描述記錄間的邏輯關(guān)系物理結(jié)構(gòu)：存儲結(jié)構(gòu)，記錄在存儲器中的組織，連續(xù)，鏈式等2、文件操作操作●INSERT●DELETE

●MODIFY●

RETRIEVE檢索方式：實時or成批更新方式：實時or成批查詢方式：Q1:簡單查詢Q2:范圍查詢

Q3:函數(shù)查詢Q4:布爾查詢Main(){FILE*fp;……}Sourcefile.c輸入數(shù)據(jù)原始數(shù)據(jù)磁盤/帶文件處理結(jié)果輸出數(shù)據(jù)文件指針文件結(jié)構(gòu)體——FILEtypedefstruct{int_fd;//文件號

int_cleft;//緩沖區(qū)中剩下的字符數(shù)

int_mode;//文件操作方式

char*_next;//文件當前讀寫位置

char*_buff;//文件緩沖區(qū)位置}FILE;文件信息用系統(tǒng)定義的名為FILE的結(jié)構(gòu)體描述Stdio.hFILE*變量名；Intfclose(FILE*fp)FILE*fopen(char*name,char*mode)

fread(buffer,size,count,fp);

fwrite(buffer,size,count,fp);標準輸入----鍵盤

stdin標準輸出----顯示器

stdout標準出錯輸出----顯示器stderr#include"stdio.h"

main(intargc,char*argv[]){FILE*in,*out;if(argc!=3){printf("Youforgottoenterafilename\n");exit(0);}if((in=fopen(argv[1],"r"))==NULL){printf("Cannotopeninfile!\n");exit(0);}if((out=fopen(argv[2],"w"))==NULL){printf("Cannotopenoutfile!\n");exit(0);}

while(!feof(in))fputc(fgetc(in),out);fclose(in);fclose(out);}？按用途

系統(tǒng)文件、庫文件、用戶文件

按保護級別

可執(zhí)行文件、只讀文件、讀寫文件按信息流向

輸入文件、輸出文件、輸入輸出文件按存放時限

臨時文件、永久文件、檔案文件按設(shè)備類型

磁盤文件、磁帶文件、卡片文件、打印文件

按文件組織結(jié)構(gòu)邏輯文件(流式文件、記錄式文件)、物理文件（順序文件、鏈接文件、索引文件）文件分類FAT：FileAllocationTableNTFS：NewTechnologyFilesSyatemWinFS：WindowsFutureStorage操作系統(tǒng)FAT12Fat16Fat32NTFSNTFS5.0WinFSDOS3.0以下是支

持

末

來

的

操

作

系

統(tǒng)Dos3.0是DOS4.0是Windows3.X是Windows95是Windows95OSR2是是Windows98是是Windows98SE是WindowsMe是是WindowsNT是是Windows2000是是是是WindowsXP是是是是Windows2003是是是是Unix

是

Linux

是是(軟盤引導)

文件大小限制最大支持8M最大支持2G不能大于4G單文件最大64GB單文件最大2TB8.2文件組織

順序方式索引方式

ISAMVSAM

散列方式鏈接方式

UNIX8.2.1順序方式文件的各個記錄按邏輯順序存放在外存的連續(xù)區(qū)內(nèi)記錄的順序往往是按主關(guān)鍵字的大小排列的適合于Q1型查詢，且檢索與更新是成批進行的適合磁帶或磁盤串聯(lián)文件：物理記錄之間的次序由指針相鏈表示的順序文件。（1）定義

順序文件（SequentialFile）：是記錄按其在文件中的邏輯順序依次進入存儲介質(zhì)而建立的，即順序文件中物理記錄的順序和邏輯記錄的順序是一致的。

連續(xù)文件：次序相繼的兩個物理記錄在存儲介質(zhì)上的存儲位置是相鄰的順序文件。（2）特點順序文件是根據(jù)記錄的序號或記錄的相對位置來進行存取的文件組織方式。它的特點是：①存取第i個記錄，必須先搜索在它之前的i－1個記錄。②插入新的記錄時只能加在文件的末尾。③若要更新文件中的某個記錄，則必須將整個文件進行復制。（3）磁帶上順序文件的批處理主文件：待修改的原始文件。事務文件：所有的修改請求集中構(gòu)成的一個文件。磁帶文件的批處理過程：首先對事務文件進行排序，然后將主文件和事務文件歸并成一個新的主文件。

其中，主文件、事務文件和新的主文件分別存放中一臺磁帶上。主文件按關(guān)鍵字自小至大（或自大至小）順序有序，事務文件必須和主文件有相同的有序關(guān)系。職工老文件事物文件職工新文件文件修改程序磁帶文件操作實例

終端事務文件排序有序的事務文件主文件新主文件

在歸并的過程中，順序讀出主文件與事務文件中的記錄，比較它們的關(guān)鍵字并分別進行處理。對于關(guān)鍵字不匹配的主文件中的記錄，則直接將其寫入新主文件中?！案摹焙汀皠h除”記錄時，要求其關(guān)鍵字相匹配?！皠h去”不用寫入，而“更改”則要將更改后的新記錄寫入新主文?！安迦搿睍r不要求關(guān)鍵字相匹配，可直接將事務文件上要插入的記錄寫到新主文件的適當位置。算法實現(xiàn)：算法中用到的各符號的含義說明如下：

f—主文件；g—事務文件；h—新主文件。它們都按關(guān)鍵字遞增排序。事務文件的每個記錄中，增設(shè)一個代碼以示修改要求，其中：“I”表示插入；“D”表示刪去；“U”表示更改。voidMergeFile(FILE*f,FILE*g,FILE*h){//由按關(guān)鍵字遞增有序的非空順序文件f和g歸并得到新文件h，三個文件均已打開，//其中，f和g為只讀文件，文件中各附加一個最大關(guān)鍵字記錄，且g文件中對該記//錄的操作為插入。h為只寫文件。

fread(*fr,sizeof(RcdType),1,f); fread(*gr,sizeof(RcdType),1,g);while(!feof(f)||!feof(g)){switch{ casefr.key<gr.key: //復制“舊”主文件中記錄

fwrite(*fr,sizeof(RcdType),1,h); if(!feof(f)) fread(*fr,sizeof(RcdType),1,f); break; casegr.code==‘D’&&fr.key==gr.key: //刪除”舊”主文件中記錄,不復制

if(!feof(f)) fread(*fr,sizeof(RcdType),1,f); if(!feof(g)) fread(*gr,sizeof(RcdType),1,g); break; casegr.code==‘I’&&fr.key>gr.key: //插入,函數(shù)P把gr加工為h的結(jié)構(gòu)

fwrite(P(gr),sizeof(RcdType),1,h); if(!feof(g)) fread(*gr,sizeof(RcdType),1,g); break; casegr.code==‘U’&&fr.key==gr.key: //更改”舊”主文件中記錄

fwrite(Q(fr,gr),sizeof(RcdType),1,h); //函數(shù)Q將fr和gr歸并成一個h結(jié)構(gòu)的記錄

if(!feof(f)) fread(*fr,sizeof(RcdType),1,f); if(!feof(g)) fread(*gr,sizeof(RcdType),1,g); break; defaultERROR(); //其他均為出錯情況

}//switch}//while}//MergeFile分析批處理算法的時間：假設(shè)主文件包含n個記錄，事務文件包含m個記錄。一般情況下，事務文件較小，可以進行內(nèi)部排序，則時間復雜度為O(m*logm)。內(nèi)部歸并的時間復雜度為O(n＋m)，則總的內(nèi)部處理時間為O(m*logm＋n)。(4)磁盤上順序文件的批處理磁盤上順序文件的批處理和磁帶文件類似，只是當修改項中沒有插入，且更新時不增加記錄的長度時，可以不建立新的主文件，而直接修改原來的主文件即可。顯然，磁盤文件的批處理可以在一個磁盤上進行。

假設(shè)所有的輸入/輸出都是通過緩沖區(qū)進行的，并假設(shè)緩沖區(qū)大小為s（個記錄），則整個批處理過程中讀/寫外存的次數(shù)為：n：主文件包含的記錄數(shù)，m：事務文件包含記錄數(shù)8.2.2索引方式“索引”指的是記錄的關(guān)鍵字值與記錄駐留在外存的地址組成數(shù)對的集合。每個數(shù)對稱為一個索引項。索引文件在存儲器上分兩區(qū)：索引區(qū)和數(shù)據(jù)區(qū)查找記錄：分兩步進行刪除記錄：只刪除索引插入記錄：先存數(shù)據(jù)，然后登記索引并重新排序建立文件：按數(shù)據(jù)存入的先后順序建立索引，最后索引排序示例：序號姓名記錄內(nèi)容記錄位置柱面號盤面號1AnCai…11人事檔案示意文件柱面的最大關(guān)鍵字柱面號CaiLong1柱面索引盤面的最大關(guān)鍵字盤面號LiHong1盤面索引

非稠密索引：數(shù)據(jù)文件中的記錄按關(guān)鍵字順序有序，則可對一組記錄建立一個索引項，這種索引表稱為非稠密索引。（1）基本術(shù)語

索引表：除了文件本身（稱做數(shù)據(jù)區(qū)）之外，另建立的一張指示邏輯記錄和物理記錄之間一一對應關(guān)系的表。

索引項：索引表中的每一項?？偸前搓P(guān)鍵字（或邏輯記錄號）順序排列。索引文件：包括文件數(shù)據(jù)區(qū)和索引表兩大部分的文件。索引順序文件：數(shù)據(jù)區(qū)中的記錄也按關(guān)鍵字順序排列的文件。索引非順序文件：數(shù)據(jù)區(qū)中的記錄不按關(guān)鍵字順序排列的文件。

稠密索引：由于數(shù)據(jù)文件中記錄不按關(guān)鍵字順序排列，則必須對每個記錄都建立一個索引項，如此建立的索引表稱為稠密索引。

在記錄輸入建立數(shù)據(jù)區(qū)的同時建立一個索引表，表中的索引項按記錄輸入的先后次序排列，待全部記錄輸入完畢后再對索引表進行排序。（2）索引表的生成索引表是由系統(tǒng)程序自動生成的。（3）索引文件的檢索檢索方式：直接存取或按關(guān)鍵字（進行簡單詢問）存取。

檢索過程：首先，查找索引表，若索引表上存在該記錄，則根據(jù)索引項的指示讀取外存上該記錄;否則說明外存上不存在該記錄，也就不需要訪問外存。

由于索引項的長度比記錄小得多，則通?？蓪⑺饕硪淮巫x入內(nèi)存，由此再索引文件中進行檢索只訪問外存兩次，即一次讀索引，一次讀記錄。并且由于索引表是有序的，則查找索引表時可用折半查找法。（4）索引文件的修改①刪除操作：刪除一個記錄時，僅需刪去相應的索引項；②插入操作：插入一個記錄時，應將記錄置于數(shù)據(jù)區(qū)的末尾，同時再索引表中插入索引項；③更新操作：更新記錄時，應將更新后的記錄置于數(shù)據(jù)區(qū)末尾，同時修改索引表中相應的索引項。（5）多級索引查找表：對索引表建立的索引。例如，上圖的索引表需占3個物理塊的外存，每一個物理塊容納3個索引，則建立的查找表如圖12.4所示。檢索記錄時，先查找查找表，再查索引表，然后讀取記錄。最大關(guān)鍵字物理塊號171382463通常最高可有四級索引：

上述的多級索引是一種靜態(tài)索引，各級索引均為順序表結(jié)構(gòu)。其結(jié)構(gòu)簡單，但修改很不方便，每次修改都要重組索引。因此，當數(shù)據(jù)文件在使用過程中記錄變動較多時，應采用動態(tài)索引。如,二叉排序樹（或二叉平衡樹）、B-樹以及鍵樹。多級索引結(jié)構(gòu)形成m路搜索樹數(shù)據(jù)區(qū)一級索引二級索引三級索引四級索引多級索引結(jié)構(gòu)形成m叉樹。每個分支結(jié)點表示一個索引塊，最多存放m個索引項每個索引項給出各子樹結(jié)點(較低一級索引塊)的最大關(guān)鍵碼和結(jié)點地址。葉結(jié)點中各索引項給出在數(shù)據(jù)表中存放的記錄的關(guān)鍵碼和存放地址。這種m叉樹用來作為多級索引，就是m路搜索樹ISAM和VSAM文件8.2.3ISAM文件（1）定義索引順序存取方法ISAM(IndexedSequentialAccessMethod)：是一種專為磁盤存取設(shè)計的文件組織方式。

由于磁盤是以盤組、柱面和磁道三級地址存取的設(shè)備，則可對磁盤上的數(shù)據(jù)文件建立盤組、柱面和磁道三級索引。①磁道索引項基本索引項關(guān)鍵字：表示該磁道中最末一個記錄的關(guān)鍵字（在此為最大關(guān)鍵字）指針：指示該磁道中第一個記錄的位置。溢出索引項關(guān)鍵字：表示該磁道溢出的記錄的最大關(guān)鍵字。指針：指示在溢出區(qū)中的第一個記錄。②柱面索引項關(guān)鍵字：表示該柱面中最末一個記錄的關(guān)鍵字（最大關(guān)鍵字）。指針：指示該柱面上的磁道索引位置。主索引柱面索引磁道索引基本數(shù)據(jù)區(qū)ISAM文件結(jié)構(gòu)示意圖圖12.5 ISAM文件結(jié)構(gòu)示例R164

磁道索引50磁道索引柱面C1

柱面索引

主索引R14R21R45R47R50164164164330

溢出區(qū)

溢出區(qū)

溢出區(qū)柱面C2柱面C3R189R215R33011004150415041508103303843215

磁道索引

磁道索引R3843R4150

關(guān)鍵字指針關(guān)鍵字指針基本索引項溢出索引項圖為存放一個磁盤組上的ISAM文件。每個柱面建立一個磁道索引，每個磁道索引項由基本索引項和溢出索引項兩部分組成。

柱面索引存放在某個柱面上，若柱面索引較大，占多個磁道時，則可建立柱面索引的索引——主索引。（2）ISAM文件的檢索在ISAM文件上檢索記錄的過程：先從主索引出發(fā)找到相應的柱面索引，再從柱面索引找到記錄所在柱面的磁道索引，最后從磁道索引找到記錄所在磁道的第一個記錄的位置，由此出發(fā)在該磁道上進行順序查找直至找到為止；反之，若找遍該磁道而不存在此記錄，則表明該文件中無此記錄。（3）溢出區(qū)和插入操作溢出區(qū)是為插入記錄所設(shè)置的。每個柱面的基本區(qū)是順序存儲結(jié)構(gòu)，而溢出區(qū)是鏈表結(jié)構(gòu)。同一磁道溢出的記錄由指針相鏈。溢出區(qū)的設(shè)置方法：①集中存放：整個文件設(shè)一個大的單一的溢出區(qū)。②分散存放：每個柱面設(shè)一個溢出區(qū)。③集中與分散相結(jié)合：溢出時記錄先移至每個柱面各自的溢出區(qū)，待滿之后再使用公共溢出區(qū)。(a)插入前R50 R60 R70R80 R90R100 R120 R130R136 R145 T2T3T4溢出區(qū)基本區(qū)90T2’1145T3’1基本索引項溢出索引項基本索引項溢出索引項道索引其中：為插入前的某一柱面上的狀態(tài)；為插入R65時，將第2道中關(guān)鍵字大于65的記錄順次后移，且使R90溢出至溢出區(qū)的情況；為插入R65之后的狀態(tài)，此時2道的基本索引項的關(guān)鍵字改為80，且溢出索引項的關(guān)鍵字改為90，其指針指向第4道第一個記錄即R90。是相繼插入R95和R83后的狀態(tài)，R95插入在第3道的第一個記錄的位置而使R145溢出。而由于80<83<90則R83被直接插入道溢出區(qū)，作為第2道在溢出區(qū)的第一個記錄，并將它的指針指向R90的位置，同時修改第2道索引的溢出索引項的指針指向R83。（4）刪除操作

ISAM文件中刪除記錄，只需找到待刪除的記錄，在其存儲位置上做刪除標記即可，而不需要移動記錄或改變指針。但在經(jīng)過多次的增刪后，文件的結(jié)構(gòu)可能變得很不合理。此時，大量的記錄進入溢出區(qū)，而基本區(qū)中又浪費很大空間。由此，通常需要周期地整理ISAM文件。把記錄讀入內(nèi)存，重新排列，復制成一個新的ISAM文件，填滿基本區(qū)而空出溢出區(qū)。（5）柱面索引的位置假設(shè)文件占有n個柱面，柱面索引在第x柱面上，則磁頭移動距離的平均值為： 令，得到。這就是說，柱面索引應放在數(shù)據(jù)文件的中間位置的柱面上。8.2.4VSAM文件控制區(qū)域（ControlRange）：順序集中一個結(jié)點連同對應所有控制區(qū)間形成的一個整體。（1）定義虛擬存儲存取方法VSAM（VirtualStorageAccessMethed）：該方法利用了操作系統(tǒng)的虛擬存儲器的功能，給用戶提供方便。對用戶來說，文件只有控制區(qū)間和控制區(qū)域等邏輯存儲單位，與外存儲器中柱面、磁道等具體存儲單位沒有必然的聯(lián)系?？刂茀^(qū)間（ControlInterval）：它是一個I/O操作的基本單位，由一組連續(xù)的存儲單元組成。同一文件上控制區(qū)間的大小相同。每個控制區(qū)間可視為一個邏輯磁道，而每個控制區(qū)域可視為一個邏輯柱面。

在VSAM文件中，記錄可以是不定長的，則在控制區(qū)間中除了存放記錄本身以外，還有每個記錄的控制信息和整個區(qū)間的控制信息，控制區(qū)間的結(jié)構(gòu)如圖所示。在控制區(qū)間上存取一個記錄時需從控制區(qū)間的兩端出發(fā)同時向中間掃描。記 記 未利用記錄n記錄1控制空錄錄 的的的控制間的控

1n 空閑空間控制信息信息制信息

控制區(qū)間的結(jié)構(gòu)示意圖（2）刪除操作在VSAM文件中刪除記錄是，需將同一控制區(qū)間中較刪除記錄關(guān)鍵字大的記錄向前移動，把空間留給以后插入的新記錄。若整個控制區(qū)間變空，則需修改順序集中相應的索引項。

（3）插入操作

VSAM文件中沒有溢出區(qū)，解決插入的辦法是在初建文件時留有空間。每個控制區(qū)間內(nèi)不填滿記錄，在最末一個記錄和控制信息之間留有孔隙；在每個控制區(qū)域中有一些完全空的控制區(qū)間，并在順序集的索引中指明這些空區(qū)間。當插入記錄時，大多數(shù)的新記錄能插入到相應的控制區(qū)間內(nèi)，但要注意為了保持區(qū)間內(nèi)記錄的關(guān)鍵字自小至大有序，則需將區(qū)間內(nèi)關(guān)鍵字大于插入記錄關(guān)鍵字的記錄向控制信息的方向移動。若在若干記錄插入之后控制區(qū)間已滿，則在下一個記錄插入時要進行控制區(qū)間的分裂，既將近乎一半的記錄移到同一控制區(qū)域中全空的控制區(qū)間中，并修改順序集中相應索引。若控制區(qū)域中已經(jīng)沒有全空的控制區(qū)間，則要進行控制區(qū)域的分裂，此時順序集中的結(jié)點亦要分裂，由此尚需修改索引集中的結(jié)點信息。8.2.5散列方式用散列（HASH）法組織的文件。特點是用一個散列函數(shù)H(key)，將關(guān)鍵字key映射為記錄的地址，即:

記錄地址=HASH(key)基本步驟:確定記錄數(shù)存儲單位（桶）記錄數(shù)確定桶數(shù)設(shè)計HASH(key)函數(shù)（4）VASM文件的特點優(yōu)點：動態(tài)地分配和釋放存儲空間，不需要對文件進行重組，并能較快地對插入的記錄進行查找，查找一個后插入記錄的時間與查找一個原有記錄的時間是相同的。缺點：占有較多的存儲空間，一般只能保持約75％的存儲空間利用率。（1）定義

直接存取文件指的是利用雜湊（Hash）法進行組織的文件。它類似于哈希表，既根據(jù)文件中關(guān)鍵字的特點設(shè)計一種哈希函數(shù)和處理沖突的方法將記錄散列到存儲設(shè)備上，故又稱散列文件。與哈希表不同的是，對于文件來說，磁盤上的文件記錄通常是成組存放的。（2）溢出處理若干個記錄組成一個存儲單位，在散列文件中，這個存儲單位叫做桶（Bucket）。假若一個桶能存放m個記錄，這就是說，m個同義詞的記錄可以存放在同一地址的桶中，而當?shù)趍＋1個同義詞出現(xiàn)時才發(fā)生“溢出”。解決溢出：鏈地址法當發(fā)生“溢出”時，需要將第m＋1個同義詞存放到另一個桶中，通常稱此桶為“溢出桶”；相對地，稱前m個同義詞存放的桶為“基桶”。溢出桶和基桶大小相同，相互之間用指針相鏈接。當在基桶中沒有待查記錄時，就順指針所指到溢出桶中進行查找。因此，希望同一散列地址的溢出桶和基桶在磁盤上的物理位置不要相距太遠，最好在同一柱面上。（3）圖形表示例如，某一文件有18個記錄，其關(guān)鍵字分別為278，109，063，930，589，184，505，269，008，083，164，215，330，810，620，110，384，355。桶的容量為m＝3，桶數(shù)b＝7。用除留余數(shù)法作哈希函數(shù)H(key)＝keyMOD7。由此得到的直接存取文件如圖所示。桶編號 基桶 溢出桶00631841589505008 33023269164410962052782158101103556930083384直接存取文件示例其中：a為存取桶數(shù)的期望值（相當于哈希表中的平均查找長度），對鏈地址處理溢出來說，a=1+α/2；te為存取一個桶所需的時間；ti為在內(nèi)存中順序查找一個記錄所需的時間。（4）查找操作查找過程：首先根據(jù)給定值求得哈希地址（即基桶號），將基桶的記錄讀入內(nèi)存進行順序查找，若找到關(guān)鍵字等于給定值的記錄，則檢索成功；否則，若基桶內(nèi)沒有填滿記錄或其指針域為空，則文件內(nèi)不含有待查記錄；否則根據(jù)指針域的值的指示將溢出桶的記錄讀入內(nèi)存繼續(xù)進行順序查找，直至檢索成功或不成功。因此，總的查找時間為：T=a(te+ti)α為裝載因子，在散列文件中：其中：n為文件的記錄數(shù)，b為桶數(shù)，m為桶的容量。（5）刪除操作在直接存取文件中刪除記錄時，僅需對被刪記錄作一標記即可。（6）直接存取文件的特點

優(yōu)點：文件隨機存放，記錄不需進行排序；插入、刪除方便，存取速度快，不需要索引區(qū)，節(jié)省存儲空間。

缺點：不能進行順序存取，只能按關(guān)鍵字隨機存取，且詢問方式限于簡單詢問，并且在經(jīng)過多次的插入、刪除之后，也可能造成文件結(jié)構(gòu)不合理，即溢出桶滿而基桶內(nèi)多數(shù)為被刪除的記錄。此時亦需重組文件。最大學號204060記錄B記錄C記錄A記錄D記錄F記錄E多重索引:在記錄中保存鏈接索引鏈接8.2.6鏈接方式多關(guān)鍵字文件

特點：在對文件進行檢索操作是，不僅對主關(guān)鍵字進行簡單詢問，還經(jīng)常需要對關(guān)鍵字進行其他類型的詢問檢索。1、多重表文件多重表文件（MultilistFile）的特點是：①記錄按主關(guān)鍵字的順序構(gòu)成一個串聯(lián)文件，并建立主關(guān)鍵字的索引（稱為主索引）；②對每一個次關(guān)鍵字項建立次關(guān)鍵字索引（稱為次索引），所有具有同一次關(guān)鍵字的記錄構(gòu)成一個鏈表。

主索引為非稠密索引，次索引為稠密索引。每個索引項包括次關(guān)鍵字、頭指針和鏈表長度。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應用1037005甲10丁^10 劉倩1359^應用^36409甲^記錄號姓名學號專業(yè)已修學分選修課程數(shù)據(jù)文件：一個多重表其中，學號為主關(guān)鍵字，記錄按學號順序鏈接，為了查找方便，分成3個子鏈表，其索引如圖(b)所示，索引項中的主關(guān)鍵字為各子表中的最大值。(b)主關(guān)鍵字索引

主關(guān)鍵字頭指針1353 011357 051359 09次關(guān)鍵字頭指針長度350~399 06 6400~449 04 4次關(guān)鍵字頭指針長度甲 02 7乙 03 3丙 01 5丁 01 4(d)“已修學分”索引(e)“選修課目”索引圖12.10 多重表文件示例(c)“專業(yè)”索引次關(guān)鍵字頭指針長度軟件 014計算機 032應用044專業(yè)、已修學分和選修課目為3個次關(guān)鍵字項，它們的索引如圖(c)～(e)所示，具有相同次關(guān)鍵字的記錄鏈接在同一鏈表中。記錄職工號姓名職務指針性別指針婚否指針工資A29丁一程序員^男E婚E898B05王二維修員E男G婚A456C02趙忠程序員G女D婚B1200D38張三工程師H女F否H2400E31王五維修員F男^婚F456F43劉玉維修員^女H婚^456G17李芳程序員A男A否D1200H46張洪工程師^女^否^3000次關(guān)鍵字長度指針程序員3C維修員3B工程師2D次關(guān)鍵字長度指針男4B女4C次關(guān)鍵字長度指針婚5C否3G職務索引性別索引婚否索引多重鏈表文件結(jié)構(gòu)2、倒排文件——在索引中保存鏈接倒排文件和多重表文件的區(qū)別在于次關(guān)鍵字索引的結(jié)構(gòu)不同。通常稱倒排文件中的次關(guān)鍵字索引為倒排表，具有相同次關(guān)鍵字的記錄之間不設(shè)指針相鏈，而在倒排表中該次關(guān)鍵字的一項中存放這些記錄的物理記錄號。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應用1037005甲10丁^10 劉倩1359^應用^36409甲^記錄號姓名