数据结构与算法9

第9章文件（2课时）9.6多关键字文件9.4索引顺序文件9.8应用实例9.3索引文件9.7外排序9.1文件的基本概念9.2顺序文件9.5散列文件文件是由大量具有相同性质的记录组成的集合。按记录类型不同，文件可以分为两类操作系统文件操作系统文件是一维的无结构连续字符序列，其中存储的数据按不同含义被划分为若干个字符组，每一个字符组就称为一条记录。数据库文件（数据结构主要讨论）数据库文件则是由多条具有相同结构的记录组成的集合。9.1文件的基本概念9.1文件的基本概念9.1.1文件的组成9.1.5磁盘存储器9.1.2文件的分类9.1.3文件的操作9.1.4文件的结构文件是大量性质相同的数据记录的集合，即一个文件包含一条或多条记录。记录是一个实体的所有数据项的集合，即一条记录包含一个或多个数据项。数据项（也称为字段或属性）是反映实体某一方面属性的数据表示，是文件存取最基本的操作对象。关键字，次关键字9.1文件的基本概念9.1.1文件的组成按文件中记录的信息长度定长文件：若每个记录含有相同长度的信息，则称这类记录为定长记录。由定长记录组成的文件称为定长文件。不定长文件：若每个记录含有不同长度的信息，则称这类记录为不定长记录。由不定长记录组成的文件则称为不定长文件按记录中关键字的数目单关键字文件：若文件中的记录只有一个用于唯一标识记录的主关键字，则这类文件称为单关键字文件。多关键字文件：若文件中的记录除了含有一个主关键字之外，还包含若干次关键字，则这类文件称为多关键字文件。9.1文件的基本概念9.1.2文件的分类文件检索简单查询区域查询函数查询布尔查询文件维护插入删除修改9.1文件的基本概念9.1.3文件的操作文件的结构逻辑结构：逻辑结构是指文件中各记录之间的逻辑关系（线性或非线性）。物理结构：物理结构是指文件在外存中的组织方式。文件基本的物理结构方式顺序结构索引结构散列结构链式结构。9.1文件的基本概念9.1.4文件的结构前面章节中的数据结构研究的是数据在内存中的组织方式，而文件研究的是数据在外存中的组织方式。由于内存和外存在存取速度上有着较大差异，因此，文件与其他数据结构研究的侧重点有所不同。硬盘的组成9.1文件的基本概念9.1.5磁盘存储器硬盘的读写步骤1.根据待读写数据所处的柱面，用动臂将读写磁头移动到此柱面上。2.根据待读写数据所处的扇区，用主轴带动盘面将该扇区转到读写磁头下面。3.用指定盘面上的读写磁头读写所需数据。硬盘上进行一次数据读写操作所需的时间其中，tseek为寻查时间，即将磁头定位到指定柱面所需的时间；tla为等待时间，即将磁头定位到指定扇区所需的时间；twm为传输时间，即传送一个扇区数据所需的时间。9.1文件的基本概念9.1.5磁盘存储器9.2顺序文件顺序文件是结构最简单的文件，文件中记录的物理顺序与逻辑顺序一致，即记录按其逻辑顺序依次存放在文件中。9.2顺序文件9.2.1顺序文件的分类9.2.2顺序文件的操作及实现按照记录是否有序有序顺序文件无序顺序文件。按照存储方式的不同连续顺序文件串联顺序文件9.2顺序文件9.2.1顺序文件的分类9.2顺序文件将待处理的顺序文件称为主文件，主文件按主关键字大小顺序排列对文件的插入、删除、修改等操作请求全部放在事务文件中根据事务文件中的操作对主文件进行更新生成新的主文件顺序文件批量处理步骤对事务文件按照主文件中主关键字的顺序进行排序对于修改主关键字值的操作，转为删除记录和插入记录两个操作顺序读出主文件与事务文件中的记录，比较它们的主关键字值9.2.2顺序文件的操作及实现9.2顺序文件例如，对表9-1的学生文件依次进行如下操作：插入一条新的记录（20110006，李延，1201091990XXXXXXXX，612，通信工程）；删除学生记录（20110005，严丽，3000141989XXXXXXXX，635，通信工程）；将学生记录（20110007，吴红，3000311990XXXXXXXX，603，计算机应用）改为（20110007，吴红，3000311990XXXXXXXX，603，通信工程）。以字符“I”、“D”和“U”分别表示插入、删除和修改操作，则生成的事务文件如表9-2所示9.2顺序文件9.2.2顺序文件的操作及实现9.2顺序文件9.2.2顺序文件的操作及实现9.2顺序文件9.2.2顺序文件的操作及实现9.3索引文件顺序文件的检索、插入、删除、修改等操作都需要频繁地进行外存的读/写操作，主要适用于批量处理的情况。对于要求高实时性的应用，则应采用非顺序文件的组织形式。本节所要介绍的索引文件是在顺序文件的基础上增加了一个索引表。9.3索引文件9.3.1顺序文件的分类9.3.2顺序文件的操作及实现9.3索引文件索引文件由主文件和索引表两部分构成。主文件中存储了所有的数据记录索引表是一个映射关系表，存储了逻辑记录和物理记录的一一对应关系索引表中各索引项严格按主关键字有序排列，而主文件中的各记录可以有序也可以无序。若主文件中各记录也是按主关键字有序排列的，则称该索引文件为索引顺序文件；否则，若主文件中各记录是无序的，则称该索引文件为索引非顺序文件。（简称为索引文件）9.3.1顺序文件的分类9.3索引文件图9-2为一个索引非顺序文件示例。主文件以学号为主关键字，但没有按主关键字有序排列。索引表按主关键字升序排列。9.3.1顺序文件的分类9.3索引文件9.3.2顺序文件的操作及实现检索操作将索引表读入内存中，并根据检索条件在索引表中进行查找。若索引表中存在匹配项，则根据匹配索引项中存储的物理地址直接读取外存上的相应记录；若索引表中不存在该记录，则说明外存上也不存在该记录、不需做外存访问操作。插入、删除和修改操作插入：在索引文件中插入一条新的记录时，直接将该记录写入主文件的末尾，并在索引表中插入索引项；删除：在删除一条记录时，只需在索引表中删除对应的索引项即可；修改：在修改记录时，需将修改后的记录写入主文件的末尾，并同时对索引表进行修改、将索引项中的物理地址改为修改后记录的存储地址。9.3索引文件9.3.2顺序文件的操作及实现

例如，对于图9-2所示的索引非顺序文件，依次进行如下操作：1）插入一条新记录（0018，陈功，23）；2）将学号为0008的记录删除；3）将学号为0076的记录的年龄改为24。上述操作之后可以得到图9-3所示的索引非顺序文件。9.3索引文件9.3.2顺序文件的操作及实现9.4散列文件散列文件是利用哈希存储方式进行组织的文件，也称为直接存取文件。与哈希表的不同之处在于：散列文件中的记录是以桶为单位成组存放的。若一个桶能存放m条记录，则当桶中已有m条同义词记录时，再存放第m+1条同义词记录就会发生“溢出”。在散列文件中，通常采用拉链法作为冲突处理方法，即将第m+1条同义词记录存放到另一个称为“溢出桶”的桶中，相应地，将存放前m条同义词记录的桶称为“基桶”，在基桶中设置一个指向溢出桶的指针。9.5多关键字文件多关键字文件就是指既包含主关键字索引、又包含多个次关键字索引的文件。本节介绍两种多关键字文件的组织方法多重表文件倒排文件9.5.1多重表文件9.5.2倒排文件9.5多关键字文件9.5多关键字文件9.5.1多重表文件9.5多关键字文件9.5.2倒排文件9.6外排序在做文件排序时就需进行多次内/外存之间的数据交换，这种基于外存的排序技术就称为外排序。如果待排序的记录数量很大，以至于不能将它们一次性读入到内存中进行处理。在对文件中的记录进行排序时，通常是把记录分成若干部分，每次只将一部分记录调入内存进行处理。9.6.1归并排序的思想9.6.2归并排序的实现9.6外排序归并排序处理步骤记录分段处理：将文件中的记录按照可用内存大小划分为若干段，依次将每段记录读入到内存中对其进行内部排序，并将排序结果输出到子文件中。这样可以生成多个有序的子文件（即文件内的记录是有序的），通常称经过排序后的段为初始归并段。文件归并处理：对上一步得到的初始归并段加以归并，直至将多段中的记录归并为一个有序文件为止。9.6外排序9.6.1归并排序的思想9.6外排序9.6.1归并排序的思想9.6外排序9.6.1归并排序的思想9.6外排序9.6.2归并排序的实现为了减少K个记录比较所占用的时间，一般利用败者树来实现K路归并败者树的结构如下：是一棵有K个叶子结点的完全二叉树；K个叶子结点分别存储从K个初始归并段中读取出来的K个待比较的记录；分支结点存储两个记录比较后败者（即具有较大关键字值的记录）所在叶子结点的序号，胜者参与更高一层的比较；通常在败者树的根结点之上再加一个结点来保存胜者（即当前K个记录中具有最小关键字值的记录）所在叶子结点的序号。9.6外排序9.6.2归并排序的实现9.6外排序失败树重构举例9.6.2归并排序的实现9.6外排序失败树重构举例9.6.2归并排序的实现9.6外排序败者树的创建9.6.2归并排序的实现9.6外排序败者树的创建9.6.2归并排序的实现9.7应用实例编写程序，以学号作为主关键字对学生文件进行外排序。