C++ Write a program that outputs the shortest distance from a given node to ever
ID: 666604 • Letter: C
Question
C++
Write a program that outputs the shortest distance from a given node to every other node in the graph. Program must use these files:
Ch20_Ex3.cpp give main program
graphType.h
linkedList.h
linkedQueue.h
queueADT.h
unorderedLinkedList.h
weightedGraph.h
I already have all these files BUT i have to build a function void weightedGraphType::createWeightedGraph() in weightedGraph.h . I JUST NEED HELP ABOUT THE FUNCTION createWeightedGraph() that's it.
I did the work but the function is not working properly: The Output Must look like This
My Output looks like This :
use notepad file name Ch20_Ex3Data.txt as input. file contains:
5
0 1 3 4 -999
1 2 -999
2 1 -999
3 1 4 -999
4 1 2 3 -999
0 0 0 1 16 3 2 4 3 -999
1 1 0 2 5 -999
2 1 3 2 0 -999
3 1 12 3 0 4 7 -999
4 1 10 2 4 3 5 4 0 -999
Main Program:'
#include <iostream>
#include <fstream>
#include "weightedGraph.h"
using namespace std;
int main()
{
weightedGraphType shortestPathGraph(50);
shortestPathGraph.createWeightedGraph();
shortestPathGraph.shortestPath(0);
shortestPathGraph.printShortestDistance(0);
cout << endl;
system("pause");
return 0;
}
THESE ARE ALL THE FILES :
#ifndef H_weightedGraph
#define H_weightedGraph
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cfloat>
#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()
{
ifstream infile;
char fileName[50];
int index;
int vertex;
int adjacentVertex;
if(gSize != 0)
clearGraph();
cout << "Enter input file name: ";
cin >> fileName;
cout << endl;
infile.open(fileName);
if(!infile)
{
cout << "Cannot open input file." << endl;
return;
}
infile >> gSize;
graph = new unorderedLinkedList<int>[gSize];
for(index = 0; index < gSize; index++)
{
infile >> vertex;
infile >> adjacentVertex;
while(adjacentVertex != -999)
{
graph[ vertex ].insertLast(adjacentVertex);
infile >> adjacentVertex;
}
}
infile.close();
?
} //createWeightedGraph
void weightedGraphType::shortestPath(int vertex)
{
for (int j = 0; j < gSize; j++)
smallestWeight[j] = weights[vertex][j];
bool *weightFound;
weightFound = new bool[gSize];
for (int j = 0; j < gSize; j++)
weightFound[j] = false;
weightFound[vertex] = true;
smallestWeight[vertex] = 0;
for (int i = 0; i < gSize - 1; i++)
{
double minWeight = DBL_MAX;
int v;
for (int j = 0; j < gSize; j++)
if (!weightFound[j])
if (smallestWeight[j] < minWeight)
{
v = j;
minWeight = smallestWeight[v];
}
weightFound[v] = true;
for (int j = 0; j < gSize; j++)
if (!weightFound[j])
if (minWeight + weights[v][j] < smallestWeight[j])
smallestWeight[j] = minWeight + weights[v][j];
} //end for
} //end shortestPath
void weightedGraphType::printShortestDistance(int vertex)
{
cout << "Source Vertex: " << vertex << endl;
cout << "Shortest Distance from Source to each Vertex."
<< endl;
cout << "Vertex Shortest_Distance" << endl;
for (int j = 0; j < gSize; j++)
cout << setw(4) << j << setw(12) << smallestWeight[j]
<< endl;
cout << endl;
} //end printShortestDistance
//Constructor
weightedGraphType::weightedGraphType(int size)
:graphType(size)
{
weights = new double*[size];
for (int i = 0; i < size; i++)
weights[i] = new double[size];
smallestWeight = new double[size];
}
//Destructor
weightedGraphType::~weightedGraphType()
{
for (int i = 0; i < gSize; i++)
delete [] weights[i];
delete [] weights;
delete smallestWeight;
}
#endif
#ifndef H_graph
#define H_graph
#include <iostream>
#include <fstream>
#include <iomanip>
#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<int> *graph; //array to create
//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 << "Enter input file name: ";
cin >> fileName;
cout << endl;
infile.open(fileName);
if (!infile)
{
cout << "Cannot open input file." << endl;
return;
}
infile >> gSize; //get the number of vertices
for (index = 0; index < gSize; 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 < gSize; index++)
graph[index].destroyList();
gSize = 0;
} //end clearGraph
?
void graphType::printGraph() const
{
int index;
for (index = 0; index < gSize; index++)
{
cout << index << " ";
graph[index].print();
cout << endl;
}
cout << endl;
} //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 < gSize; index++)
visited[index] = false;
//For each vertex that is not visited, do a depth
//first traverssal
for (index = 0; index < gSize; index++)
if (!visited[index])
dft(index,visited);
delete [] visited;
} //end depthFirstTraversal
void graphType::dft(int v, bool visited[])
{
visited[v] = true;
cout << " " << v << " "; //visit the vertex
linkedListIterator<int> graphIt;
//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 < gSize; index++)
visited[index] = false;
dft(vertex, visited);
delete [] visited;
} // end dftAtVertex
?
void graphType::breadthFirstTraversal()
{
linkedQueueType<int> queue;
bool *visited;
visited = new bool[gSize];
for (int ind = 0; ind < gSize; ind++)
visited[ind] = false; //initialize the array
//visited to false
linkedListIterator<int> graphIt;
for (int index = 0; index < gSize; index++)
if (!visited[index])
{
queue.addQueue(index);
visited[index] = true;
cout << " " << index << " ";
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 << " " << w << " ";
}
}
} //end while
}
delete [] visited;
} //end breadthFirstTraversal
//Constructor
graphType::graphType(int size)
{
maxSize = size;
gSize = 0;
graph = new unorderedLinkedList<int>[size];
}
//Destructor
graphType::~graphType()
{
clearGraph();
}
#endif
#ifndef H_LinkedListType
#define H_LinkedListType
#include <iostream>
#include <cassert>
using namespace std;
//Definition of the node
template <class Type>
struct nodeType
{
Type info;
nodeType<Type> *link;
};
template <class Type>
class linkedListIterator
{
public:
linkedListIterator();
//Default constructor
//Postcondition: current = NULL;
linkedListIterator(nodeType<Type> *ptr);
//Constructor with a parameter.
//Postcondition: current = ptr;
Type operator*();
//Function to overload the dereferencing operator *.
//Postcondition: Returns the info contained in the node.
linkedListIterator<Type> operator++();
//Overload the pre-increment operator.
//Postcondition: The iterator is advanced to the next
// node.
bool operator==(const linkedListIterator<Type>& right) const;
//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<Type>& right) const;
//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<Type> *current; //pointer to point to the current
//node in the linked list
};
template <class Type>
linkedListIterator<Type>::linkedListIterator()
{
current = NULL;
}
template <class Type>
linkedListIterator<Type>::
linkedListIterator(nodeType<Type> *ptr)
{
current = ptr;
}
template <class Type>
Type linkedListIterator<Type>::operator*()
{
return current->info;
}
template <class Type>
linkedListIterator<Type> linkedListIterator<Type>::operator++()
{
current = current->link;
return *this;
}
template <class Type>
bool linkedListIterator<Type>::operator==
(const linkedListIterator<Type>& right) const
{
return (current == right.current);
}
template <class Type>
bool linkedListIterator<Type>::operator!=
(const linkedListIterator<Type>& right) const
{ return (current != right.current);
}
?
//***************** class linkedListType ****************
template <class Type>
class linkedListType
{
public:
const linkedListType<Type>& operator=
(const linkedListType<Type>&);
//Overload the assignment operator.
void initializeList();
//Initialize the list to an empty state.
//Postcondition: first = NULL, last = NULL, 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 = NULL, last = NULL, 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<Type> begin();
//Function to return an iterator at the begining of the
//linked list.
//Postcondition: Returns an iterator such that current is
// set to first.
linkedListIterator<Type> end();
//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 NULL.
linkedListType();
//default constructor
//Initializes the list to an empty state.
//Postcondition: first = NULL, last = NULL, count = 0;
linkedListType(const linkedListType<Type>& otherList);
//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<Type> *first; //pointer to the first node of the list
nodeType<Type> *last; //pointer to the last node of the list
private:
void copyList(const linkedListType<Type>& otherList);
//Function to make a copy of otherList.
//Postcondition: A copy of otherList is created and
// assigned to this list.
};
?
template <class Type>
bool linkedListType<Type>::isEmptyList() const
{
return(first == NULL);
}
template <class Type>
linkedListType<Type>::linkedListType() //default constructor
{
first = NULL;
last = NULL;
count = 0;
}
template <class Type>
void linkedListType<Type>::destroyList()
{
nodeType<Type> *temp; //pointer to deallocate the memory
//occupied by the node
while (first != NULL) //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 = NULL; //initialize last to NULL; first has already
//been set to NULL by the while loop
count = 0;
}
template <class Type>
void linkedListType<Type>::initializeList()
{
destroyList(); //if the list has any nodes, delete them
}
template <class Type>
void linkedListType<Type>::print() const
{
nodeType<Type> *current; //pointer to traverse the list
current = first; //set current so that it points to
//the first node
while (current != NULL) //while more data to print
{
cout << current->info << " ";
current = current->link;
}
}//end print
template <class Type>
int linkedListType<Type>::length() const
{
return count;
} //end length
template <class Type>
Type linkedListType<Type>::front() const
{
assert(first != NULL);
return first->info; //return the info of the first node
}//end front
template <class Type>
Type linkedListType<Type>::back() const
{
assert(last != NULL);
return last->info; //return the info of the last node
}//end back
template <class Type>
linkedListIterator<Type> linkedListType<Type>::begin()
{
linkedListIterator<Type> temp(first);
return temp;
}
template <class Type>
linkedListIterator<Type> linkedListType<Type>::end()
{
linkedListIterator<Type> temp(NULL);
return temp;
}
template <class Type>
void linkedListType<Type>::copyList
(const linkedListType<Type>& otherList)
{
nodeType<Type> *newNode; //pointer to create a node
nodeType<Type> *current; //pointer to traverse the list
if (first != NULL) //if the list is nonempty, make it empty
destroyList();
if (otherList.first == NULL) //otherList is empty
{
first = NULL;
last = NULL;
count = 0;
}
else
{
current = otherList.first; //current points to the
//list to be copied
count = otherList.count;
//copy the first node
first = new nodeType<Type>; //create the node
first->info = current->info; //copy the info
first->link = NULL; //set the link field of
//the node to NULL
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 != NULL)
{
newNode = new nodeType<Type>; //create a node
newNode->info = current->info; //copy the info
newNode->link = NULL; //set the link of
//newNode to NULL
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 <class Type>
linkedListType<Type>::~linkedListType() //destructor
{
destroyList();
}//end destructor
template <class Type>
linkedListType<Type>::linkedListType
(const linkedListType<Type>& otherList)
{
first = NULL;
copyList(otherList);
}//end copy constructor
//overload the assignment operator
template <class Type>
const linkedListType<Type>& linkedListType<Type>::operator=
(const linkedListType<Type>& otherList)
{
if (this != &otherList) //avoid self-copy
{
copyList(otherList);
}//end else
return *this;
}
#endif
#ifndef H_UnorderedLinkedList
#define H_UnorderedLinkedList
#include "linkedList.h"
using namespace std;
template <class Type>
class unorderedLinkedList: public linkedListType<Type>
{
public:
bool search(const Type& searchItem) const;
//Function to determine whether searchItem is in the list.
//Postcondition: Returns true if searchItem is in the
// list, otherwise the value false is
// returned.
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 <class Type>
bool unorderedLinkedList<Type>::
search(const Type& searchItem) const
{
nodeType<Type> *current; //pointer to traverse the list
bool found = false;
current = first; //set current to point to the first
//node in the list
while (current != NULL && !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 <class Type>
void unorderedLinkedList<Type>::insertFirst(const Type& newItem)
{
nodeType<Type> *newNode; //pointer to create the new node
newNode = new nodeType<Type>; //create the new node
newNode->info = newItem; //store the new item in the node
newNode->link = first; //insert newNode before first
first = newNode; //make first point to the
//actual first node
count++; //increment count
if (last == NULL) //if the list was empty, newNode is also
//the last node in the list
last = newNode;
}//end insertFirst
template <class Type>
void unorderedLinkedList<Type>::insertLast(const Type& newItem)
{
nodeType<Type> *newNode; //pointer to create the new node
newNode = new nodeType<Type>; //create the new node
newNode->info = newItem; //store the new item in the node
newNode->link = NULL; //set the link field of newNode
//to NULL
if (first == NULL) //if the list is empty, newNode is
//both the first and last node
{
first = newNode;
last = newNode;
count++; //increment count
}
else //the list is not empty, insert newNode after last
{
last->link = newNode; //insert newNode after last
last = newNode; //make last point to the actual
//last node in the list
count++; //increment count
}
}//end insertLast
?
template <class Type>
void unorderedLinkedList<Type>::deleteNode(const Type& deleteItem)
{
nodeType<Type> *current; //pointer to traverse the list
nodeType<Type> *trailCurrent; //pointer just before current
bool found;
if (first == NULL) //Case 1; the list is empty.
cout << "Cannot delete from an empty list."
<< endl;
else
{
if (first->info == deleteItem) //Case 2
{
current = first;
first = first->link;
count--;
if (first == NULL) //the list has only one node
last = NULL;
delete current;
}
else //search the list for the node with the given info
{
found = false;
trailCurrent = first; //set trailCurrent to point
//to the first node
current = first->link; //set current to point to
//the second node
while (current != NULL && !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;
count--;
if (last == current) //node to be deleted
//was the last node
last = trailCurrent; //update the value
//of last
delete current; //delete the node from the list
}
else
cout << "The item to be deleted is not in "
<< "the list." << endl;
}//end else
}//end else
}//end deleteNode
?
#endif
//Header file linkedQueue.h
#ifndef H_linkedQueue
#define H_linkedQueue
#include <iostream>
#include <cassert>
#include "queueADT.h"
using namespace std;
template <class Type>
class linkedQueueType: public queueADT<Type>
{
public:
const linkedQueueType<Type>& operator=
(const linkedQueueType<Type>&);
//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 = NULL; queueRear = NULL
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<Type>& otherQueue);
//Copy constructor
~linkedQueueType();
//Destructor
private:
nodeType<Type> *queueFront; //pointer to the front of
//the queue
nodeType<Type> *queueRear; //pointer to the rear of
//the queue
};
//Default constructor
template<class Type>
linkedQueueType<Type>::linkedQueueType()
{
queueFront = NULL; //set front to null
queueRear = NULL; //set rear to null
} //end default constructor
template<class Type>
bool linkedQueueType<Type>::isEmptyQueue() const
{
return(queueFront == NULL);
} //end
template<class Type>
bool linkedQueueType<Type>::isFullQueue() const
{
return false;
} //end isFullQueue
template <class Type>
void linkedQueueType<Type>::initializeQueue()
{
nodeType<Type> *temp;
while (queueFront!= NULL) //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 = NULL; //set rear to NULL
} //end initializeQueue
?
template <class Type>
void linkedQueueType<Type>::addQueue(const Type& newElement)
{
nodeType<Type> *newNode;
newNode = new nodeType<Type>; //create the node
newNode->info = newElement; //store the info
newNode->link = NULL; //initialize the link field to NULL
if (queueFront == NULL) //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 <class Type>
Type linkedQueueType<Type>::front() const
{
assert(queueFront != NULL);
return queueFront->info;
} //end front
template <class Type>
Type linkedQueueType<Type>::back() const
{
assert(queueRear!= NULL);
return queueRear->info;
} //end back
template <class Type>
void linkedQueueType<Type>::deleteQueue()
{
nodeType<Type> *temp;
if (!isEmptyQueue())
{
temp = queueFront; //make temp point to the
//first node
queueFront = queueFront->link; //advance queueFront
delete temp; //delete the first node
if (queueFront == NULL) //if after deletion the
//queue is empty
queueRear = NULL; //set queueRear to NULL
}
else
cout << "Cannot remove from an empty queue" << endl;
}//end deleteQueue
?
//Destructor
template <class Type>
linkedQueueType<Type>::~linkedQueueType()
{
//Write the definition of the destructor
} //end destructor
template <class Type>
const linkedQueueType<Type>& linkedQueueType<Type>::operator=
(const linkedQueueType<Type>& otherQueue)
{
//Write the definition of to overload the assignment operator
} //end assignment operator
//copy constructor
template <class Type>
linkedQueueType<Type>::linkedQueueType
(const linkedQueueType<Type>& otherQueue)
{
//Write the definition of the copy constructor
}//end copy constructor
#endif
//Header file: stackADT.h
#ifndef H_queueADT
#define H_queueADT
template <class Type>
class queueADT
{
public:
virtual bool isEmptyQueue() const = 0;
//Function to determine whether the queue is empty.
//Postcondition: Returns true if the queue is empty,
// otherwise returns false.
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
C: Documents and Settings DonaldWy Documents ICSC161 Program Solutions ICh20 Ex31Ch.... Source Uertex: Shortest Distance from Source to each Uertex. Uertex Shortest Distance 2 3 4 10 7? 2 3 Press any key to continue . .Explanation / Answer
#ifndef H_weightedGraph
#define H_weightedGraph
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cfloat>
#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()
{
ifstream infile;
char fileName[50];
int index;
int vertex;
int adjacentVertex;
if(gSize != 0)
clearGraph();
cout << "Enter input file name: ";
cin >> fileName;
cout << endl;
infile.open(fileName);
if(!infile)
{
cout << "Cannot open input file." << endl;
return;
}
infile >> gSize;
graph = new unorderedLinkedList<int>[gSize];
for(index = 0; index < gSize; index++)
{
infile >> vertex;
infile >> adjacentVertex;
while(adjacentVertex != -999)
{
graph[ vertex ].insertLast(adjacentVertex);
infile >> adjacentVertex;
}
}
infile.close();
} //createWeightedGraph
void weightedGraphType::shortestPath(int vertex)
{
for (int j = 0; j < gSize; j++)
smallestWeight[j] = weights[vertex][j];
bool *weightFound;
weightFound = new bool[gSize];
for (int j = 0; j < gSize; j++)
weightFound[j] = false;
weightFound[vertex] = true;
smallestWeight[vertex] = 0;
for (int i = 0; i < gSize - 1; i++)
{
double minWeight = DBL_MAX;
int v;
for (int j = 0; j < gSize; j++)
if (!weightFound[j])
if (smallestWeight[j] < minWeight)
{
v = j;
minWeight = smallestWeight[v];
}
weightFound[v] = true;
for (int j = 0; j < gSize; j++)
if (!weightFound[j])
if (minWeight + weights[v][j] < smallestWeight[j])
smallestWeight[j] = minWeight + weights[v][j];
} //end for
} //end shortestPath
void weightedGraphType::printShortestDistance(int vertex)
{
cout << "Source Vertex: " << vertex << endl;
cout << "Shortest Distance from Source to each Vertex."
<< endl;
cout << "Vertex Shortest_Distance" << endl;
for (int j = 0; j < gSize; j++)
cout << setw(4) << j << setw(12) << smallestWeight[j]
<< endl;
cout << endl;
} //end printShortestDistance
//Constructor
weightedGraphType::weightedGraphType(int size)
:graphType(size)
{
weights = new double*[size];
for (int i = 0; i < size; i++)
weights[i] = new double[size];
smallestWeight = new double[size];
}
//Destructor
weightedGraphType::~weightedGraphType()
{
for (int i = 0; i < gSize; i++)
delete [] weights[i];
delete [] weights;
delete smallestWeight;
}
#endif
#ifndef H_graph
#define H_graph
#include <iostream>
#include <fstream>
#include <iomanip>
#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<int> *graph; //array to create
//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 << "Enter input file name: ";
cin >> fileName;
cout << endl;
infile.open(fileName);
if (!infile)
{
cout << "Cannot open input file." << endl;
return;
}
infile >> gSize; //get the number of vertices
for (index = 0; index < gSize; 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 < gSize; index++)
graph[index].destroyList();
gSize = 0;
} //end clearGraph
void graphType::printGraph() const
{
int index;
for (index = 0; index < gSize; index++)
{
cout << index << " ";
graph[index].print();
cout << endl;
}
cout << endl;
} //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 < gSize; index++)
visited[index] = false;
//For each vertex that is not visited, do a depth
//first traverssal
for (index = 0; index < gSize; index++)
if (!visited[index])
dft(index,visited);
delete [] visited;
} //end depthFirstTraversal
void graphType::dft(int v, bool visited[])
{
visited[v] = true;
cout << " " << v << " "; //visit the vertex
linkedListIterator<int> graphIt;
//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 < gSize; index++)
visited[index] = false;
dft(vertex, visited);
delete [] visited;
} // end dftAtVertex
void graphType::breadthFirstTraversal()
{
linkedQueueType<int> queue;
bool *visited;
visited = new bool[gSize];
for (int ind = 0; ind < gSize; ind++)
visited[ind] = false; //initialize the array
//visited to false
linkedListIterator<int> graphIt;
for (int index = 0; index < gSize; index++)
if (!visited[index])
{
queue.addQueue(index);
visited[index] = true;
cout << " " << index << " ";
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 << " " << w << " ";
}
}
} //end while
}
delete [] visited;
} //end breadthFirstTraversal
//Constructor
graphType::graphType(int size)
{
maxSize = size;
gSize = 0;
graph = new unorderedLinkedList<int>[size];
}
//Destructor
graphType::~graphType()
{
clearGraph();
}
#endif
#ifndef H_LinkedListType
#define H_LinkedListType
#include <iostream>
#include <cassert>
using namespace std;
//Definition of the node
template <class Type>
struct nodeType
{
Type info;
nodeType<Type> *link;
};
template <class Type>
class linkedListIterator
{
public:
linkedListIterator();
//Default constructor
//Postcondition: current = NULL;
linkedListIterator(nodeType<Type> *ptr);
//Constructor with a parameter.
//Postcondition: current = ptr;
Type operator*();
//Function to overload the dereferencing operator *.
//Postcondition: Returns the info contained in the node.
linkedListIterator<Type> operator++();
//Overload the pre-increment operator.
//Postcondition: The iterator is advanced to the next
// node.
bool operator==(const linkedListIterator<Type>& right) const;
//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<Type>& right) const;
//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<Type> *current; //pointer to point to the current
//node in the linked list
};
template <class Type>
linkedListIterator<Type>::linkedListIterator()
{
current = NULL;
}
template <class Type>
linkedListIterator<Type>::
linkedListIterator(nodeType<Type> *ptr)
{
current = ptr;
}
template <class Type>
Type linkedListIterator<Type>::operator*()
{
return current->info;
}
template <class Type>
linkedListIterator<Type> linkedListIterator<Type>::operator++()
{
current = current->link;
return *this;
}
template <class Type>
bool linkedListIterator<Type>::operator==
(const linkedListIterator<Type>& right) const
{
return (current == right.current);
}
template <class Type>
bool linkedListIterator<Type>::operator!=
(const linkedListIterator<Type>& right) const
{ return (current != right.current);
}
//***************** class linkedListType ****************
template <class Type>
class linkedListType
{
public:
const linkedListType<Type>& operator=
(const linkedListType<Type>&);
//Overload the assignment operator.
void initializeList();
//Initialize the list to an empty state.
//Postcondition: first = NULL, last = NULL, 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 = NULL, last = NULL, 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<Type> begin();
//Function to return an iterator at the begining of the
//linked list.
//Postcondition: Returns an iterator such that current is
// set to first.
linkedListIterator<Type> end();
//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 NULL.
linkedListType();
//default constructor
//Initializes the list to an empty state.
//Postcondition: first = NULL, last = NULL, count = 0;
linkedListType(const linkedListType<Type>& otherList);
//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<Type> *first; //pointer to the first node of the list
nodeType<Type> *last; //pointer to the last node of the list
private:
void copyList(const linkedListType<Type>& otherList);
//Function to make a copy of otherList.
//Postcondition: A copy of otherList is created and
// assigned to this list.
};
template <class Type>
bool linkedListType<Type>::isEmptyList() const
{
return(first == NULL);
}
template <class Type>
linkedListType<Type>::linkedListType() //default constructor
{
first = NULL;
last = NULL;
count = 0;
}
template <class Type>
void linkedListType<Type>::destroyList()
{
nodeType<Type> *temp; //pointer to deallocate the memory
//occupied by the node
while (first != NULL) //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 = NULL; //initialize last to NULL; first has already
//been set to NULL by the while loop
count = 0;
}
template <class Type>
void linkedListType<Type>::initializeList()
{
destroyList(); //if the list has any nodes, delete them
}
template <class Type>
void linkedListType<Type>::print() const
{
nodeType<Type> *current; //pointer to traverse the list
current = first; //set current so that it points to
//the first node
while (current != NULL) //while more data to print
{
cout << current->info << " ";
current = current->link;
}
}//end print
template <class Type>
int linkedListType<Type>::length() const
{
return count;
} //end length
template <class Type>
Type linkedListType<Type>::front() const
{
assert(first != NULL);
return first->info; //return the info of the first node
}//end front
template <class Type>
Type linkedListType<Type>::back() const
{
assert(last != NULL);
return last->info; //return the info of the last node
}//end back
template <class Type>
linkedListIterator<Type> linkedListType<Type>::begin()
{
linkedListIterator<Type> temp(first);
return temp;
}
template <class Type>
linkedListIterator<Type> linkedListType<Type>::end()
{
linkedListIterator<Type> temp(NULL);
return temp;
}
template <class Type>
void linkedListType<Type>::copyList
(const linkedListType<Type>& otherList)
{
nodeType<Type> *newNode; //pointer to create a node
nodeType<Type> *current; //pointer to traverse the list
if (first != NULL) //if the list is nonempty, make it empty
destroyList();
if (otherList.first == NULL) //otherList is empty
{
first = NULL;
last = NULL;
count = 0;
}
else
{
current = otherList.first; //current points to the
//list to be copied
count = otherList.count;
//copy the first node
first = new nodeType<Type>; //create the node
first->info = current->info; //copy the info
first->link = NULL; //set the link field of
//the node to NULL
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 != NULL)
{
newNode = new nodeType<Type>; //create a node
newNode->info = current->info; //copy the info
newNode->link = NULL; //set the link of
//newNode to NULL
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 <class Type>
linkedListType<Type>::~linkedListType() //destructor
{
destroyList();
}//end destructor
template <class Type>
linkedListType<Type>::linkedListType
(const linkedListType<Type>& otherList)
{
first = NULL;
copyList(otherList);
}//end copy constructor
//overload the assignment operator
template <class Type>
const linkedListType<Type>& linkedListType<Type>::operator=
(const linkedListType<Type>& otherList)
{
if (this != &otherList) //avoid self-copy
{
copyList(otherList);
}//end else
return *this;
}
#endif
#ifndef H_UnorderedLinkedList
#define H_UnorderedLinkedList
#include "linkedList.h"
using namespace std;
template <class Type>
class unorderedLinkedList: public linkedListType<Type>
{
public:
bool search(const Type& searchItem) const;
//Function to determine whether searchItem is in the list.
//Postcondition: Returns true if searchItem is in the
// list, otherwise the value false is
// returned.
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 <class Type>
bool unorderedLinkedList<Type>::
search(const Type& searchItem) const
{
nodeType<Type> *current; //pointer to traverse the list
bool found = false;
current = first; //set current to point to the first
//node in the list
while (current != NULL && !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 <class Type>
void unorderedLinkedList<Type>::insertFirst(const Type& newItem)
{
nodeType<Type> *newNode; //pointer to create the new node
newNode = new nodeType<Type>; //create the new node
newNode->info = newItem; //store the new item in the node
newNode->link = first; //insert newNode before first
first = newNode; //make first point to the
//actual first node
count++; //increment count
if (last == NULL) //if the list was empty, newNode is also
//the last node in the list
last = newNode;
}//end insertFirst
template <class Type>
void unorderedLinkedList<Type>::insertLast(const Type& newItem)
{
nodeType<Type> *newNode; //pointer to create the new node
newNode = new nodeType<Type>; //create the new node
newNode->info = newItem; //store the new item in the node
newNode->link = NULL; //set the link field of newNode
//to NULL
if (first == NULL) //if the list is empty, newNode is
//both the first and last node
{
first = newNode;
last = newNode;
count++; //increment count
}
else //the list is not empty, insert newNode after last
{
last->link = newNode; //insert newNode after last
last = newNode; //make last point to the actual
//last node in the list
count++; //increment count
}
}//end insertLast
template <class Type>
void unorderedLinkedList<Type>::deleteNode(const Type& deleteItem)
{
nodeType<Type> *current; //pointer to traverse the list
nodeType<Type> *trailCurrent; //pointer just before current
bool found;
if (first == NULL) //Case 1; the list is empty.
cout << "Cannot delete from an empty list."
<< endl;
else
{
if (first->info == deleteItem) //Case 2
{
current = first;
first = first->link;
count--;
if (first == NULL) //the list has only one node
last = NULL;
delete current;
}
else //search the list for the node with the given info
{
found = false;
trailCurrent = first; //set trailCurrent to point
//to the first node
current = first->link; //set current to point to
//the second node
while (current != NULL && !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;
count--;
if (last == current) //node to be deleted
//was the last node
last = trailCurrent; //update the value
//of last
delete current; //delete the node from the list
}
else
cout << "The item to be deleted is not in "
<< "the list." << endl;
}//end else
}//end else
}//end deleteNode
#endif
//Header file linkedQueue.h
#ifndef H_linkedQueue
#define H_linkedQueue
#include <iostream>
#include <cassert>
#include "queueADT.h"
using namespace std;
template <class Type>
class linkedQueueType: public queueADT<Type>
{
public:
const linkedQueueType<Type>& operator=
(const linkedQueueType<Type>&);
//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 = NULL; queueRear = NULL
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<Type>& otherQueue);
//Copy constructor
~linkedQueueType();
//Destructor
private:
nodeType<Type> *queueFront; //pointer to the front of
//the queue
nodeType<Type> *queueRear; //pointer to the rear of
//the queue
};
//Default constructor
template<class Type>
linkedQueueType<Type>::linkedQueueType()
{
queueFront = NULL; //set front to null
queueRear = NULL; //set rear to null
} //end default constructor
template<class Type>
bool linkedQueueType<Type>::isEmptyQueue() const
{
return(queueFront == NULL);
} //end
template<class Type>
bool linkedQueueType<Type>::isFullQueue() const
{
return false;
} //end isFullQueue
template <class Type>
void linkedQueueType<Type>::initializeQueue()
{
nodeType<Type> *temp;
while (queueFront!= NULL) //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 = NULL; //set rear to NULL
} //end initializeQueue
template <class Type>
void linkedQueueType<Type>::addQueue(const Type& newElement)
{
nodeType<Type> *newNode;
newNode = new nodeType<Type>; //create the node
newNode->info = newElement; //store the info
newNode->link = NULL; //initialize the link field to NULL
if (queueFront == NULL) //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 <class Type>
Type linkedQueueType<Type>::front() const
{
assert(queueFront != NULL);
return queueFront->info;
} //end front
template <class Type>
Type linkedQueueType<Type>::back() const
{
assert(queueRear!= NULL);
return queueRear->info;
} //end back
template <class Type>
void linkedQueueType<Type>::deleteQueue()
{
nodeType<Type> *temp;
if (!isEmptyQueue())
{
temp = queueFront; //make temp point to the
//first node
queueFront = queueFront->link; //advance queueFront
delete temp; //delete the first node
if (queueFront == NULL) //if after deletion the
//queue is empty
queueRear = NULL; //set queueRear to NULL
}
else
cout << "Cannot remove from an empty queue" << endl;
}//end deleteQueue
//Destructor
template <class Type>
linkedQueueType<Type>::~linkedQueueType()
{
//Write the definition of the destructor
} //end destructor
template <class Type>
const linkedQueueType<Type>& linkedQueueType<Type>::operator=
(const linkedQueueType<Type>& otherQueue)
{
//Write the definition of to overload the assignment operator
} //end assignment operator
//copy constructor
template <class Type>
linkedQueueType<Type>::linkedQueueType
(const linkedQueueType<Type>& otherQueue)
{
//Write the definition of the copy constructor
}//end copy constructor
#endif
//Header file: stackADT.h
#ifndef H_queueADT
#define H_queueADT
template <class Type>
class queueADT
{
public:
virtual bool isEmptyQueue() const = 0;
//Function to determine whether the queue is empty.
//Postcondition: Returns true if the queue is empty,
// otherwise returns false.
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.
};
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.