分块查找课程设计

《分块查找课程设计》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、目录1实践的目的与要求11.1实践目的11.2课程设计要求12分块查找概述12.1分块查找简介12.2基本思想12.3分块查找的优点23分块查找的步骤23.1方法描述23.2假设34流程图45编码46测试结果及运行结果57总结78系统开发所用到的技术7参考文献9附录全部代码101实践的目的与要求1.1实践目的采用分块查找的方法查找指定的关键码1.2课程设计要求1）可以循环查找，可以选择退出；2）分别采用顺序存储和链式存储完成分块查找，其中在顺序存储结果下，索引表的查找采用二分查找；3）分别用函数完成索引表查找和块

2、中查找；4）每一个函数要有必要的注释，在课程设计论文中有流程图。2分块查找概述2.1分块查找简介分块查找是折半查找和顺序查找的一种改进方法，折半查找虽然具有很好的性能，但其前提条件时线性表顺序存储而且按照关键码排序，这一前提条件在结点树很大且表元素动态变化时是难以满足的。而顺序查找可以解决表元素动态变化的要求，但查找效率很低。如果既要保持对线性表的查找具有较快的速度，又要能够满足表元素动态变化的要求，则可采用分块查找的方法。分块查找的速度虽然不如折半查找算法，但比顺序查找算法快得多，同时又不需要对全部节点进行排序

3、。当节点很多且块数很大时，对索引表可以采用折半查找，这样能够进一步提高查找的速度。分块查找由于只要求索引表是有序的，对块内节点没有排序要求，因此特别适合于节点动态变化的情况。当增加或减少节以及节点的关键码改变时，只需将该节点调整到所在的块即可。在空间复杂性上，分块查找的主要代价是增加了一个辅助数组。需要注意的是，当节点变化很频繁时，可能会导致块与块之间的节点数相差很大，没写快具有很多节点，而另一些块则可能只有很少节点，这将会导致查找效率的下降。2.2基本思想1）分块查找要求把一个大的线性表分解成若干块，每块中的节

4、点可以任意存放，但块与块之间必须排序。假设是按关键码值非递减的，那么这种块与块之间必须满足已排序要求，实际上就是对于任意的i，第i块中的所有节点的关键码值都必须小于第i+1块中的所有节点的关键码值。2）13建立一个索引表，把每块中的最大关键码值作为索引表的关键码值，按块的顺序存放到一个辅助数组中，显然这个辅助数组是按关键码值费递减排序的。1）查找时，首先在索引表中进行查找，确定要找的节点所在的块。由于索引表是排序的，因此，对索引表的查找可以采用顺序查找或折半查找。然后，在相应的块中采用顺序查找，即可找到对应的节点

5、。2.3分块查找的优点在线性表中插入或删除一个元素时，只要找到相应的块，然后在该块内进行插入或删除即可。由于块内元素个数相对较少，而且是任意存放的，所以插入或删除比较容易，不需要移动大量的元素。由于分块查找的过程是分两步进行的，所以在查找表中查找一个待查找记录的ASL为：ASLbs=ASLb+ASLw其中：ASLb是在索引表中查找记录所在块的平均查找长度；ASLw是在块中查找待查找记录的平均查找长度。假设将长度为n的查找表均匀地分为b块，每块含有s个记录，即「n/s」，再假设查找表中查找每一个记录的概率相等，则查

6、找索引表的概率为1/b，在块中查找待查找记录的概率为1/s。1)若采用顺序查找确定待查找记录所在块，那么，分块查找的平均查找长度为：ASLbs=ASLb+ASLw=所以分块查找的平均查找长度不仅与查找表的n有关，而且和每一块中的记录个数s有关。所以在给定了长度为n的查找表的前提下，每块中的记录个数d是可变的。容易证明，当s=时，ASLbs=+1，值最小。2)若采用折半查找确定待查找记录所在块，那么，分块查找的平均查找长度为：ASLbs=ASLb+ASLw=log2(b+1)+=log2(+1)+由此可见，分块查找

7、的效率是介于顺序查找和折半查找之间的。它比顺序查找的执行速度更要快，比折半查找的执行速度要慢。3分块查找的步骤3.1方法描述在查找表中的18个记录分成三个子表（R1，R2，…，R6）,(R7，R8，..,R12),(R13，R14，…13,R18)，每个子表为一块。首先用待查给定值K在索引表查找，然后再已确定的块中进行顺序查找，当查找表示有序表时，在块中也可用二分查找。3.2假设假设，如图3.1中，如果给定值K=36，则先用K和索引表各关键字进行比较，因为22

8、子表块中，然后从第二个字表块的第一个记录的位置序号7开始，按记录顺序查找，知道确定第10个记录是要找的记录为止，查找成功。又如当K=26时，则仍在第二个字表中查找，自第7个记录起按记录顺序查找至第12个记录，每个记录的关键字和K比较都不想等，则查找失败。引索表关键字值224886块起始地址171322111281020304244362548605574498655查找表