如何使一个字的线索店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

回答

相关问题