Обход дерева от узла к корню, отслеживание пути - PullRequest
Новая
       15

Обход дерева от узла к корню, отслеживание пути

1 голос
/ 24 мая 2019

Я создаю программу для проверки файловой системы. В нем есть виртуальные файлы и каталоги, представленные в виде узлов дерева. Я хочу реализовать версию команды "pwd" как функцию в этом дереве. учитывая текущий каталог - мне нужно пройти по дереву до корня и отслеживать полный путь;

Я пробовал кое-что, но я плохо справляюсь с распределением памяти. Я буду признателен за любую помощь. Спасибо!

Вот структура дерева и моя попытка - 

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, "\0");

    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);
}

1 Ответ

1 голос
/ 24 мая 2019

В вашей программе слишком много вызовов malloc. Также strcat(newPath, "\0"); является избыточным. 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);
}
...