MUST USE C++
PLEASE READ THE QUESTION CAREFULLY
ADD COMMENTS AND EXPLAIN THE CODES PLEASE.
Given the following skeleton of an unsorted list class that uses an unsorted linked list:
template < class ItemType >
struct NodeType
{
ItemType item;
NodeType* next;
};
template < class ItemType >
class UList
{
public:
UList(); // default constrctor
UList(const UList &x); // we implement copy constructor with deep copy
UList& operator = (UList &x); // equal sign operator with deep copy
bool IsThere(ItemType item) const; // return true of false to indicate if item is in the list
void Insert(ItemType item); // if item is not in the list, insert it into the list
void Delete(ItemType item); // delete item from the list
void Print(); // Print all the items in the list on screen
int Length(); // return the number of items in the list
~UList(); // we do not implement destructor: programmer should be responsible to deallocate the linked list
private:
NodeType < ItemType > * listPtr;
};
Task 1: Implement the template class UList on the basis of the above skeleton. Compile your program.
Task 2: Write a simple driver that reads values from file float.dat, inserts them into an instance, x, of the list, prints the length of the final list, and prints the values of all the list elements.
float.dat contains:
5.5
6.2
7.1
8.0
9.0
40.0
1.0
2.0
53.3
4.4
Task 3: Add code to your driver to test the remaining member functions. Delete 2.0, 9.0, and 6.2 from x and print the list to be sure they are gone.
Task 4: Create another instance, y, through the copy constructor such that the content of y is the same as that of x, but a deep copy should be done. Print out the all the list elements of y.
Task 5: Declare an instance, z, and assign the content of x to z through the operation “=”. Print out the all the list elements of z.
Task 6: Test if 9.0 is in the lists x and y via the member function: IsThere(ItemType item) and print out the test results.
Task 7: What is the Big-O notation for the time complexity of IsThere( ) function?
//UList.h
template < class ItemType >
struct NodeType
{
ItemType item;
NodeType* next;
};
template < class ItemType >
class UList
{
public:
UList(); // default constrctor
UList(const UList &x); // we implement copy constructor with deep copy
UList& operator = (UList &x); // equal sign operator with deep copy
bool IsThere(ItemType item) const; // return true of false to indicate if item is in the list
void Insert(ItemType item); // if item is not in the list, insert it into the list
void Delete(ItemType item); // delete item from the list
void Print(); // Print all the items in the list on screen
int Length(); // return the number of items in the list
~UList(); // we do not implement destructor: programmer should be responsible to deallocate the linked list
private:
NodeType < ItemType > * listPtr;
};
//UList.cpp
#include<iostream>
#include "UList.h"
using namespace std;
template < class ItemType >
UList<ItemType>::UList(){
listPtr = NULL;
}
template < class ItemType >
UList<ItemType>::UList(const UList &x){
NodeType < ItemType >*current = x.listPtr ,
*tail = NULL, *newNode;
while(current!=NULL){
newNode = new NodeType <
ItemType >;
newNode->item =
current->item;
newNode->next = NULL;
if(tail == NULL){
listPtr =
newNode;
tail =
listPtr;
}
else{
tail->next =
newNode;
tail =
newNode;
}
current = current->next;
}
}
template < class ItemType >
UList<ItemType>& UList<ItemType>::operator =
(UList<ItemType> &x){
NodeType < ItemType >*current = x.listPtr ,
*tail = NULL, *newNode;
UList *list = new UList();
while(current!=NULL){
newNode = new NodeType <
ItemType >;
newNode->item =
current->item;
newNode->next = NULL;
if(tail == NULL){
list->listPtr
= newNode;
tail =
list->listPtr;
}
else{
tail->next =
newNode;
tail =
newNode;
}
current = current->next;
}
return *list;
}
template < class ItemType >
bool UList<ItemType>::IsThere(ItemType item) const{
NodeType < ItemType >*current = listPtr;
while(current!=NULL){
if(current->item == item)return
true;
current = current->next;
}
return false;
}
template < class ItemType >
void UList<ItemType>::Insert(ItemType item){
if(this->IsThere(item))return;
NodeType < ItemType >*current = listPtr ,
*newNode;
newNode = new NodeType < ItemType >;
newNode->item = item;
newNode->next = NULL;
if(listPtr == NULL){
listPtr = newNode;
return;
}
while(current->next!=NULL){
current = current->next;
}
current->next = newNode;
}
template < class ItemType >
void UList<ItemType>::Delete(ItemType item){
NodeType < ItemType >*current = listPtr , *prev
= NULL ;
if(listPtr->item == item){
listPtr = listPtr->next;
delete current;
}
while(current!=NULL && current->item !=
item){
prev = current;
current = current->next;
}
if(current == NULL)return;
prev->next = current->next;
delete current;
}
template < class ItemType >
void UList<ItemType>::Print(){
NodeType < ItemType >*current = listPtr ;
while(current!=NULL){
cout<<current->item<<" ";
current = current->next;
}
}
template < class ItemType >
int UList<ItemType>::Length(){
NodeType < ItemType >*current = listPtr ;
int count = 0;
while(current!=NULL){
count++;
current = current->next;
}
return count;
}
template < class ItemType >
UList<ItemType>:: ~UList(){
NodeType < ItemType >*current = listPtr ,
*next;
while (current != NULL)
{
next = current->next;
delete(current);
current = next;
}
listPtr = NULL;
}
//main.cpp
#include "UList.cpp"
#include <fstream>
int main(){
UList<float> x ;
ifstream in;
in.open("float.dat");
float num;
if(!in){
cout<<"File not
opened\n";
exit(1);
}
cout<<"read\n";
while(!in.eof()){
in>>num;
x.Insert(num);
}
cout<<"Your list \n ";
x.Print();
cout<<"\nLength of list :
"<<x.Length()<<endl;
x.Delete(2.0);
cout<<"\nYour list \n ";
x.Print();
x.Delete(9.0);
cout<<"\nYour list \n ";
x.Print();
x.Delete(6.2);
cout<<"\nYour list \n ";
x.Print();
UList<float> y(x);
cout<<"\nYour list \n ";
y.Print();
UList<float> z ;
z = x;
cout<<"\nYour list \n ";
z.Print();
if(x.IsThere(9.0)){
cout<<"\n9.0 is in the list
y\n";
}
else{
cout<<"\n9.0 is not in the
list y\n";
}
if(y.IsThere(9.0)){
cout<<"\n9.0 is in the list
y\n";
}
else{
cout<<"\n9.0 is not in the
list y\n";
}
return 0;
}
//Time complexity of IsThere( ) function = O(N) where N is length
of list.
MUST USE C++ PLEASE READ THE QUESTION CAREFULLY ADD COMMENTS AND EXPLAIN THE CODES PLEASE. Given...
c++ please Given the following skeleton of an unsorted list class that uses an unsorted linked list: template<class ItemType> struct NodeType { ItemType item; NodeType* next; }; template<class ItemType> class UList { public: UList(); // default constrctor UList(const UList &x); // we implement copy constructor with deep copy UList& operator = (UList &x); // equal sign operator with deep copy bool IsThere(ItemType item) const; // return true of false to indicate if item is...
I want the full code for this part and Its needs to be done in C++ Use a linked list to implement the following skeleton of an unsorted list typedef int ItemType: struct NodeType ItemType item; NodeType "next; class List List(); // default constructor List( const List &x); I copy constructor: deep copy is required List & operator = (const List &x); // assignment operator: deep copy. 1s required bool IsThere(ItemType x); identify if x is in the list void...
C++ Implement a templated class list and listnode. You may add methods/functions as you see fit. Test these classes. I have left all of the implementation as an exercise for you. template< class NODETYPE > class List; // forward declaration template<class NODETYPE> class ListNode { friend class List< NODETYPE >; // make List a friend public: ListNode( const NODETYPE &newData); // copy constructor NODETYPE getData() const; // return data in the node private: NODETYPE data; // data ListNode< NODETYPE > *nextPtr; // next node...
MUST BE ANSWERED BY USING C++ Question 1 Unsorted List Implement a template class UnsortedList as defined by the following skeleton: #define MAX_ITEMS 10 typedef char ItemType; class UnsortedList { private: int length; ItemType values[MAX_ITEMS]; int currentPos; public: SortedList( ); // default constructor: lenght=0, currentPos=-1 void MakeEmpty; // let length=0 void InsertItem(ItemType x); // insert x into the list void DeleteItem(ItemType x); // delete x from the list bool IsFull( ); // test...
Data Structures and Algorithms C++: I'm having a hard time getting my main.cpp part of the source code (shown below) to output the following: Inserting elements to array list: The list contains 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 Deleting elements: The list contains: 2 4 6 8 10 12 14 16 18 20 22 24 this is a programming problem in...
Given an array-based stack of integers, sort it largest to smallest using recursion. Do NOT use any loop constructs such as while, for and so on. Only use the following stack ADT functions in the recursion: IsEmpty Push Pop Top (note: doesn’t remove anything from the stack). Your program should read 10 integers into a stack from a file named input.txt (outputting them to the screen first) then implement the recursions. Use stacks only, no queues. The program should then...
I'm just not sure how to tackle all the template class this header wants me to write. I got this far into making the template for public and private and would like help on the template functions. Thank you! This is in C++ by the way. #include <iostream> #include <cassert> using namespace std; #ifndef ARRAYLIST_H #define ARRAYLIST_H template<typename T> class arrayList { public: arrayList(); //Constructor with default parameter. //Sets maxSize = 100 and length = 0 if no parameter...
Requirements Print a range Write a bag member function with two parameters. The two parameters are Items x and y. The function should write to the console all Items in the bag that are between the first occurrence of x and the first occurrence of y. You may assume that items can be compared for equality using ==. Use the following header for the function: void print_value_range(const Item& x, const Item& y); print_value_range can be interpreted in a number of...
(The SortedLinkedList class template) Complete the SortedLinkedList class template which is a doubly linked list and is implemented with a header node and a tail node. // SortedLinkedList.h // SortedLinkedList.h // A collection of data are stored in the list by ascending order #ifndef SORTEDLIST_H #define SORTEDLIST_H using namespace std; template <typename T> class SortedList { private: // The basic single linked list node type. // Nested inside of SortedList. struct NodeType { T data; NodeType* next; NodeType* prev; NodeType(const...
Introduction In this lab, you are supposed to implement a graph class with the data structure implemented before like linked list and queue. graph The class graph contains three member variables: linkedList *adjacentVertices; //an array of linked list. For a vertice i, adjacentVertices[i] stores the linked list that contains all other vertices connected to vertice i. int numVertices; //The number of vertices in the graph. int maxNumVertices; //The maximum number of vertices the graph can hold. Following public methods are...