Practice Exercise
Union of Two List Sets
Your task is to write a function, listSetUnion
, that takes two lists representing sets and returns a new list that represents the union of those sets. For example, if the two lists are [4, 3, 1, 7, 6] and [3, 2, 5, 1, 6], the function should return a list containing the elements 1, 2, 3, 4, 5, 6 and 7. The values in the returned list may be in any order. Since the given lists represent sets, you may assume that no value appears more than once in a list.
Assumptions and Constraints
- No value appears more than once in a list.
- You must not use arrays.
- You must not modify the given lists.
Download
While in your practice exercises directory, run the following command:
unzip /web/cs2521/practice-exercises/lists/listSetUnion/downloads/listSetUnion.zip
If you're working at home, download listSetUnion.zip
by clicking on the above link and then unzip the downloaded file.
Files
list.c | Contains the implementation of basic list functions |
list.h | Contains the definition of the list data structure and function prototypes |
testListSetUnion.c | Contains the main function, which reads in two lists from standard input, calls listSetUnion , sorts the returned list, and prints out the result. |
listSetUnion.c | Contains listSetUnion , the function you must implement |
Makefile | A makefile to compile your code |
tests/ | A directory containing the inputs and expected outputs for some basic tests |
autotest | A script that uses the tests in the tests directory to autotest your solution. You should only run this after you have tested your solution manually. |
Examples
./testListSetUnion Enter list 1: 4 3 1 7 6 Enter list 2: 3 2 1 5 6 Set 1: {4, 3, 1, 7, 6} Set 2: {3, 2, 1, 5, 6} Union: {1, 2, 3, 4, 5, 6, 7}
./testListSetUnion Enter list 1: 1 3 5 7 9 Enter list 2: 8 6 4 2 0 Set 1: {1, 3, 5, 7, 9} Set 2: {8, 6, 4, 2, 0} Union: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
./testListSetUnion Enter list 1: Enter list 2: 1 8 3 9 Set 1: {} Set 2: {1, 8, 3, 9} Union: {1, 3, 8, 9}
./testListSetUnion Enter list 1: Enter list 2: Set 1: {} Set 2: {} Union: {}
Testing
You can compile and test your function using the following commands:
make # compiles the program ./testListSetUnion # tests with manual input, outputs to terminal ./testListSetUnion < input-file # tests with input from a file, outputs to terminal ./testListSetUnion < tests/01.in # for example, tests with input from tests/01.in # (then manually compare with tests/01.exp)
After you have manually tested your solution, you can autotest it by running ./autotest
. This will run some basic tests on your program, as well as check for memory leaks/errors.
It is possible to devise your own tests by creating your own input files. See the existing input files for examples. Note that you will need to check the output yourself.