Wykresy używające listy dopasowania w C++

Question

Próbuję zaimplementować wykres w C++. Reprezentuję węzeł na wykresie za pomocą struktury, która zawiera dwie zmienne -
a) liczbę całkowitą zawierającą pewne informacje o węźle.
b) lista zawierająca indeks innych wierzchołków, które są z nią połączone.
Poniżej znajduje się kod.

// Graphs using adjacency list 

#include <iostream> 
#include <list> 
#include <cstdlib> 
using namespace std; 

// structure to represent a vertex(node) in a graph 
typedef struct vertex{ 
    int info; 
    list<int> adj; // adjacency list of edges contains the indexes to vertex 
} *vPtr;    

int main(){ 
    vPtr node = (vPtr)malloc(sizeof(struct vertex)); 
    node->info = 34;   // some arbitrary value 
    (node->adj).push_back(2); // trying to insert a value in the list 
    return 0; 
} 

Kod jest kompilowany dobrze, ale otrzymuję błąd czasu wykonywania, podczas gdy odpycham element na liście. Czy jest jakikolwiek problem w mojej strukturze.
Używam bloków kodu i GNU GCC, kompilator C++ 98 do kompilacji mojego kodu.

Answer 1

malloc jest funkcją C - nie powinien być stosowany z C++ obiektów which is very well explained here(krótka odpowiedź: C++, gdy nie mamy do czynienia z POD typów std::list w Twoim przypadku, musisz zadzwonić do konstruktora obiektu do mieć rzeczywisty obiekt gotowy do użycia, a malloc() tego nie robi).

You should used new instead. Podczas gdy malloc tylko przydziela blok pamięci o rozmiarze vertex, new robi to, a także inicjuje std::list, jak również, wywołując jego konstruktora (ciekawe, aby zwrócić uwagę, że po wywołaniu delete(), nazywasz również desctructor obiektu, jak również).

Oto fragment kodu, który działa w Twoim przypadku, chociaż proponuję, aby zacząć korzystać więcej funkcji C++ w ramach projektów C++:

#include <iostream> 
#include <list> 
#include <cstdlib> 
#include <new> 

using namespace std; 

// structure to represent a vertex(node) in a graph 
typedef struct vertex{ 
    int info; 
    list<int> adj; // adjacency list of edges contains the indexes to vertex 
} *vPtr;    

int main(){ 
    cout << "allocating memory for our vertex struct... \n"; 
    vPtr node = new vertex(); 
    node->info = 34;   // some arbitrary value 
    (node->adj).push_back(2); // trying to insert a value in the list 
    cout << "cleaning allocated memory... \n"; 
    delete(node); 

    return 0; 
} 

Answer 2

Kilka rzeczy.

1. Ponieważ używasz malloc bez constructor kiedykolwiek nazywa, i jako takie non prymitywny członkiem adj nigdy nie jest zbudowana i jest NULL.

2. Wyciewa pamięć, ponieważ nigdy nie można zwolnić/usunąć żadnej z dynamicznie przydzielanych pamięci.

3. Jeśli używasz C++, dlaczego używasz malloc zamiast new i delete?

4. Nie musisz określać ustrukturyzowanego wierzchołka w sizeof dla C++.

Aby naprawić to można zrobić:

vPtr node = new struct vertex(); // also change to delete instead of free 

lub

// use current malloc line, change adj to be a pointer to a list and new it 
// but this will cause additional problems for you since you really need to use a constructor for STL::list 
node->adj = new list<int>; 

Konkluzja naprawdę nie powinien być używany malloc tutaj.

Answer 3

Jest to odpowiedź UpAndAdam jest napisany całkowicie.

// Graphs using adjacency list 
// 
#include <iostream> 
#include <list> 
#include <cstdlib> 
using namespace std; 

// structure to represent a vertex(node) in a graph 
typedef struct vertex{ 
    int info; 
    list<int> *adj; // adjacency list of edges contains the indexes to vertex 
} *vPtr;    

int main(){ 
    vPtr node = (vPtr)malloc(sizeof(struct vertex)); 
    node->adj = new list<int>; 
    node->info = 34;   // some arbitrary value 
    (node->adj)->push_back(2); // trying to insert a value in the list 
    return 0; 
}