神马品牌网英国本科专业学费:哪个朋友帮忙弄个程序设计,题目"二分查找与分块查找算法的比较"
来源：百度文库 编辑：神马品牌网 时间：2024/05/08 05:26:08
2． 基本要求：
a) 用模块化设计思想来完成程序的设计
b) 在VC中调试完成
3． 创新要求：
用函数完成
三、设计方法和基本原理：
1． 问题描述：
二分查找：
二分查找要求线性表中的结点必须按关键字值得递增或递减的顺序排列。它首先用要查找的关键字k与中间位置的节点的关键字进行比较，这个中间结点把线性表分成了两个子表，若比较结果相等，则查找完成；若不相等，再根据k与该中间结点关键字的比较大小的确定下一步查找哪个子表。就这样递归进行下去，直到找到满足条件的节点或者该线性表中没有这样的点。
分块查找：
分块查找又称为索引顺序查找，其性能介于顺序查找和二分查找之间。分块查找把线性表分成若干块，每一块中的元素存储顺序是任意的，但是块与块之间必须按关键字大小有序排列。
即前一块中的最大关键字小于后一块中的最小关键字值。另外还需要建立一个索引表，索引表的一项对应线性表中的一块。索引项由键域和链域组成。键域存放相应块的最大关键字，链域存放指向本块的第一个结点的指针。索引表按关键字值递增顺序排列。
分块查找的函数分两步进行，首先确定待查找的节点属于哪一块。然后在块内查找要查的点。由于索引表是递增有序的，采用二分查找时，块内个数较少。采用顺序查找，不会对执行速度有太大影响。
要求：分别实现二分查找与分块查找算法的比较，并进行定性分析，定性分析，包括平均查找长度等。
2． 问题的解决方案：
程序中输入要排序的数据，所有功能都用函数完成。
四、主要技术问题的描述：
注意，数据可用数组存储。
a) 用模块化设计思想来完成程序的设计
b) 在VC中调试完成
3． 创新要求：
用函数完成
三、设计方法和基本原理：
1． 问题描述：
二分查找：
二分查找要求线性表中的结点必须按关键字值得递增或递减的顺序排列。它首先用要查找的关键字k与中间位置的节点的关键字进行比较，这个中间结点把线性表分成了两个子表，若比较结果相等，则查找完成；若不相等，再根据k与该中间结点关键字的比较大小的确定下一步查找哪个子表。就这样递归进行下去，直到找到满足条件的节点或者该线性表中没有这样的点。
分块查找：
分块查找又称为索引顺序查找，其性能介于顺序查找和二分查找之间。分块查找把线性表分成若干块，每一块中的元素存储顺序是任意的，但是块与块之间必须按关键字大小有序排列。
即前一块中的最大关键字小于后一块中的最小关键字值。另外还需要建立一个索引表，索引表的一项对应线性表中的一块。索引项由键域和链域组成。键域存放相应块的最大关键字，链域存放指向本块的第一个结点的指针。索引表按关键字值递增顺序排列。
分块查找的函数分两步进行，首先确定待查找的节点属于哪一块。然后在块内查找要查的点。由于索引表是递增有序的，采用二分查找时，块内个数较少。采用顺序查找，不会对执行速度有太大影响。
要求：分别实现二分查找与分块查找算法的比较，并进行定性分析，定性分析，包括平均查找长度等。
2． 问题的解决方案：
程序中输入要排序的数据，所有功能都用函数完成。
四、主要技术问题的描述：
注意，数据可用数组存储。