9-数据结构与算法-北京大学2008-张铭-文件管理和外排序

数据结构与算法第9章文件管理和外排序本章由王腾蛟主写://张铭，王腾蛟，赵海燕高等教育出版社，2008.6。“十一五”国家级规划教材“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。主要内容9.1主存储器和外存储器9.2文件的组织和管理9.3外排序9.4文件管理和外排序知识点总结“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。9.1主存储器和外存储器计算机存储器主要有两种：主存储器(primarymemory或者mainmemory，简称“内存”，或者“主存”)•随机访问存储器(RandomAccessMemory,即RAM)•高速缓存(cache)•视频存储器(videomemory)外存储器(peripheralstorage或者secondarystorage，简称“外存”)•硬盘•软盘•磁带“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。外存的优缺点优点：价格低、信息不易失、便携性缺点：存取速度慢一般的内存访问存取时间的单位是纳秒（1纳秒=10-9秒），而外存一次访问时间则以毫秒（1毫秒=10-3秒）或秒为数量级。牵扯到外存的计算机程序应当尽量减少外存的访问和存取次数，从而减少程序执行的时间“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。内存的优缺点优点：访问速度快缺点：造价高、存储容量小和断电后丢失数据CPU直接与主存沟通，对存储在内存地址的数据进行访问时，所需要的时间可以看作是一个很小的常数“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。外存数据访问方式外存空间被划分成长度固定的存储块，称为页(page)，每一页包含一定数量的数据单元作为外存的基本存储单位，数据以页块为单位进行存取，这样可以减少外存的定位次数，从而减少外存读写的时间耗费“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。9.2文件的组织和管理文件(file)是存储在外存上的数据结构，是由大量性质相同的记录(record)组成的集合。所谓记录，就是具有独立逻辑意义的数据块，是文件的基本数据单位。最简单的记录可以是字符或者二进制序列，复杂的记录通常可以由若干字段或域(field)的数据项组成。“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。9.2文件的组织和管理按照记录的类型，文件可以分成两种：操作系统的文件操作系统的文件是一组连续的字符序列，这种序列没有明显的结构。用户也可以将文件中的信息划分成若干个逻辑记录，以便存取和使用。数据库文件数据库文件是有结构的记录集合，其中每一条记录都由一个或多个数据项组成，而每个数据项是不可再分的基本数据单元。“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。9.2文件的组织和管理如表9.1所示为一个数据库文件，每个学生的信息组成一个记录，每一条记录由6个数据项构成。姓名学号性别出生年月所在院系入学时间贾由00646125男1988.5数学2006.9.1陈醒00648308男1989.7计算机2006.9.1吴轲00648230男1988.3计算机2006.9.1王子琪00648139女1988.2计算机2006.9.1………………………………“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。9.2文件的组织和管理按照记录信息长度，文件可以分成定长文件如果文件中每一条记录均含有相同的信息长度，那么这种文件称为定长文件。通常定长文件处理起来比较方便。不定长文件若文件中的记录不是相等长度的，则称为不定长文件。“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。9.2文件的组织和管理按照关键码(key)的个数，文件可以分成：单关键码文件单关键码文件是指文件的记录中只有一个标识关键码多关键码文件多关键码记录文件中，记录除了有一个主关键码以外还允许有若干个次关键码“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。9.2文件的组织和管理文件的操作有实时和批量两种处理方式实时操作要求有较短的应答响应时间，在接受指令后尽可能快地完成检索或修改任务。批量的文件处理则允许较长反馈时间。用户可以根据需求选择不同的文件处理方式。“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。9.2文件的组织和管理9.2.1文件组织9.2.2C++的流文件“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。9.2.1文件组织文件逻辑组织有以下三种形式：顺序结构的定长记录、顺序结构的变长记录和按关键码存取的记录。文件的物理结构可以有多种多样的组织方式。常见的物理组织结构有：顺序文件散列文件索引文件倒排文件“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。9.2.2C++的流文件文件流是以外存文件为输入输出对象的数据流。文件流与文件不是同一个概念，文件流不是由若干个文件组成的流。文件流本身不是文件，而只是以文件为输入输出对象的流。“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。9.2.2C++的流文件标准输入输出流类包括istream，ostream和iostream类istream是通用输入流和其它输入流的基类，支持输入ostream是通用输出流和其它输出流的基类，支持输出iostream是通用输入输出流和其它输入输出流的基类，支持输入输出3个用于文件操作的文件类ifstream类，从istream类派生，用来支持从磁盘文件的输入ofstream类，从ostream类派生，用来支持向磁盘文件的输出fstream类，从iostream类派生，用来支持对磁盘文件的输入和输出“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。9.2.2C++的流文件下面是fstream类的一些主要成员函数：#includefstream.h//fstream=ifstream+ofstreamvoidfstream::open(char*name,openmodemode);//打开文件进行处理fstream::read(char*ptr,intnumbytes);//从文件当前位置读入一些字节fstream::write(char*ptr,intnumbtyes);//向文件当前位置写入一些字节//seekg和seekp：在文件中移动当前位置，以便在文件中的任何位置读出或写入字节fstream::seekg(intpos);//输入时用于设置读取位置fstream::seekg(intpos,ios::curr);fstream::seekp(intpos);//设置输出时的写入位置fstream::seekp(intpos,ios::end);voidfstream::close();//处理结束后关闭文件“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。9.2.2C++的流文件文件常见的三个基本操作：把文件指针设置到指定位置从文件的当前位置读取字节向文件中的当前位置写入字节，都是围绕文件指针进行的程序员对磁盘文件进行输入输出时，都需要管理标志文件当前位置的文件指针。“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。9.3外排序9.3.1置换选择排序9.3.2二路外排序9.3.3多路归并——选择树“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。9.3外排序如果数据存放在外存文件中，则需要考虑外存特点，采用外存文件排序技术，简称外排序(externalsort)。需要根据内存的大小，将外存中的数据文件划分成若干段，每次把其中一段读入内存并用内排序方法进行排序。这些已排序的段或有序的子文件称为顺串或归并段(run)。“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。9.3外排序外排序通常由两个相对独立的阶段组成：文件形成尽可能长的初始顺串逐趟归并顺串，最后形成对整个数据文件的排列文件外排序所需要的时间由三部分组成：内部排序所需要的时间外存信息读写所需要的时间内部归并所需要的时间减少外存信息的读写次数是提高外部排序效率的关键“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。9.3外排序对同一个文件而言，进行外排序所需读写外存的次数与归并趟数有关系假设有m个初始顺串，每次对k个顺串进行归并，归并趟数为[logkm]为了减少归并趟数，可以从两个方面着手：减少初始顺串的个数m增加归并的顺串数量k“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。9.3.1置换选择排序算法的处理过程为：从输入文件读取一定数量的记录进入输入缓冲区；然后向内存工作区放入待排序记录并进行排序；记录被处理后，写到输出缓冲区；当输出缓冲区写满的时候，把整个缓冲区写回到外存文件。当输入缓冲区为空时，再次从外存文件中读取下一块记录。“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。9.3.1置换选择排序置换选择示例30154525504935601627“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。9.3.1置换选择排序置换选择产生一个顺串的算法如下：1、初始化堆：（1）从磁盘读M个记录放到数组RAM中；（2）设置堆尾指标LAST=M–1；（3）建立一个最小堆。2、重复以下步骤，直到堆为空（即LAST0）：（1）把具有最小关键码值的记录(根结点)送到输出缓冲区；“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。9.3.1置换选择排序（2）设R是输入缓冲区中的下一条记录。判断R的关键码值是否大于刚刚输出的关键码值，①如果是，那么把R放到根结点。②否则，(a)使用数组中LAST位置的记录代替根结点；(b)把R放到LAST位置；(c)设置LAST=LAST-1。（3）重新排列堆，筛出根结点。“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。9.3.1置换选择排序【算法9.1】置换选择算法//参数A是从外存读入数据后所存放的数组，n是数组元素的个数，in和out是输入和输出文件名templateclassTvoidreplacementSelection(T*A,intn,constchar*in,constchar*out){Tmval;//存放最小堆的最小值Tr;//存放从输入缓冲区中读入的元素FILE*inputFile;//输入文件句柄FILE*outputFile;//输出文件句柄BufferTinput;//输入缓冲区BufferToutput;//输出缓冲区initFiles(inputFile,outputFile,in,out);//初始化输入输出文件“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。9.3.1置换选择排序initM