Оператор перегрузки скорее всего не работает
Не могли бы вы, ребята, проверить мою функцию что-то неправильное (), и мои операторы перегрузки. Иногда, когда я запускаю функцию что-то не так (), я получаю "True", а иногда "False". Я ничего не меняю, почему это происходит?
Это график алгоритма Дейкстры, в котором я работаю.
Благодарю вас
main.cpp:
#include <iostream>
#include <fstream>
#include "graph.h"
using namespace std;
int main(){
//
graph g;
g.addVertices();
//g.printAll();
g.addEdges();
cout << "Hello" << endl;
//g.printAdjList(5.74);
//g.DJAlgorithm();
g.somethingWrong();
return 0;
}
graph.h
#include <iostream>
#include <list>
#include <fstream>
#include "minHeap.h"
using namespace std;
class graph{
protected:
class vertex{
public:
int x;
int y;
double cost;
double weight;
vertex * parent;
list<vertex*> adjacencyList;
vertex(int xc, int yc, double c){
x = xc;
y = yc;
cost = c;
weight = -1;
parent = NULL;
}
// operator overloading
// dont know if to add =
vertex & vertex::operator=(vertex * z){
return *z;
}
bool vertex::operator==(vertex * z){
return (this->weight == z->weight);
}
bool vertex::operator!=(vertex * z){
return (this->weight != z->weight);
}
bool vertex::operator<=(vertex * z){
return (this->weight <= z->weight);
}
bool vertex::operator<(vertex * z){
return (this->weight < z->weight);
}
bool vertex::operator>=(vertex * z){
return (this->weight >= z->weight);
}
bool vertex::operator>(vertex * z){
return (this->weight > z->weight);
}
};
list<vertex*> vertexList;
int numOfVertices;
public:
int sX;
int sY;
int eX;
int eY;
graph(){
numOfVertices = 0;
}
void somethingWrong(){
vertex *dog = new vertex(0,0,0);
vertex * cat = new vertex(0,0,0);
dog->weight = 5;
cat->weight = 9;
if(dog < cat){
cout << "True" << endl;
}
else{
cout << "False" << endl;
}
}
void addVertices(){
ifstream inFile;
double w;
int countX = 1;
int countY = 1;
inFile.open("grid.txt");
if(!inFile){
cout << "Error opening file!" << endl;
return;
}
// get the coordinates of the starting and
// ending position
inFile >> sX;
inFile >> sY;
inFile >> eX;
inFile >> eY;
// get the grid of data
while(!inFile.eof()){
inFile >> w;
vertexList.push_back(new vertex(countX,countY,w));
numOfVertices++;
countX++;
if(inFile.peek() == '\n'){
countX = 1;
countY++;
}
}
}
void addEdges(){
for each(vertex * v in vertexList){
for each(vertex * w in vertexList){
if(((v->x == w->x) && (abs(v->y - w->y)) == 1) || ((v->y == w->y) && (abs(v->x - w->x) == 1))){
v->adjacencyList.push_back(w);
}
}
}
}
// prints all the grid, for verification purposes
void printAll(){
cout << sX << " " << sY << endl;
cout << eX << " " << eY << endl;
for each(vertex * v in vertexList){
cout << v->x << " " << v->y << " " << v->cost << endl;
}
}
// print a vertex's adjacency list
void printAdjList(double c){
for each(vertex * v in vertexList){
if(v->cost == c){
for each(vertex * w in v->adjacencyList){
cout << w->x << " " << w->y << " " << w->cost << endl;
}
return;
}
}
}
// problelm here
// prints the path from vertex x
void printPath(vertex * x){
if(x != NULL){
//cout << "sup" << endl;
printPath(x->parent);
cout << "(" << x->x << "," << x->y << ") weight: " << x->weight << endl;
}
}
void DJAlgorithm(){
// min Heap item
minHeap<vertex*> C(numOfVertices);
vertex * s;
vertex * x;
vertex * e;
// find required start and end vertices
for each(vertex * v in vertexList){
if(v->x == sX && v->y == sY){
s = v;
}
if(v->x == eX && v->y == eY){
e = v;
}
}
// set up all values
for each(vertex * v in vertexList){
v->weight = -1;
v->parent = NULL;
}
s->weight = 0;
// insert everything in to the queue/minHeap
for each (vertex * v in vertexList){
C.insert(v);
}
while(!C.empty()){
x = C.extractMin();
for each(vertex * v in x->adjacencyList){
// relax
// if not discovered
if(v->weight == -1){
v->weight = x->weight;
v->parent = x;
}
// if already discovered
else{
if(x->weight + v->cost < v->weight){
v->weight = x->weight + v->cost;
v->parent = x;
}
}
}
}
// print out the path back
printPath(e);
}
};
// структура данных min heap
#include <iostream>
using namespace std;
template<class THING>
class minHeap
{
private:
//array to hold items
THING * items;
int n;
//return index of parent of i
int parent(int i)
{
return (i-1)/2;
}
//return index of left child of i
int lchild(int i)
{
return i*2 + 1;
}
//return index of right child of i
int rchild(int i)
{
return i*2 + 2;
}
//return index of smaller child
int minChild(int i)
{
if( lchild(i) >= n ) //a leaf!
return i;
else if( lchild(i) == (n-1) )
return lchild(i);
else if( items[lchild(i)] < items[rchild(i)] )
return lchild(i);
else
return rchild(i);
}
//bubble item at index current up tree
//until there's no more violation
void bubbleUp(int current)
{
// ignoring all these
if( current == 0 ) //the root! easy!
{
//do nothing, done, no violation, base case!
}
else if( items[current] >= items[parent(current)] ) //no violation
{
//do nothing!, done, go home, base case!
}
else
{
//step 1: swap current with parent
swap( items[current], items[parent(current)] );
//step 2: keep bubbling item up
bubbleUp( parent(current) );
}
}
void bubbleDown(int current)
{
if( lchild(current) >= n ) //current is a leaf....
{
//do nothing! base case!! party down!
}
else if( items[current] <= items[minChild(current)] ) //no violation..
{
//done!1 party down! base case
}
else
{
//step 1: swap with min child
int mchild = minChild(current);
swap( items[current], items[mchild] );
//step 2: continue bubbling down
bubbleDown(mchild);
}
}
public:
minHeap(int cap)
{
items = new THING[cap];
n=0;
}
//return true if heap is empty
bool empty()
{
if( n==0 )
return true;
else
return false;
}
//add item x to heap
void insert(THING x)
{
//step 1: add x to end of array
items[n] = x;
n++;
//step 2: bubble up!
bubbleUp(n-1);
}
//remove and return smallest item in heap
THING extractMin()
{
//step 1: store root item in output box
THING output = items[0];
//step 2: put last item at root
items[0] = items[n-1];
n--;
//step 3: bubble down!
bubbleDown(0);
return output;
}
};
2 ответа
vertex *dog = new vertex(0,0,0);
vertex *cat = new vertex(0,0,0);
if(dog < cat)
Сравнивает два указателя и эффективно адреса. Сравнение адресов не имеет большого смысла, так как они могут иметь любые значения.
Вам нужно сравнить два объекта:
if(*dog < *cat)
Конечно, вам также нужно изменить прототип функции перегруженного оператора, чтобы учесть это.
vertex & vertex::operator=(vertex * z)
Это оператор присваивания, который принимает левую часть типа vertex и правая часть типа vextex*, Обычная подпись для operator= является:
vertex& operator=(const vertex& rhs);
Последнее определение позволяет присваивать один объект другому объекту, тогда как первое присваивает указатель на объект.