CODEWITHSUNDEEP
c++
wagnerdelima
wagnerdelima

Reputation: 360

List inside struct in c++

I have a list inside a struct in c++; I just want to insert elements to this list, as normal.

My structs are:

// A structure to represent an adjacency list node
struct AdjListNode
{
    int dest;
    int weight;
    std::list<int> adjacents;
    struct AdjListNode* next;
};

// A structure to represent an adjacency list
struct AdjList
{
    int pos;
    struct AdjListNode *head; // pointer to head node of list
};

// A structure to represent a graph. A graph is an array of adjacency lists.
// Size of array will be V (number of vertices in graph)
struct Graph
{
    int V;
    struct AdjList* array;
};

struct Graph* createGraph(int V)
{
    struct Graph* graph = (struct Graph*) malloc(sizeof(struct Graph));
    graph->V = V;

    // Create an array of adjacency lists. Size of array will be V
    graph->array = (struct AdjList*) malloc(V * sizeof(struct AdjList));


    // Initialize each adjacency list as empty by making head as NULL
    for (int i = 0; i < V; ++i) {
        graph->array[i].head = NULL;
    }

    return graph;
}

When I try to aceess:

graph->array[position].head->adjacents->push_back(number);

It just prompts this to me:

Process finished with exit code 139 (interrupted by signal 11: SIGSEGV)

Sorry, I have no clue about this error.

Upvotes: 0

Views: 4622

Answers (1)

Franck
Franck

Reputation: 1635

The segmentation fault comes from 

graph->array[position].head->adjacents.push_back(number);

with 

graph->array[position].head = NULL;

I suppose that you have implicit struct invariant in your code since you have two lists that are likely to be connected: the linked list starting at AdjList::head and iterating through AdjNode::next and the list AdjNode::adjacent.

To keep the connection you can add a (C style) function that adds an element in both lists.

void
addAdjacent(AdjList& list, int adjacent) {
    // struct AdjListNode* newNode = (struct AdjListNode*) malloc(sizeof(struct AdjListNode));
    struct AdjListNode* newNode = new AdjListNode;
    newNode->next = list.head;
    list.head = newNode;
    newNode->dest = 0;
    newNode->weight = 0;
    newNode->adjacents = std::list<int>(); // undefined behavior with malloc
    newNode->adjacents.push_back(adjacent);
}

Note that it is a bad idea to mix C style (malloc/free) with C++ style (especially with the containers of the Standard Template Library). The commented part of my code creates a segmentation fault since a std::list has not its fields filled with 0.

At the end the following main function works even if it has many memory leaks (see the valgrind tool)

int main(int argc, char** argv) {
   struct Graph* graph = createGraph(2);
   addAdjacent(graph->array[0], 1);
   addAdjacent(graph->array[1], 2);
   free(graph);
   return 0;
}

A C++-98 solution (without any memory leaks) could be:

// A structure to represent an adjacency list node
struct AdjListNode
{
    int dest;
    int weight;
    std::list<int> adjacents;
    struct AdjListNode* next;

    AdjListNode() : dest(0), weight(0), next(NULL) {}
};

// A structure to represent an adjacency list
struct AdjList
{
    int pos;
    struct AdjListNode *head; // pointer to head node of list

    // Initialize each adjacency list as empty by making head as NULL
    AdjList() : pos(0), head(NULL) {}
    ~AdjList()
      { while (head) {
          struct AdjListNode* temp = head;
          head = head->next;
          delete temp;
        }
      }

    void addAdjacent(int adjacent)
      { struct AdjListNode* newNode = new AdjListNode;
        newNode->next = head;
        head = newNode;
        newNode->adjacents.push_back(adjacent);
      }
};

// A structure to represent a graph. A graph is an array of adjacency lists.
// Size of array will be V (number of vertices in graph)
struct Graph
{
    int V;
    struct AdjList* array;

    // Create an array of adjacency lists. Size of array will be V
    Graph(int v) : V(v), array(NULL)
      { if (v >= 0 && v <= 1000)
          array = new struct AdjList[v];
        else
          throw std::bad_alloc();
      }
    ~Graph()
      { delete [] array; }
};

int main() {
   struct Graph* graph = new Graph(2);
   graph->array[0].addAdjacent(1);
   graph->array[1].addAdjacent(1);
   delete graph;
   return 0;
}

Upvotes: 1

Related Questions