Hello, I need this to be programmed only using C++ ( please do not write the cod
ID: 3800726 • Letter: H
Question
Hello,
I need this to be programmed only using C++ ( please do not write the codes... type only )
Design and code your own single liked list to hold a list of integers using forward method.
Use the C++ “struct” structure to create your nodes. Node position numbering should start with one.
Your program should include the main program to test and demonstrate one function for each list operations including:
Main with menu (20 points)
AddNode – Add a node at start of the list (10 points)
PrintList – Print the list one node per line (10 points)
AppendNode – Add a node at end of the list (10 points)
InsertNode – Inserts a node at any position in the list (10 points)
DeleteNode – Deletes a node from any position in the list (10 points)
DeleteList – Deletes all nodes from the list (10 points)
SearchList – Search a list for a value and if found returns True otherwise False (10 points)
ResverseList – Reverses the order of items in the list (10 points)
SortList – Sorts the list in ascending order (10 points)
Explanation / Answer
#include <string>
#include <cassert>
#include <vector>
#include <functional>
#include <iostream>
namespace ds {
struct qlist {
struct node_t{
node_t* prev = nullptr;
int data;
node_t(int data) : data(data), prev(nullptr){ }
virtual ~node_t(){
if(prev != nullptr){
delete prev;
prev = nullptr;
}
}
};
private:
node_t* rear = nullptr;
public:
/* add element to list on front
*/
void AddNode(int data){
if(rear == nullptr){
rear = new node_t(data);
}
else{
node_t* curr = rear;
while(curr->prev!=nullptr)
curr = curr->prev;
curr->prev = new node_t(data);
}
}
void AppendNode(int data){
if(rear == nullptr){
rear = new node_t(data);
}
else{
node_t* curr = new node_t(data);
curr->prev = rear;
}
}
void InsertNode(int position, int data){
if((rear==nullptr) && (position==1)){
AppendNode(data);
}
else{
node_t* curr = rear;
for(int i = 0; i < position; ++i){
if(curr == nullptr){
return;
}
}
if(curr->prev == nullptr){
curr->prev = new node_t(data);
}
else{
node_t* temp = new node_t(data);
temp->prev = curr->prev;
curr->prev = temp;
}
}
}
void DeleteNode(int position){
if(position == 1){
if(rear == nullptr){
return;
}
else{
rear->prev = nullptr;
delete rear;
rear = rear->prev;
}
}
node_t* curr = rear;
for(int i = 2; i < position; ++i){
if(curr == nullptr){
return;
}
}
if(curr!=nullptr){
node_t* temp = curr->prev;
curr->prev = curr->prev->prev;
temp->prev = nullptr;
delete temp;
}
}
void DeleteList(){
delete rear;
rear = nullptr;
}
private:
void traverse_list(const node_t* crear, std::function<void(int)> fn){
while(crear!=nullptr){
fn(crear->data);
crear = crear->prev;
}
}
public:
void PrintList(){
traverse_list(rear, [](int data){
std::cout << data << " ";
});
}
bool SearchList(int data){
node_t* crear = rear;
while(crear!=nullptr){
if(crear->data==data){
return true;
}
crear = crear->prev;
}
return false;
}
void ReverseList(){
node_t* curr = rear;
if((curr == nullptr)||(curr->prev==nullptr)){
return;
}
node_t* rrear = curr;
while(curr->prev!=nullptr){
node_t* temp = curr->prev;
curr->prev = curr->prev->prev;
temp->prev = rrear;
rrear = temp;
}
rear = rrear;
}
private:
void split(node_t* source,
node_t** front, node_t** back)
{
node_t* fast;
node_t* slow;
if (source == nullptr || source->prev==nullptr)
{
*front = source;
*back = nullptr;
}
else
{
slow = source;
fast = source->prev;
while (fast != nullptr)
{
fast = fast->prev;
if (fast != nullptr)
{
slow = slow->prev;
fast = fast->prev;
}
}
*front = source;
*back = slow->prev;
slow->prev = nullptr;
}
}
node_t* sorted_merge(node_t* a, node_t* b)
{
node_t* result = nullptr;
if (a == nullptr)
return(b);
else if (b==nullptr)
return(a);
if (a->data <= b->data)
{
result = a;
result->prev = sorted_merge(a->prev, b);
}
else
{
result = b;
result->prev = sorted_merge(a, b->prev);
}
return(result);
}
void SortList_Helper(node_t** crear){
node_t* rear = *crear;
node_t* a;
node_t* b;
if ((rear == nullptr) || (rear->prev == nullptr))
{
return;
}
split(rear, &a, &b);
SortList_Helper(&a);
SortList_Helper(&b);
*crear = sorted_merge(a, b);
}
public:
void SortList(){
SortList_Helper(&rear);
}
};
void test_list(){
qlist q;
assert(q.SearchList(1)==false);
/* empty list verification*/
std::vector<int> xs = {1,11,191, 87, 78, 98};
for(auto x: xs){
q.AddNode(x);
}
/* first item*/
assert(q.SearchList(xs[0])==true);
/* middle item*/
assert(q.SearchList(xs[xs.size()/2])==true);
/* last item*/
assert(q.SearchList(xs[xs.size()-1])==true);
assert(q.SearchList(5100)==false);
q.PrintList();
/*
Reverse
*/
q.ReverseList();
q.PrintList();
q.InsertNode(2,1326);
q.PrintList();
q.DeleteNode(2);
q.PrintList();
q.SortList();
q.PrintList();
q.DeleteList();
q.PrintList();
}
}
int main(int argc, const char * argv[]) {
ds::test_list();
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.