Access Violation Probs

[harrisaa93]

Writing a program that prints out the shortest path between two vertexes in a graph. I keep getting an access violation in my printGraph() method below where it is bold and underlined. I'm not sure why I'm getting an access violation instead of the loop breaking?

Here's the text file I'm passing into the program.

5
1 2 9.0
1 3 12.0
2 4 18.0
2 3 6.0
2 5 20.0
3 5 15.0
0
2 4

Here's how far the output gets before the violation.

(1, 3) Weight: 12
(1, 2) Weight: 9

#include <cstdio>
#include <iostream>
#include <list>
#include "pqueue.h"
using namespace std;

struct AdjList
{
	AdjList* nextvert;
	double weight;
	int vertex;
	
	AdjList(int vertexnum, double w, AdjList* v)
	{
		nextvert = v;
		weight = w;
		vertex = vertexnum;
	}
};

typedef AdjList* Adj;

struct Vertex 
{
	AdjList* adjacents;
	int next;
	double distance;
	bool visited;

	Vertex(){
		visited = false;
	}
};

struct Graph
{
	int numofvertices;
	Vertex* vertexi;

	Graph(int verts){
		numofvertices = verts;
		vertexi = new Vertex[verts + 1];
		for (int x = 1; x <= verts; x++){
			vertexi[x].visited = false;
		}
	}
};

bool IsEmpty(Adj x){
	return x == NULL;
}

Adj cons(int vert, double d, Adj x){
	return new AdjList(vert, d, x);
}

void insertadj(int vert, double d, Adj& x){
	x = cons(vert, d, x);
}

int getVertex(Adj x){
	return x -> vertex;
}

double getWeight(Adj x){
	return x -> weight;
}

Adj nextAdj(Adj x){
	return x -> nextvert;
}

void read(Graph g){
	int v1, v2;
	double x;
	cin >> v1;
	
	while (v1 != 0){
		cout << v1 << endl;
		cin >> v2;
		cout << v2 << endl;
		cin >> x;
		insertadj(v1, x, g.vertexi[v2].adjacents);
		insertadj(v2, x, g.vertexi[v1].adjacents);
		cin >> v1;
	}
}

void PrintVert(Adj x, int count){
	while (x->nextvert != NULL)
	{	
		int vtemp = getVertex(x);	
		if (vtemp > count)
		{
			cout << "( " << count << "," << vtemp << " ) Weight: " << getWeight(x) << endl;
		}
		x = nextAdj(x);
	}
}

void PrintGraph(Graph G){
	int count = 1;
	while (count <= G.numofvertices){
		PrintVert(G.vertexi[count].adjacents, count);
		count++;
	}
}

int main(int argc, char** argv)
{
	int x,start,end;
	cin >> x;
	Graph G(x);
	read(G);
	cin >> start;
	cin >> end;
	PrintGraph(G);
	return 0;
} 

[admkrk]

Without trying to compile this, the first thing that is most likely confusing you is the way you built your struct

struct Graph
{
	int numofvertices;
	Vertex* vertexi;

	Graph(int verts){
		numofvertices = verts;
		vertexi = new Vertex[verts + 1];
		for (int x = 1; x <= verts; x++){
			vertexi[x].visited = false;
		}
	}
};

Indexes start at 0. Making them start at index++ is almost always a bad idea. Change all the 1's in verts + 1 and x = 1 to 0's and you will probably stop going out of bounds.
If you use a debugger or print debug lines you will see why.
Alternatively, vertexi[x + 1].visited = false; would probably fix it also.

[coder777]

There's no way that it couldn't crash. Look at line 98. x must become null otherwise you have an infinite loop.

The typedef on line 22 isn't helpful at all. It rather obfuscate the true nature of Adj. It looks like an object but is really a pointer

[harrisaa93]

Ok so I here's my question now. When you get to the end of adjacency list the nextvert* pointer points to what exactly? Because I realize that I'm checking to see if the next item in the current adjacency list I'm traversing is equal to NULL, but the nextvert pointer on the last item in the adj list wouldn't point to anything. So how would I check for that?

[AbstractionAnon]

When you get to the end of adjacency list the nextvert* pointer points to what exactly?

Undefined. It points past the memory you allocated. What is in that memory location is undetermined. If you want a NULL at the end of your pointer list, you must allocate space for it and explicitly store it.

Generally, accessing a pointer list is done using an iterator or counter, not by looking for a NULL pointer at the end of the list. Accessing argv in main is a notable exception to this. In this case, the run time has explictly built the list with a NULL at the end.

Note also that both AdjList and Vertex have a memory leak. You have no destructor which frees the memory allocated for the list. Suggestion: use std::vector instead of managing your own array.

[harrisaa93]

Is there anyway I could modify my AdjList* constructor to set nextvert* to Null when it's the last item in the list?

[AbstractionAnon]

Already explained:

abstractionanon wrote:

If you want a NULL at the end of your pointer list, you must allocate space for it and explicitly store it.

Frankly, I think it would be a lot easier to use std::vector.

[harrisaa93]

I would but i have to use these specific structures... assignment requirement.

[coder777]

You're just dealing with x. So why don't you use x?

void PrintVert(Adj x, int count){
	while (x != NULL)
	{	
		int vtemp = getVertex(x);	
		if (vtemp > count)
		{
			cout << "( " << count << "," << vtemp << " ) Weight: " << getWeight(x) << endl;
		}
		x = nextAdj(x);
	}
}