#include<iostream> #include <string> using namespace::std; const int NUMBER_NAME
ID: 3796914 • Letter: #
Question
#include<iostream>
#include <string>
using namespace::std;
const int NUMBER_NAMES = 19;
const string names[NUMBER_NAMES] = { " printForward"," printReverse"," length"," lengthR"," sum"," max"," min"," countValueOccurences"," addFront",
" addBack","removeFront","removeBack","clear","isSorted","isSortedR","hasDuplicate","equal","equalR","search" };
struct node
{
int data;
node * next;
};
void printForward(const node *);
void printReverse(const node *);
int length(const node *); // count the number of nodes in the linked list
int lengthR(const node *);
int sum(const node *); // sum the data values in the linked list
int max(const node *); // assume linked list is not empty
int min(const node *); // assume linked list is not empty
int countValueOccurences(const node *, int valueToTally);
void addFront(node * &, int);
void addBack(node * &, int);
void removeFront(node * &); // if the list is empty, just return
void removeBack(node * &); // if the list is empty, just return
void clear(node * &); // return all heap memory
bool isSorted(const node *); // check if in ascending order, ok to have adjacent equal values
bool isSortedR(const node *);
bool hasDuplicate(const node *);
bool equal(const node *, const node *); // same number of members and all corresponding members are equal
bool equalR(const node *, const node *);
const node * search(const node *, int); // return the addres of the first node found holding the dat value, returnn nullptr if not found
// Utility functions written by instructor
void buildSpecificLinkedList(node * & start);
void buildFromArray(node * & start, const int * theArray, int howMany);
void returnMemory(node * & start);
int menu();
void main()
{
node * testLL = nullptr;
node * testLL2 = nullptr;
node * testLL3 = nullptr;
node * testLL4 = nullptr;
node * testLL5 = nullptr;
int testData[10] = { 8,2,9,6,2,12,2,6,1,7 };
int testData2[10] = { 8,2,9,6,2,12,2,6,1,7 };
int testData3[10] = { 8,3,4,5,8,51,4,0,9,7 };
int testData4[5] = { 1, 3, 5, 3, 5 };
int testData5[5] = { 1, 2, 3, 4, 5};
buildFromArray(testLL, testData, 10);
buildFromArray(testLL2, testData2, 10);
buildFromArray(testLL3, testData3, 10);
buildFromArray(testLL4, testData4, 5);
buildFromArray(testLL5, testData5, 5);
int choice = 0;
while (choice != -1)
{
choice = menu();
switch (choice) {
case 0: cout << "testing " << names[choice] << endl;
printForward(testLL);
break;
case 1: cout << "testing " << names[choice] << endl;
printReverse(testLL);
break;
case 2: cout << "testing " << names[choice] << endl;
cout << "length is " << length(testLL) << endl;
break;
case 3: cout << "testing " << names[choice] << endl;
cout << "length is " << lengthR(testLL) << endl;
break;
case 4: cout << "testing " << names[choice] << endl;
cout << "sum is " << sum(testLL) << endl;
break;
case 5: cout << "testing " << names[choice] << endl;
cout << "max is " << max(testLL) << endl;
break;
case 6: cout << "testing " << names[choice] << endl;
cout << "min is " << min(testLL) << endl;
break;
case 7: cout << "testing " << names[choice] << endl;
int valueToCount;
cout << "Enter value to tally ";
cin >> valueToCount;
cout << "tally is " << countValueOccurences(testLL, valueToCount) << endl;
break;
case 8: cout << "testing " << names[choice] << endl;
int valueToAddFront;
cout << "Enter the value to add at the front ";
cin >> valueToAddFront;
addFront(testLL, valueToAddFront);
break;
case 9: cout << "testing " << names[choice] << endl;
int valueToAddBack;
cout << "Enter the value to add at the back ";
cin >> valueToAddBack;
addBack(testLL, valueToAddBack);
break;
case 10: cout << "testing " << names[choice] << endl;
removeFront(testLL);
break;
case 11: cout << "testing " << names[choice] << endl;
removeBack(testLL);
break;
case 12: cout << "testing " << names[choice] << endl;
clear(testLL);
break;
case 13: cout << "testing " << names[choice] << endl;
cout << "is sorted " << isSorted(testLL) << endl;
cout << "is sorted " << isSorted(testLL4) << endl;
cout << "is sorted " << isSorted(testLL5) << endl;
break;
case 14: cout << "testing " << names[choice] << endl;
cout << "is sorted R " << isSortedR(testLL) << endl;
break;
case 15: cout << "testing " << names[choice] << endl;
cout << "has duplicate " << hasDuplicate(testLL) << endl;
break;
case 16: cout << "testing " << names[choice] << endl;
cout << "is equal " << equal(testLL, testLL2) << endl;
cout << "is equal " << equal(testLL, testLL3) << endl;
break;
case 17: cout << "testing " << names[choice] << endl;
// need code to test equarR
break;
case 18: cout << "testing " << names[choice] << endl;
int valueToSearchFor;
cout << "Enter value to search for ";
cin >> valueToSearchFor;
cout << "value found in node with address " << search(testLL, valueToSearchFor) << endl;
break;
default: cout << "Invalid choice" << endl;
break;
}; // end switch
} // end while
} // end main
The above code contains all of the function declarations for a Linked List. I am required to write a couple of recursive functions. I am unsure how. The following functions MUST be written in recusrive form. Thank you.
bool isSortedR(const node * start)//This function will return true or false depending on whether or not the Linked List is sorted
{
}
bool equalR(const node * left, const node * right) //This function will return true if the two lists are equal and false if they are not
{
return false;
}
I mainly don't understand how recusrion works with boolean functions. Any advice or tips are appreciated. Thanks!
Explanation / Answer
Here are the recursive versions for you:
bool isSortedR(const node * start)
//This function will return true or false depending on whether or not the Linked List is sorted
{
if(start == NULL) //If there are no elements in the list.
return true;
if(start->next == NULL) //If there is only one element in the list.
return true;
if(start->data < start->next->data) //If the first two elements are sorted.
return isSortedR(start->next); //Check with the other elements.
else
return false;
}
bool equalR(const node * left, const node * right)
//This function will return true if the two lists are equal and false if they are not
{
if(left == NULL && right != NULL) //If left terminates and not the right.
return false;
if(right == NULL && left != NULL) //If right terminates and not the left.
return false;
if(left == NULL && right == NULL) //If both lists are empty.
return true;
if(left->data != right->data)
return false;
return equalR(left->next, right->next);
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.