Удаление циклов из связанного списка, состоящего из графовой структуры, не работает (язык C) - PullRequest
Новая
       6

Удаление циклов из связанного списка, состоящего из графовой структуры, не работает (язык C)

0 голосов
/ 04 ноября 2018

У меня есть структура graph , где каждый graph относится к вершине в связанном списке, и у каждой вершины есть один или несколько ребер . Поэтому я пытаюсь удалить циклы из графика. Каждая структура edge имеет путь, который я установил как True , если бы я использовал этот edge в качестве пути. Каждый ребро представляет собой связанный список внутри каждой вершины в графе

Так вот что происходит ... предположим, у меня есть узел со следующими ребрами: 

node ID: 8 edge src: 8 edge dst: 33
node ID: 8 edge src: 8 edge dst: 40

Это направленные ребра, и это означает, что они начинаются с идентификатора источника и заканчиваются идентификатором назначения

Если я удаляю первое ребро " ID узла: 3 ребра: 8 ребра: 33 " и внутри функции " remove_graph_cycles " Я печатаю все ребра ... так все отлично работает ... узел печатает только один край следующим образом: 

node ID: 8 edge src: 8 edge dst: 40

Проблема в том, что я печатаю весь график за пределами этой функции. Вне функции он печатает так: 

node ID: 8 edge src: 8 edge dst: 33
node ID: 8 edge src: 8 edge dst: 40

Я не понимаю, почему ... потому что я только что удалил первое ребро ... и затем я получаю ошибку: INVALID READ или INVALID WRITE , и программа вылетает.

У меня есть следующая функция удаления: 

void remove_graph_cycles(graph_node** graph)
{
    if((*graph) == NULL){
        return;
    }
    else{
        if((*graph)->edge != NULL){
            if((*graph)->edge->path == true && (*graph)->edge_count > 1){
                delete_edge((*graph)->edge, &(*graph)->edge);
                (*graph)->edge_count--;
            }
         }
        graph_edge* temp = (*graph)->edge;
        while((*graph)->edge != NULL){
            if((*graph)->edge->path == false){
                (*graph)->edge->path = true;
                remove_graph_cycles(&((*graph)->edge->node));
            }
            if((*graph)->edge != NULL){
                (*graph)->edge = (*graph)->edge->next;
            }
            else break; 
        }
        (*graph)->edge = temp;
    }
}

Это функция удаления края: 

void delete_edge(graph_edge* edge, graph_edge** head)
{
    if (edge->src_id == (*head)->src_id && edge->dst_id == (*head)->dst_id) {
        graph_edge* temp = *head;
        *head = (*head)->next;
        free(temp);
        return;
    }
    graph_edge* current = (*head)->next;
    graph_edge* previous = *head;
    while (current != NULL && previous != NULL) {
        if (edge->src_id == current->src_id && edge->dst_id == current->dst_id) {
            graph_edge* temp = current;
            previous->next = current->next;
            free(temp);
            return;
        }
        previous = current;
        current = current->next;
    }
    return;
}

вот как я печатаю график: 

while(*graph != NULL){

graph_edge* edge_list = (*graph)->edge;

printf("---------------------node id:%d ", (*graph)->id); printf("edge count: %d\n\n", (*graph)->edge_count);

    while(edge_list != NULL){

         printf("%d ", edge_list->node->id);
         printf("%s \n\n",edge_list->node->node_name); 

         edge_list = edge_list->next;

    }

    printf("\n\n----------------------------------------------------\n\n");

*graph = (*graph)->next;}

Я печатаю каждый узел графа рядом с указателем далее . Каждый ребро представляет собой структуру с источником и местом назначения id и узлом на графике, на который он указывает .

Ниже приведена ссылка на структуру данных:

Структура данных

...