c - 重新分配(): getting an invalid pointer error in C

Question

我意识到这个问题在这里已经被打死了，但我完全不知道为什么这个错误仍然发生在我身上。

请记住，这不是作业或任何东西，因此您在我的实现中看到的任何逻辑缺陷/错误都是由于缺乏编程经验造成的；我没有，这是我第一次尝试实现典型的数据结构。我目前正在尝试自学编程，所以请理解我是否在任何地方犯了任何明显的错误。

就是说，这里是二叉搜索树实现的源代码(还有一些我扔进去的其他垃圾东西；我试着让 cin 像 C++ 的 cin 一样):

#include <stdlib.h>
#include <stdio.h>
#include <ctype.h>
#include <math.h>
#include <limits.h>
#include <stdint.h>

#define INIT_BUF_SIZE 1
#define INIT_STACK_SIZE 1
#define ERROR_MSG "The program could not allocate enough memory :[\n"

typedef enum {false, true} bool;

typedef struct Node {
    int value;
    int quantity;
    struct Node *parent;
    struct Node *left;
    struct Node *right;
} Node;

typedef struct Node_Stack {
    unsigned int size;
    unsigned int max_size;
    Node **s;
} Node_Stack;

typedef struct Count_Stack {
    unsigned int size;
    unsigned int max_size;
    unsigned int *s;
} Count_Stack;

Node *root = NULL;
Node_Stack stack;
Count_Stack c_stack;


/********************* Stack Operations *********************/
bool init_c_stack (void) {
    unsigned int *temp = calloc(INIT_STACK_SIZE, sizeof(int));
    
    if (temp == NULL) {return false;}
    
    c_stack.s = temp;
    c_stack.size = 0;
    c_stack.max_size = INIT_STACK_SIZE;
    
    return true;
}

void delete_c_stack (void) {
    c_stack.s = NULL;
    c_stack.size = 0;
    c_stack.max_size = 0;
    free(c_stack.s);
}

bool init_stack (void) {
    Node **temp = calloc(INIT_STACK_SIZE, sizeof(Node *));
    
    if (temp == NULL) {return false;}
    
    stack.s = temp;
    stack.size = 0;
    stack.max_size = INIT_STACK_SIZE;
    
    return true;
}

void delete_stack (void) {
    stack.s = NULL;
    stack.size = 0;
    stack.max_size = 0;
    free(stack.s);
}

bool init_stacks (void) {return init_stack() && init_c_stack();}

void delete_stacks (void) {
    delete_c_stack();
    delete_stack();
}

bool update_c_stack (void) {
    if (c_stack.s == NULL) {return false;}
    
    unsigned int *t = realloc(c_stack.s,
                              sizeof(*c_stack.s)*(c_stack.max_size + 1));
    
    if (t == NULL) {return false;}
    
    c_stack.s = t;
    c_stack.max_size++;
    
    return true;
}

bool update_stack (void) {
    if (stack.s == NULL) {return false;}
    
    Node **t = realloc(stack.s, sizeof(*stack.s)*(stack.max_size + 1));
    
    if (t == NULL) {return false;}
    
    printf("stack.max_size before = %u\n", stack.max_size);
    printf("reallocated to %d bytes\n",
           sizeof(Node *)*(stack.max_size + 1));
    
    stack.s = t;
    stack.max_size++;
    printf("stack.max_size after = %u\n", stack.max_size);
    
    return true;
}

bool push_count (unsigned int i) {
    if (c_stack.s == NULL) {return false;}
    
    if (c_stack.size < c_stack.max_size || update_c_stack()) {
        c_stack.s[c_stack.size++] = i;
        return true;
    }
    return false;
}

bool push (Node *i) {
    if (stack.s == NULL) {return false;}
    
    if (stack.size < stack.max_size || update_stack()) {
        stack.s[stack.size++] = i;
        return true;
    }
    return false;
}

/******************* End of Stack Operations *******************/

bool add_node (int x) {
    if (get_num_levels(root) == UINT_MAX) {
            printf("Failed to add %d to tree\n", x);
            return false;
    }

    Node *f = find(root, x), *t = (Node *)calloc(1, sizeof(Node)), *p;

    if (root == NULL) {
        t->value = x;
        t->quantity = 1;
        t->parent = NULL;
        t->left = NULL;
        t->right = NULL;
        root = t;
    }
    else if (f == NULL) { // x doesn't exist in tree
        f = root;
        p = f->parent;

        while (f != NULL) {
            p = f;
            if (x < f->value) {f = f->left;}
            else if (x > f->value) {f = f->right;}
        }
        
        t->value = x;
        t->quantity = 1;
        t->parent = p;
        t->left = NULL;
        t->right = NULL;
        
        if (x < p->value) {p->left = t;}
        else if (x > p->value) {p->right = t;}
        else {f->quantity++;} // x already exists in tree
    }

    printf("\n" TREE_SEPERATOR "\n");
    printf("\nAdded node containing %d\n", x);
    print_tree_formatted();
    printf("\nNow %d nodes in the tree.\n", get_num_nodes(root));
    printf("\nNow %d levels in the tree.\n", get_num_levels(root));

    return true;
}

bool remove_node (int x) {
    Node *f = find(root, x);

    if (f != NULL) {
        if (f->quantity > 1) {f->quantity--;}
        else {replace_node(f); free(f);}

        printf("\n" TREE_SEPERATOR "\n");
        printf("\nRemoved node containing %d\n", x);
        print_tree_formatted();
        printf("\nNow %d nodes in the tree.\n", get_num_nodes(root));
        printf("\nNow %d levels in the tree.\n", get_num_levels(root));
        return true;
    }
    
    return false;
}

/*************************************************************************
 * Function Name:                                                        *
 *     str_split                                                         *
 * Purpose:                                                              *
 *     The function below takes a single string and breaks it up into a  *
 *     set of constituent sub-strings, based on the delimiter that is    *
 *     passed in to break the string by.                                 *
 * Parameters:                                                           *
 *   - s       The string to be split                                    *
 *   - len     The length of the string                                  *
 *   - c       The size of the returned char * array                     *
 *   - delim   The delimiter by which the string s is to be broken up by *
 * Return Value:                                                         *
 *     char ** A pointer to an array of c number of strings, or NULL on  *
 *             failure to allocate enough space                          *
 *************************************************************************/
char **str_split (char *s, unsigned int len, unsigned int c, const char delim) {
    char **result;
    unsigned int i, j, k = 0, l;
    
    if (s == NULL || len == 0) {return NULL;}
    
    /* Allocate memory for c number of strings/char pointers */
    result = calloc(c + 1, sizeof(char *));
    
    if (result != NULL) {
        for (i = 0; i < c + 1; i++) {
            /* Allocate space for the actual chars for each string */
            result[i] = calloc(len, sizeof(char));
            if (result[i] == NULL) {return NULL;}
        }
        
        /***************************************************************
         * i holds index of advancing pointer                          *
         * j holds index of following pointer                          *
         * k holds index of string in returning array of char pointers *
         * l holds index of char in string                             *
         ***************************************************************
         * Loop over and copy contents of s into the each index of     *
         * result                                                      *
         ***************************************************************/
        for (i = 0, j = 0; i < len; i++) {
            l = 0;
            if (s[i] == delim) {
                for (; j < i; j++) {result[k][l++] = s[j];}
                k++;
                j = i + 1;
            }
        }
        for (; j < i; j++) {result[k][l++] = s[j];}
    }
    
    return result;
}

/*************************************************************************
 * Function Name:                                                        *
 *     cin                                                               *
 * Purpose:                                                              *
 *     The function below allows for "continuous" user input, based on   *
 *     how much the user has already entered, by dynamically allocating  *
 *     more memory whenever the input buffer is maxed out.               *
 * Parameters:                                                           *
 *   - cur_size       The initial allocation size for the input buffer   *
 * Return Value:                                                         *
 *     char *         A string/pointer to an array of characters or NULL *
 *                    if allocation failed                               *
 *************************************************************************/
char *cin (unsigned int cur_size) {
    char *input = (char *)malloc(cur_size);
    int i = 0, c = EOF;
    
    if (input != NULL) {
        // cook keyboard input until NL or EOF
        while ((c = getchar()) != '\n' && c != EOF) {
            if ((char)c == 8 || (char)c == 127) {
                printf("\b \b\b \b\b \b");
                fflush(stdout);
                i = (i > 0) ? i - 1 : i;
            }
            else {
                input[i++] = (char)c;
                if (i == cur_size) {
                    /* Attempt to double the current size of the buffer */
                    cur_size *= 2;
                    input = realloc(input, cur_size);
                    if (input == NULL) {
                        printf("Unable to allocate enough memory for input\n");
                        break;
                    }
                }
            }
        }
        
        // null-terminate user input
        input[i] = '\0';
    }
    
    return input;
}

...

int main (void) {    
    char *input, **s, t, delim = ' ';
    unsigned int len, i, count, result;
    bool valid;
    
    /* Allocate space for both stacks */
    init_stacks(); // DO NOT MOVE OR DUPLICATE CALL
    
    while (true) {
        /* Continuously grab null-terminated user input string */
        input = cin(INIT_BUF_SIZE);
        
        if (input != NULL) {
            len = string_length(input);
            
            /* Get the number of times the char delim appears in input */
            count = num_in_string(input, delim);
            
            /***********************************************************
             * First word in user input should either be:              *
             *   - "add"                                               *
             *   - "remove"                                            *
             *   - "print"                                             *
             *   - Any of the exit commands ("q", "quit", or "exit").  *
             ***********************************************************/
            t = input[0];
            
            /* Exit loop if first token is an exit command */
            if (user_exit(input)) {break;}
            
            /*******************************************************
             * Only process user input if there's at least 2 words *
             *   Eg: add 1      <-- Valid                          *
             *       add        <-- Invalid                        *
             *       remove 1   <-- Valid                          *
             *       foobar     <-- Invalid                        *
             *******************************************************/
            if (count > 0) {
                /* Get the user input split up by spaces */
                s = str_split(input, len, ++count, delim);
                
                if (s != NULL) {
                    /*******************************************
                     * Look at each token entered by the user, *
                     * except the first one                    *
                     *******************************************/
                    for (i = 1; i < count; i++) {
                        /***********************************************
                         * Assuming the token is a number, convert the *
                         * token to an integer                         *
                         ***********************************************/
                        result = string_to_int(s[i], &valid);
                        
                        if (same_string(s[0], "print")) {
                            if (same_string(s[1], "stack")) {
                                printf("size = %u\n", stack.size);
                                printf("max_size = %u\n", stack.max_size);
                            }
                            else {printf("%s\n", s[i]);}
                            fflush(stdout);
                        }
                        else if (valid) {
                            if (same_string(s[0], "add")) {
                                add_node(result);
                            }
                            else if (same_string(s[0], "remove")) {
                                remove_node(result);
                            }
                        }
                    }
                    
                    /* Free up memory allocated for split user input */
                    for (i = 0; i < count; i++) {free(s[i]);} // DO NOT MOVE
                    free(s); // DO NOT MOVE
                }
                else {printf(ERROR_MSG);} // couldn't allocate heap space
            }
            
            /* Free up memory allocated for cin */
            free(input); // DO NOT MOVE
        }
    }
    
    /* Free up memory allocated for both stacks */
    delete_stacks(); // DO NOT MOVE
    
    return 0;
}

因此，当我运行它时，程序运行良好，因为我添加了以下树(按顺序): 15, 7, 23, 3, 11, 19, 27 .

然后，当我将数字 5 添加到树中时，程序因名义错误而崩溃。我试过使用 gdb(和 lldb)进行调试，但我认为这不是很有效，即使打开了 -g 标志也是如此。

这对我来说没有意义，因为 update_stack 和 update_count_stack 中对 realloc 的调用不会失败 prior 添加数字 5。

我也确实意识到将动态分配的内存块的大小一遍又一遍地增加 1 不是典型的或好的做法，因为它效率低下，但我只是想知道为什么 这发生在这里，以及我如何能够修复它 - 我觉得我只是遗漏了一些明显的东西，并且正在为一些小事拉扯我的头发!

编辑

感谢大家的反馈。

我昨天不小心把我的源文件复制粘贴到这里，所以请原谅我现在必须运行。从那以后，我尝试尽量减少发布的代码以仅显示相关函数，其中包括调用 malloc、realloc 或 free 的函数。我还尝试在代码中添加一些注释以帮助更好地理解它。

Answer 1

回答其中一个 OP 问题；

增加分配时，

在每次增量时，增量 I.E. 的数量加倍。 1, 2, 4, 9 ...

记录当前可用的最大值和实际使用的电流，

只有在没有可用空间时才调用 `realloc()