C++ Adjacency List Insert Problems?

Question

I am having trouble implement an adjacency list in C++.
There is a problem in the insertEdgeList() function. I am trying to insert a node at the end of appropriate linked list. Instead the program is over writing the entire array.

Thanks for your help

[code]
# include


using namespace std;

struct Edge
// Purpose: Abstract structure for graph edges.
// Edge goes from i to j
{
int i;
int j;
};

struct EdgeNode
// Purpose: Linked list structure to store graph edges.
// Edge goes from (location of the linked list in the array + 1) to v
{
int v;
EdgeNode *nxt; // Pointer to next node
};


void insertEdgeMatrix(Edge e, bool m[][4] )
// Purpose: Store an edge int a matrix.
{
m[(e.i)-1][(e.j)-1] = 1;
m[(e.j)-1][(e.i)-1] = 1;
}

void insertEdgeList(int u, EdgeNode newNode, EdgeNode* l[])
// Purose: Store an edge into a adjacency list.
{
u--;

if (l[u] == NULL)
{
l[u] = &newNode;
}
else
{
EdgeNode* temp = l[u];
while(temp->nxt != NULL)
{
temp = temp->nxt;
}
temp->nxt = &newNode;
}
}

int main ()
{
// matrix for undirect graph
bool matrix[4][4] = {{0,0,0,0},
{0,0,0,0},
{0,0,0,0},
{0,0,0,0}};


EdgeNode node1;
node1.v = 2;
node1.nxt = NULL;

EdgeNode node2;
node2.v = 4;
node2.nxt = NULL;

EdgeNode node3;
node3.v = 1;
node3.nxt = NULL;

EdgeNode node4;
node4.v = 3;
node4.nxt = NULL;

EdgeNode node5;
node5.v = 2;
node5.nxt = NULL;

EdgeNode node6;
node6.v = 1;
node6.nxt = NULL;

// list for undirected graph
EdgeNode* List[4] = {NULL, NULL, NULL, NULL};

Edge edge1;
edge1.i = 1;
edge1.j = 2;

Edge edge2;
edge2.i = 1;
edge2.j = 4;

Edge edge3;
edge3.i = 2;
edge3.j = 1;

Edge edge4;
edge4.i = 2;
edge4.j = 3;

Edge edge5;
edge5.i = 3;
edge5.j = 2;

Edge edge6;
edge6.i = 4;
edge6.j = 1;

insertEdgeMatrix(edge1, matrix);
insertEdgeMatrix(edge2, matrix);
insertEdgeMatrix(edge3, matrix);
insertEdgeMatrix(edge4, matrix);
insertEdgeMatrix(edge5, matrix);
insertEdgeMatrix(edge6, matrix);

insertEdgeList(1, node1, List);
insertEdgeList(1, node2, List);
insertEdgeList(2, node3, List);
insertEdgeList(2, node4, List);
insertEdgeList(3, node4, List);
insertEdgeList(4, node5, List);

// print list
cout << endl << endl << "Adjacency list: " << endl;
for(int i = 0; i<4; i++)
{
cout << i+1 << " -> ";
EdgeNode* temp = List[i];
if(List[i] == NULL)
cout << "Empty" << endl;
else
{
cout << temp->v;
while(temp->nxt != NULL)
{
cout << ", " << temp->v;
temp = temp->nxt;
}
cout << endl;
}
}

//print matrix
cout << endl << "Adjacency Matrix: " << endl;
for(int i = 0; i<4; i++)
{
cout << "\t";
for(int j = 0; j<4; j++)
{
cout << matrix[i][j] << " ";
}
cout << endl;
}

system("pause");
return 0;
}
[/code]

Answer 1

Try changing the insertEdgeList's EdgeNode argument to a EdgeNode* :



// Purpose: Store an edge into an adjacency list.

void insertEdgeList(int u, EdgeNode *newNode, EdgeNode* l[]) {

  u--;



  if (l[u] == NULL) {

    l[u] = newNode;

  } else {

    EdgeNode* temp = l[u];

    while (temp->nxt != NULL){

      temp = temp->nxt;

    }

    temp->nxt = newNode;

  }

}



and your calls will now be :



  insertEdgeList(1, &node1, List);



etc.



Passing the EdgeNode by value, then taking the address of that argument in the function, does not do what you need it to.

Answer 2

sure, because of the fact the responder above reported, a hyperlink to the final node (circularly proper record) could be maximum useful. Or, you are able to desire to easily traverse the record till p->next is NULL.

Answer 3

particular, because of the fact the responder above suggested, a hyperlink to the final node (circularly related record) could be maximum effective. Or, you need to only traverse the record till p->next is NULL.