In c++ format please: this is the header file i have to implement which i have d
ID: 3861305 • Letter: I
Question
In c++ format please:
this is the header file i have to implement which i have done, if someone can please correct my mistakes there are syntex errors.
#include <iostream>
#include <cstdlib>
#include "List.h"
#include <vector>
using namespace std;
class Graph {
public:
/**Constructors and Destructors*/
Graph(int n);
//initializes an empty graph to have n vertices and no edges
/*** Access Functions ***/
int getNumEdges();
//returns the number of edges in the graph
int getNumVertices();
//returns the number of vertices in the graph
bool isEmpty();
//returns whether the graph is empty
/*** Manipulation Procedures ***/
void addEdge(int u, int v);
//Pre: u <= getNumVertices() && v <=getNumVertices()
//inserts vertex v into the adjacency list of vertex u (i.e. inserts v into the list at index u)
//and inserts u into v.
void removeEdge(int u, int v);
//Pre: u <= getNumVertices() && v <=getNumVertices()
//removes vertex v from the adjacency list of vertex u
//and removes u from v.
/*** Additional Operations ***/
void printGraph(ostream& output);
//Prints the adjacency list of each vertex in the graph,
//vertex: <space separated list of adjacent vertices>
//Prints to the console or to an output file given the ostream parameter
private:
int vertices, edges; //number of edges and vertices
vector<List<int> > adj;
};
my cpp file after implementation:
#include <iostream>
#include <cstdlib>
#include "List.h"
#include "Graph.h"
#include <vector>
using namespace std;
Graph::Graph(int n)
{
vector<int>(n+1);
vertices=n;
for(int i=1;i<=n;i++)
adj[i] = new List();
edges=0;
}
bool Graph::isEmpty()
{
return getNumVertices() ==0 || getNumEdges()==0;
}
int Graph::getNumEdges()
{
return edges;
}
int Graph::getNumVertices()
{
return vertices;
}
void Graph::addEdge(int u,int v)
{
assert(u <= getNumVertices());
assert(v <= getNumVertices());
if( adj[u].getSize() == 0 ||
(adj[u].getSize()!=0 && adj[u].linearSearch(v)==-1))
adj[u].insertFirst(v);
if(adj[v].getSize()==0 ||
(adj[v].getSize()!=0 && adj[v].linearSearch(u)==-1))
adj[v].insertFirst(u);
edges++;
}
void Graph::removeEdge(int u,int v)
{
assert(u<=getNumVertices());
assert(v<=getNumVertices());
int size = adj[u].getSize()
adj[u].startIterator();
for(int i=0;i < size;i++)
{
if(adj[u].getIterator()==v)
{
adj[u].removeIterator();
break;
}
adj[u]->.advanceIterator();
}
size = adj[v].getSize().
adj[v].startIterator();
for(int i=0;i < size;i++)
{
if(adj[v].getIterator()==u)
{
adj[v].removeIterator();
break;
}
adj[v].advanceIterator();
}
edges--;
}
void Graph::printGraph(ostream &output)
{
int VertSize = adj.size();
output<<" Graph has "<<getNumVertices()<<" vertices and "<< getNumEdges() << " edges ";
output<<" Adjacency list of all vertices is given below: ";
for(int i=1; i < VertSize ; i++)
{
output<< "vertex "<<i<<" adjacent to : ";
adj[i].printList();
output << " " << endl;
}
}
and this is my lab.h header file:
#ifndef LIST_H_
#define LIST_H_
#include <iostream>
#include <cstddef> //for NULL
#include "assert.h"
using namespace std;
template <class listdata>
class List
{
private:
struct Node
{
listdata data;
Node* next;
Node* previous;
Node(listdata data): data(data), next(NULL), previous(NULL){}
};
typedef struct Node* Nodeptr;
Nodeptr first;
Nodeptr last;
Nodeptr iterator;
int size;
void reverse(Nodeptr node);
//Helper function for the public printReverse() function.
//Recursively prints the data in a List in reverse.
bool isSorted(Nodeptr node);
//Helper function for the public isSorted() function.
//Recursively determines whether a list is sorted in ascending order.
int binarySearch(int low, int high, listdata data);
//Recursively searchs the list by dividing the search space in half
//Returns the index of the element, if it is found in the List
//Returns -1 if the element is not in the List
public:
/**Constructors and Destructors*/
List();
//Default constructor; initializes and empty list
//Postcondition: A new list object is created
List (const List &list);
//copy constructor
~List();
//Destructor. Frees memory allocated to the list
//Postcondition: Memory that was created has been freed
/**Accessors*/
listdata getFirst();
//Returns the first element in the list
//Precondition: List cannot be empty (there must be a first element)
listdata getLast();
//Returns the last element in the list
//Precondition: List cannot be empty (there must be a last element)
bool isEmpty();
//Determines whether a list is empty.
int getSize();
//Returns the size of the list
listdata getIterator();
//returns the element currently pointed at by the iterator
bool offEnd();
//returns whether the iterator is off the end of the list, i.e. is NULL
bool isSorted();
//Wrapper function that calls the isSorted helper function to determine whether
//a list is sorted in ascending order.
//We will consider that a list is trivially sorted if it is empty.
//Therefore, no precondition is needed for this function
int getIndex();
//Indicates the index of the Node where the iterator is currently pointing
//Nodes are numbered from 1 to size of the list
//Pre: size != 0
//Pre: !off_end()
int linearSearch(listdata data);
//Searchs the list, element by element, from the start of the List to the end of the List
//Returns the index of the element, if it is found in the List
//Calls the above indexing functions in its implementation
//Returns -1 if the element is not in the List
//Pre: size != 0
// int binarySearch(int low, int high, listdata value,);
//Returns the index where data is located in the List
//Calls the private helper function binarySearch to perform the search
//Pre: size != 0
//Pre: List is sorted (must test on a sorted list)
/**Manipulation Procedures*/
void removeLast();
//Removes the value of the last element in the list
//Precondition: List cannot be empty (there must be a last element to remove)
//Postcondition: The last element is removed
void removeFirst();
//Removes the value of the first element in the list
//Precondition: List cannot be empty (there must be a first element to remove)
//Postcondition: The first element is removed
void insertLast(listdata data);
//Inserts a new element at the end of the list
//If the list is empty, the new element becomes both first and last
//Postcondition: There is a new last element
void insertFirst(listdata data);
//insertFirst inserts a new Node IN FRONT OF the first node in the list each time it is called,
//effectively creating a new front of the list.
//Inserts a new element at the start of the list
//If the list is empty, the new element becomes both first and last
//Postcondition: There is a new first element
void startIterator ();
// moves the iterator to the start of the list
void removeIterator();
//removes the element currently pointed to by the iterator. Iterator then points to NULL.
void insertIterator(listdata data);
//inserts an element after the node currently pointed to by the iterator
void advanceIterator();
//advanceIterator: moves the iterator up by one node
void advanceToIndex(int index);
//Moves the iterator to the node whose index number is specified in the parameter
//Pre: size != 0
//Pre: index <= size
/**Additional List Operations*/
void printList();
//Prints to the console the value of each element in the list sequentially
//and separated by a blank space
//Prints nothing if the list is empty
bool operator==(const List &list);
//Tests two lists to determine whether their contents are equal
//Postcondition: returns true if lists are equal and false otherwise
void printReverse();
//Wrapper function that calls the reverse helper function to print a list in reverse
//prints nothing if the List is empty
};
template <class listdata>
//default constructor
List<listdata> ::List()
{
first = NULL;
last = NULL;
size = 0;
iterator = NULL;
}
//copy constructor
template <class listdata>
List<listdata>::List(const List &list) : size(list.size)
{
if(list.first == NULL) //If the original list is empty, make an empty list for this list
{
first = last = iterator = NULL;
}
else
{
first = new Node(list.first->data); //calling Node constructor
Nodeptr temp = list.first; //set a temporary node pointer to point at the first of the original list
iterator = first; //set iterator to point to first node of the new list
while(temp->next != NULL)
{
temp = temp->next; //advance up to the next node in the original list
iterator->next = new Node(temp->data); //using node constructor to create a new node with copy of data
iterator = iterator->next; //advance to this new node
}
last = iterator; //Why do I need this line of code?
iterator = NULL;
}
}
//default destrcutor
template <class listdata>
List<listdata> ::~List()
{
Nodeptr cursor = first;
Nodeptr temp;
while(cursor != NULL)
{
temp = cursor->next;
delete cursor;
cursor = temp;
}
}
template <class listdata>
listdata List<listdata>:: getFirst()
{
assert(size!=0);
return first->data;
}
template <class listdata>
listdata List<listdata>::getLast()
{
assert(size!=0);
return last->data;
}
template <class listdata>
bool List<listdata>::isEmpty()
{
return (size == 0);
}
template <class listdata>
int List<listdata>:: getSize()
{
return size;
}
template <class listdata>
listdata List<listdata>:: getIterator()
{
assert (size !=0);
assert(iterator != NULL);
return iterator->data;
}
template <class listdata>
bool List<listdata>:: offEnd()
{
if (iterator == NULL)
{
return true;
}
else
{
return false;
}
}
template <class listdata>
void List<listdata>:: removeLast()
{
assert (size != 0);
if (first->next == NULL)
{
delete last;
first = NULL;
last = NULL;
size = 0;
}
else
{
Nodeptr temp = first;
while (temp->next != last)
{
temp = temp->next;
}
delete last;
last = temp;
last->next = NULL;
}
size --;
}
template <class listdata>
void List<listdata>:: removeFirst ()
{
assert(size!=0);
if (size == 1)
{
delete first;
first = last = NULL;
size = 0;
}
else
{
Nodeptr temp= first;
first = first->next;
delete temp;
size --;
}
}
template <class listdata>
void List<listdata>:: insertLast (listdata data)
{
if (size == 0)
{
first = new Node(data);
last = first;
}
else
{
last -> next = new Node(data);
last = last -> next;
}
size++;
}
template <class listdata>
void List<listdata>::insertFirst(listdata data)
{
if (size==0)
{
first = new Node(data);
last = first;
}
else
{
Nodeptr N = new Node(data);
N->next = first;
first->previous = N;
first = N;
}
size++;
}
template <class listdata>
void List<listdata>:: startIterator ()
{
iterator = first;
}
template <class listdata>
void List<listdata>:: removeIterator()
{
assert(iterator != NULL);
if (iterator == last)
{
removeLast();
}
else if (iterator == first)
{
removeFirst();
}
else
{
iterator->previous->next = iterator->next;
iterator->next-> previous = iterator->previous;
delete iterator;
iterator = NULL;
}
size --;
}
template <class listdata>
void List<listdata>:: insertIterator(listdata data)
{
assert(iterator != NULL);
if (iterator == last)
{
insertLast(data);
}
else
{
Nodeptr N = new Node(data);
N->previous = iterator;
N->next = iterator->next;
iterator->next->previous = N;
iterator->next = N;
size++;
}
}
template <class listdata>
void List<listdata>:: advanceIterator()
{
assert (size != 0);
assert (iterator != NULL);
iterator = iterator->next;
}
template <class listdata>
void List<listdata>::printList()
{
Nodeptr iter= first;
while (iter != NULL)
{
cout << iter->data << " ";
iter = iter->next;
}
cout << endl;
}
template <class listdata>
bool List<listdata>:: operator == (const List& list)
{
if(size != list.size)
return false;
Nodeptr temp1 = first;
Nodeptr temp2 = list.first;
while(temp1 != NULL)
{
if(temp1->data != temp2->data)
return false;
temp1 = temp1->next;
temp2 = temp2->next;
}
return true;
}
template <class listdata>
void List <listdata>:: reverse(Nodeptr list)
{
Nodeptr temp = last;
if (temp == NULL)
return;
else
{
cout << temp->data << endl;
temp = temp->previous;
}
}
template <class listdata>
void List<listdata>:: printReverse()
{
reverse(first);
}
template <class listdata>
bool List<listdata>:: isSorted()
{
if (size ==0)
{
return isSorted();
}
else
reverse (last);
return true;
}
template <class listdata>
int List<listdata>:: getIndex()
{
assert (!offEnd());
assert (iterator != NULL);
int count =1 ;
Nodeptr temp= first;
while (temp != iterator)
{
count++;
temp = temp->next;
}
return cout ;
}
template <class listdata>
void List<listdata>:: advanceToIndex(int index)
{
assert(size!=0);
assert (iterator != NULL);
iterator = first;
for (int i = 1; i < index; i++)
{
iterator = iterator->next;
}
}
template <class listdata>
int List<listdata>::linearSearch(listdata data)
{
assert (size != 0);
Nodeptr temp;
temp = first;
int location = 1;
while (temp != NULL)
{
if (temp->data == data)
{
return location;
}
else
{
location++;
temp = temp->next;
}
}
return -1;
}
template <class listdata>
int List<listdata>:: binarySearch(int low, int high, listdata value)
{
if (high < low)
return -1;
int mid = (low + high);
if (mid % 2 != 0)
{
return mid;
}
else
advanceToIndex(mid);
if (getIterator() == value)
{
return mid;
}
else if (value < getIterator())
{
return binarySearch(low, mid -1, value);
}
else
return binarySearch( low, mid +1, value);
}
#endif /* LIST_H_ */
Explanation / Answer
#include <iostream>
#include <cstdlib>
#include "List.h"
#include <vector>
using namespace std;
class Graph {
public:
/**Constructors and Destructors*/
Graph(int n);
//initializes an empty graph to have n vertices and no edges
/*** Access Functions ***/
int getNumEdges();
//returns the number of edges in the graph
int getNumVertices();
//returns the number of vertices in the graph
bool isEmpty();
//returns whether the graph is empty
/*** Manipulation Procedures ***/
void addEdge(int u, int v);
//Pre: u <= getNumVertices() && v <=getNumVertices()
//inserts vertex v into the adjacency list of vertex u (i.e. inserts v into the list at index u)
//and inserts u into v.
void removeEdge(int u, int v);
//Pre: u <= getNumVertices() && v <=getNumVertices()
//removes vertex v from the adjacency list of vertex u
//and removes u from v.
/*** Additional Operations ***/
void printGraph(ostream& output);
//Prints the adjacency list of each vertex in the graph,
//vertex: <space separated list of adjacent vertices>
//Prints to the console or to an output file given the ostream parameter
private:
int vertices, edges; //number of edges and vertices
vector<List<int> > adj;
};
#include <iostream>
#include <cstdlib>
#include "List.h"
#include "Graph.h"
#include <vector>
using namespace std;
Graph::Graph(int n)
{
vector<int>(n+1);
vertices=n;
for(int i=1;i<=n;i++)
adj[i] = new List();
edges=0;
}
bool Graph::isEmpty()
{//modified
if(getNumVertices() ==0 || getNumEdges()==0)
return true;
else return false;
}
int Graph::getNumEdges()
{
return edges;
}
int Graph::getNumVertices()
{
return vertices;
}
void Graph::addEdge(int u,int v)
{
//assert(u <= getNumVertices());
//assert(v <= getNumVertices());
//conditional and comparisions must be done in if statements
if(u <= getNumVertices())//modified
assert(true);
else assert(false);
if(v <= getNumVertices())assert(true);
else assert(false)
if( adj[u].getSize() == 0 ||
(adj[u].getSize()!=0 && adj[u].linearSearch(v)==-1))
adj[u].insertFirst(v);
if(adj[v].getSize()==0 ||
(adj[v].getSize()!=0 && adj[v].linearSearch(u)==-1))
adj[v].insertFirst(u);
edges++;
}
void Graph::removeEdge(int u,int v)
{
// assert(u<=getNumVertices());
//assert(v<=getNumVertices());
//assert(u <= getNumVertices());
//assert(v <= getNumVertices());
//conditional and comparisions must be done in if statements
if(u <= getNumVertices())//modified
assert(true);
else assert(false);
if(v <= getNumVertices())assert(true);
else assert(false)
int size = adj[u].getSize()
adj[u].startIterator();
for(int i=0;i < size;i++)
{
if(adj[u].getIterator()==v)
{
adj[u].removeIterator();
break;
}
adj[u]->.advanceIterator();
}
size = adj[v].getSize().
adj[v].startIterator();
for(int i=0;i < size;i++)
{
if(adj[v].getIterator()==u)
{
adj[v].removeIterator();
break;
}
adj[v].advanceIterator();
}
edges--;
}
void Graph::printGraph(ostream &output)
{
int VertSize = adj.size();
output<<" Graph has "<<getNumVertices()<<" vertices and "<< getNumEdges() << " edges ";
output<<" Adjacency list of all vertices is given below: ";
for(int i=1; i < VertSize ; i++)
{
output<< "vertex "<<i<<" adjacent to : ";
adj[i].printList();
output << " " << endl;
}
}
#ifndef LIST_H_
#define LIST_H_
#include <iostream>
#include <cstddef> //for NULL
#include "assert.h"
using namespace std;
template <class listdata>
class List
{
private:
struct Node
{
listdata data;
Node* next;
Node* previous;
Node(listdata data): data(data), next(NULL), previous(NULL){}
};
typedef struct Node* Nodeptr;
Nodeptr first;
Nodeptr last;
Nodeptr iterator;
int size;
void reverse(Nodeptr node);
//Helper function for the public printReverse() function.
//Recursively prints the data in a List in reverse.
bool isSorted(Nodeptr node);
//Helper function for the public isSorted() function.
//Recursively determines whether a list is sorted in ascending order.
int binarySearch(int low, int high, listdata data);
//Recursively searchs the list by dividing the search space in half
//Returns the index of the element, if it is found in the List
//Returns -1 if the element is not in the List
public:
/**Constructors and Destructors*/
List();
//Default constructor; initializes and empty list
//Postcondition: A new list object is created
List (const List &list);
//copy constructor
~List();
//Destructor. Frees memory allocated to the list
//Postcondition: Memory that was created has been freed
/**Accessors*/
listdata getFirst();
//Returns the first element in the list
//Precondition: List cannot be empty (there must be a first element)
listdata getLast();
//Returns the last element in the list
//Precondition: List cannot be empty (there must be a last element)
bool isEmpty();
//Determines whether a list is empty.
int getSize();
//Returns the size of the list
listdata getIterator();
//returns the element currently pointed at by the iterator
bool offEnd();
//returns whether the iterator is off the end of the list, i.e. is NULL
bool isSorted();
//Wrapper function that calls the isSorted helper function to determine whether
//a list is sorted in ascending order.
//We will consider that a list is trivially sorted if it is empty.
//Therefore, no precondition is needed for this function
int getIndex();
//Indicates the index of the Node where the iterator is currently pointing
//Nodes are numbered from 1 to size of the list
//Pre: size != 0
//Pre: !off_end()
int linearSearch(listdata data);
//Searchs the list, element by element, from the start of the List to the end of the List
//Returns the index of the element, if it is found in the List
//Calls the above indexing functions in its implementation
//Returns -1 if the element is not in the List
//Pre: size != 0
// int binarySearch(int low, int high, listdata value,);
//Returns the index where data is located in the List
//Calls the private helper function binarySearch to perform the search
//Pre: size != 0
//Pre: List is sorted (must test on a sorted list)
/**Manipulation Procedures*/
void removeLast();
//Removes the value of the last element in the list
//Precondition: List cannot be empty (there must be a last element to remove)
//Postcondition: The last element is removed
void removeFirst();
//Removes the value of the first element in the list
//Precondition: List cannot be empty (there must be a first element to remove)
//Postcondition: The first element is removed
void insertLast(listdata data);
//Inserts a new element at the end of the list
//If the list is empty, the new element becomes both first and last
//Postcondition: There is a new last element
void insertFirst(listdata data);
//insertFirst inserts a new Node IN FRONT OF the first node in the list each time it is called,
//effectively creating a new front of the list.
//Inserts a new element at the start of the list
//If the list is empty, the new element becomes both first and last
//Postcondition: There is a new first element
void startIterator ();
// moves the iterator to the start of the list
void removeIterator();
//removes the element currently pointed to by the iterator. Iterator then points to NULL.
void insertIterator(listdata data);
//inserts an element after the node currently pointed to by the iterator
void advanceIterator();
//advanceIterator: moves the iterator up by one node
void advanceToIndex(int index);
//Moves the iterator to the node whose index number is specified in the parameter
//Pre: size != 0
//Pre: index <= size
/**Additional List Operations*/
void printList();
//Prints to the console the value of each element in the list sequentially
//and separated by a blank space
//Prints nothing if the list is empty
bool operator==(const List &list);
//Tests two lists to determine whether their contents are equal
//Postcondition: returns true if lists are equal and false otherwise
void printReverse();
//Wrapper function that calls the reverse helper function to print a list in reverse
//prints nothing if the List is empty
};
template <class listdata>
//default constructor
List<listdata> ::List()
{
first = NULL;
last = NULL;
size = 0;
iterator = NULL;
}
//copy constructor
template <class listdata>
List<listdata>::List(const List &list) : size(list.size)
{
if(list.first == NULL) //If the original list is empty, make an empty list for this list
{
first = last = iterator = NULL;
}
else
{
first = new Node(list.first->data); //calling Node constructor
Nodeptr temp = list.first; //set a temporary node pointer to point at the first of the original list
iterator = first; //set iterator to point to first node of the new list
while(temp->next != NULL)
{
temp = temp->next; //advance up to the next node in the original list
iterator->next = new Node(temp->data); //using node constructor to create a new node with copy of data
iterator = iterator->next; //advance to this new node
}
last = iterator; //Why do I need this line of code?
iterator = NULL;
}
}
//default destrcutor
template <class listdata>
List<listdata> ::~List()
{
Nodeptr cursor = first;
Nodeptr temp;
while(cursor != NULL)
{
temp = cursor->next;
delete cursor;
cursor = temp;
}
}
template <class listdata>
listdata List<listdata>:: getFirst()
{
//modified....
//comparision operator should be used in if statement
//assert(size!=0);
if(sizes!=0)assert(true);
else assert(false);
return first->data;
}
template <class listdata>
listdata List<listdata>::getLast()
{
//modified....
//comparision operator should be used in if statement
//assert(size!=0);
if(sizes!=0)assert(true);
else assert(false);
return last->data;
}
template <class listdata>
bool List<listdata>::isEmpty()
{
//modified..
if(size == 0)
return true;
return false;
//return (size == 0);
}
template <class listdata>
int List<listdata>:: getSize()
{
return size;
}
template <class listdata>
listdata List<listdata>:: getIterator()
{
//modified....
//comparision operator should be used in if statement
//assert (size !=0);
if(sizes!=0)assert(true);
else assert(false);
//assert(iterator != NULL);
if(iterator != NULL)
assert(true);
else assert(false);
return iterator->data;
}
template <class listdata>
bool List<listdata>:: offEnd()
{
if (iterator == NULL)
{
return true;
}
else
{
return false;
}
}
template <class listdata>
void List<listdata>:: removeLast()
{
//assert (size != 0);
//modified....
//comparision operator should be used in if statement
//assert(size!=0);
if(sizes!=0)assert(true);
else assert(false);
if (first->next == NULL)
{
delete last;
first = NULL;
last = NULL;
size = 0;
}
else
{
Nodeptr temp = first;
while (temp->next != last)
{
temp = temp->next;
}
delete last;
last = temp;
last->next = NULL;
}
size --;
}
template <class listdata>
void List<listdata>:: removeFirst ()
{
//assert(size!=0);
//modified....
//comparision operator should be used in if statement
//assert(size!=0);
if(sizes!=0)assert(true);
else assert(false);
if (size == 1)
{
delete first;
first = last = NULL;
size = 0;
}
else
{
Nodeptr temp= first;
first = first->next;
delete temp;
size --;
}
}
template <class listdata>
void List<listdata>:: insertLast (listdata data)
{
if (size == 0)
{
first = new Node(data);
last = first;
}
else
{
last -> next = new Node(data);
last = last -> next;
}
size++;
}
template <class listdata>
void List<listdata>::insertFirst(listdata data)
{
if (size==0)
{
first = new Node(data);
last = first;
}
else
{
Nodeptr N = new Node(data);
N->next = first;
first->previous = N;
first = N;
}
size++;
}
template <class listdata>
void List<listdata>:: startIterator ()
{
iterator = first;
}
template <class listdata>
void List<listdata>:: removeIterator()
{
//assert(iterator != NULL);
//modified
if(iterator != NULL)assert(true);
else assert(false);
if (iterator == last)
{
removeLast();
}
else if (iterator == first)
{
removeFirst();
}
else
{
iterator->previous->next = iterator->next;
iterator->next-> previous = iterator->previous;
delete iterator;
iterator = NULL;
}
size --;
}
template <class listdata>
void List<listdata>:: insertIterator(listdata data)
{
//assert(iterator != NULL);
//modified
if(iterator != NULL)assert(true);
else assert(false);
if (iterator == last)
{
insertLast(data);
}
else
{
Nodeptr N = new Node(data);
N->previous = iterator;
N->next = iterator->next;
iterator->next->previous = N;
iterator->next = N;
size++;
}
}
template <class listdata>
void List<listdata>:: advanceIterator()
{
assert (size != 0);
//assert (iterator != NULL);
//modified
if(iterator != NULL)assert(true);
else assert(false);
iterator = iterator->next;
}
template <class listdata>
void List<listdata>::printList()
{
Nodeptr iter= first;
while (iter != NULL)
{
cout << iter->data << " ";
iter = iter->next;
}
cout << endl;
}
template <class listdata>
bool List<listdata>:: operator == (const List& list)
{
if(size != list.size)
return false;
Nodeptr temp1 = first;
Nodeptr temp2 = list.first;
while(temp1 != NULL)
{
if(temp1->data != temp2->data)
return false;
temp1 = temp1->next;
temp2 = temp2->next;
}
return true;
}
template <class listdata>
void List <listdata>:: reverse(Nodeptr list)
{
Nodeptr temp = last;
if (temp == NULL)
return;
else
{
cout << temp->data << endl;
temp = temp->previous;
}
}
template <class listdata>
void List<listdata>:: printReverse()
{
reverse(first);
}
template <class listdata>
bool List<listdata>:: isSorted()
{
if (size ==0)
{
return isSorted();
}
else
reverse (last);
return true;
}
template <class listdata>
int List<listdata>:: getIndex()
{
assert (!offEnd());
assert (iterator != NULL);
int count =1 ;
Nodeptr temp= first;
while (temp != iterator)
{
count++;
temp = temp->next;
}
return cout ;
}
template <class listdata>
void List<listdata>:: advanceToIndex(int index)
{
// assert(size!=0);
//assert (iterator != NULL);
//assert(size!=0);
//modified....
//comparision operator should be used in if statement
//assert(size!=0);
if(sizes!=0)assert(true);
else assert(false);
if(iterator != NULL)assert(true);
else assert(false)
iterator = first;
for (int i = 1; i < index; i++)
{
iterator = iterator->next;
}
}
template <class listdata>
int List<listdata>::linearSearch(listdata data)
{
// assert (size != 0);
//assert(size!=0);
//modified....
//comparision operator should be used in if statement
//assert(size!=0);
if(sizes!=0)assert(true);
else assert(false);
Nodeptr temp;
temp = first;
int location = 1;
while (temp != NULL)
{
if (temp->data == data)
{
return location;
}
else
{
location++;
temp = temp->next;
}
}
return -1;
}
template <class listdata>
int List<listdata>:: binarySearch(int low, int high, listdata value)
{
if (high < low)
return -1;
int mid = (low + high);
if (mid % 2 != 0)
{
return mid;
}
else
advanceToIndex(mid);
if (getIterator() == value)
{
return mid;
}
else if (value < getIterator())
{
return binarySearch(low, mid -1, value);
}
else
return binarySearch( low, mid +1, value);
}
#endif /* LIST_H_ */
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.