数据结构与算法9讲解.ppt

9.6 多关键字文件;;9.1 文件的基本概念;;按文件中记录的信息长度 定长文件：若每个记录含有相同长度的信息，则称这类记录为定长记录。由定长记录组成的文件称为定长文件。 不定长文件 ：若每个记录含有不同长度的信息，则称这类记录为不定长记录。由不定长记录组成的文件则称为不定长文件 按记录中关键字的数目 单关键字文件：若文件中的记录只有一个用于唯一标识记录的主关键字，则这类文件称为单关键字文件。 多关键字文件 ：若文件中的记录除了含有一个主关键字之外，还包含若干次关键字，则这类文件称为多关键字文件。 ;;;前面章节中的数据结构研究的是数据在内存中的组织方式，而文件研究的是数据在外存中的组织方式。 由于内存和外存在存取速度上有着较大差异，因此，文件与其他数据结构研究的侧重点有所不同。 硬盘的组成 ;硬盘的读写步骤 1.根据待读写数据所处的柱面，用动臂将读写磁头移动到此柱面上。 2.根据待读写数据所处的扇区，用主轴带动盘面将该扇区转到读写磁头下面。 3.用指定盘面上的读写磁头读写所需数据。 硬盘上进行一次数据读写操作所需的时间 其中，tseek为寻查时间，即将磁头定位到指定柱面所需的时间；tla为等待时间，即将磁头定位到指定扇区所需的时间；twm为传输时间，即传送一个扇区数据所需的时间。;9.2 顺序文件;9.2 顺序文件;;9.2 顺序文件;9.2 顺序文件;9.2 顺序文件;9.2 顺序文件;9.2 顺序文件;9.3 索引文件;9.3 索引文件;;;;;9.3 索引文件;9.4 散列文件;9.5 多关键字文件;;9.5 多关键字文件;9.5 多关键字文件;9.6 外排序;; 归并排序处理步骤 记录分段处理：将文件中的记录按照可用内存大小划分为若干段，依次将每段记录读入到内存中对其进行内部排序，并将排序结果输出到子文件中。这样可以生成多个有序的子文件（即文件内的记录是有序的），通常称经过排序后的段为初始归并段。 文件归并处理：对上一步得到的初始归并段加以归并，直至将多段中的记录归并为一个有序文件为止。 ;9.6 外排序;9.6 外排序;9.6 外排序;9.6 外排序;9.6 外排序;9.6 外排序;9.6 外排序;9.6 外排序;9.7 应用实例;;Thank You !