C语言 释放导致崩溃

Question

我目前正在实现Dijkstra算法的伪代码，我在释放节点时遇到了问题。除了释放部分外，我的代码似乎工作正常。我已经释放了代码中的所有mallocs，但它仍然不断崩溃。

我已经检查了可能发生的所有可能的"无错误"，我目前对此感到困扰。

这是我的代码。

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <string.h>
#include <math.h>
//#####################################################################
//#####################################################################
//#####################################################################
//#####################################################################
//######################### Structures ################################
//#####################################################################
struct node
{
int vertex;
int cost;
struct node* next;
};
struct PQ
{
int* heap;
int* index;
double* key;
int sizePQ;
};
//#####################################################################
//######################### Graph Things ##############################
//#####################################################################
struct node* createNode(int v,int cost)
{
struct node* newNode = malloc(sizeof(struct node));
newNode->vertex = v;
newNode->cost = cost;
newNode->next = NULL;
return newNode;
}
struct G{
int n;
int* pred;
double* dist;
struct node** LIST;
};
struct G* initGraph(int vertices)
{
struct G* graph = malloc(sizeof(struct G));
graph->n = vertices-1;
graph->LIST = malloc(vertices * sizeof(struct node*));
graph->pred = malloc(vertices * sizeof(int));
graph->dist = malloc(vertices * sizeof(double));
int i;
for (i = 0; i <= vertices; i++)
graph->LIST[i] = NULL;
return graph;
}
void addEdge(struct G* graph, int src, int dest, int cost)
{
struct node* newNode = createNode(dest, cost);
newNode->next = graph->LIST[src];
graph->LIST[src] = newNode;
}
void freeG(struct G* graph){
int v;
for (v = 0; v <= graph->n+1; v++)
{
struct node* temp = graph->LIST[v];
struct node* temp2 = temp->next;
while (temp!=NULL)
{
free(temp);
temp = temp2;
temp2 = temp->next;
}
}
free(graph->pred);
free(graph->dist);
free(graph->LIST);
free(graph);
}
void freePQ(struct PQ* PQ){
free(PQ->heap);
free(PQ->key);
free(PQ->index);
free(PQ);
}
//#####################################################################
//############################ Procedures #############################
//#####################################################################
void PQ_UNDERFLOW(){
printf("Underflow Detected");
}
void InitPQ(struct G* G,struct PQ* PQ, int s){
PQ->heap = malloc(G->n * sizeof(int));
PQ->index = malloc(G->n * sizeof(int));
PQ->key = malloc(G->n * sizeof(double));
PQ->sizePQ = G->n;
// printf("%i",G->n);
int i = 1;
int v;
for(v=1;v<=G->n;v++){
if(v==s){
PQ->heap[1]=s;
PQ->index[s]=1;
PQ->key[s]=0;
}
else{
++i;
PQ->heap[i]=v;
PQ->index[v]=i;
PQ->key[v]=INFINITY;
// printf("%i//",PQ->heap[i]);
//printf("%lf ",PQ->key[v]);
}
}
}
void HEAPIFY(struct PQ* PQ,int r){
//printf("%i",PQ->heap[r]-1);
double k = PQ->key[PQ->heap[r]];
int l = PQ->heap[r];
int i = r, j = 2*i;
while(j<=PQ->sizePQ){
if (j<PQ->sizePQ && PQ->key[PQ->heap[j+1]]< PQ->key[PQ->heap[j]]){
++j;
}
if(PQ->key[PQ->heap[j]]<k){
PQ->heap[i]=PQ->heap[j];
PQ->index[PQ->heap[j]]=i;
i=j;
j=2*i;
}else break;
}
PQ->heap[i]=l;
PQ->index[l]=i;
}
int IsEmptyPQ(struct PQ* PQ){
return(PQ->sizePQ==0);
}
void EXTRACT_MIN(struct PQ* PQ, int *j){
if (PQ->sizePQ == 0) PQ_UNDERFLOW();
else{
*j=PQ->heap[1];
PQ->heap[1] = PQ->heap[PQ->sizePQ];
PQ->index[PQ->heap[1]]=1;
PQ->sizePQ=PQ->sizePQ-1;
HEAPIFY(PQ,1);
}
}
void DECREASE_KEY(struct PQ* PQ, int l, double newkey){
PQ->key[l] = newkey;
int i = PQ->index[l];//printf("pqindexl->%in",PQ->index[l]);
int j =floor(i/2);
while (i > 1 && PQ->key[PQ->heap[j]]>newkey){
PQ->heap[i]= PQ->heap[j];
PQ->index[PQ->heap[j]]=i;
i=j; j =floor(i/2);
}
PQ->heap[i]=l;
PQ->index[l]=i;
}
//#####################################################################
//############################ DIJKSTRA   #############################
//#####################################################################
void DIJKSTRA(struct G* G, struct PQ* PQ, int s){
InitPQ(G,PQ,s);
int u = 0,v;
double newval;
G->pred[s]=0;
while(!IsEmptyPQ(PQ)){
EXTRACT_MIN(PQ,&u);
if (PQ->key[u]== INFINITY){break;}
struct node* a = G->LIST[u];
while (a!=NULL)
{
v = a->vertex;//printf("vertex = %in",a->vertex);
newval = PQ->key[u]+a->cost;
if (PQ->key[v]>newval){
G->pred[v]=u;
DECREASE_KEY(PQ,v,newval);
}
a = a->next;
}
}
G->dist=PQ->key;
}

//#####################################################################
//############################  print g   #############################
//#####################################################################
void DISPLAY_PATH(struct G* G, int s,int v){
int path[G->n];
int len = 1;
path[len]=v;
int i=v;
while(i!=s){
if(G->pred[i]==0){printf("No path found");return;}
else{
i = G->pred[i];
++len;
path[len]=i;
}
}
printf("Shortest path found: ");
while(len>=1){
printf("%i",path[len]);
if(len!=1)printf(" -> ");
len--;
}
}
void printGraph(struct G* graph)
{
int v;
for (v = 1; v <= graph->n; v++)
{
struct node* temp = graph->LIST[v];
printf("n Adjacency list of vertex %dn ", v);
while (temp)
{
printf("%d -> ", temp->vertex);
temp = temp->next;
}
printf("n");
}
}
//#####################################################################
//#####################################################################
//#####################################################################
int main()
{
struct G* graph = initGraph(10);
addEdge(graph, 1, 2, 4);
addEdge(graph, 1, 8, 8);
addEdge(graph, 2, 3, 8);
addEdge(graph, 2, 8, 11);
addEdge(graph, 3, 4, 7);
addEdge(graph, 3, 9, 2);
addEdge(graph, 3, 6, 4);
addEdge(graph, 4, 5, 9);
addEdge(graph, 4, 6, 14);
addEdge(graph, 5, 6, 10);
addEdge(graph, 6, 7, 2);
addEdge(graph, 7, 8, 1);
addEdge(graph, 7, 9, 6);
addEdge(graph, 8, 9, 7);
printGraph(graph);
printf("n");
struct PQ* PQ=malloc(sizeof(struct PQ));
DIJKSTRA(graph, PQ, 1);
DISPLAY_PATH(graph,1,8);
freePQ(PQ);
freeG(graph);
}

除了释放部分外，一切正常。它打印算法的所需输出，但在程序结束时崩溃。

我也真的很想了解 malloc 和自由是如何工作的，这可能会给我更多关于它的信息。

这是我每次运行它时发生的情况

编辑：我已经在我的代码上运行了valgrind，它似乎得到了一个名为"核心转储"的错误。据我所知，当我释放节点两次或更多次时，会发生核心转储错误。不过，我的释放代码中没有看到任何错误。

这是瓦尔格林德输出的内容

Answer 1

你试过使用Valgrind吗？如果是这样，是否有任何错误？

Valgrind 是一个检查内存泄漏和内存冲突的工具。它会用自己的系统替换您的系统来观察您的操作。

另外，请避免使用大写函数，这些函数应保留用于宏和宏函数(#define(。 您还应该使用typedef来重命名结构。 例如

typedef struct s_myStruct
{
...
} t_myStruct;
t_mystruct *st = malloc(sizeof(t_mystruct));

Answer 2

这段代码似乎是错误的：

for (v = 0; v <= graph->n+1; v++)
{
struct node* temp = graph->LIST[v];

当n初始化为9时initGraph此代码将循环 v = 0， 1， ...， 10

但是，在initGraph中，您错误地分配了 10 个元素，因此现在您可以越界访问LIST。

尝试

for (v = 0; v < graph->n+1; v++)
{
struct node* temp = graph->LIST[v];

相反。

然后看看这个：

struct node* temp = graph->LIST[v];
struct node* temp2 = temp->next;

如果graph->LIST[v]为 NULL 会发生什么？

当您执行以下操作时，程序将崩溃：

temp2 = temp->next

所以你需要把代码变成这样的东西：

struct node* temp = graph->LIST[v];
while (temp!=NULL)
{
struct node* temp2 = temp->next;
free(temp);
temp = temp2;
}