从节点到根遍历树，跟踪路径

Question

我正在构建一个模拟文件系统的程序。它具有虚拟文件和目录，表示为树中的节点。我想实现 "pwd" 命令的一个版本作为该树上的一个函数。给定当前目录 - 我需要遍历树直到根并跟踪完整路径；

我已经尝试了一些方法，但我无法很好地处理内存分配。我会 appriciate 任何帮助。谢谢！

这是树结构和我的尝试 -

typedef struct Node {
    char* nameOfTheFile;
    struct Node* firstChild;
    struct Node* nextSibling;
    struct Node* parent;
    int isFile;
} NODE;

NODE* root;
NODE* currentLocation; 

char* prepend(char* path, const char* toAdd, int lastWordBeforeRoot)
{

    char *newPath = (char*)malloc(strlen(path) + 3 + strlen(toAdd));
    strcat(newPath, path);

    if(!lastWordBeforeRoot && strcmp(toAdd, "/") != 0){
        strcat(newPath,"/");
    }
    strcat(newPath,toAdd);
    free(path);
    strcat(newPath, "[=10=]");

    return newPath;
}

void pwd() {

    NODE* currentFolder = currentLocation;
    char* path = (char*)malloc(sizeof(char));

    while (currentFolder != NULL) {

        if (currentFolder->parent != NULL && strcmp(currentFolder->parent->nameOfTheFile, "/") == 0) 
        {

            path = prepend(path, currentFolder->nameOfTheFile, 1);
        }
        else 
        {
            path = prepend(path, currentFolder->nameOfTheFile, 0);
        }

        currentFolder = currentFolder->parent;

    }
    printf("%s \n", path);
}

Answer 1

您的程序中 malloc 调用过多。 strcat(newPath, "[=12=]"); 也是多余的。 strcat 将自动添加尾随 NULL 字符。

下面给出了一个简化版本，它将支持最多 256 字节的路径长度并指示更长路径的错误。

char* prepend(char* path, const char* toAdd, int lastWordBeforeRoot)
{
    if (strlen(path) + strlen(add) + 3 > 256)
    {
        // handle error
        return(path);
    }
    if(!lastWordBeforeRoot && strcmp(toAdd, "/") != 0)
    {
        strcat(path,"/");
    }
    strcat(path,toAdd);
    return (path);
}

void pwd() 
{
    NODE* currentFolder = currentLocation;
    char* path = (char*)malloc(256 * sizeof(char));

    while (currentFolder != NULL) 
    {
        if (currentFolder->parent != NULL && strcmp(currentFolder->parent->nameOfTheFile, "/") == 0) 
        {
            path = prepend(path, currentFolder->nameOfTheFile, 1);
        }
        else 
        {
            path = prepend(path, currentFolder->nameOfTheFile, 0);
        }
        currentFolder = currentFolder->parent;
    }
    printf("%s \n", path);
    free(path);
}

从节点到根遍历树，跟踪路径

Traverse a tree from node to root keeping track of path

c

tree

memory-management

traversal