分块查找课程设计讲述.doc

 目 录  TOC \o 1-3 \h \z \u  HYPERLINK \l _Toc439957152 1实践的目的与要求  PAGEREF _Toc439957152 \h 1  HYPERLINK \l _Toc439957153 1.1 实践目的  PAGEREF _Toc439957153 \h 1  HYPERLINK \l _Toc439957154 1.2 课程设计要求  PAGEREF _Toc439957154 \h 1  HYPERLINK \l _Toc439957155 2 分块查找概述  PAGEREF _Toc439957155 \h 1  HYPERLINK \l _Toc439957156 2.1 分块查找简介  PAGEREF _Toc439957156 \h 1  HYPERLINK \l _Toc439957157 2.2 基本思想  PAGEREF _Toc439957157 \h 1  HYPERLINK \l _Toc439957158 2.3 分块查找的优点  PAGEREF _Toc439957158 \h 2  HYPERLINK \l _Toc439957159 3 分块查找的步骤  PAGEREF _Toc439957159 \h 2  HYPERLINK \l _Toc439957160 3.1 方法描述  PAGEREF _Toc439957160 \h 2  HYPERLINK \l _Toc439957161 3.2 假设  PAGEREF _Toc439957161 \h 3  HYPERLINK \l _Toc439957162 4 流程图  PAGEREF _Toc439957162 \h 4  HYPERLINK \l _Toc439957163 5 编码  PAGEREF _Toc439957163 \h 4  HYPERLINK \l _Toc439957164 6 测试结果及运行结果  PAGEREF _Toc439957164 \h 5  HYPERLINK \l _Toc439957165 7 总结  PAGEREF _Toc439957165 \h 7  HYPERLINK \l _Toc439957166 8 系统开发所用到的技术  PAGEREF _Toc439957166 \h 7  HYPERLINK \l _Toc439957167 参考文献  PAGEREF _Toc439957167 \h 9  HYPERLINK \l _Toc439957168 附录 全部代码  PAGEREF _Toc439957168 \h 10   PAGE 13 1实践的目的与要求 1.1 实践目的 采用分块查找的方法查找指定的关键码 1.2 课程设计要求 可以循环查找，可以选择退出； 分别采用顺序存储和链式存储完成分块查找，其中在顺序存储结果下，索引表的查找采用二分查找； 分别用函数完成索引表查找和块中查找； 每一个函数要有必要的注释，在课程设计论文中有流程图。 2 分块查找概述 2.1 分块查找简介 分块查找是折半查找和顺序查找的一种改进方法，折半查找虽然具有很好的性能，但其前提条件时线性表顺序存储而且按照关键码排序，这一前提条件在结点树很大且表元素动态变化时是难以满足的。而顺序查找可以解决表元素动态变化的要求，但查找效率很低。如果既要保持对线性表的查找具有较快的速度，又要能够满足表元素动态变化的要求，则可采用分块查找的方法。分块查找的速度虽然不如折半查找算法，但比顺序查找算法快得多，同时又不需要对全部节点进行排序。当节点很多且块数很大时，对索引表可以采用折半查找，这样能够进一步提高查找的速度。 分块查找由于只要求索引表是有序的，对块内节点没有排序要求，因此特别适合于节点动态变化的情况。当增加或减少节以及节点的关键码改变时，只需将该节点调整到所在的块即可。在空间复杂性上，分块查找的主要代价是增加了一个辅助数组。 需要注意的是，当节点变化很频繁时，可能会导致块与块之间的节点数相差很大，没写快具有很多节点，而另一些块则可能只有很少节点，这将会导致查找效率的下降。 2.2 基本思想 分块查找要求把一个大的线性表分解成若干块，每块中的节点可以任意存放，但块与块之间必须排序。假设是按关键码值非递减的，那么这种块与块之间必须满足已排序要求，实际上就是对于任意的i，第i块中的所有节点的关键码值都必须小于第i+1块中的所有节点的关键码值。