data structure lab 1
ahmeddxn7
CSC240_GraphType.zipCSC240_GraphType/.cproject
CSC240_GraphType/.project
CSC240_Test2 org.eclipse.cdt.managedbuilder.core.genmakebuilder clean,full,incremental, org.eclipse.cdt.managedbuilder.core.ScannerConfigBuilder full,incremental, org.eclipse.cdt.core.cnature org.eclipse.cdt.core.ccnature org.eclipse.cdt.managedbuilder.core.managedBuildNature org.eclipse.cdt.managedbuilder.core.ScannerConfigNature
CSC240_GraphType/.settings/language.settings.xml
CSC240_GraphType/.settings/org.eclipse.cdt.managedbuilder.core.prefs
eclipse.preferences.version=1 environment/buildEnvironmentInclude/cdt.managedbuild.config.gnu.mingw.exe.debug.1042118174/CPATH/delimiter=; environment/buildEnvironmentInclude/cdt.managedbuild.config.gnu.mingw.exe.debug.1042118174/CPATH/operation=remove environment/buildEnvironmentInclude/cdt.managedbuild.config.gnu.mingw.exe.debug.1042118174/CPLUS_INCLUDE_PATH/delimiter=; environment/buildEnvironmentInclude/cdt.managedbuild.config.gnu.mingw.exe.debug.1042118174/CPLUS_INCLUDE_PATH/operation=remove environment/buildEnvironmentInclude/cdt.managedbuild.config.gnu.mingw.exe.debug.1042118174/C_INCLUDE_PATH/delimiter=; environment/buildEnvironmentInclude/cdt.managedbuild.config.gnu.mingw.exe.debug.1042118174/C_INCLUDE_PATH/operation=remove environment/buildEnvironmentInclude/cdt.managedbuild.config.gnu.mingw.exe.debug.1042118174/append=true environment/buildEnvironmentInclude/cdt.managedbuild.config.gnu.mingw.exe.debug.1042118174/appendContributed=true environment/buildEnvironmentLibrary/cdt.managedbuild.config.gnu.mingw.exe.debug.1042118174/LIBRARY_PATH/delimiter=; environment/buildEnvironmentLibrary/cdt.managedbuild.config.gnu.mingw.exe.debug.1042118174/LIBRARY_PATH/operation=remove environment/buildEnvironmentLibrary/cdt.managedbuild.config.gnu.mingw.exe.debug.1042118174/append=true environment/buildEnvironmentLibrary/cdt.managedbuild.config.gnu.mingw.exe.debug.1042118174/appendContributed=true
CSC240_GraphType/CSC240_Test2.exe.stackdump
Exception: STATUS_ACCESS_VIOLATION at eip=6C6DD034 eax=A4B0CEE8 ebx=A4B0CEE8 ecx=00000018 edx=2003AA6C esi=20042C11 edi=611D7DB2 ebp=00637C88 esp=00637C6C program=C:\Users\igt88\eclipseOxygen\CSC240_Test2\Debug\CSC240_Test2.exe, pid 16412, thread main cs=0023 ds=002B es=002B fs=0053 gs=002B ss=002B Stack trace: Frame Function Args 00637C88 6C6DD034 (00637CB0, 0063A4EC, 0063A4E8, 00000003) 0063CC18 00402159 (00000001, 0063CC3C, 2003A788, 610079DA) 0063CD18 61007A3F (00000000, 0063CD74, 61006A70, 00000000) End of stack trace
CSC240_GraphType/Debug/CSC240_Test2.exe
CSC240_GraphType/Debug/src/CSC240_Test2.o
CSC240_GraphType/src/CSC240_Test2.cpp
CSC240_GraphType/src/CSC240_Test2.cpp
//============================================================================
// Name : CSC240_Test2.cpp
// Author : Ivan Temesvari
// Date : 4/19/19
// Description : CSC 240 Test 2 code
//============================================================================
#include
"GraphType.h"
#include
<
iostream
>
using
namespace
std
;
void
Func
(
int
n
){
if
(
n
>
0
){
Func
(
n
/
5
);
cout
<<
n
%
5
;
}
}
int
main
()
{
//Func(73);
GraphType
<
string
>
myGraph
(
10
);
myGraph
.
AddVertex
(
"A"
);
myGraph
.
AddVertex
(
"B"
);
myGraph
.
AddVertex
(
"C"
);
myGraph
.
AddVertex
(
"D"
);
myGraph
.
AddVertex
(
"E"
);
myGraph
.
AddVertex
(
"F"
);
myGraph
.
AddVertex
(
"G"
);
myGraph
.
AddEdge
(
"A"
,
"B"
,
1
);
myGraph
.
AddEdge
(
"A"
,
"G"
,
2
);
myGraph
.
AddEdge
(
"A"
,
"C"
,
3
);
myGraph
.
AddEdge
(
"C"
,
"A"
,
3
);
myGraph
.
AddEdge
(
"C"
,
"D"
,
3
);
myGraph
.
AddEdge
(
"C"
,
"G"
,
1
);
myGraph
.
AddEdge
(
"B"
,
"A"
,
1
);
myGraph
.
AddEdge
(
"G"
,
"A"
,
2
);
myGraph
.
AddEdge
(
"G"
,
"C"
,
1
);
myGraph
.
AddEdge
(
"G"
,
"F"
,
2
);
myGraph
.
AddEdge
(
"F"
,
"G"
,
2
);
myGraph
.
AddEdge
(
"F"
,
"E"
,
1
);
myGraph
.
AddEdge
(
"F"
,
"D"
,
1
);
myGraph
.
AddEdge
(
"D"
,
"C"
,
3
);
string vertexStart
=
"A"
;
string vertexEnd
=
"E"
;
DepthFirstSearch
(
myGraph
,
vertexStart
,
vertexEnd
);
return
0
;
}
CSC240_GraphType/src/GraphType.h
#ifndef GRAPH_TYPE #define GRAPH_TYPE #include <iostream> #include "QueType.h" #include "StackType.h" using namespace std; const string NULL_EDGE = "-"; // "-" represents infinity "\u221E" template<class VertexType> // Assumption: VertexType is a type for which the "=", // "==", and "<<" operators are defined class GraphType { public: GraphType(); // Default of 50 vertices GraphType(int maxV); // maxV <= 50 ~GraphType(); string getEdge(int, int); void setEdge(int, int, string); void AddVertex(VertexType); void AddEdge(VertexType, VertexType, int); int WeightIs(VertexType, VertexType); void GetToVertices(VertexType, QueType<VertexType>&); void ClearMarks(); void MarkVertex(VertexType); bool IsMarked(VertexType); template <class VType> friend ostream& operator<<(ostream&, GraphType<VType>&); int getNumVertices(); private: int numVertices; int maxVertices; VertexType* vertices; string edges[50][50]; bool* marks; // marks[i] is mark for vertices[i]. }; template<class VertexType> GraphType<VertexType>::GraphType() // Post: Arrays of size 50 are dynamically allocated for // marks and vertices. numVertices is set to 0; // maxVertices is set to 50. { numVertices = 0; maxVertices = 50; vertices = new VertexType[50]; marks = new bool[50]; for(int r = 0; r < maxVertices; r++){ for(int c = 0; c < maxVertices; c++){ if(r == c) edges[r][c] = "0"; else edges[r][c] = NULL_EDGE; } } } template<class VertexType> GraphType<VertexType>::GraphType(int maxV) // Post: Arrays of size maxV are dynamically allocated for // marks and vertices. // numVertices is set to 0; maxVertices is set to maxV. { numVertices = 0; maxVertices = maxV; vertices = new VertexType[maxV]; marks = new bool[maxV]; for(int r = 0; r < maxVertices; r++){ for(int c = 0; c < maxVertices; c++){ if(r == c) edges[r][c] = "0"; else edges[r][c] = NULL_EDGE; } } } template<class VertexType> // Post: arrays for vertices and marks have been deallocated. GraphType<VertexType>::~GraphType() { delete [] vertices; delete [] marks; } template<class VertexType> string GraphType<VertexType>::getEdge(int row, int col){ return edges[row][col]; } template<class VertexType> void GraphType<VertexType>::setEdge(int row, int col, string n){ edges[row][col] = n; } template <class VertexType> int GraphType<VertexType>::getNumVertices(){ return numVertices; } template<class VertexType> void GraphType<VertexType>::AddVertex(VertexType vertex) // Post: vertex has been stored in vertices. // Corresponding row and column of edges has been set // to NULL_EDGE. // numVertices has been incremented. { vertices[numVertices] = vertex; for (int index = 0; index < numVertices; index++) { edges[numVertices][index] = NULL_EDGE; edges[index][numVertices] = NULL_EDGE; } numVertices++; } template<class VertexType> int IndexIs(VertexType* vertices, VertexType vertex) // Post: Returns the index of vertex in vertices. { int index = 0; while (!(vertex == vertices[index])) index++; return index; } template<class VertexType> void GraphType<VertexType>::AddEdge(VertexType fromVertex, VertexType toVertex, int weight) // Post: Edge (fromVertex, toVertex) is stored in edges. { int row; int col; row = IndexIs(vertices, fromVertex); col = IndexIs(vertices, toVertex); edges[row][col] = std::to_string(weight); } template<class VertexType> int GraphType<VertexType>::WeightIs (VertexType fromVertex, VertexType toVertex) // Post: Returns the weight associated with the edge // (fromVertex, toVertex). { int row; int col; row = IndexIs(vertices, fromVertex); col = IndexIs(vertices, toVertex); return edges[row][col]; } template<class VertexType> void GraphType<VertexType>::GetToVertices(VertexType vertex, QueType<VertexType>& adjVertices) // Post: { int fromIndex; int toIndex; fromIndex = IndexIs(vertices, vertex); for (toIndex = 0; toIndex < numVertices; toIndex++) if (edges[fromIndex][toIndex] != NULL_EDGE) adjVertices.Enqueue(vertices[toIndex]); } //IT 5/1/2019 template<class VertexType> void GraphType<VertexType>::ClearMarks(){ for(int index = 0; index < numVertices; index++) marks[index] = false; } //IT 5/1/2019 template<class VertexType> void GraphType<VertexType>::MarkVertex(VertexType vertex){ for(int index = 0; index < numVertices; index++){ if(vertices[index] == vertex){ marks[index] = true; break; } } } //IT 5/1/2019 template<class VertexType> bool GraphType<VertexType>::IsMarked(VertexType vertex){ int markedIndex = 0; for(; markedIndex < numVertices; markedIndex++){ if(vertices[markedIndex] == vertex){ if(marks[markedIndex] == true){ return true; } else{ return false; } } } return false; } template<class VertexType> void DepthFirstSearch(GraphType<VertexType>& graph, VertexType startVertex, VertexType endVertex) // Assumes VertexType is a type for which the == and "<<" // operators are defined { StackType<VertexType> stack; QueType<VertexType> vertexQ; bool found = false; VertexType vertex; VertexType item; graph.ClearMarks(); stack.Push(startVertex); do { stack.Pop(vertex); if (vertex == endVertex) { cout << vertex; found = true; } else { if (!graph.IsMarked(vertex)) { graph.MarkVertex(vertex); cout << vertex; graph.GetToVertices(vertex, vertexQ); while (!vertexQ.IsEmpty()) { vertexQ.Dequeue(item); if (!graph.IsMarked(item)) stack.Push(item); } } } } while (!stack.IsEmpty() && !found); if(found) cout << "\nPath is found." << endl; else cout << "\nPath not found." << endl; } template<class VertexType> void BreadthFirstSearch(GraphType<VertexType>& graph, VertexType startVertex, VertexType endVertex) // Assumption: VertexType is a type for which the Ò==Ò and // "<<" operators are defined. { using namespace std; QueType<VertexType> queue; QueType<VertexType> vertexQ; bool found = false; VertexType vertex; VertexType item; graph.ClearMarks(); queue.Enqueue(startVertex); do { queue.Dequeue(vertex); if (vertex == endVertex) { cout << vertex; found = true; } else { if (!graph.IsMarked(vertex)) { graph.MarkVertex(vertex); cout << vertex; graph.GetToVertices(vertex, vertexQ); while (!vertexQ.IsEmpty()) { vertexQ.Dequeue(item); if (!graph.IsMarked(item)) queue.Enqueue(item); } } } } while (!queue.IsEmpty() && !found); if(found) cout << "\nPath is found." << endl; else cout << "\nPath not found." << endl; } string addWithInfinity(string x, string y){ } //If x is less than y, then return true, else return false. bool isLessWithInfinity(string x, string y){ } string minWithInfinity(string x, string y){ } #endif
CSC240_GraphType/src/MaxItem.h
// ItemType.h StackDriver const int MAX_ITEMS = 5;
CSC240_GraphType/src/QueType.h
#ifndef QUETYPE_H #define QUETYPE_H // Header file for Queue ADT. #include <new> #include <iostream> using namespace std; class FullQueue {}; class EmptyQueue {}; template <class ItemType> struct NodeType; template <class ItemType> class QueType { public: QueType(); // Class constructor. // Because there is a default constructor, the precondition // that the queue has been initialized is omitted. QueType(int max); // Parameterized class constructor. ~QueType(); // Class destructor. void MakeEmpty(); // Function: Initializes the queue to an empty state. // Post: Queue is empty. bool IsEmpty() const; // Function: Determines whether the queue is empty. // Post: Function value = (queue is empty) bool IsFull() const; // Function: Determines whether the queue is full. // Post: Function value = (queue is full) void Enqueue(ItemType newItem); // Function: Adds newItem to the rear of the queue. // Post: If (queue is full) FullQueue exception is thrown // else newItem is at rear of queue. void Dequeue(ItemType& item); // Function: Removes front item from the queue and returns it in item. // Post: If (queue is empty) EmptyQueue exception is thrown // and item is undefined // else front element has been removed from queue and // item is a copy of removed element. private: NodeType<ItemType>* front; NodeType<ItemType>* rear; }; template <class ItemType> struct NodeType { ItemType info; NodeType* next; }; template <class ItemType> QueType<ItemType>::QueType() // Class constructor. // Post: front and rear are set to NULL. { front = NULL; rear = NULL; } template <class ItemType> void QueType<ItemType>::MakeEmpty() // Post: Queue is empty; all elements have been deallocated. { NodeType<ItemType>* tempPtr; while (front != NULL) { tempPtr = front; front = front->next; delete tempPtr; } rear = NULL; } template <class ItemType> // Class destructor. QueType<ItemType>::~QueType() { MakeEmpty(); } template<class ItemType> bool QueType<ItemType>::IsFull() const // Returns true if there is no room for another ItemType // on the free store; false otherwise. { NodeType<ItemType>* location; try { location = new NodeType<ItemType>; delete location; return false; } catch(std::bad_alloc& exception) { return true; } } template <class ItemType> bool QueType<ItemType>::IsEmpty() const // Returns true if there are no elements on the queue; false otherwise. { return (front == NULL); } template <class ItemType> void QueType<ItemType>::Enqueue(ItemType newItem) // Adds newItem to the rear of the queue. // Pre: Queue has been initialized. // Post: If (queue is not full) newItem is at the rear of the queue; // otherwise a FullQueue exception is thrown. { if (IsFull()) throw FullQueue(); else { NodeType<ItemType>* newNode; newNode = new NodeType<ItemType>; newNode->info = newItem; newNode->next = NULL; if (rear == NULL) front = newNode; else rear->next = newNode; rear = newNode; } } template <class ItemType> void QueType<ItemType>::Dequeue(ItemType& item) // Removes front item from the queue and returns it in item. // Pre: Queue has been initialized and is not empty. // Post: If (queue is not empty) the front of the queue has been // removed and a copy returned in item; // othersiwe a EmptyQueue exception has been thrown. { if (IsEmpty()) throw EmptyQueue(); else { NodeType<ItemType>* tempPtr; tempPtr = front; item = front->info; front = front->next; if (front == NULL) rear = NULL; delete tempPtr; } } #endif
CSC240_GraphType/src/StackType.h
#ifndef STACKTYPE_H #define STACKTYPE_H #include "MaxItem.h" // The class definition for StackType using templates class FullStack // Exception class thrown by Push when stack is full. {}; class EmptyStack // Exception class thrown by Pop and Top when stack is emtpy. {}; // MaxItems.h must be provided by the user of this class. // This file must contains the definition of MAX_ITEMS, // themaximum number ofitems on the stack. template<class ItemType> class StackType { public: StackType(); // Class constructor. bool IsFull() const; // Function: Determines whether the stack is full. // Pre: Stack has been initialized. // Post: Function value = (stack is full) bool IsEmpty() const; // Function: Determines whether the stack is empty. // Pre: Stack has been initialized. // Post: Function value = (stack is empty) void Push(ItemType item); // Function: Adds newItem to the top of the stack. // Pre: Stack has been initialized. // Post: If (stack is full), FullStack exception is thrown; // otherwise, newItem is at the top of the stack. void Pop(ItemType& popedItem); // Function: Removes top item from the stack. // Pre: Stack has been initialized. // Post: If (stack is empty), EmptyStack exception is thrown; // otherwise, top element has been removed from stack. // popedItem holds the data of the most recently popped item from the stack. ItemType Top(); // Function: Returns a copy of top item on the stack. // Pre: Stack has been initialized. // Post: If (stack is empty), EmptyStack exception is thrown; // otherwise, top element has been removed from stack. private: int top; ItemType items[MAX_ITEMS]; }; // The function definitions for class StackType. // The function definitions for class StackType. template<class ItemType> StackType<ItemType>::StackType() { top = -1; } template<class ItemType> bool StackType<ItemType>::IsEmpty() const { return (top == -1); } template<class ItemType> bool StackType<ItemType>::IsFull() const { return (top == MAX_ITEMS-1); } template<class ItemType> void StackType<ItemType>::Push(ItemType newItem) { if (IsFull()) throw FullStack(); top++; items[top] = newItem; } //IT 5/1/2019 Modified Pop template<class ItemType> void StackType<ItemType>::Pop(ItemType& pI) { if( IsEmpty() ) throw EmptyStack(); pI = items[top]; top--; } template<class ItemType> ItemType StackType<ItemType>::Top() { if (IsEmpty()) throw EmptyStack(); return items[top]; } #endif
