Sub: Data Structures & Algorithms. C++ The design should demonstrate a high degree of understanding of data structures a

[answerhappygod]

Sub: Data Structures & Algorithms. C++ The design
should demonstrate a high degree of understanding of data
structures and how to efficiently employ them to build
algorithms, Excellent formatting and variable naming.
Excellent, judiciously employed comments that explain the code
without just repeating the code, but remember it must compile
and run on Ed. The underlying g++ compiler in Ed is set to C++17
for this assessment. Usually, code that compiles with clang++
should also work with g++. MUST PASS ALL TESTS. tests.hpp is not
added as there is no space left to add and it not allowing to add
due to limited space. WILL GIVE UPVOTE REALLY NEED THE CORRECT
SOLUTION CODE.
Overview: In this group assignement you
will implement a templated version of a singly linked
list. You will implement several of the features that are
provided by the standard library std::forward_list in a class
called Forward_list. This programming assignment will build on what
you have done in Tutorial 3 on linked lists and Tutorial 7 on
sorting. Key new features that you will implement in this
assignment include:
maintain the size of the list
pop_front() delete the first element of the list
construct a new list from an existing one (copy constructor) or
from an initializer list like {1,3,5,7}.
sort the list. We have provided code to do merge sort, but left
to you to implement the key needed subroutines of merging two
sorted lists and splitting a list in half.
The Code: You are provided with two files:
my_forward_list.hpp: This contains all the function declarations
and instructions about which ones you need to
implement. All your implementations should be written
in this file. This is the only file we will use for
testing. You can add helper functions as needed but do not change
the signatures of the provided functions.
main.cpp: this includes a main function. You may write some code
to test your function implementations for Forward_list. This file
will not be marked so you can do anything you like with it -- just
ensure it does not cause any error. When the "run" button
is pressed, it will compile and run main.cpp.
Specifically, the functions you need to implement are
Linked list copy constructor (initialise a linked list from
another linked list)
Linked list constructor from an initializer_list (initialise a
linked list with e.g. {1,2,3,4})
push_front
pop_front
front
display (print out the list)
merge and split, two helper functions to implement merge
sort.
The code in my_forward_list.hpp has been
commented to explain the purpose of each function. Remember to read
over all the code before starting. When the "mark" button
is pressed, your code in my_forward_list.hpp will be run against
the tests in Ed. The testing code can only mark your code when your
code does not cause a program crash. If you get any error during
compiling or your program cannot stop by itself, make sure you fix
that problem first!
Testing: There are 10 tests that are run on
your code.
Test 1 is test_size_initialization. It just checks that your
code compiles with templated types and that the size of an empty
list is initialised to 0.
Test 2 is test_push_pop. It checks that push_front, front, and
pop_front are working and that the size_ variable is properly
updated under these operations.
Test 3 is test_copy_constructor. It tests your implementation of
the copy constructor.
Test 4 is test_initializer_list. It tests your constructor from
an initializer list of ints.
Test 5 is test_initializer_list_str. It tests your constructor
from an initializer list of strings.
Test 6 is test_merge. It tests your merge function.
Test 7 is test_merge_edge_cases. It tests some edge cases with
respect to the merge function.
Test 8 is test_split. It tests your split function.
Test 9 is test_split_and_merge. It tests that your split and
merge function work together to do one step of merge sort.
Test 10 is test_null_copy. It tests an edge case of your copy
constructor, to copy an empty list.
my_forward_list.hpp
#ifndef MY_FORWARD_LIST_HPP
#define MY_FORWARD_LIST_HPP
#include
template
class Forward_list
{
public:
class Node
{
public:
// A node will hold data of type T
T data{};
// next will point to the next node in the list
// we initialise next to nullptr
Node* next = nullptr;
// Because we have already intialised the variables
// the default constructor doesn't need to do anything
Node(){}
// To make life easier we also provide a constructor
// that takes the T data to be copied into the data member
variable
// There is an optional second argument which is
// used to update the next pointer. This defaults to nullptr
// if the constructor is called with just one argument.
Node(T input_data, Node* next_node= nullptr)
{
data = input_data;
next = next_node;
}
// Destructor
~Node(){}
};
private:
// private member variables for Forward_list
// the trailing underscore is a stylistic choice to
// distinguish these as private member variables
unsigned size_ = 0;
Node* head_ = nullptr;
public:
// public member functions of the Forward_list class
// We have generally used the same names as for the
// corresponding functions of std::forward_list
// Default constructor does not need to do anything
// and is provided for you.
Forward_list();

// The destructor is implemented for you
~Forward_list();
// Copy constructor
//*** For you to implement
Forward_list(const Forward_list& other);
// Constructor from initializer list
//*** For you to implement
Forward_list(std::initializer_list input);
// Add an element to the front of the list
//*** For you to implement
void push_front(const T& data);
// Remove the first element of the list
//*** For you to implement
void pop_front();
// Return the data held in the first item of the list
// This function should not change the list, which is
// why it is declared const
//*** For you to implement
T front() const;
// Print out all the data in the list in sequence
//*** For you to implement
void display() const;
// Outputs if the list is empty or not
// Implemented for you
bool empty() const;
// outputs the size of the list
// Implemented for you, but your code should properly
// update the size_ member variable as needed
unsigned size() const;
// methods related to sorting
// merge two sorted lists, *this and other
//*** For you to implement
void merge(Forward_list& other);
// split *this into its first half, which becomes the new
*this,
// and its second half which is returned
//*** For you to implement
Forward_list split();
// The sort function uses the helper functions
// merge and split that you write
// You do not need to modify sort itself
void sort();
private:
// sort is implemented via a recursive merge sort
// You do not need to modify this function
void merge_sort(Forward_list&);
};
// Default Constructor
// You do not need to change this
template
Forward_list::Forward_list()
{
}
// Destructor
// The destructor is implemented for you
template
Forward_list::~Forward_list()
{
while(head_ != nullptr)
{
Node* tmp = head_;
head_ = head_->next;
delete tmp;
--size_;
}
}
// Copy constructor
// ***For you to implement
// The copy constructor takes as argument a const reference to
a
// another Forward_list "other"
// The const means that the function should not modify other
// The function should make a "deep copy" of the other list,
// that is create a new node for every node in other and copy
// the data of other into these new nodes.
template
Forward_list::Forward_list(const Forward_list& other)
{
}
// Constructor from initializer list
// ***For you to implement
// This implements the functionality you see with, for
example,
// std::forward_list my_list = {1,2,3}
// which creates a new linked list where the first node holds 1,
second 2, and
// third 3.
// The {1,2,3} here is of type std::initializer_list and you
// see this is the argument to this constructor (with data of type
T
// rather than just int).
// You can access the elements of a std::initializer_list via an
iterator
// for example you can cycle through all the elements with
// for(auto it = input.begin(); it!= input.end(); ++it){Do
something with *it}
template
Forward_list::Forward_list(std::initializer_list input)
{
}
// Add element to front of list
// ***For you to implement
template
void Forward_list::push_front(const T& data)
{
}
// Remove the front element of the list
// If the list is empty don't do anything
// ***For you to implement
template
void Forward_list::pop_front()
{
}
// Return the data in the front element of the list
// If the list is empty the behaviour is undefined:
// you can return an arbitrary value, but don't segfault
// ***For you to implement
template
T Forward_list::front() const
{
// dummy return value, change this
return 0;
}
// Print out the list
// ***For you to implement
template
void Forward_list::display() const
{
}
// Outputs if the list is empty or not
// Implemented for you
template
bool Forward_list::empty() const
{
return (head_ == nullptr);
}
// Returns the size of the list
// It is implemented for you but you need to correctly
// update the size_ variable in your code as needed
// Note that std::forward_list actually does not have a size
function
template
unsigned Forward_list::size() const
{
return size_;
}
// the split function splits *this into its first half, which
becomes
// the new *this, and its second half which is returned
// if the the size of *this is n, then after split the size of
*this
// should be ceiling(n/2), and the size of the returned list should
be
// floor(n/2)
// As an example, if *this is of the form
// head_ -> a -> b -> c -> d -> nullptr
// then after split *this should be
// head_ -> a -> b -> nullptr
// and you should a return a Forward_list other where
// other.head_ = c -> d -> nullptr
// Don't forget to update the size_ variable of this and
other
// You do not need to create any new nodes for this function,
// just change pointers.
// ***For you to implement
template
Forward_list Forward_list::split()
{
// dummy return value, change this
return *this;
}
// Merging two sorted lists
// For this function it is assumed that both *this and the
// input Forward_list other are already sorted
// The function merges the two lists, and the merger becomes
// the new *this
// You do not need to create any new nodes in this
function,
// just update pointers.
// Set other to be an empty list at the end of the function
//***For you to implement
template
void Forward_list::merge(Forward_list& other)
{
}
// recursive implementation of merge_sort
// you do not need to change this function
template
void Forward_list::merge_sort(Forward_list& my_list)
{
if(my_list.size() == 0 || my_list.size() == 1)
{
return;
}
Forward_list second = my_list.split();
merge_sort(my_list);
merge_sort(second);
my_list.merge(second);
}
// sorts the list by calling merge_sort
// once your merge and split functions are working
// sort should automatically work
// you do not need to change this function
template
void Forward_list::sort()
{
merge_sort(*this);
}
my_forward_list.cpp
#include <iostream>
#include <ctime>
#include <vector>
#include <forward_list>
#include <algorithm>
#include "my_forward_list.hpp"
#include "tests.hpp"
int main()
{
Forward_list<int> my_list;
Tests tester;
// Here are all the tests run during the marking.
// You can uncomment them as you implement the methods
// test_size_initialization should work from the scaffold
tester.test_size_initialization();
// test_push_pop requires: push_front, front, pop_front, and
the
// size_ variable incremented correctly
//tester.test_push_pop();
// test_null_copy requires the copy constructor method
only
//tester.test_null_copy();
// test_copy_constructor requires push_front, front, pop_front
and copy constructor
//tester.test_copy_constructor();
// test_initializer_list requires initializer list constructor,
front, and pop_front
//tester.test_initializer_list();
// test_initializer_list_str requires the same as
test_initializer_list
//tester.test_initializer_list_str();
// test_merge requires push_front, front, pop_front and
merge
//tester.test_merge();
// same as test_merge
//tester.test_merge_edge_cases();
// test_split requires push_front, front, pop_front, copy
constructor and split
//tester.test_split();
// test_split_and_merge requires push_front, front, pop_front,
copy constructor, merge and split
//tester.test_split_and_merge();
// test_sort requires push_front, front, pop_front, copy
constructor, merge and split
//tester.test_sort();
return 0;
}