Practice Exercise
Difference of Two List Sets
Your task is to write a function, listSetDifference
, that takes two lists, l1
and l2
, that represent sets and returns a new list representing the set difference l1 - l2
. 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/listSetDifference/downloads/listSetDifference.zip
If you're working at home, download listSetDifference.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 |
testListSetDifference.c | Contains the main function, which reads in two lists from standard input, calls listSetDifference , sorts the returned list, and prints out the result. |
listSetDifference.c | Contains listSetDifference , 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
./testListSetDifference Enter list 1: 4 3 1 7 6 Enter list 2: 6 2 1 5 3 Set 1: {4, 3, 1, 7, 6} Set 2: {6, 2, 1, 5, 3} Difference: {4, 7}
./testListSetDifference 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} Difference: {1, 3, 5, 7, 9}
./testListSetDifference Enter list 1: 9 1 8 2 5 Enter list 2: 1 5 2 9 8 Set 1: {9, 1, 8, 2, 5} Set 2: {1, 5, 2, 9, 8} Difference: {}
Testing
You can compile and test your function using the following commands:
make # compiles the program ./testListSetDifference # tests with manual input, outputs to terminal ./testListSetDifference < input-file # tests with input from a file, outputs to terminal ./testListSetDifference < 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.