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