Homework SourseC problem Part 1 Recursive Print 40 pts Please write the rec
C++ problem
Part 1: Recursive Print (40 pts)
Please write the recursive List reverse print function, whose iterative version we wrote in class.
Below are the function signatures for the functions you are going to need:
public:
/**Additional Operations*/
void print_reverse();
//Wrapper function that calls the reverse helper function to print a list in reverse
//prints nothing if the List is empty
private:
void reverse(Nodeptr node);
//Helper function for the public printReverse() function.
//Recursively prints the data in a List in reverse.
Why do we need the private helper function here?
Since we are going to be reversing our list node by node, in a recursive fashion, we want to pass a one node at a time to our reverse function.
However, since our nodes are private, we cannot access them if we call the function inside of main.
Add these function signatures to your List.h file along with your other function prototypes inside the class definition.
Make sure that you place the reverse function inside the private portion of your List class definition and the print_reverse function prototype to the public portion of your List class definition.
Now, implement these two functions inside of List.h, under your section for additional operations.
Important: Test each function carefully inside of your ListTest.cpp to make sure that it is working properly.
Part 2: Adding an Index to Your List Nodes (20 pts)
Next, you will add the following functions to your List.h
/**Accessor Functions*/
int get_index();
//Indicates the index of the Node where the iterator is currently pointing
//Nodes are numbered from 1 to length of the list
//Pre: length != 0
//Pre: !off_end()
...
int List::get_index()
{
//Implement the function here
}
/**Manipulation Procedures*/
void scroll_to_index(int index);
//Moves the iterator to the node whose index is specified by the user
//Pre: length != 0
...
void scroll_to_index(int index)
{
//Implement function here
}
Part 3: Implementing Search as Part of Your List (40 pts)
Now, we are going to add two search functions to our List so that we can search for elements in our List.
The first of these functions is going to be a simple linear search function.
You will need to add the following function prototype and function definition to your List.h:
/**Additional Operations*/
int linear_search(listitem item);
//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
//Returns -1 if the element is not in the List
//Pre: length != 0
...
int List::linear_search(listitem item)
{
//Implement the function here
}
You are also going to add a function to perform recursive binary search on your List.
You will need to add the following function prototype and function definition to your List.h:
int binary_search(int low, int high, listitem item);
//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
//Pre: length != 0
//Pre: List is sorted (must test on a sorted list)
...
int List::binary_search(int low, int high, listitem item)
{
//Implement the function here
}
Important: For credit, you must implement the recursive version of binary search.
This is my current List.h file:
#ifndef LIST_H_
#include //for NULL
#include
#include
#include
using namespace std;
template
class List {
private:
struct Node {
listitem data;
Node* next;
Node* previous;
Node(listitem data) :
next(NULL), previous(NULL), data(data) {
}
};
typedef struct Node* NodePtr;
NodePtr start;
NodePtr end;
NodePtr cursor;
int length;
void reverse(NodePtr node);
//Helper function for the public printReverse() function.
//Recursively prints the data in a List in reverse.
public:
/**Constructors and Destructors*/
List();
//Default constructor; initializes and empty list
//Postcondition: list is initialized or is empty
~List();
//Destructor. Frees memory allocated to the list
//Postcondition: Memory in the list is deleted
List(const List &list);
//Copy construcor. Initializes list to have the same elements as another list
//Postcondition: Other lists have same elements as the main list
/**Accessors*/
listitem get_start();
//Returns the first element in the list
//Precondition: first element must not be empty
listitem get_end();
//Returns the last element in the list
//Precondition: last element must not be empty
listitem get_cursor();
//Returns the element pointed to by the iterator
//Precondition: the element pointed to by the iterator must not be empty
bool is_empty();
//Determines whether a list is empty.
bool off_end();
//Determines if the iterator is off the end of the list (i.e. whether cursor is NULL)
int get_length();
//Returns the length of the list
/**Manipulation Procedures*/
void begin_cursor();
//Moves the iterator to point to the first element in the list
//If the list is empty, the iterator remains NULL
//Postcondition: the iterator point to the first element in the list
void add_cursor(listitem data);
//Inserts a new element into the list in the position after the iterator
//Precondition: the iterator must point to an element
//Postcondition: a new element is inserted in the position after the iterator
void remove_end();
//Removes the value of the last element in the list
//Precondition: last element is not a null object
//Postcondition: the the value of the last element in the list is removed
void remove_start();
//Removes the value of the first element in the list
//Precondition: first element is not a null object
//Postcondition: the value of the first element in the list is removed
void add_end(listitem data);
//Inserts a new element at the end of the list
//If the list is empty, the new element becomes both start and end
//Postcondition: a new element is inserted at the end of the list
void add_start(listitem data);
//Inserts a new element at the start of the list
//If the list is empty, the new element becomes both start and end
//Postcondition: a new element is inserted at the start of the list
void remove_cursor();
//Removes the element pointed at by the iterator
//Precondition: the element pointed at by the iterator is not a null object
//Postcondition: the element pointed at by the iterator is removed
void move_cursor();
//Moves the iterator forward by one element in the list
//Precondition: the next element is not a null object
//Postcondition: the iterator moves forward by one element in the list
/**Additional List Operations*/
void print();
//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
/**Additional Operations*/
void print_reverse();
//Wrapper function that calls the reverse helper function to print a list in reverse
//prints nothing if the List is empty
};
template
List::List() :
start(NULL), end(NULL), cursor(NULL), length(0) {
}
template
List::~List() {
cursor = start;
NodePtr temp;
while (cursor != NULL) {
temp = cursor->next;
delete cursor;
cursor = temp;
}
}
template
List::List(const List &list) :
length(list.length) {
if (list.start == NULL) //If the original list is empty, make an empty list for this list
{
start = end = cursor = NULL;
} else {
start = new Node(list.start->data); //using second Node constructor
NodePtr temp = list.start; //set a temporary node pointer to point at the start of the original list
cursor = start; //set iterator to point to start of the new list
while (temp->next != NULL) {
temp = temp->next; //advance up to the next node in the original list
cursor->next = new Node(temp->data); //using node constructor to create a new node with copy of data
cursor = cursor->next; //advance to this new node
}
end = cursor; //Why do I need this line of code?
cursor = NULL;
}
}
template
void List::print() {
NodePtr temp = start; //create a temporary iterator
while (temp != NULL) {
//What two lines of code go here?
cout << temp->data << \" \";
temp = temp->next;
//Hint: One statement should contain a cout
}
cout << endl; //What does this do?
}
template
void List::add_start(listitem data) {
if (length == 0) //Why is this necessary?
{
start = new Node(data);
end = start;
} else {
NodePtr N = new Node(data); //create the new node by calling the node constructor
N->next = start; //set the new node\'s next field to point to the start
start->previous = N;
start = N; //make the start be the new node
}
length++;
}
template
void List::add_end(listitem data) {
if (length == 0) {
start = new Node(data);
end = start;
} else {
NodePtr N = new Node(data); //create the new node by calling the node constructor
end->next = N;
N->previous = end;
end = N;
}
length++;
}
template
bool List::is_empty() {
return (length == 0);
}
template
int List::get_length() {
return length;
}
template
listitem List::get_start() {
assert(start != NULL);
return start->data;
}
template
listitem List::get_end() {
assert(end != NULL);
return end->data;
}
template
void List::begin_cursor() {
cursor = start;
}
template
listitem List::get_cursor() {
assert(cursor != NULL);
return cursor->data;
}
template
void List::move_cursor() {
assert(cursor != NULL);
cursor = cursor->next;
}
template
bool List::off_end() {
return (cursor == NULL);
}
template
void List::remove_start() {
assert(length != 0);
if (length == 1) {
delete start;
start = end = cursor = NULL;
length = 0;
} else {
if (cursor == start)
cursor = NULL;
start = start->next;
delete start->previous;
start->previous = NULL;
length--;
}
}
template
void List::remove_end() {
assert(length != 0);
if (length == 1) {
delete end;
start = end = cursor = NULL;
length = 0;
} else {
if (cursor == end)
cursor = NULL;
end = end->previous;
delete end->next;
end->next = NULL;
length--;
}
}
template
void List::add_cursor(listitem data) {
assert(!off_end());
if (cursor == end) {
add_end(data);
} else {
NodePtr newNode = new Node(data);
newNode->next = cursor->next;
newNode->previous = cursor;
cursor->next->previous = newNode;
cursor->next = newNode;
length++;
}
}
template
void List::remove_cursor() {
assert(cursor != NULL);
if (cursor == start) {
remove_start();
} else if (cursor == end) {
remove_end();
} else {
cursor->previous->next = cursor->next;
cursor->next->previous = cursor->previous;
delete cursor;
cursor = NULL;
length--;
}
}
template
bool List::operator==(const List& list) {
if (length != list.length)
return false;
NodePtr temp1 = start;
NodePtr temp2 = list.start;
while (temp1 != NULL) {
if (temp1->data != temp2->data)
return false;
temp1 = temp1->next;
temp2 = temp2->next;
}
return true;
}
#define LIST_H_
#endif /* LIST_H_ */
Solution
Lisht.h
#include \"stdafx.h\"
#include <iostream>
#include <string>
using namespace std;
template<class listitem>
class List {
private:
struct Node {
listitem data;
Node* next;
Node* previous;
Node(listitem data) :
next(NULL), previous(NULL), data(data) {
}
};
typedef struct Node* NodePtr;
NodePtr start;
NodePtr end;
NodePtr cursor;
int length;
void reverse(NodePtr node);
public:
List();
~List();
List(const List &list);
listitem get_start();
listitem get_end();
listitem get_cursor();
bool is_empty();
bool off_end();
int get_length();
void begin_cursor();
void add_cursor(listitem data);
void remove_end();
void remove_start();
void add_end(listitem data);
void add_start(listitem data);
void remove_cursor();
void move_cursor();
void print();
bool operator==(const List &list);
// Answer
void print_reverse();
int get_index();
void scroll_to_index(int index);
int linear_search(listitem item);
int binary_search(int low, int high, listitem item);
void sort(NodePtr small);
};
List.cpp
#include \"stdafx.h\"
#include\"List.h\"
template<class listitem>
List<listitem>::List() :
start(NULL), end(NULL), cursor(NULL), length(0)
{
}
template<class listitem>
List<listitem>::~List() {
cursor = start;
NodePtr temp;
while (cursor != NULL) {
temp = cursor->next;
delete cursor;
cursor = temp;
}
}
template<class listitem>
List<listitem>::List(const List &list) :
length(list.length) {
if (list.start == NULL) //If the original list is empty, make an empty list for this list
{
start = end = cursor = NULL;
}
else {
start = new Node(list.start->data); //using second Node constructor
NodePtr temp = list.start; //set a temporary node pointer to point at the start of the original list
cursor = start; //set iterator to point to start of the new list
while (temp->next != NULL) {
temp = temp->next; //advance up to the next node in the original list
cursor->next = new Node(temp->data); //using node constructor to create a new node with copy of data
cursor = cursor->next; //advance to this new node
}
end = cursor; //Why do I need this line of code?
cursor = NULL;
}
}
template<class listitem>
void List<listitem>::print() {
NodePtr temp = start; //create a temporary iterator
while (temp != NULL) {
//What two lines of code go here?
cout << temp->data << \" \";
temp = temp->next;
//Hint: One statement should contain a cout
}
cout << endl; //What does this do?
}
template<class listitem>
void List<listitem>::add_start(listitem data) {
if (length == 0) //Why is this necessary?
{
start = new Node(data);
end = start;
}
else {
NodePtr N = new Node(data); //create the new node by calling the node constructor
N->next = start; //set the new node\'s next field to point to the start
start->previous = N;
start = N; //make the start be the new node
}
length++;
}
template<class listitem>
void List<listitem>::add_end(listitem data) {
if (length == 0) {
start = new Node(data);
end = start;
}
else {
NodePtr N = new Node(data); //create the new node by calling the node constructor
end->next = N;
N->previous = end;
end = N;
}
length++;
}
template<class listitem>
bool List<listitem>::is_empty() {
return (length == 0);
}
template<class listitem>
int List<listitem>::get_length() {
return length;
}
template<class listitem>
listitem List<listitem>::get_start() {
assert(start != NULL);
return start->data;
}
template<class listitem>
listitem List<listitem>::get_end() {
assert(end != NULL);
return end->data;
}
template<class listitem>
void List<listitem>::begin_cursor() {
cursor = start;
}
template<class listitem>
listitem List<listitem>::get_cursor() {
assert(cursor != NULL);
return cursor->data;
}
template<class listitem>
void List<listitem>::move_cursor() {
assert(cursor != NULL);
cursor = cursor->next;
}
template<class listitem>
bool List<listitem>::off_end() {
return (cursor == NULL);
}
template<class listitem>
void List<listitem>::remove_start() {
assert(length != 0);
if (length == 1) {
delete start;
start = end = cursor = NULL;
length = 0;
}
else {
if (cursor == start)
cursor = NULL;
start = start->next;
delete start->previous;
start->previous = NULL;
length--;
}
}
template<class listitem>
void List<listitem>::remove_end() {
assert(length != 0);
if (length == 1) {
delete end;
start = end = cursor = NULL;
length = 0;
}
else {
if (cursor == end)
cursor = NULL;
end = end->previous;
delete end->next;
end->next = NULL;
length--;
}
}
template<class listitem>
void List<listitem>::add_cursor(listitem data) {
assert(!off_end());
if (cursor == end) {
add_end(data);
}
else {
NodePtr newNode = new Node(data);
newNode->next = cursor->next;
newNode->previous = cursor;
cursor->next->previous = newNode;
cursor->next = newNode;
length++;
}
}
template<class listitem>
void List<listitem>::remove_cursor() {
assert(cursor != NULL);
if (cursor == start) {
remove_start();
}
else if (cursor == end) {
remove_end();
}
else {
cursor->previous->next = cursor->next;
cursor->next->previous = cursor->previous;
delete cursor;
cursor = NULL;
length--;
}
}
template<class listitem>
bool List<listitem>::operator==(const List& list) {
if (length != list.length)
return false;
NodePtr temp1 = start;
NodePtr temp2 = list.start;
while (temp1 != NULL) {
if (temp1->data != temp2->data)
return false;
temp1 = temp1->next;
temp2 = temp2->next;
}
return true;
}
template<class listitem>
void List<listitem>::reverse(NodePtr list)
{
if (list) {
reverse(list->next);
cout << list->data << endl;
}
}
template<class listitem>
void List<listitem>::print_reverse()
{
reverse(start);
}
template<class listitem>
int List<listitem>::get_index()
{
if (off_end() == true)
{
cout << \"Error! Iterator is not pointing to anything...\" << endl;
return 0;
}
else
{
int count = 1;
NodePtr temp = start;
while (temp != cursor)
{
count++;
temp = temp->next;
}
return count;
}
}
template<class listitem>
void List<listitem>::scroll_to_index(int index)
{
int max = get_length();
for (int j = index; j <= max; j++)
{
get_cursor(j);
if (cursor == NULL)
cout << \"Calling scroll when iterator is NULL\" << endl;
else
cursor = cursor->next;
}
}
template<class listitem>
int List<listitem>::linear_search(listitem item)
{
NodePtr temp = start;
int count = 1;
bool valFound = false;
while (temp != NULL)
{
if (temp->data == item)
{
valFound = true;
temp = NULL;
}
else
{
count++;
temp = temp->next;
}
}
if (valFound == false)
{
cout << \"Error. Item not found\" << endl;
return -1;
}
else
return count;
}
