Machine Problem 3 - Linked List For this assignment you will write a program tha
ID: 3783299 • Letter: M
Question
Machine Problem 3 - Linked List
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
Explanation / Answer
#include<stdlib.h>
#include<assert.h>
/* Link list node */
struct node
{
int data;
struct node* next;
};
/* pull off the front node of the source and put it in dest */
void MoveNode(struct node** destRef, struct node** sourceRef);
/* Takes two lists sorted in increasing order, and splices
their nodes together to make one big sorted list which
is returned. */
struct node* SortedMerge(struct node* a, struct node* b)
{
/* 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;
}
return(dummy.next);
}
/* UTILITY FUNCTIONS */
/* MoveNode() function takes the node from the front of the
source, and move it to the front of the dest.
It is an error to call this with the source list empty.
Before calling MoveNode():
source == {1, 2, 3}
dest == {1, 2, 3}
Affter calling MoveNode():
source == {2, 3}
dest == {1, 1, 2, 3} */
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;
}
/* Function to insert a node at the beginging of the
linked list */
void push(struct node** head_ref, int new_data)
{
/* allocate node */
struct node* new_node =
(struct node*) malloc(sizeof(struct node));
/* put in the data */
new_node->data = new_data;
/* link the old list off the new node */
new_node->next = (*head_ref);
/* move the head to point to the new node */
(*head_ref) = new_node;
}
/* Function to print nodes in a given linked list */
void printList(struct node *node)
{
while (node!=NULL)
{
printf("%d ", node->data);
node = node->next;
}
}
/* Drier program to test above functions*/
int main()
{
/* Start with the empty list */
struct node* res = NULL;
struct node* a = NULL;
struct node* b = NULL;
/* Let us create two sorted linked lists to test
the functions
Created lists, a: 5->10->15, b: 2->3->20 */
push(&a, 15);
push(&a, 10);
push(&a, 5);
push(&b, 20);
push(&b, 3);
push(&b, 2);
/* Remove duplicates from linked list */
res = SortedMerge(a, b);
printf("Merged Linked List is: ");
printList(res);
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.