欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C++前綴樹字典樹的學習與模擬實現(xiàn)代碼示例

 更新時間:2023年07月12日 09:28:30   作者:魏天樂大帥哥  
這篇文章主要介紹了C++前綴樹字典樹的學習與模擬實現(xiàn)代碼示例,Trie又被稱為前綴樹、字典樹,所以當然是一棵樹,上面這棵Trie樹包含的字符串集合是{in,inn,int,tea,ten,to},每個節(jié)點的編號是我們?yōu)榱嗣枋龇奖慵由先サ?需要的朋友可以參考下

前綴樹介紹

在計算機科學中,trie,又稱前綴樹字典樹,是一種有序樹,用于保存關(guān)聯(lián)數(shù)組,其中的鍵通常是字符串。常用與拼寫檢查自動補全等; 是一種查找結(jié)構(gòu)他的存儲邏輯類似于哈希表,但是它相對于哈希表來說,限制更多,通用性較差,但是它的功能更加強大,可定制性也更強。 leetcode指路:實現(xiàn)Trie(前綴樹)

如圖可以查看trie樹的基本結(jié)構(gòu):

在這里插入圖片描述

與二叉查找樹不同,鍵不是直接保存在節(jié)點中,而是由節(jié)點在樹中的位置決定。(這個是前綴樹的精髓,也是難理解的地方,他不用存儲某個節(jié)點的實際字符,他的對應下標映射出了需要存儲的字符!)

一個節(jié)點的所有子孫都有相同的前綴,也就是這個節(jié)點對應的字符串,而根節(jié)點對應空字符串

一般情況下,不是所有的節(jié)點都有對應的值(他們只是前綴),只有葉子節(jié)點和部分內(nèi)部節(jié)點所對應的鍵才有相關(guān)的值。

C++實現(xiàn)

核心思想

單鏈表:通過Node中封裝的Node* next來找下一個連著的節(jié)點;

二叉樹:通過Node中封裝的Node* left 和 Node* right來找左右孩子節(jié)點;

前綴樹?

因為維護了26個可能的Node*節(jié)點,所以跟上面一個道理,只是不能枚舉出來了,用了一個Node*arr[26]來維護,恰巧把這個數(shù)組的下標設(shè)計成了某個字符的種類,就可以達到利用邏輯下標存儲一個實際字符的作用了!

前綴樹插入示意圖

在這里插入圖片描述

上圖中,每經(jīng)過一個節(jié)點,將該節(jié)點的pass值加一,將末尾節(jié)點的end值加一。通過這種操作記錄所有經(jīng)過的數(shù)據(jù)記錄

前綴樹的插入是靈魂所在,搞懂了之后結(jié)構(gòu)就明白了,不管是查找還是刪除無非就是類似對鏈表的相關(guān)操作;

前綴樹的大致框架

假設(shè)只存小寫字符:

#include <iostream>
#include <vector>
#include <string>
using namespace std;
//26 個小寫英文字母
#define NUM 26
class Trie{
private:
    Trie* arr[NUM];//多叉樹(最大26個分支,因為26個小寫字母嘛)
    int end;  //代表word完整單詞的個數(shù),0就是無此單詞,只是一個前綴;insert一個單詞的時候,這個單詞的end首次出現(xiàn)就置為1;之后重復插入就end++;
    int pass; //代表以此前綴為公共前綴的節(jié)點個數(shù),每次insert的時候會調(diào)整;
public:
    Trie() {
        memset(arr,0,sizeof(arr));//每個新節(jié)點的映射數(shù)組內(nèi)容置nullptr
	    end = 0;
        ncount = 0; //初始化時以該映射信息字符為前綴的個數(shù)為1(這個字符本身算的1)
    }
    //插入單詞
    void Insert(string &x)
    {
    }
    //查找 完全匹配字符串x 的數(shù)量
    int Find(string &x)
    {
    }
    //查找 前綴為字符串x 的數(shù)量
    int FindContain(string& x)
    {
    }
    //刪除某個單詞(前綴)
    bool Erase(string &x)
    {
    }
    ~Trie()
    {
        //因為new了26個連續(xù)的tire*空間,不要某個節(jié)點,不要把它對應給下層準備的26個空間也delete掉 防止內(nèi)存泄漏
        for (int i = 0; i < NUMBER; i++)
		{
			if (nexts[i]){
                delete nexts[i];
            }
		}
    }
};
  • 二叉樹,父節(jié)點之下包含兩個節(jié)點,分別為左右子節(jié)點,分別開辟空間,進行數(shù)據(jù)存儲。
  • 前綴樹的結(jié)構(gòu)也是類似的,它的每個節(jié)點包含兩個部分: 值部分和指針部分。
  • 它的存儲方式為:在一棵樹上,從根到子節(jié)點,分別存儲所有目標數(shù)據(jù)的每一個下標位置上的數(shù)據(jù)
  • 值部分主要又包含兩個數(shù)據(jù): 路過該節(jié)點的數(shù)量為pass, 以該節(jié)點為結(jié)尾的數(shù)量為end。
  • 指針部分主要包含它的所有子節(jié)點(比如26個小寫字母),記為arr

下面的實現(xiàn)給出了四個接口:

  • Insert插入字符串,給前綴樹添加一組數(shù)據(jù)

其中Insert方法需要注意插入新單詞的過程中,路徑所有前綴的個數(shù)pass+1

  • Find查找已存入的完整匹配的字符串個數(shù)
  • FindContain 查找已存入的前綴匹配的字符串個數(shù)
  • Erase 從前綴樹中擦除一個完整字符串

Erase方法需要注意的是:

  • 需Find先檢查字符串是否存在;
  • pass == 1 時,代表其下沒有任何可能存在的字符子串,所以直接將這個節(jié)點delete刪除即可;
  • pass不為1且存在這個字符串,我們把end有效字符串個數(shù)-1就行
  • 移除節(jié)點時,需要提前寫好析構(gòu)函數(shù),將其節(jié)點開辟的26個Node*內(nèi)存全部釋放,以免出現(xiàn)內(nèi)存泄漏;

前綴樹插入字符串

另外,下面的功能代碼不過多解釋,代碼注釋自行理解,核心要點就是用數(shù)組下表映射的方式確定前往哪一條鏈表,之后的尋找和插入等操作都有點像鏈表的操作,搞個cur指針向后遍歷等;

//插入單詞
    void Insert(const string &x)
    {
        int size = x.size();
        Node* cur = root;
        cur->pass++;//不管insert啥,我們root空節(jié)點的pass相當于必須+1,最終這個root->pass可以代表一共insert了幾次=-=
        for (int i = 0; i<size; i++) {
            char index = x[i] - 'a';
            //該字符在當前分支下的映射為空,沒有那就new
            if (cur->arr[index] == nullptr) {
                cur->arr[index] = new Node;
            }
            cur->arr[index]->pass++; //不管 cur->arr[index] 是new的還是本來就有,insert要路過他了,他的pass+1,
            cur = cur->arr[index];//同時cur下指過去,進行下一個字符的insert
        }
        cur->end++;//insert最終將完整字符串個數(shù)end+1
    }

前綴樹查找完整的字符串

  //查找 完全匹配字符串 x 的數(shù)量 -->end
    int Find(const string &x)
    {
        int size = x.size();
        Node* cur = root;
        for (int i = 0; i < size; i++) {
            char index = x[i] - 'a';
            //搜索到某個字符斷了,沒有這個完整的字符串x 返回0
            if (cur->arr[index] == nullptr) return 0;
            //沒斷,繼續(xù)向下一個字符搜索;
            cur = cur->arr[index];
        }
        return cur -> end;//返回完整字符串x的有效個數(shù)end
    }

前綴樹查找前綴匹配的字符串

//查找 前綴為字符串 x 的數(shù)量 -->pass
    int FindContain(const string& x)
    {
        //與Find一模一樣的邏輯,只是最后的return 變了,這體現(xiàn)了Node*封裝 int end  和int pass的好處了吧
        int size = x.size();
        Node* cur = root;
        for (int i = 0; i < size; i++) {
            char index = x[i] - 'a';
            if (cur->arr[index] == nullptr) return 0;
            cur = cur->arr[index];
        }
        return cur -> pass;
    }

前綴樹刪除完整字符串

 //刪掉某個完整單詞-以及這個單詞后面可能存在的所有路徑;(end>1 出現(xiàn)了很多次時,只需要end--一下)
    bool Delete(const string &x)
    {
        if (Find(x) == 0) return false;//壓根沒這個單詞,刪除失敗;
        //有這個單詞,我們需要找到他的prev前一個,delete掉他,prev的arr[x]=nullptr!
        Node* cur = root;
        Node* prev = root;
        int size = x.size();
        for (int i = 0; i < size; i++) {
            char index = x[i]-'a';
            //if (cur->arr[index] == nullptr) return false;這句不需要,都過了Find 肯定x每個字符都存在于字典樹中
            cur->pass--;//別忘了路過的路徑都得-1;
            prev = cur;
            cur = cur->arr[index];
        }
        if (cur->end==1) {//代表x所在字符串的個數(shù)只有1,直接遞歸delete刪掉它 和 他后面的子串
            delete cur;//這個delete調(diào)析構(gòu),我們析構(gòu)已經(jīng)寫好了,防止內(nèi)存泄漏;
            prev->arr[x[size - 1]-'a'] = nullptr; // prev的arr[x最后一個字符-'a'] = nullptr!
        }
        else  cur->end--;//end>1 :end--代表這個節(jié)點的有效字符串個數(shù)-1,end==1 end-- == 0,這個節(jié)點的字符有效個數(shù)為0了,但是他因為pass>1,暫時保存 后面的不刪;
        //end>1,那就end有效個數(shù)-1就行了;
        return true;
    }

總結(jié)

  • 這個字典樹的樹結(jié)構(gòu)可以根據(jù)需求來進行多樣式的處理;比如我為了實現(xiàn)設(shè)計的功能,每個節(jié)點都保存了pass和end倆int方便功能記錄和函數(shù)內(nèi)的使用;
  • 字典樹本質(zhì)上是犧牲空間,換查找同前綴的字符串提升時間效率的一種措施,但是我們這種每個節(jié)點都開26個數(shù)組的方式是非常浪費空間的,比如只有一個有效字符下標,其他25個nullptr都浪費了,而且在大量相同的前綴下就是單鏈表,浪費更嚴重。
  • 這時候我們可以把Node*arr[26]數(shù)組換成map<char,Node*>這樣搞(每層某一個char只會出現(xiàn)一次,所以char做key沒問題),需要配對啥就insert給紅黑樹中添加啥,大大節(jié)省空間;

所以說這個樹沒有啥固定玩法,可塑性太強了…這可能也是不刷題的我不常見的愿因?

完整代碼

#include <iostream>
#include <vector>
#include <string>
using namespace std;
//26 個小寫英文字母
#define NUM 26
//前綴樹節(jié)點
class Node {
public:
    Node* arr[NUM];//多叉樹(最大26個分支,因為26個小寫字母嘛)
    int end;  //代表
    int pass; //代表以此前綴為公共前綴的節(jié)點個數(shù),每次insert的時候會調(diào)整
    Node()
    {
        end = 0;
        pass = 0;
        memset(arr, 0, sizeof(arr));
    }
    ~Node()
    {
        //這里有點遞歸的意思,除了刪除當前節(jié)點,更重要的是如果當前節(jié)點的子節(jié)點還有非空。遞歸delete掉!
        for (int i = 0; i < NUM; i++)
        {
            if (arr[i]!=nullptr) delete arr[i];
        }
    }
};
//前綴樹主體
class Trie{
public:
    Node* root = nullptr;
public:
    Trie() {
        root = new Node;
    }
    //插入單詞
    void Insert(const string &x)
    {
        int size = x.size();
        Node* cur = root;
        cur->pass++;//不管insert啥,我們root空節(jié)點的pass相當于必須+1,最終這個root->pass可以代表一共insert了幾次=-=
        for (int i = 0; i<size; i++) {
            char index = x[i] - 'a';
            //該字符在當前分支下的映射為空,沒有那就new
            if (cur->arr[index] == nullptr) {
                cur->arr[index] = new Node;
            }
            cur->arr[index]->pass++; //不管 cur->arr[index] 是new的還是本來就有,insert要路過他了,他的pass+1,
            cur = cur->arr[index];//同時cur下指過去,進行下一個字符的insert
        }
        cur->end++;//insert最終將完整字符串個數(shù)end+1
    }
    //查找 完全匹配字符串 x 的數(shù)量 -->end
    int Find(const string &x)
    {
        int size = x.size();
        Node* cur = root;
        for (int i = 0; i < size; i++) {
            char index = x[i] - 'a';
            //搜索到某個字符斷了,沒有這個完整的字符串x 返回0
            if (cur->arr[index] == nullptr) return 0;
            //沒斷,繼續(xù)向下一個字符搜索;
            cur = cur->arr[index];
        }
        return cur -> end;//返回完整字符串x的有效個數(shù)end
    }
    //查找 前綴為字符串 x 的數(shù)量 -->pass
    int FindContain(const string& x)
    {
        //與Find一模一樣的邏輯,只是最后的return 變了,這體現(xiàn)了Node*封裝 int end  和int pass的好處了吧
        int size = x.size();
        Node* cur = root;
        for (int i = 0; i < size; i++) {
            char index = x[i] - 'a';
            if (cur->arr[index] == nullptr) return 0;
            cur = cur->arr[index];
        }
        return cur -> pass;
    }
    //刪掉某個完整單詞-以及這個單詞后面可能存在的所有路徑;(end>1 出現(xiàn)了很多次時,只需要end--一下)
    bool Delete(const string &x)
    {
        if (Find(x) == 0) return false;//壓根沒這個單詞,刪除失敗;
        //有這個單詞,我們需要找到他的prev前一個,delete掉他,prev的arr[x]=nullptr!
        Node* cur = root;
        Node* prev = root;
        int size = x.size();
        for (int i = 0; i < size; i++) {
            char index = x[i]-'a';
            //if (cur->arr[index] == nullptr) return false;這句不需要,都過了Find 肯定x每個字符都存在于字典樹中
            cur->pass--;//別忘了路過的路徑都得-1;
            prev = cur;
            cur = cur->arr[index];
        }
        if (cur->end==1) {//代表x所在字符串的個數(shù)只有1,直接遞歸delete刪掉它 和 他后面的子串
            delete cur;//這個delete調(diào)析構(gòu),我們析構(gòu)已經(jīng)寫好了,防止內(nèi)存泄漏;
            prev->arr[x[size - 1]-'a'] = nullptr; // prev的arr[x最后一個字符-'a'] = nullptr!
        }
        else  cur->end--;//end>1 :end--代表這個節(jié)點的有效字符串個數(shù)-1,end==1 end-- == 0,這個節(jié)點的字符有效個數(shù)為0了,但是他因為pass>1,暫時保存 后面的不刪;
        //end>1,那就end有效個數(shù)-1就行了;
        return true;
    }
};

到此這篇關(guān)于C++前綴樹字典樹的學習與模擬實現(xiàn)代碼示例的文章就介紹到這了,更多相關(guān)C++前綴樹字典樹內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

  • C++類和對象之封裝詳解

    C++類和對象之封裝詳解

    大家好,本篇文章主要講的是C++類和對象之封裝詳解,感興趣的同學趕快來看一看吧,對你有幫助的話記得收藏一下,方便下次瀏覽
    2021-12-12
  • c語言求階乘精確值示例

    c語言求階乘精確值示例

    這篇文章主要介紹了c語言求階乘精確值示例,需要的朋友可以參考下
    2014-03-03
  • Linux下實現(xiàn)C++操作Mysql數(shù)據(jù)庫

    Linux下實現(xiàn)C++操作Mysql數(shù)據(jù)庫

    由于工作需要抽出一周的時間來研究C/C++訪問各種數(shù)據(jù)庫的方法,并打算封裝一套數(shù)據(jù)庫操作類,現(xiàn)在奉上最簡單的一部分:在Linux下訪問MySQL數(shù)據(jù)庫。
    2017-05-05
  • C++ 二叉搜索樹(BST)的實現(xiàn)方法

    C++ 二叉搜索樹(BST)的實現(xiàn)方法

    這篇文章主要介紹了C++ 二叉搜索樹(BST)的實現(xiàn)方法,非常不錯,具有參考借鑒價值,需要的的朋友參考下
    2017-04-04
  • C語言利用EasyX繪制小企鵝表情包

    C語言利用EasyX繪制小企鵝表情包

    這篇文章主要為大家詳細介紹了C語言如何利用EasyX繪圖庫實現(xiàn)繪制可愛的小企鵝表情包,文中的示例代碼講解詳細,感興趣的小伙伴可以了解一下
    2022-12-12
  • OpenCV實現(xiàn)拼圖板小游戲

    OpenCV實現(xiàn)拼圖板小游戲

    這篇文章主要為大家詳細介紹了OpenCV實現(xiàn)拼圖板小游戲,文中示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2019-05-05
  • 詳解C++如何實現(xiàn)在Word文檔中創(chuàng)建列表

    詳解C++如何實現(xiàn)在Word文檔中創(chuàng)建列表

    這篇文章主要為大家詳細介紹了介紹如何使用C++在Word文檔中創(chuàng)建編號列表、項目符號列表和多級列表,感興趣的小伙伴可以跟隨小編一起學習一下
    2023-05-05
  • C++中的STL常用算法之遍歷算法詳解

    C++中的STL常用算法之遍歷算法詳解

    這篇文章主要介紹了C++中的STL常用算法之遍歷算法詳解,ransform() 可以將函數(shù)應用到容器的元素上,并將這個函數(shù)返回的值保存到另一個容器中,它返回的迭代器指向輸出容器所保存的最后一個元素的下一個位置,需要的朋友可以參考下
    2023-12-12
  • C語言 數(shù)據(jù)結(jié)構(gòu)與算法之字符串詳解

    C語言 數(shù)據(jù)結(jié)構(gòu)與算法之字符串詳解

    這篇文章將帶大家深入了解C語言數(shù)據(jù)結(jié)構(gòu)與算法中的字符串,文中主要是介紹了字符串的定義、字符串的比較以及一些串的抽象數(shù)據(jù)類型,感興趣的可以學習一下
    2022-01-01
  • C++標準模板庫map的常用操作

    C++標準模板庫map的常用操作

    今天小編就為大家分享一篇關(guān)于C++標準模板庫map的常用操作,小編覺得內(nèi)容挺不錯的,現(xiàn)在分享給大家,具有很好的參考價值,需要的朋友一起跟隨小編來看看吧
    2018-12-12

最新評論