Đồ thị sử dụng Danh sách Adjacency trong C++

Question

Tôi đang cố triển khai biểu đồ trong C++. Tôi đại diện cho một nút trong biểu đồ bằng cách sử dụng một cấu trúc chứa hai biến -
a) một số nguyên chứa một số thông tin về nút.
b) danh sách chứa chỉ mục của đỉnh khác được kết nối với nó.
Sau đây là mã.

// 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; 
} 

Mã được biên dịch tốt nhưng tôi gặp phải lỗi thời gian chạy trong khi tôi đang đẩy lại phần tử trong danh sách. Có bất kỳ vấn đề nào trong cấu trúc của tôi không.
Tôi đang sử dụng các khối mã và trình biên dịch GNU GCC, C++ 98 để biên dịch mã của tôi.

Answer 1

malloc là một hàm C - nó không nên được sử dụng với các đối tượng C++, which is very well explained here(trả lời ngắn gọn: trong C++, khi bạn đang phải đối phó với POD loại, std::list trong trường hợp của bạn, bạn phải gọi constructor của đối tượng để có đối tượng thực sự sẵn sàng để sử dụng và malloc() không làm điều đó).

You should used new instead. Trong khi malloc chỉ phân bổ một khối bộ nhớ có kích thước vertex, new thực hiện điều đó và cũng khởi tạo std::list bằng cách gọi hàm tạo của nó (thú vị chỉ ra rằng khi bạn gọi delete(), bạn đang gọi đối tượng desctructor của bạn).

Dưới đây là một đoạn mã mà làm việc cho trường hợp của bạn, mặc dù tôi đề nghị bạn để bắt đầu sử dụng nhiều C++ tính năng trong các dự án 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

Vài điều.

1. Bởi vì bạn đang sử dụng malloc không constructor được bao giờ gọi, và như như phi nguyên thủy thành viên adj không bao giờ được xây dựng và là NULL.

2. Bạn đang rò rỉ bộ nhớ vì bạn không bao giờ giải phóng/xóa bất kỳ bộ nhớ được cấp phát động nào.

3. Nếu bạn đang sử dụng C++ tại sao bạn sử dụng malloc thay vì new và delete?

4. Bạn không phải nói struct vertex trong sizeof cho C++.

Để khắc phục nó, bạn có thể làm:

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

hoặc

// 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>; 

Bottom line bạn thực sự không nên sử dụng malloc đây.

Answer 3

Đây là câu trả lời UpAndAdam, được viết hoàn toàn.

// 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; 
}