下载

0下载券

加入VIP
  • 专属下载券
  • 上传内容扩展
  • 资料优先审核
  • 免费资料无限下载

上传资料

关闭

关闭

关闭

封号提示

内容

首页 网络上流传的严蔚敏数据结构(48课时)上课视频教程笔记

网络上流传的严蔚敏数据结构(48课时)上课视频教程笔记

网络上流传的严蔚敏数据结构(48课时)上课视频教程笔记

taozhifeng1996
2009-04-20 0人阅读 举报 0 0 0 暂无简介

简介:本文档为《网络上流传的严蔚敏数据结构(48课时)上课视频教程笔记pdf》,可适用于高等教育领域

来自wwwfreekaoyancom转载请注明严蔚敏数据结构教学笔记第页第十二章文件有关文件的基本概念一、文件即为记录的集合和“查找表”的差别在于“文件”指的是存储在外存储器中的记录的集合。记录是文件中可以存取的数据的基本单位。二、文件可按其中记录的类型不同而分成两类:其一为操作系统的文件文件中的记录仅是一个字符组。由于操作系统中的文件仅是一维的连续字符序列为了用户存取和加工的方便将文件中的信息划分为若干组其中每一组信息称作一个记录其二为数据库文件文件中的记录带有结构是数据项的集合。记录是文件中可以存取的数据基本单位数据项是文件中可以使用的数据最小单位。三、记录中能识别不同记录的数据项被称为关键字若该数据项能唯一识别一个记录则称为主关键字若能识别多个记录则称为次关键字。四、文件的逻辑结构指的是呈现在用户面前的文件中记录之间的逻辑关系文件的物理结构指的是文件中的逻辑记录在存储器中的组织方式。五、文件的操作:.检索:顺序存取:存取“当前记录的”下一个记录直接存取:存取第i个记录按关键字存取:存取其关键字等于给定值的记录。.修改:往文件中插入一个或一批记录从文件中删除一个或一批记录更新文件中某个记录的属性。.排序文件的操作方式可以实时处理或批量处理本章讨论文件的几种常见的物理结构。来自wwwfreekaoyancom转载请注明严蔚敏数据结构教学笔记顺序文件结构特点:记录在文件中的排列顺序是由记录进入存储介质的次序决定的即文件物理结构中记录的排列顺序和文件的逻辑结构中记录的排列顺序一致。顺序文件的具体组织形式有两种:连续文件:次序相继的两个物理记录其存储位置相邻串联文件:物理记录之间的顺序由指针相链。操作特点:.便于进行顺序存取.不便于进行直接存取为取第i个记录必须先读出前i个记录对于磁盘上的等长记录的连续文件可以进行折半查找.插入新的记录只能加在文件的末尾.删除记录时只作标记.更新记录必须生成新的文件。顺序文件的插入、删除和更新操作在多数情况下都采用批处理方式。此时为处理方便通常将顺序文件作成有序文件称作“主文件”同时将所有的操作作成一个“事务文件”(经过排序也成为有序文件)所谓“批处理”就是将这两个文件“合”为一个新的主文件。具体操作相当于“归并两个有序表”但有两点不同:()对于事务文件中的每个操作首先要判别其“合法性”()事务文件中可能存在多个操作是对主文件中同一个记录进行的。批处理的时间分析:假设主文件中含有n个记录事务文件中含有m个记录则对事务文件进行排序的时间复杂度为O(mlogm)内部归并的时间复杂度为O(mn)则总的内部处理的时间为O(mlogmn)假设对外存进行一次读取为s个记录则整个批处理过程中读写外存的次数为第页来自wwwfreekaoyancom转载请注明严蔚敏数据结构教学笔记索引文件一、结构特点:.索引文件由“主文件”和多级“索引”组成。2.索引中的每个记录由“关键字”和“指针”组成。3.通常索引文件中的主文件是无序文件索引是(按关键字有序)的有序文件。4.“索引”是在输入数据建立文件时自动生成。初建时的“索引”为无序文件经过排序后成为有序文件。二、操作的特点:1.检索方式为:直接存取和按关键字存取。“检索”将分两步进行:先查索引然后根据索引中指针所指索取记录。2.插入记录时“记录”插入在主文件的末尾而相应的“索引项”必须插入在索引的合适位置上。因此最好在建索引表时留有一定“空位”。3.删除记录时仅需删除索引表中相应的索引项即可。4.更新记录时应将更新后的记录插入在主文件的末尾同时修改相应的索引项。三、“索引”的结构1.多级静态索引此时的索引文件结构:第页来自wwwfreekaoyancom转载请注明严蔚敏数据结构教学笔记第页对主文件中每个记录建立一个索引项:主关键字记录在主文件中的存储位置称作稠密索引由这些索引项构成索引表从索引表建立的索引称查找表其中每个索引项为:最大关键字其所在数据块的存储位置称这类索引为非稠密索引。类似地由查找表建立的索引为第二查找表由第二查找表建立的索引为第三查找表。按关键字进行检索时从第三查找表开始至多访问外存五次。2.动态索引索引表采用查找树表或哈希表。优点:不需要建立多级索引初建索引不需要进行排序插入或删除记录时修改索引方便用查找树表作索引时查找索引所需访问外存次数的最大值恰为查找树的深度。可以作索引的树表有:二叉排序树、B树和键树稠密索引的优点是可以实现“预查找”缺点是索引表占用的存储空间大。索引顺序文件结构特点:主文件按主关键字有序对一组记录建立一个索引项(建立非稠密索引)。有两种典型的索引顺序文件一、ISAM文件ISAM(IndexSequentialAccessMethod)(索引顺序存取方法)是一种专为磁盘存取设计的文件组织方法。来自wwwfreekaoyancom转载请注明严蔚敏数据结构教学笔记1.文件的组织方式:主文件按柱面集中存放同时建立三级索引:磁道索引、柱面索引和主索引。磁道索引结构关键字指针关键字指针基本索引项溢出索引项2.操作的特点:检索:可有两种方式:顺序存取依关键字最小至大顺序存取按关键字存取从主索引开始到柱面索引到磁道索引最后取得记录先后访问四次外存。插入:将记录插入在某个磁道的合适位置上第页来自wwwfreekaoyancom转载请注明严蔚敏数据结构教学笔记将该磁道上关键字最大的记录移出到本柱面的溢出区中修改本磁道的索引项(包括基本索引项和溢出索引项)。删除:在被删记录当前存储位置上作“删除标记”。3.文件重组在经过多次的插入和删除操作之后大量的记录进入文件的“溢出区”而“基本存储区”中出现很多已被删去的记录空间此时的文件结构很不合理。因此对ISAM文件需要周期地进行重整。4.柱面索引的位置ISAM文件占有多个柱面其柱面索引应设在数据文件的中间位置上以使“磁头”的平均移动距离最小。二、VSAM文件VSAM(VistualStorageAccessMethod)文件是利用操作系统中提供的虚拟存储器的功能组织的文件免除了用户为读写记录时直接对外存进行的操作对用户而言文件只有控制区间和控制区域等逻辑存储单位。1.文件的结构由索引集、顺序集和数据集三部分组成。数据集内含若干控制区域而控制区域内含若干控制区间每个控制区间内含一个或多个记录当含多个记录时同一控制区间内的记录按关键字自小至大有序排列且文件中第一个控制区间中记录的关键字最小第页来自wwwfreekaoyancom转载请注明严蔚敏数据结构教学笔记第页顺序集内存放的是数据集的索引每个控制区间有一个索引项它由两部分信息组成:该控制区间中记录的最大关键字和指向该控制区间的指针。若干相邻控制区间的索引项形成顺序集中的一个结点结点之间用指针相链索引集是顺序集的索引即文件的高层索引项也由最大关键字和指针两部分信息组成。从索引文件的角度看数据集即为主文件而顺序集和索引集构成“索引”。2.控制区间是用户进行一次存取的逻辑单位可看成是一个逻辑磁道。但它的实际大小和物理磁道无关。控制区域由若干控制区间和它们的索引项组成可看成是一个逻辑柱面。VSAM文件初建时每个控制区间内的记录数不足额定数并且有的控制区间内的记录数为零。3.顺序集本身是一个单链表它包含文件的全部索引项同时顺序集中的每个结点即为B树的叶子结点索引集中的结点即为B树的非叶结点。4.文件的操作检索:可进行顺序存取和按关键字存取插入:按关键字大小插入在某个适当的控制区间中当控制区间中的记录数超过文件规定的大小时要“分裂”控制区间必要时还需要“分裂”控制区域删除:必须“真实地”删除记录因此要在控制区间内“移动”记录5.VSAM文件通常被作为大型索引顺序文件的标准组织方式。其优点是:动态地分配和释放空间不需要重组文件能较快地实现对“后插入”的记录的检索其缺点是:占有较多的存储空间一般只能保持约的存储空间利用率。(因此一般情况下极少产生需要分裂控制区域的情况)来自wwwfreekaoyancom转载请注明严蔚敏数据结构教学笔记直接存取文件1.和前几节讨论的文件组织方法不同直接存取文件的特点是由记录的关键字“直接”得到记录在外存上的映象地址。类似于哈希表的构造方法根据文件中关键字的特点设计一种“哈希函数”和“处理冲突的方法”将记录散列到外存储设备上又称“散列文件”。2.哈希文件的结构由于记录在外存上是成组存放的因此允许多个记录映象到同一个地址上。在此称外存储器中存放多个记录的“数据块”为“桶”。因此由哈希函数得到的映象地址为“桶地址”。例如:有一组关键字如下所列{}假设哈希函数为keyMOD每个桶可以容纳个记录(称桶的容量为)则可得哈希文件如下所示:在哈希文件中“冲突”和“溢出”是不同的概念。一般情况下假设桶的大小为m则允许哈希地址产生m次的冲突当发生第m次冲突时才需要进行“冲突处理”对散列文件而言通常采用链地址法出路冲突。为区别起见称直接“散列”的数据块为“基桶”而因“溢出”存放的数据块为“溢出桶”。3.文件的操作检索:只能进行按关键字的查找不能进行顺序查找。检索时先在基桶内进行查找若不存在则再到溢出桶中进行查找。插入:当查找不成功时将记录插入在相应的基桶或溢出桶内。删除:对被删记录作特殊标记。第页来自wwwfreekaoyancom转载请注明严蔚敏数据结构教学笔记第页4.优点:记录随机存放不需要进行排序插入、删除方便存取速度快节省存储空间不需要索引区。缺点:不能进行顺序存取在经过多次插入和删除操作之后需进行“重组文件”的操作。多关键字文件一、多关键字文件的特点除需要对主关键字建立“主索引”外尚需对各个次关键字建立“次索引”。次索引项:次关键字(指向记录的)指针二、次索引的组织方法.多重链表文件特点:将所有具有相同次关键字的记录链接在同一链表中该链表的头指针即为次索引项中“指针域”的值。.倒排文件特点:将所有具有相同次关键字的记录构成一个次索引顺序表此时的次索引顺序表中仅存放记录的“主关键字”或记录的“物理记录号”。次索引项中的“指针”指向相应的次索引顺序表。.次关键字索引表本身的结构可以是顺序表也可以是树表或哈希表视具体的次关键字的特性而定。学习要点熟悉各类文件的特点构造方法以及如何实现检索插入和删除等操作。

用户评价(0)

关闭

新课改视野下建构高中语文教学实验成果报告(32KB)

抱歉,积分不足下载失败,请稍后再试!

提示

试读已结束,如需要继续阅读或者下载,敬请购买!

评分:

/9

VIP

在线
客服

免费
邮箱

爱问共享资料服务号

扫描关注领取更多福利