Question: Hello, I have a file named data2.txt and I would like to know how I can open and read the file in my code while
Hello, I have a file named data2.txt and I would like to know how I can open and read the file in my code while printing the results similar to the picture provided. Everything regarding classes is implemented, the only help I need is with main.cpp file. TIA!
----------------------------------------------------------------------------
my code:
linkedList.h:
#ifndef LINKEDLIST_H
#define LINKEDLIST_H
#include
#include
using namespace std;
//Definition of the node
template
struct nodeType
{
Type info;
nodeType
};
template
class linkedListIterator
{
public:
linkedListIterator();
//Default constructor
//Postcondition: current = nullptr;
linkedListIterator(nodeType
//Constructor with a parameter.
//Postcondition: current = ptr;
Type operator*();
//Function to overload the dereferencing operator *.
//Postcondition: Returns the info contained in the node.
linkedListIterator
//Overload the pre-increment operator.
//Postcondition: The iterator is advanced to the next
// node.
bool operator==(const linkedListIterator
//Overload the equality operator.
//Postcondition: Returns true if this iterator is equal to
// the iterator specified by right,
// otherwise it returns the value false.
bool operator!=(const linkedListIterator
//Overload the not equal to operator.
//Postcondition: Returns true if this iterator is not
// equal to the iterator specified by
// right; otherwise it returns the value
// false.
private:
nodeType
/ode in the linked list
};
template
linkedListIterator
{
current = nullptr;
}
template
linkedListIterator
linkedListIterator(nodeType
{
current = ptr;
}
template
Type linkedListIterator
{
return current->info;
}
template
linkedListIterator
operator++()
{
current = current->link;
return *this;
}
template
bool linkedListIterator
(const linkedListIterator
{
return (current == right.current);
}
template
bool linkedListIterator
(const linkedListIterator
{ return (current != right.current);
}
//***************** class linkedListType ****************
template
class linkedListType
{
public:
const linkedListType
(const linkedListType
//Overload the assignment operator.
void initializeList();
//Initialize the list to an empty state.
//Postcondition: first = nullptr, last = nullptr,
// count = 0;
bool isEmptyList() const;
//Function to determine whether the list is empty.
//Postcondition: Returns true if the list is empty,
// otherwise it returns false.
void print() const;
//Function to output the data contained in each node.
//Postcondition: none
int length() const;
//Function to return the number of nodes in the list.
//Postcondition: The value of count is returned.
void destroyList();
//Function to delete all the nodes from the list.
//Postcondition: first = nullptr, last = nullptr,
// count = 0;
Type front() const;
//Function to return the first element of the list.
//Precondition: The list must exist and must not be
// empty.
//Postcondition: If the list is empty, the program
// terminates; otherwise, the first
// element of the list is returned.
Type back() const;
//Function to return the last element of the list.
//Precondition: The list must exist and must not be
// empty.
//Postcondition: If the list is empty, the program
// terminates; otherwise, the last
// element of the list is returned.
virtual bool search(const Type& searchItem) const = 0;
//Function to determine whether searchItem is in the list.
//Postcondition: Returns true if searchItem is in the
// list, otherwise the value false is
// returned.
virtual void insertFirst(const Type& newItem) = 0;
//Function to insert newItem at the beginning of the list.
//Postcondition: first points to the new list, newItem is
// inserted at the beginning of the list,
// last points to the last node in the list,
// and count is incremented by 1.
virtual void insertLast(const Type& newItem) = 0;
//Function to insert newItem at the end of the list.
//Postcondition: first points to the new list, newItem
// is inserted at the end of the list,
// last points to the last node in the
// list, and count is incremented by 1.
virtual void deleteNode(const Type& deleteItem) = 0;
//Function to delete deleteItem from the list.
//Postcondition: If found, the node containing
// deleteItem is deleted from the list.
// first points to the first node, last
// points to the last node of the updated
// list, and count is decremented by 1.
linkedListIterator
//Function to return an iterator at the begining of
//the linked list.
//Postcondition: Returns an iterator such that current
// is set to first.
linkedListIterator
//Function to return an iterator one element past the
//last element of the linked list.
//Postcondition: Returns an iterator such that current
// is set to nullptr.
linkedListType();
//Default constructor
//Initializes the list to an empty state.
//Postcondition: first = nullptr, last = nullptr,
// count = 0;
linkedListType(const linkedListType
//copy constructor
~linkedListType();
//Destructor
//Deletes all the nodes from the list.
//Postcondition: The list object is destroyed.
protected:
int count; //variable to store the number of
//elements in the list
nodeType
nodeType
private:
void copyList(const linkedListType
//Function to make a copy of otherList.
//Postcondition: A copy of otherList is created and
// assigned to this list.
};
template
bool linkedListType
{
return (first == nullptr);
}
template
linkedListType
{
first = nullptr;
last = nullptr;
count = 0;
}
template
void linkedListType
{
nodeType
//occupied by the node
while (first != nullptr) //while there are nodes in
{ //the list
temp = first; //set temp to the current node
first = first->link; //advance first to the next node
delete temp; //deallocate the memory occupied by temp
}
last = nullptr; //initialize last to nullptr; first has
//already been set to nullptr by the while loop
count = 0;
}
template
void linkedListType
{
destroyList(); //if the list has any nodes, delete them
}
template
void linkedListType
{
nodeType
current = first; //set current so that it points to
//the first node
while (current != nullptr) //while more data to print
{
cout info
current = current->link;
}
}//end print
template
int linkedListType
{
return count;
} //end length
template
Type linkedListType
{
assert(first != nullptr);
return first->info; //return the info of the first node
}//end front
template
Type linkedListType
{
assert(last != nullptr);
return last->info; //return the info of the last node
}//end back
template
linkedListIterator
{
linkedListIterator
return temp;
}
template
linkedListIterator
{
linkedListIterator
return temp;
}
template
void linkedListType
(const linkedListType
{
nodeType
nodeType
if (first != nullptr) //if the list is nonempty, make it empty
destroyList();
if (otherList.first == nullptr) //otherList is empty
{
first = nullptr;
last = nullptr;
count = 0;
}
else
{
current = otherList.first; //current points to the
//list to be copied
count = otherList.count;
//copy the first node
first = new nodeType
first->info = current->info; //copy the info
first->link = nullptr; //set the link field of
//the node to nullptr
last = first; //make last point to the
//first node
current = current->link; //make current point to
//the next node
//copy the remaining list
while (current != nullptr)
{
newNode = new nodeType
newNode->info = current->info; //copy the info
newNode->link = nullptr; //set the link of
/ewNode to nullptr
last->link = newNode; //attach newNode after last
last = newNode; //make last point to
//the actual last node
current = current->link; //make current point
//to the next node
}//end while
}//end else
}//end copyList
template
linkedListType
{
destroyList();
}//end destructor
template
linkedListType
(const linkedListType
{
first = nullptr;
copyList(otherList);
}//end copy constructor
//overload the assignment operator
template
const linkedListType
(const linkedListType
{
if (this != &otherList) //avoid self-copy
{
copyList(otherList);
}//end else
return *this;
}
#endif /* LINKEDLIST_H */
------------------------------------------------------------
------------------------------------------------------------
unorderedLinkedList.h
#ifndef UNORDEREDLINKEDLIST_H #define UNORDEREDLINKEDLIST_H
#include "linkedList.h"
using namespace std; template
void insertFirst(const Type& newItem); //Function to insert newItem at the beginning of the list. //Postcondition: first points to the new list, newItem is // inserted at the beginning of the list, // last points to the last node in the // list, and count is incremented by 1.
void insertLast(const Type& newItem); //Function to insert newItem at the end of the list. //Postcondition: first points to the new list, newItem // is inserted at the end of the list, // last points to the last node in the // list, and count is incremented by 1.
void deleteNode(const Type& deleteItem); //Function to delete deleteItem from the list. //Postcondition: If found, the node containing // deleteItem is deleted from the list. // first points to the first node, last // points to the last node of the updated // list, and count is decremented by 1. };
template
while (current != nullptr && !found) //search the list if (current->info == searchItem) //searchItem is found found = true; else current = current->link; //make current point to //the next node return found; }//end search
template
newNode = new nodeType
newNode->info = newItem; //store the new item in the node newNode->link = this->first; //insert newNode before first this->first = newNode; //make first point to the //actual first node this->count++; //increment count
if (this->last == nullptr) //if the list was empty, newNode is also //the last node in the list this->last = newNode; }//end insertFirst
template
newNode = new nodeType
newNode->info = newItem; //store the new item in the node newNode->link = nullptr; //set the link field of newNode //to nullptr
if (this->first == nullptr) //if the list is empty, newNode is //both the first and last node { this->first = newNode; this->last = newNode; this->count++; //increment count } else //the list is not empty, insert newNode after last { this->last->link = newNode; //insert newNode after last this->last = newNode; //make last point to the actual //last node in the list this->count++; //increment count } }//end insertLast
template
if (this->first == nullptr) //Case 1; the list is empty. cout first->info == deleteItem) //Case 2 { current = this->first; this->first = this->first->link; this->count--; if (this->first == nullptr) //the list has only one node this->last = nullptr; delete current; } else //search the list for the node with the given info { found = false; trailCurrent = this->first; //set trailCurrent to point //to the first node current = this->first->link; //set current to point to //the second node
while (current != nullptr && !found) { if (current->info != deleteItem) { trailCurrent = current; current = current-> link; } else found = true; }//end while
if (found) //Case 3; if found, delete the node { trailCurrent->link = current->link; this->count--;
if (this->last == current) /ode to be deleted //was the last node this->last = trailCurrent; //update the value //of last delete current; //delete the node from the list } else cout
#endif /* UNORDEREDLINKEDLIST_H */
------------------------------------------------------------------
------------------------------------------------------------------
queueADT.h:
#ifndef QUEUEADT_H #define QUEUEADT_H
template
virtual bool isFullQueue() const = 0; //Function to determine whether the queue is full. //Postcondition: Returns true if the queue is full, // otherwise returns false.
virtual void initializeQueue() = 0; //Function to initialize the queue to an empty state. //Postcondition: The queue is empty.
virtual Type front() const = 0; //Function to return the first element of the queue. //Precondition: The queue exists and is not empty. //Postcondition: If the queue is empty, the program // terminates; otherwise, the first // element of the queue is returned.
virtual Type back() const = 0; //Function to return the last element of the queue. //Precondition: The queue exists and is not empty. //Postcondition: If the queue is empty, the program // terminates; otherwise, the last // element of the queue is returned.
virtual void addQueue(const Type& queueElement) = 0; //Function to add queueElement to the queue. //Precondition: The queue exists and is not full. //Postcondition: The queue is changed and queueElement // is added to the queue.
virtual void deleteQueue() = 0; //Function to remove the first element of the queue. //Precondition: The queue exists and is not empty. //Postcondition: The queue is changed and the first // element is removed from the queue. };
#endif /* QUEUEADT_H */
---------------------------------------------------
---------------------------------------------------
linkedQueue.h:
#ifndef LINKEDQUEUE_H
#define LINKEDQUEUE_H
#include
#include
#include "queueADT.h"
using namespace std;
//Definition of the node
template
struct nodeType
{
Type info;
nodeType
};
template
class linkedQueueType: public queueADT
{
public:
const linkedQueueType
(const linkedQueueType
//Overload the assignment operator.
bool isEmptyQueue() const;
//Function to determine whether the queue is empty.
//Postcondition: Returns true if the queue is empty,
// otherwise returns false.
bool isFullQueue() const;
//Function to determine whether the queue is full.
//Postcondition: Returns true if the queue is full,
// otherwise returns false.
void initializeQueue();
//Function to initialize the queue to an empty state.
//Postcondition: queueFront = nullptr; queueRear = nullptr
Type front() const;
//Function to return the first element of the queue.
//Precondition: The queue exists and is not empty.
//Postcondition: If the queue is empty, the program
// terminates; otherwise, the first
// element of the queue is returned.
Type back() const;
//Function to return the last element of the queue.
//Precondition: The queue exists and is not empty.
//Postcondition: If the queue is empty, the program
// terminates; otherwise, the last
// element of the queue is returned.
void addQueue(const Type& queueElement);
//Function to add queueElement to the queue.
//Precondition: The queue exists and is not full.
//Postcondition: The queue is changed and queueElement
// is added to the queue.
void deleteQueue();
//Function to remove the first element of the queue.
//Precondition: The queue exists and is not empty.
//Postcondition: The queue is changed and the first
// element is removed from the queue.
linkedQueueType();
//Default constructor
linkedQueueType(const linkedQueueType
//Copy constructor
~linkedQueueType();
//Destructor
private:
nodeType
//the queue
nodeType
//the queue
};
//Default constructor
template
linkedQueueType
{
queueFront = nullptr; //set front to nullptr
queueRear = nullptr; //set rear to nullptr
} //end default constructor
template
bool linkedQueueType
{
return (queueFront == nullptr);
} //end isEmptyQueue
template
bool linkedQueueType
{
return false;
} //end isFullQueue
template
void linkedQueueType
{
nodeType
while (queueFront!= nullptr) //while there are elements
//left in the queue
{
temp = queueFront; //set temp to point to the
//current node
queueFront = queueFront->link; //advance first to
//the next node
delete temp; //deallocate memory occupied by temp
}
queueRear = nullptr; //set rear to nullptr
} //end initializeQueue
template
void linkedQueueType
{
nodeType
newNode = new nodeType
newNode->info = newElement; //store the info
newNode->link = nullptr; //initialize the link
//field to nullptr
if (queueFront == nullptr) //if initially the queue is empty
{
queueFront = newNode;
queueRear = newNode;
}
else //add newNode at the end
{
queueRear->link = newNode;
queueRear = queueRear->link;
}
}//end addQueue
template
Type linkedQueueType
{
assert(queueFront != nullptr);
return queueFront->info;
} //end front
template
Type linkedQueueType
{
assert(queueRear!= nullptr);
return queueRear->info;
} //end back
template
void linkedQueueType
{
nodeType
if (!isEmptyQueue())
{
temp = queueFront; //make temp point to the
//first node
queueFront = queueFront->link; //advance queueFront
delete temp; //delete the first node
if (queueFront == nullptr) //if after deletion the
//queue is empty
queueRear = nullptr; //set queueRear to nullptr
}
else
cout
}//end deleteQueue
//Destructor
template
linkedQueueType
{
//Write the definition of the destructor
} //end destructor
template
const linkedQueueType
(const linkedQueueType
{
//Write the definition of to overload the assignment operator
} //end assignment operator
//copy constructor
template
linkedQueueType
(const linkedQueueType
{
//Write the definition of the copy constructor
}//end copy constructor
#endif /* LINKEDQUEUE_H */
--------------------------------------------------------
--------------------------------------------------------
graphType.h:
#ifndef GRAPHTYPE_H
#define GRAPHTYPE_H
#include
#include
#include
#include "linkedList.h"
#include "unorderedLinkedList.h"
#include "linkedQueue.h"
using namespace std;
class graphType
{
public:
bool isEmpty() const;
//Function to determine whether the graph is empty.
//Postcondition: Returns true if the graph is empty;
// otherwise, returns false.
void createGraph();
//Function to create a graph.
//Postcondition: The graph is created using the
// adjacency list representation.
void clearGraph();
//Function to clear graph.
//Postcondition: The memory occupied by each vertex
// is deallocated.
void printGraph() const;
//Function to print graph.
//Postcondition: The graph is printed.
void depthFirstTraversal();
//Function to perform the depth first traversal of
//the entire graph.
//Postcondition: The vertices of the graph are printed
// using depth first traversal algorithm.
void dftAtVertex(int vertex);
//Function to perform the depth first traversal of
//the graph at a node specified by the parameter vertex.
//Postcondition: Starting at vertex, the vertices are
// printed using depth first traversal
// algorithm.
void breadthFirstTraversal();
//Function to perform the breadth first traversal of
//the entire graph.
//Postcondition: The vertices of the graph are printed
// using breadth first traversal algorithm.
graphType(int size = 0);
//Constructor
//Postcondition: gSize = 0; maxSize = size;
// graph is an array of pointers to linked
// lists.
~graphType();
//Destructor
//The storage occupied by the vertices is deallocated.
protected:
int maxSize; //maximum number of vertices
int gSize; //current number of vertices
unorderedLinkedList
//adjacency lists
private:
void dft(int v, bool visited[]);
//Function to perform the depth first traversal of
//the graph at a node specified by the parameter vertex.
//This function is used by the public member functions
//depthFirstTraversal and dftAtVertex.
//Postcondition: Starting at vertex, the vertices are
// printed using depth first traversal
// algorithm.
};
bool graphType::isEmpty() const
{
return (gSize == 0);
}
void graphType::createGraph()
{
ifstream infile;
char fileName[50];
int index;
int vertex;
int adjacentVertex;
if (gSize != 0) //if the graph is not empty, make it empty
clearGraph();
cout
cin >> fileName;
cout
infile.open(fileName);
if (!infile)
{
cout
return;
}
infile >> gSize; //get the number of vertices
for (index = 0; index
{
infile >> vertex;
infile >> adjacentVertex;
while (adjacentVertex != -999)
{
graph[vertex].insertLast(adjacentVertex);
infile >> adjacentVertex;
} //end while
} // end for
infile.close();
} //end createGraph
void graphType::clearGraph()
{
int index;
for (index = 0; index
graph[index].destroyList();
gSize = 0;
} //end clearGraph
void graphType::printGraph() const
{
int index;
for (index = 0; index
{
cout
graph[index].print();
cout
}
cout
} //end printGraph
void graphType::depthFirstTraversal()
{
bool *visited; //pointer to create the array to keep
//track of the visited vertices
visited = new bool[gSize];
int index;
for (index = 0; index
visited[index] = false;
//For each vertex that is not visited, do a depth
//first traverssal
for (index = 0; index
if (!visited[index])
dft(index,visited);
delete [] visited;
} //end depthFirstTraversal
void graphType::dft(int v, bool visited[])
{
visited[v] = true;
cout
linkedListIterator
//for each vertex adjacent to v
for (graphIt = graph[v].begin(); graphIt != graph[v].end();
++graphIt)
{
int w = *graphIt;
if (!visited[w])
dft(w, visited);
} //end while
} //end dft
void graphType::dftAtVertex(int vertex)
{
bool *visited;
visited = new bool[gSize];
for (int index = 0; index
visited[index] = false;
dft(vertex, visited);
delete [] visited;
} // end dftAtVertex
void graphType::breadthFirstTraversal()
{
linkedQueueType
bool *visited;
visited = new bool[gSize];
for (int ind = 0; ind
visited[ind] = false; //initialize the array
//visited to false
linkedListIterator
for (int index = 0; index
if (!visited[index])
{
queue.addQueue(index);
visited[index] = true;
cout
while (!queue.isEmptyQueue())
{
int u = queue.front();
queue.deleteQueue();
for (graphIt = graph[u].begin();
graphIt != graph[u].end(); ++graphIt)
{
int w = *graphIt;
if (!visited[w])
{
queue.addQueue(w);
visited[w] = true;
cout
}
}
} //end while
}
delete [] visited;
} //end breadthFirstTraversal
//Constructor
graphType::graphType(int size)
{
maxSize = size;
gSize = 0;
graph = new unorderedLinkedList
}
//Destructor
graphType::~graphType()
{
clearGraph();
}
#endif /* GRAPHTYPE_H */
-----------------------------------------------------------------------------------
-----------------------------------------------------------------------------------
weightedGraph.h:
#ifndef WEIGHTEDGRAPH_H
#define WEIGHTEDGRAPH_H
#include
#include
#include
#include
#include "graphType.h"
using namespace std;
class weightedGraphType: public graphType
{
public:
void createWeightedGraph();
//Function to create the graph and the weight matrix.
//Postcondition: The graph using adjacency lists and
// its weight matrix is created.
void shortestPath(int vertex);
//Function to determine the weight of a shortest path
//from vertex, that is, source, to every other vertex
//in the graph.
//Postcondition: The weight of the shortest path from
// vertex to every other vertex in the
// graph is determined.
void printShortestDistance(int vertex);
//Function to print the shortest weight from vertex
//to the other vertex in the graph.
//Postcondition: The weight of the shortest path from
// vertex to every other vertex in the
// graph is printed.
weightedGraphType(int size = 0);
//Constructor
//Postcondition: gSize = 0; maxSize = size;
// graph is an array of pointers to linked
// lists.
// weights is a two-dimensional array to
// store the weights of the edges.
// smallestWeight is an array to store the
// smallest weight from source to vertices.
~weightedGraphType();
//Destructor
//The storage occupied by the vertices and the arrays
//weights and smallestWeight is deallocated.
protected:
double **weights; //pointer to create weight matrix
double *smallestWeight; //pointer to create the array to
//store the smallest weight from
//source to vertices
};
void weightedGraphType::createWeightedGraph()
{
cout
} //createWeightedGraph
void weightedGraphType::shortestPath(int vertex)
{
for (int j = 0; j
smallestWeight[j] = weights[vertex][j];
bool *weightFound;
weightFound = new bool[gSize];
for (int j = 0; j
weightFound[j] = false;
weightFound[vertex] = true;
smallestWeight[vertex] = 0;
for (int i = 0; i
{
double minWeight = DBL_MAX;
int v;
for (int j = 0; j
if (!weightFound[j])
if (smallestWeight[j]
{
v = j;
minWeight = smallestWeight[v];
}
weightFound[v] = true;
for (int j = 0; j
if (!weightFound[j])
if (minWeight + weights[v][j]
smallestWeight[j] = minWeight + weights[v][j];
} //end for
} //end shortestPath
void weightedGraphType::printShortestDistance(int vertex)
{
cout
cout
cout
for (int j = 0; j
cout
cout
} //end printShortestDistance
//Constructor
weightedGraphType::weightedGraphType(int size)
:graphType(size)
{
weights = new double*[size];
for (int i = 0; i
weights[i] = new double[size];
smallestWeight = new double[size];
}
//Destructor
weightedGraphType::~weightedGraphType()
{
for (int i = 0; i
delete [] weights[i];
delete [] weights;
delete smallestWeight;
}
#endif /* WEIGHTEDGRAPH_H */
HOMEWORK #29-Shortest Path Algorithm Implement the weightedGraph.h derived template class to implement the shortest path algorithm, as outlined in Chapter 20 of Malik. Write a program that outputs the shortest distance from a given node to every other node in the graph. Create a data2.txt file with the following data for your program // Adjacency List 0 1 3 4 -999 1 2-999 2 1 -999 3 1 4 -999 4 1 2 3 -999 // Weight List // First column corresponds to the current vertex // Next entry is the destination vertex / Next entry is the weight // Next entry is the next destination vertex / Next entry is the next weight /7 Repeat until -999 // Row 0, Col 0: Source Vertex-0 / Row 0, Col 1: Destination Vertex0 // Row 0, Col 2: Weight0 // Row 0, Col 3: Destination Vertex1 // Row 0, Col 4: Weight16 Etc
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help