程序设计与数据结构.ppt

《程序设计与数据结构.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、数据结构第8章文件山东大学管理学院2021/9/8山东大学管理学院戚桂杰姚云鸿2本章内容文件概述顺序文件直接文件索引文件倒排文件2021/9/8山东大学管理学院戚桂杰姚云鸿3§1文件概述一、文件的概念域（Field）是数据的基本单位，又称为字段或数据项。域通常用于描述数据对象的属性，不可分割的域含有一个简单的值。记录（Record）是一组相关域的集合，它可以看作是应用程序的一个单元。根据设计的不同，记录可以是固定长或可变长。如果记录中某些域的长度是可变的，则该记录就是可变长度的记录。文件（File）是由大量性质相同的记录组成的集合，它被应

2、用程序看作是一个实体。文件有一个惟一的名字，可以被创建或删除。数据库（Database）是一组相关的数据，它的本质特征是数据单元间存在明确的关系，并且设计成可供许多不同的应用程序使用。数据库自身是由一种或多种不同类型的文件组成。2021/9/8山东大学管理学院戚桂杰姚云鸿4二、文件的逻辑结构文件的逻辑结构是用户能观察到的，可加以处理的数据集合。文件的逻辑结构分两种形式：一种是流式文件，另一种是记录式文件。记录成组与分解处理流式文件指文件内的数据不再组织成记录，只是连续的字符序列。记录式文件是指若干逻辑记录（按信息在逻辑上的独立含意划分的一

3、个信息单位）的集合。逻辑记录1逻辑记录2逻辑记录3物理记录逻辑记录用户缓冲区系统缓冲区2021/9/8山东大学管理学院戚桂杰姚云鸿5三、文件的物理结构构造文件物理结构的方法：计算法和指针法。四、文件的操作记录检索记录插入记录删除记录更新文件排序实现原理是设计映射算法，通过对记录关键字的计算转换成对应的物理块地址，从而找到所需记录。置专门指针，指明相应记录的物理地址或表达各记录之间的关联。2021/9/8山东大学管理学院戚桂杰姚云鸿6§2顺序文件分块块插值查找算法：（1）初始化low=1；high=N。（2）反复执行下面操作，直到high＜

4、low成立(a)i=(b)读取第i个物理块，获得Li和Hi(c)分下面三种情况执行Li≤K≤Hi时，查找成功，第i个物理块即为所求;K＞Hi时，执行low=i+1;K＜Li时，执行high=i-1;(3)查找失败，算法结束。low:查找范围内的最小物理块号；high:查找范围内的最大物理块号；Li：第i个物理块内的记录的最小关键字；Hi：第i个物理块内的记录的最大关键字2021/9/8山东大学管理学院戚桂杰姚云鸿7§3直接文件（散列文件）直接文件：记录在介质上的位置是通过对记录的键施加变换而获得相应地址。一、桶散列（静态散列）基本思想：把

5、文件的记录通过散列函数H分别存储在许多存储桶中，每个存储桶包含一个或多个物理块，一个存储桶中的物理块用指针连接形成链表，每个物理块存放若干记录。如果一个桶溢出，即它容纳不下所有属于它的记录，那么可以给该存储桶增加一个溢出块链表以存放更多的记录。操作：以i=H(key)为依据完成查找、插入、删除、更新等操作。2021/9/8山东大学管理学院戚桂杰姚云鸿8§3直接文件（散列文件）二、可扩展散列（动态散列文件）可散列文件的组织方式：散列函数H把关键字key转换成一个定长的二进制位串k′（伪关键字），取k′前i位二进制数（设为k〞）作为存储桶目录

6、表中的目录项号，即表示目录表中第k〞个目录项，目录项中的指针指向的物理块就是具有关键字key的记录所在的物理块；存储桶目录项的个数为2i。i确定记录在该物理块中的成员资格的二进制位串的位数2021/9/8山东大学管理学院戚桂杰姚云鸿9查找操作查找关键字为K的记录，先计算出H（K），取出这一二进制位串的前i位（设为k〞），并找到序号为k〞的存储桶目录项。根据此目录项的指针找到物理块B。插入操作为了插入关键字为K的记录，先其所在的物理块，若该物理块中有空闲空间，我们就把新记录存入，插入操作完成。如果B中没有空闲空间，那么根据数字i的不同有两种

7、可能：如果j=i，那么我们必须先将i加1，使存储桶目录项个数增加一倍，即2i+1。在新存储桶目录表中，序号为k〞0和k〞1（分别用0和1扩展k〞）的项都指向原k〞目录项指向的物理块。2021/9/8山东大学管理学院戚桂杰姚云鸿10插入操作如果j＜i（j的值可在每个物理块的“小凸块”中找到），那么不必对存储桶目录表做任何变化。按下面规则操作：（a）将物理块B分裂成两个存储块。（b）根据记录关键字的散列值的第j+1位，将B中的记录分配到这两个存储块中，该位为0的记录继续保留在B中，而该位为1的记录放入到新块中。（c）把j+1存储到两个存储块的

8、“小凸块”中，以标明用于确定成员资格的二进制位数。（d）调整存储桶目录项中指针，使原来指向块B的指针项指向块B或新块，这由记录关键字的散列值的第j+1位决定。注意，分裂B可能解决不了问题，因为