张铭赵海燕王腾蛟北京大学数据结构与算法国家级十一五教材.PPT

主要内容 9.1 主存储器和外存储器 9.2 文件的组织和管理 9.3 外排序 9.4 文件管理和外排序知识点总结 9.1 主存储器和外存储器 计算机存储器主要有两种： 主存储器( primary memory或者main memory ，简称“内存”，或者“主存”) 随机访问存储器( Random Access Memory, 即RAM ) 高速缓存( cache ) 视频存储器( video memory ) 外存储器(peripheral storage或者secondary storage，简称“外存”) 硬盘 软盘 磁带 外存的优缺点 优点：价格低、信息不易失 、便携性 缺点：存取速度慢 一般的内存访问存取时间的单位是纳秒（1纳秒 = 10-9秒），而外存一次访问时间则以毫秒（1毫秒 = 10-3秒）或秒为数量级 。 牵扯到外存的计算机程序应当尽量减少外存的访问和存取次数，从而减少程序执行的时间 内存的优缺点 优点：访问速度快 缺点：造价高、存储容量小和断电后丢 失数据 CPU直接与主存沟通，对存储在内存地址的数据进行访问时，所需要的时间可以看作是一个很小的常数 外存数据访问方式 外存空间被划分成长度固定的存储块，称为页(page)，每一页包含一定数量的数据单元 作为外存的基本存储单位，数据以页块为单位进行存取，这样可以减少外存的定位次数，从而减少外存读写的时间耗费 9.2 文件的组织和管理 文件(file)是存储在外存上的数据结构，是由大量性质相同的记录(record)组成的集合。 所谓记录，就是具有独立逻辑意义的数据块，是文件的基本数据单位。 最简单的记录可以是字符或者二进制序列，复杂的记录通常可以由若干字段或域(field)的数据项组成。 9.2 文件的组织和管理 按照记录的类型，文件可以分成两种： 操作系统的文件 操作系统的文件是一组连续的字符序列，这种序列没有明显的结构。用户也可以将文件中的信息划分成若干个逻辑记录，以便存取和使用。 数据库文件 数据库文件是有结构的记录集合，其中每一条记录都由一个或多个数据项组成，而每个数据项是不可再分的基本数据单元。 9.2 文件的组织和管理 如表9.1所示为一个数据库文件，每个学生的信息组成一个记录，每一条记录由6个数据项构成。 9.2 文件的组织和管理 按照记录信息长度，文件可以分成 定长文件 如果文件中每一条记录均含有相同的信息长度，那么这种文件称为定长文件。通常定长文件处理起来比较方便。 不定长文件 若文件中的记录不是相等长度的，则称为不定长文件。 9.2 文件的组织和管理 按照关键码(key)的个数，文件可以分成： 单关键码文件 单关键码文件是指文件的记录中只有一个标识关键码 多关键码文件 多关键码记录文件中，记录除了有一个主关键码以外还允许有若干个次关键码 9.2 文件的组织和管理 文件的操作有实时和批量两种处理方式 实时操作要求有较短的应答响应时间，在接受指令后尽可能快地完成检索或修改任务。 批量的文件处理则允许较长反馈时间。用户可以根据需求选择不同的文件处理方式。 9.2 文件的组织和管理 9.2.1 文件组织 9.2.2 C++的流文件 9.2.1 文件组织 文件逻辑组织有以下三种形式：顺序结构的定长记录、顺序结构的变长记录和按关键码存取的记录。 文件的物理结构可以有多种多样的组织方式。常见的物理组织结构有： 顺序文件 散列文件 索引文件 倒排文件 9.2.2 C++的流文件 文件流是以外存文件为输入输出对象的数据流。 文件流与文件不是同一个概念，文件流不是由若干个文件组成的流。文件流本身不是文件，而只是以文件为输入输出对象的流。 9.2.2 C++的流文件 标准输入输出流类包括istream，ostream和iostream类 istream是通用输入流和其它输入流的基类，支持输入 ostream是通用输出流和其它输出流的基类，支持输出 iostream是通用输入输出流和其它输入输出流的基类，支持输入输出 3个用于文件操作的文件类 ifstream类，从istream类派生，用来支持从磁盘文件的输入 ofstream类，从ostream类派生，用来支持向磁盘文件的输出 fstream类，从iostream类派生，用来支持对磁盘文件的输入和输出 9.2.2 C++的流文件 下面是fstream类的一些主要成员函数： #include fstream.h // fstream = ifstream+ofstrea