如何使一個字的線索店reincidence用C

我的線索存儲焦炭和位置（這是在當前字被讀取結束的文本的位置）的當前節點。如何使一個字的線索店reincidence用C

如果我讀了100位和第200位另一個詞「富」字「富」，如何讓我的節點商店這2 ocurrences？有沒有一個快速的方法（數組或更快的實現）還是我需要實現鏈表？

2017-06-20 DcCoO

當元素數量未知並且事先沒有使用無用區域時，當使用數組時，隨着元素數量的增加，擴展數組的過程變得不利。如果在這種情況下不需要隨機訪問，則鏈接列表是有利的。在處理少量數據時，兩者沒有多大區別（數組可能是有利的，但實際時間並不重要） – BLUEPIXY

兩者沒有太大的區別 - >沒有太大的區別。 – BLUEPIXY

在維基百科有一個很好的介紹[** Trie - 實施策略**]（https://en.wikipedia.org/wiki/Trie#Implementation_strategies）。 –

所以，你的字典樹節點看起來像

struct trie_node { 
    struct trie_node *next; 
    strict trie_node *child; 
    wchar_t   character; 
    off_t    position; 
};

代替，如果數據總是在內存中，當然你可以使用size_t position;。

如果我們假設許多前綴不映射到特定位置（因爲它們是不完整的話），這可能是使用了位置獨立的陣列，即有用。

struct positions { 
    size_t   count_max; 
    size_t   count; 
    off_t    position[]; 
}; 

struct trie_node { 
    struct trie_node *next; 
    struct trie_node *child; 
    wchar_t   character; 
    struct positions *position; 
};

不對應於完整單詞的字符節點可以有NULL position成員。 count_max對應於分配的職位數量，並且count對應於當前的職位數量。數組可以在必要時重新分配和調整大小。這種數組調整在實際應用中很常見; （重新分配）的開銷被認爲是相當可接受的，尤其是與替代方案相比。

另一個有趣的選擇是使用線性數組來表示的順序在文本的話，因爲它們出現，在指定所述陣列中的第一次出現的索引的字典樹節點的position構件。每個陣列條目將包含下一個出現的索引，加上任選的鏈接回字典樹節點：

#include <stdlib.h> 
#include <limits.h> 

struct trie_node { 
    struct trie_node *next; 
    struct trie_node *child; 
    wchar_t   character; 
    size_t    index;  /* NO_INDEX if no occurrences */ 
    size_t    occurs; /* Num of occurrences, optional */ 
    wchar_t   word[]; /* Optional, entire word */ 
}; 

/* When 'index' refers to 'none', use: */ 
#define NO_INDEX SIZE_MAX 

struct occurrence { 
    off_t    offset; 
    size_t    next; 
    struct trie_node *node; /* Optional */ 
};

的容器結構將具有的陣列，且該特里結構將懸吊它：

struct text { 
    size_t    count_max; 
    size_t    count; 
    struct occurrence *occurrences; 
    struct trie_node *trie; 
};

然後你的函數會帶一個指向struct text的指針。

在struct text的occurrences陣列可以根據需要被動態地重新分配。（這也是爲什麼first成員特里樹節點是索引數組，而不是一個指針：如果它是一個指針，我們可能要經過整個特里更新所有節點的指針，重新分配時陣列，否則。）

注意，因爲我們使用一個size_t作爲索引到所述陣列，NO_INDEX是最大可能值，並且size_t是無符號整數類型，它是足夠的，以檢查if (i < count)以驗證索引i已驗證。

對應於一個完整的字中的每個字典樹節點具有index != NO_INDEX，和C99柔性陣列構件word初始化爲全字（包括結尾L'\0'）。該occurs成員將有字的出現次數，如果它是有用。（對於它，沒有需要，除了我們人類可能對每個詞的出現次數感興趣之外。）

該方案允許直接訪問文本中的單詞序列。

如果在數組中增加偏移量，則可以使用二分查找來查找特定偏移之間的單詞。因爲每個事件都有一個反向鏈接到trie節點，該節點包含word成員中的完整單詞，所以很容易打印出文件中出現的任何單詞，而不必掃描整個樹狀結構。

我寫了這個答案，因爲我想說明如何以這種方式組合兩個非常不同的數據結構，可以打開非常有效的訪問數據的方法。我不能說是否有用，因爲有用性取決於正在解決的問題。

來源

2017-06-20 06:06:30

如何使一個字的線索店reincidence用C

回答

相關問題