c - 在关联数组中查找此数据的最佳算法？

Question

我现在正在做一项实验室作业，制作一款 Hangman 游戏，我正在尝试解决一个特定的功能。我有一个关联数组，它只是一个二叉树，其中每个节点都是一个键/值对，键是一个字符串，值是一个字符串 vector 。这些功能对于我的问题并不重要。我需要知道的是……

我需要返回一个指向包含树中最大元素数的 vector 的指针。我试图找到一种方法来通过深度优先搜索来做到这一点，但我不太清楚要比较什么以及如何跟踪所有内容。

有人可以给我伪代码或如何做到这一点的想法吗？

编辑:这是我当前的算法。

GENERIC_VECTOR* find_greatest(Node* root, MYSTRING* pattern) {
    if(root != NULL) {
        GENERIC_VECTOR* left = find_greatest(root->left, pattern);
        GENERIC_VECTOR* right = find_greatest(root->right, pattern);
        int sizeL = generic_vector_size(*left);
        int sizeR = generic_vector_size(*right);
        int sizeT = generic_vector_size(root->data->value);
        if(sizeL > sizeR) {
            if(sizeL > sizeT) {
                mystring_destroy(pattern);
                *pattern = mystring_copy(root->left->data->key);
                return left;
            } else {
                mystring_destroy(pattern);
                *pattern = mystring_copy(root->data->key);
                return &(root->data->value);
            }
        } else {
            if(right != NULL) {
                if(sizeR > sizeT) {
                    mystring_destroy(pattern);
                    *pattern = mystring_copy(root->right->data->key);
                    return right;
                } else {
                    mystring_destroy(pattern);
                    *pattern = mystring_copy(root->data->key);
                    return &(root->data->value);
                }
            } else {
                mystring_destroy(pattern);
                *pattern = mystring_copy(root->data->key);
                return &(root->data->value);
            }
        }
    } else return NULL;
}

Answer 1

由于您的 DS 是一棵树，因此您必须使用其中一种树遍历算法(即中序、前序或后序):

伪代码:

global int maxval = -1;
global NODE *max = NULL; // this pointer will contain the result!

getMaxVal(NODE *n){
    if(n!==NULL){
        if( n->val[key].length > maxval ){
            maxval = n->val[key].length;
            max = n; 
        }
            getMaxVal(n->left);
            getMaxVal(n->right); 
    }
}