Set Difference
Time limit: 5000ms
Memory limit: 256mb
Description:
Given two arrays 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 compute the difference of 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>
struct Node {
int Element;
struct Node * Left;
struct Node * Right;
}; // structure of set element
struct Set {
struct Node * set_node;
}; // structure of Set
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 doubly linked list
struct Set * set_diff(struct Set * a, struct Set * b); // calculate the difference of two integer sets: integer set a and integer set b. PS: diff(a, b) = a - b
void print_set(struct Set * r); // output the elements in the integer set in ascending.
void arr_diff(int a[], int b[], int size_a, int size_b); // output (in ascending order) the difference of two sets 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->Left = NULL;
temp->Right = 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. (Doubly 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->Left = NULL;
temp->Right = NULL;
r = temp;
return r;
} else {
struct Node* tmp = r;
struct Node* last = NULL;
while (tmp->Left) {
tmp = tmp->Left;
}
while (tmp != NULL && x > tmp->Element) {
last = tmp;
tmp = tmp->Right;
}
if (tmp == NULL) {
struct Node * temp = (struct Node *)malloc(sizeof(struct Node));
temp->Element = x;
temp->Left = last;
temp->Right = NULL;
last->Right = temp;
} else if (tmp->Element != x) {
struct Node * temp = (struct Node *)malloc(sizeof(struct Node));
temp->Element = x;
temp->Left = last;
temp->Right = tmp;
tmp->Left = temp;
if (last) {
last->Right = temp;
}
}
}
return r;
}
/**
* @brief: calculate the difference of two integer sets: integer set a and integer set b. PS: diff(a, b) = a - b
* @param: 1. Set pointer a 2. Set pointer b
* @return: 1. Set pointer a which points at the difference
* @usage: a = set_diff(a, b)
*/
struct Set * set_diff(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;
while (a_node_now->Left != NULL) {
a_node_now = a_node_now->Left;
}
while (b_node_now->Left != NULL) {
b_node_now = b_node_now->Left;
}
struct Node * a_head = a_node_now;
while (a_node_now != NULL && b_node_now != NULL) {
if (a_node_now->Element == b_node_now->Element) {
if (a_node_now->Left) {
a_node_now->Left->Right = a_node_now->Right;
} else {
a_head = a_node_now->Right;
}
if (a_node_now->Right) {
a_node_now->Right->Left = a_node_now->Left;
}
tmp = a_node_now->Right;
free(a_node_now);
a_node_now = tmp;
b_node_now = b_node_now->Right;
} else if (a_node_now->Element < b_node_now->Element) {
a_node_now = a_node_now->Right;
} else {
b_node_now = b_node_now->Right;
}
}
a->set_node = a_head;
return a;
}
/**
* @brief: print the element of a Set in the increasing 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->Left) {
tmp = tmp->Left;
}
while (tmp) {
printf("%d ", tmp->Element);
tmp = tmp->Right;
}
}
// 1. you should create set A and B and insert the elements in the array a and b into set A and B
// 2. calculate the difference between two sets (A-B)
// 3. print the difference
void arr_diff(int a[], int b[], int size_a, int size_b) {
// WRITE YOUR CODE HERE
// DO NOT MODIFY THE OTHER CODE
}
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;
}
arr_diff(arr_a, arr_b, size_a, size_b);
printf("\n");
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:
You should output the difference of setA and setB in ascending order.
Sample Input 1:
7
1 2 5 6 8 9 10
5
1 2 3 4 8
Sample Output 1:
5 6 9 10
Submit