查找算法总结

顺序查找初始版：

#include <iostream>
using namespace std;
int Sequential_Search(int* array, int n, int key)
{
    int i;
    for(i = 0; i < n; i++)
    {
        if(array[i] == key)
        {
            return i;
        }
    }
    return -1;
}

int main()
{
    int array[] = {9, 3, 7, 2, 6};
    if(Sequential_Search(array, 5, 6) >= 0)
    {
        cout << "找到了" << endl;
    }
    else
    {
        cout << "未找到" << endl;
    }
}

优化版：

#include <iostream>
using namespace std;
int Sequential_Search(int* array, int n, int key)
{
    int i = n;
    array[0] = key;
    while (array[i] != key)
    {
        i--;
    }
    return i;
}

int main()
{
    int array[] = {-1, 9, 3, 7, 2, 6};
    if(Sequential_Search(array, 5, 9) > 0)
    {
        cout << "找到了" << endl;
    }
    else
    {
        cout << "未找到" << endl;
    }
}

参考资料：大话数据结构：297

折半查找：

#include <iostream>
using namespace std;
int Binary_Search(int* array, int n, int key)
{
    int low, high, mid;
    low = 0;
    high = n - 1;
    while(low <= high)
    {
        mid = (low + high) / 2;
        if(key < array[mid])
        {
            high = mid - 1;
        }
        else if(key > array[mid])
        {
            low = mid + 1;
        }
        else
        {
            return mid;
        }
    }
    return -1;
}

int main()
{
    int array[] = {2, 7, 9, 11, 18, 32, 97, 101};
    if(Binary_Search(array, 8, 16) >= 0)
    {
        cout << "找到了" << endl;
    }
    else
    {
        cout << "未找到" << endl;
    }
}

折半查找需要一个有序的序列所以，直接给了一个有序的数组

插值查找：

#include <iostream>
using namespace std;
int Binary_Search(int* array, int n, int key)
{
    int low, high, mid;
    low = 0;
    high = n - 1;
    while(low <= high)
    {
        mid = low + (high - low) * (key -array[low]) / (array[high] - array[low]);
        if(key < array[mid])
        {
            high = mid - 1;
        }
        else if(key > array[mid])
        {
            low = mid + 1;
        }
        else
        {
            return mid;
        }
    }
    return -1;
}

int main()
{
    int array[] = {2, 7, 9, 11, 18, 32, 97, 101};
    if(Binary_Search(array, 8, 9) >= 0)
    {
        cout << "找到了" << endl;
    }
    else
    {
        cout << "未找到" << endl;
    }
}

参考资料：大话数据结构：302

斐波那契查找：

#include <iostream>
using namespace std;
const int MAXSIZE = 20;

void Fibonacci(int* F)
{
    F[0] = 0;
    F[1] = 1;
    for(int i = 2; i < MAXSIZE; ++i)
    {
        F[i] = F[i - 1] + F[i - 2];
    }
}

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

int main()
{
    int array[20] = {2, 7, 9, 11, 18, 32, 97, 101};
    if(Fibonacci_Search(array, 8, 9) >= 0)
    {
        cout << "找到了" << endl;
    }
    else
    {
        cout << "未找到" << endl;
    }
}

由于算法当找出数组长度在斐波那契数列中的位置时，会再向数组中写东西，所以讲数组的容量设的比较大。

#include <iostream>
using namespace std;

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

bool 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);
    }
}

bool InsertBST(BiTree* T, int key)
{
    BiTree p = nullptr, s = nullptr;
    if(!SearchBST(*T, key, nullptr, &p))
    {
        s = (BiTree)malloc(sizeof(BiTNode));
        s->data = key;
        s->lchild = s->rchild = nullptr;
        if(!p)
        {
            *T = s;
        }
        else if(key < p->data)
        {
            p->lchild = s;
        }
        else
        {
            p->rchild = s;
        }
        return true;
    }
    return false;
}

bool Delete(BiTree *p)
{
    BiTree q, s;
    if((*p)->rchild == nullptr)
    {
        q = *p;
        *p = (*p)->lchild;
        free(q);
    }
    else if((*p)->lchild == nullptr)
    {
        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;
        if(q != *p)
        {
            q->rchild = s->lchild;
        }
        else
        {
            q->lchild = s->lchild;
        }
        free(s);
    }
    return true;
}

bool 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);
        }
    }
}

void PrintTree(BiTree tree)
{
    if(tree != nullptr)
    {
        cout << tree->data << endl;
        PrintTree(tree->lchild);
        PrintTree(tree->rchild);
    }
    
}

int main()
{
    int a[10] = {62, 88, 58, 47, 35, 73, 51, 99, 37, 93};
    BiTree T = nullptr;
    for(int i = 0; i < 10; i++)
    {
        InsertBST(&T, a[i]);
    }
    PrintTree(T);
    DeleteBST(&T, 99);
    PrintTree(T);
}

这里要注意一个细节：Delete函数中的参数p实际上是要删除元素的父元素的lchild或者rchild。

参考资料：大话数据结构327

AVL树：

#include <iostream>
using namespace std;

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;
}

#define LH +1
#define EH 0
#define RH -1
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);
    }   
}

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

bool InsertAVL(BiTree* T, int e, bool* taller)
{
    if(!*T)
    {
        *T = (BiTree)malloc(sizeof(BiTNode));
        (*T)->data = e;
        (*T)->lchild = (*T)->rchild = nullptr;
        (*T)->bf = EH;
        *taller = true;
    }
    else
    {
        if(e == (*T)->data)
        {
            *taller = false;
            return false;
        }
        if(e < (*T)->data)
        {
            if(!InsertAVL(&(*T)->lchild, e, taller))
            {
                return false;
            }
            if(taller)
            {
                switch ((*T)->bf)
                {
                case LH:
                    LeftBalance(T);
                    *taller = false;
                    break;
                case EH:
                    (*T)->bf = LH;
                    *taller = true;
                    break;
                case RH:
                    (*T)->bf = EH;
                    *taller = false;
                    break;
                default:
                    break;
                }
            }
        }
        else
        {
            if(!InsertAVL(&(*T)->rchild, e, taller))
            {
                return false;
            }
            if(*taller)
            {
                switch((*T)->bf)
                {
                    case LH:
                        (*T)->bf = EH;
                        *taller = false;
                        break;
                    case EH:
                        (*T)->bf = RH;
                        *taller = true;
                        break;
                    case RH:
                        RightBalance(T);
                        *taller = false;
                        break;
                }
            }
        }
    }
    return true;
}

void PrintTree(BiTree tree)
{
    if(tree != nullptr)
    {
        cout << tree->data << endl;
        PrintTree(tree->lchild);
        PrintTree(tree->rchild);
    }
    
}

int main()
{
    int i;
    int a[10] = {3, 2, 1, 4, 5, 6, 7, 10, 9, 8};
    BiTree T = nullptr;
    bool taller;
    for(i = 0; i < 10; i++)
    {
        InsertAVL(&T, a[i], &taller);
    }
    PrintTree(T);
}

散列查找：

#include <iostream>
using namespace std;
#define SUCCESS 1
#define UNSUCCESS 0
#define HASHSIZE 12
#define NULLIKEY -32768
typedef struct
{
    int* elem;
    int count;
}HashTable;

int m = 0;

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

int Hash(int key)
{
    return key % m;
}

void InsertHash(HashTable* H, int key)
{
    int addr = Hash(key);
    while(H->elem[addr] != NULLIKEY)
    {
        addr = (addr + 1) % m;
    }
    H->elem[addr] = key;
}

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

int main()
{
    HashTable* table = new HashTable();
    int addr;
    InitHashTable(table);
    InsertHash(table, 2198);
    InsertHash(table, 7278);
    if(SearchHash(*table, 2198, &addr))
    {
        cout << "找到了" << endl; 
    }
    if(!SearchHash(*table, 5, &addr))
    {
        cout << "没有找到" << endl;
    }
    delete table->elem;
    delete table;
}