一、线性表的查找
1. 顺序查找法。它的执行效率比较低。不适合大数据量的查找。但简法简单,容易实现,所以对于小数据量的查找比较适合。
2. 折半查找法。它的特点是执行效率高,但对于要查找的对象也有要求,即线性表必须有序。而且它对于数据的存储也是有要求的,必须为顺序表而不能是链式表。所以通过上面折半查找法的要求可知,折半查找法适合于对删除添加操作少,有序的顺序表的查找操作
3. 分块查找(Blocking Search)又称索引顺序查找。它是一种性能介于顺序查找和二分查找之间的查找方法。
(1)首先查找索引表
索引表是有序表,可采用二分查找或顺序查找,以确定待查的结点在哪一块。
(2)然后在已确定的块中进行顺序查找
由于块内无序,只能用顺序查找。
在实际应用中,分块查找不一定要将线性表分成大小相等的若干块,可根据表的特征进行分块。
【例】一个学校的学生登记表,可按系号或班号分块。
分块查找的优点是:
①在表中插入或删除一个记录时,只要找到该记录所属的块,就在该块内进行插入和删除运算。
②因块内记录的存放是任意的,所以插入或删除比较容易,无须移动大量记录。
分块查找的主要代价是增加一个辅助数组的存储空间和将初始表分块排序的运算。
阅读(2102) | 评论(2) | 转发(0) |