9第九章：文件 -.pptVIP

数据结构与算法 D.S. 第九章 文 件 国家示范性软件学院 2006 · 秋 Slide. 9 - * 数据结构 哈尔滨工业大学软件与网络技术学院 D.S. Page. * 第一章 绪 论 9.1 文件及文件操作 9.2 文件组织 第九章 文 件 9.1 文件及文件操作 1、相关概念 文件是用于表示驻留在外存储器中的数据，是同性质 记录的有序集合。 F E D C B A 记录 沈 键 012 张 爽 011 许艺洪 010 史硕刚 009 陈 益 008 孙 喆 003 其它 物理 语文 数学 年龄 性别 姓名 学号 关键字 主关键字 次关键字 文件的逻辑结构和物理结构 逻辑结构：呈现给用户，描述记录间的逻辑关系 物理结构：存储结构，记录在存储器中的组织，连续，链式等 2、文件操作 操作 ● INSERT ● DELETE ● MODIFY ● RETRIEVE 检索方式：实时 or 成批 更新方式：实时 or 成批 查询方式：Q1:简单查询 Q2:范围查询 Q3:函数查询 Q4:布尔查询 9.2 文件组织 顺序方式 索引方式 散列方式 链接方式 倒排方式 顺序方式 文件的各个记录按逻辑顺序存放在外存的连续区内 记录的顺序往往是按主关键字的大小排列的 适合于Q1型查询，且检索与更新是成批进行的 适合磁带或磁盘 职工老文件 事物文件 职工新文件 文件修 改程序 磁带文件操作实例 磁盘文件 由柱面 和 磁道 组成 索引方式 “索引” 指的是记录的关键字值与记录驻留在外存的地址组成 数对的集合。每个数对称为一个索引项。 索引文件在存储器上分两区： 索引区 和 数据区 查找记录：分两步进行 删除记录：只删除索引 插入记录：先存数据，然后登记索引并重新排序 建立文件：按数据存入的先后顺序建立索引，最后索引排序 示例： 1 1 … An Cai 1 盘面号 柱面号 记录位置 记录 内容 姓名 序 号 人事档案示意文件 1 Cai Long 柱面号 柱面的最大关键字 柱面索引 1 Li Hong 盘面号 盘面的最大关键字 盘面索引 散列方式 用散列（HASH）法组织的文件。特点是用一个散列函数H(key)， 将关键字key映射为记录的地址，即 记录地址 = HASH(key) 基本步骤 确定记录数 存储单位（桶）记录数 确定桶数 设计HASH(key)函数 链接方式 60 40 20 最大学号 记录B 记录C 记录A 记录D 记录F 记录E 多重索引 倒排方式 在记录中保存链接 在索引中保存链接 数据结构与算法 D.S. 第九章 文 件 国家示范性软件学院 2006 · 秋 Slide. 9 - *