数据结构C++PPT8.ppt

数据结构第8章 文件管理和外排序 8.1 主存储器和辅助存储器 计算机存储器主要有两种： 主存储器( primary memory或者main memory ，简称“内存”，或者“主存”) 随机访问存储器( Random Access Memory, 即RAM ) 高速缓存( cache ) 视频存储器( video memory ) 外存储器(peripheral storage或者secondary storage，简称“外存”) 硬盘 软盘 磁带 外存的优缺点 优点：价格低、信息不易失 、便携性 缺点：存取速度慢 一般的内存访问存取时间的单位是纳秒（1纳秒 = 10-9秒），而外存一次访问时间则以毫秒（1毫秒 = 10-3秒）或秒为数量级 。 牵扯到外存的计算机程序应当尽量减少外存的访问和存取次数，从而减少程序执行的时间 内存的优缺点 优点：访问速度快 缺点：造价高、存储容量小和断电后丢失数据 CPU直接与主存沟通，对存储在内存地址的数据进行访问时，所需要的时间可以看作是一个很小的常数 外存数据访问方式 外存空间被划分成长度固定的存储块，称为页(page)，每一页包含一定数量的数据单元 作为外存的基本存储单位，数据以页块为单位进行存取，这样可以减少外存的定位次数，从而减少外存读写的时间耗费 磁盘结构 术语 扇区（sector）：I/O的基本单位 交错因子（interleaving factor）：逻辑上相邻的扇区之间的物理距离。 术语 引用的局部性（locality of reference）：如果读出了文件的一个扇区，很可能就要读出文件的下一个扇区。 簇（cluster）：多个扇区集结成组，文件分配的最小单位。 范围（extent）：属于同一个文件的一组物理上相连的簇。 内部碎片（internal fragmentation）：扇区内由于记录大小与扇区不相匹配而浪费的空间；如果文件大小不等于若干簇的大小而浪费的空间。 磁盘信息的存取 8.5 外部排序 如果数据存放在外存文件中，则需要考虑外存特点，采用外存文件排序技术，简称外排序(external sort)。 需要根据内存的大小，将外存中的数据文件划分成若干段，每次把其中一段读入内存并用内排序方法进行排序。这些已排序的段或有序的子文件称为顺串或归并段(run)。 归并排序 外排序通常由两个相对独立的阶段组成： 文件形成尽可能长的初始顺串 逐趟归并顺串，最后形成对整个数据文件的排列文件 外排序所需要的时间由三部分组成： 内部排序所需要的时间 外存信息读写所需要的时间 内部归并所需要的时间 减少外存信息的读写次数是提高外部排序效率的关键 归并排序 对同一个文件而言，进行外排序所需读写外存的次数与归并趟数有关系 假设有m个初始顺串，每次对k个顺串进行归并，归并趟数为[logkm] 为了减少归并趟数，可以从两个方面着手： 减少初始顺串的个数m 增加归并的顺串数量k 8.7 置换选择排序 置换选择算法（1） 置换选择产生一个顺串的算法如下： 1、初始化堆： （1） 从磁盘读M个记录放到数组RAM中； （2） 设置堆尾指标LAST = M – 1； （3） 建立一个最小堆。 2、重复以下步骤，直到堆为空（即LAST 0）： （1）把具有最小关键码值的记录(根结点)送到输出缓冲区； 置换选择算法（2） （2）设R是输入缓冲区中的下一条记录。判断R的关键码值是否大于刚刚输出的关键码值， ① 如果是，那么把R放到根结点。 ② 否则， (a) 使用数组中LAST位置的记录代 替根结点； (b) 把R放到LAST位置； (c) 设置LAST = LAST - 1。 （3）重新排列堆，筛出根结点。 顺串长度 二路外排序 8.8 多路归并 k路归并是每次将k个顺串合并成一个排好序的顺串。一般情况下，对m个初始顺串进行k路归并时归并趟数为logkm。增加每次归并的顺串数量k可以减少归并趟数。 选择树是完全二叉树，有两种类型：赢者树和败者树。 赢者树 假设用完全二叉树的公式化描述方法来定义赢者树，采用数组作为存储结构。 选手或叶结点用数组L[1...n]表示，内部结点用数组B[1...n-1]表示 数组B中实际存放的是数组L的索引 赢者树的一个优点是，如果一个选手L[i]的分数值改变了，可以很容易地修改这棵赢者树。只需要沿着从L[i]到根结点的路径修改二叉树，而不必改变其它比赛的结果。 赢者树 赢者树 败者树 败者树是赢者