数据结构实例教程（C语言版）：第10章 文件

1、第10章文件 学习目标 熟悉各类文件的特点和构造方法。 了解在各类文件上的检索、插入和删除等操作。 10.1文件的概念一、基本概念 1、文件的定义：性质相同的记录的集合。 2、关键字的定义：能够区别文件中各记录的域。3、定长记录文件的定义：如在一个个人书库文件中，各个 记录的结构相同，信息长度相同，因而将这样的记录称 为定长记录。由定长记录组成的文件称为定长记录文件。4、不定长记录文件的定义：在学生学籍管理文件中，不同 的年级，或者不同专业的学生，所修的课程数和课程名 称都不一样，称为不定长记录。由不定长记录组成的文 件叫做不定长记录文件。5、文件的分类： 按记录类型：文件可分为操作系统文件和

2、数据库文件。 按关键字：文件可分为单关键字文件和多关键字文件。10.1文件的概念二、文件的逻辑结构和物理结构 1、逻辑结构的定义：文件中的记录展现在用户或程序员面 前的逻辑关系。文件中的记录称“逻辑记录”，是用户 表示和存取信息的单位，例如，在学籍管理软件中，存 放学生信息的文件就是一类定长记录文件，它由若干学 生记录信息构成，每个学生记录（逻辑记录）又由很多 数据项构成，如：学号、姓名、性别、年龄等。2、物理结构的定义：即文件的存储结构，指文件在外存上 的组织方式。文件在外存上的基本的组织方式有四种： 顺序组织，索引组织，散列组织和链组织；对应的文件 分别为：顺序文件、索引文件、散列文件和多

3、关键字文 件。10.1文件的概念三、文件的操作 1、文件的操作有两类：检索和修改。2、常用四种检索方式： (1) 简单查询：查询关键字值等于给定值的记录； (2) 区域查询：查询关键字值属于某个区域内的记录； (3) 函数查询：查询关键字值满足某个函数的记录； (4) 布尔查询：由检索式的布尔运算构成组合条件。3、文件的修改和维护操作主要是指： (1)对文件进行记录的插入、删除及修改等更新操作； (2)为提高文件的效率，进行再组织操作； (3)文件被破坏后的恢复操作，以及文件中数据的安全保护等。 10.2顺序文件一、顺序文件的分类 1、存储在顺序存储器（如磁带）上的文件，只能是顺序文 件，这种

4、文件只能进行“顺序存取”和“成批处理”。 磁带顺序文件优点：连续存取时速度快，批处理效率 高，节省存储空间。缺点：实时性差，特别是更新操作 要复制整个文件，所以一般不做随机处理。2、顺序文件也可以存放在直接存取设备上，磁盘就是一个 直接存取的存储设备。对存储在这类设备上的顺序文件 不仅可以进行顺序存取，还可以进行“按记录号”的直接存取或“按关键字”进行随机存取。修改可进行批处 理，也可随机处理。10.2顺序文件一、顺序文件的定义和实例描述 1、索引用来表示关键字与相应记录的存储地址之间的对应 关系。即指出记录在存储器中的存储地址。索引文件由 “索引”和“主文件”两部分构成。2、实例描述10.4

5、索引顺序文件一、索引顺序文件的特点 1、若索引文件中的主文件按关键码有序，则称为索引顺序 文件 。索引顺序文件中的索引是“非稠密索引”，即对 主文件中连续的一组记录建立一个索引项，索引文件由 这组记录中的最大关键码和这组记录的物理地址组成。二、VSAM文件的组织方法1、VSAM是Virtual Storage Access Method(虚拟存储存取方法)的缩写，它也是一种索引顺序文件的组织方式，采用B+树作为动态索引结构。10.5散列文件一、散列文件的组织方式 1、散列文件是利用散列存储方式组织的文件，又称直接存 取文件。散列文件由若干个“桶”组成，根据设定的哈 希函数将记录“映象”到某个桶

6、号。处理冲突通常采用 链地址法，即每个桶可以包括一个或几个页块，页块之 间以指针相链。10.5散列文件二、散列文件的操作 散列文件的优点是：插入、删除方便，记录随机存放，存取速度比索引文件要快；不需要索引区，节省存储空间，容易实现文件的扩充。缺点是：不能进行顺序存取和批处理，只能按关键字随机存取，且询问方式只有简单询问；并且在经过多次的插入、删除之后，也可能造成文件结构不合理，即溢出桶满而基桶内多数为被删除的记录。此时需要重组文件。10.6多关键字文件一、多关键字文件概念 1、多关键字文件的定义：包含有多个次关键字索引的文件。2、实例描述注：“考号”为主关键字，“总分”和“数学成绩”为次关键字

7、 10.6多关键字文件二、倒排文件 在倒排文件中，为每个需要进行检索的次关键字建立一个倒排表，倒排表中具有相同次关键字的记录构成一个顺序表。10.6多关键字文件三、多重表文件 多重表文件的特点是，主文件为串联文件 (即按主关键字顺序利用指针链接为表结构)，并建立主关键字的非稠密索引-主索引，对每一个次关键字建立次索引，所有具有同一次关键字值的记录链接为一个链表，链表的头指针和链表的长度以及次关键字值构成一个索引项。10.6多关键字文件物理地址职工号姓名职务工资级别职务链工资链10103逄凯 硬件人员1211010210赵龙 硬件人员1110710610307孙加林软件人员1310810710405刘永宝穿 孔 员1410511010506丁媛媛穿 孔 员1310310612景静软件人员1110714刘芳冰硬件人员1310809耿直软件人员