Освобождение вызывает сбой - PullRequest
Новая
       3

Освобождение вызывает сбой

0 голосов
/ 02 мая 2018

В настоящее время я реализую псевдокод алгоритма Дейкстры, и у меня возникают проблемы с освобождением узлов. Мой код работает нормально, за исключением освобождающей части. Я освободил все malloc в коде, но он продолжает падать.

Я проверил все возможные ошибки, которые могут произойти, и сейчас я застрял с этим.

Вот мой код. 

#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->%i\n",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 = %i\n",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 %d\n ", 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 и freeing, и это может дать мне больше информации об этом.

Вот что происходит каждый раз, когда я запускаю его

РЕДАКТИРОВАТЬ: я запустил valgrind в моем коде, и, похоже, получена ошибка, называемая "core dumped". Насколько я знаю, ошибка сброса ядра возникает, когда я освобождаю узел дважды или более. Я не вижу никаких ошибок в моих кодах освобождения.

Вот что выводит valgrind

Ответы [ 2 ]

0 голосов
/ 02 мая 2018

Код кажется неправильным: 

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

Поскольку n инициализируется в 9 в initGraph, этот код будет зацикливаться для v = 0, 1, ..., 10

Однако в initGraph вы malloc'е 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] НЕДЕЙСТВИТЕЛЕН?

Программа вылетает, когда вы делаете: 

temp2 = temp->next

Так что вам нужно превратить код во что-то вроде: 

    struct node* temp = graph->LIST[v];
    while (temp!=NULL)
    {
        struct node* temp2 = temp->next;
        free(temp);
        temp = temp2;
    }
0 голосов
/ 02 мая 2018

вы пробовали использовать Valgrind? Если да, есть ли ошибки?

Valgrind - это инструмент для проверки утечек памяти и нарушений памяти. Он заменяет вашу систему malloc своей собственной, чтобы наблюдать за вашими действиями.

Также, пожалуйста, избегайте использования функций UPPERCASE, они должны быть зарезервированы для макросов и макрофункций (#define). Вы также должны использовать typedef, чтобы переименовать ваши структуры. Например, 

typedef struct s_myStruct
{
  ...
} t_myStruct;

t_mystruct *st = malloc(sizeof(t_mystruct));
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.

Нет похожих вопросов

...