查找算法

2017-09-25  本文已影响0人  安安zoe

1. 基本概念

查找结构通常有四种操作：查询某个特定元素是否在表中，检索满足条件的某个特定元素的各种属性，在查找表中插入某一数据元素，从查找表中删除某个元素

2. 折半查找（二分查找）

3. 键树

键树称为数字查找树，是度大于等于2的树，树的每个结点包含的是组成关键字的符号，如果关键字是数值，则结点包含一个数位，如果关键字是单词，则结点包含一个字母字符，如下图所示。

键树.png

3.1 双链树（树的孩子-兄弟链来表示键树）

每个Node有三个域：

双链表.png

3.2 字典树

字典树，又叫做Trie树，单词查找树，或者前缀树，是一种用于快速检索的多叉树结构，树的每个结点包含d个指针域，d是关键字符的基，比如英文字母的字典树是26叉树，数字字典树是10叉树。

字典树1.png 字典树2.jpg 
#include<iostream>
#include<cstdlib>
using namespace std;

const int branchNum = 26;
struct Trie_node{
    bool isStr; // 记录此处是否构成一个串
    Trie_node * next[branchNum]; //指向各个子树的指针
    
    // 初始化
    Trie_node() :isStr(false){ memset(next, NULL, sizeof(next)); }
};

class Trie{
private:
    Trie_node *root;
public:
    Trie(){ root = new Trie_node(); }
    void insert(const char * str);
    bool search(char * str);
    void deleteTrie(Trie_node * root);
    Trie_node * getTrie(){ return root; }
};

void Trie::insert(const char * str){
    Trie_node * location = root;
    while (*str){
        // 如果不存在则建立结点
        if (location->next[*str - 'a'] == NULL){
            Trie_node *temp = new Trie_node();
            location->next[*str - 'a'] = temp;
        }
        location = location->next[*str - 'a'];
        // 每插入一步，相当于新串路过，指针移动
        str++;
    }
    location->isStr = true;//标记一个串

    // Trie *temp = (Trie *) malloc(sizeof(Trie));
    // for(int i =0;i<26,i++)
    // temp->next[i] = NULL:
}


bool Trie::search(char * str){
    Trie_node * location = root;
    while (*str && location){  // *str!='\0'
        location = location->next[*str - 'a'];
        str++;
    }
    return (location != NULL && location->isStr);
}

void Trie::deleteTrie(Trie_node *root){
    for (int i = 0; i < branchNum; i++){
        if (root->next[i] != NULL)
            deleteTrie(root->next[i]);
    }
    delete(root);
}

int main(){
    char *str = "abcdefg";
    Trie trie;
    trie.insert(str);
    if (trie.search(str)) cout << "true";
    system("pause");
    return 0;
}

4.后缀树和后缀数组（suffix tree）

5. 哈希表

6. 一致性哈希

7. 海量数据处理

7.1 hash映射-分治处理

对大文件处理时，若文件过大，无法一次性读入内存，将hash映射将文件元素映射到不同小文件中，在依次处理各个小文件，最后合并处理结果。
例子：a、b文件，各存放50亿个url，请找出a、b共同的URL？
答：遍历a，hash（url）%1024，将a分别存放在1024个文件中，对b进行同样操作，处理后，**所有可能相同的url都在对应的小文件中，如a0对应b0，然后分别对小文件进行遍历搜索处理等即可

7.2 Top K问题

【编程之美】读书笔记：寻找最大的K个数
《编程之美》——寻找最大的K个数

// 快排 我们基于数组的第K个数字来调整时，最小的k个数
void getleastNumber(int *input, int n, int *output, int k){
    if (input == NULL || output == NULL || k>n || n <= 0 || k <= 0)
        return;

    int start = 0;
    int end = n - 1;
    int index = Partition(input,  start, end);
    while (index != k - 1){
        if (index > k - 1){
            end = index - 1;
            // 一趟快排
            index = Partition(input, start, end);
        }
        else{
            start = index + 1;
            index = Partition(input,  start, end);
        }
    }

    for (int i = 0; i < k; ++i)
        output[i] = input[i];
}

int Partition(int *a, int low, int high){
    int pivot = a[low];
    while (low < high){
        while (low < high && a[high] >= pivot) --high;
        a[low] = a[high];
        while (low < high && a[low] <= pivot) ++low;
        a[high] = a[low];
    }
    a[low] = pivot;
    return low;
}

// 基于multiset的实现
void getLeastNumbers(const vector<int> &data, multiset<int, int> & leastNumbers, int k){
    leastNumbers.clear();

    if (k < 1 || data.size() < k)
        return;

    vector<int>::const iterator = data.begin();
    for (; iter != data.end(); ++iter){
        if (leastNumbers.size() < k)
            leastNumbers.insert(*iter);
        else{
            mutiset<int, int>::iterator setiter = leastNumbers.begin();
            if (*iter < *(leastNumbers.begin())){
                leastNumbers.erase(setiter);
                leastNumbers.insert(iter);
            }
        }
    }
}

7.3 Bit-map

上一篇 下一篇

猜你喜欢

热点阅读