数据结构 教学课件 作者 叶乃文 郑晓红 第九章.ppt

《数据结构 教学课件 作者 叶乃文 郑晓红 第九章.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第9章文件本章中介绍下列主要内容：文件的基本概念常用的文件操作文件的组织结构以及文件的不同组织方式的特点退出9.1文件的基本概念9.2文件的操作9.3文件的组织9.1文件的基本概念文件文件是存储在外部介质上的由大量性质相同的记录组成的集合。按其记录的类型不同可以分为两类：程序文件和数据文件。程序文件是一维的、连续的、无结构的字符序列，可以看成是由一条无结构的记录组成的文件。数据文件是带有结构的、性质相同的记录的集合。每个记录由若干个数据项组成，数据项是最基本的不可分割的数据单位，也是文件中可以操作的

2、最小数据单位。本章介绍的就是数据文件的组织结构及其处理方式。关键字能够标识文件中记录的数据项称为关键字，能够唯一标识记录的关键字称为主关键字，否则为次关键字。记录的逻辑结构是指文件的记录在用户或应用程序员面前逞现的方式，是对数据间的客观联系的一种表示，是用户对数据的存取方式。记录的物理结构是指文件中的记录在物理存储介质上的存储方式，是数据的物理表示和组织。根据不同的需要、设备本身的特性及操作系统中的文件系统，记录的物理结构可以有不同的表示和组织方法。物理记录是计算机用一条I/O命令进行读写的基本数据

3、单位，对于确定的设备和操作系统，它的大小基本上是固定不变的。物理记录与逻辑记录的关系物理记录与逻辑记录之间有三种可能的关系，分别为一个物理记录中存放一个逻辑记录、一个物理记录中存放多个逻辑记录、多个逻辑记录存储于一个物理记录中。文件的存取文件存储在外部介质上，所以对文件的存取要通过访问外存储介质来实现。外存储介质的共同特点是存储容量大，存取速度慢。以目前使用最为广泛的磁盘存储器为例，读写磁盘上的信息，首先要经过选定柱面、选定磁道、选定扇区（即物理记录）三步机械定位动作，然后才能通过磁头读写盘片上的信

4、息。此外，主机对外存储介质上的数据不能直接进行存取，要读取外存储介质上的数据，首先要通过通道把数据读到内存的一个指定区域（缓冲区）中，然后从缓冲区中读取有关的数据。写操作的过程则相反，先将内容写到缓冲区中，然后通过通道将缓冲区中的数据写到外存储介质上。外存储介质上的数据存取时间往往比主机对数据进行处理的时间花费大，所以对外存储介质上的数据处理常常以访问外存储介质次数的多少作为衡量其数据结构及其算法质量的标准。节省存取时间的有效方法是：在每次访问外存储介质时，传送批量的数据，从而减少访问外存储介质的次

5、数。9.2文件的操作在这里讲述的文件操作主要是指对文件中数据的操作。其基本操作有：文件的读操作和写操作，这两种操作与具体的设备及操作系统有关，在此我们假定有专门的程序完成其功能。除此之外，还可以对文件进行检索和修改。1．文件的检索文件的检索有下列三种方式：顺序存取：存取下一个每个记录。随机存取：存取第i个逻辑记录。按关键字存取：查询一个或一批关键字与给定值相关的记录。2．文件的修改文件的修改操作包括插入一条记录、删除一条记录和更新一条记录三种操作。9.3文件的组织文件在存储介质（如磁盘或磁带）上的组

6、织方式称为物理结构。常用的文件组织方式有三种基本形式：顺序组织、随机组织和链组织。1．顺序文件顺序文件的记录是按其在文件中的逻辑顺序依次存入存储介质的。它是一种顺序组织方式。由于顺序文件中记录的物理次序与逻辑次序是一致的，所以适宜于顺序存取（即存取一个记录之后接着存取其后继记录）和批量处理。但是对顺序文件中记录的随机存取效率很低。2．散列文件散列文件类似于哈希表，即根据文件中的关键字特点设计一种哈希函数（也叫作散列函数）和处理冲突的方法来确定记录的存储位置，将记录散列在存储介质上，这样的文件被称作散

7、列文件。散列文件是一种随机组织方式。对散列文件的的随机存取效率很高，对于关键字值等于给定值的记录的访问，可以直接由散列函数及冲突处理方法求得在外存上的存储位置，从而方便地对它存取。但散列文件不适宜顺序存取和成批处理。