Modify 3 functions and write 3 functions using a recursive approach as well as t
ID: 3607318 • Letter: M
Question
Modify 3 functions and write 3 functions using a recursive approach as well as test in the test file to make sure everything is working. The functions to write are at the bottom of the node.h and node.cpp file. Asterisks boxes are above the functions that need to be modified and written
MODIFY:
list_length and list_search (regular and const versions)
CREATE:
void display_list(const node* head_ptr);
void rev_display_list(const node* head_ptr);
void delete_list(node* head_ptr);
*****************NODE.H FILE FUNCTION DEFINITIONS***************************
#ifndef MAIN_SAVITCH_NODE_H
#define MAIN_SAVITCH_NODE_H
#include // Provides size_t
class node {
public:
// ALIAS
using value_type = double;
// CONSTRUCTOR
node(const value_type& init_data = value_type(),
node* init_link = nullptr) {
data_field = init_data; link_field = init_link;
}
// Member functions to set the data and link fields:
void set_data(const value_type& new_data) { data_field = new_data; }
void set_link(node* new_link) { link_field = new_link; }
// Constant member function to retrieve the current data:
value_type data() const { return data_field; }
// Two slightly different member functions to retreive
// the current link:
// constant pointer cannot change referenced node
const node* link() const { return link_field; }
// pointer can change referenced node
node* link() { return link_field; }
private:
value_type data_field;
node* link_field;
};
// FUNCTIONS for the linked list toolkit
std::size_t list_length(const node* head_ptr);
void list_head_insert(node*& head_ptr, const node::value_type& entry);
void list_insert(node* previous_ptr, const node::value_type& entry);
node* list_search(node* head_ptr, const node::value_type& target);
const node* list_search(const node* head_ptr, const node::value_type& target);
node* list_locate(node* head_ptr, std::size_t position);
const node* list_locate(const node* head_ptr, std::size_t position);
void list_head_remove(node*& head_ptr);
void list_remove(node* previous_ptr);
void list_clear(node*& head_ptr);
void list_copy(const node* source_ptr, node*& head_ptr, node*& tail_ptr);
//**************************************************************
// ***ADDITIONAL RECURSIVE FUNCTIONS TO ADD
//***************************************************************
void display_list(const node* head_ptr);
void rev_display_list(const node* head_ptr);
void delete_list(node* head_ptr);
#endif
*****************NODE.CPP FILE TO MODIFY************
#include "node.h"
#include
#include // Provides assert
#include // Provides size_t
using namespace std;
//**************************************
//***AAA***modify to recursive version
//**************************************
// return number of nodes in list
size_t list_length(const node* head_ptr)
{
const node *cursor;
size_t answer;
answer = 0;
for (cursor = head_ptr; cursor != nullptr; cursor = cursor->link())
++answer;
return answer;
}
// insert new node with data at beginning of list
// NOTE pass by reference for head_ptr to change value
void list_head_insert(node*& head_ptr, const node::value_type& entry)
{
head_ptr = new node(entry, head_ptr);
}
// insert new node with data before given node
void list_insert(node* previous_ptr, const node::value_type& entry)
{
node *insert_ptr;
insert_ptr = new node(entry, previous_ptr->link());
previous_ptr->set_link(insert_ptr);
}
//************************************
//***AAA***modify to recursive version
//************************************
// search list for given item, return node pointer to first found item or nullptr
node* list_search(node* head_ptr, const node::value_type& target)
{
node *cursor;
for (cursor = head_ptr; cursor != nullptr; cursor = cursor->link())
if (target == cursor->data())
return cursor;
return nullptr;
}
//************************************
//***AAA***modify to recursive version
//************************************
// search list for given item, return constant node pointer to first found item or nullptr
const node* list_search(const node* head_ptr, const node::value_type& target)
{
const node *cursor;
for (cursor = head_ptr; cursor != nullptr; cursor = cursor->link())
if (target == cursor->data())
return cursor;
return nullptr;
}
// locate node at given position and return node pointer or nullptr
node* list_locate(node* head_ptr, size_t position)
{
// Library facilities used: cassert
node *cursor;
size_t i;
assert(0 < position);
cursor = head_ptr;
for (i = 1; (i < position) && (cursor != nullptr); i++)
cursor = cursor->link();
return cursor;
}
// locate node at given position and return constant node pointer or nullptr
const node* list_locate(const node* head_ptr, size_t position)
{
// Library facilities used: cassert, cstdlib
const node *cursor;
size_t i;
assert(0 < position);
cursor = head_ptr;
for (i = 1; (i < position) && (cursor != nullptr); i++)
cursor = cursor->link();
return cursor;
}
// remove node at beginning
// NOTE pass by reference for head_ptr to change value
void list_head_remove(node*& head_ptr)
{
node *remove_ptr;
remove_ptr = head_ptr;
head_ptr = head_ptr->link();
delete remove_ptr;
}
// remove node linked to given node pointer
void list_remove(node* previous_ptr)
{
node *remove_ptr;
remove_ptr = previous_ptr->link();
previous_ptr->set_link(remove_ptr->link());
delete remove_ptr;
}
// release memory for all nodes in list
// NOTE pass by reference for head_ptr to change value
void list_clear(node*& head_ptr)
{
while (head_ptr != nullptr)
list_head_remove(head_ptr);
}
// copy all nodes from source list to target head and tail
// NOTE pass by reference for head_ptr and tail_ptr to change values
void list_copy(const node* source_ptr, node*& head_ptr, node*& tail_ptr)
{
head_ptr = nullptr;
tail_ptr = nullptr;
// Handle the case of the empty list.
if (source_ptr == nullptr)
return;
// Make the head node for the newly created list, and put data in it.
list_head_insert(head_ptr, source_ptr->data());
tail_ptr = head_ptr;
// Copy the rest of the nodes one at a time, adding at the tail of new list.
source_ptr = source_ptr->link();
while (source_ptr != nullptr)
{
list_insert(tail_ptr, source_ptr->data());
tail_ptr = tail_ptr->link();
source_ptr = source_ptr->link();
}
}
//**********************************
//***AAA***added recursive function
//**********************************
void display_list(const node* head_ptr)
{
if (head_ptr != nullptr)
{
cout << head_ptr->data() << endl;
display_list(head_ptr->link());
}
}
void rev_display_list(const node* head_ptr)
{
}
void delete_list(node* head_ptr)
{
}
*********TESTING FILE FOR FUNCTIONS**************************
#include
#include "node.h"
using namespace std;
int main() {
// identify node values
double ditems[5] = { 5.5, 33.3, 22.2, 77.7, 11.1 };
int arrSize = sizeof(ditems) / sizeof(double);
// create linked list
node* head_ptr = nullptr; // empty list
// add items to list
for (int i = 0; i < arrSize; i++) {
list_head_insert(head_ptr, ditems[i]);
}
// LAB#8-->Test Recursive Toolkit Functions
// display list length
cout << "The number of items in list is " << list_length(head_ptr) << endl;
// display list
cout << "List items in order:" << endl;
display_list(head_ptr);
// display list
cout << "List items in reverse order:" << endl;
rev_display_list(head_ptr);
// searching list with non-constant function
double dval;
cout << " Searching with non-constant recursive function..." << endl;
cout << "Input a value to search (0 to end): ";
cin >> dval;
while (dval != 0.0) {
node* toFind = list_search(head_ptr, dval);
if (toFind != nullptr)
cout << toFind->data() << " has been found!" << endl;
else cout << dval << " has NOT been found!" << endl;
cout << "Input a value to search (0 to end): ";
cin >> dval;
}
// searching list with constant function
cout << " Searching with constant recursive function..." << endl;
cout << "Input a value to search (0 to end): ";
cin >> dval;
while (dval != 0.0) {
const node* toFind = list_search(head_ptr, dval);
if (toFind != nullptr)
cout << toFind->data() << " has been found!" << endl;
else cout << dval << " has NOT been found!" << endl;
cout << "Input a value to search (0 to end): ";
cin >> dval;
}
// release the memory
delete_list(head_ptr);
return EXIT_SUCCESS;
}
Explanation / Answer
Given below is teh completed code for node.cpp file.
Hope it helps. If it did, please do rate the answer .Thank you.
#include "node.h"
#include <iostream>
#include <cassert> // Provides assert
#include <cstddef>// Provides size_t
using namespace std;
//**************************************
//***AAA***modify to recursive version
//**************************************
// return number of nodes in list
size_t list_length(const node* head_ptr)
{
if(head_ptr == nullptr)
return 0;
else
return list_length(head_ptr->link()) + 1;
}
// insert new node with data at beginning of list
// NOTE pass by reference for head_ptr to change value
void list_head_insert(node*& head_ptr, const node::value_type& entry)
{
head_ptr = new node(entry, head_ptr);
}
// insert new node with data before given node
void list_insert(node* previous_ptr, const node::value_type& entry)
{
node *insert_ptr;
insert_ptr = new node(entry, previous_ptr->link());
previous_ptr->set_link(insert_ptr);
}
//************************************
//***AAA***modify to recursive version
//************************************
// search list for given item, return node pointer to first found item or nullptr
node* list_search(node* head_ptr, const node::value_type& target)
{
if(head_ptr == nullptr)
return nullptr;
else if(head_ptr->data() == target)
return head_ptr;
else
return list_search(head_ptr->link(), target);
}
//************************************
//***AAA***modify to recursive version
//************************************
// search list for given item, return constant node pointer to first found item or nullptr
const node* list_search(const node* head_ptr, const node::value_type& target)
{
if(head_ptr == nullptr)
return nullptr;
else if(head_ptr->data() == target)
return head_ptr;
else
return list_search(head_ptr->link(), target);
}
// locate node at given position and return node pointer or nullptr
node* list_locate(node* head_ptr, size_t position)
{
// Library facilities used: cassert
node *cursor;
size_t i;
assert(0 < position);
cursor = head_ptr;
for (i = 1; (i < position) && (cursor != nullptr); i++)
cursor = cursor->link();
return cursor;
}
// locate node at given position and return constant node pointer or nullptr
const node* list_locate(const node* head_ptr, size_t position)
{
// Library facilities used: cassert, cstdlib
const node *cursor;
size_t i;
assert(0 < position);
cursor = head_ptr;
for (i = 1; (i < position) && (cursor != nullptr); i++)
cursor = cursor->link();
return cursor;
}
// remove node at beginning
// NOTE pass by reference for head_ptr to change value
void list_head_remove(node*& head_ptr)
{
node *remove_ptr;
remove_ptr = head_ptr;
head_ptr = head_ptr->link();
delete remove_ptr;
}
// remove node linked to given node pointer
void list_remove(node* previous_ptr)
{
node *remove_ptr;
remove_ptr = previous_ptr->link();
previous_ptr->set_link(remove_ptr->link());
delete remove_ptr;
}
// release memory for all nodes in list
// NOTE pass by reference for head_ptr to change value
void list_clear(node*& head_ptr)
{
while (head_ptr != nullptr)
list_head_remove(head_ptr);
}
// copy all nodes from source list to target head and tail
// NOTE pass by reference for head_ptr and tail_ptr to change values
void list_copy(const node* source_ptr, node*& head_ptr, node*& tail_ptr)
{
head_ptr = nullptr;
tail_ptr = nullptr;
// Handle the case of the empty list.
if (source_ptr == nullptr)
return;
// Make the head node for the newly created list, and put data in it.
list_head_insert(head_ptr, source_ptr->data());
tail_ptr = head_ptr;
// Copy the rest of the nodes one at a time, adding at the tail of new list.
source_ptr = source_ptr->link();
while (source_ptr != nullptr)
{
list_insert(tail_ptr, source_ptr->data());
tail_ptr = tail_ptr->link();
source_ptr = source_ptr->link();
}
}
//**********************************
//***AAA***added recursive function
//**********************************
void display_list(const node* head_ptr)
{
if (head_ptr != nullptr)
{
cout << head_ptr->data() << endl;
display_list(head_ptr->link());
}
}
void rev_display_list(const node* head_ptr)
{
if(head_ptr != nullptr)
{
rev_display_list(head_ptr->link());
cout << head_ptr->data() << endl;
}
}
void delete_list(node* head_ptr)
{
if(head_ptr != nullptr)
{
delete_list(head_ptr->link());
delete head_ptr;
}
}
output
=====
The number of items in list is 5
List items in order:
11.1
77.7
22.2
33.3
5.5
List items in reverse order:
5.5
33.3
22.2
77.7
11.1
Searching with non-constant recursive function...
Input a value to search (0 to end): 22.2
22.2 has been found!
Input a value to search (0 to end): 10
10 has NOT been found!
Input a value to search (0 to end): 0
Searching with constant recursive function...
Input a value to search (0 to end): 5.5
5.5 has been found!
Input a value to search (0 to end): 11.1
11.1 has been found!
Input a value to search (0 to end): 33.3
33.3 has been found!
Input a value to search (0 to end): 0
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.