• / 64
  • 下载费用:10 金币  

数据结构 严蔚敏 第12章.ppt

关 键 词:
数据结构 严蔚敏 第12章.ppt
资源描述:
第十二章 文 件,12.1 有关文件的基本概念,12.2 顺 序 文 件,12.3 索 引 文 件,12.4 索 引 顺 序 文 件,12.5 直 接 存 取 文 件,12.6 多 关 键 字 文 件,12.1 有关文件的基本概念,一、文件即为记录的集合,和“查找表”的差别在于,“文件”指的是存储在外存储器中的记录的集合。记录是文件中可以存取的数据的基本单位。,二、文件可按其中记录的类型不同而分成两类:,其一为操作系统的文件,文件中的记录仅是一个字符组。由于操作系统中的文件仅是一维的连续字符序列,为了用户存取和加工的方便,将文件中的信息划分为若干组,其中每一组信息称作一个记录;,其二为数据库文件,文件中的记录带有结构,是数据项的集合。记录是文件中可以存取的数据基本单位,数据项是文件中可以使用的数据最小单位。,三、记录中能识别不同记录的数据项被称为关键字,若该数据项能唯一识别一个记录,则称为主关键字,若能识别多个记录则称为次关键字。,四、文件的逻辑结构指的是呈现在用户面前的文件中记录之间的逻辑关系;文件的物理结构指的是文件中的逻辑记录在存储器中的组织方式。,五、文件的操作:,检 索,修 改,排 序,,1.检索,顺序存取:存取“当前记录的”下一个记录; 直接存取:存取第i个记录; 按关键字存取:存取其关键字等于给定值的记录。,,2.修改,往文件中插入一个或一批记录;,更新文件中某个记录的属性。,从文件中删除一个或一批记录;,,文件的操作方式可以实时处理或 批量处理。,3.排序,,本章讨论文件的几种常见的 物理结构:,顺序文件,索引文件,索引顺序文件,直接存取文件,多关键字文件,,12.2 顺 序 文 件,结 构 特 点:,记录在文件中的排列顺序是由记 录进入存储介质的次序决定的, 即文 件物理结构中记录的排列顺序和文件 的逻辑结构中记录的排列顺序一致。,顺序文件的具体组织形式有两种:,串联文件:物理记录之间的顺序由指针相链。,连续文件:次序相继的两个物理记录其存储位置相邻;,操作特点:,1.便于进行顺序存取; 2.不便于进行直接存取,为取第i个记录,必须先读出前i-1个记录,对于磁盘上的等长记录的连续文件可以进行折半查找;,3.插入新的记录只能加在文件的末尾; 4.删除记录时,只作标记; 5.更新记录必须生成新的文件。,顺序文件的插入、删除和更新操 作在多数情况下都采用批处理方式。 此时,为处理方便,通常将顺序文件 作成有序文件,称作“主文件”,同时 将所有的操作作成一个“事务文件” (经过排序也成为有序文件),所谓 “批处理”,就是将这两个文件“合”为 一个新的主文件。具体操作相当于 “归并两个有序表”。,(1)对于事务文件中的每个操作首先要判别其“合法性”,(2)事务文件中可能存在多个操作是对主文件中同一个记录进行的,但有两点不同:,假设主文件中含有n个记录,事 务文件中含有m个记录,则对事务文 件进行排序的时间复杂度为O(mlogm), 内部归并的时间复杂度为O(m+n), 则总的内部处理的时间为O(mlogm+n)。,批处理的时间分析:,假设对外存进行一次读/取为s个 记录,则整个批处理过程中读/写外存 的次数为2(m/s+(m+n)/s),(其中s为对外存进行一次读/取的记录数)。,,12.3 索 引 文 件,一、结构特点:,1.索引文件由“主文件”和多级“索引”组成; 2.索引中的每个记录由“关键字”和“指针”组成; 3.通常,索引文件中的主文件是无序文件,索引是 (按关键字有序)的有序文件; 4.“索引”是在输入数据建立文件时自动生成。初建时的“静态索引”为无序文件,经过排序后成为有序文件。,二、操作的特点:,1.检索方式为:直接存取和按关键字存取。“按关键字检索”将分两步进行:先查索引,然后根据索引中指针所指索取记录; 2.插入记录时,“记录”插入在主文件的末尾,而相应的“索引项”必须插入在索引的合适位置上。因此,最好在建索引表时留有一定“空位”;,3.删除记录时,仅需删除索引表中相应的索引项即可; 4.更新记录时,应将更新后的记录插入在主文件的末尾,同时修改相应的索引项。,1.多 级 静 态 索 引,2.动 态 索 引,,1.多级静态索引,,主 文 件,,索 引 表,,查 找 表,,第 二 查 找表,,第三查找表,,,,,,,… .,,,… .,… .,… .,此时的索引文件结构:,,,,对主文件中每个记录建立一个索引项:,,主关键字 记录在主文件中的存储位置,,称作稠密索引,由这些索引项构成 索引表。,,,从索引表建立的索引称查找表,其中 每个索引项为:,,最大关键字 其所在数据块的存储位置,,称这类索引为非稠密索引。,类似地,由查找表建立的索引为第二 查找表;由
展开阅读全文
  微传网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
0条评论

还可以输入200字符

暂无评论,赶快抢占沙发吧。

关于本文
本文标题:数据结构 严蔚敏 第12章.ppt
链接地址:https://www.weizhuannet.com/p-9819128.html
微传网是一个办公文档、学习资料下载的在线文档分享平台!

微传网博客

网站资源均来自网络,如有侵权,请联系客服删除!

 网站客服QQ:80879498  会员QQ群:727456886

copyright@ 2018-2028 微传网络工作室版权所有

     经营许可证编号:冀ICP备18006529号-1 ,公安局备案号:13028102000124

收起
展开