Practice Exercise
Counting Duplicates
Your task is to write a function, listNumDuplicates, that returns the number of duplicate elements in the given linked list, which you can assume is ordered. The number of duplicate elements is the minimum number of elements that would need to be removed to obtain a list with no duplicates. For example, the list [1, 2, 2, 3, 3, 3] contains three duplicate elements, because three elements would need to be removed to obtain a list with no duplicates: 2, 3 and 3. (However, you should not actually remove any elements - you should simply return the number of duplicate values.)
Assumptions and Constraints
- The given list is sorted in either ascending or descending order.
- You must not use arrays.
- You must not use any variant of
malloc, either directly or indirectly. - You must not modify the given list.
Download
While in your practice exercises directory, run the following command:
unzip /web/cs2521/practice-exercises/lists/listNumDuplicates/downloads/listNumDuplicates.zip
If you're working at home, download listNumDuplicates.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 |
| testListNumDuplicates.c | Contains the main function, which reads in a list from standard input, calls listNumDuplicates, and prints out the result. |
| listNumDuplicates.c | Contains listNumDuplicates, 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
Your program should behave like these examples:
./testListNumDuplicates Enter list: 1 2 3 4 5 5 5 listNumDuplicates returned 2
Explanation: two elements would need to be removed to obtain a list with no duplicates: 5 and 5.
./testListNumDuplicates Enter list: 1 1 1 1 1 1 1 listNumDuplicates returned 6
Explanation: six elements would need to be removed to obtain a list with no duplicates: 1, 1, 1, 1, 1 and 1.
./testListNumDuplicates Enter list: 6 6 5 5 4 4 3 3 2 2 1 1 0 listNumDuplicates returned 6
Explanation: six elements would need to be removed to obtain a list with no duplicates: 6, 5, 4, 3, 2 and 1.
./testListNumDuplicates Enter list: 1 1 1 1 1 1 2 2 3 4 5 5 5 5 listNumDuplicates returned 9
Explanation: nine elements would need to be removed to obtain a list with no duplicates: 1, 1, 1, 1, 1, 2, 5, 5 and 5.
Testing
You can compile and test your function using the following commands:
make # compiles the program ./testListNumDuplicates # tests with manual input, outputs to terminal ./testListNumDuplicates < input-file # tests with input from a file, outputs to terminal ./testListNumDuplicates < 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.