Question

Create a C++ integer linked list program that performs the following methods below:

Please create these three source files: intList.h, intList.cpp, & intListTest.cpp.

Implement recursive routines in the intList class to do the following:

• Print the list in reverse order
• Return the value in the middle node
• Return the average of all the odd values
• Remove every node containing an odd value

Modify main (in IntListTest.cpp) so it does the following:

1. Insert the numbers 1, 3, 4, 6, 7, 10, 15, 20, 33.
2. Find the sum of all values.
3. Print the list in reverse order.
4. Print the value of the middle node.
5. Print the average of all the odd values.
6. Remove every node containing an odd value.
7. Print the list in reverse order.
8. Print the value of the middle node.

Steps 3-8 must use recursion.

Please follow requirements.

Answer 1

Note: The language used is C++. The code might not be indented in this editor, so refer to code snippets for clarity.

Code:

1. intListTest.cpp File

#include<iostream>
#include "intList.h"
using namespace std;

int main()
{
intList List;
List.insertNode(1);
List.insertNode(3);
List.insertNode(4);
List.insertNode(6);
List.insertNode(7);
List.insertNode(10);
List.insertNode(15);
List.insertNode(20);
List.insertNode(33);

cout<<"Sum of values in Linked List = "<<List.getSum()<<endl;
List.printReverseList();

cout<<"The middle element is "<<List.getMiddle()<<endl;

cout<<"The average of all odd nodes is "<<List.getAverageOfOddValues()<<endl;

cout<<"\nRemoving odd values...\n";
List.removeOddValues();

cout<<endl;
List.printReverseList();

cout<<"The middle element is "<<List.getMiddle()<<endl;

return 0;
}

2. intList.h File

#ifndef INTLIST_H
#define INTLIST_H

struct Node{
int data;
Node *next;
};

class intList
{
public:
intList();

void insertNode(int data);

int getSum();
void printReverseList();
int getMiddle();
float getAverageOfOddValues();
void removeOddValues();

private:
Node *head;
Node* createNode(int data);
void printReverseListRecur(Node *head);
void getMiddleRecur(Node *head, int &n, Node* &middle);
void getSumOfOddValues(Node *head, int & sumOfOddValues, int & n);
void removeOddValuesUtil(Node* &head);
};

#endif // INTLIST_H

3. intList.cpp File

#include<iostream>
#include "intList.h"
using namespace std;

intList::intList()
{
head = NULL;
}

Node* intList :: createNode(int data)
{
Node *newNode = new Node;
newNode->data = data;
newNode->next = NULL;
return newNode;
}

void intList :: insertNode(int data)
{
Node *newNode = createNode(data);
if(head == NULL){
head = newNode;
return;
}
Node *curr = head;
while(curr->next != NULL)
curr = curr->next;

curr->next = newNode;
}

void intList :: printReverseList()
{
cout<<"The reversed list is :\n";
printReverseListRecur(head);
cout<<"\n";
}

void intList :: printReverseListRecur(Node *head)
{
if(head == NULL)
return;
printReverseListRecur(head->next);
cout<<head->data<<" ";
}

int intList :: getSum()
{
Node *curr = head;
int sum = 0;
while(curr != NULL){
sum = sum + curr->data;
curr = curr->next;
}
return sum;
}

int intList :: getMiddle()
{
int n = 1;
Node *middle = NULL;
getMiddleRecur(head, n, middle);
return middle->data;
}

void intList :: getMiddleRecur(Node *head, int &n, Node* &middle)
{
if(head == NULL){
n = n/2;
return;
}
n++;
getMiddleRecur(head->next, n, middle);

n--;
if(n == 0)
middle = head;
}

float intList :: getAverageOfOddValues()
{
int n = 0;
int sumOfOddValues = 0;
getSumOfOddValues(head, sumOfOddValues, n);
float avg = sumOfOddValues*1.0/n;
return avg;
}

void intList :: getSumOfOddValues(Node *head, int & sumOfOddValues, int & n)
{
if(head == NULL)
return;
if(head->data % 2 != 0){
sumOfOddValues += head->data;
n++;
}
getSumOfOddValues(head->next, sumOfOddValues, n);
}

void intList :: removeOddValues()
{
//Node *curr = head;
//Node *prev = NULL;
removeOddValuesUtil(head);
}

void intList :: removeOddValuesUtil(Node* &head)
{
if(head == NULL)
return;

Node *curr = head;
Node *prev = NULL;

while(curr){
//cout<<curr->data<<endl;
if(curr->data % 2 != 0){
if(curr == head){
head = curr->next;
delete curr;
curr = head;
}else{
Node *temp = curr;
curr = curr->next;
prev->next = curr;
delete temp;
}
}else{
prev = curr;
curr = curr->next;
}
}
}

Code Snippets:

1. intListTest.cpp File

2. intList.h File

3. intList.cpp File

Sample Output: