在树中查找函数

Question

我有一个函数有问题，该函数应该找到树中具有相同名称的所有节点，我必须保存找到的每个节点的路径。

我已经使用基于深度优先搜索的算法实现了我的功能，但问题是保存的路径不完整。例如，节点在路径 /dir0rid/dir0rid/dir1rid/file1 中，函数只保存路径 /dir1rid/file1.

这是我的功能：

void find(node_t *Fs) {
    int i = 0;

    while (i < 1024) {
        if (Fs->figli[i] != NULL) {
            if (Fs->figli[i]->nome_file == NULL) {
                i++;
            } else {
                if (strcmp(Fs->figli[i]->nome_file, "DELETED") != 0) {
                    if (Fs->figli[i]->type == 1) {
                        i++;
                    } else {
                        finded[j_index] = Fs->figli[i];
                        j_index++;

                        find(Fs->figli[i]);
                        i++;
                        j_index--;
                        finded[j_index] = NULL;
                    }
                } else {
                    i++;
                }
            }
        } else {
            i++;
        }
    }

    if (hash_search(Fs, file_cercato) != NULL) {
        int j = 0;
        percorso[f_index][0] = '[=10=]';

        while (finded[j] != NULL) {
            strcat(percorso[f_index], "/");
            strcat(percorso[f_index], finded[j]->nome_file);
            j++;
        }

        strcat(percorso[f_index], "/");
        strcat(percorso[f_index], file_cercato);
        f_index++;
        percorso[f_index][0] = '[=10=]';
    }
    return;
}

Answer 1

循环的简化版本（我省略了hashstuff）：

void find2 (node_t* Fs){

    int i ;

    for(i=0; i < 1024; i++){
        if (Fs->figli[i] == NULL) continue;
        if(Fs->figli[i]->nome_file == NULL) continue;
        if(!strcmp(Fs->figli[i]->nome_file,"DELETED")) continue;
        if(Fs->figli[i]->type==1) continue;
        finded[j_index]=Fs->figli[i];

        j_index++;
        find(Fs->figli[i]);
        j_index--; // <<--

        finded[j_index]=NULL; // <<--
    }
}

现在，我不明白你的逻辑，但我认为 j_index--; 是错误的。它应该可能放在之后 finded[j_index]=NULL;

Answer 2

您的代码中存在一些问题：

您应该使用 for 循环来简化索引更新并使代码更具可读性。
在递归调用find之前，您应该将finded[j_index]设置为NULL，或者将最终循环更改为在j_index处停止。

这是修改后的版本：

void find(node_t *Fs) {
    for (int i = 0; i < 1024; i++) {
        if (Fs->figli[i] != NULL
        &&  Fs->figli[i]->type != 1
        &&  Fs->figli[i]->nome_file != NULL
        &&  strcmp(Fs->figli[i]->nome_file, "DELETED") != 0) {
            finded[j_index] = Fs->figli[i];
            j_index++;
            find(Fs->figli[i]);
            j_index--;
        }
    }
    if (hash_search(Fs, file_cercato) != NULL) {
        percorso[f_index][0] = '[=10=]';
        for (j = 0; j < j_index; j++) {
            strcat(percorso[f_index], "/");
            strcat(percorso[f_index], finded[j]->nome_file);
        }
        strcat(percorso[f_index], "/");
        strcat(percorso[f_index], file_cercato);
        f_index++;
        percorso[f_index][0] = '[=10=]';
    }
}

另请注意，所有这些使用的全局变量都应移动到作为参数传递给 find() 的结构中。

在树中查找函数

Find function in a tree

c

function

depth-first-search