0

Okay so I have been trying to get this program to work for a long time. Basically it reads a text file then populates a structure that is designed to point to the four locations around that object: up, down, left and right. I believe I have the program figured out but I am getting this Stack Overflow and Access Violations

The problem is in the Dijkstra function as I am trying to call the function inside itself using queues. I was trying to implement Dijkstra using the methods I had learned and I figured this was the best way to implement file reading and Dijkstra's algorithm.

#include <iostream>
#include <queue>
#include <fstream>

using namespace std;

struct node {
    char data;
    node* left;
    node* right;
	node* up;
	node* down;
	int distance;
	bool visit;

	node(char newData)
	{
		data = newData;
		distance = 999;
		left = NULL;
		right = NULL;
		up = NULL;
		down = NULL;
		visit = false;
	}
}*root[20][20];

queue<node> q;
node *current = new node(NULL);

void inputFile(char &a)
{
    	ifstream in;
	in.open("maze.txt");

	if (!in)
	{
		cout << "Could not Open!" << endl;
		return;
	}

		for (int i = 0; i <=15; i++)
		{
			for (int j = 0; j <= 15; j++)
			{
				in >> a;

				if(root[i][j] == NULL)
				root[i][j] = new node(a);
			}
		}
}

void fillList()
{
    for (int i = 0; i <=15; i++)
    {
        for (int j = 0; j <= 15; j++)
        {
            root[i][j]->up = root[i-1][j];
            root[i][j]->down = root[i+1][j];
            root[i][j]->left = root[i][j-1];
            root[i][j]->right = root[i][j+1];
        }
    }
}

void Print(node *root)
{
        if (root != NULL)
        {
			if (root->distance == 999)
			{
				cout << ".";
			}
			else
			{
			cout << root->distance;
			}
           Print(root->right);
        }
}

void Dijkstra(node *root)
{
	if (root->data == 'o')
		{

			if ( root->right != NULL && root->distance < root->right->distance && root->right->data == 'o' && root->right->visit == false)
			{
			root->right->distance = root->distance+1;
			q.push(*root->right);
			}

		if ( root->down != NULL && root->distance < root->down->distance && root->down->data == 'o' && root->down->visit == false)
			{
			root->down->distance = root->distance+1;
			q.push(*root->down);
			}

		if ( root->left != NULL && root->distance < root->left->distance && root->left->data == 'o' && root->left->visit == false)
			{
			root->left->distance = root->distance+1;
			q.push(*root->left);
			}

		if ( root->up != NULL && root->distance < root->up->distance && root->up->data == 'o' && root->up->visit == false)
			{
			root->up->distance = root->distance+1;
			q.push(*root->up);
			}
		
		root->visit = true;

		q.pop();
		*current = q.front();

		}

	else if (root->data == 'Y')
		return;

	Dijkstra(current);
}

int main()
{
	char a;

	inputFile(a);
	fillList();

	root[0][0]->distance = 0;
	current = root[0][0];

	for(int i = 0; i <= 15; i++)
	{
	Print(*root[i]);
	cout << endl;
	}

	Dijkstra(root[0][0]);

	system("PAUSE");
	system("CLS");

	for(int i = 0; i <= 15; i++)
	{
	Print(*root[i]);
	cout << endl;
	}

	cout << root[0][0]->distance;

	return 0;
}

And here is the errors

First-chance exception at 0x00413df9 in final.exe: 0xC00000FD: Stack overflow.
Unhandled exception at 0x00413df9 in final.exe: 0xC00000FD: Stack overflow.Unhandled exception at 0x00413dfa in final.exe: 0xC0000005: Access violation writing location 0x00030ffc.
First-chance exception at 0x00413dfa in final.exe: 0xC0000005: Access violation writing location 0x00030ffc.
Unhandled exception at 0x00413dfa in final.exe: 0xC0000005: Access violation writing location 0x00030ffc.
First-chance exception at 0x00413dfa in final.exe: 0xC0000005: Access violation writing location 0x00030ffc.
Unhandled exception at 0x00413dfa in final.exe: 0xC0000005: Access violation writing location 0x00030ffc.
The program '[1392] final.exe: Native' has exited with code 0 (0x0).

Please help me!

Edited by sm4ckth3monkey: n/a

1
Contributor
1
Reply
3
Views
6 Years
Discussion Span
Last Post by sm4ckth3monkey
0

OKay I figured out what was wrong above... actually I just rewrote the code. Now my problem is I need to figure out a way so that I can modify the contents of the structure so that I can use a queue to find which node to visit next.

I was trying to use a pointer called current but when I implemented it I was suprised to see that nothing actually was changed in my program.

The main problem I am having is located in the Dijkstra() function. I need a refresher in pointers basically =(

#include <iostream>
#include <queue>
#include <fstream>

using namespace std;

struct node {
    char data;
    node* left;
    node* right;
	node* up;
	node* down;
	int distance;
	bool visit;

	node(char newData)
	{
		data = newData;
		distance = 999;
		left = NULL;
		right = NULL;
		up = NULL;
		down = NULL;
		visit = false;
	}
}*root[20][20];

queue<node> q;
node *current;

void inputFile(char &a)
{
    	ifstream in;
	in.open("maze.txt");

	if (!in)
	{
		cout << "Could not Open!" << endl;
		return;
	}

		for (int i = 0; i <=15; i++)
		{
			for (int j = 0; j <= 15; j++)
			{
				in >> a;

				if(root[i][j] == NULL)
				root[i][j] = new node(a);
			}
		}
}

void fillList()
{
    for (int i = 0; i <=15; i++)
    {
        for (int j = 0; j <= 15; j++)
        {
            root[i][j]->up = root[i-1][j];
            root[i][j]->down = root[i+1][j];
            root[i][j]->left = root[i][j-1];
            root[i][j]->right = root[i][j+1];
        }
    }
}

void Print(node *root)
{
        if (root != NULL)
        {
			cout << root->data;
           Print(root->right);
        }
}

void PrintDistance(node *root)
{
        if (root != NULL)
        {
			if (root->distance == 999)
			{
				cout << ".";
			}
			else
			{
			cout << root->distance;
			}
           PrintDistance(root->right);
        }
}

void Dijkstra()
{
	while (q.empty()==false)
	{
		q.pop();

		if(q.empty()==false)
			*current = q.front();
		else
			return;

	if(current->up != NULL && current->up->visit==false)
	{
		if (current->distance+1 < current->up->distance)
		{
			current->up->distance = current->distance+1;
		}
		q.push(*current->up);
	}

	if(current->down != NULL && current->down->visit==false)
	{
		if (current->distance+1 < current->down->distance)
		{
			current->down->distance = current->distance+1;
		}
		q.push(*current->down);
	}

	if(current->left != NULL && current->left->visit==false)
	{
		if (current->distance+1 < current->left->distance)
		{
			current->left->distance = current->distance+1;
		}
		q.push(*current->left);
	}

	if(current->right != NULL && current->right->visit==false)
	{
		if (current->distance+1 < current->right->distance)
		{
			current->right->distance = current->distance+1;
		}
		q.push(*current->right);
	}

	current->visit = true;
	}
}

int main()
{
	char a;

	inputFile(a);
	fillList();

	root[0][0]->distance = 0;
	q.push(*root[0][0]);

	for(int i = 0; i <= 15; i++)
	{
	Print(*root[i]);
	cout << endl;
	}

	Dijkstra();

	system("PAUSE");
	system("CLS");

	for(int i = 0; i <= 15; i++)
	{
	PrintDistance(*root[i]);
	cout << endl;
	}

	return 0;
}

Edited by sm4ckth3monkey: n/a

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.