Practice Exercise
Merging Two Ordered Lists
Your task is to write a function, listMergeOrdered
, that takes two ordered lists and merges their values into a new ordered list. For example, if the two lists are [1, 5, 7, 8] and [2, 3, 4, 6, 9], the function should return the list [1, 2, 3, 4, 5, 6, 7, 8, 9].
Assumptions and Constraints
- The given lists are sorted in ascending order.
- 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/listMergeOrdered/downloads/listMergeOrdered.zip
If you're working at home, download listMergeOrdered.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 |
testListMergeOrdered.c | Contains the main function, which reads in two lists from standard input, calls listMergeOrdered , and prints out the result. |
listMergeOrdered.c | Contains listMergeOrdered , 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
./testListMergeOrdered Enter list 1: 1 5 7 8 Enter list 2: 2 3 4 6 9 List 1: [1] -> [5] -> [7] -> [8] -> X List 2: [2] -> [3] -> [4] -> [6] -> [9] -> X Merged: [1] -> [2] -> [3] -> [4] -> [5] -> [6] -> [7] -> [8] -> [9] -> X
./testListMergeOrdered Enter list 1: 1 2 4 8 9 Enter list 2: 3 5 6 List 1: [1] -> [2] -> [4] -> [8] -> [9] -> X List 2: [3] -> [5] -> [6] -> X Merged: [1] -> [2] -> [3] -> [4] -> [5] -> [6] -> [8] -> [9] -> X
./testListMergeOrdered Enter list 1: 2 3 4 4 5 7 8 Enter list 2: 1 4 7 List 1: [2] -> [3] -> [4] -> [4] -> [5] -> [7] -> [8] -> X List 2: [1] -> [4] -> [7] -> X Merged: [1] -> [2] -> [3] -> [4] -> [4] -> [4] -> [5] -> [7] -> [7] -> [8] -> X
./testListMergeOrdered Enter list 1: Enter list 2: 1 3 4 5 6 8 9 List 1: X List 2: [1] -> [3] -> [4] -> [5] -> [6] -> [8] -> [9] -> X Merged: [1] -> [3] -> [4] -> [5] -> [6] -> [8] -> [9] -> X
Testing
You can compile and test your function using the following commands:
make # compiles the program ./testListMergeOrdered # tests with manual input, outputs to terminal ./testListMergeOrdered < input-file # tests with input from a file, outputs to terminal ./testListMergeOrdered < 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.