数据结构的程序实现

数据结构的程序实现内容摘要：

） 即索引顺序存取方法 ， 是一种专为磁盘存取设计的文件组织方式。 由于磁盘是以盘组 、 柱面和磁道三级地址存取的设备 ， 所以可以对磁盘上的数据文件建立盘组 、 柱面和磁道三级索引。 文件的记录在同一盘组上存放时 ， 应先集中放在一个柱面上 ， 然后再顺序存放在相邻柱面上；对同一柱面 ， 则应按盘面的次序顺序存放。 ISAM文件结构举例 ISAM文件（续） 在一个磁盘组上的 ISAM文件 ， 每个柱面建立一个磁道索引 ， 每个磁道索引项由基本索引项和溢出索引项两部分组成 ， 每一部分都包括关键字和指针两个域 ， 前者表示该磁道中最大关键字 ， 后者指示该磁道中第一个记录的位置。 柱面索引的每一个索引项也由关键字和指针两部分组成 ， 前者表示该柱面中的最大关键字 ， 后者指示该柱面上的磁道索引位置。 柱面索引存放在某个柱面上 ， 若柱面索引较大占多个磁道时 ， 则可建立柱面索引的一个主索引。 ISAM文件（续）  在 ISAM文件上检索记录时 ， 先从主索引出发找到相应的柱面索引 ， 再从柱面索引找到记录所在柱面的磁道索引 ， 最后从磁道索引找到记录所在磁道的第一个记录的位置 ， 由此出发在该磁道上进行顺序查找直至找到为止；反之 ， 若找遍磁道而不存在此记录 ， 则表明文件中无此记录。 在前例中为每个柱面开辟了一个溢出区 ， 并在磁道索引项中有溢出索引项 （ 后面两个域 ） ， 这是为插入记录所设置的。 ISAM文件（续） 由于 ISAM文件中记录是按关键字顺序存放的 ， 在插入一个记录时需要向后移动记录 ， 并将同一磁道上的最后一个记录移至溢出区 ， 同时修改磁道索引项。 除了为每个柱面设置一个溢出区的方法外 ， 还可只集中设置一个大的公共溢出区；也可以既为每个柱面设置溢出区 ， 同时也设置了一个公共溢出区 ， 在柱面溢出区满后再使用公共溢出区。 ISAM文件中删除记录比较简单 ， 只需作删除标记而不用移动记录或改变指针。 当然应该周期性地把记录读入内存重排整理 ISAM文件 ， 以尽量填满基本区而空出溢出区。  VSAM（ virtual storage access method） 即虚拟存储存取方法。 它利用了操作系统的虚拟存储器的功能 ， 使用户只需考虑控制区间等逻辑存储单位 ， 而无需考虑其物理位置以及何时对外存储器进行读写操作 ，给用户使用文件提供了方便。  VSAM文件的结构由 索引集 、 顺序集 和 数据集 三部分组成。 数据集存放文件的所有记录 ， 顺序集和索引集构成一棵 B+树是文件的索引部分。 数据集中的一个结点称为控制区间 （ control interval） ， 它由一组连续的存储单元组成 ， 是读写操作的基本单位。 VSAM文件的结构举例 VSAM文件（续） 同一文件上的控制区间大小相同 ， 含有一个或多个按关键字升序排列的记录。 顺序集中的一个结点 ， 存放着若干相邻控制区间的索引项 ， 每个索引项由控制区间中的最大关键字和指向该控制区间的指针组成。 顺序集中的一个结点连同其下层所有控制区间形成的整体称作控制区域 （ control range）。 顺序集中的结点之间用指针相链接；在它们上层的结点又以它们为基础形成索引 ， 并逐级向上建立索引 ，形成 B+树的非终端结点。 VSAM文件（续）  对 VSAM文件中记录的检索 ， 既可以从最高层的索引逐层往下按关键字进行查找 ， 又可以在顺序集中沿着指针链顺序查找。 VSAM文件没有专门的溢出区 ， 但可利用控制区间中的空隙或控制区域中空的控制区间来插入记录 （ 即在B+树上插入记录 ）。 在控制区间中插入记录时 ， 为了保证区间内记录按关键字有序需要移动记录；而当区间中记录已满时 ，为了插入记录需要将区间分裂。 在 VSAM文件中删除记录时 ， 也是需要移动记录的。 VSAM文件（续）  VSAM文件占有较多的存储空间 ， 存储空间的利用率一般也只能保持在 75%左右。 然而它具有许多优点 ， 如动态地分配和释放存储空间 ， 无需像 ISAM文件那样定期重排文件 ， 并能较快地执行插入操作和保持较高的检索效率。  VSAM文件通常作为组织大型索引顺序文件的标准形式。 散列文件 （ Hash file） 也称作直接存取文件 ， 它是利用哈希方法组织的数据文件；即根据某个哈希函数和一定的冲突消解策略而得到的存放在外存储器上的散列表。  与哈希表不同的是 ， 磁盘上的文件记录通常是成组存放的。 若干个记录组成一个存储单位 ， 在散列文件中这个存储单位称作桶。 一个桶能存放的逻辑记录的总数称作桶的容量。 假如桶的容量为 m， 即 m个同义词的记录可以存放在同一地址的桶中 ， 当第 m+1个同义词记录出现时则发生溢出。 处理溢出也可采用哈希表中的各种处理冲突的方法 ， 但对散列文件主要是采用链地址法消解冲突。 散列文件（续） 当发生溢出时 ， 需要将第 m+1个同义词存放到另一个桶中 ， 通常称作 “ 溢出桶 ” ；相应地把存放前 m个同义词的桶称作 “ 基桶 ”。 溢出桶可以有多个 ， 它们和基桶大小相同 ， 相互之间用指针相链接。 当在基桶中没有检索到待查记录时 ， 就顺指针所指到溢出桶中去检索； 因此 ， 同一散列地址的溢出桶和基桶在磁盘上的物理位置不要相距太远 ， 最好是在同一柱面上。 散列文件举例 例如 ， 某文件有 20个记录 ， 其关键字分别为 2 1 19 8 2 1 5 6 1 2 3 8 6 17 3 35。 用除留余数法选定哈希函数 H(key)= key%7，用链地址法消解地址冲突。 桶的容量 m=3， 基桶个数 b=7，由此得到的散列文件如下图所示。 散列文件（续）  在散列文件中检索时： 先根据给定的关键字值 k求得哈希地址 ， 即基桶号； 然后将基桶的记录读入内存进行顺序检索 ， 若找到关键字值为 k的记录则检索成功； 若基桶中虽无关键字值为 k的记录但指针域非空 ， 需要把溢出桶中的记录读入内存继续检索 ， 直到检索成功或检索不成功。 检索不成功的情况为基桶没有填满记录 ， 或虽填满但指针域为空 （ 无溢出桶 ） ， 或虽有溢出桶但仍未找到关键字为 k的记录。 散列文件（续） 在散列文件中 ， 装填因子为 ， 其中 n为文件中的记录数 ，b为桶数 ， m为桶的容量；而存取桶数的期望值为。 如上例 ，。 在散列文件中 ， 删除记录时仅需对被删记录作一删除标记即可。 总之 ， 散列文件的 优点 是插入和删除方便 ， 存取速度比索引文件要快；不需要索引区 ， 节省存储空间。 其 缺点 是不能进行顺序存取 ， 只能按关键字随机存取 ， 且询问方式只有简单询问；在经过多次的插入和删除之后 ， 也可能造成溢出桶满而基桶内多数为被删除记录的不合理文件结构 ， 亦需对文件进行重新整理。 多关键字文件 （ multiple key file） 的特点是 ，在对文件进行检索操作时不仅对主关键字进行简单询问 ， 还经常需要对次关键字进行其它类型的询问检索。 因此 ， 对多关键字文件还需要建立一系列的次关键字索引。 次关键字索引和主关键字索引所不同的是 ， 每个索引项应包含次关键字和具有同一次关键字的多个记录的主关键字或物理记录号。 多重表文件 和 倒排文件 是常见的两种多关键字文件组织方法。 多关键字文件（续）  多重表文件 （ multilist file） 的 特点 是 ， 记录按主关键字的顺序构成一个串联文件 ， 并建立主关键字索引 （ 称为主索引 ） ；对每一个次关键字项建立次关键字索引 （ 称为次索引 ） ， 所有具有同一次关键字的记录构成一个链表。 主索引为非稠密索引 ， 一组记录建立一个索引项；次索引为稠密索引 ， 每个记录建立一个索引项 ，每个索引项包括次关键字 、 头指针和链表长度。 多关键字文件举例 例如 ， 下图所示为一个多重表文件。 其中工号为主关键字 ， 记录按工号顺序链接。 多关键字文件举例（续） 对工号非稠密索引分成三个子链表 ， 其索引如下图 (b)所示 ，索引项中的主关键字为各组中关键字的最大值。 职称和专业是两个次关键字项 ， 其索引分别如下图 (c)和 (d)所示 ， 具有相同次关键字值的记录链接在同一链表中。 多关键字文件（续） 有了这些次关键字索引 ， 根据关键字值找到链表头指针 ， 然后从头指针出发可列出链表中所有记录。 比如查询数学专业的教授 ， 可以专业索引表中找到“ 数学 ” 的头指针和表长 ， 逐一读取记录查看哪些记录的职称为教授即可。 此查询也可从职称索引入手进行。 当然 ， 较好的方法是先读长度较短的链表中的记录。  在多重表文件中插入一个记录是容易的 ， 只要修改指针将记录插在链表的头指针之后即可。 然而要删去一个记录却很繁琐 ， 需要在每个次关键字的链表中删去该记录。 多关键字文件（续）  倒排文件 （ inverted file） 和 多重表文件 的区别在于次关键字索引的结构不同。 倒排文件的次关键字索引称为 倒排表 ， 在倒排表的索引项中没有头指针和链长度 ， 而是直接用一个项存放具有同一关键字的所有记录的物理记录号或主关键字值。 值得注意的是 ， 倒排表中具有同一次关键字的记录号是有序排列的。 上例的倒排表如下图所示： 多关键字文件（续） 倒排表作索引的 好处 在于检索记录较快。 特别是对某些询问 ， 不用读取记录就可得到答案。 例如上例查询数学专业教授 ， 只要将 “ 数学 ” 索引中的记录号和 “ 教授 ” 索引中的记录号求集合的交集运算就可以了 ， 即 {2， 5， 9}∩{2， 6}={2}就得到记录号为 2者便是数学教授。  在插入和删除记录时 ， 倒排表也要进行相应修改；需要移动索引项中记录号以保持其有序排列。 若数据文件是索引顺序文件 （ 如 ISAM文件 ） ， 倒排表中应存放记录的主关键字而不是物理记录号。  倒排文件的 缺点 是维护困难。 同一倒排表中各项长度不同 ，不同倒排表的长度也不同 ， 这些都给倒排文件的维护带来一定的困难。 大批量数据的组织策略 文件的组织 数据库技术 文件系统的缺陷 利用文件组织大批量数据是数据组织中行之有效的方法 ， 然而 ，文件系统也存在着一些明显的缺陷。 如： 数据冗余大。 因为每个文件都是为特定用途设计的 ， 因此会造成同样的数据在多个文件中的重复存储。 数据的不一致性 ， 这往往是由于数据冗余所造成的；在数据更新时 ， 稍有不慎就会造成同一数据在不同文件中的不一致。 程序和数据之间的独立性差。 应用程序依赖于文件的存储结构 ， 使得在对文件的存储结构进行修改时 ， 必须修改应用程序。 数据联系弱。 文件与文件之间是独立的 ， 文件之间的联系必须通过程序来构造。 因此 ， 文件系统是一个不具有弹性的无结构的数据集合 ， 难以反应客观世界中事物之间的联系。 数据库技术诞生 为了克服上述文件系统的不足 ， 20世纪 60年代后期开始诞生了解决大批量数据组织和管理的数据库技术。 数据库技术诞生的标志性事件是： 1968年研制成功 ， 1969年形成产品的美国 IBM公司的数据库管理系统 IMS（ information management system） 的问世 ， 该系统支持的是层次数据模型。 美国数据系统语言协会 CODASYL（ conference on data system language） 下属的数据库任务组 DBTG（ database task group） 对数据库方法进行了系统的研究 ， 在 20世纪 60年代末期和 70年代初期发表了若干个报告 （ 称为 DBTG报告 ） ， 该报告建立了数据库的许多概念 、 方法和技术。 DBTG所提议的方法是基于网状数据模型的。 从 1970年起 ， IBM的研究员 ， 提出了数据库的关系模型 ， 开创了数据库关系方法和关系数据理论的研究 ， 为关系数据库的发展和理论研究奠定了基础。 数据库技术  数据库技术发展到现在 ， 已经是一门非常成熟的技术 ， 作为算法与数据结构课程的后续课程。  概括地讲 ， 数据库具有如下基本特征： 数据库是相互关联的数据的集合。 数据库用综合的方法组织数据 ， 并保证尽可能高的访问效率。 数据库具有较小的数据冗余 ， 可供多个用户共享。 数据库具有较高的数据独立性。 数。