c - 创建 bst 时内存泄漏，需要解析帮助

Question

Node *addToTree(Node *head, Node *newNode) {
    if (head == NULL) {
        head = newNode;
    } else {
        if (newNode->price < head->price) {
            head->left = addToTree(head->left, newNode);
        } else
        if (newNode->price > head->price) {
            head->right = addToTree(head->right, newNode);
        } else
        if (newNode->price == head->price) {
            free(newNode);
        }
    }
    return head;
}

Node *getCars(char *name) {
    FILE *fp;
    if ((fp = fopen(name, "r")) == NULL) {
        return NULL;
    } else {
        Node *head = NULL;
        Node *tmp;
        char delim[2] = "|";
        char car[MAXLINELENGTH] = {0};
        char *token = NULL;
        int ch;
        while (!feof(fp)) {
            tmp = malloc(sizeof(Node));
            tmp->left = tmp->right = NULL;
            fgets(car, MAXLINELENGTH, fp);
            token = strtok(car, delim);
            while (token != NULL) {
                if (strcmp(token, "model") == 0) {
                    token = strtok(NULL, delim);
                    strcpy(tmp->model, token);
                } else
                if (strcmp(token, "make") == 0) {
                    token = strtok(NULL, delim);    
                    strcpy(tmp->make, token);
                } else
                if (strcmp(token, "price") == 0) {
                    token = strtok(NULL, delim);                
                    tmp->price = atoi(token);
                } else
                if (strcmp(token, "year") == 0) {
                    token = strtok(NULL, delim);                
                    tmp->year = atoi(token);
                } else
                if (strcmp(token, "color") == 0) {
                    token = strtok(NULL, delim);    
                    strcpy(tmp->color, token);
                } else
                if (strcmp(token, "type") == 0) {
                    token = strtok(NULL, delim);
                    if (token == NULL) {
                        break;
                    }   
                    strcpy(tmp->type, token);
                } else
                if (strcmp(token, "mileage") == 0) {
                    token = strtok(NULL, delim);    
                    tmp->mileage = atoi(token);
                }
                token = strtok(NULL, delim);
            }
            if (check("makes.txt", tmp->make) != 1) {
                continue;
            } else
            if (check("colors.txt", tmp->color) != 1) {
                continue;
            } else
            if (check("types.txt", tmp->type) != 1) {
                continue;
            } else {
                head = addToTree(head, tmp);
            }
        }
        free(tmp);
        fclose(fp);
        return head;
    }
}

因此，对于家庭作业，我应该解析一个输入文件，其中包含大约 10000 辆汽车的制造商、型号、颜色、类型、价格、里程和年份信息，并根据价格将它们输入到 BST 中，当我运行代码，它说我在 malloc tmp 指针的那一行丢失了 274 个字节。我只是想知道解决这个问题的方法是什么，而且我真的可以提供任何关于解析的建议/帮助，因为对我来说我的 getCars 函数很难看，而且它还需要大约 15 秒才能运行，非常感谢任何帮助!

Answer 1

您的代码中存在多个问题:

• while (!feof(fp)) 总是错误的。读这个:Why is “while ( !feof (file) )” always wrong?

• 您应该检查所有属性的缺失值。

• 当您无法匹配品牌、颜色或类型时，您不会释放节点。

• 你不应该在解析循环后释放 tmp:它可能已经被插入到 BST 中，如果文件为空，它甚至可能未被初始化。

• 令人惊讶的是，您没有将汽车插入 BST，因为另一辆汽车的价格相同...您可能应该更准确地检查重复项。

这是一个改进的版本:

Node *addToTree(Node *head, Node *newNode) {
    if (head == NULL) {
        head = newNode;
    } else {
        if (newNode->price < head->price) {
            head->left = addToTree(head->left, newNode);
        } else
        if (newNode->price > head->price) {
            head->right = addToTree(head->right, newNode);
        } else
        if (newNode->price == head->price) {
            free(newNode);
        }
    }
    return head;
}

Node *getCars(const char *name) {
    FILE *fp;
    if ((fp = fopen(name, "r")) == NULL) {
        return NULL;
    } else {
        Node *head = NULL;
        char delim[] = "|";
        char car[MAXLINELENGTH];

        while (fgets(car, sizeof car, fp)) {
            Node *tmp = malloc(sizeof(Node));
            /* initialize all members */
            tmp->left = tmp->right = NULL;
            tmp->model[0] = tmp->make[0] = tmp->color[0] = tmp->type[0] = '\0';
            tmp->price = tmp->year = tmp->mileage = 0; 
            char *token = token = strtok(car, delim);
            while (token != NULL) {
                if (strcmp(token, "model") == 0) {
                    token = strtok(NULL, delim);
                    if (token == NULL) break;
                    strcpy(tmp->model, token);
                } else
                if (strcmp(token, "make") == 0) {
                    token = strtok(NULL, delim);    
                    if (token == NULL) break;
                    strcpy(tmp->make, token);
                } else
                if (strcmp(token, "price") == 0) {
                    token = strtok(NULL, delim);                
                    if (token == NULL) break;
                    tmp->price = atoi(token);
                } else
                if (strcmp(token, "year") == 0) {
                    token = strtok(NULL, delim);                
                    if (token == NULL) break;
                    tmp->year = atoi(token);
                } else
                if (strcmp(token, "color") == 0) {
                    token = strtok(NULL, delim);    
                    if (token == NULL) break;
                    strcpy(tmp->color, token);
                } else
                if (strcmp(token, "type") == 0) {
                    token = strtok(NULL, delim);
                    if (token == NULL) break;
                    strcpy(tmp->type, token);
                } else
                if (strcmp(token, "mileage") == 0) {
                    token = strtok(NULL, delim);    
                    if (token == NULL) break;
                    tmp->mileage = atoi(token);
                }
                token = strtok(NULL, delim);
            }
            if (check("makes.txt", tmp->make) != 1
            ||  check("colors.txt", tmp->color) != 1
            ||  check("types.txt", tmp->type) != 1) {
                /* unrecognized make, type or color: discard entry */
                free(tmp);
            } else {
                head = addToTree(head, tmp);
            }
        }
        fclose(fp);
        return head;
    }
}