我正在为一个学校项目编写一些代码。它是一个表达式树，以中缀表示法保存数字和运算符。树结构
这棵树具有以下结构：
typedef struct
{
char the_operator;
struct operand_node_tag *left_operand;
struct operand_node_tag *right_operand;
} operator_node;
typedef struct operand_node_tag
{
enum {operator_type, number_type} tree_node_type;
union
{
operator_node the_operator_node;
int the_number;
};
} tree_node;
我有一个可以动态创建运算符节点的函数：
tree_node *create_expression(char op, tree_node *l, tree_node *r)
{
// Dynamically reserve memory for a tree_node of type operator_type.
tree_node *newTreeNode = malloc(sizeof(tree_node));
if (newTreeNode == NULL)
{ //Return NULL if there is no available memory.
return NULL;
}
// Set the_operator to op, left_operand to l and right_operand to r
newTreeNode->the_operator_node.the_operator = op;
newTreeNode->the_operator_node.left_operand = l;
newTreeNode->the_operator_node.right_operand = r;
newTreeNode->tree_node_type = operator_type;
// and return the tree_node
return newTreeNode;
}
还有一个可以动态创建数字节点的函数：
tree_node *create_number_node(int i)
{
// Dynamically reserve memory for a tree_node of type number_type.
tree_node *newTreeNode = malloc(sizeof(tree_node));
if (newTreeNode == NULL) { //Return NULL if there is no available memory.
return NULL;
}
//Set the node type to number
newTreeNode->tree_node_type = number_type;
// Set the_number to i and return the tree_node
newTreeNode->the_number = i;
// and return the tree_node
return newTreeNode;
}
这些功能对我来说工作正常。释放分配的内存时出现问题。为此，我编写了以下函数：
void free_expression_tree(tree_node **pnode)
{
// Free all dynamically reserved memory and set *pnode to NULL.
if ((*pnode)->the_operator_node.left_operand && (*pnode)->tree_node_type == operator_type)
{
free_expression_tree(&(*pnode)->the_operator_node.left_operand);
(*pnode)->the_operator_node.left_operand = NULL;
}
if ((*pnode)->the_operator_node.right_operand && (*pnode)->tree_node_type == operator_type)
{
free_expression_tree(&(*pnode)->the_operator_node.right_operand);
(*pnode)->the_operator_node.right_operand = NULL;
}
printf("Free: ");
if ((*pnode)->tree_node_type == operator_type)
{
printf("%c, ", (*pnode)->the_operator_node.the_operator);
free(*pnode);
printf("%d, n", (*pnode)->the_operator_node.the_operator);
}
else
{
printf("%d, ", (*pnode)->the_number);
free(*pnode);
printf("%d, n", (*pnode)->the_number);
}
}
它循环遍历给定节点并释放较低级别中的所有节点。此函数在调试器 (GCC( 中似乎工作正常，在控制台中给出以下结果：
Free: 12, 3277136,
Free: 40, 3277136,
Free: 23, 3277136,
Free: 3, 3296384,
Free: -, -18,
Free: /, -18,
Free: 2, -17891602,
Free: *, -18,
Free: +, -18,
我在执行 free(( 函数之前和之后打印数字/运算符。这里似乎工作正常。
现在这是相同的结果，但在这里我实际上是在运行.exe：
Free: 12, 3735888,
Free: 40, 3735888,
Free: 23, 3735888,
Free: 3, 3763520,
Free: -, -,
Free: /, /,
Free: 2, 2,
Free: *, *,
Free: +, +,
我假设这与编译器设置有关，但我对什么一无所知。我已关闭优化。
你们有什么建议吗？
完整代码： 主.c
#include <stdio.h>
#include <stdlib.h>
#include "stack.h"
#include "tree.h"
int main(void)
{
setbuf(stdout, NULL);
tree_node *rootmin = create_expression('-', create_number_node(23), create_number_node(3));
tree_node *rootdelen = create_expression('/', create_number_node(40), rootmin);
tree_node *rootkeer = create_expression('*', rootdelen, create_number_node(2));
tree_node *root = create_expression('+', create_number_node(12), rootkeer);
printf("Infix: ");
print_tree_infix(root);
printf("n");
printf("Postfix: ");
print_tree_postfix(root);
printf("n");
FILE *file = fopen("tree.graphviz", "w");
if (file == NULL)
{
fprintf(stderr, "Error: Can not create file tree.graphviz.");
return -1;
}
create_visual_graph_from_tree(root, file);
printf("Open file tree.graphviz op https://stamm-wilbrandt.de/GraphvizFiddle/#.n");
free_expression_tree(&root);
return 0;
}
树.c：
#include <stdio.h>
#include <stdlib.h>
#include "tree.h"
#include "stack.h"
tree_node *create_number_node(int i)
{
// Dynamically reserve memory for a tree_node of type number_type.
tree_node *newTreeNode = malloc(sizeof(tree_node));
if (newTreeNode == NULL) { //Return NULL if there is no available memory.
return NULL;
}
//Set the node type to number
newTreeNode->tree_node_type = number_type;
// Set the_number to i and return the tree_node
newTreeNode->the_number = i;
// and return the tree_node
return newTreeNode;
}
tree_node *create_expression(char op, tree_node *l, tree_node *r)
{
// Dynamically reserve memory for a tree_node of type operator_type.
tree_node *newTreeNode = malloc(sizeof(tree_node));
if (newTreeNode == NULL)
{ //Return NULL if there is no available memory.
return NULL;
}
// Set the_operator to op, left_operand to l and right_operand to r
newTreeNode->the_operator_node.the_operator = op;
newTreeNode->the_operator_node.left_operand = l;
newTreeNode->the_operator_node.right_operand = r;
newTreeNode->tree_node_type = operator_type;
// and return the tree_node
return newTreeNode;
}
void free_expression_tree(tree_node **pnode)
{
// Free all dynamically reserved memory and set *pnode to NULL.
if ((*pnode)->the_operator_node.left_operand && (*pnode)->tree_node_type == operator_type)
{
free_expression_tree(&(*pnode)->the_operator_node.left_operand);
(*pnode)->the_operator_node.left_operand = NULL;
}
if ((*pnode)->the_operator_node.right_operand && (*pnode)->tree_node_type == operator_type)
{
free_expression_tree(&(*pnode)->the_operator_node.right_operand);
(*pnode)->the_operator_node.right_operand = NULL;
}
printf("Free: ");
if ((*pnode)->tree_node_type == operator_type)
{
printf("%c, ", (*pnode)->the_operator_node.the_operator);
free(*pnode);
printf("%c, n", (*pnode)->the_operator_node.the_operator);
}
else
{
printf("%d, ", (*pnode)->the_number);
free(*pnode);
printf("%d, n", (*pnode)->the_number);
}
}
void print_tree_postfix(const tree_node *node)
{
if (node)
{
print_tree_postfix(node->the_operator_node.left_operand);
print_tree_postfix(node->the_operator_node.right_operand);
if (node->tree_node_type == number_type)
{
printf("%d ", node->the_number);
}
else
{
printf("%c ", node->the_operator_node.the_operator);
}
}
}
void print_tree_infix(const tree_node *node)
{
if (node)
{
if (node->the_operator_node.right_operand)
{
printf("(");
}
print_tree_infix(node->the_operator_node.left_operand);
if (node->tree_node_type == number_type)
{
printf("%d", node->the_number);
}
else
{
printf("%c", node->the_operator_node.the_operator);
}
print_tree_infix(node->the_operator_node.right_operand);
if (node->the_operator_node.left_operand)
{
printf(")");
}
}
}
static void output_edge_to_visual_graph(char source, const tree_node *dest, FILE* file)
{
fprintf(file, " "%c" -> "", source);
switch (dest->tree_node_type)
{
case operator_type:
fprintf(file, "%c", dest->the_operator_node.the_operator);
break;
case number_type:
fprintf(file, "%d", dest->the_number);
break;
}
fprintf(file, ""n");
}
static void output_node_to_visual_graph(const tree_node *node, FILE *file)
{
if (node != NULL && node->tree_node_type == operator_type)
{
const operator_node *op = &(node->the_operator_node);
if (op->left_operand != NULL && op->right_operand != NULL)
{
output_edge_to_visual_graph(op->the_operator, op->left_operand, file);
output_edge_to_visual_graph(op->the_operator, op->right_operand, file);
output_node_to_visual_graph(op->left_operand, file);
output_node_to_visual_graph(op->right_operand, file);
}
}
}
void create_visual_graph_from_tree(const tree_node *root, FILE *file)
{
if (file != NULL)
{
fprintf(file, "digraph G {n");
if (root != NULL) output_node_to_visual_graph(root, file);
fprintf(file, "}n");
}
}
树.h：
#ifndef TREE_H_
#define TREE_H_
typedef struct
{
char the_operator;
struct operand_node_tag *left_operand;
struct operand_node_tag *right_operand;
} operator_node;
typedef struct operand_node_tag
{
enum {operator_type, number_type} tree_node_type;
union
{
operator_node the_operator_node;
int the_number;
};
} tree_node;
tree_node *create_number_node(int i);
tree_node *create_expression(char op, tree_node *l, tree_node *r);
void free_expression_tree(tree_node **pnode);
// frees all dynamically reserved memory and sets *pnode to NULL.
void print_tree_infix(const tree_node *node);
void print_tree_postfix(const tree_node *node);
void create_visual_graph_from_tree(const tree_node *root, FILE *file);
#endif /* TREE_H_ */
你有
free(*pnode);
紧跟着例如
printf("%d, n", (*pnode)->the_operator_node.the_operator);
在第二条语句中，您取消引用刚刚传递给free的指针，因此指针指向的内存不再归您的程序所有，任何取消引用指针的尝试都将导致未定义的行为。
一旦内存被释放，你就无法使用内存。
对此的解决方案是在调用free之后不要进行第二次printf调用，特别是因为它只会打印第一个printf调用打印的内容。