数据结构——-文件.pptVIP

;标候缅份了澎菊氖宵婆都肃膝涡佣懂藤玻兄驰揪折捐袖蓄狂翅骆匙呈邹未数据结构——文件数据结构——文件;文件的应用背景，数据结构范畴的文件概念。 基于检索的文件的基本形式与特点。 常用的文件方式和关键技术实现要点。;10.1.1 文件 文件（file） 文件是性质相同、逻辑上相关的数据记录集合。 按数据记录的长度是否确定而分为定长文件和不定长文件： ●定长文件：文件中所有记录含有的数据项个数相同。 ●不定长文件：文件中记录含有的数据项个数不等。;按文件实际用途可以分为操作系统文件和数据库文件： ① 操作系统文件 无严格意义下的数据结构，只是作为记录的集合，主要表现为一维无结构连续字符序列，记录之间既没有结构的解释也没有特性的解释；相应文件操作只有“整体”操作即打开或关闭文件、删除文件或复制文件等；以及“字节”操作即从文件读取一个字节或将一个字节写到文件当中。 ② 数据库文件 各项记录之间具有严格的逻辑结构（例如基本的线性表结构、关系文件和面向对象文件结构等），同时每个记录也有相应结构，即数据库记录由若干数据项构成。;数据库文件： 例：下图是一个学生学籍文件，每个学生情况形成一个记录。每个记录由学号、姓名、性别、籍贯、出生年月和住址6个数据项组成。定义“学号”是主关键字，“姓名”、“性别”等是次关键字。;按只有主关键字还是同时具有主关键字和次关键字而分为单关键字文件或多关键字文件： ●单关键字文件：记录中只有一个惟一标识记录的主关键字。 ●多关键字文件：记录中除了含有一个主关键字外还含有若干个次关键字。;1、文件逻辑结构 作为存储在外存中的数据，文件是具有相同性质的记录集合，其逻辑结构应当为集合。但在实际操作过程中，文件中各个记录至少都是“顺次”进入计算机的，即其至少具有“工作”顺序，在这种意义下，通常将文件看作一种线性表，或者说，文件就是外存中的线性表。 注意区分文件中记录的“顺序”（sequential）概念和文件记录的“有序”（order）概念。;2、文件存储结构 存储结构是文件在物理存储介质（磁盘或??带）上的组织方式，它决定了文件信息在存储设备上的存储位置。 ① 顺序文件 顺序文件在逻辑上是将数据记录间的顺序作为相应线性表中元素的“次序”关系，在存储上，这种顺序关系与物理存储顺序一致。 ② 索引文件 在存储的文件之外，建立一个相对于主文件用于描述文件逻辑记录与物理存储记录之间的一一关系（即文件的第i号记录对应存储的物理地址）的索引表，此时，主文件和其索引表构成的二元组就称为索引文件。 ③ 散列文件 散列文件也称为哈希（hash）文件或者直接存取文件，其特点是使用散列存储方式组织文件。 ④ 链式文件 链式文件中的连结点一般都比较大，同时也不定长。在文件存储方式中，链式文件通常都是结合索引文件一起使用，例如多关键字文件等。;3、文件基本操作 （1）文件检索 文件检索就是在文件中查找满足给定条件的数据记录，实现途径可以是按照记录进入外存的时间顺序（逻辑序号）查找，也可以是按照记录的关键字大小查找。 ① 顺序检索 通过逐次读取所有序号小于i的记录，定位所需要的第i号记录。 ② 直接检索 不通过逐次读取所有序号小于i的记录而直接定位第i号记录。直接检索也称为随机检索。 ③ 按关键字检索 定位关键字与给定关键字相同或相关的数据记录。 ● 简单检索：询问单个关键字等于给定值的记录。 ● 范围检索：询问单个关键字属于某个范围内的所有记录。 ● 函数检索：规定单个关键字的某个函数，询问该函数的某个值。 ● 布尔检索：以上三种询问用布尔运算(与、或、非)组合起来的询问。例如查询某成绩表中，查找表中(数学成绩90)and（性别=“女”)的记录。;3、文件基本操作 （1）文件检索2 按操作的处理方式，可分为实时与批量处理两种不同的方式: 实时处理：响应时间要求严格，要求在接受询问后几秒种内完成检索和更新。 批量处理：响应时间要求宽松一些，不同的文件系统有不同的要求。 例如一个银行的账户系统，需要满足实时检索要求，也可进行批量更新，即可以将一天的存款和提款记录在一个事务文件上，在一天的营业之后再进行批量处理。;3、文件基本操作2 （2）文件更新 数据库文件的维护操作可以分为文件更新、故障恢复、安全性保护和完整性约束等基本情形。 文件更新操作类型： ● 插入记录 在给定文件中插入给定的数据记录。此时是针对整条数据记录的操作。 ● 删除记录 在给定文件中删除其中一条或多条记录，此时也是针对整条记录的操作。 ● 修改记录 在给定文件中修改其中一条记录的某个或多个数据项，此时是针对记录中部分数据项的操作。;10.2.1 顺序文件存储结构 顺序文件在存储介质中可以有两种不同的存储结