Question

Machine Problem 3 - Linked List C++

For this assignment you will write a program that inserts 20 random integers from 0 to 100 in order in a linked list object. The program will create another linked list, but with 15 random integers from 0 – 100 in order. The program then will merge those two ordered linked list into a single ordered list.

The function merge should receive references to each of the list objects to be merged and a reference to a list object into which the merged elements will be placed. There should be no duplicate numbers in the final list.

Calculate the sum of the elements and the floating-point average of the elements.

Don’t use the STL linked list, you need to build your own linked list. You may use the one in the lecture’s example.

An example of the output:

If the first list has
10, 22, 34, 45, 48, 55, 56, 57, 57, 69, 70, 72, 74, 74, 80, 83, 84, 85, 88, 88

And the second list has
50, 55, 57, 79, 81, 84, 87, 88, 90, 92, 95, 95, 95, 96, 99

The result will:
10, 22, 34, 45, 48, 50, 55, 56, 57, 69, 70, 72, 74, 79, 80, 81, 83, 84, 85, 87, 88, 90, 92, 95, 96, 99

The sum of the final list’s elements is : xxxxx
The average of the final list is : xxxx.xx

Please upload the following:

The class .cpp file

The main program

The class .h file

Output File

Answer 1

// LinkedList.h

#ifndef LL_H_INCLUDED
#define LL_H_INCLUDED

/* Link list node */
struct node
{
int data;
struct node* next;
};

void sortedInsert(struct node** head_ref, struct node* new_node);
struct node *newNode(int new_data);
void printList(struct node *head);
void removeDuplicate(struct node **c);
void SortedMerge(struct node* a, struct node *b, struct node **c);
int sum(struct node *head);
double average(struct node *head);
#endif // LL_H_INCLUDED

//LinkedList.cpp

/* Program to insert in a sorted list */
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#include "LinkedList.h"

using namespace std;

/*
Function to insert node in sorted order
*/
void sortedInsert(struct node** head_ref, struct node* new_node)
{
struct node* current;
/* Special case for the head end */
if (*head_ref == NULL || (*head_ref)->data >= new_node->data)
{
new_node->next = *head_ref;
*head_ref = new_node;
}
else
{
/* Locate the node before the point of insertion */
current = *head_ref;
while (current->next!=NULL &&
current->next->data < new_node->data)
{
current = current->next;
}
new_node->next = current->next;
current->next = new_node;
}
}

/* A utility function to create a new node */
struct node *newNode(int new_data)
{
/* allocate node */
struct node* new_node =
(struct node*) malloc(sizeof(struct node));

/* put in the data */
new_node->data = new_data;
new_node->next = NULL;

return new_node;
}

/* Function to print linked list */
void printList(struct node *head)
{
struct node *temp = head;
while(temp != NULL)
{
printf("%d ", temp->data);
temp = temp->next;
}
}

void MoveNode(struct node** destRef, struct node** sourceRef)
{
/* the front source node */
struct node* newNode = *sourceRef;
assert(newNode != NULL);

/* Advance the source pointer */
*sourceRef = newNode->next;

/* Link the old dest off the new node */
newNode->next = *destRef;

/* Move dest to point to the new node */
*destRef = newNode;
}

/*
Utility function to removed duplicates
*/
void removeDuplicate(struct node **c)
{
struct node *temp = *c;
//printf("%d\n", temp->data);
while(temp != NULL && temp->next != NULL)
{
if (temp->data == temp->next->data)
{
if (temp->next->next != NULL)
{
temp->next = temp->next->next;
}
else
{
temp->next = NULL;
}
}
else
{
temp = temp->next;
}
}
}

/*
Merge two linked list
*/
void SortedMerge(struct node* a, struct node *b, struct node **c)
{
/* a dummy first node to hang the result on */
struct node dummy;

/* tail points to the last result node */
struct node* tail = &dummy;

/* so tail->next is the place to add new nodes
to the result. */
dummy.next = NULL;
while (1)
{
if (a == NULL)
{
/* if either list runs out, use the
other list */
tail->next = b;
break;
}
else if (b == NULL)
{
tail->next = a;
break;
}
if (a->data <= b->data)
MoveNode(&(tail->next), &a);
else
MoveNode(&(tail->next), &b);

tail = tail->next;
}

*c = dummy.next;
removeDuplicate(c);

}

/* Function to compute sum of linked list */
int sum(struct node *head)
{
int total = 0;
struct node *temp = head;
while(temp != NULL)
{
total += temp->data;
temp = temp->next;
}
}

/* Function to take average of linked list */
double average(struct node *head)
{
double total = 0.0;
int count = 0;
struct node *temp = head;
while(temp != NULL)
{
total += temp->data;
count++;
temp = temp->next;
}

return (total/count);
}

/* Drier program to test function*/
int main()
{
/* Start with the empty list */
struct node* head = NULL;

for(int i = 0; i < 20; i++)
{
int randNum = rand()%(101);
struct node *new_node = newNode(randNum);
sortedInsert(&head, new_node);

}

/* Start with the empty list */
struct node* head2 = NULL;

for(int i = 0; i < 15; i++)
{
int randNum = rand()%(101);
struct node *new_node = newNode(randNum);
sortedInsert(&head2, new_node);

}

printf("\nIf the first list has \n");
printList(head);

printf("\nAnd the second list has\n");
printList(head2);

struct node* res = NULL;
SortedMerge(head, head2, &res);

printf("\nThe result will:\n");

printList(res);

printf("The sum of the final list’s elements is : %d", sum(res));
printf("The average of the final list is : %f", average(res));

return 0;
}