Question

(C++)

You are tasked with implementing a recursive function void distanceFrom(int key) on the IntList class (provided). The function will first search through the list for the provided key, and then, recursively, change all previous values in the list to instead be their distance from the node containing the key value. Do not update the node containing the key value or any nodes after it. If the key does not exist in the list, each node should contain its distance from the end of the list.

The function must be recursive, you are not allowed to use any kind of loop. You also may NOT use global or static variables.

IntList.h:

#ifndef __INTLIST_H__
#define __INTLIST_H__

#include <ostream>

using namespace std;

struct IntNode {
int data;
IntNode *next;
IntNode(int data) : data(data), next(nullptr) {}
};

class IntList {

private:
IntNode *head;

public:

/* Initializes an empty list.
*/
IntList() : head(nullptr) {}

/* Inserts a data value to the front of the list.
*/
void push_front(int val) {
if (!head) {
head = new IntNode(val);
} else {
IntNode *temp = new IntNode(val);
temp->next = head;
head = temp;
}
}

/* Outputs to a single line all of the int values stored in the list, each separated by a space.
This function does NOT output a newline or space at the end.
*/
friend ostream & operator<<(ostream &out, const IntList &rhs) {
if (rhs.head) {
IntNode *curr = rhs.head;
out << curr->data;
for (curr = curr->next ; curr ; curr = curr->next) {
out << ' ' << curr->data;
}
}
return out;
}


/* Update all nodes previous to the node containing the passed in integer to be the distance from that node
(1 for the node directly preceding it)
No return value. Works by calling a recursive function (defined below).
*/
void distanceFrom(int);

private:

/* Recursive helper functions that will (1) find the key passed in and then
(2) recursively update the nodes preceding it to contain their distance from the node containing the key.
If the key is not found, update with the distance from the end, with the last node having the value of 1.
*/
int searchAndModify(IntNode *, int);
};

#endif

IntList.cpp:

#include "IntList.h"

void IntList::distanceFrom(int key) {
IntNode *cur = head;
IntNode *prv = head;
int i = 0;

while (cur != nullptr && cur->data != key) {
prv = cur;
cur = cur->next;
i++;
}
prv->data = searchAndModify(head, i);
}

int IntList::searchAndModify(IntNode *curr, int key) {
if (key == 1) {
return 1;
} else {
curr->data = key;
return searchAndModify(curr->next, key - 1);
}
}

Main.cpp:

#include <iostream>

using namespace std;

#include "IntList.h"

int main() {

int testNum;

cout << "Enter test number: ";
cin >> testNum;
cout << endl;

if (testNum == 1) {
IntList test1;
test1.push_front(-3);
test1.push_front(1);
test1.push_front(5);
test1.push_front(8);
test1.push_front(2);
test1.push_front(4);
test1.push_front(0);
test1.push_front(9);
cout << "Key is 8" << endl;
cout << "Before: " << test1 << endl;
test1.distanceFrom(8);
cout << "After : " << test1 << endl;
}

// Test exists function
if (testNum == 2) {
IntList test2;
test2.push_front(-3);
test2.push_front(8);
test2.push_front(10);
test2.push_front(-42);
test2.push_front(3);
test2.push_front(58);
cout << "Key is -3" << endl;
cout << "Before: " << test2 << endl;
test2.distanceFrom(-3);
cout << "After : " << test2 << endl;
}

return 0;
}

Answer 1

//InList.cpp file

#include "IntList.h"

void IntList::distanceFrom(int key) {

searchAndModify(head,key);

}

int IntList::searchAndModify(IntNode *curr, int key) {

if(curr == NULL || curr->data == key)

return 0;

return curr->data = (1 + searchAndModify(curr->next, key));

}

===================================================
SEE OUTPUT

Thanks, PLEASE COMMENT if there is any concern.