第八章 查找

查找表是由同一类型的数据元素(或记录)构成的集合.
查找表常用的操作有下面四个:

  1. 查询某个“特定的”数据元素是否在查找表中;
  2. 检索某个“特定的”数据元素的各种属性;
  3. 在查找表中插入一个数据元素;
  4. 从查找表中删去某个数据元素。

顺序查找

  • 所谓顺序查找，又称线性查找，主要用于在线性结构中进行查找。
1
2
3
4
5
6
7
8
typedef struct {
    KeyType key;
}ElemType;

typedef struct {
    ElemType *elem;
    int length;
}SSTable;

顺序查找算法的实现

1
2
3
4
5
6
Status Search_Seq(SSTable ST, KeyType key){
    ST.elem[0].key = key;
    for(int i = ST.length; ST.elem[i].key != key; i--){
        return i;
    }
}

折半查找

  • 所谓折半查找，是指先确定待查找记录所在范围，然后逐步缩小，范围直到找到或找不到该记录为止。

折半查找算法的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Status Search_Bin(SSTable ST, KeyType key){
    int L = 1, H = ST.length;
    int M;
    while(L <= H){
        M = (L + H) / 2;
        if(ST.elem[M].key == key){
            return i;
        }else if(ST.elem[M] > key){
            H = M - 1;
        }else{
            L = M + 1;
        }
    }
    return 0;
}

二叉排序树

二叉排序数的定义

  • 二叉排序树是一种动态树表。其特点是，树的结构通常不是一次生成的，而是在查找过程中，当树中不存在关键字等于给定值的结点的时候再迚行插入。新插入结点一定是一个新添加的叶子结点，并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子结点。

  • 一个无序序列可以通过构造一棵二叉排序树而变成一个有序序列，构造树的过程即为对无序序列迚行排序的过程。
  • 从刚才的插入过程还可以看到，每次插入的新结点都是二叉排序树上新的叶子结点，则在迚行插入操作时候，不必移动其他结点，仅需改动某个结点的指针，由空变为非空即可。这就相当于在一个有序序列上插入一个记录而不需要移动其他记录。
  • 这表明，二叉排序树既拥有类似于折半查找的特性，又采用了链表作为存储结构，因此是动态查找表的一种适宜表示。

二叉排序树或者是一棵空树; 或者是具有如下特性的二叉树:

  1. 若它的左子树丌空，则左子树上所有结点的值均小于根结点的值;
  2. 若它的右子树丌空，则右子树上所有结点的值均大于根结点的值;
  3. 它的左、右子树也都分别是二叉排序树。

二叉平衡树

哈希表

  • 若查找结构中存在关键字和K相等的记录，则必定在f(K)的存储位置上，因此，不需要进行比较便可直接取得所查记录，这里，我们称这个对应关系f为哈希函数，f(K)为哈希地址，按这个思想建立的查找表叫做哈希表。

  • 哈希函数是一个映像，因此哈希函数的设定很灵活幵丌是唯一的，只要使得任何关键字通过哈希函数得到的值都落在表长允许的范围之内即可。
  • 对不同的关键字可能得到同一个地址，比如乊前例子里的beijing和binzhou,也就是关键字key1丌等于关键字key2,但是关键字key1和关键字key2的哈希地址是相同的。这种现象叫做冲突。