Tools Window Help .. CSC228-Fal 2017-Prolect-2-List. Print-MergeList.pdf (page 1
ID: 3870926 • Letter: T
Question
Tools Window Help .. CSC228-Fal 2017-Prolect-2-List. Print-MergeList.pdf (page 1 of 2) Q Search Question 1 Q2- 25 pts) Add a member function mergeList to the Singly Linked List-based implementation of the List ADT. The member function takes as input a List object (representing the list of smaller size) as parameter and appends it to the List object (representing the list of larger size) on which the function will be called. Consider largerlntegerList and smallerintegerList to be the two List objects in the main function. The main function should call largerIntegerList.mergeList(smallerIntegerList) and then print the contents of the largerintegerList using the IterativePrint() member function by calling largerlntegerList.IterativePrint) from main. The mergeList member function will append the elements of the smallerIntegerList to the end of the largerlIntegerList. Use the Singly Linked List code for Question 2 attached in this project description. For example: If largerIntegerlist is 78--> 14--> 52 96 52 63 and the smaller Integer List is 44--> 22--> 11, then the contents of the largerIntegrList after the merger should be: 78-1452>96-52>63->44>22->11. 27Explanation / Answer
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
/* Link list node */
struct Node
{
int data;
struct Node* next;
};
/* Given a reference (pointer to pointer) to the head
of a list and an int, push a new node on the front
of the list. */
void insert_at_last(struct Node** head_ref, int new_data)
{
/* allocate node */
struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
struct Node *last = *head_ref; /* used in step 5*/
/* 2. put in the data */
new_node->data = new_data;
/* 3. This new node is going to be the last node, so make next of
it as NULL*/
new_node->next = NULL;
/* 4. If the Linked List is empty, then make the new node as head */
if (*head_ref == NULL)
{
*head_ref = new_node;
return;
}
/* 5. Else traverse till the last node */
while (last->next != NULL)
last = last->next;
/* 6. Change the next of last node */
last->next = new_node;
return;
}
void Node_shuffle(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;
}
/* Counts no. of nodes in linked list */
int length_LL(struct Node* head)
{
int count = 0; // Initialize count
struct Node* current = head; // Initialize current
while (current != NULL)
{
count++;
current = current->next;
}
return count;
}
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 (b!=NULL)
{
if(a!=NULL)
{
Node_shuffle(&(tail->next), &a);
}
else
{
Node_shuffle(&(tail->next), &b);
}
tail = tail->next;
}
return(dummy.next);
}
void printList(struct Node *node)
{
while (node!=NULL)
{
printf("%d ", node->data);
node = node->next;
}
}
/* Drier program to test count function*/
int main()
{
/* Start with the empty list */
struct Node* l1 = NULL;
struct Node* l2 = NULL;
struct Node* result;
insert_at_last(&l1, 78);
insert_at_last(&l1, 14);
insert_at_last(&l1, 52);
insert_at_last(&l1, 96);
insert_at_last(&l1, 52);
insert_at_last(&l1, 63);
insert_at_last(&l2, 44);
insert_at_last(&l2, 22);
insert_at_last(&l2, 11);
if(length_LL(l1)>length_LL(l2))
{
result = SortedMerge(l1, l2);
}
else
{
result = SortedMerge(l2, l1);
}
printf("Merged Linked List is: ");
printList(result);
return 0;
}