Chow's Notes

查找

发表于 | 分类于 |

1.顺序表查找算法：复杂度O[n]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int  quen_ search(int *a,int n,int key){
　　int i;
　　for(i=1;i<n;i++){
　　　　if(a[i]==key){
　　　　　　return i;
　　　　}
　　}
　　return 0;
}

优化后的：(避免每次i与n比较)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int quen_search2(int *a,int n,int key){
　　int i=n;
　　a[0]=key;
　　while(a[i]!=key){
　　　　i--;
　　}
　　return i;
}

2.有序表查找：

折半查找：复杂度O[logn],适用于有序静态查找表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def bsearch2(lst, key):
　　low = 1
　　high = len(lst) - 1
　　while(low < high):
　　　　mid = (low + high) / 2
　　　　if(key < lst[mid]):
　　　　　　high = mid - 1
　　　　elif(key > lst[mid]):
　　　　　　low = mid + 1
　　　　else:
　　　　　　return mid
　　return 0
print bsearch2([0,1, 2, 3, 4, 5, 6], 7)

插值查找：时间复杂度O[logn],对于表长较大，而关键字分布又比较均匀的查找表，插值查找方法的性能比折半要好

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def bsearch2(lst, key):
    low = 1
    high = len(lst) - 1
    while(low < high):
        mid = low + (high - low) * ((key - lst[low]) / (lst[high] - lst[low]))
        if(key < lst[mid]):
            high = mid - 1
        elif(key > lst[mid]):
            low = mid + 1
        else:
            return mid
    return 0
 
print bsearch2([0, 1, 2, 3, 4, 5, 6], 7)

斐波那契查找：黄金分割点（略）p228

三种有序表的查找本质上是分割点的不同，各有优劣，实际中要根据数据的特点综合考虑做出选择

3.线性索引查找：

索引就是把一个关键字与它对应的记录相关联的过程，一个索引由若干个索引项构成，每个索引项至少包含关键字和其对应的记录在存储器的位置等信息。索引技术是组织大型数据库以及磁盘文件的一种重要技术

线性索引就是将索引项组织为线性结构，即索引表，

三种线性索引：稠密索引、分块索引和倒排索引

稠密索引：是在索引表中，将数据集中的每个记录对应一个索引项（索引项与数据集的记录个数相同，空间代价大）

对于稠密索引这个索引表来说，索引项一定是按照关键码有序的排列

分块索引：（图书分类）普遍用于数据库表查找等技术的应用当中

分块有序，是把数据集的记录分成了若干块，并且这些块需要满足两个条件：块内无序，块间有序。对于分块有序的数据集，将每块对应一个索引项，这种索引方法叫做分块索引。分块索引的索引项结构分三个数据项：最大关键码（存储每一块中的最大关键字），块中记录的个数，指向块首数据元素的指针。查找分为两步：A.在分块索引表中查找要查关键字所在的块。B.根据块首指针找到相应的块，并在块中顺序查找关键码

倒排索引：（最基础的搜索引擎技术）

索引项的通用结构：次关键码，记录号表

记录号表存储具有相同次关键字的所有记录的记录号（可以是指向记录的指针或该记录的主关键字）。这样的索引方法就是倒排索引（由于不是由记录来确定属性值，而是有属性值来确定记录的位置）

4.二叉排序树（动态查找表：需要在查找时删除或插入的查找表）

二叉排序树（二叉查找树）：一颗空树或者具有下列性质的二叉树：若它的左子树不为空，则左子树上所有节点的值均小于它的根节点的值，右子树则大于，同样他的左右子树也是二叉排序树（递归定义）

查找，插入，删除操作p342

二叉排序树的平衡算法：

平衡二叉排序树：是一种二叉排序树，其中每一个节点的左子树和右子树的高度差至多等于1

红黑树

5.散列表查找（哈希表）

散列表：

存储位置=f(关键字)

在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使得每个关键字key对应一个存储位置f(key).

对应关系f称为散列函数，又称哈希函数。采用散列技术将记录存储在一块连续的存储空间中，这块连续的存储空间称为散列表或哈希表

散列过程：

在存储时，通过散列函数计算记录的散列地址，并按此散列地址存储改记录。

当查找记录时，我们通过同样的散列函数计算记录的散列地址，按此散列地址访问该记录

散列技术既是一种存储方法，也是一种查找方法

散列技术的记录之间不存在什么逻辑关系，它只与关键字有关，因此散列主要是面向查找的存储结构

散列技术最适合的求解问题是查找与给定值相等的记录

散列函数的构造方法：

直接定址法：取关键字的某个线性函数值为散列地址 f(k)=ak+b (a、b为常数)，适合查找表较小且连续的情况

数字分析法：适合处理关键字位数比较大的情况，如果事先知道关键字的分布且关键字的若干位分布较均匀

平方取中法：适合不知道关键字的分布，而位数又不是很大的情况

折叠法：适合不知道关键字的分布，而位数较多的情况

除留余数法：f(k)=k mod p(p<=m) m表长

随机数法 f(k)=random(k) 当关键字的长度不等时

解决散列冲突的方法：开放定址法的线性探索

散列表查找性能：理想O[1].散列函数的好坏，处理冲突的方法，散列表的装填因子（填入散列表的记录个数）