二叉树初始化函数中的内存泄漏
Memory Leak in Binary Tree Initialize Function
我正在尝试根据 C 语言中的后缀用户输入字符串创建和评估二叉表达式树。但是，我的二叉树初始化函数导致内存泄漏。总结一下我的算法，用户输入一个后缀字符串输入，它被一个函数解析并组装到树中。这是我的完整代码：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define TRUE 1
#define FALSE 0
// Define binary expression tree data structure
typedef struct binExpTree {
char *val;
struct binExpTree *left;
struct binExpTree *right;
} expTree;
// Define expression tree stack data structure
typedef struct expTreeStack {
int height;
int used;
expTree **expTreeDarr;
} treeStack;
// Function prototypes
void initStack(treeStack *stack);
expTree * getTopStack(treeStack *stack);
int isEmptyStack(treeStack *stack);
void pushStack(treeStack *stack, expTree *treeNode);
expTree * popStack(treeStack *stack);
void clearStack(treeStack *stack);
expTree * initTree(char *val);
void printCommands();
expTree * parseExpression(char *expString);
void clearTree(expTree *rootNode);
void printInfix(expTree *rootNode);
void printPrefix(expTree *rootNode);
int evalExpression(expTree *rootNode);
/* File contains all functions necessary for stack operations */
// Initialize empty binary tree stack of size 4
void initStack(treeStack *stack) {
stack->height = 4;
stack->used = 0;
stack->expTreeDarr = (expTree **)malloc(sizeof(expTree *) * stack->height);
}
// Return the tree node from the stack's top
expTree * getTopStack(treeStack *stack) {
if (stack->used > 0) {
return stack->expTreeDarr[stack->used - 1];
}
else {
return NULL;
}
}
// Discern whether tree stack is empty
int isEmptyStack(treeStack *stack) {
if (stack->used == 0) {
return TRUE;
}
else {
return FALSE;
}
}
// Push tree node pointer onto stack
void pushStack(treeStack *stack, expTree *treeNode) {
if (stack->used == stack->height) {
expTree **expTreeTmp = stack->expTreeDarr;
stack->height += 4;
stack->expTreeDarr = (expTree **)malloc(sizeof(expTree *) * stack->height);
for (int i = 0; i < stack->used; i++) {
stack->expTreeDarr[i] = expTreeTmp[i];
//free(expTreeTmp[i]);
}
free(expTreeTmp);
}
stack->expTreeDarr[stack->used] = treeNode;
stack->used = stack->used + 1;
}
// Pop tree node pointer from the stack
expTree * popStack(treeStack *stack) {
expTree *stackTmp = getTopStack(stack);
expTree *newNode = (expTree *)malloc(sizeof(expTree));
*newNode = *stackTmp;
stack->used -= 1;
return newNode;
}
// Empty stack of all data (make sure this works)
void clearStack(treeStack *stack) {
for (int i = 0; i < stack->used; i++) {
clearTree(stack->expTreeDarr[i]);
}
free(stack->expTreeDarr);
stack->used = 0;
stack->height = 0;
}
/* File contains all functions necessary for binary tree operations */
// Initialize binary expression tree with specified operator/operand
expTree * initTree(char *val) {
expTree *newTree = (expTree *)malloc(sizeof(expTree));
newTree->val = (char *)malloc(strlen(val) + 1);
strcpy(newTree->val, val);
newTree->left = NULL;
newTree->right = NULL;
return newTree;
}
// Print commands available to the user
void printCommands() {
printf("The commands for this program are:\n\n");
printf("q - to quit the program\n");
printf("? - to list the accepted commands\n");
printf("or any postfix mathematical expression using the operators of *, /, +, -\n");
}
// Return size of binary expression tree
int sizeTree(expTree *treeNode) {
if (treeNode == NULL) {
return 0;
}
else {
return 1 + sizeTree(treeNode->left) + sizeTree(treeNode->right);
}
}
// Construct a postfix binary expression tree from expression string
expTree * parseExpression(char *expString) {
char *expStringCopy = (char *)malloc(strlen(expString) + 1);
expTree *treeNode;
treeStack expStack;
initStack(&expStack);
strcpy(expStringCopy, expString);
char *expStringTok = strtok(expStringCopy, " ");
while (expStringTok != NULL) {
if (*expStringTok == '+' || *expStringTok == '-' ||
*expStringTok == '*' || *expStringTok == '/') {
if (expStack.used < 2) {
return NULL;
}
treeNode = initTree(expStringTok);
treeNode->right = popStack(&expStack);
treeNode->left = popStack(&expStack);
pushStack(&expStack, treeNode);
}
else {
treeNode = initTree(expStringTok);
pushStack(&expStack, treeNode);
}
expStringTok = strtok(NULL, " ");
}
if (expStack.used > 1 || (*(treeNode->val) != '+' && *(treeNode->val) != '-' &&
*(treeNode->val) != '*' && *(treeNode->val) != '/')) {
return NULL;
}
free(expStringCopy);
treeNode = popStack(&expStack);
clearStack(&expStack);
return treeNode;
}
// Clear binary expression tree
void clearTree(expTree *rootNode) {
if (rootNode == NULL) {
return;
}
else {
clearTree(rootNode->left);
clearTree(rootNode->right);
free(rootNode->val);
free(rootNode);
}
}
// Print infix notation of expression
void printInfix(expTree *rootNode) {
if (rootNode == NULL) {
return;
}
else {
if (*(rootNode->val) == '+' || *(rootNode->val) == '-' ||
*(rootNode->val) == '*' || *(rootNode->val) == '/') {
printf("( ");
}
printInfix(rootNode->left);
printf(" %s ", rootNode->val);
printInfix(rootNode->right);
if (*(rootNode->val) == '+' || *(rootNode->val) == '-' ||
*(rootNode->val) == '*' || *(rootNode->val) == '/') {
printf(" )");
}
}
}
// Print prefix notation of expression
void printPrefix(expTree *rootNode) {
if (rootNode == NULL) {
return;
}
else {
printf(" %s ", rootNode->val);
printPrefix(rootNode->left);
printPrefix(rootNode->right);
}
}
// Evaluate the expression tree
int evalExpression(expTree *rootNode) {
char op;
if (*(rootNode->val) == '+') {
return evalExpression(rootNode->left) + evalExpression(rootNode->right);
}
else if (*(rootNode->val) == '-') {
return evalExpression(rootNode->left) - evalExpression(rootNode->right);
}
else if (*(rootNode->val) == '*') {
return evalExpression(rootNode->left) * evalExpression(rootNode->right);
}
else if (*(rootNode->val) == '/') {
return evalExpression(rootNode->left) / evalExpression(rootNode->right);
}
else {
return atoi(rootNode->val);
}
}
int main(int argc, char const *argv[])
{
char input[300];
expTree *expPostfix;
/* set up an infinite loop */
while (1)
{
fgets(input,300,stdin);
/* remove the newline character from the input */
int i = 0;
while (input[i] != '\n' && input[i] != '[=10=]') {
i++;
}
input[i] = '[=10=]';
/* check if user enter q or Q to quit program */
if ( (strcmp (input, "q") == 0) || (strcmp (input, "Q") == 0) )
break;
/* check if user enter ? to see command list */
else if ( strcmp (input, "?") == 0)
printCommands();
/* user enters an expression */
else {
// Parse the expression into a binary expression tree
printf("%s\n", input);
expPostfix = parseExpression(input);
// Discern whether expression is valid
if (expPostfix == NULL) {
printf("Invalid expression. Enter a valid postfix expression \n");
continue;
}
// Print the expression in infix notation
printf("Infix notation: ");
printInfix(expPostfix);
printf("\n");
// Print the expression in prefix notation
printf("Prefix notation: ");
printPrefix(expPostfix);
printf("\n");
// Print the expression in postfix notation
printf("Postfix notation: ");
printf("%s\n", input);
// Evaluate expression and print result
printf("Expression result: %d \n\n", evalExpression(expPostfix));
clearTree(expPostfix);
}
}
printf("\nGoodbye\n");
return 0;
}
基于 运行 Valgrind 和“1 1 -”的输入，这是输出：
==35604==
==35604== HEAP SUMMARY:
==35604== in use at exit: 72 bytes in 3 blocks
==35604== total heap usage: 13 allocs, 10 frees, 2,236 bytes allocated
==35604==
==35604== 24 bytes in 1 blocks are definitely lost in loss record 1 of 2
==35604== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==35604== by 0x10952C: initTree (proj4base_38.c:143)
==35604== by 0x1096CC: parseExpression (proj4base_38.c:194)
==35604== by 0x109B8A: main (proj4base_38.c:323)
==35604==
==35604== 48 bytes in 2 blocks are definitely lost in loss record 2 of 2
==35604== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==35604== by 0x10952C: initTree (proj4base_38.c:143)
==35604== by 0x109719: parseExpression (proj4base_38.c:201)
==35604== by 0x109B8A: main (proj4base_38.c:323)
==35604==
==35604== LEAK SUMMARY:
==35604== definitely lost: 72 bytes in 3 blocks
==35604== indirectly lost: 0 bytes in 0 blocks
==35604== possibly lost: 0 bytes in 0 blocks
==35604== still reachable: 0 bytes in 0 blocks
==35604== suppressed: 0 bytes in 0 blocks
==35604==
==35604== For lists of detected and suppressed errors, rerun with: -s
==35604== ERROR SUMMARY: 2 errors from 2 contexts (suppressed: 0 from 0)
看来罪魁祸首是我的 initTree() 函数。但是，我就是想不通为什么会丢失这段记忆。我希望这不是太多的代码。这是之前的编辑，有人告诉我没有足够的信息可以继续。
泄漏是由popStack引起的，因为函数退出时stackTmp的目标被泄漏：
expTree * popStack(treeStack *stack) {
expTree *stackTmp = getTopStack(stack);
expTree *newNode = (expTree *)malloc(sizeof(expTree));
*newNode = *stackTmp;
stack->used -= 1;
return newNode;
}
鉴于堆栈似乎是树的独占所有者，并且不再有指向它的指针，popStack 可以通过简单地不进行复制来避免泄漏并返回原件：
expTree * popStack(treeStack *stack) {
expTree *topNode = getTopStack(stack);
stack->used -= 1;
return topNode;
}
我正在尝试根据 C 语言中的后缀用户输入字符串创建和评估二叉表达式树。但是，我的二叉树初始化函数导致内存泄漏。总结一下我的算法，用户输入一个后缀字符串输入，它被一个函数解析并组装到树中。这是我的完整代码：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define TRUE 1
#define FALSE 0
// Define binary expression tree data structure
typedef struct binExpTree {
char *val;
struct binExpTree *left;
struct binExpTree *right;
} expTree;
// Define expression tree stack data structure
typedef struct expTreeStack {
int height;
int used;
expTree **expTreeDarr;
} treeStack;
// Function prototypes
void initStack(treeStack *stack);
expTree * getTopStack(treeStack *stack);
int isEmptyStack(treeStack *stack);
void pushStack(treeStack *stack, expTree *treeNode);
expTree * popStack(treeStack *stack);
void clearStack(treeStack *stack);
expTree * initTree(char *val);
void printCommands();
expTree * parseExpression(char *expString);
void clearTree(expTree *rootNode);
void printInfix(expTree *rootNode);
void printPrefix(expTree *rootNode);
int evalExpression(expTree *rootNode);
/* File contains all functions necessary for stack operations */
// Initialize empty binary tree stack of size 4
void initStack(treeStack *stack) {
stack->height = 4;
stack->used = 0;
stack->expTreeDarr = (expTree **)malloc(sizeof(expTree *) * stack->height);
}
// Return the tree node from the stack's top
expTree * getTopStack(treeStack *stack) {
if (stack->used > 0) {
return stack->expTreeDarr[stack->used - 1];
}
else {
return NULL;
}
}
// Discern whether tree stack is empty
int isEmptyStack(treeStack *stack) {
if (stack->used == 0) {
return TRUE;
}
else {
return FALSE;
}
}
// Push tree node pointer onto stack
void pushStack(treeStack *stack, expTree *treeNode) {
if (stack->used == stack->height) {
expTree **expTreeTmp = stack->expTreeDarr;
stack->height += 4;
stack->expTreeDarr = (expTree **)malloc(sizeof(expTree *) * stack->height);
for (int i = 0; i < stack->used; i++) {
stack->expTreeDarr[i] = expTreeTmp[i];
//free(expTreeTmp[i]);
}
free(expTreeTmp);
}
stack->expTreeDarr[stack->used] = treeNode;
stack->used = stack->used + 1;
}
// Pop tree node pointer from the stack
expTree * popStack(treeStack *stack) {
expTree *stackTmp = getTopStack(stack);
expTree *newNode = (expTree *)malloc(sizeof(expTree));
*newNode = *stackTmp;
stack->used -= 1;
return newNode;
}
// Empty stack of all data (make sure this works)
void clearStack(treeStack *stack) {
for (int i = 0; i < stack->used; i++) {
clearTree(stack->expTreeDarr[i]);
}
free(stack->expTreeDarr);
stack->used = 0;
stack->height = 0;
}
/* File contains all functions necessary for binary tree operations */
// Initialize binary expression tree with specified operator/operand
expTree * initTree(char *val) {
expTree *newTree = (expTree *)malloc(sizeof(expTree));
newTree->val = (char *)malloc(strlen(val) + 1);
strcpy(newTree->val, val);
newTree->left = NULL;
newTree->right = NULL;
return newTree;
}
// Print commands available to the user
void printCommands() {
printf("The commands for this program are:\n\n");
printf("q - to quit the program\n");
printf("? - to list the accepted commands\n");
printf("or any postfix mathematical expression using the operators of *, /, +, -\n");
}
// Return size of binary expression tree
int sizeTree(expTree *treeNode) {
if (treeNode == NULL) {
return 0;
}
else {
return 1 + sizeTree(treeNode->left) + sizeTree(treeNode->right);
}
}
// Construct a postfix binary expression tree from expression string
expTree * parseExpression(char *expString) {
char *expStringCopy = (char *)malloc(strlen(expString) + 1);
expTree *treeNode;
treeStack expStack;
initStack(&expStack);
strcpy(expStringCopy, expString);
char *expStringTok = strtok(expStringCopy, " ");
while (expStringTok != NULL) {
if (*expStringTok == '+' || *expStringTok == '-' ||
*expStringTok == '*' || *expStringTok == '/') {
if (expStack.used < 2) {
return NULL;
}
treeNode = initTree(expStringTok);
treeNode->right = popStack(&expStack);
treeNode->left = popStack(&expStack);
pushStack(&expStack, treeNode);
}
else {
treeNode = initTree(expStringTok);
pushStack(&expStack, treeNode);
}
expStringTok = strtok(NULL, " ");
}
if (expStack.used > 1 || (*(treeNode->val) != '+' && *(treeNode->val) != '-' &&
*(treeNode->val) != '*' && *(treeNode->val) != '/')) {
return NULL;
}
free(expStringCopy);
treeNode = popStack(&expStack);
clearStack(&expStack);
return treeNode;
}
// Clear binary expression tree
void clearTree(expTree *rootNode) {
if (rootNode == NULL) {
return;
}
else {
clearTree(rootNode->left);
clearTree(rootNode->right);
free(rootNode->val);
free(rootNode);
}
}
// Print infix notation of expression
void printInfix(expTree *rootNode) {
if (rootNode == NULL) {
return;
}
else {
if (*(rootNode->val) == '+' || *(rootNode->val) == '-' ||
*(rootNode->val) == '*' || *(rootNode->val) == '/') {
printf("( ");
}
printInfix(rootNode->left);
printf(" %s ", rootNode->val);
printInfix(rootNode->right);
if (*(rootNode->val) == '+' || *(rootNode->val) == '-' ||
*(rootNode->val) == '*' || *(rootNode->val) == '/') {
printf(" )");
}
}
}
// Print prefix notation of expression
void printPrefix(expTree *rootNode) {
if (rootNode == NULL) {
return;
}
else {
printf(" %s ", rootNode->val);
printPrefix(rootNode->left);
printPrefix(rootNode->right);
}
}
// Evaluate the expression tree
int evalExpression(expTree *rootNode) {
char op;
if (*(rootNode->val) == '+') {
return evalExpression(rootNode->left) + evalExpression(rootNode->right);
}
else if (*(rootNode->val) == '-') {
return evalExpression(rootNode->left) - evalExpression(rootNode->right);
}
else if (*(rootNode->val) == '*') {
return evalExpression(rootNode->left) * evalExpression(rootNode->right);
}
else if (*(rootNode->val) == '/') {
return evalExpression(rootNode->left) / evalExpression(rootNode->right);
}
else {
return atoi(rootNode->val);
}
}
int main(int argc, char const *argv[])
{
char input[300];
expTree *expPostfix;
/* set up an infinite loop */
while (1)
{
fgets(input,300,stdin);
/* remove the newline character from the input */
int i = 0;
while (input[i] != '\n' && input[i] != '[=10=]') {
i++;
}
input[i] = '[=10=]';
/* check if user enter q or Q to quit program */
if ( (strcmp (input, "q") == 0) || (strcmp (input, "Q") == 0) )
break;
/* check if user enter ? to see command list */
else if ( strcmp (input, "?") == 0)
printCommands();
/* user enters an expression */
else {
// Parse the expression into a binary expression tree
printf("%s\n", input);
expPostfix = parseExpression(input);
// Discern whether expression is valid
if (expPostfix == NULL) {
printf("Invalid expression. Enter a valid postfix expression \n");
continue;
}
// Print the expression in infix notation
printf("Infix notation: ");
printInfix(expPostfix);
printf("\n");
// Print the expression in prefix notation
printf("Prefix notation: ");
printPrefix(expPostfix);
printf("\n");
// Print the expression in postfix notation
printf("Postfix notation: ");
printf("%s\n", input);
// Evaluate expression and print result
printf("Expression result: %d \n\n", evalExpression(expPostfix));
clearTree(expPostfix);
}
}
printf("\nGoodbye\n");
return 0;
}
基于 运行 Valgrind 和“1 1 -”的输入，这是输出：
==35604==
==35604== HEAP SUMMARY:
==35604== in use at exit: 72 bytes in 3 blocks
==35604== total heap usage: 13 allocs, 10 frees, 2,236 bytes allocated
==35604==
==35604== 24 bytes in 1 blocks are definitely lost in loss record 1 of 2
==35604== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==35604== by 0x10952C: initTree (proj4base_38.c:143)
==35604== by 0x1096CC: parseExpression (proj4base_38.c:194)
==35604== by 0x109B8A: main (proj4base_38.c:323)
==35604==
==35604== 48 bytes in 2 blocks are definitely lost in loss record 2 of 2
==35604== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==35604== by 0x10952C: initTree (proj4base_38.c:143)
==35604== by 0x109719: parseExpression (proj4base_38.c:201)
==35604== by 0x109B8A: main (proj4base_38.c:323)
==35604==
==35604== LEAK SUMMARY:
==35604== definitely lost: 72 bytes in 3 blocks
==35604== indirectly lost: 0 bytes in 0 blocks
==35604== possibly lost: 0 bytes in 0 blocks
==35604== still reachable: 0 bytes in 0 blocks
==35604== suppressed: 0 bytes in 0 blocks
==35604==
==35604== For lists of detected and suppressed errors, rerun with: -s
==35604== ERROR SUMMARY: 2 errors from 2 contexts (suppressed: 0 from 0)
看来罪魁祸首是我的 initTree() 函数。但是，我就是想不通为什么会丢失这段记忆。我希望这不是太多的代码。这是之前的编辑，有人告诉我没有足够的信息可以继续。
泄漏是由popStack引起的，因为函数退出时stackTmp的目标被泄漏：
expTree * popStack(treeStack *stack) {
expTree *stackTmp = getTopStack(stack);
expTree *newNode = (expTree *)malloc(sizeof(expTree));
*newNode = *stackTmp;
stack->used -= 1;
return newNode;
}
鉴于堆栈似乎是树的独占所有者，并且不再有指向它的指针，popStack 可以通过简单地不进行复制来避免泄漏并返回原件：
expTree * popStack(treeStack *stack) {
expTree *topNode = getTopStack(stack);
stack->used -= 1;
return topNode;
}