代码之家 › 专栏 › 技术社区 › Nurana

c堆栈(使用动态数组)realloc内存泄漏问题

realloc dynamic-memory-allocation stack data-structures c

Nurana · 技术社区 · 2 年前

#include <stdio.h>
#include <stdlib.h>

int LENGTH = 1;
int TOP = -1;

void push(char**, char);
char pop(char*);
char peek(char*);
int isEmpty();
int isFull();

void convertToRPN(char*, char*, char*);
int isOperator(char);
int getPrecedence(char);


int main(void) {
    char* stack = (char*) malloc(sizeof(char) * LENGTH);
    if (!stack) {
        printf("Memory allocation failed./n");
        exit(1);
    }

    char expression[100];
    printf("Enter the mathematical expression: ");
    scanf("%s", expression);

    char rpn[100];
    convertToRPN(expression, stack, rpn);

    printf("The rpn: %s\n", rpn);

    free(stack);

    return 0;
}


int isOperator(char c) {
    return (c == '+' || c == '-' || c == '*' || c == '/');
}


int getPrecedence(char c) {
    if (c == '+' || c == '-')
        return 1;
    if (c == '*' || c == '/')
        return 2;
    return 0; 
}


void convertToRPN(char *expression, char* stack, char* rpn) {
    
    int j = 0;
    for (int i = 0; expression[i] != '\0'; i++) {
        if (expression[i] >= '0' && expression[i] <= '9') {
            rpn[j] = expression[i];
            j++;
        } else if (isOperator(expression[i])) {
            while (!isEmpty() && peek(stack) != '(' && getPrecedence(peek(stack)) >= getPrecedence(expression[i])) {
                rpn[j] = pop(stack);
                j++;
            }
            push(&stack, expression[i]);
        } else if (expression[i] == '(') {
            push(&stack, expression[i]);
        } else if (expression[i] == ')') {
            while (!isEmpty() && peek(stack) != '(') {
                rpn[j] = pop(stack);
                j++;
            }
            pop(stack);
        } else {
            printf("Unsupported character.\n");
            exit(2);
        }
    }

    while (!isEmpty()) {
        rpn[j] = pop(stack);
        j++;
    }

    rpn[j] = '\0';
}


void push(char **stack, char c) {
    if (isFull()) {
        *stack = (char *)realloc(*stack, sizeof(char) * (LENGTH + 1));
        if (!*stack) {
            printf("Memory reallocation failed.\n");
            exit(5);
        }
        LENGTH++;
    }
    TOP++;
    (*stack)[TOP] = c;
}


char pop(char *stack) {
    if (isEmpty()) {
        printf("POP: the stack is empty.\n");
        exit(3);
    } else {
        char item = stack[TOP];
        TOP--;
        return item;
    }
}


char peek(char *stack) {
    if (isEmpty()) {
        printf("PEEK: the stack is empty.\n");
        exit(4);
    }
    return stack[TOP];
}


int isEmpty() {
    return TOP == -1;
}


int isFull() {
    return TOP == LENGTH - 1;
}

此代码执行RPN(反向波兰符号)转换,但在1个块中给出明确的丢失。根据valgrind的说法,该代码存在内存泄漏问题。这个消息很神秘,但我猜它在realloc()中。也许有助于传达以下信息:

输入数学表达式:5+9+2 1. rpn:59+21 +

free()/delete/delete[]/realloc()无效在0x484810F:空闲通过0x1092FE:主(练习1_2.c:34) 地址0x4a78040在大小为1的块内为0字节在0x484ABC0:realloc 通过0x109616:推送(exer1_2.c:92) 通过0x1094BB:convertToRPN 通过0x1092D4:main 块分配于在0x4845828:malloc 通过0x109256:main

堆摘要: 在出口处使用:1个块中有2个字节堆使用总量:4个分配,4个释放,2051个字节已分配

泄漏总结: 肯定丢失:1个块中有2个字节间接丢失:0个块中有0个字节可能丢失:0个块中有0个字节仍然可访问:0个块中有0个字节已抑制:0个块中有0个字节

错误摘要:1个上下文中的1个错误(已抑制:0中的0)

总的来说,我想问题出在我的堆栈实现上。

1 回复 | 直到 2 年前

Vlad from Moscow 2 年前

程序中有一个错误。指针 stack 传递给函数 convertToRPN 按价值

void convertToRPN(char*, char*, char*);

//...

convertToRPN(expression, stack, rpn);

因此,该函数处理原始指针值的副本。原始指针保持不变。因此,指针具有无效值,并且此调用 free 在里面 main

free(stack);

不会释放在函数执行期间分配的内存 转换为RPN 。

您至少应该通过指向函数的指针来引用该函数来传递指针

void convertToRPN(char*, char**, char*);

//...

convertToRPN(expression, &stack, rpn);

尽管如果堆栈的内存都没有分配到 主要的 。函数中使用堆栈 转换为RPN 其中应该分配和释放内存。

最好声明一个结构Stack,例如

struct Stack
{
    size_t top;
    size_t size;  
    char *mem;
};

并使用该结构的一个对象而不是几个单独的变量。使用全局变量是个非常糟糕的主意

int LENGTH = 1;
int TOP = -1;

我建议你重新设计代码。