《2016年数据结构》教案 第六章 存储管理、查找和排序.docVIP

ch6 存储管理、查找和排序 与前五个实习单元不同，本实习单元旨在集中对几个专门的问题作较为深入的探讨和理解，不强调对某些特定的编程技术的训练。 动态存储管理问题的实习遇到高级语言限制方面的困难。6.1题绕过了这个限制。尽管与实际情况有差距，例如，求得伙伴地址以后不能用它寻址得到伙伴的头，但还是较完整地体现了伙伴系统的主要框架和意图。希望选择此题的读者认真思考:如何修改自己的程序才能得到实用的系统。 6.2题和6.5题集中地探讨了不同的索引技术。散列技术是索引技术中的一种非常重要和有效的技术，但与实际问题(主要是关键字集的形态和特点)关系甚密。哈希函数的选择和冲突解决方法的选用都带有较强的技巧性和经验性，自己动手试一试是非常有益的：平衡树和键树有其一定的实用范围：B树是动态索引文件的一种极好的组织方式，也是物理数据库实现的基本技术。尽管此题难度大了一些，但给读者带来的提高也相应地大些，其中所含的程序设计技巧也比较多。 6.6题除了使读者对各种内部排序方法及效率获得深入理解之外，还可以给读者以启发对于一个一般的问题而言，开发高效算法的可能性如何?应该如何寻找和构造高效算法?6.7题是一个多关键字，的排序问题。 伙伴存储管理系统演示 【问题描述】 伙伴存储管理系统是一种巧妙而有效的方法。试写一个演示系统，演示分配和回收存储块前后的存储空间状态变化。 【基本要求】 程序应不断地从终端读取整数n。每个整数是一个请求。如果n0，则表示用户申请大小为n的空间：如果n0，则表示归还起始地址(即下标)为-n的块才日果n=0，则表示结束运行。每读入一个数，就处理相应的请求，并显示处理之后的系统状态。 系统状态由占用表和空闲表构成。显示系统状态意味着显示占用表中各块的始址和长度，以及空闲表中各种大小的空闲块的始址和长度。 【测试数据】 l，一①1，3，4，4，4，一①4，一①3，2，2，2，2，一②4，一①2，一②2，一③2，一④2，一③4，40，0。其中，③，2表示第③次申请大小为2的空间使得块的始址。其余类推。 【实现提示】 可以取m=5，即Spacesize=25，数据结构如下: Typedef strut BlkHeader{ BlkHeader *llink，*rlink int tag； Int kvalue； Int blkstart； //块起始地址 BlkHeader，*Link Typedef struct{ Int blksize； Link first； }ListHeader； Typedef char ell； //cell也可以是其他单位 主要变量是: cell spaceSpacesize] //被管理的空间 ListHeaderavail[m+1]； //可用空间表 Link ailocated.//占用表的表头指针 在这里，我们把每块的块头分离出来，通过blkstart域与相应的块建立联系。每个块一旦被分配，其块头就进入占用表，其中的各块头由rlink域链接在一起。tag域实际上不起作用，但为了与实际伙伴管理系统更接近，没有把它去掉。显然，在这种模拟实现方法中，不对数组space作任何引用或赋值。 【选作内容】 1)同时还用直观的图示方式显示状态。 2)写一个随机地申请和归还各种规格的存储块的函数考验你的伙伴系统。 哈希表设计 【问题描述】 针对某个集体(比如你所在的班级中的人名设计一个哈希表，使得平均查找长度不超过R，完成相应的建表和查表程序。 【基本要求】 假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用伪随机探测再散列法处理冲突。 【测试数据】 取读者周围较熟悉的30个人的姓名。 【实现提示】 如果随机函数自行构造，则应首先调整好随机函数，使其分布均匀。人名的长度均不超过19个字符(最长的人名如z庄双双(ZhangStmarlgShang〉。字符的取码方法可直接利用C语言中的toascii函数，并可对过长的人名先作折叠处理。 【选作内容】 1)从教科书上介绍的几种晗希函数构造方法中选出适用者并设计几个不同的哈希函数，比较它们的地址冲突率(可以用更大的名字集合作试验〉。 (2研究这30个人名的特点，努力找一个晗希函数，使得对于不同的拼音名一定不发生地址冲突。 3)在哈希函数确定的前提下尝试各种不同处理冲突的方法，考查平均查找长度的变化和造好的晗希表中关键字的聚簇性。 图书管理 【问题描述】 图书管理基本业务活动包括:对一本书的采编入库、清除库存、借阅和归还等等。试设计一个图书管理系统，将上述业务活动借助于计算机系统完成。 【基本要求】 〈1〉每种书的登记内容至少