第13章 文件结构.pptVIP

直接法应用示例 某个机构有100个职员，每个职员分配1~100的编号。如果建立100个职员记录的文件，可以用职员编号直接作为记录的地址。 此应用非常有限，如果用社会保险号作为键则效率低下，社会保险号有9位，需要999999999条记录的巨大文件；而公司的职员可能只有100，多数记录被浪费。应该寻求将较大的键取值范围映射到较小的地址取值范围。 直接法应用图示 2、求模法 求模法也称除余哈希法，计算地址时，求模法用文件中的记录数量去除键，将余数加1作为地址。 address = key % list_size + 1 求模法会产生冲突，尽量选择与记录数量接近的素数作为除数，相对会产生更少的冲突。 求模法应用示例 创建一个编号系统，可以容纳100万名雇员，而当前公司实际只有300名雇员，没必要创建含100万条记录的文件。 现提供可以容纳300名左右雇员的数据空间，实际选择307(大于300的第一个素数)。则某个雇员对应记录的地址为： 雇员编号 % 307 + 1 Part Ⅳ 数据组织 信工计算机教研室 第十三章 文件结构 学习目标 了解文件的存取方法。 了解顺序文件的特征。 了解索引文件的特征。 了解哈希文件的特征。 理解文本文件和二进制文件之间的区别。 13.1 存取方法 主要内容 13.3 索引文件 13.4 哈希文件 13.2 顺序文件 13.5 文本文件和二进制文件 存取方法 13.1 文件概述 文件是作为一个单元看待的相关数据的外部集合，文件主要目的是存储数据。 计算机关闭时，主存中的内容将丢失，需要使用文件这种永久的方式来存储数据。 数据的集合可能非常大，不能一次全部驻留内存，部分加载的情况下读写数据。 文件概述 文件通常存储在辅助存储设备(或二级存储设备)中，常见的存储设备有磁盘和磁带，这些设备是可读写的。 从广义的角度看，可以把键盘、显示器也看成文件，键盘只能读不能写，显示器只能写不能读。 还可以把文件看成数据记录的集合，而记录由一个或多个域组成。 13.1 存取方法 设计文件的关键在于将来如何从文件中检索信息(特定的记录)。常用的检索方法有顺序检索和随机检索，它们是由存取方法决定的。 顺序存取：如果需要顺序存取文件(从头到尾，逐条记录处理)，应该使用顺序存取文件结构。 随机存取：想存取某一特定记录而不用检索之前的所有记录，应使用随机存取文件结构。 文件结构分类 13.1 存取方法 主要内容 13.3 索引文件 13.4 哈希文件 13.2 顺序文件 13.5 文本文件和二进制文件 顺序文件 13.2 13.2 顺序文件 顺序文件的记录只能按照顺序从头到尾一个接一个地进行存取。记录被一个接一个地存储到辅助存储器中，在所有记录之后加上EOF作为文件结束标记。 处理顺序文件 使用循环结构逐条读和处理记录，当处理完最后一条记录，检测到EOF标记从而结束循环。 While Not EOF { Read the next recordProcess the record } 应用 顺序文件用于需要从头到尾存取记录的应用。如公司员工的个人资料存储在文件中，可以通过顺序存取检索每条记录来打印工资，此时更加简洁高效。 问题：随机检索效率非常低。假如银行客户记录只能被顺序存取，要想从取款机提款，必须从头到尾检索所有记录直到找到该客户，效率当然低下。 更新顺序文件 顺序文件的更新非常麻烦，涉及四个文件 新主文件：必威体育精装版的永久数据文件； 旧主文件：需要更新的永久文件，更新后该文件继续保留作为参考； 事务文件：包含对主文件要作的改变的描述。添加事务包含要添加到主文件中的数据；删除事务标识需要删除的记录；更改事务包含对文件中特定记录的修改。 错误报告文件：记录更新数据过程中的错误清单。 更新顺序文件过程 具体更新步骤 为使更新更加有效，所有文件的记录按键排序，键是文件中一个或多个能唯一标识数据(记录)的域。 更新过程中，比较事务文件和旧主文件中的键，遵循一定的规则执行添加A、删除D、修改R等操作。 具体更新步骤 更新过程从比较文件的首记录的键开始。 如果事务文件的键与旧主文件的相同。 事务代码是R，修改记录并插入新主文件；如果代码是D，忽略该记录。 两个文件的键指针同时向后移动。 如果事务文件的键大于旧主文件的键，该记录原封不动写入新主文件，旧主文件移动到下一个键，事务文件不动。 事务文件的键小，则将记录追加到新主文件中，事务文件键后移，旧主文件不动 更新的图示 13.1 存取方法 主要内容 13.3 索引文件 13.4 哈希文件 13.2 顺序文件 13.5 文本文件和二进制文件 索引文件 13.3 13.3 索引文件 要支持对文件的随机存取，必须知道记录的地址(记录在磁盘上的相对位置)。 索引文件