我想对图进行编程,但在添加顶点时会遇到问题。当我想重新分配内存时,程序停止,控制台只显示"中止(转储内核)"。
这是我的代码
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
struct Graph
{
int VertexCounter;
struct Vertices *vertex;
struct Edge **adjMat;
}MyGraph;
struct Vertices
{
int id;
char name[15];
float xPos;
float yPos;
};
struct Edge
{
int id;
struct Vertices *start;
struct Vertices *end;
};
//Initializing a graph with memory for one Vertex and one 1x1 adjecency Matrix but setting the number of Vertices to zero
void initGraph(struct Graph *graph)
{
graph = (struct Graph *) calloc(1, sizeof(struct Graph));
graph->vertex = (struct Vertices *) calloc(1, sizeof(struct Vertices));
graph->adjMat = (struct Edge **) calloc(1, sizeof(struct Edge *));
*(graph->adjMat) = (struct Edge *) calloc(1, sizeof(struct Edge));
graph->VertexCounter = 0;
printf("Number of Vertices: %dn", graph->VertexCounter);
}
//printing the number of Vertices
void test(struct Graph *graph)
{
printf("Number of Vertices: %dn", (*graph).VertexCounter);
}
//Reallocating the memory for an additional Vertex.
//I multiply the VertexCounter - 1 because the struct Graph contains space for one pointer of the type (struct Vertices *)
void addVertex(struct Graph *graph)
{
graph->VertexCounter++;
graph = (struct Graph *) realloc(graph, sizeof(struct Graph) +
(graph->VertexCounter - 1) * sizeof(struct Vertices));
}
int main()
{
struct Graph *graphPointer;
graphPointer = &MyGraph;
initGraph(graphPointer);
test(graphPointer);
addVertex(graphPointer);
test(graphPointer);
return 0;
}
输出:
顶点数:0
顶点数:0
中止(堆芯转储)
因此函数addVertex(结构体Graph*)不起作用。
我还没有包括新Edges的重新分配。
我该如何解决这个问题?
更新:
void addVertex(struct Graph **graph)
{
(*graph)->VertexCounter++;
*graph = realloc(*graph, sizeof(struct Graph) +
((*graph)->VertexCounter - 1) * sizeof(struct Vertices));
}
int main()
{
struct Graph *graphPointer;
graphPointer = &MyGraph;
initGraph(graphPointer);
test(graphPointer);
addVertex(&graphPointer);
test(graphPointer);
return 0;
}
这将返回与之前相同的输出
更新2:
void initGraph(struct Graph **graph)
{
(*graph) = (struct Graph *) calloc(1, sizeof(struct Graph *));
(*graph)->vertex = (struct Vertices *) calloc(1, sizeof(struct Vertices));
(*graph)->adjMat = (struct Edge **) calloc(1, sizeof(struct Edge *));
*((*graph)->adjMat) = (struct Edge *) calloc(1, sizeof(struct Edge));
(*graph)->VertexCounter = 0;
printf("Number of Vertices: %dn", (*graph)->VertexCounter);
}
//printing the number of Vertices
void test(struct Graph *graph)
{
printf("Number of Vertices: %dn", (*graph).VertexCounter);
}
//Reallocating the memory for an additional Vertex.
//I multiply the VertexCounter - 1 because the struct Graph contains space for one pointer of the type (struct Vertices *)
void addVertex(struct Graph **graph)
{
(*graph)->VertexCounter++;
void *temp = realloc(temp, sizeof(struct Graph *));
*graph = temp;
if(graph == NULL)
printf("Realloc failed");
}
int main()
{
struct Graph *graphPointer;
graphPointer = &MyGraph;
initGraph(&graphPointer);
test(graphPointer);
addVertex(&graphPointer);
test(graphPointer);
return 0;
}
我更改了initGraph和addVertex,但输出不会改变。
正如上面的注释中所指出的,您需要跟踪何时更改,或者可能更改graphPointer。例如,任何时候调用realloc,系统都可能被迫移动您的结构,并返回一个指向新分配的新指针。同样,正如所指出的,这个新指针被丢弃了,例如,在addVertex的末尾。如果你要改变函数中的指针,就像任何其他"引用调用"参数一样,给它传递一个指针
您真正需要做的另一件事是检查调用的返回值。有时,您认为调用有效,但事实并非如此,并且由于参数错误,总是返回NULL。无论哪种方式,你都不希望你的程序在未来某个时候崩溃,而没有任何原因。因此,例如,如果realloc失败,至少打印realloc的失败并退出。
好吧,我已经把您在示例中试图做的事情简单化了。您遇到的一个逻辑问题是initGraph
。您要分配给struct Graph
,而不是struct Vertices
或struct Edge **adjMat;
。除非您为其中任何一个添加值,否则只需将这些指针设置为NULL
,直到您实际需要为其中任意一个分配为止。
首先,让我们对struct
定义进行重新排序,以便在需要之前定义作为另一个结构一部分所需的任何结构,例如
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
struct Vertices {
int id;
char name[15];
float xPos;
float yPos;
};
struct Edge {
int id;
struct Vertices *start;
struct Vertices *end;
};
struct Graph {
int VertexCounter;
struct Vertices *vertex;
struct Edge **adjMat;
};
(注意:您的MyGraph
实例已被删除——如果您正在为graph
分配,则没有必要)
让我们向前跳,看看在main()
中如何处理指针,例如
将更改的参数编辑为addVertex
请注意,在以下所有代码中,addVertex
的参数已从struct Graph **graph
更改为struct Graph *graph
,因为addVertex
中没有重新分配graphpointer
。
int main (void) {
struct Graph *graphPointer = NULL;
initGraph (&graphPointer);
test(graphPointer);
addVertex (graphPointer);
test(graphPointer);
freeGraph (graphPointer); /* don't forget to free what you allocate */
}
上面,graphpointer
是唯一需要的指针。然后将graphpointer
的地址传递给initGraph
,以便initGraph
可以对原始地址进行操作,并且initGraph
中的分配将在main()
中可用。
要实现这一点,您可以在initGraph
中执行以下操作(注意:struct Graph
中任何其他成员的分配都会延迟,直到您真正有东西要添加为止)。如果您尝试预先分配一些直到代码中的某个未知点才会发生的事情,那么您就创建了一个灾难的配方。分配你需要的东西,当你需要的时候。(这并不妨碍你为每个块分配一个计数器,以减少所需的realloc
数量)
然后您的initGraph
变为:
void initGraph (struct Graph **graph)
{
*graph = calloc (1, sizeof **graph);
if (!*graph) { /* validate EVERY allocation */
perror ("calloc-*graph");
exit (EXIT_FAILURE);
}
(*graph)->vertex = NULL; /* set pointers NULL until you add_vertex */
(*graph)->adjMat = NULL; /* or you add_adjmat */
(*graph)->VertexCounter = 0; /* initialize counter */
}
上面已经初始化了一个struct Graph
——仅此而已——这是应该的。而使用initGraph
时,您需要传递graphpointer
的地址,以便在main()
中可以看到分配,使用addVertex
时,您只需要传递graphpointer
——因为该指针的地址在addVertex
中不会更改。您所要做的只是在graphpointer
中分配一个struct Graph
的成员,该成员可以简单地分配给vertex
指针。现在,当您准备添加顶点时,您可以执行以下操作:
void addVertex (struct Graph *graph)
{
/* always realloc using a temporary pointer */
void *tmp = realloc (graph->vertex, (graph->VertexCounter + 1) *
sizeof *graph->vertex);
if (!tmp) { /* validate EVERY reallocation */
perror ("realloc-(*graph)->vertex");
exit (EXIT_FAILURE);
}
graph->vertex = tmp;
graph->VertexCounter++;
}
还要注意,在addVertex
中,您所操作的只是graphpointer
的struct Vertices
成员,这也是应该的。如果此时要添加顶点,请考虑将其作为参数传入(或将数据作为参数传入),以便在addVertex
中分配/复制顶点数据,以将所有添加顶点代码保留在一个位置。
在您编写的任何动态分配内存的代码中,对于分配的任何内存块,您都有2个责任:(1)始终为内存块保留一个指向起始地址的指针,因此,(2)当不再需要时,它可以被释放。到目前为止,free
的快速freeGraph
功能可以是:
void freeGraph (struct Graph *graph)
{
free (graph->vertex);
free (graph);
}
(当您添加adjMat
的分配时,不要忘记在freeGraph
中添加相应的free
)
现在把它放在一起,你可以做:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
struct Vertices {
int id;
char name[15];
float xPos;
float yPos;
};
struct Edge {
int id;
struct Vertices *start;
struct Vertices *end;
};
struct Graph {
int VertexCounter;
struct Vertices *vertex;
struct Edge **adjMat;
};
void initGraph (struct Graph **graph)
{
*graph = calloc (1, sizeof **graph);
if (!*graph) { /* validate EVERY allocation */
perror ("calloc-*graph");
exit (EXIT_FAILURE);
}
(*graph)->vertex = NULL; /* set pointers NULL until you add_vertex */
(*graph)->adjMat = NULL; /* or you add_adjmat */
(*graph)->VertexCounter = 0; /* initialize counter */
}
void test (struct Graph *graph)
{
printf("Number of Vertices: %dn", graph->VertexCounter);
}
void addVertex (struct Graph *graph)
{
/* always realloc using a temporary pointer */
void *tmp = realloc (graph->vertex, (graph->VertexCounter + 1) *
sizeof *graph->vertex);
if (!tmp) { /* validate EVERY reallocation */
perror ("realloc-(*graph)->vertex");
exit (EXIT_FAILURE);
}
graph->vertex = tmp;
graph->VertexCounter++;
}
void freeGraph (struct Graph *graph)
{
free (graph->vertex);
free (graph);
}
int main (void) {
struct Graph *graphPointer = NULL;
initGraph (&graphPointer);
test(graphPointer);
addVertex (graphPointer);
test(graphPointer);
freeGraph (graphPointer); /* don't forget to free what you allocate */
}
/* move to add_adjmat functions:
(*graph)->adjMat = calloc (1, sizeof *(*graph)->adjMat);
if (!(*graph)->adjMat) {
perror ("calloc-(*graph)->adjMat");
exit (EXIT_FAILURE);
}
*(*graph)->adjMat = calloc (1, sizeof **(*graph)->adjMat);
*/
(注意:底部对adjMat
分配给将处理add_adjmat()
的任何函数的注释,等等。)
示例使用/输出
$ ./bin/graphalloc
Number of Vertices: 0
Number of Vertices: 1
内存使用/错误检查
您必须使用内存错误检查程序来确保您不会试图访问内存或在分配的块的边界之外写入,尝试读取或基于未初始化的值进行条件跳转,最后确认您释放了所有分配的内存。
对于Linux,valgrind
是正常的选择。每个平台都有类似的内存检查器。它们都很容易使用,只需通过它运行您的程序即可
$ valgrind --leak-check=full ./bin/graphalloc
==19442== Memcheck, a memory error detector
==19442== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==19442== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==19442== Command: ./bin/graphalloc
==19442==
Number of Vertices: 0
Number of Vertices: 1
==19442==
==19442== HEAP SUMMARY:
==19442== in use at exit: 0 bytes in 0 blocks
==19442== total heap usage: 3 allocs, 3 frees, 1,076 bytes allocated
==19442==
==19442== All heap blocks were freed -- no leaks are possible
==19442==
==19442== For counts of detected and suppressed errors, rerun with: -v
==19442== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
请始终确认您已经释放了分配的所有内存,并且没有内存错误。
这是一种允许您在需要时添加所需内容的方法。请注意,为了最大限度地减少重新分配,您可以添加一个VertexAllocated
成员并分配一个初始块8, 16, 32, etc..
,然后当VertexCounter == VertexAllocated
时,您可以调用realloc
和realloc
两次VertexAllocated
并继续进行。
仔细看看,如果你有问题,请告诉我。