数据结构与算法：第8章 文件

8.1文件及文件操作8.2文件组织第8章文件8.1文件及文件操作1、相关概念文件是用于表示驻留在外存储器中的数据，是同性质记录的有序集合。记录学号姓名性别年龄数学语文物理其它A003孙喆B008陈益C009史硕刚D010许艺洪E011张爽F012沈键关键字：主关键字次关键字文件的逻辑结构和物理结构逻辑结构：呈现给用户，描述记录间的逻辑关系物理结构：存储结构，记录在存储器中的组织，连续，链式等2、文件操作操作●INSERT●DELETE

●MODIFY●

RETRIEVE检索方式：实时or成批更新方式：实时or成批查询方式：Q1:简单查询Q2:范围查询

Q3:函数查询Q4:布尔查询Main(){FILE*fp;……}Sourcefile.c输入数据原始数据磁盘/带文件处理结果输出数据文件指针文件结构体——FILEtypedefstruct{int_fd;//文件号

int_cleft;//缓冲区中剩下的字符数

int_mode;//文件操作方式

char*_next;//文件当前读写位置

char*_buff;//文件缓冲区位置}FILE;文件信息用系统定义的名为FILE的结构体描述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);}？按用途

系统文件、库文件、用户文件

按保护级别

可执行文件、只读文件、读写文件按信息流向

输入文件、输出文件、输入输出文件按存放时限

临时文件、永久文件、档案文件按设备类型

磁盘文件、磁带文件、卡片文件、打印文件

按文件组织结构逻辑文件(流式文件、记录式文件)、物理文件（顺序文件、链接文件、索引文件）文件分类FAT：FileAllocationTableNTFS：NewTechnologyFilesSyatemWinFS：WindowsFutureStorage操作系统FAT12Fat16Fat32NTFSNTFS5.0WinFSDOS3.0以下是支

持

末

来

的

操

作

系

统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顺序方式文件的各个记录按逻辑顺序存放在外存的连续区内记录的顺序往往是按主关键字的大小排列的适合于Q1型查询，且检索与更新是成批进行的适合磁带或磁盘串联文件：物理记录之间的次序由指针相链表示的顺序文件。（1）定义

顺序文件（SequentialFile）：是记录按其在文件中的逻辑顺序依次进入存储介质而建立的，即顺序文件中物理记录的顺序和逻辑记录的顺序是一致的。

连续文件：次序相继的两个物理记录在存储介质上的存储位置是相邻的顺序文件。（2）特点顺序文件是根据记录的序号或记录的相对位置来进行存取的文件组织方式。它的特点是：①存取第i个记录，必须先搜索在它之前的i－1个记录。②插入新的记录时只能加在文件的末尾。③若要更新文件中的某个记录，则必须将整个文件进行复制。（3）磁带上顺序文件的批处理主文件：待修改的原始文件。事务文件：所有的修改请求集中构成的一个文件。磁带文件的批处理过程：首先对事务文件进行排序，然后将主文件和事务文件归并成一个新的主文件。

其中，主文件、事务文件和新的主文件分别存放中一台磁带上。主文件按关键字自小至大（或自大至小）顺序有序，事务文件必须和主文件有相同的有序关系。职工老文件事物文件职工新文件文件修改程序磁带文件操作实例

终端事务文件排序有序的事务文件主文件新主文件

在归并的过程中，顺序读出主文件与事务文件中的记录，比较它们的关键字并分别进行处理。对于关键字不匹配的主文件中的记录，则直接将其写入新主文件中。“更改”和“删除”记录时，要求其关键字相匹配。“删去”不用写入，而“更改”则要将更改后的新记录写入新主文。“插入”时不要求关键字相匹配，可直接将事务文件上要插入的记录写到新主文件的适当位置。算法实现：算法中用到的各符号的含义说明如下：

f—主文件；g—事务文件；h—新主文件。它们都按关键字递增排序。事务文件的每个记录中，增设一个代码以示修改要求，其中：“I”表示插入；“D”表示删去；“U”表示更改。voidMergeFile(FILE*f,FILE*g,FILE*h){//由按关键字递增有序的非空顺序文件f和g归并得到新文件h，三个文件均已打开，//其中，f和g为只读文件，文件中各附加一个最大关键字记录，且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: //插入,函数P把gr加工为h的结构

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); //函数Q将fr和gr归并成一个h结构的记录

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

}//switch}//while}//MergeFile分析批处理算法的时间：假设主文件包含n个记录，事务文件包含m个记录。一般情况下，事务文件较小，可以进行内部排序，则时间复杂度为O(m*logm)。内部归并的时间复杂度为O(n＋m)，则总的内部处理时间为O(m*logm＋n)。(4)磁盘上顺序文件的批处理磁盘上顺序文件的批处理和磁带文件类似，只是当修改项中没有插入，且更新时不增加记录的长度时，可以不建立新的主文件，而直接修改原来的主文件即可。显然，磁盘文件的批处理可以在一个磁盘上进行。

假设所有的输入/输出都是通过缓冲区进行的，并假设缓冲区大小为s（个记录），则整个批处理过程中读/写外存的次数为：n：主文件包含的记录数，m：事务文件包含记录数8.2.2索引方式“索引”指的是记录的关键字值与记录驻留在外存的地址组成数对的集合。每个数对称为一个索引项。索引文件在存储器上分两区：索引区和数据区查找记录：分两步进行删除记录：只删除索引插入记录：先存数据，然后登记索引并重新排序建立文件：按数据存入的先后顺序建立索引，最后索引排序示例：序号姓名记录内容记录位置柱面号盘面号1AnCai…11人事档案示意文件柱面的最大关键字柱面号CaiLong1柱面索引盘面的最大关键字盘面号LiHong1盘面索引

非稠密索引：数据文件中的记录按关键字顺序有序，则可对一组记录建立一个索引项，这种索引表称为非稠密索引。（1）基本术语

索引表：除了文件本身（称做数据区）之外，另建立的一张指示逻辑记录和物理记录之间一一对应关系的表。

索引项：索引表中的每一项。总是按关键字（或逻辑记录号）顺序排列。索引文件：包括文件数据区和索引表两大部分的文件。索引顺序文件：数据区中的记录也按关键字顺序排列的文件。索引非顺序文件：数据区中的记录不按关键字顺序排列的文件。

稠密索引：由于数据文件中记录不按关键字顺序排列，则必须对每个记录都建立一个索引项，如此建立的索引表称为稠密索引。

在记录输入建立数据区的同时建立一个索引表，表中的索引项按记录输入的先后次序排列，待全部记录输入完毕后再对索引表进行排序。（2）索引表的生成索引表是由系统程序自动生成的。（3）索引文件的检索检索方式：直接存取或按关键字（进行简单询问）存取。

检索过程：首先，查找索引表，若索引表上存在该记录，则根据索引项的指示读取外存上该记录;否则说明外存上不存在该记录，也就不需要访问外存。

由于索引项的长度比记录小得多，则通常可将索引表一次读入内存，由此再索引文件中进行检索只访问外存两次，即一次读索引，一次读记录。并且由于索引表是有序的，则查找索引表时可用折半查找法。（4）索引文件的修改①删除操作：删除一个记录时，仅需删去相应的索引项；②插入操作：插入一个记录时，应将记录置于数据区的末尾，同时再索引表中插入索引项；③更新操作：更新记录时，应将更新后的记录置于数据区末尾，同时修改索引表中相应的索引项。（5）多级索引查找表：对索引表建立的索引。例如，上图的索引表需占3个物理块的外存，每一个物理块容纳3个索引，则建立的查找表如图12.4所示。检索记录时，先查找查找表，再查索引表，然后读取记录。最大关键字物理块号171382463通常最高可有四级索引：

上述的多级索引是一种静态索引，各级索引均为顺序表结构。其结构简单，但修改很不方便，每次修改都要重组索引。因此，当数据文件在使用过程中记录变动较多时，应采用动态索引。如,二叉排序树（或二叉平衡树）、B-树以及键树。多级索引结构形成m路搜索树数据区一级索引二级索引三级索引四级索引多级索引结构形成m叉树。每个分支结点表示一个索引块，最多存放m个索引项每个索引项给出各子树结点(较低一级索引块)的最大关键码和结点地址。叶结点中各索引项给出在数据表中存放的记录的关键码和存放地址。这种m叉树用来作为多级索引，就是m路搜索树ISAM和VSAM文件8.2.3ISAM文件（1）定义索引顺序存取方法ISAM(IndexedSequentialAccessMethod)：是一种专为磁盘存取设计的文件组织方式。

由于磁盘是以盘组、柱面和磁道三级地址存取的设备，则可对磁盘上的数据文件建立盘组、柱面和磁道三级索引。①磁道索引项基本索引项关键字：表示该磁道中最末一个记录的关键字（在此为最大关键字）指针：指示该磁道中第一个记录的位置。溢出索引项关键字：表示该磁道溢出的记录的最大关键字。指针：指示在溢出区中的第一个记录。②柱面索引项关键字：表示该柱面中最末一个记录的关键字（最大关键字）。指针：指示该柱面上的磁道索引位置。主索引柱面索引磁道索引基本数据区ISAM文件结构示意图图12.5 ISAM文件结构示例R164

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

柱面索引

主索引R14R21R45R47R50164164164330

溢出区

溢出区

溢出区柱面C2柱面C3R189R215R33011004150415041508103303843215

磁道索引

磁道索引R3843R4150

关键字指针关键字指针基本索引项溢出索引项图为存放一个磁盘组上的ISAM文件。每个柱面建立一个磁道索引，每个磁道索引项由基本索引项和溢出索引项两部分组成。

柱面索引存放在某个柱面上，若柱面索引较大，占多个磁道时，则可建立柱面索引的索引——主索引。（2）ISAM文件的检索在ISAM文件上检索记录的过程：先从主索引出发找到相应的柱面索引，再从柱面索引找到记录所在柱面的磁道索引，最后从磁道索引找到记录所在磁道的第一个记录的位置，由此出发在该磁道上进行顺序查找直至找到为止；反之，若找遍该磁道而不存在此记录，则表明该文件中无此记录。（3）溢出区和插入操作溢出区是为插入记录所设置的。每个柱面的基本区是顺序存储结构，而溢出区是链表结构。同一磁道溢出的记录由指针相链。溢出区的设置方法：①集中存放：整个文件设一个大的单一的溢出区。②分散存放：每个柱面设一个溢出区。③集中与分散相结合：溢出时记录先移至每个柱面各自的溢出区，待满之后再使用公共溢出区。(a)插入前R50 R60 R70R80 R90R100 R120 R130R136 R145 T2T3T4溢出区基本区90T2’1145T3’1基本索引项溢出索引项基本索引项溢出索引项道索引其中：为插入前的某一柱面上的状态；为插入R65时，将第2道中关键字大于65的记录顺次后移，且使R90溢出至溢出区的情况；为插入R65之后的状态，此时2道的基本索引项的关键字改为80，且溢出索引项的关键字改为90，其指针指向第4道第一个记录即R90。是相继插入R95和R83后的状态，R95插入在第3道的第一个记录的位置而使R145溢出。而由于80<83<90则R83被直接插入道溢出区，作为第2道在溢出区的第一个记录，并将它的指针指向R90的位置，同时修改第2道索引的溢出索引项的指针指向R83。（4）删除操作

ISAM文件中删除记录，只需找到待删除的记录，在其存储位置上做删除标记即可，而不需要移动记录或改变指针。但在经过多次的增删后，文件的结构可能变得很不合理。此时，大量的记录进入溢出区，而基本区中又浪费很大空间。由此，通常需要周期地整理ISAM文件。把记录读入内存，重新排列，复制成一个新的ISAM文件，填满基本区而空出溢出区。（5）柱面索引的位置假设文件占有n个柱面，柱面索引在第x柱面上，则磁头移动距离的平均值为： 令，得到。这就是说，柱面索引应放在数据文件的中间位置的柱面上。8.2.4VSAM文件控制区域（ControlRange）：顺序集中一个结点连同对应所有控制区间形成的一个整体。（1）定义虚拟存储存取方法VSAM（VirtualStorageAccessMethed）：该方法利用了操作系统的虚拟存储器的功能，给用户提供方便。对用户来说，文件只有控制区间和控制区域等逻辑存储单位，与外存储器中柱面、磁道等具体存储单位没有必然的联系。控制区间（ControlInterval）：它是一个I/O操作的基本单位，由一组连续的存储单元组成。同一文件上控制区间的大小相同。每个控制区间可视为一个逻辑磁道，而每个控制区域可视为一个逻辑柱面。

在VSAM文件中，记录可以是不定长的，则在控制区间中除了存放记录本身以外，还有每个记录的控制信息和整个区间的控制信息，控制区间的结构如图所示。在控制区间上存取一个记录时需从控制区间的两端出发同时向中间扫描。记 记 未利用记录n记录1控制空录录 的的的控制间的控

1n 空闲空间控制信息信息制信息

控制区间的结构示意图（2）删除操作在VSAM文件中删除记录是，需将同一控制区间中较删除记录关键字大的记录向前移动，把空间留给以后插入的新记录。若整个控制区间变空，则需修改顺序集中相应的索引项。

（3）插入操作

VSAM文件中没有溢出区，解决插入的办法是在初建文件时留有空间。每个控制区间内不填满记录，在最末一个记录和控制信息之间留有孔隙；在每个控制区域中有一些完全空的控制区间，并在顺序集的索引中指明这些空区间。当插入记录时，大多数的新记录能插入到相应的控制区间内，但要注意为了保持区间内记录的关键字自小至大有序，则需将区间内关键字大于插入记录关键字的记录向控制信息的方向移动。若在若干记录插入之后控制区间已满，则在下一个记录插入时要进行控制区间的分裂，既将近乎一半的记录移到同一控制区域中全空的控制区间中，并修改顺序集中相应索引。若控制区域中已经没有全空的控制区间，则要进行控制区域的分裂，此时顺序集中的结点亦要分裂，由此尚需修改索引集中的结点信息。8.2.5散列方式用散列（HASH）法组织的文件。特点是用一个散列函数H(key)，将关键字key映射为记录的地址，即:

记录地址=HASH(key)基本步骤:确定记录数存储单位（桶）记录数确定桶数设计HASH(key)函数（4）VASM文件的特点优点：动态地分配和释放存储空间，不需要对文件进行重组，并能较快地对插入的记录进行查找，查找一个后插入记录的时间与查找一个原有记录的时间是相同的。缺点：占有较多的存储空间，一般只能保持约75％的存储空间利用率。（1）定义

直接存取文件指的是利用杂凑（Hash）法进行组织的文件。它类似于哈希表，既根据文件中关键字的特点设计一种哈希函数和处理冲突的方法将记录散列到存储设备上，故又称散列文件。与哈希表不同的是，对于文件来说，磁盘上的文件记录通常是成组存放的。（2）溢出处理若干个记录组成一个存储单位，在散列文件中，这个存储单位叫做桶（Bucket）。假若一个桶能存放m个记录，这就是说，m个同义词的记录可以存放在同一地址的桶中，而当第m＋1个同义词出现时才发生“溢出”。解决溢出：链地址法当发生“溢出”时，需要将第m＋1个同义词存放到另一个桶中，通常称此桶为“溢出桶”；相对地，称前m个同义词存放的桶为“基桶”。溢出桶和基桶大小相同，相互之间用指针相链接。当在基桶中没有待查记录时，就顺指针所指到溢出桶中进行查找。因此，希望同一散列地址的溢出桶和基桶在磁盘上的物理位置不要相距太远，最好在同一柱面上。（3）图形表示例如，某一文件有18个记录，其关键字分别为278，109，063，930，589，184，505，269，008，083，164，215，330，810，620，110，384，355。桶的容量为m＝3，桶数b＝7。用除留余数法作哈希函数H(key)＝keyMOD7。由此得到的直接存取文件如图所示。桶编号 基桶 溢出桶00631841589505008 33023269164410962052782158101103556930083384直接存取文件示例其中：a为存取桶数的期望值（相当于哈希表中的平均查找长度），对链地址处理溢出来说，a=1+α/2；te为存取一个桶所需的时间；ti为在内存中顺序查找一个记录所需的时间。（4）查找操作查找过程：首先根据给定值求得哈希地址（即基桶号），将基桶的记录读入内存进行顺序查找，若找到关键字等于给定值的记录，则检索成功；否则，若基桶内没有填满记录或其指针域为空，则文件内不含有待查记录；否则根据指针域的值的指示将溢出桶的记录读入内存继续进行顺序查找，直至检索成功或不成功。因此，总的查找时间为：T=a(te+ti)α为装载因子，在散列文件中：其中：n为文件的记录数，b为桶数，m为桶的容量。（5）删除操作在直接存取文件中删除记录时，仅需对被删记录作一标记即可。（6）直接存取文件的特点

优点：文件随机存放，记录不需进行排序；插入、删除方便，存取速度快，不需要索引区，节省存储空间。

缺点：不能进行顺序存取，只能按关键字随机存取，且询问方式限于简单询问，并且在经过多次的插入、删除之后，也可能造成文件结构不合理，即溢出桶满而基桶内多数为被删除的记录。此时亦需重组文件。最大学号204060记录B记录C记录A记录D记录F记录E多重索引:在记录中保存链接索引链接8.2.6链接方式多关键字文件

特点：在对文件进行检索操作是，不仅对主关键字进行简单询问，还经常需要对关键字进行其他类型的询问检索。1、多重表文件多重表文件（MultilistFile）的特点是：①记录按主关键字的顺序构成一个串联文件，并建立主关键字的索引（称为主索引）；②对每一个次关键字项建立次关键字索引（称为次索引），所有具有同一次关键字的记录构成一个链表。

主索引为非稠密索引，次索引为稠密索引。每个索引项包括次关键字、头指针和链表长度。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甲^记录号姓名学号专业已修学分选修课程数据文件：一个多重表其中，学号为主关键字，记录按学号顺序链接，为了查找方便，分成3个子链表，其索引如图(b)所示，索引项中的主关键字为各子表中的最大值。(b)主关键字索引

主关键字头指针1353 011357 051359 09次关键字头指针长度350~399 06 6400~449 04 4次关键字头指针长度甲 02 7乙 03 3丙 01 5丁 01 4(d)“已修学分”索引(e)“选修课目”索引图12.10 多重表文件示例(c)“专业”索引次关键字头指针长度软件 014计算机 032应用044专业、已修学分和选修课目为3个次关键字项，它们的索引如图(c)～(e)所示，具有相同次关键字的记录链接在同一链表中。记录职工号姓名职务指针性别指针婚否指针工资A29丁一程序员^男E婚E898B05王二维修员E男G婚A456C02赵忠程序员G女D婚B1200D38张三工程师H女F否H2400E31王五维修员F男^婚F456F43刘玉维修员^女H婚^456G17李芳程序员A男A否D1200H46张洪工程师^女^否^3000次关键字长度指针程序员3C维修员3B工程师2D次关键字长度指针男4B女4C次关键字长度指针婚5C否3G职务索引性别索引婚否索引多重链表文件结构2、倒排文件——在索引中保存链接倒排文件和多重表文件的区别在于次关键字索引的结构不同。通常称倒排文件中的次关键字索引为倒排表，具有相同次关键字的记录之间不设指针相链，而在倒排表中该次关键字的一项中存放这些记录的物理记录号。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甲^记录号姓名