国产又爽又长又黄视频,一区二区三区水蜜桃

大師兄的數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)筆記(十三）: KD樹
 大師兄的數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)筆記(十五）: 串

一、關(guān)于符號表

符號表(symbol table)包括詞典(dictionary)結(jié)構(gòu)和映射(map),籠統(tǒng)的稱作詞典。
詞典結(jié)構(gòu)和映射，邏輯上都是由一組數(shù)據(jù)構(gòu)成的集合，其中各元素都是由關(guān)鍵碼(key)和數(shù)據(jù)項(value)合成的詞條(entry)。
詞典結(jié)構(gòu)和映射都支持靜態(tài)查找和動態(tài)更新。
區(qū)別在于，詞典允許多個詞條擁有相同的關(guān)鍵碼，而映射要求關(guān)鍵碼互異。
符號表不要求詞條之間根據(jù)關(guān)鍵碼比大小，在詞條內(nèi)部，也不需要按照大小次序來組織數(shù)據(jù)項。

二、實現(xiàn)詞典

詞典的主要接口如下：

接口	功能
get(key)	若關(guān)鍵碼key存在，則返回對應(yīng)的數(shù)據(jù)項value；否則返回NULL。
put(key,value)	插入詞條(key,value)。
remove(key)	若關(guān)鍵碼key存在，則刪除對應(yīng)詞條；否則返回NULL。

template <typename K, typename V>
//字典條目
struct Entry {
    K key; V value;
    Entry(K k = K(), V v = V()) :key(k), value(v) {}
    Entry(const Entry<K, V>& e) :key(e.key), value(e.value) {}
    bool operator<(const Entry<K, V>& e) { return key < e.key; }
    bool operator>(const Entry<K, V>& e) { return key > e.key; }
    bool operator==(const Entry<K, V>& e) { return key == e.key; }
    bool operator!=(const Entry<K, V>& e) { return key != e.key; }
};

template<typename K, typename V>
//字典結(jié)構(gòu)
struct Dictionary
{
    virtual int size() const = 0;
    virtual bool put(K, V) = 0;
    virtual V* get(K k) = 0;
    virtual bool remove(K k) = 0;
};

詞典可以用任何一種平衡二叉搜索樹實現(xiàn)，但由于這類實現(xiàn)方法都假設(shè)“關(guān)鍵碼可以比大小”，所以實現(xiàn)的并非嚴(yán)格意義上的字典結(jié)構(gòu)。
通常使用跳轉(zhuǎn)表和散列表實現(xiàn)。

三、跳轉(zhuǎn)表

1. 從單鏈表到跳轉(zhuǎn)表

在單鏈表中，查詢某個數(shù)據(jù)需要通過遍歷，時間復(fù)雜度為 $O (n)$ 。
如果每格n個元素增加一級索引，則可以通過索引跳轉(zhuǎn)到鏈表的某一段，用更少的步數(shù)查詢數(shù)據(jù)。
以此類推，可以通過不斷地增加索引，提升查詢效率。
以上方法其實是通過單鏈表實現(xiàn)了二分查找。
這種鏈表加多級索引的結(jié)構(gòu)，就是跳轉(zhuǎn)表(Skiplist)。

2. 關(guān)于跳轉(zhuǎn)表

跳轉(zhuǎn)表基于鏈表的結(jié)構(gòu)，但為了增加索引，節(jié)點需要包含上下左右四個方向的指針，即四聯(lián)表(quadlist)。
需要用兩個鏈表來構(gòu)成跳轉(zhuǎn)表結(jié)構(gòu)，其中，每一個水平鏈表稱為一層(level)，縱向鏈表的規(guī)模稱為層高，從S0-Sh，元素的數(shù)量遞減，最底層的S0包含有表中所有的數(shù)據(jù)項；同時，同一個數(shù)據(jù)項可能在幾層都出現(xiàn)，沿縱向組成塔(tower)，從而也需要給每一個節(jié)點定義上下兩個指針。

template<class T>
// 四聯(lián)表節(jié)點
struct QualdListNode
{
    T entry; //詞條
    QualdListNode<T>* pred; //前驅(qū)
    QualdListNode<T>* succ; //后繼
    QualdListNode<T>* above; //上鄰
    QualdListNode<T>* below; //下鄰

    QualdListNode(
        T e = T(), QualdListNode<T>* p = nullptr,
        QualdListNode<T>* s = nullptr,
        QualdListNode<T>* a = nullptr,
        QualdListNode<T>* b = nullptr) :
        entry(e), pred(p), succ(s), above(a), below(b) {};

    QualdListNode<T>* insertAsSuccAbove(T const& e, QualdListNode<T>* b = nullptr); // 插入新結(jié)點，以當(dāng)前節(jié)點為前驅(qū)，以節(jié)點b為下鄰
};

template<class T>
// 插入新結(jié)點，以當(dāng)前節(jié)點為前驅(qū)，以節(jié)點b為下鄰
QualdListNode<T>* QualdListNode<T>::insertAsSuccAbove(T const& e, QualdListNode<T>* b)
{
    QualdListNode<T>* node;
    node->T = e;
    node->below = b;
    node->above = b->above;
    b->above = node;
    return node;
}

template<class T>
//四聯(lián)表
class QuadList
{
public:
    QuadList(); //構(gòu)造函數(shù)
    ~QuadList(); //構(gòu)造函數(shù)
    int size() const; //獲得規(guī)模
    bool is_empty() const; //是否為空
    QualdListNode<T>* first() const; //首節(jié)點
    QualdListNode<T>* last() const; //尾節(jié)點
    T remove(QualdListNode<T>* p); //刪除結(jié)點
    QualdListNode<T>* insertAfterAbove(T const& e, QualdListNode<T>* p, QualdListNode<T>* b = nullptr); //插入結(jié)點
private:
    int _size;
    bool empty();
    QualdListNode<T>* header;
    QualdListNode<T>* trailer;
    bool valid(QualdListNode<T>* p); //判斷是否合法
protected:
    void init(); // 創(chuàng)建時初始化
    int clear(); // 清除所有節(jié)點
};

template<class T>
//構(gòu)造函數(shù)
QuadList<T>::QuadList()
{
    init();
}

template<class T>
//析構(gòu)函數(shù)
QuadList<T>::~QuadList()
{
    clear();
    delete header;
    delete trailer;
}

template<class T>
//獲得規(guī)模
int QuadList<T>::size() const
{
    return _size;
}

template<class T>
//是否為空
bool QuadList<T>::is_empty() const
{
    return _size == 0;
}

template<class T>
//首節(jié)點
QualdListNode<T>* QuadList<T>::first()const
{
    return header;
}

template<class T>
//尾節(jié)點
QualdListNode<T>* QuadList<T>::last() const
{
    return trailer;
}

template<class T>
//判斷是否合法
bool QuadList<T>::valid(QualdListNode<T>* p)
{
    return p && (p != header) && (p != trailer);
}

template<class T>
//判斷是否為空
bool QuadList<T>::empty()
{
    return _size == 0;
}

template<class T>
//初始化表
void QuadList<T>::init()
{
    header = new QualdListNode<T>; //頭哨兵節(jié)點
    trailer = new QualdListNode<T>; //尾哨兵節(jié)點
    header->succ = trailer; //橫向哨兵
    header->pred = nullptr;
    trailer->pred = header;
    trailer->succ = nullptr;
    header->above = nullptr;
    header->below = nullptr;
    trailer->above = nullptr;
    trailer->below = nullptr;
    _size = 0;
}

template<class T>
//刪除所有節(jié)點
int QuadList<T>::clear()
{
    int oldsize = _size;
    while (_size > 0)
    {
        remove(header->succ);
        return oldsize;
    }
}

template<class T>
//刪除節(jié)點
T QuadList<T>::remove(QualdListNode<T>* p)
{
    p->pred->succ = p->succ;
    p->succ->pred = p->pred;
    T e = p->entry;
    delete p;
    return e;
}

template<class T>
//插入結(jié)點
QualdListNode<T>* QuadList<T>::insertAfterAbove(T const& e, QualdListNode<T>* p, QualdListNode<T>* b)
{
    _size++;
    return p->insertAsSuccAbove(e, b);
}

盡管不必要的重復(fù)詞條會浪費(fèi)一定的空間，但是通過空間換時間提高了跳轉(zhuǎn)表的結(jié)構(gòu)效率,跳轉(zhuǎn)表的查詢和動態(tài)操作僅需要O(logn)的時間。。
如果每個詞條都有很多重復(fù)，不僅接近于鏈表O(n)的效率，更是沒有必要的浪費(fèi)。因此約定，在Sk中出現(xiàn)的節(jié)點，也出現(xiàn)在Sk+1中的概率為1/2，也就是說，總體上，每一層節(jié)點只有它下一層節(jié)點數(shù)量的的一半。

template<typename K, typename V>
//跳轉(zhuǎn)表
class Skiplist :public Dictionary<K, V>, public List<QuadList<Entry<K, V>>* >
{
protected:
    bool skipSearch(ListNode<QuadList<Entry<K, V>>*>*& qlist, QualdListNode<Entry<K, V>>*& p, K& k); //內(nèi)部查找算法
public:
        int size() const { return empty() ? 0 : last()->data->size(); };
        int level() { return List:: size(); };
        bool put(K k, V v); //插入詞條
        V* get(K k);
        bool remove(K k);
};

template<typename K, typename V>
//內(nèi)部查找算法
bool Skiplist<K,V>::skipSearch(ListNode<QuadList<Entry<K, V>>*>*& qlist, QualdListNode<Entry<K, V>>*& p, K& k)
{
    while (true) //遍歷每一層
    {
        while (p->succ && (p->entry.key <= k)) //從前到后找更大的key
        {
            p = p->succ;
        }
        p = p->pred; //往回走一個結(jié)點
        if (p->pred && (k == p->entry.key))
        {
            return true;
        }
        qlist = qlist->succ; //轉(zhuǎn)入后一層
        if (!qlist->succ) //查詢失敗
        {
            return false;
        }
        p = (p->pred) ? p->below : qlist->data->first(); // 轉(zhuǎn)至當(dāng)前塔的下一個結(jié)點
    }
}

template<typename K, typename V>
//插入詞條
bool Skiplist<K,V>::put(K k, V v)
{
    Entry<K, V> e = Entry<K, V>(k, v); //待插入詞條
    if (empty())
    {
        insertAsFirst(new QuadList<Entry<K, V>>); //插入首個Entry
    }
    ListNode<QuadList<Entry<K, V>>*>* qlist = first(); //四聯(lián)表頂層
    QualdListNode<Entry<K, V>>* p = qlist->data->first(); //首節(jié)點
    if (skipSearch(qlist, p, k)) //如果找到結(jié)點
    {
        while (p->below)
        {
            p = p->below; //轉(zhuǎn)到塔底
        }
    }
    qlist = last();
    QualdListNode<Entry<K, V>>* b = qlist->data->insertAfterAbove(e, p);
    while (rand() & 1)
    {
        while (qlist->data->valid(p) && !p->above)
        {
            p = p->pred;
        }
        if (!qlist->data->valid(p))
        {
            if (qlist == first())
            {
                insertAsFirst(new QuadList<Entry<K, V>>);
            }
            p = qlist->pred->data->first()->pred;
        }
        else
        {
            p = p->above;
        }
        qlist = qlist->pred;
        b = qlist->data->insertAfterAbove(e, p, b);
    }
    return true;
}

template<typename K, typename V>
V* Skiplist<K, V>::get(K k)
{
    if (empty())
    {
        return nullptr;
    }
    ListNode<QuadList<Entry<K, V>>*>* qlist = first(); //從頂層獲得quadlist
    QualdListNode<Entry<K, V>>* p = qlist->data->first(); //首節(jié)點開始
    return skipSearch(qlist, p, k) ? &(p->entry.value) : nullptr; //返回值
}

template<typename K, typename V>
bool Skiplist<K, V>::remove(K k)
{
    if (empty()) //空表
    {
        return false;
    }
    ListNode<QuadList<Entry<K, V>>*>* qlist = first();
    QualdListNode<Entry<K, V>>* p = qlist->data->first();
    if (!skipSearch(qlist, p, k)) //如果搜索不到詞條
    {
        return false;
    }
    do {
        QuadListNode<Entry<K, V>>* lower = p->below; //記住下一層結(jié)點
        qlist->data->remove(p); //刪除當(dāng)前層結(jié)點
        p = lower;
        qlist = qlist->succ;
    } while (qlist->succ);
    
    while (!empty() && first()->data->empty())
    {
        List::remove(first());
    }
    return true;
}

四、散列表

1. 數(shù)組、鏈表和散列表

數(shù)組的特點是尋址容易，但是插入和刪除困難。
鏈表的特點是尋址困難，插入和刪除容易。
散列表結(jié)合了數(shù)組和鏈表的特性，尋址容易，插入和刪除也容易。
以上圖為例，左邊的 $keys$ 很明顯是個數(shù)組，數(shù)組的每個成員包括一個指針，指向一個鏈表 $bucket$ 的頭。
根據(jù)元素的一些特征(hash function)把元素分配到不同的鏈表中去。
也是根據(jù)這些特征，找到正確的鏈表，再從鏈表中找出這個元素。

2. 關(guān)于散列表

散列表(Hash table,也叫哈希表），是根據(jù)關(guān)鍵碼值(Key value)而直接進(jìn)行訪問的數(shù)據(jù)結(jié)構(gòu)，不用像數(shù)組或鏈表一樣需要遍歷。
邏輯上由一系列可存放詞條的單元組成，這些單元也稱作桶(bucket)。
桶按照邏輯次序在物理上連續(xù)排列，通常使用數(shù)組保存，稱作桶數(shù)組(bucket array)。
若桶數(shù)組的容量為 $R$ ,則其合法秩的區(qū)間 $[0,R)$ 也稱作地址空間(address space)。
散列表的查詢速度非常快，幾乎是O(1)的時間復(fù)雜度。

3.關(guān)于完美散列

如果每個桶恰好放進(jìn)一個詞條，即無空余又無重復(fù)，這種散列稱為完美散列(perfect hashing)。
完美散列在時間和空間性能均達(dá)到最優(yōu)。
完美散列在十分特定的條件下才成立，實際上并不常見。

4. 關(guān)于散列函數(shù)

散列函數(shù)(hash function)主要用于信息安全領(lǐng)域中加密算法，它把一些不同長度的信息轉(zhuǎn)化成雜亂的128位的編碼,這些編碼值叫做Hash值。
也可以說，散列函數(shù)就是到一種數(shù)據(jù)內(nèi)容和數(shù)據(jù)存放地址之間的映射關(guān)系： $hash() : key -> hash(key)$ 。
散列函數(shù)的種類有很多，包括：

方法	簡介
直接定址法	即 f(key) = a*key + b，f表示散列函數(shù)，a、b是常量，key是鍵值。
數(shù)字分析法	即對數(shù)字做左移、右移、反轉(zhuǎn)等操作獲取散列值。
除數(shù)留余法	即 f(key) = key % p，p 表示容器數(shù)量，這種方式通常用在將數(shù)據(jù)存放到指定容器中，如何決定哪個數(shù)據(jù)放到哪個容器，比如分表后插入數(shù)據(jù)如何處理（此時p表示拆分后數(shù)據(jù)表的數(shù)量），分布式Redis如何存放數(shù)據(jù)（此時p表示幾臺Redis服務(wù)器）。
隨機(jī)數(shù)法	即 f(key) = random(key)，比如負(fù)載均衡的random機(jī)制。

5. 關(guān)于散列沖突

散列沖突指的是 key1 != key2 的情況下，通過散列函數(shù)處理，hash(key1) == hash(key2)，即不同的key獲得了相同的哈希值。
由于散列值是非負(fù)整數(shù)，總量是有限的，但是現(xiàn)實世界中要處理的鍵值是無限的，將無限的數(shù)據(jù)映射到有限的集合，肯定避免不了沖突。
裝載因子 = 元素個數(shù)/散列表長度，裝載因子越大，說明空閑位置越少，沖突越多，散列表的性能越低。
對于散列沖突，可以通過以下方法來解決：

5.1 開放尋址法

開放尋址法的核心思想是: 如果出現(xiàn)了散列沖突，就重新探測一個空閑位置。

1) 線性探測法(Linear Probing)

插入數(shù)據(jù)：當(dāng)往散列表中插入數(shù)據(jù)時，如果某個數(shù)據(jù)經(jīng)過散列函數(shù)之后，存儲的位置已經(jīng)被占用了，就從當(dāng)前位置開始，依次往后查找（到底后從頭開始），看是否有空閑位置，直到找到為止。

查找數(shù)據(jù)：通過散列函數(shù)求出要查找元素的鍵值對應(yīng)的散列值，然后比較數(shù)組中下標(biāo)為散列值的元素和要查找的元素是否相等，若相等，則說明就是我們要查找的元素；否則，就順序往后依次查找。如果遍歷到數(shù)組的空閑位置還未找到，就說明要查找的元素并沒有在散列表中。

刪除數(shù)據(jù)：為了不讓查找算法失效，可以將刪除的元素特殊標(biāo)記為deleted，當(dāng)線性探測查找的時候，遇到標(biāo)記為deleted的空間，并不是停下來，而是繼續(xù)往下探測。

2) 二次探測(Quadratic probing)

線性探測每次探測的步長為1，即在數(shù)組中一個一個探測，而二次探測的步長變?yōu)樵瓉淼钠椒健?/li>

3) 雙重散列(Double hashing)

使用一組散列函數(shù)，直到找到空閑位置為止。

5.2 鏈表法

把一個文件的記錄分為若干存儲桶，每個存儲桶包含一個或多個頁塊，一個存儲桶內(nèi)的各頁塊用指針連接起來，每個頁塊包含若干記錄。散列函數(shù)h把關(guān)鍵碼值K轉(zhuǎn)換為存儲桶號，即h(K)表示具有關(guān)鍵碼值K的記錄所在的存儲桶號。
插入數(shù)據(jù)：當(dāng)插入的時候，我們需要通過散列函數(shù)計算出對應(yīng)的散列槽位，將其插入到對應(yīng)的鏈表中即可，所以插入的時間復(fù)雜度為O(1)。
查找或刪除數(shù)據(jù)：當(dāng)查找、刪除一個元素時，通過散列函數(shù)計算對應(yīng)的槽，然后遍歷鏈表查找或刪除。對于散列比較均勻的散列函數(shù)，鏈表的節(jié)點個數(shù)k=n/m，其中n表示散列表中數(shù)據(jù)的個數(shù)，m表示散列表中槽的個數(shù)，所以是時間復(fù)雜度為O(k)。
兩種方法對比：

方法	優(yōu)點	缺點	適用場景
開放尋址法	1、數(shù)據(jù)存儲在數(shù)組，可以有效利用CPU緩存加速查詢速度 2、序列化簡單	1、刪除需要特殊標(biāo)記已刪除數(shù)據(jù) 2、所有數(shù)據(jù)存儲在一個數(shù)組，發(fā)生沖突時，解決的代價更高，造成裝載因子不能太大，使得更加浪費(fèi)內(nèi)存空間	1、數(shù)據(jù)量小 2、裝載因子小
鏈表法	1、內(nèi)存利用率高，需要時再申請 2、對大裝載因子容忍度高，可大于1	1、因為鏈表需要存儲指針，存儲指針需要消耗內(nèi)存，不適合小對象存儲 2、鏈表節(jié)點不是連續(xù)空間，因此CPU緩存不友好	1、存儲大對象、大數(shù)據(jù)量的散列表 2、支持更多優(yōu)化策略，如紅黑樹代替鏈表。

5.3 實現(xiàn)散列表

#pragma once
#include <iostream>
#include <string>
#include <vector>
using namespace std;

template<class T>
//散列表節(jié)點
struct Node
{
    T key;
    string name;
    Node<T>* next;
};

template<class T>
//散列表
class hashTable
{
public:
    hashTable(); //構(gòu)造函數(shù)
    void insert(T key, string name); //插入
    void del(T key);
    void del(T key,string name); //刪除
    Node<T>* search(T key);
    Node<T>* search(T key,string name);
private:
    void insert(Node<T>* node);
    void del(Node<T>* node); 
private:
    vector<Node<T>*> _map;
    int _hash(T key);  //哈希函數(shù)
};

template<class T>
int hashTable<T>::_hash(T key)
{
    return (key * 50) % 41; //hashfunciton算法
}

template<class T>
hashTable<T>::hashTable()
{
    _map.resize(100);
    for (int i = 0; i <= 50; i++)
    {
        _map[i] = nullptr;
    }
}

template<class T>
//插入
void hashTable<T>::insert(Node<T>* node)
{
    node->next = _map[_hash(node->key)];
    _map[_hash(node->key)] = node;
}

template<class T>
void hashTable<T>::insert(T key, string name)
{
    Node<T>* node = new Node<T>;
    node->key = key;
    node->name = name;
    insert(node);
}

template<class T>
//刪除
void hashTable<T>::del(Node<T>* node)
{
    del(node->key, node->name);
}

template<class T>
void hashTable<T>::del(T key)
{
    if (_map[_hash(key)] == nullptr)return; //如果沒有對應(yīng)key
    int num = _hash(key);
    Node<T>* node = _map[num];
    while (_map[num])
    {
        node = _map[num];
        _map[num] = node->next;
        delete node;
    }
}

template<class T>
void hashTable<T>::del(T key, string name)
{
    if (_map[_hash(key)] == nullptr)return;
    int num = _hash(key);
    Node<T>* p = _map[num];
    Node<T>* q = _map[num];
    while (p)
    {
        if (p->name == name)break;
        q = p;
        p = p->next;
    }
    if (q == _map[num] && p == q)
    {
        _map[num] = p->next;
    }
    else
    {
        q->next = p->next;
    }
}

template<class T>
//查找
Node<T>* hashTable<T>::search(T key)
{
    return _map[_hash(key)];

}

template<class T>
//查找
Node<T>* hashTable<T>::search(T key,string name)
{
    if (!_map(_hash(key)))return nullptr;
    Node<T>* node = _map[_hash(key)];
    while (node)
    {
        if (node->name == name)
        {
            return node;
        }
        node = node->next;
    }
    return nullptr;
}

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

大師兄的數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)筆記(十四）: 詞典

大師兄的數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)筆記(十四）: 詞典

一、關(guān)于符號表

二、實現(xiàn)詞典

三、跳轉(zhuǎn)表

1. 從單鏈表到跳轉(zhuǎn)表

2. 關(guān)于跳轉(zhuǎn)表

四、散列表

1. 數(shù)組、鏈表和散列表

2. 關(guān)于散列表

3.關(guān)于完美散列

4. 關(guān)于散列函數(shù)

5. 關(guān)于散列沖突

5.1 開放尋址法

5.2 鏈表法

5.3 實現(xiàn)散列表

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

大師兄的數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)筆記(十四）: 詞典

一、關(guān)于符號表

二、實現(xiàn)詞典

三、跳轉(zhuǎn)表

1. 從單鏈表到跳轉(zhuǎn)表

2. 關(guān)于跳轉(zhuǎn)表

四、散列表

1. 數(shù)組、鏈表和散列表

2. 關(guān)于散列表

3.關(guān)于完美散列

4. 關(guān)于散列函數(shù)

5. 關(guān)于散列沖突

5.1 開放尋址法

5.2 鏈表法

5.3 實現(xiàn)散列表

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

一、關(guān)于符號表

二、實現(xiàn)詞典

三、跳轉(zhuǎn)表

四、散列表