This is a homework problem; however I just want some direction. I have to write a module graph.cpp that implements djikstra's algorithm. so far i am at the reading in module and am trying to make an array of structures. here is the code.

// Zachary Dain
// CSCI 3300 Assignment 3
// tab stops: every 2 spaces

#include <iostream>
#include <math.h>
using namespace std;

enum StatusType {Done, Pending, Peripheral};

struct ListCell
{
	ListCell* next;
	int adjVertex;
	double weight;
	ListCell(int v, double wt, ListCell* n)
	{
		adjVertex = v;
		weight = wt;
		next = n;
	}	
};

struct arrayOfStructs
{
	StatusType s;
	ListCell* cell;
	arrayOfStructs()
	{
		s = Pending;
		cell = NULL;
	}
};


// readGraph() reads in the graph and puts the
// values into the appropriate lists/PQ

void readGraph(int n)
{
	int firstVert, secondVert;
	double weight;
	arrayOfStructs[] j = new arrayOfStructs[n+1];
	while(firstVert != 0)
	{
		cin >> firstVert;
		if(firstVert != 0)
		{
			cin >> secondVert;
			cin >> weight;
			j[firstVert].cell = new ListCell(secondVert,weight, j[firstVert].cell);
			j[secondVert].cell = new ListCell(firstVert,weight, j[secondVert].cell);
		}
	}
}

int main()
{
	int numVertex;
	cin >> numVertex;
	readGraph(numVertex);
}

I am getting the following errors:
graph.cpp: In function ‘void readGraph(int)’:
graph.cpp:43: error: expected unqualified-id before ‘[’ token
graph.cpp:51: error: ‘j’ was not declared in this scope
make: *** [graph] Error 1

I understand that the second error is due to the first one. I have looked around and have found no solution. Any advice? Should i use a typedef?

Edited 6 Years Ago by zrd0808: n/a

Line 43, move the "[]" after the 'j' and see what happens. The braces need to be associated with the variable name, not the dataType.

Edited 6 Years Ago by Fbody: n/a

Line 43, move the "[]" after the 'j' and see what happens. The braces need to be associated with the variable name, not the dataType.

That does work and thank you; however, now one more thing. I get an error stating it doesn't know the size of j and I know how to fix it by putting j[<number here>] (line 33) before the ; then just using j later on.......but I don't want to hard code it. I am asking for the size from numVertex before I call readGraph(n) and I am passing that value. What's wrong with it?

Edited 6 Years Ago by zrd0808: Mistake

The language cannot define an array of indeterminate size. You must give it a size. One option is to make j a pointer instead and dynamically create the array with new .

Anyone willing to help me find why this is giving me a segmentation fault?

// Zachary Dain
// CSCI 3300 Assignment 3
// tab stops: every 2 spaces

#include <iostream>
#include <math.h>
using namespace std;

enum StatusType {Done, Pending, Peripheral};

struct ListCell
{
	ListCell* next;
	int adjVertex;
	double weight;
	ListCell(int v, double wt, ListCell* n)
	{
		adjVertex = v;
		weight = wt;
		next = n;
	}	
};

struct Vertex
{
	StatusType s;
	ListCell* cell;
	double distance;
	int next;
	Vertex()
	{
		distance = 0;
		s = Peripheral;
		cell = NULL;
	}
};

struct Graph
{
	Vertex* info;
	int numVertices;
};

// readGraph() reads in the graph and puts the
// values into the appropriate lists

void readGraph(Graph &g)
{
	int u = -1, v;
	double weight;

	cin >> g.numVertices;
	g.info = new Vertex[g.numVertices+1];
	while(u != 0)
	{
		cin >> u;
		if(u != 0)
		{
			cin >> v;
			cin >> weight;
			g.info[u].cell = new ListCell(v,weight, g.info[u].cell);
			g.info[v].cell = new ListCell(u,weight, g.info[v].cell);
		}
	}
}


// printGraphHelper() calculates and prints the values
// of each cell using recursion
void printGraphHelper(int i, ListCell* l)
{
	if(l != NULL)
	{
		if(l->adjVertex > i)
		{
			cout << "  (" << i << "," << l->adjVertex << ")";
			cout << " weight " << l->weight << "\n";
		}
	printGraphHelper(i,l->next);
	}
}

// printGraph() prints out the number of vertices,
// each connecting edge, and its weight

void printGraph(int n, const Graph g)
{
	cout << "There are " << n << " vertices.\n";
	cout << "The edges are as follows.\n\n";
	for(int i = 1;i<n;++i)
	{
		printGraphHelper(i,g.info[i].cell);
	}
}

// stepOneHelper() initializes all of the values in the
// adjacent lists of the start vertex to Pending allowing
// recursion in the main stepOne
void stepOneHelper(Graph &g, int u)
{
	if(g.info[u].cell != NULL)
	{
		g.info[u].s = Pending;
	}
}

// stepOne() performs the first step of Djikstra's Algorithm
// finding the pending vertex with smallest current distance.

int stepOne(Graph &g, ListCell* l, int u)
{
	int lowestVert = l->next->adjVertex;
	double lowestWt = l->next->weight;
	stepOneHelper(g,u);
	if(l == NULL)
	{
		return lowestVert;
	}
	else
	{
//		lowestVert = u;
//		lowestWt = l->weight;
		if(g.info[u].s == Pending)
		{
			if(l->weight <= lowestWt)
			{
				lowestVert = l->adjVertex;
				lowestWt = l->weight;
			}cout << lowestVert;
		}
		return stepOne(g, l->next, u);
	}
}

int main()
{
	Graph g;
	int start, end;
	readGraph(g);
	cin >> start;
	cin >> end;
	printGraph(g.numVertices, g);
	cout << stepOne(g, g.info[start].cell, start);
}

The obvious errors are things like :

In

int stepOne(Graph &g, ListCell* l, int u)
{
int lowestVert = l->next->adjVertex;  // Seg fault here if l is null
double lowestWt = l->next->weight
stepOneHelper(g,u);
// THIS test is too late.
if(l == NULL)
{
return lowestVert;
}

Also

void stepOneHelper(Graph &g, int u)
{
  // NO Test : u can be bigger than the number of info points in g.
  // e.g u > numVertex.
  if(g.info[u].cell != NULL)
   {
     g.info[u].s = Pending;
   }
}

Seg faults are relatively easy to find were they came from. Just run with the debugger unit it crashes. [If on linux use ddd and then after the crash step up until you reach your code and see what the variables are.]

I am sorry for that last one I was brain dead. I have been working on this coding just the first step for about 3 days and have gotten pretty much no where on it. I am not trying to be a bother and ask for every little thing either and I am just getting frustrated with this coding and myself that I cannot even figure out what to do next. I have everything working and all, but it won't return the right vertex. I have tried multiple ways of doing it and nothing has worked. ListCell l is not null when I read it in and for this assignment it won't be. It is returning 0 as of right now which I do not understand. I get it to either return junk or return 0. I have even tried drawing diagrams tracing what it does. With the recursion is it going from the end of the list to the front and therefore not giving me the right answer?

Test File:

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

Coding: (The part I am having trouble with is stepOne() )

// Zachary Dain
// CSCI 3300 Assignment 3
// tab stops: every 2 spaces

#include <iostream>
#include <math.h>
using namespace std;

enum StatusType {Done, Pending, Peripheral};

struct ListCell
{
	ListCell* next;
	int adjVertex;
	double weight;
	ListCell(int v, double wt, ListCell* n)
	{
		adjVertex = v;
		weight = wt;
		next = n;
	}	
};

struct Vertex
{
	StatusType s;
	ListCell* cell;
	double distance;
	int next;
	Vertex()
	{
		distance = 0;
		s = Peripheral;
		cell = NULL;
	}
};

struct Graph
{
	Vertex* info;
	int numVertices;
};

// readGraph() reads in the graph and puts the // values into the appropriate lists

void readGraph(Graph &g)
{
	int u = -1, v;
	double weight;
	cin >> g.numVertices;
	g.info = new Vertex[g.numVertices+1];
	while(u != 0)
	{
		cin >> u;
		if(u != 0)
		{
			cin >> v;
			cin >> weight;
			g.info[u].cell = new ListCell(v,weight, g.info[u].cell);
			g.info[v].cell = new ListCell(u,weight, g.info[v].cell);
		}
	}
}


// printGraphHelper() calculates and prints the values // of each cell using recursion void printGraphHelper(int i, ListCell* l) {
	if(l != NULL)
	{
		if(l->adjVertex > i)
		{
			cout << "  (" << i << "," << l->adjVertex << ")";
			cout << " weight " << l->weight << "\n";
		}
	printGraphHelper(i,l->next);
	}
}

// printGraph() prints out the number of vertices, // each connecting edge, and its weight

void printGraph(int n, const Graph g)
{
	cout << "There are " << n << " vertices.\n";
	cout << "The edges are as follows.\n\n";
	for(int i = 1;i<n;++i)
	{
		printGraphHelper(i,g.info[i].cell);
	}
}

// stepOneHelper() initializes all of the values in the // adjacent lists of the start vertex to Pending allowing // recursion in the main stepOne void stepOneHelper(Graph &g, int u, ListCell* l) {
	if(u <= g.numVertices && l != NULL)
	{
		g.info[l->adjVertex].s = Pending;
		cout << l->adjVertex << "\t" << g.info[l->adjVertex].s << "\n";
		stepOneHelper(g, u, l->next);
	}
}

// stepOne() performs the first step of Djikstra's Algorithm // finding the pending vertex with smallest current distance.

int stepOne(Graph &g, ListCell* l, int u) {
	ListCell* temp = l;
	int lowestVert;
	double lowestWt;
	if(l != NULL)
	{
		if(g.info[l->adjVertex].s == Pending)
		{
			lowestVert = temp->adjVertex;
			lowestWt = temp->weight;
			cout << "vert\t" << lowestVert << " weight\t" << lowestWt << "\n";
			if(g.info[l->adjVertex].s == Pending)
			{
				if(l->weight <= lowestWt)
				{
					lowestWt = l-> weight;
					lowestVert = l->adjVertex;
				}
			}
			return stepOne(g,l->next,u);
		}
		return stepOne(g,l->next,u);
	}
	else 
		{
			g.info[lowestVert].s = Done;
			return lowestVert;
		}
}

// stepThree() updates the values of g.info.next and // g.info.distance such that g.info.next is the next // vertex that is closes and the distance is how far // from the start vertex that vertex is.
void stepThree(Graph &g)
{

}

int main()
{
	Graph g;
	int start, end;
	readGraph(g);
	cin >> start;
	cin >> end;
	printGraph(g.numVertices, g);
	cout << stepOne(g, g.info[start].cell,start);
}

output:

There are 5 vertices.
The edges are as follows.

  (1,3) weight 12
  (1,2) weight 9
  (2,5) weight 20
  (2,3) weight 6
  (2,4) weight 18
  (3,5) weight 15
0

Edited 6 Years Ago by zrd0808: forgot end code tag

figured it out and fixed it. works now. thank you all who helped <3 <3

Given that zrd0808 hasn't been on Dnaiweb in four years, I doubt you'll get an answer :-)

Edited 1 Year Ago by Schol-R-LEA

This question has already been answered. Start a new discussion instead.