无法释放函数中的内存
Cannot free memory in a function
我正在编写一个代码，其中我从文本文件中读取一些图表以便稍后处理。我有一个函数将图形写入内存，第二个函数使用第一个函数然后对该图进行操作。问题是我在第一个函数中分配了一些内存，但我不知道应该在哪里释放它，因为在第一个函数中释放它会导致程序崩溃，而在第二个函数中编译器说没有这样的结构。
struct Graph* createGraph(struct edge edges[], int wxk, int l)
{
// allocate memory for the graph data structure
//struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
struct Graph* graph = malloc(sizeof *graph);
graph->head = malloc( l * sizeof *(graph->head) );
// initialize head pointer for all vertices
for ( int i = 0; i < wxk; i++ ) {
graph->head[i] = NULL;
}
// add edges to the directed graph one by one
for ( int i = 0; i < l; i++ )
{
// get the source and destination vertex
int src = edges[i].src;
int dest = edges[i].dest;
double weight = edges[i].weight;
// allocate new node of adjacency list from `src` to `dest`
struct node* newNode = malloc(sizeof *(newNode) );
struct node* newNode2 = malloc( sizeof *(newNode2));
newNode->dest = dest;
newNode->weight = weight;
newNode->next = NULL;
if( graph->head[src] == NULL ) {
graph->head[src] = newNode;
} else {
for( newNode2 = graph->head[src]; newNode2->next != NULL; newNode2 = newNode2->next )
;
newNode2->next = newNode;
}
struct node* newNode3 = malloc( sizeof *(newNode3) );
struct node* newNode4 = malloc( sizeof *(newNode4) );
newNode3->dest = src;
newNode3->weight = weight;
newNode3->next = NULL;
if( graph->head[dest] == NULL ) {
graph->head[dest] = newNode3;
} else {
for( newNode4 = graph->head[dest]; newNode4->next != NULL; newNode4 = newNode4->next )
;
newNode4->next = newNode3;
}
}
return graph;
}
这是第一个函数代码，其中我为newNode、newNode2、newNode3和newNode4分配了内存。当我在此函数结束时释放此内存时，程序稍后会崩溃。
void check_graph( char *plik)
{
FILE *in = fopen( plik, "r");
struct edge *edges = readfromfile(in);
int l = getl();
int wxk = getwxk();
struct Graph *graph = createGraph( edges, wxk, l);
struct FIFO queue;
short int *visited = malloc ( wxk * sizeof (int));
for( int i = 0; i < wxk; i++)
{
visited[i] = 0;
}
queue.vertices = (int *) malloc( wxk * sizeof(int) );
queue.front = 0;
queue.end = 0;
add_to_queue( &queue, 0);
visited[0] = 1;
while( queue.front != queue.end)
{
int current_vertex = del_from_queue( &queue);
struct node *tmp = graph->head[current_vertex];
while( tmp != NULL)
{
int adjVertex = tmp->dest;
if( visited[adjVertex] == 0)
{
visited[adjVertex] = 1;
add_to_queue( &queue, adjVertex);
}
tmp = tmp->next;
}
}
free(queue.vertices); // czyszczenie pamięci
free(visited);
free(edges);
for( int i = 0; i < wxk; i++ )
free( graph->head[i] );
free(graph->head);
free(graph);
}
如果我在这里尝试释放以前的内存，编译器会说变量名未声明
简答
释放内存应该在销毁特定对象的单独函数中处理，一个用于（邻接）列表，一个用于图（调用邻接列表销毁函数）。邻接表析构函数应该遍历一个列表，在访问它们时释放节点（注意节点是使用析构函数自己的局部变量释放的，而不是 newNode<i>I</i> 图构造函数中的变量）。图析构函数将从 check_graph 调用。请注意，这与代码中创建的处理方式相似。
更长的答案
如果遵循一些基本的设计原则，该程序将大有裨益。特别是，将功能分解为更基本的操作，每个操作执行单个任务（类似于 OOP 的单一职责原则）。在考虑任务的 sub-tasks 时，它们应该处于同一级别和同一域（稍后会详细介绍）。此外，功能不应过长。只要重复代码在概念上是单个任务，就可以将其抽象为单独的函数 (Don't Repeat Yourself)。尽管该程序可能未明确 object-oriented，但可以有效地应用一些 OO 约定。变量名称应该是描述性的。
开始考虑函数名。该示例包含 createGraph 和 check_graph，混合了命名约定。这本质上并不是错误的，但是只有当每个约定在做不同的事情并且位于程序的不同部分时，才应该混合命名约定。以 OO 方式命名方法的一个 C 约定是对 class 名称和 camelCase for method names (as is done in C++), and connect the two with an underscore (basically, snake case) 使用 DromedaryCase（例如 ClassName_methodName）。对此进行扩展，下划线表示范围缩小，因此嵌套的 class 方法将被命名为：Outer_Inner_methodName。替代方案包括对 class 名称使用驼峰式命名法，或对所有名称使用蛇形命名法，或使用蛇形命名法但使用双下划线表示范围（例如 outer_class__inner_class__method_name）。 “私有”方法可以用前导下划线表示。
check_graph 函数执行以下 sub-tasks:
- 打开文件
- 导致从文件中读取边
- 导致创建一个 Graph 对象
- 为队列的成员字段分配 space (
queue.vertices)
- 遍历图breadth-first
- 检查队列成员以确定队列何时为空
- 销毁队列成员、边和图
这混合了不同级别的任务（例如导致创建图形对象（发生在不同的函数中）但销毁对象本身；创建队列的一部分）和域（例如文件 I/O、内存管理和图形算法），导致多重责任。从文件中读取对象应该由负责桥接 I/O 和对象创建的组件处理。销毁图形对象应该由一个单独的函数处理，对应于 createGraph（或 Graph_create，如果您使用上面的约定）。这尤其应该解决所讨论的问题。队列操作应该外包给队列函数，encapsulating 操作和数据。
check_graph 中的大部分行都与图的 breadth-first 遍历有关。这可能是实现 BFS 算法的函数的基础，在每个顶点被访问时进行回调。 check_graph 然后会调用 BFS 函数。
重构版本草图：
typedef void (*Graph_visitor_t)(Graph_t *graph, int iVertex, void *additional);
/**
* Breadth-first traversal of a graph
*
* visit: a callback, invoked for each vertex when visited
* pAdditional: additional data passed along to the `visit` function
*/
void Graph_bfs(Graph_t *graph, Graph_visitor_t visit, void *pAdditional) {
// TODO: detect & handle memory errors
bool *visited = calloc(sizeof(*visited), graph->nVertices);
IntQueue_t *queue = IntQueue_create(graph->nVertices);
visit(graph, 0, pAdditional);
visited[0] = 1;
IntQueue_push(queue, 0);
while (! IntQueue_empty(queue)) {
int current_vertex = IntQueue_pop(queue);
/* much the same as the original `check_graph` (only
* add a call to `visit`)
*/
// ...
}
IntQueue_destroy(queue);
free(visited);
}
void _Graph_countVisited(Graph_t* graph, int iVertex, int *pnVisited) {
++(*pnVisited);
}
// Demonstrates how to use Graph_bfs (check_graph woudl be similar).
void Graph_isConnected(Graph_t *graph) {
int nVisited = 0;
Graph_bfs(graph, &_Graph_countVisited, &nVisited);
return nVisited == graph->nVertices;
}
createGraph 执行以下 sub-tasks:
- 分配图形对象和成员
- 分配邻接表节点
- 遍历邻接表
- 将节点添加到邻接列表
同样，其中一些任务处于不同级别，应该分包出去（例如邻接表操作）。在循环内操作邻接表的代码也是重复的，非常适合移至另一个函数。
许多变量名称（例如 l、wxk、newNode3）的描述性不强，导致了一些错误。例如，在 createGraph 中，graph->head 被分配来保存 l 条目，但是 wxk 条目在初始化时被访问（在这种情况下，更好的解决方法是使用 calloc 而不是手动将所有条目初始化为 NULL)。如果这些变量的名称更具描述性，例如nVertices 和 nEdges（我猜是出于什么目的），错误会更加明显，并且很可能一开始就不会发生。
void _Graph_addAdjacency(Graph_t *graph, int from, int to, double weight) {
Node_t *newNode = List_Node_create(to, weight);
if (graph->head[from] == NULL ) {
graph->head[from] = newSrcNode;
} else {
List_append(graph->head[from], newSrcNode);
}
}
void _Graph_addEdge(Graph_t *graph, Edge_t *edge) {
_Graph_addAdjacency(graph, edges[i].src, edges[i].dest, edges[i].weight);
_Graph_addAdjacency(graph, edges[i].dest, edges[i].src, edges[i].weight);
}
Graph_t* Graph_create(Edge_t edges[], int nEdges, int nVertices) {
//// allocation
// TODO: detect & handle memory errors
Graph_t *graph = malloc(sizeof *graph);
graph->head = calloc(sizeof *(graph->head), nVertices);
graph->nVertices = nVertices;
//// initialization
// add edges to the directed graph one by one
for (int i = 0; i < nEdges; i++) {
// TODO: add error detection
_Graph_addEdge(graph, edges[i]);
}
return graph;
}
示例的最后是从文件中读取图形的函数 (Graph_readFromPath) 并将它们全部绑定在一起（在本示例中为 main，尽管在较大的程序中它不会是主要功能）。
Graph_t* Graph_readFromPath(const char *fName) {
FILE *in = fopen(fName, "r");
int nVertices = Count_readFromFile(in);
int nEdges = Count_readFromFile(in);
Edge_t *edges = Edges_readFromFile(in, nEdges);
fclose(in);
Graph_t* graph = Graph_create(Edge_t edges[], nEdges, nVertices);
free(edges);
return graph;
}
int main(int argc, char **argv) {
if (argc < 2) {
fprintf(stderr, "No input file given.");
return 1;
}
const char *fName = argv[1];
if (access(fname, R_OK)) {
fprintf(stderr, "Error reading input file '%s': %s", fName, strerror(errno));
return 1;
}
Graph_t *graph = Graph_readFromFile(fName);
if (! Graph_isConnected(graph)) {
// ...
}
Graph_destroy(graph);
return 0;
}
我正在编写一个代码，其中我从文本文件中读取一些图表以便稍后处理。我有一个函数将图形写入内存，第二个函数使用第一个函数然后对该图进行操作。问题是我在第一个函数中分配了一些内存，但我不知道应该在哪里释放它，因为在第一个函数中释放它会导致程序崩溃，而在第二个函数中编译器说没有这样的结构。
struct Graph* createGraph(struct edge edges[], int wxk, int l)
{
// allocate memory for the graph data structure
//struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
struct Graph* graph = malloc(sizeof *graph);
graph->head = malloc( l * sizeof *(graph->head) );
// initialize head pointer for all vertices
for ( int i = 0; i < wxk; i++ ) {
graph->head[i] = NULL;
}
// add edges to the directed graph one by one
for ( int i = 0; i < l; i++ )
{
// get the source and destination vertex
int src = edges[i].src;
int dest = edges[i].dest;
double weight = edges[i].weight;
// allocate new node of adjacency list from `src` to `dest`
struct node* newNode = malloc(sizeof *(newNode) );
struct node* newNode2 = malloc( sizeof *(newNode2));
newNode->dest = dest;
newNode->weight = weight;
newNode->next = NULL;
if( graph->head[src] == NULL ) {
graph->head[src] = newNode;
} else {
for( newNode2 = graph->head[src]; newNode2->next != NULL; newNode2 = newNode2->next )
;
newNode2->next = newNode;
}
struct node* newNode3 = malloc( sizeof *(newNode3) );
struct node* newNode4 = malloc( sizeof *(newNode4) );
newNode3->dest = src;
newNode3->weight = weight;
newNode3->next = NULL;
if( graph->head[dest] == NULL ) {
graph->head[dest] = newNode3;
} else {
for( newNode4 = graph->head[dest]; newNode4->next != NULL; newNode4 = newNode4->next )
;
newNode4->next = newNode3;
}
}
return graph;
}
这是第一个函数代码，其中我为newNode、newNode2、newNode3和newNode4分配了内存。当我在此函数结束时释放此内存时，程序稍后会崩溃。
void check_graph( char *plik)
{
FILE *in = fopen( plik, "r");
struct edge *edges = readfromfile(in);
int l = getl();
int wxk = getwxk();
struct Graph *graph = createGraph( edges, wxk, l);
struct FIFO queue;
short int *visited = malloc ( wxk * sizeof (int));
for( int i = 0; i < wxk; i++)
{
visited[i] = 0;
}
queue.vertices = (int *) malloc( wxk * sizeof(int) );
queue.front = 0;
queue.end = 0;
add_to_queue( &queue, 0);
visited[0] = 1;
while( queue.front != queue.end)
{
int current_vertex = del_from_queue( &queue);
struct node *tmp = graph->head[current_vertex];
while( tmp != NULL)
{
int adjVertex = tmp->dest;
if( visited[adjVertex] == 0)
{
visited[adjVertex] = 1;
add_to_queue( &queue, adjVertex);
}
tmp = tmp->next;
}
}
free(queue.vertices); // czyszczenie pamięci
free(visited);
free(edges);
for( int i = 0; i < wxk; i++ )
free( graph->head[i] );
free(graph->head);
free(graph);
}
如果我在这里尝试释放以前的内存，编译器会说变量名未声明
简答
释放内存应该在销毁特定对象的单独函数中处理，一个用于（邻接）列表，一个用于图（调用邻接列表销毁函数）。邻接表析构函数应该遍历一个列表，在访问它们时释放节点（注意节点是使用析构函数自己的局部变量释放的，而不是 newNode<i>I</i> 图构造函数中的变量）。图析构函数将从 check_graph 调用。请注意，这与代码中创建的处理方式相似。
更长的答案
如果遵循一些基本的设计原则，该程序将大有裨益。特别是，将功能分解为更基本的操作，每个操作执行单个任务（类似于 OOP 的单一职责原则）。在考虑任务的 sub-tasks 时，它们应该处于同一级别和同一域（稍后会详细介绍）。此外，功能不应过长。只要重复代码在概念上是单个任务，就可以将其抽象为单独的函数 (Don't Repeat Yourself)。尽管该程序可能未明确 object-oriented，但可以有效地应用一些 OO 约定。变量名称应该是描述性的。
开始考虑函数名。该示例包含 createGraph 和 check_graph，混合了命名约定。这本质上并不是错误的，但是只有当每个约定在做不同的事情并且位于程序的不同部分时，才应该混合命名约定。以 OO 方式命名方法的一个 C 约定是对 class 名称和 camelCase for method names (as is done in C++), and connect the two with an underscore (basically, snake case) 使用 DromedaryCase（例如 ClassName_methodName）。对此进行扩展，下划线表示范围缩小，因此嵌套的 class 方法将被命名为：Outer_Inner_methodName。替代方案包括对 class 名称使用驼峰式命名法，或对所有名称使用蛇形命名法，或使用蛇形命名法但使用双下划线表示范围（例如 outer_class__inner_class__method_name）。 “私有”方法可以用前导下划线表示。
check_graph 函数执行以下 sub-tasks:
- 打开文件
- 导致从文件中读取边
- 导致创建一个 Graph 对象
- 为队列的成员字段分配 space (
queue.vertices) - 遍历图breadth-first
- 检查队列成员以确定队列何时为空
- 销毁队列成员、边和图
这混合了不同级别的任务（例如导致创建图形对象（发生在不同的函数中）但销毁对象本身；创建队列的一部分）和域（例如文件 I/O、内存管理和图形算法），导致多重责任。从文件中读取对象应该由负责桥接 I/O 和对象创建的组件处理。销毁图形对象应该由一个单独的函数处理，对应于 createGraph（或 Graph_create，如果您使用上面的约定）。这尤其应该解决所讨论的问题。队列操作应该外包给队列函数，encapsulating 操作和数据。
check_graph 中的大部分行都与图的 breadth-first 遍历有关。这可能是实现 BFS 算法的函数的基础，在每个顶点被访问时进行回调。 check_graph 然后会调用 BFS 函数。
重构版本草图：
typedef void (*Graph_visitor_t)(Graph_t *graph, int iVertex, void *additional);
/**
* Breadth-first traversal of a graph
*
* visit: a callback, invoked for each vertex when visited
* pAdditional: additional data passed along to the `visit` function
*/
void Graph_bfs(Graph_t *graph, Graph_visitor_t visit, void *pAdditional) {
// TODO: detect & handle memory errors
bool *visited = calloc(sizeof(*visited), graph->nVertices);
IntQueue_t *queue = IntQueue_create(graph->nVertices);
visit(graph, 0, pAdditional);
visited[0] = 1;
IntQueue_push(queue, 0);
while (! IntQueue_empty(queue)) {
int current_vertex = IntQueue_pop(queue);
/* much the same as the original `check_graph` (only
* add a call to `visit`)
*/
// ...
}
IntQueue_destroy(queue);
free(visited);
}
void _Graph_countVisited(Graph_t* graph, int iVertex, int *pnVisited) {
++(*pnVisited);
}
// Demonstrates how to use Graph_bfs (check_graph woudl be similar).
void Graph_isConnected(Graph_t *graph) {
int nVisited = 0;
Graph_bfs(graph, &_Graph_countVisited, &nVisited);
return nVisited == graph->nVertices;
}
createGraph 执行以下 sub-tasks:
- 分配图形对象和成员
- 分配邻接表节点
- 遍历邻接表
- 将节点添加到邻接列表
同样，其中一些任务处于不同级别，应该分包出去（例如邻接表操作）。在循环内操作邻接表的代码也是重复的，非常适合移至另一个函数。
许多变量名称（例如 l、wxk、newNode3）的描述性不强，导致了一些错误。例如，在 createGraph 中，graph->head 被分配来保存 l 条目，但是 wxk 条目在初始化时被访问（在这种情况下，更好的解决方法是使用 calloc 而不是手动将所有条目初始化为 NULL)。如果这些变量的名称更具描述性，例如nVertices 和 nEdges（我猜是出于什么目的），错误会更加明显，并且很可能一开始就不会发生。
void _Graph_addAdjacency(Graph_t *graph, int from, int to, double weight) {
Node_t *newNode = List_Node_create(to, weight);
if (graph->head[from] == NULL ) {
graph->head[from] = newSrcNode;
} else {
List_append(graph->head[from], newSrcNode);
}
}
void _Graph_addEdge(Graph_t *graph, Edge_t *edge) {
_Graph_addAdjacency(graph, edges[i].src, edges[i].dest, edges[i].weight);
_Graph_addAdjacency(graph, edges[i].dest, edges[i].src, edges[i].weight);
}
Graph_t* Graph_create(Edge_t edges[], int nEdges, int nVertices) {
//// allocation
// TODO: detect & handle memory errors
Graph_t *graph = malloc(sizeof *graph);
graph->head = calloc(sizeof *(graph->head), nVertices);
graph->nVertices = nVertices;
//// initialization
// add edges to the directed graph one by one
for (int i = 0; i < nEdges; i++) {
// TODO: add error detection
_Graph_addEdge(graph, edges[i]);
}
return graph;
}
示例的最后是从文件中读取图形的函数 (Graph_readFromPath) 并将它们全部绑定在一起（在本示例中为 main，尽管在较大的程序中它不会是主要功能）。
Graph_t* Graph_readFromPath(const char *fName) {
FILE *in = fopen(fName, "r");
int nVertices = Count_readFromFile(in);
int nEdges = Count_readFromFile(in);
Edge_t *edges = Edges_readFromFile(in, nEdges);
fclose(in);
Graph_t* graph = Graph_create(Edge_t edges[], nEdges, nVertices);
free(edges);
return graph;
}
int main(int argc, char **argv) {
if (argc < 2) {
fprintf(stderr, "No input file given.");
return 1;
}
const char *fName = argv[1];
if (access(fname, R_OK)) {
fprintf(stderr, "Error reading input file '%s': %s", fName, strerror(errno));
return 1;
}
Graph_t *graph = Graph_readFromFile(fName);
if (! Graph_isConnected(graph)) {
// ...
}
Graph_destroy(graph);
return 0;
}