Merge Two Sorted Sets
Time limit: 500ms
Memory limit: 256mb
Description:
Given two sorted arrays (in assending order) of non-negative integers, denoted as arrA and arrB.
Please complete the missing part of the following code to create the setA and setB from the array arrA and arrB using the implemented ADT.
Then merge setA and setB with the aid of the implemented ADT and print the result.
-------------------------Copy the following code, complete it and submit-------------------------
/*
I, <Your Full Name>, am submitting the assignment for
an individual project.
I declare that the assignment here submitted is original except for
source material explicitly acknowledged, the piece of work, or a part
of the piece of work has not been submitted for more than one purpose
(i.e. to satisfy the requirements in two different courses) without
declaration. I also acknowledge that I am aware of University policy
and regulations on honesty in academic work, and of the disciplinary
guidelines and procedures applicable to breaches of such policy and
regulations, as contained in the University website
http://www.cuhk.edu.hk/policy/academichonesty/.
It is also understood that assignments without a properly signed
declaration by the student concerned will not be graded by the
teacher(s).
*/
#include <stdio.h>
#include <stdlib.h>
// structure of Node
struct Node {
int Element;
struct Node * Next;
};
// structure of Set
struct Set {
struct Node * set_node;
};
struct Set * init_set(); // create an empty integer set.
struct Set * set_insert(struct Set * r, int x); // insert x into integer set r.
struct Node * node_insert(struct Node * r, int x); // insert x into a linked list.
struct Set * set_merge(struct Set * a, struct Set * b); // merge two sorted sets: integer set a and integer set b.
void print_set(struct Set * r); // output the elements in the integer set in ascending order.
void merge_sorted_set(int a[], int b[], int size_a, int size_b); // merge two sets (in ascending order) that are derived from integer arrays a and b respectively.
/**
* @brief: create an empty integer set
* @param: void
* @return: address of an empty set
* @usage: struct Set* set_a = init_set()
*/
struct Set * init_set() {
struct Set * tmp_set = (struct Set *)malloc(sizeof(struct Set));
tmp_set->set_node = NULL;
return tmp_set;
}
/**
* @brief: insert x into integer set r(if the input set is null, then create and return a new one)
* @param: 1. a Set pointer 2. the value you want to insert
* @return: the address of the set
* @usage: set_a = set_insert(set_a, 2)
*/
struct Set * set_insert(struct Set * r, int x) {
if (r == NULL) {
r = init_set();
}
if (r->set_node == NULL) {
struct Node * temp = (struct Node *)malloc(sizeof(struct Node));
temp->Element = x;
temp->Next = NULL;
r->set_node = temp;
}
else {
r->set_node = node_insert(r->set_node, x);
}
return r;
}
/**
* @brief: help function of the Set ADT, insert a value into a Set. (Linked list insertion)
* @param: 1. set element 2. the value you want to insert
* @return: address of a set element
* @usage: set_node = node_insert(set_node, 2)
*/
struct Node * node_insert(struct Node * r, int x) {
if (r == NULL) {
struct Node * temp = (struct Node *)malloc(sizeof(struct Node));
if (temp == NULL) {
return NULL;
}
temp->Element = x;
temp->Next = NULL;
r = temp;
return r;
}
else {
struct Node* tmp = r;
struct Node* last = NULL;
while (tmp != NULL && x > tmp->Element) {
last = tmp;
tmp = tmp->Next;
}
if (tmp == NULL) {
struct Node * temp = (struct Node *)malloc(sizeof(struct Node));
temp->Element = x;
temp->Next = NULL;
last->Next = temp;
}
else if (tmp->Element != x) {
struct Node * temp = (struct Node *)malloc(sizeof(struct Node));
temp->Element = x;
temp->Next = tmp;
if (last) {
last->Next = temp;
}
}
}
return r;
}
/**
* @brief: merge two integer sets in assending order
* @param: 1. Set pointer a 2. Set pointer b
* @return: 1. Set pointer a which points to the merged set
* @usage: a = merge_set(a, b)
*/
struct Set * merge_set(struct Set * a, struct Set * b) {
struct Node * a_node_now = a->set_node;
struct Node * b_node_now = b->set_node;
struct Node * tmp, * head;
if (a_node_now->Element <= b_node_now->Element) {
head = a_node_now;
tmp = a_node_now;
a_node_now = a_node_now->Next;
}
else {
head = b_node_now;
tmp = b_node_now;
b_node_now = b_node_now->Next;
}
while (a_node_now != NULL && b_node_now != NULL) {
if (a_node_now->Element <= b_node_now->Element) {
tmp->Next = a_node_now;
tmp = tmp->Next;
a_node_now = a_node_now->Next;
}
else {
tmp->Next = b_node_now;
tmp = tmp->Next;
b_node_now = b_node_now->Next;
}
}
if (a_node_now != NULL) {
tmp->Next = a_node_now;
}
else if (b_node_now != NULL) {
tmp->Next = b_node_now;
}
a->set_node = head;
return a;
}
/**
* @brief: print the element of a Set in assending order
* @param: 1. a Set pointer
* @return: void
* @usage: print_set(set_a)
*/
void print_set(struct Set * r) {
if (r == NULL || r->set_node == NULL) {
return;
}
struct Node * tmp = r->set_node;
while (tmp) {
printf("%d ", tmp->Element);
tmp = tmp->Next;
}
}
// 1. you should create set A and B and use the provided ADT for initialization
// 2. insert the elements in the array a and b into set A and B
// 3. merge set A and B and store the results in A
// 4. print the merged set A
void merge_sorted_set(int a[], int b[], int size_a, int size_b) {
// WRITE YOUR CODE HERE
}
// DO NOT MODIFY THE CODE BELOW
int main() {
int i, x;
int size_a;
int size_b;
scanf("%d", &size_a);
int arr_a[size_a];
for (i = 0; i < size_a; i++) {
scanf("%d", &x);
arr_a[i] = x;
}
scanf("%d", &size_b);
int arr_b[size_b];
for (i = 0; i < size_b; i++) {
scanf("%d", &x);
arr_b[i] = x;
}
merge_sorted_set(arr_a, arr_b, size_a, size_b);
return 0;
}
-------------------------------------------End of Code-------------------------------------------
Input:
Four lines, where:
First line is a non-negative integer A;
Second line is arrA of A non-negative integers;
Third line is a non-negative integer B;
Fourth line is arrB of B non-negative integers;
0 <= A, B <= 10^3
Output:
The elements of the merged set in ascending order.
Sample Input 1:
7
1 3 5 7 9 21 23
5
2 4 6 8 25
Sample Output 1:
1 2 3 4 5 6 7 8 9 21 23 25
Submit