查找算法

查找

1-线性表查找算法

	顺序查找	二分查找	分块查找
ASL	最大	最小	中间
适用数据结构	顺序表和链表	顺序表	顺序表和链表

顺序查找表的定义

#define MAXSIZE 100
typedef int KeyType;
typedef int InfoType;

//数据元素类型定义
struct ElemType {
    KeyType key; //关键字域
    InfoType otherinfo; //其他域
};
//顺序表结构类型定义，Sequential Search Table
struct SSTable
{
    ElemType *R; //顺序表地址指针
    int length;  //顺序表的长度
};

顺序查找算法

int SqSearch(SSTable &S, const KeyType e)
{
    //第一步：施加哨兵
    S.R[0].key = e;
    //第二步：顺序比较查找
    int i;
    for (i = S.length; S.R[i].key != e; --i)
    {
        ; //空操作
    }
    return i;
    //时间复杂度O(n)、空间复杂度O(1)，ASL=(n+1)/2
}

二分查找算法

int Search_bin(SSTable &S, const KeyType e)
{
    int low = 1, high = S.length;
    while (low <= high)
    {
        int mid = (low + high) / 2;
        if (e == S.R[mid].key) //e的值就等于中间位置的值
            return mid;
        if (e < S.R[mid].key) //e的值位于小半部分
            high = mid - 1;
        if (e > S.R[mid].key) //e的值位于大半部分
            low = mid + 1;
    }
    return -1;
}

二分查找算法递归版

int Search_bin(SSTable &S, const KeyType e, int low, int high)
{
    //递归的终止条件
    if (low > high)
        return -1;
    //递归的变化体
    int mid = (high + low) / 2;
    if (e == S.R[mid].key)
        return mid;
    if (e < S.R[mid].key)
        return Search_bin(S, e, low, mid - 1);
    else
        return Search_bin(S, e, mid + 1, high);
}

---

2-二叉树查找算法

二叉排序树的存储结构

typedef int KeyType;
typedef int InfoType;

typedef struct {
    KeyType key;
    InfoType otherinfo;
}ElemType;

typedef struct BSTNode {
    ElemType data;
    BSTNode* lchilde, * rchild;
}BSTNode, *BSTree;

二叉排序树的递归查找算法

BSTree &SearchBST(BSTree &T, const KeyType &e)
{
    if(!T || T->data.key == e)
        return T;
    else if(e < T->data.key)
        return SearchBST(T->lchild, e);
    else
        return SearchBST(T->rchild, e);
}

二叉排序树的插入

void InsertBSTree(BSTree& T, const ElemType& e)
{
    //D，查找直至某个叶子结点的左子树或右子树为空为止，则插入结点应为该叶子结点的左孩子或右孩子
    if (T == nullptr)
    {
        T = new BSTNode;
        T->data = e;
    }
    //L
    if (e.key < T->data.key)
        InsertBSTree(T->lchild, e);
    //R
    else if (e.key > T->data.key)
        InsertBSTree(T->rchild, e);
    //other，树中已有，不在插入
    if (e.key == T->data.key)
        cerr << "already hava it" << endl;
}

二叉排序树的生成

void CreatBSTree(BSTree &T)
{
    //输入序列（也可以从形参传入）
    cout << "input info about the tree" << endl;
    vector<ElemType> vec;
    ElemType input;
    //先建一个vector容器
    while(cin>>input.key)
    {
        vec.push_back(input);
    }
    //调用插入算法
    for (vector<ElemType>::iterator it = vec.begin(); it != vec.end();++it)
    {
        InsertBSTree(T, *it); //从容器中逐一取出元素，插入到二叉排序树中
    }
}