Consider the following code for Union of a sorted linked list-based Set, which u

Question

Consider the following code for Union of a sorted linked list-based Set, which uses a merge algorithm. We make a few simplifying assumptions neither input set is empty and we have access to the Sorted List methods through the SetType objects (eg. PutItem, GetLength, etc.) Because we are using a sorted list, the ItemType must overload the "<" relational operator. what should go in block 1,2,3,4,5,6,7

SetType Union(SetType setB) I Reset both sets so we can iterate from the beginning Reset0 setB Reset(): Il The set for storing the union SetType result - new SetType) ItemType a = , Item Type b- i // #2 int alength 0 int blength 0; while (acount

Explanation / Answer

Find cpp code of union of linkedllists........

#include<iostream>
using namespace std;

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

void push(struct Node** head_ref, int new_data)
{
struct Node* new_node =
(struct Node*) malloc(sizeof(struct Node));

  
new_node->data = new_data;

  
new_node->next = (*head_ref);

  
(*head_ref) = new_node;
}

void FrontBackSplit(struct Node* source, struct Node** frontRef,
struct Node** backRef)
{
struct Node* fast;
struct Node* slow;
if (source==NULL || source->next==NULL)
{
  
*frontRef = source;
*backRef = NULL;
}
else
{
slow = source;
fast = source->next;

  
while (fast != NULL)
{
fast = fast->next;
if (fast != NULL)
{
slow = slow->next;
fast = fast->next;
}
}


*frontRef = source;
*backRef = slow->next;
slow->next = NULL;
}
}

struct Node* SortedMerge(struct Node* a, struct Node* b)
{
struct Node* result = NULL;

if (a == NULL)
return(b);
else if (b==NULL)
return(a);

if (a->data <= b->data)
{
result = a;
result->next = SortedMerge(a->next, b);
}
else
{
result = b;
result->next = SortedMerge(a, b->next);
}
return(result);
}

void mergeSort(struct Node** headRef)
{
struct Node *head = *headRef;
struct Node *a, *b;

if ((head == NULL) || (head->next == NULL))
return;

FrontBackSplit(head, &a, &b);

mergeSort(&a);
mergeSort(&b);

*headRef = SortedMerge(a, b);
}

struct Node *getUnion(struct Node *head1, struct Node *head2)
{
struct Node *result = NULL;
struct Node *t1 = head1, *t2 = head2;

while (t1 != NULL && t2 != NULL)
{
if (t1->data < t2->data)
{
push(&result, t1->data);
t1 = t1->next;
}

else if (t1->data>t2->data)
{
push(&result, t2->data);
t2 = t2->next;
}

else
{
push(&result, t2->data);
t1 = t1->next;
t2 = t2->next;
}
}

while (t1 != NULL)
{
push(&result, t1->data);
t1 = t1->next;
}
while (t2 != NULL)
{
push(&result, t2->data);
t2 = t2->next;
}

return result;
}

void printList (struct Node *node)
{
while (node != NULL)
{
printf ("%d ", node->data);
node = node->next;
}
}

int main()
{
struct Node* head1 = NULL;
struct Node* head2 = NULL;
struct Node* intersection_list = NULL;
struct Node* union_list = NULL;

push(&head1, 20);
push(&head1, 4);
push(&head1, 15);
push(&head1, 10);
push(&head1, 11);

push(&head2, 10);
push(&head2, 2);
push(&head2, 4);
push(&head2, 8);

mergeSort(&head1);
mergeSort(&head2);


union_list = getUnion(head1, head2);

printf("First list is ");
printList(head1);

printf(" Second list is ");
printList(head2);

printf(" Union list is ");
printList(union_list);

return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.