C语言 按前缀查找树中的单词

Question

在我的二叉搜索树中，我想创建一个函数，该函数可以获取所有以前缀开头的单词，并将所有单词存储在名为 results 的数组中这是我的树

struct BinarySearchTree_t
{
    char *mot,*def;
    struct BinarySearchTree_t *left;
    struct BinarySearchTree_t *right;
};
typedef struct BinarySearchTree_t BinarySearchTree;

我的功能 ：

size_t findWordsByPrefix(BinarySearchTree* tree, char* prefix, char*** results)
{
    BinarySearchTree *tmp;
        tmp=tree;
    static int size=0;
    if (!tmp)
        return 0;
    else if (strncmp(tmp->mot,prefix,strlen(prefix))==0)
    {
        (*results)= realloc(*results,(1+size)*sizeof(*(*results)));
        (*(*results+size))= malloc(strlen(tmp->mot)*sizeof(char));
        strcpy((*results)[size],tmp->mot);
        size++;
       return (1 + findWordsByPrefix(tmp->left,prefix, &results) + findWordsByPrefix(tmp->right,prefix, &results));
    }
    else
        return (strncmp(tmp->mot,prefix,strlen(prefix))<0)?findWordsByPrefix(tmp->right,prefix, &results):findWordsByPrefix(tmp->left,prefix, &results) ;
}

此函数应返回许多以给定前缀开头的单词。我的问题是程序在运行时崩溃，我不知道如何调整数组结果的大小所以每次我找到一个单词时，我都应该增加结果数组的大小。

我会知道如何精确地操纵这个函数（char ***results）的arg中给出的指针的指针的指针：到底是什么意思？

Answer 1

如果我只是编译您的代码，我会收到严重的编译器警告，包括：

1>binarysearchtree.c(98) : warning C4047: 'function' : 'char ***' differs in levels of indirection from 'char ****'
1>binarysearchtree.c(98) : warning C4024: 'findWordsByPrefix' : different types for formal and actual parameter 3

仅此一项就会导致崩溃 - 您正在使用错误的参数递归调用自己的函数。

接下来，我相信你需要分配一个比字符串长度多一个，以保存字符串的副本：

malloc((strlen(tmp->mot) + 1 )*sizeof(char))

接下来，您将传递一个可变大小的字符串数组 - 并将大小存储在静态变量中。 不可能知道这是否有效，所以不要这样做。

相反，如果你想使用字符串的动态数组，我建议提取一个结构来保存它们，如下所示：

struct ResultTable_t
{
    int    size;
    char **results;
};
typedef struct ResultTable_t ResultTable;
void InitializeResults(ResultTable *p_table)
{
    p_table->size = 0;
    p_table->results = NULL;
}
void AddResult(ResultTable *p_table, char *result)
{
    if (result == NULL)
        return;
    p_table->size++;
    p_table->results = realloc(p_table->results, p_table->size * sizeof(*p_table->results));
    p_table->results[p_table->size-1] = malloc((strlen(result) + 1) * sizeof(**p_table->results));
    strcpy(p_table->results[p_table->size-1], result);
}
void FreeResults(ResultTable *p_table)
{
    if (p_table->results != NULL)
    {
        int i;
        for (i = 0; i < p_table->size; i++)
        {
            free(p_table->results[i]);
        }
        free(p_table->results);
    }
    p_table->size = 0;
    p_table->results = NULL;
}

（作为改进，您可以考虑对结果表使用几何增长而不是线性增长。

然后你的函数变成：

size_t findWordsByPrefix(BinarySearchTree* tree, char* prefix, ResultTable *p_table)
{
    if (!tree)
        return 0;
    else if (strncmp(tree->mot,prefix,strlen(prefix))==0)
    {
        AddResult(p_table, tree->mot);
        return (1 + findWordsByPrefix(tree->left,prefix, p_table) + findWordsByPrefix(tree->right,prefix, p_table));
    }
    else if (strncmp(tree->mot,prefix,strlen(prefix))<0)
    {
        return findWordsByPrefix(tree->right,prefix, p_table);
    }
    else
    {
        return findWordsByPrefix(tree->left,prefix, p_table);
    }
}

你会像这样使用它：

ResultTable results;
InitializeResults(&results);
// Get some prefix to search for.
char prefix = GetSomePrefix();
int size = findWordsByPrefix(tree, prefix, &results);
// Do something with the results
// Free all memory of the results
FreeResults(&results);

更新

如果ResultTable由于某种原因令人反感，您可以直接传入动态数组和数组大小：

void AddResult(char ***p_results, int *p_size, char *word) 
{ 
    if (word == NULL) 
        return; 
    (*p_size)++; 
    (*p_results) = realloc(*p_results, ((*p_size)+1) * sizeof(**p_results)); 
    (*p_results)[(*p_size)-1] = malloc((strlen(word) + 1) * sizeof(***p_results)); 
    strcpy((*p_results)[(*p_size)-1], word);
}
void FreeResults(char ***p_results, int *p_size)
{
    int i;
    if (p_results == NULL || *p_results == NULL)
        return;
    for (i = 0; i < (*p_size); i++)
    {
        free ((*p_results)[i]);
    }
    free (*p_results);
    *p_results = NULL;
    *p_size = 0;
}
size_t findWordsByPrefix(BinarySearchTree* tree, char* prefix, char ***p_results, int *p_size)
{
    if (!tree)
        return 0;
    else if (strncmp(tree->mot,prefix,strlen(prefix))==0)
    {
        AddResult(p_results, p_size, tree->mot);
        return (1 + findWordsByPrefix(tree->left,prefix, p_results, p_size) + findWordsByPrefix(tree->right,prefix, p_results, p_size));
    }
    else if (strncmp(tree->mot,prefix,strlen(prefix))<0)
    {
        return findWordsByPrefix(tree->right,prefix, p_results, p_size);
    }
    else
    {
        return findWordsByPrefix(tree->left,prefix, p_results, p_size);
    }
}

并像这样使用：

char **results = NULL;
int    tablesize = 0;
// Get some prefix to search for.
char prefix = GetSomePrefix();
int size = findWordsByPrefix(tree, prefix, &results, &tablesize);
// Do something with the results
// Free all memory of the results
FreeResults(&results, &tablesize);