分块查找课程设计精选.doc

目 录 1实践的目的与要求 1 1.1 实践目的 1 1.2 课程设计要求 1 2 分块查找概述 1 2.1 分块查找简介 1 2.2 基本思想 1 2.3 分块查找的优点 2 3 分块查找的步骤 2 3.1 方法描述 2 3.2 假设 3 4 流程图 4 5 编码 4 6 测试结果及运行结果 5 7 总结 7 8 系统开发所用到的技术 7 参考文献 9 附录 全部代码 10 1实践的目的与要求分块查找是折半查找和顺序查找的一种改进方法，折半查找虽然具有很好的性能，但其前提条件时线性表顺序存储而且按照关键码排序，这一前提条件在结点树很大且表元素动态变化时是难以满足的。而顺序查找可以解决表元素动态变化的要求，但查找效率很低。如果既要保持对线性表的查找具有较快的速度，又要能够满足表元素动态变化的要求，则可采用分块查找的方法。分块查找的速度虽然不如折半查找算法，但比顺序查找算法快得多，同时又不需要对全部节点进行排序。当节点很多且块数很大时，对索引表可以采用折半查找，这样能够进一步提高查找的速度。分块查找由于只要求索引表是有序的，对块内节点没有排序要求，因此特别适合于节点动态变化的情况。当增加或减少节以及节点的关键码改变时，只需将该节点调整到所在的块即可。在空间复杂性上，分块查找的主要代价是增加了一个辅助数组。 需要注意的是，当节点变化很频繁时，可能会导致块与块之间的节点数相差很大，没写快具有很多节点，而另一些块则可能只有很少节点，这将会导致查找效率的下降。 分块查找要求把一个大的线性表分解成若干块，每块中的节点可以任意存放，但块与块之间必须排序。假设是按关键码值非递减的，那么这种块与块之间必须满足已排序要求，实际上就是对于任意的i，第i块中的所有节点的关键码值都必须小于第i+1块中的所有节点的关键码值。建立一个索引表，把每块中的最大关键码值作为索引表的关键码值，按块的顺序存放到一个辅助数组中，显然这个辅助数组是按关键码值费递减排序的。查找时，首先在索引表中进行查找，确定要找的节点所在的块。由于索引表是排序的，因此，对索引表的查找可以采用顺序查找或折半查找然后，在相应的块中采用顺序查找，即可找到对应的节点。 所以分块查找的平均查找长度不仅与查找表的n有关，而且和每一块中的记录个数s有关。所以在给定了长度为n的查找表的前提下，每块中的记录个数d是可变的。容易证明，当s=时，ASLbs =+1，值最小。 若采用折半查找确定待查找记录所在块，那么，分块查找的平均查找长度为： ASLbs=ASLb+ASLw=log2(b+1)+ = log2(+1)+ 由此可见，分块查找的效率是介于顺序查找和折半查找之间的。它比顺序查找的执行速度更要快，比折半查找的执行速度要慢。 分块查找的步骤 3.1 方法描述 在查找表中的18个记录分成三个子表（R1，R2，…，R6）,(R7，R8，..,R12),(R13，R14，…,R18)，每个子表为一块。首先用待查给定值K在索引表查找，然后再已确定的块中进行顺序查找，当查找表示有序表时，在块中也可用二分查找。 3.2 假设 假设，如图3.1中，如果给定值K=36，则先用K和索引表各关键字进行比较，因为22K48，则关键字为36的记录若果存在，必定在第二个子表块中，然后从第二个字表块的第一个记录的位置序号7开始，按记录顺序查找，知道确定第10个记录是要找的记录为止，查找成功。又如当K=26时，则仍在第二个字表中查找，自第7个记录起按记录顺序查找至第12个记录，每个记录的关键字和K比较都不想等，则查找失败。 引索表 关键字值 22 48 86 块起始地址 1 7 13 22 11 12 8 10 20 30 42 44 36 25 48 60 55 74 49 86 55 查找表 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 第一子表快 第二子表块 第三子表块 图3.1 分块查找表结构示意图 流程图 编码 函数流程： struct searchtable //索引表结构体 创建索引表(程序开始)— 输入关键字数据— 自动生成索引表— 赋值并输出索引表— 循环寻找下一个反之跳出循环— 找到元素反之越界找不到元素（程序结束） #includestdio.h #includestdlib.h #includeiostream.h int table[]={22,11,12,8,10,20,30,42,44,36,25,48,60,55,74,49,86,55}; //list_1.h { int stelem; //关键字数据 int location; //关键字位置 } 测试结果及运行结果 如图6.1，运行程序后的界面，按待查找的线性表给