检查 C 字典中的单词

Question

我有一个项目，其中有一个文件(.dic)，其中包含许多不同大小的单词。另一个文件(.pal)包含一些文字。对于 .pal 文件中的每个单词，我必须在具有相同单词数的单词列表中找到它的位置，这些单词按 .dic 文件中的字母顺序排列。

例如， 在 .dic 文件中:

car
banana
dog
flower
tar

所以字典会是这样的:

3 letters: [car->dab->dog->tar]
6 letters: [banana->flower]

在 .pal 文件中:

dog
flower

所以输出将是:

dog in position 3 
flower in position 2

我的问题是:在 C 中实现此功能的最佳数据结构是什么，以便占用最少的内存和时间？

我正在考虑有一个矩阵，其中每个第一个索引(index1)对应于单词中的字母数量，第二个索引(index2)对应于我要查找的单词的第一个字母。该矩阵的每个元素都是具有索引 1 字母并从字母索引 2 开始的单词列表。

示例:

 | A  | B  | C  | .....
_______________

1|list|list|list|
2|list|....|....|
3|...
.
.

因此“dog”将位于矩阵[3][D]内的列表中。

问题1:如果没有字母数量或首字母不同的单词，矩阵就会出现漏洞 -> 浪费太多内存？

问题 2:要知道我之前询问的位置，我必须对我正在使用的列表之前的每个列表的元素数量进行求和。

示例:“狗”位置为

number of element in list [3][A]+number of element in list [3][B]+number of element in list [3][C]+"dog" position in the list

因此，当我在列表中插入一个单词时，我必须更新下一个矩阵元素中列表的元素数量。 -> 耗时？

那么你觉得这个方法怎么样？您有更好的想法吗？

Answer 1

What is the best data structure to implement this in C, so that it takes the least memory and time?

同时获得最少内存和最少时间是很困难的。如果您想保持尽可能低的内存使用量，则需要动态内存分配，考虑到时间，这会非常昂贵。

为了降低内存使用量，您可以采用以下数据结构:

 #define MAX_WORD_LEN 50
 char** dic[MAX_WORD_LEN];

你可以像这样使用它:

index 0: -----> char*, char*, char*, ...   // Words with length 1
                 |      |      |
                 |      |      ------> string (i.e. char, '\0')
                 |      |
                 |      ------> string (i.e. char, '\0')
                 |
                 ------> string (i.e. char, '\0')

index 1: -----> char*, char*, ...   // Words with length 2
                 |      |
                 |      ------> string (i.e. char, char, '\0')
                 |
                 ------> string (i.e. char, char, '\0')

这允许您为每个长度存储可变数量的单词，并且您不会为每个字符串分配超出所需的内存。它就像一个矩阵，但好处是每行可以有不同数量的列。

但是，您将需要相当多的动态内存处理，即 malloc、realloc 和 strdup。

为了节省一些执行时间，您应该将“char*, char*, char*, ...”数组增大大于 1 的 N，并将未使用的条目设置为 NULL。这将节省大量的realloc，但您需要跟踪每行中分配的元素数量。这可能需要这样的东西:

struct x
{
    char** data;
    int number_allocated;
}

#define MAX_WORD_LEN 50
struct x dic[MAX_WORD_LEN];

如果内存使用量非常大，您可以避免使用“char*, char* ...”数组，而只为每个字长使用一个大的 char 数组。喜欢:

index 0: -----> 'a', '\0', 'I', '\0', ...
index 1: -----> 'b', 'e', '\0', 't', 'o', '\0', ....

您可以这样做，因为字符数组中的所有单词都具有相同的长度。

在这种情况下，你会得到类似的东西:

struct x
{
    char* data;
    int bytes_allocated;
    int number_of_words;
}

#define MAX_WORD_LEN 50
struct x dic[MAX_WORD_LEN];