八. 查找

顺序表查找

顺序查找又叫线性查找，是最基本的查找技术，它的查找过程: 从表中第一个(或最后一个)记录开始，逐个进行记录的关键字和给定值比较，若某个记录的关键字和给定值相等，则查找成功，找到所查的记录；反之，则查找不成功。

int Sequential_Search(int *a, int n, int key) {
    int i = n;
    a[0] = key;
    while (a[i] != key) {
        i--;
    }
    return i;
}

时间复杂度为O(n)。

有序表查找

折半查找

又称为二分查找。前提是线性表中的记录必须是有序，采用的是顺序存储。若给定值与中间记录的关键字相等，则查找寻找；若小于则在记录的左半边找；若大于则在记录的右半边。不断重复上述操作，直到中数不能再对折。

int Binary_Search(int *a, int n, int key) {
    int low = 1, high = n, mid;
    while (low <= high) {
        mid = (low + high) / 2;
        if (key < a[mid]) {
            high = mid - 1;
        } else if (key > a[mid]) {
            low = mid + 1;
        } else {
            return mid;
        }
    }
    return 0;
}

时间复杂度为O(㏒n)。

斐波那契查找

int F[] = {0, 1, 1, 2, 3, 5, 8, 13, 21, 34};

int Fibonacci_Search(int *a, int n, int key) {
    int low = 1, high = n, mid, k = 0;
    while (n > F[k] - 1) {
        k++;
    }
    for (int i = 0; i < F[k] - 1; i++) {
        a[i] = a[n];
    }
    while (low <= high) {
        mid = low + F[k - 1] - 1;
        if (key < a[mid]) {
            high = mid - 1;
            k--;
        } else if (key > a[mid]) {
            low = mid + 1;
            k = k - 2;
        } else {
            if (mid <= n) {
                return mid;
            } else {
                return n;
            }
        }
    }
    return 0;
}

二叉排序树

二叉排序树又称为二叉查找树。它或者是一棵空树，或者是具有下列性质的二叉树。

• 若它的左子树不空，则左子树上所有结点的值均小于它的跟结构的值；
• 若它的右子树不空，则右子树上所有结点的值均小于它的跟结构的值；
• 它的左、右子树也分别为二叉排序树。

typedef struct BiTNode {
    int data;
    struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

/**
 递归查找二叉树排序树T中是否存在key

 @param T 二叉树
 @param key 查找key
 @param f 指针f指向T的双亲，其初始值调用值为NULL
 @param p 指向该数据元素结点
 @return TRUE OR FALSE
 */
Status SearchBST(BiTree T, int key, BiTree f, BiTree *p) {
    if (!T) {
        *p = f;
        return FALSE;
    } else if (key == T->data) {
        *p = T;
        return TRUE;
    } else if (key < T->data) {
        return SearchBST(T->lchild, key, T, p);
    } else {
        return SearchBST(T->rchild, key, T, p);
    }
}

二叉排序树插入操作

Status InsertBST(BiTree *T, int key) {
    BiTree p, s;
    if (!SearchBST(*T, key, NULL, &p)) {
        s = (BiTree)malloc(sizeof(BiTNode));
        s->data = key;
        s->lchild = s->rchild = NULL;
        if (!p) {
            *T = s;
        } else if (key < p->data) {
            p->lchild = s;
        } else {
            p->rchild = s;
        }
        return TRUE;
    }
    return FALSE;
}

二叉排序树删除操作

Status Delete(BiTree *p) {
    BiTree q, s;
    if ((*p)->rchild == NULL) {
        q = *p;
        *p = (*p)->lchild;
        free(q);
    } else if ((*p)->lchild == NULL) {
        q = *p;
        *p = (*p)->rchild;
        free(q);
    } else { //左右子树均不空
        q = *p;
        s = (*p) ->lchild;
        while (s->rchild) { //转左，然后向右到尽头(找待删结点的前驱)
            q = s;
            s = s->rchild;
        }
        (*p)->data = s->data; //s指向被删结点的直接前驱
        if (q != *p) { //重新接好后面的子树
            q->rchild = s->lchild;
        } else {
            q->lchild = s->lchild;
        }
        free(s);
    }
    return TRUE;
}

Status DeleteBST(BiTree *T, int key) {
    if (!*T) {
        return FALSE;
    } else { 
        if (key == (*T)->data) {
            return Delete(T);
        } else if (key < (*T)->data) {
            return DeleteBST(&(*T)->lchild, key);
        } else {
            return DeleteBST(&(*T)->rchild, key);
        }
    }
}

平衡二叉树(AVL树)

平衡二叉树是一种二叉排序树，其中每一个节点的左子树和右子树的高度差至多等于1。
将二叉树上结点的左子树深度减去右子树深度的值称为平衡因子BF，那么平衡二叉树上所有结点的平衡因子只可能是-1、0和1。
距离插入结点最近的，且平衡因子的绝对值大于1的结点为根的子树，称为最小不平衡子树。

#define LH +1
#define EH 0
#define RH -1

typedef struct BiTNode {
    int data;
    int bf; //平衡因子
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

void R_Rotate(BiTree *P) {
    BiTree L;
    L = (*P)->lchild;
    (*P)->lchild = L->rchild;
    L->rchild = (*P);
    *P = L;
}

void L_Rotate(BiTree *P) {
    BiTree R;
    R = (*P)->rchild;
    (*P)->rchild = R->lchild;
    R->lchild = (*P);
    *P = R;
}

void LeftBalance(BiTree *T) {
    BiTree L, Lr;
    L = (*T)->lchild;
    switch (L->bf) {
        case LH:
            (*T)->bf = L->bf = EH;
            R_Rotate(T);
            break;
        case RH:
            Lr = L->rchild;
            switch (Lr->bf) {
                case LH:
                    (*T)->bf = RH;
                    L->bf = EH;
                    break;
                case EH:
                    (*T)->bf = L->bf = EH;
                    break;
                case RH:
                    (*T)->bf = EH;
                    L->bf = LH;
                    break;
            }
            Lr->bf = EH;
            L_Rotate(&(*T)->lchild);
            R_Rotate(T);
    }
}

散列表查找概述

散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使得每个关键字key对应一个存储位置f（key）。这种对应关系f称为散列函数，又称为哈希函数。采用散列技术将记录存储在一块连续的存储空间中，这快连续存储空间称为散列表或哈希表。

散列表查找实现

#define SUCCESS 1
#define UNSUCCESS 0
#define HASHSIZE 12
#define NULLKEY -32768
typedef int Status;
typedef struct {
    int *elem; //数据元素存储基址，动态分配数组
    int count;
}HashTable;

int m = 0; //散列表表长

Status InitHashTable(HashTable *H) {
    m = HASHSIZE;
    H->count = m;
    H->elem = (int *)malloc(sizeof(int));
    for (int i = 0; i < m; i++) {
        H->elem[i] = NULLKEY;
    }
    return TRUE;
}

//散列函数
int Hash(int key) {
    return key % m; //除留余数法
}

void InsertHash(HashTable *H, int key) {
    int addr = Hash(key); //求散列地址
    while (H->elem[addr] != NULLKEY) { //如果不为空，则冲突
        addr = (addr + 1) % m; //开放定址法的线性探测
    }
    H->elem[addr] = key; //直到有空位后插入关键字
}

Status SearchHash(HashTable H, int key, int *addr) {
    *addr = Hash(key);
    while (H.elem[*addr] != key) {
        *addr = (*addr + 1) % m;
        if (H.elem[*addr] == NULLKEY || *addr == Hash(key)) {
            return UNSUCCESS;
        }
    }
    return SUCCESS;
}